IBISML @ 2011 3 29 FastConvergenceRateofMultipleKernelLearningwithElastic-NetRegularization .......

(1)

. . . . . . . . . .

Introduction

. . . .

Mixed-Norm-Elasticnet-MKL Mini-maxレート Conclusion References

.

... .

.

Fast Convergence Rate of Multiple Kernel Learning with Elastic-Net Regularization

†鈴木大慈 ^†冨岡亮太 ^‡杉山将

†東京大学大学院情報理工学系研究科

‡東京工業大学大学院情報理工学研究科

2011年3月29日

IBISML研究会@大阪

(2)

. . . . . . . . . .

Introduction

. . . .

Outline

. .¹. Introduction MKLとその拡張本研究の概要

. .². Mixed-Norm-Elasticnet-MKL 準備

Mixed-Elasticnet-MKLの収束レート . .³. Mini-maxレート

. .⁴. Conclusion

(3)

. . . . . . . . . .

Introduction

. . . .

Outline

. .⁴. Conclusion

(4)

. . . . . . . . . .. . . .

Introduction

. . . .

MKLとその拡張

教師有りカーネル法

カーネル関数 ⇔ 再生核ヒルベルト空間 (RKHS) k(x,x^′) ⇔ Hk

教師有り学習問題 ˆf ← min

f∈Hk

1 n

∑n

i=1

ℓ(y_i,f(x_i)) +C∥f∥_Hk

表現定理

∃α_i ∈R s.t. ˆf(x) =

∑n

i=1

α_ik(x_i,x)

(5)

. . . . . . . . . .. . . .

Introduction

. . . .

MKLとその拡張

カーネルの選択

カーネル法の良い点：データの構造をカーネルに詰め込める．

Challenge：どのようなカーネルを用いるか？

ガウシアン,多項式,カイ二乗,… 沢山の特徴量の候補

→ Multiple Kernel Leaning：

凸最適化でカーネルを選択・統合

(6)

. . . . . . . . . .. . . .

Introduction

. . . .

MKLとその拡張

Multiple Kernel Learning

Single Kernel Learning ˆf ← min

f∈Hk

1 n

∑n

i=1

ℓ(y_i,f(x_i)) +C∥f∥Hk

Multiple Kernel Learning (Lanckriet et al., 2004; Bach et al., 2004) ˆf =

∑M

m=1

ˆfm← min

fm∈Hm

1 n

∑n

i=1

ℓ (

yi,

∑M

m=1

fm(xi) )

+C

∑M

m=1

∥fm∥_Hm

(Hm: カーネルk_mに対応したRKHS) Group Lassoの無限次元への拡張スパースな解

表現定理により有限次元最適化で解ける(Sonnenburg et al., 2006;

Rakotomamonjy et al., 2008; Suzuki & Tomioka, 2009)

(7)

. . . . . . . . . .. . . .

Introduction

. . . .

MKLとその拡張

様々な正則化

L1-MKL (Lanckriet et al., 2004; Bach et al., 2004)：スパース

min

fm∈Hm

L ( _M

∑

m=1

fm

) +C

∑M m=1

∥fm∥Hm

L2-MKL：デンス

min

fm∈Hm

L ( _M

∑

m=1

fm

) +C

∑M m=1

∥fm∥²Hm

Elasticnet-MKL (Tomioka & Suzuki, 2009)

min

f_m∈Hm

L ( _M

∑

m=1

fm

) +C1

∑M m=1

∥fm∥Hm+C2

∑M m=1

∥fm∥²_Hm

Mixed-Norm-Elasticnet-MKL (Meier et al., 2009)

f_mmin∈Hm

L ( _M

∑

m=1

fm

) +C1

∑M m=1

√∥fm∥²n+C2∥fm∥²_H_m+C3

∑M m=1

∥fm∥²_H_m ただし，∥f∥²n:=¹_n∑n

i=1f(xi)².

(8)

. . . . . . . . . .. . . .

Introduction

. . . .

MKLとその拡張

様々な正則化

min

fm∈Hm

L ( _M

∑

m=1

fm

) +C

∑M m=1

∥fm∥Hm

L2-MKL：デンス

min

fm∈Hm

L ( _M

∑

m=1

fm

) +C

∑M m=1

∥fm∥²Hm

min

f_m∈Hm

L ( _M

∑

m=1

fm

) +C1

∑M m=1

∥fm∥Hm+C2

∑M m=1

∥fm∥²_Hm

Mixed-Norm-Elasticnet-MKL (Meier et al., 2009)

f_mmin∈Hm

L ( _M

∑

m=1

fm

) +C1

∑M m=1

∥fm∥²_H_m ただし，∥f∥²n:=¹_n∑n

i=1f(xi)².

(9)

. . . . . . . . . .. . . .

Introduction

. . . .

MKLとその拡張

様々な正則化

min

fm∈Hm

L ( _M

∑

m=1

fm

) +C

∑M m=1

∥fm∥Hm

L2-MKL：デンス

min

fm∈Hm

L ( _M

∑

m=1

fm

) +C

∑M

m=1

∥fm∥²Hm

min

fm∈Hm

L ( _M

∑

m=1

fm

) +C1

∑M m=1

∥fm∥Hm+C2

∑M m=1

∥fm∥²Hm

Mixed-Norm-Elasticnet-MKL (Meier et al., 2009)←本日のターゲット

f_mmin∈Hm

L ( _M

∑

m=1

fm

) +C1

∑M m=1

∥fm∥²_H_m ただし，∥f∥²n:=¹_n∑n

i=1f(xi)².

(10)

. . . . . . . . . .. . . .

Introduction

. . . .

本研究の概要

本日のお題

Mixed-Norm-Elasticnet-MKLの汎化誤差を導出．

既存のレートよりタイトなことを示す．

これからはregression

L(f) = 1 n

∑n

i=1

(f(xi)−yi)²

を仮定．

真の関数を

f^∗(x) =

∑M

m=1

f_m^∗(x)(=E[Y|x]) と書く．

(11)

. . . . . . . . . .. . . .

Introduction

. . . .

本研究の概要

既存の研究

∥ˆf−f^∗∥²L2の収束レート，dは真の非ゼロ要素の数d=|{m|∥f_m^∗∥Hm̸=0}|. L₁-MKL (Koltchinskii & Yuan, 2008):

Op

(

d^1−s^1+sn⁻^1+s¹ +dlog(M) n

)

Mixed-Norm-Elasticnet-MKL (Meier et al., 2009): mini-maxではない．

Op

( d

(log(M) n

)_1+s¹ )

Mixed-Norm-L1-MKL (Koltchinskii & Yuan, 2010): mini-maxレート達成，正則化項は∑

m(C1∥fm∥n+C2∥fm∥_Hm) Op

(

dn⁻^1+s¹ +dlog(M) n

)

Mini-maxレート(Raskutti et al., 2009) O_p

(

dn⁻^1+s¹ +dlog(M/d) n

)

(12)

. . . . . . . . . .. . . .

Introduction

. . . .

本研究の概要

我々の結果（概要）

Mixed-Norm-Elasticnet-MKLの収束レート：

∥ˆf −f^∗∥²L₂ =Op

(

d^1+q+s^1+q n⁻^1+q+s^1+q R

2s 1+q+s

2 +dlog(M) n

) .

既存のレートよりタイト

真の関数f^∗の滑らかさqを導入

真の関数f^∗の“ノルム”R2との関係を解明

ℓ₂ボール上でmini-max最適（既存のはℓ_∞ボール上で最適）

(13)

. . . . . . . . . .. . . .

Introduction

. . . .

本研究の概要

既存の結果との関係

滑らかさ(q) 最適性収束レート K&Y (2008) q= 1 ? d^1−s^1+sn⁻^1+s¹ +^d^log(M)_n

Meier et al. (2009) q= 0 × d

(log(M) n

) ¹

1+s

K&Y (2010) q= 0 ℓ_∞-ball dn⁻^1+s¹ +^d^log(M)_n IBIS2010 0≤q≤1 ℓ_∞-ball dn⁻^1+q+s^1+q +^d^log(M)_n

今回 0≤q≤1 ℓ2-ball (_d

n

) ^1+q

1+q+sR

2s 1+q+s

2 +^d^log(M)_n

より速く，より一般的

(14)

. . . . . . . . . .

Introduction

. . . .

Outline

. .⁴. Conclusion

(15)

. . . . . . . . . .

Introduction

. . . .. .

準備

真がスパースであると仮定．

I0:={m| ∥f_m^∗∥_Hm ̸= 0}

∥f_m^∗∥Hm >0 (m∈I0),

∥f_m^∗∥_Hm = 0 (m∈I₀^c).

d=|I0|(真の非ゼロ要素の数)とおく．

(16)

. . . . . . . . . .

Introduction

. . . .. .

準備

Spectrum Condition (s)

0<s<1: モデルの複雑さを表わす．

Mercerの定理による分解：

km(x,x^′) =∑_∞

ℓ=1µℓ,mϕℓ,m(x)ϕℓ,m(x^′) ただし，{ϕℓ,m}^∞ℓ=1はL2(P)内のONS.

.Spectrum Condition (s) .

.

... .

.

ある実数0<s<1が存在して，

µ_ℓ,m≤Cℓ⁻¹^s (∀ℓ,m).

sはRKHSの複雑さを表わす．

sが大きいと複雑，sが小さいと単純 .Proposition (Steinwart et al. (2009)) .

.

... .

. .µ_ℓ,m∼ℓ⁻¹^s ⇔N(B(Hm), ϵ,L₂(P))∼ϵ⁻^2s

(17)

. . . . . . . . . .

Introduction

. . . .. .

準備

Convolution Condition (q)

0≤q≤1: 真f^∗の滑らかさを表わす．

Σm:Hm→ Hmを⟨f,Σmg⟩Hm :=E[f(X)g(X)]なるものと定義する．

.Convolution Condition (q) (Caponnetto & de Vito, 2007) .

.

... .

.

ある実数0≤q≤1とg_m^∗ ∈ Hmが存在して，

f_m^∗= Σ^q/2_m g_m^∗ と表せる．

km^(q/2)(x,x^′) :=∑_∞

ℓ=1µ^q/2_ℓ,mϕℓ,m(x)ϕℓ,m(x^′)に対して，

f_m^∗(x) =

∫

k_m^(q/2)(x,x^′)g_m^∗(x^′)dP(x^′), と書けることと同値．

(18)

. . . . . . . . . .

Introduction

. . . .. .

準備

s と q の関係

f * モデル

(a)s大，q= 0

f * モデル

(b)s大，q>0

f*

モデル

(c)s小，q>0

(19)

. . . . . . . . . .

Introduction

. . . .. .

準備

Incoherece Condition

.Incoherece Condition (Koltchinskii & Yuan, 2008; Meier et al., 2009) .

.

... .

.

ある定数0<Cが存在して，

0<C < κ(I₀)(1−ρ²(I₀)).

κ(I) := sup {

κ≥0|κ≤ ∥∑

m∈Ifm∥²L₂

∑

m∈I∥fm∥²_L₂, ∀fm∈ Hm(m∈I) }

,

ρ(I) := sup

{ ⟨fI,gI^c⟩L₂

∥f_I∥L2∥g_Ic∥L2

|fI ∈ HI,gI^c ∈ HI^c,fI ̸= 0,gI^c ̸= 0 }

. I₀の内側とも外側とも見分けがつく.

(20)

. . . . . . . . . .

Introduction

. . . .. .

準備

その他の条件

.Basic Condition .

.

... .

.

E[Y|X] =f^∗(X) =∑M

m=1f_m^∗(X)であり，ノイズϵ:=Y −f^∗(X)は有界：|ϵ| ≤L.

sup_X_∈X|k_m(X,X)| ≤1 (∀m).

.∞-norm Bound Condition .

.

... .

.

Spectrum Condition (s)と同時に次の不等式が満たされている：

∥fm∥_∞≤C∥fm∥¹_L⁻₂_(P)^s ∥fm∥^s_H_m.

Gaussianカーネルなど，Sobolev空間に埋め込める空間はこれが成り

立っている．Mendelson and Neeman (2010); Steinwart et al. (2009)で詳細な議論がされている．

(21)

. . . . . . . . . .

Introduction

. . . .. .

Mixed-Elasticnet-MKLの収束レート

我々の結果： Mixed-Norm-Elasticnet-MKL の収束レート

f_mmin∈Hm

L (_M

∑

m=1

fm

) +λ⁽ⁿ⁾₁

∑M m=1

√

∥fm∥²n+λ⁽ⁿ⁾₂ ∥fm∥²_H_m+λ⁽ⁿ⁾₃

∑M m=1

∥fm∥²_H_m. .Theorem

. .

... .

.

Spectrum Condition (s), Convolution Condition (q), Incoherence

Condition, Basic Condition,∞-norm Bound Conditionのもと，十分大きなnにおいて，あるパラメータλ⁽ⁿ⁾₁ ,λ⁽ⁿ⁾₂ , λ⁽ⁿ⁾₃ の値のもと，

∥ˆf −f^∗∥²L₂ ≤C^′ (

d^1+q+s^1+q n⁻^1+q+s^1+q R

2s 1+q+s

2,g^∗ +dlog(M) n

) η(t)², が確率1−e⁻^√^nt−e⁻^√ⁿ (∀t ≥1)で成り立つ．

ただしη(t) := max(√ t,t/√

n)であり，R2,g∗ を次のように定義する:

R2,g∗ :=

(_M

∑

m=1

∥gm^∗∥²_H_m )¹₂

.

(22)

. . . . . . . . . .

Introduction

. . . .. .

Mixed-Elasticnet-MKLの収束レート

Bound の比較

q= 0として具体的に比較

Koltchinskii and Yuan (2010)のレート： dn⁻^1+s¹ +^d^log(M)_n . 我々のレート：d^1+q+s^1+q n⁻^1+q+s^1+q R

2s 1+q+s

2,g∗ +^d^log(M)_n .

.

^.¹. ^∥^fm^∗∥_Hm = 1 (m= 1, . . . ,d): 大きさ一様我々のレート：dn⁻^1+s¹ +^d^log(M)_n

→Koltchinskii and Yuan (2010)と同じ．

.

^.². ∥f_m^∗∥Hm =m⁻¹(m= 1, . . . ,d): 大きさ急減衰我々のレート：d^1+s¹ n⁻^1+s¹ +^d^log(M)_n

→Koltchinskii and Yuan (2010)よりd^1+s^s 倍だけ速い．

1 2

(23)

. . . . . . . . . .

Introduction

. . . .

Outline

. .⁴. Conclusion

(24)

. . . . . . . . . .

Introduction

. . . .

Mini-max レート

Mini-maxレート：どんな推定法も超えられないレート．

f_m^∗= Σ

q

m2g_m^∗に注意する．

.

^.¹. ^(∑^Mm=1∥g_m^∗∥²_H_m)¹₂

≤R₂（g^∗が半径R₂のℓ₂ボールに含まれる）

d^1+q+s^1+q n⁻^1+q+s^1+q R

2s 1+q+s

2 +dlog(M/d) n

→我々のレートに一致．

.

^.². ^max^m^∥^g^m^∗^∥Hm ≤R_∞（g^∗が半径R_∞のℓ_∞ボールに含まれる）

dn⁻^1+q+s^1+q R

2s 1+q+s

∞ +dlog(M/d) n

→q= 0,R_∞= 1のとき，Koltchinskii and Yuan (2010)のレートに一致．

(25)

. . . . . . . . . .

Introduction

. . . .

Outline

. .⁴. Conclusion

(26)

. . . . . . . . . .

Introduction

. . . .

Conclusion

Mixed-Norm-Elasticnet–MKLの収束レートを導出．

既存研究よりタイトなレートを導出．

真f^∗の滑らかさqを導入．

導出されたレートはℓ2ボール上のmini-maxレートを達成．

本研究のプレプリント（arXiv）： http://arxiv.org/abs/1103.0431 slide: http://www.simplex.t.u-tokyo.ac.jp/˜s-taiji/data/IBISML2011.pdf

(27)

. . . . . . . . . .

Introduction

. . . .

Bach, F., Lanckriet, G., & Jordan, M. (2004). Multiple kernel learning, conic duality, and the SMO algorithm. the 21st International Conference on Machine Learning(pp. 41–48).

Caponnetto, A., & de Vito, E. (2007). Optimal rates for regularized least-squares algorithm. Foundations of Computational Mathematics, 7, 331–368.

Koltchinskii, V., & Yuan, M. (2008). Sparse recovery in large ensembles of kernel machines. Proceedings of the Annual Conference on Learning Theory(pp. 229–238).

Koltchinskii, V., & Yuan, M. (2010). Sparsity in multiple kernel learning.

The Annals of Statistics,38, 3660–3695.

Lanckriet, G., Cristianini, N., Ghaoui, L. E., Bartlett, P., & Jordan, M.

(2004). Learning the kernel matrix with semi-deﬁnite programming.

Journal of Machine Learning Research,5, 27–72.

Meier, L., van de Geer, S., & B¨uhlmann, P. (2009). High-dimensional additive modeling. The Annals of Statistics,37, 3779–3821.

Mendelson, S., & Neeman, J. (2010). Regularization in kernel learning.

The Annals of Statistics,38, 526–565.

Rakotomamonjy, A., Bach, F., Canu, S., & Y., G. (2008). SimpleMKL.

Journal of Machine Learning Research,9, 2491–2521.

(28)

. . . . . . . . . .

Introduction

. . . .

Raskutti, G., Wainwright, M., & Yu, B. (2009). Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness. InAdvances in neural information processing systems 22, 1563–1570. Cambridge, MA: MIT Press.

Sonnenburg, S., Rätsch, G., Schäfer, C., & Schölkopf, B. (2006). Large scale multiple kernel learning. Journal of Machine Learning Research, 7, 1531–1565.

Steinwart, I., Hush, D., & Scovel, C. (2009). Optimal rates for regularized least squares regression. Proceedings of the Annual Conference on Learning Theory(pp. 79–93).

Suzuki, T., & Tomioka, R. (2009). SpicyMKL. arXiv:0909.5026.

Tomioka, R., & Suzuki, T. (2009). Sparsity-accuracy trade-oﬀ in MKL.

NIPS 2009 Workshop:: Understanding Multiple Kernel Learning Methods. Whistler. arXiv:1001.2615.