4
$\begingroup$

When discussing AdaBoost, authors in ESL mention that exponential loss minimizer also minimizes binomial deviance. I have trouble deriving this connection. In particular, the book states:

Another loss criterion with the same population minimizer is the binomial negative log-likelihood or deviance (also known as cross-entropy), interpreting f as the logit transform. Let $$ p(x) = Pr(Y=1|x) = \frac{1}{1 + e^{-2f(x)}} $$ and define $$ {Y}'= (Y + 1)/2 ∈ \{0, 1\}. $$ Then the binomial log-likelihood loss function is: $$ l(Y, p(x)) = {Y}' log(p(x)) + (1 - {Y}') log(1 - p(x)), $$ or equivalently the deviance is $$ -l(Y, f(x)) = log(1 + e^{-2Yf(x))}) $$

I don't understand how the last expression was obtained. In another thread here I saw an expression I can derive myself: $$ yP - log (1 + e^{P}), $$ but it doesn't look similar to the expression in the book. So the question is, how that equation for the deviance was obtained?

$\endgroup$

3 Answers 3

4
$\begingroup$

If we have a classifier which, for a given x, tells us the probability that $y=1$ and the probability that $y=-1$, using a function $f(x)$ such that the probability that $y=1$ is given by $\frac{1}{1+e^{-2f(x)}}$ and the probability that $y=-1$ is thus given by $1-\frac{1}{1+e^{-2f(x)}}=\frac{e^{-2f(x)}}{1+e^{-2f(x)}}$, then for a specific value of x, the expected negative log likelihood is given by:

$P(y=1|x)\cdot - \ln \left(\frac{1}{1+e^{-2f(x)}}\right) + P(y=-1|x)\cdot - \ln\left(\frac{e^{-2f(x)}}{1+e^{-2f(x)}}\right)$

A bit of rearranging and and noting that $P(y=1|x)+P(y=-1|x)=1$ yields: $\ln(1+e^{-2f(x)})+2\cdot P(y=-1|x)f(x)$

To find the $f(x)$ which maximises this, we differentiate wrt f(x) as were it a constant, and find:

$-2\frac{e^{-2f(x)}}{1+e^{-2f(x)}}+2P(y=-1|x)=-2\frac{e^{-2f(x)}}{1+e^{-2f(x)}}+2(1-P(y=1|x))$

which equals zero when $f(x)=\frac{1}{2}\ln\left[\frac{P(y=1|x)}{1-P(y=1|X)}\right]=\frac{1}{2}\ln\left[\frac{P(y=1|x)}{P(y=-1|X)}\right]$

This is the same $f(x)$ which minimises the expected exponential loss for any given x.

My (possibly flawed) understanding of this (in my view quite confusing) paragraph in ESL is that if we are using a function $f(x) \in \mathbb{R}$ as a classifier for a variable $y \in \{-1,1\}$, we could proceed simply by minimising exponential loss and the fact that $\frac{1}{2}\ln\left[\frac{P(y=1|x)}{P(y=-1|X)}\right]$ minimises the expected loss for any given x suggests that one can interpret the output of $f(x)$ to mean that $\hat{y}=1$ if $f(x)>0$ and $\hat{y}=-1$ if $f(x)<0$. This seems like a fairly sensible way to interpret $f(x)$ and thus maybe exponential loss is a sensible/meaningful type of loss.

Alternately, we could interpret $f(x)$ straight off the bat and somewhat arbitrarily claim that its meaning is that the probability that y=1 is given by $\frac{1}{1+e^{-2f(x)}}$. Then, if we seek to find $f(x)$ so as to maximise the expected log-likelihood, we find the expected $f(x)$ is the same as the one which minimises the exponential loss condition.

Just because the two interpretations of $f(x)$ and their corresponding loss functions lead to the same expected $f(x)$ given an underlying conditional distribution $P(y|x)$ does not mean that one would expect these two losses to yield the same classifiers given a real data set (i.e. a sample from said distribution)

$\endgroup$
2
$\begingroup$

In short, I think the equivalence is because of the change of notation and parametrization for $P(f)$. Below is my discussion.

When $y \in \{0, 1\}$, the negative binomial log-likelihood has this form: $$\tag{1}-[ylog(P)+(1-y)log(1-P)]$$, where $$P(f) = \frac{e^{f}}{1+e^{f}}$$ Then we can rewrite the original $(1)$ to obtain your last expression: $$-[ylog(\frac{e^{f}}{1+e^{f}}) + (1-y)log(1-\frac{e^{f}}{1+e^{f}})]$$ $$= -y[log(e^{f})-log({1+e^{f}})] - (1-y)log(\frac{1}{1+e^{f}})$$ $$= -y[f-log({1+e^{f}})] - (1-y)[-log(1+e^{f})]$$ $$= -yf+ylog({1+e^{f}}) +log(1+e^{f}) - ylog(1+e^{f})$$ $$= -yf + log(1+e^{f})$$ We can also denote all $y$ above by $y_{left}$ and parametrize above $P(f)$ by $$\tag{2}P=\frac{e^{f_{new}}}{e^{f_{new}}+e^{-f_{new}}}$$, which I think actually it just parameterize original $f$ by $2f_{new}$. I borrowed 'parametrize' from this paper, section 3.1 page 5.

In your question, the equivalence mentioned by the book is: $$\tag{3}-[yf - log(1+e^{f})] \equiv log(1+e^{-2yf})$$ which I think it actually is: $$\tag{*}-[y_{left}f - log(1+e^{f})] \equiv log(1+e^{-2y_{right}f_{new}})$$

, where $y_{left} \in \{0, 1\}$, and $y_{right} \in \{-1, 1\}$. The relationship between $y_{left}$ and $y_{right}$ is that $$\tag{4}y_{left} = \frac{y_{right}+1}{2}$$ and $(4)$ can be checked by plugging 0 for $y_{left}$ and -1 for $y_{right}$, or 1 for both $y_{left}$ and $y_{right}$. Other than these two pairs, the equality fails.

We can substitute P and $y$, which has been renamed by $y_{left}$ earlier, of $(1)$ by the $(2)$ and $(4)$, then $(1)$ becomes $$-\frac{y_{right}+1}{2}log(\frac{e^{2f_{new}}}{1+e^{2f_{new}}})-(1-\frac{y_{right}+1}{2})log(\frac{1}{1+e^{2f_{new}}})$$ $$= -\frac{y_{right}+1}{2}[2f_{new}-log(1+e^{2f_{new}})]+\frac{1-y_{right}}{2}log(1+e^{2f_{new}})$$ $$= -(y_{right}+1)f_{new}+\frac{y_{right}+1}{2}log(1+e^{2f_{new}})+\frac{1-y_{right}}{2}log(1+e^{2f_{new}})$$ $$= -(y_{right}+1)f_{new}+log(1+e^{2f_{new}})$$ $$\equiv log(1+e^{-2y_{right}f_{new}})$$ The last equivalance here is because that it is $log(1+e^{2f_{new}})$ when $y_{right}=-1$ and $-2f_{new}+log(1+e^{2f_{new}}) = -log(\frac{e^{2f_{new}}}{1+e^{2f_{new}}}) = -log(\frac{1}{1+e^{-2f_{new}}}) = log(1+e^{-2f_{new}})$ when $y_{right}=1$. Hence these two scenarios can be summarized by $log(1+e^{-2y_{right}f_{new}})$ of which $y_{new} \in \{-1, 1\}$

Therefore in my opinion, the above 'equivalence' $(3)$ doesn't mean that two formulas really equals to each other everywhere of $y$. It only holds when $y$ (or $y_{left}) = 0$ and $y_{right} = -1$, or $y_{left} = 1$ and $y_{right} = 1$. And the $f$ is parametrized by $2f_{new}$.

In sum, if you use $y$ (or $y_{left}$) and $f$, you will have the the left side of $(*)$ from $(1)$. If you use $y_{right}$ and $f_{new}$, you will get the right side of $(*)$ from $(1)$. So they are equivalent. (I believe there is more concise explanation than above.)

I think the parametrization is because that the logistic function $\frac{1}{1+e^{-x}}$ monotonically maps real value of $x$ from $(-\infty, \infty)$ to $(0,1)$, so a coefficient of $2$ ahead of $x$ doesn't change this mapping purpose.

$\endgroup$
0
$\begingroup$

I think it is just algebra.

$$ \begin{aligned} -l &= -y' \ln \frac{1}{1+e^{-2f}}-(1-y')\ln(1- \frac{e^{-2f}}{1+e^{-2f}}) \\ &= \ln \left[ (1+e^{-2f})^{y'} (1+e^{2f})^{1-y'} \right] \\ &= \ln (1+e^{-2yf}) \end{aligned} $$

You can verify the last equal sign by plugging in $Y=1$ and $Y=-1$ respectively.

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