Как да опитомите долината - хакове без хесия за оптимизиране на големи #NeuralNetworks

Да речем, че имате дарбата за полет (или карате чопър). Вие също сте шпионин (като във филмите за Джеймс Бонд). Предоставя ви топография на дълга тясна долина, както е показано на изображението, и ви се дава точка на среща за среща с потенциален помощник, който има интелигентност, която е полезна за вашата цел. Единствената информация, която имате за мястото на среща е следната:

"Запознайте се с най-ниската координата на" тази дълга долина "за 4 часа"

Как ще намерите най-ниската координатна точка? Нещо повече, как възнамерявате да го намерите в определен срок?

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

Забележка: има много публикации, написани на хакове за оптимизация от втори ред за Neural Network. Причината, поради която реших отново да пиша за него, е, че по-голямата част от нея скача направо в сложна Математика без много обяснения.
Вместо това се опитах да обясня математиката възможно най-кратко и най-вече насочвам към подробни източници, за да научите дали не сте обучени в конкретната област на математиката.
Поради това този пост ще бъде малко по-дълъг.

В миналите публикации използвахме алгоритми на Gradient Descent, докато разпространявахме Back, които ни помогнаха да минимизираме грешките. Можете да намерите техниките в публикацията, озаглавена „Обратно размножаване - Как нервните мрежи учат сложното поведение“

Ограничения на градиентно спускане

Няма нищо лошо в алгоритъма на Gradient Descent [или Stochastic Gradient Descent (SGD) да бъдем точни]. Всъщност доказахме, че е доста ефикасно за някои от примерите на Feed Forward, които сме използвали в миналото. Проблемът с SGD възниква, когато имаме "Deep" нервни мрежи, които имат повече от един скрит слой. Особено когато мрежата е доста голяма.

Ето няколко илюстрации на немонотонна повърхност за грешка на Deep Neural Network, за да получите представа.

Повърхност за грешки - 2Повърхност за грешки - 2

Обърнете внимание, че в илюстрацията има много минимуми и максимуми. Нека да разгледаме бързо процеса на актуализиране на теглото в SGD

Актуализации на теглото на SGD

Проблемът с използването на SGD за илюстрациите е следният:

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

Нуждаем се от по-добър метод за работа с големи или дълбоки невронни мрежи.

Оптимизация на втори ред към спасителния

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

  • Градиентно спускане
  • Под-Gradient
  • Свържете градиент
  • Случайно координирано спускане

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

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

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

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

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

По-долу са някои методи от втори ред

  • Метод на Нютон
  • Квази-Нютон, Гаус-Нютон
  • BFGS, (L) BFGS

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

Йо! Нютон, какъв е твоят метод?

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

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

Нека да кажем, че имаме функция f (x) = 0 и имаме първоначално решение x_0, което смятаме, че е неоптимално. Тогава методът на Нютон ни предлага да направим следното

  1. Намерете уравнението за допирателната линия при x_0
  2. Намерете точката, в която допирателната линия пресича оста x и наречете тази нова точка като x_1.
  3. Намерете проекцията на x_1 върху функцията f (x) = 0, която също е при x_1.
  4. Сега повторете повторение от стъпка 1, като замените x_0 с x_1.

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

5. Ако x_n (текущата стойност на x) е равна или по-малка от праг, тогава спираме.

Ето изображението, което изобразява горното:

Намиране на оптимална стойност на X с помощта на метода на Нютон.

Ето една анимация, която показва същото:

кредит за анимация

Полином от първа степен, Едномерно:

Ето математиката за функция, която е полином от първа степен с едноизмерност.

Втори степен-полином, Едномерно

Сега можем да работим върху приближението на Нютон за функция на полином от втора степен (оптимизации от втори ред) с едноизмерна (преди да стигнем до множество измерения). Полиномът от втора степен има квадратичен характер и ще се нуждае от производно от втори ред, за да работи. За да работим върху втората производна на функция, използваме приближението на Тейлър, както следва:

Втори степен-полином, многоизмерност

Да предположим, че ние работим върху полином от втора степен с множество измерения, тогава работим със същия подход на Нютон, както установихме по-горе, но заменяме първите производни с градиент, а вторите производни с хесиански, както следва:

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

Конкретно в случай на Невронна мрежа, Хесианът е квадратна матрица с броя на редовете и колоните, равен на общия брой параметри в Невронната мрежа.

Мрежата Hessian for Neural изглежда по следния начин:

Хесионова матрица на невронна мрежа

Защо теоретично подходът, базиран на Хесия, е по-добър от SGD?

Сега, оптимизацията от втория ред, използвайки метода на Нютон за итеративно намиране на оптималното „x“, е хитър хак за оптимизиране на повърхността на грешката, защото за разлика от SGD, където поставяте равнина в точката x_0 и след това определяте стъпаловидното скачане, при оптимизация от втори ред намираме плътно прилягаща квадратна крива при x_0 и директно намираме минимумите на кривината. Това е изключително ефективно и бързо.

Но !!! Емпирично обаче, можете ли да си представите как да изчислите Хесиан за мрежа с милиони параметри? Разбира се, той става много неефективен, тъй като количеството съхранение и изчисления, необходими за изчисляване на хесеца, също е в квадратичен ред. Така че, макар и на теория, това е страхотно, на практика това е гадно.

За хака се нуждаем! И отговорът изглежда се крие в Conjugate Gradients.

Свържете градиентите, умен трик.

Всъщност има няколко метода на квадратично приближение за изпъкнала функция. Но методът Conjugate Gradient работи доста добре за симетрична матрица, които са положителни. Всъщност Conjugate Gradients са предназначени да работят с много големи, оскъдни системи.

Обърнете внимание, че хесецът е симетричен около диагонала, параметрите на Невронната мрежа обикновено са оскъдни, а Хесианът на невронната мрежа е положително определен (Значение има само положителни собствени стойности). Момче, имаме ли късмет?

Ако се нуждаете от задълбочено въвеждане на методите на конюгатните градиенти, преминете през документа, озаглавен „Въведение в метода на конюгатния градиент без агонизиращата болка“ от Джонатан Ричард Шевчук. Намирам това за доста задълбочено и полезно. Бих ви препоръчал да изучавате статията в свободно време, за да придобиете задълбочено разбиране на конюгатните градиенти.

Най-лесният начин да се обясни конюгатният градиент (CG) е следният:

  • CG Descent е приложим при всякаква квадратна форма.
  • CG използва стойност на алфа 'в стъпка, подобна на SGD, но вместо фиксирана алфа, ние намираме алфата чрез алгоритъм за търсене на линия.
  • CG също се нуждае от „бета“ скаларна стойност, която помага да се намери следващата посока, която е „свързана“ към първата посока.

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

За решаване на уравнение Ax = b можем да използваме следния алгоритъм:

имидж кредит
  • Тук r_k е остатъчната стойност,
  • p_k е конюгатният вектор и,
  • x_k + 1 се итеративно актуализира с предишна стойност x_k и точков продукт на стъпка-размер alpha_k и конюгиран вектор p_k.

Като имаме предвид, че знаем как да изчислим Gradient Conjugate, нека разгледаме техниката за безплатна Hessian оптимизация.

Алгоритъм за оптимизация без Хесия

Сега, след като разбрахме алгоритъма на CG, нека разгледаме последния хитър хак, който ни позволява да се освободим от хесеца.

ЦИТАЦИЯ: Оптимизацията без Хесия е техника, възприета от Нейронните мрежи от Джеймс Мартен от Университета в Торонто в документ, озаглавен „Дълбоко учене чрез свободна оптимизация на Хесия“.

Да започнем с разширение на функция от Тейлър от втори ред:

Тук трябва да намерим най-добрия delta_x и след това да преминем към x + delta_x и да поддържаме итерация до сближаване. С други думи, стъпките в оптимизацията без Хесия са следните:

алгоритъм:

  1. Започнете с i = 0 и повторете
  2. Нека x_i е някакъв първоначален под-оптимален x_0, избран на случаен принцип.
  3. В момента x_n, като се има предвид разширението на Тейлър, показано по-горе, изчислете градиент на f (x_n) и хесиан на f (x_n)
  4. Като се има предвид разширението на Taylor, изчислете следващия x_n + 1 (който не е нищо друго освен delta_x), използвайки алгоритъма Conjugate Gradient.
  5. Повторете стъпки 2–4, докато текущият x_n се сближи.

Ключовото разбиране: Обърнете внимание, че за разлика от метода на Нютон, където е необходим хесианец за изчисляване на x_n + 1, в алгоритъма, свободен от Хесия, не ни е необходим хесиецът за изчисляване на x_n + 1. Вместо това използваме конюгатния градиент.

Clever Hack: Тъй като Hessian се използва заедно с вектор x_n, просто се нуждаем от приближение на Hessian, заедно с вектора, и НЕ се нуждаем от точния Hessian. Приближаването на Хесиан с Вектор е много по-бързо от изчисляването на самия Хесиан. Проверете следното разсъждение.

Погледнете отново хесеца:

Хесионова матрица на невронна мрежа

Тук i-тият ред съдържа частични производни на формата

Където „i“ е индексът на реда, а „j“ е индексът на колоните. Оттук произвеждат точков продукт на матрицата на Хесия и всеки вектор:

Горното дава производна посока на „e“ по отношение на „w“ в посока „v“.

Използвайки ограничени разлики, можем да оптимизираме горепосоченото, както следва:

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

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

За да разберете въздействието на техниката за оптимизация, проверете следната илюстрация.

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

Очевидно не е лесно да бъдеш шпионин ...