{"action":"created","issue":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/5041","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/5041/labels{/name}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/5041/comments","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/5041/events","html_url":"https://github.com/scikit-learn/scikit-learn/pull/5041","id":97688031,"number":5041,"title":"[WIP] _tree.pyx rewrite","user":{"login":"jmschrei","id":3916816,"avatar_url":"https://avatars.githubusercontent.com/u/3916816?v=3","gravatar_id":"","url":"https://api.github.com/users/jmschrei","html_url":"https://github.com/jmschrei","followers_url":"https://api.github.com/users/jmschrei/followers","following_url":"https://api.github.com/users/jmschrei/following{/other_user}","gists_url":"https://api.github.com/users/jmschrei/gists{/gist_id}","starred_url":"https://api.github.com/users/jmschrei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jmschrei/subscriptions","organizations_url":"https://api.github.com/users/jmschrei/orgs","repos_url":"https://api.github.com/users/jmschrei/repos","events_url":"https://api.github.com/users/jmschrei/events{/privacy}","received_events_url":"https://api.github.com/users/jmschrei/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":19,"created_at":"2015-07-28T12:01:40Z","updated_at":"2015-07-31T09:25:08Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/5041","html_url":"https://github.com/scikit-learn/scikit-learn/pull/5041","diff_url":"https://github.com/scikit-learn/scikit-learn/pull/5041.diff","patch_url":"https://github.com/scikit-learn/scikit-learn/pull/5041.patch"},"body":"The following tasks must be completed:\r\n\r\n- [x] Propose new API to simplify Criterion, Splitter, and TreeBuilder methods\r\n- [x] Rewrite FriedmanMSE and MSE criterion to support caching speed ups\r\n- [x] New API (with speedups) works with GradientBoostingClassifier/Regressor\r\n- [x] Initial multi-threading proposal  \r\n- [ ] Entropy and Gini Criterion working\r\n- [ ] New API works with RandomForestClassifier/Regressor\r\n- [ ] Multi-output predictions\r\n- [ ] Support for sparse data through SparseSplitter\r\n- [ ] Random splitting method added to DenseSplitter (for ExtraTrees estimators)\r\n- [ ] New API works with ExtraTreesClassifier/Regressor\r\n- [ ] Resolve multi-threading support issue\r\n- [ ] Add proper documentation to all objects, mostly from #5010. \r\n\r\nI attempted to get my changes proposed in #5007 to include min_sample and min_weight constraints, but the API imposed by the Criterion class/splitters was a bit difficult for me to efficiently do so without a large number of hacks. Instead, I chose to change the API in _tree.pyx to be simpler to use and easier for me to understand. The API is as follows:\r\n\r\n```\r\ncdef class Criterion:\r\n    def __cinit__( self, n_output ): # Store the number of targets, same as before\r\n    cdef void __init__( self, X, X_sample_stride, X_feature_stride, y, y_stride, w, size, min_leaf_samples, min_leaf_weight ): # Store constants about this dataset and the constraints the user imposed\r\n    cdef SplitRecord best_split(self, samples, start, end, feature) nogil: # Find the best split for a specific feature using this criterion, looking at start, end, the sample mapping, and return a SplitRecord of the best split\r\n\r\ncdef class Splitter:\r\n    cdef void init( self, X, y, sample_weight ) # Same as before\r\n    cdef SplitRecord best_split(self, start, end, n_constant_features) # Find the best split across all features. \r\n```\r\n\r\nTreeBuilder is currently has the same API, but is changed internally to handle the new API. This makes it clearer that Splitter handles shuffling the samples around based on previous splits and determining the best global split, while Criterion handles splitting a single feature, as coordinated by the Splitter.\r\n\r\nTime tests show that this is slightly slower than the embedded criterion/splitter object I proposed in #5007 with many small trees, and even slower with fewer deep trees, with time tests below. It is also slightly more accurate, but I don't know a specific reason for that. \r\n\r\n25 estimators, max depth 2\r\n\r\n```\r\n          accuracy   train time\r\nmadelon    \r\nmaster     0.68833     2.487\r\nbranch     0.70833     0.882\r\nxgboost    0.7         0.663\r\n\r\ngaussian (50,000 points, 2 classes, 200 dimensions, each dimension z=0.5 apart)\r\nmaster     0.91712     30.815\r\nbranch     0.9192      10.757\r\nxgboost    0.92068     7.232\r\n\r\nspambase\r\nmaster     0.92122     0.444\r\nbranch     0.92122     0.166\r\nxgboost    0.92122     0.110 \r\n\r\nmnist\r\nmaster     0.83786     877.432\r\nbranch     0.83871     359.564\r\nxgboost    0.81014     200.688\r\n\r\ncovtype\r\nmaster     0.71034     462.218\r\nbranch     0.71034     249.624\r\nxgboost    0.68720     103.372\r\n\r\n5 estimators, max depth 6\r\n\r\n          accuracy   train time\r\nmadelon    \r\nmaster     0.835        2.460\r\nbranch     0.832        1.218\r\nxgboost    0.818        0.5404\r\n\r\ngaussian (50,000 points, 2 classes, 200 dimensions, each dimension z=0.5 apart)\r\nmaster     0.83908     21.9226\r\nbranch     0.84588      9.4118\r\nxgboost    0.84288      4.8209\r\n\r\nspambase\r\nmaster     0.91471      0.341\r\nbranch     0.91862      0.160\r\nxgboost    0.92252      0.070\r\n\r\nmnist\r\nmaster     0.89471     720.519\r\nbranch     0.89542     463.294\r\nxgboost    0.90257     118.749\r\n\r\ncovtype\r\nmaster     0.75713     290.271\r\nbranch     0.75730     241.988\r\nxgboost    0.75476      57.540\r\n```\r\n\r\nDeep trees seem a lot slower than before (though still faster than master); I'll need to track down where this slowdown comes from. \r\n\r\nAnother change I am considering is removing the caching of constant features, for two reasons; (1) it would make multithreading easier to handle, and (2) in none of these examples do constant features arise, and they can cause a speed decrease in larger examples. I have modification (not in this pull request) which will check if a feature is constant before checking for the best split, but won't cache the result. Here are time tests I get on covtypes between this branch, and without caching.\r\n\r\nThoughts? @glouppe @pprett @ogrisel \r\n\r\n```\r\n25 trees, depth 2\r\ncovtypes\r\nbranch       249.62s\r\nno_cache     235.04s\r\n\r\nmnist\r\nbranch       359.564\r\nno_cache     333.52\r\n\r\n5 trees, depth 6\r\ncovtypes\r\nbranch       241.988\r\nno_cache     220.25\r\n\r\nmnist         \r\nbranch       463.294\r\nno_cache     428.1\r\n```\r\n"},"comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments/126620714","html_url":"https://github.com/scikit-learn/scikit-learn/pull/5041#issuecomment-126620714","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/5041","id":126620714,"user":{"login":"jmschrei","id":3916816,"avatar_url":"https://avatars.githubusercontent.com/u/3916816?v=3","gravatar_id":"","url":"https://api.github.com/users/jmschrei","html_url":"https://github.com/jmschrei","followers_url":"https://api.github.com/users/jmschrei/followers","following_url":"https://api.github.com/users/jmschrei/following{/other_user}","gists_url":"https://api.github.com/users/jmschrei/gists{/gist_id}","starred_url":"https://api.github.com/users/jmschrei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jmschrei/subscriptions","organizations_url":"https://api.github.com/users/jmschrei/orgs","repos_url":"https://api.github.com/users/jmschrei/repos","events_url":"https://api.github.com/users/jmschrei/events{/privacy}","received_events_url":"https://api.github.com/users/jmschrei/received_events","type":"User","site_admin":false},"created_at":"2015-07-31T09:25:08Z","updated_at":"2015-07-31T09:25:08Z","body":"Sorry, I'm a little confused. Is my task list not comprehensive enough? This is my first time with a major pull request, so I apologize for not being as coordinated as I should be."}}