ILASP

Inductive Learning of Answer Set Programs

Mode Declarations


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.

Extra options for mode declarations


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:

  1. 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)).
  2. 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.
  3. 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.