LR算法(基础及核心概念)

前言

首先需要清楚的是，LR（Logistic Regression）虽然是回归模型，但却是经典的分类方法。 为什么分类不用SVM呢？我们对比一下SVM，在二分类问题中，如果你问SVM，它只会回答你该样本是正类还是负类；而你如果问LR，它则会回答你该样本是正类的概率是多少~

• 文章主要内容如下：
  • LR的理论基础
  • LR的参数求解过程
  • 正则化

LR的理论基础

Logistic

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

$$f(x) = \frac{e^{-(x- \mu)/ \gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}$$

其中， $\mu$就是分布对应的均值， $\gamma$是对应的形状参数。

Regression

$$P(Y=1|X) = \frac{e^{wx}}{1+e^{wx}}$$

$$P(Y=0|X) = \frac{1}{1+e^{wx}}$$

• 一个事件的几率(odds)，定义为该事件发生与不发生的概率比值，若事件发生概率为p：
  
  
  
  odds=p1−p

  $$odds = \frac{p}{1-p}$$

• 那么该事件的对数几率（log odds或者logit）如下：
  
  
  
  logit(p)=logp1−p

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

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

也就是说，输出Y=1的对数几率是由输入x的线性函数表示的模型，这就是逻辑回归模型。易知，当 w.x的值越大，P(Y=1|x) 越接近1；w.x越小(f负无穷大),P(Y=1|x) 越接近0。

其实，LR就是一个线性分类的模型。与线性回归不同的是：LR将线性方程输出的很大范围的数压缩到了[0,1]区间上；更优雅地说：LR就是一个被logistic方程归一化后的线性回归。

LR的参数求解过程

极大似然估计

接下来便是参数估计过程，统计学中，常根据最大化似然函数的值来估计总体参数。其实，在机器学习领域，我们听到的更多是损失函数的概念，常通过构建损失函数，然后最小化损失函数求得目标参数。在这里，最大化对数似然函数与最小化对数似然损失函数其实是等价的，下面我们可以看到。

• 假设我们有n个独立的训练样本$\{(x_1,y_1),(x_2,y_2),(x_3,y_3),...,(x_n,y_n)\},y={0,1}$,那么每一个观察到的样本$(x_i,y_i)$出现的概率是：
  
  
  
  P(yi,xi)=P(yi=1|xi)yi(1−P(yi=1|xi))1−yi

  $$P(y_i,x_i) = P(y_i=1 | x_i)^{y_i}(1-P(y_i=1 | x_i))^{1-y_i}$$
  显然，$y_i$为1时，保留前半部分；$y_i$为0时，保留后半部分。

  
  

• 构建似然函数：
  
  
  
  L(θ)=∏P(yi=1|xi)yi(1−P(yi=1|xi))1−yi

  $$L(\theta) = \prod P(y_i=1|x_i)^{y_i}(1-P(y_i=1|x_i))^{1-y_i}$$

• OK,对似然函数取对数，得到对数似然函数：
  $LL(\theta) = log(L(\theta)) = log(\prod P(y_i=1|x_i)^{y_i}(1-P(y_i=1|x_i))^{1-y_i})$
  
  

  $= \sum_{i=1}^{n}y_i log P(y_i=1|x_i) + (1-y_i)log(1-P(y_i=1|x_i))$

  $= \sum_{i=1}^{n}y_i log \frac{P(y_i=1|x_i)}{1-P(y_i=1|x_i)} + \sum_{i=1}^{n}log(1-P(y_i=1|x_i))$

  $= \sum_{i=1}^{n}y_i(w.x) + \sum_{i=1}^{n}logP(y_i=0|x_i)$

  $= \sum_{i=1}^{n}y_i(w.x) - \sum_{i=1}^{n}log(1+e^{w.x})$

  $= \sum_{i=1}^{n}y_i(\theta^T.x_i) - \sum_{i=1}^{n}log(1+e^{\theta^T.x_i})$

• 用 $LL(\theta)$ 对 $\theta$ 求偏导，得：
  $\frac{\partial LL(\theta)}{\partial \theta} = \sum_{i=1}^{n}y_ix_i - \sum_{i=1}^{n} \frac{e^{\theta^T.x_i}}{1+e^{\theta^T.x_i}}.x_i$
  
  

  $= \sum_{i=1}^{n}(y_i - P(y_i=1|x_i))x_i$
  该式是无法解析求解，故下面会用到一个常见的优化算法–梯度下降(Gradient Descent).
  
  

梯度下降

Gradient Descent 又叫 Steepest Descent，是利用函数一阶的梯度信息找到函数局部最优解的一种方法，机器学习中最简单最常用的一种优化方法。

它的思想很简单：要找最小值，我只需要每一步都往下走（也就是每一步都可以让代价函数更小一点），然后不断地迭代，最终达到最小值的地方。

这里，附上一个网站,可以直观地看出各种优化算法地迭代路径，附上几张效果图如下：

Long Valley:

Saddle Point：

Beale’s Function:

$$\theta^{new} = \theta^{old}-\alpha\frac{\partial LL(\theta)}{\partial \theta} = \theta^{old} - \alpha\sum_{i=1}^{n}(y_i - P(y_i=1|x_i))x_i$$

• 其中，参数α叫学习率，这个参数设置很关键。如果设置的太大。缺点：那么很容易就在最优值附加徘徊;优点：能很快的从远离最优值的地方回到最优值附近。如果设置的太小。缺点：那么就跟蜗牛似的，迭代速度太慢了。所以通常的技巧是开始迭代时，学习率大，慢慢的接近最优值的时候，学习率变小就可以了。
• 第二点是，梯度下降算法在每次迭代更新参数时都需要遍历整个数据集，计算复杂度太高。改进的方法是一次仅随机采用一个样本数据的回归误差来更新回归系数。这个方法叫随机梯度下降算法。

综合以上两点，给出改进的随机梯度下降算法的伪代码：

------------------------------------------------- 1.初始化回归系数 2.重复下面步骤直到收敛{ 对随机遍历的数据集中的每个样本 随着迭代的逐渐进行，减小$\alpha$的值 计算该样本的梯度 使用$\alpha$ x 梯度来更新回归系数 } 3.返回回归系数值 ------------------------------------------------- 

正则化

当模型参数很多，而我们可用的数据非常少时，极易出现过拟合的问题。在机器学习领域，通常可以对损失函数引入正则项，其目的是使得参数空间受到一定的限制。

正则化是奥卡姆剃刀(Occam’s Razor)原理的一个体现：在所有可能选择(能很好地解释已知数据)的模型中，更倾向于选择尽量简单的模型。

正则项(范数)的概念已经在博文中说过一次了，这里不再赘述。只八股一下两个正则项的特点吧：

• L1范数：也称叫“稀疏规则算子”（Lasso Regularization）。为什么能稀疏呢？关键原因在于它能实现特征的自动选择。一般来说，训练集中的某些特征和输出 $y_i$ 之间并没有多大关系。在训练时引入这些特征，当然能获得更小的训练误差，但其泛化能力比较差，即造成过拟合！L1范数的引入就是为了实现特征自动选择，它会将没有信息的特征对应的权重置为0。
• L2范数：在回归里面中又称岭回归”（Ridge Regression），也有的叫法为“权值衰减”(Weight Decay)。同样是为了解决过拟合问题，但与 L1 范数不同的是L2是使得特征对应的权重尽量的小，接近于0(但不会等于0)。而越小的参数说明模型越简单，越简单的模型则越不容易产生过拟合现象。为什么呢?这里给出一个说法:参数越小，表示模型不会过分地学习训练集的某个特征，也即更不容易造成过拟合。

两者的区别可以从图中看出来，L1正则化（左图）更容易与突出的角相切，可以想象在高纬特征空间中，会有许多向外突出的角；L1倾向于使某些特征对应的参数变为0，因此能产生稀疏解。而 L2 使 w 接近0。