本课内容：1、线性回归2、梯度下降3、正规方程组 监督学习：告诉算法每个样本的正确答案，学习后的算法对新的输入也能输入正确的答案 1、线性回归问题引入：假设有一房屋销售的数据如下：
引入通用符号：m =训练样本数x =输入变量（特征）y =输出变量（目标变量）(x,y)—一个样本ith—第i个训练样本=(x(i),y(i))
本例中：m：数据个数，x：房屋大小，y：价格
监督学习过程：1) 将训练样本提供给学习算法2)
算法生成一个输出函数（一般用h表示，成为假设）3)
这个函数接收输入，输出结果。（本例中为，接收房屋面积，输出房价）将x映射到y。 如下图所示：
对假设进行线性表示：
通常来说，回归问题有多个输入特征。如上例中，我们还已知房屋的卧室数，即有个第二个特征。即x1表示大小，x2表示卧室数，则可将假设写成：
为了将公式写整洁，定义x0=1，则h可写成：
n=特征数目，θ：参数
选择θ的目的，是使h(x)与y的平方差尽量小。又由于有m个训练样本，需要计算每个样本的平方差，且为了后面求导的方便，乘以1/2，即：
我们要做的就是求：min(J(θ)) 求min(J(θ))的方法有：梯度下降法和正规方程组法 2、梯度下降（Gradient Descent） 梯度下降是一种搜索算法，基本思想：先给出参数向量一个初始值，比如0向量；不断改变，使得J(θ)不断缩小。改变的方法：梯度下降水平坐标轴表示θ0和θ1，垂直坐标表示J(θ)。假设该三维图为一个三维地表，选择的初始向量的点位于一座“山”上。梯度下降的方法是，你环视一周，寻找下降最快的路径，即为梯度的方向，每次下降一小步，再环视四周，继续下降，以此类推。结果到达一个局部最小值，如下图：
当然，假若初始点选择不同，则结果可能为另一个完全不同的局部最小值，如下图所示：
表明梯度下降的结果依赖于参数的初始值。
梯度下降算法的数学表示：
:=为赋值运算符，即表示程序中的的赋值语句。每一次将θi减去θi对J(θ)求偏导的结果，即沿最陡峭的“山坡”下降 假设只有一个训练样本时，将偏导数展开：
代入上式有：
α：学习速度，即决定了你下山时每一步迈多大。设得过小，则收敛时间长，设得过大，可能会在迈步的时候越过最小值。
特别注意：θi必须同步更新，即若假设i=0和i=1;则更新时按如下步骤：
（1）批梯度下降算法：上述为处理一个训练样本的公式，将其派生成包含m个训练样本的算法，循环下式直至收敛：
复杂度分析：
对于每个θi的每次迭代，即上式所示，时间为O(m) 每次迭代（走一步）需要计算n个特征的梯度值，复杂度为O(mn) 一般来说，这种二次函数的J(θ)的三维图形为一个碗状，有一个唯一的全局最小值。其等高线为一个套一个的椭圆形，运用梯度下降会快速收敛到圆心。
尽管α的值是固定的，梯度下降算法也会收敛到局部最小值，其原因是每次减去乘以梯度，但是梯度会越来越小，所以步子会越来越小。 下图为使用梯度下降拟合的上例房屋大小和价格的曲线
检测是否收敛的方法：1)检测两次迭代θi的改变量，若不再变化，则判定收敛2)更常用的方法：检验J(θ)，若不再变化，判定收敛
批梯度下降算法的优点是能找到局部最优解，但是若训练样本m很大的话，其每次迭代都要计算所有样本的偏导数的和，时间过慢，于是采用下述另一种梯度下降方法。
（2）随机梯度下降算法（增量梯度下降算法）：
如此一来，对每个训练样本都更新一次θi，直至收敛，其速度快于批梯度下降法，因为批梯度下降法每一次更新θi都需要遍历所有样本。即批梯度下降中，走一步为考虑m个样本；随机梯度下降中，走一步只考虑1个样本。每次迭代复杂度为O(n)。当m个样本用完时，继续循环到第1个样本。 上述使用了迭代的方法求最小值，实际上对于这类特定的最小二乘回归问题，或者普通最小二乘问题，存在其他方法给出最小值，接下来这种方法可以给出参数向量的解析表达式，如此一来就不需要迭代求解了。 3、正规方程组（Normal Equations）
假设我们有m个样本。特征向量的维度为n。因此，可知样本为{(x(1),y(1)), (x(2),y(2)),… …, (x(m),y(m))},其中对于每一个样本中的x(i),都有x(i)={x1(i), xn(i),… …,xn(i)}。令 H(θ)=θ0 + θ1×1 +θ2×2 +… + θnxn，则有
若希望H(θ)=Y，则有X · θ = Y
我们先来回忆一下两个概念：单位矩阵 和 矩阵的逆，看看它们有什么性质。
（1）单位矩阵E
AE=EA=A
（2）矩阵的逆A-1
要求：A必须为方阵
性质：AA-1=A-1A=E
再来看看式子 X · θ = Y ；若想求出θ，那么我们需要做一些转换：
step1：先把θ左边的矩阵变成一个方阵。通过乘以XT可以实现，则有
XTX · θ = XTY
step2：把θ左边的部分变成一个单位矩阵，这样就可以让它消失于无形了……
(XTX)-1(XTX) · θ = (XTX)-1XTY
step3：由于(XTX)-1(XTX)=E，因此式子变为
Eθ = (XTX)-1XTY
E可以去掉，因此得到
θ = (XTX)-1XTY
这就是我们所说的Normal Equation了。
Normal Equation VS
Gradient DescentNormal
Equation 跟 Gradient Descent一样，可以用来求权重向量θ。但它与Gradient
Descent相比，既有优势也有劣势。优势：Normal
Equation可以不在意X特征的规模大小。比如，有特征向量X={x1, x2},
其中x1的range为1~2000，而x2的range为1~4，可以看到它们的范围相差了500倍。如果使用Gradient
Descent方法的话，会导致椭圆变得很窄很长，而出现梯度下降困难，甚至无法下降梯度（因为导数乘上步长后可能会冲出椭圆的外面）。但是，如果用Normal
Equation方法的话，就不用担心这个问题了。因为它是纯粹的矩阵算法。劣势：相比于Gradient Descent，Normal
Equation需要大量的矩阵运算，特别是求矩阵的逆。在矩阵很大的情况下，会大大增加计算复杂性以及对计算机内存容量的要求。 学习Regression问题避免不了梯度问题。之前对梯度概念一直模糊，找了好多博文来读，总算也一知半解。我对梯度下降法的简单理解 （1）为什么在多元函数自变量的研究中引入方向? 在自变量为一维的情况下，也就是自变量可以视为一个标量，此时，一个实数就可以代表它了，这个时候，如果要改变自变量的值，则其要么减小，要么增加，也就是“非左即右“。所以，说到“
自变量在某个方向上移动 ”这个概念的时候，它并不是十分明显；而在自变量为n（n≥2）维的情况下，这个概念就有用了起来：假设自变量X为3维的，即每一个X是（x1,
x2,
x3）这样的一个点，其中x1，x2和x3分别是一个实数，即标量。那么，如果要改变X，即将一个点移动到另一个点，你怎么移动？可以选择的方法太多了，例如，我们可以令x1，x2不变，仅使x3改变，也可以令x1，x3不变，仅使x2改变，等等。这些做法也就使得我们有了”
方向
“的概念，因为在3维空间中，一个点移动到另一个点，并不是像一维情况下那样“非左即右”的，而是有“方向”的。在这样的情况下，找到一个合适的”方向“，使得从一个点移动到另一个点的时候，函数值的改变最符合我们预定的要求（例如，函数值要减小到什么程度），就变得十分有必要了。 （2）为什么沿梯度的反方向函数值下降最快？将目标函数f(x)在点xk处泰勒展开： 
Xk：代表第k个点的自变量（一个向量）。d：单位方向（一个向量），即|d|=1。α：步长（一个实数）。
：目标函数在Xk这一点的梯度（一个向量）。o(α):α的高阶无穷小。这个数学表达式是用泰勒公式展开得到的，样子有点难看，所以对比一下自变量为一维的情况下的泰勒展开式
就知道多维的情况下的泰勒展开式是怎么回事了。
在[1]式中高阶无穷小可以忽略，因此，要使[1]式取到最小值，应使
取到最小——这是两个向量的点积（数量积），何种情况下其值最小呢？
来看两向量
的夹角θ的余弦是如何定义的：
假设向量d与负梯度-gk的夹角为θ，我们便可求出点积
的值为：
可见，θ为0时，上式取得最小值。也就是说，d取-gk时，目标函数值下降得最快，这就是称负梯度方向为“最速下降”方向的由来了。 一个多元函数的梯度方向是该函数值增加最陡的方向。具体到一元函数中时，梯度方向首先是沿着曲线的切线，然后取切线向上增长的方向为梯度方向。如下图所示。
具体到二元函数或多元函数时，梯度向量为函数值f对每个变量的导数，该向量的方向就是梯度的方向。如下图所示。
图中箭头方向为负梯度方向。
THE END!
