Databases Reference
In-Depth Information
Fig. 27.
Outline of the gen-
eral learning approach in
CELOE: One part of the
algorithm is the generation
of promising class expres-
sions taking the available
background knowledge into
account. Another part is a
heuristic measure of how
close an expression is to be-
ing a solution of the learn-
ing problem. Figure adapted
from [56].
According to Occam's razor [26] simple solutions of the learning problem are to
be preferred over more complex ones, because they are more readable. This is even
more important in the ontology engineering context, where it is essential to suggest
simple expressions to the knowledge engineer. We measure simplicity as the
length
of
an expression, which is defined in a straightforward way, namely as the sum of the
numbers of concept, role, quantifier, and connective symbols occurring in the expres-
sion. The algorithm is biased towards shorter expressions. Also note that, for simplicity
the definition of the learning problem itself does enforce coverage, but not prediction,
i.e. correct classification of objects which are added to the knowledge base in the future.
Concepts with high coverage and poor prediction are said to
overfit
the data. However,
due to the strong bias towards short expressions this problem occurs empirically rarely
in description logics [88].
Base Learning Algorithm.
Figure 27 gives a brief overview of the
CELOE
algorithm,
which follows the common “generate and test“ approach in ILP. This means that learn-
ing is seen as a search process and several class expressions are generated and tested
against a background knowledge base. Each of those class expressions is evaluated us-
ing a heuristic, which is described in the next section. A challenging part of a learning
algorithm is to decide which expressions to test. In particular, such a decision should
take the computed heuristic values and the structure of the background knowledge into
account. For CELOE, we use the approach described in [87,88] as base, where this
problem has already been analysed, implemented, and evaluated in depth. It is based on
theideaof
refinement operators
:
Definition 7 (refinement operator).
A
quasi-ordering
is a reflexive and transitive re-
lation. In a quasi-ordered space
(
S
,
)
a
downward (upward) refinement operator
ρ
is a
mapping from S to
2
S
, such that for any C
S we have that C
∈ρ
(
C
)
implies C
∈
C
C
). C
is called a
specialisation
(
generalisation
)ofC.
(C
