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良いっぽい。
Impact = Luck x Skill
ICCSS2015 (International Conference on Computational Social Science)に参加してきた。最近ちょっと盛り上がりを見せている(?)Computational Social Science に関する会議で、今年から始まったらしい。注目すべきなのはなんといっても招待講演者の豪華なラインナップ! ワッツとかバラバシとかこの分野で著名な研究者が13人も招待講演をしてた。一般発表もあったんだけど、多分ほとんどの参加者が招待講演を聞くのを目当てに参加してたんじゃないかな。
招待講演は全部YouTubeに上がってるのでここで見ることができる。画質も音質も綺麗で素晴らしい!
バラバシ「Impact = Luck x Skill」
で、いろんな人の話を聞いたんだけど、バラバシの招待講演がダントツで一番面白かった!スケールフリーの話とかするのかな―と思ってたけど全然違う話だった。
論文がどれだけ引用されるかはたった一つのパラメータで決まる
よく言われるように、インパクトファクターは引用数の良い指標とはいえない。インパクトファクターの高い論文誌で論文を発表しても、個々の論文の引用数にはかなりの開きがある。実際、Natureなどの良い論文誌で発表された論文でもその大半は 一度も 引用されない。
バラバシたちは全ての論文は全く同じルールにしたがって引用されていくことを発見した。全ての論文は発表されてから徐々に引用されやすくなり、ピークを迎えた後に引用のされやすさが減少していく。この引用の時系列のモデルのパラメータは以下の三つ
- Fitness: 論文の質を表すパラメータで、ピーク時にどれだけ多くの引用を集めるか。
- Immediacy: 発表されてすぐに引用をたくさん集めるのか、徐々に集めるのか。引用されるピークはいつかというパラメータ。
- Longevity: 引用のピークを過ぎた後にどれくらい早く引用されやすさが減少していくか。
人が見ると全く違うカーブに見える引用の時系列を持つ論文でもこのモデルで表現できる。実際、インパクトファクターも分野もぜんぜん違う論文誌でも綺麗に同じモデルで表現できた。
たしかに引用数のカーブはカオス的だけど、これは個々の論文の性質ではなくて、我々がどうその論文を認識するかという問題なので、collective behavior、つまりモデル化しやすいということらしい。
で、この時系列のモデルは三つのパラメータを持つけど、論文が生涯でどれだけの引用数を得るかは結局たったひとつのパラメータで表される。
それが fitness だった。
Impact = Luck x Skill
研究者のキャリアについての話で、ここが最高に面白かった。
ある研究者が発表した論文のインパクト(引用数)は、LuckとSkillによって完全に決まる。Luckは どの研究者に対しても同じ で、論文を発表するたびに一様分布からサンプルされて決まる。Skillは研究者ごとに異なるが、 ある研究者のSkillは生涯変化しない 。
直感的には、良いテーマに巡り会えるかどうかはランダムに決まるが、それを良い研究にするかどうかはその研究者のスキルで決まるということらしい。つまりは、その研究者が成功するかどうかはSkillパラメータで完全に決まっている。そして、Skillパラメータはその研究者が初めて論文を発表してから10年間のデータでとても高い精度で推定できるらしい。つまり 10年間ろくな成果も出せなかった人は今後も良い成果を出せない可能性が非常に高い! やばい、あと4年だ。
共著者のうちだれがノーベル賞を取るか?
ノーベル賞というのはある論文に対して与えられる。でもかならず第一著者に対して与えられるわけじゃない。じゃあ誰が受賞するのか。委員会が決め方を明に公開しているわけじゃないので、それを予測するアルゴリズムを作ったらしい。
結論から言えば その後も同じテーマで研究を続けた人に与えられる 。面白かったのは、分析の過程で著者順の情報は一切使ってないこと。使ってないというか、ノーベル賞を受賞するかどうかには全く寄与していないということ。第一著者だろうが第n著者だろうがどの程度貢献したかは外の人にはわからないしね。
ICWSM2015で発表した
ICWSM2015で発表してきた。タイトルは"Patterns in Interactive Tagging Networks"。2年前にポスター発表していて、今回はフルペーパーで発表できた。この会議は面白いから今後も参加したいなー。
今回の発表は初めての「分析しました論文」だった。WWW2015での発表でも使ったデータと同じもの(規模は違う)を使って、Twitterにおけるユーザのタグ付け関係(リストをタグとみなした)について基礎的な分析をした。
正直、当たり前とも思える結果を示しただけなんだけど、それを「しっかり示す」ことに意義があると認められたんだとおもう。メタレビュアもそう言っていた。ICWSMは特にこの辺を重視している印象で、他の論文もこういう感じのものが多かった気がする。Research questionを明確に示して、それにしっかりと答えるのが何よりも大事ということかな。
データ:http://dx.doi.org/10.5281/zenodo.16267
コード:https://github.com/yamaguchiyuto/icwsm15
概要
Twitterにおけるユーザ間のリスト関係をタグ付け関係とみなして、いろいろと基礎的な分析を行った。
Twitterユーザは他のユーザのリストを作ることができる。これはユーザのグループみたいなもので、例えば「スポーツ」という名前のリストを作って、スポーツ選手とかをそのリストに入れることができる。本研究では、リストの名前をリスト作成者からリストに入れられているユーザへの「タグ」とみなして、ユーザ間のタグ付け関係(ネットワーク)を作った。つまりノードはユーザで、エッジはユーザからユーザへのタグ。エッジにラベルがついてるグラフを作った。
このグラフの特徴を分析するために、FlickrとDeliciousにおけるタグ付けとの比較を行った。FlickrやDeliciousでは、ユーザが写真やウェブページへのタグ付けをすることができる。つまりユーザと写真やウェブページをノード、ユーザから写真やウェブページへのタグ付けをエッジとするグラフになる。これら三つのグラフの比較を行った。比較結果として例えばTwitterとDeliciousは Broad folksonomy だがFlickrは Narrow folksonomy であることがわかった。
また、Twitterにおいてユーザがどの程度「相互に」タグ付けしているかについて分析した。また、どのような場合に相互にタグ付けするのかについて分析した。結果として、全体的に見ると相互のタグ付けは少ないが、「friends」のような友人関係に関するようなタグは相互に付与されることが多いことがわかった。
さらに、Twitterにおけるタグ付け関係とフォロー関係の比較を行った。結果として、タグ付け関係とフォロー関係はあまりオーバーラップしてないことが分かった。他にも、タグ付けとフォローがオーバーラップしているかどうかを見ることでタグを二種類に分類できることがわかった。一つは友人関係を表すfriendship tagsで、もうひとつは情報収集に用いられるsubscription tags。
他にもたくさん結果はあるけど詳しくは論文を読んでくれると嬉しいな!