Forward Greedy Selection
The central greedy rule is simple: evaluate every one-step candidate with the learning algorithm, then choose the candidate predictor with the smallest risk.
Selection Through Learning
Suppose a dataset contains many features, but the predictor should use only a selected subset. Greedy selection makes that choice by asking the learning algorithm to evaluate possible feature subsets. Feature selection is therefore coupled with learning: the method does not first select features independently and only later train a predictor.
The central greedy rule is simple: evaluate every one-step candidate with the learning algorithm, then choose the candidate predictor with the smallest risk.
Growing from Nothing
Forward selection begins with no selected features. Call the current selected set I. At that stage, every feature not already in I is a candidate for addition. The method temporarily adds each candidate feature to I, applies the learning algorithm to each resulting set, and compares the resulting risks. The feature whose candidate predictor has the smallest risk is added to I.
A Hypothetical Forward-Selection Trace
Start with an empty selected set and three available features: A, B, and C. Use the learning algorithm's candidate risk to choose each addition.
- 1Start
The selected set is empty. The candidates are the one-feature sets {A}, {B}, and {C}.
- 2First evaluation
Assume the learning algorithm gives these illustrative risks: {A} has risk 8, {B} has risk 5, and {C} has risk 7. The candidate with the smallest risk is {B}, so B is added.
- 3Second evaluation
The current set is now {B}. The remaining candidates are {B, A} and {B, C}. Assume their illustrative risks are 4 and 6. The smaller risk belongs to {B, A}, so A is added.
- 4Stopping decision
The selected set is {B, A}. Forward selection now checks its stopping rule, such as a predefined feature budget or a predictor that is accurate enough.
The trace produces the selected set {B, A} before the stopping decision. The numbers are illustrative; the method's rule is to choose the candidate with the smallest risk.
When Forward Selection Stops
Forward selection does not have to continue until every feature has been selected. One stopping condition is a predefined budget of k features. Another is that the resulting predictor is accurate enough. These choices make the stopping rule either feature-limited or accuracy-driven.
Shrinking from the Full Set
Backward elimination reverses the starting point. It begins with the full feature set rather than an empty set. If the current set is I, the method considers every feature i in I. For each candidate feature, it removes i, applies the learning algorithm to the remaining set, and obtains a predictor. The feature whose removal produces the smallest risk is removed next.
A Hypothetical Backward-Elimination Trace
Start with the full set {A, B, C} and test which single-feature removal produces the smallest candidate risk.
- 1Start
The current set is {A, B, C}. The removal candidates are {B, C}, {A, C}, and {A, B}.
- 2Evaluate removals
Assume the learning algorithm gives illustrative risks of 6 for {B, C}, 4 for {A, C}, and 7 for {A, B}. The smallest risk is 4, produced by removing B.
- 3Update
The current set becomes {A, C}. The method can now test removing A or removing C from this smaller set.
Backward elimination removes B in the first step because the predictor using {A, C} has the smallest illustrative risk among the one-feature-removal candidates.
Opposite Directions
Forward selection and backward elimination use the same evaluation principle but move through the feature-subset space in opposite directions. Forward selection grows an empty set by testing one-feature additions. Backward elimination shrinks the full set by testing one-feature removals. In both methods, the learning algorithm evaluates every one-step candidate, and the next change is chosen using the candidate predictor with the smallest risk.
| Method | Starting set | Candidate change | Next choice |
|---|---|---|---|
| Forward selection | Empty set | Add one feature not already selected | Addition whose predictor has the smallest risk |
| Backward elimination | Full feature set | Remove one feature currently selected | Removal whose resulting predictor has the smallest risk |
Both methods evaluate one-step candidate subsets through the learning algorithm.
Common Selection Mistakes
Common mistake Treating feature selection as completely separate from learning.
What it looks likeChoosing features without having the learning algorithm evaluate the resulting candidate subsets.
Why it failsGreedy selection couples feature selection with the underlying learning algorithm.
Do this insteadFor every one-step candidate subset, apply the learning algorithm and compare the resulting risks.
Common mistake Starting forward selection with the full feature set.
What it looks likeBeginning forward selection with {A, B, C} and removing features.
Why it failsForward selection begins with no selected features and tests additions.
Do this insteadStart with the empty set and consider each feature not already selected.
Common mistake Assuming backward elimination adds features.
What it looks likeTaking an empty set and adding the feature with the smallest candidate risk while calling the method backward elimination.
Why it failsBackward elimination begins with the full set and tests removals.
Do this insteadFor each feature in the current set, evaluate the set formed by removing that feature.
Common mistake Continuing forward selection without a stopping rule.
What it looks likeAdding features until every feature has been selected even when a feature budget or sufficient accuracy would stop the process earlier.
Why it failsForward selection can stop at a predefined budget of k features or when the resulting predictor is accurate enough.
Do this insteadState the stopping rule before interpreting the final selected subset.
Practice the Trace
A current forward-selection set is {A}. The remaining features are B and C. The learning algorithm evaluates {A, B} with risk 9 and {A, C} with risk 6. Which candidate becomes the next selected set, and what additional stopping information would you need before deciding whether to stop?
Hints
- Compare the risks of the one-feature additions.
- The smaller risk determines the next selected set.
- A predefined feature budget or an accuracy requirement determines whether selection continues.
Practice Answer
Choose between {A, B} with risk 9 and {A, C} with risk 6.
- 1Compare candidates
The candidate set {A, C} has the smaller risk.
- 2Update
Forward selection chooses {A, C} as the next selected set.
- 3Check the stopping rule
The process may stop if the feature budget has been reached or if the resulting predictor is accurate enough. Otherwise, it can evaluate another one-feature addition.
The next selected set is {A, C}. The risks alone choose the next set; the stopping rule determines whether another step occurs.
Key Takeaways
- 1Greedy selection lets the learning algorithm evaluate candidate feature subsets directly.
- 2Forward selection starts with an empty set, tests one-feature additions, and keeps the addition with the smallest candidate risk.
- 3Forward selection can stop at a predefined feature budget or when the resulting predictor is accurate enough.
- 4Backward elimination starts with the full set, tests one-feature removals, and removes the feature whose removal produces the smallest risk.
- 5The two methods share the same candidate-evaluation rule but differ in their starting sets and direction of movement.
At a glance
- Greedy selection couples feature selection to the learning algorithm.
- Forward selection grows a subset from empty by evaluating one-feature additions.
- Backward elimination shrinks the full set by evaluating one-feature removals.
- At each step, the candidate predictor with the smallest risk determines the next change.
- Forward selection stops according to a feature budget, sufficient predictor accuracy, or exhaustion of possible additions.