Learning with latent trees

Reading

Baker (1979) and Lari and Young (1990) on inside-outside estimation; Dempster et al. (1977) on expectation-maximization more generally.

The supervised PCFG estimator observes a tree for every training word. What can we learn if we remove those trees? The terminals remain observed, but their hierarchical analysis is latent. We will call this the tree-latent learning problem.

This terminology is deliberate. If the terminal sequences come from gold CELEX boundaries or from a CRF trained on those boundaries, the procedure is not fully unsupervised: segmentation is supervised even though constituency is not. BPE segments yield a less supervised comparison because they are learned without morphological boundary labels.

Expectation-maximization

We begin with a grammar skeleton whose rules specify the possible trees and with initial probabilities for those rules. The expectation-maximization (EM) algorithm then alternates two steps (Dempster et al. 1977):

Expectation: compute the expected number of times each rule occurs across the possible parses under the current parameters.
Maximization: renormalize those expected counts by left side to obtain new rule probabilities.

The E step replaces the observed counts used by the supervised estimator with posterior expected counts. The M step is otherwise the same relative-frequency calculation.

Inside and outside probabilities

The inside probability $\alpha_A(i,j)$ measures the probability that $A$ derives the observed substring over $[i,j]$. We computed it in the previous section.

The outside probability $\beta_A(i,j)$ measures the probability of generating the rest of the string while treating $A$ over $[i,j]$ as a fixed constituent. Its base case is

\[\beta_S(0,n)=1.\]

The remaining outside values are computed top-down. Whenever $A$ occurs as one child of a binary rule, the update multiplies three terms: the outside probability of the parent, the probability of the rule, and the inside probability of the sibling.

For a binary rule $r=A\rightarrow BC$ used over $[i,j]$ with split point $k$, the posterior expected count contributed by one string is

\[ \mathbb{E}[c(r,i,k,j)] =\frac{ \beta_A(i,j)\,p(r)\, \alpha_B(i,k)\,\alpha_C(k,j) }{ \alpha_S(0,n) }. \]

The denominator is the total probability of the observed string. Summing this expression over spans, split points, and training strings gives the expected count of $r$. Lexical rules use the analogous expression over length-one spans.

Deriving the expected-count formula

Fix the event that rule $r=A\rightarrow BC$ is used over $[i,j]$ with split $k$. Every parse containing this event separates into four pieces:

the structure outside the $A$ constituent, with total weight $\beta_A(i,j)$;
the rule choice, with weight $p(r)$;
a $B$ subtree over $[i,k]$, with total weight $\alpha_B(i,k)$; and
a $C$ subtree over $[k,j]$, with total weight $\alpha_C(k,j)$.

Their product is the joint probability of the observed string and this local rule event. Dividing by the string probability $\alpha_S(0,n)$ gives the posterior probability of the event conditional on the observed string. Because an indicator variable has expectation equal to the probability that it is one, this posterior probability is the event’s expected count. Summing the indicators over all possible spans and splits gives the expected number of uses of $r$.

Question

If a training word has exactly two parses with posterior probabilities $.7$ and $.3$, and a rule occurs once in the first parse but not in the second, what expected count does that word contribute for the rule?

Answer

$.7$. Expected counts weight each parse’s rule count by that parse’s posterior probability.

The maximization step

Let $\widetilde c(r)$ be the expected count of rule $r$. The updated probability is

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

We can derive this normalization rather than assume it. For one left side $A$, the part of the expected complete-data log likelihood that depends on its rule probabilities is

\[ Q_A=\sum_{r:\operatorname{lhs}(r)=A} \widetilde c(r)\log p(r), \]

subject to $\sum_rp(r)=1$. Introduce a Lagrange multiplier $\lambda$ and differentiate:

\[ \frac{\partial}{\partial p(r)} \left[ \sum_r\widetilde c(r)\log p(r) +\lambda\left(1-\sum_rp(r)\right) \right] =\frac{\widetilde c(r)}{p(r)}-\lambda. \]

At the optimum, this derivative is zero, so $p(r)=\widetilde c(r)/\lambda$. Summing over the rules with left side $A$ and using the normalization constraint gives $\lambda=\sum_r\widetilde c(r)$. Substitution yields the displayed update.

from collections import Counter
from collections.abc import Mapping
from math import isfinite

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


def maximize_rule_probabilities(
    expected_counts: Mapping[Rule, float],
) -> dict[Rule, float]:
    """Normalize expected rule counts within each left side."""
    left_side_totals: Counter[str] = Counter()
    for rule, count in expected_counts.items():
        left_side_totals[rule.left_side] += count

    return {
        rule: count / left_side_totals[rule.left_side]
        for rule, count in expected_counts.items()
        if left_side_totals[rule.left_side] > 0.0
    }

A complete implementation alternates the inside-outside E step with maximize_rule_probabilities until the change in corpus log likelihood falls below a threshold.

initialize rule probabilities
repeat:
    expected_counts = inside_outside(training_strings, probabilities)
    probabilities = maximize_rule_probabilities(expected_counts)
until the log-likelihood change is small

Why an EM iteration does not lower likelihood

Why should alternating these two steps improve the fit? Let $q(t)$ be the posterior probability of latent tree $t$ under the current parameters $\theta^{old}$. Terms with $q(t)=0$ contribute nothing, so the sums below range over trees in the support of $q$. For one observed string $w$,

\[ \begin{aligned} \log p_\theta(w) &=\log\sum_t p_\theta(w,t)\\ &=\log\sum_t q(t)\frac{p_\theta(w,t)}{q(t)}\\ &\geq\sum_tq(t)\log\frac{p_\theta(w,t)}{q(t)}. \end{aligned} \]

Call the right side $F(\theta,q)$. The last step is Jensen’s inequality, so $\log p_\theta(w)\geq F(\theta,q)$ for any new parameter value $\theta$. At $\theta=\theta^{old}$, the bound is tight because $q$ is the old posterior:

\[ F(\theta^{old},q)=\log p_{\theta^{old}}(w). \]

The E step computes the expectations under this fixed $q$. The M step chooses $\theta^{new}$ to maximize the parameter-dependent part of $F$, so

\[ F(\theta^{new},q)\geq F(\theta^{old},q). \]

Putting the two inequalities and the equality together gives

\[ \log p_{\theta^{new}}(w) \geq F(\theta^{new},q) \geq F(\theta^{old},q) =\log p_{\theta^{old}}(w). \]

This is the promised monotonicity result: one exact EM iteration cannot lower the observed-data log likelihood.

This guarantee is local to each iteration. EM does not add rules to the skeleton, so every training string must have at least one parse under the initial grammar. And the procedure may converge to a local optimum or to parameters whose latent categories have no useful morphological interpretation.

Three information conditions

We can now separate three comparisons that the earlier presentation conflated:

A tree-supervised PCFG observes both CELEX morpheme boundaries and CELEX trees.
A tree-latent PCFG observes CELEX boundaries, or predictions from a boundary-supervised CRF, but estimates the trees with inside-outside.
A boundary- and tree-latent PCFG uses an unsupervised segmentation such as BPE and estimates the trees with inside-outside.

The first-to-second comparison estimates what is lost when trees are hidden but boundaries are held relatively constant. The second-to-third comparison changes the boundary information as well, so it cannot isolate the contribution of tree supervision.

Evaluating the learned scores

For each trial word, we compute a length-adjusted inside score and compare its ordering with the mean human rating. Spearman’s $\rho$ is useful when we want to test a monotonic relation without assuming that differences between PCFG log probabilities are on the same scale as differences between ratings (Spearman 1904).

from collections.abc import Mapping

from scipy.stats import spearmanr


def rank_correlation(
    model_scores: Mapping[str, float],
    human_scores: Mapping[str, float],
) -> float:
    """Return Spearman correlation over words scored by both mappings."""
    words = sorted(model_scores.keys() & human_scores.keys())
    if len(words) < 2:
        raise ValueError("at least two shared words are required")
    statistic = spearmanr(
        [model_scores[word] for word in words],
        [human_scores[word] for word in words],
    ).statistic
    correlation = float(statistic)
    if not isfinite(correlation):
        raise ValueError("Spearman correlation is undefined for these scores")
    return correlation

This evaluation should be performed on held-out words. A higher correlation for the supervised PCFG would be consistent with a contribution from annotated constituency, though it would not prove that the learned categories match speakers’ representations. Differences in coverage, segmentation errors, and the grammar skeleton remain live alternative explanations.

The same inside, outside, and agenda-based ideas carry over to syntactic parsing. The next module changes the terminals from morphemes to words and then asks when context-free constituency is no longer enough.

References

Baker, James K. 1979. “Trainable Grammars for Speech Recognition.” The Journal of the Acoustical Society of America 65 (S1): S132. https://doi.org/10.1121/1.382260.

Dempster, Arthur P., Nan M. Laird, and Donald B. Rubin. 1977. “Maximum Likelihood from Incomplete Data via the EM Algorithm.” Journal of the Royal Statistical Society: Series B (Methodological) 39 (1): 1–38. https://doi.org/10.1111/j.2517-6161.1977.tb01600.x.

Lari, Karim, and Steve J. Young. 1990. “The Estimation of Stochastic Context-Free Grammars Using the Inside-Outside Algorithm.” Computer Speech & Language 4 (1): 35–56. https://doi.org/10.1016/0885-2308(90)90022-X.

Spearman, Charles. 1904. “The Proof and Measurement of Association Between Two Things.” The American Journal of Psychology 15 (1): 72–101. https://doi.org/10.2307/1412159.

--- title: Learning with latent trees bibliography: ../references.bib jupyter: python3 execute: eval: false --- ::: {.callout-tip} ## Reading @baker_trainable_1979 and @lari_estimation_1990 on inside-outside estimation; @dempster_maximum_1977 on expectation-maximization more generally. ::: The supervised PCFG estimator observes a tree for every training word. What can we learn if we remove those trees? The terminals remain observed, but their hierarchical analysis is latent. We will call this the **tree-latent learning problem**. This terminology is deliberate. If the terminal sequences come from gold CELEX boundaries or from a CRF trained on those boundaries, the procedure is not fully unsupervised: segmentation is supervised even though constituency is not. BPE segments yield a less supervised comparison because they are learned without morphological boundary labels. ## Expectation-maximization We begin with a grammar skeleton whose rules specify the possible trees and with initial probabilities for those rules. The expectation-maximization (EM) algorithm then alternates two steps [@dempster_maximum_1977]: 1. **Expectation:** compute the expected number of times each rule occurs across the possible parses under the current parameters. 2. **Maximization:** renormalize those expected counts by left side to obtain new rule probabilities. The E step replaces the observed counts used by the supervised estimator with posterior expected counts. The M step is otherwise the same relative-frequency calculation. ## Inside and outside probabilities The inside probability $\alpha_A(i,j)$ measures the probability that $A$ derives the observed substring over $[i,j]$. We computed it in the previous section. The **outside probability** $\beta_A(i,j)$ measures the probability of generating the rest of the string while treating $A$ over $[i,j]$ as a fixed constituent. Its base case is $$\beta_S(0,n)=1.$$ The remaining outside values are computed top-down. Whenever $A$ occurs as one child of a binary rule, the update multiplies three terms: the outside probability of the parent, the probability of the rule, and the inside probability of the sibling. For a binary rule $r=A\rightarrow BC$ used over $[i,j]$ with split point $k$, the posterior expected count contributed by one string is $$ \mathbb{E}[c(r,i,k,j)] =\frac{ \beta_A(i,j)\,p(r)\, \alpha_B(i,k)\,\alpha_C(k,j) }{ \alpha_S(0,n) }. $$ The denominator is the total probability of the observed string. Summing this expression over spans, split points, and training strings gives the expected count of $r$. Lexical rules use the analogous expression over length-one spans. ## Deriving the expected-count formula Fix the event that rule $r=A\rightarrow BC$ is used over $[i,j]$ with split $k$. Every parse containing this event separates into four pieces: 1. the structure outside the $A$ constituent, with total weight $\beta_A(i,j)$; 2. the rule choice, with weight $p(r)$; 3. a $B$ subtree over $[i,k]$, with total weight $\alpha_B(i,k)$; and 4. a $C$ subtree over $[k,j]$, with total weight $\alpha_C(k,j)$. Their product is the joint probability of the observed string and this local rule event. Dividing by the string probability $\alpha_S(0,n)$ gives the posterior probability of the event conditional on the observed string. Because an indicator variable has expectation equal to the probability that it is one, this posterior probability is the event's expected count. Summing the indicators over all possible spans and splits gives the expected number of uses of $r$. ::: {.callout-caution} ## Question If a training word has exactly two parses with posterior probabilities $.7$ and $.3$, and a rule occurs once in the first parse but not in the second, what expected count does that word contribute for the rule? ::: ::: {.callout-tip collapse=true} ## Answer $.7$. Expected counts weight each parse's rule count by that parse's posterior probability. ::: ## The maximization step Let $\widetilde c(r)$ be the expected count of rule $r$. The updated probability is $$ p(A\rightarrow\alpha) =\frac{\widetilde c(A\rightarrow\alpha)} {\sum_{A\rightarrow\gamma}\widetilde c(A\rightarrow\gamma)}. $$ We can derive this normalization rather than assume it. For one left side $A$, the part of the expected complete-data log likelihood that depends on its rule probabilities is $$ Q_A=\sum_{r:\operatorname{lhs}(r)=A} \widetilde c(r)\log p(r), $$ subject to $\sum_rp(r)=1$. Introduce a Lagrange multiplier $\lambda$ and differentiate: $$ \frac{\partial}{\partial p(r)} \left[ \sum_r\widetilde c(r)\log p(r) +\lambda\left(1-\sum_rp(r)\right) \right] =\frac{\widetilde c(r)}{p(r)}-\lambda. $$ At the optimum, this derivative is zero, so $p(r)=\widetilde c(r)/\lambda$. Summing over the rules with left side $A$ and using the normalization constraint gives $\lambda=\sum_r\widetilde c(r)$. Substitution yields the displayed update. ```{python} from collections import Counter from collections.abc import Mapping from math import isfinite import sys sys.path.insert(0, "_code") from grammar import Rule def maximize_rule_probabilities( expected_counts: Mapping[Rule, float], ) -> dict[Rule, float]: """Normalize expected rule counts within each left side.""" left_side_totals: Counter[str] = Counter() for rule, count in expected_counts.items(): left_side_totals[rule.left_side] += count return { rule: count / left_side_totals[rule.left_side] for rule, count in expected_counts.items() if left_side_totals[rule.left_side] > 0.0 } ``` A complete implementation alternates the inside-outside E step with `maximize_rule_probabilities` until the change in corpus log likelihood falls below a threshold. ```text initialize rule probabilities repeat: expected_counts = inside_outside(training_strings, probabilities) probabilities = maximize_rule_probabilities(expected_counts) until the log-likelihood change is small ``` ## Why an EM iteration does not lower likelihood Why should alternating these two steps improve the fit? Let $q(t)$ be the posterior probability of latent tree $t$ under the current parameters $\theta^{old}$. Terms with $q(t)=0$ contribute nothing, so the sums below range over trees in the support of $q$. For one observed string $w$, $$ \begin{aligned} \log p_\theta(w) &=\log\sum_t p_\theta(w,t)\\ &=\log\sum_t q(t)\frac{p_\theta(w,t)}{q(t)}\\ &\geq\sum_tq(t)\log\frac{p_\theta(w,t)}{q(t)}. \end{aligned} $$ Call the right side $F(\theta,q)$. The last step is Jensen's inequality, so $\log p_\theta(w)\geq F(\theta,q)$ for any new parameter value $\theta$. At $\theta=\theta^{old}$, the bound is tight because $q$ is the old posterior: $$ F(\theta^{old},q)=\log p_{\theta^{old}}(w). $$ The E step computes the expectations under this fixed $q$. The M step chooses $\theta^{new}$ to maximize the parameter-dependent part of $F$, so $$ F(\theta^{new},q)\geq F(\theta^{old},q). $$ Putting the two inequalities and the equality together gives $$ \log p_{\theta^{new}}(w) \geq F(\theta^{new},q) \geq F(\theta^{old},q) =\log p_{\theta^{old}}(w). $$ This is the promised monotonicity result: one exact EM iteration cannot lower the observed-data log likelihood. This guarantee is local to each iteration. EM does not add rules to the skeleton, so every training string must have at least one parse under the initial grammar. And the procedure may converge to a local optimum or to parameters whose latent categories have no useful morphological interpretation. ## Three information conditions We can now separate three comparisons that the earlier presentation conflated: 1. A **tree-supervised PCFG** observes both CELEX morpheme boundaries and CELEX trees. 2. A **tree-latent PCFG** observes CELEX boundaries, or predictions from a boundary-supervised CRF, but estimates the trees with inside-outside. 3. A **boundary- and tree-latent PCFG** uses an unsupervised segmentation such as BPE and estimates the trees with inside-outside. The first-to-second comparison estimates what is lost when trees are hidden but boundaries are held relatively constant. The second-to-third comparison changes the boundary information as well, so it cannot isolate the contribution of tree supervision. ## Evaluating the learned scores For each trial word, we compute a length-adjusted inside score and compare its ordering with the mean human rating. Spearman's $\rho$ is useful when we want to test a monotonic relation without assuming that differences between PCFG log probabilities are on the same scale as differences between ratings [@spearman_proof_1904]. ```{python} from collections.abc import Mapping from scipy.stats import spearmanr def rank_correlation( model_scores: Mapping[str, float], human_scores: Mapping[str, float], ) -> float: """Return Spearman correlation over words scored by both mappings.""" words = sorted(model_scores.keys() & human_scores.keys()) if len(words) < 2: raise ValueError("at least two shared words are required") statistic = spearmanr( [model_scores[word] for word in words], [human_scores[word] for word in words], ).statistic correlation = float(statistic) if not isfinite(correlation): raise ValueError("Spearman correlation is undefined for these scores") return correlation ``` This evaluation should be performed on held-out words. A higher correlation for the supervised PCFG would be consistent with a contribution from annotated constituency, though it would not prove that the learned categories match speakers' representations. Differences in coverage, segmentation errors, and the grammar skeleton remain live alternative explanations. The same inside, outside, and agenda-based ideas carry over to syntactic parsing. The next module changes the terminals from morphemes to words and then asks when context-free constituency is no longer enough.