Sequence taggers that assign one of many labels to every word, such as grammar-category ("supertag") taggers with over a thousand tags, face a choice. A conditional random field (CRF) is a classifier that scores whole label sequences and captures which label tends to follow which. It needs an $L \times L$ table of label-to-label scores, which costs $O(L^2)$ work per word. It also only looks one step back. Cheaper alternatives drop some of that structure. They replace the table with independent binary sub-taggers, tie rare transitions together, or skip transitions entirely. We propose a different replacement. Between the labels sits a small set of hidden on/off switches, each with its own memory across time. Each label is tied to a learned pattern over the switches, and the number of switches is grown from data rather than fixed in advance. The model is trained discriminatively, meaning it directly maximizes the probability of the correct labels.
The idea works in two ways at once. Sixteen switches cost about $16L$ per word instead of $L^2$. Because each switch persists across words, the model can also carry information such as "an argument is still pending" further than one step, which a first-order CRF cannot. Prior evidence suggests hidden factors like these pay off on large label sets. A generative two-layer model that tied supertags to part-of-speech (POS) tags lifted accuracy on ambiguous words from 17.23% to 58.07% with 100 training sentences (Supertagging with Factorial Hidden Markov Models). That result, however, needed gold POS annotation and a generative model that trails discriminative taggers when labeled data is plentiful. We ask whether a discriminatively trained model can discover useful anchor factors on its own, without POS labels.
Core Claim
A CRF whose label transitions pass through $M$ hidden binary Markov chains, with $M$ grown from data, can make three gains on a 1,200-label supertagging task. It can match or beat a full first-order CRF at roughly $M/L$ of the transition cost. It can beat a low-rank transition matrix with the same number of parameters, because the chains keep memory beyond one step. And its chains will align with syntactic categories like POS without ever seeing them. The claim fails if the low-rank matrix matches it, or if a plain neural tagger with no transitions matches it at every training-set size. Either outcome is informative.
Model
Each word $t$ has a label $y_t \in \{1..L\}$ and hidden switches $z_t \in \{0,1\}^M$. The model scores a labeled sequence as
$$ S(y,z,x)=\sum_t \Big[\, s_\theta(x)_{t,y_t} + \sum_{m=1}^{M} W_{y_t m}\, z_t^m + \sum_{m=1}^{M} A^m_{z_{t-1}^m z_t^m} \Big], $$
where the terms are as follows. $s_\theta(x)_{t,y}$ is an encoder's score for label $y$ at word $t$. $W_{ym}$ is label $y$'s learned affinity for switch $m$, which acts as a soft, learned binary code. $A^m$ is the $2\times 2$ persistence table of switch $m$. The model then sets $p(y\mid x)=\sum_z e^{S}/Z(x)$.
This structure has a useful property. When the labels are fixed to their gold values, the $M$ chains become independent. The numerator of the likelihood is therefore exact, at cost $O(TM)$ via $M$ small forward-backward passes over the $T$ words.
The normalizer couples labels and switches. We approximate it with structured mean-field, which runs each chain exactly and treats label beliefs per word. Each round costs $O(LM)$ per word. For $M \le 10$ exact inference is still feasible: sum out $y$ per switch configuration, then run a factored forward pass over $2^M$ states. We will use this exact computation to measure how much the approximation biases training and decoding. Decoding takes the argmax of mean-field label marginals, refined by coordinate ascent.
To set the number of switches, we borrow the spirit of the unbounded binary chains of The Infinite Factorial Hidden Markov Model, which discovers how many independent sources exist but is generative, unsupervised, and slow to sample. We use a cheaper rule. A group-sparsity penalty on the columns of $W$ switches off unused chains. A new chain is added whenever held-out conditional likelihood improves by more than a threshold.
How This Differs From Prior Work
Four lines of work frame the proposal. Factored Latent-Dynamic Conditional Random Fields already trains parallel hidden layers discriminatively and beat LSTMs by about 4% on gesture segmentation and 2% on Opportunity. It supplies our method's discriminative training recipe. However, it fixes the number of layers and states by hand and tests only 2 to 5 labels.
The Infinite Factorial Hidden Markov Model recovered exactly 5 speakers where a static method found 9. It motivates growing the chain count, but it has no labels. Max-Margin Infinite Hidden Markov Models makes an unbounded-state model discriminative, reaching 54.0% on 12-class RGBD-HuDaAct. It keeps a single categorical hidden state and classifies whole sequences rather than words. We keep neither restriction.
On the label-scaling side, Scaling Conditional Random Fields Using Error-Correcting Codes splits labels into fixed random bit codes decoded by independent binary CRFs. Revisiting Output Coding for Sequential Supervised Learning shows that independent bits miss transition structure and need cascading to recover it, a gain of over 10 points on 134-label Nettalk. This negative result constrains our design. Our codes are learned rather than random, and they are coupled through joint inference rather than decoded bit by bit. The bits are also hidden variables with their own dynamics rather than a relabeling of observed outputs.
Efficient Inference in Large Conditional Random Fields and Piecewise pseudolikelihood make first-order CRFs cheaper to run and train. They leave the model first-order, and we do not.
Research Program
We will build the model on two encoders. The first uses sparse lexical features, comparable to the older CCGbank and Penn Treebank results in the file. The second is a BiLSTM encoder, representative of current practice.
We will run four analyses. First, we measure accuracy against transition cost as $M$ and $L$ vary. Second, we measure the bias of mean-field relative to exact inference for $M\le 10$. Third, we test whether chains track syntax, via mutual information between each learned chain and gold POS tags, which the model never sees. Fourth, we test long-range memory on a synthetic tagging task where the label at $t$ depends on the label at $t-k$. A first-order CRF, full or low-rank, provably cannot solve that task.
Baselines
The naive reference is a per-word softmax tagger on the same encoder with no transition model at all. The inference-time variant adds rule-based transition masks as in Constrained Decoding for Computationally Efficient Named Entity Recognition Taggers. If the chain model cannot beat this at some training-set size, the transitions are not earning their cost.
The full first-order CRF is the accuracy reference. It is expensive but feasible on a GPU at $L\approx1{,}200$. File numbers for it include 95.78% on Penn Treebank POS and 89.78 F1 on CoNLL 2003 NER, both from the ECOC paper. We reproduce it on our own encoders rather than rely on those figures.
The strongest existing large-label methods are the following. For output codes, the ECOC-CRF reports 96.03% on Penn Treebank POS and needed 220MB of memory, against an estimated 17GB for a full CRF, on the 118-label joint chunking-plus-POS task (Scaling Conditional Random Fields Using Error-Correcting Codes). We also run cascaded codes (c-SECOC). For hidden factors, the POS-supervised factorial model FHMMB reports 86.21% on full CCGbank and 58.07% on ambiguous supertags with 100 sentences (Supertagging with Factorial Hidden Markov Models). Tied potentials and piecewise pseudolikelihood complete the set.
We also add a low-rank transition CRF, $T=UV^\top$, with rank chosen to match our parameter count. We found no reported result on Lacuna for low-rank transition CRFs on these benchmarks, so we will implement it ourselves.
Fairness rules apply across all systems. Every system uses the same encoder, splits, and tokenization. Each gets an equal hyperparameter budget of 30 validation trials and an equal GPU-hour cap. Results are reported over 5 seeds with standard deviation, which responds to the run-to-run instability noted for LSTMs in the FLDCRF paper.
Three ablations isolate the key ingredients. Setting $A^m=0$ removes chain memory and leaves a learned soft code. Fixing $M$ by validation sweep removes growth. Clamping one chain to gold POS gives a discriminative analogue of FHMMB and serves as an upper bound on what discovered anchors could deliver.
Beating the field means three things. On full CCGbank, the model must be within 0.3 points of the full CRF, or above it, at under 5% of its transition cost. It must also clearly exceed the low-rank CRF and the no-memory ablation. With 100 CCGbank sentences, without POS supervision, it must exceed FHMMB's 58.07% on ambiguous supertags.
Why not just…?
Why not just use a neural tagger with a softmax, as practitioners already do? This is the most serious threat when labeled data is plentiful, because a bidirectional encoder already sees long context. The evidence against it is regime-specific. Factored hidden layers beat LSTMs with lower variance on small sensor datasets (Factored Latent-Dynamic CRFs), and structure mattered most with 100 supertagging sentences. We settle it with learning curves from 100 sentences to full CCGbank on a shared encoder. If the softmax catches up at full data, we will report the chains as a low-data method only.
Why not just factor the transition matrix into low rank? This matches our cost and is simpler. It is equivalent to a single categorical hidden state that is redrawn at every word, so it cannot carry information across several words. The synthetic $t-k$ task and the matched-parameter CCGbank comparison decide this directly. If low-rank ties us on CCGbank, the memory claim fails for real data, and we will say so.
Why not just use error-correcting output codes, possibly cascaded? Independent codes lose transition structure (Revisiting Output Coding). Cascading patches this with a fixed bit order and retraining in sequence. Our no-memory ablation is essentially a learned, jointly decoded code. Comparing it with ECOC and c-SECOC separates the value of learning the code from the value of giving it dynamics.
Why not just sweep the number of chains on validation data? This may well select as good an $M$ as our growth rule, so the sweep is included as an ablation. The growth rule has to justify itself on cost: it should reach the sweep's accuracy in fewer total training runs. If it cannot, we drop it in favor of the sweep.
Decisive Checks
The work stands or falls on four comparisons. The first is chains versus low-rank transitions at equal parameter count, on CCGbank, the 118-label joint task, and Nettalk. The second is chains versus the no-memory ablation, which shows whether persistence matters. The third is POS mutual information of discovered chains against random chains, which shows whether the anchoring effect reported by Supertagging with Factorial Hidden Markov Models can be found without supervision. The fourth is the gap between exact and mean-field training for $M\le10$. If mean-field bias exceeds the accuracy gains, the inference scheme must change before any larger claim is made.
References
- Supertagging with Factorial Hidden Markov Models
- The Infinite Factorial Hidden Markov Model
- Factored Latent-Dynamic Conditional Random Fields for single and multi-label sequence modeling
- Max-Margin Infinite Hidden Markov Models
- Scaling Conditional Random Fields Using Error-Correcting Codes
- Revisiting Output Coding for Sequential Supervised Learning
- Efficient Inference in Large Conditional Random Fields
- Piecewise pseudolikelihood for efficient training of conditional random fields
- Constrained Decoding for Computationally Efficient Named Entity Recognition Taggers