购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

第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 1 x 2 ,…, x K ] T 表示 K 维特征向量(输入向量),若取数据集中一个指定样本的特征向量,则表示为 x n =[ x n 1 x n 2 ,…, x nK ] T 。为分析方便,假设标注值 y 是标量,后续可以推广到标注为向量的情况。

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

其中

w =[ w 0 w 1 w 2 ,…, w K ] T (3.1.3)

为模型的权系数向量,而

是扩充特征向量,即在 x 向量的第一个元素之前,增加了哑元 x 0 =1,对应系数 w 0 表示线性回归函数的偏置值。图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 1 y 2 y 3 ,…, 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 - 1 X T y (3.1.14)

如果 X 满秩,即 X 的各列线性无关,( X T X -1 存在,称

X + =( X T X - 1 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 4 )时,数据矩阵 X 相当大,直接计算式(3.1.14)需要集中处理大批量运算。一种替换方式是一次取出一个样本,构成递推计算,这种递推算法可在线实现。

将式(3.1.11)的误差和重新写为

这里 J i w )=( y i - w T 2 表示单个样本 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章给出。

现代机器学习领域经常使用小批量SGD算法,这种算法是式(3.1.25)和式(3.1.27)的一个折中,即从式(3.1.22)的数据集中随机抽取一小批量样本,重新记为

这里,小批量样本 D k +1 中的下标表示将用于计算 w k +1) ,小批量样本的元素 y m 的下标是在该集合中重新标号的,它随机抽取于大数据集。 N 1 N 是小样本集的样本数。小批量SGD算法如下

这里为了使小批量SGD算法与式(3.1.27)的单样本SGD算法的学习率 η 保持同量级,对小批量各样本的梯度进行了平均,即除以 N 1

注意,在式(3.1.27)的算法中,迭代序号 k 和所用的样本序号 i 并不一致。实际中,在第 k 次迭代时,可随机地从样本集抽取一个样本,即样本一般不是顺序使用的,一些样本可能被重用,小批量梯度算法也是如此。

3.1.3 多输出线性回归

前面介绍回归算法时为了表述简单和理解上的直观性,只给出了输出是标量的情况,即所关注的问题只有一个输出值,实际中很多回归问题可能有多个输出。例如,利用同一组经济数据预测几个同行业的股票指数,前面讨论的标量回归问题可很方便地推广到具有多个输出的情况。

由于具有多个输出,样本集 中的标注 y n 是一个 L 维向量,这里 L 是回归的输出数目,即 y n =[ y n 1 y n 2 ,…, y nL ] T ,简单地,可将每个输出写为

将各输出的权向量作为权矩阵的一列,即

W =[ w 1 w 2 ,…, w L ] (3.1.31)

则输出向量记为

为了通过样本集训练得到权系数矩阵 W ,只需要推广式(3.1.11)针对标量输出的目标函数到向量输出情况,这里不再给出详细的推导过程,只给出相应结果。

对于向量输出情况,数据矩阵 X 仍由式(3.1.12)定义,相应的标注值由向量变为矩阵,故标注矩阵表示为

Y =[ y 1 y 2 ,…, y N ] T (3.1.33)

假设 X T X 可逆,得到权系数矩阵的解为

W ML =( X T X - 1 X T Y (3.1.34)

这个解的形式与式(3.1.14)基本一致,只是用标注矩阵替代标注向量。若用 表示 Y 的第 k 列,则输出的第 k 个分量的权系数向量为

在多分量回归中,每个分量的权系数矩阵与标准单分量回归一致,仅由 Y 的一列可求得,这种互相无耦合的解是因为假设了各分量的误差满足独立高斯假设的相应结果。

由于已经得到了最优的权系数矩阵,若给出一个新的特征向量 x ,则多分量回归的输出为 erwrjVeEELhp8WSMZ1imXFlP/j1zOjYPlokIWQEOmkauCbO0Fes6k3gkisi4xkj/

点击中间区域
呼出菜单
上一章
目录
下一章
×