2018-03-07

隼時系列本：ノート2

本読み

以下の本を読みます。

時系列分析と状態空間モデルの基礎: RとStanで学ぶ理論と実装
馬場真哉

プレアデス出版 2018-02-14
売り上げランキング : 7742

Amazonで詳しく見る by G-Tools

※ 以下、キャラクターが会話します。原作とは関係ありません。上の本からそれる話も多いです。誤りがあればご指摘ください。

前回：ノート1 ／次回：まだ

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

えーと、前回やったのは、時系列分析っていうのは時系列モデルを推定することで、時系列データには周期性とかの構造があって、第2部が具体的なモデル推定の手順か（前回の最後にジュンがちょっとしゃべっちゃってたけど…）。最初はまず定常過程の説明からで、平均と分散が時刻によらず一定で、自己相関も時点によらず時間差にのみ依存するのが定常過程で、そうじゃないのが非定常過程ね。でも非定常過程でも定常過程に変換できることがあるんだ。変換できる例が単位根過程？なんか変な名前…。

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

単位根過程は1階差分が定常過程になるような非定常過程のことですね。そのような名前である理由まではこの本には触れられていないようですが、自己相関を特徴付けるある方程式が1を解にもつことに由来していて…その方程式については後の方で出てくるようですね。

ふーん？ …なあジュン、38ページの (2-6) 式って「定数＋ホワイトノイズ」なの？「定数＋ホワイトノイズ－1時点前のホワイトノイズ」にみえるんだけど、「ホワイトノイズ－1時点前のホワイトノイズ」は「ホワイトノイズ」ってこと？

確認すればいいでしょう。「ホワイトノイズ－1時点前のホワイトノイズ」の平均が0なのは自明、分散は ${\rm Var}(\varepsilon_t - \varepsilon_{t-1}) = {\rm E} \bigl( (\varepsilon_t - \varepsilon_{t-1})^2\bigr) = {\rm E}(\varepsilon_{t}^2) + {\rm E}(\varepsilon_{t-1} ^2)= 2 \sigma^2$ なので時刻によらず一定ですね。1次の自己共分散は ${\rm Cov}(\varepsilon_t - \varepsilon_{t-1}, \varepsilon_{t-1} - \varepsilon_{t-2}) = {\rm E} \bigl( (\varepsilon_t - \varepsilon_{t-1})(\varepsilon_{t-1} -\varepsilon_{t-2})\bigr) = {\rm E}(\varepsilon_{t-1}^2 )=\sigma^2$ なので1次のみゼロではありませんが、時点によらず時間差のみに依存するので結局定常過程ですね。ならいいじゃないですか。

でもちょっと気になるじゃん。サポートページにコメントしといた…ら返信もらえた！

何やってるんですか…。

42ページからはARIMAモデル？まずはARモデル…AR(1) だったらある時点の値は1時点前の値で回帰されるってことか。これって、昨日の気温が暑かったから今日も暑い、みたいな表現ができるってことだよな。iid 系列よりこういうモデルの方が時系列モデルって感じがするかも。…あれ？ iid 系列は定常過程だったけど、ARモデルは定常過程なの？ Box-Jenkins 法ではまず定常過程にしてから色々なモデルを適用するんだよな。このARモデルもそんな風にしてから適用するモデルの例ってことは、定常過程ってこと？

44ページに、AR(1) の特別な場合について何て書いてあります？

えっと待って…係数が1のときランダムウォーク？ランダムウォークって AR(1) の特別な場合なんだ。ランダムウォークは非定常過程だから、あれ、ARモデルは非定常過程ってこと？？

とは限りません。一般の AR(1) の期待値、分散、自己共分散を考えてみましょう。AR(1) の一般形は $y_t = c + \phi_1 y_{t-1} + \varepsilon_t$ です。両辺の期待値をとると、 ${\rm E}(y_t) = c + \phi_1 {\rm E}(y_{t-1})$ になり、両辺の分散を取ると ${\rm Var}(y_t) = \phi_1 ^2 {\rm Var}(y_{t-1}) + \sigma ^2$ になりますね。もしこれが定常過程であれば、 ${\rm E}(y_t) = {\rm E}(y_{t-1}) = \mu, \; {\rm Var}(y_t) = {\rm Var}(y_{t-1}) = \gamma$ ですが、 $|\phi_1| < 1$ のとき $\mu = c / (1 - \phi_1), \; \gamma =\sigma^2 / (1 - \phi_1^2)$ はこれを満たしますね。このとき自己共分散はどうでしょうか。 $k$ 次自己共分散は ${\rm Cor}(y_t, y_{t-k}) = {\rm Cor}(\phi_1 y_{t-1} + \varepsilon_t, y_{t-k}) = \phi_1 {\rm Cor}(y_{t-1}, y_{t-k}) = \phi_1^2 {\rm Cor}(y_{t-2}, y_{t-k}) = \cdots = \phi_1 ^k \gamma$ となります。これは時点に依存しませんので、定常過程です。つまり、AR(1) は $|\phi_1| < 1$ ならば定常過程になりえます。逆に $|\phi_1| < 1$ ならば期待値や分散は上の値に収束し、結局必ず定常過程になるのですが。

ARモデルが定常か非定常かは係数によるってことか…なんか面倒だな。定常データのモデリングにつかうつもりなら、もう $|\phi_1| < 1$ ってことに最初から決めておけばよくない？

1次のARモデル AR(1) の場合はそれでよいんですが…2次以上になると係数への制約をそう簡単に書き下せないんです。先ほどの AR(1) の $k$ 次自己共分散は、 $k-1$ 次自己共分散と ${\rm Cor}(y_t, y_{t-k}) = \phi_1 {\rm Cor}(y_{t-1}, y_{t-k})$ という関係が成り立っていましたよね。もっと一般に、p次のARモデル AR(p) の $k$ 次自己相関 $\rho_k$ について、 $\rho_k = \phi_1 \rho_{k-1} + \phi_2 \rho_{k-2} + \cdots + \phi_p \rho_{k-p}$ が成り立つんです。この式は、 $\rho_k$ からはじめて順に $\rho_{k-1}, \, \rho_{k-2}, \, \cdots, \rho_{0}=1$ まで自己相関を紡いでいく漸化式と見做すことができるでしょう。この漸化式の特性多項式は $f(z) = 1- \phi_1 z - \cdots \phi_p z^p$ です。同じ式が本の50ページにありますね。 $\rho_k$ はこの特性多項式の $p$ 個の根を $-k$ 乗したものの線形和で書けるんです。漸化式は数学Bでやりましたよね？数列 $a_n$ の隣接3項間漸化式を特性多項式の根を用いて解くときに、 $a_n$ の一般形に根 $\alpha$ の $n$ 乗があらわれたのを思い出してください。ここでは（添え字の向きがややこしいですが） $\rho_{0} \propto \alpha^k \rho_{k}$ かつ $\rho_0 = 1$ なので $\rho_k \propto \alpha^{-k}$ ということです。ということは、もし根 $\alpha$ の中に絶対値が1以下のものが混じっていたら、 $k$ が大きくなるほど $\alpha ^{-k}$ が振動か爆発し、ARモデルは不安定になってしまいます。というわけで、特性多項式のすべての根の絶対値が1より大きいことが、ARモデルが定常である条件なんです。

…よくわかんないけど、ARモデルが定常になる条件が面倒なのはわかったよ…。

ちなみに、37ページで出てきた「単位根過程」の名前はこのARモデルの特性多項式の「根」に由来します。単位根過程はARモデルで表現したとき特性多項式の根の1つが1になるんです。これは定常過程の1階和分を取って特性多項式を確かめてみるといいと思います。例えば―

あー！それは置いとこう！なんか全然話進んでないし！本に戻ると、ARモデルとは別にMAモデルっていうのもあるって。これは…過去 q 時点のノイズで現時点の値を回帰するってことか。…でも、ARモデルも過去の値を通して過去のノイズが含まれているよな。どう違うんだろう？

…すみません、確かに脇道にそれ過ぎましたね。ARモデルとMAモデルの関係は49ページにありますね。AR(1) は実質 MA(∞) だと。だから、過去の実現値そのものと関係がありそうな時系列データなら、ARモデルが向いているでしょう。無理やり MA(q) モデルで推定すると、q を非常に大きくしなければならないでしょうから。逆にMAモデルをARモデルで表現するときは…この話は50ページにありますね。MAモデルは（同じ期待値、分散、自己相関をもつ過程が複数存在するのですが、その内「反転可能」といわれる1つの過程は）AR(∞) に書き直すことができます。なので、MAモデルから生成されたデータを無理やり AR(p) モデルで推定しても p が大きくなってしまい、よくないでしょう。ARモデルとMAモデルはどちらかがどちらかを兼ねるというわけにはなっていないんですね。

なるほど。47ページにはARモデルとMAモデルのコレログラムがある…これは、これ見てどう思えばいいの？

モデルを推定するのに、対象時系列データの自己相関や偏自己相関のコレログラムを眺めてモデル選択するのが伝統的な手順だったんです。しかしこの本は、そう教えていませんね。そのようなコレログラムの観察は、計算資源が乏しかった頃の「古い同定の手順」だと60ページに。ただ、伝統的な手順にならえば…例えばハヤトが分析したい対象時系列データの標本自己相関をコレログラムにプロットしたところ、2次以降の自己相関がほとんどゼロだったとします。ARモデルとMAモデルのどちらを適用したいですか？

自己相関？って偏自己相関じゃない方だよな？ 47ページだと ACF っていうグラフの方…がすぐにゼロになっているのは…MAモデルの方？

ええ、逆に偏自己相関の方がすぐにゼロになっていたらARモデルを適用、という具合です。MA(q) は q+1 次以降自己相関をもちません。AR(p) は p+1 次以降偏自己相関をもちません。しかし、MA(q) は AR(∞) なので無限に偏自己相関をもち、AR(p) は MA(∞) なので無限の自己相関をもつんですね。

ARモデルとMAモデルってそういう違いがあるのか。それで、両方を組み合わせたのがARMAモデルで、ARIMAモデルというのは、何度か差分を取ってからARMAモデルを適用するってことか。54ページからのSARIMAモデルは、季節成分を考慮したARMAモデル…え、(2-39) 式って何これどうなってんの？？

落ち着いてください。例えば SARIMA(0,0,1)(0,0,1)[12] を考えてみましょう。このとき、(2-39) 式は、 $y_t = \theta(B) \Theta(B) \varepsilon_t = (1+\theta_1 B)(1+\Theta_1 B^{12}) \varepsilon_t = (1 + \theta_1 B + \Theta_1 B^{12} + \theta_1 \Theta_1 B^{13} ) \varepsilon_t$ ですから、ラグ演算子 $B$ を用いずに書けば、 $y_t = \varepsilon_t + \theta_1 \varepsilon_{t-1} + \Theta_1 \varepsilon_{t-12} + \theta_1 \Theta_1 \varepsilon_{t-13}$ ということです。

なんだそういうことか…じゃあ、SARIMA(0,0,1)(0,0,1)[12] は、1時点前のノイズに依存していてその係数が $\theta_1$ で、12時点前のノイズにも依存していてその係数が $\Theta_1$ で、13時点前のノイズにも依存していてその係数が $\theta_1 \Theta_1$ なのか…。なんか13時点前って気持ち悪くない？「1時点前」はさっきのノイズへの依存って感じで、「12時点前」は昨年のこの月のノイズへの依存って感じでわかりやすいけど、「13時点前」ってさあ…。

昨年のこの月の影響を織り込み済みのノイズ「 $\varepsilon_t + \Theta_1 \varepsilon_{t-12}$ 」を新たに「 $\tilde{\varepsilon_t}$ 」とみなしてこれで MA(1) を適用するって考えればいいんじゃないでしょうか。

あー確かに。SARIMAモデルって（月ごとに値がある周期12の時系列だったら）こんな感じなのかな？

必要ならデータ全体を前年同期との（D階）差分にする。
必要ならデータ全体を前月との（d階）差分にする。
同じ月の系列「2000年1月の値、2001年1月の値、2002年1月の値、…」を説明する ARMA(P, Q) モデルを決める（但し、どの月も同一のモデル）。
さっきの ARMA(P, Q) での過去のノイズへの依存も含めたノイズを新しい「現時点のノイズ」とみなし、過去の値への依存も含めた値を新しい「現時点の値」とみなし、ARMA(p, q) を適用する。

でもこれってなんかパラメータ多いけど、同じ期待値や自己相関をもつ過程が1つに決まるのかな…。

SARIMA が実装されているパッケージでは上手くやっているんじゃないでしょうか…。

第2部の4章の最後は、ARIMAXモデル…これはイベントの影響を考慮することができるモデルで…ダミー変数って何？過去の値とか過去のノイズだけじゃなくて、こういうのにも依存していいの？

そうですね、 $y_t$ が各日のドーナツ屋の売上高だったとしたら、よりよく推定するために、売上高以外にも日ごとの情報を色々追加してしまおうということですね。 $x_{k, t}$ は「その日が平日か休日か」「その日が晴れか雨か」「その日に近くでコンサートがあるか」などがありえると思います。しかし、「平日」も「休日」も数字ではありません。そこで仮に「平日＝0」「休日＝1」などと適当な数字を割り当ててしまいます。これがダミー変数です。

（ノート3があれば）つづく

2018-03-05

隼時系列本：ノート1

本読み

以下の本を読みます。

※ 以下、キャラクターが会話します。原作とは関係ありません。内容の誤りは本ブログ筆者に帰属します。

ジュン、忙しいところ悪いけど、この本一緒に読んでくれない？

何ですかハヤト…時系列分析？何だってそんな本読む気になったんです？

これ先月出た本なんだけど、表紙の絵がハヤブサで、通称「隼時系列本」っていうらしいんだ。それでプロデューサーが、「隼人が隼時系列本を読む」っていうネタを思いついちゃって…。

導入が雑すぎる…。

…それで読もうとしたんだけど、まずこれは何の本かを知らなきゃだろ？この本の正式なタイトルは「時系列分析と状態空間モデルの基礎」だけど、とりあえず「状態空間モデル」っていうやつの話は本の後半から始まるみたいだから置いといて、「時系列分析」って何かを読み取ろうと思ったんだ。そう思ってまえがきと目次をみると時系列分析とは何か1章に書いてあるらしいから1章を読んだんだけど、「時系列データ」っていうのは具体例から何となくイメージできたんだ。年ごとでも日ごとでも秒ごとでもいいから、一定の時間間隔ごとに1つずつ数字があればいいんだよな？毎月の売上金額とかって…。

ええ、一定の時間間隔ごとに1つずつ数字があればいいですね。もっとも、2つずつでも3つずつでもよいし、数字である必要もないですよ。1秒30フレームの動画があったとして、1フレームごとの静止画像を並べればこれも時系列データといえるでしょう。例えばある曲の1拍ごとのコード進行だって時系列データですよ。静止画像もコードも数字ではありませんけどね。まあ、静止画像もコードもどうにかすれば数値（のベクトル）に対応させることはできますから、時系列データという文脈では既に数字に変換されていることが想定されているとは思いますが。

ジュンの解説逆にややこしいんだけど…。でも、音楽も時系列なのか。なんか親近感湧いてきたな。けど、ここからが問題なんだよ…。時系列データを分析するっていう話になっていくと思うんだけど、最初に出てくる母集団やら母平均の推定っていう話がわからないんだ…。「日本人の身長の平均値」とかいう場合の平均ならわかるけどさ、「2000年1月1日の気温」に母集団も母平均も何もないだろ？「『2000年1月1日』が複数あれば異なる気温だったかもしれない」って言われても、別に複数ないし、あったとしても同じ気温にしかならないかもしれないし…。平均を推定するのが難しいって書いてあるけど、それ以前に平均なんてあるの？

…平均なんてあるのか、ですか。あるかどうかというよりは、あることにしたんです。その前後に「データ生成過程（DGP）」の話は出てきましたか？

あることにした？あ、DGPっていうのは次のページにある。

時系列分析をするときは「時系列データは確率変数列（データ生成過程＝DGP）から生成される」と仮定するんです。つまり、時系列データの各時点の値にはそれを生成する時点ごとの確率分布たちがある、ということにするんです。時系列分析の目的はこの確率分布たち＝DGPの生成過程＝時系列モデルを特定することです。いえ、もう少し正確にいうと、特定した時系列モデルによって「時系列データの将来の値を予測する」とか「複数の時系列を回帰分析する」とか、時系列データからもっと具体的な情報を引き出すことが最終的な目的ですね。逆に、目当ての具体的な情報を得る上では不要な部分を、確率的な揺らぎ＝ノイズとしたのです。本の25ページの言葉を借りれば「未来を予測する情報が含まれていない、純粋な雑音」ですね。ノイズを取り除いて、目的に沿う情報だけを取り出したいんです。確率的なゆらぎがあると決めているから、「『2000年1月1日』が複数あれば異なる気温だったかもしれない」ということになるんです。

ノイズがあると考えて目的の情報を取り出す…？うーん、でも、不要な部分を勝手に考えていいの？ある日の気温が10℃だったというのは、そういう情報じゃん。音楽も時系列って言ってたけど、俺たちの曲に不要な音なんてないだろ？

あくまである目的の上で不要、ですよ。そうですね…あるお店、ドーナツ屋でもいいです、ドーナツ屋が毎週の売上高の成長率をみて、来週の原材料の仕入れを判断しているとしましょう。このお店は売り上げが徐々に伸びていて、成長率の分、原材料を多く仕入れたいんですね。でも、今週はたまたま修学旅行生の集団がこの街にやってきて、ドーナツがとてもよく売れたんです。この週の成長率を参考に来週のために原材料を多く仕入れたら、来週はきっと原材料を余らせてしまうでしょう。あくまで来週の原材料を仕入れる上では、修学旅行生が来たことによる売上増加分はノイズだったんです。音楽でも、例えば4小節などでモチーフを反復する曲は多いでしょう？楽曲のこのような反復の周期を調べるには、4小節ずらして同じ曲を重ねたときに音の波形が重なるかを調べるかもしれません。このとき、モチーフに局所的に入れたアレンジは不要な情報になります。それは周期を調べる上でノイズというだけで、楽曲として不要な音というのではありません。

なるほど…わかってきた気がする。何か調べたいことがあって、それを調べる上で有用な部分と不要な部分に切り分けたいんだな。

もちろん勝手な切り分け方をしてよいわけではありません。有用な部分と不要な部分を切り分ける方法や、切り分け方が適切かどうかを調べる方法を、その本の続きが教えてくれるんでしょう。

でも、何を調べたいのかがまだよくわからないかも。だって、曲に何小節の周期があるかとか聞いて調べればよくない？

そうでしょうか。もしどんな周期性をもつ楽曲が流行するのかをリサーチしたいとして、調査対象が何百曲もあったら1つ1つ聞くのは大変です。楽曲データを入力するたけで判定するモデルがあれば便利だと思います。

あー確かに。

ただそれはあくまで例だったので…僕も詳しくありませんが、音楽データだったら、楽曲へのタグ付け、レコメンデーション、自動作曲などの研究が進んでいるのではないかと思います。「楽曲がどんなジャンルか判定したい」とか、「ある楽曲がある人にオススメできるか判定したい」とか、「勝手にコード進行と主旋律を決定してくれる時系列モデルがほしい」とかでしょうね（これらの目的で必ずしも音楽が時系列として扱われるかはわかりませんが…）。

えー自動作曲！？俺の仕事AIに奪われちゃう！

どうでしょう。確かにコード進行はカデンツのような雛形がありますし、自動作成しやすいと思います。でも、主旋律はもっと自由ですからね。もし本当にハヤトと同じように作曲できるAIをつくりたかったら、そのモデルにはハヤトの作曲の癖が全てプログラミングされていなければならないでしょうけど、そんなことが可能でしょうか。それに、いくらコードとメロディだけ魅力的に生成できても、歌詞やコンセプトがあっての楽曲です。細かなニュアンスを曲に反映するモデルはきっと容易ではないでしょう。作曲を完全に機械の仕事にするのはまだ難しいのではないかと思いますが…。

そっか、よくわかんないけどよかった！

いや僕も知りませんけど…本に戻りましょうか。

うん、時系列分析とは目的にあった時系列モデルを推定することってわかった。2章は時系列データの構造だって。自己相関とコレログラム？

4小節ごとにずっとモチーフを繰り返す楽曲なら、4小節ずらして重ねたときによく重なるということです。そのような曲について、1, 2, 3, 4, 5小節とずらしたときの重なりの度合いを棒グラフにして横に並べていったら、4のところの棒グラフは他より大きくなるでしょう。それがコレログラムです。

なるほど。次のページの外因性っていうのは、まさにさっきのドーナツ屋の修学旅行生のことだな。時系列データの構造って自己相関とかトレンドとか周期性なんだ。28ページの偏自己相関っていうのは自己相関とどう違うんだ…さっきの4小節ごとに繰り返す楽曲なら、8小節ずらしてもよく重なるから、本当に8小節で繰り返す周期性がどれだけあるかを知りたいときは、こっちの偏自己相関をみるってことか…。30ページはホワイトノイズと iid 系列？ホワイトノイズは iid 系列なの？そうじゃないの？

書いてあるように、もし毎時刻の確率分布が正規分布であるようなホワイトノイズであれば、iid 系列です。しかし、一般にはホワイトノイズが独立とは限りません。ホワイトノイズの定義は「毎時刻の期待値はゼロ、毎時刻の分散は一定、異なる時刻の自己相関はゼロ」というだけで独立は課していないんです。毎時刻が正規分布のホワイトノイズの場合は、自己相関がゼロというのが独立と同値になりますが。

じゃあここで iid 系列が出てきたのは何？単なる紹介？「独立性は厳しい仮定です」って言われても、「そっか厳しいんだ」って感じなんだけど…。

そうですね…iid 系列は時系列モデルの最も基本的なパーツとしてつかわれますし、（強）定常という重要な性質をもつので、ここで言及しているのでしょう。31ページで出てくるランダムウォークというモデルが、毎時刻 iid 系列である正規ホワイトノイズを足し上げていくようなモデルになっているでしょう？

iid 系列が重要なパーツになるのか…。でも iid 系列って「毎日サイコロを振った結果」みたいなもんだよな。なんか時系列データっぽくなくない？気温とか売上高とか音楽は、そういうんじゃないじゃん。前の時刻の値がどうだったかといまの値が関係あるよな、たぶん…。

分析対象の時系列データそのものの生成過程が iid 系列ということは少ないかもしれませんが、差分を取ったり、季節変動を除去したりしてデータを定常にしたらその生成過程は iid 系列に近くなるかもしれません。もし対象の売上高データが「『特定の季節変動＋特定のiidノイズ』を足し上げて生成されるもの」だとわかったらうれしいはずです。もう一期先の値の確率分布だってわかります。

差分を取ったりして、定常にする？

第2部 Box-Jenkins 法の内容になりますね。伝統的な時系列分析の手順である Box-Jenkins 法では、まずデータを定常過程に変換することを目指します。定常過程とは何かは35ページから説明がありますが、平均と分散が時刻によらず一定で、自己相関も時点によらず時間差にのみ依存するようなモデルを弱定常過程といいます。つまり、ホワイトノイズは弱定常過程です。自己相関にとどまらず同時分布の形状自体も時間差にのみ依存するようなモデルを（強）定常過程といいます。iid であれば（強）定常です。もっとも、この本では弱定常過程のことを定常過程、そうでない場合を非定常過程と呼んでいるので以降はこれにしたがいましょう。定常過程から生成したデータをプロットすると、ずっと同じ平均値の周りに、ずっと同じばらつきで推移します。他方、非定常過程であったら、平均や分散が拡大していくか、縮小していくか、波打ってしまいます。基本的に時系列モデルは、データを定常過程に変換した上でノイズを説明するように構築します。そのモデルからデータサンプルを生成するときは、ノイズを生成してから逆向きの変換をするんです。

（ノート2があれば）つづく

2018-02-10

雑記： 5次以上の方程式に解の公式が存在しない話

雑記

以下の話は厳密なものでも網羅的なものでもありません。キャラクターが登場しますが原作とは関係ありません。内容の誤りは筆者に帰属しますのでご指摘ください。

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

美希、最近仕事忙しそうだけど学校の勉強は大丈夫？

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

春香に心配されなくてもミキは成績いいの。それに今日は学校に顔出して、2次方程式の解の公式とか習ったの。解の公式があるなんて便利なの。これなら今後は何次方程式が出てきても全部パソコンとかにまかせて、ミキは寝てればいいの。あふぅ。

…美希、一応言っとくけど、5次以上の方程式に解の公式は存在しないよ？

え、そうなの？…でも、それっておかしいの。難しくてまだ公式をつくれてないだけかもなの。ないって言いきれないと思う。

ううん、言いきれるの。

なんで？

まず、解の公式って何かちゃんと決めておかなきゃだけど、 $n$ を1以上の整数として、 $n$ 次方程式 $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 =0 \; (a_n \neq 0)$ の解の公式とは、方程式に出てくる係数 $a_0, \cdots , a_n$ および（係数がつくる体と同じ体に属する）定数をつかった式で方程式の解をかきあらわしたものとする。ただし、この式でつかっていい演算は、足し算、引き算、割り算、掛け算、冪乗根（ルートを取るとか、3乗根をとるとか、もっと一般に $m$ を2以上の整数として $m$ 乗根をとるという操作のことね）に限るよ。あと、各演算をつかっていいのは有限回だけとするね。ちなみに、 $n$ 次方程式の解が複数ある場合は全部かきあらわさないと駄目だからね。 2次方程式の解の公式では $\pm$ で2つの解を1つの式にまとめているけど、こういう形にまとめないといけないってわけじゃないよ。

…まあそれはそれでいいの。2次方程式の解の公式も、係数 $a, b, c$ をつかって、足し算、引き算、掛け算（掛け算ができれば累乗もできるね）、割り算、ルートをつかって解をあらわしているの。

あと注意として、5次方程式の解の公式は存在しないけど、いつも係数で解がかけないってわけじゃないからね。例えば、 $a_5 x^5 -a_0 = 0$ という形の5次方程式だったら、 $x = \sqrt[5]{a_0 / a_5}$ が解の1つだとただちにわかるよね（これに1以外の1の5乗根をかければ5つの解が全てそろうね）。あと、係数の式で解がかけないというのは、解が存在しないという意味ではないことにも気を付けてね。係数の式で解がかけなくても解自体は存在するから、「5次方程式には解がない」というのは色んな意味で間違い。もっとも、中学校では複素数はまだ扱わないから、実数の範囲に解がないときには「解なし」という答え方をすると思うけど、5次方程式には実数解が必ず1つ以上あるしね。

「方程式の解が方程式の係数の式でかけるかかけないか」っていう問題なのはわかったの。でも、4次以下の方程式はかけるけど5次以上の方程式はかけないですとか、やっぱり変だと思うの。

まずちょっと準備として、（0で割ることを除いて）加減乗除について閉じている数の集合を体（たい）っていうんだ。例えば、実数どうしって足しても引いても掛けても割っても必ず実数になるよね。だから、実数全体は体になるんだ。他にも、有理数にだけ注目してもよくて、有理数どうしも加減乗除したら必ず有理数になるから、有理数も体なんだ。あと、高校では実数より広い複素数というのを習うけど、この複素数も体。体じゃない例としては、整数だけに注目するとこれは体じゃない。整数どうしを割り算すると整数じゃなくなっちゃうことがあるからね。それで、方程式の解って方程式の係数がつくる体に入っているとは限らない。美希が学校で習ってる2次方程式も、係数は有理数でも解は無理数になったりするよね？

無理数って $\sqrt{2}$ とかのこと？そーゆーのが解になる方程式なんかいっぱいあるの。 $x^2 = 2$ とか。

うんうん、2次方程式 $x^2 - 2 = 0$ を考えてみると、この方程式の係数は $a_2 = 1, \; a_1=0, \; a_0 =-2$ で、これらの加減乗除は有理数体 $\mathbb{Q}$ をつくるんだよね。それで、この方程式の解も同じ有理数体の中にいてくれたら、解を係数の加減乗除だけでかきあらわすことができる望みがある。でも、実際の解は $x=\pm \sqrt{2}$ で無理数だから有理数体の中にはいない。だから少なくともこの方程式は、係数の有限回の加減乗除だけでは解まで絶対たどり着けない。

体っていうのはまだよくわからないけど、 $1, 0, -2$ の有限回の加減乗除で $\sqrt{2}$ がつくれないのはわかるの。それが春香が言う「係数がつくる体に解が入ってない」ってことなのかもしれないけど、結局入ってないんじゃ駄目じゃん。それに、2次方程式にはちゃんと解の公式があるの。

加減乗除では解がつくれないと言ったけど、解の公式は加減乗除に加えて「冪根をとる」ってことができるんだよ。解の公式がかけるには、解が係数体に入っていないといけないってわけじゃないんだ。係数体 $K$ に含まれる適当な数に冪根をとったものを $K$ に加えて体を拡大して、そうしてできた新しい体 $K_1$ に含まれる数に冪根をとったものを加えてまた体を拡大して…、って繰り返しやっていって、体の中に解が含まれるまで拡大できればいいんだ。有限回の拡大でね。美希がさっき言った2次方程式 $x^2 = 2$ だと、解は $\pm \sqrt{2}$ だから、係数体 $\mathbb{Q}$ を $\mathbb{Q}(\sqrt{2})$ に拡大すれば解を含むようにできる。 $\mathbb{Q}(\sqrt{2})$ っていうのは、 $a, b$ を有理数として、 $a + \sqrt{2} b$ でかける数全体のことだよ。

春香、 $x^2 = 2$ の解は $\sqrt{2}$ と $-\sqrt{2}$ だけなの。 $a + \sqrt{2} b$ でかける数全部は要らないと思うの。

あ、体っていうのは、体の要素どうしを加減乗除しても体の要素じゃないと駄目なんだ（0で割るのは除いて）。有理数体 $\mathbb{Q}$ に $\sqrt{2}$ を加えた体をつくりたかったら、有理数と $\sqrt{2}$ を足し引きしたものは全てその体の要素なんだよね。もちろん、掛け算や割り算したものも体の要素だし、さらにそれらを加減乗除したものも体の要素だけど、それらは全て $a + \sqrt{2} b$ の形にかける。

あ、そういうことなの。ならいいの。でも、そんな体に広げて考えるなんて、なんか大げさなの。

大げさでいいんだよ。係数体や係数体を有限回何らかの冪根で拡大した体に解が入っていたら、ちゃんと求まるかどうかはともかく解の公式がかける可能性はある。有限回の加減乗除冪根の操作で解までたどり着けるってことだからね。逆に、係数体や係数体を有限回何らかの冪根で拡大した体に解が入っていなかったら、解の公式がかける可能性すらないんだよ。そして、5次以上の方程式には解の公式がかける可能性すらない。

…言いたいことは何となくわかったの。でも、そんなに体を広げて解が入っていないって言えるの？何回も足し算、引き算、掛け算、割り算、冪根をつかってよくても、解にたどり着けないものなの？解が入っていないですっていう証明なんて、できなさそうなの。なんか悪魔の証明？みたい。

そんなに手がかりがないわけじゃないよ。係数体を繰り返し拡大しても解にたどり着くことができないと直接示すのは確かに難しい。でも、係数体や係数体を拡大した体の中に解が入っているかどうかを問い掛けることができるツールがあるんだ。

そんなツールがあるの？でも春香、いまは目の前の体に解が入っているかどうか問い掛けたいんじゃなくて、これから体を何度拡大してもずっと解が入ることがないのかどうかが知りたいと思うんだけど…。

そこでなんと、このツールで解が入っているかどうか問い掛けた結果からは、その体を拡大した上で解が入っているかどうか問い掛けた結果がどうなるかも調べられるんだ。「解が入っています」という結果までたどり着くことはない、というのもわかっちゃう。

それはすごいの。どんなツールなの？

そのツールの名前はガロア群。ある方程式について、係数体の元を変えないような解の入れ替えの操作を全て集めると群の構造をしていて、これを方程式のガロア群というんだ。方程式のガロア群をとって、もしそれが単位群なら、それは「この体には解が全て入っています」ということ。単位群でなければまだ入っていない解があるから係数体を拡大する必要があるけど、拡大した体に解が入っているかどうかのガロア群をまたとるんだ（これはもう方程式のガロア群とはいわないけど同じように定義できるよ）。ただ、このときの拡大の仕方は適当に冪根を加えるのでは駄目で、元の係数体の係数をもつようなある多項式が1次式にまで因数分解できるようになるような拡大をしないといけないんだけど、この拡大の仕方は趣旨に合っているよね（そして、このような体の拡大をガロア拡大というよ）。そうやって係数体を拡大してガロア群を取り直すと、そのガロア群は元の方程式のガロア群の正規部分群になるんだ。さらに体を拡大してガロア群を取り直しても同じで、拡大する前のガロア群の正規部分群になる。特に、体に冪根を加えることによってガロア拡大するとき、拡大前後のガロア群の剰余群は巡回群になる。まとめると、元の方程式のガロア群に対して、剰余群が巡回群になるように正規部分群をとる操作を何度繰り返しても単位群にたどり着くことがないならば、係数体をどう拡大しても解を含む体にはならないということになる。

春香、待って、なんで解の入れ替えなんて話になったの？別に解を入れ替えたいわけじゃないと思うの。

「係数体の元を変えない解の入れ替え」を全て集めた群に注目すると、この群が係数体の拡大（ここでは、冪根を加えることによるガロア拡大）の前と後でどんな関係で結ばれているかがわかるんだ。つまり、後者は前者の「剰余群が巡回群になるような正規部分群」になっている。そして、この群が単位群になるまで係数体を拡大すれば解が含まれているといえる。体の拡大の前後の関係がわかって、最終目標までわかるんだよ。もし体の方だけ考えていたら、拡大したらどんな変化があるのかも、どこまで拡大したらよいのかもよくわからなかったからね。

あとその群って何？単位群とか正規部分群とか剰余群とか巡回群とかも、ミキ知らないし…。

まあ群は中学校で習わないからね（高校で習うとは言ってない）。その辺は置いといて結論を先に言うと、一般的な5次方程式のガロア群は5次対称群 $S_5$ という群になるんだけど、この $S_5$ は、「剰余群が巡回群になるように正規部分群をとる操作を何度繰り返しても単位群にたどり着くことがない」んだ。6次方程式以上も同様。

つづかない

2018-02-05

NIPS2017論文読みメモ： Tensorized LSTM（その3）

論文読み深層学習

以下の論文を読みます。

Zhen He, Shaobing Gao, Liang Xiao, Daxue Liu, Hangen He and David Barber. Wider and Deeper, Cheaper and Faster: Tensorized LSTMs for Sequence Learning. arXiv: 1711.01577, 2017. https://arxiv.org/abs/1711.01577

※ 以下、キャラクターが会話します。それぞれの原作とは関係ありません。内容の誤りは本ブログ筆者に帰属します。

前回：その2 ／次回：まだ

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

RNN は、ステップ毎に「前回の特徴＋今回の入力」を「今回の特徴」に変換することによって、ある系列の特徴を得ることを目指す。RNN層をスタックすれば特徴の特徴を得ることもできる。でも、層をスタックするほど実行時間も勾配消失（爆発）の危険も増大する。層を積み重ねずに深く特徴を抽出したいなら、ある層が抽出した特徴を次の層に渡すとき、次の時間ステップに渡すように歪めてしまう。つまり、「前回の浅い特徴＋前回の深い特徴」を「今回の深い特徴」にする。これによって、前回の浅い特徴から今回の深い特徴まで架け橋ができる。時間ステップが経過する度、特徴は深くなる。さらに、後ろの層の特徴を参照してもいい。表現力も増す。

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

前回はその Tensorized RNN まで用意できたよね。各層の隠れ状態を積み重ねたものを隠れテンソルとする。この隠れテンソルの更新をカーネルでの畳込みにより行うことでパラメータも節約できる。ただ、LSTM の機能をまだ実装できていない。LSTM は RNN に記憶セルとゲートを増設したものだから、記憶セルを設置して、各ゲート用のカーネルを用意するのじゃ駄目なのかな？

歪みのない Stacked RNN だったらそれでも大丈夫…。記憶セルは、時が流れても拡大も縮小もされない特徴を確保するための仕組み。時を遡っても誤差が拡大も縮小もされないことを保証する。でも、Tensorized RNN 上の誤差逆伝播では前のステップの同じ層にだけじゃない、前の層にも後ろの層にも誤差を伝播さなければならない…。

それはそうだけど…記憶セルのお陰で勾配消失（爆発）の懸念は払拭されたんじゃ…あ、伝播に支障をきたすのはもしかして重み係数のコンフリクトの方？

うん。再帰構造を含むニューラルネットには、時間ステップ毎に受け取りたい入力がきたり受け取りたくない入力がくるから、重み係数のコンフリクトの心配が付きまとう。だから受け取りたいときだけ受け取れるように Input Gate で制御する。でも、Input Gate が制御しているのは「記憶にどのように加算するか」…加算だけでは制御できているとはいえない。次の時間ステップにかけて層をクロスした斜め方向にも情報は流れる。この斜めのフローも、ゲート開閉を制御したい？

何となくわかった…でも、記憶セルの更新時に斜め方向への情報は移動しないよね。それこそ、テンソル更新時の畳込みにつかうカーネルを、時間ステップ毎に変えちゃうような対応が必要じゃない？

うん。「変える」。ただし、変えるのはテンソル更新時のカーネルじゃない。斜め方向のフローを制御するために、記憶セルは同じカーネルサイズで「かき混ぜる（＝畳込む）」。そしてこのかき混ぜるためのカーネルは、時間ステップ毎に $H_{t-1}^{cat}$ からつくる。「記憶セルをかき混ぜるためのカーネル」をつくるためのカーネルをも学習するのが Tensorized LSTM の完成形。

f:id:cookie-box:20180205234353p:plain:w390

（その4があれば）つづく

2018-01-26

NIPS2017論文読みメモ： Tensorized LSTM（その2）

論文読み深層学習

以下の論文を読みます。

※ 以下、キャラクターが会話します。それぞれの原作とは関係ありません。内容の誤りは本ブログ筆者に帰属します。

前回：その1 ／次回：まだ

えっと、LSTM がもてる記憶の複雑さ―つまり、同時にもてる情報量の大きさと特徴抽出の深さ―を上げるにはどうしようって話だったよね。単純に記憶の次元を増やすのじゃパラメータが激増するし、LSTM のスタックじゃせっかくの LSTM の利点である長期依存性の学習が台無しになっちゃうって言ってたよね。

うん…それでどうしようという話だけど、一般のニューラルネットワークでパラメータ数を抑制しながら情報量を増やす有名な方法には、Tensor Factorization とパラメータの再利用があるって。前者の Tensor Factorization というのは、パラメータを、低ランクのテンソルの積で表せるようなテンソルにするみたい？参考文献も読まなければ正しくはわからないけど…低ランクの積で表せるという制限を課すことでパラメータ数を抑えながら、高次元の特徴量を扱える？もう1つのパラメータの再利用は、CNN のように、小さなパラメータセットを繰り返し全体に適用するようなイメージ？

じゃあそのどちらか、あるいは両方を採用するとか？

それは…後者を。パラメータの再利用なら、特徴量ベクトルの次元数とは独立にパラメータ数を決められるし（CNNでいうと、画像の大きさとは関係なくカーネルサイズを決められる、かな…）、あと、情報をばらばらにして再帰ループさせることができるから、特徴抽出の深化に役立つって。これは、詳しくは後で？あと、それとは別に…RNNの隠れ状態ベクトル（特徴量ベクトル）をテンソルで表すって。あ、この論文では LSTM を拡張するけど、先に RNN で考える？テンソルで表すと、パラメータを共有する軸？をつくれるって。この軸と垂直な方向に隠れ状態テンソルを延ばしても、パラメータ数は増えない。これは、CNNでいう畳込み層のパラメータ数が、カーネルサイズが同じなら画像のサイズを大きくしても変わらないのと同じ。あと、高階のテンソルをつかうと、パラメータ数が同じなら、depth の割に高速にネットワークを wide にできるって。あの、「同時にもてる情報量の大きさ」と「特徴抽出の深さ」と言っていたのを、原文通りに width と depth とかくようにするね…正確ではない訳だと思うから。この、テンソルにする理由の後者はまだよくわからない。

うん。その隠れ状態のテンソルは具体的にどんな風に計算されてつくられるものなのか…プログラムでもなければ、よくわからないかな。

泉さんには、プログラムの方が読みやすい？でも、論文だから…数式。あ、RNNの隠れ状態ベクトルをテンソルにするといったけど、最初は簡単のために2次元のテンソル、つまり行列で考える。まず、普通の Stacked RNN (sRNN) からスタートする。論文3ページの Figure 1 の (a) …下に、絵を描いた。破線の左側。sRNN はある時間ステップ内で多段階の特徴抽出をする。図の例だと、3段階？この特徴抽出を、ある時刻に一段階目、次の時刻に二段階目…としたい。RNN は既に時間方向に「深い」から、特徴抽出も、これに便乗？そのように特徴抽出を時刻ごとに一段階ずつにしたのが、破線の右側。Figure 1 の (b) …これは skewed sRNN といって、sRNN をゆがめただけで…既に過去に別の論文で提案されている…。

f:id:cookie-box:20180126225422p:plain:w500

確かに、右側の絵では、データがどんどん次の時刻に流れて行っているね。出力される $h_{t-3}^{3}$ の上の添え字は何段目の RNN の隠れ状態ベクトルか、下の添え字はどの時刻の入力まで参照しているかという意味？

合ってる。上の図を、時間方向に展開しない形で書くと、下図になる。下図の一番左が sRNN で、真ん中が skewed sRNN。skewed sRNN の一層目は、一つ前の時刻の入力データと、一つ前の時刻の一層目の出力を受け取る。でも、一つ前の時刻の二層目以降の出力を受け取ってもいい。二層目の出力も受け取ったのが、下図の一番右。そして、この一番右の図の、各層の隠れ状態ベクトルを束ねた行列を隠れ状態テンソルと見做したものが、Tensorized RNN (tRNN)。

f:id:cookie-box:20180126231548p:plain:w500

tRNN の隠れ状態テンソルを $H_t \in \mathbb{R}^{P \times M}$ とかく。 $P$ が sRNN のスタック数に相当… テンソルサイズとよぶ。 $M$ は各層の隠れ状態ベクトルの次元数に相当… $M$ は画像でいうRGBチャネルのように、チャネル数とよぶ。さらに、 $H_{t-1}$ の頭に次元が合うように変換した入力データをくっつけたものを $H_{t-1}^{cat} \in \mathbb{R}^{(P+1) \times M}$ とかく。 $H_{t-1}^{cat}$ を $H_t$ に更新するときは、CNNの要領…カーネルサイズ $K$ ずつ、畳込み。その後、活性化。テンソルサイズ $P$ が大きくなっても、この畳込みのパラメータ数は増えない…。そして、例えば $K=3$ なら、「一つ前の層のさっきの出力」「この層のさっきの出力」「一つ後の層のさっきの出力」を畳み込むことになる…層をまたいだ畳込み…だから、cross-layer convolution という。

f:id:cookie-box:20180126232714p:plain:w480

なるほど。これなら、 $P$ を大きくしてもパラメータは増えないし、時の流れに便乗して特徴抽出の深化が進む…cross-layer convolution で層間でデータを相互作用させることで、複雑な学習もできる…後はこれを LSTM よろしく、記憶とゲートを増設するだけって感じかな？

基本的には…。でも、記憶とゲートを増設するだけでは、上手くいかないことが…。単純に記憶とゲートを増設すると以下。これは、Figure 1 の (d) に相当。ただこれだと、記憶は時間方向にしかスムーズに逆伝播しない。いま、cross-layer convolution しているから、層をまたぐ方向にも記憶は伝播しないといけない…。

f:id:cookie-box:20180126235221p:plain:w320

（その3があれば）つづく