Proof that Gini Impurity in a Decision Tree is Monotone Decreasing? I asked this in a reply to an answer to another of my questions; but I think this merits its own question since I couldn't find an answer, and it's a pretty interesting question on its own.
Suppose we construct a decision tree for classification based on the Gini impurity function.  Can we prove that the weighted average of the Gini impurities of children nodes is always &lt;= the Gini impurity of the parent node?
More precisely:
Let G(S)=sum_i p_i(1-p_i), where S is a finite nonempty set of points with known classification, p_i is the proportion of points in S with classification i, and the sum is taken over all classes. In the special case of binary classification, this simplifies to G(S)=2p(1-p), where p is the proportion of one of the classes.
Assume that every point x has a feature f. Denote the value of this feature by x(f). A splitting of S is defined as a partition of S into {S_left, S_right}, where S_left = {x in S: x(f) &lt;= c} and S_right = {x in S: x(f) &gt; c}. We require both of these sets to be nonempty.
A splitting is called good if
|S_left|/|S| G(S_left) + |S_right|/|S| G(S_right) &lt;= G(S)

Must there always exist at least one good splitting?
Must all splittings be good?
I think I've got a proof.
Any node can be identified with the vector (p_1,...,p_k) that gives the proportion of points with each classification. The Gini impurity function can then be viewed as a function from R^k to R. The weighted average of the proportions of points in S_left and S_right belonging to a certain class is equal to the proportion of points in S belonging to that class. Thus the inequality is just stating that the Gini impurity function is concave. But that is true; its matrix of second derivatives is just a diagonal matrix whose diagonal entries are all -1.