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

Techniques to evaluate the derivative of a function specified by a computer program

В математике и компьютерной алгебре автоматическое дифференцирование ( auto-дифференциация , autodiff или AD ) , также называемое алгоритмическим дифференцированием , вычислительным дифференцированием , ^{[1] [2]} представляет собой набор методов для вычисления частной производной функции, заданной компьютером. программа.

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

Отличие от других методов дифференциации

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

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

Приложения

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

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

Цепное правило частных производных сложных функций

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

$${\displaystyle {\begin{aligned}y&=f(g(h(x)))=f(g(h(w_{0})))=f(g(w_{1}))=f(w_{2})=w_{3}\\w_{0}&=x\\w_{1}&=h(w_{0})\\w_{2}&=g(w_{1})\\w_{3}&=f(w_{2})=y\end{aligned}}}$$

$${\displaystyle {\frac {\partial y}{\partial x}}={\frac {\partial y}{\partial w_{2}}}{\frac {\partial w_{2}}{\partial w_{1}}}{\frac {\partial w_{1}}{\partial x}}={\frac {\partial f(w_{2})}{\partial w_{2}}}{\frac {\partial g(w_{1})}{\partial w_{1}}}{\frac {\partial h(w_{0})}{\partial x}}}$$

Два типа автоматического дифференцирования

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

• прямое накопление (также называемое восходящим , прямым или касательным режимом )
• обратное накопление (также называемое нисходящим , обратным режимом или присоединенным режимом )

Прямое накопление указывает, что правило цепочки проходит изнутри наружу (то есть сначала вычисляется , а затем и наконец ), тогда как обратное накопление предполагает обход снаружи внутрь (сначала вычисляется , а затем и наконец ). Более кратко, ${\displaystyle \partial w_{1}/\partial x}$ ${\displaystyle \partial w_{2}/\partial w_{1}}$ ${\displaystyle \partial y/\partial w_{2}}$ ${\displaystyle \partial y/\partial w_{2}}$ ${\displaystyle \partial w_{2}/\partial w_{1}}$ ${\displaystyle \partial w_{1}/\partial x}$

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

Значение частной производной, называемой семенем , распространяется вперед или назад и изначально равно или . Прямое накопление оценивает функцию и вычисляет производную по одной независимой переменной за один проход. Поэтому для каждой независимой переменной необходим отдельный проход, при котором производная по этой независимой переменной устанавливается равной единице ( ), а всем остальным — нулю ( ). Напротив, обратное накопление требует оценки частичных функций для частных производных. Поэтому обратное накопление сначала оценивает функцию и вычисляет производные по всем независимым переменным за дополнительный проход. ${\displaystyle {\frac {\partial x}{\partial x}}=1}$ ${\displaystyle {\frac {\partial y}{\partial y}}=1}$ ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ ${\displaystyle {\frac {\partial x_{1}}{\partial x_{1}}}=1}$ ${\displaystyle {\frac {\partial x_{2}}{\partial x_{1}}}=\dots ={\frac {\partial x_{n}}{\partial x_{1}}}=0}$

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

• Прямое накопление более эффективно, чем обратное накопление, для функций f : Rn → Rm с n ≪ m ,  поскольку необходимо только n проходов по ^{сравнению с} m проходами для обратного накопления.
• Обратное накопление более эффективно, чем прямое накопление, для функций f : Rn → Rm с n ≫ m ,  поскольку необходимо только m проходов по ^{сравнению с} n проходами для прямого накопления.

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

Прямое накопление было предложено Р.Э. Венгертом в 1964 году. ^[3] По словам Андреаса Гриванка, обратное накопление предлагалось с конца 1960-х годов, но изобретатель неизвестен. ^[4] Сеппо Линнаинмаа опубликовал результаты обратного накопления в 1976 году. ^[5]

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

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

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

$${\displaystyle {\begin{aligned}{\frac {\partial y}{\partial x}}&={\frac {\partial y}{\partial w_{n-1}}}{\frac {\partial w_{n-1}}{\partial x}}\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{n-1}}{\partial w_{n-2}}}{\frac {\partial w_{n-2}}{\partial x}}\right)\\[6pt]&={\frac {\partial y}{\partial w_{n-1}}}\left({\frac {\partial w_{n-1}}{\partial w_{n-2}}}\left({\frac {\partial w_{n-2}}{\partial w_{n-3}}}{\frac {\partial w_{n-3}}{\partial x}}\right)\right)\\[6pt]&=\cdots \end{aligned}}}$$

якобианов

По сравнению с обратным накоплением прямое накопление является естественным и простым в реализации, поскольку поток производной информации совпадает с порядком оценки. К каждой переменной добавляется ее производная (хранящаяся в виде числового значения, а не символьного выражения). ${\displaystyle w_{i}}$ ${\displaystyle {\dot {w}}_{i}}$

$${\displaystyle {\dot {w}}_{i}={\frac {\partial w_{i}}{\partial x}}}$$

Используя цепное правило, если в вычислительном графе есть предшественники: ${\displaystyle w_{i}}$

${\displaystyle {\dot {w}}_{i}=\sum _{j\in \{{\text{predecessors of i}}\}}{\frac {\partial w_{i}}{\partial w_{j}}}{\dot {w}}_{j}}$

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

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

$${\displaystyle {\begin{aligned}y&=f(x_{1},x_{2})\\&=x_{1}x_{2}+\sin x_{1}\\&=w_{1}w_{2}+\sin w_{1}\\&=w_{3}+w_{4}\\&=w_{5}\end{aligned}}}$$

${\displaystyle w_{i}}$

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

$${\displaystyle {\begin{aligned}{\dot {w}}_{1}={\frac {\partial w_{1}}{\partial x_{1}}}={\frac {\partial x_{1}}{\partial x_{1}}}=1\\{\dot {w}}_{2}={\frac {\partial w_{2}}{\partial x_{1}}}={\frac {\partial x_{2}}{\partial x_{1}}}=0\end{aligned}}}$$

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

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

Выполнение

Псевдокод

Прямое накопление вычисляет функцию и производную (но только для одной независимой переменной) за один проход. Связанный вызов метода ожидает , что выражение Z будет получено относительно переменной V. Метод возвращает пару оцениваемой функции и ее производной. Метод рекурсивно обходит дерево выражений до тех пор, пока не будет достигнута переменная. Если запрашивается производная по этой переменной, ее производная равна 1, в противном случае — 0. Затем вычисляются частичная функция и частная производная. ^[6]

кортеж < float , float > AssessmentAndDerive ( Expression Z , Variable V ) { if isVariable ( Z ) if ( Z = V ) return { valueOf ( Z ), 1 }; еще возврат { valueOf ( Z ), 0 }; иначе, если ( Z = A + B ) { a , a ' } = AssessmentAndDerive ( A , V ); { b , b ' } = AssessmentAndDerive ( B , V ); возврат { а + б , а ' + б ' }; иначе, если ( Z = A - B ) { a , a ' } = AssessmentAndDerive ( A , V ); { b , b ' } = AssessmentAndDerive ( B , V ); вернуть { а - б , а' - б ' } ; иначе, если ( Z = A * B ) { a , a ' } = AssessmentAndDerive ( A , V ); { b , b ' } = AssessmentAndDerive ( B , V ); return { a * b , b * a ' + a * b ' }; }                                                                                              

Питон

класс  ValueAndPartial :  def  __init__ ( self ,  value ,  parts ):  self . значение  =  значение  себя . частичный  =  частичный def  toList ( self ):  return  [ self . ценность ,  сам . частичный ] Выражение класса :  def  __add__ ( self ,  Other ):  return  Plus ( self ,  Other ) def  __mul__ ( self ,  other ):  return  Multiply ( self ,  other ) Переменная класса ( Выражение ):  def  __init__ ( self ,  значение ):  self . значение  =  значение def  AssessmentAndDerive ( self ,  переменная ):  частичный  =  1  , если  сам  ==  переменная  , иначе  0  return  ValueAndPartial ( self . value ,  частичный )класс  Plus ( Выражение ):  def  __init__ ( self ,  выражениеA ,  выражениеB ):  self . выражениеA  =  выражениеA  self . выражениеB  =  выражениеB def  AssessmentAndDerive ( self ,  переменная ):  valueA ,  partsA  =  self . выражение А. AssessmentAndDerive ( переменная ) . toList ()  valueB ,  частичныйB  =  self . выражениеБ . AssessmentAndDerive ( переменная ) . toList ()  возвращает  ValueAndPartial ( значениеA  +  значениеB ,  частичноеA  +  частичноеB )класс  Multiply ( Expression ):  def  __init__ ( self ,  выражениеA ,  выражениеB ):  self . выражениеA  =  выражениеA  self . выражениеB  =  выражениеB def  AssessmentAndDerive ( self ,  переменная ):  valueA ,  partsA  =  self . выражение А. AssessmentAndDerive ( переменная ) . toList ()  valueB ,  частичныйB  =  self . выражениеБ . AssessmentAndDerive ( переменная ) . toList ()  возвращает  ValueAndPartial ( valueA  *  valueB ,  valueB  *  partsA  +  valueA  *  partsB )# Пример: нахождение частей z = x * (x + y) + y * y в (x, y) = (2, 3) x  =  Variable ( 2 ) y  =  Variable ( 3 ) z  =  x  *  ( x  +  y )  +  y  *  y xPartial  =  z . оценитьAndDerive ( x ) . частичный yPartial  =  z . оценитьAndDerive ( y ) . частичная печать ( "∂z/∂x =" ,  xPartial )  # Вывод: ∂z/∂x = 7 print ( "∂z/∂y =" ,  yPartial )  # Вывод: ∂z/∂y = 8

С++

#include <iostream> struct ValueAndPartial { значение с плавающей запятой , частичное ; }; структурная переменная ; struct Expression { virtual ValueAndPartial AssessmentAndDerive ( Переменная * переменная ) = 0 ; }; struct Variable : public Expression { значение с плавающей запятой ; Переменная ( значение с плавающей запятой ) : значение ( значение ) {} ValueAndPartial AssessmentAndDerive ( Переменная * переменная ) { float частичное = ( это == переменная ) ? 1,0ф : 0,0ф ; возврат { значение , частичное }; } }; struct Plus : public Expression { Expression * a , * b ; Плюс ( Выражение * a , Выражение * b ) : a ( a ), b ( b ) {} ValueAndPartial AssessmentAndDerive ( Переменная * переменная ) { auto [ valueA , PartialA ] = a -> AssessmentAndDerive ( переменная ); auto [ valueB , частичныйB ] = b -> AssessmentAndDerive ( переменная ); return { значениеA + значениеB , частичныйA + частичныйB }; } }; struct Multiply : public Expression { Expression * a , * b ; Умножить ( Выражение * a ,                                                                                          Выражение * b ) : a ( a ), b ( b ) {} ValueAndPartial AssessmentAndDerive ( Переменная * переменная ) { auto [ valueA , PartialA ] = a -> AssessmentAndDerive ( переменная ); auto [ valueB , частичныйB ] = b -> AssessmentAndDerive ( переменная ); return { значениеA * значениеB , значениеB * частичное A + значениеA * частичноеB }; } }; int main () { // Пример: нахождение частей z = x * (x + y) + y * y at (x, y) = (2, 3) Переменная x ( 2 ), y ( 3 ); Плюс p1 ( & x , & y ); Умножьте m1 ( & x , & p1 ); Умножьте m2 ( & y , & y ); Плюс z ( & m1 , & m2 ); плавающий xPartial = z . оценитьAndDerive ( & x ). частичный ; плавать yPartial = z . оценитьAndDerive ( & y ). частичный ; std :: cout << "∂z/∂x = " << xPartial << ", " << "∂z/∂y = " << yPartial << std :: endl ; // Вывод: ∂z/∂x = 7, ∂z/∂y = 8 return 0 ; }                                                                         

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

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

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

$${\displaystyle {\begin{aligned}{\frac {\partial y}{\partial x}}&={\frac {\partial y}{\partial w_{1}}}{\frac {\partial w_{1}}{\partial x}}\\&=\left({\frac {\partial y}{\partial w_{2}}}{\frac {\partial w_{2}}{\partial w_{1}}}\right){\frac {\partial w_{1}}{\partial x}}\\&=\left(\left({\frac {\partial y}{\partial w_{3}}}{\frac {\partial w_{3}}{\partial w_{2}}}\right){\frac {\partial w_{2}}{\partial w_{1}}}\right){\frac {\partial w_{1}}{\partial x}}\\&=\cdots \end{aligned}}}$$

При обратном накоплении процентная сумма представляет собой сопряженную величину , обозначенную чертой ; это производная выбранной зависимой переменной по отношению к подвыражению : ${\displaystyle {\bar {w}}_{i}}$ ${\displaystyle w_{i}}$

$${\displaystyle {\bar {w}}_{i}={\frac {\partial y}{\partial w_{i}}}}$$

Используя цепное правило, если в вычислительном графе есть преемники: ${\displaystyle w_{i}}$

${\displaystyle {\bar {w}}_{i}=\sum _{j\in \{{\text{successors of i}}\}}{\bar {w}}_{j}{\frac {\partial w_{j}}{\partial w_{i}}}}$

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

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

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

Операции по вычислению производной

${\displaystyle {\bar {w}}_{5}=1{\text{ (seed)}}}$

${\displaystyle {\bar {w}}_{4}={\bar {w}}_{5}\cdot 1}$

${\displaystyle {\bar {w}}_{3}={\bar {w}}_{5}\cdot 1}$

${\displaystyle {\bar {w}}_{2}={\bar {w}}_{3}\cdot w_{1}}$

${\displaystyle {\bar {w}}_{1}={\bar {w}}_{3}\cdot w_{2}+{\bar {w}}_{4}\cdot \cos w_{1}}$

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

Выполнение

Псевдокод

Обратное накопление требует двух проходов: при прямом проходе сначала вычисляется функция, а частичные результаты кэшируются. При обратном проходе вычисляются частные производные, а полученное ранее значение подвергается обратному распространению. Соответствующий вызов метода ожидает, что выражение Z будет производным и начальным значением будет производное значение родительского выражения. Для верхнего выражения Z, полученного относительно Z, это значение равно 1. Метод рекурсивно обходит дерево выражений до тех пор, пока не будет достигнута переменная, и добавляет текущее начальное значение к производному выражению. ^{[8] [9]}

void Derivative ( Выражение Z , семя с плавающей запятой ) { if isVariable ( Z ) partsialDerivativeOf ( Z ) += семя ; иначе , если ( Z = A + B ) получить ( A , семя ); получить ( B , семя ); иначе , если ( Z = A - B ) получить ( A , семя ); получить ( B , - семя ); иначе, если ( Z = A * B ) получить ( A , valueOf ( B ) * семя ); получить ( B , valueOf ( A ) * семя ); }                                               

Питон

 Выражение класса :  def  __add__ ( self ,  other ):  return  Plus ( self ,  other )  def  __mul__ ( self ,  other ):  return  Multiply ( self ,  other ) Переменная класса ( Выражение ):  def  __init__ ( self ,  значение ):  self . значение  =  значение  себя . частичный  =  0 def  оценить ( self ):  пройти def  получить ( self ,  семя ):  self . частичный  +=  семякласс  Plus ( Выражение ):  def  __init__ ( self ,  выражениеA ,  выражениеB ):  self . выражениеA  =  выражениеA  self . выражениеB  =  выражениеB  self . значение  =  Нет def  оценить ( self ):  self . выражение А. оценить ()  себя . выражениеБ . оценить ()  себя . значение  =  я . выражение А. ценность  +  сам . выражениеБ . ценить def  получить ( self ,  семя ):  self . выражение А. получить ( семя )  себя . выражениеБ . вывести ( семя )класс  Multiply ( Expression ):  def  __init__ ( self ,  выражениеA ,  выражениеB ):  self . выражениеA  =  выражениеA  self . выражениеB  =  выражениеB  self . значение  =  Нет def  оценить ( self ):  self . выражение А. оценить ()  себя . выражениеБ . оценить ()  себя . значение  =  я . выражение А. значение  *  сам . выражениеБ . ценить def  получить ( self ,  семя ):  self . выражение А. получить ( self.выражениеB.значение * семя ) self . _ _ _ _  выражениеБ . получить ( self . выражениеA . значение * семя )    # Пример: нахождение частей z = x * (x + y) + y * y в (x, y) = (2, 3) x  =  Variable ( 2 ) y  =  Variable ( 3 ) z  =  x  *  ( x  +  y )  +  y  *  y z . Assessment () print ( "z=" ,  z.value ) # Вывод: z = 19 z . получить ( 1 ) print ( "∂z/∂x =" , x . частичное ) # Вывод: ∂z/∂x = 7 print ( "∂z/∂y =" , y . частичное ) # Вывод: ∂z/ ∂у = 8     

С++

#include <iostream> struct Expression { значение с плавающей запятой ; виртуальная недействительная оценка () = 0 ; виртуальная пустота получения ( floatseed ) = 0 ; _ }; struct Variable : public Expression { float частичное ; Переменная ( float _value ) { value = _value ; частичный = 0 ; } void Assessment () {} void Derivate ( seed с плавающей запятой ) { частичное += семя ; } }; struct Plus : public Expression { Expression * a , * b ; Плюс ( Выражение * a , Выражение * b ) : a ( a ), b ( b ) {} void Assessment () { a -> Assessment (); б -> оценить (); значение = a -> значение + b -> значение ; } void Derivate ( floatseed ) { a -> Derivate ( seed ) ; б -> получить ( семя ); } }; struct Multiply : public Expression { Expression * a , * b ; Умножить ( Выражение * a , Выражение * b ) : a ( a ), b ( b ) {} void Assessment () { a -> Assessment ();                                                                                              б -> оценить (); значение = a -> значение * b -> значение ; } void Derivate ( floatseed ) { a - > Derivate ( b -> value * seed ); b -> получить ( a -> значение * семя ); } }; int main () { // Пример: нахождение частей z = x * (x + y) + y * y at (x, y) = (2, 3) Переменная x ( 2 ), y ( 3 ); Плюс p1 ( & x , & y ); Умножьте m1 ( & x , & p1 ); Умножьте m2 ( & y , & y ); Плюс z ( & m1 , & m2 ); з . оценивать (); std :: cout << "z = " << z . значение << std :: endl ; // Вывод: z = 19 z . вывести ( 1 ); std :: cout << "∂z/∂x = " << x . частичный << ", " << "∂z/∂y = " << y . частичный << std :: endl ; // Вывод: ∂z/∂x = 7, ∂z/∂y = 8 return 0 ; }                                                              

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

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

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

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

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

$${\displaystyle {\begin{aligned}(x+x'\varepsilon )+(y+y'\varepsilon )&=x+y+(x'+y')\varepsilon \\(x+x'\varepsilon )-(y+y'\varepsilon )&=x-y+(x'-y')\varepsilon \\(x+x'\varepsilon )\cdot (y+y'\varepsilon )&=xy+xy'\varepsilon +yx'\varepsilon +x'y'\varepsilon ^{2}=xy+(xy'+yx')\varepsilon \\(x+x'\varepsilon )/(y+y'\varepsilon )&=(x/y+x'\varepsilon /y)/(1+y'\varepsilon /y)=(x/y+x'\varepsilon /y)\cdot (1-y'\varepsilon /y)=x/y+(x'/y-xy'/y^{2})\varepsilon \end{aligned}}}$$

${\displaystyle (1+y'\varepsilon /y)\cdot (1-y'\varepsilon /y)=1}$

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

$${\displaystyle {\begin{aligned}P(x+x'\varepsilon )&=p_{0}+p_{1}(x+x'\varepsilon )+\cdots +p_{n}(x+x'\varepsilon )^{n}\\&=p_{0}+p_{1}x+\cdots +p_{n}x^{n}+p_{1}x'\varepsilon +2p_{2}xx'\varepsilon +\cdots +np_{n}x^{n-1}x'\varepsilon \\&=P(x)+P^{(1)}(x)x'\varepsilon \end{aligned}}}$$

начальным числом ${\displaystyle P^{(1)}}$ ${\displaystyle P}$ ${\displaystyle x'}$

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

$${\displaystyle {\begin{aligned}\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 u-v,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},u'ku^{k-1}\right\rangle \quad (u\neq 0)\\\left|\left\langle u,u'\right\rangle \right|&=\left\langle \left|u\right|,u'\operatorname {sign} u\right\rangle \quad (u\neq 0)\end{aligned}}}$$

${\displaystyle g}$

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

${\displaystyle g_{u}}$ ${\displaystyle g_{v}}$ ${\displaystyle g}$

Когда базовая двоичная арифметическая операция применяется к смешанным аргументам — паре и действительному числу — действительное число сначала увеличивается до . Производная функции в точке теперь находится путем вычисления с использованием приведенной выше арифметики, что дает результат. ${\displaystyle \langle u,u'\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 }$

Выполнение

Ниже приведен пример реализации, основанной на подходе двойного числа.

Псевдокод

Двойной плюс (Двойной А, Двойной Б) { возвращаться { реальнаяЧасть(A) + реальнаяЧасть(B), бесконечно малаяЧасть(A) + бесконечно малаяЧасть(B) };}Двойной минус (Двойной А, Двойной Б) { возвращаться { реальнаяЧасть(А) - реальнаяЧасть(В), бесконечно малая часть (A) - бесконечно малая часть (B) };}Двойное умножение (Двойной A, Двойной B) { возвращаться { реальнаяЧасть(A) * реальнаяЧасть(B), реальнаяЧасть(B) * бесконечно малаяЧасть(A) + реальнаяЧасть(A) * бесконечно малаяЧасть(B) };}Х = {х, 0};Y = {у, 0};Эпсилон = {0, 1};xPartial = бесконечно малаяЧастьOf(f(X + Эпсилон, Y));yPartial = бесконечно малаяЧастьOf(f(X, Y + Эпсилон));

Питон

class  Dual :  def  __init__ ( self ,  RealPart ,  InfinitsimalPart = 0 ):  self . RealPart  =  RealPart  self . бесконечно малая часть  =  бесконечно малая часть def  __add__ ( self ,  other )  : return  Dual (  self.realPart + other.realPart , self.infinitesimalPart + other.infinitesimalPart ) _  _  _ _ _ _ _     def  __mul__ ( self ,  other )  : return  Dual (  self.realPart * other.realPart , other.realPart * self.infinitesimalPart + self.realPart *  other.infinitesimalPart  ) _ _ _ _ _ _ _ _ _ _ _        # Пример: нахождение частей z = x * (x + y) + y * y at (x, y) = (2, 3) def  f ( x ,  y ):  return  x  *  ( x  +  y )  +  y  *  y x  =  Двойной ( 2 ) y  =  Двойной ( 3 ) эпсилон  =  Двойной ( 0 ,  1 ) a  =  f ( x  +  эпсилон ,  y ) b  =  f ( x ,  y  +  эпсилон ) print ( "∂z/∂x =" ,  a . InfinitesimalPart )  # Вывод: ∂z/∂x = 7 print ( "∂z/∂y =" ,  b . InfinitesimalPart )  # Вывод: ∂z/∂y = 8

С++

#include <iostream> struct Dual { float RealPart , InfinitesimalPart ; Dual ( float realPart , float InfinitesimalPart = 0 ) : RealPart ( realPart ), InfinitesimalPart ( InfinitesimalPart ) {} Двойной оператор + ( Dual Other ) { return Dual ( realPart + Other . RealPart , InfinitesimalPart + Other . InfinitsimalPart ); } Двойной оператор * ( Двойной другой ) { return Dual ( realPart * Other . RealPart , Other . RealPart * InfinitesimalPart + RealPart * Other . InfinitesimalPart ); } }; // Пример: нахождение частей z = x * (x + y) + y * y в (x, y) = (2, 3) Dual f ( Dual x , Dual y ) { return x * ( x + y ) + y * y ; } int main () { Dual x = Dual ( 2 ); Двойной у = Двойной ( 3 ); Двойной эпсилон = Двойной ( 0 , 1 ); Двойной a = f ( x + эпсилон , y ); Двойной b = f ( x , y + эпсилон ); std :: cout << "∂z/∂x = " << a . бесконечно малая часть << ", " << "∂z/∂y = " << b . бесконечно малая часть <<                                                                                                        станд :: конец ; // Вывод: ∂z/∂x = 7, ∂z/∂y = 8 return 0 ; }   

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

Многомерные функции можно обрабатывать с той же эффективностью и механизмами, что и одномерные функции, используя оператор производной по направлению. То есть, если достаточно вычислить , производная от at в направлении может быть рассчитана с использованием той же арифметики, что и выше. Если все элементы желательны, то требуются оценки функций. Обратите внимание, что во многих приложениях оптимизации производная по направлению действительно достаточна. ${\displaystyle y'=\nabla f(x)\cdot x'}$ ${\displaystyle y'\in \mathbb {R} ^{m}}$ ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} ^{m}}$ ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle x'\in \mathbb {R} ^{n}}$ ${\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 более сложна, а система сборки более сложна.

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

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

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

Перегрузка операторов и преобразование исходного кода

Перегруженные операторы можно использовать для извлечения графика оценки с последующим автоматическим созданием AD-версии основной функции во время выполнения. В отличие от классического ОО ААД, такая AD-функция не меняется от одной итерации к следующей. Следовательно, для каждой выборки Xi возникают какие-либо накладные расходы во время выполнения объектно-ориентированной интерпретации или интерпретации ленты.

Поскольку AD-функция генерируется во время выполнения, ее можно оптимизировать, чтобы учесть текущее состояние программы и предварительно вычислить определенные значения. Кроме того, его можно сгенерировать таким образом, чтобы последовательно использовать встроенную векторизацию ЦП для обработки 4(8)-двойных фрагментов пользовательских данных (ускорение AVX2\AVX512 x4-x8). С учетом многопоточности такой подход может привести к окончательному ускорению порядка 8 × #Cores по сравнению с традиционными инструментами AAD. Эталонная реализация доступна на GitHub. ^[11]

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

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

Примечания

1. С точки зрения весовых матриц сопряженным является транспонирование . Сложение – это ковектор , поскольку и разветвление – это вектор, поскольку ${\displaystyle [1\cdots 1]}$ ${\displaystyle [1\cdots 1]\left[{\begin{smallmatrix}x_{1}\\\vdots \\x_{n}\end{smallmatrix}}\right]=x_{1}+\cdots +x_{n},}$ ${\displaystyle \left[{\begin{smallmatrix}1\\\vdots \\1\end{smallmatrix}}\right],}$ ${\displaystyle \left[{\begin{smallmatrix}1\\\vdots \\1\end{smallmatrix}}\right][x]=\left[{\begin{smallmatrix}x\\\vdots \\x\end{smallmatrix}}\right].}$

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

1. Нейдингер, Ричард Д. (2010). «Введение в автоматическое дифференцирование и объектно-ориентированное программирование MATLAB» (PDF) . Обзор СИАМ . 52 (3): 545–563. CiteSeerX  10.1.1.362.6580 . дои : 10.1137/080743627. S2CID  17134969.
2. Байдин, Атилим Гюнес; Перлмуттер, Барак; Радуль Алексей Андреевич; Сискинд, Джеффри (2018). «Автоматическая дифференциация в машинном обучении: опрос». Журнал исследований машинного обучения . 18 : 1–43.
3. RE Wengert (1964). «Простая автоматическая программа оценки производных». Комм. АКМ . 7 (8): 463–464. дои : 10.1145/355586.364791 . S2CID  24039274.
4. Гриванк, Андреас (2012). «Кто изобрел обратный способ дифференциации?» (PDF) . Истории оптимизации, Documenta Matematica . Дополнительный том ISMP: 389–400. дои : 10.4171/dms/6/38. ISBN 978-3-936609-58-5.
5. Линнаинмаа, Сеппо (1976). «Разложение Тейлора накопленной ошибки округления». БИТ Численная математика . 16 (2): 146–160. дои : 10.1007/BF01931367. S2CID  122357351.
6. Максимилиан Э. Шюле, Максимилиан Спрингер, Альфонс Кемпер , Томас Нойманн (2022). «Оптимизация кода LLVM для автоматического дифференцирования». Материалы шестого семинара по управлению данными для сквозного машинного обучения . стр. 1–4. дои : 10.1145/3533028.3533302. ISBN 9781450393751. S2CID  248853034.{{cite book}}: CS1 maint: multiple names: authors list (link)
7. Бартоломью-Биггс, Майкл; Браун, Стивен; Кристиансон, Брюс; Диксон, Лоуренс (2000). «Автоматическое дифференцирование алгоритмов». Журнал вычислительной и прикладной математики . 124 (1–2): 171–190. Бибкод : 2000JCoAM.124..171B. дои : 10.1016/S0377-0427(00)00422-2. hdl : 2299/3010 .
8. Максимилиан Э. Шюле, Харальд Ланг, Максимилиан Шпрингер, Альфонс Кемпер , Томас Нойманн , Стефан Гюннеманн (2021). «Машинное обучение в базе данных с использованием SQL на графических процессорах». 33-я Международная конференция по управлению научными и статистическими базами данных . стр. 25–36. дои : 10.1145/3468791.3468840. ISBN 9781450384131. S2CID  235386969.{{cite book}}: CS1 maint: multiple names: authors list (link)
9. Максимилиан Э. Шюле, Харальд Ланг, Максимилиан Шпрингер, Альфонс Кемпер , Томас Нойманн , Стефан Гюннеманн (2022). «Рекурсивный SQL и поддержка графического процессора для машинного обучения в базе данных». Распределенные и параллельные базы данных . 40 (2–3): 205–259. дои : 10.1007/s10619-022-07417-7 . S2CID  250412395.{{cite journal}}: CS1 maint: multiple names: authors list (link)
10. Науманн, Уве (апрель 2008 г.). «Оптимальное накопление якобиана NP-полное». Математическое программирование . 112 (2): 427–441. CiteSeerX 10.1.1.320.5665 . дои : 10.1007/s10107-006-0042-z. S2CID  30219572. 
11. "Библиотека прототипов AADC" . 22 июня 2022 г. — через GitHub.

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

• Ралл, Луи Б. (1981). Автоматическая дифференциация: методы и приложения . Конспекты лекций по информатике. Том. 120. Спрингер . ISBN 978-3-540-10861-0.
• Гриванк, Андреас; Вальтер, Андреа (2008). Оценка производных: принципы и методы алгоритмического дифференцирования. Другие названия по прикладной математике. Том. 105 (2-е изд.). СИАМ . дои : 10.1137/1.9780898717761. ISBN 978-0-89871-659-7.
• Найдингер, Ричард (2010). «Введение в автоматическое дифференцирование и объектно-ориентированное программирование MATLAB» (PDF) . Обзор СИАМ . 52 (3): 545–563. CiteSeerX  10.1.1.362.6580 . дои : 10.1137/080743627. S2CID  17134969 . Проверено 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. Архивировано 3 августа 2016 г. на Wayback Machine.
• finmath-lib стохастическое автоматическое дифференцирование, Автоматическое дифференцирование для случайных величин (Java-реализация стохастического автоматического дифференцирования).
• Сопряженное алгоритмическое дифференцирование: калибровка и теорема о неявной функции
• Статья и реализация автоматического дифференцирования на основе шаблонов C++
• Касательные отлаживаемые производные от источника к источнику
• Точные греки первого и второго порядка путем алгоритмического дифференцирования
• Сопряженное алгоритмическое дифференцирование приложения с ускорением на графическом процессоре
• Сопряженные методы в вычислительных финансах. Программная поддержка алгоритмического дифференцирования.
• Увеличение скорости расчета цен xVA более чем в тысячу раз с помощью масштабируемых процессоров Intel Xeon