Constraint-Costed Dynamic Oracles for Zero-Shot Cross-Lingual Transition Parsing

A transition-based parser builds a syntax tree one action at a time: it shifts words from a buffer onto a stack and attaches them to each other. It runs in linear time, but it has a known weakness. It is trained only on the correct action sequence, so after its first mistake at test time it is in a situation it has never seen, and later mistakes pile up. This is called exposure bias. The standard fix is a dynamic oracle, a procedure that tells the parser the best action to take from any state, including states reached by mistakes. That fix needs a gold tree. In zero-shot cross-lingual parsing, where an English-trained parser is applied to a new language with no annotated target data, there is no gold tree. This is also the setting where the parser is most likely to make early mistakes, because its English word-order habits fail on head-final languages such as Hindi.

We propose to build a dynamic oracle for target-language text from two signals that exist without target treebanks. The first is a set of confident arcs from an English-trained teacher. The second is a small set of universal well-formedness rules from the Universal Dependencies annotation scheme: a predicate has at most one nominal subject and at most one direct object, a sentence has one root, and function words tagged case, det, aux or mark take no ordinary dependents. These rules are typically broken by adding a wrong arc, not by leaving one out. A parser action that breaks one of them can therefore be charged a cost at the moment it is taken, by a check that needs no global search. We then train the parser with exploration on raw target sentences, so it learns to recover from its own cross-lingual mistakes, and we test whether this beats simply forbidding rule-breaking actions at test time.

Core Claim

Exposure bias is a larger share of the zero-shot error than of the monolingual error, and it grows with word-order distance from English. If that is true, the right remedy is to train on the parser's own erroneous target-language states. Masking illegal actions at decoding time alone does not do this, because masking pushes the parser further off the states it was trained on. Training on erroneous target states requires an oracle defined without gold trees. "At most one"–type constraints, which become violated only when an arc is added and stay violated afterwards, are exactly the class whose cost can be computed exactly and incrementally inside a transition system. This sidesteps the problem of arc-decomposability, the property that the loss splits into independent per-arc terms, which exact dynamic oracles depend on. For SWAP that problem forced a static fallback (Arc-Hybrid Non-Projective Dependency Parsing with a Static-Dynamic Oracle), and for global constraints it pushed earlier work toward Lagrangian relaxation and branch-and-bound (Dependency Parsing with Bounded Block Degree and Well-nestedness via Lagrangian Relaxation and Branch-and-Bound).

Relation to Prior Work

The proposal reuses the dynamic-oracle and exploration machinery of A Dynamic Oracle for Arc-Eager Dependency Parsing and Training with Exploration Improves a Greedy Stack LSTM Parser. The latter samples actions from a temperature-flattened distribution and reaches 93.56 unlabeled attachment score (UAS) on the English Penn Treebank with a greedy parser. Both papers assume gold trees on the training data. We assume none on the target side.

The closest work is Frustratingly Easy Cross-Lingual Transfer for Transition-Based Dependency Parsing. It projects English parses through Europarl word alignments, keeps only the reliably aligned arcs as partial trees, and trains an arc-eager parser with a dynamic oracle that assigns zero cost to any action touching unannotated words. We differ in three ways. We use no parallel text. Our partial supervision comes from constrained decoding of a teacher rather than from alignment. Most importantly, unannotated regions are no longer free: actions there still pay for violating universal constraints. That paper names "constrained parsing techniques" as future work, and this proposal takes up that direction.

Don't Stop Me Now! Using Global Dynamic Oracles to Correct Training Biases of Transition-Based Dependency Parsers motivates our diagnostic. It shows that exploration corrects a mismatch between training and test states, with gains concentrated late in sentences (0.2 UAS on average, up to 0.7, on SPMRL treebanks). It notes that partial supervision should help multilingual transfer but never tests transfer. Approximate Dynamic Oracle for Dependency Parsing with Reinforcement Learning learns action costs from arc-reachability rewards when exact oracles are unavailable. It still needs gold trees. Our constraint costs are an exact, non-learned alternative for one class of constraints.

On the transfer side, Substructure Distribution Projection for Zero-Shot Cross-Lingual Dependency Parsing projects arc distributions through alignments into a graph-based parser and raises Hindi labeled attachment score (LAS) from 28.3 to 38.9. It needs bitext and does not enforce joint well-formedness of the projected targets. Cross-Lingual BERT Transformation for Zero-Shot Dependency Parsing and 75 Languages, 1 Model: Parsing Universal Dependencies Universally show that multilingual encoders carry transferable syntax. The UDify work in particular finds abstract syntax in middle-to-late layers. These encoders are our starting point, not our competitor.

Two lines of work constrain our design. Enforcing Subcategorization Constraints in a Parser Using Sub-parses Recombining gets real gains from valency constraints on French, raising subcategorization-frame accuracy from 80.84% to 83.50%. It depends on a curated lexicon, which low-resource targets lack. That limitation is why we restrict ourselves to lexicon-free, label-level constraints. The unsupervised role-induction work (Unsupervised Semantic Role Induction with Graph Partitioning) supports the specific choice of "no duplicate core role per predicate" as a constraint that removes degenerate solutions.

Research Program

The first step is calibration. On gold UD training treebanks across many languages, we measure how often each candidate constraint holds per head. We keep only constraints satisfied in at least roughly 99% of cases across languages, so that we enforce universal regularities rather than English habits. Coordination and ellipsis will create exceptions to "one subject". Calibration decides which label sets survive, and we report the per-language violation rates.

The second step builds the teacher signal. An English-trained biaffine parser with the same multilingual encoder produces arc marginals on raw target sentences. We decode them under the surviving constraints. This is a constrained maximum spanning tree problem, solved with Lagrangian relaxation following the bounded-block-degree work, which reports optimality certificates from relaxation alone on over 95% of English and German sentences. We keep as supervision only the arcs whose marginal exceeds a threshold, which yields partial trees, as in the Frustratingly Easy work.

The third step defines the oracle. For a parser configuration $c$ and labeled action $a$, the cost is

$$\mathrm{cost}(a;c) = \big|\mathcal{R}(c)\setminus\mathcal{R}(a(c))\big| + \lambda\, V(a,c).$$

Here $\mathcal{R}(c)$ is the set of confident teacher arcs still reachable from $c$, computed with the standard arc-hybrid reachability test. $V(a,c)$ is the number of constraint violations that the arc added by $a$ newly creates. $\lambda$ trades teacher agreement against well-formedness. Because every retained constraint is of the "at most" kind, a violation can arise only when an arc is added and can never be undone. $V$ is therefore exact and needs an O(1) check per action. Abstaining from an arc never creates a violation, so the constraint term never forces the parser into a dead end. When the parser's own earlier error makes a teacher arc illegal, for example because a wrong subject is already attached, the two terms conflict. $\lambda$ resolves the conflict, and we report how often it happens.

The fourth step trains the parser. We start from an English-trained arc-hybrid parser on the same encoder, then continue training on target raw text with temperature-flattened exploration, using the oracle above. English gold data stays in the mix to prevent drift.

Alongside the method we run a diagnostic. For each target test set we compare free-running accuracy with accuracy when the parser decodes from gold-history configurations. The gap estimates the share of errors that are propagated rather than first-order. We plot this share against a treebank-derived measure of word-order distance from English, the fraction of head-final arcs.

Baselines

The do-nothing reference is the English-trained arc-hybrid parser on the shared multilingual encoder, trained with the standard gold-tree dynamic oracle and exploration, applied directly to target languages. Every target-side method must beat it.

The ablation that isolates our key ingredient is the same target self-training pipeline with $\lambda = 0$. This is the Frustratingly Easy partial-tree oracle, with zero cost for unannotated material, transplanted to teacher-derived partial trees. Any gain of the full method over this ablation is attributable to constraint costs on target states.

A second ablation trains on the same teacher trees with a static oracle and no exploration. It separates the value of exploring erroneous states from the value of self-training data.

The strongest test-time competitor is the do-nothing parser with illegal actions masked during decoding.

The strongest existing method under our no-bitext condition is a graph-based biaffine student trained on the identical constrained partial trees and decoded under the same constraints by Lagrangian relaxation.

All systems share the encoder, the target raw sentences (UD training splits with annotations stripped), the number of update steps, and a fixed hyperparameter search. Selection uses English development data only, since a zero-shot protocol allows no target development data. We also report sensitivity to $\lambda$ and to the confidence threshold.

As an external reference we quote Substructure Distribution Projection for Zero-Shot Cross-Lingual Dependency Parsing: 38.9 LAS on Hindi in UD v2.2, against a prior best of 28.3. That system uses bitext, so it is not a like-for-like competitor. We will also run a variant that adds constraint costs to SubDP-projected supervision. The file reports no per-language numbers for UDify or the CLBT zero-shot setting beyond the +2.91 LAS gain, and no reported result was found on Lacuna for transition-based zero-shot parsing with multilingual encoders on UD v2.2.

Beating the strongest no-bitext baseline means statistically significant LAS gains over the masked-decoding baseline and the $\lambda = 0$ ablation, averaged over the target languages. We also require at least parity with the graph-based student, at linear rather than cubic decoding cost.

Why not just…?

Why not just mask rule-breaking actions at decoding time? This is the most serious threat, because it is free. It can, however, force the parser into states it never saw during training, which could worsen the very cascades we target. The masked-decoding baseline settles the question directly. If masking recovers most of the gain of the full method, we will report that constraint costs add nothing beyond decoding. We expect masking to fix violation rates but recover much less LAS, with the difference concentrated after the first masked action in a sentence.

Why not just use a graph-based biaffine parser, which has no exposure bias? Spanning-tree decoding guarantees a tree but not label-level well-formedness. With constrained decoding and the same self-training data, though, a graph-based parser may match us in accuracy. We treat this as the strongest baseline rather than argue it away. If it wins clearly, the paper's contribution narrows to the diagnostic and to a linear-time parser at parity. If it does not, the result shows that sequential parsers can be repaired on target text.

Why not just rely on a stronger multilingual encoder, as UDify does? UDify's gains come from training on many treebanks, which is not the zero-shot regime. The SubDP and CLBT results show sizable headroom over plain multilingual-encoder transfer on distant languages, such as Hindi at 28.3 LAS before SubDP. We hold the encoder fixed across all systems, so encoder strength cannot explain any difference. We will also repeat the key comparison with a larger encoder to check whether the gain shrinks as the encoder grows.

Why not just project trees through parallel text? Bitext is often unavailable or noisy for low-resource languages, and the Frustratingly Easy and SubDP results show that alignment noise must be managed carefully. Our method is orthogonal to projection. The SubDP-plus-constraint-cost variant tests whether constraint costs still help when bitext exists.

Proposed Experiments

The experiments use English UD as the only annotated source. Targets are the eight UD v2.2 languages evaluated by SubDP, including Hindi, so that the bitext reference number is comparable. To test the typological prediction we add head-final treebanks from the CoNLL 2017 UD set. Metrics are UAS and LAS, the per-sentence rate of constraint violations, and LAS split by sentence position (first versus second half), following the restart-strategy analysis in the Don't Stop Me Now paper.

Three checks are decisive. First, the propagated-error share must rise with head-final distance from English. If it is flat, the motivation for a transition-specific remedy fails and we say so. Second, the full method must beat both the $\lambda = 0$ ablation and masked decoding, with larger gains on more distant languages and in later sentence positions. That pattern is the signature of reduced error cascades rather than of better local scoring. Third, the full method must not lower accuracy on held-out gold arcs that obey the constraints. This guards against the cost term simply suppressing valid but rare constructions that calibration missed.