{"action":"created","comment":{"url":"https://api.github.com/repos/ogrisel/pygbm/pulls/comments/226331018","pull_request_review_id":166127400,"id":226331018,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIyNjMzMTAxOA==","diff_hunk":"@@ -82,18 +95,65 @@ def grow(self):\n     def _intilialize_root(self):\n         n_samples = self.features_data.shape[0]\n         depth = 0\n+        if self.splitter.constant_hessian:\n+            hessian = self.splitter.all_hessians[0] * n_samples\n+        else:\n+            hessian = self.splitter.all_hessians.sum()\n         self.root = TreeNode(depth, np.arange(n_samples, dtype=np.uint32),\n                              self.splitter.all_gradients.sum(),\n-                             self.splitter.all_hessians.sum())\n+                             hessian)\n         if (self.max_leaf_nodes is not None and self.max_leaf_nodes == 1):\n             self._finalize_leaf(self.root)\n             return\n         self._compute_spittability(self.root)\n \n-    def _compute_spittability(self, node):\n-        split_info = self.splitter.find_node_split(node.sample_indices)\n-        node.split_info = split_info\n-        if split_info.gain < self.min_gain_to_split:\n+    def _compute_spittability(self, node, only_hist=False):\n+        \"\"\"Compute histograms and split_info of a node and either make it a\n+        leave or push it on the splittable node heap.\n+\n+        only_hist is used when _compute_spittability was called by a sibling\n+        node: we only want to compute the histograms, not finalize or push\n+        the node. If _compute_spittability is called again by the grower on\n+        this same node, the histograms won't be computed again.\n+        \"\"\"\n+\n+        # Compute split_info and histograms if not already done\n+        if node.split_info is None and node.histograms is None:\n+            # If the sibling has less samples, compute its hist first (with\n+            # the regular method) and use the subtraction method for the\n+            # current node\n+            if node.sibling is not None:  # root has no sibling\n+                n_samples_sibling = node.sibling.sample_indices.shape[0]\n+                n_samples_node = node.sample_indices.shape[0]\n+                if n_samples_sibling < n_samples_node:\n+                    self._compute_spittability(node.sibling, only_hist=True)\n+                    # As hist of sibling is now computed we'll use the hist\n+                    # subtraction method for the current node.\n+                    node.hist_subtraction = True\n+\n+            tic = time()\n+            if node.hist_subtraction:\n+                split_info, histograms = (\n+                    self.splitter.find_node_split_subtraction(\n+                        node.sample_indices, node.parent.histograms,\n+                        node.sibling.histograms)\n+                )\n+            else:\n+                split_info, histograms = self.splitter.find_node_split(\n+                    node.sample_indices)\n+            toc = time()\n+            node.time = toc - tic","path":"pygbm/grower.py","position":90,"original_position":90,"commit_id":"6fb935bf3acd5fc24c1f877526763fc9c581cb4f","original_commit_id":"6fb935bf3acd5fc24c1f877526763fc9c581cb4f","user":{"login":"NicolasHug","id":1190450,"node_id":"MDQ6VXNlcjExOTA0NTA=","avatar_url":"https://avatars2.githubusercontent.com/u/1190450?v=4","gravatar_id":"","url":"https://api.github.com/users/NicolasHug","html_url":"https://github.com/NicolasHug","followers_url":"https://api.github.com/users/NicolasHug/followers","following_url":"https://api.github.com/users/NicolasHug/following{/other_user}","gists_url":"https://api.github.com/users/NicolasHug/gists{/gist_id}","starred_url":"https://api.github.com/users/NicolasHug/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NicolasHug/subscriptions","organizations_url":"https://api.github.com/users/NicolasHug/orgs","repos_url":"https://api.github.com/users/NicolasHug/repos","events_url":"https://api.github.com/users/NicolasHug/events{/privacy}","received_events_url":"https://api.github.com/users/NicolasHug/received_events","type":"User","site_admin":false},"body":"Got it\r\n\r\nThere's a lot of\r\n\r\n```python\r\ntic = time()\r\nblablah()\r\ntoc = time()\r\ntime_spent = toc - tic\r\n```\r\n\r\nDo we want a context manager that would allow us to do something like\r\n\r\n```python\r\nwith Timer() as time_spent:\r\n    blahblah()\r\n```\r\n\r\n?","created_at":"2018-10-18T14:35:28Z","updated_at":"2018-10-18T14:35:29Z","html_url":"https://github.com/ogrisel/pygbm/pull/14#discussion_r226331018","pull_request_url":"https://api.github.com/repos/ogrisel/pygbm/pulls/14","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/ogrisel/pygbm/pulls/comments/226331018"},"html":{"href":"https://github.com/ogrisel/pygbm/pull/14#discussion_r226331018"},"pull_request":{"href":"https://api.github.com/repos/ogrisel/pygbm/pulls/14"}},"in_reply_to_id":226272957},"pull_request":{"url":"https://api.github.com/repos/ogrisel/pygbm/pulls/14","id":220532405,"node_id":"MDExOlB1bGxSZXF1ZXN0MjIwNTMyNDA1","html_url":"https://github.com/ogrisel/pygbm/pull/14","diff_url":"https://github.com/ogrisel/pygbm/pull/14.diff","patch_url":"https://github.com/ogrisel/pygbm/pull/14.patch","issue_url":"https://api.github.com/repos/ogrisel/pygbm/issues/14","number":14,"state":"open","locked":false,"title":"[MRG] Histogram computation optimization","user":{"login":"NicolasHug","id":1190450,"node_id":"MDQ6VXNlcjExOTA0NTA=","avatar_url":"https://avatars2.githubusercontent.com/u/1190450?v=4","gravatar_id":"","url":"https://api.github.com/users/NicolasHug","html_url":"https://github.com/NicolasHug","followers_url":"https://api.github.com/users/NicolasHug/followers","following_url":"https://api.github.com/users/NicolasHug/following{/other_user}","gists_url":"https://api.github.com/users/NicolasHug/gists{/gist_id}","starred_url":"https://api.github.com/users/NicolasHug/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NicolasHug/subscriptions","organizations_url":"https://api.github.com/users/NicolasHug/orgs","repos_url":"https://api.github.com/users/NicolasHug/repos","events_url":"https://api.github.com/users/NicolasHug/events{/privacy}","received_events_url":"https://api.github.com/users/NicolasHug/received_events","type":"User","site_admin":false},"body":"This is an attempt to use the relation\r\n\r\n`hist(parent) = hist(parent.left) + hist(parent.right)`\r\n\r\nto only compute explicitly either `hist(parent.left)` or `hist(parent.right)`, and get the sibling's histogram by a simple subtraction.\r\n\r\nThis is supposed to be faster because explicitly computing a histogram is `O(n_samples_at_node)` while the subtraction is only `O(n_bins)` and `n_samples_at_node >> n_bins`.\r\n\r\nTODO:\r\n\r\n- [X] Ideally only the histogram of the sibling with the least number of samples should be explicitly computed. The current implementation does not support this and will compute the histogram of whatever node comes first during the tree growing process.\r\n- [ ] The code is a bit ugly, could be refactored into something better\r\n- [X] Make it actually work...\r\n- [x] Write some tests\r\n\r\nThe good news is, the predictions are the same as before. ~~The bad news is, no clear performance gain is achieved... I'll try to understand what's going on.~~","created_at":"2018-10-04T22:09:06Z","updated_at":"2018-10-18T14:35:29Z","closed_at":null,"merged_at":null,"merge_commit_sha":"2ab622dc967a0382265517e4f36dfcf97c8c2f7c","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/ogrisel/pygbm/pulls/14/commits","review_comments_url":"https://api.github.com/repos/ogrisel/pygbm/pulls/14/comments","review_comment_url":"https://api.github.com/repos/ogrisel/pygbm/pulls/comments{/number}","comments_url":"https://api.github.com/repos/ogrisel/pygbm/issues/14/comments","statuses_url":"https://api.github.com/repos/ogrisel/pygbm/statuses/6fb935bf3acd5fc24c1f877526763fc9c581cb4f","head":{"label":"NicolasHug:histogram_subtraction","ref":"histogram_subtraction","sha":"6fb935bf3acd5fc24c1f877526763fc9c581cb4f","user":{"login":"NicolasHug","id":1190450,"node_id":"MDQ6VXNlcjExOTA0NTA=","avatar_url":"https://avatars2.githubusercontent.com/u/1190450?v=4","gravatar_id":"","url":"https://api.github.com/users/NicolasHug","html_url":"https://github.com/NicolasHug","followers_url":"https://api.github.com/users/NicolasHug/followers","following_url":"https://api.github.com/users/NicolasHug/following{/other_user}","gists_url":"https://api.github.com/users/NicolasHug/gists{/gist_id}","starred_url":"https://api.github.com/users/NicolasHug/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NicolasHug/subscriptions","organizations_url":"https://api.github.com/users/NicolasHug/orgs","repos_url":"https://api.github.com/users/NicolasHug/repos","events_url":"https://api.github.com/users/NicolasHug/events{/privacy}","received_events_url":"https://api.github.com/users/NicolasHug/received_events","type":"User","site_admin":false},"repo":{"id":148841220,"node_id":"MDEwOlJlcG9zaXRvcnkxNDg4NDEyMjA=","name":"pygbm","full_name":"NicolasHug/pygbm","private":false,"owner":{"login":"NicolasHug","id":1190450,"node_id":"MDQ6VXNlcjExOTA0NTA=","avatar_url":"https://avatars2.githubusercontent.com/u/1190450?v=4","gravatar_id":"","url":"https://api.github.com/users/NicolasHug","html_url":"https://github.com/NicolasHug","followers_url":"https://api.github.com/users/NicolasHug/followers","following_url":"https://api.github.com/users/NicolasHug/following{/other_user}","gists_url":"https://api.github.com/users/NicolasHug/gists{/gist_id}","starred_url":"https://api.github.com/users/NicolasHug/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/NicolasHug/subscriptions","organizations_url":"https://api.github.com/users/NicolasHug/orgs","repos_url":"https://api.github.com/users/NicolasHug/repos","events_url":"https://api.github.com/users/NicolasHug/events{/privacy}","received_events_url":"https://api.github.com/users/NicolasHug/received_events","type":"User","site_admin":false},"html_url":"https://github.com/NicolasHug/pygbm","description":"Experimental Gradient Boosting Machines in Python.","fork":true,"url":"https://api.github.com/repos/NicolasHug/pygbm","forks_url":"https://api.github.com/repos/NicolasHug/pygbm/forks","keys_url":"https://api.github.com/repos/NicolasHug/pygbm/keys{/key_id}","collaborators_url":"https://api.github.com/repos/NicolasHug/pygbm/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/NicolasHug/pygbm/teams","hooks_url":"https://api.github.com/repos/NicolasHug/pygbm/hooks","issue_events_url":"https://api.github.com/repos/NicolasHug/pygbm/issues/events{/number}","events_url":"https://api.github.com/repos/NicolasHug/pygbm/events","assignees_url":"https://api.github.com/repos/NicolasHug/pygbm/assignees{/user}","branches_url":"https://api.github.com/repos/NicolasHug/pygbm/branches{/branch}","tags_url":"https://api.github.com/repos/NicolasHug/pygbm/tags","blobs_url":"https://api.github.com/repos/NicolasHug/pygbm/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/NicolasHug/pygbm/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/NicolasHug/pygbm/git/refs{/sha}","trees_url":"https://api.github.com/repos/NicolasHug/pygbm/git/trees{/sha}","statuses_url":"https://api.github.com/repos/NicolasHug/pygbm/statuses/{sha}","languages_url":"https://api.github.com/repos/NicolasHug/pygbm/languages","stargazers_url":"https://api.github.com/repos/NicolasHug/pygbm/stargazers","contributors_url":"https://api.github.com/repos/NicolasHug/pygbm/contributors","subscribers_url":"https://api.github.com/repos/NicolasHug/pygbm/subscribers","subscription_url":"https://api.github.com/repos/NicolasHug/pygbm/subscription","commits_url":"https://api.github.com/repos/NicolasHug/pygbm/commits{/sha}","git_commits_url":"https://api.github.com/repos/NicolasHug/pygbm/git/commits{/sha}","comments_url":"https://api.github.com/repos/NicolasHug/pygbm/comments{/number}","issue_comment_url":"https://api.github.com/repos/NicolasHug/pygbm/issues/comments{/number}","contents_url":"https://api.github.com/repos/NicolasHug/pygbm/contents/{+path}","compare_url":"https://api.github.com/repos/NicolasHug/pygbm/compare/{base}...{head}","merges_url":"https://api.github.com/repos/NicolasHug/pygbm/merges","archive_url":"https://api.github.com/repos/NicolasHug/pygbm/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/NicolasHug/pygbm/downloads","issues_url":"https://api.github.com/repos/NicolasHug/pygbm/issues{/number}","pulls_url":"https://api.github.com/repos/NicolasHug/pygbm/pulls{/number}","milestones_url":"https://api.github.com/repos/NicolasHug/pygbm/milestones{/number}","notifications_url":"https://api.github.com/repos/NicolasHug/pygbm/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/NicolasHug/pygbm/labels{/name}","releases_url":"https://api.github.com/repos/NicolasHug/pygbm/releases{/id}","deployments_url":"https://api.github.com/repos/NicolasHug/pygbm/deployments","created_at":"2018-09-14T20:59:11Z","updated_at":"2018-09-27T13:46:42Z","pushed_at":"2018-10-17T20:29:12Z","git_url":"git://github.com/NicolasHug/pygbm.git","ssh_url":"git@github.com:NicolasHug/pygbm.git","clone_url":"https://github.com/NicolasHug/pygbm.git","svn_url":"https://github.com/NicolasHug/pygbm","homepage":null,"size":180,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit","node_id":"MDc6TGljZW5zZTEz"},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"ogrisel:master","ref":"master","sha":"176a35bb1f7c0aa134b58abd8bbc552263adb936","user":{"login":"ogrisel","id":89061,"node_id":"MDQ6VXNlcjg5MDYx","avatar_url":"https://avatars0.githubusercontent.com/u/89061?v=4","gravatar_id":"","url":"https://api.github.com/users/ogrisel","html_url":"https://github.com/ogrisel","followers_url":"https://api.github.com/users/ogrisel/followers","following_url":"https://api.github.com/users/ogrisel/following{/other_user}","gists_url":"https://api.github.com/users/ogrisel/gists{/gist_id}","starred_url":"https://api.github.com/users/ogrisel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ogrisel/subscriptions","organizations_url":"https://api.github.com/users/ogrisel/orgs","repos_url":"https://api.github.com/users/ogrisel/repos","events_url":"https://api.github.com/users/ogrisel/events{/privacy}","received_events_url":"https://api.github.com/users/ogrisel/received_events","type":"User","site_admin":false},"repo":{"id":143539809,"node_id":"MDEwOlJlcG9zaXRvcnkxNDM1Mzk4MDk=","name":"pygbm","full_name":"ogrisel/pygbm","private":false,"owner":{"login":"ogrisel","id":89061,"node_id":"MDQ6VXNlcjg5MDYx","avatar_url":"https://avatars0.githubusercontent.com/u/89061?v=4","gravatar_id":"","url":"https://api.github.com/users/ogrisel","html_url":"https://github.com/ogrisel","followers_url":"https://api.github.com/users/ogrisel/followers","following_url":"https://api.github.com/users/ogrisel/following{/other_user}","gists_url":"https://api.github.com/users/ogrisel/gists{/gist_id}","starred_url":"https://api.github.com/users/ogrisel/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ogrisel/subscriptions","organizations_url":"https://api.github.com/users/ogrisel/orgs","repos_url":"https://api.github.com/users/ogrisel/repos","events_url":"https://api.github.com/users/ogrisel/events{/privacy}","received_events_url":"https://api.github.com/users/ogrisel/received_events","type":"User","site_admin":false},"html_url":"https://github.com/ogrisel/pygbm","description":"Experimental Gradient Boosting Machines in Python.","fork":false,"url":"https://api.github.com/repos/ogrisel/pygbm","forks_url":"https://api.github.com/repos/ogrisel/pygbm/forks","keys_url":"https://api.github.com/repos/ogrisel/pygbm/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ogrisel/pygbm/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ogrisel/pygbm/teams","hooks_url":"https://api.github.com/repos/ogrisel/pygbm/hooks","issue_events_url":"https://api.github.com/repos/ogrisel/pygbm/issues/events{/number}","events_url":"https://api.github.com/repos/ogrisel/pygbm/events","assignees_url":"https://api.github.com/repos/ogrisel/pygbm/assignees{/user}","branches_url":"https://api.github.com/repos/ogrisel/pygbm/branches{/branch}","tags_url":"https://api.github.com/repos/ogrisel/pygbm/tags","blobs_url":"https://api.github.com/repos/ogrisel/pygbm/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ogrisel/pygbm/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ogrisel/pygbm/git/refs{/sha}","trees_url":"https://api.github.com/repos/ogrisel/pygbm/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ogrisel/pygbm/statuses/{sha}","languages_url":"https://api.github.com/repos/ogrisel/pygbm/languages","stargazers_url":"https://api.github.com/repos/ogrisel/pygbm/stargazers","contributors_url":"https://api.github.com/repos/ogrisel/pygbm/contributors","subscribers_url":"https://api.github.com/repos/ogrisel/pygbm/subscribers","subscription_url":"https://api.github.com/repos/ogrisel/pygbm/subscription","commits_url":"https://api.github.com/repos/ogrisel/pygbm/commits{/sha}","git_commits_url":"https://api.github.com/repos/ogrisel/pygbm/git/commits{/sha}","comments_url":"https://api.github.com/repos/ogrisel/pygbm/comments{/number}","issue_comment_url":"https://api.github.com/repos/ogrisel/pygbm/issues/comments{/number}","contents_url":"https://api.github.com/repos/ogrisel/pygbm/contents/{+path}","compare_url":"https://api.github.com/repos/ogrisel/pygbm/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ogrisel/pygbm/merges","archive_url":"https://api.github.com/repos/ogrisel/pygbm/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ogrisel/pygbm/downloads","issues_url":"https://api.github.com/repos/ogrisel/pygbm/issues{/number}","pulls_url":"https://api.github.com/repos/ogrisel/pygbm/pulls{/number}","milestones_url":"https://api.github.com/repos/ogrisel/pygbm/milestones{/number}","notifications_url":"https://api.github.com/repos/ogrisel/pygbm/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ogrisel/pygbm/labels{/name}","releases_url":"https://api.github.com/repos/ogrisel/pygbm/releases{/id}","deployments_url":"https://api.github.com/repos/ogrisel/pygbm/deployments","created_at":"2018-08-04T15:17:24Z","updated_at":"2018-10-11T14:49:39Z","pushed_at":"2018-10-17T15:02:10Z","git_url":"git://github.com/ogrisel/pygbm.git","ssh_url":"git@github.com:ogrisel/pygbm.git","clone_url":"https://github.com/ogrisel/pygbm.git","svn_url":"https://github.com/ogrisel/pygbm","homepage":null,"size":83,"stargazers_count":8,"watchers_count":8,"language":"Python","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":3,"mirror_url":null,"archived":false,"open_issues_count":3,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit","node_id":"MDc6TGljZW5zZTEz"},"forks":3,"open_issues":3,"watchers":8,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/ogrisel/pygbm/pulls/14"},"html":{"href":"https://github.com/ogrisel/pygbm/pull/14"},"issue":{"href":"https://api.github.com/repos/ogrisel/pygbm/issues/14"},"comments":{"href":"https://api.github.com/repos/ogrisel/pygbm/issues/14/comments"},"review_comments":{"href":"https://api.github.com/repos/ogrisel/pygbm/pulls/14/comments"},"review_comment":{"href":"https://api.github.com/repos/ogrisel/pygbm/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/ogrisel/pygbm/pulls/14/commits"},"statuses":{"href":"https://api.github.com/repos/ogrisel/pygbm/statuses/6fb935bf3acd5fc24c1f877526763fc9c581cb4f"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"NicolasHug"}}