A n E xploration of A rbitrary- O rder S equence L abeling via E nergy- B ased I nference N etworks (2020)

Abstract: Many tasks in natural language processing involve predicting structured outputs, e.g., sequence labeling, semantic role labeling, parsing, and machine translation. Researchers are increasingly applying deep representation learning to these problems, but the structured component of these approaches is usually quite simplistic. In this work, we propose several high-order energy terms to capture complex dependencies among labels in sequence labeling, including several that consider the entire label sequence. We use neural parameterizations for these energy terms, drawing from convolutional, recurrent, and self-attention networks. We use the framework of learning energy-based inference networks (Tu and Gimpel, 2018) for dealing with the difficulties of training and inference with such models. We empirically demonstrate that this approach achieves substantial improvement using a variety of high-order energy terms on four sequence labeling tasks, while having the same decoding speed as simple, local classifiers. We also find high-order energies to help in noisy data conditions.

## introduction conditional random fields (crfs; @xcite have been shown to perform well in various sequence labeling tasks. recent work uses rich neural network architectures to define the "unary" potentials, i.e., terms that only consider a single position's label at a time @xcite @xcite . however, "binary" potentials, which consider pairs of adjacent labels, are usually quite simple and may consist solely of a parameter or parameter vector for each unique label transition. models with unary and binary potentials are generally referred to as "first order" models. a major challenge with crfs is the complexity of training and inference, which are quadratic in the number of output labels for first order models and grow exponentially when higher order dependencies are considered. this explains why the most common type of crf used in practice is a first order model, also referred to as a "linear chain" crf. one promising alternative to crfs is structured prediction energy networks (spens; @xcite , which use deep neural networks to parameterize arbitrary potential functions for structured prediction. while spens also pose challenges for learning and inference, @xcite proposed a way to train spens jointly with "inference networks", neural networks trained to approximate structured arg max inference. in this paper, we leverage the frameworks of spens and inference networks to explore highorder energy functions for sequence labeling. naively instantiating high-order energy terms can lead to a very large number of parameters to learn, so we instead develop concise neural parameterizations for high-order terms. in particular, we draw from vectorized kronecker products, convolutional networks, recurrent networks, and self-attention. we also consider "skip-chain" connections @xcite with various skip distances and ways of reducing their total parameter count for increased learnability. our experimental results on four sequence labeling tasks show that a range of high-order energy functions can yield performance improvements. while the optimal energy function varies by task, we find strong performance from skip-chain terms with short skip distances, convolutional networks with filters that consider label trigrams, and recurrent networks and self-attention networks that consider large subsequences of labels. we also demonstrate that modeling high-order dependencies can lead to significant performance improvements in the setting of noisy training and test sets. visualizations of the high-order energies show various methods capture intuitive structured dependencies among output labels. throughout, we use inference networks that share the same architecture as unstructured classifiers for sequence labeling, so test time inference speeds are unchanged between local models and our method. enlarging the inference network architecture by adding one layer leads consistently to better results, rivaling or improving over a bilstm-crf baseline, suggesting that training efficient inference networks with high-order energy terms can make up for errors arising from approximate inference. while we focus on sequence labeling in this paper, our results show the potential of developing high-order structured models for other nlp tasks in the future. ## energy functions our experiments in this paper consider sequence labeling tasks, so the input x is a length-t sequence of tokens where x t denotes the token at position t. the output y is a sequence of labels also of length t . we use y t to denote the output label at position t, where y t is a vector of length l (the number of labels in the label set) and where y t,j is the jth entry of the vector y t . in the original output space y(x), y t,j is 1 for a single j and 0 for all others. in the relaxed output space y r (x), y t,j can be interpreted as the probability of the tth position being labeled with label j. we use the following energy: ## related work linear chain crfs @xcite , which consider dependencies between at most two adjacent labels or segments, are commonly used in practice @xcite @xcite . there have been several efforts in developing efficient algorithms for handling higher-order crfs. @xcite developed an efficient decoding algorithm under the assumption that all high-order features have non-negative weights. some work has shown that high-order crfs can be handled relatively efficiently if particular patterns of sparsity are assumed @xcite . @xcite proposed an approximate crf using coarse-to-fine decoding and early updating. loopy belief propagation @xcite has been used for approximate inference in high-order crfs, such as skip-chain crfs @xcite , which form the inspiration for one category of energy function in this paper. crfs are typically trained by maximizing conditional log-likelihood. even assuming that the graph structure underlying the crf admits tractable inference, it is still time-consuming to compute the partition function. margin-based methods have been proposed @xcite to avoid the summation over all possible outputs. similar losses are used when training spens @xcite , including in this paper. the energybased inference network learning framework has been used for multi-label classification @xcite , non-autoregressive machine translation @xcite , and previously for sequence labeling @xcite . moving beyond crfs and sequence labeling, there has been a great deal of work in the nlp community in designing non-local features, often combined with the development of approximate algorithms to incorporate them during inference. these include n-best reranking @xcite , beam search (lowerre, 1976), loopy belief propagation @xcite , gibbs sampling @xcite , stacked learning @xcite , sequential monte carlo algorithms @xcite , dynamic programming approximations like cube pruning @xcite , dual decomposition @xcite , and methods based on black-box optimization like integer linear programming @xcite . these methods are often developed or applied with particular types of non-local energy terms in mind. by contrast, here we find that the framework of spen learning with inference networks can support a wide range of high-order energies for sequence labeling. ## experimental setup we perform experiments on four tasks: twitter partof-speech tagging (pos), named entity recognition (ner), ccg supertagging (ccg), and semantic role labeling (srl). ## results parameterizations for high-order energies. we first compare several choices for energy functions within our inference network learning framework. in section 3.3, we considered several ways to define the high-order energy function f . we compare performance of the parameterizations on three tasks: pos, ner, and ccg. the results are shown in the following experiment with tlm energies, we always use it with this "all" setting. self-attention (s-att) also shows better performance with larger m . however, the results for ner are not as high overall as for other energy terms. overall, there is no clear winner among the four types of parameterizations, indicating that a variety of high-order energy terms can work well on these tasks, once appropriate window sizes are chosen. we do note differences among tasks: ner benefits more from larger window sizes than pos. comparing structured energy terms. above we compared parameterizations of the high-order energy terms. in the richer energy terms tend to perform better than linear chain, at least for most tasks and energies. the skip-chain energies benefit from relatively large m values, i.e., 3 or 4 depending on the 4 m values are tuned based on dev sets. tuned m values for pos/ner/ccg/srl: skip-chain: 3/4/3/3; vkp: 2/3/2/2; cnn: 2/2/2/2; tlm: whole sequence; s-att: 8/8/8/8. comparison using deeper inference networks. we observe that inference networks trained with skip-chain energies and high-order energies achieve better results than bilstm-crf on the three datasets (the viterbi algorithm is used for exact inference for bilstm-crf). this indicates that adding richer energy terms can make up for approximate inference during training and inference. moreover, a 2-layer bilstm is much cheaper computationally than viterbi, especially for tasks with large label sets. ## analysis of learned energies in this section, we visualize our learned energy functions for ner to see what structural dependencies among labels have been captured. figure 1 visualizes two matrices in the skipchain energy with @xmath2. we can see strong associations among labels in neighborhoods from w 1 . for example, b-org and i-org are more likely to be followed by e-org. the w 3 matrix shows a strong association between i-org and e-org, which implies that the length of organization names is often long in the dataset. for the vkp energy with @xmath3, figure 2 shows the learned matrix when the first label is b-per, showing that b-per is likely to be followed by "i-per e-per", "e-per o", or "i-per i-per". in order to visualize the learned cnn filters, ## conclusion we explore arbitrary-order models with different neural parameterizations on sequence labeling tasks via energy-based inference networks. this approach achieve substantial improvement using high-order energy terms, especially in noisy data conditions, while having same decoding speed as simple local classifiers.