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

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

scikit-learn準拠で Label propagation とか実装した

scikit-learn準拠で Label propagation 的なアルゴリズム達を実装した。なんで実装したかというと、

  1. グラフそのもの(隣接行列)を入力したい。 scikit-learnには既にsklearn.semi_supervised.LabelPropagationが実装されてるけど、これはグラフを入力するんじゃなくて、普通にサンプル数×特徴数のデータ行列を与えて、そこから類似度グラフを作るようになってる。これだと例えば手元にソーシャルグラフがあって、そのユーザ(ノード)の属性(興味とか)を Label propagation で推定するということができない。
  2. ハイパーパラメータを楽に決めたい。 自分でグリッドサーチとかやるのはめんどくさいので、sklearn.grid_search.GridSearchCVとかを使いたい。そのためにsklearn準拠にした。
  3. 自分の研究成果を使いやすい形で公開したい。 AAAI15とSDM16でそれぞれラベル伝搬てきなアルゴリズムを提案したので、それを簡単に使えるようにした。

コード

github.com

使い方はREADME.mdに書いてあるけど、超ざっくり書くとこんな感じ。

from label_propagation import HMN
clf = HMN(graph=G) # Gは隣接行列(scipy.sparse)
clf.fit(x_train,y_train) # x_trainはラベル付きノードIDのリスト、y_trainは対応するノードのラベルのリスト
predicted = clf.predict(x_test) # x_testラベルを推定したいノードIDのリスト

あと、自分でpythonコードを書かなくても使えるようにmain.pyも書いた。例えばこうする(詳細はREADME)

$ python main.py lgc -g sample.edgelist -l sample.label -o outputfile --alpha 0.99

実装した手法

とりあえず以下の5つを実装した。他にも MAD [PKDD'09] とかもあるけど、それはまた今度。

Harmonic Function (HMN) [Zhu+, ICML'03]

Label propagationの始祖、全ての始まり。ハイパーパラメータが一つもない*1から簡単に使える反面、ラベルノイズに弱いという弱点がある。次のLGCと比較して、ラベルノイズがどーのこーのという話はこのへんに書いた

yamaguchiyuto.hatenablog.com

Local and Global Consistency (LGC) [Zhou+, NIPS'04]

HMNと比較するとラベルノイズに強い。でも、ラベルノイズをどの程度許容するかというパラメータが一つあるのでそれを調節する必要がある。Label propagation と言うと一般にこれを指すことが多い気がする。

Partially Absorbing Random Walk (PARW) [Wu+, NIPS'12]

PARWはノードの次数を考慮して、次数の小さいノードを超えてラベルが伝搬しないようにしている。次数の小さいノードは密なクラスタ間を接続するブリッジになっていることが多いので、こういうふうにするらしい*2。ただし、実世界のネットワーク(ソーシャルグラフとか)は次数分布がベキ分布に従っている(ハブがある)ことが多いため、そういう場合はうまくいかないと思う。

OMNI-Prop (OMNI) [Yamaguchi+, AAAI'15]

上記の三つの手法は、「隣同士のノードは同じラベルを持つ」という仮定をおいているため、「隣同士が異なるラベルを持つ」ようなグラフには適用できない。それに対してOMNIは隣同士が同じラベルを持つか異なるラベルを持つかをデータから勝手に判断してくれるのでどちらにも適用できる。詳細はこのへんに書いた

yamaguchiyuto.hatenablog.com

Confidence-Aware Modulated Label Propagation (CAMLP) [Yamaguchi+, SDM'16]

OMNIは隣同士がどういうラベルを持つかをデータから推定してくれるようになっているけど、当然データ(ラベル付きノード)が少ないときはうまくいかない。そこでCAMLPはあるラベルとあるラベルがどれくらいの確率で接続するかをパラメータとして指定する。パラメータは増えるが、適切にパラメータを決められれば強い。そういえばこの手法の紹介記事を書いてなかったからそのうち書こうかな(書かない)。

実装のポイント

  1. 上記の手法は全て F <- PF + B という行列演算の繰り返しに帰着する(CAMLPは少し例外)。Fはデータ数×ラベル数の行列で、各行に対応するデータが各ラベルを持つスコア(大きいほどそれっぽい)が入る。Pは遷移行列みたいなやつ。Bはそれぞれの手法で意味合いが少し違うけど、あらかじめ与えられたラベル(教師データ)が入る。なので、PとBを作ってやれば、あとは全ての手法で全く同じ行列演算をするだけになるから実装が簡単!
  2. scikit-learn準拠にするためには、fit(X,y)で学習、predict(X)で予測するようにしないといけない。なので、fitとかpredictに直接グラフ(隣接行列)を渡すことは出来ない。そこで、グラフはパラメータとして与えることにして、XとしてノードIDのリスト(データ数×1行列)、yとしてxに対応するノードのラベルを格納したリストを与えることにした。 つまり、Label propagationにおいては、グラフはパラメータで、特徴ベクトルはただのノードIDということになる。 scikit-learn準拠にするためにどうすれば良いかはこのへんに書いた

yamaguchiyuto.hatenablog.com

*1:類似度行列を作るときには類似度の定義やらなにやらに関するパラメータがあるけど、今回はグラフそのものを与えるので必要ない。

*2:はっきりとクラスタに分かれているようなユークリッド空間上のデータ点から類似度グラフを作った場合はこうなる。詳細は論文で。