Метод обратного распространения ошибки

Метод обратного распространения ошибки (англ. backpropagation) — метод вычисления градиента, который используется при обновлении весов многослойного перцептрона. Впервые метод был описан в 1974 г. А. И. Галушкиным, а также независимо и одновременно Полом Дж. Вербосом. Далее существенно развит в 1986 г. Дэвидом И. Румельхартом, Дж. Е. Хинтоном и Рональдом Дж. Вильямсом и независимо и одновременно С.И. Барцевым и В.А. Охониным (Красноярская группа). Это итеративный градиентный алгоритм, который используется с целью минимизации ошибки работы многослойного перцептрона и получения желаемого выхода.

Основная идея этого метода состоит в распространении сигналов ошибки от выходов сети к её входам, в направлении обратном прямому распространению сигналов в обычном режиме работы. Барцев и Охонин предложили обобщающий метод («принцип двойственности»), применимый к более широкому классу систем, включая системы с запаздыванием, распределённые системы, и т. п.

Для возможности применения метода обратного распространения ошибки передаточная функция нейронов должна быть дифференцируема. Метод является изменением классического метода градиентного спуска.

Сигмоидальные функции активации

Наиболее часто в качестве функций активации используются следующие виды сигмоид:

Функция Ферми (экспоненциальная сигмоида):

f ( s ) = 1 1 + e − 2 α s {displaystyle f(s)={frac {1}{1+e^{-2alpha s}}}}

Рациональная сигмоида (при α = 0 {displaystyle alpha =0} вырождается в т. н. пороговую функцию активации):

f ( s ) = s | s | + α {displaystyle f(s)={frac {s}{|s|+alpha }}}

Гиперболический тангенс:

f ( s ) = t h s α = e s α − e − s α e s α + e − s α {displaystyle f(s)=mathrm {th} ,{frac {s}{alpha }}={frac {e^{frac {s}{alpha }}-e^{-{frac {s}{alpha }}}}{e^{frac {s}{alpha }}+e^{-{frac {s}{alpha }}}}}} ,

где s {displaystyle s} — выход сумматора нейрона, α {displaystyle alpha } — произвольная константа.

Наименьшее количество процессорного времени, по сравнению с другими сигмоидами, требует расчёт рациональной сигмоиды. Для вычисления гиперболического тангенса требуется больше всего тактов работы процессора. Если же сравнивать с пороговыми функциями активации, то сигмоиды рассчитываются очень медленно. Если после суммирования в пороговой функции сразу можно начинать сравнение с определённой величиной (порогом), то в случае сигмоидальной функции активации нужно рассчитать сигмоид (затратить время в лучшем случае на три операции: взятие модуля, сложение и деление), и только потом сравнивать с пороговой величиной (например, нулём). Если считать, что все простейшие операции рассчитываются процессором за примерно одинаковое время, то работа сигмоидальной функции активации после произведённого суммирования (которое займёт одинаковое время) будет медленнее пороговой функции активации в 4 раза.

Функция оценки работы сети

В тех случаях, когда удаётся оценить работу сети, обучение нейронных сетей можно представить как задачу оптимизации. Оценить — означает указать количественно, хорошо или плохо сеть решает поставленные ей задачи. Для этого строится функция оценки. Она, как правило, явно зависит от выходных сигналов сети и неявно (через функционирование) — от всех её параметров. Простейший и самый распространённый пример оценки — сумма квадратов расстояний от выходных сигналов сети до их требуемых значений:

H = 1 2 ∑ τ ∈ v o u t ( Z ( τ ) − Z ∗ ( τ ) ) 2 {displaystyle H={ frac {1}{2}}sum _{ au in v_{mathrm {out} }}(Z( au )-Z^{*}( au ))^{2}} ,

где Z ∗ ( τ ) {displaystyle Z^{*}( au )} — требуемое значение выходного сигнала.

Метод наименьших квадратов далеко не всегда является лучшим выбором оценки. Тщательное конструирование функции оценки позволяет на порядок повысить эффективность обучения сети, а также получать дополнительную информацию — «уровень уверенности» сети в даваемом ответе.

Описание алгоритма

Архитектура многослойного перцептрона

Алгоритм обратного распространения ошибки применяется для многослойного перцептрона. У сети есть множество входов x 1 , . . . , x n {displaystyle x_{1},...,x_{n}} , множество выходов Outputs и множество внутренних узлов. Перенумеруем все узлы (включая входы и выходы) числами от 1 до N (сквозная нумерация, вне зависимости от топологии слоёв). Обозначим через w i , j {displaystyle w_{i,j}} вес, стоящий на ребре, соединяющем i-й и j-й узлы, а через o i {displaystyle o_{i}} — выход i-го узла. Если нам известен обучающий пример (правильные ответы сети t k {displaystyle t_{k}} , k ∈ O u t p u t s {displaystyle kin mathrm {Outputs} } ), то функция ошибки, полученная по методу наименьших квадратов, выглядит так:

E ( { w i , j } ) = 1 2 ∑ k ∈ O u t p u t s ( t k − o k ) 2 {displaystyle E({w_{i,j}})={ frac {1}{2}}!!sum _{kin mathrm {Outputs} }!!!(t_{k}-o_{k})^{2}}

Как модифицировать веса? Мы будем реализовывать стохастический градиентный спуск, то есть будем подправлять веса после каждого обучающего примера и, таким образом, «двигаться» в многомерном пространстве весов. Чтобы «добраться» до минимума ошибки, нам нужно «двигаться» в сторону, противоположную градиенту, то есть, на основании каждой группы правильных ответов, добавлять к каждому весу w i , j {displaystyle w_{i,j}}

Δ w i , j = − η ∂ E ∂ w i , j {displaystyle Delta w_{i,j}=-eta {frac {partial E}{partial w_{i,j}}}} ,

где 0 < η < 1 {displaystyle 0<eta <1} — множитель, задающий скорость «движения».

Производная считается следующим образом. Пусть сначала j ∈ O u t p u t s {displaystyle jin mathrm {Outputs} } , то есть интересующий нас вес входит в нейрон последнего уровня. Сначала отметим, что w i , j {displaystyle w_{i,j}} влияет на выход сети только как часть суммы S j = ∑ i w i , j x i {displaystyle S_{j}=sum _{i}w_{i,j}x_{i}} , где сумма берётся по входам j-го узла. Поэтому

∂ E ∂ w i , j = ∂ E ∂ S j ∂ S j ∂ w i , j = x i ∂ E ∂ S 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}}}}

Аналогично, S j {displaystyle S_{j}} влияет на общую ошибку только в рамках выхода j-го узла o j {displaystyle o_{j}} (напоминаем, что это выход всей сети). Поэтому

∂ E ∂ S j = ∂ E ∂ o j ∂ o j ∂ S j = ( ∂ ∂ o j 1 2 ∑ k ∈ O u t p u t s ( t k − o k ) 2 ) ( ∂ f ⁡ ( S ) ∂ S ∣ S = S 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 _{kin mathrm {Outputs} }(t_{k}-o_{k})^{2} ight)!!left({cfrac {partial operatorname {f} (S)}{partial S}}mid _{S=S_{j}} ight)=} = ( 1 2 ∂ ∂ o j ( t j − o j ) 2 ) ( o j ( 1 − o j ) ) 2 α = − 2 α o j ( 1 − o j ) ( t j − o j ) . {displaystyle =left({cfrac {1}{2}},{cfrac {partial }{partial o_{j}}}(t_{j}-o_{j})^{2} ight)(o_{j}(1-o_{j}))2alpha =-2alpha o_{j}(1-o_{j})(t_{j}-o_{j}).}

где f ( S ) {displaystyle f(S)} — соответствующая сигмоида, в данном случае — экспоненциальная

∂ ( 1 1 + e − 2 α S ) ∂ S = − 1 ( 1 + e − 2 α S ) 2 × ∂ ( 1 + e − 2 α S ) ∂ S = − 1 ( 1 + e − 2 α S ) 2 × ( − 2 α e − 2 α S ) = {displaystyle {frac {partial {({frac {1}{1+e^{-2alpha S}}})}}{partial {S}}}={frac {-1}{(1+e^{-2alpha S})^{2}}} imes {frac {partial {(1+e^{-2alpha S})}}{partial {S}}}={frac {-1}{(1+e^{-2alpha S})^{2}}} imes (-2alpha e^{-2alpha S})=} = 2 α e − 2 α S ( 1 + e − 2 α S ) 2 = ( 1 + e − 2 α S ( 1 + e − 2 α S ) 2 − 1 ( 1 + e − 2 α S ) 2 ) × 2 α = 2 α ( f ⁡ ( S ) − f 2 ⁡ ( S ) ) {displaystyle ={frac {2alpha e^{-2alpha S}}{(1+e^{-2alpha S})^{2}}}=left({frac {1+e^{-2alpha S}}{(1+e^{-2alpha S})^{2}}}-{frac {1}{(1+e^{-2alpha S})^{2}}} ight) imes 2alpha =2alpha (operatorname {f} (S)-operatorname {f^{2}} (S))}

Если же j-й узел — не на последнем уровне, то у него есть выходы; обозначим их через Children(j). В этом случае

∂ E ∂ S j = ∑ k ∈ C h i l d r e n ( j ) ∂ E ∂ S k ∂ S k ∂ S j {displaystyle {cfrac {partial E}{partial S_{j}}}=sum _{kin mathrm {Children} (j)}{cfrac {partial E}{partial S_{k}}},{cfrac {partial S_{k}}{partial S_{j}}}} ,

∂ S k ∂ S j = ∂ S k ∂ o j ∂ o j ∂ S j = w j , k ∂ o j ∂ S j = 2 α w j , k o j ( 1 − o j ) {displaystyle {cfrac {partial S_{k}}{partial S_{j}}}={cfrac {partial S_{k}}{partial o_{j}}},{cfrac {partial o_{j}}{partial S_{j}}}=w_{j,k}{cfrac {partial o_{j}}{partial S_{j}}}=2alpha w_{j,k}o_{j}(1-o_{j})} .

Но ∂ E ∂ S k {displaystyle {cfrac {partial E}{partial S_{k}}}} — это в точности аналогичная поправка, но вычисленная для узла следующего уровня. Будем обозначать её через δ k {displaystyle delta _{k}} — от Δ k {displaystyle Delta _{k}} она отличается отсутствием множителя ( − η x i , j ) {displaystyle (-eta x_{i,j})} . Поскольку мы научились вычислять поправку для узлов последнего уровня и выражать поправку для узла более низкого уровня через поправки более высокого, можно уже писать алгоритм. Именно из-за этой особенности вычисления поправок алгоритм называется алгоритмом обратного распространения ошибки (backpropagation). Краткое резюме проделанной работы:

для узла последнего уровня

δ j = − 2 α o j ( 1 − o j ) ( t j − o j ) {displaystyle delta _{j}=-2alpha o_{j}(1-o_{j})(t_{j}-o_{j})}

для внутреннего узла сети

δ j = 2 α o j ( 1 − o j ) ∑ k ∈ C h i l d r e n ( j ) δ k w j , k {displaystyle delta _{j}=2alpha o_{j}(1-o_{j})!!sum _{kin mathrm {Children} (j)}!!delta _{k}w_{j,k}}

для всех узлов

Δ w i , j = − η δ j o i {displaystyle Delta w_{i,j}=-eta delta _{j}o_{i}} ,

где o i {displaystyle o_{i}} это тот же x i {displaystyle x_{i}} в формуле для ∂ E ∂ w i , j {displaystyle {cfrac {partial E}{partial w_{i,j}}}} .

Получающийся алгоритм представлен ниже. На вход алгоритму, кроме указанных параметров, нужно также подавать в каком-нибудь формате структуру сети. На практике очень хорошие результаты показывают сети достаточно простой структуры, состоящие из двух уровней нейронов — скрытого уровня (hidden units) и нейронов-выходов (output units); каждый вход сети соединён со всеми скрытыми нейронами, а результат работы каждого скрытого нейрона подаётся на вход каждому из нейронов-выходов. В таком случае достаточно подавать на вход количество нейронов скрытого уровня.

Алгоритм

Алгоритм: BackPropagation ( η , α , { x i d , t d } i = 1 , d = 1 n , m , steps ) {displaystyle (eta ,alpha ,{x_{i}^{d},t^{d}}_{i=1,d=1}^{n,m},{ extrm {steps}})}

Инициализировать { w i j } i , j {displaystyle {w_{ij}}_{i,j}} маленькими случайными значениями, { Δ w i j } i , j = 0 {displaystyle {Delta w_{ij}}_{i,j}=0}

Повторить NUMBER_OF_STEPS раз: .Для всех d от 1 до m:

Подать { x i d } {displaystyle {x_{i}^{d}}} на вход сети и подсчитать выходы o i {displaystyle o_{i}} каждого узла.

Для всех k ∈ O u t p u t s {displaystyle kin Outputs} δ k = − o k ( 1 − o k ) ( t k − o k ) {displaystyle delta _{k}=-o_{k}(1-o_{k})(t_{k}-o_{k})} .

Для каждого уровня l, начиная с предпоследнего: Для каждого узла j уровня l вычислить δ j = o j ( 1 − o j ) ∑ k ∈ C h i l d r e n ( j ) δ k w j , k {displaystyle delta _{j}=o_{j}(1-o_{j})sum _{kin Children(j)}delta _{k}w_{j,k}} .

Для каждого ребра сети {i, j} Δ w i , j ( n ) = α Δ w i , j ( n − 1 ) + ( 1 − α ) η δ j o i {displaystyle Delta w_{i,j}(n)=alpha Delta w_{i,j}(n-1)+(1-alpha )eta delta _{j}o_{i}} . w i , j ( n ) = w i , j ( n − 1 ) − Δ w i , j ( n ) {displaystyle w_{i,j}(n)=w_{i,j}(n-1)-Delta w_{i,j}(n)} .

Выдать значения w i j {displaystyle w_{ij}} .

где α {displaystyle alpha } — коэффициент инерциальности для сглаживания резких скачков при перемещении по поверхности целевой функции

Пример реализации

Статья «A Step by Step Backpropagation Example» от Matt Mazur
Код по статье (реализация нейросети)
Обсуждение примера реализации

Режимы реализации

Существует два режима реализации метода обратного распространения ошибки：

Стохастического (stochastic) градиентного спуска

Пакетного (batch) градиентного спуска

Для пакетного градиентного спуска функция потерь вычисляется для всех образцов вместе взятых после окончания эпохи, и потом вводятся поправки весовых коэффициентов нейрона в соответствии с методом обратного распространения ошибки.

Стохастический метод немедленно после вычисления выхода сети на одном образце вводит поправки в весовые коэффициенты.

Пакетный метод более быстрый и стабильный, но он имеет тенденцию останавливаться и застревать в локальных минимумах. Поэтому для выхода из локальных минимумов нужно использовать особые приёмы, например, алгоритм имитации отжига.

Стохастический метод медленнее, но от того, что он не осуществляет точного градиентного спуска, а вносит «шумы», используя недовычисленный градиент, он способен выходить из локальных минимумов и может привести к лучшему результату.

В виде компромисса рекомендуют также применять мини-пакеты, когда поправка искомых весов осуществляется после обработки нескольких образцов (мини-пакета), то есть, реже чем при стохастическом спуске, но чаще чем при пакетном.

Математическая интерпретация обучения нейронной сети

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

Обучение нейронной сети характеризуется четырьмя специфическими ограничениями, выделяющими обучение нейросетей из общих задач оптимизации: астрономическое число параметров, необходимость высокого параллелизма при обучении, многокритериальность решаемых задач, необходимость найти достаточно широкую область, в которой значения всех минимизируемых функций близки к минимальным. В остальном проблему обучения можно, как правило, сформулировать как задачу минимизации оценки. Осторожность предыдущей фразы («как правило») связана с тем, что на самом деле нам неизвестны и никогда не будут известны все возможные задачи для нейронных сетей, и, быть может, где-то в неизвестности есть задачи, которые несводимы к минимизации оценки. Минимизация оценки — сложная проблема: параметров астрономически много (для стандартных примеров, реализуемых на PC — от 100 до 1 000 000), адаптивный рельеф (график оценки как функции от подстраиваемых параметров) сложен, может содержать много локальных минимумов.

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

Несмотря на многочисленные успешные применения обратного распространения, оно не является универсальным решением. Больше всего неприятностей приносит неопределённо долгий процесс обучения. В сложных задачах для обучения сети могут потребоваться дни или даже недели, она может и вообще не обучиться. Причиной может быть одна из описанных ниже.

Паралич сети

В процессе обучения сети значения весов могут в результате коррекции стать очень большими величинами. Это может привести к тому, что все или большинство нейронов будут функционировать при очень больших значениях OUT, в области, где производная сжимающей функции очень мала. Так как посылаемая обратно в процессе обучения ошибка пропорциональна этой производной, то процесс обучения может практически замереть. В теоретическом отношении эта проблема плохо изучена. Обычно этого избегают уменьшением размера шага η, но это увеличивает время обучения. Различные эвристики использовались для предохранения от паралича или для восстановления после него, но пока что они могут рассматриваться лишь как экспериментальные.

Локальные минимумы

Обратное распространение использует разновидность градиентного спуска, то есть осуществляет спуск вниз по поверхности ошибки, непрерывно подстраивая веса в направлении к минимуму. Поверхность ошибки сложной сети сильно изрезана и состоит из холмов, долин, складок и оврагов в пространстве высокой размерности. Сеть может попасть в локальный минимум (неглубокую долину), когда рядом имеется гораздо более глубокий минимум. В точке локального минимума все направления ведут вверх, и сеть не способна из него выбраться. Основную трудность при обучении нейронных сетей составляют как раз методы выхода из локальных минимумов: каждый раз выходя из локального минимума снова ищется следующий локальный минимум тем же методом обратного распространения ошибки до тех пор, пока найти из него выход уже не удаётся.

Проблемы отсутствия выпуклости в функции ошибок и как следствие трудности с локальными минимумами и плоскими участками считались недостатком метода, однако Ян Лекун в обзорной статье 2015 года утверждает, что с практической точки зрения эти явления не так опасны.

Размер шага

Если размер шага фиксирован и очень мал, то сходимость слишком медленная, если же он фиксирован и слишком велик, то может возникнуть паралич или постоянная неустойчивость. Эффективно увеличивать шаг до тех пор, пока не прекратится улучшение оценки в данном направлении антиградиента и уменьшать, если такого улучшения не происходит. П. Д. Вассерман описал адаптивный алгоритм выбора шага, автоматически корректирующий размер шага в процессе обучения. В книге А. Н. Горбаня предложена разветвлённая технология оптимизации обучения.

Согласно , метод обратного распространения ошибки является способом быстрого вычисления градиента, который далее используется в различных алгоритмах гладкой оптимизации, а наиболее перспективным является использование квазиньютоновских методов (BFGS) для вычисления направления спуска в сочетании с одномерной оптимизацией в этом направлении. Оценка для таких методов вычисляется либо по всему задачнику (batch optimisation) либо по его подмножествам ("страницам" задачника, которые впоследствии получили название "mini-batches"). В настоящее время такая точка зрения стала общепринятой.

Следует также отметить возможность переобучения сети (overfitting), что является скорее результатом ошибочного проектирования её топологии и/или неправильным выбором критерия остановки обучения. При переобучении теряется свойство сети обобщать информацию. Весь набор образов, предоставленных к обучению, будет выучен сетью, но любые другие образы, даже очень похожие, могут быть распознаны неверно.