Gaussian belief propagation

1 Parameterization

Gaussian BP is often conducted using the canonical parameterization, in which a particular node prior $m$ may be written as: $$p_m\left({\mathbf{x}}_m\right)\propto e^{-\frac{1}{2}\left[{({\mathbf{x}}_m-{\mathit{\mu }}_m)}^{\mathrm{\top }}{\mathbf{\Lambda }}_m({\mathbf{x}}_m-{\mathit{\mu }}_m)\right]}$$ where ${\mathit{\mu }}_m$ is the mean of the distribution and ${\mathrm{\Lambda }}_m$ is its precision (i.e. inverse covariance.)

Davison and Ortiz (2019) recommend the “information parameterization” of Eustice, Singh, and Leonard (2006): $$p_m\left({\mathbf{x}}_m\right)\propto e^{[-\frac{1}{2}{\mathbf{x}}_m^{\mathrm{\top }}{\mathrm{\Lambda }}_m{\mathbf{x}}_m+{\mathit{\eta }}_m^{\mathrm{\top }}{\mathbf{x}}_m]}$$ the value of either. The information vector ${\mathit{\eta }}_m$ relates to the mean vector as $${\mathit{\eta }}_m={\mathrm{\Lambda }}_m{\mathit{\mu }}_m.$$ The information form is convenient as multiplication of distributions (when we update) is handled simply by adding the information vectors and precision matrices.

Let us recap that in Gaussian tricks.

2 Linearization

See GP noise transforms for a typical way to do it. In the information parameterization the rules look different. Suppose the expected value of the measurement is given by non-linear map $h,$ in the sense that we observe Gaussian noise centred on $h({\mathbf{x}}_s)$. We define the associated Gaussian factor as follows: $$f_s\left({\mathbf{x}}_s\right)\propto e^{-\frac{1}{2}\left[{({\mathbf{z}}_s-{\mathbf{h}}_s\left({\mathbf{x}}_s\right))}^{\mathrm{\top }}{\mathrm{\Lambda }}_s({\mathbf{z}}_s-{\mathbf{h}}_s\left({\mathbf{x}}_s\right))\right]}$$ We apply the first-order Taylor series expansion of non-linear measurement function ${\mathbf{h}}_s$ to find its approximate value for state values ${\mathbf{x}}_s$ close to ${\mathbf{x}}_0$ : $${\mathbf{h}}_s\left({\mathbf{x}}_s\right)\approx {\mathbf{h}}_s\left({\mathbf{x}}_0\right)+{\mathrm{J}}_s({\mathbf{x}}_s-{\mathbf{x}}_0).$$ Here ${\mathrm{J}}_s$ is the Jacobian ${\frac{\partial {\mathbf{h}}_s}{\partial {\mathbf{x}}_s}|}_{{\mathbf{x}}_s={\mathbf{x}}_0}.$ With a bit of rearranging quadratic forms, we can massage ${\mathbf{h}}_s\left({\mathbf{x}}_s\right)$ around state variables ${\mathbf{x}}_0$, turning it into a Gaussian factor expressed in terms of ${\mathbf{x}}_s$. We use the linear factor represented in information form by information vector ${\mathit{\eta }}_s$ and precision matrix ${\mathrm{\Lambda }}_s^{\prime }$ calculated as follows: $$\begin{array}{rl}{\mathit{\eta }}_s& ={\mathrm{J}}_s^{\mathrm{\top }}{\mathrm{\Lambda }}_s[{\mathrm{J}}_s{\mathbf{x}}_0+{\mathbf{z}}_s-{\mathbf{h}}_s\left({\mathbf{x}}_0\right)]\\ {\mathrm{\Lambda }}_s^{\prime }& ={\mathrm{J}}_s^{\mathrm{\top }}{\mathrm{\Lambda }}_s{\mathrm{J}}_s.\end{array}$$

3 Variational inference

Intuition building. Noting that the distance between two Gaussians in KL is given by $$\mathrm{KL}(\mathcal{N}({\mu }_1,{\mathrm{\Sigma }}_1)\parallel \mathcal{N}({\mu }_2,{\mathrm{\Sigma }}_2))=\frac{1}{2}(\mathrm{tr}\left({\mathrm{\Sigma }}_2^{-1}{\mathrm{\Sigma }}_1\right)+({\mu }_2-{\mu }_1{)}^{\mathsf{T}}{\mathrm{\Sigma }}_2^{-1}({\mu }_2-{\mu }_1)-k+\ln \left(\frac{det{\mathrm{\Sigma }}_2}{det{\mathrm{\Sigma }}_1}\right))$$ We can think about belief propagation in terms of KL-similar updates.

Suppose I have a Gaussian RV with some prior distribution $\mathsf{x}\sim \mathcal{N}({\mathit{m}}_{\mathsf{x}},{\mathrm{\Sigma }}_{\mathsf{x}})$ and I observe some datum $\mathsf{y}\sim f(\mathsf{x}+ϵ)$ where $ϵ\sim \mathcal{N}(0,{\mathrm{\Sigma }}_{\mathsf{y}})$. Define $\hat{\mathsf{x}}:=\mathsf{x}\mid \mathsf{y}.$ Assert that we can approximate $\mathsf{x}\sim \mathcal{N}({\mathit{m}}_{\hat{\mathsf{x}}},{\mathrm{\Sigma }}_{\hat{\mathsf{x}}})$. What is the best approximation to the posterior distribution of $\mathsf{x}$ given the observation? I.e. how do we choose ${\mathit{m}}_{\hat{\mathsf{x}}},{\mathrm{\Sigma }}_{\hat{\mathsf{x}}}$? One way is to choose them to minimise a KL divergence, $$\begin{array}{rl}{\mathit{m}}_{\hat{\mathsf{x}}},{\mathrm{\Sigma }}_{\hat{\mathsf{x}}}& ={\arg \min }_{\mathit{m},\mathrm{\Sigma }}\mathrm{KL}(\mathcal{N}(\mathit{m},\mathrm{\Sigma })\parallel \mathsf{x}\mid \mathsf{y})\\ & ={\arg \min }_{\mathit{m},\mathrm{\Sigma }}\mathrm{KL}(\mathcal{N}(\mathit{m},\mathrm{\Sigma })\parallel \mathcal{N}({\mathit{m}}_{\mathsf{x}},{\mathrm{\Sigma }}_{\mathsf{x}}).\end{array}$$ We still need to choose a way of estimating this posterior which could exploit stochastic gradient estimation or a GP noise transforms. TBC.

4 Parallelisation

El-Kurdi’s thesis (Y. M. El-Kurdi 2014) exploits some assortment of tricks to attain high-speed convergence in pde-type models.

5 Robust

There are generalised belief propagations based on elliptical laws (Agarwal et al. 2013; Davison and Ortiz 2019), making this into a kind of elliptical belief propagation. It is usually referred to as a robust factor or as dynamic covariance scaling. Usually this is done with robust losses; I’m not sure why other elliptical distributions are unpopular.

6 Use in PDEs

Finite Element Models can be expressed as locally-linear constraints and thus expressed using GBP (Y. El-Kurdi et al. 2016; Y. M. El-Kurdi 2014; Y. El-Kurdi et al. 2015).

7 Tools

8 References