PA

  • Passive aggressiveは，ヒンジ損失が0となるようなパラメータの中で，今のパラメータに一番ユークリッド距離が近いパラメータを探して，更新する
    • 今のデータを十分なマージンで正しく分類できるように
      • 今のパラメータで正しく分類できていたとしても自信がないときは更新する
      • 間違って分類しているときは，間違い具合に応じて更新幅を調整する．また更新幅は入力のノルムで正規化されている
    • また，これまでのパラメータを尊重するように
  • つまり，PAは次の最適化問題を逐次的に解く
    • $ \bold{w}^{(t+1)} = \arg \min_{\bold{w}} \frac{1}{2} || \bold{w} - \bold{w}^{(t)} ||^2$
    • subject to $l_{hinge} = \max(0, 1 - y^{(t)} \bold{w} \cdot \bold{x}^{(t)}) =0$

導出

  • $l_{hinge} \geq 0$であり，場合分けして考える
  • $l_{hinge} = 0$のとき
    • $\bold{w}^{(t)}$が最適値（更新しない）
  • $l_{hinge} > 0$のとき
    • ラグランジュの未定乗数法を使い，制約を式の中に埋め込む
    • $ L(\bold{w}, \tau) = \left( \frac{1}{2} || \bold{w} - \bold{w}^{(t)} ||^2 \right) + \tau \left( 1 - y^{(t)} \bold{w} \cdot \bold{x}^{(t)} \right)$ $(\tau \geq 0)$
    • KKT条件を満たすので，最適値は
      • まず$\frac{\partial L(\bold{w}, \tau) }{\partial \bold{w}} = 0$を解いて，
        • $\bold{w} = \bold{w}^{(t)} + \tau y^{(t)} \bold{x}^{(t)}$
      • 代入して$L(\tau) = - \frac{1}{2} \tau^2 ||\bold{x}^{(t)} ||^2 + \tau (1- y^{(t)} \bold{w} \cdot \bold{x}^{(t)})$
      • $ \frac{\partial L(\tau)}{\partial \tau} = 0$を解いて，
        • $\tau = \frac{1- y^{(t)} \bold{w} \cdot \bold{x}^{(t)}}{ || \bold{x}^{(t)} ||^2 }$
    • よって，
      • $\bold{w}^{(t+1)} = \bold{w}^{(t)} + \frac{1- y^{(t)} \bold{w} \cdot \bold{x}^{(t)}}{ || \bold{x}^{(t)} ||^2 } y^{(t)} \bold{x}^{(t)} = \bold{w}^{(t)} + \frac{ l_{hinge}}{ || \bold{x}^{(t)} ||^2 } y^{(t)} \bold{x}^{(t)} $

PA-I, PA-II

  • ノイズや線形分離不可能な場合のため，ある程度の誤りは許容するように変更
    • スラック変数$\xi$,と，アグレッシブさを表す定数$C$を導入する
  • PA-I
    • $ \bold{w}^{(t+1)} = \arg \min_{\bold{w}} \frac{1}{2} || \bold{w} - \bold{w}^{(t)} ||^2 + C \xi$
    • subject to $l_{hinge} = \max(0, 1 - y^{(t)} \bold{w} \cdot \bold{x}^{(t)}) \leq \xi, \xi \geq 0$
  • PA-II
    • $ \bold{w}^{(t+1)} = \arg \min_{\bold{w}} \frac{1}{2} || \bold{w} - \bold{w}^{(t)} ||^2 + C \xi^2$
    • subject to $l_{hinge} = \max(0, 1 - y^{(t)} \bold{w} \cdot \bold{x}^{(t)}) \leq \xi^2$
  • これを解くと更新式はそれぞれ次のようになる
    • PA-I
      • $\bold{w}^{(t+1)} = \bold{w}^{(t)} + \min \left( C, \frac{ l_{hinge}}{ || \bold{x}^{(t)} ||^2 } \right) y^{(t)} \bold{x}^{(t)} $
    • PA-II
      • $\bold{w}^{(t+1)} = \bold{w}^{(t)} + \frac{ l_{hinge}}{ || \bold{x}^{(t)} ||^2 + \frac{1}{2C} }y^{(t)} \bold{x}^{(t)} $