[机器学习-2]梯度下降法及实现（python）

[机器学习-2]梯度下降法及实现（python）

• • 样例（Example）
  • 利普西斯连续（L-continuity）
  • 利普西斯光滑（L-smoothness）
  • 凸集（Convex Set）
  • 凸函数（Convex Function）
  • 强凸（Strong Convexity）
  • 方向导数
  • 泰勒展开
  • 局部与全局最优解
  • 梯度下降法
  • 回溯线算法（backtracking line search）
  • 精确线算法（exact line search）

样例（Example）

！！想看实现，直接跳转回溯线算法与精确线算法。
今天，在做机器学习的作业的时候，我的室友和我说线性回归那道题目应该用步长来做，如果大于步长减半，后来我实现这种算法以后，发现和题目要求不一样。我室友说的是回溯线算法（backtracking line search）,而我最后实现的是精确线算法（exact line search）。现在和大家介绍这两种经典算法

Figure 1
题目长这样，就是用线性回归求一个二范数的最小值.
下面简单介绍一下GD所需的数学知识

利普西斯连续（L-continuity）

利普西斯光滑（L-smoothness）

由利普西斯光滑我们可以得到一个重要的结论

凸集（Convex Set）

凸函数（Convex Function）

需要说明的是，目前仍有许多数提到上凸与下凸的概念，这种定义已经过时而且明显没有搞清楚凸函数的真正定义是什么，凸函数指的是从函数上任意两点连线，线段与函数包围的区域为凸集

强凸（Strong Convexity）

类似的，根据强凸性，我们又可以得到机器学习中一些比较好的性质

方向导数

泰勒展开

机器学习中常见的泰勒展开为二阶，二阶导为海森矩阵，根据精度要求可能会高阶展开

局部与全局最优解

以最小解为例


对于凸集，有一个非常好的性质，也是机器学习里非常关心的一个性质就是局部最优解即全局最优解，所以很多时候会把一个集合拆成多个凸集进行优化

梯度下降法

梯度下降法通俗地讲就是沿负梯度方向迭代

在步长不变时可能会出现这种问题

回溯线算法（backtracking line search）

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import math
def load_csv(path, data):
    data_read = pd.read_csv(path)
    list = data_read.values.tolist()
    data = np.array(list)
    # print(data)
    return data

def f(x,A,b):
    func = np.dot(A,x)-b
    result = 0.5*np.linalg.norm(func, ord = 2)
    return result

def step_gradient(func, start, A, b, array1, array2, array3):
    alpha = 1
    step = 0
    index = []
    for i in range(0, 1000):
        index.append(i)
        alpha = 1
        step =alpha
        grad = np.dot(A.T,(np.dot(A,start)-b)) # 1000*500 * 1000 *500
        while(func(start,A,b)<func(start-step*grad,A,b)):
            step = step*0.5
        start = start - step*grad
        array1 = np.append(array1, step)
        array2 = np.append(array2, np.linalg.norm(grad))
        array3 = np.append(array3, func(start, A, b))
    plt.figure(figsize=(4,3))
    plt.semilogy(index,array1)
    plt.figure(figsize=(4,3))
    plt.semilogy(index,array2)
    plt.figure(figsize=(4,3))
    plt.semilogy(index,array3)
    plt.show()
    return 1
if __name__ == '__main__':
    initi = np.zeros((1000,1)).reshape(1000,1)
    b = np.zeros((500,1)).reshape(500,1)
    A = np.zeros((500,1000)).reshape(500,1000)
    b = load_csv('', b)
    A = load_csv('', A)
    function = f(initi, A, b)
    arr_1 = np.array([])
    arr_2 = np.array([])
    arr_3 = np.array([])
    step_gradient(f, initi, A, b, arr_1, arr_2, arr_3)

• 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
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50

输出如下
第一张是步长的变化，第二章是向量模的变化，最后是函数值得变化

精确线算法（exact line search）

先求出目标函数的梯度为(Ax-b)

然后我才用了近似算法，其实严格来说固定变量以后，就是一个二次函数求极值的问题，只是我这里方便起见采用了近似

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import math
def load_csv(path, data):
    data_read = pd.read_csv(path)
    list = data_read.values.tolist()
    data = np.array(list)
    # print(data)
    return data

def f(x,A,b):
    func = np.dot(A,x)-b
    result = 0.5*np.linalg.norm(func, ord = 2)
    return result

def step_gradient(func, start, A, b, array1, array2, array3, matrix):
    step = 0
    index = []
    for i in range(0, 1000):
        index.append(i)
        step =0
        grad = np.dot(A.T,(np.dot(A,start)-b)) # 1000*500 * 1000 *500
        up = np.dot(grad.T,grad)
        down = np.dot(grad.T, matrix)
        down = np.dot(down, grad)
        step = up/down
        start = start - step*grad
        array1 = np.append(array1, step)
        array2 = np.append(array2, np.linalg.norm(grad))
        array3 = np.append(array3, func(start, A, b))
    plt.figure(figsize=(4,3))
    plt.semilogy(index,array1)
    plt.figure(figsize=(4,3))
    plt.semilogy(index,array2)
    plt.figure(figsize=(4,3))
    plt.semilogy(index,array3)
    plt.show()
    return 1
if __name__ == '__main__':
    initi = np.zeros((1000,1)).reshape(1000,1)
    b = np.zeros((500,1)).reshape(500,1)
    A = np.zeros((500,1000)).reshape(500,1000)
    hessian = np.zeros((1000,1000)).reshape(1000,1000)
    b = load_csv('', b)
    A = load_csv('', A)
    hessian = np.dot(A.T,A)
    function = f(initi, A, b)
    arr_1 = np.array([])
    arr_2 = np.array([])
    arr_3 = np.array([])
    step_gradient(f, initi, A, b, arr_1, arr_2, arr_3, hessian)

• 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
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52

输出如下，可以看到下降的非常快