Learning Ontology Relations by Combining Corpus-Based Techniques and Reasoning on Data from Semantic Web Sources

Wohlgenannt, Gerhard Book — Digitized Version Learning Ontology Relations by Combining Corpus-Based Techniques and Reasoning on Data from Semantic Web Sources Forschungsergebnisse der Wirtschaftsuniversität Wien, No. 44 Provided in Cooperation with: Peter Lang International Academic Publishers Suggested Citation: Wohlgenannt, Gerhard (2011) : Learning Ontology Relations by Combining Corpus-Based Techniques and Reasoning on Data from Semantic Web Sources, Forschungsergebnisse der Wirtschaftsuniversität Wien, No. 44, ISBN 978-3-631-75384-2, Peter Lang International Academic Publishers, Berlin, https://doi.org/10.3726/b13903 This Version is available at: https://hdl.handle.net/10419/182876 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Learning Ontology Relations by Combining CorpusBased Techniques and Reasoning on Data from Semantic Web Sources FORSCHUNGSERGEBNISSE DER WIRTSCHAFTSUNIVERSITÄT WIEN GERHARD WOHLGENANNT The manual construction of formal domain conceptualizations (ontologies) is labor-intensive. Ontology learning, by contrast, provides (semi-)automatic ontology generation from input data such as domain text. This thesis proposes a novel approach for learning labels of non-taxonomic ontology relations. It combines corpus-based techniques with reasoning on Semantic Web data. Corpusbased methods apply vector space similarity of verbs co-occurring with labeled and unlabeled relations to calculate relation label suggestions from a set of candidates. A meta ontology in combination with Semantic Web sources such as DBpedia and OpenCyc allows reasoning to improve the suggested labels. An extensive formal evaluation demonstrates the superior accuracy of the presented hybrid approach. Gerhard Wohlgenannt is a senior researcher at the New Media Technology Department, MODUL University Vienna. He received his PhD from the Institute for Information Business at Vienna University of Economics and Business (WU). His research interests include ontology learning, text mining and the Semantic Web. FORSCHUNGSERGEBNISSE DER WIRTSCHAFTSUNIVERSITÄT WIEN GERHARD WOHLGENANNT Learning Ontology Relations by Combining Corpus-Based Techniques and Reasoning on Data from Semantic Web Sources Learning Ontology Relations by Combining Corpus-Based Techniques and Reasoning on Data from Semantic Web Sources Forschungsergebnisse der Wirtschaftsuniversitat Wien ,.,,_ "ll./ ~MVUlnlT WIINVIENNA UNMltSITYOF ECONOMICS AND IUSINESS Band 44 • PETER LANG Frankfurt am Main · Berlin · Bern · Bruxelles · New York· Oxford· Wien GERHARD WOHLGENANNT Learning Ontology Relations by Combining Corpus-Based Techniques and Reasoning on Data from Semantic Web Sources £ PETER LANG lnternationaler Verlag der Wissenschaften Open Access: The online version of this publication is published on www.peterlang.com and www.econstor.eu under the international Creative Commons License CC-BY 4.0. Learn more on how you can use and share this work: http://creativecommons. org/licenses/by/4.0. This book is available Open Access thanks to the kind support of ZBW – Leibniz-Informationszentrum Wirtschaft. ISBN 978-3-631-75384-2 (eBook) Bibliographic Information published by the Deutsche Nationalbibliothek The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data is available in the internet at http://dnb.d-nb.de. Q) :$ Cover design: Atelier Platen according to a design of Werner WeiBhappl. University logo of the Vienna University of Economics and Business Administration. Printed with kind permission of the University. Sponsored by the Vienna University of Economics and Business Administration. ISSN 1613-3056 ISBN 978-3-631-60651-3 © Peter Lang GmbH lnternationaler Verlag der Wissenschaften Frankfurt am Main 2011 All rights reserved. All parts of this publication are protected by copyright. Any utilisation outside the strict limits of the copyright law, without the permission of the publisher, is forbidden and liable to prosecution. This applies in particular to reproductions, translations, microfilming, and storage and processing in electronic retrieval systems. www.peterlang.de Contents 1 Introduction 2 The Semantic Web 2.1 Overview . . . . . . . . . . . . . 2.1.1 Background and Vision . 2.1.2 Features ........ . 2.1.3 Misconceptions and Criticism 2.2 Applications . . . . . . . . . . . . . . 3 Ontologies 3.1 Fundamentals . . . . . . . . . 3.1.1 Purpose . . . . . . . . 3.1.2 Structure and Entities 3.1.3 Ontology Research Fields 3.2 Representation . . . . . . . . . . 3.2.1 Resource Description Framework 3.2.2 RDF Schema . . . . . . 3.2.3 Web Ontology Language 3.3 Querying and Reasoning . . 3.3.1 SPARQL and RDQL 3.3.2 Reasoning with Jena 3.3.3 Redland . . . . . . . 3.4 Public Datasets and Ontologies 3.4.1 DBpedia . 3.4.2 Freebase ........ . 3.4.3 OpenCyc 4 Methodology 4.1 Ontology Learning ............... . 4.2 Methods for Learning Semantic Associations .. 4.2.1 Natural Language Processing Techniques 19 23 23 23 26 27 28 33 33 34 35 37 40 42 51 56 63 64 67 68 69 69 73 74 77 78 81 81 6 5 4.3 4.4 4.5 4.6 CONTENTS 4.2.2 Lexico-syntactic Patterns . . . . . . . . . . . . . . . . . 85 4.2.3 Relevant Statistical and Information Retrieval Measures and Methods . . . . . . . . . 89 4.2.4 Machine Learning Paradigms . . . . . . 98 Literature Review . . . . . . . . . . . . . . . . . . 106 4.3.1 Domain Text and Semantic Associations . 107 4.3.2 The Web and Semantic Associations . 110 4.3.3 Domain Text and Linguistic Patterns . 111 4.3.4 The Web and Linguistic Patterns . . 112 4.3.5 Semantic Web Data and Reasoning 116 4.3.6 Selected Work from SemEval2007 119 4.3. 7 Learning of Qualia Structures . webLyzard Ontology Learning System . 4.4.1 System Overview . . . . . . . . . 4.4.2 Major Components of the Framework . 4.4.3 Identification of the Most Relevant Concepts . 4.4.4 Concept Positioning and Taxonomy Discovery 121 122 . 122 . 124 . 126 . 126 A Novel Method to Detect Relations . . . . . . . . . . 127 4.5.1 Relation Labeling Based on Vector Space Similarity . 129 4.5.2 Ontological Restrictions and Integration of External Knowledge. . . . . . . . . . . . . . . . . . 136 4.5.3 The Knowledge Base . . . . . . . . . . . . 144 4.5.4 A Hybrid Method for Relation Labeling . 145 4.5.5 Integration of User Feedback . . 148 Implementation of the Method . . . . . . . . 149 4.6.1 Training . . . . . . . . . . . . . . . . 150 4.6.2 Compute Vector Space Similarities . 152 4.6.3 Ontological Restrictions and Concept Grounding . 153 4.6.4 Scarlet . . . . 156 4.6.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . 157 Results and Evaluation 159 5.1 Domain Relations and Domain Corpus . 160 5.2 Evaluation of the Vector Space Model . . 162 5.2.1 Evaluation Baselines .... . 163 5.2.2 Configuration Parameters . 164 5.2.3 Average Ranking Precision . . 165 5.2.4 First Guess Correct . . . 173 5.2.5 Second Guess Correct . 177 5.3 Concept Grounding . . 178 5.4 Scarlet ............. . 181 Acknowledgements First of all, I would like to thank my supervisors, Prof. Wolfgang Panny and Prof. Arno Scharl, for providing the organizational support and a very stimulating work environment at the Institute for Information Business of the Vienna University of Economics and Business, in close collaboration with the Department of New Media Technology of MODUL University Vienna. Over the last few years, I had the opportunity to do extensive research work with the members of several project teams. Many ideas that found their way into this thesis and a number of related publications grew out of these activities. In regards to the publications, I also wish to acknowledge the anonymous reviewers' feedback and valuable comments to improve the manuscripts. It has been a pleasure to work with my current and former colleagues at the involved institutes: Heinz Lang, Johannes Liegl, Wei Liu, Roman Kern, Hans Mitlohner, Thomas Neidhart, Walter Rafelsberger, Arno Scharl, Hermann Stern, Kamran Ali Ahmad Syed, Albert Weichselbraun, and Dimitri Zibold. Particular thanks go to Arno Scharl and Albert Weichselbraun for suggesting numerous improvements in terms of content, style and structure of this thesis. Heinz Lang provided the Java source code for creating the Jena inference model, and a wrapper to access the Scarlet APL Financial support was provided by the Austrian Federal Ministry for Transport, Innovation and Technology via the FIT-IT Semantic Systems projects AVALON 1, IDIOM2 and RAVEN3. I am grateful to my friends Cathrine Konopatsch, Robert Koehl and Isabell Handler for proof-reading parts of the thesis. Finally, I would like to thank my family for their long-term support. 1 http://vvw.kmi.tugraz.at/research/projects/avalon 2 http://vvw.idiom.at :1 http: / /vvw. modul. ac. at/nmt/raven Abbreviations AE Al ARM OTO HMM IR IRI LOO LSA KBS NER NLP OWL PMI POS QName ROF ROFS ROQL RIF SPARQL SVO SVM tf-idf URI URlref URL VSM wL-OE WJC WSO Above Expectation Artificial Intelligence Association (Rule) Mining) Document Type Definition Hidden Markov Model Information Retrieval Internationalized Resource Identifier Linking Open Data Latent Semantic Analysis ( =LSI) Knowledge-Based System Named Entity Recognition Natural Language Processing Web Ontology Language Pointwise Mutual Information Part-of-speech XML Qualified Name Resource Description Framework RDF Schema RDF Data Query Language Rule Interchange Format SPARQL Protocol and RDF Query Language Single Value Decomposition Support Vector Machine term frequency -inverse document frequency Uniform Resource Identifier Uniform Resource Identifier Reference Uniform Resource Locator Vector Space Model webLyzard Ontology Extension World Wide Web Consortium Word Sense Disambiguation Abstract Ontologies are formal and shared conceptualizations of domains of interest, and are a crucial ingredient to the Semantic Web and to knowledge-based applications. The manual construction of ontologies is a cumbersome and expensive undertaking, a lot of research effort has been invested developing methods to (semi- )automatically learn ontologies. In contrast to existing approaches to ontology learning, which are typically either applied to natural language text or to structured information sources, this doctoral thesis proposes a novel approach that combines corpus-based methods with knowledge extracted from Semantic Web sources for learning non-taxonomic relations in ontologies. The corpus-based methods use vector space model similarities of verbs co-occurring with unlabeled and labeled relations to calculate relation label suggestions from an arbitrary but specified set of label candidates. The integration of additional semantics gained from reasoning on data from external sources such as DBpedia and OpenCyc links domain concepts to concepts from a meta ontology. This information from semantic inference and validation then helps to refine label suggestions generated by the corpus-based methods on the basis of ontological restrictions defined upon the meta ontology. A formal evaluation presents the accuracy and average ranking precision of the proposed hybrid approach. It demonstrates the superior performance as compared to methods that solely rely on domain text data or those that only build upon reasoning on external structured data sources. Chapter 1 Introduction Ontologies have emerged as an important area of research in the field of computer science [156] over the last decade. The number of international conferences and workshops devoted to the topic reflects this observation. Every knowledge-based system or knowledge-level agent is committed to some implicit or explicit conceptualization - an ontology is an explicit specification of a shared conceptualization [73]. There are a number of reasons for the development and application of ontologies, for example: to create and share common understanding of a specific domain in a group of people, to make domain assumptions explicit and actionable, to separate domain knowledge from operational knowledge, and to enable reuse of domain knowledge [126, 156]. The Semantic Web is an extension of the current World Wide Web, originally proposed by Burners-Lee [15]. It "provides a common framework that allows data to be shared and reused across application, enterprise, and community boundaries" 1. The Semantic Web depends strongly on the timely proliferation of ontologies [108] and requires a global consensus on the appropriate semantic structures ( domain ontologies) for representing any possible domain of knowledge [156]. Fast and easy engineering of ontologies is an important ingredient for the Semantic Web, as well as for many other applications that utilize ontologies. Although a lot of time and effort has been invested into methodologies for ontology engineering [184, 59, 126, 129, 64], the creation of a conceptualization for non-trivial domains remains a difficult and time-consuming task [37, 128]. A major challenge in ontology engineering is to develop domain models with significant domain coverage, but nevertheless meaningful and consistent generalizations. Furthermore, the evolution of domains results in a constant need for refinement of domain ontologies to ensure their usefulness. 1 http://wvw.v3.org/2001/sv 20 CHAPTER 1. INTRODUCTION Ontology engineering requires highly specialized manual effort [50], which is also the primary bottleneck and cost-driver. Automated approaches that learn ontologies from existing data would be the ideal solution to the problem. Many researchers have attempted to learn ontologies from natural language text, as there is an abundant supply of this source of input data. Although the correctness and consistency of automatically generated ontologies cannot be guaranteed, which makes human postprocessing definitely necessary [37], automated approaches improve the productivity of ontology engineers and reduce human input required. Problem Statement The labeling of non-taxonomic relations between concepts is one of the main tasks in ontology learning [108], and it is considered a particularly challenging undertaking [95]. In order to establish the niche for the present work, the thesis provides on overview of the state of the art in this research field. The overview is limited to some selected examples for the sake of brevity, for a more detailed introduction to related literature see Section 4.3. Many approaches in relation detection focus on specific types of relations, such as causal relations [67], the identification of meronyms [14, 66], telic and agentive relations [197], or the learning of qualia structures [41]. The mentioned work mostly relies on lexico-syntactic patterns in the tradition of Hearst [82], other methods apply machine learning techniques, for example Zelenko et al. [202] to extract relations like person-affiliation, or Poesio et al. [132] for the acquisition of feature norms. In contrast to methods that extract specific relations, domain-independent approaches related to the open information extraction paradigm [52] collect relations with unknown identifiers with a focus on scalability, based for example on huge text corpora [10], table structures on the Web [26], or the Deep Web [27]. Methods that acquire arbitrary relations for a typically limited or even predefined set of relation types tackle a very similar problem as do the methods presented in this doctoral thesis. SemEval 2007, an NLP workshop, included a task on the classification of semantic relations between nominals, where many participants combined techniques from machine learning and natural language processing [124, 11, 69, 125]. Rote extractors allow the automatic learning of extraction patterns for arbitrary relations upon training data [21, 7, 148]. Other text-based methods include work on extracting highly significant verbs as relation labels [95] from domain text with probabilistic measures, approaches that leverage parsing techniques [35, 144, 142], or the application of Web statistics and Web corpora in learning non-taxonomic relations [156]. 21 More recently some authors applied Semantic Web datasets and ontologies for relation detection, for example in a method for ontology construction by cutting and pasting ontology modules [4]. Other approaches to discover relations anchor the respective concepts in background ontologies [6] or in ontologies found on the Semantic Web on-the-fly [152]. Those techniques currently suffer from low recall due to a lack of appropriate domain ontologies available. Lehmann et al. [102] find connections between different DBpedia resources in the corresponding graph, but the selection of an explicit label from the paths determined is non-trivial. Goals and Contributions There are comparably few publications on combining corpus-based methods and techniques that integrate knowledge from online ontologies for the detection of non-taxonomic relations. This doctoral thesis aims at closing this gap by introducing a novel approach to detect labels for previously unlabeled non-taxonomic relations. It therefore combines corpus-based methods and knowledge derived from online semantic resources. The corpus-based methods extract verbs co-occurring with labeled as well as unlabeled relations from domain text, and generate labeling suggestions for unlabeled relations upon similarity values yielded by vector space models which include the most significant verbs. Knowledge from structured sources then refines these label suggestions. A typically small meta ontology defines a set of relation types (predicates) regarding their domain, range and property restrictions. Ontology reasoning with data from external sources grounds domain concepts occurring in unlabeled relations in the meta ontology. This allows the refinement of relation label suggestions from corpus-based methods by verifying the conformance to the ontological restrictions. The relation labeling component is an extension addressing shortcomings of an existing ontology learning framework [105] (see Section 4.4), but the approach is generally applicable. The main contributions of this thesis are: (i) the presentation of a novel method which integrates techniques from ontology learning from text with reasoning on Semantic Web data, (ii) a formal description of the processes and algorithms involved, (iii) the creation of a modular and extensible framework that implements the proposed methods, as well as the documentation of major aspects of the implementation, (iv) the introduction of a method to semantically enrich arbitrary terms with mapping and reasoning techniques applied to linked data from DBpedia and online ontologies, (v) the provision of extensive formal experiments to assess the performance of the described methods, which also evaluate the accuracy of a number of variants and configuration settings. 22 CHAPTER 1. INTRODUCTION Remainder of this Thesis Chapter 2 gives an overview of the broader context of the present work. It motivates the Semantic Web, characterizes its features and concludes with a section on Semantic Web applications. Chapter 3 formally introduces ontologies and elaborates the main research areas related to ontologies. Furthermore, it describes representation languages for ontologies: A discussion of W3C's specifications of the languages RDF, RDF Schema and OWL provides the basics necessary to understand the datasets and ontologies used in Semantic Web applications, and also for the approaches presented in Chapter 4. Query languages and ontological reasoning help to leverage the full power of semantic applications, tools such as the Redland libraries or the Jena RDF toolkit yield the mechanisms necessary for handling RDF graphs. Finally, the chapter discusses the data sources and ontologies utilized in the thesis. Chapter 4 gives an introduction into the research field of ontology learning, and then covers techniques and literature related to the novel methods presented in this thesis -those methods and the implementation thereof are a very significant constituent of Chapter 4. The first section describes the main ontology learning tasks along a set of layers, followed by a presentation of fundamental techniques from heterogeneous fields such as natural language processing, statistics or machine learning commonly applied in ontology learning. Furthermore, the chapter supplies an extensive survey of the state of the art with a focus on work in the area of learning non-taxonomic relations. The survey groups existing work by the type of input data, such as domain text corpora, the Web, or Semantic Web data sources, and by the methods applied in the learning process. The later part of the chapter outlines the novel methods developed for this thesis. The description contains the details about the two main elements of the method for labeling nontaxonomic relations, i.e. a set of algorithms that apply vector space models, and components to refine the results by reasoning on knowledge generated from information in external structured sources. The final section of the chapter depicts the architecture which implements the proposed methods. Chapter 5 addresses the crucial issue of evaluating the methods described in Chapter 4. An extensive set of experiments evaluates the performance of the overall method to label non-taxonomic relations, as well as the most important components, especially the corpus-based methods (the vector space models) and concept grounding with the help of online semantic data. Finally, Chapter 6 summarizes the presented work, it emphasizes the main contributions, draws conclusions and comments on open issues and possible lines of future research. 2.2. APPLICATIONS 29 typically uses just a single ontology that supports the integration of a set of data sources fixed at design time. D'Aquin et al. [47] present the features of next generation applications: (i) The application needs to be able to find relevant information on the Web for the task at hand dynamically. (ii) The application has to select appropriate information (in terms of quality, etc.) from the documents found in (i). (iii) As the application must be able to exploit heterogeneous knowledge sources, it cannot make assumptions about the ontological nature of target information. (iv). Ontologies and resources must be combined - as it cannot be expected that one single source provides all necessary information. To be able to leverage the power of online semantics, it is crucial to have a single access point to the data. This access point collects, analyzes, and indexes Semantic Web data and provides it to the applications. As current access points such as Swoogle5 and Sindice6 have limitations, d'Aquin et al. developed Watson [48] as a new Semantic Web gateway to provide mechanisms for extracting semantic documents with keyword search, retrieving their metadata, and querying the content (e.g. with SPARQL). "Watson offers applications all the necessary elements to select and exploit online semantic resources". Among the applications that build on the Watson gateway are Power Magpie, PowerAqua and Scarlet [48]. PowerMagpie helps users to interpret arbitrary Web content by extracting and summarizing important conceptual entities relevant to a page, it highlights those entities and puts them in context with dynamically retrieved ontologies. Power Aqua is a question-answering system based on an unlimited number of ontologies, which is able to combine various ontologies at runtime. Scarlet explores ontologies to automatically retrieve relations between two input concepts -Scarlet will be discussed in more detail in Section 4.3, as it is integrated into the system developed for the present thesis. Corporations still use Semantic Web applications quite rarely, Alani et al. [5] state that "it's probably fair to say that many organizations still view the Semantic Web with some scepticism. In part, they may suspect that they're expected to pioneer an approach in which quick wins are few". Furthermore, they worry about cost and privacy issues when linking everincreasing amounts of data to the Web. Some of the misconceptions have already been addressed in Section 2.1.3, Alani et al.[5] analyze the special characteristics of using Semantic Web technologies in corporations. They argue, that it offers local and private gains indeed for individuals and organizations that link their data and information. Some of the factors to 5 http://swoogle.umbc.edu 6 http://sindice.com 30 CHAPTER 2. THE SEMANTIC WEB make the deployment of Semantic Web technologies attractive are: Minimize disruption to existing infrastructure, e.g. gradually convert existing data to Semantic Web formats with simple scripts. Use small, well-focused ontologies for individual information assets to keep efforts of ontology development low. Show the added value gained by integration and shared access, for example consistency checking, and provide relative ease of integration and efficient data exchange and merging. Already in 2006 van Harmelen [185] observed a shift in company profiles that are active in the Semantic Web field from small start-ups to big corporations. He lists the following areas where respective technologies begin to take shape: knowledge management, mostly for intranets of big corporations; data-integration ( e.g. at Boeing); e-Science, esp. life sciences; convergence of the Semantic Grid. This overview of some of the aspects of Semantic Web applications concludes with a few examples of current Semantic Web applications. Siri7 is a personal assistant for the mobile phone capable of doing simple assistance jobs and answer questions such as "Where is the nearest shop?", or to execute commands like "I need a cab". Siri is born out of SRI's CALO Project, the largest Artificial Intelligence project in U.S. history ( according to the Siri Web site). The ambitious vision is that in the next five years almost everyone with a connected lifestyle will delegate details of day-to-day tasks to intelligent assistants, which coordinate and simplify the details of their lives. True Knowledge8 provides a question-answering system to respond to questions in any domain. It has a search engine-like natural language user interface. The application aims at giving instant and precise answers to questions - as opposed to current Web search engines, which just return a long list of possibly related documents. True Knowledge relies on Semantic Web technologies to answer complex questions by drawing inferences and conclusions on that data. WolframlAlpha9 is another question-answering system. It relies on a formal Mathematica representation at its heart. WolframlAlpha mostly depends on its own data and does not apply Semantic Web technologies or data extensively, and therefore is no Semantic Web application in the narrow sense. Triplt10 automatically organizes all of a user's travel information into a master travel itinerary that is easy to share and access. The master itinerary aggregates a lot of travel-related information in one place. Twine 11 is a service to track, find and share content. Twine uses 7 http://www.siri.com 8 http://www.trueknowledge.com 9 http://www.wolframalpha.com 10 http://www.tripit.com 11 http://www.twine.com 2.2. APPLICATIONS 31 Semantic Web technology to help people organize, disseminate and discover information related to their interests. The application stores information as RDF triples and makes them accessible via the Twine APls. TopQuadrant12 supports companies in moving from disparate data into integrated, actionable and reusable knowledge, using the product TopBraid Suite, which is a set of components for semantic solutions. The SemanticMiner is one of the products created by ontoprise. 13 This application provides semantic search capabilities for companies. Leveraging the power of ontologies, this product supports moderated search, the optimization of search results and also gives an integrated view on heterogeneous sources of data and information. 12 http://11VV.topquadrant.com 13 http://11VV.ontoprise.de Chapter 3 Ontologies This chapter introduces ontologies from a Semantic Web viewpoint. It covers fundamental aspects such as definitions, languages for ontology representation, querying and reasoning, as well as public datasets and ontologies used in the later parts of this thesis. Section 3.1 provides definitions and fundamental characteristics of formal domain conceptualizations referred to as ontologies, which serve as a vocabulary for the Semantic Web. Furthermore, the section discusses some of the main research fields regarding the topic. The following sections then present practical aspects of the Semantic Web, i.e. existing technologies and standards which implement the original ideas and tools for developing Semantic Web applications. Among those technologies are the languages for representing ontologies, e.g. RDF, RDF Schema and OWL, presented in Section 3.2, and standards for Semantic Web graph querying and tools for reasoning, such as Jena or Redland (Section 3.3). Section 3.4 discusses public ontologies and Semantic Web datasets which were applied in the course of this thesis, for example the DBpedia and Freebase datasets, or the OpenCyc ontology. 3.1 Fundamentals This section formally defines the term ontology as well as the entities that constitute an ontology. Furthermore, it discusses the motivations to build such conceptualizations relying on the work of Noy and McGuinness [126], and distinguishes lightweight and heavyweight ontologies. The Semantic Web in general, and the area of ontologies in particular, are research fields that have gained a lot of attention over the last years. Section 3.1.3 provides an outline of the major tasks in ontology research. 34 CHAPTER 3. ONTOLOGIES 3.1.1 Purpose Most work in computer science about ontologies mentions the roots of the term ontology in philosophy, especially Greek philosophy. Ontology is the study or science of being, existence or reality. Cimiano [37] elaborates on the elements of the ancient roots that are particularly relevant for the computer science use of the concept. Platon (427-347 BC) laid the foundation for ontology by explicitly contrasting the world of forms or ideas from the physical, observed, plane. His student Aristotle (384-322 BC) formed the logical background by introducing notions such as category and subsumption, and by creating hierarchies with the concepts of genus and subspecies. With the help of dijferentiae he classifies objects into categories, thereby creating subspecies of one genus. "In fact, Aristotle can be regarded as the founder of taxonomy, i.e. the science of classifying things." [37, p 9]. Ontologies provide the vocabulary that is used in the Semantic Web. Ontologies are models containing concepts and relations that are relevant to a particular task or application domain [23]. Gruber [73] states that every knowledge-based system or knowledge-level agent is committed to some implicit or explicit conceptualization. Such a conceptualization is an abstract and simplified view of some part of the world, and contains its objects, concepts, and other entities and relations that hold between them. An ontology is a formal specification of a shared conceptualization of a domain of interest. "In such an ontology, definitions associate the names of entities in the universe of discourse ( e.g. classes, relations, functions, or other objects) with human-readable text describing what the names mean, and with formal axioms that constrain the interpretation and well-formed use of these terms. Formally, an ontology is the statement of a logical theory" [73, p 909]. Noy and McGuinness [126] summarize the motivations and reasons for the development of ontologies as follows: • Sharing common understanding of the structure of information among people and software agents. If several different Web sites in one domain (e.g. a medical domain) share and publish their data based on the same underlying ontology, then computer agents can collect and aggregate that data more easily -and answer questions upon the data or make it available for other applications. • Enabling reuse of domain knowledge. Various ontologies share specific needs, such as a model to represent address data, which can be shared among the ontologies once it exists. In addition, general ontologies can be customized for personal requirements. 3.1. FUNDAMENTALS 35 • Making domain assumptions explicit. The ontology supports new users joining a domain, serves as a foundation for discussion, and also allows for adaptation when the underlying domain changes. • Separate domain knowledge from operational knowledge. This way a task or process can be described independent of the underlying application, making it easy to adopt the implementation to a new area. • Analyzing domain knowledge. McGuinness et al. [118] state that the formal analysis of terms is extremely valuable when attempting to reuse existing ontologies or extending them. 3. 1.2 Structure and Entities Ontologies usually include a taxonomic backbone, i.e. a hierarchy of concepts connected by is-a relations. Figure 3.1 shows a very small example ontology, the concepts connected which directed links form the hierarchical structure ( the taxonomy). Sub-concepts inherit the properties of parent concepts, as in the example Student inherits all properties of Person. Next to is-a relations any number of non-taxonomic relations are possible between concepts, such as the work-for relation between Professor and University. Another important distinction is between concepts and instances of concepts, instances are individuals associated with a concept. Building on Maedche et al. [108], the present work uses a lightweight definition of entities that define an ontology; for a more formal definition the interested reader is referred to [37] or [179]: • The basic entities are concepts, which are typically hierarchically organized to form a taxonomy. Such an ontology includes a set of concepts C and a concept hierarchy He, where HE C x C, with multiple inheritance between concepts. Ontology learning from text requires lexical entries Le, which provide the link between single words or phrases in text and the ontology's concepts. Function F maps lexicons to concepts. • Besides hierarchical relations between concepts there is a set of nontaxonomic relations R, where REC x C x String [156], which provide the relations that may occur between concepts. Domain and range restrictions describe the main characteristics of a relation. A function G links relations to lexicons LR. • A set of axioms A0 describing additional constraints -expressed in an appropriate logical language, e.g. first order logic [176]. 36 CHAPTER 3. ONTOLOGIES 1 (,,--·~erso;-·) ·- .... --·~ ---·-··- ~·-···········-···-. ( Student , :········• Professor ) ~-- _ ... / i \__---·-····- ! ! isSupelisedBy wo,lsAt i I ~:''"' --<Jii:~-::>J instan eOf Wohlgenannt Figure 3.1: A small example ontology The notion of domain and range restrictions on relations is of particular importance, as this doctoral thesis extensively uses those definitions in later sections. For a binary relation between two terms, also referred to as a "slot", the first term must be an instance of the class that is the domain of the slot and the second must be an instance of the class that is the range of the slot. So for example one could represent the slot mother in a way that the domain is Female Animal and the range is Animal. So domain and range restrict the terms ( or instances of classes regarding ontologies) that constitute a binary relation to a certain class (domain) or certain values (range). For the worksAt relation in Figure 3.1 one might define the domain of the relation to be instances of class Person and the range to instances of Organization. Noy and McGuinness [126] provide a simple step-by-step knowledgeengineering methodology for the construction of ontologies. Lassila and McGuinness [100] show the spectrum from very lightweight and informal ontologies to richly axiomatized heavyweight ontologies on a continuous line, see Figure 3.2. Not all ontologies share the same amount of formal explicitness [45], nor do they include all the components that can be expressed in a formal language, such as concept taxonomies and various types of formal axioms. Therefore, the ontology community usually distinguishes lightweight and heavyweight ontologies [178]. 3.1. FUNDAMENTALS Controlled Vocabularies • • Terms/ glossary Thesauri \ Formal "narrow term" •• relation \. is-a . . \. '·· Informal \ is-a •• \ • Formal instance Frame (properties) • • Value Restrs. General Logical constraints • Figure 3.2: From lightweight to heavyweight ontologies [100] • Disjointness. Inverse, Part-of, ... 37 Corcho [45] gives examples for ontologies used for document annotation within the described spectrum. Many organizations apply the Dublin Core1 element set, a lightweight ontology which belongs to the category terms/- glossary and is used to specify the characteristics of electronic documents. The popular FOAF (Friend-Of-A-Friend)2 vocabulary aims at the creation of a Web of machine-readable pages describing people and the links between them, as well as the things they create and do. FOAF can be regarded as a formal instance. An example of a heavily axiomatized ontology is GALEN3 [185], an ontology in the domain of clinical medicine. D'Aquin et al. [47] found that around 95% of online ontologies included in the Watson Semantic Web gateway are lightweight ontologies -big, dense, and large-scale ontologies are comparatively rare. 3.1.3 Ontology Research Fields This section summarizes the most important ontology research fields in a Semantic Web context. The core research area of the present work, ontology learning, holds strong connections to the other topics, which are ontology population, ontology evolution and ontology alignment. Ontology Learning Knowledge engineers may build ontologies manually using guidelines [126] or use methodologies for ontology construction such as Methontology [59] and the Melting point methodology [64] for decentralized ontology development, However, the present work focuses on (semi-)automatic ontology learning. This (semi-)automatic process leverages information from various sources to generate ontologies, information such as text, data from semi-structured sources [175, 163] or from structured sources [4]. 1 http://vvw.dublincore.org 2 http://vvw.foaf-project.org :ihttp: / /vvw. opengalen. org 38 CHAPTER 3. ONTOLOGIES • Ontology learning from structured data is executed on information sources such as database schemas, existing ontologies and knowledge bases [50]. The central problem here is to determine which pieces of information can provide relevant knowledge. This type of ontology learning is also called lifting because it lifts or maps existing schemas to ontological definitions [187, 37]. • Although methods that learn from structured data are quite successful [50], they are limited in scope because most of the data available is unstructured or semi-structured. Semi-structured data is composed of free text plus additional structural annotations, examples are HTML documents, XML documents, WordNet [56], user tags, etc. • Ontology learning from unstructured data extracts domain models from natural language text. This process builds upon a big variety of methods from a multitude of disciplines, including (computational) linguistics, machine learning, information retrieval, data mining, and others. Later sections of this thesis focus on learning from unstructured data (text) as well as on learning from Semantic Web data and ontologies available online. Section 4.1 provides extensive information on the research area of ontology learning. Ontology Population The aim of ontology population is to learn both instances of concepts as well as relations [37]. Hence the task is to learn the instance-of relation, it is thereby very closely related to many tasks in the area of ontology learning. If the ontology population application keeps a link to the text where the instances were detected and if it contextualizes the assignment with the context specified by the documents or text in question, then the task is referred to as knowledge markup or annotation [37, 45]. There is a strong relation between ontology population, Named Entity Recognition (NER) and information extraction (IE). Applying natural language processing techniques IE deals with filling predefined sets of knowledge structures ("templates"). An example of this is the seminar announcements task, where the goal is to extract the location, speaker, topic, or date of a seminar announcement from a document [37]. NER is traditionally concerned with finding instances of certain concepts (person, organization, location) in text. Current NER approaches go beyond this basic set of classes [37]. A major difference between NER and ontology population is that NER classifies each occurrence of a term in a text separately, while ontology population classifies the term 3.2. REPRESENTATION 45 I col :me co2: personalTitle l ... l "Dr." Table 3.1 presents some well-known prefixes commonly used with RDF. I Prefix N amespace URI rdf: http: //wvw. w3. org/1999/02/22-rdf-syntax-ns# rdfs: http://www.w3.org/2000/01/rdf-schema# owl: http://www.w3.org/2002/07/owl# xsd: http://www.w3.org/2001/XMLSchema# Table 3.1: Commonly applied prefixes and the respective namespace URis RDF uses URirefs to convey meaning, sets of URirefs are called vocabularies. Such vocabularies typically base on URirefs within a common namespace - so terms from the vocabulary are chosen by combining the namespace prefix with a local name. Examples are the vocabularies rdf: and rdfs: given in Figure 3.1, which include the terms defined by RDF itself and the terms from RDF Schema (see Section 3.2.2). The usage of common namespace prefixes for a vocabulary is just a convention. The RDF model does not assume any relation between URirefs from a common namespace and it is common practice to mix URirefs from various namespaces in an RDF file. The use of URirefs for the identification of things has several advantages over the use of literals. Literals like "Eric Miller" are inherently ambiguous, as there exist many persons named "Eric Miller". URlrefs provide a preciser identification of a resource, and the use of URirefs for properties yields the opportunity to give additional information and a clear semantics for that property. URirefs do not solve all problems, e.g. the problem that different URirefs may refer to the same thing is evident. OWL provides terminology to mark classes and individuals as equivalent. On the other hand organizations should try to use wide-spread terminology such as Dublin Core9 where applicable, instead of creating their own. RDF facilitates the representation of structured information, e.g. an address that consists of a number of fields such as street name or postal code, in two ways: The first option is to create an intermediate URiref to represent the aggregated concepts -this creates a universal identifier. If there is no need for such an identifier, then so-called blank nodes are a better choice. Blank nodes are anonymous resources, and they only have local identifiers, which are unique for the respective graph. As RDF allows binary relations (relations between a subject and an object), blank nodes provide a 9 http://www.dublincore.org 46 CHAPTER 3. ONTOLOGIES workaround to break down n-ary relations in binary ones. The subsequent listing, which breaks the n-ary relation between an individual and an address down with the help of the blank node _: j obnaddress exemplifies the use of blank nodes [112]: exstaff:85740 _: johnaddress _: johnaddress _: j ohnaddress exterms: address exterms: street exterms: city exterms: postal Code _: johnaddress . "1501 Grant Avenue" "Bedford" "01730" . As already mentioned, RDF supports the use of literals as values of properties (as objects). Next to plain literals, such as the string "Eric Miller" or "27", RDF provides typed literals. Plain literals involve the problem that the application processing the respective RDF statements has no additional information on how to parse the given data, a string "27" may be handled as the characters "2" and "7", as the decimal number 27, or as the octal number 27, etc. A typed literal is formed by attaching the URiref which identifies the datatype to the literal, for example: exstaff:85740 exterms:age "27""xsd:integer . xsd: integer is the abbreviated form of the full URlref <http://www. w3. org/2001/XMLScbema#integer> and marks the literal as a decimal number. So typed literals provide a way to specify the datatype of a string. The datatypes themselves are defined externally to RDF. It is common practice to use XML Schema datatypes in this context. RDF/XML RDF /XML is an XML syntax used to write down (serialize) and to exchange RDF graph models. The RDF /XML Syntax Specification 10 defines RDF /XML. The following example demonstrates some of the basic aspects ofRDF/XML: <?xml version="l.0"?> <rdf :RDF xmlns: rdf="http://www. w3. org/1999/02/22-rdf-syntax-ns#" xmlns:exterms="http://www.example.org/terms/"> <rdf:Description rdf:about="http://www.example.org/idx.html"> <exterms: creationDate>August 16, 1999 </exterms: creationDate> </rdf: Description> </rdf :RDF.> 10 http://www.w3.org/TR/2004/REC-rdf-syntax-grammar-20040210 3.2. REPRESENTATION 47 The example starts with <?xml version=" 1. 0"?>, this states that the subsequent data is XML formatted and gives information about the version used. RDF documents are required to be well-formed XML, but no validation against a Document Type Definition (DTD) is intended. Every RDF file has to start with an rdf: RDF element, which is closed at the end of the file. RDF files contain namespace declarations, which may be attributes of the rdf: RDF tag. xmlns: rdf="http: //ww. w3. org/1999/02/22-rdf-syntax-ns#" defines all resources that start with rdf: as part of the http:/ /ww. w3. org/ 1999/02/22-rdf-syntax-ns# namespace. The rest of the file contains the actual statements. The example lists only one statement, but RDF permits an arbitrary number of statements per document. The rdf: about attribute at the beginning of the statement denotes the subject element. The next line provides the property element, in this example <exterms: creationDate>. Finally, the value for property, i.e. the object, is included as a literal. So the subject encloses the property element, which itself encloses the object. Distinct rdf :Description elements separate the various statements. RDF includes a number of abbreviation formats to simplify RDF /XML, it is common practice to combine multiple statements that have the same subject: <rdf: Description rdf: about="http://www. example. org/ idx. html"> <exterms: creationDate>August 16, 1999 </exterms: creationDate > <de: language>en</dc: language> <dc:creator rdf:resource="http://www.example.org/staffid/85740"/> </rdf: Description> The previous example integrates three statements about the resource http: I /ww. example. org/ idx. html by enclosing three property elements into a single rdf: Description tag. The last property element shows how to specify resources (URirefs) as objects. The rdf: resource attribute to the property element indicates the use of an URiref property value. QNames are illegal in property attributes, therefore the attribute includes a full URiref in the example statement. There are several possible ways to represent blank nodes. A direct approach is to assign a blank node identifier, which is unknown outside the particular RDF /XML document. The blank node is referred to by the attribute rdf: Node ID instead of rdf: about or rdf: resource. Optional rdf: data type attributes to the property element specify the datatype of literals, as in this example: <rdf: Description rdf: about="http://www. example. org/idx. html"> <exterms: creationDate rdf: datatype= 48 CHAPTER 3. ONTOLOGIES "http://vvv.v3.org/2001/XMLSchema#date">1999-08-16 </exterms: creationDate> </rdf: Description> Both plain and typed literals may include Unicode characters. Instead of including full URirefs in the rdf: about attribute of a subject, rdf: ID can be used together with a fragment identifier. For example a <rdf:Description rdf:ID="item11"> [ .. ] is essentially equivalent to specifying a <rdf: Description rdf: about="http://www. example. org/products#i tem11". The fragment identifier is interpreted relative to the base URI, which by default is the URI of the document itself. Joining the fragment identifier and the document URI with a "#" yields the absolute URiref [112]. It is good practice to specify a base URI in RDF documents, this allows to distribute the document to different locations on the Web, and still have unchanged full URis to the resources defined in the document. Similar to namespace information, the xml: base element is an attribute of the rdf: RDF tag. It defines the base URI, for example xml: base="http://www. example. org/products ". By assigning URirefs to resources the RDF framework provides global identifiers. The descriptions of particular resources need not be included in one single document, it's possible to distribute them throughout the Web. XML entities help to abbreviate even the resource values of attributes. This increases the readability of RDF documents. In the example below a DOCTYPE declaration is added at the beginning of the file -this associates the name xsd with the string following the name inside the ENTITY clause. <!DOCIYPE rdf :RDF [ <!ENTITY xsd "http://vvv.v3.org/2001/XMLSchema#">]> The XML preprocessor will replace the entity reference &xsd; elsewhere in the document with the full URiref. The statement given above now takes this form: <rdf: Description rdf: about="http: //vvv. example. org/idx. html"> <exterms: creationDate rdf: datatype=" &:xsd; date"> 1999-08-16 </exterms: creationDate> </rdf: Description> So far this section presented the mechanisms to describe individuals in RDF /XML. But a very import concept in RDF is to categorize those individuals, to assign them to a type. The rdf : type property provides this functionality. The following example demonstrates the categorization of a resource, this is also called instantiation -the subject resource is declared to be 3.2. REPRESENTA'11ON 49 an instance of the object resource. The statement specifies that the item with the relative URI #i tem11 is of type http: //ww. example. com/terms/Tent. <rdf :RDF xmlns: rdf="http://www. w3. org/1999/02/22-rdf-syntax-ns#" xmlns:exterms="http://www.example.org/terms"> xml:base="http://www.example.org/products"> <rdf: Description rdf: ID=" i tem11 "> <rdf:type rdf:resource="http://www.example.com/terms/Tent"/> [ .. other properties] </rdf: Description> [ .. ] The definition of classes (like Tent) is not possible in RDF itself, but RDF Schema and OWL provide such capabilities. As the description of type information is very common in RDF, the following abbreviation syntax is a substitute to defining the type with rdf: type explicitly. The QName of the resource that refers to the category replaces the rdf :Description element: <exterms: Tent rdf: ID=" i tem11 "> [ .. other properties] </exterms: Tent> Containers provide a means to group things in RDF models, for example to list the students participating in a course. Containers are resources that contain things ( resources or literals). The contained things are called members. RDF provides vocabulary for three predefined types of containers, namely Bag, Sequence and Alternative. Members in bags ( rdf: Bag) are not ordered in any way, and bags may contain duplicates. Sequences (rdf: Seq) may also include duplicates, but, as the name suggest, the order of the members is significant. The Alternative container (rdf :Alt) includes a number of alternatives, typically only one of them is chosen by the application processing the data. Bags might be appropriate for example to record information about products in a shopping cart, the Sequence container might represent an alphabetically sorted list of students, and the Alternative container is often used to store alternative language translations. The rdf :type property describes a resource as a container. The member elements have properties with names rdf: _n, for example rdf: _1 and rdf: _2. RDF /XML includes rdf: li as convenience elements, which result in the generation of the corresponding rdf : _n elements when forming the corresponding graph. A snippet representing an example of an Alternative container follows: <rdf:Description rdf:about="http://example.org/packages/X11"> <s: DistributionSite> <rdf: Alt> 50 CHAPTER 3. ONTOLOGIES <rdf: Ii rdf: resource="ftp://ftp.example.org"/> <rdf: Ii rdf: resource=" ftp: //ftp1. example. org" /> <rdf: Ii rdf: resource=" ftp:/ /ftp2. example. org "/> </rdf: Alt> </s: DistributionSite> </rdf: Description> Statements as in the example do not actually construct a container and its members (like in programming language), they only describe the elements of a container that presumably already exist. Collections are similar to containers in the sense that they facilitate the grouping of resources. In contrast to containers, collections are closed and they include only the specified set of members. Containers, on the other hand, are open in the sense that anyone can provide additional members to an existing container in an RDF document distributed somewhere on the Web. RDF collections are represented by list structures in RDF graphs, they include an rdf: first member, as well as other members. A rdf: nil finally closes the list. The special property attribute rdf :parseType="Collection" indicates that the contents of the element should automatically be interpreted in a way to create the corresponding list structure in the RDF graph. The following RDF fragment exemplifies the usage of collections using the special notation: <rdf:Description rdf:about="http://example.org/courses/6.001"> <s:students rdf:parseType="Collection"> <rdf: Description rdf:about="http://example.org/students/Amy"/> <rdf: Description rdf:about="http://example.org/students/Mohamed"/> <rdf: Description rdf:about="http://example.org/students/Johann"/> </s: students> </rdf: Description> An interesting RDF concept is the so-called reification. Sometimes users want to specify metadata about a statement, for example who created the statement or when it was created. RDF provides a vocabulary to describe statements themselves, this is called reification of a statement. The vocabulary includes rdf: Statement, rdf: subject, rdf: predicate and rdf: object. Conventional use of reification comprises the creation of a "reification quad", i.e. four statements as given in the following example: exproducts: triple12345 exproducts: triple12345 exproducts: triple12345 exproducts: triple12345 rdf: type rdf: subject rdf: predicate rdf: object rdf: Statement . exproducts: item10245 exterms: weight . "2.4""xsd:decimal . 3.2. REPRESENTA'11ON 51 The first statement marks the resource as an rdf :Statement, the second, third and fourth describe its subject, predicate and object. Afterwards additional information about the statement, such as the author, can be added. Reification is one of the more complex subjects in RDF, and as the presented work currently doesn't use it, the interested reader is referred to online resources by the W3C, such as [112], for more details. After having presented some of the most important concepts related to the Resource Description Framework, the upcoming section presents RDF Schema. RDF Schema provides users a simple vocabulary to create their own classes and also relations between those classes. 3.2.2 RDF Schema RDF Schema (RDFS) 11 , the RDF Vocabulary Description Language 1.0, provides the means to create RDF /XML vocabularies for particular domains, i.e. to specify the relevant elements (classes) and how they relate to each other. RDF Schema defines the metadata used to describe RDF data. Therefore, the RDFS terminology itself is domain-independent and the vocabularies generated with RDFS are typically domain-specific. RDFS provides a type system for RDF, the type system is comparable to object oriented programming languages, where classes with certain properties and instances thereof exist. RDF Schema allows class instantiation and the creation of class hierarchies (suband superclasses). In contrast to programming languages RDFS only describes additional information about resources, it does not force types on data. The RDF Schema namespace is typically included as xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#" so documents usually refer to the QName rdfs. The most basic element of RDF Schema is the class, which may be thought as the category or type of a resource. Those classes may represent almost any kind of thing, be it physical or abstract. The description of classes involves the following RDFS resources: rdfs:Class, rdfs:Resource, rdf:type and rdfs:subClass • f. For example, if someone wants to create a vocabulary in the climate change domain, then he or she might define the class GreenhouseGas: J ex: GreenhouseGas rdf: type rdfs: Class . 11 The specification of the RDF vocabulary description language is at http://www.w3. org/TR/rdf-schema, the location presents more details about RDFS to the interested reader; http://www. w3. org/TR/rdf-primer /#rdf schema gives an introduction to RDFS. 52 CHAPTER 3. ONTOLOGIES The rdf: type property specifies instances of classes. Any class in RDF Schema is an instance of rdf s : Class. The statement I ex: Methane rdf: type ex: GreenhouseGas. creates an instance of the class ex: GreenhouseGas. The subClassOf property allows to define a specialization relation between two classes. For example ex: Oi!Company rdfs: subClassOf ex:Company . states that ex: OilCompany is a specialization of ex: Company, which means that any instance of ex: OilCompany is also an instance of ex: Company - this fact is inferred by software that understands RDF Schema. The rdfs: subClassOf property is transitive, therefore, if ex: Oi!Company rdfs: subClassOf ex: Company ex: Russian Oil Company rdfs: subClassOf ex: Oi!Company then ex: RussianOilCompany is also a rdfs: subClassOf ex: Company. /01/rdf-schema#subClassOf http://www.example.org/schemas/vehicles#PassengerVehicle /2000/01/rdf-schema#subClassOf Figure 3.5: "A Vehicle Class Hierarchy", adopted from [112] 3.2. REPRESENTATION 53 Figure 3.5 shows a class hierarchy in the domain of vehicles. The figure omits the relations of each defined class to rdf s: Class for simplicity. The model defines various classes which represent vehicles, and also demonstrates that a class can be a subclass of multiple other classes. All classes in RDFS are implicitly subclasses of rdfs: Resource. An RDF /XML serialization of the model might be as follows: 12 <?xml version="l.0"?> <rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#" xml: base="http: //example. org/schemas/vehicles "> <rd fs : Class rdf: ID=" MotorVehicle "/> <rdfs: Class rdf :ID="PassengerVehicle"> <rd fs : subClassOf rdf: resource="#MotorVehicle "/> </rdfs: Class> <rdfs: Class rdf:ID="Truck"> <rdfs:subClassOf rdf:resource="#MotorVehicle"/> </rdfs: Class> <rdfs: Class rdf: ID="Van "> <rdfs:subClassOf rdf:resource="#MotorVehicle"/> </rdfs: Class> <rdfs: Class rdf:ID="MiniVan"> <rd fs : su bClassOf rdf: resource="#Van "/> <rdfs:subClassOf rdf:resource="#PassengerVehicle"/> </rdfs: Class> </rdf :RDF> rdf: ID describes the vehicle class names, which creates abbreviated URIrefs relative to the base document, and ensures that the names are unique in the document. Next to the description of classes, RDF Schema also provides the facilities to define the specific properties of those classes. rdf : Property constructs, in combination with the additional RDF Schema elements rdfs :domain, rdfs: range and rdfs: subPropertyOf, describe properties. So every property in RDF is of type rdf: Property: Jex: study rdf:type rdf: Property . 12 See http://www.w3.org/TR/rdf-primer/#schemac1asses 54 CHAPTER 3. ONTOLOGIES The rdf s : domain and rdf s : range properties are crucial for the application of semantic validation and inference in the method presented in Chapter 4. rdfs: domain indicates that a given property applies to instances of a particular class. The example I ex: study rdfs: domain ex: Person . states that the property ex: study applies to instances of class ex: Person. A property may have zero, one, or more than one rdf s: domain restrictions. If no rdfs: domain is given, nothing is said about which resources the property is applied to. If there is one rdfs: domain stated, then the property applies to instances of that specific class. If multiple rdfs: domain properties are given, then the resources have to be an instance of all these classes. Similar to the rdfs: domain property, rdfs: range indicates that the values of the property are instances of a particular class. The statement lex:study rdfs:range ex: Topic . declares that the values (objects) of the property ex:study are instances of the class ex: Topic. Like rdfs: domain, a property can have zero, one or more than one rdfs: range descriptions. The remarks given on this subject for rdfs: domain hold analogously for rdfs: range. Next to indicating the class instance that a property has as its value, rdfs: range can also restrict the value to a typed literal. The following statement specifies that the value for the property ex: age is of type xsd: integer: I ex: age rd fs : range xsd: integer . The subsequent listing gives a more extensive example. It illustrates the application of rdfs: domain and rdfs: range together with collections (see Section 3.2.1 ). The snippet describes the domain and range restrictions for the property study as the union of a number of classes defined in another ontology ( denoted with the QN ame cl : ) . All resources involved in a study relation as subject resource are instances of one of the classes cl: Person, cl: Organization, etc., and the values of the relation are instances of cl: AbstractTopic, etc. The next section will introduce the OWL terminology used. <owl: Object Property rdf: ID=" study"> <rdfs: domain> <owl: Class> <owl: union Of rdf: parseType="Collection "> <owl:Class rdf:about="cl:Person"/> <owl:Class rdf:about="cl:0rganization"/> <owl:Class rdf:about="cl:Unknown"/> 3.2. REPRESENTATION 61 The owl: someValuesFrom property yields a similar type of restriction: At least one of the members having the property must connect to a member of the class mentioned as value of some ValuesFrom. Another type of property restrictions are cardinality constraints. owl: cardinality permits to exactly specify the number of elements in a relation. The following example states that every vintage has exactly one vintage year: <owl:Class rdf:ID="Vintage"> <rdfs: subClassOf> <owl: Restriction> <owl:onProperty rdf:resource="#hasVintageYear"/> <owl: cardinality rdf:datatype= "&xsd; nonNegati velnteger ">1</owl: cardinality> </owl: Restriction> </rdfs: subClassOf> </owl: Class> In OWL Lite cardinality expressions are limited to values of O and 1. OWL DL allows all positive integer values. The properties owl: minCardinali ty and owl: maxCardinali ty describe lower and upper bounds, if preciser restrictions are necessary. OWL supports the mapping of ontologies at the level of classes, properties and individuals. Mapping and merging ontologies is an important task, as ontologies should be widely shared and reused in order to have maximal impact, and to avoid the cumbersome task of building ontologies from scratch. The owl: equi valentClass tag indicates that two classes have exactly the same members. <owl:Class rdf:ID="Wine"> <owl: equivalent Class rdf: resource="&vin; Wine"/> </owl: Class> Two individuals are declared as identical with owl: sameAs, the property is commonly applied to state that individuals described in different documents are actually the same. The following example from the DBpedia page about "Fossil fuel" links the resource to a corresponding resource in Freebase.com: <rdf: Description rdf:about="http://dbpedia.org/resource/Fossil_fuel"> <owl: sameAs xmlns: owl="http://www. w3. org/2002/07 / owl#" rdf: resource= "http://rdf.freebase.com/ns/guid.9202a8c0641f80dd"/> </rdf: Description> On the contrary, owl: differentFrom states that values are mutually distinct. 62 CHAPTER 3. ONTOLOGIES <WineSugar rd f: ID=" Dry" /> <WineSugar rdf: ID=" Sweet"> <owl: different From rdf: resource="#Dry" /> </WineSugar> When combined with a cardinality restriction that a wine has only one hasSugar relation, these statements prevent a wine from being described as both dry and sweet. The owl: AllDifferent element, combined with owl: distinctMembers, gives a more convenient way to define distinct members then to state that resources are pairwise distinct [ 173]. <owl: AIIDifferent > <owl: distinctMembers rdf: parseType="Collection "> <vin: WineColor rdf: about="#Red" /> <vin: WineColor rdf: about=" #White" /> <vin: WineColor rdf: about="#Rose" /> </owl: distinctMembers> </owl: AIIDifferent > OWL provides additional constructs for class creation in the form of class expressions. Basic set operations, enumerations, or the explicit statement of contained individuals support the generation of complex classes. Set operations include the OWL constructs intersectionOf, unionOf, complementOf, all of which are applied to owl: Class constructs. An example for intersections defines Burgundy as wines that have at least one locatedln property with the value BourgogneRegion. <owl: Class rdf: about="#Burgundy "> <owl: intersection Of rdf: parseType="Collection"> <owl:Class rdf:about="#Wine" /> <owl: Restriction> <owl: onProperty rdf: resource="#locatedln" /> <owl: has Value rdf: resource="#BourgogneRegion" /> </owl: Restriction> </owl: intersectionOf> </owl: Class> The definition of union constructs is usually a little simpler, as shown in this self-explanatory example: <owl:Class rdf:ID="Fruit"> <owl: union Of rdf: parseType="Collection "> <owl:Class rdf:about="#SweetFruit" /> <owl:Class rdf:about="#NonSweetFruit" /> </owl: union Of> 3.3. QUERYING AND REASONING 63 I </owl: Class> A fragment from the classification ontology (see Chapter 4), gives an example for defining the domain restrictions for the property study using the owl: unionOf element. <owl: Object Property rdf: ID=" study"> <rdfs: domain> <owl: Class> <owl: union Of rdf: parseType="Collection "> <owl:Class rdf:about="#Person"/> <owl:Class rdf:about="#0rganization"/> <owl:Class rdf:about="#Unknown"/> </owl: unionOf> </owl: Class> </rdfs :domain> </owl: Object Property> Finally, as the last of the mentioned set operations, the construct owl: complement•f selects all individuals from the domain that are not members of a specified class. OWL also provides the means to explicitly list the members of a class with the owl: one•f construct. owl: one•f completely specifies the class members, no other members may be added to the class afterwards. The following example (from the OWL Guide [173]) defines the class WineColor as enumeration of the individuals White, Rose and Red. <owl: Class rdf: ID="WineColor"> <rdfs:subClassOf rdf:resource="#WineDescriptor"/> <owl: oneOf rdf: parseType="Collection"> <owl: Thing rdf: about="#White"/> <owl: Thing rdf: about=" #Rose"/> <owl: Thing rdf: about="#Red "/> </owl: oneOf> </owl: Class> The owl: dist inctWi th construct defines that a member of a given class cannot also be a member of another classes listed as values of the distinct With property. 3.3 Querying and Reasoning The mechanisms introduced in the previous sections about representation languages for ontologies are not sufficient to leverage the full potential of the Semantic Web. Besides defining vocabularies and statements, it is necessary to have techniques and tools to query the datasets, as well as to have support 64 CHAPTER 3. ONTOLOGIES for reasoning on semantic data. Section 3.3.1 discusses the SPARQL and RDQL query languages for Semantic Web data, the Sections 3.3.2 and 3.3.3 briefly introduce the Jena toolkit and the Redland RDF libraries. Those frameworks support a broad range of features, among which are parsing RDF data, building graph models or querying and reasoning. 3.3.1 SPARQL and RDQL RDF graphs are kept in RDF stores, also called triple stores. A triple store is in some respect similar to relational databases or XML stores. As in database management systems, query languages are the typical means to access triple stores. This section gives an overview over SPARQL, which is the W3C standard for RDF query languages, and also touches RDQL, a predecessor ofSPARQL. SPARQL In 2008 the W3C made its standardized query language SPARQL a W3C Recommendation. SPARQL's name is a recursive acronym which stands for SPARQL Protocol and RDF Query Language. SPARQL is a successor of query languages such as RDF Query Language and RDQL. SPARQL queries are centered around patterns which are matched against an RDF graph. Those graph patterns are constructed from the most basic element, the triple pattern. A triple pattern looks similar to an RDF triple already presented in Section 3.2.1, but variables replace some of the elements (subject, predicate, object) in the triple. The? (or$) symbols are prepended to the variables. A few examples of such triple patterns follow: ?a rdf: type dbpedia: Organization. <http:// dbpedia. org /resource/ ALGore> owl: sameAs ? c. The patterns are to be read as: Which resource in the graph is of type dbpedia: Organization? What objects are marked being the same as the DBpedia resource for Al Gore? The syntax of triple patterns is very simple: subject, predicate, object and finally a dot. A query engine returns the entities that match the given query pattern, either in a table format, or as a resulting RDF graph. A set of triple patterns makes up a graph pattern, SPARQL uses braces to enclose this list of triple patterns. It is important to note that a variable that appears in two or more triple patterns has to match the same resource in the graph. Examples for graph patterns are: { ?a rdf: type dbpedia: Organization. ?a dbprop:formed ?c. } 3.3. QUERYING AND REASONING 65 { ?a rdf:type ex:Person. ?a ex:born ?c. ?c geo: isln geo: Austria. The first graph pattern extracts all dbpedia: Organization organizations and the date when they were formed. The second query selects resource names and locations for resources of type ex: Person which were born in a location inside geo: Austria. In graph patterns all of the triple patterns must match, and every occurrence of a variable must match the same resource [8]. The UNION operator allows the combination of triples in graph patterns, as shown below: { { ?a rdf:type UNION { ?a rdf: type dbpedia: Organization. d bpedia: Person. } SPARQL supports different output formats, such as simply to list the appropriate bindings for variables, or also to return the complete subgraph of statements matching the query. The SELECT form returns the binding list, it generates a table of values corresponding to the variables. This is presented in an example query, which extracts the name and email-address (specified with FOAF vocabulary) of resources from an RDF model: PREFIX foaf: <http://xmlns.com/foaf/O.l/> SELECT ?name ?mbox WHffiE { ?x foaf:name ?name ?x foaf:mbox ?mbox} The PREFIX keyword in the first line associates a label (loaf) with an IRI (<http://xmlns.com/foaf /0. 1/>), the colon concatenates the prefix name and the local name. The prefix name or the local part may stay empty. The prefixes are similar to the QNames presented in Section 3.2.1. The SELECT clause lists variables to appear in the query results. In the given example the variables name and mbox must appear in the results, but not the variable x. The WHERE clause includes the graph pattern matched against the data. The result of the query is a solution sequence, with zero, one, or multiple solutions to the graph pattern. Table 3.2 gives the resulting sequence for the previous query: In addition to resources, RDF graphs also include literals -SPARQL supports plain and typed literals in queries. The first query in the example below looks for triples with the literal "cat" as object, whereas the second 66 CHAPTER 3. ONTOLOGIES I name I mbox Johnny Lee Outlaw Peter Goodguy <mailto:[email protected]> <mailto:[email protected]> Table 3.2: Query result for a SELECT query f 135] query shows the use of arbitrary datatypes: SELECT ?v WHERE { ?v ?p II cat 11 } SELECT ?v WHERE { ?v ?p 11 abc 11 "<http://example.org/ datatype#specialDatatype > } As an alternative to the SELECT clause, SPARQL supports the CONSTRUCT mode. The application of CONSTRUCT produces a new graph matching the input pattern. Prud'hommeaux and Seaborne [135] give an example for the CONSTRUCT query form. CONSTRUCT returns a number of RDF triples, which can be serialized to RDF /XML. PREFIX fo a f : PREFIX org: <http://xmlns.com/ foaf /0.1/ > <http:/ /example.com/ns#> OONSffiUCT { ?x foaf: name ?name } WHERE { ?x org: employeeName ?name } Another import capability of SPARQL are term constraints, i.e. FILTER constructs which restrict solutions to elements where the filter expression evaluates to True. Filters are included into the graph patterns and filter functions like regex operate on RDF literals: SELECT ?title WHERE { ?x de: ti tie ? ti tie . FILTER regex(?title, 11 -SPARQL") The FILTER construct also applies to arithmetic expressions: SELECT ?title ?price WHERE { ?x ns: price ? price . FILTER (?price< 30.5) ?x de: title ?title . } For more information about other term constraints the interested reader is referred to the W3C Recommendation on SPARQL [135]. The document includes many other SPARQL features not mentioned in this brief introduction such as: the handling of RDF constructs (blank nodes and RDF collections, etc.), more details on graph patterns and filtering, optional pattern matching, modifications to solution sequences, the ASK and DESCRIBE query forms. 3.3. QUERYING AND REASONING RDQL 67 This section introduces the reader to some facts about RDF Data Query Language (RDQL), because the present work relies on RDQL for some querying tasks in connection with the Redland framework (information about Redland follows in Section 3.3.3). RDQL, like SPARQL, allows the extraction of information from RDF graphs. The basic constructs used to achieve this goal are graph patterns. The syntax differs in some points from SPARQL, and the SPARQL language is more expressive than RDQL. Some of the features missing in RDQL are: the sorting of results, the ability to add optional information to query results, expressive testing (RDQL only has crude support for datatypes) and named graphs. In order to give an impression of RDQL and its syntax, the current section present a few example queries. The present work used RDQL together with the RDF Query Library, which Redland builds upon for its RDF querying facilities. SELECI' ?a ?b WHffiE (?a ?b dbpedia: Person) USING dbpedia FOR <http://dbpedia.org/ on to logy/> The query presented above selects all subjects and predicates from an RDF model which have dbpedia:Person as their object. RDQL is quite similar to SPARQL in the way it uses graph patterns and variables. A major difference concerns the specification of namespace prefix declarations. In contrast to SPARQL, RDQL declares such prefixes with the USING keyword as part of the query: SELECI' ?resource WHffiE (?resource info:age ?age) AND ? age >= 24 USING info FOR <http://example.org/ people Info#,> The example also demonstrates another difference to SPARQL. Instead of the FILTER construct, RDQL applies an AND clause. 3.3.2 Reasoning with Jena Jena17 is a Java-based framework for building Semantic Web applications. It provides programmatic support for W3C's Semantic Web recommendations RDF, RDFS, OWL and SPARQL, as well as for its own query language RDQL, and also includes rule-based inferencing. Jena is free software (open source), and originates from work at HP Labs' Semantic Web Programme.18 17 http://jena.sourceforge.net 18 http://wv.hpl.hp.com/semweb 68 CHAPTER 3. ONTOLOGIES At the heart of the Jena RDF toolkit is the RDF graph. Jena perceives reasoning support for RDFS and OWL as graph-to-graph transformations, which produces graphs of virtual triples [29]. Jena includes rich APis for building models and for handling RDFS and OWL ontologies. The first release of Jena [116] was in 2000, the Jena2 series started in 2003. Besides its model API for the manipulation of RDF graphs, Jena provides an RDF- /XML parser, as well as 1/0 modules for N3, N-triples and RDF /XML. The framework yields modules to store graphs in memory, or persistently in native persistence engines or in relational databases. The present work uses Jena to create inferred models from input OWL ontologies such as the DBpedia ontology or the OpenCyc ontology. Those models are saved persistently to a PostgreSQL database. The inferred models include the original statements from the input ontology and the statements inferred. The Jena2 inference subsystem allows to plug various inference engines or reasoners into Jena. The inference mechanism permits the application of languages such as RDFS and OWL to create additional facts from instance data and class descriptions. The mechanism is quite general though, it is based on a generic rule engine which can be applied to many RDF processing and transformation tasks. 3.3.3 Redland Redland 19 is a set of free libraries written in C. Redland allows for storage, querying and manipulation of RDF models [12]. It is designed to be flexible and modular. Furthermore, it aims at portability and computational performance. Similar to Jena, Redland provides mechanisms to store RDF models in memory, or persistently in databases, triple stores, as well as in files. The major building blocks of Redland are four libraries: • libraptor. The Raptor RDF Parser Library parses and serializes RDF content. The library supports many different parsing syntaxes, for example RDF /XML, N-Triples, RSS, Atom, various microformats and GRDDL. Serialization formats include RDF /XML, Atom 1.0, GraphViz, JSON, N-Triples, RSS 1.0 and XMP. • librasqal. The Rasqal RDF Query Library facilitates the execution of queries against RDF models. The library includes an API to construct and access queries, as well as to bind results. Furthermore, librasqal contains a query engine with constraint expression evaluation and a standalone query utility program. Rasqal supports the RDQL and 19 http://librdf.org 3.4. PUBLIC DATASETS AND ONTOLOGIES 69 SPARQL query languages, and also LAQRS, which is an experimental set of syntax extensions for SPARQL. • librdf The Redland RDF Library, which requires Raptor and Rasqal, provides the high-level language APis for RDF manipulation and storage. • Redland Language Bindings. The Redland language bindings contain APis to the Redland libraries in languages such as Perl, PHP, Python and Ruby. The framework built for the present thesis makes use of Redland for processing DBpedia and Freebase resources, i.e. to build RDF models and execute queries in the RDQL and SPARQL languages. Besides its rich set of features, Redland was chosen for its simplicity of use in combination with the Python programming language. 3.4 Public Datasets and Ontologies This section introduces the external datasets which were used in the course of the present work, and also two ontologies linked to the datasets: the OpenCyc and the DBpedia ontology. We focused on the DBpedia dataset, information from the Freebase dataset complements the DBpedia statements. These two sources provide structured information on a wealth of cross-domain topics. DBpedia yields structured data extracted from Wikipedia and covers over two million "things". DBpedia is heavily interlinked with other datasets from the Linking Open Data project, most relevant for the present work are outgoing links to Freebase and to concepts from the OpenCyc ontology. The presented method maps concept labels to entries in DBpedia and then tries to infer a concept type according to a given set of types with the help of a number of heuristics and ontology reasoning. 3.4.1 DBpedia Over the last years, Wikipedia evolved into one of the central knowledge sources of mankind, and in contrast to traditional encyclopedias, it is a community-based project maintained and constantly enhanced by thousands of voluntary contributors around the globe. DBpedia leverages this comprehensive source of knowledge, it extracts structured information from Wikipedia and then provides the information on the Web [18]. Bizer et al. [18] demonstrate the size of DBpedia: "The resulting DBpedia knowledge base 70 CHAPTER 3. ONTOLOGIES currently describes more than 2.6 million entities, including 198,000 persons, 328,000 places, 101,000 musical works, 34,000 films, and 20,000 companies. The knowledge base contains 3.1 million links to external Web pages; and 4.9 million RDF links into other Web data sources." The characteristics of information in Wikipedia and therefore in DBpedia are, next to the sheer size, that it covers many domains and builds on real community agreement on the topics discussed. Other advantages are true multilingualism and the automatic evolution of DBpedia along with changes in Wikipedia. Bizer et al. [18] list three major contributions of DBpedia: its extraction framework that builds the knowledge base, the provision of Web-dereferenceable identifiers for entities, and the linkage between DBpedia and other data sources. The current section will cover those contributions in more detail in the following. Extraction Framework The information extraction framework aims at building a rich multi-domain knowledge base from Wikipedia content. Besides free text, Wikipedia includes structured information in the form of infoboxes, as well as categorization information, images, links to external resources, redirects, disambiguation pages, etc. DBpedia builds on this structured information to generate its knowledge base. A number of extractor components, geared towards specific Wikipedia structures accomplish the actual extraction task. This process results in triple data about the corresponding resource. Bizer et al. [18] present the details of the extraction architecture. The following RDF /XML snippet from the DBpedia page on "Al Gore" gives an impression of a typical DBpedia resource: <rdf :RDF xmlns: rdf=" http://www. w3. org/ 1999/02/22-rdf-syntax-ns#" xmlns: rdfs="http://www. w3. org/2000/01/rdf-schema#"> <rdf: Description rdf:about="http://dbpedia.org/resource/Al_Gore"> <rdfs:label xml: lang="en">Al Gore</rdfs: label> </rdf: Description> <rdf: Description rdf:about="http://dbpedia.org/resource/Al_Gore"> <rdfs:comment xml:lang="en">Albert Arnold Gore, Jr. (born March 31, 1948) is an American environmental activist , author, businessperson, former politician, and former journalist. He served as the forty-fifth Vice President of the United States from 1993 to 2001 under President Bill Clinton. </rdfs :comment> </rdf: Description> Chapter 4 Methodology This chapter focuses on the presentation of a novel approach for the labeling of unnamed relations between concepts in ontologies. Sections 4.1 to 4.4 introduce state-of-the-art methods for learning semantic relations, a review of related literature, and the webLyzard ontology extension architecture - and thereby provide the foundation for the novel methods formally discussed in Section 4.5 and described regarding their implementation in Section 4.6. The presented methods combine an approach to label non-taxonomic relations based on corpus statistics with knowledge about the relations' concepts inferred from Semantic Web data. The input to the method are a list of unnamed relations, a set of predefined relation types to choose from as well as associated ontological definitions, and a domain corpus. At first the algorithm extracts verbs co-occurring with the input concept pairs from domain text. Vector space similarity of the verb vector of the unnamed relation with relations from a knowledge base then yields relation label suggestions. Concept type information inferred via external structured data sources combined with internal ontological restrictions helps to remove invalid relation label suggestions or to decrease their similarity scores. The method itself is independent from any particular ontology learning system, but, as already mentioned, it has been developed as part of the webLyzard ontology extension architecture. The chapter is organized as follows: Section 4.1 introduces and motivates the research of ontology learning and elaborates on typical ontology learning tasks. Section 4.2 gives an overview of fundamental techniques commonly applied in ontology learning and especially for the learning of semantic relations, including methods from computational linguistics, machine learning and statistics. It focuses on techniques used in the approach put forward in this thesis, and helps to comprehend the literature review, which follows in Section 4.3. The webLyzard ontology extension architecture (Section 4.4) 78 CHAPTER 4. METHODOLOGY applies some of the methods for ontology learning discussed throughout the chapter and also introduces others, it represents the foundation for the novel method introduced in this doctoral thesis. Section 4.5 gives a very detailed description of the proposed algorithms for detecting non-taxonomic relations, their interactions, and of the integration of the various components of the system. Finally, Section 4.6 provides an overview of the design and technical features of the Python-based and database-driven software components that implement the presented approach. 4.1 Ontology Learning As already emphasized in the previous chapter, ontologies play a key part in the Semantic Web as they provide its backbone. However, constructing ontologies manually is a cumbersome and expensive process [128], which relies on highly specialized human effort ( e.g. from domain specialists and knowledge engineering experts) [50]. For the success of the Semantic Web and knowledge based systems, fast and cheap ontology development is crucial - an approach for tackling this problem is to learn ontologies semi-automatically or automatically. The respective field of research is called ontology learning, which is concerned with knowledge discovery from different data sources and with its representation in an ontological structure [50]. Cimiano [37] describes ontology learning as the acquisition of a domain model from data. Section 3.1.3 already mentioned the three possible kinds of input data used in ontology learning [13]: structured data, semi-structured data and unstructured data. Ontology learning systems extract the concepts for a domain and the relations holding between them, and eventually axioms. It is crucial that the input data is representative for the domain to be modeled [37]. Ontology learning can be seen as a reverse engineering task, which reconstructs the world model expressed implicitly by the authors of domain texts. A major problem pointed out by Brewster et al. [19] is that most domain-specific text assumes basic domain knowledge, and only the part of the domain which is the issue of the text is mentioned more or less explicitly. Salience, as addressed by Sowa [17 4], is another issue in ontology learning from text -the problem that people often prefer more salient terms in comparison to more precise, but less salient, terms. As an example, dogs are usually referred to as "animals", a term which has a high salience, and not as "mammals" , which would be more precise. This systematically damages the extraction of relevant terms with statistical methods. Salience is also a problem in ontology alignment, as more salient terms are sometimes wrongly preferred as concept descriptors. 4.1. ONTOLOGY LEARNING 79 Although the ontology engineering process used to be more an art or a craft [32] than a science, much effort has been put in the creation of methodologies to turn it into the latter. Cimiano et al. [39] summarize the typical ontology engineering phases: feasibility study, requirements analysis, conceptualization, and deployment. These phases form a loop of application, evaluation and maintenance of the ontology. Ontology learning can support several critical parts of these phases, for example to build an initial conceptualization of the domain, which then serves as base for discussion, or to extend and refine an existing ontology model in the maintenance phase. It is necessary to identify the steps involved in OL in order to establish the ontology learning tasks -Buitelaar et al. [23] organize the aspects of ontology learning into a set of layers, as presented in Figure 4.1. The identification of domain concepts is possible only after the extraction of their natural language representations (symbols) -this is especially important for ontology learning from text [50]. Those lexical entries Le (as presented in Section 3.1.2) provide links between single words or phrases in text and the ontology's concepts. Synonym extraction helps to detect and merge redundant or very similar terms that refer to the same concept. After building a concept taxonomy He, which serves as backbone for the ontology, the next step focuses on the learning of non-taxonomy relations R, which represents the major contribution of this doctoral thesis. Finally, rules (axioms) may be defined and acquired [23] in order to derive facts that are not explicitly encoded by the ontology. Axioms Relationships Concept Hierarchies Concepts Synonyms Terms Figure 4.1: Ontology Learning Layers (adopted from [23]) 80 CHAPTER 4. METHODOLOGY The following summary describes the steps involved in ontology learning, as shown in Figure 4.1, in more detail: • Terms: The goal in term extraction is to find linguistic realizations of domain-specific concepts -it lays the foundation for further steps. The lexical entries are a set of relevant symbols for concepts and relations, which are characteristic for the underlying domain texts. Terms can be single-word or multi-word compounds, and they have a very specific, often technical, meaning in the domain in question. The input to the task is domain text (in the case of learning from unstructured data), and the output is a set of terms that denote concepts and relations. • Synonyms: Synonym detection aims at finding words that represent the same concept. It is well known that real synonyms rarely existing, most synonyms refer to slight variants in meaning. But in ontology learning, synonyms usually correspond to synsets as used in WordNet [56], i.e. terms that share a common meaning which can be used to form concepts relevant to a domain. There is a strong relatedness and overlap between synonymy and cohyponymy -cohyponymy is the relation between hyponyms that share a common hypernym. • Concepts: Ideally concept formation should provide an intentional definition of concepts, together with their extension and the lexical symbols which are used to refer to the concepts [24]. The intention of a concept can be described in natural language to give the intuitive meaning, such as the glosses in WordNet, or with a collection of concept attributes. • Concept Hierarchies: This task is concerned with inducing, refining and extending the ontology's backbone. Hierarchy induction generates a concept hierarchy from scratch, concept hierarchy refinement links new subconcepts into an existing hierarchy, and lexical extension learns new lexical realizations for a given concept. For a more formal description see Cimiano [37]. • Relations: Ontology learning typically focuses on binary relations, i.e. relations between exactly two concepts. The approaches presented in the literature commonly distinguish the following subtasks for learning non-taxonomic relations: (i) find concepts that are in some relation, without further labeling the relation; (ii) find appropriate labels (relation identifiers) for the relations learned in step (i), for example on the basis of a given corpus; (iii) learn domain and range restrictions for the given relations, as well as the right level of abstraction within 4.2. METHODS FOR LEARNING SEMANTIC ASSOCIATIONS 81 the concept hierarchy for those restrictions; (iv) identify a hierarchical order between the given relations • Axiom Schemata Instantiations: Axiom schemata provide axioms for concepts such as disjointness or equivalence, and for example the transitivity axiom for a relation. The goal in ontology learning is not to learn the axiom schemata itself, but to learn the instantiations of those given axioms, e.g. to determine for which concept pairs the disjointness axiom holds. • General Axioms: In this case axioms themselves are learned, but not axiom-instantiations from schemata as described above, but specific axioms that hold just between specified concepts and relations. For example one could define that for all concepts of type country there must exist a capital of that country. 4.2 Fundamental Methods for Learning Semantic Associations This section introduces fundamental methods and techniques from various fields such as computational linguistics, machine learning and statistics. The presented methods are in no way meant to be exhaustive for those areas, as that would go far beyond the scope of this thesis. The goal is rather to provide a foundation helping to understand the material described in the upcoming Section 4.3 Literature Review and the section about the methods applied in the present work, Section 4.5. While this section summarizes traditional and state-of-the-art techniques and methodologies, Section 4.3 deals with the application of those methods to ontology learning, especially for the task of extraction and learning of non-taxonomic relations. 4.2.1 Natural Language Processing Techniques Preprocessing Natural language is the primary medium by which humans communicate with each other, it allows to ask questions, express beliefs, desires and attitudes, as well as to report events, actions and states [37]. The various syntactic categories (nouns, verbs, adverbs, etc.) are used in natural language to refer to different ontological entities. The following enumeration lists the most important syntactic categories, including their typical application and some examples: 82 CHAPTER 4. METHODOLOGY • Proper Nouns, also called Proper Names represent unique entities, i.e. denote particular persons, places, or things, etc. Examples: Andrei Tarkovsky, Quahog, NASA. • Nouns, also called Common Nouns refer to classes of entities. Examples: henchman, city, fruit. • Adjectives: typically modify nouns, set attribute values for nouns. Examples: sweet in "sweet fruit", or big in "big nose". • Verbs: generally express occurrences, attitudes, events, actions, states, etc. Examples: love, tell, travel, use. • Adverbs: modify other parts of language, except nouns. Examples: "The butterfly looks well", "He often does sports". • Prepositional Phrases: set spatio-temporal conditions. Examples: "Return to the cocoon", or "Terrance and Phillip look for treasure". It has to be noted that this classification is a very rough one -natural language is rich in the ways things can be expressed, and there are many exceptions to most prototypical rules, for example nouns are often used to express events (e.g. "the climate summit at Copenhagen"). Jurafsky and Martin [94] give more detailed information on English part-of-speech. Verbs often relate nouns with each other, a characteristic that is exploited in the present thesis. Verbs also indicate which members of classes can perform an action or participate in an event. This is exemplified in "The man drinks a glass of water", which indicates that to drink can be performed by members of the class man. Such limitations correspond to selectional restrictions [143]in computational linguistics, which can be seen as the conditions specifying where types of classes are applicable, regarding verbs or adjectives. It is necessary to preprocess natural language text in order to exploit its characteristics e.g. for ontology learning when applying a more advanced analysis. Preprocessing typically includes the following steps [37] -the Natural Language Processing (NLP) application does not have to apply them in this exact order: • Segmentation / Tokenization • Part-of-Speech tagging • Lemmatization / Stemming • Named Entity Recognition 4.2. METHODS FOR LEARNING SEMANTIC ASSOCIATIONS 83 Segmentation and tokenization aim at detecting sentence and word boundaries. Sentence splitting or sentence tokenization can be done with complex regular expressions, or with binary classifiers based on machine learning techniques. A typical problem in sentence splitting is to distinguish punctuation signs such as periods in their use as abbreviations and as end-of-sentence markers. The NLP application then splits sentences into single words ( word tokenization), mostly relying on spaces in sentences and some additional rules. Other languages such as Chinese or Thai do not use spaces as potential word boundaries, therefore other algorithms need to be applied [94]. A normalization step can be integrated into segmentation, for example to transform occurrences of dates into a standard format. Most applications that provide tokenization include a stopword removal component to filter non-discriminating words such as "the", "many", etc. from the list of terms based on a stopword dictionary. Part-of-speech (POS) tagging assigns the respective part-of-speech to each token. The part-of-speech denotes the syntactic word category, such as noun, verb, adjective -usually in a more fine-grained differentiation. Depending on the tagset used, computational linguistics typically distinguishes more then 40 separate parts-of-speech for the English language. A simple word dictionary is not sufficient to do POS tagging, because many words represent different POS depending on their usage and context. Frequently applied tagsets include the Penn Treebank tagset1 [113], which contains 45 tags, and the 87-tag tagset used for the Brown corpus [61, 62]. The Brown corpus is a million-word collection of samples from various genres, assembled at Brown University in 1963-1964. The corpus was automatically tagged and then manually corrected. Two commonly used POS taggers are Brill tagger [20] and TreeTagger [161]. Brill tagger is a transformation-based tagger, which assigns a tag to each word and then changes it using a set of predefined rules. This tagger applies lexical rules to initially assign tags, and contextual rules to refine the tags afterwards. TreeTagger is based on decision trees, which estimate transition probabilities with the help of a transition tree. Stemming completely removes the endings (inflections) of words, leaving over the stem or root. For example generat is the stem of generate, generating etc. A well-known stemmer is the Porter stemmer [134], which uses a simple and efficient algorithm based on a series of cascaded rewrite rules. This thesis applies a lemmatization approach, where different inflected forms are grouped together to their lemma with the help of a lexicon. So for example 1 http://wvv.comp.leeds.ac.uk/amalgam/tagsets/upenn.html 84 CHAPTER 4. METHODOLOGY better and good are replaced with good, generating and generated are reduced to generate. Named Entity Recognition is a subtask of information extraction that aims at recognizing unique objects, such as Dr. Thaddeus Venture or Matterhorn. Traditionally named entity recognition is restricted to detect certain entity classes, which typically include persons, organizations, locations, dates. State-of-the-art systems have a near-human performance, see as example Radu et al. [60], who combine four diverse classifiers (robust linear classifier, maximum entropy, transformation-based learning, and hidden Markov model). Another preprocessing step often executed in NLP is chunking, also referred to as shallow or partial parsing [37]. Chunking relies on techniques such as regular expressions and finite state automata to group together words to large syntactic and meaning-bearing units. The main element of that unit is the head, in noun phrases in English language text the rightmost noun is generally the head, in verb phrases the verb is the main meaning-bearing unit. Those syntactic units (chunks) are non-overlapping, non-recursive, and non-exhaustive. Non-exhaustive means that some words in a sentence may not belong to a chunk. Chunkers (in contrast to syntactic parsers, see below) do not detect grammatical relations (such as subject, object etc.) nor syntactic or semantic ambiguities. Chunkers are used when no complete parse trees are needed for all inputs [94]. These basic preprocessing steps are frequently applied as prerequisite for other methods. For example Ruiz-Casado et al. [148] apply segmentation (tokenizer and sentence splitter), POS tagging, stemming, NER, and a chunker (partial syntactic analyzer) to support the extraction of relations in the process of semantic annotation of Wikipedia. Syntactic Analysis More complex and challenging than simple chunking is syntactic analysis (parsing), which aims at discovering the full syntactic structure of a given input sentence [37]. Parsing detects larger units of words and makes dependency relations explicit. It determines the grammatical structure of a sentence with respect to a given formal grammar. The result of this step is a parse tree, where the whole sentence (root of the tree) is split into smaller syntactic units recursively. There are two main strategies in syntactic parsing: bottom-up ( data-directed search) and top-down (goal-directed search). An example of a syntactic parser is LoPar [162], a parser for probabilistic context-free grammars as well as head-lexicalized probabilistic context-free grammars. 4.2. METHODS FOR LEARNING SEMANTIC ASSOCIATIONS 85 Contextual Features The extraction and representing of the context of a certain word, or of word pairs in the case of rote extractors (see Section 4.2.2), is important in many NLP applications. Context is crucial in Word Sense Disambiguation (WSD) for example, which is concerned with detecting the correct meaning of a word in a given context. The problem is often exemplified by the term bank, which refers to a financial institute or a seating-accommodation, depending on the context. One common way to represent context are word window models, that consider n words to left and right of the target word as contextual features. Cimiano [37] proposes two other approaches for extracting contextual features, which both rely on linguistic processing techniques to identify constructs such as subjects and objects of verbs, adjectives or prepositional phrases. Syntactic dependency processing parses a text and extracts the constructs mentioned above from the parse tree. The sentence "The cat eats an apple strudel" would result in eat_subject(cat), eat_object(apple strudel). Pseudo-syntactic dependencies apply shallow parsing combined with regular expressions to avoid the need for real syntactic parsing. 4.2.2 Lexico-syntactic Patterns Generalizing textual patterns to identify relations has been proposed since the early 1990's, when Marti Hearst presented her seminal work on "Automatic Acquisition of Hyponyms from Large Text Corpora" [82]. The work was inspired by the pattern-based interpretation techniques used in the processing of Machine Readable Dictionaries, which were developed in the 1980's. The approach aims at extracting semantic relations from text with little understanding of the content itself by applying simple lexico-syntactic patterns. An example of such a pattern and the implied relation is: NP 1 {,NPn}* {,}orotherNPo. for all NP;, 1 :<:::: i :<:::: n, hyponym(lemma(NP;),lemma(NP 0 )) (4.1) NP stands for a noun phrase, curly braces denote optional elements in the pattern, and the * indicates that O - n occurrences of an element are allowed. Matched on the sentence fragment "Bruises, wounds, broken bones or other injuries ... ", the pattern extracts the following hyponym relations: hyponym(bruise, injury), hyponym(wound, injury), hyponym(broken bone, injury). The function lemma returns the base of a word, in the example above: injury for input injuries, or wound for wounds. Hearst also sketches a procedure on how to learn new patterns for a given relation, or patterns for a new relation. This procedure basically relies on acquiring occurrences of 86 CHAPTER 4. METHODOLOGY the corresponding terms, and generalization of the respective phrases found in text. Hearst [82] describes a number of patterns for extracting is-a relations, among which is the example given above. The difficulty lies in finding constructions that frequently and reliably indicate a relation of interest. The following characteristics are desired [82]: 1. The patterns occur frequently and in many text genres. 2. They (almost) always indicate the relation of interest. 3. They can be recognized with little or no pre-encoded knowledge. So the first characteristic is concerned with the recall of the pattern, the second one with precision. But both recall and precision of the original Hearst patterns are not satisfactory, the patterns occur quite rarely in ordinary text, so large corpora are necessary. Some of the subsequent work related to lexicosyntactic patterns described below addresses the issues of raising precision and recall. Many research papers were published inspired by the original paper of Hearst in 1992. Among those are extensions of the set of patterns [89], the application of Hearst patterns in specific contexts, the definition of patterns to extract and populate other types of relations, non-taxonomic relations [133, 3, 14, 197, 67], and the combination of Hearst patterns with methods such as Latent Semantic Indexing [30]. More recently researchers also matched the patterns on the Web using search engine APis such as the one of Google [156, 40, 41, 53] -addressing low recall as a well-known problem of Hearst patterns. For more information on the details of these approaches see Section 4.3, Literature Review. An important step in the evolution of lexico-syntactic patterns is the automatic acquisition of patterns for a list of predefined relations. This learning task is typically based on a set of hand-crafted examples per relation, and a corpus from which patterns are extracted subsequently. A well-known approach for pattern learning are rote extractors [21, 1, 140]. Rote extractors allow extracting non-taxonomic relations from text. Rote extractors look for textual contexts that happen to convey a certain relation between two concepts [7]. More precisely, rote extractors estimate the probability of a relation r(p, q) given the surround context A1 pA2qA3 [110]. The method of Ravichandran and Hovy [140] is often applied to train a rote extractor from the Web: The first step is to select a pair of related elements (e.g. Dickens, 1812 for a relation birth-year). A query to a Web search engine in the form of terml AND term2 ( e.g. "Dickens AND 1812") generates 4.2. METHODS FOR LEARNING SEMANTIC ASSOCIATIONS 93 Dimension 2: tournament A l·· ❖ •· 0 Query: "tennis", •tournament• Y Document 1 ,,,,., Document 2 . . --:...--------+J························· • . . 1 2 Dimension 1: tennis Figure 4.2: Two dimensions from a simple VSM example, showing the query vector and two document vectors discussing various measures to compute the similarity between vectors, let us briefly reflect on another application of the VSM, which is directly related to the method presented in Chapter 4. In ontology learning, the context of a word is a very important property in order to assess the similarity between words [37]. In this thesis instead of words the author applies this principle to word pairs, i.e. the two concept labels ( regular expressions) representing the concepts of a relation occurring in the same sentence. The basic idea, however, remains unchanged. The well-known distributional hypothesis of Harris [77] states that two words are similar to the extend that they share similar context. Empirical investigations support the correctness of Harris' hypothesis. Grefenstette [72] further demonstrates that relatedness in vector space correlates with semantic relatedness of words [37]. As in most work in ontology learning, the assumption that similarity in context corresponds with semantic similarity is a key aspect in this thesis. A common way to represent context is a vector in high-dimensional space, the interesting question is what features are extracted to serve as context of a word (or relation). Cimiano [37] list various alternatives on how do define context: One alternative is to define the whole document a word appears in as context [104, 154], which leads to very high dimensional and computationally intensive vectors. 94 CHAPTER 4. METHODOLOGY Other alternatives are word windows of n words to the left and right of the target [81, 199, 166, 192], or simply the use of the sentences where the target appears ( used in this thesis next to word windows), or specific grammatical constructs such as appositions, copulas, verb-object, verb-subject, adjective modifiers, and nominal modifiers [87, 72, 28]. Similarity Measures for the VSM. Cimiano [37] defines the characteristics of a similarity measure. It is a function sim : IR x IR -+ [O, 1], with some special properties: For a feature vector the similarity to another feature vector is O if there is no dimension where they both have non-zero values. If there is a dimension where both compared vectors have non-zero values, then the similarity exceeds 0. The maximum similarity is 1, and is given when a vector is compared to itself. Not all similarity metrics need to be symmetric. A distance measure is a related type of function, that can be transformed into a similarity measure by a bijective and monotonic decreasing function. One of the characteristics of a distance measure is that the distance between a vector and itself is 0. A basic ingredient in many similarity measures is the dot product, also called inner product of two vectors, which is defined in Equation 4.11. n a• b = L aibi = a1b1 + a2b2 + a3b3 + · · · + anbn i=l ( 4.11) The dot product is no appropriate similarity measure by itself, as it is sensitive to the size of the involved vectors -it favors longer vectors and does not remain in the range of [O, 1]. Therefore the dot product needs to be normalized, typically with the vector length. Vector length exists in two variants, the "simple" vector length (Equation 4.12) and the Euclidian vector length (Equation 4.13): n <a>= La; i=l ( 4.12) ( 4.13) The simplest similarity measures are the ones geared towards binary vectors. The values in binary vectors are in the range of {O, 1 }, i.e. a feature is present are not. The Dice and Jaccard coefficients are two traditional IR measures, they both combine dot product and variants of vector length defined above. 4.2. METHODS FOR LEARNING SEMANTIC ASSOCIA11ONS 95 2a • b Dice(a, b) = b <a>+< > (4.14) a•b L~-i a;b; Jaccard(a, b) = b <a>+< > -a• E~=i a;+ E~=i b; - E~=i a;b; (4.15) The two given measures for binary vectors have been adopted to vectors containing weighted features. Grefenstette [72] adopted the Jaccard measure as follows: En min(a;, b;) Gref enstette/ Jaccard(a, b) = E~=i ( b i=i max a;, ; (4.16) The numerator in Equation 4.16 reflects the overlapping features in the two input vectors, and the denominator serves as normalizing factor [94]. Curran [46] extended the Dice measure to weighted feature vectors, he uses the Jaccard numerator and replaces the denominator with the total sum of non-zero entries in the vectors. C ID . ( b)-2):~=imin(a;,b;) urran ice a, - '°'n b L..i=i a;+ i ( 4.17) Exemplified with our example from above, Grefenstette/ Jaccard yields the following results -which favor di over d2: 1 + 1 Gre f enstette / J accard( Qi, di) = 2 2 + +1+1 1 Grefenstette/ Jaccard(qi, d2) = - 1 -+- 3 -+-l 1 - 3 1 5 Another, and also the most commonly used way to assess the distance and similarity between vectors is to approach the task with geometrical measures. The simplest among those is the Manhattan distance (also known as Levenshtein distance or Ll norm, see [941), which is defined as: n Li(a, b) = L /a; - b;/ ( 4.18) i=i The Euclidian distance or L2 norm is defined as follows: n L2(a, b) = L(a; - b;) 2 ( 4.19) i=i 96 CHAPTER 4. METHODOLOGY Those two measures assess the distance between the vector end points, and both stem from the more general Lq or Minkowski measure [37]. They are very intuitive, but rarely used for vector similarity as they obviously are very sensitive to extreme values, i.e. there is no normalization involved. The cosine measure is the most frequency used vector similarity measure [94]. It is basically a normalized dot product -the dot product is divided by the products of the lengths of the vectors involved: ( ) Ln-1 a;b; cos a b = ---,~.===•-::::::;.::====..: ' JE~=I a; L~=I b; (4.20) The normalized dot product is the same as the cosine of the angle between the two vectors, Equation 4.21 demonstrates this observation: a•b cos0 = lallbl (4.21) For our example presented above the cosine similarity measure yields the following results, which clearly support the intuition that document d1 is more relevant for query q1: 2+1 cos(q1 ,d 1) = J2"'+To = 0.87 2 + 10 1 cos(q1, d2) = J2+TI = 0.28 2 + 11 The cosine is not sensitive to vector length, i.e. longer documents or vectors representing more frequently occurring entities are not favored -the cosine just measures the angle between two vectors, independent of vector length. The resulting value ranges from 1 (if the vectors point in the same direction) to O (for orthogonal vectors that share no common features). The presented ingredients, i.e. the vector space representation for documents (or other entities) and eventually queries, combined with similarity measures, allow to create an ad hoc information retrieval system. Such a system accepts a user query, transforms it into a vector, computes the similarity to documents in the collection, and then returns a similarity-ordered list of documents. Ranked retrieval is one of the advantages of the vector space model, next to its simplicity and the ease with which vectors can be modified. One of the downsides is that the vector space model assumes orthogonality, and hence independence between features [153]. Another way to measure similarities bases on probability distributions. For more information about this topic and related measures such as relative entropy, mutual information, or Jenson-Shannon or Skew divergences, the 4.2. METHODS FOR LEARNING SEMANTIC ASSOCIATIONS 97 interested reader is referred to Cimiano [37] and Jurafsky and Martin [94]. Probably the most famous, and rather simple to explain, of these measures is pointwise mutual information [54], which relies on information on how often two events x and y co-occur, in relation to how often they should co-occur when they are independent of each other. Latent Semantic Analysis A document collection in information retrieval can be represented as a termdocument matrix. Figure 4.3 gives the general form of a term document matrix A. It is typically a sparse matrix in which the rows represent the documents in the collection (D 1 • • • Dm), and the columns correspond to all the terms occurring in the whole collection (T 1 • • • Tn)- T1 T2 Tn D,C" a12 "'") A= D2 a21 a22 a2n . . . . . . Dm aml am2 amn Figure 4.3: Term-Document matrix A A technique that builds on matrices such as the term-document matrix is Latent Semantic Analysis ( =LSI) (LSA) (also called Latent Semantic Indexing {LSI) in information retrieval context). LSA is a mathematical method for computer modeling and simulation of the meaning of words and passages. It analyzes representative corpora of natural text and thereby closely approximates many aspects of human language learning and understanding [99]. LSA analyzes relations between a set of documents and a set of words via concepts that are generated for the terms in the occurrence matrix. It uses singular value decomposition to reduce the size of the term-document matrix [75]. Single Value Decomposition (SYD) is a well-known technique in matrix theory, which became practical for application to such complex problems only after the advent of powerful enough machines and algorithms to exploit them in the late 1980s [99]. Opposed to techniques such as the vector space model, which operate directly on keywords without semantic knowledge ( "surface co-occurrence"), SYD promises to approximate many aspects of human language learning and understanding. LSA vectors approximate the meaning of a word as its average effect on the meaning of the documents where it occurs, and it reciprocally approximates the meaning of documents as the average of the meaning of their words [99]. Possible applications for 98 CHAPTER 4. METHODOLOGY LSA are various tasks in information retrieval, such as comparing documents in concept space ( clustering and classification) or cross-language information retrieval (finding similar documents across languages), or the detection of relations between terms via the concepts. For more information about LSA see for example the description of LSA from a rather psychological point of view [98], a deeper discussion of its mathematical aspects [119], or an early article describing the general aspects of method in some detail [49]. 4.2.4 Machine Learning Paradigms Machine learning is a discipline that is concerned with the automatic recognition and detection of certain patterns and regularities within data. The applications are manifold, they encompass natural language processing, machine perception, syntactic pattern recognition, biotechnology, even tasks such as credit card fraud detection or stock market analysis -to name but a few. Besides academia, industry applies machine learning methods extensively in very heterogeneous areas. Machine learning is a sub-field of artificial intelligence [167], a definition from Samuel [155] from the early days states that machine learning is "the field of study that gives computers the ability to learn without being explicitly programmed. Mitchell [121] gives a more recent and precise definition, he calls machine learning a well-posed learning problem, where a computer program is said to learn from an experience E with respect to a task T and a performance measure P -if the performance in learning the task is improved by the experience E. So machine learning bases on induction from patterns detected in data. Ontology learning often utilizes machine learning approaches, but due to the large extent of the field this section will only include the basic principles of the field in order to understand the work presented in Section 4.3, such as the two main paradigms of supervised and unsupervised learning. In supervised learning, the system provides labeled training examples including the "correct answer" as input to a learning algorithm. The aim is to train the learning algorithm to give answers for new examples. The input is an n-dimensional feature vector, for example a system might get features such as the weight, and color. of an object to predict if the object is a kiwi or an orange. Every input feature corresponds to a dimension. In classification tasks the output (the variable predicted) of a system is a discrete value, in regression analysis it is a continuous value. So in a classification task the algorithm predicts a target class label (from a set of classes) based on an input feature vector. Binary classification is a specialization of the classification task where there are only two target classes. 4.2. METHODS FOR LEARNING SEMANTIC ASSOCIATIONS 99 The prediction algorithm needs a mapping function from Rn (the feature vector space) to L ( the target class labels) [37]. The goal is to approximate the mapping function from training examples, the approximation must not be too close ( overfitting) in order to be able to generalize from training examples to new examples. More precisely, the aim of a classifier is to minimize the empirical risk of misclassification based on a loss function, which quantifies the cost of misclassifying one example from one class as another [37]. When training a classifier one has to be aware of the problems of overfitting and skewed datasets. To avoid overfitting, classifiers should never be evaluated on training data itself but on test data. The problem of skewed data emerges when some target classes are much more frequent than others. A credit card fraud detection classifier would gain 99.9% accuracy when the output is always "no fraud" -which is definitely not the expected behavior. The algorithms of unsupervised learning need no explicit training examples as input, the input is just a dataset - for example a natural language text corpus -the learning algorithm tries to find interesting structures in the data. Typical examples of unsupervised learning are clustering methods, which detect and exploit frequent and common patterns in data. Other applications range from market segmentation to the detection of galaxies from astronomical data. Computational learning theory is a branch of theoretical computer science concerned with the analysis of machine learning algorithms. On the one hand learning theory helps to estimate the performance of machine learning algorithms. Furthermore, it gives clues such as how many training examples are sufficient for a certain application of a supervised learning algorithm. Computational learning scientists also study the complexity and feasibility of learning. An algorithm is regarded as feasible if it runs in polynomial time. Supervised Learning Methods Supervised learning methods generate a function to map input (feature vectors) to an output. The type of the output variable ( discrete vs. continuous) determines if a classification or regression task emerges. Jurafsky and Martin [94] distinguish sequential and non-sequential classification problems. In a sequential classification problem a model is applied that assigns some label to each unit in a sequence. POS tagging is an example of such a problem. Probabilistic sequence classifiers compute a probability distribution over possible labels and choose the best label sequence. Hidden Markov models (see below) are an example of such a probabilistic sequence classifier. Nonsequential classification assigns a class to a single observation based on its features, this includes tasks such as text categorization ( e.g. is an email spam 100 CHAPTER 4. METHODOLOGY or not), and sentiment analysis (does the text fragment express positive or negative opinion) [94]. A probabilistic classifier also gives the probability that an observation is correctly assigned to a class, in fact it gives a probability distribution over all classes. A common problem in machine learning are imbalanced datasets. An example was already mentioned with the credit card fraud sample, where almost all transactions are in the class "no fraud". In order to get the desired results from a classifier, techniques such as rebalancing are applied: Oversampling replicates some training examples from the minority class, undersampling removes some examples from the majority class until the wanted distribution is obtained [37]. Rebalancing has to be used with care, oversampling may lead to overfitting, and undersampling removes potentially helpful input. Another way to cope with imbalanced datasets is the use of cost-sensitive learning, which assigns relative costs of misclassification to the specific classes. The cost of misclassification for the minority class is typically high. The learning algorithm minimizes total cost. Bayesian Classification. Bayesian classifiers are statistical classifiers to predict class membership probability [75]. They are based on Bayes' theorem, which states that one conditional probability, for example the probability of a hypothesis given observed evidence, depends on its inverse -in this example the probability of the evidence (E) given the hypothesis (H). In the simple case of only involving discrete distributions the Bayes theorem can be formulated as: P(HIE) = P(EIH) · P(H) P(E) (4.22) Studies show that simple Bayesian classifiers, also called naive Bayesian classifiers, which assume that all features are independent and have the same relevance, are comparable in performance with other methods such as decision trees and neural networks [75]. In contrast to naive Bayesian models, Bayesian belief networks are graphical models that allow the representation of dependencies among subsets of features. The training of a Bayesian classifier is performed simply with a set of examples, which consist of a list of features and the respective classification for the example. Naive Bayesian classifiers are simple to learn and to adopt, and it's easy to interpret the learned probabilities of features. However, the independence of features leads to the inability to exploit combinations of features [167]. 4.2. METHODS FOR LEARNING SEMANTIC ASSOCIATIONS 101 Hidden Markov Models. Hidden Markov Models (HMM) are models for sequence classification, and are among the most important learning models in speech and language processing [94], used e.g. for speech and handwriting recognition, or POS tagging. HMM base upon Markov chains (also called the observed Markov model). Markov chains are special cases of weighted finite-state automata, where every input sequence uniquely determines which states the automata will go through. A weighted finite-state automaton is defined by a set of states and possible transitions between those states -every such transition (arc) has an associated probability, which creates a transition probability matrix. Such a Markov chain helps to compute the probability of a sequence of events observed in the world. A HMM allows to talk about observed events and hidden events -hidden events cannot be directly observed in the real world. In POS tagging, for example, the observed events are the words in a sentence, the hidden events correspond to the POS tags. So next to a transition matrix a HMM includes a sequence of observation likelihoods, i.e. the probability of a observation being generated in a distinct state. HMMs are characterized by three fundamental problems [139, 94]: The first one ( likelihood) is to determine the likelihood of making a given observation sequence for a given HMM. The second one (decoding) is, given an observation sequence and a HMM, to discover the best hidden state sequence -in POS tagging that is the main problem to be tackled. The final tasks (learning) consist of learning the parameters of an HMM, given a sequence of observation and a set of states. Maximum Entropy Models. Maximum entropy (MaxEnt) models are applicable for non-sequential and sequential classifiers. MaxEnt is a probabilistic classifier, it belongs to the family of exponential or log-linear classifiers. MaxEnt combines input features linearly, i.e. features are weighted and then added up -this sum is used as exponent in a function that determines the probability that observation x is in class c. For more detail on MaxEnt models and their background see for example Jurafsky and Martin [94]. Decision Trees. Decision trees ( also called tree diagrams) are models used for classification. Decision trees consist of internal nodes and leafs. Internal nodes correspond to tests for a distinct feature, the arcs reflect the value of a certain feature, which finally leads into leafs. Leaf nodes are the classes used for classification. So in order to classify some input observation, starting from the root of the tree, the features of the observation determine the path through the tree -until a leaf is reached. The learning or induction of a decision tree can be done in a greedy manner with a top-down recursive 102 CHAPTER 4. METHODOLOGY divide-and-conquer algorithm [75, 138]. Starting from the root node, which includes all training samples, an entropy-based measure detects the feature with the most discriminative power, which then separates the samples into classes. The process is recursively applied until all samples are of the same class or there are no more features left. A big advantage of decision trees is that learned models are easy to interpret by a human, for example to determine which features of the feature set are useful and discriminative. Decision trees are well suited for datasets with a lot of categorical data and numerical data that has breakpoints. For problems with many numerical input features or complicated relations between the features, decision trees are not the best choice [167]. Kernel Methods. Kernel methods are a class of algorithms for pattern analysis. They allow the study of general types of relations such as clusters, correlations and classifications in general types of data, for example text, sets of points, or images. As a recent development in the field of machine learning algorithms, kernel methods became widely used for relation extraction [7]. Traditionally, theory and algorithms of machine learning have been well developed for the linear case, but real world data and analysis problems often require nonlinear methods in order to detect the kind of dependencies that allow successful prediction of properties of interest [88]. The advantage of kernel methods is that they provide efficient training algorithms (as opposed to multi-layered neuronal networks for example, which are hard to train) and once trained, they are very fast in classifying new examples. Another strength is the ability to represent complex nonlinear functions [149]. Drawbacks are the need for large datasets in order to produce good accuracy, and the difficulty of interpreting a Support Vector Machine (SVM) [167]. SVMs are a specialization of kernel machines, which are typically applied for binary classification problems [37]. A nonlinear transformation maps the input vector space into some other vector space. The kernel function, which needs to be established, then defines the dot product between vectors in that transformed vector space [37]. Subsequently, the goal is to find the maximum-margin hyperplane which splits the training examples into two classes, this hyperplane represents the best discriminator between the two classes. Training examples next to the hyperplane are called support vectors, only the support vectors are finally needed to define the hyperplane [37]. So in fact a nonlinear problem, or more precisely nonlinear observations, are mapped into a higher-dimensional space, where a linear classifier is applied 4.3. LITERATURE REVIEW 109 RelExt, as described by Schutz and Buitelaar [164], provides a tool for relation extraction in the context of ontology extension. They build on the common idea that verbs express the relation between two concepts, and specify domain and range. This idea is associated with the work on selectional preferences for verb arguments [188]. RelExt extracts relevant verbs and their grammatical arguments from domain-specific text and computes corresponding relations with a combination of statistical and linguistic processing. More precisely, in a first step highly domain-relevant headnouns and verbs are extracted, then the algorithm computes selectional preferences for the verbs. Finally, that information is used to construct triples. So basically the most relevant verbs are chosen as relation labels. Gamallo et al. [63] present a corpus-based approach to automatically extract semantic relations between words. In a first step, syntactic dependencies are automatically classified according to their selectional restrictions, thereby creating semantic groups. Furthermore, they detect groups of nouns according to their distribution in detected selectional restrictions. Interpretation rules help to learn the specific semantic relations underlying syntactically related words, i.e. the interpretation rules provide a mapping from the syntactic level to relations in a semantic space. Cimiano [37] proposes a method for learning relations from corpora based on verbal expressions that follows the tradition of the already mentioned work of Gamallo et al. [63], Schutz and Buitelaar [164] and Ciaramita et al. [34]. The main focus in this approach is the generalization of the arguments of a relation with respect to a taxonomy. They demonstrate this with an example: instead of work_for(woman,store) or work-.for(employee,institute) the most general signature, in this case possibly work_for(person,organization), is of most interest. Various statistical measures, namely conditional probability, x2 and Pointwise Mutual Information (PMI) are evaluated for their ability to find the correct level of generalization upon the Genia corpus and the Genia ontology. Conditional probability outperforms the other measures in these experiments. Ciaramita et al. [35] present an unsupervised approach for learning arbitrary relations between annotated named entities in the molecular biology domain using the Genia ontology and the Genia corpus, the approach is also applicable to other domains. The method relies on dependency structures generated by a constituent syntactic parser [22] for the extraction of relation candidates. A x2 test which compares the observed and expected frequencies helps to select relations for ordered pairs of named entities from the list of candidates. A manual evaluation of the method is included. Rinaldi et al. [144] describe an environment to extract domain-specific relational information, with experiments based on an extended version of the richly an- 110 CHAPTER 4. METHODOLOGY notated Genia corpus. For this task they apply deep-linguistic parsing and manually created patterns as well as ontological constraints. In an unsupervised method to learn ontologies from scratch, Reinberger et al. [142] apply shallow parsing to select functional relations from the syntactic structure subject-verb-direct-object. Clustering then allows to build semantic classes of terms sharing a certain relation. They applied and evaluated the approach upon two domain corpora, one from the medicine domain (SwissProt) and a small legal corpus. Poesio et al. [132] present a supervised approach that learns feature norms for given concepts, that is relation types that intend to "provide insights into mental representation of concepts". These feature norms are related to qualia structures, and are manually compiled for subjects aiming to find the most important properties for a set of concepts. The authors evaluate relations such as external surface property, origin or function. They applied kernel methods for the learning process, combining a global and a local kernel function with mostly linguistic features, and used SVM as learning algorithm. Zelenko et al. [202] leverage kernel methods to extract relations from unstructured natural language text. The kernels are defined over shallow parse representations of text. With the help of SVMs and Voted Perceptron as learning algorithms, they extract the specific relations person-affiliation and organization-location. An evaluation of the method comparing it with feature-based learning algorithms shows promising results. 4.3.2 The Web and Semantic Associations Wong et al. [196] propose a method for acquiring semantic relations for the construction of lightweight ontologies which uses only Web resources (Wikipedia and search engines) as input. Their approach includes two phases, namely term mapping and term resolution. In the mapping phase Wikipedia mappings yield connections between input terms. The main contribution is the resolution phase, which comprises lexical simplification, word disambiguation and association inference. Lexical simplification reduces the lexical complexity of composite terms in order to be able to find mappings in Wikipedia. Mutual information between constituents of an input term calculated with Google page count statistics guides the lexical simplification process, resulting in appropriate subphrases. Word disambiguation aims at finding correct senses for ambiguous terms by the virtue of the senses' relatedness to the already mapped terms. In the association inference step cluster analysis is applied to terms labeled as non-existent during the mapping phase, which means that those terms have no lexical matches in Wikipedia. The 4.3. LITERATURE REVIEW 111 authors propose a term clustering algorithm with featureless similarity measures known as Tree-11raversing Ant [195] to generate potential associations. Jiang et al. [90] present a knowledge-rich method for the mining of generalized associations of semantic relations, based on textual content from the Web. As opposed to classical text mining methods, which transform the input textual content into simplistic intermediate representations ,such as bags of words or word vectors, the authors aim at an intermediate representation that can express semantic relations between the concepts found in text. For this purpose they use RDF (see Section 3.2.1), which enables the representation of text as simplified conceptual graphs. After applying NLP tools such as part-of-speech, tagging a set of predefined syntactic patterns is used to extract semantic relations, which are encoded as RDF statements. Additionally a term taxonomy is generated on-the-fly with WordNet and domain-specific lexicons. As traditional association rule mining on the extracted RDF statements suffers from data sparseness (relations are seldom repeated in many documents), and some appropriate kind of generalization is needed, the authors propose a novel generalized association pattern mining algorithm ( GP-Close) to find the proper level of abstraction and labeling. 4.3.3 Domain Text and Linguistic Patterns Many authors have applied handcrafted patterns in the tradition of Hearst to natural language text for various tasks, for example anaphora resolution [133], or in specialized environments, for example the extraction of relations in texts surrounding images [3]. Berland and Charniak [14] adopted Hearst patterns for the identification of meronyms (part-of relations). Various other approaches to learn specific relation types based on linguistic patterns are listed in Sanchez and Moreno [156]. Yamada and Baldwin [197] discover telic and agentive roles for nouns from text data -as parts of qualia structures, where the telic role represents a typical purpose of the entity and the agentive role represents the origin of the entity, they rely on certain lexico-syntactic patterns as well as maximum entropy model classifiers; Girju and Moldovan [67] present a semi-automatic method to discover generally applicable lexico-syntactic patterns that refer to the causal relation. Poesio and Almuhareb [131] present a method for determining combinations of some of these relation types. This type of handcrafted patterns works well for specific relation types in a given domain, but is restricted to certain relations and domains as the cost of adopting patterns can be too high [122]. Byrd and Ravin [25] extract salient concepts from document collections, and unnamed (see above) and named relations between them. They extract named relations with certain grammatical patterns using specially-built fi- 112 CHAPTER 4. METHODOLOGY nite state automata, for example "Gerstner, the CEO of IBM, ... " results in the relation triple <Gerstner:CEO:IBM>. Filtering the output, such as including selectional restrictions facilitated by named entity recognition, helps to improve the results. Alfonseca et al. [7] present methods and algorithms to improve the precision of rote extractors, which are a common method to extract non-taxonomic relation instances (see Section 4.2.2). Their evaluation shows that precision values are lower than expected for many patterns learned by traditional rote extractors, especially for those that are ambiguous -those patterns are filtered subsequently. Ruiz-Casado et al. [148] apply these improved rote extractors aiming at semi-automated semantic annotation of Wikipedia. Based on a given set of relations they associate Wikipedia entries and argue that -although automatic methods in the field of natural language processing (NLP) typically produce some amount of mistakes -it needs less effort to correct the mistakes than annotating the relations from scratch. Their method starts with a seed list of training examples per relation type, and extracts sentences from a Wikipedia corpus with NLP tools. The corpus itself is created by recursively crawling a part of Wikipedia from some starting points. The patterns found in text are then generalised in order to raise recall and pruned to improve precision. They evaluate the approach with eight predefined relations such as person's birth year, actor-film or player-team. The measured precision ranges from values >74% for person's birth to below 10% for player-team. Ruiz-Casado et al. attribute this to the fact that some relations often appear with fixed and unambiguous patterns, other relation types use more general and ambiguous patterns. Chagnoux et al. [33] extend the idea of automatically learning new patterns for given relation types. Their system integrates new relations found in external ontologies, and automatically learns patterns representing the new relations -thereby iteratively extending the pattern base. But the architecture is not completely automatic, for all new patterns and relations they enforce a step of manual validation to ensure correctness and relevance. 4.3.4 The Web and Linguistic Patterns Etzioni et al. [53] use Hearst style patterns applied to the Web as part of KnowltAll, a system that aims to automate extracting large collections of facts from the Web autonomously, domain-independent, and in a scalable manner. Markert et al. [114] apply shallow patterns to the Web for nominal anaphora resolution. Cederberg and Widdows [30] show that the precision of Hearst patterns can be improved by filtering the results of patterns with Latent Semantic Indexing (see Section 4.2.3). They assume that hyponyms 4.3. LITERATURE REVIEW 113 and hypernyms are distributionally similar, and filter pairs below a certain threshold -resulting in a reduction in the rate of error by 30%. To increase the recall of Hearst patterns they apply a graph-based model of noun-noun similarity which was learned automatically from coordination patterns, and present a five-fold increase in the number of correct hyponymy relations extracted. Section 4.2.2 already described the idea of Open Information Extraction -it bases on large-scale (to the point of Web scale) extraction of relational data, independent of the type of relation. TextRunner [9] is an implementation of the Open IE paradigm on the basis of natural-language text. To figure out if there is a general model of how relations are expressing in English text the authors manually examined 500 random sentences from an IE corpus, and come to the result that most relations are indeed expressed with a compact set of relation-independent patterns. These patterns are listed in [52], and include very simple ones such as "E 1 Verb E2 ". Detailed additional contextual clues are necessary to decide if there really is a relation between the two entities occurring with the verb. The original version of TEXTRUNNER, presented by Banko et al. [9], used a "Naive Bayes Classifier to predict whether heuristically-chosen tokens between two entities indicated a relation or not" [10, p 32]. This classifier was then replaced with a graphical model called a conditional random field (CRF), which, given a set of input observations, maximizes the conditional probability of a finite set of labels. With CRF the extractor learns to label each word in a sentence by annotating the beginning and end both of entity names and relation strings. Among the features used in the model are regular expressions, part-of-speech tags, context words, etc. For more details on the model and its characteristics see Banko and Etzioni [10]. After training the model, TEXTRUNNER can be run on a corpus in linear time and extracts triples trying to capture the relations existing in the sentence. Many additional modules such as synonym detection help to improve the quality of extracted relations, or to make them accessible, e.g. by indexing them with Lucene. 7 The applications of the system are various, for example for question answering, opinion mining and fact checking [52]. Compared to traditional information extraction, Open IE offers higher levels of precision, at the expense of recall. Open IE should be preferred when the relation labels are not known in advance, new relations should be discovered, or their number is massive. Banko and Etzioni [10] also present and evaluate a hybrid extraction approach combining traditional and Open IE. 7 http://lucene.apache.org 114 CHAPTER 4. METHODOLOGY WEBTABLES [26] applies the Open IE paradigm to the extraction of relations from structured data, more precisely from HTML tables on the Web. So the approach aims at generating relational data by exploiting the implicit structure of the HTML table tag. Cafarella et al. [27] estimate that only a minor percentage ( 1.1 % ) of HTML tables on Web really contain relational data, the rest is used for page layout etc. The main challenge is to distinguish relational from non-relational tables automatically, WEBTABLES applies a two-step procedure: Step 1 throws away tables that are obviously not relational. In step 2 a statistical classifier distinguishes relational from non-relational tables based on a set of hand-written features, such as the number of rows, the number of columns, the number of columns with numeric data etc. The advantage of exploiting tables is that they contain a big number of facts structured in a way that makes it easy to detect the involved terms and their relations. The so-called "Deep Web" refers to content on the Web only accessible through forms, and therefore usually hidden from search engine crawlers. Cafarella et al. [27] propose a method to surface that hidden information into Web pages that can be indexed by search engines. Referring to the spirit of Open IE that method should be efficient and scalable. The major obstacle is to pre-compute the form submissions for any given form in order to surface plenty of the underlying database. Cafarella et al. [27] propose heuristics such as using keywords extracted from the page and iteratively from the result set, as well as using libraries of types for typed text boxes (e.g. US zip codes). Sanchez and Moreno [156] present an unsupervised approach using verbs from sentences containing domain concepts and search engine queries in the process of learning non-taxonomic relations. This method combines a pattern/rule-based approach with the intensive use of Web statistics. We describe it in some more details, because the approach also includes and exemplifies the use of Web statistics, which some researchers in the field of ontology learning applied quite successfully in the last few years. The Web, due to its huge size and heterogeneity can be assumed to approximate the real distribution of information of mankind [36]. Relying on the Web is a way to tackle the sparse data problem [96]. Although individual Web resources are considered untrustworthy, redundancy of information on different sites can represent a measure of relevance and trustiness [42]. Keyword based search engines such as Google or Yahoo provide statistics about the information distribution on the whole Web. These statistics about the presence of a certain query term can be computed efficiently from the estimated amount of returned results. Turney [183] presents several heuristics to leverage statistics provided by search engines, for example forms of pointwise 4.3. LITERATURE REVIEW 115 mutual information (see Section 4.2.3). These measures use hit counts to calculate the degree of relation between two query terms - for example with a query between an initial word (term 1) and a related concept (term 2 ): S ( ) _ hits(term 1 AND term 2) core term 1, term 2 - h. ( ) its term 2 Such statistics can be retrieved in a very efficient and almost immediate manner, avoiding the analysis of large corpora, and they provide very robust measures as they are obtained from the whole Web. Returning to the work of Sanchez and Moreno, the authors start the process of learning non-taxonomic relations with the extraction of verbs including prepositions from sentences that contain concept pairs, more precisely a concept and the hyponym of the concept, from an ( evolving) taxonomy built with their ontology learning system. They apply some linguistic filtering rules to raise the quality of the resulting verbs [156]. The verb candidates are then tested for domain relatedness with a query that adopts the Web statistics formula presented above: S ( b d . K d) _ hits( verb AND domainK eyword) core ver , amain eywor - h. (d . K d) its omam eywor A selection threshold controls which verbs are considered domain-specific, empirically a value of IE -3 to IE -5 appears suitable. Those verbs are the labels for the new, domain-specific relations. Search engine queries with concepts and their respective verbs return a corpus of sentences. A very strict linguistic pattern extracts candidate terms for a non-taxonomic relation with the original concept and verb. A search engine query similar to the one just presented tests those concept candidates for domain relevance. The ontology learning process inherits the learned non-taxonomic relations to all subclasses of concepts, which also saves computational resources, as selected or rejected verbs need not be examined again for subclasses. The method of Sanchez and Moreno has some interesting features: it is completely unsupervised, so it avoids the need for a human expert, it is a domain independent solution, and the learned ontologies can be dynamically adopted and extended to reflect evolving domain knowledge. One of the downsides is that the learned relation labels have no further semantic properties, i.e. they cannot be used for inference, and the current implementation lacks capabilities to detect synonyms, inverses, etc. 116 CHAPTER 4. METHODOLOGY 4.3.5 Semantic Web Data and Reasoning This section introduces related work that exploits structured data present in the current Semantic Web to support ontology learning tasks, especially to detect relations between concepts. Harvesting the Semantic Web, i.e. automatically finding and exploring online knowledge sources, has been a novel trend in the last few years -favored by the recent growth of online semantic data and the building of gateways to access these data [151]. Alani [4] proposes a method for ontology construction by cutting and pasting ontology modules from online ontologies. He proposes a five-step system architecture for ontology construction: (i) identify ontologies relevant to a keyword search via Semantic Web search gateways, rank these ontologies for relevance in (ii); (iii) segment ontologies to extract relevant parts; (iv) merge those parts with ontology merging/mapping algorithms; (v) evaluate of the constructed ontology to ensure a certain level of quality. Another interesting method, which is not directly related with the learning of non-taxonomic relations, but could potentially be adopted to disambiguate and enrich relation labels, is presented by Garcia et al. [71]. Their unsupervised approach dynamically uses online ontologies for word-sense disambiguation of input keywords. The knowledge represented by a pool of ontologies available on the Web yields possible senses for the input keywords. The algorithm then combines the information from the Semantic Web with Google based frequencies to select the right senses. Scarlet [152] 8 provides a technique for discovering relations between two concepts by harvesting the Semantic Web. We present this approach in more detail, because it is a part of the method described in the present thesis. Scarlet automatically selects and exploits online ontologies to discover relations between two input concepts. In a simple example, given the concept label Researcher and AcademicStuff, Scarlet identifies online ontologies to determine how the two concepts are related at run-time -and combines the information to infer the relation, e.g. Researcher ~ AcademicStuff. Originally Scarlet was restricted to subClassOJ (~) and distjointWith (-.L) relations, but has been extended to include named relations as well. Scarlet was initially built for the task of ontology matching, where it delivered background knowledge from the Semantic Web to the matcher [150] -but the component and its functionality can be integrated into third-party systems as well. Various parameters help to regulate the run-time performance and accuracy of Scarlet. Relation discovery with Scarlet anchors the given input concept labels in online ontologies (A and B are anchored as A' and B'). There are basically two strategies: Strategy Sl consists of finding ontologies that contain both 8 http://scarlet.open.ac.uk 4.3. LITERATURE REVIEW 117 Online Ontologies Online Ontologies I \= I ------B Figure 4.4: Relation discovery within one ontology (S1) and across ontologies (S2), from Sabou et al. [152] concepts A and B. The system extracts the relations from those ontologies, combines them in a way set by the given parameters (see below), and returns the result to the caller. If strategy S1 fails, then strategy S2 can be applied. S2 uses multiple ontologies to extract relations in a recursive fashion -concepts related to A are extracted from one ontology, and then concepts related to B from another ontology. The concepts related to A include the parent concepts and subclasses of A For example, to detect a relation between cabbage and meat, one ontology might state that Cabbage !:;: Vegetable, and another that Vegetable 1Meat, resulting in Cabbage 1Meat. Figure 4.4 gives a graphical impression of S1 and S2 [152]. Scarlet supplies a set of parameters to customize its behavior. As mentioned above, the caller can decide whether to use strategy S1 or S2, which has a significant impact on the run-time of a query. Furthermore, the number of derived relations is configurable. The options range from just returning the first found match, with higher risk that the information is inaccurate, to returning all found matches, and potentially combining them, which is computationally more expensive. The methods to combine relations if various matches are found range from returning all matches unaggregated to returning the most frequent relation type or only return a type if all relations are the same. Finally, for strategy S2, the depth of search in ontology hierarchies determines if only the direct parent and subclass of a concept are considered (depth= 1), or deeper levels as well (depth= n). 118 CHAPTER 4. METHODOLOGY Scarlet is closely related to the Watson Semantic Web search engine [48] 9, which serves as ontology retrieval backend, although Swoogle can be used as backend, too. Watson collects and indexes semantic information found on the Web, and provides a variety of access mechanisms; the goal is to support the building of new kinds of applications that benefit from of the Semantic Web. Via its plugin10, Watson helps ontology engineers to edit an ontology, suggesting additional statements for classes found in online ontologies. The plugin is available for the NeonToolkit 11 and for Protege.12 Evolva [201] integrates Watson and Scarlet in an ontology evolution system, where Scarlet is applied to retrieve relations between existing and newly added concepts in the evolving ontology. Aleksovski et al. [6] use an idea similar to Scarlet. They extract relations between terms by looking for relations between their anchored concepts in background knowledge. That background knowledge is a rich domain ontology, and finding relations means using a reasoning service to exploit the structure of the background knowledge ontology. This approach depends on the availability of a suitable, i.e. large and rich, domain ontology appropriate for the task at hand. The goal of the DBpedia Relationship Finder (RF) of Lehmann et al. [102] is to provide a user interface to explore the DBpedia dataset by giving a way to find connections between different objects. RF uses structured data, that is RDF triples, from the DBpedia infoboxes managed by a triple store and lets users query the data by entering two objects which are described by Wikipedia articles. It yields a number of labeled connections between the two input objects including all the intermediary objects connecting the two. A path from Object1 to Object2 therefore typically includes a number of different relation (property) labels. Parameters such as maximum number of results, maximum distance and a blacklist of objects or properties which are not allowed in the connection help to fine-tune the query. The method that has been successfully applied to DBpedia is also applicable for other RDF graphs. In a preprocessing step the RF detected subgraphs in the DBpedia dataset, and determined that the DBpedia graph is very dense (almost all objects have a distance from five to nine from a random start object). If adopted in the learning of non-taxonomic relations, the approach has some shortcomings: Firstly, the objects and relations are not domain-specific, all DBpedia data is included. Secondly, as the system returns a number of paths between two objects, and those paths each include a number of intermediary 9http://watson.kmi.open.ac.uk/WatsonWUI 10 http://watson.kmi.open.ac.uk/editor_plugins.html 11 http://www.neon-toolkit.org 12 http://protege.stanford.edu 4.4. WEBLYZARD ONTOLOGY LEARNING SYSTEM 125 Collection of New Domain Concepts to Build a Semantic Network The current architecture uses three modules to gather evidence on new terms, each with different functions: • Co-occurrence analysis. For every seed term the system calculates c<r occurring terms on the document and sentence level, and ranks them by significance. The system utilizes concept candidates if their significance exceeds a predefined threshold [105]. The significance calculation is based on the distribution of terms in a target and a - usually bigger -reference corpus, computed with a x2-test of significance with Yates correction for continuity. A recent version of the system integrates a module to detect significant phrases into the c<roccurrence calculations. This module inspired by Bautin and Hart [78] extracts biand tri-grams using statistical collocation information in the form of log-likelihood ratios to decide the n-grams' significance. Finally, partof-speech tags allow restricting the new terms to certain grammatical entities if needed. • 1hgger phrases, which are strongly related to Hearst patterns presented in Section 4.2.2, help to identify possible synonyms, hyponyms and hypernyms of seed terms. An sentence "Methane is a greenhouse gas" for example suggests a hyponym (subClassOf/is-a) relation between the involved terms [105]. • Prior to the detection of possible hypernyms, hyponyms and synonyms on WordNet, each of the seed terms is disambiguated, and thereby linked to a WordNet sense. Vector space similarity (see Section 4.2.3) facilitates the disambiguation task. Vectors for the seed terms include the ceroccurring terms, vectors for WordNet senses are built from relevant keywords found on WordNet. Directed labeled links connect all new terms found by the evidence sources to their respective seed concepts. This creates a semantic network, which is then transformed to a spreading activation network. The link weights are computed by functions depending on the type of evidence source and features such as significance values or term frequencies. New terms extracted with trigger phrases typically gain a low weight, as such phrases are rather unreliable. WordNet also receives a low value, as domain terminology is preferred. The weights for ceroccurring terms mainly depend on their significance values. 126 CHAPTER 4. METHODOLOGY 4.4.3 Identification of the Most Relevant Concepts Replacing the link labels with weights in the previous step creates a spreading activation (SA) network. Spreading activation is a search technique inspired by the human brains' cognitive models, where neurons fire activations to adjacent neurons [105]; for more information on artificial neuronal networks see Section 4.2.4. The SA network acts as glue to combine the terms extracted from evidence sources. In SA processing sets of pulses are sent through the network in multiple iterations -each time also checking for termination conditions. Terms that acquire high activation levels in the SA process are elected candidate terms, which are suggested to domain experts to be included in the extended ontology. 4.4.4 Concept Positioning and Taxonomy Discovery Positioning the new concepts in the extended ontology is the most challenging task. Liu et al. [105] propose a four-step process: (i) Accept semantic relations (hypernymy etc.) which can be confirmed with WordNet or by head noun analysis; (ii) identify modifiers of noun phrases which also appear on the list of activated concepts. (iii) Initiate another round of spreading activation where non-confirmed terms serve as seed terms in order to detect appropriate nodes to connect these concepts to. Subsumption analysis is then applied to determine eventual taxonomic relations. (iv) Consult domain experts for support in the concept positioning task. Subsumption analysis [157] helps to automatically generate taxonomies based on the assumption that for co-occurring terms the more general term (hypernym) should appear more frequently than the specific term [105]. For two terms x and y, x subsumes y if P(xly) 2:: 0.8 and P(ylx) < l. Figure 4.7 gives an example of an extended ontology created by wL-OE. The directed solid lines in the figure indicate taxonomic relations, dashed lines labeled m denote modifiers, r marks unnamed relations between two concepts. The concepts in ontologies learned by wL-OE are rather terms than concepts with rich semantic content. As mentioned, the systems generates conceptualizations including taxonomic relations, as well as additional unlabeled non-taxonomic relations. The present thesis addresses the task of labeling the non-taxonomic relations with a novel approach presented in Chapter 4. Building on the foundations laid in the previous sections, i.e. methods for learning semantic associations, related work, and the webLyzard ontology extension architecture, Section 4.5 introduces and formally discusses novel 4.5. A NOVEL METHOD TO DETECT RELATIONS I w in d farms I 1.0 I I ' \ ' \ I c li ma te j 1 .ol "'' \ ::... _E~ d ·~ so lar r ad iat ion 1.0 "/ , ... .. .. . .... ·· ·· ····r· ·· ··· , ,solar energy 1.0, ............... , .... ... ....... . ' ' "I l emiss io ns J 0. 51 I carbon I 1.0 I ' ' ' r ad iation 1.0 I biomas~ I 1.0 I j ren ewable so urces I 1.0 I G~~g 1.0 Figure 4. 7: The ontology after two rounds of spreading activation 127 methods for learning non-taxonomic relations which combine corpus-based techniques with knowledge inferred from data available on the Semantic Web. 4.5 A Novel Method for Detecting Non-taxonomic Relations: Conceptual and Formal Description The presented supervised approach for labeling non-taxonomic relations relies on the combination of two ingredients: vector space similarity computed for verbs co-occurring with input relations, and background knowledge about concepts involved in relations which is retrieved from online semantic data 128 CHAPTER 4. METHODOLOGY sources. The method evolved from using vectors space models only [191] to the addition of a rather simplistic way of concept type detection by querying DBpedia [194] and finally integrated an extended mechanism for concept grounding and type detection [190]. Figure 4.8 gives an overview of the relation labeling system. The input to relation labeling consists of (i) an XML/RDF representation of the OWL domain ontology containing labeled (optional) and unlabeled relations (14.•n• ), (ii) the classification meta ontology which includes the classification concepts and the relation labels and as well as definitions of the relations' domain, range, and property restrictions, (ii) a natural language domain corpus, (iv) optionally additional training relation specifications to complement the named relations defined in the domain ontology, and ( v) structured information collected on the fly from online sources. Domain Dntology R Domain D0<uments ~ Domain On1alogy Domain Corpus utrad Determine Per-Concept Domain Concepts Regular Expressions I dentify Sentences Containing two Domain Concepts (Cm, Cn) Create ( ) Yedor Space - Normalize Verbs ----- Representation utrO<I Verbs with or without Prepositions Classification Ontology Integrate Similarity and External Knowledge _ 'i" Relation Lobel ~ Suggestion l Knowledge Bose RR D~o Op~c Figure 4.8: Overview of the relation labeling architecture [190] Based on relations from the domain ontology the framework collects verbs from domain documents which co-occur with concepts (Cm, Cn) participating in the relation 14.nRegular expressions c;,,, and C~ represent the respective concept. After verb normalization (lemmatization) the system builds verb vectors from the most significant verbs per relation -according to the tfidf measure. A VSM yields similarity scores between training relations and 4.5. A NOVEL METHOD TO DETECT RELA11ONS 129 unlabeled relations Rm•n•. Finally, the semantic validation and inference process refines those similarity scores, leveraging information from external sources. The refined similarity scores are transformed to labeling suggestions for unlabeled relations. In accordance with the development history of the method and to increase clarity this section distinguishes the vector space model based component from the improvements yielded by concept type detection and ontological constraints and definitions. Section 4.5.1 elaborates the details of relation type suggestion based solely on corpus analysis, Section 4.5.2 then presents the classification ontology and components for grounding domain concepts, and finally Section 4.5.4 describes the integration of the VSM-based approach with information inferred from structured sources to refine the relation labeling results. 4.5.1 Relation Labeling Based on Vector Space Similarity Formally introduced in Section 4.2.3, the Vector Space Model (VSM) is a common information retrieval method used for tasks such as computing the similarity between a query and a set of documents in document retrieval, or to calculate similarities between documents themselves. The documents or queries have to be transformed into a vector representation, typically by some segmentation algorithm that generates a list of terms. The method then associates those terms with a term weight, which is, for example, simply the term frequency in the document. Terms combined with term weights constitute a vector, and similarity measures such as the cosine yield similarity scores between two vectors. The present work transfers the idea of similarity assessment with VSMs to the learning of non-taxonomic relations. Previous approaches extract cooccurring verbs as relation labels directly [95]. But as briefly mentioned in Section 4.3.1, it is a problem to directly map co-occurrences (e.g. co-occurring verbs) to "deep" ontological relations, as those verbs often also occur in a large semantic context. The method presented here tackles this issue by not using the verbs as labels directly, but adding the co-occurring verbs as features into a VSM, aiming at the detection of more general and already axiomatized relation types. The relation labeling method starts with collecting verbs co-occurring with the predefined relation types from domain text, and then builds verb centroids. The actual provision of label suggestions for unnamed relations is based upon a comparison of centroids for the unnamed relations with 130 CHAPTER 4. METHODOLOGY centroids from training relations. The following sections formally describe the training process and the computation of label suggestions for unnamed relations. Training Process The present description of the training process and the terminology used is adopted and extended from the work presented in Weichselbraun et al. [191] -the upper part of Figure 4.8 illustrates the order of the main tasks in the training procedure. The first step in training the relation detection component is the acquisition of a number of training examples for each relation type, typically extracted from existing ontologies or handcrafted by domain experts. Future research will incorporate bootstrapping methods to reduce the human effort involved. Each training example contains two related concepts (Cm, Cn) and links Rmn(Cm, Cn) between them. Every concept C is connected to er, which is a list of Perl-style regular expressions used to detect the concept in natural language text. The algorithm applies the regular expressions to domain-specific corpora -extracting sentences s; that "contain" relations Rmn from the training examples. Part-of-speech tags help to collect verbs occurring in those sentences. Equation 4.23 specifies the procedure more formally: Lmn = {verbs(s;) I match(C:-n,s;) A match(C~,s;) A idx(C:-n, s;) < idx(C~, s;) } ( 4.23) The Boolean function match(C, s;) takes a list of regular expressions er and a sentence s; as input, and returns true if at least one of the regular expressions matches. For a sentence to be considered, both concepts of a particular relation have to be detected in the sentence. Furthermore, the order of occurrence of the concepts is important, the function idx(cr, s;) yields the location of the matches in the sentences, and ensures that concept Cm occurs prior to the second concept Cn. As the direction of a relation is important, the component always adds relations with inverted direction to the training examples in order to detect and use the original and the inverted relation. We define those relations as Rmn(Cm,Cn) := Rnm(Cn,Cmt1• Finally, the verbs from the sentences found per training relation are extracted with the function verbs(s;). Lmn refers to the list of verbs compiled by the verbs function, which characterizes the semantic relation between Cm and Cn. Various modifications of the verbs(s;) operator are of interest regarding optimizing the method and its evaluation, those variations can be interpreted 4.5. A NOVEL METHOD TO DETECT RELATIONS 131 as generating alternative knowledge bases (KB, KB', KB" etc.) as they alter the verbs in the verb vectors and the resulting relation centroids: • Lemmatization: The operator verbs(s;) supports optional lemmatization of the verbs extracted, i.e. to convert the verbs from their inflected form to their lemma with the help of a lexicon. Example: goes • go, went • go. Lemmatization reduces data sparseness, with the drawback of potential loss of some semantic information. The application of lemmatization is the default setting. • Prepositions: A further variation concerning the verbs function is whether or not to consider prepositions directly following a verb. For example there is obviously a difference regarding the semantics of the verb look when used in look at as opposed to look after. We implemented and evaluated both methods of extraction (with and without prepositions). For evaluation results see Chapter 5. • Sliding Windows: The initial implementation of the method collected all verbs from sentences co-occurring with the relations' concepts. Especially in long sentences composed from multiple phrases, some of the verbs in phrases distant from the target concepts bear little reference to the particular unnamed relation - a way to tackle this problem is to apply word windows in the extraction process. We experimented with verb windows of various size (5 or 7 words). The initial version of the VSM [191, 194] simply used the frequency of verbs co-occurring with the particular relation as features for building the vectors. Observations on the data set and similarity scores between relations revealed that this favors relations with bigger vectors, i.e. relations that often appear in the corpus text, as such relations include a large subset of verbs occurring in common English language. In order to tackle this problem, the current implementation computes the most relevant verbs for each relation with a tf-idf measure, and only selects a fixed maximum number of verbs ( for example the 150 most significant verbs) for inclusion into the verb vector. We utilized a common variant of tf-idf (see Section 4.2.3) which normalizes the term frequency with the document size, i.e. the total number of terms in the document. The following Equations 4.24-4.26 define the tf-idf measure used: 132 CHAPTER 4. METHODOLOGY tf .. _ n;,j i,J - Lk nk,j . IDI idf; = log df; t f-idf;,j = t f;,j · idfi ( 4.24) (4.25) (4.26) Applying these equations to the situation at hand, tfi,j for verb i is computed as the number of times ni,j the verb occurs with a particular relation j normalized by the size of the relation, i.e. the number of all verbs Lk nk,j occurring with that relation. The logarithmic function log applied to the total number of relations IDI divided by the number of distinct relations df; that a verb i occurs with yields idf;. The first term in tf-idf favors verbs that are more frequent with specific relations, the second one verbs that appear with few relations. Example. The following example illustrates this process. Having snippets from a domain corpus and from a set of training relations, the system extracts sentences and verbs. Table 4.3 contains a few training relations, and also a numeric identifier used to refer to them subsequently. Table 4.4 gives the regular expressions for all concepts in the example relations, those regular expressions are matched against the domain corpus snippet -yielding a set of sentences associated to each relation. Table 4.5 contains the results of the verbs function on those sentences, it presents three variants regarding word window size. I ID I subject predicate object 1 co2 effectOn climate change Relations 2 noaa study global warming 3 vehicle use gasoline Table 4.3: Examples of training relations Corpus: [ ... ] (sl) reducing co2 protects us from the threat of climate change. (s2) sorting out our energy generation problem will do two things - it will halt the dumping of co2 into the environment, which will appease those who believe this co2 is causing climate change. (s3) the study, paid for by the united states national oceanic and atmospheric administmtion, describes the marshall islands as one of the "innocent victims" of global warming. (s4) 4.5. A NOVEL METHOD TO DETECT RELA11ONS I Concept-ID I Concept C 1 co2 2 climate change 3 noaa 4 global warming 5 vehicle 6 gasoline Regular Expressions er ( co2icarbon dioxide?) climate change (noaainational oceanic and atmospheric administration) global warming vehicles? (gasoline I petrol ( eum) ?) 133 Table 4.4: Concepts occurring in example relations including associated regular expressions the new study comes from researchers at the georgia institute of technology in atlanta, us. {s5) jerry mahlman, who used to be noaa's top climate model expert, said that a decade ago then-vice president al gore asked if global warming could cause more tornadoes. {s6) researchers working with toyota at berkeley will concentrate on consumer behavior, sounding out their view of plug-in hybrids before and after driving them. [ ... ] Rel-ID Sent-ID verbs(s;) all14 sliding window 71 :, sliding win. 1 sl reduce, protect protect protect cause 1 sort, do, halt s2 appease believe believe cause cause cause 2 s3 pay, describe describe describe 2 s5 use, be, say be, say ask, cause 510 Table 4.5: Sentences found per relation including extraction variants of lemmatized verbs 14Extract all verbs from the respective sentence. Ir.Extract verbs within a sliding window of 7 words. wExtract verbs within a sliding window of 5 words. 134 CHAPTER 4. METHODOLOGY Generation of Centroids The extraction of the verbs per sentence for each training relation is followed by the final task in the training process, the computation of verb centroids. Equation 4.27 calculates the centroid limn from the list of verbs Lmn· limn is the verb vector for the relation 'Rmn between the two concepts Cm, Cn. The operator vsmn yields the n verbs with the highest tf-idf significance transformed into a vector space representation. In the evaluation we experimented with n = 20 (include only the 20 most significant verbs into the vector) and with n = 150. ( 4.27) In addition to the verb centroids, the knowledge base (KB) stores mappings from concept pairs (Cm,Cn) to their relation label j in the form of a function Mmn• j· So the mapping function connects concept pairs to relation labels j. For the examples given above, the centroids for the relations with ID 1 and 2, when extracting all verbs from the sentence, are17 : appease: 0.077 ask: 0.099 believe: 0.077 be: 0.099 cause: 0.000 0.000 do: 0.077 cause: ll12 = halt: 0.077 lfa4 = describe: 0.099 protect: 0.077 pay: 0.099 reduce: 0.077 say: 0.099 sort: 0.077 use: 0.099 The values in the two vectors represent the tf-idf scores computed for this very simple case of only two training relations. The constituent for the verb reduce, for example, follows from a term frequency n;,i of 1, a "relation size" Lk nk,i of 9, a total number of relations IDI of 2 and a number of distinct relations df; of 1 where the verb occurs. The verb cause appears with all relations, leading to an idf; of 0. 17Note that verbs themselves are not included into the real vectors, only the respective significance numbers. 4.5. A NOVEL METHOD TO DETECT RELATIONS <owl:onProperty rdf:resource="#subClass0f" /> <owl: allValuesFrom rdf: resource="#0rganization" /> </owl: Restriction> </rdfs: subClassOf> </owl: Class> Concept Grounding 141 For the application of the presented restrictions in the relation label suggestion process we need to map concepts from unnamed relations to concept (meta) types from the classification ontology. We applied two strategies for grounding concepts in the current work. The first prototype relies on queries against DBpedia pages for respective resources [194], a more sophisticated successive implementation involves a reasoning-based approach on ontologies linked by the DBpedia page. Queries against DBpedia. A simple way to guess the type of a term representing a concept is to exploit the data about this term which resides directly in the corresponding DBpedia page (and eventually the Freebase resource linked in that page). For example, if a resource has the property http://dbpedia.org/ontology/birthdate, then we can infer that it is an instance of Person, as this is stated by domain restrictions for that property in the DBpedia ontology. Similarly, if a resource has the property http://dbpedia.org/property/parentagency, then it is likely to be an Organization. If Freebase reveals that something is of type base. science, we assume the resource to be an AbstractTopic. The following listing sketches the procedure applied to the detect type information for a concept with the queries against DBpedia method: 1. If a cached DBpedia data file for the concept exists, skip to step 6. 2. Check if there is a DBpedia page lexically corresponding to the concept label (term) in question, abort the procedure if there is no entry. 3. If the entry found in DBpedia is a redirect page, follow this redirect. 4. If the entry is a DBpedia disambiguation page: abort. Currently we have not yet implemented mechanisms for term disambiguation, this if part of future work. 5. Download and store a cached version of the page for easy access in upcoming calls. 142 CHAPTER 4. METHODOLOGY 6. Iterate over all predefined queries. If a query matches, return the concept type. 7. If DBpedia does not return a concept type, and there is a link to Freebase: iterate over queries defined for Freebase, and return the type found, if any. Reasoning on External Ontologies. This section describes a more sophisticated method to detect the type of concepts according to a classification ontology. The basic idea is to extract links to external ontologies ( currently: OpenCyc, DBpedia ontology) from the DBpedia page, and then apply reasoning techniques on those ontologies to determine if the resource is a subclass of a predefined grounding meta concept. Before classifying individual resources, we have to create the inferred models and to define of classification ontology mappings: • Creating the inferred models: This step involves the creation of a persistent inferred model for the external ontologies in question, i.e. a reasoner helps to infer triples which are stored together with the asserted triples in a database or triple store. • Classification ontology mappings: The system relies on mapping definitions between concepts from external ontologies and the local classification ontology, for example a mapping from the Organization concept in the DBpedia ontology to cl: Organization in the classification ontology. The OWL snippet below defines the cl: Organization concept as the union of external classes with are mapped onto it. Such mappings need to be defined for all concepts in the classification ontology. Mappings from existing classification ontologies should be reused. <owl: Class rdf: ID=" Organization"> <owl: union Of rdf: parseType="Collection "> <owl: Class rdf:about="http://sw.opencyc.org/concept/Mx4r ... " /> <owl: Class rdf:about="http://dbpedia.org/ontology/Organisation" /> </owl: unionOf> </owl: Class> After the acquisition of the DBpedia page for a concept label with the procedure described in step 1-5 for the method queries against DBpedia, the first step in the actual classification process is to collect links to external ontologies, therefore we exploit owl: sameAs and rdf: type properties occurring 4.5. A NOVEL METHOD TO DETECT RELATIONS 143 in the respective DBpedia page. The crucial element of the procedure is then to check via SPARQL queries against the inferred ontology models if the resource is a subclass of any mapping classes defined in the classification meta ontology. Figure 4.12 gives a visual impression of the results of this technique: The DBpedia resource http://dbpedia.org/resource/Scientist, which represents the domain concept "scientist", contains an owl: sameAs link into OpenCyc. It follows from the OpenCyc ontology that OpenCyc: Scientist is a subconcept of OpenCyc: Person. According to the definitions in the classification ontology, the system maps OpenCyc : Person to cl : Person. For demonstration purposes Figure 4.12 also includes a branch leading to no classification results. ------------ 9\ I http://dbpedia.org/resource/Scientist I ' - ~ ~ -7 - ~ - - - - ) rdf.type , _____ _________ -~: _: ~ ___ , owl,.-: sa_m_~-'A:...s---~ :, ?_P_e~i::~ :~~~s~~!:~~~Y~:~i~i~~ _: ( OpenCyc:Scientist) rdfs:subClassOf • , - ----- - --- - - - --- -- -- - ... : OpenCyc:ExistingObjectType ; " - - - - - - - --- ... -- .. -- .. - .. -- ... ' , " rdfs:subClassOf ~ ( OpenCyc:Researcher ) I rdfs:subClossOf 't ( OpenCyc:Person ) \ rdfs:subClassOf + --- 1 cl :Person Figure 4.12: Reasoning example for the concept label scientist Figure 4.13 includes another example of concept type detection with the help of ontological reasoning. This time the concept grounding component finally maps the concept "NOAA" to Organization. The mapping process is a little more complicated, it involves the resolution of a DBpedia redirect and also shows a longer reasoning chain. The result from concept grounding is a set of ontology fragments which ground the domain concepts in the classification meta ontology, as illustrated in the statements below: 144 CHAPTER 4. METHODOLOGY http://dbpedia.org/page/NOAA redirected to + dbpedia: Nationa I_ Oceanic_ and_ Atmospheric _Administration rdf :iype ... OpenCyc :en/USFederalGovernmentAgency ,' rdfs:suBClassOf ; I ••• , .... rdfs:subClassOf . ...... />:. . OpenCyc.:Soc,all.Jnit ' ;~---- ..... -----~-,.. ..... ~ rdfs ·subClassOf ,.. ' rdfs .subClassOf ---- r df s:subClassOf OpenCyc:USFederalGovernmentOrganization rdfs : subC lassOf ... OpenCyc:LegalGovernmentOrganization \ rdfs: subC lassOf .. ................ If rdfs:subClassOf .... -( OpenCyc:GovernmentalOrgani2ation ) \ rdfs:subClassOf .. ' OpenCyc.Locat,on '. rdfs:subClassOf rdfs:subClassOf ( OpenCyc:The_union_of_[ ... Jorganisations) rdfs:su. bCl assOf - .. --- ... __ I[ __ __ OpenCyc:lndividuai ; ' OpenCyc:TemporallyExi,,tingThing ~ ( OpenCyc:Organization ) groun°ded to ... ( ;.,;rg~ n ~a; io~ .... __ _,....,,_ ., Figure 4.13: Reasoning example for the concept label NOAA [190] <!-- information derived from reasoning -> <http://dbpedia.org/resourcejNOAA> <rdf:type rdf:resource="tcl;0rganization"/> <http://dbpedia.org/ resource/ Scientist> <rd fs : su bClassOf rdf: resource="tcl; Person"/> 4.5.3 The Knowledge Base The knowledge base (KB) for the relation detection framework emerges from the mechanisms described in this section, i.e. it contains the data generated in the various steps. The final step, the calculation of relation suggestions, is executed upon this KB. The following constituents make up the KB: 4.5. A NOVEL METHOD TO DETECT RELATIONS 145 • The list of all centroids Vm;n 1 which represent any of the relations Rm,n1• This includes the centroids for the training relations, as well as for the testing relations. • The mapping Mmn---.j between relation labels j and the relations Rm;n 1• • The classification meta ontology Oc1 and the domain ontology 0. • A set of ontology fragments { 01, 02, ••• , On} generated based on D Bpedia graph queries and with reasoning on external sources -containing formalized knowledge of the domain (Section 4.5.2). ( 4.28) 4.5.4 A Hybrid Method for Relation Labeling The final step in the presented framework is to label relations based on the information compiled within the knowledge base. As mentioned, the refined labeling suggestions build on the similarities computed by the VSM, i.e. the similarities sim(Vm•n•, Vmn) between the unlabeled relations and all the centroids for training relations from the knowledge base. The system then combines these similarity scores with domain knowledge. Equation 4.29 outlines the process: simmn = W 0 ,m•n•(Mmn •j(Cm,Cn)) · sim(Vm•n•, Vmn) j (4.29) The outcome of the multiplication of the weighting factor Wo,m•n• with the similarity score from the VSM results in an enhanced similarity value simmn between an unlabeled relation Rm•n• and a training relation 'RmnThe weighting factor Wo,m•n• applies to an unlabeled relation R;,.n and a particular relation label j. The weighting factor's purpose is to integrate domain knowledge, Equation 4.30 describes the heuristic used to compute it: 1.0 if O p= Cm• E dom(j) I\ 0 F Cn• E range(j) /\O(j(Cm•,Cn•)) 0.01 if O p= Cm• (/. dom(j) V Wo,m•n•(j) = Cn• (/. range(j) V ,O(j(Cm•,Cn• )) 0.8 if O p= Cm• E dom(j) V Cn• E range(j) 0.6 otherwise. (4.30) 146 CHAPTER 4. METHODOLOGY Equation 4.30 yields the weight Wo,m•n• by checking if the knowledge base (generated in previous steps) supports the domain and range restriction, as well as local restrictions, for the label suggestion j and combination with concepts Cm•, Cn•. We applied a set of fixed weights depending on the level of correspondence with the restrictions. Those weights were chosen in an intuitive and ad-hoc fashion and performed well in the experiments. We chose the weights independent of the evaluations, and they are therefore also applicable on other datasets and domains. Future research will optimizing the weights generally and for specific applications. If the concept grounding component successfully detects the type ( according to the classification ontology) of both concepts involved in the unlabeled relation, and if these concepts fulfill all restrictions defined for a label j (i.e., the ontology snippets ('.) imply ( F) that domain, range and property restrictions are met), then a weighting factor of 1.0 results. This means that the subject satisfies the domain restrictions, the object satisfies the range restrictions and also property restrictions are fulfilled. If the system can only detect the concept type of one of the two concepts involved in the relation, and that concept fulfills the restrictions, then the system applies a weighting factor of 0.8 in Equation 4.29. In situations where the types of both concepts are unknown, we have no additional evidence on the correctness of a candidate label. If restrictions cannot be verified, a weighting factor of 0.6 results. Finally, if the concepts are in conflict with restrictions, the system yields a factor of 0.01 -which has the effect that the suggestion will be ranked at the very end, but the original order of suggestions from the VSM is not completely lost. Table 4.8 presents an example for the computation of simmn as specified in Equation 4.29. The example compares the unlabeled relation scientist tt greenhouse effect to four training relations. The process starts with similarity scores from the VSM (sim := sim(Vm•n•, Vmn)) given in the column sim. The mapping function Mmn---->J simply yields the relation label j for concept pairs from training relations. The VSM similarity scores are adjusted by the weighting factor Wo,m•n•, which combines external domain knowledge ( concept grounding) with ontological restrictions -finally resulting into simmn· The example in Table 4.8 distinguishes four cases of success in concept grounding, which are reflected by four rows per training relation in the table. Either both concepts could be grounded, or just the subject concept or the object concept, and finally there is also a case where none of the concepts could be grounded. The symbol "-" indicates failure in the grounding process. The symbol "c" refers to concepts which conform to the restrictions, "v" marks violations of domain, range or property restrictions. 4.5. A NOVEL METHOD TO DETECT RELA11ONS 147 Cm,Cn Mmu•j ------'+ j sim constraints Wo,m•n• simmn domain range V V 0.01 0.0033 oil, fossil fuel subClassOf 0.33 C -0.8 0.264 -C 0.8 0.264 - - 0.6 0.198 NOAA, C C 1.00 0.30 climate study 0.30 C -0.8 0.240 change -C 0.8 0.240 - - 0.6 0.180 climate V V 0.01 0.0031 change, studiedBy 0.31 V - 0.01 0.0031 NOAA -V 0.01 0.0031 - - 0.6 0.186 NOAA, C C 1.00 0.29 greenhouse study 0.29 C -0.8 0.232 effect -C 0.8 0.232 --0.6 0.174 Table 4. 8: Relation label suggestion for the relation scientist ( cl: Per son) • greenhouse effect {cl:Object1'opic), the letters "c" and "v" indicate that information is "corresponding to" or "violating" ontological constraints. "-" implies that grounding was not successful for the concept The VSM yields the similarity values sim of 0.33, 0.3, 0.31, and 0.29 between the unlabeled relation scientist -+ greenhouse effect and the four training relations. The relation labels suggested by the training relations and determined with the mapping function are subClassOf, study, studiedBy and study. In case of the first training relation, with both concepts from the unlabeled relation grounded successfully, we have a weighting factor of 0.01, as the subClassOJ predicate includes local restrictions which basically state that the subject and object have to be of the same classification type. So the types Person and ObjectTopic conflict with this restriction. In the other three cases where one or both concept types are unknown we have no conflicts for subClassOJ with ontological restrictions, but a certain level of uncertainty, which results in the factors 0.8 and 0.6 respectively. The restrictions defined on the study relation are consistent with the grounding results, this leads to a factor of 1.0 when grounding was successful. The studiedBy relation, on the other hand, has a domain of { Topic, 148 CHAPTER 4. METHODOLOGY Unknown} and a range of {Person, Organization, Unknown} -so if any of the concepts can be grounded this induces a conflict. A consolidated view on the example indicates that when relying on the VSM only, the relation label subClassOf possesses the highest similarity score to the unlabeled relation scientist • greenhouse effect. But with the integration of domain knowledge in the form of concept grounding the method prefers the study relation -in the case where grounding was successful for both concepts from the unlabeled relation. The last step which finally results in an ordered list of relation label suggestions starts with sorting the candidates (which is the list of training relations) for any unnamed relation by the similarity value simmn, as computed in Equation 4.29. The algorithm then translates this candidate list into a list of relation labels j with the help of the mapping function Mmn-+j applied to the training relations 'Rmn· As already mentioned in Section 4.5.1 we experimented with using the unmodified ordered list of suggestions, and also included aggregation mechanisms, so the method suggests the labels following one of three strategies: 1. Simply select the relation labels j of relations 'Rmn with the highest similarity simmn· 2. Calculate the average similarity Sj, aggregating the similarity values simmn of training relations 'Rmn for each of the relation labels j, and then choose j according to this average score. 3. Use only the best (i.e. most similar) 30% of training relations 'Rmn for each relation label, and then aggregate into an average similarity si per relation type just as in the mechanism above. Using only the most similar 30% of training relations acknowledges that relations such as use include variations in meaning depending on the specific context - the 30% threshold is a way to limit the influence of variations other than the one used in the unlabeled relation. 4.5.5 Integration of User Feedback The integration of user feedback extends the initial knowledge base built from training relations on-the-fly. The knowledge base (KB) includes all training relations, i.e. known relations with their types from the domain ontology, and additionally relations manually compiled by domain experts as training data. The integration of user feedback component, which is optional, adds testing relations to the KB as new training data after being validated by a domain expert. Domain experts either confirm or discard the addition of 4.6. IMPLEMENTATION OF THE METHOD 149 a new relation. If confirmed, the system adds the relation Rm,n 1 and the centroid representing it Vm,n 1, as well as and its mapping Mm,n,-~j, to the KB. If the newly added relations are in conflict with the definitions from the classification meta ontology, then the architecture reports feedback to an ontology engineer who either updates the classification ontology or discards the new information. The availability of an increasing set of pre-learned centroids, and the updates on the classification ontology, help to constantly improve the performance of the method. 4.6 Implementation of the Method The method presented in Section 4.5 was implemented using the Python programming language19 . We separated the relation suggestion architecture into a few packages which represent the major components of the system, i.e. packages containing the various modules for training the system, for computing similarities between vectors, for concept grounding and modules that integrate external sources. Finally, there are packages for generating suggestions and evaluating the approach. The components are complemented by modules that provide common tools shared among the packages, such as database access, configuration handling, handling of CSV data and many others. The application makes heavy use of a database driven by the PostgreSQL20 database management system. The architecture stores almost all data, e.g. corpus definitions, training and testing relations, sentences, verb vectors, grounding results and evaluations in that database. This helps to modularize the application and to serialize tasks. However, the domain corpora are not included into the database. In the case of large text corpora, a database system has little advantage over storage in the file system. In Section 4.6.1 we shed light on the implementation of the training process, i.e. the extraction of verbs occurring with the relations' concepts, and then continue with the realization of the computation of vector space similarities in 4.6.2. Section 4.6.3 describes the modules for concept grounding, followed by a brief discussion of the code to access the Scarlet RelationFinder in 4.6.4. This section concludes with an overview over the evaluation package and related configuration settings in 4.6.5. 19 http://www.python.org 20 http://www.postgresql.org 150 Domain Spec. <<component>> Metadata Update CHAPTER 4. METHODOLOGY <<database>> <<component>> Rel-Detection StoreCorpus ~-~ , -.____J--, Postgresql-DB <<component>> StoreRelatlons <<component>> ------._--'AddRegexs Figure 4.14: Component diagram of metadata and relation specification 4.6.1 Training The first step in applying the architecture is to specify high level metadata about knowledge domains and associated text corpora to be used in the system, and also to give training relations. Figure 4.14 shows a component diagram of the involved modules. At first the user specifies a domain, which basically consists of a domain name. Every corpus is associated with a domain, corpus definitions also include metadata about corpus text files, more precisely XML-annotated natural language text and the additional file with contains the corresponding part-of-speech (POS) tags. The specification of training relations is a more complex task, which includes the automatic creation of corresponding regular expressions. Users specify training relations via CSV data files. Like corpora, training relations are associated with a domain. For every relation the system automatically generates a relation with inverted direction, for example for scientist -study -greenhouse effect it generates a relation greenhouse effect -studiedBy -scientist. For every relation the metadata upload scripts create entries in a concept table for subjects and objects in that relation. The concept table also includes the regular expressions, the application automatically generates them with the help of some heuristics which compile singular and plural forms of the terms. A domain expert can extend those regular expressions if necessaryfor large scale implementation of the architecture this will be not feasible, in this case synonyms or WordNet senses detected in earlier phases of ontology learning should be applied.