Dynamic Programming: Segmentation (21)
Michael L. Littman
December 1st, 1998
DYNAMIC PROGRAMMING
End-Game Plan
What?
DP Examples
SEGMENTATION
Segmentation
Choices
Count in 1M Tokens (WSJ)
Algorithmic Ideas
Simple Path Example
Problems with Path Approach
Probabilistic Language Models
Unigram Idea
Unigram Algorithms
Probability of a Segmentation
Maximum Probability Segmentation
Final Table
Algorithm
Discussion
Correctness
Algorithmic Design
Next:
DYNAMIC PROGRAMMING