Strategies in Combined Learning via Logic Programs.
We discuss the adoption of a three-valued setting for inductive concept learning. Distinguishing between what is true, what is false and what is unknown can be useful in situations where decisions have to be taken on the basis of scarce, ambiguous, or downright contradictory information. In a three-valued setting, we learn a definition for both the target concept and its opposite, considering positive and negative examples as instances of two disjoint classes. To this purpose, we adopt Extended Logic Programs (ELP) under a Well-Founded Semantics with explicit negation (WFSX) as the representation formalism for learning, and show how ELPs can be used to specify combinations of strategies in a declarative way also coping with contradiction and exceptions.Explicit negation is used to represent the opposite concept, while default negation is used to ensure consistency and to handle exceptions to general rules. Exceptions are represented by examples covered by the definition for a concept that belong to the training set for the opposite concept.Standard Inductive Logic Programming techniques are employed to learn the concept and its opposite. Depending on the adopted technique, we can learn the most general or the least general definition. Thus, four epistemological varieties occur, resulting from the combination of most general and least general solutions for the positive and negative concept. We discuss the factors that should be taken into account when choosing and strategically combining the generality levels for positive and negative concepts.In the paper, we also handle the issue of strategic combination of possibly contradictory learnt definitions of a predicate and its explicit negation.All in all, we show that extended logic programs under well-founded semantics with explicit negation add expressivity to learning tasks, and allow the tackling of a number of representation and strategic issues in a principled way.Our techniques have been implemented and examples run on a state-of-the-art logic programming system with tabling which implements WFSX.
Introduction
Most work on inductive concept learning considers a two-valued setting. In such a
setting, what is not entailed by the learned theory is considered false, on the basis
of the Closed World Assumption (CWA) [44]. However, in practice, it is more often
the case that we are confident about the truth or falsity of only a limited number of
facts, and are not able to draw any conclusion about the remaining ones, because
the available information is too scarce. Like it has been pointed out in [13, 10], this
is typically the case of an autonomous agent that, in an incremental way, gathers
information from its surrounding world. Such an agent needs to distinguish between
what is true, what is false and what is unknown, and therefore needs to learn within
a richer three-valued setting.
To this purpose, we adopt the class of Extended Logic Programs (ELP, for short,
in the sequel) as the representation language for learning in a three-valued setting.
ELP contains two kinds of negation: default negation plus a second form of nega-
tion, called explicit, whose combination has been recognized elsewhere as a very
expressive means of knowledge representation. The adoption of ELP allows one to
deal directly in the language with incomplete and contradictory knowledge, with
exceptions through default negation, as well as with truly negative information by
means of explicit negation [39, 2, 3]. For instance, in [2, 5, 16, 9, 32] it is shown
how ELP is applicable to such diverse domains of knowledge representation as concept
hierarchies, reasoning about actions, belief revision, counterfactuals, diagnosis,
updates and debugging.
In this work, we show, for the first time in a journal, that various approaches
and strategies can be adopted in Inductive Logic Programming (ILP, henceforth)
for learning with ELP under an extension of well-founded semantics. As in [25,
24], where answer-sets semantics is used, the learning process starts from a set of
positive and negative examples plus some background knowledge in the form of
an extended logic program. Positive and negative information in the training set
are treated equally, by learning a definition for both a positive concept p and its
(explicitly) negated concept :p. Coverage of examples is tested by adopting the
SLX interpreter for ELP under the Well-Founded Semantics with explicit negation
defined in [2, 16], and valid for its paraconsistent version [9].
negation is used in the learning process to handle exceptions to general
rules. Exceptions to a positive concept are identified from negative examples,
whereas exceptions to a negative concept are identified from positive examples.
In this work, we adopt standard ILP techniques to learn some concept and its
opposite. Depending on the technique adopted, one can learn the most general
or the least general definition for each concept. Accordingly, four epistemological
varieties occur, resulting from the mutual combination of most general and least
general solutions for the positive and negative concept. These possibilities are
expressed via ELP, and we discuss some of the factors that should be taken into
account when choosing the level of generality of each, and their combination, to
define a specific learning strategy, and how to cope with contradictions. (In the
paper, we concentrate on single predicate learning, for the sake of simplicity.)
Indeed, separately learned positive and negative concepts may conflict and, in
order to handle possible contradiction, contradictory learned rules are made defeasible
by making the learned definition for a positive concept p depend on the
default negation of the negative concept :p, and vice-versa. I.e., each definition
is introduced as an exception to the other. This way of coping with contradiction
can be even generalized for learning n disjoint classes, or modified in order to take
into account preferences among multiple learning agents or information sources (see
[28]).
The paper is organized as follows. We first motivate the use of ELP as target and
background language in section 2, and introduce the new ILP framework in section
3. We then examine, in section 4, factors to be taken into account when choosing
the level of generality of learned theories. Section 5 proposes how to combine the
learned definitions within ELP in order to avoid inconsistencies on unseen atoms
and their opposites, through the use of mutually defeating ("non-deterministic")
rules, and how to incorporate exceptions through negation by default. A description
of our algorithm for learning ELP follows next, in section 6, and the overall
system implementation in section 7. Section 8 evaluates the obtained classification
accuracy. Finally, we examine related works in section 9, and conclude.
2. Logic Programming and Epistemic Preliminaries
In this section, we first discuss the motivation for three-valuedness and two types
of negation in knowledge representation and provide basic notions of extended logic
programs and W FSX.
2.1. Three-valuedness, default and explicit negation
Artificial Intelligence (AI) needs to deal with knowledge in flux, and less than
perfect conditions, by means of more dynamic forms of logic than classical logic.
Much of this has been the focus of research in Logic Programming (LP), a field
of AI which uses logic directly as a programming language 1 , and provides specific
implementation methods and efficient working systems to do so 2 .
Horn clause notation is used to express that conclusions must be supported,
"caused", by some premises. Implication is unidirectional, i.e., not contrapositive:
"causes" do not run backwards.
Various extensions of LP have been introduced to cope with knowledge representation
issues. For instance, default negation of an atom P , "not P ", was introduced
by AI to deal with lack of information, a common situation in the real world. It
introduces non-monotonicity into knowledge representation. Indeed, conclusions
might not be solid because the rules leading to them may be defeasible. For in-
stance, we don't normally have explicit information about who is or is not the
lover of whom, though that kind of information may arrive unexpectedly. Thus we
not lover(H; L)
I.e., if we have no evidence to conclude lover(H; L) for some L given H , we can
assume it false for all L given H .
Mark that not should grant positive and negative information equal standing.
That is, we should equally be able to write:
to model instead a world where people are unfaithful by default or custom, and
where it is required to explicitly prove that someone does not take any lover before
concluding that person not unfaithful.
Since information is normally expressed positively, by dint of mental and linguistic
economics, through Closed World Assumption (CWA), the absent, non explicitly
obtainable information, is usually the negation of positive information. Which
means, when no information is available about lovers, that :lover(H; L) is true by
CWA, whereas lover(H; L) is not. Indeed, whereas the CWA is indispensable in
some contexts, viz. at airports flights not listed are assumed non-existent, in others
that is not so: though one's residence might not be listed in the phone book, it may
not be ruled out that it exists and has a phone.
These epistemologic requisites can be reconciled by reading ':' above not as
classical negation, which complies with the excluded middle provision, but as yet
a new form of negation, dubbed in Logic Programming "explicit negation" [39]
(which ignores that provision), and adopted in ELP.
This requires the need for revising assumptions and for introducing a third truth-
value, named "undefined", into the framework. In fact, when we combine, for
instance, the viewpoints of the two above worlds about faithfulness we become
confused: assuming married(H; K) for some H and K; it now appears that both
faithful(H; K) and :faithful(H; K) are contradictorily true. Indeed, since we
have no evidence for lover(H; L) nor :lover(H; L) because there simply is no information
about them, we make two simultaneous assumptions about their falsity.
But when any assumption leads to contradiction one should retract it, which in a
three-valued setting means making it undefined.
The imposition of undefinedness for lover(H; L) and :lover(H; L) can be achieved
simply, by adding to our knowledge the clauses:
:lover(H; L) / not lover(H; L)
lover(H; L) / not :lover(H; L)
thereby making faithful(H; K) and :faithful(H; K) undefined too. Given no
other information, we can now prove neither of lover(H; L) nor :lover(H; L) true,
or false. Any attempt to do it runs into a self-referential circle involving default
negation, and so the safest, skeptical, third option is to take no side in this marital
dispute, and abstain from believing either.
Even in presence of self-referential loops involving default negations, the well-founded
semantics of logic programs (WFS) assigns to the literals in the above two
clauses the truth value undefined, in its knowledge skeptical well-founded model,
but allows also for the other two, incompatible non truth-minimal, more credulous
models.
2.2. Extended Logic Programs
An extended logic program is a finite set of rules of the form:
with n  0, where L 0 is an objective literal, L are literals and each rule
stands for the sets of its ground instances. Objective literals are of the form A
or :A, where A is an atom, while a literal is either an objective literal L or its
default negation not L. :A is said the opposite literal of A (and vice versa),
not A the complementary literal of A (and vice versa).
By not fA we mean fnot A not An g where A i s are literals. By
we mean f:A g. The set of all objective literals of a
program P is called its extended Herbrand base and is represented as H E (P ). An
interpretation I of an extended program P is denoted by T [ not F , where T and
F are disjoint subsets of H E (P ). Objective literals in T are said to be true in I ,
objective literals in F are said to be false in I and those in H are said to be
undefined in I . We introduce in the language the proposition u that is undefined
in every interpretation I .
WFSX extends the well founded semantics (WFS ) [46] for normal logic programs
to the case of extended logic programs. WFSX is obtained from WFS by adding
the coherence principle relating the two forms of negation: "if L is an objective
literal and :L belongs to the model of a program, then also not L belongs to the
model ", i.e., :L ! not L.
Notice that, thanks to this principle, any interpretation I F of an
extended logic program P considered by WFSX semantics is non-contradictory,
i.e., there is no pair of objective literals A and :A of program P such that A
belongs to T and :A belongs to T [2]. The definition of WFSX is reported in


Appendix

. If an objective literal A is true in the WFSX of an ELP P we write
A.
Let us now show an example of WFSX in the case of a simple program.
Example: Consider the following extended logic program:
a / b:
A WFSX model of this program is not :b; not ag: :a is true, a is false,
:b is false (there are no rules for :b) and b is undefined. Notice that not a is in the
model since it is implied by :a via the coherence principle.
One of the most important characteristic of WFSX is that it provides a semantics
for an important class of extended logic programs: the set of non-stratified pro-
grams, i.e., the set of programs that contain recursion through default negation.
An extended logic program is stratified if its dependency graph does not contain
any cycle with an arc labelled with \Gamma. The dependency graph of a program P is
a labelled graph with a node for each predicate of P and an arc from a predicate
p to a predicate q if q appears in the body of clauses with p in the head. The arc
is labelled with appears in an objective literal in the body and with \Gamma if it
appears in a default literal.
Non-stratified programs are very useful for knowledge representation because
the WFSX semantics assigns the truth value undefined to the literals involved
in the recursive cycle through negation, as shown in section 2.1 for lover(H; L)
and :lover(H; L). In section 5 we will employ non stratified programs in order to
resolve possible contradictions.
WFSX was chosen among the other semantics for extended logic programs,
answer-sets [21] and three-valued strong negation [3], because none of the others
enjoy the property of relevance [2, 3] for non-stratified programs, i.e., they cannot
have top-down querying procedures for non-stratified programs. Instead, for WFSX
there exists a top-down proof procedure SLX [2], which is correct with respect to
the semantics.
Cumulativity is also enjoyed by WFSX, i.e., if you add a lemma then the semantics
does not change (see [2]). This property is important for speeding-up the implemen-
tation. By memorizing intermediate lemmas through tabling, the implementation
of SLX greatly improves. Answer-set semantics, however, is not cumulative for
non-stratified programs and thus cannot use tabling.
The SLX top-down procedure for WFSX relies on two independent kinds of
derivations: T-derivations, proving truth, and TU-derivations proving non-falsity,
i.e., truth or undefinedness. Shifting from one to the other is required for proving a
default literal not L: the T-derivation of not L succeeds if the TU-derivation of L
fails; the TU-derivation of not L succeeds if the T-derivation of L fails. Moreover,
the T-derivation of not L also succeeds if the T-derivation of :L succeeds, and
the TU-derivation of L fails if the T-derivation of :L succeeds (thus taking into
account the coherence principle). Given a goal G that is a conjunction of literals,
if G can be derived by SLX from an ELP P , we write P 'SLX G
The SLX procedure is amenable to a simple pre-processing implementation, by
mapping WFSX programs into WFS programs through the T-TU transformation
[8]. This transformation is linear and essentially doubles the number of program
clauses. Then, the transformed program can be executed in XSB, an efficient
logic programming system which implements (with polynomial complexity) the
WFS with tabling, and subsumes Prolog. Tabling in XSB consists in memoizing
intermediate lemmas, and in properly dealing with non-stratification according to
WFS. Tabling is important in learning, where computations are often repeated for
testing the coverage or otherwise of examples, and allows computing the WFS with
simple polynomial complexity on program size.
3. Learning in a Three-valued Setting
In real-world problems, complete information about the world is impossible to
achieve and it is necessary to reason and act on the basis of the available partial
information. In situations of incomplete knowledge, it is important to distinguish
between what is true, what is false, and what is unknown or undefined.
Such a situation occurs, for example, when an agent incrementally gathers information
from the surrounding world and has to select its own actions on the
basis of such acquired knowledge. If the agent learns in a two-valued setting, it
can encounter the problems that have been highlighted in [13]. When learning in
a specific to general way, it will learn a cautious definition for the target concept
and it will not be able to distinguish what is false from what is not yet known (see
figure 1a). Supposing the target predicate represents the allowed actions, then the
agent will not distinguish forbidden actions from actions with an outcome and this
can restrict the agent acting power. If the agent learns in a general to specific way,
instead, it will not know the difference between what is true and what is unknown
(figure 1b) and, therefore, it can try actions with an unknown outcome. Rather,
by learning in a three-valued setting, it will be able to distinguish between allowed
actions, forbidden actions, and actions with an unknown outcome (figure 1c). In
this way, the agent will know which part of the domain needs to be further explored
and will not try actions with an unknown outcome unless it is trying to expand its
knowledge.

Figure

1. (taken from [13])(a,b): two-valued setting, (c): three-valued setting
We therefore consider a new learning problem where we want to learn an ELP from
a background knowledge that is itself an ELP and from a set of positive and a set of
negative examples in the form of ground facts for the target predicates. A learning
problem for ELP's was first introduced in [25] where the notion of coverage was
defined by means of truth in the answer-set semantics. Here the problem definition
is modified to consider coverage as truth in the preferred WFSX semantics
Definition 1. [Learning Extended Logic Programs]
Given:
ffl a set P of possible (extended logic) programs
ffl a set E + of positive examples (ground facts)
ffl a set E \Gamma of negative examples (ground facts)
ffl a non-contradictory extended logic program B (background knowledge 4 )
Find:
ffl an extended logic program P 2 P such that
Eg.
We suppose that the training sets E are disjoint. However, the system is
also able to work with overlapping training sets.
The learned theory will contain rules of the form:
for every target predicate p, where ~
stands for a tuple of arguments. In order to
satisfy the completeness requirement, the rules for p will entail all positive examples
while the rules for :p will entail all (explicitly negated) negative examples. The
consistency requirement is satisfied by ensuring that both sets of rules do not entail
instances of the opposite element in either of the training sets.
Note that, in the case of extended logic programs, the consistency with respect
to the training set is equivalent to the requirement that the program is non-contradictory
on the examples. This requirement is enlarged to require that the
program be non-contradictory also for unseen atoms, i.e., B[P 6j= L":L for every
atom L of the target predicates.
We say that an example e is covered by program P if P e. Since the
SLX procedure is correct with respect to WFSX, even for contradictory programs,
coverage of examples is tested by verifying whether P 'SLX e.
Our approach to learning with extended logic programs consists in initially applying
conventional ILP techniques to learn a positive definition from E
and a negative definition from In these techniques, the SLX procedure
substitutes the standard Logic Programming proof procedure to test the coverage
of examples.
The ILP techniques to be used depend on the level of generality that we want to
have for the two definitions: we can look for the Least General Solution (LGS) or
the Most General Solution (MGS) of the problem of learning each concept and its
complement. In practice, LGS and MGS are not unique and real systems usually
learn theories that are not the least nor most general, but closely approximate one
of the two. In the following, these concepts will be used to signify approximations
to the theoretical concepts.
LGSs can be found by adopting one of the bottom-up methods such as relative
least general generalization (rlgg) [40] and the GOLEM system [37], inverse resolution
[36] or inverse entailment [30]. Conversely, MGSs can be found by adopting a
top-down refining method (cf. [31]) and a system such as FOIL [43] or Progol [35].
4. Strategies for Combining Different Generalizations
The generality of concepts to be learned is an important issue when learning in a
three-valued setting. In a two-valued setting, once the generality of the definition
is chosen, the extension (i.e., the generality) of the set of false atoms is undesirably
and automatically decided, because it is the complement of the true atoms set.
In a three-valued setting, rather, the extension of the set of false atoms depends
on the generality of the definition learned for the negative concept. Therefore,
the corresponding level of generality may be chosen independently for the two
definitions, thus affording four epistemological cases. The adoption of ELP allows
to express case combination in a declarative and smooth way.
Furthermore, the generality of the solutions learned for the positive and negative
concepts clearly influences the interaction between the definitions. If we learn the
MGS for both a concept and its opposite, the probability that their intersection is
non-empty is higher than if we learn the LGS for both. Accordingly, the decision
as to which type of solution to learn should take into account the possibility of
interaction as well: if we want to reduce this possibility, we have to learn two LGS,
if we do not care about interaction, we can learn two MGS. In general, we may learn
different generalizations and combine them in distinct ways for different strategic
purposes within the same application problem.
The choice of the level of generality should be made on the basis of available
knowledge about the domain. Two of the criteria that can be taken into account
are the damage or risk that may arise from an erroneous classification of an unseen
object, and the confidence we have in the training set as to its correctness and
representativeness.
When classifying an as yet unseen object as belonging to a concept, we may later
discover that the object belongs to the opposite concept. The more we generalize
a concept, the higher is the number of unseen atoms covered by the definition and
the higher is the risk of an erroneous classification. Depending on the damage that
may derive from such a mistake, we may decide to take a more cautious or a more
confident approach. If the possible damage from an over extensive concept is high,
then one should learn the LGS for that concept, if the possible damage is low then
one can generalize the most and learn the MGS. The overall risk will depend too
on the use of the learned concepts within other rules.
The problem of selecting a solution of an inductive problem according to the cost
of misclassifying examples has been studied in a number of works. PREDICTOR
[22] is able to select the cautiousness of its learning operators by means of meta-
heuristics. These metaheuristics make the selection based on a user-input penalty
for prediction error. [41] provides a method to select classifiers given the cost of
misclassifications and the prior distribution of positive and negative instances. The
method is based on the Receiver Operating Characteristic (ROC) graph from signal
theory that depicts classifiers as points in a graph with the number of false positive
on the X axis and the number of true positive on the Y axis. In [38] it is discussed
how the different costs of misclassifying examples can be taken into account into a
number of algorithms: decision tree learners, Bayesian classifiers and decision lists
learners. The Reduced Cost Algorithm is presented that selects and order rules
after they have been learned in order to minimize misclassification costs. More-
over, an algorithm for pruning decision lists is presented that attempts to minimize
costs while avoiding overfitting. In [23] it is discussed how the penalty incurred if
a learner outputs the wrong classification is considered in order to decide whether
to acquire additional information in an active learner.
As regards the confidence in the training set, we can prefer to learn the MGS for
a concept if we are confident that examples for the opposite concept are correct and
representative of the concept. In fact, in top-down methods, negative examples are
used in order to delimit the generality of the solution. Otherwise, if we think that
examples for the opposite concept are not reliable, then we should learn the LGS.
In the following, we present a realistic example of the kind of reasoning that can
be used to choose and specify the preferred level of generality, and discuss how to
strategically combine the different levels by employing ELP tools to learning.
Example: Consider a person living in a bad neighbourhood in Los Angeles. He
is an honest man and to survive he needs two concepts, one about who is likely to
attack him, on the basis of appearance, gang membership, age, past dealings, etc.
he wants to take a cautious approach, he maximizes attacker and minimizes
:attacker, so that his attacker1 concept allows him to avoid dangerous situations.
Another concept he needs is the type of beggars he should give money to (he is
a good man) that actually seem to deserve it, on the basis of appearance, health,
age, etc. Since he is not rich and does not like to be tricked, he learns a beggar1
concept by minimizing beggar and maximizing :beggar, so that his beggar concept
allows him to give money strictly to those appearing to need it without faking.
However rejected beggars, especially malicious ones, may turn into attackers, in
this very bad neighbourhood. Consequently, if he thinks a beggar might attack
him he had better be more permissive about who is a beggar and placate him with
money. In other words, he should maximize beggar and minimize :beggar in a
beggar2 concept.
These concepts can be used in order to minimize his risk taking when he carries, by
his standards, a lot of money and meets someone who is likely to be an attacker,
with the following kind of reasoning:
lot of money(X);
lot of money(X); give money(X; Y )
give
give
If he does not have a lot of money on him, he may prefer not to run as he risks
being beaten up. In this case he has to relax his attacker concept into attacker2,
but not relax it so much that he would use :attackerMGS .
The various notions of attacker and beggar are then learnt on the basis of previous
experience the man has had (see [29]).
5. Strategies for Eliminating Learned Contradictions
The learnt definitions of the positive and negative concepts may overlap. In this
case, we have a contradictory classification for the objective literals in the intersec-
tion. In order to resolve the conflict, we must distinguish two types of literals in
the intersection: those that belong to the training set and those that do not, also
dubbed unseen atoms (see figure 2).
In the following, we discuss how to resolve the conflict in the case of unseen
literals and of literals in the training set. We first consider the case in which the
training sets are disjoint, and we later extend the scope to the case where there is a
non-empty intersection of the training sets, when they are less than perfect. From
now onwards, ~
stands for a tuple of arguments.
For unseen literals, the conflict is resolved by classifying them as undefined, since
the arguments supporting the two classifications are equally strong. Instead, for
literals in the training set, the conflict is resolved by giving priority to the classification
stipulated by the training set. In other words, literals in a training set that
are covered by the opposite definition are made as exceptions to that definition.

Figure

2. Interaction of the positive and negative definitions on exceptions.
Contradiction on Unseen Literals For unseen literals in the intersection, the
undefined classification is obtained by making opposite rules mutually defeasible,
or "non-deterministic" (see [5, 2]). The target theory is consequently expressed in
the following way:
not :p( ~
not p( ~
X)
are, respectively, the definitions learned for the positive
and the negative concept, obtained by renaming the positive predicate by p + and its
explicit negation by p \Gamma . From now onwards, we will indicate with these superscripts
the definitions learned separately for the positive and negative concepts.
We want p( ~
X) and :p( ~
X) each to act as an exception to the other. In case
of contradiction, this will introduce mutual circularity, and hence undefinedness
according to WFSX. For each literal in the intersection of p + and are
two stable models, one containing the literal, the other containing the opposite
literal. According to WFSX, there is a third (partial) stable model where both
literals are undefined, i.e., no literal p( ~
X), :p( ~
X), not p( ~
X) or not :p( ~
to the well-founded (or least partial stable) model. The resulting program contains
a recursion through negation (i.e., it is non-stratified) but the top-down SLX procedure
does not go into a loop because it comprises mechanisms for loop detection
and treatment, which are implemented by XSB through tabling.
Example: Let us consider the Example of section 4. In order to avoid contradictions
on unseen atoms, the learned definitions must be:
MGS (X); not :attacker1(X)
LGS (X); not attacker1(X)
LGS (X); not :beggar1(X)
MGS (X); not beggar1(X)
MGS (X); not :beggar2(X)
LGS (X); not beggar2(X)
LGS (X); not :attacker2(X)
LGS (X); not attacker2(X)
Note that p
X)
X) can display as well the undefined truth value, either
because the original background is non-stratified or because they rely on some
definition learned for another target predicate, which is of the form above and
therefore non-stratified. In this case, three-valued semantics can produce literals
with the value "undefined", and one or both of p
X)
X) may be undefined.
If one is undefined and the other is true, then the rules above make both p and :p
undefined, since the negation by default of an undefined literal is still undefined.
However, this is counter-intuitive: a defined value should prevail over an undefined
one.
In order to handle this case, we suppose that a system predicate undefined(X)
is available 5 , that succeeds if and only if the literal X is undefined. So we add the
following two rules to the definitions for p and :p:
According to these clauses, p( ~
X) is true when
X) is true and
X) is undefined,
and conversely.
Contradiction on Examples Theories are tested for consistency on all the literals
of the training set, so we should not have a conflict on them. However, in
some cases, it is useful to relax the consistency requirement and learn clauses that
cover a small amount of counter examples. This is advantageous when it would
be otherwise impossible to learn a definition for the concept, because no clause is
contained in the language bias that is consistent, or when an overspecific definition
would be learned, composed of very many specific clauses instead of a few general
ones. In such cases, the definitions of the positive and negative concepts may cover
examples of the opposite training set. These must then be considered exceptions,
which are then are due to abnormalities in the opposite concept.
Let us start with the case where some literals covered by a definition belong
to the opposite training set. We want of course to classify these according to
the classification given by the training set, by making such literals exceptions. To
handle exceptions to classification rules, we add a negative default literal of the form
not abnorm p ( ~
X)
X)) to the rule for p( ~
X)), to
express possible abnormalities arising from exceptions. Then, for every exception
p( ~ t), an individual fact of the form abnorm p ( ~ t) (resp. abnorm:p ( ~ t)) is asserted
so that the rule for p( ~
X)) does not cover the exception, while the
opposite definition still covers it. In this way, exceptions will figure in the model of
the theory with the correct truth value. The learned theory thus takes the form:
not abnorm p ( ~
not :p( ~
not abnorm:p ( ~
not p( ~
Abnormality literals have not been added to the rules for the undefined case because
a literal which is an exception is also an example, and so must be covered by its
respective definition; therefore it cannot be undefined.
Notice that if E example p( ~ t), then p( ~ t) is classified
false by the learned theory. A different behaviour would obtain by slightly changing
the form of learned rules in order to adopt, for atoms of the training set, one
classification as default and thus give preference to false (negative training set) or
true (positive training set)
Individual facts of the form abnorm p ( ~
used as examples for learning
a definition for abnorm p and abnorm:p , as in [25, 19]. In turn, exceptions to the
definitions of abnorm p and abnorm:p might be found and so on, thus leading to a
hierarchy of exceptions (for our hierarchical learning of exceptions, see [27]).
Example: Consider a domain containing entities a; b; c; d; e; f and suppose the
target concept is f lies. Let the background knowledge be:
bird(a) has wings(a)
jet(b) has wings(b)
angel(c) has wings(c) has limbs(c)
penguin(d) has wings(d) has limbs(d)
dog(e) has limbs(e)
cat(f) has limbs(f)
and let the training set be:
A possible learned theory is:
f lies(X) / f lies + (X); not abnormal flies (X); not :f lies(X)
f lies(X) / f lies
lies
abnormal flies (d)
where f lies (X) / has wings(X) and f lies(X) \Gamma / has limbs(X).

Figure

3. Coverage of definitions for opposite concepts
The example above and figure 3 show all the various cases for a literal when learning
in a three-valued setting. a and e are examples that are consistently covered by the
definitions. b and f are unseen literals on which there is no contradiction. c and d
are literals where there is contradiction, but c is classified as undefined whereas d
is considered as an exception to the positive definition and is classified as negative.
Identifying contradictions on unseen literals is useful in interactive theory revision,
where the system can ask an oracle to classify the literal(s) leading to contradiction,
and accordingly revise the least or most general solutions for p and for :p using a
theory revision system such as REVISE [7] or CLINT [12, 14]. Detecting uncovered
literals points to theory extension.
Extended logic programs can be used as well to represent
When one has to learn n disjoint classes, the training set contains a
number of facts for a number of predicates
i be a definition
learned by using, as positive examples, the literals in the training set classified as
belonging to p i and, as negative examples, all the literals for the other classes. Then
the following rules ensure consistency on unseen literals and on exceptions:
not abnormal p1 ( ~
not abnormal p2 ( ~
not abnormal pn ( ~
regardless of the algorithm used for learning the
6. An Algorithm for Learning Extended Logic Programs
The algorithm LIVE (Learning In a 3-Valued Environment) learns ELPs containing
non-deterministic rules for a concept and its opposite. The main procedure of the
algorithm is given below:
1. algorithm LIVE( inputs training sets,
2. B: background theory, outputs learned theory)
3.
4.
5. Obtain H by:
6. transforming H p , H:p into "non-deterministic" rules,
7. adding the clauses for the undefined case
8. output H
The algorithm calls a procedure LearnDefinition that, given a set of positive,
a set of negative examples and a background knowledge, returns a definition for
the positive concept, consisting of default rules, together with definitions for abnormality
literals if any. The procedure LearnDefinition is called twice, once for
the positive concept and once for the negative concept. When it is called for the
negative used as the positive training set and E + as the negative
one.
LearnDefinition first calls a procedure Learn(E learns a definition
H p for the target concept p. Learn consists of an ordinary ILP algorithm,
either bottom-up or top-down, modified to adopt the SLX interpreter for testing
the coverage of examples and to relax the consistency requirement of the solution.
The procedure thus returns a theory that may cover some opposite examples. These
opposite examples are then treated as exceptions, by adding a default literal to the
inconsistent rules and adding proper facts for the abnormality predicate. In partic-
ular, for each rule
covering some negative examples,
a new non-abnormality literal not abnormal r ( ~
X) is added to r and some facts for
abnormal r ( ~
are added to the theory. Examples for abnormal r are obtained from
examples for p by observing that, in order to cover an example p( ~ t) for p, the atom
abnormal r ( ~ t) must be false. Therefore, facts for abnormal r are obtained from the
r of opposite examples covered by the rule.
1. procedure LearnDefinition( inputs positive examples,
2. negative examples, B: background theory,
3. outputs learned theory)
4.
5. H := H p
6. for each rule r in H p do
7. Find the sets
r of positive and negative examples covered by r
8.
r is not empty then
9. Add the literal not abnormal r ( ~
X) to r
~ t)g from facts in
r by
11. transforming each p( ~
r into abnormal r ( ~ t)
13. endif
14. enfor
15. output H
Let us now discuss in more detail the algorithm that implements the Learn pro-
cedure. Depending on the generality of solution that we want to learn, different
algorithms must be employed: a top-down algorithm for learning the MGS, a
bottom-up algorithm for the LGS. In both cases, the algorithm must be such that,
if a consistent solution cannot be found, it returns a theory that covers the least
number of negative examples.
When learning with a top-down algorithm, the consistency necessity stopping criterion
must be relaxed to allow clauses that are inconsistent with a small number
of negative examples, e.g., by adopting one of the heuristic necessity stopping criteria
proposed in ILP to handle noise, such as the encoding length restriction [43]
of FOIL [43] or the significancy test of mFOIL [18]. In this way, we are able to
learn definitions of concepts with exceptions: when a clause must be specialized too
much in order to make it consistent, we prefer to transform it into a default rule and
consider the covered negative examples as exceptions. The simplest criterion that
can be adopted is to stop specializing the clause when no literal from the language
bias can be added that reduces the coverage of negative examples.
When learning with a bottom-up algorithm, we can learn using positive examples
only by using the rlgg operator: since the clause is not tested on negative examples,
it may cover some of them. This approach is realized by using the system GOLEM,
as in [25].
7. Implementation
In order to learn the most general solutions, a top-down ILP algorithm (cf. [31]) has
been integrated with the procedure SLX for testing the coverage. The specialization
loop of the top-down system consists of a beam search in the space of possible
clauses. At each step of the loop, the system removes the best clause from the
beam and generates refinements. They are then evaluated according to an accuracy
heuristic function, and their refinements covering at least one positive example are
added to the beam. The best clause found so far is also separately stored: this
clause is compared with each refinement and is replaced if the refinement is better.
The specialization loop stops when either the best clause in the beam is consistent
or the beam becomes empty. Then the system returns the best clause found so far.
The beam may become empty before a consistent clause is found and in this case
the system will return an inconsistent clause.
In order to find least general solutions, the GOLEM [37] system is employed. The
finite well-founded model is computed, through SLX, and it is transformed by replacing
literals of the form :A with new predicate symbols of the form neg A. Then
GOLEM is called with the computed model as background knowledge. The output
of GOLEM is then parsed in order to extract the clauses generated by rlgg before
they are post-processed by dropping literals. Thus, the clauses that are extracted
belong to the least general solution. In fact, they are obtained by randomly picking
couples of examples, computing their rlgg and choosing the consistent one that
covers the biggest number of positive examples. This clause is further generalized
by choosing randomly new positive examples and computing the rlgg of the previously
generated clause and each of the examples. The consistent generalization
that covers more examples is chosen and further generalized until the clause starts
covering some negative examples. An inverse model transformation is then applied
to the rules thus obtained by substituting each literal of the form neg A with the
literal :A.
LIVE was implemented in XSB Prolog [45] and the code of the system can be
found at :
http://www-lia.deis.unibo.it/Software/LIVE/.
8. Classification Accuracy
In this section, we compare the accuracy that can be obtained by means of a two-valued
definition of the target concept with the one that can be obtained by means
of a three-valued definition.
The accuracy of a two-valued definition over a set of testing examples is defined
as
number of examples correctly classified by the theory
total number of testing examples
The number of examples correctly classified is given by the number of positive
examples covered by the learned theory plus the number of negative examples not
covered by the theory. If Np is the number of positive examples covered by the
learned definition, Nn the number of negative examples covered by the definition,
Nptot the total number of positive examples and Nntot the total number of negative
examples, then the accuracy is given by:
Nptot +Nntot
When we learn in a three value setting a definition for a target concept and its
opposite, we have to consider a different notion of accuracy. In this case, some atoms
(positive or negative) in the testing set will be classified as undefined. Undefined
atoms are covered by both the definition learned for the positive concept and that
learned for the opposite one. Whichever is the right classification of the atom in
the test set, it is erroneously classified in the learned three-valued theory, but not
so erroneously as if it was covered by the opposite definition only. This explains
the weight assigned to undefined atoms (i.e., 0.5) in the new, generalized, notion of
accuracy:
number of examples correctly classified by the theory
total number of testing examples
+0.5 \Theta
number of examples classified as unknown
total number of testing examples
In order to get a formula to calculate the accuracy, we first define a number of
figures that are illustrated in figure 4:
ffl Npp is the number of positive examples covered by the positive definition only,
ffl Npn is the number of positive examples covered by the negative definition only,
ffl Npu is the number of positive examples covered by both definitions (classified
as undefined),
ffl Nnn is the number of negative examples covered by the negative definition only,
ffl Nnp is the number of negative examples covered by the positive definition only,
ffl Nnu is the number of negative examples covered by both definitions (classified
as undefined).
The accuracy for the three-valued case can thus be defined as follows:
Nptot +Nntot
It is interesting to compare this notion of accuracy with that obtained by testing
the theory in a two-valued way. In that case the accuracy would be given by:
Nptot +Nntot
We are interested in situations where the accuracy for the three-valued case is higher
than the one for the two-valued case, i.e., those for which Accuracy 3 ? Accuracy 2 .
By rewriting this inequation in terms of the figures above, we get:
This inequation can be rewritten as:
Figure

4. Sets of examples for evaluating the accuracy of a three-valued hypothesis
where the expression Nntot represents the number of negative examples
not covered by any definition (call it Nn not covered). Therefore, the accuracy
that results from testing the theory in a three-valued way improves the two-valued
one when most of the negative examples are covered by any of the two definitions,
the number of negative examples on which there is contradiction is particularly
high, and the number of positive examples on which there is contradiction is low.
When there is no overlap between the two definitions, and no undefinedness, the
accuracy is the same.
9. Related Work
The adoption of negation in learning has been investigated by many authors. Many
propositional learning systems learn a definition for both the concept and its op-
posite. For example, systems that learn decision trees, as c4.5 [42], or decision
rules, as the AQ family of systems [33], are able to solve the problem of learning a
definition for n classes, that generalizes the problem of learning a concept and its
opposite. However, in most cases the definitions learned are assumed to cover the
whole universe of discourse: no undefined classification is produced, any instance is
always classified as belonging to one of the classes. Instead, we classify as undefined
the instances for which the learned definitions do not give a unanimous response.
When learning multiple concepts, it may be the case that the descriptions learned
are overlapping. We have considered this case as non-desirable: this is reasonable
when learning a concept and its opposite but it may not be the case when learning
more than two concepts (see [17]). As it has been pointed out by [34], in some cases
it is useful to produce more than one classification for an instance: for example if
a patient has two diseases, his symptoms should satisfy the descriptions of both
diseases. A subject for future work will be to consider classes of paraconsistent logic
programs where the overlap of definitions for p and :p (and, in general, multiple
concepts) is allowed.
The problems raised by negation and uncertainty in concept-learning, and Inductive
Logic Programming in particular, were pointed out in some previous work
(e.g., [4, 13, 10]). For concept learning, the use of the CWA for target predicates
is no longer acceptable because it does not allow to distinguish between what is
false and what is undefined. De Raedt and Bruynooghe [13] proposed to use a
three-valued logic (later on formally defined in [10]) and an explicit definition of
the negated concept in concept learning. This technique has been integrated within
the CLINT system, an interactive concept-learner. In the resulting system, both a
positive and a negative definition are learned for a concept (predicate) p, stating,
respectively, the conditions under which p is true and those under which it is false.
The definitions are learned so that they do not produce an inconsistency on the
examples. Furthermore, CLINT does not produce inconsistencies also on unseen
examples because of its constraint handling mechanism, since it would assert the
constraint false , and take care that it is never violated. Distinctly from
this system, we make sure that the two definitions do not produce inconsistency
on unseen atoms by making learned rules non-deterministic. This way, we are able
to learn definitions for exceptions to both concepts so that the information about
contradiction is still available. Another contradistinction is that we cope with and
employ simultaneously two kinds of negation, the explicit one, to state what is false,
and the default (defeasible) one, to state what can be assumed false.
The system LELP (Learning Extended Logic Programs) [25] learns ELPs under
answer-set semantics. LELP is able to learn non-deterministic default rules with a
hierarchy of exceptions. Hierarchical learning of exceptions can be easily introduced
in our system (see [27]). From the viewpoint of the learning problems that the
two algorithms can solve, they are equivalent when the background is a stratified
extended logic program, because then our and their semantics coincide. All the
examples shown in [25] are stratified and therefore they can be learned by our
algorithm and, viceversa, example in section 5 can be learned by LELP. However,
when the background is a non-stratified extended logic program, the adoption of a
well-founded semantics gives a number of advantages with respect to the answer-set
semantics. For non-stratified background theories, answer-sets semantics does not
enjoy the structural property of relevance [15], like our WFSX does, and so they
cannot employ any top-down proof procedure. Furthermore, answer-set semantics
is not cumulative [15], i.e., if you add a lemma then the semantics can change, and
thus the improvement in efficiency given by tabling cannot be obtained. Moreover,
by means of WFSX, we have introduced a method to choose one concept when the
other is undefined which they cannot replicate because in the answer-set semantics
one has to compute eventually all answer-sets to find out if a literal is undefined.
The structure of the two algorithms is similar: LELP first generates candidate rules
from a concept using an ordinary ILP framework. Then exceptions are identified
(as covered examples of the opposite set) and rules specialized through negation as
default and abnormality literals, which are then assumed to prevent the coverage
of exceptions. These assumptions can be, in their turn, generalized to generate
hierarchical default rules. One difference between us and [25] is in the level of
generality of the definitions we can learn. LELP learns a definition for a concept
only from positive examples of that concept and therefore it can only employ a
bottom-up ILP technique and learn the LGS. Instead, we can choose whether to
adopt a bottom-up or a top-down algorithm, and we can learn theories of different
generality for different target concepts by integrating, in a declarative way, the
learned definitions into a single ELP. Another difference consists in that LELP
learns a definition only for the concept that has the highest number of examples
in the training set. It learns both positive and negative concepts only when the
number of positive examples is close to that of negative ones (in
while we always learn both concepts.
Finally, many works have considered multi-strategy learners or multi-source learn-
ers. A multi-strategy learner combines learning strategies to produce effective hypotheses
(see [26]). A multi-source learner implements an algorithm for integrating
knowledge produced by the separate learners. Multi-strategy learning has been
adopted, for instance, for the improvement of classification accuracy [17], and to
equip an autonomous agent with capabilities to survive in an hostile environment
[11].
Our approach considers two separate concept-based learners, in order to learn
a definition for a concept and its opposite. Multiple (opposite) target concepts
constitute part of the learned knowledge base, and each learning element is able
to adopt a bottom-up or a top-down strategy in learning rules. This can be easily
generalized to learn definitions for n disjoint classes of concepts or for multiple agent
learning (see our [28]). Very often, the hypothesis can be more general than what is
required. The second step of our approach, devoted to the application of strategies
for eliminating learned contradictions, can be seen as a multi-source learner [26] or
a meta-level one [6], where the learned definitions are combined to obtain a non-contradictory
extended logic program. ELPs are used to specify combinations of
strategies in a declarative way, and to recover, in the the process, the consistency
of the learned theory.
10. Concluding Highlights
The two-valued setting that has been adopted in most work on ILP and Inductive
Concept Learning in general is not sufficient in many cases where we need to represent
real world data. This is for example the case of an agent that has to learn
the effect of the actions it can perform on the domain by performing experiments.
Such an agent needs to learn a definition for allowed actions, forbidden actions
and actions with an unknown outcome, and therefore it needs to learn in a richer
three-valued setting.
In order to achieve that in ILP, the class of extended logic programs under the
well-founded semantics with explicit negation (WFSX ) is adopted by us as the representation
language. This language allows two kinds of negation, default negation
plus a second form of negation called explicit, that is mustered in order to explicitly
represent negative information. Adopting extended logic programs in ILP
prosecutes the general trend in Machine Learning of extending the representation
language in order to overcome the recognized limitations of existing systems.
The programs that are learned will contain a definition for the concept and its
opposite, where the opposite concept is expressed by means of explicit negation.
Standard ILP techniques can be adopted to separately learn the definitions for the
concept and its opposite. Depending on the adopted technique, one can learn the
most general or the least general definition.
The two definitions learned may overlap and the inconsistency is resolved in a different
way for atoms in the training set and for unseen atoms: atoms in the training
set are considered exceptions, while unseen atoms are considered unknown. The
different behaviour is obtained by employing negation by default in the definitions:
default abnormality literals are used in order to consider exceptions to rules, while
non-deterministic rules are used in order to obtain an unknown value for unseen
atoms. We have shown how the adoption of extended logic programs in ILP allows
to tackle both learning in a three-valued setting and specify the combination of
strategies in a declarative way, also coping with contradiction and exceptions in the
process.
The system LIVE (Learning in a three-Valued Environment) has been developed
to implement the above mentioned techniques. In particular, the system learns a
definition for both the concept and its opposite and is able to identify exceptions and
treat them through default negation. The system is parametric in the procedure
used for learning each definition: it can adopt either a top-down algorithm, using
beam-search and a heuristic necessity stopping criterion, or a bottom-up algorithm,
that exploits the GOLEM system.
Notes
1. For definitions and foundations of LP, refer to [16]. For a recent state-of-the art of LP extensions
for non-monotonic reasoning, refer to [2].
2. For the most advanced, incorporating more recent theoretical developments, see the XSB
system at: htpp://www.cs.sunysb.edu/~sbprolog/xsb-page.html.
3. Notice that in the formula not lover(H; L) variable H is universally quantified, whereas L is
existentially quantified.
4. By non-contradictory program we mean a program which admits at least one WFSX model.
5. The undefined predicate can be implemented through negation NOT under CWA (NOT P
means that P is false whereas not means that P is false or undefined), i.e., undefined(P ) /



--R


Reasoning with Logic Programming
"Classical"

Logic programming and knowledge representation.

REVISE: An extended logic programming system for revising knowledge bases.
Abduction on 3
A survey on paraconsistent semantics for extended logic programs.
Interactive Theory Revision: An Inductive Logic Programming Approach.
Learning to survive.
Towards friendly concept-learners
On negation and three-valued logic in interactive concept learning
Interactive concept learning and constructive induction by analogy.
A classification-theory of semantics of normal logic programs: I
Prolegomena to logic programming and non-monotonic reasoning
Multistrategy learning: An analytical approach.

Cooperation of abduction and induction in logic programming.
The stable model semantics for logic programming.
Logic programs with classical negation.
Explicitly biased generalization.
Learning active classifiers.
Learning abductive and nonmonotonic logic programs.
Learning extended logic programs.
A framework for multistrategy learning.
Learning in a three-valued setting
Agents learning in a three-valued setting
Strategies in combined learning via logic programs.
A tool for efficient induction of recursive programs.

Generalizing updates: from models to programs.
Discovery classification rules using variable-valued logic system VL1
A theory and methodology of inductive learning.
Inverse entailment and Progol.
Machine invention of first-order predicates by inverting resolution
Efficient induction of logic programs.
Reducing misclassification costs.
Well founded semantics for logic programs with explicit negation.
A note on inductive generalization.
Analysis and visualization of classifier performance: Comparison under imprecise class and cost distribution.

Learning logical definitions from relations.
On closed-word data bases
The XSB Programmer's Manual Version 1.7.
The well-founded semantics for general logic programs
--TR
Explicitly biased generalization
Logic programs with classical negation
The well-founded semantics for general logic programs
Sub-unification
Interactive Concept-Learning and Constructive Induction by Analogy
Well founded semantics for logic programs with explicit negation
C4.5: programs for machine learning
SLXMYAMPERSANDmdash;a top-down derivation procedure for programs with explicit negation
Interactive theory revision
Strategies in Combined Learning via Logic Programs
A survey of paraconsistent semantics for logic programs
Reasoning with Logic Programming
Inductive Logic Programming
MYAMPERSANDlsquo;ClassicalMYAMPERSANDrsquo; Negation in Nonmonotonic Reasoning and Logic Programming
Learning Logical Definitions from Relations
Generalizing Updates
Abduction over 3-Valued Extended Logic Programs
Prolegomena to Logic Programming for Non-monotonic Reasoning

--CTR
Chongbing Liu , Enrico Pontelli, Nonmonotonic inductive logic programming by instance patterns, Proceedings of the 9th ACM SIGPLAN international symposium on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland
Chiaki Sakama, Induction from answer sets in nonmonotonic logic programs, ACM Transactions on Computational Logic (TOCL), v.6 n.2, p.203-231, April 2005
Evelina Lamma , Fabrizio Riguzzi , Lus Moniz Pereira, Strategies in Combined Learning via Logic Programs, Machine Learning, v.38 n.1-2, p.63-87, Jan.&slash;Feb. 2000
Thomas Eiter , Michael Fink , Giuliana Sabbatini , Hans Tompits, Using methods of declarative logic programming for intelligent information agents, Theory and Practice of Logic Programming, v.2 n.6, p.645-709, November 2002
inductive logic programming;multi-strategy learning;explicit negation;contradiction handling;non-monotonic learning