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

Sampling from complex probability distributions is a cornerstone of modern NLP, yet for globally normalized sequence models, it remains a daunting computational challenge. Globally normalized models are often preferred because they avoid the "label bias" problem inherent in locally normalized models. However, they are mathematically intractable—calculating the total probability requires summing over an exponential number of possible sequences.

Standard tools like beam search only find the top-$k$ sequences, failing to capture the full diversity of the model. Particle filtering (a type of sequential importance sampling) is better for sampling, but it is typically "blind." It builds the output sequence $y$ from left to right, only considering the input $x$ it has seen so far. This lack of foresight often leads the sampler into low-probability regions of the state space.

Methods

The core innovation of this work is the transition from filtering (looking only at the past) to smoothing (looking at both the past and the future).

Illustration of the neural particle smoothing process, showing the lookahead mechanism $H_t$ estimating future sequence probabilities.

The proposed Neural Particle Smoothing method incorporates several key components:

  1. The Lookahead Mechanism: Since the entire input string $x$ is usually available in NLP tasks, the authors use a right-to-left LSTM to encode the "future" of the input.
  2. The "Logprob-to-go": Similar to the heuristic $h$ in A* search, the model trains a neural network to estimate $H_t$—the total probability of all possible ways to complete the sequence from the current point.
  3. Neural OOHMMs: The authors demonstrate that their neural model is essentially a non-linear, low-dimensional approximation of an "Output-Output Hidden Markov Model" (OOHMM).
  4. Hybrid Training: The sampler is trained using a combination of inclusive KL divergence (to ensure coverage of high-probability sequences) and exclusive KL divergence (to minimize time spent on low-probability sequences).

Experimental Setup

The method was evaluated on three distinct tasks:

  • English Stressed Syllable Tagging: Predicting stress patterns for phoneme sequences using the CMU Pronunciation Dictionary. This task requires lookahead because English stress often depends on the remaining syllables in a word.
  • Chinese Social Media NER: A named entity recognition task using social media data.
  • String Source Separation: A challenging task where two strings are interleaved, and the model must disentangle them.

Results and Discussion

Across all tasks, Neural Particle Smoothing (PS) consistently outperformed standard Particle Filtering (PF) at every ensemble size ($M$). On the stressed syllable task, the smoothing sampler achieved significantly lower "offset KL divergence" compared to both filtering and beam search.

A key insight is that the smoothing sampler is more computationally efficient. It often achieves the same KL divergence as a standard particle filter while using only 1/4th the number of particles. Furthermore, while resampling (pruning low-weight particles) helps standard filters, the smoothing sampler is so accurate in its proposals that it often maintains high performance without it.

Conclusion

Neural Particle Smoothing demonstrates that "peeking" at the future input can drastically reduce the variance of a sequential sampler. While currently restricted to tasks where the input and output lengths are equal ($|y| = |x|$), future work aims to extend this to sequence-to-sequence (seq2seq) models. This would broaden the application to tasks like machine translation or summarization, potentially involving joint end-to-end training of the generative model and the sampler.

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