libDAI
|
Approximate inference algorithm by Montanari and Rizzo [MoR05]. More...
#include <dai/mr.h>
Classes | |
struct | Properties |
Parameters for MR. More... | |
Public Member Functions | |
MR () | |
Default constructor. More... | |
MR (const FactorGraph &fg, const PropertySet &opts) | |
Construct from FactorGraph fg and PropertySet opts. More... | |
General InfAlg interface | |
virtual MR * | clone () const |
Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor) More... | |
virtual MR * | construct (const FactorGraph &fg, const PropertySet &opts) const |
Returns a pointer to a newly constructed inference algorithm. More... | |
virtual std::string | name () const |
Returns the name of the algorithm. More... | |
virtual Factor | belief (const Var &v) const |
Returns the (approximate) marginal probability distribution of a variable. More... | |
virtual Factor | belief (const VarSet &) const |
Returns the (approximate) marginal probability distribution of a set of variables. More... | |
virtual Factor | beliefV (size_t i) const |
Returns the (approximate) marginal probability distribution of the variable with index i. More... | |
virtual std::vector< Factor > | beliefs () const |
Returns all beliefs (approximate marginal probability distributions) calculated by the algorithm. More... | |
virtual Real | logZ () const |
Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph). More... | |
virtual void | init () |
Initializes all data structures of the approximate inference algorithm. More... | |
virtual void | init (const VarSet &) |
Initializes all data structures corresponding to some set of variables. More... | |
virtual Real | run () |
Runs the approximate inference algorithm. More... | |
virtual Real | maxDiff () const |
Returns maximum difference between single variable beliefs in the last iteration. More... | |
virtual size_t | Iterations () const |
Returns number of iterations done (one iteration passes over the complete factorgraph). More... | |
virtual void | setProperties (const PropertySet &opts) |
Set parameters of this inference algorithm. More... | |
virtual PropertySet | getProperties () const |
Returns parameters of this inference algorithm converted into a PropertySet. More... | |
virtual std::string | printProperties () const |
Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]". More... | |
Public Member Functions inherited from dai::DAIAlg< GRM > | |
DAIAlg () | |
Default constructor. More... | |
DAIAlg (const GRM &grm) | |
Construct from GRM. More... | |
FactorGraph & | fg () |
Returns reference to underlying FactorGraph. More... | |
const FactorGraph & | fg () const |
Returns constant reference to underlying FactorGraph. More... | |
void | clamp (size_t i, size_t x, bool backup=false) |
Clamp variable with index i to value x (i.e. multiply with a Kronecker delta ) More... | |
void | makeCavity (size_t i, bool backup=false) |
Sets all factors interacting with variable with index i to one. More... | |
void | makeRegionCavity (std::vector< size_t > facInds, bool backup) |
Sets all factors indicated by facInds to one. More... | |
void | backupFactor (size_t I) |
Make a backup copy of factor I. More... | |
void | backupFactors (const VarSet &vs) |
Make backup copies of all factors involving the variables in vs. More... | |
void | restoreFactor (size_t I) |
Restore factor I from its backup copy. More... | |
void | restoreFactors (const VarSet &vs) |
Restore the factors involving the variables in vs from their backup copies. More... | |
void | restoreFactors () |
Restore all factors from their backup copies. More... | |
Public Member Functions inherited from dai::InfAlg | |
virtual | ~InfAlg () |
Virtual destructor (needed because this class contains virtual functions) More... | |
virtual std::string | identify () const |
Identifies itself for logging purposes. More... | |
virtual Factor | beliefF (size_t I) const |
Returns the (approximate) marginal probability distribution of the variables on which factor I depends. More... | |
virtual std::vector< size_t > | findMaximum () const |
Calculates the joint state of all variables that has maximum probability. More... | |
virtual void | setMaxIter (size_t) |
Sets maximum number of iterations (one iteration passes over the complete factorgraph). More... | |
Public Attributes | |
struct dai::MR::Properties | props |
Private Types | |
typedef boost::dynamic_bitset | sub_nb |
Type used for managing a subset of neighbors. More... | |
Private Member Functions | |
Real | calcCavityCorrelations () |
Initialize cors. More... | |
void | propagateCavityFields () |
Iterate update equations for cavity fields. More... | |
void | calcMagnetizations () |
Calculate magnetizations. More... | |
Real | _tJ (size_t i, sub_nb A) |
Calculate the product of all tJ[i][_j] for _j in A. More... | |
Real | Omega (size_t i, size_t _j, size_t _l) |
Calculate as defined in [MoR05] eqn. (2.15) More... | |
Real | T (size_t i, sub_nb A) |
Calculate as defined in [MoR05] eqn. (2.17) with . More... | |
Real | T (size_t i, size_t _j) |
Calculates where j is the _j 'th neighbor of i. More... | |
Real | Gamma (size_t i, size_t _j, size_t _l1, size_t _l2) |
Calculates as defined in [MoR05] eqn. (2.16) More... | |
Real | Gamma (size_t i, size_t _l1, size_t _l2) |
Calculates as defined in [MoK07] on page 1141. More... | |
Real | appM (size_t i, sub_nb A) |
Approximates moments of variables in A. More... | |
void | sum_subs (size_t j, sub_nb A, Real *sum_even, Real *sum_odd) |
Calculate sum over all even/odd subsets B of A of _tJ(j,B) appM(j,B) More... | |
Private Attributes | |
bool | supported |
Is the underlying factor graph supported? More... | |
GraphAL | G |
The interaction graph (Markov graph) More... | |
std::vector< std::vector< Real > > | tJ |
tJ[i][_j] is the hyperbolic tangent of the interaction between spin i and its neighbour G.nb(i,_j) More... | |
std::vector< Real > | theta |
theta[i] is the local field on spin i More... | |
std::vector< std::vector< Real > > | M |
M[i][_j] is . More... | |
std::vector< std::vector< std::vector< Real > > > | cors |
Cavity correlations. More... | |
std::vector< Real > | Mag |
Magnetizations. More... | |
Real | _maxdiff |
Maximum difference encountered so far. More... | |
size_t | _iters |
Number of iterations needed. More... | |
Approximate inference algorithm by Montanari and Rizzo [MoR05].
|
private |
Type used for managing a subset of neighbors.
|
inline |
Default constructor.
dai::MR::MR | ( | const FactorGraph & | fg, |
const PropertySet & | opts | ||
) |
Construct from FactorGraph fg and PropertySet opts.
fg | Factor graph. |
opts | Parameters |
NOT_IMPLEMENTED | if fg has factors depending on three or more variables or has variables with more than two possible states. |
|
inlinevirtual |
Returns a pointer to a new, cloned copy of *this
(i.e., virtual copy constructor)
Implements dai::InfAlg.
|
inlinevirtual |
Returns a pointer to a newly constructed inference algorithm.
fg | Factor graph on which to perform the inference algorithm; |
opts | Parameters passed to constructor of inference algorithm; |
Implements dai::InfAlg.
|
inlinevirtual |
Returns the name of the algorithm.
Implements dai::InfAlg.
Returns the (approximate) marginal probability distribution of a variable.
Reimplemented from dai::InfAlg.
Returns the (approximate) marginal probability distribution of a set of variables.
NOT_IMPLEMENTED | if not implemented/supported. |
BELIEF_NOT_AVAILABLE | if the requested belief cannot be calculated with this algorithm. |
Implements dai::InfAlg.
|
virtual |
Returns the (approximate) marginal probability distribution of the variable with index i.
For some approximate inference algorithms, using beliefV() is preferred to belief() for performance reasons.
Reimplemented from dai::InfAlg.
|
virtual |
Returns all beliefs (approximate marginal probability distributions) calculated by the algorithm.
Implements dai::InfAlg.
|
inlinevirtual |
Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph).
NOT_IMPLEMENTED | if not implemented/supported |
Implements dai::InfAlg.
|
inlinevirtual |
Initializes all data structures of the approximate inference algorithm.
Implements dai::InfAlg.
|
inlinevirtual |
Initializes all data structures corresponding to some set of variables.
This method can be used to do a partial initialization after a part of the factor graph has changed. Instead of initializing all data structures, it only initializes those involving the variables in vs.
NOT_IMPLEMENTED | if not implemented/supported |
Implements dai::InfAlg.
|
virtual |
Runs the approximate inference algorithm.
Implements dai::InfAlg.
|
inlinevirtual |
Returns maximum difference between single variable beliefs in the last iteration.
NOT_IMPLEMENTED | if not implemented/supported |
Reimplemented from dai::InfAlg.
|
inlinevirtual |
Returns number of iterations done (one iteration passes over the complete factorgraph).
NOT_IMPLEMENTED | if not implemented/supported |
Reimplemented from dai::InfAlg.
|
virtual |
Set parameters of this inference algorithm.
The parameters are set according to the PropertySet opts. The values can be stored either as std::string or as the type of the corresponding MF::props member.
Implements dai::InfAlg.
|
virtual |
Returns parameters of this inference algorithm converted into a PropertySet.
Implements dai::InfAlg.
|
virtual |
Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]".
Implements dai::InfAlg.
|
private |
Initialize cors.
|
private |
Iterate update equations for cavity fields.
|
private |
Calculate magnetizations.
Calculate the product of all tJ[i][_j] for _j in A.
i | variable index |
A | subset of neighbors of variable i |
|
private |
Calculate as defined in [MoR05] eqn. (2.15)
Calculate as defined in [MoR05] eqn. (2.17) with .
i | variable index |
A | subset of neighbors of variable i |
|
private |
Calculates where j is the _j 'th neighbor of i.
|
private |
Calculates as defined in [MoR05] eqn. (2.16)
|
private |
Calculates as defined in [MoK07] on page 1141.
Approximates moments of variables in A.
Calculate the moment of variables in A from M and cors, neglecting higher order cumulants, defined as the sum over all partitions of A into subsets of cardinality two at most of the product of the cumulants (either first order, i.e. M, or second order, i.e. cors) of the entries of the partitions.
i | variable index |
A | subset of neighbors of variable i |
Calculate sum over all even/odd subsets B of A of _tJ(j,B) appM(j,B)
j | variable index |
A | subset of neighbors of variable j |
sum_even | on return, will contain the sum over all even subsets |
sum_odd | on return, will contain the sum over all odd subsets |
|
private |
Is the underlying factor graph supported?
|
private |
The interaction graph (Markov graph)
|
private |
tJ[i][_j] is the hyperbolic tangent of the interaction between spin i and its neighbour G.nb(i,_j)
|
private |
theta[i] is the local field on spin i
|
private |
M[i][_j] is .
|
private |
Cavity correlations.
|
private |
Magnetizations.
|
private |
Maximum difference encountered so far.
|
private |
Number of iterations needed.