サポートクラスによるPassive-Aggressiveアルゴリズムの多クラス化

摘要

Online learning is recently getting attention in the field of NLP due to its simple updates, efficiency in terms of computing time and memory space, and theoretical guarantees for its performance. We propose Support Class Passive-Aggressive Algorithm (SPA), an online learning classifier for multiple classes, derived from the Passive Aggressive Algorithm (PA). While the PA framework allows integrations with different loss functions, so far, it has not been combined with a multiclass loss function that exactly classifies the current training instance into the correct class. Our SPA determines a set of support classes, and the parameters are updated for the support classes. SPA always classifies the current training instance into the correct class. Experiments show our method improves the traditional PA algorithms.%逐次学習は、訓練データを受け取る毎に簡単なパラメータ更新を行うだけでよいため、計算時間やメモリの効率が良い点、理論的な性能の保障など、多くの面から近年注目されている。本研究は、逐次学習の中でも有力な枠組の一つであるPassive-Aggressiveアルゴリズム（PA）を多クラス分類に拡張したSupport Class Passive-Aggressiveアルゴリズム（SPA）を提案する。PAは、損失関数を与えれば、一貫した定式化で多クラス分類のパラメータ更新式を導出することができるが、既存の多クラスRAで用いられている更新式はパラメータ更新後も受け取った訓練データを誤分類する場合がある。我々が提案するSPAは、データを受け取る毎にサポートクラスと呼ぶクラスの集合を定め、このサポートクラス全体に関してパラメータ更新を行う。SPAによる更新後の分類器は受け取った訓練データを必ず正しく分類する。文書分類問題および画像認識問題に対する評価実験を行い、SPAが既存の逐次学習の手法に比べ良い精度を達成することを確認した。