Unsupervised Spectral Learning of WCFG as Low-rank Matrix Completion

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 624–635, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Unsupervised Spectral Learning of WCFG as Low-rank Matrix Completion Rapha¨el Bailly† Xavier Carreras† Franco M. Luque‡ Ariadna Quattoni† † Universitat Polit`ecnica de Catalunya Barcelona, 08034 rbailly,carreras,aquattoni@lsi.upc.edu ‡ Universidad Nacional de C´ordoba and CONICET X500HUA C´ordoba, Argentina francolq@famaf.unc.edu.ar Abstract We derive a spectral method for unsupervised learning of Weighted Context Free Grammars. We frame WCFG induction as finding a Han- kel matrix that has low rank and is linearly constrained to represent a function computed by inside-outside recursions. The proposed al- gorithm picks the grammar that agrees with a sample and is the simplest with respect to the nuclear norm of the Hankel matrix. 1 Introduction Weighted Context Free Grammars (WCFG) define an important class of languages. Their expressivity makes them good candidates for modeling a wide range of natural language phenomena. This expres- sivity comes at a cost: unsupervised learning of WCFG seems to be a particularly hard task. And while it is a well-studied problem, it is still to a great extent unsolved. Several methods for unsupervised learning of WCFG have been proposed. Some rely on heuristics that are used to build incrementally an approxima- tion of the unknown grammar (Adriaans et al., 2000; Van Zaanen, 2000; Tu and Honavar, 2008). Other methods are based on maximum likelihood estima- tion, searching for the grammar that has the largest posterior given the training corpus (Baker, 1979; Lari and Young, 1990; Pereira and Schabes, 1992; Klein and Manning, 2002). Several Bayesian in- ference approaches have also been proposed (Chen, 1995; Kurihara and Sato, 2006; Liang et al., 2007; Cohen et al., 2010). These approaches perform pa- rameter estimation by exploiting Markov sampling techniques. Recently, for the related problem of unsupervised dependency parsing, Gormley and Eisner (2013) proposed a new way of framing the max-likelihood estimation. In their formulation the problem is ex- pressed as an integer quadratic program subject to non-linear constraints. They exploit techniques from mathematical programming to solve the resulting optimization. In spirit, the work by Clark (2001; 2007) is prob- ably the most similar to our approach since both ap- proaches share an algebraic view of the problem. In his case the key idea is to work with an algebraic representation of a WCFG. The problem of recover- ing the constituents of the grammar is reduced to the problem of identifying its syntactic congruence. In the last years, multiple spectral learning algo- rithms have been proposed for a wide range of mod- els (Hsu et al., 2009; Bailly et al., 2009; Bailly et al., 2010; Balle et al., 2011; Luque et al., 2012; Cohen et al., 2012). Since the spectral approach provides a good thinking tool to reason about distributions over Σ∗, the question of whether they can be used for un- supervised learning of WCFG seems natural. Still, while spectral algorithms for unsupervised learning of languages can learn regular languages, tree lan- …

Content truncated to 500 words