回顾
在讲解牛顿法之前我们先回顾一下最速梯度下降法,泰勒展开与Hessian矩阵之间的关系。
泰勒展开
对于一元函数f(x),在x处的泰勒展开为:
f(x+σ)=f(x)+f′(x)σ+21f′′(x)σ2+......
对于多元函数,一般写成矩阵形式:
f(x+σ)=f(x)+gTσ+21σTHσ+......
其中,x=[x1,x2]T,gT=[∂x1∂f,∂x2∂f]T,
H=[∂x12∂2f∂x2∂x1∂2f∂x1∂x2∂2f∂x22∂2f]
Hessian矩阵
上式中H就是Hessian矩阵,它具有以下性质:
- 具有对称性
- 若主对角线上的元素都大于零,则为正定矩阵;若不全大于零,则为半正定矩阵。
这个Hessian矩阵的正定性与函数凹凸性有很大关系:
1.若矩阵正定,则函数的二阶偏导数恒>0.
2.函数为凸(凸性就可以收敛到局部或者全局最优解)
更多关于Hessian正定性与函数凹凸性可移步这篇博文
最速梯度下降法
最速梯度下降法是将当前点进行一阶近似,用上面的泰勒展开来说,就是这样的:
f(x+σ)≈f(x)+gTσ
接下来我们将牛顿法:
总而言之,牛顿法就是函数当前点用二阶近似,从泰勒展开形式上说,就是在上面的最速梯度下降法后面再加了一个二次项:
f(x+σ)≈f(x)+gTσ+21σTHσ
那么这个一个什么函数?对,二次函数!因为最高次幂为2。而此前的最速梯度下降就是一个一次函数。直观的来讲,最速梯度下降是在当前点的切线方向画了一条线,而牛顿法是画了一个二次曲线:
对于上面的二阶近似,为了求下一点,进而得到极值点,对方向σ求导:
∂σ∂f=0
=> g+Hσ=0
=> σ=−H−1g (σ就是牛顿方向)
那么这个牛顿方向是不是下降方向?这就要将此方向与梯度方向作内积:
Δf=f(x+σ)−f(x)=gTσ
将上式的σ代入:Δf=−gTH−1g
要想找到极小值点,因此Δf<0, 即−gTH−1g<0,那么H≥0,也就是Hesian矩阵H应当正定。
有了下降方向σ,那么迭代就变成了:xk+1=xk+α(σk)。由此可见牛顿法与最速梯度下降法不同之处在于计算下降方向。
为什么牛顿法比最速梯度法更快收敛
因为最速梯度下降法是在当前点位置移动步长乘以当前点梯度,而越接近极值点梯度肯定越接近0,导致到最后越老越慢。
那么牛顿法是这个二次曲线与函数相切的时候,而下一个点是哪里呢?你可以在二次曲线上过最低点作一条垂线,垂线与函数相交的那点就是下一个位置。最后收敛的时候就是二次曲线最低点与函数极值点重合的时候。这不仅跨步大,比最速梯度下降法大得多。
那么用牛顿法有什么要求呢?就是Hessian矩阵一定要是半正定的。不然函数不是凸的,也就不能保证找到的是极值点。
如何保证Hessian矩阵正定性
根据线性代数知识可以知道,对于方阵H可以做特征值分解:
⎝⎜⎛λ1⋮…⋯⋱⋯⋯⋮λn⎠⎟⎞
若矩阵正定,则λi≥0。若不是,则可以修改H:
Hk^=1+βHk+βIn。
因此原来的特征值就变成了:
⎝⎜⎜⎛1+βλ1+β⋮…⋯⋱⋯⋯⋮1+βλn+β⎠⎟⎟⎞
在判别H正定性的时候,若其非正定,则β会设置很大,以至于所有的λi都大于0。若正定,β会设置很小。那么β怎么选?在矩阵特征根分解的时候不是会排序嘛?把选则β比最小的那个负值的绝对值大就可以了。