The limitations of deductive logic-based approaches at deriving operational knowledge from ontologies may be overcome by inductive (instancebased) methods, which are usually efficient and noise-tolerant. However the evaluation of such methods is made particularly difficult by the open-world semantics which may often cause individuals not to be deductively classified by the reasoner. In this paper an evaluation method is proposed that is suitable for comparing inductive classification methods to standard reasoners. Experimentally we show that the behavior of a nearest neighbor classifier is comparable with the one of a standard reasoner in terms of the proposed indices.
Classification for retrieving resources from a knowledge base (KB) in the context of the
Semantic Web (SW) is an important task that is performed by means of logical methods.
These may fail due to the inherent incompleteness and incoherence of the KBs caused
by their distributed nature. This has given rise to alternative methods for approximate
reasoning (see the discussion in [
The evaluation of an inductive classification procedure would essentially require the comparison of the inductive answers provided by the inductive method to the correct ones which would derive from the intended semantics of the considered KBs. However this setting is often infeasible as it would require querying the experts and knowledge engineers that built the KB.
Alternatively one may want to compare the inductive answers to those provided
by a deductive reasoner, often more efficiently and in a more robust way w.r.t. noise.
In previous works [
In order to perform experiments with evaluating an inductive classification method,
an extension of the Nearest Neighbor classification procedure (henceforth, NN) [
The paper is organized as follows. The basics of the NN procedure applied to SW representations and the similarity measures adopted are recalled in x2. The new indices for measuring the performance of inductive classifiers is presented in x3, and x4 reports the outcomes of experiments measuring the performance of the inductive procedure in terms of the new indices. Concluding remarks are reported in x5. 2
In the following, OWL-DL knowledge bases will be considered with their standard
semantics borrowed from DL languages [
Classification boils down to determining whether an individual belongs to a concept extension (instance checking). An inductive classification method should be able to provide an answer even when this may not be logically inferred. Moreover, it may also provide a measure of the likelihood of its answer.
In instance-based learning [
The k-NN algorithm approximates hC for classifying x on the grounds of the value that hC is known to assume for the training instances in Nk(x), i.e. the k closest instances to x in terms of a dissimilarity measure. The value is decided by a weighted majority voting procedure: it is simply the most voted value by the instances in Nk(x) weighted by the similarity of the neighbor individual.
The estimate of the hypothesis function for the query individual is:
k h^C (x) := argmax X wi (v; hC (xi)) v2V i=1 (1) (2) where returns 1 in case of matching arguments and 0 otherwise, and, given a dissimilarity measure d, the weights are determined by wi = 1=d(x; xi).
Note that h^C is defined extensionally: the method needs not to provide an
analytically defined function, as other inductive methods do [
To deal with the open-world semantics, the absence of information on whether a training instance x belongs to the extension of the query concept C should count as neutral (uncertain) information. Thus, assuming the alternate viewpoint, the multi-class problem is transformed into a ternary one. Hence another value set has to be adopted, namely V = f+1; 1; 0g, where the values denote, respectively, membership, nonmembership, and uncertainty, respectively.
The task can be cast as follows: given a query concept C, determine the membership of an instance x through the NN procedure (see Eq. 1) where V = f 1; 0; +1g and the hypothesis function values for the training instances are determined as follows: hC (x) = +1 if K j= C(x), hC (x) = 1 if K j= :C(x) and hC (x) = 0 otherwise.
It should be noted that the inductive inference made by the procedure shown above is not guaranteed to be deductively valid. Indeed, inductive inference naturally yields a certain degree of uncertainty. In order to measure the likelihood of the decision made by the procedure (x has a classification corresponding to the value v maximizing the argmax argument in Eq. 1), given the nearest training individuals in Nk(x) = fx1; : : : ; xkg, the quantity that determined the decision should be normalized by dividing it by the sum of such arguments over the (three) possible values: `[class(x) = vjNk(x)] =
P u2V Pk i=1 wi Pk i=1 wi (v; hC (xi)) (u; hC (xi)) Hence the likelihood of the assertion C(x) corresponds to the case when v = +1. 2.2
Various definitions of semantic similarity (or dissimilarity) measures for concept
languages have been proposed [
The new dissimilarity measures are based on the idea of comparing the semantics of the input individuals along a number of dimensions represented by a committee of concept descriptions. Indeed, on a semantic level, similar individuals should behave similarly with respect to the same concepts. Totally semantic distance measures for individuals can be defined in the context of a knowledge base. More formally, the rationale is to compare individuals on the grounds of their semantics w.r.t. a collection of concept descriptions, say F = fF1; F2; : : : ; Fmg, which stands as a group of discriminating features expressed in the OWL-DL sublanguage taken into account.
In its simple formulation, a family of distance functions for individuals inspired to
Minkowski’s norms Lp can be defined as follows [
The weight vector w may be determined by the amount of information conveyed by
each feature, which can be measured as its estimated entropy: wi = H(Fi) (as in [
Machine learning focuses on binary or multiple classification problems that can be reduced to the binary case, as normally classes are assumed to be mutually disjoint. In a representation that adopts an open-world semantics a ternary response function requires a different treatment. Adopting a response set V = f 1; 0; +1g, cases of uncertain classification may happen. In the following we assume to evaluate a set of inductive classifications IC to one of deductive classifications DC on concept C, where C(a) 2 IC iff h^C (a) = +1 and :C(a) 2 IC iff h^C (a) = 1; the same applies for DC where ^ hC = hC , i.e. it should be deductively computed by the reasoner. 3.1
Since classification can be employed to retrieving the individuals that are related to a
given query concept, it is quite straightforward to adopt the standard measures used
in IR: precision (P ), recall (R), F-measure. However this suits settings with binary
responses determined by a notion of relevance w.r.t. the query. In the SW context, a
different purpose is pursued by the semantic precision and recall measures [
As a first step, the definition of precision and recall may be generalized adopting
different measures of the overlap [
P!(S1; S2) = !(S1; S2) jS1j
R!(S1; S2) = !(S1; S2) jS2j (3) where originally these sets are made up of alignments, but we may consider them as membership axioms.
These measures should be chosen so that some properties are fulfilled : 8S1; S2 positiveness maximality boundedness (4) (5) – !(S1; S2) – !(S1; S2) – !(S1; S2) 0 min(jS1j; jS2j) jS1 \ S2j
Now considering S1 = IC and S2 = DC , the basic definition of the measures corresponds to !0 := jIC \ DC j which trivially fulfills all properties above.
In our specific setting, since the answers of the inductive classifier are to be compared to those of the reasoner, one may also check the precision and recall of the single responses v 2 V separately and then consider the (weighted) average of these precision (or recall) measures as an overall index.
P (IC ; DC ) := X wv jICv \ DCv j
jICv j v2V R(IC ; DC ) := X wv jICv \ DCv j
jDCv j v2V average precision average recall where ICv (resp. DCv ) denotes the subset of the individuals with same classification: fa 2 IC j h^C (a) = vg (resp. fa 2 DC j h^C (a) = v). The case of uniform weights wv = 1=jV j; 8v 2 V corresponds to macro-averaging over the possible values in V . Alternatively, one may consider the choice wv = jDCv j=jTSj; 8v 2 V , where T S represents an independent set of individuals employed for testing.
In [
max-correctness max-completeness definiteness positiveness maximality boundedness where j= is a shortcut for the entailment relation between the assertions in each set and Cn( ) returns the set of assertions entailed by the input set of assertions. Of course entailment w.r.t. the models of the underlying KB is considered.
Proposition 3.1. Measures P and R fulfill properties 1–6.
Proof. We will consider the uniform weight case wv = 1=jV j: 1. P (IC ; DC ) = jV1 j Pv2V jICv \ DCv j=jICv j = jV1 j Pv2V jICv j=jICv j = 1; 2. analogously; 3. Cn(IC ) = Cn(DC ) iff 8v 2 V : (ICv \ DCv ) = ICv = DCv iff
P (IC ; DC ) = 1 and R(IC ; DC ) = 1; 4. trivial; 5. trivial; 6. P (IC ; DC ) = jV1 j Pv2V jICv \ DCv j=jICv j jV1 j Pv2V jICv \ DCv j=jIC j = = jIC \ DC j=jIC j = P (IC ; DC ); analogously R(IC ; DC ) R(IC ; DC ).
An ideal semantic generalization of the precision and recall measures in Eq.3
exploits the derivation closures (see Fig. 1) in the computation of the overlaps:
Pideal(IC ; DC ) := P!0 (Cn(IC ); Cn(DC )) = jCn(IC ) \ Cn(DC )j
jCn(IC )j
Rideal(IC ; DC ) := R!0 (Cn(IC ); Cn(DC )) = jCn(IC ) \ Cn(DC )j
jCn(DC )j
However, as noted in [
Psem(IC ; DC ) := P!0 (IC ; Cn(DC )) = jIC \ Cn(DC )j jIC j Rsem(IC ; DC ) := R!0 (Cn(IC ); DC ) = jCn(IC ) \ DC j jDC j where the problem is solved since jIC j
It is easy to prove that: jTSj and jDC j jTSj.
Proposition 3.2. Measures Psem and Rsem fulfill properties 1–6.
Proof. 1. DC j= IC ) Cn(DC )
jIC j=jIC j = 1; 2. analogously; 3. Cn(IC ) = Cn(DC ) iff IC Cn(IC ) = Cn(DC ) DC iff
Psem(IC ; DC ) = jIC j=jIC j = 1 and Rsem(IC ; DC ) = jDC j=jDC j = 1; 4. trivial; 5. trivial; 6. trivial since IC Cn(IC ) and DC Cn(DC ).
IC ) Psem(IC ; DC ) = jIC \ Cn(DC )j=jIC j =
Alternative evaluation indices have been used [
Each case increases an index with a single unit (zero-one loss). This can be generalized by exploiting the likelihood measure provided by the inductive procedure in order to assign parts of the unit to each of the three possible responses. This, in turn, has an impact on the measure of the indices normally presented in terms of rates.
Specifically, comparing the inductive answers to those of a reasoner, for each inductive classification, instead of incrementing a single count, one may selectively increase more indices at the same time, using the estimated likelihood measures as in Eq. 2 (8v 2 V : `v = `[class(x) = v]): 1: increase the match count with the likelihood ` 1, increase the omission error count with `0, increase the commission error count with `+1; 0: increase the match count with the likelihood `0, increase the induction count with ` 1 + `+1; +1: increase the match count with the likelihood `+1, increase the omission error count with `0, increase the commission error count with ` 1.
The counts above can be represented in a contingency matrix M = (muv)u;v2V which gives an idea of the performance in multi-class problems. An even better evaluation can be performed by comparing M to another matrix R = (ruv)u;v2V representing the outcomes with the random classifier exploiting the row and column totals: ruv = (Pw2V muw Pw2V mwv)=N , with N = Pw;t2V mwt. The kappa statistic :=
Pv2V mvv
N Pv2V rvv
Pv2V rvv
can be employed to measure the relative improvement over the random classifier [
In order to test the NN procedure integrated with the pseudo-metric proposed in the previous sections, it was applied to a number of classification problems. To this purpose, we selected some OWL ontologies from different domains, namely: SURFACEWATER-MODEL (SWM), NEWTESTAMENTNAMES (NTN) from the Prote´ge´ library1, our Semantic Web Service Discovery dataset2 (SWSD), one generated by the Lehigh University Benchmark (LUBM), the BioPax glycolysis ontology3 (BioPax) and FINANCIAL ontology4. Tab. 1 summarizes important details concerning these ontologies.
A 10-fold cross validation was performed. The simplest version of the distance (d1F) was employed using all the concepts in the knowledge base for determining the set F. The parameter k was set to pjInd(A)j depending on the number of individuals in the ontology. The performance was evaluated comparing the unductive responses to those returned by a standard reasoner5 as a baseline.
The outcomes are reported in Fig.2. For each knowledge base, we report the average values (and the standard deviation) obtained classifying each individual against each concept in the KB using both the reasoner and the NN classifier.
It is possible to note that generally results are good especially for the smaller ontologies (in terms of number of individuals). In particular precision was good (> 90%) for all but for the SWSD and NTN ontologies for which it drops to around 80%. Namely, 1 http://protege.stanford.edu/plugins/owl/owl-library 2 https://www.uni-koblenz.de/FB4/Institutes/IFI/AGStaab/Projects/xmedia/ dl-tree.htm 3 http://www.biopax.org/Downloads/Level1v1.4/ 4 http://www.cs.put.poznan.pl/alawrynowicz/ 5 We employed PELLET v. 1.5.2. See http://pellet.owldl.com SWSD turned out to be more difficult (also in terms of recall) for two reasons: a very limited number of individuals per concept was available and the number of different concepts is larger than in other knowledge bases. For the other ontologies scores are quite high, as testified also by the F-measure values. The results in terms of recall are also more stable than those for recall as proved by the limited variance observed, whereas some concepts turned out to be quite difficult.
The reason for precision being less than recall are probably due to the open-world assumption. Indeed, in a many cases it was observed that the NN procedure deemed some individuals as relevant for the target concept while the DL reasoner was not able to assess this relevance and this was computed as a mistake while it may likely turn out to be a correct inference when judged by a human expert. Thus different indices would be needed in this case that may make explicit both the rate of inductively classified individuals and the nature of the mistakes. 4.2
Tab. 3 reports the outcomes in terms of the set-theoretic loss-function and the new indices exploiting the likelihood value provided by the NN classifier. Preliminarily, it is important to note that, in each experiment, the commission error was low or absent (except for the BioPax ontology). This means that the search procedure is generally quite accurate: it did not make critical mistakes i.e. cases when an individual is deemed as an instance of a concept while it really is an instance of a disjoint one. Also omission error and induction rates are quite low, yet they were more typically observed in the experiments with the considered ontologies.
The usage of all concepts for the set F of d1F made the measure quite accurate, which
is the reason why the procedure resulted quite conservative as regards inducing new
assertions. In many cases, it matched rather faithfully the reasoner decisions. From the IR
point of view the cases of induction are interesting because they suggest new assertions
which cannot be logically derived by using a deductive reasoner yet they might be used
to complete a knowledge base [
Other extensions of the current measures may be made exploiting the probabilistic
output and different loss-functions. Futher measures such as specificity, sparsity, fallout
could also be generalized. Moreover, the same criteria may be adopted also in the
evaluation of approximate reasoning methods [