ALENEX'15 論文採択：指数時間 Branch-and-Reduce アルゴリズムの実性能

国際学会 ALENEX 2015 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカの San Diego です．

今回の論文は "Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover" というタイトルで，研究室同期の岩田との共著です．

背景１：アルゴリズム研究における理論と実性能の乖離

アルゴリズムが好きな人はよく御存知の通り，アルゴリズムの世界には理論（オーダーによる計算量解析）と実性能（実装し実データに適用した際の性能）に大きな乖離があります．これは，理論コミュニティでのアルゴリズムの評価基準が，理論的な計算量の改善を証明できるか否かのみにほぼなっており，本当に実性能が優れているかをほぼ全く考慮しないことによるものです．それ故，「理論的に計算量を改善するアプローチ」と「現実のデータにおける高速化を達成するアプローチ」に大きな違いがある場合も少なくなく，しばしば，理論的なアルゴリズム研究の価値が問われることとなってしまっています．

背景２：厳密指数時間アルゴリズムにおける理論と実性能の乖離

大きな乖離が存在する一つのアルゴリズム研究分野として，探索・最適化のアルゴリズムがあります．

例えば，実際によく用いられている CPLEX や Gurobi などの最適化ソフトウェアは，branch and cut と呼ばれるフレームワークに基づいており，良い cut を導入することによって探索空間を狭めてゆく工夫が中心となっています．一方，理論コミュニティでは branch and cut が扱われることは殆どありません．これは，理論的な計算量の改善を証明することが困難であるからです．

そこで，理論コミュニティでは，計算量の改善が証明可能な異なるアプローチが次々と提案されてきました．その 1 つが，branch and reduce と呼ばれるものです．問題を簡潔化する reduction rule を導入することで，受け取るインスタンスを reduction 済みのものと仮定します．すると，可能性が限定されるため，探索の分岐数を理論的に抑えることができます．例えば，頂点被覆問題では O*(1.212^n) 時間での動作が理論的に保証可能なアルゴリズムがこのアプローチにより提案されています．

（詳しくは岩田のこの資料の P.29 からをどうぞ：指数時間アルゴリズム入門）

本論文の内容：branch and reduce アルゴリズムは本当に理論的価値しか持たないのか？

本論文では「こういった branch and reduce のアルゴリズムは本当に理論的価値しか持たないのか？」という疑問に向き合い，そして典型的な予想を裏切るポジティブな結果を提示します．

我々は，頂点被覆問題を例に取り，今まで理論的な価値のみが重視されてきた数々の branch and reduce テクニックを徹底的に盛り込んだ実装を作成しました．そして，様々な現実のインスタンスを用い，branch and cut に基づく CPLEX や branch and bound に基づく MCS アルゴリズム等との比較を行いました．

結果は非常に興味深いもので，インスタンスの種別による得意不得意はあるものの，多くのインスタンスで branch and reduce によるアルゴリズムは（全く cut を用いないにも関わらず）branch and cut に匹敵する性能を達成しました．特に，ソーシャルネットワークやウェブグラフ等の大規模疎グラフにおいては，branch and reduce に基づくアルゴリズムが最も良い性能を示しました．数千万辺・一億辺規模のソーシャルネットワークの最小頂点被覆も厳密に求めることに成功しました．

また，今回の実装は branch and reduce に基づいているため，他の手法と違い，実用上高速なだけでなく理論的に計算量の証明ができることも面白い点です．O*(1.2210^n) 時間で動作することが証明できる他，最良優先探索と組み合わせた場合は O(m 4^k + m√n) 時間で動作することも証明できます（k は integrality gap）．

頂点被覆問題が高速に解けて嬉しいのか？

BIP2 と呼ばれるクラスに属する整数計画問題は全て「難しさ」（integrality gap）を保ったまま線形時間で頂点被覆問題に帰着できることが知られています．BIP2 に属する問題は Odd Cycle Transversal, Almost 2-SAT, Split Vertex Deletion, Edge Bipartization, Min SAT, Generalized Vertex Cover, Generalized 2-SAT, ... などなどいっぱい有ります．論文中では Odd Cycle Transversal のインスタンスを用いた実験も行っています．

関連研究・感想など

アルゴリズム研究における理論と実性能の乖離を問題視している研究者は少なくありませんが，その問題に実際に取り組んでいる研究者は残念ながらかなり少ないです．この問題に正面から取り組み成果を挙げているのが，Microsoft Research でお世話になっていた Andrew Goldberg 先生達です．交通ネットワークにおける最短経路クエリのヒューリスティクスを理論的に解析する枠組み，コンピュータビジョン系のインスタンスに特化した最大流アルゴリズムの理論的解析など，とても面白い研究をなさっているので，興味がある方はそちらも是非見てみて下さい．

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)

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