Uncertainty management in rule-based information extraction systems

ABSTRACT

Rule-based information extraction is a process by which structured objects are extracted from text based on user-defined rules. The compositional nature of rule-based information extraction also allows rules to be expressed over previously extracted objects. Such extraction is inherently uncertain, due to the varying precision associated with the rules used in a specific extraction task. Quantifying this uncertainty is crucial for querying the extracted objects in probabilistic databases, and for improving the recall of extraction tasks that use compositional rules. In this paper, we provide a probabilistic framework for handling the uncertainty in rule-based information extraction. Specifically, for each extraction task, we build a parametric exponential model of uncertainty that captures the interaction between the different rules, as well as the compositional nature of the rules; the exponential form of our model follows from maximum-entropy considerations. We also give model-decomposition techniques that make the learning algorithms scalable to large numbers of rules and constraints. Experiments over multiple real-world extraction tasks confirm that our approach yields accurate probability estimates with only a small performance overhead. Moreover, our framework supports incremental pay-as-you-go improvements in the accuracy of probability estimates as new rules, data, or constraints are added.

REFERENCES

• 1: Automatic Content Extraction 2005 Evaluation (ACE05) Dataset, http://www.nist.gov/speech/tests/ace/2005/.
• 2: Lyublena Antova , Thomas Jansen , Christoph Koch , Dan Olteanu, Fast and Simple Relational Processing of Uncertain Data, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.983-992, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497507]
• 3: Douglas E. Appelt , Boyan Onyshkevych, The common pattern specification language, Proceedings of a workshop on held at Baltimore, Maryland: October 13-15, 1998, October 13-15, 1998, Baltimore, Maryland [doi>10.3115/1119089.1119095]
• 4: Douglas E. Appelt, Introduction to information extraction, AI Communications, v.12 n.3, p.161-172, August 1999
• 5: M. Avriel. Nonlinear Programming. Prentice-Hall, 1976.
• 6: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Martin Theobald , Jennifer Widom, Databases with uncertainty and lineage, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.2, p.243-264, March 2008 [doi>10.1007/s00778-007-0080-z]
• 7: B. Boguraev. Annotation-based finite state processing in a large-scale NLP architecture. In RANLP, pages 61--80, 2003.
• 8: Mary Elaine Califf , Raymond J. Mooney, Relational learning of pattern-match rules for information extraction, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.328-334, July 18-22, 1999, Orlando, Florida, United States
• 9: H. Cunningham, D.Maynard, and V. Tablan. JAPE: a Java annotation patterns engine. Technical report, Dept. of Computer Science, University of Sheffield, 2000.
• 10: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 11: Oren Etzioni , Michele Banko , Stephen Soderland , Daniel S. Weld, Open information extraction from the web, Communications of the ACM, v.51 n.12, December 2008 [doi>10.1145/1409360.1409378]
• 12: Warren R. Greiff , Jay M. Ponte, The maximum entropy approach and probabilistic IR models, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.246-287, July 2000 [doi>10.1145/352595.352597]
• 13: Rahul Gupta , Sunita Sarawagi, Creating probabilistic databases from information extraction models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 14: Ravi Jampani , Fei Xu , Mingxi Wu , Luis Leopoldo Perez , Christopher Jermaine , Peter J. Haas, MCDB: a monte carlo approach to managing uncertain data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376686]
• 15: T. Jayram, R. Krishnamurthy, S. Raghavan, S. Vaithyanathan, and H. Zhu. Avatar information extraction system. IEEE Data Engrg. Bull., 29(1):40--48, 2006.
• 16: Nanda Kambhatla, Combining lexical, syntactic, and semantic features with maximum entropy models for extracting relations, Proceedings of the ACL 2004 on Interactive poster and demonstration sessions, p.22-es, July 21-26, 2004, Barcelona, Spain [doi>10.3115/1219044.1219066]
• 17: Rajasekar Krishnamurthy , Yunyao Li , Sriram Raghavan , Frederick Reiss , Shivakumar Vaithyanathan , Huaiyu Zhu, SystemT: a system for declarative information extraction, ACM SIGMOD Record, v.37 n.4, December 2008 [doi>10.1145/1519103.1519105]
• 18: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 19: Sofus A. Macskassy , Haym Hirsh , Arunava Banerjee , Aynur A. Dayanik, Converting numerical classification into text classification, Artificial Intelligence, v.143 n.1, p.51-77, January 2003 [doi>10.1016/S0004-3702(02)00359-4]
• 20: Robert Malouf, A comparison of algorithms for maximum entropy parameter estimation, proceedings of the 6th conference on Natural language learning, p.1-7, August 31, 2002 [doi>10.3115/1118853.1118871]
• 21: V. Markl , P. J. Haas , M. Kutsch , N. Megiddo , U. Srivastava , T. M. Tran, Consistent selectivity estimation via maximum entropy, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.1, p.55-76, January 2007 [doi>10.1007/s00778-006-0030-1]
• 22: B. Marthi, B. Milch, and S. Russell. First-order probabilistic models for information extraction. In IJCAI 2003 Workshop on Learning Statistical Models from Relational Data, 2003.
• 23: J. McCarthy and W. Lehnert. Using decision trees for coreference resolution. In IJCAI, pages 1050--1055, 1995.
• 24: Einat Minkov , Richard C. Wang , William W. Cohen, Extracting personal names from email: applying named entity recognition to informal text, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.443-450, October 06-08, 2005, Vancouver, British Columbia, Canada [doi>10.3115/1220575.1220631]
• 25: Vincent Ng , Claire Cardie, Improving machine learning approaches to coreference resolution, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073102]
• 26: K. Nigam, J. Lafferty, and A. McCallum. Using maximum entropy for text classification. In IJCAI Workshop on Machine Learning for Information Filtering, 1999.
• 27: Bo Pang , Lillian Lee , Shivakumar Vaithyanathan, Thumbs up?: sentiment classification using machine learning techniques, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.79-86, July 06, 2002 [doi>10.3115/1118693.1118704]
• 28: L. Peshkin and A. Pfeffer. Bayesian information extraction network. In IJCAI, pages 421--426, 2003.
• 29: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 30: H. Poon and P. Domingos. Joint inference in information extraction. In AAAI, pages 913--918, 2007.
• 31: Hoifung Poon , Pedro Domingos, Joint unsupervised coreference resolution with Markov logic, Proceedings of the Conference on Empirical Methods in Natural Language Processing, October 25-27, 2008, Honolulu, Hawaii
• 32: Frederick Reiss , Sriram Raghavan , Rajasekar Krishnamurthy , Huaiyu Zhu , Shivakumar Vaithyanathan, An Algebraic Approach to Rule-Based Information Extraction, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.933-942, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497502]
• 33: Prithviraj Sen , Amol Deshpande , Lise Getoor, Exploiting shared correlations in probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453944]
• 34: Warren Shen , AnHai Doan , Jeffrey F. Naughton , Raghu Ramakrishnan, Declarative information extraction using datalog with embedded extraction predicates, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 35: C. Siefkes. Incremental information extraction using tree--based context representations. In CICLing, pages 510--521, 2005.
• 36: C. Siefkes and P. Siniakov. An overview and classification of adaptive approaches to information extraction. LNCS J. Data Semantics IV, pages 172--212, 2005.
• 37: M. Skounakis, M. Craven, and S. Ray. Hierarchical hidden Markov models for information extraction. In IJCAI, pages 427--433, 2003.
• 38: Charles Sutton , Andrew McCallum, Piecewise pseudolikelihood for efficient training of conditional random fields, Proceedings of the 24th international conference on Machine learning, p.863-870, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273605]
• 39: System Text for Information Extraction http://www.alphaworks.ibm.com/tech/systemt.
• 40: Peter D. Turney, Thumbs up or thumbs down?: semantic orientation applied to unsupervised classification of reviews, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073153]
• 41: Daisy Zhe Wang , Eirinaios Michelakis , Minos Garofalakis , Joseph M. Hellerstein, BayesStore: managing large, uncertain data repositories with probabilistic graphical models, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453896]
• 42: Q. Xu, Y. Liang, and Y. Du. Monte Carlo cross-validation for selecting a model and estimating the prediction error in multivariate calibration. J. Chemometrics, 18(2):112--120, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

General Terms:
Algorithms, Experimentation, Performance

Keywords:
information extraction, maximum entropy, probabilistic modeling