Feature selection with neural networks.
We present a neural network based approach for identifying salient features for classification in feedforward neural networks. Our approach involves neural network training with an augmented cross-entropy error function. The augmented error function forces the neural network to keep low derivatives of the transfer functions of neurons when learning a classification task. Such an approach reduces output sensitivity to the input changes. Feature selection is based on the reaction of the cross-validation data set classification error due to the removal of the individual features. We demonstrate the usefulness of the proposed approach on one artificial and three real-world classification problems. We compared the approach with five other feature selection methods, each of which banks on a different concept. The algorithm developed outperformed the other methods by achieving higher classification accuracy on all the problems tested.
Introduction
Learning systems primary source of information is data. For numerical systems
like Neural Networks (NNs), data are usually represented as vectors in a
subspace of R k whose components - or features - may correspond for example to
measurements performed on a physical system or to information gathered from
the observation of a phenomenon. Usually all features are not equally
informative: some of them may be noisy, meaningless, correlated or irrelevant for
the task. Feature selection aims at selecting a subset of the features which is
relevant for a given problem. It is most often an important issue: the amount of
data to gather or process may be reduced, training may be easier, better estimates
will be obtained when using relevant features in the case of small data sets, more
sophisticated processing methods may be used on smaller dimensional spaces
than on the original measure space, performances may increase when non
relevant information do not interfere, etc.
Feature selection has been the subject of intensive researches in statistics and in
application domains like pattern recognition, process identification, time series
modelling or econometrics. It has recently began to be investigated in the machine
learning community which has developed its own methods. Whatever the domain
is, feature selection remains a difficult problem. Most of the time this is a non
monotonous problem, i.e. the best subset of p variables does not always contain
the best subset of q variables (q < p). Also, the best subset of variables depends
on the model which will be further used to process the data - usually, the two
steps are treated sequentially. Most methods for variable selection rely on
heuristics which perform a limited exploration on the whole set of variable
combinations.
In the field of NNs, feature selection has been studied for the last ten years and
classical as well as original methods have been employed. We discuss here the
problem of feature selection specifically for NNs and review original methods
which have been developed in this field. We will certainly not be exhaustive since
the literature in the domain is already important, but the main ideas which have
been proposed are described.
We describe in sections 2 and 3 the basic ingredients of feature selection methods
and the notations. We then briefly present, in section 4, statistical methods used
in regression and classification. They will be used as baseline techniques. We
describe, in section 5, families of methods which have been developed
specifically for neural networks and may be easily implemented either for
regression or classification tasks. Representative methods are then compared on
different test problems in section 6.
. Basic ingredients of feature selection methods.
A feature selection technique typically requires the following ingredients:
. a feature evaluation criterion to compare variable subsets, it will be
used to select one of these subsets,
. a search procedure, to explore a (sub)space of possible variable
combinations,
. a stop criterion or a model selection strategy.
2.1.1 Feature evaluation
Depending on the task (e.g. prediction or classification) and on the model (linear,
logistic, neural networks.), several evaluation criteria, based either on statistical
grounds or heuristics, have been proposed for measuring the importance of a
variable subset. For classification, classical criteria use probabilistic distances or
entropy measures, often replaced in practice by simple interclass distance
measures. For regression, classical candidates are prediction error measures. A
survey of classical statistical methods may be found in (Thomson 1978) for
regression and (McLachlan 1992) for classification.
Some methods rely only on the data for computing relevant variables and do not
take into consideration the model which will then be used for processing these
data after the selection step. They may rely on hypothesis about the data
distribution (parametric methods) or not (non parametric methods). Other
methods take into account simultaneously the model and the data - this is usually
the case for NN variable selection.
2.1.2 Search
In general, since evaluation criteria are non monotonous, comparison of feature
subsets amounts to a combinatorial problem (there are 2 k -1 possible subsets for
k variables), which rapidly becomes computationally unfeasible, even for
moderate input size. Branch and Bound exploration (Narendra and Fukunaga
1977) allows to reduce the search for monotonous criteria, however the
complexity of these procedures is still prohibitive in most cases. Due to these
limitations, most algorithms are based upon heuristic performance measures for
the evaluation and sub-optimal search. Most sub-optimal search methods follow
one of the following sequential search techniques (see e.g. Kittler,
. start with an empty set of variables and add variables to the already
selected variable set (forward methods)
. start with the full set of variables and eliminate variables from the
selected variable set (backward methods)
. start with an empty set and alternate forward and backward steps
(stepwise methods). The Plus l - Take away r algorithm is a
generalisation of the basic stepwise method which alternates l
forward selections and r backward deletions.
2.1.3 Subset selection - Stopping criterion
Let be given a feature subset evaluation criterion and a search procedure. Several
methods examine all the subsets provided by the search (e.g. 2 k -1 for an
exhaustive search or k for a simple backward search) and select the most relevant
according to the evaluation criterion.
When the empirical distribution of the evaluation measure or of related statistics is
known, tests may be performed for the (ir)relevance hypothesis of an input
variable. Classical sequential selection procedures use a stop criterion: they
examine the variables sequentially and stop as soon as a variable is found
irrelevant according to a statistical test. For classical parametric methods,
distribution characteristics (e.g. estimates of the evaluation measure variance) are
easily derived (see sections 4.1 and 4.2). For non parametric or flexible methods
like NNs, these distributions are more difficult to obtain. Confidence intervals
which would allow to perform significance testing might be computed via monte
carlo simulations or bootstrapping. This is extremely prohibitive and of no
practical use except for very particular cases (e.g. Baxt and White 1996).
Hypothesis testing is thus seldom used with these models. Many authors use
instead heuristic stop criteria.
A better methodology, whose complexity is still reasonable in most applications,
is to compute for the successive variable subsets provided by the search
algorithm an estimate of the generalization error (or prediction risk) obtained with
this subset. The selected variables will be those giving the best performances.
The generalization error estimate may be computed using a validation set or
cross-validation or algebraic methods although the latter are not easy to obtain
with non linear models. Note that this strategy involves retraining a NN for each
subset.
3 . Notations
We will denote ( , )
k g the realization of a random variable pair (X,Y)
with probability distribution P. x i will be the i th component of x and x l the l th
pattern in a given data set D of cardinality N. In the following, we will restrict
ourselves to one hidden layer NNs, the number of input and output units will be
denoted respectively by k and g. The transfer function of the network will be
denoted f. Training will be performed here according to a Mean Squared Error
criterion (MSE) although this is not restrictive. We will consider, in the
selection methods for classification and regression tasks.
4 . Model independent Feature Selection
We introduce below some methods which perform the selection and the
classification or regression steps sequentially, i.e. which do not take into account
the classification or regression model during selection. These methods are not
NN oriented and are used here for the experimental comparison with NN specific
selection techniques (section 6). The first two are basic statistical techniques
aimed respectively at regression and classification. These methods are not well
fitted for NNs since the hypothesis they rely on do not correspond to situations
where NNs might be useful. However since most NN specific methods are
heuristics they should be used for a baseline comparison. The third one has been
developed more recently and is a general selection technique which is data
hypothesis free and might be used for any system either for regression or
classification. It is based on a probabilistic dependence measure between two sets
of variables.
4.1 Feature selection for linear regression
We will consider only linear regression, but the approach described below may
be trivially extended for multiple regression. Let x 1 , x 2 , . x k and y be real
variables which will be supposed centered. Let us denote:
the current approximation of y with p selected variables (the x i are renumbered so
that the p first selected variables correspond to numbers 1 to p). The residuals
x are assumed identically and independently distributed.
Let us denote:
l
l =1
For forward selection, the choice of the p th variable is usually based on R p 2 , the
partial correlation coefficient (table 1) between y and regressor f (p) , or on an
adjusted coefficient 1 . This coefficient represents the proportion of y total variance
explained by the regressor f (p) . The p th variable to select is the one for which
f (p) maximizes this coefficient. The importance of a new variable is usually
measured via a Fisher test (Thompson, 1978) which compares the models with
p-1 and p variables (Fs(p) forward in table 1). Selection is stopped if
1 The adjusted coefficient R
is often used instead of R p
.
Fs(p) forward < F(1,N-p,a) the Fisher statistics with (1,N-p) degrees of
freedom for a confidence level of a.
Choice Stop
(y l ) 2N
Backward SSR
l =1

Table

1: Choice and Stop criteria used with statistical forward and backward
methods.
Note that F S could also be used in place of R p 2 as a choice criterion:
forward
When p-1 variables have already been selected, R p-1 2 has a constant value in
[0,1] and maximizing F s is similar to maximizing R p 2 . Equation (4.1.3) selects
variables in the same order as R p 2 does.
For backward elimination the variable eliminated from the remaining p is the less
significant in terms of the Fisher test i.e. it is the one with the smallest value of
SSR p-1 or equivalently of Fs(p) backward (table 1). Selection is stopped if
backward > F(1,N-p,a).
4.2 Feature Selection For Classification
For classification, we shall select the variable subset which allows the best
separation of the data. Variable selection is usually performed by considering a
class separation criterion for the choice criterion and an associated F-test as
stopping criterion. As for regression, forward, backward or stepwise methods
may be used.
Data separation is usually computed through an inter-class distance measure
(Kittler, 1986). The most frequent discriminating measure is the Wilks lambda
(Wilks, 1963) L sV p defined as follows:
where W is the intra-class matrix dispersion corresponding to the selected
variable set SV p , B the corresponding inter-class matrix 2 and |M| the determinant
of matrix M. The determinant of a covariance matrix being a measure of the
volume occupied by the data, |W| measures the mean volume of the different
classes and |W+B| the volume of the whole data set. These quantities are
computed for the selected variables so that a good discriminating power
corresponds to a small value of L sv p : the different classes are represented by
compact clusters and are well separated. This criterion is well suited in the case of
multinormal distributions with equal covariance for each class, it is meaningless
for e.g. multimodal distributions. This is clearly a very restrictive hypothesis.
With this measurement the statistic F s , defined below, has a F(g-1,N-g-p+1,a)
distribution (McLachlan 1992):
We can then use the Wilks lambda both for estimating the discriminating power
of a variable and for stopping the selection in forward, backward (Habbema and
Hermans, 1977) or stepwise methods.
For the comparisons in section 6, we used Stepdisc, a stepwise method based on
(4.2.2) with a 95% confidence level.
4.3 Mutual Information
When data are considered as realization of a random process, probabilistic
information measures may be used in order to compute the relevance of a set of
these two quantities are defined as :
x l -class j
with g the number of classes, n j the number of samples in class j, - j the mean of
class j and - the global mean.
variables with respect to other variables. Mutual information is such a measure
which is defined as:
a,b
where a and b are two variables with probability density P(a) and P(b).
Mutual information is independent from any inversible and differentiable
transformation of the variables. It measures the "uncertainty reduction" on b
when a is known. It is also known as the Kullbak-Leibler distance between the
joint distribution P(a,b) and the marginal distribution product P(a)*P(b).
The method described below does not make use of restrictive assumptions on the
data and is therefore more general and attractive than the ones described in
sections 4.1 and 4.2, especially when these hypothesis do not correspond to the
data processing model, which is usually the case for NNs. It may be used either
for regression or discrimination. On the other hand such non parametric methods
are computationally intensive. The main practical difficulty here is the estimation
of the joint density P(a,b) and of the marginal densities P(a) and P(b). Non
parametric density estimation methods are costly in high dimensions and
necessitate a large amount of data.
The algorithm presented below uses the Shannon entropy (denoted H(.)) to
compute the mutual information It is possible to
use other entropy measures like quadratic or cubic entropies (Kittler, 1986).
Battiti (1994) proposed to use mutual information with a forward selection
algorithm called MIFS (Mutual Information based Feature Selection). P(a,b) is
estimated by Fraser algorithm (Fraser and Swinney, 1986), which recursively
partitions the space using c 2 tests on the data distribution. This algorithm can
only compute the mutual information between two variables. In order to compute
the mutual information between x p and the selected variable set SV p-1 does
not belong to SV p-1 ), Battiti uses simplifying assumptions. Moreover, the
number of variables to select is fixed before the selection. This algorithms uses
forward search and variable x p is the one which maximises the value :
where SV p-1 is the set of p - 1 already selected variables.
Bonnlander and Weigend (1994) use Epanechnikov kernels for density
estimation (H-rdle, 1990) and a Branch&Bound (B&B) algorithm for the search
(Narendra and Fukunaga, 1977). B&B warrants an optimal search if the criterion
used is monotonous and it is less computationally intensive than exhaustive
search. For the search algorithm, one can also consider the suboptimal floating
search techniques proposed by Pudil et al. (1994) which offer a good
compromise between the sequential methods simplicity and the relative
computational cost of the Branch&Bound algorithm.
For the comparisons in section 6, we have used Epanechnikov kernels for
density estimation in (4.3.2), a forward search, and the selection is stopped
when the MI increase falls below a fixed threshold (0.99).
5 . Model dependent feature selection for Neural Networks
Model dependent feature selection attempts to perform simultaneously the
selection and the processing of the data: the feature selection process is part of the
training process and features are sought for optimizing a model selection
criterion. This "global optimization" looks more attractive than model-independent
selection where the adequacy of the two steps is up to the user.
However, since the value of the choice criterion depends on the model
parameters, it might be necessary to train the NN with different sets of variables:
some selection procedures alternate between variable selection and retraining of
the model parameters. This forbids the use of sophisticated search strategies
which would be computationally prohibitive.
Some specificities of NNs should also be taken into consideration when deriving
feature selection algorithms:
. NNs are usually non linear models. Since many parametric model-independent
techniques are based on the hypothesis that input-output variables
dependency is linear or that input variables redundancy is well measured by linear
correlation between these variables, such methods are clearly ill fitted for NNs.
. The search space has usually many local minima, and relevance
measures will depend on the minimum the NN will have converged to. These
measures should be averaged over several runs. For most applications this is
prohibitive and has not been considered here.
. Except for (White 1989) who derives results on the weight distribution
there is no work in the NN community which might be used for hypothesis
testing.
For NN feature selection algorithms, choice criteria are mainly based on heuristic
individual feature evaluation functions. Several of them have been proposed in
the literature, we have made an attempt to classify them according to their
similarity. We will distinguish between:
. zero order methods which use only the network parameter values.
. first order methods which use the first derivatives of network parameters.
. second order methods which use second derivatives of network
parameters.
Most feature evaluation criteria only allow to rank variables at a given time, the
value of the criterion by itself being non informative. However, we will see that
most of these methods work reasonably well.
Feature selection methods with neural networks use mostly backward search
although some forward methods have also been proposed (Moody 1994, Goutte
1997). Several methods use individual evaluation of the features for ranking them
and do not take into consideration their dependencies or their correlations. This
may be problematic for selecting minimal relevant sets of variables. Using the
correlation as a simple dependence measure is not enough since NNs capture non
linear relationships between variables, on the other hand, measuring non linear
dependencies is not trivial. While some authors simply ignore this problem,
others propose to select only one variable at a time and to retrain the network with
the new selected set before evaluating the relevance of remaining variables. This
allows to take into account some of the dependencies the network has discovered
among the variables.
More critical is the difficulty for defining a sound stop criterion or model choice.
Many methods use very crude techniques for stopping the selection, e.g. a
threshold on the choice criterion value, some rank the different subsets using an
estimation of the generalization error. The latter is the expected error performed
on future data and is defined as:
where in our case, r(x,y) is the euclidean error between desired and computed
outputs. Estimates can be computed using a validation set, cross-validation or
algebraic approximations of this risk like the Final Prediction
1970). Several estimates have been proposed in the statistical (Gustafson and
Hajlmarsson 1995) and NN (Moody 1991, Larsen and Hansen 1994) literature.
For the comparison in section 6, we have used a simple threshold when the
authors gave no indication for the stop criterion and a validation set
approximation of the risk otherwise.
5.1 Zero Order Methods
For linear regression models, the partial correlation coefficient can be expressed
as a simple function of the weights. Although this is not sound for non linear
models, there have been some attempts for using the input weight values in the
computation of variable relevance. This has been observed to be an inefficient
heuristic: weights cannot be easily interpreted in these models.
A more sophisticated heuristic has been proposed by Yacoub and Bennani
(1997), it exploits both the weight value and the network structure of a multilayer
perceptron. They derived the following criterion:
I
O
where I, H, O denote respectively the input, hidden and output layer.
For a better understanding of this measure, let us suppose that each hidden and
output unit incoming weight vector has a unitary L 1 norm, the above equation
can be written as:
In (5.1.2), the inner term is the product of the weights from input i to hidden unit
j and from j to output o. The importance of variable i for output o is the sum of
the absolute values of these products over all the paths -in the NN- from unit i to
unit o. The importance of variable i is then defined as the sum of these values
over all the outputs. Denominators in (5.1.1) operate as normalizing factors, this
is important when using squashing functions, since these functions limit the
effect of weight magnitude. Note that this measure will depend on the magnitude
of the input, the different variables should then be in a similar range. The two
weight layers do have different role in a MLP which is not reflected in (5.1.1),
for example, if the outputs are linear, the normalization should be suppressed in
the inner summation of (5.1.1).
They used a backward search and the NN is retrained after each variable deletion,
the stop criterion is based on the evolution of the performances on a validation
set, elimination is stopped as soon as performances decrease.
5.2 First Order Methods
Several methods propose to evaluate the relevance of a variable by the derivative
of the error or of the output with respect to this variable. These evaluation criteria
are easy to compute, most of them lead to very similar results. These derivatives
measure the local change in the outputs wrt a given input, the other inputs being
fixed. Since these derivatives are not constant like in linear models, they must be
averaged over the training set. For these measures to be fully meaningful, inputs
should be independent and since these measures average local sensitivity values,
the training set should be representative of the input space.
5.2.1 Saliency Based Pruning (SBP)
This backward method (Moody and Utans 1992) uses as evaluation criterion the
variation of the learning error when a variable x i is replaced by its empirical mean
here since variables are assumed centered):
where MSE x
l
l
l l
l
This is a direct measure of the usefulness of the variable for computing the
output. For large values of N, computing S i is costly, and a linear approximation
may be used:
f y
x
l l
l
l
l
x
Variables are eliminated in the increasing order of S i .
For each feature set, a NN is trained and an estimate of the generalization error - a
generalization of the Final Prediction Error criterion - is computed. The model
with minimum generalization error is selected.
Changes in MSE is not ambiguous only when inputs are not correlated. Variable
relevance being computed once here, this method does not take into account
possible correlations between variables. Relevance could be computed from the
successive NNs in the sequence at a computational extra-cost (O(k 2
computations instead of O(k) in the present method).
5.2.2 Methods using computation of output derivatives
For a linear model the output derivative wrt any input is a constant, which is not
the case for non linear NNs. Several authors have proposed to measure the
sensitivity of the network transfer function with respect to input x i by computing
the mean value of outputs derivative with respect to x i over the whole training set.
In the case of multilayer perceptrons, this derivative can be computed
progressively during learning (Hashem, 1992). Since these derivatives may take
both positive and negative values, they may compensate and produce an average
near zero. Most measures use average squared or absolute derivatives. Tenth of
measures based on derivatives have been proposed, and many others could be
defined, we thus give below only a representative sample of these measures.
The sum of the derivative absolute values has been used e.g. in Ruck et al.
l =1
For classification Priddy et al. (1993) remark that since the error for decision j
x may be estimated by 1 - f j (x) , (5.2.3) may be interpreted as the
absolute value of the error probability derivative averaged over all decisions
(outputs) and data.
Squared derivatives may be used instead of the absolute values, Refenes et al.
(1996) for example proposed for regression a normalized sum:
x
f y
f
x
l
l
x
x
where var holds for variance. They also proposed a series of related criteria,
among
- a normalized standard deviation of the derivatives:
f
x
f
x
f
x
l
l
l
l
x
- a weighted average of the derivatives absolute values where the weights
reflect the relative magnitude of x and f(x):
f
x
x
f
l i
l
l
x
x
All these measures being very sensitive to the input space representativeness of
the sample set, several authors have proposed to use a subset of the sample in
order to increase the significance of their relevance measure.
In order to obtain robust methods, "non-pathological" training examples should
be discarded. For regression and radial basis function networks, Dorizzi et al.
(1996) propose to use the 95% percentile of the derivative absolute value:
-f
Aberrant points being eliminated, this contributes to the robustness of the
measure. Note that the same idea could be used with other relevance measures
proposed in this paper.
Following the same line, Czernichow (1996) proposed a heuristic criterion for
regression, estimated on a set of non pathological examples whose cardinality is
N'. The proposed choice criterion is:
-f
-l
-f
-l
For classification, Rossi (1996), following a proposition made by Priddy et al.
(1993), considers only the patterns which are near the class frontiers. He
proposes the following relevance measure:
f
x
f
x
l
frontier
l
x
x
x
The frontier is defined as the set of point for which - ( ) >
x
l
f x e where e is a
fixed threshold. Several authors have also considered relative contribution of
partial derivatives to the gradient as in (5.2.9).
All these methods use a simple backward search.
For the stopping criteria, all these authors use heuristic rules, except for Refenes
et al. (1996) who define statistical tests for their relevance measures. For non
linear NNs, this necessitates an estimation of the relevance measure distribution,
which is very costly and in our opinion usually prohibits this approach, even if it
looks attractive.
5.2.3 Links between these methods
All these methods use simple relevance measures which depend upon the gradient
of network outputs with respect to input variables. It is difficult to rank the
different criteria, all that can be said is that it is wise to use some reasonable rules
like discarding aberrant points for robustness, or retraining the NN after
discarding each variable and computing new relevance measures for each NN in
the sequence, in order to take into account dependencies between variables. In
practice, all these methods give very similar results as will be shown in section 6.
We summarize below in table 2 the main characteristics of relevance measures for
the different methods.
Derivative
used
Task
C/R
Data
used
(Moody (5.2.1)) -f
C/R All
(Refenes (5.2.5)) -f
C/R All
(Dorizzi (5.2.7)) -f
C/R Non pathological
data
(Refenes (5.2.6)) -f
C/R All
(Czernichow (5.2.8)) -f
-C/R Non pathological
data
(Refenes (5.2.4)) -f
(Ruck
(Rossi
C Frontier between
classes

Table

2. Computation of the relevance of a variable by different methods using
the derivative of the network function. C /R denote respectively Classification
and Regression tasks.
5.3 Second Order Methods
Several methods propose to evaluate the relevance of a variable by computing
weight pruning criteria for the set of weights of each input node. We present
below three methods. The first one is a Bayesian approach for computing the
weight variance. The other two use the hessian of the cost function for
computing the cost function dependence upon input unit weights.
5.3.1 Automatic Relevance Determination (ARD)
This method was proposed by MacKay (1994) in the framework of Bayesian
learning. In this approach, weight are considered as random variables and
regularization terms taking into account each input are included into the cost
function. Assuming that the prior probability distribution of the group of weights
for the i th input is gaussian, the input posterior variance s i 2 is estimated (with
the help of the hessian matrix).
ARD has been successful for time serie prediction, learning with regularization
terms improved the prediction performances. However ARD has not really been
used as a feature selection method since variables were not pruned during
training.
5.3.2 Optimal Cell Damage
Several neural selection methods have been inspired by weight pruning
techniques. For the latter, the decision of pruning a weight is made according to a
relevance criterion often named the weight saliency, the weight being pruned if
its saliency is low. Similarly, the saliency for an input cell is usually defined as
the sum of its weights saliencies.
where fan-out(i) is the set of weights of input i.
Optimal Cell Damage (OCD) has been proposed by Cibas et al. (1994a, 1996)
similar method has also been proposed by Mao et al., 1994). This feature
selection method is inspired from the Optimal Brain Damage (OBD) weight
pruning technique developed by LeCun (1990). In OBD, the connection saliency
is defined by :
which is an order two Taylor expansion of MSE variation around a local
minimum. The Hessian matrix H can be easily computed using gradient descent
but this may be computationally intensive for large networks. For OBD, the
authors use a diagonal approximation for the hessian which can then be computed
in O(N). The saliency of an input variable is defined accordingly as:
Cibas et al. (1994) proposed to use (5.3.5) as a choice criterion for eliminating
variables. The NN is trained so as to reach a local minimum, variables whose
saliency is below a given threshold are eliminated. The threshold value is fixed
by cross validation. This process is then repeated until no variable is found below
the threshold.
This method has been tested on several problems and gave satisfying results.
Once again, the difficulty lies in selecting an adequate threshold. Furthermore,
since several variables can be eliminated simultaneously whereas only individual
variable pertinence measures are used, significant sets of dependent variables
may be eliminated.
For stopping, the generalization performances of the NN sequence are estimated
via a validation set and the variable set corresponding to the NN with the best
performances is chosen.
The hessian diagonal approximation has been questioned by several authors,
Hassibi and Stork (1993), for example, proposed a weight pruning algorithm,
Optimal Brain Surgeon (OBS) which is similar to OBD, but uses the whole
hessian for computing weight saliencies. Stahlberger and Riedmiller (1997)
proposed a feature selection method similar to OCD except that it takes into
account non diagonal terms in the hessian.
For all these methods, saliency is computed using for performance measure the
error variation on the training set. Weight estimation and model selection both use
the same data set, which is not optimal. Pedersen et al. (1996) propose two
weight pruning methods gOBD and gOBS that compute weight saliency
according to an estimate of the generalization error: the Final Prediction Error
(Akaike 1970). Similarly to OBD and OBS, these methods could be also
transformed into feature selection methods.
5.3.3 Early Cell Damage (ECD)
Using a second order Taylor expansion, as in the OBD family of methods, is
justified only when a local minimum is reached and the cost is locally quadratic in
this minimum. Both hypothesis are barely met in practice. Tresp et al. (1997)
propose two weight pruning techniques from the same family, coined EBD
(Early Brain Damage) and EBS (Early Brain Surgeon). They use a heuristic
justification to take into account early stopping by adding a new term in the
saliency computation.
These methods can be extended for feature ranking, we will call ECD (Early Cell
Damage) the EBD extension. For ECD, the saliency of input i is defined as:
The algorithm we propose is slightly different from OCD: only one variable is
eliminated at a time, and the NN is retrained after each deletion.
For choosing the "best" set of variables, we have used a variation of the
"selection according to an estimate of the generalization error" method. This
estimate is computed using a validation set. Since the performances may oscillate
and be not significantly different, several subsets may have the same
performances (see e.g. figure 1). Using a Fisher test we compare any model
performances with those of the best model, we then select the set of networks
whose performances are similar to the best ones and choose among these
networks the one with the smallest number of input variables.
6 . Experimental comparison
We now present comparative performances of different feature selection
methods. Comparing these methods is a difficult task: there is not a unique
measure which characterizes the importance of each input, the selection accuracy
also depends on the search technique and on the variable subset choice criterion.
In the case of NNs, these different steps rely on heuristics which could be
exchanged from one method to the other. The NNs used are multilayer
perceptrons with one hidden layer of 10 neurons.
The comparison we provide here is not intended for a definite ranking of the
different methods but for illustrating the general behavior of some of the methods
which have been described before. We have used two synthetic classification
problems which illustrate different difficulties of variable selection. In the first
one the frontiers are "nearly" linear and there are dependent variables as well as
pure noise variables. The second problem has non linear frontiers and variables
can be chosen independent or correlated.
The first problem has been originally proposed by Breiman et al. (1984). It is a
three class waveforms classification problem with 19 noisy dependent features.
We have also used a variation of this problem where 21 pure noise variables are
added to the 19 initial variables (there are 40 inputs for this variant). The training
set has 300 patterns and the test set 4300. A description of this problem is
provided in the appendix. The performances of the optimal Bayes classifier
estimated on this test set are 86% correct classification. A performance
comparison appears in tables 3 and 4 for these two instances.
Method p * Selected Variables Perf .
Stepdisc (4.2.2) 14 000110111111111011100 0000000000000000000
(Bonnlander (4.3.2)) 12 000011101111111110000 0000000000000000000
(Moody
(Ruck (5.2.3))
(Dorizzi (5.2.7))
(Czernichow (5.2.8)) 17 010111111111111111100 0000000000000000000
(Cibas (5.3.5)) 9 000001111110111000000 0000000000000000000
82.26 %
(Leray (5.3.6)) 11 000001111111111100000 0000000000000000000

Table

3. Performance comparison of different variable selection on the noisy
wave problem.
For the noisy problem, all methods do eliminate pure noise variables. Except for
the two methods at the bottom of table 3 which give slightly lower performances
and select fewer variables , all give similar values around 85% correct. Stepdisc
also gives good performances since in this problem data have a unimodal
distribution and the frontiers are nearly linear. For the non noisy problem,
performances and methods ordering change. The two techniques at the bottom of
table 4 give now slightly better performances.
Method p * Selected Variables Perf .
None 21 111111111111111111111
Stepdisc (4.2.2) 14 001110101111111011100
(Bonnlander (4.3.2)) 8 000001100111101010000
(Moody (5.2.1))
(Ruck (5.2.3))
(Dorizzi
(Czernichow
(Cibas (5.3.5)) 15 001011111111111110100
(Leray

Table

4. Performance comparison of different variable selection methods on the
original wave problem.
Number of remaining variables
ECD
OCD

Figure

1. Performance comparison of two variable selection methods (OCD and
ECD) according to the number of remaining variables for the noisy wave
problem.

Figure

shows performance curves for two methods, OCD and ECD, estimated
on a validation set. Since we have used a single validation set, there are small
fluctuations in the performances. Some form of cross validation should be used
in order to get better estimates, the test strategy proposed for ECD looks also
attractive in this case. It can be seen that for this problem, performances are more
or less similar during the backward elimination (they slightly rise) until they
quickly drop when relevant variables are removed.842060100
None
Yacoub
Moody
Cibas
Leray
Ruck
Stepdisc
Bonnlander
Czernichow

Figure

2. Performance comparison of different variable selection methods vs.
percentage of selected variables on the original wave problem. x axis: percentage
of variables selected, y axis: percentage of correct classification.

Figure

2 gives the repartition of different variable selection methods for the
original wave problem according to their performances (y axis) and the
percentage of selected variables (x axis). The best methods are those with the best
performances and the lower number of variables. In this problem, "Leray" is
satisfying (see figure 2). "Yacoub" does not delete enough variables while
"Bonnlander" deletes too much variables.
The second problem is a two class problem in a 20 dimensional space. The
classes are distributed according two gaussians with respectively - 1 =(0,.,0),
(a is chosen so that ||- 1 - 2 In this
problem, variable relevance is ordered according to their index: x 1 is useless,
x i+1 is more relevant than x i .
Method p * Selected Variables Perf .
Stepdisc (4.2.2) 17 10001111111111111111
(Bonnlander (4.3.2)) 5 00010000000000011011
90.60 %
94.86 %
(Moody (5.2.1)) 9 01000100011000110111
92.94 %
(Ruck
94.86 %
(Dorizzi (5.2.7)) 11 00000000101111111111
(Czernichow (5.2.8)) 9 00000000001101111111
(Cibas
(Leray (5.3.6)) 15 01011011101110111111

Table

5. Performance comparison of different variable selection methods on the
two gaussian problem with uncorrelated variables.9193954080%
None
Yacoub Stepdisc
Leray
Cibas Dorizzi
Ruck
Czernichow
Moody
Bonnlander

Figure

3. Performance comparison of different variable selection methods vs.
percentage of selected variables on the two gaussian problem with uncorrelated
variables. x axis: percentage of variables selected, y axis: percentage of correct
classification.
Table

5 shows that Stepdisc is not adapted for this non linear frontier: it is the
only method that selects x 1 which is useless for this problem. We can remark on
figure 3 that Bonnlander's method deletes too many variables whereas Yacoub's
stop criterion is too rough and does not delete enough variables.
In an other experiment, we replaced the I matrix in S 1 and S 2 by a block
diagonal matrix. Each block is 5x5 so that there are four groups of five
successive correlated variables in the new problem.
Method p * Selected Variables Perf .
90.58 %
Stepdisc (4.2.2) 11 00001101011010110111
(Bonnlander (4.3.2)) 5 00001001010000100001
(Ruck
91.06 %
(Leray
90.72 %

Table

6. Performance comparison of different variable selection methods on the
two gaussian problem with correlated variables.

Table

6 gives the results of some representative methods for this problem:
. Stepdisc still gives a model with good performances but selects
many correlated variables,
. Bonnlander's method selects only 5 variables and gives
significantly lower results,
. Ruck's method obtains good performances but selects some
correlated variables,
. Leray's method, thanks to the retraining after each variable deletion,
find models with good performances and few variables (7 compared
to 10 and 11 for Ruck and Stepdisc).
7 . Conclusion
We have reviewed variable selection methods developed in the field of Neural
Networks. The main difficulty here is that NNs are non linear systems which do
not make use of explicit parametric hypothesis. As a consequence, selection
methods rely heavily on heuristics for the three steps of variable selection :
relevance criterion, search procedure - NN variable selection use mainly
backward search - and choice of the final model. We first discussed the main
difficulties for developing each of these steps. We then introduced different
families of methods and discussed their strengths and weaknesses. We believe
that a variable selection method must remain computationally feasible for being
useful, and we have not considered techniques which rely on computer intensive
methods like e.g. bootstrap at each step of the selection . Instead, we have
proposed a series of rules which could be used in order to enhance several of the
methods which have been described, at a reasonable extra computational cost,
e.g. retraining each NN in the sequence and computing the relevance for each of
these NN allows to take into account some correlations between variables, simple
estimates of the generalization error may be used for the evaluation of a variable
subset, simple tests on these estimates, allow to choose minimal variable sets
(section 5.3.3). Finally we performed a comparison of representative NN
selection techniques on synthetic problems.



--R

Statistical Predictor Identification
Using Mutual Information for Selecting Features in Supervised Neural Net Learning
Bootstrapping confidence intervals for clinical input variable effects in a network trained to identify the presence of acute myocardial infraction
Selecting Input Variables Using Mutual Information and Nonparametric Density Evaluation
Classification and Regression Trees.
Fogelman Souli-
Fogelman Souli-
Architecture Selection through Statistical Sensitivity Analysis.

Independent Coordinates for Strange Attractors from Mutual Information
Extracting the Relevant Decays in Time Series Modelling
Gustafson and Hajlmarsson
Selection of Variables in Discriminant Analysis by F-statistic and Error Rate
Applied Nonparametric Regression.
Econometric Society Monograph n.
Sensitivity Analysis for Feedforward Artificial Neural Networks with Differentiable Activation Functions.
Second Order Derivatives for Network Pruning
Feature Selection and Extraction
Generalized performances of regularized neural networks models.

Bayesian Non-linear Modelling for the Energy Prediction Competition

Discriminant Analysis and Statistical Pattern Recognition
Note on generlization
Principled Architecture Selection for Neural Networks: Application to Corporate Bond Rating Prediction.
Prediction Risk and Architecture Selection for Neural Networks in From Statistics to Neural Networks - Theory and Pattern Recognition Applications

A Branch and Bound Algorithm for Feature Subset Selection.


Floating search methods in feature selection.
Pattern Recognition Letters

Attribute Suppression with Multi-Layer Perceptron

Fast Network Pruning and Feature Extraction Using the Unit-OBS Algorithm
Selection of Variables in Multiple Regression.


Learning in Artificial Neural Networks
Mathematical Statistics
HVS: A Heuristic for Variable Selection in Multilayer Artificial Neural Network Classifier.
--TR
Feature selection for automatic classification of non-Gaussian data
Image enhancement and thresholding by optimization of fuzzy compactness
Introduction to statistical pattern recognition (2nd ed.)
Floating search methods in feature selection
Merging back-propagation and Hebbian learning rules for robust classifications
Feature Selection
Neural Networks for Pattern Recognition

--CTR
E. Gasca , J. S. Snchez , R. Alonso, Rapid and brief communication: Eliminating redundancy and irrelevance using a new MLP-based feature selection method, Pattern Recognition, v.39 n.2, p.313-315, February, 2006
Rajen B. Bhatt , M. Gopal, On fuzzy-rough sets approach to feature selection, Pattern Recognition Letters, v.26 n.7, p.965-975, 15 May 2005
M. Bacauskiene , A. Verikas, Selecting salient features for classification based on neural network committees, Pattern Recognition Letters, v.25 n.16, p.1879-1891, December 2004
Chao-Ton Su , Long-Sheng Chen , Tai-Lin Chiang, A neural network based information granulation approach to shorten the cellular phone test process, Computers in Industry, v.57 n.5, p.412-423, June 2006
D. Franois , F. Rossi , V. Wertz , M. Verleysen, Resampling methods for parameter-free and robust feature selection with mutual information, Neurocomputing, v.70 n.7-9, p.1276-1288, March, 2007
R. E. Abdel-Aal, GMDH-based feature ranking and selection for improved classification of medical data, Journal of Biomedical Informatics, v.38 n.6, p.456-468, December 2005
regularization;classification;feature selection;neural network