人工智能算法学习笔记（二）——线性模型之线性回归
根据上一篇开篇的那个思维导图，还是从有监督机器学习开始，其中线性模型里的算法是大多数机器学习者最初接触的，那么就从它开始吧。
一、线性模型根据周志华老师的《机器学习》（俗称西瓜书）中的定义，线性模型是指其通过属性的线性组合来进行预测的函数：f(x)=w1∗x1+w2∗x2+w3∗x3+...+wd∗xd+bf(x)=w_1*x_1+w_2*x_2+w_3*x_3+...+w_d*x_d+bf(x)=w1∗x1+w2∗x2+w3∗x3+...+wd∗xd+b用一般的向量形式，则写成：f(x)=wT∗x+bf(x)=w^{T}*x+bf(x)=wT∗x+b，其中w=(w1,w2,...,wn)w=(w_1,w_2,...,w_n)w=(w1,w2,...,wn)在学到www和bbb之后，模型也就确定了。因此，我们对模型有了一个初步了解，就是说要用训练集学习出一条线（or更高维度的平面或者其他什么）作为模型函数，而究竟这条线是用来拟合数据还是分类数据，就要看模型是属于回归模型还是分类模型了。比如线性回归是属于回归模型的，而逻辑回归是属于分类模型的。我会分两章来分别记录这两种模型。
二、线性回归2.1线性回归概述线性回归是对给定的训练数据集进行线性拟合，从而找到一条能使得大多数样本点都尽可能被准确预测的拟合线，比如公式如下：f(xi)=wT∗xi+bf(x_i)=w^{T}*x_i+bf(xi)=wT∗xi+b，使得f(xi)≈yif(x_i)approxy_if(xi)≈yi二维下的线性回归是一条线，三维下的是一个平面，N维。。。（画不出来了）二维的线性回归模型
三维的线性回归模型
2.2线性回归的学习策略对于线性回归问题，我们最终的目的就是学习得到www和bbb，建立起这个模型公式，而目前最首要的问题就是：如何确定www和bbb最优就是接下来要学习的目标了。求解www和bbb的最优解，常用的有两种方法（我目前所学到的，以后如果遇到更多解法且消化了再补充记录），一种是最小二乘法，另一种是梯度下降法。
2.2.1最小二乘法接下来将通过一个贴近真实世界的例子来使用最小二乘法来学习到www和bbb.以估计房价为例吧，假设真实世界里房子的面积xxx和房价yyy的关系是线性关系，且真实世界存在无法估计的误差ϵepsilonϵ，由于真实世界影响房价的因素（也就是房屋特征）很多，所以本例中就列举两个因素（特征,本例中比如房屋的面积x1x_1x1和卧室的数量x2x_2x2），这样模型就是y=w0+w1∗x1+w2∗x2+ϵy=w_0+w_1*x_1+w_2*x_2+epsilony=w0+w1∗x1+w2∗x2+ϵ。w0w_0w0，w1w_1w1，w2w_2w2的值让误差的平方和ϵTϵepsilon^{T}epsilonϵTϵ最小。假如我们收集了五条数据：y1=w0+w1∗x11+w2∗x12+ϵ1y_1=w_0+w_1*x_{11}+w_2*x_{12}+epsilon_1y1=w0+w1∗x11+w2∗x12+ϵ1y2=w0+w1∗x21+w2∗x22+ϵ2y_2=w_0+w_1*x_{21}+w_2*x_{22}+epsilon_2y2=w0+w1∗x21+w2∗x22+ϵ2y3=w0+w1∗x31+w2∗x32+ϵ3y_3=w_0+w_1*x_{31}+w_2*x_{32}+epsilon_3y3=w0+w1∗x31+w2∗x32+ϵ3y4=w0+w1∗x41+w2∗x42+ϵ4y_4=w_0+w_1*x_{41}+w_2*x_{42}+epsilon_4y4=w0+w1∗x41+w2∗x42+ϵ4y5=w0+w1∗x51+w2∗x52+ϵ5y_5=w_0+w_1*x_{51}+w_2*x_{52}+epsilon_5y5=w0+w1∗x51+w2∗x52+ϵ5用矩阵将这组式子进行简化，如下所示：y=[y1y2y3y4y5]y=egin{bmatrix}y_1\y_2\y_3\y_4\y_5end{bmatrix}y=⎣⎢⎢⎢⎢⎡y1y2y3y4y5⎦⎥⎥⎥⎥⎤X=[1x11x121x21x221x31x321x41x421x51x52]X=egin{bmatrix}1&x_{11}&x_{12}\1&x_{21}&x_{22}\1&x_{31}&x_{32}\1&x_{41}&x_{42}\1&x_{51}&x_{52}end{bmatrix}X=⎣⎢⎢⎢⎢⎡11111x11x21x31x41x51x12x22x32x42x52⎦⎥⎥⎥⎥⎤w=[w0w1w2]w=egin{bmatrix}w_0\w_1\w_2end{bmatrix}w=⎣⎡w0w1w2⎦⎤ϵ=[ϵ1ϵ2ϵ3ϵ4ϵ5]epsilon=egin{bmatrix}epsilon_1\epsilon_2\epsilon_3\epsilon_4\epsilon_5end{bmatrix}ϵ=⎣⎢⎢⎢⎢⎡ϵ1ϵ2ϵ3ϵ4ϵ5⎦⎥⎥⎥⎥⎤那么y=Xw+ϵy=Xw+epsilony=Xw+ϵ，最小二乘法的思想就是要找到www让误差的平方和最小，即minw ϵTϵunderset{w}{min}:epsilon^{T}epsilonwminϵTϵ由于ϵ=y−Xwepsilon=y-Xwϵ=y−Xw，(AB)T=BTAT(AB)^{T}=B^{T}A^{T}(AB)T=BTAT且矩阵代数符合乘法分配律，因此：ϵTϵ =(y−Xw)T(y−Xw)epsilon^{T}epsilon:=(y-Xw)^T(y-Xw)ϵTϵ=(y−Xw)T(y−Xw)=(y−Xw)Ty−(y−Xw)TXwqquad=(y-Xw)^Ty-(y-Xw)^TXw=(y−Xw)Ty−(y−Xw)TXw=yTy−wTXTy−yTXw+wTXTXwqquad=y^Ty-w^TX^Ty-y^TXw+w^TX^TXw=yTy−wTXTy−yTXw+wTXTXw由于wTXTyw^TX^TywTXTy和yTXwy^TXwyTXw都是1∗11*11∗1的标量，对于标量aaa，aT=aa^T=aaT=a，因此wTXTy=(wTXTy)T=yTXww^TX^Ty=(w^TX^Ty)^T=y^TXwwTXTy=(wTXTy)T=yTXw那么ϵTϵ=yTy−2wTXTy+wTXTXwepsilon^Tepsilon=y^Ty-2w^TX^Ty+w^TX^TXwϵTϵ=yTy−2wTXTy+wTXTXw令ϵTϵepsilon^TepsilonϵTϵ的梯度为0即可求得最小值w^widehat{w}w，梯度就是导数的标量、向量或者矩阵形式，用▽ riangledown▽表示梯度。对于ϵTϵepsilon^TepsilonϵTϵ的梯度被定义为：
▽w=[∂ϵTϵ∂w0∂ϵTϵ∂w1∂ϵTϵ∂w2] riangledown_w=egin{bmatrix}frac{partialepsilon^Tepsilon}{partialw_0}\\frac{partialepsilon^Tepsilon}{partialw_1}\\frac{partialepsilon^Tepsilon}{partialw_2}end{bmatrix}▽w=⎣⎢⎢⎢⎢⎢⎡∂w0∂ϵTϵ∂w1∂ϵTϵ∂w2∂ϵTϵ⎦⎥⎥⎥⎥⎥⎤分别对w0,w1,w2w0,w1,w2w0,w1,w2求偏导，组成向量就是ϵTϵepsilon^TepsilonϵTϵ的梯度。那么如何求呢？可以将其分为三部分yTyy^TyyTy、−2wTXTy-2w^TX^Ty−2wTXTy和wTXTXww^TX^TXwwTXTXw分别对www求梯度。由于yTyy^TyyTy中并没有www，因此▽wyTy=0 riangledown_wy^Ty=0▽wyTy=0;在求另外两项梯度前，先看如下情况：情况1：求▽wwTa,a=[a1a2a3] riangledown_ww^Ta,a=egin{bmatrix}a1\a2\a3end{bmatrix}▽wwTa,a=⎣⎡a1a2a3⎦⎤
用标量形式表示wTa=w0a0+w1a1+w2a2w^Ta=w_0a_0+w_1a_1+w_2a_2wTa=w0a0+w1a1+w2a2，可得▽wwTa=[∂wTa∂w0∂wTa∂w1∂wTa∂w2]=[a0a1a2]=a riangledown_ww^Ta=egin{bmatrix}frac{partialw^Ta}{partialw_0}\\frac{partialw^Ta}{partialw_1}\\frac{partialw^Ta}{partialw_2}end{bmatrix}=egin{bmatrix}a0\a1\a2end{bmatrix}=a▽wwTa=⎣⎢⎢⎢⎢⎢⎡∂w0∂wTa∂w1∂wTa∂w2∂wTa⎦⎥⎥⎥⎥⎥⎤=⎣⎡a0a1a2⎦⎤=a因此ϵTϵepsilon^TepsilonϵTϵ中−2wTXTy-2w^TX^Ty−2wTXTy的梯度是−2XTy-2X^Ty−2XTy
情况2：对于▽wwTAw riangledown_ww^TAw▽wwTAw，AAA必须为对称矩阵，即：A=[a11a12a13a12a22a23a13a23a33]A=egin{bmatrix}a_{11}&a_{12}&a_{13}\a_{12}&a_{22}&a_{23}\a_{13}&a_{23}&a_{33}end{bmatrix}A=⎣⎡a11a12a13a12a22a23a13a23a33⎦⎤可得wTAw=[w0w1w2][a11a12a13a12a22a23a13a23a33][w0w1w2]=[w0w1w2][a11w0+a12w1+a13w2a12w0+a22w1+a23w2a13w0+a23w1+a33w2]=a11w02+a22w12+a33w22+2a12w0w1+2a13w0w2+2a23w1w2w^TAw=egin{bmatrix}w_0&w_1&w_2end{bmatrix}egin{bmatrix}a_{11}&a_{12}&a_{13}\a_{12}&a_{22}&a_{23}\a_{13}&a_{23}&a_{33}end{bmatrix}egin{bmatrix}w_0\\w_1\\w_2end{bmatrix}\qquadquad=egin{bmatrix}w_0&w_1&w_2end{bmatrix}egin{bmatrix}a_{11}w_0+a_{12}w_1+a_{13}w_2\a_{12}w_0+a_{22}w_1+a_{23}w_2\a_{13}w_0+a_{23}w_1+a_{33}w_2end{bmatrix}\qquadquad=a_{11}w_0^2+a_{22}w_1^2+a_{33}w_2^2+2a_{12}w_0w_1+2a_{13}w_0w_2+2a_{23}w_1w_2wTAw=[w0w1w2]⎣⎡a11a12a13a12a22a23a13a23a33⎦⎤⎣⎢⎢⎢⎢⎡w0w1w2⎦⎥⎥⎥⎥⎤=[w0w1w2]⎣⎡a11w0+a12w1+a13w2a12w0+a22w1+a23w2a13w0+a23w1+a33w2⎦⎤=a11w02+a22w12+a33w22+2a12w0w1+2a13w0w2+2a23w1w2因此，▽wwTAw=[∂wTAw∂w0∂wTAw∂w1∂wTAw∂w2]=[2a11w0+2a12w1+2a13w22a12w0+2a22w1+2a23w22a13w0+2a23w1+2a33w2]=2Aw riangledown_ww^TAw=egin{bmatrix}frac{partialw^TAw}{partialw0}\\frac{partialw^TAw}{partialw1}\\frac{partialw^TAw}{partialw2}end{bmatrix}=egin{bmatrix}2a_{11}w_0+2a_{12}w_1+2a_{13}w_2\\2a_{12}w_0+2a_{22}w_1+2a_{23}w_2\\2a_{13}w_0+2a_{23}w_1+2a_{33}w_2end{bmatrix}=2Aw▽wwTAw=⎣⎢⎢⎢⎢⎢⎡∂w0∂wTAw∂w1∂wTAw∂w2∂wTAw⎦⎥⎥⎥⎥⎥⎤=⎣⎢⎢⎢⎢⎡2a11w0+2a12w1+2a13w22a12w0+2a22w1+2a23w22a13w0+2a23w1+2a33w2⎦⎥⎥⎥⎥⎤=2Aw
对于ϵTϵepsilon^TepsilonϵTϵ中的wTXTXww^TX^TXwwTXTXw，无论有多少条数据，XTXX^TXXTX都是3×33 imes33×3对称矩阵，因此可得wTXTXww^TX^TXwwTXTXw的梯度是2XTXw2X^TXw2XTXw。
由以上推导可得梯度是：▽wϵTϵ=[∂ϵTϵ∂w0∂ϵTϵ∂w1∂ϵTϵ∂w0]=2XTXw−2XTy riangledown_wepsilon^Tepsilon=egin{bmatrix}frac{partialepsilon^Tepsilon}{partialw_0}\\frac{partialepsilon^Tepsilon}{partialw_1}\\frac{partialepsilon^Tepsilon}{partialw_0}\\end{bmatrix}=2X^TXw-2X^Ty▽wϵTϵ=⎣⎢⎢⎢⎢⎢⎢⎢⎡∂w0∂ϵTϵ∂w1∂ϵTϵ∂w0∂ϵTϵ⎦⎥⎥⎥⎥⎥⎥⎥⎤=2XTXw−2XTy
当ϵTϵepsilon^TepsilonϵTϵ最小时梯度为0，梯度上的各项偏导数为0，由此可得该位置的w^hat{w}w^就是所求的www2XTXw^−2XTy=02X^TXhat{w}-2X^Ty=02XTXw^−2XTy=0XTXw^=XTyX^TXhat{w}=X^TyXTXw^=XTyw^=(XTX)−1XTyhat{w}=left(X^TX ight)^{-1}X^Tyw^=(XTX)−1XTy
2.2.2梯度下降法前文的最小二乘法直接对梯度求导找出极值来求线性回归损失函数的最优解,它为非迭代法。本节将记录一种新的方法来求损失函数的极值：梯度下降法（GradientDescendent,GD），梯度下降法为最优化算法通常用于求解函数的极值，梯度下降法为迭代法，给定一个β在梯度下降最快方向调整β，经过N次迭代后找到极值，也就是局部最小值或全局最小值。来个梯度下降核心算法直接的表达：Repeat{θj:=θj−α∂J(θ0,θ1,...,θn)∂θj}Repeatleft{\ heta_{j}:= heta_{j}-alphafrac{partialJleft( heta_{0}, heta_{1},..., heta_{n} ight)}{partial heta_{j}}\ ight}Repeat{θj:=θj−α∂θj∂J(θ0,θ1,...,θn)}可以看到，针对每一个系数，都采用对其取偏导数，然后使用一个合适的学习率参数αalphaα进行相乘并递减，重复这个过程，直到代价函数收敛到某个范围内。
随机梯度下降和批量梯度下降是两种迭代求解思路。对于如下：h(θ)=∑j=0nθjxjhleft( heta ight)=sum_{j=0}^{n} heta_{j}x_{j}h(θ)=∑j=0nθjxjJ(θ)=12m∑i=1m(yi−hθ(xi))2Jleft( heta ight)=frac{1}{2m}sum_{i=1}^{m}left(y^{i}-h_{ heta}left(x^{i} ight) ight)^{2}J(θ)=2m1∑i=1m(yi−hθ(xi))2h(θ)hleft( heta ight)h(θ)是要拟合的函数，J(θ)Jleft( heta ight)J(θ)是损失函数，θ hetaθ是参数，要迭代求解的值，θ hetaθ求解出来了，那么最终要拟合的函数h(θ)hleft( heta ight)h(θ)就出来了。其中m是训练集的记录条数，i是参数的个数。
批量梯度下降（BGD）求解思路如下：
将J(θ)Jleft( heta ight)J(θ)对θ hetaθ求偏导，得到每个θ hetaθ对应的梯度，∂J(θ)∂θj=−1m∑i=1m(yi−hθ(xi))xjifrac{partialJleft( heta ight)}{partial heta_j}=-frac{1}{m}sum_{i=1}^{m}left(y^i-h_ hetaleft(x^i ight) ight)x_j^i∂θj∂J(θ)=−m1∑i=1m(yi−hθ(xi))xji由于是要最小化风险函数，所以按每个参数θ hetaθ的梯度负方向，来更新每个θ hetaθθj=θj−1m∑i=1m(yi−hθ(xi))xji heta_j= heta_j-frac{1}{m}sum_{i=1}^{m}left(y^i-h_ hetaleft(x^i ight) ight)x_j^iθj=θj−m1∑i=1m(yi−hθ(xi))xji从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度！！！因此，就引入了另外一种方法，随机梯度下降。PS：批量梯度下降每次学习都是用整个训练集，因此其优点在于每次更新都会朝着正确的方向进行，最后能够保证收敛于极值点（凸函数收敛于全局极值点非凸函数可能会收敛于局部极值点），但是其缺点在于每次学习时间过长，并且如果训练集很大以至于需要消耗大量的内存，并且全量梯度下降不能进行在线模型参数更新。随机梯度下降（SGD）求解思路如下：
上面的风险函数可以写成如下形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：J(θ)=1m∑i=1m12(yi−hθ(xi))2=1m∑i=1mcost(θ,(xi,yi))Jleft( heta ight)=frac{1}{m}sum_{i=1}^{m}frac{1}{2}left(y^i-h_ hetaleft(x^i ight) ight)^2=frac{1}{m}sum_{i=1}^{m}costleft( heta,left(x^i,y^i ight) ight)J(θ)=m1∑i=1m21(yi−hθ(xi))2=m1∑i=1mcost(θ,(xi,yi))cost(θ,(xi,yi))=12(yi−hθ(xi))2costleft( heta,left(x^i,y^i ight) ight)=frac{1}{2}left(y^i-h_ hetaleft(x^i ight) ight)^2cost(θ,(xi,yi))=21(yi−hθ(xi))2每个样本的损失函数对θ hetaθ求偏导得到对应梯度，来更新θ hetaθθj=θj+(yi−hθ(xi))xji heta_j= heta_j+left(y^i-h_ hetaleft(x^i ight) ight)x_j^iθj=θj+(yi−hθ(xi))xji随机梯度下降是通过每个样本来迭代更新一次，如果样本很大的情况（如几十万），那么可能只用其中的几万或者几千条的样本，就已经将θ hetaθ迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。两者区别
批量梯度下降——最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小。随机梯度下降——最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体方向是向全局最优解的，最终的结果往往是在全局最优解附近。未完待续。。。