机器学习中最大熵模型的介绍，包括模型思想、学习问题、学习算法等
最大熵原理
预备知识
离散型变量\(X\)的概率分布是\(\color{blue}{P(X)}\)。它的熵\(\color{blue}{H(X) \; or \; H(P)}\)越大，代表越均匀、越混乱、越不确定。各种熵点这里 \[ \color{blue}{H(P)} = \color{red} {- \sum_{x \in X}P(x) \log P(x)} \] 熵满足下面不等式 \[ 0 \le H(P) \le \log |X|, \quad 其中|X|是X的取值个数 \] 当前仅当\(X\)的分布是均匀分布的时候等号成立。当\(X\)服从均匀分布时，熵最大。
最大熵的思想
最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。
事情分为两个部分：确定的部分（约束条件）和不确定的部分。选择模型时要
- 要满足所有的约束条件，即满足已有的确定的事实
- 要均分不确定的部分
\(X\)有5个取值\(\{A, B,C,D,E\}\)，取值概率分别为\(P(A), P(B), P(C), P(D), P(E)\)。满足以下约束条件 \[ P(A)+ P(B)+ P(C)+ P(D)+ P(E) = 1 \] 满足这个条件的模型有很多。再加一个约束条件 \[ P(A) + P(B) = \frac{3}{10} \] 则，满足约束条件，不确定的平分（熵最大）：这样的模型是最好的模型 \[ P(A) = P(B) = \frac{3}{20}, \quad P(C)=P(D)=P(E) = \frac{7}{30} \] 即：约束条件，熵最大
最大熵模型
假设分类模型是一个条件概率分布\(\color{blue}{P(Y \mid X)}\)。(有的不是选择条件模型，如论文里面)。训练数据集\(N\)个样本 \(T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}\)
基本概念
- 联合分布：\(\color{blue}{P(X, Y)}\)
- 边缘分布：\(\color{blue}{P(X)}\)
- 联合经验分布：\(\color{blue}{\widetilde{P}(X, Y)} = \color{red}{\frac {v(X=x, Y=y)}{N}}\)，其中\(v(x, y)\)为频数
- 联合边缘分布：\(\color{blue}{\widetilde P(X) = \color{red} {\frac{v(X=x)}{N}}}\)
特征函数\(\color{blue}{f(x, y)}\)用来描述\(x\)和\(y\)满足的一个事实约束条件： \[ f(x, y) = \begin{cases} 1, \quad & x与y满足一个事实，即约束条件 \\ 0, \quad & 否则 \end{cases} \] 如果有\(n\)个特征函数\(\color{blue}{f_i(x, y), i = 1, 2, \cdots, n}\), 就有\(n\)个约束条件。
概率期望的计算
\(X\)的期望
\(X\) 是随机变量，概率分布是\(P(X)\) ，或概率密度函数是\(f(x)\) \[ E(X) = \begin{cases} &\sum_{i} x_i P(x_i), \quad & \text{离散} \\ & \int_{-\infty}^{+\infty} {x \cdot f(x)} \, {\rm d}x , \quad & \text{连续} \\ \end{cases} \] 下面只考虑离散型的期望，连续型同理，求积分即可。
一元函数的期望
\(Y = g(X)\)，期望是 \[ E[Y] = E[g(X)] = \sum_{i}^{\infty} g(x_i) \cdot P(x_i) \] 二元函数的期望
\(Z = g(X, Y)\) ，期望是 \[ E(Z) = \sum_{x, y} g(x, y) \cdot p(x, y) = \sum_{i=1} \sum_{j=1} g(x_i, y_j) p(x_i, y_j) \] 期望其实就是\(E 狗 = \sum 狗 \cdot 老概率\) 。可离散，可连续。
约束条件等式
实际分布期望
特征函数\(f(x, y)\)关于经验分布\(\color{blue}{\widetilde P(x, y)}\)的期望\(\color{blue}{E_{\widetilde P}(f)}\)，即实际应该有的特征 ，也就是一个给模型加的约束条件 ： \[ \color{blue}{E_{\widetilde P}(f)} = \sum_{x, y} \color{red} {\widetilde P(x,y)} f(x, y) \] 理论模型期望
特征函数\(f(x, y)\) 关于模型\(\color{blue}{P(Y\mid X)}\)和经验分布\(\color{blue}{\widetilde P(X)}\)的期望\(\color{blue}{E_{P}(f)}\) ，即理论上模型学得后的期望： \[ \color{blue}{E_{ P}(f)} =\sum_{x, y} \color{red} { \widetilde{P}(x) P(y \mid x)} f(x, y) \] 要从训练数据中获取信息，特征函数关于实际经验分布和理论模型的两个期望就得相等，即理论模型要满足实际约束条件 \[ E_{\widetilde P}(f) = E_{ P}(f) \]
最大熵模型思想
条件概率分布\(P(Y \mid X)\)的条件熵为\(\color{blue}{H(P)}\)如下，条件熵： \[
\color{blue}{H(P)} =
\color{red} {- \sum_{x, y} \widetilde P(x) P(y \mid x) \log P(y \mid x)}
\] 则满足约束条件\(\color{blue}{E_{\widetilde P}(f) = E_{ P}(f)}\)的模型中，条件熵\(\color{blue}{H(P)}\)最大的模型就是最大熵模型。
最大熵模型的学习
学习问题
最大熵模型的学习等价于约束最优化问题，这类问题可以用拉格朗日对偶性去求解。
给定数据集\(T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}\)和特征函数\(\color{blue}{f_i(x, y), i = 1, 2, \cdots, n}\)。
要满足2个约束条件 \[ \color{red} {E_{\widetilde P}(f) = E_{ P}(f), \quad \sum_{x, y}P(y \mid x) = 1 } \] 要得到最大化熵 \[ \max \limits_{P \in C} \; \color{blue}{H(P)} = \color{red} {- \sum_{x, y} \widetilde P(x) P(y \mid x) \log P(y \mid x)} \] 按照最优化问题的习惯，将求最大值问题改写为等价的求最小值问题 ，如下 \[ \min \limits_{P \in C} \; \color{blue}{ - H(P)} = \color{red} { \sum_{x, y} \widetilde P(x) P(y \mid x) \log P(y \mid x)} \]
推导最大熵模型
一般使用拉格朗日对偶性去求解，可以见李航书附录。 引入拉格朗日乘子\(\color{blue}{w = (w_0, w_1, \cdots, w_n)}\)，即参数向量，构造拉格朗日函数\(\color{blue}{L(P, w)}\) ： \[
\color{blue}{L(P, w)} = \color{red}{
-H(P) +
w_0 \cdot \left( 1 - \sum_{x, y} P(y \mid x)\right)
+ \sum_{i=1}^n w_i \cdot \left(E_{\widetilde P}(f) - E_{ P}(f) \right)
}
\] 由于是凸函数，根据相关性质，所以原始问题和对偶问题同解，原始问题如下： \[
\min \limits_{P \in C} \max \limits_{w} L(P, w)
\] 对应的对偶问题如下： \[
\max \limits_{w} \min \limits_{P \in C} L(P, w)
\] 主要思路是：先固定\(\color{blue}{w}\)，去计算\(\color{blue} {\min \limits_{P \in C} L(P, w)}\)，即去找到一个合适的\(\color{blue}{P(Y \mid X)}\)。再去找到一个合适的\(\color{blue}{w}\)。
第一步：求解\(\color{blue}{P}\) 。设对偶函数\(\color{blue} { \Psi (w)}\)如下： \[
\color{blue} { \Psi (w)} = \color{red} {\min \limits_{P \in C} L(P, w) = L(P_w, w)}
\] 对偶函数的解，即我们找到的\(P(Y \mid X)\)，记作\(\color{blue}{P_w}\)，如下： \[
\color{blue}{P_w} = \arg \min \limits_{P \in C} L(P, w) =\color{red} {P_w(y \mid x)}
\] 用\({L(P, w)}\)对\(P\)进行求偏导，令偏导为0，可以解得\({P_w}\)，即最大熵模型 如下： \[
\color{blue}{P_w(y \mid x)} = \color{red} {\frac{1}{Z_w(x)} \cdot \exp \left({\sum_{i=1}^nw_if_i(x, y)}\right) },
\;
\color{blue}{Z_w(x)} = \color{red} {\sum_{y} \exp \left( \sum_{i=1}^{n} w_i f_i(x, y)\right) }
\] 其中\(\color{blue}{Z_w(x)}\)是归一化因子，\(\color{blue} {f_i(x, y)}\)是特征函数，\(\color{blue}{w_i}\)是特征的权值，\(\color{blue}{P_w(y \mid x)}\) 就是最大熵模型， \(\color{blue}{w}\)是最大熵模型中的参数向量。
第二步：求解\(\color{blue}{w}\)。即求\(w\)去最大化对偶函数，设解为\(\color{blue} {w^*}\) 。可以使用最优化算法去求极大化。 \[ \color{blue}{w^*} = \color{red} {\arg \max \limits_{w} \Psi(w)} \] 最终，求到的\(\color{blue} {P^* = P_{w^*} = P_{w^*}(y \mid x)}\)就是学习得到的最大熵模型。
最大熵模型
最大熵模型如下，其中\(\color{blue}{Z_w(x)}\)是归一化因子，\(\color{blue} {f_i(x, y)}\)是特征函数，\(\color{blue}{w_i}\)是特征的权值 。 \[
\color{blue}{P_w(y \mid x)} = \color{red} {\frac{1}{Z_w(x)} \cdot \exp \left({\sum_{i=1}^nw_if_i(x, y)}\right) },
\;
\color{blue}{Z_w(x)} = \color{red} {\sum_{y} \exp \left( \sum_{i=1}^{n} w_i f_i(x, y)\right) }
\]
极大似然估计
其实对偶函数\(\color{blue}{\Psi(w)}\)的极大化等价于最大熵模型的极大似然估计。
已知训练数据的经验分布\(\widetilde{P}(X, Y)\)，条件概率分布的\(P(Y \mid X)\)的对数似然函数是： \[
\begin{align*}
\color{blue} {L_{\widetilde P}(P_w)}
& = \log \prod_{x, y} P(y \mid x) ^ {\widetilde{P}(X, Y)} = \sum_{x, y} \widetilde P(x, y) \log P(y \mid x) \\
& = \color{red}{\sum_{x, y}\widetilde{P}(X, Y) \sum_{i=1}^{n} w_i f_i(x, y) - \sum_{x} \widetilde{P}(X)\log Z_w(x) }
\end{align*}
\] 可以证明得到，$L_{P}(P_w) = (w) $，极大似然函数等于对偶函数。
模型学习的最优化算法
逻辑回归、最大熵模型的学习都是以似然函数为目标函数的最优化问题，可以通过迭代算法求解。这个目标函数是个光滑的凸函数。通过很多方法都可以保证找到全局最优解，常用的有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法，其中牛顿法和拟牛顿法一般收敛速度更快。
改进的迭代尺度法
改进的迭代尺度法(improved iterative scaling, IIS)是一种最大熵模型学习的最优化算法。
已知最大熵模型如下： \[ \color{blue}{P_w(y \mid x)} = \color{red} {\frac{1}{Z_w(x)} \cdot \exp \left({\sum_{i=1}^nw_if_i(x, y)}\right) }, \; \color{blue}{Z_w(x)} = \color{red} {\sum_{y} \exp \left( \sum_{i=1}^{n} w_i f_i(x, y)\right) } \] 对数似然函数如下： \[ \color{blue} {L_{\widetilde P}(P_w)} = \color{red}{\sum_{x, y}\widetilde{P}(X, Y) \sum_{i=1}^{n} w_i f_i(x, y) - \sum_{x} \widetilde{P}(X)\log Z_w(x) } \] 目标是：通过极大似然估计学习模型参数，即求对数似然函数的极大值\(\color{blue} {\hat w}\)。
基本思想
当前参数向量\(w = (w_1, w_2, \cdots, w_n)^T\)，找到一个新的参数向量\(w+\delta = (w_1 + \delta_1, w_2 + \delta_2, \cdots, w_n + \delta_n)\)，使得每次更新都使似然函数值增大。
由于\(\delta\)是一个向量，含有多个变量，不易同时优化。所以IIS 每次只优化其中一个变量\(\delta_i\)，而固定其他变量\(\delta_j\)。
设所有特征在\((x, y)\)中的出现次数\(f^\#(x, y) = M\) ： \[ \color{blue}{f^\# (x, y)} = \sum_i f_i(x, y) \] 计算每次的改变量： \[ L(w+\delta) - L(w) \ge \color{blue}{B(\delta \mid w)}, \; 改变量的下界限 \] 如果找到适当的\(\delta\)使得改变量的下界\(B(\delta \mid w)\)提高，则对数似然函数也能提高。
计算\(B(\delta \mid w)\)对\(\delta_i\)求偏导，令偏导等于0，得如下方程： \[ \color{red} { \sum_{x, y} \widetilde P(x) P_w(y \mid x) f_i(x, y) \exp \left(\delta_i f^\#(x, y)\right) = E_{\widetilde p}(f_i) }, \quad 其中\, E_{\widetilde p}(f_i) = \sum_{x, y} \widetilde P(x, y)f_i(x, y) \] 然后，依次对\(\delta_i\)求解该方程，就可以求得\(\delta\)，也就能够更新\(w\)，即\(w \to w+\delta\)
算法步骤
输入：特征函数\(f_1, \cdots, f_n\)；经验分布\(\widetilde P(x, y)\)，模型\(P_w(y \mid x)\)
输出：最优参数值\(w_i^*\)；最优模型\(P_{w^*}\)
初始化参数，取初值 \(w_i = 0\)
- 求解方程 \(\delta_i\) \[ \sum_{x, y} \widetilde P(x) P_w(y \mid x) f_i(x, y) \exp \left(\delta_i f^\#(x, y)\right) = E_{\widetilde p}(f_i), \]
更新参数 \(w_i + \delta_i \to w_i\)
其中解方程的时候，如果特征出现次数\(f^\#(x, y)\) 是常数\(M\)，则可以直接计算\(\delta_i\) ： \[
\color{blue}{\delta_i } = \color{red} {\frac{1}{M} \log \frac{E_{\widetilde p}(f_i)}{E_{p}(f_i)} }
\] 如果\(f^\#(x, y)\)不是常数，则必须通过数值计算\(\delta_i\)。最简单就是通过牛顿迭代法去迭代求解\(\delta_i^*\)。以\(g(\delta_i) = 0\) 表示该方程，进行如下迭代： \[
\color{blue} {\delta_i^{(k+1)}} = \color{red} {\delta_i^{(k)} - \frac{g(\delta_i^{(k)})}{g^\prime (\delta_i^{(k)})} }
\]
