README.md

GradientDescent

В какой-то момент я переведу текст ниже на английский язык и он будет в этом месте.

О проекте

Градиентный спуск... Вы можете спросить меня "Зачем изобретать велосипед?". Поэтому, для начала, хотелось бы сказать зачем этот проект нужен лично мне. В какой-то момент я решил заняться ML и градиент занимает здесь одно из главных мест. После первого собеседования в VK, я понял, что не до конца понимаю что это вообще такое и решил разобраться. После небольшого катарсиса я сел пописать код ручками (чтобы лучше усвоилось) и теперь делюсь результатами. Возможно, у кого-то возникают схожие с моими вопросы; поэтому, надеюсь, моя работа кому-то поможет.

Как работает

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

Задача линейной регрессии.

Пусть даны объекты $x_i$ и соответствующие им значения $y_i = k x_i + b + \epsilon$, где $\epsilon$ - шум в данных.

Нужно построить модель $f(x_i) = a_0 + a_1 x_i$, которая будет лучше всего описывать наши данные (то есть $f(x_i) \rightarrow y_i$).

Коэффициенты $a_0$ и $a_1$ представим в виде вектора:

$$A = \begin{pmatrix} a_0\\\ a_1 \end{pmatrix},$$

$x_i$ и $y_i$ соответственно:

$$X = \begin{pmatrix} 1 & x_1\\\ 1 & x_2\\\ ... & ...\\\ 1 & x_n \end{pmatrix},\quad Y = \begin{pmatrix} y_1\\\ y_2\\\ ...\\\ y_n \end{pmatrix}.$$

В таком случае $Y^* = XA, Y^* \rightarrow Y$.

Функция потерь

Существуют различные функции потерь ($loss$), которые показывают насколько "далеко" наши посчитанные значения от тех, которые должны быть. Например, можно смотреть на сумму квадратов разностей между реальными и полученными значениями $loss = \sum (y_i - y_i^*)^2$. Если разделить полученное значение на количество элементов $n$, то получим популярную функцию потерь Mean Squared Error (MSE).

Основные метрики в задачах регрессии:

• Mean Absolute Error (MAE) $= \frac{1}{n} \ast \sum |y_i - y_i^*|$
• Mean Absolute Percentage Error (MAPE) $= \frac{1}{n} \ast \sum |\frac{y_i - y_i^*}{y_i}|$
• Mean Squared Error (MSE) $= \frac{1}{n} \ast \sum (y_i - y_i^*)^2$
• Root Mean Squared Error (RMSE) $= \sqrt{\frac{1}{n} \ast \sum (y_i - y_i^*)^2}$

Градиент

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

Суть метода в том, чтобы считать градиент функции потерь и идти в обратном направлении (в сторону антиградиента), что позволит приблизиться к точке минимума функции потерь. А теперь вспомним что этого мы и хотим: найти такие коэффициенты $A$, при которых разница между реальными $Y$ и полученными значениями $Y^*$ будет минимальной.

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

$$\nabla f(x) = \begin{pmatrix} \frac{\partial f(x)}{\partial x_1} & \frac{\partial f(x)}{\partial x_2} & ... & \frac{\partial f(x)}{\partial x_n} \end{pmatrix}^T$$

В этот момент и возникла нестыковка. Изначально, мне сразу в голову приходила наша функция $f(x_i)$, коэффициенты которой мы ищем. К тому же, можно визуализировать процесс изменения функции с каждым шагом градиентного спуска, и будет видно, что есть "оптимальное" положение функции, которое мы ищем, к которому наша функция стремится. В голове возник вопрос: может градиент показывает в сторону этого оптимального положения? В этот момент я и потерялся.

Самый простой пример

А теперь стоит рассказать как дело обстоит на самом деле. Для этого рассмотрим самый простой пример, который может быть. Допустим, у нас есть одна точка $(x_1, y_1)$ и мы хотим найти такие коэффициенты $a_0$ и $a_1$, чтобы $a_1 x_1 + a_0 = y_1$. Понятно, что таких функций бесконечно много, но это сейчас не важно.

Допустим, мы находимся на каком-то промежуточном шаге и получили коэффициенты $a_0, a_1$. Посчитаем функцию потерь: $loss = (a_1 x_1 + a_0 - y_1)^2$.

Теперь поймем, что мы хотим уменьшить $loss$. А для этого будем менять коэффициенты $a_0, a_1$ (параметры модели), так как у нас $x_1, y_1$ уже зафиксированы. То есть коэффициенты и переменные поменялись ролями.

Можно нарисовать плоскость, на осях которой будут значения $a_0, a_1$. Тогда существует прямая $a_0 = y_1 - x_1 a_1$, точки которой, при подстановке в исходную функцию как коэффициенты, будут давать функции, проходящие через заданную по условию точку $(x_1, y_1)$. А для каждой точки в пространстве параметров модели, не лежащей на такой прямой, $loss > 0$, и чем дальше точка, тем больше $loss$. То есть над плоскостью, являющейся пространством параметров модели, можно нарисовать поверхность функции потерь.

Для примера с одной точкой подходит рисунок ниже:

Здесь прямая - это наши решения при поиске нужных коэффициентов. Поверхность функции потерь принимает такую форму, что в любом сечении, перпендикулярном нашей прямой, будет парабола. Если взять любую точку на прямой, $loss = 0$, иначе антиградиент будет указывать в сторону этой прямой с подходящими коэффициентами для исходной функции.

По сути, мы будем на каждом шаге строить градиент функции потерь в пространстве параметров модели и спускаться постепенно к ее минимуму. Именно этого понимания мне не хватало раньше.

Каким образом будем спускаться? Вычитая из каждого коэффициента соответствующий элемент градиента. Однако, чтобы не перескочить через точку минимума, вводят дополнительный коэффициент $0 < \lambda < 1$.

$$A_{k+1} = A_k - \lambda\ast\nabla loss_k$$

Пример с двумя точками

Поняв как это работает для одной точки, добавим еще одну. Теперь для каждой точки подходящие коэффициенты $a_0, a_1$ будут лежать на разных прямых и в их пересечении будет та, которая позволит провести прямую (исходную функцию) через обе точки; то есть в ней $loss = 0$. Поверхность функции потерь будет теперь из себя представлять параболоид.

Пример представлен на рисунке ниже:

Красной линией здесь показан процесс градиентного спуска (корректировки коэффициетов для уменьшения значения функции потерь).

Процесс изменения коэффициентов (и положения прямой соответственно) показан на рисунке ниже:

Обобщение

Рассмотрим случай с тремя точками. Если они лежат на одной прямой, то будет существовать точка в пространстве параметров модели, в которой $loss = 0$. Если не лежат, то такую прямую провести нельзя, однако можно провести прямую так, чтобы среднеквадратичная ошибка была минимальной; в таком случае, к этому набору параметров нас и будет вести градиентный спуск.

Понятно, что у нас может быть не два параметра $a_0, a_1$, а в общем случае вектор $a_0, a_1, ..., a_m$. Тут уже не получится визуализировать процесс градиентного спуска, но суть та же: с каждым шагом движемся в сторону антиградиента функции потерь в пространстве параметров модели.

Аналогично каждый объект может из себя представлять не одно значение $x_i$, а вектор. Тогда:

$$A = \begin{pmatrix} a_0\\\ a_1\\\ ...\\\ a_m \end{pmatrix},\quad X = \begin{pmatrix} 1 & x_{1, 1} & x_{1, 2} & ... & x_{1, m}\\\ 1 & x_{2, 1} & x_{2, 2} & ... & x_{2, m}\\\ ... & ... & ... & & ...\\\ 1 & x_{n, 1} & x_{n, 2} & ... & x_{n, m} \end{pmatrix},\quad Y = \begin{pmatrix} y_1\\\ y_2\\\ ...\\\ y_n \end{pmatrix}.$$

Тут также $Y^* = XA, Y^* \rightarrow Y$. Градиент будет набором $m$ частных производных функции потерь по всем параметрам модели $a_i$.

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

Стохастический градиентный спуск

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

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

При этом, мне было не совсем понятно как именно выбрать размер выборок (batch size). Поэтому я решил подробнее изучить данный момент в этом репозитории.

Программная реализация

Проект содержит в себе следующие файлы:

• В файле data_gen.py происходит генерация данных $X, Y$.
• linear_model.py показывает процесс градиентного спуска для задачи линейной регрессии.
• loss_surface.py отрисовывает поверхность функции потерь для задачи с двумя точками.
• polynomial_model.py показывает процесс градиентного спуска для полинома второй степени (при этом можно увеличить степень, но придется уменьшить значение $\lambda$, иначе произойдет переполнение при подсчете градиента).

В процессе работы программы, в консоли выводятся также значения в формате [a0, a1]: loss. Пример:

Контакты

Вы можете найти меня здесь:

• Telegram
• VK

Также можете ознакомиться с моим резюме.