golib  0.5
Public Member Functions | List of all members
goMaxSum< T, Tfloat > Class Template Reference
Belief propagation and factor graphs

The max-sum algorithm. More...

#include <gomaxsum.h>

Public Member Functions

virtual bool run (goFGNode< T, Tfloat > *root, goFactorGraph< T, Tfloat > &fg)
 Run the max-sum algorithm. More...
 
bool variableSend (goFGNode< T, Tfloat > *fgn, goIndex_t parentIndex)
 Create and "send" message from a variable node fgn along a given edge. More...
 
bool factorSend (goFGNode< T, Tfloat > *fgn, goSize_t parentIndex)
 Calculate outgoing message for a factor node in the max-sum algorithm. More...
 
bool forwardPass (goFGNode< T, Tfloat > *node)
 
bool backwardPass (goFGNode< T, Tfloat > *node)
 
Tfloat maxsum (goFGNodeFactor< T, Tfloat > *factorNode, goFunctorBase1< Tfloat, const goMath::Vector< T > & > *f, goMath::Vector< T > &X, goSize_t i, goSize_t fixed_index, Tfloat currentMax, goMath::Vector< T > &maxX)
 Recursive max/sum for the max-sum algorithm. More...
 
bool flooding (goFGNode< T, Tfloat > *startNode, goFactorGraph< T, Tfloat > &fg, goSize_t maxPasses=0)
 "Flooding" type scheme for graphs with loops. More...
 
virtual bool action (goFGNode< T, Tfloat > *node)
 
- Public Member Functions inherited from goMessagePassing< T, Tfloat >
goDouble sum (goFunctorBase1< Tfloat, const goMath::Vector< T > & > *f, goMath::Vector< T > &X, goSize_t i, goSize_t fixed_index)
 Recursive sum. More...
 
void setValueCount (goSize_t c)
 
goSize_t getValueCount () const
 
void setDirection (Direction d)
 
Direction getDirection () const
 
- Public Member Functions inherited from goGraphAlgorithm< goFGNode< T, Tfloat >, goFGEdge< T, Tfloat > >
bool breadthFirst (goFGNode< T, Tfloat > *root)
 BFS. More...
 
bool breadthFirstTree (goFGNode< T, Tfloat > *root)
 
bool depthFirstRecursive (goFGNode< T, Tfloat > *root)
 
bool depthFirst (goFGNode< T, Tfloat > *root)
 
bool depthFirstTree (goFGNode< T, Tfloat > *root)
 Same as depthFirst(), plus fills parent fields in the nodes. More...
 
virtual bool action (const goFGNode< T, Tfloat > *node) const
 

Additional Inherited Members

- Public Types inherited from goMessagePassing< T, Tfloat >
enum  Direction { FORWARD, BACKWARD }
 

Detailed Description

template<class T, class Tfloat>
class goMaxSum< T, Tfloat >

The max-sum algorithm.

Note
The factors in the factor graph must return logarithms, no extra log() is called.
References:
  Kschischang, F.R. & Frey, B.J. 
  Iterative Decoding of Compound Codes by Probability Propagation in Graphical Models 
  IEEE Journal on Selected Areas in Communications, 1998, 16, 219-230

  F.R. Kschischang; B.J. Frey & H. Loeliger 
  Factor Graphs and the Sum-Product Algorithm 
  IEEE Transactions on Information Theory, 2001, 47, 498-508

  Bishop, C.M. 
  Pattern Recognition and Machine Learning 
  Springer, 2006
Author
Christian Gosch
Examples
sumproduct/sp.cpp.

Member Function Documentation

◆ factorSend()

template<class T, class Tfloat>
bool goMaxSum< T, Tfloat >::factorSend ( goFGNode< T, Tfloat > *  fgn,
goSize_t  parentIndex 
)
inline

Calculate outgoing message for a factor node in the max-sum algorithm.

Parameters
fgnFactor node.
parentIndexIndex into fgn->adj pointing to the "parent" link, i.e. the link where the message is sent to.
Returns
True if successful, false otherwise.

◆ flooding()

template<class T, class Tfloat>
bool goMaxSum< T, Tfloat >::flooding ( goFGNode< T, Tfloat > *  startNode,
goFactorGraph< T, Tfloat > &  fg,
goSize_t  maxPasses = 0 
)
inline

"Flooding" type scheme for graphs with loops.

Uses a sort of flooding message passing schedule (not parallel, but driven by a queue of pending messages).

Note
Notice that this will fail to give a consistent maximising configuration in case there are multiple maximising configurations. We are simply applying the maximisation to all variable nodes locally instead of using a backtracking step (which does not work here .. is that a bug or does it generally not work?).
Parameters
startNode"Root" node. Does not serve any purpose as long as no backtracking is implemented.
fgFactor graph to work on.
maxPassesMaximal number of passes each node is allowed to send messages for. If 0 (default), the algorithm will terminate when no more messages are pending. If there are loops in the graph and maxPasses is 0, the algorithm will run indefinitely.
Returns
True if successful, false otherwise.

◆ maxsum()

template<class T, class Tfloat>
Tfloat goMaxSum< T, Tfloat >::maxsum ( goFGNodeFactor< T, Tfloat > *  factorNode,
goFunctorBase1< Tfloat, const goMath::Vector< T > & > *  f,
goMath::Vector< T > &  X,
goSize_t  i,
goSize_t  fixed_index,
Tfloat  currentMax,
goMath::Vector< T > &  maxX 
)
inline

Recursive max/sum for the max-sum algorithm.

Calculates $ \max\limits_{x_1,\ldots,x_M} \left[ \ln f(x,x_1,\ldots,x_M) + \sum\limits_{m \in neighbours(f)\backslash x} \mu_{x_m \mapsto f}(x_m) \right] $ with x being the variable with fixed_index, $x_1,\ldots,x_M$ the other variables connected to factorNode, and $\mu$ the messages stored in the edges between the variable nodes and factorNode. The above term constitutes the messages $ \mu_{f \mapsto x}(x) $ for the max-sum algorithm.

Parameters
factorNodeFactor node to calculate on.
fFunctor of factorNode (usually, but can also be a different one).
XInput for f
iCurrent index into X we are summing over.
fixed_indexIndex into X of the variable that is held fixed (not summed over).
currentMaxCurrent maximum – start with a value lower than all other occuring values.
maxXMaximising variable values – set by this function.
Returns
The max/sum value.

◆ run()

template<class T, class Tfloat>
bool goMaxSum< T, Tfloat >::run ( goFGNode< T, Tfloat > *  root,
goFactorGraph< T, Tfloat > &  fg 
)
inlinevirtual

Run the max-sum algorithm.

Parameters
fgFactor graph to run the algorithm on.
valueCountThe values of the variables are in the range [0,valueCount-1].
Returns
True if successful, false otherwise.

Implements goMessagePassing< T, Tfloat >.

◆ variableSend()

template<class T, class Tfloat>
bool goMaxSum< T, Tfloat >::variableSend ( goFGNode< T, Tfloat > *  fgn,
goIndex_t  parentIndex 
)
inline

Create and "send" message from a variable node fgn along a given edge.

Parameters
fgnVariable node to send from.
parentIndexIndex into fgn->adj of edge to send the message along (the other connected node is a variable and "receives" the message).
Returns
True if successful, false otherwise.
The documentation for this class was generated from the following files: