機器學習：梯度下降和牛頓法

一、問題描述

考慮将基本梯度下降和牛頓法應用到表中的資料上。

(a)用這兩種算法對二維資料給出

和

的判别。對梯度下降法取

。畫出以疊代次數為準則函數的曲線。

(b)估計這兩種方法的數學運算量。

(c)畫出收斂時間-學習率曲線。求出無法收斂的最國小習率。

二、算法核心思想分析

1、線性判别函數

由

的各個分量的線性組合而成的函數：

這裡

是“權向量”，

被稱為“門檻值權”。對于二分類器來說，若

，則判定為

，若

，則判定為

。方程

定義了一個判定面，把兩個類分開，被稱為“超平面”。

2、廣義線性判别函數

線性判别函數

可寫成：

其中系數

是權向量

的分量。通過加入另外的項（

的各對向量之間的乘積），我們得到二次判别函數：

因為

，不失一般性我們可以假設

。由此，二次判别函數擁有更多系數來産生複雜的分隔面。此時

定義的分隔面試一個二階曲面或說是“超二次曲面”。

若繼續加入更高次的項，我們就得到多項式判别函數。這可看做對某一判别函數

做級數展開，然後取其截尾逼近，此時廣義線性判别函數可寫成：

或

這裡

通常被稱為“增廣特征向量”，類似地，

被稱為“增廣權向量”，設

，可寫成：

對于兩類線性可分的情況，使用判别函數

來劃分

和

，若

，則判定為

，若

，則判定為

。

通常引入邊界裕量

限制解區域，要求解向量滿足：

3、梯度下降

我們在尋找滿足線性不等式組

的解時所采用的方法是：定義一個準則函數

，當

是解向量時，

為最小。這樣就将問題簡化為一個标量函數的極小化問題——通常可用梯度下降法來解決。梯度下降的原理非常簡單，首先從一個任意選擇的權向量

開始，計算其梯度向量

，下一個值

由自

向下降最陡的方向移一段距離而得到，即沿梯度的負方向。通常

由等式

計算，

是正的比例因子，或者說是用于設定步長的“學習率”（learning rate）。我們希望得到這樣一個權向量序列：最終收斂到一個使

極小化的解上。

步驟：初始化權向量

、門檻值

和學習率

，不斷疊代更新

，直到

，使得準則函數達到一個極小值，

收斂。

4、牛頓法

牛頓法權向量的更新公式為：

其中，

為準則函數的赫森矩陣。收斂條件為：

因為牛頓法使用了準則函數的二次偏導，是以牛頓法比梯度下降每一步都給出了更好的步長，也就更快收斂。但是每次遞歸都要計算赫森矩陣

的逆，時間複雜度為

，運算量更大。

三、題目分析

1、題目分析

本題表格中給出用于求判别函數中解向量的資料，二維資料

、

共20組。需要假設用于判别的準則函數，使用梯度下降算法和牛頓法分别與準則函數結合，求出解向量，進而求得線性判别函數。并畫出以疊代次數為準則函數的曲線。

本題中假設準則函數為：

梯度如下：

其中

為解向量，

為訓練資料，

為邊界裕量。

2、梯度下降

使用LMS算法進行疊代。學習率設為0.001，門檻值設為0.01，沿負梯度方向更新權值，最後畫出【疊代次數-準則函數曲線】、【分類界面】、【學習率-疊代次數曲線】，并得出無法收斂的最國小習率。

3、牛頓法

黑塞矩陣H由準則函數的二階偏導求得，為

，代入樣本計算即可，将其求逆并與梯度相乘，更新權重。最後畫出【疊代次數-準則函數曲線】和【分類界面】。

4、Notice：

• 學習率

  

  的選擇對于梯度下降算法收斂至關重要。如果

  

  太小，收斂将非常慢；如果

  

  太大的話可能會過沖（overshoot），甚至發散。
• 對于資料的使用需要注意，不是直接利用原始資料進行訓練，而是将原始資料增加一列，将其變成增廣矩陣。
• 邊界裕量

  

  的取值任意
• 牛頓法中學習率為

  

  ，是以需要赫森矩陣

  

  是非奇異矩陣。

四、代碼及運作結果

1、梯度下降

# -*- coding:utf-8 -*-
import xlrd
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False


# 讀取資料
def read_data():
    x = []
    data = xlrd.open_workbook("lab4_data.xlsx")
    table = data.sheets()[0]
    rows = table.nrows
    for i in range(1, rows):
        row_value = table.row_values(i)
        if row_value[2] == 1 or row_value[2] == 3:
            x.append(row_value)
    return x


# 準則函數
def get_j(a, b, y):
    j = 0.5 * np.power(np.linalg.norm((y * a - b)), 2)
    print("j", j)
    return j


# 準則函數的梯度
def get_gradient(a, b, y):
    gradient = y.T * (y * a - b)
    print("gradient", np.shape(gradient), "\n", gradient)
    return gradient


# 權向量的變化
def get_delta(eta, a, b, y):
    gradient = get_gradient(a, b, y)
    delta = eta * gradient
    print("delta", np.shape(delta), "\n", delta)
    return delta


# 解向量
def get_a(a_k, delta):
    a = a_k - delta
    print("a", np.shape(a), "\n", a)
    return a


# 線性判别函數
def get_gx(a, y):
    gx = a.T * y
    return gx


# 梯度下降：傳入學習率，傳回收斂時間、準則函數
def gradient_decent(eta, a, b, y, theta):
    iteration = []
    J = []
    count = 0
    loop_max = 100

    j = get_j(a, b, y)
    print("(", count, j, ")")
    iteration.append(count)
    J.append(j)
    delta = get_delta(eta, a, b, y)
    while np.linalg.norm(delta) >= theta:
        count += 1
        if count >= loop_max:
            print("break!")
            break
        delta = get_delta(eta, a, b, y)
        a = get_a(a, delta)  # 更新a
        j = get_j(a, b, y)
        iteration.append(count)
        J.append(j)
        print("(", count, j, ")")

    return iteration, J


def main():
    data = read_data()
    # print("data\n", np.mat(data))
    w = [x[:2] for x in filter(lambda x: x, data)]
    y = list(map(lambda x: [1, *x], w))
    # print("y\n", np.mat(y))

    # 規範化
    w1 = [x[:2] for x in filter(lambda x: x[2] == 1, data)]
    w3 = [x[:2] for x in filter(lambda x: x[2] == 3, data)]
    test = []
    for i in range(len(w1)):
        w1[i].insert(0, 1)
        test.append(w1[i])
    # w3 = (-1 * np.mat(w3)).tolist()
    for i in range(len(w3)):
        w3[i].insert(0, -1)
        test.append(w3[i])
    print(np.mat(test))
    y = test

    # initial
    a = [1, 1, 1]  # 權向量a
    theta = 0.01  # 門檻值θ
    eta = 0.001  # 學習率η
    b = [1 for i in range(len(y))]  # 邊界裕量

    y = np.mat(y)
    a = np.mat(a).T
    b = np.mat(b).T

    print("y", np.shape(y), "\n", y)
    print("a", np.shape(a), "\n", a)
    print("b", np.shape(b))  # , "\n", b

    # Gradient Decent
    fig1 = plt.figure(1)

    iteration, J = gradient_decent(eta, a, b, y, theta)
    plt.plot(iteration, J)  # 準則函數

    plt.title(u"學習率η = " + str(eta))
    plt.xlabel(u"疊代次數")
    plt.ylabel(u"準則函數")

    # 繪制樣本點
    fig2 = plt.figure(2)
    w1 = [x[:2] for x in filter(lambda x: x[2] == 1, data)]
    w3 = [x[:2] for x in filter(lambda x: x[2] == 3, data)]
    w1x1 = [x[0] for x in filter(lambda x: x, w1)]
    w1x2 = [x[1] for x in filter(lambda x: x, w1)]
    w3x1 = [x[0] for x in filter(lambda x: x, w3)]
    w3x2 = [x[1] for x in filter(lambda x: x, w3)]

    plt.scatter(w1x1, w1x2, c='r')
    plt.scatter(w3x1, w3x2, c='g')
    plt.xlabel("x1")
    plt.ylabel("x2")
    plt.title(u"分類界面")

    # # 準則函數分隔面
    x = [np.linspace(-5.1, 6.8, 100)]  # [1 for i in range(len(y))],
    x = np.mat(x).T

    x2 = (a[0, 0] + a[1, 0] * x) / a[2, 0]
    plt.plot(x, x2)

    # 學習率-收斂時間
    fig3 = plt.figure(3)
    learn_rate = [0.0005, 0.001, 0.0015, 0.002, 0.0025, 0.003, 0.0035, 0.004, 0.0045, 0.005, 0.0055]
    convergence = []
    for i in range(len(learn_rate)):
        iteration, J = gradient_decent(learn_rate[i], a, b, y, theta)
        convergence.append(iteration[-1])

    print(learn_rate, "\n", convergence)
    plt.plot(learn_rate, convergence)
    for xy in zip(learn_rate, convergence):
        plt.annotate("(%s,%s)" % xy, xy=xy, xytext=(-20, 10), textcoords='offset points')
    plt.xlabel(u"學習率")
    plt.ylabel(u"收斂時間")
    plt.title(u"學習率-收斂時間")

    plt.show()


if __name__ == '__main__':
    main()
           

【疊代次數-準則函數曲線】

學習率為0.001時，在所設門檻值下，梯度下降16次收斂

【分類界面】

權向量為[ 0.73775053 -0.19529194 0.23079494 ]

可以看到LMS算法并未給出最優解

【學習率-疊代次數曲線】

當學習率達到0.0045左右時，梯度下降無法收斂

2、牛頓法

# -*- coding:utf-8 -*-
import xlrd
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False


# 讀取資料
def read_data():
    x = []
    data = xlrd.open_workbook("lab4_data.xlsx")
    table = data.sheets()[0]
    rows = table.nrows
    for i in range(1, rows):
        row_value = table.row_values(i)
        if row_value[2] == 1 or row_value[2] == 3:
            x.append(row_value)
    return x


# 準則函數
def get_j(a, b, y):
    j = 0.5 * np.power(np.linalg.norm((y * a - b)), 2)
    print("j", j)
    return j


# 準則函數的梯度
def get_gradient(a, b, y):
    gradient = y.T * (y * a - b)
    print("gradient", np.shape(gradient), "\n", gradient)
    return gradient


# 權向量的變化
def get_delta(H, a, b, y):
    gradient = get_gradient(a, b, y)
    delta = H * gradient
    print("delta", np.shape(delta), "\n", delta)
    return delta


# 解向量
def get_a(a_k, delta):
    a = a_k - delta
    print("a", np.shape(a), "\n", a)
    return a


# 線性判别函數
def get_gx(a, y):
    gx = a.T * y
    return gx


def newton(H, a, b, y, theta):
    iteration = []
    J = []
    count = 0
    loop_max = 100

    j = get_j(a, b, y)
    print("(", count, j, ")")
    iteration.append(count)
    J.append(j)
    delta = get_delta(H, a, b, y)
    while np.linalg.norm(delta) >= theta:
        count += 1
        if count >= loop_max:
            print("break!")
            break
        delta = get_delta(H, a, b, y)
        a = get_a(a, delta)  # 更新a
        j = get_j(a, b, y)
        iteration.append(count)
        J.append(j)
        print("(", count, j, ")")
    return iteration, J


def main():
    data = read_data()
    # print("data\n", np.mat(data))
    w = [x[:2] for x in filter(lambda x: x, data)]
    y = list(map(lambda x: [1, *x], w))
    # print("y\n", np.mat(y))

    # 規範化
    w1 = [x[:2] for x in filter(lambda x: x[2] == 1, data)]
    w3 = [x[:2] for x in filter(lambda x: x[2] == 3, data)]
    test = []
    for i in range(len(w1)):
        w1[i].insert(0, 1)
        test.append(w1[i])
    # w3 = (-1 * np.mat(w3)).tolist()
    for i in range(len(w3)):
        w3[i].insert(0, -1)
        test.append(w3[i])
    print(np.mat(test))
    y = test

    # initial
    a = [1, 1, 1]  # 權向量a
    theta = 0.001  # 門檻值θ
    H = 0  # 學習率 黑塞矩陣的逆
    b = [1 for i in range(len(y))]  # 邊界裕量

    y = np.mat(y)
    a = np.mat(a).T
    b = np.mat(b).T

    print("y", np.shape(y), "\n", y)
    print("a", np.shape(a), "\n", a)
    print("b", np.shape(b))  # , "\n", b

    H = (y.T * y).I
    print("H", H)

    fig1 = plt.figure(1)

    iteration, J = newton(H, a, b, y, theta)
    plt.plot(iteration, J)  # 準則函數

    plt.xlabel(u"疊代次數")
    plt.ylabel(u"準則函數")
    plt.title(u"疊代次數-準則函數")

    # 繪制樣本點
    fig2 = plt.figure(2)
    w1 = [x[:2] for x in filter(lambda x: x[2] == 1, data)]
    w3 = [x[:2] for x in filter(lambda x: x[2] == 3, data)]
    w1x1 = [x[0] for x in filter(lambda x: x, w1)]
    w1x2 = [x[1] for x in filter(lambda x: x, w1)]
    w3x1 = [x[0] for x in filter(lambda x: x, w3)]
    w3x2 = [x[1] for x in filter(lambda x: x, w3)]

    plt.scatter(w1x1, w1x2, c='r')
    plt.scatter(w3x1, w3x2, c='g')
    plt.xlabel("x1")
    plt.ylabel("x2")
    plt.title(u"分類界面")

    # 準則函數分隔面
    x = [np.linspace(-6, 7, 100)]  # [1 for i in range(len(y))],
    x = np.mat(x).T

    x2 = (a[0, 0] + a[1, 0] * x) / a[2, 0]
    plt.plot(x, x2)

    plt.show()


if __name__ == '__main__':
    main()
           

【疊代次數-準則函數曲線】

在所設門檻值下，牛頓法收斂步數遠小于梯度下降

【分類界面】

權向量為[ 0.39200249 -0.15039118 0.2144672 ]

牛頓法和梯度下降都是為了尋找準則函數的極小值，是以兩者最後收斂結果一緻，僅在算法複雜度和收斂步數有差別。

3、運算量分析

梯度下降運算量：取決于收斂的步數，即疊代的次數，學習量與疊代次數成正比。

牛頓法運算量：不僅取決于收斂的步數，同時取決于赫森矩陣H 的運算複雜度。

五、總結

基本梯度下降法和牛頓法都能求得最終的權向量，使得準則函數取得一個極小值。一般來說，即使有了最佳的η(k) ，牛頓法也比梯度下降法在每一步都給出了更好的步長，是以收斂速度更快。但是當赫森矩陣H 為奇異矩陣時就不能用牛頓法了。而且，即使H 是非奇異的，每次遞歸時計算H 逆矩陣所需的

時間可輕易地将牛頓法帶來的好處給抵消了。實際上，将η(k) 設定為比較小的常數

，雖然比每一步都使用最優的η(k) 将需要更多步驟來校正，但通常總的時間開銷卻更少。

如有錯誤請指正