Ex. 10.5

Ex. 10.5

Multiclass exponential loss (Multi-class adaboost). For a $K$-class classification problem, consider the coding $Y=(Y_1,...,Y_K{)}^T$ with

$$Y_k=\{\begin{array}{ll}1,& \text{ if }G={\mathcal{G}}_k\\ -\frac{1}{K-1},& \text{ otherwise. }\end{array}$$

Let $f=(f_1,...,f_K{)}^T$ with $\sum _{k=1}^K{f}_k=0$, and define

$$L(Y,f)=\exp (-\frac{1}{K}{Y}^{T}f).$$

(a)

Using Lagrange multipliers, derive the population minimizer $f^{\ast }$ of $L(Y,f)$, subject to the zero-sum constraint, and relate these to the class probabilities.

(b)

Show that a multiclass boosting using this loss function leads to a reweighting algorithm similar to AdaBoost, as in Section 10.4.

Soln. 10.5

(a)

We follow the similar arguments in Ex. 10.2. We're interested in

$$\underset{f(x)}{\mathrm{argmin}}{E}_{Y|x}[\exp (-\frac{1}{K}(Y_1{f}_1(x)+...+Y_K{f}_K(x)))]$$

subject to

$$f_1(x)+...+f_K(x)=0.$$

The Lagrange multiplier, denoted as $H(f_1,...,f_k,\lambda )$, becomes

$$\begin{array}{rcl}& & P(Y=1|x)\cdot \exp (-\frac{1}{K}{f}_1(x)-\frac{1}{K-1}(f_2(x)+...+f_K(x)))\\ & +& P(Y=2|x)\cdot \exp (-\frac{1}{K}{f}_2(x)-\frac{1}{K-1}(f_1(x)+f_3(x)...+f_K(x)))\\ & +& ...\\ & +& P(Y=K|x)\cdot \exp (-\frac{1}{K}{f}_K(x)-\frac{1}{K-1}(f_1(x)+f_2(x)...+f_{K-1}(x)))\\ \text{(1)}& & -& \lambda (f_1(x)+...+f_K(x))\end{array}$$

Note that $f_1(x)+...+f_K(x)=0$, so $\text{(1)}$ simplifies to

$$\begin{array}{rcl}& & P(Y=1|x)\cdot \exp (-\frac{1}{K-1}{f}_1(x))\\ & +& P(Y=2|x)\cdot \exp (-\frac{1}{K-1}{f}_2(x))\\ & +& ...\\ & +& P(Y=K|x)\cdot \exp (-\frac{1}{K-1}{f}_K(x))\\ \text{(2)}& & -& \lambda (f_1(x)+...+f_K(x)).\end{array}$$

For $k=1,...,K$, setting $\frac{\partial H}{\partial f_k(x)}=0$ and $\frac{\partial H}{\partial \lambda }=0$ yields

$$\begin{array}{rcl}-\frac{1}{K-1}P(Y=k|x)\cdot \exp (-\frac{1}{K-1}{f}_k(x))-\lambda & =& 0,\text{ for }k=1,...,K\\ f_1(x)+...+f_K(x)& =& 0.\end{array}$$

Note that we have $K+1$ equations with $K+1$ unknowns. We first represent $f_k(x)$ in terms of $\lambda$ by the first set of equations above:

$$\begin{array}{rcl}{f}_k^{\ast }(x)& =& -(K-1)\log \left(\frac{(K-1)\lambda }{P(Y=k|x)}\right)\\ \text{(3)}& & =& (K-1)\log (P(Y=k|x))-(K-1)\log ((K-1)\lambda )\end{array}$$

Then by $\sum _{k=1}^K{f}_k^{\ast }(x)=0$ we have

$$\sum _{k=1}^K((K-1)\log (P(Y=k|x))-(K-1)\log ((K-1)\lambda ))=0$$

so that

$$\begin{array}{}\text{(4)}& \lambda =\frac{1}{K-1}\prod _{k=1}^{K}P(Y=k|x{)}^{\frac{1}{K}}.\end{array}$$

Plug $\lambda$ above back to $\text{(3)}$ we obtain that for $k=1,...,K$,

$$f_k^{\ast }(x)=(K-1)\log (P(Y=k|x))-\frac{K-1}{K}\sum _{\tilde{k}=1}^K\log P(Y=\tilde{k}|x).$$

Once $f_k^{\ast }(x)$ are estimated for $k=1,...,K$, we are able to estimate $P(Y=k|x)$ in terms of $f_k^{\ast }(x)$. From $\text{(3)}$ and $\text{(4)}$, we obtain for $k=1,...,K$,

$$\begin{array}{}\text{(5)}& P(Y=k|x)=\exp \left(\frac{f_k^{\ast }(x)}{K-1}\right)\cdot (\prod _{j=1}^{K}P(Y=j|x{)}^{\frac{1}{K}}).\end{array}$$

Summing $P(Y=k|x)$ for $k=1,...,K$ we obtain

$$1=(\prod _{j=1}^{K}P(Y=j|x{)}^{\frac{1}{K}})\cdot (\sum _{k=1}^K\exp \left(\frac{f_k^{\ast }(x)}{K-1}\right)),$$

thus

$$\begin{array}{}\text{(6)}& (\prod _{j=1}^{K}P(Y=j|x{)}^{\frac{1}{K}})=(\sum _{k=1}^K\exp \left(\frac{f_k^{\ast }(x)}{K-1}\right){)}^{-1}.\end{array}$$

Plugging equation above back to $\text{(5)}$ we get

$$P(Y=k|x)=\frac{\exp \left(\frac{f_k^{\ast }(x)}{K-1}\right)}{\sum _{k=1}^K\exp \left(\frac{f_k^{\ast }(x)}{K-1}\right)}.$$

(b)

Following the idea of two-class AdaBoost, we start with a Stagewise Additive Modeling using a Multi-class Exponential loss function (SAMME).

SAMME

Note that SAMME shares the same simple modular structure of AdaBoost with a simple but subtle different in (c), specifically, the extra term $\log (K-1)$.

The link between exponential loss function and SAMME follows the same arguments in Section 10.4. Specifically, we have as (10.12),

$${\beta }_m=\frac{(K-1{)}^2}{K}(\log \frac{1-{\text{err}}_m}{{\text{err}}_m}+\log (K-1)).$$