逻辑回归与最大熵模型

2021-08-28 本文已影响0人米斯特芳

本文为《统计学习方法》第6章笔记。

概论

逻辑回归与最大熵模型都属于对数线性模型，逻辑回归求解似然函数的极大值，得到参数w，最大熵模型先转对偶问题，求得条件概率模型，也是通过极大值求解得到w。涉及到最优化算法的部分都比较晦涩，由于本人理解得也不深刻，这里就不详细展开了。

逻辑回归模型

逻辑斯蒂分布

设X为连续随机变量，服从逻辑斯蒂分布的分布函数和密度函数分别为：
$F(x)=P(X \leq x)=\frac{1}{1+e^{-(x-u)/\gamma}}\\ f(x)=F'(x)=\frac{e^{-(x-u)/\gamma}}{\gamma(1+e^{-(x-u)/\gamma})^2}$

二项逻辑斯蒂回归模型

条件概率分布为：
$P(Y=1|x)=\frac{exp(w \odot x+b)}{1+exp(w \odot x+b)}\\ P(Y=0|x)=\frac{1}{1+exp(w \odot x+b)}$
将b扩充到w向量内，1扩充到x向量内，则方程简化为
$P(Y=1|x)=\frac{exp(w \odot x)}{1+exp(w \odot x)}\\ P(Y=0|x)=\frac{1}{1+exp(w \odot x)}$
几率：事情发生与不发生的概率之比。
对数几率： $logit(p)=log\frac{p}{1-p}$
对逻辑回归而言，对数几率为 $w\odot x$

模型参数估计

设 $P(Y=1|x)=\pi(x)\\ P(Y=0|x)=1-\pi(x)$
似然函数为：
$\prod_{i=1}^N \pi(x_i)^{y_i}[1-\pi(x_i)]^{1-y_i}$
对数似然函数为：
$L(w)=\sum_{i=1}^N [y_ilog\pi(x_i)+(1-y_i)log(1-\pi(x_i))]\\ =\sum_{i=1}^N [y_i log\frac{\pi(x_i)}{1-\pi(x_i)}+log(1-\pi(x_i))]\\ =\sum_{i=1}^N [y_i (w \odot x_i)-log(1+exp(w \odot x_i))]$
对L(w)求极大值，得到w的估计值。一般使用梯度下降或拟牛顿法（代码中常见的BFGS算法）

多项逻辑斯蒂回归

$P(Y=k|x)=\frac{exp(w_k \odot x)}{1+\sum_{k=1}^{K-1}exp(w_k \odot x)},k=1,2,...K-1\\ P(Y=K|x)=\frac{1}{1+\sum_{k=1}^{K-1}exp(w_k \odot x)}$

最大熵模型

假设离散随机变量X的概率分布为P(X)，则其熵为：
$H(P)=-\sum_x P(x)logP(x)$
熵满足不等式：
$0 \leq H(p) \leq log|X|$
|X|为X的取值个数，当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出现的频次$
用特征函数f描述x和y之间的某一个事实：
$f(x,y)= \left\{\begin{array}\\ 1，x与y满足某一个事实\\ 0，其他 \end{array}\right.$
f关于联合经验分布的期望值为：
$E_{\widetilde P}(f)=\sum_{x,y}\widetilde P(x,y)f(x,y)$
f关于边缘经验分布及模型P(Y|X)的期望为：
$E_P(f)=\sum_{x,y}\widetilde P(x)P(y|x)f(x,y)$
如果模型能够获取数据中的信息，那么2个期望值应该相等
$E_{\widetilde P}(f)=E_P(f)$
定义在P(Y|X)上的条件熵为：
$H(P)=-\sum_{x,y}\widetilde P(x)P(y|x)logP(y|x)$
满足所有约束的模型集合C为：
$C \equiv {P \in \rho|E_{\widetilde P}(f_i)=E_P(f_i),i=1,2,...n}$
模型集合C中条件熵最大的模型成为最大熵模型，公式中对数为自然对数。
在约束条件下的求解，需要用到拉格朗日函数，然后转对偶问题，这里略去推导过程（可自行查询资料），对偶问题为：
$max_w min_{P \in C} L(P,w)$
先求得 $min_{P \in C} L(P,w)$ 的解为
$P_w(y|x)=\frac{1}{Z_w(x)}exp(\sum_{i=1}^n w_if_i(x,y))\\ Z_w(x)=\sum_y exp(\sum_{i=1}^n w_if_i(x,y)) ，称为规范化因子$
再求极大化问题，得到参数w的解。这需要用到最优化算法，常见的有改进的迭代尺度法（IIS）、梯度下降法、牛顿法、拟牛顿法（典型如BFGS）
这里稍微做点介绍：
IIS思路：假设 $w+\delta$ 能使得模型的似然函数增大，则更新 $w\rightarrow w+\delta$
IIS最后求解的方程为：
$\sum_ {x,y}\widetilde P(x)P_w(y|x) f_i(x,y)exp(\delta_i f^{\#}(x,y))=E_{\widetilde P}(f_i) -----------(1)\\ f^{\#}(x,y)=\sum_i f_i(x,y)，表示特征在(x,y)出现的次数$
如果 $f^{\#}(x,y)$ 是常数M（对任何x,y），则：
$\delta_i=\frac{1}{M}log\frac{E_{\widetilde P}(f_i)}{E_{P}(f_i)}$
如果不是常数，可以通过牛顿法求解：
以 $g(\delta_i)=0$ 表示以上(1)式，则：
$\delta_i^{k+1}=\delta_i^k-\frac{g(\delta_i^k)}{g'(\delta_i^k)}$
拟牛顿法思路：牛顿法需要求解黑塞矩阵H的逆，较为麻烦，拟牛顿法考虑用一个n阶矩阵逼近H（BFGS算法）或H的逆（DFP算法）
BFGS算法更新逼近矩阵：
$B_{k+1}=B_k+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}\\ y_k=g_{k+1}-g_k , \delta_k=w^{k+1}-w^k \\ 其中B_k用于逼近H$