Microsoft Research Silicon Valley 最後の日を見て

8 月中旬より，インターンとしてマウンテンビューに位置する Microsoft Research Silicon Valley (MSR SVC) に滞在して研究をしていました．期間は 3 ヶ月の予定で，11 月中旬まで居る予定でした．しかし，Microsoft の経営判断により MSR SVC の閉鎖が突然決定され，所属チームの方々を含む殆どの研究者は解雇となり，僕の滞在も突如終了になりました．

このショッキングな事件は，英語のみならず日本語のニュースサイトにも取り上げられています．

この異変を偶然にも内側から見た者として，その実態や思ったことについて書いておきたいと思います．ただし，私はあくまでここに 1 ヶ月間滞在していただけの学生に過ぎないことに気をつけていただければと思います．特に，なるべく区別するようにしますが，研究所・会社の考えと私個人の考え・憶測は異なっている可能性があります．

続きを読む

ICFP Programming Contest 2014 準優勝

7 月末に開催された ICFP Programming Contest 2014 の結果がスウェーデンで開催中の学会 ICFP 2014 で発表されたようです．例によって我々は事前にこっそり知らされていましたが，結果は準優勝！

（写真は現地の @esumii 先生にお願いして使わせて頂いています．）


このブログでももう何度か紹介していますが，ICFP-PC は他のプログラミングコンテストよりも圧倒的に「なんでもあり」の世界的なコンテストです．1 つの大きめのタスクにチームで 72 時間取り組み成績を競います．チーム人数，プログラミング言語，計算資源などに一切制限は無く，問題も形式からして毎年大きく異なります．（類似するコンテストとして挙げられるコンテストが皆無で，毎年かなり内容が違うこともあり，人にどのようなコンテストかを説明するのは毎回苦労します．）

今年は，去年優勝を果たした際のチームと同一のメンバーで出場しました．今年もチームの持つ幅広い面での力が発揮でき良かったと思います．チームで良い連携ができると，やっぱり一人でやっているより格段に楽しいです．

「連覇に失敗した」という捉え方をするチームメイトも居ますが，僕は上出来だと思っています．今年の内容は対戦ゲームの AI 作成でした．対戦ゲームはどうしても対戦相手との相性が重要になってくる部分があり，「強い」「弱い」でのランキングというより「多くの AI を倒せる AI」が良い順位を取ることになります．そして勿論その辺まで予測するのは困難ですので，良い順位を取るためには運も必要になってきます．（更に，今年のようなタスクでは評価に用いられるステージの性質も大きく響きますが，今年も評価に使うステージはコンテスト中には公開されませんでした．）

とはいえ，もちろん優勝したかったことには間違いないです．来年がまた楽しみです．

追記

色んなプログラミング言語を使ったのですが，恐らくリポジトリからの統計で，C++ が我々指定の言語という扱いになったようです．というわけで，1 年間 C++ が "a fine tool for many applications" ですのでよろしくお願いします．

DEIM フォーラム 2014 最優秀論文賞：2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化

DEIM フォーラム 2014 での発表論文が最優秀論文に選ばれ，本日開催されたソーシャルコンピューティングシンポジウム (SoC 2014) にて行われた授賞式に参加しました．後輩の大坂君との共著論文も優秀論文賞を受賞しました．

このような極めて高い評価を頂けたことは身に余る光栄です．私だけでなく，著者グループ全体で見ても DEIM や関連イベントへの参加・投稿経験を持つ者は居ず，我々のような「新参者」であっても公平に高い評価をしてくださるコミュニティに感謝と敬意を表したいと思います．

元々，私の研究の興味は「アルゴリズムとデータ構造」であり，卒論の頃から，アルゴリズムの研究室（東大今井研）を選びずっと所属しています．しかし，アルゴリズムのコミュニティにて重視されるような漸近的な理論解析よりも，私は大規模データ・実性能・社会へのインパクトなどに興味があり，配属当初は（正確には研究室選びの頃から）価値観の違いに悩んでいました．

そんな時，ふとしたきっかけで見つけ感激したのが，SIGMOD'10 の大規模グラフ上の最短経路クエリに関する論文でした．研究の世界をよく知らなかった当時，データベースといえば本当にデータベース自体についてのみ研究をしているのではないかと思い込んでいましたし，かなり不思議にも思いましたが，この論文は自分の興味・価値観に，ばっちり，これ以上ないほど，合致していました．「こういう研究がしたい！」と思い，卒論ではこの論文に基づいた研究を行いました．

そうしてその後も，このブログでも度々報告している通り，データベース関連の国際学会に少しずつ挑戦し，いくつかの論文がお陰様で採択されてきました．ただ，所属する研究室や近隣研究室ではデータベースのコミュニティへの論文投稿の経験を持つ人は殆ど居なかったため，活動はかなりが手探りでした．実際，僕の今までの共著者は，殆どが理論系のアルゴリズム研究者です．そして，実は心の中では，「自分のような研究内容で，胸を張って参加できる研究コミュニティは存在するのだろうか」というような疑問をずっと持ち続けてきました．なにせ，研究内容はグラフアルゴリズムですが，理論解析での貢献は薄いので，アルゴリズムのコミュニティでは高い評価を受けません．一方，データベースの学会に論文を採択して貰ってはいても，グラフアルゴリズムのようなトピックはとても隅っこの方の存在なのではないか，というようになんとなく感じていました．

従って今回の受賞は，受賞だけでも大変嬉しいのですが，このような背景から「僕のようなトピックでもデータベースコミュニティの一員として認めていただけるんだ」と感じられて，とても喜んでいます．これからも，きっと近いスコープで研究を続けていくと思いますので，まだ未熟者ではありますが，どうかよろしくお願いします．

VLDB'14 論文採択：グラフの構造を活用した Personalized PageRank の高速計算

論文が国際学会 VLDB'14 に採択されました．VLDB (International Conference on Ver Large Data Bases) は SIGMOD と並ぶデータベースの最も有名な学会です．学会は 9 月に中国の杭州です．

今回の論文は "Computing Personalized PageRank Quickly by Exploiting Graph Structures" というタイトルで，NII の前原さん，同じ研究室の岩田, NII の河原林先生との共著です．

内容

この論文は大規模なソーシャルネットワークやウェブグラフにおいて Personalized PageRank を高速に計算する手法を提案する論文です．Personalized PageRank は有名な PageRank の一般化です．PageRank が担っていた重要度の計算の他，関連度としても使われ，幅広い応用を持ちます．

今回の提案手法は，Tree-decomposition を拡張した Core-tree-decomposition を用い，グラフの性質を活用して計算を効率化します．

Core-Tree-Decomposition による Core と Whisker の分離

グラフ理論における有名な概念である tree-decomposition (木分解) を拡張した core-tree-decomposition という道具を用いることにより，グラフを Core 部分と Whisker 部分に分離することができます．Whisker 部分は木に類似した構造を持ち，グラフ理論の言葉を用いて言えば treewidth (木幅) が小さいです．一方，Core 部分は密に絡みあっており，グラフ理論の言葉を用いて言えば expander graph に近いです．

Core-Tree-Decomposition の高速な計算

core-tree-decomposition を利用していくための問題点の 1 つとして，計算コストがありました．そこで本論文では，まず，データ構造の工夫により core-tree-decomposition をより高速かつ省メモリに計算するための新たなアルゴリズムを提案しています．

Whisker 部分の処理: LU 分解による Preconditioning

Personalized PageRank の計算は連立方程式の球解に他なりません．ただし，そのままでは LU 分解のような直接法はスケールせず，一般的には反復法が用いられます．

ただし，上記の通り，Whisker 部分は木幅が小さく，これは，この部分に関しては LU 分解が効率的に動作するということを意味します．従って，Whisker 部分に関しては LU 分解により直接的に解を求め，その解を用いて連立方程式を Core 部分のみの問題に帰着します．

Core 部分の処理: GMRES 法

一方，Core 部分は expander graph に近いため，LU 分解のような直接法の性能は絶望的です．しかし，逆に Core 部分は Core 部分で，expander graph に近いという性質を活用し計算を効率化することができます．

通常の Personalized PageRank の計算では基本的な反復法であるヤコビ法や Gauss–Seidel 法が用いられます．しかし，今回提案しているのは，Core 部分には GMRES 法 (generalized minimal residual method) を用いることです．expander graph から来る性質の良い連立方程式において GMRES が効率的に収束することは，理論的にも実験的にも言うことができます．

ここで面白いのは，Core と Whisker の分離を行わないでそのままの連立方程式に適用した時は，GMRES 法はヤコビ法等よりも低速であるという点です．これは，そのままの問題ではあまり性質が良くなく，GMRES の高い収束性能を発揮できず，反復回数で差をつけることができないため，オーバーヘッドの部分で負けてしまうからです．一方，今回は Core 部分を抽出したことにより，オーバーヘッドを加味してもなお GMRES 法が優位に立ちます．

論文採択について

今まで VLDB はとにかく負け続きだったので，第二著者とはいえ，VLDB への初の論文採択は本当に待ち望んでいたものであり嬉しいです．アルゴリズムが面白いという点が査読者にも気に入ってもらえたのが良かったのだと思います．

乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−

本日，PFI セミナーにて「乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−」というタイトルで話をさせてもらいました．スライドは以下になります．

Ustream の録画もあります．

内容としては，以下の操作を効率的に行うための集合に関するデータ構造 (Sketch) の最近の進歩を紹介しました．

  • 集合の類似度の推定 (Jaccard 係数)
  • 集合異なり数の推定 (distinct counting)

どちらも重要かつ基礎的な操作で，b-bit MinHash や HyperLogLog など，既に実用的な手法が提案されており，実際にも使われています．しかし，2014 年になって，Odd Sketch や HIP Estimator という，これらをさらに改善する手法が立て続けに発表されました．

今日の発表ではこれを踏まえ，まず MinHash の基礎を復習し，次に今まで最も有力な手法であった b-bit MinHash，HyperLogLog の説明をし，最後にこれらの新しい手法を紹介しました．新しい手法は両方とも，新しいアイディアに基づく本質的な改善ながら，手法自体はかなりシンプルなので，実装も困難ではないと思います．是非使ってみて下さい．

今日の発表は主に以下の 2 つの論文に基づいています．より詳しい情報は論文をご参照下さい．

  • Michael Mitzenmacher, Rasmus Pagh, and Ninh Pham. Efficient estimation for high similarities using odd sketches. In WWW 2014.
  • Edith Cohen. All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis. In PODS 2014.

Cache-Oblivious データ構造入門 @DSIRNLP#5

「データ構造と情報検索と言語処理勉強会」にお邪魔して，「Cache-Oblivious データ構造入門」という発表をさせてもらいました．

実はこういうインターネットから集う感じのいわゆる勉強会に参加するのは初めてでした．発表も初めてなので結構緊張していて大変だったのですが，参加者の皆さんがとても優しくて助かりました．懇親会 (新年会) もとても楽しかったです．主催の overlast さん，会場を提供してくださっていたスマートニュースさん，どうもありがとうございました．


発表の内容は以下のような感じです．

  1. DB の索引としての B 木の利点の復習
  2. Cache-Oblivious の考え方
  3. vEB レイアウト (Cache-Oblivious の例)
  4. 実際の事例紹介 (TokuDB)

ちなみに，実況ツイートをしてくださっていた方々の説明が大変良い要約になっています（僕の舌足らずの説明よりよっぽどわかりやすい，ありがとうございます！）．ハッシュタグつきのツイートを適当に引用させてもらいます．一方で，データ構造の説明部分は図を見てもらえば結構一発に近いと思うのでそちらを見てもらえればと思います．

WWW'14 に論文採択

論文が国際学会 WWW'14 (23rd International World Wide Web Conference) に採択されました！ WWW はその名の通りウェブに関するトップ学会で，比較的新しいものの最近ではかなりの人気を誇る学会だと思います．

WWW の最近の人気は，例えば Microsoft Academic Search の学会ランキングで伺うことができます．最近 5 年に限定すると，なんとコンピュータ科学の全分野合わせても 2 位*1，最近 10 年にしても 3 位ということで，かなり順位が高いです．その分もちろん競争も激しく，採択率は 84/650 = 12.9% だそうです． 所属する河原林グラフ ERATO からもかなりの本数が提出されたようですが，知る限り残ったのは僕の論文だけのようです．

論文タイトルは "Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling" というもので，またもや研究室同期の岩田と NII の吉田さんとの共著になっています．

内容について

論文タイトルからわかるとおり，これまた SIGMOD'13，CIKM'13，ALENEX'14 と出してきた最短路クエリの論文の続きの新編です．今回も対象は大規模なソーシャルネットワークやウェブグラフです．そして，論文タイトルの冒頭になっているとおり，今回は Dynamic と Historical というのが新しい点です．この論文の貢献は主に 2 つあります．

貢献 1: Dynamic Update

今までの最短路クエリではグラフは静的であることを仮定し，グラフの変更を反映するには前計算をしなおす必要がありました．しかし，今回提案する動的更新アルゴリズムを組み込むと，なんとグラフの変更を即座に反映することができるようになります． ちなみに 1 本の枝に対する処理は数ミリ秒で終わります．

ただし，対応しているグラフの変更は今の所残念ながら辺の追加のみです．しかし，現実のネットワークでは辺の追加の方が削除よりも遥かに多いため，実用的にはそれでもかなり価値があるという事を主張しています．今までは再構築をするまで反映されなかった変更が，追加だけとはいえ即座に追加されるのは有用であると思います．

貢献 2: Historical Queries

さらに，データ構造にもう少し情報を入れることにより，最新の状態での距離だけでなく，「昔，時間 t の頃の距離はいくつだったか？」や「距離が変化したのはいつか？」というような質問に答えることができるということを提案しています．

これを使うと，辺に時間の入った大規模なグラフデータにおいて，距離を使った指標がどのように時間経過と共に変化していくかを観察できるようになります．下図はその例です．

(Fig.3 は平均距離と有効直径の変化，Fig.4 は近接中心性の変化，Fig.5 は temporal hop plot です．）

論文採択について

今回の論文も，実は最初に VLDB に投稿して落とされていて，その次で WWW に投稿しました．

この論文に限らず，VLDB では，正直毎回かなり納得の行かない査読コメントと共に落とされています．かなり頭に来たので，今回は DB 分野はもういいかなということで思い切って WWW に投稿するという判断をしました．これは，どうやら正解だったようです．同等の競争率のはずですが，かなり高い評価と共に論文は採択されました．

とはいえもちろん，VLDB に出した原稿をただ WWW に再提出して採択されたわけではなく，かなり念入りに修正をしています．特に，WWW の査読でウケるように，「何ができるか」に重点を起き，上で示した例などを追加しました．また，VLDB で納得してもらえなかった点の議論の防御を強めました．

特に今回は，「更新で削除が対応していない」という点がかなりきつい防御ポイントで，VLDB で落とされたのもその点の影響も大きかったと思います． 「WWW に 5 年で 6 本」で有名な松尾先生も仰っている通り，論文を通すためには失点を少なくすることが重要であり，こういう大きな突っ込まれ得るポイントがあると，例え面白くても「論文を通す」という観点からは結構厳しいです．そのような部分を今回は議論で押し切ることができたというのは少し自信につながり嬉しいです．

*1:1 位は納得の CVPR ですね． その次という順位は結構すごいように思います．このランク付けがどれだけ意味のあるものかという議論の余地は当然ありますが，少なくともこの指標ではこの順位だということに一定の意味はあると思います．