Differential Evolution Based Feature Selection and Classifier Ensemble for Named Entity Recognition

Proceedings of COLING 2012: Technical Papers, pages 2475–2490, COLING 2012, Mumbai, December 2012. Differential Evolution based Feature Selection and Classifier Ensemble for Named Entity Recognition Utpal Kumar Sikdar Asif Ekbal∗ Sriparna Saha∗ Department of Computer Science and Engineering Indian Institute of Technology Patna, Patna, India {utpal.sikdar,asif,sriparna}@iitp.ac.in ABSTRACT In this paper, we propose a differential evolution (DE) based two-stage evolutionary approach for named entity recognition (NER). The first stage concerns with the problem of relevant feature selection for NER within the frameworks of two popular machine learning algorithms, namely Conditional Random Field (CRF) and Support Vector Machine (SVM). The solutions of the final best population provides different diverse set of classifiers; some are effective with respect to recall whereas some are effective with respect to precision. In the second stage we propose a novel technique for classifier ensemble for combining these classifiers. The approach is very general and can be applied for any classification problem. Currently we evaluate the pro- posed algorithm for NER in three popular Indian languages, namely Bengali, Hindi and Telugu. In order to maintain the domain-independence property the features are selected and developed mostly without using any deep domain knowledge and/or language dependent resources. Experi- mental results show that the proposed two stage technique attains the final F-measure values of 88.89%, 88.09% and 76.63% for Bengali, Hindi and Telugu, respectively. The key contribu- tions of this work are two-fold, viz. (i). proposal of differential evolution (DE) based feature selection and classifier ensemble methods that can be applied to any classification problem; and (ii). scope of the development of language independent NER systems in a resource-poor scenario. KEYWORDS: Named Entity Recognition, Differential Evolution, Feature Selection, Classifier Ensemble. Authors equaly contributed for this paper. * corresponding authors 2475 1 Introduction Named Entity Recognition (NER) aims to identify and classify each word of a document into some predefined target categories such as person, location, organization, miscellaneous (e.g., date, time, number, percentage, monetary expressions etc.) and none-of-the-above. Over the decades, it has shown success in almost all application areas of Natural Language Pro- cessing (NLP) that includes information retrieval, information extraction, machine translation, question-answering and automatic summarization etc. Proper identification and classification of NEs are very crucial and pose a big challenge to the NLP researchers. The main challenge is due to the fact that named entity (NE) expressions are hard to analyze using traditional NLP because they belong to the open class of expressions, i.e., there is an infinite variety and new expressions are constantly being invented. The problem of NER was actually formulated in Message Understanding Conferences (MUCs) [MUC6; MUC7] (Chinchor, 1995, 1998). The issues of correct identification of NEs were specif- ically addressed and benchmarked by the developers of information extraction system, such as the GATE system (Cunningham, 2002). The existing approaches for NER can be grouped into three main categories, namely rule-based, machine learning based and hybrid approach. Majority of the research focussed on machine learning (ML) approaches (Bikel et al., 1999; Borthwick, 1999; Sekine, 1998; Lafferty …

Content truncated to 500 words