Under consideration for publication in Theory and Practice of Logic Programming

1

arXiv:1802.07966v1 [] 22 Feb 2018

Incremental and Iterative Learning of Answer Set
Programs from Mutually Distinct Examples
Arindam Mitra and Chitta Baral
Arizona State University
(e-mail: {amitra,chitta}@asu.edu)
submitted 1 January 2003; revised 1 January 2003; accepted 1 January 2003

Abstract
Over these years the Artificial Intelligence (AI) community has produced several datasets which have given
the machine learning algorithms the opportunity to learn various skills across various domains. However, a
subclass of these machine learning algorithms that aimed at learning logic programs, namely the Inductive
Logic Programming algorithms, have often failed at the task due to the vastness of these datasets. This
has impacted the usability of knowledge representation and reasoning techniques in the development of
AI systems. In this research, we try to address this scalability issue for the algorithms that learn Answer
Set Programs. We present a sound and complete algorithm which takes the input in a slightly different
manner and perform an efficient and more user controlled search for a solution. We show via experiments
that our algorithm can learn from two popular datasets from machine learning community, namely bAbl (a
question answering dataset) and MNIST (a dataset for handwritten digit recognition), which to the best of
our knowledge was not previously possible. The system is publicly available at https://goo.gl/KdWAcV.
KEYWORDS: Inductive Logic Programming, Answer Set Programming, Question Answering, Handwritten
Digit Recognition, Context Dependent Learning.

1 Introduction
Answer Set Programming has emerged as a powerful tool for knowledge representation and
reasoning. To use this tool for an application, however, one needs application specific knowledge.
For e.g., if a system uses answer set programming to answer the question from column 1 in Table
1 the system needs to know that “X is to the right of Y IF Y is to the left of Z and Z is above X”.
Inductive Logic Programming algorithms aim to learn these kinds of knowledge from dataset.
However, existing ILP algorithms have limited scalabilty and often fail to learn knowledge from a
machine learning dataset. This leads to manual construction of knowledge base which can be very
time consuming and may not be practical sometimes. For e.g. for applications where an effective
representation of the rules is unknown, such as for the case of handwritten digit recognition (Fig.
1), one may need to try several representations before settling down for a winner. However, this
may be unrealistic given that MNIST dataset (Fig. 1) contains 50, 000 examples and writing down
the rules that explain all these examples for a particular choice of representation will take a long
amount of time.
In this work, we consider this scalability issue. We observe that one major obstruction in scalability arises from the discrepancy between the definition of Inductive Logic Programming and the

2

Arindam Mitra and Chitta Baral

The square is above the rectangle.
x The triangle is to the left of the
square.
Is the rectangle to the right of the
triangle?
y Yes

The square is below the rectangle.
The triangle is to the right of the
square.
Is the rectangle to the right of the
triangle?
No

The square is below the rectangle.
The triangle is to the right of the
square.
Is the triangle below the rectangle?
Yes

Table 1: A set of examples taken from the Task 17 of bAbI question answering dataset.

Fig. 1: A set of images from the MNIST dataset.
structure of a machine learning dataset. The learning problem in Inductive Logic Programming
is defined as follows (Muggleton 1991):
Definition 1 (Inductive Logic Programming)
Given a set of positive examples E + , negative examples E − and some background knowledge B,
an ILP algorithm finds an Hypothesis H such that,
B ∪ H |= E + , B ∪ H 6|= E −
The hypothesis space is restricted with a language bias that is specified by a series of mode
declarations M.
A machine learning dataset on the other hand contains a series of < x, y > pairs, x being the
input and y being the desired output (Table 1). To work with an ILP algorithm, one needs to first
convert the < x, y > pairs in the format of < B, E + , E − >. The conversion process is carried out
by the user and so there might be some variations. However, normally the sets E + and E − are
created using y’s and the x’s go inside B. Extra care is taken so that different < x, y > pairs do
not interfere with each other. Table 2(a) shows one example of this process. Since the number of
< x, y > pairs are usually large, the problem instance becomes too big for the ILP solvers to handle
. For example, consider someone wants to employ an ILP algorithm to learn from a question
answering task from bAbI dataset (Weston et al. 2015), which contains 1, 000 comprehension
examples similar to the ones in Table 1. The resulting background knowledge B will contain
10, 000 facts and E + will contain 1, 000 positive annotations pertaining to answers and E − will
contain a total of 1, 000 negative examples describing what is not an answer for each questions.
An ILP solver such as XHAIL (Ray 2009) will throw memory errors when given an input of
this size. The question that we ask here is “can we find a solution to the ILP problem without
considering all the < x, y > pairs together ?” We show that the answer is yes. In fact it is possible
to find a solution considering only one < x, y > pair at a time. To achieve this we model the
learning task as follows:
Definition 2 (Inductive Logic Programming for Distinct Examples)
An Inductive Logic Programming for Distinct Examples task ILPDE is a tuple hB, M, Di, where B

Theory and Practice of Logic Programming

3

is an Answer Set Program, called the background knowledge, M defines the set of rules allowed
in hypotheses (the hypothesis space) and D is the dataset containing a series of context dependent
examples < E1 , E2 , ..., En >. Here each Ei is a tuple hOi , Ei+ , Ei− i where, Oi is a logic program,
called observation , E + is a set of positive ground literals and E − is a set of negative ground
literals. A hypothesis H is an inductive solution of T (written as H ∈ ILPDE (B, M, D)) iff,
H ∪ B ∪ Oi ` Ei+ , ∀i = 1...n
H ∪ B ∪ Oi 0 Ei− , ∀i = 1...n
In this formulation, each example hOi , Ei+ , Ei− i directly corresponds to a < x, y > pair and it
takes into consideration that there are several distinct examples in a dataset, so there is no need to
explicitly isolate them from each other . Table 2(b) shows the encoding of the running example
in the format of ILPDE . It turns out that the ILPDE task described here is a simplification of
the Context-dependent Learning from Ordered Answer Sets task proposed in (Law et al. 2016).
However, to solve the Context-dependent Learning from Ordered Answer Sets task the authors in
(Law et al. 2016) convert it to a standard ILP problem which creates the same scalability issue.
Table 2: The sample predicate is used to separate different examples. The constants tri, rec, sq
respectively denote triangle, rectangle and square. holdsAt(rp(sq, rec, above), 1) says that the
square is to the above of the rectangle at time point 1.
ans(X, no) ← not ans(X, yes), id(X).
sample(1, holdsAt(rp(sq, rec, above), 1)).
sample(1, holdsAt(rp(tri, sq, le f t), 1)).
ans(1, yes) ←
sample(1, holdsAt(rp(rec, tri, right), 1)).
sample(2, holdsAt(rp(sq, rec, below), 1)).
B sample(2, holdsAt(rp(tri, sq, right), 1)).
ans2(yes) ←
sample(2, holdsAt(rp(rec, tri, right), 1)).
sample(3, holdsAt(rp(tri, sq, le f t), 1)).
sample(3, holdsAt(rp(tri, sq, le f t), 1)).
ans(3, yes) ←
sample(3, holdsAt(rp(tri, rec, below), 1)).
E + {ans(1, yes),ans(2, no),ans(3, yes).}
E − {ans(1, no),ans(2, yes),ans(3, no).}
(a) An ILP encoding of the problem in Table 1

E1

E2

E3

holdsAt(rp(sq, rec, above), 1).
O1 holdsAt(rp(tri, sq, le f t), 1).
ans(yes) ← holdsAt(rp(rec, tri, right), 1).
E1+ {ans(yes)}
E1− {ans(no)}
holdsAt(rp(sq, rec, below), 1).
O2 holdsAt(rp(tri, sq, right), 1).
ans(yes) ← holdsAt(rp(rec, tri, right), 1).
E2+ {ans(no)}
E2− {ans(yes)}
holdsAt(rp(tri, sq, le f t), 1).
O3 holdsAt(rp(tri, sq, le f t), 1).
ans(yes) ← holdsAt(rp(tri, rec, below), 1).
E3+ {ans(yes)}
E3− {ans(no)}

(b) An ILPDE encoding of the problem in Table 1

It should be noted that any standard ILP problem hB, M, E + , E − i can be thought of as an ILPDE
problem with only one example, h{}, M, h(B, E + , E − )ii. Similarly any ILPDE task can be converted
to an ILP task. However, utilizing the ‘distinctness’ property of the examples we can do better.
The algorithm that we propose here roughly works as follows: Given an instance of the ILPDE
task, it first finds a solution H1 of E1 . Then it expands H1 minimally to solve only E2 and
obtains H2 . In the next iteration it again expands H2 minimally to solve E1 and it continues
expanding until it finds a hypothesis that solves both E1 and E2 . Next it starts with a solution of
hE1 , E2 i and tries to expand it iteratively until it solves all of E1 , E2 and E3 . The process continues
until a hypothesis is found that explains all the examples. Section 3 describes the algorithm. We
show that the algorithm is sound and complete when H ∪ B ∪ Oi is stratified for all i = 1, ..., n.

4

Arindam Mitra and Chitta Baral

Our algorithm allows more control over the mode declarations (Section 2) which can lead to
noticeable speed up in the search process. We evaluate our algorithm on two popular datasets:
1) a question answering dataset published by Facebook AI Research (Weston et al. 2015) and 2)
a handwritten digit recognition database (LeCun 1998). To the best of our knowledge no sound
and complete ILP algorithm could learn from these two datasets. The work of (Mitra and Baral
2016) that learns from the bAbl dataset uses a modification of an existing ILP algorithm and the
resulting algorithm is not complete. We discuss this further in section 5.

2 Background
In this section, we describe the type of the rules that our algorithm can deal with, the syntax of
the mode declarations ans the XHAIL algorithm which plays a crucial role in our algorithm.
Answer Set Programming
An answer set program is a collection of rules of the form,
L0 ← L1 , ..., Lm , not Lm+1 , ..., not Ln
where each of the Li ’s is a literal in the sense of a classical logic. Intuitively, the above rule means
that if L1 , ..., Lm are true and if Lm+1 , ..., Ln can be safely assumed to be false then L0 must be true.
The left-hand side of an ASP rule is called the head and the right-hand side is called the body.
Predicates and ground terms in a rule start with a lower case letter, while variable terms start
with a capital letter. We will follow this convention throughout the paper. A rule with no head
is called a constraint. A rule with empty body is referred to as a f act. The semantics of ASP is
based on the stable model semantics of logic programming (Gelfond and Lifschitz 1988). In this
work, both the background knowledge B and the solution H are collection of such ASP rules.
Mode Declarations
Given a set of positive examples E + , negative examples E − and some background knowledge B,
an ILP algorithm computes a set of rules H so that B ∪ H |= E. The rules in H are often restricted
with a language bias that is specified by a series of mode declarations M (Muggleton 1995). One
can think of this as a way of injecting expert knowledge for the learning task.
There are two types of mode declarations, namely modeh declarations and modeb declarations.
A modeh(s) declaration (Table 3) specifies a literal s that can appear as the head of a rule in H.
A modeb(s) declaration (Table 3) specifies a literal s that can appear in the body of a rule. The
argument s is called schema and comprises of two parts: 1) an identifier for the literal and 2) a
list of placemakers for each argument of that literal. A placemaker is either +type (input), -type
(output) or #type (constant), where type denotes the type of the argument. An answer set rule is
in the hypothesis space defined by M (call it L(M)) if and only if its head (resp. each of its body
literals) is constructed from the schema s in a modeh(s) (resp. in a modeb(s)) in L(M)) as follows:
- By replacing an output (-) placemaker by a new variable.
- By replacing an input (+) placemaker by a variable that appears in the head or in a previous
body literal.
- By replacing a ground (#) placemaker by a ground term.

Theory and Practice of Logic Programming

5

Table 3 shows a set of mode declarations M sample that one can use to solve the example problem in Table 1.There is only one modeh(s) declaration in M sample , where the schema is holdsAt(relativeposition(+op1,+op1, $direction), +time ). Assuming there are only four constants of
type directions, the set of possible head literals are:



holdsAt(relativeposition(X, Y, le f t), T ), 














 holdsAt(relativeposition(X, Y, right), T ), 







holdsAt(relativeposition(X, Y, above), T ),








 holdsAt(relativeposition(X, Y, below), T ) 
Where X and Y are variables of type op1 and T has type time. There are three modeb declarations and they restrict additions of literals to the body as directed by their individual schema. Note
that rule “holdsAt(relativeposition(X, Y, le f t), T ) ← holdsAt(relativeposition(Z, X, above), T ),
holdsAt(relativeposition(Y, Z, right), T ).” is in L(M sample ), as the head is allowed by the modeh
and the third modeb allows the addition of holdsAt(relativeposition(Z, X, above), T ) with Z being
an output (new) variable and the first modeb allows the addition of holdsAt(relativeposition(Y, Z,
right), T ), as all the associated variables Y, Z and T have appeared before.
#modeh holdsAt(relativeposition(+op1,+op1,$direction),+time).
#modeb holdsAt(relativeposition(+op1,+op1,$direction),+time).
#modeb holdsAt(relativeposition(+op1,-op1,$direction),+time).
#modeb holdsAt(relativeposition(-op1,+op1,$direction),+time).

Table 3: Mode declarations for the problem of Table 1
Additionally, weights can be assigned to modeh and modeb (written as #modeh(s)=w) and
express the cost that is involved when a mode declaration is used. The default weight for mode
declarations is 1. Existing implementations of the ILP algorithms, take only one set of mode
declarations and thus all the modeh declarations share the same set of modebs. Our algorithm
allows the user to provide modeh specific modeb declarations. This additional feature allows the
user to provide more supervision in the search procedure and makes the search faster.
XHAIL
The XHAIL (Ray 2009) algorithm plays a crucial role in the algorithm that we present here.
In this section, we describe various concepts and notations associated the XHAIL algorithm.
Given an ILP task ILP(B, M, E = {E + ∪ E − }), XHAIL (Ray 2009) derives the hypothesis in three
steps, namely the abductive step, the deductive step and the inductive step. We will explain these
steps with respect to the example E1 from Table 2(b). The set B contains the representation of
x1 , denoted as O1 and the set E contains annotations derived from y1 . M is the set of mode
declarations described in Table 3.
Abductive Step
In the first step XHAIL finds a set of ground (variable free) atoms 4 = {α1 , ..., αn } such that
B ∪ 4 |= E, where each αi is a ground instance of the modeh(s) declaration atoms. For the running

6

Arindam Mitra and Chitta Baral

example there is only one modeh declaration. Thus the set 4 can contain ground instances of
only holdsAt(relativeposition(X, Y, Z), T ). In the following we show one possible 4 that meets
the above requirement.
n
o
4 = holdsAt(relativeposition(rectangle, triangle, right), 1)

Deductive Step
i
In the second step, XHAIL computes a clause αi ← δ1i ...δm
i for each αi in 4, where B ∪ 4 |=
j
i
δi , ∀1 ≤ i ≤ n, 1 ≤ j ≤ mi and each clause αi ← δ1i ...δm
i is a ground instance of a rule in L(M). In the
running example, 4 contains only one atom, α1 = holdsAt(relativeposition(rectangle, triangle,
right), 1) which is initialized to the head of the clause k1 . The body of k1 is saturated by adding
all possible ground instances of the literals in modeb(s) declarations that satisfy the constraints
mentioned above. There are two ground instances, holdsAt(relativeposition(rectangle, triangle,
right), 1) and holdsAt(relativeposition(rectangle, triangle, right), 1), of the literals in the modeb(s)
declarations and both of them can be added to the body as specified by M. In the following we
show the set of ground clauses K (called kernel) constructed in this step and their variabilized
version Kv (called generalization) that is obtained by replacing all input and output terms by
variables.





holdsAt(relativeposition(rectangle, triangle, right), 1)










K=
←
holdsAt(relativeposition(square,
rectangle,
above),
1),










holdsAt(relativeposition(triangle, square, le f t), 1). 




holdsAt(relativeposition(X, Y, right), T )










Kv = 
←
holdsAt(relativeposition(Z,
X,
above),
T
),










holdsAt(relativeposition(Y, Z, le f t), T ). 

Inductive Step
In this step XHAIL tries to find a compressive theory H by selecting from Kv as little literals as
possible while ensuring that B ∪ H |= E. For this example, working out this problem will lead to
an unique solution,
n
o
H = holdsAt(relativeposition(X, Y, right), T ).
which contains a single rule with empty body. In general, the compression process may lead to
multiple options for H.
Let < HI , HG , 4 > denote a solution returned by XHAIL(B, M, E), where HG is the generalization computed from 4 and HI is a compressed version of HG that solves E. It should be noted that
there might be many choices for 4 and correspondingly there might be many possible solutions
< HI , HG , 4 >. In the following table, we define few notations which will be useful later.

Theory and Practice of Logic Programming

7

Notations
XHAIL(B,M,E) The set of all the solutions hHI , HG , 4i to the problem P = ILP(B, M, E),
where HI is minimal i.e. no compressed version of HI can solve P.
4(B, M, E)
{4|hHI , HG , 4i ∈ XHAIL(B, M, E) for some HI , HG }.
HG (B, M, E)
{HG |hHI , HG , 4i ∈ XHAIL(B, M, E) for some 4, HI }.
HG (4)
The generalization computed from 4.

3 Algorithm
XHAIL can compute the solutions of ILP(BE1 , M, {E + , E − }E1 ). However how to compute the solutions of ILPDE (B, M, hE1 , E2 i) without solving the standard inductive logic programming task
constructed from E1 and E2 (denoted by ILP(BE1 ,E2 , M, {E + , E − }E1 ,E2 )) ? This section addresses
this question. Before that we define following terms which will be needed for the discussion.
Definition 3
H1 ≤ H2 Two answer set programs H1 and H2 are related by “≤” (denoted as H1 ≤ H2 ) if and
only if H1 can be transformed into H2 by either adding new rules to H1 or by adding new literals
in the body of the existing rules.
Definition 4
Minimality A solution H of ILP(B, M, E) is minimal iff @H 0 < H in L(M) that solves ILP(B, M, E).
Definition 5
Distinctness A series of examples Ei hOi , Ei+ , Ei− i, i = 1...n are said to be distinct iff, ∆(B ∪ O1 ∪
...∪On , M, ∪ni=1 Ei+ , ∪ni=1 Ei− ) = {∪ni=1 4i |(41 , ..., 4n ) ∈ ∆(B∪O1 , M, E1+ , E1− )×...×∆(B∪On , M, En+ , En− )}.
A series of examples Ei hOi , Ei+ , Ei− i, i = 1...n are said to be mutually distinct iff all subset of the
examples are distinct.
Now consider the two examples E1 and E2 . Since E1 and E2 are distinct examples constructed from two different hx, yi pairs, by definition, ∆(B ∪ O1 ∪ O2 , M, ∪2i=1 Ei+ , ∪2i=1 Ei− ) = {41 ∪
42 |(41 , 42 ) ∈ ∆(B ∪ O1 , M, E1+ , E1− ) × ∆(B ∪ O2 , M, E2+ , E2− )}. Thus, for any solution hHI , HG , 4i of
ILP(B∪O1 ∪O2 , M, ∪2i=1 Ei+ , ∪2i=1 Ei− ), ∃41 ∈ ∆(B∪O1 , M, E1+ , E1− ) and ∃42 ∈ ∆(B∪O2 , M, E2+ , E2− )
such that,
HG (4) = HG (41 ) ∪ HG (42 ) ≥ HI
This property allows us to search for HI ’s without solving ILP(B∪O1 ∪O2 , M, ∪2i=1 Ei+ , ∪2i=1 Ei− )
directly. The search procedure can be briefly described as follows: For any choice of (41 , 42 ) pair,
first find all the minimal H ≤ HG (41 ) ∪ HG (42 ) that solves E1 and then expand those minimally,
with respect to E2 and E1 alternatively, until all the minimal HI ’s that solves both E1 and E2 are
found. To find all the HI one simply needs to iterate over all possible (41 , 42 ) pairs which can be
computed from ILP(B ∪ O1 , M, E1+ , E1− ) and ILP(B ∪ O2 , M, E2+ , E2− ) individually.
It should be noted that it is possible to have HG (40 ) = HG (400 ), even though 40 , 400 . Thus, the
above search procedure can be optimized by iterating over pairs of generalizations instead of iterating over the abducibles. Another drawback of the above search procedure is that the search results of (HG1 (41 ), HG2 (42 )) do not give any information for the search initiated on (HG1 (401 ), HG2 (402 )).
In every iteration it starts from scratch. However, if we remember the solutions of ILPDE (B, M, E1 ),
we can use those as lower bounds for finding the solutions of ILPDE (B, M, hE1 , E2 i). This is because, if HI is a minimal solution of ILPDE (B, M, hE1 , E2 i), then HI also solves ILPDE (B, M, E1 )

8

Arindam Mitra and Chitta Baral

and there exist a < HI1 , HG1 , 41 > ∈ ILPDE (B, M, E1 ) such that HI1 ≤ HI . Thus, for the iteration
(HG1 (41 ), HG2 (42 )), one can search if some HI1 ≤ HG1 (41 ) can expanded by either expanding some
rules in HI1 or by adding new rules from the remainder of HG1 (41 ) ∪ HG2 (42 ) or both to solve E2
along with E1 . Theorem 1 formalizes this idea.
Theorem 1
For any solution < HI , HG , 4 > of ILPDE (B, M, hE1 , E2 , ..., Ei i) there exists a solution < HI0 , HG0 , 40 >
of ILPDE (B, M, hE1 , E2 , ..., Ei−1 i) and a generalization HG00 in ILPDE (B, M, Ei ) such that, HI0 ≤
HI ≤ HG0 ∪ HG00 . 
With this in mind, the algorithm for finding the solutions of ILPDE (B, M, {E1 , E2 , ..., En }) is
described in Algorithm 1. The proof of the theorem is in Appendix A.
Example
In this subsection we describe how our algorithm computes a solution to the running example
ILPDE (B, M, hE1 , E2 , E3 i) from Table 1. Here B contains all the constants of type op1, direction
and time and M is the one described in 3 .
Initialization: First the stack is filled with the output from XHAIL(B, M, E1 ). In section 1, we
have seen that the output contain only one tuple. The following block shows the content of the
stack after initialization.The highlighted part denotes HI , where HG is the entire program.
holdsAt(relativeposition(X, Y, right), T )
← holdsAt(relativeposition(Z, X, above), T ),
holdsAt(relativeposition(Y, Z, le f t), T ).
T op

T op

Iteration 1: In iteration 1, the hypothesis on the top (denoted as Top< HI , HG >) of the
T op
stack is popped. One can see that the hypothesis HI does not cover E2 . So, the algorithm tries
to find an expansion of it which solves E2 and E1 both. For that it first finds HG (B, M, E2 ) and
creates a new refinement stack with lower bound - upper bound pairs as shown below:
holdsAt(relativeposition(X, Y, right), T )
← holdsAt(relativeposition(Z, X, above), T ),
holdsAt(relativeposition(Y, Z, le f t), T ).
It may be noted that HG (B, M, E2 ) is empty as E2 does not contain any positive examples, so
the stack contains only and exactly the Top. Next it pops the refinement stack and tries to find the
minimal extensions of the Top that covers E2 . There are two such minimal extensions , H 0 , H 00
and both of them are pushed to the refinement stack.




holdsAt(relativeposition(X, Y, right), T )










0
H =
.
←
holdsAt(relativeposition(Z,
X,
above),
T
),











holdsAt(relativeposition(Y, Z, le f t), T ).




holdsAt(relativeposition(X, Y, right), T )










00
H =
.
←
holdsAt(relativeposition(Z,
X,
above),
T
),











holdsAt(relativeposition(Y, Z, le f t), T ).

9

Theory and Practice of Logic Programming
Algorithm 1: I 2 XHAIL

1
2

3

4

5

6
7

8

9

10
11
12
13

14

15
16

17
18

19

20
21

Data: An instance of ILPDE (B, M, {E1 , . . . , En })
Result: A solution to the problem
/* initialize a stack with the solutions of ILP(B, M, E1 )
stack = XHAIL(ILP(B, M, E1 ));
while statck is not empty do
/* pop the hypothesis from the top
hHI , HG i = stack.pop();
/* get an example Ei such that B ∪ HI ∪ Oi 0 Ei+ or B ∪ HI ∪ Oi ` Ei−
Ei = nextUncoveredExample(HI );
/* No such example exists
if Ei is null then
/* found a solution
return HI .

*/

*/
*/
*/
*/

else
/* Find expansions of HI that also solves Ei
*/
re f inementsS tack = <> ;
/* support set denotes the set of examples from which < Hi , HG >
is created
*/
supports = supportS et(HI ) ∪ {Ei };
/* compute a set of lower bound-upper bound pair for the search
space.
*/
HG (Ei ) = f indGeneralizatons(B, M, Ei );
foreach H in HG (Ei ) do
push < HI , HG ∪ H > to re f inementsS tack
while refinementsStack is not empty do
/* get a candidate lower bound-upper bound pair
*/
0
0
< HI , HG > = re f inementsS tack.pop();
/* get an example from supports that is not covered by HI0
*/
E j = nextUncoveredExampleFromS (HI0 , supports);
if E j is null then
/* if no such example exists then we found a solution to
the subproblem. Push it to the stack.
*/
push < HI0 , HG0 > to stack;
else
/* Expand HI0 minimaly along HG0 so that it covers E j
*/
expansions = expandMinimal(< HI0 , HG0 >, B, E j );
/* Push all expansions in the re f inementsS tack for further
updates.
*/
00
00
foreach < HI , HG > in expansions do
refinementsStack.push(< HI00 , HG00 >)

10

Arindam Mitra and Chitta Baral

The algorithm then goes on popping the top of the refinement stack, say H 0 . Since H 0 solves
both E1 and E2 the condition on line 16 of Algorithm 1 is satisfied and H 0 is pushed into the
main stack. Similarly, H 00 is popped next and pushed to the main stack. At this point refinement
stack becomes empty and iteration 1 exits as it has discovered all the minimal extensions of T op.
The stack now contains H 00 on top of H 0 .
Iteration 2: In the next iteration the algorithm pops hHI00 , HG00 i which is currently on the top of
the stack. The next problem it does not solve is E3 . It then computes HG (B, M, E3 ) which contain
only one element,




holdsAt(relativeposition(X, Y, below), T )










000
.
H =
←
holdsAt(relativeposition(Z,
Y,
below),
T
),











holdsAt(relativeposition(X, Z, right), T ).
It then pushes hHI00 , HG00 ∪ H 000 i to refinement stack and finds the minimal expansions of HI00
within the bound of HG00 ∪ H 000 . There will be only one such expansion, H f inal which will then
be pushed into the refinement stack and finally into the main stack. Since H f inal solves all three
examples, the algorithms terminates returning H f inal as the solution.

H

f inal






 holdsAt(relativeposition(X, Y, right), T ) ← holdsAt(relativeposition(Y, Z, le f t), T ).

.
=



 holdsAt(relativeposition(X, Y, below), T ) ← .

On the Minimality of the Solution

The solution returned by algorithm 1 may not be minimal. This is because if HI is expanded
minimally to HI0 to solve a new example E, it does not ensure that HI0 is minimal with respect to
the relevant subproblem. An example of this is the following: B = {}, E1 = h{p., b., c.}, {a}, {}i, E2 =
h{b.}, {}, {a}i, E3 = h{c.}, {a}, {}i, and M = {#modeh a, #modeb b, #modeb c, #modeb p}. There are
two solutions in ILPDE (B, M, hE1 , E2 i): H1 = {a ← c.} and H2 = {a ← p.}. If H2 is expanded first,
it will produce {a ← p., a ← c.} as the solution of ILPDE (B, M, hE1 , E2 , E3 i) and since it covers
all the examples, it will be returned as the solution. However, only {a ← c.} is sufficient to cover
E1 , E2 , E3 . Thus the output is not minimal. The minimal solution can be found by computing all
the solutions to ILPDE (B, M, hE1 , E2 , E3 i) and then discarding the ones which have a compressed
version of it already in ILPDE (B, M, hE1 , E2 , E3 i). However, algorithm 1 prefers efficiency over
minimality and returns the first solution found.
4 Related Work
In the recent years the field of Inductive logic programming has seen major advancements in
many of its areas. Different ILP algorithms have been proposed (Ray 2009; Athakravi et al. 2013;
Law et al. 2014; Athakravi et al. 2015; Katzouris et al. 2015; Kazmi et al. 2017; Schüller and
Kazmi 2017). Researchers have analyzed various kinds of “good” rules that cannot be learned
with the current definition of entailment (called “cautious inference”) and proposed an alternative
to that, named as “brave inference”. ILP Algorithms have thus been proposed that can do only
“brave inference” (Otero 2001) or both (Sakama 2005; Sakama and Inoue 2009; Law et al. 2015).
Efforts have also been made to learn answer set programs that not only contain Horn clauses but
also the choice rules and the constraints (Law et al. 2015). With these developments and the

Theory and Practice of Logic Programming

11

various systems that have been produced with these researches, people have successfully applied
the paradigm of Inductive logic programming to various areas (Gulwani et al. 2015; Mitra and
Baral 2016). And with these exposure to different applications, several changes are being made
to the paradigm of ILP.
Recently (Law et al. 2016) proposed context dependent learning for ordered answer set programs. Due to lack of space we do not discuss learning ordered answer set programs here. Interested readers can refer to(Law et al. 2016). The definition of context dependent learning in this
paper is an adaptation of their definition for standard ILP setting. It should be noted that even
though the concept of context depending learning was proposed in (Law et al. 2016), to solve the
problem their method converts it to a standard ILP problem using choice rules. Here, we have
made the first attempt to solve the problem in its original form.
In this work, we deal with the situation where there are many small distinct examples {(x1 , y1 ), ....,
(xn , yn )}. Another situation where scalability is needed when there is a single but big example.
Works in (Katzouris et al. 2015; Katzouris et al. 2017) talk about this situation. Our work is also
related to the work in logical vision ((Dai et al. 2015)) that aims to learn symbolic representation
of simple geometric concepts.
5 Experiments
We have applied our algorithm on two datasets. They are discussed below:
Task 6: Lists/Sets
Sandra picked up the football
there.
Sandra journeyed to the office.
Sandra took the apple there.
Sandra discarded the apple.
What is Sandra carrying?

Task 17: Path finding
The office is east of the hallway.

Task 10: Indefinite reasoning
Fred is either in the school or the
park.
The kitchen is north of the office. Mary went back to the office.
The garden is west of the bedroom. Bill is either in the kitchen or the
park.
The office is west of the garden.
Fred moved to the cinema.
How do you go from the kitchen to Is Bill in the office?
the garden?

Table 4: Example question answering tasks from bAbI dataset
Question Answering
Recently a group of researchers from Facebook has proposed a question answering challenge
(Weston et al. 2015) containing 20 different tasks. Table 1 and 4 shows examples of such tasks.
Each task contain 1000 or more such stories in the training data. The goal is to build a system
that uniformly solves all the tasks.
The work of (Mitra and Baral 2016) has shown how Inductive logic programming can be used
to solve the tasks. Their method can be summarized as follows: Given the input containing a
story and a question, first translate it to an Answer Set Program using a natural language parser
and some handwritten rules, then use some knowledge to answer the question. In the training
phase, learn those necessary knowledge. They have used XHAIL system to learn the knowledge.
However, XHAIL could not scale to the entire dataset. So they have divided the dataset. For
each task their method takes a bunch of examples together, learns from the bunch using XHAIL,
adds the learned hypothesis back to the background knowledge and then takes the next bunch
to learn from. Since knowledge learned from a group of examples is never updated again, they

12

Arindam Mitra and Chitta Baral

TASK
1: Single Supporting Fact
2: Two Supporting Facts
3: Three Supporting facts
4: Two Argument Relations
5: Three Argument Relations
6: Yes/No Questions
7: Counting
8: Lists/Sets
9: Simple Negation
10: Indefinite Knowledge

Time
3
3
2
6
5
4
4
9

Rules Acc
10 100
2
100
100
8
100
20 100
100
14 100
8
100
13 100
21 100

TASK
11: Basic Coreference
12: Conjunction
13: Compound Coreference
14: Time Reasoning
15: Basic Deduction
16: Basic Induction
17: Positional Reasoning
18: Size Reasoning
19: Path Finding
20: Agent’s Motivations

Time
4

4
4
4
4
4
17
2

Rules Acc
5
100
100
100
4
100
1
100
1
93.6
26 100
4
100
2
100
6
100

Table 5: Performance on the set of 20 tasks. The tasks for which training is not required is marked
with ‘-’. Running time is measured in minutes.
had to manually find a group size that will work for this dataset. The group size depended on
the task and clearly it might happen that for some new task there does not exist a group size to
which xhail can scale. In this work, we reuse the dataset, their mode declarations and have found
that our algorithm can learn all the knowledge given the input ILPDE (B, M, Dtask ), where Dtask
contains all the 1000 examples of a task. Table 5 shows the time it has taken, the number of rules
learned for each task and the accuracy for each task. Our system has achieved the same accuracy
as that of (Mitra and Baral 2016).
Semantic Parsing We have done further experiments with the task of semantic parsing. We took
all the unique sentences in the training dataset of (Weston et al. 2015) and the corresponding
parse tree of the sentences and then train an ILP system to do the conversion from scratch. Table
6 shows an example of this task. The training dataset contain 5458 such examples. Our system
learned a collection of 165 rules in 128 minutes from the training data which accurately parsed
all the sentences of test data.
Sentence
Daniel journeyed to the bathroom.
ASP Representation Oi
index(1..5). lemma(1,daniel). pos(1,nn). lemma(2,journey). pos(2,vbd). lemma(3,to).
pos(3,to). lemma(4,the). pos(4,dt). lemma(5,bathroom). pos(5,nn).
Positive Examples Ei+
arg1(journey01,daniel), arg2(journey01,bathroom) .
Positive Examples Ei−
any possible output that is not in E + .

Table 6: An example from the semantic parsing task. For each word in the sentence the representation contains its lemma and pos tag, which are obtained using Stanford parser .
Handwritten Digit Recognition
The MNIST dataset (LeCun 1998) contains images of handwritten digits. Each image is a 28 × 28
matrix and is labeled with a number between 0 to 9 denoting the digit it represents. The value of a
cell (pixel) in the matrix (image) ranges between 0 (black) to 255 (white) capturing the darkness
at that point. In this experiment we use our ILP algorithm to learn rules that identifies digits. For
that we represent the images in the following way:

13

Theory and Practice of Logic Programming

1. First, we divide all cell value by 255 so that the value of each cell belongs to [0, 1].
2. For each 4 × 4 non-overlapping submatrix we create a super-pixel whose value is the sum
of the all the pixels in that region. This gives a 7 × 7 size matrix representation of the
original image. Note that in this reduced matrix, each cell value ranges between 0 to 16.
3. If the value of a super-pixel from the 7 × 7 matrix is less than 2 we consider it to be in
the off state. If the value is more than or equal to 5 we consider it be in the on state. The
original image is then described as two disjoint sets: 1) a set of positions where the state
of the super-pixel is off and 2) another set where all the super-pixel are on.
We learn rules on this representation. Each learned rule for a digit d simply says, if the superpixels in certain positions are off and are on for some other positions then the image represents
the digit d. The training data in the MNIST dataset contains a total of 60, 000 images with approximately 6, 000 images for each digit. To learn the rules for each digit we take all the examples
of that digit and take equal amount of images that represent other digits and pass that to our algorithm. Table 7 shows the number of rules learned for each digit and the performance on the test
data. Except for the digit 1, it takes 7 days to learn the rules for each digit.
Digit
0
1
2
3
4

#Rules #Test Examples
3,021
980
444
1134
4,606
1032
3,661
1010
3,416
982

Acc(%)
60.91
95.85
32.95
49.80
49.59

Digit
5
6
7
8
9

#Rules #Test Examples
3,459
891
2,621
958
2,430
1028
3,237
978
2,382
1009

Acc(%)
42.65
65.03
63.52
54.50
69.18

Table 7: Performance on handwritten digit recognition tasks. For each digit, column 2 shows the
numbers of rules learned, the number instances of that digit in the test set and the percentage of
instances correctly classified.
As the Table 7 suggests the performance on handwritten digit recognition is quite poor in comparison to the state-of-the-art neural network classifier (Wan et al. 2013) that achieves 99.79%
accuracy on this dataset. The number of rules column in Table provides insights on this high
error rates. Consider the example of digit 0. If there are 5000 instances of digit 0 and the algorithm outputs 3, 021 rules that means the representation that we have chosen does not allow good
generalization. However, the representation seems to work quite well for the digit 1.
An important lesson learned from this experiment is that even though it takes a small amount
of time to perform a hypothesis refinement when finding a solution H for hE1 , ..., Ei i from a
solution of hE1 , ..., Ei−1 i, the algorithm needs to verify if H explains all of {E1 , ..., Ei } before it
can proceed to the next iteration. If the size of H is big (such as the case for digit recognition) and
too many refinements are taking place then the algorithm spends a lot of time in the verification
phase. An important future work will be to optimize this step by identifying which examples
could have been effected if a hypothesis goes through refinement . Nevertheless, the algorithm
is able to output a solution and does not blow up when a problem of this size is given as input.
The dataset associated with all the experiments and the learned rules are available at https:
//goo.gl/k6AEEz. All experiments were performed on an intel i7 machine with 12 GB RAM.
6 Conclusion
Earlier days of Artificial Intelligence have seen many handwritten rule based systems. Later those
were replaced by better performing machine learning based systems. With the advancements of

14

Arindam Mitra and Chitta Baral

knowledge representation and reasoning languages, a natural question arises, “if machines can
learn logic programs, can it achieve better accuracy than existing statistical machine learning
methods such neural networks?” It should be noted that the system of (Mitra and Baral 2016)
achieved better results than the existing deep learning models on the bAbI dataset. To further
explore this possibility we need to focus on the task of learning of logic programs and need
to develop systems that can learn from large datasets. In this paper, we have made an attempt
towards that.
References
Athakravi, D., Alrajeh, D., Broda, K., Russo, A., and Satoh, K. 2015. Inductive learning using constraintdriven bias. In Inductive Logic Programming, pp. 16–32. Springer, Cham.
Athakravi, D., Corapi, D., Broda, K., and Russo, A. 2013. Learning through hypothesis refinement using
answer set programming. In International Conference on Inductive Logic Programming, pp. 31–46.
Springer.
Dai, W.-Z., Muggleton, S. H., and Zhou, Z.-H. 2015. Logical vision: Meta-interpretive learning for simple
geometrical concepts. In ILP (Late Breaking Papers), pp. 1–16.
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In ICLP/SLP,
Volume 88, pp. 1070–1080.
Gulwani, S., Hernandez-Orallo, J., Kitzelmann, E., Muggleton, S., Schmid, U., and Zorn, B. 2015. Inductive programming meets the real world. Communications of the ACM 58, 11, 90–99.
Katzouris, N., Artikis, A., and Paliouras, G. 2015. Incremental learning of event definitions with inductive
logic programming. Machine Learning 100, 2-3, 555–585.
Katzouris, N., Artikis, A., and Paliouras, G. 2017. Distributed online learning of event definitions.
CoRR abs/1705.02175.
Kazmi, M., Schüller, P., and Saygın, Y. 2017. Improving scalability of inductive logic programming via
pruning and best-effort optimisation. Expert Systems with Applications.
Law, M., Russo, A., and Broda, K. 2014. Inductive learning of answer set programs. In European Workshop
on Logics in Artificial Intelligence, pp. 311–325. Springer, Cham.
Law, M., Russo, A., and Broda, K. 2015. Learning weak constraints in answer set programming. Theory
and Practice of Logic Programming 15, 4-5, 511–525.
Law, M., Russo, A., and Broda, K. 2016. Iterative learning of answer set programs from context dependent
examples. Theory and Practice of Logic Programming 16, 5-6, 834–848.
LeCun, Y. 1998. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/ .
Mitra, A. and Baral, C. 2016. Addressing a question answering challenge by combining statistical methods
with inductive rule learning and reasoning. In AAAI, pp. 2779–2785.
Muggleton, S. 1991. Inductive logic programming. New generation computing 8, 4, 295–318.
Muggleton, S. 1995. Inverse entailment and progol. New generation computing 13, 3-4, 245–286.
Otero, R. 2001. Induction of stable models. Inductive Logic Programming, 193–205.
Ray, O. 2009. Nonmonotonic abductive inductive learning. Journal of Applied Logic 7, 3, 329–340.
Sakama, C. 2005. Induction from answer sets in nonmonotonic logic programs. ACM Trans. Comput.
Logic 6, 2 (April), 203–231.
Sakama, C. and Inoue, K. 2009. Brave induction: a logical framework for learning from incomplete information. Machine Learning 76, 1 (Jul), 3–35.
Schüller, P. and Kazmi, M. 2017. Best-effort inductive logic programming via fine-grained cost-based
hypothesis generation. arXiv preprint arXiv:1707.02729.
Wan, L., Zeiler, M., Zhang, S., Le Cun, Y., and Fergus, R. 2013. Regularization of neural networks using
dropconnect. In International Conference on Machine Learning, pp. 1058–1066.
Weston, J., Bordes, A., Chopra, S., and Mikolov, T. 2015. Towards ai-complete question answering: a set
of prerequisite toy tasks. arXiv preprint arXiv:1502.05698.

Theory and Practice of Logic Programming

15

Appendix A Proof of Theorem 1
Theorem 1
For any solution < HI , HG , 4 > of ILPDE (B, M, hE1 , E2 , ..., En i) there exists a solution < HI0 , HG0 , 40 >
of ILPDE (B, M, hE1 , E2 , ..., En−1 i) and a generalization HG00 in ILPDE (B, M, En ) such that, HI0 ≤
HI ≤ HG0 ∪ HG00 .
Proof Recall that ∆(B, M, E) ={4|hHI , HG , 4i ∈ XHAIL(B, M, E) for some HI , HG }. We further
define,
4(B, M, < E1 , ..., En >) = {(41 , 42 , ..., 4n )|4i ∈ 4(B, M, Ei ), ∀i = 1..n}
HG (4 = (41 , 42 , ..., 4n )) = ∪ni=1 HG (4i )
Since HI is a solution to ILPDE (B, M, hE1 , E2 , ..., En−1 i) and HI ∪ B ∪ Oi is assumed to be a stratified program, there is a unique set containing only ground instances of modeh literals (abducibles
predicates), 4∗ = (4∗1 , 4∗2 , ..., 4∗n−1 ) in 4(B, M, < E1 , ..., En >) such that ∀i ∈ 1, ..., n − 1,
i B ∪ Oi ∪ HI ` 4∗i ,
ii @40i .(40i ∈ 4(B, M, Ei )) ∧ (B ∪ Oi ∪ HI ` 40i ) ∧ (4∗i ⊂ 40i ).
Similarly, since HI is a solution to ILPDE (B, M, En ) there is a unique 4̄ such that,
i B ∪ On ∪ HI ` 4̄,
ii @40n .(40n ∈ 4(B, M, En )) ∧ (B ∪ On ∪ HI ` 4̄) ∧ (4̄ ⊂ 40n ).
HI is then bounded by HG (4∗ ) ∪ HG (4̄). If this is not the case then HI has at least one rule
whose body is not satisfied in any of the context provided by B ∪ Oi , for all i = 1...n. And hence
HI cannot be minimal. Now consider the set S containing all the minimal solution hHI0 , HG0 , 4∗ i
of ILPDE (B, M, hE1 , E2 , ..., En−1 i) that can be obtained from 4∗ . Let HI∗ denote the set of all rules
from HI that are satisfied in at least one of the context B ∪ Oi ∪ HI , for i = 1...n − 1. Then, there
must exist at least one HI0 ∈ S such that HI0 ≤ HI∗ ≤ HI . Otherwise, HI∗ is a minimal solution of
ILPDE (B, M, hE1 , E2 , ..., En−1 i) that can be obtained from 4∗ but not in S . A contradiction. 

