Irrelevant Features and the Subset Selection Problem

We address the problem of finding a subset of features tha t allows a supervised induction algori thm to induce small high-accuracy concepts. We examine notions of relevance and irrelevance, and show tha t the definitions used in the machine learning literature do not adequately part i t ion the features into useful categories of relevance. We present definitions for irrelevance and for two degrees of relevance. These definitions improve our understanding of the behavior of previous subset selection algorithms, and help define the subset of features tha t should be sought. The features selected should depend not only on the features and the target concept, but also on the induction algorithm. We describe a method for feature subset selection using cross-validation tha t is applicable to any induction algorithm, and discuss experiments conducted with ID3 and C4.5 on artificial and real datasets . 1 I N T R O D U C T I O N In supervised learning, one is given a training set containing labelled instances. The instances are typically specified by assigning values to a set of features, and the task is to induce a hypothesis tha t accurately predicts the label of novel instances. Following Occam's razor (Blumer et al. 1987), min imum description length (Rissanen 1986), and min imum message length (Wallace & Freeman 1987), one usually a t t empts to find structures tha t correctly classify a large subset of the training set, and yet are not so complex tha t they begin to overfit the da ta . Ideally, the induction algor i thm should use only the subset of features tha t leads to the best performance. Since induction of minimal structures is NP-hard in many cases (Hancock 1989; Blum & Rivest 1992), algorithms usually conduct a heuristic search in the Figure 1: An example where ID3 picks a bad relevant feature (correlated) for the root, and an irrelevant feature (irrelevant). space of possible hypotheses. This heuristic search may lead to induced concepts which depend on irrelevant features, or in some cases even relevant features tha t hurt the overall accuracy.  1 shows such a choice of a non-optimal split at the root made by ID3 (Quinlan 1986). The Boolean target concept is (AO A Al ) V (BO A Bl). The feature named "irrelevant" is uniformly random, and the feature "correlated" matches the class label 75% of the t ime. The left subtree is the correct decision tree, which is correctly induced if the "correlated" feature is removed from the da ta . C4.5 (Quinlan 1992) and CART (Breiman et al. 1984) induce similar trees with the "correlated" feature at the root. Such a split causes all these induction algorithms to generate trees tha t are less accurate than if this feature is completely removed. The problem of feature subset selection involves finding a "good" set of features under some objective function. Common objective functions are prediction accuracy, 122 John, Kohavi, and Pfleger structure size, and minimal use of input features (e.g., when features are tests tha t have an associated cost). In this paper we chose to investigate the possibility of improving prediction accuracy or decreasing the size of the structure without significantly decreasing prediction accuracy. This specific problem has been thoroughly investigated in the statistics literature, but under assumptions tha t do not apply to most learning algorithms (see Section 5). We begin by describing the notions of relevance and irrelevance tha t have been previously defined by researchers. We show tha t the definitions are too coarse-grained, and tha t better understanding can be achieved by looking at two degrees of relevance. Section 3 looks at two models for feature subset selection: the filter model and the wrapper model. We claim tha t the wrapper model is more appropriate than the filter model, which has received more attention in machine learning. Section 4 presents our experimental results, Section 5 describes related work, and Section 6 provides a summary and discussion of future work. 2 D E F I N I N G R E L E V A N C E In this section we present definitions of relevance tha t have been suggested in the literature. We then show a single example where the definitions give unexpected answers, and we suggest tha t two degrees of relevance are needed: weak and strong. The input to a supervised learning algorithm is a set of n training instances. Each instance X is an element of the set F\ x F2 x • • • x Fm, where Fi is the domain of the i th feature. Training instances are tuples (X, Y) where Y is the label, or output . Given an instance, we denote the value of feature Xi by X{. The task of the induction algorithm is to induce a structure (e.g., a decision tree or a neural net) such tha t , given a new instance, it is possible to accurately predict the label Y. We assume a probability measure p on the space F\ x F2 x • • • x Fm x Y. Our general discussion does not make any assumptions on the features or on the label; they can be discrete, continuous, linear, or structured, and the label may be single-valued or a multi-valued vector of arbitrary dimension. 2.1 E X I S T I N G D E F I N I T I O N S Almuallim and Dietterich (1991, p . 548) define relevance under the assumption tha t all features and the label are Boolean and tha t there is no noise. D e f i n i t i o n 1 A feature X{ is said to be re levant to a concept C if X{ appears in every Boolean formula that represents C and irrelevant otherwise. Gennari et al. (1989, Section 5.5) define relevance a s 1 xThe definition given is a formalization of their stateDefinition Relevant Irrelevant Definition 1 Xx X2,X3,X4,Xs Definition 2 None All Definition 3 All None Definition 4 X2,Xs,X4,X^ Table 1: Feature relevance for the Correlated XOR problem under the four definitions. Def in i t i on 2 Xi is relevant iff there exists some X{ and y for which p(X{ = X{) > 0 such that p ( Y = y \ X i = xi)j:p(Y = y) . Under this definition, Xi is relevant if knowing its value can change the estimates for Y, or in other words, if Y is conditionally dependent of X{. Note tha t this definition fails to capture the relevance of features in the parity concept, and may be changed as follows. Let Si be the set of all features except Xi, i.e., Si = {Xi,..., X{-1, Xi+i,..., Xm }. Denote by Si a valueassignment to all features in Si. Def in i t i on 3 Xi is relevant iff there exists some Xi, y, and Si for which p(Xi = Xi) > 0 such that p(Y = y,Si = S i I Xi = *,.) ^ p(Y = y,Si = Si) . Under the following definition, Xi is relevant if the probability of the label (given all features) can change when we eliminate knowledge about the value of Xi. Def in i t i on 4 Xi is relevant iff there exists some Xi, y, and Si for which p(Xi = Si =$,-)>() such that p(Y = y\ Xi = Xi,Si = Si)^p(Y = y\Si = Si) The following example shows tha t all the definitions above give unexpected results. E x a m p l e 1 ( C o r r e l a t e d X O R ) Let features X\,..., X*> be Boolean. The instance space is such that X2 and X3 are negatively correlated with X4 and X§, respectively, i.e., X4 = X2, X$ = X3. There are only eight possible instances, and we assume they are equiprobable. The (deterministic) target concept is y = I I © I 2 (0 denotes XOR) . Note tha t the target concept has an equivalent Boolean expression, namely, Y = X\ 0 I 4 . The features X3 and X5 are irrelevant in the strongest possible sense. Xi is indispensable, and one of X2, X4 can be disposed ment: "Features are relevant if their values vary systematically with category membership." Irrelevant Features and the Subset Selection Problem 123