Topological Fields as the Structural Prior for Minimal-Grammar Induction in German

German sentences have a rigid outer frame and a loose interior. The finite verb or a subordinating conjunction opens the clause, the remaining verbs close it, and arguments shuffle freely in between. Linguists call these slots topological fields. When treebanks annotate them, German becomes context-free and much easier to parse. Separately, minimal grammar optimization, a family of unsupervised methods, learns tags or grammar rules by asking for the smallest rule set that can still explain every sentence. In English part-of-speech tagging this beats plain likelihood maximization by several points. We propose to join the two. We encode the field frame as a small fixed automaton, and we run the "smallest grammar that covers the corpus" optimization over word classes and their field positions together, rather than over word classes alone. The output is tags and field boundaries for German text, induced from raw sentences plus a word-to-possible-tags dictionary, with no annotated trees.

This matters for two reasons. Every accurate topological field parser today is trained on the TüBa-D/Z treebank or on rule-converted NEGRA. That leaves out historical German, dialect corpora and other text without such annotation. It also matters for parsimony methods themselves. Their known weak spot is that they look only at neighboring word pairs, and German's hardest tagging ambiguity cannot be decided locally. That ambiguity is the -en verb form: gehen is either finite plural or infinitive, and the deciding cue is whether it sits in the opening or closing verb slot.

Core Claim

Requiring every sentence to be explained by a minimal set of tag transitions and a minimal set of tag-to-field placements, inside a hard-coded clause frame, should resolve long-distance ambiguities that bigram-only minimization cannot. In this setting the field frame plays the same role that universal combinatory rules played for supertagging. The frame should improve both tagging and unsupervised field labeling more than either the frame or minimization does alone.

The closest precedents each supply one ingredient but not the combination. Minimized Models for Unsupervised Part-of-Speech Tagging supplies the core method. It solves an integer program for the fewest distinct tag bigrams that still let every sentence be tagged, then runs EM on the pruned model. This raised 45-tag English accuracy from 81.7% to 84.5%, and to 91.6% with alternating dictionary refinement. Fast, Greedy Model Minimization for Unsupervised Tagging supplies the scalable solver (MIN-GREEDY). It is greedy set cover followed by greedy path completion, and it reaches 87.1% against 82.3% for EM on 973k tokens where the exact program did not finish. Minimized Models and Grammar-Informed Initialization for Supertagging with Highly Ambiguous Lexicons motivates the design. It showed that adding linguistic structure to minimization (38.7% to 59.6% on ambiguous CCG tokens) beats either component alone, though its structure was a bias on initial probabilities rather than a hard constraint on what minimization may select. On the field side, Annotating Topological Fields and Chunks - and Revising POS Tags at the Same Time is the strongest motivating evidence. A hand-written field cascade corrected tagger output and cut finite-verb errors from 9.95% to 8.07% and subordinator errors from 3.33% to 1.53%. That shows field structure carries exactly the information bigrams lack. That work, however, revises a supervised tagger's output with hand rules and learns nothing. Our proposal learns which placements exist, from raw text.

Research Program

The model is a product hidden Markov model whose hidden state is a pair: a word class from the Stuttgart-Tübingen tagset, and a topological field. The field component is a fixed finite-state clause frame with three clause types:

  • verb-second clauses: optional left dislocation, forefield, left bracket, midfield, right bracket, final field;
  • verb-first clauses;
  • verb-final clauses opened by a complementizer.

Embedding is bounded at depth two, in the spirit of the finite-state cascade. The frame encodes only orderings stated in the field-grammar literature, namely A Grammar Combining Phrase Structure and Field Structure and Topological Dependency Trees: A Constraint-Based Account of Linear Precedence. It never says which tags may fill which field.

Every rule the model could use is a binary choice: a tag transition $(t, t')$, or a placement $(t, f)$ allowing tag $t$ in field $f$. The minimization selects

$$\min_{x \in \{0,1\}^R} \sum_{r} w_r x_r \quad \text{s.t. every sentence has at least one path through the frame using only rules with } x_r = 1.$$

Here $R$ is the set of candidate rules, $x_r$ indicates whether rule $r$ is kept, and $w_r$ is a cost. The cost is 1 for transitions and $\lambda$ for placements, with $\lambda$ tuned on a development set. Candidate paths per token come from the type-level tag dictionary, crossed with the fields the frame allows at that position.

We solve the problem with an adaptation of MIN-GREEDY. Greedy set cover picks placements and transitions that cover the most uncovered word–tag–field triples. Path completion then adds the cheapest rules that close gaps in each sentence's lattice. EM finally re-estimates probabilities on the pruned product model. We will also test the alternating dictionary and grammar refinement from Ravi and Knight, now with field placements as part of the grammar. For example, if minimization never needs "infinitive in left bracket", that placement is removed and the dictionary entry is effectively narrowed per position.

The analysis has three goals. First, which placements the minimal solution keeps, compared with the placement inventory observed in TüBa-D/Z. Second, whether degenerate optima, a known weakness of exact solvers, concentrate on rare fields such as left dislocation. Third, whether minimality systematically drops low-frequency but valid placements, which is the overgeneralization-versus-fidelity tension the minimal-grammar literature itself flags. This last point is the risk we expect to bite. Extraposition into the final field is rare and might be minimized away.

Baselines

The naive reference point is EM on a bigram tag model with the same dictionary, plus field labels assigned afterward by the frame's most probable path given those tags. No reported German result was found on Lacuna for this. The English analogue is 81.7% (45 tags) in Ravi and Knight. We will run it on the same TüBa-D/Z text and dictionary, with the same number of EM iterations and restarts as every other system. Beating it means a gain on overall tag accuracy and on finite-versus-infinitive verb accuracy, significant across restarts.

The strongest unsupervised competitor for tagging is MIN-GREEDY applied exactly as published, with bigram minimization only, followed by EM. Fields are again assigned afterward by the frame. It is the strongest because it is the best published scalable parsimony method, reporting 87.1% against 82.3% for EM on 973k English tokens in Fast, Greedy Model Minimization for Unsupervised Tagging. It shares our dictionary, corpus, EM schedule and solver code. The only difference is the missing placement variables, so it doubles as the ablation that isolates our key ingredient. The proposal beats it if verb finiteness and subordinator accuracy improve. Those are the categories where Müller and Ule saw field information help. A gain confined to frequent unambiguous tags would not count.

Two further ablations separate frame from parsimony. The first is EM on the full product model with the field frame but no minimization. The second is field-informed initialization only: placement probabilities biased toward placements implied by verb morphology in the dictionary, which is the analogue of grammar-informed initialization from the supertagging work. If the frame alone delivers the gain, minimization is not earning its keep.

For field labeling there are three reference points. The first is a reimplementation of the deterministic rule cascade of Annotating Topological Fields and Chunks - and Revising POS Tags at the Same Time, applied to the same dictionary-only induced tags. The second is supervised upper bounds that use the treebank we deliberately withhold: 97.24% token field accuracy for the Bi-LSTM labeler in Transition-based dependency parsing with topological fields, and 95.15% $F_1$ for the latent-variable parser in Topological Field Parsing of German, the latter with gold tags. We do not expect to beat the supervised systems. Success means closing a stated fraction of the gap between the naive baseline and 97.24% without any trees.

Why not just…?

Why not just run a hand-written field cascade on top of an unsupervised tagger? This is the most serious alternative. Field rules are largely deterministic once verbs are tagged correctly. Its weakness is the dependence on that condition: the cascade inherits every finiteness error from the tagger. Müller and Ule show the cascade can repair tags, but only by starting from a supervised tagger and hand rules. Our cascade baseline over dictionary-only EM tags tests this directly. If that pipeline matches joint minimization on field accuracy and verb tagging, the joint optimization is unnecessary and we will report so. The joint method would still need to show a tagging advantage to justify itself.

Why not just train on TüBa-D/Z and transfer to the target text? For modern newspaper German this will win, and we do not dispute it. The claim is restricted to text with no field treebank. To settle it honestly, we will run the transfer baseline on the out-of-domain novel portion of the DEREKO subset and on whatever historical sample we can evaluate. The proposal is relevant only where transfer degrades below our induced labels. Automatic Topological Field Identification in (Historical) German Texts indicates historical field identification is an active problem, but the file gives no numbers for it.

Why not just use a large unsupervised discontinuous grammar? Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars uses up to 4,500 nonterminals and parsing cost growing with the fifth power of sentence length. It reaches 46.1 overall $F_1$ and 8.0 discontinuous $F_1$ on NEGRA, and Neural Unsupervised Parsing Beyond English reports 0.41 $F_1$ for PRPN on German. These systems target full constituency and produce no fields. They are not competitors on our main metrics, but they bound what overparameterized induction currently achieves. In a secondary check, we will feed induced field brackets as hard constraints to a cubic-time PCFG inducer on NEGRA and compare against 46.1 overall $F_1$ under the same length cutoff.

Proposed Experiments

The main data are TüBa-D/Z, which provides gold tags and fields. The dictionary is built from the training-section lexicon only, mirroring Ravi and Knight's protocol, and evaluation is on held-out sentences. A second condition uses the 490k-token DEREKO subset, so that verb and subordinator error rates can be compared with the categories Müller and Ule report.

Metrics are:

  • overall tag accuracy;
  • accuracy on ambiguous tokens;
  • accuracy on finite verbs, infinitives and subordinators;
  • token-level field accuracy and per-field labeled $F_1$, matching the supervised papers;
  • induced grammar size and solver runtime.

The decisive check has two parts. On -en verb tokens and subordinators, field-aware minimization must beat MIN-GREEDY. It must also beat both frame-only and initialization-only ablations, so the gain is attributable to joint parsimony and not to the frame. A second decisive check scales to the full corpus: greedy solving must stay within a small multiple of MIN-GREEDY's runtime despite the larger product state space. If the joint method improves fields but not tags, or tags but only through the frame, we will report the corresponding narrower conclusion.