Algorithms#
CRFE#
CRFE (constrained recursive feature elimination) is recursive feature elimination
(RFE) in which a CP-SAT solver decides which features to remove at each iteration,
subject to the constraints. Without constraints, CRFE is the standard RFE: at each
iteration the step least important features are removed, until the target
number of features is reached.
Elimination loop#
Let \(N\) the number of features, \(S\) be the set of retained features and \(k\) the number of features to select. Each iteration:
Fits a clone of the estimator on the columns in \(S\).
Computes the importance \(I_i\) of each retained feature, from
coef_orfeature_importances_, or fromimportance_getterfor each feature \(i =1,\ldots,N\). Attribute importances are squared, as in RFE.Sets the number of features to remove to \(r = \min(\text{step}, |S| - k)\).
Solves for the features to keep and removes the others from \(S\). The strategy below defines how the solver decides.
The loop stops when \(|S| = k\), when no removal is feasible, or when the
callback requests a stop. The solver keeps at least \(k\) features, as an
at-least-k constraint over all features. If n_features_to_select is None,
\(k = 1\).
At each iteration the solver maximizes the importance of the retained features:
subject to the constraints, at least \(k\) features retained, and
\(x_i = 0\) for every feature removed in an earlier iteration or in this one.
The offset \(\epsilon\) (importance_offset, default 1e-3) keeps
zero-importance features unless a constraint requires removing them.
Features removed in an earlier iteration stay removed. ranking_ follows RFE:
selected features have rank 1, and a feature removed earlier has a higher rank.
Strategy#
The strategy parameter is used only with constraints. It decides what
happens when removing the \(r\) least important retained features is
infeasible. Both strategies start from the same candidates: the \(r\) least
important retained features that are not blocked.
- Greedy
Adds all the candidates as hard constraints and solves once. If that is infeasible, the search stops with
INFEASIBLE, even if some candidates could be removed on their own.- Probing
Tests the candidates as one set, using assumptions on one literal per feature, so the model is unchanged during the test. If that is infeasible, it tests the features one by one, from least to most important, on top of the features already accepted in this iteration. A feature that can be removed is accepted. A feature that cannot is blocked for the rest of the run, because removals only accumulate. The search stops when \(r\) features are accepted or all the features have been tested, and the accepted features are then removed. A probe that reaches the time limit is skipped for this iteration and is not blocked. If no feature can be removed, the search stops with
INFEASIBLE.
Greedy |
Probing |
|
|---|---|---|
Features removed per iteration |
\(r\), or more if a constraint forces further removals |
Up to \(r\) |
Infeasible candidate set |
Stops the search |
Removes the features it can |
Solver calls per iteration |
One |
One if the candidate set is feasible; otherwise one per tested feature and one final solve |
Default |
No |
Yes |
Greedy can remove more than \(r\) features when a constraint forces it. For
example, OnlyEnforceIfConstraint with \(x_a \leq x_b\) forces the removal of
\(a\) when \(b\) is removed. Greedy is cheaper per iteration, but it stops
early when the full step is infeasible. Probing continues with fewer features
removed per iteration instead of stopping.
CRFECV#
CRFECV chooses the number of features by cross-validation, as in scikit-learn’s RFECV. Each fold runs CRFE on its training rows, with the same constraints and strategy, so everything above applies. The CV step adds these implications:
The model is built once per fold and once more for the final run, so the cost is about \(n_\text{folds} + 1\) CRFE runs.
Data-dependent constraints are computed on the training rows of each fold. For example, the correlations used by
MaxCorrelationConstraint.The full set of features is compared unless the constraints do not allow it, for example under a budget. Then it is excluded and CRFECV warns.
Within each fold, every size reached by the search is scored on the test rows. These held-out scores are what CRFECV compares. In CRFE, the score is only a training-data record.
Only sizes reached by all folds are compared. With constraints, a fold can stop early when infeasible, so the smallest sizes may not be compared.
The size with the highest mean held-out score is chosen. Ties go to fewer features, as in RFECV.
The final CRFE run on all the data stops at that size. Its selected features are not necessarily the features of any fold. If the chosen size is infeasible on the full data, the run stops at the last feasible size, as CRFE does.