1. 概述

梯度下降法
高斯牛顿迭代法
牛顿法
共轭梯度法

2. 基础知识

2.1 微分

函数图像中，某点的切线的斜率
函数的变化率

例子：

$\frac{d(x^2)}{dx} = 2x$，为单变量微分。

$\frac{\partial}{\partial x}(x^2y^2) = 2xy^2$，为多变量微分

2.2 梯度

梯度实际上就是多变量微分的一般化
在单变量的函数中，梯度其实就是函数的微分，代表着函数在某个给定点的切线的斜率
在多变量函数中，梯度是一个向量，向量有方向，梯度的方向就指出了函数在给定点的上升最快的方向
- 分别对每个变量进行微分，然后用逗号分割开，梯度是用<>包括起来，说明梯度其实一个向量
梯度的方向是函数在给定点上升最快的方向，那么梯度的反方向就是函数在给定点下降最快的方向
只要沿着梯度的方向一直走，就能走到局部的最低点

例子：

$J(\Theta) = 0.55 - (5\theta_1 + 2\theta_2 - 12\theta_3)$,

$\bigtriangledown J(\Theta) = <\frac{\partial J}{\partial \theta_1}, \frac{\partial J}{\partial \theta_2}, \frac{\partial J}{\partial \theta_3}> = <-5, -2, 12>$.

2.3 泰勒公式

用多项式函数去逼近光滑函数

$f(x) = \sum_{i=0}^{n}\frac{f^{(i)}(x_0)}{i!}(x - x_0)^{i}$.

3. 梯度下降法

3.1 原理分析

目标
- 有一个可微分的函数，找到这个函数的最小值，就是找到给定点的梯度，然后朝着梯度相反的方向，就能让函数值下降的最快
核心公式

$\theta_1 = \theta_0 - \alpha \bigtriangledown J(\theta)$.
该公式的主要含义如下
- J是$\theta$的函数
- 当前处在$\theta_0$点，目标是要从这个点走到J的最小值点
- 先确定前进的方向，也就是梯度的反向，然后走一段距离的步长$\alpha$，此时到了$\theta_1$
- 如果$\theta_1$就是使得函数局部最小值的点，那么迭代结束
- 如果$\theta_1$不是使得函数取得局部最小值的点，那么继续迭代下去
- 公式中负号的含义是朝着梯度相反的方向前进；因为梯度的方向实际就是函数在此点上升最快的方向，我们需要朝着下降最快的方向走，自然就是负的梯度的方向，所以此处需要加上负号

例子1：

假设单变量函数为$J(\theta) = \theta^2$，其微分为$J’(\theta) = 2\theta$，假设起点为$\theta_0 = 1$，步长为$\alpha = 0.4$，那么梯度下降法的迭代过程如下：

$\theta_0 = 1$,

$\theta_1 = \theta_0 - \alpha J’(\theta_0) = 1 - 0.4 2 = 0.2$,

$\theta_2 = \theta_1 - \alpha J’(\theta_1) = 0.2 - 0.4 2 * 0.2 = 0.04$,

$\theta_3 = 0.008$,

$\theta_4 = 0.0016$.

如果我们要求的精度为1e2或者迭代次数最大4次，那么，此时我们的算法已收敛。

例子2：

假设目标函数为$J(\Theta) = \theta_1^2 + \theta_2^2$，初始值为(1, 3)，步长为0.1，函数的梯度为$\bigtriangledown J(\Theta) = <2\theta_1, 2\theta_2>$，迭代过程如下：

$\Theta_0 = (1, 3)$,

$\Theta_1 = \Theta_0 - \alpha \bigtriangledown J(\Theta) = (1, 3) - 0.1 (2, 6) = (0.8, 2.4)$,

$\Theta_2 = \Theta_1 - \alpha \bigtriangledown J(\Theta) = (0.8, 2.4) - 0.1 (1.6, 4.8) = (0.64, 1.92)$,

$\Theta_3 = (0.512, 1.536)$,

$\dots$,

$\Theta_{10} = (0.1073, 0.3221)$,

$\dots$,

$\Theta_{100} = (1.629e^{-10}, 4.8888e^{-10})$.

3.2 算法实现

线性回归

import numpy as np

# Size of the points dataset.
m = 20

# Points x-coordinate and dummy value (x0, x1).
X0 = np.ones((m, 1))
X1 = np.arange(1, m+1).reshape(m, 1)
X = np.hstack((X0, X1))

# Points y-coordinate
y = np.array([
    3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,
    11, 13, 13, 16, 17, 18, 17, 19, 21
]).reshape(m, 1)

# The Learning Rate alpha.
alpha = 0.01

def error_function(theta, X, y):
    '''Error function J definition.'''
    diff = np.dot(X, theta) - y
    return (1./2*m) * np.dot(np.transpose(diff), diff)

def gradient_function(theta, X, y):
    '''Gradient of the function J definition.'''
    diff = np.dot(X, theta) - y
    return (1./m) * np.dot(np.transpose(X), diff)

def gradient_descent(X, y, alpha):
    '''Perform gradient descent.'''
    theta = np.array([1, 1]).reshape(2, 1)
    gradient = gradient_function(theta, X, y)
    while not np.all(np.absolute(gradient) <= 1e-5):
        theta = theta - alpha * gradient
        gradient = gradient_function(theta, X, y)
    return theta

optimal = gradient_descent(X, y, alpha)
print('optimal:', optimal)
print('error function:', error_function(optimal, X, y)[0,0])

3.3 梯度下降法大家族（BGD，SGD，MBGD）

批量梯度下降法（Batch Gradient Descent）
- 批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新
随机梯度下降法（Stochastic Gradient Descent）
- 随机梯度下降法，其实和批量梯度下降法原理类似，区别在与求梯度时没有用所有的样本的数据，而是仅仅选取一个样本来求梯度
小批量梯度下降法（Mini-batch Gradient Descent）
- 小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于m个样本，我们采用x个样子来迭代
批量梯度下降法python实现

def train(X, y, W, B, alpha, max_iters):
    '''
    使用了所有的样本进行梯度下降
    X: 训练集,
    y: 标签,
    W: 权重向量,
    B: bias,
    alpha: 学习率,
    max_iters: 最大迭代次数.
    '''
    dW = 0 # 权重梯度收集器
    dB = 0 # Bias梯度的收集器
    m = X.shape[0] # 样本数
    for i in range(max_iters):
        dW = 0 # 每次迭代重置
        dB = 0
        for j in range(m):
            # 1. 迭代所有的样本
            # 2. 计算权重和bias的梯度保存在w_grad和b_grad,
            # 3. 通过增加w_grad和b_grad来更新dW和dB
            W = W - alpha * (dW / m) # 更新权重
            B = B - alpha * (dB / m) # 更新bias

    return W, B

3.4 梯度下降法和最小二乘法

梯度下降法和最小二乘法相比，梯度下降法需要选择步长，而最小二乘法不需要
梯度下降法是迭代求解，最小二乘法是计算解析解
如果样本量不算很大，且存在解析解，最小二乘法比起梯度下降法要有优势，计算速度很快
如果样本量很大，用最小二乘法由于需要求一个超级大的逆矩阵，这时就很难或者很慢才能求解解析解了，使用迭代的梯度下降法比较有优势

3.5 优缺点

靠近极小值时收敛速度减慢
直线搜索时可能会产生一些问题
可能会“之字形”地下降

vSLAMNet（四）-最优化-梯度下降法