Hatena::ブログ(Diary)

(iwi)の日記

2015-01-05

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

18:28 |  1/30 発売!「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」を含むブックマーク  1/30 発売!「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」のブックマークコメント

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


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

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

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


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

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

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


f:id:iwiwi:20150105182230p:image:w450

(AOJ の画面)


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

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

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


f:id:iwiwi:20150105182618p:image:w450

(AOJ の基礎問題コース)


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

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

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


目次


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


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

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


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

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

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

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


Short Coding 〜職人達の技法

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

ショートコーディング 職人達の技法

ショートコーディング 職人達の技法

NN 2015/01/16 07:20 発売を楽しみにしています。この本はPDFで出るのでしょうか?他のマイナビの本はPDFに積極的なので出ることを期待しています。

2014-11-11

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

14:30 |  AAAI'15 論文採択:Top-k 最短経路クエリとネットワーク構造予測への応用を含むブックマーク  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 論文などでも扱ってきたように,最短経路・距離の計算は大規模なグラフでも非常に高速に行えるようになってきています.

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

f:id:iwiwi:20141111142907p:image

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


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

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

f:id:iwiwi:20141111142908p:image:w400

ここで "関連度" とダブルクオーテーションで囲っているのは,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 最短経路の長さを計算する提案手法は,簡単に利用して頂ける形のソフトウェアとして近日公開する予定です.グラフ上の頂点ペアを扱う様々な応用で利用して頂けるのではないかと期待しています.是非使ってみて下さい.

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" ですのでよろしくお願いします.