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

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

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は以下のように書ける。

{ \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文庫)

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著者だろうがどの程度貢献したかは外の人にはわからないしね。