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

Proceedings of NAACL HLT 2007, pages 65–72, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Structured Local Training and Biased Potential Functions for Conditional Random Fields with Application to Coreference Resolution Yejin Choi and Claire Cardie Department of Computer Science Cornell University Ithaca, NY 14853 {ychoi,cardie}@cs.cornell.edu Abstract Conditional Random Fields (CRFs) have shown great success for problems involving structured out- put variables. However, for many real-world NLP applications, exact maximum-likelihood training is intractable because computing the global normal- ization factor even approximately can be extremely hard. In addition, optimizing likelihood often does not correlate with maximizing task-specific evalu- ation 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 vari- ables are used to capture interactions between lo- cal inference and global inference. Furthermore, we introduce biased potential functions that empir- ically drive CRFs towards performance improve- ments w.r.t. the preferred evaluation measure for the learning task. We report promising experimen- tal results on two coreference data sets using two task-specific evaluation measures. 1 Introduction Undirected graphical models such as Conditional Random Fields (CRFs) (Lafferty et al., 2001) have shown great success for problems involving struc- tured output variables (e.g. Wellner et al. (2004), Finkel et al. (2005)). For many real-world NLP ap- plications, however, the required graph structure can be very complex, and computing the global normal- ization factor even approximately can be extremely hard. Previous approaches for training CRFs have either (1) opted for a training method that no longer maximizes the likelihood, (e.g. McCallum and Well- ner (2004), Roth and Yih (2005)) 1, or (2) opted for a 1Both McCallum and Wellner (2004) and Roth and Yih (2005) used the voted perceptron algorithm (Collins, 2002) to train intractable CRFs. simplified graph structure to avoid intractable global normalization (e.g. Roth and Yih (2005), Wellner et al. (2004)). Solutions of the first type replace the computation of the global normalization factor � y p(y|x) with argmaxy p(y|x) during training, since finding an argmax of a probability distribution is often an eas- ier problem than finding the entire probability distri- bution. Training via the voted perceptron algorithm (Collins, 2002) or using a max-margin criterion also correspond to the first option (e.g. McCallum and Wellner (2004), Finley and Joachims (2005)). But without the global normalization, the maximum- likelihood criterion motivated by the maximum en- tropy principle (Berger et al., 1996) is no longer a feasible option as an optimization criterion. The second solution simplifies the graph struc- ture for training, and applies complex global infer- ence only for testing. In spite of the discrepancy between the training model and the testing model, it has been empirically shown that (1) performing global inference only during testing can improve performance (e.g. Finkel et al. (2005), Roth and Yih (2005)), and (2) full-blown global training can of- ten perform worse due to insufficient training data (e.g. Punyakanok et al. (2005)). Importantly, how- ever, attempts to reduce the …

Content truncated to 500 words