Самостоятельная реализация градиентного спуска по сравнению с SciPy Минимизировать - PullRequest
Новая
       12

Самостоятельная реализация градиентного спуска по сравнению с SciPy Минимизировать

1 голос
/ 13 июня 2019

Это задание для класса выпуклой оптимизации, которое я беру. Назначение выглядит следующим образом:

Реализовать алгоритм градиентного спуска с поиском по обратной линии, чтобы найти оптимальный размер шага. Ваша реализация будет сравниваться с функцией Python scipy.optimize.minimize.

Специальная функция для минимизации - это функция наименьших квадратов. Ошибка между решением, найденным библиотекой Python, и вашей реализацией должна быть меньше 0,001.

Я сделал реализацию, но значение ошибки колеблется около 1, и я искал пути ее улучшения, но у меня возникли некоторые проблемы. Вот код, который я написал:

Градиентный спуск + обратная линия поиска Реализация поиска 

import numpy as np

# Gradient descent.
def min_gd(fun, x0, grad, args=()):
    alpha = 0.3
    beta = 0.8

    delta_x = -grad(x0, *args)
    t = backtracking_line_search(fun, x0, grad, delta_x, alpha, beta, args)
    x_new = x0 + (t * delta_x)

    if np.linalg.norm(x_new) ** 2 > np.linalg.norm(x0) ** 2:
        return min_gd(fun, x_new, grad, args)
    else:
        return x_new

# Line search function returns optimal step size.
def backtracking_line_search(fun, x, grad, delta_x, alpha, beta, args=()):
    t = 1
    derprod = grad(x, *args) @ delta_x

    while fun((x + (t * delta_x)), *args) > fun(x, *args) + (alpha * t * derprod):
        t *= beta

    return t

Другие заданные функции 

import numpy as np
from scipy.optimize import minimize
import gd

# Least Squares function
def LeastSquares(x, A, b):
    return np.linalg.norm(A @ x - b) ** 2

# gradient  
def grad_LeastSquares(x, A, b):
    return 2 * ((A.T @ A) @ x - A.T @ b)

Ошибка между двумя результатами в основном рассчитывается с использованием L2-нормы.

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

Любая обратная связь приветствуется.

Редактировать

На случай, если кому-нибудь интересно, какой финальный код я написал, чтобы он работал желаемым образом: 

def min_gd(fun, x0, grad, args=()):
    alpha = 0.3
    beta = 0.8

    delta_x = -grad(x0, *args)
    t = backtracking_line_search(fun, x0, grad, delta_x, alpha, beta, args)
    x_new = x0 + (t * delta_x)

    if np.linalg.norm(grad(x_new, *args)) < 0.01:
        return x_new
    else:
        return min_gd(fun, x_new, grad, args)

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

Надеюсь, это поможет кому-нибудь в будущем.

1 Ответ

1 голос
/ 14 июня 2019

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

def min_gd(fun, x0, grad, args=()):
    alpha = 0.3
    beta = 0.8
    eps = 0.001

    x_new = x0
    delta_x = -grad(x0, *args)
    while np.linalg.norm(delta_x) > eps:
        t = backtracking_line_search(fun, x_new, grad, delta_x, alpha, beta, args)
        x_new = x_new + (t * delta_x)
        delta_x = -grad(x_new, *args)

    return x_new

, где eps - это небольшой положительный допуск.

...