Блог

Я написал этот код, чтобы получить градиентный спуск векторной функции .

Где: f — функция, X0 — начальная точка, а eta — размер шага.

По сути, он состоит из двух частей: первая, которая получает градиент функции, и вторая, которая выполняет итерацию по x, вычитая градиент.

проблема в том, что у вас обычно возникают проблемы с конвергенцией некоторых функций, например:

если мы возьмем, градиентный спуск не сходится к [20,25]

Что-то, что мне нужно изменить или добавить?

 def descenso_grad(f,X0,eta):

    def grad(f,X):
        import numpy as np
        def partial(g,k,X):
            h=1e-9
            Y=np.copy(X)
            X[k-1]=X[k-1] h
            dp=(g(X)-g(Y))/h
            return dp
        grd=[]
        for i in np.arange(0,len(X)):
            ai=partial(f,i 1,X)
            grd.append(ai)
        return grd
    #iterations

    i=0
    while True:
        i=i 1
        X0=X0-eta*np.array(grad(f,X0))

        if np.linalg.norm(grad(f,X0))<10e-8 or i>400: break
    return X0
 

Ваша реализация градиентного спуска — хорошая базовая реализация, но ваш градиент иногда колеблется и взрывается. Сначала мы должны уточнить, что ваш градиентный спуск не всегда расходится. Для некоторых комбинаций eta и X0 он действительно сходится.

Но сначала позвольте мне предложить несколько изменений в коде:

• import numpy as np Оператор должен находиться в верхней части вашего файла, а не внутри функции. В общем, любой оператор импорта должен быть в начале кода, чтобы они выполнялись только один раз
• Лучше не писать вложенные функции, а разделять их: вы можете написать partial функцию вне grad функции, а grad функцию вне descendo_grad функции. это лучше для отладки.
• Я настоятельно рекомендую передавать такие параметры, как скорость обучения ( eta ), количество шагов ( steps ) и допуск (заданный в 10e-8 в вашем коде или 1e-7) в качестве параметров descendo_grad функции. Таким образом, вы сможете сравнить их влияние на результат.

В любом случае, вот реализация вашего кода, которую я буду использовать в этом ответе:

 import numpy as np

def partial(g, k, X):
    h = 1e-9
    Y = np.copy(X)
    X[k - 1] = X[k - 1]   h
    dp = (g(X) - g(Y)) / h
    return dp

def grad(f, X):
    grd = []
    for i in np.arange(0, len(X)):
        ai = partial(f, i   1, X)
        grd.append(ai)
    return grd

def descenso_grad(f,X0,eta, steps, tolerance=1e-7):

    #iterations
    i=0
    while True:
        i=i 1
        X0=X0-eta*np.array(grad(f,X0))

        if np.linalg.norm(grad(f,X0))<tolerance or i>steps: break
    return X0

def f(X):
    return (X[0]-20)**4   (X[1]-25)**4

 

Теперь о сходимости. Я сказал, что ваша реализация не всегда расходится. Действительно:

 X0 = [2, 30]
eta = 0.001
steps = 400
xmin = descenso_grad(f, X0, eta, steps)
print(xmin) 
 

Будет печатать [20.55359068 25.55258024]

Но:

 X0 = [2, 0]
eta = 0.001
steps = 400
xmin = descenso_grad(f, X0, eta, steps)
print(xmin)
 

На самом деле будут расходиться в [ 2.42462695e 01 -3.54879793e 10]

1) Что произошло

Ваш градиент на самом деле колеблется вокруг оси y. Давайте вычислим градиент f at X0 = [2, 0] :

 print(grad(f, X0))
 

Мы получаем grad(f, X0) = [-23328.00067961216, -62500.01024454831] , что это довольно высоко, но в правильном направлении.

Теперь давайте вычислим следующий шаг градиентного спуска:

 eta = 0.001
X1=X0-eta*np.array(grad(f,X0))
print(X1)
 

Мы получаем X1 = [25.32800068 62.50001025] . Мы можем видеть, что по оси x мы фактически приближаемся к минимуму, но по оси y градиентный спуск перескочил на другую сторону от минимума и ушел еще дальше от него. Действительно, X0[1] был на расстоянии 25 от минимального ( X0[1] - Xmin[1] = 25 ) слева от него, в то время X0[1] как теперь находится на расстоянии, 65-25 = 40 но справа от него *. Поскольку кривая, нарисованная с помощью f , имеет простую U-образную форму вокруг оси y, значение, полученное с помощью f in X1 , будет выше, чем раньше (для упрощения мы игнорируем влияние координаты x).

Если мы посмотрим на следующие шаги, мы ясно увидим взрывные колебания вокруг минимального:

 X0 = [2, 0]
eta = 0.001
steps = 10

#record values taken by X[1] during gradient descent
curve_y = [X0[1]]

i = 0
while True:
    i = i   1
    X0 = X0 - eta * np.array(grad(f, X0))
    curve_y.append(X0[1])

    if np.linalg.norm(grad(f, X0)) < 10e-8 or i > steps: break

print(curve_y)
 

Мы получаем [0, 62.50001024554831, -148.43710232226067, 20719.6258707022, -35487979280.37413] . Мы можем видеть, что X1 становится все дальше и дальше от минимума, колеблясь вокруг него.

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

Обратите внимание, что градиентный спуск, который мы привели в качестве примера, делает всего 5 шагов, в то время как мы запрограммировали 10 шагов. Это связано с тем, что, когда значения, принимаемые функцией, слишком высоки, python не удается определить разницу между f(X[1]) и f(X[1] h) , поэтому он вычисляет градиент, равный нулю:

 x = 24 # for the example
y = -35487979280.37413
z = f([x, y h]) - f([x, y])
print(z)
 

Мы получаем 0.0 . Этот вопрос касается точности вычислений компьютера, но мы вернемся к этому позже.

Итак, эти колебания обусловлены сочетанием:

• очень высокое значение частичного градиента по отношению к оси y
• слишком большое значение eta этого не компенсирует взрывной градиент в обновлении.

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

 X0 = [2, 0]
# divide eta by 100
eta = 0.0001
steps = 400
xmin = descenso_grad(f, X0, eta, steps)
print(xmin)
 

Мы получим [18.25061287 23.24796497] . Возможно, нам потребуется больше шагов, но на этот раз мы сходимся!!

2) Как этого избежать?

А) В вашем конкретном случае

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

 
def grad_clipped(f, X, clip):
    grd = []
    for i in np.arange(0, len(X)):
        ai = partial(f, i   1, X)
        if ai<0:
            ai = max(ai, -1*clip)
        else:
            ai = min(ai, clip)
        grd.append(ai)
    return grd

def descenso_grad_clipped(f,X0,eta, steps, clip=100, tolerance=10e-8):

    #iterations
    i=0
    while True:
        i=i 1
        X0=X0-eta*np.array(grad_clipped(f,X0, clip))

        if np.linalg.norm(grad_clipped(f,X0, clip))<tolerance or i>steps: break
    return X0

 

Давайте протестируем это на примере расходящегося:

 X0 = [2, 0]
eta = 0.001
steps = 400
clip=100
xmin = descenso_grad_clipped(f, X0, eta, clip, steps)
print(xmin)
 

На этот раз мы сходимся : [19.31583901 24.20307188] . Обратите внимание, что это может замедлить процесс, поскольку градиентный спуск будет выполняться меньшими шагами. Здесь мы можем приблизиться к реальному минимуму, увеличив количество шагов.

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

Б) В целом

В общем, есть много предостережений, которых все алгоритмы градиентного спуска пытаются избежать (взрывающиеся или исчезающие градиенты, седловые точки, локальные минимумы …). Алгоритмы обратного распространения, такие как Adam, RMSProp, Adagrad и т. Д., Стараются избегать этих предостережений.

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

• Хорошая статья о towardsdatascience.com объяснение основ уклонов спусков и их наиболее распространенных недостатков
• Обзор алгоритмов градиентного спуска