最大熵模型

作者: MaosongRan | 来源:发表于2019-03-26 22:05 被阅读0次

最大熵模型详细解析 | 统计学习方法学习笔记 | 数据分析 |
熵
逻辑斯谛回归与最大熵模型
逻辑斯谛回归与最大熵模型
最大熵模型
Day 2080：学习
改进的迭代尺度法(IIS)详细解析 | 统计学习方法学习笔记 |
最大熵模型
最大熵模型
统计学习方法7.3 - 7.4笔记

GitHub
简书
 CSDN

1. 最大熵原理

最大熵模型（Maximum Entropy Model)是通过最大熵原理推导实现,那什么是最大熵原理？

熵是随机变量不确定性大的度量，不确定性越大，熵值越大；若随机变量变为定值，即某个值发生的概率为1，而其它事件都为0，此时熵值为0，均匀分布是熵值最大的分布，也即“最不确定的分布”。

假设离散随机变量 $X$ 的概率分布是 $P(X)$ ,则其熵为:

$H(P)=-\sum_{x}p(x)logp(x) \tag{1}$

熵满足如下条件:

$0 \leq H(P) \leq log|X|$
其中, $|X|$ 表示 $X$ 的取值，当 $X$ 的分布是均匀分布时，满足左边等号，当 $X$ 是确定事件时，满足左边的等号。

从上面可知，最大熵原理认为该求解的概率模型满足如下条件:

满足事先已约束的条件；
然后在满足这些条件的模型中选择熵最大的模型，即让不确定的信息等可能的发生；

2. 最大熵模型

将最大熵原理应用到分类问题中即得到最大熵模型。假设分类模型的一个条件概率分布 $P(Y|X)$ , $X\in\chi\subseteq R^n$ 表示输入， $X\in\gamma$ 表示输出。这个模型表示给定的输入 $X$ ,以条件概率 $P(Y|X)$ 输出 $Y$ 。

给定一个训练数据集

$T=\{(x_1, y_1), (x_2,y_2)...(x_N, y_N)\}$

学习的目标是用最大熵原理选择最好的模型。

对于给定训练数据集，我们可以确定联合分布 $P(X, Y)$ 的经验分布 $\tilde P(X,Y)$ 和边缘分布 $P(X)$ 的经验分布 $\tilde P(X)$ ,即：

$\tilde P(X=x, Y=x) = \frac{v(X=x, Y=y)}{N} \\ \tilde P(X=x) = \frac{X(X=x)}{N} \tag{2}$

其中， $v(X=x, Y=y)$ 表示训练数据中样本 $(x, y)$ 出现的频数， $V(X=x)$ 表示训练数据集中 $x$ 出现的频数。 $N$ 表示训练样本的总容量。

特征函数 $f(x, y)$ 表示输入 $x$ 和输出 $y$ 之间的某个约束。其定义为:

$f(x,y)=\begin{cases} 1,\quad x和y满足约束\\ 0, \quad x和y不满足约束 \end{cases} \tag{3}$

特征函数 $f(x,y)$ 关于经验分布 $\tilde P(X, Y)$ 的期望值为:

$E_{\tilde p}(f) = \sum_{x, y} \tilde P(x,y)f(x, y) \tag{4}$

特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 和经验分布 $\tilde P(X)$ 的期望值为:

$E_{p}(f) = \sum_{x, y} \tilde P(x)P(y|x)f(x, y) \tag{5}$

因为机器学习的目的就是从数据集中学得数据中包含的某种内在信息，因此我们可以假设公式4和公式5相等，即

$E_{\tilde p}(f) = E_{p}(f) \\ \sum_{x, y} \tilde P(x,y)f(x, y) = \sum_{x, y} \tilde P(x)P(y|x)f(x, y) \tag{6}$

公式6就作为模型的约束条件，如果有 n 个特征函数，则就有 n 个约束条件。

最大熵模型 假设满足所有约束条件的模型集合为

$C=\{P|E_{\tilde p}(f_i) = E_{p}(f_i), i=1,2...n\}$

定义在条件概率分布 $P(Y|X)$ 上的条件熵为:

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

则模型集合 $C$ 条件熵最大的模型成为最大熵模型

补充

条件概率的熵的公式为
$H(y|x)=-\sum_{x,y}p(x,y)logp(y|x) \tag{8}$

因此最大熵模型如公式7所示。

总之，最大熵模型就是在满足约束的模型集合中选择条件概率分布 $P(Y|X)$ 最大的模型。

3. 最大熵模型的学习

通过上述上述的描述，最大熵模型可以形式化为约束最优化问题，即

$\max_{P \in C} H(P) = -\sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) \\ s.t. \quad E_{\tilde p}(f_i) = E_{p}(f_i), \quad i=1, 2...,n \\ \quad \sum_yP(y|x) = 1 \tag{9}$

按照优化习惯，通常将最大值优化转换为最小值优化。即
$\max_{P \in C} -H(P) = \sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) \\ s.t. \quad E_{\tilde p}(f_i) = E_{p}(f_i), \quad i=1, 2...,n \\ \quad \sum_yP(y|x) = 1 \tag{10}$

公式10所得出的解就是最大熵模型学习的模型。

解决上述约束最优化问题，我们通过拉格朗日对偶性来进行解决。

首先我们引入拉格朗日乘子 $w_0, w_1,w_2...w_n$ ,定义拉格朗日函数 $L(p, w)$ 为
$\begin{aligned} L(P, w) &=-H(P) + w_0(1-\sum_yP(y|x))+\sum_{i=1}^{n}w_i(E_{\tilde p}(f_i) - E_{p}(f_i)) \\ &=\sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) + w_0(1-\sum_yP(y|x)) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P(y|x)f(x, y)) \end{aligned} \tag{11}$

因此，最优化问题的原始问题为
$\min_{P\in C} \max_{w} L(P,w) \tag{12}$
对偶问题

$\max_{w} \min_{P\in C} L(P,w) \tag{13}$

我们称公式10、11和12为原始问题，公式13为原始问题的对偶问题，且原始问题的解与对偶问题的解是等价的，因此，公式11的解就是我们求解的模型。

我们首先求解对偶问题公式13内部的极小化问题 $\min_{P\in C} L(P,w)$ ,该函数是关于 $w$ 的函数，我们将其记作:

$\psi (w) = \min_{P\in C} L(P,w) = L(P_w, w) \tag{14}$

$\psi (w)$ 称为对偶函数，同时其解记为:

$P_w = \arg \min_{p}L(P,w) = P_w(y|x) \tag{15}$

我们可以利用偏导数来求解公式15，即

$\begin{aligned} \frac{\partial L(P,w)}{\partial P(y|x)} &= \sum_{x,y}(\tilde P(x) \log P(y|x) + \tilde{P}(x)) -\sum_{y}w_o+\sum_{i=1}^{n}w_i(-\sum_{x,y}\tilde{P}(x)f_{i}(x,y)) \\ &= \sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1) - \sum_{y}w_0-\sum_{x,y}{\tilde{P}(x)\sum_{i=1}^nw_if_i(x,y)} \\ &=\sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1) - \sum_x \tilde{P}(x)\sum_{y}w_0-\sum_{x,y}{\tilde{P}(x)\sum_{i=1}^nw_if_i(x,y)} \\ &= \sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1-w_0-\sum_{i=1}^nw_if_i(x,y)) \end{aligned} \tag{16}$

由于 $L(P,w)$ 是凸函数，我们我可令上式偏导数为0，在 $\tilde P(x)>0$ 的情况下，即可求出 $P(y|x)$ , 即：
$\begin{aligned} P(y|x) &=\exp(\sum_{i=1}^{n}w_if_i(x,y)+w_0-1)\\ &=\frac{\exp{\sum_{i=1}^{n}w_if_i(x,y)}}{\exp(1-w_0)} \end{aligned} \tag{17}$

由于在概率论中， $\sum_{y}P(y|x)=1$ ,因此需对公式17进行归一化，又 $\exp(1-w_0)$ 为常数,因此：

$P_w(y|x)=\frac{1}{Z_w(x)}\exp(\sum_{i=1}^{n}w_if_i(x,y)) \tag{18}$

其中

$Z_w(x)=\sum_{y}\exp(\sum_{i=1}^nw_if_i(x,y)) \tag{19}$

公式18、19表示的模型就是最大熵模型 $P_w=p_w(y|x)$ .然后求解对偶函数的极大化问题
$\max_{w} \psi (w) \tag{20}$

求得 $w^*$ ,得到最终模型。

4 极大似然估计

通过上面一小节的计算，我们已经求出最大熵模型，但是此时该模型还是一个关于 $w$ 的函数，我们如何求出 $w$ 来求得最终的模型呢。

我们先来描述对数似然函数，通过前面一章的逻辑回归模型中的最大似然估计，我们可知对数似然函数和熵在值上互为相反数，又通过公式8得知条件概率的熵形式，因此我们可以得知，条件概率分布 $P(Y|X)$ 的对数似然函数

$L_{\tilde P}(P_w) = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \tag{21}$

我们再冲似然函数的定义方面证明上述公司的正确性。

在给定数据集 $\{(x_1,y_1),(x_2,y_2)...(x_n,y_n)\}$ ,我们可求得当前模型的似然函数为:

$L(\theta)=\prod_{i=1}^n P(x_i, \theta) \tag{22}$

我们假设 $X_i$ 在训练集中出现了 $C(x_i)$ ,因此公式22可以转化为:

$L(\theta)=\prod_{i=1}^k P(x_i, \theta)^{C(x_i)} \tag{23}$

$k$ 表示训练数据集中总共有 k 种不同的输入特征，我们对上市求其 $\frac{1}{n}$ 次方，得：

$L(\theta)^{\frac{1}{n}}=\prod_{i=1}^k P(x_i, \theta)^{\frac{C(x_i)}{n}} \tag{24}$

对公式24求对数的:

$\begin{aligned} \log L(\theta)^{\frac{1}{n}} &=\log \prod_{i=1}^k P(x_i, \theta)^{\frac{C(x_i)}{n}} \\ &= \sum_{i=1}^k \frac{C(x_i)}{n} \log P(x_i, \theta)\\ \end{aligned} \tag{25}$

因此对于 $\log L(\theta)^{\frac{1}{n}}$ 和 $\log L(\theta)$ 是等价的，

因此对于条件概率分布 $P(Y|X)$ 的对数似然函数

$L_{\tilde P}(P_w) = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \tag{26}$

对于公式21-26的推导，不具有严格的树学理论，只是为了理解下面公式27做铺垫。

一直训练数据的经验概率分布 $\tilde P(X,Y),$ 条件概率分布 $P(Y|X)$ 的对数似然函数表示为

$\begin{aligned} L_{\tilde P}(P_w) &=\log \prod_{xy}P(y|x)^{\tilde P(x,y)} = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \end{aligned} \tag{27}$

将公式18和19带入公式27可得:
$\begin{aligned} L_{\tilde P}(P_w) &=\sum_{x,y}\tilde{P}(x,y)(\sum_{i=1}^{n}w_if_i(x,y)-\log Z_w(x) \\ &=\sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^{n}w_if_i(x,y)-\sum_{x,y}\tilde{P}(x,y)\log Z_w(x) \\ &=\sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^{n}w_if_i(x,y)-\sum_{x}\tilde {P}(x)\log Z_w(x) \end{aligned} \tag{28}$

公式28就是极大似然函数。上式最后两步最后一项的转化是因为 $Z_w(x)$ 是关于 x 的函数，所以可以对 $\tilde{P}(x,y)$ 对 $x$ 进行累加得到 $\tilde {P}(x)$ .

我们再看看对偶函数 $\psi (w)$ ,我们将 $P_w(y|x)$ 带入公式11得:

$\begin{aligned} \psi (w) =& \sum_{x,y}\tilde P(x)P_w(y|x)\log P_w(y|x) + w_0(1-\sum_yP(y|x)) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P_w(y|x)f(x, y)) \\ =&\sum_{x,y}\tilde P(x)P_w(y|x)\log P_w(y|x) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P_w(y|x)f(x, y)) \\ =& \sum_{x,y}\tilde P(x,y)\sum_{i=1}^{n}w_if(x, y)+\sum_{x,y}\tilde{P}(x)P_w(y|x)(\log P_w(y|x)-\sum_{i=1}^{n}w_if_i{(x,y)}) \\ =& \sum_{x,y}\tilde P(x,y)\sum_{i=1}^{n}w_if(x, y)-\sum_{x,y}\tilde{P}(x)P_w(y|x)\log Z_w(x) \\ =& \sum_{x,y}\tilde P(x,y)\sum_{i=1}^{n}w_if(x, y)-\sum_{x,y}\tilde{P}(x)\log Z_w(x) \end{aligned} \tag{29}$

公式29第三步到第四步用到下面公式进行推导:

$P_w(y|x)=\frac{1}{Z_w(x)}\exp(\sum_{i=1}^{n}w_if_i(x,y)) \Rightarrow \log P_w(y|x)=\sum_{i=1}^{n}w_if_i(x,y)-\log Z_w(x)$

倒数第二步到最后一步的推导用到了 $\sum_{y}P(y|x)=1$ .

比较公式公式28和公式29，可得:

$\psi (w) = L_{\tilde P}(P_w)$

因此，可以证明，最大熵模型学习中的对偶函数极大化等价于最大熵模型的极大似然估计。

最大熵模型详细解析 | 统计学习方法学习笔记 | 数据分析 |
本文包括： 1.最大熵模型简介2.最大熵的原理3.最大熵模型的定义4.最大熵模型的学习 1.最大熵模型简介：最大...
熵
一、看文章 “熵”不起：从熵、最大熵原理到最大熵模型（一）“熵”不起：从熵、最大熵原理到最大熵模型（二）“熵”不起...
逻辑斯谛回归与最大熵模型
逻辑斯谛回归与最大熵模型逻辑斯谛回归模型最大熵模型最大熵模型的学习逻辑斯谛回归（logistic regr...
逻辑斯谛回归与最大熵模型
逻辑斯谛回归与最大熵模型首先介绍逻辑斯谛分布：二项逻辑斯谛回归模型：最大熵模型：最大熵原理是概率模型...
最大熵模型
在满足约束条件的模型集合中选取熵最大的模型，即不确定最大熵模型。最大熵模型就是要学习到合适的分布 P(y|x) ,...
Day 2080：学习
#统计学习最大熵模型：由最大熵原理推导而得最大熵原理是概率模型学习的一个准则，它认为所有可能的概率模型中，熵最...
改进的迭代尺度法(IIS)详细解析 | 统计学习方法学习笔记 |
IIS是一种最大熵模型学习的最优化算法。最大熵模型：舟晓南：统计学习方法 - 最大熵模型解析 | 数据分析，机器学...
最大熵模型
序本次记录的主要内容有：1、熵的概念2、最大熵模型推导模型属性 ME是经典的分类模型ME是对数线性模型最大熵...
最大熵模型
GitHub简书CSDN 1. 最大熵原理最大熵模型（Maximum Entropy Model)是通过最大熵原...
统计学习方法7.3 - 7.4笔记
7.3 最大熵模型：拉格朗日乘子法最大熵模型：在待选集合C中挑选条件熵最大的条件概率分布（P），并且符合约束条件...