Error-Correcting Neural Sequence Prediction

James O'Neill, Danushka BollegalaarXiv 2019 · arXiv

TL;DR

This paper introduces ECOC-NSP, a method that replaces the computationally expensive softmax layer in neural sequence models with Error-Correcting Output Codes (ECOC). By representing words as binary strings with redundant bits, the authors achieve massive parameter compression and faster inference while introducing a novel "Latent Variable Mixture Sampling" technique to solve the long-standing problem of exposure bias.

The Challenge: Efficiency and Exposure Bias

In modern Natural Language Processing (NLP), predicting the next word in a sequence usually involves a softmax layer. This layer calculates a probability distribution over the entire vocabulary. When the vocabulary size ($|V|$) reaches tens or hundreds of thousands, this becomes a massive computational and memory bottleneck.

Furthermore, these models suffer from exposure bias. During training, models are typically given the "ground truth" previous word (a technique called teacher forcing). But at test time, the model must rely on its own previous predictions. If it makes one small mistake early on, that error compounds, leading to gibberish sequences.

The authors aim to create a model that is:

  1. Efficient: Reducing the decoder's parameter count.
  2. Robust: Handling prediction errors gracefully using error-correction principles.
  3. Generalizable: Mitigating the gap between training and inference (exposure bias).

Proposed Method: ECOC-NSP and LVMS

The core innovation is the move from 1-hot encoding to Error-Correcting Output Codes (ECOC).

  • ECOC-NSP: Instead of predicting a probability for every word, the model predicts a sequence of bits (a codeword). By adding redundant "error-check" bits, the model can still recover the correct word even if it flips a few bits during prediction.
  • Semantic Codebooks: Rather than assigning binary codes randomly, the authors use word embedding similarities. They arrange the codebook so that semantically similar words (like "car" and "automobile") have codewords with small Hamming distances. This ensures that if the model makes an error, it's likely to predict a synonym rather than a completely unrelated word.
  • Latent Variable Mixture Sampling (LVMS): To fight exposure bias, the authors propose mixing the "true" target bits with the model's "predicted" bits during training.
  • Differentiable LVMS: Sampling discrete bits is usually non-differentiable. The authors use the Gumbel-Softmax (or Concrete Distribution) trick to create a continuous relaxation of these bits, allowing the entire system to be trained via standard gradient descent.
Diagram of the ECOC-NSP architecture showing the relationship between predicted and target codewords.

Experimental Evaluation

The authors evaluated their approach on standard language modeling and text generation benchmarks including the Penn Treebank (PTB), WikiText-2, WikiText-103, and MSCOCO for image captioning.

Key Results

  • Massive Compression: On the Penn Treebank dataset, ECOC-NSP achieved performance nearly identical to a full softmax model while using only 40 bits (compared to a vocabulary of ~10,000 words).
  • Superior Generation: In image captioning (MSCOCO), the DLVMS-ECOC variant outperformed standard "Scheduled Sampling" and full softmax models across BLEU, ROUGE-L, and METEOR metrics.
  • Efficiency: The authors demonstrated that the model maintains high accuracy even when the decoder parameters are reduced to just 2% of their original size.
Validation and test perplexity across different datasets as a function of decoder parameters.

Conceptual Breakthroughs

  • Graceful Failure: By tying Hamming distance to semantic similarity, the model gains a "topological" understanding of the output space. Standard softmax treats all incorrect words as equally wrong; ECOC-NSP understands that some mistakes are "closer" to the truth than others.
  • Tunable Trade-offs: The length of the codeword ($|c|$) acts as a dial. You can use very short codes for maximum speed on mobile devices or longer codes with more error-correction bits for high-performance server applications.
  • Latent Space Correction: Most solutions for exposure bias operate on the final word tokens. This paper argues that correcting errors in the latent bit space is more efficient and provides a smoother training signal.

Limitations and Future Work

While promising, the approach has some constraints. If too many error-correction bits are used, convergence speed can suffer. Additionally, finding the mathematically optimal codebook for a specific language remains an open challenge. Finally, because ECOC doesn't naturally produce a standard probability distribution, converting results to "perplexity" for comparison might not fully capture the unique strengths of the bit-based approach.

Summary updated

BibTeX
@misc{oneill2019error,
  author = {James O'Neill and Danushka Bollegala},
  title = {{Error-Correcting Neural Sequence Prediction}},
  year = {2019},
  eprint = {1901.07002},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.07002},
}
Figure