TEG: a hybrid approach to information extraction

ABSTRACT

This paper describes a hybrid statistical and knowledge-based information extraction model, able to extract entities and relations at the sentence level. The model attempts to retain and improve the high accuracy levels of knowledge-based systems while drastically reducing the amount of manual labor by relying on statistics drawn from a training corpus. The implementation of the model, called TEG (Trainable Extraction Grammar), can be adapted to any IE domain by writing a suitable set of rules in a SCFG (Stochastic Context Free Grammar) based extraction language, and training them using an annotated corpus. The system does not contain any purely linguistic components, such as PoS tagger or parser. We demonstrate the performance of the system on several named entity extraction and relation extraction tasks. The experiments show that our hybrid approach outperforms both purely statistical and purely knowledge-based systems, while requiring orders of magnitude less manual rule writing and smaller amount of training data. The improvement in accuracy is slight for named entity extraction task and more pronounced for relation extraction.

REFERENCES

• 1: Nancy Chinchor , David D. Lewis , Lynette Hirschman, Evaluating message understanding systems: an analysis of the third message understanding conference (MUC-3), Computational Linguistics, v.19 n.3, p.409-449, September 1993
• 2: ACE. http://www.itl.nist.gov/iad/894.01/tests/ace/. in ACE - Automatic Content Extraction. 2002.
• 3: Alexander Yeh , Lynette Hirschman , Alexander Morgan, Background and overview for KDD Cup 2002 task 1: information extraction from biomedical articles, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.87-89, December 2002 [doi>10.1145/772862.772873]
• 4: Daniel M. Bikel , Richard Schwartz , Ralph M. Weischedel, An Algorithm that Learns What‘s in a Name, Machine Learning, v.34 n.1-3, p.211-231, Feb. 1999 [doi>10.1023/A:1007558221122]
• 5: Hai Leong Chieu , Hwee Tou Ng, Named entity recognition: a maximum entropy approach using global information, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan [doi>10.3115/1072228.1072253]
• 6: Andrew McCallum , Dayne Freitag , Fernando C. N. Pereira, Maximum Entropy Markov Models for Information Extraction and Segmentation, Proceedings of the Seventeenth International Conference on Machine Learning, p.591-598, June 29-July 02, 2000
• 7: Ronen Feldman , Yonatan Aumann , Michal Finkelstein-Landau , Eyal Hurvitz , Yizhar Regev , Ariel Yaroshevich, A Comparative Study of Information Extraction Strategies, Proceedings of the Third International Conference on Computational Linguistics and Intelligent Text Processing, p.349-359, February 17-23, 2002
• 8: Kushmerick, N. Finite-state approaches to Web information extraction. in 3rd Summer Convention on Information Extraction. 2002. Rome.
• 9: Freitag, D., Using grammatical inference to improve precision in information extraction, in Workshop on Grammatical Inference, Automata Induction, and Language Acquisition (ICML'97), Nashville, TN. 1997.
• 10: Aitken, J.S. Learning Information Extraction Rules: An Inductive Logic Programming approach. in 15th European Conference on Artificial Intelligence. 2002: IOS Press.
• 11: Dayne Freitag, Information extraction from HTML: application of a general machine learning approach, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.517-523, July 1998, Madison, Wisconsin, United States
• 12: Gunter Grieser , Klaus P. Jantke , Steffen Lange , Bernd Thomas, A Unifying Approach to HTML Wrapper Representation and Learning, Proceedings of the Third International Conference on Discovery Science, p.50-64, December 04-06, 2000
• 13: Leek, T.R., Information extraction using hidden Markov models. M.Sc.Thesis, UC San Diego, 1997.
• 14: Dayne Freitag , Andrew McCallum, Information Extraction with HMM Structures Learned by Stochastic Optimization, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.584-589, July 30-August 03, 2000
• 15: Freitag, D. and A.K. McCallum, Information extraction with HMMs and shrinkage, in Proceedings of the AAAI-99 Workshop on Machine Learning for Informatino Extraction. 1999.
• 16: De Sitter, A. and W. Daelemans. Information Extraction via Double Classification. in International Workshop on Adaptive Text Extraction and Mining. 2003. Dubrovnik.
• 17: Sun, A., et al. Using Support Vector Machine for Terrorism Information Extraction. in 1st NSF/NIJ Symposium on Intelligence and Security Informatics. 2003.
• 18: Kushmerick, N., E. Johnston, and S. McGuinness. Information extraction by text classification. in IJCAI-01 Workshop on Adaptive Text Extraction and Mining. 2001. Seattle, WA.
• 19: 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
• 20: Miller, S., et al., Algorithms that learn to extract information-BBN: Description of the SIFT system as used for MUC, in Proceedings of the Seventh Message Understanding Conference (MUC-7). 1998.
• 21: Collins, M. and S. Miller. Semantic Tagging using a Probabilistic Context Free Grammar. in Proceedings of the Sixth Workshop on Very Large Corpora. 1998.
• 22: Michael Collins, Three generative, lexicalised models for statistical parsing, Proceedings of the 35th annual meeting on Association for Computational Linguistics, p.16-23, July 07-12, 1997, Madrid, Spain
• 23: Eugene Charniak, A maximum-entropy-inspired parser, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.132-139, April 29-May 04, 2000, Seattle, Washington
• 24: Brian Roark , Mark Johnson, Efficient probabilistic top-down and left-corner parsing, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.421-428, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034743]
• 25: Ronen Feldman , Yonatan Aumann , Michal Finkelstein-Landau , Eyal Hurvitz , Yizhar Regev , Ariel Yaroshevich, A Comparative Study of Information Extraction Strategies, Proceedings of the Third International Conference on Computational Linguistics and Intelligent Text Processing, p.349-359, February 17-23, 2002
• 26: Daniel M. Bikel , Scott Miller , Richard Schwartz , Ralph Weischedel, Nymble: a high-performance learning name-finder, Proceedings of the fifth conference on Applied natural language processing, p.194-201, March 31-April 03, 1997, Washington, DC [doi>10.3115/974557.974586]
• 27: Klein, D. and C. Manning, An O(n3) Agenda-Based Chart Parser for Arbitrary Probabilistic Context-Free Grammars., in Technical Report dbpubs/2001. 2001, Stanford University.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation, Languages, Performance, Theory

Keywords:
HMM, information extraction, rules based system, text mining