Graph-Based Lexicon Expansion with Sparsity-Inducing Penalties

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 677–687, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Graph-Based Lexicon Expansion with Sparsity-Inducing Penalties Dipanjan Das and Noah A. Smith Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213, USA {dipanjan,nasmith}@cs.cmu.edu Abstract We present novel methods to construct com- pact natural language lexicons within a graph- based semi-supervised learning framework, an attractive platform suited for propagating soft labels onto new natural language types from seed data. To achieve compactness, we induce sparse measures at graph vertices by incorporating sparsity-inducing penalties in Gaussian and entropic pairwise Markov networks constructed from labeled and unla- beled data. Sparse measures are desirable for high-dimensional multi-class learning prob- lems such as the induction of labels on natu- ral language types, which typically associate with only a few labels. Compared to standard graph-based learning methods, for two lexicon expansion problems, our approach produces significantly smaller lexicons and obtains bet- ter predictive performance. 1 Introduction Semi-supervised learning (SSL) is attractive for the learning of complex phenomena, for example, lin- guistic structure, where data annotation is expen- sive. Natural language processing applications have benefited from various SSL techniques, such as dis- tributional word representations (Huang and Yates, 2009; Turian et al., 2010; Dhillon et al., 2011), self-training (McClosky et al., 2006), and entropy regularization (Jiao et al., 2006; Smith and Eisner, 2007). In this paper, we focus on semi-supervised learning that uses a graph constructed from labeled and unlabeled data. This framework, graph-based SSL—see Bengio et al. (2006) and Zhu (2008) for introductory material on this topic—has been widely used and has been shown to perform better than sev- eral other semi-supervised algorithms on benchmark datasets (Chapelle et al., 2006, ch. 21). The method constructs a graph where a small portion of ver- tices correspond to labeled instances, and the rest are unlabeled. Pairs of vertices are connected by weighted edges denoting the similarity between the pair. Traditionally, Markov random walks (Szum- mer and Jaakkola, 2001; Baluja et al., 2008) or op- timization of a loss function based on smoothness properties of the graph (Corduneanu and Jaakkola, 2003; Zhu et al., 2003; Subramanya and Bilmes, 2008, inter alia) are performed to propagate labels from the labeled vertices to the unlabeled ones. In this work, we are interested in multi-class gen- eralizations of graph-propagation algorithms suit- able for NLP applications, where each graph ver- tex can assume one or more out of many possible labels (Talukdar and Crammer, 2009; Subramanya and Bilmes, 2008, 2009). For us, graph vertices cor- respond to natural language types (not tokens) and undirected edges between them are weighted using a similarity metric. Recently, this setup has been used to learn soft labels on natural language types (say, word n-grams or syntactically disambiguated pred- icates) from seed data, resulting in large but noisy lexicons, which are used to constrain structured pre- diction models. Applications have ranged from domain adaptation of part-of-speech (POS) taggers (Subramanya et …

Content truncated to 500 words