Filter Methods for Feature Selection

Choosing Features Through Learning

Suppose a dataset contains many features, but the final predictor should use only a smaller subset. Greedy selection lets the learning algorithm help make that choice. Instead of selecting features independently of learning, the method forms candidate feature subsets, trains or applies the learning algorithm to each candidate, and compares the resulting risks. The candidate with the smallest risk determines the next change.

Forward Selection from Nothing

Forward greedy selection begins with an empty selected set. Call the current selected set I. At each stage, the method examines every feature that is not already in I. It creates one candidate set for each possible addition, applies the learning algorithm to every candidate, and compares their risks. The feature whose addition gives the candidate predictor the smallest risk is added to I.

1. Start with no selected features.
2. List every feature that is not yet selected.
3. Add each remaining feature separately to the current set to form one-step candidate subsets.
4. Apply the learning algorithm to every candidate subset.
5. Compare the candidate risks.
6. Add the feature belonging to the candidate with the smallest risk.
7. Repeat until a stopping condition is reached.

Why the Risk Decides

A feature is not added merely because it is available. Its addition must produce a candidate predictor whose risk is compared with the risks of the other one-step candidates. The next change is the addition associated with the smallest risk. This makes the learning algorithm part of the selection mechanism rather than a separate step performed only after selection.

Forward selection can stop when it reaches a predefined budget of k features. It can also stop earlier when the resulting predictor is accurate enough. More generally, the process need not continue until every feature has been selected; the stopping rule determines whether the procedure is limited by feature count or by the desired predictor accuracy.

Backward Elimination from Everything

Backward elimination starts at the opposite point: the current set contains every feature. If the current set is I, the method considers each feature i in I as a possible removal. For each candidate, it applies the learning algorithm to I without i and obtains a predictor. The feature removed next is the one whose removal produces the smallest risk.

1. Start with the full feature set.
2. Consider removing each feature currently in the set.
3. Apply the learning algorithm to every set produced by one removal.
4. Compare the risks of the resulting candidate predictors.
5. Remove the feature whose removal produces the smallest risk.
6. Repeat with the reduced set.

Opposite Directions, Same Decision Rule

Independent Filter Scores

A filter method reduces a feature set by scoring each feature independently. It examines one feature on its own, assigns that feature a quality score, and compares the scores before selecting the stronger candidates. Assessment therefore produces one result per feature, while selection happens afterward when those results are compared.

The score is not fixed by the filter procedure itself. Many quality measures are possible. One direct approach is predictive: give a feature a score based on the error rate of a predictor trained solely from that feature.

Scoring with Squared Loss

The source illustrates an error-based filter score with linear regression and squared loss. To assess the jth feature, use only that feature's values across the training examples together with the matching target values. Train a predictor using this single feature. The predictor produces a target estimate for each example. The difference between each estimate and its matching target is an error; squared loss squares those errors and combines them into an empirical measure of prediction quality.

1. Take the values of one candidate feature across the training examples.
2. Pair those feature values with the matching target values.
3. Train a predictor using only that feature; the source illustration uses linear regression.
4. Generate a prediction for each training example.
5. Compare each prediction with its matching target to obtain an error.
6. Square the errors and combine them into the empirical squared-loss quality measure.
7. Use the resulting score to compare this feature with other independently assessed features.

Common Selection Mistakes

• Treating forward selection as an independent feature-ranking method.

  Forward greedy selection evaluates one-step candidate subsets through the learning algorithm at each stage. The next choice is based on candidate risk, not simply on a permanent initial ranking.

  Fix: At every stage, form the candidate additions to the current selected set and compare their resulting predictor risks.

• Starting backward elimination with an empty set.

  Backward elimination begins with the full feature set and tests one-feature removals.

  Fix: Begin with all features, evaluate the candidate sets produced by removing each current feature, and remove the feature associated with the smallest risk.

• Assuming a filter method combines all features while assigning individual scores.

  The filter procedure described here examines each feature on its own and produces one assessment result per feature.

  Fix: Assess each feature separately, then compare the resulting quality scores during selection.

• Assuming squared loss is the prediction itself.

  Predictions are compared with matching targets to obtain errors. Squared loss is produced after the errors are squared and combined.

  Fix: Distinguish the single-feature predictor, its predictions, its errors, and the resulting empirical squared-loss measure.

Practice the Two Directions

Key Takeaways

1. Greedy selection couples feature selection with a learning algorithm by evaluating candidate subsets through their predictors and risks.
2. Forward selection starts empty, tests one-feature additions, and adds the feature whose candidate predictor has the smallest risk.
3. Backward elimination starts with all features, tests one-feature removals, and removes the feature whose removal produces the smallest risk.
4. Forward selection may stop at a feature budget or when the predictor is accurate enough.
5. A filter method assesses features independently, and a single-feature predictor with empirical squared loss can provide an error-based quality score.