Repository: scikit-learn/scikit-learn
Pull request: ENH Adds n_features_to_select upper limit to SeqFeatureSelector
<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/main/CONTRIBUTING.md
-->

#### Reference Issues/PRs
Fixes #20137
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->


#### What does this implement/fix? Explain your changes.
Add `aborted_rate` parameter in SequentialFeatureSelector.
If aborted_rate is NOT None, Fitting is aborted if new_score is lower than old_score plus aborted_rate.

#### Any other comments?
I think it shoud make tests that aborted_rate is set.
but, I have no ideas for tests. please let me know if you have good ideas.

<!--
Please be aware that we are a loose team of volunteers so patience is
necessary; assistance handling other issues is very welcome. We value
all user contributions, no matter how minor they are. If we are slow to
review, either the pull request needs some benchmarking, tinkering,
convincing, etc. or more likely the reviewers are simply busy. In either
case, we ask for your understanding during the review process.
For more information, see our FAQ on this topic:
http://scikit-learn.org/dev/faq.html#why-is-my-pull-request-not-getting-any-attention.

Thanks for contributing!
-->


Problem statement:
sklearn.feature_selection.SequentialFeatureSelector  Select features as long as score gets better.
Dear Developers,

Currently one can give `sklearn.feature_selection.SequentialFeatureSelector`
parameter 'n_features_to_select'
to get desired number of features.

It would be desired, that instead of giving a fixed number of 'n_features_to_select' one could use it as an upper limit and select features only up to point where the score improves (so the number of selected features could be smaller than 'n_features_to_select').

Terveisin, Markus

Hints from issue discussion:
I agree. The problem is how to manage backward compat with the current behavior without introducing too many spurious deprecation warnings and too many new parameters...

@norbusan suggested the following strategy in a private conversation: add a new `tol` parameter as an absolute tolerance on the score change before and after including the new feature, with a default value of `None` that would keep the existing behavior. If not `None` (for instance `tol == 0.`, this value would be use to stop the loop earlier.

We will `_get_best_new_feature` return `(new_feature_idx, new_score)` instead of just `new_feature_idx`.


What is good with the solution above is:

- we introduce a minimal number of new parameter,
- the backward compat is preserved with no change in the default behavior

There are several things I find itchy with the solution proposed above:

- I find the `n_features_to_select` defaulting to `n_features // 2` potentially confusing when `tol=0.`, one would rather like `max_features=n_features` in this case.
- it would be nice to use automated selection based on score change (tol=0) by default in the future.

Maybe we could implement the following with an additional `max_features`:

- `SequentialFeatureSelector()` default is equivalent to `SequentialFeatureSelector(n_features_to_select=None, max_features=None, tol=None)` and implements the current behavior
- `SequentialFeatureSelector()` (both `n_features_to_select is None and max_features is None`) would raise a `FutureWarning` that in the future `tol=0` will be used instead of selecting half of the features by default. We could tell the use to set `tol=0` explicitly to silence the warning.
- `SequentialFeatureSelector(n_features_to_select=some_integer)` would always respect this (ignoring `tol` and `max_features`.
- `SequentialFeatureSelector(tol=0.)` would do the automatic selection, implicitly assuming `max_features=n_features`.
- `SequentialFeatureSelector(tol=0., max_features=some_integer)` would do the automatic selection up to that number of features.
- `SequentialFeatureSelector(tol=0., n_features_to_select=some_integer)` would raise `ValueError` with an informative error message
- `SequentialFeatureSelector(n_features_to_select=some_integer, max_features=some_integer_or_float)` would raise `ValueError` with an informative error message


Optionally we could make `max_features` also accept a float between 0 and 1 to select a percentage of `X_train.shape[1]` for convenience and consistency with `BaggingClassifier` and the like.


WDYT @NicolasHug and others?
Just another comment which I forgot from the initial request: 

It may be the case that adding one feature more will always improve score (not sure about this). So some sort of threshold how much the score must improve in order to continue adding features might be needed....
> It may be the case that adding one feature more will always improve score (not sure about this). So some sort of threshold how much the score must improve in order to continue adding features might be needed....

I agree, this is the purpose of the `tol` parameter I introduced above.
@ogrisel you mentioned `tol=0`, but wouldn't `tol=0` be equivalent to `tol=None`, i.e. equivalent to the current behaviour?

I'm not sure I properly understand this point:

>     it would be nice to use automated selection based on score change (tol=0) by default in the future.

Regarding this one:
>  I find the n_features_to_select defaulting to n_features // 2 potentially confusing when tol=0., one would rather like max_features=n_features in this case.

The current default for `n_features_to_select` is `None`. We can extend `None` to actually mean `n_features` when `tol != None`? That would still be backward compatible and that wouldn't be confusing as long as we properly document this in `tol`'s and `n_features_to_select`'s docstring.


Eitherway, this is a form of early stopping. I think I would prefer what I just proposed but if we're going to introduce more parameters, we might need to also introduce an `early_stopping` parameter to keep consistent with the rest of the code base.
`tol=0` would make it possible to switch to the new early stopping behavior while the default `tol=None` would keep the current behavior during the depreciation cycle.
> The current default for n_features_to_select is None. We can extend None to actually mean n_features when tol != None? That would still be backward compatible and that wouldn't be confusing as long as we properly document this in tol's and n_features_to_select's docstring.

That's an option. I think I like it.

The only remaining question would be: do we plan to enable the early stopping behavior by default in the future? (I think that would be nice). How do we handle the deprecation? 

- `tol="warn"` whose behavior would be equivalent to `tol=None` for now with a `FutureWarning` that mentions that in the future `tol=0.` will be the default;
- `tol=0` will be the future default value with early stopping enable as a result;
- `tol=eps` with `eps > 0` would also work for enabling early stopping with an increment gap;
- passing `tol=None` explicitly makes it possible to keep using the current behavior.
@NicolasHug do you agree with the plan above? If so we can implement it as part of  #20145.
Yes this sounds good.

An alternative that I slightly prefer would be to directly introduce `tol=0` and instead do the deprecation on `n_features_to_select`:

- set `n_features_to_select` to 'warn' indicating that `None` is deprecated in favor of 'auto'
- Switch the default to 'auto' in 2 versions and remove `None`.

The reason the default is currently None is for consistency with RFE, but 'auto' is a more accurate name. Since we have to deprecate something anyway, we might as well introduce a better name in the process.

I'm fine with either strategy anyway, so feel free to implement the one you like best.

Commit message: Update sklearn/feature_selection/_sequential.py

Co-authored-by: Thomas J. Fan <thomasjpfan@gmail.com>

Patch to review:
diff --git a/doc/whats_new/v1.0.rst b/doc/whats_new/v1.0.rst
index fa5d9c9a43850..7240940862af0 100644
--- a/doc/whats_new/v1.0.rst
+++ b/doc/whats_new/v1.0.rst
@@ -335,6 +335,14 @@ Changelog
   `sample_weight` passed by a user were overwritten during the fit.
   :pr:`20515` by :user:`Carsten Allefeld <allefeld>`.
 
+- |Feature| Added auto mode to :class:`feature_selection.SequentialFeatureSelection`.
+  If the argument `n_features_to_select` is `'auto'`, select features until
+  the score improvement does not exceed the argument `tol`.
+  The default value of `n_features_to_select` changed from `None` to `‘warn’` in 1.1
+  and will become `'auto'` in 1.3. `None` has been disabled. `'warn'` is deprecated
+  in 1.0 and will be disabled in 1.3.
+  :pr:`20145` by :user:`murata-yu`.
+
 :mod:`sklearn.inspection`
 .........................
 
diff --git a/sklearn/feature_selection/_sequential.py b/sklearn/feature_selection/_sequential.py
index 19958ce759c76..e608d5584abef 100644
--- a/sklearn/feature_selection/_sequential.py
+++ b/sklearn/feature_selection/_sequential.py
@@ -5,6 +5,8 @@
 
 import numpy as np
 
+import warnings
+
 from ._base import SelectorMixin
 from ..base import BaseEstimator, MetaEstimatorMixin, clone
 from ..utils._tags import _safe_tags
@@ -29,11 +31,33 @@ class SequentialFeatureSelector(SelectorMixin, MetaEstimatorMixin, BaseEstimator
     estimator : estimator instance
         An unfitted estimator.
 
-    n_features_to_select : int or float, default=None
-        The number of features to select. If `None`, half of the features are
-        selected. If integer, the parameter is the absolute number of features
-        to select. If float between 0 and 1, it is the fraction of features to
-        select.
+    n_features_to_select : "auto", int or float, default='warn'
+        If `"auto"`, the behaviour depends on the `tol` parameter:
+
+        - if `tol` is not `None`, then features are selected until the score
+          improvement does not exceed `tol`.
+        - otherwise, half of the features are selected.
+
+        If integer, the parameter is the absolute number of features to select.
+        If float between 0 and 1, it is the fraction of features to select.
+
+        .. versionadded:: 1.1
+           The option `"auto"` was added in version 1.1.
+
+        .. deprecated:: 1.1
+           The default changed from `None` to `"warn"` in 1.1 and will become
+           `"auto"` in 1.3. `None` has been disabled. `"warn"` is deprecated
+           in 1.1 and will be disabled in 1.3. To keep the same behaviour
+           as with `None`, you should manually set `n_features_to_select="auto"`
+           and set `tol=None`.
+
+    tol : float, default=None
+        If the score is not incremented by at least `tol` between two
+        consecutive feature additions or removals, stop adding or removing even
+        if `n_features_to_select` has not been reached. `tol` is enabled only
+        when `n_features_to_select` is `"auto"`.
+
+        .. versionadded:: 1.1
 
     direction : {'forward', 'backward'}, default='forward'
         Whether to perform forward selection or backward selection.
@@ -116,7 +140,8 @@ def __init__(
         self,
         estimator,
         *,
-        n_features_to_select=None,
+        n_features_to_select="warn",
+        tol=None,
         direction="forward",
         scoring=None,
         cv=5,
@@ -125,6 +150,7 @@ def __init__(
 
         self.estimator = estimator
         self.n_features_to_select = n_features_to_select
+        self.tol = tol
         self.direction = direction
         self.scoring = scoring
         self.cv = cv
@@ -144,6 +170,20 @@ def fit(self, X, y):
         -------
         self : object
         """
+        # FIXME: to be removed in 1.2
+        if self.n_features_to_select in ("warn", None):
+            # for backwards compability
+            warnings.warn(
+                "Leaving `n_features_to_select` to "
+                "None is deprecated in 1.0 and will become 'auto' "
+                "in 1.2. To keep the same behaviour as with None "
+                "(i.e. select half of the features) and avoid "
+                "this warning, you should manually set "
+                "`n_features_to_select='auto'` and set tol=None "
+                "when creating an instance.",
+                FutureWarning,
+            )
+
         tags = self._get_tags()
         X, y = self._validate_data(
             X,
@@ -155,16 +195,22 @@ def fit(self, X, y):
         )
         n_features = X.shape[1]
 
+        # FIXME: to be fixed in 1.3
         error_msg = (
-            "n_features_to_select must be either None, an "
-            "integer in [1, n_features - 1] "
+            "n_features_to_select must be either 'auto', 'warn', "
+            "None, an integer in [1, n_features - 1] "
             "representing the absolute "
             "number of features, or a float in (0, 1] "
             "representing a percentage of features to "
             f"select. Got {self.n_features_to_select}"
         )
-        if self.n_features_to_select is None:
-            self.n_features_to_select_ = n_features // 2
+        if self.n_features_to_select in ("auto", "warn", None):
+            if self.tol is not None:
+                # With auto feature selection, `n_features_to_select_` will be updated
+                # to `support_.sum()` after features are selected.
+                self.n_features_to_select_ = n_features - 1
+            else:
+                self.n_features_to_select_ = n_features // 2
         elif isinstance(self.n_features_to_select, numbers.Integral):
             if not 0 < self.n_features_to_select < n_features:
                 raise ValueError(error_msg)
@@ -190,25 +236,36 @@ def fit(self, X, y):
         current_mask = np.zeros(shape=n_features, dtype=bool)
         n_iterations = (
             self.n_features_to_select_
-            if self.direction == "forward"
+            if self.n_features_to_select == "auto" or self.direction == "forward"
             else n_features - self.n_features_to_select_
         )
+
+        old_score = -np.inf
+        is_auto_select = self.tol is not None and self.n_features_to_select == "auto"
         for _ in range(n_iterations):
-            new_feature_idx = self._get_best_new_feature(
+            new_feature_idx, new_score = self._get_best_new_feature_score(
                 cloned_estimator, X, y, current_mask
             )
+            if is_auto_select and ((new_score - old_score) < self.tol):
+                break
+
+            old_score = new_score
             current_mask[new_feature_idx] = True
 
         if self.direction == "backward":
             current_mask = ~current_mask
+
         self.support_ = current_mask
+        self.n_features_to_select_ = self.support_.sum()
 
         return self
 
-    def _get_best_new_feature(self, estimator, X, y, current_mask):
-        # Return the best new feature to add to the current_mask, i.e. return
-        # the best new feature to add (resp. remove) when doing forward
-        # selection (resp. backward selection)
+    def _get_best_new_feature_score(self, estimator, X, y, current_mask):
+        # Return the best new feature and its score to add to the current_mask,
+        # i.e. return the best new feature and its score to add (resp. remove)
+        # when doing forward selection (resp. backward selection).
+        # Feature will be added if the current score and past score are greater
+        # than tol when n_feature is auto,
         candidate_feature_indices = np.flatnonzero(~current_mask)
         scores = {}
         for feature_idx in candidate_feature_indices:
@@ -225,7 +282,8 @@ def _get_best_new_feature(self, estimator, X, y, current_mask):
                 scoring=self.scoring,
                 n_jobs=self.n_jobs,
             ).mean()
-        return max(scores, key=lambda feature_idx: scores[feature_idx])
+        new_feature_idx = max(scores, key=lambda feature_idx: scores[feature_idx])
+        return new_feature_idx, scores[new_feature_idx]
 
     def _get_support_mask(self):
         check_is_fitted(self)
diff --git a/sklearn/feature_selection/tests/test_sequential.py b/sklearn/feature_selection/tests/test_sequential.py
index 817bbec09fd94..21d1e00a9436f 100644
--- a/sklearn/feature_selection/tests/test_sequential.py
+++ b/sklearn/feature_selection/tests/test_sequential.py
@@ -9,6 +9,7 @@
 from sklearn.datasets import make_regression
 from sklearn.linear_model import LinearRegression
 from sklearn.ensemble import HistGradientBoostingRegressor
+from sklearn.model_selection import cross_val_score
 
 
 @pytest.mark.parametrize("n_features_to_select", (0, 5, 0.0, -1, 1.1))
@@ -17,23 +18,27 @@ def test_bad_n_features_to_select(n_features_to_select):
     sfs = SequentialFeatureSelector(
         LinearRegression(), n_features_to_select=n_features_to_select
     )
-    with pytest.raises(ValueError, match="must be either None"):
+    with pytest.raises(ValueError, match="must be either 'auto'"):
         sfs.fit(X, y)
 
 
 def test_bad_direction():
     X, y = make_regression(n_features=5)
-    sfs = SequentialFeatureSelector(LinearRegression(), direction="bad")
+    sfs = SequentialFeatureSelector(
+        LinearRegression(), n_features_to_select="auto", direction="bad"
+    )
     with pytest.raises(ValueError, match="must be either 'forward' or"):
         sfs.fit(X, y)
 
 
+@pytest.mark.filterwarnings("ignore:Leaving `n_features_to_select` to ")
 @pytest.mark.parametrize("direction", ("forward", "backward"))
-@pytest.mark.parametrize("n_features_to_select", (1, 5, 9, None))
+@pytest.mark.parametrize("n_features_to_select", (1, 5, 9, "auto", None))
 def test_n_features_to_select(direction, n_features_to_select):
     # Make sure n_features_to_select is respected
 
-    X, y = make_regression(n_features=10)
+    n_features = 10
+    X, y = make_regression(n_features=n_features, random_state=0)
     sfs = SequentialFeatureSelector(
         LinearRegression(),
         n_features_to_select=n_features_to_select,
@@ -41,13 +46,103 @@ def test_n_features_to_select(direction, n_features_to_select):
         cv=2,
     )
     sfs.fit(X, y)
-    if n_features_to_select is None:
-        n_features_to_select = 5  # n_features // 2
+
+    if n_features_to_select in ("auto", None):
+        n_features_to_select = n_features // 2
+
     assert sfs.get_support(indices=True).shape[0] == n_features_to_select
     assert sfs.n_features_to_select_ == n_features_to_select
     assert sfs.transform(X).shape[1] == n_features_to_select
 
 
+@pytest.mark.parametrize("direction", ("forward", "backward"))
+def test_n_features_to_select_auto(direction):
+    """Check the behaviour of `n_features_to_select="auto"` with different
+    values for the parameter `tol`.
+    """
+
+    n_features = 10
+    tol = 1e-3
+    X, y = make_regression(n_features=n_features, random_state=0)
+    sfs = SequentialFeatureSelector(
+        LinearRegression(),
+        n_features_to_select="auto",
+        tol=tol,
+        direction=direction,
+        cv=2,
+    )
+    sfs.fit(X, y)
+
+    max_features_to_select = n_features - 1
+
+    assert sfs.get_support(indices=True).shape[0] <= max_features_to_select
+    assert sfs.n_features_to_select_ <= max_features_to_select
+    assert sfs.transform(X).shape[1] <= max_features_to_select
+    assert sfs.get_support(indices=True).shape[0] == sfs.n_features_to_select_
+
+
+@pytest.mark.parametrize("direction", ("forward", "backward"))
+def test_n_features_to_select_stopping_criterion(direction):
+    """Check the behaviour stopping criterion for feature selection
+    depending on the values of `n_features_to_select` and `tol`.
+
+    When `direction` is `'forward'`, select a new features at random
+    among those not currently selected in selector.support_,
+    build a new version of the data that includes all the features
+    in selector.support_ + this newly selected feature.
+    And check that the cross-validation score of the model trained on
+    this new dataset variant is lower than the model with
+    the selected forward selected features or at least does not improve
+    by more than the tol margin.
+
+    When `direction` is `'backward'`, instead of adding a new feature
+    to selector.support_, try to remove one of those selected features at random
+    And check that the cross-validation score is either decreasing or
+    not improving by more than the tol margin.
+    """
+
+    X, y = make_regression(n_features=50, n_informative=10, random_state=0)
+
+    tol = 1e-3
+
+    sfs = SequentialFeatureSelector(
+        LinearRegression(),
+        n_features_to_select="auto",
+        tol=tol,
+        direction=direction,
+        cv=2,
+    )
+    sfs.fit(X, y)
+    selected_X = sfs.transform(X)
+
+    rng = np.random.RandomState(0)
+
+    added_candidates = list(set(range(X.shape[1])) - set(sfs.get_support(indices=True)))
+    added_X = np.hstack(
+        [
+            selected_X,
+            (X[:, rng.choice(added_candidates)])[:, np.newaxis],
+        ]
+    )
+
+    removed_candidate = rng.choice(list(range(sfs.n_features_to_select_)))
+    removed_X = np.delete(selected_X, removed_candidate, axis=1)
+
+    plain_cv_score = cross_val_score(LinearRegression(), X, y, cv=2).mean()
+    sfs_cv_score = cross_val_score(LinearRegression(), selected_X, y, cv=2).mean()
+    added_cv_score = cross_val_score(LinearRegression(), added_X, y, cv=2).mean()
+    removed_cv_score = cross_val_score(LinearRegression(), removed_X, y, cv=2).mean()
+
+    assert sfs_cv_score >= plain_cv_score
+
+    if direction == "forward":
+        assert (sfs_cv_score - added_cv_score) <= tol
+        assert (sfs_cv_score - removed_cv_score) >= tol
+    else:
+        assert (added_cv_score - sfs_cv_score) <= tol
+        assert (removed_cv_score - sfs_cv_score) <= tol
+
+
 @pytest.mark.parametrize("direction", ("forward", "backward"))
 @pytest.mark.parametrize(
     "n_features_to_select, expected",
@@ -55,7 +150,7 @@ def test_n_features_to_select(direction, n_features_to_select):
         (0.1, 1),
         (1.0, 10),
         (0.5, 5),
-        (None, 5),  # just to make sure .5 is equivalent to passing None
+        (None, 5),
     ),
 )
 def test_n_features_to_select_float(direction, n_features_to_select, expected):
@@ -100,12 +195,17 @@ def test_sanity(seed, direction, n_features_to_select, expected_selected_feature
     assert_array_equal(sfs.get_support(indices=True), expected_selected_features)
 
 
-def test_sparse_support():
+# TODO: Remove test for n_features_to_select=None in 1.3
+@pytest.mark.filterwarnings("ignore:Leaving `n_features_to_select` to ")
+@pytest.mark.parametrize("n_features_to_select", ["auto", None])
+def test_sparse_support(n_features_to_select):
     # Make sure sparse data is supported
 
     X, y = make_regression(n_features=10)
     X = scipy.sparse.csr_matrix(X)
-    sfs = SequentialFeatureSelector(LinearRegression(), cv=2)
+    sfs = SequentialFeatureSelector(
+        LinearRegression(), n_features_to_select=n_features_to_select, cv=2
+    )
     sfs.fit(X, y)
     sfs.transform(X)
 
@@ -118,13 +218,17 @@ def test_nan_support():
     X, y = make_regression(n_samples, n_features, random_state=0)
     nan_mask = rng.randint(0, 2, size=(n_samples, n_features), dtype=bool)
     X[nan_mask] = np.nan
-    sfs = SequentialFeatureSelector(HistGradientBoostingRegressor(), cv=2)
+    sfs = SequentialFeatureSelector(
+        HistGradientBoostingRegressor(), n_features_to_select="auto", cv=2
+    )
     sfs.fit(X, y)
     sfs.transform(X)
 
     with pytest.raises(ValueError, match="Input contains NaN"):
         # LinearRegression does not support nans
-        SequentialFeatureSelector(LinearRegression(), cv=2).fit(X, y)
+        SequentialFeatureSelector(
+            LinearRegression(), n_features_to_select="auto", cv=2
+        ).fit(X, y)
 
 
 def test_pipeline_support():
@@ -136,12 +240,25 @@ def test_pipeline_support():
 
     # pipeline in SFS
     pipe = make_pipeline(StandardScaler(), LinearRegression())
-    sfs = SequentialFeatureSelector(pipe, cv=2)
+    sfs = SequentialFeatureSelector(pipe, n_features_to_select="auto", cv=2)
     sfs.fit(X, y)
     sfs.transform(X)
 
     # SFS in pipeline
-    sfs = SequentialFeatureSelector(LinearRegression(), cv=2)
+    sfs = SequentialFeatureSelector(
+        LinearRegression(), n_features_to_select="auto", cv=2
+    )
     pipe = make_pipeline(StandardScaler(), sfs)
     pipe.fit(X, y)
     pipe.transform(X)
+
+
+# FIXME : to be removed in 1.3
+def test_raise_deprecation_warning():
+    """Check that we raise a FutureWarning with `n_features_to_select`."""
+    n_samples, n_features = 50, 3
+    X, y = make_regression(n_samples, n_features, random_state=0)
+
+    warn_msg = "Leaving `n_features_to_select` to None is deprecated"
+    with pytest.warns(FutureWarning, match=warn_msg):
+        SequentialFeatureSelector(LinearRegression()).fit(X, y)
diff --git a/sklearn/tests/test_docstring_parameters.py b/sklearn/tests/test_docstring_parameters.py
index 8f6326f62e4aa..1a8fd93045668 100644
--- a/sklearn/tests/test_docstring_parameters.py
+++ b/sklearn/tests/test_docstring_parameters.py
@@ -261,6 +261,10 @@ def test_fit_docstring_attributes(name, Estimator):
     if Estimator.__name__ == "TSNE":
         est.set_params(learning_rate=200.0, init="random")
 
+    # FIXME: TO BE REMOVED for 1.3 (avoid FutureWarning)
+    if Estimator.__name__ == "SequentialFeatureSelector":
+        est.set_params(n_features_to_select="auto")
+
     # For PLS, TODO remove in 1.1
     skipped_attributes = {"x_scores_", "y_scores_"}
 


Code review comments:
diff_hunk: @@ -335,6 +335,14 @@ Changelog
   `sample_weight` passed by a user were overwritten during the fit.
   :pr:`20515` by :user:`Carsten Allefeld <allefeld>`.
 
+- |Feature| Added auto mode to :class:`feature_selection.SequentialFeatureSelection`.
+  If the argument `n_features_to_select` is `'auto'`, select features until
+  the score improvement does not exceed the argument `tol`.
+  The default value of `n_features_to_select` changed from `None` to `‘warn’` in 1.1
+  and will become `'auto'` in 1.3. `None` has been disabled. `'warn'` is deprecated
+  in 1.0 and will be disabled in 1.3.
path: doc/whats_new/v1.0.rst
text: @user1:
```suggestion
  and will become `'auto'` in 1.3. `None` and `'warn'` will be removed in 1.3.
```

diff_hunk: @@ -29,11 +31,33 @@ class SequentialFeatureSelector(SelectorMixin, MetaEstimatorMixin, BaseEstimator
     estimator : estimator instance
         An unfitted estimator.
 
-    n_features_to_select : int or float, default=None
-        The number of features to select. If `None`, half of the features are
-        selected. If integer, the parameter is the absolute number of features
-        to select. If float between 0 and 1, it is the fraction of features to
-        select.
+    n_features_to_select : "auto", int or float, default='warn'
+        If `"auto"`, the behaviour depends on the `tol` parameter:
+
+        - if `tol` is not `None`, then features are selected until the score
+          improvement does not exceed `tol`.
+        - otherwise, half of the features are selected.
+
+        If integer, the parameter is the absolute number of features to select.
+        If float between 0 and 1, it is the fraction of features to select.
+
+        .. versionadded:: 1.1
+           The option `"auto"` was added in version 1.1.
+
+        .. deprecated:: 1.1
+           The default changed from `None` to `"warn"` in 1.1 and will become
+           `"auto"` in 1.3. `None` has been disabled. `"warn"` is deprecated
+           in 1.1 and will be disabled in 1.3. To keep the same behaviour
+           as with `None`, you should manually set `n_features_to_select="auto"`
+           and set `tol=None`.
path: sklearn/feature_selection/_sequential.py
text: @user1:
```suggestion
           `"auto"` in 1.3. `None` and `'warn'` will be removed in 1.3.
           To keep the same behaviour as `None`, set 
           `n_features_to_select="auto" and `tol=None`.
```

diff_hunk: @@ -155,16 +195,22 @@ def fit(self, X, y):
         )
         n_features = X.shape[1]
 
+        # FIXME: to be fixed in 1.3
         error_msg = (
-            "n_features_to_select must be either None, an "
-            "integer in [1, n_features - 1] "
+            "n_features_to_select must be either 'auto', 'warn', "
+            "None, an integer in [1, n_features - 1] "
             "representing the absolute "
             "number of features, or a float in (0, 1] "
             "representing a percentage of features to "
             f"select. Got {self.n_features_to_select}"
         )
-        if self.n_features_to_select is None:
-            self.n_features_to_select_ = n_features // 2
+        if self.n_features_to_select in ("auto", "warn", None):
path: sklearn/feature_selection/_sequential.py
text: @user1:
In the edge case where `tol is not None` and `n_features_to_select=None`, we need to include the same code path as before:

```python
if self.n_features_to_select in ("warn", None):
    if self.tol is not None:
		raise ValueError("tol is only enabled if `n_features_to_select='auto'`")
    self.n_features_to_select_ = n_features // 2
elif self.n_features_to_select == "auto":
```

@author:
fixed to be addressed until 1.3 https://github.com/scikit-learn/scikit-learn/pull/20145/commits/1ba4b4cbd2f5a7d0556114d06e734821ff70080c

fixed to include the same code path https://github.com/scikit-learn/scikit-learn/pull/20145/commits/23f722c686af450b8664ae53cdf59a7fed76d396