A Named Entity Recognition Method based on Decomposition and Concatenation of Word Chunks

Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 828–836, Chiang Mai, Thailand, November 8 – 13, 2011. c⃝2011 AFNLP A Named Entity Recognition Method based on Decomposition and Concatenation of Word Chunks Tomoya Iwakura† Hiroya Takamura‡ Manabu Okumura‡ †Fujitsu Laboratories Ltd. iwakura.tomoya@jp.fujitsu.com ‡Precision and Intelligence Laboratory, Tokyo Institute of Technology {takamura,oku}@pi.titech.ac.jp Abstract We propose a Named Entity (NE) recog- nition method in which word chunks are repeatedly decomposed and concatenated. We can obtain features from word chunks, such as the first word of a word chunk and the last word of a word chunk, which can- not be obtained in word-sequence-based recognition methods. However, each word chunk may include a part of an NE or mul- tiple NEs. To solve this problem, we use the following operators: SHIFT for sepa- rating the first word from a word chunk, POP for separating the last word from a word chunk, JOIN for concatenating two word chunks, and REDUCE for assigning an NE label to a word chunk. We evalu- ate our method on a Japanese NE recog- nition data set that includes about 200,000 annotations of 191 types of NEs from over 8,500 news articles. The experimental re- sults show that the training and processing speeds of our method are faster than those of a linear-chain structured perceptron and a semi-Markov perceptron while high ac- curacy is maintained. 1 Introduction Named Entity (NE) recognition is a process by which the names of particular classes and nu- meric expressions are recognized in text. NEs include person names, locations, organizations, dates, times, and so on. NE recognition is one of the basic technologies used in text processing, in- cluding Information Extraction (IE), Question An- swering (QA), and Information Retrieval (IR). Supervised learning algorithms have been ap- plied successfully to create NE recognizers. In the early stages, algorithms for training classi- fiers, including Maximum Entropy Models (Uchi- moto et al., 2000), AdaBoost (Carreras et al., 2002), and Support Vector Machines (Yamada, 2007) were widely used. Recently, learning al- gorithms for structured prediction, such as linear- chain Conditional Random Fields (CRFs) (Laf- ferty et al., 2001), linear-chain structured per- ceptron (Collins, 2002a), semi-Markov perceptron (Cohen and Sarawagi, 2004), and semi-Markov Conditional Random Fields (Sarawagi and Cohen, 2004), have been widely used because of their good performances in terms of accuracy. However, the computational cost of using these algorithms for structured prediction can become problematic when we handle a large number of types of NE classes. The computational cost of learning first-order-Markov models with linear- chain CRFs or structured perceptron is O(K2N), where K is the number of types of classes and N is the length of the sentence. Semi-Markov- based algorithms, such as semi-Markov percep- tron and semi-Markov CRFs, enumerate NE can- didates represented by word chunks in advance for capturing features such as the first word of a chunk and the last word of a chunk. Therefore, the computational cost of a semi-Markov perceptron is O(KLN), where L is the upper …

Content truncated to 500 words