大话交叉熵

前言：为什么要写这一篇文章呢？大概是因为自己的脑子太笨了吧……以前就问过龙哥这个东西怎么理解，他给了我一套公式: $H(p,q) = -\sum_xp(x) \log q(x)$ 瞅了半天，发现以自己的智商并不能从公式中总结出什么门道儿，所以有感而发：”熵”这个字是特么谁发明的……内心的焦灼已经按耐不住了，既然要学，就学个明明白白，刨根问底！文章将陆续更新直至更新不动……

---

什么是熵？(Entropy)

熵的英文单词为：Entropy。熵是热力学中表征物质状态的参量之一，用符号S表示，其物理意义是体系混乱程度的度量。我们在中学时期学习热力学第二定律，

• 热力学第二定律（second law of thermodynamics）：不可能把热从低温物体传到高温物体而不产生其他影响，或不可能从单一热源取热使之完全转换为有用的功而不产生其他影响。
  其实我们学到的是删减版的内容，真实的热力学第二定律还有一条：
• 不可逆热力过程中熵的微增量总是大于零。又称“熵增定律”，表明了在自然过程中，一个孤立系统的总混乱度（即“熵”）不会减小。
  熵越大，表示系统越无序，熵越小，表示系统越有序。
  如何理解这句话呢？不妨在仔细揣摩一下前面的第二定律，我们知道热能是不可能完全用来做功的，因为有热散失，这部分散失就表示我们的系统是不可逆的，这就是熵增的过程。也就是说：如果一个系统没有外接干扰，肯定是向整体能量变低的方向运动的，也就是熵值变大。对任何已知孤立的物理系统的演化，热熵只能增加，不能减少。

---

什么是信息熵？(Information Entropy)

信息熵是香农引入到信息论当中的计量单位。用来衡量一个随机变量出现的希望值。香农提出了用信息熵来定量衡量信息的大小，就像热力学中一样，概率越大的事件，信息熵越小；概率越小的事件，信息熵越大。在信息世界，熵越高（大），则能传输越多的信息，熵越低（小），则意味着传输的信息越少。然而这里与热熵相反的是，信息熵只能减少，不能增加。
举一个简单的例子来体会在生活中什么是信息熵：
比如：你在炒股，正在10支股票中犹豫不决，而这时候我作为某公司内部人员告诉你：第3支股票明天涨停。这时候我说的这句话就有很高的信息熵；再比如：我告诉你太阳明天从东方升起。这句话的信息熵就很低，因为它几乎是概率为1的确定性事件。
所以到这里，我们明白了：所谓信息熵高，就是说，我得到某个信息后，事件的不确定性大幅度降低了。 反观“太阳从东边升起” 这句话，从信息论的角度讲，并没有消除任何不确定性，所以它的信息熵几乎为0。
信息熵不仅定量衡量了信息的大小，同时也为信息编码提供了理论上的最优值：编码平均长度的理论下界就是信息熵。即：信息熵为数据压缩的极限。

如何计算信息熵？

熵的本质是香农信息量$(\log\frac{1} {p} )$的期望。

我们以一个例子来说明。

比如说：百米赛跑，有四位选手参加,分别是：$ {A, B, C, D }$,他们获胜的概率分别为：$ { \frac{1} {2}, \frac{1} {4}, \frac{1} {8}, \frac{1} {8} }$。接下来，我们将“谁能获胜”视为一个随机变量 $X\in{A,B,C,D}$ 。假定我们需要用尽可能少的二元问题来确定随机变量 X 的取值。

例如：

问题1：A获胜了吗？

问题2：B获胜了吗？

问题3：C获胜了吗？

最后我们可以通过最多3个二元问题，来确定 $X$ 的取值，即谁赢了比赛。

如果 $X=A$ ，那么需要问1次（问题1：是不是$A$？），概率为$ \frac{1} {2} $；

如果$ X=B$ ，那么需要问2次（问题1：是不是$A$？问题2：是不是$B$？），概率为$ \frac{1} {4} $；

如果 $X=C$，那么需要问3次（问题1，问题2，问题3），概率为$ \frac{1} {8} $;

如果 $X=D$ ，那么同样需要问3次（问题1，问题2，问题3），概率为$ \frac{1} {8} $;

那么很容易计算，在这种问法下，为确定 $ X $ 取值的二元问题数量为：

$$E(N) = \frac {1} {2}\cdot 1+\frac{1} {4}\cdot2 + \frac{1} {8} \cdot 3 + \frac{1} {8} \cdot 3 =\frac {7} {4}$$

那么我们回到信息熵的定义，会发现通过之前的信息熵公式，神奇地得到了：

$$H(X) = \frac {1} {2}\log(2) + \frac{1} {4} \log(4) + \frac{1} {8} \log(8)+ \frac{1} {8} \log(8) = \frac{7} {4} bits$$

---

在计算机领域中的应用

另一个稍微复杂的例子是假设一个随机变量$X$，取三种可能值$x_1,x_2,x_3$，概率分别为$\frac{1} {2}$，$\frac{1} {4}$，$\frac{1} {4}$，那么编码平均比特长度为：$\frac{1} {2}\times1+\frac{1} {4}\times2+\frac{1} {4}\times2 = \frac{3} {2} $ 因此信息熵为$\frac{3} {2}$

在二进制计算机中，一个比特为0或1，其实就代表了一个二元问题的回答。也就是说，在计算机中，我们给“谁能夺冠” 这个事件进行编码，所需要的平均码长为1.75个比特。

平均码长的定义为：

$$L(C)=\sum\limits_{x\in\mathcal{X}}p(x)l(x)$$

很显然，为了尽可能减少码长，我们要给发生概率 $p(x)$ 较大的事件，分配较短的码长 $l(x)$ 。这个问题深入讨论，可以得出霍夫曼编码的概念。

因此信息熵实际是对随机变量的比特量和顺次发生概率相乘再总和的数学期望。

---

什么是交叉熵？

交叉熵 : 其用来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小。

现有关于样本集的2个概率分布$p$和$q$，其中 $p$ 为真实分布，$q$非真实分布。按照真实分布$p$来衡量识别一个样本的所需要的编码长度的期望(即平均编码长度)为：$H(p)=\sum{i}^{} p(i)\log \frac{1}{p(i)}$。如果使用错误分布$q$来表示来自真实分布$p$的平均编码长度，则应该是:$H(p,q)= \sum{i} p(i) \log \frac{1} {q(i)}$ 。因为用$q$来编码的样本来自分布$p$，所以期望$H(p,q)$中概率是$p(i)$。$H(p,q)$我们称之为“交叉熵”。

标准的交叉熵公式为：

$$\sum_{k=1}^N p_k \log_2 \frac{1}{q_k}$$

其中$ p_k$ 表示真实分布， $q_k$ 表示非真实分布。

举例：

真实分布 $p_k = (\frac {1} {2},\frac {1} {4},\frac {1} {8},\frac {1} {8})$，
非真实分布 $q_k = (\frac {1} {4},\frac {1} {4},\frac {1} {4},\frac {1} {4})$，
交叉熵为$\frac{1} {2}\times\log_2 4 + \frac{1} {4}\times \log_2 4 + \frac{1} {8} \times \log_2 4 + \frac{1} {8} \times \log_2 4 = 2$
可以看到这个交叉熵是比真实分布 $\sum_{k=1}^N p_k \log_2 \frac{1} {p_k}$
计算得出的信息熵要大一些的。因此，交叉熵越低，这个策略就越好，最低的交叉熵也就是使用了真实分布所计算出来的信息熵，此时 交叉熵 = 信息熵。这也是为什么在机器学习中的分类算法中，我们总是最小化交叉熵，因为交叉熵越低，就证明由算法所产生的策略最接近最优策略，也间接证明我们算法所算出的非真实分布越接近真实分布。

---

什么是相对熵($KL$散度)？

我们如何去衡量不同策略之间的差异呢？这就需要用到相对熵，其用来衡量两个取值为正的函数或概率分布之间的差异即：

$$KL(f(x) || g(x)) = \sum_{ x \in X} f(x) * \log_2 \frac{f(x)} {g(x)}$$

现在，假设我们想知道 策略$A$ 和 最优策略 之间的差异，我们就可以用相对熵来衡量这两者之间的差异。即：相对熵($KL$散度)= 策略$A$ 的交叉熵 - 信息熵（根据系统真实分布计算而得的信息熵，为最优策略），公式如下：

\begin{equation}
\begin{aligned}
KL (p | q) &= H(p,q) - H(p) \&= \sum{k=1} ^N p_k \log_2 \frac{1} {q_k} - \sum{k=1} ^N pk \log_2 \frac{1} {p_k} \&= \sum{k=1}^N p_k \log_2 \frac{p_k} {q_k}
\nonumber
\end{aligned}
\end{equation}

---

机器学习中的交叉熵？

$$H(p,q) = -\sum_{x}p(x)\log q(x)$$

从名字上看，$Cross Entropy$(交叉熵)主要是描述两个事件之间的相互关系，事件$A$对自己求交叉熵就等于熵。即：$H(A,A) = S(A)$

• 熵的意义是对A事件中的随机变量进行编码所需的最小字节数。
• $KL$散度的意义是“额外所需的编码长度”如果我们用B的编码来表示A。
• 交叉熵指的是当你用B作为密码本来表示A时所需要的“平均的编码长度。

  机器如何“学习”？

  机器学习的过程就是希望在训练数据上模型学到的分布 $P(model) $和真实数据的分布 $P(real)$ 越接近越好。
  那么怎么最小化两个分布之间的不同呢？方法就是：使其KL散度最小！但我们没有真实数据的分布，那么只能退而求其次，希望模型学到的分布和训练数据的分布 $P(training) $尽量相同，也就是把训练数据当做模型和真实数据之间的代理人。假设训练数据是从总体中独立同步分布采样$(Independent $ $and$ $ identically $ $distributed$ $ sampled$ $ )$ 而来，那么我们可以利用最小化训练数据的经验误差来降低模型的泛化误差。简单讲：

1. 最终目的是希望学到的模型的分布和真实分布一致： $P(model) \simeq P(real )$
2. 但真实分布是不可知的，我们只好假设 训练数据 是从真实数据中独立同分布采样而来： $P(training) \simeq P(real )$
3. 退而求其次，我们希望学到的模型分布至少和训练数据的分布一致 $P(model) \simeq P(training)$
   由此非常理想化的看法是如果模型(左)能够学到训练数据(中)的分布，那么应该近似的学到了真实数据(右)的分布：$ P(model) \simeq P(training) \simeq P(real)$

---

参考文献：

1. 香农信息论.
2. 什么是信息熵.
3. 为什么交叉熵可以用于计算代价.