Gini impurity greedily optimises a loss function in decision trees

Question

I am trying to understand how the Gini criterion for decision decision tree construction actually greedily optimises a loss function.

The Gini impurity, sometimes also called Gini index, for a region (think: set) $R_{j}$ is defined as $\sum_{i=1}^K p_{i}^j (1-p_{i}^j)$ where $p_{i}^j$ is the probability of drawing an example of class $i$ from region $R_{j}$ and $K$ is the number of classes.

I have two references which suggest this but I am not able to fully understand either of them so I would appreciate some help. Yang2019 write:

Given some node, the objective function after splitting on this node can be written as $$ L\left(s, f_L, f_R\right)=\sum_{i: s\left(x_i\right)=0} l\left(f_L\left(x_i\right), y_i\right)+\sum_{i: s\left(x_i\right)=1} l\left(f_R\left(x_i\right), y_i\right) \text {, } $$ where $s(\cdot)$ denotes a binary split function which decides whether an input instance that reaches this node should progress through the left or right branch emanating from the node; and $f_L(\cdot), f_R(\cdot)$ denote the output function w.r.t the left and right child, respectively.

Given a specific split function $s(\cdot)$, we have the reduction of objective function $$ \begin{aligned} t(s)=\min _w \sum_{i=1}^n l\left(w, y_i\right)-\min _{w^L} & \sum_{i: s\left(x_i\right)=0} l\left(w^L, y_i\right) & -\min _{w^R} \sum_{i: s\left(x_i\right)=1} l\left(w^R, y_i\right), \end{aligned} $$ where $w, w^L, w^R$ denote the output values of the node and left and right child node, since instances in one node have the same output values. --- Based on this equation, we can directly prove that the essence of various splitting criteria is to optimize some loss functions greedily. For instance, the frequently-used criteria gini impurity and information gain are essentially equivalent to optimizing the square loss and softmax loss [23], respectively.

I understand the equations above but I do not see how a split $s$ that minimises the Gini index reduces the squared error loss function $l(w_{L}, y_{i}) = (w_{L} - y_{i})^2$ (resp. for $R$).

Let's try something else then. Leistner2009 consider margin losses instead and argue that the Gini index greedily optimises a loss function "related to the Hinge loss"

We can write the empirical loss at a node $R_j$ as $$ \mathcal{L}\left(\mathcal{R}_j\right)=\frac{1}{\left|\mathcal{R}_j\right|} \sum_{(\mathbf{x}, y) \in \mathcal{R}_j} \ell\left(g_y(\mathbf{x})\right) . $$ where $g_{y}(x)$ is the "true margin vector of $x$" i.e. Let $\mathbf{g}(\mathbf{x})=\left[g_1(\mathbf{x}), \cdots, g_K(\mathbf{x})\right]^T$ be a multivalued functio, then. $\mathbf{g}(\mathbf{x})$ is called a margin vector, if $$ \forall \mathbf{x}: \sum_{i=1}^K g_i(\mathbf{x})=0 . $$ Defining the margin vector as $\mathbf{g}^j(\mathbf{x})=\left[p_1^j-\right.$ $\left.\frac{1}{K}, \cdots, p_K^j-\frac{1}{K}\right]^T$, we can develop the empirical loss as $$ \begin{aligned} \mathcal{L}\left(\mathcal{R}_j\right) & =\frac{1}{\left|\mathcal{R}_j\right|} \sum_{(\mathbf{x}, y) \in \mathcal{R}_j} \sum_{i=1}^K \mathbb{I}(y=i) \ell\left(p_i^j-\frac{1}{K}\right) \\ & =\frac{1}{\left|\mathcal{R}_j\right|} \sum_{i=1}^K \ell\left(p_i^j-\frac{1}{K}\right) \sum_{(\mathbf{x}, y) \in \mathcal{R}_j} \mathbb{I}(y=i) \\ & =\sum_{i=1}^K p_i^j \ell\left(p_i^j-\frac{1}{K}\right) . \end{aligned} $$ Using (these) results, we can see that (...) the Gini index is related to the hinge loss function.

Again, I understand the derivation but I am unable to see how the Gini index $\sum_{i=1}^K p_{i}^j (1-p_{i}^j)$ can be related to the equation above and via what $\ell$.

Answer 1

I got a somewhat mathematical explanation for this. The idea is to argue that the negative Gini index is a generator function for a Bregman divergence that corresponds to classification margins.

I hope it makes sense. Let me know if there's anything wrong with it.

One may suggest a measure of purity as the probability of drawing two different outcomes from the examples in the current cell.

Def: Let $p_{k} = \mathbb{P}_P(k|X)$ be the probability of drawing an example orepf class $k$ from node $P$. The probability of drawing one example of class $k$ and one of a different class is $p_{k}(1-p_{k})$. The probability of drawing two examples of any two different classes then is the Gini index $$ G := \sum_{k}p_{k}(1-p_{k}) = 1 - \sum_k p_k^2 $$

We will now argue that a reduction in the Gini index in fact pushes values $p_{k}$ to the extremes of the probability simplex. We perform a slight shift in perspective and consider the classification margin instead of the estimated probabilites.

Def: The classifier margin for class $k$ of an example $X$ is the difference between the model's confidence that $X$ is of class $k$ and the next-best class: $$ m_{k}(X) := \mathbb{P}(k|X) - \max_{j\not=k} > \mathbb{P}(j|X) $$

For a pair $(X,y)$ of example and true outcome, the model's prediction is correct iff $m_y(X) > 0$ The vector $m(x) = [m_{1}(x), \dots, m_{K}(x)]^\top$, where $K$ is the total number of classes, is called a margin vector iff its components sum to zero.

We will argue that the Gini index split criterion, which finds a split such that the Gini index is reduced, in fact maximises the classification margins.

Lemma: Let $p$ be a probability distribution and $u$ an arbitrary vector. Let $G =\sum_{k} p_{k}(1-p_{k})$ be the Gini index. Then $-G$ is the generator for the Bregman divergence $$ B_{-G}(p,u) =\sum_{k}(p_{k}-u_{k})^2 $$

Proof: Let $\phi(q) := (-1) \sum_{k} p_{k}(1-p_{k})$. Then, the first equality follows by definition of a Bregman divergence and the second equality by arithmetic. \begin{align*} B_{-G}(p,u) &= \underbrace{(-1) \sum_{k} p_{k}(1-p_{k})}_{\phi(p)} ~ ~ - ~ ~ \underbrace{(-1) \sum_{k} u_{k}(1-u_{k})}_{\phi(u)} ~ ~ - ~ ~ \underbrace{\sum_{k} (2u_{k}-1)(p_{k}-u_{k})}_{\langle \nabla \phi(u), p-u \rangle} \\ &= \sum_{k} (p_{k}-u_{k})^2 \end{align*}

Note further that maximising the value of the generator function $\phi$ with respect to $p$ while leaving the the other parameter $u$ fixed also maximises the divergence $B(p,u)$. The sign of the generator value and the sign of the divergence are related in that $B_{-\phi}(p,u) = - B(p,u)$. This means that minimising the Gini index during splitting maximises component-wise sum of squared errors between $p$ and $u$. $$ \min G \rightarrow \min B_{-G}(p,u) \rightarrow \max B_{-G}(p,u) = \sum_{k}\left( p_{k} - u_k \right)^2 $$

If $p$ is a probability distribution and $u := [\frac{1}{k}, \dots, \frac{1}{k}]^\top$, then $p-u$ is a margin vector and the optimisation corresponds to maximising the classification margins as measured by the squared error.

A common approach in training classification models is margin maximisation [2] in which we aim to maximise the margin of the true label $m_{y}(X)$. A margin loss function $\ell : \mathbb{R} \to \mathbb{R}$ is a margin-maximising loss if $\ell'(m_{y}(X)) \leq 0$ for all values of $m_{y}$ [3].

An example for a margin-maximising loss function is the hinge loss defined as $\ell(m_{y}(x)) := \max \{ 0, 1-p \}$. Its subderivative is $$ \frac{\partial\ell}{\partial p} = \begin{cases} -1 & p \leq 1 \\ 0 & \text{else} \end{cases} $$ and hence it is a margin-maximising loss.

A decision tree can also be evaluated based on a margin loss. The empirical error of a decision tree node $P$ with respect to a margin loss $\ell$ can be written as $L(P) = \frac{1}{|P|} \sum_{i \in P} \ell\left(m_{y}(x_{i})\right)$ where $m_{y}(x_{i})$ is the value of the true margin. Then the following holds [3]. \begin{align*} L(P) &= \frac{1}{|P|}\sum_{i \in P} \sum_{k} \mathbb{1}(y_{i}=k) ~ ~ \cdot ~ ~ \ell \left( m_y(x_i) \right) \\ &= \sum_{k} \frac{1}{|P|} \sum_{i \in P} \mathbb{1}(y_{i}=k) ~ ~ \cdot ~ ~ \ell(m_{k}(x_{i})) \\ &= \sum_k p_k(x_i) \ell(m_k(x_i)) \end{align*} Hence we see that the Gini index splitting criterion greedily optimises classification margins and thus margin-maximising losses.

Side note: Another commonly used splitting criterion is the information gain corresponding to the Shannon entropy. The entropy is the Bregman generator for the KL-divergence. So, a very similar argument could be applied to argue that the information gain optimises the KL-divergence.

[2] schapire_BoostingFoundationsAlgorithms_2012

[3] leistner_SemiSupervisedRandomForests_2009