机器学习及其应用最新章节_汪荣贵著

2.2 模型优化基本方法

在优化目标较为复杂时，通常很难直接通过参数估计方法求得最优估计值。事实上，机器学习的模型训练除了使用前述参数估计法之外，还可通过数值优化计算方法确定模型参数。这类数值优化方法通常采用迭代逼近的方式确定最优解。在逼近最优解的过程中，模型性能会逐渐提升，故称此类方法为模型优化方法。由于模型优化方法采用迭代方式逼近最优解的策略，故在很多情况下能够有效应对优化目标较为复杂的情况。机器学习的模型优化方法有很多，本节主要介绍两种基本方法，即梯度下降方法和牛顿迭代法。

2.2.1 梯度下降法

梯度下降方法是机器学习最常用的模型优化方法之一，其基本思想是朝着函数梯度的反方向不断迭代更新参数。由于梯度方向为函数值上升最快的方向，故梯度反方向就是函数值下降最快的方向。一直朝着梯度反方向更新参数可以使函数值得到最快的下降，从而能够尽可能快速地逼近函数极小值点直至收敛。梯度下降方法的数学表达如下

其中， step _k 为第 k 次迭代的步长； P _k 为第 k 次寻优方向，即为梯度反方向。

式（2-11）的含义是在第 k 次迭代起始点 X _k 确定的情况下，向目标函数梯度反方向走一段距离并将此次所到新位置 X _k + step _k P _k 作为下次迭代的起点赋值给 X _k ₊₁ 。通过对 step _k 适当取值就可由此得到目标函数的最优解。图2-1表示初始迭代点为 X ₁ 的梯度下降迭代过程。

梯度下降方法的关键在于如何确定每次迭代的搜索方向和迭代步长。以图2-1所示的迭代过程为例，从起始点 X ₁ 开始通过梯度下降法进行迭代优化，则有

X ₂ = X ₁ + step ₁ P ₁

其中，。

令 F （ X ）为优化的目标函数，则步长 step ₁ 可通过下列优化方式确定

图2-1 梯度下降方法的迭代过程

现给出步长 step _k 的具体计算公式，根据二次泰勒展开式可将目标函数 F （ X ）近似表示为正定二次函数

其中， A 为正定的系数矩阵； X 为参数向量； b 为常数向量； c 为常数。

在 X _k 处对 F （ X ）求梯度可得。从 X _k 点出发沿着梯度的反方向进行搜索，则有

在选择最优步长时，每步搜索方向均与上步搜索方向正交，即有。将展开，则有[ A （ X _k - step _k P _k ）+ b ^T ] P _k =0，由此解出 step _k 并将其代入迭代公式（2-14），则可将梯度下降迭代公式进一步改写为

在机器学习的具体应用中，梯度下降方法的步长有时会根据需要人为设定，这需要一定的经验。如果步长设定过大，则会导致算法不收敛；如果步长设定过小，则会使算法收敛得较慢，提高计算的时间成本。

例如，对于函数问题min ，显然有

假设起始点为 X ₁ =（1，1） ^T ，则有 F （ X ₁ ）=5，。由迭代公式可得

若迭代次数允许，则可一直迭代下去，直到满足终止条件，得到近似最优解。

【例题2.5】 试根据表2-4中的数据建立线性回归模型，并使用该模型预测出面积为137m ² 的房屋价格，要求其中对目标函数的优化采用梯度下降法。

表2-4 房屋价格与房屋面积数据

【解】 表2-4中数据较大，不方便计算，因此这里先对其进行归一化处理再求解线性回归模型，具体方式为

X =（ S _i - S _min ）/（ S _max - S _min ）； y =（ P _i - P _min ）/（ P _max - P _min ）

其中， S _min 和 S _max 分别表示最小和最大的房屋面积取值； S _i 表示序号为 i 的房屋的面积取值； P _min 和 P _max 分别表示最小和最大的房屋价格取值； P _i 表示序号为 i 的房屋价格取值。

经过归一化后的数据如表2-5所示。

表2-5 归一化后的数据

假设模型的具体形式为 y = w ₁ X + w ₀ 。使用该模型构造目标函数，并采用误差平方和作为优化目标。为方便计算，将目标函数定义为1/2倍的误差平方和，即

其中， y ⁱ 为序号为 i 的数据的真实值；为对应的预测值； w =（ w ₀ ， w ₁ ） ^T 为参数向量

使用梯度下降方法对上述目标函数进行优化，通过如下迭代公式更新参数向量

其中， η 为步长，此处步长选定为 η =0.01； w _old 表示当前更新的起点； w _new 表示更新后的权重向量。目标函数 E （ w ）的梯度为

由此可将梯度下降算法的迭代计算公式转化为

设置 w ⁰ =（1，1） ^T ，对上式进行1000次迭代，通过Python编程计算可得如表2-6所示的计算结果（表中仅给出部分迭代结果）。

表2-6 梯度下降方法迭代取值表

由表2-6中数据可知，经过1000次迭代后算法趋于收敛。因此可根据梯度下降方法求得线性回归模型为 y =0.704037 X +0.142370。对面积为137m ² 的房屋价格进行预测时，应先对该面积数据进行归一化计算，得到归一化后数据为 X =0.2。将其代入回归模型计算对应的预测输出为 y =0.2831774，即得房屋价格预测值为257.33万元。

梯度下降法在靠近极小值时收敛速度通常会减慢，使得计算效率下降。人们为此提出了很多改进策略，共轭梯度下降法就是其中之一。共轭梯度下降法最初为求解非线性方程组而提出，后被推广到求解无约束优化问题，并逐渐成为最具代表性的最优化方法之一。该算法思想与梯度下降方法的相同之处在于都有着沿目标函数负梯度方向搜索的步骤；不同点在于梯度下降方法的搜索方向一直是负梯度方向，共轭梯度下降法的搜索方向从第二次确定搜索方向时，不再采用负梯度方向，而是经修正后的方向。因此，如何修正下次迭代的搜索方向是共轭梯度下降法的关键技术。下面具体介绍共轭梯度下降法。首先，给出共轭的概念。

设 A 为 R ⁿ ^× ⁿ 上的对称正定矩阵， Q ₁ ， Q ₂ 为 R ⁿ 上的两个非零向量，若有，则称 Q ₁ 与 Q ₂ 关于矩阵 A 共轭，向量 Q ₁ 与 Q ₂ 的方向为一组 共轭方向 。

共轭梯度下降法的基本思路如图2-2所示。首先，任意选取初始点 X ₁ ，计算目标函数在该点的梯度值，并将负梯度方向作为初次搜索方向，即；然后，按图中箭头方向搜索下一点，即按公式 X _k ₊₁ = X _k + α _k P _k 计算下一点 X ₂ ，其中 α _k 表示第 k 次迭代步长，为的优化值。

图2-2 共轭梯度下降法

搜索到 X ₂ 后，计算该点对应的梯度值，并按下式调整搜索方向

其中， step _k 为调整搜索方向时的步长。将式（2-16）两侧同时乘以 AP _k 可得

将步长 step _k 调整为 step _k ₊₁ ，使得 P _k ₊₁ 和 P _k 关于 A 共轭，即有，可得

重复以上步骤，即可得到逼近最优解的序列{ X ₁ ， X ₂ ，…， X _n ，…}。

例如，对于优化问题，取 X ₁ =（2，2） ^T 为迭代初始值，由此可得初次的搜索方向，并按下式计算 X ₂

首先，通过优化问题arg min[2（2-8 α ₁ ） ² +（2-4 α ₁ ） ² ]求出 α ₁ =5/18，然后由此算出 X ₂ =（-2/9，8/9） ^T 和。再由式（2-18）算出 α ₂ =9/20，由此算出函数极值点 X ₃ =（0，0） ^T 。

【例题2.6】 UCI_IRIS数据集是一个常用训练数据集，共有121条数据，表2-7为其中的部分数据。试用UCI_IRIS数据集和共轭梯度下降法训练一个多层神经网络模型。

【解】 由表2-7可知，UCI_IRIS数据集中每个示例包含4个特征，所有示例分属3个类别。故感知机模型输入层应包含4个特征输入结点及1个偏置输入结点，输出层应包含3个输出结点。由此可构造如图2-3所示具有10个隐含结点的神经网络模型。

表2-7 UCI_IRIS数据训练集中部分数据

图2-3 包含10个隐含结点的多层神经网络

令为第 ι 层第 i 个神经元与第 ι +1层第 k 个神经元之间的连接权重，为第 ι 层第 i 个结点的偏置项，第 ι 层激活函数表示为 φ ^ι ，则对于样本输入 X =（ x ₁ ， x ₂ ， x ₃ ， x ₄ ） ^T ，该模型的第 j 个隐含层结点的输出 h _j 为

将上式表示为矩阵形式，则有

同理可得该模型的输出 f （ X ）为

其中， φ ² 为Sigmoid激活函数； φ ³ 为softmax激活函数，该激活函数可将模型输出映射为伪概率形式。

通过对目标函数的优化计算方式估计模型参数。可将目标函数定义为模型输出在训练集上的平均误差，通过该误差（目标函数）的最小化实现对模型的训练构造。具体地说，使用如下的式（2-19）作为目标函数，该目标函数依据模型对样本输出类别的概率来对错分样本施加一定惩罚，并将对所有错分样本所施加惩罚的均值作为模型输出在训练集上的平均误差。

其中， f _j （ X _i ）表示模型第 j 个输出结点对样本 X _i 的输出；为样本 X _i 所对应的标签向量 y _i 中第 j 个元素的取值。

代入数据并用共轭梯度算法优化上述目标函数，通过TersonFlow框架编程计算可得权重更新结果，表2-8为输入层到隐藏层的部分连接权重的部分计算数据，表2-9为隐藏层到输出层的部分连接权重的部分计算数据，取值保留小数点后两位。

表2-8 输入层到隐藏层的部分连接权重取值

表2-9 隐藏层到输出层的部分连接权重取值

取满足精度要求的第100000迭代得到的连接权重 w ^*1 ， w ^*2 和偏置 b ^*1 ， b ^*2 作为最终模型参数，由此得到所求的分类映射规则

使用所求模型对如表2-10所示的测试数据进行预测，得到表中最后一列的预测计算结果。与该表中实际种类值进行比较，可知预测结果均为正确。

表2-10 测试数据与计算结果比较

共轭梯度下降法可以看成是梯度下降法的一种改进策略，仅需一阶导数信息，并克服了梯度法迭代后期收敛速度较慢的不足，是一种比较有效的优化算法。

2.2.2 牛顿迭代法

牛顿迭代法（以下简称牛顿法）是一种快速迭代搜索算法，主要用于求函数零点，即求方程的根。该算法要求目标函数具有二阶连续偏导数，这是因为下一个近似值需要通过在现有近似值附近进行一阶泰勒展开来确定。由微积分理论可知，任意 n 阶可导的函数都可在任意点 X _k 处展开为幂函数形式，故可将具有连续二阶导数的函数 f （ X ）在点 X _k 处展开为

如果忽略上述二阶展开式的余项，则可将方程 f （ X ）=0近似表示为

若 f′ （ X _k ）≠0，则可由上式得到方程 f （ X ）=0的一个近似根，即 X = X _k - f （ X _k ） /f′ （ X _k ），将其作为新的近似根，记为 X _k ₊₁ ，则可得到如下迭代式

如果迭代初值 X ₀ 选择适当，则可通过上述迭代公式获得以方程 f （ X ）=0的根为极限的收敛序列{ X _k }。当 k 值足够大时，就可获得满足精度要求的方程近似根 X _k 。

我们知道，对于函数优化问题，目标函数的极值点为函数驻点，即为目标函数导函数的根，故可使用上述牛顿迭代法求解目标函数导函数的根，由此获得目标函数的极值点。为此令函数 f （ X ）为函数 F （ X ）的导函数，则当 f （ X ）=0时， F （ X ）在点 X 处取得极值。

假设目标函数 F （ X ）具有连续的三阶导数且 F″ （ X _k ）≠0，则同理可得到如下迭代式

适当选择初值 X ₀ 就可使上述迭代收敛到方程 F′ （ x ）=0的根，即目标函数 F （ x ）的极值点，故可用这种推广的牛顿法进行模型优化。然而，机器学习的代价函数或目标函数通常比较复杂，一般会包含多个模型参数，此时通过牛顿法进行模型参数更新就相当于求解多元目标函数的极小值点。故将上述一元函数的牛顿法进一步推广到多元函数的向量情形。

设 F （ X ）为三次可微的 n 元函数，则由多元函数泰勒展开式将其在 X _k 展开，得

其中， X =（ x ₁ ， x ₂ ，…， x _n ） ^T ；处的一阶导数，即

时的二阶导数，是一个Hesse矩阵，具体形式为

假定式（2-23）右边为n元正定二次凸函数且存在唯一的最优解，对上式求一阶微分，则可将近似地表示为

由上式可得的一个近似解，记为 X _k ₊₁ ，则得到如下迭代式

可将上式表示为迭代搜索通式 X _k ₊₁ = X _k + step _k P _k ，其中搜索步长 step _k 恒为1，搜索方向为。由于方向 P _k 为从 X _k 到二次函数极小点的方向，故亦称为从 X _k 发出的 牛顿方向 。由此可知，牛顿迭代法其实就是从迭代初始点开始，沿着牛顿方向且步长恒为1的迭代搜索算法。根据以上讨论，可得牛顿迭代法的具体计算步骤归纳如下：

（1）设定初始点 X ₀ 和终止准则，并置 X _k =0；

（2）求解点 X _k 对应的目标函数值、梯度和Hesse矩阵；

（3）根据确定搜索方向 P _k ；

（4）依迭代公式（2-26）确定下一个点 X _k ₊₁ ；

（5）判断是否满足终止条件，若满足，则输出解 X _k ₊₁ ；否则 k = k +1，转到步骤2。

【例题2.7】 试根据表2-11中的数据建立一个预测广告投入和净利润之间关系的机器学习模型，并使用该模型预测广告投入为2.1万元时所对应的净利润，要求模型优化过程采用牛顿迭代法。

表2-11 广告投入和销售额数据表（单位：万元）

【解】 画出表2-11中数据散点图如图2-4所示。由图2-4可知，可用二次函数拟合表中数据，故设机器学习模型为 y = w ₀ + w ₁ X + w ₂ X ² 。使用该模型构造目标函数并用误差平方和作为优化目标。为便于计算，将目标函数定义为误差平方和的1/2，即

其中， y ⁱ 为第 i 个数据的真实值；为对应的预测值。

代入数据求得目标函数具体表达式为

设置初始点 W ₀ =（ w ₀ ， w ₁ ， w ₂ ） ^T =（1，1，1） ^T ，求出分别为

因为目标函数为二次函数，故Hesse矩阵为常数。根据牛顿迭代法公式

求得 W ₁ =（-0.5559，5.313，-0.1448） ^T ，得到所求机器学习模型为

y =-0.5559 X ² +5.313 X -0.1448

该模型的函数图像如图2-5所示。将 X =2.1代入模型可得 y =8.560981，即广告投入为2.1万元时预测可获得的净利润为8.560981万元。

图2-4 广告投入和净利润数据散点图

图2-5 最终模型的函数图像

牛顿法的收敛速度很快，这是其他算法难以媲美的。究其原因是由于该算法每次迭代都会构造一个恰当的二次函数逼近目标函数，并使用从迭代点指向该二次函数极小点的方向来构造搜索方向。牛顿法的不足之处主要在于搜索方向构造困难，不仅需要计算梯度，还要计算Hesse矩阵及逆矩阵。为此介绍一种名为 拟牛顿法 的改进牛顿法。

拟牛顿法不仅收敛速度快，而且不用计算Hesse矩阵。首先，给出拟牛顿法的基本原理和实现步骤，然后介绍拟牛顿法中一种有效的具体实现算法，即DFP算法。

，，则可将牛顿法迭代式转化为如下形式

拟牛顿法的基本原理就是寻求一个近似矩阵来取代Hesse矩阵的逆矩阵。假设这个近似矩阵为 H _k = H （ X _k ），则迭代公式可转化为如下形式

显然，当近似矩阵 H _k 为单位阵时，则上式就是梯度法的迭代公式。为使得 H _k 能够更好地近似，需要其满足如下条件：

（1） H _k 应为对称正定矩阵，以确保算法朝着目标函数下降的方向搜索；

（2） H _k ₊₁ 和 H _k 之间应有一定关系，例如 H _k ₊₁ = H _k + Ψ _k ，其中 Ψ _k 为修正矩阵。

（3） H _k 应满足拟牛顿条件。

现在导出拟牛顿条件。假设目标函数 F （ X ）具有连续三阶导数，将 F （ X ）在 X = X _k ₊₁ 处进行二阶泰勒展开并略去余项，可得

则当 G _k ₊₁ 为正定矩阵时有。既然要用矩阵 H _k ₊₁ 来近似取代，那么 H _k ₊₁ 也应该满足

上式即为拟牛顿条件。

令Δ X _k = X _k ₊₁ - X _k ，Δ g _k = g _k ₊₁ - g _k ，则亦可将拟牛顿条件写成

拟牛顿法在一定程度上保留了牛顿法计算速度较快的优势，其具体实现还取决于 Ψ _k 的选取，不同的 Ψ _k 构成不同的具体算法。下面介绍一种名为DFP的常用拟牛顿法。DFP算法对拟牛顿法中修正公式的修正项进行如下优化，即设

其中， δ _k 和 τ _k 都是待定常数； Q _k 和 M _k 是 n 维向量。

由于上式应满足式（2-23），故有 Ψ _k Δ g _k =Δ X _k - H _k Δ g _k ，即有

令，则有

代回式（2-30），得到

此时，可将修正公式转化为

下面结合实例介绍DFP算法的具体实现过程。例如，对于优化问题取初始点 X ₀ =（1，1） ^T ，则有 g ₀ =（2，8） ^T 。根据公式进行计算，可得

由式（2-34），可得

从而算得搜索方向 P ₁ =- H ₁ g ₁ =（-1.49416，0.09340） ^T 。通过对下列目标函数的优化计算arg F （ X ₁ + step ₁ P ₁ ）获得搜索步长，得到 step ₁ =0.49423，由此算出 X ₂ =（0，0） ^T 。由于在点 X ₂ 处梯度为 0 ，故 X ₂ 即为最优解。