Выполнение наивного градиентного спуска в python

Question

Я пытаюсь реализовать очень наивный градиентный спуск в python. Однако похоже, что он переходит в бесконечный цикл. Не могли бы вы помочь мне отладить его?

y = lambda x : x**2 
dy_dx = lambda x : 2*x 
def gradient_descent(function,derivative,initial_guess): 
    optimum = initial_guess 
    while derivative(optimum) != 0: 
     optimum = optimum - derivative(optimum) 
    else: 
     return optimum 
gradient_descent(y,dy_dx,5) 

Edit:

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

y = lambda x : x**2 
dy_dx = lambda x : 2*x 
def gradient_descent(function,derivative,initial_guess): 
    optimum = initial_guess 
    while abs(derivative(optimum)) > 0.01: 
     optimum = optimum - 2*derivative(optimum) 
     print((optimum,derivative(optimum))) 
    else: 
     return optimum 
gradient_descent(y,dy_dx,5) 

Теперь я пытаюсь применить его к задаче регрессии, однако выходные данные не являются правильными, как показано на рисунке выхода:

Output of gradient descent code below

import matplotlib.pyplot as plt 
def stepGradient(x,y, step): 
    b_current = 0 
    m_current = 0 
    b_gradient = 0 
    m_gradient = 0 
    N = int(len(x)) 
    for i in range(0, N): 
     b_gradient += -(1/N) * (y[i] - ((m_current*x[i]) + b_current)) 
     m_gradient += -(1/N) * x[i] * (y[i] - ((m_current * x[i]) + b_current)) 
    while abs(b_gradient) > 0.01 and abs(m_gradient) > 0.01: 
     b_current = b_current - (step * b_gradient) 
     m_current = m_current - (step * m_gradient) 
     for i in range(0, N): 
      b_gradient += -(1/N) * (y[i] - ((m_current*x[i]) + b_current)) 
      m_gradient += -(1/N) * x[i] * (y[i] - ((m_current * x[i]) + b_current)) 
    return [b_current, m_current] 

x = [1,2, 2,3,4,5,7,8] 
y = [1.5,3,1,3,2,5,6,7] 
step = 0.00001 
(b,m) = stepGradient(x,y,step) 


plt.scatter(x,y) 
abline_values = [m * i + b for i in x] 
plt.plot(x, abline_values, 'b') 
plt.show() 

Fixed : D

import matplotlib.pyplot as plt 
def stepGradient(x,y): 
    step = 0.001 
    b_current = 0 
    m_current = 0 
    b_gradient = 0 
    m_gradient = 0 
    N = int(len(x)) 
    for i in range(0, N): 
     b_gradient += -(1/N) * (y[i] - ((m_current*x[i]) + b_current)) 
     m_gradient += -(1/N) * x[i] * (y[i] - ((m_current * x[i]) + b_current)) 
    while abs(b_gradient) > 0.01 or abs(m_gradient) > 0.01: 
     b_current = b_current - (step * b_gradient) 
     m_current = m_current - (step * m_gradient) 
     b_gradient= 0 
     m_gradient = 0 
     for i in range(0, N): 
      b_gradient += -(1/N) * (y[i] - ((m_current*x[i]) + b_current)) 
      m_gradient += -(1/N) * x[i] * (y[i] - ((m_current * x[i]) + b_current)) 
    return [b_current, m_current] 

x = [1,2, 2,3,4,5,7,8,10] 
y = [1.5,3,1,3,2,5,6,7,20] 
(b,m) = stepGradient(x,y) 


plt.scatter(x,y) 
abline_values = [m * i + b for i in x] 
plt.plot(x, abline_values, 'b') 
plt.show() 

Answer 1

Ваш while цикл останавливается только при расчете значение с плавающей запятой равно нулю. Это наивно, поскольку значения с плавающей запятой редко вычисляются точно. Вместо этого остановите цикл, когда вычисленное значение равно достаточно близко к нулю. Используйте что-то вроде

while math.abs(derivative(optimum)) > eps: 

где eps - желаемая точность расчетного значения. Это может быть сделано другим параметром, возможно, со значением по умолчанию 1e-10 или некоторыми такими.

---

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

optimum = optimum - 2*derivative(optimum) 

переместит значение из optimum ближе к фактическому оптимальному значению. В вашем конкретном случае переменная optimum просто перемещается взад и вперед между 5 (ваше начальное предположение) и -5. Отметим, что производная при 5 составляет 10, а производная при -5 составляет -10.

Поэтому вам нужно избегать такого велосипедного движения. Вы можете умножить свой дельта 2*derivative(optimum) на что-то меньшее, чем 1, которое будет работать в вашем конкретном случае y=x**2. Но в целом это не сработает.

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

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

Answer 2

Кроме того, необходимо, чтобы уменьшить размер шага (гамма в градиентной формуле спуска):

y = lambda x : x**2 
dy_dx = lambda x : 2*x 
def gradient_descent(function,derivative,initial_guess): 
    optimum = initial_guess 
    while abs(derivative(optimum)) > 0.01: 
     optimum = optimum - 0.01*derivative(optimum) 
     print((optimum,derivative(optimum))) 
    else: 
     return optimum