scikit-learn/scikit-learn — pull request #2000 by jnothman (2013-05-26 06:28:17+00:00)
Title: [WIP] Estimator.iter_fits for efficient parameter search

This implements an approach to generalised cross validation (#1626) by allowing each estimator to control its fitting over a sequence of parameter settings. `iter_fits` returns an iterator (usually a generator) over parameters and models fit with those parameters.

This PR is to open comment, rather than to finalize the implementation in the near term.

The default implementation allows an estimator to specify parameters which when changed do not require `fit` to be called again. Estimators where it is possible to warm start from the model attributes learnt with the previous parameters may utilise that fact; in particular, this approach emphasises that the same data is being used, where multiple calls to `fit` does not. A `Pipeline` resolves its ordering through a depth-first traversal of the parameters affecting each pipeline step (ordered by that step's estimator), and the use of generators means the output of `transform` from higher levels is retained in the stack, which adds a memory cost (it may be possible to optionally reduce this cost later) but cuts a lot of repeated work. The model iterator approach means regularization paths can be easily incorporated if rewritten as generators.

[Grid search](https://gist.github.com/jnothman/5624440) (cv=3, n_jobs=1) over a simple pipeline of (StandardScaler, SelectKBest, ElasticNet) ran in 67% of the baseline time (repeated calls to `Pipeline.fit`) using this implementation, with the following call counts:

| Method | calls@master | calls@iter_fits |
|----------------------------|--------------|-----------------|
|`StandardScaler.fit` |241 |7 |
|`StandardScaler.transform` |481 |247 |
|`SelectKBest.fit` |241 |7 |
|`SelectKBest.transform` |481 |265 |
|`ElasticNet.fit` |241 |241 |
(Note: many calls to `transform` are at predict time, which is not affected by this change.)

Caveats and comments:
* `iter_fits` will often overwrite attributes of the same object in each iteration. It's therefore necessary to *copy* any data off the models or call any methods *while iterating*. This may make it a dangerous method for public use, and it may be worthwhile to require that each iteration yields a clone of the estimator, at some added expense and complication.
* a common pattern for implementing `iter_fits` is to group the list of parameter settings by the values of some "higher-order" parameters (those requiring substantial work to be done at each change) within which groups lower-order parameters are iterated. Thus:
* the parameter settings need to be grouped by each estimator, making the dict form in which parameters are transmitted cumbersome
* parameter values may be objects that are unorderable and/or unhashable and/or un-boolean-comparable (`ndarray` is all of these), making the grouping operation and other generic parameter equality evaluations not trivial to code
* in many cases it should be possible instead to order merely on the basis of parameter names and some simple ordering rules for each parameter, resulting in less repeated reordering work (and on the scale of number of parameter names, not number of parameter value combinations). Setting a pipeline step (#1769) presents a case where parameter names are not sufficient information for an estimator to return an ordering.
* user-intended candidate ordering, and the manner of their generation, is ignored. This makes the solution generic, but it's harder to harness the properties of a grid, for example. The reordering also means parameter search may return a different best candidate with the same top score.
* since the ordering is performed at `fit` time, each fold of a cv-search process may operate in parallel. To recombine the outputs, it is easiest if the reordering is deterministic, and therefore the same across all folds. Also because the reordering is coupled with fitting, parallelisation beyond one-process-per-fold may require arbitrary splits in the candidate sequence.