Neural Particle Smoothing for Sampling from Conditional Sequence Models

Chu-Cheng Lin, Jason Eisner

Abstract

We introduce neural particle smoothing, a sequential Monte Carlo method for sampling annotations of an input string from a given probability model. In contrast to conventional particle filtering algorithms, we train a proposal distribution that looks ahead to the end of the input string by means of a right-to-left LSTM. We demonstrate that this innovation can improve the quality of the sample. To motivate our formal choices, we explain how our neural model and neural sampler can be viewed as low-dimensional but nonlinear approximations to working with HMMs over very large state spaces.

Introduction

In Natural Language Processing (NLP), many tasks involve labeling an input sequence $x$ with a corresponding tag sequence $y$ (e.g., part-of-speech tagging or named entity recognition). Ideally, these tasks utilize globally normalized models, which evaluate the probability of a sequence based on the entire input. While powerful, these models are often mathematically intractable because calculating the partition function requires summing over an exponential number of possible tag combinations.

Practitioners typically rely on beam search or particle filtering to navigate this space. However, beam search is prone to bias, and standard particle filters are "blind"—they sample tags one by one based only on the prefix of the input, ignoring the future context that is often already available in NLP tasks.

Neural Particle Smoothing: The Look-Ahead Mechanism

The core contribution of this work is Neural Particle Smoothing. Unlike traditional filtering, which only considers the past, this method treats the sampling process as a smoothing problem by incorporating the entire input sequence $x$ into the proposal distribution at every step $t$.

Neural Particle Smoothing uses a right-to-left LSTM to incorporate future context into the current sampling step.

As illustrated in the figure above, when deciding on a tag $y_t$ for the input $x_t$, the sampler does not just look at the history $G_{t-1}$. It also utilizes a "look-ahead" component $H_t$. This is achieved through:

  1. A Right-to-Left LSTM: This encoder processes the future input string ($x_{t:T}$) to provide context for the current decision.
  2. Neural Approximation of "Score-to-Go": In simple models like HMMs, one can calculate the exact probability of all possible future paths. For complex neural models, the authors use a neural network ($c_\phi$) to approximate this "logprob-to-go," acting as a heuristic that guides the sampler toward high-probability global sequences.

Training the Sampler

The neural sampler is trained to mimic the target model by minimizing a weighted combination of Inclusive KL Divergence (ensuring the sampler covers all high-probability regions) and Exclusive KL Divergence (ensuring the sampler does not waste resources on low-probability paths). This dual objective allows the sampler to be both robust and efficient.

Experimental Evaluation

The authors evaluated Neural Particle Smoothing across three distinct sequence labeling tasks:

  • English Stressed Syllable Tagging: Tagging phonemes with stress markers using the CMU Pronunciation Dictionary. This task is particularly suited for smoothing because English stress often depends on the remaining length of the word.
  • Chinese Social Media NER: Named Entity Recognition on noisy social media text.
  • String Source Separation: A synthetic task where two interleaved strings must be recovered (e.g., separating "FoBoar" back into "Foo" and "Bar").

Key Results

  • Efficiency: In the stress-tagging task, the smoothing sampler achieved the same performance as a standard particle filter while using only 25% of the particles.
  • Accuracy: Across all tasks, Neural Particle Smoothing consistently achieved lower KL divergence from the true model distribution compared to both standard filtering and beam search.
  • Robustness: The smoothing sampler rarely produced "junk" particles with low weights, making the traditional step of "resampling" (pruning low-weight hypotheses) less critical than it is in standard filters.

Conclusion

Neural Particle Smoothing bridges the gap between the expressive power of globally normalized neural models and the efficiency of sequential sampling. By viewing neural networks as nonlinear approximations of belief states in massive HMMs, the authors provide a principled way to use "future" information to guide "present" sampling decisions. Future work may involve joint training of the model and the sampler to further optimize performance in complex sequence-to-sequence tasks.

Summary updated

Abstract

We introduce neural particle smoothing, a sequential Monte Carlo method for sampling annotations of an input string from a given probability model. In contrast to conventional particle filtering algorithms, we train a proposal distribution that looks ahead to the end of the input string by means of a right-to-left LSTM. We demonstrate that this innovation can improve the quality of the sample. To motivate our formal choices, we explain how our neural model and neural sampler can be viewed as low-dimensional but nonlinear approximations to working with HMMs over very large state spaces.
BibTeX
@inproceedings{lin2018neural,
  author = {Chu-Cheng Lin and Jason Eisner},
  title = {{Neural Particle Smoothing for Sampling from Conditional Sequence Models}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2018},
  url = {https://openreview.net/forum?id=rk4cBQbO-H},
}
Figure