欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

Alink探讨：用L-BFGS优化进行线性回归（Alink漫谈第十一部分）

最编程 2024-08-13 11:30:04
...

Alink漫谈(十一) ：线性回归 之 L-BFGS优化

0x00 摘要

Alink 是阿里巴巴基于实时计算引擎 Flink 研发的新一代机器学习算法平台，是业界首个同时支持批式算法、流式算法的机器学习平台。本文介绍了线性回归的L-BFGS优化在Alink是如何实现的，希望可以作为大家看线性回归代码的Roadmap。

因为Alink的公开资料太少，所以以下均为自行揣测，肯定会有疏漏错误，希望大家指出，我会随时更新。

0x01 回顾

到目前为止，已经处理完毕输入，请参见Alink漫谈(十) ：线性回归实现 之 数据预处理，接下来就是优化。优化的主要目标是找到一个方向，参数朝这个方向移动之后使得损失函数的值能够减小，这个方向往往由一阶偏导或者二阶偏导各种组合求得。 所以我们再次复习下基本思路。

1.1 优化基本思路

对于线性回归模型 f(x) = w'x+e，我们构造一个Cost函数（损失函数）J(θ)，并且通过找到 J(θ) 函数的最小值，就可以确定线性模型的系数 w 了。

最终的优化函数是：min(L(Y, f(x)) + J(x)) ，即最优化经验风险和结构风险，而这个函数就被称为目标函数。

我们要做的是依据我们的训练集，选取最优的θ，在我们的训练集中让f(x)尽可能接近真实的值。我们定义了一个函数来描述 “f(x)和真实的值y之间的差距“，这个函数称为目标函数，表达式如下：

J(θ)≈12∑i≈1m(fθ(x(i)—y(i))2J(θ)≈\frac{1}{2} \sum_{i≈1}^m(f_θ(x^{(i)} — y^{(i)})^2\\

这里的目标函数就是著名的最小二乘函数。

我们要选择最优的θ，使得f(x)最近进真实值。这个问题就转化为求解最优的θ，使目标函数 J(θ) 取最小值。

1.2 各类优化方法

寻找合适的W令目标函数f(W) 最小，是一个无约束最优化问题，解决这个问题的通用做法是随机给定一个初始的W0，通过迭代，在每次迭代中计算目标函数的下降方向并更新W，直到目标函数稳定在最小的点。

不同的优化算法的区别就在于目标函数下降方向Dt的计算。下降方向是通过对目标函数在当前的W下求一阶倒数（梯度，Gradient）和求二阶导数（海森矩阵，Hessian Matrix）得到。常见的算法有梯度下降法、牛顿法、拟牛顿法。

  • 梯度下降法直接采用目标函数在当前W的梯度的反方向作为下降方向。
  • 牛顿法是在当前W下，利用二次泰勒展开近似目标函数，然后利用该近似函数来求解目标函数的下降方向。其中Bt为目标函数f(W)在Wt处的海森矩阵。这个搜索方向也称作牛顿方向。
  • 拟牛顿法只要求每一步迭代中计算目标函数的梯度，通过拟合的方式找到一个近似的海森矩阵用于计算牛顿方向。
  • L-BFGS(Limited-memory BFGS)则是解决了BFGS中每次迭代后都需要保存N*N阶海森逆矩阵的问题，只需要保存每次迭代的两组向量和一组标量即可。

Alink中，UnaryLossObjFunc是目标函数，SquareLossFunc 是损失函数，使用L-BFGS算法对模型进行优化。

即 优化方向由拟牛顿法L-BFGS搞定(具体如何弄就是看f(x)的泰勒二阶展开)，损失函数最小值是平方损失函数来计算。

0x02 基本概念

因为L-BFGS算法是拟牛顿法的一种，所以我们先从牛顿法的本质泰勒展开开始介绍。

2.1 泰勒展开

泰勒展开是希望基于某区间一点x_0展开，用一组简单的幂函数来近似一个复杂的函数f(x)在该区间的局部。泰勒展开的应用场景例如：我们很难直接求得sin(1)的值，但我们可以通过sin的泰勒级数求得sin(1)的近似值，且展开项越多，精度越高。计算机一般都是把 sin(x)进行泰勒展开进行计算的。

泰勒当年为什么要发明这条公式？

因为当时数学界对简单函数的研究和应用已经趋于成熟，而复杂函数，比如：f(x) = sin(x)ln(1+x) 这种一看就头疼的函数，还有那种根本就找不到表达式的曲线。除了代入一个x可以得到它的y，就啥事都很难干了。所以泰勒同学就迎难而上！决定让这些式子统统现出原形，统统变简单。

要让一个复杂函数变简单，能不能把它转换成别的表达式？泰勒公式一句话描述：就是用多项式函数去逼近光滑函数。即，根据“以直代曲、化整为零”的数学思想，产生了泰勒公式。

泰勒公式通过把【任意函数表达式】转换（重写）为【多项式】形式，是一种极其强大的函数近似工具。为什么说它强大呢？

  • 多项式非常【友好】，三易，易计算，易求导，易积分
  • 几何感觉和计算感觉都很直观，如抛物线和几次方就是底数自己乘自己乘几次

如何通俗推理？

泰勒公式干的事情就是：使用多项式表达式估计（近似） 在 附近的值。

当我们想要仿造一个东西的时候，无形之中都会按照如下思路，即先保证大体上相似，再保证局部相似，再保证细节相似，再保证更细微的地方相似……不断地细化下去，无穷次细化以后，仿造的东西将无限接近真品。真假难辨。

物理学家得出结论：把生活中关于“仿造”的经验运用到运动学问题中，如果想仿造一段曲线，那么首先应该保证曲线的起始点一样，其次保证起始点处位移随时间的变化率一样（速度相同），再次应该保证前两者相等的同时关于时间的二阶变化率一样（加速度相同）……如果随时间每一阶变化率（每一阶导数）都一样，那这俩曲线肯定是完全等价的。

所以如果泰勒想一个办法让自己避免接触 sin(x)这类函数，即把这类函数替换掉。 就可以根据这类函数的图像，仿造一个图像，与原来的图像相类似，这种行为在数学上叫近似。不扯这个名词。讲讲如何仿造图像。

仿造的第一步，就是让仿造的曲线也过这个点。

完成了仿造的第一步，很粗糙，甚至完全看不出来这俩有什么相似的地方，那就继续细节化。开始考虑曲线的变化趋势，即导数，保证在此处的导数相等。

经历了第二步，现在起始点相同了，整体变化趋势相近了，可能看起来有那么点意思了。想进一步精确化，应该考虑凹凸性。高中学过：表征图像的凹凸性的参数为“导数的导数”。所以，下一步就让二者的导数的导数相等。

起始点相同，增减性相同，凹凸性相同后，仿造的函数更像了。如果再继续细化下去，应该会无限接近。所以泰勒认为“仿造一段曲线，要先保证起点相同，再保证在此处导数相同，继续保证在此处的导数的导数相同……”

泰勒展开式就是把一个三角函数或者指数函数或者其他比较难缠的函数用多项式替换掉。

也就是说，有一个原函数f(x) ，我再造一个图像与原函数图像相似的多项式函数 g(x) ，为了保证相似，我只需要保证这俩函数在某一点的初始值相等，1阶导数相等，2阶导数相等，……n阶导数相等。

2.2 牛顿法

牛顿法的基本思路是，在现有极小点估计值的附近对 f(x) 做二阶泰勒展开，进而找到极小点的下一个估计值。其核心思想是利用迭代点 x_k 处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值。

梯度下降算法是将函数在 xn 位置进行一次函数近似，也就是一条直线。计算梯度，从而决定下一步优化的方向是梯度的反方向。而牛顿法是将函数在 xn 位置进行二阶函数近似，也就是二次曲线。计算梯度和二阶导数，从而决定下一步的优化方向。

我们要优化的都是多元函数，x往往不是一个实数，而是一个向量。所以f(x) 的一阶导数也是一个向量，再求导的二阶导数是一个矩阵，就是Hessian矩阵。

2.2.1 泰勒一阶展开

牛顿法求根可以按照泰勒一阶展开。例如对于方程 f(x) = 0，我们在任意一点 x0 处，进行一阶泰勒展开：

f(x)=f(x0)+(x−x0)f′(x0)f(x) = f(x_0) + (x - x_0)f^{ '}(x_0)

令 f(x) = 0，带入上式，即可得到：

x=x0−f(x0)f′(x0)x = x_0 - \frac{f(x_0)}{f^{'}(x_0)}

注意，这里使用了近似，得到的 x 并不是方程的根，只是近似解。但是，x 比 x0 更接近于方程的根。

然后，利用迭代方法求解，以 x 为 x0，求解下一个距离方程的根更近的位置。迭代公式可以写成：

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f^{'}(x_n)}

2.2.2 泰勒二阶展开

机器学习、深度学习中，损失函数的优化问题一般是基于一阶导数梯度下降的。现在，从另一个角度来看，想要让损失函数最小化，这其实是一个最值问题，对应函数的一阶导数 f'(x) = 0。也就是说，如果我们找到了能让 f'(x) = 0 的点 x，损失函数取得最小值，也就实现了模型优化目标。

现在的目标是计算 f’(x) = 0 对应的 x，即 f’(x) = 0 的根。转化为求根问题，就可以利用上一节的牛顿法了。

与上一节有所不同，首先，对 f(x) 在 x0 处进行二阶泰勒展开：

f(x)=f(x0)+(x−x0)f′(x0)+12(x−x0)2f′′(x0)f(x) = f(x_0) + (x - x_0)f^{'}(x_0) + \frac{1}{2}(x-x_0)^2f^{''}(x_0)

上式成立的条件是 f(x) 近似等于 f(x0)。令 f(x) = f(x0)，并对 (x - x0) 求导，可得：

x=x0−f′(x0)f′′(x0)x = x_0 - \frac{f^{'}(x_0)}{f^{''}(x_0)}

同样，虽然 x 并不是最优解点，但是 x 比 x0 更接近 f'(x) = 0 的根。这样，就能得到最优化的迭代公式：

xn+1=xn−f′(xn)f′′(xn)x_{n+1} = x_n - \frac{f^{'}(x_n)}{f^{''}(x_n)}

通过迭代公式，就能不断地找到 f'(x) = 0 的近似根，从而也就实现了损失函数最小化的优化目标。

2.2.3 高维空间

在机器学习的优化问题中，我们要优化的都是多元函数，所以x往往不是一个实数，而是一个向量。所以将牛顿求根法利用到机器学习中时,x是一个向量，f(x) 的一阶导数也是一个向量，再求导的二阶导数是一个矩阵，就是Hessian矩阵。

在高维空间，我们用梯度替代一阶导数，用Hessian矩阵替代二阶导数，牛顿法的迭代公式不变：

xk+1=xk−[Hf(xk)−1].Jf(xk)x_{k+1} = x_k - [Hf(x_k)^{-1}].J_f(x_k)

其中 J 定义为 雅克比矩阵，对应一阶偏导数。

推导如下 ：

我们假设f(x)是二阶可微实函数，把f(x)在xk处Taylor展开并取二阶近似为

f(x)≈f(xk)+∇f(xk)T(x−xk)+12(x−xk)T∇2f(xk)(x−xk)xk为当前的极小值估计值∇f(xk)是f(x)在xk处的一阶导数∇2f(x)是f(x)在xk处的Hessen矩阵。\begin{aligned}&f(x)≈f(x^k)+∇f(x^k)T(x−x^k)+\frac{1}{2}(x−x^k)^T∇^2f(x^k)(x−x^k)\\&x^k为当前的极小值估计值\\&∇f(x^k)是f(x)在x^k处的一阶导数\\&∇^2f(x) 是f(x)在x^k处的Hessen矩阵。\\\end{aligned}

推荐阅读