SOFIE: a self-organizing framework for information extraction

ABSTRACT

This paper presents SOFIE, a system for automated ontology extension. SOFIE can parse natural language documents, extract ontological facts from them and link the facts into an ontology. SOFIE uses logical reasoning on the existing knowledge and on the new knowledge in order to disambiguate words to their most probable meaning, to reason on the meaning of text patterns and to take into account world knowledge axioms. This allows SOFIE to check the plausibility of hypotheses and to avoid inconsistencies with the ontology. The framework of SOFIE unites the paradigms of pattern matching, word sense disambiguation and ontological reasoning in one unified model. Our experiments show that SOFIE delivers high-quality output, even from unstructured Internet documents.

REFERENCES

• 1: Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In ISTCS 1995.
• 2: 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]
• 3: Eneko Agirre , Philip Edmonds, Word Sense Disambiguation: Algorithms and Applications (Text, Speech and Language Technology), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak, Z. G. Ives. Dbpedia: A nucleus for a Web of open data.% In ISWC, volume 4825 of LNCS, pages 722--735. Springer, 2007. In ISWC 2007.
• 5: M. Banko, M. J. Cafarella, S. Soderland, M. Broadhead, O. Etzioni. Open information extraction from the Web. In IJCAI 2007.
• 6: Michele Banko , Oren Etzioni, Strategies for lifelong knowledge extraction from the web, Proceedings of the 4th international conference on Knowledge capture, October 28-31, 2007, Whistler, BC, Canada [doi>10.1145/1298406.1298425]
• 7: M. Battiti, R. Protasi. Approximate algorithms and solutions for Max SAT. In G. Xue, editor, Handbook of Combinatorial Optimization DingZhu Du and Panos M. Pardalos (co-editors), Kluwer Academic Publishers, 1998, Vols. 1--3, ISBN: 0-7923-5285-8, volume 19, pages 425--430, 2001. , Kluwer, 2001.
• 8: Robert Baumgartner , Oliver Frölich , Georg Gottlob, The Lixto Systems Applications in Business Intelligence and Semantic Web, Proceedings of the 4th European conference on The Semantic Web: Research and Applications, June 03-07, 2007, Innsbruck, Austria [doi>10.1007/978-3-540-72667-8_3]
• 9: Sebastian Blohm , Philipp Cimiano, Using the Web to Reduce Data Sparseness in Pattern-Based Information Extraction, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_6]
• 10: S. Blohm, P. Cimiano, E. Stemle. Harvesting relations from the Web-quantifiying the impact of filtering functions. In Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07), pages 1316--1323. Association for the Advancement of Artificial Intelligence (AAAI), JUL 2007. In AAAI 2007.
• 11: 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
• 12: Jianer Chen , Donald K. Friesen , Hao Zheng, Tight bound on Johnson's algorithm for maximum satisfiability, Journal of Computer and System Sciences, v.58 n.3, p.622-640, June 1999 [doi>10.1006/jcss.1998.1612]
• 13: Martin Davis , George Logemann , Donald Loveland, A machine program for theorem-proving, Communications of the ACM, v.5 n.7, p.394-397, July 1962 [doi>10.1145/368273.368557]
• 14: V. de Boer, M. van Someren, B. J. Wielinga. Extracting instances of relations from Web documents using redundancy. In ESWC 2006.
• 15: Gerard de Melo , Fabian Suchanek , Adam Pease, Integrating YAGO into the Suggested Upper Merged Ontology, Proceedings of the 2008 20th IEEE International Conference on Tools with Artificial Intelligence, p.190-193, November 03-05, 2008 [doi>10.1109/ICTAI.2008.34]
• 16: Pedro DeRose , Warren Shen , Fei Chen , AnHai Doan , Raghu Ramakrishnan, Building structured web community portals: a top-down, compositional, and incremental approach, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 17: O. Etzioni, M. Banko, M. J. Cafarella. Machine reading. In AAAI 2006.
• 18: 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]
• 19: C. Fellbaum, editor. WordNet: An Electronic Lexical Database. MIT Press, 1998.
• 20: William A. Gale , Kenneth W. Church , David Yarowsky, One sense per discourse, Proceedings of the workshop on Speech and Natural Language, February 23-26, 1992, Harriman, New York [doi>10.3115/1075527.1075579]
• 21: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 22: Lise Getoor , Ben Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning), The MIT Press, 2007
• 23: Brigitte Jaumard , Bruno Simeone, On the complexity of the maximum satisfiability problem for Horn formulas, Information Processing Letters, v.26 n.1, p.1-4, 15 Sept. 1987 [doi>10.1016/0020-0190(87)90028-7]
• 24: D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci., 9(3):256--278, 1974.
• 25: Douglas B. Lenat , R. V. Guha, Building Large Knowledge-Based Systems; Representation and Inference in the Cyc Project, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 26: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 27: Rolf Niedermeier , Peter Rossmanith, New upper bounds for maximum satisfiability, Journal of Algorithms, v.36 n.1, p.63-88, July 2000 [doi>10.1006/jagm.2000.1075]
• 28: Ian Niles , Adam Pease, Towards a standard upper ontology, Proceedings of the international conference on Formal Ontology in Information Systems, p.2-9, October 17-19, 2001, Ogunquit, Maine, USA [doi>10.1145/505168.505170]
• 29: S. P. Ponzetto and M. Strube. Deriving a large-scale taxonomy from Wikipedia. In AAAI, 2007.
• 30: H. Poon and P. Domingos. Joint inference in information extraction. In AAAI, 2007.
• 31: Cartic Ramakrishnan , Pablo N. Mendes , Shaojun Wang , Amit P. Sheth, Unsupervised Discovery of Compound Entities for Relationship Extraction, Proceedings of the 16th international conference on Knowledge Engineering: Practice and Patterns, September 29-October 02, 2008, Acitrezza, Italy [doi>10.1007/978-3-540-87696-0_15]
• 32: Venkatesh Raman , B. Ravikumar , S. Srinivasa Rao, A simplified NP-complete MAXSAT problem, Information Processing Letters, v.65 n.1, p.1-6, Jan 1, 1998 [doi>10.1016/S0020-0190(97)00223-8]
• 33: F. Reiss, S. Raghavan, R. Krishnamurthy, H. Zhu, S. Vaithyanathan. An algebraic approach to rule-based information extraction. In ICDE 2008.
• 34: Matthew Richardson , Pedro Domingos, Markov logic networks, Machine Learning, v.62 n.1-2, p.107-136, February 2006 [doi>10.1007/s10994-006-5833-1]
• 35: Sunita Sarawagi, Information Extraction, Foundations and Trends in Databases, v.1 n.3, p.261-377, March 2008 [doi>10.1561/1900000003]
• 36: 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
• 37: S. Staab and R. Studer, editors. Handbook on Ontologies, 2nd edition. Springer, 2008.
• 38: F. M. Suchanek. Automated Construction and Growth of a Large Ontology. PhD thesis, Saarland University, Germany, 2008.
• 39: Fabian M. Suchanek , Georgiana Ifrim , Gerhard Weikum, Combining linguistic and statistical analysis to extract relations from web documents, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150492]
• 40: Fabian M. Suchanek , Gjergji Kasneci , Gerhard Weikum, Yago: a core of semantic knowledge, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242667]
• 41: Fabian M. Suchanek , Gjergji Kasneci , Gerhard Weikum, YAGO: A Large Ontology from Wikipedia and WordNet, Web Semantics: Science, Services and Agents on the World Wide Web, v.6 n.3, p.203-217, September, 2008 [doi>10.1016/j.websem.2008.06.001]
• 42: Luca Trevisan , Gregory B. Sorkin , Madhu Sudan , David P. Williamson, Gadgets, Approximation, and Linear Programming, SIAM Journal on Computing, v.29 n.6, p.2074-2097, April 2000 [doi>10.1137/S0097539797328847]
• 43: Octavian Udrea , Lise Getoor , Renée J. Miller, Leveraging data and structure in ontology integration, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247531]
• 44: G. Wang, Y. Yu, H. Zhu. Pore: Positive-only relation extraction from Wikipedia text. In ISWC, 2007.
• 45: N. Weber and P. Buitelaar. Web-based ontology learning with Isolde. In ISWC Workshop on WebContent Mining with Human Language Technologies 2006.
• 46: Fei Wu , Daniel S. Weld, Autonomously semantifying wikipedia, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321449]
• 47: Fei Wu , Daniel S. Weld, Automatically refining the wikipedia infobox ontology, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367583]
• 48: Zhao Xing , Weixiong Zhang, MaxSolver: an efficient exact algorithm for (weighted) maximum satisfiability, Artificial Intelligence, v.164 n.1-2, p.47-80, May 2005 [doi>10.1016/j.artint.2005.01.004]
• 49: Mihalis Yannakakis, On the approximation of maximum satisfiability, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.1-9, September 1992, Orlando, Florida, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

General Terms:
Algorithms, Design

Keywords:
automated reasoning, information extraction, ontology