Backward Elimination
Greedy selection evaluates feature subsets through the learning algorithm rather than separating selection from learning.
The Search Begins with a Choice
Suppose a dataset contains many features, but the predictor should use only a selected subset. The central question is not simply which features look useful in isolation. Instead, a learning algorithm can evaluate candidate subsets directly. Greedy selection couples feature selection with the underlying learning algorithm: each possible next change is tested by applying the learning algorithm, and the candidate with the smallest risk is chosen.
Backward elimination starts with every feature and repeatedly considers removing one feature at a time.
Removing Features from the Full Set
Let I represent the current set of selected features. In backward elimination, I initially contains the full feature set. At a stage of the search, the method considers every feature i in I. Each candidate is formed by removing i, so the candidates have the form I without i. The learning algorithm is applied to every candidate subset. The removal chosen for the next step is the one whose candidate predictor has the smallest risk.
The diagram shows one iteration with four features. The method does not remove a feature arbitrarily. It creates one candidate for each possible removal, evaluates all of them through the learning algorithm, and then keeps the candidate associated with the smallest risk as the current set for the next iteration.
How Candidate Subsets Are Evaluated
Feature selection and learning are therefore connected at every step. The candidate subsets are not ranked by a separate feature-selection rule in the description. Each candidate is passed through the learning algorithm, and its resulting predictor supplies the risk used for the greedy choice.
A Complete Removal Step
Choosing One Feature to Remove
A current feature set is {A, B, C}. Illustrate one backward-elimination step by considering every one-feature removal.
Start with the current set: The current set is {A, B, C}, which represents the features presently used by the predictor.
Form the candidates: Removing A produces {B, C}; removing B produces {A, C}; removing C produces {A, B}.
Evaluate the candidates: The learning algorithm is applied to each candidate subset, producing a predictor and its risk for each candidate.
Make the greedy choice: The candidate with the smallest risk becomes the next feature set. The feature absent from that candidate is the feature removed in this step.
Backward elimination changes the current set by removing exactly one feature selected through the candidate predictors' risks.
Forward and Backward Directions
| Method | Starting set | Candidates at each stage | Direction |
|---|---|---|---|
| Forward selection | Empty set | Add one feature not already selected | Grows the set |
| Backward elimination | Full feature set | Remove one feature currently selected | Shrinks the set |
Forward selection begins with no selected features. If the current set is I, it considers every feature not already in I, adds each one in turn, and chooses the addition whose candidate predictor has the smallest risk. Backward elimination uses the reverse starting point and change: it begins with the full set and tests one-feature removals.
When the Search Stops
The source describes two stopping conditions for forward greedy selection. A predefined budget can stop the process when the selected set reaches k features. Alternatively, the process can stop earlier when the resulting predictor is accurate enough. The stopping rule therefore determines whether the search is limited by the number of features or by the desired predictor accuracy.
Common Reasoning Mistakes
Starting backward elimination with an empty set
Backward elimination begins with the full feature set and shrinks it by testing removals.
Fix:
Write the full set as the initial current set, then form one candidate for each possible one-feature removal.Removing the first feature that seems unhelpful
The method considers every feature in the current set and applies the learning algorithm to each resulting candidate subset.
Fix:
Evaluate all one-feature removals and choose the candidate predictor with the smallest risk.Confusing the removed feature with the chosen subset
Risk belongs to the candidate predictor formed after a removal.
Fix:
Choose the candidate subset with the smallest risk; the feature absent from that subset is the feature removed.Describing forward selection and backward elimination as the same search
Forward selection starts empty and tests additions, while backward elimination starts full and tests removals.
Fix:
State both the starting point and the one-step modification when identifying the method.
Check Your Understanding
A current feature set is {P, Q, R, S}. Describe the candidates that backward elimination must evaluate during its next step, and explain how it chooses the next set. Then describe how forward selection would behave if its current selected set were empty.
Hints
- For backward elimination, create one candidate for each feature removed from the current set.
- For forward selection, begin with no selected features and consider one-feature additions.
- In both cases, the learning algorithm evaluates the candidate predictors and the smallest risk determines the next set.
The Greedy Pattern
- Greedy selection couples feature selection with the learning algorithm by evaluating candidate subsets through their predictors.
- Backward elimination starts with the full feature set and tests every one-feature removal.
- The next backward-elimination set is the candidate whose predictor has the smallest risk.
- Forward selection starts empty and tests one-feature additions, while backward elimination starts full and tests one-feature removals.
- Forward selection can stop at a predefined budget of k features or when the resulting predictor is accurate enough.
Key Takeaways
- Backward elimination begins with every feature and removes one feature per greedy step.
- Every possible one-feature removal is evaluated through the learning algorithm.
- The candidate predictor with the smallest risk determines the next feature set.
- Forward selection grows from an empty set, whereas backward elimination shrinks the full set.
- Forward greedy selection may stop at a feature budget or when the predictor is accurate enough.