Ran some time tests with and without presorting for GradientBoostingClassifier.

max_depth = 3

with presorting
spambase   0.91     0.11
Gaussian   0.853    8.51
mnist      0.837  191.26
covtypes   0.708  111.45

without presorting
spambase   0.91     0.14
Gaussian   0.853   20.29
mnist      0.837  263.88
covtypes   0.708  134.32

max_depth = 6

with presorting
spambase   0.925    0.29
Gaussian   0.911   22.29
mnist      0.912  718.27
covtypes   0.774  306.24

without presorting
spambase   0.926    0.28
Gaussian   0.911   38.73
mnist      0.913  549.19
covtypes   0.774  249.28

So it looks like some function of max_depth, n_samples, and n_features corresponds to training time. Do you think it's worth finding a good switch, or mentioning it in the docs and leaving it to users to determine if they want to presort or not?

So it looks like some function of max_depth, n_samples, and n_features corresponds to training time. Do you think it's worth finding a good switch, or mentioning it in the docs and leaving it to users to determine if they want to presort or not?

I would leave that to the user and only enable presort for boosting. Let's keep things simple :)

I have added unit tests for Gradient Boosting and Forests to ensure that presorting returns the same results as not using presorting. I have also added unit tests for Gradient Boosting testing sparse inputs, and ensuring that they give the same results as dense inputs. Please review when you have the time.

First thanks @jmschrei to give love to those codes. Here a few thoughts about this pull request.

I find great that you add sparsity support to gbrt. (Though I would have done that in another pr). As pointed by some people in the @PPRET pull request, it is needed to store the sparse X matrix in both csr and csc format to handle sparse matrix efficiently. It allows to avoid costly format conversions between the csr and the csc format.

I understand the need and the benefits to merge more of the logic between pre-sort best splitter and the best spliter. In this pr, it is proposed to interleave the codes with if else. If we go to more rationalization such as merging the random splitter and the sparse splitters, this approach might start leading to spaghetti code. What do you think of having inline methods which would be overriden by each concrete implementation? The advantage is that it would add code re-use with some semantics.

I am not fan of adding a presort parameter to the random forest estimators. Since that most (all?) people builds totally developed trees, it might not be used much and add some complexify in terms of usage and maintenance. In the gradient boosting case, I wouldn't allow the user to choose and switch presort or not depending on the matrix sparsity.

Thanks for the comments @arjoly.

To be clear, I haven't added in sparsity support for presorting. I added an option to turn presorting off for gradient boosting, and when you do, you get the same sparsity support that decision trees/random forests get. Thus not having a separate PR for it.

I can understand the concern about spaghetti code. Presorting and best splitting are so similar that merging them makes much more sense than any other merger, because it's not an algorithmic difference in how the split is calculated, just in how Xf is prepared for the split. This requires only the addition of 31 lines of code (15 of which are initializing and declaring variables) versus having an entirely new object and ~250 lines of repeated code.

Having inline methods may be the correct way to merge more code in the future. I was thinking about factorizing the node_split method into several methods, such as "sort_array", "sort_array_w_presorting", and "sort_sparse_array", which would return Xf. Then have a "best_split" method which takes in Xf and finds the best split, or a "random_split" method which finds the best random split. Lastly, a "partition_samples" method which is shared. I haven't fully formed the idea yet, but if you have ideas I'd love to see them.

I like the addition of presorting for these other methods, but am not tied to it--it seems like a "why not" case. It's easy to do add in, the default behaviour is not to use it so users won't notice a difference unless they know what they're doing, and should it become difficult to maintain it can be easily removed. Maybe @glouppe will have an opinion.

I am not fan of adding a presort parameter to the random forest estimators. Since that most (all?) people builds totally developed trees, it might not be used much and add some complexify in terms of usage and maintenance. In the gradient boosting case, I wouldn't allow the user to choose and switch presort or not depending on the matrix sparsity.

It is true that presorting is not very useful outside of GBRT. +1 for not adding this parameter in forests and keep the public API as it is.

Presorting has been removed as an option for tests. Code, unit tests, and documentation have been updated to reflect this.

You should test for presorting in test_tree.py. You can do that I believe by changing

"Presort-DecisionTreeClassifier": partial(DecisionTreeClassifier, splitter="presort-best"),

to

"Presort-DecisionTreeClassifier": partial(DecisionTreeClassifier, presort=True),

(and the same for the regressor)

Thanks for the review @glouppe! Good catch, I forgot to change that over. I've incorporated all your comments. It looks like a bunch of TSNE unit tests are failing. :(

Great, thanks for the changes! +1 for merge on my side.

@jmschrei It seems there are conflicts in your branch? (I imagine this comes from the what's new)

@arjoly Any more comments?

Yep, rebased this branch onto master.

I've addressed comments, added an 'auto' default option, and added some more unit tests. Since this PR is getting rather hefty now, I am going to submit another PR in the future applying the same style changes to _splitter.pyx as _criterion.pyx, instead of handling that here.

To grow a tree on sparse, you need the data to be in sparse csc format. However to make a prediction, you need a sparse csr data.This means that whenever you build a boosting models at each step you:
(1) convert the X matrix to csc if needed (2) build the tree (3) convert the X matrix to csr (4) predict with the current tree and (5) repeat (1) until we have done n_estimators. This transformation from csc and csr induce computational costs that should be avoided.

To grow a tree on sparse, you need the data to be in sparse csc format. However to make a prediction, you need a sparse csr data.This means that whenever you build a boosting models at each step you:
(1) convert the X matrix to csc if needed (2) build the tree (3) convert the X matrix to csr (4) predict with the current tree and (5) repeat (1) until we have done n_estimators. This transformation from csc and csr induce computational costs that should be avoided.

Got it. Apologies for the confusion.

Comments have been incorporated. For sparse data, csc matrices are passed into fitting functions, and csr matrices are passed into prediction functions. Thanks @arjoly for the thorough review.

Any more comments @arjoly ? If not I believe we can merge this one.

I made a last round of review.

Comments have been into account, and commits have been squashed.

LGTM

thanks @jmschrei

🎺