Learning Structural Decision Trees from Examples

1 Introduction

Structural learning, also known as relational learning, has a long if not prominent history in machine learning. Like attribute-value concept learners, structural concept learners try to induce a description of a concept from positive and negative examples of the concept. Struc­ tural concept learners differ in using a more expressive first-order predicate calculus representation for their hy­ potheses.

One of the reasons for the unpopularity of structural learning is the problems posed by learning in a first­ order representation. Examples are described in terms of objects and the relationships among them; hypotheses may include existentially quantified variables. The abili­ ty to quantify over objects adds a great deal of expressive power to the representation. However, even matching a hypothesis to an example is an NP-complete problem [Haussler, 1989].

Recently, the advantages of a first-order representation have motivated further research into learning in this hy­ pothesis language. FOIL [Quinlan, 1990a] KATE [Man­ ago, 1989], are some recent systems that can learn struc­ tural concepts.

This paper introduces a system, STRUCT, that learn­ s structural concepts from positive and negative exam­ ples. STRUCT integrates and extends previous work

*This research was supported in part by NSF grant IRI 8822031.

Larry Rendell

Beckman Institute and Dept. of Computer Science University of Illinois Urbana, IL 61801

in structural and attribute-value machine learning re­ search. From KATE it borrows the use of decision trees to learn structural concepts. From FOIL it borrows the approach and several techniques. From FRINGE [Pagal­ lo and Haussler, 1990] it borrows the iterative, adaptive feature construction algorithm to produce more concise, accurate, decision trees. From INDUCE [Dietterich and Michalski, 1981] it borrows the representation of exam­ ples.

The main purpose of this paper is to explore how these different techniques can be integrated into a structural concept learning system. In addition, this paper de­ scribes the results of empirically evaluating several of these refinements.

The paper is organized as follows. First, we describe related research in section 2. The algorithm is described in section 3. Next, we describe some experiments in structural domains and discuss the results of these ex­ periments. Section 5 presents the conclusions of this research.

2 Related Work

In this section, we review systems that use an information-theoretic approach to learning disjunctive structural descriptions. There are many systems that use other approaches, or address different problems in structural learning. Some of these systems are described in [Kodratoff and Ganascia, 1986; Iba et al., 1988; Muggleton, 1990].

2.1 Separate-and-conquer

Separate-and-conquer algorithms for structural domains, also known as covering algorithms, try to find a DNF de­ scription of a concept by iteratively generating disjuncts that cover some of the positive examples while excluding the negative examples.

An early application of this algorithm to structural do­ mains is INDUCE [Dietterich and Michalski, 1981]. IN­ DUCE generates disjuncts by constructing a cover from from the literals of one positive example, called the seed.

Quinlan's more recent FOIL [1989; 1990] differs from INDUCE in a number of ways. First, it uses a tuple­ based learning paradigm, as opposed to an example­ based learning paradigm. Second, FOIL does not re­ strict the cover to use literals from a seed but searches the entire space of literals. We refer to this as full-width search, because all one-step specializations are consid­ ered as candidates. However, having evaluated the can­ didates, FOIL commits itself to one particular choice and discards the other candidates. In contrast, INDUCE chooses a subset of the candidates for specialization. Third, INDUCE uses a general user definable evaluation function, whereas FOIL's information-theoretic evalua­ tion function is an integral part of the system.

Another recent separate-and-conquer algorithm for learning structural descriptions is Pazzani and Kibler's [1990) FOCL algorithm. FOCL uses a form of typed logic with sortal and semantic constraints to reduce the number of literals considered for inclusion in the cover. This improves efficiency and accuracy. FOCL can also use incomplete and incorrect background knowledge to aid induction, and an iterative-widening search to find a cover for the examples.

2.2 Divide-and-conquer

Although divide-and-conquer algorithms, also known as decision tree inducers, have been widely used in attribute-value domains, until recently few systems have used this strategy in structural domains. Bergadano and Giordana's [1988) ML-SMART system uses a special­ ization tree approach that uses heuristics and domain knowledge to drive induction. Manago's [1989) KATE is a decision-tree algorithm that uses an object-oriented frame language equivalent to first-order predicate calcu­ lus. KATE makes extensive use of the structure provid­ ed by the object hierarchy and heuristics to control the generation of literals considered as branch tests. This system has a strong bias against introducing new ex­ istentially quantified variables into the description, un­ like FOIL which favors introducing new variables. Later, we discuss an experiment comparing the two strategies. Manago has also used INDUCE's partial-star algorithm as a feature construction algorithm for KATE.

2.3 Adaptive Feature Construction

Like FOIL, Pagallo and Haussler's [1990] FRINGE uses a tuple-based learning paradigm, but unlike the structure­ oriented systems, FRINGE uses the tuples simply as ex­ amples for atribute-based leaning. FRINGE also differs from INDUCE, FOIL, FOCL, KATE, and ML-SMART in that FRINGE accepts only the training examples, no other knowledge. Nevertheless, FRINGE and its succes­ sors Symmetric FRINGE [Pagallo, 1990) and DCFringe [Yang et a/., 1991] have been shown to improve accura­ cy. These algorithms learn structure in the form of new features constructed as more and more complex conjunc­ tions and disjunctions of the original attributes. The scheme is to perform iterative feature construction at the leaves of successive decision trees output by an ID3like algorithm. Extensions of the FRINGE method have been tested by Matheus [1990) which do not restrict con­ structions to the fringe nodes [also see Yang et a/., 90).

3 STRUCT

Our system learns structural decision trees from positive and negative examples.

Databases: DBl = Train: father( Christopher, Arthur), father( Christopher, Victoria), mother(Penelope, Arthur), mother(Penelope, Victoria), brother(Arthur, Victoria), sister(Victoria, Arthur), son(Arthur, Christopher), son(Arthur, Penelope), daughter(Victoria, Christopher), daughter(Victoria, Penelope), husband(Christopher, Penelope), wife( Penelope, Christopher). father(Christopher, Arthur) :- DBl -father(Victoria, Arthur) :- DBl Classes:

father(X, Y)

Figure 1: Input for STRUCT.

3.1 Representation

STRUCT represents relations as Horn clauses. A Horn clause can be viewed as a logical implication, where the consequent consists of a single literal, called the head of the Horn clause, and the antecedent consists of zero or more literals, called the body of the Horn clause. This representation of examples is similar to the inductive assertions used in INDUCE. In contrast, FOIL learns a relation from positive and negative tuples of a rela­ tion. The following shows the input for STRUCT: The Databases section defines zero or more databases that can be referenced by examples. Examples are horn claus­ es, whose antecedent may be an explicit list ofliterals or a reference to a database. The Classes section defines the classes that are to be included in the decision tree. Unifying the head of the training examples with the class literal yields the signed substitutions:

• +: {(Christopher/X),(Arthur/Y)}

-: {(Victoria/X),(Arthur/Y)}

where the sign of the substitution indicates whether one of the literals was negated before unifying. In con­ trast, FOIL would be given the tuples

+: <Christopher, Arthur>

-: <Victoria, Arthur>

which are isomorphic to the substitutions constructed by STRUCT. The Classes may be followed by a Test section giving the test set.

The ability of STRUCT to store data in multiple databases rather than one global database can make induction more efficient . Information that is not rele­ vant to an example can be ignored when learning from that example. If this kind of relevance information is not available, all the data can still be stored in a single database.

STRUCT also represents knowledge in the form of Horn clauses. This knowledge may be prior knowledge given to the system or a constructed feature. Before constructing the decision tree, STRUCT computes the Create Tree( class, examples)

• create a node root labelled by the literal class.
• select the subset of examples whose head unifies with class or -,class
• RecursiveSplit( root)

RecursiveSplit( node)

If all training examples at node are positive or negative examples, label node with pos or neg.

else

• select a test based on one literal
• label node with the literal
• create child nodes, left and right
• place the examples that match node at left and the others at right
• RecursiveSplit(left)
• RecursiveSplit(right)

Figure 2: Recursive Splitting Algorithm.

deductive closure of the body of each example, and re­ places the body with the closure. This form of logical constructive induction has previously been implemented in INDUCE.

3.2 Structural Decision Trees

In this section we describe the decision tree formed by STRUCT and how it is used to classify examples. STRUCT learns a Boolean decision tree as shown in Fig­ ure 2. The decision tree algorithm is modified to han­ dle structural descriptions by associating a Horn clause with each of the nodes of the tree, and SLD-resolution is used as the match procedure. The clause associated with a node is defined by the following mapping. Let nodeo, ... , noden be the nodes along the path from the root to node nod en. Define L; to be the literal labeling node node; if node; is the left child of node;_1, other­ wise its negation. Then the clause La +--- L 1, ... , Ln is associated with node noden . The node noden matches an example if the head of the example can be derived with SLD-resolution from the above clause and the lit­ erals in the body of the example.

3.3 Generating Literals for Branch Tests

In this section, we first review FOIL's method for gener­ ating literals for branch tests, then compare its method to STRUCT's method.

FOIL generates the literals used as tests using the following procedure: If the clause associated with the current node is P(X1, ... , Xm) +--- L1, ... , Ln then a new literal of form Xj = X~;, Xj "# X~;, Q(V1, ... , Vr ), or ·Q(V1, ... , Vr) can be added to the clause, where X;'s are existing variables, the V; 's are existing or new vari­ ables, and Q is some relation. The entire space of these literals is searched with the following exceptions:

• literals may be pruned
• the literal must contain at least one existing variable
• the literal must satisfy some constraints designed to avoid problematic recursion.

In contrast, STRUCT generates the literals used as tests using the following procedure: if the current node is current, the parent of current is parent, the clause associated with parent is P(X1, ... , Xm) +- L1, ... , Ln , {) is a substitution that matches the current node to an example, Q(A1, ... ,A~;) is a literal in the example, and Q(V1, ... , V~;) o 0 = Q(A1. ... ,A~;), then Q(V1, ... , Vk) is a candidate literal for partitioning current. STRUCT also considers all candidate literals of form Xj = Xk, where X;'s are variables in the clause associated with parent . The entire space of these literals is searched with the following exceptions:

• the literal must contain at least one variable from parent
• the literal must satisfy constraints to avoid prob­ lematic recursion.

Pazzani and Kibler [1990] analyze the complexity of FOIL's approach, and describe how sortal and semantic constraints are incorporated into their system, FOCL. The complexity of FOIL's strategy, without pruning, is approximately ( n + k - 1 )k, where n is the number of old variables in the clause, and k is the arity of the predicate in the new literal. This must be repeated for each predi­ cate and each generated literal must be matched against the examples, so the cost of generating and choosing a literal for a node is upper bounded by t · p · ( n + k - 1 )k , where t is the number of tuples covered by the current clause, and p is the number of predicates. Quinlan re­ ports that pruning results in a dramatic improvement in the efficiency of the algorithm.

STRUCT's strategy is comparable in complexity to FOIL. The number of substitutions is the same as the number of tuples in Quinlan's formalism. The cost of generating and choosing a literal is upper bounded by t · I· ( v + k- 1)k, where t is the number of matches of the parent node to the examples, I is the number of lit­ erals, and v is the maximum number of variables that are bound to the the same constant in any substitition.

3.4 Evaluating Literals

STRUCT uses the following evaluation function to eval­ uate candidate literals. Let S be the set of examples at a node, X a literal, Sx the subset of S that matches X, and Sx, y the subset of Sx that belongs to class y. Then the evaluation function gives X the value:

Maximizing this evaluation function is equivalent maximizing information gain [Quinlan, 1983]. FOIL's evaluation function sums over the tuples covered by the new clause, and is therefore asymmetric. The above e­ valuation function sums over both the matched and un­ matched examples (not tuples).

FOIL gives a small credit to a literal that introduces new variables. STRUCT may give either a small reward or penalty (± .1) for each new variable in a literal. In our experimental section, we compare the effects of the reward and penalty strategies on the accuracy of the learned concepts.

1. Delete all instances of the relation to be learned from the database.
2. As the decision tree is constructed, whenever a leaf node is created, add the literals in the heads of the examples at the leaf nodes to the database.

Figure 3: Recursive Learning Strategy.

3.5 Recursive Definitions

One issue that faces structural learners is the problem of recursive definitions. Quinlan [1990] proposes a partial ordering strategy that can eliminate some, but not all, of the problematic recursion.

The problem arises because instances of the relation being learned are in the knowledge base. Clearly, the relation itself is the best feature for splitting the positive and negative examples; i.e.

perfectly splits the tree. But there is an implicit re­ quirement on the learning system that it be able to clas­ sify future examples without knowing the same kind of information that is available to it during training, name­ ly the classification of the example.

One possible approach to this problem is to explicitly remove from the database information that the decision tree is supposed to learn, unless the decision tree has already learned it (see Figure 3). STRUCT currently does not implement this procedure, but it avoids adding new literals with the same predicate and variables as the head of the clause. STRUCT also has a non-recursive mode, where definitions are may not add literals with the same predicate as the one being learned.

A second problem that can arise is an infinite regres­ sion during induction. For example, suppose the descrip­ tion associated with the current node is Q <-- P(X, Y, Z) and the literal to be added is P(X, Y', Z'). The new defi­ nition matches exactly the same set of examples, and the system may continue to add another alphabetic variant of the literal indefinitely:

To avoid this problem, STRUCT forms co-designation constraints on the possible bindings of a literal. These are created for every pair of literals L; and Lj, where

• Lj is a new literal that has just been added to the definition
• L; is a literal with the same predicate as Lj.
• The j-th argument of Lj is either a new variable, or is the same variable as the j-th argument of L;.

The constraint on unification of Lj is defined as fol­ lows: let Y1 , ... , Yn be the new variables in Lj, and X1, ... , Xn be the variables in L; at the corresponding argument positions. Then Y1 ::/: X1 , ... , Yn ::j: Xn are added as co-designation constraints on unification of Lj.

These co-designation constraints prevent the inductive recursion that sometimes occurred in earlier versions of STRUCT.

find-feature! (leaf) Let Lp be the literal at the parent node of leaf Let L 9 be the literal at the grandparent node of leaf If leaf is to the left of its parent Lo = Lp else Lo = -,£p If leaf is to the left of its grandparent Lt = L9 else Lt = -,£ 9 Return P(Xt, ... ,Xn) +-Lo,Lt, where X; are the variables from the unnegated literals in Lo, Lt and P is a new predicate. find-feature2(leaf) Let Lr be the literal at the root of the tree Let P(Xt, ... , Xn) +- Lo, Lt, be the feature returned by find-featurel(leaf) . Return P(Xt, ... ,Xn) +- Lo,Lt, with guard Lr

3.6 Feature Construction

One problem with decision trees as a representation scheme is that DNF concepts cannot be represented con­ cisely. Representing a DNF concept as a decision tree may require replicating many parts of each disjunct in d­ ifferent branches of the tree. Pagallo and Haussler [1990] call this the replication problem, and propose an adap­ tive, iterative feature construction algorthm, FRINGE, as a solution to this problem.

Pagallo and Haussler have conducted experiments with FRINGE in random and real-world domains. In the random domain experiments, FRINGE produced more concise and more accurate decision trees for small DNF. In the real-world domain experiments, FRINGE pro­ duced decision trees that were at least as accurate and more concise. In STRUCT, we investigated a modifica­ tion of the FRINGE algorithm for a structural decision tree. The algorithm is essentially the same as FRINGE, with a few changes to handle variables. The algorithm begins with the initial set of relations, and constructs a decision tree as described in the previous sections. Next , a find-features procedure generates a new set of relation definitions by examining the fringe of the tree, by calling find-featurel for each leaf in the tree at depth ~ 2 (see Figure 4).

We also implemented a variant of find-features, mo­ tivated by the following considerations. In the original find-features, the variables in literals at the fringe of the tree are usually bound by literals higher in the tree. However, the bindings are lost when the fringe literals are made into an independent feature. Thus, the feature tends to be overly general if the literal is unnegated, or overly specific if the literal is negated.

An additional source of potential problems is that the literal in the head of the example contains information that is ignored during feature construction. However, this literal cannot be added to the body of a feature definition because it matches literals in the head of an example, not the body. Accordingly, we modified the rule representation and matching algorithm to handle guard literals. These literals must match the head of an example as a precondition of the rule.

The find-features procedure constructs new relation definitions. The new relation definitions are added to the knowledge base, in the form of Horn clauses. Old re­ lation definitions are removed from the knowledge base if they define a relation that is not in the decision tree, and are not necessary for computing a relation that is in the decision tree. This method of feature pruning is Pagallo's Keep Used Last method. The examples are re­ placed by the deductive closure of the base level literals under the new knowledge base. Then, the decision tree algorithm and find-features procedure is repeated. The process stops when the same decision tree is constructed as in the previous iteration, or when a fixed number of iterations (7) is exceeded.

4 Experiments

We had several objectives in performing the experiments. First , we wanted to evaluate the overall performance of the system on some standard domains. Second, we want­ ed to determine if Quinlan's heuristic of assigning a small credit to new variables worked well in a decision tree sys­ tem. Third, we wanted to investigate the effectiveness of a modified FRINGE strategy for structural domains.

4.1 Kinship Domain

Hinton [1986] implemented a connectionist system for learning family relationships in two families. For a de­ tailed description of the learning task, we refer the reader to Quinlan's excellent [1989, 1990] descriptions.

4.2 Method

In our experiments, we followed the procedure described in [Quinlan, 1990b]. The instances of each relation were partitioned into input-output vectors that have the same relation name and same second argument. Only input­ output vectors with at least one positive instance were used. There are 24 instances (equivalently, tuples or ex­ amples) in each of the total of 104 input-output vectors.

The 104 input-output vectors were randomly parti­ tioned into training and testing sets . The size of the training set was varied among the values 4, 10, 20, and 40. Each of the test items was scored as correct only if all 24 examples within the vector were correctly classified.

We extended Quinlan's experiment by manipulating whether new variables were credited or penalized in the evaluation of literals. The same samples were used across conditions with the same sample size. Each condition was run 20 times. These results are summarized in Ta­ ble 1.

4.3 R esults and Observations

STRUCT performed significantly better than FOIL on this domain for conditions with the same sample size. Perhaps family relationships, being trees, are easily learned by a decision-tree algorithm.

For STRUCT, assigning a small credit to new variables resulted in decision trees of no better or worse accuracy. Quinlan's rationale for the credit strategy is that adding new variables will allow new literals to be introduced that might have more information gain. This locally increases the size of the hypothesis space. However, the larger hypothesis may also result in overfitting.

4.4 Chess Endgame

The chess endgame domain was used in a comparison of human and machine learning formalisms [M uggleton et a/. , 1989] Muggleton et a/. concluded that the ability to produce high-performance in this domain was almost entirely dependent on the ability to express first-order predicate relationships. Thus, this domain seems to be a natural test-bed for structural learning. Quinlan's (1990] results for FOIL on this domain are included in Table 2.

The problem faced by the learner in the chess endgame domain is to learn the concept of an Illegal position in­ volving three pieces- a white rook, white king, and black king. A position is Illegal if either king is in check or two pieces occupy the same square.

4.5 Experiment 1

In this experiment we compared three strategies against a default strategy for training sizes of 100 and 1000. The control condition assigned a penalty for new variables in literal tests, and used a symmetric evaluation function. The other conditions differed from the control condition in one aspect of their strategy. The reward condition assigned a small reward for new variables. The asym condition used an symmetric evaluation function simi­ lar to the one used in FOIL, except that it evaluated information about examples rather than tuples.

Each condition was run with 10,000 testing examples and repeated for 10 trials. The same samples were used across conditions with the same sample size, and the two-tailed correlated t-test was used to test significance.

4.6 Results and Observations

As shown in Table 2, STRUCT achieved comparable ac­ curacy to FOIL for both sample sizes; their mean accu­ racies are within one standard deviation of each other's. However, FOIL finds descriptions of greater simplicity than STRUCT.

The evaluation function results in Table 3 indicate that on the chess endgame domain, STRUCT perform­ s better with the symmetric evaluation function (the control condition) than with the asymmetric evalua­ tion function . The sym condition produced more accurate trees, particularly for larger sample sizes. Perhaps the symmetric evaluation function is appropriate for the symmetric decision tree algorithm, and the asymmetric evaluation function is apppropriate for the asymmetric separate-and-conquer algorithm.

On this domain, assigning a small credit to new vari­ ables was also significantly worse than assigning a small penalty to new variables. This result is not surprising as a complete and consistent description can be constructed without introducing any new variables.

Feature construction did not result in a significan­ t increase or decrease in accuracy in any condition, so these results are not included in Table 3. For this data, feature construction's only advantage is the greater conciseness of the decision tree. Our result­ s are consistent with the results in [Matheus, 1990; Pagallo and Haussler, 1990] which showed little or no im­ provement in accuracy for the· datasets obtained from the UCI Repository of Machine Learning Domains. Matheus conjectures that the poor results are due to the high quality of the initial features.

4. 7 Experiment 2

This experiment was motivated by the disparity in Pa­ gallo's [1990] results for feature construction on synthet­ ic domains and the UCI domains. We conjectured that feature construction might be more effective if the dis­ tribution was biased to generate more of the difficult examples.

Accordingly, we created an example generator that produced relatively more examples of illegal positions where the black king was in check by the rook. We also biased the example generator to generate many near­ misses of this case - situations where the black king would be in check by the rook if the white king were not in the way. To improve the efficiency of the da­ ta generator, we did not check for repeated positions in either the training or testing set. Each example was gen­ erated independently of every other example. The same distribution bias was used for the training and testing sets.

We ran the experiment for each of the two find-features strategies, and a control condition with no feature con­ struction. The FFJ condition used find-featurel, and the FF2 condition used find-feature2. Each feature construc­ tion strategy was run with 100 and 1000 training items, and 10,000 test items; the experiment was repeated 20 times. The same samples were used across condition­ s with the same sample size. In Table 4, the correlated two-tailed t-test was used to find significance. In the first and last groups of three rows, each feature construction strategy is compared to the control; in the middle group of two rows, FF2 is compared with FFJ.

4.8 Results and Observations

For the biased distribution, there were significant differ­ ences for accuracy with and without feature construc­ tion. Overall, FF2 performed best, followed by FFJ . Interestingly, the accuracy without feature construction is about the same as for the unbiased distribution.

FF1 learned with less accuracy than the control for 100 training items, but the difference is not significant. However, it did learn with significantly better accuracy for the larger sample size. FF2learned with significantly better accuracy than the control for both sample sizes, and significantly better accuracy than FF1 for the small­ er sample size.

These results suggest that feature construction is de­ pendent on the example distribution. On the other hand, it may be quite easy to bias the distribution- one can use the decision tree as a test of whether or not an example is difficult. Namely, examples that are incorrectly clas­ sified by a first-attempt decision tree might be used to construct a biased distribution for feature construction.

The difference between the two feature construction results seems to indicate that the context of the literal is important for feature construction when learning from smaller sample sizes.

5 Conclusions

STRUCT is a structural decision tree algorithm that pro­ vides good performance on the two test domains. On the kinship domain, it learns more accurate descriptions than FOIL. On the chess domain, it learns descriptions of comparable accuracy to FOIL. However, FOIL is con­ siderably faster than STRUCT. This can be important if there are many examples. In addition, FOIL generally finds simpler definitions than STRUCT.

Our experiments demonstrated that Quinlan's heuris­ tic of assigning a small credit to new variables does not work effectively in STRUCT for these datasets. Assign­ ing a small debit to new variables produced more ac­ curate decision trees. We conjecture that these results would be reversed for a separate-and-conquer strategy: Quinlan's evaluation function would consistently outper­ form our evaluation function because of the asymmetry of the algorithm.

The feature construction results indicate that the lack of effectiveness of feature construction on real-world do­ mains may be due to the distribution of the examples. In order to use feature construction effectively, it may be necessary to bias the distribution. Our results showed that a straightforward extension of FRINGE for struc­ tural decision trees produced significantly less accurate descriptions for smaller sample sizes than an alternate approach that compensated for loss of context informa­ tion.

Acknowledgements

Discussions with Pat Langley, Sudhakar Yerramareddy, and members of the Inductive Learning Group contribut­ ed to this paper. We would also like to thank Ross Quin­ lan for sending us FOIL.2.1.