IBIS2010

スパース正則化学習の学習性能，特にスパ ス性と汎化誤差の関係について
特にスパース性と汎化誤差の関係について
鈴木 大慈
東京大学
情報理工学系研究科
数理情報学専攻2010年11月4日
冨岡亮太（東京大学），杉山将（東京工業大学）との共同研究

1スパース性と汎化誤差の関係
どのような正則化が好ましい？
M ltiple Kernel Learning (MKL)
Multiple↓

Elasticnet MKL
Lp--norm MKL
Lp
汎化誤差を理論的に解析
化誤差を理論的 解析
2

教師有りカ ネル法
教師有りカーネル法
カーネル関数（ ：再生核ヒルベルト空間）

回帰, 判別: SVM, SVR, ….

3

カーネル関数の例
カネル関数の例• ガウシアン，多項式,ガウシアン 多項式 カイ二乗,カイ二乗 ….
– パラメータ：ガウス幅, 多項式の次数，…

• 特徴量– ComputerpVision：色,, 勾配,, sift ((sift,, hsvsift,,huesift, scaling of sift), Geometric Blur,
画像領域の切り出し, ．．．
画像領域の切り出し

MKL：
MKL： カーネルを選択して統合
4

MKL: Multiplep Kernel Learningg[Lanckriet et al. 2004]: M個のカーネル関数：カ
カーネル関数k
ネル関数kmに付随したRKHS

L1正則化：
L1正則化：
スパース• Gourp Lassoの無限次元への拡張[Bach Lanchriet,[Bach,Lanchriet Jordan:ICML2004]5

カ ネル重みとの関係
カーネル重みとの関係：givenYoungの不等式[Micchelli & Pontil: JMLR2005]

kはkmらの凸結合
目的関数をカ ネ 関数 凸結合 中 最小化
目的関数をカーネル関数の凸結合の中で最小化

6カーネル重み:
カネル重み L2
Ｌ１ (MKL)

スパース

Ｌ2 (Uniform)(U if)

デンス
デンス
結構良い性能：単なる一様重みでの重ね合わせ：単なる様重みでの重ね合わせ
7

デンス

L2

L1スパース8

L1とL2の橋渡し
Elasticnet MKL

Lp-norm MKL (1≦p≦2)[Shawe-Taylor: NIPS workshop 2008,
Tomioka & Suzuki: NIPS workshop 2009]
cf. elastic-net: [Zou & Hastie: JRSS, 2005][Marius et al.: NIPS2009]9

Elasticnet MKL: caltech 101 dataset

Best

L1

L2

中間的なスパースさが良い
dense
M diMediumddensity
it10[Tomioka & Suzuki: NIPS 2009 Workshop ]Lp-norm MKL

MKL (sparse)()
一様重み (dense)
中間(p=4/3)
中間(p4/3)# of features[Cortes, Mohri, and Rostamizadeh: UAI 2009]11ここまでのまとめ• L1(MKL)とL2(一様重み)の中間的なスパースさ→ elasticnet/Lp-norm MKL→ 実験的に性能○
実は，• 計算量も少なくてすむ（後述）12• なぜ，性能が良いのか？
• どのような条件のとき，中間的スパースさが良いのか？

以後，主にElasticnet
後 主MKLを扱う．
を扱う

13

概要
• 導入
• 効率的計算法• 漸近的汎化誤差の解析– Elasticnet MKLの収束レート
収束••

真がスパースな状況
真
真がスパースでない状況– Lp-norm
Lp norm MKLの収束レMKLの収束レート
ト14効率的計算法

15

双対問題
表現定理：

Fenchel双対降下法（Newton法など）が使えるなめらか！

16

数値実験
UCI:Ringnorm
SimpleMKL(L1)

UCI:Splice

SpicyMKL(L1)Elasticnet MKL17

概要• 導入• 効率的計算法• 漸近的汎化誤差の解析– Elasticnet MKLの収束レート
収束••

真がスパースな状況
真
真がスパースでない状況– Lp-norm
Lp norm MKLの収束レMKLの収束レート
ト18

漸近的汎化誤差の解析
これからは二乗ロス（回帰）を想定：

19

スパ ス学習の収束レ ト
スパース学習の収束レート• LassoL& Dantzig
D t i Selector
S l t– Candes & Tao: AS2007 ((Dantzigg selector))– Bunea, Tsybakov & Wegkamp: AS2007 (Lasso)– Meinshausen & Yu: AS2009 (Lasso)– Bickel, Ritov & Tsybakov: AS2009 (Dantzig&Lasso)– Raskutti, Wainwright & Yu: arXiv:0910.2042, 2009.
mini-max レート
20

MKLに関する既存の結果• L1-MKL– Koltchinskii & Yuan: COLT2008
タイトではない• Minimax-レート
Minimax レート– Raskutti, Wainwright & Yu: NIPS2009• Elasticnet型正則化
El tit型正則化– Meier,, van de Geer & Bühlmann: AS2009• Sobolev空間
21

: 真の関数• 収束レートの導出：二つの状況設定– 真が厳密にスパース– 真が大体スパース
真が大体スパ ス

dやMはサンプル数に応じて増えてもよい．

22

スパースな状況

23• RKHSの複雑さの仮定（s,複雑仮定
スペクトルの条件）
条s :RKHSの複雑さを表わす定数s が大きい → 複雑
s が小さい → 単純

Mercerの定理: ONS in L1wPD

ある実数 (S< s < d が存在して24

covering numberとも関係あり，[Steinwart, Hush & Scovel: COLT2009]• 真の関数の積分表現の仮定
真はある関数と積分核とのたたみこみで，十分なめらか．
ある

ただしが存在してが存在して，.

[Koltchinskii & Yuan: COLT2008, Bach: JMLR2008]25

定理：Elasticnet MKLの収束レート
前述の仮定と次の二つの条件が満たされているとする：
前述の仮定と次の二つの条件が満たされているとする••.

あるCf +が存在してちょっと強い仮定のとき,

すると，mini-max レートを達成
26

定理：L1-MKLの収束レート

より強い仮定が必要

前述の仮定と次の二つの条件が満たされているとする：←dによらない：L1では真が大きくなれない

••
すると，

.

あるCf +が存在してのとき,これはKoltchinskii & Yuan (COLT2008)による結果を改善:27

その他の仮定• Incoherence条件[[Koltchinskii& Yuan:COLT2008,Meier, van de Geer & Bühlmann:AS2009]

ある定数 (S< C が存在して非ゼロ成分はその他の成分で代用できず，かつ解の一意性が保証されている．

• カ
カーネルは有界
ネルは有界
28

実は，
••
とい た強い条件は取り除けるといった強い条件は取り除ける．

29

正則化項の変換
Elasticnet MKL

cf. Meier, van de Geer & Bühlmann: AS2009.

• より弱い条件で速い収束レより弱い条件で速い収束レートを実現
トを実現• 最適化は難しい30

• 真の関数の積分表現の仮定 (q)q 真の滑らかさを表わす定数（大き ほどなめらか）
q：真の滑らかさを表わす定数（大きいほどなめらか）
先の仮定はq=1を仮定していることに相当

ただし.

[Caponnetto & de Vito: FCM2007]では単一カーネルの場合を考察.

31

定理
前述 仮定 次 条件 満 さ
前述の仮定と次の条件が満たされているとする：
る する•

すると

に対し，の時，非ゼロ要素がd個の場合のmini-maxレート32

既存のバウンドとの比較
我々の結果:• Meier, van de Geer & Bühlmann: AS2009q) (の時,

• 我々のバウンドは彼らのバウンドを改善• q)) (をへ拡張• 一般のRKHSで議論
33

有限次元(L有限次元(Lasso)との比較)との比較• Lassoはmini-maxレートを達成• L1-MKLは難しそう
理由：無限次元ではL2ノルムとRKHSノルが同値でなが同値でない．

34

その他の仮定• 無限大ノルムのバウンド.
Sobolev空間や Gaussian RKHSはこの条件を満たす．
cf. [Mendelson and Neeman, 2008; Steinwart, Hush and Scovel, COLT2009]• Incoherence条件• カーネルは有界
カ ネルは有界
35

大体スパースな状況

もとの正則化を考える
36

• 一般化Incoherence条件
般化Incoherence条件
b：各RKHS間の相関の強さを表す定数（小さいほど低い相関）ある定数 (S< C が存在してデザイン行列のIにおける最小個有値

I と Icの相関37q) dを仮定し，カーネルの数はべき乗で増えるとする:の時，各手法の収束レートはの時
各手法の収束レ トは下の図のような関係になる:: β が小さく (非スパース) で b が大 (相関が強い).

38

L
Lp-norm
MKL39

L
Lp-norm
MKLの収束レ ト
MKLの収束レート

pが大で大pが小で小pが大で小pが小で大トレ ドオフ
トレードオフ真のスパ スさと推定量のスパ スさの兼ね合い
真のスパースさと推定量のスパースさの兼ね合い
40

まとめ
まとめと今後の課題• L1とＬ2の中間的なスパ
L1とＬ2の中間的なスパースさ
スさ– 実験的に性能○– 計算量も少なくて済む• 理論的に性能の良さを考察– Elasticnet MKLは弱い条件で速い収束– 正則化項を変えることによりさらに条件を緩和– RKHS間の相関が強く，あまりスパースでないときRKHS間の相関が強く あまりスパ スでないときにElasticnet MKLは良い性能– Lp-norm MKLは真のスパースさに応じて最適なノルムが変化
41