Стохастично градиентно спускане е днешният стандартен метод за оптимизация за широкомащабни проблеми с машинното обучение. Използва се за обучение на широка гама от модели, от логистична регресия до изкуствени невронни мрежи. В тази статия ще илюстрираме основните принципи на градиентно спускане и стохастичен градиент с линейна регресия.
Формализиране на нашия проблем с машинното обучение
Както може би знаете, контролираното машинно обучение се състои в намирането на функция, наречена функция за вземане на решения, която най-добре моделира връзката между входни/изходни двойки данни. За да намерим тази функция, трябва да формулираме този учебен проблем в оптимизационен проблем.
Нека разгледаме следната задача: намиране на най-добрата линейна функция, която картографира входното пространство, променливата X към изходното пространство, променливата Y.
Докато се опитваме да моделираме връзката между X и Y чрез линейна функция, наборът от функции, които алгоритъмът за обучение има право да избира, е следният:
Терминът b е прихващането, наричано още bias в машинното обучение.
Този набор от функции е нашето пространство за хипотези.
Но как да изберем стойностите за параметрите a,bи как да преценим дали добро предположение ли е или не?
Ние дефинираме функция, наречена функция на загуба, която оценява нашия избор в контекста на резултата Y.
Дефинираме нашата загуба като загуба на квадрат (можехме да изберем друга функция на загуба, като абсолютната загуба):
Квадратът на загубата наказва разликата между действителния резултат y и резултата, изчислен чрез избиране на стойности за набора от параметри a,b. Тази функция на загуба оценява нашия избор по една точка, но ние трябва да оценим нашата функция за вземане на решения по всички точки на обучение.
Така изчисляваме средната стойност на квадрата на грешките: средната квадратна грешка.
където n е броят точки с данни.
Тази функция, която зависи от параметрите, дефиниращи нашето пространство на хипотезата, се нарича Емпиричен риск.
Rn(a,b) е квадратична функция на параметрите, следователно нейният минимум винаги съществува, но може да не е уникален.
В крайна сметка постигнахме първоначалната си цел: формулиране на учебния проблем в оптимизационен!
Наистина, всичко, което трябва да направим, е да намерим решаващата функция, коефициентите a, b, които минимизират този емпиричен риск.
Това би била най-добрата функция за вземане на решения, която бихме могли да създадем: нашата целева функция.
В случай на проста линейна регресия можем просто да диференцираме емпиричния риск и да изчислим коефициентите a, b, които анулират производната. По-лесно е да се използва матрична нотация за изчисляване на решението. Удобно е да включите постоянната променлива 1 в X и да запишете параметри aи b като единичен вектор β. По този начин нашият линеен модел може да се запише като:
и нашата функция на загуба става:
Векторът бета, минимизиращ нашето уравнение, може да бъде намерен чрез решаване на следното уравнение:
Нашата линейна регресия има само два предиктора (a и b), следователно X е n x 2матрица (където n е броят на наблюденията и 2 броят на предикторите). Както можете да видите, за да решим уравнението, трябва да изчислим матрицата (X^T X), след което да я обърнем.
При машинното обучение броят на наблюденията често е много голям, както и броят на предикторите. Следователно тази операция е много скъпа от гледна точка на изчисления и памет.
Алгоритъмът за градиентно спускане е итеративен алгоритъм за оптимизация, който ни позволява да намерим решението, като същевременно поддържаме ниска изчислителна сложност. Описваме как работи в следващата част на тази статия.
Гмуркане в принципа на градиентно спускане
Алгоритъмът за градиентно спускане може да се илюстрира със следната аналогия. Представете си, че сте се изгубили в планината посред нощ. Не можете да видите нищо, тъй като е тъмно и искате да се върнете в селото, разположено в дъното на долината (опитвате се да намерите локалния/глобалния минимум на функцията за средна квадратна грешка). За да оцелеете, вие разработвате следната стратегия:
- На вашето текущо местоположение усещате стръмността на хълма и намирате посоката с най-стръмен наклон. Най-стръмният наклон съответства на градиента на средната квадратна грешка.
- Следвате тази посока надолу и вървите на фиксирано разстояние и спирате, за да проверите дали все още сте в правилната посока. Това фиксирано разстояние е скоростта на обучение на алгоритъма за градиентно спускане. Ако вървите твърде дълго, можете да пропуснете селото и да се озовете на склона от другата страна на долината. Ако не ходите достатъчно, ще ви отнеме много време, за да стигнете до селото и има риск да заседнете в малка дупка (местен минимум).
- Повтаряте тези стъпки, докато не бъде изпълнен критерий, който сте фиксирали: например разликата във височината между две стъпки е много малка.
В крайна сметка ще стигнете дъното на долината или ще заседнете в местен минимум...
Сега, след като разбрахте принципа с тази алегория, нека се потопим в математиката на алгоритъма за градиентно спускане!
За намиране на параметрите a, b, които минимизират средната стойност квадратна грешка, алгоритъмът може да се приложи, както следва:
- Инициализирайте стойностите на a и b, например a=200 и b=-200
- Изчислете градиента на средната квадратна грешка по отношение на a и b. Градиентът е посоката на най-стръмния наклон на текущото местоположение.
След това актуализирайте стойностите на a и b, като извадите градиента, умножен по размера на стъпката:
с η, нашият фиксиран размер на стъпката.
Изчислете средната квадратична загуба с актуализираните стойности на a и b.
Повторете тези стъпки, докато не бъде изпълнен критерий за спиране. Например намалението на средната квадратична загуба е по-ниско от прага ϵ.
На анимацията по-долу можете да видите актуализацията на параметъра a, извършена от алгоритъма за градиентно спускане, както и напасването на нашия модел на линейна регресия:
Тъй като монтираме модел с два предиктора, можем да визуализираме процеса на алгоритъм за градиентно спускане в 3D пространство!
Градиентно спускане: ще мащабира ли това до големи данни?
При всяка итерация на алгоритъма за спускане на градиента, трябва да разгледаме всички наши точки за обучение, за да изчислим градиента.
Следователно времевата сложност на този алгоритъм е O(n). Ще отнеме много време за изчисляване на много голям набор от данни. Може би бихме могли да изчислим приблизителна оценка на градиента, вместо да разглеждаме всички точки от данни: този алгоритъм се нарича минипакетно спускане на градиент.
Минипартидно градиентно спускане се състои в използване на произволно подмножество с размер N за определяне на посоката на стъпката при всяка итерация.
- За голямо подмножество от данни получаваме по-добра оценка на градиента, но алгоритъмът е по-бавен.
- За малък поднабор от данни получаваме по-лоша оценка на градиента, но алгоритъмът изчислява решението по-бързо.
Ако използваме произволно подмножество с размер N=1, това се нарича стохастичен градиентен низход. Това означава, че ще използваме една произволно избрана точка, за да определим посоката на стъпката.
В следващата анимация синята линия съответства на стохастичен градиентен спускане, а червената е основен градиентен алгоритъм.
Надявам се, че тази статия ви е помогнала да разберете този основен алгоритъм за оптимизация, ако ви е харесал или ако имате някакви въпроси, не се колебайте да коментирате!
Можете да намерите кода, който направих за прилагане на стохастичен градиент на спускане и създаване на анимации в моя GitHub: https://github.com/baptiste-monpezat/stochastic_gradient_descent.
Можете също да намерите оригиналната публикация в моя блог: https://baptiste-monpezat.github.io/blog/stochastic-gradient-descent-for-machine-learning-clearly-explained
