BPTT

BPTTとは何か

BPTTは Back-Propagation Through Time の略で、「時間をさかのぼる誤差逆伝播」という意味の名前です。リカレントニューラルネットワーク(RNN)の重みを学習するときに、勾配を計算する方法を指します。勾配とは、損失を小さくするために各重みをどちらへどれだけ動かせばよいかを表す値です。

RNNは、系列を1要素ずつ読み込み、前の時刻に計算した隠れ状態を次の時刻の計算に渡すネットワークです。系列とは、文章の単語の並びや時刻ごとの測定値の並びのように、順番に意味があるデータのことです。

イアン・グッドフェロー(Ian Goodfellow)、ヨシュア・ベンジオ(Yoshua Bengio)、アーロン・クールヴィル(Aaron Courville)による教科書『Deep Learning』(2016年)の第10章は、RNNを時刻ごとに展開した計算グラフへ誤差逆伝播法を適用したものをBPTTと呼んでいます。同書は、RNNの勾配の計算は素直なもので、展開した計算グラフに一般的な誤差逆伝播法を当てはめるだけでよく、特別なアルゴリズムは要らないと述べています。つまりBPTTは、誤差逆伝播法とは別の新しい学習則ではありません。求めた勾配は、勾配を使う一般的な最適化手法にそのまま渡して、重みの更新に使えます。

誰が最初にこの方法を提案したかは、この記事の根拠にした教科書の該当箇所には書かれていません。

ループを時刻ごとに並べ直した計算グラフ

RNNを図に描くと、隠れ層から自分自身へ戻るループを持った形になります。このままでは、どの計算がどの計算の結果を使っているかが時刻をまたいで見えにくくなります。そこで、時刻1から系列の最後の時刻 $\tau$(タウ)までの計算を時刻ごとに横へ並べ直します。これを展開(unfold)と呼び、並べ直した結果を展開した計算グラフと呼びます。展開した計算グラフでは、1つ1つの節点がどれか1つの時刻に対応します。

同書が例に使うRNNは、時刻 $t$ で次の計算をします。

$$a^{(t)}=b+W{h}^{(t-1)}+U{x}^{(t)},h^{(t)}=\tanh \left(a^{(t)}\right),o^{(t)}=c+V{h}^{(t)}$$

$x^{(t)}$ は時刻 $t$ の入力、$h^{(t)}$ は隠れ状態、$o^{(t)}$ は出力です。$U$ は入力から隠れ層への重み行列、$W$ は1つ前の時刻の隠れ層から今の時刻の隠れ層への重み行列、$V$ は隠れ層から出力への重み行列で、$b$ と $c$ はバイアスです。計算は初期状態 $h^{(0)}$ を決めるところから始まります。

$W$、$U$、$V$、$b$、$c$ は、すべての時刻で同じものを使います。展開した計算グラフには同じ $W$ が時刻の数だけ繰り返し現れますが、別々の重みが $\tau$ 個あるわけではありません。この点が、あとで重みの勾配を求めるときに効いてきます。

系列全体の損失は、各時刻の損失 $L^{(t)}$ の和です。

$$L=\sum _{t=1}^{\tau }{L}^{(t)}$$

最後の時刻から勾配をさかのぼらせる

BPTTの計算は2つの段階からなります。まず順伝播で、展開した計算グラフを時刻1から時刻 $\tau$ へ向かって計算し、各時刻の隠れ状態・出力・損失を求めます。次に逆伝播で、同じグラフを時刻 $\tau$ から時刻1へ向かってたどり、勾配を求めます。

逆伝播は系列の最後から始めます。最後の時刻の隠れ状態 $h^{(\tau )}$ は、その時刻の出力 $o^{(\tau )}$ にしか影響しないので、勾配を出力の側からだけ受け取ります。それより前の時刻の隠れ状態 $h^{(t)}$ は、同じ時刻の出力 $o^{(t)}$ と、次の時刻の隠れ状態 $h^{(t+1)}$ の両方に影響します。そのため $h^{(t)}$ の勾配は、次の時刻から戻ってくる分と、同じ時刻の出力から戻ってくる分の和になります。同書はこれを次の式で書いています。

$${\nabla }_{h^{(t)}}L=W^{\top }\mathrm{diag}\left(1-{\left(h^{(t+1)}\right)}^2\right)\left({\nabla }_{h^{(t+1)}}L\right)+V^{\top }\left({\nabla }_{o^{(t)}}L\right)$$

${\nabla }_{h^{(t)}}L$ は、損失 $L$ を $h^{(t)}$ の各要素で微分した値を並べたもので、$h^{(t)}$ についての勾配です。$\mathrm{diag}\left(1-{\left(h^{(t+1)}\right)}^2\right)$ は、$1-{\left(h_i^{(t+1)}\right)}^2$ を対角に並べた行列で、活性化関数 tanh の微分に当たります。右辺の第1項が1つ後の時刻から戻ってくる分、第2項が同じ時刻の出力から戻ってくる分です。この式を $t=\tau -1$ から $t=1$ まで順に当てはめることで、勾配が時刻をさかのぼって伝わります。

第1項には $W^{\top }$ が掛かっています。時刻を1つさかのぼるたびにこの項を通るので、遠い過去の隠れ状態に届く勾配には、$W^{\top }$ と tanh の微分の行列が、さかのぼった時刻の数だけ繰り返し掛かることになります。

共有した重みの勾配は時刻ごとの寄与の合計になる

各時刻の隠れ状態の勾配がそろったら、重みの勾配を求めます。同じ $W$ がすべての時刻で使われているので、$W$ が損失に与える影響も全時刻に散らばっています。同書は、時刻 $t$ だけで使う $W$ の写し $W^{(t)}$ を考え、時刻ごとの寄与を求めてから全時刻について足し合わせる形で、次の式を示しています。

$${\nabla }_{W}L=\sum _t\mathrm{diag}\left(1-{\left(h^{(t)}\right)}^2\right)\left({\nabla }_{h^{(t)}}L\right){\left(h^{(t-1)}\right)}^{\top }$$

$U$ の勾配も同じ形で、$h^{(t-1)}$ の代わりにその時刻の入力 $x^{(t)}$ が入ります。

この「時刻ごとの寄与を足す」を数値で確かめるために、式を小さくした例を使います。値はすべて説明のために決めた架空のものです。計算を簡単にするため活性化関数を省き(tanh の代わりに入力をそのまま返す関数を使い)、隠れ状態も重みも1つの数にします。

$$h^{(t)}=w{h}^{(t-1)}+u{x}^{(t)}$$

重みを $w=0.5$、$u=1$、初期状態を $h^{(0)}=0$、入力を $x^{(1)}=1$、$x^{(2)}=2$、$x^{(3)}=3$ とし、損失を最後の隠れ状態そのもの $L=h^{(3)}$ とします。

順伝播は時刻1から順に進みます。逆伝播は時刻3から始まり、$L=h^{(3)}$ なので $\partial L/\partial h^{(3)}=1$ です。$h^{(3)}=w{h}^{(2)}+u{x}^{(3)}$ なので、時刻を1つさかのぼるたびに $w=0.5$ が掛かり、時刻2では $0.5$、時刻1では $0.25$ になります。

$w$ の勾配は、各時刻で $w$ が掛かった相手 $h^{(t-1)}$ に、その時刻の $\partial L/\partial h^{(t)}$ を掛けて、3つの時刻の分を足し合わせたものです。

$$\frac{\partial L}{\partial w}=1\times h^{(2)}+0.5\times h^{(1)}+0.25\times h^{(0)}=2.5+0.5+0=3$$

確かめとして、$h^{(3)}$ を $w$ だけの式に書き直すと $h^{(3)}=w^2+2w+3$ です。これを $w$ で微分した $2w+2$ に $w=0.5$ を入れると $3$ になり、上の結果と一致します。同じように $u$ の勾配は $1\times 3+0.5\times 2+0.25\times 1=4.25$ です。どれか1つの時刻の寄与だけでは正しい勾配にならず、全時刻の分を足して初めて正しくなります。

計算時間とメモリはどちらも系列の長さに比例する

同書は、BPTTの計算時間を $O(\tau )$ としています。$O(\tau )$ は、系列の長さ $\tau$ が2倍になれば計算量もおよそ2倍になる、という増え方を表す記法です。さらに同書は、この計算時間は並列化で短くできないと述べています。理由は、順伝播がもともと逐次的だからです。時刻 $t$ の隠れ状態は、時刻 $t-1$ の隠れ状態が決まるまで計算できません。上の例でも、$h^{(3)}$ を求めるには先に $h^{(2)}$ が、$h^{(2)}$ を求めるには先に $h^{(1)}$ が必要でした。

メモリについても同書は $O(\tau )$ としています。逆伝播の式は、順伝播で求めた隠れ状態を使います。そのため順伝播で計算した状態は、逆伝播で使い終わるまで保存しておく必要があります。上の例でも、$\partial L/\partial w$ を求めるのに $h^{(0)}$ から $h^{(2)}$ までをすべて使いました。

同書はここまでの説明のまとめとして、隠れ層どうしに再帰を持つネットワークはとても強力だが、学習の費用も大きいと述べています。

教師強制でBPTTを避けられる場合と避けられない場合

同書は、この費用を避ける方法として教師強制(teacher forcing)を取り上げています。教師強制は、ある時刻の出力から次の時刻の隠れ層へつながる接続を持つRNNで使える学習方法です。学習のときに、モデル自身の出力の代わりに訓練データにある正解 $y^{(t)}$ を時刻 $t+1$ への入力として与えます。

再帰が出力から次の時刻の隠れ層への接続だけで、隠れ層どうしの再帰を持たないネットワークでは、前の時刻の出力を先に計算する必要がありません。その値の正解が訓練データに書かれているからです。したがって各時刻の勾配を他の時刻から切り離して計算でき、学習を並列化できます。ただし同書は、この形のネットワークは隠れ層どうしの再帰を持つものより表現できる関数の範囲が狭いとも述べています。

隠れ層どうしの再帰を持つモデルでも、出力から次の時刻への接続があれば教師強制を適用できます。しかし同書によれば、隠れ層が過去の時刻の関数になった時点でBPTTが必要になります。このため、教師強制とBPTTの両方を使って学習するモデルもあります。教師強制はどんなRNNでもBPTTの代わりになるわけではなく、隠れ層どうしの再帰があるかどうかで、BPTTが要るかどうかが決まります。