Градиентный спуск — метод нахождения локального экстремума. В этом «алгоритме» используется движение вдоль градиента.
Подпишись на группу Вконтакте и Телеграм-канал. Там еще больше полезного контента для программистов.
А на YouTube-канале ты найдешь обучающие видео по программированию. Подписывайся!
Нахождение локального минимума
Для этого используется следующая формула для поиска локального минимума: 𝑥𝑖+1=𝑥𝑖−𝜎𝑓′(𝑥𝑖), где 𝜎 — темп спуска
Разберём метод спуска на примере с параболой, заданной формулой: 𝑓(𝑥)=𝑥^2−3𝑥−15. Для начала построим её график:
In[1]:
from math import pi
import matplotlib.pyplot as plt
import numpy as np
import seaborn as sns
In[2]:
x = np.linspace(-8, 11, 1000)
def f(x):
return x*2 - 3x - 15
def get_plot(x, f):
sns.set()
fig = plt.figure(figsize=(14, 7))
axes = fig.subplots()
axes.plot(x, f(x), color='red')
axes.set_xlabel('x', fontsize=14)
axes.set_ylabel('y', fontsize=14)
axes.grid(True)
axes.axhline(y=0, color='black', linewidth=3)
axes.axvline(x=0, color='black', linewidth=3)
return axes
axes = get_plot(x, f)

Теперь вычислим производную от выражения, представляющего нашу параболу:
𝑓′(𝑥)=(𝑥^2−3𝑥−15)′=(𝑥^2)′−(3𝑥)′−(15)′=2𝑥−3
Заметим, что локальным минимумом является точка 𝑥0=1,5, т.е. решение уравнения 𝑓′(𝑥)=0
In[3]: def df(x): return 2*x - 3
Прекрасно. Теперь выберем начальную точку 𝑥0=−5. Реализуем функцию спуска, отображающую результат на графике функции.
In[4]: def gradient_descent_to_min(x0=0, sigma=1, f=lambda x : x, df=lambda x: 1, iters=10, axes=None): x = x0 for i in range(iters): x0 -= sigma * df(x0)if axes:
axes.scatter([x0], [f(x0)], color='blue', linewidths=3)
axes.plot([x, x0], [f(x), f(x0)], color='green')
x = x0
return x0
In[5]: axes = get_plot(x, f) gradient_descent_to_min(x0=-7, sigma=0.1, f=f, df=df, iters=15, axes=axes)

Теперь попробуем выбрать точку 𝑥0=10.
In[6]: axes = get_plot(x, f) gradient_descent_to_min(x0=10, sigma=0.1, f=f, df=df, iters=15, axes=axes)

Почему так работает?
Как мы знаем, знак 𝑓′(𝑥) в точке 𝑥0 зависит от того, спадает или возрастает функция вокрестности точки 𝑥0.
Если функция спадает, то 𝑓′(𝑥)<0, и наоборот.
Теперь рассмотрим наш пример. Если мы зафиксируем 𝑥0=−5, то производная будет иметь отрицательное значение, а это значит, что выражение x0 -= sigma*df(x0) будет только увеличивать значение 𝑥0.
В случае, когда 𝑥0=10, 𝑓′(𝑥)>0 ⇒ выражение x0 -= sigma*df(x0) будет уменьшать значение 𝑥0.
Нахождение локального максимума
Для этого используется всё та же логика, только меняется знак
Δ𝑥=(𝑥𝑖−𝑥j) (j = i + 1)
𝑥j=𝑥𝑖+𝜎𝑓′(𝑥)
Немного изменим функцию градиентного спуска:
In[7]: def gradient_descent_to_max(x0=0, sigma=1, f=lambda x : x, df=lambda x: 1, iters=10, axes=None): x = x0 for i in range(iters): x0 += sigma * df(x0)if axes:
axes.scatter([x0], [f(x0)], color='blue', linewidths=3)
axes.plot([x, x0], [f(x), f(x0)], color='green')
x = x0
return x0
Теперь протестируем наш алгоритм на функции 𝑠𝑖𝑛(𝑥/2).
In[8]: x = np.linspace(-4pi, 4pi, 1000) def f(x): return np.sin(x / 2)
Как известно, 𝑠𝑖𝑛′(𝑥/2) =0.5𝑐𝑜s(x/2).
In[9]: def df(x): return 0.5 * np.cos(x / 2)
In[10]: axes = get_plot(x, f) gradient_descent_to_max(x0=0, sigma=0.05, f=f, df=df, iters=10, axes=axes)

Здесь же мы наблюдаем проблему выбора темпа спуска. Давайте проверим результат выполнения фрагмента кода, заменив
sigma = 0.05 на sigma=0.5.
In[11]: axes = get_plot(x, f) gradient_descent_to_max(x0=0, sigma=0.5, f=f, df=df, iters=10, axes=axes)

Как мы видим, увеличение темпа спуска увеличил скорость спуска к локальному максимуму в этом варианте. Однако в некоторых случаях это только усугубит ситуацию.
Заключение
Сегодня мы разобрали основы градиентного спуска. У этого метода существует множество вариаций, многие из которых применяются в машинном обучении. Надеюсь, эта статья была вам полезна. Поздравляю всех читателей с прошедшим Новым годом!
Ссылка на файл с кодом здесь.
Также рекомендую прочитать статью Программирование графов на Python с помощью NetworkX. А также подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.