Toward Optimal Feature Selection
Daphne Koller
Gates Building 1A
Computer Science Department
Stanford University
Stanford, CA 94305-9010
koller@cs.stanford.edu
Mehran Sahami
Gates Building 1A
Computer Science Department
Stanford University
Stanford, CA 94305-9010
sahami@cs.stanford.edu
Abstract
In this paper, we examine a metho d for fea-
ture subset selection based on Information
Theory. Initially,aframework for dening
the theoretically optimal, but computation-
ally intractable, method for feature subset se-
lection is presented. We show that our goal
should be to eliminate a feature if it gives
us little or no additional information beyond
that subsumed by the remaining features. In
particular, this will be the case for both ir-
relevant and redundant features. Wethen
give an ecient algorithm for feature selec-
tion which computes an approximation to the
optimal feature selection criterion. The con-
ditions under which the approximate algo-
rithm is successful are examined. Empirical
results are given on a number of data sets,
showing that the algorithm eectively han-
dles datasets with large numbers of features.
1 Intro duction
In the classic
supervisedlearning
task, we are given a
training set of labeled xed-length feature vectors, or
instances, from which to induce a classication model.
This mo del is then used to predict the class lab el for
a set of previously unseen instances. Thus, the infor-
mation about the class that is inherent in the features
determines the accuracy of the model. Theoretically,
having more features should give us more discriminat-
ing power. However, the real-world provides us with
many reasons why this is not generally the case.
First, the time requirements for an induction algo-
rithm often grow dramatically with the number of fea-
tures, rendering the algorithm impractical for prob-
lems with a large number of features. Furthermore,
many learning algorithms can be viewed as p erform-
ing (a biased form of ) estimation of the probabilityof
the class label given a set of features. In domains with
alargenumber of features, this distribution is very
complex and of high dimension. Unfortunately, in the
real world, we are often faced with the problem of lim-
ited data from which to induce a model. This makes
it very dicult to obtain go od estimates of the many
probabilistic parameters. In order to avoid over-tting
the model to the particular distribution seen in the
training data, many algorithms employ the Occam's
Razor (Blumer
et al.
1987) bias to build as simple a
model as p ossible that still achieves some acceptable
level of performance on the training data. This bias
often leads us to prefer a small number of relatively
predictive features overavery large number of features
that, taken in the prop er, but complex, combination,
are entirely predictive of the class lab el. Irrelevant and
redundant features also cause problems in this context
as they may confuse the learning algorithm by helping
to obscure the distributions of the small set of truly
relevant features for the task at hand.
If we reduce the set of features considered by the al-
gorithm, we can therefore servetwo purposes. We can
considerably decrease the running time of the induc-
tion algorithm, and we can increase the accuracy of
the resulting model. In light of this, a numberofre-
searchers have recently addressed the issue of feature
subset selection in machine learning. As dened by
(John, Kohavi, & Peger 1994), this work is often di-
vided along two lines: lter and wrapp er mo dels.
In the lter model, feature selection is performed as
a preprocessing step to induction. Thus the bias of
the learning algorithm do es not interact with the bias
inherent in the feature selection algorithm. Twoof
the most well-known lter metho ds for feature selec-
剩余8页未读，继续阅读
资源评论
