|
libDAI
|
Implements BBP (Back-Belief-Propagation) [EaG09]. More...
#include <dai/bbp.h>
Classes | |
| struct | Properties |
| Parameters for BBP. More... | |
Public Member Functions | |
Constructors/destructors | |
| BBP (const InfAlg *ia, const PropertySet &opts) | |
| Construct BBP object from a InfAlg ia and a PropertySet opts. | |
Initialization | |
| void | init (const std::vector< Prob > &adj_b_V, const std::vector< Prob > &adj_b_F, const std::vector< Prob > &adj_psi_V, const std::vector< Prob > &adj_psi_F) |
| Initializes from given belief adjoints adj_b_V, adj_b_F and initial factor adjoints adj_psi_V, adj_psi_F. | |
| void | init (const std::vector< Prob > &adj_b_V, const std::vector< Prob > &adj_b_F) |
| Initializes from given belief adjoints adj_b_V and adj_b_F (setting initial factor adjoints to zero) | |
| void | init_V (const std::vector< Prob > &adj_b_V) |
| Initializes variable belief adjoints adj_b_V (and sets factor belief adjoints and initial factor adjoints to zero) | |
| void | init_F (const std::vector< Prob > &adj_b_F) |
| Initializes factor belief adjoints adj_b_F (and sets variable belief adjoints and initial factor adjoints to zero) | |
| void | initCostFnAdj (const BBPCostFunction &cfn, const std::vector< size_t > *stateP) |
| Initializes with adjoints calculated from cost function cfn, and state stateP. | |
BBP Algorithm | |
| void | run () |
| Perform iterative updates until change is less than given tolerance. | |
Query results | |
| Prob & | adj_psi_V (size_t i) |
| Returns reference to variable factor adjoint. | |
| const Prob & | adj_psi_V (size_t i) const |
| Returns constant reference to variable factor adjoint. | |
| Prob & | adj_psi_F (size_t I) |
| Returns reference to factor adjoint. | |
| const Prob & | adj_psi_F (size_t I) const |
| Returns constant reference to factor adjoint. | |
| Prob & | adj_b_V (size_t i) |
| Returns reference to variable belief adjoint. | |
| const Prob & | adj_b_V (size_t i) const |
| Returns constant reference to variable belief adjoint. | |
| Prob & | adj_b_F (size_t I) |
| Returns reference to factor belief adjoint. | |
| const Prob & | adj_b_F (size_t I) const |
| Returns constant reference to factor belief adjoint. | |
| size_t | Iterations () |
| Return number of iterations done so far. | |
Public Attributes | |
| struct dai::BBP::Properties | props |
Private Member Functions | |
| Prob | unnormAdjoint (const Prob &w, Real Z_w, const Prob &adj_w) |
| Computes the adjoint of the unnormed probability vector from the normalizer and the adjoint of the normalized probability vector. | |
| Real | getUnMsgMag () |
| Calculates averaged L1 norm of unnormalized message adjoints. | |
| void | getMsgMags (Real &s, Real &new_s) |
| Calculates averaged L1 norms of current and new normalized message adjoints. | |
| void | getArgmaxMsgM (size_t &i, size_t &_I, Real &mag) |
| Returns indices and magnitude of the largest normalized factor->variable message adjoint. | |
| Real | getMaxMsgM () |
| Returns magnitude of the largest (in L1-norm) normalized factor->variable message adjoint. | |
| Real | getTotalMsgM () |
| Calculates sum of L1 norms of all normalized factor->variable message adjoints. | |
| Real | getTotalNewMsgM () |
| Calculates sum of L1 norms of all updated normalized factor->variable message adjoints. | |
| Real | getTotalMsgN () |
| Calculates sum of L1 norms of all normalized variable->factor message adjoints. | |
| std::vector< Prob > | getZeroAdjF (const FactorGraph &fg) |
| Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the factors in the factor graph fg. | |
| std::vector< Prob > | getZeroAdjV (const FactorGraph &fg) |
| Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the variables in the factor graph fg. | |
Initialization helper functions | |
| void | RegenerateT () |
| Calculate T values; see eqn. (41) in [EaG09]. | |
| void | RegenerateU () |
| Calculate U values; see eqn. (42) in [EaG09]. | |
| void | RegenerateS () |
| Calculate S values; see eqn. (43) in [EaG09]. | |
| void | RegenerateR () |
| Calculate R values; see eqn. (44) in [EaG09]. | |
| void | RegenerateInputs () |
| Calculate _adj_b_V_unnorm and _adj_b_F_unnorm from _adj_b_V and _adj_b_F. | |
| void | RegeneratePsiAdjoints () |
| Initialise members for factor adjoints. | |
| void | RegenerateParMessageAdjoints () |
| Initialise members for message adjoints for parallel algorithm. | |
| void | RegenerateSeqMessageAdjoints () |
| Initialise members for message adjoints for sequential algorithm. | |
| void | Regenerate () |
| Called by init, recalculates intermediate values. | |
Accessors/mutators | |
| Prob & | T (size_t i, size_t _I) |
| Returns reference to T value; see eqn. (41) in [EaG09]. | |
| const Prob & | T (size_t i, size_t _I) const |
| Returns constant reference to T value; see eqn. (41) in [EaG09]. | |
| Prob & | U (size_t I, size_t _i) |
| Returns reference to U value; see eqn. (42) in [EaG09]. | |
| const Prob & | U (size_t I, size_t _i) const |
| Returns constant reference to U value; see eqn. (42) in [EaG09]. | |
| Prob & | S (size_t i, size_t _I, size_t _j) |
| Returns reference to S value; see eqn. (43) in [EaG09]. | |
| const Prob & | S (size_t i, size_t _I, size_t _j) const |
| Returns constant reference to S value; see eqn. (43) in [EaG09]. | |
| Prob & | R (size_t I, size_t _i, size_t _J) |
| Returns reference to R value; see eqn. (44) in [EaG09]. | |
| const Prob & | R (size_t I, size_t _i, size_t _J) const |
| Returns constant reference to R value; see eqn. (44) in [EaG09]. | |
| Prob & | adj_n (size_t i, size_t _I) |
| Returns reference to variable->factor message adjoint. | |
| const Prob & | adj_n (size_t i, size_t _I) const |
| Returns constant reference to variable->factor message adjoint. | |
| Prob & | adj_m (size_t i, size_t _I) |
| Returns reference to factor->variable message adjoint. | |
| const Prob & | adj_m (size_t i, size_t _I) const |
| Returns constant reference to factor->variable message adjoint. | |
Parallel algorithm | |
| void | calcNewN (size_t i, size_t _I) |
| Calculates new variable->factor message adjoint. | |
| void | calcNewM (size_t i, size_t _I) |
| Calculates new factor->variable message adjoint. | |
| void | calcUnnormMsgN (size_t i, size_t _I) |
| Calculates unnormalized variable->factor message adjoint from the normalized one. | |
| void | calcUnnormMsgM (size_t i, size_t _I) |
| Calculates unnormalized factor->variable message adjoint from the normalized one. | |
| void | upMsgN (size_t i, size_t _I) |
| Updates (un)normalized variable->factor message adjoints. | |
| void | upMsgM (size_t i, size_t _I) |
| Updates (un)normalized factor->variable message adjoints. | |
| void | doParUpdate () |
| Do one parallel update of all message adjoints. | |
Sequential algorithm | |
| void | incrSeqMsgM (size_t i, size_t _I, const Prob &p) |
| Helper function for sendSeqMsgM(): increases factor->variable message adjoint by p and calculates the corresponding unnormalized adjoint. | |
| void | setSeqMsgM (size_t i, size_t _I, const Prob &p) |
| Sets normalized factor->variable message adjoint and calculates the corresponding unnormalized adjoint. | |
| void | sendSeqMsgN (size_t i, size_t _I, const Prob &f) |
| Implements routine Send-n in Figure 5 in [EaG09]. | |
| void | sendSeqMsgM (size_t i, size_t _I) |
| Implements routine Send-m in Figure 5 in [EaG09]. | |
Private Attributes | |
Input variables | |
| BP_dual | _bp_dual |
| Stores a BP_dual helper object. | |
| const FactorGraph * | _fg |
| Pointer to the factor graph. | |
| const InfAlg * | _ia |
| Pointer to the approximate inference algorithm (currently, only BP objects are supported) | |
Output variables | |
| std::vector< Prob > | _adj_psi_V |
| Variable factor adjoints. | |
| std::vector< Prob > | _adj_psi_F |
| Factor adjoints. | |
| std::vector< std::vector< Prob > > | _adj_n |
| Variable->factor message adjoints (indexed [i][_I]) | |
| std::vector< std::vector< Prob > > | _adj_m |
| Factor->variable message adjoints (indexed [i][_I]) | |
| std::vector< Prob > | _adj_b_V |
| Normalized variable belief adjoints. | |
| std::vector< Prob > | _adj_b_F |
| Normalized factor belief adjoints. | |
Internal state variables | |
| std::vector< Prob > | _init_adj_psi_V |
| Initial variable factor adjoints. | |
| std::vector< Prob > | _init_adj_psi_F |
| Initial factor adjoints. | |
| std::vector< std::vector< Prob > > | _adj_n_unnorm |
| Unnormalized variable->factor message adjoint (indexed [i][_I]) | |
| std::vector< std::vector< Prob > > | _adj_m_unnorm |
| Unnormalized factor->variable message adjoint (indexed [i][_I]) | |
| std::vector< std::vector< Prob > > | _new_adj_n |
| Updated normalized variable->factor message adjoint (indexed [i][_I]) | |
| std::vector< std::vector< Prob > > | _new_adj_m |
| Updated normalized factor->variable message adjoint (indexed [i][_I]) | |
| std::vector< Prob > | _adj_b_V_unnorm |
| Unnormalized variable belief adjoints. | |
| std::vector< Prob > | _adj_b_F_unnorm |
| Unnormalized factor belief adjoints. | |
| std::vector< std::vector< Prob > > | _Tmsg |
| _Tmsg[i][_I] (see eqn. (41) in [EaG09]) | |
| std::vector< std::vector< Prob > > | _Umsg |
| _Umsg[I][_i] (see eqn. (42) in [EaG09]) | |
| std::vector< std::vector < std::vector< Prob > > > | _Smsg |
| _Smsg[i][_I][_j] (see eqn. (43) in [EaG09]) | |
| std::vector< std::vector < std::vector< Prob > > > | _Rmsg |
| _Rmsg[I][_i][_J] (see eqn. (44) in [EaG09]) | |
| size_t | _iters |
| Number of iterations done. | |
Related Functions | |
(Note that these are not member functions.) | |
| Real | numericBBPTest (const InfAlg &bp, const std::vector< size_t > *state, const PropertySet &bbp_props, const BBPCostFunction &cfn, Real h) |
| Function to verify the validity of adjoints computed by BBP using numerical differentiation. | |
Index cache management (for performance) | |
| typedef std::vector< size_t > | _ind_t |
| Index type. | |
| std::vector< std::vector < _ind_t > > | _indices |
| Cached indices (indexed [i][_I]) | |
| void | RegenerateInds () |
| Prepares index cache _indices. | |
| const _ind_t & | _index (size_t i, size_t _I) const |
| Returns an index from the cache. | |
typedef std::vector<size_t> dai::BBP::_ind_t [private] |
Index type.
| dai::BBP::BBP | ( | const InfAlg * | ia, |
| const PropertySet & | opts | ||
| ) | [inline] |
Construct BBP object from a InfAlg ia and a PropertySet opts.
| ia | should be a BP object or something compatible |
| opts | Parameters |
| void dai::BBP::RegenerateInds | ( | ) | [private] |
Prepares index cache _indices.
| const _ind_t& dai::BBP::_index | ( | size_t | i, |
| size_t | _I | ||
| ) | const [inline, private] |
Returns an index from the cache.
| void dai::BBP::RegenerateT | ( | ) | [private] |
Calculate T values; see eqn. (41) in [EaG09].
| void dai::BBP::RegenerateU | ( | ) | [private] |
Calculate U values; see eqn. (42) in [EaG09].
| void dai::BBP::RegenerateS | ( | ) | [private] |
Calculate S values; see eqn. (43) in [EaG09].
| void dai::BBP::RegenerateR | ( | ) | [private] |
Calculate R values; see eqn. (44) in [EaG09].
| void dai::BBP::RegenerateInputs | ( | ) | [private] |
Calculate _adj_b_V_unnorm and _adj_b_F_unnorm from _adj_b_V and _adj_b_F.
| void dai::BBP::RegeneratePsiAdjoints | ( | ) | [private] |
Initialise members for factor adjoints.
| void dai::BBP::RegenerateParMessageAdjoints | ( | ) | [private] |
Initialise members for message adjoints for parallel algorithm.
| void dai::BBP::RegenerateSeqMessageAdjoints | ( | ) | [private] |
Initialise members for message adjoints for sequential algorithm.
Same as RegenerateMessageAdjoints, but calls sendSeqMsgN rather than updating _adj_n (and friends) which are unused in the sequential algorithm.
| void dai::BBP::Regenerate | ( | ) | [private] |
Called by init, recalculates intermediate values.
| Prob& dai::BBP::T | ( | size_t | i, |
| size_t | _I | ||
| ) | [inline, private] |
Returns reference to T value; see eqn. (41) in [EaG09].
| const Prob& dai::BBP::T | ( | size_t | i, |
| size_t | _I | ||
| ) | const [inline, private] |
Returns constant reference to T value; see eqn. (41) in [EaG09].
| Prob& dai::BBP::U | ( | size_t | I, |
| size_t | _i | ||
| ) | [inline, private] |
Returns reference to U value; see eqn. (42) in [EaG09].
| const Prob& dai::BBP::U | ( | size_t | I, |
| size_t | _i | ||
| ) | const [inline, private] |
Returns constant reference to U value; see eqn. (42) in [EaG09].
| Prob& dai::BBP::S | ( | size_t | i, |
| size_t | _I, | ||
| size_t | _j | ||
| ) | [inline, private] |
Returns reference to S value; see eqn. (43) in [EaG09].
| const Prob& dai::BBP::S | ( | size_t | i, |
| size_t | _I, | ||
| size_t | _j | ||
| ) | const [inline, private] |
Returns constant reference to S value; see eqn. (43) in [EaG09].
| Prob& dai::BBP::R | ( | size_t | I, |
| size_t | _i, | ||
| size_t | _J | ||
| ) | [inline, private] |
Returns reference to R value; see eqn. (44) in [EaG09].
| const Prob& dai::BBP::R | ( | size_t | I, |
| size_t | _i, | ||
| size_t | _J | ||
| ) | const [inline, private] |
Returns constant reference to R value; see eqn. (44) in [EaG09].
| Prob& dai::BBP::adj_n | ( | size_t | i, |
| size_t | _I | ||
| ) | [inline, private] |
Returns reference to variable->factor message adjoint.
| const Prob& dai::BBP::adj_n | ( | size_t | i, |
| size_t | _I | ||
| ) | const [inline, private] |
Returns constant reference to variable->factor message adjoint.
| Prob& dai::BBP::adj_m | ( | size_t | i, |
| size_t | _I | ||
| ) | [inline, private] |
Returns reference to factor->variable message adjoint.
| const Prob& dai::BBP::adj_m | ( | size_t | i, |
| size_t | _I | ||
| ) | const [inline, private] |
Returns constant reference to factor->variable message adjoint.
| void dai::BBP::calcNewN | ( | size_t | i, |
| size_t | _I | ||
| ) | [private] |
| void dai::BBP::calcNewM | ( | size_t | i, |
| size_t | _I | ||
| ) | [private] |
| void dai::BBP::calcUnnormMsgN | ( | size_t | i, |
| size_t | _I | ||
| ) | [private] |
Calculates unnormalized variable->factor message adjoint from the normalized one.
| void dai::BBP::calcUnnormMsgM | ( | size_t | i, |
| size_t | _I | ||
| ) | [private] |
Calculates unnormalized factor->variable message adjoint from the normalized one.
| void dai::BBP::upMsgN | ( | size_t | i, |
| size_t | _I | ||
| ) | [private] |
Updates (un)normalized variable->factor message adjoints.
| void dai::BBP::upMsgM | ( | size_t | i, |
| size_t | _I | ||
| ) | [private] |
Updates (un)normalized factor->variable message adjoints.
| void dai::BBP::doParUpdate | ( | ) | [private] |
Do one parallel update of all message adjoints.
| void dai::BBP::incrSeqMsgM | ( | size_t | i, |
| size_t | _I, | ||
| const Prob & | p | ||
| ) | [private] |
Helper function for sendSeqMsgM(): increases factor->variable message adjoint by p and calculates the corresponding unnormalized adjoint.
| void dai::BBP::setSeqMsgM | ( | size_t | i, |
| size_t | _I, | ||
| const Prob & | p | ||
| ) | [private] |
Sets normalized factor->variable message adjoint and calculates the corresponding unnormalized adjoint.
| void dai::BBP::sendSeqMsgN | ( | size_t | i, |
| size_t | _I, | ||
| const Prob & | f | ||
| ) | [private] |
Implements routine Send-n in Figure 5 in [EaG09].
| void dai::BBP::sendSeqMsgM | ( | size_t | i, |
| size_t | _I | ||
| ) | [private] |
Implements routine Send-m in Figure 5 in [EaG09].
Computes the adjoint of the unnormed probability vector from the normalizer and the adjoint of the normalized probability vector.
| Real dai::BBP::getUnMsgMag | ( | ) | [private] |
Calculates averaged L1 norm of unnormalized message adjoints.
Calculates averaged L1 norms of current and new normalized message adjoints.
| void dai::BBP::getArgmaxMsgM | ( | size_t & | i, |
| size_t & | _I, | ||
| Real & | mag | ||
| ) | [private] |
Returns indices and magnitude of the largest normalized factor->variable message adjoint.
| Real dai::BBP::getMaxMsgM | ( | ) | [private] |
Returns magnitude of the largest (in L1-norm) normalized factor->variable message adjoint.
| Real dai::BBP::getTotalMsgM | ( | ) | [private] |
Calculates sum of L1 norms of all normalized factor->variable message adjoints.
| Real dai::BBP::getTotalNewMsgM | ( | ) | [private] |
Calculates sum of L1 norms of all updated normalized factor->variable message adjoints.
| Real dai::BBP::getTotalMsgN | ( | ) | [private] |
Calculates sum of L1 norms of all normalized variable->factor message adjoints.
| std::vector< Prob > dai::BBP::getZeroAdjF | ( | const FactorGraph & | fg | ) | [private] |
Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the factors in the factor graph fg.
| std::vector< Prob > dai::BBP::getZeroAdjV | ( | const FactorGraph & | fg | ) | [private] |
Returns a vector of Probs (filled with zeroes) with state spaces corresponding to the variables in the factor graph fg.
| void dai::BBP::init | ( | const std::vector< Prob > & | adj_b_V, |
| const std::vector< Prob > & | adj_b_F, | ||
| const std::vector< Prob > & | adj_psi_V, | ||
| const std::vector< Prob > & | adj_psi_F | ||
| ) | [inline] |
Initializes from given belief adjoints adj_b_V, adj_b_F and initial factor adjoints adj_psi_V, adj_psi_F.
| void dai::BBP::init | ( | const std::vector< Prob > & | adj_b_V, |
| const std::vector< Prob > & | adj_b_F | ||
| ) | [inline] |
Initializes from given belief adjoints adj_b_V and adj_b_F (setting initial factor adjoints to zero)
| void dai::BBP::init_V | ( | const std::vector< Prob > & | adj_b_V | ) | [inline] |
Initializes variable belief adjoints adj_b_V (and sets factor belief adjoints and initial factor adjoints to zero)
| void dai::BBP::init_F | ( | const std::vector< Prob > & | adj_b_F | ) | [inline] |
Initializes factor belief adjoints adj_b_F (and sets variable belief adjoints and initial factor adjoints to zero)
| void dai::BBP::initCostFnAdj | ( | const BBPCostFunction & | cfn, |
| const std::vector< size_t > * | stateP | ||
| ) |
Initializes with adjoints calculated from cost function cfn, and state stateP.
Uses the internal pointer to an inference algorithm in combination with the cost function and state for initialization.
| void dai::BBP::run | ( | ) |
Perform iterative updates until change is less than given tolerance.
| Prob& dai::BBP::adj_psi_V | ( | size_t | i | ) | [inline] |
Returns reference to variable factor adjoint.
| const Prob& dai::BBP::adj_psi_V | ( | size_t | i | ) | const [inline] |
Returns constant reference to variable factor adjoint.
| Prob& dai::BBP::adj_psi_F | ( | size_t | I | ) | [inline] |
Returns reference to factor adjoint.
| const Prob& dai::BBP::adj_psi_F | ( | size_t | I | ) | const [inline] |
Returns constant reference to factor adjoint.
| Prob& dai::BBP::adj_b_V | ( | size_t | i | ) | [inline] |
Returns reference to variable belief adjoint.
| const Prob& dai::BBP::adj_b_V | ( | size_t | i | ) | const [inline] |
Returns constant reference to variable belief adjoint.
| Prob& dai::BBP::adj_b_F | ( | size_t | I | ) | [inline] |
Returns reference to factor belief adjoint.
| const Prob& dai::BBP::adj_b_F | ( | size_t | I | ) | const [inline] |
Returns constant reference to factor belief adjoint.
| size_t dai::BBP::Iterations | ( | ) | [inline] |
Return number of iterations done so far.
| Real numericBBPTest | ( | const InfAlg & | bp, |
| const std::vector< size_t > * | state, | ||
| const PropertySet & | bbp_props, | ||
| const BBPCostFunction & | cfn, | ||
| Real | h | ||
| ) | [related] |
Function to verify the validity of adjoints computed by BBP using numerical differentiation.
Factors containing a variable are multiplied by small adjustments to verify accuracy of calculated variable factor adjoints.
BP_dual dai::BBP::_bp_dual [private] |
Stores a BP_dual helper object.
const FactorGraph* dai::BBP::_fg [private] |
Pointer to the factor graph.
const InfAlg* dai::BBP::_ia [private] |
Pointer to the approximate inference algorithm (currently, only BP objects are supported)
std::vector<Prob> dai::BBP::_adj_psi_V [private] |
Variable factor adjoints.
std::vector<Prob> dai::BBP::_adj_psi_F [private] |
Factor adjoints.
std::vector<std::vector<Prob> > dai::BBP::_adj_n [private] |
Variable->factor message adjoints (indexed [i][_I])
std::vector<std::vector<Prob> > dai::BBP::_adj_m [private] |
Factor->variable message adjoints (indexed [i][_I])
std::vector<Prob> dai::BBP::_adj_b_V [private] |
Normalized variable belief adjoints.
std::vector<Prob> dai::BBP::_adj_b_F [private] |
Normalized factor belief adjoints.
std::vector<Prob> dai::BBP::_init_adj_psi_V [private] |
Initial variable factor adjoints.
std::vector<Prob> dai::BBP::_init_adj_psi_F [private] |
Initial factor adjoints.
std::vector<std::vector<Prob> > dai::BBP::_adj_n_unnorm [private] |
Unnormalized variable->factor message adjoint (indexed [i][_I])
std::vector<std::vector<Prob> > dai::BBP::_adj_m_unnorm [private] |
Unnormalized factor->variable message adjoint (indexed [i][_I])
std::vector<std::vector<Prob> > dai::BBP::_new_adj_n [private] |
Updated normalized variable->factor message adjoint (indexed [i][_I])
std::vector<std::vector<Prob> > dai::BBP::_new_adj_m [private] |
Updated normalized factor->variable message adjoint (indexed [i][_I])
std::vector<Prob> dai::BBP::_adj_b_V_unnorm [private] |
Unnormalized variable belief adjoints.
std::vector<Prob> dai::BBP::_adj_b_F_unnorm [private] |
Unnormalized factor belief adjoints.
std::vector<std::vector<Prob > > dai::BBP::_Tmsg [private] |
_Tmsg[i][_I] (see eqn. (41) in [EaG09])
std::vector<std::vector<Prob > > dai::BBP::_Umsg [private] |
_Umsg[I][_i] (see eqn. (42) in [EaG09])
std::vector<std::vector<std::vector<Prob > > > dai::BBP::_Smsg [private] |
_Smsg[i][_I][_j] (see eqn. (43) in [EaG09])
std::vector<std::vector<std::vector<Prob > > > dai::BBP::_Rmsg [private] |
_Rmsg[I][_i][_J] (see eqn. (44) in [EaG09])
size_t dai::BBP::_iters [private] |
Number of iterations done.
std::vector<std::vector<_ind_t> > dai::BBP::_indices [private] |
Cached indices (indexed [i][_I])
1.7.4