AIN : Fast and Accurate Sequence Labeling with Approximate Inference Network (2020)

Abstract: The linear-chain Conditional Random Field (CRF) model is one of the most widely-used neural sequence labeling approaches. Exact probabilistic inference algorithms such as the forward-backward and Viterbi algorithms are typically applied in training and prediction stages of the CRF model. However, these algorithms require sequential computation that makes parallelization impossible. In this paper, we propose to employ a parallelizable approximate variational inference algorithm for the CRF model. Based on this algorithm, we design an approximate inference network that can be connected with the encoder of the neural CRF model to form an end-to-end network, which is amenable to parallelization for faster training and prediction. The empirical results show that our proposed approaches achieve a 12.7-fold improvement in decoding speed with long sentences and a competitive accuracy compared with the traditional CRF approach.

## introduction sequence labeling assigns each token with a label in a sequence. tasks such as named entity recognition (ner) @xcite , part-of-speech (pos) tagging @xcite and chunking @xcite can all be formulated as sequence labeling tasks. bilstm-crf @xcite @xcite is one of the most successful neural sequence labeling architectures. it feeds pretrained (contextual) word representations into a single layer bi-directional lstm (bilstm) encoder to extract contextual features and then feeds these features into a crf @xcite decoder layer to produce final predictions. the crf layer is a linear-chain structure that models the relation between neighboring labels. in the traditional crf approach, exact probabilistic inference algorithms such as the forward-backward and viterbi algorithms are applied for training and prediction respectively. in many sequence labeling tasks, the crf layer leads to better results than the simpler method of predicting each label independently. in practice, we sometimes require very fast sequence labelers for training (e.g., on huge datasets like wikiann @xcite ) and prediction (e.g. for low latency online serving). the bilstm encoder and the crf layer both contain sequential computation and require o(n) time over n input words even when parallelized on gpu. a common practice to improve the speed of the encoder is to replace the bilstm with a cnn structure @xcite , distill larger encoders into smaller ones @xcite or in other settings @xcite @xcite . the crf layer, however, is more difficult to replace because of its superior accuracy compared with faster alternatives in many tasks. in order to achieve sublinear time complexity on the crf layer, we must parallelize the crf prediction over the tokens. in this paper, we apply mean-field variational inference (mfvi) to approximately decode the linear-chain crf. mfvi iteratively passes messages among neighboring labels to update their distributions locally. unlike the exact probabilistic inference algorithms, mfvi can be parallelized over different positions in the sequence, achieving time complexity that is constant in n with full parallelization. previous work @xcite showed that such an algorithm can be unfolded as an rnn for grid crf struc- factorized second-order crf 𝑌𝑌 1 𝑌𝑌 2 𝑌𝑌 3 𝑌𝑌 4 𝑌𝑌 5 linear-chain crf 𝑌𝑌 1 𝑌𝑌 2 𝑌𝑌 3 𝑌𝑌 4 𝑌𝑌 5 unary factor binary factor … figure 1: factor graphs of different crfs. y i is the random variable representing the i-th label. ## approaches given an input sequence with n tokens @xmath0, x 2 , . . . , x n ] and a corresponding label sequence @xmath1, y 2 , . . . , y n ] with a label set of size l, the conditional probability of y given x specified by a crf with position-wise factorization is: in the simplest case, the potential function is just a softmax function that outputs the distribution of each label independently. we call it the maxent approach. in a typical linear-chain crf, the potential function is decomposed into a unary potential ψ u and a binary potential ψ b (called the emission and transition functions respectively): ## conclusion in this paper, we propose approximate inference networks (ain) that use mean-field variational inference (mfvi) instead of exact probabilistic inference algorithms such as the forward-backward and viterbi algorithms for training and prediction on the conditional random field for sequence labeling. the mfvi algorithm can be unfolded as a recurrent neural network and connected with the encoder to form an end-to-end neural network. ains can be parallelized over different positions in the sequence. empirical results show that ains are significantly faster than traditional crf and do very well in tasks that require more local information. our approaches achieve competitive accuracy on 4 tasks with 15 datasets over three encoder types. our code is publicly available at https://github.com/alibaba-nlp/ain . language treebank de gsd en ewt es gsd fr sequoia it postwita nl lassysmall sl sst sv lines