8.4. Автоматическое дифференцирование вперёд

Автоматическое дифференцирование вперёд (прямое, forward mode, forward accumulation) является видом автоматического дифференцирования, в котором вычисления производных распространяются от аргументов функции к её результату. Впервые этот метод дифференцирования был представлен R.E. Wengert [Wen64].

Сначала мы продемонстируем работу алгоритма на частном примере функции из Раздела 8.3, а затем опишем общий случай. Ниже показана функция из примера и её граф вычисления.

\[f(x_1, x_2, x_3) = \frac{x_1 x_2 + \sin{x_3}}{x_3}\]

Рис. 8.5 Граф вычислений функции \(f(x_1, x_2, x_3) = (x_1 x_2 + \sin{x_3})/x_3\).

Поставим задачу вычисления первой частной производной \(\partial f / \partial x_1\). Будем считать, что \(f\) это сложная (композитная) функция от промежуточных значений. Например, можно сказать, что \(f\) явно зависит от \(x_3\) и \(x_6\), которые, в свою очередь, неявно зависят (или не зависят) от \(x_1\). Это позволит нам воспользоваться правилом дифференцирования сложной функции и, в конечном итоге, получить производную \(\partial f / \partial x_1\).

Итак, наша задача найти все частные производные вида

\[\frac{\partial x_j}{\partial x_1}, \quad j = 1, \dots, 7.\]

Часть этих производных нулевые, а при \(j = 7\) мы получим \(\partial x_7 / \partial x_1 \equiv \partial f / \partial x_1\), т.е. искомую частную производную.

Шаг 1. Произведём инициализацию алгоритма. Нам известны значения аргументов \(x_1\), \(x_2\), \(x_3\) и их частные производные по \(x_1\)

\[\frac{\partial x_1}{\partial x_1} = 1, \quad \frac{\partial x_2}{\partial x_1} = \frac{\partial x_3}{\partial x_1} = 0.\]

Запомним их.

Шаг 2. Найдём производную \(\partial x_4 / \partial x_1\). Для этого считаем \(x_4\) сложной функцией в соответствии с графом вычисления (см. аргументы вычисления \(x_4\) на Рисунке 8.5)

\[x_4 = x_4(x_1, x_2) = x_1 \times x_2(x_1) = x_4(x_1)\]

и получим

\[\frac{\partial x_4}{\partial x_1} = \frac{\partial x_1}{\partial x_1} x_2 + x_1 \frac{\partial x_2}{\partial x_1} = 1 \times x_2 + x_1 \times 0 = x_2.\]

Здесь мы воспользовались правилом дифференцирования произведения. Производные \(\partial x_1 / \partial x_1 = 1\) и \(\partial x_2 / \partial x_1 = 0\) нам известны с шага 1. В конце шага запомним не только производную \(\partial x_4 / \partial x_1\), но и значение \(x_4 = x_1 x_2\).

Шаг 3. Найдём производную \(\partial x_5 / \partial x_1\). Поступая также, как на шаге 2, посчитаем \(x_5\) сложной функцией от \(x_3\)

\[x_5 = x_5(x_3) = \sin{x_3(x_1)} = x_5(x_1),\]

тогда

\[\frac{\partial x_5}{\partial x_1} = \frac{\partial x_5}{\partial x_3} \frac{\partial x_3}{\partial x_1} = \cos{x_3} \times 0 = 0.\]

Здесь мы воспользовались правилом дифференцирования сложной функции и производной функции синуса. Производная \(\partial x_3 / \partial x_1 = 0\) известна с шага 1. Как и на шаге 2, запомним \(x_5 = \sin{x_3}\) и \(\partial x_5 / \partial x_1\).

Шаг 4. Найдём производную \(\partial x_6 / \partial x_1\). Значение \(x_6\) явно вычисляется по \(x_4\) и \(x_5\)

\[x_6 = x_6(x_4, x_5) = x_4(x_1) + x_5(x_1) = x_6(x_1),\]

тогда

\[\frac{\partial x_6}{\partial x_1} = \frac{\partial x_4}{\partial x_1} + \frac{\partial x_5}{\partial x_1} = x_2 + 0 = x_2\]

Здесь мы воспользовались правилом дифференцирования суммы функций и значениями производных, полученных на шагах 2 и 3. Запомним значение \(x_6 = x_4 + x_5 = x_1 x_2 + \sin{x_3}\) и производную \(\partial x_6 / \partial x_1\).

Шаг 5. Последний шаг, найдём производную \(\partial x_7 / \partial x_1 \equiv \partial f / \partial x_1\). Значение \(x_7\) явно определяется по значениям \(x_3\) и \(x_6\)

\[x_7 = x_7(x_3, x_6) = \frac{x_6(x_1)}{x_3(x_1)},\]

а производная по \(x_1\) имеет вид

\[\frac{\partial x_7}{\partial x_1} = \frac{ (\partial x_6 / \partial x_1 ) \times x_3 - x_6 \times (\partial x_3 / \partial x_1) }{ x^2_3 } = \frac{x_1 \times x_3 - x_6 \times 0}{x^2_3} = \frac{x_1}{x_3} , \quad x_3 \neq 0.\]

Здесь мы воспользовались правилом дифференцирования деления функций и значениями производных с шагов 1 и 4. Таким образом, мы вычислили значение первой компоненты градиента функции \(\partial f / \partial x_1\).

Отметим, что все промежуточные значения и производные выражались на протяжении алгоритма через значения аргументов функции \(x_1\), \(x_2\) и \(x_3\). При этом промежуточные значения и производные мы получали в направлении «слева-направо» по графу вычислений, т.е. от аргументов к результату \(x_7 \equiv f\). На Рисунке 8.6 показан граф вычисления значения функции \(f\) и её производной \(\partial f / \partial x_1\) в точке \([1, 2, 3]^\top\).

Рис. 8.6 Граф вычисления \(f(1, 2, 3)\) и \(\partial f / \partial x_1 (1, 2, 3)\). Вычисления распространяются «слева-направо». У каждой вершины подписаны значение промежуточной величины \(x_i\) и производной \(\partial x_i / \partial x_1\). Напоминает дуальные числа?

8.4.1. Общий случай

В общем случае задача автоматического дифференцирования сводится к поиску всех производных вида

\[\frac{\partial x_j}{\partial x_i}, \quad j = 1,\dots,V,\ i = 1,\dots,n,\ V \ge n,\]

где \(x_1\), …, \(x_n\) это аргументы функции, а \(x_1\), …, \(x_V\) промежуточные значения в графе вычислений. В примере выше аргументов было \(n = 3\), а промежуточных значений \(V = 7\).

Автоматическое дифференцирование по-разному пользуется правилом дифференцирования сложной (композитной) функции. В случае дифференцирования вперёд промежуточное значение \(x_j\) представляется в виде функции

(8.7)\[x_j = x_j( \{ x_k(x_i) \}_{k \in K} ) = x_j(x_i),\]

где \(\{x_k\}_{k \in K}\) это промежуточные значения, от которых \(x_j\) зависит явно, непосредственно (а \(K\) это множество индексов таких вершин). Т.е. на графе вычислений \(\{x_k\}_{k \in K}\) это вершины, которые связаны с \(x_j\) стоком.

Рис. 8.7 Общая схема графа вычислений \(\partial x_j / \partial x_i\) для автоматического дифференцирования вперёд. Явные связи (дуги графа) показаны прямыми стрелками, а неявные связи показаны волнистыми стрелками.

Применяя к представлению функции \(x_j\) в виде (8.7) правило дифференцирования сложной функции, получаем

\[\frac{\partial x_j}{\partial x_i} = \sum_{k \in K} \frac{\partial x_j}{\partial x_k} \frac{\partial x_k}{\partial x_i},\]

где производные \(\partial x_k / \partial x_i\) известны с предыдущих шагов обхода графа вычислений. В свою очередь, производные \(\partial x_j / \partial x_k\) вычисляются на текущем шаге обхода по явной связи \(x_j(\{ x_k \}_{k \in K})\).

8.4.2. Быстродействие и применимость

Пусть стоит задача вычисления градиента функции вида \(f: \real^n \to \real\)

\[\frac{\partial f}{\partial x_i},\ i = 1, \dots, n.\]

В этой задаче автоматическому дифференцированию вперёд требуется \(n\) проходов графа вычислений, по одному проходу на каждую производную.

Если же стоит задача найти производные функции \(f: \real \to \real^m\), т.е.

\[\frac{\partial f_j}{\partial x},\ j = 1, \dots, m,\]

то автоматическому дифференцированию вперёд требуется всего один проход графа вычислений.

В общем случае функции вида \(f: \real^n \to \real^m\) автоматическое дифференцирование вперёд эффективно для вычисления матрицы Якоби при \(n \ll m\).

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

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

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

Примечание

Воспользоваться автоматическим дифференцированием вперёд в Julia можно, например, с помощью пакета ForwardDiff.jl, [RLP16].