Основно съдържание

Курс: Анализ на функции на много променливи > Раздел 3

Урок 4: Оптимизиране на функции на много променливи (статии)

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

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

Преговор

Какво представлява това?

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

\nabla f = 0

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

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

f (x) = x^{2} - 4 x

, тогава можем лесно да намерим

\nabla f = 0

, за да установим, че

x = 2

минимизира

f (x)

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

x \approx 1,999 99967

. И по двата начина получаваме един и същ резултат.

Но ако формулата на функцията е сложна, тогава е много трудно и дори понякога невъзможно да се реши

\nabla f = 0

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

Какво представлява методът на градиентното спускане

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

Представи си някаква функция

f (x; y)

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

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

x_{0}

и изминем положително разстояние

α

по посока на отрицателния градиент, тогава нашето ново и подобрено

x_{1}

ще изглежда по следния начин:

x_{1} = x_{0} - α \nabla f (x_{0})

Ако обобщим, това означава, че можем да напишем формула за превръщането на

x_{n}

x_{n + 1}

x_{n + 1} = x_{n} - α \nabla f (x_{n})

Като започнем с някаква първоначална стойност

x_{0}

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

Пример 1

Да разгледаме функцията

f (x) = \frac{x^{2} \cos (x) - x}{10}

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

Ако изберем

x_{0} = 6

и стъпка

α = 0, 2

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

x_{0}

, а линиите свързват всяка точка със следващата. Само след

10

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

x = 4

Ако използваме същата стойност за

x_{0}

, но стъпката е

α = 1, 5

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

Ако започнем от

x_{0} = 7

със стъпка

α = 0, 2

, ще достигнем до съвсем различен локален минимум.

Пример 2

Да използваме метода на градиентното спускане, за да решим следната задача: Коя е най-добрата апроксимация на функцията $\sin (x)$ ‍ с полином от $5$ ‍-та степен в интервала $- 3 < x < 3$ ‍?

p (x) = a_{0} + a_{1} x + \dots + a_{5} x^{5}

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

f

. Логично е, че нашата цел е да намерим коефициентите

a_{0}, \dots, a_{5}

, за които полинома

p (x)

е максимално близък до

\sin (x)

за стойностите на

x

, принадлежащи на интервала

- 3

3

. Има много начини да превърнем това във функция, която да минимизираме. Единият от тях е така нареченият метод на най-малките квадрати:

f (a_{0}; \dots; a_{5}) = \int_{- 3}^{3} (p (x) - \sin (x))^{2} d x

Това означава, че дефинираме нашата функция

f

като сума от грешките на стойностите на полинома

p (x)

във всяка точка. Например, ако

p (x) = 2

около

x = 0

, тогава

f

ще нарасне много, защото

\sin (0) = 0

, а не на

2

. Градиентното спускане ще се опита да даде възможно най-ниската стойност на

f

, което означава стойностите на

p (x)

да са максимално близки до стойностите на

\sin (x)

. Повдигаме разликите на квадрат, така че интегралът винаги ще бъде положителен.

Ето какво се получава, ако започнем със случайни числа за

a_{0}, \dots, a_{5}

и се движим по посока на отрицателния градиент. Числото горе вляво ни показва колко стъпки сме направили досега, като използваме стъпка с размер

α = 0,001

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

\sin (x)

\begin{aligned} p (x) = & - 0,001 77 + 0,889 74 x + 0,002 87 x^{2} \\ - 0,116 13 x^{3} - 0,000 48 x^{4} + 0,002 24 x^{5} \end{aligned}

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

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

Без този момент топката ще остане на мястото на локалния минимум.

С помощта на момента намираме глобалния минимум:

Формално погледнато, тръгваме от позиция

x_{0}

със скорост

v_{0} = 0

. На всяка стъпка добавяме част от старата скорост

λ

(обикновено около

0, 9

) към новия градиент. По този начин част от съществуващия момент се запазва.

\begin{aligned} v_{n + 1} & = λ v_{n} - α \nabla f (x_{n}) \\ x_{n + 1} & = x_{n} + v_{n + 1} \end{aligned}

Ограничения

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

Едно от ограниченията на метода е това, че чрез него може да се определят само локалните минимуми, (но не и глобалният минимум). Когато алгоритъмът намери някаква точка, която е локален минимум, той може да блокира, ако размерът на стъпката не превишава размера на хлътването.

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

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

Друго ограничение на метода на градиентното спускане е свързано с размера на стъпката

α

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

Подходящият размер на стъпката бързо намалява.

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

Стъпка с голям размер, която нараства.

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

Стъпка с голям размер, която бавно намалява.

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

Малка стъпка, която се смалява бавно.

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

Градиентното спускане не работи при недиференцируеми функции.

Обобщение

Градиентното спускане е метод за минимизиране на диференцируеми функции, чиято изходна стойност е число, а аргументите им може да съдържат произволен брой променливи.
Алгоритъмът включва допускане за първоначалната стойност $x_{0}$ ‍ и последователно прилагане на формулата $x_{n + 1} = x_{n} - α \nabla f (x_{n})$ ‍. Това означава, че алгоритъмът прави малки стъпки по посока на отрицателния градиент.
Градиентното спускане не може да различава локален и глобален максимуми.
Размерът на стъпката $α$ ‍ определя дали алгоритъмът се приближава до минимума бързо или бавно, или се отдалечава от него.
Много практически задачи са свързани с минимизиране на функция.

Искаш ли да се присъединиш към разговора?

Вписване в профила

Сортирай по:

Все още няма публикации.

Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.