Low-Rank Regularization for Sparse Conjunctive Feature Spaces: An Application to Named Entity Classification

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 126–135, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Low-Rank Regularization for Sparse Conjunctive Feature Spaces: An Application to Named Entity Classification Audi Primadhanty Universitat Polit`ecnica de Catalunya primadhanty@cs.upc.edu Xavier Carreras Ariadna Quattoni Xerox Research Centre Europe xavier.carreras@xrce.xerox.com ariadna.quattoni@xrce.xerox.com Abstract Entity classification, like many other important problems in NLP, involves learning classifiers over sparse high- dimensional feature spaces that result from the conjunction of elementary fea- tures of the entity mention and its context. In this paper we develop a low-rank reg- ularization framework for training max- entropy models in such sparse conjunctive feature spaces. Our approach handles con- junctive feature spaces using matrices and induces an implicit low-dimensional rep- resentation via low-rank constraints. We show that when learning entity classifiers under minimal supervision, using a seed set, our approach is more effective in con- trolling model capacity than standard tech- niques for linear classifiers. 1 Introduction Many important problems in NLP involve learn- ing classifiers over sparse high-dimensional fea- ture spaces that result from the conjunction of el- ementary features. For example, to classify an en- tity in a document, it is standard to exploit features of the left and right context in which the entity oc- curs as well as spelling features of the entity men- tion itself. These sets of features can be grouped into vectors which we call elementary feature vec- tors. In our example, there will be one elementary feature vector for the left context, one for the right context and one for the features of the mention. Observe that, when the elementary vectors consist of binary indicator features, the outer product of any pair of vectors represents all conjunctions of the corresponding elementary features. Ideally, we would like to train a classifier that can leverage all conjunctions of elementary fea- tures, since among them there might be some that are discriminative for the classification task at hand. However, allowing for such expressive high dimensional feature space comes at a cost: data sparsity becomes a key challenge and controlling the capacity of the model is crucial to avoid over- fitting the training data. The problem of data sparsity is even more se- vere when the goal is to train classifiers with min- imal supervision, i.e. small training sets. For ex- ample, in the entity classification setting we might be interested in training a classifier using only a small set of examples of each entity class. This is a typical scenario in an industrial setting, where developers are interested in classifying entities ac- cording to their own classification schema and can only provide a handful of examples of each class. A standard approach to control the capacity of a linear classifier is to use ℓ1 or ℓ2 regularization on the parameter vector. However, this type of regu- larization does not seem to be effective when deal- ing with sparse conjunctive feature …

Content truncated to 500 words