Chainer MeetUP #03 を開催しました

Hideto Masuoka

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・ハイパーパラメータの決定)問題文