Structured Sparsity in Structured Prediction

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1500–1511, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Structured Sparsity in Structured Prediction Andr´e F. T. Martins∗† Noah A. Smith∗ Pedro M. Q. Aguiar‡ M´ario A. T. Figueiredo† ∗School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA ‡Instituto de Sistemas e Rob´otica, Instituto Superior T´ecnico, Lisboa, Portugal †Instituto de Telecomunicac¸˜oes, Instituto Superior T´ecnico, Lisboa, Portugal {afm,nasmith}@cs.cmu.edu, aguiar@isr.ist.utl.pt, mtf@lx.it.pt Abstract Linear models have enjoyed great success in structured prediction in NLP. While a lot of progress has been made on efficient train- ing with several loss functions, the problem of endowing learners with a mechanism for feature selection is still unsolved. Common approaches employ ad hoc filtering or L1- regularization; both ignore the structure of the feature space, preventing practicioners from encoding structural prior knowledge. We fill this gap by adopting regularizers that promote structured sparsity, along with efficient algo- rithms to handle them. Experiments on three tasks (chunking, entity recognition, and de- pendency parsing) show gains in performance, compactness, and model interpretability. 1 Introduction Models for structured outputs are in demand across natural language processing, with applications in in- formation extraction, parsing, and machine transla- tion. State-of-the-art models usually involve linear combinations of features and are trained discrim- inatively; examples are conditional random fields (Lafferty et al., 2001), structured support vector machines (Altun et al., 2003; Taskar et al., 2003; Tsochantaridis et al., 2004), and the structured per- ceptron (Collins, 2002a). In all these cases, the un- derlying optimization problems differ only in the choice of loss function; choosing among them has usually a small impact on predictive performance. In this paper, we are concerned with model se- lection: which features should be used to define the prediction score? The fact that models with few features (“sparse” models) are desirable for several reasons (compactness, interpretability, good gener- alization) has stimulated much research work which has produced a wide variety of methods (Della Pietra et al., 1997; Guyon and Elisseeff, 2003; McCallum, 2003). Our focus is on methods which embed this selection into the learning problem via the regular- ization term. We depart from previous approaches in that we seek to make decisions jointly about all candidate features, and we want to promote sparsity patterns that go beyond the mere cardinality of the set of features. For example, we want to be able to select entire feature templates (rather than features individually), or to make the inclusion of some fea- tures depend on the inclusion of other features. We achieve the goal stated above by employ- ing regularizers which promote structured sparsity. Such regularizers are able to encode prior knowl- edge and guide the selection of features by model- ing the structure of the feature space. Lately, this type of regularizers has received a lot of attention in computer vision, signal processing, and compu- tational biology (Zhao et al., 2009; Kim and Xing, 2010; Jenatton et al., 2009; Obozinski et al., 2010; …

Content truncated to 500 words