Метод градиентного спуска | Оптимизация

Метод градиентного спуска

Все курсы > Оптимизация > Занятие 2

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

$$ y = w \cdot x $$

Сегодня мы научимся находить минимум функции с двумя переменными w и b и построим полноценную модель простой линейной регрессии (Simple Linear Regression).

$$ y = w \cdot x + b $$

Для этого мы напишем алгоритм, который называется методом градиентного спуска (gradient descent method). Однако перед этим мы возьмем более простую функцию и на ее примере изучим, как работает этот метод.

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

Функция нескольких переменных

Возьмем вот такую функцию потерь.

$$ f(w_1, w_2) = w_1^2 + w_2^2 $$

График этой функции можно представить в трехмерном пространстве, где по осям w1 и w2 отложены веса исходной модели, а по оси f(w1, w2) — уровень потерь при заданных весах.

Откроем ноутбук к этому занятию

Посмотрим на график этой функции.

оптимизация многомерной функции (функции нескольких переменных)

Предположим мы начали с весов в точке A с координатами (3, 4, 25). Как нам спуститься в минимум функции в точке B (0, 0, 0)? Просто двигаться в направлении обратном производной мы не можем. Ведь единственной производной, которая бы описывала все изменения нашей функции, просто не существует.

Все дело в том, что если смотреть на нашу функцию «сверху» (то есть на график изолиний или линий уровня, contour lines), то в каждой точке у нас теперь два направления, по оси w1 и по оси w2.

изолинии (линии уровня) многомерной функции

Как понять куда нам двигаться?

Частная производная

Если «заморозить» одну из переменных (то есть представить, что это константа), пусть это будет w2, мы можем найти производную по первой переменной w1.

$$ f_{w_1} = \frac{\partial f}{\partial w_1} = 2w_1 $$

Такая производная называется частной (partial derivative), потому что она описывает изменение только в первой переменной w1.

Графически, мы как бы убираем переменную w2 (получается сечение, представленное параболой) и ищем производную функции, в которой есть только переменная w1.

частная производная многомерной функции

Точно таким же образом мы поступаем со второй переменной w2. Мы замораживаем первую переменную w1 и вычисляем частную производную.

$$ f_{w_2} = \frac{\partial f}{\partial w_2} = 2w_2 $$

Теперь, взяв точку на плоскости (w1, w2), мы будем точно знать скорость изменения функции f(w1, w2) в этой точке в каждом из направлений.

Например, возьмем ту же точку A с координатами w1 = 3, w2 = 4, скорость изменения функции в первом измерении будет равна 2 x 3 = 6, во втором 2 x 4 = 8.

Нотация анализа

Вы вероятно заметили, что мы использовали две нотации (записи) частной производной. С первой мы уже знакомы по предыдущему занятию, это нотация Лагранжа.

$$ f(w) \rightarrow f'(w) $$

Вторую нотацию, нотацию Лейбница, удобнее использовать для записи частных производных.

$$ f(w_1, w_2) \rightarrow \frac{\partial f}{\partial w_1}, \frac{\partial f}{\partial w_2} $$

Она позволяет сразу увидеть, по какой переменной происходит дифференцирование.

Напомню, что запись формул (и, в частности, производной) в текстовых ячейках ноутбуков с помощью LaTeX мы изучили, когда говорили про Jupyter Notebook.

Взятие частных производных

Пошагово рассмотрим, как мы пришли к результату (2w1, 2w2). Вначале найдем производную по первой переменой w1. Вторую переменную, w2, мы будем считать константой, то есть некоторым числом.

$$ \frac{\partial f}{\partial w_1} (w_1^2 + w_2^2) $$

Первое, что бросается в глаза, это то, что у нас производная суммы, а она, как известно, равна сумме производных.

$$ \frac{\partial f}{\partial w_1} (w_1^2 + w_2^2) = \frac{\partial f}{\partial w_1} (w_1^2) + \frac{\partial f}{\partial w_1} (w_2^2) $$

Производную первого слагаемого мы найдем по правилу производной степенной функции. Второе слагаемое мы решили считать константой, а производная константы равна нулю.

$$ \frac{\partial f}{\partial w_1} (w_1^2) + \frac{\partial f}{\partial w_1} (w_2^2) = 2w_1 + 0 = 2w_1 $$

Частная производная по второй переменной находится аналогично.

Использование SymPy

Функцию diff() библиотеки SymPy можно также использовать для взятия частных производных. Вначале импортируем функцию diff() и символы x и y (мы их используем вместо w1 и w2).

Напишем функцию, которую хотим дифференцировать.

После этого мы можем находить частные производные, передав в diff() функцию для дифференцирования, а затем либо первую, либо вторую переменную.

частная производная с помощью функции diff() библиотеки SymPy по первой переменной
частная производная с помощью функции diff() библиотеки SymPy по второй переменной

Градиент

Градиент (gradient) — есть не что иное, как совокупность частных производных по каждой из независимых переменных. Его можно назвать «полной производной».

Он обозначается через греческую букву набла ∇ или оператор Гамильтона.

$$ \nabla f(w_1, w_2) = \begin{bmatrix}  \frac{\partial f}{\partial w_1} \\  \frac{\partial f}{\partial w_1} \end{bmatrix} = \begin{bmatrix}  2w_1 \\  2w_2 \end{bmatrix} $$

Еще раз посмотрим, чему равен градиент в точке (3, 4), но уже в новой записи.

$$ \nabla f(3, 4) = \begin{bmatrix}  2 \cdot 3 \\  2 \cdot 4 \end{bmatrix} = \begin{bmatrix}  6 \\  8 \end{bmatrix} $$

Как вы видите, такая функция на входе принимает два числа, а на выходе выдает вектор, также состоящий из двух чисел. В этом случае говорят о вектор-функции (vector-valued function).

Метод градиентного спуска

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

метод градиентного спуска: направление антиградиента на графике изолиний

Если мы сдвинемся на −6 по оси w1 и на −8 по оси w2, то обязательно пройдем через минимум функции. При этом, если мы сдвинемся на всю величину градиента, то «перескочим» через минимум. Именно поэтому нам нужен коэффициент скорости обучения (learning rate).

Теперь мы готовы дать определение:

Метод градиентного спуска — это способ нахождения локального минимума функции в процессе движения в направлении антиградиента. Он был предложен Огюстеном Луи Коши еще в 1847 году.

Воспользуемся этим методом для нахождения минимума приведенной выше функции. Другими словами, проделаем путь из точки А в точку B.

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

Вначале объявим необходимые функции.

Зададим исходные параметры модели.

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

Найдем минимум функции потерь.

Как мы видим, уже после ста итераций, как веса модели, так и уровень ошибки приблизились к нулю.

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

Остается посмотреть на графике, какой путь проделал наш алгоритм градиентного спуска.

путь алгоритма оптимизации методом градиентного спуска на Питоне

Промежуточные выводы

Давайте еще раз проговорим основные идеи пройденного материала.

  1. Градиент показывает скорость изменения многомерной функции по каждому из измерений (по каждой из переменных)
  2. Если «заморозить» все независимые переменные кроме одной и сделать срез, то наклон касательной к кривой среза будет значением частной производной по этому измерению.
  3. И самое важное для нас: градиент показывает направление скорейшего подъёма (возрастания) функции. Двигаясь в обратном направлении, мы придем к минимуму функции.

Простая линейная регрессия

А теперь давайте с нуля напишем нашу первую модель машинного обучения. Мы наконец-то приобрели для этого все необходимые знания. Наша модель будет по-прежнему иметь только один признак, но при этом будет учитываться не только наклон, но и сдвиг прямой.

$$ \hat{y} = w \cdot x + b $$

Данные и постановка задачи

Сегодня мы возьмем хорошо известные нам данные роста и обхвата шеи и сразу преобразуем их в массив Numpy.

Выведем эти данные на графике с помощью диаграммы рассеяния или точечной диаграммы.

точечная диаграмма роста и обхвата шеи

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

MSE

Также приведу формулу.

$$ MSE = \frac {1}{n} \sum^{n}_{i=1} (y_i-\hat{y}_i) ^2 $$

Решение методом наименьшних квадратов

Прежде чем использовать алгоритм градиентного спуска найдем аналитическое решение с помощью метода наименьших квадратов (МНК, least squares method). Для уравнения с одной независимой переменной, напомню, используется следующая формула.

$$ w = \frac {\sum_{i = 1}^{n} (x_i-\bar{x})(y_i-\bar{y})} {\sum_{i = 1}^{n} (x_i-\bar{x})^2} $$

$$ b = \bar{y}-w\bar{x} $$

Собственная модель

Давайте вычислим наклон и сдвиг прямой с помощью этой формулы на Питоне.

Также давайте реализуем этот алгоритм с помощью векторизованного кода.

Модель LinearRegression библиотеки sklearn

Надо сказать, что модель LinearRegression, которую мы использовали на вводном занятии по оптимизации и затем на занятии по линейной регрессии применяет именно МНК для минимизации MSE.

Давайте еще раз применим класс LinearRegression, чтобы убедиться в получении одинаковых результатов.

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

Позднее мы сравним этот результат с аналогичным показателем алгоритма градиентного спуска.

МНК и метод градиентного спуска

Одна из причин использования алгоритма градиентного спуска вместо МНК заключается в том, что этот алгоритм менее требователен к вычислительным ресурсам при большом объеме (количество наблюдений) и размерности (количество признаков) данных.

Кроме того, метод градиентного спуска может применяться не только в задачах линейной регрессии, но и в других алгоритмах (например, в логистической регрессии, SVM или нейросетях).

Решение методом градиентного спуска

Модель линейной регрессии и функция потерь

Начнем с того, что объявим функцию линейной модели.

Теперь давайте немного модифицируем функцию потерь и найдем половину среднеквадратической ошибки (half MSE). Обозначим нашу функцию буквой J.

$$ J_{MSE} = \frac{1}{2n} \sum_{i=1}^{n} (y_i-(wx_i+b))^2 $$

Число два в знаменателе удачно сократится с двойкой, полученной при дифференцировании степенной функции. При этом точка минимума функции не изменится.


Дополнительно замечу, что использование именно среднеквадратической, то есть усредненной на количество наблюдений, ошибки (MSE) вместо «простой» суммы квадратов отклонений (Sum of Squared Errors, SSE)

$$ J_{SSE} = \sum_{i=1} (y_i-(wx_i+b))^2 $$

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


Частные производные функции потерь

Найдем частные производные этой функции. Их будет две: одна по наклону (w), вторая по сдвигу (b). Начнем с наклона.

$$ \frac{\partial J}{\partial w} \left( \frac{1}{2n} \sum_{i=1}^{n} (y_i-(wx_i+b))^2 \right) $$

Шаг 1. Вынесем число 1/2n за скобку по правилу умножения на число. В данном случае n, то есть количество наблюдений, превратится в число, как только мы применим формулу к набору данных.

$$  \frac{\partial J}{\partial w} = \frac{1}{2n} \frac{\partial J}{\partial w} \sum_{i=1}^{n} \left( (y_i-(wx_i+b))^2 \right) $$

Шаг 2. Теперь давайте для удобства перепишем выражение в векторизованной форме. Теперь x и y будут не отдельными числами, а векторами.

$$  \frac{\partial J}{\partial w} = \frac{1}{2n} \frac{\partial J}{\partial w} \left( (y-(wx+b)) ^2 \right) $$

Шаг 3. Перед нами композиция из двух функций. Применим chain rule.

$$ \frac{\partial J}{\partial w} = \frac{1}{2n} \cdot 2(y-(wx+b)) \cdot \frac{\partial J}{\partial w} (y-(wx+b)) $$

Шаг 4. К внутренней функции мы можем применить правило суммы и разности производных.

$$ \frac{1}{2n} \cdot 2(y-(wx+b)) \cdot (0-(x+0)) $$

Замечу, что при дифференцировании внутренней функции, y превратился в ноль, потому что это константа. Одновременно переменную b мы «заморозили» и также решили считать константой.

Шаг 5. Упростим выражение.

$$ \frac{\partial J}{\partial w} = \frac{1}{\cancel{2}n} \cdot \cancel{2}-x(y-(wx+b)) = \frac{1}{n} \cdot -x(y-(wx+b)) $$

Аналогично найдем частную производную по сдвигу.

$$ \frac{\partial J}{\partial b} = \frac{1}{n} \cdot -(y-(wx+b)) $$

Здесь стоит уточнить лишь, что при нахождении производной внутренней функции мы «заморозили» переменную w.

$$ \frac{\partial J}{\partial b} \left( (y-(wx+b)) \right) = 0-(0+1)$$

В невекторизованной форме производные выглядят следующим образом.

$$ \frac{\partial J}{\partial w} = \frac{1}{n} \sum_{i=1}^{n} -x_i(y_i-(wx_i+b)) $$

$$ \frac{\partial J}{\partial b} = \frac{1}{n} \sum_{i=1}^{n} -(y_i-(wx_i+b)) $$

Поменяв слагаемые в скобках местами и умножив на $-1$, частные производные можно записать и так.

$$ \frac{\partial J}{\partial w} = \frac{1}{n} \sum_{i=1}^{n} ((wx_i+b)-y_i) \cdot x_i $$

$$ \frac{\partial J}{\partial b} = \frac{1}{n} \sum_{i=1}^{n} ((wx_i+b)-y_i) $$

Пропишем эти функции на Питоне.

Алгоритм градиентного спуска

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

Обучение модели

Применим написанную выше функцию для обучения модели. Используем следующие гиперпараметры модели:

  • количество итераций — 200 000
  • коэффициент скорости обучения — 0,01

Напомню, что гиперпараметр — это параметр, который мы задаем до обучения модели.

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

Посмотрим на результат на графике.

результат метода градиентного спуска: линия регрессии на точечной диаграмме

Кроме того, мы можем посмотреть на то, как снижался уровень ошибки с каждой последующей итерацией.

снижение уровня ошибки в процессе оптимизации, рисунок 1

Как мы видим, в первые итерации уровень ошибки снижался настолько стремительно, что последующие изменения практически незаметны. Давайте попробуем отбросить первые 150 наблюдений.

снижение уровня ошибки в процессе оптимизации, рисунок 2

И все же кажется, что после 150000 итераций ошибка перестает снижаться и можно было бы обойтись меньшим количеством шагов. На самом деле это не так.

снижение уровня ошибки в процессе оптимизации, рисунок 3

В целом подбор количества итераций и длины шага (коэффициента скорости обучения) довольно существенно влияют на качество обучения. Ближе к концу занятия мы рассмотрим этот момент более подробно.

Оценка качества модели

Оценим качество модели с помощью встроенной в sklearn метрики.

Результат очень близок к тому, который мы получили, используя МНК.

Визуализация шагов алгоритма оптимизации

Мы также как и раньше, можем посмотреть на путь, пройденный алгоритмом оптимизации.

путь алгоритма градиентного спуска, трехмерный график

Мы также можем построить график изолиний («вид сверху»).

путь алгоритма градиентного спуска, график изолиний

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

Про выбор гиперпараметров модели

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

Коэффициенты довольно сильно отличаются от найденных ранее значений. Посмотрим на графике изолиний, где остановился наш алгоритм.

настройка гиперпараметров модели линейной регрессии, изменение количества итераций

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

настройка гиперпараметров модели линейной регрессии, изменение шага

В данном случае, так как мы делали слишком маленькие шаги, то продвинулись еще меньше.

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

Подведем итог

В первой части занятия мы посмотрели как применить понятие производной к многомерной функции, познакомились с понятием градиента и методом градиентного спуска. Во второй части мы построили модель простой линейной регрессии и оптимизировали ее с помощью метода наименьших квадратов и алгоритма градиентного спуска.

Вопросы для закрепления

Вопрос. Что такое градиент?

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

Вопрос. Какие гиперпараметры существенно влияют на качество оптимизации модели линейной регрессии?

Ответ: количество итераций и коэффициент скорости обучения

Логичным продолжением будет построение модели многомерной или множественной линейной регрессии (multiple linear regression) с несколькими признаками. Однако прежде будет полезно еще раз в деталях изучить взаимосвязь переменных.


Ответы на вопросы

Вопрос. Почему если умножить функцию потерь на число, в частности на 1/2, точка ее минимума не изменится?

Ответ. Давайте посмотрим на график параболы и параболы, умноженной на 1/2.

умножение функции потерь на число

Как мы видим, точка минимума не изменилась.

При этом обратите внимание на то, что изменился наклон (значение градиента). Эффект умножения функции потерь на число аналогичен измененению коэффициента скорости обучения (learning rate). Чем круче наклон, тем большие по размеру шаги мы будем делать.


Вопрос. Скажите, а как работает функция np.meshgrid()?

Ответ. Функция np.meshgrid() на входе принимает одномерные массивы и создает двумерный массив с привычной прямоугольной (декартовой) системой координат.

функция np.meshgrid() библиотеки Numpy

Обратите внимание, начало координат находится в левом нижнему углу.


Вопрос. Функция plt.fill_between() заполняет пространство между двумя функциями, но не очень понятно, какие параметры мы ей передаем.

Ответ. Функция np.fill_between(x, y1, y2 = 0) принимает три основных параметра: координаты по оси x, координаты по оси y (первая функция, y1) и координаты по оси y (вторая функция, y2) и заполняет пространство между y1 и y2. Параметр y2 не является обязательным. Если его не указывать, будет заполняться пространство между линией y1 и осью x (то есть функцией y = 0).

В конце ноутбука⧉ я привел два примера, когда параметр y2 не указывается, то есть равен 0, и когда y2 задает отличную от нуля функцию.