【机器学习】什么是线性回归、cost function以及常用的线性回归算法

我们首先通过回归问题中最简单的线性回归(Linear Regression)来了解什么是监督学习。
监督学习的模型一般可以表示成如下：

在监督学习的问题中，我们要找到一个函数h(x)，使得对于一个给定的数据集x，能预测出对应的输出y。即 $y = h(x)$y=h(x)
如果我们所要预测的y值是连续的，比如房价，那么这就是一个回归问题；如果y值是一些离散的点，比如是良性肿瘤还是恶性肿瘤，那么这就是一个分类问题。

线性回归

1.表达形式

所谓线性回归，就是y和x的关系是线性的。

对于只有一个特征的线性回归，$h_{\theta}(x)$hθ​(x)可以表示成：
$h_{\theta}(x) = \theta_{1} x+\theta_{0}$hθ​(x)=θ1​x+θ0​

如果有多个特征，那么h(x)可以表示成：
$h_{\theta}(x)=\theta_{0}+\theta_{1}x_{1}+\theta_{2}x_{2}+...+\theta{n}x_{n}$hθ​(x)=θ0​+θ1​x1​+θ2​x2​+...+θnxn​

其中，$n$n代表特征的个数。

2.cost function

代价函数(cost function)，有些地方也叫损失函数(loss function).它是用来衡量预测值$h_{\theta}(x)$hθ​(x)与真实值y之间的差异，记为$J(\theta)$J(θ)。需要注意的是，对于每种算法来说，cost function并不是唯一的。如果$J(\theta)$J(θ)的值越小，那么说明模型和参数越符合训练样本。
训练参数的过程就是不断地改变$\theta$θ，从而得到更小的$J(\theta)$J(θ)的过程。
一个好的cost function需要满足两个最基本的要求：(1)能够评价模型的准确性 （2）对参数$\theta$θ可微。
在线性回归中，最常用的cost function就是均方误差(Mean squared error).具体表现形式是：
$J(\theta_0,\theta_1,...\theta_n)=\frac{1}{2m}\sum_{i=1}^{m}(\hat{y}^{(i)}-y^{(i)})^2=\frac{1}{2m}\sum_{i=1}^{m}(h_\theta(x_0^{(i)},x_1^{(i)},...x_n^{(i)})-y^{(i)})^2$J(θ0​,θ1​,...θn​)=2m1​i=1∑m​(y^​(i)−y(i))2=2m1​i=1∑m​(hθ​(x0(i)​,x1(i)​,...xn(i)​)−y(i))2

其中$m$m表示样本的数量。
那么对于给定的样本，我们需要找到$\theta_0,\theta_1,...\theta_n$θ0​,θ1​,...θn​得到
$\min\limits_{\theta_0,\theta_1,...,\theta_n}J(\theta_0,\theta_1,...\theta_n)$θ0​,θ1​,...,θn​min​J(θ0​,θ1​,...θn​)

3.梯度下降法

梯度下降法(Gradient descent)是求$J(\theta)$J(θ)最小值的一种常用的算法。
在微积分里，对多元函数的参数求$\partial$∂偏导，把求得的各个参数的偏导数以向量的形式写出来，就是梯度，例如$J(\theta_0,\theta_1)$J(θ0​,θ1​)对$\theta_0$θ0​和$\theta_1$θ1​求偏导，得到的梯度向量就是$(\frac{\partial{J}}{\partial{\theta_0}},\frac{\partial{J}}{\partial{\theta_1}})^{T}$(∂θ0​∂J​,∂θ1​∂J​)T。梯度向量，从几何意义上讲，是函数增加最快地地方。也就是说，从某一个点出发，沿着梯度向量的方向，容易找到函数的最大值。
如果我们要求$J(\theta_0,\theta_1)$J(θ0​,θ1​)的最小值，那么沿着梯度向量相反的方向，也就是$-(\frac{\partial{J}}{\partial{\theta_0}},\frac{\partial{J}}{\partial{\theta_1}})^{T}$−(∂θ0​∂J​,∂θ1​∂J​)T的方向，一步一步迭代求解。
但是梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解，但如果$J(\theta_0,\theta_1)$J(θ0​,θ1​)是凸函数，梯度下降法得到的解就一定是全局最优解。
对于有多个特征参数的损失函数$J(\theta_0,\theta_1,...,\theta_n)$J(θ0​,θ1​,...,θn​)，梯度下降法的具体算法是：
$\theta_0=\theta_0-\alpha\frac{\partial}{\partial\theta_0}J(\theta_0,\theta_1,...,\theta_n)$θ0​=θ0​−α∂θ0​∂​J(θ0​,θ1​,...,θn​)

$\vdots$⋮

$\theta_j=\theta_j-\alpha\frac{\partial}{\partial\theta_j}J(\theta_0,\theta_1,...,\theta_n)$θj​=θj​−α∂θj​∂​J(θ0​,θ1​,...,θn​)

$\vdots$⋮

$\theta_n=\theta_n-\alpha\frac{\partial}{\partial\theta_n}J(\theta_0,\theta_1,...,\theta_n)$θn​=θn​−α∂θn​∂​J(θ0​,θ1​,...,θn​)

一直迭代更新，直到收敛。其中，$\alpha$α是步长，也叫学习速率(learning rate)。$\alpha$α值的选择也比较关键，如果$\alpha$α选择的值太小，会使得收敛太慢，但如果$\alpha$α的值太大，会导致损失函数$J(\theta)$J(θ)不仅不收敛，反而会发散。
把梯度下降法的公式带入线性回归的损失函数$J(\theta_0,...,\theta_n)$J(θ0​,...,θn​)的公式中：
$\theta_j=\theta_j-\frac{\alpha}{m}\sum_{i=1}^{m}(h_\theta(x_0^{(i)},x_1^{(i)},...x_n^{(i)})-y^{(i)})x_j^{(i)}$θj​=θj​−mα​i=1∑m​(hθ​(x0(i)​,x1(i)​,...xn(i)​)−y(i))xj(i)​

其中$x_0^{(i)}$x0(i)​的值为1。

4.梯度下降法的矩阵表示形式

线性回归的模型假设函数为
$h(x_0,x_1,...,x_n)=\theta_0x_0+\theta_1x_1+...+\theta_nx_n$h(x0​,x1​,...,xn​)=θ0​x0​+θ1​x1​+...+θn​xn​

表示为矩阵形式为
$h_\theta(X)=X\theta$hθ​(X)=Xθ

其中，$\theta$θ为$(n+1)\times1$(n+1)×1维的向量，$X$X为$m\times(n+1)$m×(n+1)维的矩阵，$h_\theta(X)$hθ​(X)为$m\times1$m×1维的向量。$m$m代表样本的个数，$n$n代表特征的个数。
那么损失函数$J(\theta)$J(θ)的表示形式为：
$J(\theta)=\frac{1}{2m}(X\theta-Y)^T(X\theta-Y)$J(θ)=2m1​(Xθ−Y)T(Xθ−Y)

其中$Y$Y是样本的输出向量，维度为$m\times1$m×1。
梯度下降算法的更新过程可以表示为：
$\theta=\theta-\frac{\alpha}{m}X^T(X\theta-Y)$θ=θ−mα​XT(Xθ−Y)

5.归一化

样本中不同特征的取值范围不同，可能导致迭代范围很慢。为了减少特征取值的影响，可以对特征数据归一化，也就是对每个特征$x$x，求出它的期望$\overline{x}$x和标准差$std(x)$std(x),然后转化为：
$x=\frac{x-\overline{x}}{std(x)}$x=std(x)x−x​

6.正规方程(Normal Equation)

梯度下降法是一种求损失函数最小值的算法，现在我们讨论另外一种算法–正规方程(Normal Equation)。正规方程的好处是无需迭代即可直接求取出$\theta$θ值。
下面来演示一下推导过程，前面已经得到损失函数的矩阵表达式为：
$J(\theta)=\frac{1}{2m}(X\theta-Y)^T(X\theta-Y)$J(θ)=2m1​(Xθ−Y)T(Xθ−Y)

因为$\frac{1}{2m}$2m1​是常数，对最终的解没有影响，我们可以先将这部分省去。于是将上式展开得：
$J(\theta)=(\theta^TX^T-Y^T)(X\theta-Y)$J(θ)=(θTXT−YT)(Xθ−Y)

$J(\theta)=\theta^TX^TX\theta-(X\theta)^TY-Y^TX\theta+Y^TY$J(θ)=θTXTXθ−(Xθ)TY−YTXθ+YTY

因为$X\theta$Xθ和$Y$Y都是$m\times1$m×1维的向量，所以这两者相乘先后顺序没有关系，于是上式简化成：
$J(\theta)=\theta^TX^TX\theta-2(X\theta)^TY+Y^TY$J(θ)=θTXTXθ−2(Xθ)TY+YTY

接着对$\theta$θ求导：
$\frac{\partial}{\partial\theta}J(\theta)=2X^TX\theta-2X^TY$∂θ∂​J(θ)=2XTXθ−2XTY

当$\frac{\partial}{\partial\theta}J(\theta)=0$∂θ∂​J(θ)=0时取极值，得到:
$X^TX\theta=X^TY$XTXθ=XTY

于是得到$\theta$θ的值为：
$\theta=(X^TX)^{-1}X^TY$θ=(XTX)−1XTY

即为最优解。

7.梯度下降法和正规方程的比较

正规方程可以直接求$\theta$θ，不需要多次迭代，而且也不需要做归一化，而归一化对梯度下降非常重要，但是正规方程却增加了计算的复杂度，不适用于特征非常多的样本。下面把这两种算法的优缺点列出来：

这是Andrew课程中的图片。在实际应用中，根据实际的情况选择对应的算法。