Benchmarking Approximate Inference Methods for Neural Structured Prediction

Proceedings of NAACL-HLT 2019, pages 3313–3324 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 3313 Benchmarking Approximate Inference Methods for Neural Structured Prediction Lifu Tu Kevin Gimpel Toyota Technological Institute at Chicago, Chicago, IL, 60637, USA {lifu,kgimpel}@ttic.edu Abstract Exact structured inference with neural net- work scoring functions is computationally challenging but several methods have been proposed for approximating inference. One approach is to perform gradient descent with respect to the output structure di- rectly (Belanger and McCallum, 2016). An- other approach, proposed recently, is to train a neural network (an “inference network”) to perform inference (Tu and Gimpel, 2018). In this paper, we compare these two families of inference methods on three sequence label- ing datasets. We choose sequence labeling because it permits us to use exact inference as a benchmark in terms of speed, accuracy, and search error. Across datasets, we demon- strate that inference networks achieve a better speed/accuracy/search error trade-off than gra- dient descent, while also being faster than ex- act inference at similar accuracy levels. We find further benefit by combining inference networks and gradient descent, using the for- mer to provide a warm start for the latter.1 1 Introduction Structured prediction models commonly involve complex inference problems for which finding ex- act solutions is intractable (Cooper, 1990). There are generally two ways to address this difficulty. One is to restrict the model family to those for which inference is feasible. For example, state-of- the-art methods for sequence labeling use struc- tured energies that decompose into label-pair po- tentials and then use rich neural network archi- tectures to define the potentials (Collobert et al., 2011; Lample et al., 2016; Ma and Hovy, 2016, inter alia). Exact dynamic programming algo- rithms like the Viterbi algorithm can be used for inference. 1Code is available at github.com/lifu-tu/ BenchmarkingApproximateInference The second approach is to retain computationally-intractable scoring functions but then use approximate methods for inference. For example, some researchers relax the struc- tured output space from a discrete space to a continuous one and then use gradient descent to maximize the score function with respect to the output (Belanger and McCallum, 2016). Another approach is to train a neural network (an “infer- ence network”) to output a structure in the relaxed space that has high score under the structured scoring function (Tu and Gimpel, 2018). This idea was proposed as an alternative to gradient descent in the context of structured prediction energy networks (Belanger and McCallum, 2016). In this paper, we empirically compare exact in- ference, gradient descent, and inference networks for three sequence labeling tasks. We train condi- tional random fields (CRFs) for sequence labeling with neural networks used to define the potentials. We choose a scoring function that permits exact inference via Viterbi so that we can benchmark the approximate methods in terms of search error in addition to speed and accuracy. We consider three families of neural network architectures to serve as inference networks: convolutional neural net- works (CNNs), recurrent neural networks …

Content truncated to 500 words