An Exploration of Arbitrary-Order Sequence Labeling via Energy-Based Inference Networks

Lifu Tu, Tianyu Liu, Kevin Gimpel

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

Sequence labeling—the task of assigning tags such as Part-of-Speech (POS) or Named Entity (NER) labels to a string of words—is a fundamental component of natural language processing. For decades, the Conditional Random Field (CRF) has been the standard model for this task. However, standard CRFs are typically "first-order," meaning they only consider dependencies between a tag and its immediate neighbor.

While higher-order relationships (e.g., trigrams or long-range dependencies) are known to exist, modeling them in traditional CRFs is computationally expensive. The complexity of finding the optimal label sequence (inference) grows exponentially with the order of the model, forcing a trade-off between model expressiveness and computational efficiency. This research aims to break this trade-off by introducing a framework that captures complex, high-order label dependencies without the associated exponential cost.

Methodology: Energy-Based Inference Networks

The proposed approach leverages Structured Prediction Energy Networks (SPENs). Instead of calculating explicit probabilities, the model defines an energy function $E(x, y)$ for an input $x$ and a label sequence $y$. The objective is to find the sequence $y$ that minimizes this energy.

To overcome the "inference bottleneck" associated with high-order models, the authors employ Inference Networks. Rather than using expensive algorithms like Viterbi or iterative optimization at test time, a separate neural network is trained to directly approximate the label sequence that minimizes the energy. This allows the model to maintain the inference speed of a simple local classifier.

Computational complexity comparison showing that energy-based inference networks match the inference speed of local classifiers.

Several novel neural parameterizations for high-order energy terms are explored:

  • Vectorized Kronecker Product (VKP): Models $M$-th order dependencies using compact label embeddings.
  • CNN Energies: Captures local patterns like trigrams using convolutional filters over label sequences.
  • Tag Language Models (TLM): Scores sequences based on a learned language model of the tags.
  • Self-Attention (S-Att): Captures global, long-range dependencies across the entire sequence.
  • Skip-Chain Energies: Models dependencies between labels at a fixed distance $M$.

Experimental Setup

The framework was evaluated on four diverse benchmarks:

  1. Twitter POS Tagging: Noisy social media text.
  2. Named Entity Recognition (NER): CoNLL 2003 English dataset.
  3. CCG Supertagging: Syntactic tagging using CCG-bank.
  4. Semantic Role Labeling (SRL): CoNLL 2005 shared task (WSJ and Brown corpora).

Results and Discussion

Performance Gains

The proposed models consistently outperformed BiLSTM and CRF baselines across all tasks. As shown in the results below, the high-order models achieved significant improvements. For instance, on the NER task, the Skip-Chain model achieved an F1 score of 86.7, a gain of 0.8 points over the Linear Chain (CRF) baseline.

Performance comparison across POS, NER, CCG, and SRL tasks, demonstrating consistent improvements over baselines.

The framework is also compatible with modern pre-trained models. Integrating high-order skip-chain energies into a BERT-based architecture improved NER performance from 92.13 to 92.46 F1.

Key Insights

  • Efficiency: Despite the inclusion of high-order logic, decoding speed remains identical to a standard BiLSTM classifier ($O(T*L)$), successfully avoiding the $O(L^M)$ complexity of traditional high-order Viterbi decoding.
  • Robustness to Noise: High-order energies prove particularly effective in noisy data conditions. When input words are randomly replaced with "UNK" tokens, high-order models significantly outperform first-order ones, suggesting that the model relies more on the learned "grammar" of labels when input features are unreliable.
  • Task-Specific Structure: No single energy function is optimal for all tasks. NER benefits from larger windows and global context, while POS tagging is more localized. CNN-based energies with a window size of 3 (capturing trigrams) emerged as a consistently strong baseline.

Conclusion

This work demonstrates that high-order label dependencies can be effectively modeled in sequence labeling tasks without sacrificing inference speed. By combining neural energy functions with inference networks, the proposed framework achieves state-of-the-art performance and increased robustness to noise. Future research may extend this energy-based approach to more complex structured outputs like dependency parsing or machine translation.

Summary updated

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.
BibTeX
@inproceedings{tu2020exploration,
  author = {Lifu Tu and Tianyu Liu and Kevin Gimpel},
  title = {{An Exploration of Arbitrary-Order Sequence Labeling via Energy-Based Inference Networks}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=GZTRQWMK8g},
}
Figure