ニューラルネットワーク (4) 誤差逆伝播法 (1) - らんだむな記憶では、重みを $\Theta$ とし、誤差関数を $J(\Theta)$ としたが、今回は重みを $w = (w_{ij}^{(\ell)})_{1 \leq \ell \leq L, 1 \leq i \leq I, 1 \leq j \leq J}$ とし($w_{ij}^{(\ell)}$ は $\ell$ 番目の層の $i$ 番目のニューロンから $\ell+1$ 番目の層の $j$ 番目のニューロンへの重み)、誤差関数を $E(w)$ と書くことにする。
勾配法を使うには $\mathrm{grad}(E) = \left( \frac{\del E}{\del w_{11}^{(1)}}, \cdots, \frac{\del E}{\del w_{ij}^{(\ell)}}, \cdots \right)$ を計算することになる。
ここで数値微分を行う場合、 $w = w_0$ での勾配の計算のためには、微小な数 $h_{ij}^{(\ell)}$ を用いて、中心差分 $\frac{E(w_0 + h_{ij}^{(\ell)}) - E(w_0 - h_{ij}^{(\ell)})}{2 h_{ij}^{(\ell)}}$ によって、 $\frac{\del E}{\del w_{ij}^{(\ell)}}\Big|_{w=w_0}$ を近似することになる。
この計算のオーダーを $w = (w_{11}^{(1)}, \cdots, w_{ij}^{(\ell)}, \cdots)$ について見よう。各 $\ell,\ i,\ j$ に対して $\frac{E(w_0 + h_{ij}^{(\ell)}) - E(w_0 - h_{ij}^{(\ell)})}{2 h_{ij}^{(\ell)}}$ における全 $w_{ij}^{(\ell)}$ の計算が入るので重みが関与する計算回数は $LIJ$ 回である。そして、この $\ell,\ i,\ j$ を全パターン回して勾配を計算するので、勾配の計算において重みが関与する計算回数は $\times LIJ$ 倍の $(LIJ)^2$ 回となる。
$W := LIJ$ つまり、重みの個数とすると、数値微分による計算のオーダーは $O(W^2)$ となる。このことが、PRML *1のpp.246-247「5.3.3 Efficiency of backpropagation」にかけてかいてある。「深層学習」*2のp.42でも計算量が多くなるといった記述があるが、本質的にはこのようなことを指していると思われる。(PRMLにあるように結局誤差逆伝播法でも計算のオーダーは $O(W)$ なので少ないかと言われると・・・ではあるのだが、数値計算で勾配を計算すると相対的にオーダーが大きいということを言っているのだと思う。しかもこの計算オーダーを叩き出すためには最初に順伝播で出力を求める際に、各層を通る入力テンソルの値をキャッシュしておかないとならない・・・)
