《统计学习方法》第六章：逻辑斯谛回归与最大熵模型

模型

逻辑斯谛回归模型

逻辑斯谛分布具有良好的性质，能够将 $(-\infty,+\infty)$ 映射至 $(-1，+1)$，因此选用逻辑斯谛分布作为回归模型。逻辑斯谛分布函数与密度函数为

$$\begin{align} F(x)&=P(\leqslant x)=\frac{1}{1+\mathrm{e}^{-(x-\mu)/\gamma}}\\ f(x)&=F'(x)=\frac{\mathrm{e}^{-(x-\mu)/\gamma}}{\gamma(1+\mathrm{e}^{-(x-\mu)/\gamma})^2} \end{align}$$

逻辑斯谛分布函数与密度函数的图像分别如下：

逻辑斯谛分布

将逻辑斯谛分布函数简化，可以得到 Sigmoid 函数：

$$S(x)=\frac{1}{1+\mathrm{e}^{-x}}=\frac{\mathrm{e}^x}{1+\mathrm{e}^x}$$

回忆二分类的感知机 $w\cdot x+b$，超平面将实例分作 $w\cdot x+b\geqslant 0$ 与 $w\cdot x+b< 0$ 两类。可以看出，$w\cdot x+b$ 的值域为实数域，那么就可以利用逻辑斯谛分布将实数域映射到 $(-1，+1)$，实现分类。

为了表述简洁，令 $w=(w^{(1)},w^{(2)},\cdots,w^{(n)},b)^{\mathrm{T}}$，$x=(x^{(1)},x^{(2)},\cdots,x^{(n)},1)^{\mathrm{T}}$，将 $w\cdot x$ 代入 Sigmoid 函数：

$$\begin{align} P(Y=1|x)&=\frac{\exp(w\cdot x)}{1+\exp(w\cdot x)}\\ P(Y=0|x)&=1-P(Y=1|x)=\frac{1}{1+\exp(w\cdot x)} \end{align}$$

这就是二项逻辑斯谛回归模型。从式中也能看到，若线性函数 $w\cdot x$越大，$P(Y=1|x)$ 概率越大；若线性函数 $w\cdot x$越小，$P(Y=0|x)$ 概率越大。最后就通过对比 $P(Y=1|x)$ 与 $P(Y=0|x)$ 的大小来确定实例的类别。

最大熵模型

最大熵原理认为，熵最大的模型是最好的模型。这是一个十分在「直觉」的原理，例如说，在等待公交车时，下一辆公交车只有两种情况——「乘」或「不乘」，基于这种判断，通常会认为下一辆公交车有 50% 的概率可乘，50% 的概率不可乘。

再例如，某事件有 $\{A,B,C,D,E\}$ 5 种情况，相应满足约束：

$$P(A)+P(B)+P(C)+P(D)+P(E)=1$$

在没有更多信息的情况下，根据最大熵原理，我们会认为

$$P(A)=P(B)=P(C)=P(D)=P(E)=\frac{1}{5}$$

如果额外获得了信息 $P(A)+P(B)=\frac{3}{10}$，那么根据最大熵原理就会认为

$$P(A)=P(B)=\frac{3}{20},\ P(C)=P(D)=P(E)=\frac{7}{30}$$

可以看出，在缺少信息的情况下，最大熵原理将那些不确定的部分都视作等可能。等概率表示了对于事实的无知，但是没有更多信息，这种判断又是合理的。

对于训练数据集，可以得到经验分布 $\tilde{P}(X=x,Y=y)$ 与 $\tilde{P}(X=x)$，这里的经验分布是用频数估计得到的。但是使用频数估计联合分布是不准确的，这种不准确在最大熵模型中会造成约束条件的不准确，而约束条件又是最大熵模型的关键。例如上例中，约束条件为 $P(A)+P(B)=\frac{3}{10}$，若该约束条件不准确，后续的概率估计也是无意义的。

因此在最大熵模型中需要引入特征函数，特征函数用于人为选取「合适」的实例：

$$\begin{equation} f(x,y)= \begin{cases} 1, &x\ 与\ y\ 满足某事实\\ 0, &否则 \end{cases} \end{equation}$$

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

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

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

$$E_P(f)=\sum_{x,y}\tilde{P}(x)P(y|x)f(x,y)$$

若模型准确，二者理应相等，即

$$E_{\tilde{P}}(f)=E_P(f)$$

Note 回忆条件概率基本公式 $P(x,y)=P(y|x)P(x)$。

满足所有约束条件的模型构成的集合为

$$\mathcal{C}\equiv \{P\in\mathcal{P}|E_P(f_i)=E_{\tilde{P}}(f_i)\}$$

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

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

在集合 $\mathcal{C}$ 中选出 $H(P)$ 最大的模型即为最大熵模型。

策略

逻辑斯谛回归模型

设数据集中的概率为

$$P(Y=1|x)=\pi(x),\ P(Y=0|x)=1-\pi(x)$$

构造对数似然函数：

$$\begin{align} L(w)&=\log\prod_{i}[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}\\ &=\sum_i[y_i\log\pi(x_i)+(1-y_i)\log(1-\pi(x_i))]\\ &=\sum_i[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i)] \end{align}$$

那么求 $L(w)$ 的极大值，就能得到估计值 $\hat{w}$，得到回归模型。也就是说，求解逻辑斯谛回归模型就是对于对数似然函数的最优化问题。

Note 似然函数定义为 $L(p)=\prod_i p^{x_i}(1-p)^{1-x_i}$，即抽样结果中各概率之积。由于每次抽样独立同分布的前提，可以认为似然函数为抽样结果（该事件）发生的概率。因为已经得到了该抽样结果，该事件发生的概率理应为 1，所以就要使似然函数最大化，这就是最大似然估计的原理。

广义拉格朗日函数

最大熵模型中使用了拉格朗日乘数法，因此有必要先介绍一下广义拉格朗日函数。回忆一下高等数学中的拉格朗日函数，若函数 $z=f(x,y)$ 有约束条件 $\varphi(x,y)=0$，那么拉格朗日函数就为

$$L(x,y)=f(x,y)+\lambda\varphi(x,y)$$

欲寻找函数 $z=f(x,y)$ 的可能极值点，只需令拉格朗日函数的各一阶偏导数为零，联立求解。

这里引入广义拉格朗日函数，若有约束最优化问题：

$$\begin{align} \min_x&\quad f(x)\\ \mathrm{s.t.}&\quad c_i(x)\leqslant0,\ h_j(x)=0 \end{align}$$

那么广义拉格朗日函数为

$$L(x,\alpha,\beta)=f(x)+\color{teal}{\sum_i\alpha_ic_i(x)}+\color{steelblue}{\sum_j\beta_jh_j(x)}$$

其中 $\alpha_i$ 与 $\beta_j$ 为拉格朗日乘子，$\alpha_i\geqslant0$。

可以看出，只要 $x$ 满足约束，$L(x,\alpha,\beta)$ 的第二项是递减的，第三项是不增的。那么就有

$$\begin{equation} \max_{\alpha,\beta:\alpha_i\geqslant0}L(x,\alpha,\beta)= \begin{cases} f(x), &x\ 满足约束\\ +\infty, &否则 \end{cases} \end{equation}$$

原来的约束最优化问题 $\min_xf(x)$ 在这里就可以改写为

$$\min_x\max_{\alpha,\beta:\alpha_i\geqslant0}L(x,\alpha,\beta)$$

在满足 Karush-Kuhn-Tucker（KKT）条件下，原始问题的解与对偶问题的解相等，即

$$\min_x\max_{\alpha,\beta:\alpha_i\geqslant0}L(x,\alpha,\beta)=\max_{\alpha,\beta:\alpha_i\geqslant0}\min_xL(x,\alpha,\beta)$$

最大熵模型

最大熵模型的学习过程是有约束的最优化问题：

$$\begin{align} \max_{P\in\mathcal{C}}&\quad H(P)=-\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\\ \mathrm{s.t.}&\quad E_P(f_i)=E_{\tilde{P}}(f_i),\ \sum_yP(y|x)=1 \end{align}$$

按照凸优化的习惯（求向下凸的函数的最小值），问题等价于

$$\begin{align} \min_{P\in\mathcal{C}}&\quad -H(P)=\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\\ \mathrm{s.t.}&\quad E_P(f_i)=E_{\tilde{P}}(f_i),\ \sum_yP(y|x)=1 \end{align}$$

构造拉格朗日函数 $L(P,w)$：

$$L(P,w)\equiv-H(P)+w_0\left[1-\sum_yP(y|x)\right]+\sum_iw_i[E_P(f_i)-E_{\tilde{P}}(f_i)]$$

在这里，原始问题的解与对偶问题的解同样是等价的，即

$$\underbrace{\min_{P\in\mathcal{C}}\max_wL(P,w)}_{原始形式}=\underbrace{\max_w\min_{P\in\mathcal{C}}L(P,w)}_{对偶形式}$$

那么就可以通过求解对偶问题来求解原始问题，具体来说，就是先求解 $\min_{P\in\mathcal{C}}L(P,w)$，固定 $w$，令 $\frac{\partial L(P,w)}{\partial P(y|x)}=0$，得到 $P(y|x)$ 的表达式后将其代入 $L(P,w)$ 得到 $\min_{P\in\mathcal{C}}L(P,w)$。再令 $\frac{\partial \min_{P\in\mathcal{C}}L(P,w)}{\partial w}=0$，最终得到 $P(y|x)$。

算法

逻辑斯谛回归模型和最大熵模型都是光滑的凸函数，适用于多种最优化方法，常用的方法包括迭代尺度算法、梯度下降法、牛顿法或拟牛顿法。

改进的迭代尺度法

令 $\frac{\partial L(P,w)}{\partial P(y|x)}=0$，可以得到

$$P(y|x)=\frac{\exp(\sum_iw_if_i(x,y))}{\exp(1-w_0)}$$

其中的 $\exp(1-w_0)$ 部分是个定值，不影响概率的相对大小，因此略去该项并归一化，得到

$$\begin{align} P_w(y|x)&=\frac{1}{Z_w(x)}\exp\left(\sum_iw_if_i(x,y)\right)\\ Z_w(x)&=\sum_y\exp\left(w_if_i(x,y)\right) \end{align}$$

对数似然函数为

$$L(w)=\log\prod_{x,y}P(y|x)^{\tilde{P}(x,y)}=\sum_{x,y}\tilde{P}(x,y)\log P(y|x)$$

将 $P_w(y|x)$ 代入得到

$$L(w)=\sum_{x,y}\tilde{P}(x,y)\sum_iw_if_i(x,y)-\sum_x\tilde{P}(x)\log Z_w(x)$$

迭代尺度法的思路就是寻找一个新参数向量 $w+\delta=(w_i+\delta_1,w_2+\delta_2,\cdots,w_n+\delta_n)^\mathrm{T}$，使 $L(w)$ 增大，并不断迭代更新 $w\rightarrow w+\delta$，最终使 $L(w)$ 最大。

为了简化计算，在该算法中需要引入一个量 $f^\#(x,y)$：

$$f^\#(x,y)=\sum_if_i(x,y)$$

$f^\#(x,y)$ 表示了所有特征出现的次数。

$w$ 更新前后似然函数的变化值为（证明略）

$$L(w+\delta)-L(w)\geqslant B(\delta|w)$$

$$B(\delta|w)=\sum_{x,y}\tilde{P}(x,y)\sum_i\delta_if_i(x,y)+1-\sum_x\tilde{P}(x)\sum_yP_w(y|x)\sum_i\left(\frac{f_i(x,y)}{f^\#(x,y)}\right)\exp(\delta_i,f^\#(x,y))$$

我们需要找到 $B(\delta|w)$ 的极值，让每次迭代后 $L(w)$ 尽可能大，因此求 $B(\delta|w)$ 对 $\delta_i$ 的偏导，并令其为零，得到

$$\underbrace{\sum_{x,y}\tilde{P}(x)P_w(y|x)f_i(x,y)}_{E_P(f_i)}\exp(\delta_if^\#(x,y))=E_{\tilde{P}}(f_i)$$

解该方程即可得到用于每次迭代的 $\delta$。

若 $f^\#(x,y)$ 为常数，那么

$$\delta_i=\frac{1}{f^\#(x,y)}\log\frac{E_{\tilde{P}}(f_i)}{E_P(f_i)}$$

若 $f^\#(x,y)$ 不是常数，通常使用数值计算的方法求解。

算法 6.1（IIS 算法）

输入：特征函数 $f_i$；经验分布 $\tilde{P}(X,Y)$；模型 $P_w(y|x)$；
输出：最优参数 $w^*_i$；最优模型 $P_{w^*}$。

对所有 $i$，取初值 $w_i=0$。
对每一个 $i$，
1. 解以下方程得到 $\delta_i$：
  $$\sum_{x,y}\tilde{P}(x)P_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))=E_{\tilde{P}}(f_i)$$
2. 更新 $w_i$：$w_i\leftarrow w_i+\delta_i$。
若不是所有 $w_i$ 收敛，重复第 2 步。

牛顿法与拟牛顿法

牛顿法

对于最优化的目标目标函数 $f(x)$，若满足二阶可微的前提，可以在 $x=x^{(k)}$ 处二阶泰勒展开：

$$f(x)=f(x^{(x)})+\nabla f(x^{(k)})\Delta x^{(k)}+\frac{1}{2}(\Delta x^{(k)})^\mathrm{T}\nabla^2f(x^{(k)})\Delta x^{(k)}$$

其中 $\Delta x^{(k)}=x-x^{(k)}$。牛顿法的思路就是利用二阶泰勒展开近似，寻找合理的下降方向 $p_k$，使 $f(x)$ 在数次迭代后到达极小值。显然当 $f(x)$ 达到极小值时梯度为 0。那么假设下一次（第 $k+1$ 次）迭代时 $f(x)$ 就能达到极小值，也就是令上式在 $x^{(k+1)}$ 处的梯度为零：

$$\begin{align} \nabla f(x)&=\nabla f(x^{(k)})+\nabla^2f(x^{(k)})\Delta x^{(k)}\\ \nabla f(x^{(k+1)})&=\nabla f(x^{(k)})+\nabla^2f(x^{(k)})(x^{(k+1)}-x^{(k)})=0\\ x^{(k+1)}&=x^{(k)}-\nabla^2f(x^{(k)})^{-1}\nabla f(x^{(k)}) \end{align}$$

将其中的 $\nabla^2f(x^{(k)})^{-1}$ 记作 $H^{-1}_k$，是黑塞矩阵的逆，将 $\nabla f(x^{(k)})$ 记作 $g_k$。令 $p_k=-H^{-1}_kg_k$，称为牛顿方向，那么每次迭代的过程就是

$$x^{(k+1)}=x^{k}+p_k$$

Note 这里的泰勒展开为矩阵形式，因此式中带有转置与逆等符号，若对求导过程有疑惑，可以参考泰勒展开的矩阵形式。

拟牛顿法

考虑以上推导过程中得到的

$$\begin{align} \nabla f(x^{(k+1)})&=\nabla f(x^{(k)})+\nabla^2f(x^{(k)})(x^{(k+1)}-x^{(k)})\\ g_{k+1}-g_k&=H_k(x^{(k+1)}-x^{(k)})\\ \end{align}$$

令 $y_k=g_{k+1}-g_k$，$\delta_k=x^{(k+1)}-x^{(k)}$，可以改写为

$$\begin{align} y_k&=H_k\delta_k\\ H^{-1}_ky_k&=\delta_k \end{align}$$

由于牛顿法每次迭代都需要计算黑森矩阵的逆 $H^{-1}_k$，逆矩阵的计算过程比较繁琐，拟牛顿法的思路是寻找一个矩阵 $G_k$，使其代替逆黑森矩阵：

$$G_{k+1}y_k=\delta_k$$

或是用 $B_k$ 逼近黑塞矩阵：

$$B_{k+1}\delta_k=y_k$$

那么每次迭代的步骤就是更新该矩阵：

$$B_{k+1}=B_k+\Delta B_k$$

拟牛顿矩阵更新方式不同，会有不同的计算公式和算法，这里以 BFGS 算法为例推导矩阵更新公式。

假设 $B_{k+1}=B_k+P_k+Q_k$，其中 $P_k$ 与 $Q_k$ 为待定矩阵：

$$B_{k+1}\delta_k=\color{teal}{y_k}=\color{steelblue}{B_k\delta_k}+\color{teal}{P_k\delta_k}+\color{steelblue}{Q_k\delta_k}$$

$P_k$ 与 $Q_k$ 在该式中可以有多种取法，这里用最简单的取法：

$$\begin{align} &\color{teal}{P_k\delta_k=y_k}\\ &\color{steelblue}{Q_k\delta_k=-B_k\delta_k} \end{align}$$

那么就可以得到迭代公式：

$$B_{k+1}=B_k+\frac{y_ky^\mathrm{T}_k}{y^\mathrm{T}_k\delta_k}-\frac{B_k\delta_k\delta^\mathrm{T}_kB_k}{\delta^\mathrm{T}_kB_k\delta_k}$$

Note 式中有许多 $y_ky^\mathrm{T}_k$ 类型结构，这是为了将向量转化为方阵，才有逆运算，否则向量不具有除法运算。

算法 6.2（最大熵模型的 BFGS 算法）

输入：特征函数 $f_i$；经验分布 $\tilde{P}(x,y)$；目标函数 $f(w)=-L(w)$，梯度 $g(w)=\nabla f(w)$，精度 $\varepsilon$；
输出：最优参数值 $w^*$；最优模型 $P_{w^*}(y|x)$。

选定初始点 $w^{(0)}$，取 $B_0$ 为正定对称矩阵，置 $k=0$；
计算 $g_k=g(w^{(k)})$。若 $||g_k||<\varepsilon$，则停止，$w^*=w^{(k)}$，否则继续。
$B_kp_k=-g_k$，求 $p_k$。
求 $\lambda_k$ 使得 $f(w^{(k)}+\lambda_kp_k)=\min_{\lambda\geqslant0}f(w^{(k)}+\lambda p_k)$。
$w^{(k+1)}=w^{(k)}+\lambda_kp_k$。
$g_{k+1}=g(w^{(k+1)})$，若 $||g_{k+1}||\varepsilon$，则停止，$w^*=w^{(k)}$，否则按 BFGS 迭代公式求 $B_{k+1}$。
$k=k+1$，回到步骤 3。

《统计学习方法》第六章：逻辑斯谛回归与最大熵模型

Leo

模型

逻辑斯谛回归模型

最大熵模型

策略

逻辑斯谛回归模型

广义拉格朗日函数

最大熵模型

算法

改进的迭代尺度法

牛顿法与拟牛顿法

牛顿法

拟牛顿法

References