When a word is inflected, its spelling often changes at the seams. English spy + plural becomes spies. In Turkish, the vowel of a suffix changes to match the vowels of the stem. For decades the most reliable way to handle this has been two-level morphology, in which a linguist writes a small set of declarative rules. Each rule says which pairings of an abstract "lexical" character with a written "surface" character (for example, lexical y written as surface i) are allowed, or required, in which neighboring contexts. The rules compile into a finite-state transducer, a compact machine that both analyzes and generates words. These systems are accurate, inspectable and bidirectional, but every rule is written by hand. The Turkish analyzer of Two-level Description of Turkish Morphology needed 22 hand-written rules and about 100 suffix lexicons.
Unsupervised part-of-speech tagging offers a way to automate this. There, the biggest gains came from searching for the smallest grammar consistent with the data, posed as an integer linear program, rather than fitting probabilities by Expectation-Maximization (EM), which spreads weight over every possible structure. We propose to apply the same parsimony principle to two-level rules. Given a few dozen inflection tables, an integer program chooses three things together: the underlying forms of stems and affixes, the character alignments between lexical and surface strings, and the cheapest set of two-level rules under which every attested form is derivable and no attested contrast is violated. The result is a hand-editable rule grammar that compiles directly to a transducer. It is learned from data that a linguist could collect in an afternoon.
Core Claim
The structure of two-level rules makes rule induction an exact covering problem, not a heuristic search. There are two rule types in the formalism formalized by On the Generative Power of Two-Level Morphological Rules:
- A context restriction rule says a character pair may occur only in listed contexts. In covering terms, every occurrence of that pair must fall inside some selected context.
- A surface coercion rule says a lexical character in a given context must be written a certain way. In covering terms, a selected context may contain no counterexample.
The first gives set-cover constraints and the second gives packing constraints. Both are linear once the latent alignment and underlying form of each word are encoded as binary choices.
We claim this joint program does two things that nothing in the file does. First, it recovers compact, linguistically plausible rule sets. Second, it generalizes to unseen lemmas in both generation and analysis at least as well as neural inflection models when training data is very small.
The closest prior work solves a neighboring problem in each case:
- Improving Morphology Induction by Learning Spelling Rules learns boundary insertion and deletion rules by Gibbs sampling under sparsity priors. It handles only a single stem plus one suffix, has no substitutions, and produces no transducer.
- Frugal Paradigm Completion uses minimum set cover to decide which paradigm cells to ask a human for. The grammar itself remains a Transformer.
We use set cover to choose the rules themselves.
Research Program
The input is a set of triples: lemma, feature bundle (such as N;PL;DAT), and surface form, drawn from UniMorph (UniMorph 2.0: Universal Morphology). Morphotactics is taken as given at the level of feature order, so the lexical string of each form is the underlying stem followed by the underlying affixes for its features. Both the underlying stem and the underlying affixes are latent.
Candidate generation. For each word we enumerate a small set of candidate analyses. Each candidate is an underlying stem and affix choice together with a lexical-to-surface alignment. The candidates come from edit-distance alignments with bounded insertions, deletions and substitutions, similar in spirit to the edit trees of Unsupervised Morphological Paradigm Completion.
For every non-identity pair occurrence in a candidate, such as y:i, we generate candidate contexts. A context is a left and right window of up to two positions over characters, over the morpheme boundary, or over automatically proposed character classes. A class is a set of symbols that appear interchangeably in the same windows; this is what lets a rule like vowel harmony be stated once rather than once per vowel.
The integer program. Let $x_r \in \{0,1\}$ indicate that candidate rule $r$ is selected, with cost $c_r$ growing with context length. Let $z_m \in \{0,1\}$ indicate that lexicon entry $m$ (an underlying stem or affix string) is used, with cost $|m|$ in characters. Let $y_{w,k} \in \{0,1\}$ indicate that word $w$ takes candidate analysis $k$, with $\lambda$ a weight trading rules against lexicon. The objective is
$$\min \; \sum_r c_r x_r + \lambda \sum_m |m|\, z_m,$$
subject to five constraints:
- $\sum_k y_{w,k} = 1$, so each word takes exactly one analysis.
- $y_{w,k} \le z_m$ for every lexicon entry $m$ that analysis $k$ uses.
- $y_{w,k} \le \sum_{r \in R(o)} x_r$ for every non-identity pair occurrence $o$ in analysis $k$, where $R(o)$ is the set of context-restriction rules whose context matches $o$. This is the covering constraint.
- $x_r + y_{w,k} \le 1$ whenever analysis $k$ contains a counterexample to coercion rule $r$. This is the packing constraint.
- A set of paradigm-contrast constraints, described next.
The paradigm-contrast constraints supply negative evidence. Under the chosen grammar, generation from an attested lexical string must not yield a different surface form that competes with the attested one in the same cell.
Why the joint objective matters. Weighting lexicon size against rule cost is aimed at the "over-explanation" failure reported by Naradowsky and Goldwater. When their model minimized stems freely, it reanalyzed -ed as -d plus an e-insertion rule and lost suffix accuracy. Sweeping $\lambda$ exposes that trade-off explicitly, where their priors left it implicit.
Guarantee on the output. Every output is a set of declarative two-level rules, so it can always be compiled back into a transducer. General transducers that violate Ritchie's subsequence property are simply not in the search space. We do not claim that path-completion heuristics produce non-compilable machines, since the file frames that only as a possibility; our construction avoids the question entirely.
Scaling. For small inputs we solve exactly. For larger inputs we follow Fast, Greedy Model Minimization for Unsupervised Tagging: greedy covering of pair occurrences first, then greedy repair of words left without a legal analysis, with every greedy step restricted to whole rules. On tagging, that approach took 34.3 seconds versus 93.0 for exact IP on 24k words, at a cost of 478 versus 459 bigrams. Measuring this optimality gap on morphology is part of the study.
Two predictable failure points. Ties among equal-cost grammars are broken by preferring rules that also hold on held-out attested forms. The known NP-completeness of two-level recognition (Computational Complexity in Two-Level Morphology) affects decoding with the finished transducer, not induction, because induction here works on fixed attested strings.
Baselines
Frequency-filtered rule extraction (naive reference). Align lemma and form once by minimum edit distance and read off every non-identity pair with its immediate context. Keep any rule whose precision on training data exceeds a threshold tuned on development data. This is what a practitioner would try first. It uses the same candidate space as our method but no joint choice of underlying forms or alignments. It receives the same inputs and the same compiler, and beating it requires higher held-out generation accuracy with no larger rule set.
Neural character inflection model (strongest competitor on accuracy). This is a Transformer inflection model like the predictor in Frugal Paradigm Completion. It is the strongest competitor because neural transducers dominate inflection when data is plentiful. It is trained on exactly the same lemma splits, with a comparable hyperparameter search budget measured in trials. For analysis, which a single two-level grammar performs for free, it is trained as a separate reverse model.
No reported result was found on Lacuna for UniMorph held-out-lemma inflection accuracy of such a model. We will therefore report our own runs. Success means matching or beating it at 10 to 100 training paradigms. We expect it to win with more data, and we will report where the curves cross.
Bayesian spelling-rule model (strongest structured competitor). This is the Gibbs-sampling model of Improving Morphology Induction by Learning Spelling Rules. It is run on its own benchmark: 7,487 Penn Treebank verbs evaluated against CELEX. It reports Stem Underlying Form Accuracy (the fraction of words whose recovered underlying stem matches the gold analysis) of .786, and pairwise recall of .911 (the fraction of word pairs sharing a gold stem that the model also groups together). Its baseline without spelling rules scored .580 and .647. Beating it means exceeding .786 Stem accuracy without its drop in suffix accuracy.
Concatenative MDL segmenter. Morfessor (Morfessor 2.0: Toolkit for Statistical Morphological Segmentation) serves as a reference for lexicon size, since it models no boundary changes at all.
Ablations. Three ablations isolate the key ingredient:
- Fixing alignments and underlying forms in advance, so only rules are chosen. This isolates the value of joint latent choice.
- Replacing the exact solver with greedy covering. This measures the optimality gap.
- Dropping coercion and contrast constraints. This measures how much negative evidence prevents overgeneration.
Hand-written reference. For Turkish, Oflazer's 22 hand-written rules serve as a qualitative reference for rule count and content, not as a scored system.
Why not just…?
Why not just train a neural inflection model and stop? With enough tables it will likely be more accurate, and we do not claim otherwise. The case for rules rests on three properties the neural model lacks:
- A single rule grammar both generates and analyzes words.
- It cannot invent forms outside its rules.
- A linguist can read and edit it.
There is also evidence that neural models struggle when inflected forms are rare, as on Finnish in Unsupervised Morphological Paradigm Completion. The learning-curve experiment settles where the crossover lies. If the neural model wins even at 10 paradigms, the contribution narrows to interpretability and bidirectionality, and we will say so.
Why not just extract rules from edit alignments and filter by frequency? This is the real threat. On languages with mostly local, unambiguous alternations, it may match the integer program. The integer program should win only where the right underlying form is not recoverable from any single word, such as stems whose final vowel surfaces differently across cells, or harmony that depends on a class. The fixed-alignment ablation and the naive baseline are designed to show whether that happens. If they tie across languages, the joint program adds nothing, and we would reframe the work as a compiler for filtered rules.
Why not just use Bayesian sparsity priors, as Naradowsky and Goldwater did? Their sampler already favors compact analyses. However, their model cannot express substitutions or multiple suffixes, and their paper shows the over-explanation failure. The CELEX comparison measures directly whether exact joint minimization with an explicit rule-versus-lexicon weight avoids that failure. Running both methods on identical candidate spaces separates the effect of exact search from the effect of rule expressiveness.
Why not just hand-write the rules? For well-resourced languages that remains best. The Turkish description shows the cost, however, and the frugal-elicitation results show that experts' effort is better spent supplying a few forms than authoring rules. Our output is meant as a first draft for the linguist to correct, not a replacement.
Proposed Experiments
Low-resource learning curves. We train on 10, 25, 50 and 100 UniMorph paradigms per language, in Turkish, Finnish, Hungarian, German, Russian, Latin and English (the latter four overlapping the frugal-completion set). We evaluate on held-out lemmas and report:
- exact-match accuracy for generation,
- exact-match accuracy for analysis,
- the number of spurious analyses per surface form,
- the number of rules,
- the size of the compiled transducer.
CELEX English verbs. This gives a direct numeric comparison to the published Stem Underlying Form Accuracy of .786, alongside suffix accuracy.
Turkish harmony audit. We compare the learned rules for Turkish harmony with Oflazer's hand-written harmony rules. The question is whether class-based contexts emerge from the character-class candidates or the program instead memorizes rules for each vowel separately.
Three decisive checks. Each would change the project if it failed:
- The joint program must beat frequency-filtered extraction on at least the harmony and stem-alternation languages.
- Moving from exact to greedy solving must cost little accuracy, or the method will not scale.
- At 10 to 25 paradigms, the rule grammar must at least tie the neural model on generation while also providing analysis. If it does not, interpretability alone does not justify the approach.
As a secondary test, we will substitute the learned grammar for the Transformer inside the frugal-completion query loop. This asks whether an explicit rule learner needs fewer than the reported 1.2 to 3.6 queries per paradigm.
References
- Two-level Description of Turkish Morphology
- On the Generative Power of Two-Level Morphological Rules
- Improving Morphology Induction by Learning Spelling Rules
- Frugal Paradigm Completion
- UniMorph 2.0: Universal Morphology
- Unsupervised Morphological Paradigm Completion
- Fast, Greedy Model Minimization for Unsupervised Tagging
- Computational Complexity in Two-Level Morphology
- Morfessor 2.0: Toolkit for statistical morphological segmentation