com.aliasi.crf
Class ForwardBackwardTagLattice<E>

java.lang.Object
  extended by com.aliasi.tag.TagLattice<E>
      extended by com.aliasi.crf.ForwardBackwardTagLattice<E>
Type Parameters:
E - Type of tokens in the lattice.

public class ForwardBackwardTagLattice<E>
extends TagLattice<E>

The ForwardBackwardTagLattice provides an implementation of a tag lattice based on forward, backward, transition and normalizing values.

The forward and backward values are available through logBackward(int,int) and logForward(int,int); see the method doc for details on the indexing. Transition values are available through logTransition(int,int,int). The normalizing term is returned by logZ().

Typically, this class is used only as a return object, not as a return type. For instance, the marginal tagging interface for HMMs and CRFs specifies the return type only as implementing TagLattice. The class is public here so that there is some public way available for creating tag lattices from their component pieces.

Since:
LingPipe3.9
Version:
3.9
Author:
Bob Carpenter

Constructor Summary
ForwardBackwardTagLattice(List<E> tokens, List<String> tags, double[][] logForwards, double[][] logBackwards, double[][][] logTransitions, double logZ)
          Construct a log tag lattice from the specified list of tokens, list of tags in order of symbol identifier along with log forward, backward, transition and normalizing values on a log probability scale.
 
Method Summary
 double logBackward(int token, int tag)
          Returns the log of the backward probability to the specified token and tag.
 double logForward(int token, int tag)
          Return the log of the forward probability of the specified tag at the specified position.
 double logProbability(int token, int tag)
          Return the log of the conditional probability that the specified token has the specified tag, given the complete list of input tokens.
 double logProbability(int tokenFrom, int[] tags)
          Return the log conditional probability that the tokens starting with the specified token position have the specified tags given the complete sequence of input tokens.
 double logProbability(int tokenTo, int tagFrom, int tagTo)
          Convenience method returning the log of the conditional probability that the specified two tokens have the specified tag given the complete list of input tokens.
 double logTransition(int tokenFrom, int tagFrom, int tagTo)
          Returns the log of the transition probability from the specified input token position with the specified previous tag to the specified target tag.
 double logZ()
          Return the log of the normalizing constant for the lattice.
 int numTags()
          Return the number of tags in this tag lattice.
 int numTokens()
          Returns the length of this tag lattice as measured by number of tokens.
 String tag(int id)
          Return the tag with the specified symbol identifier.
 List<String> tagList()
          Returns an unmodifiable view of the list of tags used in this lattice, indexed by identifier.
 SymbolTable tagSymbolTable()
          Returns a symbol table which converts tags to identifiers and vice-versa.
 E token(int n)
          Return the token at the specified position in the input.
 List<E> tokenList()
          Return an unmodifiable view of the underlying tokens for this tag lattice.
 String toString()
          Return a string-based representation of this tag lattice.
 
Methods inherited from class com.aliasi.tag.TagLattice
tokenClassification
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

ForwardBackwardTagLattice

public ForwardBackwardTagLattice(List<E> tokens,
                                 List<String> tags,
                                 double[][] logForwards,
                                 double[][] logBackwards,
                                 double[][][] logTransitions,
                                 double logZ)
Construct a log tag lattice from the specified list of tokens, list of tags in order of symbol identifier along with log forward, backward, transition and normalizing values on a log probability scale.

The lists of tokens and tags are copied so that changes to the supplied list will not affect the constructed lattice.

The probabilities returned are all relative the normalizing term logZ, which might not even be negative. True probabilities are computed as described in the class documentation above.

See the class documentation above for information on how these arrays are used to compute probabilities.

Warning: No check is made to ensure the log probabilities are coherent, only that the arrays are the right size and are filled with non-positive numbers.

Parameters:
tokens - Underlying tokens in order.
tags - List of tags in symbol order.
logForwards - Log forward probabilities.
logBackwards - Log backward probabilities.
logTransitions - Log transition probabilities.
logZ - Log normalizing probability.
Throws:
IllegalArgumentException - If the various arrays are not properly sized, meaning for tokens of length N and tags of length K, logForwards[N][K], logBackward[N][K], logTransitions[N-1][K][K], where N is the size of the tokens list and K the length of the tags array, or if any of the log probabilities is not finite.
Method Detail

tokenList

public List<E> tokenList()
Description copied from class: TagLattice
Return an unmodifiable view of the underlying tokens for this tag lattice.

Specified by:
tokenList in class TagLattice<E>
Returns:
The tokens for this lattice.

tagList

public List<String> tagList()
Description copied from class: TagLattice
Returns an unmodifiable view of the list of tags used in this lattice, indexed by identifier.

Specified by:
tagList in class TagLattice<E>
Returns:
The symbol table for tags.

tag

public String tag(int id)
Description copied from class: TagLattice
Return the tag with the specified symbol identifier.

Specified by:
tag in class TagLattice<E>
Parameters:
id - Identifer for tag.
Returns:
Tag with specified ID.

numTags

public int numTags()
Description copied from class: TagLattice
Return the number of tags in this tag lattice.

Specified by:
numTags in class TagLattice<E>
Returns:
Number of tags for this tag lattice.

token

public E token(int n)
Description copied from class: TagLattice
Return the token at the specified position in the input.

Specified by:
token in class TagLattice<E>
Parameters:
n - Input position.
Returns:
Token at position.

numTokens

public int numTokens()
Description copied from class: TagLattice
Returns the length of this tag lattice as measured by number of tokens.

Specified by:
numTokens in class TagLattice<E>
Returns:
Number of tokens in this lattice.

tagSymbolTable

public SymbolTable tagSymbolTable()
Description copied from class: TagLattice
Returns a symbol table which converts tags to identifiers and vice-versa.

A new symbol table is constructed for each call, so it should be saved and reused if possible. Changing the returned symbol table will not affect this lattice.

Specified by:
tagSymbolTable in class TagLattice<E>
Returns:
Symbol table for tags in this lattice.

logProbability

public double logProbability(int token,
                             int tag)
Return the log of the conditional probability that the specified token has the specified tag, given the complete list of input tokens.

Specified by:
logProbability in class TagLattice<E>
Parameters:
token - Position of input token.
tag - Identifier of tag.
Returns:
The log probability the token has the tag.
Throws:
ArrayIndexOutOfBoundsException - If the token or tag identifiers are not in range.

logProbability

public double logProbability(int tokenTo,
                             int tagFrom,
                             int tagTo)
Description copied from class: TagLattice
Convenience method returning the log of the conditional probability that the specified two tokens have the specified tag given the complete list of input tokens.

This method returns results defined by

 logProbability(nTo,tagFrom,tagTo) 
     == logProbability(n-1,new int[] { tagFrom, tagTo })

Specified by:
logProbability in class TagLattice<E>
Parameters:
tokenTo - Position of second token.
tagFrom - First Tag from which transition is made.
tagTo - Second Tag to which transition is made.
Returns:
Log probability of the tags at the specified position.

logProbability

public double logProbability(int tokenFrom,
                             int[] tags)
Return the log conditional probability that the tokens starting with the specified token position have the specified tags given the complete sequence of input tokens.

Specified by:
logProbability in class TagLattice<E>
Parameters:
tokenFrom - Starting position of sequence.
tags - Tag identifiers for sequence.
Returns:
Log probability that sequence starting at the specified position has the specified tags.
Throws:
IllegalArgumentException - If the token is out of range or the token plus the length of the tag sequence is out of range of tokens, or if any of the tags is not a known identifier.

logForward

public double logForward(int token,
                         int tag)
Description copied from class: TagLattice
Return the log of the forward probability of the specified tag at the specified position. The forward probability is the sum of the joint probabilities of all sequences from the initial token to the specified token ending with the specified tag.

Specified by:
logForward in class TagLattice<E>
Parameters:
token - Token position.
tag - Tag identifier.
Returns:
Log forward probability specified token has specified tag.

logBackward

public double logBackward(int token,
                          int tag)
Description copied from class: TagLattice
Returns the log of the backward probability to the specified token and tag. The backward probability is the sum of the joint probabilities of all sequences starting from the specified token and specified tag and going to the end of the list of tokens.

Specified by:
logBackward in class TagLattice<E>
Parameters:
token - Input token position.
tag - Tag identifier.

logTransition

public double logTransition(int tokenFrom,
                            int tagFrom,
                            int tagTo)
Description copied from class: TagLattice
Returns the log of the transition probability from the specified input token position with the specified previous tag to the specified target tag.

Specified by:
logTransition in class TagLattice<E>
Parameters:
tokenFrom - Token position from which the transition is made.
tagFrom - Identifier for the previous tag from which the transition is made.
tagTo - Tag identifier for the target tag to which the the transition is made.
Returns:
Log probability of the transition.

logZ

public double logZ()
Return the log of the normalizing constant for the lattice. Its value is the log of the marginal probability of the input tokens. By the additive law of probability, this is equivalent to the sum of the probabilities of all possible analyses for the input sequence

Specified by:
logZ in class TagLattice<E>
Returns:
The normalizing constant.

toString

public String toString()
Return a string-based representation of this tag lattice. All of the information in the string is available programatically through methods.

Overrides:
toString in class Object
Returns:
String representation of this lattice.