In real-world supervised Machine Learning tasks, 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, incremental approaches allow to revise the existing theory to account for the new evidence, instead of learning a new theory from scratch. In many cases, positive and negative examples are provided 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 properties. 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.
Supervised Machine Learning approaches based on First-Order Logic representations 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 evidence 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 with the new examples. A generalization operator is needed to refine a hypothesis 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
specialization 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
shortcomings, 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 [
Preliminaries
The logic framework in which we build our solution exploits Datalog [
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. 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 completely 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 equivalent 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
We deal with Datalog under the Object identity (OI) assumption, defined as follows:
Within a clause, terms denoted with di↵erent symbols must be distinct.
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) [
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 ) = { 6
t = 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
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 [
The ordering relation defined by the notion of ✓ -subsumption under OI upon
Datalog clauses [
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
substitution 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 [
Like ✓ -subsumption, ✓ OI -subsumption induces a quasi-ordering upon the space of Datalog clauses, as stated by the following result. Proposition 1 Let C, D, E be Datalog clauses. Then:
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. (reflexivity) (transitivity) Non-injective substitutions would yield contradictions when applied to constraints (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 complexity of the ✓ OI -subsumption test is ||DC|| . 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 [
The canonical inductive paradigm requires the learned theory to be complete 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.):
– 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↵ 9 C 2 H: C is inconsistent wrt N . – A theory T is inconsistent i↵ 9 H ✓ T , 9 N 2 E : H is inconsistent wrt N .
– A hypothesis H is incomplete wrt P i↵ 8 C 2 H: not(P OI C). – A theory T is incomplete i↵ 9 H ✓ T , 9 P 2 E+: H is incomplete wrt P .
When the theory is to be learned incrementally, it becomes relevant to
define operators that allow a stepwise (incremental) refinement of too weak or too
strong programs [
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 .
Particularly important are locally finite, proper and complete (ideal )
refinement operators [
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 [
Inspired to a concept given by Shapiro [
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 D, if D <OI C, then C 2 OkI (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 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, 8 D 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 sucient 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 C0 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 substitution 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: j (E, C) = body(E). j 1 body(C) where j 1 is the extended antisubstitution of j . An antisubstitution is a mapping from terms onto variables. When a clause C ✓ OI -subsumes an example E through a substitution , then it is possible to define a corresponding antisubstitution, 1, 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 according to 1, we introduce the extension of 1, denoted with 1, that is defined on the whole set consts(E), and takes values in the set of the variables of the language3: 1(cn) = ⇢ 1(cn) if cn 2 vars(C).
otherwise 3 Variables denoted by are new variables, managed as in Prolog. The residuals obtained from the positive examples Pi, i = 1, . . . , n, can be exploited to build a space of complete positive downward refinements, denoted with P, and formally defined as follows.
P =
S
T
jk (Pk, C) 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 = Sj=1,...,m 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: {C0 | head(C0) = head(C) ^ body(C0) = 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
inconsistency. 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 8 d 2 D :6 9 c 2
C s.t. d. = c.
operator are always minimal [
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 [
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:
S = Tj=1,...,m Note that S ✓ S. Based on S, the space of consistent negative downward refinements 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: {C0 | head(C0) = head(C) ^ body(C0) = body(C) [ { l}, l 2 Sc} ✓
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 ⇢ cOoIns on the space L of constant-free DatalogOI linked program clauses. Definition 9 (⇢ cOoIns) ⇢ cOoIns : L ! 2L8 C 2 L : ⇢ cOoIns(C) = {C0 | head(C0) = head(C) ^ body(C0) = body(C) [ { l}, l 2 (P S) [ Sc} Proposition 7 The downward refinement operator ⇢ cOoIns is ideal.
The ideality of ⇢ cOoIns is owed to the peculiar structure of the search space when ordered by the relation OI . mgdrOI (C, N ) 5
Discussion and Extension of the Specialization
Operator The existing definition of ⇢ cOoIns 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 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:
P =
S Now, what we need to consider is S0c = ¬(S
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.
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: {C0 | head(C0) = head(C) ^ body(C0) = 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 permitted 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 sucient 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. 8 i : 9 l 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: – 8 r 2 (N, C) : • Pr = {Pi 2 P| r 2 • Pr = {Pi 2 P| r 62 – 8 S ✓ (N, C) : • PS = \ r2 S Pr • PS = [ r2 S Pr (Pi, C)} (Pi, C)} 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 residuals 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 \P u = {P1}\{ P2, P3} = ; ; P{s,u} = Ps \ Pu = {P2, P3}[{ P1} = P: SOLUTION! P{t,r} = Pt \ P r = {P1, P2} \ { P3} = ; ; P{t,r} = Pt \ Pr = {P3} [ { P1, P2} = P: SOLUTION! P{t,u} = Pt \ P u = {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 ecient 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:
This ensures, in particular, that PS = ; ^ PS = P , PS = ; , also note that positive example (un-)coverage is monotonic: 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 ⇢ cOoIns fails, then 8 r 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 = ; ) P S = ; ) |P S | = 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 Algorithm 1 Backtracking specialization strategy
S = ; ; R = repeat r
(N, C) select from R OR backtrack R R \ { r}; S0 S [ { r} if PS0 6= PS (, PS0 6= PS ) (, P S0 P S , PS0
S S 0 end if until PS = ; (, PS = P) OR no more backtracking available if PS = ; (, PS = P) then
return S else
return failure end if PS ) then 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 Object 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 deficiencies and proposes solutions that result in improved operators. Specifically, the downward refinement operator is considered. A preliminary prototype of the operator 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, abstraction and predicate invention. Experiments aimed at assessing the eciency and e↵ectiveness of the operator in real-world domains are also planned. Acknowledgments This work was partially funded by the Italian PON 2007-2013 project PON02 00563 3489339 ‘Puglia@Service’.