libDAI
|
Exact inference algorithm using junction tree. More...
#include <dai/jtree.h>
Classes | |
struct | Properties |
Parameters for JTree. More... | |
Public Member Functions | |
Constructors/destructors | |
JTree () | |
Default constructor. More... | |
JTree (const FactorGraph &fg, const PropertySet &opts, bool automatic=true) | |
Construct from FactorGraph fg and PropertySet opts. More... | |
General InfAlg interface | |
virtual JTree * | clone () const |
Returns a pointer to a new, cloned copy of *this (i.e., virtual copy constructor) More... | |
virtual JTree * | 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 VarSet &vs) const |
Returns the (approximate) marginal probability distribution of a set of variables. 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... | |
std::vector< size_t > | findMaximum () const |
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... | |
Additional interface specific for JTree | |
void | construct (const FactorGraph &fg, const std::vector< VarSet > &cl, bool verify=false) |
Constructs a junction tree based on the cliques cl (corresponding to some elimination sequence). More... | |
void | GenerateJT (const FactorGraph &fg, const std::vector< VarSet > &cl) |
Constructs a junction tree based on the cliques cl (corresponding to some elimination sequence). More... | |
const Factor & | message (size_t alpha, size_t _beta) const |
Returns constant reference to the message from outer region alpha to its _beta 'th neighboring inner region. More... | |
Factor & | message (size_t alpha, size_t _beta) |
Returns reference to the message from outer region alpha to its _beta 'th neighboring inner region. More... | |
void | runHUGIN () |
Runs junction tree algorithm using HUGIN (message-free) updates. More... | |
void | runShaferShenoy () |
Runs junction tree algorithm using Shafer-Shenoy updates. More... | |
size_t | findEfficientTree (const VarSet &vs, RootedTree &Tree, size_t PreviousRoot=(size_t)-1) const |
Finds an efficient subtree for calculating the marginal of the variables in vs. More... | |
Factor | calcMarginal (const VarSet &vs) |
Calculates the marginal of a set of variables (using cutset conditioning, if necessary) 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 | belief (const Var &v) const |
Returns the (approximate) marginal probability distribution of a variable. More... | |
virtual Factor | beliefV (size_t i) const |
Returns the (approximate) marginal probability distribution of the variable with index i. More... | |
virtual Factor | beliefF (size_t I) const |
Returns the (approximate) marginal probability distribution of the variables on which factor I depends. More... | |
virtual void | setMaxIter (size_t) |
Sets maximum number of iterations (one iteration passes over the complete factorgraph). More... | |
Public Attributes | |
RootedTree | RTree |
The junction tree (stored as a rooted tree) More... | |
std::vector< Factor > | Qa |
Outer region beliefs. More... | |
std::vector< Factor > | Qb |
Inner region beliefs. More... | |
struct dai::JTree::Properties | props |
Private Attributes | |
std::vector< std::vector< Factor > > | _mes |
Stores the messages. More... | |
Real | _logZ |
Stores the logarithm of the partition sum. More... | |
Related Functions | |
(Note that these are not member functions.) | |
std::pair< size_t, BigInt > | boundTreewidth (const FactorGraph &fg, greedyVariableElimination::eliminationCostFunction fn, size_t maxStates=0) |
Calculates upper bound to the treewidth of a FactorGraph, using the specified heuristic. More... | |
Exact inference algorithm using junction tree.
The junction tree algorithm uses message passing on a junction tree to calculate exact marginal probability distributions ("beliefs") for specified cliques (outer regions) and separators (intersections of pairs of cliques).
There are two variants, the sum-product algorithm (corresponding to finite temperature) and the max-product algorithm (corresponding to zero temperature).
|
inline |
Default constructor.
dai::JTree::JTree | ( | const FactorGraph & | fg, |
const PropertySet & | opts, | ||
bool | automatic = true |
||
) |
Construct from FactorGraph fg and PropertySet opts.
fg | factor graph |
opts | Parameters |
automatic | if true , construct the junction tree automatically, using the heuristic in opts['heuristic']. |
|
inlinevirtual |
Returns a pointer to a new, cloned copy of *this
(i.e., virtual copy constructor)
Implements dai::InfAlg.
Reimplemented in dai::TreeEP.
|
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.
Reimplemented in dai::TreeEP.
|
inlinevirtual |
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 all beliefs (approximate marginal probability distributions) calculated by the algorithm.
Implements dai::InfAlg.
|
virtual |
Returns the logarithm of the (approximated) partition sum (normalizing constant of the factor graph).
NOT_IMPLEMENTED | if not implemented/supported |
Implements dai::InfAlg.
Reimplemented in dai::TreeEP.
|
virtual |
MAXPROD
Reimplemented from dai::InfAlg.
|
inlinevirtual |
Initializes all data structures of the approximate inference algorithm.
Implements dai::InfAlg.
Reimplemented in dai::TreeEP.
|
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.
Reimplemented in dai::TreeEP.
|
virtual |
Runs the approximate inference algorithm.
Implements dai::InfAlg.
Reimplemented in dai::TreeEP.
|
inlinevirtual |
Returns maximum difference between single variable beliefs in the last iteration.
NOT_IMPLEMENTED | if not implemented/supported |
Reimplemented from dai::InfAlg.
Reimplemented in dai::TreeEP.
|
inlinevirtual |
Returns number of iterations done (one iteration passes over the complete factorgraph).
NOT_IMPLEMENTED | if not implemented/supported |
Reimplemented from dai::InfAlg.
Reimplemented in dai::TreeEP.
|
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.
Reimplemented in dai::TreeEP.
|
virtual |
Returns parameters of this inference algorithm converted into a PropertySet.
Implements dai::InfAlg.
Reimplemented in dai::TreeEP.
|
virtual |
Returns parameters of this inference algorithm formatted as a string in the format "[key1=val1,key2=val2,...,keyn=valn]".
Implements dai::InfAlg.
Reimplemented in dai::TreeEP.
void dai::JTree::construct | ( | const FactorGraph & | fg, |
const std::vector< VarSet > & | cl, | ||
bool | verify = false |
||
) |
Constructs a junction tree based on the cliques cl (corresponding to some elimination sequence).
First, constructs a weighted graph, where the nodes are the elements of cl, and each edge is weighted with the cardinality of the intersection of the state spaces of the nodes. Then, a maximal spanning tree for this weighted graph is calculated. Subsequently, a corresponding region graph is built:
true
, checks whether each factor is subsumed by a clique. void dai::JTree::GenerateJT | ( | const FactorGraph & | fg, |
const std::vector< VarSet > & | cl | ||
) |
Constructs a junction tree based on the cliques cl (corresponding to some elimination sequence).
Invokes construct() and then constructs messages.
|
inline |
Returns constant reference to the message from outer region alpha to its _beta 'th neighboring inner region.
|
inline |
Returns reference to the message from outer region alpha to its _beta 'th neighboring inner region.
void dai::JTree::runHUGIN | ( | ) |
Runs junction tree algorithm using HUGIN (message-free) updates.
void dai::JTree::runShaferShenoy | ( | ) |
Runs junction tree algorithm using Shafer-Shenoy updates.
size_t dai::JTree::findEfficientTree | ( | const VarSet & | vs, |
RootedTree & | Tree, | ||
size_t | PreviousRoot = (size_t)-1 |
||
) | const |
Finds an efficient subtree for calculating the marginal of the variables in vs.
First, the current junction tree is reordered such that it gets as root the clique that has maximal state space overlap with vs. Then, the minimal subtree (starting from the root) is identified that contains all the variables in vs and also the outer region with index PreviousRoot (if specified). Finally, the current junction tree is reordered such that this minimal subtree comes before the other edges, and the size of the minimal subtree is returned.
Calculates the marginal of a set of variables (using cutset conditioning, if necessary)
|
related |
Calculates upper bound to the treewidth of a FactorGraph, using the specified heuristic.
fg | the factor graph for which the treewidth should be bounded |
fn | the heuristic cost function used for greedy variable elimination |
maxStates | maximum total number of states in outer regions of junction tree (0 means no limit) |
OUT_OF_MEMORY | if the total number of states becomes larger than maxStates |
|
private |
Stores the messages.
|
private |
Stores the logarithm of the partition sum.
RootedTree dai::JTree::RTree |
The junction tree (stored as a rooted tree)
std::vector<Factor> dai::JTree::Qa |
Outer region beliefs.
std::vector<Factor> dai::JTree::Qb |
Inner region beliefs.