NIPS2018読みメモ： Graphical model inference: SMC meets deterministic approximations（その1）

以下の論文を読みます。解釈誤りは筆者に帰属します。問題点がありましたらご指摘いただけますと幸いです。

Fredrik Lindsten, Jouni Helske, Matti Vihola. Graphical model inference: Sequential Monte Carlo meets deterministic approximations. In Proceedings of NIPS 2018. https://papers.nips.cc/paper/8041-graphical-model-inference-sequential-monte-carlo-meets-deterministic-approximations

次回：まだ

タイトルは「グラフィカルモデルによる推論」かな？ サブタイトル的なのが「逐次モンテカルロ法と決定論的近似手法の出会い」？？ 何だそれ…。なんでこの論文選んだの？

なんかちょっとタイトルが面白かったので。

それだけ！？

そういえば all you need というタイトルの論文をまれによくみますよね。

論文タイトルはポエム書く場所じゃないだろ！？

でもグラフィカルモデルってよく知らないんですよね。いくつかの丸を、向きがあったりなかったりする矢印で結んだ絵という理解しかないです。

絵！？ じゃあ、逐次モンテカルロ法っていうのは？

そちらは聞いたことがあります。逐次モンテカルロ法（SMC）は粒子フィルタともいうんですが、直接観測できない状態変数の分布をベイズ的にトラッキングする枠組みです。状態分布を点（粒子）の集合で表現するので原理上どのような形状の分布でも扱えます。手順としては初期の状態分布の粒子たちを発生させて、それぞれの粒子を少し先の時刻までシステムモデルによって時間発展させた後、それぞれの粒子からその時刻に実際に観測された値が観測される尤度を計算して、尤度が大きい粒子は増やして、尤度が小さい粒子は捨ててしまいます（リサンプリング）。以降、時間発展とリサンプリングを繰り返すだけです。ただそうして求めたある時刻の状態分布はあくまで粒子近似なので、分布のモーメントが保たれるかは議論しなければなりませんけど。

ふーん…「逐次モンテカルロ法」は事後分布の「近似」的な解を求める方法なのか。じゃあそれって「決定論的」なの？

いえ…システムモデルは一般にノイズを含むので、粒子を時間発展させる際にはシステムノイズの分布に従う乱数を加えることになると思います。乱数のシードを変えたら得られる状態分布が変わってくるはずなので、逐次モンテカルロ法の結果は確率的であり、決定論的なアルゴリズムではないと思いますが…。

じゃあ、タイトルの「決定論的近似手法」は「逐次モンテカルロ法」とはまた別の何かなんだな。まあ出会ってるくらいだからそれぞれ別だとは思うけど。アブストラクトを読むと、確率的グラフィカルモデルによる近似的な推論は「決定論的」なのと「モンテカルロ的」なのに分類されて、前者はおしなべて正確で高速だけど、見積りづらいバイアスがある？ バイアスって何だ…。後者は漸近一致するけど計算コストがかかる？ まあそれで当然この論文では両者を組み合わせることになるよな。具体的に、決定論的近似手法の結果を効果的に利用するような逐次モンテカルロ法を考案したんだって。利用する決定論的近似手法は何でもいいんだけど、論文中では具体的に以下の3つの手法を取り上げてるって。全部何のことかさっぱりわかんないけど…。

• loopy belief propagation
• expectation propagation
• Laplace approximations

それで、提案手法の結果はバイアスが修正されていて、決定論的手法のみの場合や単純な逐次モンテカルロ法よりも改善がみられたらしい…。

僕もその3つの手法はわかりませんね…そういえばPRMLの第8章が「グラフィカルモデル」ですね。目次を眺めてみると、ちょうど8.4.7 節がループあり確率伝播（loopy belief propagation）です。これは、ループがあるグラフ（厳密な推論が困難）に対する、最も単純な近似手法の一つということなんでしょうか。また、第10章の「近似推論法」の 10.7 節が EP 法（expectation propagation）ですね。これは変分法とよばれるクラスの解法のようです。ラプラス近似（Laplace approximations）は上巻の 4.4 節にあります。第4章は「線形識別モデル」ですね。全部PRMLに載っていますね。

載ってるのはいいけどそれどれもまだ読んでない章じゃん！ …で結論を読むと、提案手法には twisted SMC って名前が付けられてるな…最初からそう呼べばよかったんじゃないか…。まあそれでこの twisted SMC をつかうにはきっと twisting function っていうのが要るんだな。最適な twisting function を近似するのに決定論的手法をつかうっぽい。そうやって決定論的手法と SMC を組み合わせるんだな。この論文で提案したアプローチは擬似周辺化MCMC（pseudo-marginal MCMC）とか粒子MCMC（particle MCMC）とかにもプラグインとして適用しうるって。無理やり日本語訳してみたけど擬似周辺化MCMCという言葉はネット上にないな…。将来的には、SMC と組み合わせるのに一番ぴったりな近似手法を追及するとか、twisting function をイテレーティブに改善していくとかやりたいって。

では、その twisting function というのがどのようなもので、どのように機能するのかさえ読み取ればよさそうですね。

いやいやグラフィカルモデルについても決定論的近似手法についても何もわかってないんだけど！ でイントロダクションに戻ると、確率的グラフィカルモデルっていうのは高次元で複雑な統計モデルの依存構造を表現するのに広くつかわれていると…。それでそういうモデルでは往々にして分布がガウシアンじゃなかったり依存関係が非線形？だったりして厳密な事後分布を求めるのは困難なんだな。仮に確率変数が離散的な場合であっても、グラフが木構造？でない場合は計算量が爆発して厳密な推論が不可能…木構造って？

PRMLの 8.4.2 節が「木」ですよ。

木て！

グラフの構造が以下のような場合は「木」というそうです。

• 無向グラフの場合、任意の2つのノード間のパスが1通りしかないグラフを木（無向木）という。
• 有向グラフの場合、ルートとよばれる親をもたないノードを1つだけもち、他の全てのノードは1つだけ親をもつグラフを木（有向木）という。

※ ここに木を描く。

関係ないけどさ、「決定木」とか「ランダムフォレスト」とか、なんで木とか森とかが当然のようにモデルぶってるの？ おかしくない？

分岐するものの象徴だからじゃないですか。他により適した表現がありますか？

そういわれると…分岐するもの…ブロッコリー？

末端ノード多くないですか！？

まあそれで、一般に確率的グラフィカルモデルでは厳密な推論は難しいから近似的な事後分布の推定手法が発達しているわけだけど、近似手法はアブストラクトでもいわれていたように2種類に大別されるって。

• 決定論的な近似手法。
• モンテカルロシミュレーションに基づいた近似手法。

この前者がラプラス近似、EP法、ループあり確率伝播、変分推論とかだって。決定論的近似手法はモンテカルロ的手法に比べて速いし、限られた計算資源で高精度に到達しやすいけど、一方で近似誤差はあって、どれくらいの誤差があるのか定量的に見積もりづらいし、この誤差は計算資源を投入すれば減らせるというものでもない。バイアスってそういうことか。どれくらいの精度が見込めるかを出すがモンテカルロ手法より難しいのかな…挙げられてる近似手法を全部知らないから全然わかんないな。それでモンテカルロ的な手法の方はギブスサンプリングにSMCとかで、これは漸近一致性をもつ…って何？

おそらくですが…それらは目標の分布にしたがうサンプル点を大量に生成する手法です。サンプル点をいくらでもたくさん生成していいなら、目標の分布が突き止められるはずなんです。つまり、サンプルを増やせば推定分布は目標の分布に収束するということです。しかし、「いくらでもたくさん」は現実には達成されませんし、サンプルの採択／棄却の判断時にも誤差が発生していくかもしれません。

まあ2種類のどちらの手法も短所があるから上手く組み合わせようって話になるんだよな。この論文では因子グラフ（factor graph）として表される確率的グラフィカルモデルに対する手法を提案しているって。因子グラフとは…。

さっきの「木」の次の節の 8.4.3 節ですね。因子ノードというノードを導入して、同時分布を因子の積でかけるようにしたグラフです。

ふーん…それで、因子グラフに対する SMC は既にあるけど、提案手法では SMC の目標分布に twisting function というのを適用して「未来の」変数への依存性も考慮できるようにする？ 何じゃそりゃ…。でも SMC において目標分布を「ねじろう」っていうのは近年注目されているアイデアっぽい。状態空間モデルの推定とかではそういうのが取り入れられてるんだけど、それをグラフの推論にも応用したっていうのがこの論文なのか。

次回があればつづく

Reinforcement Learning: An Introduction〔Second Edition〕（その3）

以下の本を読みます。何かお気付きの点がありましたらご指摘いただけますと幸いです。
Sutton & Barto Book: Reinforcement Learning: An Introduction

〈参考〉過去に強化学習についてかいたものへのリンク

• 「これからの強化学習」勉強会#1
• 「これからの強化学習」勉強会#2
• Sutton本第1版の邦訳を読んだときの記事のまとめ

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

えっと、前回学んだのは、強化学習とは「各状態でどの行動を選択すべきか学ぶこと」つまり「方策を学ぶこと」だということですね。本番の前にあらかじめ方策を学んでおくことも、いきなり本番で方策を学んでいかなければならないこともあるようですが…。そしてその、エージェントが行動を選択して状態の間を移動していく舞台が「マルコフ決定過程」です。そうですね…いうなれば、状態とは海に点々と浮かぶ島々で、行動はそれぞれの島から他の島に行く（あるいはもといた島に戻ってくる）船です。エージェントはある島にいて、その島で乗れる船に乗ります。乗れる船はきっと複数あるのでどれか選ばなければなりません。それぞれの船が行きつく先の島は確実に決まっているかもしれないし、確率的に複数の島のどれかになるというようになっているかもしれませんが、その確率はエージェントがいまいる島と選んだ船のみで決まり、過去にいた島や過去に乗った船に左右されることはありません…。

なるほど、部長は船に乗って島々の間を船で旅するんだ。趣のある喩えだね。その旅の目的は何かな？

目的…そうです、この旅には目的があります。それは得られる報酬の和を最大化すること…報酬とは、それぞれの島で船に乗ったときにもらえる…ログインボーナスです。

趣が消滅したよ！？

ではそうですね…船に乗ったら、どこの島でどの船を選んだかに応じて金貨がもらえるんです。もらえる金貨の枚数は船によって異なります。いえ、船によっては逆に金貨を支払わなければならないかもしれません。ならば船を選ぶときに最も自分にとって得になる船を選べばよさそうですが、そうではありません。いま損をする船を選んだとしても、その船の行き先の島にはとてもたくさんの金貨がもらえる船があるかもしれないからです。それが「遅延報酬」、目先の損得だけ考えればよいのではないという強化学習の大きな特徴です。

もう1つの特徴は？

はい、困ったことに、どの船に乗るとどれだけの金貨がもらえてどの島に行きつくのかというのは最初わからないんです（※）。教えてくれる人がいないんです。だから、最初はとりあえず適当な船に乗ってみるしかありません。この、自分でやってみて情報を集めていくしかないというのが強化学習のもう1つの特徴である「トライ＆エラー」です…って、あれ？

※	環境モデルが既知の問題設定の場合はこれがわかっています。

どうしたの？

この旅はいつまで続くのでしょう。もしや永遠に続くのですか？ しかし、将棋の対局は終わりますよね…。それに、もしもらえる金貨が正になるようなループが見つかったら獲得できる金貨の枚数は無限大になってしまうのでは…それは無限大にうれしいということなんでしょうか…。

…まず、永遠に続く旅とそうでない旅があるよ。将棋の対局は後者だね。その場合は、島々の中に「この島で終わり」という島がある。そこにたどり着いたらもう他の島には移動できない。将棋の例から明らかなように、終わりの島は複数あってもいい。いろいろな詰みの盤面があるからね。

そこにたどり着いたら終わり、終着点…奥多摩駅のような。

違うよ？ 奥多摩駅からはちゃんと立川方面の列車が出てるよ？

確かに。ではその終着の島は、そこに行きつく船はあるが、そこから船は出ていないということですか？

と考えてもいいし、船は出ているけど必ずその島に戻ってくる船しかないと考えてもいい。どっちでもいいよ。後者と考えると、他の島と同じように扱えたりするけどね。一方で、終着の島がない場合もある。その場合は、永遠に旅が続くから、永遠に旅が続かない場合でも、集められる金貨の枚数が収束しないことがあるかもしれないね。でも、そういう場合は現在からある程度の期間に得られる報酬の和の最大化を目指すことが多いと思う。よくあるのが、 ステップ後に得られる報酬を 倍にすることで、遠い未来の報酬に得られる報酬ほど重みを小さくする。 にすれば報酬の和が発散するのを抑えられそうだよね。55ページの式 (3.8) がそうかな。

なるほど…旅は終わらなくてもいいのですか…自らが状態を移ろい続ける世界に終着点がないと知ったときエージェントは何を思うのでしょうね…。

さあ…。本に戻ると、2ページの中ほどでは「教師あり学習」を引き合いに出して、「正解付きの教師データをもとに未知データに対する正解を予測しようとする」という学び方も重要だけど、環境と相互作用しながら学ぶ場合はそれでは不十分だとあるね。もしかしたらサンプルデータがある場合もあるかもしれないけど、それが正解なのかわからないし、きっとそのサンプルデータはあらゆる状況を網羅してもいない。「地図にない場所」を探さなければ、最大の報酬は達成できないって。

そうですね、棋譜が手元にたくさんあったとしても、その盤面に対する正解手かはわかりませんし、あらゆる盤面の情報があるとも思えません。

次の段落では強化学習は「教師なし学習」とも違うとある。強化学習は教師あり学習ではないからといって教師なし学習でもないって。教師なし学習は正解ラベルのないデータに隠れた構造を見出す手法だけど、強化学習は構造を見出すのではなく報酬を最大化するものだからって。「教師あり学習」と「教師なし学習」という言葉はいかにも MECE に機械学習を分類しているようだけど、そうではなく、強化学習はそれらのどちらとも違う第3のパラダイムだって。

はい、教師あり学習は「見本となるデータをもとに未知データの正解を予測する」、教師なし学習は「データの構造を見出す」、強化学習は「環境と相互作用しながら報酬を最大化する」ですから互いに目指していることは異なりますね。なので、Mutually Exclusive なのはいいような気がするんですが、ではこの3者を Collect すると何を Exhaustive なんでしょう。3者に共通する目的は、「得られたデータ（中のサンプル）について何らかの判断をする」と思います…「この未知画像サンプルは数字の『3』だ」「このデータ中のこのサンプルは2峰の正規分布のこちら側に属している」「この状況ではこう行動する」などといった具合です。しかし、教師あり／なし学習と強化学習では、一度だけ判断すればいいのか、何度も判断を続けなければならないかが違いますね…強化学習が判断を下す対象は、データというよりはそれを生成するモデルであるようです。しかもその生成モデルは判断を下す度に判断に応じて変化する。なので、3者を特徴付ける軸として、判断する対象が「標本」なのか「モデル」なのかという軸を一つ考えます。また、何に基づいて判断するのかも3者は異なると思います。つまり、何を学習するかです。正解付きの訓練データから学習するのは教師あり学習のみです。教師なし学習では判断する対象データそのものに基づいて判断するようです。強化学習では、事前に判断の手がかりになる情報から学習する場合もあれば、それが不可能で対象データとの相互作用しながら判断を修正していくしかない場合もあるかもしれません。まとめるとこうです。

	判断をする対象のデータ	判断の根拠となるデータ （学習対象のデータ）	つまり、学習（根拠の抽出）と判断が
教師なし学習	未知生成モデルから生成されたデータ（標本）	未知生成モデルから生成されたデータ自体	同時である（未知データから根拠を抽出することが判断することに等しい）
教師あり学習		事前に得た「正解付き」類似データ	同時でない（事前データから根拠を抽出した後、未知データに対する判断を「予測」する）
強化学習	未知生成モデルそのもの（これについて連続した判断の列を与える）（判断する度に判断に応じて生成モデルは変化する＝未知生成モデルと相互作用する）	未知生成モデルから生成されたデータ自体の場合もあるし、事前に得た類似モデル／データの場合もあるし、そのどちらも用いる場合もある（が、事前に得た類似モデル／データの場合でも正解は付いていない）	3パターンありうる 同時である（未知データから根拠抽出） 同時でない（事前データから根拠抽出） 事前データからも根拠抽出するし、未知データからも根拠抽出する

もう少しシンプルにするとこうです。

	対象	モデルとの 相互作用	事前情報	事前情報に 対する正解
教師なし学習	標本	－	×	－
教師あり学習	標本	－	〇	〇
強化学習	モデル	〇	△	×

どうでしょうか？

といわれてもこの本は機械学習概論とかじゃないんだけど…部長がそう考えてわかりやすかったならいいんじゃない？

---

2019-01-12 追記

3ページは、他の学習にはない、強化学習が乗り越えないといけない独特の課題として「探索（exploit）と利用（explore）のトレードオフ」が挙げられているね。そうだね、いま部長がある島で10艘ある船のどれに乗るか選ぼうとしているとする（※）。実は目の前の船のうち9艘にはこれまでに乗ったことがあって、その9艘の中で一番金貨がもらえる船はもう知っている。だから、そのときの知識を「利用」してその船に乗りたい気がする。でも、これから先に得る金貨の枚数の合計を最大化するためには、やっぱり残り1艘の船も「探索」してみてもらえる金貨の枚数を確かめてみたい。実はその船が最も金貨をもらえる船かもしれないし、もしそうだったらそれを見過ごし続けていたら損してしまうからね。でも、あまりに「探索」にこだわっていたらせっかく得た知識をろくに「利用」する前に旅が終わってしまうかもしれない。難しいのは、「利用」と「探索」のどちらを選んでも不利益があるかもしれない。それを避けられない。ジレンマだね。それを呑み込んで、ある程度「利用」してある程度「探索」する、とバランスを取らないといけないんだよね。

ああ、わかります。私はいつもモスバーガーでモスバーガーを選ぶのですが、あそこにはテリヤキバーガーやロースカツバーガーなど何やら魅力的なメニューも他に多くあるでしょう？ たまには他のメニューも探索してみるべきなのではないかとふと思うのです。しかし、確実に口に合うものかはわかりませんし、これまでの経験からモスバーガーを選べば満足する未来は確約されていますから、結局モスバーガーを選んでしまうのです。これが探索と知識利用のジレンマだったんですね。

えっと…それは確かに探索と知識利用のジレンマが存在するけど、いうほど部長はジレンマに陥ってなさそうだね…というかモスバーガーなんていつでも行けるんだからメニューの全探索くらいできるんじゃないの…。

いえ、そうはいいますが、私が高校を卒業したら近くにモスバーガーのない土地で生活することになる可能性もあるでしょう？ モスバーガー側が永続する保証もありません。メニューを全探索するとなると、毎週モスバーガーに行くとしても半年程度はかかるはずです。残りの高校生活のうち半年間も探索に費したら、知識利用フェーズの割合があまりに削られてしまいます。

実は満足の合計を最大化するために探索と知識利用のバランスとってる…？

（次回があれば）つづく

Reinforcement Learning: An Introduction〔Second Edition〕（その2）

以下の本を読みます。何かお気付きの点がありましたらご指摘いただけますと幸いです。
Sutton & Barto Book: Reinforcement Learning: An Introduction

〈参考〉過去に強化学習についてかいたものへのリンク

• 「これからの強化学習」勉強会#1
• 「これからの強化学習」勉強会#2
• Sutton本第1版の邦訳を読んだときの記事のまとめ

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

Chapter 1 に入るよ。前回ネタバレしちゃったように、強化学習は環境と相互作用しながら行動を判断していくけど、そもそも自然界の動物ってそうだよねって話があるね。例えば幼児は明示的に教えられているわけではないけど、遊びながら／手を動かしながら／周囲を見回しながら、ある行動をしたときに何が起こるかを知って、それを繰り返して自分の目的を達成するにはどうするべきかを学んでいくって。

行動して、その結果をみて、また行動して…ということですか…？ あっ、それはもしやよくいわれる PDCA サイクルのことですか？ 申し訳ありません、私はそのような意識の高い幼児ではありませんでした…。

とっさにその単語が出てくる高校生は意識が高いんじゃないかな！？ 別に自分で意識はしてなくてもいいよ。意識的でも無意識でも、人間含め動物ってそうやって生きる方法を学んでいくよねって話だから。むしろ、意識してやる方法を、再現可能な手続きをこれからこの本で学ぶんだよ。もちろんコンピュータでやるんだから、評価も学習も完全に定量的な PDCA サイクルをね。

ということは、強化学習を学ぶと、仕事や人生が上手くいくんですか？ なんともはや…。

いや、仕事や人生だとまず「状態」や「行動」の集合を定義するのが困難なんじゃないかな…観測される情報ってとてもたくさんあるし、別に部長は毎ターン行動選択するって感じで生きてるわけじゃないでしょ。さらに何を目的（ゴール）としてどう報酬を設計するのかって話だし、そこまでできたとして上手く解けるかもまた別の話だしね。逆に「状態」や「行動」の集合及びゴールが比較的明確なボードゲームやコンピュータゲームをプレイするのなんかは強化学習の得意とするところだね。Chapter 1 の導入部分の最後に、強化学習は他の機械学習よりもゴールを意識した手法だとあるね。強化学習は本質的に「エージェントにどうふるまってほしいか」と切り離せないからね。もちろん他の機械学習手法にも目的（関数）はあるけど、それがモデルを学習する人間の現実的なゴールとぴったり重なっているかっていうと必ずしもそうでないことも多いんじゃないかなって意味だと私は思ったよ。

何を目的とするか…確かに PDCA サイクル以前に、自分が何を目指すのかが明確でなければなりませんね。私はまだ人生に強化学習を導入しようという段階になかったようです…。

よくわかんないけどわかってくれたならいいよ…。1.1 節の冒頭には、報酬を最大化するために何をするべきかを学ぶ、つまり状態から行動への写像を学ぶのが強化学習だとあるね。前回の絵にかいたように、この状態から行動への写像のことを方策というよ。そして強化学習の最も重要な特徴は以下の2点だとある。

• トライ＆エラー ― 正解の行動を教えてくれる人はいないので、自分でいろいろ行動してみて報酬を大きくするような行動を見つけ出さなければならない。
• 遅延報酬 ― いまとった行動が目先の報酬だけでなく後々の報酬まで影響するかもしれない。

これらを考慮しながら上手く行動しないといけないのが強化学習の難しいところだね。

トライ＆エラー…？ すみません、仮に私が将棋をプレイするエージェントだとしましょう。「いろいろ行動してみて報酬を大きくする行動を見つける」とはどういうことですか？ 勝ったら賞金をもらえる対局が1回しか開催されなかったら、何度もやってみるというのはできないのでは？

…そうだね、Chapter 1 の冒頭には幼児の学習の例があった。幼児の場合は方策を学ぶと同時に利用しているね。きっと幼児の目的は快適に生きることで、毎日より面白い遊びを探すだろうし、毎日その日の遊びの楽しさを享受している。他方、私は前回将棋をプレイするエージェントの話をした。このエージェントの方策が利用される場面はここ一番の対局だろうね。じゃあその対局で方策を学ぶかというとそれでは遅いよね。指し始めるまで何も知らなかったら、どの手が最も勝ちにつながるかなんてわからない。だからこの場合は幼児と違って、少なくともあらかじめ方策を学んでいる。幼児の場合は前世の記憶を引き継いで生まれたのでもなければ、「生まれる前からあらかじめ面白い遊びを知っている」ということはできないけどね。…まとめると、「強化学習とは方策を学ぶこと」といっても、その方策はあらかじめ学んでおくことができるのか、方策を利用したい場面で初めて学ばなければならないのかの別があると思うんだよね。方策を利用したい場面を「本番」とでも呼ぶならば、以下の3パターンがあると思うよ。

• 本番の前に方策を学んでおくことはせず、本番中に方策を学んでいく（方策を変更していく）。
• 本番の前に方策を学んでおき、本番中はその方策にしたがうのみ（方策を変更はしない）。
• 本番の前に方策を学んでおき、本番中にもさらに方策を学んでいく（方策を変更していく）。

快適に生きようとする幼児は上の1番目だ。他の例としては、まあこれもネタバレになっちゃうけど「目の前に10台のスロットマシンがある。どのスロットマシンも引くとコインがある確率で1枚出てくるが、その確率はスロットマシンごとにばらばらで、あらかじめわからない。このスロットマシンを合計1000回引けるとする。より多くのコインを得るにはどのような計画で引いていくべきか」みたいな問題も1番目に該当するかな。2番目は、ボードゲームをプレイするエージェントは割とここなんじゃないかな。本番でよい方策を学ぶんじゃ到底パターンが足りないから、あらかじめたくさんの棋譜を学んでおくとか、コンピュータどうしの対戦で腕を磨くとかしておくと思う。3番目は、事前に学習しておくことが可能だけど、本番中にも適応した方がいいケースかな。もちろん事前の学習と本番中の学習は異なる手法かもしれない。…そして、トライ＆エラーというのは、この1～3番目のうち「1番目や3番目の本番中の学習」「2番目や3番目の事前学習のうち、シミュレーションによって方策を学習するもの」にあてはまる概念だと思う。それなら「やってみて結果をみてみる」という要素があるからね。でも、例えば事前学習しかしない場合で、「やってみて結果をみてみる」という要素がない事前学習手法もあると思う。例えば Chapter 4 の Dynamic Programming（DP）はそうだと思うんだよね。DP の価値推定はトライ＆エラーって感じじゃないと思う。ただもしかしたら、DP は強化学習とは別枠の古典的なアルゴリズムってみなされてるかもしれないけど…。

えっと、わかりました。将棋エージェントにおけるトライ＆エラーとは、本番に臨む前のシミュレーションでの訓練で何局もやってみるということだったんですね。そうですね、飛車を振ってあまりに負けるようだったら、やはり居飛車戦法にするかもしれません。

まあ、強化学習問題のちゃんとした定式化は Chapter 3 でやるみたいだよ。定式化には動的システム論という分野の、不完全観測マルコフ決定過程の最適制御の概念を借りるみたいだね。

マルコフ決定過程？

マルコフ決定過程（MDP）というのは、状態がいくつかあって、それぞれの状態で取りうる行動をとると確率的に状態遷移と報酬の支払いがあるシステムであって、状態遷移確率がいまいる状態と選択した行動のみに依存する（過去にいた状態や過去に選択した行動には依存しない＝マルコフ性をみたす）ようなものの上で遷移する過程だね。強化学習エージェントが行動を選択する舞台だ。それが MDP で定式化されるから、これでもう強化学習問題のかなりの部分の定式化が整ったといえる。参考に昔描いた絵を貼っておくと、下の左側の絵が MDP の状態遷移図だね。この MDP には「不満」「満足」という2つの状態があって、「不満」の状態で取りうる行動は「残留」「転職」の2つ。「満足」の状態で取りうる行動は「残留」のみ。「不満」の状態で「残留」したら次も絶対「不満」に遷移する。「転職」したら「満足」に遷移するかもしれないしやっぱり「不満」に遷移するかもしれない。「満足」にいる状態で「残留」しても確率的に「不満」に遷移するかもしれない。あと、「不満」に遷移するときは不満なりの報酬（きっとマイナス）が、「満足」に遷移するときは満足なりの報酬（きっとプラス）が、「転職」したときは転職コスト（マイナスの報酬）がかかるっていうシステムだね。

なんでそんなマルコフ決定過程考えたんですか…あと、それどう行動するのが最適なんですか…。

部長だって人生の強化学習に興味があったじゃん…これは一つの定式化だよ…上の例では、行動選択が発生するのは「不満」状態においてのみだけど、転職するコストが小さいならとりあえず転職するのが最適なんじゃないの…わかんないけど…。

（次回があれば）つづく

パターン認識と機械学習 下（第7章：その1）

以下の本を読みます。上巻を読むこともあります。何か問題点がありましたらご指摘いただけますと幸いです。

パターン認識と機械学習 下 (ベイズ理論による統計的予測)

前回：第6章 その6 ／次回：まだ

第7章は「疎な解を持つカーネルマシン」ですね。

この章のタイトルだけ雰囲気違くない？ なんかラノベのタイトルっぽくない？

そうなんですか？ ラノベのタイトルって「俺の疎な解を持つカーネルマシンの学習が収束しないのはお前らが悪い」みたいなのじゃないんですか？

他人のせいにするなよ！

導入を読むと「疎な解」というのはおそらくこういうことなんですね。カーネル法は可算無限個の重みの最適化を有限個の重みの最適化に変換してくれる手法ですが、有限個といっても訓練データの個数なのでそれもそれで多く、学習にも予測にも計算コストがかかります。しかし、重みの解が疎な場合には計算コストを抑えることができる。本章ではそのような場合をピックアップするということだと思います。というか取り扱うモデルは次の2つですね。7.1 節が SVM（サポートベクトルマシン）と、7.2 節が RVM（関連ベクトルマシン）です。前者では出力の事後確率は得られませんが、後者では事後確率の推定ができるらしいです。

事後確率が得られないっていうと、スパムメールかどうかの分類はしてくれるけど、どれくらいの確率でスパムメールかまでは教えてくれないってことだよな。

7.1 節で最初に出てくる2値分類問題は第6章の最終回で参考にした「学習システムの理論と実現」の「第3章 カーネルマシン」で出てくる話とむしろ同じですね。まずカーネル関数のことは忘れて素朴に考えます。いま、モデル を、訓練データ で学習したいです。ただし です。なお、訓練データは特徴空間で線形分離可能とします。このとき一般には、特徴空間において のサンプルたちと のサンプルたちを分離する超平面は無数に存在します。サンプルたちを分離する超平面が1つあったら、それをほんの少しずらしてもやはりサンプルたちを分離しているでしょうから。訓練データを分離するだけなら無数にある超平面のどれを選んでも違いはありませんが、未知のデータの識別への適用を考えると、あまりサンプルすれすれで分離するような超平面は選びたくないものです。なので、方針として、分離超平面の中でも分離超平面に最も近いサンプルまでの距離が最大であるものを求める解とします。このように学習することを「マージン最大化」といい、そうやって学習したモデルが SVM ですね。なぜマージン最大化するのかは改めて後の節で説明があるようですが、36～37ページの説明によると、クラスごとに Parzen 推定法（分散 のガウスカーネル）で密度推定し、その密度をもとに誤分類率が最小となる超平面を求めると、 の極限でマージン最大超平面と一致するそうです。なぜそうなるかは を に近づけるにつれ分離超平面はサポートベクトル以外のデータ点からの影響を受けなくなるから…この後40ページで初めて出てくるサポートベクトルという単語を37ページで使ってきましたね…。

てかその説明いる？ マージン最大な分離超平面の方がよさそうだからでよくない？

…僕たちは分類器を学習するとき、何も訓練データにおける損失関数を最小化したいわけではないはずです。未知の点を分類したいはずなんです。であれば、即座に訓練データを分離する超平面を探すのではなく、クラス毎の密度を推定するのが誠実な手順といえると思います。36～37ページの主張は、ある密度推定をしたもとでの誤分類率最小分離超平面の極限がマージン最大分離超平面に一致するというものですから、マージン最大化に正当な意味を与えているでしょう？ なぜマージン最大化をしたのかと訊かれたとき、その方がよさそうだから、では回答として曖昧でしょう？

はい。

線形分離可能な仮定のもとでは、点 から分離超平面 までの距離は なので、解きたいマージン最大化問題は ですね。どう解きますか、ハヤト？

えっ？ 1番近いデータ点までの距離が最大になるように超平面のパラメータ を探すんだよな… ってのが邪魔だよな。どれがマージン最大な分離超平面に一番近い点かって最初からわかんないし。そこがなければ普通に についての勾配が求まるんじゃない？

ええ、 は邪魔ですね。そこで、 には定数倍の自由度があることを利用します。 としてしまうんです。そういう を選ぶと決めるんです。そうすれば先の最大化問題は となって、邪魔だった が消えます。

まるっと消えた！？ あれでも、その最大化問題って常に をゼロベクトルに近づけろ、みたいなことにならない？ てか最大値発散しない？

もちろん、 に入れた制約を無視してはいけません。いま という値はこれが最小となる で とすると決めたので、すべての で でなければなりません。この不等式制約の下で を解きます（二次計画問題）。というか計算上の便利のために に読み替えます。 このような不等式制約下での最大／最小化問題はラグランジュ乗数法においてラグランジュ乗数に という制約を入れると解くことができます。かなり見づらいですが2次元の特徴空間で適当な4つのデータ点で計算してみたのが以下のノートです。というか2枚目の1行目までは一般的な話です。1枚目の矢印の直前までは を最適化しようとしていたんですが、矢印の直後では を消してしまって の最適化問題に変換してしまっています。これがマージン最大化問題の双対表現です。

※ 矢印の根元の近くの は の誤りです。

へー、不等式の制約があっても解けるんだ。…ってあれ？ 一番下のとこ、最終的にまた不等式の制約がある最大化問題になってない？ プロデューサーはこっからどうやって解いたの？

はい、再び二次計画問題になるんです。この解き方は 7.1.1 節で議論するようです。なおプロデューサーさんは上の最大化を場合分けで解こうとしてよくわからなくなり R の optim 関数の力を借りました。

そっか…。

ちなみに、ノートの2枚目の1行目の式から、双対表現において特徴空間の点の座標は内積（カーネル関数）としてのみ現れるのがわかります。また、 より、最適解が と例によって「サンプル点におけるカーネル関数の重み付き和」になっていることがわかります。つまり、この最適解は再生核ヒルベルト空間の元の中で最もよい解です。

…レプリゼンタ定理って不等式制約あってもいいの？

…すみません、よくわからなかったんです。ただ、マージン最大化問題は、不等式制約付き最大化問題の形の他に、40ページの (7.19) 式の最小化問題の形にもかけるということです。こちらであれば不等式制約がありません。ただ、この という関数は をとるということで、これは実数値関数とはいえません。レプリゼンタ定理では、ここは実数値関数でなければならないので…ただ、結果的には大丈夫なんだろうとは思います。39ページに戻ると、このマージン最大化問題におけるカーネル関数もまた正定値である必要があるという記述がありますね。正定値だと最大化すべきラグランジュ関数が上に有界になると。PRML においてカーネル関数は個別事例で出てくるので、毎度カーネル関数が満たすべき性質を確認しているのかもしれません。

40ページの、「すべてのデータ点について あるいは が成り立つ」って？

上のノートだと、右上の白い点には が成り立ち他の3点には が成り立ちます。 が成り立つというのはすなわちその 番目の点が分離超平面に最も近いということです。最も近いなら とすると決めたので。上のノートの例だと分離超平面に最も近い点が3点存在します。そしてこの3点の座標のみが分離超平面をどこに引くべきかに影響を及ぼします。右上の白い点は（結果的にですが）分離超平面に影響を及ぼしていません。未知の点に対する予測時に、未知の点とこの点とのカーネルは使わないんです。 というのはそういうことです。逆に予測に影響を及ぼす である点をサポートベクトルといいます。上のノートの例だと右上の白い点を除いた3点がサポートベクトルです。この例だと全データ4点中3点がサポートベクトルなのでわかりづらいですが、現実の場面では普通全データ数が膨大で、サポートベクトルであるデータ数はそれに比べると僅かになります。これが SVM が「疎な解」たる所以で、予測の計算コスト上とてもうれしい性質です。

あー結果的に右上の白い点は存在しないのと同じなんだな。最初からはわかんないけど。40ページの続きにはバイアスパラメータ の求め方があるな。でも って双対表現に書き換えるために を消去したとき の式で表してたんじゃないの…って違うな。それは の方だけで は勝手に消えたのか。プロデューサーってどうやって 求めたの？

ええ、困ったのでサポートベクトルであるデータ点を1つ選んで を について解きました。しかし、この解き方はカーネル法の文脈では不可ですね。 を陽に扱ってはいけませんから。カーネル法における正しいバイアスパラメータ の求め方は、この式に を代入して を解くことです（式 7.17）。理論上はサポートベクトルのうち任意の1点を選べば は求まりますが、実用上は数値誤差抑制の観点から全てのサポートベクトルから を求めて平均するようですね。

（次回があれば）つづく

NIPS2018読みメモ： Precision and Recall for Time Series

以下の論文を読みます。解釈誤りは筆者に帰属します。問題点がありましたらご指摘いただけますと幸いです。

Nesime Tatbul, Tae Jun Lee, Stan Zdonik, Mejbah Alam, Justin Gottschlich. Precision and Recall for Time Series. In Proceedings of NIPS 2018. https://papers.nips.cc/paper/7462-precision-and-recall-for-time-series

ハヤト、今年もNIPS読みやりますよ。

俺たちは去年読んでないだろ！ 去年読んでたの別の子たちだよ！

この論文のタイトルは「時系列の精度（Precision）と感度（Recall）」ですね。

精度と感度？ って確か…。

どちらもモデルの判定のよさの指標ですね。「スパムメールフォルダに振り分けられたメールのうち、何%が本当にスパムメールだったか」が精度、「届いたスパムメールのうち、何%をちゃんとスパムメールフォルダに振り分けたか」が感度ですね。分子は同じですが分母が違いますね。「スパムメール判定の『精度』がよいか」、「スパムメール検出の『感度』がよいか」と覚えると覚えやすいですよね。

	スパム判定器がスパムメール フォルダに振り分けた （陽性：Positive）	スパム判定器がスパムメール フォルダに振り分けなかった （陰性：Negative）
届いた全てのスパムメール のうち	正しく振り分けた件数 ＝True Positive（真陽性：TP）	誤って振り分けなかった件数 ＝False Negative（偽陰性：FN）
届いた全てのスパムではない メールのうち	誤って振り分けた件数 ＝False Positive（偽陽性：FP）	正しく振り分けなかった件数 ＝True Negative（真陰性：TN）

精度： Precision = TP / (TP + FP)　分母はスパムメールフォルダに振り分けたメールの件数
感度： Recall = TP / (TP + FN)　分母は届いた全てのスパムメールの件数

いや覚えやすくなってねーよ！ 現にプロデューサーちっとも覚える気配なくて毎回定義検索してるよ！

アブストラクトによると、伝統的な異常検知では「点」ベースで、つまり、時系列であればある一時点の値がそれ単体で異常かどうかを検知しますが、通常現実世界での異常はある程度の期間にわたって起きる（range-based）。このことを考慮して、時系列の分類モデルを評価する手法を考案した、という話のようですね。アブストラクトからはこれ以上詳しい内容はわかりませんね…。

ふーん…あれでも、そういうある程度の期間にわたって起きる時系列の異常に対する検知手法って普通になかったっけ？

異常検知と変化検知 (機械学習プロフェッショナルシリーズ)

その辺は伝統的な異常検知という扱いではないんだと思います。というか検知手法があるかではなくて評価手法があるかって話なんで。

そっか。

ちょっと情報不足なので先に結論も読んでしまいますね。この論文ではある期間にわたる「モデルの予測値」と「実際に観測された値」の距離のようなものを表す量を定義したみたいですね。予測値と実績値の重なりとか、相対位置とか。そして、バイアス関数なるものでさまざまな基準の重み付けをカスタマイズできるみたいです。さまざまなデータ及び異常検知モデルに対して、他の2つの評価モデルと提案評価モデルを比較したところ、提案評価モデルの方が expressive で flexible で extensible だったと…これらの意味するところは後で要確認ですね。提案評価モデルは適用ドメインによってカスタマイズすべきであるものの、extensible なので論文内で示したセッティングでもじゅうぶん機能するだろうとあります。

評価手法の評価って意味わかんなくなってくるな…それに、色んなデータに適用できますって本当なのかな。時系列データって色々あると思うし。

とにかく最初からみていきましょう。イントロダクションに戻ると、この論文ではある程度の期間にわたって発生する異常を range-based anomalies とよぶようですが、range-based anomalies とは contextual な異常と collective な異常の部分集合だとありますね。特にその期間中に単体として異常な点が1つもなくても期間データとして異常を含む場合を range-based anomalies というそうです。

contextual と collective？

それぞれ参考文献である以下のドキュメントの 15:7 ページと 15:8 ページに記述があるようですね。
https://www.vs.inf.ethz.ch/edu/HS2011/CPS/papers/chandola09_anomaly-detection-survey.pdf

• Contextual Anomalies というのはある「文脈」では異常だが他の「文脈」では異常ではない、という異常のことみたいです。だからこの異常を検知するには「文脈」も明らかになっていないといけません。…という説明だと抽象的で意味がわからないので具体例をあげると、東京である日の気温が10℃だったとします。それが1月だったら取り立てて珍しいことでもないですよね。でも8月だったら異常な事態だと思います。その点がグラフの中で自然な場所に位置するか、不自然な場所に位置するかといった感じですかね。
• Collective Anomalies というのは1点1点は異常ではないが、まとまっていることで異常、といった感じですね。15:9 ページにグラフで載っている例は心電図で、一定の周期ごとに大きい値をとって小さい値をとるようなパルスがみられますが、1箇所だけそのパルスの間隔が大きくあいていますよね。その箇所のデータは1点1点が異常値というわけではないですが、その値がずっと続いていることが異常といえます。

これらのような異常を検知する場合、「点」ベースの異常の場合と異なり、単純な精度や感度によってモデルの性能を評価できません。にもかかわらず無理に適用することで誤った評価がなされるという弊害があったり、近年のリアルタイムデータの増加でこれらのような range-based な異常の検知手法の必要性も高まったりしているので評価指標の確立が求められている、といった内容が第一段落目までですかね。

contextual な異常と collective な異常って、その気温と心電図の具体例はわかるけど一般的にはよくわかんないな…まあいっか。確かにそういう異常を検知するモデルをつくったときにどう評価するべきかってのは明らかじゃないかも。

イントロダクションの続きを読むと、提案評価モデルは伝統的な評価指標も包含するみたいですね。かつ、特殊化関数なるもので評価軸ごとの重みをコントロールすることによってデータドメイン毎へのカスタマイズも可能だと。この論文のスコープ外になるが提案評価モデルは機械学習モデルの目的関数にもつかえるのでその方面での活用も期待できるとありますね。

そっか、評価指標だったら学習の目的関数になるよな。回帰モデルの2乗誤差とかよく目的関数かつ評価指標になってるし。

そこまでがイントロダクションで、次の第2節は背景と目的といった感じですかね。図1(b) に帯のような絵がありますが、これは帯の部分が検知すべき異常ということなんでしょうね。モデルの予測によると赤い帯が異常で、実際の異常は水色の帯だったということと思います。このときモデルの予測のよさをどう評価すればいいか、という話ですね。

えっと、モデルの予測は実際の異常を少しは当ててるっちゃ当ててるけど、モデルが予測した異常と実際の異常が部分的に重なっていたり、モデルが予測した異常が実際の2つの異常にまたがっていたり…よくわかんない！

ええ、本文にも「部分的な重なりがだいたい悪い」とありますね。モデルが予測した異常期間のうち一部が実際の異常期間に重なっていたら、モデルの予測は部分的には True Positive で部分的には False Positive みたいなことになるわけですが、この場合は TP と FP の比率を定量化できれば評価できそうです。しかし、例えば時間の長さの比などにしてしまえばよいかというとそうでもありません。実際の異常のどの箇所を当てたかなども判断基準になりうるので。一般的な実用場面では、異常の始点側を予測できた方がうれしいはずです。異常が終わりかけになって初めて予測できたのではあまりうれしくありません。そもそも、図1(b) の右側のようにモデルの予測した異常と実際の異常が1対1対応しない場合は、比率をどう定義すべきかよくわかりません。だから、異常の重なりをとらえるとき何か「濃度（cardinality）」をとらえたいと。ここでいう「濃度」は数学用語の「集合の元の個数」の拡張のような意味の濃度であって、日常語の濃度ではないので注意してください…まあ、実際の異常期間とモデルの異常期間が1対1対応であったらそうでない対応のときより評価すべき、という程度の意味でしょうが…。

あー、例えば地震を予測するモデルだったら、その予測が揺れている期間の始まり側と重なっている場合と終わり側と重なっている場合の価値が違うな。揺れ始めてからアラートを出されても全然うれしくないし。でもそういわれると一般的にどんな時系列データでも「始まりの方が肝心」ってあてはまりそうな気がする…。

続きには今回の評価指標の設計のゴールがありますね。あ、ここで Expressive, Flexible, Extensible の説明がありますね。

• Expressive： range-based な異常特有の性質（部分的な重なり、異常の濃度）をとらえる。
• Flexible： ドメインに応じて重み付けを調整できる。
• Extensible： さらに必要に応じてドメイン特有の基準を追加できる。

これらを達成する評価モデルにしたいということです。

ふーん…なんかゴールとしてその3点で足りてるのかとかよくわかんないな。

まあこの3点が満たされている方がそうでないよりいいのでは。続く第3節は先行研究ですね。まず時系列データの分類や異常検知は重要という話があります。スペースシャトルに Web サービス、医療データやサイバー攻撃まで、異常検知が求められるドメインはたくさんあり、それぞれに手法が提案されてきましたが、評価モデルの確立は後手に回っていたと。といっても、センサーによる行動認識とか、変化点検知とか、評価モデルが提案されている領域もあるにはあるようです。特に Ward2011 らの手法はきめ細かいらしいですが、それらの既存評価モデルはチューニングができないと。Lavin2015 らも時系列データに対する確たる評価指標の不存在を指摘していたらしいですが、彼らの NAB（Numenta Anomaly Benchmark）評価モデルは本論文の提案手法より柔軟性に欠けるらしいです。このモデルは実験パートで提案手法の比較対象になっていますね。7ページ以降の図表で Numenta と表記されているのがそうですね。

…なんかさ、この手の論文の先行研究パートって先行研究の粗探しみたいじゃない？

論文なんだから先行研究に対して新規性や有効性がないと仕方ないでしょう…第4節は期間にわたるデータに対する感度と精度ですね。というか感度と精度という組合せは踏襲するんですね。先に感度からで…実際の異常期間の集合を とし、モデルが予測した異常期間の集合を として、全期間を通した平均感度を

と定義します。 は1つの異常期間 を検知したかどうかで、これが肝心です。 は以下のようなものであってほしいです。

• が1点のみからなる異常であっても検知したかどうかを評価してほしい（存在）。
• のうち多くの割合の点を検知するほど高い感度になってほしい（サイズ）。
• のうちどの位置を検知したかも考慮するものであってほしい（位置）。
• を1つの予測異常期間 で検知するのと、2つ以上の予測異常期間で検知するのとでは、前者の方をより評価してほしい（濃度）。

注文多いな！

そこで、 を、「存在」を評価する と「サイズ、位置、濃度」を評価する の重み付き和とすることにします。

前者の は のうち1点でも検知したかどうかです。0 or 1 です。面倒なので式は省略します。 はさらに以下の要素からなります。

は となる関数で濃度要素を、 は となる関数でサイズ要素を定義します。 は となる関数で、位置要素を定義します。関数 の具体形は…あ、関数自体がカスタマイズ対象なんですね。

そこは自分で考えないといけないのか。

でも実際ドメインによって何を重視して評価するかの差も出そうなところですしね。それに、4ページの図2にちゃんと の実装例がありますよ。 は のうち多くの割合の点を検知するほど高い感度になるように定義すればいいですが、実装例ではシンプルに重み付き検知率ですね。 の全ての点を検知したら 1 だし、1つも検知しなかったら 0 だし（その場合そもそも がゼロですけど）、その中間だったら検知した点の重みによります。その重みを決めるのが というだけです。位置により重みに差を付けない例と、前方／後方／中央の重みを大きくする例が紹介されていますね。 の例はないですけど、これは「1対1対応じゃなかったときにどれだけペナルティするか」なんで、ペナルティする必要がなかったら 1 でいいし、ペナルティする必要があったら「対応する予測異常期間が2つ以上だったら 0.5 にする」とか「予測異常期間の数の逆数にする」とか適当に決めればいいんじゃないですか。

実装例が Figure 2 なのが地味に気になるんだけど…コードって図なの…？

読めれば何でもいいでしょう…でもこういう疑似コードは普通 Algorithm 1 とかなっていることが多いんですかね。ちなみに、精度についても全期間を通した平均精度はほぼ同様ですね。 だったところを にする必要がありますが。感度は「それぞれの実際の異常が検知されたか」なので についての和ですが、精度は「それぞれの予測が正しかったか」ですから についての和になりますね。そして、 に相当するものはないですね。感度の場合は、それぞれの実際の異常期間が「そもそも検知されたか」「どれくらい理想的に検知されたか」の二段構えでしたが、精度の場合は、それぞれの実際の予測期間が「どれくらい理想的に実際の異常を予測したか」しかないです。「そもそも予測が何かしらの実際の異常にぶつかったか」という要素は考えないんですね。感度の場合は、異常が検知されただけで一定の価値を与えていましたが、予測の場合は、予測を異常にぶつけただけで一定の価値を与えるということはせず、ぶつけ方をみるということなんですね。この非対称性は何となくわかりますけど、すっきり説明しづらいですね。

（実験パートの追記があれば）つづく