NIPS2012より識別モデル学習の進展を垣間見る
こんばんは．[twitter:@kisa12012]です．しがない機械学習系大学院生をやっております．Machine Learning Advent Calendar 2012 9日目では，"NIPS2012より識別も出る学習の進展を垣間見る"という無駄に野心的なタイトルで，先ほどまで開催されていたNIPS2012で発表された数本の論文概要を紹介します．機械学習，特に識別モデル学習の最先端が多少なりとも垣間見える，もしくは論文本体を読んでみようと思わせられる記事になっていれば幸いです．
重要: 概要紹介のみですので，数式は一切出てきません．（数式を記述する前に力尽きました……）
NIPS2012とは？
ホームページ : http://nips.cc/Conferences/2012/
機械学習のトップ国際会議の一つ．機械学習の理論的な面を解析した論文や，理論的背景を持ったアルゴリズムの導出を提案した論文が多いですが，脳科学・ロボット・画像解析・言語解析等への機械学習応用を目的とした論文も数多く出ている会議です．MLAC 6日目の[twitter:@koh_t]さんの記事もNIPS2012で発表された論文です．
今年は，12月3日〜8日までアメリカネバダ州のレイク・タホで開催されてました．
NIPSについて詳しくは，朱鷺の社のNIPS紹介の記事をご参照下さい．
紹介する論文
今回紹介するのは，以下の識別モデル学習に関連した3本の論文です．
Learning Multiple Tasks using Shared Hypotheses
- K. Crammer, Y. Mansour
A Stochastic Gradient Method with an Exponential Convergence Rate with Finite Training Sets
- N. Le Roux, M. Schmidt, F. Bach
- pdf : http://books.nips.cc/papers/files/nips25/NIPS2012_1246.pdf
- Arxiv Full version : http://arxiv.org/abs/1202.6258
- Slide : http://nicolas.le-roux.name/files/sag_nips_slides.pdf
- これは識別モデル学習に限らないですが…
Volume Regularization for Binary Classification
- K. Crammer, T. Wagner
Learning Multiple Tasks using Shared Hypotheses
概要
複数の関連する分類問題を同時に最適化するマルチタスク分類問題を考える．例として，個々人の受信メールから重要度の高いメールを抽出するタスクはマルチタスク問題として考えられる*1 *2．
上記のようにパーソナライゼーション等のタスクでは，タスク数は非常に多いが一人ひとりのデータ数が少ない場合が考えられる．この条件下では，タスク数より少ない数の学習器のみを用い，タスク間で学習器をシェアしながら学習を行う方が理論的にも実験的にもよりよい結果が得られる事を示した．
背景
- タスク毎のデータ量が少ない場合，十分な汎化性能を持つような学習は困難
- パーソナライゼーション等では一般的な現象
- 全タスクを一つのタスクと思って単一の学習器で学習する場合は，タスク間で異なる特性を捉えられず識別精度が悪化
- 中庸をとりたい，つまり複数のタスクで分類器を共有
- 分類器の学習に，複数タスクのデータを用いることが可能に
貢献
- 本問題設定におけるVC次元の上限・下限を導出
- VC次元を用いた汎化誤差上限を評価
- タスク数:多 仮説数:少 の時，各タスクで分類器を学習した場合より小さい汎化誤差上限で抑えられる
アルゴリズム
- 1. 各タスクのデータを学習用とバリデーション用に分割
- 2. 各タスクが用いる学習器をランダムに割り当て
- 3. 各学習器に割り当てられたタスクの全学習用データでの損失最小化問題を解き，学習器を更新
- 4. 各タスクのバリデーションデータに関して一番予測精度の高い学習器に割り当て直す
- 5. 一定の回数反復，あるいは一定の収束基準を満たすまで，3.4ステップを反復
- 6. 学習用とバリデーション用データを用いて各学習器を更新
雑感
- パーソナライゼーション系のマルチタスク学習には相当強そう
- タスクの分割が大雑把だったとしても上手く動きそうなのが素晴らしい
- 実装は簡単，背後の理論は複雑かつ盤石，と良い研究のお手本
A Stochastic Gradient Method with an Exponential Convergence Rate with Finite Training Sets
概要
データが事前に固定されていれば，ある種の一般的条件設定のもとで，データ数に対して定数オーダーの計算コストで線形収束を実現するSGDを提案．確率的最適化手法であるSGDと全データの勾配を毎ステップ計算して最適化するGDのハイブリッド（良いとこ取り）手法を提案し，こちらも理論的・実験的に非常に高速に最適解へ収束する事を示した．
貢献
アルゴリズム
- 1. データを1つランダムに選択し，現在の重みベクトルで勾配を計算
- 2. 各データの「最後に」算出された勾配を集め，その平均ベクトルを用いて学習器を更新
- 3. 一定の回数反復，あるいは一定の収束基準を満たすまで，1,2ステップを反復
実装上の工夫など
雑感
- 以前も結構話題になっていたので，すでに読んでいる人も多い？
- 以前実装して実験を回してみましたが，実際SGDより遥かに高速に収束してました
- 証明を解釈する会開きましょう（白目）
Volume Regularization for Binary Classification
概要
分類問題を多次元空間の「点（重みベクトル）」ではなく「箱（重みベクトルの集合）」の形で最適化する．ここで「箱」の形で最適化する，とは「箱」中の重みベクトル集合の中で最悪性能を示す重みベクトルで最適化問題を評価した場合の値を最大化する事．さらに，理論的にはPAC-Bayesian Boundを求めており，ノイズ環境下ではAROWやSVMよりも非常に高い性能を示すことを確認している．
背景
- 既存の線形モデルは，信頼度や代替となる重みベクトルの情報を持たせる事が困難
- Bayesian Classifierは，計算量やメモリ制約の問題から近似手法が必要
- これまた中庸を取る
- 重みベクトル集合，つまり「箱」の最適化を行う
- 高速かつ省メモリでパラメータ更新が可能かつパラメータとして信頼できる重みベクトル集合が得られる
