最大熵模型

2019-02-28 本文已影响81人 madao756

前言：艰难的最大熵模型。最大熵有很多很难的地方，这篇文章不会去讲预备知识，而是在这个知识出现的时候，先讲结论，再来叙述。这样做的目的就是你可以记住结论，跳过这一个模块。来吧，让我们开始

最大熵原理

最大熵原理是概率学习的一个准则，最大熵原理认为，学习概率模型时，在所有的概率模型分布中，熵最大的模型是最好的模型。

$H(P)=-\sum{P(x)logP(x)}$

要记住，我们训练就要使这个式子最大，得到 $P(x)$ 的分布。

条件熵

做分类的时候，我们不光有 x 还有 y 。也就是说，我们要做有条件的最大熵。这时引入条件熵。
结论：推导出条件熵的公式，训练使条件熵最大

一开始看这个式子的时候，搞不清楚 P(x, y) 和 P(y | x) 的区别。

其实

$P(x, y) = \frac{V(X=x, Y=y)}{N}$

$P(y | x) = \frac{P(x, y)}{P(x)}$

优化条件熵的约束

现在，我们的问题转换成

最大化：

$H(P)=-\sum_{x,y}{\overline P(x)P(y|x)logP(y|x)}$

但是习惯于最小化，所以变成

最小化：

$-H(P) = \sum_{x,y}{\overline P(x)P(y|x)logP(y|x)}$

约束：

$E_{p}(f_{i})=E_{\widetilde p}(f_{i})$
$\sum_{y}^{}{P(y|x)} = 1$

约束条件的由来

$E_{p}(f_{i})=E_{\widetilde p}(f_{i})$
等式左边是训练模型的期望，等式右边是由数据得出来的期望。
$E_{\widetilde p}(f_{i}) = \sum_{x, y}{\widetilde P(x,y)f(x,y)}$
$E_{p}(f_{i}) = \sum_{x, y}{\widetilde P(x)P(x|y)f(x,y)}$

约束条件下的优化

在约束条件下求函数最值，引入拉格朗日函数，文章篇幅不宜过长，我在另一篇文章介绍拉格朗日函数及其对偶性

先记住结论，由于拉格朗日函数及其对偶性，我们把约束条件和要最小化的函数整合到了一块。

最小化：
$L(P, w) = -H(P) + w_{0}(1-\sum_{y}{P(y|x)}) + \sum_{i=1}^{n}w_{i}(E_{p}(f_{i})-E_{\widetilde p}(f_{i}))$

其中：

$-H(P) = \sum_{x,y}{\overline P(x)P(y|x)logP(y|x)}$
$E_{\widetilde p}(f_{i}) = \sum_{x, y}{\widetilde P(x,y)f(x,y)}$
$E_{p}(f_{i}) = \sum_{x, y}{\widetilde P(x)P(x|y)f(x,y)}$

求导

对 $L(P, w)$ 求 $P(y|x)$ 导数，得到的 $P(y|x)$ 模型就是我们要求的模型，并记做 $P_{w}(y|x)$ 。

具体推导看《统计学习方法》，在这里补充他没有讲到的地方。

求导得到

$P_{w}(y|x) = \frac{exp(\sum_{i=1}^{n}w_{i}f_{i}(x,y))}{exp(1-w_{0})}$

记做

$P_w(y|x)=\frac{1}{Z_{w}(x)}exp(\sum_{i=1}^{n}w_{i}f_{i}(x,y))$

现在推导 $Z_w(x)$ :
$\because \sum_{y}^{}{P(y|x)} = 1$
$\therefore \sum_{y}{\frac{1}{Z_{w}(x)}exp(\sum_{i=1}^{n}w_{i}f_{i}(x,y))} = 1$
$\therefore Z_w(x) = \sum_{y}exp(\sum_{i=1}^{n}w_{i}f_{i}(x,y))$

在这里 $Z_w(x)$ 被称为规范因子， $w_i$ 是特征的权值， $P_{w}(y|x)$ 就是学习到的模型。

求解参数

通过上一步的求导，得到 $P_{w}(y|x)$ ，带入最上面提到的拉格朗日的函数。

最后对 $w$ 求导取零得到最优参数

直接求导等于零，太复杂了。不能直接求出解析解。我们要换个思路，在换个思路之前，我们要提一提极大似然估计

极大似然估计

不写公式推导了，《统计学习方法》写的很详细了
只需知道

学习到的最大熵模型
$P_{w}(y|x) = \frac{exp(\sum_{i=1}^{n}w_{i}f_{i}(x,y))}{exp(1-w_{0})}$
其中
$Z_w(x) = \sum_{y}exp(\sum_{i=1}^{n}w_{i}f_{i}(x,y))$
对数似然函数为
$L(w)=\sum_{x, y}\widetilde P(x, y)\sum_{i=1}^{n}w_if_i(x, y)-\sum_x\widetilde P(x)logZ_w(x)$

换个思路求最优参数

写到这里，离最后实现代码真的不远了，到最后自己实现的时候，代码真的不难，难的是里面的数学原理，太复杂了

这一节主要告诉你用改进的迭代尺度算法更新参数，具体证明我也不会，只需要知道如何更新参数就能完成代码了

算法（改进的迭代尺度算法IIS）

详见《统计学习方法》，在这里不详细叙述了

实现

GitHub

实现有一个很难的地方，不知道如何去计算

$P(y|x)$ 注意这里的 $P(y|x)$ x 是多个 x 和特征函数不同。 $f_i(x, y)$ 是键值对。是一个 x 对应一个 y。