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

В математике и компьютерной алгебре, автоматическое дифференцирование (AD), также называемое алгоритмическое дифференцирование, вычислительное дифференцирование, автоматическое дифференцирование или просто autodiff, представляет собой набор методов для численной оценки производная функции, заданной компьютерной программой. AD использует тот факт, что каждая компьютерная программа, независимо от ее сложности, выполняет последовательность элементарных арифметических операций (сложение, вычитание, умножение, деление и т. Д.) И элементарных функций (exp, log, sin, cos и т. Д.). Путем многократного применения правила цепочки к этим операциям производные произвольного порядка могут быть вычислены автоматически с точностью до рабочей точности и с использованием не более небольшого постоянного множителя для большего числа арифметических операций, чем в исходной программе.

Рисунок 1: Как автоматическое дифференцирование связано с символическим дифференцированием

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

• 1 Правило цепочки, прямое и обратное накопление
  • 1.1 Прямое накопление
  • 1.2 Обратное накопление
  • 1.3 Помимо прямого и обратного накопления
• 2 Автоматическое дифференцирование с использованием двойных чисел
  • 2.1 Векторные аргументы и функции
  • 2.2 Высокий порядок и множество переменных
• 3 Реализация
  • 3.1 Преобразование исходного кода (SCT)
  • 3.2 Перегрузка оператора (OO)
• 4 Примечания
• 5 Ссылки
• 6 Дополнительная литература
• 7 Внешние ссылки

В основе AD лежит разложение дифференциалов, обеспечиваемое правилом цепочки. Для простой композиции

$y\; =\; f\; (g\; (h\; (x)))\; =\; f\; (g\; (h\; (w\; 0)))\; =\; f\; (g\; (w\; 1))\; =\; f\; (w\; 2)\; =\; w\; 3\; w\; 0\; знак\; равно\; XW\; 1\; знак\; равно\; час\; (вес\; 0)\; вес\; 2\; знак\; равно\; г\; (вес\; 1)\; вес\; 3\; знак\; равно\; е\; (вес\; 2)\; =\; Y\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; y\; =\; f\; (g\; (h\; (x)))\; =\; f\; (g\; (h\; (w\_\; \{0\})))\; =\; f\; (g\; (w\_\; \{1\}))\; =\; f\; (w\_\; \{2\})\; =\; w\_\; \{3\}\; \backslash \backslash \; w\_\; \{0\}\; =\; x\; \backslash \backslash \; w\_\; \{\; 1\}\; =\; h\; (w\_\; \{0\})\; \backslash \backslash \; w\_\; \{2\}\; =\; g\; (w\_\; \{1\})\; \backslash \backslash \; w\_\; \{3\}\; =\; f\; (w\_\; \{2\})\; =\; y\; \backslash \; end\; \{выровнено\}\}\}$

цепное правило дает

$dydx\; =\; dydw\; 2\; dw\; 2\; dw\; 1\; dw\; 1\; dx\; =\; df\; (w\; 2)\; dw\; 2\; dg\; (w\; 1)\; dw\; 1\; dh\; (w\; 0)\; dx\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{dy)\; \}\; \{dx\}\}\; =\; \{\backslash \; frac\; \{dy\}\; \{dw\_\; \{2\}\}\}\; \{\backslash \; frac\; \{dw\_\; \{2\}\}\; \{dw\_\; \{1\}\}\}\; \{\backslash \; frac\; \{dw\_\; \{1\}\}\; \{dx\}\}\; =\; \{\; \backslash \; frac\; \{df\; (w\_\; \{2\})\}\; \{dw\_\; \{2\}\}\}\; \{\backslash \; frac\; \{dg\; (w\_\; \{1\})\}\; \{dw\_\; \{1\}\}\}\; \{\backslash \; frac\; \{dh\; (w\_\; \{0\})\}\; \{\; dx\}\}\}$

Обычно представлены два различных режима AD: прямое накопление (или прямой режим ) и обратное накопление (или реверсивный режим ). Прямое накопление указывает, что каждый проходит по правилу цепочки изнутри наружу (то есть сначала вычисляется $dw\; 1\; /\; dx\; \{\backslash \; displaystyle\; dw\_\; \{1\}\; /\; dx\}$, а затем $dw\; 2\; /\; dw\; 1\; \{\backslash \; displaystyle\; dw\_\; \{2\}\; /\; dw\_\; \{1\}\}$и, наконец, $dy\; /\; dw\; 2\; \{\backslash \; displaystyle\; dy\; /\; dw\_\; \{2\}\}$), а обратное накопление имеет обход снаружи внутрь (сначала вычисляем $dy\; /\; dw\; 2\; \{\backslash \; displaystyle\; dy\; /\; dw\_\; \{2\}\}$, а затем $dw\; 2\; /\; dw\; 1\; \{\backslash \; displaystyle\; dw\_\; \{\; 2\}\; /\; dw\_\; \{1\}\}$и, наконец, $dw\; 1\; /\; dx\; \{\backslash \; displaystyle\; dw\_\; \{1\}\; /\; dx\}$). Более лаконично,

1. накопление вперед вычисляет рекурсивное отношение : $dwidx\; =\; dwidwi\; -\; 1\; dwi\; -\; 1\; dx\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{dw\_\; \{i\}\}\; \{dx\}\}\; =\; \{\backslash \; гидроразрыв\; \{dw\_\; \{i\}\}\; \{dw\_\; \{i-1\}\}\}\; \{\backslash \; frac\; \{dw\_\; \{i-1\}\}\; \{dx\}\}\}$с $w\; 3\; =\; y\; \{\backslash \; displaystyle\; w\_\; \{3\}\; =\; y\}$, а
2. обратное накопление вычисляет рекурсивное отношение : $dydwi\; =\; dydwi\; +\; 1\; dwi\; +\; 1\; dwi\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{dy\}\; \{\; dw\_\; \{i\}\}\}\; =\; \{\backslash \; frac\; \{dy\}\; \{dw\_\; \{i\; +\; 1\}\}\}\; \{\backslash \; frac\; \{dw\_\; \{i\; +\; 1\}\}\; \{dw\_\; \{i\}\}\}\}$с $w\; 0\; =\; x\; \{\backslash \; displaystyle\; w\_\; \{0\}\; =\; x\}$.

Как правило, как прямое, так и обратное накопление являются конкретными проявлениями применения оператора композиции программы, фиксирующего соответствующее одно из двух сопоставлений $(w,\; y)\; \{\backslash \; displaystyle\; (w,\; y)\}$.

Прямое накопление

Рисунок 2: Пример прямого накопления с вычислительным графом

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

$\partial \; y\; \partial \; x\; =\; \partial \; y\; \partial \; wn\; -\; 1\; \partial \; wn\; -\; 1\; \partial \; x\; =\; \partial \; y\; \partial \; wn\; -\; 1\; (\partial \; wn\; -\; 1\; \partial \; wn\; -\; 2\; \partial \; wn\; -\; 2\; \partial \; x)\; =\; \partial \; y\; \partial \; wn\; -\; 1\; (\partial \; wn\; -\; 1\; \partial \; wn\; -\; 2\; (\partial \; wn\; -\; 2\; \partial \; wn\; -\; 3\; \partial \; wn\; -\; 3\; \partial \; x))\; Знак\; равно\; \cdots \; \{\backslash \; Displaystyle\; \{\backslash \; frac\; \{\backslash \; partial\; y\}\; \{\backslash \; partial\; x\}\}\; =\; \{\backslash \; frac\; \{\backslash \; partial\; y\}\; \{\backslash \; partial\; w\_\; \{n-1\}\}\}\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{n-1\; \}\}\; \{\backslash \; partial\; x\}\}\; =\; \{\backslash \; frac\; \{\backslash \; partial\; y\}\; \{\backslash \; partial\; w\_\; \{n-1\}\}\}\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{n-1\}\}\; \{\backslash \; partial\; w\_\; \{n\; -2\}\}\}\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{n-2\}\}\; \{\backslash \; partial\; x\}\}\; \backslash \; right)\; =\; \{\backslash \; frac\; \{\backslash \; partial\; y\}\; \{\backslash \; partial\; w\_\; \{n-1\}\}\}\; \backslash \; left\; (\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{n-1\}\}\; \{\backslash \; partial\; w\_\; \{n-2\}\}\}\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{n-2\}\}\; \{\backslash \; partial\; w\_\; \{n-3\}\})\; \}\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{n-3\}\}\; \{\backslash \; partial\; x\}\}\; \backslash \; right)\; \backslash \; right)\; =\; \backslash \; cdots\}$

Это можно обобщить на несколько переменных как матричное произведение якобианов.

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

$w\; \dot{}\; =\; \partial \; w\; \partial \; x\; \{\backslash \; displaystyle\; \{\backslash \; dot\; \{w\}\}\; =\; \{\backslash \; frac\; \{\backslash \; partial\; w\; \}\; \{\backslash \; partial\; x\}\}\}$

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

В качестве примера рассмотрим функцию:

$z\; =\; f\; (x\; 1,\; x\; 2)\; =\; x\; 1\; x\; 2\; +\; sin\; \; x\; 1\; =\; w\; 1\; w\; 2\; +\; sin\; \; w\; 1\; =\; w\; 3\; +\; вес\; 4\; знак\; равно\; вес\; 5\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; z\; =\; f\; (x\_\; \{1\},\; x\_\; \{2\})\; \backslash \backslash \; =\; x\_\; \{1\}\; x\_\; \{2\}\; +\; \backslash \; sin\; x\_\; \{1\}\; \backslash \backslash \; =\; w\_\; \{1\}\; w\_\; \{2\}\; +\; \backslash \; sin\; w\_\; \{1\}\; \backslash \backslash \; =\; w\_\; \{3\}\; +\; w\_\; \{4\}\; \backslash \backslash \; =\; w\_\; \{5\}\; \backslash \; end\; \{align\}\}\}$

Для ясности, отдельные подвыражения были помечены переменными w i.

. Выбор независимой переменной, для которой выполняется дифференцирование, влияет на начальные значения ẇ 1 и ẇ 2. Учитывая интерес к производной этой функции по x 1, начальные значения должны быть установлены на:

$w\; \dot{}\; 1\; =\; \partial \; x\; 1\; \partial \; x\; 1\; =\; 1\; w\; \dot{}\; 2\; =\; \partial \; x\; 2\; \partial \; Икс\; 1\; знак\; равно\; 0\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; \{\backslash \; dot\; \{w\}\}\; \_\; \{1\}\; =\; \{\backslash \; frac\; \{\backslash \; partial\; x\_\; \{1\}\}\; \{\backslash \; partial\; x\_\; \{1\}\}\}\; =\; 1\; \backslash \backslash \; \{\backslash \; dot\; \{w\}\}\; \_\; \{2\}\; =\; \{\backslash \; frac\; \{\backslash \; partial\; x\_\; \{2\}\}\; \{\backslash \; partial\; x\_\; \{1\}\}\}\; =\; 0\; \backslash \; end\; \{align\}\}\}$

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

$Операции\; для\; вычисления\; значения\; Операции\; для\; вычисления\; производной\; w\; 1\; =\; x\; 1\; w\; \dot{}\; 1\; =\; 1\; (начальное\; число)\; w\; 2\; =\; x\; 2\; w\; \dot{}\; 2\; =\; 0\; (начальное\; значение)\; w\; 3\; =\; w\; 1\; \cdot \; w\; 2\; w\; \dot{}\; 3\; =\; w\; 2\; \cdot \; w\; \dot{}\; 1\; +\; w\; 1\; \cdot \; w\; \dot{}\; 2\; w\; 4\; =\; sin\; \; w\; 1\; w\; \dot{}\; 4\; =\; cos\; \; w\; 1\; \cdot \; w\; \dot{}\; 1\; w\; 5\; =\; w\; 3\; +\; w\; 4\; w\; \dot{}\; 5\; =\; w\; \dot{}\; 3\; +\; w\; \dot{}\; 4\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{l\; |\; l\}\; \{\backslash \; text\; \{Операции\; для\; вычисления\; значения\}\}\; \{\backslash \; text\; \{Операции\; для\; вычисления\; производной\}\}\; \backslash \backslash \backslash \; hline\; w\_\; \{1\}\; =\; x\_\; \{1\}\; \{\; \backslash \; dot\; \{w\}\}\; \_\; \{1\}\; =\; 1\; \{\backslash \; text\; \{(seed)\}\}\; \backslash \backslash \; w\_\; \{2\}\; =\; x\_\; \{2\}\; \{\backslash \; dot\; \{w\}\}\; \_\; \{2\}\; =\; 0\; \{\backslash \; text\; \{\; (начальное\; число)\}\}\; \backslash \backslash \; w\_\; \{3\}\; =\; w\_\; \{1\}\; \backslash \; cdot\; w\_\; \{2\}\; \{\backslash \; dot\; \{w\}\}\; \_\; \{3\}\; =\; w\_\; \{2\}\; \backslash \; cdot\; \{\backslash \; dot\; \{w\}\}\; \_\; \{\; 1\}\; +\; w\_\; \{1\}\; \backslash \; cdot\; \{\backslash \; dot\; \{w\}\}\; \_\; \{2\}\; \backslash \backslash \; w\_\; \{4\}\; =\; \backslash \; sin\; w\_\; \{1\}\; \{\backslash \; dot\; \{w\}\}\; \_\; \{4\}\; =\; \backslash \; cos\; w\_\; \{\; 1\}\; \backslash \; cdot\; \{\backslash \; dot\; \{w\}\}\; \_\; \{1\}\; \backslash \backslash \; w\_\; \{5\}\; =\; w\_\; \{3\}\; +\; w\_\; \{4\}\; \{\backslash \; dot\; \{w\}\}\; \_\; \{5\}\; =\; \{\backslash \; dot\; \{w\}\; \}\; \_\; \{3\}\; +\; \{\backslash \; dot\; \{w\}\}\; \_\; \{4\}\; \backslash \; end\; \{array\}\}\}$

Чтобы вычислить градиент этой функции примера, которая требует производных от f по отношению не только для x 1, но также для x 2, дополнительное сканирование выполняется по вычислительному графу с использованием начальных значений $w\; 1\; =\; 0;\; w\; \dot{}\; 2\; =\; 1\; \{\backslash \; displaystyle\; \{\backslash \; dot\; \{w\}\}\; \_\; \{1\}\; =\; 0;\; \{\backslash \; dot\; \{w\}\}\; \_\; \{2\}\; =\; 1\}$.

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

Прямое накопление более эффективно, чем обратное накопление для функций f: ℝ → ℝ с m ≫ n, поскольку необходимы только n разверток по сравнению с m развертками для обратного накопления.

Обратное накопление

Рисунок 3: Пример обратного накопления с вычислительным графом

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

$\partial \; y\; \partial \; x\; =\; \partial \; y\; \partial \; w\; 1\; \partial \; w\; 1\; \partial \; x\; =\; (\partial \; y\; \partial \; w\; 2\; \partial \; w\; 2\; \partial \; вес\; 1)\; \partial \; вес\; 1\; \partial \; Икс\; знак\; равно\; ((\partial \; Y\; \partial \; вес\; 3\; \partial \; вес\; 3\; \partial \; вес\; 2)\; \partial \; вес\; 2\; \partial \; вес\; 1)\; \partial \; вес\; 1\; \partial \; x\; =\; \cdots \; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{\backslash \; partial\; y\}\; \{\backslash \; partial\; x\}\}\; =\; \{\backslash \; frac\; \{\backslash \; partial\; y\}\; \{\backslash \; partial\; w\_\; \{1\}\}\}\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{1\}\}\; \{\backslash \; partial\; x\}\}\; =\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; частичный\; y\}\; \{\backslash \; partial\; w\_\; \{2\}\}\}\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{2\}\}\; \{\backslash \; partial\; w\_\; \{1\}\}\}\; \backslash \; right)\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{1\}\}\; \{\backslash \; partial\; x\; \}\}\; =\; \backslash \; left\; (\backslash \; left\; (\{\backslash \; frac\; \{\backslash \; partial\; y\}\; \{\backslash \; partial\; w\_\; \{3\}\}\}\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{3\}\}\; \{\backslash \; partial\; w\_\; \{2\}\}\}\; \backslash \; right)\; \{\; \backslash \; frac\; \{\backslash \; partial\; w\_\; \{2\}\}\; \{\backslash \; partial\; w\_\; \{1\}\}\}\; \backslash \; right)\; \{\backslash \; frac\; \{\backslash \; partial\; w\_\; \{1\}\}\; \{\backslash \; partial\; x\}\}\; =\; \backslash \; cdots\}$

При обратном накоплении интересующая нас величина - сопряженная, обозначенная чертой (w̄); это производная выбранной зависимой переменной относительно подвыражения w:

$w\; ¯\; =\; \partial \; y\; \partial \; w\; \{\backslash \; displaystyle\; \{\backslash \; bar\; \{w\}\}\; =\; \{\backslash \; frac\; \{\backslash \; partial\; y\}\; \{\backslash \; partial\; w\}\; \}\}$

Обратное накопление проходит по правилу цепочки извне внутрь или, в случае вычислительного графа на рисунке 3, сверху вниз. В примере функции используется скалярное значение, поэтому для вычисления производной используется только одно начальное значение, а для вычисления (двухкомпонентного) градиента требуется только одно сканирование вычислительного графа. Это только половина работы по сравнению с прямым накоплением, но обратное накопление требует хранения промежуточных переменных w i, а также инструкций, которые их создали в структуре данных, известной как список Венгерта (или «лента»), который может потреблять значительный объем памяти, если вычислительный граф большой. Это можно смягчить до некоторой степени, сохраняя только подмножество промежуточных переменных, а затем восстанавливая необходимые рабочие переменные путем повторения оценок, метод, известный как рематериализация. Контрольная точка также используется для сохранения промежуточных состояний.

Операции по вычислению производной с использованием обратного накопления показаны в таблице ниже (обратите внимание на обратный порядок):

$Операции\; по\; вычислению\; производной\; w\; ¯\; 5\; =\; 1\; (начальное\; значение)\; w\; ¯\; 4\; =\; w\; ¯\; 5\; вес\; ¯\; 3\; знак\; равно\; вес\; ¯\; 5\; вес\; ¯\; 2\; =\; вес\; ¯\; 3\; \cdot \; вес\; 1\; вес\; ¯\; 1\; =\; вес\; ¯\; 3\; \cdot \; вес\; 2\; +\; вес\; ¯\; 4\; \cdot \; соз\; \; вес\; 1\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{l\}\; \{\backslash \; text\; \{Операции\; для\; вычисления\; производной\}\}\; \backslash \backslash \backslash \; hline\; \{\backslash \; bar\; \{w\}\}\; \_\; \{5\}\; =\; 1\; \{\backslash \; text\; \{(seed)\}\}\; \backslash \backslash \; \{\backslash \; bar\; \{w\}\}\; \_\; \{4\}\; =\; \{\backslash \; бар\; \{w\}\}\; \_\; \{5\}\; \backslash \backslash \; \{\backslash \; bar\; \{w\}\}\; \_\; \{3\}\; =\; \{\backslash \; bar\; \{w\}\}\; \_\; \{5\}\; \backslash \backslash \; \{\backslash \; bar\; \{w\}\}\; \_\; \{2\}\; =\; \{\backslash \; бар\; \{w\}\}\; \_\; \{3\}\; \backslash \; cdot\; w\_\; \{1\}\; \backslash \backslash \; \{\backslash \; bar\; \{w\}\}\; \_\; \{1\}\; =\; \{\backslash \; bar\; \{w\}\}\; \_\; \{3\}\; \backslash \; cdot\; w\_\; \{2\}\; +\; \{\backslash \; bar\; \{w\}\}\; \_\; \{4\}\; \backslash \; cdot\; \backslash \; cos\; w\_\; \{1\}\; \backslash \; end\; \{array\}\}\}$

Графом потока данных вычисления можно управлять, чтобы вычислить градиент исходного вычисления. Это делается путем добавления сопряженного узла для каждого основного узла, соединенного смежными ребрами, которые параллельны основным ребрам, но текут в противоположном направлении. Узлы сопряженного графа представляют собой умножение на производные функций, вычисленных узлами в прямом. Например, сложение в основных причинах разветвления в смежных; разветвление в первичных причинах сложение в смежных; унарная функция y = f (x) в прямых причинах x̄ = ȳ f ′ (x) в сопряженном; и т.д.

Обратное накопление более эффективно, чем прямое накопление для функций f: ℝ → ℝ с m ≪ n, поскольку необходимы только m разверток, по сравнению с n развертками для прямого накопления.

Обратный режим AD был впервые опубликован в 1976 году Сеппо Линнаинмаа.

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

Помимо прямого и обратного накопления

Прямое и обратное накопление - это всего лишь два (крайних) способа обхода правила цепочки. Задача вычисления полного якобиана f: ℝ → ℝ с минимальным числом арифметических операций известна как задача оптимального якобиана накопления (OJA), которая является NP-полной. Центральным в этом доказательстве является идея о том, что между локальными частичными элементами, которые маркируют ребра графа, могут существовать алгебраические зависимости. В частности, две или более метки края могут быть признаны равными. Сложность проблемы остается открытой, если предположить, что все метки ребер уникальны и алгебраически независимы.

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

. Замените каждое число $x\; \{\backslash \; displaystyle\; \backslash ,\; x\}$числом $x\; +\; x\; \prime \; \epsilon \; \{\backslash \; displaystyle\; x\; +\; x\; \text{'}\backslash \; varepsilon\}$, где $x\; \prime \; \{\backslash \; displaystyle\; x\text{'}\}$- действительное число, но $\epsilon \; \{\backslash \; displaystyle\; \backslash \; varepsilon\}$- абстрактное число со свойством $\epsilon \; 2\; =\; 0\; \{\backslash \; displaystyle\; \backslash \; varepsilon\; ^\; \{2\}\; =\; 0\}$(бесконечно малое ; см. Гладкий анализ бесконечно малых ). Используя только это, обычная арифметика дает

$(x\; +\; x\; \prime \; \epsilon )\; +\; (y\; +\; y\; \prime \; \epsilon )\; =\; x\; +\; y\; +\; (x\; \prime \; +\; y\; \prime )\; \epsilon \; (x\; +\; x\; \prime \; \epsilon )\; \cdot \; (y\; +\; y\; \prime \; {\rm E})\; знак\; равно\; xy\; +\; xy\; \prime \; \epsilon \; +\; yx\; \prime \; \epsilon \; +\; x\; \prime \; y\; \prime \; \epsilon \; 2\; =\; xy\; +\; (xy\; \prime \; +\; yx\; \prime )\; \epsilon \; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; (x\; +\; x\; \text{'}\backslash \; varepsilon)\; +\; (\; y\; +\; y\; \text{'}\backslash \; varepsilon)\; =\; x\; +\; y\; +\; (x\text{'}\; +\; y\; \text{'})\; \backslash \; varepsilon\; \backslash \backslash \; (x\; +\; x\text{'}\; \backslash \; varepsilon)\; \backslash \; cdot\; (y\; +\; y\; \text{'}\backslash \; varepsilon)\; =\; xy\; +\; xy\text{'}\; \backslash \; varepsilon\; +\; yx\; \text{'}\backslash \; varepsilon\; +\; x\text{'}y\text{'}\; \backslash \; varepsilon\; ^\; \{2\}\; =\; xy\; +\; (xy\; \text{'}+\; yx\text{'})\; \backslash \; varepsilon\; \backslash \; end\; \{align\}\}\}$

и аналогично для вычитания и деления.

Теперь многочлены могут быть вычислены в этой расширенной арифметике. Если $P\; (x)\; =\; p\; 0\; +\; p\; 1\; x\; +\; p\; 2\; x\; 2\; +\; \cdots \; +\; pnxn\; \{\backslash \; displaystyle\; P\; (x)\; =\; p\_\; \{0\}\; +\; p\_\; \{1\}\; x\; +\; p\_\; \{2\}\; x\; ^\; \{\; 2\}\; +\; \backslash \; cdots\; +\; p\_\; \{n\}\; x\; ^\; \{n\}\}$, тогда

$P\; (x\; +\; x\; \prime \; \epsilon )\; =\; p\; 0\; +\; p\; 1\; (x\; +\; x\; \prime \; \epsilon )\; +\; \cdots \; +\; pn\; (x\; +\; x\; \prime \; \epsilon )\; n\; =\; p\; 0\; +\; p\; 1\; x\; +\; \cdots \; +\; pnxn\; +\; p\; 1\; x\; \prime \; \epsilon \; +\; 2\; p\; 2\; xx\; \prime \; \epsilon \; +\; \cdots \; +\; npnxn\; -\; 1\; x\; \prime \; \epsilon \; =\; P\; (x)\; +\; P\; (1)\; (Икс)\; Икс\; \text{'}\epsilon \; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{Выровненный\}\; P\; (х\; +\; х\text{'}\; \backslash \; varepsilon)\; =\; p\_\; \{0\}\; +\; p\_\; \{1\}\; (x\; +\; x\; \text{'}\backslash \; varepsilon)\; +\; \backslash \; cdots\; +\; p\_\; \{n\}\; (x\; +\; x\; \text{'}\backslash \; varepsilon)\; ^\; \{n\}\; \backslash \backslash \; =\; p\_\; \{0\}\; +\; p\_\; \{1\}\; x\; +\; \backslash \; cdots\; +\; p\_\; \{n\}\; x\; ^\; \{n\}\; +\; p\_\; \{1\}\; x\text{'}\; \backslash \; varepsilon\; +\; 2p\_\; \{2\}\; xx\; \text{'}\backslash \; varepsilon\; +\; \backslash \; cdots\; +\; np\_\; \{n\}\; x\; ^\; \{n-1\}\; x\text{'}\; \backslash \; varepsilon\; \backslash \backslash \; =\; P\; (x)\; +\; P\; ^\; \{(1)\}\; (x)\; x\; \text{'}\; \backslash \; varepsilon\; \backslash \; end\; \{align\}\}\}$

где $P\; (1)\; \{\backslash \; displaystyle\; P\; ^\; \{(1)\}\}$обозначает производную от $P\; \{\backslash \; displaystyle\; P\}$относительно своего первого аргумента, и $x\; \prime \; \{\backslash \; displaystyle\; x\; \text{'}\}$, называемый начальным значением, можно выбрать произвольно.

Новая арифметика состоит из упорядоченных пар, элементов, записанных $⟨x,\; x\; \prime ⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; x,\; x\; \text{'}\backslash \; rangle\}$, с обычной арифметикой для первого компонента и арифметикой дифференцирования первого порядка для второго компонента, как описано выше. Распространение приведенных выше результатов о полиномах на аналитические функции дает список основных арифметических и некоторых стандартных функций для новой арифметики:

$⟨u, u ′⟩ + ⟨v, v ′⟩ = ⟨u + v, u ′ + v ′⟩ ⟨u, u ′⟩ - ⟨v, v ′⟩ = ⟨u - v, u ′ - v ′⟩ ⟨u, u ′⟩ ∗ ⟨v, v ′⟩ = ⟨uv, u ′ v + uv ′⟩ ⟨u, u ′⟩ / ⟨v, v ′⟩ = ⟨uv, u ′ v - uv ′ v 2⟩ (v ≠ 0) sin ⁡ ⟨u, u ′⟩ = ⟨sin ⁡ (u), u ′ cos ⁡ (u)⟩ cos ⁡ ⟨u, u ′⟩ = ⟨cos ⁡ (u), - u ′ sin ⁡ (u)⟩ exp ⁡ ⟨u, u ′⟩ = ⟨exp ⁡ u, u ′ exp ⁡ u⟩ log ⁡ ⟨u, u ′⟩ = ⟨log ⁡ (u), u ′ / u⟩ (u>0) ⟨u, u ′⟩ k = ⟨uk, kuk - 1 u ′ ⟩ (U ≠ 0) | ⟨U, u ′⟩ | = ⟨| u | U 'знак U⟩ (U ≠ 0) {\ Displaystyle {\ begin {align} \ left \ langle u, u' \ right \ rangle + \ left \ langle v, v '\ right \ rangle = \ left \ langle u + v, u '+ v' \ right \ rangle \\\ left \ langle u, u '\ right \ rangle - \ left \ langle v, v' \ right \ rangle = \ left \ langle uv, u '-v' \ right \ rangle \\\ left \ langle u, u '\ right \ rangle * \ left \ langle v, v' \ right \ rangle = \ left \ langle uv, u'v + uv '\ right \ rangle \\\ left \ langle u, u '\ right \ rangle / \ left \ langle v, v' \ right \ rangle = \ left \ langle {\ frac {u} {v}}, {\ frac {u'v-uv '} {v ^ {2}}} \ right \ rangle \ quad (v \ neq 0) \\\ sin \ left \ langle u, u' \ right \ rangle = \ left \ langle \ sin (u), u '\ cos (u) \ right \ rangle \\\ cos \ left \ langle u, u' \ right \ rangle = \ left \ langle \ cos (u), - u '\ sin (u) \ right \ rangle \\\ exp \ left \ langle u, u '\ right \ rangle = \ left \ langle \ exp u, u' \ exp u \ right \ rangle \\\ log \ left \ langle u, u '\ right \ rangle = \ left \ langle \ log (u), u' / u \ right \ rangle \ quad (u>0) \\\ left \ langle u, u '\ right \ rangle ^ {k} = \ left \ langle u ^ {k}, ku ^ {k-1} u '\ right \ rangle \ quad (u \ neq 0) \\\ left | \ left \ langle u, u' \ правый \ правый \ правый | = \ l eft \ langle \ left | u \ right |, u '{\ t_dv {sign}} u \ right \ rangle \ quad (u \ neq 0) \ end {выравнивается}}}$

и в целом для примитивной функции $g\; \{\backslash \; displaystyle\; g\}$,

$g\; (⟨u,\; u\; \prime ⟩,\; ⟨v,\; v\; \prime ⟩)\; =\; ⟨g\; (u,\; v)\; гу\; (и,\; v)\; и\; \text{'}+\; gv\; (и,\; v)\; v\text{'}⟩\; \{\backslash \; displaystyle\; g\; (\backslash \; langle\; u,\; u\; \text{'}\backslash \; rangle,\; \backslash \; langle\; v,\; v\text{'}\; \backslash \; rangle)\; =\; \backslash \; langle\; g\; (u,\; v),\; g\_\; \{u\}\; (u,\; v)\; u\; \text{'}+\; g\_\; \{v\}\; (u,\; v)\; v\text{'}\; \backslash \; rangle\}$

где $gu\; \{\backslash \; displaystyle\; g\_\; \{u\}\}$и $gv\; \{\backslash \; displaystyle\; g\_\; \{v\}\}$являются производными от $g\; \{\backslash \; displaystyle\; g\}$по его первому и второму аргументам соответственно.

Когда к смешанным аргументам применяется базовая двоичная арифметическая операция - пара $⟨u,\; u\; \prime ⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; u,\; u\; \text{'}\backslash \; rangle\}$и действительное number $c\; \{\backslash \; displaystyle\; c\}$- действительное число сначала поднимается до $⟨c,\; 0⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; c,\; 0\; \backslash \; rangle\}$. Производная функции $f:\; R\; \to \; R\; \{\backslash \; displaystyle\; f:\; \backslash \; mathbb\; \{R\}\; \backslash \; rightarrow\; \backslash \; mathbb\; \{R\}\}$в точке $x\; 0\; \{\backslash \; displaystyle\; x\_\; \{\; 0\}\}$теперь находится путем вычисления $f\; (⟨x\; 0,\; 1⟩)\; \{\backslash \; displaystyle\; f\; (\backslash \; langle\; x\_\; \{0\},\; 1\; \backslash \; rangle)\}$с использованием вышеуказанная арифметика, которая дает $⟨f\; (x\; 0),\; f\; \prime \; (x\; 0)⟩\; \{\backslash \; displaystyle\; \backslash \; langle\; f\; (x\_\; \{0\}),\; f\; \text{'}(x\_\; \{0\})\; \backslash \; rangle\}$как результат.

Векторные аргументы и функции

Функции с несколькими переменными могут обрабатываться с той же эффективностью и механизмами, что и функции с одной переменной, путем принятия оператора производной по направлению. То есть, если достаточно вычислить $y\; \prime \; =\; \nabla \; f\; (x)\; \cdot \; x\; \prime \; \{\backslash \; displaystyle\; y\; \text{'}=\; \backslash \; nabla\; f\; (x)\; \backslash \; cdot\; x\text{'}\}$, производную по направлению $y\; \prime \; \in \; р\; м\; \{\backslash \; displaystyle\; y\; \text{'}\backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{m\}\}$из $f:\; R\; n\; \to \; R\; m\; \{\backslash \; displaystyle\; f:\; \backslash \; mathbb\; \{\; R\}\; ^\; \{n\}\; \backslash \; rightarrow\; \backslash \; mathbb\; \{R\}\; ^\; \{m\}\}$в $x\; \in \; R\; n\; \{\backslash \; displaystyle\; x\; \backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\}$в направлении $x\; \prime \; \in \; R\; n\; \{\backslash \; displaystyle\; x\; \text{'}\backslash \; in\; \backslash \; mathbb\; \{R\}\; ^\; \{n\}\}$, это может быть вычислено как $(⟨y\; 1,\; y\; 1\; \prime ⟩,\dots ,\; ⟨ym,\; ym\; \prime ⟩)\; =\; f\; (⟨x\; 1,\; x\; 1\; \prime ⟩,\dots ,\; ⟨xn,\; xn\; \prime ⟩)\; \{\backslash \; displaystyle\; (\backslash \; langle\; y\_\; \{1\},\; y\; \text{'}\; \_\; \{1\}\; \backslash \; rangle,\; \backslash \; ldots,\; \backslash \; langle\; y\_\; \{m\},\; y\; \text{'}\_\; \{m\}\; \backslash \; rangle)\; =\; f\; (\backslash \; langle\; x\_\; \{1\},\; x\text{'}\; \_\; \{1\}\; \backslash \; rangle,\; \backslash \; ldots,\; \backslash \; langle\; x\_\; \{n\},\; x\; \text{'}\_\; \{n\}\; \backslash \; rangle)\}$используя ту же арифметику, что и выше. Если все элементы $\nabla \; f\; \{\backslash \; displaystyle\; \backslash \; nabla\; f\}$требуются, то требуются оценки функции $n\; \{\backslash \; displaystyle\; n\}$. Обратите внимание, что во многих оптимизационных приложениях действительно достаточно производной по направлению.

Высокий порядок и многие переменные

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

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

Преобразование исходного кода (SCT)

Рисунок 4: Пример того, как может работать преобразование исходного кода

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

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

Перегрузка оператора (OO)

Рисунок 5: Пример того, как может работать перегрузка оператора

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

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

Перегрузка операторов как для прямого, так и для обратного накопления может хорошо подходить для приложений, где объекты являются векторами действительных чисел, а не скалярами. Это потому, что лента содержит векторные операции; это может облегчить вычислительно эффективные реализации, в которых каждая векторная операция выполняет множество скалярных операций. Методы векторного сопряженного алгоритмического дифференцирования (векторного AAD) могут использоваться, например, для дифференцирования значений, вычисленных с помощью моделирования Монте-Карло.

Примерами реализаций автоматического дифференцирования с перегрузкой операторов в C ++ являются библиотеки Adept и Stan.

• Rall, Louis B. (1981). Автоматическое дифференцирование: методы и приложения. Конспект лекций по информатике. 120 . Спрингер. ISBN 978-3-540-10861-0.
• Гриванк, Андреас; Вальтер, Андреа (2008). Оценка производных: принципы и методы алгоритмического дифференцирования. Другие названия по прикладной математике. 105 (2-е изд.). СИАМ. ISBN 978-0-89871-659-7. Архивировано с оригинального 23 марта 2010 г. Проверено 21 октября 2009 г.
• Нейдингер, Ричард (2010). «Введение в автоматическое дифференцирование и объектно-ориентированное программирование MATLAB» (PDF). SIAM Обзор. 52 (3): 545–563. CiteSeerX 10.1.1.362.6580. doi : 10.1137 / 080743627. Проверено 15 марта 2013 г.
• Науманн, Уве (2012). Искусство дифференциации компьютерных программ. Программное обеспечение-среды-инструменты. СИАМ. ISBN 978-1-611972-06-1.
• Хенрард, Марк (2017). Объяснение алгоритмической дифференциации в финансах. Объяснение финансового инжиниринга. Пэлгрейв Макмиллан. ISBN 978-3-319-53978-2.

• www.autodiff.org, «сайт входа на все, что вы хотите знать об автоматическом различении»
• Автоматическая дифференциация параллельных программ OpenMP
• Автоматическая дифференциация, шаблоны C ++ и фотограмметрия
• Автоматическая дифференциация, подход с перегрузкой оператора
• Вычисление аналитических производных любой программы на Fortran77, Fortran95 или C через веб-интерфейс Автоматическое дифференцирование программ на языке Fortran
• Описание и пример кода для прямого автоматического дифференцирования в Scala
• finmath-lib расширения автоматического дифференцирования, автоматическое дифференцирование для случайных величин (реализация в Java стохастического автоматического дифференцирования).
• Сопряженное алгоритмическое дифференцирование: калибровка и теорема о неявной функции
• Статья об автоматическом различении на основе шаблонов C ++ и реализация
• Касательная Отлаживаемые производные от источника к источнику
• [1 ], Exac t Греки первого и второго порядка по алгоритмической дифференциации
• [2], сопряженной алгоритмической дифференциации приложений с ускорением на GPU
• [3], вспомогательных методов в программных средствах вычислительной финансовой поддержки для алгоритмической дифференциации

.