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

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

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

Цепное правило, прямое и обратное накопление

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

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

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

1. прямое накопление вычисляет рекурсивное отношение: с , и,${\ displaystyle {\ frac {dw_ {i}} {dx}} = {\ frac {dw_ {i}} {dw_ {i-1}}} {\ frac {dw_ {i-1}} {dx}} }$${\ displaystyle w_ {3} = y}$
2. обратное накопление вычисляет рекурсивное отношение: с .${\ displaystyle {\ frac {dy} {dw_ {i}}} = {\ frac {dy} {dw_ {i + 1}}} {\ frac {dw_ {i + 1}} {dw_ {i}}} }$${\ displaystyle w_ {0} = x}$

Накопление вперед

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

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

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

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

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

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

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

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

Операции по вычислению стоимости	Операции по вычислению производной
${\ displaystyle w_ {1} = x_ {1}}$	${\ displaystyle {\ dot {w}} _ {1} = 1}$ (семя)
${\ displaystyle w_ {2} = x_ {2}}$	${\ displaystyle {\ dot {w}} _ {2} = 0}$ (семя)
${\ displaystyle w_ {3} = w_ {1} \ cdot w_ {2}}$	${\ displaystyle {\ dot {w}} _ {3} = w_ {2} \ cdot {\ dot {w}} _ {1} + w_ {1} \ cdot {\ dot {w}} _ {2} }$
${\ displaystyle w_ {4} = \ sin w_ {1}}$	${\ displaystyle {\ dot {w}} _ {4} = \ cos w_ {1} \ cdot {\ dot {w}} _ {1}}$
${\ displaystyle w_ {5} = w_ {3} + w_ {4}}$	${\ displaystyle {\ dot {w}} _ {5} = {\ dot {w}} _ {3} + {\ dot {w}} _ {4}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автоматическое дифференцирование с использованием двойных чисел

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

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

то же самое для вычитания и деления.

Теперь полиномы можно вычислять в этой расширенной арифметике. Если , то ${\ Displaystyle P (x) = p_ {0} + p_ {1} x + p_ {2} x ^ {2} + \ cdots + p_ {n} x ^ {n}}$

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

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

аналитические функции дает список базовой арифметики и некоторых стандартных функций для новой арифметики: ${\ Displaystyle \ langle х, х '\ rangle}$

$${\ 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' \ right \ rangle \ right | & = \ left \ langle \ left | u \ right |, u '{\ mbox {знак}} u \ right \ rangle \ quad (u \ neq 0) \ end {выравнивается}}}$$

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

$${\ displaystyle g (\ langle u, u '\ rangle, \ langle v, v' \ rangle) = \ langle g (u, v), g_ {u} (u, v) u '+ g_ {v} ( и, v) v '\ rangle}$$

где и - производные по первому и второму аргументам соответственно. ${\ displaystyle g_ {u}}$${\ displaystyle g_ {v}}$${\ displaystyle g}$

Когда базовая двоичная арифметическая операция применяется к смешанным аргументам - паре и действительному числу, - действительное число сначала поднимается до . Производная функции в точке теперь находится путем вычисления с использованием вышеуказанной арифметики, которая дает в качестве результата. ${\ Displaystyle \ langle и, и '\ rangle}$${\ displaystyle c}$${\ displaystyle \ langle c, 0 \ rangle}$${\ displaystyle f: \ mathbb {R} \ to \ mathbb {R}}$${\ displaystyle x_ {0}}$${\ displaystyle f (\ langle x_ {0}, 1 \ rangle)}$${\ Displaystyle \ langle f (x_ {0}), f '(x_ {0}) \ rangle}$

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

С многомерными функциями можно работать с той же эффективностью и механизмами, что и с одномерными функциями, путем принятия оператора производной по направлению. То есть, если достаточно вычислить производную по направлению at в направлении , это можно вычислить, используя ту же арифметику, что и выше. Если требуются все элементы , то требуются оценки функций. Обратите внимание, что во многих оптимизационных приложениях действительно достаточно производной по направлению. ${\ displaystyle y '= \ nabla f (x) \ cdot x'}$${\ Displaystyle у '\ в \ mathbb {R} ^ {m}}$${\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R} ^ {m}}$${\ Displaystyle х \ в \ mathbb {R} ^ {п}}$${\ Displaystyle х '\ в \ mathbb {R} ^ {п}}$${\ displaystyle (\ langle y_ {1}, y '_ {1} \ rangle, \ ldots, \ langle y_ {m}, y' _ {m} \ rangle) = f (\ langle x_ {1}, x '_ {1} \ rangle, \ ldots, \ langle x_ {n}, x' _ {n} \ rangle)}$${\ displaystyle \ nabla f}$${\ displaystyle n}$

Высокий порядок и множество переменных

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

Выполнение

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

• Дифференцируемое программирование

Заметки

Рекомендации

дальнейшее чтение

• Ралл, Луис Б. (1981). Автоматическое дифференцирование: методы и приложения . Конспект лекций по информатике. 120 . Springer . ISBN 978-3-540-10861-0.
• Гриванк, Андреас; Вальтер, Андреа (2008). Оценка производных: принципы и методы алгоритмической дифференциации . Другие названия по прикладной математике. 105 (2-е изд.). СИАМ . ISBN 978-0-89871-659-7. Архивировано из оригинала на 2010-03-23 . Проверено 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] , Точные греки первого и второго порядка с помощью алгоритмического дифференцирования.

[2] , Сопутствующая алгоритмическая дифференциация приложений, ускоренных на GPU.

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