{
"cells": [
{
"cell_type": "markdown",
"id": "42c1db60",
"metadata": {},
"source": [
"# Factor Graphs \n",
"\n",
"\n",
"- **[1]** Consider the following state-space model:\n",
"$$\\begin{align*}\n",
"z_k &= A z_{k-1} + w_k \\\\\n",
"x_k &= C z_k + v_k \n",
"\\end{align*}$$\n",
"where $k=1,2,\\ldots,n$ is the time step counter; $z_k$ is an *unobserved* state sequence; $x_k$ is an *observed* sequence; $w_k \\sim \\mathcal{N}(0,\\Sigma_w)$ and $v_k \\sim \\mathcal{N}(0,\\Sigma_v)$ are (unobserved) state and observation noise sequences respectively; $z_0 \\sim \\mathcal{N}(0,\\Sigma_0)$ is the initial state and $A$, $C$, $\\Sigma_v$,$\\Sigma_w$ and $\\Sigma_0$ are known parameters. The Forney-style factor graph (FFG) for one time step is depicted here:\n",
"\n",
"\n",
"\n",
" (a) Rewrite the state-space equations as a set of conditional probability distributions. \n",
" $$\\begin{align*}\n",
" p(z_k|z_{k-1},A,\\Sigma_w) &= \\ldots \\\\\n",
" p(x_k|z_k,C,\\Sigma_v) &= \\ldots \\\\\n",
" p(z_0|\\Sigma_0) &= \\ldots\n",
"\\end{align*}$$ \n",
" > $$\\begin{align*}\n",
" p(z_k|z_{k-1},A,\\Sigma_w) &= \\mathcal{N}(z_k|A z_{k-1},\\Sigma_w) \\\\\n",
" p(x_k|z_k,C,\\Sigma_v) &= \\mathcal{N}(x_k|C z_k,\\Sigma_v) \\\\\n",
" p(z_0|\\Sigma_0) &= \\mathcal{N}(z_0|0,\\Sigma_0)\n",
"\\end{align*}$$ \n",
"\n",
" (b) Define $z^n \\triangleq (z_0,z_1,\\ldots,z_n)$, $x^n \\triangleq (x_1,\\ldots,x_n)$ and $\\theta=\\{A,C,\\Sigma_w,\\Sigma_v\\}$. Now write out the generative model $p(x^n,z^n|\\theta)$ as a product of factors. \n",
" > $$\\begin{align*}\n",
"p(x^n,z^n|\\theta) &= p(z_0|\\Sigma_0) \\prod_{k=1}^n p(x_k|z_k,C,\\Sigma_v) \\,p(z_k|z_{k-1},A,\\Sigma_w) \\\\\n",
" &= \\mathcal{N}(z_0|0,\\Sigma_0) \\prod_{k=1}^n \\mathcal{N}(x_k|C z_k,\\Sigma_v) \\,\\mathcal{N}(z_k|A z_{k-1},\\Sigma_w)\n",
"\\end{align*}$$\n",
"\n",
" (c) We are interested in estimating $z_k$ from a given estimate for $z_{k-1}$ and the current observation $x_k$, i.e., we are interested in computing $p(z_k|z_{k-1},x_k,\\theta)$. Can $p(z_k|z_{k-1},x_k,\\theta)$ be expressed as a Gaussian distribution? Explain why or why not in one sentence. \n",
" > Yes, since the generative model $p(x^n,z^n|\\theta)$ is (one big) Gaussian.\n",
"\n",
" (d) Copy the graph onto your exam paper and draw the message passing schedule for computing $p(z_k|z_{k-1},x_k,\\theta)$ by drawing arrows in the factor graph. Indicate the order of the messages by assigning numbers to the arrows. \n",
" > \n",
" \n",
" > Some permutations of this order are also possible. The most important thing here is that you recognize the tree with $Z_k$ as a root of the tree and pass messages from the terminals (e.g., $Z_{k-1}$, $X_k$, etc.) towards the root. \n",
" \n",
" (e) Now assume that our belief about parameter $\\Sigma_v$ is instead given by a distribution $p(\\Sigma_v)$ (rather than a known value). Adapt the factor graph drawing of the previous answer to reflects our belief about $\\Sigma_v$. \n",
" > See drawing in previous answer. \n",
" \n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f2b614bd",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Julia 1.5.2",
"language": "julia",
"name": "julia-1.5"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.5.2"
}
},
"nbformat": 4,
"nbformat_minor": 5
}