In the line of our investigation on inductive methods for Semantic Web reasoning, we propose an alternative way for approximate ABox reasoning based on the analogical principle of the nearestneighbors. Once neighbors of a test individual are selected, a combination rule descending from the Dempster-Shafer theory can join together the evidence provided by the neighbor individuals. We show how to exploit the procedure for determining unknown class- and role-memberships or llers for datatype properties which may be the basis for many further ABox inductive reasoning algorithms.
In the context of reasoning in the Semantic Web (SW), a growing interest is
being committed to alternative procedures extending the standard methods so
that they can deal with the various facets of uncertainty related with Web
reasoning [
The main contributions of this work regard the extension of a framework for the classi cation of individuals through a prediction procedure based on evidence theory and similarity. In particular we propose using Yager's rule of combination and exploiting the mentioned families of metrics de ned for individuals in ontologies. This allows for measuring the con rmation of the truth of candidate assertions. The prediction of the values (related to class-membership or datatype and object properties) may have plenty of applications in uncertainty reasoning with ontologies.
The remainder of the paper is organized as follows. In the next section (x2), distance measures that shall be utilized for selecting neighbor individuals are introduced. Then (x3), the basics of the Dempster-Shafer theory and a nearestneighbor procedure based on an alternative rule of combination are recalled. Hence (x4) we present the applications of the method to the problems of determining the class- or role-membership of individuals w.r.t. given query concepts / roles as well as the prediction of llers for datatype properties. Relevant related work are discussed in (x5) and we conclude (x6) proposing extensions and applications of these methods in further works. 2
Since the reasoning method to be presented in the following is intended to be
general purpose, no speci c language will be assumed in the following for
resources, concepts (classes) and their properties. It su ces to consider a generic
representation that can be mapped to some Description Logic language with the
standard model-theoretic semantics (see [
A knowledge base K = hT ; Ai comprises a TBox T and an ABox A. T is a set of axioms concerning the (partial) de nition of concepts (and roles) through class (role) expressions. A contains assertions (ground facts) concerning the world state. The set of the individuals occurring in A will be denoted with Ind(A). Each individual can be assumed to be identi ed by its own URI (it is useful in this context to make the unique names assumption ).
Similarity-based tasks, such as individual classi cation, retrieval, and
clustering require language-independent measures for individuals whose de nition
can capture semantic aspects of their occurrence in the knowledge base [
For our purposes, we need functions to assess the similarity of individuals.
However individuals do not have an explicit syntactic (or algebraic) structure
that can be compared (unless one resorts to language-speci c notions [
K j= Ci(a)
K j= :Ci(a)
otherwise
The case of i(a) = 12 corresponds to the case when a reasoner cannot give
the truth value for a certain membership query. This is due to the Open World
Assumption normally made in Semantic Web reasoning. Hence, as in the classic
probabilistic models, uncertainty may be coped with by considering a uniform
distribution over the possible cases. Further ways to approximate these values
in case of uncertainty are investigated in [
The discernibility functions related to the context w.r.t. which two input individuals are compared are de ned as follows. Given a feature concept Ci 2 C, the related discernibility function i : Ind(A) Ind(A) 7! [0; 1] is de ned as: 8(a; b) 2 Ind(A) Ind(A) i(a; b) = j i(a) i(b)j
The discernibility function i assigns 0 if the two individuals a and b have the same behavior w.r.t. Ci, that is if they are both instance of Ci or both instance of :Ci or nothing is known about this. This is because, if a and b have the same bahavior w.r.t. Ci then there are no other information for discriminating them.
Finally, a family of dissimilarity measures for individuals that is inspired to
the Minkowski's metrics can be de ned [
Ind(A) dpC(a; b) = "
X wi i(a; b)p Ci2C
1 # p
The e ect of the weights1 is to normalize w.r.t. the other features involved.
Obviously these measures are not absolute, then they should be also considered
1 A possible way for determining the wi is to assign a high value if the corresponding
feature concept re ects high information content, low value otherwise (see [
Compared to other proposed measures [
One should assume that C represents a set of (possibly redundant) features
that are able to discriminate individuals that are actually di erent. The choice
of the concepts to be included (a feature selection problem [
Evidence-Theoretic Nearest-Neighbor Prediction
In this section the basics of the theory of evidence and combination rules [
Basics of the Evidence Theory In the Dempster-Shafer theory, a frame of discernment is de ned as the set of all hypotheses in a certain domain. Particularly, in a classi cation problem it is the set of all possible classes. A basic belief assignment (BBA) is a function m that de nes a mapping m : 2 7! [0; 1] verifying: PA2 m(A) = 1. Given a certain piece of evidence, the value of the BBA for a given set A expresses a measure of belief that is committed exactly to A. The quantity m(A) pertains only to A and does not imply any additional claims about any of its subsets. If m(A) > 0, then A is called a focal element for m.
The BBA m cannot be considered a proper probability measure: it is
dened over 2 instead of and it does not require the properties of monotone
measures [
The Dempster-Shafer rule of combination [
Di erent evidence fusion rules have been proposed [
m1( ) m2( ) + c : 0
A 6= A = A = ; ^ A 6= ; This means that the con ict between the two sources of evidence is not hidden, but it is explicitly recognized as a contributor to ignorance.
Due to the associativity and commutativity of the operations involved, it is easy to prove that the resulting combination operator is associative and commutative, and admits the vacuous BBA ( unique focal set) as neutral element. 3.2
The Nearest Neighbors Procedure Let us consider the nite set of instances X and a nite set of integers V ZZ to be used as labels (which may correspond to disjoint classes or distinct attribute values). The available information is assumed to consist in a training set TrSet = f(x1; v1); : : : ; (xM ; vM )g Ind V of single-labeled instances (examples). In our case, X = Ind(A), the set of individual names occurring in the ontology.
Let xq be a new individual to be classi ed on the basis of its nearest neighbors in TrSet. Let Nk(xq) = f(xo(j); vo(j)) j j = 1; : : : ; kg be the set of the k nearest neighbors of xq in TrSet sorted by a function o( ) depending on an appropriate metric d which can be applied to ontology individuals (e.g. one of the measures in the family de ned in the previous section x2).
Each pair (xi; vi) 2 Nk(xq) constitutes a distinct item of evidence regarding the value to be predicted for xq. If xq is close to xi according to d, then one will be inclined to believe that both instances are associated to the same value, while when d(xq; xi) increases, this belief decreases and that leads to a situation of almost complete ignorance concerning the value to be predicted for xq.
Consequently, each (xi; vi) 2 Nk(xq) may induce a BBA mi over V which
can be de ned as follows [
A = fvig A = V otherwise where 2]0; 1[ is a parameter and ( ) is a decreasing function such that (0) = 1 and limd!1 (d) = 0 (e.g. (d) = exp( dn) with > 0 and n 2 IN). The values of the parameters can be determined heuristically.
Considering each training individual in Nk(xq) as an separate source of evidence, k BBAs mj are obtained. These can be pooled by means of the rule of combination leading to the aggregated BBA m that synthesizes the nal belief: (3) (4) k m = M mj = m1 j=1
mk In order to predict a value, functions Bel and Pl can be derived from m using the equations seen above, and the query individual xq is assigned the value in V that maximizes the belief or plausibility: vq = The former choice (select the hypothesis with the greatest degree of belief the most credible) corresponds to a skeptical viewpoint while the latter (select the hypothesis with the lowest degree of doubt the most plausible) is more credulous. The degree belief (or plausibility) of the predicted value provides also a way to compare the answers of an algorithm built on top of such analogical procedure. This is useful for tasks such as ranking, matchmaking, etc..
Finally, it is possible to combine the two measures Bel and Pl analogously
to necessity (Nec) and possibility (Pos) in Possibility Theory (which can be
considered a special case2 of Dempster-Shafer theory). One can de ne a single
2 Precisely, the body of evidence must contain consonant focal sets, i.e. when the set
of focal elements is a nested family [
Compute mi (Eq. 3) 3. for each v 2 V do
Compute m (Eq. 4) and derive Bel and Pl (Eqs. 1{2)
Compute the con rmation C (Eq. 5) from Bel and Pl
4. Select v 2 V that maximizes C (Eq. 6).
measure of con rmation C, ranging in [ 1; +1], by means of a simple one-to-one
transformation [
C(A) = Bel(A) + Pl(A)
1 vq = Hence, denoted with C the combination of Bel and Pl, the resulting rule for predicting the uncertain value for the test individual can be written as follows: Summing up, the procedure is as reported in Fig. 1:
It is worthwhile to note that the complexity of the method is polynomial in the number of instances in the TrSet. If this set is compact and contains very prototypical individuals with plenty of related assertions, then the resulting predictions are likely to be accurate. Another source of complexity in the computations may be the number of values in V which may yield a large number of subsets 2jV j for which BBAs are to be computed. However this depends also on the kind of problem that is to be solved (e.g. in class membership detection jV j = 2). Moreover what really matters in the number of focal sets for each BBA which may be much less than 2jV j. 4
The utility of the presented procedure when applied to ontology reasoning can be
manifold. In the following we propose its employment in the inductive prediction
of unknown values related to class-membership and datatype / object property
llers. This feature may be easily embedded in an ontology management system
in order to help the knowledge engineers elicit assertions which may be not be
derived from the knowledge base yet they can be rather made in analogy with
the others [
In the following, the symbol j in expressions like K j will denote the derivation of the assertion from the knowledge base K obtained through an alternative procedure (like the evidence nearest neighbor presented in the previous section). (5) (6) 4.1
Class-Membership
Let us suppose a (query) concept Q is given. In this case one may consider only
examples made up of individuals with a de nite class-membership leading to a
binary problem with a set of values VQ = f+1; 1g denoting, resp., membership
and non-membership w.r.t. the query concept. Alternatively, one may admit
ternary problems with some labels set to 0 to explicitly denote an inde nite
(uncertain) class-membership [
Now to predict the class-membership value vq for some individual xq w.r.t. Q, it su ces to call the procedure ENNk(xq; TrSetQ; VQ) and decide on the grounds of the returned value. Thus in a binary setting (VQ = f+1; 1g), one will either conclude that K j Q(xq) or K j :Q(xq) depending on the value that maximizes C in Eq. 6 (resp., vq = +1 or vq = 1). Moreover the value of the con rmation function which determined the returned value vq can be exploited for ranking the hits by comparing the strength of the inductive conclusions.
Adopting a ternary setting, it may turn out that the most likely value is vq = 0 resulting in an uncertain case. One may force the choice among the values of C for vq = 1 and vq = +1, e.g. when the con rmation degree exceeds a some threshold.
The inductive procedure described above can be trivially exploited for performing the retrieval of a certain concept inductively. Given a certain concept Q, it would su ce to nd all individuals a 2 Ind(A) that are such that K j Q(a). The hits could be returned ranked by the respective con rmation value C(+1). 4.2
Datatype Fillers K j In this case, let us suppose a certain (functional) datatype property P is given and the problem is to predict its value for a certain test individual a (which has to be supposed to be in its domain). The set of values VP may correspond to the (discrete and nite) range of the property or to its restriction to the observed values for the training instances: VP = fv 2 range(P ) j 9P (a; v) 2 Ag. Di erent settings may be devised allowing for some special value(s) denoting the case of a yet unobserved value(s) for that property.
The related training set will be some TrSetP domain(P ) VP , where domain(P ) Ind(A) is the set of individual names that have a known P -value in the knowledge base. Di erently from the previous problem, datatype properties generally do not have a speci c intensional de nition in the knowledge base (except for the speci cation of domain and range), hence a mere look-up in the ABox should su ce to determine the TrSet.
Now to predict the value in VP of the datatype property P for some individual a, the method requires calling the procedure with ENNk(a; TrSetP ; VP ). Thus in this setting, if vq is the value that maximizes Eq. 6 then we can write
P (a; vq). Also in this case the value of the con rmation function which determined choice of the value vq can be exploited for comparing the strength of an inductive conclusion to others.
In case of special settings with dummy values indicating unobserved values, when these are found to be the most credible among the others, a knowledge engineer should be contacted for the necessary changes to the ontology.
The inductive procedure described above can be trivially exploited for performing alternate forms of retrieval, e.g. nding all individuals with a certain value for the given property. Given a certain value v, it would su ce to nd all individuals a 2 Ind(A) that are such that K j P (a; v). Again, the hits could be returned ranked according to the respective con rmation value C(+1).
The limitation of treating only functional datatype properties may be
overcome by considering a di erent way to assign the probability mass to BBAs than
Eq. 3, including subsets of all possible values. Examples are to be constructed
accordingly (labels will be chosen in 2VP ). Alternatively, more complex frames
of discernment, e.g. 0 = 2 , so consider sets of values as possible llers of
the property. In all such settings the computation of the BBAs and descending
measures would become of course much more complex and expensive, yet clever
solutions (or approximations) proposed in the literature [
Relationships among Individuals
In principle, a very similar setting may be used in order to establish the
possibility that a certain test individual is related through some object property with
some other individual [
Since the set Ind(A) is nite (the target is not discovering relations with unseen individuals), one may want to nd all individuals that are related to a test one through some object property, say R. The problem can be decomposed into smaller ones aiming at verifying whether K j R(a; b) holds: for each b 2 Ind(A) do for each a 2 Ind(A) do
TrSet f(x; v) j x 2 Ind(A) n fag; if K j= R(x; b) then v vbR ENNk(a; TrSet; f+1; 1g) if vbR = +1 then
return K j R(a; b) else return K j :R(a; b) +1 else v 1g
Note that, in the construction of the training sets, the inference K j= R(x; b)
may turn out to be merely an ABox lookup operation for the given assertions
(when roles are not intensionally de ned in a proper RBox). Conversely, if an
RBox is available (sometimes as a subset of the TBox) the values of the label for
the training examples can be obtained through deductive reasoning
(instancechecking) or the mentioned facilities made available by advanced reasoners or
knowledge management systems [
This simple setting makes a sort of closed-world assumption in the decision of the induced assertions descending from the adoption of the binary value set and the composition of the TrSet. A more cautious setting would involve a ternary value set VR = f 1; 0; +1g which allows for an explicit treatment of those individuals a for which R(a; b) is not derivable (or just absent from the ABox). The nal decision on the induced conclusion has to consider also this new possibility (e.g. using a threshold of con rmation for accepting likely assertions). 5
The proposed method is related to those approaches devised to o er alternative ways of reasoning with ABoxes for eliciting hidden knowledge (regularities) in order to complete and populate the ontology with likely assertions even in the occurrence of incorrect parts, supposing this kind of noise is not systematic.
The tasks of ontology completion and population have often been tackled
through formal methods (such as formal concept analysis [
Similarity-based reasoning with ontologies is the primary aim of this work
which follows a number of related methods founded on dissimilarity measures for
individuals in knowledge bases expressed in Description Logics [
Similar approaches based on lazy learning have been proposed that adopt
generalized probability theories such as the Dempster-Shafer. In [
One of the most appreciated advantages of performing inductive ABox
reasoning through these methods is that they can naturally handle inconsistent
(and inherently incomplete) knowledge bases, especially when inconsistency is
not systematic. In [
In the line of our investigation of inductive methods for Semantic Web reasoning, we have proposed an alternative way for approximate ABox reasoning based on the nearest-neighbors analogical principle. Once neighbors of a test individual are selected through some distance measures, a combination rule descending from the Dempster-Shafer theory can fuse the evidence provided by the various neighbor individuals. We have shown how to exploit the procedure for assertion prediction problems such as determining unknown class- or role-memberships as well as attribute-values which may be the basis for many ABox inductive reasoning algorithms. The method is being implemented so to allow an extensive experimentation on real ontologies.
Special settings to accommodate cases of uncertain or unobserved values
are to be investigated. One promising extension of the method concerns the
possibility of considering in nite sets of values V following the studies [
As necessity and possibility measures are related to the belief measures (see
note 2 at page 32) a natural extension may be towards the possibilistic theory and
its calculus which is, in general, di erent from the Dempster-Shafer theory and
calculus. Further possible extensions concern all other monotone measures such
as the Sugeno -measures [