线性回归

即线性拟合，给定N个样本数据（x1,y1）,(x2,y2)....(xN,yN)<script type="math/tex" id="MathJax-Element-6887">（x_1,y_1）,(x_2,y_2)....(x_N,y_N)</script>当中xi<script type="math/tex" id="MathJax-Element-6888">x_i</script>为输入向量，yi<script type="math/tex" id="MathJax-Element-6889">y_i</script>表示目标值，即想要预測的值。採用曲线拟合方式，找到最佳的函数曲线来逼近原始数据。通过使得代价函数最小来决定函数參数值。
採用斯坦福大学公开课的样例：假如一套房子的价格仅仅考虑由房屋面积(Living area)与卧室数目(bedrooms)两个因素决定，如今拿到手有m个样本，例如以下图所看到的。

此例中。输入x=(x1,x2)<script type="math/tex" id="MathJax-Element-6890">x=(x_1,x_2)</script>为2维向量。分别相应房屋面积和卧室数目,y<script type="math/tex" id="MathJax-Element-6891">y</script>相应价格。如今想依据上述样本数据，预測新的输入x(k)<script type="math/tex" id="MathJax-Element-6892">x^{(k)}</script>相应的y(k)<script type="math/tex" id="MathJax-Element-6893">y^{(k)}</script>。

我们採用x<script type="math/tex" id="MathJax-Element-6894">x</script>的线性函数hθ(x)=θ0+θ1x1+θ2x2<script type="math/tex" id="MathJax-Element-6895">h_θ(x)=θ_0+θ_1x_1+θ_2x_2</script>来近似y<script type="math/tex" id="MathJax-Element-6896">y</script>值，当中θ0<script type="math/tex" id="MathJax-Element-6897">θ_0</script>为偏移量。

令x0=1<script type="math/tex" id="MathJax-Element-6898">x_0=1</script>,简写为hθ(x)=θTx<script type="math/tex" id="MathJax-Element-6899">h_θ(x)=θ^Tx</script>。

如今的问题是怎样选择θ<script type="math/tex" id="MathJax-Element-6900">θ</script>的值，来使得hθ(x(i))<script type="math/tex" id="MathJax-Element-6901">h_θ(x^{(i)})</script>最大程度接近y(i)<script type="math/tex" id="MathJax-Element-6902">y^{(i)}</script>值。

最小二乘代价函数

採用最小二乘法定义代价函数J(θ)=12∑mi=1(hθ(x(i))?y(i))2<script type="math/tex" id="MathJax-Element-790">J(θ)=\frac12∑_{i=1}^m(h_θ(x^{(i)})?y^{(i)})^2</script>,表示每一个样本的预測值与真实值得差值平方的累加和。
如今问题转化为代价函数J(θ)<script type="math/tex" id="MathJax-Element-791">J(θ)</script>最小相应的θ<script type="math/tex" id="MathJax-Element-792">θ</script>值。当中因子12<script type="math/tex" id="MathJax-Element-793">\frac12</script>是为了后面的计算方便。

梯度下降：

梯度下降的思想是沿着函数负梯度方向，不断更新θ<script type="math/tex" id="MathJax-Element-6903">θ</script>值，每次更新一次。函数值下降一次。算法例如以下：

1.初始化θ<script type="math/tex" id="MathJax-Element-6904">θ</script>值；
2.更新θ<script type="math/tex" id="MathJax-Element-6905">θ</script>值，使得J(θ)<script type="math/tex" id="MathJax-Element-6906">J(θ)</script>值更小 ：θ:=θ?α?θJ(θ)<script type="math/tex" id="MathJax-Element-6907"> θ:=θ?α?_θJ(θ)</script>。
3.假设J(θ)<script type="math/tex" id="MathJax-Element-6908">J(θ)</script>值能够继续降低，返回第2步；

当中α<script type="math/tex" id="MathJax-Element-6909">α</script>称为学习率，决定着每一次迭代跨越的步长。θT=(θ0,θ1,θ2)<script type="math/tex" id="MathJax-Element-6910">θ^T=(θ_0,θ_1,θ_2)</script>为一个三维向量，梯度偏导数计算方法：

对于单个样本数据，则更新方法为θj:=θj?α(hθ(x)?y)xj<script type="math/tex" id="MathJax-Element-6911">θ_j:=θ_j?α(h_θ(x)?y)x_j</script>

关于梯度下降与梯度上升：
注意到，我们上述求偏导数得到(hθ(x)?y)xj<script type="math/tex" id="MathJax-Element-6912">(h_θ(x)?y)x_j</script>，此方向为梯度上升方法，因为我们要求J(θ)<script type="math/tex" id="MathJax-Element-6913">J(θ)</script>的最小值，所以应沿着负梯度方向，即θj:=θj?α(hθ(x)?y)xj<script type="math/tex" id="MathJax-Element-6914">θ_j:=θ_j?α(h_θ(x)?y)x_j</script>，若提取负号，就变为θj:=θj+α(y?hθ(x))xj<script type="math/tex" id="MathJax-Element-6915">θj:=θj+α(y?h_θ(x))x_j</script>,尽管变为正号，仍然是沿着负梯度方向，仅仅是公式形式变了。在《机器学习实战》中。就採用的后一种形式θj:=θj+α(y?hθ(x))xj<script type="math/tex" id="MathJax-Element-6916">θ_j:=θ_j+α(y?h_θ(x))x_j</script>，在那本书里被称为梯度上升，实际上仍然为负梯度方向。

1.批梯度下降(batch gradient descent)

上述为批梯度下降θ<script type="math/tex" id="MathJax-Element-6917">θ</script>值得更新算法，每一次更新θ<script type="math/tex" id="MathJax-Element-6918">θ</script>值，都须要计算整个样本集数据。即综合全局梯度方向算出下一步最优梯度方向。

在学习率α<script type="math/tex" id="MathJax-Element-6919">α</script>比較小的情况下。上述算法必定收敛。同一时候因为J(θ)<script type="math/tex" id="MathJax-Element-6920">J(θ)</script>为凸二次函数，局部最优值，即全局最优值。
可是对于样本集非常大的情况下，此种算法必定导致效率非常低，因为每一次对θ<script type="math/tex" id="MathJax-Element-6921">θ</script>的更新，都需计算每一个样本的预測值与真实值的差。

2.随机梯度下降（stochastic gradient descent）

算法的长处是，遍历整个数据集。每一次更新θ<script type="math/tex" id="MathJax-Element-6922">θ</script>的值仅仅计算单个样本数据的梯度方向。可是此种算法不一定收敛到最小值。可能会在最小值附近震荡。在数据量非常大的情况下。仍建议採用随机梯度下降算法。

3.mini-batch梯度下降
把批梯度下降与随机梯度下降算法折中。即每次採用若干样本的梯度综合，更新θ<script type="math/tex" id="MathJax-Element-6923">θ</script>的值，被称为mini-batch梯度下降。
θj=θj+α∑n(y(i)?hθ(x(i)))<script type="math/tex" id="MathJax-Element-6924">θ_j=θ_j+α∑_n(y^{(i)}?h_θ(x^{(i)})) </script>(for every j)

解析式求解

改写J(θ)<script type="math/tex" id="MathJax-Element-2756">J(θ)</script>成矩阵的形式：
J(θ)=12∑mi=1(hθ(x(i))?y(i))2=12(Xθ?Y)T(Xθ?Y)<script type="math/tex" id="MathJax-Element-2757">J(θ)=\frac12∑_{i=1}^m(h_θ(x^{(i)})?y^{(i)})^2=\frac12(Xθ?Y)^T(Xθ?Y)</script>。当中X为m×n,θ<script type="math/tex" id="MathJax-Element-2758">θ</script>为n×1，Y=(y(1),y(2)...y(m))T<script type="math/tex" id="MathJax-Element-2759">Y=(y^{(1)},y^{(2)}...y^{(m)})^T </script>
令?θJ(θ)=?θ12(θTXTXθ?θTXTY?YTXθ+YTY)=12(2XTXθ?2XTY)=XTXθ?XTY=0<script type="math/tex" id="MathJax-Element-2760">?_θJ(θ)=?θ\frac12(θ^TX^TXθ?θ^TX^TY?Y^TXθ+Y^TY)=\frac12(2X^TXθ?2X^TY)=X^TXθ?X^TY=0 </script>
解得θ=(XTX)?1XTY<script type="math/tex" id="MathJax-Element-2761">θ=(X^TX)^{?1}X^TY</script>;
当XTX<script type="math/tex" id="MathJax-Element-2762">X^TX</script>为神秘矩阵时。通常选择在原始函数中加入正则项，确保矩阵非神秘。

一种简单的正则化项为：E(θ)=12θTθ<script type="math/tex" id="MathJax-Element-2763">E(θ)=\frac12θ^Tθ</script>, 原始目表函数变为J(θ)+λE(θ)=12∑mi=1(hθ(x(i))?y(i))2+λ2θTθ<script type="math/tex" id="MathJax-Element-2764">J(θ)+λE(θ)=\frac12∑^m_{i=1}(h_θ(x^{(i)})?y^{(i)})^2+\fracλ2θ^Tθ</script>,当中λ<script type="math/tex" id="MathJax-Element-2765">λ</script>为调和因子,对目标函数求导并令为0，解得θ=(XTX+λI)?1XTY<script type="math/tex" id="MathJax-Element-2766">θ=(X^TX+λI)^{?1}X^TY</script>

最小二乘法的概率解释与几何解释

1.概率解释

假定原始拟合函数为：y(i)=θTx(i)+?(i)<script type="math/tex" id="MathJax-Element-7269">y^{(i)}=θ^Tx^{(i)}+?^{(i)}</script>。即每一个样本受到一个噪声?(i)<script type="math/tex" id="MathJax-Element-7270">?^{(i)}</script>因子的影响，同一时候噪声分别服从正态高斯分布，即均值为0，方差为σ2<script type="math/tex" id="MathJax-Element-7271">σ^2</script>。

?(i)<script type="math/tex" id="MathJax-Element-7272">?(i)</script>~N(0,σ2)<script type="math/tex" id="MathJax-Element-7273">N(0,σ^2) </script>
?P(?(i))=12π√σexp(?(?(i))22σ2)<script type="math/tex" id="MathJax-Element-7274">\Longrightarrow P(?^{(i)})=\frac1{\sqrt{2π}σ}exp(?\frac{(?^{(i)})^2}{2σ^2})</script>
?P(y(i)|x(i);θ)=12π√σexp(?(y(i)?θTx(i))22σ2)<script type="math/tex" id="MathJax-Element-7275">\Longrightarrow P(y^{(i)}|x^{(i)};θ)=\frac1{\sqrt{2π}σ}exp(?\frac{(y^{(i)}-\theta^Tx^{(i)})^2}{2σ^2}) </script>
写法P(y(i)|x(i);θ)<script type="math/tex" id="MathJax-Element-7276">P(y^{(i)}|x^{(i)};θ)</script>表示在參数θ<script type="math/tex" id="MathJax-Element-7277">θ</script>的情况下，给定x(i)。y(i)<script type="math/tex" id="MathJax-Element-7278">x^{(i)}。y^{(i)}</script>服从的分布。

因为假定噪声因子之间?(i)<script type="math/tex" id="MathJax-Element-7279">?^{(i)}</script>为独立同分布，写出其似然函数为。如今的目的是採用最大释然预计得方法计算出最优的參数θ<script type="math/tex" id="MathJax-Element-7280">θ</script>值

改成对数释然函数为：

我们目的要最大化释然函数。即要求最小化第二项 12∑mi=1(hθ(x(i))?y(i))2<script type="math/tex" id="MathJax-Element-7281">\frac12∑^m_{i=1}(h_θ(x^{(i)})?y(i))^2</script>。此即我们的最小二乘的方法。
採用最小二乘的方法作为优化目标即潜在的使用了最大释然预计的方法。

2.几何解释

以下从几何角度解释最小二乘法的原理:为了结合以下的图形解释，须要改变一下数据的表示方法。

假定样本量的数目为N<script type="math/tex" id="MathJax-Element-7414">N</script>，样本i记为(xi,ti)<script type="math/tex" id="MathJax-Element-7415">(x_i,t_i)</script>，且样本特征xi的维数为M<script type="math/tex" id="MathJax-Element-7416">M</script>,M<N<script type="math/tex" id="MathJax-Element-7417">M 1.全部样本目标真实值ti<script type="math/tex" id="MathJax-Element-7418">t_i</script>。构成一个N维列向量t=(t1,t2...tN)T<script type="math/tex" id="MathJax-Element-7419">t=(t_1,t_2...t_N)^T</script>;
2.全部样本的特征数据x构成一个N×M的矩阵X;矩阵X的第j个列向量记维φj<script type="math/tex" id="MathJax-Element-7420">φ_j</script>。即X=(φ0,φ1,...,φM?1)<script type="math/tex" id="MathJax-Element-7421">X=(φ_0,φ_1,...,φ_{M?1}) </script>
3.假定真实最优參数为θ?=(θ0,θ1,...θM?1)T<script type="math/tex" id="MathJax-Element-7422">θ^?=(θ_0,θ_1,...θ_{M?1})^T</script>,则有t=Xθ?=(φ0,φ1,...,φM?1)θ?<script type="math/tex" id="MathJax-Element-7423">t=Xθ^?=(φ_0,φ_1,...,φ_{M?1})θ^? </script>

我们的目的是寻找最好的拟合參数θ<script type="math/tex" id="MathJax-Element-7424">θ</script>，使得拟合出的预測值y=Xθ=(φ0,φ1,...,φM?1)θ<script type="math/tex" id="MathJax-Element-7425">y=Xθ=(φ_0,φ_1,...,φ_{M?1})θ</script>离真实值向量t<script type="math/tex" id="MathJax-Element-7426">t</script>近期。注意到X<script type="math/tex" id="MathJax-Element-7427">X</script>是样本数据，是固定值，每一列的φi<script type="math/tex" id="MathJax-Element-7428">φ_i</script>即相当于M<script type="math/tex" id="MathJax-Element-7429">M</script>维空间的一个基向量。(φ0,φ1,...,φM?1)<script type="math/tex" id="MathJax-Element-7430">(φ_0,φ_1,...,φ_{M?1})</script>,即构成了M<script type="math/tex" id="MathJax-Element-7431">M</script>维子空间的一组基向量。记做子空间S<script type="math/tex" id="MathJax-Element-7432">S</script>。

子空间S<script type="math/tex" id="MathJax-Element-7433">S</script>中不论什么向量都能够通过基向量的线性组合表示。最小二乘法在几何上解释，即寻找一个向量y<script type="math/tex" id="MathJax-Element-7434">y</script>与向量t<script type="math/tex" id="MathJax-Element-7435">t</script>之间欧式距离最小。如今的目的即是在S<script type="math/tex" id="MathJax-Element-7436">S</script>中寻找一个向量y<script type="math/tex" id="MathJax-Element-7437">y</script>,使得y<script type="math/tex" id="MathJax-Element-7438">y</script>离向量t<script type="math/tex" id="MathJax-Element-7439">t</script>的距离近期。最由图中能够看出，离t<script type="math/tex" id="MathJax-Element-7440">t</script>近期的向量y<script type="math/tex" id="MathJax-Element-7441">y</script>即是向量t<script type="math/tex" id="MathJax-Element-7442">t</script>向子空间S<script type="math/tex" id="MathJax-Element-7443">S</script>的正交投影。

局部加权回归（LWR）

LWR算法是非參数模型的一种。因为每一次预測新的数据，都须要採用原始样本计算一次，必定降低了效率。线性回归算法属于參数模型的一种，当得到最优參数θ<script type="math/tex" id="MathJax-Element-7444">θ</script>,预測新的数据时，就不须要原始数据样本了。

最小二乘法的目标(代价)函数是J(θ)=12∑mi=1(hθ(x(i))?y(i))2<script type="math/tex" id="MathJax-Element-7445">J(θ)=\frac12∑^m_{i=1}(h_θ(x^{(i)})?y(i))^2</script>。它採用了整体样本数据的性质，来预測新的数据,即所以样本的权重同样，不考虑局部性质。它的缺点是若原始数据分布由多个模型函数共同产生，採用最小二乘法的原则并不能最佳地逼近原始数据形态。

而局部加权回归通过增大预測的数据x(i)<script type="math/tex" id="MathJax-Element-7446">x^{(i)}</script>附近的样本点的权重。较小相对较远的样本数据的权重，来预測输出值h(x(i))<script type="math/tex" id="MathJax-Element-7447">h(x^{(i)})</script>。
局部加权回归算法：

当中ω(i)为第i个样本的权重
一种经常使用的权重分布函数为。相似高斯分布曲线：

參数τ控制偏离预測点距离权重的下降幅度。

參考：机器学习公开课—Andrew Ng