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

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

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

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

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

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

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

Основою AD є розклад диференціалів використовуючи ланцюгове правило. Застосувавши його до складеної функції Шаблон:Math отримаємо:

$\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^{\prime }\epsilon )$, де $a^{\prime }$ є дійсним числом, а $\epsilon$ є уявною одиницею, такою, що ${\epsilon }^2=0$. Така конструкція називається дуальним числом.

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

$(a+a^{\prime }\epsilon )+(b+b^{\prime }\epsilon )=(a+b)+(a^{\prime }+b^{\prime })\epsilon =(a+b)+(a+b{)}^{\prime }\epsilon$

$(a+a^{\prime }\epsilon )*(b+b^{\prime }\epsilon )=ab+(a{b}^{\prime }+b{a}^{\prime })\epsilon =ab+(ab{)}^{\prime }\epsilon$

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

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

$g(⟨a,a^{\prime }⟩,⟨b,b^{\prime }⟩)=⟨g(a,b),g_a(a,b)a^{\prime }+g_b(a,b)b^{\prime }⟩$

де $g_a$ та $g_b$ є похідними $g$ по першому та другому аргументу відповідно.

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

$\begin{array}{cc}⟨a,a^{\prime }⟩+⟨b,b^{\prime }⟩& =⟨a+b,a^{\prime }+b^{\prime }⟩\\ ⟨a,a^{\prime }⟩-⟨b,b^{\prime }⟩& =⟨a-b,a^{\prime }-b^{\prime }⟩\\ ⟨a,a^{\prime }⟩*⟨b,b^{\prime }⟩& =⟨ab,a^{\prime }b+a{b}^{\prime }⟩\\ ⟨a,a^{\prime }⟩/⟨b,b^{\prime }⟩& =⟨\frac{a}{b},\frac{a^{\prime }b-a{b}^{\prime }}{b^2}⟩(b\ne 0)\\ \sin ⟨a,a^{\prime }⟩& =⟨\sin (a),a^{\prime }\cos (a)⟩\\ \cos ⟨a,a^{\prime }⟩& =⟨\cos (a),-a^{\prime }\sin (a)⟩\\ \exp ⟨a,a^{\prime }⟩& =⟨\exp a,a^{\prime }\exp a⟩\\ \log ⟨a,a^{\prime }⟩& =⟨\log (a),a^{\prime }/a⟩(a>0)\\ {⟨a,a^{\prime }⟩}^k& =⟨a^k,k{a}^{k-1}{a}^{\prime }⟩(a\ne 0)\\ \left|⟨a,a^{\prime }⟩\right|& =⟨\left|a\right|,a^{\prime }\text{sign}a⟩(a\ne 0)\end{array}$

Реалізація

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

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

Джерела

• www.autodiff.org An "entry site to everything you want to know about automatic differentiation" Шаблон:Webarchive