edu.northwestern.at.morphadorner.corpuslinguistics.postagger

## Class Viterbi

- java.lang.Object
- - edu.northwestern.at.morphadorner.corpuslinguistics.postagger.Viterbi

-     public class Viterbi
      extends java.lang.Object

  Viterbi algorithm.

  The Viterbi trellis is a (# of words) x (# of part-of-speech-tags) matrix containing transition probability states from one word/tag to the next for each tag. Because this is a very sparse matrix, we use a HashMap2D to hold the probability values. In addition, we use another HashMap2D to hold the back trace tags. This allows use to produce the optimal (most probable) path from the last tag in a sentence back to the first.

  To improve performance, we define a beam width which allows us to eliminate trellis states which are highly unlikely to be part of the optimal tag path. The default beam width s 1000 which appears to work well in practice.

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected int` | `beamSearchRejections` Count of tags rejected by beam search.
    `protected double` | `beamWidth` Beam width for beam search.
    `protected Logger` | `logger` Logger used for output.
    `protected Map2D<java.lang.Integer,java.lang.String,java.lang.String>` | `tracebackTags` Viterbi traceback for tags.
    `protected Map2D<java.lang.Integer,java.lang.String,Probability>` | `trellis` Viterbi probability trellis.

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Viterbi()` Create Viterbi object.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `double` | `beamWidth()` Get the beam width.
    `void` | `beamWidth(double beamWidth)` Set the beam width.
    `int` | `getBeamSearchRejections()` Return number of entries rejected by beam search.
    `Logger` | `getLogger()` Get the logger.
    `Probability` | `getScore(int index, java.lang.String tag)` Get probability value for a specified word index and tag.
    `java.lang.String` | `getTracebackTag(int index, java.lang.String tag)` Get traceback tag for a specified tag and word index.
    `java.util.List<java.lang.String>` | `optimalTags(int nWords, java.util.List<java.lang.String> tags)` Get optimal set of tags via backtracking.
    `protected java.util.List<java.lang.String>` | `pruneTags(int wordIndex, java.util.List<java.lang.String> tags, Probability bestScore)` Prune tags using beam search.
    `void` | `reset()` Reset viterbi to clean state.
    `void` | `setLogger(Logger logger)` Set the logger.
    `void` | `setScore(int index, java.lang.String tag, java.lang.String tracebackTag, Probability score)` Store Viterbi score and traceback tag for a specified word index.
    `java.util.List<java.lang.String>` | `updateScore(int wordIndex, Probability[] lexicalProbs, Map2D contextualProbs, java.util.List<java.lang.String> tags, java.util.List<java.lang.String> prevTags)` Perform Viterbi scoring for bigram.
    `java.util.List<java.lang.String>` | `updateScore(int wordIndex, Probability[] lexicalProbs, Map3D contextualProbs, java.util.List<java.lang.String> tags, java.util.List<java.lang.String> prevTags, java.util.List<java.lang.String> prevPrevTags)` Perform Viterbi scoring for trigram.

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### trellis

          protected Map2D<java.lang.Integer,java.lang.String,Probability> trellis

      Viterbi probability trellis.

    - #### tracebackTags

          protected Map2D<java.lang.Integer,java.lang.String,java.lang.String> tracebackTags

      Viterbi traceback for tags.

    - #### beamWidth

          protected double beamWidth

      Beam width for beam search.

    - #### beamSearchRejections

          protected int beamSearchRejections

      Count of tags rejected by beam search.

    - #### logger

          protected Logger logger

      Logger used for output.

  - ### Constructor Detail

    - #### Viterbi

          public Viterbi()

      Create Viterbi object.

  - ### Method Detail

    - #### reset

          public void reset()

      Reset viterbi to clean state.

    - #### getScore

          public Probability getScore(int index,
                             java.lang.String tag)

      Get probability value for a specified word index and tag.
      Parameters:
        `index` - Word index.
        `tag` - Part of speech tag.
      Returns:
        Probability. If (index,tag) not found, returns 0.

    - #### getTracebackTag

          public java.lang.String getTracebackTag(int index,
                                         java.lang.String tag)

      Get traceback tag for a specified tag and word index.
      Parameters:
        `index` - Word index.
        `tag` - Part of speech tag.
      Returns:
        Part of speech tag. Returns "*" if (index,tag) not found, which should never happen, unless the part of speech guesser fails to return any parts of speech for a word (which should also never happen).

    - #### setScore

          public void setScore(int index,
                      java.lang.String tag,
                      java.lang.String tracebackTag,
                      Probability score)

      Store Viterbi score and traceback tag for a specified word index.
      Parameters:
        `index` - Word index.
        `tag` - Part of speech tag.
        `tracebackTag` - Traceback tag to store.
        `score` - Score to store.

    - #### updateScore

          public java.util.List<java.lang.String> updateScore(int wordIndex,
                                                     Probability[] lexicalProbs,
                                                     Map2D contextualProbs,
                                                     java.util.List<java.lang.String> tags,
                                                     java.util.List<java.lang.String> prevTags)

      Perform Viterbi scoring for bigram.
      Parameters:
        `wordIndex` - Word index for current word.
        `lexicalProbs` - Array of lexical probabilities. Entries match corresponding tags in "tags" parameter.
        `contextualProbs` - HashMap2D mapping words and tags to contextual probabilities.
        `tags` - Possible tags for current word.
        `prevTags` - Possible tags for previous word.
      Returns:
        Tags passing beam search criterion.

    - #### updateScore

          public java.util.List<java.lang.String> updateScore(int wordIndex,
                                                     Probability[] lexicalProbs,
                                                     Map3D contextualProbs,
                                                     java.util.List<java.lang.String> tags,
                                                     java.util.List<java.lang.String> prevTags,
                                                     java.util.List<java.lang.String> prevPrevTags)

      Perform Viterbi scoring for trigram.
      Parameters:
        `wordIndex` - Word index for current word.
        `lexicalProbs` - Array of lexical probabilities. Entries match corresponding tags in "tags" parameter.
        `contextualProbs` - HashMap3D mapping words and tags to contextual probabilities.
        `tags` - Possible tags for current word.
        `prevTags` - Possible tags for previous word.
        `prevPrevTags` - Possible tags for previous word of previous word.
      Returns:
        Tags passing beam search criterion.

    - #### pruneTags

          protected java.util.List<java.lang.String> pruneTags(int wordIndex,
                                                   java.util.List<java.lang.String> tags,
                                                   Probability bestScore)

      Prune tags using beam search.
      Parameters:
        `wordIndex` - The word index.
        `tags` - The tags to prune.
        `bestScore` - The best score for this word and set of tags.
      Returns:
        The pruned list of tags.

        Compares the ratio of the best score scross all the tags to each individual tag's score. Tags with a ratio larger than the beam width are removed from further consideration in succeeding states.

    - #### optimalTags

          public java.util.List<java.lang.String> optimalTags(int nWords,
                                                     java.util.List<java.lang.String> tags)

      Get optimal set of tags via backtracking.
      Parameters:
        `nWords` - Number of words.
        `tags` - Final state tags.
      Returns:
        Optimal list of tags.

    - #### getBeamSearchRejections

          public int getBeamSearchRejections()

      Return number of entries rejected by beam search.
      Returns:
        Number of entries rejected by beam search.

    - #### beamWidth

          public double beamWidth()

      Get the beam width.
      Returns:
        The beam width.

    - #### beamWidth

          public void beamWidth(double beamWidth)

      Set the beam width.
      Parameters:
        `beamWidth` - The beam width.

    - #### getLogger

          public Logger getLogger()

      Get the logger.
      Returns:
        The logger.

    - #### setLogger

          public void setLogger(Logger logger)

      Set the logger.
      Parameters:
        `logger` - The logger.