56d04bcd475c5436aae31a1175264bbe099c0b24
1 /* This file is part of libDAI - http://www.libdai.org/
3 * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
5 * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
10 /// \brief Defines class LC, which implements loop corrections for approximate inference
13 #ifndef __defined_libdai_lc_h
14 #define __defined_libdai_lc_h
18 #include <dai/daialg.h>
20 #include <dai/factorgraph.h>
21 #include <dai/properties.h>
22 #include <dai/exceptions.h>
28 /// Approximate inference algorithm "Loop Corrected Belief Propagation" [\ref MoK07]
29 class LC
: public DAIAlgFG
{
31 /// Stores for each variable the approximate cavity distribution multiplied with the omitted factors
32 std::vector
<Factor
> _pancakes
;
33 /// Stores for each variable the approximate cavity distribution
34 std::vector
<Factor
> _cavitydists
;
35 /// _phis[i][_I] corresponds to \f$ \phi^{\setminus i}_I(x_{I \setminus i}) \f$ in the paper
36 std::vector
<std::vector
<Factor
> > _phis
;
37 /// Single variable beliefs
38 std::vector
<Factor
> _beliefs
;
39 /// Maximum difference encountered so far
41 /// Number of iterations needed
47 /// Enumeration of possible ways to initialize the cavities
48 /** The following initialization methods are defined:
49 * - FULL calculates the marginal using calcMarginal()
50 * - PAIR calculates only second order interactions using calcPairBeliefs() with \a accurate == \c false
51 * - PAIR2 calculates only second order interactions using calcPairBeliefs() with \a accurate == \c true
52 * - UNIFORM uses a uniform distribution
54 DAI_ENUM(CavityType
,FULL
,PAIR
,PAIR2
,UNIFORM
);
56 /// Enumeration of different update schedules
57 /** The following update schedules are defined:
58 * - SEQFIX sequential fixed schedule
59 * - SEQRND sequential random schedule
61 DAI_ENUM(UpdateType
,SEQFIX
,SEQRND
);
63 /// Verbosity (amount of output sent to stderr)
66 /// Maximum number of iterations
69 /// Tolerance for convergence test
72 /// Complete or partial reinitialization of cavity graphs?
75 /// Damping constant (0.0 means no damping, 1.0 is maximum damping)
78 /// How to initialize the cavities
81 /// What update schedule to use
84 /// Name of the algorithm used to initialize the cavity distributions
85 std::string cavainame
;
87 /// Parameters for the algorithm used to initialize the cavity distributions
88 PropertySet cavaiopts
;
92 /// Default constructor
93 LC() : DAIAlgFG(), _pancakes(), _cavitydists(), _phis(), _beliefs(), _maxdiff(), _iters(), props() {}
95 /// Construct from FactorGraph \a fg and PropertySet \a opts
96 /** \param fg Factor graph.
97 * \param opts Parameters @see Properties
99 LC( const FactorGraph
&fg
, const PropertySet
&opts
);
102 /// \name General InfAlg interface
104 virtual LC
* clone() const { return new LC(*this); }
105 virtual LC
* construct( const FactorGraph
&fg
, const PropertySet
&opts
) const { return new LC( fg
, opts
); }
106 virtual std::string
name() const { return "LC"; }
107 virtual Factor
belief( const Var
&v
) const { return beliefV( findVar( v
) ); }
108 virtual Factor
belief( const VarSet
&/*vs*/ ) const;
109 virtual Factor
beliefV( size_t i
) const { return _beliefs
[i
]; }
110 virtual std::vector
<Factor
> beliefs() const { return _beliefs
; }
111 virtual Real
logZ() const { DAI_THROW(NOT_IMPLEMENTED
); return 0.0; }
113 virtual void init( const VarSet
&/*ns*/ ) { init(); }
115 virtual Real
maxDiff() const { return _maxdiff
; }
116 virtual size_t Iterations() const { return _iters
; }
117 virtual void setMaxIter( size_t maxiter
) { props
.maxiter
= maxiter
; }
118 virtual void setProperties( const PropertySet
&opts
);
119 virtual PropertySet
getProperties() const;
120 virtual std::string
printProperties() const;
123 /// \name Additional interface specific for LC
125 /// Approximates the cavity distribution of variable \a i, using the inference algorithm \a name with parameters \a opts
126 Real
CalcCavityDist( size_t i
, const std::string
&name
, const PropertySet
&opts
);
127 /// Approximates all cavity distributions using inference algorithm \a name with parameters \a opts
128 Real
InitCavityDists( const std::string
&name
, const PropertySet
&opts
);
129 /// Sets approximate cavity distributions to \a Q
130 long SetCavityDists( std::vector
<Factor
> &Q
);
131 /// Updates the belief of the Markov blanket of variable \a i based upon the information from its \a _I 'th neighboring factor
132 Factor
NewPancake (size_t i
, size_t _I
, bool & hasNaNs
);
133 /// Calculates the belief of variable \a i
134 void CalcBelief (size_t i
);
135 /// Returns the belief of the Markov blanket of variable \a i (including the variable itself)
136 const Factor
&pancake (size_t i
) const { return _pancakes
[i
]; };
137 /// Returns the approximate cavity distribution for variable \a i
138 const Factor
&cavitydist (size_t i
) const { return _cavitydists
[i
]; };
143 } // end of namespace dai