Neural Particle Smoothing for Sampling from Conditional Sequence Models

Proceedings of NAACL-HLT 2018, pages 929–941 New Orleans, Louisiana, June 1 - 6, 2018. c⃝2018 Association for Computational Linguistics Neural Particle Smoothing for Sampling from Conditional Sequence Models Chu-Cheng Lin and Jason Eisner Center for Language and Speech Processing Johns Hopkins University, Baltimore MD, 21218 {kitsing,jason}@cs.jhu.edu 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. 1 Introduction Many structured prediction problems in NLP can be reduced to labeling a length-T input string x with a length-T sequence y of tags. In some cases, these tags are annotations such as syntactic parts of speech. In other cases, they represent actions that incrementally build an output structure: IOB tags build a chunking of the input (Ramshaw and Marcus, 1999), shift-reduce actions build a tree (Yamada and Matsumoto, 2003), and finite-state transducer arcs build an output string (Pereira and Riley, 1997). One may wish to score the possible taggings us- ing a recurrent neural network, which can learn to be sensitive to complex patterns in the training data. A globally normalized conditional probability model is particularly valuable because it quantifies uncer- tainty and does not suffer from label bias (Lafferty et al., 2001); also, such models often arise as the predictive conditional distribution p(y | x) corre- sponding to some well-designed generative model p(x, y) for the domain. In the neural case, however, inference in such models becomes intractable. It is hard to know what the model actually predicts and hard to compute gradients to improve its predictions. In such intractable settings, one generally falls back on approximate inference or sampling. In the NLP community, beam search and importance sam- pling are common. Unfortunately, beam search con- siders only the approximate-top-k taggings from an exponential set (Wiseman and Rush, 2016), and importance sampling requires the construction of a good proposal distribution (Dyer et al., 2016). In this paper we exploit the sequential structure of the tagging problem to do sequential importance sampling, which resembles beam search in that it constructs its proposed samples incrementally—one tag at a time, taking the actual model into account at every step. This method is known as particle filtering (Doucet and Johansen, 2009). We extend it here to take advantage of the fact that the sampler has access to the entire input string as it constructs its tagging, which allows it to look ahead or—as we will show— to use a neural network to approximate the effect of lookahead. Our resulting method is called neural particle smoothing. 1.1 What this paper provides For …

Content truncated to 500 words