cc.mallet.grmm.types
Class FactorGraph

java.lang.Object
  cc.mallet.grmm.types.FactorGraph

All Implemented Interfaces:

Factor, java.io.Serializable, java.lang.Cloneable

Direct Known Subclasses:

DirectedModel, UndirectedModel

public class FactorGraph
extends java.lang.Object
implements Factor

Class for undirected graphical models. Created: Mon Sep 15 15:18:30 2003

Version:

$Id: FactorGraph.java,v 1.1 2007/10/22 21:37:44 mccallum Exp $

Author:

Charles Sutton

See Also:

Serialized Form

Constructor Summary

FactorGraph()

FactorGraph(java.util.Collection factors)

FactorGraph(Factor[] factors)

FactorGraph(int capacity)
Create a model with the given capacity (i.e., capacityin terms of number of variable nodes).

FactorGraph(Variable[] vars)
Create a model with the variables given.

Method Summary

void	addFactor(Factor factor) Adds a factor to the model.
void	addFactor(Variable var1, Variable var2, double[] probs)
protected void	afterFactorAdd(Factor factor) Performs operations on a factor after it has been added to the model, such as caching.
java.util.Collection	allFactorsContaining(java.util.Collection vars) Returns a collection of all factors that involve only the given variables.
java.util.List	allFactorsContaining(Variable var)
java.util.List	allFactorsOf(java.util.Collection c) Returns a list of all factors in the graph whose domain is exactly the specified Collection of Variables.
java.util.List	allFactorsOf(Variable var) Returns a list of all factors in the graph whose domain is exactly the specified var.
boolean	almostEquals(Factor p) Returns whether this is almost equal to another potential.
boolean	almostEquals(Factor p, double epsilon)
int	argmax() Returns the assignment that maximizes this potential.
AssignmentIterator	assignmentIterator() Returns an iterator over all assignments to all variables of this graphical model.
AbstractTableFactor	asTable()
protected void	beforeFactorAdd(Factor factor) Performs checking of a factor before it is added to the model.
void	clear() Removes all potentias from this model.
boolean	containsVar(Variable v1) Returns whether this variable is part of the model.
void	divideBy(Factor pot) Computes this /= pot
void	dump() Dumps all the variables and factors of the model to System.out in human-readable text.
void	dump(java.io.PrintWriter out)
java.lang.String	dumpToString()
Factor	duplicate() Returns a copy of this model.
double	entropy() Returns the expected log factor value, i.e., sum_x factor.value(x) * Math.log (factor.value (x)) where the summation is taken over all passible assignments.
void	exponentiate(double power)
Factor	extractMax(java.util.Collection vars) Returns a potential phi over the given variables obtained by taking phi (x) = max_[all v that contain x] this.prob (x)
Factor	extractMax(Variable var) Returns a potential phi over the given variables obtained by taking phi (x) = max_[all v that contain x] this.prob (x)
Factor	extractMax(Variable[] vars) Returns a potential phi over the given variables obtained by taking phi (x) = max_[all v that contain x] this.prob (x)
Factor	factorOf(java.util.Collection c) Searches the graphical model for a factor over the given collection of variables.
Factor	factorOf(Variable var) Returns the factor for a given node.
Factor	factorOf(Variable var1, Variable var2) Returns the factor defined over a given pair of variables.
Factor	factorOf(VarSet varSet) Returns the factor in this graph, if any, whose domain is a given clique.
double	factorProduct(Assignment assn) Returns the unnormalized probability for an assignment to the model.
java.util.Collection	factors() Returns collection that contains factors in this model.
java.util.Iterator	factorsIterator() Returns an iterator of all the factors in the graph.
Variable	findVariable(java.lang.String name) Searches this model for a variable with a given name.
Variable	get(int index) Returns a variable from this model with a given index.
VarSet	getAdjacentVertices(Variable var) Returns all variables that are adjacent to a given variable in this graph---that is, the set of all variables that share a factor with this one.
int	getDegree(Variable var) Returns the degree of a given variable in this factor graph, that is, the number of factors in which the variable is an argument.
Factor	getFactor(int i)
int	getIndex(Factor factor)
int	getIndex(Variable var) Returns a unique numeric index for a variable in this model.
java.lang.Object	getInferenceCache(java.lang.Class inferencer) Caches some information about this graph that is specific to a given type of inferencer (e.g., a junction tree).
Variable	getVariable(int i)
boolean	isAdjacent(Variable v1, Variable v2) Returns whether two variables are adjacent in the model's graph.
boolean	isNaN()
void	logify()
double	logValue(Assignment assn)
double	logValue(AssignmentIterator it)
double	logValue(int loc)
Factor	marginalize(java.util.Collection vars) Returns the marginal of this distribution over the given variables.
Factor	marginalize(Variable var) Returns the marginal of this distribution over one variable.
Factor	marginalize(Variable[] vars) Returns the marginal of this distribution over the given variables.
Factor	marginalizeOut(Variable var) Returns the marginal distribution attained by summing out the given variable.
Factor	marginalizeOut(VarSet varset) Returns the marginal distribution attained by summing out the given set of variables.
Factor	multiply(Factor dist) Returns the elementwise product of this factor with another.
void	multiplyBy(Factor pot) Does this *= pot.
Factor	normalize() Multiplies this potential by a constant such that it sums to 1.
int	numVariables() Returns the number of variable nodes in the graph.
java.lang.String	prettyOutputString()
void	printAsDot(java.io.PrintWriter out)
void	printAsDot(java.io.PrintWriter out, Assignment assn)
void	remove(java.util.Collection vars) Removes a Collection of variables from this model, along with all of its factors.
void	remove(Variable var) Removes a variable from this model, along with all of its factors.
Assignment	sample(Randoms r) Return an assignment sampled from this factor, interpreting it as an unnormalized probability distribution.
Assignment	sampleContinuousVars(Randoms r) Samples the continuous variables in this factor graph.
void	setInferenceCache(java.lang.Class inferencer, java.lang.Object info) Caches some information about this graph that is specific to a given type of inferencer (e.g., a junction tree).
Factor	slice(Assignment assn)
Factor	slice(Assignment assn, java.util.Map toSlicedMap)
double	sum() Returns the sum of this potential over all cases.
java.lang.String	toString()
double	value(Assignment assn) FACTOR IMPLEMENTATION
double	value(AssignmentIterator it) Returns the probability of an assignment to these variables.
java.util.Iterator	variablesIterator()
java.util.Set	variablesSet()
VarSet	varSet() Returns set of variables in this potential.
java.util.Iterator	varSetIterator() Returns an iterator of all the VarSets in the graph over which factors are defined.

Methods inherited from class java.lang.Object

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

Constructor Detail

FactorGraph

public FactorGraph()

FactorGraph

public FactorGraph(Variable[] vars)

Create a model with the variables given. This is much faster than adding the variables one at a time.

FactorGraph

public FactorGraph(Factor[] factors)

FactorGraph

public FactorGraph(java.util.Collection factors)

FactorGraph

public FactorGraph(int capacity)

Create a model with the given capacity (i.e., capacityin terms of number of variable nodes). It can expand later, but declaring the capacity in advance if you know it makes many things more efficient.

Method Detail

numVariables

public int numVariables()

Returns the number of variable nodes in the graph.

variablesSet

public java.util.Set variablesSet()

variablesIterator

public java.util.Iterator variablesIterator()

getAdjacentVertices

public VarSet getAdjacentVertices(Variable var)

Returns all variables that are adjacent to a given variable in this graph---that is, the set of all variables that share a factor with this one.

factors

public java.util.Collection factors()

Returns collection that contains factors in this model.

factorsIterator

public java.util.Iterator factorsIterator()

Returns an iterator of all the factors in the graph.

assignmentIterator

public AssignmentIterator assignmentIterator()

Returns an iterator over all assignments to all variables of this graphical model.

Specified by:

assignmentIterator in interface Factor

See Also:

Assignment

varSetIterator

public java.util.Iterator varSetIterator()

Returns an iterator of all the VarSets in the graph over which factors are defined.

getIndex

public int getIndex(Variable var)

Returns a unique numeric index for a variable in this model. Every UndirectedModel mdl maintains a mapping between its variables and the integers 0...size(mdl)-1 , which is suitable for caching the variables in an array.

getIndex and get are inverses. That is, if idx == getIndex (var), then get(idx) will return var.

Parameters:

var - A variable contained in this graphical model

Returns:

The numeric index of var

See Also:

get(int)

getIndex

public int getIndex(Factor factor)

get

public Variable get(int index)

Returns a variable from this model with a given index. Every UndirectedModel mdl maintains a mapping between its variables and the integers 0...size(mdl)-1 , which is suitable for caching the variables in an array.

getIndex and get are inverses. That is, if idx == getIndex (var), then get(idx) will return var.

See Also:

getIndex(Variable)

getFactor

public Factor getFactor(int i)

getDegree

public int getDegree(Variable var)

Returns the degree of a given variable in this factor graph, that is, the number of factors in which the variable is an argument.

findVariable

public Variable findVariable(java.lang.String name)

Searches this model for a variable with a given name.

Parameters:

name - Name to find.

Returns:

A variable var such that var.getLabel().equals (name)

factorOf

public Factor factorOf(VarSet varSet)

Returns the factor in this graph, if any, whose domain is a given clique.

Returns:

The factor defined over this clique. Returns null if no such factor exists. Will not return potential defined over subsets or supersets of this clique.

See Also:

addFactor(Factor), factorOf(Variable,Variable), factorOf(Variable)

factorOf

public Factor factorOf(Variable var1,
                       Variable var2)

Returns the factor defined over a given pair of variables.

This method is equivalent to calling factorOf(cc.mallet.grmm.types.VarSet) with a VarSet that contains only v1 and v2.

Parameters:

var1 - One variable of the pair.

var2 - The other variable of the pair.

Returns:

The factor defined over the pair (v1, v2) Returns null if no such potential exists.

allFactorsContaining

public java.util.Collection allFactorsContaining(java.util.Collection vars)

Returns a collection of all factors that involve only the given variables. That is, all factors whose domain is a subset of the given collection.

allFactorsContaining

public java.util.List allFactorsContaining(Variable var)

allFactorsOf

public java.util.List allFactorsOf(Variable var)

Returns a list of all factors in the graph whose domain is exactly the specified var.

allFactorsOf

public java.util.List allFactorsOf(java.util.Collection c)

Returns a list of all factors in the graph whose domain is exactly the specified Collection of Variables.

remove

public void remove(Variable var)

Removes a variable from this model, along with all of its factors.

remove

public void remove(java.util.Collection vars)

Removes a Collection of variables from this model, along with all of its factors. This is equivalent to calling remove(Variable) on each element of the collection, but because of the caching performed elsewhere in this class, this method is vastly more efficient.

isAdjacent

public boolean isAdjacent(Variable v1,
                          Variable v2)

Returns whether two variables are adjacent in the model's graph.

Parameters:

v1 - A variable in this model

v2 - Another variable in this model

Returns:

Whether there is an edge connecting them

containsVar

public boolean containsVar(Variable v1)

Returns whether this variable is part of the model.

Specified by:

containsVar in interface Factor

Parameters:

v1 - Any Variable object

Returns:

true if this variable is contained in the moel.

addFactor

public void addFactor(Variable var1,
                      Variable var2,
                      double[] probs)

addFactor

public void addFactor(Factor factor)

Adds a factor to the model.

If a factor has already been added for the variables in the given clique, the effects of this method are (currently) undefined.

All convenience methods for adding factors eventually call through to this one, so this is the method for subclasses to override if they wish to perform additional actions when a factor is added to the graph.

Parameters:

factor - A factor over the variables in clique.

beforeFactorAdd

protected void beforeFactorAdd(Factor factor)

Performs checking of a factor before it is added to the model. This method should throw an unchecked exception if there is a problem. This implementation does nothing, but it may be overridden by subclasses.

Parameters:

factor - Factor that is about to be added

afterFactorAdd

protected void afterFactorAdd(Factor factor)

Performs operations on a factor after it has been added to the model, such as caching. This implementation does nothing, but it may be overridden by subclasses.

Parameters:

factor - Factor that has just been added

clear

public void clear()

Removes all potentias from this model.

factorProduct

public double factorProduct(Assignment assn)

Returns the unnormalized probability for an assignment to the model. That is, the value return is

  \prod_C \phi_C (assn)

where C ranges over all cliques for which factors have been defined.

Parameters:

assn - An assignment for all variables in this model.

Returns:

The unnormalized probability

factorOf

public Factor factorOf(Variable var)

Returns the factor for a given node. That is, this method returns the factor whose domain is exactly this node.

This method is equivalent to calling factorOf(cc.mallet.grmm.types.VarSet) with a clique object that contains only v.

Parameters:

var - which the factor is over.

Returns:

The factor defined over the edge v (such as by addFactor(Factor)). Returns null if no such factor exists.

Throws:

java.lang.RuntimeException - If the model contains more than one factor over the given variable. Use allFactorsOf in this case.

factorOf

public Factor factorOf(java.util.Collection c)

Searches the graphical model for a factor over the given collection of variables.

Returns:

The factor defined over the given collection. Returns null if no such factor exists. Will not return factors defined over subsets or supersets of the given collection.

Throws:

java.lang.RuntimeException - If multiple factors exist over the given collection.

See Also:

allFactorsOf(java.util.Collection), addFactor(Factor), factorOf(VarSet)

duplicate

public Factor duplicate()

Returns a copy of this model. The variable objects are shared between this model and its copy, but the factor objects are deep-copied.

Specified by:

duplicate in interface Factor

dump

public void dump()

Dumps all the variables and factors of the model to System.out in human-readable text.

dump

public void dump(java.io.PrintWriter out)

dumpToString

public java.lang.String dumpToString()

Specified by:

dumpToString in interface Factor

value

public double value(Assignment assn)

FACTOR IMPLEMENTATION

Specified by:

value in interface Factor

value

public double value(AssignmentIterator it)

Description copied from interface: Factor

Returns the probability of an assignment to these variables. The assignment used is the curret assignment from the given AssignmentIterator.

This can be used to do things like

         DiscretePotential phi = createMyPtl ();
         for (AssignmentIterator it = phi.assignmentIterator; it.hasNext(); it.advance()) {
           double val = ptl.phi (it);
                 // do something with val
   }
  

This is equivalent to creating an assignment object explicitly using (Assignment) it.next(), but can be much faster.

Specified by:

value in interface Factor

normalize

public Factor normalize()

Description copied from interface: Factor

Multiplies this potential by a constant such that it sums to 1. Destructive; returns this factor.

Specified by:

normalize in interface Factor

marginalize

public Factor marginalize(Variable[] vars)

Description copied from interface: Factor

Returns the marginal of this distribution over the given variables.

Specified by:

marginalize in interface Factor

marginalize

public Factor marginalize(java.util.Collection vars)

Description copied from interface: Factor

Returns the marginal of this distribution over the given variables.

Specified by:

marginalize in interface Factor

marginalize

public Factor marginalize(Variable var)

Description copied from interface: Factor

Returns the marginal of this distribution over one variable.

Specified by:

marginalize in interface Factor

marginalizeOut

public Factor marginalizeOut(Variable var)

Description copied from interface: Factor

Returns the marginal distribution attained by summing out the given variable.

Specified by:

marginalizeOut in interface Factor

marginalizeOut

public Factor marginalizeOut(VarSet varset)

Description copied from interface: Factor

Returns the marginal distribution attained by summing out the given set of variables.

Specified by:

marginalizeOut in interface Factor

extractMax

public Factor extractMax(java.util.Collection vars)

Description copied from interface: Factor

Returns a potential phi over the given variables obtained by taking phi (x) = max_[all v that contain x] this.prob (x)

Specified by:

extractMax in interface Factor

extractMax

public Factor extractMax(Variable var)

Description copied from interface: Factor

Returns a potential phi over the given variables obtained by taking phi (x) = max_[all v that contain x] this.prob (x)

Specified by:

extractMax in interface Factor

extractMax

public Factor extractMax(Variable[] vars)

Description copied from interface: Factor

Returns a potential phi over the given variables obtained by taking phi (x) = max_[all v that contain x] this.prob (x)

Specified by:

extractMax in interface Factor

argmax

public int argmax()

Description copied from interface: Factor

Returns the assignment that maximizes this potential.

Specified by:

argmax in interface Factor

sample

public Assignment sample(Randoms r)

Description copied from interface: Factor

Return an assignment sampled from this factor, interpreting it as an unnormalized probability distribution.

Specified by:

sample in interface Factor

sampleContinuousVars

public Assignment sampleContinuousVars(Randoms r)

Samples the continuous variables in this factor graph.

sum

public double sum()

Description copied from interface: Factor

Returns the sum of this potential over all cases.

Specified by:

sum in interface Factor

entropy

public double entropy()

Description copied from interface: Factor

Returns the expected log factor value, i.e., sum_x factor.value(x) * Math.log (factor.value (x)) where the summation is taken over all passible assignments.

Specified by:

entropy in interface Factor

multiply

public Factor multiply(Factor dist)

Description copied from interface: Factor

Returns the elementwise product of this factor with another.

Specified by:

multiply in interface Factor

multiplyBy

public void multiplyBy(Factor pot)

Description copied from interface: Factor

Does this *= pot.

If both potentials are currently in log space, then does addition instead.

Specified by:

multiplyBy in interface Factor

exponentiate

public void exponentiate(double power)

Specified by:

exponentiate in interface Factor

divideBy

public void divideBy(Factor pot)

Description copied from interface: Factor

Computes this /= pot

If both potentials are currently in log space, then does subtraction instead.

Specified by:

divideBy in interface Factor

varSet

public VarSet varSet()

Description copied from interface: Factor

Returns set of variables in this potential.

Specified by:

varSet in interface Factor

almostEquals

public boolean almostEquals(Factor p)

Description copied from interface: Factor

Returns whether this is almost equal to another potential.

Specified by:

almostEquals in interface Factor

almostEquals

public boolean almostEquals(Factor p,
                            double epsilon)

Specified by:

almostEquals in interface Factor

isNaN

public boolean isNaN()

Specified by:

isNaN in interface Factor

logValue

public double logValue(AssignmentIterator it)

Specified by:

logValue in interface Factor

logValue

public double logValue(int loc)

Specified by:

logValue in interface Factor

getVariable

public Variable getVariable(int i)

Specified by:

getVariable in interface Factor

slice

public Factor slice(Assignment assn)

Specified by:

slice in interface Factor

slice

public Factor slice(Assignment assn,
                    java.util.Map toSlicedMap)

setInferenceCache

public void setInferenceCache(java.lang.Class inferencer,
                              java.lang.Object info)

Caches some information about this graph that is specific to a given type of inferencer (e.g., a junction tree).

Parameters:

inferencer - Class of inferencer that can use this information

info - The information to cache.

See Also:

getInferenceCache(java.lang.Class)

getInferenceCache

public java.lang.Object getInferenceCache(java.lang.Class inferencer)

Caches some information about this graph that is specific to a given type of inferencer (e.g., a junction tree).

Parameters:

inferencer - Class of inferencer which wants the information

Returns:

Whatever object was previously cached for inferencer using setInferenceCache. Returns null if no object has been cached.

See Also:

setInferenceCache(java.lang.Class, java.lang.Object)

logify

public void logify()

logValue

public double logValue(Assignment assn)

Specified by:

logValue in interface Factor

asTable

public AbstractTableFactor asTable()

Specified by:

asTable in interface Factor

prettyOutputString

public java.lang.String prettyOutputString()

Specified by:

prettyOutputString in interface Factor

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

printAsDot

public void printAsDot(java.io.PrintWriter out)

printAsDot

public void printAsDot(java.io.PrintWriter out,
                       Assignment assn)