Speech and Language Processing: ノート1(2章の一部)

以下の本を読みます。キャラクターは架空のものです。解釈の誤りは筆者に帰属します。お気付きの点がありましたらコメントでご指摘いただけますと幸いです。

まとめ(ていない)

  • 2章では正規表現、正規化、編集距離―「テキストデータをどこで区切るべきか」や「区切ったらどの単語とどの単語を同じと扱うべきか」を与える確立されたツールが紹介されている。

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

スピーチと言語の処理、ですか。28章もあるんですね…。1章のイントロダクションはまだ執筆されていませんね。2章は Regular Expressions, Text Normalization, Edit Distance ということですが…冒頭にユーザと ELIZA さんという方との会話が出てきますね。…この ELIZA さんあたりがきつくないですか? 「助けがほしい」という人に「助けられたら何だというのか」といいますか??

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

イライザっていうみたいだね。実に1966年につくられた自動応答システムらしい。

パターンマッチを活用して心理療法士の会話を模倣していて、例えば「X が必要だ」といわれたら「X を得られたらあなたにとってどんな意味がありますか?」というように返すみたい。そんな単純な仕組みにもかかわらず、イライザと対話した人々は本当にイライザが自分で考えて応答しているのだと信じ込んだというようにあるね。教科書にもウィキペディアにも。

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

ええ…イライザさんは心理療法士ボットだったんですか…? 心の治療に行ったのに逆にストレスを負いそうな…。

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

どうかな、「やせなければならない」という強迫観念をもっている人には「やせたらどうなりますか?」と訊いて治療していくんじゃないのかな。知らないけど。

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

そんなものですかね…なるほど、この導入で正規表現と正規化が出てくるんですね。正規化はより細かくみるとトークン化、レンマ化(単純なレンマ化の方法の一つがステミング)、文区切りなどの手続きが含まれているということですが…イライザさんの例では、いわれたことに応答するという目的を達成するために、「X が必要だ」というパターンに合致するかどうかを判定しますが、きっと(正規化と)正規表現を利用していますよね。自然言語処理って細かいプラクティスが多くて面倒そうですね…。

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

裏を返せばそれだけデータの構造と意味を予め知っているからなんじゃないかな。もしテキストデータをそのまま数値(ASCIIコードか何か)の配列として扱って「入力されたテキストに対する心理療法士の応答」を学ぼうとするときっと途方もなく効率が悪いけど、実際の会話にかなり構造のパターンがあることがわかっていれば1960年代でも人間らしいボットが実現できるんだから。この頃の画像認識とかなんて人間っぽく何の画像か色々見分けたりはできなかったんじゃないの? 知らないけど。

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

さっきから教科書への相槌が雑ですね…それに、テキストデータへの理解には分があるといってもそれ以上にタスクも曖昧で困難なものが求められがちじゃないんですか? 質問に答えるとか翻訳するとか…。そういえば、アラビア語って活用形が多いんですか? レンマ化のくだりに morphologically complex languages like Arabic とありますが。

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

ウィキペディアをみると、「現代アラビア語では、派生形は基本的に第10形までしかなく、古典アラビア語が持つ第15形までの派生形はほとんど用いられない」ってあるよ。

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

いや、「10個しかないので大丈夫ですよ」みたいにいわれても…。導入部の最後に編集距離(Edit Distance)というのが出てきますが、スペルミス検出とかスピーチ認識において同一のものを指す単語の検出とかにつかうんですね。ある文字列を別の文字列にするのに何回の挿入、削除、置換を要したかというようなものなのでしょうか。…これって最短経路を求めるの大変なんじゃないですか?

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

うん、2.5.1節に "The space of all possible edits is enormous, so we can’t search naively." とあるね。だから、動的計画法(具体的にはビタビアルゴリズムやCKYアルゴリズムなど)で解いたりするってある。

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

ビタビアルゴリズム放送大学教材の「自然言語処理」で名前は目にしたことがあります。39ページです。しかし、このときは編集距離という文脈ではなかったような…日本語の文章の形態素解析で複数の解釈がありえる場合がありますよね。教科書の例が以下です。以下のように列挙すると4パターンありますが(単純な例なので少ないですが実際にはとても多い)、途中の「元気」まで、「ね(根)‐たら(鱈)」を経由するのと「ねたら(寝たら)」を経由するのではコスト(ノードやエッジに対して適切に定義してください)が小さいのは後者なのでこの時点で「ね(根)‐たら(鱈)」の可能性は刈り取れるということです。

  • 《文頭》‐ね(根)‐たら(鱈)‐元気‐に‐なった‐《文末》
  • 《文頭》‐ねたら(寝たら)‐元気‐に‐なった‐《文末》 ※ 正解
  • 《文頭》‐ね(根)‐たら(鱈)‐元気‐になった(担った)‐《文末》
  • 《文頭》‐ねたら(寝たら)‐元気‐になった(担った)‐《文末》
…しかし、これはスペルミス検出ではないですよね?

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

うん、こちらの教科書で Viterbi Algorithm が出てくる8.4.5節でもむしろその放送大学の教科書の例に近い品詞タグ付けタスクの例で説明されている。編集距離に沿った説明については2.5.1節のつづきを読んだ方がよさそう…2.5.1節で最初に出てくる数式がその方法かな。この数式に具体的に X="inten" と Y="execu" をあてはめるとこうだね。

  • 「inten を execu にする最小コスト」は、以下のうち最小のものである。
    • 【1】「n を削除するコスト」+「inte を execu にする最小コスト」
    • 【2】「inten を exec にする最小コスト」+「u を挿入するコスト」
    • 【3】「inte を exec にする最小コスト」+「n を u に置換するコスト」
文字列から文字列への最短経路(最小コスト)を求める問題を、より短い文字列から文字列への最小コストを求める問題にできている。これを利用すればどんどん短い文字列に対する問題にできる。

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

え、うーん、わかるような気はしますが…場合分けってそれでMECEになっているんですか?

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

文字列を文字を参照しているポインタの配列と考えるとわかりやすいかも。つまり、「削除」「挿入」「置換」を、「削除」は配列からポインタを取り除くこと、「挿入」は新しいポインタを配列のどこかに挿入すること、「置換」はポインタの参照先の文字を書き換えることって考える。このとき、以下の場合分けはMECEだよね。

  • n 文字の元文字列を m 文字の新文字列にするような操作は、以下の3パターンに場合分けできる。
    • 元文字列の n 番目のポインタが取り除かれる。
    • 元文字列の n 番目のポインタが新文字列において m-1 番目までにいる。
    • 元文字列の n 番目のポインタが新文字列において m 番目にいる。
これと以下の事実を組み合わせればいい。
  • 元文字列の n 番目のポインタが取り除かれるならば、そのポインタがいつ取り除かれるにせよ、そのポインタが取り除かれる操作を除いた残りの操作は「元文字列の n-1 文字目までを新文字列の m 文字目までにする」操作になっている。
  • 新文字列において元文字列の n 番目のポインタが生き残っていて、かつ、それより後ろにポインタがあるならば、それらのポインタは全て挿入されたものである(「削除」「挿入」「置換」は元文字列のポインタの順序を変えない)。

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

その説明で伝わりますかね…? とにかく、intention から execution へのレーベンシュタイン距離(編集距離であって、コストの定義は削除コストが1、挿入コストが1、異なる文字への置換コストが2)を求めてみましょう。面倒なので、intent から execut へのレーベンシュタイン距離を測ります。同じなので。先に図2.16から正解を確認しておくと、8ですね。delete が1回、substitute が3回、insert が1回ですから。では D("intent", "execut") を求めていきますが、レーベンシュタイン距離では異なる文字への置換は挿入+削除としてもコストが同じなので、同じ文字への置換でない限り上の【3】を無視してかいています。

  • D("inte", "e") = 3 ①②③
  • D("inte", "ex") = min{ 1+D("int", "ex")=6, D("inte", "e")+1=4 } = 4
  • D("inte", "exe") = min{ 1+D("int", "exe")=7, D("inte", "ex")+1=5 } = 5
  • D("inte", "exec") = min{ 1+D("int", "exec")=8, D("inte", "exe")+1=6 } = 6
  • D("inte", "execu") = min{ 1+D("int", "execu")=9, D("inte", "exec")+1=7 } = 7
  • D("inte", "execut") = min{ 1+D("int", "execut")=8, D("inte", "execu")+1=8 } = 8
  • D("inten", "ex") = min{ 1+D("inte", "ex")=5, D("inten", "e")+1=5 } = 5
  • D("inten", "exe") = min{ 1+D("inte", "exe")=6, D("inten", "ex")+1=6 } = 6
  • D("inten", "exec") = min{ 1+D("inte", "exec")=7, D("inten", "exe")+1=7 } = 7
  • D("inten", "execu") = min{ 1+D("inte", "execu")=8, D("inten", "exec")+1=8 } = 8
  • D("inten", "execut") = min{ 1+D("inte", "execut")=9, D("inten", "execu")+1=9 } = 9
  • D("intent", "ex") = min{ 1+D("inten", "ex")=6, D("intent", "e")+1=6 } = 6
  • D("intent", "exe") = min{ 1+D("inten", "exe")=7, D("intent", "ex")+1=7 } = 7
  • D("intent", "exec") = min{ 1+D("inten", "exec")=8, D("intent", "exe")+1=8 } = 8
  • D("intent", "execu") = min{ 1+D("inten", "execu")=9, D("intent", "exec")+1=9 } = 9
  • D("intent", "execut") = min{ 1+D("inten", "execut")=10, D("intent", "execu")+1=10, D("inten", "execu")=8 } = 8 ★ ここから出発
以上のようになります。D("intent", "execut") から最短経路を逆にたどってピンク色に塗りました。しかし、最短経路はこれ以外にもあります(削除や挿入の順序に自由度がありますから)。あくまでこの経路は一例です。この経路をかきくだすと以下のようになります。レーベンシュタイン距離は8です。
  • intention
    →(①②③ int を削除する)→ ention
    →(④ x を挿入する)→ xention
    →(⑤ e を挿入する)→ exention
    →(⑥ c を挿入する)→ execntion
    →(⑦ u を挿入する)→ execuntion
    →(⑧ n を削除する)→ execution

次回があればつづく

Time Series Analysis: ノート2章(その2)

以下の本を読みます。キャラクターは架空のものです。解釈の誤りは筆者に帰属します。お気付きの点がありましたらコメントでご指摘いただけますと幸いです。

Time Series Analysis

Time Series Analysis

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

前回はテキストの2.1節~2.3節の途中まで読んだのですが、どんな話だったかというと…というか、きちんと読んでいないんですがそもそも1章ではまず線形差分方程式で表される系列の性質を調べたのですよね? 例えば2次の差分方程式だったら (1.2.13) 式の解  \lambda_1, \lambda_2 が重要な意味をもつはずです。つまり、これらのいずれか一方でも絶対値が1より大きければ、ある時刻の w_t がそれより未来のある時刻の y_{t+j} に与える影響(=ダイナミックマルチプライヤ)が、j \to \infty で発散(振動)します。どちらも絶対値が1より小さければ収束します。なので、系列が bounded であってくれるためには  \lambda_1, \lambda_2 の絶対値は1未満でないと困るわけです。

他方、2章ではラグオペレータ L なるものを導入しました。この L を系列にくっつけるとすべての時刻の要素が1ステップずつ未来に引っ張り出された新しい系列ができるとでもいうのでしょうか、そんなものです。くっつけられた系列さんにしてみれば1ステップ未来に引っ張りだされますが、くっつける私たちからみれば対象の系列の1ステップ過去を覗いているわけです。だから何なのかというと、2次の差分方程式は2ステップまで過去の自分を参照しますが、ラグオペレータをつかうと過去の自分を参照しない形で表現できます(系列が bounded であるという仮定の下でですが、 1 - \lambda L の逆オペレータが定義できるので)。そうするとまた先ほどの  \lambda_1, \lambda_2 に出くわします。ここでもまた  \lambda_1, \lambda_2 の絶対値は1未満でないと困るということにたどりつきます。

…1章も2章も内容としては、「系列が bounded であってくれるためには、系列を生み出すモデルはこうあってほしい」というのをそれぞれ別の側面から取り扱っているのではないかと思うのですが…確かに、時系列に対するモデルには、ふつう「前の時刻がこうだったら次の時刻はこうする」というのを入れるわけですから、下手なことをするとすぐ発散(振動)してしまう恐れがあります。分析対象の時系列を適切にプレ処理して bounded なモデルを当てる必要があるといいたいのでしょうか…?

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

2章にはそれに加えて最後の2.5節に株価 P_t と配当 D_t の具体例が挙げられているみたいだけど。というかこれ株式評価の配当割引モデルだな…。

2次の差分方程式を例にして、1章のアプローチをまとめておくと、

  •  y_t = \phi_1 y_{t-1} + \phi_2 y_{t-2} + w_t で表される系列の性質を知りたい。
  • 2次の差分だと逐次的に扱うことができないので、1次の差分にする(以下)。
     \left( \begin{array}{c} y_t \\ y_{t-1} \end{array} \right) = \left( \begin{array}{cc} \phi_1 & \phi_2 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} y_{t-1} \\ y_{t-2} \end{array} \right) + \left( \begin{array}{c} w_t \\ 0 \end{array} \right)
  • ある時刻の w_ty_{t+j} \; (j > 0) に与える影響を知るには、以下の行列 Fj 乗の (1,1) 成分をとればよい( ∵ \tau < ty_{\tau}=0 だったとすると、y_t = w_t であり、(y_{t+1}, y_t)^\top = F (w_t, 0)^\top であり、(y_{t+j}, y_{t+j-1})^\top = F^j (w_t, 0)^\top である)。
     F = \left( \begin{array}{cc} \phi_1 & \phi_2 \\ 1 & 0 \end{array} \right)
  • 行列を累乗するには対角化するのが常套手段である。F=T \Lambda T^{-1} として \Lambda を対角行列にするには、以下の方程式の解を \Lambda の対角要素とすればよい。
     \lambda^2 - \phi_1 \lambda - \phi_2 = 0
    ステップが進むと対角要素は何回でも掛け合わされていくので、この方程式の解の絶対値が1を超えると系列は bounded にならないことがわかる。

対して2章のアプローチは、

  •  y_t = \phi_1 y_{t-1} + \phi_2 y_{t-2} + w_t で表される系列の性質を知りたい。
  • これだと y_t について解けないので、ラグオペレータ L というものを導入してみる(以下)。
     (1 - \phi_1 L - \phi_2 L^2) y_t = w_t
  • ラグオペレータは  1 - \lambda L の形にすると逆オペレータ  (1 - \lambda L)^{-1} = 1 + \lambda L + \lambda^2 L^2 + \cdots が存在する。ので、上の式を以下の形にしたい。
     (1 - \lambda_1 L)(1 - \lambda_2 L) y_t = w_t
     \Rightarrow y_t = (1 - \lambda_1 L)^{-1}(1 - \lambda_2 L)^{-1}w_t
  •  (1 - \phi_1 L - \phi_2 L^2) = (1 - \lambda_1 L)(1 - \lambda_2 L) が成り立つためには、係数比較より、 \lambda_1 + \lambda_2 = \phi_1 \lambda_1 \lambda_2 = -\phi_2 が成り立たなければならないが、2次方程式の解と係数の関係より、\lambda_1, \lambda_2 は以下の方程式の解に他ならない。
     \lambda^2 - \phi_1 \lambda - \phi_2 = 0
    この方程式の解は何回でも掛け合わされていくので(逆オペレータの定義)、この方程式の解の絶対値が1を超えると系列は bounded にならないことがわかる。

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

前回の続きの2.4節は一般のp次の差分方程式の場合ですね。

 y_t = \phi_1 y_{t-1} + \phi_2 y_{t-2}+ \cdots + \phi_p y_{t-p} + w_t
 (1 - \phi_1 L - \phi_2 L^2 + \cdots + \phi_p L^{p}) y_t = w_t
これを以下のように因数分解したいわけです。
 (1 - \lambda_1 L)(1 - \lambda_2 L) \cdots (1 - \lambda_p L)y_t = w_t
が、この \lambda_1, \lambda_2, \cdots, \lambda_p を求めるのは式 (1.2.3) の行列 F固有値を求めることと同じというように Proposition 2.2 にありますが…?

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

解と係数の関係から  \lambda_1, \cdots, \lambda_p が Proposition 1.1 の (1.2.16) 式の解になることを示して、かつ、行列 F固有値(1.2.16) 式の解になることを示せばいいんじゃないかな。帰納法で示せるんじゃないのかな。

あとで追記

Time Series Analysis: ノート2章(その1)

以下の本を読みます。キャラクターは架空のものです。解釈の誤りは筆者に帰属します。お気付きの点がありましたらコメントでご指摘いただけますと幸いです。

Time Series Analysis

Time Series Analysis

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

2章のタイトルは「ラグオペレータ」というのでしょうか。まず「オペレータ」とは時系列(たち)を受け取って新しい時系列を出力するものみたいですね。「時系列0を \beta 倍する」とか「時系列0と時系列1を足す」とかがその例のようです。いわば「掛け算オペレータ」と「足し算オペレータ」ですね。これらのオペレータについては「入力された時系列の時刻 t の値をつかって新しい時系列の時刻 t の値をつくる」ということしかしないので、「時系列0と時系列1をそれぞれ \beta 倍してから足す」ということをしても「時系列0と時系列1を足してから \beta 倍する」ということをしても結果は同じということです。

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

時系列が値を取る空間で分配法則が成り立っていればそれはそうなるね。

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

まあただ本当に利用したいのは「ラグオペレータ」なわけです。ラグオペレータ Ly_t = Lx_t \equiv x_{t-1} ということをするオペレータです。日本語でいうなら「入力された時系列の時刻 t-1 の値をそのまま新しい時系列の時刻 t の値にする」ですね。入力された時系列のインデックスを1ステップ遅らせるからラグというのでしょうか。入力された時系列の1ステップ昔を覗くメガネということもできそうです。

それで、ラグオペレータは掛け算オペレータや足し算オペレータと交換するということです。つまり、

  • 時系列0を \beta 倍してからインデックスに1を足す。
  • 時系列0のインデックスに1を足してから \beta 倍する。
はどちらも同じ時系列になりますし、
  • 時系列0と時系列1を足してからインデックスに1を足す。
  • 時系列0と時系列1それぞれインデックスに1を足してから両者を足す。
もどちらも同じ時系列になります…ということは、もしや任意のオペレータは交換するのでは?

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

そんなわけないかな。例えば各インデックスが日付だったとして、「月曜日の値だけ2倍する」というオペレータがありうるけど、これはラグオペレータと交換しないよ。「月曜日の値だけ2倍する」オペレータを先に作用させると元の時系列の月曜日の値が2倍されてから火曜日にずらされるけど、先にラグオペレータを作用させると元の時系列の日曜日の値が月曜日にずらされてから2倍されるからね。

元時
系列
1234567
月曜
2倍
1434567
ラグ
  
0143456
元時
系列
1234567
ラグ
  
0123456
月曜
2倍
0223456
ラグオペレータと交換するには「新しい時系列の時刻 t の値が、元の時系列の時刻  \{t + c_i\}_{i = 0, 1, \cdots} の値たち(c_0, c_1, \cdotst によらない整数)および t に依存しない定数たちのみに依存する」ようなオペレータじゃないといけないんじゃないかな。「掛け算オペレータ」や「足し算オペレータ」の他に「値が10を超える場合は10にする」「その日を中心にした3日間の平均をとる」みたいなオペレータとかもありうると思う。無論ラグオペレータ自身もラグオペレータと交換するね。

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

ぬ…。まあそれで、ラグオペレータをつかうと y_t = \phi y_{t-1} + w_t のような差分方程式が y_t = \phi L y_t + w_t とかけるとのことです。さらに移項することによって  (1 - \phi L)y_t = w_t \tag{2.2.2} となると。それはまあそうですが…それで、この両辺に以下をかける?

 1 + \phi L + \phi^2 L^2 + \cdots + \phi^t L^t \tag{2.2.3}
なぜこんなものをかけるんです…いくらなんでも唐突すぎるでしょう…。

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

やりたいことは、y_t を、y_{t-1} に何をしたものかで表すんじゃなく、一番最初の y_{-1} に何をしたものかで表すことだね。そうするには  (1 - \phi L)y_t = w_t の左辺を  (1 - a L^{t+1})y_t にすればいい(a は適切な係数)。y_t にラグオペレータを t+1 回かければ y_{-1} に巻き戻せるからね。以下の因数分解の公式を思い出すと、

 1 - x^n = (1 - x)(1 + x + x^2 + \cdots + x^{n-1})
 (1 - \phi L)y_t = w_t の両辺に  1 + \phi L + \phi^2 L^2 + \cdots + \phi^t L^t をかければ以下のようにできるよね。
 (1 - \phi^{t+1} L^{t+1})y_t = (1 + \phi L + \phi^2 L^2 + \cdots + \phi^t L^t)w_t \tag{2.2.6}
このラグオペレータを適用して移項すると以下のようになる。
 y_t = \phi^{t+1} y_{-1} + w_t + \phi w_{t-1} + \phi^2 w_{t-2} + \cdots + \phi^t w_0 \tag{2.2.7}
最初の差分方程式と並べると、
 \begin{split} y_t &= \phi y_{t-1} + w_t  \\ y_t &= \phi^{t+1} y_{-1} + w_t + \phi w_{t-1} + \phi^2 w_{t-2} + \cdots + \phi^t w_0  \end{split}
それぞれ y_t がどのような値か説明しているけど説明の仕方が違うよね。前者は「前のステップの値 y_{t-1}\phi 倍に w_t を足したものです」と説明しているけど、後者は前のステップの値とか最近のステップの値とかつかわずに「一番最初の y_{-1}\phi^{t+1} をかけたものに  \sum_{\tau = 0}^t \phi^{t-\tau} w_\tau を足したものです」といっているからね。前ステップの出力を用いる前者が Recurrent Neural Network 的で、前ステップの出力を用いない後者が Temporal Convolutional Network 的にもみえる(もし2つ以上前のステップの値にも依存する差分方程式だったら RNN 的にはならないけど)。

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

いや、後者の説明の仕方のほうがだいぶ面倒ではないですか? 「前のステップの値 y_{t-1}\phi 倍に w_t を足したものです」の方が簡潔ですよね? 唐突に (2.2.3) 式を持ち出してきた意義がよくわかりません。

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

前者が簡潔にみえるのはこの差分方程式が前者が簡潔になるものだからかな。それに、 (1 - \phi L)y_t = w_t という時系列 \{y_t\} の性質を調べるのに、(1 - \phi L) というオペレータの逆数のようなオペレータがあったら便利そうだよね。…もし |\phi| < 1y_{-1} が有限の値だったら、t \to \infty \phi^{t-1} y_{-1} \to 0 だから、大きな t で以下の1行目が成り立つ。ということは、大きな t で以下の2行目も成り立つ。

 \begin{split} (1 - \phi^{t+1} L^{t+1})y_t & \approx y_t \\ (1 + \phi L + \phi^2 L^2 + \cdots + \phi^t L^t)(1 - \phi L)y_t & \approx y_t \end{split}
さらに、どの y_t も有限の値をもつ( bounded である)と仮定する。このとき上の2行目から、「オペレータ (1 - \phi L) を適用してオペレータ  (1 + \phi L + \phi^2 L^2 + \cdots + \phi^t L^t) を適用することは何もしないことと同じである」といえるよね(オペレータの順序は逆でもいい; もし bounded でなかったらこのようなオペレータの分解はできない、不定形になっちゃってるかもだから)。だったら、以下のようなオペレータを考えることができる(これは定義だと思うからイコールではなくあえて \equiv にしてみたよ)。
 (1 - \phi L)^{-1} \equiv \lim_{j \to \infty} (1 + \phi L + \phi^2 L^2 + \cdots + \phi^j L^j) \tag{2.2.8}
このオペレータ (1 - \phi L)^{-1} は、(1 - \phi L) と合わせて適用すると何もしないことになるようなオペレータだ。…これを利用すると、以下のような時系列 \{y_t\} があるとき、
 (1 - \phi L)y_t = w_t
|\phi| < 1 かつ \{y_t\} が bounded だったら( \{y_t\} がな場合は定常だったら)、(1 - \phi L)^{-1} というオペレータが定義されるのでこれを両辺にかけて、
 y_t = (1 - \phi L)^{-1} w_t
が成り立つ。つまり、以下が成り立つ。
 y_t = w_t + \phi w_{t-1} + \phi^2 w_{t-2} + \phi^3 w_{t-3} + \cdots \tag{2.2.9}
\{y_t\}, \{w_t\} が確率的だったら、この式を使えば \{w_t\} の分布から \{y_t\} の分布が出るんじゃないかな。

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

うーん…逐次的に y_t の実現値を求めたいとかではなくて y_t の定常分布を知りたいとかならその (2.2.9) 式が便利かもしれないですね。しかし、\{y_t\} が bounded とか定常とかでなかったら駄目なんですか? だって、その式の両辺に (1 - \phi L) をかければ  (1 - \phi L)y_t = w_t になるので (2.2.9) 式はいつでも正しいのではないですか?

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

(2.2.9) 式が  (1 - \phi L)y_t = w_t 式を満たすのはいつでも正しいよ。その逆が真じゃない。(2.2.9) 式の右辺に a_0 \phi^ta_0 は任意の定数)を足したものだって  (1 - \phi L)y_t = w_t を満たすからね。だから一般には (1 - \phi L)^{-1} というオペレータが定まってない。でも、\{y_t\} が bounded とか定常という条件が課されていればこの a_0 \phi^t の項は a_0 = 0 でないといけない。でないと、|\phi| < 1 なら t \to -\infty にしたときこの項(の絶対値)は発散しちゃうから、という説明だけど…結構違和感あるな…オペレータ (1 - \phi L)^{-1} を定義したときに t \to -\infty の側の極限の議論なんてしてないし…a_0 = 0 という要請は t \to -\infty で発散してしまうからではなくて単に初期条件としてそうすべきって話じゃないのかな…。

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

面倒なので次節に行きましょう。今度は2次の差分方程式 (1 - \phi_1 L - \phi_2 L^2) y_t = w_t になりました。それでこれを (1 - \lambda_1 L)(1 - \lambda_2 L) y_t = w_t因数分解しようとしてますね。\lambda_1, \lambda_2 を求めるには式 (2.3.5)z の方程式と考えて解けばいいです。解が \lambda_1^{-1}\lambda_2^{-1} になります。\lambda_1, \lambda_2 は1章で出てきた行列 (2.3.17)固有値でもあります…いやまあそうなんですけど、だから何というか…。

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

結局 \lambda_1, \lambda_2 の絶対値が1より小さいとき時系列は定常になるんだよね。1章と2章はAR過程が定常になる条件を異なるアプローチで求めてるんじゃないかな。1章では「繰り返し掛け算するのはどんな行列だろう?」って発想で、\lambda_1, \lambda_2 はその行列の固有値って形で出てきた。繰り返し掛け算する行列の固有値の絶対値が1より小さくないと任意の時刻の平均が等しくはならないよね。発散か振動していって平均が移動していっちゃうから。他方、2章では「ノイズ(\{w_t\})の式で表すとどうなるだろう?」って発想で、ノイズの係数として \lambda_1^t, \lambda_2^t が出てきたのかな。これも絶対値が1より小さくないといずれ発散か振動して困る。2章の発想はAR過程をMA(∞)過程でかき直したともいうかな。

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

急にめちゃくちゃ沖本本参照しないでください…。

その2があればつづく

雑記: ネイマン-ピアソンの補題とカーリン-ルビンの定理

参考文献
  1. 日本統計学会公式認定 統計検定1級対応 統計学 | 二宮嘉行, 大西俊郎, 小林 景, 椎名 洋, 笛田 薫, 田中研太郎, 岡田謙介, 大屋幸輔, 廣瀬英雄, 折笠秀樹, 日本統計学会, 竹村彰通, 岩崎学 |本 | 通販 | Amazon
  2. ネイマン・ピアソンの補題 - Wikipedia
  3. probability - Proof of Karlin-Rubin's theorem, detail about a real analysis fact. - Mathematics Stack Exchange
  4. https://www.soph.uab.edu/sites/edu.ssg/files/People/KZhang/BST695-11Fall/BST695-2011-Fall-Chapter-08.pdf

参考文献1. の93、94ページに「ネイマン-ピアソンの基本定理」と「単調尤度比と一様最強力検定」がありますが、証明がなかったので、前者は参考文献2. を、後者は参考文献3. にリンクがあった参考文献4. を参考にかきました。ただ後者の証明はだいぶ自分でかいたのでおかしい点があるかもしれません。私の誤りは私に帰属します。お気付きの点がありましたらコメントでご指摘いただけますと幸いです。

ネイマン-ピアソンの補題
X を確率変数(または確率変数ベクトル)、 f(x;\theta)X確率密度関数X が離散型の場合は確率質量関数)とし、帰無仮説\theta=\theta_0 とし、対立仮説を \theta=\theta_1 とする。このとき、もし以下のような検定 \delta の第一種の誤りの確率が \alpha であれば、この検定 \delta有意水準 \alpha の検定の中で最強力検定である。
検定 \delta X の実現値 x に対して、
  • f(x;\theta_1)/f(x;\theta_0) > c ならば、帰無仮説を棄却する。
  • f(x;\theta_1)/f(x;\theta_0) = c ならば、X とは独立に (0,1) 区間の一様分布にしたがう確率変数 Y の実現値 y を生成して、
  • f(x;\theta_1)/f(x;\theta_0) < c ならば、帰無仮説を棄却しない。
証明のイメージ
f:id:cookie-box:20200322115905p:plain:w480
証明
検定 \delta の棄却域を  R_\delta とする。示すべきことは、任意に取ってきた有意水準 \alpha の検定 \delta' (棄却域 R_{\delta'} )に対して、以下が成り立つことである。
{\rm P}(X \in R_\delta \, | \, \theta = \theta_1) \geqq {\rm P}(X \in R_{\delta'} \, | \,  \theta = \theta_1)
ここで、任意の \theta に対して以下が成り立つことから、
 \displaystyle {\rm P}(X \in R_\delta \, | \, \theta)    = {\rm P}(X \in R_\delta \cap R_{\delta'} \, | \,  \theta) + {\rm P}(X \in R_\delta \cap R_{\delta'}^C \, | \,  \theta)
 \displaystyle {\rm P}(X \in R_{\delta'} \, | \, \theta) = {\rm P}(X \in R_\delta \cap R_{\delta'} \, | \,  \theta) + {\rm P}(X \in R_\delta^C \cap R_{\delta'} \, | \,  \theta)
示すべきことは以下のようにかきかえられる。
 {\rm P}(X \in R_\delta \cap R_{\delta'}^C \, | \,  \theta = \theta_1) \geqq {\rm P}(X \in R_\delta^C \cap R_{\delta'} \, | \,  \theta = \theta_1)
これは以下のように示される(離散型の場合は \int\sum にする)。
 \displaystyle \begin{split} {\rm P}(X \in R_\delta \cap R_{\delta'}^C \, | \,  \theta = \theta_1) &= \int_{R_\delta \cap R_{\delta'}^C} f(x;\theta_1) dx \\ &\geqq c \int_{R_\delta \cap R_{\delta'}^C} f(x;\theta_0) dx \\ &= c {\rm P}(X \in R_\delta \cap R_{\delta'}^C \, | \,  \theta = \theta_0) \\&\geqq c {\rm P}(X \in R_\delta^C \cap R_{\delta'} \, | \,  \theta = \theta_0)  \\ &= c \int_{R_\delta^C \cap R_{\delta'}} f(x;\theta_0) dx \\ &\geqq \int_{R_\delta^C \cap R_{\delta'}} f(x;\theta_1) dx \\&=  {\rm P}(X \in R_\delta^C \cap R_{\delta'} \, | \,  \theta = \theta_1) \end{split}
ここで、1行目→2行目、3行目→4行目、5行目→6行目の式変形には以下を用いる。
  • 検定 \delta の棄却域  R_\delta は以下である。よって、この領域内では f(x;\theta_1) \geqq c f(x;\theta_0) が成り立つ。
     \displaystyle R_\delta = \left\{ x \, \middle| \, \frac{f(x;\theta_1)}{f(x;\theta_0)} > c\right\} \cup \left\{ x \, \middle| \, \frac{f(x;\theta_1)}{f(x;\theta_0)} = c \, \land \, y < r \right\}
  • 有意水準 \alpha の検定(つまり、第一種の誤りの確率が \alpha 以下の検定)\delta' を任意に取ってきて、その棄却域を R_{\delta'} とすると、以下が成り立つ。
     \displaystyle \alpha = {\rm P}(X \in R_\delta \, | \, \theta = \theta_0) \geqq {\rm P}(X \in R_{\delta'} \, | \,  \theta = \theta_0)
    よって、以下が成り立つ。
     {\rm P}(X \in R_\delta \cap R_{\delta'}^C \, | \,  \theta = \theta_0) \geqq {\rm P}(X \in R_\delta^C \cap R_{\delta'} \, | \,  \theta = \theta_0)
  •  R_\delta の外では f(x;\theta_1) \leqq c f(x;\theta_0) が成り立つ。
カーリン-ルビンの定理
X を確率変数(または確率変数ベクトル)、 f(x;\theta)X確率密度関数X が離散型の場合は確率質量関数)、\theta を1次元のパラメータとする。また、任意の \theta_1 < \theta_2 について、尤度比 f(x;\theta_2)/f(x;\theta_1) が、ある統計量 T(x) と広義単調増加関数  g(T(x); \theta_1, \theta_2) を用いて、
 \displaystyle \frac{f(x;\theta_2)}{f(x;\theta_1)} =  g(T(x); \theta_1, \theta_2)
とかけるとする(≡ T(x) に関して単調尤度比をもつ)。このとき、帰無仮説\theta \leqq \theta_0 であり対立仮説が \theta > \theta_0 である検定問題を考える。もし以下のような検定 \delta\theta = \theta_0 のときの棄却の確率が \alpha であれば、この検定 \delta有意水準 \alpha の検定の中で一様最強力検定である。
検定 \delta X の実現値 x に対して、
  • T(x)> c ならば、帰無仮説を棄却する。
  • T(x) = c ならば、X とは独立に (0,1) 区間の一様分布にしたがう確率変数 Y の実現値 y を生成して、
  • T(x) < c ならば、帰無仮説を棄却しない。
証明
検定 \delta の棄却域を  R_\delta とする。示すべきことは、一つは、\theta_{-1} < \theta_0 である任意の \theta_{-1} について以下が成り立つ(棄却の確率が \alpha 以下である)ことである(そもそもこの検定 \delta有意水準 \alpha の検定である)。
 \alpha = {\rm P}(X \in R_\delta \, | \, \theta_0) \geqq {\rm P}(X \in R_\delta \, | \,  \theta_{-1}) \qquad \forall \theta_{-1} < \theta_0
もう一つは、\theta_1 > \theta_0 である任意の \theta_1 と任意に取ってきた有意水準 \alpha の検定 \delta' (棄却域 R_{\delta'} )について以下が成り立つことである(一様最強力検定である)。
{\rm P}(X \in R_\delta \, | \, \theta_1) \geqq {\rm P}(X \in R_{\delta'} \, | \,  \theta_1) \qquad \forall \theta_1 > \theta_0

ここで、\theta_{-1} < \theta_0 である任意の \theta_{-1} を一つとって、帰無仮説\theta=\theta_{-1}、対立仮説を \theta=\theta_0 とし、検定 \delta をする。g は広義単調増加関数なので、T(x)>c という条件は g(T(x); \theta_{-1}, \theta_0) >g(c; \theta_{-1}, \theta_0) \equiv k にかきかえることができる。つまり、f(x;\theta_0)/f(x;\theta_{-1}) > k とかきかえることができる。よって、ネイマン-ピアソンの補題より、検定 \delta有意水準 {\rm P}(X \in R_{\delta} \, | \, \theta_{-1}) \equiv \alpha_{-1} の最強力検定であり、その検出力は {\rm P}(X \in R_{\delta} \, | \, \theta_0) = \alpha である。ところで、x の実現値にかかわらず確率 \alpha_{-1}帰無仮説を棄却する検定 o有意水準  \alpha_{-1} の検定であり、その検出力は \alpha_{-1} だが、検定 \delta有意水準  \alpha_{-1} の最強力検定であることから、\alpha \geqq \alpha_{-1} \; \Leftrightarrow \; \alpha \geqq {\rm P}(X \in R_{\delta} \, | \, \theta_{-1}) が成り立たなければならない。これは任意の \theta_{-1} < \theta_0 について成り立つ。

次に、\theta_1 > \theta_0 である任意の \theta_1 を一つとって、帰無仮説\theta=\theta_0、対立仮説を \theta=\theta_1 とし、検定 \delta をする。上と同様に議論により、検定 \delta有意水準 {\rm P}(X \in R_{\delta} \, | \, \theta_0) \equiv \alpha の最強力検定である。これは任意の \theta_1 > \theta_0 について成り立つ。ので、検定 \delta帰無仮説 \theta=\theta_0、対立仮説 \theta > \theta_0 に対する有意水準 \alpha の一様最強力検定である。他方、帰無仮説\theta \leqq \theta_0 にすることは有意水準に影響を及ぼさない(第一種の誤りの確率が大きくなることはない)。したがって結局、検定 \delta帰無仮説 \theta \leqq \theta_0、対立仮説 \theta > \theta_0 に対する有意水準 \alpha の一様最強力検定である。

素朴には「帰無仮説が正しいならばまれなこと」が起きたときに帰無仮説を棄却しますが、いったいどこを囲んで「まれなこと」としてぬりつぶすべきかは本当は帰無仮説だけみつめていてもよくわかりません。渡辺ベイズ本の6章の章末にも「『りんごとXのどちらが好きですか? Xはわかりません』という質問にあなたは答えられますか?」という問いがあった気がします。いま渡辺ベイズ本が手元にありません。

帰無仮説を棄却することで支持したい対立仮説があればもっとはっきりします。「1の出る目が1/6だという帰無仮説を立てる(内心、1の出る目がそれより高いと思っている)」というのだったら、サイコロをn回投げて1の目が出た回数が閾値より大きいことを「まれなこと」として、このときに帰無仮説を棄却すればいいです。閾値は、帰無仮説が正しいにもかかわらず帰無仮説を棄却してしまう確率がある値以下になるように決めます(この値を有意水準といい、よく 0.05 などにされます)。

しかし、こうしてつくった検定は、帰無仮説が正しいときに誤る確率が有意水準以下であることは保証されているものの、帰無仮説が正しくないときに帰無仮説をいい感じに棄却してくれるのかはわかりません。例えばあなたはうっかりしていて、帰無仮説を棄却することで1の出る目が1/6よりも大きいことを示したいのに、1の目が出た回数が閾値以下のときに帰無仮説を棄却するというとんちんかんな検定をつくってしまうかもしれません。こんな検定は有意水準が 0.05 であっても、あなたが思い描く対立仮説を検出する力はほとんど皆無です。

なのでネイマンさんとピアソンさんは、「『1の目の出る目が1/6』という帰無仮説と『1の出る目が1/3』という対立仮説を検定したいなら、後者÷前者の尤度比が閾値以上のときに棄却するのが同じ有意水準の検定の中では最強ですよ」といいました(いったかはわかりません)。これが最強なのは上の図から明らかです。もし有意水準が同じである他の検定があったとしても、棄却域の差の部分で絶対勝てるのです。こっちは尤度比が閾値以上かどうかで棄却域を囲っていますので。そもそも内心では後者なのではないかと疑っているときに、後者÷前者の尤度比を基準に棄却域をつくるべきなのは当然です。# なお、「1の目が出た回数」が閾値より大きいかどうかで検定すると尤度比検定になっています。

また、尤度比がある統計量の広義単調増加関数になっていれば、「『1の目の出る目が1/6』という帰無仮説と『1の出る目が1/3』という対立仮説」から「『1の目の出る目が1/6以下』という帰無仮説と『1の出る目が1/6を超える』という対立仮説」に広げることができます。1/6 とそれより小さい任意の p との間、1/6 とそれより大きい任意の p との間にネイマン-ピアソンの補題がつかえるからです。

論文読みメモ: An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling

以下の論文を読みます。

Shaojie Bai, J. Zico Kolter, Vladlen Koltun. An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling. arXiv:1803.01271, 2018. [1803.01271] An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling
まとめ
  • 近年の CNN の系列データへの適用事例に着想を得て、シンプルで汎用的な TCN( Temporal Convolutional Networks )を提案した。TCN は再帰構造をもたず(スキップ付きの)畳込みのみで現時点までの入力から現時点の出力を生成する。
  • 11種類の系列データに対するタスク(人工的なタスク、曲に対する予測、文字/単語に対する予測)のほとんどで、TCN は同一モデルサイズ(パラメータ数だと思う)の LSTM、GRU、vanilla RNN よりも高い性能を発揮した。
  • 系列データへのファーストトライアルは RNN 系のニューラルネットに代わって TCN とすべきである。
所感
  • 検証されているタスクの半分が言語データに対するタスクであり、むしろ実際に予測タスクの需要があると考えられる経済データや自然データなどでの検証はなされていない点が気になった。
  • 推論時にその時点までの全データを参照する TCN が長期記憶性で有利なのは当然のようには感じる(というかそれは記憶なのだろうか)。RNN は過去の入力データを保持しない代わりに現時点までの特徴にバックアップしており、RNN と TCN のどちらを採用するか(どう組み合わせるか)は推論時に使用できるメモリサイズに依存しそう。
  • 確かに最初から再帰構造縛りでモデリングする意味はわからないので、現実に系列データをニューラルネットで学習するのはまず利用できるメモリサイズで TCN する方が適当なように思う。
※ キャラクターは架空のものです。私の誤りは私に帰属します。お気付きの点がありましたらコメントでご指摘ください。
f:id:cookie-box:20200101101603p:plain:w60

「系列データに対する様々なタスクにおいて、単純な畳込みニューラルネットの方が伝統的な再帰ニューラルネットより効果的だったので、系列データのモデリングのファーストトライアルは再帰ニューラルネットではなく畳込みニューラルネットに改めるべきだ」というようなアブストラクトですね。なぜ単純な畳込みニューラルネットの方が効果的なんでしょうか? どんなモデルでどんなタスクを検証したのでしょう?

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

確かにどんなタスクを調べたのか気になるね。4節に「系列データのモデリングのタスク」ってまとめられてるのがそれかな。RNN アーキテクチャの性能比較によく使われるタスクを集めたみたい。

The adding problem そのまま「足し算」かな。以下のような2次元系列が入力で、第2成分がマーカーになっていて、マーカーが付いた数字を足し算しろというタスクだね。
f:id:cookie-box:20200228194641p:plain:w360
LSTM の原論文( https://www.bioinf.jku.at/publications/older/2604.pdf )が初出で、LSTM の登場より前の RNN では解けなかったとある。確かに入力系列の長さが自在に調節できるし、長期記憶性を測るのにうってつけって感じがするかも。「あてずっぽうに予測値を 1.0 にすると MSE が 0.1767 になる」ってあるけど、第1成分を [0,1] の一様乱数から生成するなら以下より MSE は 1.667 になるんじゃと思うんだけど誤植なのかな…?
 \displaystyle \int_{x=0}^1 \int_{y=0}^1 (1 - x - y)^2 dx dy = \frac{1}{6}
Sequential MNIST and P-MNIST MNIST は 28×28=784 ピクセルのグレースケール手書き数字画像だけど、それを長さが 784 の系列データとして入力して分類しろってタスクか…画像は縦と横の広がりがある2次元のデータなのに1次元にして判別しろっていうのも意地悪だな…。
f:id:cookie-box:20200315171206p:plain:w500
それで P-MNIST っていうのはさらにこの長さ 784 の系列データをランダムに並び替えるらしい。全ての訓練データ、テストデータに対して並び替え方は同じだと思う。これは、単に画像データを1次元の系列に解きほぐしたのでは元画像における右隣・左隣のピクセルはまだ隣り合ったままだけど、その横方向のつながりをもぶち壊すために permutation したってことだよね。ますます意地悪だな…。そもそも現実にありうる系列データのパターンに対する性能が大事なのに、系列データに対するファーストトライアルを提案する論文で意図的に自然なパターンをぶち壊していくのってどうなのかな…。
Copy memory これは下図のように「最初に入力した数字の列を覚えておいて、こちらが9を入力し始めたらその1ステップ後から出力すること」ってタスクだね。下図では4桁の数字を覚えさせているけど本当は10桁らしい。まあどうでもいいけど。出力させるまでに何ステップおくかもモデルの性能を測りたい人が適当に決めるんだろうね。
f:id:cookie-box:20200315173233p:plain:w540
JSB Chorales and Nottingham 「J. S. バッハのコラール」は382曲の4声コラール(賛美歌)が、88次元(ピアノの鍵盤数だよね)のベクトルの列で表されているっぽいね。ベクトルの各要素は0か1で、そのとき押されている鍵盤が1になっているっぽいけど、それだと「タンタン」と「ターーン」の区別付かないような…。あと4部合唱ということは同時に1になる成分は高々4つまでなのかな…ウィキペディアの画像をみてもこれ伴奏とかじゃなくて歌唱旋律だよね…まあどっちでもいいけど…。ノッティンガム」は1200曲のイギリス・アメリカのフォーク音楽のデータセットらしい。じゃあこれらのデータセットで何をするのかだけど、Greff 2017 では4分音符ごとの系列にした JSB Chorales に対して次のステップを予測する(このとき負の対数尤度を最小化することを目指す)というタスクになっているみたいだね。
PennTreebank これは言語データで、このデータで文字レベルの系列の学習も、単語レベルの系列の学習もやったらしい。
  • 文字レベルの系列としてみると、訓練データは 5059K 文字、バリデーションデータは 396K 文字、テストデータは 446K 文字含むらしい。"with an alphabet size of 50" ってのは何なんだろう。アルファベットは26文字だと思うんだけど…Miyamoto 2016 をみると、「10K の高頻度語、51 の高頻度文字にプリプロセスされている」とあるね。じゃあ 50 という数は単に決め打ったもので、26文字のアルファベットの他に記号とか文頭・文末のマーカーとかが含まれているのかな…?
  • 単語レベルの系列としてみると、訓練データは 888K 単語、バリデーションデータは 70K 単語、テストデータは 79K 単語含むらしい。
Wikitext-103 PTB より 110 倍大きいデータセットで、語彙サイズは 268K らしい。28K のウィキペディア記事(103M 単語)を訓練データに、60 の記事(218K 単語)をバリデーションデータに、60 の記事(246K 単語)をテストデータにしたらしい。PTB より代表的・現実的なデータセットで、レアな単語を含むのが特徴だとか。
LAMBADA 小説から 10K の節(それぞれの節が4.6 文のコンテキスト文と、1文のターゲット文からなる)を抜き出してきたデータセットみたいだね。ターゲット文の最後の単語が予測対象になるらしい。ターゲット文の最後の単語は、人間にとって、「コンテキスト文があると容易にわかるけどターゲット文だけ見てもわからない」ものになっているんだって。つまりモデルは長い文脈を捉える必要があって、色々なモデルが LAMBADA の予測に失敗しているんだって。LAMBADA タスクの訓練に用いたデータは(LAMBADA じゃないのか?)2662 の小説の全文で、200M 語以上あって、語彙数は 93K だって。
text8 PTB の 20 倍のサイズの、100M 文字を含むウィキペディア由来のデータセットで、文字レベルの言語モデリングに用いたらしい。90M 文字を訓練に、5M 文字をバリデーションに、5M 文字をテストにつかったみたいだけど、どんなデータなのか、文章や記事に区切られているのかとかよくわかんないな…。
…これらをみる限り、「人工タスク」「人工タスク」「人工タスク」「音楽タスク」「言語タスク」「言語タスク」「言語タスク」「言語タスク」だね。系列データってもっと、金融データとか、売上高データとか、気温や天候などの自然現象データとか、遺伝子データとか、色々あると思うんだけど…音楽や小説の次の内容なんかより売上高や天候の方が予測したいはずだし…。それに、言語タスクといっても次の語を予測とかじゃなくて翻訳やサマリーとかある(むしろそっちのが現実に需要がある)と思うし…。

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

確かに後半が言語データセットばかりですね…で、それらに対して再帰ニューラルネットと畳込みニューラルネットを適用した結果どうなったんです?

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

それが Table 1 かな。再帰ニューラルネット側は、LSTM、GRU、vanilla RNN を適用したみたいだけど、比較対象の TCN( Temporal Convolutional Networks )は3節のアーキテクチャを参照ってあるから3節「Temporal Convolutional Networks」を確認しようかな。TCN はこの著者の人たちが汎用的になるように設計したアーキテクチャみたいだけど、新しいものではないらしい。TCN という言葉自体も Lea 2017 に既に出てきているって。TCN は系列データの予測に用いるので、以下を満たすらしい。

  • 畳込み時に未来から過去へのリーケージがないようにする。
  • 任意の長さの入力系列を受け取って、同じ長さの系列を出力できる。
TCN は近年発表された畳込みニューラルネットによる系列データ学習(以下)に着想を得ているみたいだけど、よりシンプルで長期記憶性をもつようにしているみたいだね。まず 3.1 節で系列モデリングとは  L(y_0, \cdots, y_T, f(x_0, \cdots, x_T)) を最小化するような f を見つけることと定式化されている。
 \hat{y}_0, \cdots, \hat{y}_T = f(x_0, \cdots, x_T) \tag{1}
これで多くの系列データに対するタスクがカバーできるけど、翻訳などのような seq2seq タスクはカバーできないって。アウトプットの各データに全てのインプットを利用するからって。…じゃあ翻訳なんかはこのフレームワークに当てはまらないから対象外ってことなんだね。

それで CNN でどうやって系列データに対するタスクに取り組むのかって話だけど、過去を参照せずに入力系列と同じ長さの系列を出すには以下みたいに1次元の FCN にすればいい。

f:id:cookie-box:20200316170220p:plain:w160
FCN(fully-convolutional network)というのは全て畳込み層のみからなるネットワークのことで、画像内の物体認識とかで性能がいいみたいだね。ただ上図のアーキテクチャだと長記憶性をもたせるのに畳込みのフィルタを大きくするか、層数を増やさないといけなくて、あまり重いモデルになるとファーストトライアルに向かない。なので WaveNet よろしく dilated convolutions(下図)を採用する。これで飛躍的に過去のデータを反映できる。
f:id:cookie-box:20200316172603p:plain:w260
一応 dilated convolutions を定式化しておくと以下ね。d 個飛ばしに k 個のデータを取って、i 個目のデータには重み f(i) をかけるってことだね。
 \displaystyle F(s) = (x \ast_d f)(s) = \sum_{i = 0}^{k - 1} f(i) x_{s-di} \tag{2}
これにさらに Residual Connection と Weight Normalization が組み込まれているらしい。これらについては効果があることが実証されてきたって感じで、今回なんで組み込むのかの説明があんまりないかな…? 3節の最後にこの TCN の特徴が RNN と対比して以下のようにまとめられている。
  • ⭕ 並列に計算できる。
  • ⭕ 受容長さをフレキシブルに変更できる(RNN も多段にすれば達成できると思うけど…)。
  • ⭕ 勾配爆発/消失がない。
  • ⭕ 省メモリで訓練できる。
  • ❌ 逆にモデルの利用時には、データを順番に入力していけばいい RNN と違って全てのデータをメモリに載せないとならないので、メモリを食う。
  • ❌ 受容長さが短いドメインから長いドメインにモデルを転移させることができない。
最後のって逆に RNN でもできるのかな…まあ TCN だと原理上無限の過去までみているわけではなくてあるところで打ち切られてはいるけどね。

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

そうですね…今の文脈でいう「系列データに対するタスク」って「現在のステップまでのすべての入力を踏まえた出力を出す」ですが、「1つ前のステップにおける隠れ層の出力を利用しなければならない」なんてルールはないですから、RNN は縛りプレイしている気がします。かといって、この縛りを外すとたくさんのデータを保持しなければ推論できないですね。1つ前のステップまでの情報が1つ前のステップにおける隠れ層の出力に込められているわけではなくなってしまいますから…。

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

RNN の出力は「その時点まですべての系列の特徴を集約したもの」、TCN の出力は「その時点あたりの特徴を集約したもの」だよね。RNN に入力する系列は入力したらもう捨てていいけど、TCN に入力する系列は TCN に参照される可能性がある限り保持しないといけないから、TCN で長期にわたる特徴を捉えようとすることはできるけどメモリが大変で、なんかもうメモリとの相談だよね。もちろん両者を組み合わせることもできて、まさに以下の記事で参照している Lai 2018 は先に TCN して次に RNN してるね。

逆に先に RNN して 後から TCN することもできると思うけど、その時点までの特徴にされる前の生データの系列を参照したいなら先に TCN の方がよさそうかな。どれだけ過去の生データまで参照できるかはメモリとの相談になるけどね。そういう意味では、上のアーキテクチャってなんかごてごてした恣意的なものにみえるけど割と素直なものなのかも。

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

逆に RNN や dilated convolutions 以外に系列データを学習するニューラルネットアーキテクチャってないんですか? まあ極論をいえば全結合とかありますけど…。

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

CNN だって部分を取って全結合するみたいなもんだし…じゃあその部分をどう取るかとか、dilated convolutions のスキップ幅自体でも学習すれば?

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

面倒です。

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

じゃあなんで訊いたし…。

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

Table 1 の結果をみると全て TCN が優れていたということなのですかね。直感的に足し算タスクやコピーメモリータスクはそりゃ再帰させる特徴を経由しない方が有利だろうという気はします。モデルサイズでなく推論時の利用メモリをそろえないとフェアでない気がしますが…。6節の Conclusion には LSTM には最近よい正則化手法が提案されたという話題がありますね。TCN ももっと広まって多くの人に改良してほしいといった感じでしょうか。

おわり