javaslam.tjt
Class ThinJunctionTree

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

public class ThinJunctionTree

extends JunctionTree

A thin (approximate) junction tree for a Gaussian graphical model. The width of this junction tree (and hence its time complexity for inference) can be constrained by employing variable contractions, in which variables are removed from clusters in such a way as to preserve the running-intersection property.

In this implementation, the width of a junction tree is defined to be the maximum size of its clusters; another implementation could redefine the width to be the maximum dimension of its clusters. This latter notion of width makes more sense because the complexity of inference is related more tightly to the dimension of its clusters than their sizes; however, it also requires splitting vector variables, which is complex to implement.

This class records counts of all floating point operations using Flops.count(long) (except those used in the service of debugging and avoiding numerical errors).

See Also:

"Thin junction tree filters for simultaneous localization and mapping. Mark A. Paskin. Computer Science Division Technical Report CSD-02-1198, University of California, Berkeley. 2002."

Nested Class Summary

class

ThinJunctionTree.Contraction Represents a variable contraction of a variable v along an edge e = Ci -> Cj.

Nested classes inherited from class javaslam.tjt.JunctionTree

JunctionTree.Cluster, JunctionTree.JTEdge

Field Summary

protected PriorityQueue

clustersBySize A priority queue of clusters prioritized by their size.

Fields inherited from class javaslam.tjt.JunctionTree

clusters, significance, updated, variables, varToClusters

Constructor Summary

ThinJunctionTree()
Default constructor.

Method Summary

JunctionTree.Cluster	clone(JunctionTree.Cluster c) Duplicates the supplied cluster and attaches the duplicate as a leaf off of the original cluster.
JunctionTree.Cluster	contract(Variable var) Contracts var from all clusters but one and returns that cluster.
void	contractTo(Variable var, JunctionTree.Cluster cluster) Contracts var from all clusters but cluster (which must contain var).
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.
ThinJunctionTree.Contraction	getContraction(JunctionTree.JTEdge e, Variable v) Creates a variable contraction of the supplied variable along the supplied edge.
protected JunctionTree.JTEdge	isSubtreeLeaf(JunctionTree.Cluster c, Variable v) Determines if the supplied cluster is a non-root leaf of the subtree induced by the supplied variable.
protected JunctionTree.Cluster	largestCluster() Returns the cluster with largest size in the junction tree.
protected JunctionTree.Cluster	newLeaf(JunctionTree.Cluster c) Creates an empty cluster and attaches it as a leaf off of the supplied cluster.
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 double	thin(int limit) Thins the junction tree via a sequence of variable contractions so that no clusters have a size greater than limit.
double	thin(JunctionTree.Cluster c, int limit, Variable exclude) Removes variables from the supplied cluster so as to ensure its size is no greater than limit.
String	toString() Returns a String representation of this thin junction tree.
protected void	updateClusterSize(JunctionTree.Cluster c) Updates the clustersBySize index of cluster sizes.
int	width() Computes the width of this junction tree.

Methods inherited from class javaslam.tjt.JunctionTree

add, bestCover, bestCoverToExtend, checkValid, consistent, contains, createCover, extend, getClusters, getClustersWith, getCover, getMarginal, getMarginals, getVariables, link, marginalizeOut, merge, mergeClustersWith, parents, passFlows, remove, rename, setSignificance, times, times

Methods inherited from class java.lang.Object

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

Field Detail

clustersBySize

protected PriorityQueue clustersBySize

A priority queue of clusters prioritized by their size.

Constructor Detail

ThinJunctionTree

public ThinJunctionTree()

Default constructor.

Method Detail

toString

public String toString()

Returns a String representation of this thin junction tree.

Overrides:

toString in class JunctionTree

width

public int width()

Computes the width of this junction tree. The width is the size of the largest cluster in the junction tree.

Returns:

the size of the largest cluster in this junction tree

updateClusterSize

protected void updateClusterSize(JunctionTree.Cluster c)

Updates the clustersBySize index of cluster sizes.

Parameters:

c - the cluster whose size has changed

largestCluster

protected JunctionTree.Cluster largestCluster()

Returns the cluster with largest size in the junction tree.

Returns:

the cluster with largest size in the junction tree

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. This method is overrided here to call enlarge and then record the change in the cluster's size.

Overrides:

enlarge in class JunctionTree

Parameters:

var - the variable to be added to the cluster

See Also:

JunctionTree.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. This method is overrided here to call reduce and then record the change in the cluster's size.

Overrides:

reduce in class JunctionTree

Parameters:

var - the variable to be added to the cluster

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 overrided here to call newLeaf and then record the cluster in the priority queue.

Overrides:

newLeaf in class JunctionTree

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

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. This method is overrided here to call remove and then remove the cluster from the priority queue.

Overrides:

remove in class JunctionTree

Parameters:

c - the cluster to be removed

Throws:

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

getContraction

public ThinJunctionTree.Contraction getContraction(JunctionTree.JTEdge e,
                                                   Variable v)

Creates a variable contraction of the supplied variable along the supplied edge.

Parameters:

v - the variable to be contracted

e - the edge along which the variable should be contracted

Returns:

a variable contraction of v along e

clone

public JunctionTree.Cluster clone(JunctionTree.Cluster c)

Duplicates the supplied cluster and attaches the duplicate as a leaf off of the original cluster. This operation preserves consistency and validity.

Parameters:

c - the cluster to be cloned

Returns:

the clone

thin

protected double thin(int limit)

Thins the junction tree via a sequence of variable contractions so that no clusters have a size greater than limit.

Parameters:

limit - the cluster size limit

Returns:

the approximation error introduced by the thinning; this error is the Kullback-Liebler divergence from the original distribution to the thinner distribution (in natural logarithmic units)

isSubtreeLeaf

protected JunctionTree.JTEdge isSubtreeLeaf(JunctionTree.Cluster c,
                                            Variable v)

Determines if the supplied cluster is a non-root leaf of the subtree induced by the supplied variable. The subtree induced by v is the set of clusters that contain v; because of the singly-connected and running-intersection properties, this set must be a tree. If c is a leaf of this subtree (and is not the only cluster in this subtree), then this method returns the JTEdge to c from its neighbor in the subtree; otherwise, this method returns null.

Algorithm: This implementation tests if c has exactly one neighbor that also contains v. Assuming the singly-connected and running-intersection properties hold, this is necessary and sufficient for c to be a leaf of v's induced subtree. Then it returns the edge to c from this neighbor.

Parameters:

c - a cluster

v - a variable contained in c

Returns:

the JTEdge to c from its neighbor in the subtree, or null if c is not a non-root leaf of the subtree induced by v

Throws:

IllegalArgumentException - if c does not contain v

thin

public double thin(JunctionTree.Cluster c,
                   int limit,
                   Variable exclude)

Removes variables from the supplied cluster so as to ensure its size is no greater than limit. The approximation error introduced is returned. If not enough variables can be removed to satisfy the supplied limit, then an exception is thrown.

This method evaluates the approximation error that would arise from contracting each variable that does not only occur in c and chooses the contraction that results in the least amount of error.

Parameters:

c - the cluster to be thinned

limit - the size to which the cluster should be thinned

exclude - if not null, this variable will not be removed from c

Returns:

the approximation error introduced by the thinning; this error is the Kullback-Liebler divergence from the original distribution to the thinner distribution (in natural logarithmic units)

Throws:

UnsupportedOperationException - if not enough variables in c appear elsewhere

contractTo

public void contractTo(Variable var,
                       JunctionTree.Cluster cluster)

Contracts var from all clusters but cluster (which must contain var).

Parameters:

var - the variable to be contracted

cluster - a cluster containing var

contract

public JunctionTree.Cluster contract(Variable var)

Contracts var from all clusters but one and returns that cluster.

Parameters:

var - the variable to be contracted

Returns:

the only cluster containing var