--- title: "CKY Scoring, Evaluation, and Shallow Parsing" module: Linguistic Structure moduleNumber: 6 lessonNumber: 2 order: 602 summary: > The CKY chart returns every parse but does not say which is correct. Disambiguation needs a score on trees. This lesson attaches probabilities to a grammar (the PCFG and lexicalization), replaces the grammar with a neural span scorer over a pretrained encoder, states the self-attentive results that made it the state of the art, evaluates parsers against a treebank with PARSEVAL, and closes with chunking and shallow parsing for tasks that need only the flat phrases. topics: [Structure] sources: - book: Jurafsky ref: "Ch. 13 — Constituency Parsing; §13.3 Span-Based Neural Parsing; §13.4 Evaluating Parsers (PARSEVAL)" - book: Jurafsky ref: "§13.5 Partial Parsing (chunking, base-NP, BIO tagging)" --- This builds on [constituency parsing](/natural-language-processing/linguistic-structure/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 \rightarrow \beta$ a probability $P(\beta \mid A)$, with the probabilities of all expansions of a given $A$ summing to one.[^jm-pcfg] The probability of a parse tree $T$ is the product of the rule probabilities used to build it, $$ P(T) = \prod_{A \rightarrow \beta \, \in \, T} P(\beta \mid A), $$ 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 $$ \pi[i,j,A] = \max_{A \rightarrow B\,C} \; \max_{i < k < j} \; P(B\,C \mid A) \cdot \pi[i,k,B] \cdot \pi[k,j,C], $$ the same triangular fill, now carrying a probability and a back-pointer to the winning $(B, C, k)$. $$ % caption: A probabilistic CFG attaches a probability to each expansion of a % nonterminal (the numbers on each VP rule sum to 1). The parse probability is the % product of the rule probabilities used; probabilistic CKY keeps the max-scoring % subtree per cell. \begin{tikzpicture}[>=stealth, font=\footnotesize, rule/.style={draw, minimum width=44mm, minimum height=8mm, align=center, inner sep=3pt}] \definecolor{acc}{HTML}{2348F2} \node[rule, draw=acc, text=acc] (h) at (0,2.7) {VP: the three expansions}; \node[rule] (r1) at (0,1.5) {VP $\to$ Verb NP}; \node[rule] (r2) at (0,0.4) {VP $\to$ Verb NP PP}; \node[rule] (r3) at (0,-0.7) {VP $\to$ VP PP}; \node[anchor=west, font=\footnotesize] at (2.9,1.5) {0.55}; \node[anchor=west, font=\footnotesize] at (2.9,0.4) {0.30}; \node[anchor=west, font=\footnotesize] at (2.9,-0.7) {0.15}; \draw[->, acc, thick] (h.south) -- (r1.north); \draw[black, dashed] (1.9,-1.35) -- (3.55,-1.35); \node[anchor=west, font=\footnotesize, text=acc] at (2.5,-1.7) {sum = 1.00}; \end{tikzpicture} $$ 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.[^jm-lexicalized] $$ % caption: A lexicalized parse tree: every nonterminal carries its lexical head % word in parentheses. The head propagates up from the head child, so S(dumped) % inherits its head from VP(dumped), which inherits from the verb. \begin{tikzpicture}[>=stealth, font=\footnotesize, level distance=10mm, every node/.style={inner sep=1.6pt}, level 1/.style={sibling distance=48mm}, level 2/.style={sibling distance=30mm}, level 3/.style={sibling distance=22mm}] \definecolor{acc}{HTML}{2348F2} \node[text=acc] {S(dumped)} child { node {NP(workers)} child { node {\textit{workers}} } } child { node {VP(dumped)} child { node {VBD(dumped)} child { node {\textit{dumped}} } } child { node {NP(sacks)} child { node {\textit{sacks}} } } child { node {PP(into)} child { node {P(into)} child { node {\textit{into}} } } child { node {NP(bin)} child { node {\textit{a bin}} } } } }; \end{tikzpicture} $$ ## Span-based neural parsing Modern parsers drop the hand-written grammar's role in scoring and let a neural network score constituents directly.[^jm-neural] 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](/natural-language-processing/transformers/large-language-models), each fencepost is represented by a forward and a backward half-vector, and a span is encoded by differencing its endpoints, $$ v(i,j) = \big[\, \overrightarrow{y}_j - \overrightarrow{y}_i \; ; \; \overleftarrow{y}_{j+1} - \overleftarrow{y}_{i+1} \,\big], $$ 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, $$ s(T) = \sum_{(i,j,l) \, \in \, T} s(i,j,l), \qquad \hat{T} = \arg\max_{T} s(T). $$ $$ % caption: Span-based neural parsing. An encoder embeds the words; each span (i, j) % is scored per label by an MLP; a CKY-style recursion combines span scores into % the best tree. The grammar's constraining role is replaced by the learned scores. \begin{tikzpicture}[>=stealth, font=\footnotesize, box/.style={draw, minimum width=22mm, minimum height=9mm, align=center}] \definecolor{acc}{HTML}{2348F2} \node[box] (enc) at (0,0) {encoder\\(BERT)}; \node[box] (span) at (3.6,0) {span\\encoding}; \node[box] (mlp) at (7.2,0) {MLP score\\s(i, j, l)}; \node[box, draw=acc, text=acc, thick] (cky) at (10.8,0) {CKY over\\span scores}; \draw[->, acc, thick] (enc) -- (span); \draw[->, acc, thick] (span) -- (mlp); \draw[->, acc, thick] (mlp) -- (cky); \node[font=\scriptsize, anchor=north] at (0,-0.75) {words in}; \node[font=\scriptsize, anchor=north, text=acc] at (10.8,-0.75) {best tree out}; \end{tikzpicture} $$ 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 $$ s_{\text{best}}(i,j) = \max_l s(i,j,l) \; + \; \max_{i < k < j} \big[\, s_{\text{best}}(i,k) + s_{\text{best}}(k,j) \,\big]. $$ 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. $$ % caption: Labeled F1 on the Penn Treebank WSJ test set as the span encoder changed: % classical lexicalized PCFG (~90), Stern et al. RNN spans (~91.8), Kitaev-Klein % self-attentive (~93.6), with ELMo (~95.1), with BERT (~95.6). The chart recursion % is unchanged; only the encoder feeding the span scores improves. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \draw[->, black] (0,0) -- (0,4.4) node[above, black, font=\scriptsize] {WSJ F1}; \draw[black] (-0.1,0.5) -- (0.1,0.5) node[left, black, font=\scriptsize, xshift=-2mm] {90}; \draw[black] (-0.1,3.5) -- (0.1,3.5) node[left, black, font=\scriptsize, xshift=-2mm] {96}; % bars: map F1 in [90,96] to y in [0.5,3.5]; scale (F1-90)*0.5+0.5 \foreach \x/\f/\lab in {0.9/90.0/{PCFG}, 2.5/91.8/{RNN spans}, 4.1/93.6/{self-attn}, 5.7/95.1/{+ELMo}, 7.3/95.6/{+BERT}} { \fill[acc!22, draw=acc] (\x-0.35,0) rectangle (\x+0.35,{(\f-90)*0.5+0.5}); \node[anchor=north, font=\scriptsize] at (\x,-0.05) {\lab}; \node[anchor=south, font=\scriptsize, text=acc] at (\x,{(\f-90)*0.5+0.5}) {\f}; } \end{tikzpicture} $$ ### 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.[^neural-parse] ## Evaluating parsers with PARSEVAL To score a parser we compare its trees against gold trees from a treebank, using **PARSEVAL**.[^jm-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: $$ \text{P} = \frac{\#\ \text{correct constituents in hypothesis}}{\#\ \text{constituents in hypothesis}}, \qquad \text{R} = \frac{\#\ \text{correct constituents in hypothesis}}{\#\ \text{constituents in reference}}, $$ reported together as their harmonic mean $F_1 = \dfrac{2\,\text{P}\,\text{R}}{\text{P} + \text{R}}$. A third metric, **crossing brackets**, counts constituents where the hypothesis brackets as $(A\,(B\,C))$ but the reference brackets as $((A\,B)\,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 $$ F_1 = \frac{2 \cdot 0.83 \cdot 0.71}{0.83 + 0.71} \approx 0.77. $$ $$ % caption: PARSEVAL on a worked example. Of 6 hypothesis constituents, 5 match a % reference constituent exactly (span + label); the reference has 7. Precision = % 5/6, recall = 5/7, F1 ~ 0.77. The unmatched brackets are the errors. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % hypothesis column \node[font=\small, text=acc] at (0,3.1) {hypothesis (6)}; \foreach \y in {2.4,1.8,1.2,0.6,0} \fill[acc] (0,\y) circle (2.6pt); \draw[red, thick] (0,-0.6) ++(-3pt,-3pt) -- ++(6pt,6pt); \draw[red, thick] (0,-0.6) ++(-3pt,3pt) -- ++(6pt,-6pt); % reference column \node[font=\small] at (5,3.1) {reference (7)}; \foreach \y in {2.4,1.8,1.2,0.6,0,-0.6,-1.2} \fill[black] (5,\y) circle (2.6pt); % match lines for the 5 correct \foreach \y in {2.4,1.8,1.2,0.6,0} \draw[acc] (0.15,\y) -- (4.85,\y); % labels \node[anchor=west, font=\scriptsize, text=red] at (0.25,-0.6) {unmatched}; \node[anchor=west, font=\scriptsize] at (5.25,-0.6) {missed}; \node[anchor=west, font=\scriptsize] at (5.25,-1.2) {missed}; % score box \node[draw=acc, text=acc, align=left, anchor=west, minimum height=13mm] at (7.2,1.1) {P = 5/6 = 0.83\\ R = 5/7 = 0.71\\ F1 = 0.77}; \end{tikzpicture} $$ 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.[^jm-partial] 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.[^jm-chunk] 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: ```text [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: ```text [NP The morning flight] from [NP Denver] has arrived. ``` $$ % caption: A chunked sentence. Chunks are flat, non-overlapping base phrases: each % noun phrase (NP), the preposition (PP), and the verb phrase (VP) is a single % bracket with no nesting. Compare a full parse tree, which would nest these % phrases into a hierarchy. \begin{tikzpicture}[>=stealth, font=\footnotesize, chunk/.style={draw, minimum height=8mm, align=center, inner sep=4pt}, npc/.style={chunk, draw=acc, text=acc}, ppc/.style={chunk}, vpc/.style={chunk}] \definecolor{acc}{HTML}{2348F2} \node[npc] (a) at (0,0) {The morning f\/light}; \node[ppc] (b) at (3.25,0) {from}; \node[npc] (c) at (4.75,0) {Denver}; \node[vpc] (d) at (7.2,0) {has arrived}; \node[text=acc, font=\scriptsize, anchor=north] at (0,-0.55) {NP}; \node[font=\scriptsize, anchor=north] at (3.25,-0.55) {PP}; \node[text=acc, font=\scriptsize, anchor=north] at (4.75,-0.55) {NP}; \node[font=\scriptsize, anchor=north] at (7.2,-0.55) {VP}; \end{tikzpicture} $$ 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 ```text [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**.[^jm-bio] 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: $$ % caption: BIO tags for full chunking. Each token gets B- (begin) or I- (inside) % of a chunk type, so "The morning flight" is B-NP I-NP I-NP. The tag changes to % B-PP at "from" and B-VP I-VP over "has arrived", marking each chunk boundary. \begin{tikzpicture}[>=stealth, font=\footnotesize, wtok/.style={align=center, font=\footnotesize}, tag/.style={draw, minimum width=13mm, minimum height=7mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\w in {0/The, 1/morning, 2/f\/light, 3/from, 4/Denver, 5/has, 6/arrived} \node[wtok] (w\i) at (\i*1.85,0.75) {\w}; \foreach \i/\t in {0/B-NP, 1/I-NP, 2/I-NP, 3/B-PP, 4/B-NP, 5/B-VP, 6/I-VP} \node[tag] (t\i) at (\i*1.85,0) {\t}; \foreach \i in {0,1,2,3,4,5,6} \draw[->, acc] (w\i.south) -- (t\i.north); \end{tikzpicture} $$ 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: $$ % caption: BIO tags for base-NP chunking only. Now only noun phrases are marked; % "from", "has", and "arrived" fall outside any chunk and receive O. The B-/I- % distinction still marks where each NP starts and continues. \begin{tikzpicture}[>=stealth, font=\footnotesize, wtok/.style={align=center, font=\footnotesize}, tag/.style={draw, minimum width=12mm, minimum height=7mm, align=center, font=\scriptsize}, otag/.style={draw, minimum width=12mm, minimum height=7mm, align=center, font=\scriptsize, text=black}] \definecolor{acc}{HTML}{2348F2} \foreach \i/\w in {0/The, 1/morning, 2/f\/light, 3/from, 4/Denver, 5/has, 6/arrived} \node[wtok] (w\i) at (\i*1.85,0.75) {\w}; \node[tag] (t0) at (0,0) {B-NP}; \node[tag] (t1) at (1.85,0) {I-NP}; \node[tag] (t2) at (3.7,0) {I-NP}; \node[otag] (t3) at (5.55,0) {O}; \node[tag] (t4) at (7.4,0) {B-NP}; \node[otag] (t5) at (9.25,0) {O}; \node[otag] (t6) at (11.1,0) {O}; \foreach \i in {0,1,2,3,4,5,6} \draw[->, acc] (w\i.south) -- (t\i.north); \end{tikzpicture} $$ ### 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.[^jm-chunk] 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](/natural-language-processing/linguistic-structure/dependency-parsing) of the next lesson, is needed. [^jm-pcfg]: **Jurafsky & Martin**, §13.1 and Appendix C — probabilistic context-free grammars: rule probabilities, the most-probable parse, and probabilistic CKY. [^jm-lexicalized]: **Jurafsky & Martin**, §12.4.3 and §12.6 — Heads and Head Finding; Lexicalized Grammars: annotating nonterminals with lexical heads and the head child that propagates the head upward. [^jm-neural]: **Jurafsky & Martin**, §13.3 — Span-Based Neural Constituency Parsing: scoring spans with a neural classifier over a pretrained encoder, the span representation, and a CKY variant that combines span scores. [^neural-parse]: Neural constituency parsers. **Stern, Andreas, and Klein**, "A Minimal Span-Based Neural Constituency Parser," _ACL_ (2017) — the span-scoring plus chart-assembly recipe with a margin-based training objective (~91.8 WSJ $F_1$). **Kitaev and Klein**, "Constituency Parsing with a Self-Attentive Encoder," _ACL_ (2018) — a transformer encoder over spans with factored content/position attention (~93.6 $F_1$, ~95.1 with ELMo). **Kitaev, Cao, and Klein**, "Multilingual Constituency Parsing with Self-Attention and Pre-Training," _ACL_ (2019) — a BERT encoder (~95.6 $F_1$ English) and a single multilingual model across ten languages. **Gaddy, Stern, and Klein**, "What's Going On in Neural Constituency Parsers? An Analysis," _NAACL_ (2018) — greedy per-span labeling forms a valid tree ~95% of the time. The reported $F_1$ figures are approximate and drawn from these papers' Penn Treebank evaluations. [^jm-parseval]: **Jurafsky & Martin**, §13.4 — Evaluating Parsers: PARSEVAL labeled precision, recall, and $F_1$ over constituents, crossing brackets, and `evalb`. [^jm-partial]: **Jurafsky & Martin**, §13.5 — Partial Parsing: partial / shallow parses as a cheaper alternative to full trees, and their use in information extraction, which identifies segments likely to hold valuable information rather than parsing everything. [^jm-chunk]: **Jurafsky & Martin**, §13.5 — Chunking: flat, non-overlapping base (non-recursive) phrases; the segmenting-and-labeling split; base-NP chunking; base phrases keep the head plus pre-head material and drop post-head modifiers (avoiding attachment ambiguity); training a supervised labeler, extracting chunks from a treebank, and evaluating with precision, recall, and $F_1$. [^jm-bio]: **Jurafsky & Martin**, §13.5 (and Ch. 8) — BIO tagging for chunks: a **B**-_type_ tag beginning each chunk, **I**-_type_ inside it, and **O** for tokens outside any chunk, casting chunking as per-token sequence labeling.