牛顿迭代与梯度下降_求最小值迭代算法

牛顿迭代法

牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

原理

首先牛顿法是求解函数值为0时的自变量取值的方法。
1

利用牛顿法求解目标函数的最小值其实是转化成求使目标函数的一阶导为0的参数值。这一转换的理论依据是，函数的极值点处的一阶导数为0.
　其迭代过程是在当前位置x0求该函数的切线，该切线和x轴的交点x1，作为新的x0,重复这个过程，直到交点和函数的零点重合。此时的参数值就是使得目标函数取得极值的参数值。

其迭代过程如下：
　　

迭代的公式如下：

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

其中H叫做海森矩阵，其实就是目标函数对参数θ的二阶导数。

梯度下降法

梯度下降的思想
·　通过搜索方向和步长来对参数进行更新。其中搜索方向是目标函数在当前位置的负梯度方向。因为这个方向是最快的下降方向。步长确定了沿着这个搜索方向下降的大小。
　迭代的过程就像是在不断的下坡，最终到达坡地。

原理

牛顿法

import numpy as np
import matplotlib.pyplot as plt
'''
牛顿迭代法实现 y =（x-2）**3的解
'''
def f(x):
    return (x-2)**3
def fd(x):
    return 3*((x-2)**2)
def newtonMethod(n,assum):
    time = n
    x = assum
    next = 0
    a = f(x)
    b = fd(x)
    print('a = '+str(a)+',b = '+str(b)+',time = '+str(time))
    if f(x) == 0.0:
        return time,x
    else:
        next = x-a/b
        print('next x = '+str(next))
    if a - f(next)<1e-6:
        print('meet f(x) = 0 , x = '+ str(next))  ##设置跳出条件，同时输出满足f(x) = 0 的x的值
    else:
        return newtonMethod(n+1,next)

newtonMethod(0,4.0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

梯度下降

def fit_gd(self,X_train,y_train,eta = 0.01, n_iters = 1e4):
    '''根据训练数据集X_train,y_train，使用梯度下降法训练线性回归模型'''
    assert X_train.shape[0] == y_train.shape[0] , 'the size of X_train must equal to the size of y_train'
    
    def J(theta,X_b,y):
    '''计算损失函数'''
      try:
        return np.sum((y - X_b.dot(theta))**2) / len(y)
      except:
        return float('inf')
      
    def dJ(theta,X_b,y):
    '''计算损失函数在每一个特征上的导数，即为梯度'''
      res = np.empty(len(theta))
      res[0] = np.sum(X_b.dot(theta) - y)
      for i in range(1,len(theta)):
        res[i] = (X_b.dot(theta) - y).dot(X_b[:,i])
      return res * 2 / len(X_b)

    def gradient_descent(X_b,y,initial_theta,eta,n_iters = 1e4,epsilon = 1e-8):
    '''计算随着梯度下降，最终得到的theta'''
      theta = initial_theta
      cur_iter = 0
      while cur_iter < n_iters:
        gradient = dJ(theta,X_b,y)
        last_theta = theta
        theta = theta - eta * gradient
        if(abs(J(theta,X_b,y) - J(last_theta,X_b,y)) < epsilon):
          break
        cur_iter += 1 
      return theta

    X_b = np.hstack([np.ones((len(X_train),1)),X_train])
    initial_theta = np.zeros(X_b.shape[1])
    self._theta = gradient_descent(X_b,y_train,initial_theta,eta,n_iters)
    self.interception_ = self._theta[0]
    self.coef_ = self._theta[1:]

    return self

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

参考博客