[ML] Avoid computing best splits for nodes which we know can't split

[tveasey]

We only split nodes for which the gain > small positive constant. If there were a cheap upper bound available for gain we could avoid the expensive operation of computing the various split derivatives and finding the best split. Handily there is...

The penalty from regularisation is known in advance: "size penalty" + "depth penalty". We also know that an optimal split must come from amongst the n - 1 possible 2-splits one obtains from sorting the node's values by increasing target. This can be used to cheaply upper bound the maximum reduction in loss. The necessary statistics can be computed once and passed down from the parent node when it is split.

[valeriy42]

Let G^+ and G^- be a sum of positive and negative gradients respectively, let H^+ and H^- be a sum of hessians corresponding to the positive and negative gradients respectively. The we have
gain <= G^+/(H^+ + lambda) + G^-/(H^- + lambda) - root_{similarity} =: gain_{max} the upper bound over gain.

Due to the penalties gamma for tree size and alpha*\sum exp((depth/target_depth - 1)/tolerance) for tree depth, we only need to consider the splitting of the nodes with gain_{max} >= gamma + alpha*\sum exp((depth/target_depth - 1)/tolerance).

Furthermore, the difference between gain_max and the penalty terms can be seen as "improvement potential" for prioritization in the priority queue.

[tveasey]

Furthermore, the difference between gain_max and the penalty terms can be seen as "improvement potential" for prioritization in the priority queue.

This may be referring to the following, but to be explicit, we have the priority queue of nodes to split and a maximum permitted tree size. We perform splitting in gain order so we can slightly tighten this bound. Letting m be the number of nodes in the queue,n the current tree size and maximum N the maximum tree size then to possibly select a split we have gain_{max} - gamma - alpha (2 * exp(depth/tolerance) - exp((target_depth - 1)/tolerance)) > nodegain_{(m - (N - n))} where nodegain_{(i)} := 0 for i < 0 and the i'th largest gain in the queue otherwise. Again there is no point in computing gain if this bound is not satisfied.

[tveasey]

Computing the bounds proved slightly fiddly: there is a tradeoff between how much extra work you do and how tight you can get the bound. In the end, the approach documented here proved effective.

[tveasey]

This was addressed in #1537.