The Utility of Feature Construcuon for Back-Propagation

1 Introduction

Recent progress in artificial neural networks (ANNs) and their use in disparate domains have spurred the interests of researchers in studying various means of improving them. ANNs have shown promising results for a number of problem areas including content addressable mem?ry, pattern recognition and association, category formatwn, speech production and global optimization [Kohonen, 1984; Rumelhart et al., 1986; Anderson, 1977; Sejnowski and Rosenberg 1987; Hopfield and Tank, 1986]. They have also been 'tried with fairly good results in financial [Dutta and Shekhar, 1988] and in manufacturing applica­ tions [Rangwala and Dornfeld, 1989] among ot.her areas.

Back-propagation (BP) is one of the most Widely used neural network algorithms due to its powerful problem solving capabilities. There have been numerous studies by researchers who are interested in the dynamics of the BP algorithm, and the network (multi-layered percep­ trons) on which back-propagation is based. Although BP has varied advantages, such as being able to repre­ sent/learn any function (Hornik et al., 1989], an inherent problem with the algorithm is that it is very slow to con­ verge (learn). Researchers in the area have successfully implemented modifications to enable faster convergence of the neural networks using disparate means, ranging from modifications to the BP algorithm itself to appro­ priate implementations of the algorithm in VL~I com­ ponents. In this paper, we present a novel techruque for improving the learning process in a feed-forward neu­ ral network by pre-processing the input (training) data using an automated methodology.

"This research was supported in part by National Science Foundation grant no. IRI-88-22031. We would like to thank Christopher Matheus and Larry Rendell for providing us a copy of CITRE.

A difficult concept shows a high degree of dispersion in the input representation space due to the inability of the low-level measurement attributes to describe the concepts concisely and accurately. Given any feature set for data representation, the concept dispersion measure .6. [Ragavan and Rendell, 1991] estimates the difficulty of learning any concept using that feature set, and thus the quality of the feature set. We use feature construc­ tion (Pagallo, 1989; Matheus and Rendell, 1989; Drastal et al., 1989] to develop new features from the original set of attributes, to decrease the concept's dispersion in the constructed feature space. The constructed feature sets are then used as input to the BP algorithm. New fea­ tures are constructed using CITRE (Matheus, 1989] and used to improve the performance of the BP algorithm considerably.

2 Reducing Concept Dispersion by Feature Construction

Difficult concepts exhibit numerous "peaks" or regions in instance space (Rendell and Seshu, 1990] ifthe attributes used for describing data are inappropriate. These con­ cepts require changes in representation, for example through feature construction. Good feature constru~t~on can reduce the difficulty of such concepts, by proVIding a more compact representation for the training data.

For difficult concepts, each subset of the training data formed by conditioning on a value of any attribute would contain a large number of both positive and negative ex­ amples and consequently show high uncertainty about the co~cept class. Entropy 1 measures this uncertainty­ to measure concept difficulty, we estimate the net con­ ditional entropy in the training data, using all the attributes (assumed independent) on which the concept depends.

1 Entropy of a boolean concept y is defined as H(y) = - (p logl p + n log 2 n) where p an~ n .are the prior proba­ bilities of finding a positive or negative mstance of y.

We define dispersion .6. of a concept y as

where

N·ll number of effective attributes

(those relevant to the concept)

ith effective attribute

entropy of y conditioned on Zi.

The entropy of y conditional on Zi is defined as

over all values j of z; . .6. has a value between 0 and 1.0. In general, the more difficult the concept, the higher its dispersion. At the other extreme, if any single feature splits the positive and negative examples cleanly, such a feature alone is sufficient to determine the concept; no uncertainty would result when the instances are condi­ tioned on such a feature. .6. captures the difficulty of a concept for learning using any given feature set. It can therefore be used estimate feature set quality.

We use feature construction, specifically using CITRE [Matheus, 1989], to create new feature sets with lower .6. values. Using .6. as an indicator of feature quality, we show that .6. decreases in the successive feature spaces constructed by CITRE. More importantly, BP perfor­ mance increases as .6. decreases.

The FRINGE [Pagallo, 1989] module of CITRE con­ structs features iteratively from decision trees. It forms new features by conjoining two nodes at the fringe of the tree-the parent and grandparent nodes of positive leaves are conjoined to give a new feature. New fea­ tures are added to the set of original attributes and a new decision tree is constructed using the maximum in­ formation gain criterion [Quinlan, 1986]. This feature selection phase thus chooses from both the newly con­ structed features as well as the original attributes for re­ building the decision tree. The iterative process of tree­ building and feature construction continues until no new features are found. Splitting continues to purity, i.e., no pruning [Breiman et al., 1984] is used. The reader is re­ ferred to [Matheus, 1989] for a more detailed discussion on CITRE.

We use three different disjunctive boolean concepts to illustrate our experiments. The three functions are:

Yl = :iia:ii1zs + :il7Z4:iis + :iiazsz7

Ya = z1:iisz9 + :ii1:iiaz2 + zsz1z2

Y2 = :iiaz1zs + zsz4:ii1 + z9:iisz1

Three different data sets were generated for the functions Y1 1 Y2 and Ya, and used as input to the FRINGE feature construction module in CITRE. The newly constructed features and the trees that were generated for the first function (yl) are shown in Fig.l.

The .6. values of the feature sets selected by CITRE during the different tree generations are evaluated. Re­ sults for all three disjunctive concepts are shown in Fig.2.

Tree generation 1: att3 att4 att5 att6 att7 att8 . New Features: fi and(equal(att3,false),equal(att5,true)) f2 and(equal(att4,true),equal(att8,false)) f3 and(equal(att8,true),equal(att6,false)) Tree generation 2: f1 f2 f3 att7. New Features: f4 and(equal(att7,true),equal(f1,true)) f5 and(equal(f2,true),equal(att7,false)) f6 and(equal(f3,true),equal(f2,false)) Tree generation 3: f4 f5 f3 att7. New Features: f7 and(equal(att7,false),equal(f3,true)) f8 and(equal(f5,true),equal(f4,false)) Tree generation 4: f4 f5 f7. New Features: f9 and(equal(f7,true),equal(f5,false)) Tree generation 5: f4 f5 f7.

As can be seen from this figure, the .6. values drop signif­ icantly as new feature sets are used. We use the features from each tree as input to the BP algorithm. As we show in the next section, decreasing the concept's dispersion in the condensed feature sets in this manner speeds up the convergence of the BP algorithm greatly.

3 Learning with Back-Propagation

A number of previous studies [Dutta and Shekar, 1988; Fisher and McKusick, 1989; Mooney et al., 1989; Weiss and Kapouleas, 1989] have compared BP with other clas­ sification methods including statistical tree induction, with results favoring BP in terms of classification ac­ curacy. One of the major drawbacks of BP is that it is very slow. Several researchers [Fahlman, 1988; Becker and Le Cun, 1988] have worked on this problem trying to increase the convergence speed of the BP algorithm by disparate means. There are four primary means of increasing the convergence speed of BP: (1) by appro­ priately pre-processing the data used as input to the al­ gorithm, (2) by improving the BP algorithm itself, (3) by hard-wiring the algorithm using VLSI circuits, and (4) by utilizing the inherent parallelism in the BP algorithm through implementations in parallel machines.

Several researchers [Becker and Le Cun, 1988; Fahlman, 1988; Parker, 1987; Waltrous, 1987] have suc­ cessfully modified the BP algorithm using second-order gradient search methods resulting in improved perfor­ mance. Kung, Vlontos, and Hwang [1990] describe a VLSI architecture for implementing BP using a pro­ grammable systolic array. Hinton [1985] and Deprit [1989] describe the use of parallel processing comput­ ers to implement the BP algorithm with each unit in the network assigned to a processor.

In this study, no attempt is made to improve the BP algorithm itself as in previous studies. Instead, the data used as input to the BP algorithm is pre-processed (see [Piramuthu, 1990]). More specifically the .6. of the con­ cept is reduced in the attributes used as input to BP, to enable it to learn more effectively. As discussed in sec­ tion 2, feature construction can be used to reduce the A of concepts. Using feature construction, a subset of the initial and newly constructed attributes that are deemed to be better for representation are used as input to the BP algorithm. The new representation has fewer con­ cept regions per class. This makes the search space less complex, which in turn increases the convergence speed ofBP.

4 Using Good Feature Sets for BP

The criterion we use to categorize a newly generated fea­ ture set as "good" is that it should have small .6. values, relative to the initial feature set. Feature spaces with reduced .6. values have fewer concept regions, and are thus relatively easier for learning, i.e., for separating the examples belonging to different classes. The disjunctive concepts of Section 2 are used to study the effect of de­ crease in .6. on the convergence speed of BP.

As the initial weights in the network were set ran­ domly, we ran the BP algorithm 5 times for each set of features corresponding to the various trees constructed by CITRE. The average of 5 BP runs and their standard deviations are given in Table 1. The number of units in the network 2 is also shown in the table. The number of hidden units is roughly half the total number of input and output units for all the networks. The output layer always has 1 unit which classifies an example as either positive or negative.

In Table 1, the decision trees constructed by CITRE are indicated by tm,H for the tree constructed after the (n- 1)th iteration for the function Ym· The identical entries in Table 1 for the rows corresponding to the last two trees of each function (e.g., t25 and t26) are due to the identical final trees that CITRE produces on conver­ gence.

The decision attributes used in the final trees (tu, t26, ta6) are fewer than those in the initial set (9). This reduces the number of input units, in turn reducing the hidden units that are necessary. Thus the total num­ ber of units used in the network is reduced. Except for a few cases, the standard deviations for each of the re­ sulting values are low compared to their respective mean values. It can also be seen that the standard deviation values do not have any specific pattern with respect to the number of units used in the neural network.

We now take a closer look at the first two performance criteria listed in Table 1. The number of epochs and time taken to converge by BP for the three concepts as a function of constructed feature sets (tree generations) are shown in graphically in Figs.3 and 4 respectively.

As Fig.3 shows, the epochs required for convergence shows a slight initial increase in some cases, but then reduces considerably as better representations are constructed. The number of epochs taken by the final set of features (t15 , t2e, tae) to converge decreases to about half the value corresponding to the original attributes (tu, t21, tat), for all three examples.

2 a+b+c- a, b, and care the number of input, hidden, and output units respectively.

In Fig.4, the time taken for BP to converge, for all three examples, drops precipitously as the tree genera­ tion proceeds, before finally levelling off. The time taken for the BP algorithm to converge using the final set of attributes is less than an order of magnitude compared to using the initial attributes.

This trend of improved performance with decreasing concept difficulty is also clear from the reducing number of connection updates (CUs =#epochs x total number of units in the network) in Table 1. The reduction in convergence time is substantial due to significant drop in the number of connection . updates, as newer feature sets are generated. Because of serial processing, the time taken per epoch depends to a large extent on the total number of units that are used in the network. This would not be the case if parallel processors (e.g., Connection Machine) are used for the units.

Neural networks require fewer epochs to learn a con­ cept if its dispersion is decreased by using good features. By constructing new features, we reduce not only the number of effective attributes that are needed to define the concepts, but also increase the average information content at each of the constructed input units. This is achieved by considering the interaction effect! of the at­ tributes in disjunctive concept terms in addition to the main effect6 of the individual disjunctive terms, through feature construction.

5 Discussion

The Back Propagation algorithm is being successfully used in commercial applications, such as credit risk rat­ ing of companies. There have also been developments

70

Cll

.,......_ 60

~

Cll

<'.)

.§

..._,. 50

E-< 40

<'.)

u 5 30

00

....

<'.)

~

u

0 20

Cl. 10

~

0

-- ....

1

2

3

yl

----- y2

y3

...................

=n.:n.m.~.:n. :

4

5

6

Feature Set #

Figure 4: BP Convergence Time improvement.

in the area of creating expert systems using neural net­ works. In a commercial credit risk rating situation, for example, the learning speed of the BP algorithm is crit­ ical for the firm to be able to make quicker decisions for it to remain competitive. We have shown a means of getting closer to the goal of achieving faster learning using a feed-forward neural network by automating the input feature selection process. Feature construction can be used to automatically generate better feature sets, as measured by their a values, which are used as in­ put to the BP algorithm. The proposed methodology also eliminates the least important attributes from the training data, thus facilitating efficient use of computing resources by directing attention to only those attributes important for a given classification problem.

Advantanges of neural networks such as good perfor­ mance in high feature interaction domains [Indhurkya and Weiss, 1990) are combined with advantages of decision-tree based induction by this method. Incor­ porating a front-end like CITRE to the BP algorithm also provides a facile technique for introducing domain knowledge in neural nets. Knowledge gets compiled into the constructed features.

It should also be noted that the classification ac­ curacy was a full 100 percent for feature sets corre­ sponding to each of the trees (tu, t12, t1a, t14, t15, t21, t22, ha, t24 1 t25, t2e, tat, ta2, taa, ta4, ta5, tae), in spite of the reduction in the number of attributes used as input after feature construction. By using a set of attributes with reduced a, along with other means of increasing the convergence speed such as second-order gradient methods, the convergence speed of the BP algo­ rithm can be significantly improved. Performance with noisy data remains to be investigated.