Segmentation as structured prediction

Reading

Rabiner (1989) on hidden Markov models, Lafferty et al. (2001) on conditional random fields, and Jurafsky and Martin (2023, Ch. 8) on sequence labeling.

BPE learns an ordered list of substring merges, but it never sees a gold morpheme boundary. What changes if those boundaries are available during training? We can treat segmentation as boundary tagging: the model assigns a label to every character, and the label sequence determines the segmentation.

For fully segmented words, two labels suffice. B marks the beginning of a morpheme and I marks every later character inside it.

u	n	h	a	p	p	i	n	e	s	s
B	I	B	I	I	I	I	B	I	I	I

The table encodes $\langle\text{un},\text{happi},\text{ness}\rangle$. An O label is useful when some characters may fall outside any segment, but that case does not arise here.

from collections.abc import Sequence
from typing import Literal

type BoundaryTag = Literal["B", "I"]


def morphemes_to_tags(
    morphemes: Sequence[str],
) -> list[BoundaryTag]:
    """Convert a sequence of morphemes to character-level BI tags."""
    tags: list[BoundaryTag] = []
    for morpheme in morphemes:
        if not morpheme:
            raise ValueError("morphemes must be nonempty")
        tags.append("B")
        tags.extend("I" for _ in morpheme[1:])
    return tags


def tags_to_morphemes(
    word: str,
    tags: Sequence[BoundaryTag],
) -> list[str]:
    """Decode a valid BI tag sequence into morphemes."""
    if len(word) != len(tags):
        raise ValueError("word and tags must have the same length")
    if not word:
        return []
    if tags[0] != "B":
        raise ValueError("a nonempty BI sequence must begin with B")
    if any(tag not in ("B", "I") for tag in tags):
        raise ValueError("tags must contain only B and I")

    morphemes: list[str] = []
    start = 0
    for index, tag in enumerate(tags[1:], start=1):
        if tag == "B":
            morphemes.append(word[start:index])
            start = index
    morphemes.append(word[start:])
    return morphemes

The valid-sequence condition is part of the representation: the empty word has the empty tag sequence, and every nonempty word begins with B. Thus, morphemes_to_tags([]) returns [], while tags_to_morphemes rejects a nonempty sequence beginning with I. On valid inputs, the two functions are inverses because each B marks exactly one substring start and every character belongs to the substring begun by the most recent B.

assert morphemes_to_tags([]) == []
assert tags_to_morphemes("", []) == []
assert tags_to_morphemes("unhappiness", morphemes_to_tags(
    ["un", "happi", "ness"]
)) == ["un", "happi", "ness"]

try:
    tags_to_morphemes("un", ["I", "I"])
except ValueError:
    pass
else:
    raise AssertionError("a nonempty BI sequence cannot begin with I")

An HMM tagger

An HMM models the joint probability of characters $\mathbf{x}$ and tags $\mathbf{y}$:

\[ p(\mathbf{x},\mathbf{y}) =p(y_1)p(x_1\mid y_1) \prod_{i=2}^n p(y_i\mid y_{i-1})p(x_i\mid y_i). \]

The transition distribution captures which boundary labels tend to follow one another; the emission distribution captures which characters tend to occur under each label. Viterbi decoding finds the most probable tag sequence for an observed word in $O(n|Y|^2)$ time (Viterbi 1967).

Why the Viterbi recurrence finds the best tag sequence

Why does this recurrence find the best complete tag sequence rather than merely the best tag at each position? Fix a nonempty observed word $x_1\cdots x_n$ and a finite tag set $Y$. For a position $i$ and tag $y$, define

\[ \delta_i(y) =\max_{y_1,\ldots,y_{i-1}} p(y_1)p(x_1\mid y_1) \prod_{j=2}^{i}p(y_j\mid y_{j-1})p(x_j\mid y_j), \]

where $y_i=y$. Thus, $\delta_i(y)$ is intended to be the probability of the best tag sequence for the prefix $x_1\cdots x_i$ that ends in $y$. We call this statement the Viterbi invariant.

At the first character, there is only one valid length-one BI sequence: B. We enforce this constraint with $p(B)=1$ and $p(I)=0$, so

\[ \delta_1(y)=p(y)p(x_1\mid y). \]

The base case follows. Now fix $i>1$ and suppose that the invariant holds at $i-1$. Any sequence ending in tag $y$ at position $i$ has some preceding tag $y'$. Its probability is the probability of its prefix through $i-1$, multiplied by $p(y\mid y')p(x_i\mid y)$. For a fixed $y'$, the induction hypothesis tells us that no prefix ending in $y'$ has probability greater than $\delta_{i-1}(y')$, and that some prefix attains this value. It follows that

\[ \delta_i(y) =p(x_i\mid y) \max_{y'\in Y} \delta_{i-1}(y')p(y\mid y'). \]

Both directions now follow. Every candidate in the maximum extends a real prefix and is thus a real tag sequence; conversely, every tag sequence ending in $y$ appears under the candidate corresponding to its penultimate tag. Recording the maximizing $y'$ as a backpointer preserves the sequence that attains each value.

After position $n$, every complete tag sequence ends in exactly one $y\in Y$. Thus, $\max_y\delta_n(y)$ is the probability of the globally best sequence, and following the stored backpointers reconstructs that sequence from right to left. The empty-word case does not enter the recurrence: its decoder returns [] before allocating a chart.

For a numeric trace, take the observed string unh and the two tags B and I. Set the initial probabilities to $p(B)=1$ and $p(I)=0$, and use the following transition and emission probabilities:

previous tag	next `B`	next `I`
`B`	.30	.70
`I`	.40	.60

tag	emit `u`	emit `n`	emit `h`
`B`	.50	.20	.30
`I`	.10	.50	.40

At position one, the base case gives $\delta_1(B)=1(.50)=.500$ and $\delta_1(I)=0(.10)=0$. For B at the second character, the recurrence compares both possible predecessors:

\[ \begin{aligned} \delta_2(B) &=.20\max\{.500(.30),0(.40)\}\\ &=.20\max\{.150,0\}=.030. \end{aligned} \]

The winning predecessor is B, so the backpointer for the state (2, B) points to (1, B). Repeating the comparison for every state gives the complete table:

position	character	$\delta_i(B)$	predecessor of `B`	$\delta_i(I)$	predecessor of `I`
1	`u`	.5000	start	.0000	start
2	`n`	.0300	`B`	.1750	`B`
3	`h`	.0210	`I`	.0420	`I`

For instance, the final I value is $.40\max\{.030(.70),.175(.60)\}=.0420$, and its winning predecessor is I. The final argmax compares $.0210$ for B with $.0420$ for I, so decoding ends in I at position three. Its backpointer leads to I at position two, whose backpointer leads to B at position one. Reversing that backward path reconstructs B I I, the highest-probability valid tag sequence for this example.

There are $n|Y|$ table entries. Computing one entry examines $|Y|$ predecessor tags and performs constant work for each, yielding $O(n|Y|^2)$ time. The table and its backpointers require $O(n|Y|)$ space; if only the best probability is needed, two adjacent columns suffice.

from collections.abc import Mapping

import numpy as np
from hmmlearn.hmm import CategoricalHMM
from numpy.typing import NDArray


def characters_to_observations(
    word: str,
    character_ids: Mapping[str, int],
) -> NDArray[np.int_]:
    """Encode a word in the shape expected by ``CategoricalHMM``."""
    observations = np.asarray(
        [character_ids[character] for character in word.lower()],
        dtype=int,
    )
    return observations.reshape(-1, 1)


latent_hmm = CategoricalHMM(n_components=2, n_iter=100)

assert characters_to_observations("", {}).shape == (0, 1)

CategoricalHMM(n_components=2) is an unlabeled latent-state model. Fitting it to character observations alone neither identifies which state is B nor enforces the B-initial constraint; exchanging the two state IDs gives an equivalent latent model. A supervised BI tagger must instead estimate its parameters from gold character-tag pairs, fix the state-to-tag mapping, and set its initial distribution to [1, 0], or implement the constrained Viterbi recurrence directly. The object above demonstrates the array shape expected by the library, not a trained BI segmenter.

The HMM’s emission at position $i$ depends on $y_i$ and $x_i$, not on the neighboring characters. It thus cannot directly express a feature such as “the current character is n and the preceding substring is un.” A conditional model can.

A CRF tagger

A linear-chain conditional random field (CRF) models $p(\mathbf{y}\mid\mathbf{x})$ directly (Lafferty et al. 2001):

\[ p(\mathbf{y}\mid\mathbf{x}) =\frac{1}{Z(\mathbf{x})} \exp\left( \sum_{i=1}^n\sum_k \lambda_k f_k(y_{i-1},y_i,\mathbf{x},i) \right). \]

Each feature function may inspect the label transition and any bounded property of the observed word. The normalizer $Z(\mathbf{x})$ sums the unnormalized scores of every label sequence for the same word.

For morphology, useful features include the current character, neighboring characters, character $n$-grams, and whether the position is word-initial or word-final.

type FeatureValue = str | bool
type CharacterFeatures = dict[str, FeatureValue]


def character_features(word: str, index: int) -> CharacterFeatures:
    """Return local segmentation features at ``index``."""
    features: CharacterFeatures = {
        "character": word[index],
        "is_vowel": word[index] in "aeiou",
        "is_first": index == 0,
        "is_last": index == len(word) - 1,
        "previous": word[index - 1] if index > 0 else "<START>",
        "following": (
            word[index + 1] if index + 1 < len(word) else "<END>"
        ),
    }

    if index > 0:
        features["left_bigram"] = word[index - 1:index + 1]
    if index + 1 < len(word):
        features["right_bigram"] = word[index:index + 2]
    return features


def word_features(word: str) -> list[CharacterFeatures]:
    """Return one feature mapping per character in ``word``."""
    return [character_features(word, index) for index in range(len(word))]

import sklearn_crfsuite

crf = sklearn_crfsuite.CRF(
    algorithm="lbfgs",
    max_iterations=100,
)

# features = [word_features(word) for word, _ in training_data]
# labels = [morphemes_to_tags(morphemes) for _, morphemes in training_data]
# crf.fit(features, labels)

The HMM and CRF both return a flat label sequence. The CRF can condition on richer observations, while the HMM provides a joint model with a more restrictive independence structure. Neither model supplies morphological constituency. That distinction sets up the probabilistic CFG: the segmenter proposes terminals, and the grammar assigns structures and probabilities to sequences of those terminals.

References

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.

Lafferty, John, Andrew McCallum, and Fernando C. N. Pereira. 2001. “Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data.” Proceedings of the 18th International Conference on Machine Learning, 282–89.

Rabiner, Lawrence R. 1989. “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” Proceedings of the IEEE 77 (2): 257–86. https://doi.org/10.1109/5.18626.

Viterbi, Andrew. 1967. “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm.” IEEE Transactions on Information Theory 13 (2): 260–69. https://doi.org/10.1109/TIT.1967.1054010.

--- title: Segmentation as structured prediction bibliography: ../references.bib jupyter: python3 execute: eval: false --- ::: {.callout-tip} ## Reading @rabiner_tutorial_1989 on hidden Markov models, @lafferty_conditional_2001 on conditional random fields, and @jurafsky_speech_2023[Ch. 8] on sequence labeling. ::: BPE learns an ordered list of substring merges, but it never sees a gold morpheme boundary. What changes if those boundaries are available during training? We can treat segmentation as **boundary tagging**: the model assigns a label to every character, and the label sequence determines the segmentation. For fully segmented words, two labels suffice. `B` marks the beginning of a morpheme and `I` marks every later character inside it. | u | n | h | a | p | p | i | n | e | s | s | |---|---|---|---|---|---|---|---|---|---|---| | B | I | B | I | I | I | I | B | I | I | I | The table encodes $\langle\text{un},\text{happi},\text{ness}\rangle$. An `O` label is useful when some characters may fall outside any segment, but that case does not arise here. ```{python} from collections.abc import Sequence from typing import Literal type BoundaryTag = Literal["B", "I"] def morphemes_to_tags( morphemes: Sequence[str], ) -> list[BoundaryTag]: """Convert a sequence of morphemes to character-level BI tags.""" tags: list[BoundaryTag] = [] for morpheme in morphemes: if not morpheme: raise ValueError("morphemes must be nonempty") tags.append("B") tags.extend("I" for _ in morpheme[1:]) return tags def tags_to_morphemes( word: str, tags: Sequence[BoundaryTag], ) -> list[str]: """Decode a valid BI tag sequence into morphemes.""" if len(word) != len(tags): raise ValueError("word and tags must have the same length") if not word: return [] if tags[0] != "B": raise ValueError("a nonempty BI sequence must begin with B") if any(tag not in ("B", "I") for tag in tags): raise ValueError("tags must contain only B and I") morphemes: list[str] = [] start = 0 for index, tag in enumerate(tags[1:], start=1): if tag == "B": morphemes.append(word[start:index]) start = index morphemes.append(word[start:]) return morphemes ``` The valid-sequence condition is part of the representation: the empty word has the empty tag sequence, and every nonempty word begins with `B`. Thus, `morphemes_to_tags([])` returns `[]`, while `tags_to_morphemes` rejects a nonempty sequence beginning with `I`. On valid inputs, the two functions are inverses because each `B` marks exactly one substring start and every character belongs to the substring begun by the most recent `B`. ```{python} assert morphemes_to_tags([]) == [] assert tags_to_morphemes("", []) == [] assert tags_to_morphemes("unhappiness", morphemes_to_tags( ["un", "happi", "ness"] )) == ["un", "happi", "ness"] try: tags_to_morphemes("un", ["I", "I"]) except ValueError: pass else: raise AssertionError("a nonempty BI sequence cannot begin with I") ``` ## An HMM tagger An HMM models the joint probability of characters $\mathbf{x}$ and tags $\mathbf{y}$: $$ p(\mathbf{x},\mathbf{y}) =p(y_1)p(x_1\mid y_1) \prod_{i=2}^n p(y_i\mid y_{i-1})p(x_i\mid y_i). $$ The transition distribution captures which boundary labels tend to follow one another; the emission distribution captures which characters tend to occur under each label. Viterbi decoding finds the most probable tag sequence for an observed word in $O(n|Y|^2)$ time [@viterbi_error_1967]. ### Why the Viterbi recurrence finds the best tag sequence Why does this recurrence find the best complete tag sequence rather than merely the best tag at each position? Fix a nonempty observed word $x_1\cdots x_n$ and a finite tag set $Y$. For a position $i$ and tag $y$, define $$ \delta_i(y) =\max_{y_1,\ldots,y_{i-1}} p(y_1)p(x_1\mid y_1) \prod_{j=2}^{i}p(y_j\mid y_{j-1})p(x_j\mid y_j), $$ where $y_i=y$. Thus, $\delta_i(y)$ is intended to be the probability of the best tag sequence for the prefix $x_1\cdots x_i$ that ends in $y$. We call this statement the **Viterbi invariant**. At the first character, there is only one valid length-one BI sequence: `B`. We enforce this constraint with $p(B)=1$ and $p(I)=0$, so $$ \delta_1(y)=p(y)p(x_1\mid y). $$ The base case follows. Now fix $i>1$ and suppose that the invariant holds at $i-1$. Any sequence ending in tag $y$ at position $i$ has some preceding tag $y'$. Its probability is the probability of its prefix through $i-1$, multiplied by $p(y\mid y')p(x_i\mid y)$. For a fixed $y'$, the induction hypothesis tells us that no prefix ending in $y'$ has probability greater than $\delta_{i-1}(y')$, and that some prefix attains this value. It follows that $$ \delta_i(y) =p(x_i\mid y) \max_{y'\in Y} \delta_{i-1}(y')p(y\mid y'). $$ Both directions now follow. Every candidate in the maximum extends a real prefix and is thus a real tag sequence; conversely, every tag sequence ending in $y$ appears under the candidate corresponding to its penultimate tag. Recording the maximizing $y'$ as a backpointer preserves the sequence that attains each value. After position $n$, every complete tag sequence ends in exactly one $y\in Y$. Thus, $\max_y\delta_n(y)$ is the probability of the globally best sequence, and following the stored backpointers reconstructs that sequence from right to left. The empty-word case does not enter the recurrence: its decoder returns `[]` before allocating a chart. For a numeric trace, take the observed string `unh` and the two tags `B` and `I`. Set the initial probabilities to $p(B)=1$ and $p(I)=0$, and use the following transition and emission probabilities: | previous tag | next `B` | next `I` | |---|---:|---:| | `B` | .30 | .70 | | `I` | .40 | .60 | | tag | emit `u` | emit `n` | emit `h` | |---|---:|---:|---:| | `B` | .50 | .20 | .30 | | `I` | .10 | .50 | .40 | At position one, the base case gives $\delta_1(B)=1(.50)=.500$ and $\delta_1(I)=0(.10)=0$. For `B` at the second character, the recurrence compares both possible predecessors: $$ \begin{aligned} \delta_2(B) &=.20\max\{.500(.30),0(.40)\}\\ &=.20\max\{.150,0\}=.030. \end{aligned} $$ The winning predecessor is `B`, so the backpointer for the state `(2, B)` points to `(1, B)`. Repeating the comparison for every state gives the complete table: | position | character | $\delta_i(B)$ | predecessor of `B` | $\delta_i(I)$ | predecessor of `I` | |---:|:---:|---:|:---:|---:|:---:| | 1 | `u` | .5000 | start | .0000 | start | | 2 | `n` | .0300 | `B` | .1750 | `B` | | 3 | `h` | .0210 | `I` | .0420 | `I` | For instance, the final `I` value is $.40\max\{.030(.70),.175(.60)\}=.0420$, and its winning predecessor is `I`. The final argmax compares $.0210$ for `B` with $.0420$ for `I`, so decoding ends in `I` at position three. Its backpointer leads to `I` at position two, whose backpointer leads to `B` at position one. Reversing that backward path reconstructs `B I I`, the highest-probability valid tag sequence for this example. There are $n|Y|$ table entries. Computing one entry examines $|Y|$ predecessor tags and performs constant work for each, yielding $O(n|Y|^2)$ time. The table and its backpointers require $O(n|Y|)$ space; if only the best probability is needed, two adjacent columns suffice. ```{python} from collections.abc import Mapping import numpy as np from hmmlearn.hmm import CategoricalHMM from numpy.typing import NDArray def characters_to_observations( word: str, character_ids: Mapping[str, int], ) -> NDArray[np.int_]: """Encode a word in the shape expected by ``CategoricalHMM``.""" observations = np.asarray( [character_ids[character] for character in word.lower()], dtype=int, ) return observations.reshape(-1, 1) latent_hmm = CategoricalHMM(n_components=2, n_iter=100) ``` ```{python} assert characters_to_observations("", {}).shape == (0, 1) ``` `CategoricalHMM(n_components=2)` is an unlabeled latent-state model. Fitting it to character observations alone neither identifies which state is `B` nor enforces the `B`-initial constraint; exchanging the two state IDs gives an equivalent latent model. A supervised BI tagger must instead estimate its parameters from gold character-tag pairs, fix the state-to-tag mapping, and set its initial distribution to `[1, 0]`, or implement the constrained Viterbi recurrence directly. The object above demonstrates the array shape expected by the library, not a trained BI segmenter. The HMM's emission at position $i$ depends on $y_i$ and $x_i$, not on the neighboring characters. It thus cannot directly express a feature such as “the current character is `n` and the preceding substring is `un`.” A conditional model can. ## A CRF tagger A linear-chain conditional random field (CRF) models $p(\mathbf{y}\mid\mathbf{x})$ directly [@lafferty_conditional_2001]: $$ p(\mathbf{y}\mid\mathbf{x}) =\frac{1}{Z(\mathbf{x})} \exp\left( \sum_{i=1}^n\sum_k \lambda_k f_k(y_{i-1},y_i,\mathbf{x},i) \right). $$ Each feature function may inspect the label transition and any bounded property of the observed word. The normalizer $Z(\mathbf{x})$ sums the unnormalized scores of every label sequence for the same word. For morphology, useful features include the current character, neighboring characters, character $n$-grams, and whether the position is word-initial or word-final. ```{python} type FeatureValue = str | bool type CharacterFeatures = dict[str, FeatureValue] def character_features(word: str, index: int) -> CharacterFeatures: """Return local segmentation features at ``index``.""" features: CharacterFeatures = { "character": word[index], "is_vowel": word[index] in "aeiou", "is_first": index == 0, "is_last": index == len(word) - 1, "previous": word[index - 1] if index > 0 else "<START>", "following": ( word[index + 1] if index + 1 < len(word) else "<END>" ), } if index > 0: features["left_bigram"] = word[index - 1:index + 1] if index + 1 < len(word): features["right_bigram"] = word[index:index + 2] return features def word_features(word: str) -> list[CharacterFeatures]: """Return one feature mapping per character in ``word``.""" return [character_features(word, index) for index in range(len(word))] ``` ```{python} import sklearn_crfsuite crf = sklearn_crfsuite.CRF( algorithm="lbfgs", max_iterations=100, ) # features = [word_features(word) for word, _ in training_data] # labels = [morphemes_to_tags(morphemes) for _, morphemes in training_data] # crf.fit(features, labels) ``` The HMM and CRF both return a flat label sequence. The CRF can condition on richer observations, while the HMM provides a joint model with a more restrictive independence structure. Neither model supplies morphological constituency. That distinction sets up the probabilistic CFG: the segmenter proposes terminals, and the grammar assigns structures and probabilities to sequences of those terminals.