Statistical Parsers (1997) › The Solution: Learning from Treebanks

Statistical parsing addressed these fundamental limitations by learning parsing models directly from large annotated corpora, especially the Penn Treebank. Instead of encoding linguistic knowledge through hand-crafted rules, statistical parsers learned probabilistic models that captured both the grammatical patterns and the statistical regularities present in real language use. This shift from rules to probabilities gave parsing systems a way to rank ambiguous analyses and account for variation in real language.

The Penn Treebank, developed at the University of Pennsylvania beginning in 1989, provided the essential resource that made statistical parsing possible. This corpus contained tens of thousands of sentences from the Wall Street Journal, each manually annotated with detailed parse trees showing the hierarchical structure of phrases, clauses, and sentences. These annotations represented an enormous investment of human linguistic expertise, but they provided something that rule-based systems could never achieve on their own: a large-scale sample of how expert linguists parse real sentences.

Michael Collins's 1997 parser represented a breakthrough in how statistical parsing models could be constructed from treebank data. Instead of simply counting parse tree frequencies, Collins developed a sophisticated probabilistic model that learned to score different parse structures based on multiple factors: lexical dependencies between words, phrase structure patterns, and contextual information. The parser used a probabilistic context-free grammar framework, where each grammar rule was associated with a probability learned from the training data.

The core innovation of Collins's approach was lexicalization, the incorporation of specific word identities into the parsing model. Traditional context-free grammars operated at the level of syntactic categories like noun phrase or verb phrase, treating all nouns or all verbs as equivalent. Collins's parser learned that different words have different syntactic preferences: the verb "put" almost always requires a direct object and a prepositional phrase, while "sleep" typically requires neither. By learning these word-specific preferences from the treebank, the parser could make much more informed decisions about how to structure sentences.

The probabilistic framework also enabled principled ambiguity resolution. When a sentence had multiple valid parse trees, the parser could calculate the probability of each parse given the learned model and select the most probable one. This wasn't simply choosing the most frequent parse pattern; it involved calculating complex interactions between lexical preferences, phrase structure probabilities, and contextual factors. The result was a parsing system that could generate linguistically valid analyses and identify which analyses were most likely to be correct.

The mathematical foundation of statistical parsing lay in probabilistic context-free grammars (PCFGs), which extended traditional context-free grammars by associating each grammar rule with a probability. In a PCFG, a rule like $NP \to Det\ N$ (a noun phrase consists of a determiner followed by a noun) would have an associated probability $P(NP \to Det\ N)$ indicating how likely this expansion is when generating a noun phrase.

These probabilities are learned from treebank data through maximum likelihood estimation. If the treebank contains 1000 noun phrases, and 800 of them follow the pattern $Det\ N$, then the probability $P(NP \to Det\ N)$ would be estimated as 0.8. More sophisticated smoothing techniques ensure that rare or unseen patterns still receive non-zero probabilities, allowing the parser to handle constructions that didn't appear in the training data.

The probability of a complete parse tree is calculated by multiplying the probabilities of all rules used in that parse. If a sentence has two possible parse trees, the parser selects the one with the higher probability. This probabilistic approach provides a principled mathematical basis for ambiguity resolution, replacing the ad hoc heuristics used in rule-based systems with well-founded probability theory.

However, basic PCFGs have limitations. They treat all words in the same syntactic category as equivalent, missing important lexical dependencies. The sentence "The cat sat" and "The dog sat" would be treated identically by a basic PCFG, even though the lexical properties of "cat" versus "dog" might be relevant for parsing more complex sentences.

Collins's key contribution was developing lexicalized parsing models that incorporated word identities into the probabilistic framework. Instead of only learning probabilities for syntactic categories, these models learned probabilities for specific lexical items and their interactions. This lexicalization enabled the parser to capture fine-grained patterns that basic PCFGs missed.

In a lexicalized model, the parser might learn that the verb "put" strongly prefers a structure with both a direct object and a prepositional phrase, while "sleep" typically requires neither. It might learn that "believe" often introduces a complement clause, while "think" can appear in simpler structures. These word-specific preferences are learned automatically from the treebank, without requiring linguists to manually encode lexical properties.

The mathematical formulation of lexicalized parsing involves conditioning probabilities on lexical heads. Instead of simply calculating $P(NP \to Det\ N)$, a lexicalized model might calculate $P(NP(h) \to Det\ N(h))$ where $h$ represents the head word of the noun phrase. This allows the parser to learn that noun phrases headed by different words might have different structural preferences, even when they belong to the same syntactic category.

Collins's parser used a sophisticated factorization scheme that decomposed the probability of a parse tree into multiple components: the probability of generating lexical heads, the probability of generating phrase structures, and the probability of generating dependency relationships between words. This factorization made the learning problem tractable while still capturing the complex interactions between lexical and structural information.

Training a statistical parser involves learning the parameters of the probabilistic model from treebank data. This typically uses maximum likelihood estimation, where the parser chooses parameters that maximize the probability of the training data. The treebank provides both the input sentences and the correct parse trees, creating a supervised learning problem where the parser learns to reproduce the expert annotations.

The training process involves counting how often different rules and patterns appear in the treebank and converting these counts into probabilities. More sophisticated techniques use smoothing to handle rare patterns and ensure that all possible rules receive non-zero probabilities. This allows the parser to generalize beyond the exact patterns seen in training, handling new sentences that contain constructions not explicitly present in the treebank.

Inference on a new sentence requires finding its most probable parse tree according to the learned model. This is computationally challenging because the number of possible parse trees grows exponentially with sentence length. Collins's parser used dynamic programming techniques, specifically the CKY algorithm (a variant of the Cocke-Younger-Kasami algorithm), to efficiently find the most probable parse without exhaustively exploring all possibilities.

The CKY algorithm builds parse trees bottom-up, starting with individual words and progressively combining them into larger phrases. At each step, it maintains a table storing the highest-probability parse for each span of words and each syntactic category. By reusing these sub-problem solutions, the algorithm can find the optimal parse tree in polynomial time, making statistical parsing computationally practical for real-world applications.