Day14~15 第六章 Logistic 回归与最大熵模型

1 Logistc 回归模型

1.1 Logistic 分布

定义 6.1 (logistic 分布) 设 $X$ 是连续随机变量， $X$ 服从 logistic 分布是指 $X$ 具有下列分布函数和密度函数
$\begin{align} F(x)=P(X\leqslant x)=\frac{1}{1+e^{-(x-\mu)/\gamma}}\\ f(x)=F'(x)=\frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}\\ \end{align}$ 其中， $\mu$ 为位置参数， $\gamma >0$ 为形状参数。

1.2 二项 logistic 回归模型

二项 logistic 回归模型由条件概率分布 $P(Y|X)$ 表示，形式为参数化的 logistic 分布。这里随机变量 $X$ 取值为实数， $Y$ 取值为 0 或 1。
定义 6.2 (二项 logistic 回归模型) $\begin{align} P(Y=1|x)=\frac{\exp(\omega \cdot x +b)}{1+\exp(\omega \cdot x +b)}\\ P(Y=0|x)=\frac{1}{1+\exp(\omega \cdot x +b)}\\ \end{align}$ 其中， $x\in \mathbb{R}^n$ 为输入， $Y\in \{0,1\}$ 为输出， $\omega\in\mathbb{R}^n$ 和 $b\in\mathbb{R}$ 为参数， $\omega$ 称为权重向量， $b$ 称为偏置，符号 “ $\cdot$ ” 表示向量内积。
二项 logistic 回归模型对于给定的输入实例 $x$ ，可以通过定义计算 $P(Y=1|x)$ 与 $P(Y=|x)$ 并比较大小，将实例 $x$ 分到概率值更大的那一类。

有时为了方便，令 $\tilde{\omega} = (\omega^T,b)^T$ ， $\tilde{x} = (x^T,1)^T$ ，有 $\tilde{\omega}\cdot\tilde{x}=\omega \cdot x +b$ 。形式上仍然记为 $\omega \cdot x$ ，此时 logistic 回归模型为：
$\begin{align} P(Y=1|x)=\frac{\exp(\omega \cdot x)}{1+\exp(\omega \cdot x)}\\ P(Y=0|x)=\frac{1}{1+\exp(\omega \cdot x)}\\ \end{align}$

1.3 模型参数估计

Logisitic 回归模型学习时，给定训练集 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$ ，其中， $x_i\in \mathbb{R}^n$ ， $y_i\in\{0,1\}$ ，一般可以应用极大似然估计法估计模型参数。求得对数似然函数为
$L(\omega) = \sum\limits_{i=1}^N [y_1(\omega\cdot x_i)-\log(1+\exp(\omega\cdot x_i))]$ 对 $L(\omega)$ 求最大值，即可求到 $\omega$ 的估计值 $\hat{\omega}$ 。那么学习得到的模型为
$\begin{align} P(Y=1|x)=\frac{\exp(\hat{\omega} \cdot x)}{1+\exp(\hat{\omega}\cdot x)}\\ P(Y=0|x)=\frac{1}{1+\exp(\hat{\omega} \cdot x)}\\ \end{align}$

1.4 Logisitc 回归模型的优缺点

1. 优点

实现简单，应用广泛。
分类时计算量非常小，速度很快，存储资源低。
便利的观测样本概率分数。

2. 缺点

当特征空间很大时，逻辑回归的性能不是很好。
容易欠拟合，一般准确度不太高。
依赖所有数据，很难处理数据不平衡问题；
处理非线性数据较麻烦。在不引入其他方法的情况下，只能处理线性可分的数据。

2 最大熵模型

2.1 最大熵原理

最大熵原理认为：学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。
假设离散随机变量 $X$ 的概率分布为 $P(X)$ ，则其熵为 $H(P)=-\sum\limits_{x}P(x)\log P(x)$ 熵满足下列不等式 $0\leqslant H(P)\leqslant \log |X|$ 其中 $|X|$ 为 $X$ 的取值个数，在前面的章节曾证明过，当且仅当 $X$ 的分布为均匀分布时右边的等号成立。即当 $X$ 服从均匀分布时，熵最大。

2.2 最大熵模型的定义

定义 6.3 (最大熵模型) 假设满足所有约束条件的模型集合为 $\mathcal{C}=\{P\in\mathcal{P}|E_P(f_i)=E_{\tilde{P}}(f_i),\ i=1,2,\dots,n\}$ 其中， $E_{\tilde{P}}(f)$ 表示特征函数 $f(x,y)$ 关于经验分布 $\tilde{P}(X,Y)$ 的期望 $E_{\tilde{P}}(f)=\sum\limits_{x,y}\tilde{P}(X,Y)f(x,y)$ $E_{{P}}(f)$ 表示特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 与经验分布 $\tilde{P}(X)$ 的期望 $E_{{P}}(f)=\sum\limits_{x,y}{P}(X,Y)f(x,y)$ 特征函数 $f(x,y)$ 描述输入 $x$ 与输出 $y$ 之间的一个事实，若满足则取 1，否则取 0。定义在条件概率分布 $P(Y|X)$ 熵的条件熵为 $\begin{align}H(P)= H(Y|X) &= \sum\limits_{i=1}^n P(x_i) H(Y|X=x_i) \\ &= - \sum\limits_{i=1}^n P(x_i)\sum\limits_{j=1}^n P(y_j|x_i)\log P(y_j|x_i) \\ &= - \sum\limits_{x,y} \tilde{P}(x)P(y|x)\log P(y|x) \\ \end{align}$ 则模型集合 $\mathcal{C}$ 中条件熵 $H(P)$ 最大的模型称为最大熵模型。

2.3 最大熵模型的学习

对于给定的数据集 $T = \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$ 以及特征函数 $f_i(x,y),i=1,2,\dots,n$ ，最大熵模型的学习等价于约束最优化问题： $\begin{align} &\max\limits_{P\in\mathcal{C}}H(P)= - \sum\limits_{x,y} \tilde{P}(x)P(y|x)\log P(y|x) \\ &\ \ \text{s.t.}\quad E_P(f_i)-E_{\tilde{P}}(f_i)=0,\quad i=1,2,\dots,n\\ &\qquad\quad\sum\limits_{y}P(y|x)=1\\ \end{align}$

最大熵模型的求解思路和步骤如下：

运用 Lagrange 乘子法将求解最大熵模型等价的约束最优化的问题转化为无约束最优化的问题，该问题为极小极大问题。

利用对偶问题的等价性，将无约束最优化问题转化为求解对偶形式的极大极小问题。

解得 $P_{\omega}(y|x)=\frac{1}{Z_\omega (x)}\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,y)\right)$ 其中 $Z_\omega (x)=\sum\limits_{y}\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,y)\right)$ $Z_\omega(x)$ 称为规范因子； $f_i(x,y)$ 是特征函数； $\omega_i$ 是特征的权值。
模型 $P_{\omega}(y|x)$ 就是所求的最大熵模型。对偶函数的极大化等价于最大熵模型的极大似然估计。

3 最大熵模型与 Logistic 模型的关系

当类标签只有两个的时候，最大熵模型就是logistics回归模型。证明如下：

设 $x \in \mathcal{X} \subseteq \mathbb{R}^n$ ，并且由于类标签只有两个故 $y \in \mathcal{Y} = \{0, 1\}$ ，取特征函数
$f_i(x,y)=\left\{\begin{array}{l} x_i,\quad y=1\\ 0,\quad y=0\\ \end{array}\right.\quad i =1,2,\dots n$ 由 2.3 小节可知最大熵模型为
$P_{\omega}(y|x)=\frac{\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,y)\right)}{\sum\limits_{y}\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,y)\right)}$ 于是当 $y=1$ 时有
$\begin{align} P_{\omega}(y=1|x) &=\frac{\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,1)\right)}{\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,1)\right)+\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,0)\right)} \\ &=\frac{\exp\left(\sum\limits_{i=1}^n \omega_i x_i\right)}{\exp\left(\sum\limits_{i=1}^n \omega_i x_i\right)+\exp\left(\sum\limits_{i=1}^n \omega_i \times 0\right)}\\ &=\frac{\exp\left(\omega\cdot x\right)}{\exp\left(\omega\cdot x\right)+\exp\left(0\right)}\\ &=\frac{\exp\left(\omega\cdot x\right)}{\exp\left(\omega\cdot x\right)+1}\\ \end{align}$ 同样当 $y=0$ 时有
$\begin{align} P_{\omega}(y=0|x) &=\frac{\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,0)\right)}{\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,1)\right)+\exp\left(\sum\limits_{i=1}^n \omega_i f_i(x,0)\right)} \\ &=\frac{\exp\left(\sum\limits_{i=1}^n \omega_i \times 0\right)}{\exp\left(\sum\limits_{i=1}^n \omega_i x_i\right)+\exp\left(\sum\limits_{i=1}^n \omega_i \times 0\right)}\\ &=\frac{1}{\exp\left(\omega\cdot x\right)+1}\\ \end{align}$

此时，最大熵模型为
$\begin{align} P(Y=1|x)=\frac{\exp({\omega} \cdot x)}{1+\exp({\omega}\cdot x)}\\ P(Y=0|x)=\frac{1}{1+\exp({\omega} \cdot x)}\\ \end{align}$ 即为 logistic 回归模型。Q.E.D.

4 习题

习题6.2 写出 logistic 回归模型学习的梯度下降算法。
解：
logistic 回归模型为：
$\begin{align} P(Y=1|x)=\frac{\exp(\omega \cdot x)}{1+\exp(\omega \cdot x)}\\ P(Y=0|x)=\frac{1}{1+\exp(\omega \cdot x)}\\ \end{align}$ 求得对数似然函数为
$L(\omega) = \sum\limits_{i=1}^N [y_1(\omega\cdot x_i)-\log(1+\exp(\omega\cdot x_i))]$ 将 $L(\omega)$ 求梯度，可得 $\text{grad} L(\omega) = \left[\frac{\partial L(\omega)}{\partial\omega_1},\frac{\partial L(\omega)}{\partial\omega_2},\dots,\frac{\partial L(\omega)}{\partial\omega_n},\frac{\partial L(\omega)}{\partial b}\right]$
其中 $\frac{\partial L(\omega)}{\partial\omega_i}=\sum\limits_{k=1}^N\left[x_k\times y_k-\frac{x_k\times \exp (\omega_i\times x_k)}{1+\exp (\omega_i\times x_k)}\right]$
于是 Logistic 回归模型学习的梯度下降算法：