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

*Тази статия има 2 части (текстов документ и примери за код), примерите за код за методите са достъпни на тази връзка: https://github.com/alevalve/Optimization_ML_Methods

Въведение

Математиката е област, която присъства във всеки аспект от човешкия живот. От началото на първите математически теореми, създадени от Архимед, Платон, Питагор до най-новите математици като Нютон и Лайбниц.

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

С увеличаването на инструментите за машинно обучение необходимостта от нови оптимизации, които преобразуват различни ситуации, които нямат права линейна връзка, стана по-често срещана в общността. Следователно модели като Xgboost, Neural Networks и други, които имат тези типове характеристики, стават по-използвани през последните години.

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

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

Y = mX + b + e

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

m = наклон

x = предиктор

b = очаквано пресичане при 0

e = грешка

Хиперравнина R² и R³

DeepAI, s.f

Има много връзки между данни, които не могат да бъдат монтирани от линия, следователно е необходимо да се прилагат различни трансформации. При традиционните регресионни методи е възможно да се приложи логаритмична, квадратична или кубична трансформация към данните като някои примери за прогнозиране на зависимата променлива. Дали обаче тези трансформации оказват влияние върху прогнозата на модела, тъй като неговата стойност се променя, така че за нещо, което трябва да прогнозира стойност въз основа на модела и няма това предвид, може да причини объркване и лошо тълкуване. За тези ситуации се появяват други методи, специално за тези отношения.

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

Най-често използваните математически методи за оптимизация в ML моделите за избягване на тези проблеми са следните:

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

A) Нютон Рафсън

Един от най-известните методи за оптимизация е Newton Raphson. Направен е от Исак Нютон и Джоузеф Рафсън. Основната цел на този алгоритъм е да оцени корена на функция, използвайки тангенса на 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 и стойностите, които зачитат функцията спрямо нейната производна в тази точка. Това е полезен метод за изчисляване, но не винаги е минимумът на функцията, следователно този метод е само основата за по-напреднали.

Методът на Нютон е „големият брат“ на алгоритъма на Гаус-Нютон; въпреки това има много разлики с Newton Raphson по отношение на своята формула и подходи.

Методът на Нютон позволява да се вземе едно първоначално число и да се изчисли следващата стъпка въз основа на Фигура 1.1, резултатът ще ни покаже допирателна точка в кривата, която е по-добро приближение към оценката на корена. Можете да продължите да итерирате формулата и да видите как стъпките ще намалят разликите между тях, когато разликата е близо до 0, можем да кажем, че коренът е оптимизиран.

Този метод обаче има някои проблеми, опитвайки се да получи резултати с някои (xo), тъй като в някои случаи може да влезе в цикъл или да не може да изчисли добре минимума на функцията, защото когато градиентът се раздели, следващата оценка ще приеме стойност, която няма да се сближи до минимума, защото е много малък. Основната причина, поради която не се използва много в машинното обучение, е, че е алгоритъм за намиране на корен по дизайн, което означава, че целта му е да намери стойността x, за която дадена функция е минимална. (Делфин, 2022)

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

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

Методът на Гаус-Нютон е опростяване или приближение на метода на Нютон, като се взема предвид втората производна. (Floater, 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

Опростена формула на Хесен

*Градиентът на Hessian Matrix F е квадратната матрица на частните производни от втори ред

Фиг. 1.8

J(t) = Транспониране на thr Jacobian

Jr = Якобиан

Методът на Gauss Newthon основно изважда Q и запазва само произведението на транспонирането на Jaconian и Jacobian. Така итерацията е следната.

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

Фиг. 1.9

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

X(k) = X точка

Jr = Якобиан

r = вектор на остатъците

T = Транспониране

-1 = Обратно

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

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

Друг аспект е, че този метод на Нютон го задава на нула, за да се финират корените, но не е обичайно да се намира най-добрата стойност при нула, има някои случаи, когато глобалният минимум е на друго място, следователно този метод позволява да се влезе в местен минимум.

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

Може би най-известният метод за оптимизация, който присъства в моделите за машинно обучение. Неговите изобретения се приписват на Луи-Коши през 1847 г., но 60 години по-късно Жак Адамар предлага подобен метод.

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

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

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

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

d/dθ = Производна на базата на θ

J(θ) = Функция на разходите въз основа на θ

Фиг. 2.0

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

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

Градиентното усилване обикновено използва функция цена/грешка, за да изчисли производното по отношение на прогнозираната променлива. Защо? Тъй като елементът, който е необходим за оптимизиране, е прогнозата на модела. Най-често срещаната функция цена/грешка е MSE за регресионни проблеми.

Функция за грешка:

Фиг. 2.1

Стъпки за намаляване и получаване на формулата за спускане:

Изчислете производната спрямо y_old (yi)

Фиг. 2.2

2. Променете yi с a y = mx+b

Фиг. 2.2

3. Модифицирайте m за действителния наклон на функцията

4. Променете y с действителната стойност на y

5. Задайте intercept на 0

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

7. Получете размера на стъпката

Фиг. 2.3

LR = Скорост на обучение

8. Изчислете новото y с разликата между старото y и размера на стъпката

Фиг. 2.4

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

След целия този процес ще можете да намерите минимумите, където функцията ще минимизира грешката, не е задължително сумата на грешката да е равна на 0, но формулата ще се опита да постигне число, където не е възможно да се намери по-малка грешка тук е конвергентното число.

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

Проблемът с Gradient Descent е, че в някои случаи алгоритъмът намира локални минимуми, а не глобалните, което е проблем, който трябва да бъде коригиран чрез промяна на скоростта на обучение или добавяне на нови членове в зависимост от първоначалното уравнение.

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

Levenberg-Marquardt е много известен метод за оптимизация. Той прилага формула, която отчита ламбда стойност, която в зависимост от нейната стойност формулата може да бъде оценена като градиентно спускане или метод на Нютон. Този начин за оптимизация има много положителни аспекти по отношение на намирането на минимума на функция, тъй като тя ще се побере според позицията на параметрите, за да се намери оптималната точка.

Формула:

Фиг. 2.4

Levenberg-Marquardt заема позиция въз основа на ламбда стойност, в зависимост от стойността, която ще реши как да се движи, за да намери оптималната стойност.

Този метод се използва главно за намиране на минимума от нелинейни функции, като тези могат да имат множество локални минимуми. Алгоритмите за напасване ще се сближат с различни локални минимуми в зависимост от стойностите на първоначалното предположение, шума от измерването и алгоритмичните параметри. Напълно подходящо и добре е да използвате най-добрата налична оценка на желаните параметри като първоначално предположение. (Гавин, 2016)

Местен Levenberg-Marquardt

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

LLM Якобианска формула:

Фиг. 2.5

np = общ брой проби

nl-1 = неврон в l-ия по-късно минус 1

Едно от най-важните предимства на този метод е, че той ще конвергира по-бързо от обикновения LM. Размерът на Jacobian позволява постигане на по-бърз резултат спрямо другия метод.

Този метод е отличен начин за изчисляване на функциите на най-малкия квадрат, където връзката на точките от данни има логаритмична крива, тъй като ще минимизира според остатъците и данните.

Има някои библиотеки в Python, които са интегрирали този алгоритъм в него, за да го използват в нелинейни проблеми на най-малките квадрати. Най-познатата от тях е библиотеката SciPy с функцията „odeint“.

E) Метод на квази-Нютон

Изчисляването на градиента и матрицата на Хесиан в методите на Нютон не гарантира конвергенция към решение, това се случва, защото е необходимо да се намалят колкото е възможно повече изчислителните разходи за изчисляване на Хесиан, следователно тези методи използват приближени градиенти, разбира се, това ще има цена по отношение на конвергенцията.

Методът на квази-Нютон предлага приближаване на обърнатата матрица на Хесен без изчисление и нейното обръщане.

Квазиформула на Нютон:

α = параметър за търсене на линия

B = приближение на Хесен

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

Методът на квази-Нютон избягва изчисляването на матрицата на Хесиан чрез изчисляване на производната спрямо предишните итерации. Този метод е известен като секантен метод, подклас на методите на квази-Нютон. Но откъде идва тази формула?

Този метод на оптимизация идва от общата формула за метода на Нютон.

Има много променливи относно методите на квази-Нютон, в тази статия ще обясним метода на Бройдън-Флетчър-Голдфарб-Шано (BFGS). Това е може би известният метод, който е създаден въз основа на метода Q-N.

Методът на квазиНютон има някои прилики с метода на Нютон, и двата имат квадратичен подход към минимума, но QN методът също има линеен подход, следователно е добре да се изчисляват минимуми, без да се страда от постигане на пясъци поради параболоидната функция.

Този метод не се използва много в машинното обучение, но има някои изследователски статии, които използват този метод в невронни мрежи, за да осигурят методи за конвергенция, знаейки, че NN няма кривина, този алгоритъм за оптимизация може да бъде добър вариант за намиране на минимумите (Jahani, Richtárik, Takáč, 2020)

Заключение

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

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

От моя гледна точка, с нарастването на невронните мрежи в различни индустрии, тези методи, които се доближават до Хесиан, ще станат най-мощни, защото ще позволят на оптимизатора да постигне точка близо до минимума, без риск да посети пясъчна точка.

В момента обаче най-важният метод, който трябва да знаете, е градиентното спускане и подобните му, много методи използват този алгоритъм за оптимизация, защото начинът е изчисление и „простотата“ в общи линии зачита останалите.