In this paper, definition 4 claims that a

tree grown by recursive partitioning is $\alpha$-regular for some $\alpha>0$ if each split leaves at least a fraction $\alpha$ of the available training examples on each side of the split, and moreover, the trees are fully grown to depth $k$ for some $k \in \mathbb{N}$ (i.e. there are between $k$ and $2k-1$ observations in each terminal node of the tree.

the first part of the definition makes sense to me, but I am not sure I understand how they conclude that there are between $k$ and $2k-1$ observations in a terminal node. Say you train a tree with $n$ observations, and you choose a depth $k$, then based on the $\alpha$-regularity, and assuming $\alpha < 0.5$ the minimum number of observations in a node at depth $k$ is going to be $n\alpha^k$, and the largest is $n(1-\alpha)^k$ - so I am not sure how they are able to conclude that the size of the node is between $k$ and $2k-1$.

update: my best guess is that they didn't mean a depth of $k$, but rather they require that the tree is grown fully, and since $\alpha$ is a proportion, it can at most be $0.5$, and so the number of observations in a terminal leaf will be between $k$ and $2k-1$ for some $k$. As the number of data points gets larger, this requires that the tree to become deeper since (I assume) $k$ is kept fixed



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.