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

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

トップ > python

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

machine learning python

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

実装した手法

とりあえず以下の５つを実装した。他にも 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のリスト（データ数×１行列）、yとしてxに対応するノードのラベルを格納したリストを与えることにした。 つまり、Label propagationにおいては、グラフはパラメータで、特徴ベクトルはただのノードIDということになる。 scikit-learn準拠にするためにどうすれば良いかはこのへんに書いた

yamaguchiyuto.hatenablog.com

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

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

TransE [NIPS'13] を実装（と実験再現）した

machine learning paper python

Graph embedding を調べる上で避けては通れないっぽいTransEを実装して実験再現してみた。モデルがシンプルでカッコイイし実装も簡単だった。データもパラメータも公開されてて実験を再現できたのもポイント高い。

TransE

NIPS'13で提案されたGraph embeddingをする手法。Google scholarで既に100以上引用されていろんな拡張モデルが提案されてる。論文は以下。

papers.nips.cc

TransEはKnowledge graph（Freebaseとか）をベクトル空間上にembeddingする。入力としてKnowledge graphを与えると、全てのsubject, predicate, objectに対してそれぞれk次元のベクトルを出力する。ポイントは出力されたベクトル空間に構造があること。例えば、

v(Kei Nishikori) + v(profession) = v(tennis player)*1

みたいな足し算ができるようになる*2。これは、("Kei Nishikori", "profession", "tennis player")というトリプルがある（ありそう）ということに対応している。

これの何が嬉しいかというと、例えばKnowledge graphのスキーマを意識しながらSPARQLを書いて問合せするっていうめんどくさいことをしなくても、単にベクトルの足し算をするだけで ("Kei Nishikori", "profession", ?) みたいな質問に答えられるようになる。もっと言うと ("Kei Nishikori", "profession", "tennis player") というトリプルがKnowledge graph上になくても、ベクトルの足し算をするだけで"tennis player"という答えを予測できるようになる。

学習

D = \{(h_i, r_i, t_i)\}_{i=1}^{n}というトリプルの集合（つまりKnowledge graph）が与えられた時、全てのトリプルについてできるだけ以下を満たすようにしたい：

{ \displaystyle v(h)+v(r) \simeq v(t) }

逆に、Dに含まれないトリプル（例えば ("Kei Nishikori", "profession", "politician") とか）については上記の足し算が成り立たないようにしたい。

これをどうやるかというと、まず、トリプルの "それっぽさ" を測る以下のスコア関数を定義する：

{ \displaystyle f(h,r,t) = ||v(h)+v(r)-v(t)|| }

右辺はノルムを表す。これは足し算が成り立つ時は0に近い値を取り、そうじゃない時は大きな値を取る。それっぽいトリプルは足し算が成り立つようにしたいので、このスコア関数が小さい値を取るように上手いことベクトルを割り当ててやる。逆に全然それっぽくないトリプルについてはこのスコア関数が大きな値を取るようにしたい。

うまいことベクトルを割り当ててやるには、以下の目的関数を最小化するようなベクトルを学習すれば良い*3：

{ \displaystyle L(V) = \sum_{(h,r,t) \in D} max(0, f(h,r,t) + \gamma - f(h',r,t')) }

f(h,r,t) が小さくて f(h',r,t') が大きければ全体として小さくなる（ガンマはマージンみたいな役割）。ここで (h',r,t') というトリプルが突然出てきてるんだけどこれがすごく重要な役割を果たす。Dには正例しか含まれない、つまりそれっぽくないトリプルは含まれないので、じゃあ人工的にそれっぽくないトリプルを作っちゃいましょうということで出てきたのが (h',r,t')。どうやって作るかというと、あるトリプル (h,r,t) に対して、hかtのいずれかを、ランダムに取ってきたentity（h'もしくはt'）と交換する。つまり一つのトリプル (h,r,t) にたいして一つの "それっぽくない" トリプル (h',r,t')を作る。こうすることで正例と負例の両方を使って学習することができるようになる*4。

上記の目的関数の最小化には mini-batch SGD を使う。勾配は単に（L1 or L2）ノルムを微分すれば良い。

実装

transe.pyが本体で、それ以外は論文の実験を再現するためのスクリプト。注意するポイントは特に無さそう。論文に書いてあるとおりに実装できる（えらい）。論文にはearly stoppingしたほうが良いよって書いてあったけどそこだけ無視した（あんまり変わらない）。

Reproducing TransE experiments NIPS'13

実験

論文に書いてある実験結果を部分的に再現してみた。データもパラメータもちゃんと公開されててすばらしい。

データはここで公開されてるFB15kをつかった。これはFreebaseからサンプルされた15,000エンティティを含むデータ。割りと小さいけど評価実験するくらいならこれくらいでいいのかな。

まずデータを用意する。

% wget 'https://everest.hds.utc.fr/lib/exe/fetch.php?media=en:fb15k.tgz'
% mv fetch.php\?media=en:fb15k.tgz fb15k.tgz
% tar zxvf fb15k.tgz

学習する。パラメータは論文に書いてあるとおり。SGD は mini-batch の size を5000で 1000 epochs 回した*5。標準出力に表示されている 10 1528.218 みたいなのは 10 epochs 回した直後の validation set での mean rank の値を表している（Mean rankについては後述）。結果として学習されたモデルが "transe.model" というファイルに書き出される（pickle）。

% python train.py FB15k/freebase_mtr100_mte100-train.txt FB15k/freebase_mtr100_mte100-valid.txt
0 3560.291
10 1528.218
.
.
.
990 198.681

論文中の実験を再現する前に少し遊んでみる。predict.pyに 予測したいトリプル (h,r,?) を入力するとそれっぽい t を上位 n 件返してくれる。使用したデータセットはエンティティをFreebaseのmidで管理してるのでわかりづらいんだけど、"/m/051q39/"は有名なテニスプレイヤーの Rafael Nadal を表していて、以下の例ではそれのnationalityを知りたいということになる。

% python predict.py transe.model /m/051q39  /people/person/nationality 10
/m/0b1t1        7.87806854062
/m/0d04z6       8.14848562699
/m/06mkj        8.1821732884
/m/03rk0        8.24374933051
/m/027rn        8.27577702421
/m/0hzlz        8.2857627988
/m/0160w        8.31141651263
/m/015fr        8.37179251603
/m/05r4w        8.4572799401
/m/04g5k        8.4820680158

結果としてFreebaseのmidが出てくるので非常にわかりづらいんだけど、top3は"London", "Cuba", "Spain"となった。正しいnationalityはスペインなので、まあそれなりの結果なのかな。右の列の数値はスコア関数の値で、結果はこの値でソートされている（小さいほどそれっぽい）。ちなみに ("Rafael Nadal", "nationality", "Spain") というトリプルは学習データに含まれていないので、上手いこと正しいトリプルを予測できたことになる。データセットが小さいのであまりおもしろい結果は出ないんだけど、色々試してみるといいかも。

さてさて、論文中の実験を再現する。論文中ではMeanRankとHit10という二つの評価尺度が使われている。MeanRankというのは ("Kei Nishikori", "profession", ?) みたいなトリプルを入力した時に正しい答え "tennis player" が予測されたランクを全てのテストトリプルについて平均をとったもの。小さいほどよい。Hit10というのは同じくテストトリプルを入力した時に正しい答えが上位10位以内に予測された割合。大きいほどよい。

% python test.py transe.model FB15k/freebase_mtr100_mte100-test.txt
MeanRank: 190.301450796
Hit10: 0.417192869598

論文中ではMeanRankが243、Hit10が34.9になってるのでそれより結構良い結果が出ちゃったけどまぁいいでしょうということで。

まとめ

とにかくシンプル。ムダなところを一切削ぎ落としたようなモデルでカッコイイね。ただシンプル過ぎてこれでうまくいくのかよという感もある。実際TransEではうまくいかない例もいくつもあって、後続の（他の人が提案した）いろんなモデルで修正されてる。ただ後続の手法も枠組みはTransEとほぼおなじで、おおまかに言えばスコア関数 f を変えてるだけ。たくさんの人に使ってもらうには surprisingly simple and moderately effective なものを作るのが重要だといういい例だった。

*1:v(.)は埋め込まれたベクトルを表す

*2:ちょっと前にかなり話題になったword2vecっぽいし、論文中にもinpired by word2vecと書いてある。

*3:論文中の表記はわかりづらいので変更してある

*4:Negative samplingと言う。

*5:なぜかmini-batch sizeをどうしたかだけ論文中に記載がなかった。

Graph embedding の RESCAL [ICML'11] を実装した

machine learning paper python

最近Graph embeddingに興味があって調べてるので有名っぽいRESCAL [ICML'11] をとりあえず実装してみた。さすが結構引用されてるだけあって簡単お手頃に実装できた。やっぱシンプルさ大事。

Graph embedding

入力

グラフ G = (V,E)

出力

それぞれの頂点 v \in V に対して r次元ベクトルを１つずつ

要するにグラフ上の頂点の特徴を表す特徴ベクトルがほしいってこと。Representation learningとも言える。グラフ（上の頂点）をベクトル空間上に "埋め込む" からGraph embeddingと呼ばれている。この特徴ベクトルを使うことで普通のベクトルベースの機械学習手法をグラフにそのまま適用できるからうれしいねということになる。

RESCAL

ICML'11で提案されて、WWW'12でちょっと修正＆拡張されてちょっとでかめの実データで実験されてる。論文は以下。

RESCALは複数種類のエッジがあるグラフをembeddingする。複数種類のエッジがあるグラフっていうのはLODとかそういうやつ。最近の主流はこれで、DBPediaとかFreebaseとかYAGOとかのKnowledge graphをembeddingしたい人が多いらしい。

複数種類のエッジがあるグラフはテンソルで表現されるので、RESCALはテンソル分解ベースでembeddingをする。具体的には入力として与えられた n x n x m テンソルXに対して

{ \displaystyle X_k \approx AR_kA^{T} }

という分解をする。ただし、 X_k は n x n行列でテンソル X のk番目のfrontal slice（全部でm個ある）。また、Aは全てのkで共通。この n x r 行列 Aがembeddingの結果で、Aの各行がそれぞれの頂点の r次元ベクトルとなる。つまりテンソルXを復元できるような行列A（と行列Rk）を学習するという問題になる。基本的にはこれだけなんだけど詳細は論文をよんでね。

実装

お手軽簡単実装。ポイントはQR分解を使って目的関数に含まれる行列サイズを小さくするところと、クロネッカー積をうまいこと使うところかな。

gist3303398a61aa00f5707c

テスト

ICML'11の論文にある例（下の図）を使ってテストする。

f:id:yamaguchiyuto:20160214103156p:plain

著者的には (Bill, party, Party X) というトリプルが予測されてほしいらしい。果たして予測されるのか！？ 上のGistのコードを実行すると予測されたトリプルが出力される。

% python rescal.py
('Lyndon', 'vicePresidentOf', 'Bill')
('AI', 'vicePresidentOf', 'John')
('Bill', 'party', 'Party X')

確かに所望のトリプルは予測されたけど、余計なのも混じってる。まぁでも小さい例だしモデル上しょうがないのかな。

この例だけだと流石に小さすぎるので（気が向いたら）自分が公開してるTwitterリストのデータを使って試してみたい。

Following/Followers and Tags on 0.1 million Twitter Users - Zenodo

導出

書きたいけどちょっと力尽きた。気が向いたら。

まとめ

実装簡単。実行速い。精度はどうなんだろ*1。

*1:TransEの論文ではボロクソに書かれてた

scikit-learn準拠の学習器を作ってgrid searchとかcross validationする

python

Python Advent Calender 2014の19日目。

scikit-learnに準拠した学習器を自分で実装してscikit-learnに実装されているgrid searchとかcross validationを使えるようにするお話。Pythonの話というか完全にscikit-learnの話なんだけど、まあいいよね。

scikit-learnについてはこの辺がわかりやすいかな。

pythonの機械学習ライブラリscikit-learnの紹介

はじパタlt scikit-learnで始める機械学習

scikit-learn準拠にするには？

全部下のページに書いてある。

Contributing — scikit-learn 0.15.2 documentation

やること

  1. sklearn.base.BaseEstimatorを継承する
  2. 回帰ならRegressorMixinを（多重）継承する
  3. 分類ならClassifierMixinを（多重）継承する
  4. fitメソッドを実装する
    • 学習データとラベルを受け取って学習したパラメータをフィールドにセットする
    • initでパラメータをいじる操作を入れるとgrid searchが動かなくなる（後述）
  5. predictメソッドを実装する
    • テストデータを受け取ってラベルのリストを返す

実装例（リッジ回帰）

scikit-learn-compatible Ridge Regression

Grid search

使用例

パラメータlambをうまく選んでやらないといけない。scikit準拠で実装したのでscikitに実装されてるgrid searchが使えて簡単にパラメータのバリデーションが出来る。

GridSearchCVに学習器RidgeRegression()とパラメータのリストparametersとデータを何分割するかcvを与える。それでfitしてbest_estimator_を取るだけでスコアが最も高かったパラメータを持った学習器が手に入る。Grid searchなんてめんどくさい作業がたった４行で出来るなんて！

Grid search for oreore regression

結果

f:id:yamaguchiyuto:20141205140900p:plain

青が学習したい関数、青い点がgrid searchに使ったデータ、緑が学習した曲線。うまくパラメータ（ラムダ）が選ばれて過学習してない。やったね！

Cross validation

使用例

5-fold cross validationをする。簡単のためラムダは0にした。

Cross validationもものすごく簡単で、学習器、データ、cv、スコアとして何を使うか（ここではMSE）を渡すだけ。結果としてcvの数だけ指定したスコアが返ってくる。たったの３行。

Cross validation for oreore regression

結果

$ python cross_validation.py
-0.0552436216908

なぜかMSEなのに負の結果が帰って来て困惑したけどこれは仕様らしくて、下のページで議論されてる。どうやらMSEが-1倍された値が返ってくるらしい。

MSE is negative when returned by cross_val_score #2439

initでパラメータをいじるとダメ

例えば上で実装したRidgeRegressionの6行目を下のように変えるとgrid searchがエラーを吐いて動かなくなる。

self.lamb = 2*lamb

initではパラメータの代入しかしちゃいけないっぽい。公式にもこう書いてある。

As grid_search.GridSearchCV uses set_params to apply parameter setting to estimators, it is essential that calling set_params has the same effect as setting parameters using the init method. The easiest and recommended way to accomplish this is to not do any parameter validation in __init__. All logic behind estimator parameters, like translating string arguments into functions, should be done in fit.

まとめ

scikit-learn準拠の学習器を作ってgrid searchやcross validationをした。簡単なルールに従うだけでscikit-learn準拠に出来る。もちろんscikit-learnに元々入ってる学習器に対してもgrid searchやcross validationできる。超便利。

グラフのエッジリストから次数分布等をプロットするスクリプト書いた

python

グラフのデータを手に入れたらまずは次数分布をプロットするのが定石だけど、なぜか毎回毎回実装しなおしててアホだったから反省してちゃんと書いた。

次数分布とそのCDF、CCDFをプロットする。

要Numpy, Scipy, Matplotlib, Networkx。

使い方

言わずと知れたEnron email networkで試してみる。

まずデータをSNAPから取ってくる。

余談だけどSNAPにはいろんなネットワークデータがあって、これ眺めてるだけで楽しくなってくるね。

$ wget http://snap.stanford.edu/data/email-Enron.txt.gz
$ gunzip email-Enron.txt.gz

最初の4行は余計なものが入ってるので消す（tailで+5と指定すると5行目から最後までを出力してくれる便利機能があったなんて知らなかった）。

$ head -n4 email-Enron.txt
# Directed graph (each unordered pair of nodes is saved once): Email-Enron.txt
# Enron email network (edge indicated that email was exchanged, undirected edges)
# Nodes: 36692 Edges: 367662
# FromNodeId    ToNodeId
$ tail -n +5 email-Enron.txt > enron
$ head -n5 enron
0   1
1   0
1   2
1   3
1   4

各行にはエッジで繋がれてるノードのペアがタブ区切り（スペースでもOK）で記述されている必要がある。左がsource、右がdestination。

あとはedgelistのファイルを指定して実行するだけ。

$ python basic_plot.py enron

結果としてenron_{in|out}degree_{distribution|cdf|ccdf}.epsの6個のプロットが出力される。

ちなみにEnronのネットワークは無向グラフなのでindegreeもoutdegreeも同じになる。

enron_indegree_distribution.eps

f:id:yamaguchiyuto:20141214121220p:plain

enron_indegree_cdf.eps

f:id:yamaguchiyuto:20141214121223p:plain

enron_indegree_ccdf.eps

f:id:yamaguchiyuto:20141214121227p:plain

実装

Networkxでedgelistを読み込んでscipy.sparseに変換してから次数分布を計算してるけどこれが良いのか悪いのか分からない。多分悪い。