深層強化学習ライブラリChainerRL

Yasuhiro Fujita

2017-02-16 19:10:47

Chainerを使った深層強化学習ライブラリChainerRLを公開しました. https://github.com/pfnet/chainerrl

PFNエンジニアの藤田です.社内でChainerを使って実装していた深層強化学習アルゴリズムを”ChainerRL”というライブラリとしてまとめて公開しました.RLはReinforcement Learning(強化学習)の略です.以下のような最近の深層強化学習アルゴリズムを共通のインタフェースで使えるよう実装してまとめています.

A3CでAtari 2600のゲームをプレイするexampleや,

DDPGでヒューマノイドロボットの制御を学習するexampleなどがあります.

以下では簡単にChainerRLの使い方を説明します.

まず,強化学習を使って問題を解くには,解きたい問題(”環境”と呼びます)をしっかり定義する必要があります.環境の定義の仕方は,OpenAIが公開している強化学習ベンチマーク環境のGym(https://github.com/openai/gym)のインタフェースに従っています.Gymの環境で動かすこともできますし,インタフェースを揃えればオリジナルな環境で動かすこともできます.基本的にはresetとstepという2つのメソッドが実装されていれば十分です.

env = YourEnv()
# reset は環境をリセットして現在の観測を返す
obs = env.reset()
action = 0
# step は環境にアクションを送り,4つの値(次の観測,報酬,エピソード終端かどうか,追加情報)を返す
obs, r, done, info = env.step(action)

深層強化学習では,状態から行動を決める方策(Policy)や,状態や行動の価値を予測する価値関数(V-function,Q-function)をニューラルネットで表現し,そのパラメータを学習します.ChainerRLでは,これらは単に__call__を実装したChainerのLinkとして表現されます.

class CustomDiscreteQFunction(chainer.Chain):
    def __init__(self):
        super().__init__(l1=L.Linear(100, 50)
                         l2=L.Linear(50, 4))
    def __call__(self, x, test=False):
        h = F.relu(self.l1(x))
        h = self.l2(h)
        return chainerrl.action_value.DiscreteActionValue(h)

class CustomGaussianPolicy(chainer.Chain):
    def __init__(self):
        super().__init__(l1=L.Linear(100, 50)
                         mean=L.Linear(50, 4),
                         var=L.Linear(50, 4))
    def __call__(self, x, test=False):
        h = F.relu(self.l1(x))
        mean = self.mean(h)
        var = self.var(h)
        return chainerrl.distribution.GaussianDistribution(mean, var)

このように作ったモデルやChainerのOptimizer,アルゴリズムごとに必要な引数を渡して”エージェント”を作ります.エージェントは環境とのインタラクションを通じてデータを集めながらモデルの学習を行います.

q_func = CustomDiscreteQFunction()
optimizer = chainer.Adam()
optimizer.setup(q_func)
agent = chainerrl.agents.DQN(q_func, optimizer, ...)  # 残りの引数は省略

エージェントを作ったら,自分で学習ループを書いて動かすか,

# Training
obs = env.reset()
r = 0
done = False
for _ in range(10000):
    while not done:
        action = agent.act_and_train(obs, r)
        obs, r, done, info = env.step(action)
    agent.stop_episode_and_train(obs, r, done)
    obs = env.reset()
    r = 0
    done = False
agent.save('final_agent')

あるいはあらかじめ用意されている学習用関数に渡せば学習が行なえます.

chainerrl.experiments.train_agent_with_evaluation(
    agent, env, steps=100000, eval_frequency=10000, eval_n_runs=10,
    outdir='results')

とりあえず動かしてみるためのクイックスタートガイドを用意しました. https://github.com/pfnet/chainerrl/blob/master/examples/quickstart/quickstart.ipynb

ChainerRLはまだベータ版ですが,強化学習に興味がある方はぜひ試してもらってフィードバックをいただけるとありがたいです.ライブラリとしての使いやすさや,新しいアルゴリズムの追加など,今後も改善を続けていこうと思います.

ChainerMN による分散深層学習の性能について

秋葉 拓哉
リサーチャー

2017-02-08 11:49:16

米サンフランシスコで開催された「Deep Learning Summit 2017」にて、PFN は Chainer のマルチノードでの分散学習対応への取り組みについて発表しました。本記事では、その発表について詳しく説明していきます。

分散深層学習の重要性と現状

GPU の性能は継続的に向上していますが、より大きなデータを活用してより精度の高いモデルを実現するために、深層学習で使われるモデルのパラメータ数や計算量も増大しています。そのため、現在でも、Chainer を含む一般的なフレームワークを用いた標準的な学習では 1 週間以上かかってしまうようなユースケースが少なくありません。より大規模なデータを扱ったり、試行錯誤のイテレーションを効率化するために、複数の GPU を連携させ学習を高速化させることは重要な課題です。そこで、我々は Chainer にマルチノードでの分散学習の機能を追加するパッケージ ChainerMN を開発しています。

ChainerMN の実装方針

今回の実装はデータ並列と呼ばれるアプローチを採用しており、その中でも同期型の実装を採用しています。これは、各ワーカーがモデルのコピーを持ち、1 イテレーションのミニバッチを分割し全ワーカーで協力して勾配を計算する、というアプローチです。

実装には MPI を利用しており、ノード外の通信は MPI を通じて行うことにより、InfiniBand のような高性能なネットワークの性能を活用できます。ノード内の GPU 間の通信には NVIDIA 公式の NCCL というライブラリを利用しています。

性能測定の結果

ImageNet の画像分類データセットを使って性能を測定しました。CNN のモデルとしては ResNet-50 を使いました。実験にはさくらインターネットの高火力コンピューティングを利用しています。詳しい実験の設定については記事末尾の付録をご覧ください。

以下の性能測定の結果は、完全に公平とは言えない可能性がある事をご留意下さい。まず、性能測定を行った環境は我々が開発を行った環境でもあるため、測定環境に特に適した実装になっている可能性があります。また、他のフレームワークに関しても、性能を出すためにある程度の試行錯誤をしたものの、我々は十分な経験を持ち合わせていないため、完全に性能を出し切れているとは限りません。第三者による検証を推奨するため、比較に利用したプログラムは他フレームワークのものも含めて公開予定です。

ChainerMN の性能

下図は、GPU 数を増やしたときに学習完了にかかる時間がどのように高速化されるかを表した図です。学習完了とは同じエポック数の学習を行うこととしています。4 GPU までが同じノード内で、8 GPU 以上ではノードを跨いでいます。比較的理想的な高速化を達成しており、今回の設定では 128 GPU で 100 倍程度の高速化となりました。

下図は、横軸に実時間、縦軸に validation accuracy を描いた学習曲線です。2 度精度がジャンプするところは、学習率を 0.1 倍しているタイミングであり、ImageNet 系の学習曲線で見られる一般的な現象です。この図から、今回の設定では 128 GPU を使った場合でもちゃんと精度が上がってきていることが確認できます。

他フレームワークとの比較

下図は、128 GPU を用いる同じ設定下で各フレームワークが学習完了に要する時間です。開発チームとしても実は意外な結果だったのですが、ChainerMN が最も高速という結果になりました。この理由については次の実験と併せて考察していきます。

下図は、GPU 数を変えた時の各フレームワークのスループットを描いています。計測のイテレーション数を少なめにしてしまったのでやや不安定ですが、傾向が見て取れます。まず、1GPU の時には ChainerMN よりも MXNet, CNTK のほうが高速です。これは、MXNet, CNTK が C++ で記述されているのに対し、Chainer が Python で記述されているからだと考えられます。次に、4GPU の時を見ると、MXNet が少し出遅れます。この理由の1つとしては、CNTK と ChainerMN が NVIDIA NCCL の提供する高速な GPU 間集団通信を活用しているのに対し、MXNet は自前でノード内の通信を行っている、ということが言えると思います。一方で、ノード間通信では、CNTK よりも MXNet, ChainerMN のほうが良いスケーラビリティを示しています。結果、128 GPU では、ノード内・ノード間の両方で高速な通信を実現した ChainerMN が最も高速です。

TensorFlow の結果の解釈には注意が必要です。TensorFlow は通常の利用では十分高速なフレームワークです。上図の実験で 1 GPU の時ですら低いパフォーマンスとなってしまっているのは、1 GPU でも分散実行時と同じ設定で実行しているためです。別プロセスとして起動しているパラメータサーバとの gRPC を用いた通信に大きなオーバーヘッドが存在し、1 GPU の時ですらこのような速度になってしまっています。TensorFlow の速度については、他所でのベンチマークでも同様の結果が報告されています [1, 2]。

分散深層学習の難しさと課題について

分散深層学習の難しさの 1 つとして、スループットの向上が常にそのまま学習効率の向上になるわけではない、という点が挙げられます。例えば、データ並列のアプローチでは、GPU 数を増やすほどバッチサイズが大きくなります。しかし、ある程度以上のバッチサイズでは、バッチサイズを大きくするとモデルの学習に悪い影響があり、得られるモデルの精度が段々下がっていきます。まず、同じエポック数の学習を行う場合、イテレーション数が減ってしまうため、モデルが成熟しないことがあります。加えて、勾配の分散が小さくなることにより、性質の悪い局所解(sharp minima と呼ばれます)に進みやすくなってしまい、結果として得られるモデルの汎化性能が悪くなってしまう、という現象も知られています。

こういったことを加味せずスループットのみを報告するベンチマーク結果には意味が有りません。バッチサイズを上げたり同期頻度を下げたりすることにより、いくらでもスループットのスケーラビリティは上げることができますが、そういった設定では有用なモデルを学習させることはできません。今回も、GPU のメモリにはかなり余裕がある状況ながら、各 GPU の担当バッチサイズを小さめに抑えることで、それなりの精度のモデルを得る事ができる設定にしています。

今後について

ChainerMN は、今月中にも社内での試用を開始し、そこでのフィードバックを反映した上で、数ヶ月以内に OSS で公開予定です。

続きを読む »

2016年Chainerアドベントカレンダーのまとめ

mitmul
リサーチャー

2017-01-17 11:32:37

2016年12月1日〜12月25日の間、Chainerアドベントカレンダー2016がQiita上で開催されました。記事をご投稿下さった皆様、どうもありがとうございました。皆様のおかげで無事全てのスロットが埋まりました。この記事では、どのような投稿が集まったかを簡単に分野別にまとめました。

botに持っていかれやすい記事の冒頭を避け、ここで突然自己紹介をはさみます。初めまして、齋藤俊太と申します。専門はComputer Visionで、昨年9月にPreferred Networksに入社しました。現在は応用を中心とした研究および、Chainerの開発・普及といったことに取り組んでいます。

For English speakers, there is a summarization of all articles by corochann: English summary of “Chainer Advent Calendar 2016″

自然言語処理系

音楽情報処理

画像関連

時系列信号処理

ランク学習

強化学習関連

Chainer周辺情報

Chainer内部解説/外部ツール等

Chainerを使っている研究プロジェクト

beam2d
リサーチャー

2016-12-02 16:18:49

Chainer Advent Calender 2日目です。このポストは Chainer Blog の記事 “Research projects using Chainer” とほぼ同じ内容の日本語版です)

最近、アルゴリズムの実装や実験に Chainer を使用している研究プロジェクトが出てきています。そこで、arXivで公開されている論文で Chainer を使っているものを検索し、リンク付きで表にまとめました: Research projects using Chainer

続きを読む »

2016年夏季インターンシップ開催報告

大野 健太
エンジニア

2016-10-28 18:41:49

PFI・PFNでは今年8, 9月に夏季インターンとして14名の方に来て頂き、機械学習・深層学習に関する様々なプロジェクトに取り組みました。このブログエントリでは、PFI・PFNのインターンシッププログラムの概要と、今年のインターンシップ、特に最終成果発表会についてを紹介します(写真は中間発表のポスター発表の様子です)。

2016%e3%82%a4%e3%83%b3%e3%82%bf%e3%83%bc%e3%83%b3%e4%b8%ad%e9%96%93%e7%99%ba%e8%a1%a8

PFI・PFNのインターンプログラムについて

PFI, PFNでは、2010年からインターンシップを実施しています(PFNは2015年から)。夏季のインターンシップは毎年行っており、また毎年ではありませんが、春季にもインターンを実施しています。PFI・PFNのインターンシップの特徴として、8, 9月の2ヶ月間と比較的長期であること、インターンで行うプロジェクトのテーマに精通している社員がメンターにつき一緒にプロジェクトを進めていくこと(大抵の場合1人の学生に対してメンター2人)、インターン中の成果は論文やOSSなどの形で可能な範囲で公開できることなどが挙げられます。

準備に関しても4月から募集要項の作成を進めており、春季インターンも含めると、1年のうち半分以上はインターンに関して何らかのプロジェクトが動いていることになります。PFI・PFNがここまでインターンシップに力を入れている理由として、インターンを行った後に社員としてPFNに来ている方がメンバーとして活躍していること、社員の側もインターンで来ていただく学生の方々から最新の研究について学んでいること、インターンでのプロジェクトが学生の方の研究・学業にも直接的・間接的に役に立っているという自負があることなどが挙げられます。

選考は書類審査・コーディング審査・面接審査で実施しております(選考方法に関しては今後変更になる可能性は十分あります)。コーディング試験に関しては別のブログエントリにて、過去の選考で出題した課題を公開しておりますのでご参照ください。選考では、本人の興味・研究分野・得意な技術などを考慮し、指導できるメンターとの間でマッチングを行います。幸いなことに、PFI・PFNでのインターンを希望していただける方は多く、また、皆さん優秀な方が多いので、毎年選考には頭を悩ませています(そして、大体毎年想定以上の人数を採用してインターン期間中はてんやわんやになります)。今年の募集要項は過去のNewsをご参照ください。

今年の夏季インターンについて

PFNが事業を拡大し、人数面・設備面でキャパシティが増えたことで、今年の夏季インターンでは14人と例年以上に多くの方に参加していただきました(倍率としては例年と同等程度でした)。今年4月にオフィスを本郷三丁目から大手町に移転した時には空席がたくさんあると思っていたのですが、実際にインターンを開始したら、危うく席が足りなくなりそうになり、若干ヒヤヒヤしました。

インターンシップの募集する際に、大まかなテーマは設定していますが、具体的にどのようなテーマで行うかは採用後にインターン生とメンターとの間で議論を行い、プロジェクトの方向性を決めていきます。今年のテーマは以下の通りです。どのプロジェクトでも関しても異常検知・強化学習・深層生成モデルなどに関する最先端のテーマに取り組んでいただきました。

  • 対話における商品の営業
  • Automatically Fusing Functions on CuPy
  • Generation of 3D-avatar animation from latent representations
  • Response Summarizer: An Automatic Summarization System of Call Center Conversation
  • Imitation Learning for Autonomous Driving in TORCS
  • 3D Volumetric Data Generation with Generative Adversarial Networks
  • DQN with Differentiable Memory Architectures
  • Anomaly Detection by ADGM / LVAE
  • Multi-modal Deep Generative Model for Anomaly Detection
  • CNN based robotic grasping for randomly placed objects by human demonstration
  • Bayesian Dark Knowledge and Matrix Factorization

今年の新しい試みとして、中間発表・最終発表を従来の口頭発表形式から、ポスター形式に変更しました。また、最終発表は一般公開し、外部の方も参加していただけるようにしました。発表をポスター形式にしたことで、インターンの学生の方たちがPFI, PFN社員やお客さんと双方向の議論が出来たのはよかったのではないかと思います。最終発表会は当初2時間を予定していましたが、終了時間が過ぎても活発に議論が続いていました。最終発表会当日のポスターはリンク先のconnpassページにまとめておりますので、是非ご覧になってください(発表資料は順次追加していきます)。

今後のインターンシップに関して

PFNでは(私がPFN所属なのでこのような主語を置きます)来年以降も夏季インターンシップを実施する予定で、募集要項は4月頃に掲載する予定です。また、PFNでは、春季インターンなどの通年インターンシップやアルバイトも随時実施しております(通年でのインターンシップはまだ仕組みが整備されていないため、受け入れられる数が限定されていますが、HPへの募集要項の掲載などの準備を進めています)。PFI・PFNでのインターンシップやアルバイトに興味のある方は是非ご一報いただければと思います。

CEATEC2016に出展してきました 〜ロボット編〜

Taizan Yonetsuji

2016-10-20 16:03:19

PFNは2016年10月4-6日に千葉幕張メッセで開催されたCEATEC2016で、スマートピッキングロボットおよびバラ積みロボットの展示を行ってきました。ロボットの他にもドローンやDIMoに関する展示も一緒に行いました。こちらに関しては関連記事をご参照ください。

以下では、もう少し詳細な解説をしたいと思います。

続きを読む »

CEATEC2016に出展してきました 〜ドローン編〜

PreferredNetworks

2016-10-17 15:58:17

PFNは2016年10月4-6日に千葉幕張メッセで開催されたCEATEC2016で、深層強化学習に基づくドローン(マルチコプター)の自律飛行に関する展示を行ってきました。ドローンの他にもロボットやDIMoに関する展示も一緒に行いました。こちらに関しては関連記事をご参照ください。

ドローンスペースでは実機による自律飛行を披露しただけではなく、説明用のデモ動画を作って上映しました。以下がその動画となります。

 

以下では、この動画よりも少し踏み込んだ内容について知りたい方向けに解説したいと思います。

続きを読む »

Amazon Picking Challenge 2016 ~ドイツ・ライプチヒにて~

神谷保徳

2016-09-02 16:25:17

神谷です。

7月上旬、ドイツ・ライプチヒで開催されたAmazon Picking Challenge(以降APC)に、PFNとして参加しました。これは、Amazonが主催しているロボット競技会で、Amazonの倉庫内に在庫された商品から、購入された商品を棚から集めるタスクの自動化を想定した競技です。今回で2回目で、前回からのタスクである、指定された商品を棚からロボットで取得しカゴに入れるPickタスクと、新しく加わった、カゴに入っている商品を棚に入れるStowタスクの、二つのタスクがあります。Pickタスクは、前回から商品の種類や難易度も上昇しています。

実際に我々が作り上げたシステムの技術内容に関しては、PFI&PFNセミナーで概要ではありますが既に発表しており[1][2]、また日経Roboticsに弊社システムの解説記事や弊社岡野原のコラム、APC全体の技術解説も載る予定ですので、今回はドイツ・ライプチヒにおいて、実際に我々がどんなことを行っていたか、旅行記風に紹介しようと思います。


6/28、お昼頃、会場入りしました。スーツケースをたくさん持っているのは、手持ちのロボット部材や、工具があるためです。ぎりぎりまで開発を行っていたため、手持ちとなった物が多くあります。
DSC01675

輸送されたロボットアーム達。実は、輸送に時間がかかるため、本番用ロボットアームは先に送り、直前までの開発には別のロボットを使用していました。それにまつわる様々なトラブル回避もありました。そうまでしたのは、それだけ短期間での開発だったためでもあります。
DSC01691

箱開け。きれいに、きっちりと梱包されています。ぎりぎりまでの輸送タイミング交渉、また税関など、この輸送自体に関してもかなりの問題解決/回避が行われました。
DSC01701
DSC01699

設置の様子。設置に関しても準備を凝らしていましたが、それでも電圧の違いによるトラブルが少しありました。ロジスティクスの方と協力し、短時間で完了しました。
DSC01707

本番前々日
設置後、調整と改良が続きました。
本番前の調整では、奇跡的に隣にあった、ホームセンターが大活躍しました。例えば、照明条件の違いから、ライトを購入したり。ロボット競技では、現地でのイレギュラーがつきものです。
DSC01840

本番前日
調整と改良を続けます。
DSC01847

また、Amazon.deの見学にも行きました。
DSC01775

試走のスケジュール表。試走では本気を出していない(動作の確認に徹している)チームもあり、まだまだ分かりません。
DSC01789

本番直前。ぎりぎりまで改良を行いました。
DSC01999

そして本番。オレンジのTシャツの人が、Amazonの委員の人です。ターゲットのアイテムと、棚内のアイテムの配置は数パターンあり、くじで選択する形です。委員の人がアイテムを慎重に配置していました。また、棚のずらしも、配置前に行われます。
DSC02006

本番中。ハラハラドキドキ。本番のロボットの動作の様子はYouTubeに上がっています[3]。
DSC02007

終わりました。幾つかミスはありましたが、満足のいく動作でした。
DSC02009

そして表彰式
DSC02015

表彰式後の一コマ
DSC02018

その夜のパーティ。みんな笑顔。
他のチームの方やAmazonの方ともいろいろなお話をしました。
DSC02026

次の日はデモです。試合までは調整であまり見られなかった他チームのシステムについて、拝見、質問をしました。我々が開発中に気付かなかったアイディアも幾つかありました。また、我々のシステムについてもいくつも質問を受けました。
DSC02036

お片付け。ロボット達はまたPFNに戻ってきます。おつかれさまです。
DSC02038



この数か月間、非常に大変でしたが、結果も伴い、とても良い形となりました。
DSC02011

—————————————————————————
[1]http://www.slideshare.net/pfi/amazon-picking-challenge
[2]https://www.youtube.com/watch?v=gqcO8ZX0jB8
[3]https://www.youtube.com/watch?v=w7NgejZMSsA

Chainer MeetUP #03 を開催しました

preferred

2016-07-15 20:36:54

最近得居さんに雑なあだ名を付けられて、凹んでる舛岡です。

7/2(土)にChainer Meetup #03をドワンゴ様セミナールームで行いました!

今回も、アカデミックや企業で活躍されている方々にお話しして頂きました。
ドワンゴ様には前回に引き続き今回も会場をお借りしました。またニコ生の放送もお手伝い頂きました。この場を借りてお礼を申し上げます。

Chainer Meetupでの資料

Chainer, CuPy入門 @unnonounoさん


Chainer Update v1.8.0 -> v1.10.0+ @beam2dさん


シンパーセプション研究におけるChainer活用事例 @n_hidekeyさん


Chainerを使って細胞を数えてみた @samacobaさん


ヤフー音声認識サービスでのディープラーニングとGPU利用事例 Yahoo! Japan 磯部さん


NVIDIA更新情報: Tesla P100 PCIe/cuDNN 5.1 NVIDIA 井﨑さん


俺のtensorが全然flowしないのでみんなchainer使おう @hidesukeさん


深層学習ライブラリの環境問題 @yutakashinoさん


Peephole connectionsを実装してChainerのcontributorになった話 @Kotaro_Setoyamaさん


Chainerを使って白黒アニメの彩色実験をしてみた @Eiji_Kbさん

Real-Time Style Transferについて @_mayfaさん


On the benchmark of Chainer @delta2323_


ドーナツスポンサー

今回も エヌビディア合同株式会社様に、ドーナツスポンサーになって頂きました!
毎回準備していただく エヌビディア合同株式会社様、@yukofujiさんには感謝しております!

IMG_0056 - コピー IMG_0057 - コピー

当日の様子

IMG_0048 - コピーIMG_0062 - コピーIMG_0053 - コピーIMG_0058 - コピーIMG_0065 - コピー IMG_0079 - コピー

IMG_0059 - コピー IMG_0071 - コピー 受付 IMG_0084 - コピー IMG_0086 - コピー

 

SIGMOD Programming Contest 2016 優勝

秋葉 拓哉
リサーチャー

2016-07-06 20:05:09

はじめまして。7/1 に入社しました新入社員の秋葉です。参加していた SIGMOD Programming Contest 2016 の結果が先週末にアナウンスされ、アドバイザーとして参加していたチームが優勝となりました。コンテストと我々のアプローチを簡単にご紹介したいと思います。

スクリーンショット 2016-07-02 0.43.16.jpg_small2

 

 

SIGMOD Programming Contest とは?

SIGMOD Programming Contest は学会 SIGMOD の併設プログラミングコンテストです。SIGMOD は VLDB と並ぶデータベース分野の最も有名な ACM 系の国際学会です。コンテストの題材も学会のテーマに沿っており、大規模データの処理の高速化を競うものが殆どです。特に、近年に論文が複数出ているようなホットなトピックが選ばれるようです。

ちなみに、参加者は学生に限定されています。チームの人数に制限はありません。チームは教員を一人アドバイザーにすることができます。前職では国立情報学研究所の特任助教でしたので、学生時代の出身研究室の後輩同輩である生田くん、林くん、矢野くん、岩田さんのチームにアドバイザーとして参加しました。特に、実装は生田くんと林くんが全て頑張ってくれました。

100 チーム以上が参加し、5 チームがファイナリストとして選出され、サンフランシスコで開催されていた SIGMOD 2016 にて結果がアナウンスされました。

スクリーンショット 2016-07-02 0.42.09.jpg_small2

 

 

今年のコンテストの問題は?

今年のコンテストの問題は、動的グラフ上のいわゆる最短経路クエリ(より正確には距離クエリ)です。入力として、まず最初に大規模なグラフが与えられます。少し前処理の時間ももらえます。次に、以下の 2 種類のクエリが与えられます。

* 距離の質問:2 頂点が指定されるので、その間の距離を答える
* グラフの変更:辺の追加や削除が指定される

細かいルールは省きましたが概ねこれだけです。とてもシンプルな問題です。グラフは小さいものから大きい物まであり、大きいものは数百万頂点・数千万辺の規模でした。

スクリーンショット 2016-07-02 0.41.29.jpg_small2

 

 

問題の難しさ

一部の方はご存知の通り、実は最短経路クエリに対する索引付け手法は僕のこれまでの専門のど真ん中でした。「ズルい!」という声すら聞こえてきそうです。それでは、果たして本当に簡単に優勝できたのでしょうか?

残念ながら、枝刈りラベリング法などの僕らが作ってきたこれまでの手法は、実は今回はほぼ全く使う事ができませんでした。その理由は、過酷な問題設定にあります。今回の問題設定では、グラフが動的であり、しかも更新の頻度が高すぎるため、ガッツリとした索引データ構造を作ってしまうと、構築・更新のコストのせいで逆に損をしてしまう状況でした。しかも、実はグラフがソーシャルグラフだったり交通グラフだったりと性質もバラバラでした。

 

他チームのアプローチ

先に他のチームのアプローチから紹介します。予想通り、過酷すぎる問題設定故に、索引データ構造を保持するようなアルゴリズム的に興味深い手法を採用しているチームは無かったようです。枝刈りやキャッシュヒット率向上のためのちょっとした処理をグラフに加えるぐらいで、基本的には両側幅優先探索をひたすら高速化していたようです。

 

我々のチームのアプローチ

我々も両側幅優先探索の効率化に尽力しました。しかし、我々のチームは他のチームと異なり、今回の問題設定に適した軽量の索引データ構造を組み込み利用しました。ここが一番面白いかと思うので、この点について重点的に紹介します。

利用した手法は k-All-Path Cover (k-APC) です。k-APC は VLDB’14 で発表されベストペーパー賞を受賞しています。これを使うと、オーバーレイグラフと呼ばれる、元のグラフを「荒くした」グラフのようなものを作ることができます。遠い頂点対の処理をする際、始点終点の近くは元のグラフを探索し、それ以外の大部分はオーバーレイグラフの上だけを探索する、というようにすることができ、処理する頂点数・枝数を減らすことができます。

実際には VLDB’14 で発表された k-APC をそのまま今回の問題設定に使うことはできませんでした。しかし、我々は実はちょうど k-APC の後続研究をしており、その技術をそのまま利用することができました。(ちなみにこの研究は論文投稿中です。)

ただし、k-APC は交通グラフのような平均距離の長いグラフでは効果があるものの、ソーシャルグラフのようなグラフでは効果がありませんでした。そこで、最初にグラフの性質を判定し、k-APC を利用するか否かの判断をするようにしました。

 

感想など

実は、SIGMOD Programming Contest では、2 年前にもグラフ解析の高速化がテーマとなっています。その時にも今回に近いメンバーで参戦したのですが、残念ながら勝つことができませんでした。今回はアルゴリズム的にも面白いアプローチで奇策が功を奏し勝つことができて本当に良かったです。頑張ってくれたメンバー達に心からお礼を言いたいです。

記事の写真は全て筑波大学の塩川先生よりご提供頂きました。ありがとうございます。

12345...