Стохастичний градієнтний спуск

Стохастичний градієнтний спуск (англ. stochastic gradient descent, incremental gradient descent) — ітеративний метод оптимізації градієнтного спуску за допомогою стохастичного наближення[en]. Використовується для прискорення пошуку цільової функції шляхом використання обмеженого за розміром тренувального набору, який вибирається випадково при кожній ітерації.

Недавня стаття[1] недвозначно приписує розробку метода Герберту Роббінсу та Саттону Монро (англ. Sutton Monro), які описали його у статті 1951 року «Метод стохастичного наближення» (англ. A Stochastic Approximation Method).[2]

Основна ідея ред.

Градієнтні методи — це широкий клас оптимізаційних алгоритмів, які використовують не лише в машинному навчанні. В даному випадку градієнтний підхід буде розглядатись як спосіб підбору векторів синаптичних ваг   в лінійному класифікаторі. Нехай   — цільова залежність, яка відома лише на об'єктах навчальної вибірки:  .

Знайдемо алгоритм  , що апроксимує залежність  . У випадку лінійного класифікатора шуканий алгоритм має вигляд:

 ,

де   грає роль функції активації (в найпростішому випадку можна використовувати  ).

Згідно з принципом мінімізації емпіричного ризику, для цього достатньо вирішити оптимізаційну задачу:

 ,

де   — задана функція втрат.

Позначимо через   значення функції втрат на  -му спостереженні. Тоді,

 

Для мінімізації використаємо метод градієнтного спуску. Це покроковий алгоритм, на кожній ітерації якого вектор   змінюється в напрямку найбільшого спадання функціоналу   (тобто в напрямку протилежному градієнту):

 

де   — додатній параметр, який називається швидкістю навчання.

Існують такі підходи в реалізації градієнтного спуску:

  • Пакетний (batch), коли на кожній ітерації навчальна вибірка переглядається цілком, тільки після чого змінюється  . Такий підхід потребує великих обчислювальних затрат та дуже добре надається при паралельних обчисленнях.
  • Стохастичний (stochastic/online), коли на кожній ітерації алгоритму з навчальної вибірки випадковим чином обирається лише один об'єкт. Таким чином вектор   налаштовується кожен раз на новобраний об'єкт.

Алгоритм ред.

Вхід:

  •   — навчальна вибірка
  •   — темп навчання
  •   — параметр згладжування функціоналу  

Вихід:

  • Вектор ваг  

Тіло:

  1. Ініціалізувати ваги  , ( , де   — розмірність простору ознак);
  2. Ініціалізувати поточну оцінку функціоналу:
     ;
  3. Повторювати:
    1. Вибрати об'єкт   із   (наприклад, випадковим чином);
    2. Обчислити вихідне значення алгоритму   та помилку:
       ;
    3. Зробити крок градієнтного спуску:
       ;
    4. Оцінити значення функціоналу:
       ;
  4. Поки значення   не стабілізується та/або ваги   не припинять змінюватись.

Порядок вибору об'єктів ред.

Вище сказано, що у випадку стохастичного градієнтного спуску об'єкти слід обирати випадковим чином. Однак існують евристики, що направлені на покращення збіжності, які дещо модифікують звичайний випадковий вибір:

  • Перемішування (shuffling). Пропонується випадково обирати об'єкти, але поперемінно з різних класів. Ідея в тому, що об'єкти з різних класів скоріше за все менш «схожі», ніж об'єкти з одного класу, тому вектор   буде кожного разу змінюватись сильніше.
  • Можливий варіант алгоритму, коли вибір кожного об'єкта нерівноймовірний, при чому ймовірність випадення об'єкта обернено пропорційна величині помилки на об'єкті. Слід зауважити, що за такої евристики метод стає дуже чутливим до шумів.

Способи ініціалізації ваг ред.

  • Ініціалізувати вектор   нулями. Цей спосіб використовується в багатьох системах, але не завжди є найкращим.
  •  , де   — розмірність простору ознак. Цей метод більш вдалий, ніж попередній, якщо відповідним чином нормалізувати опис ознак. (див. «Недоліки та способи боротьби з ними».)
  • Ще один підхід полягає в тому, щоб вирішити вихідну задачу оптимізації у випадку статистично незалежних ознак, лінійної функції активації ( ) та квадратичної функції втрат ( ). Тоді рішення має вигляд:
 .

Параметр згладжування ред.

В алгоритмі для оцінки функціоналу   на кожній ітерації використовується його наближене значення за методом експоненціального згладжування, звідки   краще брати порядку  . Якщо довжина вибірки надмірно велика, то   слід збільшувати.

Деякі окремі випадки алгоритму ред.

Метод стохастичного градієнта (за відповідного вибору функцій активації та втрат) є узагальненням таких широко розповсюджених евристик підбору   та алгоритмів класифікації:

  1. Адаптивний лінійний елемент (ADALINE);
  2. Правило Хебба;
  3. Алгоритм k-середніх;
  4. Квантизація навчального вектора[en] (LVQ).

Переваги методу ред.

  • Метод пристосований для динамічного (online) навчання, коли навчальні об'єкти надходять потоком, та потрібно швидко оновлювати вектор  .
  • Алгоритм здатен навчатись на надмірно великих вибірках за рахунок того, що випадкової підвибірки може вистачати для навчання.
  • Можливі різноманітні стратегії навчання. Якщо вибірка надмірно велика, або навчання відбувається динамічно, то є допустимим не зберігати навчальні об'єкти. Якщо вибірка маленька, то можна повторно подавати для навчання ті самі об'єкти.

Недоліки та способи боротьби з ними ред.

  • Алгоритм може не збігатись або збігатись занадто повільно (див. «Збіжність алгоритму».)
  • Як правило, функціонал   має багато екстремумів та процес градієнтного спуску може «застрягти» на одному із локальних мінімумів. Для боротьби з цим використовують техніку струшування коефіцієнтів (англ. jog of weights). Вона полягає у тому, що при кожній стабілізації функціонала робити випадкові модифікації вектора   в достатньо широкому околі поточного значення та запускати процес градієнтного спуску з нових точок.
  • За великої розмірності простору ознак   та/або малої довжини вибірки   можливе перенавчання, тобто класифікація стає нестійкою, і ймовірність помилки збільшується. При цьому сильно виростає норма вектора ваг. Для боротьби з цим недоліком використовують регуляризацію Тихонова. Він полягає в тому, щоб обмежити можливий ріст норми  , додавши до   штрафний доданок:
 .

В результаті правило обновлення ваг приймає вигляд:

 .
  • Якщо функція активації має горизонтальні асимптоти, то процес може потрапити в стан «паралічу». За великих значень скалярного добутку   значення   стає близьким до нуля і вектор   перестає суттєво змінюватися. Тому звичною практикою є попередня нормалізація ознак:
 , де   — відповідно мінімальне та максимальне відхилення j-ї ознаки. Якщо при цьому  , то  

Відзначимо, що регуляризація також є способом попередження «паралічу».

Збіжність алгоритму ред.

Як вже було сказано, збіжність в загальному випадку не гарантується, але встановлено, що у випадку опуклої функції   та при виконанні таких трьох умов:

  1.  ;
  2.  ;
  3.  

процес градієнтного спуску буде збіжним. Наприклад, можна закласти:  . Проте, як свідчить практика, це не дуже вдалий спосіб.

Примітки ред.

  1. Mei, Song (2018). A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences. doi:10.1073/pnas.1806579115.
  2. Herbert Robbins, Sutton Monro (September 1951). A stochastic approximation method. The Annals of Mathematical Statistics. 22 (3): 400—407. JSTOR 2236626.

Література ред.