Analyzing the Errors of Unsupervised Learning

Proceedings of ACL-08: HLT, pages 879–887, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Analyzing the Errors of Unsupervised Learning Percy Liang Dan Klein Computer Science Division, EECS Department University of California at Berkeley Berkeley, CA 94720 {pliang,klein}@cs.berkeley.edu Abstract We identify four types of errors that unsu- pervised induction systems make and study each one in turn. Our contributions include (1) using a meta-model to analyze the incor- rect biases of a model in a systematic way, (2) providing an efficient and robust method of measuring distance between two parameter settings of a model, and (3) showing that lo- cal optima issues which typically plague EM can be somewhat alleviated by increasing the number of training examples. We conduct our analyses on three models: the HMM, the PCFG, and a simple dependency model. 1 Introduction The unsupervised induction of linguistic structure from raw text is an important problem both for un- derstanding language acquisition and for building language processing systems such as parsers from limited resources. Early work on inducing gram- mars via EM encountered two serious obstacles: the inappropriateness of the likelihood objective and the tendency of EM to get stuck in local optima. With- out additional constraints on bracketing (Pereira and Shabes, 1992) or on allowable rewrite rules (Carroll and Charniak, 1992), unsupervised grammar learn- ing was ineffective. Since then, there has been a large body of work addressing the flaws of the EM-based approach. Syntactic models empirically more learnable than PCFGs have been developed (Clark, 2001; Klein and Manning, 2004). Smith and Eisner (2005) pro- posed a new objective function; Smith and Eis- ner (2006) introduced a new training procedure. Bayesian approaches can also improve performance (Goldwater and Griffiths, 2007; Johnson, 2007; Kurihara and Sato, 2006). Though these methods have improved induction accuracy, at the core they all still involve optimizing non-convex objective functions related to the like- lihood of some model, and thus are not completely immune to the difficulties associated with early ap- proaches. It is therefore important to better under- stand the behavior of unsupervised induction sys- tems in general. In this paper, we take a step back and present a more statistical view of unsupervised learning in the context of grammar induction. We identify four types of error that a system can make: approxima- tion, identifiability, estimation, and optimization er- rors (see Figure 1). We try to isolate each one in turn and study its properties. Approximation error is caused by a mis-match between the likelihood objective optimized by EM and the true relationship between sentences and their syntactic structures. Our key idea for understand- ing this mis-match is to “cheat” and initialize EM with the true relationship and then study the ways in which EM repurposes our desired syntactic struc- tures to increase likelihood. We present a meta- model of the changes that EM makes and show how this tool can shed some light on the undesired biases of the HMM, the PCFG, and the dependency model with valence (Klein …

Content truncated to 500 words