Passive-Aggressive Algorithmメモ

機械学習

はじめに

Perceptronについて調べてたりするとよく間違えた出てくるPAアルゴリズムについて調べたのでメモ。

Passive-Aggressive(PA) Algorithm

  • Passive-Aggressive
    • 心理学とかだと「やれといわれる(受動的)けど実際はやらない(攻撃的)」みたいな意味らしい
    • でも今回のは、制約条件を満たすようにできるだけ変化させずに更新する、的なニュアンスみたい
  • 以下、オンライン学習する話
  • 問題設定(2値分類の場合)
    • x : 入力ベクトル
    • y : 正解ラベル(1か-1)
    • w : 重みベクトル
    • max. w_{t+1}=argmin_{w \in R^n}{\frac{1}{2}{||w-w_t||^2}
    • s.t. loss(w; (x_t, y_t))=0
    • 要は、データが来たら、損失がないような一番変化の少ない重みwに更新する、を繰り返す
    • lossには、ヒンジ損失を用いる
      • loss(w; (x_t, y_t) = 0 : y(w*x)>=1
      • loss(w; (x_y, y_t) = 1 - y(w \cdot x) : otherwise
  • ラグランジュ未定乗数法を用いて上記の最適化問題を解くと、一回の更新式は、
    • w_{t+1}=w_t + \tau_t y_t x_t
    • \tau_t = \frac{loss_t}{||x_t||^2}
    • すなわち、データが来たら、損失を計算して、0じゃないならば式に従って重みwを更新する

PA-I, PA-II

  • PAではノイズが含まれていたり、線形分離不可能な場合はよろしくない
  • そこで、PAに「分類の緩さ」的なものを追加(スラック変数\xi, アグレッシブさC)
  • ソフトマージン的な。
  • PA-I
    • max. w_{t+1}=argmin_{w \in R^n}{\frac{1}{2}{||w-w_t||^2}+C \xi
    • s.t. loss(w; (x_t, y_t)) \leq \xi and \xi \geq 0
    • このとき、
    • \tau_t = min\{C, \frac{loss_t}{||x_t||^2}\}
  • PA-II
    • max. w_{t+1}=argmin_{w \in R^n}{\frac{1}{2}{||w-w_t||^2}+C \xi^2
    • s.t. loss(w; (x_t, y_t)) \leq \xi
    • このとき、
    • \tau_t = \frac{loss_t}{||x_t||^2 + \frac{1}{2C}}
  • 更新式の\tauが変わるだけ
  • 性能的にはPA-IIの方がよいみたい

回帰問題への適用

  • PAは回帰問題へも適用することができる
    • (1,2),(2,4),(3,6)と来たら(4,?)は何でしょう？みたいな問題
  • 問題設定(回帰の場合)
    • y_t : 実数値
    • lossに、ε-insensitiveヒンジ損失を用いる
    • loss(w; (x_t, y_t) = 0 : |w*x_t-y_t|<=ε
    • loss(w; (x_t, y_t) = |w \cdot x_t - y_t|-\epsilon : otherwise
  • 1回ごとの更新式は、
    • w_{t+1}=w_t + sign(y_t-\hat{y}_t)\tau_t x_t
    • \tauは上記と同じ
    • y_t : 正解の実数値
    • \hat{y}_t : 現在の重みwで計算したときの実数値

多クラス問題への適用

  • 多クラス問題へも適用することができる
  • kクラスあったら、それぞれに対しスコアを計算し、ランキングでクラスを推定する
    • 属するクラスは上位に来て、属しないクラスは下位にくる
  • 1個の重みベクトルで計算するsingle-prototypeとk個の重みベクトルで計算するmulti-prototypeがある
    • 以下、multi-prototypeクラス分類の場合
  • データが来たとき、正解ラベル集合Y_tから以下の2つのクラスを選ぶ
    • 正解ラベルで一番内積の値が小さいもの(r)
      • argmin_{r \in Y_t} w_t^r \cdot w_t
    • 正解じゃないラベルで一番内積の値が大きいもの(s)
      • argmax_{s \notin Y_t} w_t^s \cdot w_t
  • 損失関数
    • loss(w_t^1,...,w_t^k;(x_t, Y_t) = 0 : w_t^r \cdot x_t - w_t^s \cdot x_t \geq 1
    • loss(w_t^1,...,w_t^k;(x_t, Y_t) = 1-w_t^r \cdot x_t + w_t^s \cdot x_t : otherwise
  • 更新式
    • w_{t+1}^r=w_t^r+\tau x_t
    • w_{t+1}^s=w_t^s+\tau x_t
    • \tauは上記と同じ
  • 要は、分類で一番怪しい2つのラベルを見つけて、良い感じになるように重みをそれぞれ更新するだけ

その他

  • 論文では以下の問題についても書かれている
    • Uniclass Prediction(単一クラス予測)
    • Multi-class single-prototype classification
    • Cost-sensitive Multi-class classification
    • 構造学習

参考文献