Regular Expression Learning for Information Extraction

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 21–30, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Regular Expression Learning for Information Extraction Yunyao Li, Rajasekar Krishnamurthy, Sriram Raghavan, Shivakumar Vaithyanathan IBM Almaden Research Center San Jose, CA 95120 {yunyaoli, rajase, rsriram}@us.ibm.com, shiv@almaden.ibm.com H. V. Jagadish∗ Department of EECS University of Michigan Ann Arbor, MI 48109 jag@umich.edu Abstract Regular expressions have served as the dom- inant workhorse of practical information ex- traction for several years. However, there has been little work on reducing the manual ef- fort involved in building high-quality, com- plex regular expressions for information ex- traction tasks. In this paper, we propose Re- LIE, a novel transformation-based algorithm for learning such complex regular expressions. We evaluate the performance of our algorithm on multiple datasets and compare it against the CRF algorithm. We show that ReLIE, in ad- dition to being an order of magnitude faster, outperforms CRF under conditions of limited training data and cross-domain data. Finally, we show how the accuracy of CRF can be im- proved by using features extracted by ReLIE. 1 Introduction A large class of entity extraction tasks can be ac- complished by the use of carefully constructed reg- ular expressions (regexes). Examples of entities amenable to such extractions include email ad- dresses and software names (web collections), credit card numbers and social security numbers (email compliance), and gene and protein names (bioinfor- matics), etc. These entities share the characteristic that their key representative patterns (features) are expressible in standard constructs of regular expres- sions. At first glance, it may seem that constructing ∗Supported in part by NSF 0438909 and NIH 1-U54- DA021519. a regex to extract such entities is fairly straightfor- ward. In reality, robust extraction requires the use of rather complex expressions, as illustrated by the following example. Example 1 (Phone number extraction). An obvious pattern for identifying phone numbers is “blocks of digits separated by hyphens” represented as R1 = (\d+\-)+\d+.1 While R1 matches valid phone numbers like 800-865-1125 and 725-1234, it suffers from both “precision” and “recall” problems. Not only does R1 produce incorrect matches (e.g., social security numbers like 123-45-6789), it also fails to identify valid phone numbers such as 800.865.1125, and (800)865-CARE. An improved regex that addresses these problems is R2 = (\d{3}[-.\ ()]){1,2}[\dA-Z]{4}. While multiple machine learning approaches have been proposed for information extraction in recent years (McCallum et al., 2000; Cohen and McCal- lum, 2003; Klein et al., 2003; Krishnan and Man- ning, 2006), manually created regexes remain a widely adopted practical solution for information extraction (Appelt and Onyshkevych, 1998; Fukuda et al., 1998; Cunningham, 1999; Tanabe and Wilbur, 2002; Li et al., 2006; DeRose et al., 2007; Zhu et al., 2007). Yet, with a few notable exceptions, which we discuss later in Section 1.1, there has been very little work in reducing this human effort through the use of automatic learning techniques. In this paper, we propose a novel formulation of the problem of learn- 1Throughout this paper, …

Content truncated to 500 words