深層強化学習による自動駐車の実装

Shiba Shintaro

2017-03-22 19:15:13

初めまして! PFN でアルバイトをさせてもらっている芝慎太朗です。普段は東京大学大学院で行動神経科学の研究をしています。僕が去年取り組んでいた、「車が自ら駐車場に向かい停止する」自動駐車プロジェクトについて報告します。まずはこちらのアニメーションをご覧ください。(アニメーションがうまく再生されない場合は画像をクリックしてください)

We implemented self-driving car that parks itself using deep reinforcement learning. The English slide is available at SlideShare!

背景

深層強化学習は、2015年から非常に注目され始めた人工知能技術であり、深層学習と強化学習を組み合わせたものです。深層強化学習によって、それまでできなかったような複雑なタスクにおいてもコンピューターが人を上回り始めました。プロ棋士を破ったことで一躍話題になった Google DeepMind による囲碁の人工知能 AlphaGo もこの技術を使っています。最近では スマッシュブラザーズにおいても威力を発揮し 話題になりました。

深層強化学習は制御タスクとの相性がよく、実際に PFN でもぶつからない車の自動運転ドローンの制御などに成功してきました。

PFN が CES 2016 で展示した自動運転(参照)では、アルゴリズムとして深層強化学習ブームの火付け役となった Deep Q Network(以下DQN)を用いています [Mnih et al., 2015]。ニューラルネットワークへの入力は、LIDAR(wikipediaによる解説)を模した近接物への距離と角度センサー、直前の行動、現在の車のスピードとステアリング(ハンドルの曲がり具合)でした。

しかし自動運転技術を現実に応用することを考えると、一般に距離センサーよりもカメラの方が安価という特徴があります。一方で、距離の計算が必要になるためカメラ画像の方が制御は難しくなると考えられます。実際、つい最近も ブラウザ上で動作するような簡単な自動運転デモ が公開されたばかりですが、これも距離センサーを使用しており、使用しているニューラルネットは3層程度の簡易なものです。
距離センサー・カメラそれぞれに得意・不得意な状況や利点・欠点があるので一概にどちらを用いるべきとは言えませんが、いずれにせよ、距離センサーに頼らずカメラ画像のみを用いて車を制御するようなアルゴリズムの研究開発は非常に重要です。

本プロジェクト

このプロジェクトでは、距離センサーではなく、車に取り付けられたカメラによる主観的な画像の入力によってend-to-endのアルゴリズムで車を制御できないか、ということに挑戦しました。具体的なタスクとして選んだのは駐車です。すなわち、車を駐車スペースに移動して停止させます。

アルゴリズムとしては DQN の改善版である Double DQN を使用しました。Double DQN は行動価値の見積もり値である Q 値の過大評価を防ぎ、ニューラルネットの発散を防ぐことで学習を安定させるという特徴があります [Hasselt et al., 2015]。詳しくは解説スライド(この投稿の最後にリンクが貼ってあります)や元論文をご覧ください。

まずは環境の定義です。今回は実機や既存のシミュレータを使用せず、簡単な車の物理シミュレータを自分で実装しました。このシミュレータはアクセル、ブレーキ、ハンドルの曲がり具合を受け取り、牽引力、空気抵抗、転がり抵抗、遠心力、制動力、コーナリング力を計算し、車の位置、速度、加速度を更新します。車や駐車スペースの大きさと、車が探索できる地面の範囲なども定義しました。次の図は、シミュレーションされた環境を上から見た俯瞰画像です。黒い長方形が駐車スペース、赤と黄色の長方形が車(黄色が前)になります。


次にエージェントへの入出力を定義します。エージェントは環境の状態を入力として受け取り、アルゴリズムにしたがって適切な行動を選択します。現実世界に例えるなら車に乗っている人に相当するでしょう。行動はアクセル、ブレーキ、ハンドルを左右に曲げることの組み合わせで全部で9種類用意しました。状態としては、環境を車から見た主観画像と、現在の車のスピードとステアリング(ハンドルの曲がり具合)を使用しました。つまり、車の現在位置や駐車スペースまでの距離を直接知ることはできません。

主観画像は、車を中心に3方向または4方向に設置されたカメラ画像を用意し、車の周りをぐるりと見渡せるようにします。次の画像はカメラが4台の場合の主観画像です。画像の大きさはニューラルネットに入力する直前で 80 x 80 に縮小します。わかりやすいように中心に先ほどと同様の俯瞰画像を載せました。


エージェントは、画像の入力に合わせて適切な行動を選択し、車を駐車スペースに導いてそこで停車することが求められます。状態がカメラ台数分の画像と、画像でないパラメータ(現在の車のスピードとステアリング)からなるため、ニューラルネットの構造を工夫して以下のようにしました。この図はカメラが3台の場合に使用されたニューラルネットワークです。図中の Convolution とは、画像を処理するための畳み込みニューラルネットを示します。


最後に報酬を定義しておきます。「車が駐車スペースに向かい、その中で停止する」、すなわち「車ができるだけ長く駐車スペースの内側にいる」ことを学習するような報酬の与え方を考えます。いろいろな設定を試しましたが、最終的に

  • 車が駐車スペースの内側にいる場合、+1
  • 車が地面の外にいる場合、-1
  • その他の場合、0.01 – 0.01 * ゴールまでの距離

というふうに設定してみました。
その他の細かい設定や、他に試した報酬の設計などは末尾のスライドをご覧ください。

結果

GeForce GTX TITAN X 上で約一週間ほど学習を回し続けた結果、冒頭で示したように、車が自動で駐車スペースに向かい停止するように学習できました。次のアニメーションは冒頭と同じもので、左が車の軌跡、右が実際にニューラルネットワークに入力された画像です。

しかしながらやはりタスクの難しさもあって、このまま学習を続けていくと車が地面をぐるぐる回り続けたり、パラメタによっては学習途中でニューラルネットの出力が発散してしまったりという場合もありました。こちらも詳細はスライドを見ていただければと思います。


考察

深層強化学習を用いて、主観画像の入力から自動駐車を学習できました。画像を入力して車を制御するのは、距離や角度のセンサーよりも一段階難しいタスクです。実は、このプロジェクトも距離などを入力にして学習させるところから始めました。距離を直接入力した場合には安定してすぐに学習できたものの、主観画像では Q 値の発散や、うねうねと動き続ける車が誕生したりとなかなか安定しませんでした。

原因として考えられることの1つに、畳み込み層で車や駐車スペースの場所がうまく検出しきれていない可能性があります。先にCNNから位置を回帰するような事前学習をおこなってその重みを初期値として使うことや、一度 CNN 部分の出力を可視化してみることも有用でしょう。

また学習を安定させるために、アルゴリズムの変更も効果的かもしれません。例えば A3C [Mnih et al., 2016] や TRPO [Schulman et al., 2016] を使ってみたり、モンテカルロ法と組み合わせた学習などは試す価値があると考えられます。

実際にはいきなり始めから主観画像を入力したわけではなく、上で少し述べたように、簡単なタスクから徐々に難しくしていました。また、報酬の設計を変更しつつ、駐車スペースの位置や車の初期設定を変えながらカリキュラム学習をしたりと細かい実験を試しています。これらの詳細が知りたい方は上記のスライドを見ていただければと思います。

まとめ

本プロジェクトの結果はまだ様々な状況で完全に対応できるものではありませんが、深層強化学習によってカメラ画像のみで自動駐車が実装できる可能性を示したものだと言えます。今後の方向性としては、学習アルゴリズムを変更して学習を安定させたいです。シミュレーションだけではなく、実機でも実現できれば非常に面白いと思います。

僕は現在も他のプロジェクトに取り組みながらアルバイトを続けています。初めからプログラミングや強化学習ができたわけではなく、自分で勉強しつつ、わからないところをメンターに教えていただきながら、大変恵まれた環境で進めることができたプロジェクトでした。学生の皆さんも興味があればアルバイトやインターンに積極的に飛び込んでいってみてはいかがでしょうか。

深層強化学習ライブラリ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年夏季インターンシップ開催報告

大野 健太
エンジニア

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に関する展示も一緒に行いました。こちらに関しては関連記事をご参照ください。

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

 

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

続きを読む »

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

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

夏季インターンのコーディング課題を公開します

大野 健太
エンジニア

2016-07-01 09:14:57

PFNの大野です。暑くなってきましたね。

PFI/PFNでは毎年8, 9月にインターンシップを実施しています。2ヶ月間と日本で行われるインターンシップの中では比較的長期間のプログラムですが、毎年多くの方にご参加いただいています。我々自身、インターンで来ていただく方から多くの事を勉強することができ、最も力を入れているイベントの1つです。今回は本社を大手町に移転してから初めてのインターンシップです。今年は例年以上の応募をいただき、過去最大規模でのインターンシップとなりそうです。

さて、インターンシップの選考では、応募者の方々にコーディング課題を解いていただいています。このコーディング課題は情報科学の基礎知識・プログラミング能力・問題解決能力を測ることを目的としており、毎年担当者が趣向を凝らした問題を作成しています。例年、どのような問題がコーディング課題として出題されるのか問い合わせをいただいておりましたが、公平性の観点からお答えできることが限られておりました。

そこで今回、過去のインターンの選考で出題したコーディング課題を公開することにいたしました。PFI/PFNのインターンに興味のある方はぜひ参考にしていただければと思います。改めて見ますと、我々の会社が得意としているアルゴリズムとデータ構造・文字列処理・画像処理・機械学習などのテーマでの出題が多かったようです。これらの分野を勉強・研究する方にとっても良い練習問題になるのではないかと思います。

  • 2011年(テーマ:文字列処理・回文)問題文
  • 2012年(テーマ:文字列処理・一般化しりとり)問題文
  • 2013年(テーマ:グラフ・探索アルゴリズム)問題文
  • 2014年(テーマ:画像処理・テンプレートマッチング)問題文
  • 2015年(テーマ:機械学習・前処理・教師あり学習)問題文
  • 2016年(テーマ:深層学習・AutoEncoder・ハイパーパラメータの決定)問題文

PFI/PFNのパーティーでプログラミングビンゴ大会を開催しました

海野 裕也
リサーチャー

2016-06-17 13:37:03

海野です。先週の金曜日に、PFIの設立10周年およびPFI/PFNのオフィス移転を記念してパーティーを行いました。主に、株主様や取引先様、また社員のご家族を呼んだパーティーで、ホテルのパーティー会場を借りて行いました。 この中でプログラミングコンテストビンゴ大会という、おそらく日本で(世界で?)類を見ない余興を実施しました。 今日は当日の様子と、開催の経緯をお伝えしようと思います。


IMG_8252

続きを読む »

1234