Accurate Unlexicalized Parsing

An unlexicalized PCFG can parse far more accurately than previously shown, using simple, linguistically motivated state splits that break down false independence assumptions of the vanilla treebank grammar: 86.36% F1, better than early lexicalized PCFGs (Magerman 1995, Collins 1996) and close to the state of the art.

Johnson (1998) improved an unlexicalized treebank PCFG enormously just by parent annotation, and Gildea (2001) found that removing bilexical probabilities from a good lexicalized parser cost at most 0.5% in-domain and nothing out of domain.

Sparseness: a million words isn’t enough. Even for central WSJ topics, plausible dependencies occur once (stocks stabilized) or never (stocks skyrocketed).

It is more compact, easier to replicate, interpret and improve; parsing is simpler, better understood and asymptotically faster (\(O(n^3)\) vs \(O(n^5)\) naively, or \(O(n^4)\) with Eisner and Satta 1999), with smaller grammar constants and easier optimization and pruning.

No: lexical dependencies are useful for major ambiguity classes and parsers should use them. They argued that unlexicalized structural context was underexploited, giving a much stronger lower bound and showing that lexicalization’s benefit had been overestimated.

Train on WSJ sections 2–21, develop on 393 sentences of section 22 (a partly manual hill-climb on features), test on section 23. Trees are transformed, then rule probabilities are unsmoothed maximum-likelihood estimates, parsed exhaustively with a generalized CKY parser.

Only tagging probabilities were smoothed: words map to classes by capitalization, suffix, digits and other character features, and \(P(\text{tag} \mid \text{word}) = \frac{c(\text{tag}, \text{word}) + \kappa P(\text{tag} \mid \text{wordclass})}{c(\text{word}) + \kappa}\), then inverted to \(P(\text{word} \mid \text{tag})\).

(1) Categories are too coarse to make expansions independent of context: a subject NP is 8.7 times more likely than an object NP to be just a pronoun. (2) Sparsity: many rules seen once are overestimated, and many rules in test sentences were never seen.

Vertical: how many ancestors condition an expansion (\(v = 2\) is parent annotation, e.g. NP^S vs NP^VP). Horizontal: how many previously generated siblings condition the next child, generating right-hand sides outward from the head. The raw treebank grammar is \(v = 1\), \(h = \infty\), a historical accident; increasing \(v\) and decreasing \(h\) both help.

Intermediate symbols remember the head and the last generated sibling: ⟨VP:[VBZ]⟩ → VBZ; ⟨VP:[VBZ]…NP⟩ → ⟨VP:[VBZ]⟩ NP; ⟨VP:[VBZ]…PP⟩ → ⟨VP:[VBZ]…NP⟩ PP; VP → ⟨VP:[VBZ]…PP⟩. These are ordinary PCFG rules.

More vertical history helped, even exhaustive grandparent annotation, while for horizontal history a variable-order second-order model (\(h \le 2\)) was best. Best cell: \(v = 3\), \(h \le 2\), 79.74 F1 vs 72.62 for the raw grammar. Further work used \(v \le 2\), \(h \le 2\) (77.77 F1), the best compromise of grammar size and useful history.

External annotation (marked ^X) records a feature of a node’s environment that influences its expansion, like parent annotation. Internal annotation (marked -X) records a feature of the node’s hidden contents that influences its distribution, like head lexicalization (a radical case).

UNARY-INTERNAL marks nodes with a single child, so unary rewrites are confined to contexts where they occur (+0.55 F1 alone). Marking only-child tags captures distributional distinctions the Penn tags conflate: demonstratives (that, those) vs determiners (the, a), and e.g. as well vs also.

Parent annotation of preterminal tags, the best single annotation (+2.52 F1 alone). Tags in non-canonical positions behave differently: the most common adverbs under ADVP are also and now, under VP n’t and not, under NP only and just.

IN conflates subordinating conjunctions (while, if), complementizers (that, for) and prepositions (of, in), which TAG-PA only partly separates. SPLIT-IN is a linguistically motivated 6-way split, e.g. letting if prefer S complements in “to see if advertising works”.

SPLIT-AUX marks all forms of be and have; SPLIT-CC marks but and &, which behave unlike other conjunctions; and % gets its own tag, like $. Together they reached 81.81 F1.

At function words vs content words: annotating phrasal nodes with closed-class distinctions (like CP[for], PP[to], or VP finiteness) is standard linguistic practice and allowed; using open-class words (NP[stocks]) for monolexical or bilexical probabilities is not.

With pure maximum-likelihood estimation and no interpolation to unsplit categories, detailed lexical splits make many sentences fail to parse or get weird parses; only a few distinctions with major distributional impact pay off. Even after lexeme splits the grammar had only 9255 states vs 7619 in the baseline.

Mostly not: keeping them dropped the raw grammar from 72.62 to 71.49 F1, and the markovized baseline from 77.77 to 72.87. But selected ones help: TMP-NP keeps -TMP on NPs and pushes it down to the head tag (so “CNN last night” isn’t parsed as a compound), and GAPPED-S marks S nodes with empty subjects.

POSS-NP marks possessive NPs, which have a very different distribution (NP → NP α is only used with a possessive left child). SPLIT-VP marks VPs with their head tag, merging finite forms into VBF, so finite and infinitival VPs differ (present-tense verbs rarely take bare infinitive complements). SPLIT-VP gave +2.66 F1, more than in isolation.

High and low attachments often use the same rules, and height or linear distance isn’t encoded in labels; marking yield sizes would explode the state space. Indirect indicators instead: BASE-NP marks NPs dominating only preterminals, DOMINATES-V marks nodes containing a verb, RIGHT-REC-NP marks NPs with an NP on their right periphery.

Collins (1999) also inserted a unary non-base NP above base NPs that lacked one; this erased a useful signal (base NPs are commoner in subject position) and cost 0.37 F1 in isolation. Marking base NPs without the unary gained 0.73.

Every chart item is a label over a span, e.g. NP[0,5], and a rule combines adjacent spans like NP[0,5] and VP[5,12] into S[0,12]; the span lengths are right there, yet only the labels are used in scoring.

On section 23 (sentences ≤ 40 words): LP 86.9, LR 85.7, F1 86.3, better than Magerman (1995) and Collins (1996) but below Charniak (1997) and Collins (1999, 88.7/88.6). Development F1 climbed from 77.77 (markovized baseline) to 87.04 through the annotations.

step	dev F1
raw treebank grammar	72.62
markovized, \(v \le 2\), \(h \le 2\)	77.77
+ unary marks, TAG-PA, SPLIT-IN	81.19
+ lexeme splits, TMP-NP, GAPPED-S, POSS-NP, SPLIT-VP	85.72
+ BASE-NP, DOMINATES-V, RIGHT-REC-NP	87.04

A compact maximum-likelihood unlexicalized PCFG can match early lexicalized parsers; the necessity of lexical selection had been overstated. Their annotations are partly easier than lexicalization and partly orthogonal to it, so lexicalized parsers could use them too, and they affirm the value of linguistic analysis for feature discovery.