On the Use of Virtual Evidence in Conditional Random Fields

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 1289–1297, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP On the Use of Virtual Evidence in Conditional Random Fields Xiao Li Microsoft Research One Microsoft Way Redmond, WA 98052 USA xiaol@microsoft.com Abstract Virtual evidence (VE), first introduced by (Pearl, 1988), provides a convenient way of incorporating prior knowledge into Bayesian networks. This work general- izes the use of VE to undirected graph- ical models and, in particular, to condi- tional 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 us- ing the Expectation-Maximization algo- rithm while maintaining the discriminative nature of CRFs. When evaluated on the CLASSIFIEDS data, our approach signif- icantly outperforms the best known solu- tions reported on this task. 1 Introduction Statistical approaches to sequential labeling prob- lems rely on necessary training data to model the uncertainty of a sequence of events. Human’s prior knowledge about the task, on the other hand, often requires minimum cognitive load to spec- ify, and yet can provide information often com- plementary to that offered by a limited amount of training data. Whenever prior knowledge becomes available, it is desired that such information is in- tegrated to a probabilistic model to improve learn- ing. Virtual evidence (VE), first introduced by Pearl (1988), offers a principled and convenient way of incorporating external knowledge into Bayesian networks. In contrast to standard evidence (also known as observed variables), VE expresses a prior belief over values of random variables. It has been shown that VE can significantly extend the modeling power of Bayesian networks without complicating the fundamental inference method- ology (Bilmes, 2004; Reynolds and Bilmes, 2005). This work extends the use of VE to undi- rected graphical models and, in particular, to con- ditional random fields (CRFs). We show that VE can be naturally encoded into an undirected graphical model as potential functions. More im- portantly, we discuss a semi-supervised machine learning setting for estimating CRFs with the pres- ence of VE. As the conditional likelihood objec- tive of CRFs is not directly maximizable with re- spect to unlabeled data, we propose a novel semi- supervised learning objective that can be opti- mized using the Expectation-Maximization (EM) algorithm while maintaining the discriminative nature of CRFs. We apply our model to the CLASSIFIEDS data (Grenager et al., 2005). Specifically, we use VE to incorporate into a CRF model two types of prior knowledge specified in previous works. The first is defined based on the notion of prototypes, i.e., example words for a given label; and the other as- sumes that adjacent tokens tend to have the same label. When unlabeled data becomes available, we further extend the sparse prototype informa- tion to other words based on distributional similar- ity. This results in so-called collocation lists, each consisting of a …

Content truncated to 500 words