Improving the Scalability of Semi-Markov Conditional Random Fields for Named Entity Recognition

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 465–472, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Improving the Scalability of Semi-Markov Conditional Random Fields for Named Entity Recognition Daisuke Okanohara† Yusuke Miyao† Yoshimasa Tsuruoka ‡ †Department of Computer Science, University of TokyoJun’ichi Tsujii†‡§ Hongo 7-3-1, Bunkyo-ku, Tokyo, Japan ‡School of Informatics, University of Manchester POBox 88, Sackville St, MANCHESTER M60 1QD, UK §SORST, Solution Oriented Research for Science and Technology Honcho 4-1-8, Kawaguchi-shi, Saitama, Japan {hillbig,yusuke,tsuruoka,tsujii}@is.s.u-tokyo.ac.jp Abstract This paper presents techniques to apply semi-CRFs to Named Entity Recognition tasks with a tractable computational cost. Our framework can handle an NER task that has long named entities and many labels which increase the computational cost. To reduce the computational cost, we propose two techniques: the first is the use of feature forests, which enables us to pack feature-equivalent states, and the sec- ond is the introduction of a filtering pro- cess which significantly reduces the num- ber of candidate states. This framework allows us to use a rich set of features ex- tracted from the chunk-based representa- tion that can capture informative charac- teristics of entities. We also introduce a simple trick to transfer information about distant entities by embedding label infor- mation into non-entity labels. Experimen- tal results show that our model achieves an F-score of 71.48% on the JNLPBA 2004 shared task without using any external re- sources or post-processing techniques. 1 Introduction The rapid increase of information in the biomedi- cal domain has emphasized the need for automated information extraction techniques. In this paper we focus on the Named Entity Recognition (NER) task, which is the first step in tackling more com- plex tasks such as relation extraction and knowl- edge mining. Biomedical NER (Bio-NER) tasks are, in gen- eral, more difficult than ones in the news domain. For example, the best F-score in the shared task of Bio-NER in COLING 2004 JNLPBA (Kim et al., 2004) was 72.55% (Zhou and Su, 2004) 1, whereas the best performance at MUC-6, in which systems tried to identify general named entities such as person or organization names, was an accuracy of 95% (Sundheim, 1995). Many of the previous studies of Bio-NER tasks have been based on machine learning techniques including Hidden Markov Models (HMMs) (Bikel et al., 1997), the dictionary HMM model (Kou et al., 2005) and Maximum Entropy Markov Mod- els (MEMMs) (Finkel et al., 2004). Among these methods, conditional random fields (CRFs) (Laf- ferty et al., 2001) have achieved good results (Kim et al., 2005; Settles, 2004), presumably because they are free from the so-called label bias problem by using a global normalization. Sarawagi and Cohen (2004) have recently in- troduced semi-Markov conditional random fields (semi-CRFs). They are defined on semi-Markov chains and attach labels to the subsequences of a sentence, rather than to the tokens2. The semi- Markov formulation allows one to easily construct entity-level features. Since the features can cap- ture all the characteristics of a …

Content truncated to 500 words