从最大熵模型到loss的设计
熵
由来
自然界里,气体分子的扩散,是一个从有序到无序的过程,因为原先泾渭分明的两种气体分子彼此交融;水的蒸发,是一个从有序到无序的过程,因为原先有序排列的水分子变得无序;人类的学习,知识的积累与传播,也是在不断地打破原有的知识结构,形成新的认知。自然界大量的现象,都需要我们创造出一个量,用于数学的刻画一个系统无序的程度。这个量就是熵。
假设现在有一个系统,它有n种可能的状态,每一状态的概率为pi,我们为这个系统引入熵函数Hn(p1, p2, ...pn)。这个量应当满足三个性质(公理): - 1.连续性:Hn是其变量的连续函数 - 2.极值性:当所有$p_i=\frac1n$时,Hn取最大值 - 3.可加性:Hn + 1(p1, …, (1 − q)pn + 1, qpn + 1) = Hn(p1, …, pn) + pn + 1H2(1 − q, q),其中0 < q < 1,这一点等价于,对于独立随机变量X, Y, 满足S[p(x)p(y)] = S[p(x)] + S[p(y)]
在这种假设下,由数学推导,熵可以被唯一地定义为(α是正常数) $$H_n(p_1,p_2,...p_n)=-\alpha \sum_{i=1}^n p_i\log p_i$$ 对于等概率的情况,即$p_i=\frac1n$,熵的值为 $$H_n\left(\frac1n,\frac1n,\ldots,\frac1n\right)= \alpha \log n$$ 这与物理学中的玻尔兹曼熵形式一致,α可以取为kB(玻尔兹曼常数)。n就是系统的微观状态数。玻尔兹曼熵定义为 SB = kBlog Ω 其中Ω是系统的微观状态数。kB是玻尔兹曼常数。
因此,关于熵的定义,我们总结出如下两种形式
对于给定分布的离散随机变量X,熵定义为: S = −∑xp(x)log p(x) 对于给定分布的连续随机变量X,熵定义为 S = −∫p(x)log p(x)dx 同时,我们可以自然的得到两种特殊的熵的定义,其一是联合熵 SXY = −∫∫p(x, y)log p(x, y)dxdy 其二是条件熵,我们已经知道,条件分布就是在联合分布p(x, y)的基础上,已经知道p(x)的分布,求X确定时,Y的分布情况。那么条件熵自然是在联合熵的基础上,再引入X的熵,所剩下的熵值:
S(Y|X) = S[p(x, y)] − S[p(x)] = −∑x∑yp(x, y)log p(y|x)
一言以蔽之,条件熵就是说本来不确定性有S[p(x, y)]这么多,引入p(x)能带来量为S[p(x)]的信息,减少掉一定的不确定性,剩下的不确定性,就是条件熵。
应用
任何排序算法时间复杂度不可超过O(nlog n)
排序算法的时间复杂度分析是每一个计算机专业学生的必修课。有趣的是,我们可以通过熵直接证明,排序算法的时间复杂度不可能更优于O(nlog n)。
假设我们现在有n个元素需要排序,也就是说,这一系统的微观状态数为n!。利用Stirling公式,我们可以将这一系统的熵写为 $$\log(n!)\sim\log\left[\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right]\sim\mathcal{O}(n\log n)$$
在排序算法的时间复杂度分析中,以每一次比较数据为一个单位。事实上,每一次比较最多获取1比特信息,(p=0.5时,S=log2=1比特,比较大小消除了这一p=0.5的不确定性,提供了1bit信息)。因此,排序算法的时间复杂度至少为
𝒪(nlog n)
决策树
决策树是机器学习中常用的分类方法。决策树的构建过程可以看作是一个不断地减少不确定性的过程。每一次分裂,都是在选择一个特征,使得分裂后的子集的不确定性(熵)最小化。
特征选择
特征选择是机器学习中一个重要的步骤。通过计算特征与目标变量之间的熵,可以选择出最有信息量的特征。常用的方法包括信息增益和信息增益率。
熵的最大和最小
在机器学习中,我们可以使熵最大或者最小,得到两种截然相反的应用。
最大熵模型
最大熵模型是一种基于信息论的概率模型,它的基本思想是,在已知的条件下,选择熵最大的概率分布。这一思想的出发点,主要基于泛化性能考虑。在训练模型的参数的时候,我们希望模型能够在训练集上表现良好,同时又不希望模型过拟合。这时候,我们就需要最大化模型的熵,把熵最大化意味着选择一种最不确定的分布,信息量最大的分布,这意味着承认我们的无知,选择最少的先验知识和主观假设
最小熵模型
最小熵模型则是通过最小化熵来达到特定的目标,什么情况下需要最小呢?比如人类的语言,语言是一种及其有序,有规律的系统,因此在语言模型中,我们希望生成的句子具有较低的熵,即更高的确定性。这意味着承认别人的聪明,接纳更多的先验知识和系统客观性质
交叉熵&KL散度
在介绍交叉熵与KL散度之前,我们先回顾一下熵的定义。 $$H_p(X)=\sum_xp(x)\cdot\log\frac{1}{p(x)}$$
众所周知,p(x)描述事件x发生的概率,那么我们可以把$\log\frac{1}{p(x)}$看做事件x发生后带来的信息量。当p = 1时,意味着我们知道此事必然发生,那么这一事件的发生并没有带来什么信息量。反之,一个小概率事件发生了,可以为我们带来很大的的信息量,这一系统就更出乎我们的意料,更混乱,具有更大的熵。
在这种视角下,我们可以自然地引出交叉熵,这用于衡量两个概率分布的差异,举个例子,给定随机事件X, 其客观真实分布为p(x),我们的主观预测分布为q(x),当我们带着自己的主观预测,与不断观察X的客观发生,我们收获的信息量应当是
$$H(p,q)=\sum_x p(x)\log \frac{1}{q(x)}$$
什么时候交叉熵会很大?当我们主观上认为一个事情发生的概率很低(q(x)很大),但是客观上发生概率很高(p(x)很大)的时候,也就是主观认知和客观现实非常不匹配的时候。因此机器学习使用交叉熵做函数,就是为了最小化模型的主观预测与数据的客观分布之间的差异。
交叉熵可以衡量我们基于某种主观认识去感受客观世界时,收获的信息量。但是只要事件仍然随机而非确定,客观信息本身也会有自己的熵0,KL散度(相对熵)就是从收获的全部信息(混乱程度)减去客观信息本身的熵,得到的剩余信息量。定义为
$$\begin{aligned}D_{KL}(p||q)&=H_{p,q}(X)-H_{p}(X)\\&=\int p(x)\log\frac{1}{q(x)}dx-\int p(x)\log\frac{1}{p(x)}dx\\&=\int p(x)\log\frac{p(x)}{q(x)}dx\end{aligned}$$
不过,在模型优化中直接采用交叉熵作为损失函数就好了,因为客观分布并不随参数变化,后一项在优化过程中为常数,求导为0,优化交叉熵等价于优化KL散度。
softmax
多分类神经网络中,有一个现实的矛盾。对于预测n个类的任务,我们通过神经网络输出了n个节点的实数值,然而这些值并不能直接表示每个类的概率分布。这为我们使用交叉熵做损失函数提供了不小的麻烦。为了解决这个问题,我们引入了softmax函数,它可以将任意实数向量转换为一个概率分布。 softmax函数的定义为 $$\text{softmax}(z_i) = \frac{e^{z_i}}{\sum_{j=1}^n e^{z_j}}$$ 其中zi是神经网络输出的第i个节点的实数值,n是输出节点的数量。softmax函数的输出满足概率分布的性质,即所有输出值之和为1,并且每个输出值都在0到1之间。
初次看到这一形式,必然感到很困惑,凭什么是指数函数?凭什么是e?凭什么是softmax?实际上,使用softmaxmax拟合概率有一定的道理。
- 从物理学的角度来说,softmax与多种能级的气体玻尔兹曼分布形式一模一样
- 从熵的角度来说,若认定输出的zi就是能量,在能量期望守恒的条件下,softmax就不做任何假设,仅从最大熵原理得出的概率分布形式
- 从数值计算的角度来说,softmax函数可以有效地将实数值映射到概率分布,避免了数值计算中的溢出问题。同时,若使用softmax与交叉熵结合,导数形式比较简单:
$$\begin{aligned}l(\mathbf{y},\hat{\mathbf{y}})&=-\sum_{j=1}^qy_j\log\frac{\exp(o_j)}{\sum_{k=1}^q\exp(o_k)}\\&=\sum_{j=1}^qy_j\log\sum_{k=1}^q\exp(o_k)-\sum_{j=1}^qy_jo_j\\&=\log\sum_{k=1}^q\exp(o_k)-\sum_{j=1}^qy_jo_j.\end{aligned}$$
$$\partial_{o_j}l(\mathbf{y},\hat{\mathbf{y}})=\frac{\exp(o_j)}{\sum_{k=1}^q\exp(o_k)}-y_j=\mathrm{softmax}(\mathbf{o})_j-y_j.$$
它的梯度正好是目标分布与预测分布之差,只要两者不相等,那么梯度就一直存在,优化就可以持续下去,这是交叉熵的优点。当然,某些情况下这也是缺点,因为Softmax只有在误差几乎为0的时候才会得到one hot,换言之正常情况下都不会出现one hot,即优化一直不会完全停止,那么就有可能导致过度优化,这也是一些替代品的动机。
Appendix
Proof.1:softmax形式上的深刻意义
机器学习对应
设神经网络输出为 o = (o1, o2, …, oq),我们需要将其转换为概率分布 p = (p1, p2, …, pq)。从三条基本假设开始推导
- 概率归一化:$\sum_{i=1}^q p_i = 1$
- 特征期望约束:$\mathbb{E}_p[o_i] = \sum_{i=1}^q p_i o_i = \mu_o$ 其中 μo 是模型输出的期望值。这一点相当于物理里面的能量守恒。
- 最大熵原理
优化目标
最大化熵: $$H(p) = -\sum_{i=1}^q p_i \ln p_i$$ 引入拉格朗日函数 ℒ = −∑ipiln pi + λ(1 − ∑ipi) + β(μo − ∑ipioi) 对 pk 求偏导: $$\frac{\partial \mathcal{L}}{\partial p_k} = -\ln p_k - 1 - \lambda - \beta o_k = 0$$ ln pk = −βok − 1 − λ pk = e−βok ⋅ e−1 − λ 令 C = e−1 − λ,则: ∑kpk = C∑ke−βok = 1 $$C = \frac{1}{\sum_{i=1}^q e^{-\beta o_i}}$$ $$p_k = \frac{e^{-\beta o_k}}{\sum_{i=1}^q e^{-\beta o_i}}$$ 在深度学习中: - 取 β = −1(相当于负温度参数) - 定义 ok 为模型输出值 得到: $$\boxed{p_k = \frac{e^{o_k}}{\sum_{i=1}^q e^{o_i}}}$$
统计力学对应
在正则系综中,状态 k 的概率为: $$p_k = \frac{e^{-E_k/kT}}{Z}$$
其中: - Ek = 状态 k 的能量 - T = 系统温度 - k = 玻尔兹曼常数 - Z = ∑e−Ei/kT = 配分函数
令: - ok = −Ek(模型输出表示负能量) - kT = 1(单位温度)
则: $$p_k = \frac{e^{o_k}}{\sum e^{o_i}} = \text{softmax}(o_k)$$
玻尔兹曼能级分布描述了在热平衡状态下,粒子在不同能级上的分布情况,通常用玻尔兹曼因子表示。一个物理学系统天然满足最大熵原理。
Proof.2
最大熵原理往往结合一定的先验假设或者约束条件来推导出概率分布。 常用的假设为 E[f(x)] = ∑xp(x)f(x) = τ 当f(x) = x,式子变为物理中的能量守恒。
在k个这样的假设下,原问题的拉格朗日函数可以写为 $$\begin{gathered}-\sum_xp(x)\log p(x)-\lambda_0\left(\sum_xp(x)-1\right)-\lambda_1\left(\sum_xp(x)f_1(x)-\tau_1\right)\\-\cdots-\lambda_k\left(\sum_xp(x)f_k(x)-\tau_k\right)\end{gathered}$$
解得 $$\begin{aligned}p(x)&=\frac{1}{Z}\mathrm{exp}{\left(-\sum_{i=1}^k\lambda_if_i(x)\right)}\\\\\\Z&=\sum_x\exp{\left(-\sum_{i=1}^k\lambda_if_i(x)\right)}\end{aligned}$$
带入约束条件 ∑xp(x)fi(x) − τi = 0, (i = 1, 2, …, k) 可以求得拉格朗日系数,但实际上很难求得,需要付出昂贵的数值计算代价。
$$\frac{n_i}{N}=\frac{g_i/\left[e^{(\varepsilon_i-\mu)/(k_BT)}-1\right]}{\sum_jg_j/\left[e^{(\varepsilon_j-\mu)/(k_BT)}-1\right]}$$
参考文献
熵的推导与最大熵模型 - https://spaces.ac.cn/archives/3534 - https://spaces.ac.cn/archives/3552 - https://spaces.ac.cn/archives/3567 - https://www.zhihu.com/search?type=content&q=softmax%E7%9A%84%E6%9C%AC%E8%B4%A8
application - https://spaces.ac.cn/archives/3638 - 从理论上证明,排序算法的时间复杂度不可能更优于O(nlogn)
为什么是交叉熵?,谈KL散度与交叉熵 - 理论联系:https://zhuanlan.zhihu.com/p/573385147
玻尔兹曼分布,玻色分布和爱因斯坦分布 - https://wuli.wiki/online/MBsta.html