I understand intuitively why cross-entropy is always bigger. However, could someone show that mathematically?
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
$$ 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}}} \sum_{x}^{}p_{x}\log(\frac{q_{x}}{p_{x}}) \leq \log[\sum_{}^{}p_{x}(\frac{q_{x}}{p_{x}})] \\ \log[\sum_{}^{}\not{p_{x}}\frac{q_{x}}{\not{p_{x}}}] = \log(\sum_{x_{p_{x}\neq 0}}^{}q_{x}) \leq \log(\sum_{x}^{}q_{x}) = \log(1) = 0 \\ \xrightarrow[]{} \sum_{x}^{}p_{x}\log(\frac{q_{x}}{p_{x}}) \leq \log[\sum_{x_{p_{x}\neq 0}}^{}p_{x}(\frac{q_{x}}{p_{x}})] \leq 0 \\ \xrightarrow[]{} \text{Proved} $$
$\begingroup$
$\endgroup$
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.
