読者です 読者をやめる 読者になる 読者になる

PHP の壊れた mt_rand の品質を統計的に検証した

メルセンヌ・ツイスターと似て非なるアルゴリズムが実装されていたことが発覚して話題の PHP の mt_rand 関数の品質を統計的に検証しました.果たして,PHP の「壊れた」mt_rand は安心して使うことができるのでしょうか……?

ちなみに,結論から言うと,PHP の壊れた mt_rand は,(少なくともこのテストの範囲では)本家メルセンヌ・ツイスター遜色ない品質を持っているようです.ただし,最後に PHP の乱数の別の懸念点についても紹介します.

壊れた mt_rand とは

PHP の mt_rand は,ドキュメントによると,有名な乱数生成アルゴリズムメルセンヌ・ツイスター」を利用して高品質の乱数を生成する関数です.ところが,どうやら一部では知られていたこととして,PHP の mt_rand の実装にはバグがあり,本家メルセンヌ・ツイスターと挙動が一致していませんでした.このバグのある mt_rand の実装をこの記事では「壊れた mt_rand」と呼びます.

今回話題となっている一連の騒動は,

  1. kusano さんが壊れている mt_rand を修正する pull request を送り,一度マージされた.
  2. でも,後方互換性を崩す,とリバートされた.
  3. それどころか,壊れていることが維持されるようにテストがついた.

といった感じだと思います.

詳しくは以下のブログ記事にまとまってますので是非.

kusano-k.hatenablog.com

sucrose.hatenablog.com


なぜ擬似乱数の品質は重要なのか?

擬似乱数が「ちゃんと乱数に近い」ことは,統計的な実験やシミュレーション,確率的アルゴリズム,暗号,ゲーム等に欠かすことのできない要因です.

例えば最近だと,「グラブル問題」などソシャゲのガチャの確率の話をよく聞きます.意図的にガチャの確率を弄っている場合まだ良い(……良くはないですが少なくとも運営の意図通りではあるしすぐ直せる)として,擬似乱数の性質が要因でバグとして確率の偏りが起こってしまうと,とても悲惨だと思います.

BigCrush テストとは

ここ最近での乱数のテストといったら,BigCrush だと思います.

例えば,Google Chrome で採用され話題になった xorshift128+ の作者公式サイトでも,BigCrush でのテスト結果が(自慢気に)載ってます.

Here quality is measured using the powerful BigCrush suite of tests.
http://xorshift.di.unimi.it/

メルセンヌ・ツイスター作者の松本先生の最近の研究でも,品質で真っ先に言及されるテストが BigCrush です.

XORSHIFT-ADD は128ビットの内部状態空間と2128-1の周期を 持ち、 TestU01 の bigcrush test を通ります。
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/

BigCrush は,統計的なテストを大量に実行します.数学的に解析を行うことのできるシミュレーション等を擬似乱数を用いて実行し,「本当に乱数だったらこういう確率分布になるはず」という分布と実際の結果から検定を行います.

どういうメニューがあるかは,Diehard Test の Wikipedia 記事を見るとイメージが湧きやすいかも.BigCrush は 10 時間近く乱数を生成し続け 160 種類のテストを実行します.(Diehard より BigCrush のほうがテストが豊富)

結果

PHP の mt_rand のコードを取り出してきて,BigCrush に掛けるためのコードを書きました.

github.com

上述の xorshift128+ の公式サイトを参考にして,適当な 100 個のシードで BigCrush を実行し,落ちたテストの数を表にしました.

アルゴリズム 落ちたテスト(16000 個中)
壊れた mt_rand 230
修正済 mt_rand 236

なんと,ほとんど差が無いんですね.むしろ「壊れた」って呼ぶのが失礼かもしれないぐらいです.上述の xorshift128+ 公式に載ってるメルセンヌ・ツイスターの結果とそこそこ合致してると思うので,テストは正しくできているのではないかと思います.あと,C 言語の stdlib の rand も実行してみましたが,こちらは一万個近く落ちる結果になりました.線形合同法は,厳しい.

ちなみに,もっと意地悪をしてみようと思い,生成した乱数を bit reverse して BigCrush にかける,というテストも実行しましたが,結果はやはり殆ど変わりませんでした.(例えば,XSadd は普通に BigCrush すると通るものの,こうやって reverse すると落ちまくるらしい.)

表の数字をよく考えると分かる通り,実はメルセンヌ・ツイスターは正しく実装されていても BigCrush が結構落ちます.特に,必ず落ちるテストというのが 2 種類あって,それが 100 シード全部で落ちるのでそれだけで 200 個落ちてます.その点,最近の xorshift128+,xorshift1024* は,同様のテストを実行しても,落ちるテストは数十個みたいです.

BigCrush テストの出力も同リポジトリ内に置いてますので,詳しい結果が気になる方は直接ご覧ください.特に,seed = 12345678 で実行した結果は,上述の集計には入れてませんが,テストでよく使われている(例1, 例2)みたいなので置いてみました.最初に出力してる 16 個がそれら 2 つと一致しているので,壊れてる mt_rand・修正後の mt_rand 共に,公式と一致する実装が取り出せてると思います.

雑談:mt_rand が奇数しか生成しない(値域の指定によっては)

これはやや別の話題ですが,PHP の mt_rand が奇数しか生成しない」という現象がやや前に報告されていました.ここで話題になっているコードを実行すると,確かに今でも奇数しか出てきません.これ,ヤバくないですか……?(というか,もしそうなら,何故 BigCrush に通るの……?)

これは実は,mt_rand の引数で値域が与えられた場合に,乱数生成器の出力を値域内に縮めたり広げたりする操作が,めちゃくちゃ雑に実装されていることが原因です.この RAND_RANGE 関数ですね.例えば,2 倍の範囲に広げる際,単純に 2 を掛けるという極めて雑な実装になっているので,偶奇が固定されてしまうんですね.RAND_RANGE は mt_rand だけじゃなくて rand でも使われてるので,そっちでも同じことが起こります.今回の BigCrush テストは値域の拡大縮小部分は対象外ですので,この点は結果に表れませんでしたが,値域を指定して使うのは要注意だと思います.

ちなみに,ドキュメントをよく読むと,「注意」のセクションにこの現象に関するものと思われる記述があります.

警告
64 ビット版の PHP で max を 2^32 より大きくすると、mt_rand() の返り値の分布にバイアスがかかり、偶数よりになります。 max が mt_getrandmax() の返り値より大きくなると、 乱数生成器の出力をスケールアップする必要があるからです。
http://php.net/manual/ja/function.mt-rand.php

ただし,そこには値域を拡大する際の警告のみが書かれていますが,この実装では原理的には値域の縮小の際にも偏りが起こるはずなので,ヤバいことが起きてる事案がこれまでにあっても不思議ではないと思います.

その点,例えば C++ の std::uniform_int_distribution は,libc++ でも libstdc++ でも,値域を拡大させる際はもちろん,縮小させる際にも必要に応じて乱数を複数使うように書かれていました.安心.

ICFP Programming Contest 2015 優勝


先月開催された ICFP Programming Contest 2015 の結果が本日発表されました.我々チーム Unagi は二度目の優勝を達成です!嬉しい!

ICFP とは?

ICFP とは The ACM SIGPLAN International Conference on Functional Programming の略で,関数型プログラミングに関する有名な学会です.分野としてはプログラミング言語になります.

今年の ICFP 2015 は 8/31 よりバンクーバーで開催されています.

ICFP Programming Contest とは?

学会 ICFP の名前を冠し,20 年近い歴史を持つ有名なコンテストです.結果は毎年学会 ICFP にて発表されます.

ICFP Programming Contest は「なんでもあり」が特徴の,他とは一線を画す特徴的なプログラミングコンテストです.

  1. プログラミング言語制限なし
  2. 計算資源制限なし
  3. チーム人数制限なし
  4. 72 時間ぶっ続け勝負

ICFP Programming Contest 2015 について

今年の問題は,テトリスに類似したゲームをできるだけ上手にプレイする AI を作成するという問題でした.
ただし,18 個の「秘密のフレーズ」が設定されており,操作シーケンスに秘密のフレーズが入るたびにボーナス点が入ります.
うまく秘密のフレーズを埋め込みながら,できるだけ長いことテトリスをプレイする,というゲームになっていました.

全世界から約 300 チーム,合計約 800 人が参加したとのことです.

チーム Unagi について

chokudai, imos, iwiwi, sulume, tos, wata の 6 人で参加しました(アルファベット順).同じメンバーで 2013 に優勝,2014 に準優勝,一部共通するメンバーで 2011 に準優勝しています.

感想など

これだけのメンバーと一緒に参加出来て本当に幸せだなと思います.チームメンバーとは元々プログラミングコンテストでの繋がりなので,チーム内である程度共通したボキャブラリーや考え方を共有しているのがとても楽です.一方,単に「いわゆる」なプログラミングコンテストで強かったというだけでなく,みんな異なる強みを持っており,それでいて良好なチームワークが発揮できるのが素晴らしいなと毎年思います.

去年は惜しくも準優勝となってしまい連覇にならなかったので,次こそ連覇を実現するのが来年の目標でしょうか.頑張ります.

VLDB'16 論文採択:媒介中心性の動的更新

国際学会 VLDB 2016 に論文が採択されました.VLDB (International Conference on Very Large Data Bases) は SIGMOD と並ぶデータベース分野の最も有名な学会です.学会は来年 9 月にインドのニューデリーです.

今回の論文は "Fully Dynamic Betweenness Centrality Maintenance on Massive Networks" というタイトルで,東大今井研の林くん(主著者),NII の吉田さんとの共著です.我々は DEIM 2015 にて「動的なネットワークにおける媒介中心性の高速計算手法」というタイトルの発表をしており,優秀論文賞を頂くことができました.今回の論文はその論文の続きに相当しますが,いくつかのアイディアの追加により更に大幅に性能が向上しています.

媒介中心性とは?

中心性 (centrality) とは,グラフ上の頂点の重要さを測定する指標のことです.媒介中心性 (betweenness centrality) は最も人気のある中心性の 1 つで,ネットワーク解析を扱う書籍には必ず取り上げられており,実際の解析を行う方々からお話を伺っても,よく話に上がります.コミュニティ検出アルゴリズムの定番である Girvan-Newman アルゴリズムも媒介中心性に基いています.

媒介中心性は,全頂点対の最短経路が通る割合として定義されます(より詳しくは Wikipedia などをご覧下さい).感覚的には,物や情報が「どのぐらいその頂点を通過したいか」で重要度を表す,という気持ちだと思います.実際に実データに適用した際の結果は確かになかなか興味深くて,例えば人間関係のグラフでは,単に友人が多いといよりも,多数のコミュニティに所属するような人物が浮き上がってきます.

媒介中心性に対するアルゴリズム

媒介中心性の厳密な値の計算は,Brandes のアルゴリズムにより O(頂点数 * 枝数) 時間で行うことができ,計算量の意味では,これ以上高速なアルゴリズムは知られていません.(ちなみに,Brandes のアルゴリズムは巧妙な動的計画法に基づく面白いアルゴリズムなので是非調べてみて下さい.)

Brandes のアルゴリズムは,残念ながら,百万頂点を軽く超える現在の大規模なグラフに適用することは困難な計算量を持っています.そこで,大規模グラフでも媒介中心性を使えるようにするため,近年,推定値を高速に計算するアルゴリズムがとても良く研究されてきています.

本論文:動的ネットワークにおける媒介中心性の更新

本論文で扱うのは,動的なグラフにおいて,各頂点の媒介中心性の推定値を更新し続けるという問題です.それを実現する一番単純な方法は,グラフが更新されるたびに,既存の手法で 1 から計算し直す方法ですが,毎回とても時間がかかってしまいます.そこで,グラフに対して付加的なデータ構造を管理しておくことにより,瞬時に媒介中心性の推定値を更新する,というのが本論文で扱うアプローチです.

基本的な考え方としては,グラフの頂点対を幾つかサンプリングし,それらの間の最短経路の DAG による表現を管理します.我々はこれを Hypergraph Sketch と呼んでいます.頂点の追加・削除の際には,一定確率で,偏らせた確率分布を用いてサンプリングを再度行うことにより,サンプルを保ちます.辺の追加・削除の際には,各最短路 DAG を必要に応じて更新します.ただし,最短路 DAG の更新は,それだけを持っている状態では効率的に行うのは難しいです.そこで,両側幅優先探索の途中状態をデータ構造化した Two-Ball Index というデータ構造を別途保っておくことにより,更新が必要な箇所を高速に特定できるようにします.しかし,このデータ構造を用いても,到達不能な頂点対が一定数存在する場合には,とても大きな範囲を無駄に探索することになり性能が著しく低下してしまいます.そこで,大まかに到達可能性を判定できるデータ構造も新たに導入し,それらを組み合わせることにより無駄な探索を抑えています(我々はこれを Special-Purpose Reachability Index と呼んでいます).

我々の実験では,これらのパーツを組み合わせたデータ構造は数十億辺からなるソーシャルグラフやウェブグラフにおいても十分高速に自身のデータ構造と媒介中心性の推定値を更新できました(ただし,性能は要求する精度によります).

感想など

今回作ったデータ構造は,自分の最短経路への愛情をちょっと発揮できた気がして気に入ってます.上述の 3 つのデータ構造は,3 つとも最短路木や最短路 DAG 及びその一部分(+それぞれの付加情報)になってます.最短経路の塊みたいなデータ構造です.

AtCoder 株式会社に入社しました

5 月より AtCoder 株式会社に入社しました.主となる勤務先は国立情報学研究所のままで,兼任としての入社になります.

AtCoder とは?

AtCoderプログラミングコンテストの開催を主な業務とするスタートアップ企業です.設立からそろそろ 3 年で,私を入れてメンバーは現在 3 人になります.社長は書籍「最強最速アルゴリズマー養成講座」などで有名な @chokudai です.ICFP Programming Contest で優勝を果たした際のチームメイトでもあります.

オンラインのコンテスト AtCoder Regular Contest (ARC), AtCoder Beginner Contest (ABC) を土曜日にほぼ毎週開催しています.また,宣伝と採用を兼ねた企業のプログラミングコンテストを,システムのレンタル,問題の作成代行,集客,開催のコンサルティングなどの面でサポートしています(記事1記事2記事3).

また,最近ではエンジニアの採用におけるプログラミング能力の推定と足切りの支援にも取り組んでいます.

なんで AtCoder

プログラミングコンテストは,間違いなく自分の人生に最も大きな影響を与えたものです.プログラミングコンテストで育った者として,今後はコミュニティへの恩返し,即ちコミュニティの活発化や優秀な人材の発掘・育成などの活動を行っていく責務を負っていると考えています.私は,AtCoder との兼任を通じてこれを果たしていきたいと考えています.

私はこれまで,アルバイトやインターンといった立場で,Broadtail, Preferred Infrastructure といった先輩達のスタートアップ企業に関わり,その成長を見てきました.少数精鋭のスタートアップ企業が自ら道を切り拓き世の中にインパクトを与えることに強く魅力を感じています.

AtCoder はまだ小さいチームですが,既にコミュニティ内外に大きな影響をもたらしています.日本語でのプログラミングコンテストの頻繁な開催は,裾野を大きく広げました.また,プログラミングコンテストに興味を持ってくださる企業さんの数も増えており,就職・転職の機会や賞金額といったような状況は数年前と比べ物にならない状況にあります.

ということで,今後とも私と AtCoder をよろしくお願いします.プログラミングコンテストについてのご相談など,是非ご連絡下さい.

1/30 発売!「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」

書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」が近日中に発売される予定です.会津大の渡部先生が著者で,Short Coding 本の Ozy さんと私が協力としての参加です.どうかよろしくお願いします.

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造


本書はアルゴリズムとデータ構造の入門書です.整列,探索,木構造などをはじめとする基礎的なアルゴリズムとデータ構造を初学者向けに説明します.前提とするのは基礎的なプログラミング能力のみです.コード例では C++ を用いています.

これだけだと,よくある本のように思われるかもしれません.しかし,本書は非常にユニークな特徴として,オンラインジャッジシステムとの密な連携をしています.実装を行い,正しさのチェックを受けてから次に進むことで,基礎を着実に身に付けることのできる本になっています.

(Ozy さんのこちらの紹介記事も是非ご覧になって下さい.より簡潔に売りがまとまってます.)

オンラインジャッジシステムとは?

オンラインジャッジシステムとは,元々,プログラミングコンテストの過去問にオンラインで挑戦できるようにしたシステムです.プログラムを提出すると,自動でコンパイルと実行が行われ,テストケースに対する出力により正誤が判定されます.また,実行時間制限があり,正しいだけでなく,要求される効率で処理が行えるプログラムを作成する必要があります.

オンラインジャッジシステムは古くから UVA, POJ, SPOJ など世界中で多くのものが作られ運用されてきました.日本のものでは会津大の Aizu Online Judge (AOJ) が最も大きく有名なオンラインジャッジシステムの 1 つです.AOJ は以下のような特徴を持ち,日本人を中心として人気が高く,日々活発に用いられています.

  • 日本人が作成した問題が重点的に収録されている
  • API が公開されており,サードパーティ製のアプリケーション・サービスが数多く存在
  • コンテストの過去問のみならず,プログラミングやアルゴリズムの初学者向けの基礎問題コースを持つ



(AOJ の画面)

本書のオンラインジャッジシステムとの連携

さて,何を隠そう,本書の主著者は AOJ を作成され管理されている会津大学の渡部先生です.従って,言わずもがなですが,本書では AOJ と連携しています.しかも,AOJ 管理者の先生によって書かれた本ゆえに,非常に密な連携が実現されています.

本書は,前述した AOJ のアルゴリズム初学者向け基礎問題コースに沿っています.アルゴリズムの基礎的な説明と問題の紹介・解説を交互に繰り返して進んでいきます.できれば,AOJ 上で実際に問題を解きながら進めていってもらいたいと考えています.



(AOJ の基礎問題コース)

オンラインジャッジシステムを用いる意義

アルゴリズム入門書がオンラインジャッジシステムと連携する意義は非常に大きいと思います.実装をしてみることは,アルゴリズムをよりよく理解するための近道です.しかし,アルゴリズムやデータ構造の実装は,落とし穴だらけのことも多く,間違った実装で満足してしまう場合もしばしば見受けられます.一方,本書でアルゴリズムの学習を進めていけば,オンラインジャッジシステムとの連携により,正しく実装できたかをチェックしながら進むことができます.

ちなみに,タイトルでは「プログラミングコンテスト攻略のための」ということになっています.プログラミングコンテストでは,アルゴリズムを自在に応用できるよう十分理解すること,そしてアルゴリズムを正しく実装することが重要です.また,一部のアルゴリズムは,コンテスト本番で「ライブラリ」として用いられるように,自分で実装した後で蓄えておけるようなものとなっています.従って,この本はプログラミングコンテストを目指す初心者にお勧めだと思います.一方,個人的には,このブログでここまで紹介してきました通り,プログラミングコンテストには特に興味がないような方にも勧めできる本だと考えています.

目次

既存の本に対する位置づけ

プログラミングコンテストチャレンジブック

拙著「プログラミングコンテストチャレンジブック」はアルゴリズムとデータ構造の入門書ではありません.既存の本で説明されてこなかったプログラミングコンテストにおけるアルゴリズムの設計・活用に重点を置くため,入門書で解説されるような基礎知識の説明は省いていました.従って,アルゴリズムとデータ構造の基礎知識に自信がない方は,プログラミングコンテストチャレンジブックの前に本書を読んでいただけると良いと思います.

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

オンラインジャッジではじめるC/C++プログラミング入門

渡部先生の前著「オンラインジャッジではじめるC/C++プログラミング入門」では,オンラインジャッジを用いた同様のアプローチでプログラミング言語 C/C++ を学ぶことができます.本書はその続編とも言えますが,本書だけで独立して読んでいただけるようになっています.

オンラインジャッジではじめるC/C++プログラミング入門

オンラインジャッジではじめるC/C++プログラミング入門

Short Coding 〜職人達の技法

オンラインジャッジでは,解いた問題数などで努力が可視化されるため,つい競う心が生まれ学習が促進されるという一面があります.一方,本書のもう一人の協力者 Ozy さんの著書「ショートコーディング 職人達の技法」では,オンラインジャッジの変わった楽しみ方として,コードの長さをどれだけ短くできるかの競争を扱っています.

AAAI'15 論文採択:Top-k 最短経路クエリとネットワーク構造予測への応用

国際学会 AAAI 2015 に論文が採択されました.AAAI は人工知能分野の最も有名な会議の 1 つです.発表は来年の 1 月にアメリカのオースティンです.AAAI への論文採択は 2 年連続となります.

今回の論文は "Efficient Top-k Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling" というタイトルで,研究室後輩の林くん,京大の則さん,研究室同期の岩田,NII の吉田さんとの共著です.内容は,グラフにおける Top-k 最短経路を高速に計算するためのスケーラブルなインデクシング技法の提案,及びそのネットワーク構造予測への応用です.特に,応用面のインパクトを示す試みを論文内に入れることができたのが大変気に入っています.

背景:ネットワーク上の 2 点間の関連度推定に関する課題

グラフにおける 2 頂点間の関連度・類似度の強さを推定することは様々なタスクにおける基礎的な処理です.最も基礎的な関連度指標はグラフ上の距離(最短経路の長さ)です.私の SIGMOD 2013 論文などでも扱ってきたように,最短経路・距離の計算は大規模なグラフでも非常に高速に行えるようになってきています.

しかし,距離は関連度の指標としては構造をいまいち上手く捉えられません.例えば,下図のようなグラフを考えてみましょう.黒い頂点同士の距離は同じですが,直感的には関連度が同じ強さだとは思えません.

そこで,距離よりも構造を把握できる関連度指標として Random Walk with Restart (RWR)SimRank などの指標が提案され使われてきました.しかし,学習や評価のために大量のペアに対する関連度を評価しなければならない場合や,ネットワークを加味した検索サービスの応答のために数多くのペアに対する関連度を瞬時に評価しなければならない場合などを考えた場合,そういった指標に対するアルゴリズムはスケーラビリティ,クエリ応答速度,あるいは精度のいずれかに課題があります.

新たな "関連度" としての Top-k 最短経路

そこで我々は,新たな "関連度" として Top-k 最短経路の長さを用いることを提案します.Top-k 最短経路とは,2 点間のパスのうち短いものから k 本(k はパラメータ)のことです.下表は上図の各グラフに対応しています.Top-k 最短経路の長さが このようなグラフの関連度の違いを識別できることがわかります.

ここで "関連度" とダブルクオーテーションで囲っているのは,Top-k 最短経路の長さは他の指標と異なり 1 つの数ではなく k 個の数のベクトルになるからです.しかし,一部の応用では,これは問題にならず,それどころか有利であると考えています.例えば,機械学習の分類器などの特徴量として用いる場合,特徴ベクトルとして k 個の数を入れれば,その間の調整は問題ごとに分類器に任せることができます.

提案手法:Top-k 最短経路の高速なクエリ応答

上で挙げたような極めて高速な計算が求められる状況でも Top-k 最短経路を用いることができるようにするため,新たなアルゴリズムとデータ構造を提案しています.提案手法は常に正しい Top-k 最短経路を計算します.そして,実験により,千万辺クラスの大規模グラフから索引が構築でき,数十マイクロ秒で 2 点間の Top-k 最短経路が回答できることを示しています(k は数十という想定).

提案手法は SIGMOD 2013 で発表した索引付け手法の拡張になっています.ただし,同じパスを 2 度出してしまわないようにするための工夫やその証明は非自明です.また,安易な拡張を行うと前処理時間や索引サイズが k 倍になってしまうため,それを防ぐための高速化技法複数提案しています.

応用実験:Top-k 最短経路のリンク予測問題における活用

Top-k 最短経路は今までネットワーク上の関連度指標として使われてきませんでした.従って,直感で「実は有用なはずだ」と述べているだけでは説得力は薄いです.そこで,実際のタスクとしてリンク予測問題という有名な問題を取り上げ,Top-k 最短経路の有用性を検証しました.

具体的には,Top-k 最短経路と SVMサポートベクターマシン)を組み合わせたアプローチを他の基礎的なアプローチと比較しました.比較対象として用いたのは,共通近傍数,Jaccard 係数,Adamic-Adar 等の簡単な指標,及びそれらを SVM と組み合わせたものや,SVD (特異値分解), RWR などです.Top-k 最短経路を用いる手法が概ね良好な結果を出すことが確認できました.

感想など

昨年の SIGMOD より続いていた最短経路クエリのシリーズも一応これにて一段落の予定です.感慨深いです.

Top-k 最短経路の長さを計算する提案手法は,簡単に利用して頂ける形のソフトウェアとして近日公開する予定です.グラフ上の頂点ペアを扱う様々な応用で利用して頂けるのではないかと期待しています.是非使ってみて下さい.

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