Ex. 10.10

Show that for $K = 2$ class classification, only one tree needs to be grown at each gradient-boosting iteration.

Soln. 10.10

For classification the loss function (for a single training sample) is the multinomial deviance

\begin{array}{rcl} L (y, p (x)) & = & - \sum_{k = 1}^{K} 1 (y = G_{k}) \log p_{k} (x) \\ = & - \sum_{k = 1}^{K} 1 (y = G_{k}) f_{k} (x) + \log (\sum_{l = 1}^{K} e^{f_{l} (x)}), \end{array}

where

p_{k} (x) = \frac{e^{f_{k} (x)}}{\sum_{l = 1}^{K} e^{f_{l} (x)}} .

Then $K$ least square trees are constructed at each iteration, with each tree is fit to its respective negative gradient

1 (y = G_{k}) - p_{k} (x) for k = 1, . . ., K .

When $K = 2$ , we have $p_{1} (x) + p_{2} (x) = 1$ . When we build the first least square tree $T_{1}$ , it is fit to

1 (y = G_{1}) - p_{1} (x),

which is the negative of the target of the second tree $T_{2}$ :

1 (y = G_{2}) - p_{2} (x) .

To see that, note

1 (y = G_{1}) - p_{1} (x) = (1 - 1 (y = G_{2})) - (1 - p_{2} (x)) = - (1 (y = G_{2}) - p_{2} (x)) .

Therefore, once we build $T_{1}$ , we can flip the sign and get $T_{2}$ .