Автоматичне диференціювання

Автоматичне диференціювання (англ. automatic differentiation, AD) в математиці та символьних обчисленнях — спосіб обчислити похідну для функції, яка задана алгоритмом.

AD використовує той факт, що довільна функція в комп'ютерній програмі все одно буде обчислюватись за допомогою арифметичних дій (+, -, *, /) та елементарних функцій стандартних бібліотек (exp, log, sin, cos, і т.д.). Застосовуючи ланцюгове правило, похідна довільного порядку може бути обчислена з заданою точністю, за кількість операцій, що пропорційна кількості операцій для обчислення самої функції.

Автоматичне диференціювання не є:

• ні символьним диференціюванням,
• ні чисельним диференціюванням.

Символьне диференціювання не завжди ефективне, оскільки деякі функції важко представити єдиним виразом, а чисельне диференціювання призводить до внесення похибок округлення та дискретизації. Обидва ці методи не є зручними для обчислення похідних високих порядків, оскільки похибка і складність значно зростає. Також обидва ці методи є повільними при обчисленні часткових похідних для функції багатьох аргументів. Автоматичне диференціювання вирішує всі ці проблеми, але вводить додаткову програмну залежність.

Ланцюгове правило вперед і назад

Основою AD є розклад диференціалів використовуючи ланцюгове правило. Застосувавши його до складеної функції y = g(h(x)) = g(w) отримаємо:

${\frac {dy}{dx}}={\frac {dy}{dw}}{\frac {dw}{dx}}$

Рух вперед

Зафіксувавши незалежну змінну, і застосовуючи ланцюгове правило до проміжної функції, отримаємо:

${\frac {\partial y}{\partial x}}={\frac {\partial y}{\partial w_{1}}}{\frac {\partial w_{1}}{\partial x}}={\frac {\partial y}{\partial w_{1}}}\left({\frac {\partial w_{1}}{\partial w_{2}}}{\frac {\partial w_{2}}{\partial x}}\right)={\frac {\partial y}{\partial w_{1}}}\left({\frac {\partial w_{1}}{\partial w_{2}}}\left({\frac {\partial w_{2}}{\partial w_{3}}}{\frac {\partial w_{3}}{\partial x}}\right)\right)=\cdots$

Рух назад

Застосовуючи ланцюгове правило до початкової функції по нововведеній змінній отримаємо:

${\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$

Рух вперед і назад є крайніми випадками застосування ланцюгового правила. Задача ж обчислення повного Якобіана з мінімальною кількістю операцій є NP-повною.

Використання дуальних чисел

Застосовуючи рух вперед, помістимо поряд із кожним числом, що використовується для обчислення функії, ще одне, яке міститиме значення похідної. Буквально, замінимо дійсне число $\,a$ на конструкцію $(a+a'\varepsilon )$, де $a'$ є дійсним числом, а $\varepsilon$ є уявною одиницею, такою, що $\varepsilon ^{2}=0$. Така конструкція називається дуальним числом.

Тоді для арифметичних операцій отримаємо:

$(a+a'\varepsilon )+(b+b'\varepsilon )=(a+b)+(a'+b')\varepsilon =(a+b)+(a+b)'\varepsilon$

$(a+a'\varepsilon )*(b+b'\varepsilon )=ab+(ab'+ba')\varepsilon =ab+(ab)'\varepsilon$

Тобто, уявна частина знову буде містити значення похідної від виразу в дійсній частині.

Запишемо дуальні числа без уявної одиниці у вигляді впорядкованої пари $\langle a,a'\rangle$ і використаємо ланцюгове правило для функції двох аргументів $g$:

$g(\langle a,a'\rangle ,\langle b,b'\rangle )=\langle g(a,b),\;\;g_{a}(a,b)a'+g_{b}(a,b)b'\rangle$

де $g_{a}$ та $g_{b}$ є похідними $g$ по першому та другому аргументу відповідно.

Підставивши замість $g$ арифметичні операції та елементарні функції, отримаємо повний набір операцій над дуальними числами:

${\begin{aligned}\left\langle a,a'\right\rangle +\left\langle b,b'\right\rangle &=\left\langle a+b,a'+b'\right\rangle \\\left\langle a,a'\right\rangle -\left\langle b,b'\right\rangle &=\left\langle a-b,a'-b'\right\rangle \\\left\langle a,a'\right\rangle *\left\langle b,b'\right\rangle &=\left\langle ab,a'b+ab'\right\rangle \\\left\langle a,a'\right\rangle /\left\langle b,b'\right\rangle &=\left\langle {\frac {a}{b}},{\frac {a'b-ab'}{b^{2}}}\right\rangle \quad (b\neq 0)\\\sin \left\langle a,a'\right\rangle &=\left\langle \sin(a),a'\cos(a)\right\rangle \\\cos \left\langle a,a'\right\rangle &=\left\langle \cos(a),-a'\sin(a)\right\rangle \\\exp \left\langle a,a'\right\rangle &=\left\langle \exp a,a'\exp a\right\rangle \\\log \left\langle a,a'\right\rangle &=\left\langle \log(a),a'/a\right\rangle \quad (a>0)\\\left\langle a,a'\right\rangle ^{k}&=\left\langle a^{k},ka^{k-1}a'\right\rangle \quad (a\neq 0)\\\left|\left\langle a,a'\right\rangle \right|&=\left\langle \left|a\right|,a'{\mbox{sign}}a\right\rangle \quad (a\neq 0)\end{aligned}}$

Реалізація

Реалізація автоматичного диференціювання можлива через:

• автоматичне перетворення вихідного коду,
• перевантаження функцій та операторів.

Джерела

• www.autodiff.org An "entry site to everything you want to know about automatic differentiation" [Архівовано 14 квітня 2021 у Wayback Machine.]