読者です 読者をやめる 読者になる 読者になる

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

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

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次元ベクトルを1つずつ

要するにグラフ上の頂点の特徴を表す特徴ベクトルがほしいってこと。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の論文ではボロクソに書かれてた

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:この辺についてはまたちゃんと書いてみたい。

Personalized PageRankとLabel Propagationが等価という話

machine learning

無向グラフの時のPersonalized PageRank*1とLabel Propagation*2(LGCとも呼ばれる)が本質的に等価というお話。つまりLabel Propagationを計算したいときはPersonalized PageRankを計算すれば等価な結果が得られる。Personalized PageRankとLabel Propagationを知ってる人向けに書くのでわからない人はブラウザの戻るボタンを押してね。

まず、Label Propagationは以下のように書ける。

{ \displaystyle
f = \alpha Sf + (1-\alpha ) y
}

ただし、 S = D^{-1/2} W D^{-1/2}で、Wはデータ間の類似度行列、Dは次数の対角行列を示す。また、yはlabeled exampleのラベルを格納するベクトルで、positiveなら1、そうでなければ0を格納する(unlabeledも0)。αは0から1のパラメータ。この等式を満たすfが求められればLabel Propagationが計算できたことになる。

次にPersonalized PageRank

{ \displaystyle
x = \alpha Px + (1-\alpha ) b
}

ただし、 P = W D^{-1}。またbはpreference vectorを表す。

ここで、SはPを用いて以下のように書ける。

{ \displaystyle
S = D^{-1/2} P D^{1/2}
}

これを使うと、Label Propagationの式は以下のように書き換えられる。

{ \displaystyle
f = \alpha D^{-1/2} P D^{1/2}f + (1-\alpha ) y
}

両辺に D^{1/2}をかけて

{ \displaystyle
D^{1/2}f = \alpha  P D^{1/2}f + (1-\alpha ) D^{1/2}y
}

ここで x' = D^{1/2}f, b'=D^{1/2}yと置くと、

{ \displaystyle
x' = \alpha Px' + (1-\alpha ) b'
}

Personalized PageRankを同じ式になった! b'は要素の合計が1になるように正規化されてないけどPersonalized PageRankの計算の収束性には影響ない。これでPageRankを計算するプログラムを使ってLabel Propagationを計算できるようになった。まとめると、

手順

  1.  P = WD^{-1}
  2.  b = D^{1/2}y
  3.  x = PPR(P,b) # PPR(P,b)はPersonalized PageRank vector xを計算する
  4.  f = D^{-1/2}x

まとめ

ランダムウォーク系のアルゴリズムってそれぞれかなり密につながってるからこれも結構自明な結果だったりする*3。これが分かることによって何が嬉しいかというとPersonalized PageRankを高速に計算するアルゴリズムが出てきたらそれを使ってLabel Propagationも高速に計算できるようになることかな。

*1:Scaling personalized web search, WWW2003

*2:Learning with Local and Global Consistency, NIPS2003

*3:ソースは"Ranking on Data Manifolds", NIPS03

2015年まとめ

自分のために2015年をまとめておく

帰国した

去年の4月から1年間 CMU の Faloutsos 先生のグループに留学していたけどそれが終わった。研究面ではもちろんものすごい勉強になったしアメリカで生活したのも良い経験になった。おいしい日本食がないし英語もあんまり通じなかったし辛かったけどそれ以上に色々楽しかった。また(別のところにでも)行ってみたい。

ポスドクになった

4月から現所属のポスドクになった。この年で社会人一年目。ポスドクだけど学生の研究を見させてもらったりいい経験をしてる。ただいろんなミーティングとか会議とかが多くて自由に研究できる時間が去年より少ないのがちょっと残念。ポスドクでこれなのに先生方はホントにどうやって研究する時間を捻出しているのか本当に謎。

論文発表

今年は6件の論文が採択された。学生さんとやってた研究が形になったのは嬉しかった。もう少しレベルの高いところに通してもらえるように指導できるように精進したい。あとは同時期に CMU に留学していたブラジル人の同僚と一緒にやってた研究がKDDに通ったのもかなり嬉しかった。来年は 1st で通したい! 自分が 1st のフルペーパーは2件しかなかったので全然ダメ。もちろん本数だけではないけど生産性を高めていきたい。

  • WWW2015のポスター採択(1st)
  • ICWSM2015のフルペーパー採択(1st)
  • KDD2015のフルペーパー採択(留学中の同僚と共著; 2nd)
  • WISE2015のショートペーパー採択(学生さんの研究; 2nd)
  • CoopIS2015のフルペーパー採択(学生さんの研究; 2nd)
  • SDM2016のフルペーパー採択(1st)

国際会議参加

今年は5つの国際会議に参加した。5月はWWW, ICWSM, ICCSSの連続出張で、日本とヨーロッパの往復は楽しかったけど流石に疲れた。イタリアからイギリスに行くのに事務から「日本に帰ってきてからまた行ってください」とか言われるの、どうにかなりませんかね? あとイタリアに行く途中の飛行機の中でパスポートが敗れて入国拒否されそうになったりして大変だった。英語力が高まれば高まるほど国際会議に参加する意義が高まると思うので来年はもっと英語力を付けたい。英語力というかコミュニケーション能力かも。

  • AAAI2015(去年採択された論文の発表)
  • WWW2015(ポスター発表)
  • ICWSM2015(論文発表)
  • ICCSS2015(聴講)
  • CoopIS2015(学生さんの発表の付き添い)

論文を読んだ

当たり前だけど。今年はちゃんと読んで、読んだ後にMendeleyに登録した論文は81本だった。みんなどれくらい読んでるの? 後半から自分的まとめをすこしでも書くようにしてたけど後で見直すときにかなり便利だった。来年も続けよう。

小説を読んだ

n年ぶりに小説を読んだ。3冊も。すごい。特に『星を継ぐもの』はかなり面白かった。おすすめ。あとはオーウェルの『1984』。イギリスで「最も読んだふりをされる本」らしい。読破できてよかった。難しかったけど面白さは分かった。また読み返してみたい。『アンドロイドは電気羊の夢を見るか』は面白くなかった。なんでこれ評価高いんだろう。

一九八四年[新訳版] (ハヤカワepi文庫)

一九八四年[新訳版] (ハヤカワepi文庫)

アンドロイドは電気羊の夢を見るか? (ハヤカワ文庫 SF (229))

アンドロイドは電気羊の夢を見るか? (ハヤカワ文庫 SF (229))

星を継ぐもの (創元SF文庫)

星を継ぐもの (創元SF文庫)