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" というタイトルで，研究室同期の岩田との共著です．

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

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

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

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

例えば，実際によく用いられている 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 への初の論文採択は本当に待ち望んでいたものであり嬉しいです．アルゴリズムが面白いという点が査読者にも気に入ってもらえたのが良かったのだと思います．