Microsoft PowerPoint - ElasticConvergence

Transcription

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

2 スパース性と汎化誤差の関係 どのような正則化が好ましい? Multiple Kernel Learning (MKL) Elasticnet MKL Lp-norm MKL 汎化誤差を理論的に解析 2

3 教師有りカーネル法 カーネル関数 ( : 再生核ヒルベルト空間 ) 回帰, 判別 : SVM, SVR,. 3

4 カーネル関数の例 ガウシアン, 多項式, カイ二乗,. パラメータ : ガウス幅, 多項式の次数, 特徴量 Computer Vision: 色, 勾配, sift (sift, hsvsift, huesift, scaling of sift), Geometric Blur, 画像領域の切り出し,... MKL: カーネルを選択して統合 4

5 MKL: Multiple Kernel Learning [Lanckriet et al. 2004] : M 個のカーネル関数 : カーネル関数 k m に付随した RKHS L1 正則化 : スパース Gourp Lasso の無限次元への拡張 [Bach, Lanchriet, Jordan:ICML2004] 5

6 カーネル重みとの関係 :given Young の不等式 [Micchelli & Pontil: JMLR2005] k は k m らの凸結合 目的関数をカーネル関数の凸結合の中で最小化 6

7 カーネル重み : L 2 L 1 (MKL) スパース L (Uniform) L 2 デンス 結構良い性能 : 単なる一様重みでの重ね合わせ 7

8 デンス L 2 L 1 スパース 8

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

10 Elasticnet MKL: caltech 101 dataset Best L1 L2 中間的なスパースさが良い dense Medium density 10 [Tomioka & Suzuki: NIPS 2009 Workshop ]

11 Lp-norm MKL MKL (sparse) 中間 (p=4/3) 一様重み (dense) # of features [Cortes, Mohri, and Rostamizadeh: UAI 2009] 11

12 ここまでのまとめ L 1 (MKL) と L 2 ( 一様重み ) の中間的なスパースさ elasticnet/lp-norm MKL 実験的に性能 実は, 計算量も少なくてすむ ( 後述 ) 12

13 なぜ, 性能が良いのか? どのような条件のとき, 中間的スパースさが 良いのか? 以後, 主にElasticnet MKL を扱う. 13

14 概要 導入 効率的計算法 漸近的汎化誤差の解析 Elasticnet MKLの収束レート 真がスパースな状況 真がスパースでない状況 Lp-norm MKL の収束レート 14

15 効率的計算法 15

16 双対問題 表現定理 : Fenchel 双対 降下法 (Newton 法など ) が使える なめらか! 16

17 数値実験 UCI:Ringnorm SimpleMKL(L1) UCI:Splice SpicyMKL(L1) Elasticnet MKL 17

18 概要 導入 効率的計算法 漸近的汎化誤差の解析 Elasticnet MKLの収束レート 真がスパースな状況 真がスパースでない状況 Lp-norm MKL の収束レート 18

19 漸近的汎化誤差の解析 これからは二乗ロス ( 回帰 ) を想定 : 19

20 スパース学習の収束レートス学習の収束レ Lasso & Dantzig Selector Candes & Tao: AS2007 (Dantzig selector) Bunea, Tsybakov & Wegkamp: AS2007 (Lasso) Meinshausen & Yu: AS2009 (Lasso) Bickel, Ritov & Tsybakov: AS2009 (Dantzig&Lasso) Raskutti, Wainwright & Yu: arxiv: , mini-max レート 20

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

22 : 真の関数 収束レートの導出 : 二つの状況設定 真が厳密にスパース 真が大体スパースス d や M はサンプル数に応じて増えてもよい. 22

23 スパースな状況 23

24 RKHSの複雑さの仮定 (s, スペクトルの条件 ) s :RKHS の複雑さを表わす定数 s が大きい 複雑 s が小さい 単純 Mercer の定理 : ONS in L P ある実数 <s< が存在して 24 covering number とも関係あり,[Steinwart, Hush & Scovel: COLT2009]

25 真の関数の積分表現の仮定 真はある関数と積分核とのたたみこみで, 十分なめらか. あるが存在して, ただし. [Koltchinskii & Yuan: COLT2008, Bach: JMLR2008] 25

26 定理 :Elasticnet MKL の収束レート 前述の仮定と次の二つの条件が満たされているとする : あるC が存在して. ちょっと強い仮定 すると, のとき, mini-max レートを達成 26

27 定理 :L 1 -MKL の収束レート より強い仮定が必要 前述の仮定と次の二つの条件が満たされているとする : d によらない :L 1 では真が大きくなれない あるC が存在して. すると, のとき, これは Koltchinskii & Yuan (COLT2008) による結果を改善 : 27

28 その他の仮定 Incoherence 条件 [ ある定数 <C が存在して [Koltchinskii & Yuan:COLT2008, Meier, van de Geer & Bühlmann:AS2009] 非ゼロ成分はその他の成分で代用できず, かつ解の一意性が保証されている. カーネルは有界 28

29 実は, といった強い条件は取り除ける. 29

30 正則化項の変換 Elasticnet MKL cf. Meier, van de Geer & Bühlmann: AS2009. より弱い条件で速い収束レートを実現 最適化は難しい 30

31 真の関数の積分表現の仮定 (q) q: 真の滑らかさを表わす定数 ( 大きいほどなめらか ) 先の仮定は q=1 を仮定していることに相当 ただし. [Caponnetto & de Vito: FCM2007] では単一カーネルの場合を考察. 31

32 定理 前述の仮定と次の条件が満たされているとする : するとに対し, の時, 非ゼロ要素が d 個の場合の mini-max レート 32

33 既存のバウンドとの比較 我々の結果 : Meier, van de Geer & Bühlmann: AS2009 q の時, 我々のバウンドは彼らのバウンドを改善 q をへ拡張 一般のRKHSで議論 33

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

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

36 大体スパースな状況 もとの正則化を考える 36

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

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

39 Lp-norm MKL 39

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

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