第六章 逻辑斯蒂回归与最大熵模型

逻辑斯蒂回归（logistic regression）是统计学习中的经典分类方法。

最大熵是概率模型学习的一个准则，将其推广到分类问题得到最大熵模型（maximum entropy model）。

逻辑斯蒂回归模型与最大熵模型都属于对数线性模型。

6.1 逻辑斯蒂回归模型

6.1.1 逻辑斯蒂分布

首先介绍逻辑斯蒂分布（logistic distribution）。

定义 6.1（逻辑斯蒂分布） 设$X$是连续随机变量，$X$服从逻辑斯蒂分布是指$X$具有下列分布函数和密度函数：

$$F(x) = P(X \leq x) = \frac{1}{1 \ + \ e^{-(x - \mu)/\gamma}} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.1)$$ $$f(x) = F'(x) = \frac{e^{-(x - \mu)/\gamma}}{\gamma(1 \ + \ e^{-(x - \mu)/\gamma})^2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.2)$$

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

分布函数属于逻辑斯蒂函数，其图形是一条$S$形曲线（sigmoid curve）。该曲线以点$(\mu,\frac{1}{2})$为中心对称，即满足

$$F(-x \ + \ \mu) - \frac{1}{2} = -F(x \ + \ \mu) + \frac{1}{2}$$

形状参数$\gamma$的值越小，曲线在中心附近增长得越快。

6.1.2 二项逻辑斯蒂回归模型

二项逻辑斯蒂回归模型（binomial logistic regression model）是一种分类模型，由条件概率分布$P(Y|X)$表示，形式为参数化的逻辑斯蒂分布。

定义 6.2（逻辑斯蒂回归模型） 二项逻辑斯蒂回归模型是如下的条件概率分布：

$$P(Y=1|x) = \frac{\exp(\omega·x + b)}{1 \ + \ \exp(\omega·x + b)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.3)$$ $$P(Y=0|x) = \frac{1}{1 \ + \ \exp(\omega·x + b)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.4)$$

这里，$x \in R^n$是输入，$Y \in \{0,1\}$是输出，$\omega \in R^n $和$b \in R$是参数，$\omega$称为权值向量，$b$称为偏置，$\omega·x$为$\omega$和$x$的内积。

对于给定的输入实例$x$，逻辑斯蒂回归比较两个条件概率值的大小，将实例$x$分到概率值较大的那一类。

有时为了方便，将权值向量和输入向量加以扩充，仍记作$\omega,x$，即$\omega = (\omega^{(1)},\omega^{(2)},…,\omega^{(n)},b)^T,\ x = (x^{(1)},x^{(2)},…,x^{(n)},1)$。这时，逻辑斯蒂回归模型如下：

$$P(Y=1|x) = \frac{\exp(\omega·x)}{1 \ + \ \exp(\omega·x)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.5)$$ $$P(Y=0|x) = \frac{1}{1 \ + \ \exp(\omega·x)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.6)$$

---

一个事件的几率（odds）是指该事件发生的概率与该事件不发生的概率的比值。如果事件发生的概率是$p$，那么该事件的几率是$\frac{p}{1-p}$，该事件的对数几率（log odds）或logit函数是

$$logit(p) = \log\frac{p}{1-p}$$

对于逻辑斯蒂回归而言，由式$(6.5)$与式$(6.6)$得

$$\log\frac{P(Y=1|x)}{1\ - \ P(Y=1|x)} = \omega ·x$$

这就是说，在逻辑斯蒂回归模型中，输出$Y=1$的对数几率是输入$x$的线性函数。或者说，输出$Y=1$的对数几率是由输入$x$的线性函数表示的模型，即逻辑斯蒂回归模型。

6.1.3 模型参数估计

逻辑斯蒂回归模型学习时，对于给定的训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$，其中，$x_i \in R^n, y_i \in\{0,1\} $，可以应用极大似然估计法估计模型参数，从而得到逻辑斯蒂回归模型。

设：

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

似然函数为

$$\prod\limits_{i=1}^{N}[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}$$

对数似然函数为

$$L(\omega) = \sum\limits_{i=1}^{N}[y_i \log \pi(x_i)\ + \ (1-y_i)\log(1-\pi(x_i))]$$ $$\ \ \ \ =\sum\limits_{i=1}^{N}[y_i \log \frac{\pi(x_i)}{1-\pi(x_i)}\ + \ \log(1-\pi(x_i))]$$ $$\ \ =\sum\limits_{i=1}^{N}[y_i (\omega·x_i)\ - \ \log(1+\exp(\omega · x_i))]$$

对$L(\omega)$求极大值，得到$\omega$的估计值。

这样，问题就变成了以对数似然函数为目标函数的最优化问题。逻辑斯蒂回归学习中通常采用的方法是梯度下降法及拟牛顿法。

6.1.4 多项逻辑斯蒂回归

上面介绍的逻辑斯蒂回归模型是二项分类模型，用于二类分类。可以将其推广为多项逻辑斯蒂回归模型（multi-nominal logistic regression model），用于多类分类。

设离散型随机变量$Y$的取值集合是$\{1,2,…,K\}$，那么多项逻辑斯蒂回归模型是

$$P(Y=k|x) = \frac{\exp(\omega_k·x)}{1 \ + \ \sum\limits_{k=1}^{K-1}\exp(\omega_k·x)}, \ \ k = 1,2,...,K-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.7)$$ $$P(Y=K|x) = \frac{1}{1 \ + \ \sum\limits_{k=1}^{K-1}\exp(\omega_k·x)}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.8)$$

这里，$x \in R^{n+1},\omega_k \in R^{n+1}$。

二项逻辑斯蒂回归的参数估计法也可以推广到多项逻辑斯蒂回归。

6.2 最大熵模型

最大熵模型（maximum entropy model）由最大熵原理推导实现。

6.2.1 最大熵原理

最大熵原理认为，学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。通常用约束条件来确定概率模型的集合，所以，最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型。

假设离散随机变量$X$的概率分布是$P(X)$，则其熵是

$$H(P) = -\sum\limits_{x}P(x)\log P(x)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.9)$$

熵满足下列不等式：

$$0 \leq H(P) \leq \log|X|$$

式中，$|X|$是$X$的取值个数，当且仅当$X$的分布是均匀分布时右边的等号成立。这就是说，当$X$服从均匀分布时，熵最大。

直观地，最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分都是“等可能的”。最大熵原理通过熵的最大化来表示等可能性。“等可能”不容易操作，而熵则是一个可优化的数值指标。

6.2.2 最大熵模型的定义

假设分类模型是一个条件概率分布$P(Y|X),X \in \chi \subseteq R^n$表示输入，$Y \in \mathcal{Y}$表示输出，$\chi $和$\mathcal{Y}$分别是输入和输出的集合。这个模型表示的是对于给定的输入$X$，以条件概率$P(Y|X)$输出$Y$。

给定一个训练数据集

$$T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$$

学习的目标是用最大熵原理选择最好的分类模型。

---

首先考虑模型应该满足的条件。给定训练数据集，可以确定联合分布$P(X,Y)$的经验分布和边缘分布$P(X)$的经验分布，分别以$\tilde{P}(X,Y)$和$\tilde{P}(X)$表示。这里，

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

其中，$\upsilon(X=x,Y=y)$表示训练数据中样本$(x,y)$出现的频数，$\upsilon(X=x)$表示训练数据中输入$x$出现的频数，$N$表示训练样本容量。

用特征函数（feature function）$f(x,y)$描述输入$x$和输出$y$之间的某一个事实。其定义是

$$f(x,y) = \lbrace_{0, \ \ \ 否则}^{1,\ \ \ x与y满足某一事实}$$

特征函数$f(x,y)$关于经验分布$\tilde{P}(X,Y)$的期望值，用$E_{\tilde{P}}(f)$表示：

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

特征函数$f(x,y)$关于模型$P(Y|X)$与经验分布$\tilde{P}(X)$的期望值，用$E_P(f)$表示：

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

如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等，即

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

或

$$\sum\limits_{x,y}\tilde{P}(x)P(y|x)f(x,y) = \sum\limits_{x,y}\tilde{P}(x,y)f(x,y)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.11)$$

将式$(6.10)$或式$(6.11)$作为模型学习的约束条件。假设有$n$个特征函数$f_i(x,y),\ \ i=1,2,…,n$，那么就有$n$个约束条件。

---

定义 6.3（最大熵模型） 假设满足所有约束条件的模型集合为

$$\mathcal{C} \equiv \{P\in \mathcal{P}|E_P(f_i)=E_{\tilde{P}}(f),\ \ \ i=1,2,...,n\}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.12)$$

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

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

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

6.2.3 最大熵模型的学习

最大熵模型的学习过程就是求解最大熵模型的过程。最大熵模型的学习可以形式化为约束最优化问题。

对于给定的训练数据集$T = \{(x_1,y_1),(x_2,y_2),…,(x_N,y_N)\}$以及特征函数$f_i(x,y),i=1,2,…,n$，最大熵模型的学习等价于约束最优化问题：

$$\max\limits_{P \in \mathcal{C}} H(P) = -\sum\limits_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)$$ $$s.t.\ \ \ E_P(f_i)=E_{\tilde{P}}(f_i),\ \ \ i=1,2,...,n$$ $$\sum\limits_{y} P(y|x) = 1$$

按照最优化问题的习惯，将求最大值问题改写为等价的求最小值问题：

$$\min\limits_{P \in \mathcal{C}} -H(P) = \sum\limits_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.14)$$ $$s.t.\ \ \ E_P(f_i) - E_{\tilde{P}}(f_i) = 0,\ \ \ i=1,2,...,n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.15)$$ $$\sum\limits_{y} P(y|x) = 1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.16)$$

求解约束最优化问题$(6.14)~(6.16)$，所得出的解，就是最大熵模型学习的解。具体推导省略。详见《统计学习方法-李航》98~100页。

可以应用最优化算法求对偶函数$\Psi(\omega)$的极大化，得到$\omega^$，用来表示$P^ \in \mathcal{C}$。这里，$P^=P_{\omega^}=P_{\omega^*}(y|x)$是学习到的最优模型（最大熵模型）也就是说，最大熵模型的学习归结为对偶函数$\Psi(\omega)$的极大化。

6.2.4 极大似然估计

对偶函数极大化等价于最大熵模型的极大似然估计。对偶函数$\Psi(\omega)$等价于对数似然函数$L_{\tilde{P}}(P_\omega)$。具体推导省略。详见《统计学习方法-李航》102~103页。

这样，最大熵模型的学习问题就转换为具体求解对数似然函数极大化或对偶函数极大化的问题。

可以将最大熵模型写成更一般的形式。

$$P_{\omega}(y|x)=\frac{1}{Z_{\omega}(x)}\exp(\sum\limits_{i=1}^n \omega_if_i(x,y))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.28)$$

其中，

$$Z_{\omega}(x)=\sum\limits_{y} \exp(\sum\limits_{i=1}^n \omega_if_i(x,y))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6.29)$$

最大熵模型与逻辑斯蒂回归模型由类似的形式，它们又称为对数线性模型（log linear model）。模型学习就是在给定的训练数据条件下对模型进行极大似然估计或正则化的极大似然估计。

6.3 模型学习的最优化算法

逻辑斯蒂回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。从最优化的观点看，这时的目标函数具有很好的性质。它是光滑的凸函数，因此多种最优化的方法都适用，保证能找到全局最优解。常用的方法有改进的迭代尺度法、梯度下降法、牛顿法和拟牛顿法。牛顿法或拟牛顿法一般收敛速度更快。

6.3.1 改进的迭代尺度法

改进的迭代尺度法（improved iterative scaling，IIS）是一种最大熵模型学习的最优化算法。

6.3.2 拟牛顿法