———— 穷且益坚,不坠青云之志。

1. 最小均方误差 (Least Mean Squares)

上回说到,我们利用线性回归模型进行拟合,需要根据训练数据调节参数 [公式] 的值,使得对于任意训练数据 [公式] ,模型的输出 [公式] 更加接近目标值 [公式] ,同时最小化代价函数 (或误差函数)[公式] 使之无限趋近于0。由于误差函数是系数 [公式] 的二次函数(线性回归 [公式] 本身定义就是针对 [公式] 的线性函数),所以其导数是关于 [公式] 的线性函数,误差函数的最小值有唯一最优解 [公式] ,线性回归问题也可以看作是针对误差函数的优化问题。但由于求解系数 [公式] 通常是在一整个大数据集上进行的,我们很难得到精确的 [公式] ,最直观的方法就是逐一考虑每一个数据点 [公式] 来逼近 [公式] 

这种求解方法也称作顺序算法 (sequential algorithm)(或在线算 (on-line algorithm)),通过迭代每次只考虑⼀个数据点,模型的参数在每观测到数据点之后进⾏更新(实际上一般不会在每个点计算后都更新一次,这样效率极低且误差函数往往震荡不收敛。一般都是在小批量操作的),在迭代过程中通常梯度下降 (gradient descent) 算法来逐步优化求解 [公式] 

为了能找到使误差函数 [公式] 最小的参数 [公式] ,我们对 [公式] 的初值先做出一定假设(比如初始化为0),然后在利用梯度下降算法不断更新 [公式] 使之收敛至某处可以最小化 [公式] ,如下

[公式]

其中 [公式] 是迭代次数, [公式] 被称作学习率,是我们需要手动调节的超参数 (hyperparameter),会直接影响到函数能否收敛,需要反复斟酌选定。梯度下降算法通过反复迭代使权值向量 [公式] 都会沿着误差函数 [公式] 下降速度最快的⽅向移动,因此这种⽅法被称为梯度下降法或最速下降法 (steepest descent)。假设线性回归函数形式为 [公式] ,方便起见我们令 [公式] ,对于 [公式] 的平⽅和误差函数,有

[公式]

这被称为最小均方 (least mean squares, LMS) 或 Widrow-Hoff 算法。这种⽅法在直觉上看很合理,预测和目标之差 [公式] 是参数 [公式] 更新幅值的一项因子,包含梯度方向和幅值信息,因此,当预测值与真实目标比较接近时, [公式] 变化幅度也会较小,反之亦然。

2. 梯度下降 (Gradient Descent)

梯度下降算法使⽤梯度信息,权值参数 [公式] 通过迭代的方式,每次在误差函数 [公式] 关于 [公式] 负梯度⽅向上通过⼀次⼩的移动进行更新。误差函数是关于训练集定义的,因此计算 [公式] ,每⼀步都需要处理整个训练集,也称作批量梯度下降 (batch gradient descent),如下

[公式]

需要注意的是,虽然梯度下降通常可能会受到局部极小值的影响,但我们在此处针对的优化问题 [公式] 是一个关于 [公式] 的二次凸函数 (convex quadratic function),因此它只存在一个全局极小值 (global minimum) 且没有局部最小 (local minimum)。如下图所示

图片来自 CS229 lecture 1 讲义,椭圆表示二次型函数轮廓的轮廓采样。蓝色轨迹表示参数通过梯度下降算法的连续过程。

对于非线性的情形,误差函数 [公式] 可能存在多个局部最优,为了能找到⼀个⾜够好的极⼩值,可能有必要多次运⾏梯度下降算法,每次都随机选⽤不同的起始点,然后在⼀个独⽴的数据集上对⽐最终性能。

实际上批量梯度下降法在大数据集使用时效率很低,每一步都需要计算全部数据的梯度值,运算开销很高。然⽽,梯度下降法有另⼀个版本,与批量梯度下降算法不同,我们每一步更新都是基于⼀个独⽴观测数据的误差函数,这种算法也称作随机梯度下降 (stochastic gradient descent) 或顺序梯度下降 (sequential gradient descent, Bishop PRML) 或递增梯度下降 (incremental gradient descent, CS229),使得权值参数的更新每次只依赖于⼀个数据点,即

[公式]

与批量梯度下降相⽐,随机梯度下降的⼀个优点是可以更加⾼效地处理数据中的冗余性。考虑⼀种极端的情形:给定⼀个数据集,我们将每个数据点都复制⼀次,从⽽将数据集的规模翻倍,但这仅仅把误差函数乘以⼀个因⼦2,等价于使⽤原始的误差函数。批量梯度下降法必须付出两倍的计算量来计算误差函数的梯度,⽽在随机梯度下降法则不受影响。

随机梯度下降另⼀个特点是便于逃离局部极⼩值点,因为整个数据集误差函数的驻点通常不会是单一数据点误差函数的驻点,然而,也正因如此,我们几乎永远无法得到关于整个数据集的参数最优解 [公式] ,因为我们每次计算的都是单一数据点误差函数关于 [公式] 的梯度。此外,随机梯度下降法的参数更新过于频繁,除了迭代次数会骤增,权值参数的更新过程也会不断震荡很难收敛。折中的⽅法是,每次更新依赖于一组独立观测的数据点,实现小批量数据上的随机梯度下降 (minibatch stochastic gradient descent)。

3. 梯度之上:Jacobian 和 Hessian 矩阵

该部分参考自 Bengio《Deep Learning》,难度较大直接引用原文译文较多。

有时我们需要计算输入输出均为向量的函数的所有偏导数(可以理解为多目标的回归问题或分类问题),包含所有这样的偏导数的矩阵被称为 Jacobian 矩阵。具体来说,如果我们有一个函数映射 [公式]  [公式] 的 Jacobian 矩阵 [公式] 定义为 [公式] 

有时,我们也对导数的导数感兴趣,即二阶导数 (second derivative),一维情况下,我们将二阶导数记作 [公式] ,二阶导数表示一阶导数如何随着输入的变化而改变,即基于梯度信息的下降步骤是否会产生如我们预期的那样的改善。二阶导数是对曲率 (curvature) 的衡量。

3.1 二次函数曲率

延续上述篇幅的所使用的二次误差函数 [公式] ,真实的误差函数形式往往要复杂许多,但利用泰勒展开我们可以在小范围区间用多项式函数拟合绝大部分未知函数,而随机梯度下降的更新也是在微观步骤上更新的,因此对于连续可导的误差函数 [公式] ,我们同样可以把它当做一个样条函数(参见第一篇文章),每一处都当做一个多项式函数,为简便起见我们只考虑到二阶泰勒展开级数,也就是使用二次函数进行局部拟合,此时误差函数就可以看做由无数个不同的二次函数的微小区间所组成的连续且处处可导的函数。

取二次函数进行拟合也是为了更方便的观察二阶导数,我们使用沿负梯度方向大小为的 [公式] 下降步(类似上文梯度下降算法中的学习率 [公式] ,因为梯度下降算法目标与预测值之差也会包含一定下降幅度信息,而此处下降步包含了所有梯度下降的幅度信息)。当该梯度是 1 时,代价函数将下降 [公式] 。 如果二阶导数是负的 (negative curvature),函数曲线向上凸出,代价函数将下降的比 [公式] 多;如果二阶导数为 0 (no curvature),那就没有曲率,仅用梯度就可以预测它的值;如果二阶导数是正的 (positive curvature),函数曲线是向下凸出,代价函数将下降的比 [公式] 少。下图依次反应了三种情况的曲率如何影响基于梯度的预测值与真实误差函数值的关系。

图片来自 Bengio 《Deep Learning》. Figure 4.4.

3.2 Hessian 特征值

当函数具有多维输入输出时,二阶导数也有很多。我们可以将这些导数合并成一个矩阵,称为 Hessian 矩阵。Hessian 矩阵 [公式] 定义为

[公式]

其中二阶导数项表示 [公式] 的一阶导数(关于 [公式] )关于 [公式] 的导数,Hessian 等价于梯度的 Jacobian 矩阵,微分算子在任何二阶偏导连续的点处可交换,也就是它们的顺序可以互换。这意味着 [公式] ,因此 Hessian 矩阵在这些点上是对称的。因为 Hessian 矩阵是实对称的,我们可以将其分解成一组实特征值和一组特征向量的正交基。在特定方向 [公式] 上的二阶导数可以写成 [公式] 。当 [公式]  [公式] 的一个特征向量时,这个方向的二阶导数就是对应的特征值。对于其他的方向 [公式] ,方向二阶导数是所有特征值的加权平均,权重在 0 和 1 之间, 且与 [公式] 夹角越小的特征向量的权重越大。最大特征值确定最大二阶导数,最小特征值确定最小二阶导数。

我们可以通过(方向)二阶导数预期一个梯度下降步骤能表现得多好。我们在 当前点 [公式] 处作函数 [公式] 的近似二阶泰勒级数:

[公式]

其中 [公式] 是梯度, [公式]  [公式] 点的 Hessian。如果我们使用学习率 [公式] , 那么新的点 [公式] 将会是 [公式] 。 代入上述近似,可得

[公式]

其中有 3 项:函数的原始值、函数斜率导致的预期改善、函数曲率导致的校正。当最后一项太大时,梯度下降实际上是可能向上移动的。当 [公式] 为零或负时,近似的泰勒级数表明增加 [公式] 将永远使 [公式] 下降。在实践中,泰勒级数不会在 [公式] 大的时候也保持准确,因为我们对误差函数的近似二次拟合都是微小区间的,学习率过大很可能就到另一个二次函数的区间了,因此在这种情况下我们必须采取更启发式的选择。当 [公式] 为正时,通过计算可得,使近似泰勒级数下降最多的最优学习率为

[公式]

最坏的情况下, [公式]  [公式] 最大特征值 [公式] 对应的特征向量对齐,则最优步长是 [公式] 。 我们要最小化的误差函数能用二次函数很好地近似的情况下,Hessian 的特征值决定了学习率的量级。

3.3 二阶导数测试

二阶导数还可以被用于确定一个临界点是否是局部极大点、局部极小点或鞍点。在临界点处 [公式] 。而 [公式] 意味着 [公式] 会随着我们移向右边而增加,移向左边而减小,也就是 [公式]  [公式] 对足够小的 [公式] 成立。因此我们得出结论,当 [公式]  [公式] 时, [公式] 是一个局部极小点。同样,当 [公式]  [公式] 时, [公式] 是一个局部极大值点。这就是所谓的二阶导数测试 (second derivative test)。不幸的是,当 [公式] 时测试是不确定的。在这种情况下, [公式] 可以是一个鞍点或平坦区域的一部分。

在多维情况下,我们需要检测函数的所有二阶导数。利用 Hessian 的特征值分解,我们可以将二阶导数测试扩展到多维情况。在临界点处 [公式] ,我们通过检测 Hessian 特征值来判断该临界点是一个局部极大点、局部极小点还是鞍点。 当 Hessian 是正定的(所有特征值都是正的),则该临界点是局部极小点。同样的,当 Hessian 是负定的(所有特征值都是负的),这个点就是局部极大点。在多维情况下,我们可以找到确定该点是否为鞍点的迹象。如果 Hessian 的特征值中至少一个是正的且至少一个是负的,那么 [公式]  [公式] 某个横截面的局部极大点,却是另一个横截面的局部极小点,典型例子就是鞍点。最后,多维二阶导数测试可能像单变量版本那样是不确定的。当所有非零特征值是同号的且至少有一个特征值是 0 时,这个检测就是不确定的。这是因为单变量的二阶导数测试在零特征值对应的横截面上是不确定的。

多维情况下, 单个点处每个方向上的二阶导数是不同。Hessian 的条件数 (condition number) 衡量这些二阶导数的变化范围。当 Hessian 的条件数很差时,梯度下降法也会表现得很差。这是因为一个方向上的导数增加得很快,而在另一个方向上增加得很慢。梯度下降不知道导数的这种变化,所以它不知道应该优先探索导数长期为负的方向,如下图所示。为了避免冲过最小而向具有较强正曲率的方向,防止发生震荡,我们需要将学习率设置较小,然而这也导致了更新步长太小,在其他较小曲率的方向上进展不明显。

图片来自 Bengio 《Deep Learning》. Figure 4.6.

3.4 牛顿法

上图中,红线表示梯度下降的路径。这个非常细长的二次函数类似一个长峡谷。梯度下降把时间浪费于在峡谷壁反复下降,因为它们是最陡峭的特征。由于步长有点大,有超过函数底部的趋势,因此需要在下一次迭代时在对面的峡谷壁下降。与指向该方向的特征向量对应的 Hessian 的大的正特征值表示该方向上的导数值仍然较大,因此基于 Hessian 的优化算法可以预测,在此情况下最陡峭方向实际上不是有前途的搜索方向。

我们可以使用 Hessian 矩阵的信息来指导搜索,以解决这个问题。其中最简单的方法是牛顿法 (Newton’s method)。仅使用梯度信息的优化算法被称为一阶优化算法 (first-order optimization algorithms),如梯度下降。使用 Hessian 矩阵的优化算法被称为二阶最优化算法 (second-order optimization algorithms),如牛顿法。牛顿法基于一个二阶泰勒展开来近似 [公式] 附近的 [公式] 

[公式]

计算这个函数的临界点,令 [公式] ,得

[公式]

 [公式] 是一个正定二次函数时,牛顿法只要应用一次式就能直接跳到函数的最小点。如果 [公式] 能在局部近似为正定二次,牛顿法则需要多次迭代。迭代地更新近似函数和跳到近似函数的最小点可以比梯度下降更快地到达临界点。这在接近局部极小点时是一个特别有用的性质,但是在鞍点附近是有害的。当附近的临界点是最小点(Hessian 的所有特征值都是正的)时牛顿法才适用,而梯度下降不会被鞍点吸引。

4. 解析法 (Analytic Method)

上回说到,我们可以利用梯度下降法来求解最小平方和函数,回忆第一节所定义的平方和误差函数 [公式] ,也是似然函数,我们可以用最大似然的方法确定 [公式]  [公式] ,在条件⾼斯噪声分布的情况下,采用线性基函数的形式,线性函数的对数似然函数如下(详细定义参考第一篇 1.3 节)

[公式]

线性模型的似然函数的最⼤化等价于平⽅和误差函数的最⼩化,我们在第二篇文章提及,对数似然函数是关于 [公式] 的二次函数,所以似然函数有唯一最优解 [公式] ,前文中我们是从微观的角度将训练集中的数据依次代入计算 [公式] ,通过梯度下降算法用迭代的形式逼近 [公式]。本文将使用一种更为直观,整体的方法,首先对数似然函数的梯度为

[公式]

令对数似然函数的梯度为 0 求解 [公式] ,可得

[公式]

这就是使用解析法 (analytic method) 对方程直接求解,也称为最小平方问题的规范方程 (normal equation)。这⾥ [公式] 是⼀个 [公式] 的矩阵,被称为设计矩阵 (design matrix),它的元素为 [公式] ,即

[公式]

 [公式] 被称为矩阵 [公式] 的 Moore-Penrose 伪逆矩阵 (pseudo-inverse matrix)。 它可以被看成逆矩阵的概念对于⾮⽅阵的矩阵的推⼴。实际上,如果 [公式] 是⽅阵且可逆,那么使⽤性质 [公式] ,我们可以看到 [公式] 。在实际应⽤中,当 [公式] 接近奇异矩阵时,直接求解规范⽅程会导致数值计算上的困难。特别地,当两个或者更多的基函数向量共线(矩阵 [公式] 的列)或者接近共线时,最终的参数值会相当⼤。这种数值计算上的困难可以通过奇异值分解 (singular value decomposition) 的⽅法解决。注意,正则项的添加确保了矩阵是⾮奇异的,关于正则项会在下一篇文章讨论。

注意此处关于基函数的写法,实际上 (12) 式中 [公式] ,参数 [公式] 维度 [公式] ,在第一篇文章 1.2 节提到,线性基函数变换的本质还是特征提取,此处直接对基函数变换之后的特征进行线性变换,所以我们忽略了数据点 [公式] 的原始维度,而 CS229 讲义中是对原始数据 [公式] 进行线性变换,所以写法上略有不同,但原理是一样的,此处的 [公式] 相当于 CS229 讲义中的 [公式] ,是一个 [公式] 的矩阵,横向是将 (12) 式中的求和步骤改为将所有训练数据点合并在矩阵内,纵向是每个数据点的特征,如果是直接进行线性变换就是原始数据点的维度,如果进行过基函数变换就是基函数的数量。

现在,我们可以更加深刻地认识偏置参数 [公式] 。如果我们显式地写出偏置参数,那么误差函 数变为

[公式]

令关于 [公式] 的导数等于零,解出 [公式] ,可得

[公式]

可以看出偏置 [公式] 补偿了训练数据⽬标值的平均值 [公式] 与基函数的值的平均值的加权求和 [公式] 之间的差。

回归第一篇文章 1.3 节内容,我们也可以关于噪声精度参数 [公式] 最⼤化似然函数

[公式]

因此我们看到噪声精度的倒数由⽬标值在回归函数周围的残留⽅差 (residual variance) 给出。

5. 最小平方的几何描述 (Geometry of Least Squares)

我们考虑⼀个 [公式] 维空间,它的坐标轴由 [公式] 给出, 即 [公式] 是这个空间中的⼀个向量。 每个在 [公式] 个数据点处估计的基函数 [公式] 也可以表示为这个空间中的⼀个向量, 记作 [公式]  [公式] 对应于 [公式] 的第 [公式] 列,⽽ [公式] 对应于 [公式] 的第 [公式] ⾏。 如果基函数的数量 [公式] ⼩于数据点的数量 [公式] (很容易联想特征数小于数据点个数,未知参数才有唯一解),那么 [公式] 个向量 [公式] 将会张成⼀个 [公式] 维的⼦空间 [公式] 。我们定义 [公式] 是⼀个 [公式] 维向量。由于 [公式]  [公式] 个向量 [公式] 的任意线性组合,因此它可以位于 [公式] 维⼦空间的任何位置。这样,平⽅和误差函数就等于 [公式]  [公式] 之间的欧⽒平方距离。 因此, [公式] 的最⼩平⽅解对应位于⼦空间 [公式] 的与 [公式] 最近的 [公式] 的选择。直观来看,根据下图,我们很容易猜想这个解对应于 [公式] 在⼦空间 [公式] 上的正交投影。 事实上确实是这样。 假设 [公式] (下图中的 [公式] ,此处重新定义向量是针对原书做区分,原书中已经定义了 [公式] 是一个 [公式] 维向量此处又出现在⼦空间 [公式] 上容易产生误解)是子空间 [公式]  [公式] 在参数为[公式] 时的线性组合,只要证明它的表达式为 [公式] 的正交投影即可。

图片来自 Bishop PRML. Figure 3.2.

本文主要讲了利用梯度下降算法和解析法解决最小平方误差和的问题,以及关于梯度的一些延伸。线性回归部分暂时到此结束,基本按照 CS229 为主线,内容大部分都选取 Bishop PRML ,但书上线性回归模型一共有五小节内容,到此我也只总结完第一节内容,后面内容更复杂,第一遍过教材还是希望能建立一个完整的知识体系,对机器学习有个宏观的认识架构,尽量避免深究拖延进度导致战线拉长而失去热情。下一篇文章将介绍一些机器学习的学习理论知识。