C06. Logistic 回归与最大熵模型

Logistic 回归是分类模型，最大熵是其学习准则。(强烈建议先看 [^Bishop,2006]Ch 04了解原理，再通过此书看推导)

6.1 Logistic 模型

6.1.1 Logistic 分布

Logistic 概率分布函数是 Sigmoid 函数

• $F ( x ) =P ( X\leq x ) =\frac1{1+\exp{- ( x-\mu ) /\gamma}}$
  • $\mu$ 为位置参数
  • $\gamma>0$ 为形状参数

Logistic 概率密度函数

• $f ( x ) =F’ ( x ) =\frac{\exp{- ( x-\mu ) /\gamma}}{\gamma [1+\exp{- ( x-\mu ) /\gamma}^2]}$

6.1.2 二项 Logistic 回归模型

二项 Logistic 回归模型是二分类模型，由条件概率分布 $p ( X|Y )$ 表示，形式为参数化的 Logistic 分布，使用监督学习方法来估计模型参数。

模型的条件概率分布

• $\text{x}\in\mathbb{R}^n$ 表示输入
• $Y\in{0,1}$ 表示输出
• $\text{w}\in\mathbb{R}^n$ 和 $b\in\mathbb{R}$ 表示参数
  • $\text{w}$ 表示可能会向量
  • $b$ 表示偏置

$$
\begin{aligned}
P ( Y=1|\text{x} ) &=\frac{\exp{\text{w}^T \text{x} +b}}{1+\exp{\text{w}^T \text{x} +b}}\
P ( Y=0|\text{x} ) &=\frac1{1+\exp{\text{w}^T \text{x} +b}}
\end{aligned}
$$

概率分布的简化

• 向量扩充
  • $\dot{\text{w}}= ( \text{w}^T,b )^T$
  • $\dot{\text{x}}= ( \text{x}^T,1 )^T$

$$
\begin{aligned}
P ( Y=1|\text{x} ) &=\frac{\exp{\dot{\text{w}}^T \dot{\text{x}}}}{1+\exp{\dot{\text{w}}^T \dot{\text{x}}}}\
P ( Y=0|\text{x} ) &=\frac1{1+\exp{\dot{\text{w}}^T \dot{\text{x}}}}
\end{aligned}
$$

一个事件的几率 ( odds ) 是指该事件发生的概率与该事件不发生的概率的比值，例如：如果事件发生的概率是 $p$，则这个事件的几率是 $\frac{p}{1-p}$，这个事件的对数几率是$\text{logit}=\ln\frac{p}{1-p}$。

概率分布的对数几率是输入 $\text{x}$ 的线性函数，即 Logistic 回归模型。

$$
\ln\frac{P ( Y=1|\text{x} )}{1-P ( Y=1|\text{x} )}=\text{w}^T\text{x}
$$

根据模型的概率条件分布可以将线性函数转化为概率，从而作为分类判断的概率依据。

6.1.3 模型参数估计

使用 最大似然估计方法 求解模型参数

• 前提条件
  • 给定训练数据集 $T={( \text{x}_1,y_1 ) ,\cdots, ( \text{x}_N,y_n )}$
  • $P ( Y=1|\text{x} ) =\pi ( \text{x} )$
  • $P ( Y=0|\text{x} ) =1-\pi ( \text{x} )$
• 似然函数

$$
\prod_{i=1}^N [\pi ( \text{x}_i )]^{y_i}[1-\pi ( \text{x}_i )]^{1-y_i}
$$

对数似然函数
$$
\begin{aligned}
L ( \dot{\text{w}} )
&=\sum_{i=1}^N [y_i\ln\pi ( \text{x}_i ) + ( 1-y_i ) \ln ( 1-\pi ( \text{x}i )) ]\
&=\sum{i=1}^N [y_i\ln\frac{\pi ( \text{x}_i )}{1-\pi ( \text{x}_i )}+\ln ( 1-\pi ( \text{x}i )) ]\
&=\sum{i=1}^N [y_i ( \dot{\text{w}}^T\dot{\text{x}} ) -\ln ( 1+\exp{\dot{\text{w}}^T\dot{\text{x}}} )
\end{aligned}
$$

问题转化成对数似然函数的最优化问题，一般采用梯度下降法或者拟牛顿法。

6.1.4 多项 Logistic 回归模型

多项 Logistic 回归模型是多分类模型

• 前提条件：离散随机变量 $Y\in{1,\cdots,K}$
• 多项 Logistic 回归模型 ( 详情参考[^Bishop,2006] )

$$
\begin{aligned}
P ( Y=k|\text{x} )
&=\frac{\exp{\dot{\text{w}}k^T \dot{\text{x}}}}{1+\sum{k=1}^{K-1}\exp{\dot{\text{w}}k^T \dot{\text{x}}}},k=1,\cdots,K-1\
P ( Y=K|\text{x} ) &=\frac1{1+\sum{k=1}^{K-1}\exp{\dot{\text{w}}_k^T \dot{\text{x}}}}
\end{aligned}
$$

6.2 最大熵模型

6.2.1 最大熵原理

基于最大熵原理推导的，表示条件概率分布的分类模型，可以用于二类或多类分类。

• 最大熵原理的思想：在所有可能的概率模型 ( 分布 ) 的集合中，熵最大的模型是最好的模型。
• 最大熵原理的直觉：选择的概率模型必须满足已有的事实 ( 即约束条件 )，在没有更多信息时，不确定的部分都是「等可能的」，而均匀分布的熵是所有离散熵中最大的。
• 准则 : 最大熵原理是概率模型学习或估计的一个准则。

6.2.2 最大熵模型的定义

最大熵模型就是基于最大熵原理在分类问题中建立的模型。

• 例 6.1,6.2 方便理解最大熵模型的算法原理。

假设分类模型是一个条件概率分布 $P(Y|X)$

• $X\in\mathcal{X}\subseteq\mathbb{R}^n$ 表示输入，$\mathcal{X}$ 表示输入的集合
• $Y\in\mathcal{Y}$ 表示输出，$\mathcal{Y}$ 表示输出的集合
• 训练数据集 $T={(\text{x}_1,y_1) ,\cdots, ( \text{x}_N,y_N)}$
• 学习目标：基于最大熵原理选择最好的分类模型

基于训练数据集，得到联合分布 $P(X,Y)$ 和边缘分布 $P(X)$

• $v(X=\text{x},Y=y)$ 表示训练数据中样本 $(\text{x},y)$ 出现的频数
• $v(X=\text{x})$ 表示训练样本中输入 $\text{x}$ 出现的频数
• $N$ 表示训练样本的容量
• $\tilde{P}(X,Y)$ 表示 $P(X,Y)$ 的经验分布
• $\tilde{P}(X)$ 表示 $P(X)$ 的经验分布

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

使用特征函数 $f(\text{x},y)$ 描述输入 $\text{x}$ 与 输出 $y$ 之间的某一个事实，定义如下
$$
f(\text{x},y)=
\begin{cases}
1,&\text{x与}y\text{满足某一事实}\
0,& others
\end{cases}
$$
特征函数 $f(\text{x},y)$ 关于经验分布 $\tilde{P}(X,Y)$ 的期望为
$$
E_{\tilde{P}}(f)=\sum_{\text{x},y} \tilde{P}(\text{x},y)f(\text{x},y)
$$
特征函数 $f(\text{x},y)$ 关于模型 $\tilde{P}(Y|X)$ 和经验分布 $\tilde{P}(X)$ 的期望为
$$
E_{P}(f)=\sum_{\text{x},y} \tilde{P}(\text{x})P(y|\text{x})f(\text{x},y)
$$
如果模型能够获取训练数据中的信息，那么就可以假设这两个期望相等，即$E_P(f)=E_{\tilde{P}}(f)$，以此作为模型学习的约束条件，假设有 $n$ 个特征函数 $f_i(\text{x},y),i=1,\cdots,n$，那么就有 $n$ 个约束条件。

定义 6.3 ( 最大熵模型 ) ：假设满足所有约束条件的模型集合为
$$
\mathcal{C}\equiv{P\in\mathcal{P}|E_P(f_i)=E_{\tilde{P}}(f_i),i=1,\cdots,n}
$$
定义在条件概率分布 $P(Y|X)$ 上的条件熵为
$$
H(P)=-\sum_{x,y}\tilde{P}(x)P(y|x)\ln P(y|x)
$$

则模型集合 $\mathcal{C}$ 中令条件熵 $H(P)$ 最大的模型 $P$ 为最大熵模型。

6.2.3 最大熵模型的学习

最大熵模型的学习过程就是求解的过程，学习可以形式化为有约束的最优化问题 ( 对偶问题 )

• 拉格朗日乘子参考附录 C

前提条件

• 训练数据集 $T={(\text{x}_1,y_1) ,\cdots, ( \text{x}_N,y_N)}$
• 特征函数 $f_i(\text{x},y),i=1,\cdots,n$

等价模型

• 最大熵模型的学习等价于约束最优化问题

$$
\begin{aligned}
&\max_{P\in\mathcal{C}}&H(P)&=-\sum_{x,y}\tilde{P}(x)P(y|x)\ln P(y|x)\
&\text{s.t.}&E_P(f_i)&=E_{\tilde{P}}(f_i),i=1,\cdots,n\
&&\sum_y P(y|\text{x})&=1
\end{aligned}
$$

• 求解极大值问题转化为求解极小值问题

$$
\begin{aligned}
&\min_{P\in\mathcal{C}}&-H(P)&=\sum_{x,y}\tilde{P}(x)P(y|x)\ln P(y|x)\
&\text{s.t.}&E_P(f_i)-E_{\tilde{P}}(f_i)&=0,i=1,\cdots,n\
&&\sum_y P(y|\text{x})&=1
\end{aligned}
$$

• 将约束最优化的原始问题 $\min_{P\in\mathcal{C}}\max_{\text{w}} L(P,\text{w})$ 转化为无约束最优化的对偶问题 $\max_{\text{w}}\min_{P\in\mathcal{C}} L(P,\text{w})$
  • 引入Language乘子 $\text{w}=(w_0,\cdots,w_n)^T$
  • 定义Lagrange函数$L(P,\text{w})$

$$
\begin{aligned}
L(P,\text{w})
&\equiv -H(P)+w_0\biggl(1-\sum_y P(y|\text{x})\biggl)+\sum_{i=1}^n w_i\biggl(E_{\tilde{P}}(f_i)-E_P(f_i)\biggl)\
&=\sum_{\text{x},y}\tilde{P}(\text{x})P(y|\text{x} )\ln p ( y|\text{x})+w_0\biggl(1-\sum_y P(y|\text{x})\biggl)\
&+\sum_{i=1}^n\biggl(\sum_{\text{x},y}\tilde{P}(\text{x},y)f_i(\text{x},y)-\sum_{\text{x},y} \tilde{P}(\text{x})P(y|\text{x})f_i(\text{x},y)\biggl)
\end{aligned}
$$

• 由于Language函数 $L(P,\text{w})$ 是凸函数，所以原始问题的解与对偶问题的解是等价的

对偶问题的求解

• 定义对偶函数：$\Psi(\text{w})=\min_{P\in\mathcal{C}} L(P,\text{w})=L(P_{\text{w}},\text{w})$
  • 对偶函数的解记为：$P_{\text{w}}=\arg\min_{P\in\mathcal{C}} L(P,\text{w})=P_{\text{w}}(y|\text{x})$
  • 对 $L(P,\text{w})$ 关于 $P(y|\text{x})$ 求导

$$
\begin{aligned}
\frac{\partial L(P,\text{w})}{\partial P(y|\text{x})}
&=\sum_{\text{x},y} \tilde{P}(\text{x})\biggl(\ln P(y|\text{x})+1\biggl)-\sum_y w_0 -\sum_{\text{x},y} \biggl(\tilde{P}(\text{x})\sum_{i=1}^n w_i f_i(\text{x},y)\biggl)\
&=\sum_{\text{x},y} \tilde{P}(\text{x})\biggl(\ln P(y|\text{x})+1-w_0-\sum_{i=1}^n w_i f_i(\text{x},y)\biggl)
\end{aligned}
$$

• 令偏导数等于0，在 $\tilde{P}(\text{x})>0$ 下，得解

$$
\begin{aligned}
P(y|\text{x})
&=\exp{\sum_{i=1}^n w_i f_i(\text{x},y)+w_0-1}\
&=\frac{\exp{\sum_{i = 1}^n w_i f_i(\text{x},y)}}{\exp{1-w_0}}
\end{aligned}
$$

• 由于 $\sum_y P(y|\text{x})=1$ 得解 $P_{\text{w}}(y|\text{x})$ 即所求的最大熵模型
  • $Z_{\text{w}}(\text{x})$ 为规范化因子
  • $f_i(\text{x},y)$ 是特征函数
  • $w_i$ 是特征权值
  • $\text{w}$ 表示最大熵模型中的参数向量

$$
\begin{aligned}
P_{\text{w}}(y|\text{x})&=\frac1{Z_{\text{w}}(\text{x})}\exp{\sum_{i = 1}^n w_i f_i(\text{x},y)}\
Z_{\text{w}}(\text{x})&=\sum_y\exp{\sum_{i = 1}^n w_i f_i(\text{x},y)}
\end{aligned}
$$

• 求解对偶问题的极大化问题，并将其解记为 $\text{w}^*=\arg\max_{\text{w}}\Psi(\text{w})$
• 结论
  • 可以应用最优化算法求解对偶函数 $\Psi(\text{w})$ 的极大化问题，得到 $\text{w}^*$，用来表示 $P^*\in\mathcal{C}$
  • 因此 $P^*=P_{\text{w}^*}=P_{\text{w}^*}(y|\text{x})$ 是学习得到的最优模型(即最大熵模型)
  • 最大熵模型的学习归结为对偶函数 $\Psi(\text{w})$ 的极大化问题

6.2.4 极大似然估计

对偶函数的极大化 等价于 最大熵模型的极大似然估计 的证明：

• 基于训练数据得到经验概率分布 $\tilde{P}(X,Y)$
• 基于模型写出条件概率分布的对数似然函数

$$
\begin{aligned}
L_{\tilde{P}}(P_{\text{w}})
&=\ln\prod_{\text{x},y}P(y|\text{x})^{\tilde{P}(\text{x},y)}\
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\ln P(y|\text{x})\
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n w_i f_i(\text{x},y)-\sum_{\text{x},y} \tilde{P}(\text{x},y)\ln Z_{\text{w}}(\text{x})\
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n w_i f_i(\text{x},y)-\sum_{\text{x}} \tilde{P}(\text{x})\ln Z_{\text{w}}(\text{x})
\end{aligned}
$$

• 引入Language算子，得对偶函数

$$
\begin{aligned}
\Psi(\text{w})
&=\sum_{\text{x},y} \tilde{P}(\text{x})P_{\text{w}}(y|\text{x})\ln P_{\text{w}}(y|\text{x})\
&+\sum_{i=1}^n w_i\biggl(\sum_{\text{x},y} \tilde{P}(\text{x},y)f_i(\text{x},y)-\sum_{\text{x},y} \tilde{P}(\text{x})P_{\text{w}}(y|\text{x})f_i(\text{x},y)\biggl)\
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n w_i f_i(\text{x},y)+\sum_{\text{x},y} \tilde{P}(\text{x})P_{\text{w}}(y|\text{x})\biggl(\ln P_{\text{w}}(y|\text{x})-\sum_{i = 1}^n w_i f_i(\text{x},y)\biggl)\
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n w_i f_i(\text{x},y)-\sum_{\text{x},y}\tilde{P}(\text{x})P_{\text{w}}(y|\text{x})\ln Z_{\text{w}}(\text{x})\
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n w_i f_i(\text{x})-\sum_{\text{x},y} \tilde{P}(\text{x})\ln Z_{\text{w}}(\text{x})
\end{aligned}
$$

• 因为 $\sum_{y} P(y|\text{x})=1$，所以 $\sum_{\text{x},y} f(\cdot) P(y|\text{x})=\sum_{\text{x}} f(\cdot)$
• 将对数似然函数 和 对偶函数 比较，得 $\Psi(\text{w})=L_{\tilde{P}}(P_{\text{w}})$

最大熵模型与 Logistic 回归模型有着类似的形式，它们统称为「对数线性模型」。模型的学习就是在给定的训练数据下对模型进行极大似然估计或者正则化极大似然估计。

6.3 模型学习的最优化算法

因为目标函数是凸函数，因此采用数值优化方法可以求解极值。常用的求解无约束最优化问题的算法

6.3.1 改进的迭代尺度法

改进的迭代尺度法(Improved Iterative Scaling, IIS)是可以学习最大熵模型的最优化算法。

基本思路

• 假设最大熵模型的参数向量为 $\text{w}=(w_1,\cdots,w_n)^T$
• 寻找新的参数向量 $\text{w}+\delta=(w_1+\delta_1,\cdots,w_n+\delta_n)^T$，使得似然函数值增大
• 基于一种参数向量更新的方法：$\tau:\text{w}\rightarrow\text{w}+\delta$，对数似然函数的改变量为

$$
\begin{aligned}
L(\text{w}+\delta)-L(\text{w})
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\ln P_{\text{w}+\delta}(y|\text{x})-\sum_{\text{x},y} \tilde{P}(\text{x},y)\ln P_{\text{w}}(y|\text{x})\
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n \delta_i f_i(\text{x},y)-\sum_{\text{x}} \tilde{P}(\text{x})\ln\frac{Z_{\text{w}+\delta}(\text{x})}{Z_{\text{w}}(\text{x})}
\end{aligned}
$$

基于不等式 $-\ln \alpha \geq 1-\alpha,\alpha>0$，建立对数似然函数改变量的下界
$$
\begin{aligned}
L(\text{w}+\delta)-L(\text{w})
&\geq\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n \delta_i f_i(\text{x},y)+1-\sum_{\text{x}} \tilde{P}(\text{x})\ln\frac{Z_{\text{w}+\delta}(\text{x})}{Z_{\text{w}}(\text{x})}\
&=\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n \delta_i f_i(\text{x},y)+1-\sum_{\text{x}} \tilde{P}(\text{x})\sum_y P_{\text{w}}(y|\text{x})\exp{\sum_{i = 1}^n \delta_i f_i(\text{x},y)}
\end{aligned}
$$

将右端记为$A(\delta|\text{w})$，则 $L(\text{w}+\delta)-L(\text{w})\geq A(\delta|\text{w})$，故 $A(\delta|\text{w})$ 是对数似然函数改变量的下界。

如果找到合适的 $\delta$ 使下界 $A(\delta|\text{w})$ 提高，那么对数似然函数也会提高。然而，$\delta$ 是一个向量，即有多个变量，不易同时优化，而 IIS 就是试图一次只优化其中一个变量，而固定其他变量。

6.3.2 拟牛顿法

最大熵模型
$$
P_{\text{w}}(y|\text{x})=\frac{\exp{\sum_{i=1}^n w_i f_i(\text{x},y)}}{\sum_y\exp{\sum_{i = 1}^n w_i f_i(\text{x},y)}}
$$

目标函数
$$
\min_{\text{w}\in\mathbb{R}^n}f(\text{w})=\sum_{\text{x}}\tilde{P}(\text{x})\ln\sum_y\exp{\sum_{i = 1}^n w_i f_i(\text{x},y)}-\sum_{\text{x},y} \tilde{P}(\text{x},y)\sum_{i=1}^n w_i f_i(\text{x},y)
$$

梯度
$$
g(\text{w})=(\frac{\partial f(\text{w})}{\partial w_1},\cdots,\frac{\partial f(\text{w})}{\partial w_n})^T
$$

其中
$$
\frac{\partial f(\text{w})}{\partial w_i}=\sum_{\text{x},y} \tilde{P}(\text{x})P_{\text{w}}(y|\text{x})f_i(\text{x},y)-E_{\tilde{P}}(f_i),i=1,\cdots,n
$$
最大熵模型基于拟牛顿法的 BFGS 算法。

本章概要

• Logistic 回归模型是由条件概率分布表示的分类模型，可以用于二分类问题或者多分类问题
  • Logistic 回归模型源自 Logistic 分布，其分布函数 $F(\text{x})$ 是 S 形函数
  • Logistic 回归模型是由输入的线性函数表示的输出的对数几率模型
• 最大熵模型是由条件概率分布表示的分类模型，也可以用于二分类问题或者多分类问题
  • 最大熵模型由最大熵原理推导得出
  • 最大熵原理是模型学习或者参数估计的一个准则
  • 最大熵原理认为在所有可能的概率模型(分布)的集合中，熵最大的模型是最好的模型
  • 将最大熵原理应用到分类模型的学习中，将分类问题转化为约束最优化问题，求解此最优化问题的对偶问题得到最大熵模型
• Logistic 模型与最大熵模型
  • 都属于对数线性模型。(对比学习还可参考[^周志华，2018] Ch 03)
  • 都采用极大似然估计或者正则化最大似然估计来求解
    • 注 : 极大似然估计的原理性的说明可以参考 ( [^周志华，2018]Ch 07 P149, [^Duda,2003] Ch 03P67 )
  • 都可以将模型的学习过程形式化为无约束最优化问题
    • 求解最优化问题的算法包括：改进的迭代尺度法、梯度下降法、拟牛顿法
    • 最优化算法 : 在各种机器学习和模式识别的书里面都有介绍，推荐 ( [^周志华，2018] Appendix B, [^Hagan,2006] Ch 09 )