机器学习（1）多元线性回归

概述

线性回归是一个典型的监督学习问题，它常常被用来解决连续值的预测问题。我们通常需要给出一个训练集，训练集中包含已知的目的数据，同时还有与该预测可能相关的特征。
一个简单的一元线性回归的示例是：
我们能否给出房屋价格与房屋面积的关系预测？（或者给出当房屋面积为某个值时，房价的一个预测）
其中我们要给出一个训练集，训练集中包含多个房屋面积与对应房屋价格的真实数据。

符号约定与术语解释

术语解释

• 特征：在本例中，房屋的面积、房屋的建筑年龄等一些与房屋价格可能相关的都是特征。
• 特征向量：我们通常将同一个对象的特征数据使用一个特征向量来表示，该特征向量的分量都是该对象的一个特征。
• 预测函数：我们想要得到的有关输入与输出的映射关系。
• 代价函数：通常我们需要一种手段来衡量我们预测的好坏。我们一般使用一个代价函数来量化拟合与实际值的偏离程度。

符号约定

• $x_i$xi​用来表示第i个特征，$x^{(i)}$x(i)用来表示第i个输入的特征向量，同样的$x^{(i)}_j$xj(i)​表示第i个输入的第j个特征值。
• 输出向量我们用$y$y来表示，其中$y^{(i)}$y(i)代表第i个输入向量对应的输出。
• 预测函数我们表示为：
  $h_\theta(x)=\theta_0+\theta_1x_1+...+\theta_nx_n=\theta^Tx$hθ​(x)=θ0​+θ1​x1​+...+θn​xn​=θTx
  这表示预测函数的输入向量$x$x有n个分量，也即n个特征。
• 代价函数我们表示为：$J(\theta)$J(θ)

代价函数

代价函数是衡量预测函数给出的预测值与实际值之间的偏离程度。
一个常用的代价函数是：
$J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2$J(θ)=2m1​i=1∑m​(hθ​(x(i))−y(i))2
值得说明的是：这里的m指的是训练集中样本的个数，这里的$\frac{1}{2}$21​是为了与求导时平方带来的2抵消。

目的

我们的目的是：确定一个预测函数
$h_\theta(x)=\theta_0+\theta_1x_1+...+\theta_nx_n=X\theta$hθ​(x)=θ0​+θ1​x1​+...+θn​xn​=Xθ
对于每一个输入的向量$x$x，给出预测的$y$y值。
事实上是确定参数$\theta$θ，使得$J(\theta)$J(θ)取到最小值。
也即$min(J(\theta))$min(J(θ))。

解决思路

可以看到我们经过问题形式的变化，已经将其转化为了一个最优化问题。由于线性回归的特殊性，其代价函数是一个凸函数，也就是说，不存在会陷入某个局部最优点的情况。
凸函数的解释详见 凸函数-维基百科
针对这个对于代价函数的最优化问题，我们想到了两种解决思路：梯度下降法与正规方程法

梯度下降法

梯度下降法的思路是：把代价函数看做一个势函数，每次迭代时，选择向该点的梯度方向前进一步。
梯度的解释详见 梯度-维基百科。
也即每次向势函数下降最快的方向前进一步，对于一个凸函数，只要我们每次前进的距离足够小，那么最终一定能到达该最优点。
值得注意的是，梯度下降法是一个普遍的最优化问题的启发算法，该算法并不保证能找到一个全局最优解，事实上这依赖于我们选择的初始点所在的位置。
该算法的工作过程示意图如下：

再次重申一下，这里目标是$min(J(\theta))$min(J(θ))，自变量是$\theta$θ。
我们选择的初始位置是$\theta$θ，则每次我们都需要根据当前的梯度来更新下一次的$\theta$θ。
更新公式是：
$\theta_j=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta)$θj​=θj​−α∂θj​∂​J(θ) $\alpha$α是学习率，也叫步长。
值得注意的是：这其中 $\alpha\frac{\partial}{\partial\theta_j}J(\theta)$α∂θj​∂​J(θ) 部分是这个代价函数对于$\theta_j$θj​的偏导数。
这就是我们所说的每次向该函数的梯度方向前进一步。

我们通常结束迭代的条件是，$\theta_j$θj​收敛或改变在某个精确度内。编程上应当注意的点是，对于$\theta$θ，其各维度应当同步更新。

学习率的选择

学习率的选择是一个困难的问题。
当学习率过小时，其收敛速度实在太慢，我们将不得不重复进行更多次的迭代。
当学习率过大时，我们很容易跨过最优点，而到达一个没那么好的点，甚至有可能会比原来的代价函数更大。
在实践中，我们通常每3倍尝试一次，比如：

$α=0.001,0.003,0.01…0.3,1$α=0.001,0.003,0.01…0.3,1

特征缩放

有时我们会碰到参数的范围差异过大的情况。比如，一个参数取值在[0,1]，而另一个参数的范围则在[0,100000]，这在图中会显示出一个极其狭长的椭圆。（比下图还要夸张的多），我们每次在进行梯度下降迭代时，会遇到困难，这将使我们不得不进行更多次的迭代。

解决该问题的一个思路是：特征缩放（也叫归一化），该方法的思想是将所有特征的取值映射到一个合理的范围内。
通常，我们会将特征映射到[-0.5,0.5]的范围内，缩放公式是：
$x_i=\frac{x_i-\bar x_i}{max(x_i)-min(x_i)}$xi​=max(xi​)−min(xi​)xi​−xˉi​​
经过映射后的代价函数像下图这样，不会再呈现出一种奇怪的狭长椭圆形。
该方法事实上是换了一个坐标系，将不同量度的特征映射到了量程差别不大的坐标系内。

正规方程法

还记得吗？我们的优化目标是$min(J(\theta))$min(J(θ))，自变量是$\theta$θ。
上面的方法，令我们头疼的一点是学习率的选择，而且它需要频繁的迭代，除此之外，上面的方法并不能给出一个解析解。
因此我们尝试使用正规方程法来解决该问题：
值得注意的是：由于我们是多元线性回归，最后得到的是一个 $y$y 向量，因此我们根据
$J(\theta)=\frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x^{(i)})-y^{(i)})^2$J(θ)=2m1​i=1∑m​(hθ​(x(i))−y(i))2
写出代价函数的向量表示方式：
$J(\theta)=\frac{1}{2m}(h_\theta(x)-y)^T(h_\theta(x)-y)$J(θ)=2m1​(hθ​(x)−y)T(hθ​(x)−y)
其中$(h_\theta(x)-y)$(hθ​(x)−y)是一个列向量。
下式是预测函数的定义：
$h_\theta(x)=\theta_0+\theta_1x_1+...+\theta_nx_n=X\theta$hθ​(x)=θ0​+θ1​x1​+...+θn​xn​=Xθ
我们将其代入得到：
$J(\theta)=\frac{1}{2m}(X\theta-y)^T(X\theta-y)$J(θ)=2m1​(Xθ−y)T(Xθ−y)
其中$X$X是一个$m\times (n+1)$m×(n+1)的矩阵，构造方法是：
$X= \left\{ \begin{matrix} 1 & x^{(1)^T} \\ 1 & x^{(2)^T} \\ ...&...\\ 1 & x^{(m)^T} \end{matrix} \right\}$X=⎩⎪⎪⎨⎪⎪⎧​11...1​x(1)Tx(2)T...x(m)T​⎭⎪⎪⎬⎪⎪⎫​
其中$x^{(i)}$x(i)代表训练集中第 i 组数据，被写成一个($n\times 1$n×1)的列向量形式。
令 $\frac{d J(\theta)}{d\theta}=0$dθdJ(θ)​=0 求使得代价函数取到最小值的点。
解得：
$\theta=(X^TX)^{-1}X^Ty$θ=(XTX)−1XTy
这里不给出证明
只给出一个帮助记忆的方式：
最理想的情况是：$(X\theta-y)=0$(Xθ−y)=0
或者说是至少为一个很小很小的 $\delta$δ，因此有
$X\theta=y$Xθ=y
由于$\theta$θ是一个$(n+1)\times1$(n+1)×1的列向量，$y$y是一个($m\times 1$m×1)的列向量。而$X$X是一个$m\times (n+1)$m×(n+1)的矩阵，X不是方阵无法求逆，因此需要左乘一个$X^T$XT在左边构造一个$((n+1)\times (n+1))$((n+1)×(n+1))的方阵$X^TX$XTX。
此时等式变为：
$X^TX\theta=X^Ty$XTXθ=XTy
接着我们在两边左乘一个$(X^TX)^{-1}$(XTX)−1
得到
$\theta=(X^TX)^{-1}X^Ty$θ=(XTX)−1XTy
值得注意的是：$(X^TX)^{-1}$(XTX)−1部分的计算要花费$O(n^3)$O(n3)的时间复杂度。同时$(X^TX)$(XTX)有时可能不可逆。
比如$(X^TX)$(XTX)不满秩，也即有两行内容线性相关，或者两个特征线性相关，或者训练集的样本个数小于特征数。

梯度下降与正规方程的对比

	梯度下降法	正规方程法
时间复杂度	$O(n^2)$O(n2)	O(n^3)
优点	计算速度快	写代码方便，不需迭代
缺点	需要选择适当的学习率$\alpha$α	当特征数相当高时，时间代价相当高，此外有时逆矩阵可能不存在。
应用场景	比较普遍，除此之外甚至能应用到一些更加复杂的算法中	当特征数不高时