《Machine Learning》第二讲 线性回归与梯度下降
1.线性回归问题（linear regression）
1. 代价函数定义
如图所示：线性回归主要用于连续值或者说y的范围是实数时的预测，截图中的模型是房子的大小与价格的关系图，h(x)=θ1*x+θ0，如何选择出误差最小的θ是问题的关键。
何为误差最小呢，这个地方给出的是 Cost function(代价函数) 或者说是平方误差代价函数，计算公式在图片等右上角。h(x)为训练出的hypothesis, x(i),表示第 i 个训练data。
2. 假设函数与代价函数
如图所示，已知h(x)=θ0+θ1*x 假设θ0为0时，来讨论θ1与代价函数J(θ1) 之间的关系，在图中给出的数据示例中，J(θ1)与θ1的图像是一个二次函数，而最低点的位置 ，就是我们所追求的最佳的θ1的参数。
补充：这里有个概念必须要强调一下，所提到的假设函数h(x)是一个基于固定的θ以x作为自变量的函数，而代价函数则是一个基于固定的x以θ作为自变量的函数，不要混淆这个基本的概念，因此我们在之后的学习中，说到的梯度下降也就是在不断调整θ值的过程。
拓展到复杂的模型，我们在用线性回归寻找最佳的参数时，应当也是遵循此理念，找出最小的J(θ)所对应的θ0，θ1，如下图所示，3D模型中的最低点即为我 们所寻找的 fit（拟合）data best 的参数.
2.Gradient Descent(梯度下降)
1. 梯度下降定义
首先我们要了解梯度下降是什么，注意到 gradient 的意思有梯度，斜率等意思，斜率也可以联想到导数，导数下降是什么意思呢，在一个三维坐标系中，某个点的导数有关于x的偏导数，也有关于y的偏导数，如果这两个偏导数同时下降（减小），就意味着这个点正在从一个较为高且陡的地方向一个较为低且平缓的地方移动，在最后将会停在一个最低点的地方（可能是局部最优或者全局最优），停下来是因为导数为0，所以无法再下降了。而我们之前在线性回归中所说的，就是要找一个最低点的坐标，从而确定线性回归拟合数据最好的两个参数，θ0与θ1。下图所示的就是一个梯度下降的过程。
2. 梯度下降算法实现
首先分析这个循环体内的代码，θj 用来代指θ0和θ1，这个等式实际上可以拆成两个式子，“ := ”是一个赋值运算符，不能直接用“ = ”，“ = ”表示一个boolean判断，然后α的含义是learning rate，它的值用来指定梯度下降的幅度，α越大，每一次梯度下降的幅度越大。后面的一个偏导数式子就是分别计算J(θ0,θ1)分别关于θ0和θ1 的偏导数。 在接下来重点强调了θ0和θ1的值一定要 simultaneous update，左边的是正确的做法，右边的不正确，因为θ1在进行更新时，后面的θ0已经更新过了，二者就不同步了，找到的最优解也不是真实的最优解了。
——————————————————————————————————————————————————————————— 上面的式子中，θj更新一次的操作是用 θj 减去J(θ)在该维度j的偏导数值（也就是在θj 的斜率／导数），如何理解这个操作呢，我们假设考虑一个特征量且θ0 = 0 时的情况，这时 J(θ1)~θ1的函数图像如上图所示，
当θ1在最低点的右边时，该点的斜率为正值，学习速率也是一个正值，所以θ1减去一个正值，自然会减小，J(θ1)的值也会向最低点移动了；
当θ1在最低点的左边时，该点的斜率为负值，学习速率是一个正值，所以θ1减去一个负值，θ1的值增大，J(θ1)的值向最低点移动了。
因此，这就解释了θj的更新操作，我们从上面的简单例子推导，泛化到n个特征量的形式，将每一维的θj减去该点的偏导数值。
———————————————————————————————————————————————————————————
上面这幅图为我们详细介绍了偏导数是如何计算的，注意，在计算偏导数的过程中，θ0和θ1是自变量，而x,y这两个理解为参数，由于数据集是给定的，所以x,y是已知的常数，因此在求偏导的过程中，对θ0求偏导，则只需把θ0当作自变量，θ1同理。因此，最终能够得到图片底部的式子。
小结：梯度下降的过程实际上是同步的减小θ0和θ1的偏导数，直至偏导数都为0，达到一个收敛的效果。learning rate的值不要设置过大，梯度下降的幅度是越来越慢的，因为偏导数的值在趋向0的过程中越来越小，反倒若是α设置较大，很有可能出现θ0和θ1变化幅度太大越过了最优解，最后J(θ0,θ1)发散，找不到代价最小的点。
3. 梯度下降算法的泛化
在上面描述的线性回归模型中，讨论的是一元线性回归，即讨论了房价与房屋面积的线性关系，而在实际情况中，决定房价的可能还包含了其他因素，比如卧室的数量、楼的层数以及房屋的年限等，这个时候就设计到了多元线性回归的问题了。计算方法和一元的情况类似，如下图所示：
为了便于描述，我们定义x0=1.也就是把每一个数据X,加上一个元素x0为1，对应的特征值是θ0。因此，我们发现X和θ都是一个(n+1)维的列向量，并且h(x)可以简写为：h(x) =向量θ的转置与向量X的乘积。
上图给出了多元线性回归函数是如何用梯度下降计算的出最小值的，与之前算法的区别是，θ的下标是从0开始一直到n进行同步更新的，全部更新完一轮之后，再进行下一轮的下降，不断迭代直至 J(θ)即代价收敛于某一个值。
需要注意的是，图中累积求和公式中的m，它代表的是数据集的大小，它是不变的，刚刚增加的x0, 是把数据集中的每一个元素增加了一个维度而已，所以不要把求和的m也加上了1 。
4.梯度下降之特征缩放(Feature Scaling)
4.1 0-1 normalization（标准化）
在上图可以看到，未经过处理是x1的范围址（0～2000），x2的范围是（1～5），这个导致所得到的二元线性回归的图像的等高图呈又细又长的样子，导致梯度下降的进程十分缓慢，这样肯定是降低我们机器学习的效率的，因此，可以将数据进行处理，乘以或者除以一定的倍数，使得特征值处于（0～1）的区间，在这个区间的附近也行，这样就可以得到右边的图像，大大提升了梯度下降的速率，减少了迭代的次数。
4.2 mean normalization（均值标准化）
另外一种做法就是如上图所示，处理特征值，使其能够分布在（-0.5，0.5）的区间，分子是 x-mean,分母是(x的最大值 - x的最小值)。
除了上述的两种标准化／归一化的方法以外，还有一些其他的方法，之后遇到再进行补充。
5. 梯度下降之学习速率(Learning Rate)
如图所示，建立min J(θ)与No.of iterations的函数图像，min J(θ)表示每次迭代完产生的最小的代价值，No.of iterations表示迭代的次数，对于一个正确的learning rate α，所产生的图像应该就是这样，每次的迭代产生的最小代价值都在减小。当一次迭代中，代价值 J(θ)减小的少于0.001时，我们称函数收敛，即此时的结果为最优解，即找到了拟合训练数据最好的参数集θ了。
如果α值设定过小的话，J(θ)会缓慢的收敛；如果α值设定过大的话，J(θ)可能不一定在每次的迭代中减小，甚至出现最终无法收敛，越来越大的情况。
选择一个合适的α值，建议按照 … , 0.001 , 0.003 , 0.01 , 0.03 , 0.1 , 0.3 , 1 , …( 乘以3逐渐增大)
3.标准／正规方程（Normal Equation）
1.标准方程定义
首先要知道的是，标准方程也是一种求解参数向量θ的方法，与梯度下降不同，这种方法是直接对θ的每一个维度求偏导，即对θ0，θ1，θ2，…，θn分别求偏导，计算出所有偏导数值为0时，所对应的θi值.
我们在上一节计算梯度下降的最优解的时候，发现最优解出现的位置，就是各个方向的偏导值为0的点，因此，标准方程法只需要一次就可以计算出参数向量θ，不需要多次迭代，不需要特征缩放，更不需要设置学习速率α。
在上图中，首先直观上，对于一元线性回归，θ为一个实数（只有一个θ1，θ0 = 0）时，所得的J(θ)图像是一个二次函数图像，导数值为0点取得最优解，进一步地推论，θi在每一个维度取得的偏导数为0时的θi解，即为我们所求的θ。
2.通过矩阵求解 θ
图中给出了房屋的4个特征值，然后我们再手动加上一列x0。重点观察此处是如何得到矩阵X与列向量y的。矩阵X可以看作由 m=4 个列向量x=(x0,x1,x2,x2,x4)的转置向量组成的4*1矩阵。，列向量y直接由m=4个label组成。
红色标注的地方，就是θ的求解方法，目前知道这样即可，之后再作研究。
上图描述了，m个训练样本，n个特征值时，矩阵X的计算方法，只需记住，矩阵X的每一列，描述的每一个样本对应的同一个特征值即可。
3. 梯度下降法与标准方程法的比较