Dynamic Feature Induction: The Last Gist to the State-of-the-Art

Proceedings of NAACL-HLT 2016, pages 271–281, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics Dynamic Feature Induction: The Last Gist to the State-of-the-Art Jinho D. Choi Department of Mathematics and Computer Science Emory University Atlanta, GA 30322, USA jinho.choi@emory.edu Abstract We introduce a novel technique called dynamic feature induction that keeps inducing high di- mensional features automatically until the fea- ture space becomes ‘more’ linearly separable. Dynamic feature induction searches for the fea- ture combinations that give strong clues for distinguishing certain label pairs, and gener- ates joint features from these combinations. These induced features are trained along with the primitive low dimensional features. Our ap- proach was evaluated on two core NLP tasks, part-of-speech tagging and named entity recog- nition, and showed the state-of-the-art results for both tasks, achieving the accuracy of 97.64 and the F1-score of 91.00 respectively, with about a 25% increase in the feature space. 1 Introduction Feature engineering typically involves two processes: the process of discovering novel features with domain knowledge, and the process of optimizing combina- tions between existing features. Discovering novel features may require linguistic background as well as good understanding in machine learning such that it is often difficult to do. Optimizing feature combi- nations can be also difficult but usually requires less domain knowledge and more importantly, it can be as effective as discovering new features. It has been shown for many tasks that approaches using simple machine learning with extensive feature engineering outperform ones using more advanced machine learn- ing with less intensive feature engineering (Xue and Palmer, 2004; Bengtson and Roth, 2008; Ratinov and Roth, 2009; Zhang and Nivre, 2011). Recently, people have tried to automate the second part of feature engineering, the optimization of fea- ture combinations, through leading-edge models such as neural networks (Collobert et al., 2011). Coupled with embedding approaches (Mikolov et al., 2013; Le and Mikolov, 2014; Pennington et al., 2014), neural networks can find the optimal feature combinations using techniques such as random weight initialization and back-propagation, and have established the new state-of-the-art for several tasks (Socher et al., 2013; Devlin et al., 2014; Yu et al., 2014). However, neural networks are not as good at optimizing combinations between sparse features, which are still the most dom- inating factors in natural language processing. This paper introduces a new technique called dy- namic feature induction that automates the optimiza- tion of feature combinations (Section 3), and can be easily adapted to any NLP task using sparse features. Dynamic feature induction allows humans to focus on the first part of feature engineering, the discovery of novel features, while machines handle the second part. Our approach was experimented with two core NLP tasks, part-of-speech tagging (Section 4) and named entity recognition (Section 5) and showed the state-of-the-art results for both tasks. 2 Background 2.1 Nonlinearity in NLP Linear classification algorithms such as Perceptron, Winnow, or Support Vector Machines with a linear kernel have performed exceptionally well for various NLP tasks (Collins, 2002; Zhang and …

Content truncated to 500 words