CKY Scoring, Evaluation, and Shallow Parsing

This builds on constituency parsing, which developed the context-free grammar, the structural ambiguity that gives one sentence many trees, and the CKY chart that recovers all of them in one cubic-time pass. CKY recovers all parses but does not rank them. Picking the right tree out of the many it produces, and measuring how well a parser does, is where we pick up.

From all parses to the right one

CKY hands back every parse; it does not say which is correct. Disambiguation needs a score on trees. The classical answer is the probabilistic CFG (PCFG): attach to each rule $A\to \beta$ a probability $P(\beta \mid A)$, with the probabilities of all expansions of a given $A$ summing to one.¹ The probability of a parse tree $T$ is the product of the rule probabilities used to build it,

and the best parse of a sentence is $\hat{T}=\arg {\max }_{T}P(T)$. A small change to CKY turns it into the parser that finds $\hat{T}$: each cell stores, for each nonterminal, the maximum-probability subtree spanning that cell, taking a max over split points instead of a union. The recurrence for the best score of nonterminal $A$ over span $[i,j]$ is

the same triangular fill, now carrying a probability and a back-pointer to the winning $(B,C,k)$.

Plain PCFGs are weak because the independence assumption is too strong: the probability of VP → Verb NP PP should depend on which verb, but the rule probability ignores the words. Lexicalization fixes this by annotating every nonterminal with its lexical head — the grammatically central word it dominates (N heads an NP, V heads a VP). A rule then reads VP(dumped) → VBD(dumped) NP(sacks) PP(into), and the probabilities can capture that dumped prefers a PP(into) complement. Heads propagate up the tree: each node inherits the head of its designated head child.²

Span-based neural parsing

Modern parsers drop the hand-written grammar's role in scoring and let a neural network score constituents directly.³ A span is a stretch between fenceposts $i$ and $j$ with a candidate label $l$; a classifier assigns it a score $s(i,j,l)$. The tokens are embedded by a pretrained encoder such as BERT, each fencepost is represented by a forward and a backward half-vector, and a span is encoded by differencing its endpoints,

which a small MLP maps to a score per possible label. A tree $T$ is a set of labeled spans, and its score is the sum over its spans,

The best tree is found with the same CKY recursion, now maximizing summed span scores: for length-one spans $s_{\text{best}}(i,i+1)={\max }_{l}s(i,i+1,l)$, and for longer spans

The grammar's job — constraining which constituents may combine — is gone; the neural model learns those constraints from data instead. The chart machinery is unchanged; only the source of the scores is different.

Beyond the chart: self-attentive parsing and its results

The span-based parser above sketches the idea; the named work that made it the state of the art fixes where the span scores come from and how the model is trained. Three public papers trace the line; their measured numbers quantify the gain over the classical PCFG.

From RNN spans to a self-attentive encoder (Stern 2017; Kitaev and Klein, 2018)

The minimal-span parser of Stern, Andreas, and Klein (ACL 2017) established the approach: score every labeled span with a neural network, then run a CKY-style chart to assemble the highest-scoring tree, trained with a margin objective that pushes the gold tree's score above every wrong tree by a margin. It reached about $91.8$ labeled $F_1$ on the Penn Treebank Wall Street Journal test set, already competitive with the best lexicalized PCFGs without any explicit grammar.

Kitaev and Klein (ACL 2018) replaced the recurrent span encoder with a self-attentive encoder — a transformer stack — and found two design points that mattered. First, factoring the attention into separate content and position streams sharpened the span representations. Second, and more surprising, the parser improved when it was prevented from mixing content and position information too freely in early layers. On the same WSJ test set the self-attentive parser reached about $93.6$$F_1$; adding ELMo contextual word representations pushed it near $95.1$. The follow-up (Kitaev, Cao, and Klein, ACL 2019) swapped in BERT as the encoder and reported roughly $95.6$ $F_1$ on English, and — using a single multilingual model — strong results across ten languages at once, showing the span-scoring recipe is not English-specific.

Why the grammar could be dropped

The classical picture in this lesson makes the grammar do two jobs: it constrains which constituents may combine (an NP and a VP make an S, a Det and a Nominal make an NP), and a PCFG's rule probabilities score how likely each combination is. The neural parser drops the first job entirely — its chart allows any label on any span — and folds the second into learned span scores. What replaces the grammar's constraints is the encoder's context: a self-attentive representation of a span already encodes whether the surrounding words make an NP plausible there, so the model rarely proposes an incoherent tree even without a rule forbidding it. Gaddy, Stern, and Klein (NAACL 2018) observed that a greedy per-span labeling forms a valid tree about $95\%$ of the time, which is why the CKY step, though still used to guarantee a tree, matters less than it did for the hand-written grammar. The optimal-substructure argument that makes CKY correct is untouched; the source of the per-span evidence moved from counts over rules to a transformer over words.⁴

Evaluating parsers with PARSEVAL

To score a parser we compare its trees against gold trees from a treebank, using PARSEVAL.⁵ A constituent in the hypothesis is correct if the reference tree has a constituent with the same start point, end point, and nonterminal label. From that we compute the same precision and recall as in any tagging task:

reported together as their harmonic mean $F_1=\frac{2\text{P}\text{R}}{\text{P}+\text{R}}$. A third metric, crossing brackets, counts constituents where the hypothesis brackets as $(A(BC))$ but the reference brackets as $((AB)C)$ — groupings that are structurally incompatible rather than merely missing.

Work a small case. Suppose the reference tree has 7 labeled constituents and the parser's hypothesis has 6, of which 5 match a reference constituent exactly (same span, same label). Then precision is $5/6\approx 0.83$, recall is $5/7\approx 0.71$, and

The canonical PARSEVAL implementation is evalb, which also applies a canonicalization step that strips grammar-specific details (auxiliaries, pre-infinitival to) so parsers built on different grammars can be compared fairly.

Chunking and shallow parsing

A full CKY parse is often more than a task needs. Many applications never use the deep hierarchy, only the flat phrases near the leaves — and recovering just those is far cheaper and far more robust than building the whole tree.⁶ A partial parse (or shallow parse) does exactly that: it identifies and classifies the basic phrases of a sentence without nesting them into a complete structure. Information-extraction systems, for instance, do not need every constituent; they need the noun phrases that name entities and little else.

Chunking

The standard form of shallow parsing is chunking: segmenting a sentence into flat, non-overlapping phrases that correspond to the major content parts-of-speech — noun phrases, verb phrases, adjective phrases, prepositional phrases.⁷ A chunk is a base (non-recursive) phrase: it never contains another phrase of its own type. Because chunks do not nest, a simple bracketing notation suffices — no tree needed:

[NP The morning flight] [PP from] [NP Denver] [VP has arrived.]

Chunking involves two coupled tasks, visible in that bracketing: segmenting, finding the non-overlapping extents of the chunks, and labeling, assigning each discovered chunk its phrase type. The most common special case is base-NP chunking — finding just the base noun phrases and ignoring everything else. There, some words belong to no chunk at all:

[NP The morning flight] from [NP Denver] has arrived.

What counts as a base phrase depends on the application, but one guideline holds almost everywhere: a base phrase includes its headword and any pre-head material, but excludes all post-head modifiers. Dropping post-head material is what avoids the attachment ambiguities that made full parsing hard — there is no PP to attach high or low, because the PP is its own separate chunk. This does produce oddities: prepositional and verb phrases often shrink to just their heads. The phrase a flight from Indianapolis to Houston chunks flat as

[NP a flight] [PP from] [NP Indianapolis] [PP to] [NP Houston]

where each PP is a bare preposition and the noun phrases it would have contained stand alone.

BIO tagging for chunks

Chunking is a segmentation problem, and the standard way to cast segmentation as a tagging problem — one label per token — is BIO tagging.⁸ Each chunk type gets two tags: B-type marks the beginning of a chunk, I-type marks a token inside the same chunk, and a single O marks tokens outside any chunk. A supervised sequence labeler then learns to emit these tags token by token. The bracketed sentence above becomes, with every chunk type tagged:

The O tag matters when only some phrases are wanted. In base-NP chunking, every non-NP word is simply O, so the same sentence tagged for base noun phrases alone reads:

Training and using a chunker

Chunking is done by supervised learning: train a BIO sequence labeler — a CRF, RNN, or Transformer — on annotated data, exactly the machinery used for part-of-speech tagging and named-entity recognition.⁷ Hand-annotating chunks is expensive, so training data is usually extracted from an existing treebank like the Penn Treebank: read the full parse, find each phrase's head with head-finding rules, keep the head and the material to its left, and discard the material to its right. This is somewhat error-prone, since it inherits any mistakes in the head-finding rules. A trained chunker is scored the same way as any tagger, by comparing its output against gold-standard human chunks with precision, recall, and $F_1$ over the discovered chunks.

Shallow parsing suffices exactly when the downstream task needs which phrases are present and where, but not how they combine — entity extraction, keyword and noun-phrase indexing, and quick approximations of syntactic structure. When the task turns on how phrases relate (which argument attaches to which verb, what modifies what), the flat chunk view is not enough and a full parse, or the dependency parse of the next lesson, is needed.