Learning with Local and Global Consistency - todo314 @ ウィキ

Learning with Local and Global Consistency

• Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, Bernhard Schölkopf
• NIPS 2003

概要

• 半教師あり学習
• 滑らかにしたい

仮定

• 局所的：近くの点は同じラベルを持つ
• 大域的：同じ構造中の点同士は同じラベルを持ちやすい
• k-NNとかは前者だけで後者はあまり反映出来ていない
• ただのSVMでも微妙

提案アルゴリズム

• 自分のラベルを周りに伝播する感じ
• x1,…xlがラベル有り（y1,…,yl）、x{l+1},…,xnがラベル無し
• n×c行列F
  • $$ y_i = \mathrm{argmax}_{j}F_{ij} $$
  • 一番大きいラベルを割り当てる
• n×c行列Y
  • $$ Y_{ij}=[y_i=j] $$
  • ラベル無しのはどうするの？

• アルゴリズムの挙動

1. affinity matrix Wを構築
2. S = D^{-1/2}WD^{-1/2}
3. F(t+1)=αSF(t)+(1-α)Y を反復
4. F*を元に出力

• ラベル有りの入力に対応するラベル変化しうる
• α=0.99とかして、ちょっとだけ加味する
• 大体personalized PageRank
  • 参考 http://yamaguchiyuto.hatenablog.com/entry/graph-base-ssl
  • SをWD^{-1}とかにしてもOK
• F*=(1-α)(I-αS)^{-1} Y

• Regularization Framework
• $$ \frac{1}{2}\left(\sum_{i,j} W_{ij}\left\| \frac{F_i}{\sqrt{D_{ii}}} - \frac{F_j}{\sqrt{D_{jj}} } \right\|^2 + \mu\sum_{i}\|F_i -Y_i\|^2 \right) $$
• でこれの最小値がF*で達成される

実験

• toy example、桁認識、テキスト分類
• 反復していくとじわじわ伝搬していく
• 滑らかになっていく様子も何か描画されている
• SVMした（微妙な）結果をsmoothingすると良くなった

まとめ

• こんな感じで良いのだなぁ…
• 本当はもっとスペクトラルな感じの解析とかを加えたいのだろう。

NIPS グラフベース半教師あり学習 ラベル伝播 半教師あり学習

2017/06/11