でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

Label propagationとLabel spreading

グラフベース半教師あり学習 (SSL) のLabel propagation (LP) とLabel spreading (LS) の違いを説明している文献があまりなかったのでそれについてちょっと書いてみる。SSL自体とかLP、LSについては以下の記事にまとめた文献がいい感じなのでそちらを参照。

半教師あり学習のモデル仮定 - でかいチーズをベーグルする

LPの元論文はこれ (PDF)

"Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions", ICML2003

LSの元論文はこれ (PDF)

"Learning with Local and Global Consistency", NIPS2003

まとめ

  • LPとLSの超概要、ランダムウォークとしての解釈、最適化問題としての解釈を書いた
  • 軽い実験をした
    • 基本的にLSの方がLPより高精度っぽい
    • ラベル密度が小さい時は精度の差が開くっぽい
    • ラベルにノイズが有る時は精度の差が開くっぽい

Label propagation

超概要

データをノード、データ間の類似度をエッジとしてグラフを構築し、そのグラフ上でラベル付きノードからラベル無しノードへラベルを「伝播」させる。近くにラベル1が多いノードはラベル1に、近くにラベル2が多いノードはラベル2に分類される感じ。解としてはラベルなしノードiのラベルがkである確率 F_{ik}が全てのiとkについて得られる(つまり行列Fが得られる)。ちなみにパラメータはない*1

ランダムウォークとしての解釈

データiのラベルを知りたいとき、グラフ上でデータiに対応するノードからランダムウォークをスタートする。このとき、ランダムウォークが初めにラベルがkであるラベル付きデータ(ノード)に到達する確率は、LPによって得られる解 F_{ik}と等しい。

最適化問題としての解釈

  1. ラベル付きデータのラベルは変化しないという制約のもと、
  2. グラフ上で隣接しているノードは同じラベルを持ちやすい

というコスト関数を最小化する Fを求める。これがLPの解と等しい。

Label spreading

超概要

LPと同様にデータ間の類似度からグラフを構築し、ラベル付きノードからラベル無しノードへとラベルを伝播させる。LPとの違いはラベル付きノードのラベルも同時に再推定する点。つまり、LSはラベル付きデータ i のラベルが変化することを許す。例えば、ラベルが k であるラベル付きデータ i がたくさんのラベル k' データと類似していれば、i のラベルは k ではなく実は k' である確率が高いと出力する。これがLSのキモ。

パラメータは\alpha \in (0,1)の一つで、どれだけ元のラベルを重視するかを表す。\alphaが大きいほどラベル付きデータのラベルは変わりやすくなる。パラメータのチューニングが必要という点ではLSの方が使いづらいのかな。ちなみに元論文では\alpha = 0.99と決め打ちされていた。

ランダムウォークとしての解釈

LPと同様に、データ i のラベルを知りたいとき、グラフ上でデータ i に対応するノードからランダムウォークをスタートする。ただし確率\alphaで隣接ノードのどれかに移動するが、確率(1-\alpha)でデータ i に対応するノードに戻る。これを無限ステップ繰り返した時、ウォークがラベル k のラベル付きノードにいる確率はLSの出力F_{ik}に等しい。

最適化問題としての解釈

  1. ラベル付きデータは元々の自分のラベルからは変わりづらく、
  2. グラフ上で隣接しているノードは同じラベルを持ちやすい

というコスト関数を最小化するFを求める。これがLSの解と等しい。パラメータ\alphaは(1)と(2)の重みとして働く。LPではラベル付きノードがもともとの自分のラベルから変わらないような 制約 を入れていたが、LSでは制約にはなっていない。

実験

LPとLSはどっちを使ったらいいんだ、どう使い分けたらいいんだ、さっぱり分からん!ということで軽く実験をしてみた。scikit-learnに入ってるLPとLSの実装Digitsデータを使った。LPとLSの他にふつーのSVMも比較した。

実験設定

Digitsデータを分類した。入力は画像データそのもので、ラベルはその画像がどの数字か(0から9)。1000サンプルのうちからランダムで一定の割合のノードのラベルを隠して分類を30回繰り返した。LP、LS、SVMカーネルはRBFカーネルを使った。パラメータ(バンド幅、SVMのC)はグリッドサーチで決定。LSの\alphaは元論文と同様に0.99に決め打ちした。

  1. ラベル密度を変えた実験:全体のデータ数に対するラベル付きデータの割合を1%から50%まで変化させてどう精度が変わるかを見た。
  2. ラベルにノイズを入れた実験:ラベル付きデータのラベルをランダムに変更してどう精度が変わるかを見た。ノイズを入れる割合は0%から50%、ラベル密度は5%にした。

コードはここに置いたので興味のある人だけどうぞ。

ラベル密度を変えた実験

結果

  • 期待通りラベル密度を小さくしていくとLPとLS共にSVMに勝った。
  • LPよりLSの方がちょっと精度が高い。
  • ラベル密度を小さくしていくとLPとLSの精度の差が少しずつ開いていく。

f:id:yamaguchiyuto:20141202235147p:plain

横軸はラベル密度、縦軸は精度、エラーバーは標準偏差

考察(注意:個人の感想です)

ラベル密度が小さい時にSVMに勝てるのはまぁ周知の事実。と言うかそれが半教師あり学習の強み。 面白いのはラベル密度を小さくしていくとLPとLSの精度の差が開いたところ。なんでか考えたんだけど、多分LSのランダムウォークとしての解釈のところでランダムウォークが確率1-\alphaで始点に戻るところが効いてるのかな。ラベル密度が小さいとランダムウォークがラベル付きノードに到達せずにどんどん始点から遠ざかってしまう事が多くなるけど、LSでは一定確率で始点に戻ることでそれがある程度防げるとか。

ラベルにノイズを入れた実験

結果

  • ノイズを入れる割合を大きくしていくとLPとLSの差が顕著に開く。
  • SVMは悲惨な結果だけどLPとLSは高い精度を維持。

f:id:yamaguchiyuto:20141202235150p:plain

横軸はノイズの割合、縦軸は精度、エラーバーは標準偏差

考察(注意:個人の感想です)

予想通りの結果になった。LSはもともとラベルがついてるデータのラベルを変更することも許してるから、ノイズでラベルが変わってしまったノードのラベルも正しく修正出来たってことだと思う。一方でLPとSVMはノイズで変わってしまったラベルも"信じきって"学習した結果精度が落ちてしまったって感じかな?ちょっとわからなかったのが、LPの精度もそこまで下がらなかったところ。ラベル密度も小さいし(1000サンプル中50個しかない)、そのうちの半分のラベルがランダムに変更されているのにこれだけ精度高いとは。。。

おわりに

今回実験した限りだとLSを使っとけば問題ないという結果になった。まぁでも「どんな場合でもLSの方が優れている」なんてことは無いしLPを使ったほうがいい場面も多分あるんだろうな。分からんけど。ちなみに今回の実験の設定ではSVMが悲惨な結果でLPとLSが圧勝してたけど、これは今回はLPとLSのモデル仮定(類似してるデータは同じラベルを持つ)が正しかったからであって、どんな場合でも(ラベル密度が小さければ)半教師ありがSVMとかの教師あり学習に勝てるわけじゃない。

*1:類似度の計算にRBFカーネルを使う場合が多いので、その場合はバンド幅のパラメータが必要になる。