論文読みメモ： Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting

2021-02-14 3枚目の絵を修正しました。

以下の論文を読みます。私の誤りは私に帰属します。お気付きの点がありましたらご指摘いただけますと幸いです。

Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, Wancai Zhang. Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting. arXiv preprint arXiv:2012.07436, 2020.
[2012.07436] Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting
GitHub - zhouhaoyi/Informer2020: The GitHub repository for the paper "Informer" accepted by AAAI 2021.

まとめ

遠い過去のステップも直接「注意」しにいける Transformer は時系列データの長期予測に有用と考えられるが、長い系列を Transformer に流すには以下の難点がある。

セルフアテンションする以上、系列長 $L$ に対して $\mathcal{O}(L^2)$ の計算量がかかる。
セルフアテンション層を積み重ねる原理上、推論時に膨大なメモリを要する。
推論に時間がかかる（再帰的にデコードするため）（誤差の蓄積の問題もある）。

そこで提案モデル「Informer」ではこれらの難点を以下のように克服した。

「ProbSparse」というセルフアテンション手法で特徴抽出性能を維持しつつ計算量を $\mathcal{O}(L \log L)$ に抑えた。

方針として、 ${\rm Softmax}(QK^\top /\sqrt{d}) \in \mathbb{R}^{L \times L}$ の各行のうち一様分布からの逸脱度が大きい行（＝重要な「注意」を含んでいる見込みが高い）だけを残し他の行は捨てる。サンプリングによって逸脱度を見積もる。

セルフアテンション層を出る度に Conv1D + MaxPool1D して系列の長さを半分にしていくことでメモリ使用量を抑えた（セルフアテンション蒸留）。
再帰的にデコードするのではなく一気にデコードすることで推論速度を大幅に向上させた（生成的デコーダ）。

この「Informer」はデータセット「Electricity Transformer Temperature（著者による変電所の変圧器の油温データ）」、「Electricity Consuming Load」、「Weather」を使用したさまざまな長期予測タスク（単/多変量予測 × 24～960ステップ先予測）のほとんどで既存手法（ARIMA、Prophet、LSTMa、LSTnet、DeepAR）を上回る精度を示した。また、

「ProbSparse」によるセルフアテンションの有効性の検証として、「通常のセルフアテンション」「Reformer のセルフアテンション」「LogSparse Transformer のセルフアテンション」に置き換えたモデルとも比較されたが、やはりほとんどのタスクでこれらのモデルよりも高い精度を示した。特に、通常のセルフアテンション（計算量大）よりもむしろ精度がよいケースが多かった（＝「ProbSparse」による取捨選択が功を奏した）。
セルフアテンション蒸留の有効性の検証として、セルフアテンション蒸留しないモデル構造とも比較されたが、入力系列の長さが同じであれば蒸留しないモデルの方が精度が出るが、蒸留しないモデルでは入力系列を長くするとアウトオブメモリーになるので、結局セルフアテンション蒸留をした方がよかった。
生成的デコーダの検証として再帰的にデコードするモデルとも比較されたが、再帰的にデコードするモデルでは誤差が大きすぎた。

所感

提案した3コンポーネント全ての有効性を示している。
セルフアテンションの計算量の削減の仕方が、先行研究の LogSparse Transformer のように「近くは綿密に計算するが遠くにいくほどどんどんとばす」という幾分アドホックなものではなく、積極的に何かを強く注意している行を優先して残そうとするものになっている。その有効性は通常のセルフアテンションの予測性能を上回っていることで示されている。
NeurIPS2020 の Adversarial Sparse Transformer は Transformer を敵対的に学習することで長期予測における誤差の蓄積を回避したが、そもそも再帰的に予測したいという要請がなければ Informer のように一度に予測すればよいと考えられる。

導入
モデル
検証データと比較手法

導入

f:id:cookie-box:20190101155733p:plain:w60

この「Informer」は「Transformer による時系列の長期予測」とのことですが、つい最近も「Transformer による時系列の長期予測」をみた気が…以下の「AST（Adversarial Sparse Transformer）」ですね。

NeurIPS2020読みメモ： Adversarial Sparse Transformer for Time Series Forecasting

「AST」が工夫した点は α-entmax を用いてアテンションを疎にし重要な情報をこそ注意するようにした点と、ネットワークを GAN の要領で敵対的に学習した点でしょうか。遠い未来の予測値はそこに至るまでの予測値の系列を再帰的に利用して生成するわけですから、あたかも本物と見紛うような予測値の系列を生み出す必要があるわけで、GAN を用いて学習するというのはイメージとして合っているような気がします。

他方、こちらの「Informer」はやはり Transformer が遠い過去の情報を掴めることを利用しているわけですが、Transformer を時系列に応用するにあたって以下が問題だといっていますね。

セルフアテンションする以上、系列長 $L$ に対して $\mathcal{O}(L^2)$ の計算量がかかる。
セルフアテンション層を積み重ねる原理上、推論時に膨大なメモリを要する。
推論に時間がかかる（再帰的に推論するため）。

1. や 2. は確かに Transformer の一般的な難点と思います。3. は1つの文章を分類などする分には気にならない点と思いますが。「AST」では 1. や 2. のような計算量やメモリについて何か言及していましたっけ？

f:id:cookie-box:20190101160814p:plain:w60

していなかった気がするけどな…でも、Transformer を時系列に応用するにあたってその系列長に関する計算量のボトルネックを何とかしようという話ならむしろ NeurIPS2019 にあったよね。以下の記事の中の「Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting」かな。このモデルの通称は「LogSparse Transformer」だね。

雑記： NeurIPS 2019 Proceedings の「時系列」を含むタイトル

趣旨が同じだから当然「Informer」からも「LogSparse Transformer」は引用されているね。というか6ページ目の検証結果の Table 1 や Table 2 内で「LogTrans」とされて比較手法になっているね（今回の提案手法でのセルフアテンションの仕方の有効性を確かめるためにセルフアテンションの仕方だけを置き換えた形だと思うけど）。表をみると「LogTrans」は Table 2 の多変量時系列予測部門の ECL データセットの1週間後、2週間後予測で優勝しているね。他の予測でも提案手法に肉薄している気もするけど。

うおお勝手に先を読まないでください。アブストラクトに戻ると今回の「Informer」は上記の問題に対し、

「ProbSparse」なるアテンション手法で特徴抽出性能を維持しつつ計算量を $\mathcal{O}(L \log L)$ に抑えた。
「セルフアテンション蒸留」で系列長を削減していくことでメモリ使用量を抑えた。
「生成的デコーダ」によって1ステップでの長期予測を達成し推論速度を大幅に向上させると共に、誤差の蓄積も抑えた。

のように対処したとのことですが…ともかく本文に入ると、既存の時系列予測モデルは基本的に長期予測に耐えるようにできていないということですね。Figure 1 (c) のように「LSTM で長期予測をしたら遠い未来を予測するほど誤差は増えていき、その1点の予測値を得る時間も増える」と。なお、この Figure 1 (c) の LSTM は何を学習したものかというと、ETT データセット（著者が作成したデータセット；後述）の1時間ごとの変電所の変圧器の油温を、直近の12点（つまり半日分）を用いて未来を予測するように学習したもので、Figure 1 (c) では最長で480点先（20日後）まで予測したということですね。20日後の変圧器の油温の予測とは果てしない気がしますが…。

でもよく知らないけど電気を発電するなら20日くらい前から石油なり石炭なりを発注しておく必要とかあったりするんじゃないのかな。と考えると遠い未来に送電すべき量がわかるに越したことはない気はするけど、その推論速度がそんなにシビアなのかとか、信頼区間を予測した方がいいのではとかは思うかな。「生成的デコーダ」を導入した効果は推論速度よりも「誤差の蓄積を抑えた」という方が重要そうに思うんだよね。「誤差の蓄積を抑えた」というよりは、「長期予測を想定していない従来手法を無理にそのまま再帰的に利用すると誤差が蓄積されるので、長期予測にフォーカスするなら異なる枠組みを導入した方がよい」という感じがするけど。

私にいわれましても…まあそれで、遠い過去の情報を活用するとなると、過去の入力を再帰を介さずに直接「注意」しにいける Transformer に白羽の矢が立つわけですが、先に述べた通りの難点があるわけです。「セルフアテンションの威力がこそボトルネックになってしまう」と…いや何のデメリットもなくおいしい話はそうないと思いますが…。ともかくそのボトルネックを何とかしようとしにいくわけですが、何もボトルネックを何とかしようという研究はこれまでもあったわけです。列挙されているものは以下ですね。

Compressive Transformer（Rae et al. 2019）
Sparse Transformer（Child et al. 2019）	Transformer を画像にも適用しているんですね。これは論文の3ページ目の Figure 3. をみるに、アテンションの行列 ${\rm Softmax}(QK^\top /\sqrt{d})$ を完全に計算することを捨てた、といった感じがします。あるステップからどのステップに注目するかを相対位置または絶対位置に制限してしまうといったような。これは実際データに対して「この箇所に文脈として効くのはこの範囲だろう」という事前知識があれば有効でしょう。しかし、事前知識がないときには利用しづらそうに思います。
LogSparse Transformer（Li et al. 2019）	これは件の NeurIPS2019 の論文ですね。5ページ目の図をみるに、これもアテンションの行列 ${\rm Softmax}(QK^\top /\sqrt{d})$ を完全に計算することを捨てていますが、相対位置や絶対位置でフィルタするのではなく、「近くは綿密に、遠くにいくほど大雑把に」といった感じでもう少し情報の拾い漏れを防いでいるのでしょうか。
Reformer（Kitaev et al. 2019）	これも計算量を $\mathcal{O}(L \log L)$ にしていますがより技巧的にみえます。論文の4ページ目に絵があります。なんというか、処理するステップたちをあるルールで「青組、黄組、赤組、白組」に組分けした上で人口の多い組から順に並べ、等間隔にサブ系列に切って、「サブ系列内 or 自分の組内のみでアテンションする」といった感じです。それで組分けのルール locality sensitive hashing が肝心ですが、これは3ページ目の図でしょうか。点 x とその少し後ろにいる点 y があったとして、点 x をランダムに回転させたときに同じ色のエリアにいるか、といった絵にみえますが…後で実装をみてみましょう。
Linformer（Wang et al. 2020）	セルフアテンション内での射影の行列を低ランク近似することで $\mathcal{O}(L)$ を達成しているのですかね。しかし時系列の長期予測の場合は行列が固定できない故に $\mathcal{O}(L^2)$ まで劣化する可能性があるとありますが…？
Transformer-XL（Dai et al. 2019）	これらは「補助隠れ状態」を用いることで計算量を抑えつつ遠い過去の情報を利用できるようにしたようですが、であれば今回用いられたアプローチとは違いますね。これらのアプローチは時系列には応用できるのでしょうか…？

何にせよこれらでは「時系列の長期予測」という目的を達成するのに不十分といっているわけです。問題点の 1. の計算量にしか対処していないと。そもそも「LogSparse Transformer」を除いて時系列の予測を企図していませんし、「LogSparse Transformer」も長期予測を主眼においてはいないと思いますが。

問題点の 3. は長期予測に独特だからともかく、2. の必要メモリへの取り組みはあったんじゃないのかな。そのまま「蒸留BERT」なるモデルが公開されていて Linformer でも引用されているし、さらに「貧乏人のためのBERT」なんていう論文もあるよ。今回の手法とは枠組みが違うのかな？

BERT を動かせない人が貧乏なのではありません、BERT を動かせる計算資源を利用できる人がお金持ちなのです…。

モデル

気を取り直してモデルの詳細に入りましょう。まずモデルの入出力は、

モデルの入力は $d_x$ 次元ベクトルが $L_x$ 個並んだもの $\mathcal{X}^t = \{x_1^t, \cdots, x_{L_x}^t\}$ です。
モデルが出力すべきは $d_y$ 次元ベクトルが $L_y$ 個並んだもの $\mathcal{Y}^t = \{y_1^t, \cdots, y_{L_y}^t\}$ です。つまり、長期予測といっても、遠い未来の1点ではなく、遠い未来までのすべての点の予測を目指すということを含意していると思います。

そしてまず Self-Attention の話がありますね。Self-Attention の復習として下に絵を描いてみました。これは "I understand." という文章（ピリオドも1トークンとしさらに先頭トークンと末尾トークンを追加すれば5トークンからなる）を流したときのイメージで、アテンションの行列の数値は実際にこの文章を bert-large-cased 学習済みモデルに流して書き出したものです。であれば実際はヘッド数は16あるんですが面倒なので4ヘッドしか描いていません。bert-large-cased では入力特徴及び出力特徴の次元数は1024次元で、1ヘッドあたりが出力するのは64次元ですね。図中の $d=64$ ということです。

うん、自然言語処理では普通「文章長さ＜特徴次元数」だからその図の入出力みたいに横長の長方形になるわけだよね。でも今回は長期予測をしたいから、Table 1, Table 2 にある数値の単位がステップ数で合っているなら予測部分だけで960ステップ流したいことになるよね。BERTには256ステップ以上流せない設定になっているくらいだから、長いわけだね。計算量は流すステップの長さを $L$ とするなら $QK^\top$ の部分の行列積が $\mathcal{O}(L \cdot d \cdot L)$ で、最後のアテンションを適用するときの行列積が $\mathcal{O}(L \cdot L \cdot d)$ だから、 $d$ を定数扱いすれば $\mathcal{O}(L^2)$ だね。

ええまさにそのような話が続きます。なので計算量が $\mathcal{O}(L^2)$ になることを割けるべく、これまで Sparse Transformer や LogSparse Transformer は行列 ${\rm Softmax}(QK^\top /\sqrt{d})$ （面倒なのでこれ以降セルフアテンション行列とよびます）の成分を全て計算するのではなく間引きをやってきたわけですが、幾分ヒューリスティックな回避策であったわけです。それに、全ての Multi-Head で同じ間引き方をしていたと…そうなんですか？いやいわれてみれば Head ごとに間引き方を変えるべきですよね…。ともかく、現実にはセルフアテンション行列は疎であるということです。まあ特に自然言語処理では過去の単語たちをべったり注意することもないでしょうね。しかしどのように疎なのかがわからないから間引き方がわからないのですが…読み進めると3ページ目の2段目の最上部では、あるステップから各ステップをどれだけ注意するかの分布 $p$ と、一様分布 $q$ のKLダイバージェンスを取っていますね。なるほど一様分布から逸脱しているほど特定のステップに着目し、重要な情報を掴んでいる見込みが高いというわけでしょうか。以下の図でも計算してみました。

f:id:cookie-box:20210211142747p:plain:w520

上図の一番最後の式の第1項は定数なので無視して、第2項と第3項が式 (2) の $M(q_i, K)$ に相当しますね。論文中では sparsity measurement とよばれていますが、「ステップ $i$ からの各ステップへの注意分布の一様分布からの逸脱度」です（以下この記事中では逸脱度とよびましょう）。そしてセルフアテンション行列の各行のうち、逸脱度が高い $u$ 本のみを残すと。 $u$ を $\log L$ に比例させるようにとれば計算量は $\mathcal{O}(L \log L)$ になると…いやいやいや！そもそもセルフアテンション行列を得る計算量が $\mathcal{O}(L^2)$ なわけですよね？セルフアテンション行列が得られた上で「この $u$ 本だけ残そう」では意味がないですよね？？

続きを読もう。しかし逸脱度自体を得るのに $\mathcal{O}(L^2)$ かかってしまう、だから逸脱度を近似するというようにあるよ。まず補題1で逸脱度の上下限を示しているね。上下限がこうなるのは上図の式と見比べればわかる。それでこの上限の方を、完全なセルフアテンション行列からではなく、サンプリングした一部の要素だけ計算したセルフアテンション行列から見積もる。 $Q, K$ の分布の形にある程度の仮定をおけば、 $Q$ の行と $K^\top$ の列の組を $L \log L$ 組サンプリングすることで見積もれるって。そのことをきちんと示したのが命題1かな。 $k_j$ が正規分布にしたがうとしているのはどれくらい適切なのかわからないけど。まあ確かに分布が一様分布から離れているかって、分布の一番高いところが高かったらそれは離れているし、各行の最大値を見積もるだけなら行列の要素を全て計算しなくてもよさそうだよね。

サンプリングの仕方は追えていませんが、一様分布から離れているかどうかというのは、過去のヒューリスティックな回避策に比べれば積極的に意味のあるアテンションを残そうとしていますね。

セルフアテンションの計算量の問題が片付いたら次はメモリの問題でしたっけ。モデルサイズの問題といってもいいのでしょうか。セルフアテンション時の計算量を間引いても、セルフアテンション層をどんどん積み重ねるならパラメータ数とメモリ使用量は増えるばかりです。

その問題については論文4ページ目の Figure 3 をみるに、セルフアテンション層を抜ける度に Conv1D + MaxPool1D することで系列の長さを半分にしているようにみえるね。あ、この図では Attention Block という薄オレンジの直方体の中にガラス板（？）が4枚浮かんでいるようにみえるけど、これは4つのヘッドのセルフアテンション行列だね。式 (5) をみると Conv1D を適用した後に ELU で活性化している。

ELU — PyTorch 1.7.1 documentation

では最後はここまで改造した Transformer を用いてどのように推論するのかという問題ですか。1ステップずつ再帰的に読み出していくのでは時間がかかるというより誤差が積み重なっていくのですよね？

それについてはそのまま「1ステップで読み出すようにした」という感じにみえるな。以下にイメージ図を描いたよ。水色が目的変数でピンク色が説明変数（タイムスタンプなど）ね。本文中の例では、向こう7日分を予測するのに、デコーダにここまでの5日分をフィードするみたい。それで予測してほしい箇所はゼロにした状態（いわば「プレースホルダ」）を渡してそこに埋まるものを返してねって感じなんだけど、エンコーダに渡す期間とデコーダに渡す期間が把握できていないから、以下の図は GitHub の Informer の実装をみて描き直すかもしれないかな…。それで損失関数は MSE とあるね。検証したのは全部回帰タスクみたいだし。特に言及がないから、近い未来の誤差も遠い未来の誤差も重さは等しいということなのかな？

f:id:cookie-box:20210214014501p:plain:w290

検証データと比較手法

ではモデルについては一通り確認したので検証されたデータセットをみてみましょう。「電気」「電気」「天気」といったところでしょうか。

ETT (Electricity Transformer Temperature)	これは著者らが収集されたデータなのですね。以下に公開されているようです。 GitHub - zhouhaoyi/ETDataset: The Electricity Transformer dataset is collected to support the further investigation on the long sequence forecasting problem. Electricity Transformer Temperature という言葉が聞き慣れないですが、このデータセットは「変圧器の油温」を予測することを企図したものであるようです。よくわからないのですが、変圧器の油温というのが上昇しすぎると危険であって、変圧器に負荷がかからないように送電するために重要な指標ということなんでしょうか。説明変数には High UseFul Load などが含まれていますがこれは最大実効負荷などと訳すのでしょうか。ともかく、ETT-small-m1, ETT-small-m2 というのが中国のある2つの省の分単位のデータであって2年×365日×24時間×60分=1,051,200点のデータを含むそうです。時間単位になっている ETT-small-h1, ETT-small-h2 なるデータもあるようですね。
ECL (Electricity Consuming Load)	また電気ですが、お馴染みの UCI Machine Learning Repository のデータですね。 UCI Machine Learning Repository: ElectricityLoadDiagrams20112014 Data Set このデータは NeurIPS2018 の Deep State Space Models for Time Series Forecasting や NeurIPS2020 の AST でも利用されていました。ある期間におけるポルトガルの370人の個々の顧客の15分ごとの電力消費量です。
Weather	アメリカの1600地点での1時間毎の気候データでしょうか。論文中のリンクは以下に転記してみましたが、この記事をかいている時点で重すぎてアクセスできる気配がないのですよね…。 https://www.ncdc.noaa.gov/orders/qclcd/

そして比較対象となっている手法は以下です。

ARIMA	ARIMA は ARIMA ですね。ただ ARIMA の参考文献として以下が引用されているのは何故なんでしょうか。 (PDF) Stock price prediction using the ARIMA model
Prophet	Prophet も Prophet です。
LSTMa	LSTMa とは…？これは機械翻訳の論文のようですが、LSTM を普通に利用するのではなく、LSTM の各ステップの特徴を用いてデコードするコンフィギュレーションのことを LSTMa というのでしょうか。間違っていたらごめんなさい。
LSTnet	LSTnet は以下の論文を読んだときに引用されていましたね。絵も描きました。畳込みと再帰のハイブリッドモデルさんでしたね。論文読みメモ： Think Globally, Act Locally: A Deep Neural Network Approach to High-Dimensional Time Series Forecasting（その1） - クッキーの日記
DeepAR	DeepAR も DeepAR です。AST でも DeepAR の敵対的学習を試行されていましたね。ただ DeepAR は後続に Deep State Space Models があったと思いますがそちらは利用できないものなのでしょうか。

さらに、これらのモデルとは別に、「ProbSparse」によるセルフアテンションの有効性の検証として、今回のモデルのセルフアテンション部分のみを「通常のセルフアテンション」「Reformer のセルフアテンション」「LogSparse Transformer のセルフアテンション」に置き換えたモデルも比較対象にエントリーされています。公平を期すために、どのモデルのコンフィギュレーションも1GPUで推論可能なように調整されているようです（通常のセルフアテンションもなんでしょうか？）。

その結果が Table 1, Table2 ですね。ほとんどのタスクで Informer が最高精度を達成しています…って、通常のセルフアテンションよりも高精度が出ているタスクが多いのですね。Informer はセルフアテンション行列の計算を間引いたのに間引かないよりも性能がよいとはなぜなのでしょう？

取るに足らないアテンションなら最初から要らなかったということだよね。単変量予測の Table 1 で目立つのは ECL データの 48, 168, 336 ステップ先予測で DeepAR が健闘しているね。どうしてなんだろう？

私にいわれましても…。多変量予測の Table 2 もだいたい Informer 眷属の独断場ですがたまに LSTnet さんが健闘していますね。

Table 2 のモデルの中でさ、畳込みも再帰も利用しているのって LSTnet だけだよね。Transformer は特殊な畳込み扱いとして。逆に色々使っている LSTnet が少ししか勝てないのが Transformer の威力なんじゃないのかな。

私にいわれましても…。セルフアテンション手法の Reformer は精度が奮わないですね。時系列データと相性が悪いんでしょうか。Table 4 はセルフアテンション蒸留をしない場合の参考記録ですね。ハイフンになっている箇所はアウトオブメモリーと。フィードする入力系列の長さが同じならさすがに蒸留しない方が高精度は出ますが、如何せん入力系列の長さが食えないので結局蒸留した方がよい、といえそうです。Table 5 は再帰的にデコードした場合の結果で…再帰的なデコードでは誤差が大きすぎてもうお話にならなかったようですね。

一旦おわり