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の論文ではボロクソに書かれてた
CMU教授直伝の論文の書き方
CMUに留学している時にFaloutsos教授に教わった論文の書き方をまとめる。この書き方に従うことで論文の採択率がかなり上がった。今となっては自分的に当たり前のことだし、できる研究者の皆様は自然と守っていることも多いと思うけど良い論文を書きたいと思っている学生とかに参考にしてもらえたらと思う。ただし、Faloutsos教授に教えてもらったことを一旦自分で噛み砕いてからまとめたものなので自分の主観とかが混じってしまっているかもしれない。
主語が大きくならないように予め断っておくけど、この書き方はもちろんすべての論文に対して当てはまるわけじゃなくて以下の前提条件がある。
- 国際会議論文である
- データマイニング関連分野の論文である
論文誌とか卒論とかもっと長めの論文を書くときは当てはまらない項目もあるし、データマイニング関連分野以外の論文を書いたことが無いのでそれ以外の分野の論文に当てはまるかも分からない。
"Make your paper STRUCTURED and APPEALING"
論文を書くときの思想。以下のTIPSは全てこの思想に従ってる。論文を構造化することでこの論文に何が書いてあるのかがパッと見わかるようになるし、アピーリングにすることで読んでみたくなる。
論文を構造化するというのはだらだらと文章を書くんじゃなくてResearch questionに番号をつけて適宜参照するとか、箇条書きをうまく使うとか、主張一つ一つに番号を付けるとか。論文中のベタ書き文章は実験結果とか図とか表とか定理とかを説明するためにあるだけであって、極端だけど おまけ にすぎない。おまけをだらだらと書くのはやめよう*1。
(MUST) "Don't go into detail in abstract"
アブストには詳細を書かない。特に提案アルゴリズムの詳細なんて書いた日にはそんな論文は誰も読まなくなる。読者がアブストに期待しているのは「その論文によって何ができるようになったのか(What)」を知ることであって、「どのようにしたのか(How)」ではない。
(MUST) "Start with your questions"
アブストとイントロを質問文から始める。複数あっても良い(三つくらいが限度?)。この質問文というのは、この研究で扱うResearch questionをもう少し柔らかくしたようなもの。読者はこの質問文を読むことでいきなりこの研究が何をしようとしているのかなんとなく分かる。例えばPageRankの論文を自分が書くとしたら "How to rank an enormous number of Web pages?" って感じで始めるかな。
Crown jewel
この論文のメインの実験結果を表す図を論文の1ページ目(もしくは2ページ目)の一番上に載せる。ここに載せた図は後の実験の節で再び登場してもOK。同じ図を複数回載せるのが良いか悪いかは議論を呼びそうだけど、これも全て論文をアピーリングにするため。ちなみに自分はこれにはあまり肯定的ではないので、これをすることによって論文がいい感じになりそうなときだけ従ってる。
(MUST) 3 words title in caption
図や表のキャプションの書き方にはいろいろ派閥があるみたいだけど、自分が教わってこれが一番いいなと思ったのはこのやり方。まず3単語以内でその図のタイトルを書く。これは強調するためにボールドとかにしたほうが良い。その後に図の説明をして、もう少し長く図から言えることを書く。
例) Three words title: Figure legends go here. Write the result of this figure here.
キャプションで説明したことは本文中でも説明する。同じことを書いてもOK。
(MUST) "State your main result in introduction"
この論文を読む読者(査読者)に伝えたい結果をイントロに書く。もし結果が複数ある場合はその中でもっとも重要なものを書く。明確に、目立たせて書く。読者にこれを伝えないと読者はなぜこの論文を読む必要があるかが分からない。
(MUST) "List your contributions in introduction"
イントロで自分の研究の貢献を 箇条書き にする。これをやらないとリジェクト。論文の中では自分の主張が最も重要なのでこれを明確に、目立つように記述しなくてはいけない。これは論文を構造化するためにもアピーリングにするためにも重要。
(MUST) Salesman's table
既存手法と自分の手法とを比較して自分の手法が優れているということを主張するための表のこと。関連研究の節で書く。深く関連する既存研究がいくつかあるときにはマストだと思う。こんな感じで優劣がひと目で分かる。
既存手法1 | 既存手法2 | 既存手法3 | 提案手法 | |
---|---|---|---|---|
速い | x | x | x | |
精度良い | x | x | ||
シンプル | x | x |
こういう表を書いている論文は結構あるので見たことはあるんじゃないかな。ただし、これはただ単に定性的な比較なので理解を助けるという意味でしか使えない。もちろんこの主張を裏付ける理論的もしくは実験的な比較はやらないとダメ。
"Don't cite any related work in your proposal"
自分の提案(手法)を書く節では関連研究を引用するなという話。これについては「ホントにそれでいいのか?」と思う部分があるけど言いたいことは分かる。自分の提案をしている時に既存研究の話が出てくるとどこまでが既存研究でどこからが自分の研究かわかりづらくなるし、そもそも新規性も薄れてしまいがちになる。自分の研究の位置づけはイントロと関連研究の節で済ませておくべきなので提案手法の節でそれをやってはいけないということ。
(MUST) "Number your observations"
定義とか定理とかに番号をつけて明示的に書くってのはみんなやってるけど実験結果から言えるObservationに対しても番号をつけましょうということ。
Observation 1: ---
みたいに書くということ。こうすれば読者はこの実験から言えることは何かが明確にわかるし、後の文章で参照することもできる。もっと言うとObservationにかぎらず重要な項目は全て番号をつけて強調して書くべき。
(MUST) "Repeat your contributions in conclusion"
イントロで挙げた貢献をconclusionでもう一度述べよということ。具体的には、貢献とそれをサポートする結果とを結びつけてリストアップする。こうすることで、
- 読者(査読者)の理解を助ける、
- イントロで挙げた貢献(主張)が本当にこの論文でサポートされたかがはっきりする。
多分2点目は最も重要で、これができていない論文はほぼ確実にリジェクトされる。(できる)研究者の間では共通見解として持たれていると思うんだけど、これができていない論文の多いことよ。自分の主張とやったこととを 厳密に 対応させることは最も重要。そのためにconclusionで貢献をリピートすることが重要。
*1:この辺についてはまたちゃんと書いてみたい。