2
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ The name Gini is attached, with some historical justification, to quite different measures. This measure based on squared probabilities is not the same as that covered in the book by Yitzhaki and Schechtman. $\endgroup$
    – Nick Cox
    Oct 30, 2023 at 2:10
  • $\begingroup$ To make the distinction concrete, note that for the measure here it is necessary and sufficient to know or estimate probabilities of $K$ classes, $p_k$ (I've changed the OP's notation slightly). At the simplest we might have just categories $A$ and $B$ and two probabilities. Then $\sum_{k=1}^K p_k^2$ is a measure of homogeneity, quaintly sometimes called purity, maximised at $1$ if one $p_k$ is $1$ and the others all $0$. Similarly $1 - \sum_{k=1}^K p_i^2$ is a measure of heterogeneity (impurity). $\endgroup$
    – Nick Cox
    Oct 30, 2023 at 9:15
  • $\begingroup$ This is nothing to do with any Gini index based on pairwise differences $x_i - x_j$ for pairs of values $x_i, x_j$ for a counted or measured variable $x$ (income is a common example in economics). It's unfortunate that the same name is persistently used for different measures, but confusion should not survive a look at the algebra or the results of calculations. $\endgroup$
    – Nick Cox
    Oct 30, 2023 at 9:17
  • $\begingroup$ I don't have an answer to the question! $\endgroup$
    – Nick Cox
    Oct 30, 2023 at 11:49
  • $\begingroup$ Thank you for your comments. Indeed, I am referring to the quantity that @NickCox describes. The better term is probably "Gini impurity". Also described on this wikipedia page. Since opening this question I thought about it some more, see my answer below. $\endgroup$
    – ngmir
    Oct 30, 2023 at 14:24

1 Answer 1

0
$\begingroup$

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

$\endgroup$

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.