文章目录
  1. 1. 最大熵原理
  2. 2. 最大熵模型介绍
  3. 3. 最大熵模型学习
    1. 3.1. 原始问题与对偶问题
    2. 3.2. 指数形式求解
    3. 3.3. 最大似然估计
  4. 4. 总结
  5. 5. 参考

最大熵原理

:其物理意义是体系混乱程度的衡量,在热力学中越大表示物质越混乱,但同时也为越稳定~
现假设离线随机变量$X$的概率分布为$P(X)$,则其熵为定义为:
$$H(P)= -\sum_x P(x) \text{log} P(x)$$

当$X$为均匀分布时,熵值最大:

上图是两个类别的示例,可以看到这两个类别的概率一样时其熵值最大

在机器学习领域,我们通常以最小化风险为目标,其实就是将熵进行最大化.
最大熵模型亦是如此,直观的说,最大熵模型就是在满足现有的约束条件之下,将那部分不确定的都设为等可能(熵最大)
下面看一个简单的例子:
假设现在有一个随机变量$X$可能取值为$\{A,B,C\}$,现在需要来估计各个值的概率:$P(A)$,$P(B)$,$P(C)$

其实这些概率值肯定会满足如下条件:
$$P(A)+P(B)+P(C)=1$$
但是满足这个约束条件的概率分布有无限多个,如果没有其他信息的条件下,则取值风险最小的方法是:
$$P(A)=P(B)=P(C)=\frac{1}{3}$$
现告诉你取$P(A)$的概率为$\frac{1}{2}$,则根据熵最大的原理其他两个概率取值将会为
$$P(B) = P(C) = \frac{1}{4}$$
也就是$B$和$C$是等概率的,假如接下来还有其他可知的约束条件的话,在满足其他约束条件的情况下继续进行等概率分布.上面的整个划分的过程也就是遵循了最大熵原理

现假如用欧式空间的单纯形来表示随机变量$X$的话,定义单纯形中的任意一点到$x$到达相应顶点对应边的距离为取值概率,并且三边距离之和为1,这两种取值情况:
$$P(A)=1,P(B)=P(C)=0 \\
P(A)=P(B)=P(C)=\frac{1}{3}$$
可以依次使用下面两个图来表示

知道了上面单纯形的表示方法之后,根据下图其最大熵原理可以得到如下的刻画:

  1. 不加任何约束的时候,可以用图(a)表示,整个取值空间为单纯形上的任何一点,只需要找到熵最大的情况即可
  2. 当添加约束C1的时候,将需要在满足C1的情况下再寻找熵最大的取值(也就是图(b))
  3. 图(c)表示在图(b)的C1基础上继续增加了C2的约束,此时对两个约束进行了满足之后取值空间将会被固定在C1和$C2$的交点上,只有一个唯一解
  4. 假设图(d)里面在C1的基础了增加了C2,但是此时C1C2并无交点,在这两者约束下将会无解

最大熵模型介绍

最大熵模型其实就是在满足已有约束的条件下求得熵最大的过程,最终会转为一个解约束最优化的问题

现将最大熵原理应用到分类的最大熵模型:
假设现有训练数据集
$$T=\{(x_1,y_1),(x_2,y_2),….(x_n,y_n)\}$$
最大熵模型就是分别根据已有的输入$X$和输出$Y$集合去学习训练数据的条件概率分布$P(y|x)$,应用最大熵原理去学习分类能力最好的模型.
根据最大熵原理,是需要在满足约束的情况对已有数据求得熵最大,那在最大熵分类模型里面的约束条件又是啥呢?

对于给定的训练数据集,我们可以确定联合分布$P(X,Y)$的经验分布$\tilde{P}(X,Y)$以及边缘分布$P(X)$的经验分布$\tilde{P}(X)$,即:
$$\tilde{P}(X=x,Y=y)=\frac{count(X=x,Y=y)}{N} \\ \tilde{P}(X=x) = \frac{count(X=x)}{N}$$

其中$count(\cdot)$表示满足条件在样本中的计数,$N$表示总的训练样本容量

现在引入特征函数$f(x,y)$,它是描述输入$x$与输出$y$之间满足的某一事实,为了方便起见,我们将$f(x,y)$定义为二值函数:
$$ f(x,y)=\left\{
\begin{aligned}
1 & \quad \text{x,y满足某一事实} \\
0 & \quad \text{否则} \\
\end{aligned}
\right.$$

上面的特征函数比较抽象,下面借用别人的栗子来说明一下:
假设我们需要来判断字是量词还是动词,目前有下面的训练数据集:
$$
(x_1,y_1) = (\text{一打火柴},\text{量词}) \\
(x_2,y_2) = (\text{三打啤酒},\text{量词}) \\
(x_3,y_3) = (\text{五打袋子},\text{量词}) \\
(x_4,y_4) = (\text{打电话},\text{动词}) \\
(x_5,y_5) = (\text{打篮球},\text{动词})
$$
通过观察我们可以发现前面位数字时,量词,如果后面跟着的是名词,则打为动词,为基于刚刚观察的两个实时我们用特征函数来表示则为:
$$ f_1(x,y)=\left\{
\begin{aligned}
1 & \quad \text{“打”的前面为数字} \\
0 & \quad \text{否则} \\
\end{aligned}
\right.$$
$$ f_2(x,y)=\left\{
\begin{aligned}
1 & \quad \text{“打”的后面为名词} \\
0 & \quad \text{否则} \\
\end{aligned}
\right.$$
有了特征函数之后,我们将现有的数据代入这两个特征函数即有:
$$f_1(x_1,y_1) = f_1(x_2,y_2) = f_1(x_3,y_3) = 1,f_1(x_4,y_4) = f_1(x_5,y_5) = 0 \\
f_2(x_1,y_1) = f_2(x_2,y_2) = f_2(x_3,y_3) = 0,f_2(x_4,y_4) = f_2(x_5,y_5) = 1
$$

对于任意的特征函数$f(x,y)$,
现记$E_{\tilde{P}}(f)$表示特征函数$f$在训练数据集$T$上关于$\tilde{P}(x,y)$的数学期望,有:
$$E_{\tilde{P}}(f) = \sum_{x,y} \tilde{P}(x,y) f(x,y)$$
另记$E_{P}(f)$表示特征函数$f$在训练数据集$T$上关于$P(x,y)$的数学期望,有:
$$E_{P}(f) = \sum_{x,y} P(x,y) f(x,y)$$
但是$P(x,y)$是未知的,而我们的目标是为了计算$P(y|x)$,根据Bayes我们可以做如下转换
$$P(x,y) = P(y|x) \cdot p(x)$$
虽说$p(x)$仍为未知,但是我们此时可以使用$\tilde{P}(x)$进行近似,也就是最终有:
$$E_{P}(f) = \sum_{x,y} P(y|x) \tilde{P}(x) f(x,y)$$

我们希望上述两个期望值是一值的(应该也是符合既定事实的吧?),这样就会有:
$$E_{\tilde{P}}(f) = E_{P}(f)$$
或者
$$ \sum_{x,y} \tilde{P}(x,y) f(x,y) = \sum_{x,y} P(y|x) \tilde{P}(x) f(x,y)$$

上述式子就可以作为模型的约束条件,假如有$n$个特征函数,则就会有$n$个约束条件(实际中一般特征的维度就是约束条件的个数)
用$C$来表示满足约束的模型集合:
$$C=\{P|E_{\tilde{P}}(f) = E_{P}(f),I=1,2,3..n\}$$
满足约束条件同时使用$P(y|x)$的熵最大的模型即为最大熵模型~

到了这里我们还差一个熵的定义,我们的目标是为了获取条件概率的分布,因为也使用了相应的条件熵
$$H(P)= - \sum_{x,y} \tilde{P}(x) P(y|x) log P(y|x)$$

向上面一样,$P(x)$用$\tilde{P}(x)$进行了近似

这样我们就可以给出最大熵模型的完成公式描述了:
$$
\begin{align}
\underset{P \in C}{max} &\quad H(P) = - \sum_{x,y} \tilde{P}(x) P(y|x) \text{log} P(y|x) \\
st. &\quad E_{P}(f) = E_{\tilde{P}}(f),I=1,2,3..n \\
&\quad \sum_y P(y|x)=1
\end{align}
$$

最大熵模型学习

最大熵模型的学习就是求解最大熵的过程,按照优化的习惯,我们一般会将最大化问题转为最小化再进行优化:
$$
\begin{align}
\underset{P \in C}{min} &\quad -H(P) = \sum_{x,y} \tilde{P}(x) P(y|x) \text{log} P(y|x) \\
st. &\quad E_{\tilde{P}}(f)- E_{P}(f) = 0,I=1,2,3..n \\
&\quad 1-\sum_y P(y|x)=0
\end{align}
$$

接下来我们求解的思路是:

  1. 接下来的求解方式是利用拉格朗日乘子将带约束的最优化问题转为等价无约束优化,它是一个极小极大问题
  2. 然后利用对偶的等价性,将上述极小极大问题转为对偶的极大极小问题

原始问题与对偶问题

首先我们引入拉格朗日乘子$w_0,w_1,w_2….w_n$,定义拉格朗日函数为$L(P,W)$
$$
\begin{align}
L(P,W) &= -H(P) + w_0\left(1-\sum_y P(y|x) \right) + \sum_{i=1}^n w_i\left( E_{\tilde{P}}(f)- E_{P}(f) \right) \\
&= \sum_{x,y} \tilde{P}(x) P(y|x) \text{log} P(y|x) + w_0\left(1-\sum_y P(y|x) \right) \\
&\quad + \sum_{i=1}^n w_i\left( \sum_{x,y} \tilde{P}(x,y) f(x,y)- \sum_{x,y} P(y|x) \tilde{P}(x) f(x,y) \right)
\end{align}
$$

则最优化的原始问题为:
$$\underset{P \in C}{\text{min}} \underset{W}{\text{max}} L(P,W)$$
则转为等价的对偶问题为:
$$ \underset{W}{\text{max}} \underset{P \in C}{\text{min}} L(P,W)$$

其中$L(P,W)$是关于$P$的凸函数,那我们首先求对偶的极小化部分$ \underset{P \in C}{\text{min}} L(P,W)$,它是关于$W$的函数,将其记为:
$$\varphi(w) = \underset{P \in C}{\text{min}} L(P,W) = L(P_w,W)$$
其中
$$P_w = \underset{P \in C}{\text{argmin}} L(P,W) = P_w(y|x)$$

关于这里,我认为我们需要求解的是$P(y|x)$,同时可以将$L(P,W)$看为关于$P(y|x)$的函数,所以为了上面的解,需要下面的偏导~

指数形式求解

先对$L(P,W)$求$P(y|x)$的偏导,
$$
\begin{align}
\frac{\delta L(P,W)}{\delta P(y|x)} &= \left( \sum_{x,y} \tilde{P}(x) \text{log} P(y|x) + \sum_{x,y} \tilde{P}(x) \right) - \sum_yw_0 -\sum_{i=1}^n w_i \tilde{P}(x) f_i(x,y) \\
&= \sum_{x,y} \tilde{P}(x) \left( \text{log} P(y|x) + 1-w_0- \sum_{i=1}^n w_i f_i(x,y) \right)
\end{align}
$$

这里对于$\tilde{P}(x)>0$,在求最小值是其偏导数为0,因此会有:
$$P(y|x) = e^{\sum_{i=1}^n w_i f_i(x,y)+w_0-1} = \frac{e^{\sum_{i=1}^n w_i f_i(x,y)}}{e^{1-w_0}}$$

因为有$\sum_yP(y|x)=1$,则可以有:
$$e^{1-w_0} = \sum_y e^{\sum_{i=1}^n w_i f_i(x,y)} $$
最终我们可以将$P_w(y|x)$表示为:
$$P_w(y|x) = \frac{1}{Z_w(x)} e^{\sum_{i=1}^n w_i f_i(x,y)} $$
其中
$$Z_w(x) = \sum_y e^{\sum_{i=1}^n w_i f_i(x,y)}$$

$Z_w(x)$被称为规范化因子,上面样式的算分与逻辑回归非常相似,所以又称为对数线性模型,同时又经过了规范化因子之后可以发现其最后的算分与Softmax极其相似

这里上面两个式子就是表示$P_w = P_w(y|x)$的最大熵模型,其中向量$W$即为模型的参数
现在求解了内部的极小化之后,还需要求解外部的极大化
$$\underset{w}{\text{max}} \varphi(W) $$
其解标记为$W^{*}$
$$W^{*} = \underset{w}{\text{max}} \varphi(W) $$
模型参数$W^{*}$就是对对偶的极大化,得到的$W^{*}$可以表示为$W^{*} \in C$,最终$P_{w^{*}} = P_{w^{*}}(y|x)$即为模型的最终解。也就是最大熵模型需要解对偶函数 $\varphi(W)$的极大化~

最大似然估计

在求解上面极大化之前,我们先来看下最大熵模型的极大似然法:
已知其经验概率分布$\tilde{P}(X,Y)$和其条件概率分布$P(Y|X)$,可以得到其对数似然函数为:
$$
\begin{align}
LL_{\tilde{P}}(P_w) &= \text{log} \prod_{x,y} P(y|x)^{\tilde{P}(x,y)} \\
&= \sum_{x,y} \tilde{P}(x,y) \text{log} P(y|x) \\
&= \sum_{x,y} \tilde{P}(x,y) \text{log} \frac{e^{\sum_{i=1}^n w_i f_i(x,y)}}{Z_w(x)} \\
&= \sum_{x,y} \tilde{P}(x,y) \text{log} e^{\sum_{i=1}^n w_i f_i(x,y)} - \sum_{x,y} \tilde{P}(x,y) \text{log} Z_w(x) \\
&= \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^n w_i f_i(x,y) - \sum_{x,y} \tilde{P}(x,y) \text{log} Z_w(x) \\
&= \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^n w_i f_i(x,y) - \sum_{x,y} \tilde{P}(x) \tilde{P}(y|x) \text{log} Z_w(x) \\
&= \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^n w_i f_i(x,y) - \sum_x \tilde{P}(x) {\color{Blue}{\sum_y \tilde{P}(y|x)}} \text{log} Z_w(x) \\
&= \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^n w_i f_i(x,y) - \sum_x \tilde{P}(x) \text{log} Z_w(x) \quad \text{利用} {\color{Blue} {\sum_y \tilde{P}(y|x)=1}}
\end{align}
$$

回头再将$P(y|x)$的解代入到对偶函数$\varphi(W)$中:
$$
\begin{align}
\varphi(w) &= \sum_{x,y} \tilde{P}(x) P(y|x) \text{log} P(y|x) + w_0\left(1-\sum_y P(y|x) \right) \\
&\quad + \sum_{i=1}^n w_i\left( \sum_{x,y} \tilde{P}(x,y) f(x,y)- \sum_{x,y} P(y|x) \tilde{P}(x) f(x,y) \right) \\
&= \sum_{x,y} \tilde{P}(x) P(y|x) \left(\sum_{i=1}^n w_i f_i(x,y) - \text{log}Z_w(x) \right) \\
&\quad + \sum_{i=1}^n w_i\left( \sum_{x,y} \tilde{P}(x,y) f(x,y)- \sum_{x,y} P(y|x) \tilde{P}(x) f(x,y) \right) \\
&= {\color{Red}{\sum_{x,y} \tilde{P}(x) P(y|x) \sum_{i=1}^n w_i f_i(x,y)}} - \sum_{x,y} \tilde{P}(x) P(y|x)\text{log}Z_w(x) \\
&\quad + \sum_{i=1}^n w_i \sum_{x,y} \tilde{P}(x,y) f(x,y)- {\color{Red}{\sum_{i=1}^n w_i \sum_{x,y} P(y|x) \tilde{P}(x) f(x,y)}} \\
&= \sum_{i=1}^n w_i \sum_{x,y} \tilde{P}(x,y) f(x,y) - \sum_x \tilde{P}(x) {\color{Blue}{\sum_y P(y|x)}} \text{log} Z_w(x) \\
&= \sum_{x,y} \tilde{P}(x,y)\sum_{i=1}^n w_i f(x,y) - \sum_x \tilde{P}(x)\text{log} Z_w(x)
\end{align}
$$

上面第一步的换算是借助了$\text{log} P(y|x) = \sum_{i=1}^n w_i f_i(x,y) - \text{log}Z_w(x)$,同时还有$\sum_y P(y|x)=1$

现在再来对比$\varphi(w)$与$LL_{\tilde{P}}(P_w)$最终的表达式,可以惊奇的发现:
$$\varphi(w) = LL_{\tilde{P}}(P_w)$$
于是就证明了对偶函数的极大化等于模型极大似然估计这一事实,这样模型学习就可以在给定训练数据条件下进行极大化似然估计~

总结

关于具体的解就不再详说了,既然是可以用最大似然法解,则其常用的解法有梯度下降法牛顿法或者还有专门的GIS法等,参考[2]

关于最大熵模型:

  1. 利用最大熵原理熵越大事物越混乱,其分类风险越小
  2. 为了防止其解空间太大,利用特征函数建立起约束
  3. 在求解模型时使用对偶的方式进行求解,先解最小化的负熵,再求极大化的对偶函数
  4. 解最小化负熵时可以得到最大熵模型最后的形式是指数形式,类似逻辑回归
  5. 又在求极大化对偶函数时,可以发现其对偶函数与模型的极大似然法形式一致
  6. 因此最终可以按极大似然法的方式去解决模型

参考

  1. 最大熵模型 Maximum Entropy Model
  2. 《统计学习方法》.李航 第6章
  3. 最大熵学习笔记
  4. 1996-A Maximum Entropy Approach

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可,我的博客欢迎复制共享,但在同时,希望保留我的署名权kubiCode,并且,不得用于商业用途。如您有任何疑问或者授权方面的协商,请给我留言

文章目录
  1. 1. 最大熵原理
  2. 2. 最大熵模型介绍
  3. 3. 最大熵模型学习
    1. 3.1. 原始问题与对偶问题
    2. 3.2. 指数形式求解
    3. 3.3. 最大似然估计
  4. 4. 总结
  5. 5. 参考