Я. Гудфеллоу, И. Бенджио, А. Курвилль

Алгоритм 6.1.
Процедура, которая выполняет вычисления, отображающие 
n
i
входов 
u
(1)
, …, 
u
(
ni
)
в выход 
u
(
n
)
. Она определяет граф вычислений, в котором каж-
дая вершина вычисляет числовое значение 
u
(
i
)
путем применения функции 
f
(
i
)
ко 
множеству аргументов 
𝔸 
(
i
)
, содержащему значения предыдущих вершин 
u
(
j
)
, 
j
< 
i
и 
j
∈
Pa
(
u
(
i
)
). Входом для графа вычислений является вектор 
x
, хранящийся в пер-
вых 
n
i
вершинах 
u
(1)
, …, 
u
(
n
i
)
. Результат графа вычислений читается из последней 
(выходной) вершины 
u
(
n
)
.
for
i
= 1, …, 
n
i
do
u
(
i
)
⟵
x
i
end for
for
i
= 
n
i
+ 1, …, 
n
do
𝔸 
(
i
)
⟵
{
u
(
j
)
| 
j
∈
Pa
(
u
(
i
)
)}
u
(
i
)
⟵
f
(
i
)
(
𝔸 
(
i
)
)
end for
return 
u
(
n
)
Алгоритм обратного распространения призван уменьшить количество общих 
подвыражений без учета доступной памяти. Точнее, он вычисляет порядка одного 
произведения якобиана на вектор на каждую вершину графа. Это видно из того, 
что алгоритм 6.2 посещает каждое ребро из вершины 
u
(
j
)
в вершину 
u
(
i
)
графа ровно 
один раз для вычисления ассоциированной с ним частной производной 
∂
u
(
i
)
/
∂
u
(
j
)
. 
Таким образом, алгоритм обратного распространения предотвращает экспоненци-
альный рост повторяющихся подвыражений. Другие алгоритмы могут еще умень-
шить число подвыражений путем упрощения графа вычислений, а могут сэконо-
мить память, повторно вычисляя некоторые подвыражения вместо их сохранения. 
Мы вернемся к этим идеям, после того как опишем сам алгоритм обратного рас-
пространения.

---

184 

 
Глубокие сети прямого распространения 
z
y
x
w
f
f
f
Рис. 6.9 

Граф вычислений градиента, в котором возникают пов-
торяющиеся подвыражения. Обозначим 
w
∈
ℝ
– вход графа. В качестве опе-
рации, применяемой на каждом шаге цепочки, используем ту же функцию 
f
: 
ℝ
⟶
ℝ
, т. е. 
x
= 
f
(
w
)
, 
y
= 
f
(
x
)
, 
z
= 
f
(
y
)
. Для вычисления 
∂
z
/
∂
w
применяем 
уравнение 6.44 и получаем:
(6.50)
(6.51)
= 
f
 
′
(
y
)
f
 
′
(
x
)
f
 
′
(
w
) 
(6.52)
= 
f’
(
f
(
f
(
w
)))
f
 
′
(
f
(
w
))
f
 
′
(
w
). 
(6.53)
Уравнение (6.52) подсказывает реализацию: вычислить значение 
f
(
w
)
один 
раз и сохранить его в переменной 
x
. Именно такой подход применяется в ал-
горитме обратного распространения. Альтернативный подход подсказан 
уравнением (6.53), в котором подвыражение 
f
(
w
)
встречается более одного 
раза. В этом случае 
f
(
w
)
заново вычисляется всякий раз, как понадобится. 
Если памяти для хранения значений подвыражений достаточно, то подход, 
подсказанный уравнением (6.52), очевидно, предпочтительнее, т. к. требует 
меньше времени. Но и уравнение (6.53) – допустимая реализация правила 
дифференцирования сложной функции, полезная, когда память ограничена.
Алгоритм 6.2.
Упрощенный вариант алгоритма обратного распространения для 
вычисления производных 
u
(
n
)
по переменным в графе. Этот пример позволит луч-
ше понять алгоритм в простом случае, когда все переменные – скаляры, а мы хотим 
вычислить производные по 
u
(1)
, …, 
u
(
n
i
)
. Вычислительная сложность этого алгорит-
ма пропорциональна числу ребер графа в предположении, что вычисление частной 
производной, ассоциированной с каждым ребром, занимает постоянное время. По-
рядок тот же, что для объема вычислений в алгоритме прямого распространения. 
Каждая производная 
∂
u
(
i
)
/
∂
u
(
j
)
является функцией от родителей 
u
(
j
)
вершины 
u
(
i
)
, 
и таким образом вершины прямого графа связываются с добавленными в граф об-
ратного распространения.

---

Обратное распространение и другие алгоритмы дифференцирования 

185
Выполнить алгоритм прямого распространения (алгоритм 6.1) для вычисления 
функций активации сети.
Инициализировать 
grad_table
, структуру данных, в которой будут храниться 
вычисленные производные. В элементе 
grad_table
[
u
(
i
)
] хранится вычисленное 
значение 
∂
u
(
n
)
/
∂
u
(
i
)
.
grad_table
[
u
(
n
)
] 
⟵
1