Concept addition, an ontology evolution's edit operation, includes adding taxonomic (hierarchical structure) and non-taxonomic (concept properties) relations. Generating concept properties requires information extraction from various sources, such as WordNet. Other than semantic similarities generated by WordNet, self-information generated from existing non-taxonomic relations has aided non-taxonomic relation addition to ontologies. Evaluation is based on using an ontology as gold standard and detaching and reattaching the nodes. Non-taxonomic relation generation without accessing an enormous amount of information has proven to be quite di cult; the results displayed in this work are an indication of this di culty.
Ontology is commonly de ned as a formal, explicit speci cation of a shared
conceptualisation [
Changing an ontology involves both changing the concepts and the relations.
Ontology relations have been divided into two categories: taxonomic relations
such as subClassOf and disjointWith in OWL [
A fundamental design operation for having a successful ontology evolution
application includes concept addition [
The de nition of an ontology in this paper is a set C of concepts and a set of
relations R1; : : : ; Rn, Ri C C. Since multiple relations with di erent labels
are allowed to exist in ontologies, labelled graphs also known as multigraphs
(G = (V; E1; : : : ; En)) with the set of vertices V () C and a set of edges
Ei () Ri are a logical choice of representing them. A graph with the stated
characteristics is called an ontology graph and is able to cover all important
structural OWL ontology features including individuals, classes, relations,
object properties, datatype properties, and restrictions [
A successful ontology change application must be able to detect what needs
to be changed, gather su cient information about the element that needs to
be changed, and nally decide how to implement change. Extracting relevant
and su cient information is crucial. In this work, WordNet [
This work has generated semantic similarities from Wikipedia as well.
Although many have mentioned that Wikipedia is much richer and a far better
source [
Ontology development is highly dependent on ontology experts, and domain experts. The perception of an expert about a correct or an incorrect relation may di er from another expert. This issue has contributed to the complexity of ontology development and update. Nonetheless, this work proposes that when adding a non-taxonomic relation, provided that the consistency of the ontology holds and the ontological statement is semantically correct, the new statement is as welcomed as any existing statement. For example when given the three concepts Student, Library, and Group, and the relation memberOf, an expert might generate Student memberOf some Library, Student memberOf some Group, or both. Absence of either of these two statements will not make the ontology incorrect but in certain circumstances it can be claimed that the ontology is less accurate. The same justi cation holds when a system is automatically generating non-taxonomic statements.
Commonly when generating non-taxonomic statements, a common approach
is to provide a set of possible properties for each concept, rank them
according to their frequencies, and nally according to some criteria select the highly
probably one. However, this work does not intend to generate new properties for
concept, but to assign an existing property to an input concept. Non-taxonomic
relations can be classi ed into two general groups: object properties (intrinsic
and extrinsic), and data-type properties [
In this work, the complete set of possible answers (Ans list) is generated, and the existing statements in the ontology (Cur list) are extracted. Ans list is a combination of an input concept I, the set of vertices V = V1; V2; : : : ; Vn, the set of edges E = E1; E2; : : : ; En, and the set of restrictions. Note that in this work only the two restrictions some and only are considered. Sample statements for the following approaches are as follows:
Existing Statement: V1 E1 some V2
Generated Statement: I E1 some V3 4.1
The members of list Ans for an input concept I, m vertices, the two restrictions, and n edges will be 4 m n which comparative to list Cur are numerous. This approach consists of a number of lters to prune Ans list according to Cur list with the aid of various semantic similarities. To be able to apply semantic similarities, a random entropy or self-information approach has been selected. Probability of the event of randomly connecting a to b by an Ri relation is de ned by P (e) = P ((a; b) 2 Ri). The prior probability therefore being P (e) = k1 , where k is the number of possible links (a; b) 2 Ri. Given some semantic similarity distances (see Section 3) s(a; b) 2 [0; 1], the posterior probability of a connection assuming a dependency between e and s(a; b) is:
P (e j s(a; b)) 6= P (e) Since s(a; b) is a similarity distance (taking values in [0; 1] with 0 corresponding to the most similar), it can be assumed that the posterior probability of connection monotonically depends (/) on 1 s(a; b):
P (e j s(a; b)) / 1 s(a; b) The monotonicity for two events e1 = (a; b) and e2 = (a; c) means the following: s(a; b) s(a; c) () 1 s(a; b) 1
s(a; c) =) P (e1 j s(a; b))
P (e2 j s(a; c))
The probability can be used to compute self-information as follows [
The rst lter is called hierarchy ltering; it is based on the patterns of the siblings of the input concept. A sibling is referred to a concept with a disjointWith relation. This work focuses on non-taxonomic patterns. For the input concept I, assuming that one of the statements in Ans is IE1onlyV1, the patterns would be IE1only and E1onlyV1. This approach only makes use of the forward patterns which in this example is E1onlyV1. Any member of the Ans list which does not contain the same pattern as one of the members of Cur list will be excluded from Ans. Also, if the input concept I and the rst concept of a member of Cur list do not have the same parent, the statement will be excluded from Ans. Presuming both the pattern and the parent is matched, when the success rate of comparing the generated statement with all the members of Cur list is more than 50%, the statement will still remain in Ans, otherwise dropped. At this stage, only the statements with the patterns similar to the existing nontaxonomic statements remain.
From this point onwards, Equation 1 will aid the pruning process. For the second lter Q1 = h(I; E1), Q2 = h(V3; E1), Q3 = h(V2; E1), and Q4 = h(V1; E1) are generated. The goal of this lter is to investigate Q1 + Q2 Q3 + Q4 2 [0:1]; if in more than half the occurrences this function holds, then the generated statement will be accepted; otherwise rejected. The aim is for the self-information of the generated statement to be less than or equal to the self-information of the current statements.
For the third lter Q5 = h(I; V1) and Q6 = h(V2; V3) are calculated. This lter will examine that in more than half the occurrences Q5 Q6 2 [0; 1] holds.
The forth lter will generate Q7 = h(I; V2) and Q8 = h(V1; V3); the relation Q7 Q8 2 [0; 1] must hold in more than half the occurrences for the generated statement to be accepted.
The last lter will generate the self-information among all the members of the generated and the current statement:
Qi = h(Statement f rom Ans list; Statement f rom Cur list)
The result generated by Qi are sorted and the k most similar statements selected. Tables 1 and 2 display the results when k = 2. 4.2
The members of the Ans list have to be pruned according to the members of Cur list. A comparison between all the members of both lists is made. Providing that a statement from one of lists has the same relation and restriction (for example EK Some or EK Only) as the other list, the occurring pattern and its frequency is recorded. The list containing the patterns P at will be sorted ascending with regard to the frequencies, and the top half selected. Those statements in Ans which do not contain these patterns will be omitted from the nal answer pool. The statement V1 E1 some V2 contains two patterns; (1) E1 some V2 and (2) V1 E1 some.
The aim of this step is to prune Ans list according to the patterns in Cur list; there is a trade o to this lter, some semantically correct statements will not be validated due to the low or lack of frequencies.
Hierarchy ltering as discussed in approach (I) will lter the remaining members of the Ans list. When the siblings of the input concept contain a nontaxonomic relation which have occurred in more than 50% of the cases and this taxonomic relation is among the remaining members of the Ans list, this statement will be accepted, otherwise rejected from Ans list. 4.3
Both of the introduced approaches have the potential of producing transitive
relations, which from the consistency point of view have to be eliminated.
Inheritance through the hierarchy has to be modelled in an ontology graph. Transitive
reduction on directed graphs is the answer to this problem. Presuming there is
the possibility of representing information in the directed graph G with fewer
arcs than the current amount, then that is the solution [
For approach (II), since all the remaining members of the Ans list are selected, transitive reduction is applied after the last step. However, approach (I) is more complicated due to selecting the top k generated relations. Transitive reduction can be applied before or after the top k selection, which this work has adopted the latter. Regardless of the approach, in situations in which a child inherits a property and the algorithm identi es this transitive property, the property is dropped. 4.4
This work has adopted an evaluation mechanism based on precision and recall
measurements [
P (E0; E) = jE \ E0j jE0j
R(E0; E) = jE \ E0j
jEj F (E0; E) = 2
P (E0; E)R(E0; E)
P (E0; E) + R(E0; E)
Other than studying the e ect of a single concept addition, the e ect of adding a sequence of concepts also has to be studied. The order in which concepts a and b are added to the system has an e ect on the non-taxonomic relations generated; generally, the semantic richness of the ontology is a ected by the existing concepts and relations. This work has studied the e ect of adding two (p = 2) and ten (p = 10) concepts to the ontology graph. Due to all the input concepts being known, the average of all the possible orders have been displayed.
Approaches (I) clearly has better results than approaches (II) excluding one exception. The more frequent a pattern, the higher the probability of it being selected; also, the closer the pattern in the hierarchy, the greater the likelihood of it being the nal answer. The major di erence between the two approaches other than the F-measure is in the number of statements being selected as the nal answer. In the approach (I), the number of statements selected has a limit; as a result, fewer unmatched statements are selected. However, approach (II) has no limit on the number of generated statement, but at the same time more unmatched statements are in the nal answer pool. The reason this paper is using the expression unmatched instead of incorrect is that studying the nal results has shown that more than 50% of the unmatched statements are actually semantically and logically accurate, although, not present in the original answer pool. Nevertheless, Table (1) and 2 only display the result of correctly matched edges to the original graph. 5
One ontology evolution operation is concept addition, which implies adding a concept by taxonomic and non-taxonomic relations. Commonly for changing an ontology some external information is required. In this work WordNet as an external source for generating similarities between concepts and relations has been selected. The semantic similarities generated by WordNet, self-information produced from patterns within ontologies, and the hierarchical structure of ontologies are the basis of approaches introduced in this paper. The focus is on intrinsic properties; presuming that intrinsic properties already exist, the assumption is that an input concept is more likely to have the same intrinsic properties as its siblings. Evaluation is based on calculating the precision and recall of detaching a node from an ontology and attempting to reattach it. The results displayed in this paper are based on this evaluation technique. Due to the poor F-measures generated by the introduced approaches, an investigation into the cause of this poor performance revealed that more than 50% of the statements that were considered incorrect are actually semantically accurate. These results if generated by an ontology expert, could easily be regarded as correct.
The next step for this research is to generate more complex non-taxonomic relations, such as statements including conjunction and disjunction. Throughout the development of this work, the need for a ternary and a quaternary comparison has been visible. Such a comparison is essential for generating more meaningful ontology statements. Another future direction is to develop a source capable of ternary and quaternary comparison.