本例中:m:数据个数,x:房屋大小,y:价格
算法生成一个输出函数(一般用h表示,成为假设)
这个函数接收输入,输出结果。(本例中为,接收房屋面积,输出房价)将x映射到y。
对假设进行线性表示:
通常来说,回归问题有多个输入特征。如上例中,我们还已知房屋的卧室数,即有个第二个特征。即x1表示大小,x2表示卧室数,则可将假设写成:
为了将公式写整洁,定义x0=1,则h可写成:
n=特征数目,θ:参数
表明梯度下降的结果依赖于参数的初始值。
:=为赋值运算符,即表示程序中的的赋值语句。
α:学习速度,即决定了你下山时每一步迈多大。设得过小,则收敛时间长,设得过大,可能会在迈步的时候越过最小值。
复杂度分析:
尽管α的值是固定的,梯度下降算法也会收敛到局部最小值,其原因是每次减去乘以梯度,但是梯度会越来越小,所以步子会越来越小。
批梯度下降算法的优点是能找到局部最优解,但是若训练样本m很大的话,其每次迭代都要计算所有样本的偏导数的和,时间过慢,于是采用下述另一种梯度下降方法。
如此一来,对每个训练样本都更新一次θi,直至收敛,其速度快于批梯度下降法,因为批梯度下降法每一次更新θi都需要遍历所有样本。即批梯度下降中,走一步为考虑m个样本;随机梯度下降中,走一步只考虑1个样本。
假设我们有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 + θ1x1 +θ2x2 +... + θ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了。
Gradient Descent
Equation 跟 Gradient Descent一样,可以用来求权重向量θ。但它与Gradient
Descent相比,既有优势也有劣势。
Equation可以不在意X特征的规模大小。比如,有特征向量X={x1, x2},
其中x1的range为1~2000,而x2的range为1~4,可以看到它们的范围相差了500倍。如果使用Gradient
Descent方法的话,会导致椭圆变得很窄很长,而出现梯度下降困难,甚至无法下降梯度(因为导数乘上步长后可能会冲出椭圆的外面)。但是,如果用Normal
Equation方法的话,就不用担心这个问题了。因为它是纯粹的矩阵算法。
Equation需要大量的矩阵运算,特别是求矩阵的逆。在矩阵很大的情况下,会大大增加计算复杂性以及对计算机内存容量的要求。
自变量在某个方向上移动 ”这个概念的时候,它并不是十分明显;
x2,
x3)这样的一个点,其中x1,x2和x3分别是一个实数,即标量。那么,如果要改变X,即将一个点移动到另一个点,你怎么移动?可以选择的方法太多了,例如,我们可以令x1,x2不变,仅使x3改变,也可以令x1,x3不变,仅使x2改变,等等。这些做法也就使得我们有了”
方向
“的概念,因为在3维空间中,一个点移动到另一个点,并不是像一维情况下那样“非左即右”的,而是有“方向”的。在这样的情况下,找到一个合适的”方向“,使得从一个点移动到另一个点的时候,函数值的改变最符合我们预定的要求(例如,函数值要减小到什么程度),就变得十分有必要了。
就知道多维的情况下的泰勒展开式是怎么回事了。
可见,θ为0时,上式取得最小值。也就是说,d取-gk时,目标函数值下降得最快,这就是称负梯度方向为“最速下降”方向的由来了。
具体到二元函数或多元函数时,梯度向量为函数值f对每个变量的导数,该向量的方向就是梯度的方向。如下图所示。
图中箭头方向为负梯度方向。