Aligning the States a Parser Actually Visits: Adversarial Domain Adaptation for Transition-Based Parsers

A transition-based dependency parser builds a sentence's grammatical tree the way a person reads. It moves left to right, keeps partly built pieces on a stack, and makes one irreversible decision at a time, such as "attach this word to that one" or "move on to the next word." This gives it linear running time and makes it fast. It also makes it fragile. One early mistake puts the parser in a situation it never saw during training, and later decisions go wrong in a cascade. When such a parser moves from news text to product reviews, web fiction, or a new language, the two problems compound. Unfamiliar words cause more early mistakes, and each mistake pushes the parser further from anything it was trained on.

Adversarial domain adaptation trains a network so that a second network, the "discriminator," cannot tell whether an internal representation came from the labeled source domain or the unlabeled target domain. Every published adversarial or alignment method for cross-domain dependency parsing applies this to the sentence encoder of a graph-based parser, which scores all word pairs at once and has no cascading errors. We propose to apply it where a transition parser's decisions actually happen: the parser states (stack, buffer, and partial tree) that the parser reaches when it runs on target text. The key design choice is the source side of the comparison. We compare target states against source states generated by training with deliberate mistakes, so the source side already contains error states from which the parser has learned to recover. The goal is that the parser's target-domain mistakes land in regions where it already knows how to recover, rather than being disguised as clean states.

Core Claim

In a transition parser, domain shift and exposure bias are the same problem seen from two sides. Exposure bias means the parser is only trained on correct states but must act on its own erroneous ones at test time. Target sentences produce states that are unfamiliar in two ways: their words come from a different distribution, and the parser's own errors leave the stack in shapes it rarely saw on the correct training path.

We claim that aligning the distribution of states visited on-policy (states reached by running the current parser itself) across domains is more effective than aligning encoder outputs, provided two conditions hold. First, the source states include exploration states produced by a dynamic oracle. Second, the source exploration rate is set so that source and target rollouts are comparably "broken." If the second condition fails, the discriminator can identify the domain simply by how many errors a state contains. The extractor would then be pushed to make target error states look like correct ones, which would hide errors instead of making them recoverable.

The concrete prediction is that the improvement will concentrate on words parsed after the first error in a sentence (a smaller cascade), not on the first error itself. Encoder-level alignment predicts the opposite pattern.

Research Program

Parser. The backbone is an arc-hybrid or arc-eager parser, the two standard ways of defining the parser's available moves. We choose these because dynamic oracles require the "arc-decomposable" systems identified in Training Deterministic Parsers with Non-Deterministic Oracles. A dynamic oracle is a procedure that, given any state including a wrong one, returns the best remaining actions. That paper introduced such oracles and training with exploration, raising English arc-eager UAS (unlabeled attachment score, the fraction of words given the correct head) from 86.10% to 88.69%. We reuse this technique as the method supplier.

The controller (the classifier that picks the next action) reads a state vector. This vector is built from encoder outputs at the top stack and buffer positions, in the spirit of the feature-window design of A Fast and Accurate Dependency Parser using Neural Networks. A second variant uses the Stack-LSTM summary of Greedy, Joint Syntactic-Semantic Parsing with Stack LSTMs, a recurrent network that updates as items are pushed and popped. Encoders are a BiLSTM for the Chinese multi-domain experiments and XLM-RoBERTa for cross-lingual transfer, matching the prior work we compare against.

Training. Each step runs the current policy on a batch of source sentences with dynamic-oracle exploration. With probability $p$ the parser follows its own prediction rather than the oracle's. The oracle supplies loss on every visited state. The same policy also runs, without labels, on unlabeled target sentences. Every visited state from both sides is passed through a gradient reversal layer to a domain discriminator. A gradient reversal layer passes values forward unchanged but flips the sign of gradients flowing back, as used in the GRL-based work cited in the file, for example FAN-Net. The objective is

$$\min_{\theta}\max_{\phi}\; \mathcal{L}_{\text{oracle}}(\theta; \mathcal{C}_S^{p}) - \lambda\, \mathcal{L}_{\text{dom}}(\phi; \mathcal{C}_S^{p}, \mathcal{C}_T),$$

where $\theta$ are encoder and controller parameters and $\phi$ are discriminator parameters. $\mathcal{C}_S^{p}$ is the set of states visited on source sentences under exploration rate $p$, and $\mathcal{C}_T$ is the set of states visited by the current policy on target sentences. $\mathcal{L}_{\text{oracle}}$ is the dynamic-oracle cross-entropy, $\mathcal{L}_{\text{dom}}$ is the discriminator's binary cross-entropy, and $\lambda$ sets the alignment strength.

Matching error levels. The parameter $p$ is the lever that matches error levels across domains. We set it so that the parser's mean action confidence on source rollouts matches its confidence on target rollouts. This needs no target labels. We compare this rule against choosing $p$ on a small labeled target development set.

Handling divergent syntax. A conditional variant feeds the controller's predicted action distribution to the discriminator alongside the state. This lets alignment respect cases where the correct action given a state genuinely differs across domains. That is the negative-transfer risk flagged for highly informal text in Unsupervised Domain Adaptation Method with Semantic-Structural Alignment for Dependency Parsing.

Stability. That same paper constrains our design, because it abandoned adversarial alignment as unstable when target data is scarce. State-level alignment offers a partial answer. Every sentence yields roughly $2n$ states, where $n$ is the sentence length, so the discriminator sees about two orders of magnitude more samples than a sentence-level discriminator does from the same unlabeled corpus. We will test whether this helps rather than assume it, by reporting variance over seeds. The discriminator is dropped at test time, so parsing speed is unchanged. We will confirm this against the 1,013 sentences per second reported by Chen and Manning.

Diagnostics. We decompose target error into two quantities: the first-error rate per sentence, and the attachment error rate conditioned on the distance after the first error. We also probe residual domain separability separately for states on the gold path and states off it.

Relation to Prior Work

Four papers adapt dependency parsers across domains or languages, and all four use graph-based BiAffine parsers. They motivate the gap and supply comparison points.

Representation Alignment and Adversarial Networks for Cross-lingual Dependency Parsing is the closest work. It puts a GRL language discriminator on XLM-RoBERTa encoder outputs, adds dictionary-based input alignment, and parses Chinese to Vietnamese. We keep its adversarial encoder as a baseline but move the discriminator onto parser states and require no bilingual dictionary.

Unsupervised Domain Adaptation Method with Semantic-Structural Alignment for Dependency Parsing aligns with local maximum mean discrepancy (a non-adversarial distance between feature distributions) and graph-attention structure matching. It rejects adversarial training as unstable. We address that objection directly, and we use a state-level version of its distance-based loss as an alternative to our discriminator.

Semi-supervised Domain Adaptation for Dependency Parsing with Dynamic Matching Network matches encoder layers using labeled target data. Semi-supervised Domain Adaptation for Dependency Parsing conditions the parser on a domain embedding and fine-tunes ELMo on target text. Both need labeled target sentences, which our main setting does not use.

None of these works can observe cascading errors, because their parsers never decode step by step. On the transition side, Left-to-Right Dependency Parsing with Pointer Networks and Transition-based Dependency Parsing with Selectional Branching document the garden-path cascade that motivates our diagnostics. Beam search and global training, as in A Neural Probabilistic Structured-Prediction Model for Transition-Based Dependency Parsing, fight the cascade at extra inference cost. We aim to fight it at no inference cost.

Baselines

Naive reference. An arc-hybrid parser trained on source with the static oracle (which only ever shows correct states) and applied directly to target text. It sets the size of the domain gap.

Exploration only. The same parser trained with dynamic-oracle exploration, as in Training Deterministic Parsers with Non-Deterministic Oracles, with no target data. It isolates how much of the target gap is really exposure bias.

Encoder-level adversarial alignment. This is the strongest competitor on our question. It transplants the adversarial encoder of Representation Alignment and Adversarial Networks for Cross-lingual Dependency Parsing: the same transition parser, the same dynamic-oracle training, and a GRL discriminator on encoder token outputs. It is the obvious way to combine the two fields and differs from ours only in where alignment is applied. On Chinese-to-Vietnamese, the original graph-based adversary-only model reports 68.47 LAS (labeled attachment score, the fraction of words given both the correct head and the correct relation label). The full model reports 68.98 LAS and 76.81 UAS, against 68.09 LAS for plain fine-tuning.

State-level distance matching. A state-level analogue of the maximum-mean-discrepancy alignment of Unsupervised Domain Adaptation Method with Semantic-Structural Alignment for Dependency Parsing. It tests whether the adversarial game itself matters. That paper reports average gains of 1.12 UAS and 1.14 LAS over BiAffine and adversarial baselines on CODT1. No absolute scores were found on Lacuna for it.

Self-training. The target is pseudo-labeled by the source parser and then retrained, in the style of The Alpage Architecture at the SANCL 2012 Shared Task, which reported error accumulation. No attachment-score result was found on Lacuna for that system.

Graph-based ceiling. A BiAffine parser with encoder-level GRL sets the accuracy ceiling for the slower, cascade-free alternative.

Ablations. Our method is also run with static-oracle source states (no exploration) and with a fixed, unmatched $p$. These isolate the key ingredient.

Fairness. All systems share the encoder, the unlabeled target corpus, the number of training updates, and a hyperparameter budget of an equal number of trials over $\lambda$ and learning rate. Model selection uses the same target development protocol for every system. We report means and standard deviations over five seeds.

What counts as success. Beating the encoder-level adversary means a target LAS gain larger than the seed standard deviation on at least three of the four target settings (PB, ZX, PC, VTB), together with a smaller post-first-error cascade. On Vietnamese, matching or exceeding 68.98 LAS with a linear-time parser and no dictionary would be a strong result. Landing within one point of it would still be meaningful, given the speed advantage.

Why not just…?

Why not just put the discriminator on the encoder, as the cross-lingual work does? This is the real threat. If the domain gap is mostly lexical, encoder alignment may capture nearly all of the gain. Evidence that a lexical fix is valuable comes from the domain-specific lower layers found by Semi-supervised Domain Adaptation for Dependency Parsing with Dynamic Matching Network. The head-to-head comparison and the cascade decomposition settle the question. If state alignment gives equal LAS and no reduction in post-first-error errors, our claim is wrong, and we would report encoder alignment plus exploration as the recommended recipe.

Why not just train with a dynamic oracle and skip adaptation? Exploration teaches recovery from source-style errors, but target errors occur in lexically different contexts. The exploration-only baseline measures exactly how much of the gap this closes. Its gains in Training Deterministic Parsers with Non-Deterministic Oracles are in-domain only.

Why not just use a graph-based parser, which has no cascades? For accuracy alone that may be the right answer, and we report it as a ceiling. The proposal targets settings where linear-time greedy parsing matters, such as long documents and streaming input. It asks how much of the graph-based advantage adaptation can recover at no inference cost.

Why not just self-train on the target? Self-training feeds the parser's cascaded errors back as labels, the accumulation documented by The Alpage Architecture at the SANCL 2012 Shared Task. The two methods are complementary, and we also test self-training initialized from our adapted parser.

Proposed Experiments

Chinese multi-domain. Train on the balanced news corpus of the NLPCC-2019 / CODT benchmarks, using unlabeled PB, ZX, and PC text. Evaluate UAS and LAS on each target test set. The semi-supervised results of Semi-supervised Domain Adaptation for Dependency Parsing (77.16 LAS on PB and 75.11 on ZX, using target labels) are cited only as an upper reference, not as a competitor.

Cross-lingual. Transfer from UD Chinese GSDSimp to Vietnamese VTB, comparing against the numbers above.

English sanity check. Evaluate on PTB Section 23 to confirm that adaptation does not hurt source accuracy. The reference is 92.2 UAS from Chen and Manning.

First decisive check: where the gain lands. The error decomposition should show state-level alignment reducing errors after the first mistake more than encoder alignment does.

Second decisive check: why exploration and matched $p$ are needed. The ablation with static-oracle source states should lose most of the gain, or even hurt on PC. A fixed mismatched $p$ should show the discriminator separating domains by error density. We will verify this with an off-gold-path probe.

Third decisive check: stability. Seed variance for state-level adversarial training should be no larger than for encoder-level training, directly testing the instability objection.