On the Use of Virtual Evidence in Conditional Random Fields

Xiao LiEMNLP 2009 · OpenReview

Abstract

Virtual evidence (VE), first introduced by Pearl (1988), provides a convenient way of incorporating prior knowledge into Bayesian networks. This work generalizes the use of VE to undirected graphical models and, in particular, to conditional random fields (CRFs). We show that VE can be naturally encoded into a CRF model as potential functions. More importantly, we propose a novel semi-supervised machine learning objective for estimating a CRF model integrated with VE. The objective can be optimized using the Expectation-Maximization algorithm while maintaining the discriminative nature of CRFs. When evaluated on the CLASSIFIEDS data, our approach significantly outperforms the best known solutions reported on this task.

Introduction

In many sequence labeling tasks, researchers face a common dilemma: a scarcity of expensive labeled data alongside an abundance of "free" human intuition. For instance, in extracting information from classified ads, a human knows that the word "bedroom" typically implies a "size" field. While standard Conditional Random Fields (CRFs) are powerful discriminative models, they often struggle to incorporate these "rules of thumb" effectively without resorting to rigid hard constraints.

This paper bridges the gap between Bayesian networks and undirected graphical models by introducing Virtual Evidence (VE) into CRFs. By treating human prior knowledge as "soft" probabilistic constraints, the authors develop a semi-supervised framework that significantly boosts accuracy, particularly in low-data regimes.

Methodology

The authors propose three key innovations to integrate human knowledge into the mathematically rigorous CRF framework:

  1. VE as Potential Functions: Virtual Evidence—originally a concept for expressing beliefs over variables in Bayesian networks—is mathematically encoded as additional potential functions in a CRF. This allows the model to favor certain labels based on prior knowledge without forcing them, maintaining flexibility.
  2. A Novel Semi-Supervised Objective: Standard CRF training (conditional likelihood) cannot directly utilize unlabeled data. The authors propose a new objective function that maximizes the marginal probability of the Virtual Evidence given the input. This is optimized using the Expectation-Maximization (EM) algorithm, allowing the model to "self-correct" its understanding of unlabeled data using human-provided hints.
  3. Collocation-based VE: To handle the noise inherent in automatically expanded prototype lists, they introduce a collocation rule. The model only trusts a noisy prototype if it appears near another word from the same category, using local context to filter out ambiguity (e.g., distinguishing "water" as a utility vs. a feature).
Comparison between a standard CRF (a) and a CRF integrated with Virtual Evidence nodes (b).

Experimental Setup

The model was evaluated on the CLASSIFIEDS dataset, consisting of 8,767 apartment rental advertisements. The dataset was split into a small labeled set of 302 ads (annotated with 12 fields like size, rent, neighborhood) and a large unlabeled set of ~8,400 ads. Prior knowledge was incorporated via prototype lists (example words for labels) and sentence boundary heuristics.

Key Results

The approach established a new state-of-the-art for the CLASSIFIEDS task:

  • Supervised Boost: Simply adding VE to a standard supervised CRF improved accuracy from 79.1% to 81.1% with 100 labeled examples.
  • Low-Data Efficiency: With only 10 labeled examples, the semi-supervised EM approach reached 78.8% accuracy—nearly matching the performance of a standard CRF trained on ten times as much data.
  • Superiority over Competitors: The model achieved absolute accuracy increases of 2.6% to 5.7% over previous state-of-the-art methods like Generalized Expectation (GE) criteria.
Performance of semi-supervised models on the CLASSIFIEDS dataset across different amounts of labeled data.

Discussion and Limitations

The success of this method stems from its "soft" integration of knowledge. Unlike hard constraints, VE allows the model to remain robust even when human-provided rules are occasionally violated. By using EM, the model identifies prototypes in unlabeled text to better understand surrounding context, iteratively improving its feature set.

However, some challenges remain. The weights for the Virtual Evidence ($ω_1, ω_2$) currently require manual tuning, as automatic estimation led to poor performance. Additionally, the reliance on simple punctuation-based heuristics for sentence boundaries may not generalize to more complex document structures. Future work will explore the generalizability of the collocation logic to other sequence labeling tasks, such as Named Entity Recognition (NER).

Summary updated

Abstract

Virtual evidence (VE), first introduced by (Pearl, 1988), provides a convenient way of incorporating prior knowledge into Bayesian networks. This work generalizes the use of VE to undirected graphical models and, in particular, to conditional random fields (CRFs). We show that VE can be naturally encoded into a CRF model as potential functions. More importantly, we propose a novel semi-supervised machine learning objective for estimating a CRF model integrated with VE. The objective can be optimized using the Expectation-Maximization algorithm while maintaining the discriminative nature of CRFs. When evaluated on the CLASSIFIEDS data, our approach significantly outperforms the best known solutions reported on this task.
BibTeX
@inproceedings{li2009use,
  author = {Xiao Li},
  title = {{On the Use of Virtual Evidence in Conditional Random Fields}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=rJZMqzz_WB},
}
Figure