In this paper we describe a semi-automated approach for ontology learning. Exploiting an ontology-based multimodal information extraction system, the ontology learning subsystem accumulates documents that are insufficiently analysed and through clustering proposes new concepts, relations and interpretation rules to be added to the ontology.
In recent years, ontologies have become extremely popular as a means for representing machine-readable knowledge. Driven mainly by the movement towards a semantic web, which tries to attach machine-readable semantic information to all of the resources found in the “traditional” web, ontologies address the issue of representation for this semantic information. Having the infrastructure for representing knowledge, one can construct an ontology and semantically annotate all the desired web resources. Realizing the difficulty of designing the grand ontology of the world, research on the semantic web has focused on the development of domain or task-specific ontologies, which have started making their appearance in fairly large numbers. Three major approaches have been presented for acquiring domain or taskspecific ontologies: • By integrating existing ontologies. • By constructing an ontology from scratch, or by extending (populating and enriching) an existing ontology, usually based on information extracted from a domain.
• By specialising a generic ontology, in order to adapt it to a specific domain.
Acquiring domain knowledge for constructing ontologies is a resource-demanding and time-consuming task. Thus, the automated or semi-automated construction, enrichment and adaptation of ontologies, is highly desired. The process of automated or semi-automated construction, enrichment and adaptation of ontologies is known as ontology learning. Ontology learning can be decomposed into six major subtasks: • Term identification: Terms are the “symbols” that represent ontological concepts and relations, “lexicalising” them into objects of the real word. • Synonym identification: Synonyms are sets of terms, representing the same real object or event. • Concept identification: Concepts are the basic building blocks of an ontology, as they constitute the primitive elements through which the semantic model of the ontology is constructed. • Taxonomic relation identification: Relations are semantic associations holding between two ontological concepts. Taxonomic relations organise concepts into a taxonomy. • Non-taxonomic relation identification. • Rule acquisition: Rules formalise constraints over the concepts and relations of an ontology.
The work in this paper presents an approach for learning an ontology by extending an existing one with the use of information extracted from a thematic domain. Assuming an ontology-driven content analysis system able to extract domain-specific information and semantically represent it in the form of an ontology, the proposed approach identifies possible additions to the ontology, in the form of new concepts, relations and rules. The strength of this approach is that it can identify and propose possible concepts and relations even when no initial ontology exists. In other words, it can be used to construct an ontology from scratch.
This paper is organised as follows: in section 2 the semi-automated approach for ontology learning is presented. The co-operation of the learning approach with an extraction system is discussed, and the organisation of a suitable system is briefly presented. Then, a more detailed approach is presented focusing on the task of learning new concepts. Finally, section 3 presents the results of an evaluation of the proposed approach with the following sections presenting some alternative approaches and concluding the document. 2
Assuming the existence of an ontology-driven information extraction system, the proposed learning approach is able to identify new concepts, relations and rules as candidates for extending the existing ontology that drives the information extraction system. These candidate additions are formed through similarity-based clustering of the extracted information. The candidate additions are shown to a domain expert through a suitable interface, and the expert is responsible for accepting, revising or rejecting them after examining the supporting evidence.
The proposed approach operates on the results of an ontology-driven information extraction engine, which must meet some requirements: • To represent extracted information in terms of ontological concept instances. • To extract relations between instances and represent them as instances of ontological relations.
In addition, an optional but useful characteristic is the adaptability of the information extraction engine to changes in the ontology. If the ontology is enriched with a new concept/relation/rule and the extraction engine can adapt to the change and extract instances of the new concept/relation, then the proposed learning approach will attempt to improve further the ontology, following for example a bootstrapping approach: the extracted information from the information extraction engine can is used to evolve the ontology, and through the evolved ontology the extraction of information is improved. The boostrapping process can continue until no more information can be extracted from the corpus. 2.1
Such an extraction engine has been developed in the BOEMIE project. This engine
implements a modular approach
The first two levels implement ontology-driven, modality-specific information extraction, while the last one fuses the information obtained from the previous levels of analysis.
Within BOEMIE, modality-specific analysis (levels 1 and 2) is performed as a two
step process: the first step involves the identification of “primitive” concepts, as well
as instances of relations between them. “Primitive” concepts, known as “mid-level”
concepts (MLCs) in BOEMIE, are concepts whose instances can be directly identified
in corpora of a specific modality. For example, in the textual modality the name or the
age of a person is a mid-level or “primitive” concept, as instances of the concepts are
associated directly with relevant text segments. The second one semantically
interprets (with the help of reasoning rules
Once a multimedia document has been decomposed into single-modality elements and each element has been analysed and semantically interpreted separately, the various interpretations must be fused into one or more alternative explanations of the multimedia document as a whole. This process is also performed through reasoning, using rules of the domain ontology.
This extracted information is given to the ontology learning module in the form of OWL ABoxes. These ABoxes typically include instances of MLCs, relations between them, HLCs, relations between them and possibly instances of the specific MLC “unknown” (when the low-level analysis could not classify a certain object).
According to the information contained in the ABoxes, the ontology learning
system triggers either the ontology population or the ontology enrichment activity.
The former refers to the activity of adding new individuals into the ontology. The
latter refers to the extension of the ontology through the addition of new concepts and
relations. The system identifies four different evolution patterns, each of them
determining the characteristics of the ABox and defining the process to be performed
over the ontology (figure 2). In this paper, the focus is on the ontology enrichment
task. More information about the whole ontology evolution activity can be found in
In the case where the background knowledge is not sufficient to explain the extracted information from the processed documents, ontology enrichment is performed.
As explained above, ontology concepts in BOEMIE are separated into two main types, according to whether they can be identified directly in corpora (MLCs), or inferred through reasoning (HLCs). The BOEMIE ontology learning approach aims to discover both types of concepts. However, the discovery of MLCs is by its nature a modality-specific process, with significant dependencies upon the underlying information extraction system. Although the learning process is not very different from that of HLCs, it poses additional requirements to the extraction system and thus it cannot be presented in isolation from it. For this reason emphasis is given here to the discovery of high-level concepts.
The discovery of HLCs can be decomposed into the following tasks: • Concept Learning: It includes two subtasks: Object clustering, which identifies similarities between unclassified objects and clusters them into potentially new concepts and relations. Concept formation, which examines the clustered elements in order to extract common information, such as concepts, properties and relations, and use this to form a new concept. • Concept enhancement: This task is responsible for improving a candidate concept, through knowledge acquired from external knowledge sources, such as external domain ontologies or taxonomies. • Concept definition: This task presents the definitions of the candidate concepts and relations to the ontology expert. An ontology expert is expected to revise and finally approve them in order to be assimilated into the ontology. • Concept validation: This task performs consistency checking, by trying to detect possible inconsistencies caused by the addition of a new concept or relation to the ontology. • Concept assimilation: The last task is responsible for performing the required changes to the ontology, in order to incorporate the newly formed concept/relation into the ontology.
From the above staged process the first two tasks constitute the core of concept learning and the focus of this paper.
We have identified and addressed three concept learning scenarios, according to the dependency of learned concepts to existing ones:
Specialising an existing concept. This scenario corresponds to the discovery of concepts that are specializations of existing ones. For example, assuming the domain of athletics and the existence of a concept covering all jumping sports in the domain ontology, this scenario examines whether a more specific concept describing a single sport (such as high jump or pole vault) can be learned.
discovery of concepts that generalize existing ones. Continuing on the above example, if concepts representing specific sports like pole vault and high jump already exist in the ontology, this scenario examines whether similarities of these two sports can be captured and a more abstract concept such as jumping can be learned.
Learning a concept similar to an existing one. This scenario corresponds to the discovery of concepts that are similar to, but different from existing ones. An example of this learning scenario is to learn a concept for high jump, if a concept representing the sport of pole vault is already known. The difference of this scenario from the previous ones is that no assumption is made that the learned concepts have any hierarchical relations, i.e., subsume or subsumed by, existing ones. Usually the two similar concepts are sibling under the same parent concept, which may even not exist yet and need to be discovered. 2.3
The above three scenarios are modeled after three basic tree operators, namely node splitting (for specializing an existing concept), node merging (for generalizing a set of existing concepts) and creation of new nodes (for learning a concept similar to an existing one). Each scenario identified as applicable may propose a set of possible proposals, which the domain expert is expected to filter in order to guide ontology evolution.
The first scenario (specializing an existing concept) is implemented using two operators: specialize by contextual evidence, and specialize by property evidence. The former examines cases that an HLC can be separated by the presence of another concept. For instance, sports involving the use of some equipment (i.e. throwing related sports). The implementation of this operator is based on co-occurrence statistics: examining HLCs with strong co-occurrence information with nonaggregated MLCs. The second operator examines cases where an HLC can be specialized due to its property/properties. For instance, athletes can be specialized by gender. This operator is implemented based on clustering property values, using standard clustering algorithms, on property values that have a textual representation (i.e. originate from the text modality).
The second scenario (generalizing a set of existing concepts) performs two operations: the identification of concepts that are “similar” and the identification of common properties from similar concepts. The first operation measures similarity between concepts, where the similarity is defined as the mean value of similarities among all individuals of the compared concepts. Concepts whose similarity is above a certain threshold (configurable by the domain expert with a default value of 0.8) are forwarded to the second operation, where the Least Common Subsumer is calculated and proposed as a possible abstraction to the domain expert.
The third scenario (learning a concept similar to an existing one) is implemented by two operators: extend by contextual evidence and reduce by property evidence. The first operator may propose to add a property and extend the original concept. Suppose for example, that the ontology contains an HLC that denotes a person, which does not have properties related to nationality, gender or age. Provided that there are instances of gender, age and nationality extracted by the semantics extraction toolkit, this operator may propose to add such a property and extend the original concept. This is implemented based on co-occurrence statistics: HLCs with strong co-occurrence information with non-aggregated HLCs/MLCs are examined as possible additions to any HLC. The second operator examines whether a property can be removed from an existing concept definition. An example of the latter is the case that an ontology contains an HLC that describes a sport like pole vault, but does not contain an HLC for high jump. The HLC representing pole vault may suggest the presence of a horizontal bar and a pole to completely represent the sport. However, instances representing high jump events are not expected to be associated with a pole, a situation that can be identified by this operator. The implementation of this operation is based on statistical information: if more than 30% of instances do not have a value for a specific property, this property is proposed for removal from the HLC under examination. 3
For the purposes of evaluation, a single evaluation scenario has been constructed which mainly concentrates on the second learning scenario, i.e., evaluating the ability to learn a generalised concept from a set of inter-related existing ones. According to this evaluation scenario an initial ontology is constructed manually. Then the goal of learning is to reconstruct the basic organisation, i.e., the most “important” concepts, of this ontology, from manually annotated corpora. The choice of this evaluation scenario is based on data availability. Annotations about a single sport only are needed in order to assess the performance of the system in this scenario, in contrast with the other two, where a larger manually annotated corpus involving two or more sports is needed. 3.1
In order to perform the evaluation two resources are required: an ontology and corpus annotated with this ontology. For the purposes of this experiment, a small ontology has been manually constructed, covering the domain of athletics. This ontology contains only mid-level concepts and relations between MLCs. The concepts and relations contained in the ontology are shown in table 11.
As shown in the table, the ontology contains mid-level concepts acting as properties for four high-level concepts that are not present in the ontology: athlete, sport, sport round and event. In addition to these concepts, the ontology contains an extensive set of relations between these mid-level concepts. These relations connect concepts belonging to the same (absent) HLC, such as a relation between the name of an athlete and its age or performance, but also connect MLCs that “belong” to a different HLC, such as a relation between the name of an athlete and the name of an event.
Having constructed an initial ontology, the ontology was used to manually annotate a textual corpus, simulating the results of an ontology-based information extraction process driven by the ontology.
All instances of concepts found in the corpus and all possible relations between these instances were annotated, leading to the creation of an OWL ABox for each document in the corpus. The corpus contained 250 HTML web pages, from various sites belonging to official associations, like IAAF2, EAA3 and USATFF4. The thematic domain of the collected corpus refers to the sport of high jump. 3.2
The evaluation scenario seeks to reconstruct the ontology by learning new HLCs like athlete, sport or event, having as starting point instances of the mid-level concepts and the relations between them shown in table 1. This task is accomplished by exploiting similarities among instances, through clustering. Furthermore, in the concept enhancement step, the clustering results are filtered in order to form a proposal that an ontology expert should examine, possibly revise and finally approve.
Clustering is a form of machine learning and as such two questions arise when it is
used: which clustering algorithm should be used, and how the data to be clustered can
be more effectively represented in order to obtain the desired results. Regarding the
clustering algorithm the Expectation Maximisation (EM) clustering algorithm
PersonName Age Gender CountryName Performance Ranking SportsRoundName Date SportsName Date CityName StadiumName SportsEventName Date CityName CountryName
Relations personNameToAge personNameToCountryName personNameToGender personNameToPerformance, personNameToRanking performanceToRanking sportsRoundNameToDate sportsRoundNameToPerformance, sportsRoundNameToRanking sportsRoundNameToPersonName sportsNameToCity sportsNameToStadiumName sportsNameToDate sportsNameToPersonName, sportsNameToSportsRoundName sportsNameToPerformance, sportsNameToRanking sportsEventNameToCityName sportsEventNameToCountryName sportsEventNameToDate sportsEventNameToSportsName, sportsEventNameToPersonName •
The representation scheme selected as input to clustering relies on the concepts and relations of each instance. A single feature vector is created for each concept instance found in the corpus, containing the following features: • The concept of the instance. • For each binary relation that has as subject the instance, the number of times this instance is related to other instances with this relation type.
Thus, the representation scheme contains only the concept of an instance and the relations the instance participates in as subject of the relation.
The desired result of the learning process is a concept proposal, which is created by filtering the clustering results. The desired characteristics of such a concept proposal include: • •
The set of concepts the new concept “combines”.
The set of “internal” relations that are used to relate the concepts that are “combined” by the new concept.
Possibly, a set of “external” relations that relate this new concept with other “composite” – HLCs.
The filtering has been implemented as a two phase process. During the first phase, an initial concept proposal is formed by collecting all concepts and binary relations found in all vectors of a cluster. This essentially collects the concept of all individuals in the cluster, along with all relations where each individual acts as a subject. Still within the first phase, all gathered relations are examined, and all concepts that appear as a subject of a relation are added to the concept proposal. By the end of the first phase, the concept proposal contains all concepts the proposed concept groups, and the set of relations between them. Furthermore, additional relations of the proposed concept with other proposed concepts may exist. The task of the second phase is to discover and eliminate such cases. This is achieved by examining all formed concept propositions to identify concepts that participate in more than one proposal. These concepts are eliminated from all proposals that do not contain a relation where this concept appears as a subject. In case a concept has been removed from a proposal, all relations that employ this concept as subject are marked as “external” ones. Finally, concept proposals that are subsumed by another concept proposal are eliminated. 3.3
All documents in the corpus were manually annotated with instances of concepts from the ontology, resulting in an OWL ABox for each document. Then, each ABox was processed creating a feature vector for each instance in the ABox. Vectors generated from all ABoxes were merged into a single training corpus, which has been processed by the EM algorithm. 10-fold cross validation was employed to the whole training corpus to identify the number of clusters that exist in the training data. The clustering results over the training data were filtered, in order to form the proposals of the new concepts, which were manually examined by an ontology expert. The concept proposals shown in table 2 were considered correct. The same experiment was conducted with various numbers of documents constituting the training corpus, while WEKA 3.5 implementations of both the EM algorithm and 10-fold cross validation were used for performing the experiments. The obtained results are shown in table 3. Proposed Concept Athlete Performance Sport Round Sport Event
Combined “Internal” Relations Concepts
PersonName, Age, personNameToAge, Gender, personNameToCountryNa CountryName me, personNameTo\
Gender Performance, Ranking SportsRoundName, Date SportsName, Date, CityName, StadiumName SportsEventName, Date, CityName, performanceToRanking sportsRoundNameToDate sportsNameToCity, sportsNameToStadiumNam e, sportsNameToDate sportsEventNameToCityNa me, “External” Relations personNameToPerformance personNameToRanking sportsRoundNameToPerformance sportsRoundNameToRanking sportsRoundNameToPersonName sportsNameToPersonName sportsNameToSportsRoundName sportsNameToPerformance sportsNameToRanking sportsEventNameToSportsName sportsEventNameToPersonName 10 15 25 50 80 100 175 250
CountryName sportsEventNameToCountr yName, sportsEventNameToDate The evaluation results clearly show that the proposed learning approach is able to make reasonable proposals for new concepts. The concept learning approach was particularly successful in relatively small corpora, and its proposals remained reasonable in larger corpora. When the training corpus contains more than 50 documents the Performance concept cannot be recognised easily and interferes with the recognition of the other concepts. For example, training with 100 documents learns the concept Athlete and Performance combined into a single concept, denoted as (Athlete + Performance) in table 3. The reason for this failure is two fold: the small size of the concept (it has only two MLCs and a single relation) and the limited occurrences of the single relation in the corpus. The number of documents that contain instances of the performanceToRanking relation, meaning that both performance and ranking are described in the document, is about 20% of the corpus. When training with large corpora, the number of instances of this relation is much lower than the number of instances of the other six *ToRanking and *ToPerformance relations, misleading the clustering algorithm to attach the Performance and Ranking concepts to the concepts that refer to them more frequently through relations, like the athlete, sport and sportRound concepts.
Thus, the inability of the proposed approach to make accurate proposals can be attributed mostly to data sparseness and imbalanced distribution of the concepts and their relations. 4
The recent success of distributed and dynamic infrastructures for knowledge
sharing has increased the need of semi-automated or automated ontology evolution
strategies
In
The advantage of BOEMIE approach over the above methods is that it operates solely on the results of information extraction that have been augmented with the results of reasoning, as explained in the previous sections. For example, the method can construct an ontology for a different domain, given the extracted entities and relations of this new domain by the extraction engine. Also, the distinction made between “primitive” and “composite” concepts helps the information extraction process becoming more independent of the ontology structure. 5
In this paper an approach for ontology learning has been presented that is able to perform semi-automated learning of concepts. Relying on an ontology-based information extraction system, the proposed approach exploits similarities obtained through clustering from extracted data, to propose possible ontology extensions to a domain expert. Three learning scenarios have been briefly presented that can be supported by the proposed approach, one of which has been evaluated. Evaluation results have shown that the implemented system is able to perform reasonable suggestions to the ontology expert. The BOEMIE Project is funded by the 6th EU Framework Programme, under contract FP6-027538.