在前面的时间，我学习了Logistic回归，这是用来进行二分类学习的一种算法。虽然按照书上的介绍，编写了算法实现代码，但对其原理并不清楚，总感觉没有理解透。于是我又找到吴恩达的Marchine Learning课程，再次学习了线性回归和Logistic回归。
Machine Leanring这门课程是先从线性回归讲起，然后再介绍的Logistic回归，个人感觉这样的次序更容易理解。《机器学习实战》这本书也有线性回归的内容，不过放在比较后面的第8章，而且书中给出的解法是直接求解法，并没有采用梯度下降算法。
线性回归
在[机器学习实战札记] Logistic回归中，我们了解到回归的定义，其目的是预测数值型的目标值，最直接的方法是依据输入写出一个目标值的计算公式。比如：
HorsePower = 0.0015 * annualSalary - 0.99 * hoursListeningToPublicRadio 复制
这就是所谓的回归方程(regression equation)，其中的0.0015和-0.99称作回归系数(regression weights)，求这些回归系统的过程就是回归。一旦有了这些回归系统，再给定输入，做预测就非常容易。
回归中使用得最多的就是线性回归，而非线性回归问题也可以经过变化，简化为线性回归问题。比如有如下图所示的数据集：
可以通过引入高阶多项式：
这样问题仍然变成如何求解回归系数的问题。
如何求解这些回归系统呢？这里就需要理解代价函数(Cost Function)的概念。
代价函数
直观上，我们判断一个拟合函数的好坏，就是看我们的实际值离拟合直线是近还是远，理想的情况下，数据点都在拟合直线上，但现实中往往并没有这样一条拟合直线，如下图所示：
那如何评价数据点离拟合直线的远近呢？最常使用的就是方差距离，这个应该不陌生，在k-近邻算法中就是使用了该公式来表示数据点之间的距离。
因为训练数据集有多个数据点，所以使用均值作为最终的评估数据，这就是为什么要引入代价函数的原因。
该图简化了模型，只考虑单输入变量，所以只需要θ0, θ1两个回归参数。
理想的情况下，J的函数值为0。现在的问题是，如何取θ0, θ1值，使得J(θ)最小。
在Cost Funciton - Intuition部分，讲解了如何推导θ0, θ1，其方法依然是逐步简化，比如先固定θ0, 分别取不同的值，然后画出假设函数和Cost Function函数，下一步固定θ0, θ1，分别取不同的值：
右面曲线的含义是，选取任何颜色并沿着“圆”走，会获得相同的成本函数值。例如，上面绿线上的三个绿色点对于J(θ0，θ1)具有相同的值。越往曲线的中心，J(θ0，θ1)值越小，所以曲线中心对应的θ0，θ1就是我们要找到的回归系统。
梯度递减算法
在x轴上放置θ0，在y轴上放置θ1，在垂直z轴上放置代价函数，那么图上的点将是使用我们的假设与那些特定theta参数的成本函数的结果，如下面的图表所示：
很明显，如果我们找到图中的“坑底”，我们就已经成功了，图中红色箭头显示图表中的最小点。现在的问题是如何找到这个“坑底”呢？其实看到这个图，你是否会联想到一座山，如何到达山谷，只要我们沿着下坡走，就可以到达山谷，至于起点在哪，并不重要。如何最快达到山谷？当然是沿着最陡的坡度下山。梯度递减算法的原理和下山的原理一样：
- 任意选择一个θ0, θ1
- 根据梯度下降原则更新θ0, θ1，直到代价函数值达到最小
在上图中，存在多个“坑底”，也就是存在多个局部最优解，按照梯度递减算法，得到局部最优解，可能并不是全局最优解。不过对于我们的线性回归代价函数而言，不存在多个局部最优解，只有一个全局最优解，这就是所谓凸函数的概念。
梯度下降算法是，重复以下计算，直到收敛：
需要注意的是，每次迭代，θ0, θ1需要同步更新，也就是说在一次迭代过程中，不能使用新计算出的的θ0值来更新θ1。
看到这个算式是不是有点懵，在高数中一定学过偏导数这个概念，大多数人可能忘了，没关系。如果我们固定θ0，只考虑θ1的迭代，上面的算式可以写为：
如果对高数还有一点印象的话，可以理解这是一个导数算式。如果这个也不记得，那我们可以简单理解为对函数曲线的某一个点画切线，这个斜率就是函数在该点的导数。
这个斜率可能为正数，也可能为负数，这样无论从哪个点出发，经过迭代，都可以到达最低点。当斜率为0时，θ1值不再变化，即求得最优解。
α值的选取
在上面的梯度下降算法中，还有一个重要的参数α，这个相当于下山的步幅，这个α值的选择也有讲究，如果值过小，梯度下降缓慢，需要很多次的迭代才能达到收敛。如果值过大，梯度下降过程中可能越过了最低点，形成震荡，无法收敛。
如何选择这个α值，主要依靠经验。另外就是先选择一个值，评估一下收敛速度，然后再选择一个适合的值。
实现梯度下降算法
上面给出了梯度下降算法的一般化形式，如果要实现这个算法，我们需要知道那个偏导数的算术表达式。回到线性回归，梯度下降算法的表达式为：
其中m为训练数据集的大小，xi, yi为训练数据集的值。
其实有一个更通用的偏导数推导公式：
为了方便矩阵运算，数据集添加了一列，x0=1，代入到上述公式，就可以看出它们其实是等价的。
多变量回归
教程为了简化起见，从单变量回归入手，然后再过渡到多变量回归。有了单变量回归的基础，理解多变量回归并不困难，其中最主要的一点是要理解矩阵运算，将单变量回归的算术运算改写为矩阵运算即可。比如回归函数的矩阵化表示为：
需要注意的是，x0是为了方便矩阵化表示而引入的，x0固定等于1。
相应的，我们的梯度递减算法升级为：
可以看出，和单变量回归非常相似，仅仅是多了一些计算。
在k-近邻算法中，我们讨论过归一化数值的问题。在梯度递减算法中，也要对数据进行处理，以加快迭代速度，通常采用的计算方法为：
其中μi是特征(i)的所有值的平均值，si是值的范围(max - min)或标准偏差。
正态方程式解法
看过《机器学习实战》第8章的同学可能会疑惑，书上并没有采用梯度下降算法，而是直接采用如下方程式求解：
这个方程式看起来很简洁，实现起来似乎更简单，不需要迭代。然而问题在于这个方程式存在求逆的运算，这带来两个问题：
- 并非所有的矩阵都存在逆
- 对一个巨大的矩阵求逆，将非常耗时
下表给出两种方法各自的优缺点：
| 梯度下降算法 | 正态方程式 |
|---|---|
| 需要选择一个合适的alpha值 | 不需要选择alpha值 |
| 需要多次迭代 | 无需迭代 |
| 复杂度O(kn2) | 复杂度O(n3), 需要计算XTX的逆 |
| 当n很大时可以很好的工作 | 如果n很大，将会非常慢 |
用正态方程求逆的复杂度为O(n3)。 所以如果有很多特征，那么正态方程求解将会很慢。在实践中，当n超过10,000时，采用梯度递减算法更合适。
小结
在《机器学习实战》第8章，还介绍了局部加权线性回归。其实，对于这些基础的算法，基本上不需要我们去编写代码，现有的机器学习库都已经实现得相当完善，那这是不是意味着我们不需要去了解算法呢？也不是。就拿线性回归来说，我们需要了解什么情况下使用梯度递减法、alpha值的选择，如何判断迭代是否收敛等等。也就是说，有了对算法的了解，我们可以在实际中更好的选择合适的算法，更好的调整参数。