\documentclass[12pt]{article}

\input{cps130}

\begin{document}

\title{Dynamic Programming: Segmentation (21)}
\author{Michael L. Littman}
\date{December 1st, 1998}

\maketitle 

\section{DYNAMIC PROGRAMMING}

\subsection{End-Game Plan}

\ni This week, DP examples (segmentation, LCS).

\ni Next week, NP completeness (theory, practice).


\subsection{What?}

\ni The term ``dynamic programming'' is incredibly misleading.

\ni It's one of the main techniques I use in my work, but when I tell
people that's what I do, a substantial percentage think it has
something to do with self-modifying code.

\ni As cool as that is, it's not what I do.

\ni Dynamic programming is neither especially dynamic nor especially
program related.

\ni The term was coined (I think) by Richard Bellman in the late 50s
to describe an algorithm-design {\em technique\/} in which an
optimization problem is solved by filling in values in a table.

\ni Pretty mundane, eh?

\ans{Yes.}

\ni Various dynamic-programming algorithms have a similar flavor, but
there is no single algorithm that gives you the whole story.  Instead,
it is usually taught by example.

\subsection{DP Examples}

\ni 

\ul

\li minimum-cost matrix-chain product: given a sequence of matrices to
multiply together, what order should the intermediate products be
computed to minimize the running time?  (Described in book.)

\li longest common subsequence: given two lists, find the largest
subset of each (in order) that is the same (next time).

\li longest increasing subsequence: given a list of numbers, find the
largest subset (in order) that is sorted (HW).

% Used in the UNIX {\tt diff} command.)

\li edit distance: given two words, how many keystrokes would it take
to turn one into the other?  (Useful for spelling correction and even
historical linguistics, HW.)

\li minimum-cost triangulation of a polygon (in book)

\li TSP approximation in the plane, bitonic TSP (in book).

\li shortest paths (last time, others in book).

\li searching along a 1-d road

\li segmentation (today)

\li speech recognition: given a sequence of acoustic signals and a
probabilistic model of phonemes, find the most likely phoneme
(Viterbi, hidden Markov models).

\li dynamic time warping: given a sequence of acoustic samples and a
template model of a phoneme, find the minimum way to stretch and
squeeze the sequence to fit the template.

\li text alignment: given a sequence of sentences in English and their
French translations and a probabilistic model relating the two
languages, find the most likely way the two sequences are lined up.

\li stochastic parsing: given a sentence and a stochastic grammar,
find the most likely parse tree for the sentence.

\li part-of-speech tagging: given a sentence and a probabilistic model
of language, find the most likely part-of-speech tags for the words
in the sentence.

\el

\ni Sequence and language related things are quite popular.

\section{SEGMENTATION}

\subsection{Segmentation}

\ni The segmentation problem is one of taking a sequence and breaking
it up into useful pieces.

$$\mbox{\tt bothearthandsaturnspin.}$$

\ni Related problems:

\ul

\li Break a string of letters into words.

\li Break a string of words into sentences.

\li Break a string of Chinese characters into words.

\li Break a sequence of phonemes into words.

\li Find the most likely answer to a long crossword puzzle answer
	given probabilities on the crossing letters.

\el

\ni \href{http://cgi.cs.duke.edu/~keim/crossword/segmenter.cgi}{Greg
Keim's Segmenter}

\subsection{Choices}

\ni Given a sequence of $n$ characters, we need to decide where to put
the spaces so that we get a sequence of valid words out.

\ni How many different ways can we insert spaces?

\ans{There's $n-1$ places a space can be, and each can either have a
space or not... so $2^{n-1}$.}

\ni On the other hand, how many possible words are in there?

\ans{Each word must begin at some position and end at some later
position, so it's something like $n(n-1)/2$.}

\ni If there are multiple ways to do this, which should we prefer?

\ni We'll work up to a probabilistic model: choose the segmentation
that gives us the most likely sequence of words.

\subsection{Count in 1M Tokens (WSJ)}

\begin{tabular}{|lr|lr|lr|lr|lr|lr|}
\hline
b & 304 & bo & 2 & && both & 631 &&&&\\
o & 88 &&&&&&&&&&\\
t & 4655 & th & 140 & the & 65779 &&&&&&\\
h & 151 & he & 4602 && & hear & 54 & heart & 68 &&\\
e & 143 && & ear & 7 && & earth & 38 &&\\
a & 27857 && & art & 121 &&&&&&\\
r & 207 &&&&&&&&&&\\
t & 4655 & th & 140 && & than & 2264 &&&&\\
h & 151 &&&&& hand & 154 & hands & 107 &&\\
a & 27857 & an & 4413 & and & 22490 &&&&&&\\
n & 311 & nd & 6 &&&& &&&&\\
d & 479 & ds & 1 &&&&&&&&\\
s & 15889 & sa & 6 & sat & 29&&&& & saturn & 1 \\
a & 27857 & at & 6475 &&&& &&&&\\
t & 4655 & tu & 1 &&& turn & 167 & turns & 47 &&\\
u & 2551 &&&&&&&&&&\\
r & 207 &&&&&&&&&&\\
n & 311 &&&&&&&&&&\\
s & 15889 & sp & 2 && & spin & 23 &&&&\\
p & 464 & pi & 1 & pin & 7 &&&&&&\\
i & 1666 & in & 23251 &&&&&&&&\\
n & 311&&&&&&&&&& \\
. & 100000&&&&&&&&&& \\
\hline
\end{tabular}

\subsection{Algorithmic Ideas}

\ni How would you attack this?

\ul

\li greedy by common words

\li greedy by length

\li greedy alphabetically

\li path problem

\li transformation rules

\li probabilistic model

\el

\subsection{Simple Path Example}

\ni Want to go from beginning of sentence to the end using only valid
words.

\ni For now, let's say that valid words are 3 or more letters:

\ul

\li both, the, hear, heart, ear, earth, art, than, hand, hands, and,
sat, saturn, turn, turns, spin, pin

\el

\ni What kind of graph do we get?  What is true of the order of the
nodes?

\ans{DAG.  Path goes left to right.}

\ni How find a path through?

\ans{DFS.}

\ni Use a table to decrease our overhead.


\subsection{Problems with Path Approach}

\ni Although fast and often sufficient, there are problems with the
path approach:

\ul

\li Rare words: Approach will refuse to find a path with an unknown
word, even if evidence is strong: ``{\tt theyattenddookuniversity.}''
(\href{http://cgi.cs.duke.edu/~keim/crossword/segmenter.cgi}{Greg
Keim's Segmenter}).

\li Competing interpretations: Approach gives no guidance if two
sequence of words are possible, even if one is much more probable.

\el

\pagebreak

\subsection{Probabilistic Language Models}

\ni A popular idea in computational linguistics is to create a
probabilistic model of language.  Such a model assigns a probability
to every sentence in English in such a way that more likely sentences
(in some sense) get higher probability.  If you are unsure between two
possible sentences, pick the higher probability one.

\ni {\em Comment\/}: A ``perfect'' language model is only attainable
with true intelligence.  However, approximate language models are
often easy to create and good enough for many applications.

\ni Some models:

\ul

\li unigram: words generated one at a time, drawn from a fixed distribution.

\li bigram: probability of word depends on previous word.

\li tag bigram: probability of part of speech depends on previous part
of speech, probability of word depends on part of speech.

\li maximum entropy: lots of other random features can contribute.

\li stochastic context free: words generated by a context-free grammar
augmented with probabilitistic rewrite rules.

\el

\ni We'll use unigrams.


\subsection{Unigram Idea}

\ni Imagine that a sentence is produced by choosing a random word, or
``.'' from a particular distribution.

\ni Continue generating random words until a period is chosen
(probability 0.1).

\ni Picture.  Expected sentence length?  Mostly likely sentence?
Total probability over all sentences?

\ans{Expected length is $1/(1-p)$ for $p$ the probability of getting a
period.  Most likely sentence is just ``.''.  Total probability is
$1$.}


\subsection{Unigram Algorithms}

\ni To specify a unigram language model, we need a big dictionary that
maps words to probabilities (good data structure?).

\ans{I'm thinking hash table.}

\ni Given a unigram language model, what might we want to do?

\ul

\li Generate random sentences respecting the probabilities
in the model (interesting to try to solve efficiently).

\ans{Pick random words biased by the probabilities (binary search is
useful here).}

%  If we end up with fewer than $n$ letters, append
% another word.  If we go over, through everything away and start
% again.  There's probably a more efficient way of doing this.}
 
\li Given a sentence, what is its probability?

\ans{Just multiply the unigram probabilities together, described below.}

\li Given a sequence of letters, what is the most likely sentence
consistent with the sequence?

\ans{DP algorithm described below.}

\li Given a sequence of letters, what is the total probability of all
sentences consistent with the sequence?

\ans{DP algorithm, not described below.}

\el

\subsection{Probability of a Segmentation}

\ni Example: 
\begin{tabular}{cccccccc}
bo & the & art & hands & a & turns & pin & .\\
2 & 65779&121&    107& 27857&47&  7 & 100000
\end{tabular}

\ni Probability: $1561049421506297800000/1M^{8} = 1.56 \times 10^{-27}$.

% 1.561049

\ni This is a million times less likely that the best sentence.

% \pagebreak

\subsection{Maximum Probability Segmentation}

\ni Of all possible segmentations for a sequence of letters, we want
the one with the highest probability.

\ni Proceed like in the path example (in fact, this is a path problem,
if phrased correctly...).

\ni Start from the end... go up to ``t''.

\subsection{Final Table}

\begin{tabular}{|r|c|c|c|}
\hline
$i$&$s[i]$&$p[i]$&$q[i]$ \\
\hline
1&b & 1.24e-21& ``both''\\
2&o & 8.02e-25 & ``o''\\
3&t & 9.11e-21 & ``the''\\
4&h & 7.79e-20 & ``heart''\\
5&e & 1.97e-18 & ``earth''\\
6&a & 1.39e-19 & ``art''\\
7&r & 5.16e-22 & ``r''\\
8&t & 2.49e-18 & ``than''\\
9&h & 1.14e-15 & ``hands''\\
10&a & 5.17e-14 & ``and''\\
11&n & 1.38e-17 & ``nd''\\
12&d & 1.10e-15 & ``d''\\
13&s & 2.30e-12 & ``saturn'' \\
14&a & 1.07e-11 & ``at''\\
15&t & 3.84e-10 & ``turn''\\
16&u & 3.78e-16 & ``u''\\
17&r & 1.48e-13 & ``r''\\
18&n & 7.15e-10 & ``n''\\
19&s & 2.30e-06 & ``spin''\\
20&p & 1.08e-06 & ``p'' \\
21&i & 2.33e-03 & ``in'' \\
22&n & 3.11e-05 & ``n'' \\
23&. & 1.00e-01 & \\
\hline
\end{tabular}

% b & 1.24031e-21& ``both''\\
% o & 8.018951e-25 & ``o''\\
% t & 9.112444e-21 & ``the''\\
% h & 7.785225e-20 & ``heart''\\
% e & 1.965626e-18 & ``earth''\\
% a & 1.385312e-19 & ``art''\\
% r & 5.163095e-22 & ``r''\\
% t & 2.494249e-18 & ``than''\\
% h & 1.144886e-15 & ``hands''\\
% a & 5.1727e-14 & ``and''\\
% n & 1.38e-17 & ``nd''\\
% d & 1.1017e-15 & ``d''\\
% s & 2.3e-12 & ``saturn'' \\
% a & 1.069987e-11 & ``at''\\
% t & 3.841e-10 & ``turn''\\
% u & 3.777192e-16 & ``u''\\
% r & 1.480671e-13 & ``r''\\
% n & 7.153e-10 & ``n''\\
% s & 2.3e-06 & ``spin''\\
% p & 1.078846e-06 & ``p'' \\
% i & 0.0023251 & ``in'' \\
% n & 3.11e-05 & ``n'' \\
% . & .1 & \\


\subsection{Algorithm}

\ni Given a string of letters $s$ and a dictionary $D$ with (unigram)
probabilities, find the probability of the most likely sequence of
words.

\begin{algorithm}{Maxprob}{s, D}
 n \= |s| \\
 p[n+1] \= 1.0 \\
 \begin{FOR}{i \= n \TO 1}
  p[i] \= 0.0 \\
  \begin{FOR}{j \= i \TO n}
   w \= s[i..j] \\
   \begin{IF}{D[w] \cdot p[i-|w|] > p[i]}
    p[i] = D[w] \cdot p[i-|w|] \\
    q[i] = w
   \end{IF}
  \end{FOR}
 \end{FOR} \\
 \RETURN p[1]
\end{algorithm}

\subsection{Discussion}

\ni Running time: $O(n^2)$.

\ni $p[i]$ is the probability of the most likely sequence of words in
the string $s[i..n]$.

\ni $q[i]$ is the first word in that sequence.

\ni HW: Modify {\sc Maxprob} to print the most likely sequence of
words.  Give the running time for this operation.

% \ni EC: Modify {\sc Maxprob} to return the probability of {\em all\/} word
% sequences consistent with $s$.


\subsection{Correctness}

\ni Write: $g: s$ to stand for all elements of the set of
segmentations of a string $s$.

\ni $M(s)$ is the maximum probability of a segmentation of string $s$.

\ul
\li $M(s) = \max_{g: s} \prod_k D[g[k]]$
\li $= \max_{i=1}^{|s|} \max_{g: s[(i+1)..n]} D[s[1..i]] \prod_k D[g[k]]$
\li $= \max_{i=1}^{|s|} D[s[1..i]] \max_{g: s[(i+1)..n]} \prod_k D[g[k]]$
\li $= \max_{i=1}^{|s|} D[s[1..i]] M(s[(i+1)..n])$
\el

\ni Can implement this directly to get a correct but exponential-time
algorithm.  Need to {\em reuse\/} results instead of recomputing over
and over.

\ni Recurrence: $T(1) = 1$, $T(n) = n + \sum_{i = 1}^{n-1} T(i)$.  
% HW: solve it.


\subsection{Algorithmic Design}

\ul

\li Problem: word segmentation
\li Step 0 (formalize): unigram model, find maximum probability segmentation
\li Step 1 (devise algorithm): table-based approach (DP)
\li Step 2 (correctness): follows from equation for probability
\li Step 3 (time): time per cell times number of cells ($O(n^2)$)
\li refine: better formal model, better data structure, worse formal model!
\el


\end{document}
