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

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

Градієнтні методи — це широкий клас оптимізаційних алгоритмів, які використовують не лише в машинному навчанні. В даному випадку градієнтний підхід буде розглядатись як спосіб підбору векторів синаптичних ваг ${\displaystyle w}$ в лінійному класифікаторі. Нехай ${\displaystyle y^{*}:X\to Y}$ — цільова залежність, яка відома лише на об'єктах навчальної вибірки: ${\displaystyle X^{n}=(x_{i},y_{i})_{i=1}^{n},\;y_{i}=y^{*}(x_{i})}$.

Знайдемо алгоритм ${\displaystyle a(x,w)}$, що апроксимує залежність ${\displaystyle y^{*}}$. У випадку лінійного класифікатора шуканий алгоритм має вигляд:

${\displaystyle a(x,w)=\varphi \left(\sum _{j=1}^{n}w_{j}x^{j}-w_{0}\right)}$,

де ${\displaystyle \varphi (z)}$ грає роль функції активації (в найпростішому випадку можна використовувати ${\displaystyle \varphi (z)=\operatorname {sgn}(z)}$).

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

${\displaystyle Q(w)={\frac {1}{n}}\sum _{i=1}^{n}L(a(x_{i},w),\,y_{i})\to \min _{w}}$,

де ${\displaystyle L(a,y)}$ — задана функція втрат.

Позначимо через ${\displaystyle Q_{i}(w)}$ значення функції втрат на ${\displaystyle i}$-му спостереженні. Тоді,

${\displaystyle Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w).}$

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

${\displaystyle w:=w-\eta \nabla Q(w)=w-{\frac {\eta }{n}}\sum _{i=1}^{n}\nabla Q_{i}(w),}$

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

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

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

Вхід:

• ${\displaystyle X^{n}}$ — навчальна вибірка
• ${\displaystyle \eta }$ — темп навчання
• ${\displaystyle \lambda }$ — параметр згладжування функціоналу ${\displaystyle Q}$

Вихід:

• Вектор ваг ${\displaystyle w}$

Тіло:

1. Ініціалізувати ваги ${\displaystyle w_{j}}$, (${\displaystyle j=0,\dots ,k}$, де ${\displaystyle k}$ — розмірність простору ознак);
2. Ініціалізувати поточну оцінку функціоналу:

   ${\displaystyle Q:=\sum _{i=1}^{n}L(a(x_{i},w),\,y_{i})}$;

3. Повторювати:
   1. Вибрати об'єкт ${\displaystyle x_{i}}$ із ${\displaystyle X^{n}}$ (наприклад, випадковим чином);
   2. Обчислити вихідне значення алгоритму ${\displaystyle a(x_{i},w)}$ та помилку:

      ${\displaystyle \varepsilon _{i}\,{:=}\,L(a(x_{i},w),y_{i})}$;

   3. Зробити крок градієнтного спуску:

      ${\displaystyle 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}}$;

   4. Оцінити значення функціоналу:

      ${\displaystyle Q:=(1-\lambda )Q+\lambda \varepsilon _{i}}$;

4. Поки значення ${\displaystyle Q}$ не стабілізується та/або ваги ${\displaystyle w}$ не припинять змінюватись.

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

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

• Ініціалізувати вектор ${\displaystyle w}$ нулями. Цей спосіб використовується в багатьох системах, але не завжди є найкращим.
• ${\displaystyle w_{j}:=rand\left(-{\frac {1}{k}},{\frac {1}{k}}\right)}$, де ${\displaystyle k}$ — розмірність простору ознак. Цей метод більш вдалий, ніж попередній, якщо відповідним чином нормалізувати опис ознак. (див. «Недоліки та способи боротьби з ними».)
• Ще один підхід полягає в тому, щоб вирішити вихідну задачу оптимізації у випадку статистично незалежних ознак, лінійної функції активації (${\displaystyle \varphi }$) та квадратичної функції втрат (${\displaystyle L}$). Тоді рішення має вигляд:

${\displaystyle w_{j}:={\frac {\langle y,f_{j}\rangle }{\langle f_{j},f_{j}\rangle }}}$.

В алгоритмі для оцінки функціоналу ${\displaystyle Q}$ на кожній ітерації використовується його наближене значення за методом експоненціального згладжування, звідки ${\displaystyle \lambda }$ краще брати порядку ${\displaystyle {\frac {1}{n}}}$. Якщо довжина вибірки надмірно велика, то ${\displaystyle \lambda }$ слід збільшувати.

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

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

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

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

${\displaystyle Q_{\tau }(w)=Q(w)+{\frac {\tau }{2}}||w||^{2}}$.

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

${\displaystyle w:=w(1-\eta \tau )-\eta \nabla Q(w)}$.

• Якщо функція активації має горизонтальні асимптоти, то процес може потрапити в стан «паралічу». За великих значень скалярного добутку ${\displaystyle \langle w,x_{i}\rangle }$ значення ${\displaystyle \varphi ^{\prime }}$ стає близьким до нуля і вектор ${\displaystyle w}$ перестає суттєво змінюватися. Тому звичною практикою є попередня нормалізація ознак:

${\displaystyle x^{j}:={\frac {x^{j}-x_{\min }^{j}}{x_{\max }^{j}-x_{\min }^{j}}},\;j=1,\dots ,k}$, де ${\displaystyle x_{\min }^{j},\,x_{\max }^{j}}$ — відповідно мінімальне та максимальне відхилення j-ї ознаки. Якщо при цьому ${\displaystyle w_{j}\in \left[-{\frac {1}{k}},{\frac {1}{k}}\right]}$, то ${\displaystyle \langle w,x\rangle \in [-1,1].}$

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

Як вже було сказано, збіжність в загальному випадку не гарантується, але встановлено, що у випадку опуклої функції ${\displaystyle Q(w)}$ та при виконанні таких трьох умов:

1. ${\displaystyle \eta _{t}{\xrightarrow[{t\to \infty }]{}}0\,}$;
2. ${\displaystyle \sum _{t=1}^{\infty }\eta _{t}\,=\,\infty }$;
3. ${\displaystyle \sum _{t=1}^{\infty }\eta _{t}^{2}\,<\,\infty }$

процес градієнтного спуску буде збіжним. Наприклад, можна закласти: ${\displaystyle \eta _{t}\,=\,{\frac {\eta _{0}}{t}}}$. Проте, як свідчить практика, це не дуже вдалий спосіб.

• Машинное обучение (курс лекций, К. В. Воронцов) (рос.)
• Stochastic Learning (англ.)
• Goodfellow, Ian; Bengio, Yoshua; Courville, Aaron (2016). 5.9 Stochastic gradient descent. Deep Learning. MIT Press. с. 149—150. ISBN 978-0262035613. (англ.)
• Bottou, Léon (2004), Stochastic Learning, Advanced Lectures on Machine Learning, LNAI, т. 3176, Springer, с. 146—168, ISBN 978-3-540-23122-6 (англ.)
• Buduma, Nikhil; Locascio, Nicholas (2017), Beyond Gradient Descent, Fundamentals of Deep Learning : Designing Next-Generation Machine Intelligence Algorithms, O'Reilly (англ.)
• LeCun, Yann A.; Bottou, Léon; Orr, Genevieve B.; Müller, Klaus-Robert (2012), Efficient BackProp, Neural Networks: Tricks of the Trade, Springer, с. 9—48, ISBN 978-3-642-35288-1 (англ.)
• Spall, James C. (2003), Introduction to Stochastic Search and Optimization, Wiley, ISBN 978-0-471-33052-3 (англ.)
• Використання стохастичного градієнту в C++, Boost, Ublas для лінійної регресії (англ.)
• Алгоритми машинного навчання (англ.)
• Goh (4 квітня 2017). Why Momentum Really Works. Distill.Gradient Descent, How Neural Networks Learn. 3Blue1Brown. 16 жовтня 2017 — через YouTube. Інтерактивна стаття з поясненням моментів. (англ.)

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.

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

В іншому мовному розділі є повніша стаття Stochastic gradient descent(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (серпень 2022) Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.