FOIDL [4] is an inductive logic programming (ILP) [3] system. Unlike most other ILP approaches that learn unordered sets of Horn clauses, FOIDL learns first-order decision lists, i.e., ordered lists of clauses. First-order decision lists seem to be a very appropriate formalism for representing linguistic knowledge, as they allow for an elegant way of representing exceptions to general rules. The exceptions are placed before the general rules in a decision list: the first applicable rule from the list is used when treating new cases. The data structure produced by FOIDL thus implements a version of the Elsewhere Condition, well known in morphological theory [2].
Another important feature of FOIDL is its ability to learn decision lists from positive examples only. Most other ILP systems rely on negative examples to avoid overly general hypotheses. FOIDL on the other hand, uses an output completeness assumption. A mode declaration for the target predicates is provided by the user, specifying for each argument whether it is an input or an output argument. The output completeness assumption states that the training set contains all of the corresponding output patterns for every unique input pattern that it contains. The ability to learn from positive data only is also very important for almost all linguistic applications of ILP.
Like all ILP systems, FOIDL can use background knowledge defining predicates relevant for learning the target predicate. While some ILP systems, e.g., FOIL [5], can only use extensional background knowledge, consisting of ground facts only, FOIDL can use intensional background knowledge consisting of PROLOG clauses. Predicates for list processing, relevant for learning linguistic concepts, can thus be represented concisely and efficiently.
FOIDL has been successfully applied to the problem of learning rules for forming the past tense of English verbs [4]. Three different variants of the problem have been addressed: phonetic representation, phonetic representation of regular verbs only, and orthographic representation. For illustration, past([s,l,e,e,p],[s,l,e,p,t]) is a positive example for the last case.
In all three cases, the list processing predicate split(A,B,C), which splits a list A into two nonempty lists B and C, was used as background knowledge. This predicate is defined as:
split([X,Y|Z],[X],[Y|Z]). split([X|Y],[X|Z],W) :- split(Y,Z,W).
The first argument (present tense of the verb) of the target predicate past is an input argument and the second (past tense) is an output argument. FOIDL was given the opportunity to use constant prefixes and suffixes in its rules. An excerpt from a first-order decision list learned by FOIDL from 250 examples is given below.
past(A,B) :- split(A,C,[e,p]), split(B,C,[p,t]),!. ... past(A,B) :- split(B,A,[d]), split(A,C,[e]), !. past(A,B) :- split(B,A,[e,d]).
Note the ! (cuts) in the clauses: these indicate that only the first applicable clause from the list should be used when treating new examples. The FOIDL output, however, does not list the cuts. The FOIDL output in the next Section is shown in its original form without cuts. When treating new cases, it is interpreted as a decision list, i.e., as if the cuts were there.
Given 1392 examples, FOIDL used up to 500 examples for learning and the remainder for testing. Given 500 examples for learning, FOIDL achieves accuracy of approximately 85% on the testing set. The running time on a SUN SPARC 10 was on the order of 8 hours.