1
$\begingroup$

In bagging and boosting models like random forest and xgboost we have hyper-parameters like minimum instances per node and max depth. If max depth is high the minimum instances per node will be less and vice versa.

Is there a mathematical equation I can make out the between two hyperparameters? That is if I had to calculate depth as a function of min instances per node, what it would be like?

This is what I have for now-

enter image description here

Let us say we have only one numerical variable with the number of bins set to mB. This is the number of levels in the case of categorical variables. We N number of samples in our dataset and the minimum number of samples needed to create a node is n. Our aim is to find the maximum possible depth(maxDepth) this tree could go to.

Now, for the tree to go the maximum depth the other nodes have to terminate instantly. If they get more samples than the bare minimum, our max depth suffers. Here in the diagram, I have shown the node to be splitting into 3 (mB) nodes. mB-1 of them have to terminate so that more and more samples can go to one node and we can thus calculate the maxDepth the tree can go to.

So at the end of the first split, we have two leaf nodes and one active/parent node. This parent node has N-N*(mb-1) samples at depth=1. So for the tree to terminate, at the depth=maxDepth, it should have at least n samples or else the tree won't grow to maxDepth.

And the number of samples at depth=maxDepth would be $$N-n*(mB-1)*maxDepth$$

thus giving us

$$N-n*(mB-1)*maxDepth \ge n$$

which leads to

$$maxDepth \le \frac{(N-n)}{n*(mB-1)} $$

Assumptions

I have made the following assumptions to reach here 1. The number of splits made at each level are same - mB 2. Each split will result in mB-1 nodes being leaf nodes and just one node capable of being a parent node.

I want to know if my calculations are correct and if it is theoretically possible for a tree to have more depth than what I have calculated.

Also, is there a way I can improve/optimize this equation so that it gives me more practical estimates?

$\endgroup$
1
  • $\begingroup$ The relationship is data dependent. Fwiw, that variation might be used to characterize different natures of data. This connects to the ideas of variable importance and greedy. I really would like to get back to you on this, I think it is an important question to ask. $\endgroup$ Sep 21 '18 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.