Upgrade to Pro — share decks privately, control downloads, hide ads and more …

SOLVE-GP: ガウス過程の新しいスパース変分推論法

SOLVE-GP: ガウス過程の新しいスパース変分推論法

論文紹介
Jiaxin Shi, Michalis K. Titsias, and Andriy Mnih, "Sparse Orthogonal Variational Inference for Gaussian Processes," AISTATS 2020. http://proceedings.mlr.press/v108/shi20b.html

Takahiro Kawashima

October 05, 2021
Tweet

More Decks by Takahiro Kawashima

Other Decks in Research

Transcript

  1. 論文概要 • Title: Sparse Orthogonal Variational Inference for Gaussian Processes

    • Author: Jiaxin Shi, Michalis Titsias, Andriy Mnih • Published in: AISTATS 2020 ガウス過程をスパース近似する新たな変分推論法 SOLVE-GP を 提案 2
  2. ガウス過程の基本的結果 言わずと知れたガウス過程,最大の難点は scalability の悪さ 𝑁 個の説明変数 𝒙𝑛 ∈ X ⊂

    ℝ𝑑 から 𝒚𝑛 ∈ Y ⊂ ℝ への回帰を考える このときガウス過程の尤度は,𝔼[𝑦𝑛 ] = 0 なら 𝑝(𝒚|𝑿) = N(𝟎, 𝑲ff + 𝜎2𝑰) で,新規入力 𝑿∗ に対する予測分布は 𝑝(𝒚∗|𝒚, 𝑿, 𝑿∗) = N(𝑲∗f (𝑲ff + 𝜎2𝑰)−1𝒚, 𝑲∗∗ − 𝑲∗f (𝑲ff + 𝜎2𝑰)−1𝑲f∗ ). 𝑲ff : 𝑿 のグラム行列 (𝑁 × 𝑁) 𝑲f∗ : 𝑿, 𝑿∗ の各要素のカーネル出力による行列 (𝑁 × 𝑁∗ ) 𝑲∗∗ : 𝑿∗ のグラム行列 (𝑁∗ × 𝑁∗ ) 3
  3. ガウス過程の計算量 ガウス過程の尤度と予測分布 𝑝(𝒚|𝑿) = N(𝟎, 𝑲ff + 𝜎2𝑰), 𝑝(𝒚∗|𝒚, 𝑿,

    𝑿∗) = N(𝑲∗f (𝑲ff + 𝜎2𝑰)−1𝒚, 𝑲∗∗ − 𝑲∗f (𝑲ff + 𝜎2𝑰)−1𝑲f∗ ).  ガウス過程の計算は本質的に O(𝑁3) オーダー なんとかして計算オーダーを落としたい ∠ ガウス過程のスパース近似 (SVGP)が有効1[1, 2]. 1和書では「ベイズ深層学習」(須山,2019) に(やたら)詳しい. 4
  4. ガウス過程が生成する関数 ガウス過程の尤度 𝑝(𝒚|𝑿) = N(𝟎, 𝑲ff + 𝜎2𝑰) は,𝒇 ∈

    ℝ𝑁 を補助的に導入することで 𝑝(𝒚|𝒇) = N(𝒇, 𝜎2𝑰) 𝑝(𝒇|𝑿) = N(𝟎, 𝑲ff ) と分解でき,実際 𝒇 を周辺化するともとの尤度 𝑝(𝒚|𝑿) にもどる. この 𝒇 をガウス過程の生成する関数の実現値,すなわち 𝒇 = (𝑓(𝒙1 ), … , 𝑓(𝒙𝑁 ))⊤ とみなし 𝑓 ∼ GP(0, 𝑘(𝒙, 𝒙′)) などと書く(平均関数を陽に考える場合もある) . 5
  5. ガウス過程の分解 ガウス過程の尤度は,𝑀1 個の 𝒛𝑚 ∈ X を導入することで,さらに 𝑝(𝒚|𝒇) = N(𝒇,

    𝜎2𝑰) 𝑝(𝒇|𝑿) = N(𝑲fu 𝑲−1 uu 𝒖, 𝑲ff − 𝑲fu 𝑲−1 uu 𝑲uf ) 𝑝(𝒖|𝒁) = N(𝟎, 𝑲uu ) と分解できる. ここで 𝑲uu ∈ 𝕊𝑀1 ++ は 𝒁 のグラム行列, 𝑲fu ∈ ℝ𝑁×𝑀1 は 𝒁 と 𝑿 とのカーネル出力を並べた行列. 𝒇, 𝒖 を周辺化するとやはりもとの尤度 𝑝(𝒚|𝑿) にもどる. 6
  6. スパース近似の概略 ガウス過程のスパース近似 (SVGP) の戦略: 1. 𝑀1 < 𝑁 個の誘導点 (inducing

    points) 𝒛𝑚 ∈ X を適当に配置 2. 𝑲ff ≈ 𝑲fu 𝑲−1 uu 𝑲uf =∶ 𝑸ff とグラム行列を低ランク近似 • 𝒁 のグラム行列が 𝑲uu ,𝒁 と 𝑿 とのカーネル出力を並べた 行列が 𝑲fu . 3. 任意の 𝑿∗ ∈ X とデータ点 𝑿・誘導点 𝒁 に対する関数出力 𝒇∗, 𝒇, 𝒖 の事後分布2 𝑝(𝒇∗, 𝒇, 𝒖|𝒚) = 𝑝(𝒇∗, 𝒇|𝒚, 𝒖)𝑝(𝒖) の変分事後分布 𝑞(𝒇∗, 𝒇, 𝒖) = 𝑝(𝒇∗, 𝒇|𝒚, 𝒖)𝑞(𝒖) による近似 がよくなるよう,KL ダイバージェンスを最小化 2実際には 𝑿, 𝑿∗, 𝒁 でも条件付けられているが,省略している. 7
  7. スパース近似の主結果 最小化したい目的関数は min 𝑞 KL[𝑞(𝒇∗, 𝒇, 𝒖)‖𝑝(𝒇∗, 𝒇, 𝒖|𝒚)] =

    min 𝑞 KL[𝑞(𝒇, 𝒖)‖𝑝(𝒇, 𝒖|𝒚)]. 𝑝(𝒖) = N(𝟎, 𝑲uu ) (⇔ 𝑢 ∼ GP(0, 𝑘(𝒛, 𝒛′)) であることを使えば, 上の KL ダイバージェンスを最小化する 𝑞(𝒖) は解析的に導ける ガウス過程のスパース近似 (SVGP) 𝑞(𝒖) = N(𝒎u , 𝑺u ) 𝒎u = 𝜎−2𝑲uu (𝑲uu + 𝜎−2𝑲uf 𝑲fu )−1𝑲uf 𝒚 𝑺u = 𝑲uu (𝑲uu + 𝜎−2𝑲uf 𝑲fu )−1𝑲uu 8
  8. スパース近似による計算量の削減 ガウス過程のスパース近似 (SVGP) 𝑞(𝒖) = N(𝒎u , 𝑺u ) 𝒎u

    = 𝜎−2𝑲uu (𝑲uu + 𝜎−2𝑲uf 𝑲fu )−1𝑲uf 𝒚 𝑺u = 𝑲uu (𝑲uu + 𝜎−2𝑲uf 𝑲fu )−1𝑲uu 変分事後分布 𝑞(𝒇, 𝒖) = 𝑝(𝒇|𝒖)𝑞(𝒖) の他の項は, 𝑝(𝒇|𝒖) = N(𝑲fu 𝑲−1 uu 𝒖, 𝑲ff − 𝑸ff ) で,予測分布も変分事後分布から解析的に(近似)計算できる.  これらの計算量は O(𝑁𝑀2 1 + 𝑀3 1 ) に削減された. 9
  9. ガウス過程が生成する関数の直交分解 SVGP では次の項が出てきた: 𝑝(𝒇|𝒖) = N(𝑲fu 𝑲−1 uu 𝒖, 𝑲ff

    − 𝑸ff ). このうち,誘導点 𝒁 の関数出力 𝒖 に依存するのは平均成分のみ. そこで,𝒇 を以下のように分解してみる: 𝒇 = 𝒇‖ + 𝒇⟂ , 𝒇‖ = 𝑲fu 𝑲−1 uu 𝒖 ∼ N(𝟎, 𝑲fu 𝑲−1 uu 𝑲uf ), 𝒇⟂ = N(𝟎, 𝑲ff − 𝑸ff ). これは 𝑓 ∼ GP(0, 𝑘(𝒙, 𝒙′)) を「誘導点 𝒁 で説明できる成分 𝑓‖ 」 と「その直交補空間上の成分 𝑓⟂ 」とに分解したことに相当. 10
  10. SOLVE-GP: Sparse OrthogonaL Variational infErence for GP 提案する SOLVE-GP では,𝒁

    ∈ ℝ𝑀1 ×𝑑 に加えてもう一組直交誘導 点 (orthogonal inducing points) 𝑶 ∈ ℝ𝑀2 ×𝑑 を導入. 直交誘導点の関数出力を 𝒗⟂ = 𝑓⟂ (𝑶) と書くと,同時分布は 𝑝(𝒚|𝒇⟂ + 𝑲fu 𝑲−1 uu 𝒖)𝑝(𝒖|𝒁)𝑝⟂ (𝒇⟂ |𝒗⟂ )𝑝⟂ (𝒗⟂ |𝑶). SVGP は 𝑞(𝒖) ≈ 𝑝(𝒖|𝒁) と変分事後分布をおいた状態に相当. SOLVE-GP では 𝑝⟂ (𝒗⟂ ) あるいは 𝑝⟂ (𝒗⟂ ), 𝑝⟂ (𝒇⟂ |𝒗⟂ ) の両方を変分 事後分布で置き換える. 以降はとくに後者の場合を議論する3. 3原論文では前者の設定も付録で扱っている. 11
  11. SOLVE-GP による変分下限 上記の方針では,𝑞(𝒗⟂ ) ∶= N(𝒎v , 𝑺v ) とおいて

    𝑞(𝒖, 𝒇⟂ , 𝒗⟂ ) = 𝑞(𝒖)𝑞(𝒗⟂ )𝑝⟂ (𝒇⟂ |𝒗⟂ ) という変分事後分布を考えることになる.これによる変分下限は 𝔼𝑞(𝒖)𝑞⟂ (𝒇⟂ ) [log 𝑝(𝒚|𝒇⟂ + 𝑲fu 𝑲−1 uu 𝒖)] − KL[𝑞(𝒖)‖𝑝(𝒖)] − KL[𝑞(𝒗⟂ )‖𝑝⟂ (𝒗⟂ )] と得られる.ここで 𝑞⟂ (𝒇⟂ ) ∶= ∫ 𝑝⟂ (𝒇⟂ |𝒗⟂ )𝑞(𝒗⟂ )𝑑𝒗⟂ = N(𝑪fv 𝑪−1 vv 𝒎v , 𝑺𝑓⟂ ) 𝑺𝑓⟂ ∶= 𝑪ff + 𝑪fv 𝑪−1 vv (𝑺v − 𝑪vv )𝑪−1 vv 𝑪vf 𝑪ff ∶= 𝑲ff − 𝑸ff で,𝑪fv などに関しては同様. 12
  12. SOLVE-GP による変分下限 SOLVE-GP の変分下限 SOLVE-GP の変分下限は次で与えられる: 𝔼𝑞(𝒖)𝑞⟂ (𝒇⟂ ) [log

    𝑝(𝒚|𝒇⟂ + 𝑲fu 𝑲−1 uu 𝒖)] − KL[𝑞(𝒖)‖𝑝(𝒖)] − KL[𝑞(𝒗⟂ )‖𝑝⟂ (𝒗⟂ )]  各種計算量は O(𝑁 ̄ 𝑀2 + ̄ 𝑀3) ( ̄ 𝑀 = max{𝑀1 , 𝑀2 }). 上記の変分下限は適当な設定のもと SVGP のそれよりタイト 13
  13. SOLVE-GP の変分下限:タイトネス これは SVGP の変分下限は log N(𝒚|𝟎, 𝑸ff + 𝜎2𝑰)

    − 1 2𝜎2 tr(𝑲ff − 𝑸ff ). 一方 SOLVE-GP の変分下限は,𝑞∗(𝒖) = 𝑝(𝒖|𝒇⟂ , 𝒚) と 𝒖 の変分事 後分布に 𝒇⟂ との依存関係を入れると, log N(𝒚|𝟎, 𝑸ff + 𝜎2𝑰) − 1 2𝜎2 tr(𝑲ff − 𝑸ff ) + 1 2𝜎4 tr{𝑲fu (𝑲uu + 𝜎−2𝑲uf 𝑲fu )−1𝑲uf (𝑲ff − 𝑸ff )}. 下線部は共通で,SOLVE-GP の変分下限の tr{⋅} の中は半正定値 ∠  よりタイトな変分下限が得られた 14
  14. 1 次元回帰 文献 [1] の簡単な ℝ → ℝ の回帰を解いてみる. 𝑀

    = 10 の SVGP と同等の良さ(𝑀 が 𝑟 倍になると逆行列は O(𝑟3) オーダーで計算量が増えることに注意) . SOLVE-GP は 𝑀1 + 𝑀2 = 10 だが,逆行列の計算量は O(𝑀3 1 + 𝑀3 2 ) のオーダー. 15
  15. CIFAR-10 with (Deep) Convolutional GPs たたみ込み演算を取り入れたカーネ ルによる GP である Convolutional

    GP と,その深層化である Deep Convolutional GP で CIFAR-10 を 判別. 17
  16. むすび ガウス過程の新たなスパース変分推論法である SOLVE-GP を提案 • 従来の SVGP より効率的かつ高性能 • 今回は割愛したが,ODVGP

    というスパース変分推論法 [3] を 特別な場合として含む • 充実の実験と Appendix • 激リスペクト • 教師ありガウス過程のお話なので,教師なし(GPLVM)バー ジョンに拡張してみたい…… 18
  17. References [1] Snelson E., Ghahramani Z., “Sparse Gaussian processes using

    pseudo-inputs.” NeurIPS 2006. [2] Titsias M., “Variational learning of inducing variables in sparse gaussian processes.” AISTATS 2009. [3] Salimbeni H., et al., “Orthogonally decoupled variational Gaussian processes.” NeurIPS 2018.