多クラス識別問題におけるPassive-Aggressiveアルゴリズムの効率的厳密解法

松島 慎  清水 伸幸  吉田 和弘  二宮 崇  中川 裕志  

誌名
電子情報通信学会論文誌 D   Vol.J93-D   No.6   pp.724-732
発行日: 2010/06/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
論文種別: 特集論文 (情報爆発論文特集)
専門分野: 自然言語処理,知識獲得
キーワード: 
逐次学習,  多値分類,  PAアルゴリズム,  サポートクラス,  

本文: PDF(319KB)
>>論文を購入


あらまし: 
多くの機械学習ではデータ全体に対して一つの最適な関数を求めるため,大量のデータに対して学習を行う際に計算コストの面から困難が生じる場合があるが,逐次学習法は,データを一つずつ受け取りながら逐次的に識別関数を学習していく手法であり,低い計算コストで学習可能である.Passive-Aggressiveアルゴリズムは代表的な逐次学習法による学習アルゴリズムであるが,多クラス識別問題においては,厳密なPassive-Aggressiveアルゴリズムの枠組みから外れた近似解法が用いられてきた.本論文では,本来のPassive-Aggressiveアルゴリズムの厳密解をサポートクラスという概念を用いて導出し,識別関数の更新を効率的に行うための定理の証明を与えるとともにこれらに基づくアルゴリズムを提案する.この手法に対する文書分類や手書き文字認識の実験を行い,既存のPassive-Aggressiveアルゴリズムより精度が高く,SVMに比べ同程度の精度をより高速に実現することを確認した.