An Algebra for Feature Extraction

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 1891–1900 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1173 Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, pages 1891–1900 Vancouver, Canada, July 30 - August 4, 2017. c⃝2017 Association for Computational Linguistics https://doi.org/10.18653/v1/P17-1173 An Algebra for Feature Extraction Vivek Srikumar School of Computing University of Utah svivek@cs.utah.edu Abstract Though feature extraction is a necessary first step in statistical NLP, it is often seen as a mere preprocessing step. Yet, it can dominate computation time, both during training, and especially at deployment. In this paper, we formalize feature extraction from an algebraic perspective. Our for- malization allows us to define a message passing algorithm that can restructure fea- ture templates to be more computationally efficient. We show via experiments on text chunking and relation extraction that this restructuring does indeed speed up feature extraction in practice by reducing redun- dant computation. 1 Introduction Often, the first step in building statistical NLP models involves feature extraction. It is well un- derstood that the right choice of features can sub- stantially improve classifier performance. How- ever, from the computational point of view, the process of feature extraction is typically treated, at best as the preprocessing step of caching fea- turized inputs over entire datasets, and at worst, as ‘somebody else’s problem’. While such ap- proaches work for training, when trained models are deployed, the computational cost of feature ex- traction cannot be ignored. In this paper, we present the first (to our knowl- edge) algebraic characterization of the process of feature extraction. We formalize feature extrac- tors as arbitrary functions that map objects (words, sentences, etc) to a vector space and show that this set forms a commutative semiring with respect to feature addition and feature conjunction. An immediate consequence of the semiring characterization is a computational one. Every semiring admits the Generalized Distributive Law (GDL) Algorithm (Aji and McEliece, 2000) that exploits the distributive property to provide com- putational speedups. Perhaps the most common manifestation of this algorithm in NLP is in the form of inference algorithms for factor graphs and Bayesian networks like the max-product, max- sum and sum-product algorithms (e.g. Goodman, 1999; Kschischang et al., 2001). When applied to feature extractors, the GDL algorithm can refactor a feature extractor into a faster one by reducing re- dundant computation. In this paper, we propose a junction tree construction to allow such refactor- ing. Since the refactoring is done at the feature template level, the actual computational savings grow as classifiers encounter more examples. We demonstrate the practical utility of our ap- proach by factorizing existing feature sets for text chunking and relation extraction. We show that, by reducing the number of operations performed, we can obtain significant savings in the time taken to extract features. To summarize, the main contribution of this pa- per is the recognition that feature extractors form a commutative semiring over addition and conjunc- …

Content truncated to 500 words