{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Factor Graphs" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "\n", "### Preliminaries\n", "\n", "- Goal \n", " - Introduction to Forney-style factor graphs and message passing algorithms\n", "- Materials \n", " - Mandatory\n", " - These lecture notes \n", " - [Loeliger, 2007](./files/Loeliger-2007-The-factor-graph-approach-to-model-based-signal-processing.pdf), pp. 1295-1300 (until section IV)\n", " - Optional\n", " - [Video lecture](https://www.youtube.com/watch?v=Fv2YbVg9Frc&t=31) by Frederico Wadehn (ETH Zurich) (**highly recommended**)\n", " \n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Why Factor Graphs?\n", "\n", "- A probabilistic inference task gets its computational load mainly through the need for marginalization (i.e., computing integrals). E.g., for a generative model $p(x_1,x_2,x_3,x_4,x_5)$, the inference task $p(x_2|x_3)$ is given by \n", "\n", "$$\\begin{align*}\n", "p(x_2|x_3) = \\frac{\\idotsint p(x_1,x_2,x_3,x_4,x_5) \\, \\mathrm{d}x_1 \\mathrm{d}x_4 \\mathrm{d}x_5}{\\idotsint p(x_1,x_2,x_3,x_4,x_5) \\, \\mathrm{d}x_1 \\mathrm{d}x_2 \\mathrm{d}x_4 \\mathrm{d}x_5}\n", "\\end{align*}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Since these computations suffer from the \"curse of dimensionality\", we often need to solve a simpler problem in order to get an answer. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Factor graphs provide a computationally efficient approach to solving inference problems **if the generative distribution can be factorized**. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Factorization helps. For instance, if $p(x_1,x_2,x_3,x_4,x_5) = p(x_1)p(x_2,x_3)p(x_4)p(x_5|x_4)$, then\n", "\n", "$$\\begin{align*}\n", "p(x_2|x_3) &= \\frac{\\idotsint p(x_1)p(x_2,x_3)p(x_4)p(x_5|x_4) \\, \\mathrm{d}x_1 \\mathrm{d}x_4 \\mathrm{d}x_5}{\\idotsint p(x_1)p(x_2,x_3)p(x_4)p(x_5|x_4) \\, \\mathrm{d}x_1 \\mathrm{d}x_2 \\mathrm{d}x_4 \\mathrm{d}x_5} \n", " = \\frac{p(x_2,x_3)}{\\int p(x_2,x_3) \\mathrm{d}x_2}\n", "\\end{align*}$$\n", "\n", "which is computationally much cheaper than the general case above." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- In this lesson, we discuss how computationally efficient inference in factorized probability distributions can be automated." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Factor Graph Construction Rules\n", "\n", "- Consider a function \n", "$$\n", "f(x_1,x_2,x_3,x_4,x_5) = f_a(x_1,x_2,x_3) \\cdot f_b(x_3,x_4,x_5) \\cdot f_c(x_4)\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- The factorization of this function can be graphically represented by a **Forney-style Factor Graph** (FFG):\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- An FFG is an **undirected** graph subject to the following construction rules ([Forney, 2001](http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=910573&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F18%2F19638%2F00910573.pdf%3Farnumber%3D910573))\n", "\n", " 1. A **node** for every factor;\n", " 1. An **edge** (or **half-edge**) for every variable;\n", " 1. Node $g$ is connected to edge $x$ **iff** variable $x$ appears in factor $g$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Some FFG Terminology\n", "\n", "- $f$ is called the **global function** and $f_\\bullet$ are the **factors**. \n", "\n", "- A **configuration** is an assigment of values to all variables.\n", "\n", "- The **configuration space** is the set of all configurations, i.e., the domain of $f$\n", "\n", "- A configuration $\\omega=(x_1,x_2,x_3,x_4,x_5)$ is said to be **valid** iff $f(\\omega) \\neq 0$\n", " " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Equality Nodes for Branching Points\n", "\n", "\n", "- Note that a variable can appear in maximally two factors in an FFG (since an edge has only two end points)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Consider the factorization (where $x_2$ appears in three factors) \n", "\n", "$$\n", " f(x_1,x_2,x_3,x_4) = f_a(x_1,x_2)\\cdot f_b(x_2,x_3) \\cdot f_c(x_2,x_4)\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- For the factor graph representation, we will instead consider the function $g$, defined as\n", "$$\\begin{align*}\n", " g(x_1,x_2&,x_2^\\prime,x_2^{\\prime\\prime},x_3,x_4) \n", " = f_a(x_1,x_2)\\cdot f_b(x_2^\\prime,x_3) \\cdot f_c(x_2^{\\prime\\prime},x_4) \\cdot f_=(x_2,x_2^\\prime,x_2^{\\prime\\prime})\n", "\\end{align*}$$\n", " where \n", "$$\n", "f_=(x_2,x_2^\\prime,x_2^{\\prime\\prime}) \\triangleq \\delta(x_2-x_2^\\prime)\\, \\delta(x_2-x_2^{\\prime\\prime})\n", "$$\n", "\n", " \n", " " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Equality Nodes for Branching Points, cont'd\n", "\n", "- Note that through introduction of auxiliary variables $X_2^\\prime$ and $X_2^{\\prime\\prime}$ each variable in $g$ appears in maximally two factors. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- The constraint $f_=(x,x^\\prime,x^{\\prime\\prime})$ enforces that $X=X^\\prime=X^{\\prime\\prime}$ **for every valid configuration**." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Since $f$ is a marginal of $g$, i.e., \n", "$$\n", "f(x_1,x_2,x_3,x_4) = \\iint g(x_1,x_2,x_2^\\prime,x_2^{\\prime\\prime},x_3,x_4)\\, \\mathrm{d}x_2^\\prime \\mathrm{d}x_2^{\\prime\\prime}\n", "$$\n", "it follows that any inference problem on $f$ can be executed by a corresponding inference problem on $g$, e.g.,\n", "$$\\begin{align*}\n", "f(x_1 \\mid x_2) &\\triangleq \\frac{\\iint f(x_1,x_2,x_3,x_4) \\,\\mathrm{d}x_3 \\mathrm{d}x_4 }{ \\idotsint f(x_1,x_2,x_3,x_4) \\,\\mathrm{d}x_1 \\mathrm{d}x_3 \\mathrm{d}x_4} \\\\\n", " &= \\frac{\\idotsint g(x_1,x_2,x_2^\\prime,x_2^{\\prime\\prime},x_3,x_4) \\,\\mathrm{d}x_2^\\prime \\mathrm{d}x_2^{\\prime\\prime} \\mathrm{d}x_3 \\mathrm{d}x_4 }{ \\idotsint g(x_1,x_2,x_2^\\prime,x_2^{\\prime\\prime},x_3,x_4) \\,\\mathrm{d}x_1 \\mathrm{d}x_2^\\prime \\mathrm{d}x_2^{\\prime\\prime} \\mathrm{d}x_3 \\mathrm{d}x_4} \\\\\n", " &\\triangleq g(x_1 \\mid x_2)\n", "\\end{align*}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- $\\Rightarrow$ **Any factorization of a global function $f$ can be represented by a Forney-style Factor Graph**." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Probabilistic Models as Factor Graphs\n", "\n", "- FFGs can be used to express conditional independence (factorization) in probabilistic models. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- For example, the (previously shown) graph for \n", "$f_a(x_1,x_2,x_3) \\cdot f_b(x_3,x_4,x_5) \\cdot f_c(x_4)$ \n", "could represent the probabilistic model\n", "$$\n", "p(x_1,x_2,x_3,x_4,x_5) = p(x_1,x_2|x_3) \\cdot p(x_3,x_5|x_4) \\cdot p(x_4)\n", "$$\n", "where we identify \n", "$$\\begin{align*}\n", "f_a(x_1,x_2,x_3) &= p(x_1,x_2|x_3) \\\\\n", "f_b(x_3,x_4,x_5) &= p(x_3,x_5|x_4) \\\\\n", "f_c(x_4) &= p(x_4)\n", "\\end{align*}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- This is the graph\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Inference by Closing Boxes\n", "\n", "- Factorizations provide opportunities to cut on the amount of needed computations when doing inference. In what follows, we will use FFGs to process these opportunities in an automatic way (i.e., by message passing). " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Assume we wish to compute the marginal\n", "$$\n", "\\bar{f}(x_3) = \\sum_{x_1,x_2,x_4,x_5,x_6,x_7}f(x_1,x_2,\\ldots,x_7)\n", "$$\n", "where $f$ is factorized as given by the following FFG\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- Due to the factorization, we can decompose this sum by the **distributive law** as\n", "$$\\begin{align*}\n", "\\bar{f}(x_3) = & \\underbrace{ \\left( \\sum_{x_1,x_2} f_a(x_1)\\,f_b(x_2)\\,f_c(x_1,x_2,x_3)\\right) }_{\\overrightarrow{\\mu}_{X_3}(x_3)} \\\\\n", " & \\underbrace{ \\cdot\\left( \\sum_{x_4,x_5} f_d(x_4)\\,f_e(x_3,x_4,x_5) \\cdot \\underbrace{ \\left( \\sum_{x_6,x_7} f_f(x_5,x_6,x_7)\\,f_g(x_7)\\right) }_{\\overleftarrow{\\mu}_{X_5}(x_5)} \\right) }_{\\overleftarrow{\\mu}_{X_3}(x_3)}\n", "\\end{align*}$$\n", "which is computationally (much) lighter than executing the full sum $\\sum_{x_1,\\ldots,x_7}f(x_1,x_2,\\ldots,x_7)$\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- Messages may flow in both directions on any edge (here on $X_3$). We often draw _directed edges_ in a FFG in order to distinguish forward messages $\\overrightarrow{\\mu}_\\bullet(\\cdot)$ (in the same direction as the arrow of the edge) from backward messages $\\overleftarrow{\\mu}_\\bullet(\\cdot)$ (in opposite direction). With directed edges, the FFG looks as follows: \n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Crucially, drawing arrows on edges is only meant as a notational convenience. Technically, an FFG is an undirected graph. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Note that $\\overleftarrow{\\mu}_{X_5}(x_5)$ is obtained by multiplying all enclosed factors ($f_f$, $f_g$) by the green dashed box, followed by marginalization over all enclosed variables ($x_6$, $x_7$). " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- This is the **Closing the Box**-rule, which is a general recipe for marginalization of hidden variables and leads to a new factor with outgoing (sum-product) message \n", "$$ \\mu_{\\text{SP}} = \\sum_{ \\stackrel{ \\textrm{enclosed} }{ \\textrm{variables} } } \\;\\prod_{\\stackrel{ \\textrm{enclosed} }{ \\textrm{factors} }}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "### Evaluating the closing-the-box rule for individual nodes\n", " \n", "\n", "- First, closing a box around the **terminal nodes** leads to $\\overrightarrow{\\mu}_{X_1}(x_1) \\triangleq f_a(x_1)$, $\\overrightarrow{\\mu}_{X_2}(x_2) \\triangleq f_b(x_2)$ etc. \n", " - So, the message out of a terminal node is the factor itself.\n", " - (Exercise) Derive now that the message coming from the open end of a half-edge always equals $1$. " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- The messages from **internal nodes** evaluate to:\n", "$$\\begin{align*}\n", "\\overrightarrow{\\mu}_{X_3}(x_3) &= \\sum_{x_1,x_2} f_a(x_1) \\,f_b(x_2) \\,f_c(x_1,x_2,x_3) \\\\\n", " &= \\sum_{x_1,x_2} \\overrightarrow{\\mu}_{X_1}(x_1) \\overrightarrow{\\mu}_{X_2}(x_2) \\,f_c(x_1,x_2,x_3) \\\\\n", "\\overleftarrow{\\mu}_{X_5}(x_5) &= \\sum_{x_6,x_7} f_f(x_5,x_6,x_7)\\,f_g(x_7) \\\\\n", " &= \\sum_{x_6,x_7} \\overrightarrow{\\mu}_{X_7}(x_7)\\, f_f(x_5,x_6,x_7) \\\\\n", "\\end{align*}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Crucially, all message update rules can be computed from information that is **locally available** at each node." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Sum-Product Algorithm\n", "\n", "- (**Sum-Product update rule**). This recursive pattern for computing messages applies generally and is called the **Sum-Product update rule**, which is really just a special case of the closing-the-box rule: For any node, the outgoing message is obtained by taking the product of all incoming messages and the node function, followed by summing out (marginalization) all incoming variables. What is left (the outgoing message) is a function of the outgoing variable only: \n", "\n", "$$ \\boxed{\n", "\\overrightarrow{\\mu}_{Y}(y) = \\sum_{x_1,\\ldots,x_n} \\overrightarrow{\\mu}_{X_1}(x_1)\\cdots \\overrightarrow{\\mu}_{X_n}(x_n) \\,f(y,x_1,\\ldots,x_n) }\n", "$$\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- (**Sum-Product Theorem**). If the factor graph for a function $f$ has **no cycles**, then the marginal $\\bar{f}(x_3) = \\sum_{x_1,x_2,x_4,x_5,x_6,x_7}f(x_1,x_2,\\ldots,x_7)$ is given by the Sum-Product Theorem:\n", "\n", "$$ \\boxed{\n", "\\bar{f}(x_3) = \\overrightarrow{\\mu}_{X_3}(x_3)\\cdot \\overleftarrow{\\mu}_{X_3}(x_3)}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- (**Sum-Product Algorithm**). If folows that the marginal $\\bar{f}(x_3) = \\sum_{x_1,x_2,x_4,x_5,x_6,x_7}f(x_1,x_2,\\ldots,x_7)$ can be efficiently computed through sum-product messages. Executing inference through SP message passing is called the **Sum-Product Algorithm**." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- (Exercise) Verfiy for yourself that all maginals in a cycle-free graph (a tree) can be computed exactly by starting with messages at the terminals and working towards the root of the tree." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Processing Observations in a Factor Graph\n", "\n", " - Terminal nodes can be used describe **observed variables**, e.g., use a factor $$f_Y(y) = \\delta(y-3)$$ to terminate the edge for variable $Y$ if $y=3$ is observed.\n", " " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ " \n", " ##### Example\n", " \n", " - Consider a generative model \n", "$$p(x,y_1,y_2) = p(x)\\,p(y_1|x)\\,p(y_2|x) .$$ \n", " - This model expresses the assumption that $Y_1$ and $Y_2$ are independent measurements of $X$.\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ " \n", "- Assume that we are interested in the posterior for $X$ after observing $Y_1= \\hat y_1$ and $Y_2= \\hat y_2$. The posterior for $X$ can be inferred by applying the sum-product algorithm to the following graph:\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ " - (Note that) we usually draw terminal nodes for observed variables in the graph by smaller solid-black squares. This is just to help the visualization of the graph, since the computational rules are no different than for other nodes. " ] }, { "cell_type": "markdown", "metadata": { "collapsed": true, "slideshow": { "slide_type": "fragment" } }, "source": [ "- (Exercise) Can you draw the messages that infer $p(x\\,|\\,y_1,y_2)$?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### CODE EXAMPLE\n", "\n", "We'll use ForneyLab, a factor graph toolbox for Julia, to build the above graph, and perform sum-product message passing to infer the posterior $p(x|y_1,y_2)$. We assume $p(y_1|x)$ and $p(y_2|x)$ to be Gaussian likelihoods with known variances:\n", "$$\\begin{align*}\n", " p(y_1\\,|\\,x) &= \\mathcal{N}(y_1\\,|\\,x, v_{y1}) \\\\\n", " p(y_2\\,|\\,x) &= \\mathcal{N}(y_2\\,|\\,x, v_{y2})\n", "\\end{align*}$$\n", "Under this model, the posterior is given by:\n", "$$\\begin{align*}\n", " p(x\\,|\\,y_1,y_2) &\\propto \\overbrace{p(y_1\\,|\\,x)\\,p(y_2\\,|\\,x)}^{\\text{likelihood}}\\,\\overbrace{p(x)}^{\\text{prior}} \\\\\n", " &=\\mathcal{N}(x\\,|\\,\\hat{y}_1, v_{y1})\\, \\mathcal{N}(x\\,|\\,\\hat{y}_2, v_{y2}) \\, \\mathcal{N}(x\\,|\\,m_x, v_x) \n", "\\end{align*}$$\n", "so we can validate the answer by solving the Gaussian multiplication manually." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "slideshow": { "slide_type": "subslide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Sum-product message passing result: p(x|y1,y2) = 𝒩(1.1428571428571428,0.5714285714285714)\n", "Manual result: p(x|y1,y2) = 𝒩(1.1428571428571428, 0.5714285714285714)\n" ] } ], "source": [ "using ForneyLab \n", "\n", "# Data\n", "y1_hat = 1.0\n", "y2_hat = 2.0\n", "\n", "# Construct the factor graph\n", "fg = FactorGraph()\n", "@RV x ~ GaussianMeanVariance(constant(0.0), constant(4.0), id=:x) # Node p(x)\n", "@RV y1 ~ GaussianMeanVariance(x, constant(1.0)) # Node p(y1|x)\n", "@RV y2 ~ GaussianMeanVariance(x, constant(2.0)) # Node p(y2|x)\n", "Clamp(y1, y1_hat) # Terminal (clamp) node for y1\n", "Clamp(y2, y2_hat) # Terminal (clamp) node for y2\n", "# draw(fg) # draw the constructed factor graph\n", "\n", "# Perform sum-product message passing\n", "eval(Meta.parse(sumProductAlgorithm(x, name=\"_algo1\"))) # Automatically derives a message passing schedule\n", "x_marginal = step_algo1!(Dict())[:x] # Execute algorithm and collect marginal distribution of x\n", "println(\"Sum-product message passing result: p(x|y1,y2) = 𝒩($(mean(x_marginal)),$(var(x_marginal)))\")\n", "\n", "# Calculate mean and variance of p(x|y1,y2) manually by multiplying 3 Gaussians (see lesson 4 for details)\n", "v = 1 / (1/4 + 1/1 + 1/2)\n", "m = v * (0/4 + y1_hat/1.0 + y2_hat/2.0)\n", "println(\"Manual result: p(x|y1,y2) = 𝒩($(m), $(v))\")" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Example: SP Messages for the Equality Node\n", "\n", "- Let´s compute the SP messages for the **equality node** $f_=(x,y,z) = \\delta(z-x)\\delta(z-y)$: \n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "$$\\begin{align*}\n", "\\overrightarrow{\\mu}_{Z}(z) &= \\iint \\overrightarrow{\\mu}_{X}(x) \\overrightarrow{\\mu}_{Y}(y) \\,\\delta(z-x)\\delta(z-y) \\,\\mathrm{d}x \\mathrm{d}y \\\\\n", " &= \\overrightarrow{\\mu}_{X}(z) \\int \\overrightarrow{\\mu}_{Y}(y) \\,\\delta(z-y) \\,\\mathrm{d}y \\\\\n", " &= \\overrightarrow{\\mu}_{X}(z) \\overrightarrow{\\mu}_{Y}(z) \n", "\\end{align*}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- By symmetry, this also implies (for the same equality node) that\n", "\n", "$$\\begin{align*}\n", "\\overleftarrow{\\mu}_{X}(x) &= \\overrightarrow{\\mu}_{Y}(x) \\overleftarrow{\\mu}_{Z}(x) \\quad \\text{and} \\\\\n", "\\overleftarrow{\\mu}_{Y}(y) &= \\overrightarrow{\\mu}_{X}(y) \\overleftarrow{\\mu}_{Z}(y)\\,.\n", "\\end{align*}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "- Let us now consider the case of Gaussian messages $\\overrightarrow{\\mu}_{X}(x) = \\mathcal{N}(\\overrightarrow{m}_X,\\overrightarrow{V}_X)$, $\\overrightarrow{\\mu}_{Y}(y) = \\mathcal{N}(\\overrightarrow{m}_Y,\\overrightarrow{V}_Y)$ and $\\overrightarrow{\\mu}_{Z}(z) = \\mathcal{N}(\\overrightarrow{m}_Z,\\overrightarrow{V}_Z)$. Let´s also define the precision matrices $\\overrightarrow{W}_X \\triangleq \\overrightarrow{V}_X^{-1}$ and similarly for $Y$ and $Z$. Then applying the SP update rule leads to multiplication of two Gaussian distributions, resulting in \n", "\n", "$$\\begin{align*}\n", "\\overrightarrow{W}_Z &= \\overrightarrow{W}_X + \\overrightarrow{W}_Y \\\\ \n", "\\overrightarrow{W}_Z \\overrightarrow{m}_z &= \\overrightarrow{W}_X \\overrightarrow{m}_X + \\overrightarrow{W}_Y \\overrightarrow{m}_Y\n", "\\end{align*}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- It follows that **message passing through an equality node is similar to applying Bayes rule**, i.e., fusion of two information sources. Does this make sense?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### (OPTIONAL SLIDE) Example: SP Messages for the Addition Nodes\n", "\n", "- Next, consider an **addition node** $f_+(x,y,z) = \\delta(z-x-y)$: \n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "$$\\begin{align*}\n", "\\overrightarrow{\\mu}_{Z}(z) &= \\iint \\overrightarrow{\\mu}_{X}(x) \\overrightarrow{\\mu}_{Y}(y) \\,\\delta(z-x-y) \\,\\mathrm{d}x \\mathrm{d}y \\\\\n", " &= \\int \\overrightarrow{\\mu}_{X}(x) \\overrightarrow{\\mu}_{Y}(z-x) \\,\\mathrm{d}x \\,, \n", "\\end{align*}$$\n", "i.e., $\\overrightarrow{\\mu}_{Z}$ is the convolution of the messages $\\overrightarrow{\\mu}_{X}$ and $\\overrightarrow{\\mu}_{Y}$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "- Of course, for Gaussian messages, these update rules evaluate to\n", "\n", "$$\\begin{align*}\n", "\\overrightarrow{m}_Z = \\overrightarrow{m}_X + \\overrightarrow{m}_Y \\,,\\,\\text{and}\\,\\,\\overrightarrow{V}_z = \\overrightarrow{V}_X + \\overrightarrow{V}_Y \\,.\n", "\\end{align*}$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "-