カーネル法の新展開
ー その理論と応用 ー
福水健次

統計数理研究所 ／ 総合研究大学院大学

第15回情報論的学習理論ワークショップ（IBIS2012）2012.11.7‐9. @筑波大学東京キャンパス

1Outline1.

イントロダクション：2.

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

3.

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

4.

カーネル推論則

5.

おわりにカーネル法の概要

2

データの高次元性，非線形性• 高次元データに潜む非線形性，複雑な構造
生物，遺伝，文書，ソーシャルネットワーク，宇宙，気象，…

• データの非線形性の抽出
Common practice:(X, Y, Z)  (X, Y, Z, X2, Y2, Z2, XY, YZ, ZX, …)• 高次元性に伴う計算量爆発例） 10,000 次元データに２次特徴を加えると特徴空間の次元 = 10000C1 + 10000C2 = 50,005,000 (!)• より効率的な方法は？

 カーネル法

正定値カーネルと再生核ヒルベルト空間定義. : 集合.
,,Gram行列∶Ω Ω →が正定値であるとは，[対称] かつ任意の ∈ , , … ,∈  に対し,が半正定値行列．

例） Gaussian RBFカーネル exp ||Laplace カーネル∑exp|| /2||

• 再生核ヒルベルト空間（Reproducing kernel Hilbert space, RKHS）• 正定値カーネルにより定まる，Ω上の関数からなる関数空間．
• 特殊な内積を持つ．

,∙,（再生性）4データ変換：RKHSへの特徴写像
特徴写像xi

特徴空間上で線形データ解析を行う.
SVM, PCA, CCA, etc

H

Φ xi
x jΦ

xｊ

特徴空間(関数空間)

元のデータ空間• 特徴ベクトル:
•,…,

↦Φ

,…,Φ

カーネルトリック

Φ,Φ∙,∑

内積計算：,∑,Φ,,⋅,∑Φ,,∈,β5• 線形アルゴリズムのカーネル化（既存）• 特徴ベクトルに対する線形アルゴリズム
 さまざまなカーネル法
e.g. カーネルPCA, 非線形SVM, カーネルCCA, etc.
• 大きさ（データ数）の Gram 行列計算に還元される．

• 高次元データに適する.
c.f. 高次項による展開• データ数 が大きい時は低ランク近似 が有効．

• カーネル法の新しい展開• カーネル平均，条件付カーネル平均を用いた確率分布の表現• Gram行列計算によるノンパラメトリックな推論計算の実現

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

7

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

8

カーネル平均：特徴ベクトルの平均: 可測空間 Ω上に値を取る確率変数 ~ : Ω上の正定値カーネル.
: で定まるRKHS.
Def.

における のカーネル平均:≔Φ⋅,⋅,∈• 期待値の再生性,∀• カーネル平均は例）,の高次モーメントの情報を持つ.
⋯0 , e.g.,∈.

⋯モーメント母関数9特性的なカーネル(Fukumizu et al. JMLR 2004, AoS 2009; Sriperumbudur et al. JMLR2010)

Def. 有界で可測な正定値カーネル
P →,が特性的(characteristic) とは，↦が単射であることをいう．すなわち~⋅,~⋅,⇔

特性的なカーネルによるカーネル平均定める．
例: Gaussian, Laplace カーネル.

は，確率分布を一意に(多項式カーネル: 非特性的.).
c.f. 特性関数
カーネル平均  効率的な計算が可能.
10

カーネル法によるノンパラメトリック推論の原理

特性的なカーネルにより，確率分布に関する推論• 分布の均一性検定（⇒カーネル平均に関する推論・計算か？） • 独立性検定（ と は独立か？）

?
⊗?

11

RKHSにおける分散共分散(X , Y : X Y に値を取る確率変数,,,: X , Y 上のRKHSと正定値カーネルDef. (非心化) 共分散作用素
Φ•

Φ

:→,,:
Φ→
Φ

通常の共分散行列 （線形写像）のRKHS値変数への一般化• テンソル（積空間）との同一視：Φ⊗Φ∈⊗
一般に線形写像 ≅ 2階のテンソル↦,↔
⊗(ランク１の場合)
12サンプルによる推定, , ,…,,~ , i.i.d.,
推定量: 標本平均，標本共分散でOK
1⋅,,1⋅,⊗⋅,• さまざまな量がGram行列で表現可能• 1/ ‐オーダーでの一致性 (in norm) や中心極限定理が保証される (see e.g., Berlinet & Thomas‐Agnan 2004)13条件付確率の表現と推定精度

14条件付カーネル平均• X, Y: ガウス確率変数(∈,ℓ, resp.),argmin∈ ℓ• 特性的なカーネルを用いると, 一般のX , Y に対しargmin
∈

Φ

⊗,,ΦΦ

Φ

Φ
を与えたときのの条件付確率のカーネル平均15条件付カーネル平均の応用• 確率モデルに基づく推論 e.g. グラフィカルモデル（後述）• 条件付独立性／依存性 (Fukumizu et al. JMLR 2004, AoS 2009,NIPS 2010)• ノンパラメトリック回帰（c.f. ガウス過程/ カーネルリッジ回帰)|⋅⋅,,…,,…,

⋅,

∈

,

∈

: 正則化係数16収束の速さ
Y : 1次元と仮定．X のみに カーネルを用いる
|≔ガウス過程/ カーネルリッジ回帰• 一致性 1 (Eberts & Steinwart , NIPS2011)∈,：ガウスカーネル,仮定のもと，任意の > 0 に対し，|
Note:∈, ある種の緩い|→∞は，線形推定量の最適オーダー (Stone 1982).
*: オーダー のSobolev空間
17• 一致性 2 (case:を特性的，|∈)∈ Range（0）とするとき，,|,|• 収束のレートは m （ の次元）に依存しない（「次元の呪い」の解消？）
しかし「一致性1」の → ∞の場合より遅い．
• Gaussian RKHS ⊂, 稠密の任意の関数をGaussian RKHSの• 「一致性1」では，なる関数により近似する際の，モデル誤差の議論が必要．モデル誤差は次元に依存．
18

比較実験
• 実験条件カーネルリッジ回帰（Gaussカーネル）
局所線形回帰（Epanechnikov kernel） (R: ‘locfit’パッケージ）,(A)~0,,~0, 0.1

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0.040.015
Kernel method
Local linear

Kernel method
Local linear
Mean square errors

0.03
0.025
0.020.015

exp

(A)

0.01

0.005

(C)

0.01

1/ 1.5

| |

0.005
002

4
6
Dimension of X

28x 100010246
Dimension of X

810-3

Kernel method
Local linear
Mean square errors

Mean square errors

0.035

1.5

10.5

∑

(B)002

46Dimension of X

81020

カーネル推論則21

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

22

Kernel Sum Rule•Sum rule:•カーネル化：|≔•Gram行列表現：∑ℓInput:∑ΦΦ,,,…,,~,,.
,•

Intuition:

Φ,ΦΦ

Φ
Φ
Φ
23

Kernel Chain Rule•

Chain rule:,•

カーネル化：|≔•

Gram行列表現：∑ℓInput:∑•

Intuition:ΦΦ

Note,,,…,⊗Φ:→

From Sum Rule,⊗,~,,.
Φ⊗Φ⊗Φ, |Φ⊗ΦΦ⊗Φ

′24

Kernel Bayes’ Rule•

ベイズルール,•.

カーネルベイズルール (KBR, Fukumizu et al NIPS2011)
ベイズ則は，,に対する， → の回帰．

Φ|,where•

Gram行列表現： Input:
∑Φ
|,||

ΛΛ
DiagΛ

∑ℓΦ

,,,…,,~,,,…,

Λ,,25,

KBRによる推論
KBR は事後確率|自身ではなく，そのカーネル平均を推定．

Bayes推論にどのように用いるか？
•∈に対するのノンパラメトリック回帰

|→.

(一致性)

KBR推定量where•,…,.

点推定:
argmin|Φ

数値的解法が必要

26

カーネル推論則の応用例
完全な「ノンパラメトリック」ベイズ推論
分布の情報もサンプルで表現
c.f. “いわゆる”ノンパラメトリックベイズ

X0 X1 X2 X3…

Y0 Y1 Y2 Y3
応用例• ノンパラメトリックHMM (Fukumizu et al. NIPS 2011)
や|をサンプルで表現.

•YT

Kernel Approximate Bayesian Computation (Kernel ABC)(Nakagome , Fukumizu, Mano. 2012)

尤度関数が陽に書けない場合•カーネルBelief Propagation (Song et al, AISTATS2011)•POMDP: Bellman方程式のカーネル化

XT(Nishiyama et al UAI2012)27• ノンパラメトリックＨＭＭへの応用：カメラ角度の推定• 隠れ変数 : 室内に位置を固定されたビデオカメラの角度.
• 観測変数 : 部屋の動画像 + 人工ガウスノイズ.
• 20 x 20 RGB 画素 (1200次元 ).

noise

KBR (Trace)

Kalmanfilter(Q)2 = 10-4

0.15

0.01

0.560.02

2 = 10-3

0.21 0.01

0.54

0.02

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

おわりに
• カーネル法は，ノンパラメトリック推論の有力な方法論• 高次元データに対する適性：

計算量，推定精度• カーネル平均，共分散作用素に基づく推論則.
• 完全な「ノンパラメトリック」な推論• ベイズ推論が実現可能.

• セミパラメトリックなカーネルベイズへの展開• パラメトリック部分 ＋ ノンパラメトリック部分（カーネル法）
例）セミパラメトリックHMM
XT
X0 X1 X2 X3
遷移過程：条件付確率known…
観測過程：unknownだがデータが存在• 粒子フィルタ＋カーネル法（D40, 金川ら） Y Y Y YYT0123• 厳密計算＋カーネル法（D46, 西山ら）
29

Collaborators

Bernhard Schölkopf (MPI)

Arthur Gretton (UCL/MPI)Le Song (Georgia Tech)
Bharath Sriperumbudur (Cambridge)

中込滋樹(ISM)

間野修平(ISM)

西山悠(ISM)

金川元信(奈良先端)30