Backward Elimination

Backward elimination starts with every feature and repeatedly considers removing one feature at a time.

Programming

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.

Key point

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.

What happens as backward elimination starts with every feature and removes one feature at a time?

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

How does the learning algorithm evaluate each possible feature removal before the next subset is chosen?

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.

How does feature selection use the learning algorithm's result to choose the next feature subset?

A Complete Removal Step

Worked example

Choosing One Feature to Remove

A current feature set is {A, B, C}. Illustrate one backward-elimination step by considering every one-feature removal.

1
Start with the current set
The current set is {A, B, C}, which represents the features presently used by the predictor.
2
Form the candidates
Removing A produces {B, C}; removing B produces {A, C}; removing C produces {A, B}.
3
Evaluate the candidates
The learning algorithm is applied to each candidate subset, producing a predictor and its risk for each candidate.
4
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.

Result

Backward elimination changes the current set by removing exactly one feature selected through the candidate predictors' risks.

Forward and Backward Directions

How do forward selection and backward elimination differ in their starting feature sets, candidate changes, and direction of search?

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

Both methods evaluate every one-step candidate through the learning algorithm and choose the candidate predictor with the smallest risk.

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.

When does the search stop, and how does the stopping condition determine the final selected feature set?

Common Reasoning Mistakes

Common mistake
Starting backward elimination with an empty set
What it looks like
Treating backward elimination as though it first selected a feature and then added more
Why it fails
Backward elimination begins with the full feature set and shrinks it by testing removals.
Do this instead
Write the full set as the initial current set, then form one candidate for each possible one-feature removal.
Common mistake
Removing the first feature that seems unhelpful
What it looks like
Deleting a feature without evaluating the alternatives
Why it fails
The method considers every feature in the current set and applies the learning algorithm to each resulting candidate subset.
Do this instead
Evaluate all one-feature removals and choose the candidate predictor with the smallest risk.
Common mistake
Confusing the removed feature with the chosen subset
What it looks like
Saying that the feature with the smallest risk is selected
Why it fails
Risk belongs to the candidate predictor formed after a removal.
Do this instead
Choose the candidate subset with the smallest risk; the feature absent from that subset is the feature removed.
Common mistake
Describing forward selection and backward elimination as the same search
What it looks like
Saying that both methods begin from the same feature set
Why it fails
Forward selection starts empty and tests additions, while backward elimination starts full and tests removals.
Do this instead
State both the starting point and the one-step modification when identifying the method.

Check Your Understanding

MEDIUM

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.

Your attempt (not saved)

The Greedy Pattern

1
Greedy selection couples feature selection with the learning algorithm by evaluating candidate subsets through their predictors.
2
Backward elimination starts with the full feature set and tests every one-feature removal.
3
The next backward-elimination set is the candidate whose predictor has the smallest risk.
4
Forward selection starts empty and tests one-feature additions, while backward elimination starts full and tests one-feature removals.
5
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.

Related concepts

More concepts starting with B