Microsoft PowerPoint - IBIS2012_open.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - IBIS2012_open.pptx"

めぐのしんまつ
5 years ago
Views:

1 カーネル法の新展開ーその理論と応用ー福水健次統計数理研究所 / 総合研究大学院大学第 15 回情報論的学習理論ワークショップ (IBIS2012) 筑波大学東京キャンパス 1

2 Outline 1. イントロダクション : カーネル法の概要 2. 確率分布の表現としてのカーネル法 3. 条件付確率の表現と推定精度 4. カーネル推論則 5. おわりに 2

3 データの高次元性, 非線形性高次元データに潜む非線形性, 複雑な構造生物, 遺伝, 文書, ソーシャルネットワーク, 宇宙, 気象, データの非線形性の抽出 Common practice: (X, Y, Z) (X, Y, Z, X 2, Y 2, Z 2, XY, YZ, ZX, ) 高次元性に伴う計算量爆発例 ) 10,000 次元データに 2 次特徴を加えると特徴空間の次元 = C C 2 = 50,005,000 (!) より効率的な方法は? カーネル法

4 正定値カーネルと再生核ヒルベルト空間定義. : 集合. Ω Ω が正定値であるとは,,, [ 対称 ] かつ任意の,,, に対し Gram 行列, が半正定値行列. 例 ) Gaussian RBFカーネル Laplace カーネル exp /2 exp 再生核ヒルベルト空間 (Reproducing kernel Hilbert space, RKHS) 正定値カーネルにより定まる,Ω 上の関数からなる関数空間. 特殊な内積を持つ.,, ( 再生性 ) 4

5 データ変換 :RKHS への特徴写像 x i x j 特徴写像 Φ xi Φ x j H 特徴空間上で線形データ解析を行う. SVM, PCA, CCA, etc 元のデータ空間特徴空間 ( 関数空間 ) 特徴ベクトル :,, Φ,,Φ カーネルトリック Φ,Φ,,,, 内積計算 : Φ, Φ,,,, β 5

6 線形アルゴリズムのカーネル化 ( 既存 ) 特徴ベクトルに対する線形アルゴリズムさまざまなカーネル法 e.g. カーネル PCA, 非線形 SVM, カーネル CCA, etc. 大きさ ( データ数 ) の Gram 行列計算に還元される. 高次元データに適する. c.f. 高次項による展開データ数が大きい時は低ランク近似が有効. カーネル法の新しい展開カーネル平均, 条件付カーネル平均を用いた確率分布の表現 Gram 行列計算によるノンパラメトリックな推論計算の実現 6

7 既存のノンパラメトリック推定平滑化カーネル ( 正定値とは限らない ): カーネル密度推定, 局所多項式 / 特性関数の方法 : スプライン, ウェーブレット, etc, etc, 次元の呪い平滑化カーネル : 高次元 (4, 5 次元ぐらい ) で困難カーネル法によるノンパラメトリック推定何ができるのか? 次元の呪いを解決しているか? 7

8 確率分布の表現としてのカーネル法 8

9 カーネル平均 : 特徴ベクトルの平均 : 可測空間 Ω 上に値を取る確率変数 ~ : Ω 上の正定値カーネル. : で定まるRKHS. Def. におけるのカーネル平均 : Φ,, 期待値の再生性,. カーネル平均はの高次モーメントの情報を持つ. 例 ), 0, e.g., モーメント母関数 9

10 特性的なカーネル (Fukumizu et al. JMLR 2004, AoS 2009; Sriperumbudur et al. JMLR2010) Def. 有界で可測な正定値カーネルが特性的 (characteristic) とは, P, が単射であることをいう. すなわち ~, ~,. 特性的なカーネルによるカーネル平均は, 確率分布を一意に定める. 例 : Gaussian, Laplace カーネル ( 多項式カーネル : 非特性的.) c.f. 特性関数. カーネル平均効率的な計算が可能. 10

11 カーネル法によるノンパラメトリック推論の原理特性的なカーネルにより, 確率分布に関する推論カーネル平均に関する推論計算分布の均一性検定 ( か?)? 独立性検定 (とは独立か?)? 11

12 RKHS における分散共分散 (X, Y: X Y に値を取る確率変数,,, : X, Y 上のRKHSと正定値カーネル Def. ( 非心化 ) 共分散作用素 :, : Φ Φ, Φ Φ 通常の共分散行列 ( 線形写像 ) のRKHS 値変数への一般化テンソル ( 積空間 ) との同一視 : Φ Φ 一般に線形写像 2 階のテンソル, ( ランク1の場合 ) 12

13 サンプルによる推定,,,,, ~, i.i.d., 推定量 : 標本平均, 標本共分散でOK 1,, 1,, さまざまな量が Gram 行列で表現可能 1/ オーダーでの一致性 (in norm) や中心極限定理が保証される (see e.g., Berlinet & Thomas Agnan 2004) 13

14 条件付確率の表現と推定精度 14

15 条件付カーネル平均 X, Y: ガウス確率変数 (, l,resp.) argmin l, 特性的なカーネルを用いると, 一般の X, Y に対し argmin Φ, Φ, Φ Φ Φ を与えたときのの条件付確率のカーネル平均 15

16 条件付カーネル平均の応用確率モデルに基づく推論 e.g. グラフィカルモデル ( 後述 ) 条件付独立性 / 依存性 (Fukumizu et al. JMLR 2004, AoS 2009, NIPS 2010) ノンパラメトリック回帰 (c.f. ガウス過程 / カーネルリッジ回帰 ),,,,,,, : 正則化係数 16

17 収束の速さ Y : 1 次元と仮定.X のみにカーネルを用いるガウス過程 / カーネルリッジ回帰一致性 1 (Eberts & Steinwart, NIPS2011), : ガウスカーネル,, ある種の緩い仮定のもと, 任意の > 0 に対し, Note: は, 線形推定量の最適オーダー (Stone 1982). * : オーダーの Sobolev 空間 17

18 一致性 2 (case: ) を特性的, Range ( 0) とするとき,,, 収束のレートは m ( の次元 ) に依存しない ( 次元の呪いの解消?) しかし一致性 1 のの場合より遅い. Gaussian RKHS, 稠密一致性 1 では, の任意の関数をGaussian RKHSのなる関数により近似する際の, モデル誤差の議論が必要. モデル誤差は次元に依存. 18

19 実験条件比較実験カーネルリッジ回帰 (Gaussカーネル) 局所線形回帰 (Epanechnikov kernel) (R: locfit パッケージ ), ~ 0,, ~ 0, 0.1 (A) exp (B), not included in Gaussian RKHS (C) 1/ 1.5 not included in Gaussian RKHS データ数 n = 100, 次元 m = 1,,10 (at most), 500 runs バンド幅, 正則化係数は CV で選択. 19

20 Kernel method Local linear Kernel method Local linear Mean square errors (A) exp Mean square errors (C) 1/ Dimension of X Mean square errors x Dimension of X Kernel method Local linear (B) Dimension of X 20

21 カーネル推論則 21

22 条件付確率を用いた推論則 Sum rule: Chain rule:, Bayes rule: カーネル化 : 変数の関係をすべてデータで表す ( ノンパラメトリック!) 分布をすべて ( 重み付 ) カーネル平均, 共分散作用素で表現 Gram 行列計算によって上記の計算ルールを実現する. 22

23 Kernel Sum Rule Sum rule: カーネル化 : Gram 行列表現 : l Input: Φ,,,,, ~, Φ,., Intuition: Φ, Φ Φ Φ Φ Φ 23

24 Kernel Chain Rule Chain rule:, カーネル化 : Gram 行列表現 : Input: l Φ,,,,, ~ Φ Φ,. Intuition: Note :, Φ Φ Φ From Sum Rule,, Φ Φ Φ Φ 24

25 Kernel Bayes Rule ベイズルール,. カーネルベイズルール (KBR, Fukumizu et al NIPS2011) ベイズ則は,, に対する, の回帰. Φ where, l Gram 行列表現 : Input: Φ,,,,, ~, Φ,,,,,, Λ Λ Λ, ΛDiag 25

26 KBR による推論 KBR は事後確率自身ではなく, そのカーネル平均を推定. Bayes 推論にどのように用いるか? に対するのノンパラメトリック回帰. KBR 推定量 ( 一致性 ) where,,. 点推定 : 数値的解法が必要 argmin Φ 26

27 カーネル推論則の応用例完全なノンパラメトリックベイズ推論分布の情報もサンプルで表現 c.f. いわゆるノンパラメトリックベイズ X 0 X 1 X 2 X 3 X T 応用例ノンパラメトリックHMM (Fukumizu et al. NIPS 2011) やをサンプルで表現. Kernel Approximate Bayesian Computation (Kernel ABC) (Nakagome, Fukumizu, Mano. 2012) 尤度関数が陽に書けない場合カーネル Belief Propagation (Song et al, AISTATS2011) Y 0 Y 1 Y 2 Y 3 Y T POMDP: Bellman 方程式のカーネル化 (Nishiyama et al UAI2012) 27

28 ノンパラメトリック HMM への応用 : カメラ角度の推定隠れ変数 : 室内に位置を固定されたビデオカメラの角度. 観測変数 : 部屋の動画像 + 人工ガウスノイズ. 20 x 20 RGB 画素 (1200 次元 ). noise KBR (Trace) Kalman filter(q) 2 = = Average MSE for camera angles (10 runs) To represent SO(3) model, Tr[AB 1 ] for KBR, and quaternion expression for Kalman filter are used. 28

29 おわりにカーネル法は, ノンパラメトリック推論の有力な方法論高次元データに対する適性 : 計算量, 推定精度カーネル平均, 共分散作用素に基づく推論則. 完全なノンパラメトリックな推論ベイズ推論が実現可能. セミパラメトリックなカーネルベイズへの展開パラメトリック部分 + ノンパラメトリック部分 ( カーネル法 ) 例 ) セミパラメトリックHMM 遷移過程 : 条件付確率 known 観測過程 :unknownだがデータが存在粒子フィルタ+カーネル法 (D40, 金川ら ) 厳密計算 +カーネル法 (D46, 西山ら ) X 0 X 1 X 2 X 3 X T Y 0 Y 1 Y 2 Y 3 Y T 29

30 Collaborators Bernhard Schölkopf (MPI) Arthur Gretton (UCL/MPI) Bharath Sriperumbudur (Cambridge) Le Song (Georgia Tech) 中込滋樹 (ISM) 間野修平 (ISM) 西山悠 (ISM) 金川元信 ( 奈良先端 ) 30

Microsoft PowerPoint - OsakaU_1intro.pptx

Microsoft PowerPoint - OsakaU_1intro.pptx カーネル法入門. カーネル法へのイントロダクション福水健次統計数理研究所 / 総合研究大学院大学大阪大学大阪大学大学院基礎工学研究科集中講義 204 September カーネル法 : 近年 990 年代半ばごろから発展したデータ解析の方法論. 非線形な情報や高次モーメントの扱いが容易. サポートベクターマシンの提案が発端となった. 2 線形なデータ解析非線形なデータ解析 3 データ解析とは?