机器学习入门之 — 梯度下降，牛顿法，拟牛顿法

梯度下降法

梯度下降法用来求解目标函数的极值。这个极值是给定模型给定数据之后在参数空间中搜索找到的。迭代过程为：

梯度下降方法的问题：
每一步走的距离在极值点附近非常重要，如果走的步子过大，容易在极值点附近震荡而无法收敛。

解决办法：将alpha设定为随着迭代次数而不断减小的变量，但是也不能完全减为零。

牛顿法

牛顿法是为了求解函数值为零的时候变量的取值问题的，具体地，当要求解 f(θ)=0时，如果 f可导，那么可以通过迭代公式。

当θ是向量时，牛顿法可以使用下面式子表示：

其中H叫做海森矩阵，H (-1) 表示的是海森矩阵的逆矩阵 ，其实就是目标函数对参数θ的二阶导数。

牛顿法的优点：
牛顿法收敛速度相比梯度下降法很快，而且由于海森矩阵的的逆在迭代中不断减小，起到逐渐缩小步长的效果。
缺点：
牛顿法的缺点就是计算海森矩阵的逆比较困难，消耗时间和计算资源。因此有了拟牛顿法。

• 网上一个牛顿法求解的例子：

  
  

海森矩阵的定义：

• 代码实现：
  用牛顿法求解 f = 100 * (x2-x1** 2) ** 2 + (1-x1)**2

import numpy as np
import matplotlib.pyplot as plt

#梯度的公式
def tidu(x):
    return np.array([-400*x[0]*(x[1]-x[0]**2)-2*(1-x[0]),200*(x[1]-x[0]**2)])

#海森矩阵的公式
def hessian(x):
    return np.array([[-400*(x[1]-3*x[0]**2)+2,-400*x[0]],[-400*x[0],200]])

#牛顿法
def newton(x):
    print("初始点为 : ",x)
    res=[]
    res.append(x)
    i = 1
    imax = 1000
    delta = 1
    #迭代的条件是小于imax，或者是更新的距离小于一个很小的数值
    while i<imax and delta>10**(-5):
        p = -np.dot(np.linalg.inv(hessian(x)),tidu(x))
        x_new = x + p
        res.append(x_new)
        delta = sum((x-x_new)**2)   # 更新的距离
        print("初始点为 : ",x_new)
        i=i+1
        x=x_new  # 更新x
    return np.array(res)


if __name__ =="__main__":
    # 用牛顿法求解  f=100*(x2-x1**2)**2+(1-x1)**2
    X1=np.arange(-1.5,1.5+0.05,0.05)
    X2=np.arange(-3.5,2+0.05,0.05)
    [x1,x2]=np.meshgrid(X1,X2)
    f=100*(x2-x1**2)**2+(1-x1)**2;   # 给定的函数
    plt.contour(x1,x2,f,20)          # 画出函数的20条轮廓线

    x0 = np.array([-1.2,1])
    res=newton(x0)

    res_x=res[:,0]
    res_y=res[:,1]
    plt.plot(res_x,res_y)
    plt.show()

---

然后就是拟牛顿法了

• 拟牛顿法

todo

牛顿法需要求海森矩阵，这个矩阵需要计算二阶偏导数，比较复杂。为了改良这个问题，提出了拟牛顿法。
基本idea是：不求二阶偏导数，构造出一个近似的海森矩阵。

---

参考：
https://www.zhihu.com/question/19723347
https://blog.csdn.net/xmu_jupiter/article/details/47402497
https://blog.csdn.net/u014688145/article/details/53688585