Tractable Induction and Classification in First Order Logic Via Stochastic Matching

1 Introduction

This paper is concerned with learning from examples ex­ pressed in (a restriction of) First-Order Logic (FOL). This language is required to describe examples that in­ clude several objects of the same kind (e.g. a car involves several wheels, a molecule involves several atoms), either when these objects cannot be ranked in a canonical way (e.g. atoms in a molecule) or when it makes sense to compare objects of different ranks (e.g. front left and front right wheels).

Learning in FOL, usually referred to as Inductive Logic Programming (ILP) (Muggleton & De Raedt, 1994) , is receiving growing attention as it appears the only way for machine learning to tackle complex domains such as organic chemistry (King, Srinivasan, & Sternberg, 1995)

Celine Rouveirol

LRI, Universite d'Orsay 91405 Orsay, France

Celine .Rouveirol@lri.fr

or natural language (Mooney, 1996). And a number of FOL learners have been developed: FOIL (Quinlan, 1990) , ML-Smart (Bergadano & Giordana, 1990) , FOCL (Pazzani & Kibler , 1992) , KEG (Bisson, 1992), REGAL (Giordana & Neri, 1994), PROGOL (Muggleton, 1995) , RIEL (Emde & Wettscherek, 1996) and REMO (Zucker & Ganascia, 1996) to name a few.

The specific difficulty of ILP is related to the match­ ing step: If a clause involves three literals part and the description of a given device involves 40 parts, there are 40 3 possible ways (termed matchings) to instantiate the literals in the clause by the literals describing the de­ vice. Discriminant induction requires all such match­ ings to be considered (to ensure the clause discrimi­ nates the device); and the same goes for deduction in the worst case (to check whether the clause covers the device). In other words, induction and deduction are exponential in the size of FOL hypotheses. This limita­ tion is dealt with in the literature by inducing short hy­ potheses, by means of search strategies (Quinlan, 1990; Bergadano & Giordana, 1990; Pazzani & Kibler , 1992; Muggleton, 1995) and/or syntactic restrictions (Gior­ dana & Neri , 1994; Kietz & Liibbe, 1994; Muggleton, 1995) .

This paper is interested in polynomial induction and use of FOL hypotheses, with no size restrictions. This is made possible by stochastic matching: one only consid­ ers some samples of matchings between examples and hypotheses - instead of exhaustively considering all matchings between examples and (short) hypotheses. The considered matchings are constructed by a stochas­ tic sampling mechanism, and the number of samples al­ lowed is supplied by the user. By so-doing, s/he controls both the induction cost (linear in the number of samples) and the quality of the hypotheses (the more samples are considered, the more likely the hypotheses are consis­ tent).

This heuristic is embedded in the Disjunctive Ver­ sion Space framework (DiVS) (Sebag, 1996) , which con­ structs all consistent hypotheses covering at least one training example. This framework extends that of Ver­ sion Space (Mitchell, 1982) and likewise implies a single bias, that of the hypothesis language. In particular, as it does not restrict the size of hypotheses, Di VS shows intractable for hypothesis languages such as logic programs or constraint logic programs 1 (Sebag & Rouveirol , 1996) .

The algorithm combining Di VS and stochastic match­ ing is termed STILL for Stochastic Inductive Learning. Stochastic matching allows STILL to learn hypotheses of any size (at most as long as the examples) in polynomial time, and to use them in polynomial time too. Stochas­ tic matching corresponds to a new kind of learning bias (Mitchell , 1991). The stochastic bias contrasts with lan­ guage and search biases, inasmuch it does not involve any expert knowledge about the problem or about how to find relevant solutions. Rather , it reflects the avail­ able computational resources; and the more resources, the better.

This paper is organized as follows . Section 2 briefly presents Di VS; the reader is assumed to be familiar with the Version Space (VS) framework (Mitchell , 1982). Section 3 details the stochastic sampling mechanism and outlines the induction and classification algorithms of STILL. Experimental validation on the mutagenesis problem (King, Srinivasan, & Sternberg, 1995) is pre­ sented in section 4; the influence of the stochastic match­ ing mechanism is discussed, and STILL is compared to prominent learners. We conclude with some research perspectives.

2 Disjunctive Version Space

This section recalls how Disjunctive Version Space ad­ dresses the limitations of Version Space (failures, expo­ nential complexity). Details on the algorithms are found in (Sebag, 1996; Sebag & Rouveirol , 1996).

2.1 Overcoming VS failures

Basically, VS fails when the maximally specific complete hypotheses (set S) are not more specific than the maxi­ mally general consistent hypotheses (set G). But noisy examples lead to over-generalize S and over-specialize G; and examples from a disjunctive concept result in an over-generalization of S if the hypothesis language is conjunctive. This explains why VS fails to handle real­ world problems, which include noisy examples and tackle disjunctive concepts most of the time.

VS failures are soundly prevented in three cases: a) when there is no negative example; b) when there is no positive example; and c) when there is exactly one positive example E , provided that E does not belong also to the negative examples (which can easily be checked). The third case is preferred as it is more robust with regard to noise (Sebag, 1996).

The general case, that is, learning from several posi­ tive and negative examples , is amenable to the favorable case of a unique positive example by hybridizing Version Space and the AQ algorithm (Michalski , 1983): For each (positive or negative) seed example E , one constructs the star H (E) as the set of all consistent hypotheses covering E. If F1 , .. Fm denote the examples not belonging to the same class as E , termed counter-examples 2 to E , H (E) exactly is the version space learned from E as unique positive example, and F; as negative examples.

1 Constraint logic programming notably contains t he ex­ tensions of logic programming concerned with number han­ dling. But this point will not be discussed herein .

The disjunction of the stars H(E) , for E ranging over the training set, constitutes the Disjunctive Version Space of all consistent partially complete hypotheses.

2.2 Overcoming VS intractability

Building H(E) is intractable even within a propositional language: H(E) is characterized by its lower bound (S = E) and its upper bound G, which is the disjunc­ tion of an exponential number of conjunctive hypotheses (Haussler, 1988) .

Di VS overcomes this limitation by characterizing H(E) as a conjunction of disjunctions. This is done as follows. Let D(E, F;) denote the set of hypotheses cov­ ering E and discriminating counter-example F;. H(E) includes all hypotheses discriminating all F;, hence it is equal to the conjunction of D(E, F;), for F; ranging over the counter-examples to E .

In an attribute-value language, D(E, F;) gets character­ ized as the disjunction of all maximally general selec­ tors (Michalski, 1983) discriminating E and F;. Table 1 illustrates how D(E, F ) can be built from E and F with linear complexity in the number of attributes; se­ lectors are here restricted to [att = V] , where V denotes a value in the domain of a nominal attribute att , or an interval in the domain of a linear attribute att (selector [size= (12, + oo)] is written [si ze > 12] for the sake of simplicity).

As in most bottom-up approaches, missing values are handled without problems and no preliminary discretiza­ tion of linear attribute domains is required.

Finally, the complexity of building H(E) is in O(N x P), where N denotes the number of examples and P the number of attributes. The whole disjunctive version space is characterized with complexity O(N 2 x P ).

2.3 Flexible classification with DiVS

Classification in Di VS much resembles a k-nearest­ neighbor (k-NN) classification process: An instance E' is said to be neighbor of a training example E iff there exists a hypothesis in H(E) that covers E' (one says for short that E' belongs to H (E)); and E' is classified according to the majority vote of its neighbors.

2 The counter-examples to a positive example are t he neg­ ative examples; and vice versa.

Table 2: FOL and Tabular Representations of E and F

E: active(a) :- atam(a,a1,carbon,22),atom(a,a2,hydrogen,3),cc(a,a1,a3 )

F : inactive(b) :- atam(b, b1, hydrogen,2) ,atom(b,b2,oxygen,19)

These neighborhoods, and hence the classification pro­ cess, can be tuned to cope with noise. Formally, E' be­ longs to H(E) iff it belongs to D(E, Fi) for all Fi counter­ examples to E. This condition is relaxed by allowing E: exceptions (counter-examples Fi such that E' does not belong to D(E, Fi)).

Independently, H(E) can also be made more specific to cope with sparse data. Formally, D(E, Fi) is a dis­ junction of selectors and E' belongs to D(E, Fi) iff it satisfies at least one of these selectors. This is modified by handling from now on D(E, Fi) as an M-of-P con­ cept: E' thereafter belongs to D(E, Fi) iff it satisfies at least M selectors in D(E, Fi)-

This way, the set of consistent and partially complete hypotheses is constructed once and for all. Still, classi­ fication can employ hypotheses of any degree of consis­ tency and generality - at no extra cost: the complexity of classification is O(N 2 x P).

2.4 DiVS In First-Order Logic

Let us see how the construction of the set D(E, F) of hypotheses covering E and discriminating F extends to FOL. Let E and F be now described as definite clauses 3 , the head of which are built on opposite target predicates (Table 2). Let us express seed E as E = CB, where C is the clause obtained from E by turning every term t i in E into a distinct variable X j, and B is the substitution on C defined by {Xj / ti} .

Let the hypothesis language be that of constrained clauses Gp, where G generalizes C and p is a conjunc­ tion of constraints generalizing e (a formal presentation is found in (Sebag & Rouveirol , 1996)). Such clauses generalize seed E by construction; they discriminate F iff they do not generalize the clause~ F , built from F by replacing the predicate in its head (e.g. inactive) by the opposite target predicate (active).

Clause C allows for a tabular representation of E and - F (Table 2). By construction, E is represented by sub­ stitution B. Let the clause built from C by dropping all predicates absent from F (here cc), be still denoted C by abuse of notation. Then by construction~ F is subsumed by C, and F is described 4 by the set L:F of substitutions a- on C, such that Cu ~ ~F. In our example, L:p ineludes four substitutions a-1 ... a-4 , which correspond to the four ways of mapping the two literals atam in C onto the two literals atom in F.

3 The reader interested in learning from constrained clauses is referred to (Sebag & Rouveirol, 1996).

4 Given the hypothesis language, predicates in F that are absent from E can be omitted with no loss of informat ion.

This attribute-value reformulation of FOL examples much resembles the LINUS and REMO approaches (Lavrac & Dzeroski, 1994; Zucker & Ganascia, 1996). The difference is twofold. First, the tabular reformu­ lation in LINUS and REMO operates on the whole dataset ; the format of the table is derived from a single clause, specialized if no satisfactory hypothesis is found during the current induction step. Second, the refor­ mulation is one-to-one in . LINUS, thanks to syntactic restrictions, and it is one-to-many in REMO (but the exponential factor is limited by the size of the clause). In contrast, the reformulation in DiVS is rather bottom­ up than top-down: the format of the table is derived from the current seed example, and one considers at once all information conveyed by the seed. Hence, the reformulation is one-to-one for the seed (E is completely described by e given C) whereas it is one-to-many for the counter-examples. As the exponential factor is not limited here, DiVS turns out to be intractable on real relational problems (see below).

Given this reformulation of E and F , building D(E, F ) is amenable to attribute-value discrimination: substitu­ tions on C can be handled as attribute-value examples and conjunctive constraints on C can be handled as con­ junctions of selectors in the same attribute-value lan­ guage. Finally, let P F denote the set of predicates in E absent from F ; then Gp in the hypothesis language belongs to D(E, F) iff either G includes a predicate in PF, or p belongs to D(B, a-) for all a- in I:F.

Further, an instance E' belongs to D(E, F) iff E' is subsumed by GT, where G generalizes the body of C and either G includes a predicate in P F, or T belongs to D ( e l 0") , for all 0" in I: F.

3 Stochastic Induction and Classification

This section describes how to construct FOL hypotheses at a polynomial cost, with no size restrictions. Further, these hypotheses can be used at polynomial cost too.

3.1 Stochastic Induction

As seen in section 2.4, Di VS can construct hypotheses including as many literals as the seed. The size of the matching set L:p can thus be exponential in the size of the examples; e.g. in the mutagenesis dataset , examples are described by up to 40 literals atoms; the size of L;p hence goes up to 40 40 ...

To overcome this limitation, only a fraction of the sub­ stitutions in L;p is considered. The number of substitu­ tions to consider, noted 'T} , is supplied by the user, and these substitutions are provided by a stochastic sampling mechanism, as follows . For each literal p(X1 ,X2 , .. ) in C, a literal p( t1 , t2 ... ) built on the same predicate is se­ lected with uniform probability in F; substitution a is iteratively defined by a = a U { X;jti}. More sophis­ ticated sampling mechanisms can also be designed (see section 4.2).

By combining Di VS with such a sampling mechanism, STILL constructs an approximation of D(E, F), noted D 17 (E,F):

Definition 1. Let L; 17 be a set of 'T} substitutions sam­ pled in L;p, and let Gp be in the hypothesis language. Gp belongs to D 17 (E, F) iff either G includes a predicate in Pp , or pis in D(B,a) for all a in L; 17 .

By construction, D 17 (E, F) includes D(E, F) and D17 (E, F) goes to D(E, F) as 'TJ goes to infinity. The important point is that D 17 (E, F) is constructed with polynomial complexity: the construction of a sample a is linear in the number of literals in C, and the construc­ tion of D( B, a) is linear in the number V of variables inC. As the number of literals is less than V, the complexity of D 17 (E, F) is O('TJ x V).

STILL finally approximates the star H(E) of a seed example E as H 17 (E) , given as the conjunction of D 17 (E, Fi) for Fi ranging over the counter-examples to E. The Disjunctive Version Space is approximated as the collection of stars H 17 (E) for E ranging over the train­ ing examples. If N still denotes the number of training examples , the complexity of STILL induction finally is 0(7) X v X N 2 ).

3.2 Stochastic Classification

The fact that the hypotheses in D 17 (E, F) can be con­ structed at a polynomial cost particularly does not imply that they can be used at a polynomial cost: as mentioned earlier on, deduction is potentially exponential in the size of FOL hypotheses.

Let E' be the current instance to classify, let the clause obtained from C by dropping all predicates absent from E' be still denoted C by abuse of notation, and let L;E' denote the set of substitutions a on C such that Ca ~ E'. Then , checking whether E' is covered by a hypothesis in (for short, belongs to) Dry(E, F) normally requires to examine all substitutions in L;E' ; and the size of L;E' is no less than that of I; F ...

Again , this limitation is overcome by means of stochas­ tic matching: STILL only considers K substitutions ran­ domly sampled in L; E'.

Definition 2. Let L;K be a set of K substitutions se­ lected in I; E' . The instance E' is said to K -belong to D, 7 (E, F) if either E' includes a predicate absent from F or there exists at least one substitution r in L;K such that T belongs to D( e, a) for all a in L;1).

Note that, if E' K-belongs to D 17 (E, F) , it does belong to D 17 (E , F); but the converse is not necessarily true. The above definition thus corresponds to a more specific ac­ ception of D 17 (E, F) than the standard logical one. But again, this definition goes to the standard logical defini­ tion as K goes to infinity.

The complexity of checking whether E' K-belongs to D 17 (E , F) is in O(K x 'TJ x V) ; and finally the complexity of classification in STILL is O(K x 'TJ x V x N 2 ).

4 Experimental Validation

STILL has been experimented and compared to promi­ nent learners on the mutagenesis dataset (King, Srini­ vasan, & Sternberg, 1995) . We also compare the basic stochastic sampling mechanism with a specifically de­ signed sampling mechanism, which incorporates some expert knowledge. ·

4.1 The Data and Reference Results

The learning goal is to determine among the nitroaro­ matic molecules occurring in car exhaust fumes, those which might have a carcinogenic effect. The carcino­ genicity of a molecule is known to be correlated to its mutagenic activity, but the literature does not yet pro­ vide any explicit model for mutagenic activity.

Two descriptions of the mutagenicity problem are available. In a FOL framework , a molecule is represented by a definite clause, the head of which corresponds to its activity (boolean: active or inactive). The body of the clause describes: a) the atoms of the molecule and the bonds between these atoms; b) the global properties (five attributes) of the molecule, e.g. its hydrophobicity; and c) the chemical structures eventually present in the molecule, e.g. benzenic rings . As witnessed by the size of the matching set (section 3.1) , this description is truly relational. It has been processed by FOIL, PROGOL, and another ILP learner with number handling facilities , FORS (Karalic, 1995).

An attribute-value description of the molecules is also available; this second dataset has been processed by lin­ ear regression (LR), neural nets (NN) and CART.

Table 3 displays the reference results, obtained by 10-fold crossvalidation and reported from (Srinivasan & Muggleton, 1995) and (Karalic, 1995):

The computational costs given for PROGOL, FOIL and FORS vary with the description used: PRO­ COL takes from 117, 000 to 40,000 seconds (on HP735), FOIL from 9, 000 to .5 seconds (HP-735) and FORS about 900 seconds (on Sparc-10).

4.2 STILL results

In our experimental setting, the dataset was randomly divided into a training set including 90% of the data and a test set, in such a way that the ratio of active/inactive molecules is the same as in the whole dataset (2 to 1) . The result was averaged on 25 independent selections of the training/test sets. This procedure is in the same vein as 10-cross fold validation; but a higher number of independent runs is advisable to evaluate stochastic algorithms.

STILL involves 4 parameters: 'T/ and K , which respec­ tively control stochastic induction and stochastic deduc­ tion; and c: and M , which respectively control the consis­ tency and the generality of the hypotheses (section 2.3) , with c: = 0 and M = 1 respectively meant as perfect con­ sistency and maximal generality. Parameters 'T/ and K are set to 300 and 3; complementary experiments show that doubling 'T/ or K increases the predictive accuracy by less than one point. Parameters c: and M respectively vary between 0 and 4 (the value used for PROGOL) , and 1 and 10.

STILL was experimented with two sampling mecha­ nisms (SM). The first , basic one, was described in 3.1. The "advanced" one uses some naive (authors') knowl­ edge, by rather mapping an atom of a given kind i.n E , onto an atom of the same kind in F. More prec1sely, an atam is repeatedly selected with uniform probabil­ ity in C; this atom, say the i-th, is mapped by CJ onto the j-atom in F, such that atom j in F is as similar as possible 5 to atom i in E . The substitution CJ so defined can be viewed as a "near-miss" with respect to substitu­ tion B.

Table 4 displays the results obtained by STILL when combined with both sampling mechanisms. For each value of c: and M , the average predictive accuracy on the test set is given with its standard deviation, as well as the run-time in seconds on a Pentium 166. The pre­ dictive accuracy degrades gracefully as c: increases.

Unexpectedly, STILL does not perform better when combined with the "advanced" SM. This fact, rather en­ couraging with regards to the generality of stochastic induction, can be explained as follows . A substitution CJ built by the advanced SM tends to associate atoms in the seed E to the most similar atoms in the counter-example F. As a result , D( () , CJ) lists a few acute discriminant dif­ ferences , e.g. the electric-charge of atom 17 must be less than .33. In contrast, the basic SM compares any atom in E to any atom in F , and D(B, CJ) therefore lists anum­ ber of rough discriminant differences: atom 1 must be a carbon, atom 2 must be an hydrogen, atom 3 must be a carbon, ...

During classification, one checks whether an instance E' belongs to Dry(E, F) , i.e. whether there exists a sub­ stitution which satisfies at least M conditions listed in D(B, CJ) for all sampled CJ (section 2.3) . A substitution built by the advanced SM easily satisfies a few acute conditions: it is sufficient that the concerned atoms in E are considered first, and hence mapped on the sim­ ilar atoms in E'. Incidentally, this is why high values of M are required in this case (and the computational cost increases with M). In contrast, the ways atoms are "distributed" in E and E'- must be close in order for a substitution built by the basic SM to satisfy some out of the discriminant conditions in D( () , CJ) for all sampled CJ .

With respect to other ILP learners and on the mutage­ nesis problem, STILL shows quite competitive in terms of predictive accuracy. Further , it is faster by two or three orders of magnitude: e.g. PROGOL and FOIL process the purely structural description of molecules (atoms and bonds only) in respectively 60,000 and 9,000 seconds (Srinivasan & Muggleton, 1995) , whereas STILL takes less than two minutes for the same dataset (these times on HP-735 workstation).

5 Discussion and Perspectives

STILL inherits most characteristics of Version Spaces and Di VS, notably the absence of restrictions on candi­ date hypotheses, except consistency and (partial) com­ pleteness. This contrasts with most other learners searching for "optimal" candidate hypotheses, no matter whether this optimality refers to the quantity of informa­ tion, the Gini criterion or the MDL principle (Quinlan, 1990; Bergadano & Giordana, 1990; Muggleton, 1995). It has been suggested that redundancy (and Di VS and STILL are redundant to an extreme extent ) could im­ prove the reliability of the learning output (Webb, 1996). In any case, it avoids the disadvantages of myopic search, such as incurred by decision tree learners.

The price to pay is the readability of the learning output 6 : when expressed as a list (disjunction) of conjunctive hypotheses , Version Spaces are indeed of expo­ nential size (Haussler, 1988) .

6 However , STILL is definitely not a black box: the clas­ sification process constructively exhibits hypotheses relevant to the classification of the current instance. One can thus justify the classification of any instance from an intelligible sub- t heory, extracted from the whole theory.

Another aspect of STILL is that it combines logi­ cal aspects and example neighborhoods, in the line of KEG (Bisson, 1992), RISE (Domingos, 1995) and RIEL (Emde & Wettscherek, 1996). The specificity of STILL is that it involves neighborhoods which are constructed by induction, whereas the above learners rely on a built­ in similarity or distance.

But the main originality of STILL, due to the stochas­ tic matching heuristic, is to allow a number of expensive hypotheses to be approximately characterized and used. This contrasts with the main trend in ILP, oriented to­ ward the exact characterization of a few affordable hy­ potheses. Further, stochastic matching allows a fine con­ trol of the computational cost, with no expert knowledge on the problem domain.

Note that the use of stochasticity in STILL radically differs from what is done in GA-based learners such as REGAL (Giordana & Neri, 1994): in STILL the stochastic mechanism samples the matching space and it operates as a pre-processor of induction; in contrast, the stochastic mechanism in REGAL samples the hypoth­ esis space and so to say replaces 7 induction. Note also that STILL does not directly pertain to the Bayesian Inductive Logic Programming framework (Muggleton, 1994), nor to probabilistic induction, in the sense that it does neither assume nor take as input any a priori probability distribution on the hypothesis space.

A main perspective of research is to give STILL a PAC model in the sense of Valiant (1984): stochastic induc­ tion and deduction approximate standard induction and deduction, and one would like to know how the num­ ber of samples 11 and K relate to the probability for this approximation to be correct.