Overview

Reading

Chandlee (2017) on the complexity of morphological maps and Jurafsky and Martin (2023) on context-free grammars and parsing.

The previous module separated two kinds of finite state object: FSAs describe languages of strings, while FSTs describe relations between strings. Many morphological maps—including prefixation, suffixation, and bounded copying—are subsequential or otherwise finite state (Chandlee 2017). Unrestricted total reduplication is not. So what do we need beyond a finite-state map?

That boundary does not, by itself, motivate the formalism we use in this module. Our immediate problem is morphological constituency: morphemes form nested units, and different nestings may correspond to different interpretations. The word unlockable, for instance, permits both $[\text{un}[\text{lock-able}]]$ and $[[\text{un-lock}]\text{-able}]$. A flat segmentation identifies the same three morphemes in both analyses but does not distinguish their structures.

We will treat segmentation and parsing as separate tasks. A segmenter finds the morpheme-like units in a word; a parser determines how those units compose. Sequence models such as HMMs and CRFs will handle the first task. Context-free grammars and their probabilistic extensions will handle the second. We start with the second task so that we can say exactly what kind of structure the parser must recover.

The formalism we’ll use for this is the context-free grammar (CFG). A context-free grammar is a 4-tuple $G = (V, \Sigma, R, S)$ where:

$V$ is a finite set of variables (or nonterminals)
$\Sigma$ is a finite set of terminals (the alphabet—in our case, morphemes)
$R \subseteq V \times (V \cup \Sigma)^*$ is a finite set of rules (or productions) of the form $A \rightarrow \alpha$, where $A \in V$ and $\alpha \in (V \cup \Sigma)^*$
$S \in V$ is the start variable

The left side of every rule contains exactly one variable. Thus, whether $A \rightarrow \alpha$ may apply depends on $A$, not on the symbols surrounding it. This is the sense in which the grammar is context-free.

Define Rule and ContextFreeGrammar

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

To make this concrete, here is a simple morphological grammar for a fragment of English derivational morphology:

grammar = ContextFreeGrammar(
    alphabet={'happy', 'un', 'ness', 'kind', 'ly', 'help', 'ful'},
    variables={'Word', 'Adj', 'Adv', 'N', 'Prefix', 'Suffix'},
    rules={
        Rule('Adj', 'happy'),
        Rule('Adj', 'kind'),
        Rule('Adj', 'help', 'ful'),

        Rule('Word', 'Adj'),
        Rule('Word', 'Adv'),
        Rule('Word', 'N'),

        Rule('Adj', 'Prefix', 'Adj'),   # un + kind → unkind
        Rule('N', 'Adj', 'Suffix'),     # kind + ness → kindness
        Rule('Adv', 'Adj', 'Suffix'),   # kind + ly → kindly

        Rule('Prefix', 'un'),
        Rule('Suffix', 'ness'),
        Rule('Suffix', 'ly'),
        Rule('Suffix', 'ful'),
    },
    start_variable='Word'
)

for rule in sorted(grammar.rules(), key=lambda r: str(r)):
    print(rule)

This grammar can assign hierarchical analyses to unkind, kindness, and unkindly. It also illustrates a point that will recur: the alphabet contains the observed units, while the variables name the categories and constituents that the analysis posits.

So the module proceeds in three steps. We first work out how CFGs behave and how CKY and Earley recover their structures. We then look at the acceptability data and CELEX analyses. With those pieces in place, we compare sequence-based segmentation, supervised probabilistic grammars, and inside-outside estimation without gold parse trees.

References

Chandlee, Jane. 2017. “Computational Locality in Morphological Maps.” Morphology 27 (4): 599–641. https://doi.org/10.1007/s11525-017-9316-9.

Jurafsky, Daniel, and James H. Martin. 2023. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. 3rd ed. https://web.stanford.edu/~jurafsky/slp3/old_jan23/ed3book.pdf.

--- title: Overview bibliography: ../references.bib jupyter: python3 --- ::: {.callout-tip} ## Reading @Chandlee2017 on the complexity of morphological maps and @jurafsky_speech_2023 on context-free grammars and parsing. ::: The previous module separated two kinds of finite state object: FSAs describe languages of strings, while FSTs describe relations between strings. Many morphological maps—including prefixation, suffixation, and bounded copying—are subsequential or otherwise finite state [@Chandlee2017]. Unrestricted total reduplication is not. So what do we need beyond a finite-state map? That boundary does not, by itself, motivate the formalism we use in this module. Our immediate problem is **morphological constituency**: morphemes form nested units, and different nestings may correspond to different interpretations. The word *unlockable*, for instance, permits both $[\text{un}[\text{lock-able}]]$ and $[[\text{un-lock}]\text{-able}]$. A flat segmentation identifies the same three morphemes in both analyses but does not distinguish their structures. We will treat segmentation and parsing as separate tasks. A *segmenter* finds the morpheme-like units in a word; a *parser* determines how those units compose. Sequence models such as HMMs and CRFs will handle the first task. Context-free grammars and their probabilistic extensions will handle the second. We start with the second task so that we can say exactly what kind of structure the parser must recover. The formalism we'll use for this is the *context-free grammar* (CFG). A context-free grammar is a 4-tuple $G = (V, \Sigma, R, S)$ where: 1. $V$ is a finite set of *variables* (or *nonterminals*) 2. $\Sigma$ is a finite set of *terminals* (the alphabet—in our case, morphemes) 3. $R \subseteq V \times (V \cup \Sigma)^*$ is a finite set of *rules* (or *productions*) of the form $A \rightarrow \alpha$, where $A \in V$ and $\alpha \in (V \cup \Sigma)^*$ 4. $S \in V$ is the *start variable* The left side of every rule contains exactly one variable. Thus, whether $A \rightarrow \alpha$ may apply depends on $A$, not on the symbols surrounding it. This is the sense in which the grammar is *context-free*. ```{python} #| code-fold: true #| code-summary: Define `Rule` and `ContextFreeGrammar` import sys sys.path.insert(0, '_code') from grammar import Rule, ContextFreeGrammar ``` To make this concrete, here is a simple morphological grammar for a fragment of English derivational morphology: ```{python} grammar = ContextFreeGrammar( alphabet={'happy', 'un', 'ness', 'kind', 'ly', 'help', 'ful'}, variables={'Word', 'Adj', 'Adv', 'N', 'Prefix', 'Suffix'}, rules={ Rule('Adj', 'happy'), Rule('Adj', 'kind'), Rule('Adj', 'help', 'ful'), Rule('Word', 'Adj'), Rule('Word', 'Adv'), Rule('Word', 'N'), Rule('Adj', 'Prefix', 'Adj'), # un + kind → unkind Rule('N', 'Adj', 'Suffix'), # kind + ness → kindness Rule('Adv', 'Adj', 'Suffix'), # kind + ly → kindly Rule('Prefix', 'un'), Rule('Suffix', 'ness'), Rule('Suffix', 'ly'), Rule('Suffix', 'ful'), }, start_variable='Word' ) for rule in sorted(grammar.rules(), key=lambda r: str(r)): print(rule) ``` This grammar can assign hierarchical analyses to *unkind*, *kindness*, and *unkindly*. It also illustrates a point that will recur: the alphabet contains the observed units, while the variables name the categories and constituents that the analysis posits. So the module proceeds in three steps. We first work out how CFGs behave and how CKY and Earley recover their structures. We then look at the acceptability data and CELEX analyses. With those pieces in place, we compare sequence-based segmentation, supervised probabilistic grammars, and inside-outside estimation without gold parse trees.