Backpropagation

Метод зворотного поширення помилки (англ. backpropagation) — метод навчання багатошарового перцептрону. Це ітеративний градієнтний алгоритм, який використовується з метою мінімізації помилки роботи багатошарового перцептрону та отримання бажаного виходу. Основна ідея цього методу полягає в поширенні сигналів помилки від виходів мережі до її входів, в напрямку, зворотному прямому поширенню сигналів у звичайному режимі роботи. Для можливості застосування методу зворотного поширення помилки функція активації нейронів повинна бути диференційовною.

Функція оцінки роботи мережі

Навчання нейронних мереж можна представити як задачу оптимізації. Оцінити — означає вказати кількісно, добре чи погано мережа вирішує поставлені їй завдання. Для цього будується функція оцінки. Вона, як правило, явно залежить від вихідних сигналів мережі і неявно (через функціонування) — від всіх її параметрів. Найпростіший і найпоширеніший приклад оцінки — сума квадратів відстаней від вихідних сигналів мережі до їх необхідних значень: ${\displaystyle H={\frac {1}{2}}\sum _{\tau \in v_{out}}(Z(\tau )-Z^{*}(\tau ))^{2}}$, де ${\displaystyle Z^{*}(\tau )}$ — необхідне значення вихідного сигналу.

Метод найменших квадратів далеко не завжди є найкращим вибором оцінки. Ретельне конструювання функції оцінки дозволяє на порядок підвищити ефективність навчання мережі, а також одержувати додаткову інформацію — «рівень впевненості» мережі у відповіді

Опис алгоритму

Архітектура багатошарового перцептрону

Алгоритм зворотного поширення помилки застосовується для багатошарового перцептрону. У мережі є множина входів ${\displaystyle x_{1},...,x_{n}}$, множина виходів Outputs і безліч внутрішніх вузлів. Перенумеруємо всі вузли (включаючи входи і виходи) числами від 1 до N (наскрізна нумерація, незалежно від топології шарів). Позначимо через ${\displaystyle w_{i,j}}$ вагу зв'язку, що з'єднує i-й і j-й вузли, а через ${\displaystyle o_{i}}$ — вихід i-го вузла. Якщо нам відомий навчальний приклад (правильні відповіді мережі ${\displaystyle t_{k}}$, ${\displaystyle k\in Outputs}$), то функція помилки, отримана за методом найменших квадратів, виглядає так:

${\displaystyle E(\{w_{i,j}\})={\cfrac {1}{2}}\sum _{k\in Outputs}(t_{k}-o_{k})^{2}.}$

Як модифікувати ваги? Ми будемо реалізовувати стохастичний градієнтний спуск, тобто будемо підправляти ваги після кожного навчального прикладу і, таким чином, «рухатися» в багатовимірному просторі ваг. Щоб «добратися» до мінімуму помилки, нам потрібно «рухатися» в сторону, протилежну градієнту, тобто, на підставі кожної групи правильних відповідей, додавати до кожної ваги ${\displaystyle w_{i,j}}$

${\displaystyle \Delta w_{i,j}=-\eta {\frac {\partial E}{\partial w_{i,j}}}}$,

де ${\displaystyle 0<\eta <1}$ — множник, що задає швидкість «руху».

Похідна розраховується таким чином. Нехай спочатку ${\displaystyle j\in Outputs}$, тобто вага, яка нас цікавить, входить в нейрон останнього рівня. Спочатку зазначимо, що ${\displaystyle w_{i,j}}$ впливає на вихід мережі лише як частина суми ${\displaystyle S_{j}=\sum _{i}w_{i,j}x_{i}}$, де сума береться по входах j-го вузла. Тому

${\displaystyle {\cfrac {\partial E}{\partial w_{i,j}}}={\cfrac {\partial E}{\partial S_{j}}}{\cfrac {\partial S_{j}}{\partial w_{i,j}}}=x_{i}{\cfrac {\partial E}{\partial S_{j}}}}$

Аналогічно, ${\displaystyle S_{j}}$ впливає на загальну помилку тільки в рамках виходу j-го вузла ${\displaystyle o_{j}}$ (нагадуємо, що це вихід всієї мережі). Тому

${\displaystyle {\cfrac {\partial E}{\partial S_{j}}}={\cfrac {\partial E}{\partial o_{j}}}{\cfrac {\partial o_{j}}{\partial S_{j}}}=\left({\cfrac {\partial }{\partial o_{j}}}{\cfrac {1}{2}}\sum _{k\in Outputs}(t_{k}-o_{k})^{2}\right)\left({\cfrac {\partial \sigma (S_{j})}{\partial S_{j}}}\right)=\left({\cfrac {1}{2}}{\cfrac {\partial }{\partial o_{j}}}(t_{j}-o_{j})^{2}\right)(o_{j}(1-o_{j}))=-o_{j}(1-o_{j})(t_{j}-o_{j}),}$

де ${\displaystyle \sigma ()}$ — це функція активації, у даному випадку (стосовно обчислення похідної) являє собою Експоненційну сигмоїду (функцію Фермі) розглянуту вище

Якщо ж j-й вузол — не на останньому рівні, то у нього є виходи; позначимо їх через Children (j). У цьому випадку

${\displaystyle {\cfrac {\partial E}{\partial S_{j}}}=\sum _{k\in Children(j)}{\cfrac {\partial E}{\partial S_{k}}}{\cfrac {\partial S_{k}}{\partial S_{j}}}}$,

і

${\displaystyle {\cfrac {\partial S_{k}}{\partial S_{j}}}={\cfrac {\partial S_{k}}{\partial o_{j}}}{\cfrac {\partial o_{j}}{\partial S_{j}}}=w_{i,j}{\cfrac {\partial o_{j}}{\partial S_{j}}}=w_{i,j}o_{j}(1-o_{j})}$.

А ${\displaystyle {\cfrac {\partial E}{\partial S_{k}}}}$ — це аналогічна поправка, але обчислена для вузла наступного рівня (будемо позначати її через ${\displaystyle \delta _{k}}$ — від ${\displaystyle \Delta _{k}}$ вона відрізняється відсутністю множника ${\displaystyle (-\eta x_{i,j})}$. Оскільки ми навчилися обчислювати поправку для вузлів останнього рівня і виражати поправку для вузла нижчого рівня через поправки більш високого, можна вже створювати алгоритм навчання. Саме через цю особливість обчислення поправок цей алгоритм називається алгоритмом зворотного поширення помилки (англ. backpropagation).

Коротке викладення вищесказаного:

• Для вузла останнього рівня

${\displaystyle \delta _{j}=-o_{j}(1-o_{j})(t_{j}-o_{j})}$

• Для внутрішнього вузла мережі

${\displaystyle \delta _{j}=o_{j}(1-o_{j})\sum _{k\in Outputs(j)}\delta _{k}w_{j,k}}$

• Для всіх вузлів

${\displaystyle \Delta w_{i,j}=-\eta \delta _{j}x_{i}}$

Отриманий алгоритм представлений нижче. На вхід алгоритму, крім зазначених параметрів, потрібно також подавати в якому-небудь форматі структуру мережі. На практиці дуже гарні результати показують мережі досить простої структури, що складаються з двох рівнів нейронів — прихованого рівня (hidden units) і нейронів-виходів (output units), кожен вхід мережі з'єднаний з усіма прихованими нейронами, а результат роботи кожного прихованого нейрона подається на вхід кожному з нейронів-виходів. У такому випадку досить подавати на вхід кількість нейронів прихованого рівня.

Алгоритм

Алгоритм: BackPropagation ${\displaystyle (\eta ,\alpha ,\{x_{i}^{d},t^{d}\}_{i=1,d=1}^{n,m},NUMBER\_OF\_STEPS)}$

1. Ініціалізувати ${\displaystyle \{w_{ij}\}_{i,j}}$ маленькими випадковими значеннями, ${\displaystyle \{\Delta w_{ij}\}_{i,j}=0}$
2. Повторити NUMBER_OF_STEPS раз:

   Для всіх d від 1 до m:

   1. Подати ${\displaystyle \{x_{i}^{d}\}}$ на вхід сітки і підрахувати виходи ${\displaystyle o_{i}}$ кожного вузла.
   2. Для всіх ${\displaystyle k\in Outputs}$

      ${\displaystyle \delta _{k}=-o_{k}(1-o_{k})(t_{k}-o_{k})}$.

   3. Для кожного рівня l, починаючи з останнього:

      Для кожного вузла j рівня l порахувати

      ${\displaystyle \delta _{j}=o_{j}(1-o_{j})\sum _{k\in Children(j)}\delta _{k}w_{j,k}}$.

   4. Для кожного ребра сітки {i, j}

      ${\displaystyle \Delta w_{i,j}=\alpha \Delta w_{i,j}+(1-\alpha )\eta \delta _{j}o_{i}}$.

      ${\displaystyle w_{i,j}=w_{i,j}+\Delta w_{i,j}}$.

3. Видати значення ${\displaystyle w_{ij}}$.

Математична інтерпретація навчання нейронної мережі

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

Навчання нейронної мережі характеризується чотирма специфічними обмеженнями, що виділяють навчання нейромереж із загальних задач оптимізації: астрономічне число параметрів, необхідність високого паралелізму при навчанні, багато критеріально вирішуваних завдань, необхідність знайти досить широку область, в якій значення всіх функцій, що мінімізуються близькі до мінімальних. Стосовно решти проблему навчання можна, як правило, сформулювати як завдання мінімізації оцінки. Обережність попередньої фрази («як правило») пов'язана з тим, що насправді нам невідомі і ніколи не будуть відомі всі можливі завдання для нейронних мереж, і, може, десь в невідомості є завдання, які не зводяться до мінімізації оцінки. Мінімізація оцінки — складна проблема: параметрів астрономічно багато (для стандартних прикладів, що реалізуються на РС — від 100 до 1000000), адаптивний рельєф (графік оцінки як функції від підлаштовуваних параметрів) складний, може містити багато локальних мінімумів.

Недоліки алгоритму

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

Параліч мережі

У процесі навчання мережі значення ваг можуть в результаті корекції стати дуже великими величинами. Це може призвести до того, що всі або більшість нейронів будуть функціонувати при дуже великих значеннях OUT, в області, де похідна стискаючої функції дуже мала. Так як помилка, що посилається назад у процесі навчання, пропорційна цій похідній, то процес навчання може практично завмерти. У теоретичному відношенні ця проблема погано вивчена. Зазвичай цього уникають зменшенням розміру кроку η, але це збільшує час навчання. Різні евристики використовувалися для запобігання від паралічу або для відновлення після нього, але поки що вони можуть розглядатися лише як експериментальні.

Локальні мінімуми

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

Розмір кроку

Уважний розбір доведення збіжності показує, що корекції ваг передбачаються нескінченно малими. Ясно, що це нездійсненно на практиці, тому що веде до безкінечного часу навчання. Розмір кроку повинен братися скінченним. Якщо розмір кроку фіксований і дуже малий, то збіжність надто повільна, якщо ж він фіксований і занадто великий, то може виникнути параліч або постійна нестійкість. Ефективно збільшувати крок до тих пір, поки не припиниться поліпшення оцінки в даному напрямку антиградієнта і зменшувати, якщо такого покращення не відбувається. П. Д. Вассерман описав адаптивний алгоритм вибору кроку, який автоматично коректує розмір кроку в процесі навчання. В книзі А. Н. Горбаня запропонована розгалужена технологія оптимізації навчання. Слід також відмітити можливість перенавчання мережі, що є скоріше результатом помилкового проектування її топології. При дуже великій кількості нейронів втрачається властивість мережі узагальнювати інформацію. Весь набір образів, наданих до навчання, буде вивчений мережею, але будь-які інші образи, навіть дуже схожі, можуть бути класифіковані невірно.

Історія

Вперше метод був описаний в 1974 р. А. І. Галушкіним , а також незалежно і одночасно Полом Дж. Вербосом . Далі істотно розвинений в 1986 р. ^[en], Джефрі Е. Хінтоном і ^[en] і незалежно й одночасно С. І. Барцом та В. А. Охоніним .

Література

• Philip D. Wasserman. Neural Computing: Theory and Practice. Coriolis Group. June 1, 1989. 230 pages. ISBN-13 ‏:‎ 978-0442207434. ISBN-10 ‏:‎ 0442207433
• Simon S. Haykin. Neural Networks: A Comprehensive Foundation.Prentice Hall, 1999 - 842 pages. ISBN-13: 978-0132733502 ISBN-10: 0132733501

Зноски

1. Миркес Е. М., Нейрокомпьютер. Проект стандарта [ 15 червня 2009 у Wayback Machine.]. — Новосибирск: Наука, Сибирская издательская фирма РАН, 1999. — 337 с. Інші копії онлайн: [1] [ 30 червня 2009 у Wayback Machine.], [2] [ 3 липня 2009 у Wayback Machine.].
2. Rumelhart, David E.; Williams, Ronald J. (1986). Learning Internal Representations by Error Propagation. In: Parallel Distributed Processing (англ.). Cambridge, MA: MIT Press. 1: 318—362.
3. Wasserman P. D. Experiments in translating Chinese characters using backpropagation. Proceedings of the Thirty-Third IEEE Computer Society International Conference.. — Washington: D. C.: Computer Society Press of the IEEE, 1988.
4. Горбань А. Н. Обучение нейронных сетей. — Москва: СП ПараГраф, 1990.
5. Галушкин А. И. Синтез многослойных систем распознавания образов. — М.: «Энергия», 1974.
6. Werbos P. J., Beyond regression: New tools for prediction and analysis in the behavioral sciences. Ph.D. thesis, Harvard University, Cambridge, MA, 1974.
7. Барцев С. И., Охонин В. А. Адаптивные сети обработки информации. Красноярск : Ин-т физики СО АН СССР, 1986. Препринт N 59Б. — 20 с.

Див. також

• Метод зворотного поширення похибки в часі

Посилання

• Olah, Christopher. Calculus on Computational Graphs: Backpropagation -- colah's blog. Процитовано 5 лютого 2019.

1. С++ код простої нейромережі, що навчається за алгоритмом зворотного поширення помилки
2. Терехов С. А., Лекции по теории и приложениям искусственных нейронных сетей.
3. Миркес Е. М., Красноярск: ИПЦ КГТУ, 2002, 347 с. .