Parsing Engine

danbikel.parser
Class EMChart

java.lang.Object
  extended bydanbikel.parser.Chart
      extended bydanbikel.parser.CKYChart
          extended bydanbikel.parser.EMChart
All Implemented Interfaces:
Serializable

public class EMChart
extends CKYChart

Implementation of a chart for performing constrained CKY parsing so as to perform the E-step of the Inside-Outside algorithm.

See Also:
Serialized Form

Nested Class Summary
protected static class EMChart.Entry
          Contains all information and items covering a particular span.
 
Field Summary
 
Fields inherited from class danbikel.parser.Chart
cellLimit, chart, debugNumItemsGenerated, debugNumPrunedItems, itemPool, numPrePruned, numPruned, pruneFact, pruning, relax, size, totalItems, totalItemsGenerated
 
Constructor Summary
EMChart()
          Constructs a new chart with the default chart size.
EMChart(int size)
          Constructs a new chart with the specified chart size.
 
Method Summary
 boolean add(int start, int end, EMItem item)
          Adds this item that has no antecedents to the chart.
 boolean add(int start, int end, EMItem item, EMItem ante1, EMItem ante2, TrainerEvent[] events, double[] probs)
          Adds this item to the chart, recording its antecedents and the events and their probabilities that allowed this item (consequent) to be produced.
 boolean add(int start, int end, EMItem item, EMItem ante1, EMItem ante2, TrainerEvent event, double prob)
          Adds this item to the chart, recording its antecedents and the events and their probabilities that allowed this item (consequent) to be produced.
 void clear()
          Checks every map of the chart covering a span less than or equal to size and clears it; if a chart entry is null, then a new map is created.
 void doPruning()
          This method has been overloaded so that it simply throws an UnsupportedOperationException, since pruning is inappropriate when performing the E-step of the Inside-Outside algorithm.
 EMItem getNewEMItem()
          Returns a new EMItem.
 int numUnaryLevels(int start, int end)
          Returns the number of unary levels for the chart entry at the specified span.
protected  boolean outsideBeam(Item item, double topProb)
          Returns whether the specified chart item is outside the beam given the specified top log prob.
 void setSize(int size)
          Ensures that the size of the chart is at least as large as the specified size.
protected  void setUpItemPool()
          Sets up the item object pools.
protected  boolean toPrune(int start, int end, Item item)
          Returns true if the specified chart item should not be added to the specified set of items because its probability is not within Chart.pruneFact of the highest-ranked item.
 int[] unaryLevelCounts(int start, int end)
          Returns an array of integers containing the number of chart items at each of the unary levels of the specified span.
 
Methods inherited from class danbikel.parser.CKYChart
cellLimitShouldApplyTo, clearNonPreterminals, getNewItem, reclaimItemCollection
 
Methods inherited from class danbikel.parser.Chart
add, dontDoPruning, dontRelax, get, getTopItem, getTopLogProb, numItems, postParseCleanup, prune, reclaimItem, reclaimItemsInChart, relax, resetTopLogProb, setPruneFactor, setSizeAndClear
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

EMChart

public EMChart()
Constructs a new chart with the default chart size.


EMChart

public EMChart(int size)
Constructs a new chart with the specified chart size.

Parameters:
size - the initial size of this chart
Method Detail

setSize

public void setSize(int size)
Ensures that the size of the chart is at least as large as the specified size.

Overrides:
setSize in class Chart
Parameters:
size - the size to be set for this chart

clear

public void clear()
Checks every map of the chart covering a span less than or equal to size and clears it; if a chart entry is null, then a new map is created.

Overrides:
clear in class Chart

outsideBeam

protected boolean outsideBeam(Item item,
                              double topProb)
Description copied from class: Chart
Returns whether the specified chart item is outside the beam given the specified top log prob.

Overrides:
outsideBeam in class CKYChart

toPrune

protected boolean toPrune(int start,
                          int end,
                          Item item)
Description copied from class: Chart
Returns true if the specified chart item should not be added to the specified set of items because its probability is not within Chart.pruneFact of the highest-ranked item. This method is guaranteed to be called by Chart.add(int,int,Item) when a sorted set of chart items already exists (and hence contains at least one chart item).

Overrides:
toPrune in class Chart
Parameters:
start - the start of the span for the specified item
end - the end of the span for the specified item
item - the item being added to items
Returns:
true if the specified chart item should not be added to the set of items covering the specified span

doPruning

public void doPruning()
This method has been overloaded so that it simply throws an UnsupportedOperationException, since pruning is inappropriate when performing the E-step of the Inside-Outside algorithm.

Overrides:
doPruning in class Chart

add

public boolean add(int start,
                   int end,
                   EMItem item)
Adds this item that has no antecedents to the chart.

Parameters:
start - the start of the span of this item
end - the end of the span of this item
item - the item to be added
Returns:
whether the specified item was added to the chart (false if an existing, equivalent item already exists in chart and the specified item's inside probability is added to the existing item's inside probability)

add

public boolean add(int start,
                   int end,
                   EMItem item,
                   EMItem ante1,
                   EMItem ante2,
                   TrainerEvent event,
                   double prob)
Adds this item to the chart, recording its antecedents and the events and their probabilities that allowed this item (consequent) to be produced.

Parameters:
start - the start of the span of the item to be added
end - the end of the span of the item to be added
item - the item to be added
ante1 - the first of two possible antecedents of the item to be added
ante2 - the second of two possible antecedents of the item to be added; if the item has only one antecedent, the value of this parameter should be null
event - the single event that allowed this item (consequent) to be produced from its antecedent(s)
prob - the probability of the specified event
Returns:
whether the specified item was added to the chart (false if an existing, equivalent item already exists in chart and the specified item's inside probability is added to the existing item's inside probability)

add

public boolean add(int start,
                   int end,
                   EMItem item,
                   EMItem ante1,
                   EMItem ante2,
                   TrainerEvent[] events,
                   double[] probs)
Adds this item to the chart, recording its antecedents and the events and their probabilities that allowed this item (consequent) to be produced.

Parameters:
start - the start of the span of the item to be added
end - the end of the span of the item to be added
item - the item to be added
ante1 - the first of two possible antecedents of the item to be added
ante2 - the second of two possible antecedents of the item to be added; if the item has only one antecedent, the value of this parameter should be null
events - the events that allowed this item (consequent) to be produced from its antecedent(s)
probs - an array of probabilities of the same size and coindexed with the specified array of events, where each probability is that for its coindexed event
Returns:
whether the specified item was added to the chart (false if an existing, equivalent item already exists in chart and the specified item's inside probability is added to the existing item's inside probability)

setUpItemPool

protected void setUpItemPool()
Description copied from class: Chart
Sets up the item object pools. This allows subclasses to specify the type of item to be held in the object pool.

Overrides:
setUpItemPool in class CKYChart

getNewEMItem

public EMItem getNewEMItem()
Returns a new EMItem.

Returns:
a new EMItem

numUnaryLevels

public int numUnaryLevels(int start,
                          int end)
Returns the number of unary levels for the chart entry at the specified span.

Parameters:
start - the start of the span for which to retrieve the number of unary levels
end - the end of the span for which to retrieve the number of unary levels
Returns:
the number of unary levels for the chart entry at the specified span.

unaryLevelCounts

public int[] unaryLevelCounts(int start,
                              int end)
Returns an array of integers containing the number of chart items at each of the unary levels of the specified span. The size of the array is the integer returne by numUnaryLevels(int, int) for the same span.

Parameters:
start - the start of the span for which to retrieve the unary level counts
end - the start of the span for which to retrieve the unary level counts
Returns:
an array of integers containing the number of chart items at each of the unary levels of the specified span

Parsing Engine

Author: Dan Bikel.