PRML読書会 #5 資料「線形識別モデル(3)」

機械学習 読書会 PRML
これは パターン認識と機械学習(PRML)読書会 #5 (4章 線形識別モデル) での発表用の資料「4.1.7 パーセプトロン・アルゴリズム」〜「おまけ(PA, CW)」です。 まとめメインで、細かい計算やサンプルは板書する予定です。

4.1.7 パーセプトロンアルゴリズム

  • 線形モデル y({\boldsymbol x}) = {\boldsymbol w}^T \phi({\boldsymbol x}) において、
    • φは特徴ベクトル、 \phi_0({\boldsymbol x}) = 1 (bias)
    • 目的変数: t ∈ {-1, +1}
    • {\boldsymbol w}^T \phi({\boldsymbol x}) \geq 0 なら +1(positive), < 0 なら -1(negative) に分類
  • ここで {\boldsymbol w}^T \phi({\boldsymbol x}_n) t_n が正の時は正解、負の時は誤分類を示す
  • 誤差関数 : E_P({\boldsymbol w}) = -\sum_{n\in\mathcal{M}} {\boldsymbol w}^T \phi_n t_n, \hspace{4ex} \mathcal{M}: 誤分類された n
  • {\boldsymbol w}^{(\tau+1)}={\boldsymbol w}^{(\tau)}-\eta\nabla E_P({\boldsymbol w})={\boldsymbol w}^{(\tau)}+\eta\phi_n t_n
    • \eta : 学習率パラメータ。w を定数倍しても符号は不変ゆえ、\eta=1 としてよい
  • w は decision surface の法線ベクトル。これに誤分類した入力ベクトルを加える(あるいは引く)という動作になる
パーセプトロンの収束定理

「厳密解が存在する場合は」
「有限回」の繰り返しで解に収束する

問題点：
  • 収束に必要な繰り返し回数が非常に多い
  • 初期値やデータの提示順によって様々な解に収束してしまう(★解の最適性を評価していない)
  • K>2 への一般化が容易ではない(値の正負しか意味を持たないため)
Passive Aggresive Algorism *1
  • margin が閾値 1 を下回っていたら、正解であっても補正する(aggressive)
  • 累積二乗損失(cumulative squared loss)の最大値が想定可能であることを示す
  • １次＆２次の正則項を導入できる(PA1 & PA2)
  • Cost-Sensitive Multiclass Classification に応用
    • ★そのうち試してみるつもり
Confidence-Weighted*2
  • {\boldsymbol w} が \mathcal{N}({\boldsymbol \mu}, \Sigma) に従うとして、({\boldsymbol \mu}, \Sigma) を逐次学習するアルゴリズム
    • ★結構泥臭い計算＆泥臭い結果なのに、性能がいいというのがおもしろい
  • 収束が早い。繰り返し無しでも十分な精度
    • ★と書いてあるが、岡野原さんの oll＋手元のデータで試した限りでは、１回では精度がでなかった

*1:Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz, S., & Singer, Y. (2006). Online passive-aggressive algorithms. JMLR, 7, 551-585.

*2:Mark Dredze, Koby Crammer, and Fernando Pereira. 2008. Confidence-weighted linear classification. In ICML.