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

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

• Метод пристосований для динамічного (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. Інтерактивна стаття з поясненням моментів. (англ.)