Probabilistic context-free grammars

Reading

Jurafsky and Martin (2023, Ch. 18) on probabilistic context-free grammars and the inside algorithm.

A context-free grammar determines which trees are possible. But how can it rank two possible trees, or two words with different sets of trees? A probabilistic context-free grammar (PCFG) additionally specifies how probability mass is divided among the rules with the same left side.

Rule, tree, and string probabilities

Let $p(A\rightarrow\alpha)$ be the probability of a rule. For every $A\in V$,

\[ \sum_{A\rightarrow\alpha\in R}p(A\rightarrow\alpha)=1. \]

This local normalization is necessary, but it does not by itself guarantee that the grammar eventually reaches terminals with probability one. A grammar that can expand forever may place some mass on infinite derivations. We call a PCFG consistent when the probabilities of its finite terminal strings sum to one. The recurrences below compute probabilities of finite trees whether or not the grammar is consistent. When we interpret those values as a probability distribution over strings, we assume consistency.

The probability of a parse tree $t$ is the product of its rule probabilities:

\[ p(t)=\prod_{r\in t}p(r), \]

where repeated uses of a rule contribute repeated factors. The probability of a terminal string sums over its parses:

\[ p(\boldsymbol\sigma)= \sum_{t\,:\,\operatorname{yield}(t)=\boldsymbol\sigma}p(t). \]

This distinction matters whenever the grammar is ambiguous. A Viterbi parser returns the highest-probability tree; the inside algorithm returns the total probability of the string.

Question

A word has two parses with probabilities $.12$ and $.08$. What does a Viterbi parser return, and what probability does the PCFG assign to the word?

Answer

Viterbi returns the first parse with probability $.12$. The string probability is $.12+.08=.20$.

Supervised estimation

If the training data contain parse trees, the maximum-likelihood estimate is the relative frequency of a rule among rules with the same left side:

\[ \widehat p(A\rightarrow\alpha) =\frac{c(A\rightarrow\alpha)} {\sum_{A\rightarrow\beta}c(A\rightarrow\beta)}. \]

The numerator counts occurrences, not merely whether a tree contains the rule. Our CELEX tree class thus exposes rule_occurrences in addition to the set-valued rules property used for display.

from collections import Counter
from collections.abc import Iterable

import sys
sys.path.insert(0, "_code")
from celex import MorphTree
from grammar import Rule

type RuleProbabilities = dict[Rule, float]


def estimate_rule_probabilities(
    trees: Iterable[MorphTree],
) -> RuleProbabilities:
    """Estimate PCFG rule probabilities from parsed trees."""
    rule_counts: Counter[Rule] = Counter()
    for tree in trees:
        rule_counts.update(tree.rule_occurrences)

    left_side_counts: Counter[str] = Counter()
    for rule, count in rule_counts.items():
        left_side_counts[rule.left_side] += count

    return {
        rule: count / left_side_counts[rule.left_side]
        for rule, count in rule_counts.items()
    }

This estimator assigns zero probability to every unseen rule. Smoothing PCFG rules is possible, but it requires deciding which unobserved rules belong to the event space. We will keep the unsmoothed estimator and report when a word cannot be parsed.

The inside algorithm

For a CNF grammar, let $\alpha_A(i,j)$ be the total probability that $A$ derives the substring spanning $[i,j]$. The lexical case is

\[ \alpha_A(i,i+1)=p(A\rightarrow\sigma_i). \]

For a longer span,

\[ \alpha_A(i,j) =\sum_{A\rightarrow BC} \sum_{k=i+1}^{j-1} p(A\rightarrow BC)\alpha_B(i,k)\alpha_C(k,j). \]

Thus, $p(\boldsymbol\sigma)=\alpha_S(0,n)$. This is the probabilistic version of the CKY recurrence: set insertion becomes addition, and combining two children multiplies their probabilities.

Why the inside recurrence sums every parse once

Why does the inside recurrence sum every parse without counting any parse twice? Fix a variable $A$ and a span $[i,j]$. Partition the parse trees rooted at $A$ by two properties of their root: the binary rule $A\rightarrow BC$ and the split point $k$ between its children.

Once those properties are fixed, a complete tree consists of three independent choices under the PCFG model:

use the root rule, with probability $p(A\rightarrow BC)$;
choose a $B$ tree over $[i,k]$, whose total probability is $\alpha_B(i,k)$; and
choose a $C$ tree over $[k,j]$, whose total probability is $\alpha_C(k,j)$.

Multiplying the three terms gives the total probability of all trees in that part of the partition. Summing over rules and split points then covers every possible $A$ tree. It does not count a tree twice: a binary parse tree has one root rule and one boundary between its two root children.

For a length-one span, the only possible CNF tree is a lexical rule $A\rightarrow\sigma_i$, which gives the base case. Induction on span length thus shows that $\alpha_A(i,j)$ is exactly the sum of the probabilities of all $A$-rooted trees over that span. Setting $A=S$, $i=0$, and $j=n$ proves $p(\boldsymbol\sigma)=\alpha_S(0,n)$.

from collections import defaultdict
from collections.abc import Mapping, Sequence

type InsideCell = dict[str, float]
type InsideChart = list[list[InsideCell]]


def inside_probability(
    tokens: Sequence[str],
    start_variable: str,
    rule_probabilities: Mapping[Rule, float],
) -> float:
    """Return the total PCFG probability of ``tokens``."""
    if not tokens:
        return rule_probabilities.get(Rule(start_variable), 0.0)

    lexical_index: defaultdict[
        str, list[tuple[str, float]]
    ] = defaultdict(list)
    binary_index: defaultdict[
        tuple[str, str], list[tuple[str, float]]
    ] = defaultdict(list)

    for rule, probability in rule_probabilities.items():
        if len(rule.right_side) == 1:
            lexical_index[rule.right_side[0]].append(
                (rule.left_side, probability)
            )
        elif len(rule.right_side) == 2:
            binary_index[rule.right_side].append(
                (rule.left_side, probability)
            )

    size = len(tokens)
    chart: InsideChart = [
        [{} for _ in range(size + 1)] for _ in range(size + 1)
    ]

    for left, token in enumerate(tokens):
        for variable, probability in lexical_index[token]:
            chart[left][left + 1][variable] = (
                chart[left][left + 1].get(variable, 0.0) + probability
            )

    for span_length in range(2, size + 1):
        for left in range(size - span_length + 1):
            right = left + span_length
            for split in range(left + 1, right):
                for left_variable, left_probability in chart[left][
                    split
                ].items():
                    for right_variable, right_probability in chart[
                        split
                    ][right].items():
                        for parent, rule_probability in binary_index[
                            (left_variable, right_variable)
                        ]:
                            contribution = (
                                rule_probability
                                * left_probability
                                * right_probability
                            )
                            chart[left][right][parent] = (
                                chart[left][right].get(parent, 0.0)
                                + contribution
                            )

    return chart[0][size].get(start_variable, 0.0)

For a large grammar, these products may underflow. An implementation used for estimation should work in log space and replace addition with logsumexp. The probability-space version makes the recurrence easier to inspect.

Estimating from CELEX

The supervised pipeline has three stages:

parse each usable StrucLab value into a MorphTree;
count its rule occurrences and estimate rule probabilities; and
convert the resulting grammar to CNF, carrying the probabilities through the added administrative rules.

The third stage requires care. CNF conversion preserves strings, but adding probability-one administrative rules and redistributing probability across eliminated rules must also preserve tree probability. For this reason, it is often simpler to normalize the grammar before estimating its probabilities or to use an Earley-style inside algorithm that accepts the original rules.

Scoring acceptability

Given a segmented trial word, the inside score supplies one predictor of its mean acceptability. Raw string probabilities are strongly affected by length, so we will use mean log probability per morpheme or include morpheme count as a separate predictor:

\[ \operatorname{score}(\boldsymbol\sigma) =\frac{\log p(\boldsymbol\sigma)}{|\boldsymbol\sigma|}. \]

This score tests whether rule combinations that are probable under the CELEX trees also tend to receive higher ratings. It does not isolate hierarchy by itself, because the supervised grammar has access to both gold segmentation and gold trees. The next section removes the gold trees and treats them as latent structure.

References

Jurafsky, Daniel, and James H. Martin. 2023. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. 3rd ed. https://web.stanford.edu/~jurafsky/slp3/old_jan23/ed3book.pdf.

--- title: Probabilistic context-free grammars bibliography: ../references.bib jupyter: python3 execute: eval: false --- ::: {.callout-tip} ## Reading @jurafsky_speech_2023[Ch. 18] on probabilistic context-free grammars and the inside algorithm. ::: A context-free grammar determines which trees are possible. But how can it rank two possible trees, or two words with different sets of trees? A **probabilistic context-free grammar** (PCFG) additionally specifies how probability mass is divided among the rules with the same left side. ## Rule, tree, and string probabilities Let $p(A\rightarrow\alpha)$ be the probability of a rule. For every $A\in V$, $$ \sum_{A\rightarrow\alpha\in R}p(A\rightarrow\alpha)=1. $$ This local normalization is necessary, but it does not by itself guarantee that the grammar eventually reaches terminals with probability one. A grammar that can expand forever may place some mass on infinite derivations. We call a PCFG **consistent** when the probabilities of its finite terminal strings sum to one. The recurrences below compute probabilities of finite trees whether or not the grammar is consistent. When we interpret those values as a probability distribution over strings, we assume consistency. The probability of a parse tree $t$ is the product of its rule probabilities: $$ p(t)=\prod_{r\in t}p(r), $$ where repeated uses of a rule contribute repeated factors. The probability of a terminal string sums over its parses: $$ p(\boldsymbol\sigma)= \sum_{t\,:\,\operatorname{yield}(t)=\boldsymbol\sigma}p(t). $$ This distinction matters whenever the grammar is ambiguous. A Viterbi parser returns the highest-probability tree; the inside algorithm returns the total probability of the string. ::: {.callout-caution} ## Question A word has two parses with probabilities $.12$ and $.08$. What does a Viterbi parser return, and what probability does the PCFG assign to the word? ::: ::: {.callout-tip collapse=true} ## Answer Viterbi returns the first parse with probability $.12$. The string probability is $.12+.08=.20$. ::: ## Supervised estimation If the training data contain parse trees, the maximum-likelihood estimate is the relative frequency of a rule among rules with the same left side: $$ \widehat p(A\rightarrow\alpha) =\frac{c(A\rightarrow\alpha)} {\sum_{A\rightarrow\beta}c(A\rightarrow\beta)}. $$ The numerator counts *occurrences*, not merely whether a tree contains the rule. Our CELEX tree class thus exposes `rule_occurrences` in addition to the set-valued `rules` property used for display. ```{python} from collections import Counter from collections.abc import Iterable import sys sys.path.insert(0, "_code") from celex import MorphTree from grammar import Rule type RuleProbabilities = dict[Rule, float] def estimate_rule_probabilities( trees: Iterable[MorphTree], ) -> RuleProbabilities: """Estimate PCFG rule probabilities from parsed trees.""" rule_counts: Counter[Rule] = Counter() for tree in trees: rule_counts.update(tree.rule_occurrences) left_side_counts: Counter[str] = Counter() for rule, count in rule_counts.items(): left_side_counts[rule.left_side] += count return { rule: count / left_side_counts[rule.left_side] for rule, count in rule_counts.items() } ``` This estimator assigns zero probability to every unseen rule. Smoothing PCFG rules is possible, but it requires deciding which unobserved rules belong to the event space. We will keep the unsmoothed estimator and report when a word cannot be parsed. ## The inside algorithm For a CNF grammar, let $\alpha_A(i,j)$ be the total probability that $A$ derives the substring spanning $[i,j]$. The lexical case is $$ \alpha_A(i,i+1)=p(A\rightarrow\sigma_i). $$ For a longer span, $$ \alpha_A(i,j) =\sum_{A\rightarrow BC} \sum_{k=i+1}^{j-1} p(A\rightarrow BC)\alpha_B(i,k)\alpha_C(k,j). $$ Thus, $p(\boldsymbol\sigma)=\alpha_S(0,n)$. This is the probabilistic version of the CKY recurrence: set insertion becomes addition, and combining two children multiplies their probabilities. ## Why the inside recurrence sums every parse once Why does the inside recurrence sum every parse without counting any parse twice? Fix a variable $A$ and a span $[i,j]$. Partition the parse trees rooted at $A$ by two properties of their root: the binary rule $A\rightarrow BC$ and the split point $k$ between its children. Once those properties are fixed, a complete tree consists of three independent choices under the PCFG model: 1. use the root rule, with probability $p(A\rightarrow BC)$; 2. choose a $B$ tree over $[i,k]$, whose total probability is $\alpha_B(i,k)$; and 3. choose a $C$ tree over $[k,j]$, whose total probability is $\alpha_C(k,j)$. Multiplying the three terms gives the total probability of all trees in that part of the partition. Summing over rules and split points then covers every possible $A$ tree. It does not count a tree twice: a binary parse tree has one root rule and one boundary between its two root children. For a length-one span, the only possible CNF tree is a lexical rule $A\rightarrow\sigma_i$, which gives the base case. Induction on span length thus shows that $\alpha_A(i,j)$ is exactly the sum of the probabilities of all $A$-rooted trees over that span. Setting $A=S$, $i=0$, and $j=n$ proves $p(\boldsymbol\sigma)=\alpha_S(0,n)$. ```{python} from collections import defaultdict from collections.abc import Mapping, Sequence type InsideCell = dict[str, float] type InsideChart = list[list[InsideCell]] def inside_probability( tokens: Sequence[str], start_variable: str, rule_probabilities: Mapping[Rule, float], ) -> float: """Return the total PCFG probability of ``tokens``.""" if not tokens: return rule_probabilities.get(Rule(start_variable), 0.0) lexical_index: defaultdict[ str, list[tuple[str, float]] ] = defaultdict(list) binary_index: defaultdict[ tuple[str, str], list[tuple[str, float]] ] = defaultdict(list) for rule, probability in rule_probabilities.items(): if len(rule.right_side) == 1: lexical_index[rule.right_side[0]].append( (rule.left_side, probability) ) elif len(rule.right_side) == 2: binary_index[rule.right_side].append( (rule.left_side, probability) ) size = len(tokens) chart: InsideChart = [ [{} for _ in range(size + 1)] for _ in range(size + 1) ] for left, token in enumerate(tokens): for variable, probability in lexical_index[token]: chart[left][left + 1][variable] = ( chart[left][left + 1].get(variable, 0.0) + probability ) for span_length in range(2, size + 1): for left in range(size - span_length + 1): right = left + span_length for split in range(left + 1, right): for left_variable, left_probability in chart[left][ split ].items(): for right_variable, right_probability in chart[ split ][right].items(): for parent, rule_probability in binary_index[ (left_variable, right_variable) ]: contribution = ( rule_probability * left_probability * right_probability ) chart[left][right][parent] = ( chart[left][right].get(parent, 0.0) + contribution ) return chart[0][size].get(start_variable, 0.0) ``` For a large grammar, these products may underflow. An implementation used for estimation should work in log space and replace addition with `logsumexp`. The probability-space version makes the recurrence easier to inspect. ## Estimating from CELEX The supervised pipeline has three stages: 1. parse each usable `StrucLab` value into a `MorphTree`; 2. count its rule occurrences and estimate rule probabilities; and 3. convert the resulting grammar to CNF, carrying the probabilities through the added administrative rules. The third stage requires care. CNF conversion preserves strings, but adding probability-one administrative rules and redistributing probability across eliminated rules must also preserve tree probability. For this reason, it is often simpler to normalize the grammar before estimating its probabilities or to use an Earley-style inside algorithm that accepts the original rules. ## Scoring acceptability Given a segmented trial word, the inside score supplies one predictor of its mean acceptability. Raw string probabilities are strongly affected by length, so we will use mean log probability per morpheme or include morpheme count as a separate predictor: $$ \operatorname{score}(\boldsymbol\sigma) =\frac{\log p(\boldsymbol\sigma)}{|\boldsymbol\sigma|}. $$ This score tests whether rule combinations that are probable under the CELEX trees also tend to receive higher ratings. It does not isolate hierarchy by itself, because the supervised grammar has access to both gold segmentation and gold trees. The next section removes the gold trees and treats them as latent structure.