Методы математической оптимизации для машинного обучения

*Эта статья состоит из 2 частей (текстовый документ и примеры кода), примеры кода по методам доступны по этой ссылке: https://github.com/alevalve/Optimization_ML_Methods

Введение

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

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

С увеличением количества инструментов ML потребность в новых оптимизациях, которые преобразуют различные ситуации, которые не имеют прямой линейной зависимости, стала более распространенной в сообществе. Поэтому в последние годы все чаще используются такие модели, как Xgboost, Neural Networks и другие, обладающие такими характеристиками.

Понять, что такое линейная модель и почему она важна при создании новых нелинейных инструментов. По сути, это отношение между 2 или более переменными, которые могут быть нанесены на гиперплоскость, необходимо признать, что гиперплоскость, по сути, является линией, наилучшим образом подходящей для данных в 3 или более n измерениях (n-1), которая основана на формула линейной регрессии (Anirudh,s.f). Тем не менее, не все отношения могут быть выражены на простой гиперплоскости из-за ее сложности, поэтому именно по этим причинам появляются нелинейные методы.

Формула линейной регрессии:

Y = mX + b + e

Y = зависимая переменная

м = уклон

х = предиктор

b = предполагаемое пересечение в 0

е = ошибка

Гиперплоскости R² и R³

DeepAI, с.ф.

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

Методы оптимизации:

Наиболее распространенные методы математической оптимизации, используемые в моделях ML, чтобы избежать этих проблем, заключаются в следующем:

Метод Ньютона
Алгоритм Гаусса-Ньютона
Метод градиентного спуска
Алгоритм Левенберга-Марквардта
Квазиньютоновский метод

А) Ньютон Рафсон

Одним из самых известных методов оптимизации является метод Ньютона Рафсона. Его создали Исаак Ньютон и Джозеф Рафсон. Основной целью этого алгоритма является оценка корня функции с использованием касательной f(x) в точке x(o), улучшение достигается там, где прямая, касательная от f(x) до x(o), пересекает x- ось. Для этого он вычисляет x(xo) минус функция f(x) в точке x(xo) по первой производной функции в точке x(xo).

Формула

Рис 1.1

Xt+1= прошлое значение для X

(▽²xf)^-1 = обратная матрица Гессе

▽xf = матрица Якоби

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

Метод Ньютона — «старший брат» алгоритма Гаусса-Ньютона; однако он имеет много отличий от Ньютона Рафсона с точки зрения формулы и подходов.

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

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

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

B) Алгоритм Гаусса-Ньютона

Метод Гаусса-Ньютона представляет собой упрощение или приближение метода Ньютона с учетом второй производной. (Поплавок, 2018).

Формула Гаусса-Ньютона основана на алгоритме метода Ньютона-Рафсона, который представляет собой упрощенную версию исходного метода Ньютона.

Рис 1.2

Xt+1 = Минимум

Xt = Фактическое значение X

f(xt) = функция в точке xt

f’(xt) = производная функции в точке xt

Основной целью метода Гаусса-Ньютона является минимизация ошибки суммы квадратов (SSE).

Для этого необходимо найти минимум следующей нелинейной функции:

Рис 1.3

Мы можем переформулировать эту функцию, минимизируя f с остатками:

Рис 1.4

Алгоритм Гаусса-Ньютона применяется к указанной выше функции, дифференцирующей по каждому x, поэтому он дает нам сумму производной ri по xj * r. Этот результат представляет собой градиент f

Рис. 1.5

* Градиент F представляет собой вектор, состоящий из частных производных функции

Рис.1.6

Jt = якобиан r

R = [r1,….rm]

Однако нам нужно снова взять производную от ri по xk, это результат, если гессиан f, который является той же формулой выше (рис. 1.3), но теперь умножает ri на вторую производную от ri по xj*xk

Формула Гессе

Рис. 1.7

Упрощенная формула Гессе

* Градиент матрицы Гессе F представляет собой квадратную матрицу частных производных второго порядка.

Рис. 1.8

J(t) = Транспонирование якобиана

младший = якобиан

Метод Гаусса-Ньютона в основном удаляет Q и сохраняет только произведение транспонирования якониана и якобиана. Таким образом, итерация следующая.

Окончательная формула

Рис. 1.9

X(k+1) = Минимум

X(k) = X точка

младший = якобиан

r = вектор остатков

T = транспонировать

-1 = Обратный

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

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

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

C) Метод градиентного спуска (повышение)

Возможно, самый «известный» метод оптимизации, присутствующий в моделях машинного обучения. Его изобретение приписывают Луи-Коши в 1847 году, но спустя 60 лет аналогичный метод предложил Жак Адамар.

Основное свойство основано на функции с несколькими переменными, определенной и дифференцируемой в точке a, затем f(x) уменьшается в направлении отрицательного градиента F, чтобы найти точку минимума, в которой будет оптимальный прогноз.

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

θ = точка пересечения

а = скорость обучения

d/dθ = производная на основе θ

J (θ) = функция стоимости, основанная на θ

Рис 2.0

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

Существует множество моделей, которые используют градиентный спуск в качестве инструмента оптимизации для уменьшения MSE (среднеквадратичной ошибки) или других функций потерь, некоторые из них: Xgboost, LightGBM, нейронные сети (другой алгоритм) и другие.

Gradient Boosting обычно использует функцию стоимости/ошибки для вычисления производной относительно прогнозируемой переменной. Почему? Потому что элементом, который необходимо оптимизировать, является предсказание модели. Наиболее распространенной функцией стоимости/ошибки является MSE для задач регрессии.

Функция ошибки:

Рис 2.1

Шаги, чтобы уменьшить и получить формулу спуска:

Вычислить производную по y_old (yi)

Рис 2.2

2. Замените yi на a y = mx+b

Рис 2.2

3. Измените m для фактического наклона функции.

4. Измените y на фактическое значение y.

5. Установите перехват на 0

6. Решите сумму квадратов остатков

7. Получите размер шага

Рис 2.3

LR = скорость обучения

8. Рассчитайте новый y с разницей между старым y и размером шага

Рис 2.4

9. Повторяйте процесс до тех пор, пока разница между точками пересечения не сойдется к числу, при котором разница является оптимальной.

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

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

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

D) Алгоритм Левенберга-Марквардта

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

Формула:

Рис 2.4

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

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

Местный Левенберг-Марквардт

В машинном обучении этот метод используется для обучения нейронных сетей, хотя это отличный метод, обычно он не работает в больших нейронных сетях, поэтому некоторые исследователи обнаружили некоторые модификации формулы с точки зрения размера Якобиена. . В основном Bilsky, Kowalczyk, Machlewska и Zurada, 2020, внесли модификацию в способ расчета якобиана. Они решают разбить J на более мелкие матрицы, уникальные для каждого нейрона.

Формула Якоби LLM:

Рис. 2.5

np = общее количество образцов

nl-1 = нейрон в l-м конце минус 1

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

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

В Python есть несколько библиотек, которые интегрировали этот алгоритм внутри себя, чтобы использовать его в нелинейных задачах наименьших квадратов. Наиболее узнаваемой является библиотека SciPy с функцией «odeint».

E) Квазиньютоновский метод

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

Метод квазиньютона предлагает аппроксимировать обращенную матрицу Гессе без вычислений и инвертировать ее.

Квазиньютоновская формула:

α = параметр поиска строки

B = приближение Гессе

▽f(x) = матрица Якоби

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

Этот метод оптимизации исходит из общей формулы метода Ньютона.

Есть много переменных в квазиньютоновских методах, в этой статье мы объясним метод Бройдена-Флетчера-Гольдфарба-Шанно (BFGS). Возможно, это знаменитый метод, созданный на основе метода Q-N.

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

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

Заключение

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

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

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

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