机器学习教程(微课视频版)最新章节_张旭东著

第3章
基本回归算法

本章讨论监督学习的一种类型——回归，首先介绍线性回归，然后推广到基函数回归。通过正则化可以有效地控制模型复杂度与泛化性的关系，本章将详细讨论回归中的正则化技术，介绍求解线性回归的批处理算法和常用的递推算法——随机梯度下降（stochastic gradient descent，SGD）算法。

3.1　线性回归

视频讲解

作为监督学习的一种，回归的数据集是带标注的，即形式为，这里 x _n 是样本的特征向量， y _n 是标注。为了处理方便，先假设 y _n 是标量，但可以很直接地推广到向量情况。在回归问题中，标注 y _n 是连续值，通过学习过程得到一个模型 = f （ x ； w ），该模型的输出是连续量。这里 f （·）表示一个数学函数，是预先选定的一类函数； w 表示函数的参数向量，需通过学习来确定； x 是输入的特征向量，分号“；”表示只有 x 是函数的变量， w 只是一个参数向量，这样的模型是一个参数化模型。用带标注的训练数据集通过学习过程确定参数向量 w ，则得到回归模型。模型一旦确定，对于一个新输入 x ，带入函数中可计算出回归输出。确定模型参数的过程称为学习过程或训练过程，带入新输入计算回归输出的过程称为预测或推断。

本章讨论最基本的一类回归模型，模型表达式 f （ x ； w ）是参数 w 的线性函数，称为线性回归模型。在线性回归模型中， f （ x ； w ）与 x 的关系可以是线性的，也可以是非线性的。当 f （ x ； w ）与 x 是线性关系时，这是一种最简单的情况，即基本线性回归模型。若通过一种变换函数 x ϕ （ x ）将特征向量 x 变换为基函数向量 ϕ （ x ），并用 ϕ （ x ）替代基本线性回归模型中的 x ，则回归输出为 w 的线性函数、 x 的非线性函数，称为线性基函数回归模型。本节讨论基本线性回归模型。

3.1.1　基本线性回归

设有满足独立同分布条件（I.I.D）的训练数据集

用通用符号 x =[ x ₁ ， x ₂ ，…， x _K ] ^T 表示 K 维特征向量（输入向量），若取数据集中一个指定样本的特征向量，则表示为 x _n =[ x _n ₁ ， x _n ₂ ，…， x _nK ] ^T 。为分析方便，假设标注值 y 是标量，后续可以推广到标注为向量的情况。

回归学习的目标是利用这个数据集，训练一个线性回归函数。定义线性回归函数为

其中

w =[ w ₀ ， w ₁ ， w ₂ ，…， w _K ] ^T （3.1.3）

为模型的权系数向量，而

是扩充特征向量，即在 x 向量的第一个元素之前，增加了哑元 x ₀ =1，对应系数 w ₀ 表示线性回归函数的偏置值。图3.1.1是线性回归学习的原理性示意图，这是一个最简单情况，即 x 只是一维的标量，图3.1.1中每一个点表示数据集中的一个样本，斜线是通过学习得到的回归模型，即相当于已确定了参数的式（3.1.2）。图3.1.2是线性回归的计算结构，图中的空心圆仅表示多元素的加法运算。

图3.1.1　线性回归学习的原理性示意图

图3.1.2　线性回归的计算结构

为了从数据集学习模型参数 w ，用式（3.1.2）逼近训练数据集。对于每个样本（ x _i ， y _i ），将特征向量带入回归函数计算得到的输出（ x _i ， w ）是对标注 y _i 的逼近，假设存在逼近误差 ε _i ，则有

为了得到问题的有效解，通常对误差 ε _i 给出一种概率假设。这里假设 ε _i 服从高斯分布，且均值为0，方差为，则 y _i 的概率密度函数表示为

注意，这里把 y _i 看作随机变量， x _i 看作已知量。

如果将所有样本的标注值表示为向量

y =[ y ₁ ， y ₂ ， y ₃ ，…， y _N ] ^T （3.1.7）

则由样本集的I.I.D性，得到 y 的联合概率密度函数为

由于标注集 y 是已知的，式（3.1.8）随 w 的变化是似然函数，令似然函数最大可求得 w 的解，这就是 w 的最大似然解，为了求解更方便，取对数似然函数为

若求 w 使得式（3.1.9）的对数似然函数最大，则等价于求如下和式最小：

即最大似然等价于 J （ w ）最小，这里 J （ w ）是训练集上回归函数（ x _i ， w ）与标注 y _i 的误差平方之和，式（3.1.10）求和号前的系数1/2只是为了后续计算方便。

对于求解回归模型的参数 w 来讲，误差平方和准则（等价于样本的均方误差准则）和高斯假设下的最大似然准则是一致的，故在后续讨论回归问题时，根据方便可使用其中之一。由式（3.1.5），重写误差平方和式（3.1.10）如下：

这里 y 如式（3.1.7）所示，为所有样本的标注向量， X 为数据矩阵，表示为

为求使式（3.1.11）最小的 w ，求 J （ w ）对 w 的导数，即梯度（标量函数对向量的梯度公式见附录B），该导数是 K +1维向量，即

令参数向量的解为 w _ML ，即当取 w = w _ML 时上式为 0 ，回归系数 w 满足方程

X ^T Xw _ML = X ^T y （3.1.13）

若 X ^T X 可逆，有

w _ML =（ X ^T X ） ^- ¹ X ^T y （3.1.14）

如果 X 满秩，即 X 的各列线性无关，（ X ^T X ） ^-1 存在，称

X ⁺ =（ X ^T X ） ^- ¹ X ^T （3.1.15）

为 X 的伪逆矩阵。得到权系数向量后，线性回归函数确定为

将 w _ML 的解（3.1.14）代入式（3.1.10）并除以样本数 N （同时省略系数1/2），得到数据集上的均方误差为

式（3.1.17）中，向量表示由训练集各样本特征向量带入式（3.1.16）得到的对标注集向量 y 的逼近，即

用式（3.1.14）表示的线性回归权系数向量的解，称为最小二乘（LS）解。若存在一个独立的测试集，也可计算测试集上的均方误差，若测试集误差也满足预定要求，则可确定式（3.1.16）为通过训练过程求得的线性回归函数。当给出一个新的特征向量 x ，将其代入式（3.1.16）可计算出相应的预测值（ x ， w ）。

在训练集上可对线性回归的解给出一个几何解释，重写式（3.1.18）如下

这里表示 X 的第 i 列（序号以0起始），若由 X 的各列向量为基张成一个向量子空间（称为数据子空间），则可将看作在数据子空间上的投影，投影系数由 w _ML 的各系数确定。

在训练集上，线性回归函数对每个标注值的逼近误差写成误差向量，即

这里 P 表示投影矩阵， P ^⊥ = I - P 表示误差投影矩阵。可以证明

即两者正交。可见是 y 在数据子空间的正交投影，误差向量 ε 与投影正交，因此 ε 的平方范数最小。图3.1.3给出了正交投影的示意图。

图3.1.3　正交投影示意

3.1.2　线性回归的递推学习

线性回归函数的学习是现代机器学习中最简单的算法之一。若给出式（3.1.1）表示的数据集，按式（3.1.12）的方式构成数据矩阵 X ，按式（3.1.7）构成标注向量 y ，则可通过解析表达式（3.1.14）计算得到线性回归模型的权系数向量 w _ML ，本质上该权向量是最大似然解。这种将数据集中所有数据写到数据矩阵，然后通过一次计算得到权系数向量的方法称为批处理。批处理需要集中进行运算，当问题的规模较大时，批处理需要集中处理大量运算，实际中可以考虑更经济的增量计算方法。

为方便，将数据集重写如下：

当特征向量 x _n 的维数 K 较大（例如 K >100）且数据集的规模较大（例如 N >10 ⁴ ）时，数据矩阵 X 相当大，直接计算式（3.1.14）需要集中处理大批量运算。一种替换方式是一次取出一个样本，构成递推计算，这种递推算法可在线实现。

将式（3.1.11）的误差和重新写为

这里 J _i （ w ）=（ y _i - w ^T ） ² 表示单个样本 i 的误差函数，即可以将总体误差函数分解为各样本误差函数之和。

为了导出一种递推算法，使用梯度下降算法，即假设从 w 的一个初始猜测值 w ^（0）开始，按照目标函数式（3.1.23）的负梯度方向不断递推，最终收敛到 w 的最优解。设已得到第 k 次递推的权系数向量为 w ^（ ^k ^），用该向量计算式（3.1.23）对 w 的梯度，即

注意，为了避免当样本数 N 太大时，以上和式的梯度太大，式（3.1.24）除以 N 以得到各样本对梯度贡献的均值。根据梯度下降算法，系数向量更新为

式（3.1.25）是权系数向量的递推算法，称为梯度算法。由于式（3.1.25）使用了所有样本的平均梯度进行运算，并不是逐个样本更新的在线算法。实际上，由式（3.1.24）可知，总的梯度是所有样本点的梯度平均，在每次更新时，若只选择一个样本对梯度的贡献，即只取

作为梯度进行权系数向量的更新，则有

由于样本值 y _i 、 x _i 取自随机分布的采样且具有随机性，因此式（3.1.26）表示的梯度也具有随机性，称为随机梯度。当样本量充分大时，式（3.1.24）中 N 项求平均的梯度逼近随机梯度的期望值，趋向一个确定性的梯度。因此，式（3.1.25）为梯度算法，式（3.1.27）的递推公式称为随机梯度下降（stochastic gradient descent，SGD）算法。针对线性回归问题的这种SGD算法也称为LMS（least-mean-squares）算法，这是最早使用随机梯度解决机器学习中优化问题的算法。在相当长的时间内，LMS算法在信号处理领域作为自适应滤波的经典算法，应用非常广泛。本质上回归学习和自适应滤波是等价的。

式（3.1.25）和式（3.1.27）中的参数 η >0是控制迭代步长的，称为学习率，用于控制学习过程中的收敛速度。 η 过大，递推算法不收敛， η 过小，收敛速度太慢，选择合适的 η 很关键。对于式（3.1.25）的梯度算法和式（3.1.27）的SGD算法，可以证明 η <1/ λ _max 可以保证收敛。这里 λ _max 是矩阵 X ^T X / N 的最大特征值，但由于计算 X ^T X / N 的特征值并不容易（若容易计算 X ^T X / N 的特征值，就可以直接用式（3.1.14）的批处理，不必用在线算法），实际上参数 η 的确定大多通过经验或实验来确定，或通过一些对特征值的近似估算确定一个参考值，再通过实验调整。实际学习率随迭代次数变化可记为 η _k ，关于随机梯度中学习率 η _k 满足的收敛条件等更一般性的讨论，将在第10章给出。