Computationally Efficient M-Estimation of Log-Linear Structure Models

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 752–759, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics Computationally Efficient M-Estimation of Log-Linear Structure Models∗ Noah A. Smith and Douglas L. Vail and John D. Lafferty School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 USA {nasmith,dvail2,lafferty}@cs.cmu.edu Abstract We describe a new loss function, due to Jeon and Lin (2006), for estimating structured log-linear models on arbitrary features. The loss function can be seen as a (generative) al- ternative to maximum likelihood estimation with an interesting information-theoretic in- terpretation, and it is statistically consis- tent. It is substantially faster than maximum (conditional) likelihood estimation of condi- tional random fields (Lafferty et al., 2001; an order of magnitude or more). We com- pare its performance and training time to an HMM, a CRF, an MEMM, and pseudolike- lihood on a shallow parsing task. These ex- periments help tease apart the contributions of rich features and discriminative training, which are shown to be more than additive. 1 Introduction Log-linear models are a very popular tool in natural language processing, and are often lauded for per- mitting the use of “arbitrary” and “correlated” fea- tures of the data by a model. Users of log-linear models know, however, that this claim requires some qualification: any feature is permitted in principle, but training log-linear models (and decoding under them) is tractable only when the model’s indepen- dence assumptions permit efficient inference proce- dures. For example, in the original conditional ran- dom fields (Lafferty et al., 2001), features were con- ∗This work was supported by NSF grant IIS-0427206 and the DARPA CALO project. The authors are grateful for feed- back from David Smith and from three anonymous ACL re- viewers, and helpful discussions with Charles Sutton. fined to locally-factored indicators on label bigrams and label unigrams (with any of the observation). Even in cases where inference in log-linear mod- els is tractable, it requires the computation of a parti- tion function. More formally, a log-linear model for random variables X and Y over X, Y defines: pw(x, y) = ew⊤f(x,y) � x′,y′∈X×Yew⊤f(x′,y′) = ew⊤f(x,y) Z(w) (1) where f : X×Y → Rm is the feature vector-function and w ∈ Rm is a weight vector that parameterizes the model. In NLP, we rarely train this model by maximizing likelihood, because the partition func- tion Z(w) is expensive to compute exactly. Z(w) can be approximated (e.g., using Gibbs sampling; Rosenfeld, 1997). In this paper, we propose the use of a new loss function that is computationally efficient and statis- tically consistent (§2). Notably, repeated inference is not required during estimation. This loss func- tion can be seen as a case of M-estimation1 that was originally developed by Jeon and Lin (2006) for nonparametric density estimation. This paper gives an information-theoretic motivation that helps eluci- date the objective function (§3), shows how to ap- ply the new estimator to structured models used in NLP (§4), and compares it to a state-of-the-art noun …

Content truncated to 500 words