Document

Nightmare at Test Time: Robust
Learning by Feature Deletion
Amir Globerson
Computer Science and Articial Intelligence Laboratory, MIT, Cambridge, MA, USA
Sam Roweis
Department of Computer Science, University of Toronto, Canada
All the equation images are clipped from this paper.
論文紹介者：坪井祐太
(IBM東京基礎研究所/奈良先端大博士課程1年)
2006-07-29
ICML2006 読む会: Nightmare at Test Time (坪
井)
1
論文の見どころ
 意味深な(?)タイトル
 Nightmare at Test Time
→ 最悪な状況を前提に関数の最大化
 目的：分類器のRobust学習
 特定の素性にOver weightingしない学習
 うまい問題設定
 古くからの課題(素性選択)と似ているようでちょっ
と違う
 でも、素性選択と比べて解きやすい問題
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
2
ゲーム理論的枠組みによるモデル
 学習時に使える素性が、分類時に使えるとは限らな
い
 Spam filtering: 言葉の移り変わり
 Image processing: pixel欠損 (pepper noise)
 Sensor network: neurons die
→素性が消えることを前提とした学習
 MinMaxシナリオ: 2プレーヤーゲーム
 Player 1: feature removal mechanism
 Classifierにもっとも性能を落とす素性を消す
 Player 2: classifier builder
 最適なパラメータ（重み）を見つける
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
3
SVM (hinge loss)を前提に2player gameを定式化
Player 1: feature removal mechanism
 worst caseシナリオ：各学習サンプル(xi)で
Lossが最大になる素性を選択する
 設定パラメータ: K (feature消去最大数)
Worst case hinge loss
Loss max=最悪シナリオ
K個消去済み
素性ベクトル
αij ：学習サンプル(xi)の消去する素性の位置(j)を示す
(1-αi):学習サンプル(xi)の残る素性を示すベクトル
注意：各学習サンプルで消される素性は異なる
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
4
SVM (hinge loss)を前提に2player gameを定式化
Player 2: classifier builder
 素性消去最悪シナリオ時のloss(hwc)を最小
化する重みwを求める（SVM）
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
5
Player 1: feature removal mechanism
の式変形
 最悪シナリオ時のlossを不等式制約のある最小化問題に式変形
最適値を変えることなく
制約をRelax
si:素性を消すこ
とによって増える
loss
双対問題
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
6
最終的な最小化問題：FDROP
 二次計画 & 凸問題
 効率的に解ける
 パラメータ数：O(事例数*次元数)
 SVMはO(事例数+次元数)
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
7
その他 (結果のみ紹介)
 Multi-classにも適用可能
 Hinge loss以外の関数(log lossなど)にも適
用可能かは不明(challenge)
 Kernelに出来る？
 消去素性選択があるため自明でない(challenge)
 学習サンプル間で同じ素性を削除する場合は？
 凸問題だが、α(どの素性を消すかを現す変数)の制
約をrelaxできないので提案手法ほど簡単に解けな
い
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
8
素性選択との関係(1)
提案手法の方が計算量が少ない
 一般的な素性選択
 lossを最小にするfeatureをK個選択する問題
 凸問題でない
K個残した素
性ベクトル
 FDROPはdifferent computational class
 二次計画 & 凸問題で効率的に解ける。
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
9
素性選択との関係(2)
素性選択としても使える？
 FDROPで消去されやすい素性を採用すること
で素性選択に使える可能性がある
 実験中：情報利得による素性選択と同程度の性能
Clipped from: A. Globerson & S. Roweis, “Nightmare at Test Time: Robust Learning by Feature Deletion”, ICML 2006
手書き文字認識問題でFDROPによ
り素性が削除された画像
→認識に重要な素性が落ちてそうな
ので、逆に言えば重要な素性が見
つけられている？
2006-07-29
ICML2006 読む会: Nightmare at Test Time
(坪井)
10
分類問題によるSVMとの実験結果
 素性の一部が失われたデータではSVMより
有効
 スパムフィルタでは素性が無い場合でも良い
性能
Clipped from: A. Globerson & S. Roweis, “Nightmare at Test Time: Robust Learning by Feature Deletion”, ICML 2006
人工データ
一番重要な素性を削除
2006-07-29
手書き認識
ランダムに素性削除
ICML2006 読む会: Nightmare at Test Time
(坪井)
スパムフィルタ
ランダムに素性削除
11

Download Report