il2.inf.bp
Class BeliefPropagation

Object
  extended by BeliefPropagation
Direct Known Subclasses:
MaxProduct

public abstract class BeliefPropagation
extends Object

some implementation notes: = we perform message-passing on the factor graph representation of a given Table[] array. This is not exactly belief propagation on a Bayesian network, although the approximations will be the same. = this implementation employs a somewhat minor performance optimization. Namely, we do not pass messages to and from a factor mentioning a single variable. I may refer to this as a "unit table" (analagous to unit clause), or sometimes as a "twig" (as in the treewidth-based reduction rule). This enhancement may be effective in networks with many unit tables, e.g., as in the large grid graphs used in low-level vision tasks such as stereo. This type of message passing is equivalent to ED-BP where we delete ALL factor graph edges EXCEPT twig edges (edges from a node to a unit factor). = I use Shenoy-Shafer style message passing; Hugin style message passing should make things faster; at least for passing messages from variable nodes. Hugin-style message passing may lead to significant speed-up at some relatively small expense in memory requirements. Hugin-style message passing may not be desirable for factor nodes, as they require us to maintain factor marginals.


Constructor Summary
BeliefPropagation(Table[] tables, int mi, long tm, double ct)
           
BeliefPropagation(Table[] tables, MessagePassingScheduler s, int mi, long tm, double ct)
           
 
Method Summary
 boolean converged()
           
 double getCompilationTime()
           
 double getPropagationTime()
           
 int iterations()
           
abstract  double logPrEvidence()
           
 double oneMoreIteration(boolean restart)
           
abstract  double prEvidence()
           
 double residual()
           
 void setEvidence(IntMap e)
           
 void setTable(int i, Table t)
           
abstract  Table tableConditional(int table)
           
abstract  Table tableJoint(int table)
           
 long timeMillis()
           
abstract  Table varConditional(int var)
           
abstract  Table varJoint(int var)
           
 
Methods inherited from class Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BeliefPropagation

public BeliefPropagation(Table[] tables,
                         MessagePassingScheduler s,
                         int mi,
                         long tm,
                         double ct)

BeliefPropagation

public BeliefPropagation(Table[] tables,
                         int mi,
                         long tm,
                         double ct)
Method Detail

oneMoreIteration

public double oneMoreIteration(boolean restart)

setEvidence

public void setEvidence(IntMap e)

setTable

public void setTable(int i,
                     Table t)

logPrEvidence

public abstract double logPrEvidence()

prEvidence

public abstract double prEvidence()

tableConditional

public abstract Table tableConditional(int table)

tableJoint

public abstract Table tableJoint(int table)

varConditional

public abstract Table varConditional(int var)

varJoint

public abstract Table varJoint(int var)

converged

public boolean converged()

residual

public double residual()

iterations

public int iterations()

timeMillis

public long timeMillis()

getCompilationTime

public double getCompilationTime()

getPropagationTime

public double getPropagationTime()


Copyright 2010 UCLA Automated Reasoning Group