Визуализация и понимание 7 алгоритмов оптимизации в глубоком обучении

(!!! Предупреждение о слишком большом количестве картинок)

(Эта статья направлена на оптимизацию одномерных функций. На самом деле параметры модели имеют более миллиона размерностей, и разрыв очень большой. Поэтому эту статью лучше использовать как понимание вспомогательного метода, а не как основу для оценки плюсов и минусов алгоритма.)

8.13 Алгоритм обновления 6: алгоритм второго порядка, метод Ньютона, алгоритм 7: метод Ньютона + регуляризация

В глубоком обучении существует много видов алгоритмов оптимизации.Эти алгоритмы должны выполнять градиентный спуск в чрезвычайно высоких размерностях (обычно их больше миллиона параметров), то есть миллионы измерений.Оптимизированные параметры, обычно этот процесс может столкнуться с различные ситуации, например:

1. Локальный минимум встречается заранее и застревает, а глобальный минимум уже не найти.

2. Встречается чрезвычайно плоское место: «Равнина», где градиент чрезвычайно мал, и его нельзя оставить после многих итераций. Точно так же и седловая точка одинаковая.В седловой точке уклон во все стороны крайне мал, хотя можно уйти, пройдясь немного в одном направлении.

3. «Обрыв», градиент параметров в определенном направлении может внезапно стать чрезвычайно большим, в этом месте градиент может вызвать непредсказуемые последствия, из-за которых сходящиеся параметры могут внезапно убежать в очень далекое место.

Чтобы визуализировать и лучше понять эти алгоритмы оптимизации, я сначала описал очень извращенную 1D-функцию:

f(x)=(0.15x)^2+cos(x)+sin(3x)/3+cos(5x)/5+sin(7x)/7

Его производная имеет очень простой вид

f’(x) = 0.045x -sin(x)+cos(3x)-sin(5x)+cos(7x)

Конкретно выглядит так:

При обрывах и большом количестве локальных минимумов этого достаточно для моделирования более сложных оптимизационных ситуаций.

Алгоритм 1: Чистый градиентный спуск

Алгоритм прост и может быть выражен следующим образом:

          首先给出学习率lr，初始x        
           while True：
                  x = x - lr*df/dx

В зависимости от скорости обучения можно увидеть разные эффекты. Если скорость обучения слишком мала, она застрянет в локальном минимуме, а если скорость обучения слишком велика, она вообще не сойдется.

Алгоритм 2: градиентный спуск + импульс

Алгоритм основан на методе чистого градиентного спуска и добавляет градиент, таким образом записывая историческую ситуацию с градиентом, тем самым снижая риск застревания в локальном минимуме, и все еще будет оставаться определенное v, где градиент = 0, поэтому что в Swing вокруг минимума

       首先给出学习率lr，动量参数m
       初始速度v=0,初始x
       while True：
                  v = m * v - lr * df/dx
                  x += v

Вы можете увидеть картинку ниже:

Отсюда мы видим, что:

Чем меньше lr, тем он более устойчив.Если он слишком велик, трудно сходиться к минимальному значению, но если он слишком мал, сходимость будет слишком медленной.
Параметр импульса не может быть слишком маленьким, выше 0,9 работает лучше, но он не может быть слишком большим и не может оставаться на минимальном значении.

Алгоритм 3: Алгоритм АдаГрад

Идея алгоритма AdaGrad состоит в том, чтобы накапливать градиенты (квадраты), произошедшие в истории, и использовать квадратный корень из суммы накопленных квадратов градиентов для уменьшения текущего градиента поэлементно. В некотором смысле, это само по себе снижает скорость обучения, а уменьшение скорости обучения связано с градиентом, имевшим место в прошлом.

Недостатком является то, что градиент параметров обычно велик в начале, но алгоритм сильно уменьшает размер градиента в начале, также известный как преждевременное чрезмерное снижение скорости обучения.

Описание алгоритма:

给出学习率lr，delta=1e-7
累计梯度r=0，初始x
while True：
      g = df/dx
      r  = r + g*g
      x = x - lr / (delta+ sqrt(r)) * g

Эффект не очень...

Алгоритм 4: RMSProp

Алгоритм AdaGrad может иметь большой градиент на ранней стадии, который сохраняется от начала до конца, что сделает скорость обучения на более поздней стадии слишком маленькой. На этой основе RMSProp добавляет член затухания квадрата градиента, который может регистрировать только градиент последнего периода и может быстро сходиться при нахождении чашеобразной области.

Описание алгоритма:

给出学习率lr，delta=1e-6，衰减速率p
累计梯度r=0，初始x
while True：
      g = df/dx
      r  = p*r + （1-p）*g*g
      x = x - lr / (delta+ sqrt(r)) * g

Скорость затухания сложная, рекомендуется настроить параметры самостоятельно......

Алгоритм 5: Алгоритм Адама

Алгоритм Адама похож на предыдущий, и это также алгоритм адаптивного снижения скорости обучения, разница в том, что он обновляет момент первого порядка и момент второго порядка, момент первого порядка немного похож градиентный спуск с импульсом, а момент второго порядка используется для снижения скорости обучения.

Кроме того, используется формула, подобная s = s / (1-p1^t), которая удваивает s, когда t мало, так что градиент больше, параметры выполняются быстрее и быстрее приближаются к ожидаемой точке. Когда последующее t относительно велико, s = s / (1-p1^t) в основном эквивалентно s=s, что бесполезно.

Алгоритм следующий:

给出学习率lr，delta=1e-8，衰减速率p1=0.9，p2=0.999 
累计梯度r=0，初始x ,一阶矩s=0，二阶矩r=0
时间t = 0
while True：       
    t += 1
    g = df/dx 
    s = p1*s + (1-p1) *g
    r = p2*r +（1-p2）*g*g   

    s = s / (1-p1^t)
    r = r / (1-p2^t)    

    x = x - lr / (delta+ sqrt(r)) * s

Алгоритм Адама, призрачная производительность

Да, вы не ошиблись, эта штука вообще не сходится... и работает крайне плохо

После тщательного изучения алгоритма я обнаружил, что p2 = 0,999 слишком велико, когда t очень мало, в результате чего r = r / (1-p2^t), 1-p2^t близко к 0, r быстро взорвался и дошли до инф в сотне шагов. Позже, после изменения p2=0,9, эффект стал намного лучше.

Алгоритм Адама, производительность на уровне бога

В конце концов, Адам работает лучше всех :), хотя скорость обучения все еще нуждается в серьезной настройке.

Алгоритм 6: метод Ньютона

Метод Ньютона — это метод аппроксимации второго порядка, который работает как разложение функции до квадратичного (квадратичного) члена:

$L(x)=L(x_0) + (x-x_0)^{T}▽L(x_0) + \frac{1}{2}(x-x_0)^{T}H(x-x_0)$

Если повезет, это расширение представляет собой поверхность с отверстием вверх, и одна ступенька ведет к самой нижней точке поверхности:

$x=x_0 - H^{-1}▽L(x_0)$

初始x 
while True：            
        g = df(x)  # 一阶导数
        gg = ddf(x)   # 二阶导数
        x = x - g/gg   # 走到曲面的最低点

Метод бедного Ньютона, статический график

Картина как выше, действительно жалко смотреть... На самом деле метод Ньютона требует, чтобы матрица H была положительно определенной (в одномерном случае производная второго порядка больше нуля). размерность, такую ситуацию трудно удовлетворить, и большое количество минимальных значений, обрывов и седловых точек будет иметь эффект, делая невозможным плавное продолжение.Чтобы лучше выполнять метод Ньютона, нам нужно его упорядочить.

Алгоритм 7: метод Ньютона + регуляризация

Метод Ньютона плюс регуляризация позволяют избежать застревания на минимальном значении, и метод также очень прост: формулу обновления можно изменить на следующую

$x=x_0 - (H+\alpha\times I)^{-1}▽L(x_0)$

Одномерный алгоритм выглядит следующим образом:

初始x  ，正则化强度alpha
while True：                     
       g = df(x)  # 一阶导数         
       gg = ddf(x)   # 二阶导数         
       x = x - g/（gg+alpha）   # 走到曲面的最低点

Изображение эффекта:

Это действительно жалко видеть... Квадратичный метод действительно плох в невыпуклом случае. Также в алгоритме используется обратная матрица H, для которой требуется вычисление O (n ^ 3), что недоступно для глубокого обучения.

использованная литература:

[1] Ян Гудфеллоу, Глубокое обучение, People's Posts and Tele Communications Press, 170–190.

Код:

#coding:utf-8
from __future__ import print_function
import numpy as np
import matplotlib.pyplot as plt

def f(x):
    return (0.15*x)**2 + np.cos(x) + np.sin(3*x)/3 + np.cos(5*x)/5 + np.sin(7*x)/7

def df(x):
    return (9/200)*x - np.sin(x) -np.sin(5*x) + np.cos(3*x) + np.cos(7*x)

points_x = np.linspace(-20, 20, 1000)
points_y = f(points_x)


# 纯粹的梯度下降法,GD
for i in range(10):
    # 绘制原来的函数
    plt.plot(points_x, points_y, c="b", alpha=0.5, linestyle="-")
    # 算法开始
    lr = pow(2,-i)*16
    x = -20.0
    GD_x, GD_y = [], []
    for it in range(1000):
        GD_x.append(x), GD_y.append(f(x))
        dx = df(x)
        x = x - lr * dx

    plt.xlim(-20, 20)
    plt.ylim(-2, 10)
    plt.plot(GD_x, GD_y, c="r", linestyle="-")
    plt.title("Gradient descent,lr=%f"%(lr))
    plt.savefig("Gradient descent,lr=%f"%(lr) + ".png")
    plt.clf()


# 动量 + 梯度下降法
for i in range(10):
    # 绘制原来的函数
    plt.plot(points_x, points_y, c="b", alpha=0.5, linestyle="-")
    # 算法开始
    lr = 0.002
    m = 1 - pow(0.5,i)
    x = -20
    v = 1.0
    GDM_x, GDM_y = [], []
    for it in range(1000):
        GDM_x.append(x), GDM_y.append(f(x))
        v = m * v - lr * df(x)
        x = x + v

    plt.xlim(-20, 20)
    plt.ylim(-2, 10)
    plt.plot(GDM_x, GDM_y, c="r", linestyle="-")
    plt.scatter(GDM_x[-1],GDM_y[-1],90,marker = "x",color="g")
    plt.title("Gradient descent + momentum,lr=%f,m=%f"%(lr,m))
    plt.savefig("Gradient descent + momentum,lr=%f,m=%f"%(lr,m) + ".png")
    plt.clf()


# AdaGrad
for i in range(15):
    # 绘制原来的函数
    plt.plot(points_x, points_y, c="b", alpha=0.5, linestyle="-")
    # 算法开始
    lr = pow(1.5,-i)*32
    delta = 1e-7
    x = -20
    r = 0
    AdaGrad_x, AdaGrad_y = [], []
    for it in range(1000):
        AdaGrad_x.append(x), AdaGrad_y.append(f(x))
        g = df(x)
        r = r + g*g # 积累平方梯度
        x = x - lr /(delta + np.sqrt(r)) * g

    plt.xlim(-20, 20)
    plt.ylim(-2, 10)
    plt.plot(AdaGrad_x, AdaGrad_y, c="r", linestyle="-")
    plt.scatter(AdaGrad_x[-1],AdaGrad_y[-1],90,marker = "x",color="g")
    plt.title("AdaGrad,lr=%f"%(lr))
    plt.savefig("AdaGrad,lr=%f"%(lr) + ".png")
    plt.clf()


# RMSProp
for i in range(15):
    # 绘制原来的函数
    plt.plot(points_x, points_y, c="b", alpha=0.5, linestyle="-")
    # 算法开始
    lr = pow(1.5,-i)*32
    delta = 1e-6
    rou = 0.8
    x = -20
    r = 0
    RMSProp_x, RMSProp_y = [], []
    for it in range(1000):
        RMSProp_x.append(x), RMSProp_y.append(f(x))
        g = df(x)
        r = rou * r + (1-rou)*g*g # 积累平方梯度
        x = x - lr /(delta + np.sqrt(r)) * g

    plt.xlim(-20, 20)
    plt.ylim(-2, 10)
    plt.plot(RMSProp_x, RMSProp_y, c="r", linestyle="-")
    plt.scatter(RMSProp_x[-1],RMSProp_y[-1],90,marker = "x",color="g")
    plt.title("RMSProp,lr=%f,rou=%f"%(lr,rou))
    plt.savefig("RMSProp,lr=%f,rou=%f"%(lr,rou) + ".png")
    plt.clf()

# Adam
for i in range(48):
    # 绘制原来的函数
    plt.plot(points_x, points_y, c="b", alpha=0.5, linestyle="-")
    # 算法开始
    lr = pow(1.2,-i)*2
    rou1,rou2 = 0.9,0.9  # 原来的算法中rou2=0.999，但是效果很差
    delta = 1e-8
    x = -20
    s,r = 0,0
    t = 0
    Adam_x, Adam_y = [], []
    for it in range(1000):
        Adam_x.append(x), Adam_y.append(f(x))
        t += 1
        g = df(x)
        s = rou1 * s + (1 - rou1)*g
        r = rou2 * r + (1 - rou2)*g*g # 积累平方梯度
        s = s/(1-pow(rou1,t))
        r = r/(1-pow(rou2,t))
        x = x - lr /(delta + np.sqrt(r)) * s

    plt.xlim(-20, 20)
    plt.ylim(-2, 10)
    plt.plot(Adam_x, Adam_y, c="r", linestyle="-")
    plt.scatter(Adam_x[-1],Adam_y[-1],90,marker = "x",color="g")
    plt.title("Adam,lr=%f"%(lr))
    plt.savefig("Adam,lr=%f"%(lr) + ".png")
    plt.clf()

# 牛顿法
for i in range(72):
    # 绘制原来的函数
    plt.plot(points_x, points_y, c="b", alpha=0.5, linestyle="-")
    # 算法开始
    alpha= pow(1.2,-i)*20
    x = -20.0
    Newton_x, Newton_y = [], []
    for it in range(1000):
        Newton_x.append(x), Newton_y.append(f(x))
        g = df(x)
        gg = ddf(x)
        x = x - g/(gg+alpha)

    plt.xlim(-20, 20)
    plt.ylim(-2, 10)
    plt.plot(Newton_x, Newton_y, c="r", linestyle="-")
    plt.scatter(Newton_x[-1],Newton_y[-1],90,marker = "x",color="g")
    plt.title("Newton,alpha=%f"%(alpha))
    plt.savefig("Newton,alpha=%f"%(alpha) + ".png")
    plt.clf()