Embedded-State Latent Conditional Random Fields for Sequence Labeling

Dung Thai, Sree Harsha Ramesh, Shikhar Murty, Luke Vilnis, Andrew McCallumCoNLL 2018 · OpenReview

TL;DR

This paper introduces the "Embedded-State Latent CRF" (EL-CRF), a novel graphical model for sequence labeling that combines the power of deep neural networks for feature extraction with a more expressive global structure. By incorporating a large number of latent states and learning their transitions through low-rank embeddings, the EL-CRF can capture complex, non-local output constraints that are missed by standard linear-chain CRFs, leading to improved performance on challenging information extraction tasks.

What Problem Does This Paper Address?

Information extraction tasks, like identifying specific pieces of information within text (e.g., names, dates, diagnoses), are often framed as sequence labeling problems. While deep neural networks (like LSTMs) have become excellent at extracting rich, context-aware features from the input text, they often struggle to enforce global consistency and complex relationships between the output labels. Traditional approaches often use a simple "linear-chain CRF" to enforce local dependencies between adjacent labels. However, this simple structure fails to capture more intricate, non-local constraints, such as a specific field appearing only once, or its presence being dependent on another distant field. This limitation hinders performance on tasks with complex, structured outputs.

Methods

The core innovation of this paper is the Embedded-State Latent CRF (EL-CRF). It builds upon the standard deep neural network + linear-chain CRF architecture but introduces a crucial enhancement: a sequence of latent hidden states ($z_t$) for each output label ($y_t$).

Here's how it works:

  • Input Featurization: Similar to existing methods, the input text is first processed by a bidirectional LSTM to generate contextualized feature vectors ($f_t$) for each token.
  • Latent States: Instead of directly mapping input features to output labels, the EL-CRF introduces a much larger set of possible hidden states ($M$) compared to the number of output labels ($N$). This allows for a richer representation of the underlying structure.
  • Factorized Transition Log-Potentials: A key challenge with a large number of hidden states is the explosion of parameters for modeling transitions between them ($z_t \to z_{t+1}$). To combat this and prevent overfitting, the authors propose learning these transitions using low-rank matrices. Specifically, they factorize the transition log-potential matrix into two smaller matrices ($U$ and $V$), effectively learning an "embedding space" for the hidden states. This allows them to use a large number of states without a prohibitive parameter count.
  • Global Inference: The model allows for exact inference (finding the most likely sequence of labels) using a modified forward-backward algorithm, similar to a standard linear-chain CRF. This is possible because the mapping from hidden states to output labels is deterministic.

Datasets

The authors evaluate their proposed model on two datasets:

  • UMass Citations Dataset: This dataset is used for citation field extraction and features a hierarchical label space with complex, non-local constraints.
  • CLEF eHealth Dataset: This dataset focuses on clinical information extraction from nursing handover records, also featuring hierarchical labels and requiring the model to learn constraints from a relatively small amount of data.

Key Insights and Ideas

  • Bridging the Gap Between Local and Global: The EL-CRF effectively bridges the gap between powerful local feature extraction by RNNs and the need for global structural consistency in output labels.
  • Latent States for Expressivity: Introducing latent states significantly increases the model's capacity to represent complex dependencies that are not directly apparent in the input features.
  • Low-Rank Embeddings for Scalability: The clever use of low-rank factorization for transition log-potentials is crucial for making the model scalable to a large number of latent states without overfitting, enabling representation learning in the output space.
  • Interpretable Latent Structure: The paper suggests that the learned embeddings of hidden states can reveal interpretable structures, offering insights into the relationships between different output labels.

Key Results

  • Improved Performance: The EL-CRF consistently outperforms the baseline BiLSTM+CRF model on both datasets.
  • On the UMass Citations dataset, the EL-CRF achieved an F1 score of 95.18, compared to 95.07 for the baseline.
  • On the CLEF eHealth dataset, the EL-CRF achieved an F1 score of 70.32, a significant improvement over the baseline's 68.66.
  • Larger Gains on Smaller Datasets: The improvements were more pronounced on the smaller CLEF eHealth dataset, highlighting the benefit of the EL-CRF's parsimonious approach to output representation learning when data is scarce.
  • Evidence of Constraint Learning: Qualitative analysis showed that the EL-CRF successfully learned and enforced non-local constraints, such as preventing certain tags from appearing together or ensuring a specific tag appears only once per document, which the baseline CRF failed to do.

Limitations and Future Work

  • Exact Inference Complexity: While the model allows for exact inference, the computational cost can still be significant with a very large number of hidden states.
  • Future Work: The authors suggest exploring:
  • Applying the model to even larger datasets with more intricate dependencies.
  • Introducing multiple latent states per time step to further increase expressivity, potentially at the cost of exact inference.
  • Investigating approximate inference methods (like expectation propagation) to speed up computation for larger models.
  • Further exploring the interpretability of the learned latent state embeddings.

Summary updated

Abstract

Complex textual information extraction tasks are often posed as sequence labeling or \emph{shallow parsing}, where fields are extracted using local labels made consistent through probabilistic inference in a graphical model with constrained transitions. Recently, it has become common to locally parametrize these models using rich features extracted by recurrent neural networks (such as LSTM), while enforcing consistent outputs through a simple linear-chain model, representing Markovian dependencies between successive labels. However, the simple graphical model structure belies the often complex non-local constraints between output labels. For example, many fields, such as a first name, can only occur a fixed number of times, or in the presence of other fields. While RNNs have provided increasingly powerful context-aware local features for sequence tagging, they have yet to be integrated with a global graphical model of similar expressivity in the output distribution. Our model goes beyond the linear chain CRF to incorporate multiple hidden states per output label, but parametrizes their transitions parsimoniously with low-rank log-potential scoring matrices, effectively learning an embedding space for hidden states. This augmented latent space of inference variables complements the rich feature representation of the RNN, and allows exact global inference obeying complex, learned non-local output constraints. We experiment with several datasets and show that the model outperforms baseline CRF+RNN models when global output constraints are necessary at inference-time, and explore the interpretable latent structure.
BibTeX
@inproceedings{thai2018embedded,
  author = {Dung Thai and Sree Harsha Ramesh and Shikhar Murty and Luke Vilnis and Andrew McCallum},
  title = {{Embedded-State Latent Conditional Random Fields for Sequence Labeling}},
  booktitle = {CoNLL},
  year = {2018},
  url = {https://openreview.net/forum?id=SO-NiVgt8bc},
}
Figure