Concepts / Forward Greedy Selection

Forward Greedy Selection

Greedy selection evaluates feature subsets through the learning algorithm rather than separating selection from learning.

  • Programming

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.

applyproducescompareCandidate subsetI plus one featureLearning algorithmBuild predictorCandidate riskEvaluate predictorNext featureSmallest risk
How do candidate feature subsets move through the learning algorithm, get evaluated, and determine the next selected feature?

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.

test additionstest additionscontinue or stopEmpty setI = {}One featureAdd best candidateTwo featuresAdd best candidateSelected subsetStop by rule
What happens at each step as forward selection starts with no features, tests additions, and builds the selected feature set?

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.

Start: The selected set is empty. The candidates are the one-feature sets {A}, {B}, and {C}.

First 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.

Second 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.

Stopping 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.

add Aadd Badd CchooseCurrent set ISelected featuresI plus ACandidate risk 8I plus BSmallest riskI plus BCandidate risk 5I plus CCandidate risk 7
How are the current feature set, candidate one-feature additions, and their evaluation scores connected when choosing the next set?

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.

checkcheckcheckreachedsufficientno candidatesContinue selectionEvaluate additionsFeature budget kTarget reachedStopReturn current setAccurate predictorAccuracy sufficientAll features selectedNo additions remain
What changes in the selection process when no candidate improves the score, the target size is reached, or all features have been considered?

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.

test removalschoose smallest riskcontinue or stopFull setI contains every featureOne removalTest I without iSmaller setRemove best candidateSelected subsetStop by rule
What happens as backward elimination starts with every feature and repeatedly removes the least useful feature?

A Hypothetical Backward-Elimination Trace

Start with the full set {A, B, C} and test which single-feature removal produces the smallest candidate risk.

Start: The current set is {A, B, C}. The removal candidates are {B, C}, {A, C}, and {A, B}.

Evaluate 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.

Update: 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.

growchoose smallest riskshrinkchoose smallest riskEmpty setForward startFull setBackward startAdd featureTest one-feature additionsRemove featureTest one-feature removalsSelected subsetGrow toward resultSelected subsetShrink toward result
How do forward selection and backward elimination differ in their starting sets, candidate changes, and direction of movement toward the final feature subset?
MethodStarting setCandidate changeNext choice
Forward selectionEmpty setAdd one feature not already selectedAddition whose predictor has the smallest risk
Backward eliminationFull feature setRemove one feature currently selectedRemoval whose resulting predictor has the smallest risk

Common Selection Mistakes

  • Treating feature selection as completely separate from learning.

    Greedy selection couples feature selection with the underlying learning algorithm.

    Fix: For every one-step candidate subset, apply the learning algorithm and compare the resulting risks.

  • Starting forward selection with the full feature set.

    Forward selection begins with no selected features and tests additions.

    Fix: Start with the empty set and consider each feature not already selected.

  • Assuming backward elimination adds features.

    Backward elimination begins with the full set and tests removals.

    Fix: For each feature in the current set, evaluate the set formed by removing that feature.

  • Continuing forward selection without a stopping rule.

    Forward selection can stop at a predefined budget of k features or when the resulting predictor is accurate enough.

    Fix: State the stopping rule before interpreting the final selected subset.

Practice the Trace

EASY

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.

Compare candidates: The candidate set {A, C} has the smaller risk.

Update: Forward selection chooses {A, C} as the next selected set.

Check 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

  1. Greedy selection lets the learning algorithm evaluate candidate feature subsets directly.
  2. Forward selection starts with an empty set, tests one-feature additions, and keeps the addition with the smallest candidate risk.
  3. Forward selection can stop at a predefined feature budget or when the resulting predictor is accurate enough.
  4. Backward elimination starts with the full set, tests one-feature removals, and removes the feature whose removal produces the smallest risk.
  5. The two methods share the same candidate-evaluation rule but differ in their starting sets and direction of movement.

Key Takeaways

  • 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.

Related Topics

  • Feature Selection
  • Learning Algorithms
  • Predictor Evaluation
  • Risk Minimization