=Paper=
{{Paper
|id=Vol-1195/long7
|storemode=property
|title=Toward an Improved Downward Refinement Operator for Inductive Logic Programming
|pdfUrl=https://ceur-ws.org/Vol-1195/long7.pdf
|volume=Vol-1195
|dblpUrl=https://dblp.org/rec/conf/cilc/Ferilli14
}}
==Toward an Improved Downward Refinement Operator for Inductive Logic Programming==
<pdf width="1500px">https://ceur-ws.org/Vol-1195/long7.pdf</pdf>
<pre>
      Toward an Improved Downward Refinement
      Operator for Inductive Logic Programming

                                        S. Ferilli1,2
                   1
                     Dipartimento di Informatica – Università di Bari
                              stefano.ferilli@uniba.it
    2
      Centro Interdipartimentale per la Logica e sue Applicazioni – Università di Bari




         Abstract. In real-world supervised Machine Learning tasks, the learned
         theory can be deemed as valid only until there is evidence to the con-
         trary (i.e., new observations that are wrongly classified by the theory).
         In such a case, incremental approaches allow to revise the existing the-
         ory to account for the new evidence, instead of learning a new theory
         from scratch. In many cases, positive and negative examples are pro-
         vided in a mixed and unpredictable order, which requires generalization
         and specialization refinement operators to be available for revising the
         hypotheses in the existing theory when it is inconsistent with the new
         examples. The space of Datalog Horn clauses under the OI assumption
         allows the existence of refinement operators that fulfill desirable proper-
         ties. However, the versions of these operators currently available in the
         literature are not able to handle some refinement tasks. The objective of
         this work is paving the way for an improved version of the specialization
         operator, aimed at extending its applicability.



1      Introduction

Supervised Machine Learning approaches based on First-Order Logic represen-
tations are particularly indicated in real-world tasks in which the relationships
among objects play a relevant role in the definition of the concepts of interest.
Given an initial set of examples, a theory can be learned from them by providing
a learning system with the whole ‘batch’ of examples. However, being inductive
inference only falsity preserving, the learned theory can be deemed as valid only
until there is evidence to the contrary (i.e., new observations that are wrongly
classified by the theory). In such a case, either a new theory is to be learned from
scratch using the new batch made up of both the old and the new examples, or
the existing theory must be incrementally revised to account for the new evi-
dence as well. To distinguish these two stages, we may call them ‘training’ and
‘tuning’, respectively. In extreme cases, the initial batch is not available at all,
and learning must start and proceed incrementally from scratch. In many real
cases, positive and negative examples are provided in a mixed and unpredictable
order to the tuning phase, which requires two di↵erent refinement operator to be
available for revising the hypotheses in the existing theory when it is inconsistent


                                         99
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    with the new examples. A generalization operator is needed to refine a hypothe-
    sis that does not account for a positive example, while a specialization operator
    must be applied to refine a hypothesis that erroneously accounts for a negative
    example. So, the kind of modifications that are applied to the theory change
    its behavior non-monotonically. The research on incremental approaches is not
    very wide, due to the intrinsic complexity of learning in environments where the
    available information about the concepts to be learned is not completely known
    in advance, especially in a First-Order Logic (FOL) setting. Thus, the literature
    published some years ago still represents the state-of-the-art for several aspects
    of interest.
        The focus of this paper is on supervised incremental inductive learning of
    logic theories from examples, and specifically on the extension of existing spe-
    cialization operators. Indeed, while these operators have a satisfactory behavior
    when trying to add positive literals to a concept definition, the way they handle
    the addition of negative information has some shortcomings that, if solved, would
    allow a broader range of concepts to be learned. Here we point out these short-
    comings, and propose both improvements of the existing operator definitions,
    and extensions to them. Theoretical results on the new version of the operator
    are sketched, and an algorithm for it is provided and commented. The solution
    has been implemented and embedded in the multistrategy incremental learning
    system InTheLEx [3]. The next section lays the logic framework in which we
    cast our proposal; then, Sections 3 and 4 introduce the learning framework in
    general and the state-of-the-art specialization operator for it in particular. Sec-
    tion 5 describes our new proposal, and finally Section 6 concludes the paper.
    Due to lack of space, proofs of theoretical results will not be provided.


    2     Preliminaries
    The logic framework in which we build our solution exploits Datalog [1, 4] as
    a representation language. Syntactically, it can be considered as a sublanguage
    of Prolog in which no function symbols are allowed. I.e., a Datalog term can
    only be a variable or a constant, which avoids potentially infinite nesting in
    terms and hence simplifies clause handling by the operators we will define in
    the following. The missing expressiveness of function symbols can be recovered
    by Flattening [9], a representational change that transforms a set of clauses
    containing function symbols into another, semantically equivalent to it, made up
    of function-free clauses1 . In a nutshell, each n-ary function symbol is associated
    to a new (n+1)-ary predicate, where the added argument represents the function
    result. Functions are replaced, in the literals in which they appear, by variables
    or constants representing their result.
        In the following, we will denote by body(C) and head(C) the set of literals
    in the body and the atom in the head of a Horn clause C, respectively. Pure
    1
        Flattening potentially generates an infinite function free program. This is not our
        case, where we aim at learning from examples, and thus our universe is limited by
        what we see in the examples.



                                            100
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    Datalog does not allow the use of negation in the body of clauses. A first way to
    overcome this limitation is the Closed World Assumption (CWA): if a fact does
    not logically follows from a set of Datalog clauses, then we assume its negation
    to be true. This allows the deduction of negative facts, but not their use to infer
    other information. Conversely, real world description often needs rules containing
    negative information. Datalog¬ allows to use negated literals in clauses body, at
    the cost of a further safety condition: each variable occurring in a negated literal
    must occur in another positive literal of the body too.
        Since there can be several minimal Herbrand models instead of a single a
    least one, CWA cannot be used. In Stratified Datalog¬ this problem is solved by
    partitioning a program P in n sets P i (called layers) s.t.:

     1. all rules that define the same predicate in P are in the same layer;
     2. P 1 contains only clauses without negated literals, or whose negated literals
        correspond to predicates defined by facts in the knowledge base;
     3. each layer P i , i > 1, contains only clauses whose negated literals are com-
        pletely defined in lower level layers (i.e., layers P j with j < i).

    Such a partition is called stratification, and P is called stratified.
    A stratified program P with stratification P 1 , . . . , P n is evaluated by growing
    layers, applying to each one CWA locally to the knowledge base made up by
    the original knowledge base and by all literals obtained by the evaluation of the
    previous layers.
        There may be di↵erent stratifications for a given program, but all are equiv-
    alent as regards the evaluation result. Moreover, not all programs are stratified.
    The following notion allows to know if they are.

    Definition 1 (Extended dependence graph) Let P be a Datalog¬ program.
    The extended dependence graph of P , EDG(P ), is a directed graph whose nodes
    represent predicates defined by rules in P , and there is an edge hp, qi if q occurs
    in the body of a rule defining p.
    An edge hp, qi is labeled with ¬ if there exists at least one rule having p as its
    head and ¬q in its body.

    A program P is stratified if EDG(P ) contains no cycles containing edges marked
    with ¬. The evaluation of a stratified program produces a minimal Herbrand
    model, called perfect model.
        A specific kind of negation is expressed by the inequality built-in predicate
    6=. Using only this negation in Datalog yields an extension denoted by Datalog6= .


    2.1    Object Identity

    We deal with Datalog under the Object identity (OI) assumption, defined as
    follows:

    Definition 2 (Object Identity)
    Within a clause, terms denoted with di↵erent symbols must be distinct.


                                            101
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    This notion is the basis for the definition of an equational theory for Datalog
    clauses that adds one rewrite rule to the set of the axioms of Clark’s Equality
    Theory (CET) [6]:
     t 6= s 2 body(C) for each clause C in L and
         for all pairs t, s of distinct terms that occur in C                                 (OI)
    where L denotes the language that consists of all the possible Datalog clauses
    built from a finite number of predicates. The (OI) rewrite rule can be viewed as
    an extension of both Reiter’s unique-names assumption [8] and axioms (7), (8)
    and (9) of CET to the variables of the language.
       DatalogOI is a sublanguage of Datalog6= resulting from the application of OI
    to Datalog. Under OI, any Datalog clause C generates a new Datalog6= clause
    COI consisting of two components, called core and constraints:
     – core(COI ) = C and
     – constraints(COI ) = {t 6= s | t, s 2 terms(C) ^ t, s distinct}
       are the inequalities generated by the (OI) rewrite rule.
       Formally, a DatalogOI program is made up of a set of Datalog6= clauses of
    the form
                             l0 : l 1 , . . . , l n , c 1 , . . . , c m
    where the li ’s are as in Datalog, and the cj ’s are the inequalities generated by
    the (OI) rule and n 0. Nevertheless, DatalogOI has the same expressive power
    as Datalog, that is, for any Datalog program we can find a DatalogOI program
    equivalent to it [11].

    2.2     OI -subsumption

    Applying the OI assumption to the representation language causes the classical
    ordering relations among clauses to be modified, thus yielding a new structure
    of the corresponding search spaces for the refinement operators.
        The ordering relation defined by the notion of ✓-subsumption under OI upon
    Datalog clauses [2, 10] is ✓OI -subsumption.
    Definition 3 (✓OI -subsumption ordering) Let C, D be Datalog clauses. D
    ✓-subsumes C under OI (D ✓OI -subsumes C), written C OI D, i↵ 9 substi-
    tution s.t. DOI . ✓ COI . This means that D is more general than or equivalent
    to C (in a theory revision setting, D is an upward refinement of C and C is a
    downward refinement of D) under OI. C <OI D stands for C OI D^D 6OI C.
    C and D are equivalent under OI (C OI D) when C OI D and D OI C.
    A substitution, as usual, is a mapping from variables to terms [13]. Its domain
    can be extended to terms: applying a substitution to a term t means that
    is applied to all variables in t. In our case, applying a substitution to a constant
    leaves it unchanged.
        Like ✓-subsumption, ✓OI -subsumption induces a quasi-ordering upon the
    space of Datalog clauses, as stated by the following result.


                                            102
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    Proposition 1 Let C, D, E be Datalog clauses. Then:

     1. C OI C                                                                    (reflexivity)
     2. C OI D and D OI E ) C OI E                                             (transitivity)

        Other interesting properties of ✓OI -subsumption are the following:

    Proposition 2 Let C, D be Datalog clauses.

     – C OI D ) C ✓ D, where ✓ denotes ✓-subsumption
       (i.e., ✓OI -subsumption is a weaker relation than ✓-subsumption).
     – C OI D ) |C| |D|.
     – C OI D i↵ C and D are renamings.

    Non-injective substitutions would yield contradictions when applied to con-
    straints (e.g., [x 6= y].{x/a, y/a} = [a 6= a]). So, under OI, substitutions are
    required to be injective.
        Requiring that terms are distinct ‘freezes’ the number of literals of the clause
    (since they cannot unify among each other), hence ✓OI -subsumption maps each
    literal of the subsuming clause onto a single, di↵erent literal in the subsumed
    one. In particular, equivalent clauses under OI must have the same number of
    literals, hence the only way to have equivalence is through variable renaming.
    Thus, a search space ordered by ✓OI -subsumption is made up of non-redundant
    clauses, i.e. no subset of a clause can be equivalent to the clause itself under
    OI. This yields smaller equivalence classes than those in a space ordered by
    ✓-subsumption.

    Proposition 3 (Decidability of ✓OI -subsumption) Given two clauses C and
    D, C OI D is a decidable relationship.

    In the worst case, i.e. when |D|  |C|, all literals in D match with all literals
    in |C|, and all such matchings are pairwise compatible, an upper bound to the
                                                |C|
    complexity of the ✓OI -subsumption test is |D|   .


    3    Incremental Inductive Synthesis

    ILP aims at learning logic programs from examples. In our setting, examples are
    represented as clauses, whose body describes an observation, and whose head
    specifies a relationship to be learned, referred to terms in the body. Negative
    examples for a relationship have a negated head. A learned program is called a
    theory, and is made up of hypotheses, i.e. sets of program clauses all defining the
    same predicate. A hypothesis covers an example if the body of at least one of
    its clauses is satisfied by the body of the example. The search space is the set of
    all clauses that can be learned, ordered by a generalization relationship.
        In ILP, a standard practice to restrict the search space is imposing biases
    on it [7]. In the following, we are concerned with logic theories expressed as
    hierarchical (i.e., non-recursive) programs, for which it is possible to find a level


                                            103
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    mapping [6] s.t., in every program clause, the level of every predicate symbol
    occurring in the body is less than the level of the predicate in the head. This has
    strict connections with stratified programs, that are needed when the language
    is extended to deal with negation. Another bias on the representation language
    is that, whenever we write about clauses, we mean Datalog linked clauses. A
    clause is linked if, for any term appearing in its body, it also appears in the head
    or it is possible to find a chain of terms such that adjacent terms appear in the
    same literal and at least a term in the chain appears in the head.
        The canonical inductive paradigm requires the learned theory to be com-
    plete and consistent. For hierarchical theories, the following definitions are given
    (where E and E + are the sets of all the negative and positive examples, resp.):

    Definition 4 (Inconsistency)

     – A clause C is inconsistent wrt N 2 E i↵ 9 s.t.2 body(C). ✓ body(N )^
       ¬head(C). = head(N ) ^ constraints(COI ). ✓ constraints(NOI )
     – A hypothesis H is inconsistent wrt N i↵ 9C 2 H: C is inconsistent wrt N .
     – A theory T is inconsistent i↵ 9H ✓ T , 9N 2 E : H is inconsistent wrt N .

    Definition 5 (Incompleteness)

     – A hypothesis H is incomplete wrt P i↵ 8C 2 H: not(P OI C).
     – A theory T is incomplete i↵ 9H ✓ T , 9P 2 E + : H is incomplete wrt P .

        When the theory is to be learned incrementally, it becomes relevant to de-
    fine operators that allow a stepwise (incremental) refinement of too weak or too
    strong programs [5]. A refinement operator, applied to a clause, returns one of
    its upward or downward refinements. Refinement operators are the means by
    which wrong hypotheses in a logic theory are changed in order to account for
    new examples with which they are incomplete or inconsistent. In the following,
    we will assume that logic theories are made up of clauses that have only variables
    as terms, built starting from observations described as conjunctions of ground
    facts (i.e., variable-free atoms). This assumption causes no loss in expressive
    power, since a reification process allows to express through predicates all the
    information that may be carried out by constants. Put another way, we take to
    the extreme the flattening procedure, considering even constants as 0-ary func-
    tions that are replaced by 1-ary predicates having the same name and meaning.
    This restriction simplifies the refinement operators for a space ordered by ✓OI -
    subsumption defined in [2, 10], and the associated definitions and properties.

    Definition 6 (Refinement operators under OI) Let C be a Datalog clause.

     – D 2 ⇢OI (C) ( downward refinement operator) when
       body(D) = body(C) [ {l}, where l is an atom s.t. l 62 body(C).
     – D 2 OI (C) ( upward refinement operator) when
       body(D) = body(C) \ {l}, where l is an atom s.t. l 2 body(C).
    2
        ¬head(C). = head(N ) because the relationship must be the same as for N .



                                            104
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


        Particularly important are locally finite, proper and complete (ideal ) refine-
    ment operators [10]. Such a kind of operators are not feasible when full Horn
    clause logic is chosen as representation language and either ✓-subsumption or im-
    plication is adopted as generalization model, because of the existence of infinite
    unbound strictly ascending/descending chains. On the contrary, in the space of
    Datalog clauses ordered by ✓OI -subsumption such a kind of chains do not exist,
    since equivalence among clauses coincides with alphabetic variance. This makes
    possible the existence of ideal refinement operators under the ordering induced
    by ✓OI -subsumption [2, 10].
        By the definition of OI , any possible generalization of a clause must have as
    body a subset of its body, and hence there are 2|body(C)| such generalizations.
    Proposition 4 [10] The refinement operators in Definition 6 are ideal for Dat-
    alog clauses ordered by ✓OI -subsumption.
    Inspired to a concept given by Shapiro [12], we have a measure for the complexity
    of a clause:
    Definition 7 (sizeOI ) The size of a clause C under OI (size OI (C)) is the num-
    ber of literals in the body of C:
                                   sizeOI (C) =| body(C) |
    Under ✓OI -subsumption it allows to predict the exact number of steps required
    to perform a refinement, based only on the syntactic structure of the clauses
    involved (that could be known or bounded a priori ): given two clauses C and
                              k
    D, if D <OI C, then C 2 OI   (D), D 2 ⇢kOI (C), k = sizeOI (D) sizeOI (C) =
    |body(D)| |body(C)|


    4    Downward Refinement
    When a negative example is covered, a specialization of the theory must be
    performed. Starting from the current theory, the misclassified example and the
    set of processed examples, the specialization algorithm outputs a revised theory.
    In our framework, specializing means adding proper literals to a clause that is
    inconsistent with respect to a negative example, in order to avoid its covering
    that example. The possible options for choosing such a literal might be so large
    that an exhaustive search is not feasible. Thus, we want the operator to focus the
    search into the portion of the space of literals that contains the solution of the
    diagnosed commission error, as a result of an analysis of its algebraic structure.
        According to the theoretical operator in Definition 6, only positive literals
    can be added. To this aim, we try to add to the clause one (or more) atom(s),
    which characterize all the past positive examples and can discriminate them
    from the current negative one. The search for such atoms is performed in the
    space of positive literals, that contains information coming from the positive
    examples used to learn the current theory, but not yet exploited by it. First
    of all, the process of abstract diagnosis detects all the clauses that caused the
    inconsistency. Let P = {P1 , . . . , Pn } be the positive examples ✓OI -subsumed by


                                            105
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    a clause C that is inconsistent wrt a negative example N . The set of all possible
    most general downward refinements under OI of C against N is:
        mgdrOI (C, N ) = {M | M OI C, M consistent wrt N, 8D s.t. D OI C, D
                           consistent wrt N : not(M <OI D)}
    Among these, the search process aims at finding one that is compliant with
    the previous positive examples in P, i.e. one of the most general downward
    refinements under OI (mgdr OI ) of C against N given P1 , . . . , Pn :
     mgdrOI (C, N | P1 , . . . , Pn ) = {M 2 mgdrOI (C, N ) | Pj OI M, j = 1, . . . , n}
    Since the downward refinements we are looking for must satisfy the property of
    maximal generality, the operator tries to add as few atoms as possible. Thus, it
    may happen that, even after some refinement steps, the added atoms are still
    not sufficient to rule out the negative example, i.e. the specialization of C is still
    overly general. This suggests to further exploit the positive examples in order
    to specialize C. Specifically, if there exists a literal that, when added to the
    body of C, is able to discriminate from the negative example N that caused
    the inconsistency of C, then the downward refinement operator should be able
    to find it. The resulting specialization should restore the consistency of C, by
    refining it into a clause C 0 which still ✓OI -subsumes the positive examples Pi ,
    i = 1, 2, . . . , n.
        The process of refining a clause by means of positive literals can be described
    as follows. For each Pi , i = 1, 2, . . . , n, suppose that there exist ni distinct
    substitutions s.t. C ✓OI -subsumes Pi , and consider all the possible n-tuples of
    substitutions obtained by picking one of such substitutions for every positive
    example. Each of these substitutions yields a distinct residual, consisting of all
    the literals in the example that are not involved in the ✓OI -subsumption test,
    after having properly turned their constants into variables. Formally:
    Definition 8 (Residual) Let C be a clause, E an example, and j a substitu-
    tion s.t. body(C). j ✓ body(E) and constraints(COI ). j ✓ constraints(EOI ).
    A residual of E wrt C under the mapping j , denoted by j (E, C), is:
                                                         1
                               j (E, C) = body(E). j          body(C)

    where j 1 is the extended antisubstitution of j . An antisubstitution is a map-
    ping from terms onto variables. When a clause C ✓OI -subsumes an example E
    through a substitution , then it is possible to define a corresponding antisub-
                 1
    stitution,     , which is the inverse function of , mapping some constants in
    E to variables in C. Since not all constants in E have a corresponding variable
                     1                                     1                1
    according to       , we introduce the extension of       , denoted with   , that is
    defined on the whole set consts(E), and takes values in the set of the variables
    of the language3 :
                                       ⇢ 1
                             1             (cn ) if cn 2 vars(C).
                               (cn ) =
                                                 otherwise
    3
        Variables denoted by    are new variables, managed as in Prolog.



                                            106
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    The residuals obtained from the positive examples Pi , i = 1, . . . , n, can be ex-
    ploited to build a space of complete positive downward refinements, denoted with
    P, and formally defined as follows.
                                     S        T
                             P=                      jk (Pk , C)
                                      i=1,...,n k=1,...,n
                                     ji =1,...,ni

    where the symbol jk (Pk , C) denotes one of the nk residuals of Pk wrt C, and
    \k=1,...,n jk (Pk , C), when jk 2 {1, . . . , nk }, is the set of the literals common to
    an n-tuple of residuals (one residual for each positive example Pk , k = 1, . . . , n).
    Moreover, denoted with ✓j , j = 1, . . . , m, all the substitutions which make C
    inconsistent wrt N , let us define a new space:
                                      S
                                  S = j=1,...,m j (N, C)
    which includes all the literals that cannot be used for refining C, because they
    would still be present in N .
    Proposition 5 Given a clause C that ✓OI -subsumes the positive examples P1 , . . . , Pn
    and is inconsistent wrt the negative example N , then:
    {C 0 | head(C 0 ) = head(C) ^ body(C 0 ) = body(C) [ {l}, l 2 P S} ✓
    ✓ mgdrOI (C, N | P1 , . . . , Pn )
        Hence, every downward refinement built by adding a literal in P S to the
    inconsistent clause C restores the properties of consistency and completeness
    of the original hypothesis. Moreover, it is one of the most general downward
    refinements of C against N .
        It may happen that no (set of) positive literal(s) is able to characterize the
    past positive examples and discriminate the negative example that causes incon-
    sistency. In such a case, the above version of the operator would fail. However,
    we don’t want to give up yet, since the addition of a negative literal to the
    clause body might restore consistency4 . To take this opportunity, we extend the
    search space to Datalog¬ . These literals are interpreted according to the CWA.
    Of course, suitable adaptations of the notions presented in Section 2 are used
    to handle these literals5 . So, in case of failure on the search for positive literals,
    the algorithm autonomously performs a representation change, that allows it to
    extend the search to the space of negative literals, built by taking into account
    the negative example that caused the commission error. The new version of the
    operator tries to add the negation of a literal, that is able to discriminate the
    negative example from all the past positive ones. Revisions performed by this
    4
      Note that a negative literal in the body corresponds to a positive literal in the
      clause. However, here we are expressing the fact that a condition must not hold in
      an observation in order to infer the relationship in the head.
    5
      E.g., given two clauses under OI, C = C + [ C and D = D+ [ D , where C + and
      D+ include the positive literals and the OI-constraints, and C and D are sets of
      negative literals, C OI D i↵ 9 substitution s.t. D+ . ✓ C + and 8d 2 D :6 9c 2
      C s.t. d. = c.



                                              107
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    operator are always minimal [14], since all clauses in the theory contain only vari-
    ables as arguments. Moreover, this operator is ideal in the space of constant-free
    clauses. The definitions and results in the rest of this section are taken from [2].
        When the space P         S does not contain any solution to the problem of
    specializing an inconsistent clause, a change of representation must be performed
    in order to search for literals in another space, corresponding to the quotient set
    of the Datalog¬ linked clauses. In the following, a slightly di↵erent but equivalent
    specification of the operator in this space will be provided with respect to [2].
        First of all, we define the new target space, called the space of negative
    downward refinements:
                              Sn = ¬S = ¬([j=1,...,m        j (N, C))

    where, given a set of literals ' = {l1 , . . . , ln }, n 1: ¬' = {¬l1 , . . . , ¬ln }. Again,
    we are interested in a specific subset of Sn , because of the properties satisfied
    by its elements. Let us introduce the following notation:
                                       T
                                   S = j=1,...,m j (N, C)

    Note that S ✓ S. Based on S, the space of consistent negative downward refine-
    ments can be defined as:
                               Sc = ¬S = ¬(\j=1,...,m       j (N, C))

    Indeed, Sc , compared to Sn , fulfills the following property:
    Proposition 6 Given a clause C and an example N , then:
    {C 0 | head(C 0 ) = head(C) ^ body(C 0 ) = body(C) [ {l}, l 2 Sc } ✓ mgdrOI (C, N )
        Overall, the search for a complete and consistent hypothesis can be viewed
    as a two-stage process: the former stage searches into the space P S, the latter
    into Sc . It is now possible to formally define the downward refinement operator
    ⇢cons
     OI on the space L of constant-free Datalog
                                                     OI
                                                        linked program clauses.
    Definition 9 (⇢cons  cons       L          cons
                   OI ) ⇢OI : L ! 2 8C 2 L : ⇢OI (C) =
      0         0                   0
    {C | head(C ) = head(C) ^ body(C ) = body(C) [ {l}, l 2 (P                 S) [ Sc }

    Proposition 7 The downward refinement operator ⇢cons
                                                    OI is ideal.

       The ideality of ⇢cons
                        OI   is owed to the peculiar structure of the search space
    when ordered by the relation OI .


    5    Discussion and Extension of the Specialization
         Operator
    The existing definition of ⇢cons
                                OI aims at identifying a set of literals each of which,
    when added to a clause C, yields a new clause that is both consistent with the
    given negative example and complete with respect to all the previous positive
    examples. Now, this is true if the added literal belongs to the space of complete


                                            108
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    positive downward refinements P S. Conversely, the space of consistent negative
    downward refinements does not ensure completeness wrt the previous positive
    examples, since it is computed considering only all possible residuals of the
    negative example. This can be easily shown in the following example6 .

    Example 1. Consider the following situation.
    Two positive examples: P1 = h : p, q, t, u. and P2 = h : p, q, v.
    produce as a least general generalization the clause C1 = h : p, q.
    Then, the negative example N1 = h : p, q, t, u, v. arrives.
    The residuals of P1 and P2 wrt C1 are {t, u} and {v}, respectively.
    The residual of N1 is {t, u, v}. So, P S = ({t, u} \ {v}) {t, u, v} = ;
    {t, u, v} = ;, hence no specialization by means of positive literals can be obtained
    (as expected, since C was a least general generalization). Switching to the space
    of negative literals, we have that Sc = ¬({t, u, v}) = {¬t, ¬u, ¬v}. However, none
    of these literals generates a clause that is complete with all previous positive
    examples:
        C20 = h : p, q, ¬t. where P1 6OI C20
        C200 = h : p, q, ¬u. where P1 6OI C200
        C2000 = h : p, q, ¬v. where P2 6OI C2000

        So, what we need to consider is not Sc . Intuitively, we want to select a literal
    that is present in all residuals of the negative example and that is not present
    in any residual of any positive example. Let us define:
                                              S
                                    P=                   ji (Pi , C)
                                           i=1,...,n
                                          ji =1,...,ni


    Now, what we need to consider is S0c = ¬(S              P).

    Example 2. In the previous example, we would have S0c = ({t, u, v}) ({t, u} [
    {v}) = {t, u, v} {t, u, v} = ; which shows, as expected, that no complete
    refinement can be obtained for the given case.
        Consider now another set of positive examples: P1 = h : p, q, t, u., P2 = h :
      p, q, r. and P3 = h : p, q, s, t.
    whose least general generalization is, again, the clause C1 = h : p, q.
    Then, the negative example N1 = h : p, q, t, u, v, w. arrives.
    The residuals of the positive examples are: (C1 , P1 ) = {t, u}, (C1 , P2 ) = {r}
    and (C1 , P3 ) = {s, t}.
    The residual of N1 is {t, u, v, w} = S. So, P S = ({t, u} \ {r} \ {s, t})
    {t, u, v, w} = ; {t, u, v, w} = ;, hence again no specialization by means of
    positive literals can be obtained. Switching to the space of negative literals, we
    have that S0c = ¬(S P) = ¬({t, u, v, w} ({t, u}[{r}[{s, t})) = ¬({t, u, v, w}
    6
        For the sake of readability, in the following we will often switch to a propositional
        representation. This means that the residual is unique for each example, so the
        subscript in i (·, ·) is no more necessary.



                                             109
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    {r, s, t, u}) = ¬({v, w}) = {¬v, ¬w} and indeed, adding any of these literals to
    C generates a clause that is complete with all previous positive examples:
        C20 = h : p, q, ¬v. where P1 OI C20 , P2 OI C20 and P3 OI C20 ;
        C200 = h : p, q, ¬w. where P1 OI C200 , P2 OI C200 , P3 OI C200 .
        This is captured by the following result:

    Proposition 8 Given a clause C = h :– body(C) that ✓OI -subsumes the positive
    examples P1 , . . . , Pn and is inconsistent wrt the negative example N , then:
    {C 0 | head(C 0 ) = head(C) ^ body(C 0 ) = body(C) [ {l}, l 2 S0c } ✓
    ✓ mgdrOI (C, N | P1 , . . . , Pn )

        Now, an additional problem arises. Indeed, in some cases a single negative
    literal is not enough to ensure that the correctness of the theory is restored. The
    situation may be clarified by the following example.
    Example 3. Consider again the situation described in Example 1.
        While no single (positive or negative) literal can restore completeness and
    consistency of the theory, either C20 = h : p, q, ¬(t, v). or C200 = h : p, q, ¬(u, v).
    would be correct refinements of C1 wrt {P1 , P2 , N1 }. These solutions are not per-
    mitted in the representation language, since only literals may appear in the body
    of clauses. However, any of the two above clauses corresponds to the conjunction
    of two clauses, e.g. C20 is equivalent to {h : p, q, ¬t., h : p, q, ¬v.}. This solution
    would introduce some redundancy in the theory, since the body of the original
    clause C1 would appear in both specialized clauses. This might be undesirable,
    in which case we may leverage Datalog implication and solve the problem by
    inventing a new predicate s as follows: {h : p, q, ¬(s)., s : t, v.}. The intuition
    behind this choice is that the need to place together the literals in the negation
    might be a hint of a more general relationship among them. This relationship
    might be captured by a so far unknown concept, that is explicitly added. A
    useful side e↵ect of this setting is that when the same combination will occur
    in future observations, it will be recognized and explicitly added by saturation,
    this way obtaining higher level descriptions.
        So, the extension comes into play when no single literal is sufficient to restore
    correctness of the theory. Indeed, when a single literal is to be negated there is
    no need for inventing any predicate. More formally, we are not looking anymore
    for a single l 2 S0c to be added to C, but we need a S ✓ S0c s.t. 8i : 9l 2 S
    s.t. l 62 Pi . In particular, we would like to find a minimal such set. Minimality
    may be in terms of set inclusion or of number of elements: S = arg minS (|S|).
    To formally express our operator, let us define:

     – 8r 2 (N, C) :
        • Pr = {Pi 2 P|r 2          (Pi , C)}
        • Pr = {Pi 2 P|r 62         (Pi , C)}
     – 8S ✓ (N, C) :
        • PS = \r2S Pr
        • PS = [r2S Pr



                                            110
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    Pr is the set of positive examples that are no more covered when adding ¬r to C;
    Pr is the set of positive examples that are still covered when adding ¬r to C. PS
    is the set of positive examples that are no more covered when adding neg(S) to
    C; PS is the set of positive examples that are still covered when adding neg(S)
    to C. This helps us to define what we are looking for. Specifically, we need a
    S ✓ (N, C) s.t. PS = ; ^ PS = P, as shown by the following example:
    Example 4. Consider the set of positive examples P = {P1 , P2 , P3 } where:
    P1 = h : p, q, s, t. P2 = h : p, q, t, u. P3 = h : p, q, u, r.
    Given their least general generalization C = h : p, q., the corresponding resid-
    uals are:
        (P1 , C) = {s, t}   (P2 , C) = {t, u}     (P3 , C) = {u, r}
    Now, given the negative example N = h : p, q, s, t, u, r covered by C, with
    residual (N, C) = {s, t, u, r}, we have:
    P{s,u} = Ps \Pu = {P1 }\{P2 , P3 } = ;; P{s,u} = Ps \Pu = {P2 , P3 }[{P1 } = P:
    SOLUTION!
    P{t,r} = Pt \ Pr = {P1 , P2 } \ {P3 } = ;; P{t,r} = Pt \ Pr = {P3 } [ {P1 , P2 } = P:
    SOLUTION!
    P{t,u} = Pt \ Pu = {P1 , P2 } \ {P2 , P3 } = {P2 } 6= ;; P{t,u} = Pt \ Pu =
    {P3 } [ {P1 } = {P3 , P1 } =
                               6 P: NOT A SOLUTION!
    . . . and so on.
    Of course, a trial-and-error approach would solve the problem, but there is an
    exponential number of subsets to be tried. In order to devise a more efficient
    algorithm, let us analyze the sets Pr , Pr , PS and PS to better understand them
    and their behavior. First of all, the Px ’s and Px ’s are complementary:

    Proposition 9 Given a clause C and a negative example N covered by C:

     1. 8r 2 (N, C) : {Pr , Pr } is a partition of P;
     2. 8S ✓ (N, C) : {PS , PS } is a partition of P.

    This ensures, in particular, that PS = ; ^ PS = P , PS = ; , PS = P. We
    also note that positive example (un-)coverage is monotonic:

    Proposition 10 8S 0 ⇢ S 00 ✓         (N, C) : PS 00 ✓ PS 0 ^ PS 0 ✓ PS 00

    Finally, let us note that any element of the residual of the negative example,
    added to C, causes some positive example to become uncovered (which will be
    used in the first iteration of our algorithm):

    Proposition 11 If ⇢cons
                       OI fails, then 8r 2             (N, C) : Pr 6= ;.

       We propose a sequential covering-like strategy to find such an S, according
    to Algorithm 1. Note that, at the beginning of the algorithm, S = ; ) PS =
    ; ) |PS | = 0 and S = ; ) PS = P ) |PS | = n. However, as soon as
    the loop is entered, the selection and addition of the first r makes P 6= ; by
    Proposition 11; so, the condition of the IF statement is true, hence S is updated
    and a second round of the loop is guaranteed to take place. At each round, a new


                                            111
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming

    Algorithm 1 Backtracking specialization strategy
        S = ;; R = (N, C)
        repeat
           r    select from R OR backtrack
           R     R \ {r}; S 0   S [ {r}
           if PS 0 6= PS (, PS 0 6= PS ) (, PS 0 PS , PS 0 PS ) then
              S     S0
           end if
        until PS = ; (, PS = P) OR no more backtracking available
        if PS = ; (, PS = P) then
           return S
        else
           return failure
        end if



    r is removed from R and added to S only if the coverage improves, otherwise it
    is discarded. If the last r does not satisfy the loop condition, the overall solution
    is not complete and backtracking is applied. Note that, in the worst case, adding
    the whole residual to C would be a solution, which ensures termination of the
    algorithm (unless there is a positive example that includes the whole residual,
    which can be checked before starting the algorithm). If di↵erent solutions are
    requested, backtracking can be applied to non-discarded items.



    6     Conclusions and Future Work


    Incremental supervised Machine Learning approaches using First-Order Logic
    representations are mandatory when tackling complex real-world tasks, in which
    relationships among objects play a fundamental role. A noteworthy framework
    for these approaches is based on the space of Datalog Horn clauses under the Ob-
    ject Identity assumption, which ensures the existence of (upward and downward)
    refinement operators fulfilling desirable requirements. The refinement operators
    for this framework proposed in the current literature have some limitations that
    this paper aims at overcoming. So, after recalling the most important elements of
    the framework and of the current operators, this paper points out these deficien-
    cies and proposes solutions that result in improved operators. Specifically, the
    downward refinement operator is considered. A preliminary prototype of the op-
    erator has been implemented, and is currently being integrated in the InTheLEx
    learning system.
        Future work includes a study of the possible connections of the extended
    operator with related fields of the logic-based learning, such as deduction, ab-
    straction and predicate invention. Experiments aimed at assessing the efficiency
    and e↵ectiveness of the operator in real-world domains are also planned.


                                            112
S. Ferilli. Toward an Improved Downward Refinement Operator for Inductive Logic Programming


    Acknowledgments

    This work was partially funded by the Italian PON 2007-2013 project
    PON02 00563 3489339 ‘Puglia@Service’.


    References
     [1] S. Ceri, G. Gottlöb, and L. Tanca. Logic Programming and Databases. Springer-
         Verlag, Heidelberg, Germany, 1990.
     [2] F. Esposito, A. Laterza, D. Malerba, and G. Semeraro. Locally finite, proper
         and complete operators for refining datalog programs. In Z. W. Raś and
         M. Michalewicz, editors, Foundations of Intelligent Systems, number 1079 in Lec-
         ture Notes in Artificial Intelligence, pages 468–478. Springer, 1996.
     [3] F. Esposito, G. Semeraro, N. Fanizzi, and S. Ferilli. Multistrategy Theory Re-
         vision: Induction and abduction in INTHELEX. Machine Learning Journal,
         38(1/2):133–156, 2000.
     [4] P. C. Kanellakis. Elements of relational database theory. In J. van Leeuwen,
         editor, Handbook of Theoretical Computer Science, volume B — Formal Models
         and Semantics, pages 1073–1156. Elsevier Science Publishers, 1990.
     [5] H. J. Komorowski and S. Trcek. Towards refinement of definite logic programs.
         In Z. W. Raś and M. Zemankova, editors, Methodologies for Intelligent Systems,
         number 869 in Lecture Notes in Artificial Intelligence, pages 315–325, Berlin, 1994.
         Springer-Verlag.
     [6] J. W. Lloyd. Foundations of Logic Programming. Springer-Verlag, Berlin, second
         edition, 1987.
     [7] C. Nédellec, C. Rouveirol, H. Adé, F. Bergadano, and B. Tausend. Declarative
         bias in ILP. In L. de Raedt, editor, Advances in Inductive Logic Programming,
         pages 82–103. IOS Press, Amsterdam, NL, 1996.
     [8] R. Reiter. Equality and domain closure in first order databases. Journal of the
         ACM, 27:235–249, 1980.
     [9] C. Rouveirol. Extensions of inversion of resolution applied to theory completion.
         In Inductive Logic Programming, pages 64–90. Academic Press, 1992.
    [10] G. Semeraro, F. Esposito, and D. Malerba. Ideal refinement of datalog programs.
         In M. Proietti, editor, Logic Program Synthesis and Transformation, number 1048
         in Lecture Notes in Computer Science, pages 120–136. Springer-Verlag, 1996.
    [11] G. Semeraro, F. Esposito, D. Malerba, N. Fanizzi, and S. Ferilli. A logic framework
         for the incremental inductive synthesis of datalog theories. In N. E. Fuchs, editor,
         Logic Program Synthesis and Transformation, number 1463 in Lecture Notes in
         Computer Science, pages 300–321. Springer-Verlag, 1998.
    [12] E.Y. Shapiro. Inductive inference of theories from facts. Technical Report Re-
         search Report 192, Yale University, 1981.
    [13] J. H. Siekmann. An introduction to unification theory. In R. B. Banerji, edi-
         tor, Formal Techniques in Artificial Intelligence - A Sourcebook, pages 460–464.
         Elsevier Science Publisher, 1990.
    [14] S. Wrobel. Concept Formation and Knowledge Revision. Kluwer Academic Pub-
         lishers, Dordrecht Boston London, 1994.




                                            113

</pre>