MARKUS, a derivative of Shapiro's Model Inference System MIS,
induces Prolog programs from positive and negative
examples. MARKUS employs a covering strategy as, e.g., FOIL.
It induces clauses with functions and is able to start induction
with a preliminary incomplete or inconsistent definition of the target
predicate which is then refined.
For inducing single clauses, MARKUS searches a refinement graph.
The search starts with the most general clause which is specialised by
applying the refinement operators taken over from MIS. In
contrast to MIS, MARKUS generates an optimal refinement
graph, i.e., a refinement graph without duplicate nodes, thus
improving efficiency. The refinement graph is searched by iterative
deepening search. When MARKUS encounters a clause covering at
least one yet uncovered positive and no negative example, the clause
is added to the predicate definition. Redundant clauses are removed
from the predicate definition.
As MARKUS realizes an exhaustive search, restricting the
hypothesis space is crucial for learning. Therefore, MARKUS
offers elaborate mechanisms for explicit and implicit declaration of
the language bias. First of all, the language bias which is defined
implicitly by the refinement operator can be adjusted to the learning
task by choosing the appropriate refinement operator, as MARKUS
offers a refinement operator for learning DCG clauses and a general
refinement operator for inducing logic programs. The application of
the general refinement operator is guided by input/output mode
declarations and type definitions for the arguments of the target and
background predicates specified by the user. A set of parameters
determines the form of clauses generated by the refinement operator.
E.g., these parameters allow to define the maximum number of body
literals, and the maximum structure depth of head arguments. For
further tuning of the search space, the user can specify various
concrete syntactic restrictions within individual type and background
predicate definitions in a uniform manner. E.g., these restrictions
make it possible to define argument symmetry or to prevent particular
combinations of literals.
MARKUS is a non-interactive learner, learning from positive and negative
examples which offers various options for adjusting the system bias.
It uses logic with functors and is able to generate hypothesis clauses
with negated body literals.
The background knowledge is defined intensionally.
The user has to provide mode declarations and type definitions for the
arguments of target and background predicates.
References
M. Grobelnik.
MARKUS: An optimized model inference system.
In C. Rouveirol, editor, Proceedings of the ECAI-92 Workshop on
Logical Approaches to Machine Learning, 1992.
M. Grobelnik.
Induction of Prolog programs with MARKUS.
In Y. Deville, editor, Proceedings of the 3rd International
Workshop on Logic Program Synthesis and Transformation. Workshops in
Computing, Springer-Verlag, 1993.
E.Y. Shapiro.
Algorithmic Program Debugging.
The MIT Press, 1983.