Sequential Labeling with Latent Variables: An Exact Inference Algorithm and its Efficient Approximation

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 772–780, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Sequential Labeling with Latent Variables: An Exact Inference Algorithm and Its Efficient Approximation Xu Sun† Jun’ichi Tsujii†‡§ †Department of Computer Science, University of Tokyo, Japan ‡School of Computer Science, University of Manchester, UK §National Centre for Text Mining, Manchester, UK {sunxu, tsujii}@is.s.u-tokyo.ac.jp Abstract Latent conditional models have become popular recently in both natural language processing and vision processing commu- nities. However, establishing an effective and efficient inference method on latent conditional models remains a question. In this paper, we describe the latent-dynamic inference (LDI), which is able to produce the optimal label sequence on latent con- ditional models by using efficient search strategy and dynamic programming. Fur- thermore, we describe a straightforward solution on approximating the LDI, and show that the approximated LDI performs as well as the exact LDI, while the speed is much faster. Our experiments demonstrate that the proposed inference algorithm out- performs existing inference methods on a variety of natural language processing tasks. 1 Introduction When data have distinct sub-structures, mod- els exploiting latent variables are advantageous in learning (Matsuzaki et al., 2005; Petrov and Klein, 2007; Blunsom et al., 2008). Actu- ally, discriminative probabilistic latent variable models (DPLVMs) have recently become popu- lar choices for performing a variety of tasks with sub-structures, e.g., vision recognition (Morency et al., 2007), syntactic parsing (Petrov and Klein, 2008), and syntactic chunking (Sun et al., 2008). Morency et al. (2007) demonstrated that DPLVM models could efficiently learn sub-structures of natural problems, and outperform several widely- used conventional models, e.g., support vector ma- chines (SVMs), conditional random fields (CRFs) and hidden Markov models (HMMs). Petrov and Klein (2008) reported on a syntactic parsing task that DPLVM models can learn more compact and accurate grammars than the conventional tech- niques without latent variables. The effectiveness of DPLVMs was also shown on a syntactic chunk- ing task by Sun et al. (2008). DPLVMs outperform conventional learning models, as described in the aforementioned pub- lications. However, inferences on the latent condi- tional models are remaining problems. In conven- tional models such as CRFs, the optimal label path can be efficiently obtained by the dynamic pro- gramming. However, for latent conditional mod- els such as DPLVMs, the inference is not straight- forward because of the inclusion of latent vari- ables. In this paper, we propose a new inference al- gorithm, latent dynamic inference (LDI), by sys- tematically combining an efficient search strategy with the dynamic programming. The LDI is an exact inference method producing the most prob- able label sequence. In addition, we also propose an approximated LDI algorithm for faster speed. We show that the approximated LDI performs as well as the exact one. We will also discuss a post-processing method for the LDI algorithm: the minimum bayesian risk reranking. The subsequent section describes an overview of DPLVM models. We discuss the probability distribution of DPLVM …

Content truncated to 500 words