第3章
CHAPTER 3


基本回归算法








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




视频讲解


3.1线性回归


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


本章讨论最基本的一类回归模型，模型表达式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)的训练数据集


D={(x1,y1),(x2,y2),…,(xN,yN)}={(xn,yn)}Nn=1(3.1.1)


用通用符号x=［x1,x2,…,xK］T表示K维特征向量(输入向量)，若取数据集中一个指定样本的特征向量，则表示为xn=［xn1,xn2,…,xnK］T。为
分析方便，假设标注值y是标量，后续可以推广到标注为向量的情况。


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



y^(x,w)=w0+∑Kk=1wkxk=∑Kk=0wkxk=wTx-(3.1.2)


其中


w=［w0,w1,w2,…,wK］T(3.1.3)


为模型的权系数向量，而


x-=［1,x1,x2,…,xK］T(3.1.4)






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




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




图3.1.2线性回归的计算结构




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


yi= y^(xi,w)+εi=wTx-i+εi(3.1.5)


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



py(yi|w)=1(2πσ2ε)12exp
-12σ2ε(yi-y^(xi,w))2(3.1.6)


注意，这里把yi看作随机变量，xi看作已知量。


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


y=［y1,y2,y3,…,yN］T(3.1.7)


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


py(y|w)=∏Ni=1py(yi|w)=∏Ni=11(2πσ2ε)12exp
-12σ2ε(yi-y^(xi,w))2
=1(2πσ2ε)N2exp-12σ2ε∑Ni=1(yi-y^(xi,w))2
(3.1.8)


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


logpy(y|w)=-N2log(2πσ2ε)-12σ2ε∑Ni=1(yi-y^(xi,w))2(3.1.9)


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


J(w)=12∑Ni=1(yi-y^(xi,w))2(3.1.10)


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


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


J(w)=12∑Nn=1ε2i=12∑Ni=1［yi-y^(xi,w)］2
=12∑Ni=1(yi-wTx-i)2
=12(y-Xw)T(y-Xw)
=12‖y-Xw‖22(3.1.11)


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


X=x-T1
x-T2

x-TN=
1x11…x1K
1x21…x2K
…
1xN1…xNK(3.1.12)


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


J(w)w=12(y-Xw)T(y-Xw)w=-XTy+XTXw


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


XTXwML=XTy(3.1.13)


若XTX可逆，有


wML= (XTX)-1XTy (3.1.14)


如果X满秩，即X的各列线性无关，(XTX)-1存在，称


X+= (XTX)-1XT(3.1.15)


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


y^(x,w)=wTMLx-(3.1.16)


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


Jmin=1NJ(
wML)=1NεTε
=1N［y-X(XTX)-1XTy］T［y-X(XTX)-1XTy］
=1NyT［I-X(XTX)-1XT］Ty
=1NyT(y-XwML)=1NyT(y-y^)(3.1.17)


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


y^=［y^1,y^2,y^3,…,y^N］T

=［wTMLx-1,wTMLx-2,…,wTMLx-N］T=XwML(3.1.18)


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

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


y^=XwML=［
x～0x～1…x～K］wML=∑Ki=0
wML,ix～i(3.1.19)


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



图3.1.3正交投影示意


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


ε=y-y^=y-Py=P⊥y(3.1.20)


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


εTy^=0(3.1.21)



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


3.1.2线性回归的递推学习


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

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



D={(x1,y1),(x2,y2),…,(xN,yN)}={(xn,yn)}Nn=1(3.1.22)


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

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


J(w)=12∑N-1n=0ε2i=12∑Ni=1(yi-y^(xi,w))2
=12∑Ni=1(yi-wTx-i)2=∑Ni=1Ji(w)
(3.1.23)


这里Ji(w)= (yi-wTx-i)2表示单个样本i的误差函数，即可以将总体误差函数分解为各样本误差函数之和。


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


1NJ(w)ww=w(k)=1N∑Ni=1Ji(w)ww=w(k)
=-1N∑Ni=1(yi-w(k)Tx-i)x-i
(3.1.24)


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


w(k+1)=w(k)-η1NJ(w)ww=w(k)
=w(k)+ηN∑Ni=1(yi-w(k)Tx-i)x-i(3.1.25)


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


Ji(w)ww=w(k)=-(yi-w(k)Tx-i)x-i(3.1.26)


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


w(k+1)=w(k)-ηJi(w)ww=w(k)
=w(k)+η(yi-w(k)Tx-i)x-i
(3.1.27)


由于样本值yi、xi取自随机分布的采样且具有随机性，因此式(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是矩阵XTX/N的最大特征值，但由于计算XTX/N的特征值并不容易(若容易计算XTX/N的特征值，就可以直接用式(3.1.14)的批处理，不必用在线算法)，实际上
参数η的确定大多通过经验或实验来确定，或通过一些对特征值的近似估算确定一个参考值，再通过实验调整。实际
学习率随迭代次数变化可记为ηk，关于随机梯度中学习率ηk满足的收敛条件等更一般性的讨论，将在第10章
给出。

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


Dk+1={(xm,ym)}N1m=1(3.1.28)


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


w(k+1)=w(k)+η1N1∑N1m=1(ym-w(k)Tx-m)x-m(3.1.29)


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

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

3.1.3多输出线性回归

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


由于具有多个输出，样本集D={(xn,yn)}Nn=1中的标注yn是一个L维向量，这里L是回归的输出数目，即yn=［yn1,yn2,…,ynL］T，简单地，可将每个输出写为



y^i(x,wi)=∑Kk=0wikxk=wTix-(3.1.30)


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


W=［w1,w2,…,wL］(3.1.31)


则输出向量记为


y^(x,W)=［y^1(x,w1)，…，y^L(x,wL)］T=WTx-(3.1.32)


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


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



Y=［y1,y2,…,yN］T(3.1.33)


假设XTX可逆，得到权系数矩阵的解为


WML= (XTX)-1XTY(3.1.34)


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



wk,ML= (XTX)-1XTy～k(3.1.35)


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

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


y^(x,WML)=WTMLx-(3.1.36)


3.2正则化线性回归

在线性回归系数向量的解中，要求XTX可逆，实际上当XTX的条件数很大时，解的数值稳定性不好。一个矩阵的条件数为其最大特征值与最小特征值之比，设XTX的所有特征值记为{λ0,λ1,λ2,…,λK}，若特征值是按从大到小排列的，则其条件数为λ0/λK。矩阵XTX的行列式为
|XTX|=∏Ki=0λi，由于XTX是对称矩阵，其特征值λi≥0。若最小特征值λK=0则矩阵不可逆，若有一个到几个特征值很小，相应条件数很大，矩阵行列式值可能很小，根据矩阵求逆的格莱姆法则，则XTX的逆矩阵中有很多大的值，相应解向量可能范数很大且数值不稳定。


当X中的一些不同列互成比例时，XTX不满秩，这时XTX不可逆。当X的一些列相互近似成比例时，对应大的条件数，尽管此时严格讲XTX可逆，但当计算精度受限时数值稳定性不好。从以上的分析可见，X的不同列分别对应权系数向量的一个分量，当X的一些列成比例时，相当于对应的权系数有冗余，可以减少权系数数目，即减少模型的复杂性。当X的条件数很大时，相当于模型参数数目超过了必需的数目，而过多的参数其实更多地被用于拟合训练数据集中的噪声，使得泛化性能变差。因此，XTX条件数很大，对应的是模型的过拟合。解决过拟合的基本方法，一是增加数据集规模，二是删除一些冗余变量及相应权系数，三是采用正则化。这里介绍正则化方法。


如第1章所引出的结论，所谓正则化是在用误差平方和表示的目标函数中增加一项约束参数向量自身的量，一种常用的约束量选择为参数向量的范数平方，即‖w‖22=wTw，因此加了正则化约束的目标函数为



J(w)=12∑Nn=1ε2i+λ2∑Ki=1w2i=12∑Ni=1(yi-y^(xi,w))2+λ2∑Ki=1w2i
=12∑Ni=1(yi-wTx-i)2+λ2‖w‖22

=12(y-Xw)T(y-Xw)+λ2wTw(3.2.1)


这里λ是一个可选择的参数，用于控制误差项与参数向量范数约束项的作用。为求使式(3.2.1)最小的w值，计算


J(w)w=12(y-Xw)T(y-Xw)w+λ2wTww
=-XTy+2XTXw+λw


令w=wR时上式为0，得


(XTX+λI)wR=XTy(3.2.2)


求得参数向量的正则化解为


wR= (XTX+λI)-1XTy(3.2.3)


这里，解wR中用下标R表示正则化解。线性回归的正则化是一般性正则理论的一个特例。
Tikhonov正则化理论的泛函由两部分组成： 一项是经验代价函数，如式(3.1.11)中的误差平方和是一种经验代价函数，另一项是正则化项，它是约束系统结构的，在参数优化中用于约束参数向量的范数。每一种不同的正则化项代表设计的一种
“偏爱”，例如权系数范数平方作为正则化项是一种对小范数的权系数的偏爱，这种正则化称为“权衰减”(weigh decay)。

例3.2.1若给定一个数据集，
XTX的最大特征值为λmax=1.0，最小特征值为λmin=0.01，条件数T=λmax/λmin=100。若正则化参数取λ=0.1，则XTX+λI的最大特征值和最小特征值分别为λmax+λ=1.1和λmin+λ=0.11，因此条件数变为TR=1.1/0.11=10，对于线性回归来讲，正则化相当于改善了数据矩阵的条件数。


正如式(3.1.10)的误差平方和目标函数与最大似然等价，式(3.2.1)的正则化目标函数与贝叶斯框架下的MAP参数估计是等价的。若采用贝叶斯MAP估计，需要给出参数向量w的先验分布，假设w的各分量为均值为0、方差为σ2w且互相独立的高斯分布，则先验分布表示为


pw(w)=1(2πσ2w)K+12exp
-12σ2wwTw(3.2.4)


根据MAP估计，求w使得下式最大： 


p(w|y)∝p(y|w)pw(w)=
1(2πσ2ε)N2exp
-12σ2ε(y-Xw)T(y-Xw)1(2πσ2w)K+12exp-12σ2wwTw


对上式取对数可知，求上式最大等价于求w使得下式最小： 


J(w)=12σ2ε(y-Xw)T(y-Xw)+12σ2wwTw
=12σ2ε
(y-Xw)T(y-Xw)+σ2εσ2wwTw
(3.2.5)


令λ=σ2eσ2θ，则式(3.2.5)中方括号内的内容与式(3.2.1)相同，其参数向量w的解为式(3.2.3)。因此，可将正则化线性回归中权系数向量的先验分布看作高斯分布下的贝叶斯MAP估计。


用式(3.2.1)第2行对w求导，不难得到相应于式(3.2.3)解的梯度递推算法，这里只给出小批量SGD算法如下： 


w(k+1)=(1-λη)w(k)+η1N1∑N1m=1(ym-w(k)Tx-m)x-m(3.2.6)


当取N1=1时小批量退化成单样本SGD。与式(3.1.29)比，在w(k)前多了一个收缩因子(1-λη)，并增加了一个超参数λ。

这里可以得到一个基本的结论，若一类机器学习算法的目标函数是通过最大似然得到的，则任何一种对权系数向量施加先验分布pw(w)，从而建立在MAP意义下的贝叶斯扩展，均可以等价为一类正则化方法。


通过不同的正则化，可得到不同的针对特定偏爱的结果。例如，用1范数取代式(3.2.1)中的平方范数，则得到w具有稀疏特性(sparsity)的解。所谓稀疏特性是指w中的一些分量更偏向于取0值。这里w的1范数定义为其各分量的绝对值之和，即‖w‖1=∑Kk=1|wk|，故具有稀疏解的回归目标函数为


Js(w)=12(y-Xw)T(y-Xw)+λ2‖w‖1(3.2.7)


在一些特定情况下，稀疏约束可得到更有意义的结果，关于回归的稀疏学习可进一步参考文献［20］。


本节注释在正则化过程中，对系数向量作为约束(惩罚)条件时，一般不将偏置w0作为约束分量。在训练前，首先对输入向量xn的每个分量进行归一化和零均值化，w0由训练集标注的均值估计
，即w^0=1N∑Nn=1yn，故w0不参与式(3.2.1)的优化，对应式(3.2.3)的系数向量不包括偏置。本节
对应式(3.1.12)中X的定义内第1列的全“1”列被删除。

3.3线性基函数回归

到目前为止,所讨论的均是线性回归,输出是特征向量或其各分量的线性函数,即


y^(x,w)=∑Kk=0wkxk=wTx-(3.3.1)


其中扩充特征向量x-和权向量w的定义如式(3.1.4)和式(3.1.3)所示。为了将回归的输出与特征向量之间的关系扩展到更一般的非线性关系，可以通过定义一组非线性映射函数来实现。非线性映射函数的一般表示如下： 


i(x),i=0,1,2,…,M(3.3.2)


每个非线性映射函数i将K维向量x映射为一个标量值，其按次序排列为一个M+1维向量


(x)=［0(x),1(x),…,M(x)］T(3.3.3)


一般地，令0(x)=1为哑元。这里x|→(x)将K维向量映射为M维向量，称(x)为特征向量x的基函数向量。

定义权系数向量为


w=［w0,w1,…,wM］T


可以通过基函数向量定义新的回归模型为


y^(,w)=∑Mk=0wkk(x)=wT(x)(3.3.4)


在式(3.3.4)的模型中，输出与特征向量x的关系一般是非线性的，具体非线性形式由(x)的定义决定，但输出与权系数w的关系仍然是线性的，因此称这种模型为线性基函数回归模型。这里线性指的是回归输出与权系数是线性关系，与特征向量的非线性形式由基函数确定。


对于一个训练样本集D={(xn,yn)}Nn=1，取任意样本，由特征向量xn产生一个对应基函数向量(xn)，得到模型输出y^(n,w)=wT(xn)，注意，这里用到了简写符号n=(xn)。模型输出与标注的误差为


εn=yn-y^(n,w)=yn-wT(xn)(3.3.5)


与基本线性回归相比，只要用(xn)代替xn，其他是一致的，因此定义新的基函数数据矩阵为



Φ=T(x1)
T(x2)

T(xN)
=0(x1)1(x1)…M(x1)
0(x2)1(x2)…M(x2)
…
0(xN)1(xN)…M(xN)(3.3.6)


注意到，与基本线性回归问题相比，这里除了数据矩阵Φ由式(3.3.6)通过基函数映射进行计算外，一旦数据矩阵Φ确定了，由于待求参数向量w仍保持线性关系，需求解的问题与基本线性回归是一致的，故线性基函数回归系数向量的解为


wML= (ΦTΦ)-1ΦTy(3.3.7)


其中，y是标注值向量。注意到，与线性回归的不同主要表现在数据矩阵Φ中。对于线性回归，若特征向量xn是K维的，数据矩阵X是N×(K+1)维矩阵，且矩阵的每个元素直接来自训练集中一个特征向量的分量(包括了哑元)； 对于线性基函数回归，数据矩阵Φ是N×(M+1)维矩阵，即数据矩阵的列数为M+1，M由基函数数目确定。一般来讲，M≥K，基函数将特征向量x映射到更高维空间，并且数据矩阵Φ的每个元素需要通过相应映射函数计算得到，增加了计算量。一旦
计算得到数据矩阵Φ，线性基函数回归的求解问题和线性回归是一致的。


基函数的类型有很多，常用的有多项式基函数、高斯函数、正余弦函数集等。下面看几个例子。


例3.3.1讨论一个线性基函数回归的问题。设样本集的特征向量是一个三维向量，即


xn=［xn,1,xn,2,xn,3］T


设基函数向量为多项式形式，具体地，本例最高取二阶项，则


(xn)=［0(xn),1(xn),…,9(xn)］T
=［1,xn,1,xn,2,xn,3,x2n,1,x2n,2,x2n,3,xn,1xn,2,xn,2xn,3,xn,1xn,3］T


这里M=9，为了与线性回归区别，将线性基函数回归的权系数向量记为


w=［w,0,w,1,w,2,…,w,9］T


基函数回归的输出为


y^(n,w)
=∑9k=0w,kk(xn)
=w,0+w,1xn,1+w,2xn,2+w,3xn,3+w,4x2n,1+w,5x2n,2+
w,6x2n,3+w,7xn,1xn,2+w,8xn,2xn,3+w,9xn,1xn,3



假设数据集规模为N=50，则标注向量为


y=［y1,y2,…,y50］T


数据矩阵Φ为


Φ=
1,x1,1,x1,2,x1,3,x21,1,x21,2,x21,3,x1,1x1,2,x1,2x1,3,x1,1x1,3
1,x2,1,x2,2,x2,3,x22,1,x22,2,x22,3,x2,1x2,2,x2,2x2,3,x2,1x2,3

1,x50,1,x50,2,x50,3,x250,1,x250,2,x250,3,x50，1x50,2,x50,2x50,3,x50,1x50,3



Φ是一个50×10的数据矩阵，计算(ΦTΦ)-1需要求10×10方阵的逆矩阵。

注意到，对此问题若采用基本线性回归，则输出写为


y^(xn,w)=w0+w1xn,1+w2xn,2+w3xn,3


数据矩阵X是50×4的矩阵，则(XTX)-1的计算只需求4×4方阵的逆矩阵。另外，也需注意，计算Φ需要一定的计算量，尤其当Φ中存在复杂非线性函数时，附加计算量可能是相当可观的，而写出X不需要附加计算量。


例3.3.2正余弦类的基函数和高斯基函数的例子。与例3.3.1一样，设特征向量是一个三维向量，即


xn=［xn,1,xn,2,xn,3］T


定义正弦基函数向量的一个分量为


k(xn)=sin(i1πxn,1)sin(i2πxn,2)sin(i3πxn,3)


其中，0≤i1,i2,i3≤L取正整数； L是预先确定的一个整数或作为超参数通过交叉验证确定，本例中(xn)是(L+1)3维向量。

也可以定义高斯基函数的一个分量为


k(xn)=exp-‖xn-μk‖22σ2k


作为基函数使用时，高斯函数不需要归一化，每个基函数分量由中心矩μk确定，μk是预先确定的一组向量
，且与特征向量x同维度。例如，本例是三维情况，x的取值范围限定在三维正方体中，每维平均划分成L份，则三维正方体被划分成L3个等体积的小正方体，μk表示每个小立方体的中心点位置。σ2k控制了每个基函数的有效作用范围，一个简单的选择是各个基函数分量的σ2k参数共用一个值。


与基本的线性回归算法一样，线性基函数回归也可以通过随机梯度算法实现，同样，只要用(xn)代替xn，可将SGD算法直接用于基函数情况，基本的SGD算法可写为


w(n+1)=w(n)+η
［yi-w(n)T(xi)］(xi)(3.3.8)


其中，i为在权系数的第n+1次更新时用到的样本序号。同样，可以将小批量SGD算法直接应用于基函数情况。


可直接将3.2节讨论的正则化技术推广到基函数情况，也可直接将3.1.3节讨论的多输出回归推广到基函数情况，由于这两个推广都是非常直接的，请读者自己完成(正则化公式推广见习题)，此处不再赘述。


例3.3.3一个数值例子。本例在第1章用于说明概念，本章已经介绍了这个例子所使用的算法，故重新看一下这个例子。假设存在一个输入输出模型，其关系为


f(x)=11+exp(-5x)


这里x是标量，在区间x∈［-1,1］ 均匀采样产生输入样本集{xn}Nn=1，并通过关系式yn=f(xn)+εn产生标注值yn，其中εn~N(0,0.152)表示采样噪声。用带噪声的标注数据{xn,yn}Nn=1为f(x)建模。作为说明，首先设训练集样本数为N=10，f(x)和训练样本值如图3.3.1(a)所示。用同样的方法产生100个样本作为测试集。

使用基函数回归，选择多项式基函数向量为


(xn)=［0(xn),1(xn),…,M(xn)］T
=［1,xn,x2n,…,xMn］T


回归模型为



y^(n,w)=∑Mk=0wkk(xn)=∑Mk=0wkxkn



多项式阶数M是一个可选择的值。


首先选择M=3，利用式(3.3.7)计算权系数向量，得到的回归模型
如图3.3.1(b)所示。注意，为了比较方便，将训练样本和f(x)也画于同一图中。然后，选择M=9，结果
如图3.3.1(c)所示。比较图3.3.1(b)和图3.3.1(c)可见，M=3学习到的模型是合适的，尽管存在训练误差，但误差都在较小范围内； M=9的模型是过拟合的，尽管其训练误差为0，即学习的模型y^(,w)通过所有训练样本点，因此在所有样本点处yn=y^(n,w)，但其泛化性能很差，测试误差很大。原理上讲，M=9的模型更复杂，表达能力更强，但在有限训练集下，为使训练误差更小，将特别关注匹配标注值，而标注值中的噪声将起到很大的引导作用，尽管训练误差为零，但泛化性很差。

图3.3.1(d)所示为M为1~9时，训练误差和测试误差的变化关系。误差度量采用的是均方根误差，可以看到，随着模型复杂度升高，训练误差持续下降，但测试误差先下降再升高，表现为U形特性，尽管该图是针对这一具体例子得到的，但这个规律具有一般性。对于一个具体问题，在有限的训练集下，当模型复杂度高到一定程度，将出现过拟合，这时模型对训练集的表现优异，但泛化性能变差。对于本例，M取值为3~7比较合适，两个误差均较小。

如果选择了一个较复杂的模型，可以通过正则化降低过拟合。在本例中，取M=9时，通过正则化降低过拟合。取正则化参数为lnλ=-2(实际通过交叉验证确定)得到图3.3.1(e)的结果，与图3.3.1(c)比较，消除了过拟合问题。

图3.3.1例3.3.3的数值实验结果




在一般的机器学习中，增加数据可改善性能是一个基本原则，即具有大的有效数据集，等价
地，可用于训练的数据集增大。本例中若取训练集规模为N=150，M=9，不使用正则化，则训练得到的模型如图3.3.1(f)所示，由于训练数据规模明显增加，尽管选择M=9的复杂模型，并且没有使用正则化，学习得到的模型优于N=10情况下最好的结果。



对以上例子，选择不同的基函数集，误差性能会不同。例如，可选择傅里叶基函数做以上的实验，这个留作习题，有兴趣的读者可自行编程实验。对于许多实际应用，怎样选择合适的基函数集是一个重要、实际的问题。很多情况下，基函数的选择与所处理的问题密切相关，大多是启发式的选择。基函数方法与所谓核函数方法密切相关，其实任何一个基函数向量(x)都可以对应一个核函数。一个与基函数向量相对应的核函数定义为


κ(x,xn)=T(x)(xn)(3.3.9)


因此，核函数是一个具有两个变元的标量函数，具有许多良好的特性。直接利用核函数构造回归模型并利用误差的高斯假设求解该模型的一类方法称为“高斯过程”(在机器学习中，“高斯过程”有这样的专指，不同于随机过程中一般的高斯过程的概念，高斯过程也用于分类)。利用核函数构造支持向量机(SVM)算法则是核函数最重要的应用之一，在SVM框架下，既可以得到回归算法，也可以得到分类算法。有关核函数与SVM的详细讨论见第6章。

3.4本章小结

本章介绍了机器学习中一类基本的回归算法——线性回归。尽管线性回归比较简单，但仍可有效解决一些复杂度有限的问题。本章首先详细分析了基本线性回归算法，包括其最小二乘解、正则化方法、随机梯度求解和多输出问题。通过基函数映射，讨论了线性基函数回归，由不同的基函数，使得回归输出与输入特征向量之间得到各种非线性关系。


本章对求解线性回归问题给出了较为详细的介绍，实际上许多机器学习的著作都有对线性回归的较完整介绍，例如Bishop或Murphy的著作（见本书参考文献［6，33］）。本章仅提及了稀疏回归学习的基本概念，限于篇幅未能展开讨论，有关稀疏
回归学习可进一步参考Hastie等的著作（见本书参考文献［20］）
。

习题


1. 设x是一个标量，
共有3个(xi,yi)样本，即{(1,0.8),(1.5,0.9),(2,1.2)}，用这些数据训练一个简单的回归模型y^=w0+w1x，请计算模型参数。


2. 设x是个标量，
共有3个(xi,yi)样本，即{(1,0.8),(1.5,0.9),(2,1.2)}，用这些数据训练一个线性回归模型y^=w0+w1x，取λ=0.05，使用正则化方法计算模型参数。


3. 设线性回归模型的权系数具有以下广义高斯先验分布，即


p(w;α,σ2)=∏Kk=012βΓ(1/α)exp
-|wk|αβα


其中，β=σΓ(1/α)Γ(3/α)，Γ(·)是Gamma函数，有
Γ(α)=∫∞0tα-1e-tdt,α>0。证明： 利用贝叶斯MAP方法对参数向量w的估计等价于正则化目标函数


J(w)=12(y-Xw)T(y-Xw)+λ∑Ki=0|wi|α


4. 在基函数回归情况下，正则化约束的目标函数为


J(w)=12∑Ni=1(yi-wT(xi))2+λ2‖w‖22


证明： 线性基函数回归的正则化解为


wML= (ΦTΦ+λI)-1ΦTy


5*. 设x=［x1,x2］T是二维向量，定义函数
g(x)=sin(2πx1)sin(2πx2)，
产生一组训练样本，在x∈［0，1］×［0，1］范围均匀采样225个点，组成输入集{xn}225n=1，对每个xn，通过yn=g(xn)+νn产生标注值，这里νn~N(0,0.05)是独立高斯噪声，产生的训练样本为{xn,yn}225n=1，再独立但用同样模型产生100个样本{x*n,y*n}100n=1作为测试集。要求训练一个多项式模型y^(
,w)=∑Mk=0
wkk(x)=wT(x)，用于逼近数据存在的规律g(x)，基函数的每项取k(x)=xd11xd22,0≤d1+d2≤M的形式，M是指定的多项式阶数。

(1) 设M=3，用训练样本学习模型参数，用测试样本计算所训练模型与标注值之间的均方误差。

(2) 取M=1和M=5，重复(1)的内容，并比较结果。

(3) (选做)自行实验，取更大的M，使以上方法出现过拟合，计算过拟合时测试集均方误差。选择适当的λ，通过正则化克服过拟合问题，并给出正则化情况下的均方测试误差。


6*. 重做例3.3.3的数值例子，将基函数向量替换为傅里叶基，即


(x)=［0(x),1(x),…,M(x)］T
=［1,sin(πx),cos(πx),sin(2πx),cos(2πx),…,sin(Kπx),cos(Kπx)］T


其中，M=2K+1，取不同的M值，重复例3.3.3的各项实验内容。