The part where I was surprised by this was in recognising that cv.split gets called in each evaluation... I thought we had ensured the cv split would be the same across evaluations.

but it is the same across evaluations... as long as the input data is the same, right?

For the return value, in my situation I agree I could get by with the current behavior. And only returning the result of the last call might make other implementations harder. Maybe we can even return both? @janvanrijn you've been building custom SearchCV objects, what do you think about this?

@jnothman thinking more about whether returning the results from all the calls to evaluate_candidate or just the last one:

• returning only the last one makes it a bit hard to reconstruct all of the results in the custom _run_search. I personally don't need it for successive halving, but other implementations may.
• returning results from all the calls makes it possible to return this dict in run_search: that would allow to remove this nonlocal variable which I would think is a good thing. However, this forces the results dict to be ordered, else there is no way to know which are the results of the last call to evaluate_results in run_search. If the dict is not ordered, I cannot implement the successive halving search.

WDYT?

Another solution we discussed with @amueller would be to pass another parameter info: evaluate_candidate(candidates, X, y, info=None)

info would be a dict whose keys would be transformed into columns in cv_results. This way in SuccessiveHalving I could pass which candidates correspond to which iteration, and find the best candidate accordingly.

I pushed 80963f3 and will write tests/checks if you're OK with this design?

I've not really got why info goes into the results...? I haven't understood how this solves the problem of selecting samples. Maybe it should be called more_results or something. Also, it might be a good idea to generally include the evaluation number in results where multiple evaluations are performed...

Also should this PR just go ahead and introduce a HalvingSearchCV?

I've not really got why info goes into the results

It goes into the results dict so that in HalvingSearchCV I can properly overload refit to only keep the best candidates out of the last iteration (i.e. the last call to evaluate). And I agree more_results is a better name.

I haven't understood how this solves the problem of selecting samples

It is unrelated to the addition of X and y to evaluate, if that's what you mean.

Also should this PR just go ahead and introduce a HalvingSearchCV?

I'm currently implementing HalvingSearchCV in another repo and see how it goes but yes I'm planning to submit a PR eventually.

Yes, I have modified my implementation of SuccessiveHalving like so:

...
            info = {'iter': [iter_i] * n_candidates,
                    'n_samples': [n_samples_iter] * n_candidates}
            out = evaluate_candidates(candidate_params, X_iter, y_iter,
                                      info=info)

...

Passing n_samples is not really needed here.

Now in results I have a new column indicating the iteration (i.e. when evaluate was called), and the number of samples used at this iteration

@jnothman with the current version of this PR, here is how we can implement SuccessiveHalving:

    def _run_search(self, evaluate_candidates, X, y):
        rng = check_random_state(self.random_state)

        candidate_params = list(self._generate_candidate_params())
        n_iterations = int(ceil(log2(len(candidate_params))))
        n_samples_total = X.shape[0]

        for iter_i in range(n_iterations):
            # randomly sample training samples
            n_candidates = len(candidate_params)
            n_samples_iter = floor(n_samples_total /
                                   (n_candidates * n_iterations))
            indices = rng.choice(n_samples_total, n_samples_iter,
                                 replace=False)
            X_iter, y_iter = X[indices], y[indices]

            more_results= {'iter': [iter_i] * n_candidates,
                           'n_samples': [n_samples_iter] * n_candidates}
            out = evaluate_candidates(candidate_params, X_iter, y_iter,
                                      more_results=more_results)

            # Select the best half of the candidates for the next iteration
            # We need to filter out candidates from the previous iterations
            n_candidates_to_keep = ceil(n_candidates / 2)
            best_candidates_indices = np.argsort(out['mean_test_score'])[::-1]
            best_candidates_indices = [i for i in best_candidates_indices
                                       if out['iter'][i] == iter_i]
            best_candidates_indices = \
                best_candidates_indices[:n_candidates_to_keep]
            candidate_params = [out['params'][i]
                                for i in best_candidates_indices]

        assert len(candidate_params) == n_candidates_to_keep == 1

def _refit_callable(results):
    # Custom refit callable to return the index of the best candidate. We want
    # the best candidate out of the last iteration. By default BaseSearchCV
    # would return the best candidate out of all iterations.

    last_iter = np.max(results['iter'])
    sorted_indices = np.argsort(results['mean_test_score'])[::-1]
    best_index = next(i for i in sorted_indices
                      if results['iter'][i] == last_iter)
    return best_index

Example of a dataframe, originally with n_samples = 1000:

The proposed design makes it easy to implement SuccessiveHalving and will allow any sort of other search estimators. If you're OK with the design I'll start to write tests and checks

@jnothman shall we discuss this during the sprint?

I'm in favor of adding SuccessiveHalvingCV btw. I'm happy to put it into experimental if we decided we want that module.

We agreed with Joel during the sprint that ideally only the CV object could be passed, instead of passing X and y. We can do the subsampling inside the CV.
I'll get to it soon and will report back.

And yes I think it could be a good fit for the experimental module

@jnothman , I've been trying to only pass cv instead of X, y.

We still have to pass cv into both _run_search and evaluate_candidates. We cannot avoid passing cv into _run_search: using something like cv = check_cv(self.cv) in _run_search is not possible since we need y to stratify.

So basically this only replaces X and y with cv everywhere. Do you still think it's worth it?

What I mean is that currently in fit, the cv object is set as such:

cv = check_cv(self.cv, y, classifier=is_classifier(estimator))

We can't write the same thing in _run_search unless we pass y. So the more natural way is just to pass cv to _run_search.

I don't think that's much better than passing X and y.

Hmm maybe passing indices is a nice alternative since unlike X and y, indices can have default values (None).

I think we should pass both row indices and column indices. This way we could also implement feature subsampling: in successive halving the budget can also be the number of features.

I'm not sure I entirely understand what you said before about joblib being able to use a numpy memmap. It seems to me that the memmapping only happens over a single call to Parallel, so multiple calls to evaluate_candidates can't leverage the same memmapping anyway, right?

Could you please expand on prenpending SuccessiveHalvingResampler? I'm not following

• I've implemented SH by passing indices to evaluate_candidates instead of X and y. It works fine, but doesn't make the code simpler IMO. It requires changing evaluate_candidates like so:

  def evaluate_candidates(candidate_params, sample_indices=None):
    # ...
    if sample_indices is not None:
        X_, y_ = X[sample_indices], y[sample_indices]
    else:
        X_, y_ = X, y
    # ...
    # use X_ and y_ from now on, since using nonlocal isn't an option

  Also, we still need to pass X and y to _run_search anyway, else there is no way we can do the resampling.

  So passing X and y seems to be the most natural way here.

• It is also possible to remove the more_results parameter. But it is honestly quite helpful and makes SucessiveHalving code cleaner and less magic. In particular, @amueller came up with this nice plot that is only possible if there is an 'iter' column:

  res = pd.DataFrame(sh.cv_results_)
  res['params_str'] = res.params.apply(str)
  reshape = res.pivot(index='iter', columns='params_str', values='mean_test_score')
  reshape.plot(legend=False, alpha=.4, c='k')

Would you agree to keep the proposed changed as they are? If yes I'll start writing tests

Also It'd be useful to introduce a _check_input_parameters method. Right now input checking can only be done in _run_search. WDYT?

Also It'd be useful to introduce a _check_input_parameters method. Right now input checking can only be done in _run_search. WDYT?

well it can also be done in fit... why would it be better done in _run_search?

well it can also be done in fit... why would it be better done in _run_search?

I mean it would be nice to have a _check_input_parameters that would be called in fit, before _run_search.

Right now for successive halving I am forced to do the input checking in _run_search since this is the only method that I can override.

Because apart from _run_search, fit doesn't call any method that can be overridden. I don't want to override the whole fit method

Right, I was thinking of a hook that could be called anywhere in fit, but indeed for input validation this would make sense.

Could you please post a summary and what needs to be done here @NicolasHug ?

@adrinjalali This PR is actually superseded by #13900

I see, you said "This builds upon #13145, whose changes are required." on that PR, so I assumed you need this one first. Closing then.