机器学习Ng课程笔记——线性回归算法

1. 定义
2. 假设函数与代价函数(损失函数)
3. 特征量放缩
4. 最小化代价函数
5. 收敛判定

1.什么是线性回归

在统计学中，线性回归是利用被称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间的关系进行建模的一种回归分析。在回归分析中，只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析；如果回归分析中包括两个及以上个自变量，且因变量和自变量直接是线性关系，则称之为多元线性回归分析。

2.假设函数与代价函数

在这里依然使用经典的例子——房价预测

因为存在两个自变量，所以这是一个多元线性回归的例子（如果只有面积或房间数则是一元线性回归），由此我们可以写出假设函数：$$h_{\Theta}(x)=\Theta_{0}+\Theta_{1}x_{1}+\Theta_{2}x_{2}$$
可分析得出，对于任意n元线性回归的假设函数可统一于如下表示：$$h_{\Theta}(x)=\sum_{i=1}^{m}\Theta_{i}x_{i}$$
上式中$x_{0}=1$。对于线性方程的求解，实质上就是对参数θ的求解。
建立模型后，我们需要对假设函数的准确性进行判优，其实就是去衡量θ的选取是否最优，我们引入代价函数：$$J(\Theta_{0},\Theta_{1}...\Theta_{n})=\frac{1}{2}\sum_{i=1}^{m}(h_{\Theta}(x^{(i)})-y^{(i)})^2$$
函数前面的1/2是为了在后面的求导过程中使式子简化。因此，我们现在的任务就是：求解代价函数的最小值，从而得出最优θ。

3.特征量放缩

在实际的数据集中，每个自变量的范围可能相差特别大，为了加速求解，我们需要将数据进行放缩，以此使得算法能够更加快速的收敛，特征量放缩的方法可以采用如下公式：$$x_{i}=\frac{x_{i}-\overline{x}}{max(x_{i})-min(x_{i})}$$

4.最小化代价函数

4.1最小二乘法（正规方程）
将训练特征量表示为X矩阵，训练集对应的结果值为y向量（注：本方法公式中y都是指向量y），即：
$$X=\begin{bmatrix}1 & 2104&3 \\ 1& 1600 & 3\\ 1& 2400&3 \\ 1& 1416 & 2\\ 1& 3000& 4\end{bmatrix};y=\begin{bmatrix}400\\ 330\\ 369\\ 232\\ 540\end{bmatrix}$$
其中，第一列对应x0，且x0恒为1，所以假设函数就可以表示为：
$$h_{\Theta}(x)=X\Theta$$
代价函数可以表示为：$$J(\Theta)=\frac{1}{2}(h_{\Theta}(x^{(i)})-y^{(i)})^2=\frac{1}{2}(X\Theta-y)^{T}(X\Theta-y)$$
由高等数学的知识，可以知道求代价函数的最优值，就是对每一个θ求偏导，令其为0。对上式进行求导展开：$$\frac{\partial }{\partial \Theta }J(\Theta)=\frac{1}{2}\frac{\partial }{\partial \Theta }(\Theta^{T}X^{T}X\Theta-\Theta^{T}X^{T}y-y^{T}X\Theta+y^{T}y)$$
由于θ转置是1*3，X转置是3*5，X是5*3，θ是3*1，所以上式第一项是1*1，即一个单一量方阵，同理可以得到其他的都是1*1方阵，所以上式又可以写成：$$\frac{\partial }{\partial \Theta }J(\Theta)=\frac{1}{2}\frac{\partial }{\partial \Theta }tr(\Theta^{T}X^{T}X\Theta-\Theta^{T}X^{T}y-y^{T}X\Theta)$$
最后可以变形为：$$\frac{\partial }{\partial \Theta }J(\Theta)=X^{T}X\Theta-X^{T}y$$
令上式为0，最终可得θ为：$$\Theta=(X^{T}X)^{-1}X^{T}y$$
在这种情况下，需要X的转置乘以X可逆，如果不可逆，可能的原因可能是：

1.特征量矩阵中存在两种特征数据线性相关；
2.特征数远大于数据集的个数，这时可以尝试着删除某些不是那么重要的特征数据；

这种方法对于求解问题相当的暴力简单，不需要迭代，不需要选择学习速率参数，但是当n的个数大于10,000时，这种方法的计算速度就非常之慢了。

4.2 梯度下降法
4.2.1 批量梯度下降（BGD）
在曲面上方向导数的最大值方向就代表了梯度方向，因此在我们在进行梯度下降时选择梯度的方向进行值更新，就可以找到最优解，θ的按照如下方法进行更新，其中α称为学习速率:$$\Theta_{j}:=\Theta_{j}-\alpha\frac{\partial }{\partial \Theta }J(\Theta)$$
首先假设假设函数只有一个参数，我们可辅以Ng课上的一张图片加以理解：

对于学习速率α的选择，如果太大，每次变化太大则容易超过最小值，太小则迭代次数过多。同时，当选定了学习速率时，我们不用再每次θ更新时也更新α，因为当我们接近局部最小或全局最小值时，梯度会自动的减小，直至为0，因此我们不必重复的去减小α。
当θ为2时，

当求解问题是线性回归时，代价函数就是一个线性最小二乘求解，就已经保证了代价函数是凸函数(如上图所示类似)，所以批量梯度一定能找到全局最优解；而当其他问题，非线性时，代价函数就可能变成非凸函数，批量梯度找到的就可能是局部最优，如图：

梯度下降类似于在山的某一点环顾四周，计算出下降最快的方向（多维），然后踏出一步，这属于一次迭代，同步更新一次值（所有θ必须是同步更新，不能更新了θ1,就用θ1更新后的值计算θ2，要所有的都计算完之后同步更新）；实际算法中并没有“环视四周”的步骤，因为当我们进行梯度计算时，就已经代表我们在朝着最小值方向前进。之所以称之为“批量梯度下降”是因为每一次迭代计算θ时都使用了整个样本集。但是，现在机器学习所处理的数据量相当的大，每次迭代都要遍历整个样本集无疑会耗费大量时间。算法描述如下：

4.2.2 随机梯度下降（SGD）
随机梯度的思路是：每次只使用一个样本来确定梯度，循环m次，这样就能得到一个十分逼近最优解的值。算法描述如下：

原始的随机梯度下降（SGD）适合于低精度的任务，而梯度下降算法适合用于高精度的任务。
如果接受一个比较低的精度（应用问题中往往不要求高精度），那么由于SGD每次只利用一个或部分样本的梯度做更新，所以前期迭代较快，导致前期一段时间内比梯度下降算法下降得多。
但是由于原始的SGD算法在目标函数强凸的情况下依旧无法做到线性收敛，所以当执行的时候足够长的时候SGD的精度会被梯度下降算法赶超，因为梯度下降算法可以在目标函数强凸的时候有线性收敛速（本段摘自：https://www.zhihu.com/questio...）

5.收敛判定

具体的收敛判定方法，待解决。

注：关于最小二乘法中得到矩阵形式的详细证明请参考本人其他相关文章，CSDN太难用了。

参考：

1.http://cs229.stanford.edu/sec...
2.http://lib.csdn.net/article/m...
3.http://open.163.com/movie/200...
4.CourseRa-斯坦福大学机器学习公开课
5.http://keson96.github.io/2016...