Перегляд вихідного коду сторінки Стохастичний градієнтний спуск

'''Стохастичний градієнтний спуск''' ({{lang-en|stochastic gradient descent, incremental gradient descent}})&nbsp;— [[Метод ітерації (алгоритм)|ітеративний метод]] [[Оптимізація (математика)|оптимізації]] [[Градієнтний спуск|градієнтного спуску]] за допомогою {{Нп|Стохастичне наближення|стохастичного наближення||stochastic approximation}}. Використовується для прискорення пошуку [[Функція втрат|цільової функції]] шляхом використання обмеженого за розміром [[Тренувальний набір|тренувального набору]], який вибирається випадково при кожній ітерації.

Недавня стаття<ref>{{cite journal | last = Mei | first = Song | title = A mean field view of the landscape of two-layer neural networks | journal = Proceedings of the National Academy of Sciences | volume =  | issue =  | year = 2018 | pages =  | jstor =  | doi = 10.1073/pnas.1806579115 }}</ref> недвозначно приписує розробку метода [[Герберт Роббінс|Герберту Роббінсу]] та Саттону Монро ({{lang-en|Sutton Monro}}), які описали його у статті 1951 року «Метод стохастичного наближення» ({{lang-en|A Stochastic Approximation Method}}).<ref>{{cite journal | author= [[Герберт Роббінс|Herbert Robbins]], Sutton Monro| title = A stochastic approximation method | url= https://archive.org/details/sim_annals-of-mathematical-statistics_1951-09_22_3/page/400| journal = The Annals of Mathematical Statistics| volume = 22 | issue = 3 | year = September 1951| pages =  400—407| jstor =2236626  | doi = }}</ref>

== Основна ідея ==
''[[Градієнтний спуск|Градієнтні методи]]''&nbsp;— це широкий клас [[Оптимізація (математика)|оптимізаційних]] алгоритмів, які використовують не лише в [[Машинне навчання|машинному навчанні]].
В даному випадку градієнтний підхід буде розглядатись як спосіб підбору векторів синаптичних ваг <math>w</math> в [[Лінійний класифікатор|лінійному класифікаторі]].
Нехай <math>y^*: X \to Y</math>&nbsp;— цільова залежність, яка відома лише на об'єктах [[Тренувальний набір|навчальної вибірки]]:
<math>X^n = (x_i,y_i)_{i=1}^n, \; y_i = y^*(x_i)</math>.

Знайдемо алгоритм <math>a(x, w)</math>, що [[Апроксимація|апроксимує]] залежність <math>y^*</math>.
У випадку лінійного класифікатора шуканий алгоритм має вигляд:
: <math>a(x, w) = \varphi\left(\sum_{j=1}^n w_j x^j - w_0\right)</math>,
де <math>\varphi(z)</math> грає роль ''[[Функція активації|функції активації]]'' (в найпростішому випадку можна використовувати <math>\varphi(z) = \sgn(z)</math>).

Згідно з принципом [[Мінімізація емпіричного ризику|мінімізації емпіричного ризику]], для цього достатньо вирішити оптимізаційну задачу:
: <math>Q(w) = \frac 1n \sum_{i=1}^n L(a(x_i, w), \, y_i) \to \min_w</math>,
де <math>L(a,y)</math>&nbsp;— задана [[функція втрат]].

Позначимо через <math>Q_i(w)</math> значення функції втрат на <math>i</math>-му спостереженні. Тоді,
: <math>Q(w) = \frac{1}{n}\sum_{i=1}^n Q_i(w).</math>

Для мінімізації використаємо метод ''[[Градієнтний спуск|градієнтного спуску]]''. Це покроковий алгоритм, на кожній [[Ітерація|ітерації]] якого вектор <math>w</math> змінюється в напрямку найбільшого спадання [[функціонал]]у <math>Q</math> (тобто в напрямку протилежному градієнту):
: <math>w := w - \eta \nabla Q(w)= w - \frac{\eta}{n} \sum_{i=1}^n \nabla Q_i(w),</math>
де <math>\eta</math>&nbsp;— додатній параметр, який називається ''[[Темп навчання|швидкістю навчання]]''.

Існують такі підходи в реалізації градієнтного спуску:
* ''Пакетний (batch)'', коли на кожній ітерації навчальна вибірка переглядається цілком, тільки після чого змінюється <math>w</math>. Такий підхід потребує великих обчислювальних затрат та дуже добре надається при [[Паралельні обчислення|паралельних обчисленнях]]. 
* ''[[Стохастичний процес|Стохастичний]] (stochastic/online)'', коли на кожній [[Ітерація|ітерації]] алгоритму з навчальної вибірки випадковим чином обирається лише один об'єкт. Таким чином вектор <math>w</math> налаштовується кожен раз на новобраний об'єкт.

== Алгоритм ==
'''Вхід:'''
* <math>X^n</math>&nbsp;— навчальна вибірка
* <math>\eta</math>&nbsp;— темп навчання
* <math>\lambda</math>&nbsp;— параметр згладжування функціоналу <math>Q</math>
'''Вихід:'''
* Вектор ваг <math>w</math>
'''Тіло:'''
# Ініціалізувати ваги <math>w_j</math>, (<math>j = 0, \dots, k</math>, де <math>k</math>&nbsp;— розмірність [[Простір ознак|простору ознак]]);
# Ініціалізувати поточну оцінку функціоналу:
#: <math>Q := \sum_{i=1}^n L(a(x_i, w), \, y_i)</math>;
# Повторювати:
## Вибрати об'єкт <math>x_i</math> із <math>X^n</math> (наприклад, випадковим чином);
## Обчислити вихідне значення алгоритму <math>a(x_i, w)</math> та помилку:
##: <math>\varepsilon_i \, {:=} \, L(a(x_i, w), y_i)</math>;
## Зробити крок градієнтного спуску:
##: <math>w  := w - \eta L_a^\prime \left(a(x_i, w), y_i\right) \varphi^\prime \left(\langle w, x_i\rangle\right) x_i</math>;
## Оцінити значення функціоналу:
##: <math>Q := (1 - \lambda)Q + \lambda\varepsilon_i</math>;
# Поки значення <math>Q</math> не стабілізується та/або ваги <math>w</math> не припинять змінюватись.

=== Порядок вибору об'єктів ===
Вище сказано, що у випадку стохастичного градієнтного спуску об'єкти слід обирати випадковим чином. Однак існують евристики, що направлені на покращення збіжності, які дещо модифікують звичайний випадковий вибір:
* ''Перемішування (shuffling).'' Пропонується випадково обирати об'єкти, але поперемінно з різних класів. Ідея в тому, що об'єкти з різних класів скоріше за все менш «схожі», ніж об'єкти з одного класу, тому вектор <math>w</math> буде кожного разу змінюватись сильніше.
* Можливий варіант алгоритму, коли вибір кожного об'єкта нерівноймовірний, при чому ймовірність випадення об'єкта обернено пропорційна величині помилки на об'єкті. Слід зауважити, що за такої евристики метод стає дуже чутливим до шумів.

=== Способи ініціалізації ваг ===
* Ініціалізувати вектор <math>w</math> нулями. Цей спосіб використовується в багатьох системах, але не завжди є найкращим.
* <math>w_j := rand\left(-\frac{1}{k}, \frac{1}{k}\right)</math>, де <math>k</math>&nbsp;— розмірність [[Простір ознак|простору ознак]]. Цей метод більш вдалий, ніж попередній, якщо відповідним чином нормалізувати опис ознак. (див. «[[#Недоліки та способи боротьби з ними|Недоліки та способи боротьби з ними]]».)
* Ще один підхід полягає в тому, щоб вирішити вихідну задачу оптимізації у випадку статистично незалежних ознак, лінійної функції активації (<math>\varphi</math>) та квадратичної функції втрат (<math>L</math>). Тоді рішення має вигляд:
: <math>w_j := \frac{\langle y, f_j\rangle}{\langle f_j, f_j\rangle}</math>.

=== Параметр згладжування ===
В алгоритмі для оцінки функціоналу <math>Q</math> на кожній ітерації використовується його наближене значення за методом [[експоненціальне згладжування|експоненціального згладжування]], звідки <math>\lambda</math> краще брати порядку <math>\frac{1}{n}</math>. Якщо довжина вибірки надмірно велика, то <math>\lambda</math> слід збільшувати.

=== Деякі окремі випадки алгоритму ===
Метод стохастичного градієнта (за відповідного вибору функцій активації та втрат) є узагальненням таких широко розповсюджених евристик підбору <math>w</math> та алгоритмів класифікації:
# [[ADALINE|Адаптивний лінійний елемент (ADALINE)]];
# [[Дельта-правило|Правило Хебба]];
# [[Кластеризація методом к–середніх|Алгоритм k-середніх]];
# {{нп|Квантизація навчального вектора||en|Learning Vector Quantization}} (LVQ).

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

== Недоліки та способи боротьби з ними ==
* Алгоритм може не збігатись або збігатись занадто повільно (див. «[[#Збіжність алгоритму|Збіжність алгоритму]]».)
* Як правило, функціонал <math>Q</math> має багато [[екстремум]]ів та процес градієнтного спуску може «застрягти» на одному із локальних мінімумів. Для боротьби з цим використовують техніку ''струшування коефіцієнтів ({{lang-en|jog of weights}})''. Вона полягає у тому, що при кожній стабілізації функціонала робити випадкові модифікації вектора <math>w</math> в достатньо широкому [[Окіл|околі]] поточного значення та запускати процес градієнтного спуску з нових точок.
* За великої розмірності простору ознак <math>k</math> та/або малої довжини вибірки <math>n</math> можливе перенавчання, тобто класифікація стає нестійкою, і ймовірність помилки збільшується. При цьому сильно виростає норма вектора ваг. Для боротьби з цим недоліком використовують [[Регуляризація_Тихонова|регуляризацію Тихонова]]. Він полягає в тому, щоб обмежити можливий ріст норми <math>w</math>, додавши до <math>Q(w)</math> [[Метод штрафів|штрафний доданок]]: 
: <math>Q_{\tau}(w) = Q(w) + \frac{\tau}{2}||w||^2</math>.

В результаті правило обновлення ваг приймає вигляд:
: <math>w := w(1 - \eta \tau) - \eta \nabla Q(w)</math>.
* Якщо функція активації має горизонтальні [[Асимптота|асимптоти]], то процес може потрапити в стан «[[Метод_зворотного_поширення_помилки#Параліч_мережі|паралічу]]». За великих значень скалярного добутку <math>\langle w, x_i\rangle </math> значення <math>\varphi^\prime</math> стає близьким до нуля і вектор <math>w</math> перестає суттєво змінюватися. Тому звичною практикою є попередня нормалізація ознак:
: <math>x^j := \frac{x^j - x_{\min}^j}{x_{\max}^j - x_{\min}^j}, \; j = 1, \dots, k</math>, де <math>x_{\min}^j, \, x_{\max}^j</math>&nbsp;— відповідно мінімальне та максимальне відхилення ''j''-ї ознаки. Якщо при цьому <math>w_j \in \left[-\frac{1}{k}, \frac{1}{k}\right]</math>, то <math>\langle w, x\rangle \in [-1,1].</math>

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

== Збіжність алгоритму ==
Як вже було сказано, збіжність в загальному випадку не гарантується, але встановлено, що у випадку опуклої функції <math>Q(w)</math> та при виконанні таких трьох умов:
# <math>\eta_t \xrightarrow[{t \to \infty}]{} 0 \,</math>;
# <math>\sum_{t=1}^{\infty} \eta_t \, = \, \infty</math>;
# <math>\sum_{t=1}^{\infty} \eta_t^2 \, < \, \infty</math>
процес градієнтного спуску буде збіжним. Наприклад, можна закласти: <math>\eta_t \, = \, \frac{\eta_0}{t}</math>. Проте, як свідчить практика, це не дуже вдалий спосіб.

== Примітки ==
{{reflist}}

== Література ==
* [http://www.machinelearning.ru/wiki/index.php?title=Машинное_обучение_%28курс_лекций%2C_К.В.Воронцов%29 Машинное обучение (курс лекций, К.&nbsp;В.&nbsp;Воронцов)] {{ref-ru}}
* [http://leon.bottou.org/papers/bottou-mlss-2004 Stochastic Learning] {{ref-en}}
* {{Cite book|last1=Goodfellow|first1=Ian|url=https://www.deeplearningbook.org/contents/ml.html
|title=Deep Learning|last2=Bengio|first2=Yoshua|last3=Courville|first3=Aaron|publisher=MIT Press|year=2016|isbn=978-0262035613
|author-link=Ян Ґудфелоу
|розділ=5.9 Stochastic gradient descent
|сторінки=149-150}} {{ref-en}}
* {{Citation
 | last = Bottou
 | first = Léon
 | author-link = Léon Bottou
 | contribution = Stochastic Learning
 | year = 2004
 | title = Advanced Lectures on Machine Learning
 | pages = 146–168
 | publisher = Springer
 | series = LNAI
 | volume = 3176
 | chapter-url = http://leon.bottou.org/papers/bottou-mlss-2004
 | isbn = 978-3-540-23122-6
 | ref = none
}} {{ref-en}}
* {{citation |first1=Nikhil |last1=Buduma |first2=Nicholas |last2=Locascio |year=2017 |title=Fundamentals of Deep Learning : Designing Next-Generation Machine Intelligence Algorithms |chapter=Beyond Gradient Descent |publisher=O'Reilly |chapter-url=https://www.google.com/books/edition/Fundamentals_of_Deep_Learning/80glDwAAQBAJ?hl=en&gbpv=1&pg=PA63 }} {{ref-en}}
* {{citation |first1=Yann A. |last1=LeCun |author-link=Ян ЛеКун |first2=Léon |last2=Bottou |first3=Genevieve B. |last3=Orr |first4=Klaus-Robert |last4=Müller |chapter=Efficient BackProp |title=Neural Networks: Tricks of the Trade |publisher=Springer |isbn=978-3-642-35288-1 |year=2012 |pages=9–48 |chapter-url=https://www.google.com/books/edition/Neural_Networks_Tricks_of_the_Trade/VCKqCAAAQBAJ?hl=en&gbpv=1&pg=PA9 }} {{ref-en}}
* {{Citation
 | title = Introduction to Stochastic Search and Optimization
 | first = James C.
 | last = Spall
 | publisher = [[John Wiley & Sons|Wiley]]
 | year = 2003
 | isbn = 978-0-471-33052-3
 | ref = none
}} {{ref-en}}
* [http://codingplayground.blogspot.it/2013/05/stocastic-gradient-descent.html Використання стохастичного градієнту в C++, Boost, Ublas для лінійної регресії] {{ref-en}}
* [http://studyofai.com/machine-learning-algorithms/ Алгоритми машинного навчання] {{ref-en}}
* {{cite web|url=https://distill.pub/2017/momentum/|title=Why Momentum Really Works|last=Goh|work=[[Distill (journal)|Distill]]|date=4 квітня 2017}}{{cite web |work=3Blue1Brown |title=Gradient Descent, How Neural Networks Learn |date=16 жовтня 2017 |url=https://www.youtube.com/watch?v=IHZwWFHWa-w&list=PLZHQObOWTQDNU6R1_67000Dx_ZCJB-3pi&index=2 |via=[[YouTube]] }} Інтерактивна стаття з поясненням моментів. {{ref-en}}

{{Algorithms-stub}}
{{AI-stub}}
{{Перекласти|en|дата=серпень 2022}}


{{Диференційовні обчислення}}

[[Категорія:Стохастична оптимізація]]
[[Категорія:Обчислювальна статистика]]
[[Категорія:Градієнтні методи|Стохастичного градієнта]]
[[Категорія:M-оцінки]]
[[Категорія:Алгоритми машинного навчання]]
[[Категорія:Опукла оптимізація]]
[[Категорія:Статистичні наближення]]