In the context of the Semantic Web many applications of inductive inference ultimately rely on a notion of similarity for the standard knowledge representations of the ontologies. We have tackled the problem of statistical learning with ontologies proposing a family of structural kernels for ALCN that has been integrated with support vector machines. Here we extend the de nition of the kernels to more expressive languages of the family, namely those backing OWL.
As such the kernels are designed for comparing concept descriptions. In order
to apply them to instance comparison w.r.t. real ontologies, that likely exploit
the full extent of the most expressive DL languages, (upper) approximations of
the most speci c concepts that cover the single individuals had to be computed
[
Coupling valid kernels with e cient algorithms such as the support vector
machines, many tasks based on inductive classi cation can be tackled.
Particularly, we demonstrate how to perform important inferences on semantic
knowledge bases, namely concept retrieval and query answering. These tasks are
generally grounded on merely deductive procedures which easily fail in case of
(partially) inconsistent or incomplete knowledge. The methods has been shown to
work comparably well w.r.t. standard reasoners [
Moreover, these kernels naturally induce distance measures which allow for
extensions to further metric-based learning methods such as nearest-neighbor
classi cation [
Preliminaries on Representation and Inference
The basics of the DLs will be brie y recalled. The reader may refer to the DL
handbook [
Let us consider a triple hNC ; NR; NI i made up. respectively, by a set of primitive concept names NC , to be interpreted as sets of objects in a certain domain, a set of primitive role names NR, to be interpreted as binary relationships between the mentioned objects, and a set of individual names NI for the objects themselves.
The semantics of the descriptions is de ned by an interpretation I = ( I ; I ), where I is a non-empty set, the domain of the interpretation, and I is the interpretation function that maps each individual a 2 NI to a domain object aI 2 I , each primitive concept name A 2 NC to its extension AI I and for each R 2 NR the extension is a binary relation RI I I .
Complex descriptions can be built in ALCQ using the language constructors
listed in Table 1, along with their semantics derived from the interpretation of
atomic concepts and roles [
OWL o ers further constructors that extend the expressiveness of this
language. Its DL equivalent is SHOIQ(D) [
The main inference employed with these representations is assessing whether a concept subsumes another concept based on their semantics:
sumed by D, denoted by C v D, i for every interpretation I it holds that CI DI . When C v D and D v C then they are equivalent, denoted with C D.
Note that this naturally induces a generality relationship on the space of concepts.
Generally subsumption is not assessed in isolation but rather related to the models of a system of axioms representing the background knowledge and the world state: De nition 2.2 (knowledge base). A knowledge base K = hT ; Ai contains a TBox T and an ABox A. T is the set of terminological axioms of concept descriptions C D, where C is the concept name and D is its description. A contains assertions on individuals C(a) and R(a; b).
An interpretation that satis es all its axioms is a model of the knowledge base.
Note that de ned concepts should have a unique de nition. However de ning concepts through inclusions axioms (C v D) is also generally admitted. Moreover, such de nitions are assumed to be unfoldable.
Example 2.1 (royal family). This example shows a knowledge base modeling concepts and roles related to the British royal family: T = f Male :Female,
Woman Human u Female, Man Human u Male, Mother Woman u 9hasChild.Human, Father Man u 9hasChild.Human, Parent Father t Mother, Grandmother Mother u 9hasChild.Parent, Mother-w/o-daughter Mother u 8hasChild.:Female,
Super-mother Mother u 3 hasChild.Human g A = f Woman(elisabeth), Woman(diana), Man(charles), Man(edward), Man(andrew), Mother-w/o-daughter(diana), hasChild(elisabeth, charles), hasChild(elisabeth,edward), hasChild(elisabeth, andrew), hasChild(diana, william), hasChild(charles, william) g
Note that the Open World Assumption (OWA) is made in the underlying semantics, since normally knowledge representation systems are applied in situations where one cannot assume that the knowledge in the base is complete. Although this is quite di erent from the standard settings considered in machine learning and knowledge discovery, it is convenient for the Semantic Web context where new resources (e.g. Web pages, Web services) may be continuously made available.
The basic inference services for DL knowledge bases can be viewed as entailments as they amount to verifying whether a generic relationship is a logical consequence of the knowledge bases axioms.
Typical reasoning tasks for TBoxes regards the satis ability of a concept,
subsumption, equivalence or disjointness between two concepts. For example
in the knowledge base reported in Ex. 2.1, Father is subsumed by Man and is
disjoint with Woman. These inferences can be reduced to each of them, hence
normally reasoners support only one of them. Reasoning is performed though
tableau algorithms [
Inference problems concerning ABoxes are mainly related to checking its consistency, that is, whether it has a model, especially w.r.t. those of the TBox. For example, an ABox like the one in Ex. 2.1 containing also the assertion Father(elisabeth) is not consistent.
Since we aim at crafting inductive methods that manipulate individuals, a
prototypical inference is instance checking [
The adopted open world semantics has important consequences on the way queries are answered. While the closed-world semantics identi es a database with a single model an ABox represents possibly in nitely many interpretations. Hence a reasoner might be unable to answer certain queries because it may be actually able to build models for both a positive (K [ fC(a)g) and a negative (K [ f:C(a)g) answer.
Example 2.2 (open world semantics).
Given the ABox is Ex. 2.1, while it is explicitly stated that diana is a Mother-w/odaughter, it cannot be proven for elisabeth because she may have daughters that are simply not known in the knowledge base. Analogously, elisabeth is an instance of Super-mother while this cannot be concluded for diana as only two children are known in the current knowledge base. Although these instance checks fail because of the inherent incompleteness of the knowledge state, this does not imply that the individuals belong to the negated concepts, as could be inferred in case the CWA were made.
Another related inference is retrieval which consists in querying the knowledge base to know the individuals that belong to a given concept: De nition 2.3 (retrieval). Given an knowledge base K and a concept C, nd all individuals a such that K j= C(a).
A straightforward algorithm for a retrieval query can be realized via instance checking on each individual occurring in the ABox, testing whether it is an instance of the concept.
Dually, it may be necessary to nd the (most speci c) concepts which an individual belongs to. This is called a realization problem. One especially seeks for the most speci c one (up to equivalence):
a, the most speci c concept of a w.r.t. A is the concept C, denoted MSCA(a), such that A j= C(a) and for any other concept D such that A j= D(a), it holds that C v D.
This is a typical way to lift individuals to the conceptual level [
For some languages, the MSC may not be expressed by a nite description [
Many semantically equivalent (yet syntactically di erent) descriptions can be
given for the same concept. Equivalent concepts can be reduced to a normal
form by means of rewriting rules that preserve their equivalence [
Preliminarily, some notation is necessary for naming the various nested subparts (levels) of a concept description D: { prim(D) is the set of all the primitive concepts (or their negations) at the top-level of D; { valR(D) is the1 concept in ALCQ normal form in the scope of the value restriction (if any) at the top-level of D (otherwise valR(D) = >); { exR(D) is the set of the descriptions C0 appearing in existential restrictions 9R:C0 at the top-level conjunction of D; { minR:C (D) = maxfn 2 IN j D v nR:Cg (always a nite number); { maxR:C (D) = minfn 2 IN j D v nR:Cg (if unlimited, maxR:C (D) = 1).
A normal form may be recursively de ned as follows:
normal form i C = ? or C = > or if C = C1 t t Cn with
l Ci =
P u P 2prim(Ci) R2NR:
8 l <8R:valR(Ci) u l 9R:E u
E2exR(Ci)
l h C2NC
i mR:C R:C u
9 M Ri:C R:Ci= ; where miR:C = minR:C (Ci), M Ri:C = maxR:C (Ci) and, for all R 2 NR, valR:C(Ci) and every sub-description in exR:C(Ci) are, in their turn, in ALCQ normal form.
Example 2.3 (ALCQ normal form). The concept description C (:A1 u A2) t (9R1:B1 u 8R2:(9R3:(:A3 u B2))) is in normal form, whereas the following is not: D A1 t B2 u :(A3 u 9R3:B2) t 8R2:B3 u 8R2:(A1 u B3) where Ai's and Bj 's are primitive concept names and the Rk's are role names.
This normal form can be obtained by means of repeated applications of
equivalence preserving operations, namely replacing de ned concepts with their
de nition as in the TBox and pushing the negation into the nested levels
(negation normal form). This normal form induces an AND-OR tree structure for the
concept descriptions in this language. This structure can be used for comparing
di erent concepts and asses their similarity.
1 A single one because multiple value restrictions can be gathered using the equivalence
8R:C u u 8R:Cn 8R:(C1 u u Cn). Then the nested descriptions can be
transposed in normal form using further rewriting rules (distributiveness, etc.. . . )
[
Structural Kernels for ALCQ
in ALCQ normal form:
disjunctive descriptions:
A simple way to de ne a kernel function for concept descriptions in normal form
would require to adapt a tree kernel [
The kernel function de nition should not be based only on structural elements but also (partly) on their semantics, since di erent descriptions may have similar extensions and vice-versa, especially with expressive DL languages such as ALCQ.
Normal form descriptions can be decomposed level-wise into sub-descriptions. For each level, there are three possibilities: the upper level is dominated by the disjunction (1) of concepts that, in turn, are made up of a conjunction (2) of complex or primitive (3) concepts. In the following the de nition of the ALCQ kernel is reported.
Y kId (valR(C1); valR(C2)) R2NR
Y R2NR CCij12 22 eexxRR((CC12))
X kd (Ci1; Cj2)
I R2NR C2NC
Y
Y kn((minR:C (C1); maxR:C (C1)); (minR:C (C2); maxR:C (C2)))
I numeric restrictions: if min(MC ; MD) > max(mC ; mD) kn((mC ; MC ); (mD; MD)) =
I min(MC ; MD) max(MC ; MD) max(mC ; mD) + 1 min(mC ; mD) + 1 2 We use the superscripts k for more clarity. otherwise kn((mC ; MC ); (mD; MD)) = 0.
I primitive concepts: kp (P1; P2) = kset(P1I ; P2I ) = jP1I \ P2I j
I
where kset is the kernel for set structures de ned in [
The rst kernel function (kd) computes the similarity between disjunctive descriptions as the sum of the cross-similarities between all couples of disjuncts from the top-level of either description. The term is employed to lessen the contribution coming from the similarity of the sub-descriptions (i.e. amount of indirect similarity between concepts that are related to those at this level) on the grounds of the level where they occur.
The conjunctive kernel (kc) computes the similarity between two input descriptions, distinguishing primitive concepts, those referred in value restrictions and those referred in existential restrictions. These values are multiplied re ecting the fact that all the restrictions have to be satis ed at a conjunctive level.
The similarity of the quali ed numeric restrictions is simply computed (by kn) as a measure of the overlap between the two intervals. Namely it is the ratio of the amounts of individuals in the overlapping interval and those the larger one, whose extremes are minimum and maximum. Note that some intervals may be unlimited above: max = 1. In this case we may approximate with an upper limit N greater than j I j + 1.
The similarity between primitive concepts is measured (by kp) in terms of
the intersection of their extension. Since the extension is in principle unknown,
we will epistemically approximate it recurring to the notion of retrieval (see
Def. 2.3). Making the unique names assumption on the names of the individual
occurring in the ABox A, one can consider the canonical interpretation [
Besides, the kernel can be normalized as follows: since the kernel for primitive concepts is essentially a set kernel it may be multiplied by a constant p = 1= I so that the cardinality of the intersection is weighted by the number of individuals occurring in the overall ABox. Alternatively, another choice could be parameterized on the primitive concepts of the kernel de nition P = 1=jP1I [P2I j which would weight the rate of similarity (the extension intersection) measured by the kernel with the size of the concepts measured in terms of the individuals belonging to their extensions.
Discussion. Being partially based on the concept structure and only ultimately on the extensions of the concepts at the leaves of the tree, it may be objected that the proposed kernel functions may only roughly capture the semantic similarity of the concepts. This may be well revealed by the case of input concepts that are semantically almost equivalent yet structurally di erent. However, it must be also pointed out that the rewriting process for putting the concepts in normal form tends to eliminate these di erences. More importantly, the ultimate goal for de ning a kernel is comparing individuals rather than concepts. This will be performed recurring to the most speci c concepts of the individuals w.r.t. the same ABox (see Sect. 4). Hence, it was observed that semantically similar individuals tend to share the same structures as elicited from the same source.
The validity of a kernel depends on the fact that the function is de nite
positive. Yet validity can be also proven exploiting some closure properties of the
class of kernel functions w.r.t. several operations [
Observe that the core function is the one on primitive concept extensions. It is
essentially a set kernel [
As regards the computational complexity, it is possible to show that the
kernel function can be computed in time O(jN1jjN2j) where jNij, i = 1; 2, is
the number of nodes of the concept AND-OR trees. It can computed by means
of dynamic programming. It is also worthwhile to note that Knowledge Base
Management Systems, especially those dedicated to storing instances [
It has been objected that the kernels in this familty would not work for concepts that are equivalent yet syntactically di erent. However, they are not intended for assessing a concept similarity: ultimately kernel machines employed in inductive tasks need to be applied to instances described in this representation, therefore the most important extension is towards the case of individuals.
Indeed, the kernel function can be extended to the case of individuals a; b 2 Ind(A) by taking into account the approximations of their MSCs (see Sect. 2.2). In this way, we move from a graph representation like the ABox portion containing an individual to an intensional tree-structured representation: kI (a; b) = kI (MSC (a); MSC (b))
Note that before applying the kernel functions a sort of completion of the input descriptions is necessary, substituting the de ned concepts with the concept descriptions corresponding to their de nitions, so to make explicit the relevant knowledge concerning either individual (example).
The extension of the kernel function to more expressive DL is not trivial. DLs allowing normal form concept de nitions can only be considered. Moreover, for each constructor not included in the ALCQ logic, a kernel de nition has to be provided.
Another extension for the kernel function could be made taking into account the similarity between di erent relationships in a more selective way. This would amount to considering each couple of existential and value restrictions with one element from each description (or equivalently from each related ANDOR tree) and the computing the convolution of the sub-descriptions in the restriction. As previous suggested for , this should be weighted by a measure of similarity between the roles measured on the grounds of the available semantics. We propose therefore the following weight: given two roles R; S 2 NR: RS = jRI \ SI j=j I I j.
All of these weighting factors need not to be mere constants. Another possible extension is considering them as functions of the depth of the nodes to be compared: : N 7! ]0; 1] (e.g. (n) = 1=n). In this way one may control the decay of impact of the similarity of related individuals/concepts located ad more deeply nested levels.
As suggested before, the intersection could be measured on the grounds of the relative role extensions with respect to the whole domain of individuals, as follows:
RS = jRI \ SI j
jRI [ SI j
It is also worthwhile to recall that some DLs knowledge bases contain also an
R-box [
In order to increase the applicability of precision of the structural kernels and tackle the DL languages supporting the OWL versions, they should be able to work with inverse roles and nominals. The former may be easily accommodated by considering, in the normal form and kernels, a larger set of role names NR = NR [ fS j 9R 2 NR : S = R g. The latter can be dealt with with a set kernel, as in the sub-kernel for primitive concepts. Given the set of individual names O1 and O2: ko (O1; O2) = kset(O1I ; O2I ) = jO1I \ O2I j.
I
Finally, as discussed in [
Kernel functions have been de ned for OWL descriptions which was integrated with a SVM for inducing a statistical classi er working with the complex representations. The resulting classi er could be tested on inductive retrieval and classi cation problems.
The induced classi er can be exploited for predicting or suggesting missing information about individuals, thus completing large ontologies. Speci cally, it can be used to semi-automatize the population of an ABox. Indeed, the new assertions can be suggested to the knowledge engineer that has only to validate their inclusion. This constitutes a new approach in the SW context, since the e ciency of the statistical and numerical approaches and the e ectiveness of a symbolic representation have been combined.
The derivation of distance measures from the kernel function may enable a series of further distance-based data mining techniques such as clustering and instance-based classi cation. Conversely, new kernel functions can be de ned transforming newly proposed distance functions for these representations, which are not language dependent and allow the related data mining methods to better scale w.r.t. the number of individuals in the ABox.