It seems pretty obvious that if I currently have a tree with a certain total impurity, then by splitting it again optimally, I can never end up with a greater total impurity. It seems similar to the idea of R squared.

I was wondering if there was a simple proof for this.


2 Answers 2


'optimally' is not necessary. What you really need to prove is that, impurity wouldn't increase no matter how you split. This could be done via a simple trick using concave function.

Since you didn't specify the impurity function, I'll try to be more general. In a $k$ class problem, let the impurity measure be $$ L(\mathbf{p})=\sum_i^k{l(p_i)}$$ where $p_i$ is the proportion of points from class $i$, and $l(\cdot)$ is concave.

Suppose in a parent node there are $(a_1,a_2,\ldots, a_k)$ samples for each class, and $(b_1,\ldots,b_k), (c_1,\ldots,c_k)$ for left child and right child separately.

Let $A=\sum_i{a_i}$, and $B,C$ are similarly defined. (thus $A=B+C $)

Then total impurity for child nodes is: $$ \frac{B}{A}\sum_i{l(\frac{b_i}{B})}+\frac{C}{A}\sum_i{l(\frac{c_i}{C})} = \sum_i{ \big( \frac{B}{A} l(\frac{b_i}{B}) +\frac{C}{A}l(\frac{c_i}{C}) \big) }\\ (\mbox{Jensen's inequality}) \qquad \leq \sum_i{ l(\frac{B b_i}{AB}+\frac{Cc_i}{AC})}\\ =\sum_i{l(\frac{a_i}{A})}$$ The last row is exactly the impurity of parent node.

Now for regression impurity:

Let $y_i,i=1 \ldots n$ be the samples in parent node. Then the impurity is SSE of the following regression(with only intercept): $$y_i=b_0+\epsilon_i$$ Create variable $x_i=1_{(\mbox{sample } i \ \mbox{goes to left node})}$, then the impurity sum for child nodes is the SSE of regression: $$ y_i=b_0+b_1x_i+\epsilon_i $$

SSE never increases when you add more covariates.

  • $\begingroup$ Sorry I should have been more specific because I want to show this for a regression tree and in particular the least squares impurity function. $\endgroup$
    – Jim
    Aug 20, 2015 at 15:25
  • $\begingroup$ @Jim That should be even easier. I've just added it to answer. $\endgroup$
    – Lii
    Aug 20, 2015 at 18:24

Lii's answer applies to current terminal nodes. It might be worth noting that this is true if you condition on the current configuration of the splits (in the tree above where you are proposing any split). However, if you change any split rule in the interior of the tree (not a split rule that results in 2 terminal nodes) then this isn't necessarily true. This is a result of the NP-hardness of finding an optimal tree. The tree growing process makes greedy choices at each split which may be locally optimal but aren't necessarily globally optimal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.