Learning Dynamic Feature Selection for Fast Sequential Prediction

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 146–155, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Learning Dynamic Feature Selection for Fast Sequential Prediction Emma Strubell Luke Vilnis Kate Silverstein Andrew McCallum College of Information and Computer Sciences University of Massachusetts Amherst Amherst, MA, 01003, USA {strubell, luke, ksilvers, mccallum}@cs.umass.edu Abstract We present paired learning and inference algorithms for significantly reducing com- putation and increasing speed of the vector dot products in the classifiers that are at the heart of many NLP components. This is accomplished by partitioning the features into a sequence of templates which are or- dered such that high confidence can of- ten be reached using only a small fraction of all features. Parameter estimation is arranged to maximize accuracy and early confidence in this sequence. Our approach is simpler and better suited to NLP than other related cascade methods. We present experiments in left-to-right part-of-speech tagging, named entity recognition, and transition-based dependency parsing. On the typical benchmarking datasets we can preserve POS tagging accuracy above 97% and parsing LAS above 88.5% both with over a five-fold reduction in run-time, and NER F1 above 88 with more than 2x in- crease in speed. 1 Introduction Many NLP tasks such as part-of-speech tagging, parsing and named entity recognition have become sufficiently accurate that they are no longer solely an object of research, but are also widely deployed in production systems. These systems can be run on billions of documents, making the efficiency of inference a significant concern—impacting not only wall-clock running time but also computer hardware budgets and the carbon footprint of data centers. This paper describes a paired learning and infer- ence approach for significantly reducing computa- tion and increasing speed while preserving accu- racy in the linear classifiers typically used in many NLP tasks. The heart of the prediction computa- tion in these models is a dot-product between a dense parameter vector and a sparse feature vec- tor. The bottleneck in these models is then often a combination of feature extraction and numeri- cal operations, each of which scale linearly in the size of the feature vector. Feature extraction can be even more expensive than the dot products, in- volving, for example, walking sub-graphs, lexicon lookup, string concatenation and string hashing. We note, however, that in many cases not all of these features are necessary for accurate predic- tion. For example, in part-of-speech tagging if we see the word “the,” there is no need to perform a large dot product or many string operations; we can accurately label the word a DETERMINER us- ing the word identity feature alone. In other cases two features are sufficient: when we see the word “hits” preceded by a CARDINAL (e.g. “two hits”) we can be confident that it is a NOUN. We present a simple yet novel approach to im- prove processing speed by dynamically determin- ing on a per-instance basis …

Content truncated to 500 words