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

Градиент

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

где x = [x1, x2, …, xn]^T, а n — количество переменных.

Свойства градиентов

Некоторые свойства градиента включают в себя:

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

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

Ассоциативное свойство. Ассоциативное свойство градиентов утверждает, что градиент составной функции равен градиенту внутренней функции, оцениваемому на выходе внешней функции, умноженному на градиент оцениваемой внешней функции. на том же выходе.

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

Градиент квадратичной формы. Градиент квадратичной формы x^T A x относительно x равен (A + A^T) x, где A — симметричная матрица.

Градиент произведения Адамара. Произведение Адамара, также известное как поэлементное произведение двух функций, определяется как точечное произведение значений функций в заданной точке. Если f(x) и g(x) две функции, их произведение Адамара обозначается как h(x) = f(x) * g(x). Градиент произведения Адамара двух функций можно рассчитать с помощью цепного правила дифференцирования, и результатом будет поэлементная сумма произведения каждой функции и ее градиента.

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

Регрессия

Регрессия — это статистический метод, используемый для моделирования связи между зависимой переменной и одной или несколькими независимыми переменными. Он используется для прогнозирования зависимой переменной на основе значений независимых переменных.

Пусть X — матрица независимых переменных, а Y — вектор зависимых переменных. Цель регрессии — найти линейную зависимость между X и Y, представленную вектором коэффициентов θ.

В этом уравнении h_θ(x_i) представляет функцию гипотезы для i-го экземпляра с учетом вектора признаков x_i и коэффициентов θ. Символ шляпы (^) используется для обозначения расчетного или прогнозируемого значения.

Уравнение h_θ(x_i) = θ^T x_i показывает, что прогнозируемое значение получается путем скалярного произведения вектора признаков x_i и коэффициентов θ. Это приводит к скалярному значению, которое представляет прогнозируемое значение для зависимой переменной. Ошибки прогнозов измеряются с помощью функции потерь L = y_i — y^.

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

Чтобы найти оптимальное значение вектора коэффициентов θ*, нам нужно найти индекс функции потерь

Затем оценочные коэффициенты можно использовать для прогнозирования новых данных.

Норма L2 является обычным выбором функции стоимости, где

То же самое уравнение может быть представлено в закрытой форме или в нормальной форме как:

Также можно показать, что оптимальное значение коэффициента равно:

Предостережения:

  1. Вычисление обратной матрицы имеет кубическую временную сложность.
  2. (X^T.X) должен иметь полный ранг, чтобы быть обратимым.

Градиентный спуск

Наконец, теперь мы можем математически понять алгоритм градиентного спуска.

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

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

Математически градиентный спуск можно записать так:

где:

  • θ_j — j-й параметр в векторе параметров θ
  • J(θ) — функция стоимости
  • ∇_θ J(θ) — градиент функции стоимости по параметрам θ
  • α — скорость обучения, скаляр, определяющий размер шага для каждой итерации.
  • m - количество обучающих примеров

Градиент функции стоимости по параметрам можно рассчитать с помощью цепного правила дифференцирования. Например, в линейной регрессии функция стоимости представляет собой среднеквадратичную ошибку:

Можно найти градиент этой функции стоимости:

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

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

Сходимость может быть достигнута, если выполняется одно из следующих условий:

  1. градиент становится нулевым
  2. алгоритм достиг максимального количества итераций
  3. изменение коэффициентов в последовательных итерациях очень незначительно (~ 0,00001)
  4. изменение функции стоимости очень незначительно в последовательных итерациях (~ 0,00001)

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

Градиентный спуск — простой и эффективный алгоритм оптимизации для многих задач, но он также имеет некоторые недостатки и ограничения. Некоторые из основных недостатков градиентного спуска:

  1. Скорость сходимости. Градиентный спуск может сходиться медленно, особенно для сложных и многомерных функций стоимости. На скорость сходимости также может влиять выбор скорости обучения и наличие локальных минимумов.
  2. Локальные минимумы. Градиентный спуск чувствителен к наличию локальных минимумов в функции стоимости, что может привести к застреванию в неоптимальном решении. Чтобы смягчить эту проблему, были разработаны различные варианты градиентного спуска, такие как стохастический градиентный спуск, мини-пакетный градиентный спуск и оптимизация импульса.
  3. Гиперпараметры. Градиентный спуск требует установки скорости обучения, которую сложно настроить. Если скорость обучения слишком высока, алгоритм может колебаться и не сходиться, а если скорость обучения слишком низкая, скорость сходимости может быть очень низкой.
  4. Требуется масштабирование. Градиентный спуск предполагает, что объекты имеют одинаковый масштаб, поэтому перед применением алгоритма необходимо нормализовать входные данные. Если данные не масштабированы должным образом, скорость сходимости может быть низкой или алгоритм может вообще не сходиться.
  5. Чувствителен к инициализации: начальное предположение параметров может сильно повлиять на сходимость алгоритма, особенно если функция стоимости невыпуклая. Чтобы смягчить эту проблему, можно использовать различные методы инициализации, такие как случайная инициализация или предварительное обучение.
  6. Вычислительные затраты. Градиентный спуск — это алгоритм пакетной оптимизации, а это означает, что для оценки градиента требуется большой объем данных. Это может потребовать значительных вычислительных ресурсов и памяти, особенно для многомерных задач.
  7. Не подходит для недифференцируемых функций: градиентный спуск основан на вычислении градиента функции стоимости, что требует ее дифференцируемости. Если функция стоимости не дифференцируема, градиентный спуск нельзя использовать напрямую.
  8. Чувствителен к выбору функции стоимости. На производительность градиентного спуска может сильно повлиять выбор функции стоимости, и он может работать не для всех типов задач. Например, градиентный спуск может изо всех сил пытаться оптимизировать функции стоимости, которые сильно нелинейны или имеют много локальных минимумов.

Заключение

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

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

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

Ссылка:

  1. Симар (2023). Визуализация градиентного спуска (https://www.mathworks.com/matlabcentral/fileexchange/35389-gradient-descent-visualization), MATLAB Central File Exchange. Проверено 30 января 2023 г.