Pattern Recognition and Machine Learning - 1481675604

1：karino2：2016/12/14(水) 09:33:24: Pattern Recognition and Machine Learning (Information Science and Statistics)

いわゆるPRML。
機械学習の定番教科書として有名だが、難しい事でも有名。

https://www.amazon.co.jp/dp/0387310738
91：karino2：2017/06/17(土) 18:00:00: 13.2.3 sum-productと一致している、という事を確認。
8章の内容をあまり覚えてないので、読み直す必要あり。
92：karino2：2017/06/17(土) 18:10:09: 13.2.4 小さい数を扱う事になるので、数値的にinstable。
そこでスケールして計算する、という話。
93：karino2：2017/06/18(日) 11:12:42: 13.2.5はlatent variabveの方に関心がある場合の推計の仕方。
マージナルを別々に最大化してもシーケンスとして実現確率が高いとは限らないので、max-sumで出す必要がある。
HMMでのmax-sumはビタビアルゴリズムと呼ばれている。

具体的な手順とその解釈。
max-sumの具体例という程度の話。
94：karino2：2017/06/18(日) 17:42:20: 13.2.6はHMMの拡張。

まず生成モデルの最尤法ではなく分類問題として解く方が良い場合は、クロスエントロピーの最小化問題として解く。

次にHMMの問題点について。
一つ目は、一定期間kになったあとに別のステートに行く、みたいな問題にうまくフィットしない。
遷移核が時間不変だからかね。
遷移行列の対角成分をゼロにしてうんぬん、と対策がなんか書いてあるが、良く分からず。

二つ目は離れた期間の影響を捉えるのが難しい、という事。
そこで観測値同士も依存させるautoregressive HMMというのが紹介されている。
その他input-outputとかfactorialとか。

plethora 大量の
95：karino2：2017/06/21(水) 21:36:14: 13.3 Linear Dynamical Systems
latent variableをノイズのある観測結果の系列から知りたいが、latent variableも時間と共に変わる、という問題設定。
時間と共にモデルが複雑にならない、という制約の元でモデルを考える。

指数関数族だと前の時点の変数をマージナライズしてもまた同じ形となる。
ここではガウス分布を中心に考える。

p636の下から10行目くらいのBy contrastからは何言ってるか分からない。

13.75から13.77が実際のモデルの式となる。
Aが遷移核か。
96：karino2：2017/06/21(水) 22:02:36: 13.3.1は

HMMのアルファとベータの定義はp620にあって、アルファがx1��xnとznの同時確率。
ベータがznの元でのxn+1からxNまでの条件付き確率。
c_nの定義はp627にあって、xn-1までのxを元にしたx_nの条件付き確率。
13.59はp628にある。
97：karino2：2017/06/21(水) 22:24:52: 13.3.1はLDSの推計。
漸化式の関係はHMMとほぼ同じになり、ガウス分布をあてはめて13.86となる。
一つ前までのパラメータが分かってるという前提で現時点のパラメータを出す。
一つ前の時点の積分（右辺）は混合ガウス分布の式なので実行出来て、そこから左辺のパラメータが分かる。
結果は13.89��13.91

尤度関数も13.63（p628）から出るとの事。

次に漸化式の解釈。
13.89の第一項は単純に１期前のzn-1の平均を遷移させた物。
そこに、それを遷移させた物からのemissionと実際の観測結果の差分で補正している。

ここまではx_nまでの観測データを使ってz_nを推計してきたが、次にx_N全てを使ってz_nを推計する問題を考える。
これはx_Nからのメッセージ送信とx_1からのメッセージ送信を合わせる事で分かる。
LDSでは少しメッセージを変形するとガウシアンになるので、それで解く慣例となってるとか。

最後にEM法で必要になるゼータの式を導出している。
98：karino2：2017/06/22(木) 21:00:49: 13.3.1はパラメータがわかっているという前提でzを推計した。
13.3.2はzが分かってる前提でパラメータを推計する（EM法）

同時確率をzの遷移とzからxのemissionに分解し（13.108）、これの、古いパラメータを元に出したzの事後分布の期待値を取る（13.109）。

あとは求めたいパラメータに着目して順番に式を整理し、この対数尤度を最大化してパラメータを決定していく。
99：karino2：2017/06/22(木) 21:23:56: いまいち何をやってるのか良く分からなくなってきたな。少し立ち止まって見直そう。

まず13.3でLDSの具体的な式をもうちょっと注意してみておく必要があった気がする。

13.75と76を見ると、z_n-1が観測された時のz_nの確率は、z_n-1にAをかけて遷移させた物を中心としたガウス分布をとる。
x_nはz_nにCをかけたものを中心としたガウス分布となる。
これがLDSという物らしい。

で、13.3.1ではパラメータを既知として、z_nを観測値から推計するのだよな。
それは直感的にはz_0から始めてz_1、z_2と分布を求めていく事が出来て、さらにそこからx_0、x_1と出していけるので、このxの値と突き合わせる事でパラメータを決めていけば良いのだろう。
ただEM法を使う、となってるので、そんな簡単には出ないのだろうね。

EM法的にはまずzを推計する訳だな。zの元でのxの分布は出て、観測されたxの値がもっとも得られやすいzはここから出せば良さそう。
13.85を少し追ってみたいな。MeatPieDayに乗り換え。
100：karino2：2017/06/22(木) 22:13:03: https://gist.github.com/karino2/785f3ddd0811c98bc8a98ec76e525761

よし、z_nの推計は理解した。
101：karino2：2017/06/24(土) 15:40:41: EM法の負担率。

観測値があった時に、それがクラスkからの寄与と考えられる度合い（ガンマの意味、EM法より）
102：karino2：2017/06/24(土) 15:48:57: 関係ないが変数はグザイだった。
103：karino2：2017/06/24(土) 15:50:08: 13.16は誤植でガンマじゃなくてグザイ（日本語版は治ってるとか）
104：karino2：2017/06/24(土) 16:11:34: グザイは観測値を元にjからkに遷移した個数を数えるようなもの。
隠れじゃないマルコフ遷移では、遷移核は遷移した数を数えて平均とる事で推計出来る。その拡張になっている。
105：karino2：2017/07/17(月) 15:08:57: 6章の予習。
まずは粗筋。

6冒頭ではカーネル関数の定義が出て来るが、どう使うかは不明。

6.1で線形モデルをカーネル関数に置き換える。
単純にパラメータwについて、ロス最小で解いた式をカーネル関数に置き換える。
するとpredictionはトレーニングセットのデータ点に依存した形と解釈出来る。

6.2 カーネル関数の探し方
基底を選んでdot積を取る事でカーネル関数を構築する事は出来るが、別に基底がわからなくてもカーネルがvalidな物かどうかを判定する事は出来そうで、実際出来る。
6.13から6.22で合成出来る関数は全てvalidとなるとか。
まぁなりそうね。

直接カーネル関数を扱うメリットとしては、
1. シンボリックな物が扱いやすい
2. 生成モデルから構築出来る（そして分類器として使える）
106：karino2：2017/07/17(月) 18:17:19: 6.3はradial basis function
冒頭はそれが出てきた歴史的なコンテキストの話が4つ。

1. まずn点を通る関数を導出するという問題。
2. regularization theoryというので二乗和のlossの解としてなんか制約があるとGreen関数がradial distanceだけに依存するとか
3. 入力がnoisyな時の補完の変分解（これは6.3.1でやるとか）
4. kernel密度推定で出て来るとか（これも6.3.1でやる）

そして近似解の話が。
107：karino2：2017/07/17(月) 18:44:51: 6.3.1はNadaraya-Watsonモデル。
カーネル密度推定、という物の話をしているが、いまいちなんなのかは良く分からない。

ただ、やってる事はそんな難しくない。
確率分布として6.42の形を仮定して、predictionの式を導出する。
すると6.47と置くと6.45と表せる。
108：karino2：2017/07/17(月) 19:38:40: 6.4はガウス過程。
6.4.1は線形回帰をガウス過程として見直す。
線形回帰は6.52と6.53のような正規分布と表せる。
一般にyがxの関数で、x_nの同時確率が正規分布で表せるような物をガウス過程と呼ぶ。

dispense: 無しですます
109：karino2：2017/07/17(月) 19:51:10: 6.4.2はガウス過程の回帰を扱う。
まず、ガウス過程の時のyのマージナルとtのマージナルを求める。
ここでカーネル関数は入力点2つ与えた時のy同士の共分散として導入されるので、2つの点のyを予測する時における近さを与えている、と解釈できる。

そして新たな入力に対するpredictはnまでは分かってるとしてn+1番目の入力を足した時のn+1番目の分布として考える。
すると6.66と6.67の正規分布になる。

あとは複数点への拡張などの話。
110：karino2：2017/07/19(水) 12:22:05: 6.4.3はカーネル関数としてパラメータのある物を想定し、最尤法などでパラメータを求める、という話題。

6.4.4は入力と出力の間のパラメータを学習させる事で、複数の入力のうちどれが効いてるかを学習出来る、という話。

6.4.5はclassificationにガウス過程を使うという話。
出力をsigmoid関数をかませて、ベルヌーイ分布を考える。
出て来る予測分布の式6.76はそのままでは計算出来ないとの事。
111：karino2：2017/07/19(水) 12:49:52: 6.4.6は前の項の分類問題にラプラス近似を適用する、という話。
ラプラス近似はモードの回りの正規分布に近似する、という奴か。
モードは6.83までで出せて、それを元にaの事後分布は6.86と近似出来る。
これを用いて予測分布の積分6.76を計算出来て、6.87と6.88となる。

次にパラメータを出す為に最尤法にもラプラス近似を適用する。
C.21は逆行列の微分。
式はごついが、結局は尤度のシータによる微分を求めている。
112：karino2：2017/07/19(水) 12:56:00: 6.4.7はニューラルネットとガウス過程の関係について話してるが良く分からない。
hidden unitを無限に増やすとガウス過程になる？
113：karino2：2017/07/25(火) 20:57:04: 7章はSparse Kernel Machines

冒頭: 6章のやり方はトレーニングセットが多くなるとそれに伴って計算量が増えてしまう。
そこで7章はトレーニングセットの中の少しの点だけに依存してpredictするカーネル法の亜種を考える。
114：karino2：2017/07/25(火) 21:13:45: 7.1はMaximum Margin Cllasifiers

二値分類を考える。
まずは線形で分離平面が定義出来るとする。
この時、マージンが最大になるように分離平面を決める事を考える。
すると7.7みたいなラグランジアンが定義出来て、7.10��7.12が解となる。
ここで7.10でカーネル関数が導入されている。

この解を用いて新たな点を分類する事を考えると、7.13式で分類する事になるので、あとはこのkやらa_nやらbを出すという話に。

ラグランジアンからキューンタッカー条件7.14��7.16が出てきて、slack じゃない式に出てくるデータ点をサポートベクターと呼ぶ、という事か。
サポートベクターは7.15で等号のケースとなる。
これらからa_nが出て、それを用いて7.18でbが出る。
115：karino2：2017/07/25(火) 21:25:37: 7.1.1はデータ点が綺麗に分離出来ない場合でも動くように拡張する。
これはマージンを最大化する所で、誤分類のペナルティを加える事で実現する。
加えた物が7.21。

それをひたすら解いて結局7.32は同じ式となるが、制約条件に違いがあって、7.33と7.34となる。

結果の解釈として、a_nが0の点はこれまで通りだが、a_n が0より大きい時は、Cかそれ未満かで変わる。a_nがC の時はこのサポートベクターはこれまで通り分離面の境界にあり、Cより小さい場合はマージンの中にある、という事になる。
116：karino2：2017/07/25(火) 21:28:40: 7.1.2はロジスティック回帰との関係。
いろいろ変形すると、7.45と7.47の関係となり、誤差関数がロジスティック関数かヒンジ関数かの違いと解釈出来る。
117：karino2：2017/07/25(火) 21:35:19: 7.1.3はマルチクラスの拡張。
いろいろあるが難しい、という話。

7.1.4は回帰。
7.51と7.52みたいな式を最適化するとして、あとは分類と同じ。

7.1.5はどれだけデータがあれば十分な汎化性能が得られるか、という理論でSVMは対象とされてた、みたいなお話。
118：karino2：2017/07/26(水) 21:31:19: 7.2はRelevance Vector Machine。

7.2.1でRVMのregressionを扱う。
普通の線形回帰のセッティング7.76で、yが7.78の時を考える。
さらにwのpriorを7.80と定義して、wに関してマージナライズした物（7.84）を最大化する。
すると、アルファの幾つかが発散するので、その発散する項のwの事後分布はゼロとなるから取り除くことが出来て、残った基底のベクトルがrelevance vector。

で、アルファとベータが出たら、7.90式で新たな入力xについてpredict出来る。
119：karino2：2017/07/26(水) 21:37:23: なんかここまで見た感じだと、ほとんど単なる線形回帰じゃん、という気がする。

違うのはアルファをデータ点ごとに定義する所と7.78の形でデータ点から基底を作る所か。後者は単なるカーネル法だよな。

いまいち新しい感じもしないが、まぁいいか。
120：karino2：2017/09/07(木) 13:09:00: 次は11章、という事で11章の予習開始。

さっそく11.5が分からないが、ググってたら以下の解説が。

http://retrofocus28.blogspot.jp/2013/08/pattern-recognition-and-machine.html

なるほど。
121：karino2：2017/09/08(金) 11:45:25: 11冒頭は素朴にサンプリングする場合の問題点の話。

1. 普通にベイジアンネットで表される分布で観測値が無ければ、ルートのノードから順番にサンプリングしていけば問題無い
2. 観測値がある場合はサンプリングして観測値と当たってなければやりなおし、で理論上は出せるが、偶然当たる事はめったにない
3. マルコフネットの時は楽な方法は無くて、Gibbsサンプリングとか
122：karino2：2017/09/08(金) 11:49:55: 11.1.1 uniformな分布から変形して求められる場合。
hとその逆関数が出せれば出す事は出来る。
多次元の場合も少し工夫すれは出せる。

当然hやその逆関数が出せる物に制限される。
123：karino2：2017/09/08(金) 11:53:01: 11.1.2 rejecting sample法
この辺は毎回見る都度何言ってるか分からなくなるが、しばらく考えると分かる、という感じなんだよなぁ。

11.4の図を見ながら考えるのが良くて、まず分かる分布についてサンプリングする。この図の場合はz0。
これがサンプリングされる頻度はグレーの分だけ割増されている。
だからグレーの分だけ割り引く必要がある。
124：名無しさん：2017/09/08(金) 12:20:19: 比較の為にユニフォームな分布を考える。

https://imgur.com/YgqIInE.jpg

この場合でも計算は出来るが、分布の頻度がすごく低いところにも等しく当たってしまう。
この場合は評価してみるまでもなく、だいたいハズレ。

一方で提案分布の形が近ければ、そもそもここを引く率自体が低いので、逆に言うとわざわざここが出た時には残る可能性は高い。
125：karino2：2017/09/08(金) 12:44:34: すぐ分からなくなるので、ユニフォームな分布をもう少し。
通常のモンテカルロ法との比較を考える。

正方形の中の点をランダムに打つ。
この点が、pより下の個数と上の個数を数える。
この比率はpの面積となる。
ある点に対してはpより上か下かは評価出来るが、積分は分からない、という場合にもこれで面積が分かる。

欲しいのは面積では無くて、分布の形に従ったサンプルの点なので、高い所にはたくさん出て、低い所にはあんま出ないようなサンプラーが欲しい。
そこでzを適当に引いて、このzについて、p(z)より上か下かを引いて上だったら捨てる、下だったら取る、とやる。

もう少し具体的に。0, 1, 2, 3,...,10と離散的な値について。
順番に0の点で乱数を引いて、p(0)より下の点だけ取る、次に1の点で同様の作業を10まで行う。
こうすると点が残ったり残らなかったりする。
残った数をカウントしていく。

一回の試行では0か1かがまだらに並ぶ。
二回目の試行では0から2 までが並ぶ。
これを何度も繰り返すと、度数分布となる。
126：karino2：2017/09/08(金) 12:46:46: rejection samplingはこの試す回数自体を点ごとに偏らせて、その分残す敷居は低くする、という物。
欲しいのはサンプルの点なので、rejectはなるべくされない方が良い。
127：karino2：2017/09/08(金) 12:57:00: kの値について。
kを大きくする、というのは、全ての点について等しくrejectされる領域を増やす、というもの。
全部の点で等しくrejectされる度合いを増やすので、結果の値には影響は与えない。
128：名無しさん：2017/09/08(金) 13:15:34: https://imgur.com/0NSGspw.jpg

あれ？等しいの？
129：名無しさん：2017/09/08(金) 13:19:16: 違った。こうか。
https://imgur.com/EwTiBRg.jpg
130：karino2：2017/09/10(日) 16:37:57: 11.1.3は提案分布をrejectされるごとにその接点を通る関数との線形和を足す事でrefineしていく、というやり方。
logをとると直線になるような物を足していく、という事なので分布に足す関数自体はexpとなる。

後半では高次元の時にはrejectされまくってしまう、という話がある。
これは確かにそうだろうな。
昔MCMCの勉強してた時はこの辺の話を良く理解出来ていなかったが、今読むと良く分かる。
131：karino2：2017/09/10(日) 17:18:46: 11.1.4 importance sampling
分布を求めるのでは無くて期待値を求めるというアイデア。
q(z)からサンプルを引くまでは同じだが、この引いた値に、p(z)から引く場合と比べた偏りを割り引く事で、和が期待値になるように出来る、というもの。

pの分布でのf(z)の期待値は、各zの値にp(z)を掛けたものの積分となるが、これをqでの期待値に変換すると、f(z)p(z)/q(z)の期待値を求める事と同じである事が分かる。
あとはそれをq(z)からのサンプリングの和に置き換えれば良い。

規格化定数が分からない時もごちゃこちゃ計算すれば結果が出る。

こっちの方がrejectされる訳じゃないのでサンプルが有効に使えそうだが、probability massが集まってる所に当たらないと良い結果にならないという点では似た欠点を持つ。

最後にevidenceがある場合の計算方法についての話がちらっとある。
まずuniform samplingという手法の話があるが、単純過ぎて良い結果にはあんまりなりそうも無い。
で、その改善としてlikihood weighted samplingというのが紹介されてる。これは条件つき確率にすべき部分を同時確率に観測値をいれただけの物で代用して、期待値の所で条件付き確率とのずれを補正する物。
11.24式はちゃんとは追ってないが、同時確率と条件付き確率の関係を考えるとマージナライズした分だけ偏るのだから、こんな感じの式になりそう。
132：karino2：2017/09/11(月) 10:48:34: 11.1.5 Sampling-importance-resampling

最初二回目のサンプリングというのがなんなのか分からなかったが、一回目にサンプリングした値から何度も選ぶって事ね。
だから一回目にサンプリングした値しか出てこないのか。
最初にL個サンプリングした後に、このLの内部での相対的なもっともらしさを重みとするのか。
なかなかシンプルだな。
133：karino2：2017/09/11(月) 11:07:44: 11.1.6はEMアルゴリズムでのサンプリングの使用。
これは何も新しい事は無い気がする。
IPアルゴリズムというのもあまりにもストレートフォワード過ぎて何が新しいのかを考える方が難しいくらい。
134：karino2：2017/09/11(月) 11:46:23: 11.2 MCMC
冒頭では簡単にMCMCによるサンプリングの概要が述べられている。
提案分布が時間の前と後ろで対象な時の話。

11.2.1はマルコフ連鎖の性質の話。
時間依存が無い時で、invariantな分布に収束するとはどういう事か、そして詳細釣り合い条件を満たすとinvariantだ、みたいな話をする。
最後に基本となるトランジションをmixtureしたトランジションの事が軽く触れられている。
135：karino2：2017/09/11(月) 11:59:46: 12.2.2はMetropolis-Hastingsアルゴリズム。
12.2の冒頭はMetropolisアルゴリズムで、これは連鎖の前と後の向きに対して対象な提案分布の物だった。
MH法はそれの拡張で、非対称な物でも使えるようにしたもの。
Aを詳細釣り合い条件を満たすように変更する。

その後qの選び方の話を。大きい分散だとrejectされがちだが小さい分散だとなかなか移動しないので、サンプルする間隔を広くしないとサンプル同士の相関が。
136：karino2：2017/09/13(水) 12:37:16: 11.3、11.4は別段難しい事は無いので置いとく。

11.5.1はHMCの話か。

ポテンシャルエネルギーの定義は割と簡単だが、運動エネルギーとはなんなのだろうか？
zが変化をしまくるような系は不安定、という事か？
このしまくる大変さ、みたいなのが運動エネルギーなのだろうか。
137：karino2：2017/09/13(水) 13:04:39: invariant: ある確率分布から一つ時間発展させても同じ分布になる事。

ergodicity: 初期状態に関わらずmを増やしていくと同じinvariantな分布に収束する性質。
138：karino2：2017/09/13(水) 13:18:07: 位置を固定して運動量を確率分布からサンプルする、というのがどうしてinvariantなのかが直感的に良く分からないので考える。

ある位置に対して望ましい運動量というのはあるのか？
ポテンシャルが凄く高い所で、周囲のポテンシャルが凄く低いなら、ここで静止しているのはおかしい気がする。
そういう点ではポテンシャルの場所による微分と関係がありそうだ。
11.55はそういうのに近い。

感覚的には、ポテンシャルの極小の点に居ない為には、ある程度の運動量が必要だろうな。
そういう意味では、ある点に居そうな運動量というのは多分あるだろう。
それは軌道が偶然そこを通るくらいの運動量で、なるべくゆっくりな物が一番確率が高いのだろうな。
ゆっくりな程偶然そこが観測される可能性が高いから。

あれ？それだとちょうど静止してるくらいが一番じゃないか？
例えばいろんな場所から弾を射出して、偶然ここを通る事が観測される可能性って事だよな。
ここで静止するのはよそから打つ場合は不可能か。
完全にまっすぐここに向かって打って、ちょうどここで反転するのが一番長くこの点を通る気もするが、それは向きがピンポイント過ぎるので積分するとそんなによく見るとも限らないのかなぁ。

この辺はいまいちよく分からないな。
139：karino2：2017/10/13(金) 16:09:09: 10章のノート。これはブログに書いた。

https://karino2.github.io/2017/10/13/54.html
140：karino2：2017/10/15(日) 19:02:47: PRMLの勉強会が終わった
https://karino2.github.io/2017/10/15/55.html