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 (坪井)

ICML2006 読む会: Nightmare at Test Time (坪井) 論文の見どころ 意味深な(?)タイトル Nightmare at Test Time → 最悪な状況を前提に関数の最大化 目的：分類器のRobust学習 特定の素性にOver weightingしない学習 うまい問題設定 古くからの課題(素性選択)と似ているようでちょっと違う でも、素性選択と比べて解きやすい問題 2006-07-29 ICML2006 読む会: Nightmare at Test Time (坪井)

ICML2006 読む会: Nightmare at Test Time (坪井) ゲーム理論的枠組みによるモデル 学習時に使える素性が、分類時に使えるとは限らない 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 (坪井)

ICML2006 読む会: Nightmare at Test Time (坪井) SVM (hinge loss)を前提に2player gameを定式化 Player 1: feature removal mechanism worst caseシナリオ：各学習サンプル(xi)でLossが最大になる素性を選択する 設定パラメータ: K (feature消去最大数) Worst case hinge loss K個消去済み素性ベクトル Loss max=最悪シナリオ αij ：学習サンプル(xi)の消去する素性の位置(j)を示す (1-αi):学習サンプル(xi)の残る素性を示すベクトル 注意：各学習サンプルで消される素性は異なる 2006-07-29 ICML2006 読む会: Nightmare at Test Time (坪井)

SVM (hinge loss)を前提に2player gameを定式化 Player 2: classifier builder 素性消去最悪シナリオ時のloss(hwc)を最小化する重みwを求める（SVM） 2006-07-29 ICML2006 読む会: Nightmare at Test Time (坪井)

Player 1: feature removal mechanismの式変形 最悪シナリオ時のlossを不等式制約のある最小化問題に式変形 最適値を変えることなく制約をRelax si:素性を消すことによって増えるloss 双対問題 2006-07-29 ICML2006 読む会: Nightmare at Test Time (坪井)

ICML2006 読む会: Nightmare at Test Time (坪井) 最終的な最小化問題：FDROP 二次計画 & 凸問題 効率的に解ける パラメータ数：O(事例数*次元数)　 SVMはO(事例数+次元数) 2006-07-29 ICML2006 読む会: Nightmare at Test Time (坪井)

ICML2006 読む会: Nightmare at Test Time (坪井) その他 (結果のみ紹介) Multi-classにも適用可能 Hinge loss以外の関数(log lossなど)にも適用可能かは不明(challenge) Kernelに出来る？ 消去素性選択があるため自明でない(challenge) 学習サンプル間で同じ素性を削除する場合は？ 凸問題だが、α(どの素性を消すかを現す変数)の制約をrelaxできないので提案手法ほど簡単に解けない 2006-07-29 ICML2006 読む会: Nightmare at Test Time (坪井)

素性選択との関係(1) 提案手法の方が計算量が少ない 一般的な素性選択 lossを最小にするfeatureをK個選択する問題 凸問題でない FDROPはdifferent computational class 二次計画 & 凸問題で効率的に解ける。 K個残した素性ベクトル 2006-07-29 ICML2006 読む会: Nightmare at Test Time (坪井)

素性選択との関係(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 (坪井)

ICML2006 読む会: Nightmare at Test Time (坪井) 分類問題による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 (坪井)