|
Метод градиентного спускаНа этом занятии
мы с вами рассмотрим довольно популярный алгоритм под названием «метод
градиентного спуска» или, еще говорят «метод наискорейшего спуска». Идея метода
довольно проста. Предположим, имеется дифференцируемая функция
но она используется лишь для визуализации метода градиентного спуска. В действительности функции могут быть гораздо сложнее и зависеть от произвольного числа аргументов, для которых решать системы уравнений достаточно хлопотное занятие. Или же, функция постоянно меняется и нам необходимо под нее подстраиваться для определения текущего положения точки минимума. Все эти задачи удобнее решать с позиции алгоритмов направленного поиска, например, градиентного спуска.
Итак, из рисунка
мы хорошо видим, что справа от точки экстремума x* производная
положительна, а слева – отрицательна. И это общее математическое правило для
точек локального минимума. Предположим, что мы выбираем произвольную начальную
точку
Здесь n – номер итерации работы алгоритма. Но, вы можете спросить: а где же тут градиент? В действительности, мы его уже учли чисто интуитивно, когда определяли перемещение вдоль оси абсцисс для поиска оптимальной точки x*. Но математика не терпит такой вульгарности, в ней все должно быть прописано и точно определено. Как раз для этого нужно брать не просто производную, а еще и определять направление движения, используя единичные векторы декартовой системы координат:
И градиент
функции
то есть, это будет уже направление вдоль оси ординат и направлен в сторону наибольшего увеличения функции. Соответственно, двигаясь в противоположную сторону, будем перемещаться к точке минимума x*. Конечно, в результирующей формуле алгоритма поиска этот единичный вектор не пишется, а вместо него указывается разность по оси ординат, т.к. именно вдоль нее он и направлен:
Однако у такой формулы есть один существенный недостаток: значение производной может быть очень большим и мы попросту «перескочим» через значение x* и уйдем далеко влево или вправо. Чтобы этого не происходило, производную дополнительно умножают на некоторое небольшое число λ:
которое, в общем случае, также может меняться от итерации к итерации. Этот множитель получил название шаг сходимости. Давайте, для примера, реализуем этот алгоритм на Python для случая одномерной параболы. Вначале подключим необходимые библиотеки и определим две функции: параболу
и ее производную:
import time import numpy as np import matplotlib.pyplot as plt def f(x): return x*x - 5*x + 5 def df(x): return 2*x – 5 Затем, определим необходимые параметры алгоритма и сформируем массивы значений по осям абсцисс и ординат: N = 20 # число итераций xx = 0 # начальное значение lmd = 0.1 # шаг сходимости x_plt = np.arange(0, 5.0, 0.1) f_plt = [f(x) for x in x_plt] Далее, переходим в интерактивный режим работы с графиком, чтобы создать анимацию для перемещения точки поиска минимума и создаем окно с осями графика: plt.ion() # включение интерактивного режима отображения графиков fig, ax = plt.subplots() # Создание окна и осей для графика ax.grid(True) # отображение сетки на графике Отображаем начальный график: ax.plot(x_plt, f_plt) # отображение параболы point = ax.scatter(xx, f(xx), c='red') # отображение точки красным цветом Запускаем алгоритм градиентного поиска: for i in range(N): xx = xx - lmd*df(xx) # изменение аргумента на текущей итерации point.set_offsets([xx, f(xx)]) # отображение нового положения точки # перерисовка графика и задержка на 20 мс fig.canvas.draw() fig.canvas.flush_events() time.sleep(0.02) В конце выводим найденное значение аргумента и оставляем график на экране устройства: plt.ioff() # выключение интерактивного режима отображения графиков print(xx) ax.scatter(xx, f(xx), c='blue') plt.show() Реализация алгоритма на Python (файл grad1_1.py) После запуска увидим скатывание точки к экстремуму функции. Установим значение lmd = 0.9 Увидим «перескоки» оптимального значение, то есть, неравномерную сходимость к точки минимума. А вот, если поставить параметр lmd = 1 то скатывания совсем не будет, т.к. аргумент x будет «перескакивать» точку минимума и никогда ее не достигать. Вот так параметр λ влияет на работу алгоритма градиентного спуска. Выбор шага сходимостиВажно правильно его подбирать в каждой конкретной решаемой задаче. Обычно, это делается с позиции «здравого смысла» и опыта разработчика, но общие рекомендации такие: начинать со значения 0,1 и уменьшать каждый раз на порядок для выбора лучшего,
который обеспечивает и скорость и точность подбора аргумента x. В целом, это элемент творчества и, например, можно встретить и такой вариант изменения шага сходимости:
Функция min здесь выбирает наименьшее из двух аргументов и использует его в знаменателе дроби. Это необходимо, чтобы величина шага при больших n не становилась слишком маленькой и ограничивалась величиной
где mn – некоторое заданное ограничивающее значение. Еще один прием связан с нормализацией градиента на каждом шаге работы алгоритма. В этом случае градиент функции (то есть, вектор):
приводится к единичной норме:
И уже он используется в алгоритме наискорейшего спуска:
В одномерном случае нашего примера, это, фактически означает, что вместо действительного значения градиента, берутся числа ±1:
И алгоритм в Python примет вид: xx = xx - lmd*np.sign(df(xx)) # изменение аргумента на текущей итерации Как видите, такой подход требует уменьшения величины шага сходимости, на последующих итерациях, например, так:
Получим: lmd = 1/min(i+1, mn) Результат выглядит уже лучше и при этом, мы не привязаны к значению градиента. Реализация алгоритма на Python (файл grad1_2.py) Локальный минимумЕще одной особенностью работы этого алгоритма является попадание в область локального минимума функции. Например, если взять вот такой график:
То при начальном значении x=0 получим один минимум, а, например, при x=2,5 – другой. В этом легко убедиться, если в нашей программе переписать функции: def f(x): return np.sin(x)+0.5*x def df(x): return np.cos(x) + 0.5 (последняя – это
производная: x_plt = np.arange(-5.0, 5.0, 0.1) и запустим программу. Теперь, установим начальное значение xx=2,5, снова запустим и увидим уже другую точку локального минимума. Это, наверное, основной недостаток данного алгоритма – попадание в локальный минимум. Чтобы решить эту проблему перебирают несколько разных начальных значений и смотрят: при котором был достигнуто наименьшее значение. Его и отбирают в качестве результата. Такой ход не дает нам гарантии, что действительно был найден глобальный минимум функции (иногда он может не существовать, как, например, с нашей синусоидой), но, тем не менее, это повышает наш шанс найти лучшее решение. Вот базовая теория и практика применения метода наискорейшего спуска. Видео по теме |
с точкой экстремума x*. Нам нужно
найти эту точку. Для простоты восприятия информации, предположим, что это
парабола с точкой экстремума x*. Конечно, для такого простого случая
эту точку можно очень легко определить из уравнения:
на оси абсцисс. Теперь,
смотрите, чтобы из 
). Увеличим
диапазон отображения графика:
