2.1 Answer set programming

A disjunctive rule R is of the form $\mathtt{h_1\lor\ldots\lor h_m\texttt{:- } b_1,\ldots,b_n,}$ $\mathtt{\texttt{not } c_1,\ldots,\texttt{not } c_o}$ , where $\lbrace\mathtt{h_1},\ldots,\mathtt{h_m} \rbrace$ , $\lbrace\mathtt{b_1},\ldots,\mathtt{b_n}\rbrace$ and $\lbrace\mathtt{c_1},\ldots,\mathtt{c_o}\rbrace$ are sets of atoms denoted $\textit{head}(R)$ , $\textit{body}^{+}(R)$ and $\textit{body}^{-}(R)$ , respectively. A normal rule R is a disjunctive rule such that $|\textit{head}(R)| = 1$ . A definite rule R is a disjunctive rule such that $|\textit{head}(R)| = 1$ and $|\textit{body}^{-}(R)| = 0$ . A hard constraint R is a disjunctive rule such that $|\textit{head}(R)| = 0$ . Sets of disjunctive, normal and definite rules are called disjunctive, normal and definite logic programs (respectively).

Given a (first-order) disjunctive logic program P, the Herbrand base ( $\textit{HB}_{P}$ ) is the set of all atoms constructed using constants, functions and predicates in P. The program $\textit{ground}(P)$ is constructed by replacing each rule with its ground instances (using only atoms from the Herbrand base). An (Herbrand) interpretation I (of P) assigns each element of $\textit{HB}_{P}$ to $\mathtt{\top}$ or $\mathtt{\bot}$ , and is usually written as the set of all elements in $\textit{HB}_{P}$ that I assigns to $\mathtt{\top}$ . An interpretation I is a model of P if it satisfies every rule in P; that is for each rule $R \in \textit{ground}(P)$ if $\textit{body}^{+}(R)\subseteq I$ and $\textit{body}^{-}(R)\cap I = \emptyset$ then $\textit{head}(R)\cap I \neq \emptyset$ . A model of P is minimal if no strict subset of P is also a model of P. The reduct of P wrt I (denoted $P^{I}$ ) is the program constructed from $\textit{ground}(P)$ by first removing all rules R such that $\textit{body}^{-}(R)\cap I \neq\emptyset$ and then removing all remaining negative body literals from the program. The answer sets of P are the interpretations I such that I is a minimal model of $P^I$ . The set of all answer sets of P is denoted $\textit{AS}(P)$ .

There is another way of characterising answer sets, by using unfounded subsets. Let P be a disjunctive logic program and I be an interpretation. A subset $U\subseteq I$ is unfounded (w.r.t. P) if there is no rule $R\in\textit{ground}(P)$ for which the following three conditions all hold: (1) $\textit{head}(R)\cap I\subseteq U$ ; (2) $\textit{body}^{+}(R)\subseteq I\backslash U$ ; and (3) $\textit{body}^{-}(R)\cap I = \emptyset$ . The answer sets of a program P are the models of P with no non-empty unfounded subsets w.r.t. P.

Unless otherwise stated, in this paper, the term ASP program is used to mean a program consisting of a finite set of disjunctive rules. ^{Footnote 2}

2.2 Learning from answer sets

The Learning from Answer Sets framework, introduced in (Law et al. Reference Law, Russo and Broda2014), is targeted at learning ASP programs. The basic framework has been extended several times, allowing learning weak constraints (Law et al. Reference Law, Russo and Broda2015), learning from context-dependent examples (Law et al. Reference Law, Russo and Broda2016) and learning from noisy examples (Law et al. Reference Law, Russo and Broda2018b). This section presents the ${ILP}_{{\scriptsize LAS}}^{{ \scriptsize noise}}$ learning framework, which is used in this paper. ^{Footnote 3}

Examples in ${ILP}_{{\scriptsize LAS}}^{{ \scriptsize noise}}$ are Context-dependent Partial Interpretations (CDPIs). CDPIs specify what should or should not be an answer set of the learned program. A partial interpretation $e_{\mathit{pi}}$ is a pair of sets of atoms $\langle e^{\mathit{inc}}, e^{\mathit{exc}}\rangle$ called the inclusions and the exclusions, respectively. An interpretation I extends $e_{\mathit{pi}}$ if and only if $e^{\mathit{inc}}\subseteq I$ and $e^{\mathit{exc}}\cap I = \emptyset$ . ^{Footnote 4} A Context-dependent Partial Interpretation e is a pair $\langle e_{\mathit{pi}}, e_{\mathit{ctx}}\rangle$ where $e_{\mathit{pi}}$ is a partial interpretation and $e_{\mathit{ctx}}$ (the context of e) is a disjunctive logic program. A program P is said to accept e if there is at least one answer set A of $P\cup e_{\mathit{ctx}}$ that extends $e_{\mathit{pi}}$ – such an A is called an accepting answer set of e w.r.t. P, written $A\in \textit{AAS}(e, P)$ .

heads(V1) :- coin(V1), not tails(V1).

tails(V1) :- coin(V1), not heads(V1).

• P accepts $e = \langle \langle\lbrace \mathtt{heads(c1)}\rbrace, \lbrace\mathtt{tails(c1)}\rbrace\rangle, \lbrace \mathtt{coin(c1)\texttt{.}}\rbrace\rangle$ . The only accepting answer set of e w.r.t. P is $\lbrace\mathtt{heads(c1)}, \mathtt{coin(c1)}\rbrace$ .

• P accepts $e = \langle \langle\lbrace \mathtt{heads(c1)}\rbrace$ , $\lbrace\mathtt{tails(c1)}\rbrace\rangle, \lbrace \mathtt{coin(c1)\texttt{.}\;\;coin(c2)\texttt{.}}\rbrace\rangle$ . The two accepting answer sets of e w.r.t. P are $\lbrace\mathtt{heads(c1)}$ , $\mathtt{heads(c1)}$ , $\mathtt{coin(c1)}$ , $\mathtt{coin(c2)}\rbrace$ and $\lbrace\mathtt{heads(c1)}$ , $\mathtt{tails(c1)}$ , $\mathtt{coin(c1)}$ , $\mathtt{coin(c2)}\rbrace$ .

• P does not accept $e = \langle \langle\lbrace \mathtt{heads(c1)}, \mathtt{tails(c1)}\rbrace, \emptyset\rangle, \lbrace \mathtt{coin(c1)\texttt{.}}\rbrace\rangle$ .

• P does not accept $e = \langle \langle\lbrace \mathtt{heads(c1)} \rbrace, \lbrace\mathtt{tails(c1)}\rbrace\rangle, \emptyset\rangle$ .

In learning from answer sets tasks, CDPIs are given as either positive (resp. negative) examples, which should (resp. should not) be accepted by the learned program.

Noisy examples.

In settings where all examples are correctly labelled (i.e. there is no noise), ILP systems search for a hypothesis that covers all of the examples. Many systems search for the optimal such hypothesis – this is usually defined as the hypothesis minimising the number of literals in H ( $|H|$ ). In real settings, examples are often not guaranteed to be correctly labelled. In these cases, many ILP systems (including ILASP) assign a penalty to each example, which is the cost of not covering the example. A CDPI e can be upgraded to a weighted CDPI by adding a penalty $e_{\mathit{pen}}$ , which is either a positive integer or $\infty$ , and a unique identifier, $e_{\mathit{id}}$ , for the example.

Learning task.

Definition 1 formalises the ${ILP}_{{\scriptsize LAS}}^{{ \scriptsize noise}}$ learning task, which is the input of the ILASP systems. A rule space $S_{M}$ (often called a hypothesis space and characterised by a mode bias ^{Footnote 5} M) is a finite set of disjunctive rules, defining the space of programs that are allowed to be learned. Given a rule space $S_{M}$ , a hypothesis H is any subset of $S_{M}$ . The goal of a system for ${ILP}_{{\scriptsize LAS}}^{{ \scriptsize noise}}$ is to find an optimal inductive solution H, which is a subset of a given rule space $S_M$ , that covers every example with infinite penalty and minimises the sum of the length of H plus the penalty of each uncovered example.

1. 1. $\mathcal{U}(H, T)$ is the set consisting of: (a) all positive examples $e \in E^{+}$ such that $B \cup H$ does not accept e; and (b) all negative examples $e \in E^{-}$ such that $B \cup H$ accepts e.

2. 2. the score of H, denoted as $\mathcal{S}(H, T)$ , is the sum $|H| + \sum_{e \in \mathcal{U}(H, T)} e_{pen}$ .

3. 3. H is an inductive solution of T (written $H \in {ILP}_{{\scriptsize LAS}}^{{ \scriptsize noise}}(T)$ ) if and only if $\mathcal{S}(H, T)$ is finite (i.e. H must cover all examples with infinite penalty).

4. 4. H is an optimal inductive solution of T (written $H \in$ $^*{ILP}_{{\scriptsize LAS}}^{{ \scriptsize noise}}(T)$ ) if and only if $\mathcal{S}(H, T)$ is finite and $\nexists H' \subseteq S_{M}$ such that $\mathcal{S}(H, T) > \mathcal{S}(H', T)$ .

3.1 The CDILP procedure

The algorithm presented in this section is a cycle comprised of four steps, illustrated in Figure 1. Step 1, the hypothesis search, computes an optimal solve result $\langle H, U, s\rangle$ w.r.t. the current set of coverage constraints. Step 2, the counterexample search, finds an example e which is not in U (i.e. an example whose coverage constraints are respected by H) that H does not cover. The existence of such an example e is called a conflict, and shows that the coverage constraints are incomplete. The third step, conflict analysis, resolves the situation by computing a new coverage constraint for e that is not respected by H. The fourth step, constraint propagation, is optional and only useful for noisy tasks. The idea is to check whether the newly computed coverage constraint can also be used for other examples, thus “boosting” the penalty that must be paid by any hypothesis that does not respect the coverage constraint and reducing the number of iterations of the CDILP procedure. The CDILP procedure is formalised by Algorithm 1.

Fig. 1.

The average computation time of ILASP3, ILASP4a and ILASP4b for the Hamilton learning task, with varying numbers of examples, with 5, 10 and 20% noise.

Hypothesis search.

The hypothesis search phase of the CDILP procedure finds an optimal solve result of the current CC if one exists; if none exists, it returns nil. This search is performed using Clingo. By default, this process uses Clingo 5’s (Gebser et al. Reference Gebser, Kaminski, Kaufmann, Ostrowski, Schaub and Wanko2016) C++ API to enable multi-shot solving (adding any new coverage constraints to the program and instructing the solver to continue from where it left off in the previous iteration). This multi-shot solving can be disabled by calling ILASP with the “–restarts” flag. This ASP program is entirely based on the coverage constraints and does not use the examples or background knowledge. This means that if checking the coverage of an example in the original object-level domain is computationally intensive (e.g. if it has a large grounding or the decision problem is NP-hard or higher), the hypothesis search phase can be much easier than solving a meta-level encoding of the background knowledge and examples because the hard aspects of the original problem have essentially been “compiled away” in the computation of the coverage constraints. For reasons of brevity, the actual ASP encodings are omitted from this paper, but detailed descriptions of very similar ASP encodings can be found in Law (Reference Law2018).

Counterexample search.

A counterexample to a solve result $\langle H, U, s\rangle$ , is an example e that is not covered by H and is not in U. The existence of such an example proves that the score s is lower than $\mathcal{S}(H, T)$ , and hence, H may not be an optimal solution of T. This search is again performed using Clingo, and is identical to the findRelevantExample method of ILASP2i (Law et al. Reference Law, Russo and Broda2016) and ILASP3 (Law Reference Law2018). If no counterexample exists, then by Corollary 1, H must be an optimal solution of T, and is returned as such; if not, the procedure continues to the conflict analysis step.

Conflict analysis.

Let $\langle H, U, s\rangle$ be the most recent solve result and ce be the most recent counterexample. The goal of this step is to compute a coverage formula F that does not accept H but that must hold for ce to be covered. The coverage constraint $\langle ce, F\rangle$ is then added to CC. This means that if H is computed in a solve result in the hypothesis search phase of a future iteration, then it will be guaranteed to be found with a higher score (including the penalty paid for not covering ce). There are many possible strategies for performing conflict analysis, several of which are presented in the next section and evaluated in Section 5. Beginning with ILASP version 4.0.0, the ILASP system allows a user to customise the learning process by providing a Python script (called a PyLASP script). Future versions of ILASP will likely contain many strategies, appropriate for different domains and different kinds of learning task. In particular, this allows a user to define their own conflict analysis methods. Provided the conflict analysis method is guaranteed to terminate and compute a coverage constraint whose coverage formula does not accept the most recent hypothesis, the customised CDILP procedure is guaranteed to terminate and return an optimal solution of T (resources permitting). We call such a conflict analysis method valid. The three conflict analysis methods presented in the next section are proven to be valid.

Constraint propagation.

The final step is optional (and can be disabled in ILASP with the flag “-ncp”). In a task with many examples with low penalties, but for which the optimal solution has a high score, there are likely to be many iterations required before the hypothesis search phase finds an optimal solution. This is because each new coverage constraint only indicates that the next hypothesis computed should either conform to the coverage constraint, or pay a very small penalty. The goal of constraint propagation is to find a set of examples which are guaranteed to not be covered by any hypothesis H that is not accepted by F. For each such example e, $\langle e, F\rangle$ can be added as a coverage constraint (this is called propagating the constraint to e). Any solve result containing a hypothesis that does not conform to F must pay the penalty not only for the counterexample ce, but also for every constraint that F was propagated to. In Section 5, it is shown that by lowering the number of iterations required to solve a task, constraint propagation can greatly reduce the overall execution time.

There are two methods of constraint propagation supported in the current version of ILASP. Both were used in ILASP3 and described in detail in Law (Reference Law2018) as “implication” and “propagation”, respectively. The first is used for positive examples and brave ordering examples, and for each example e searches for a hypothesis that is not accepted by F, but that covers e. If none exists, then the constraint can be propagated to e. The second method, for negative examples, searches for an accepting answer set of e that is guaranteed to be an answer set of $B\cup H\cup e_{ctx}$ for any hypothesis H that is accepted by F. A similar method is possible for propagating constraints to cautious orderings; however, our initial experiments have shown it to be ineffective in practice, as although it does bring down the number of iterations required, it adds more computation time than it saves. Similarly to the conflict analysis phase, users can provide their own strategy for constraint propagation in PyLASP, and in future versions of ILASP will likely have a range of alternative constraint propagation strategies built in.

Correctness of CDILP.

Theorem 2 proves the correctness of the CDILP approach. The proof of the theorem assumes that the conflict analysis method is valid (which is proven for the three conflict analysis methods presented in the next section). A well-formed task has finite number of examples, and for each example context C, the program $B\cup S_{M}\cup C$ has a finite grounding. The theorem shows that the CDILP approach is guaranteed to terminate, and is both sound and complete w.r.t. the optimal solutions of a task; i.e. any hypothesis returned is guaranteed to be an optimal solution and if at least one solution exists, then CDILP is guaranteed to return an optimal solution.

3.2 Comparison to previous ILASP systems

ILASP1 and ILASP2 both encode the search for an inductive solution as a meta-level ASP program. They are both iterative algorithms and use multi-shot solving (Gebser et al. Reference Gebser, Kaminski, Kaufmann, Ostrowski, Schaub and Wanko2016) to add further definitions and constraints to the meta-level program throughout the execution. However, the number of rules in the grounding of the initial program is roughly proportional to the number of rules in the grounding of $B\cup S_M$ (together with the rules in the contexts of each example) multiplied by the number of positive examples and (twice the number of) brave orderings (Law Reference Law2018). This means that neither ILASP1 nor ILASP2 scales well w.r.t. the number of examples.

ILASP2i attempts to remedy the scalability issues of ILASP2 by iteratively constructing a set of relevant examples. The procedure is similar to CDILP in that it searches (using ILASP2) for a hypothesis that covers the current set of relevant examples, and then searches for a counterexample to the current hypothesis, which is then added to the set of relevant examples before the next hypothesis search. This simple approach allows ILASP2i to scale to tasks with large numbers of examples, providing the final set of relevant examples stays relatively small (Law et al. Reference Law, Russo and Broda2016). However, as ILASP2i uses ILASP2 for the hypothesis search, it is still using a meta-level ASP program which has a grounding that is proportional to the number of relevant examples, meaning that if the number of relevant examples is large, the scalability issues remain.

The CDILP approach defined in this section goes further than ILASP2i in that the hypothesis search phase is now completely separate from the groundings of the rules in the original task. Instead, the program used by the hypothesis search phase only needs to represent the set of (propositional) coverage formulas.

The major advantage of the CDILP approach compared to ILASP2i (as demonstrated by the evaluation in Section 5) is on tasks with noisy examples. Tasks with noisy examples are likely to lead to a large number of relevant examples. This is because if a relevant example has a penalty it does not need to be covered during the hypothesis search phase. It may be required that a large number of “similar” examples are added to the relevant example set before any of the examples are covered. The CDILP approach overcomes this using constraint propagation. When the first example is found, it will be propagated to all “similar” examples which are not covered for the same “reason”. In the next iteration the hypothesis search phase will either have to attempt to cover the example, or pay the penalty of all of the similar examples.

4.1 Positive CDPI examples

In this section, we describe how the three conflict analysis methods behave when $\textit{conflict_analysis}(e, H, T)$ is called for a positive CDPI example e, a hypothesis H (which does not accept e) and a learning task T. Each of the three conflict analysis methods presented in this paper work by incrementally building a coverage formula which is a disjunction of the form $D_1\lor\ldots\lor D_n$ . The intuition is that in the $i^{th}$ iteration the algorithm searches for a hypothesis H’ that accepts e, but which is not accepted by $D_1\lor\ldots\lor D_{i-1}$ . The algorithm then computes an answer set I of $B\cup e_{ctx}\cup H'$ that extends $e_{pi}$ . If such an H’ exists, a coverage formula $D_i$ is computed (and added to the disjunction) s.t. $D_i$ does not accept H and $D_i$ is necessary for I to be an accepting answer set of e (i.e. $D_i$ is respected by every hypothesis that accepts e). We denote this formula $\psi(I, e, H, T)$ . If no such H’ exists then $F = D_1\lor\ldots\lor D_{i-1}$ is necessary for the example to be accepted and it will clearly not accept H (as none of the disjuncts accept H). It can therefore be returned as a result of the conflict analysis.

The overall conflict analysis methods are formalised by Algorithm 2. The three conflict analysis methods use different definitions of $\psi(I, e, H, T)$ , which are given later this section. Each version of $\psi(I, e, H, T)$ is linked to the notion of the translation of an interpretation I. Essentially, this is a coverage formula that is accepted by exactly those hypotheses H’ for which I is an answer set of $AS(B\cup e_{ctx}\cup H')$ . The translation is composed of two parts: first, a set of rules which must not appear in H’ for I to be an answer set – these are the rules for which I is not a model; and second, a set of disjunctions of rules – for each disjunction, at least one of the rules must appear in H’ for I to be an answer set. The notion of the translation of an interpretation is closely related to the definition of an answer set based on unfounded sets. For I to be an answer set, it must be a model of H and it must have no non-empty unfounded subsets w.r.t. $B\cup e_{ctx}\cup H'$ . For any H’ that is accepted by the translation, the first part guarantees that I is a model of H’, while the second part guarantees that there are no non-empty unfounded subsets of I, by ensuring that for each potential non-empty unfounded subset U there is at least one rule in H’ that prevents U from being unfounded.

1. 1. $\lnot R_{id}$ for each $R \in S_M$ such that I is not a model of R.

2. 2. $R_{id}^1\lor\ldots\lor R_{id}^n$ for each subset minimal set of rules $\lbrace R^1,\ldots,R^n\rbrace$ such that there is at least one non-empty unfounded subset of I w.r.t. $B\cup e_{ctx}\cup (S_{M}\backslash \lbrace R^1,\ldots,R^n\rbrace)$ .

We write $\mathcal{T}_1(I, e, T)$ and $\mathcal{T}_2(I, e, T)$ to refer to the conjunctions of coverage formulas in (1) and (2), respectively. Note that the empty conjunction is equal to $\top$ .

$B = \left\{\begin{array}{l} \mathtt{p \texttt{:- } \texttt{not } q.}\\ \mathtt{q \texttt{:- } \texttt{not } p.}\\ \end{array}\right\}$

$S_M = \left\{ \begin{array}{rl} h^1:& \mathtt{r \texttt{:- } t.}\\ h^2:& \mathtt{t \texttt{:- } q.}\\ h^3:& \mathtt{r.}\\ h^4:& \mathtt{s \texttt{:- } t.}\\ \end{array} \right\}$

Let e be a CDPI such that $e_{pi} = \langle \lbrace \mathtt{r}\rbrace, \emptyset\rangle$ , and $e_{ctx} = \emptyset$ . Consider the four interpretations $I_1 = \lbrace \mathtt{q}$ , $\mathtt{r}$ , $\mathtt{t}\rbrace$ , $I_2 = \lbrace \mathtt{q}$ , $\mathtt{r}\rbrace$ , $I_3 = \lbrace \mathtt{p}$ , $\mathtt{r}\rbrace$ and $I_4 = \lbrace \mathtt{q}$ , $\mathtt{r}$ , $\mathtt{s}$ , $\mathtt{t}\rbrace$ . The translations are as follows:

• $\mathcal{T}(I_1, e, T) = \lnot h^4_{id} \land (h^1_{id} \lor h^3_{id}) \land h^2_{id}$ .

• $\mathcal{T}(I_2, e, T) = \lnot h^2_{id} \land h^3_{id}$ .

• $\mathcal{T}(I_3, e, T) = h^3_{id}$ .

• $\mathcal{T}(I_4, e, T) = h^4_{id} \land (h^1_{id} \lor h^3_{id}) \land h^2_{id}$ .

The following theorem shows that for any interpretation I that extends $e_{pi}$ , the translation of I w.r.t. e is a coverage formula that captures the class of hypotheses H for which I is an accepting answer set of $B\cup H$ w.r.t. e.

Given the notion of a translation, one potential option for defining $\psi(I,e, H, T)$ would be to let $\psi(I, e, H, T) = \mathcal{T}(I, e, T)$ . In fact, this is exactly the approach adopted by the ILASP3 algorithm. We show later in this section that this results in a valid method for conflict analysis; however, the coverage constraints returned from this method can be extremely long, and computing them can require a large number of iterations of the $\textit{iterative_conflict_analysis}$ procedure. For that reason, it can be beneficial to use definitions of $\psi$ which return more general coverage formulas, resulting in more general coverage constraints that can be computed in fewer iterations. As the translation of an interpretation is a conjunction, $\psi(I, e, H, T)$ can be defined as the conjunction of any subset of the conjuncts of $\mathcal{T}(I, e, T)$ , so long as at least one of the conjuncts does not accept H. Definition 5 presents three such approaches.

• If I is a model of H, $\psi_{\alpha}(I, e, H, T)$ is an arbitrary conjunct of $\mathcal{T}_2(I, e, T)$ that does not accept H; otherwise, $\psi_{\alpha}(I, e, H, T) = \mathcal{T}_1(I, e, T)$ .

• If I is a model of H, $\psi_{\beta}(I, e, H, T) = \mathcal{T}_2(I, e, T)$ ; otherwise, $\psi_{\beta}(I, e, H, T) = \mathcal{T}_1(I, e, T)$ .

• $\psi_{\gamma}(I, e, H, T) = \mathcal{T}(I, e, T)$ .

• First, consider $\psi_{\alpha}$ . In the first iteration, $F = \bot$ , so we need to find an accepting answer set for any hypothesis in the space. One such accepting answer set is $I_1 = \lbrace \mathtt{q},$ $\mathtt{r},$ $\mathtt{t}\rbrace$ (which is an accepting answer set for $\lbrace h^2, h^3\rbrace$ ). $I_1$ is a model of H, so $\psi_{\alpha}$ will pick an arbitrary conjunct of $\mathcal{T}_2(I_1, e, T) = (h^1_{id} \lor h^3_{id})\land h^2_{id}$ that does not accept H. Let $D_1$ be $(h^1_{id} \lor h^3_{id})$ . F becomes $D_1$ at the start of the next iteration. At this point, there are no hypotheses that cover e that do not accept F. Hence, $(h^1_{id} \lor h^3_{id})$ is returned as the result of conflict analysis.

• Next, consider $\psi_{\beta}$ . Again, let $I_1 = \lbrace \mathtt{q},$ $\mathtt{r},$ $\mathtt{t}\rbrace$ (which is an accepting answer set for $\lbrace h^2, h^3\rbrace$ ). $I_1$ is a model of H, so $D_1 = \mathcal{T}_2(I_1, e, T) = (h^1_{id} \lor h^3_{id})\land h^2_{id}$ . F becomes $D_1$ at the start of the next iteration. Next, let $I_2 = \lbrace \mathtt{q},$ $\mathtt{r} \rbrace$ (which is an accepting answer set for $\lbrace h^3\rbrace$ ). $I_2$ is a model of H, so $D_2 = \mathcal{T}_2(I_2, e, T) = h^3_{id}$ . F becomes $D_1\lor D_2$ at the start of the next iteration. At this point, there are no hypotheses that cover e that do not accept F. Hence, $((h^1_{id} \lor h^3_{id}) \land h^2_{id})\lor h^3_{id}$ is returned as the result of conflict analysis.

• Finally, consider $\psi_{\gamma}$ . In the first iteration, $F = \bot$ . Again, let $I_1 = \lbrace \mathtt{q},$ $\mathtt{r},$ $\mathtt{t}\rbrace$ (which is an accepting answer set for $\lbrace h^2, h^3\rbrace$ ). $D_1 = \mathcal{T}(I_1, e, T) = (h^1_{id} \lor h^3_{id})\land h^2_{id}\land \lnot h^4_{id}$ . F becomes $D_1$ at the start of the next iteration. Next, let $I_2 = \lbrace \mathtt{q},$ $\mathtt{r} \rbrace$ (which is an accepting answer set for $\lbrace h^3\rbrace$ ). $D_2 = \mathcal{T}(I_2, e, T) = h^3_{id} \land \lnot h^2$ . F becomes $D_1\lor D_2$ at the start of the next iteration. Let $I_3 = \lbrace \mathtt{q},$ $\mathtt{r},$ $\mathtt{s},$ $\mathtt{t}\rbrace$ (which is an accepting answer set for $\lbrace h^2, h^3, h^4\rbrace$ ). $D_3 = \mathcal{T}(I_3, e, T) = (h^1_{id} \lor h^3_{id}) \land h^3 \land h^4_{id}$ . F becomes $D_1 \lor D_2 \lor D_3$ at the start of the next iteration. At this point, there are no hypotheses that cover e that do not accept F. Hence, $ ((h^1_{id} \lor h^3_{id}) \land h^2_{id} \land \lnot h^4_{id}) \lor (h^3_{id} \land \lnot h^2) \lor ((h^1_{id} \lor h^3_{id}) \land h^2_{id} \land h^4_{id}) $ is returned as the result of conflict analysis.

This example shows the differences between the different $\psi$ ’s. $\psi_{\gamma}$ , used by ILASP3, essentially results in a complete translation of the example e – the coverage formula is satisfied if and only if the example is covered. $\psi_{\alpha}$ , on the other hand, results in a much smaller coverage formula, which is computed in fewer steps, but which is only necessary (and not sufficient) for e to be covered. Consequently, when $\psi_{\alpha}$ is used, it may be necessary for multiple conflict analysis steps on the same example – for instance, a future hypothesis search phase might find $\lbrace h^1\rbrace$ , which satisfies the coverage formula found using $\psi_{\alpha}$ but does not cover e. $\psi_{\alpha}$ and $\psi_{\gamma}$ are two extremes: $\psi_{\alpha}$ finds very short, easily computable coverage formulas and may require many iterations of the CDILP algorithm for each example; and $\psi_{\gamma}$ finds very long coverage formulas that may take a long time to compute, but only requires at most one iteration of the CDILP algorithm per example. $\psi_{\beta}$ provides a middle ground. In this example, it finds a formula which is equivalent to the one found by $\psi_{\gamma}$ but does so in fewer iterations.

The following two theorems show that for each of the three version of $\psi$ presented in Definition 5, the iterative conflict analysis algorithm is guaranteed to terminate and is a valid method for computing a coverage constraint for a positive CDPI.

1. 1. $F_{\psi}$ does not accept H.

2. 2. If e is a positive example, the pair $\langle e, F_{\psi}\rangle$ is a coverage constraint.

4.2 Negative CDPI examples

This section presents two methods of conflict analysis for a negative CDPI e. The first, used by ILASP3, is to call $iterative\_conflict\_analysis(e, H, T,\psi_{\gamma})$ . As the result of this is guaranteed to return a coverage formula F that is both necessary and sufficient for e to be accepted, the negation of this formula ( $\lnot F$ ) is guaranteed to be necessary and sufficient for e to not be accepted – that is for e to be covered (as e is a negative example). This result is formalised by Theorem 5.

The method for computing a necessary constraint for a negative CDPI e is much simpler than for positive CDPIs. Note that each disjunct in the formula F computed by $\textit{iterative_conflict_analysis}(e, H, T, \psi_{\gamma})$ is sufficient but not necessary for the CDPI e to be accepted (i.e. for e to not be covered, as it is a negative example), and therefore its negation is necessary but not sufficient for e to be covered. This means that to compute a necessary constraint for a negative CDPI, we only need to consider a single interpretation. This is formalised by the following theorem. The approach used in ILASP4 computes an arbitrary such coverage formula. Note that this is guaranteed to terminate and the following theorem shows that the method is a valid method for conflict analysis.

1. 1. $\lnot \mathcal{T}(I, e, T)$ does not accept H.

2. 2. $\langle e, \lnot \mathcal{T}(I, e, T)\rangle$ is a coverage constraint.

As shown by Theorem 3, $\mathcal{T}(I_1, e, T)$ is accepted by exactly those hypotheses H’ s.t. $I_1 \in AAS(e, B\cup H')$ . Hence, any hypothesis that accepts F does not cover e. Therefore $\langle e, \lnot \mathcal{T}(I_1, e, T)\rangle$ is a coverage constraint.

4.3 ILASP3 and ILASP4

ILASP3 and ILASP4 are both instances of the CDILP approach to ILP formalised in this paper. The difference between the two algorithms is their approaches to conflict analysis.

ILASP3 uses $\psi_{\gamma}$ for conflict analysis on positive examples and essentially uses the same approach for negative examples, negating the resulting coverage formula (Theorem 5 proves that this is a valid method for conflict analysis). Hence, by Theorem 2, ILASP3 is sound and complete and is guaranteed to terminate on any well-formed learning task.

The conflict analysis methods adopted by ILASP3 may result in extremely long coverage constraints that take a very long time to compute. This is more apparent on some learning problems than others. The following definition defines two classes of learning task: categorical learning tasks for which all programs that need to be considered to solve the task have a single answer set; and non-categorical learning tasks, in which some programs have multiple answer sets. The performance of ILASP3 and ILASP4 on categorical learning tasks is likely to be very similar, whereas on non-categorical tasks, ILASP3’s tendency to compute long coverage constraints is more likely to be an issue, because larger numbers of answer sets tend to lead to longer coverage constraints.

In the evaluation in the next section, we consider two versions of ILASP4. The first (ILASP4a) uses $\psi_{\alpha}$ and the coverage constraints for negative examples defined in Theorem 6. The second (ILASP4b) uses $\psi_{\beta}$ and the same notion of coverage constraints for negative examples. As we have shown that these approaches to conflict analysis are valid, both ILASP4a and ILASP4b are sound and complete and are guaranteed to terminate on any well-formed learning task. Both approaches produce more general coverage constraints than ILASP3 (with ILASP4b being a middle ground between ILASP4a and ILASP3), meaning that each iteration of the CDILP approach is likely to be faster (on non-categorical tasks). The trade-off is that whereas in ILASP3 the coverage constraint computed for an example e is specific enough to rule out any hypothesis that does not cover e, meaning that each example will be processed at most once, in ILASP4, this is not the case and each example may be processed multiple times. So ILASP4 may have a larger number of iterations of the CDILP procedure than ILASP3; however, because each of these iterations is likely to be shorter, in practice, ILASP4 tends to be faster overall. This is supported by the experimental results in the next section.

5.1 Comparison between ILASP versions on benchmark tasks

In (Law et al. Reference Law, Russo and Broda2016), ILASP was evaluated on a set of non-noisy benchmark problems, designed to test all functionalities of ILASP at the time (at that time, ILASP was incapable of solving noisy learning tasks). The running times of all incremental versions of ILASP (ILASP1 and ILASP2 are incapable of solving large tasks) on two of these benchmarks are shown in Table 1. ^{Footnote 7} The remaining results are available in Appendix A, showing how the different versions of ILASP compare on weak constraint learning tasks.

Table 1.

The running times (in seconds) of various ILASP systems on the set of benchmark problems. TO denotes a timeout (where the time limit was 1800s).

The first benchmark problem is to learn the definition of whether a graph is Hamiltonian or not (i.e. whether it contains a Hamilton cycle). The background knowledge is empty and each example corresponds to exactly one graph, specifying which $\mathtt{node}$ and $\mathtt{edge}$ atoms should be true. Positive examples correspond to Hamiltonian graphs, and negative examples correspond to non-Hamiltonian graphs. This is the context-dependent “Hamilton B” setting from Law et al. (Reference Law, Russo and Broda2016). ILASP2i and both versions of ILASP4 perform similarly, but ILASP3 is significantly slower than the other systems. This is because the Hamiltonian learning task is non-categorical and the coverage formulas generated by ILASP3 tend to be large. This experiment was repeated with a “noisy” version of the problem where 5% of the examples were mislabelled (i.e. positive examples were changed to negative examples or negative examples were changed to positive examples). To show the scalability issues with ILASP2i on noisy learning tasks, three versions of the problem were run, with 60, 120 and 180 examples. ILASP2i’s execution time rises rapidly as the number of examples grows, and it is unable to solve the last two tasks within the time limit of 30 minutes. ILASP3 and ILASP4 are all able to solve every version of the task in far less than the time limit, with ILASP4b performing best. The remaining benchmarks are drawn from non-noisy datasets, where ILASP2i performs fairly well.

The second setting originates from Law et al. (Reference Law, Russo and Broda2014) and is based on an agent learning the rules of how it is allowed to move within a grid. Agent A requires a hypothesis describing the concept of which moves are valid, given a history of where an agent has been. Examples are of the agent’s history of moving through the map and a subset of the moves which were valid/invalid at each time point in its history. Agent B requires a similar hypothesis to be learned, but with the added complexity that an additional concept is required to be invented (and used in the rest of the hypothesis). In Agent C, the hypothesis from Agent A must be learned along with a constraint ruling out histories in which the agent visits a cell twice (not changing the definition of valid move). This requires negative examples to be given, in addition to positive examples. Although scenarios A and C are technically non-categorical, scenario B causes more of an issue for ILASP3 because of the (related) challenge of predicate invention. The potential to invent new predicates which are unconstrained by the examples means that there are many possible answer sets for each example, which leads ILASP3 to generate extremely long coverage formulas. In this case ILASP3 is nearly two orders of magnitude slower than either version of ILASP4. As the Agent tasks are non-noisy and have a relatively small problem domain, ILASP2i solves these task fairly easily and, in the case of Agent A and Agent B, in less time than either version of ILASP4. On simple non-noisy tasks, the computation of coverage constraints are a computational overhead that can take longer than using a meta-level approach such as ILASP2i.

5.2 Comparison between methods for conflict analysis on a synthetic noisy dataset

In Law et al. (Reference Law, Russo and Broda2018b), ILASP3 was evaluated on a synthetic noisy dataset in which the task is to learn the definition of what it means for a graph to be Hamiltonian. This concept requires learning a hypothesis that contains choice rules, recursive rules and hard constraints, and also contains negation as failure. The advantage of using a synthetic dataset is that the amount of noise in the dataset (i.e. the number of examples which are mislabelled) can be controlled when constructing the dataset. This allows us to evaluate ILASP’s tolerance to varying amounts of noise. ILASP1, ILASP2 and ILASP2i (although theoretically capable of solving any learning task which can be solved by the later systems) are all incapable of solving large noisy learning tasks in a reasonable amount of time. Therefore, this section only presents a comparison of the performance of ILASP3 and ILASP4 on the synthetic noisy dataset from Law et al. (Reference Law, Russo and Broda2018b).

For $n = 20, 40, \ldots, 200$ , n random graphs of size one to four were generated, half of which were Hamiltonian. The graphs were labelled as either positive or negative, where positive indicates that the graph is Hamiltonian. Three sets of experiments were run, evaluating each ILASP algorithm with 5%, 10% and 20% of the examples being labelled incorrectly. In each experiment, an equal number of Hamiltonian graphs and non-Hamiltonian graphs were randomly generated and 5%, 10% or 20% of the examples were chosen at random to be labelled incorrectly. This set of examples were labelled as positive (resp. negative) if the graph was not (resp. was) Hamiltonian. The remaining examples were labelled correctly (positive if the graph was Hamiltonian; negative if the graph was not Hamiltonian). Figures 1 and 2 show the average running time and accuracy (respectively) of each ILASP version with up to 200 example graphs. Each experiment was repeated 50 times (with different randomly generated examples). In each case, the accuracy was tested by generating a further 1000 graphs and using the learned hypothesis to classify the graphs as either Hamiltonian or non-Hamiltonian.

Fig. 2.

The average accuracies of ILASP3, ILASP4a and ILASP4b for the Hamilton learning task, with varying numbers of examples, with 5, 10 and 20% noise.

The experiments show that each of the three conflict-driven ILASP algorithms (ILASP3, ILASP4a and ILASP4b) achieve the same accuracy on average (this is to be expected, as each system is guaranteed to find an optimal solution of any task). They each achieve a high accuracy (of well over 90%), even with 20% of the examples labelled incorrectly. A larger percentage of noise means that ILASP requires a larger number of examples to achieve a high accuracy. This is to be expected, as with few examples, the hypothesis is more likely to “overfit” to the noise, or pay the penalty of some non-noisy examples. With large numbers of examples, it is more likely that ignoring some non-noisy examples would mean not covering others, and thus paying a larger penalty. The computation time of each algorithm rises in all three graphs as the number of examples increases. This is because larger numbers of examples are likely to require larger numbers of iterations of the CDILP approach (for each ILASP algorithm). Similarly, more noise is also likely to mean a larger number of iterations. The experiments also show that on average, both ILASP4 approaches perform around the same, with ILASP4b being marginally better than ILASP4a. Both ILASP4 approaches perform significantly better than ILASP3. Note that the results reported for ILASP3 on this experiment are significantly better than those reported in Law et al. (Reference Law, Russo and Broda2018b). This is due to improvements to the overall ILASP implementation (shared by ILASP3 and ILASP4).

The effect of constraint propagation.

The final experiment in this section evaluates the benefit of using constraint propagation on noisy learning tasks. The idea of constraint propagation is that although it itself takes additional time, it may decrease the number of iterations of the conflict-driven algorithms, meaning that the overall running time is reduced. Figure 3 shows the difference in running times between ILASP4a with and without constraint propagation enabled on a repeat of the Hamilton 20% noise experiment. Constraint propagation makes a huge difference to the running times demonstrating that this feature of CDILP is a crucial factor in ILASP’s scalability over large numbers of noisy examples.

Fig. 3.

The average running times of ILASP4a with and without constraint propagation enabled for the Hamilton learning task with 20% noise.