Inductive Learning of Answer Set Programs

The conventional way to specify a hypothesis space is to give a set of
*mode declarations* (this is sometimes called a *mode bias*).

A *placeholder* is a term `var(t)`

or `const(t)`

for some constant term
`t`

. The idea is that these can be replaced by any variable or constant
(respectively) of *type* t.

Each constant `c`

which is allowed to replace a `const`

term of type `t`

should be specified as `#constant(t, c)`

.

A mode declaration is a ground atom whose arguments can be placeholders.
An atom `a`

is *compatible* with a mode declaration `m`

if each of the
placeholder constants and placeholder variables in `m`

has been replaced
by a constant or variable of the correct type (the user does not have to
list the variables which can be used, but ILASP will ensure that no
variable occurs twice in the same rule with a different type).

There are four types of mode declaration: `#modeh`

the *normal head*
declarations; `#modeha`

, the *aggregate head* declarations; `#modeb`

,
the *body* declarations; `#modec`

, the *condition* declarations; and
`#modeo`

, the *optimisation* body declarations. Each mode declaration
can also be specified with a *recall*, which is an integer specifying
the maximum number of times that mode declaration can be used in each
rule. For example, a user can specify a mode declaration stating that
the predicate `p`

with arity 1 can be used in each rule up to two times
with a single variable of type `type1`

, for example, as ```
#modeb(2,
p(var(type1)))
```

.

The maximum number of variables in any rule can be specified using the
predicate `#maxv`

; for example `#maxv(2)`

states that at most 2
variables can be used in each rule of the hypothesis. Similarly,
`#max_penalty`

specifies an upper bound on the size of the hypothesis
returned. By default, this is 15. Lower values for this are likely to
increase the speed of computation, but in some cases larger bounds are
needed (as in the sudoku example in the next section).

**Example.**

Consider the following language bias:

```
#modeha(r(var(t1), const(t2)))
#modeh(p)
#modeb(1, p)
#modeb(2, q(var(t1)))
#constant(t2, c1)
#constant(t2, c2)
#maxv(2).
```

This leads to the following search space:

```
:- q(V1).
:- p.
:- not p.
:- q(V1), p.
:- q(V1), not p.
p.
p :- q(V1).
0 { r(V1, c1) } 1 :- q(V1).
0 { r(V1, c1) } 1 :- q(V1), p.
0 { r(V1, c1) } 1 :- q(V1), not p.
0 { r(V1, c2) } 1 :- q(V1).
0 { r(V1, c2) } 1 :- q(V1), q(V2).
0 { r(V1, c2) } 1 :- q(V1), q(V2), p.
0 { r(V1, c2) } 1 :- q(V1), p.
0 { r(V1, c2) } 1 :- q(V1), q(V2), not p.
0 { r(V1, c2) } 1 :- q(V1), not p.
0 { r(V1, c1); r(V1, c2) } 1 :- q(V1).
0 { r(V1, c1); r(V1, c2) } 1 :- q(V1), p.
0 { r(V1, c1); r(V1, c2) } 1 :- q(V1), not p.
1 { r(V1, c1); r(V1, c2) } 1 :- q(V1).
1 { r(V1, c1); r(V1, c2) } 1 :- q(V1), p.
1 { r(V1, c1); r(V1, c2) } 1 :- q(V1), not p.
1 { r(V1, c1); r(V1, c2) } 2 :- q(V1).
1 { r(V1, c1); r(V1, c2) } 2 :- q(V1), p.
1 { r(V1, c1); r(V1, c2) } 2 :- q(V1), not p.
0 { r(V1, c1); r(V2, c1) } 1 :- q(V1), q(V2).
0 { r(V1, c1); r(V2, c1) } 1 :- q(V1), q(V2), p.
0 { r(V1, c1); r(V2, c1) } 1 :- q(V1), q(V2), not p.
1 { r(V1, c1); r(V2, c1) } 1 :- q(V1), q(V2).
1 { r(V1, c1); r(V2, c1) } 1 :- q(V1), q(V2), p.
1 { r(V1, c1); r(V2, c1) } 1 :- q(V1), q(V2), not p.
1 { r(V1, c1); r(V2, c1) } 2 :- q(V1), q(V2).
1 { r(V1, c1); r(V2, c1) } 2 :- q(V1), q(V2), p.
1 { r(V1, c1); r(V2, c1) } 2 :- q(V1), q(V2), not p.
0 { r(V1, c1); r(V2, c2) } 1 :- q(V1), q(V2).
0 { r(V1, c1); r(V2, c2) } 1 :- q(V1), q(V2), p.
0 { r(V1, c1); r(V2, c2) } 1 :- q(V1), q(V2), not p.
1 { r(V1, c1); r(V2, c2) } 1 :- q(V1), q(V2).
1 { r(V1, c1); r(V2, c2) } 1 :- q(V1), q(V2), p.
1 { r(V1, c1); r(V2, c2) } 1 :- q(V1), q(V2), not p.
1 { r(V1, c1); r(V2, c2) } 2 :- q(V1), q(V2).
1 { r(V1, c1); r(V2, c2) } 2 :- q(V1), q(V2), p.
1 { r(V1, c1); r(V2, c2) } 2 :- q(V1), q(V2), not p.
0 { r(V1, c2); r(V2, c2) } 1 :- q(V1), q(V2).
0 { r(V1, c2); r(V2, c2) } 1 :- q(V1), q(V2), p.
0 { r(V1, c2); r(V2, c2) } 1 :- q(V1), q(V2), not p.
1 { r(V1, c2); r(V2, c2) } 1 :- q(V1), q(V2).
1 { r(V1, c2); r(V2, c2) } 1 :- q(V1), q(V2), p.
1 { r(V1, c2); r(V2, c2) } 1 :- q(V1), q(V2), not p.
1 { r(V1, c2); r(V2, c2) } 2 :- q(V1), q(V2).
1 { r(V1, c2); r(V2, c2) } 2 :- q(V1), q(V2), p.
1 { r(V1, c2); r(V2, c2) } 2 :- q(V1), q(V2), not p.
```

Note that ILASP will try to omit rules which will never appear in an
optimal inductive solution; for example, as `p :- q(V1), q(V2)`

is
satisfied if and only if `p :- q(V1).`

is satisfied, the former will
never be part of an optimal solution, and so is not generated.

A final argument may be given to any mode declarations, which is a tuple to restrict the use of this mode declaration. The idea is that this can be used to further steer the search away from hypotheses which are uninteresting and thus improve the speed of the search.

This final argument is a tuple which may contain the any of the constants:
`anti_reflexive`

, `symmetric`

, `positive`

. The meaning of these
constants is as follows:

`anti_reflexive`

is intended for use on predicates of arity 2. It means that the predicate should not be generated with 1 variable repeated for both arguments; for example,`p(X,X)`

is not compatible with`#modeh(p(var(t),var(t)),(anti_reflexive))`

.`symmetric`

is intended for use on predicates of arity 2. It means that, for example, given the mode declaration`#modeh(p(var(t),var(t)),(symmetric))`

, rules containing`p(X, Y)`

are considered equivalent to the same rule replaced with`p(Y, X)`

and, as such, only one is generated.`positive`

means that the negation as failure of the predicate in the mode declaration should not be generated.

Other options, aimed mainly at choice rules (as it is very easy to
generate a search space with a massive number of choice rules) are
`#disallow_multiple_head_variables`

, which prevents more than one
variable being used in the head of a rule; `#minhl`

and `#maxhl`

which
are predicates of arity 1 specifying the minimum and maximum number of
literals which can occur in the head of a choice rule.