

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object  +javaslam.tjt.JunctionTree  +javaslam.tjt.ThinJunctionTree
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 runningintersection 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).
Nested Class Summary  
class 
ThinJunctionTree.Contraction
Represents a variable contraction of a variable v along an edge e = C_{i} >
C_{j}. 
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 runningintersection 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 nonroot 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 
protected PriorityQueue clustersBySize
Constructor Detail 
public ThinJunctionTree()
Method Detail 
public String toString()
toString
in class JunctionTree
public int width()
protected void updateClusterSize(JunctionTree.Cluster c)
clustersBySize
index of cluster sizes.
c
 the cluster whose size has changedprotected JunctionTree.Cluster largestCluster()
protected void enlarge(JunctionTree.Cluster c, Variable var)
enlarge
and then record the change in the cluster's size.
enlarge
in class JunctionTree
var
 the variable to be added to the clusterJunctionTree.extend(JunctionTree.Cluster,Variable)
protected void reduce(JunctionTree.Cluster c, Variable var)
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.
reduce
in class JunctionTree
var
 the variable to be added to the clusterprotected JunctionTree.Cluster newLeaf(JunctionTree.Cluster c)
newLeaf
and then record the cluster in the priority queue.
newLeaf
in class JunctionTree
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
IllegalArgumentException
 if c == null
but this junction tree is not emptyprotected void remove(JunctionTree.Cluster c)
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.
remove
in class JunctionTree
c
 the cluster to be removed
IllegalArgumentException
 if c
is connected
to any other clusters of the
junction treepublic ThinJunctionTree.Contraction getContraction(JunctionTree.JTEdge e, Variable v)
v
 the variable to be contractede
 the edge along which the variable should be contracted
v
along e
public JunctionTree.Cluster clone(JunctionTree.Cluster c)
c
 the cluster to be cloned
protected double thin(int limit)
limit
.
limit
 the cluster size limit
protected JunctionTree.JTEdge isSubtreeLeaf(JunctionTree.Cluster c, Variable v)
v
is the set of clusters that contain
v
; because of the singlyconnected and
runningintersection 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 singlyconnected and runningintersection 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.
c
 a clusterv
 a variable contained in c
JTEdge
to
c
from its neighbor in the subtree, or
null
if c
is not a nonroot leaf
of the subtree induced by v
IllegalArgumentException
 if c
does not
contain v
public double thin(JunctionTree.Cluster c, int limit, Variable exclude)
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.
c
 the cluster to be thinnedlimit
 the size to which the cluster should be thinnedexclude
 if not null
, this variable will not
be removed from c
UnsupportedOperationException
 if not enough variables in
c
appear elsewherepublic void contractTo(Variable var, JunctionTree.Cluster cluster)
var
from all clusters but cluster
(which must contain var
).
var
 the variable to be contractedcluster
 a cluster containing varpublic JunctionTree.Cluster contract(Variable var)
var
from all clusters but one and returns
that cluster.
var
 the variable to be contracted


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 