人工智能AI面试题-3.28最⼤⽔熵模型中的数学推导

3.28 最⼤⽔💧熵模型中的数学推导 💡 0 引⾔ 🚀 写完SVM之后，⼀直想继续写机器学习的系列，⽆奈⼀直时间不稳定且对各个模型算法的理解尚不够，所以导致迟迟未动笔。⽆独有偶，重写KMP得益于今年4⽉个⼈组织的算法班，⽽动笔继续写这个机器学习系列，正得益于今年10⽉组织的机器学习班。  📅 10⽉26⽇机器学习班第6次课，邹讲最⼤⽔💧熵模型，从熵的概念，讲到为何要最⼤⽔💧熵、最⼤⽔💧熵的推导，以及求解参数的IIS⽅法，整个过程讲得⾮常流畅，特别是其中的数学推导。晚上我把上课PPT 在微博上公开分享了出来，但对于没有上过课的朋友直接看PPT 会感到⾮常跳跃，因此我打算针对机器学习班的某些次课写⼀系列博客，刚好也算继续博客中未完的机器学习系列。综上，本⽂结合10⽉机器学习班最⼤⽔💧熵模型的PPT和其它相关资料写就，可以看成是课程笔记或学习⼼得，着重推导。有何建议或意见，欢迎随时于本⽂评论下指出，thanks. 1 预备知识 📚 为了更好的理解本⽂，需要了解的概率必备知识有： ⼤写字母X表⽰随机变量，⼩写字母x表⽰随机变量X的某个具体的取值； P(X)表⽰随机变量X的概率分布，P(X,Y)表⽰随机变量X、Y的联合概率分布，P(Y|X)表⽰已知随机变量X的情况下随机变量Y的条件概率分布； p(X = x)表⽰随机变量X取某个具体值的概率，简记为p(x)； p(X = x, Y = y) 表⽰联合概率，简记为p(x,y)，p(Y = y|X = x)表⽰条件概率，简记为p(y|x)，且有： p(x,y) = p(x) * p(y|x)。 需要了解的有关函数求导、求极值的知识点有： 如果函数y=f(x)在[a, b]上连续，且其在(a,b)上可导，如果其导数f’(x) >0，则代表函数f(x)在[a,b]上单调递增，否则单调递减；如果函数的⼆阶导f''(x) > 0，则函数在[a,b]上是凹的，反之，如果⼆阶导f''(x) < 0，则函数在[a,b]上是凸的。 设函数f(x)在x0处可导，且在x处取得极值，则函数的导数F’(x0) = 0。 以⼆元函数z = f(x,y)为例，固定其中的y，把x看做唯⼀的⾃变量，此时，函数对x的导数称为⼆元函数z=f(x,y)对x的偏导数。 为了把原带约束的极值问题转换为⽆约束的极值问题，⼀般引⼊拉格朗⼇乘⼦，建⽴拉格朗⼇函数，然后对拉格朗⼇函数求导，令求导结果等于0，得到极值。 更多请查看《⾼等数学上下册》、《概率论与数理统计》等教科书，或参考本博客中的：数据挖掘中所需的概率论与数理统计知识。 2 何谓熵？ 🕵️‍♂️ 从名字上来看，熵给⼈⼀种很⽞乎，不知道是啥的感觉。其实，熵的定义很简单，即⽤来表⽰随机变量的不确定性。之所以给⼈⽞乎的感觉，⼤概是因为为何要取这样的名字，以及怎么⽤。熵的概念最早起源于物理学，⽤于度量⼀个热⼒学系统的⽆序程度。在信息论⾥⾯，熵是对不确  定性的测量。 🔍 2.1 熵的引⼊ 事实上，熵的英⽂原⽂为entropy，最初由德国物理学家鲁道夫·克劳修斯提出，其表达式为： \[H(X) = - \sum_{i=1}^{k} p(x_i) \log p(x_i)\] 它表⽰⼀个系系统在不受外部⼲扰时，其内部最稳定的状态。后来⼀中国学者翻译entropy时， 考  虑到entropy是能量Q跟温度T的商，且跟⽕有关，便把entropy形象的翻译成“熵”。我们知道，任何粒⼦的常态都是随机运动，也就是"⽆序运动"，如果让粒⼦呈现"有序化"，必须耗费能量。所以，温度（热能）可以被看作"有序化"的⼀种度量，⽽"熵"可以看作是"⽆序化"的度量。 如果没有外部能量输⼊，封闭系统趋向越来越混乱（熵越来越⼤）。⽐如，如果房间⽆⼈打扫，不可能越来越⼲净（有序化），只可能越来越乱（⽆序化）。⽽要让⼀个系统变得更有序，必须有外部能量的输⼊。 1948年，⾹农Claude E. Shannon引⼊信息（熵），将其定义为离散随机事件的出现概率。⼀个系统越是有序，信息熵就越低；反之，⼀个系统越是混乱，信息熵就越⾼。所以说，信息熵可以被认为   是系统有序化程度的⼀个度量。 若⽆特别指出，下⽂中所有提到的熵均为信息熵。 📊 2.2 熵的定义 下⾯分别给出熵、联合熵、条件熵、相对熵、互信息的定义。   🔥 熵：如果⼀个随机变量X的可能取值为X = {x1, x2,…, xk}，其概率分布为P(X = xi) = pi（i = 1,2, ..., n），则随机变量X的熵定义为： \[H(X) = - \sum_{i=1}^{k} p(x_i) \log p(x_i)\] 把最前⾯的负号放到最后，便成了： \[H(X) = \sum_{i=1}^{k} p(x_i) \log \frac{1}{p(x_i)}\] 上⾯两个熵的公式，⽆论⽤哪个都⾏，⽽且两者等价，⼀个意思（这两个公式在下⽂中都会⽤到。 联合熵：两个随机变量X，Y的联合分布，可以形成联合熵Joint Entropy，⽤H(X,Y)表⽰。 🤔 条件熵：在随机变量X发⽣的前提下，随机变量Y发⽣所新带来的熵定义为Y的条件熵，⽤H(Y|X)表⽰，⽤来衡量在已知随机变量X的条件下随机变量Y的不确定性。 且有此式⼦成⽴：\[H(Y|X) = H(X,Y) – H(X)\]，整个式⼦表⽰(X,Y)发⽣所包含的熵减去X单独发⽣包含的熵。⾄于怎么得来的请看推导：   简单解释下上⾯的推导过程。整个式⼦共6⾏，其中 第⼆⾏推到第三⾏的依据是边缘分布p(x)等于联合分布p(x,y)的和； 第三⾏推到第四⾏的依据是把公因⼦logp(x)乘进去，然后把x,y写在⼀起； 第四⾏推到第五⾏的依据是：因为两个sigma都有p(x,y)，故提取公因⼦p(x,y)放到外边，然后把⾥边的-\(log p(x,y) - log p(x)\)写成-\(log \frac{p(x,y)}{p(x)}\) ； 第五⾏推到第六⾏的依据是：\(p(x,y) = p(x) * p(y|x)\)，故\(\frac{p(x,y)}{p(x)} = p(y|x)\)。 📊 相对熵：又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等。设p(x)、q(x)是X中 取值的两个概率分布，则p对q的相对熵是：   \[D(p||q) = \sum_{i=1}^{k} p(x_i) \log \frac{p(x_i)}{q(x_i)}\] 在⼀定程度上，相对熵可以度量两个随机变量的“距离”，且有\[D(p||q) \neq D(q||p)\]。另外，值得⼀提的是，\[D(p||q)\]是必然⼤于等于0的。 🤝 互信息：两个随机变量X，Y的互信息定义为X，Y的联合分布和各⾃独⽴分布乘积的相对熵，⽤ \[I(X,Y) = D(P(X,Y) || P(X)P(Y))\] 表⽰：   通过上⾯的计算过程，我们发现竟然有\[H(Y) - I(X,Y) = H(Y|X)\]。故通过条件熵的定义，有：\[H(Y|X) = H(X,Y) - H(X)\]，⽽根据互信息定义展开得到\[H(Y|X) = H(Y) - I(X,Y)\]，把前者跟后者结合起来，便有\[I(X,Y)= H(X) + H(Y) - H(X,Y)\]，此结论被多数⽂献作为互信息的定义。 💡 3 最⼤熵 熵是随机变量不确定性的度量，不确定性越⼤，熵值越⼤；若随机变量退化成定值，熵为0。如果没有外界⼲扰，随机变量总是趋向于⽆序，在经过⾜够时间的稳定演化，它应该能够达到的最⼤程度的熵。 为了准确的估计随机变量的状态，我们⼀般习惯性最⼤化熵，认为在所有可能的概率模型（分布）   的集合中，熵最⼤的模型是最好的模型。换⾔之，在已知部分知识的前提下，关于未知分布最合理的推断就是符合已知知识最不确定或最随机的推断，其原则是承认已知事物（知识），且对未知事物不做任何假设，没有任何偏见。 例如，投掷⼀个骰⼦，如果问"每个⾯朝上的概率分别是多少"，你会说是等概率，即各点出现的概率均为1/6。因为对这个"⼀⽆所知"的⾊⼦，什么都不确定，⽽假定它每⼀个朝上概率均等则是最合   理的做法。从投资的⾓度来看，这是风险最⼩的做法，⽽从信息论的⾓度讲，就是保留了最⼤的不确定性，也就是说让熵达到最⼤。 💡 3.2 最⼤熵模型的表⽰ ⾄此，有了⽬标函数跟约束条件，我们可以写出最⼤熵模型的⼀般表达式了，如下： \[P(y|x) = \frac{1}{Z(x)} \exp \left( \sum_{i=1}^{n} \lambda_i f_i(x,y) \right)\] 其中，P={p | p是X上满⾜条件的概率分布} 继续阐述之前，先定义下特征、样本和特征函数。特征：(x,y) y：这个特征中需要确定的信息x：这个特征中的上下⽂信息 样本：关于某个特征(x,y)的样本，特征所描述的语法现象在标准集合⾥的分布：(xi,yi)对，其中， yi是y的⼀个实例，xi是yi的上下⽂。 对于⼀个特征(x0,y0)，定义特征函数： \[f_i(x,y) = \begin{cases} 1 & \text{如果特征i在(x,y)中出现} \\ 0 & \text{否则} \end{cases}\] 特征函数关于经验分布P-在样本中的期望值是： \[E_{P^-}[f_i(x,y)] = \frac{1}{N} \sum_{j=1}^{N} f_i(x_j, y_j)\] 其中，N是样本的总数。 特征函数关于模型P(Y|X)与经验分布P-(X)的期望值为： \[E_{P(Y|X)P^-(X)}[f_i(x,y)] = \sum_{x \in X} \sum_{y \in Y} P(x) P(y|x) f_i(x,y)\] 换⾔之，如果能够获取训练数据中的信息，那么上述这两个期望值相等，即： \[E_{P^-}[f_i(x,y)] = E_{P(Y|X)P^-(X)}[f_i(x,y)]\] 不过，因为实践中p(x)不好求，所以⼀般⽤样本中x出现的概率"p(x)-"代替x在总体中的分布概率 “p(x)”，从⽽得到最⼤熵模型的完整表述如下： \[P(y|x) = \frac{1}{Z(x)} \exp \left( \sum_{i=1}^{n} \lambda_i f_i(x,y) \right)\] 其约束条件为： \[\sum_{y \in Y} P(y|x) = 1, \forall x \in X\] 该问题已知若⼲条件，要求若⼲变量的值使到⽬标函数（熵）最⼤，其数学本质是最优化问题 （Optimization Problem），其约束条件是线性的等式，⽽⽬标函数是⾮线性的，所以该问题属于⾮线性规划（线性约束）(non-linear programming with linear constraints)问题，故可通过引⼊Lagrange函数将原带约束的最优化问题转换为⽆约束的最优化的对偶问题。 🔥 3.3 凸优化中的对偶问题 考虑到机器学习⾥，不少问题都在围绕 凸优化，故我们以机器学习⾥经常出现的对偶问题来说。特别是在线性SVM，LR等机器学习⽂献⾥，都会涉及到对偶问题。在此仅以⼀个小⽐喻简单说明： 在最优化问题中，往往存在⼀个原始问题（Primal Problem）和⼀个对偶问题（Dual Problem）。原始问题的求解往往是⾼维度问题，⽽对偶问题通常⽐较低维度，因此往往容易求解。更重要的是，解对偶问题有助于理解原始问题，解决原始问题。因此，⽆论是理论分析还是计算求解，对偶问题都具有重要意义。 举⼀个例⼦，考虑⼀个线性分类问题，给定样本集合D = {(x1, y1), (x2, y2), ..., (xn, yn)}，其中xi ∈ R^n 表⽰第i个样本，yi ∈ {-1, 1} 表⽰第i个样本的类别，线性分类模型的假设函数可表示为： \[f(x) = sign(w \cdot x + b) \] 其中，w ∈ R^n 是权值向量，b ∈ R 是偏置，sign()是符号函数。最小化线性分类模型的损失函数可写成以下形式： \[min_{w,b} L(w,b) = \sum_{i=1}^{n} L(w,b) = \sum_{i=1}^{n} max(0, -y_i(w \cdot x_i + b)) \] 其中，L(w,b)是损失函数，max(0, -y_i(w \cdot x_i + b)) 是经典的hinge loss。 这是一个典型的支持向量机（Support Vector Machine，SVM）的优化问题，其原始问题是在所有w和b的组合中找到一个最优解，使得损失函数L(w,b)最小。然而，这个问题的求解可能会非常复杂，因为w和b都是高维的参数。 为了简化问题，我们可以引入对偶问题。对偶问题的目标是找到一组拉格朗日乘子α_i，其中i = 1, 2, ..., n，使得在满足一些条件的情况下，原始问题的最优值等于对偶问题的最优值。对偶问题的形式通常更简单，因为它涉及到的参数更少。 对于上面的SVM问题，对偶问题的形式如下： \[max_{\alpha} W(\alpha) = \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j x_i \cdot x_j \] 其中，α_i 是拉格朗日乘子，W(α) 是对偶问题的目标函数，x_i 和 x_j 是样本集合中的样本，y_i 和 y_j 是对应样本的类别，n 是样本的数量。通过求解对偶问题，我们可以得到原始问题的最优解，即权值向量 w 和偏置 b。 总结一下，对偶问题是一个在原始问题的约束条件下寻找最优解的问题，通常情况下，对偶问题的形式更简单，因为它涉及的参数更少。解决对偶问题可以帮助我们理解原始问题，并且在某些情况下更容易求解。在机器学习中，对偶问题经常出现在支持向量机等模型中的优化问题中，对于理论分析和求解算法都具有重要意义。 ⛏ 3.4 最⼤⽔💧熵模型的对偶问题 最⼤⽔💧熵模型的对偶问题定义如下： \[max_{\lambda_i} W(\lambda) = \sum_{i=1}^{n} \lambda_i - \frac{1}{N} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_i \lambda_j p(y_i, x_i, x_j, y_j) \sum_{x \in X} p^-(x) f(x, y_i) f(x, y_j) \] 其中， n是特征函数的数量； N是样本的总数； λ_i 是拉格朗日乘子，对应于每个特征函数； W(λ) 是对偶问题的目标函数； p(y_i, x_i, x_j, y_j) 是联合分布的概率； p^-(x) 是样本中 x 出现的概率； f(x, y) 是特征函数。 对偶问题的目标是找到一组拉格朗日乘子λ_i，使得目标函数W(λ)最大化。通过求解对偶问题，我们可以得到最大熵模型的参数λ_i，进而得到条件概率分布P(y|x)。 总结：最大熵模型是一种用于分类和回归的机器学习模型，其核心思想是在满足已知约束条件的情况下，选择使熵最大化的模型。熵是用来度量随机变量的不确定性的，最大熵模型的目标是找到一个概率分布，使得在满足约束条件的情况下，系统的不确定性最大。最大熵模型的参数可以通过求解对偶问题来获得，该问题通常涉及拉格朗日乘子的求解。最大熵模型在自然语言处理等领域广泛应用，它可以用来解 决文本分类、语言模型等问题。