Filter Methods for Feature Selection

The central connection is this: feature selection is coupled with the underlying learning algorithm because candidate subsets are judged through the predictors they produce.

Programming

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.

Key point

The central connection is this: feature selection is coupled with the underlying learning algorithm because candidate subsets are judged through the predictors they produce.

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.

Starting with no selected features, which candidate subsets are evaluated at each step, which feature is added, and how does the selected set grow?

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.

Worked example

One Forward-Selection Round

Assume the current selected set is empty and the remaining features are A, B, and C. The learning algorithm evaluates the one-feature candidates and reports hypothetical risks: A has risk 4, B has risk 7, and C has risk 5.

1
Form candidates
The candidates are the one-feature sets containing A, B, or C.
2
Compare risks
The method compares the three candidate predictors using their risks.
3
Choose the addition
Because the candidate containing A has the smallest hypothetical risk, A is added to the selected set.

Result

The selected set becomes {A}. The next round tests additions to {A}, such as {A, B} and {A, C}, using the same process.

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.

What happens when no remaining feature improves the evaluation score, or when the allowed number of features has been reached?

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.

Starting with every feature, which feature is removed at each step, and how does the remaining feature set shrink?

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.

Worked example

One Backward-Elimination Round

Assume the current set is {A, B, C}. The learning algorithm evaluates the sets produced by removing one feature and reports hypothetical risks: removing A gives risk 6, removing B gives risk 4, and removing C gives risk 8.

1
Form removal candidates
The candidates are {B, C}, {A, C}, and {A, B}, corresponding to removing A, B, or C.
2
Compare risks
The method compares the risks of the three candidate predictors.
3
Choose the removal
Removing B gives the smallest hypothetical risk, so B is removed.

Result

The remaining set becomes {A, C}. The next round tests removals from this smaller set.

Opposite Directions, Same Decision Rule

How do forward selection and backward elimination choose and evaluate their next feature sets from opposite starting points?

Property	Forward selection	Backward elimination
Starting point	Empty feature set	Full feature set
Candidate change	Add one feature not yet selected	Remove one feature currently selected
Learning step	Apply the learning algorithm to every one-feature addition	Apply the learning algorithm to every one-feature removal
Next change	Addition whose candidate predictor has the smallest risk	Removal whose candidate predictor has the smallest risk
Direction	Grows the selected set	Shrinks the selected set

Both methods compare one-step candidate predictors through the learning algorithm, but they begin and move in opposite directions.

Key point

The shared rule is smallest risk among the candidates being considered. The difference is which one-step candidates exist: additions for forward selection and removals for backward elimination.

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.

How does the method evaluate each feature separately, assign it a score, and rank the features before selection?

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.

How does a predictor trained using only one feature produce predictions, and how are the squared errors combined into that feature's quality score?

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.

Key point

A feature receives a predictive score according to how well a predictor based only on that feature performs. Under squared loss, the score reflects the combined size of the prediction errors after those errors are squared.

Common Selection Mistakes

Common mistake
Treating forward selection as an independent feature-ranking method.
What it looks like
Ranking every feature once and then adding features in that fixed order.
Why it fails
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.
Do this instead
At every stage, form the candidate additions to the current selected set and compare their resulting predictor risks.
Common mistake
Starting backward elimination with an empty set.
What it looks like
Testing which feature should be added first while calling the procedure backward elimination.
Why it fails
Backward elimination begins with the full feature set and tests one-feature removals.
Do this instead
Begin with all features, evaluate the candidate sets produced by removing each current feature, and remove the feature associated with the smallest risk.
Common mistake
Assuming a filter method combines all features while assigning individual scores.
What it looks like
Training one model on the entire feature set and calling the resulting single score an independent feature score.
Why it fails
The filter procedure described here examines each feature on its own and produces one assessment result per feature.
Do this instead
Assess each feature separately, then compare the resulting quality scores during selection.
Common mistake
Assuming squared loss is the prediction itself.
What it looks like
Calling a feature's predicted target value its squared-loss score.
Why it fails
Predictions are compared with matching targets to obtain errors. Squared loss is produced after the errors are squared and combined.
Do this instead
Distinguish the single-feature predictor, its predictions, its errors, and the resulting empirical squared-loss measure.

Practice the Two Directions

EASY

A current forward-selection set is {A}. The remaining features are B and C. The candidate predictor using {A, B} has risk 3, while the candidate predictor using {A, C} has risk 5. What is the next selected set, and why?

Hints

Forward selection tests additions to the current set.
Choose the candidate predictor with the smaller risk.

Your attempt (not saved)

EASY

A current backward-elimination set is {A, B, C}. Removing A gives risk 6, removing B gives risk 8, and removing C gives risk 4. Which feature is removed next, and what remains?

Hints

Backward elimination tests one-feature removals.
The removal producing the smallest risk is selected.

Your attempt (not saved)

What do you think happens?

A forward-selection process has reached its allowed budget of k features, but another feature could produce a lower-risk candidate. Does the process continue?

Yes, because lower risk always overrides the budget
No, because reaching the predefined budget is a stopping condition

Reveal answer

Answer:

No, because reaching the predefined budget is a stopping condition.

Forward selection can be limited by a predefined number of features. It can also stop earlier when the resulting predictor is accurate enough.

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.

At a glance

Greedy selection uses a learning algorithm to compare one-step feature-set changes.
Forward greedy selection grows an empty set through feature additions.
Backward elimination shrinks the full set through feature removals.
Filter methods score features independently before comparing those scores for selection.
Empirical squared loss measures the combined squared prediction errors of a predictor trained with one feature.

More concepts starting with F