A Feature Induction Algorithm with Application to Named Entity Disambiguation

Proceedings of Recent Advances in Natural Language Processing, pages 685–691, Hissar, Bulgaria, 7-13 September 2013. A Feature Induction Algorithm with Application to Named Entity Disambiguation Laura Tolos¸i, Valentin Zhikov, Georgi Georgiev, Borislav Popov OntotextAD laura.tolosi, valentin.zhikov, georgi.georgiev, borislav.popov@ontotext.com Abstract The performance of NLP classifiers largely depends on the quality of the features considered for prediction (feature engineering). However, as the number of features increases, the more likely overfit- ting becomes and performance decreases. Also, due to the very large number of features, only slimple linear classifiers are considered, thus disregarding potentially predictive non-linear combinations of features. Here we propose an automated method for feature induction, which selects and includes in the model features and feature combinations which are likely to be useful for the prediction.The result- ing model relies on a smaller feature set, is non-linear and is more accurate than the baseline, which is the model trained on the entire feature set. The method uses a greedy filtering approach based on various univariate measures of feature relevance and it is very fast in practice. Also, our feature induction method is independent of the classifier used: we applied it together with Na¨ıve Bayes and Perceptron models. 1 Introduction NLP classification tasks are characterized by a very large number of features. When the num- ber of available samples is smaller (for example several orders of magnitude less samples), over- fitting can occur, leading to poor performance. In order to avoid overfitting, feature selection is com- monly applied. In (Guyon and Elisseeff, 2003), the main approaches to feature selection are sum- marized: filter, wrapper and embedded methods. Filters use some scoring measure to quantify the predictivity of each feature independently. Then, features are ranked and only the top scoring ones are kept in the final model. The most popular measures for feature predictivity are Mutual In- formation (Lewis, 1992; Taira and Haruno, 1999), Information Gain (Uguz, 2011; Yang and Peder- sen, 1997), Kullback-Leibler divergence (Lee and Lee, 2006; Schneider, 2004; Lee et al., 2011), Chi-squared statistics (Yang and Pedersen, 1997; Mesleh, 2007), Fisher statistics, Pearson corre- lation, etc. In (Yang and Pedersen, 1997) and (Forman, 2003), comparisons of the most popular methods are presented. Filter methods are com- putationally fast, but the univariate scoring can lead to the elimination of features that are use- ful only in combinations (Guyon and Elisseeff, 2003). Wrapper methods (Kohavi and John, 1997) can score subsets of features directly, by evalu- ating the performance of the classifier on the re- spective subset. A strategy of iteratively updat- ing the subset of features is used, with the goal of finding a (close to) optimal subset. Forward se- lection, backward elimination, branch-and-bound (Narendra and Fukunaga, 1977), simulated an- nealing (Ekbal et al., 2011), genetic algorithms (Yang and Honavar, 1998) are among the most popular strategies. Wrapper methods tend to be slow in practice, because a classifier needs to be trained at each iteration. Embedded methods are explicitly optimizing an objective function that in- corporates feature selection. In general, the …

Content truncated to 500 words