Метод зворотного поширення помилки

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Сигмоїдні функції активації[ред.ред. код]

Найчастіше в якості функцій активації використовуються такі види сигмоїд:

Функція Фермі (Експоненційна сигмоїда): f(s)= \frac{1}{1+e^{-2 \alpha s}}

Раціональна сигмоїда: f(s)= \frac{s}{|s|+ \alpha}

Гіперболічний тангенс: f(s)= th \frac{s}{\alpha} = \frac{ e^{ \frac{s}{\alpha} } - e^{ - \frac{s}{\alpha}} } 
{e^{ \frac{s}{\alpha} } + e^{ - \frac{s}{\alpha}}}

де s — вихід суматора нейрона, \alpha — довільна константа.

Процесорний час розрахунку раціональної сигмоїдної функцій активації є найменшим з усіх сигмоїд. Для обчислення гіперболічного тангенса потрібно найбільше тактів роботи процесора. Якщо ж порівнювати з пороговими функціями активації, то сигмоїди розраховуються дуже повільно. Якщо після підсумовування в пороговій функції відразу можна починати порівняння з певною величиною (порогом), то у випадку сигмоїдної функції активації потрібно розрахувати сигмоїду (затратити час у кращому випадку на три операції: взяття модуля, додавання і поділ), і тільки потім порівнювати з пороговою величиною (наприклад, нулем). Якщо вважати, що всі прості операції розраховуються процесором за приблизно однаковий час, то робота сігмоідальной функції активації після зробленого підсумовування (яке займе однаковий час) буде повільнішою від порогової функції активації в пропорції 1:4.

Функція оцінки роботи мережі[ред.ред. код]

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

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

Опис алгоритму[ред.ред. код]

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

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

E(\{w_{i,j}\}) = \cfrac{1}{2} \sum_{k \in Outputs} (t_k - o_k)^2

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

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

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

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

\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}

Аналогічно, S_j впливає на загальну помилку тільки в рамках виходу j-го вузла o_j (нагадуємо, що це вихід всієї мережі). Тому

\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).

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

\cfrac{\partial E}{\partial S_j} = \sum_{k \in Children(j)} \cfrac{\partial E}{\partial S_k} \cfrac{\partial S_k}{\partial S_j} ,

і

\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).

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

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

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

\delta _j = -o_j(1 - o_j)(t_j - o_j)

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

\delta _j = -o_j(1 - o_j)\sum_{k \in Outputs(j)} \delta _k w_{j,k}

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

\Delta w_{i,j} = -\eta \delta _j x_{i}

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

Алгоритм[ред.ред. код]

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

  1. Ініціалізувати \{w_{ij}\}_{i,j} маленькими випадковими значеннями, \{\Delta w_{ij}\}_{i,j} = 0
  2. Повторити NUMBER_OF_STEPS раз:
    Для всіх d від 1 до m:
    1. Подати \{x_i^d\} на вхід сітки і підрахувати виходи o_i кожного вузла.
    2. Для всіх k \in Outputs
      \delta _k = o_k(1 - o_k)(t_k - o_k).
    3. Для кожного рівня l, починаючи з останнього:
      Для кожного вузла j рівня l порахувати
      \delta _j = o_j(1 - o_j)\sum_{k \in Children(j)} \delta _k w_{j,k}.
    4. Для кожного ребра сітки {i, j}
      \Delta w_{i,j} = \alpha \Delta w_{i,j} + ( 1 - \alpha ) \eta \delta _j o_{i}.
      w_{i,j} = w_{i,j} + \Delta w_{i,j}.
  3. Видати значення w_{ij}.

Математична інтерпретація навчання нейронної мережі[ред.ред. код]

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

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

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

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

Параліч мережі[ред.ред. код]

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

Локальні мінімуми[ред.ред. код]

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

Розмір кроку[ред.ред. код]

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

Література[ред.ред. код]

  • Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. — М.: «Мир», 1992.
  • Хайкин С. Нейронные сети: Полный курс. Пер. с англ. Н. Н. Куссуль, А. Ю. Шелестова. 2-е изд., испр. — М.: Издательский дом Вильямс, 2008, 1103 с.
  1. Барцев С. И., Гилев С. Е., Охонин В. А., Принцип двойственности в организации адаптивных сетей обработки информации, В кн.: Динамика химических и биологических систем. — Новосибирск: Наука, 1989. — С. 6-55.
  2. Галушкин А. И. Синтез многослойных систем распознавания образов. — М.: «Энергия», 1974.
  3. Werbos P. J., Beyond regression: New tools for prediction and analysis in the behavioral sciences. Ph.D. thesis, Harvard University, Cambridge, MA, 1974.
  4. а б Rumelhart DE, Hinton GE, Williams RJ, Learning Internal Representations by Error Propagation. In: Parallel Distributed Processing, vol. 1, pp. 318—362. Cambridge, MA, MIT Press. 1986.
  5. Барцев С. И., Охонин В. А. Адаптивные сети обработки информации. Красноярск : Ин-т физики СО АН СССР, 1986. Препринт N 59Б. — 20 с.
  6. Миркес Е. М., Нейрокомпьютер. Проект стандарта. — Новосибирск: Наука, Сибирская издательская фирма РАН, 1999. — 337 с. ISBN 5-02-031409-9 Інші копії онлайн: [1], [2].
  7. 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.
  8. Горбань А. Н. Обучение нейронных сетей.. — Москва: СП ПараГраф, 1990.

Посилання[ред.ред. код]

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