Быстрое дифференцирование

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM ChatGPT, GPT-5.6 Thinking и проверена участником Vadim Iamaletdinov 18:13, 18 июля 2026 (MSD)

Содержание

1 Зачем нужно быстрое дифференцирование
2 Формальная постановка
3 Прямой режим
- 3.1 Двойственные числа
4 Обратный режим
5 Пример вычисления
6 Обратное распространение ошибки
7 Вычислительная сложность
- 7.1 Время и память
8 Сравнение способов вычисления производных
9 Производные высших порядков
10 Реализация в программных системах
- 10.1 Перегрузка операций
- 10.2 Преобразование программы
11 Ограничения и типичные ошибки
12 Применения
13 История
14 См. также
15 Примечания
16 Литература

Быстрое дифференцирование — совокупность алгоритмов вычисления производных сложной функции, заданной не одной формулой, а последовательностью элементарных операций. В современной терминологии основным воплощением этой идеи является автоматическое, или алгоритмическое, дифференцирование (automatic differentiation, AD). Для скалярной функции многих переменных его обратный режим позволяет вычислить весь градиент за один прямой и один обратный проход по вычислению функции. В нейронных сетях тот же алгоритмический принцип известен как метод обратного распространения ошибки (backpropagation).

Слово «быстрое» относится прежде всего к асимптотике: стоимость вычисления градиента скалярной функции имеет тот же порядок, что и стоимость вычисления самой функции, и отличается от неё лишь постоянным множителем. Это делает дифференцирование моделей с миллионами и миллиардами параметров практически возможным. Быстрое дифференцирование лежит в основе градиентного обучения, дифференцируемого программирования, оптимального управления, обратных задач и многих методов научных вычислений.^[1]

Зачем нужно быстрое дифференцирование

Во многих задачах машинного обучения параметры $w\in{\rm R}^n$ выбираются минимизацией функции потерь

$L(w)=\frac{1}{\ell}\sum_{i=1}^{\ell}\mathcal L\bigl(a(x_i,w),y_i\bigr)+\lambda R(w),$

где $a(x_i,w)$ — прогноз модели, $\mathcal L$ — функция потерь, $R$ — регуляризатор. Градиентные методы требуют на каждой итерации вычислять

$\nabla_w L(w)=\left(\frac{\partial L}{\partial w_1},\ldots,\frac{\partial L}{\partial w_n}\right).$

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

$\frac{\partial L(w)}{\partial w_j}\approx \frac{L(w+h e_j)-L(w)}{h}.$

Кроме высокой стоимости, этот подход содержит ошибку усечения и чувствителен к округлению: слишком большое $h$ даёт грубую аппроксимацию, а слишком малое приводит к вычитанию близких чисел. Символьное дифференцирование даёт точную формулу, но может многократно дублировать одинаковые подвыражения и порождать громоздкие выражения.

Быстрое дифференцирование использует третий путь:

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

В результате вычисляется численное значение производной, а не развёрнутая символьная формула. Погрешность усечения отсутствует; остаются обычные ошибки машинной арифметики и ошибки, связанные с некорректно заданными локальными правилами дифференцирования.^[1]

Формальная постановка

Пусть программа вычисляет отображение

$F:{\rm R}^n\to{\rm R}^m,\qquad y=F(x).$

Её выполнение представляется ориентированным ациклическим вычислительным графом. Входные вершины содержат компоненты $x_1,\ldots,x_n$ , а каждая последующая вершина вычисляет элементарную операцию

$v_i=\varphi_i(v_{p_1},\ldots,v_{p_k}).$

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

Полная производная $F$ задаётся матрицей Якоби

$J_F(x)=\left(\frac{\partial y_i}{\partial x_j}\right)_{i=1,\ldots,m;\;j=1,\ldots,n}.$

Автоматическое дифференцирование обычно не строит эту матрицу явно. Вместо этого оно эффективно вычисляет произведения $J_F r$ или $J_F^{{\rm T}}q$ . Выбор одного из этих произведений приводит соответственно к прямому и обратному режимам.

Прямой режим

В прямом режиме вместе с каждым обычным значением $v_i$ , называемым основным или прямым, вычисляется касательная величина

$\dot v_i=\frac{d v_i}{dt},$

соответствующая возмущению входа $x(t)=x+t r$ . Для вершины

$v_i=\varphi_i(v_{p_1},\ldots,v_{p_k})$

касательная распространяется по правилу

$\dot v_i= \sum_{s=1}^{k} \frac{\partial\varphi_i}{\partial v_{p_s}}\dot v_{p_s}.$

Если положить $\dot x=r$ , на выходе получится

$\dot y=J_F(x)r.$

Таким образом, один прямой проход вычисляет произведение Якобиана на произвольный вектор, или JVP (Jacobian–vector product). При $r=e_j$ получается $j$ -й столбец Якобиана.

Прямой режим особенно выгоден, когда входов мало, а выходов много, например для отображения $F:{\rm R}\to{\rm R}^m$ . Для построения полного Якобиана общего отображения требуется до $n$ прямых проходов — по одному на каждый базисный вектор входного пространства.^[1]

Двойственные числа

Одна из реализаций прямого режима основана на двойственных числах

$v+\dot v\varepsilon,\qquad \varepsilon^2=0.$

Например,

$(u+\dot u\varepsilon)(v+\dot v\varepsilon) =uv+(u\dot v+\dot u v)\varepsilon.$

Коэффициент при $\varepsilon$ автоматически воспроизводит правило производной произведения. Перегрузив элементарные операции для двойственных чисел, можно выполнять исходную программу и одновременно получать направленную производную.

Обратный режим

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

Для скалярного результата $L$ каждой промежуточной переменной сопоставляется сопряжённая величина

$\bar v_i=\frac{\partial L}{\partial v_i}.$

Алгоритм состоит из двух фаз.

Прямой проход. Вычисляются все $v_i$ и фиксируются зависимости между операциями.
Обратный проход. Устанавливается $\bar L=1$ , после чего вершины обходятся в обратном топологическом порядке. Для каждого ребра $v_j\to v_i$ выполняется накопление
$\bar v_j\leftarrow \bar v_i\frac{\partial v_i}{\partial v_j}.$

Знак накопления принципиален: одна промежуточная переменная может влиять на результат несколькими путями, и её полная производная равна сумме вкладов всех этих путей.

Для векторного выхода и начального вектора $q\in{\rm R}^m$ обратный проход вычисляет

$J_F(x)^{{\rm T}}q,$

то есть VJP (vector–Jacobian product). Если $m=1$ и $q=1$ , результатом является полный градиент $\nabla F(x)$ за один обратный проход.^[1]

Пример вычисления

Рассмотрим функцию

$f(x_1,x_2)=\ln x_1+x_1x_2-\sin x_2.$

Представим её как последовательность элементарных операций:

Номер	Операция	Значение при $x_1=2,\;x_2=5$
$v_1$	$v_1=\ln x_1$	$\ln 2\approx 0{,}693$
$v_2$	$v_2=x_1x_2$	$10$
$v_3$	$v_3=\sin x_2$	$\sin 5\approx-0{,}959$
$v_4$	$v_4=v_1+v_2$	$10{,}693$
$f$	$f=v_4-v_3$	$11{,}652$

Обратный проход начинается с $\bar f=1$ . Локальные производные дают

$\bar v_4=1,\qquad \bar v_3=-1,$ $\bar v_1=\bar v_4=1,\qquad \bar v_2=\bar v_4=1.$

Далее накапливаются производные по входам:

$\bar x_1= \bar v_1\frac{1}{x_1}+\bar v_2x_2 =\frac{1}{2}+5=5{,}5,$ $\bar x_2= \bar v_2x_1+\bar v_3\cos x_2 =2-\cos 5\approx1{,}716.$

Итак,

$\nabla f(2,5)\approx(5{,}5,\;1{,}716).$

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

Обратное распространение ошибки

Обратное распространение ошибки — частный случай обратного режима для слоистой нейронной сети. Пусть

$h^{(0)}=x,$ $z^{(l)}=W^{(l)}h^{(l-1)}+b^{(l)},\qquad h^{(l)}=\sigma_l\bigl(z^{(l)}\bigr),\quad l=1,\ldots,L,$

а скалярная функция потерь равна $\mathcal L(h^{(L)},y)$ . Введём ошибки слоёв

$\delta^{(l)}=\frac{\partial\mathcal L}{\partial z^{(l)}}.$

Для выходного слоя $\delta^{(L)}$ определяется производной функции потерь и активации. Для внутренних слоёв правило цепочки даёт рекурсию

$\delta^{(l)}= \left(W^{(l+1)}\right)^{{\rm T}}\delta^{(l+1)} \circ\sigma_l'\bigl(z^{(l)}\bigr),$

где $\circ$ обозначает покомпонентное произведение. Градиенты параметров имеют вид

$\frac{\partial\mathcal L}{\partial W^{(l)}}= \delta^{(l)}\left(h^{(l-1)}\right)^{{\rm T}},\qquad \frac{\partial\mathcal L}{\partial b^{(l)}}=\delta^{(l)}.$

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

Публикация Д. Румельхарта, Дж. Хинтона и Р. Уильямса 1986 года сделала backpropagation широко известным как метод обучения многослойных сетей,^[1] однако обратный режим автоматического дифференцирования был сформулирован раньше и имеет более широкую область применения.

Вычислительная сложность

Пусть ${\rm ops}(F)$ — число элементарных арифметических операций, необходимых для вычисления $F:{\rm R}^n\to{\rm R}^m$ . Один проход автоматического дифференцирования требует порядка

$c\,{\rm ops}(F)$

операций, где $c$ — небольшая константа. Для стандартных моделей вычисления приводится теоретическая граница $c<6$ , а в типичных реализациях арифметическая работа часто возрастает примерно в 2—3 раза.^[1]

Полный Якобиан можно получить:

прямым режимом примерно за $n$ проходов;
обратным режимом примерно за $m$ проходов.

Отсюда практическое правило:

при $n\ll m$ предпочтителен прямой режим;
при $m\ll n$ предпочтителен обратный режим;
при сопоставимых $n$ и $m$ выбор зависит от структуры вычислений, разреженности и доступной памяти.

Для скалярной функции $F:{\rm R}^n\to{\rm R}$ обратный режим вычисляет весь градиент за один прямой и один обратный проход. Теорема Баура—Штрассена формализует фундаментальный факт: для функции, вычисляемой арифметической прямолинейной программой, все первые частные производные можно вычислить с арифметической сложностью, отличающейся от сложности исходной функции лишь постоянным множителем.^[1]

Время и память

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

Основной способ уменьшения памяти — контрольные точки (checkpointing, rematerialization). Сохраняется лишь часть промежуточных состояний, а остальные повторно вычисляются во время обратного прохода. Это создаёт управляемый компромисс: меньше памяти ценой дополнительного времени. Современные системы также освобождают ненужные буферы, объединяют операции, используют статический анализ времени жизни и задаваемые пользователем правила повторного вычисления.

Сравнение способов вычисления производных

Метод	Точность	Стоимость градиента скалярной функции	Основные ограничения
Ручное дифференцирование	С точностью машинной арифметики	Может быть оптимальной	Трудоёмкость, риск ошибок, сложность сопровождения
Конечные разности	Приближённая	Обычно $O(n)$ вычислений функции	Выбор шага, ошибки усечения и округления
Символьное дифференцирование	Формально точная	Зависит от размера полученной формулы	Разрастание выражений, трудности с обычным программным управлением
Прямой режим AD	С точностью машинной арифметики	$n$ проходов для полного градиента	Невыгоден при очень большом числе входов
Обратный режим AD	С точностью машинной арифметики	Один обратный проход	Хранение или повторное вычисление промежуточных значений

Автоматическое дифференцирование не следует называть ни численным, ни символьным в обычном смысле. Оно использует аналитические правила производных элементарных операций, но распространяет численные значения производных по фактически выполненной программе.^[1]

Производные высших порядков

Режимы можно вкладывать друг в друга. Например:

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

Для дважды дифференцируемой скалярной функции $f:{\rm R}^n\to{\rm R}$ и вектора $r$ произведение

$H_f(x)r=\nabla^2 f(x)r$

можно вычислить без формирования матрицы $n\times n$ . Метод Пирлмуттера применяет направленное дифференцирование к программе обратного прохода и получает точное, с учётом машинной арифметики, произведение Гессиана на вектор со стоимостью того же порядка, что и вычисление градиента.^[1]

Матрично-свободные произведения $Hr$ применяются в методах Ньютона—Крылова, оценивании кривизны, анализе чувствительности и вычислении гиперградиентов. Полный Гессиан часто не строят, поскольку его хранение требует $O(n^2)$ памяти.

Реализация в программных системах

Существуют два основных подхода.

Перегрузка операций

Числовые объекты заменяются объектами, которые вместе со значением хранят касательную информацию или записывают операцию на ленту (tape). Программа исполняется обычным образом, а граф производной формируется динамически. Подход удобен для интерактивного программирования и сложного управления потоком.

Преобразование программы

Исходная программа или промежуточное представление компилятора преобразуется в новую программу, вычисляющую значения и производные. Такой подход позволяет заранее оптимизировать граф: удалять общие подвыражения, объединять операции, планировать память и компилировать вычисления для процессоров и ускорителей.

На практике используются гибридные системы. Например:

torch.autograd в PyTorch записывает граф операций и реализует прежде всего обратный режим;^[1]
JAX предоставляет преобразования grad, jvp, vjp, а также их композиции;^[1]
TensorFlow записывает операции в tf.GradientTape и затем проходит их в обратном порядке.^[1]

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

Ограничения и типичные ошибки

Негладкие функции

Для $|x|$ , ReLU, максимума и других негладких операций классическая производная в некоторых точках не существует. Система обычно выбирает условное значение, например одну из односторонних производных или элемент субдифференциала. Это соглашение должно быть известно пользователю: автоматически полученное число не превращает негладкую функцию в дифференцируемую.

Ветвления и циклы

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

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

Дискретные операции

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

Численная устойчивость

AD точно дифференцирует реализованный алгоритм, но сам алгоритм может быть численно неустойчив. Например, программная формула для softmax без вычитания максимума способна переполниться; её автоматически полученный градиент также будет испорчен. Полезный принцип: сначала выбрать устойчивый способ вычисления функции, затем дифференцировать его.

Дифференцирование приближения

Если точная функция заменена конечным числом итераций численного метода, AD вычислит производную именно конечной программы. Она не обязана совпадать с производной предельного решения. Возможны три разных объекта:

производная усечённого алгоритма;
производная точного решения неявной задачи;
приближение нужной производной.

Различие существенно при оптимизации через численные решатели, дифференциальные уравнения и задачи с внутренним циклом оптимизации.

Проверка градиента

Даже при использовании AD полезно выполнять тесты:

сравнивать несколько случайных направленных производных с центральными разностями;
проверять скалярное тождество сопряжённости

$q^{{\rm T}}(J_Fr)=(J_F^{{\rm T}}q)^{{\rm T}}r;$

тестировать крайние значения и точки смены ветвей;
контролировать NaN, бесконечности и масштабы градиентов;
отдельно проверять пользовательские правила производных.

Конечные разности здесь используются не как основной способ обучения, а как независимая диагностическая проверка.

Применения

Быстрое дифференцирование применяется в следующих задачах:

обучение нейронных сетей и других параметрических моделей;
Градиентный спуск, квазиньютоновские и матрично-свободные методы второго порядка;
Оптимальное управление и вычисление сопряжённых переменных;
решение обратных коэффициентных задач;
дифференцируемые физические симуляторы;
вероятностное программирование и вариационный вывод;
метаобучение, подбор гиперпараметров и гиперградиенты;
анализ чувствительности и неопределённости;
дифференцируемая визуализация, рендеринг и обработка сигналов.

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

История

Идеи автоматического вычисления производных развивались вместе с программированием численных алгоритмов. Р. Венгерт в 1964 году описал разложение функции на последовательность элементарных присваиваний и автоматическое распространение производных по этой последовательности.^[1] С. Линнайнмаа сформулировал ранний вариант обратного накопления при анализе распространения ошибок округления.^[1] В 1980-х годах теория сложности и программные реализации установили обратный режим как общий метод, а популяризация backpropagation связала его с обучением многослойных нейронных сетей.^[1]^[1]

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

См. также

Примечания

Литература

Griewank A., Walther A. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. — 2-е изд.. — Philadelphia: SIAM, 2008. — 438 с. — ISBN 978-0-89871-659-7
Baydin A. G., Pearlmutter B. A., Radul A. A., Siskind J. M. Automatic Differentiation in Machine Learning: a Survey // Journal of Machine Learning Research. — 2018. — Т. 18. — № 153. — С. 1—43.
Baur W., Strassen V. The Complexity of Partial Derivatives // Theoretical Computer Science. — 1983. — Т. 22. — № 3. — С. 317—330.
Pearlmutter B. A. Fast Exact Multiplication by the Hessian // Neural Computation. — 1994. — Т. 6. — № 1. — С. 147—160.
Евтушенко Ю. Г. Оптимизация и быстрое автоматическое дифференцирование. — М.: ВЦ им. А. А. Дородницына РАН, 2013. — 144 с.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%B4%D0%B8%D1%84%D1%84%D0%B5%D1%80%D0%B5%D0%BD%D1%86%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5»

Категории: Машинное обучение | Нейронные сети | Методы оптимизации | Энциклопедия анализа данных