9
$\begingroup$

I understand intuitively why cross-entropy is always bigger. However, could someone show that mathematically?

$\endgroup$

3 Answers 3

8
$\begingroup$

Let's say you have two distributions $p$ and $q$. Cross entropy is: $H(p,q)=-\sum_x{p(x)\log{q(x)}}$. First, you'll manipulate it to obtain the very well known form: $H(p,q)=H(p)+D_{KL}(p||q)$, where $D_{KL}(p||q)$ is called the KL distance.

$$H(p,q)=-\sum_x{p(x)\log{\left(\frac{q(x)p(x)}{p(x)}\right)}}=-\sum_xp(x)\log{\left(\frac{q(x)}{p(x)}\right)}-\sum_x{p(x)\log{p(x)}}=D_{KL}(p||q)+H(p)$$

Then, it only remains to prove that $D_{KL}(p,q)\geq 0$, which can be done in various ways. The page I shared uses $\log(x)\leq x-1$: $$D_{KL}(p||q)\geq \sum_x{p(x)\left(1-\frac{q(x)}{p(x)} \right)}=\sum_x{p(x)}-\sum_x{q(x)}=1-\sum_x{q(x)}\geq 0$$

From the beginning, we assume that $x$ is in the support set of $p(x)$, i.e. $p(x)$ is non-zero. In the wikipedia entry, it says $\sum_x{q(x)}=1$, but I disagree with it, since support set of $q(x)$ can be different.

$\endgroup$
1
$\begingroup$

More intuitively with logical deduction:

i) P(x) is the "real scenario", how things really happens, and Q(x) is the estimation ii) P(x) (-Log(Q(x))* is the "loss / punishment" function, since if indeed when, as example, probability P(x) to occur to so high and Q(x) is very low, then as P and Q are always between 0 and 1, that loss / punishment function will be VERY HIGH (due to log of a very small number)

So

a) By definition: H(P) = Sum_over_x (P(x)*Log(P(x)) is the Entropy, and P is the "Ground True" (or known to have minimal errors if the ground true cannot be properly measured)

b) then it follows, for ALL other estimated distribution/probabilities Qi, H(P,Qi): Sum_over_x (P(x)*Log(Qi(x)) is always on average less accurate, and hence greater than H(P)

Hence H(P,Q) >= H(P) is really by definition of the H(P).

Note: Compare
error A: P(x1) is 0.1, and Q(x1) is 0.5, log(0.5) = -0.69314718056, P(x1)* -Log (Q(x1)) = 0.0693.....
error B: P(x2) is 0.5 vs Q(x2) is 0.1, log(0.1) = -2.302585093 P(x2)* -Log (Q(x2)) = 1.151.....

In machine learning use case, P(xi) * -Log (Q(xi)) will penalize more those predict a lot lower probability when indeed it is a high probability case, whereas for a lower probability P(xi) such as 0.1 in error A above,

You can look at the following for more information: https://machinelearningmastery.com/cross-entropy-for-machine-learning/#:~:text=Cross%2Dentropy%20is%20commonly%20used,difference%20between%20two%20probability%20distributions.

$\endgroup$
1
$\begingroup$

$$ H(p,q) \geq H(p) \xrightarrow[]{} \sum_{x}^{}-p_{x}\log(q_{x}) \geq \sum_{x}^{}-p_{x}\log(p_{x}) \\ \xrightarrow[]{-\log(x)=\log(\frac{1}{x})} \sum_{x}^{}p_{x}\log(\frac{1}{q_{x}}) \geq \sum_{x}^{}p_{x}\log(\frac{1}{p_{x}}) \\ \xrightarrow[]{} \sum_{x}^{}p_{x}\log(\frac{1}{p_{x}}) - \sum_{x}^{}p_{x}\log(\frac{1}{q_{x}}) \leq 0 \\ \xrightarrow[]{} \sum_{x}^{}p_{x}[\log(\frac{1}{p_{x}})- \log(\frac{1}{q_{x}})] \leq 0 \\ \xrightarrow[]{\log(x) - \log(y) = \log(\frac{x}{y})} \sum_{x}^{}p_{x}\log(\frac{q_{x}}{p_{x}}) \leq 0 \\ \xrightarrow[\sum_{x}^{}p_{x} = 1, \text{So It Is Like $\color{red}\alpha$ In Concave Definition}]{{\log \text{is a Concave Function}}} \log[\sum_{x_{p_{x}\neq 0}}^{}p_{x}(\frac{q_{x}}{p_{x}})] \leq 0 \\ \xrightarrow[]{} \log[\sum_{x_{p_{x}\neq 0}}^{}\not{p_{x}}\frac{q_{x}}{\not{p_{x}}}] \leq 0 \xrightarrow[]{} \log(\sum_{x_{p_{x}\neq 0}}^{}q_{x}) \leq 0 \\ \xrightarrow[]{} \log(\sum_{x_{p_{x}\neq 0}}^{}q_{x}) \leq \log(\sum_{x}^{}q_{x}) = \log(1) = 0 \\ \xrightarrow[]{} \text{Proved} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.