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)}$