LogisticRegression & Maxent（面试准备

2020-02-28 本文已影响0人单调不减

1、手推LogisticRegression（损失函数）

二项逻辑斯蒂回归模型是如下条件概率分布：

$P(Y=1|x) = \frac{ \exp(wx)}{ 1+\exp(wx)}$

$P(Y=0|x) = \frac{ 1}{1+\exp(wx)}$

这里的 $w$ 包含偏置项 $b$ ，即为 $w_0$ ，其对应的 $x_0=1$ 。

由此可得：

$\log\frac{P(Y=1|x)}{P(Y=0|x)}=w\cdot x$

即：

$\log\frac{P(Y=1|x)}{1-P(Y=1|x)}=w\cdot x$

也就是说， $Y=1$ 的对数几率由输入 $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)}$

对数似然函数为：

$\begin{aligned} L(w)&=\sum_{i=1}^N [y_i\log\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\cdot x_i)-\log(1+\exp(w\cdot x_i))] \end{aligned}$

$L(w)$ 直接对 $w$ 求导是无法得到解析解的，因此采用梯度下降法或者拟牛顿法等方法优化 $L(w)$ 。

这里我们可以求解 $L(w)$ 对各 $w_i$ 的梯度，为了推导简便，我们写出 sigmoid 函数：

$\sigma(x)= \frac{ 1}{1+\exp(-x)}$

从而：

$\pi(x)=\sigma(w\cdot x)$

$\sigma(x)$ 有一个很好的性质：

$\sigma^{\prime}(x)=\sigma(x)(1-\sigma(x))$

从而 $L(w)$ 可以写作：

$L(w) = \sum_{i=1}^N [y_i\log\sigma(w\cdot x_i)+(1-y_i)\log(1-\sigma(w\cdot x_i))]$

接下来求 $L(w)$ 对各 $w_i$ 的梯度：

$\begin{aligned} \frac{\partial L(w)}{\partial w_i}&=\left(y \frac{1}{\sigma\left(w\cdot x\right)}-(1-y) \frac{1}{1-\sigma\left(w\cdot x\right)}\right) \frac{d}{d w_i } \sigma\left(w\cdot x\right) \\ &=\left(y \frac{1}{\sigma\left(w\cdot x\right)}-(1-y) \frac{1}{1-\sigma\left(w\cdot x\right)}\right) \sigma\left(w\cdot x\right)\left(1-\sigma\left(w\cdot x\right)\right) \frac{d}{d w_{i}} (w\cdot x) \\ &=\left(y\left(1-\sigma\left(w\cdot x\right)\right)-(1-y) \sigma\left(w\cdot x\right)\right) x_{i}\\ &=\left(y-\sigma(w\cdot x) \right) x_{i} \\ \end{aligned}$

2、逻辑斯蒂回归在多分类时的情形

对于 $K$ 分类：

$\begin{aligned} &P(Y=k|x) = \frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^K\exp(w_k\cdot x)},\ \ \ k=1,2,\dots,K-1 \\ &P(Y=K|x) = \frac{1}{1+\sum_{k=1}^K\exp(w_k\cdot x)} \end{aligned}$

3、逻辑斯蒂回归为什么采用 sigmoid 函数？

sigmoid 函数可以很方便的将 $w\cdot x$ 的结果映射到 $(0,1)$ 区间上，从而代表分类概率的大小。
sigmoid 函数在 0 附近斜率较大，而在远离 0 处的斜率较小，这体现了模型对不同样本点的敏感性的大小，即对于远离分类边界的点敏感性较小，对于分类边界附近的点敏感性较大。这有利于模型重点关注较难分类的样本，从而取得较好的分类效果。
sigmoid 函数的选择也可以从最大熵模型推导得出。

4、最大熵模型与逻辑斯蒂回归模型的关系

逻辑斯蒂回归模型可以视作最大熵模型的一个特例。

假设分类模型是一个条件概率分布 $P(Y|X)$ ，给定训练数据集，可以确定联合分布 $P(X,Y)$ 的经验分布 $\tilde{P}(X,Y)$ 和边缘分布 $P(X)$ 的经验分布 $\tilde{P}(X)$ 。

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

$\tilde{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$ 之间的某个事实，定义为：

$\begin{equation} f(x,y)=\left\{ \begin{array}{rcl} 1 & & {x,y满足某一事实}\\ 0 & & {否则} \end{array} \right. \end{equation}$

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

$E_{\tilde{P}}(f)=\sum_{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_{x,y}\tilde{P}(x)P(y|x)f(x,y)$

若模型能够获取训练数据中的信息，则可假设这两个期望相等（注意 $P(y|x)$ 是我们的模型学得的结果）：

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

将上式作为模型的约束条件，设所有满足约束的模型集合为：

$C\equiv \{P\in \it{P} |E_P(f_i)=E_{\tilde{P}}(f_i),\quad i=1,2,\dots,n\}$

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

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

则最大熵模型的学习变为求解约束最优化问题：

$\begin{aligned} & \max_{P\in C} && H(P) = -\sum_{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,\dots,n \\ & && \sum_{y}P(y|x)=1 \\ \end{aligned}$

改写为等价的最小化问题：

$\begin{aligned} & \min_{P\in C} && -H(P) = \sum_{x,y} \tilde{P}(x)P(y|x)\log P(y|x) \\ & s.t. && E_P(f_i) - E_{\tilde{p}}(f_i)=0,\ \ i=1,2,\dots,n \\ & && \sum_{y}P(y|x)=1 \\ \end{aligned}$

引入拉格朗日乘子 $w_0,w_1,\dots,w_n$ ，构造拉格朗日函数：

$\begin{aligned} L(P,w)& =-H(P)+w_0(1- \sum_{y}P(y|x))+\sum_{i=1}^n w_i(E_{\tilde{P}}(f_i)-E_P(f_i)) \\ & =\sum_{x,y} \tilde{P}(x)P(y|x)\log P(y|x)+w_0(1-\sum_{y}P(y|x))+\sum_{i=1}^n w_i(E_{\tilde{P}}(f_i)-E_P(f_i)) \\ \end{aligned}$

原问题等价于：

$min_{P\in C} \max_{w}L(P,w)$

对偶问题为：

$\max_{w}min_{P\in C} L(P,w)$

求 $L(P,w)$ 对 $P(y|x)$ 对偏导数：

$\frac{\partial L(P,w)}{\partial P(y|x)}=\sum_{x,y}\tilde{P}(x)(\log P(y|x)+1-w_0-\sum_{i=1}^n w_i f_i(x,y))=0$

解得：

$P(y|x) = \frac{ \exp(\sum_{i=1}^n w_i f_i(x,y))}{\exp(1-w_0)}$

由 $\sum_{y}P(y|x)=1$ 得：

$P(y|x) = \frac{ \exp( \sum_{i=1}^n w_i f_i(x,y))}{ \sum_y \exp(\sum_{i=1}^n w_i f_i(x,y))}$

之后，求解对偶问题外层的极大化问题，即把上式带入 $L(P,w)$ 后再求解最优的 $w^*$ 使得 $L(w)$ 最大。

不难看出，这里的 $P(y|x)$ 的形式和 Logistic Regression 很像。

实际上，若取特征函数：

$f(x_i, y_i)=\left\{\begin{array}{cl} x_i & y_i=1 \\ 0 & y_i=0 \\ \end{array}\right.$

则：

$P(y=1|x) = \frac{\exp(\sum_{i=1}^n w_i f_i(x,y))}{ \sum_y \exp(\sum_{i=1}^n w_i f_i(x,y))} = \frac{ \exp(wx) }{ 1+\exp(wx) }$

这就得到了逻辑斯蒂回归。

5、LR 与 SVM 的区别与联系

相同点：

LR 和 SVM 都是分类算法
如果不考虑核函数，LR 和 SVM 都是线性分类算法，即分类决策面都是线性的
LR 和 SVM 都是有监督学习算法
LR 和 SVM 都是判别模型

不同点：

损失函数的不同。LR 采用的是对数损失函数，SVM 采用的是合页损失函数。而前者比后者发散更快，因此相比 SVM，LR 对异常值更加敏感。

分类原理的不同。LR 基于概率模型，通过极大似然估计的方法估计出参数的值，而 SVM 基于几何间隔最大化原理。所以 SVM 会找到唯一的最优解，而 LR 没有这个特性。
对于线性不可分的复杂情形，SVM 可以利用核函数将线性不可分的低维数据映射为线性可分的高维数据；而 LR 很少用到核函数（LR 是可以使用核函数的，接下来会进行说明），因为 LR 模型中每个样本点都必须参与核函数的计算，计算复杂度很高。所以在具体应用中，LR 很少运用核函数机制，遇到线性不可分的情形多使用 SVM 解决。

这里简要说下 Kernel Logistic Regression（KLR）：

为了说明 LR 可以使用核函数，先证明如下定理：

对于任意带 L2 正则化的线性模型都可以使用 Kernel Trick。

具体说来，对如下模型：

$\min_{w} \frac{ \lambda}{ N}w^T w+\frac{1}{N}\sum_{n=1}^N loss(y_n,w^T x_n)$

最优解 $w^*$ 一定可以表示成 $w^*=\sum_{n=1}^N\beta_n x_n$ ，从而使得 ${w^*}^T x_n$ 中出现内积的形式，可以使用 Kernel Trick 简化计算。

证明：设 $w^*=w_{||}+w_{\perp}$ ，其中 $w_{||}\in span(x_n)$ ，且 $w_{\perp} \perp span(x_n)$ 。若 $w_{\perp}\neq 0$ ，则：

$loss(y_n,{w^*}^T x_n)=loss(y_n,(w_{||}+w_{\perp})^T x_n)=loss(y_n,w_{||}^T x_n)$

且：

${w^*}^T w^*=w_{||}^T w_{||}+w_{\perp}^T w_{\perp} +2w_{||}^T w_{\perp} = w_{||}^T w_{||}+w_{\perp}^T w_{\perp} > w_{||}^T w_{||}$

则 $w_{||}$ 是比 $w^*$ 更好的解，矛盾。因此 $w_{\perp}=0$ ，即 $w^*\in span(x_n)$ ，即 $w^*$ 可由 $x_n$ 的线性组合表示。证毕。

应用此定理可知，带 L2 正则项的 LR 模型可以应用 Kernel Trick，得到的模型 KLR 具有处理非线性可分数据的能力，且一定程度上可以防止过拟合（因为包含正则项）。

SVM 输出分类结果 0 或 1，而 LR 输出介于 0 和 1 之间的表示分类概率的数值，这在某些应用场景下是非常有用的，比如医疗诊断这样后果较为严重的场合，或者我们对数据质量并不是十分有信心的时候，LR 可以告诉我们在多大程度上可以相信模型产生的分类结果。
SVM 的结果只受边界附近少数几个样本点的影响，LR 的结果则受所有样本点的影响。两者没有绝对的优劣之分，具体使用结合应用场景。

Reference

https://blog.csdn.net/cuiy0818/article/details/81288701

https://medium.com/@george.drakos62/support-vector-machine-vs-logistic-regression-94cc2975433f