机器学习(一):回归算法

持续更新中。。。


什么是回归算法

回归算法是一种比较常用的机器学习算法,用来建立”解释”变量和观测值之间的关系;
从机器学习的角度来讲,就是通过学习,构建一个算法模型(函数),来做属性与标签之间的映射关系。

回归算法中算法(函数)的最终结果是一个 连续 的数据值,输入值(属性值)是一个d维度的属性/数值向量。

回归涉及的算法模型:线性回归(Linear)、岭回归(Ridge)、LASSO回归、Elastic Net弹性网络算法
正则化:L1-norm、L2-norm
损失函数/目标函数:
θ求解方式:最小二乘法(直接计算,目标函数是平方和损失函数)、梯度下降(BGD\SGD\MBGD)

广义线性模型对样本要求不必要服从正态分布、只需要服从指数分布簇(二项分布、泊松分布、伯努利分布、指数分布等)即可;广义线性模型的自变量可以是连续的也可以是离散的。


BGD、SGD、MBGD介绍与区别

  • BGD:批量梯度下降法 Batch Gradient Descent
    更新每一参数时都使用所有的样本来进行更新。
    优点:全局最优解;易于并行实现;
    缺点:当样本数目很多时,训练过程会很慢。

  • SGD:随机梯度下降法 Stochastic Gradient Descent
    随机梯度下降是通过每个样本来迭代更新一次,如果样本量很大的情况(例如几十万),那么可能只用其中几万条或者几千条的样本,就已经将theta迭代到最优解了,对比上面的批量梯度下降,迭代一次需要用到十几万训练样本,一次迭代不可能最优,如果迭代10次的话就需要遍历训练样本10次。但是,SGD伴随的一个问题是噪音较BGD要多,使得SGD并不是每次迭代都向着整体最优化方向。
    优点:训练速度快;
    缺点:准确度下降,并不是全局最优;不易于并行实现。

  • MBGD:小批量梯度下降法 Mini-batch Gradient Descent。
    如果即需要保证算法的训练速度,又需要保证最终参数训练的准确率,可以采取折衷方案MBGD。MBGD在每次更新参数时使用b个样本(b一般为10)。

  • BGD和SGD比较
    1)SGD速度比BGD快(迭代次数少)
    2)SGD在某些情况下(全局存在多个相对最优解/J(θ)不是一个二次)有可能跳出某些小的局部最优解,所以不会比BGD坏
    3)BGD一定能够得到一个局部最优解(在线性回归模型中一定是得到一个全局最优解),SGD由于随机性的存在可能导致最终结果比BGD的差
    注意:两者优先选择SGD

损失函数:$J_{train}(\theta)=1/(2m)\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})^{2}$


回归要调的参数有哪些

对于各种算法模型(线性回归)来讲,我们需要获取θ、λ、p的值;
θ的求解其实就是算法模型的求解,一般不需要开发人员参与(算法已经实现),
主要需要求解的是λ和p的值,这个过程就叫做调参(超参)


局部加权回归

普通线性回归损失函数:
局部加权回归损失函数:

$W^i$是权重,它根据要预测的点与数据集中的点的距离来为数据集中的点赋权值。
当某点离要预测的点越远,其权重越小,否则越大。常用值选择公式为:

该函数称为指数衰减函数,其中k为波长参数,它控制了权值随距离下降的速率
注意:使用该方式主要应用到样本之间的相似性考虑,主要内容在SVM中再考虑(核函数)


Softmax回归

Softmax回归是logistic回归的一般化,适用于K分类的问题,第k类的参数为向量$θ_k$ ,组成的二维矩阵为$θ_k*n$ 。
Softmax函数的本质就是将一个K维的任意实数向量压缩(映射)成另一个K维的实数向量,其中向量中的每个元素取值都介于(0,1)之间。

softmax回归概率函数为:


什么是正则化?L1正则与L2正则介绍

为了防止过拟合,在成本函数中加入一个正则项,惩罚模型的复杂度

Logistic 回归中的正则化
对于 Logistic 回归,加入 L2 正则化(也称“L2 范数”)的成本函数:
$$J(w,b) = \frac{1}{m}\sum_{i=1}^mL(\hat{y}^{(i)},y^{(i)})+\frac{\lambda}{2m}{||w||}^2_2$$

  • L1 正则化(LASSO回归 Least Absolute Shrinkage and Selection Operator)
    $$\frac{\lambda}{2m}{||w||}_1 = \frac{\lambda}{2m}\sum_{j=1}^{n_x}{|w_j|}$$
  • L2 正则化(Ridge回归 岭回归)
    $$\frac{\lambda}{2m}{||w||}^2_2 = \frac{\lambda}{2m}\sum_{j=1}^{n_x}w^2_j = \frac{\lambda}{2m}w^Tw$$

其中,λ 为正则化因子,是超参数。
注意,lambda在 Python 中属于保留字,所以在编程的时候,用lambd代替这里的正则化因子。

L1范数可以使权值稀疏,方便特征提取。
L2范数可以防止过拟合,提升模型的泛化能力。

L1正则与L2正则

L2-norm(岭回归)中,由于对于各个维度的参数缩放是在一个圆内缩放的,不可能导致有维度参数变为0的情况,那么也就不会产生稀疏解;实际应用中,数据的维度中是存在噪音和冗余的,L1(LASSO回归)稀疏的解可以找到有用的维度并且减少冗余,因此LASSO模型也具有较高的求解速度

同时使用L1正则和L2正则的线性回归模型就称为Elasitc Net算法(弹性网络算法)
弹性网络


正则化为什么可以防止过拟合

正则化是在成本函数中加入一个正则化项,惩罚模型的复杂度。是针对过拟合而提出的。

  • 直观解释
    正则化因子设置的足够大的情况下,为了使成本函数最小化,相应的参数就会被调小,甚至接近于0值,直观上相当于消除了很多特征值的影响。而且一般情况下参数越小(或者特征值越少),函数越光滑,模型越简单,奥卡姆剃刀原理。

  • 其他解释
    在权值 w变小之下,输入样本 X 随机的变化不会对模型造成过大的影响,模型受局部噪音的影响的可能性变小。这就是正则化能够降低模型方差的原因。

  • 神经网络防止过拟合还有一种数学解释,即每层权重变小,在 z 较小(接近于 0)的区域里,tanh(z)函数就近似线性,所以每层的函数就近似线性函数,所以防止过拟合。


L1和L2正则先验分别服从什么分布

面试中遇到的,L1和L2正则先验分别服从什么分布,L1是拉普拉斯分布,L2是高斯分布

先验就是优化的起跑线, 有先验的好处就是可以在较小的数据集中有良好的泛化性能,当然这是在先验分布是接近真实分布的情况下得到的了,从信息论的角度看,向系统加入了正确先验这个信息,肯定会提高系统的性能。
对参数引入高斯正态先验分布相当于L2正则化, 这个大家都熟悉:


对参数引入拉普拉斯先验等价于 L1正则化, 如下图:


从上面两图可以看出, L2先验趋向零周围, L1先验趋向零本身。


梯度的定义


什么是梯度下降?为什么要用梯度下降

推荐一篇文章:吴恩达机器学习线性回归总结

梯度下降法(gradient descent)是解决无约束优化问题的最简单和最古老的方法之一,常用在机器学习中 逼近最小偏差搜索方向为梯度的负方向,越接近目标值,步长越小,前进越慢。



X1,X2..Xn 描述的是feature里面的分量,比如x1=房间的面积,x2=房间的朝向等等。θ是我们要调的参数,通过调整θ可以控制feature中每个分量的影响力。

损失函数J(θ)是用来判断θ取值是否比较好。换言之,我们把对x(i)的估计值与真实值y(i)差的平方和作为损失函数,前面乘上的1/2是为了在求导的时候,这个系数就不见了。

如何调整θ以使得J(θ)取得最小值有很多方法,其中有最小二乘法(min square),另外一种就是梯度下降法。

梯度下降法的算法流程
1)首先对θ赋值,这个值可以是随机的,也可以让θ是一个全零的向量。
2)改变θ的值,使得J(θ)按梯度下降的方向进行减少。

为了描述的更清楚,给出下面的图:

这是一个表示参数θ与误差函数J(θ)的关系图,红色的部分是表示J(θ)有着比较高的取值,我们需要的是,能够让J(θ)的值尽量的低,也就是达到深蓝色的部分。θ0,θ1表示θ向量的两个维度。
在上面提到梯度下降法的第一步是给θ给一个初值,假设随机给的初值是在图上的十字点。
然后我们将θ按照梯度下降的方向进行调整,就会使得J(θ)往更低的方向进行变化,如下图所示,算法的结束将是在θ下降到无法继续下降为止。

当然,可能梯度下降的最终点并非是全局最小点,即也可能是一个局部最小点,如下图所示:

上面这张图就是描述的一个局部最小点,这是我们重新选择了一个初始点得到的,看来我们这个算法将会在很大的程度上被初始点的选择影响而陷入局部最小点。
下面我将用一个例子描述一下梯度减少的过程,对于我们的函数J(θ)求偏导J:

下面是更新的过程,也就是θi会向着梯度最小的方向进行减少。θi表示更新之前的值,-后面的部分表示按梯度方向减少的量,α表示步长,也就是每次按照梯度减少的方向变化多少。

一个很重要的地方值得注意的是,梯度是有方向的,对于一个向量θ,每一维分量θi都可以求出一个梯度的方向,我们就可以找到一个整体的方向,在变化的时候,我们就朝着下降最多的方向进行变化就可以达到一个最小点,不管它是局部的还是全局的。


梯度下降法容易收敛到局部最优,为什么应用广泛

深度神经网络“容易收敛到局部最优”,很可能是一种想象,实际情况是,你可能从来没有找到过“局部最优”,更别说全局最优了。

大部分情况你达到的是 鞍点,鞍点详解见我的深度学习笔记


梯度下降法找到的一定是下降最快的方向么

梯度下降法并不是下降最快的方向,它只是目标函数在当前点的切平面下降最快的方向。一般认为牛顿方向(考虑海森距离)才是下降最快的方向。


牛顿法和梯度下降法的区别

效率对比:
(a)从收敛速度上看 ,牛顿法是二阶收敛,梯度下降是一阶收敛,前者牛顿法收敛速度更快。但牛顿法仍然是局部算法,只是在局部上看的更细致,梯度法仅考虑方向,牛顿法不但考虑了方向还兼顾了步子的大小,其对步长的估计使用的是二阶逼近。
(b)根据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径。
注:红色的牛顿法的迭代路径,绿色的是梯度下降法的迭代路径

牛顿法的优缺点总结:
优点:二阶收敛,收敛速度快;
缺点:函数必须具有连续的一阶二阶偏导数,海森矩阵必须正定。其次计算非常复杂。


共轭梯度

共轭:两个概率分布如果具有相同的形式,我们就说它们是共轭的

共轭梯度法是介于梯度下降法(最速下降法)与牛顿法之间的一个方法,它仅需利用一阶导数信息,但克服了梯度下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hessian矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性最优化最有效的算法之一。在各种优化算法中,共轭梯度法是非常重要的一种。其优点是所需存储量小,具有逐步收敛性,稳定性高,而且不需要任何外来参数。

下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图:

注:绿色为梯度下降法,红色代表共轭梯度法


简单介绍下LR

1)吴恩达机器学习逻辑回归总结
2)Logistic Regression 的前世今生
3)机器学习算法与Python实践之七-逻辑回归


把LR从头到脚都给讲一遍。建模,现场数学推导,每种解法的原理,正则化,LR和maxent模型啥关系,lr为啥比线性回归好。有不少会背答案的人,问逻辑细节就糊涂了。原理都会? 那就问工程,并行化怎么做,有几种并行化方式,读过哪些开源的实现。还会,那就准备收了吧,顺便逼问LR模型发展历史。


LR与线性回归的区别与联系

整理中。。。

LR 工业上一般指Logistic Regression(逻辑回归)而不是Linear Regression(线性回归)。LR在线性回归的实数范围输出值上施加 sigmoid 函数将值收敛到 0~1 范围,其目标函数也因此从差平方和函数变为对数损失函数,以提供最优化所需导数(sigmoid函数是softmax函数的二元特例, 其导数均为函数值的f*(1-f)形式)。

请注意, LR 往往是解决二元 0/1 分类问题的, 只是它和线性回归耦合太紧, 不自觉也冠了个回归的名字。若要求多元分类,就要把sigmoid换成大名鼎鼎的softmax了。

  • 个人感觉逻辑回归和线性回归首先都是广义的线性回归,
  • 其次经典线性模型的优化目标函数是最小二乘,而逻辑回归则是似然函数,
  • 另外线性回归在整个实数域范围内进行预测,敏感度一致,而分类范围,需要在[0,1]。逻辑回归就是一种减小预测范围,将预测值限定为[0,1]间的一种回归模型,因而对于这类问题来说,逻辑回归的鲁棒性比线性回归的要好。

逻辑回归的模型本质上是一个线性回归模型,逻辑回归都是以线性回归为理论支持的。但线性回归模型无法做到sigmoid的非线性形式,sigmoid可以轻松处理0/1分类问题。


LR模型为什么要使用sigmoid函数

假设W已知,现有函数 P(y|x) = f(wx),求分布f,使得在正样本里 P(y=1|w,x)尽可能大,在负样本里尽可能小。根据最大熵原则,我们知道所有可能的分布模型集合中,熵最大的模型是最好的模型。即对未知分布最合理的推断就是符合已有前提下最不确定或最随机的推断。又已知LR符合伯努利分布,将伯努利分布转换为指数分布的过程中,可以得到sigmod函数,这就是LR的理论基础。


逻辑回归相关问题

(3)L1-norm和L2-norm
  其实稀疏的根本还是在于L0-norm也就是直接统计参数不为0的个数作为规则项,但实际上却不好执行于是引入了L1-norm;而L1norm本质上是假设参数先验是服从Laplace分布的,而L2-norm是假设参数先验为Gaussian分布,我们在网上看到的通常用图像来解答这个问题的原理就在这。
  但是L1-norm的求解比较困难,可以用坐标轴下降法或是最小角回归法求解。

(4)LR和SVM对比
  首先,LR和SVM最大的区别在于损失函数的选择,LR的损失函数为Log损失(或者说是逻辑损失都可以)、而SVM的损失函数为hinge loss。

  其次,两者都是线性模型。
  最后,SVM只考虑支持向量(也就是和分类相关的少数点)

(5)LR和随机森林区别
  随机森林等树算法都是非线性的,而LR是线性的。LR更侧重全局优化,而树模型主要是局部的优化。

(6)常用的优化方法
  逻辑回归本身是可以用公式求解的,但是因为需要求逆的复杂度太高,所以才引入了梯度下降算法。
  一阶方法:梯度下降、随机梯度下降、mini 随机梯度下降降法。随机梯度下降不但速度上比原始梯度下降要快,局部最优化问题时可以一定程度上抑制局部最优解的发生。

  二阶方法:牛顿法、拟牛顿法:
  这里详细说一下牛顿法的基本原理和牛顿法的应用方式。牛顿法其实就是通过切线与x轴的交点不断更新切线的位置,直到达到曲线与x轴的交点得到方程解。在实际应用中我们因为常常要求解凸优化问题,也就是要求解函数一阶导数为0的位置,而牛顿法恰好可以给这种问题提供解决方法。实际应用中牛顿法首先选择一个点作为起始点,并进行一次二阶泰勒展开得到导数为0的点进行一个更新,直到达到要求,这时牛顿法也就成了二阶求解问题,比一阶方法更快。我们常常看到的x通常为一个多维向量,这也就引出了Hessian矩阵的概念(就是x的二阶导数矩阵)。
缺点:牛顿法是定长迭代,没有步长因子,所以不能保证函数值稳定的下降,严重时甚至会失败。还有就是牛顿法要求函数一定是二阶可导的。而且计算Hessian矩阵的逆复杂度很大。

拟牛顿法:不用二阶偏导而是构造出Hessian矩阵的近似正定对称矩阵的方法称为拟牛顿法。拟牛顿法的思路就是用一个特别的表达形式来模拟Hessian矩阵或者是他的逆使得表达式满足拟牛顿条件。主要有DFP法(逼近Hession的逆)、BFGS(直接逼近Hession矩阵)、 L-BFGS(可以减少BFGS所需的存储空间)。


逻辑回归为什么要对特征进行离散化

在工业界,很少直接将连续值作为逻辑回归模型的特征输入,而是将连续特征离散化为一系列0、1特征交给逻辑回归模型,这样做的优势有以下几点:

  1. 离散特征的增加和减少都很容易,易于模型的快速迭代;
  2. 稀疏向量内积乘法运算速度快,计算结果方便存储,容易扩展;
  3. 离散化后的特征对异常数据有很强的鲁棒性:比如一个特征是年龄>30是1,否则0。如果特征没有离散化,一个异常数据“年龄300岁”会给模型造成很大的干扰;
  4. 逻辑回归属于广义线性模型,表达能力受限;单变量离散化为N个后,每个变量有单独的权重,相当于为模型引入了非线性,能够提升模型表达能力,加大拟合;
  5. 离散化后可以进行特征交叉,由M+N个变量变为M*N个变量,进一步引入非线性,提升表达能力;
  6. 特征离散化后,模型会更稳定,比如如果对用户年龄离散化,20-30作为一个区间,不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反,所以怎么划分区间是门学问;
  7. 特征离散化以后,起到了简化了逻辑回归模型的作用,降低了模型过拟合的风险。
    李沐曾经说过:模型是使用离散特征还是连续特征,其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型,也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说,前者容易,而且可以n个人一起并行做,有成功经验;后者目前看很赞,能走多远还须拭目以待。

逻辑回归并行化怎么做,有几种并行化方式,读过哪些开源的实现

http://www.csdn.net/article/2014-02-13/2818400-2014-02-13