javaslam.tjt
Class JunctionTree

java.lang.Object
  |
  +--javaslam.tjt.JunctionTree

Direct Known Subclasses:

ThinJunctionTree

public class JunctionTree

extends Object

A junction tree for a Gaussian graphical model. A junction tree over a set of potentials is a graph whose nodes (called clusters) are sets of variables and that has three properties:

1. singly-connected property: the graph is a tree; and,
2. potential property: all potentials that have been added to this junction tree are covered by at least one cluster; and,
3. running intersection property: if C₁ and C₂ are clusters that contain the variable x, then all clusters (and separators) on the (unique) path between C₁ and C₂ also contain x.

In addition, each edge has an associated separator which is the intersection of its two incident clusters. Finally, every cluster and separator has an associated potential function over its variables. A junction tree is consistent if each separator potential agrees with (the appropriate marginal of) its incident clusters' potentials. If a junction tree is valid (meaning all of the above properties hold) and it is consistent, then each of its cluster (and separator) potentials are marginal distributions for the graphical model defined by the normalized product of the potentials in the junction tree.

This implementation is designed to efficiently support incremental operations such as adding new variables, multiplying in new potentials, and marginalizing out variables; at all times, the junction tree remains valid and consistent so that cluster marginals are accessible in constant time.

Nested Class Summary

class	JunctionTree.Cluster A cluster of a junction tree.
protected class	JunctionTree.JTEdge A (directed) edge from one cluster to another in a junction tree.

Field Summary

protected ListSet	clusters The Clusters in this junction tree.
protected double	significance A threshold used in adaptive message passing.
protected Set	updated The set of clusters that have been updated with new evidence but have not yet distributed their evidence (due to lazy or adaptive message passing).
protected ListSet	variables The Variables present in this junction tree.
protected Map	varToClusters Maps each Variable to the Set of Clusters containing it.

Constructor Summary

JunctionTree()
Default constructor.

Method Summary

protected void	add(Variable var) Adds a variable to this junction tree.
protected JunctionTree.Cluster	bestCover(Set vars) Returns the cluster whose intersection with the supplied set of variables is largest and whose size is the smallest.
protected JunctionTree.Cluster	bestCoverToExtend(Set vars) Returns the cluster that, if extended with the variables in vars, would cause the fewest number of cluster enlargements.
void	checkValid() Tests to see if the junction tree is valid.
boolean	consistent() Tests to see if the junction tree is consistent.
boolean	contains(Variable var) Returns true if this junction tree contains the supplied variable.
protected JunctionTree.Cluster	createCover(Set vars) Updates this junction tree so that it has a cluster containing the supplied set of variables, while preserving validity and consistency.
protected void	enlarge(JunctionTree.Cluster c, Variable var) Extends the supplied cluster so that it contains the supplied variable without preserving consistency or the running-intersection property.
protected void	extend(JunctionTree.Cluster cluster, Variable var) Minimally alters the structure and parameterization of the junction tree so that cluster covers var and validity and consistency are preserved.
Set	getClusters() Returns a Sets of the JunctionTree.Clusters of this junction tree.
Set	getClustersWith(Variable var) Returns an unmodifiable set of Clusters containing the supplied variable.
protected JunctionTree.Cluster	getCover(Set vars) Returns the smallest cluster containing the supplied variables, or null if there is no such cluster.
Gaussian	getMarginal(Set vars, boolean force) Extracts the marginal from the junction tree.
Map	getMarginals(Collection vars) Extracts a set of unary marginals from the junction tree without inverting any cluster potential more than once.
Set	getVariables() Gets an unmodifiable set of the Variables in this junction tree.
protected void	link(JunctionTree.Cluster c1, JunctionTree.Cluster c2) Adds a new pair of edges between the supplied clusters.
void	marginalizeOut(Variable var) Marginalizes a variable out of this junction tree.
protected JunctionTree.Cluster	merge(JunctionTree.JTEdge e) Merges the two clusters that are incident to the supplied edge.
protected JunctionTree.Cluster	mergeClustersWith(Variable var) Merges all clusters containing a particular variable.
protected JunctionTree.Cluster	newLeaf(JunctionTree.Cluster c) Creates an empty cluster and attaches it as a leaf off of the supplied cluster.
int[]	parents() Returns a directed representation of the junction tree.
void	passFlows() Restores consistency; all clusters into new potentials have been multiplied that have not yet distributed their evidence do so.
protected void	reduce(JunctionTree.Cluster c, Variable var) Reduces the supplied cluster so that it no longer contains the supplied variable.
protected void	remove(JunctionTree.Cluster c) Removes a cluster from this junction tree.
protected void	remove(Variable var) Removes a variable from this junction tree.
void	rename(Variable var, Variable subst) Renames a variable in this junction tree.
void	setSignificance(double s) Sets a threshold used in adaptive message passing.
JunctionTree.Cluster	times(Gaussian p) Multiplies a new potential into the junction tree and restores validity (but not consistency).
void	times(Gaussian p, JunctionTree.Cluster cluster) Multiplies a new potential into a particular cluster of this junction tree and restores validity (but not consistency).
String	toString() Returns a String representation of this junction tree.

Methods inherited from class java.lang.Object

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

Field Detail

variables

protected ListSet variables

The Variables present in this junction tree. This set's iterator is consistent with the order in which the variables were added to the junction tree.

clusters

protected ListSet clusters

The Clusters in this junction tree.

varToClusters

protected Map varToClusters

Maps each Variable to the Set of Clusters containing it. Variables that are not currently in the junction tree may still be in this map, but they will map to empty sets.

updated

protected Set updated

The set of clusters that have been updated with new evidence but have not yet distributed their evidence (due to lazy or adaptive message passing). When this set is empty, the junction tree is consistent.

significance

protected double significance

A threshold used in adaptive message passing. If significance is non-negative, then when distributing evidence from a cluster, messages are only propagated while the differential relative entropy (or kl divergence) from a separator potential to its new value (in nats) after the message is passed is larger than significance.

See Also:

JunctionTree.Cluster.distributeEvidence(JunctionTree.Cluster,double)

Constructor Detail

JunctionTree

public JunctionTree()

Default constructor. significance is initialized to -1.0 so that all messages will be passed.

Method Detail

setSignificance

public void setSignificance(double s)

Sets a threshold used in adaptive message passing. If s is non-negative, then when distributing evidence from a cluster, messages are only propagated while the differential relative entropy (or kl divergence) from a separator potential to its new value (in nats) after the message is passed is larger than s.

Parameters:

s - the new threshold value

See Also:

JunctionTree.Cluster.distributeEvidence(JunctionTree.Cluster,double)

contains

public boolean contains(Variable var)

Returns true if this junction tree contains the supplied variable.

getVariables

public Set getVariables()

Gets an unmodifiable set of the Variables in this junction tree. The iteration order of this set is the order in which the variables were added to the juntion tree.

getClusters

public Set getClusters()

Returns a Sets of the JunctionTree.Clusters of this junction tree.

Returns:

a Sets of the JunctionTree.Clusters of this junction tree.

remove

protected void remove(Variable var)

Removes a variable from this junction tree.

Parameters:

var - the variable to be removed

Throws:

IllegalArgumentException - if var is present in any cluster of the junction tree

add

protected void add(Variable var)

Adds a variable to this junction tree.

Parameters:

var - the variable to be added

rename

public void rename(Variable var,
                   Variable subst)

Renames a variable in this junction tree.

Parameters:

var - the original variable

subst - the variable substituted for the original variable

Throws:

IllegalArgumentException - if var and subst have differing dimensions

getClustersWith

public Set getClustersWith(Variable var)

Returns an unmodifiable set of Clusters containing the supplied variable.

Returns:

the set of Clusters of this junction tree that contain var or null if var is not in the junction tree

getCover

protected JunctionTree.Cluster getCover(Set vars)

Returns the smallest cluster containing the supplied variables, or null if there is no such cluster.

Parameters:

vars - a set of Variables

Returns:

the smallest cluster containing vars or null if there is no such cluster

times

public void times(Gaussian p,
                  JunctionTree.Cluster cluster)

Multiplies a new potential into a particular cluster of this junction tree and restores validity (but not consistency). If the supplied potential acts on variables that are not yet present in the junction tree, these variables are first added to the junction tree.

Parameters:

p - the potential to be multiplied in

cluster - the cluster into which it should be multiplied

times

public JunctionTree.Cluster times(Gaussian p)

Multiplies a new potential into the junction tree and restores validity (but not consistency). If the supplied potential acts on variables that are not yet present in the junction tree, these variables are first added to the junction tree.

Parameters:

p - the potential to be multiplied in

Returns:

the cluster into which p was multiplied

enlarge

protected void enlarge(JunctionTree.Cluster c,
                       Variable var)

Extends the supplied cluster so that it contains the supplied variable without preserving consistency or the running-intersection property.

It is part of the contract of this class that whenever a variable is added to a cluster, this method must be invoked.

Parameters:

var - the variable to be added to the cluster

See Also:

extend(JunctionTree.Cluster,Variable)

reduce

protected void reduce(JunctionTree.Cluster c,
                      Variable var)

Reduces the supplied cluster so that it no longer contains the supplied variable. The cluster potential is updated by marginalizing out this variables as well. This method preserves consistency, but it makes no attempt to ensure the running intersection property; that property will only persist if c is a leaf of the subtree induced by var.

It is part of the contract of this class that whenever a variable is removed from a cluster, this method must be invoked; However, this method is not invoked if a cluster is removed from the junction tree entirely; in that case, remove is called instead.

Parameters:

var - the variable to be added to the cluster

remove

protected void remove(JunctionTree.Cluster c)

Removes a cluster from this junction tree. This method only works if c is not connected to any other clusters.

It is part of the contract of this class that this method is invoked whenever a cluster is removed from the junction tree.

Parameters:

c - the cluster to be removed

Throws:

IllegalArgumentException - if c is connected to any other clusters of the junction tree

newLeaf

protected JunctionTree.Cluster newLeaf(JunctionTree.Cluster c)

Creates an empty cluster and attaches it as a leaf off of the supplied cluster. This method is the only correct way to create a new junction tree cluster.

It is part of the contract of this class that this method is invoked whenever a new cluster is added to the junction tree.

Parameters:

c - the cluster to which the new cluster will be attached as a leaf; this may be null if the junction tree currently has no clusters

Returns:

the new cluster

Throws:

IllegalArgumentException - if c == null but this junction tree is not empty

extend

protected void extend(JunctionTree.Cluster cluster,
                      Variable var)

Minimally alters the structure and parameterization of the junction tree so that cluster covers var and validity and consistency are preserved.

Algorithm: In order to restore the running intersection property, the closest cluster C containing var is found, and var is added to all clusters (and separators) on the path to C. Consistency is restored by passing flows backwards along this path. This operation can result in non-maximal clusters; these are subsequently detected by traversing the path and removed by cluster merging.

Parameters:

cluster - a cluster of the junction tree to be extended

var - the variable to be added to the cluster

bestCover

protected JunctionTree.Cluster bestCover(Set vars)

Returns the cluster whose intersection with the supplied set of variables is largest and whose size is the smallest.

Parameters:

vars - a Set of Variables

Returns:

the cluster whose intersection with vars is largest and whose size is the smallest

bestCoverToExtend

protected JunctionTree.Cluster bestCoverToExtend(Set vars)

Returns the cluster that, if extended with the variables in vars, would cause the fewest number of cluster enlargements. This differs from the result of bestCover(Set) because it takes into account the cost of restoring the running intersection property. (Note that there may be a better cluster to extend---in that its extension will increase the width of the junction tree by a smaller amount---but this criterion is a fairly good and cheap heuristic.)

Parameters:

vars - a Set of Variables

Returns:

the best choice of clusters to extend with the variables in vars

createCover

protected JunctionTree.Cluster createCover(Set vars)

Updates this junction tree so that it has a cluster containing the supplied set of variables, while preserving validity and consistency. The bestCoverToExtend is found and then is extended to cover each variable in vars.

Parameters:

vars - the set of Variables that must be covered

Returns:

the cover created for vars

merge

protected JunctionTree.Cluster merge(JunctionTree.JTEdge e)

Merges the two clusters that are incident to the supplied edge. The "to" cluster is merged into the "from" cluster. All edges incident to the "to" cluster are "swung" over to the "from" cluster. This method preserves validity and consistency.

Parameters:

e - the edge whose incident clusters are to be merged

Returns:

the merged cluster (which is the same as e.from)

mergeClustersWith

protected JunctionTree.Cluster mergeClustersWith(Variable var)

Merges all clusters containing a particular variable. The resulting merged cluster is returned.

Parameters:

var - the variable whose cover clusters are to be merged

Returns:

the merged cluster

marginalizeOut

public void marginalizeOut(Variable var)

Marginalizes a variable out of this junction tree. If the junction tree was previously consistent, then it will be consistent after this method is invoked. All clusters containing the variable are merged together and then the variable is marginalized out of the resulting cluster.

Parameters:

var - the variable to be marginalized out

passFlows

public void passFlows()

Restores consistency; all clusters into new potentials have been multiplied that have not yet distributed their evidence do so. If no new potentials have been multiplied into the junction tree since the last time this method was invoked, then this method does nothing.

getMarginal

public Gaussian getMarginal(Set vars,
                            boolean force)

Extracts the marginal from the junction tree. This method first calls passFlows() to ensure the junction tree is consistent.

Parameters:

vars - the set of Variables whose marginal is to be computed

force - if true, then the junction tree is restructured if necessary to compute the marginal; otherwise, null is returned if there is no cover for vars in this junction tree.

Returns:

a marginal potential over vars (in the canonical parameterization), or null if force is false and vars do not reside together in a cluster of the junction tree

getMarginals

public Map getMarginals(Collection vars)

Extracts a set of unary marginals from the junction tree without inverting any cluster potential more than once. This method first calls passFlows() to ensure the junction tree is consistent.

Parameters:

vars - a collection of Variables, or null to indicate all variables in this junction tree

Returns:

a map whose keys are the (distinct) elements of vars and whose values are the corresponding Gaussian marginals (in the moment parameterization)

toString

public String toString()

Returns a String representation of this junction tree.

Overrides:

toString in class Object

checkValid

public void checkValid()

Tests to see if the junction tree is valid. A valid junction tree has three properties:

1. potential property: all potentials that have been added to this junction tree are covered by at least one cluster; (this is not checked)
2. singly-connected property: the graph is a tree; and
3. running intersection property: if C₁ and C₂ are clusters that contain the variable x, then all clusters (and separators) on the (unique) path between C₁ and C₂ also contain x.

(This method is superfluous, since all public methods of this class preserve the validity of the junction tree. It is provided as a debugging tool.)

Throws:

InternalError - if this junction tree is invalid

consistent

public boolean consistent()

Tests to see if the junction tree is consistent. A junction tree is consistent if each separator potential agrees with (the appropriate marginal of) its incident clusters' potentials. (This method is provided as a debugging tool.)

parents

public int[] parents()

Returns a directed representation of the junction tree. An array of integer parent indices into the iteration order of the set returned by getClusters(). The cluster whose parent index is 0 is the root.

This function is provided to facilitate the plotting of junction trees in Matlab.

Returns:

An array of integer parent indices into the iteration order of the set returned by getClusters()

link

protected void link(JunctionTree.Cluster c1,
                    JunctionTree.Cluster c2)

Adds a new pair of edges between the supplied clusters. The separator is initialized to unity.

Parameters:

c1 - a cluster

c2 - another cluster