Structured Local Training and Biased Potential Functions for Conditional Random Fields with Application to Coreference Resolution

Yejin Choi, Claire CardieNAACL 2007 · OpenReview

Abstract

Conditional Random Fields (CRFs) have shown great success for problems involving structured output variables. However, for many real-world NLP applications, exact maximum-likelihood training is intractable because computing the global normalization factor even approximately can be extremely hard. In addition, optimizing likelihood often does not correlate with maximizing task-specific evaluation measures. In this paper, we present a novel training procedure, structured local training, that maximizes likelihood while exploiting the benefits of global inference during training: hidden variables are used to capture interactions between local inference and global inference. Furthermore, we introduce biased potential functions that empirically drive CRFs towards performance improvements w.r.t. the preferred evaluation measure for the learning task. We report promising experimental results on two coreference data sets using two task-specific evaluation measures.

Introduction

Conditional Random Fields (CRFs) are powerful tools for structured prediction, but they encounter significant scalability issues when applied to complex problems like coreference resolution—the task of determining which mentions in a text refer to the same entity. Two major hurdles exist:

  1. Intractability: Training a CRF requires calculating a global normalization factor, which involves summing over every possible labeling. In coreference resolution, the number of potential mention pairings is astronomical, making exact training impossible.
  2. Metric Mismatch: Standard CRF training maximizes likelihood, which often fails to correlate with task-specific metrics like F1-score or MUC-score. A model that fits the data distribution well may still perform poorly on the metrics used to judge real-world success.

This paper introduces two novel techniques to address these issues: Structured Local Training (SLT) and Biased Potential Functions (BPF).

Methodology

Structured Local Training (SLT)

To bypass the computational nightmare of full global training, SLT employs an Expectation-Maximization (EM) style approach. The authors introduce a hidden variable ($h$) representing local pairwise decisions.

  • The E-Step: The model identifies a labeling that is close to the ground truth while satisfying global constraints, such as transitivity (if A=B and B=C, then A=C).
  • The M-Step: The model updates its parameters to increase the likelihood of these "corrected" local decisions.

This framework allows the model to learn from global structure without performing expensive global normalization during the training loop.

Biased Potential Functions (BPF)

To resolve the "Metric Mismatch," the authors modify the CRF's potential functions by introducing a bias factor ($\beta$). This factor allows researchers to tune the model toward specific evaluation metrics. For instance, since coreferent pairs are relatively rare, the model can be biased to amplify the importance of these pairs to boost recall. Additionally, biasing the model toward mentions that are physically closer in the text—where linguistic signals are often clearer—can improve specific metrics like the MUC-score.

Experimental Results

The methods were evaluated on two primary coreference benchmarks: MUC6 and MPQA. The combination of SLT and BPF yielded significant performance gains over standard local training (BASE).

Comparison of BASE and SLT performance on MUC6 and MPQA datasets before and after clustering.

Key Performance Insights

  • Error Reduction: On the MPQA dataset, SLT reduced the error rate ($e \%$) from 9.83% to 6.39% after clustering.
  • Metric Alignment: For MUC6, the MUC-F1 score improved from 66.4% in the baseline to 69.9% when using biased potential functions.
  • Pairwise Improvement: On MPQA, the pairwise F1-score increased from 65.1% to 70.6% using biased functions.
Performance of SLT with Biased Potential Functions (BPF) on the MUC6 dataset across pairwise and MUC metrics.

Discussion and Conclusion

The research highlights that maximizing likelihood is often a proxy for pairwise accuracy rather than the final goal of high F1-scores after clustering. SLT effectively bridges the "transitivity gap" by forcing local classifiers to recognize global contradictions during training. While SLT is approximately twice as computationally expensive as local training due to the EM iterations, it remains vastly more efficient than full global training, which is often intractable for these graph structures.

Future work may involve integrating more sophisticated clustering algorithms into the SLT framework and exploring the application of these techniques to other structured prediction tasks, such as semantic role labeling or dependency parsing.

Summary updated

Abstract

Conditional Random Fields (CRFs) have shown great success for problems involving structured output variables. However, for many real-world NLP applications, exact maximum-likelihood training is intractable because computing the global normalization factor even approximately can be extremely hard. In addition, optimizing likelihood often does not correlate with maximizing task-specific evaluation measures. In this paper, we present a novel training procedure, structured local training, that maximizes likelihood while exploiting the benefits of global inference during training: hidden variables are used to capture interactions between local inference and global inference. Furthermore, we introduce biased potential functionsthat empirically drive CRFs towards performance improvements w.r.t. the preferred evaluation measure for the learning task. We report promising experimental results on two coreference data sets using two task-specific evaluation measures.
BibTeX
@inproceedings{choi2007structured,
  author = {Yejin Choi and Claire Cardie},
  title = {{Structured Local Training and Biased Potential Functions for Conditional Random Fields with Application to Coreference Resolution}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
  url = {https://openreview.net/forum?id=HkVgpQWuWH},
}
Figure