gov.sandia.cognition.graph.inference

Class SumProductInferencingAlgorithm<LabelType>

java.lang.Object

gov.sandia.cognition.graph.inference.SumProductInferencingAlgorithm<LabelType>

Type Parameters:

LabelType - The type for labels

All Implemented Interfaces:

EnergyFunctionSolver<LabelType>

Direct Known Subclasses:

SumProductBeliefPropagation, SumProductDirectedPropagation

@PublicationReference(author="Jonahtan S. Yedidia, William T. Freeman, and Yair Weiss",
                      title="Understanding Belief Propagation and its Generalizations",
                      type=TechnicalReport,
                      year=2001,
                      notes="Institution: Mitsubishi Electric Research Laboratories")
public abstract class SumProductInferencingAlgorithm<LabelType>
extends java.lang.Object
implements EnergyFunctionSolver<LabelType>

Base class for Sum-Product inferencing algorithms on graphs/energy functions

Author:

jdwendt, tong

Field Summary

Fields

Modifier and Type	Field and Description
static double	DEFAULT_EPS The default stopping epsilon that will be used
static int	DEFAULT_MAX_ITERATIONS The default maximum number of iterations that will be run
static int	DEFAULT_NUM_THREADS The default number of threads that will be used
protected EnergyFunction<LabelType>	fn The input energy function to learn against
protected java.util.List<gov.sandia.cognition.graph.inference.Node<LabelType>>	nodes This internally stores the nodes with their values for the learning

Constructor Summary

Constructors

Constructor and Description
SumProductInferencingAlgorithm() Creates a new solver with the default settings.
SumProductInferencingAlgorithm(int maxNumIterations) Creates a new solver with the default settings excepting max number of iterations.
SumProductInferencingAlgorithm(int maxNumIterations, double eps, int numThreads) Creates a new solver with the specified settings.

Method Summary

Modifier and Type	Method and Description
protected abstract void	computeTemporaryMessage(int edge) Private helper that computes the temporary message for the specified edge for the current iteration going in the specified direction (a different message for each direction)
double	getBelief(int i, int label) Gets the belief for node i with the specified label.
void	init(EnergyFunction<LabelType> f) Initializes internal state and stores the energy function for future solutions.
boolean	solve() Solves for the energy function passed in during initialize, e.g., compute the beliefs.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_EPS

public static final double DEFAULT_EPS

The default stopping epsilon that will be used

See Also:

Constant Field Values

DEFAULT_MAX_ITERATIONS

public static final int DEFAULT_MAX_ITERATIONS

The default maximum number of iterations that will be run

See Also:

Constant Field Values

DEFAULT_NUM_THREADS

public static final int DEFAULT_NUM_THREADS

The default number of threads that will be used

See Also:

Constant Field Values

nodes

protected java.util.List<gov.sandia.cognition.graph.inference.Node<LabelType>> nodes

This internally stores the nodes with their values for the learning

fn

protected EnergyFunction<LabelType> fn

The input energy function to learn against

Constructor Detail

SumProductInferencingAlgorithm

public SumProductInferencingAlgorithm(int maxNumIterations,
                                      double eps,
                                      int numThreads)

Creates a new solver with the specified settings.

Parameters:

maxNumIterations - The maximum number of iterations that will be run

eps - The stopping epsilon that will be used

numThreads - The number of threads that will be used

SumProductInferencingAlgorithm

public SumProductInferencingAlgorithm(int maxNumIterations)

Creates a new solver with the default settings excepting max number of iterations.

Parameters:

maxNumIterations - The maximum number of iterations that will be run

SumProductInferencingAlgorithm

public SumProductInferencingAlgorithm()

Creates a new solver with the default settings.

Method Detail

solve

public boolean solve()

Description copied from interface: EnergyFunctionSolver

Solves for the energy function passed in during initialize, e.g., compute the beliefs.

Specified by:

solve in interface EnergyFunctionSolver<LabelType>

Returns:

true if converged, false otherwise.

computeTemporaryMessage

protected abstract void computeTemporaryMessage(int edge)

Private helper that computes the temporary message for the specified edge for the current iteration going in the specified direction (a different message for each direction)

Parameters:

edge - The edge to compute the temporary message for (you can't replace the current message yet as the current message may be needed for other edges).

init

public void init(EnergyFunction<LabelType> f)

Description copied from interface: EnergyFunctionSolver

Initializes internal state and stores the energy function for future solutions. The energy function can still change its unary and pairwise method outputs after this is called, but the number of nodes, edges, etc. must stay constant.

Specified by:

init in interface EnergyFunctionSolver<LabelType>

Parameters:

f - The energy function to initialize against

getBelief

public double getBelief(int i,
                        int label)

Description copied from interface: EnergyFunctionSolver

Gets the belief for node i with the specified label. This can only be called after solve().

Specified by:

getBelief in interface EnergyFunctionSolver<LabelType>

Parameters:

i - The index of the node whose belief associated with the input label is wanted

label - The label for the node whose belief is desired

Returns:

The belief for the input node/label pair