A Maximum Expected Utility Framework for Binary Sequence Labeling

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 736–743, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics A Maximum Expected Utility Framework for Binary Sequence Labeling Martin Jansche∗ jansche@acm.org Abstract We consider the problem of predictive infer- ence for probabilistic binary sequence label- ing models under F-score as utility. For a simple class of models, we show that the number of hypotheses whose expected F- score needs to be evaluated is linear in the sequence length and present a framework for efficiently evaluating the expectation of many common loss/utility functions, including the F-score. This framework includes both exact and faster inexact calculation methods. 1 Introduction 1.1 Motivation and Scope The weighted F-score (van Rijsbergen, 1974) plays an important role in the evaluation of binary classi- fiers, as it neatly summarizes a classifier’s ability to identify the positive class. A variety of methods ex- ists for training classifiers that optimize the F-score, or some similar trade-off between false positives and false negatives, precision and recall, sensitivity and specificity, type I error and type II error rate, etc. Among the most general methods are those of Mozer et al. (2001), whose constrained optimization tech- nique is similar to those in (Gao et al., 2006; Jansche, 2005). More specialized methods also exist, for ex- ample for support vector machines (Musicant et al., 2003) and for conditional random fields (Gross et al., 2007; Suzuki et al., 2006). All of these methods are about classifier training. In this paper we focus primarily on the related, but orthogonal, issue of predictive inference with a fully trained probabilistic classifier. Using the weighted F-score as our utility function, predictive inference amounts to choosing an optimal hypothesis which maximizes the expected utility. We refer to this as ∗Current affiliation: Google Inc. Former affiliation: Center of Computational Learning Systems, Columbia University. the prediction or decoding task. In general, decoding can be a hard computational problem (Casacuberta and de la Higuera, 2000; Knight, 1999). In this paper we show that the maximum expected F-score decod- ing problem can be solved in polynomial time under certain assumptions about the underlying probabil- ity model. One key ingredient in our solution is a very general framework for evaluating the expected F-score, and indeed many other utility functions, of a fixed hypothesis.1 This framework can also be ap- plied to discriminative classifier training. 1.2 Background and Notation We formulate our approach in terms of sequence la- beling, although it has applications beyond that. This is motivated by the fact that our framework for evalu- ating expected utility is indeed applicable to general sequence labeling tasks, while our decoding method is more restricted. Another reason is that the F-score is only meaningful for comparing two (multi)sets or two binary sequences, but the notation for multisets is slightly more awkward. All tasks considered here involve strings of binary labels. We write the length of a given string y ∈ {0,1}n as |y| = n. It is convenient to view such …

Content truncated to 500 words