A framework for message passing algorithms

Cf. F. R. Kschischang, B. J. Frey and H.-A. Loeliger, "Factor Graphs and the Sum-Product Algorithm", IEEE Transactions on Information Theory 47:498-519, 2001. More...

#include <messagepassing.hxx>

Inheritance diagram for opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >:

Collaboration diagram for opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >:

Classes
struct	Parameter

struct	RebindGm

struct	RebindGmAndAcc

Public Types
typedef GM	GraphicalModelType

typedef ACC	Accumulation

typedef ACC	AccumulatorType

typedef DIST	Distance

typedef UPDATE_RULES::FactorHullType	FactorHullType

typedef UPDATE_RULES::VariableHullType	VariableHullType

typedef visitors::VerboseVisitor< MessagePassing< GM, ACC, UPDATE_RULES, DIST > >	VerboseVisitorType
	Visitor. More...

typedef visitors::TimingVisitor< MessagePassing< GM, ACC, UPDATE_RULES, DIST > >	TimingVisitorType
	Visitor. More...

typedef visitors::EmptyVisitor< MessagePassing< GM, ACC, UPDATE_RULES, DIST > >	EmptyVisitorType
	Visitor. More...

Public Types inherited from opengm::Inference< GM, ACC >
typedef GM	GraphicalModelType

typedef ACC	AccumulationType

typedef GraphicalModelType::LabelType	LabelType

typedef GraphicalModelType::IndexType	IndexType

typedef GraphicalModelType::ValueType	ValueType

typedef GraphicalModelType::OperatorType	OperatorType

typedef GraphicalModelType::FactorType	FactorType

typedef GraphicalModelType::IndependentFactorType	IndependentFactorType

typedef GraphicalModelType::FunctionIdentifier	FunctionIdentifier

Public Member Functions
	MessagePassing (const GraphicalModelType &, const Parameter &=Parameter())

std::string	name () const

const GraphicalModelType &	graphicalModel () const

InferenceTermination	marginal (const size_t, IndependentFactorType &out) const
	output a solution for a marginal for a specific variable More...

InferenceTermination	factorMarginal (const size_t, IndependentFactorType &out) const
	output a solution for a marginal for all variables connected to a factor More...

ValueType	convergenceXF () const
	cumulative distance between all pairs of messages from variables to factors (between the previous and the current interation) More...

ValueType	convergenceFX () const
	cumulative distance between all pairs of messages from factors to variables (between the previous and the current interation) More...

ValueType	convergence () const
	cumulative distance between all pairs of messages (between the previous and the current interation) More...

virtual void	reset ()

InferenceTermination	infer ()

template<class VisitorType >
InferenceTermination	infer (VisitorType &)

void	propagate (const ValueType &=0)
	invoke one iteration of message passing More...

InferenceTermination	arg (std::vector< LabelType > &, const size_t=1) const
	output a solution More...

void	setMaxSteps (size_t maxSteps)

Public Member Functions inherited from opengm::Inference< GM, ACC >
virtual	~Inference ()

virtual void	setStartingPoint (typename std::vector< LabelType >::const_iterator)
	set initial labeling More...

virtual InferenceTermination	args (std::vector< std::vector< LabelType > > &) const

virtual ValueType	bound () const
	return a bound on the solution More...

virtual ValueType	value () const
	return the solution (value) More...

InferenceTermination	constrainedOptimum (std::vector< IndexType > &, std::vector< LabelType > &, std::vector< LabelType > &) const

InferenceTermination	modeFromMarginal (std::vector< LabelType > &) const

InferenceTermination	modeFromFactorMarginal (std::vector< LabelType > &) const

Public Attributes
	OPENGM_GM_TYPE_TYPEDEFS

Detailed Description

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>
class opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >

A framework for message passing algorithms

Cf. F. R. Kschischang, B. J. Frey and H.-A. Loeliger, "Factor Graphs and the Sum-Product Algorithm", IEEE Transactions on Information Theory 47:498-519, 2001.

Examples:: grid_potts.cxx, and markov-chain.cxx.

Definition at line 50 of file messagepassing.hxx.

Member Typedef Documentation

§ Accumulation

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef ACC opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::Accumulation

Definition at line 53 of file messagepassing.hxx.

§ AccumulatorType

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef ACC opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::AccumulatorType

Definition at line 54 of file messagepassing.hxx.

§ Distance

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef DIST opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::Distance

Definition at line 56 of file messagepassing.hxx.

§ EmptyVisitorType

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef visitors::EmptyVisitor<MessagePassing<GM, ACC, UPDATE_RULES, DIST> > opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::EmptyVisitorType

Visitor.

Definition at line 65 of file messagepassing.hxx.

§ FactorHullType

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef UPDATE_RULES::FactorHullType opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::FactorHullType

Definition at line 57 of file messagepassing.hxx.

§ GraphicalModelType

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef GM opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::GraphicalModelType

Definition at line 52 of file messagepassing.hxx.

§ TimingVisitorType

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef visitors::TimingVisitor<MessagePassing<GM, ACC, UPDATE_RULES, DIST> > opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::TimingVisitorType

Visitor.

Definition at line 63 of file messagepassing.hxx.

§ VariableHullType

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef UPDATE_RULES::VariableHullType opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::VariableHullType

Definition at line 58 of file messagepassing.hxx.

§ VerboseVisitorType

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

typedef visitors::VerboseVisitor<MessagePassing<GM, ACC, UPDATE_RULES, DIST> > opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::VerboseVisitorType

Visitor.

Definition at line 61 of file messagepassing.hxx.

Constructor & Destructor Documentation

§ MessagePassing()

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::MessagePassing	(	const GraphicalModelType &	,
		const Parameter &	= `Parameter()`
	)

Definition at line 180 of file messagepassing.hxx.

Here is the caller graph for this function:

Member Function Documentation

§ arg()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

InferenceTermination opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::arg	(	std::vector< LabelType > &	arg,
		const size_t	argIndex = `1`
	)		const

inlinevirtual

output a solution

Parameters

[out]	arg	labeling
	argIndex	solution index (1=best, 2=second best, etc.)

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 622 of file messagepassing.hxx.

Here is the caller graph for this function:

§ convergence()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

MessagePassing< GM, ACC, UPDATE_RULES, DIST >::ValueType opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::convergence ( ) const

inline

cumulative distance between all pairs of messages (between the previous and the current interation)

Definition at line 615 of file messagepassing.hxx.

Here is the call graph for this function:

§ convergenceFX()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

MessagePassing< GM, ACC, UPDATE_RULES, DIST >::ValueType opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::convergenceFX ( ) const

inline

cumulative distance between all pairs of messages from factors to variables (between the previous and the current interation)

Definition at line 599 of file messagepassing.hxx.

§ convergenceXF()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

MessagePassing< GM, ACC, UPDATE_RULES, DIST >::ValueType opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::convergenceXF ( ) const

inline

cumulative distance between all pairs of messages from variables to factors (between the previous and the current interation)

Definition at line 583 of file messagepassing.hxx.

§ factorMarginal()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

InferenceTermination opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::factorMarginal	(	const size_t	factorIndex,
		IndependentFactorType &	out
	)		const

inlinevirtual

output a solution for a marginal for all variables connected to a factor

Parameters

	factorIndex	index of the factor
[out]	out	the marginal

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 569 of file messagepassing.hxx.

Here is the caller graph for this function:

§ graphicalModel()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

const MessagePassing< GM, ACC, UPDATE_RULES, DIST >::GraphicalModelType & opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::graphicalModel ( ) const

inlinevirtual

Implements opengm::Inference< GM, ACC >.

Definition at line 238 of file messagepassing.hxx.

§ infer() [1/2]

template<class GM , class ACC , class UPDATE_RULES , class DIST >

InferenceTermination opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::infer ( )

inlinevirtual

Implements opengm::Inference< GM, ACC >.

Definition at line 244 of file messagepassing.hxx.

Here is the call graph for this function:

§ infer() [2/2]

template<class GM , class ACC , class UPDATE_RULES , class DIST >

template<class VisitorType >

InferenceTermination opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::infer ( VisitorType & visitor )

inline

Definition at line 253 of file messagepassing.hxx.

Here is the call graph for this function:

§ marginal()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

InferenceTermination opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::marginal	(	const size_t	variableIndex,
		IndependentFactorType &	out
	)		const

inlinevirtual

output a solution for a marginal for a specific variable

Parameters

	variableIndex	index of the variable
[out]	out	the marginal

Reimplemented from opengm::Inference< GM, ACC >.

Definition at line 557 of file messagepassing.hxx.

Here is the call graph for this function:

Here is the caller graph for this function:

§ name()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

std::string opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::name ( ) const

inlinevirtual

Implements opengm::Inference< GM, ACC >.

Definition at line 232 of file messagepassing.hxx.

§ propagate()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

void opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::propagate ( const ValueType & damping = 0 )

inline

invoke one iteration of message passing

Definition at line 394 of file messagepassing.hxx.

Here is the call graph for this function:

Here is the caller graph for this function:

§ reset()

template<class GM , class ACC , class UPDATE_RULES , class DIST >

void opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::reset ( )

virtual

Definition at line 209 of file messagepassing.hxx.

§ setMaxSteps()

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

void opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::setMaxSteps ( size_t maxSteps )

inline

Definition at line 157 of file messagepassing.hxx.

Here is the call graph for this function:

Member Data Documentation

§ OPENGM_GM_TYPE_TYPEDEFS

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>

opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >::OPENGM_GM_TYPE_TYPEDEFS

Definition at line 55 of file messagepassing.hxx.

Classes

Public Types

Public Member Functions

Public Attributes

Detailed Description

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance> class opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >

Member Typedef Documentation

§ Accumulation

§ AccumulatorType

§ Distance

§ EmptyVisitorType

§ FactorHullType

§ GraphicalModelType

§ TimingVisitorType

§ VariableHullType

§ VerboseVisitorType

Constructor & Destructor Documentation

§ MessagePassing()

Member Function Documentation

§ arg()

§ convergence()

§ convergenceFX()

§ convergenceXF()

§ factorMarginal()

§ graphicalModel()

§ infer() [1/2]

§ infer() [2/2]

§ marginal()

§ name()

§ propagate()

§ reset()

§ setMaxSteps()

Member Data Documentation

§ OPENGM_GM_TYPE_TYPEDEFS

template<class GM, class ACC, class UPDATE_RULES, class DIST = opengm::MaxDistance>
class opengm::MessagePassing< GM, ACC, UPDATE_RULES, DIST >