LINUS is an ILP learner which
incorporates existing attribute-value learning systems. The idea is to
transform a restricted class of ILP problems into propositional form and
solve the transformed learning problem with an attribute-value learning
algorithm. The propositional learning result is then re-transformed into
the first-order language. On the one hand, this approach enhances the
propositional learners with the use of background knowledge and the more
expressive hypothesis language. On the other hand, it enables the
application of successful propositional learners in a first-order
framework. As various propositional learners can be integrated and accessed
via LINUS, LINUS also qualifies as an ILP toolkit offering
several learning algorithms with their specific strengths. The present
distribution of LINUS provides interfaces to the attribute-value
learners ASSISTANT, NEWGEM, and CN2. Other propositional
learners may be added. LINUS can be run in two modes. Running in
CLASS mode, it corresponds to an enhanced attribute-value learner. In
RELATION mode, LINUS behaves as an ILP system.
The basic principle of the transformation from first-order into
propositional form is that all body literals which may possibly appear in a
hypothesis clause (in the first-order formalism) are determined, thereby
taking into account variable types. Each of these body literals
corresponds to a boolean attribute in the propositional formalism. For
each given example, its argument values are substituted for the variables
of the body literal. Since all variables in the body literals are required
to occur also as head variables in a hypothesis clause, the substitution
yields a ground fact. If it is a true fact, the corresponding
propositional attribute value of the example is true, and false
otherwise. The learning results generated by the propositional learning
algorithms are retransformed in the obvious way. The induced hypotheses are
compressed in a postprocessing step.
In order to enable the transformation into propositional logic and vice
versa, some restrictions on the hypothesis language and background
knowledge are necessary. As in most systems, training examples are ground
facts. These may contain structured, but nonrecursive terms. Negative
examples can be stated explicitly or generated by LINUS according
to the CWA. LINUS offers several options for controlling the
generation of negative examples.
The hypothesis language of LINUS is restricted to constrained
deductive hierarchical database clauses, that is, to typed program clauses
with nonrecursive predicate definitions and nonrecursive types where the
body variables are a subset of the head variables. Besides utility
functions and predicates, hypothesis clauses consist of literals unifying
two variables (X = Y) and of literals assigning a constant to a variable
(X = a). Certain types of literals may appear in negated form in the
body of a hypothesis clause.
Background knowledge has the form of deductive database clauses, that is,
possibly recursive program clauses with typed variables. The variable type
definitions which are required to be nonrecursive have to be provided by
the user. The background knowledge consists of two types of predicate
definitions, namely utility functions and utility predicates. Utility
functions are predicates which compute a unique output value for given
input values. The user has to declare their input/output mode. When
occuring in an induced clause, the output arguments are bound to
constants. Utility predicates are boolean functions with input arguments
only. For a given input, these predicates compute true or false.
References
S. Dzeroski and N. Lavrac.
Learning relations from noisy examples: An empirical comparison of
LINUS and FOIL.
In L. Birnbaum and G. Collins, editors, Proceedings of the 8th
International Workshop on Machine Learning, pages 399-402. Morgan Kaufmann,
1991.
N. Lavrac and S. Dzeroski.
Inductive Logic Programming: Techniques and Applications.
Ellis Horwood, 1994.