理解机器学习中常用优化方法

理解机器学习中常用优化方法

最优化方法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。

大部分的机器学习算法的本质就是建立优化模型,通过最优化方法对目标函数(或损失函数)进行优化,从而训练出最好的模型。

梯度下降法

梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为是”最速下降法“。注意这里的最快下降不是全局来说,只是针对当前位置。

最速下降法和梯度下降还是有区别的,梯度下降法可以看作是欧式范数(2)下的最速下降法。此外最速下降的步长t是直线搜索的当前的最优步长,梯度下降一般提前指定,t为固定步长。

搜索方向为什么选负梯度方向

回忆:向量的方向可以用方向角向量进行表示, 阅读了解 矩阵求导常用公式 Hessian矩阵 Jacobian矩阵 | Oath2yangmen’s Blog

方向导数角度

方向导数代表多元函数在各个方向上的变化率,梯度是方向导数最大的方向。所以负梯度方向是当前位置下降最快方向。

阅读参考 为什么梯度下降法每次找到的都是下降最快的点-忆臻的回答

一阶泰勒展开+柯西-施瓦茨不等式角度

梯度下降推导

最速下降法的搜索路径

搜索路径一般呈直角锯齿,新点处的梯度与搜索方向垂直。

梯度下降搜索路径

从任意迭代点A1出发,沿其负梯度方向T1一维搜索到极小点A2,则A2点应为向量与目标函数等值线的切点。下次迭代从点A2出发,沿其负梯度方向一维搜索,根据梯度方向的性质可知应是目标函数等值线在A2点的法线T2,因而T1与T2必为正交向量。这就表明,梯度法迭代过程中前后两次迭代向量为正交。故梯度法迭代过程是呈直角锯齿形路线曲折走向目标函数的极小点。

当目标函数的等值线接近一个圆(球)时,最速下降法下降较快,当等值线是个扁长的椭圆(球)时,最速下降法刚开始几步比较快,后来出现锯齿变的缓慢。圆上的任意点的切线的法线都指向圆心最小值点,而椭圆不一定。

解决直角锯齿搜索的方法

选择合适的初始点

锯齿现象和初始点有关,举个例子:当该点的梯度方向和等值线的切线的法线指向全局最小点时,一步到位。如何选择初始点是个很难的问题。

不精确的一维搜索

比如梯度下降法采用定长的t,而未采用最速下降里直线搜索使得下降最大的t。

三种梯度下降优化框架

批量梯度下降(Batch gradient descent)

优点是每次更新都会朝着正确的方向进行,最后能够保证收敛于极值点(凸函数收敛于全局极值点,非凸函数可能会收敛于局部极值点),但是其缺点在于每次学习时间过长,并且如果训练集很大以至于需要消耗大量的内存,并且全量梯度下降不能进行在线模型参数更新

随机梯度下降(Stochastic gradient descent)

每次的学习是非常快速的,并且可以进行在线更新。随机梯度下降最大的缺点在于每次更新可能并不会按照正确的方向进行,因此可以带来优化波动(扰动)。

不过从另一个方面来看,随机梯度下降所带来的波动有个好处就是,对于类似盆地区域(即很多局部极小值点)那么这个波动的特点可能会使得优化的方向从当前的局部极小值点跳到另一个更好的局部极小值点,这样便可能对于非凸函数,最终收敛于一个较好的局部极值点,甚至全局极值点。

由于波动,因此会使得迭代次数(学习次数)增多,即收敛速度变慢。不过最终其会和全量梯度下降算法一样,具有相同的收敛性,即凸函数收敛于全局极值点,非凸损失函数收敛于局部极值点。

小批量梯度下降(Mini-batch gradient descent)

相对于随机梯度下降,Mini-batch梯度下降降低了收敛波动性,即降低了参数更新的方差,使得更新更加稳定。相对于全量梯度下降,其提高了每次学习的速度。并且其不用担心内存瓶颈从而可以利用矩阵运算进行高效计算。

梯度下降法的缺点

靠近极小值时速度减慢。

直线搜索可能会产生一些问题。

可能会“之字型”地下降。

选择一个合理的学习速率很难。如果学习速率过小,则会导致收敛速度很慢。如果学习速率过大,那么其会阻碍收敛,即在极值点附近会振荡。

学习速率调整(又称学习速率调度,Learning rate schedules)试图在每次更新过程中,改变学习速率,如退火。一般使用某种事先设定的策略或者在每次迭代中衰减一个较小的阈值。无论哪种调整方法,都需要事先进行固定设置,这边便无法自适应每次学习的数据集特点。

模型所有的参数每次更新都是使用相同的学习速率。如果数据特征是稀疏的或者每个特征有着不同的取值统计特征与空间,那么便不能在每次更新中每个参数使用相同的学习速率,那些很少出现的特征应该使用一个相对较大的学习速率。

对于非凸目标函数,容易陷入那些次优的局部极值点中,如在神经网路中。

对于后面的几个缺点,在深度学习神经网络中,对梯度下降求解方法进行了各自优化。可参考【干货】机器学习最常用优化之一——梯度下降优化算法综述搜狐科技搜狐网

牛顿法

从梯度下降法可以知道,负梯度方向不能说是一个特别好的方向,牛顿法提出的方向要比负梯度更具有全局性。

牛顿法搜索方向推导

牛顿法推导

牛顿法和梯度下降法

阅读了解 椭球范数范数与距离的关系以及在机器学习中的应用 - CSDN博客
梯度下降法是欧式范数下的最速下降,牛顿法是椭球范数下的最速下降。

牛顿法的几点说明

图片来自 本章要点:最速下降法的基本思想及特点牛顿方向Newton法 - 道客巴巴

牛顿法几点说明

一维搜索牛顿法

针对上面的说明,在牛顿法中加入一维搜索。

一维搜索牛顿法

牛顿法优缺点

牛顿法收敛快,但每次需要存储二阶导数矩阵,且需要对其求逆运算。大规模场景下存储和计算代价太大,所以适合中小规模场景的算法。

MarQuart法

MarQuart法将牛顿法和最速下降法相结合,在初始时采用最速下降,靠近最小值点时采用牛顿法。

MarQuart法

拟牛顿法

为了避免每次循环都需要算Hessian矩阵并求逆运算,所以提出了拟牛顿方法。通过拟合一个近似的Hessian矩阵来求牛顿方向。

在学习过程中,参考了几个资料,在某些方面资料之间有些出入。几点说明里会写查了其他资料后我对出入的地方的理解

资料 牛顿法与拟牛顿法学习笔记(二)拟牛顿条件 - CSDN博客
逻辑回归:从入门到精通
wiki-Limited-memory_BFGS
wiki-BFGS
wiki-DFP

拟牛顿条件

拟牛顿条件

DFP

DFP推导

BFGS

BFGS推导

L-BFGS

L-BFGS推导-1

L-BFGS推导-2

L-BFGS的两步循环方法

下面两个资料写的很详细,可阅读:

逻辑回归:从入门到精通
wiki-Limited-memory_BFGS

几点说明

BFGS和DFP的区别

DFP拟合的是Hessian矩阵的逆,BFGS拟合的是Hessian矩阵本身并最终利用Sherman-Morrison公式直接推出直接从Dk的逆到Dk+1的逆

BFGS比DFP好在哪

BFGS和DFP都有一定能力进行自我修正,如果某个位置选择的矩阵不好,在未来几步,可以自我修正。这个能力,BFGS比DFP效果要好,这也是BFGS比较常用的原因。

换句话理解就是DFP有时候会震荡,而互换了y和s之后的BFGS更稳定,BFGS有自校正的性质(self-correcting property)。通俗来说,如果某一步BFGS对Hessian阵的估计偏了,导致优化变慢,那么BFGS会在较少的数轮迭代内(取决于线搜索的质量),校正估计的Hessian阵。

L-BFGS占用的存储空间

需要存储前m个 Si 和 Yi, 还有第k次的梯度gk。二次循环过程中的alpha, p, r。
其实要说的是初始的Hessian矩阵到底怎么取,取D0? 取 Dk-m?当然Dk-m肯定不行,为了省存储提出的L-BFGS方法,不会存储o(n^2)的Dk-m。所以这里需要一个对Dk-m的估计,与直接取D0 = I 相比,下面的近似好很多。

wiki-L-BFGS

各自的优缺点

BFGS和DFP一个比较好的性质是,如果H_k是正定的,则下一个Hk+1也是正定的,可以从公式中推导出来。不好的地方就是:需要存储这个对称矩阵。

L-BFGS需要的存储空间更小。

OWL-QN

QWL-QN 可阅读 逻辑回归:从入门到精通

由于L1正则项 | X | 在0点不可微,所以L-BFGS不能直接用来求解L1正则问题。QWL-QN方法通过定义伪梯度,将搜索限定在Xk的某个象限内,也就是说限定了Xk的每一项的正负,此时| X | 变成了一个线性项。

wiki-QWL-QN


0 Comments

理解PCA

PCA

PCA(Principal Component Analysis)是一种常用的数据分析方法。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示,可用于提取数据的主要特征分量,常用于高维数据的降维。

参考 PCA的数学原理(转)

基变换理解PCA降维

基变换

可以理解为:如果我们有M个N维向量,想将其变换为新空间里的M个R维向量,那么需要找到R个基按行组成矩阵P,然后将原始向量按列组成矩阵X,两矩阵的乘积PX就是降维结果,其中PX的第m列为X中第m列变换后的结果。

PCA求解过程推导

PCA要解决的问题就是:找到含有R个向量(R < 原始数据维度N)的一组基,并且尽量使得信息丢失最少。

信息丢失最少,即降维后的数据尽量保留原来数据之间的区分性。区分性在数学上可以用方差来表示;同时,不同的基尽量保持不相关。

PCA推导


0 Comments

理解L1和L2正则化

L1和L2正则化

首先回顾范数、拉普拉斯分布、高斯分布。
范数、拉普拉斯分布、高斯分布

过拟合

过拟合示例

通常过拟合时为了拟合更多的数据,拟合的曲线的导数都会变得很大,所以模型的参数很大。为了防止过拟合,可以引入正则化来限制模型参数过大。

什么情况下容易发生过拟合

在数据维度很高的情况下,模型参数很多,模型复杂度高,容易发生过拟合。比如,“small n, large p problem”。n是样本数,p是特征维度。在这种情况下,p越大模型越复杂,由线性代数里的解方程问题知 wx = y,此时会存在无穷多个解。

L1、L2正则化

L1、L2正则化

不管是L1正则,还是L2正则,都是将参数大小的贡献计算进了模型的损失里,来约束模型参数不取过大绝对值的数。

L1、L2正则化的不同

L1通常导致稀疏解,即稀疏的模型,使得参数里有很多的0,这些为0的特征可以理解为与问题相关性很小,这样稀疏的模型在线上大规模数据场景下优势明显,稀疏的解除了计算量上的好处之外,更重要的是更具有“可解释性”。

L2虽然也限制参数,但L2下参数保持非0的状态,向0靠近,但依旧不是0,也可以理解为L2认为所有特征都是有用的,只是相关性大小不同。

L1、L2正则化理解

从3个角度理解L1和L2正则化:

约束解

正则化可以理解成增加了一种约束,使得“小 n 大 p“问题的无穷解里,选择出一个合适的解。“小 n 大 p“说明了数据不足以确定一个在泛化数据上也效果很好的解,所以增加正则化约束来选择一个泛化效果也不错的解,泛化效果好,也就是防止了过拟合。

约束解-几何解释

如上图,损失函数的最小值容易在L1的角上取的,此时一个参数为0;而L2约束是一个圆,L2约束使得最优解靠近0。

梯度解析

梯度

从这个角度,L1带给参数的更新是sgn(Wi),即Wi为正时是1,为负时是-1。每次更新的方向都是将Wi每次改变恒定的一个单位长度向0靠近,直至为0,为0时L1正则的影响结束;

L2正则化每次更新的力度是Wi,随着Wi减小,更新的力度也随着减小,慢慢趋向于0。

先验分布

从贝叶斯的角度来看,正则化等价于对模型参数引入先验分布

回顾最大后验估计
最大似然估计和贝叶斯估计
Regularized Regression: A Bayesian point of view

以线性回归为例,y = wTx + e. e - N(0, l)

L1正则可以认为是给参数引入拉普拉斯分布

引入拉普拉斯分布

L2正则可以认为是给参数引入高斯分布

引入高斯分布


0 Comments

矩阵求导常用公式 Hessian矩阵 Jacobian矩阵

矩阵求导常用公式

机器学习推导时,有时候需要矩阵求导,可以先推导每个元素,最终归纳出矩阵形式,当然比较方便的就是查公式。

常用公式

Hessian矩阵、Jacobian矩阵

回顾:

方向角:一个向量与各个坐标轴的夹角。
一个向量的方向可以用坐标来表示,例如(-1,2,1),也可以用方向角来表示 (cos a, cos b, cos c)。 可阅读了解 向量的模与方向余弦的坐标表示式

参数方程:曲线上的任意一个点的坐标,都是某个参数t的函数,x = f(x), y = f(t). 对于t的每一个取值,参数方程组确定的点都在曲线上,这个方程组就是这条曲线的参数方程组。
可阅读了解 参数方程 - 数学知识点 - 简单学习网

多元函数,多个因变量下的一阶导数是Jacobian矩阵;

单一因变量下的一阶导数是一个与自变量维数相同的向量;

单一因变量下的二阶导数是Hessian 矩阵,矩阵的行数等于因变量的个数,列数等于自变量的个数,二阶导数等于一阶导数向量的Jacobian矩阵。

二阶导数代表了函数的凹凸性。

可阅读了解 最优化理论·光滑函数·Hessian矩阵·Jacobian矩阵·方向导数 - CSDN博客


0 Comments

容器-Advanced

散列与散列码

标准类库中的类被用作HashMap的键,用的很好,因为它具备了键所需要的全部性质。

如果需要使用自己的类作为HashMap的键,必须同时重载hashCode()和equals()。
hashCode()不需要总是能够返回唯一的标识码(应该更关注生成速度,而不是唯一性),但是equals()方法必须严格地判断两个对象是否相同。通过hashCode()和equals()必须能够完全的确定对象的身份。

实用的hashCode()一般速度快,且有意义。也就是说,它一般是基于对象的内容生成散列码,因为在使用中,两个对象的内容是否一致一般是场景下判断是否产生了重复元素的依据。

HashMap源码

HashMap在实现上采用数组+链表的方式。产生的hash冲突通过链表来解决。

HashMap的性能相关:

  1. 容量: 表中的桶位数,当负载达到负载因子水平时,会自动以2倍的量扩容。
  2. 初始容量: 表在创建时所拥有的桶位数,要求一定是2的n次幂。
  3. 负载因子: 超过负载自动扩容,扩容开销大。但负载因子太大,空间利用虽然提高,但查询遍历等操作变慢,因为链表变长了。
  4. null: HashMap允许null的key和null的value。key为null的键值对存储在table[0]下,但不一定在表头。

此外,新增的键值对会头插到每个桶的表头。

1
2
3
4
5
6
7
8
//计算hash值的方法 通过键的hashCode来计算
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

length为2的n次幂的好处:通过位运算实现取余操作,提升性能

1
2
3
static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值
return h & (length-1);
}

其他细节参考两篇解读源码的文章:

Java集合源码剖析:HashMap源码剖析

Java集合:HashMap源码剖析

0 Comments