ВВЕДЕНИЕ

Градиентный спуск — это итеративный алгоритм оптимизации, который может оптимизировать многие алгоритмы машинного обучения. Это алгоритм, который находит локальный минимум дифференцируемой функции.
Как правило, алгоритм градиентного спуска пытается найти значения различных параметров итеративно, «идя вниз», пока (надеюсь) не будет достигнут минимум.

МЕТОД

Это делается с помощью следующих шагов:

Определите функцию потерь. Это функция, которую необходимо минимизировать.
2. Определите количество параметров, которые необходимо оптимизировать.
3. Определите скорость обучения. Скорость обучения определяет размер шага. Размер шага — это изменение значения параметра между итерациями.
4. Определите минимальный размер шага. Это один из критериев остановки, наряду с максимальным количеством итераций. Алгоритм остановится, когда размер шага станет меньше минимального размера шага.
5. Выберите начальное предположение для каждого параметра.
6. Вычислите значение производной от функцию потерь по каждому параметру в точке начального предположения.
7. Установите новые значения как соответствующее значение производной, умноженное на скорость обучения.
8. Вернитесь к шагу 6 и продолжайте, пока выполнен один из критериев остановки.

ПРОСТОЙ ПРИМЕР

Начнем с простого примера. Предположим, что мы пытаемся найти минимум параболы y = (x-3)².
Минимальное значение этой функции находится при x=3. Это наша функция потерь.

В этой задаче у нас есть только 1 параметр для оптимизации: x. скорость обучения, которую мы выбираем, составляет 0,1, а минимальный размер шага составляет 0,001.
Мы начнем с начальным предположением x = -5 (выбранным случайным образом) и вычислить производную функции потерь в этой точке (которая представляет собой наклон функции потерь при x = -5). Производная y по x равна:
dy/dx = 2(x-3) и если мы заменим x на -5, то получим -16. Вот как это выглядит:

Размер шага определяется путем умножения значения производной на скорость обучения: шаг = 0,1 * (-16) = -1,6, новое предположение: -5-(-1,6) ) = -3,4.
теперь еще раз вычисляем значение производной, на этот раз в точке x=-3,4, и получаем 2*(-3,4-3) = -12,8. Размер шага теперь составляет 0,1 * (-12,8) = -1,28, поэтому новое предположение: -3,4-(-1,28) = -2,12, и так далее. После 10 итераций алгоритм достиг x = 2,141:

И после 36 итераций алгоритм сходится и достигает x = 2,9968:

Что очень близко к желаемому значению, 3.
Теперь давайте проверим влияние скорости обучения. В общем, если мы выберем очень маленькую скорость обучения, алгоритм может очень медленно сходиться или даже достичь максимального количества итераций, потому что размеры шагов будут очень маленькими. С другой стороны, если мы выберем очень большую скорость обучения, алгоритм может иметь выброс или даже расходиться. На этом рисунке показано количество итераций и конечный результат в зависимости от скорости обучения для значений от 0,001 до 0,1:

Как видно, количество итераций уменьшаетсяпо мере увеличения скорости обучения, а точность увеличивается по мере увеличения скорости обучения. >. Обе кривые достигают плато, и скорость обучения должна быть установлена ​​в соответствии с требованиями к точности и желаемой скоростью. Если бы я продолжал увеличивать скорость обучения, я бы дошел до точки расхождения.
Теперь давайте проверим влияние минимального размера шага на результат алгоритма:

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

Теперь я буду использовать алгоритм градиентного спуска на менее простом примере.

ДРУГОЙ ПРИМЕР

Я попытаюсь оптимизировать коэффициенты простой модели линейной регрессии.

Линейная регрессия

Простая модель линейной регрессии с одной зависимой и одной независимой переменной определяется следующим уравнением:

где бета 0 – точка пересечения, а бета 1 – наклон подобранной линии, а эпсилон – ошибка или шум.
Цель простой линейной регрессии – подобрать наилучшую линию к данным с максимально возможной точностью. возможный. Для этого используется обычный метод наименьших квадратов (МНК). Этот метод минимизирует сумму квадратов остатков. Это делается путем дифференцирования выражения:

и вычисление значений бета0 и бета1, которые приводят производную S к нулю.
Алгоритм градиентного спуска также можно использовать для определения этих коэффициентов. Я собираюсь продемонстрировать это сейчас.

Пример градиентного спуска 2

Я буду использовать очень простой и небольшой набор данных по автострахованию в Швеции, где X — количество претензий, а Y — общая сумма выплат по всем претензиям в тысячах шведских крон. Общее количество наблюдений в этом наборе данных составляет 63.
Если я посмотрю на точечную диаграмму этих двух переменных, то на первый взгляд она кажется довольно линейной:

Из подгонки линии линейной регрессии методом МНК определяются следующие коэффициенты: beta0 ~= 19,994 и beta1~= 3,414.
Теперь я попытаюсь использовать алгоритм градиентного спуска для этих данных.
шаг 1: остаточная сумма квадратов — это моя функция потерь.
шаг 2: как упоминалось ранее, необходимо оптимизировать две переменные — точку пересечения и наклон подобранной линии.
шаг 3: мы выбрали скорость обучения, равную 0,001 (типичное значение).
> шаг 4: минимальный размер шага устанавливается равным 1e-5.
шаг 5: затем выбираются начальные предположения для точки пересечения и наклона:
beta0 = 0 и beta1 = 1. Это даже близко не к оптимальным значениям:

Теперь начинается итеративный процесс. Функция потерь

а производные по бета0 и бета1:

Затем эти значения рассчитываются путем суммирования всех наблюдений и использования первоначальных предположений коэффициентов. После нескольких итераций алгоритм расходится. Это связано с тем, что размер шага слишком велик для этой задачи. Начальное предположение далеко от оптимизированного решения, и даже после умножения на 0,001 (скорость обучения) размер шага слишком велик.
Решение этой проблемы — уменьшить скорость обучения. Я попытался использовать скорость обучения 1e-5 и минимальный размер шага 1e-6 и получил следующий результат после 8813 итераций:

Как видно, результаты очень близки друг к другу (примерно 0,3% ошибки в точке пересечения и 0,04% ошибки в наклоне).

Эти две линии очень близки друг к другу. Уменьшение минимального размера шага до 1e-5 привело к более быстрой сходимости алгоритма после 5199 итераций, но с меньшей точностью:

Это то же самое, что показано в простом примере ранее. Более высокий минимальный размер шага вызывает более быструю сходимость, но более низкую точность.

ЗАКЛЮЧЕНИЕ

Градиентный спуск — это мощный алгоритм, который можно использовать для оптимизации различных параметров. Я продемонстрировал алгоритм на очень простой параболической функции потерь, а затем на задаче линейной регрессии, где были оптимизированы два параметра.
Один из основных недостатков этого алгоритма заключается в том, что при очень большом количестве наблюдений алгоритм может потребоваться много времени до сходимости. это можно решить, используя стохастический градиентный спуск (который будет объяснен в будущем).
Другим недостатком этого алгоритма является то, что он очень чувствителен к значениям скорости обучения и минимального размера шага, и эти значения нужно выбирать тщательно.

Источник набора данных: https://college.cengage.com/mathematics/brase/understandable_statistics/7e/students/datasets/slr/frames/frame.html