API reference

Docstrings

Belief Propagation

BeliefPropagation.BP — Type
BP{F<:BPFactor, FV<:BPFactor, M, MB, G<:FactorGraph}

A type representing the state of the Belief Propagation algorithm.

Fields

  • g: a FactorGraph(see IndexedFactorGraphs.jl)
  • ψ: a vector of BPFactor representing the factors {ψₐ(xₐ)}ₐ
  • ϕ: a vector of BPFactor representing the single-variable factors {ϕᵢ(xᵢ)}ᵢ
  • u: messages from factor to variable
  • h: messages from variable to factor
  • b: beliefs
source
BeliefPropagation.BP — Method
BP(g::FactorGraph, ψ::AbstractVector{<:BPFactor}, states; ϕ)

Constructor for the BP type.

Arguments

  • g: a FactorGraph
  • ψ: a vector of BPFactor representing the factors {ψₐ(xₐ)}ₐ
  • states: an iterable of integers of length equal to the number of variable nodes specifyig the number of values each variable can take
  • ϕ: (optional) a vector of BPFactor representing the single-variable factors {ϕᵢ(xᵢ)}ᵢ
source
BeliefPropagation.BeliefConvergence — Type
BeliefConvergence

Called after an iteration in a callback, it computes the maximum absolute change in beliefs with (::BeliefConvergence)(::BP, errv, errf, errb, it)

source
BeliefPropagation.Decimation — Type
Decimation(n, maxiter, tol)

Return an instance of the Decimation callback.

Arguments

  • n: total number of variables
  • maxiter: maximum number of iterations
  • tol: tolerance for convergence check

Optional arguments

source
BeliefPropagation.Decimation — Type
Decimation <: Callback

A callback that implements the decimation procedure: whenever the desired convergence tolerance has been reached, the variable with the most biased belief is fixed to that value by modifying the corresponding ϕ factor. The procedure is repeated until all variables are fixed. The recommended constructor is Decimation(n::Integer, tol::Real).

source
BeliefPropagation.MessageConvergence — Type
MessageConvergence

Called after an iteration in a callback, it computes the maximum absolute change in messages with (::MessageConvergence)(::BP, errv, errf, errb, it)

source
BeliefPropagation.ProgressAndConvergence — Type
ProgressAndConvergence <: Callback

A basic callback that prints a progress bar and checks convergence.ù The recommended constructor is ProgressAndConvergence(maxiter::Integer, tol::Real).

Fields

  • prog: a Progress from ProgressMeter.jl
  • tol: the tolerance below which BP is considered at a fixed point
  • conv_checker: a ConvergenceChecker
source
BeliefPropagation.UniformFactor — Type
UniformFactor

A type of BPFactor which returns the same value for any input: it behaves as if it wasn't even there. It is used as the default for single-variable factors

source
BeliefPropagation.avg_energy — Method
avg_energy([f], bp::BP)

Return the average energy

\[\langle E \rangle =\sum_a\sum_{\underline{x}_a}b_a(\underline{x}_a) \left[-\log\psi_a(\underline{x}_a)\right] + \sum_i\sum_{x_i}b_i(x_i) \left[-\log\phi_i(x_i)\right]\]

source
BeliefPropagation.bethe_free_energy — Method
bethe_free_energy([f], bp::BP)

Return the bethe free energy

\[F=\sum_a\sum_{\underline{x}_a}b_a(\underline{x}_a) \left[-\log\frac{b_a(\underline{x}_a)}{\psi_a(\underline{x}_a)}\right] + \sum_i\sum_{x_i}b_i(x_i) \left[-\log\frac{b_i(x_i)^{1-\lvert\partial i\rvert}}{\phi_i(x_i)}\right]\]

source
BeliefPropagation.energy — Method
energy(bp::BP, x)

Return the energy

\[E(\underline{x})=\sum_a \left[-\log\psi_a(\underline{x}_a)\right] + \sum_i \left[-\log\phi_i(x_i)\right]\]

of configuration x.

source
BeliefPropagation.evaluate — Method
evaluate(bp::BP, x)

Return the unnormalized probability $\prod_a\psi_a(\underline{x}_a)\prod_i\phi_i(x_i)$ of configuration x.

source
BeliefPropagation.iterate! — Method
iterate!(bp::BP; kwargs...)

Run BP.

Optional arguments

  • update_variable!: the function that computes and updates variable-to-factor messages
  • update_factor!: the function that computes and updates factor-to-variable messages
  • maxiter: maximum number of iterations
  • tol: convergence check parameter
  • damp: damping parameter
  • rein: reinforcement parameter
  • callbacks: a vector of callbacks. By default a ProgressAndConvergence
  • extra arguments to be passed to custom update_variable! and update_factor!
source

Models

BeliefPropagation.Models.IsingCoupling — Type
IsingCoupling

A type of BPFactor representing a factor in an Ising distribution. It involves $\pm 1$ variables $\boldsymbol{\sigma}_a=\{\sigma_1, \sigma_2, \ldots\}$. The factor evaluates to $\psi(\boldsymbol{\sigma}_a)=e^{\beta J \prod_{i\in a}\sigma_i}$. A particular case is the pairwise interaction where $a=\{i,j\}$ is a pair of vertices involved in an edge $(ij)$.

Fields

  • βJ: coupling strength.
source
BeliefPropagation.Models.KSATClause — Type
KSATClause

A type of BPFactor representing a clause in a k-SAT formula. It involves $\{0,1\}$ variables $\boldsymbol{x}_a=\{x_1, x_2, \ldots, x_k\}$. The factor evaluates to $\psi_a(\boldsymbol{x}_a)=1 - \prod_{i\in a}\delta(x_i, J^a_{i})$.

Fields

  • J: a vector of booleans.
source
BeliefPropagation.Models.fast_ising_bp — Function
fast_ising_bp(g::AbstractFactorGraph, ψ::Vector{<:IsingCoupling}, [ϕ])

Return a BP instance with Ising factors and messages and beliefs in log-ratio format:

\[\begin{align*} &m_{a\to i}(\sigma_i) \propto e^{u_{a\to i}\sigma_i}\\ &u_{a\to i} = \frac12\log\frac{m_{a\to i}(+1)}{m_{a\to i}(+1)} \end{align*}\]

source
BeliefPropagation.Models.fast_ksat_bp — Function
fast_ksat_bp(g::AbstractFactorGraph, ψ::Vector{<:KSATClause}, [ϕ])

Return a specialized BP instance with KSATClause and messages encoded as reals instead of vectors: only the probability of x=1 is stored. ```

source

Test utilities

BeliefPropagation.Test.rand_bp — Method
rand_bp([rng], g::FactorGraph, states)

Return a BP with random factors.

states is an iterable containing the number of values that can be taken by each variable.

source

Index