Orthogonal Matching Pursuit
Orthogonal Matching Pursuit presents feature selection as part of the learning process: instead of choosing features independently and training later, the learning algorithm evaluates each candidate feature subset directly.
Selection Through Learning
Suppose a dataset contains many features, but the final predictor should use only a selected subset. Orthogonal Matching Pursuit presents feature selection as part of the learning process: instead of choosing features independently and training later, the learning algorithm evaluates each candidate feature subset directly. The best next change is the one whose candidate predictor has the smallest risk.
Orthogonal Matching Pursuit uses greedy selection to evaluate feature subsets through the learning algorithm. At each stage, it examines one-step candidate changes and chooses the candidate predictor with the smallest risk.
Forward Selection Trace
Forward greedy selection starts with an empty selected feature set. At a given stage, call the current selected set I. The method considers every feature that is not already in I. Each candidate is formed by adding one of those features to I. The learning algorithm evaluates every resulting candidate set, and the feature producing the smallest-risk candidate predictor is added to I.
Choosing Additions by Risk
Start with an empty selected set and consider features a, b, and c. The following candidate risks are illustrative values for this example.
- 1Start
The selected set is empty. The algorithm tests adding a, adding b, and adding c.
- 2First choice
Assume the candidate risks for {a}, {b}, and {c} are 8, 5, and 7. The candidate {b} has the smallest risk, so b is added.
- 3Second choice
The current set is now {b}. The algorithm tests {b, a} and {b, c}. If their risks are 4 and 6, it adds a because {b, a} has the smaller risk.
- 4Current result
After two forward steps, the selected set is {b, a}. The method has made each choice by evaluating one-feature additions through the learning algorithm.
The forward trace is empty set, then {b}, then {b, a}. The numerical risks are generated only to demonstrate the selection rule.
Forward Stopping Rules
Forward selection is not required to continue until every feature has been selected. It may stop when it reaches a predefined budget of k features. It may also stop earlier when the resulting predictor is accurate enough. The stopping rule therefore determines whether the process is limited by the desired number of features or by the desired predictor accuracy.
When tracing forward selection, record both the selected set and the stopping rule. A larger selected set is not automatically the goal: the process can be limited by a feature budget or ended once the predictor is accurate enough.
Backward Elimination Trace
Backward elimination begins with the full feature set rather than an empty set. If the current set is I, the method considers every feature in I as a possible removal. For each possible removal, it applies the learning algorithm to the remaining features. The feature whose removal produces the smallest-risk candidate predictor is removed next.
Choosing Removals by Risk
Start with the full feature set {a, b, c}. The following candidate risks are illustrative values for this example.
- 1Start
The current set is {a, b, c}. The algorithm tests removing a, removing b, and removing c.
- 2First removal
Assume the risks for {b, c}, {a, c}, and {a, b} are 9, 4, and 6. Removing b produces the smallest risk because the remaining set {a, c} has risk 4.
- 3Second removal
The current set is now {a, c}. The algorithm tests {c} and {a}. If their risks are 8 and 5, it removes c because the remaining set {a} has the smaller risk.
- 4Current result
After two backward steps, the remaining set is {a}. Each removal was selected by comparing the risks of the candidate predictors after one feature was removed.
The backward trace is {a, b, c}, then {a, c}, then {a}. The numerical risks are generated only to demonstrate the removal rule.
Two Directions of Greedy Change
| Aspect | Forward greedy selection | Backward elimination |
|---|---|---|
| Starting point | Empty selected feature set | Full feature set |
| Candidate change | Add one feature not already selected | Remove one feature currently selected |
| Learning evaluation | Apply the learning algorithm to every one-feature addition | Apply the learning algorithm to every one-feature removal |
| Next set | Candidate predictor with the smallest risk | Candidate predictor with the smallest risk |
Both methods use the learning algorithm to evaluate every one-step candidate; they differ in their starting point and direction of change.
Common Tracing Mistakes
Common mistake Starting forward selection with the full feature set
What it looks likeBeginning with {a, b, c} and removing features is a backward-elimination trace, not a forward-selection trace.
Why it failsForward greedy selection begins with no selected features and grows the set through additions.
Do this insteadStart with the empty set, test every one-feature addition, and add the feature whose candidate predictor has the smallest risk.
Common mistake Choosing the feature with the smallest individual risk without comparing candidate sets
What it looks likeSelecting a because it looks best alone, without evaluating the current set plus each possible addition.
Why it failsThe method evaluates candidate feature subsets through the learning algorithm at the current stage.
Do this insteadForm every one-step candidate set and compare the risks of their candidate predictors.
Common mistake Treating backward elimination as the reverse order of forward selection
What it looks likeAssuming that backward elimination must remove features in the exact reverse order that forward selection would add them.
Why it failsThe two methods begin from different sets and evaluate different one-step candidates.
Do this insteadFor backward elimination, begin with the full set and independently compare each possible one-feature removal at the current stage.
Common mistake Assuming forward selection must choose every feature
What it looks likeContinuing after the requested feature budget has been reached.
Why it failsForward selection can stop at a predefined budget of k features or when the predictor is accurate enough.
Do this insteadCheck the stopping rule after the relevant selection steps.
Practice the Next Move
A forward-selection process currently has the selected set {p}. The unselected features are q and r. The learning algorithm produces risk 6 for the candidate set {p, q} and risk 3 for {p, r}. Which feature is added next, and what is the new selected set? Then describe how the same decision would be approached by backward elimination if the current full set were {p, q, r}.
Hints
- Forward selection compares candidate additions to the current set.
- Choose the candidate predictor with the smaller risk.
- Backward elimination would compare the remaining sets produced by removing p, q, or r from the current set.
What do you think happens?
In the forward-selection practice scenario, which feature is added next?
Reveal answer
r
The candidate set {p, r} has risk 3, which is smaller than the risk 6 of {p, q}. Therefore r is added and the new selected set is {p, r}.
Key Takeaways
- 1Greedy selection couples feature selection with the learning algorithm by evaluating candidate predictors directly.
- 2Forward selection starts with an empty set, tests one-feature additions, and keeps the addition with the smallest risk.
- 3Forward selection can stop at a feature budget or when the resulting predictor is accurate enough.
- 4Backward elimination starts with the full set, tests one-feature removals, and keeps the removal whose remaining predictor has the smallest risk.
- 5The methods differ in direction and starting point, but both choose the next set by comparing one-step candidate predictors through the learning algorithm.
At a glance
- Orthogonal Matching Pursuit treats feature selection and learning as a coupled process.
- Forward greedy selection grows from an empty set by testing additions.
- Backward elimination shrinks the full set by testing removals.
- In both methods, the next change is selected by the candidate predictor with the smallest risk.
- Forward selection may stop at a feature budget or when predictor accuracy is sufficient.