Introduction

Building and maintaining large ontologies pose several challenges to Knowledge Representation (KR) because of their size. In DL ontologies, although standard inferences help structuring the knowledge base (KB), e.g., by automatically building a concept hierarchy, they are, for example, not sufficient when it comes to (automatically) generating new concept descriptions from given ones. They also fail if the concepts are specified using different vocabularies (i.e. sets of concept names and role names) or if they are described on different levels of abstraction. Altogether it has turned out that for building and maintaining large DL KBs, besides the standard inferences, additional so-called non-standard inferences are required [27,19]. Among them, the first ones to be studied have been the Least Common Subsumer (LCS) of a set concepts [3] and the Most Specific Concept (MSC) of an individual [32,10,20,1]. Very recently, a unified framework for non-standard reasoning services in DLs has been proposed [8]. It is based on the use of second-order sentences in DLs [7] as the unifying definition model for all those constructive reasoning tasks which rely on specific optimality criteria to build up the objective concept. E.g., LCS is one of the cases considered for one such reformulation in terms of optimal solution problems.

Since [27], much work has been done in DL reasoning to support the construction and maintenance of DL KBs. This work has been more or less explicitly related to induction. E.g., the notion of LCS has subsequently been used for the bottom-up induction of Classic concept descriptions from examples [5,6]. Induction has been widely studied in Machine Learning (ML). Therefore it does not come as a surprise that the problem of finding an appropriate concept description for given concept instances, reformulated as a problem of inductive learning from examples, has been faced in ML, initially attacked by heuristic means [6,18,14] and more recently in a formal manner [2,12,13,22] by adopting the methods and the techniques of that ML approach known as Concept Learning.

In this paper, we present a formal characterization of Concept Learning in DLs which relies on recent results in KR and ML. Notably, the proposed formulation can be justified by observing that the inductive inference deals with findingor constructing -a concept. Therefore, non-standard reasoning services based on induction can be considered as constructive reasoning tasks. Starting from this assumption, and inspired by Colucci et al 's framework, Concept Learning is modeled as a second-order concept expression in DLs and reformulated in terms that allow for a construction possibly subject to some optimality criteria.

The paper is structured as follows. Section 2 is devoted to preliminaries on Concept Learning according to the ML tradition. Section 3 defines the Concept Learning problem statement in the KR context. Section 4 proposes a reformulation of Concept Learning as a constructive reasoning task in DLs. Section 5 concludes the paper with final remarks and directions of future work.

Preliminaries

Machine Learning

The goal of ML is the design and development of algorithms that allow computers to evolve behaviors based on empirical data [30]. The automation of the inductive inference plays a key role in ML algorithms, though other inferences such as abduction and analogy are also considered. The effect of applying inductive ML algorithms depends on whether the scope of induction is discrimination or characterization [28]. Discriminant induction aims at inducing hypotheses with discriminant power as required in tasks such as classification. In classification, observations to learn from are labeled as positive or negative instances of a given class. Characteristic induction is more suitable for finding regularities in a data set. This corresponds to learning from positive examples only.

Ideally, the ML task is to discover an operational description of a target function f : X → Y which maps elements in the instance space X to the values of a set Y . The target function is unknown, meaning that only a set D (the training data) of points of the form (x, f (x)) is provided. However, it may be very difficult in general to learn such a description of f perfectly. In fact, ML algorithms are often expected to acquire only some approximation f to f by searching a very large space H of possible hypotheses (the hypothesis space) which depend on the representation chosen for f (the language of hypotheses). The output approximation is the one that best fits D according to a scoring function score(f, D). It is assumed that any hypothesis h ∈ H that approximates f well w.r.t. a large set of training cases will also approximate it well for new unobserved cases. These notions have been mathematically formalized in computational learning theory within the Probably Approximately Correct (PAC) learning framework [36].

Summing up, given a hypothesis space H and a training data set D, ML algorithms are designed to find an approximation f of a target function f s.t.:

1. f ∈ H; 2. f (D) ≈ f (D); and/or 3. f = argmax f ∈H score(f, D).

It has been recently stressed that the first two requirements impose constraints on the possible hypotheses, thus defining a Constraint Satisfaction Problem (CSP), whereas the third requirement involves the optimization step, thus turning the CSP into an Optimization Problem (OP) [9]. We shall refer to the ensemble of constraints and optimization criterion as the model of the learning task. Models are almost by definition declarative and it is useful to distinguish the CSP, which is concerned with finding a solution that satisfies all the constraints in the model, from the OP, where one also must guarantee that the found solution be optimal w.r.t. the optimization function. Examples of typical CSPs in the ML context include Concept Learning for reasons that will become clearer by reading the following subsection.

Concept Learning

Concept Learning deals with inferring the general definition of a category based on members (positive examples) and nonmembers (negative examples) of this category. Here, the target is a boolean-valued function f : X → {0, 1}, i.e. a concept. When examples of the target concept are available, the resulting ML task is said supervised, otherwise it is called unsupervised. The positive examples are those instances with f (x) = 1, and negative ones are those with f (x) = 0.

In Concept Learning, the key inferential mechanism for induction is generalization as search through a partially ordered space of inductive hypotheses [29]. Hypotheses may be ordered from the most general ones to the most specific ones. We say that an instance x ∈ X satisfies a hypothesis h ∈ H if and only if h(x) = 1. Given two hypotheses h i and h j , h i is more general than or equal to h j (written h i g h j , where g denotes a generality relation) if and only if any instance satisfying h j , also satisfies h i . Note that it may not be always possible to compare two hypotheses with a generality relation: the instances satisfied by the hypotheses may intersect, and not necessarily be subsumed by one another. The relation g defines a partial order (i.e., it is reflexive, antisymmetric, and transitive) over the space of hypotheses.

A hypothesis h that correctly classifies all training examples is called consistent with these examples. For a consistent hypothesis h it holds that h(x) = f (x) for each instance x. The set of all hypotheses consistent with the training examples is called the version space with respect to H and D. Concept Learning algorithms may use the hypothesis space structure to efficiently search for relevant hypotheses. E.g., they may perform a specific-to-general search through the hypothesis space along one branch of the partial ordering, to find the most specific hypothesis consistent with the training examples. Another well known approach, candidate elimination, consists of computing the version space by an incremental computation of the sets of maximally specific and maximally general hypotheses. An important issue in Concept Learning is associated with the so-called inductive bias, i.e. the set of assumptions that the learning algorithm uses for prediction of outputs given previously unseen inputs. These assumptions represent the nature of the target function, so the learning approach implicitly makes assumptions on the correct output for unseen examples.

Inductive Logic Programming (ILP) was born at the intersection between Concept Learning and the field of Logic Programming [31]. From Concept Learning it has inherited the inferential mechanisms for induction [33]. However, a distinguishing feature of ILP with respect to other forms of Concept Learning is the use of prior knowledge of the domain of interest, called background knowledge (BK), during the search for hypotheses. Due to the roots in Logic Programming, ILP was originally concerned with Concept Learning problems where both hypotheses, observations and BK are expressed with first-order Horn rules (usually Datalog for computational reasons). E.g., Foil is a popular ILP algorithm for learning sets of Datalog rules for classification purposes [34]. It performs a greedy search in order to maximize an information gain function. Therefore, Foil implements an OP version of Concept Learning.

Over the last decade, ILP has widened its scope significantly, by considering, e.g., learning in DLs (see next section) as well as within those hybrid KR frameworks integrating DLs and first-order clausal languages [35,17,25,26].

Learning Concepts in Description Logics

Early work on the application of ML to DLs essentially focused on demonstrating the PAC-learnability for various terminological languages derived from Classic. In particular, Cohen and Hirsh investigate the CoreClassic DL proving that it is not PAC-learnable [4] as well as demonstrating the PAC-learnability of its sublanguages, such as C-Classic [5], through the bottom-up LcsLearn algorithm. It is also worth mentioning unsupervised learning methodologies for DL concept descriptions, whose prototypical example is Kluster [18], a polynomial-time algorithm for the induction of BACK terminologies. More recently, algorithms have been proposed that follow the generalization as search approach by extending the methodological apparatus of ILP to DL languages [2,11,12,21,22]. Supervised (resp., unsupervised) learning systems, such as YinYang [16] and DL-Learner [23], have been implemented. Based on a set of refinement operators borrowed from YinYang and DL-Learner, a new version of the Foil algorithm, named DL-Foil, has been proposed [13]. In DL-Foil, the information gain function takes into account the Open World Assumption (OWA) holding in DLs. Indeed, many instances may be available which cannot be ascribed to the target concept nor to its negation. This requires a different setting to ensure a special treatment of the unlabeled individuals.

The Problem Statement

In this section, the supervised Concept Learning problem in the DL setting is formally defined. For the purpose, we denote: Note that the definition given above provides the CSP version of the supervised Concept Learning problem. However, as already mentioned, Concept Learning can be regarded also as an OP. Algorithms such as DL-Foil testify the existence of optimality criteria to be fulfilled in Concept Learning besides the conditions of completeness and consistency.

The Solution Strategy

In Def. 1, we have considered a language of hypotheses DL H that allows for the generation of concept definitions in any DL. These definitions can be organized according to the concept subsumption relationship . Since induces a quasi-order (i.e., a reflexive and transitive relation) on DL H [2,11], the problem stated in Def. 1 can be cast as the search for a correct (i.e., complete and consistent) concept definition in (DL H , ) according to the generalization as search approach in Mitchell's vision. In such a setting, one can define suitable techniques (called refinement operators) to traverse (DL H , ) either top-down or bottom-up.

Definition 2 (Refinement operator in DLs). Given a quasi-ordered search space (DL H , )

a downward refinement operator is a mapping ρ :

DL H → 2 DL H such that ∀C ∈ DL H ρ(C) ⊆ {D ∈ DL H | D C} -an upward refinement operator is a mapping δ : DL H → 2 DL H such that ∀C ∈ DL H δ(C) ⊆ {D ∈ DL H | C D}

Definition 3 (Refinement chain in DLs). Given a downward (resp., upward) refinement operator ρ (resp., δ) for a quasi-ordered search space (DL H , ), a refinement chain from C ∈ DL H to D ∈ DL H is a sequence

C = C 0 , C 1 , . . . , C n = D such that C i ∈ ρ(C i−1 ) (resp., C i ∈ δ(C i−1 )) for every 1 ≤ i ≤ n.

Note that, given (DL, ), there is an infinite number of generalizations and specializations. Usually one tries to define refinement operators that can traverse efficiently throughout the hypothesis space in pursuit of one of the correct definitions (w.r.t. the examples that have been provided). The corresponding notions for upward refinement operators are defined dually.

Designing a refinement operator needs to make decisions on which properties are most useful in practice regarding the underlying learning algorithm. Considering the properties reported in Def. 4, it has been shown that the most feasible property combination for Concept Learning in expressive DLs such as ALC is {weakly complete, complete, proper} [21]. Only for less expressive DLs like EL, ideal, i.e. complete, proper and finite, operators exist [24].

Concept Learning as Constructive Reasoning in DLs

In this section, we formally characterize Concept Learning in DLs by emphasizing the constructive nature of the inductive inference.

Second-order Concept Expressions

We assume to start from the syntax of any Description Logic DL where N c , N r , and N o are the alphabet of concept names, role names and individual names, respectively. In order to write second-order formulas, we introduce a set N x = X 0 , X 1 , X 2 , ... of concept variables, which we can quantify over. We denote by DL X the language of concept terms obtained from DL by adding N x .

Definition 5 (Concept term).

A concept term in DL X is a concept formed according to the specific syntax rules of DL augmented with the additional rule C −→ X for X ∈ N x .

Since we are not interested in second-order DLs as themselves, we restrict our language to particular existential second-order formulas of interest to this paper. In particular, we allow formulas involving an ABox. By doing so, we can easily model the computation of, e.g., the MSC, which was left out as future work in Colucci et al.'s framework. This paves the way to the modeling of Concept Learning as shown in the next subsection.

Definition 6 (Concept expression). Let a 1 , . . . , a m ∈ DL be individuals, C 1 , . . . , C m , D 1 , . . . , D m ∈ DL X be concept terms containing concept variables X 0 , X 1 , . . . , X n . A concept expression Γ in DL X is a conjunction (C 1 D 1 ) ∧ . . . ∧ (C l D l ) ∧ (C l+1 D l+1 ) ∧ . . . ∧ (C m D m )∧ (a 1 : D 1 ) ∧ . . . ∧ (a l : D l ) ∧ (a l+1 : ¬D l+1 ) ∧ . . . ∧ (a m : ¬D m )(1)

of (negated or not) concept subsumptions and concept assertions with 1 ≤ l ≤ m.

We use General Semantics, also called Henkin semantics, for interpreting concept variables [15]. In such a semantics, variables denoting unary predicates can be interpreted only by some subsets among all the ones in the powerset of the domain 2 ∆ I -instead, in Standard Semantics a concept variable could be interpreted as any subset of ∆ I . Adapting General Semantics to our problem, the structure we consider is exactly the sets interpreting concepts in DL. That is, the interpretation X I of a concept variable X ∈ DL X must coincide with the interpretation E I of some concept E ∈ DL. The interpretations we refer to in the following definition are of this kind.

Definition 7 (Satisfiability).

A concept expression Γ of the form (1) is satisfiable in DL iff there exist n + 1 concepts E 0 , . . . , E n ∈ DL such that, extending the semantics of DL for each interpretation I, with: (X i ) I = (E i ) I for i = 0, . . . , n, it holds that 1. for each j = 1, . . . , l, and every interpretation I, (C j ) I ⊆ (D j ) I and (a j ) I ∈ (D j ) I , and 2. for each j = l + 1, . . . , m, there exists an interpretation I s.t.

(C j ) I ⊆ (D j ) I and (a j ) I ∈ (D j ) I

Otherwise, Γ is said to be unsatisfiable in DL.

Definition 8 (Solution). If a concept expression Γ of the form (1) is satisfiable in DL, then E 0 , . . . , E n is a solution for Γ . Moreover, we say that the formula

∃X 0 • • • ∃X n .Γ(2)

is true in DL if there exist at least a solution for Γ , otherwise it is false.

Modeling Concept Learning with Second-Order DLs

It has been pointed out that the constructive reasoning tasks can be divided into two main categories: tasks for which we just need to compute a concept (or a set of concepts) and those for which we need to find a concept (or a set of concepts) according to some minimality/maximality criteria [8]. In the first case, we have a set of solutions while in the second one we also have a set of suboptimal solutions to the main problem. E.g., the set of sub-optimal solutions in LCS is represented by the common subsumers. Both MSC and Concept Learning belong to this second category of constructive reasoning tasks. We remind the reader that MSC can be easily reduced to LCS for DLs that admit the one-of concept constructor. However, this reduction is not trivial for the general case.

Hereafter, first, we show how to model MSC in terms of formula ( 2). This step is to be considered as functional to the modeling of Concept Learning.

Most Specific Concept Intuitively, the MSC of individuals described in an ABox is a concept description that represents all the properties of the individuals including the concept assetions they occur in and their relationship to other individuals. Similar to the LCS, the MSC is uniquely determined up to equivalence. More precisely, the set of most specific concepts of individuals a 1 , . . . , a k ∈ DL forms an equivalence class, and if S is defined to be the set of all concept descriptions that have a 1 , . . . , a k as their instance, then this class is the least element in [S] w.r.t. a partial ordering on equivalence classes induced by the quasi ordering . Analogously to the LCS, we refer to one of its representatives by MSC(a 1 , . . . , a k ). The MSC need not exist. Three different phenomena may cause the non existence of a least element in [S], and thus, a MSC: A concept E is not the MSC of a 1 , . . . , a k iff the following formula is true in DL:

∃X.(a 1 : X) ∧ . . . ∧ (a k : X) ∧ (X E) ∧ (E X)(3)

that is, E is not the MSC if there exists a concept X which is a most specific concept, and is strictly more specific than E.

Concept Learning Following Def. 1, we assume that

Ind + C (A) = {a 1 , . . . , a m } and Ind − C (A) = {b 1 , . . . , b n }. A concept D ∈ DL H is a correct concept definition for the target concept name C w.r.t. Ind + C (A) and Ind − C (A)

iff it is a solution for the following second-order concept expression:

(C X) ∧ (X C) ∧ (a 1 : X) ∧ . . . ∧ (a m : X) ∧ (b 1 : ¬X) ∧ . . . ∧ (b n : ¬X) (4)

The CSP version of the task is therefore modeled with the following formula.

∃X.(CX)∧(X C)∧(a 1 : X)∧. . .∧(a m : X)∧(b 1 : ¬X)∧. . .∧(b n : ¬X) (5)

A simple OP version of the task could be modeled with the formula:

∃X.(C X) ∧ (X C) ∧ (X E) ∧ (E X)∧ (a 1 : X) ∧ . . . ∧ (a m : X) ∧ (b 1 : ¬X) ∧ . . . ∧ (b n : ¬X)(6)

which asks for solutions that are compliant with a minimality criterion involving concept subsumption checks. Therefore, a concept E ∈ DL H is not a correct concept definition for C w.r.t. Ind + C (A) and Ind − C (A) if there exists a concept X which is a most specific concept, and is strictly more specific than E.

Conclusions

In this paper, we have provided a formal characterization of Concept Learning in DLs according to a declarative modeling language which abstracts from the specific algorithms used to solve the task. To this purpose, we have defined a fragment of second-order logic under the general semantics which allows to express formulas involving concept assertions from an ABox. One such fragment enables us to cover the general case of MSC as well. Also, as a minor contribution, we have suggested that the generalization as search approach to Concept Learning in Mitchell's vision is just that unifying framework necessary for accompanying the declarative modeling language proposed in this paper with a way of computing solutions to the problems declaratively modeled with this language. More precisely, the computational method we refer to in this paper is based on the iterative application of suitable refinement operators. Since many refinement operators for DLs are already available in the literature, the method can be designed such that it can be instantiated with a refinement operator specifically defined for the DL in hand.

The preliminary results reported in this paper open a promising direction of research at the intersection of KR and ML. For this research we have taken inspiration from recent results in both areas. On one hand, Colucci et al.'s work provides a procedure which combines Tableaux calculi for DLs with rules for the substitution of concept variables in second-order concept expressions [8]. On the other hand, De Raedt et al.'s work shows that off-the-shelf constraint programming techniques can be applied to various ML problems, once reformulated as CSPs and OPs [9]. Interestingly, both works pursue a unified view on the inferential problems of interest to the respective fields of research. This match of research efforts in the two fields has motivated the work presented in this paper which, therefore, moves a step towards bridging the gap between KR and ML in areas such as the maintenance of KBs where the two fields have already produced interesting results though mostly indipendently from each other. New questions and challenges are raised by the cross-fertilization of these results. In the future, we intend to investigate how to express optimality criteria such as the information gain function within the second-order concept expressions and how the generalization as search approach can be effectively integrated with second-order calculus.