47, 2, Multiple Kernel Learning Learning Theory of Multiple Kernel Learning Taiji Suzuki Multiple Kernel Learning (MKL) l 1 - l 1 - l 2

141頁∼157頁  

Multiple Kernel Learning の学習理論

鈴木 大慈

^∗

Learning Theory of Multiple Kernel Learning

Taiji Suzuki

^∗

Multiple Kernel Learning (MKL)について正則化法およびベイズ推定法を紹介し，その汎化

誤差解析について概説する．正則化法については，`1-正則化およびエラスティックネット型の正 則化を考察する．エラスティックネット型の正則化はスパース性を誘導する`1-正則化と滑らか さを制御する`2-正則化の組み合わせで表される．ベースとなるカーネル関数の数は多くても，真 の関数に必要なカーネル関数の数は少ないスパースな状況を考察し，これまで得られていたレー トよりも速い収束レートを導出する．さらに，ガウシアンプロセス事前分布を用いたベイズ推定 量を考察し，一次独立性の条件を仮定せずとも速い収束レートを達成できることを示す．

We review convergence rate analyses about multiple kernel leaning (MKL) by regularization methods and a Bayes method. As for regularization methods, we show convergence rates for

`1 and elastic-net regularizations. The elastic-net regularization is a composition of an `1- regularizer for inducing the sparsity and an`2-regularizer for controlling the smoothness. We focus on a sparse setting where the total number of kernels is large but the number of non-zero components of the ground truth is relatively small, and show sharper convergence rates than the learning rates ever shown for both`1 and elastic-net regularizations. Moreover, we show that, using a Bayesian method with Gaussian process priors, we don’t need a strong conditions on the design to achieve a fast learning rate.

キーワード: Multiple Kernel Learning，カーネル法，統計的学習理論，高次元スパース推定，正 則化法

1.

はじめに

サポートベクトルマシンに代表されるように，カーネル法は長い間，機械学習において 中心的な役割を果たしてきた

(Sch¨ olkopf and Smola (2002), Shawe-Taylor and Cristianini (2004))．しかし，その精度はカーネルの選択に大きく依存し，いかにして良いカーネルを

選ぶかという問題はカーネル法の利用において常に問題になってきた．カーネルを選ぶ方 法として，これまで例えば交差検証法

(Chapelle et al. (2002))

や「カーネル学習」のア

∗ 東京大学，JSTさきがけ，理研AIP：〒113-8656東京都文京区本郷7-3-1 (E-mail: [email protected])．

プローチ

(Ong et al. (2005), Argyriou et al. (2006), Bach (2009), Cortes et al. (2009a), Varma and Babu (2009))

といった方法が提案されてきた．

その中でも系統だった手法としてマルチプルカーネル学習

(MKL, multiple kernel learn- ing)

と呼ばれる手法がある．これは，候補となるカーネルの最適な線形結合を凸最適化に よって見つける手法である

(Lanckriet et al. (2004))

．

Bach et al. (2004)

によると，

MKL

は

`

1

-

混合ノルム正則化手法とみなせることが示されている．この定式化により，

MKL

は スパース加法モデルのスパース正則化推定手法ともみなすことができる．また，正則化と カーネルの線形結合の重みの最適化を結び付けて考えることで，MKLの様々なバリエー ションが提案されてきた．例えば，スパース正則化（`<sub>1</sub>）とリッジ正則化（`₂）の間の「中間 的」な正則化として，エラスティックネット型正則化

(Shawe-Taylor (2008), Tomioka and Suzuki (2009))

や

`

p

-混合ノルム正則化 (1 < p < 2) (Micchelli and Pontil (2005), Kloft et al. (2009))

といった拡張が提案されてきた．

これら

MKL

の定式化および学習アルゴリズムの研究と同時に，その統計的解析の研究も 進められてきている．

`

1

-

混合ノルム正則化に関しては，

Koltchinskii and Yuan (2008)

が，

適切な仮定のもと，

d

^1−s1+s

n

^−1+s1

+ d log(M )/n

という汎化誤差の収束レートを導出している．

ここで，nはサンプルサイズで，

d

は真のカーネル重みの非ゼロ要素の数，また，Mはベー スとなるカーネルの数で，s

(0 < s < 1)

はそれらベースとなるカーネルに対応した再生 核ヒルベルト空間

(RKHS, reproducing kernel Hilbert space)

の複雑さを表すパラメータ である．なお，彼らの解析では，真の関数の滑らかさに強い仮定をおいている．Meier

et

al. (2009)

はエラスティックネット型正則化を考察しほぼミニマックス最適な収束レート

d (n/ log(M ))

^−1+s1 を導出している．Koltchinskii and Yuan (2010)は

`

1

-混合ノルム正則化

の変形版を考察し，

(これを `

1

-MKL

と本稿では呼ぶ)それがミニマックス最適レートを達成 し，

log(M )

への依存性を

Meier et al. (2009)

によるものより改善した

dn

^−1+s1

+d log(M )/n

なる汎化誤差バウンドを導出した．その他の方向として，真の関数にスパース性を仮定せ ず，ベースとなるカーネルのクラスの

Rademacher

複雑度を解析するなどして汎化誤差を 導出する研究もある

(Srebro and Ben-David (2006), Ying and Campbell (2009), Cortes et al. (2009b), Kloft et al. (2010), Suzuki (2011)).

本稿では，`₁

-MKL

やエラスティックネット型

MKL

のシャープな学習レートを示した

Suzuki and Sugiyama (2012, 2013)

の結果およびベイズ推定量のシャープな汎化誤差バウ ンドを導出した

Suzuki (2012)

の結果を紹介する．Suzuki and Sugiyama (2012, 2013)は，

次の収束レートを導出した:

(`

1

-MKL) d

^1−s1+s

n

^−1+s1

R

2s 1+s

1,f∗

+ d log(M )

n ,

(Elastic-net MKL) d

^1+q+s1+q

n

^−1+q+s1+q

R

2s 1+q+s

2,g∗

+ d log(M )

n .

ただし，

R

1,f∗は真の関数の

`

1

-混合ノルムで， R

2,g∗は真の関数のある種の

`

2

-混合ノルムで

あり，q

(0 ≤ q ≤ 1)

は真の関数の滑らかさを表すパラメータである．ここで，真の関数が ある関数に積分核を作用させたものであるとき，真の関数は「滑らかである」と呼ぶ

(仮定 3.2

を参照せよ

)

．直観的には

q

が大きいほど，真の関数は「滑らか」である．エラスティッ クネット型

MKL

は真の関数の滑らかさを適切に利用していると言える．すなわち，真が 滑らかであるほど，エラスティックネット型

MKL

の収束レートは改善されてゆく．

Meier et al. (2009)

と

Koltchinskii and Yuan (2010)

は

q = 0

の状況に対応し，Koltchinskii and

Yuan (2008)

は

q = 1

である状況に対応する．我々の解析はこれら二つの状況を包含し，

0 ≤ q ≤ 1

の全てを含む．この結果から，スパース性と滑らかさの間にトレードオフの関係 が見て取れる．`₁

-MKL

はエラスティックネット型よりもよりスパースな解を出しやすい が，エラスティックネット型正則化はより滑らかな解を出しやすい．それによって，真の 滑らかさが弱い場合

(q = 0)，`

₁

-MKL

がより速い収束レートを達成し，そうでない場合，

エラスティックネット型がより速い収束レートを達成する．

上記の解析には，制限固有値条件のような，入力分布へのやや強い条件が必要である．

そこで，

Suzuki (2012)

では，ベイズ推定量を用いることで，そのような条件がなくても速

い収束レート

(fast convergence rate)

が達成可能であることが示されている．そこでは，

PAC-Bayes

の技法をノンパラメトリックなガウス過程回帰の理論を組み合わせることで，

MKL

のベイズ推定量版が制限固有値条件を仮定せずともミニマックス最適レートを達成 することが示されている．

2.

問題設定と

MKL

{ (x

_i

, y

_i

) }

ⁿi=1を

n

個の観測値とし，各

x

_iは集合

X

から周辺分布

Π

に従って独立同一に 生成された確率変数で，y_i

∈ R

は

x

_iに対する出力とし，

y

i

= f

^∗

(x

i

) +

i

というモデルに従って生成されているとする．なお，

iは

x

iと独立な観測ノイズである．

今，

M

個の正定値対称カーネル関数

k

m

(m = 1, . . . , M )

があり，それぞれのカーネル関数

k

_mに対応する再生核ヒルベルト空間を

H

mとする．真の関数は

f

^∗

(x) =

∑

M m=1

f

_m^∗

(x)

と

f

_m^∗

∈ H

mを用いて書けると仮定する．ここで，

k f

m

k

_Hmで

f

m

∈ H

mの

RKHS

ノルム を表す．

このモデルを学習する方法として

MKL

があるが，MKLは以下のように定式化される．

Aronszajn (1950)

によると，カーネル関数

k

mの和で表されるカーネル関数

k ¯ = ∑

M m=1

k

m

に対応する再生核ヒルベルト空間

H ¯

の元は全て

f = ∑

M

m=1

f

m

(f

m

∈ H

m

)

の形で書け，そ の

RKHS

ノルム

k f k

_H^¯は

k f k

²H¯

= inf {

_M

∑

m=1

k f

_m

k

²_Hm

| f =

∑

M m=1

f

_m

, f

_m

∈ H

m

(m = 1, . . . , M) }

で与えられる．さらに，この結果を拡張することで，d_m

> 0

を満たす重み

(d

_m

)

^M_m=1を用 いてカーネルの重み付き和

¯ k = ∑

M

m=1

d

_m

k

_mに対応する再生核ヒルベルト空間

H ¯

に含ま れる元

f

の

RKHS

ノルムは

k f k

²H¯

= inf {

_M

∑

m=1

k f

m

k

²_Hm

d

_m

| f =

∑

M m=1

f

m

, f

m

∈ H

m

(m = 1, . . . , M) }

(2.1)

で与えられる．今，カーネル関数

¯ k

を用いたカーネルリッジ回帰は

inf

f∈H¯

1 n

∑

n i=1

(y

i

− f (x

i

))

²

+ λ k f k

²H¯

なる最適化問題で記述できる．ただし，λ >

0

は正則化の強さを調整する正則化パラメー タである．すると，式

(2.1)

より，これは

inf

f_m∈Hm

(m=1,...,M)

1 n

∑

n i=1

( y

_i

−

∑

M m=1

f

_m

(x

_i

) )

2

+ λ

∑

M m=1

k f

m

k

²_Hm

d

m

と同値である．これに加え，さらに重み

(d

m

)

^M_m=1もデータに合わせて選ぶことを考える．そ こで，重みに関する正則化を表す関数

h : R

^M+

→ R

+

∪ {∞}

を用いて¹⁾，

d = (d

1

, . . . , d

M

)

^>

として

inf

f_m∈Hm

(m=1,...,M), d∈R^M+

1 n

∑

n i=1

( y

_i

−

∑

M m=1

f

_m

(x

_i

) )

2

+ λ (

_M

∑

m=1

k f

m

k

²_Hm

d

m

+ h(d) )

(2.2)

なる最適化問題を考える．表現定理

(Kimeldorf and Wahba (1971))

によって，この最適 化問題は有限次元最適化問題に帰着される．

例

2.1 (ノルム制約による `

₁

-正則化)

h(d) =

 



 

0 ( ∑

M

m=1

d

_m

≤ 1),

∞ (otherwise),

1) ここでR⁺:={a∈R|a≥0}

とする．この時，最適化問題

(2.2)

における

(d

m

)

^M_m=1の最適解は

d

m

=

PM^kfmkHm m0=1kf_m0kHm0

で 与えられ，最適化問題

(2.2)

は

min

f_m∈Hm

(m=1,...,M)

( y

_i

−

∑

M m=1

f

_m

(x

_i

) )

2

+ λ (

_M

∑

m=1

k f

_m

k

_Hm

)

2

と書き直せる．

例

2.2 (

ノルム罰則による

`

1

-

正則化

) h(d) = ∑

m

m=1

d

mとすると，最適化問題

(2.2)

に おける

(d

m

)

^M_m=1の最適解は

d

m

= k f

m

k

Hmで与えられ，最適化問題

(2.2)

は

min

fm∈Hm

(m=1,...,M)

( y

i

−

∑

M m=1

f

m

(x

i

) )

²

+ 2λ

∑

M m=1

k f

m

k

_Hm

と書き直せる．

これら二つの例は正則化パラメータ

λ

を適切に設定することで，同値であることが示せる．

もとの

MKL (Lanckriet et al. (2004))

は，例

2.1

の形式で定式化されているが，上記の観 測から，`₁

-正則化学習とみなせることがわかる (Bach et al. (2004))．特に，この定式化

によって効率的な最適化手法が導出できる

(Sonnenburg et al. (2006), Rakotomamonjy et al. (2008), Suzuki and Tomioka (2011))．

さらに，これを拡張することで，以下の変種を得られる．

例

2.3 (Tikhonov

型

`

p

-ノルム正則化) 1 ≤ p ≤ 2

に対して，

h(d) =

 



 

0 ( ∑

M

m=1

d

^p/(2m ^−p)

≤ 1),

∞ (otherwise),

とする（ただし，p

= 2

のときは，h(d) = 1 (if max_m=1,...,M

d

m

≤ 1), 0 (otherwise)

とす る）．この時，最適化問題

(2.2)

における

(d

m

)

^M_m=1の最適解は

d

m

=

^kfmk

2−pHm

(PM

m0=1kf_m0k^p_Hm0)(2−p)/p

で与えられ，最適化問題

(2.2)

は

min

f_m∈Hm

(m=1,...,M)

( y

_i

−

∑

M m=1

f

_m

(x

_i

) )

2

+ λ (

_M

∑

m=1

k f

_m

k

^p_Hm

)

_p²

と書き直せる．

例

2.4 (Ivanov

型

`

p

-ノルム正則化) 1 ≤ p < 2

に対して，h(d) = ²⁻_p^p

∑

m

m=1

d

^p/(2m ^−p)

とすると，最適化問題

(2.2)

における

(d

m

)

^M_m=1の最適解は

d

m

= k f

m

k

²_H⁻_m^pで与えられ，最

適化問題

(2.2)

は

min

fm∈Hm

(m=1,...,M)

( y

i

−

∑

M m=1

f

m

(x

i

) )

2

+ 2λ p

∑

M m=1

k f

m

k

^p_Hm

と書き直せる．

一方で，正則化項を直接修正して，ある

g : R

^M+

→ R

を用いて

min

f_m∈Hm

(m=1,...,M)

1 n

∑

n i=1

( y

_i

−

∑

M m=1

f

_m

(x

_i

) )

2

+ λg (

k f

₁

k

²_H1

, . . . , k f

_M

k

²_HM

)

(2.3)

と一般化することも考えられる．

例

2.5 (

エラスティックネット型正則化

)

最適化問題

(2.3)

において

g(q

1

, . . . , q

M

) =

∑

M

m=1

(θ √ q

_m

+ (1 − θ)q

_m

)

とすればエラスティックネット型の正則化が得られ，最適化問 題

(2.3)

は

min

f_m∈Hm

(m=1,...,M)

1 n

∑

n i=1

( y

_i

−

∑

M m=1

f

_m

(x

_i

) )

2

+ λ

∑

M m=1

( θ k f

_m

k

_Hm

+ (1 − θ) k f

_m

k

²_Hm

)

となる．

実は，定式化

(2.2)

と

(2.3)

は互いに双対の関係として結び付けることが可能である

(Tomioka and Suzuki (2010))．

定理

2.1 h : R

^M+

→ R

は真閉凸関数で，原点で

0

であるとする．また，

x, y ∈ R

^M+ が

x

m

≤ y

mをすべての

m ∈ { 1, . . . , M }

で満たすなら，

h(x) ≤ h(y)

を満たすと仮定する．

すると，

˜ h(y) := − h(1/y

₁

, . . . , 1/y

_M

)

は凹関数である．また，

g(x) = 1 2 inf

y∈R^M+

{

x

^>

y − ˜ h(y) }

とすると，定式化

(2.2)

と

(2.3)

は同値，すなわち最適解は等しい．さらに，gが微分可能 なら，最適な重み

(d

m

)

^M_m=1は最適解

f ˆ = ( ˆ f

1

, . . . , f ˆ

M

)

を用いて，

d

_m

= (

2 ∂g( k f ˆ

1

k

²_H1

, . . . , k f ˆ

M

k

²_HM

)

∂x

m

)

₋1

で与えられる．

詳細は

Tomioka and Suzuki (2010)

を参照されたい．

3. Preliminaries

前節で導入した

MKL

の正則化法としての定式化をもとにして，その汎化誤差の評価を 行う．そのため，いくつかの準備を行う．

定式化 ここでは，エラスティックネット型

MKL

を考える．例

2.5

で与えられた正則化 は実用上は有用であるが，理論的にはこれを用いてミニマックス最適なレートを導出する ことは難しい．そこで，Meier

et al. (2009)

によって提案された変種を考える:

f ˆ = arg min

fm∈Hm (m=1,...,M)

1 n

∑

n i=1

( y

_i

−

∑

M m=1

f

_m

(x

_i

) )

2

+

∑

M m=1

(

λ

⁽ⁿ⁾₁

k f

_m

k

n

+ λ

⁽ⁿ⁾₂

k f

_m

k

_Hm

+λ

⁽ⁿ⁾₃

k f

_m

k

²_Hm

) .

(3.1)

ただし，

k f

m

k

n

:=

√

1 n

∑

n

i=1

f

m

(x

i

)

²である．これは，例

2.5

で与えたエラスティックネッ ト型正則化に

∑

M

m=1

k f

m

k

nが足されたものである．実用上はこの項がなくても問題なく精 度は出るが，理論上はこの項によってミニマックス最適レートを達成することが証明でき る．なお，

Koltchinskii and Yuan (2010)

は

∑

m

λ

⁽ⁿ⁾₁

k f

m

k

n

+ λ

⁽ⁿ⁾₂

k f

m

k

Hm だけからなる

`

₁

-正則化を考えている．λ

⁽ⁿ⁾₃

= 0

の状況と

λ

⁽ⁿ⁾₃

> 0

の状況を分けるため，λ⁽ⁿ⁾₃

= 0

にお ける学習方法

(3.1)

を

`

₁

-MKL

と呼び，λ⁽ⁿ⁾₃

> 0

の時はエラスティックネット型

MKL

と 呼ぶ.

表現定理

(Kimeldorf and Wahba (1971))

によって，最適解

f ˆ

は

nM

個のカーネル関数 の線形和で書き下せる:

∃ α

m,i

∈ R , f ˆ

m

(x) = ∑

n

i=1

α

m,i

k

m

(x, x

i

).

よって，グラム行列

K

m

= (k

m

(x

i

, x

j

))

i,jを用いて，式

(3.1)

内の正則化項は

∑

M m=1

( λ

⁽ⁿ⁾₁

√

α

^>_m

K

_m

K

_m

n α

m

+ λ

⁽ⁿ⁾₂

√

α

^>_m

K

m

α

m

+ λ

⁽ⁿ⁾₃

α

^>_m

K

m

α

m

)

とある

α

m

= (α

m,i

)

ⁿ_i=1

∈ R

ⁿを用いて表すことができる．このことから，最適化問題は有 限次元最適化問題に帰着され，Bach

et al. (2004)

にあるように

SOCP (second-order cone programming)

で解いたり，座標降下法を適用したり

(Meier et al. (2008))，もしくは交互

方向乗数法を用いることで解くことができる

(Boyd et al. (2011))

．

表記と仮定 ここでは，理論に必要な仮定を与える．

H = H

1

⊕· · ·⊕H

M

= { f

₁

+ · · · +f

_M

| f

_m

∈ H

m

(m = 1, . . . , M ) }

とする．ここで，多少表記の濫用を許して，f

∈ H

の表記に よって，f

= ∑

M

m=1

f

mを与える積集合の元

(f

1

, . . . , f

M

) ∈ H

1

× · · · × H

M も表すことに する．この分解は一意とは限らないが，特に混乱がない場合はこの表記を用いる．

以下の条件を仮定する．

仮定

3.1 (基本的条件)

(A3.1 -1) f

^∗

= (f

₁^∗

, . . . , f

_M^∗

) ∈ H

が存在して，E[Y

| X ] = ∑

M

m=1

f

_m^∗

(X )

が成り立つ．ま た，雑音

:= Y − f

^∗

(X )

は有界である：

| | ≤ L．

(A3.1 -2)

各

m = 1, . . . , M

において，

H

mは可分でかつ

sup

_X∈X

| k

m

(X, X) | ≤ 1

が成り 立っている．

最初の仮定

(A3.1 -1)

は

H

が真の関数を含むこと，および

| | ≤ L

なる条件によって

f

が

f

に関して

Lipschitz

連続であることを保証する．これらの仮定は本質的ではなく，モ

デルに真が含まれていない状況や雑音がガウス分布のような非有界な設定に拡張できる

(Raskutti et al. (2012)).

しかし，理論の簡単さのためこれらの仮定をおく．(A3.1 -2)の条 件は

k f

m

k

∞

≤ k f

m

k

Hm を与えることが知られている

(Steinwart and Christmann (2008)

の

Chapter 4

を参照せよ

)

．

カーネル関数の仮定より

sup

_x,x0

| k

m

(x, x

⁰

) | ≤ sup

_x

| k

m

(x, x) | ≤ 1

なので，積分作用素

T ˜

m

: L

2

(Π) → L

2

(Π)

を

( ˜ T

m

f )(x) =

∫

k

m

(x, y)f (y)dΠ(y)

とすると，

T ˜

mはヒルベルト

-

シュミット作用素で，特にコンパクトである．さらに，カー ネル関数

k

mは正定値対称なので，ある非負実数の列

(µ

`,m

)

^∞_`=1と

L

2

(Π)

内の正規直交系

(φ

_`,m

)

^∞_`=1 が存在して，

T ˜

_m

=

∑

∞

`=1

µ

_`,m

h· , φ

_`,m

i

L₂(Π)

φ

_`,m

と分解できる（収束は作用素ノルムに関して成り立つ）（例えば，Reed and Simon (1981) を参照されたい）．この表記に従うと，

k

m

(x, x

⁰

) =

∑

∞

`=1

µ

`,m

φ

`,m

(x)φ

`,m

(x

⁰

) (3.2)

も成り立つ（収束は

L

2

(Π × Π)

に関して成り立つ）．このスペクトル分解に従うと，再生 核ヒルベルト空間

H

m内の内積は

h f

_m

, g

_m

i

Hm

= ∑

_∞

`=1

µ

⁻_`,m¹

h f

_m

, φ

_`,m

i

L₂(Π)

h φ

_`,m

, g

_m

i

L₂(Π)

で与えられる．作用素

T

_m

: H

m

→ H

mを

h f

_m

, T

_m

g

_m

i

_Hm

:= E[f

_m

(X )g

_m

(X)],

を任意の

f

m

, g

m

∈ H

mに対して満たすものとして定義する．f_m

∈ H

mは

k f

m

k

_Hm

≤

k f

m

k

_∞が成り立つことより，

f

m

∈ L

2

(Π)

でもある．この自然な埋め込みを

ι : H

m

, → L

2

(Π)

と書くと，T_m

= ι

⁻¹

◦ T ˜

m

◦ ι

であることが確認できる．

仮定

3.2 (畳み込みの条件)

ある実数

0 ≤ q ≤ 1

と

g

_m^∗

∈ H

mが存在して，

(A3.2 ) f

_m^∗

(x) =

∫

X

k

^(q/2)_m

(x, x

⁰

)g

^∗_m

(x

⁰

)dΠ(x

⁰

) ( ∀ m = 1, . . . , M),

が成り立つ．ただし，

k

m^(q/2)

(x, x

⁰

) = ∑

_∞

k=1

µ

^q/2_k,m

φ

k,m

(x)φ

k,m

(x

⁰

)

である．これは，次の作 用素を用いた表現と同等である

:

f

_m^∗

= T

q

m2

g

_m^∗

. g

^∗

∈ H

を

g

^∗

= (g

₁^∗

, · · · , g

_M^∗

)

もしくは

g

^∗

= ∑

M

m=1

g

^∗_mと定義する．

定数

q

は真の関数

f

_m^∗ の滑らかさを表現している．なぜなら，

f

_m^∗ は積分核

k

^(q/2)m を

g

^∗_mに作 用させて得られており,

q

が大きいほど

“高周波成分”

が抑制されるからである．よって，q が大きくなるほど

f

^∗は

“滑らか”

になることがわかる．仮定

(A3.2)

は

Caponnetto and de

Vito (2007)

で考察され，カーネルリッジ回帰の収束レートの解析に使われている．MKL

の設定では，

Koltchinskii and Yuan (2008)

が

q = 1

の仮定のもと

MKL

の速い収束レート を導出しており，

Bach (2008)

は

q = 1

を仮定して

MKL

におけるカーネル選択の一致性を 示している．

Bach (2008)

の

Proposition 9

は，仮定

(A3.2)

が

q = 1

で成り立つための十 分条件を平行移動不変カーネル

k

_m

(x, x

⁰

) = h

_m

(x − x

⁰

)

に対して与えている．Meier

et al.

(2009)

は

Sobolev

空間で

q = 0

の状況を考えている．Koltchinskii and Yuan (2010)の解 析は

q = 0

に対応している．ここで，仮定

(A3.2)

が

q = 0

で成り立っていても，真の関数 の滑らかさに関して何も仮定していないことに注意されたい．

畳み込み条件

(A3.2)

のもとでは，qが増加するごとに収束レートが良くなることが期待 される．この予想は確かに成り立つが

(式 (4.3)

および

Steinwart et al. (2009))，学習時に

用いるモデルはこの条件によって制限を受けず変わらないため，これは自明ではないこと に注意されたい．

次に，再生核ヒルベルト空間の

“

複雑さ

”

を表すパラメータを導入する．

仮定

3.3 (スペクトル条件)

ある実数

0 < s < 1

と

0 < c

が存在し，カーネル

k

_mのス ペクトル

{ µ

_j,m

}

^∞j=1

(式 (3.2)

を参照)が

(A3.3) µ

j,m

≤ cj

^−1s

, (1 ≤ ∀ j, 1 ≤ ∀ m ≤ M ),

を満たす．

スペクトル条件

(A3.3)

はカバリングナンバーへの制約条件として書き換えられることが 知られている²⁾

(Steinwart et al. (2009)): log[ N (, B

_Hm

, L

2

(Π))] ≤ c

⁰

^−2s

.

2) -カバリングナンバーN(,BHm, L2(Π))は，再生核ヒルベルト空間Hmの単位球BHmをL2(Π)-距離で 測った半径の球で覆うのに必要な最小の球の数である．(van der Vaart and Wellner (1996)).

I

0を真の関数に使われるカーネルのインデックスとする：

I

₀

:= { m | k f

_m^∗

k

Hm

> 0 } . I

0の要素数を

d := | I

0

|

とする．

f = ∑

M

m=1

f

m

∈ H

と

I ⊆ { 1, . . . , M }

に対し，

H

I

=

⊕

m∈I

H

mとし，

f

I

∈ H

I を

f

をインデックス集合

I

に制限したものとする

, i.e., f

I

=

∑

m∈I

f

m

. I ⊆ { 1, . . . , M }

に対して

, κ(I)

を

I

に含まれる再生核ヒルベルト空間の間の相 関を表す量とする:

κ(I) := sup {

κ ≥ 0 κ ≤ k ∑

m∈I

f

_m

k

²L₂(Π)

∑

m∈I

k f

m

k

²_L2(Π)

, ∀ f

m

∈ H

m

(m ∈ I) }

.

同様に，Iと

I

^cの間の相関にあたる量を次のように定義する:

ρ(I) := sup

{ h f

I

, g

I^c

i

L2(Π)

k f

_I

k

L₂(Π)

k g

_Ic

k

L₂(Π)

f

I

∈ H

I

, g

I^c

∈ H

I^c

, f

I

6 = 0, g

I^c

6 = 0 }

.

これらの量を用いることで

f ∈ H

の

L

₂

(Π)-ノルムを { f

_m

}

m∈I の

L

₂

(Π)-ノルムで下から

評価することができる．

補題

3.1

任意の

I ⊆ { 1, . . . , M }

に対して，以下が成り立つ

: k f k

²L2(Π)

≥ (1 − ρ(I)

²

)κ(I)

( ∑

m∈I

k f

_m

k

²L2(Π)

)

. (3.3)

κ(I

₀

)

と

ρ(I

₀

)

に次の仮定をおく．

仮定

3.4 (独立性条件)

真の非ゼロ要素

I

0に対し，κ(I₀

)

は正の値をとり

ρ(I

0

)

は

1

よ り真に小さい

:

(A3.4) 0 < κ(I

0

)(1 − ρ

²

(I

0

)).

この条件は

incoherence condition

として

Koltchinskii and Yuan (2008), Meier et al.

(2009)

で用いられている．

最後に，

sup-

ノルムに次の技術的な条件を課す．

仮定

3.5 (Sup-ノルム条件)

スペクトル条件

(A3.3)

に加え， ある定数

C

₁が存在して，

次が成り立つ：

(A3.5) k f

_m

k

∞

≤ C

₁

k f

_m

k

¹_L⁻_2(Π)^s

k f

_m

k

^s_Hm

( ∀ f

_m

∈ H

m

, m = 1, . . . , M ),

ただし，sはスペクトル条件

(A3.3)

で現れた定数である．

この条件はやや強いように見えるが，再生核ヒルベルト空間がある

Sobolev

空間に連続的 に埋め込まれる場合は成り立つ．例えば，ガウシアンカーネルに対応する再生核ヒルベル ト空間は任意の

Sobolev

空間に連続的に埋め込まれるので，sup-ノルム条件

(A3.5)

は満た される．

4.

収束レート解析

この節では，MKLの収束レートを示す．

4.1 `

1

-MKL

とエラスティックネット型

MKL

の収束レート

ここでは，式

(3.1)

で与えられる推定量

f ˆ

の汎化誤差の評価を与える

(この結果は Suzuki and Sugiyama (2012, 2013)

で示されたものである

)

．ここで，カーネルの数

M

と真の非 ゼロ要素の数

d

はサンプルサイズ

n

に応じて増加することも許す．全ての結果は有限サン プルサイズで成り立つものである．

Koltchinskii and Yuan (2010), Raskutti et al. (2012)

は，

`

_∞

-混合ノルムに関する単位球において最適レートを導出しているが，ここではより精

密なレートが導出できることを示す．特に，`₁

-混合ノルムに関する単位球や `

₂

-混合ノル

ムに関する単位球における最適レートを達成できることが示され，それらは

`

_∞

-混合ノル

ム球の最適レートよりも速い．

η(t) (t > 0)

と

ξ

n

(λ) (λ > 0)

を次のように定義する:

η(t) := max(1, √ t, t/ √

n), (4.1a)

ξ

n

:= ξ

n

(λ) = max (

λ^−s2

√n

,

^λ−

1 2

n^1+s1

,

√

log(M) n

)

. (4.1b)

ある与えられた

f ∈ H

と

1 ≤ p ≤ ∞

に対し，fの

`

_p

-混合ノルムを以下のように定義する:

R

p,f

:= (∑

M

m=1

k f

m

k

^p_Hm

)

_p¹

.

すると，`₁

-MKL

およびエラスティックネット型

MKL

の収束レートが以下のように与え られる．

定理

4.1 (`

₁

-MKL

とエラスティックネット型

MKL

の収束レート) 仮定

3.1–3.5

が 満たされているとする．すると，ある

s, c, L, C

1

, ρ(I

0

), κ(I

0

)

に依存した定数

C ˜

と

ψ

sが 存在して，ある

M, d, C, s, f ˜

^∗に依存した

N

に対して任意の十分大きな

n ≥ N

において，

以下が成り立つ:

(`

1

-MKL) λ = d

^11+s−s

n

^−1+s1

R

⁻

2 1+s

1,f∗ に対して，

λ

⁽ⁿ⁾₁

= ψ

s

η(t)ξ

n

(λ), λ

⁽ⁿ⁾₂

= λ

⁽ⁿ⁾₁

λ

¹²

, λ

⁽ⁿ⁾₃

= 0

とする．この時，

`

1

-MKL

の汎化誤差は高い確率で以下のように抑えられる

:

k f ˆ − f

^∗

k

²L₂(Π)

≤ C ˜ (

d

^1−s1+s

n

^−1+s1

R

2s 1+s

1,f^∗

+ d

^s−11+s

n

^−1+s1

R

2 1+s

1,f^∗

+ d log(M ) n

)

η(t)

²

. (4.2)

(エラスティックネット型 MKL) λ = d

^1+q+s1

n

^−1+q+s1

R

⁻

2 1+q+s

2,g^∗ に対して，λ⁽ⁿ⁾₁

= ψ

_s

η(t)ξ

_n

(λ), λ

⁽ⁿ⁾₂

= λ

⁽ⁿ⁾₁

λ

¹²

, λ

⁽ⁿ⁾₃

= λ

とすると，エラスティックネット型

MKL

の汎化 誤差は高い確率で以下のように抑えられる:

k f ˆ − f

^∗

k

²L2(Π)

≤ C ˜ (

d

^1+q+s1+q

n

^−1+q+s1+q

R

2s 1+q+s

2,g^∗

+d

^1+q+sq+s

n

^{−1+q+s1+q −}(1+s)(1+q+s)^q(1−s)

R

2 1+q+s

2,g∗

+ d log(M ) n

)

η(t)

²

. (4.3)

この定理の正確な記述及び証明は

Suzuki and Sugiyama (2012, 2013)

を参照されたい．

これらは，

“`

1

-

混合ノルム球

”

および

“`

2

-

混合ノルム球

”

におけるミニマックス最適レート を達成していることが示されている

(

詳細は

Suzuki and Sugiyama (2012, 2013)

を参照

)

． これらのバウンドはいくつかの追加の弱い条件を課すことで次のように簡易化することがで きる．R_1,f∗

≤ Cd

がある定数

C

について成り立っているなら

(これは， k f

_m^∗

k

Hm

≤ C ( ∀ m)

なら成り立つ)，式

(4.2)

の第一項は第二項より大きく，`₁

-MKL

の収束レート

(4.2)

は次 のように書き直せる:

k f ˆ − f

^∗

k

²L2(Π)

≤ O

p

(

d

^1−s1+s

n

^−1+s1

R

2s 1+s

1,f^∗

+ d log(M ) n

)

. (4.4)

同様にして，もし

R

_2,g² ∗

≤ Cn

^1+sq

d

がある定数

C

に対して成り立っているなら

(これは k g

_m^∗

k

Hm

≤ √

C ( ∀ m)

なら成り立つ

)

，エラスティックネット型

MKL

の収束レート

(4.3)

は次のように書き直せる

:

k f ˆ − f

^∗

k

²L₂(Π)

≤ O

_p

(

d

^1+q+s1+q

n

^−1+q+s1+q

R

2s 1+q+s

2,g^∗

+ d log(M ) n

)

. (4.5)

ここで，

s

が小さくなれば

(

つまり，再生核ヒルベルト空間が単純になれば

)

，

`

1

-MKL

も エラスティックネット型

MKL

も

R

1,f^∗

, R

2,g^∗

≥ 1

なる条件のもと，その収束レートが速く なることがわかる．`₁

-MKL

およびエラスティックネット型

MKL

の解はどちらも一つの 最適化問題の枠組み

(3.1)

から与えられるが，λ⁽ⁿ⁾₃

= 0

であるかどうかに依存して，二つ の異なる収束レート

(4.4)

および

(4.5)

が得られている．`₁

-MKL

の収束レート

(4.4)

は滑 らかさのパラメータ

q

には依存していないが，エラスティックネット型のレート

(4.5)

は

q

に依存している．これら二つの収束レートを

q = 0

と

q > 0

の場合で比較してみよう．

(i) (q = 0)

この状況では，真の関数

f

^∗は滑らかではなく

g

^∗

= f

^∗である

(g

^∗の定義は仮 定

3.2

を参照).

d

に依存する項は

`

1

-MKL

においては

d

^1−s1+s である．よって，`₁

-MKL

は

d

について緩い依存性を持つ．これは，

`

1

-MKL

がスパースな解を出すことに対応している と考えられる．しかも，

`

1

-MKL

の汎化誤差バウンドはエラスティックネット型よりも小 さな値をとる．なぜなら，

Jensen

の不等式より

R

1,f^∗

≤ √

dR

2,f^∗ なので，

d

^11+s−s

n

^−1+s1

R

2s 1+s

1,f^∗

≤ d

^1+s1

n

^−1+s1

R

2s 1+s

2,f^∗

,

が成り立つからである．よって，この場合は

`

1

-MKL

の方が望ましいと考えられる．

(ii) (q > 0) q

が大きくなると

(

つまり真の関数が滑らかになると

),

エラスティックネッ ト型

MKL

の収束レートは速くなる．nに関する項を取り出すとエラスティックネット型は

n

^−1+q+s1+q であるが，これは

`

₁

-MKL

の

n

^−1+s1 よりも小さい．これは，エラスティックネッ

ト型

MKL

は真の関数

f

^∗の滑らかさを追加の

`

₂

-正則化によってうまくとらえているもの

と解釈できる．上で確認されたように，`₁

-MKL

は

q = 0

においてはエラスティックネッ ト型

MKL

よりもタイトなバウンドを与えていた．これらより，f^∗の滑らかさに応じて，

どちらが好ましいかが変わることがわかる．

5.

ガウシアンプロセス加法モデル

本節では，

MKL

をベイズ推定で行うことを考え，その汎化誤差の収束レートを導出す る．ここでの結果は

Suzuki (2012)

による．ここで考えるベイズ推定量は仮定

3.4

にあるよ うな入力分布およびカーネル関数に関する条件は必要ない．なお，汎化誤差は

{ x

_i

}

ⁿi=1 を 固定した固定デザインで考える．つまり，以下の経験的

L

₂

-ノルムを汎化誤差とする:

k f − f

^∗

k

²n

:=

_n¹

∑

n

i=1

(f (x

_i

) − f

^∗

(x

_i

))

²

.

母集団に関する

L

2

-

ノルムも解析できるが，ここでは簡単のため経験的

L

2

-

ノルムを考察す る．経験的

L

2

-

ノルムに付随して，内積を

h f, g i

n

:=

_n¹

∑

n

i=1

f (x

i

)g(x

i

)

と定める．

Suzuki

(2012)

のアプローチではガウシアンプロセス事前分布を各要素

f

_m^∗ に適用する．スパース

推定を行う場合，要素数に指数的重みの事前分布を乗せてどのカーネルを用いるかを推定 する．M 個の関数の組

f = (f

₁

, . . . , f

_M

)

に関する事前分布として，積空間に次のような事 前分布をおく:

Π(df ) = ∑

J∈P({1,...,M})

π

_J

· ∏

m∈J

∫

λ_m∈R+

GP

_m

(df

_m

| λ

_m

) G (dλ

_m

) · ∏

m /∈J

δ

₀

(df

_m

). (5.1)

ただし，

P ( { 1, . . . , M } )

は

{ 1, . . . , M }

に含まれるすべての部分集合を指し，δ₀

(df

_m

)

は

f

_m

= 0

をサポートにする

Dirac

測度である;

{ π

_J

}

J∈P({1,...,M})はある

ζ ∈ (0, 1)

に対して，

各モデルに次のような重みを乗せた事前分布である:

π

_J

= ζ

^|J|

∑

M j=0

ζ

^j

( M

| J | )

₋1

,

ただし，J

∈ P ( { 1, . . . , M } ) (この π

Jの選び方は

Alquier and Lounici (2011)

で提案され た);

G (dλ

m

)

は指数分布

G (dλ

m

) = exp( − λ

m

)dλ

mであり，ガウシアンプロセスのスケー ルに関して共役事前分布である; GP_m

(df | λ

m

)

はスケールが

λ

mのガウシアンプロセス事 前分布である（詳細は次の節で定義する）．

5.1

ガウシアンプロセス事前分布と対応する再生核ヒルベルト空間

f

_m^∗ には，カーネル

k

mに対応した平均

0

のガウシアンプロセス

GP

mを採用する．こ こで，空間

X

上の平均

0

のガウシアンプロセス

W

^(m)

= (W

x^(m)

: x ∈ X )

は，x

∈ X

で インデックス付けされた確率変数

W

x^(m)の組で，ある共通の確率空間

(Ω

m

, U

m

, P

m

)

の上 に定義されていて，任意の有限部分集合

(W

x^(m)1

, . . . , W

x^(m)j

) (j = 1, 2, . . . )

が平均

0

の多 変量正規分布に従うものと定義される．ここで，全ての

ω ∈ Ω

mでサンプルパスは有界

sup

_x∈X

| W

x^(m)

(ω) | < ∞

であると仮定する．これより，

W

^(m)

: Ω

_m

→ L

_∞

( X )

とみなせる．

また，W^(m)

: Ω

_m

→ L

_∞

( X )

はタイトで

Borel

可測とする．これは，ある半ノルム

ρ

_mが

X

上に存在して，(

X , ρ

_m

)

が全有界でほとんどすべての

ω ∈ Ω

_mで

x 7→ W

x^(m)

(ω)

が一様

ρ

_m

-連続なら成り立つ (詳細は例えば van der Vaart and Wellner (1996)

の

Section 1.5

を 参照せよ)．GP_mに対応したカーネル関数

k

m

: X × X → R

は以下で定義される共分散関 数である:

k

m

(x, x

⁰

) := E[W

_x^(m)

W

_x^(m)₀

].

カーネル関数はガウシアンプロセスの有限次元周辺分布の振る舞いを完全に規定する．カー ネル関数

k

mに付随して決まる再生核ヒルベルト空間を

H

mと書く．

無限次元の場合，再生核ヒルベルト空間

H

mはガウシアンプロセスのサポートに比べる とずっと

“

小さい

”

ことが知られている．実際，再生核ヒルベルト空間

H

mが無限次元の 場合，ガウシアンプロセスは

H

mの確率測度が

0

になる．これより，

f

_m^∗

∈ H

mという仮 定のもとでは，

f

_m^∗ をガウシアンプロセス事前分布を用いて通常のベイズ推定しても，最 適レートを達成しないことが知られている

(van der Vaart and van Zanten (2011)).

この 問題を回避するため，ガウシアンプロセス事前分布を

λ

_mでスケーリングし，小さな空間

H

mに推定量を近づける．スケールパラメータ

λ

_mでスケールされたガウシアンプロセス 事前分布

GP

_m

( ·| λ

_m

)

はスケールされたカーネル関数

˜ k

_m,λm

= k

_m

/λ

_mに対応したガウシア ンプロセスであると定義する．

H

m,λ_mを

k ˜

m,λ_mに対応した再生核ヒルベルト空間とする．

すると，f

∈ H

mは

H

m,λ_mに埋め込まれ，

H

mの元としての

f

と

H

m,λ_m の元としての

f

を同じ記号で表すと，

√ λ

m

k f k

_Hm

= k f k

_Hm,λm

が成り立つ．

式

(5.1)

で導入された事前分布に応じて，

“事後分布”

とベイズ推定量を定義する．D_n

:=

(y

1

, . . . , y

n

)

とする．ある定数

β > 0

に対し，(f₁

, . . . , f

M

)

の事後分布を

Π(df | D

n

) := exp( − ∑

n

i=1

(y

i

− ∑

M

m=1

f

m

(x

i

))

²

/β)

∫ exp( − ∑

n

i=1

(y

i

− ∑

M

m=1

f ˜

m

(x

i

))

²

/β)Π(d ˜ f ) Π(df ),

と定める

(ノイズが正規分布でない場合や β

の選び方によってはこれは正確な意味での事

後分布ではなくなるが，ここでは簡単のため「事後分布」と呼ぶ)．事後分布に応じて，そ の平均を計算することで，ベイズ推定量

f ˆ

が得られる：

f ˆ =

∫ ∑

^M

m=1

f

m

Π(df | D

n

).

本稿では，この推定方法をベイズ

-MKL

と呼ぶ．すると，

Suzuki (2012)

で仮定された雑音 の条件のもと，次の定理を得る．

定理

5.1 f

_m^∗

∈ H

mが全ての

m ∈ I

0で成り立ち，

max

m∈I₀

k f

_m^∗

k

Hm

≤ R

とする．する と，

{ s

m

}

m∈I₀

, R, β

および雑音の分布に依存したある定数

C

₁⁰ が存在して，

E

_Y1:n|x1:n

[ k f ˆ − f

^∗

k

²n

] ≤ C

₁⁰

{

dn

^−1+s1

+ d n log

( M e κ | I

₀

|

)}

が成り立つ．

これは，再生核ヒルベルト空間の間の相関に依存しないことに注意されたい．しかも，`_∞

-

混合ノルム球における最適レートを達成している．より詳細の議論および一般化は

Suzuki (2012)

を参照されたい．

6.

まとめ

MKL

の推定方法として正則化法とベイズ推定法を考察し，それらの汎化誤差バウンド を紹介した．また，MKLの定式化としてカーネルの重みを最適化する方式と正則化によ る方式の双対関係を論じた．正則化学習による

MKL

では

`

₁

-正則化とエラスティックネッ

ト型正則化を解析し，真の関数の滑らかさおよびスパース性によってそれぞれの汎化誤差 を特徴づけた．これらの結果は，`₁以外の正則化（例えば

`

p

-正則化）が良い精度を出すと

いう実験的知見

(Cortes et al. (2009b), Kloft et al. (2009), Tomioka and Suzuki (2009))

をある程度説明するものである．さらに，ベイズ推定法としてガウシアンプロセス事前分 布とモデルの指数重み平均を用いた方法を紹介し，カーネル間の相関に関する条件を課さ ずともミニマックス最適レートを達成することを紹介した．

本稿で紹介できなかったトピックとして，

Suzuki (2011)

はスパース性を仮定しないで任 意の混合ノルム型凸正則化に対する汎化誤差バウンドを導出している．さらに，これをも とに

adaptive lasso

と似た適応的重みを用いた正則化学習法が

Suzuki (2013)

で提案され ており，精度向上が報告されている．このような工夫は実データ解析では有用である．

謝辞

本稿で紹介した研究において多くの議論と助言をいただいた冨岡亮太さん，杉山将先生，

Alexandre Tsybakov

氏，Pierre Alquier氏に感謝いたします．また，博士課程からの研究