Hatena::ブログ(Diary)

(iwi)の日記

2014-10-26

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

13:03 |  ALENEX'15 論文採択:指数時間 Branch-and-Reduce アルゴリズムの実性能を含むブックマーク  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" というタイトルで,研究室同期の岩田との共著です.


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

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


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

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

例えば,実際によく用いられている 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 先生達です.交通ネットワークにおける最短経路クエリヒューリスティクスを理論的に解析する枠組み,コンピュータビジョン系のインスタンスに特化した最大流アルゴリズムの理論的解析など,とても面白い研究をなさっているので,興味がある方はそちらも是非見てみて下さい.

2014-09-22

Microsoft Research Silicon Valley 最後の日を見て

14:44 |  Microsoft Research Silicon Valley 最後の日を見てを含むブックマーク  Microsoft Research Silicon Valley 最後の日を見てのブックマークコメント

f:id:iwiwi:20140823230954j:image:w550

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

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

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

続きを読む

TakagawaU16TakagawaU16 2014/09/23 09:59 MSR SVCは、"高名な"研究者を集め自由な空気で活動させてきたが、際だった成果も無く閉鎖論は以前からあったがBill Gatesの肝いりで開設されたことから、閉鎖の英断が出来なかっただけかと。長く所長を務めて来たGordon Bellも高齢のためか研究心は失せていたように思います。一方、Google X Labは実業に結びつく成果を出し続け、最近では別の研究コンセプトで長期的研究を行うGoogle Y Labまで新設するに至っています。何れも、即戦力となる研究者集団であり、インターンはいなかったと思います。企業研究所という点で見ると、NTTの研究所もMSR SCVと同じように実業に反映する成果を出せていませんから同じ運命を.....かも知れません。

2014-09-03

ICFP Programming Contest 2014 準優勝

02:56 | ICFP Programming Contest 2014 準優勝を含むブックマーク ICFP Programming Contest 2014 準優勝のブックマークコメント

f:id:iwiwi:20140903104903j:image:w400

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

(写真は現地の @esumii 先生にお願いして使わせて頂いています.)


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

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

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

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


追記

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

2014-06-21

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

21:35 |  DEIM フォーラム 2014 最優秀論文賞:2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化を含むブックマーク  DEIM フォーラム 2014 最優秀論文賞:2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化のブックマークコメント

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

f:id:iwiwi:20140621202847j:image:w450

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

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

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

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

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

2014-06-04

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

12:35 |  VLDB'14 論文採択:グラフの構造を活用した Personalized PageRank の高速計算を含むブックマーク  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 をより高速かつ省メモリに計算するための新たなアルゴリズムを提案しています.

f:id:iwiwi:20140604123339p:image:w450


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

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

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

f:id:iwiwi:20140604123858p:image:w300


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 法が優位に立ちます.

f:id:iwiwi:20140604123340p:image


論文採択について

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