在數學 和計算機代數 中,自動微分 有時稱作演算式微分 ,是一種可以藉由電腦程式計算一個函數導數 的方法。兩種傳統做微分的方法為:
對一個函數的表示式做符號上的微分,並且計算其在某一點上的值。
使用差分 。
使用符號微分最主要的缺點是速度慢及將電腦程式轉換成表示式的困難。此外,很多函數在要計算更高階微分時會變得複雜。
使用差分的兩個重要的缺點是捨棄誤差 及數值化 過程和相消誤差。此兩者傳統方法在計算更高階微分時,都有複雜度及誤差增加的問題。自動微分則解決上述的問題。
自動微分使用這個事實:任何實作一個向量函數 y =F(x )的電腦程式,一般而言,可以被分解成由基本指定運算所成的序列,而其中每一個都可以藉由查表而輕易地微分。這些計算某一特定項的 "基本偏微分" 是依照微積分中的複合函數求導法則 來合併成某個 F 的微分資訊(如梯度 、切線 、雅可比矩陣 等)。這個過程會產生確實(數值上準確)的導數。因為只在最基礎的層面做符號轉換,自動微分避免了複雜的符號運算的問題。
複合函數求導法則,前向和反向積累
前向式積累自動微分的由來與二元數
前向式積累自動微分可藉由擴充實數 中的代數 並得到一個新的算術 系統來達成。
每一個數都會新增另一數,用來表示一函數在這數上導數的數。
而每一個算術運算都被擴充於此新的代數。
這個擴充後的代數就是二元數 的代數。
將每一個數
x
{\displaystyle \,x}
替換成數
x
+
x
′
ε
{\displaystyle x+x'\varepsilon }
,其中
x
′
{\displaystyle x'}
是一個實數,但
ε
{\displaystyle \varepsilon }
則只是一個據有
ε
2
=
0
{\displaystyle \varepsilon ^{2}=0}
這個特性的符號。
使用這特性,我們可以有運算
(
x
+
x
′
ε
)
+
(
y
+
y
′
ε
)
=
x
+
y
+
(
x
′
+
y
′
)
ε
{\displaystyle (x+x'\varepsilon )+(y+y'\varepsilon )=x+y+(x'+y')\varepsilon }
(
x
+
x
′
ε
)
⋅
(
y
+
y
′
ε
)
=
x
y
+
x
y
′
ε
+
y
x
′
ε
+
x
′
y
′
ε
2
=
x
y
+
(
x
y
′
+
y
x
′
)
ε
{\displaystyle (x+x'\varepsilon )\cdot (y+y'\varepsilon )=xy+xy'\varepsilon +yx'\varepsilon +x'y'\varepsilon ^{2}=xy+(xy'+yx')\varepsilon }
減法和除法則類似。
現在,我們可以計算多項式 。
如果
P
(
x
)
=
p
0
+
p
1
x
+
p
2
x
2
+
⋯
+
p
n
x
n
{\displaystyle P(x)=p_{0}+p_{1}x+p_{2}x^{2}+\cdots +p_{n}x^{n}}
,則
P
(
x
+
x
′
ε
)
{\displaystyle P(x+x'\varepsilon )}
=
{\displaystyle =\,}
p
0
+
p
1
(
x
+
x
′
ε
)
+
⋯
+
p
n
(
x
+
x
′
ε
)
n
{\displaystyle p_{0}+p_{1}(x+x'\varepsilon )+\cdots +p_{n}(x+x'\varepsilon )^{n}}
=
{\displaystyle =\,}
p
0
+
p
1
x
+
⋯
+
p
n
x
n
{\displaystyle p_{0}+p_{1}x+\cdots +p_{n}x^{n}}
+
p
1
x
′
ε
+
2
p
2
x
x
′
ε
+
⋯
+
n
p
n
x
n
−
1
x
′
ε
{\displaystyle \,{}+p_{1}x'\varepsilon +2p_{2}xx'\varepsilon +\cdots +np_{n}x^{n-1}x'\varepsilon }
=
{\displaystyle =\,}
P
(
x
)
+
P
(
1
)
(
x
)
x
′
ε
{\displaystyle P(x)+P^{(1)}(x)x'\varepsilon }
其中
P
(
1
)
{\displaystyle P^{(1)}}
表示
P
{\displaystyle P}
對第一個參數的導數。
而
x
′
{\displaystyle x'}
則稱作「種子」,可以任意選擇。
新的算術是由有序對 、寫成
⟨
x
,
x
′
⟩
{\displaystyle \langle x,x'\rangle }
及對第一項的運算和對第二項的第一階微分運算所組成。
將上述結果應用於多項式的解析函數 上,
我們可以得到一系列關於基本算術和一些標準函數的新算術:
⟨
u
,
u
′
⟩
+
⟨
v
,
v
′
⟩
=
⟨
u
+
v
,
u
′
+
v
′
⟩
{\displaystyle \langle u,u'\rangle +\langle v,v'\rangle =\langle u+v,u'+v'\rangle }
⟨
u
,
u
′
⟩
−
⟨
v
,
v
′
⟩
=
⟨
u
−
v
,
u
′
−
v
′
⟩
{\displaystyle \langle u,u'\rangle -\langle v,v'\rangle =\langle u-v,u'-v'\rangle }
⟨
u
,
u
′
⟩
∗
⟨
v
,
v
′
⟩
=
⟨
u
v
,
u
′
v
+
u
v
′
⟩
{\displaystyle \langle u,u'\rangle *\langle v,v'\rangle =\langle uv,u'v+uv'\rangle }
⟨
u
,
u
′
⟩
/
⟨
v
,
v
′
⟩
=
⟨
u
v
,
u
′
v
−
u
v
′
v
2
⟩
(
v
≠
0
)
{\displaystyle \langle u,u'\rangle /\langle v,v'\rangle =\left\langle {\frac {u}{v}},{\frac {u'v-uv'}{v^{2}}}\right\rangle \quad (v\neq 0)}
sin
⟨
u
,
u
′
⟩
=
⟨
sin
(
u
)
,
u
′
cos
(
u
)
⟩
{\displaystyle \sin \langle u,u'\rangle =\langle \sin(u),u'\cos(u)\rangle }
cos
⟨
u
,
u
′
⟩
=
⟨
cos
(
u
)
,
−
u
′
sin
(
u
)
⟩
{\displaystyle \cos \langle u,u'\rangle =\langle \cos(u),-u'\sin(u)\rangle }
exp
⟨
u
,
u
′
⟩
=
⟨
exp
u
,
u
′
exp
u
⟩
{\displaystyle \exp \langle u,u'\rangle =\langle \exp u,u'\exp u\rangle }
log
⟨
u
,
u
′
⟩
=
⟨
log
(
u
)
,
u
′
/
u
⟩
(
u
>
0
)
{\displaystyle \log \langle u,u'\rangle =\langle \log(u),u'/u\rangle \quad (u>0)}
⟨
u
,
u
′
⟩
k
=
⟨
u
k
,
k
u
k
−
1
u
′
⟩
(
u
≠
0
)
{\displaystyle \langle u,u'\rangle ^{k}=\langle u^{k},ku^{k-1}u'\rangle \quad (u\neq 0)}
|
⟨
u
,
u
′
⟩
|
=
⟨
|
u
|
,
u
′
sign
u
⟩
(
u
≠
0
)
{\displaystyle \left|\langle u,u'\rangle \right|=\langle \left|u\right|,u'{\mbox{sign}}u\rangle \quad (u\neq 0)}
並且,一般而言,對於一個函數
g
{\displaystyle g}
,我們會有
g
(
⟨
u
,
u
′
⟩
,
⟨
v
,
v
′
⟩
)
=
⟨
g
(
u
,
v
)
,
g
(
1
)
(
u
,
v
)
u
′
+
g
(
2
)
(
u
,
v
)
v
′
⟩
{\displaystyle g(\langle u,u'\rangle ,\langle v,v'\rangle )=\langle g(u,v),g^{(1)}(u,v)u'+g^{(2)}(u,v)v'\rangle }
其中
g
(
1
)
{\displaystyle g^{(1)}}
和
g
(
2
)
{\displaystyle g^{(2)}}
分別是
g
{\displaystyle g}
對其第一項和第二項的導數。
對一個二元算術運算作用於混合的參數時(數對
⟨
u
,
u
′
⟩
{\displaystyle \langle u,u'\rangle }
和實數
c
{\displaystyle c}
),
實數會先被轉成
⟨
c
,
0
⟩
{\displaystyle \langle c,0\rangle }
。
函數
f
:
R
→
R
{\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} }
在
x
0
{\displaystyle x_{0}}
上的導數
則為以上述算術計算
f
(
⟨
x
0
,
1
⟩
)
{\displaystyle f(\langle x_{0},1\rangle )}
,其結果為
⟨
f
(
x
0
)
,
f
′
(
x
0
)
⟩
{\displaystyle \langle f(x_{0}),f'(x_{0})\rangle }
。
向量參數和函數
藉由採取方向導數 的運算,
多變數函數也可以同單變數函數的效率和機制來處理。
亦即,函數
f
:
R
n
→
R
m
{\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}}
在
x
∈
R
n
{\displaystyle x\in \mathbb {R} ^{n}}
這點,
和
x
′
∈
R
n
{\displaystyle x'\in \mathbb {R} ^{n}}
這個方向上的方向導數
y
′
∈
R
m
{\displaystyle y'\in \mathbb {R} ^{m}}
,
可以使用上述相同的算術來計算
(
⟨
y
1
,
y
1
′
⟩
,
…
,
⟨
y
m
,
y
m
′
⟩
)
=
f
(
⟨
x
1
,
x
1
′
⟩
,
…
,
⟨
x
n
,
x
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 )}
而求得。
更高階微分
以上的算術可以被一般化,以用於二階及三階導數。
然而,此算術的規則將會迅速變得複雜。
其複雜度將與最高階導數階數成平化。
取而代之的是使用限縮泰勒級數 。
這是可行的,因為函數的泰勒級數中的通項為己知系數和函數導數的乘積。
使用自動微分來計算黑塞矩陣 在某些最佳化已被證明是可行的。
實作
前向式積累是由對程式的非標準化轉譯程序來實作。
即將實數替換成二元數,常數則換成有第二項為零系數的二元數。
而數值上基本運算則被換成二元數的運算。
非標準化轉譯程序一般使用兩者策略之一:程式碼轉換 和運算符重載 。
程式碼轉換
Figure 4: Example of how source code transformation could work
一個函數的程式碼會被自動產生的程式碼所替換,
新生成用來計算導數的程式碼則會插入原程式碼中。
程式碼轉換可實作在所有的程式語言上,且它對編譯器而言,是容易最佳化的。
然而,實作自動微分的工具則是比較困難的。
例子:
ADIC[ 1] (C/C++, 前向積累)
ADIFOR[ 2] (Fortran77)
OpenAD[ 3] (Fortran77, Fortran95, C/C++)
TAPENADE[ 4] (Fortran77, Fortran95)
運算符重載
Figure 5: Example of how operator overloading could work
如果所使用的程式語言支持,運算符重載 是個可行的方法。
實數的物件跟基本數學運算必須重載以滿足上述 augmented 算術。
這不須要改變要被微分的函數的程式碼。
運算符重載對前向積累是容易實作的,並且可能對反向積累亦如此。
然而,與前向積累相比,現有的編譯器在最佳化程式碼方面則是較為落後。
例子:
ADC Version 4.0[ 5] (C/C++)
ADF Version 4.0[ 6] (Fortran 77, Fortran 95)
ADOL-C[ 7] (C/C++)
FADBAD++[ 8] (C/C++)
CppAD[ 9] (C/C++)
MAD[ 10] (Matlab)
Sacado (Trilinos[ 11] 的一部分) (C++, forward/reverse)
參考文獻
Rall, Louis B. Automatic Differentiation: Techniques and Applications. Lecture Notes in Computer Science 120 . Springer . 1981. ISBN 978-3-540-10861-0 .
Griewank, Andreas. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. Frontiers in Applied Mathematics 19 . SIAM . 2000. ISBN 0-89871-451-6 .
外部連結