最大熵模型

1 最大熵思想

1. 最大熵模型指出，在预测一个样本或者一个事件的概率分布时，首先应当满足所有的约束条件，进而对未知的情况不做任何的主观假设。在这种情况下，概率分布最均匀，预测的风险最小，因此得到的概率分布的熵是最大。最大熵原理就是在满足已知条件的概率模型集合中，找到熵最大的模型。
2. 假设随机变量$X$有$5$个取值$\{A,B,C,D,E\}$，如果约束条件为$P(A)+ P(B)+ P(C)+ P(D)+ P(E)=1$。在没有其他任何信息的情况下要估计各个值的概率时，我们只能估计为等概率，即$P(A)=P(B)=P(C)=P(D)=P(E)=1/6$。且这种判断是合理的。若我们除此之外还有了其他约束条件时，如：$P(A)+P(B)=3/10$，那么我们可以认为$A$与$B$等概率，$C$、$D$、$E$是等概率的。

2 最大熵模型的定义

1. 已知数据集$\{(x_1, y_1), (x_2,y_2),...,(x_n,y_n)\}$, 其中$x_i$表示$n$维输入特征，$y_i$代表一共存在$k$个分类

2. 定义一个输出值为1、0的特征函数: $$f(x,y) = \left\{ \begin{matrix} 1, & 如果x,y满足条件\\ 0, & 否则 \end{matrix} \right.\\ 定义、p'(x,y), p'(x)分别为x,y的经验联合概率分布以及x的经验边缘分布\\ p'(x,y) = \frac{v(X=x,Y=y)}{N}, p'(x)=\frac{v(X=x)}{N}\\ E_{p'}(f) = \sum_{x,y} p'(x,y)f(x,y) \\ E_{p}(f)= \sum_{x,y} p(x,y)f(x,y) \approx \sum_{x,y} p'(x)p(y|x)f(x,y)\\ 经验分布与特征函数结合便能代表概率模型需要满足的约束，\\只需使得两个期望项相等:E_p(f) = E_{p'}(f)\\ \longrightarrow \sum_{x,y} p'(x)p(y|x)f(x,y) = \sum_{x,y} p'(x,y)f(x,y)\\ 这便构成了约束条件$$

3. 定义条件概率分布$P(Y|X)$上的条件熵为： $$H(Y|X) = -\sum_{x,y}p'(x)p(y|x)\log(p(y|x))$$

4. 形式定义 $$\min\ -H(Y|X)=\sum_{x,y}p'(x)p(y|x)\log(p(y|x))\\ s.t.\ E_p(f_i) - E_{p'}(f_i) = 0, \sum_{y}p(y|x) - 1= 0$$

3 最大熵模型求解

1. 拉格朗日乘子 $$L(w,p) = \sum_{x,y} p'(x)p(y|x)\log(p(y|x))\\ + w_0(1 - \sum_{y}p(y|x) ) + \sum_{i=1}^n w_i(\sum_{x,y} p'(x,y)f_i(x,y) - \sum_{x,y} p'(x)p(y|x)f_i(x,y))$$

2. 对偶问题 $$\frac{\partial L(P,w)}{\partial p(y|x)} =\sum_{x,y} p'(x)(\log(p(y|x))+1)-\sum_y w_0 - \sum_{x,y} (p'(x)\sum_{i=1}^nw_if_i(x,y))\\ = \sum_{x,y} p'(x)(\log(p(y|x))+1-w_0 -\sum_{i=1}^nw_if_i(x,y))=0\\ \longrightarrow p(y|x) = \exp(\sum_{i=1}^nw_if_i(x,y) +w_0-1)=\frac{\exp(\sum_{i=1}^nw_if_i(x,y))}{\exp(1-w_0)}$$

3. 归一化

$$\sum_{y}p(y|x) = 1 \rightarrow \sum_y\frac{\exp(\sum_{i=1}^nw_if_i(x,y))}{\exp(1-w_0)} = 1\\ \exp(1-w_0) = \sum_y\exp(\sum_{i=1}^nw_if_i(x,y))$$

• 最终结果

$$p_w(y|x) = \frac{1}{z_w(x)}\exp(\sum_{i=1}^nw_if_i(x,y))\\ z_w(x) = \sum_y\exp(\sum_{i=1}^nw_if_i(x,y))$$

• 得出了$P(y|x)$和$w$的关系，从而可以把对偶函数$ψ(w)$里面的所有的$P(y|x)$替换成用$w$表示，这样对偶函数$ψ(w)$就是全部用$w$表示了。接着我们对$ψ(w)$求极大化，就可以得到极大化时对应的w向量的取值，带入$p(y|x)$和$w$的关系式， 从而也可以得到$p(y|x)$的最终结果。 $$\begin{aligned} \Psi(w) &=\sum_{x,y}p'(x)p_w(y|x)\log p_w(y|x) + \sum^n_{i=1}w_i\left (\sum_{x,y}p'(x ,y)f(x,y) -\sum_{x,y}p'(x)p_w(y|x)f(x,y) \right )\\ &= \sum_{x,y} p'(x,y)\sum_{i=1}^nw_if_i(x,y) +\sum_{x,y}p'(x)p_w(y|x)\left (\log p_w(y|x) - \sum_{i=1}^nw_if_i(x,y) \right) \\ &=\sum_{x,y} p'(x,y)\sum_{i=1}^nw_if_i(x,y) +\sum_{x,y}p'(x)p_w(y|x)\log z_w(x)\\ &=\sum_{x,y} p'(x,y)\sum_{i=1}^nw_if_i(x,y) +\sum_xp'(x)\log z_w(x)\sum_yp_w(y|x)\\ &=\sum_{x,y} p'(x,y)\sum_{i=1}^nw_if_i(x,y) +\sum_xp'(x)\log z_w(x)\\ \end{aligned}$$

这是一个典型的凸优化问题。

4 最大熵模型与逻辑回归

1. 特征函数 $$f_i(x,y) = \left\{ \begin{matrix} g_i(x), & y =y_1\\ 0, &y = y_0 \end{matrix} \right.$$ 其中$g(x)$是当$y=1$是抽取的$x$的特征，可以每一个维度都有一个特征

2. 逻辑回归是最大熵模型的特殊情况 $$P(y_1|x) = \frac{\exp(\sum_{i=1}^n w_if_i(x,y_1))}{\exp(\sum_{i=1}^n w_if_i(x,y_0))+\exp(\sum_{i=1}^n w_if_i(x,y_1))} \\ = \frac{1}{1+\exp(-\sum_{i=1}^n w_if_i(x,y_1))}\\ P(y_0|x) = \frac{\exp(\sum_{i=1}^n w_if_i(x,y_0))}{\exp(\sum_{i=1}^n w_if_i(x,y_0))+\exp(\sum_{i=1}^n w_if_i(x,y_1))} \\ = \frac{1}{1+\exp(\sum_{i=1}^n w_if_i(x,y_1))} \\ = \frac{\exp(-\sum_{i=1}^n w_if_i(x,y_1))}{1+\exp(-\sum_{i=1}^n w_if_i(x,y_1))} = 1-P(y_1|x)$$