\documentstyle[jair,twoside,11pt,theapa,pstricks]{article}
\input epsf %% at top of file

\jairheading{5}{1996}{139-161}{4/96}{10/96}
\ShortHeadings{Learning First-Order Definitions of Functions}
{Quinlan}
\firstpageno{139}


\newlength{\twodig}
\settowidth{\twodig}{99}
\newcommand{\dd}[1]{\makebox[\twodig][r]{#1}}
\newlength{\threedig}
\settowidth{\threedig}{999}
\newcommand{\ddd}[1]{\makebox[\threedig][r]{#1}}
\newlength{\fourdig}
\settowidth{\fourdig}{9999}
\newcommand{\dddd}[1]{\makebox[\fourdig][r]{#1}}
\newlength{\dec}
\settowidth{\dec}{99.9}
\newcommand{\ddf}[1]{\makebox[\dec][r]{#1}}

\newcommand{\sect}[1]{\vspace{1.5\baselineskip}{\large \bf #1}}
\newcommand{\subsect}[1]{\vspace{0.5\baselineskip}{\bf #1}}
\newcommand{\scrunch}{\vspace{-\baselineskip}}

\setlength{\unitlength}{1mm}

\newcommand{\tuple}[1]{{$\langle$\small #1$\rangle$}}
\newcommand{\xtuple}[1]{$\langle#1\rangle$}
\newcommand{\mtuple}[1]{\langle#1\rangle}
\newcommand{\qbox}[1]{\\\rule{0mm}{1.5\baselineskip}\hspace{2.5cm}\begin{minipage}[t]{12cm}{\sf #1}\end{minipage}\\\rule{0mm}{1.5\baselineskip}}
\newcommand{\xsp}{\vspace{\baselineskip}}
\newcommand{\nulllist}{\mbox{\small [\hspace{1mm}]}}

\newcommand{\foil}{{\sc foil}}
\newcommand{\ffoil}{{\sc ffoil}}
\newcommand{\foidl}{{\sc Foidl}}
\newcommand{\filp}{{\sc filp}}
\newcommand{\golem}{{Golem}}
\newcommand{\progol}{{Progol}}

\newcommand{\qq}{{\small ?}}

\newcommand{\plt}{\prec}
\newcommand{\oow}{{$\wedge$}}

\newcommand{\element}[5]{\put(#1){\framebox(#2){}}%
\put(#4){\makebox(20,3)[l]{\small \sf #5}}}

\renewcommand{\floatpagefraction}{0.9}

\begin{document}

\title{Learning First-Order Definitions of Functions}

\author{\name J.~R.~Quinlan \email quinlan@cs.su.oz.au\\
	\addr Basser Department of Computer Science\\
	      University of Sydney\\
	      Sydney 2006 Australia}

\maketitle

\begin{abstract}
First-order learning involves finding a clause-form
definition of a relation from examples of the relation and relevant
background information.
In this paper, a particular first-order learning system is modified to
customize it for finding definitions of functional relations.
This restriction leads to faster learning times and, in some cases,
to definitions that have higher predictive accuracy.
Other first-order learning systems might benefit from similar specialization.
\end{abstract}

\section{Introduction}
\label{introduction}


Empirical learning is the subfield of AI that develops algorithms
for constructing theories from data.
Most classification research in this area has used the {\it attribute-value}\/
formalism, in which data are represented as vectors of values of
a fixed set of attributes and are labelled with one of a small number
of discrete classes.  A learning system then develops a mapping from
attribute values to classes that can be used to
classify unseen data.

Despite the well-documented
successes of algorithms developed for
this paradigm
(e.g., Michie, Spiegelhalter, and Taylor, 1994; Langley and Simon, 1995),
there are potential applications of learning that do
not fit within it.
Data may concern objects or observations with arbitrarily complex structure
that cannot be captured by the values of a predetermined
set of attributes.
Similarly, the propositional theory language employed by attribute-value
learners may be inadequate to express patterns in such structured data.
Instead, it may be necessary
to describe learning
input by {\it relations}, where a relation is just a set of
tuples of constants, and to represent what is learned in
a first-order language.
Four examples of practical learning tasks of this kind are:
\begin{itemize}
\item {\it Speeding up logic programs}\/ (Zelle and Mooney, 1993).
The idea here is to learn a guard for each nondeterministic clause
that inhibits its execution unless it will lead to a solution.
Input to the learner consists of a Prolog program and one or
more execution traces.
In one example {\sc Dolphin},
the system cited above, transformed a program from complexity
$O(n!)$ to $O(n^2)$.
\item {\it Learning search control heuristics}\/ (Leckie and Zukerman, 1993).
Formulation of preference criteria that improve efficiency in
planning applications has a similar flavor.
One task investigated here is the familiar `blocks world' in which
varying numbers of blocks must be rearranged
by a robot manipulator.
Each input to learning concerns a particular situation during search
and includes a complete description of the current planning state
and goals.  As the amount of this information increases with the
number of blocks and their inter-relationships, it cannot be encoded as a fixed set of values.
\item {\it Recovering software specifications}.  Cohen (1994) describes
an application based on a software system consisting of over
a million lines of C code.
Part of the system implements virtual relations that compute projections and
joins of
the underlying base relations, and the goal is to
reconstruct their definitions.
Input to learning consists of queries, their responses, and traces
showing the
base relations accessed while answering the queries.
The output is a logical description of the virtual relation;
since this involves quantified variables, it lies beyond
the scope of propositional attribute-value languages.
\item {\it Learning properties of organic molecules}\/ (Muggleton, King,
and Sternberg, 1992; Srinivasan, Muggleton, Sternberg, and King, 1996).
The approach to learning in these papers is based on representing the
structure of the molecules
themselves in addition to properties of molecules and
molecule segments.
The latter paper notes the discovery of a useful indicator of mutagenicity
expressed in terms of this structure.
\end{itemize}

The development of learning methods based on this more powerful relational
formalism is sometimes called {\it inductive logic programming}
(Muggleton, 1992; Lavra\v{c} and D\v{z}eroski, 1994; De Raedt, 1996).
Input typically consists of tuples that belong, or do not belong,
to a {\it target} relation, together with relevant information expressed
as a set of {\it background} relations.
The learning task is then to formulate a definition of the target relation
in terms of itself and the background relations.

This relational learning task is described in more detail in
the following section.
Several algorithms for relational learning have been developed recently,
and Section 3 introduces one such system
called \foil\ (Quinlan, 1990).
While \foil\ can be used with relations of any kind, one particularly
common use of relations is to represent functions.
Changes to \foil\ that in effect customize it for learning functional
relations are outlined in Section 4.
Several comparative studies, presented in Section 5, show that this
specialization leads to much shorter learning times and, in some cases,
to more accurate definitions.
Related work on learning functional relations is discussed in
Section 6, and the paper ends with some conclusions from this study and
directions for further development.

\section{Relational Learning}
\label{relational learning}


An $n$-ary relation $R_E$ consists of a set of $n$-tuples of ground
terms (here constants).  All constants in the $i$th position of
the tuples belong to some type,
where types may be differentiated or
all constants may be taken to belong to a single universal type.

As an alternative to this extensional definition as a (possibly infinite)
set, a relation can be specified intensionally via an $n$-argument predicate
$R_I$ defined by a Prolog program.
If
\[\mtuple{c_1,c_2,...c_n} \in R_E \mbox{ if and only if } R_I(c_1,c_2,...,c_n) \mbox{ is true}\]
for any constants $\{c_i\}$,
then the intensional and extensional definitions are equivalent.
For convenience, the subscripts of $R_E$ and $R_I$ will be omitted
and $R$ will be used to denote either the set of tuples or the predicate.

Input to a relational learning task consists of extensional information
about a target relation $R$ and extensional or intensional
definitions of a collection of background relations.
Examples of tuples known to belong to the target relation are provided
and, in most cases, so are examples of tuples known not to belong to $R$.
The goal is to learn a Prolog program for $R$ that covers all tuples
known to belong to $R$ but no tuples known not to belong to $R$ or,
in other words, a program that agrees with the extensional information
provided about $R$.

Many relations of interest are infinite.  An alternative to selecting
examples that belong or do not belong to $R$ is to define a finite
vocabulary $V$ and to specify relations with respect to this
vocabulary.
That is, $R$ is represented as the finite set of tuples, all constants
in which belong to $V$.
Since this specification of $R$ is complete over the vocabulary,
the tuples that do not belong to $R$ can be
inferred by the {\it closed world assumption}
as the complement of the tuples in $R$.

A function $f(X_1,X_2,...,X_k)$ of $k$ arguments
can be represented by a $k$+1-ary relation $F(X_1,X_2,...,X_k,X_{k+1})$
where, for each tuple in $F$, the value of the
last argument is the result of applying $f$ to the first $k$ arguments.
(Rouveirol (1994) proves that this {\it flattening} can be used to
remove all non-constant function symbols from any first-order language.)
Such {\it functional} relations have an additional property that
for any constants \{$c_1,c_2,..,c_k$\} there is exactly one
value of $c_{k+1}$ such that $\mtuple{c_1,c_2,...,c_{k+1}}$ belongs
to $F$.

As an example, consider the three-argument predicate {\sf append(A,B,C)}
whose meaning is that the result of appending list {\sf A} to list {\sf B}
is list {\sf C}.\footnote{%
In Prolog, {\sf append} can be invoked with any combination of its
arguments bound so as to find possible values for the unbound arguments.
Here and in Section 5.1, however, {\sf append} is treated as a function
from the first two
arguments to the third.}
The corresponding relation {\sf append} is infinite, but a restricted
vocabulary can be defined as all flat lists containing only
elements from \{1,2,3\} whose length is less than or equal to 3.
There are 40 such lists
\begin{center}
\small
\nulllist, [1], [2], [3], [1,2], ...., [3,3,2], [3,3,3]\\
\end{center}
and 64,000 3-tuples of lists.  
With respect to this vocabulary, {\sf append} consists of 142 of
these 3-tuples, viz.:
\begin{center}
\tuple{\nulllist,\nulllist,\nulllist}, \tuple{\nulllist,[1],[1]}, ...,
\tuple{[2],[1,3],[2,1,3]}, ..., \tuple{[3,3,3],\nulllist,[3,3,3]}.
\end{center}
There is also a background relation {\sf components}, where
{\sf components(A,B,C)} means that list {\sf A} has head {\sf B}
and tail {\sf C}.
The goal is then to learn an intensional definition of
{\sf append} given the background relation {\sf components}.
A suitable result might be expressed as
%
\qbox{\hspace*{-10mm}\sf append(\nulllist,A,A).\\
\hspace*{-10mm}append(A,B,C) :- components(A,D,E), append(E,B,F),
components(C,D,F).}
%
which is recognizable as a Prolog definition of {\sf append}.

\section{Description of \foil}
\label{foil}

In common with many first-order learning systems,
\foil\ requires that the background relations are also defined
extensionally by sets of tuples of constants.\footnote{%
Prominent exceptions include {\sc focl} (Pazzani and Kibler, 1992),
\filp\ (Bergadano and Gunetti, 1993), and \foidl\ (Mooney and Califf,
1995), that allow background relations to be defined extensionally,
and \progol\ (Muggleton, 1995), in which information about all
relations can be in non-ground form.}
Although the intensional definition is learned
from a particular set of examples,
it is intended to be executable as a Prolog program in which
the background relations may also be specified intensionally by definitions
rather than by sets of ground tuples.
For instance,
although the {\sf append} definition above might have been
learned from particular examples of lists,
it will correctly append arbitrary lists,
provided that {\sf components} is specified
by a suitable clausal definition.
(The applicability of learned definitions to unseen examples cannot be
guaranteed, however;
Bell and Weber (1993) call this the {\it open domain assumption}.)

The language in which \foil\ expresses theories is a restricted form of
Prolog that omits cuts, fail, disjunctive goals, and functions other
than constants, but allows
negated literals {\it not($L$(...))}.
This is essentially the {\it Datalog} language specified by Ullman (1988),
except that there is no requirement that all variables in a negated
literal appear also in the head or in another unnegated literal;
\foil\ interprets {\it not} using
{\it negation as failure} (Bratko, 1990).

\subsection{Broad-brush overview}

\begin{figure}
\begin{center}
\it
\fbox{%
\parbox{128mm}{%
\begin{itemize}
\item[] Initialization:\\
\hspace*{5mm}{\sf definition} := null program\\
\hspace*{5mm}{\sf remaining} := all tuples belonging to target relation $R$
\item[] While {\sf remaining} is not empty
  \begin{itemize}
  \item[]\vspace*{-2mm}/* Grow a new clause */
  \item[] {\sf clause} := $R(A,B,...)$ :-
  \item[] While {\sf clause} covers tuples known not to belong to $R$
    \begin{itemize}
    \item[] /* Specialize clause */
    \item[] Find appropriate literal(s) $L$\\
	Add $L$ to body of {\sf clause}
    \end{itemize}
  \item[] Remove from {\sf remaining} tuples in $R$ covered by {\sf clause}\\
    Add {\sf clause} to {\sf definition}
  \end{itemize}
\end{itemize}
}}

\vspace{\baselineskip}
{\it Figure 1:} \rm Outline of \foil
\end{center}
\end{figure}
As outlined in Figure 1,
\foil\ uses the separate-and-conquer method, iteratively
learning a clause and removing the tuples in the target relation $R$
covered by the clause until
none remain.  A clause is grown by repeated specialization, starting
with the most general clause head and adding literals to the body until
the clause does not cover any tuples known not to belong to $R$.

Literals that can appear in the body of a clause are restricted by the
requirement that programs be function-free, other than for
constants appearing in equalities.
The possible literal forms that
\foil\ considers are:
\begin{itemize}
\item $Q(X_1,X_2,...,X_k)$ and {\it not\/$(Q(X_1,X_2,...,X_k))$}, where
$Q$ is a relation and the $X_i$'s denote {\it known}\/ variables
that have been bound earlier in the clause or {\it new}\/ variables.
At least one variable must have been bound earlier in the
partial clause, either by the head or a literal in the body.
\item $X_i$=$X_j$ and $X_i$$\neq$$X_j$, for known variables $X_i$ and $X_j$
of the same type.
\item $X_i$=$c$ and $X_i$$\neq$$c$, where $X_i$ is a known variable and
$c$ is a constant of the appropriate type.  Only constants that have been
designated as suitable to appear in a definition are considered --
a reasonable definition
for {\sf append}
might reference the null list
\nulllist\ but not an arbitrary list such as {\small [1,2]}.
\item $X_i \leq X_j$, $X_i > X_j$, $X_i \leq t$, and $X_i > t$,
where $X_i$ and $X_j$ are known variables with numeric values and
$t$ is a threshold chosen by \foil.
\end{itemize}
If the learned definition must be pure Prolog, negated literal
forms {\it not\/$(Q(...))$} and $X_i$$\neq$... can be excluded by an option.

Clause construction is guided by different possible {\it bindings}
of the variables
in the partial clause that satisfy the clause body.
If the clause contains $k$ variables, a binding is a $k$-tuple of constants
that specifies a value for all variables in sequence.
Each possible binding
is labelled $\oplus$ or $\ominus$ according to whether the tuple of values
for the variables in the clause head does or does not belong in the
target relation.

As an illustration, consider the tiny task of constructing
a definition of {\sf plus(A,B,C)}, meaning {\sf A}+{\sf B} = {\sf C},
using the background relation {\sf dec(A,B)}, denoting {\sf B} = {\sf A}$-$1.
The vocabulary is restricted to just the integers 0, 1, and 2, so that
{\sf plus} consists of the tuples
\begin{center}
\tuple{0,0,0},
\tuple{1,0,1},
\tuple{2,0,2},
\tuple{0,1,1},
\tuple{1,1,2},
\tuple{0,2,2}\\
\end{center}
and {\sf dec} contains only \tuple{1,0} and \tuple{2,1}.

The initial clause consists of the head
%
\qbox{\sf plus(A,B,C) :-}
%
in which each variable is unique.  The labelled bindings corresponding to this
initial partial clause are just the tuples that belong, or do not belong,
to the target relation, i.e.:
\begin{center}
\begin{tabular}[b]{cccccc}
\tuple{0,0,0} $\oplus$&
\tuple{1,0,1} $\oplus$&
\tuple{2,0,2} $\oplus$&
\tuple{0,1,1} $\oplus$&
\tuple{1,1,2} $\oplus$&
\tuple{0,2,2} $\oplus$\\
\hline
\tuple{0,0,1} $\ominus$&
\tuple{0,0,2} $\ominus$&
\tuple{0,1,0} $\ominus$&
\tuple{0,1,2} $\ominus$&
\tuple{0,2,0} $\ominus$&
\tuple{0,2,1} $\ominus$\\
\tuple{1,0,0} $\ominus$&
\tuple{1,0,2} $\ominus$&
\tuple{1,1,0} $\ominus$&
\tuple{1,1,1} $\ominus$&
\tuple{1,2,0} $\ominus$&
\tuple{1,2,1} $\ominus$\\
\tuple{1,2,2} $\ominus$&
\tuple{2,0,0} $\ominus$&
\tuple{2,0,1} $\ominus$&
\tuple{2,1,0} $\ominus$&
\tuple{2,1,1} $\ominus$&
\tuple{2,1,2} $\ominus$\\
\tuple{2,2,0} $\ominus$&
\tuple{2,2,1} $\ominus$&
\tuple{2,2,2} $\ominus$\\
\end{tabular}.
\end{center}

\foil\ repeatedly tries to construct a clause that covers some tuples in
the target relation $R$ but no tuples that are definitely not in $R$.
This can be restated as finding a clause that has
some $\oplus$ bindings but no $\ominus$ bindings,
so
one reason for adding a literal to the clause is to
move in this direction by increasing the relative proportion
of $\oplus$ bindings.
Such {\it gainful} literals are evaluated using an information-based heuristic.
Let the number of $\oplus$ and $\ominus$ bindings of a partial clause be
$n^\oplus $ and $n^\ominus $ respectively.
The average information provided by the discovery that one of the bindings
has label $\oplus$ is
%\[I(n^\oplus ,n^\ominus ) = -\mbox{ log}_2 \;\;n^\oplus /\;(n^\oplus  + n^\ominus )\mbox{ bits.}\]
\[I(n^\oplus ,n^\ominus ) = -\mbox{ log}_2 \left( { n^\oplus \over n^\oplus  + n^\ominus} \right)\mbox{ bits.}\]
If a literal $L$ is added,
some of these bindings may be excluded and each of the rest
will give rise to one or more bindings for the new partial clause.
Suppose that $k$ of the $n^\oplus $ bindings are not excluded by $L$,
and that the numbers of bindings of the new partial clause are
$m^\oplus $ and $m^\ominus $ respectively.
If $L$ is chosen so as to increase the proportion of $\oplus$ bindings,
the total information gained by adding $L$ is then
\[k \times (I(n^\oplus ,n^\ominus ) - I(m^\oplus ,m^\ominus )) \mbox{ bits.}\]

Consider the result of specializing the above clause by the addition
of the literal {\sf A=0}.
All but nine of the bindings are eliminated because the corresponding
values of the variables do not satisfy the new partial clause.  The
bindings are reduced to
\begin{center}
\begin{tabular}{cccccc}
\tuple{0,0,0} $\oplus$&
\tuple{0,1,1} $\oplus$&
\tuple{0,2,2} $\oplus$\\
\hline
\tuple{0,0,1} $\ominus$&
\tuple{0,0,2} $\ominus$&
\tuple{0,1,0} $\ominus$&
\tuple{0,1,2} $\ominus$&
\tuple{0,2,0} $\ominus$&
\tuple{0,2,1} $\ominus$\\
\end{tabular}
\end{center}
in which the proportion of $\oplus$ bindings has increased from
6/27 to 3/9.  The information gained by adding this literal
is therefore $3\times(I(6,21) - I(3,6))$
or about 2 bits.  Adding the further literal {\sf B=C} excludes all
the $\ominus$ bindings, giving a complete first clause
%
\qbox{\sf plus(A,B,C) :- A=0, B=C.}
%
or, as it would be more commonly written,
%
\qbox{\sf plus(0,B,B).}
%
This clause covers three tuples of {\sf plus} which are then removed from
the set of tuples to be covered by subsequent clauses.  At the commencement
of the search for the second clause, the head is again {\sf plus(A,B,C)} and
the bindings are now
\begin{center}
\begin{tabular}[b]{cccccc}
\tuple{1,0,1} $\oplus$&
\tuple{2,0,2} $\oplus$&
\tuple{1,1,2} $\oplus$\\
\hline
\tuple{0,0,1} $\ominus$&
\tuple{0,0,2} $\ominus$&
\tuple{0,1,0} $\ominus$&
\tuple{0,1,2} $\ominus$&
\tuple{0,2,0} $\ominus$&
\tuple{0,2,1} $\ominus$\\
\tuple{1,0,0} $\ominus$&
\tuple{1,0,2} $\ominus$&
\tuple{1,1,0} $\ominus$&
\tuple{1,1,1} $\ominus$&
\tuple{1,2,0} $\ominus$&
\tuple{1,2,1} $\ominus$\\
\tuple{1,2,2} $\ominus$&
\tuple{2,0,0} $\ominus$&
\tuple{2,0,1} $\ominus$&
\tuple{2,1,0} $\ominus$&
\tuple{2,1,1} $\ominus$&
\tuple{2,1,2} $\ominus$\\
\tuple{2,2,0} $\ominus$&
\tuple{2,2,1} $\ominus$&
\tuple{2,2,2} $\ominus$\\
\end{tabular}.
\end{center}

The above literals were added to the body of the first clause because
they gain information.
A quite different justification for adding a literal
is to introduce new variables that may be
needed in the final clause.
{\it Determinate}\/ literals are based on an idea introduced
by \golem\ (Muggleton and Feng, 1992).
A determinate literal is one that introduces new variables
so that the new partial clause has exactly one binding for each $\oplus$
binding in the current clause, and at most one binding for each
$\ominus$ binding.
Determinate literals are useful because they introduce new variables,
but neither
reduce the potential coverage of the clause
nor increase the number of bindings.

Now that the $\oplus$ bindings do not include any with {\sf A=0},
the literal {\sf dec(A,D)} is determinate because, for each value of
{\sf A}, there is one value of {\sf D} that satisfies the literal.
Similarly, since the $\oplus$ bindings contain none with {\sf C=0},
the literal {\sf dec(C,E)} is also determinate.

In Figure 1, the literals $L$ added by \foil\ at each step
are
\begin{itemize}
\item the literal with greatest gain, if this gain is near the maximum
possible\\
(namely $n^\oplus \times I(n^\oplus, n^\ominus)$) ; otherwise
\item all determinate literals found; otherwise
\item the literal with highest positive gain; otherwise
\item the first literal investigated that introduces a new variable.
\end{itemize}
At the start of the second clause,
no literal has near-maximum gain and so all
determinate literals are added to the clause body.
The partial clause
%
\qbox{\sf plus(A,B,C) :- dec(A,D), dec(C,E),}
%
has five variables and the bindings that satisfy it are
\begin{center}
\begin{tabular}[b]{ccccc}
\tuple{1,0,1,0,0} $\oplus$&
\tuple{2,0,2,1,1} $\oplus$&
\tuple{1,1,2,0,1} $\oplus$\\
\hline
\tuple{1,0,2,0,1} $\ominus$&
\tuple{1,1,1,0,0} $\ominus$&
\tuple{2,0,1,1,0} $\ominus$&
\tuple{2,1,1,1,0} $\ominus$&
\tuple{2,1,2,1,1} $\ominus$
\end{tabular}
\end{center}
The literal {\sf plus(B,D,E)}, which uses these newly-introduced
variables, is now satisfied by all three $\oplus$ bindings but none of the
$\ominus$ bindings, giving a complete second clause
%
\qbox{\sf plus(A,B,C) :- dec(A,D), dec(C,E), plus(B,D,E).}
%
All tuples in {\sf plus} are covered by one or other of these clauses,
so they constitute a complete intensional definition of the target
relation.

\subsection{Details omitted}

\foil\ is a good deal more complex than this overview would suggest.
Since they are not important for this paper, matters such
as the following
are not discussed here, but are covered in (Quinlan and Cameron-Jones, 
1993; 1995):
\begin{itemize}
\item {\it Recursive soundness}.  If the goal is to be able to execute
the learned definitions as ordinary Prolog programs, it is
important that they terminate.  \foil\ has an elaborate mechanism to
ensure that any recursive literal (such as {\sf plus(B,D,E)} above)
that is added to a clause body will not cause problems in this respect,
at least for ground queries.
\item {\it Pruning}.  In practical applications with numerous
background relations, the number of possible literals $L$ that could
be added at each step grows exponentially with the number of
variables in the partial clause.  \foil\ employs some further
heuristics to limit this space, such as \golem's bound on the
{\it depth} of a variable (Muggleton and Feng, 1992).
More importantly, some regions of the literal space can be pruned
without examination because they can be shown to contain neither
determinate literals, nor literals with higher gain than the best
gainful literal found so far.
\item {\it More complete search}.  As presented above, \foil\ is a
straightforward greedy hill-climbing algorithm.  In fact, because \foil\
can sometimes reach an impasse in its search for a clause, it
contains a limited non-chronological backtracking facility to
allow it to recover from such situations.
\item {\it Simplifying definitions}.  
The addition
to the partial clause
of {\it all} determinate literals found
may seem excessive.  However, as a clause is completed,
\foil\ examines each literal in the clause body to see whether it
could be discarded without causing the simpler clause to match
tuples not in the target relation $R$.
Similarly, when the definition is complete, each clause is checked
to see whether it could be omitted without leaving any tuples in
$R$ uncovered.
There are also heuristics that aim to make clauses more understandable
by substituting simpler literals (such as variable equalities) for
literals based on more complex relations.
\item {\it Recognizing boundaries of closed worlds}.
Some literals that appear to discriminate $\oplus$ from $\ominus$
bindings do so only as a consequence of boundary effects attributable to
a limited vocabulary.\footnote{An example of this arises in Section 5.1.}
When a definition including such literals
is executed with larger vocabularies,
the open domain assumption mentioned above may be violated.
\foil\ contains an optional mechanism for describing when literals might be
satisfied by bindings outside the closed world, allowing some
literals
with unpredictable behavior to be excluded.
\end{itemize}
Quinlan (1990) and  Quinlan and Cameron-Jones (1995) summarize
several applications successfully addressed by \foil, some
of which are also discussed in Section 5.

\section{Learning Functional Relations}
\label{functional relations}

The learning approach used by \foil\ makes no assumptions about
the form of the target relation $R$.
However, as with {\sf append} and {\sf plus} above,
the relation is often used to represent a function --
in any tuple of constants that satisfies $R$, the last constant is
uniquely determined by the others.
Bergadano and Gunetti (1993) show that this property
can be exploited to
make the learning task more tractable.


\subsection{Functional relations and \foil}

Although \foil\ can learn definitions for functional relations, it
is handicapped in two ways:
\begin{itemize}
\item {\it Ground queries:}\/ \foil's approach to recursive soundness
assumes that only ground queries will be made of the learned definition.
That is, a definition of $R(X_1,X_2,...,X_n)$ will be used to provide
true-false answers to queries of the form $R(c_1,c_2,...,c_n)$\qq\ 
where the $c_i$'s are constants.
If $R$ is a functional relation, however, a more sensible query would
seem to be $R(c_1,c_2,...,c_{n-1},X)$\qq\ to determine the value of the function
for specified ground arguments.
In the case of {\sf plus}, for instance, we would not expect to
ask {\sf plus(1,1,2)\qq} (``is 1+1=2?''), but rather {\sf plus(1,1,X)\qq}
(``what is 1+1?'').
$R(c_1,c_2,...,c_{n-1},X)$\qq\ will
be called the {\it standard query}\/ for functional
relations.
\item {\it Negative examples:}\/ \foil\ needs both tuples that belong
to the target relation and at least some that do not.
In common with other ILP systems such as \golem\ (Muggleton and Feng, 1992),
the latter are used to detect when a partial clause is still too general.
These can be specified to \foil\ directly or, more commonly, 
are derived under the
closed world assumption that, with respect to the vocabulary,
all tuples in $R$ have been given.
This second mechanism can often lead to very large collections of
tuples not in $R$; there were nearly 64,000 of them
in the {\sf append} illustration earlier.
Every tuple not belonging to $R$ results in a binding at the start of
each clause, so there can be uncomfortably many bindings that must
be maintained and tested at each stage of clause development.\footnote{%
For this reason, \foil\ includes an option to sample the $\ominus$
bindings instead of using all of them.}
However, functional relations do not need explicit counter-examples,
even when the set of tuples belonging to $R$ is not complete with
respect to some vocabulary --
knowing that $\mtuple{c_1,c_2,...,c_n}$ belongs to $R$ implies that
there is no other constant $c'_n$ such that $\mtuple{c_1,c_2,...,c'_n}$
is in $R$.
\end{itemize}
These problematic aspects of \foil\ vis \`{a} vis functional
relations suggest modifications to address them.
The alterations lead to a new system, \ffoil, that is still close
in spirit to its progenitor.

\subsection{Description of \ffoil}

Since the last argument of a functional relation has a special role,
it will be referred to as the {\it output argument}\/ of the relation.
Similarly, the variable corresponding to this argument in the head of a clause
is called the {\it output variable}.

The most fundamental change in \ffoil\ concerns the bindings of partial
clauses and the way that they are labelled.
A new constant $\Box$ is introduced to indicate an undetermined value
of the output variable in a binding.
Bindings will be labelled according to the value of the output variable,
namely
$\oplus$ if this value is correct (given the value of the earlier
constants), $\ominus$ if the value is incorrect, and $\odot$ if the
value is undetermined.

The outline of \ffoil\ (Figure 2) is very similar to
Figure 1, the only differences being those highlighted.
\begin{figure}
\begin{center}
\it
\fbox{%
\parbox{128mm}{%
\begin{itemize}
\item[] Initialization:\\
\hspace*{5mm}{\sf definition} := null program\\
\hspace*{5mm}{\sf remaining} := all tuples belonging to target relation $R$
\item[] While {\sf remaining} is not empty
  \begin{itemize}
  \item[]\vspace*{-2mm}/* Grow a new clause */
  \item[] {\sf clause} := $R(A,B,...)$ :-
  \item[] While {\sf clause}
	  \psframebox*[fillcolor=yellow]{has $\ominus$ or $\odot$ bindings}
    \begin{itemize}
    \item[] /* Specialize clause */
    \item[] Find appropriate literal(s) $L$\\
	Add $L$ to body of {\sf clause}
    \end{itemize}
  \item[] Remove from {\sf remaining} tuples in $R$ covered by {\sf clause}\\
    Add {\sf clause} to {\sf definition}
  \end{itemize}
\item[] \psframebox*[fillcolor=yellow]{Simplify final definition}
\item[] \psframebox*[fillcolor=yellow]{Add default clause}
\end{itemize}
}}

\vspace{\baselineskip}
{\it Figure 2:} \rm Outline of \ffoil
\end{center}
\end{figure}
At the start of each clause there is one binding for every remaining
tuple in the target relation.  The output variable has the value $\Box$
in these bindings and this value is changed only when some subsequent
literal assigns a value to the variable.
In the small {\sf plus} example of Section 3.1,
the initial bindings for the first clause are
\begin{center}
\begin{tabular}{cccccc}
\tuple{0,0,$\Box$} $\odot$&
\tuple{1,0,$\Box$} $\odot$&
\tuple{2,0,$\Box$} $\odot$&
\tuple{0,1,$\Box$} $\odot$&
\tuple{1,1,$\Box$} $\odot$&
\tuple{0,2,$\Box$} $\odot$\\
\end{tabular}
\end{center}

Like its ancestor, \ffoil\ also assesses potential literals for adding
to the clause body as gainful or determinate, although both concepts
must be adjusted to accommodate the new label $\odot$.
Suppose that there are $r$ distinct constants in the
range of the target function.
Each $\odot$ binding can be converted to a $\oplus$ binding only by
changing $\Box$ to the correct value of the function, and to
a $\ominus$ binding by changing $\Box$ to any of the $r-1$
incorrect values.
In computing information gain, \ffoil\ thus counts each $\odot$ binding
as 1 $\oplus$ binding and $r-1$ $\ominus$ bindings.
A determinate literal is now one that introduces one or more
variables so that, in the new partial clause, there is exactly
one binding for each current $\oplus$ or $\odot$ binding
and at most one binding for each current $\ominus$ binding.
\ffoil\ uses the same preference criterion for adding literals $L$:
a literal with near-maximum gain, then all determinate literals, then
the most gainful literal, and finally a non-determinate
literal that introduces a new variable.

The first literal chosen by \foil\ in Section 3.1 was {\sf A=0}
since this increases the concentration of $\oplus$ bindings from 9 in 64
to 3 in 9 (with a corresponding information gain).
>From \ffoil's perspective, however, this literal simply reduces six
$\odot$ bindings to three and so gives no gain;
as the range of {\sf plus} is the set \{0,1,2\},
$r=3$, and so the putative concentration of $\oplus$ bindings would
alter from 6 in 18 to 3 in 9.
The literal {\sf A=C}, on the other hand,
causes the value of the output variable to be determined and results in
the bindings
\begin{center}
\begin{tabular}[b]{ccc}
\tuple{0,0,0} $\oplus$&
\tuple{1,0,1} $\oplus$&
\tuple{2,0,2} $\oplus$\\
\hline
\tuple{0,1,0} $\ominus$&
\tuple{1,1,1} $\ominus$&
\tuple{0,2,0} $\ominus$\\
\end{tabular} .
\end{center}
This corresponds to an increase in concentration of $\oplus$
bindings from a notional 6 in 18 to 3 in 6, with an information gain of
about 2 bits.
Once this literal has been added to the clause body, \ffoil\ finds
that a further literal {\sf B=0} eliminates all
$\ominus$ bindings, giving the complete clause
%
\qbox{plus(A,B,C) :- A=C, B=0.}
%
The remaining tuples of {\sf plus} give the bindings
\begin{center}
\begin{tabular}{ccc}
\tuple{0,1,$\Box$} $\odot$&
\tuple{1,1,$\Box$} $\odot$&
\tuple{0,2,$\Box$} $\odot$\\
\end{tabular}
\end{center}
at the start of the second clause.
The literals {\sf dec(B,D)} and {\sf dec(E,A)} are both determinate and,
when they are added to the clause, the bindings become
\begin{center}
\begin{tabular}{ccc}
\tuple{0,1,$\Box$,0,1} $\odot$&
\tuple{1,1,$\Box$,0,2} $\odot$&
\tuple{0,2,$\Box$,1,1} $\odot$\\
\end{tabular}
\end{center}
in which the output variable is still undetermined.
If the partial clause is further specialized by adding
the literal {\sf plus(E,D,C)}, the new bindings
\begin{center}
\begin{tabular}{ccc}
\tuple{0,1,1,0,1} $\oplus$&
\tuple{1,1,2,0,2} $\oplus$&
\tuple{0,2,2,1,1} $\oplus$\\
\end{tabular}
\end{center}
give the correct value for {\sf C} in each case.
Since there are no $\odot$ or $\ominus$ bindings, this clause is also
complete.

One important consequence of the new way that bindings
are initialized  at
the start of each clause is easily overlooked.
With \foil, there is one $\ominus$ binding for each tuple that does not
belong in $R$; since each clause excludes all $\ominus$ bindings,
it discriminates some tuples in $R$ from all tuples not in $R$.
This is the 
reason that the learned clauses can be regarded as a set
and can be executed in any order without changing the set of answers
to a query.
In \ffoil, however,
the initial bindings concern only the remaining tuples in $R$, so
a learned clause
depends on the context established by earlier clauses.
%discriminates some tuples in $R$ from the corresponding
%tuples not in $R$;
%it does not necessarily discriminate tuples in $R$ from tuples covered
%by previous clauses!
For example, suppose a target relation {\sf S} and a background
relation {\sf T} are defined as
%
\qbox{S = \{\tuple{v,1}, \tuple{w,1}, \tuple{x,1}, \tuple{y,0}, \tuple{z,0}\}\\
T = \{\tuple{v}, \tuple{w}, \tuple{x}\} .}
%
The first clause learned by \ffoil\ might be
%
\qbox{S(A,1) :- T(A).}
%
and the remaining bindings {\sf \{\tuple{y,0}, \tuple{z,0}\}} could then be
covered by the clause
%
\qbox{S(A,0).}
%
The latter clause is clearly correct only for standard queries that are not
covered by the first clause.
As this example illustrates,
the learned clauses must be interpreted in the order in
which they were learned, and each clause must be ended with a cut `!'
to protect later clauses from giving possibly incorrect answers to a query.
Since the target relation $R$ is functional, so that there is only
one correct response to a standard query as defined above,
this use of cuts is safe in that it cannot rule out a correct answer.

Both \foil\ and \ffoil\ tend to give up too easily when learning
definitions to explain noisy data.  This can result in over-specialized
clauses that cover the target relation only partially.
On tasks for which the definition learned by \ffoil\ is incomplete,
a final {\it global simplification} phase is invoked.
Clauses in the definition are generalized by removing literals
so long as the total number of errors on the target relation
does not increase.
In this way, the accuracy of individual clauses is balanced against
the accuracy of the definition as a whole; simplifying a clause
by removing a literal may increase the number of errors made by
the clause, but this can be offset by a reduction in the number of
uncovered bindings and a consequently lower global error rate.
When all clauses have been simplified as much as possible,
entire clauses that contribute nothing to the accuracy of the definition
are removed.

In the final step of Figure 2,
the target relation is assumed to represent a total function,
with the consequence that
a response must always be returned for a standard query.
As a safeguard, \ffoil\ adds a default clause
%
\qbox{$R(X_1,X_2,...,X_{n-1},c).$}
%
where $c$ is the most common value of the function.\footnote{No default
clause is added if each value of the function occurs only once.}
The most common value of the output argument of {\sf plus} is 2,
so the complete definition for this example,
in normal Prolog notation, becomes
%
\qbox{plus(A,0,A) :- !.\\
plus(A,B,C) :- dec(B,D), dec(E,A), plus(E,D,C), !.\\
plus(A,B,2).}

\subsection{Advantages and disadvantages of \ffoil}

Although 
the definitions for {\sf plus} in Sections 3.1 and 4.2
are superficially similar,
there are considerable differences in the learning processes by
which they were constructed and in their operational characteristics
when used.
\begin{itemize}
\item \ffoil\ generally needs to maintain fewer bindings and so learns
more quickly.
Whereas \foil\ keeps up to 27 bindings while learning a definition
of {\sf plus}, \ffoil\ never uses more than 6.
\item The output variable is guaranteed to be
bound in every clause learned by \ffoil.
This is not necessarily the case with \foil, since there is no requirement
that every variable appearing in the head must also appear in the
clause body.
\item Definitions found by \ffoil\ often execute more efficiently
than their \foil\ counterparts.
Firstly, \ffoil\ definitions, through the use of cuts, exploit the
fact that there cannot be more than one correct answer to a
standard query.
Secondly, clause bodies constructed by \ffoil\ tend not to use the
output variable until it has been bound, so there is less backtracking
during evaluation.
As an illustration, the \foil\ definition of Section 3.1
evaluates 81 goals in answering the query {\sf plus(1,1,X)\qq},
many more than the six evaluations needed by the \ffoil\ definition
for the same query.
\end{itemize}
There are also entries on the other side of the ledger:
\begin{itemize}
\item \foil\ is applicable to more learning tasks that \ffoil,
which is limited to learning definitions of functional relations.
\item The implementation of \ffoil\ is more complex
than that of \foil.  For example, many of the heuristics for pruning the
literal search space and for checking recursive soundness require
special cases for the constant $\Box$ and for $\odot$ bindings.
\end{itemize}

\section{Empirical Trials}
\label{results}

In this section the performance of \ffoil\ on a variety
of learning tasks is summarized and compared with that of \foil\ (release
6.4).
Since the systems are similar in most respects, this comparison highlights
the consequences of restricting the target relation to a function.
Times are for a DEC AXP 3000/900 workstation.
The learned definitions from the first three subsections may be found
in the Appendix.

\subsection{Small list manipulation programs}

Quinlan and Cameron-Jones (1993) report the results of
applying \foil\ to 16 tasks
taken from Bratko's (1990) well-known
Prolog text.
The list-processing examples and exercises of Chapter 3 
are attempted in sequence, where the background information for each
task includes all previously-encountered relations (even though most
of them are irrelevant to the task at hand).
Two different vocabularies are used: all 40 lists of length up to 3
on three elements and all 341 lists of length up to 4 on four elements.

\begin{figure}
\begin{center}
\begin{tabular}{|l c|rrr r|rrr r|}
\hline
Task& Bkgd& \multicolumn{4}{c|}{Length 3}& \multicolumn{4}{c|}{Length 4}\\
\cline{3-10}
&Relns&
\multicolumn{2}{c}{Bindings}&
\multicolumn{2}{c|}{Time}&
\multicolumn{2}{c}{Bindings}&
\multicolumn{2}{c|}{Time}\\
&&\multicolumn{1}{c}{$\oplus$}&
\multicolumn{1}{c}{$\ominus$}&
\foil& \ffoil&
\multicolumn{1}{c}{$\oplus$}&
\multicolumn{1}{c}{$\ominus$}&
\foil& \ffoil\\
\hline
append& 2& 142& 63,858& 3.0& 0.5&
	1593& 396,502& 22.4& 10.9\\
last element& 3& 39& 81& 0.0& 0.0&
	340& 1024& 0.5& 0.3\\
reverse& 10& 40& 1560& 2.6& 0.3&
	341& 115,940& 195.9& 9.0\\
left shift& 12& 39& 1561& 0.5& 0.3&
	340& 115,940& 26.6& 6.8\\
translate& 14& 40& 3120& 817.9& 1.1&
	341& 115,940& 495.9& 28.0\\
\hline
\end{tabular}

\vspace{\baselineskip}
{\it Table 1:} Results on tasks from (Bratko, 1990).\\
\end{center}
\end{figure}
Table 1 describes the five functional relations in this set
and presents the performance of \foil\ and \ffoil\ on them.
All the learned definitions are correct for arbitrary lists, with one
exception -- \foil's definition of {\sf reverse} learned from
the larger vocabulary includes the clause
%
\qbox{reverse(A,A) :- append(A,A,C), del(D,E,C).}
%
that exploits the bounded length of lists.\footnote{If
{\sf C} is twice the length of {\sf A} and {\sf E} is one element longer
than {\sf C} while still having length $\leq 4$, then
the length of {\sf A} must be 0 or 1.  In that case {\sf A} is its
own reverse.}
The times reveal a considerable advantage to \ffoil\ in all tasks
except the second.  In fact, for the first and last task with the
larger vocabulary, these times understate \ffoil's advantage.
The total number of bindings for {\sf append} is $341^3$, or about
40 million, so a \foil\ option was used to sample only 1\% of the
$\ominus$ bindings to prevent \foil\ exceeding available
memory.  Had it been possible to run \foil\ with all
bindings, the time required to learn the definition would have
been considerably longer.
Similarly, \foil\ exhausted available memory on the translation task
when all 232,221 possible bindings were used,
so the above results were obtained using a
sample of 50\% of the $\ominus$ bindings.

\subsection{Learning quicksort and bubblesort}

These tasks concern learning how to sort lists from examples
of sorted lists.
In the first, the target relation 