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

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

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ってのを知ってそれを使ってみたくなったのでこの記事を書いてみたのでした。ブログから別のところに飛ばすと その時点でみんな読むのやめるけど どうしても読んでみたい人はどうぞ!

yamaguchiyuto.gitbooks.io

まとめ

Gitbook良いっぽい。

Impact = Luck x Skill

ICCSS2015 (International Conference on Computational Social Science)に参加してきた。最近ちょっと盛り上がりを見せている(?)Computational Social Science に関する会議で、今年から始まったらしい。注目すべきなのはなんといっても招待講演者の豪華なラインナップ! ワッツとかバラバシとかこの分野で著名な研究者が13人も招待講演をしてた。一般発表もあったんだけど、多分ほとんどの参加者が招待講演を聞くのを目当てに参加してたんじゃないかな。

招待講演は全部YouTubeに上がってるのでここで見ることができる。画質も音質も綺麗で素晴らしい!

www.youtube.com

バラバシ「Impact = Luck x Skill」

で、いろんな人の話を聞いたんだけど、バラバシの招待講演がダントツで一番面白かった!スケールフリーの話とかするのかな―と思ってたけど全然違う話だった。

www.youtube.com

論文がどれだけ引用されるかはたった一つのパラメータで決まる

よく言われるように、インパクトファクターは引用数の良い指標とはいえない。インパクトファクターの高い論文誌で論文を発表しても、個々の論文の引用数にはかなりの開きがある。実際、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 だがFlickrNarrow folksonomy であることがわかった。

また、Twitterにおいてユーザがどの程度「相互に」タグ付けしているかについて分析した。また、どのような場合に相互にタグ付けするのかについて分析した。結果として、全体的に見ると相互のタグ付けは少ないが、「friends」のような友人関係に関するようなタグは相互に付与されることが多いことがわかった。

さらに、Twitterにおけるタグ付け関係とフォロー関係の比較を行った。結果として、タグ付け関係とフォロー関係はあまりオーバーラップしてないことが分かった。他にも、タグ付けとフォローがオーバーラップしているかどうかを見ることでタグを二種類に分類できることがわかった。一つは友人関係を表すfriendship tagsで、もうひとつは情報収集に用いられるsubscription tags。

他にもたくさん結果はあるけど詳しくは論文を読んでくれると嬉しいな!

WWW2015でポスター発表した

WWW2015でポスター発表してきた。WWWは以前聴講だけで参加したことがあって、今回はポスターだったので、次回はフルペーパーで発表したい。今回のポスターのタイトルは"Why Do You Follow Him? Multilinear Analysis on Twitter"。キャッチーなタイトルにしたいなーと思ってあれこれ考えた結果結局ありがちなタイトルになった笑

今回の発表はTwitterにおいてユーザが他のユーザをフォローする理由を分析しましょうというもの。以前から@ceekzさんと一緒にTwitterのデータ使った研究しましょうと言ってたのでようやく一つ発表できた。基本的には@ceekzさんにデータの収集と基本的な分析をしてもらって、僕が持ってたちょっとしたアイデアテンソル分解)を試してみた感じ。

この発表に関するリソースは以下のとおり。

データ:http://dx.doi.org/10.5281/zenodo.13966

コード:yamaguchiyuto/tagf · GitHub

ポスター:http://www.kde.cs.tsukuba.ac.jp/~yuto/resources/www2015/www15_poster.pdf

論文:http://www.www2015.it/documents/proceedings/companion/p137.pdf

概要

目的はユーザAがBをフォローした時の理由を明らかにすること。

これをリストデータを使って分析する。Twitterユーザは他のユーザのリストを作ることができるんだけど、この発表ではそれをタグ付けと捉える。つまり、例えばユーザAが「スポーツ」っていうリストを作ってユーザBをそのリストに加えた時、AはBを「スポーツ」というタグでタグ付けしたとみなす。

この「タグ付け関係」を表すグラフを考える。ノードはユーザで、エッジはタグ付け関係。それぞれのタグには対応するタグ(単語)がラベルとして付いている。またそれに加えてユーザの「フォロー関係」のグラフも用意する。同様にノードはユーザで、エッジはフォロー関係。エッジのラベルはない。

んで、グラフをテンソルにする。タグ付け関係のグラフは3階テンソル、フォロー関係のグラフは2階テンソル、つまり行列になる。タグのテンソルは(ユーザ、ユーザ、タグ)という三つ組を表し、フォロー行列は(ユーザ、ユーザ)のペアを表す。

f:id:yamaguchiyuto:20150530224856p:plain

ここからが(ちょっと)新しいんだけど、これらのテンソルと行列の軸を合わせて貼り合わせる。ここではユーザの二軸が対応してるので、その軸に合わせて貼り合わせる。イメージは図の通り。そしてこの張り合わさったテンソルと行列に対してテンソル分解をかけて潜在パターンを見つけ出す。

出てきた潜在パターンがあら不思議!ユーザがユーザをフォローしてる理由になってますね。すごーい。というお話でした。詳細は論文を読んでね!2ページだけだし。

貢献

  • ユーザ間のタグ付け(リスト)関係、フォロー関係のデータを収集、公開した(こちらは@ceekzさんの成果)
  • フォローの理由を分析するためにタグ付けおよびフォロー関係をテンソルで表して分解するという手法を提案した
  • 上記のデータをつかって実験をして、結果として出てきたいろんな潜在パターンを定性的に評価した

PAKDD2015で発表し(てもらっ)た

PAKDD2015に論文が通っていたので発表した。タイトルは"SocNL: Bayesian Label Propagation with Confidence"。自分で参加して発表したかったんだけどちょうど同じ日程でWWW2015が開催されていて、そっちでの発表もあったので、PAKDDには参加できなかった。残念。なので共著のFaloutsos教授の知り合いの方にかわりに発表してもらった。大変お世話になりました。

前回のAAAI2015に引き続き、今回の発表もグラフ上でのノード分類アルゴリズムの提案。やっぱりアルゴリズムを考えていろいろ解析するのは楽しい。今後もこういう研究をしていきたい。

概要

今回の発表はグラフ上でのノード分類アルゴリズムベイズ推定から導いて、推定結果に確信度を付与するというもの。ノード分類アルゴリズムはたくさんあるんだけど推定結果に確信度を付与できるものは(なぜか?)なかった。

提案したアルゴリズムは全てのラベルなしノードのラベルについて事前分布を仮定して、隣接ノードのラベルを手がかりとして事後分布を推定する。ただ、隣接ノードにもまたラベルなしノードが存在する(ことが多い)ので、事後分布を再帰的に計算する。

結果としてノードのラベルの事後分布を出力する。これを使えば推定結果の確信度を求めることができる。基本的には隣接ノードが多いほど事後分布はシャープな形状になる。なぜなら手がかりが多いから。逆に隣接ノードが一つとかだと手がかりが少なすぎるので分布は平たくなり、確信度は小さい。これは直感にも合っていると思う。

貢献

以下の長所を持つアルゴリズムを提案した。

  • Confidence: 推定結果に確信度を付与

  • Simple: アルゴリズムは簡単な線形システムを解くだけ

  • Fast: 必ず収束するし、計算量は入力サイズに線形

結果

アルゴリズムの理論的解析と実験的解析をした。

理論的解析では収束性とか、計算量とか、他のアルゴリズムとの等価性とかを示した。

実験的解析では三つのネットワークデータセットを使ってLabel Propagationと提案アルゴリズムの亜種と比較した。