<p dir="auto">Currently the tree fitting procedure tries all possible splits between unique values of each feature in <code class="notranslate">find_best_split</code> and <code class="notranslate">_smallest_sample_larger_than</code> in <code class="notranslate">_tree.pyx</code>. This can be very expensive for large datasets.</p>
<p dir="auto">TMVA [1] implements both this same procedure as well as a mode that histograms each feature with a fixed number of bins [2]:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="The cut values are optimised by scanning over the variable range with a granularity that is set
via the option nCuts. The default value of nCuts=20 proved to be a good compromise between
computing time and step size. Finer stepping values did not increase noticeably the performance
of the BDTs. However, a truly optimal cut, given the training sample, is determined by setting
nCuts=-1. This invokes an algorithm that tests all possible cuts on the training sample and finds
the best one."><pre class="notranslate"><code class="notranslate">The cut values are optimised by scanning over the variable range with a granularity that is set
via the option nCuts. The default value of nCuts=20 proved to be a good compromise between
computing time and step size. Finer stepping values did not increase noticeably the performance
of the BDTs. However, a truly optimal cut, given the training sample, is determined by setting
nCuts=-1. This invokes an algorithm that tests all possible cuts on the training sample and finds
the best one.
</code></pre></div>
<p dir="auto">A similar feature in scikit-learn would be nice and should offer a speedup on large datasets with many features. Hopefully this issue can be converted to a PR soon (preferably after <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="9489967" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/1488" data-hovercard-type="pull_request" data-hovercard-url="/scikit-learn/scikit-learn/pull/1488/hovercard" href="https://github.com/scikit-learn/scikit-learn/pull/1488">#1488</a> is merged). Just noting it here for future reference and to incite discussion.</p>
<p dir="auto">[1] <a href="http://tmva.sourceforge.net/" rel="nofollow">http://tmva.sourceforge.net/</a><br>
[2] <a href="http://tmva.sourceforge.net/docu/TMVAUsersGuide.pdf" rel="nofollow">http://tmva.sourceforge.net/docu/TMVAUsersGuide.pdf</a> (sections 8.12.2 and 8.12.3)</p>
<p dir="auto">This is a follow-up of <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="5546611" data-permission-text="Title is private" data-url="https://github.com/scikit-learn/scikit-learn/issues/946" data-hovercard-type="pull_request" data-hovercard-url="/scikit-learn/scikit-learn/pull/946/hovercard" href="https://github.com/scikit-learn/scikit-learn/pull/946">#946</a>. We came to the conclusion that the algorithm behind <code class="notranslate">find_split</code> should be redesigned in order to decrease one step further the training time in decision trees.</p>
<p dir="auto">Below is a summary of the strategies we discussed.</p>
<hr>
<p dir="auto">N = total number of training samples<br>
N_i = number of training samples at node i<br>
d = n_features.</p>
<p dir="auto">Let's assume for now that max_features = d.</p>
<ol dir="auto">
<li>
<p dir="auto">Building X_argsort is O(N log(N) * d)</p>
</li>
<li>
<p dir="auto">On master, at each node, find_split is O(N * d). To build a fully developed tree, find_split has to be called O(N) times, which results in a cumulative complexity for find_split of O(N^2 * d).</p>
</li>
</ol>
<p dir="auto">In total, the complexity of building a single tree is then O(N log(N) * d + N^2 * d)</p>
<p dir="auto">If T trees are built, the complexity is O(N log(N) * d + T * N^2 * d) since X_argsort is shared for all trees.</p>
<ol start="3" dir="auto">
<li>[Strategy A] Assume that we remove sample_mask and that, at each node, we rather reorder X_argsorted in a divide and conquer fashion.</li>
</ol>
<p dir="auto">In that case, at each node, find_split is O(N_i *d). To build a fully developped tree, find_split has to be called O(N) times, which results, if we further assume that the tree is balanced, in a cumulative complexity for find_split of O(N log(N) * d).</p>
<p dir="auto">In total, the complexity of building a single tree is then O(N log(N) * d + * N log(N) * d).</p>
<p dir="auto">If T trees are built, the complexity is O(N log(N) * d + T * N log(N) * d) but requires extra-memory of O(N*d * n_jobs).</p>
<ol start="4" dir="auto">
<li>[Strategy B] Assume that we remove X_argsort and sample_mask and that, each node, we sort the node samples<br>
along the considered features.</li>
</ol>
<p dir="auto">In that case, at each node, find_split is O(N_i log(N_i) * d). I don't exactly know the cumulative complexity in that case but my intuition is that it sould be should something like O(N log(N)^2 * d). Anyway, far less that O(N^2 * d).</p>
<p dir="auto">In total, the complexity of building a single tree should be around O(N log(N)^2 * d).</p>
<p dir="auto">If T trees are built, then complexity should be O(T * N log(N)^2 * d).</p>
<hr>
<p dir="auto">Overall, I think Strategy A is the best of all but the extra-memory required is a significant disadvatange.</p>
<p dir="auto">Regarding Strategy B, theory says that asymptotically it is better than master, even for building ensemble of trees. However I agree that we should account for the constant factors behind this analysis. I remain convinced however that we should at least try and see! (I can work on that.)</p>