Відкрити головне меню

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

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

Зміст

Основна ідеяРедагувати

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

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

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

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

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

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

 ,
де   — додатній параметр, який називається темпом навчання (learning rate).

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

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

Алгоритм Stochastic Gradient (SG)Редагувати

Вхід:

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

Вихід:

  • Вектор ваг  

Тіло:

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

Порядок вибору об'єктівРедагувати

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

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

Способи ініціалізації вагРедагувати

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

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

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

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

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

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

Переваги SGРедагувати

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

Недоліки SG та способи боротьби з нимиРедагувати

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

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

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

  1.  ;
  2.  ;
  3.  

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

ЛітератураРедагувати

  1. Машинное обучение (курс лекций, К. В. Воронцов)
  2. Stochastic Learning


  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.