Мысли и теория

Можем ли мы использовать стохастический градиентный спуск (SGD) в модели линейной регрессии?

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

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

В этой статье используется модель линейной регрессии, чтобы показать, когда допустимо использовать стохастический градиентный спуск. Затем он указывает, почему стохастический градиентный спуск может быть неэффективным, и объясняет, как оптимизатор Adam делает стохастический градиентный спуск более эффективным.

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

Чтобы узнать значения параметров для модели линейной регрессии f (x) = xᵀ · w,, где x - функции, а w - модель параметры, определите функцию потерь L (w):

и минимизировать эту функцию потерь относительно параметров модели w.

В приведенной выше формуле X и Y формируют обучающий набор данных (X, Y):

  • X - это матрица формы n × p, поэтому n точек данных, p функций .
  • Y - это матрица формы n × 1.
  • w - вектор параметров формы p × 1.

Поскольку L (w) - выпуклая функция, по умолчанию способ минимизировать ее - вычислить ее производную по w и установить для этой производной ноль, чтобы найти местоположение где L (w) - наименьшее значение. Установка производной равной нулю дает вам нормальное уравнение ниже, левая часть которого является производной:

Нормальное уравнение имеет векторную форму, потому что X и Y - матрицы, а w - вектор. Решение этого векторного уравнения для получения значений параметров:

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

На практике решение нормального уравнения может быть сложной задачей, потому что:

  1. Инверсия матрицы (XᵀX) ⁻¹ может быть дорогостоящей. X - матрица n × p, XᵀX - матрица p × p, причем p - количество функций. Инверсия матриц стоит очень дорого. В другой моей статье Разреженный и вариационный гауссовский процесс - что делать, когда объем данных велик я наглядно продемонстрировал, насколько медленным является обращение матрицы. Так что, если ваша модель имеет тысячи функций, что возможно в настоящее время, эта инверсия становится очень дорогой.
  2. Решение обычного уравнения w = (XᵀX) ⁻¹XᵀY с упоминанием полного набора обучающих данных (X, Y) должно содержать весь набор данных в памяти. Если у вас большой набор данных, вам может не хватить памяти.

Чтобы решить проблему номер 1, мы можем использовать градиентный спуск, чтобы минимизировать L (w). Алгоритму градиентного спуска требуется только вычислить градиент функции потерь. Градиент равен -2Xᵀ (Y-X · w); он не требует инверсии матрицы.

Но градиентный спуск не решает проблему номер 2. Чтобы оценить градиент -2Xᵀ (Y-X · w), алгоритм градиентного спуска по-прежнему должен хранить весь набор обучающих данных в памяти. Это связано с тем, что градиент -2Xᵀ (Y-X · w) упоминает полный набор обучающих данных (X, Y).

Чтобы решить проблему номер 2, мы можем использовать мини-пакетный стохастический градиентный спуск (который я сокращу до стохастического градиентного спуска). Стохастический градиентный спуск выбирается случайным образом с заменой некоторых точек данных из (X, Y) и используется этот образец, называемый мини-пакетом (который я сокращу до пакета), для оценки градиента. Мы можем контролировать потребление памяти, изменяя размер пакета.

Допустимость использования стохастического стохастического спуска в линейной модели

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

Давайте сначала разберемся с требованием действительности:

  1. Полный градиент - это градиент -2Xᵀ (Y-X · w). Он называется полным градиентом, потому что в нем упоминаются полные данные обучения (X, Y).
  2. Стохастический градиент - это градиент, вычисленный из пакета точек данных, выбранных из обучающих данных, скажем (Xₘ, Yₘ), где (Xₘ, Yₘ) - случайное подмножество из (X, Y).
  3. Ожидание стохастических градиентов: поскольку пакет (Xₘ, Yₘ) является случайной выборкой из полных обучающих данных, точки данных в этом пакете имеют случайность - конкретный пакет может включать в себя некоторые точки данных, а не другие. Поскольку стохастический градиент - это выражение, в котором упоминаются эти случайно выбранные точки данных, оно также становится случайным. Итак, мы можем говорить об ожиданиях этих стохастических градиентов.
  4. Только в том случае, если ожидание стохастических градиентов нашей модели линейной регрессии равно полному градиенту, стохастический градиентный спуск является допустимым методом для обучения параметрам для нашей модели.

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

Давайте представим вектор U:

где U₁, U₂, U₃ - скаляры в соответствии с их определением Uᵢ = Yᵢ-Xᵢ · w. U - функция от w, потому что в нем упоминается w.

Доказательство действительности

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

Если быть более точным:

  • На каждом этапе оптимизации алгоритм стохастического градиента выбирает один пакет и вычисляет стохастический градиент функции потерь, используя этот пакет.
  • Мы хотим показать, что на этом этапе, если бы мы должны были нарисовать много пакетов и вычислить стохастический градиент для каждого из этих пакетов, ожидаемое значение (или среднее значение) этих стохастических градиентов равно полным градиентам, вычисленным с использованием полных данных обучения, при ЭТО ШАГ.

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

Полный градиент

Если вышеперечисленные шаги вам не понятны, особенно шаг (2), пожалуйста, посмотрите Приложение здесь.

Давайте сделаем строку (5) более явной, чтобы помочь понять полный градиент:

Таким образом, полный градиент - это вектор длины 2, по одному для каждого параметра, w₁ и w₂. Каждая строка в векторе представляет собой частную производную по одному параметру. Эта строка суммирует один столбец в X - столбец, соответствующий параметру модели по дифференцированному, то есть столбец 1 в X для w₁, столбец 2 для w₂.

Например, первая строка - это градиент относительно первого параметра w₁. Этот градиент суммирует Xᵢ, ₁ · Uᵢ для всех 3 точек данных i = 1, 2, 3. Это можно записать так:

Я ввел имя G_first, чтобы обозначить первую строку полного градиента для последующего использования.

Запятая в Xᵢ, ₁ предназначена для четкого разделения буквы и числа, т. Е. i ссылается на размер строки X матрица, а 1 ссылается на размер столбца. Если индексы обоих измерений являются числами, я просто пишу X₁₂ без запятой.

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

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

Давайте определим пакет m как набор индексов обучающих данных в этом пакете. Например, если в пакете m есть две точки данных (X ₁, Y₁) и (X₃, Y₃), тогда m = {1, 3}, где 1 - индекс первой точки данных, а 3 - индекс третьей точки данных.

Функция потерь, вычисленная с использованием этого пакета и обозначенная Lₘ (w), равна:

Следуя тем же шагам, что и при вычислении полного градиента, стохастический градиент для этого пакета равен:

Если мы запишем последнюю строку более подробно:

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

Обязательства по доказательству

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

Как было сказано ранее, мы можем представить пакет m как {j₁, j₂,…, jₘ}. Каждый индекс, например j₁, является случайной величиной из равномерного распределения Uniform (1, n), поскольку каждый элемент в пакете может ссылаться на любую точку обучающих данных с равной вероятностью. .

Первая строка стохастического градиента, то есть частная производная по первому параметру w₁, :

В приведенном выше выражении упоминаются j, индексы из пакета m. Поскольку каждый индекс j является случайной величиной, весь стохастический градиент также является случайной величиной. Этот градиент упоминает m случайных величин: j₁, j₂,…, jₘ.

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

нижний индекс «j, 1»:

  • Часть «j» означает j-ю строку в обучающих данных X. Помните, что j - это целое число, указывающее на одну точку данных из набора обучающих данных, который выбирается в пакет.
  • Часть «1» означает 1-й столбец X. Это потому, что мы говорим о производной потерянной функции по первому параметру w₁.

Например, поскольку наш X:

когда j = 3,

И в

часть нижнего индекса j₁ ссылается на индекс в пакете m = {j₁, j₂,…, jₘ}.

То же значение индексов в Uⱼ.

Ожидание стохастических градиентов

Теперь давайте рассчитаем математическое ожидание приведенных выше стохастических градиентов для параметра w₁. Математическое ожидание относится к случайной величине j₁, j₂,…, jₘ:

Строка (1) - это обозначение математического ожидания стохастических градиентов для параметра w₁. Обозначение показывает, что математическое ожидание относится к случайным величинам j₁, j₂,…, jₘ. При вычислении ожиданий (по сути, среднего) очень важно знать, по каким случайным величинам вы усредняете.

Линия (2) подставляет формулу стохастического градиента.

Строка (3) переписывает одно большое ожидание в m маленьких ожиданий, используя свойство линейности ожидания.

Строка (4) отбрасывает ненужные случайные величины в этих маленьких ожиданиях, потому что каждое маленькое ожидание упоминает только одну случайную переменную - первое маленькое ожидание упоминает случайную переменную j₁, второе маленькое ожидание упоминает j₂ и так далее.

Строка (5) - это ключ. Обратите внимание, что все эти m маленькие ожидания имеют одинаковую структуру, с той лишь разницей, что в них упоминается случайная величина. Также обратите внимание, что все эти случайные величины j₁, j₂,…, jₘ относятся к одному и тому же равномерному распределению Uniform (1, n). Значит, ценности всех этих маленьких ожиданий должны быть одинаковыми. Мы можем использовать значение первого небольшого ожидания для представления этого же значения. Есть m небольших ожиданий, поэтому вся формула упрощается до m раз больше значения первого небольшого ожидания. Это упрощение дает нам формулу с единственной случайной величиной j₁.

Строка (6) j₁ - случайная величина из неформального распределения Uniform (1, n). Математическое ожидание выражения относительно j₁ - это среднее значение этого выражения, усредненное по всем возможным значениям j₁. Все возможные значения j₁ равны 1, 2, 3,…, n с равной вероятностью.

Строка (7) упрощает формулу из Строки (6), добавляя имя G_first, которое мы ввели для представления полного градиента.

Доказательство провалилось?

Теперь мы доказали, что математическое ожидание первой строки стохастического градиента для параметра w₁ не равно первой строке полного градиента. G_first.

Но мы можем умножить этот стохастический градиент на n / m, чтобы создать стохастический градиент, ожидание которого равно G_first.

Итак, мы доказали, что стохастический градиент применим к нашим моделям для обучения параметрам - нам просто нужно масштабировать исходный стохастический градиент на n / m, чтобы превратить стохастический градиент в несмещенную оценку полного градиента . Интуитивно это означает, что нам нужно увеличить (чтобы стохастический градиент стал больше) исходный стохастический градиент, чтобы противостоять тому факту, что этот стохастический градиент вычисляется из подмножества всех точек обучающих данных.

Приведенное выше доказательство относится к градиенту по первому параметру w₁. Доказательства для других параметров такие же.

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

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

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

Вы можете спросить, существуют ли модели, для которых стохастический градиентный спуск не является допустимым алгоритмом обучения параметрам? да. Например, регрессионная модель гауссовского процесса и модель вариационного гауссовского процесса. Обе модели требуют полных обучающих данных (X, Y) для их целевой функции, чтобы найти оптимальные значения параметров модели. Только в модели разреженного и вариационного гауссовского процесса целевая функция превращается в форму, которая принимает пакет данных.

Стохастический градиентный спуск может быть неэффективным

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

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

Давайте воспользуемся следующей иллюстрацией, чтобы указать на это: левая сторона показывает направления полных градиентов; справа - стохастические градиенты. Оба они начинают с внешних кругов и движутся к внутренним кругам. Внешние кружки представляют собой значения функции высоких потерь, внутренние кружки представляют собой более низкие значения функции потерь. И градиентный спуск, и стохастический градиентный спуск перемещаются от внешнего к внутреннему, что означает, что они оба минимизируют функцию потерь.

Мы это видим:

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

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

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

Адам - ​​сглаживание стохастического градиента

Адам улучшает два аспекта алгоритма стохастического градиентного спуска:

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

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

Экспоненциальное сглаживание

Для данной последовательности необработанных значений r₁, r₂, r₃,… экспоненциально сглаженная последовательность s₁, s₂, s₃,…, определяется следующим образом:

В приведенном выше определении β называется коэффициентом сглаживания. На следующей диаграмме показано влияние экспоненциального сглаживания на необработанные данные черным цветом. Красная кривая сглажена с коэффициентом β = 0,5. Синяя кривая: β = 0,9.

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

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

Оптимизатор Адама

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

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

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

Предположим, у нас есть параметр p, w₁ to w ₚ, в момент t (т. Е. t-я оптимизация step), правило обновления для i-го параметра wᵢ:

куда:

  • wᵢ, ₜ - это обновленное значение параметра для i-го параметра wᵢ в момент времени t.
  • wᵢ, ₜ ₋ ₁ - значение того же параметра wᵢ в предыдущий раз t-1.
  • g ᵢ, ₜ - градиент wᵢ в момент времени t.
  • α - скорость обучения.

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

Правило обновления параметров в алгоритме Адама

В алгоритме Адама правило обновления для i-го параметра wᵢ:

Линия (1) сглаживает стохастические градиенты g ᵢ, ₜ с использованием коэффициента экспоненциального сглаживания β₁, обычно равного 0,9. В результате получается последовательность сглаженных стохастических градиентов mᵢ, ₁, mᵢ, ₂ и т. д. . Начальное значение mᵢ, ₀ установлено на 0.

Строка (2) - это фактическое обновление параметров с использованием сглаженного градиента mᵢ, ₜ.

Обратите внимание, что экспоненциальное сглаживание не меняет количество точек данных. То есть сглаженная последовательность имеет то же количество точек данных, что и необработанная последовательность. Смысл использования сглаженных стохастических градиентов в Адаме:

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

Адаптивная настройка скорости обучения для каждого параметра в Adam

Помимо сглаживания стохастических градиентов, Адам включает еще одно усовершенствование, которое решает проблему изменения скорости обучения для каждого параметра.

В приведенном выше правиле обновления параметров используется одинаковая скорость обучения α для всех параметров w₁, w₂ и т. Д. . Скорость обучения контролирует размер шага насколько мы меняем значение параметра при каждом обновлении параметра.

Различные параметры могут иметь разные шкалы диапазонов, один параметр может находиться в диапазоне от 1 до 100, другой - от -1000 до 2000. Одна скорость обучения вряд ли обеспечит надлежащий размер шага для всех параметров с разными масштабами.

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

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

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

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

Как и раньше, эти три формулы предназначены только для i-го параметра wᵢ.

Линия (1) - это сглаживание стохастических градиентов, как и раньше, с использованием коэффициента сглаживания β₁.

Линия (2) является новой, она сглаживает квадраты стохастических градиентов, используя коэффициент сглаживания β₂, обычно равный 0,999. Эти сглаженные последовательности представляют собой дисперсию стохастических градиентов. Начальное значение vᵢ, ₀ установлено на 0.

Строка (3) изменена, единичная скорость обучения α теперь обратно масштабируется на квадратный корень из дисперсии (что является стандартным отклонением). ε - это небольшое положительное число, чтобы избежать деления на ноль при стандартном отклонении 0. ε обычно устанавливается равным 10⁻⁸.

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

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

Выводы

В этой статье показано, как мы можем доказать, применим ли стохастический градиентный спуск к нашим моделям машинного обучения. После того, как у нас есть доказательство, мы знаем, что использование стохастического градиентного спуска является правильным. Но это не обязательно эффективно. Затем эта статья коснулась оптимизатора Adam и объясняет, как он делает стохастический градиентный спуск более эффективным.

Поддержите меня

Если вам понравится моя история, я буду благодарен, если вы подумаете о поддержке меня, став участником Medium по этой ссылке: https://jasonweiyi.medium.com/membership.

Я буду продолжать писать эти истории.