Orthogonal Matching Pursuit
Greedy selection evaluates feature subsets through the learning algorithm rather than separating selection from learning.
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.
Start: The selected set is empty. The algorithm tests adding a, adding b, and adding c.
First 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.
Second 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.
Current 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.
Start: The current set is {a, b, c}. The algorithm tests removing a, removing b, and removing c.
First 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.
Second 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.
Current 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 |
Common Tracing Mistakes
Starting forward selection with the full feature set
Forward greedy selection begins with no selected features and grows the set through additions.
Fix:
Start with the empty set, test every one-feature addition, and add the feature whose candidate predictor has the smallest risk.Choosing the feature with the smallest individual risk without comparing candidate sets
The method evaluates candidate feature subsets through the learning algorithm at the current stage.
Fix:
Form every one-step candidate set and compare the risks of their candidate predictors.Treating backward elimination as the reverse order of forward selection
The two methods begin from different sets and evaluate different one-step candidates.
Fix:
For backward elimination, begin with the full set and independently compare each possible one-feature removal at the current stage.Assuming forward selection must choose every feature
Forward selection can stop at a predefined budget of k features or when the predictor is accurate enough.
Fix:
Check 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
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
- Greedy selection couples feature selection with the learning algorithm by evaluating candidate predictors directly.
- Forward selection starts with an empty set, tests one-feature additions, and keeps the addition with the smallest risk.
- Forward selection can stop at a feature budget or when the resulting predictor is accurate enough.
- Backward elimination starts with the full set, tests one-feature removals, and keeps the removal whose remaining predictor has the smallest risk.
- The methods differ in direction and starting point, but both choose the next set by comparing one-step candidate predictors through the learning algorithm.
Key Takeaways
- 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.