Online Passive-Aggressive Algorithms on a Budget

AISTATS という学会で出てた論文．Projectron の更新の遅さを解決している模様．より正確には，Forgetron や Random Budget Perceptron と更新が同じ計算オーダ (O(B); BPA-NN) で O(B^2) の Projectron++ と同程度の精度が出るとのこと．パッと見たところ，mistake bound の analysis は無いようだ．あと，hinge loss を ramp loss にして精度改善 (訓練例のマージンが小さい時だけ更新する PA-I という感じの更新式). ramp loss と active learning の関連に言及している辺りが面白い．以前聴いた Learning with Annotation Noise も関係してるかな (後で確認しよう)．