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:この辺についてはまたちゃんと書いてみたい。
Personalized PageRankとLabel Propagationが等価という話
無向グラフの時のPersonalized PageRank*1とLabel Propagation*2(LGCとも呼ばれる)が本質的に等価というお話。つまりLabel Propagationを計算したいときはPersonalized PageRankを計算すれば等価な結果が得られる。Personalized PageRankとLabel Propagationを知ってる人向けに書くのでわからない人はブラウザの戻るボタンを押してね。
まず、Label Propagationは以下のように書ける。
ただし、で、Wはデータ間の類似度行列、Dは次数の対角行列を示す。また、yはlabeled exampleのラベルを格納するベクトルで、positiveなら1、そうでなければ0を格納する(unlabeledも0)。αは0から1のパラメータ。この等式を満たすfが求められればLabel Propagationが計算できたことになる。
次にPersonalized PageRank。
ただし、。またbはpreference vectorを表す。
ここで、SはPを用いて以下のように書ける。
これを使うと、Label Propagationの式は以下のように書き換えられる。
両辺にをかけて
ここでと置くと、
Personalized PageRankを同じ式になった! b'は要素の合計が1になるように正規化されてないけどPersonalized PageRankの計算の収束性には影響ない。これでPageRankを計算するプログラムを使ってLabel Propagationを計算できるようになった。まとめると、
手順
まとめ
ランダムウォーク系のアルゴリズムってそれぞれかなり密につながってるからこれも結構自明な結果だったりする*3。これが分かることによって何が嬉しいかというとPersonalized PageRankを高速に計算するアルゴリズムが出てきたらそれを使ってLabel Propagationも高速に計算できるようになることかな。
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』。イギリスで「最も読んだふりをされる本」らしい。読破できてよかった。難しかったけど面白さは分かった。また読み返してみたい。『アンドロイドは電気羊の夢を見るか』は面白くなかった。なんでこれ評価高いんだろう。
- 作者: ジョージ・オーウェル,高橋和久
- 出版社/メーカー: 早川書房
- 発売日: 2009/07/18
- メディア: 文庫
- 購入: 38人 クリック: 329回
- この商品を含むブログ (328件) を見る
アンドロイドは電気羊の夢を見るか? (ハヤカワ文庫 SF (229))
- 作者: フィリップ・K・ディック,カバーデザイン:土井宏明(ポジトロン),浅倉久志
- 出版社/メーカー: 早川書房
- 発売日: 1977/03/01
- メディア: 文庫
- 購入: 70人 クリック: 769回
- この商品を含むブログ (438件) を見る
- 作者: ジェイムズ・P・ホーガン,池央耿
- 出版社/メーカー: 東京創元社
- 発売日: 1980/05/23
- メディア: 文庫
- 購入: 207人 クリック: 2,160回
- この商品を含むブログ (476件) を見る
EMアルゴリズムでPLSAとSSNBを導出
Machine Learning Advent Calendar 2015 の10日目です。
EMアルゴリズム自体の説明は溢れてるけど実際にEMアルゴリズムを使って何かを解いてみたっていう例題はGMM(Gaussian Mixture Model)以外あまり見ない気がする。なので今日は二つの例題を使って具体的にEMアルゴリズムを使ってみる。
導出してみるのはかの有名なPLSA(Probabilistic Latent Semantic Analysis)とあまり有名じゃないSSNB(Semi-Supervised Naive Bayes)。二つとも例題としてはかなり優秀だと思う。
- 論文
- "Unsupervised learning by probabilistic Latent Semantic Analysis", JMLR, 2001
- "Text Classification from Labeled and Unlabeled Documents using EM", JMLR, 2000
続きはGitbookで
最近Gitbookってのを知ってそれを使ってみたくなったのでこの記事を書いてみたのでした。ブログから別のところに飛ばすと その時点でみんな読むのやめるけど どうしても読んでみたい人はどうぞ!
まとめ
Gitbook良いっぽい。