Logistic 回归和最大熵模型都被称为对数线性模型.

1 Logistic 回归模型

1.1 Logistic 分布

1.2 二项 Logistic 回归模型

用几率定义一个事件发生与不发生的比率. 对 Logistic 回归模型, 发生 (${\displaystyle Y=1}$) 的对数几率为$$\log \frac{p}{1-p}=\omega \cdot x$$是关于${\displaystyle x}$的线性函数; 换言之, Logistic 回归模型的作用是将实数域上的线性函数转换为概率值.

1.3 模型参数估计

对给定的训练数据集${\displaystyle T=\{(x_1,y_1),\cdots ,(x_N,y_N)\}}$, 其中${\displaystyle x_i\in {\mathbb{R}}^n,y_i\in \{0,1\}}$, 采用极大似然估计来确定参数. 记${\displaystyle \pi (x)=P(Y=1|x),1-\pi (x)=P(Y=0|x)}$. 则似然函数为

对数似然函数为$$\begin{array}{rl}L(\omega )=& \sum _{i=1}^N[y_i\log \frac{\pi (x_i)}{1-\pi (x_i)}+\log (1-\pi (x_i))]\\ =& \sum _{i=1}^N[y_i(\omega \cdot x_i)-\log (1+\exp (\omega \cdot x_i))].\end{array}$$
求极大值: $$\frac{\partial L}{\partial \omega }=\sum _{i=1}^N[y_i{x}_i-\frac{x_i\exp (\omega \cdot x_i)}{1+\exp (\omega \cdot x_i)}]=0,$$ 发现 ${\displaystyle \omega }$ 没有解析解, 可以用数值方法得到 ${\displaystyle \hat{\omega }}$, 因此最终的 Logistic 模型为

(注意这里的 ${\displaystyle \hat{\omega }}$ 已经被增广了)

1.4 多项 Logistic 回归

改设${\displaystyle Y=\{1,\cdots ,K\}}$, 其他设置与这里相同. 则 Logistic 回归模型为

2 最大熵模型

2.1 最大熵原理

最大熵原理认为, 在满足某些约束条件下, 要找尽可能熵最大的模型. 假设离散随机变量${\displaystyle X}$有概率分布${\displaystyle P(X)}$, 其熵为

自然, 熵满足不等式$$0\le H(P)\le \log |X|.$$这里${\displaystyle |X|}$是${\displaystyle X}$取值的个数. 上述不等式可由对数和不等式推导, 取等条件为${\displaystyle X}$是均匀分布.

最大熵模型 认为 , 在满足了约束条件后, 所有不确定部分都是“等可能的”, 用熵的最大化来表示等可能性. 从 (2.1) 看出, 分布越接近均匀分布, 熵越大; 反之则表现出某种集中性, 熵越小.

2.2 最大熵模型的定义

设分类模型是${\displaystyle P(Y|X)}$, 输入为${\displaystyle X\in \mathcal{X}\subset {\mathbb{R}}^n}$, 输出为${\displaystyle Y\in \mathcal{Y}}$. 训练集${\displaystyle T=\{(x_1,y_1),\cdots ,(x_N,y_N)\}}$.
为了应用最大熵模型, 首先要考虑约束条件. 首先从给定数据集确定${\displaystyle P(X,Y)}$和边缘分布${\displaystyle P(X)}$的经验分布, 记为${\displaystyle \tilde{P}(X,Y),\tilde{P}(X)}$; 再记${\displaystyle \nu (X=x,Y=y),\nu (X=x)}$表示对应的频数. 则$$\tilde{P}(X=x,Y=y)=\frac{\nu (X=x,Y=y)}{N},\tilde{P}(X=x)=\frac{\nu (X=x)}{N}.$$

上面的式 (2.2) 可以看作模型学习的约束条件; ${\displaystyle n}$个特征函数对应${\displaystyle n}$个约束条件.

2.3 最大熵模型的学习

最大熵模型的求解等价于最优化问题$$\begin{array}{rl}\underset{P\in \mathcal{C}}{min}& -H(P)=\sum _{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\\ \mathrm{s}.\mathrm{t}.& E_P(f_i)-E_{\tilde{P}}(f_i)=0,i=1,\cdots ,n,\\ & \sum _{y}P(y|x)=1.\end{array}$$
转换为对偶( #Dual )问题 . 定义 Lagrange 函数 $$\begin{array}{rl}L(P,\omega )=& -H(P)+{\omega }_0(1-\sum _{y}P(y|x))+\sum _{i=1}^n{\omega }_i[E_{\tilde{P}}(f_i)-E_P(f_i)]\\ =& \sum _{x,y}\tilde{P}(x)P(y|x)\log P(y|x)+{\omega }_0(1-\sum _{y}P(y|x))\\ \text{(2.3)}& & +\sum _{i=1}^n{\omega }_i(\sum _{x,y}\tilde{P}(x,y)f_i(x,y)-\sum _{x,y}\tilde{P}(x)P(y|x)f_i(x,y)).\end{array}$$
最优化问题的对偶问题 (因为 ${\displaystyle L}$ 是关于 ${\displaystyle P}$ 的凸函数): $$\underset{P\in \mathcal{C}}{min}\underset{\omega }{max}L(P,\omega )\to \underset{\omega }{max}\underset{P\in \mathcal{C}}{min}L(P,\omega )$$

• 首先, 求解内部的${\displaystyle \underset{P\in \mathcal{C}}{min}L(P,\omega )}$. 记${\displaystyle \psi (\omega )=\underset{P\in \mathcal{C}}{min}L(P,\omega )=L(P_{\omega },\omega )}$, (${\displaystyle \psi (\omega )}$称为对偶函数.) 并将解${\displaystyle P_{\omega }}$记为${\displaystyle P_{\omega }=\arg \underset{P\in \mathcal{C}}{min}L(P,\omega )=P_{\omega }(y|x)}$. 为了具体求解, 计算$$\begin{array}{rl}\frac{\partial L(P,\omega )}{\partial P(y|x)}=& \sum _{x,y}\tilde{P}(x)[\log P(y|x)+1]-\sum _y{\omega }_o-\sum _{x,y}(\tilde{P}(x)\sum _{i=1}^n{\omega }_i{f}_i(x,y))\\ =& \sum _{x,y}\tilde{P}(x)(\log P(y|x)+1-{\omega }_0-\sum _{i=1}^n{\omega }_i{f}_i(x,y)),\end{array}$$
  (用了${\displaystyle \sum _x\tilde{P}(x)=1}$.) 进而令偏导为${\displaystyle 0}$, 得到$$P(y|x)=\frac{\exp (\sum _{i=1}^n{\omega }_i{f}_i(x,y))}{\exp (1-{\omega }_0)},$$
  这确定了${\displaystyle P_{\omega }(y|x)}$的比例关系; 再结合${\displaystyle \sum _{y}P(y|x)=1}$得到

这就是最大熵模型的决策依据. 在这里我们记分母为${\displaystyle Z_{\omega }(x)}$.

• 其次, 求解外部的${\displaystyle \underset{\omega }{max}\psi (\omega )}$. 记解为${\displaystyle {\omega }^{\ast }}$, 则${\displaystyle {\omega }^{\ast }=\arg \underset{\omega }{max}\psi (\omega )}$, 则${\displaystyle P^{\ast }=P_{{\omega }^{\ast }}}$就是要学习的最优模型. 也即, 最大熵模型的学习归结为对偶函数${\displaystyle \psi (\omega )}$的最大化.

2.4 极大似然估计的等价性证明

下面证明: 对偶函数的极大化等价于最大熵模型的极大似然估计. 为此, 考察${\displaystyle P(Y|X)}$的对数似然函数$$L_{\tilde{P}}(P_{\omega })=\log \prod _{x,y}P(y|x{)}^{\tilde{P}(x,y)}=\sum _{x,y}\tilde{P}(x,y)\log P(y|x).$$

• 一方面, 如果${\displaystyle P(y|x)}$由 (2.4) 给出, 则$$L_{\tilde{P}}(P_{\omega })=\sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{\omega }_i{f}_i(x,y)-\sum _x\tilde{P}(x)\log Z_{\omega }(x).$$
• 另一方面, 考察对偶函数, 带入 (2.3) 得$$\begin{array}{rl}\psi (\omega )=& \sum _{x,y}\tilde{P}(x)P_{\omega }(y|x)\log P_{\omega }(y|x)\\ & +\sum _{i=1}^n{\omega }_i(\sum _{x,y}\tilde{P}(x,y)f_i(x,y)-\sum _{x,y}\tilde{P}(x)P_{\omega }(y|x)f_i(x,y))\\ =& \sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{\omega }_i{f}_i(x,y)+\sum _{x,y}\tilde{P}(x)P_{\omega }(y|x)(\log P_{\omega }(y|x)-\sum _{i=1}^n{\omega }_i{f}_i(x,y))\\ =& \sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{\omega }_i{f}_i(x,y)-\sum _{x,y}\tilde{P}(x)P_{\omega }(y|x)\log Z_{\omega }(x)\\ =& \sum _{x,y}\tilde{P}(x,y)\sum _{i=1}^n{\omega }_i{f}_i(x,y)-\sum _x\tilde{P}(x)\log Z_{\omega }(x),\end{array}$$

从而得到了${\displaystyle L_{\tilde{P}}(P_{\omega })=\psi (\omega )}$.
由此, 最大熵模型的学习转化为对偶函数极大化或对数似然函数极大化问题.