Why attach probabilities to a grammar?
A grammar can license several analyses of the same sentence. The earlier CKY chart answers whether an analysis exists and can record its possible splits; it does not say how plausible each analysis is under a model. A probabilistic context-free grammar (PCFG) assigns a probability to each production and thereby weights complete parse trees. This gives a precise ranking or a total weight, not a guarantee that the preferred tree expresses the speaker's intended meaning.
We will compute two different quantities for the same sentence. The inside probability adds the weights of all its parses. The Viterbi probability is the weight of its single most probable parse. The first is useful for comparing the probability assigned to observed sentences; the second supplies one analysis. Replacing every sum by a maximum changes the question.
A finite model and its assumptions
Definition 32.1.1
(Binary probabilistic grammar and tree weight)
Let be a finite nonterminal set, a finite terminal vocabulary, a finite set of labeled productions, and the start symbol. A derivation tree records the identity of the production chosen at each node: distinct rule labels count as distinct derivations even when their written left and right sides coincide. Every production has form or , with and . Productions with the same left side have nonnegative probabilities summing to one. At each node labeled , choose a production according to these probabilities using an independent draw at each node, with the distribution determined by that node’s label. The probability, or weight, of a finite parse tree is the product of the probabilities of all productions used in it.
Local normalization alone does not ensure that generation eventually terminates. For example, with probability 1 never produces a terminal sentence. Assume in addition that the process starting from terminates almost surely; then its finite terminal trees form a probability distribution. Without this assumption, the finite chart still gives the unconditional probability of the specified finite sentence, but the probabilities of all finite sentences sum to less than one whenever nontermination has positive probability. A zero-weight production may be omitted.
Definition 32.1.2
(Inside and Viterbi values)
For a nonempty observed sentence , a nonterminal and , let be the sum of weights of all finite trees rooted at whose leaves are exactly , inclusive, and let be the largest weight of one such tree, or zero if there is none. The inside probability of the sentence is and its Viterbi probability is .
Write and for rule probabilities. The inside values satisfy
The first sum handles distinct labeled lexical rules with the same spelling if the grammar represents them separately. If trees are distinguished by node symbols and branching but not by duplicate production identities, combine the probabilities of identically written alternatives first; a single rule label with their summed probability then represents them. The probability assigned to the entire sentence is under the terminating model. We do not divide by sentence length or by the number of parses.
Why the recurrence is correct
Theorem 32.1.3
(Inside recurrence)
For a fixed nonempty sentence and the binary/lexical grammar above, the recurrence computes the sum of the weights of exactly its parse trees rooted at each . With a terminating start process, is the probability of generating that sentence.
Proof
(Induction on span length)
Use induction on span length. A one-token tree has exactly one lexical production at its root, so summing the applicable rule weights gives the base case. For a longer span the root must choose a binary production . Both children produce nonempty spans, so the left child ends at one uniquely determined split . Conversely, a rule, a split, a left tree and a right tree uniquely determine a parent tree. Different choices in this description represent distinct trees; none are omitted or counted twice.
By the induction hypothesis the child sums are correct. Multiplying them distributes over every pair of child trees, and multiplying by the root probability gives each resulting tree's product weight. Summing over rules and splits therefore gives exactly the desired total. For a fixed , a binary tree has leaves and binary nodes, so only finitely many labeled derivations occur; no interchange of infinite sums is needed.
Proof X-ray
Where independence enters
The proof uses three facts, each at one place. The bijection between a tree and the data (root rule, split, left tree, right tree) is the key move; it needs every production to be binary or lexical, so that a parent has exactly one split point. Distributivity then turns the product of two sums into a sum over all pairs of child trees. The generative model enters only in the statement that a tree weighs the product of its rule probabilities, which is justified by independent choices at separate nodes. A system in which a rule choice depends on the entire preceding sentence needs a different state or recurrence. The chart is exact for the stated model, not for every language model. If unary rules such as and were allowed, one span would have infinitely many trees and the induction on span length would no longer reach a base case.
Best tree versus total probability
The Viterbi values obey the same recurrence with every sum replaced by a maximum. The lexical base uses a maximum over matching rules, and the binary recurrence is
An empty maximum is zero.
Theorem 32.1.4
(Viterbi recurrence with backpointers)
For a fixed nonempty sentence, the recurrence above computes , the largest weight of a tree rooted at over (zero if there is none). If , a rule and a split that attain the maximum, followed recursively in the two children, reconstruct a tree of weight .
Proof
(A maximum of products of independent factors)
Use induction on span length. A one-token tree consists of one lexical production, so the best weight is the maximum of the matching rule probabilities. For a longer span every tree has a root rule , a split , a left tree over and a right tree over , and its weight is . For a fixed rule and split, and are chosen independently and all weights are nonnegative, so the maximum of is the product of the two maxima, which are and by the induction hypothesis. Maximizing over rules and splits gives the stated recurrence.
If the maximum is positive, a maximizing rule and split have and . By the induction hypothesis the children have best trees of those weights, and combining them under the root rule gives a tree of weight .
Concept lensStructural
One chart shape, different operations
Both charts have the shape . The inside chart uses and on nonnegative numbers; the Viterbi chart uses and . The proofs above differ only in why multiplication passes through : for sums and for . Replacing every rule probability by "true", by "or" and by "and" gives the recognition chart of CKY, which only records whether some tree exists. The three charts answer three different questions about the same set of trees: the total weight, the heaviest tree, and whether any tree exists.
Following backpointers reconstructs one best tree. Ties may give several equally good trees. Store all maximizing witnesses to recover all tied best trees. A zero entry cannot by itself distinguish no parse from a syntactically possible parse of weight zero; retain a separate Boolean chart if that distinction matters.
Proposition 32.1.5
(Cost of the two charts)
Let the sentence have tokens, let and be the binary and lexical rules, and assume constant-cost arithmetic. Direct iteration over rules evaluates at most binary rule-and-split terms and lexical terms, so the time is . A numerical chart has entries, which is .
Proof
(Counting spans and splits)
A cell with has possible splits , and each binary rule gives one term per split. Writing , there are cells of length , so the number of rule-and-split terms is . Each of the one-token cells examines every lexical rule once. The chart has one entry per nonterminal and per span , and there are spans. Retaining every backpointer may take more space than the numerical chart.
Worked examples
Worked example 32.1.6
(Two analyses of three tokens)
Let have probability and probability . This branching process terminates almost surely: if is its extinction probability, it is the smallest solution in of , namely . To see why the smallest root applies, let be the probability that every branch has stopped by depth . Starting from , the recurrence increases to the extinction probability; it stays below every nonnegative fixed point. The two trees for aaa have bracketings and . Each uses two binary rules and three lexical rules, so each has weight . Thus , while . Either tree is a valid Viterbi answer. The total exceeds the weight of either tree because the two derivations are distinct events.
Worked example 32.1.7
(Filling both charts for two parses of unequal weight)
Take the productions with probability , with probability , and , , , , , each with probability . For the sentence abc, the one-token cells are and zero for every other nonterminal. For length two, and ; the Viterbi values are the same. Every other length-two entry is zero. In particular the cell for over ab is zero: would need an over a alone, and would need a over b alone. So ab is an but not an , which is a zero entry caused by a missing parse rather than a zero-weight rule.
For the whole sentence, the rule with split contributes , and with split contributes . Hence and , with backpointer , which gives the tree . The conditional probability of that tree given the sentence is . The inside value is consistent with the model: abc is the only sentence with positive probability.
Worked example 32.1.8
(Underflow and the log-sum-exp step)
Suppose a long sentence has exactly two parses, of weights and . Both numbers are below the smallest positive double-precision number, so a direct product would underflow to zero and the chart could not tell them apart. In logarithms the first weight is and the second is . The Viterbi value is the larger one, . The inside value needs the sum: . Replacing the log-sum-exp by a maximum would report and underestimate the inside probability by the factor .
Common mistakes and subtle points
Counterexample mode
The highest-weight tree need not determine the highest-weight sentence
Claim: the sentence whose best parse tree is heavier is the more probable sentence. Take and with probability each, with probability , and , , , , , each with probability . The productions with each left side sum to one, and every derivation stops after two rewriting levels, so the finite trees have total weight . The sentence ab has two trees, and , of weight each, so and . The sentence cd has the single tree of weight , so . The Viterbi values rank cd first, but the sentence probabilities are and , so ab is the more probable sentence. Sentences must be compared by inside probability; Viterbi only chooses a tree for a given sentence.
The probability of a tree conditional on the observed sentence is its tree weight divided by , provided this denominator is positive. This posterior is different from the joint weight reported by Viterbi. Under the counterexample, each of the two trees for ab has conditional probability . If the sentence has zero probability, this conditional expression is undefined. In practice products of many small probabilities can underflow; log probabilities replace multiplication by addition, while computing a sum requires a stable log-sum-exp operation rather than a maximum.
Common mistake
(Counting the words instead of the derivations)
For aaa in the grammar (probability ), (probability ), the bracketings and yield the same string, and it is tempting to count them as one analysis and report . They are distinct trees, so the inside probability is . The sum runs over derivations, not over distinct strings of words.
Common mistake
(Local normalization is not termination)
Take with probability and with probability . The probabilities with left side sum to one, yet the finite trees have total weight only (the smaller root of ), so the sentence probabilities from the chart sum to rather than . Normalizing each rule family does not make the whole generative process a probability distribution over finite sentences.
Exercises
Quick check
(For the grammar (probability ), (probability ), compute and the total probability of aaaa. Explain the three possible root splits for the latter.)
Write for the inside value of copies of a and sum over the split lengths.
Solution · Answer
There is one two-token tree, of weight . The splits for four tokens have lengths , so
Equivalently there are five binary trees, each with three binary and four lexical rules, of weight .
Quick check
(Suppose two parses of a sentence have weights and , and no other parse has positive weight. Find its inside value, its Viterbi value and the posterior probability of the second parse given the sentence.)
Sum for one, maximize for the other, then divide a tree weight by the inside value.
Solution · Answer
The inside value is and the Viterbi value is . Conditional on the sentence, the second parse has probability . The maximum and sum answer different questions.
Quick check
(A grammar has with probability and with probability . Find the smallest solution in of . Why does local normalization not imply termination almost surely?)
Rearrange to a quadratic and look for a root different from .
Solution · Answer
The two solutions are and , so the extinction probability is . At every node the alternatives sum to one, but there is probability of an infinite derivation. Normalized local choices describe each step; they do not establish that the entire process halts.
Quick check
(In the grammar of the abc example, change the probabilities of and to and . Find the inside value, the Viterbi value and the backpointer at the top cell.)
Only the two top-level terms change; the length-two entries stay the same.
Solution · Answer
The terms are for at split and for at split . The inside value is , the Viterbi value is , and the backpointer is , giving the tree . The best tree has conditional probability .