PRML 読書会 #9 資料(関連ベクトルマシン)

機械学習 読書会 PRML
「パターン認識と機械学習」(PRML)読書会 #9 で担当する 7.2 章の資料です。 いつもついつい資料を作り込んでしまってたけど、今回は念願の「資料はアジェンダ＋疑問点のまとめ」「板書メイン」になる予定。

7.2 関連ベクトルマシン

SVM(support vector machine) と RVM(relevace vector machine) の対比

SVM RVM
疎 もっと疎
２値 確率
半正定値 正定値性不要
凸 非凸
O(N^2) O(N^3)
交差検定とか ARD
  • サポートベクトル＝マージン境界上
  • 関連ベクトル＝境界から離れた位置にも

7.2.1 回帰問題に対するRVM

【３章の復習】ベイズの枠組みでの線形回帰
  • 1. モデル(条件付き確率) p(y|x,w,β) = N(y|w^T φ(x), β^-1)
  • 2. 事前確率 p(w|α) = N(w|0, α^-1)
  • 3. 尤度関数 p(t|w,β) = Πp(t_n|x_n,w,β)
  • 4. 事後確率 p(w|t,α,β) ∝ p(t|w,β) p(w|α)
  • 5. エビデンス(周辺尤度) p(t|α,β) = ∫p(t|w,β) p(w|α)dw
    • エビデンス最大化する場合はα,βを更新→4. を収束するまで繰り返し
  • 6. 周辺予測 p(y|x,t,α,β) = ∫p(y|x,w,β) p(w|t,α,β) dw
RVM のポイント = 事前分布の取り方
  • 個々の重みパラメータ w_i ごとに異なった hyperparameter α_i を用いる(★ARD 事前分布)
    • 他の条件付き分布、事後分布、周辺化などはベイズ線形回帰と全く一緒(むしろ SVM とはあまり関係ない……？)
  • 基底関数は「カーネル＋入力」で与える場合も含めてφ(x)と書く
  • エビデンスを最大化すると、大部分の α_i→∞、w_i→0 となり、対応する基底関数を取り除くことができる
    • α_i (< ∞) を「関連度」と呼ぶ？
    • w_i≠0 な重みを持つ基底関数に対応する入力 x_n を「関連ベクトル」
α,βの更新式( 式 7.87 & 7.88 )
  • かなり筋の悪い計算だなあ……
    • 事後確率の平均 m を止めて考えている（つまり \frac{\partial \bf{m}}{\partial \alpha_i} = 0 とみなす )
    • が、m はαに依存しているので、偏微分前の式変形の度合いによって結果が変わる(!!?)
  • なぜ \alpha_i^{-1}=\Sigma_{ii}+m_i^2 と「陽に」せずに、\alpha_i=\frac{1-\alpha_i\Sigma_{ii}}{m_i^2} と右辺にα_iを残すのだろう……？　何かメリットがある？(収束しやすいとか……)
  • PRML 演習問題の解答(PRML 原書サポート)での式 (133) における \frac 12\ln |\Sigma| は \frac 12\ln |\Sigma^{-1}| の間違い。
  • どこからどこまでを ARD(関連度自動決定)と呼んでいる？　ARD 事前分布から？　7.2.2 も含む？

7.2.2 疎性の解析

  • SVM は KKT の相補性条件から疎性が得られる
  • RVM は なんで？

エビデンス最大⇔観測値 t での確率密度を最大に

  • 左(α無限)と右(α有限)のどちらの p(t) が大きそう？　左！
    • t と相関が低い \varphi_i に対応する α_i は無限大に行きやすい
    • （これは境界となる hypersurface と関係がない）
RVM の計算量
  • 事後分布の共分散Σを求めるのに O(M^3) の計算量が必要(M=基底関数の個数)
  • カーネル＋入力点から基底関数を構成するなら O(N^3) に(N=入力点の個数)

⇒ 解の疎性を利用して RVM の計算量を減らす

逐次的疎ベイジアン学習アルゴリズム
  • エビデンス最大化の繰り返しを基底関数に対して逐次的に行う
    • 対数周辺尤度 L(α) を α_i を含まない部分 L(\bf{\alpha}_{-i}) と含む部分 λ(α_i) に分ける
    • α_i に対する疎性パラメータ＆品質パラメータを導入。λ(α_i) の微分や、対応する点が関連ベクトルかどうかを判別する式をそれらで表す
    • α_i を「陽に」求める式(他の hyperparam を固定)
  • α_i が∞となる基底関数を逐次取り除き、Σの計算に使う基底関数の個数を減らす
疑問とか
  • 「解の疎性が生じる原因の数学的な考察」(p61)はどこ行った？
    • 図7.10 で一定の納得は得られる。けど。
  • 逐次的疎ほにゃらら は入力点の追加には使え……ない？　「古い」α_i を更新しないからダメかなあ。
  • α_i を求めた後、α_1, ..., α_{i-1} は更新しなくていいの？　まじめに毎回全てのパラメータを計算する 7.2.1 と 7.2.2 はどれくらい結果に差が出る？
  • φと\varphiを同時に使うなんて、相変わらず記号使いがひどすぎるｗ

7.2.3 分類問題に対する RVM

【４章の復習】ベイズの枠組みでの分類(ロジスティック回帰)
  • 1. モデル(条件付き確率): p(y=1|x,w) = σ(w^T φ(x))
    • 訓練データは正確にラベル付けされているとする(β無し)
  • 2. 事前確率: p(w|α) = N(w|0, α^-1)
  • 3. 尤度関数: p(t|w) = Πp(t_n|x_n,w) = \prod t_n^y_n (1-t_n)^(1-y_n)
  • 4. 事後確率: p(w|t,α) ∝ p(t|w) p(w|α)
  • 5. 周辺尤度(エビデンス): p(t|α) = ∫p(t|w) p(w|α)dw
    • 1. が線形でないため解析的に計算できない→ラプラス近似
  • 6. 周辺予測: p(y=1|x,t,α) = ∫p(y=1|x,w) p(w|t,α) dw
    • これもかなり計算が面倒。ガンガン近似。
RVM における分類
  • 事前分布が ★ARD prior★(個々の重み w_i ごとに異なった hyperparameter α_i を用いる)
    • 他はロジスティック回帰と全く一緒(むしろ SVM とはあまり(ry
  • 予測分布も PRML 4.5.2 と同様に計算(できるはず)
    • プロビット関数の逆関数で近似とかするやつ
  • 関連ベクトルはサポートベクトルよりさらに疎(になりやすい？)
  • 出力クラスの確率を予測できる
    • 多クラス分類への自然な拡張(ソフトマックス)
  • 交差検定によらずハイパーパラメータを決定できる
疑問とか
  • 式 (7.118) を導出できなかった。ごめん。
    • とりあえず左辺のβは間違い(不要)
  • RVM は SVM ほど名前聞かない(素人観測)けど、実用性はどれくらいあるの？　交差検定しなくてよい(ほんと？)し、予測分布も得られるから、かなり嬉しいかなーと思うんだけど。
  • 関連ベクトルには幾何的な意味はないのかなあ(サポートベクトルの「マージン境界上」みたいな)

その他

  • VC 次元おもしろい
    • 数学屋さんにとっての集合の公理みたいなもん？
    • 線形分離器の VC 次元が(入力空間の次元＋１)なのはちょっと考えたらわかるけど、一般に VC 次元って計算できるものなの？
    • PAC って確かにベイズ流の対極だなあと感じたけど、PAC-Bayesian とかあるんだよね……(まだよく知らない)

気になるリファレンス

SMO (sequencial minimal optimization)
Error-correcting output code
PAC-Bayesian framework
  • McAllester (2003). PAC Bayesian stochastic model selection
Relevance Vector Machine
ARD(Automatic Relevance Determination)