正則化学習法における最適化手法

鈴木 大慈
東京大学
情報理工学系研究科
数理情報学専攻2013/2/18@九州大学伊都キャンパス
文部科学省委託事業数学協働プログラム「最適化ワークショップ: 拡がっていく最適化」

1

高次元データ
スパース正則化学習法
最適化手法
proximal point algorithm
確率最適化手法2

問題設定
スパース正則化学習

3

高次元線形判別
物体認識

自然言語処理音声認識

バイオインフォマティクス

4特徴ベクトル
DNAデータ判別
ベクトル化

癌になりやすい癌になりにくい高次元
5特徴ベクトル
テキストデータ
判別
ベクトル化

何の話題か？

高次元6

特徴ベクトル
画像データ

判別
ベクトル化

顔か？
顔でないか？

高次元
7

線形判別

8

1
1-1
1-1-1
11

サン
プ
ル数
次元: サンプル

次元 > サンプル数 → 余分な情報を落としたい9

1
1-1
1-1-1
11

サン
プ
ル数
次元

０: サンプル

次元 > サンプル数 → 余分な情報を落としたい10スパース推定：L1正則化

間違いへのペナルティ：ロス関数=間違いの度合いが大きいほど大きな値

平面の「複雑さ」
L1ノルム→スパース

11

イメージ

最適解

12

L2正則化の場合

最適解：スパースでない13

スパース正則化の例
例１：Ｇｒｏｕｐ Ｌａｓｓｏ

グループ構
造重複あり

14

例2：低ランク行列推定

低ランク

ユーザの趣向推定

＝顧客
DVD

15

例3：グラフ型正則化

54

12
316

スパース正則化学習の最適化
proximal point algorithm[Rockafellar, 1976]

双対乗数法 [Hestenes, 1969; Powel 1969]17

proximal point alg.：
乗数法：乗数法

prox. point alg.
主問題

FOBOS [Duchi&Singer,2009]
FISTA [Beck&Teboulle,2009](近似解法・近接勾配法)

ADMM(Alternating DirectionMultiplier Method)[Glowinski&Marrocco,75;Boyd et.al.,10](近似解法)

prox. point alg.

乗数法
双対問題

DAL
(Dual AugmentedLagrangian)

SpicyMKL[Tomioka&Sugiyama,2009;Tomioka,Suzuki&Sugiyama,2011]18

FOBOS (Forward Backward Splitting)
Nesterov (2007), Duchi&Singer (2009), FISTA:Beck&Teboulle (2009)

prox. point alg.

線形近似：ステップ幅パラメータ

L1正則化での更新式 (最適化の途中でもスパースな解)Soft threshold19

Proximal Operation
FOBOSは以下のproximal operationで更新(射影の一般化)
FOBOS：

例：L1ノルムでのproximal operation ()Soft threshold• 各変数ごとの最適化に分離．変数間の絡みがない．
• 解析解の存在．
20

収束レート• 一般の凸ロス関数• 滑らかな凸ロス関数•が正則で強凸かつ滑らかなロス関数21

proximal point alg.：
乗数法：

prox. point alg.
主問題

FOBOS [Duchi&Singer,2009]
FISTA [Beck&Teboulle,2009](近似解法・近接勾配法)

乗数法

ADMM
(Alternating Direction
Multiplier Method)[Glowinski&Marrocco,75;Boyd et.al.,10](近似解法)

乗数法
双対問題

prox. point alg.

DAL
(Dual AugmentedLagrangian)[Tomioka&Sugiyama,2009;
Tomioka,Suzuki&Sugiyama,2011]22

Dual Augmented Lagrangian(DAL)[Tomioka&Sugiyama,2009;
Tomioka,Suzuki&Sugiyama,2011]: Moreau’s envelope
L*が滑らかな場合，
ρに関するNewton法
23

DALの性質•の微分をスキップできる→ スパース性を利用した高速化• （超）一次収束なら24最適解が一意である必要はない

SpicyMKL [Suzuki&Tomioka, 2011]
DALのMKLへの拡張
Multiple Kernel Learning (MKL) [Lanckriet et al. 2004]
グループ正則化の各グループを無限次元の再生核ヒルベルト空間とした方法．
沢山のカーネル関数とそれに付随した再生核ヒルベルト空間

Sparse learning

グループ化

Lasso
Group Lasso

カーネル化

Multiple Kernel Learning (MKL)25ソフトウェアの公開
Matlabコード

http://www.simplex.t.u-tokyo.ac.jp/~s-taiji/software/SpicyMKL/

http://www.ibis.t.u-tokyo.ac.jp/ryotat/dal/

26

数値実験
CPU time v.s. # of kernels

SpliceSpicyMKLRingnorm•カーネルの数に対し良くスケールする
27

IDA data set, L1 regularization.

IDA data set, L1 regularization.

CPU time v.s. # of samples

SpliceSpicyMKL

Ringnorm• サンプル数に対しては既存手法とほぼ同じスケール28

proximal point alg.：
乗数法：

prox. point alg.
主問題

FOBOS [Duchi&Singer,2009]
FISTA [Beck&Teboulle,2009](近似解法・近接勾配法)

乗数法

ADMM
(Alternating Direction
Multiplier Method)[Glowinski&Marrocco,75;Boyd et.al.,10](近似解法)

乗数法
双対問題

prox. point alg.

DAL
(Dual Augmented
Lagrangian)[Tomioka&Sugiyama,2009;
Tomioka,Suzuki&Sugiyama,2011]29

prox. op.が計算しにくい例• 重複ありグループ正則化
変数間に絡み重複あり• 解決策•各正則化関数に応じた賢い方法で解く [Yuan et al. 2011]•変数を増やして問題を簡単にする (汎用的)を満たし

idea:が計算しやすいを利用する．
30

分離凸31ADMM(Alternating Direction Multiplier Method)• 乗数法： wとyを同時最適化• Splitting Technique
wとyの最適化を分離ADMM

32

ADMMの収束レート• リプシッツ連続凸ロス関数•

が正則で強凸かつ滑らかなロス関数

33

確率的最適化（オンライン学習）34

近年のデータ
Flickr
100万枚/日
twitter
２億ﾂｲｰﾄ/日(2011/6/30)
トルストイ「戦争と平和」8163冊分

次世代シーケンサ
60億本 x100塩基

ARISTA
20億画像

多量
全データをメモリに保持できない
35

確率的最適化
prox. point alg.

全データを保持するのではなく，一つサンプルを見たらwを更新してサンプルを捨てる方法• FOBOS (Forward Backward Splitting) [Duchi&Singer,2009]

一つのサンプル・線形近似• RDA (Regularized Dual Averaging)[Xiao,09; Nesterov,09]

双対変数（勾配）の平均で過去の情報を保持

36

確率的ADMM[Suzuki, ICML2013]

ADMM + 確率的最適化• FOBOS型ADMM• RDA型ADMM

実装が簡単！
37

収束レートデータ：• 一般の凸ロス関数• 強凸正則化関数

条件•データはi.i.d.系列•ロスと正則化項はLipschitz連続•wのドメインは有界38数値実験：確率的ADMM
人工データ

実データ（Adult, a9a@LIVSVM data sets)
テス
トデータでの判別誤差

最適値との差1,024次元512サンプル
重複ありグループ正則化

提案手法

15,252次元
32,561サンプル
重複ありグループ正則化+ L1正則化
39

バッチデータに対する確率的最適化

40

Stochastic Dual Coordinate Ascent[Shalev-Shwartz&Zhang,2012]

1. をランダムに選択
２.次元i方向に最適化

３. 上の1,2を繰り返す．

が強凸でが滑らかな時，双対ギャップの期待値

41

まとめ• 正則化学習の最適化法
proximal point algorithm ⇔ 乗数法
双対の関係

prox. point alg.

乗数法

FOBOSADMM(近似解法・近接勾配法)(近似解法)

乗数法

prox. point alg.

DAL

• 確率的最適化法－ FOBOS・RDA－確率的ADMM←最近のトレンド42