クロネッカー積とvec作用素とRoth's column lemma
クロネッカー積とvec作用素は見た目簡単なんだけど、各要素のインデックスを書き下すと頭の中こんがらがってわけわからなくなるから一旦整理した。インデックスに関する記事ってほとんどないね。あとそれに関連して Roth's column lemma っていうのが便利なのでちょっと紹介する。
まとめ
クロネッカー積とは
下の式を見ればひと目で分かるけど、 IxJ 行列 と KxL 行列 から IKxJL 行列を作る。
Wikipediaの例を見ると分かりやすい。
クロネッカー積のインデックス
クロネッカー積の定義は一目見ればすぐ分かるのに、各要素の定義を見ると途端にめんどくさくなる。
行のインデックスを見ると、K進数みたいになってるのが分かる。 の行のインデックスが1つ増えるためには、 の行のインデックスを一回ずつ辿らなきゃいけないって考えるとそうなることが分かる。列についても同じ。
実験
上式のインデキシングが本当に合ってるのか numpy.kron
を使って確かめる。
gist6cf39c77df3bf44fe6ed5aaf98c343cc
vec作用素
vec作用素は、以下のように IxJ 行列 の列ベクトルを全て一列に並べて1つの大きな IJ 次元列ベクトルを作る。
例えば、以下のようになる
vec作用素のインデックス
こっちはクロネッカー積よりは簡単。
クロネッカー積のときと同じで、J進数みたいになってる。各列ベクトルがJ次元なので、 の が増えるためには を全部辿らなきゃならない。
Roth's column lemma
これが成り立つ。
証明
をIxJ行列、 をJxK行列、 をKxL行列とし、
と置く。 は IxL 行列。
の各要素は(とうぜん)以下のように書ける。
クロネッカー積の要素を考えると
vec作用素の要素を考えると
なので、以下の行列ベクトル積の要素を考えると、
だから、証明完了。
Alternating Least Square (ALS) でCP分解
テンソル分解の基本中の基本のCP分解を導出して実装した。最適化の方法は色々あるらしいけど多分いちばんよく使われる Alternating Least Square (ALS) を使った。ちなみにここでテンソルって呼んでるのはただの多次元配列のこと。
まとめ
- CP分解とは
- AlSによるCP分解の更新式を導出
- ALSによるCP分解をpythonで実装
- 人工データを使って実験
CP分解とは
CP分解が何かを知るためには、まず Matrix factorization (MF) について知ると良い。
MFでは、N x M 行列 X を以下のように分解する
ここで、は N x R 行列で、は M x R 行列。この分解を要素ごとに書くとこうなる
つまり要素 を なんかよくわからない次元のベクトル との内積で表現することにしましょうと言っているわけ。
じゃあこの と っていうベクトルたちをどうやって求めるかという話になるわけだけど、それはこの辺に良い説明があるので説明しない。
Matrix Factorization: A Simple Tutorial and Implementation in Python @ quuxlabs
Matrix Factorizationとは - Qiita
ここまでわかるとCP分解が何なのかはすぐに理解できる。3階の I x J x K テンソル のCP分解は要素ごとに書くと以下のようになる
これはMFとほぼ同じで、右辺が3つの積になっただけ。簡単簡単。ほんとにこれだけ。
この記事では、この と と をどう求めるかを説明する。以下では、 と と をまとめて
と表記する。
ちなみにCP分解はCanonical Polyadic分解の略だけど、ほかにもいろんな呼び名があって、例えばPARAFAC(Parallel Factor Analysis)とか、CANDECOMP(Canonical Decomposition)とか。なぜか知らないけどいろいろある。ここではとりあえずCP分解に統一する。
CP分解のALSによる更新式の導出
上で軽く説明したように、CP分解では3階の I x J x K テンソル *1 を3つの行列 、、 (潜在変数行列と呼ぶ)に分解するわけだけど、ALS は簡単に言うと「他の2つを固定して、1つの潜在変数を最小二乗法で推定する」という方法。それを繰り返して更新していく。だから "Alternating" Least Square と呼ばれる。
ではまず をどう推定するかを考える。
最小二乗なので、コスト関数を以下で定義する
ただ単に全要素の差の二乗を取っているだけ。これを今後の見通しが良くなるように書き換える
はベクトルの要素積(アダマール積という)。
んで、これを最小化するを求めたいので、で微分する
ここで、
というベクトルを定義すると、以下のように書ける
これを0と置いて解くと、
となる。また、 と置いて行列で書くと、
となり、これでが求まった。
同様に、 と もついても以下のように書ける
このように、ALSでは2つの潜在変数行列を固定して、1つの潜在変数行列を更新するということを繰り返す。まとめると、
- 、、を適当に初期化
- 収束するまで3-6を繰り返す
実装
入力データは X[(i,j,k)] = value
という辞書で与える。fit
で学習して、predict
で予測する。self.A[i]
にi次のモードに対応する潜在変数行列が入っている。
上の説明では正則化は入れてなかったけど、データによっては逆行列の計算でこける(特異行列)ので、実装ではL2正則化をいれてある。
あと、潜在変数行列は平均 0、分散 0.01 の正規分布で初期化した。
gist36b4c4c07e96e392f9c876ddcc84e7bc
実験
適当な潜在変数を予め用意して、それを使ってデータテンソルを作る。そんで、CP分解でそのテンソルを分解する。
fit
すると、self._losses
に各イテレーション時のロスの値が入るので、それをプロットした。
適当に選んだ要素をちゃんとCP分解が復元できるかもためした(うまくいった)。
scikit-learn準拠で Label propagation とか実装した
scikit-learn準拠で Label propagation 的なアルゴリズム達を実装した。なんで実装したかというと、
- グラフそのもの(隣接行列)を入力したい。 scikit-learnには既にsklearn.semi_supervised.LabelPropagationが実装されてるけど、これはグラフを入力するんじゃなくて、普通にサンプル数×特徴数のデータ行列を与えて、そこから類似度グラフを作るようになってる。これだと例えば手元にソーシャルグラフがあって、そのユーザ(ノード)の属性(興味とか)を Label propagation で推定するということができない。
- ハイパーパラメータを楽に決めたい。 自分でグリッドサーチとかやるのはめんどくさいので、sklearn.grid_search.GridSearchCVとかを使いたい。そのためにsklearn準拠にした。
- 自分の研究成果を使いやすい形で公開したい。 AAAI15とSDM16でそれぞれラベル伝搬てきなアルゴリズムを提案したので、それを簡単に使えるようにした。
コード
使い方は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と比較して、ラベルノイズがどーのこーのという話はこのへんに書いた
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は隣同士が同じラベルを持つか異なるラベルを持つかをデータから勝手に判断してくれるのでどちらにも適用できる。詳細はこのへんに書いた
Confidence-Aware Modulated Label Propagation (CAMLP) [Yamaguchi+, SDM'16]
OMNIは隣同士がどういうラベルを持つかをデータから推定してくれるようになっているけど、当然データ(ラベル付きノード)が少ないときはうまくいかない。そこでCAMLPはあるラベルとあるラベルがどれくらいの確率で接続するかをパラメータとして指定する。パラメータは増えるが、適切にパラメータを決められれば強い。そういえばこの手法の紹介記事を書いてなかったからそのうち書こうかな(書かない)。
実装のポイント
- 上記の手法は全て F <- PF + B という行列演算の繰り返しに帰着する(CAMLPは少し例外)。Fはデータ数×ラベル数の行列で、各行に対応するデータが各ラベルを持つスコア(大きいほどそれっぽい)が入る。Pは遷移行列みたいなやつ。Bはそれぞれの手法で意味合いが少し違うけど、あらかじめ与えられたラベル(教師データ)が入る。なので、PとBを作ってやれば、あとは全ての手法で全く同じ行列演算をするだけになるから実装が簡単!
- scikit-learn準拠にするためには、
fit(X,y)
で学習、predict(X)
で予測するようにしないといけない。なので、fit
とかpredict
に直接グラフ(隣接行列)を渡すことは出来ない。そこで、グラフはパラメータとして与えることにして、X
としてノードIDのリスト(データ数×1行列)、y
としてxに対応するノードのラベルを格納したリストを与えることにした。 つまり、Label propagationにおいては、グラフはパラメータで、特徴ベクトルはただのノードIDということになる。 scikit-learn準拠にするためにどうすれば良いかはこのへんに書いた
TransE [NIPS'13] を実装(と実験再現)した
Graph embedding を調べる上で避けては通れないっぽいTransEを実装して実験再現してみた。モデルがシンプルでカッコイイし実装も簡単だった。データもパラメータも公開されてて実験を再現できたのもポイント高い。
TransE
NIPS'13で提案されたGraph embeddingをする手法。Google scholarで既に100以上引用されていろんな拡張モデルが提案されてる。論文は以下。
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"という答えを予測できるようになる。
学習
というトリプルの集合(つまりKnowledge graph)が与えられた時、全てのトリプルについてできるだけ以下を満たすようにしたい:
逆に、Dに含まれないトリプル(例えば ("Kei Nishikori", "profession", "politician") とか)については上記の足し算が成り立たないようにしたい。
これをどうやるかというと、まず、トリプルの "それっぽさ" を測る以下のスコア関数を定義する:
右辺はノルムを表す。これは足し算が成り立つ時は0に近い値を取り、そうじゃない時は大きな値を取る。それっぽいトリプルは足し算が成り立つようにしたいので、このスコア関数が小さい値を取るように上手いことベクトルを割り当ててやる。逆に全然それっぽくないトリプルについてはこのスコア関数が大きな値を取るようにしたい。
うまいことベクトルを割り当ててやるには、以下の目的関数を最小化するようなベクトルを学習すれば良い*3:
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 なものを作るのが重要だといういい例だった。
Graph embedding の RESCAL [ICML'11] を実装した
最近Graph embeddingに興味があって調べてるので有名っぽいRESCAL [ICML'11] をとりあえず実装してみた。さすが結構引用されてるだけあって簡単お手頃に実装できた。やっぱシンプルさ大事。
Graph embedding
入力
グラフ G = (V,E)
出力
それぞれの頂点 に対して r次元ベクトルを1つずつ
要するにグラフ上の頂点の特徴を表す特徴ベクトルがほしいってこと。Representation learningとも言える。グラフ(上の頂点)をベクトル空間上に "埋め込む" からGraph embeddingと呼ばれている。この特徴ベクトルを使うことで普通のベクトルベースの機械学習手法をグラフにそのまま適用できるからうれしいねということになる。
RESCAL
ICML'11で提案されて、WWW'12でちょっと修正&拡張されてちょっとでかめの実データで実験されてる。論文は以下。
- A Three-Way Model for Collective Learning on Multi-Relational Data, ICML11
- Factorizing YAGO Scalable Machine Learning for Linked Data, WWW12
RESCALは複数種類のエッジがあるグラフをembeddingする。複数種類のエッジがあるグラフっていうのはLODとかそういうやつ。最近の主流はこれで、DBPediaとかFreebaseとかYAGOとかのKnowledge graphをembeddingしたい人が多いらしい。
複数種類のエッジがあるグラフはテンソルで表現されるので、RESCALはテンソル分解ベースでembeddingをする。具体的には入力として与えられた n x n x m テンソルXに対して
という分解をする。ただし、 は n x n行列でテンソル X のk番目のfrontal slice(全部でm個ある)。また、Aは全てのkで共通。この n x r 行列 Aがembeddingの結果で、Aの各行がそれぞれの頂点の r次元ベクトルとなる。つまりテンソルXを復元できるような行列A(と行列Rk)を学習するという問題になる。基本的にはこれだけなんだけど詳細は論文をよんでね。
実装
お手軽簡単実装。ポイントはQR分解を使って目的関数に含まれる行列サイズを小さくするところと、クロネッカー積をうまいこと使うところかな。
テスト
ICML'11の論文にある例(下の図)を使ってテストする。
著者的には (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の論文ではボロクソに書かれてた