NormalBPState#

class graph_tool.dynamics.NormalBPState(g, x=1, mu=0, theta=1, em_m=None, em_s=None, vm_m=None, vm_s=None, marginal_init=False, frozen=None, converge=True)[source]#

Bases: BPBaseState

Belief-propagation equations for the multivariate Normal distribution.

Parameters:

gGraph: Graph to be used for the dynamics.
xfloat or EdgePropertyMap (optional, default: 1.): Inverse covariance couplings. If a EdgePropertyMap is given, it needs to be of type double. If a scalar is given, this will be determine the value for every edge.
mufloat or VertexPropertyMap (optional, default: 0.): Node means. If a VertexPropertyMap is given, it needs to be of type double. If a scalar is given, this will be determine the value for every vertex.
thetafloat or iterable or VertexPropertyMap (optional, default: 1.): Diagonal of the inverse covariance matrix. If VertexPropertyMap, this needs to be of type double. If a scalar is given, this will be determine the value for every vertex.
em_mEdgePropertyMap (optional, default: None): If provided, it should be an EdgePropertyMap of type vector<double>, containing the edge messages for the means.
em_sEdgePropertyMap (optional, default: None): If provided, it should be an EdgePropertyMap of type vector<double>, containing the edge messages for the variances.
vm_mVertexPropertyMap (optional, default: None): If provided, it should be an VertexPropertyMap of type vector<double>, containing the node marginal means.
vm_sVertexPropertyMap (optional, default: None): If provided, it should be an VertexPropertyMap of type vector<double>, containing the node marginal variances.
marginal_initboolean (optional, default: False): If True, the messages will be initialized from the node marginals.
frozenVertexPropertyMap (optional, default: None): If provided, it should be an VertexPropertyMap of type bool, where a value True means that a vertex is not a variable, but a fixed field.
convergeboolean (optional, default: True): If True, the function GenPottsBPState.converge() will be called just after construction.

Notes

This implements BP equations [mezard_information_2009] for the mutivariate Normal distribution given by

\[P(\boldsymbol s | \boldsymbol A, \boldsymbol x, \boldsymbol \mu \boldsymbol\theta) = \frac{\exp\left(-\frac{1}{2}(\boldsymbol s-\boldsymbol\mu)^{\intercal} \boldsymbol X (\boldsymbol s - \boldsymbol\mu)\right)} {Z(\boldsymbol X)}\]

where \(X_{ij}=A_{ij}x_{ij}\) for \(i\neq j\), \(X_{ii}=\theta_i\), and \(Z(\boldsymbol X) = (2\pi)^{N/2}\left|\boldsymbol X\right|^{-1/2}\).

The BP equations consist in the Bethe approximation

\[\log Z(\boldsymbol X) = \log Z_i - \sum_{i<j}A_{ij}\log Z_{ij}\]

with \(Z_{ij}=Z_j/Z_{j\to i}=Z_i/Z_{i\to j}\), obtained from the message-passing equations

\[\begin{split}\begin{aligned} m_{i\to j} &= \frac{\sum_{k\in \partial i\setminus j}A_{ik}x_{ik}m_{k\to i} - \mu_i} {\theta_i - \sum_{k\in \partial i\setminus j}A_{ik}x_{ik}^2\sigma_{k\to i}^2},\\ \sigma_{i\to j}^2 &= \frac{1}{\theta_i - \sum_{k\in \partial i\setminus j}A_{ik}x_{ik}^2\sigma_{k\to i}^2}, \end{aligned}\end{split}\]

with

\[\begin{split}\begin{aligned} \log Z_{i\to j} &= \frac{\beta_{i\to j}^2}{4\alpha_{i\to j}} - \frac{1}{2}\log\alpha_{i\to j} + \frac{1}{2}\log\pi\\ \log Z_{i} &= \frac{\beta_{i}^2}{4\alpha_{i}} - \frac{1}{2}\log\alpha_{i} + \frac{1}{2}\log\pi \end{aligned}\end{split}\]

where

\[\begin{split}\begin{aligned} \alpha_{i\to j} &= \frac{\theta_i - \sum_{k\in \partial i\setminus j}A_{ik}x_{ik}^2\sigma_{k\to i}^2}{2}\\ \beta_{i\to j} &= \sum_{k\in \partial i\setminus j}A_{ik}x_{ik}m_{k\to i} - \mu_i\\ \alpha_{i} &= \frac{\theta_i - \sum_{j\in \partial i}A_{ij}x_{ij}^2\sigma_{j\to i}^2}{2}\\ \beta_{i} &= \sum_{j\in \partial i}A_{ij}x_{ij}m_{j\to i} - \mu_i. \end{aligned}\end{split}\]

From these equations, the marginal node probability densities are normal distributions with mean and variance given by

\[\begin{split}\begin{aligned} m_i &= \frac{\sum_{j}A_{ij}x_{ij}m_{j\to i} - \mu_i} {\theta_i - \sum_{j}A_{ij}x_{ij}^2\sigma_{j\to i}^2},\\ \sigma_i^2 &= \frac{1}{\theta_i - \sum_{j}A_{ij}x_{ij}^2\sigma_{j\to i}^2}. \end{aligned}\end{split}\]

References

[mezard_information_2009]

Marc Mézard, and Andrea Montanari, “Information, physics, and computation”, Oxford University Press, 2009. https://web.stanford.edu/~montanar/RESEARCH/book.html

Examples

>>> g = gt.GraphView(gt.collection.data["polblogs"].copy(), directed=False)
>>> gt.remove_parallel_edges(g)
>>> g = gt.extract_largest_component(g, prune=True)
>>> state = gt.NormalBPState(g, x=1/200, mu=g.vp.value.t(lambda x: arctanh((2*x-1)*.9)))
>>> s = state.sample()
>>> gt.graph_draw(g, g.vp.pos, vertex_fill_color=s,
...               output="bp-normal.svg")
<...>

../_images/bp-normal.svg — Marginal sample of a multivariate normal distribution.#

Methods

`converge`([epsilon, max_niter, update_marginals])	Calls `iterate()` until delta falls below `epsilon` or the number of iterations exceeds `max_niter`.
`copy`()	Return a copy of the state.
`energy`(s)	Obtains the energy (Hamiltonean) of state `s` (a `VertexPropertyMap`).
`iterate`([niter, parallel, update_marginals])	Updates meassages synchronously (or asyncrhonously if `parallel=False`), niter number of times.
`log_Z`()	Obtains the log-partition function from the current messages.
`log_prob`(s)	Obtains the log-probability of state `s` (a `VertexPropertyMap`).
`marginal_log_prob`(s)	Obtains the marginal log-probability of state `s` (a `VertexPropertyMap`).
`sample`([update_marginals])	Samples a state from the marignal distribution.
`update_marginals`()	Update the node marginals from the current messages.

converge(epsilon=1e-08, max_niter=1000, update_marginals=True, **kwargs)#

Calls iterate() until delta falls below epsilon or the number of iterations exceeds max_niter.

If update_marignals=True, this function calls update_marginals() at the end.

The remaining keyword arguments are passed to iterate().

copy()#: Return a copy of the state.

energy(s)#

Obtains the energy (Hamiltonean) of state s (a VertexPropertyMap).

If s is vector valued, it’s assumed to correspond to multiple states, and the total energy sum is returned.

iterate(niter=1, parallel=True, update_marginals=True)#

Updates meassages synchronously (or asyncrhonously if parallel=False), niter number of times. This function returns the interation delta of the last iteration.

If update_marignals=True, this function calls update_marginals() at the end.

Parallel implementation.

If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.

log_Z()#: Obtains the log-partition function from the current messages.

log_prob(s)#

Obtains the log-probability of state s (a VertexPropertyMap).

If s is vector valued, it’s assumed to correspond to multiple states, and the total log-probability sum is returned.

marginal_log_prob(s)#

Obtains the marginal log-probability of state s (a VertexPropertyMap).

If s is vector valued, it’s assumed to correspond to multiple states, and the total marginal log-probability sum is returned.

sample(update_marginals=True)[source]#

Samples a state from the marignal distribution. This functio returns a VertexPropertyMap of type given by val_type.

If update_marignals=True, this function calls update_marginals() before sampling.

update_marginals()#: Update the node marginals from the current messages.

NormalBPState

Contents

NormalBPState#