AndrewNG机器学习听课札记（1 ）——线性回归（linear regression）

Andrew NG机器学习听课笔记（1）

                                                  ——线性回归（linear regression）

听课的时候只是觉得这老师讲课听起来真舒服，等差不多的时候，实验室一小子说这货就是大名鼎鼎的coursera的创始人之一NG先生，此时此刻，在自责我自己有眼无珠的同时也暗暗的庆幸，能搜到这样的公开课实属万幸。。

线性回归是一种监督学习的方法，本节主要讲了最小二乘法以及梯度下降法。

为了以后的笔记方便，首先规定下符号的意义：

m ：训练集的容量（即训练样本的个数）

n ：样本的维数

：参数，也叫回归系数

：训练样本

: i =1…m：第i个样本

： j=1…n：样本的第j维

:回归方程

：给定对应的值，也叫target，目标

以后的所有符号都遵从这个记法。

线性回归问题可以简单的描述为给定m个训练样本以及与之对应的target，求得回归方程，使得能够对一个新的样本对应的target 做出相应的预测。

首先定义一个衡量预测的标准：

我们可以用偏差平方和：来表示，当然这个表示方法不唯一，不同的表示方法可能会导致不同的结果，我们会在以后慢慢讨论。

这样的话我们就有了目标：。

这样，线性回归问题就转化为一个优化问题了。怎么使上式取得最小呢？本节课主要介绍了三种方法：

第一种是 梯度下降法（gradient descent）

首先从一个初始值开始，重复以下步骤

直到最后的收敛条件。

下面我们求，首先我们针对只有一个样本的情况：

从而上述的更新算法 

这是针对一个样本的情况，当有多个样本（m）时更新算法就变成了

上式就是随机梯度下降法最终的更新准则。其中是一个自己设定的参数，叫做学习率，由它控制着梯度下降的速度。

通过上面的描述不难发现一个严重的问题：当样本容量非常大的时候，每更新一个都要把所有的样本跑一遍，这样浪费了大量的时间和空间复杂度，同时当样本足够大的时候，算法是不可行的。

为此提出了一个类似于梯度下降法的优化方法：随机梯度下降法：

算法如下：

For j = 1:m

(对所有的i)

repeat

另外对于最小二乘，大家都知道的一个方法：

，  ，

则

，从而，对关于求导并让导数等于0，最终就得到了，从而，这是一个非迭代的算法，算是一个解析解吧。

下面讨论针对有不同的表示方法：

下面给出minkowski距离的一个通式：

上式中q取不同的值，会导致我们最终的迭代收敛的位置：当q=1时，算法收敛于中值，当q=2时，算法收敛于均值，当q=0时，算法收敛于众数。

最终还有一个关于收敛终止条件的，有两种方法，第一种是前后两次更新的的差小于某个阈值。但更常用的是前后两次更新后的值的变化。