A Scheme for Feature Construction and a Comparison of Empirical Methods

1 Introduction

Supervised concept learning is the problem of finding a description of an unknown class of objects for which we are given a set of training examples. The most common approaches to this problem can be collectively referred to as similarity-based learning (SBL), including agglomera­ tive learning systems and splitting algorithms [Breiman et al., 1984; Quinlan, 1983].

The effectiveness of most SBL algorithms is influenced by concept difficulty, variously measured as feature in­ teraction [Devijver and Kittler, 1982; Rendell and Seshu, 1990], concept dispersion [Rendell and Cho, 1990], cross entropy [Ragavan and Rendell, 1990], and term and lit­ eral complexity [Ehrenfeucht et al., 1988]. These studies

·The authors gratefully acknowledge the support of NSF grant IRI 8822031. Blix is supported by the Royal Norwegian Research Council for Science and Humanities and University of Illinois CS Fellowships.

+

+

Figure 1: Decision tree representation for z1z2 V zaz4.

show that SBL concept difficulty affects the accuracy and conciseness of machine learning systems.

Concepts used to test similarity-based learning sys­ tems are often not difficult, because their corresponding feature set is selected with the aid of human experience. However, for many interesting and important concepts the appropriate level of abstraction is not directly avail­ able. A shift of inductive bias through feature construc­ tion may help construct an instance space at a proper level of abstraction for conventional SBL system to work [Utgoff, 1986; Matheus, 1989]. This paper discusses a general approach to feature construction and compares specific approaches based on the FRINGE algorithm.

FRINGE [Pagallo and Haussler, 1990; Pagallo, 1989] is a feature construction algorithm for decision-tree learn­ ing designed to combat the replication problem. The replication problem is the duplication of a sequence of tests in different branches of a decision tree (Fig. 1 ), leading to an inconcise representation that also tends to have low predictive accuracy. Although replications are inherent to the decision tree representation rather than the concept itself, the replication problem is a manifes­ tation of underlying concept characteristics that is ac­ centuated for difficult concepts [Yang et al., 1991].

Section 2 presents a generalized algorithm schema based on FRINGE that utilizes the output of similarity­ based learning for feature construction. We present some specific approaches captured by this algorithm schema. Section 3 summarizes and interprets the results of ex­ periments with three feature construction algorithms. Finally, section 4 discusses inherent limitations and re­ search directions.

Concept learning algorithm CL

Let Prm be the set of primitive user-given attributes.

Input the Data expressed using Prm, each with its class-membership value.

Initialize active feature set Act ..,_ Prm.

Repeat until some stopping criterion is met:

1. convert Data from ground Prm to active form Act;
2. perform SBL( Act, Data, Tree)
3. (build a decision tree using splitting algorithm);
4. if required, call FC to construct new feature(s) New to add to Act;
5. if Act is large, prune to eliminate less useful features.

Figure 2: Concept learning with feature construction.

2 Feature Construction Based on SBL Output

FRINGE [Pagallo, 1989] and CITRE [Matheus, 1989] are two members of a class of concept learning algo­ rithms CL that incorporate feature construction. Given a set of primitive attributes and corresponding data annotated with class-membership values, CL learns a concept by iterating two basic steps: (1) attempt to learn the concept through some standard induction method, and (2) use the output to construct new fea­ tures and repeat the process. This algorithm schema also summarizes other approaches to feature construc­ tion (e.g., [Devijver and Kittler, 1982; Schlimmer, 1987; Seshu et al., 1989]).

Figure 2 shows more detail. Although step 2 could use any attribute-based induction algorithm, we confine this discussion to SBL methods that output decision trees (e.g., [Breiman et al., 1984; Quinlan, 1983]). To detect whether feature construction FC is appropriate, step 3 might base its decision on accuracy or the size of Tree [Matheus, 1989; Pagallo, 1990; Rendell and Seshu, 1990], but in our simplified approach, the loop's stopping crite­ rion is failure to produce new features. Step 4 is impor­ tant for difficult problems [Devijver and Kittler, 1982; Pagallo, 1990; Seshu et al., 1989], but is not part of the algorithms we test.

Henceforth, the acronym FC refers to feature con­ struction based on decision Tree output of SBL. Since feature construction is complex, appropriate bias is es­ sential. The following sections present increasingly in­ volved attempts to utilize the structure of Tree to pro­ duce useful new features.

2.1 First Attempts at Effective Constraint

One scheme for construction is to form exactly one fea­ ture for each positive branch in Tree. Each branch pro­ duces a conjunction, e.g., Figure 1 would give three con­ junctions, one of which is z 1 -,z2z 3z 4. This sort of con­ struction is not very useful.

A more interesting technique is to retain the branch oriented approach but to restrict the conjunction to a binary operation. This restriction effectively allows multiple conjunction, but only after further iteration of the SBL procedure. On a variety of problem domains, Matheus [1989] tried three choices of operands for binary

FRINGE( Tree) New= NIL for every Leaf at depth ~ 2 in 1\-ee if Leaf is a positive leaf then Feature = Conjoin( Leaf) New = New + Feature return( New)

Conjoin( Leaf) if Leaf is left child of Parent then if Parent is left child of Grandparent then return(·Parent & ·GrandParent) else return(·Parent & GrandParent) else if Parent is left child of Grandparent then return(Parent & ·GrandParent) else return(Parent & GrandParent) Disjoin( Leaf) if Leaf is left child of Parent then if Parent is left child of Grandparent then return(·Parent V GrandParent) else return( ·Parent V -..,GrandParent) else if Parent is left child of Grandparent then return(Parent V GrandParent) else return( Parent V -..,GrandParent)

conjunction: the two nodes at the root of a branch, the two at the fringe (the leaf and its predecessor [Pagallo, 1989]), and any two adjacent nodes. The best accuracy was usually attained using the Fringe method, although in some cases Adjacent had slightly better accuracy (but poorer efficiency).

2.2 FRINGE

Pagallo [1989; 1990] and Pagallo and Haussler [1990] re­ ported results using a different set of schemes, but again the best choice was FRINGE (Fig. 3). (Pagallo applies this name to her entire algorithm analogous to CL; we use FRINGE to denote the feature construction scheme only.) Construction proceeds by conjoining the parent and grandparent nodes of all positive fringes in the tree; the position of the leaf node relative to the parent and grandparent determines whether the parent and grand­ parent occur negated in the conjunction (Fig. 4).

FRINGE alleviates the replication problem. In her analysis, Pagallo [1990] noted that even a simple boolean concept such as C = z 1z 2 V z 3z 4 causes replication. For example if we traverse the decision tree for C in Figure 1, we find H = Z1Z2 V ·z1zaz4 V z1-,z2zaz4. Replication causes inconciseness and inaccuracy because H is divided into more disjunctive components than necessary, thus dispersing the training examples. In contrast, FRINGE

Sy:mFringe( Tree) New= NIL for every Leaf at depth ~ 2 in Tree Feature = Conjoin( Leaf) New = New + Feature return( New) Figure 5: SymFringe (Symmetric FRINGE). DCFringe( Tree) New= NIL for every Leaf at depth ~ 2 in 1\-ee if Leaf is a positive leaf then if (sibling of Leaf is a negative leaf) and else (parent's sibling of Leaf is a positive leaf) then Feature = Disjoin( Leaf) Feature = Conjoin( Leaf) New = New + Feature return( New)

prevents dispersion by constructing conjunctive features such as :~: 3 :~: 4 , which tend to be selected early in another round of SBL.

Pagallo [1990] demonstrated the value of FRINGE for several DNF expressions, most of which used 16 to 80 attributes with 6 to 16 terms oflength 3 to 7, and two of which had more terms. But she also noted limited suc­ cess on parity concepts, and anticipated problems with CNF-type concepts. CNF-type refers to concepts whose CNF representations are more compact than the corre­ sponding DNF-type concept expression.

2.3 Pagallo's Improvements to FRINGE

Pagallo [1989] proposed that the CNF problem can be attacked with a dual heuristic for negative leaves, us­ ing disjunction instead of conjunction. Later, Pagallo [1990] implemented an algorithm Symmetric FRINGE that combines the constructions of FRINGE and Dual FRINGE.

Figure 5 shows the symmetric version, whose name we abbreviate to SymFringe. Technically, SymFringe differs from Symmetric FRINGE in that SymFringe performs conjunction for both positive and negative leaves. How­ ever, the two versions produce the same features, modulo negation. Conjunction of positive leaves in SymFringe is identical .to the FRINGE component of Symmetric FRINGE; conjunction of negative leaves in SymFringe is equivalent to negation of disjunctions in the Dual FRINGE component. Pagallo [1990] showed that Dual FRINGE and Symmetric FRINGE give better accuracy on two difficult CNF-type concepts that have more than a thousand terms when expressed in DNF form.

2.4 An Improved Construction Method

Shown in Figure 6, DCFringe is like SymFringe except that DCFringe guides construction using more detailed properties of the tree output by SBL. Whereas Sym­ Fringe chooses disjunction or conjunction according to the sign of a single leaf node, DCFringe makes its choice based on additional information. To understand the dif­ ference between SymFringe and DCFringe, consider first a simpler relationship between DCFringe and the origi­ nal FRINGE.

Figure 7 depicts all possible patterns that can occur near the fringe of a binary decision tree. The crucial ob­ servation is that patterns reveal useful ways to combine features. Although both FRINGE and DCFringe use this observation, DCFringe considers more of the con­ text in which the pattern occurs before deciding which feature to construct. FRINGE performs the construction shown in Figure 7a regardless of the node types of the sibling and the parent's sibling. In contrast, DCFringe constructs a disjunctive feature when the sibling is a leaf and the parent's sibling is a positive leaf, i.e., for pat­ terns typical oftrees representing CNF-type concepts as depicted in Figure 7b. Otherwise DCFringe performs the same conjunction operation as FRINGE. The signs within the new conjunction or disjunction depend on whether the current node lies in the left (false) branch or the right (true) branch of its parent node, and also the relative position of the parent node to the grandparent node (Fig. 4).

Compared with DCFringe, SymFringe is less selective because it forms all conjunctions and disjunctions, re­ gardless of the tree structure. SymFringe produces more features, which can proliferate in multiple iterations.

2.5 Summary and Discussion of Methods

All our FC algorithms perform the binary operations of conjunction and/or disjunction, applying them to nodes in the decision tree output by SBL. The more interesting implementations are summarized in Table 1. Matheus' [1989] results demonstrate another interesting point. In addition to Root and Adjacent, he also tested heuris­ tics such as Root-Fringe, which is the combination of Root and Fringe. The features generated by these vari­ ations have the following relationships: Fringe, Root ~ Root-Fringe ~ Adjacent. Intuitively, Adjacent should be most accurate since it generates a superset of the other heuristics' features. However, Matheus' results are not consistent with this intuition. For most of the cases, Ad­ jacent is inferior to Fringe. Unnecessary features con­ fuse SBL evaluation and cause overfitting, which suggests that since DCFringe ~ SymFringe, DCFringe may work better than SymFringe. In Section 3 we present and analyze experiments on this and other relationships among FRINGE, SymFringe and DCFringe.

3 Experimental Results and Analysis

We compare the behavior of three feature construction algorithms, by varying size of training sample and type of concept. We also discuss the strengths and weaknesses of the approaches.

3.1 Experimental Design

The three systems, FRINGE, SymFringe, and DCFringe, were run on 160 randomly generated concepts over 10 attributes. More precisely, 10 concepts each were gener­ ated from 16 pre-determined classes, each class a four­ dimensional boolean choice. The boolean dimensions were DNF versus CNF, monotone versus non-monotone, p, versus non-p,, and 4/2 versus 2/4. 1 An expression is monotone if all its literals are positive. A concept is p,­ DNF (p,-CNF) if each attribute occurs in at most one term (clause) ofits DNF (CNF) expression [Ehrenfeucht et al., 1988].

For each of the 160 target concepts, N training ex­ amples and 200 testing examples were generated such that no two examples were the same. The values of N were determined empirically to be within the range where DCFringe is most effective [Yang, 1991]; this gave values of N = 30, 60, and 90. 2 The underlying SBL sys­ tem was PLS1, which performs much like ID3 [Rendell and Cho, 1990]. Although their splitting criteria differ, this factor has been shown to have a minor effect on the behavior of a decision tree learner [Breiman et al., 1984; Mingers, 1989; Rendell and Cho, 1990].

In the following three sections we present and discuss results from our experiments with the three feature con­ struction schemes. First we compare their overall per­ formance; the criteria are predictive accuracy, learning efficiency, and tree conciseness. Then we investigate the effect of training set size on accuracy improvement. Fi­ nally, we show how learning behavior depends on concept p,-ness, which leads to a discussion of the limitations of the FC algorithms studied.

1 We use the notation k/l to signify a DNF expression hav­ ing exactly k terms of exactly lliterals, or a CNF expression having k clauses of lliterals. Note that 2/4 11-CNF is equiv­ alent to non-11 16/2-DNF, and 4/2 11-CNF is equivalent to non-11 16/4-DNF.

2 In continuing experiments, the size ofthe training sample is being varied over a wider range.

3.2 General Utility of the Different Algorithms

Table 2 provides a comparison of the overall performance of each algorithm. Values are averaged over all160 runs for 90 training data. Each entry represents a 95% con­ fidence interval for the corresponding algorithm. The first row shows final predictive accuracy (separate test sample) after convergence (several rounds of SBL and FC). The second row gives the difference between this value and the basic SBL algorithm. The third row indi­ cates the tree conciseness as measured by the number of leaves in the final tree. The fourth and fifth rows in­ dicate learning efficiency as the number of new features and the number of iterations before convergence.

FRINGE generates conjunctive features only, and is incapable of learning CNF-type concepts [Yang, 1991]. Since half of the 160 target concepts are CNF-type, FRINGE cannot perform well on average. SymFringe and DCFringe generate appropriate disjunctive features in addition to conjunctive features. They both perform better than FRINGE. DCFringe is even more accurate than SymFringe (the t value for improvement in accu­ racy is 1.7, which implies a confidence level of 90%).

In terms of efficiency, DCFringe is better than Sym­ Fringe. DCFringe generates significantly fewer features than SymFringe and uses almost the same number of iterations. FRINGE sacrifices accuracy and conciseness to be faster than DCFringe.

In terms of conciseness, SymFringe and DCFringe are significantly better than FRINGE. DCFringe and Sym­ Fringe have the smallest final trees. A reduction in tree size not only facilitates human comprehensibility, but also provides better statistical support for splitting de­ cisions since the sample size within a node increases.

3.3 Accuracy Improvement vs. Sample Size

Table 3 shows how training set size influences accuracy for each algorithm. Here we consider the 80 p, concepts only. The results for FRINGE are retained mainly as a baseline for comparison. The t values listed in the last column compare DCFringe with SymFringe. The entries under the algorithm names show the 95% confidence in­ terval for predictive accuracy improvement beyond the basic SBL algorithm.

This table indicates that DCFringe significantly out­ performs SymFringe in terms of accuracy. DCFringe has consistently better accuracy across training set size. (The t value of 1.8 in the second row corresponds to a significance level of about 97%, and the consistent trend substantiates the claim further.)

The extra features generated by SymFringe confuse the feature selection mechanism in the underlying SBL system. This effect and possible overfit cause SymFringe to perform less well than might be expected.

3.4 Accuracy vs. Concept Difficulty

Figure 8 shows the accuracy improvement obtained by DCFringe and SymFringe, as a function of concept JJ.­ ness. DCFringe attains significantly better accuracy im-

provement than SymFringe for all training sets on J1. con­ cepts (Fig. 8a). But the tendencies are less clear for non-JJ. concepts (Fig. 8b). The superiority of DCFringe over SymFringe has vanished, and the relationship even seems to reverse, although not significantly.

Our conjecture to explain this phenomenon is that hard concepts have degrees of concept difficulty. From the perspective of the decision tree output of SBL, the replication problem is just one manifestation of diffi­ culty. When concepts are J1. DNF (Jl. CNF) the diffi­ culty is restricted in two ways. First, the number of literals in a J1. concept is limited to the dimensionality of the instance space, whereas concepts become more difficult for SBL roughly as the number of literals (at­ tribute occurrences) increases [Ehrenfeucht et al., 1988; Rendell and Seshu, 1990]. Second, our preliminary ex­ periments indicate that J1. concepts often have replica­ tions, whereas non-JJ. concepts exhibit less replication (although they have obscure patterns of attribute du­ plication). On non-JJ. concepts, DCFringe is not more Extended feature construction procedure FC/2.

3 Accuracies relative to SBL are shown as percentage point differences.

1. Using the SBL Tree, and possibly knowledge, create a set of pattern&;
2. Grouping these patterns by class-membership values and other constraints, form candidate pattern claue&.
3. Convert stronger pattern classes into new features to add to New.
4. Return New to CL.

Figure 9: Refined construction from a decision tree.

accurate than SymFringe because the features generated by DCFringe help replications only.

Moreover, all three FC methods we evaluated improve accuracy only marginally with non-JJ. concepts. This elu­ cidates the limitation of the basic FRINGE approach. The FC methods we tested are unlikely to generate use­ ful features if the decision tree does not exhibit replica­ tion.

4 Discussion and Future Work

Our experimental analysis has raised several issues. One is the general utility of FRINGE-like algorithms. ffthey primarily help J1. concepts, these algorithms have limited practical value. Of all possible boolean concepts, the proportion ofnon-JJ. concepts is large, and increases with the number of attributes. In hard practical problems, non-JJ. concepts (or their non-boolean analogues) often occur since low-level primitive attributes tend to par­ ticipate repeatedly in many high-level features. To un­ derstand more precisely when FRINGE-like algorithms work, we need to address the problem of characteriz­ ing concepts. Although concept characterization is it­ self problematic [Ragavan and Rendell, 1990], the basic intuition is that concepts become more difficult as the numbers of literals and terms increase [Ehrenfeucht et al., 1988], i.e., as feature interaction worsens [Rendell and Seshu, 1990].

Given a suitable measure of concept difficulty for SBL, and after using that measure to ascertain the limits of current feature construction, we anticipate several pos­ sible improvements to FC. For non-JJ. concepts, the 1ree regularities may be more complex than the replications enjoyed by DCFringe, requiring more subtle feature con­ struction. Figure 9 outlines FC/2, an extended version of FC, for boolean and non-boolean problems for which we may have some knowledge or hunches.

Analogous to the conjunctive construction of FC, Step 1 of FC/2 forms conjunctions as pattern&. One way to obtain patterns is to conjoin attributes that oc­ cur frequently in multiple branches of the tree: a candi­ date pattern is favored if its attributes appear in many branches. A second way to decide good patterns may be combined with the first: Given a pattern proposed by the branch popularity method, one or more conjuncts may be dropped from or added to that initial pattern for various reasons. One reason for dropping a conjunct is to respond to overfit. Another reason for dropping or adding specific conjuncts is to match available knowl­ edge or patterns from other branches, to make a more coherent set of patterns.

For hard problems with much feature interaction, cor­ rect patterns are difficult to determine because greedy SBL is limited even when aided by FRINGE-like algo­ rithms [Pagallo, 1990]. We need to study the tradeoffs between relaxation of SBL greediness [Breiman et al., 1984, chapter 5] and overall learning behavior.

Step 2 of FC/2forms pattern claues, which are poten­ tial disjunctions. A pattern class is a set of similar pat­ terns. Two patterns are similar if their class-membership values are alike, and if they share some syntactic or semantic commonality to improve their coherence (i.e., unifying principle [Smith and Medin, 1981]). In real­ world problems, pieces of knowledge are often avail­ able that can help form pattern classes [Matheus, 1990; Rendell and Seshu, 1990].

Especially when little knowledge is available for hard problems, FC/2 will encounter extreme problems involv­ ing large numbers of patterns and pattern classes. Since large numbers of features aggravate problems of over­ fit and evaluation, we need sensitive measures of feature utility [Ragavan and Rendell, 1990]. Step 3 of FC/2 should create new features only after they attain credi­ bility in terms of support from data, pattern coherence, and general and specific knowledge. We also need ef­ fective means to combine multiple measures of support [Gunsch, 1991].

Acknowledgments

Discussions with Tom Dietterich, Chris Matheus, Ed­ uardo Perez, Barish Ragavan, Raj Seshu, and Larry Watanabe contributed to this paper.