A quality-aware optimizer for information extraction

ABSTRACT

A large amount of structured information is buried in unstructured text. Information extraction systems can extract structured relations from the documents and enable sophisticated, SQL-like queries over unstructured text. Information extraction systems are not perfect and their output has imperfect precision and recall (i.e., contains spurious tuples and misses good tuples). Typically, an extraction system has a set of parameters that can be used as “knobs” to tune the system to be either precision- or recall-oriented. Furthermore, the choice of documents processed by the extraction system also affects the quality of the extracted relation. So far, estimating the output quality of an information extraction task has been an ad hoc procedure, based mainly on heuristics. In this article, we show how to use Receiver Operating Characteristic (ROC) curves to estimate the extraction quality in a statistically robust way and show how to use ROC analysis to select the extraction parameters in a principled manner. Furthermore, we present analytic models that reveal how different document retrieval strategies affect the quality of the extracted relation. Finally, we present our maximum likelihood approach for estimating, on the fly, the parameters required by our analytic models to predict the runtime and the output quality of each execution plan. Our experimental evaluation demonstrates that our optimization approach predicts accurately the output quality and selects the fastest execution plan that satisfies the output quality restrictions.

REFERENCES

• 1: Adamic, L. A. and Huberman, B. A. 2002. Zipf's law and the Internet. Glottometrics 3, 143--150.
• 2: Yevgeny (Eugene) Agichtein , Luis Gravano, Extracting relations from large text collections, Columbia University, New York, NY, 2005
• 3: Eugene Agichtein , Luis Gravano, Snowball: extracting relations from large plain-text collections, Proceedings of the fifth ACM conference on Digital libraries, p.85-94, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336644]
• 4: Agichtein, E. and Gravano, L. 2003. Querying text databases for efficient information extraction. In Proceedings of the 19th IEEE International Conference on Data Engineering (ICDE'03).
• 5: Agichtein, E., Ipeirotis, P. G., and Gravano, L. 2003. Modeling query-based access to text databases. In Proceedings of the 6th International Workshop on the Web and Databases, (WebDB'03), 87--92.
• 6: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 7: Sergey Brin, Extracting Patterns and Relations from the World Wide Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.172-183, March 27-28, 1998
• 8: Michael J. Cafarella , Oren Etzioni, A search engine for natural language applications, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060811]
• 9: Cafarella, M. J., Re, C., Suciu, D., Etzioni, O., and Banko, M. 2007. Structured querying of Web text: A technical challenge. In 3rd Biennial Conference on Innovative Data Systems Research (CIDR'07).
• 10: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.436-447, June 01-04, 1998, Seattle, Washington, United States
• 11: Cohen, W. W. 1995. Fast effective rule induction. In Proceedings of the 12th International Conference on Machine Learning (ICML'95), 115--123.
• 12: Cohen, W. W. 2004. Minorthird: Methods for identifying names and ontological relations in text using heuristics for inducing regularities from data. http://minorthird.sourceforge.net.
• 13: Downey, D., Etzioni, O., and Soderland, S. 2005. A probabilistic model of redundancy in information extraction. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05), 1034--1041.
• 14: Egan, J. P. 1975. Signal Detection Theory and ROC Analysis. Academic Press.
• 15: Erdreich, L. S. and Lee, E. T. 1981. Use of relative operating characteristic analysis in epidemiology. Amer. J. Epidemiol. 114, 5, 649--662.
• 16: Oren Etzioni , Michael Cafarella , Doug Downey , Stanley Kok , Ana-Maria Popescu , Tal Shaked , Stephen Soderland , Daniel S. Weld , Alexander Yates, Web-scale information extraction in knowitall: (preliminary results), Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988687]
• 17: Fawcett, T. 2003. ROC graphs: Notes and practical considerations for data mining researchers. Tech. rep., HPL-2003-4, HP Labs.
• 18: Gelman, A., Carlin, J. B., Stern, H. S., and Rubin, D. B. 2003. Bayesian Data Analysis, 2nd ed. Chapman and Hall/CRC.
• 19: Goldstein, M., Morris, S., and Yen, G. G. 2004. Problems with fitting to the power-law distribution. The Eur. Phys. J. B - Condensed Matter Complex Syst. 41, 2, 255--258.
• 20: Ralph Grishman, Information Extraction: Techniques and Challenges, International Summer School on Information Extraction: A Multidisciplinary Approach to an Emerging Information Technology, p.10-27, January 1997
• 21: Ralph Grishman , Silja Huttunen , Roman Yangarber, Information extraction for enhanced access to disease outbreak reports, Journal of Biomedical Informatics, v.35 n.4, p.236-246, August 2002 [doi>10.1016/S1532-0464(03)00013-3]
• 22: 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
• 23: Hiyakumoto, L., Lita, L. V., and Nyberg, E. 2005. Multi-Strategy information extraction for question answering. In Proceedings of the International Florida Artificial Intelligence Research Society Conference (FLAIRS'05), 678--683.
• 24: Panagiotis G. Ipeirotis , Eugene Agichtein , Pranay Jain , Luis Gravano, To search or to crawl?: towards a query optimizer for text-centric tasks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142504]
• 25: Panagiotis G. Ipeirotis , Eugene Agichtein , Pranay Jain , Luis Gravano, Towards a query optimizer for text-centric tasks, ACM Transactions on Database Systems (TODS), v.32 n.4, p.21-es, November 2007 [doi>10.1145/1292609.1292611]
• 26: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 27: Jain, A., Doan, A., and Gravano, L. 2007a. Optimizing SQL queries over text databases. In Proceedings of the 24th IEEE International Conference on Data Engineering (ICDE'08). 636--645.
• 28: Jain, A., Doan, A., and Gravano, L. 2007b. SQL queries over unstructured text databases. In Proceedings of the 23rd IEEE International Conference on Data Engineering (ICDE'07).
• 29: Alpa Jain , Panagiotis Ipeirotis , Luis Gravano, Building query optimizers for information extraction: the SQoUT project, ACM SIGMOD Record, v.37 n.4, December 2008 [doi>10.1145/1519103.1519108]
• 30: Sofus A. Macskassy , Foster Provost , Saharon Rosset, ROC confidence bands: an empirical evaluation, Proceedings of the 22nd international conference on Machine learning, p.537-544, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102419]
• 31: Imran R. Mansuri , Sunita Sarawagi, Integrating Unstructured Data into Relational Databases, Proceedings of the 22nd International Conference on Data Engineering, p.29, April 03-07, 2006 [doi>10.1109/ICDE.2006.83]
• 32: Newman, M. E. J. 2005. Power laws, Pareto distributions and Zipf's law. Contemporary Phys. 46, 5, 323--351.
• 33: Marius Paşca , Dekang Lin , Jeffrey Bigham , Andrei Lifchits , Alpa Jain, Names and similarities on the web: fact extraction in the fast lane, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, p.809-816, July 17-18, 2006, Sydney, Australia [doi>10.3115/1220175.1220277]
• 34: Foster Provost , Tom Fawcett, Robust Classification for Imprecise Environments, Machine Learning, v.42 n.3, p.203-231, March 2001 [doi>10.1023/A:1007601015854]
• 35: Ellen Riloff , Rosie Jones, Learning dictionaries for information extraction by multi-level bootstrapping, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.474-479, July 18-22, 1999, Orlando, Florida, United States
• 36: Victor S. Sheng , Foster Provost , Panagiotis G. Ipeirotis, Get another label? improving data quality and data mining using multiple, noisy labelers, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401965]
• 37: Yangarber, R. and Grishman, R. 1998. NYU: Description of the Proteus/PET system as used for MUC-7. In Proceedings of the 7th Message Understanding Conference (MUC-7).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
Information Extraction, ROC curves