Метод стохастичного градієнта

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

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

Основна ідея

Градієнтні методи — це широкий клас оптимізаційних алгоритмів, які використовують не лише в машинному навчанні. В даному випадку градієнтний підхід буде розглядатись як спосіб підбору векторів синаптичних ваг ${\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}}}$. Проте, як свідчить практика, це не дуже вдалий спосіб.

Примітки

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.

Література

• Машинное обучение (курс лекций, К. В. Воронцов) (рос.)
• Stochastic Learning (англ.)
• Goodfellow, Ian; Bengio, Yoshua; Courville, Aaron (2016). 5.9 Stochastic gradient descent. Deep Learning. MIT Press. с. 149—150. ISBN . (англ.)
• (2004), Stochastic Learning, Advanced Lectures on Machine Learning, LNAI, т. 3176, Springer, с. 146—168, ISBN  (англ.)
• 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  (англ.)
• Spall, James C. (2003), Introduction to Stochastic Search and Optimization, , ISBN  (англ.)
• Використання стохастичного градієнту в C++, Boost, Ublas для лінійної регресії (англ.)
• Алгоритми машинного навчання (англ.)
• Goh (4 квітня 2017). Why Momentum Really Works. .Gradient Descent, How Neural Networks Learn. 3Blue1Brown. 16 жовтня 2017 — через YouTube. Інтерактивна стаття з поясненням моментів. (англ.)