Motivation
A sequence of words carries more information than its word counts. Constituency describes how a sentence can be assembled from smaller phrases; hidden-state models describe how unobserved categories can generate observed tokens. Both approaches replace unrestricted interpretation by a precise mathematical task. A parser asks which derivations a grammar permits. An HMM computes probabilities or a most probable state path under specified parameters. Neither answer is automatically a complete account of meaning.
Ambiguity makes this distinction important. One token sequence can have several parse trees, and many state paths can explain the same observations. A correct algorithm must decide whether to retain every possibility, sum their probabilities, or choose a maximum. Interchanging these operations changes the question. Dynamic programming is useful because many candidate explanations share the same subproblems.
This unit presents finite models that expose those shared calculations. It gives full correctness arguments for CKY in a restricted grammar form and for HMM forward and Viterbi inference.
Definitions
Definition 7.1.1
(Context-free grammar, parse tree and ambiguity)
A context-free grammar consists of finite nonterminals , terminal vocabulary , start symbol , and production rules. A parse tree's internal nodes expand according to productions; its terminal leaves, read left to right, give the token sequence. A grammar is ambiguous if some sentence of its language has two distinct parse trees rooted at the start symbol . Ambiguity concerns the grammar's structural explanations, not just whether a sequence is accepted.
Definition 7.1.2
(Chomsky normal form and the CKY chart)
For CKY we assume Chomsky normal form without empty or unit productions: every rule is or , with nonterminals and terminal . We parse a nonempty token sequence . This restriction excludes empty sentences; handling them or unary chains requires an explicit extension. Let contain the nonterminals deriving exactly tokens . Indices include both endpoints.
Definition 7.1.3
(Hidden Markov model, likelihood and Viterbi decoding)
An HMM has a finite hidden-state set , initial probabilities , transition probabilities and emission probabilities over a finite vocabulary. Every row of and sums to one, and . Given a state path , transitions are first-order Markov and emissions are conditionally independent given the states. Its joint probability with observations is
These conditional-independence assumptions define the model; they are not consequences of the dynamic program. The observation likelihood sums this joint probability over all hidden paths. Viterbi decoding instead maximizes the joint probability over paths. A maximum-posterior path is the same maximizer when the observation likelihood is positive, since every candidate shares that denominator.
Theorem/Proposition
Theorem 7.1.4
(CKY recognition and parse reconstruction)
Initialize with all having . For increasing span lengths, put in whenever some split and rule have , . Then exactly when derives that span. The sentence belongs to the grammar exactly when . Storing every witnessing rule and split as backpointers represents all parse trees in a finite packed chart.
Theorem 7.1.5
(Forward sums and Viterbi maxima)
For a nonempty observation sequence, define forward values and Viterbi values . For ,
Then and is the largest joint probability among paths of length ending at . Thus likelihood is and the best-path joint value is . Maximizing predecessor backpointers reconstruct a best path; ties can be retained if all maximizing paths are wanted.
Proposition 7.1.6
(Maximum-likelihood rows from labeled counts)
Fix a state and let be the transition counts out of , with total . Among all probability rows , the function (with ) has the unique maximizer . Emission rows and the initial distribution are maximized in the same way from their own counts.
Proof sketch or proof idea
Proof
(Induction on span length)
For CKY, induct on span length. A one-token derivation in this grammar must use a lexical production, giving the initialization. For a longer span, a parse tree's root must use some binary production . Its left subtree covers an initial nonempty portion ending at a unique split , and its right subtree covers the remaining portion. By induction both children appear in their chart cells, so the recurrence inserts . Conversely, every insertion has two valid smaller derivations, which can be joined under the witnessing rule. This proves completeness and soundness together. Following stored witnesses reconstructs trees; storing only membership recognizes the sentence but loses structural explanations.
Proof X-ray
Where the normal form and the span order are used
The normal form is used twice. A length-one span can be derived only by a lexical rule, since no empty or unit rule exists, and a longer span must be derived by a binary rule whose two children are each nonempty and therefore strictly shorter. That strict shrinking is what makes induction on span length legitimate: every cell is computed from cells of smaller length only.
The key move is that the split point is part of the witness. Different splits of the same root rule give different trees, so the recurrence ranges over all and, for the existence question, a single successful split suffices. The argument closes in two directions: a derivation produces a chart entry by induction, and a chart entry carries two smaller derivations that are joined.
A unit rule would break the order, since the cell would then depend on itself, and a cycle such as , gives infinitely many trees for one span. An empty production would allow a child to cover zero tokens. Both need an explicit extension, as noted above.
With a direct loop over binary rules, split points and spans, CKY takes time and membership space. Backpointer storage can be larger, and explicitly listing all trees may take exponential output size. A polynomial recognition algorithm does not imply a polynomial number of parses.
Proof
(Partitioning paths by the previous state)
For forward inference, partition all paths ending at according to their previous state . These cases are disjoint. The HMM factorization multiplies each previous prefix probability by transition and emission , and addition combines the cases. This proves the recurrence by induction on . Summing final states accounts for all paths exactly once.
Proof
(Replacing a prefix by a better prefix)
For Viterbi, fix the final state and the preceding state . Every such path shares the same last transition and emission factor, which is nonnegative. Therefore the best prefix ending at can replace any weaker prefix without reducing the joint probability. Maximize over and then over final states. An argmax pointer records which optimal prefix achieved each entry, permitting a backwards reconstruction. The argument relies on the last factor depending only on the states and the current token; it cannot be applied unchanged to models with long-range dependencies.
Concept lensAlgorithmic
The same dependency graph answers two different questions
Forward and Viterbi pass messages along the same time-state graph. Multiplication extends a path in both. Addition totals mutually exclusive explanations; maximum selects one explanation. Replacing addition by maximum therefore changes likelihood into best-path probability. It does not merely speed up the same calculation.
Both recurrences use arithmetic for dense transitions. Forward likelihood can use two length- arrays; path reconstruction needs stored pointers or recomputation. Long products can underflow in floating-point arithmetic. Viterbi can use log probabilities, with zero represented by minus infinity. Forward sums need scaling or log-sum-exp, not simply a maximum of logarithms. These numerical changes must preserve the intended sum or maximum.
When hidden states are observed in a training corpus, parameter estimation is also explicit. Let count transitions from to over all separately delimited sequences, and count emissions of from state . The complete-data likelihood separates into multinomial factors, one for each row, so each row can be maximized on its own.
Proof
(Maximizing a multinomial row)
Write and let be any probability row. Terms with contribute zero to the objective, so only the set matters, and is needed on for a finite value. Then
using with equality only at . Equality throughout forces on and , so off . Hence is the unique maximizer, and zero-count entries receive zero at this unsmoothed optimum.
A row with no observations is unidentifiable by that likelihood and needs an additional choice, not division by zero. Hidden-state learning requires another procedure, such as posterior-weighted expected counts, and is not derived here.
Proof X-ray
How the constraint closes the multinomial argument
After dividing by , the gap between the two objectives becomes times a -weighted sum of , and is applied term by term. This is the only analytic input. It turns the bound into , and that quantity is at most precisely because is a probability row: the constraint, not calculus with multipliers, closes the argument. Zero-count entries drop out of the objective, so restricts the sum; any mass that places outside makes and the inequality strict. The equality case of then forces , which gives uniqueness.
Worked examples
Worked example 7.1.7
(A small grammar has two structural explanations)
Use rules and . For tokens aaa, all three length-one cells contain S. Both length-two cells contain S through their only split. The length-three cell has two witnesses: split after token one, giving , and split after token two, giving . Both parse trees are represented in the same membership entry. Counting derivations replaces set insertion by summing products of child counts, yielding two, rather than treating the two witnesses as one explanation.
Worked example 7.1.8
(Likelihood differs from the best-path value)
Use states R,D, initial probabilities , transition rows and , and emission probabilities for a of and b of . For observation ab, first-step values are . Forward gives second-step values and likelihood . Viterbi gives ; the best path is R,D with joint probability . Its posterior probability is , far from certainty even though it is the best individual explanation.
Worked example 7.1.9
(Learning from labeled sequences preserves boundaries)
Take one labeled state sequence R,R,D,D,R, with tokens a,a,b,b,a. Transition counts from R are one to R and one to D, while from D they are one to D and one to R. Both estimated transition rows are . All observed R emissions are a and D emissions are b, giving unsmoothed probabilities one and zero. The initial distribution from this single sequence puts all mass on R. Appending another independent sequence must contribute a new initial-state count, not an artificial transition from the old sequence's last state to the new sequence's first.
Common mistakes
Counterexample mode
A recognized sentence need not have a unique parse
The grammar accepts aaa but has the two bracketings above. A chart cell containing one symbol S records existence, not uniqueness. The repair is to retain witnesses or use a counting recurrence when ambiguity itself matters. A parser should not claim that recognition alone selects the intended meaning.
Common mistake
(Reading numbered HMM states as grammatical categories)
An HMM state label need not correspond to a human-interpretable grammatical category unless the model construction makes that connection. A state is an index in the model, and a name attached afterwards is an interpretation, not a property of the parameters.
Common mistake
(Maximizing each time step separately)
Maximizing each time's posterior state independently solves a different problem from maximizing one joint path. A sequence of individually preferred states can have an impossible transition. Dynamic programming preserves cross-time constraints that local choices can lose.
Common mistake
(Treating membership as probability, and ignoring tokenization)
Grammar membership and probability are likewise different. A rule set may permit several trees without assigning probabilities to them. Adding rule probabilities requires a properly specified probabilistic grammar and changes the objective. Tokenization is part of the model: unseen vocabulary, punctuation and multiword expressions cannot be handled by pretending they were already in the finite vocabulary. Smoothing may assign positive probability to unobserved events, but its assumptions must be stated separately from maximum likelihood.
Summary
CKY shares derivations by spans and proves recognition with an induction on tree structure. HMM inference shares path prefixes by time and final state; sums give likelihood while maxima give a best path. Labeled-sequence counts yield explicit multinomial estimates under the model, with important boundaries at zero counts and sequence endpoints. These methods provide exact answers to well-defined finite tasks while leaving semantic interpretation and richer language modeling open.
Exercises
Exercise 7.1.10
(For the grammar , count the parses of by considering its three possible root splits. Explain why the chart membership entry alone cannot store this count.)
Core
Solution(3)
- 1
Count the parses of shorter spans
Let be the number of parses of . Then , , and .
- 2
Sum over the three root splits
Key step
.
Because: A root rule splits the span after one, two or three tokens, and the two subtrees are chosen independently.
- 3
Compare with the membership entry
Membership records only that occurs in the cell, so all five derivations collapse to one symbol. Counts or packed backpointers preserve the additional information.
Exercise 7.1.11
(For the two-state example and the observation , list the four hidden-path joint probabilities and verify both the likelihood and the Viterbi answer.)
Core
Solution(3)
- 1
Compute the four joint probabilities
With initial , transition rows and , and emission probabilities , , , :
- 2
Verify the likelihood and the best path
The sum is and the maximum is , attained at . Summing the paths ending in gives and those ending in gives , reproducing the forward entries.
- 3
Interpret the two numbers
The likelihood is the total over all explanations, and the best path has posterior probability . A likelihood therefore cannot be reported as the probability of the single best explanation.
Exercise 7.1.12
(A labeled corpus has transition counts from state equal to . Find the unsmoothed maximum-likelihood row. What can be concluded for another state with transition counts ?)
Foundation
Solution(3)
- 1
Normalize the observed counts
The total is , so the maximum-likelihood row is .
- 2
Check the zero entry
A positive probability for the unobserved third transition would reduce the mass available to the observed transitions and lower the unsmoothed likelihood.
Because: Giving positive probability to an unobserved transition takes mass from the observed ones.
- 3
Treat the row with no observations
For the all-zero row the likelihood factor is constant over every probability row, so the data do not identify a unique estimate. A prior or smoothing policy can select one, but no particular row follows from these counts alone.
Exercise 7.1.13
(A two-state model has initial probabilities and identity transition matrix, and both states emit the single token with probability one. For the observation , compute the likelihood, the best-path joint probability and the number of maximizing paths. Explain what a tie-breaking pointer retains.)
Synthesis
Solution(3)
- 1
Find the positive paths
The paths and each have probability . The cross paths and need a transition of probability zero, so they have probability zero.
- 2
Compute the three quantities
The likelihood is , the best-path joint value is , and there are two maximizers.
- 3
Explain the pointer
A deterministic tie-breaking pointer returns one valid maximizing path and loses the other explanation unless ties are stored explicitly.