统计学习方法笔记之逻辑斯谛模型与最大熵模型

2019-08-15 本文已影响1人 Aengus_Sun

更多文章可以访问我的博客Aengus | Blog

逻辑斯谛回归（Logistic Regression）模型是经典的分类方法，而最大熵则是概率模型中学习的一个准则，将其推广到分类问题得到最大熵模型（maximum entropy model）。两者都属于对数线性模型。

逻辑斯谛模型

逻辑斯谛分布

设 $X$ 是连续随机变量， $X$ 服从逻辑斯谛分布是指 $X$ 具有以下分布函数和密度函数：
$F(x) = P(X< x) = \frac{1}{1+e^{\frac{-(x-\mu)}{\gamma}}}$

$f(x) = F'(x) = \frac{e^{\frac{-(x-\mu)}{\gamma}}}{\gamma(1+e^{\frac{-(x-\mu)}{\gamma}})^2}$

其中， $\mu$ 是位置参数， $\gamma >0$ 为形状参数。

逻辑斯谛分布的密度函数 $f(x)$ 和分布函数 $F(x)$ 如下所示。分布函数属于逻辑斯谛函数，其图像是一条 $S$ 形曲线，该曲线以 $(\mu, \frac{1}{2})$ 为中心对称，即满足：
$F(-x+\mu)- \frac{1}{2} = -F(x+\mu)+\frac{1}{2}$
曲线在中心附近增长速度较快，在两端增长速度较慢。形状参数 $\gamma$ 的值越小，曲线在中心附近增长越快。

逻辑斯谛分布

二项逻辑斯谛回归

二项逻辑斯谛回归模型是一种分类模型，由条件概率分布 $P(Y|X)$ 表示，形式为参数化的逻辑斯谛分布， $X$ 的取值范围为实数， $Y$ 的取值为1或0，那么如下的条件概率分布：
$P(Y=1|x) = \frac{\exp(w \cdot x+b)}{1+\exp(w \cdot x+b)} \\ P(Y=0|x) = \frac{1}{1+\exp(w \cdot x+b)}$
其中 $w \cdot x$ 表示内积， $x \in R^n$ ， $w \in R^n$ 和 $b \in R$ 是参数， $w$ 称为权值向量， $b$ 称为偏置。

对于输入的实例 $x$ ，逻辑斯谛模型计算其条件概率 $P(Y=1|x)$ 与 $P(Y=0|x)$ ，通过比较大小将 $x$ 分到概率值大的那一类。

有时为了方便，将权值向量与输入实例 $x$ 进行扩充，仍记作 $w,x$ ，即 $w=(w^{(1)},w^{(2)},\cdots,w^{(n)}, b)^T$ ， $x=(x^{(1)},x^{(2)}, \cdots,x^{(n)},1)^T$ ，这时，逻辑斯谛模型就变成了：
$P(Y=1|x) = \frac{\exp(w \cdot x)}{1+\exp(w \cdot x)} \\ P(Y=0|x) = \frac{1}{1+\exp(w \cdot x)}$

模型特点

一个事件的几率是指该事件发生的概率和不发生的概率的比值。如果一个事件发生的概率是 $p$ ，那么该事件的几率就是 $\frac{p}{1-p}$ ，该事件的对数几率就是：
$logit(p) = \log\frac{p}{1-p}$
对于逻辑斯谛模型来说， $Y=1$ 的几率就是：
$\log \frac{P(Y=1|x)}{1-P(Y=1|x)} = w \cdot x$
也就是说，在逻辑斯谛模型中，输出 $Y=1$ 的对数几率是输入 $x$ 的线性函数。考虑到公式
$P(Y=1|x) = \frac{\exp(w \cdot x)}{1+\exp(w \cdot x)}$
可以得到，线性函数的值越接近于正无穷，概率值就越接近1；线性函数的值越接近负无穷，概率值就越接近0。

多项逻辑斯谛回归

设随机变量 $Y$ 的取值集合为 $\{1,2,\cdots,K\}$ ，那么多项逻辑斯谛回归模型是：
$P(Y=k|x) = \frac{\exp(w_k \cdot x)}{1+\sum^{K-1}_{k=1}\exp(w_k \cdot x)},k=1,2,\cdots,K-1 \\ P(Y=K|x) = \frac{1}{1+\sum^{K-1}_{k=1}\exp(w_k \cdot x)}$
其中 $x\in R^{n+1}$ ， $w \in R^{n+1}$ 。

模型参数估计

可以应用极大似然估计模型参数。

设：
$P(Y=1|x) = \pi(x),P(Y=0|x) = 1 - \pi(x)$
似然函数为：
$\prod^N_{i=1} [\pi(x_i)]^{y_i}[1 - \pi(x_i)]^{1-y_i}$
对数似然函数为：
$\begin{align} L(w) &= \sum^N_{i=1}[y_i \log \pi(x_i) + (1-y_i)\log(1-\pi(x_i))] \\ &=\sum^N_{i=1}\left[ y_i\log \frac{\pi(x_i)}{1-\pi(x_i)} + \log(1-\pi(x_i)) \right] \\ &= \sum^N_{i=1}[y_i(w \cdot x_i) - \log (1+\exp(w \cdot x_i))] \end{align}$
对 $L(w)$ 求极大值，得到 $w$ 的估计值。这样，问题就变成了以对数似然函数为目标函数的最优化问题。逻辑斯谛回归学习中通常采用的方法是梯度下降法及拟牛顿法。

最大熵模型

最大熵原理认为，学习概论模型时，在所有可能的概率模型分布中，熵最大的模型时最好的模型。

假设离散随机变量 $X$ 的概率分布是 $P(X)$ ，则其熵为：
$H(P) = -\sum_x P(x)\log P(x)$
熵满足下列不等式：
$0 \leq H(P) \leq \log|X|$
式中， $|X|$ 是 $X$ 的取值个数，当且仅当 $X$ 的分布是均匀分布时右边的等号成立，这就是说 $X$ 服从均匀分布时，熵最大。换句话说，最大熵原理认为要选择的概率模型首先必须满足已有的事实，在没有更多信息的情况下，那些不确定的部分都是等可能的。

定义

首先考虑模型应该满足的条件。给定数据集，可以确定联合分布 $P(X,Y)$ 的经验分布和 $P(X)$ 的经验分布，记作 $\widetilde{P}(X,Y)$ 和 $\widetilde{P}(x)$ ：
$\widetilde{P}(X=x,Y=y) = \frac{v(X=x,Y=y)}{N}\\ \widetilde{P}(X=x) = \frac{v(X=x)}{N}$
$v(X=x,Y=y)$ 表示样本 $(x,y)$ 出现的频数； $v(X=x)$ 表示训练数据中样本 $x$ 出现的频数， $N$ 代表训练样本容量。

特征函数 $f(x,y)$ 描述输入 $x$ 与输出 $y$ 是否满足某一事实：
$f(x,y) = \left\{ \begin{align} 1,\ x\; and \; y \;satify \;a\;fact; \\ 0,\ otherwise \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{align} \right.$
$E_{\widetilde{P}}(f)$ 代表特征函数 $f(x,y)$ 对 $\widetilde{P}(X,Y)$ 的期望值：
$E_{\widetilde{P}}(f) = \sum_{x,y}\widetilde{P}(x,y)f(x,y)$
$E_P(f)$ 代表关于模型 $P(Y|X)$ 特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 与 $\widetilde{P}(X)$ 的期望值：
$E_P(f) = \sum_{x,y}\widetilde{P}(x)P(y|x)f(x,y)$
如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值想等，即：
$E_P(f) = E_{\widetilde{P}}(f)$
将上式作为模型学习的约束条件，假设有 $n$ 个特征函数 $f_i(x,y)$ ，那么就有 $n$ 个约束条件。

设满足所有约束条件的模型集合为：
$\mathcal{C}\equiv \{P\in \mathcal{P} | E_P(f_i = E_{\widetilde{P}}(f_i)),i=1,2,\cdots,n \}$
定义在条件概率分布 $P(Y|X)$ 上的条件熵为：
$H(P) = -\sum_{x,y}\widetilde{P}(x)P(y|x) \log P(y|x)$
则模型集合 $\mathcal{C}$ 中条件熵最大的模型称为最大熵模型。式中的对数为自然对数。

模型的学习

最大熵模型的学习也就是求解最大熵模型的过程。对于给定的数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$ 以及特征函数 $f_i(x,y),i=1,2,\cdots,n$ ，最大熵模型的学习等价于约束最优化问题：
$\max_{P \in \mathcal{C}} H(P) = -\sum_{x,y}\widetilde{P}(x)P(y|x) \log P(y|x) \\ s.t. \ E_P(f_i) = E_{\widetilde{P}}(f_i), \quad i=1,2,\cdots,n \\ \sum_y P(y|x) = 1$
按照最优化问题的习惯，将求最大值问题改写为等价的求最小值问题：
$\min_{P \in \mathcal{C}} - H(P) = \sum_{x,y}\widetilde{P}(x)P(y|x) \log P(y|x) \\ s.t. \ E_P(f_i) = E_{\widetilde{P}}(f_i), \quad i=1,2,\cdots,n \\ \sum_y P(y|x) = 1$
这里，将约束最优化的原始问题转化为无约束最优化的对偶问题。首先，引入拉格朗日乘子 $w_0,w_1,\cdots,w_n$ ，定义拉格朗日函数 $L(P,w)$ ：
$L(P,w) = -H(P)+w_o(1-\sum_y P(y|x) ) + \sum^n_{i=1}w_i(E_{\widetilde{P}}(f_i)-E_P(f_i))$
最优化的原始问题是 $\min_{P \in \mathcal{C}} \max_w L(P,w)$ ，对偶问题是 $\max_w \min_{P \in \mathcal{C}}L(P,w)$ 。

首先，求解对偶问题的极小化问题 $\min_{P \in \mathcal{C}}L(P,w)$ 。 $\min_{P \in \mathcal{C}}L(P,w)$ 是 $w$ 的函数，将其记作：
$\psi(w) = \min_{P \in \mathcal{C}}L(P,w) = L(P_w,w)$
$\psi(w)$ 称为对偶函数，同时将其解记作：
$P_w = \arg \min_{P \in \mathcal{C}} L(P,w) = P_w(y|x)$
具体地，求 $L(P,w)$ 对 $P(y|x)$ 的偏导数并令其等于0，在 $\widetilde{P} > 0$ 的情况下，解得：
$P(y|x) = \frac{\exp(\sum^n_{i=1}w_i f_i(x,y))}{exp(1-w_0)}$
由于 $\sum_y P(y|x) = 1$ ，得：
$P_w (y|x) = \frac{1}{Z_w(x)}\exp(\sum^n_{i=1}w_i f_i(x,y))$
其中：
$Z_w(x) = \sum_y \exp(\sum^n_{i=1}w_if_i(x,y))$
称为规范化因子。

然后求解对偶问题外部的极大化问题 $\max_w \psi(w)$ ，

将其解记为 $w^*$ ，即 $w^* = \arg \max_w \psi(w)$ ，也就是说，可以应用最优化算法求对偶函数 $\psi(w)$ 的极大化，得到 $w^*$ ，即最大熵模型。

最优化算法

改进的迭代尺度算法IIS

假设输入特征函数 $f_1(x,y),f_2(x,y),\cdots,f_n(x,y)$ ，经验分布 $\widetilde{P}(X,Y)$ ，模型 $P_w(y|x)$ ，按以下步骤求解：

（1）对所有 $i \in \{1, 2, \cdots, n\}$ ，取初值 $w_i=0$ ；

（2）对每一 $i \in \{1, 2, \cdots, n\}$ ，

（a）令 $\delta_i$ 是方程
$\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y)\exp(\delta_i,f^\#(x,y))=E_{\widetilde{P}}(f_i)$
的解，其中：
$f^\#(x,y) = \sum^n_{i=1}f_i(x,y)$
（b）更新 $w_i$ 值： $w_i \gets w_i + \delta_i$ ；

（3）如果不是所有的 $w_i$ 都收敛，重复（2）步；

拟牛顿法

对于最大熵模型而言，
$P_w(y|x) = \frac{\exp(\sum^n_{i=1}w_i f_i(x,y))}{\sum_y \exp(\sum^n_{i=1}w_if_i(x,y))}$
目标函数：
$\min_{w \in R^n} f(w) = \sum_x \widetilde{P}(x)\log \sum_y \exp(\sum^n_{i=1}w_i f_i(x,y)) - \sum_{x,y}\widetilde{P}(x,y)\sum^n_{i=1}w_if_i(x,y)$
梯度：
$g(w) = \left( \frac{\partial f(w)}{\partial w_1}, \frac{\partial f(w)}{\partial w_2}, \cdots, \frac{\partial f(w)}{\partial w_n} \right)^T$
其中
$\frac{\partial f(w)}{\partial w_i} = \sum^n_{i=1}\widetilde{P}(x,y)P_w(y|x)f_i(x,y) - E_{\widetilde{P}}(f_i), \quad i=1,2,\cdots,n$
响应的拟牛顿法BFGS如下：

假设输入特征函数 $f_1(x,y),f_2(x,y),\cdots,f_n(x,y)$ ，经验分布 $\widetilde{P}(X,Y)$ ，目标函数 $f(w)$ ，梯度 $g(w)=\nabla f(w)$ ，精度要求 $\varepsilon$ ，按以下步骤求解：

（1）选定初始点 $w^{(0)}$ ，取 $B_0$ 为正定对称矩阵，置 $k=0$ ；

（2）计算 $g_k=g(w^{(k)})$ 。若 $||g_k|| < \varepsilon$ ，则停止计算，得 $w^* = w^{(k)}$ ；否则转（3）；

（3）由 $B_k p_k = -g_k$ ，求出 $p_k$ ；

（4）一维搜索：求 $\lambda_k$ 使得：
$f(w^{(k)} +\lambda_kp_k) = \min_{\lambda \geq 0}f(w^{(k)} + \lambda p_k)$
（5）置 $w^{(k+1)} = w^{(k)}+\lambda_k p_k$ ；

（6）计算 $g_{k+1} = g(w^{(k+1)})$ ，若 $||g_{k+1}|| < \varepsilon$ ，则停止计算，得 $w^* = w^{(k+1)}$ ；否则，按下式求出 $B_{k+1}$ ：
$B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T \delta_k} - \frac{B_k \delta_k \delta^T_k B_k}{\delta_k^T B_k \delta_k}$
其中，
$y_k = g_{k+1} - g_k, \quad \delta_k = w^{(k+1)} - w^{(k)}$
（7）置 $k = k+1$ ，转（3）；