Bandit Feedback下での多クラス分類アルゴリズム

ICML2011のMulticlass Classification with Bandit Feedback using Adaptive Regularizationをざっくりと読んだのでメモ．
論文

概要

Bandit Feedbackでの多クラス分類問題における新たなアルゴリズムを提案
アルゴリズムは，Second-order Perceptronとupper-confidence boundを組み合わせたもの
- exploration時に現在のスコアや不確実性を考慮したものに拡張した点がポイント
Regret を達成 (既存手法のベストは，)
- 但し，データ分布には一定の確率分布に従う，という仮定を置いている
実験結果より，Label Noise環境下での分類精度が向上することを確認 (Bandit Feedbackと似ているため)

Bandit Feedback

Bandit Feedbackとは？

多クラス分類問題に関連する実タスクでは，多くの場合正解ラベルは明示的に与えられない．

Ex. 多クラス分類問題によるリコメンデーションを実装したとき，ユーザーが本当はどの商品をリコメンドして欲しかったかどうかは分からず，リコメンドされた商品を購入したかどうかしか分からない．

このような環境を，Bandit Feedbackと呼ぶ．

Bandit Feedbackの難しさ

「不正解」の場合は，正解ラベルに関する情報が非常に限定的．(正解ラベル候補は，K-1ラベル)
従って，学習の際にはexplorationとexploitationのトレードオフ調節が課題となる．

exploration : 解探索のため，スコアの低いラベルを予測に用いる
exploitation : 最高スコアのラベルをそのまま予測に用いる

アルゴリズム

不確実性スコアの導入

入力データ $\mathbf{x}_t$ に対するスコア $\mathbf{w}_i \mathbf{x}_t$ の不確実性を示すスコア $\eta_{i,t}$ を導入
この値が大きいほど， $\mathbf{w}_i \mathbf{x}_t$ で導出されるパラメータへの信頼度が低い
具体的には，
$\eta^2_{i,t} = \eta_t \mathbf{x}_t^T A_{i,t}^{-1} \mathbf{x}_t$
$\eta_t$ は，exploration, exploitationの調整パラメータ． $A_{i,t}$ は，second-order perceptronの共分散行列（厳密には，second-order perceptronとは，パラメータの更新方法が異なる）．
で定義