SIGMOD 2014 に参加しました

楠本充
エンジニア

2014-07-03 12:23:01

初めまして,新入社員の楠本です.今年の4月からPFIで働いています.
先週 SIGMOD 2014 (Special Interest Group on Management of Data) という学会に参加してきたのでその参加記を記したいと思います.
SIGMOD はデータベース分野でトップに位置づけられる会議の1つです.SIGMOD では併設で PODS という理論系データベースの会議も同時開催されています.
今年はアメリカ合衆国ユタ州のスノーバードというスキーリゾート地で開催されました.この時期は夏だったのでスキーはなかったのですが自然が雄大な場所でした.(↓写真)

1

3

今回は修士時代にやっていた研究の論文が受理されたので,発表(と他の発表の聴講)をするために参加しました.

会議について

SIGMOD/PODS は全部で6日間開催されており,以下のようなスケジュールで行われていました.

  • 1日目:ワークショップ
  • 2日目:PODS
  • 3日目:SIGMOD / PODS
  • 4日目:SIGMOD
  • 5日目:SIGMOD
  • 6日目:ワークショップ

ワークショップは参加費が高かったので2日目から5日目にかけて参加しました.
会議ではいくつものセッションが常に並列されていました.チュートリアルやデモセッションも含めると常に6並列で行われていたようです.
そうなると全部の発表を見るのはとても無理なのですが,その埋め合わせとして(?)夜に全ての研究についてのポスターセッションが開かれていて,興味のあるものはオーラルで聞いて,聞き逃したりしたものはポスターで聞くということが可能になっていました.

リサーチペーパーには418本の提出があり,そのうち107本が採択されました (採択率25%).去年に比べると採択率が上がっています(去年は20%).
採択された論文の本数を国別で見ると今年は圧倒的に US が多く,その次に大きく差を開けて中国が続くという風になっていました.日本からは 3 本の論文が採択されていました.

1

来年の SIGMOD はメルボルン,再来年はサンフランシスコで開催される予定だそうです.

今回発表した論文について

今回採択された論文は NII の前原さんと河原林先生との共著です.
SimRank というリンクベースで2つのオブジェクトの類似度を計算する指標があるのですが,それを効率よく計算するアルゴリズムを提案しました.(論文リンク)
個人的な話をさせて頂きますと,僕は元々修士の頃に JST/ERATO の河原林巨大グラフプロジェクト という研究プロジェクトでリサーチアシスタントをやっていたのですが,今回の件はそこでやっていた研究の1つになります.
(余談ですが,今回の論文のテーマであるところの SimRank を違う問題設定で計算する研究を同時期にやっていて,そちらは先日 KDD(Knowledge Discovery and Data Mining) に採択されました.)

それぞれの発表について

SIGMOD はデータベースの会議なのでデータベースがメインに扱われているのですが,僕は(上に書いたように元々実ネットワークを対象にした研究プロジェクトにいたこともあって)実ネットワーク上のアルゴリズムやデータ構造に興味があるのでそういう系のセッションに張り付いて聞いていました.
聞いた発表でいくつか印象に残ったものを雑多に紹介したいと思います.

Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
(Youze Tang, Nanyang Technological University; Xiaokui Xiao, Nanyang Technological University; Yanchen Shi, Nanyang Technological University)

影響最大化(Influence Maximization )とは「ソーシャルネットワーク上でいかに口コミを色んな人に広めるか」という問題です.
厳密には,ネットワーク \(G=(V,E)\) が与えられるので,そのうちの頂点の部分集合 \(S \subseteq V\) を選んで,最初に \(S\) が口コミを広げた後,最終的に広まる口コミの影響を最大にするのが目的です.
口コミの広まり方には色々なものがありますが,Independent Cascade Model というモデルがよく使われている気がします.このモデルでは,口コミはターン制で広がり,ある人が口コミを拡散することになった後,別の人に広まるかどうかは確率的に独立に決まるという風になっています.確率はネットワークの枝ごとに設定されています.
(説明が雑ですいません.詳しくはググってください.)
扱うものは口コミでなくても影響を広めるものならなんでもよいです.

Independent Cascade Model では貪欲法を使って選ぶと最適解の近似解が得られることが劣モジュラ性により保証されるという話があるのですが,このとき計算速度に時間が掛かることが問題になっていました.
既存研究で,確率的アルゴリズムによって計算時間を大体線形時間にしたものがあって,理論的には高速なものの実用的には定数倍が大きくて使えないというものがありました.
この発表では,(おそらくその既存研究の手法を元に?)実用的にも高速で精度もよいアルゴリズムを提案していました.

ちなみにこの発表は「Social Networks I」というセッションに配置されていたのですが,他の発表も影響最大化に関するものだったので,実質的に影響最大化に関するセッションになっていました.個人的には,影響最大化は問題としては面白いけど実際に使う場合どうするんだろうなぁと疑問に思うところもあるのですが,人気分野になっているようです.

Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs
(Yubao Wu, Case Western Reserve University; Ruoming Jin, Kent State University; Xiang Zhang, Case Western Reserve University)

グラフ上の \(k\)-近傍探索問題を考えます.つまり,ネットワーク \(G=(V,E)\) があり,クエリとして頂点 \(u \in V\) が与えられるので,\(u\) に似た頂点のトップ \(k\) を出力する問題です.
ここでは2つの頂点が似ている指標としてランダムウォークベースの指標 (Hitting time のいくつかの変種や,CIKM’13で提案された Effective importance) を考えます.
この手の研究ではインデックスを最初に構築して,インデックスサイズとクエリ時間のトレードオフを考えるのが普通なのですが,この論文ではインデックスを作成せず,クエリされた頂点 \(u\) を中心に局所探索をしてトップ \(k\) を求めるという手法を取っています.
そのために,これらの類似度の指標には局所的な最大値が存在しないことを証明し,その上で,局所探索の過程で今見ている頂点の類似度の上下界を管理し,見る必要が無くなったところは見ないように枝刈りするということをしているようです.

Reachability Queries on Large Dynamic Graphs: A Total Order Approach
(Andy Diwen Zhu, Nanyang Technological University; Wenqing Lin, Nanyang Technological University; Sibo Wang, Nanyang Technological University; Xiaokui Xiao, Nanyang Technological University)

到達可能性クエリという問題に関する研究です.これは,有向無閉路ネットワーク \(G=(V,E)\) があり,クエリとして 2 つの頂点 \(u, v\) が与えられるので,\(u\) から \(v\) に向かう有向パスが存在するかどうかを答える問題です.インデックス構築時間・インデックスサイズ・クエリ時間の3つの要素の良いトレードオフを実現するアルゴリズムを考えることが課題です.
既存研究でも到達可能性クエリはよく研究されていて,巨大なグラフを効率よく扱える手法が幾つかあったのですが,静的なネットワークを対象にしたものがほとんどでした.この研究では動的グラフ,つまりリアルタイムでグラフの枝や頂点が削除されうる状況で到達可能性クエリを扱っていました.
で,その手法が結構面白いと思ったのですが,既存の静的グラフ用のいくつかの有力な手法に共通する要素を1つのフレームワークとして抽象化し,そのフレームワーク上で動的グラフ用のアルゴリズムを考案するということをしていました.そして,そのフレームワークに沿った,より効率の良い手法(正確にはラベリング方法?)を提案し,動的グラフで効率よく到達可能性クエリを捌くことができると主張していました.
既存の有力な手法には東大今井研の秋葉さんや矢野くんの手法が含まれています.
複数の既存手法を1つのフレームワークにまとめてしまうというのは結構驚きな気がします.

Independent Range Sampling
(Xiaocheng Hu, Chinese University of Hong Kong; Miao Qiao, Chinese University of Hong Kong; Yufei Tao, Chinese University of Hong Kong)

こちらは PODS の発表です.データ構造の話になります.
考える問題は次のようなものです:1次元上に点の集合 \(P\) があります.クエリとして区間 \([x,y]\) と \(t\ge1\) が与えられるので,点集合 \(P \cap [x, y]\) の中から \(t\) 個の点を一様な確率でランダムサンプリングしたい.
計算モデルとしては RAM モデルを仮定し,できるだけビット並列のようなことをして計算量を減らすのが目的です.
この研究では,いくつかの異なるモデル (点がstaticかdynamicか / 外部メモリ無しか有りか) について割とタイトな計算時間の上下界を得ていました.
基礎的な問題に対して計算時間の改良を与えられているのは面白いなぁと思いました.(ちょっと改善ポイントが細かい?というのはあるかもしれませんが.)
ちなみにこのセッションでは著者の Yufei Tao が他にもう1本論文を通していたようで,2回連続で発表していました.発表がとてもエネルギッシュで聞いていて楽しかったです.

謝辞

今回の SIGMOD 参加はJST/ERATO 河原林巨大グラフプロジェクトよりご支援を頂きました.関係者の方々に深く感謝致します.今後ともよろしくお願い致します.

Group Lassoでグループごと重みが0に潰れる理由

海野 裕也
リサーチャー

2014-05-23 18:15:03

海野です。
先日会社の論文読み会で、ICML2014のMaking the Most of Bag of Words: Sentence Regularization with Alternating Direction Method of Multipliersという論文を紹介しました。さて、この時話題になったのが正則化項をグループ化すると何でグループごと重みが0に潰れるのかという話でした。式を見ても直感的にはわからなかったのですが、得居さんがとてもわかり易い説明をしてくれました。この話、日本語で検索してもあまり出てこないのでちょっと紹介します。

続きを読む »

東大先端研での勉強会でライフサイエンスでのデータ分析に関して講演を行いました

大野 健太
エンジニア

2014-04-23 11:29:33

大野です。

先日4月9日、東京大学先端科学科学技術研究センターで開催された大規模データ分析に関する勉強会において、「大規模・多種多様なデータを扱うための検索・機械学習」というタイトルで、ライフサイエンスへの検索・機械学習の応用に関して講演を行いました。
主催の油谷先生を始め、関係者・参加者の皆様、この場を借りてお礼を申し上げたいと思います。

資料は弊社のslideshareにアップロードしております。

rcast_20140411 from Preferred Infrastructure Inc,

続きを読む »

言語処理学会年次大会で文法圧縮チュートリアル講義をしてきました

maruyama
リサーチャー

2014-03-24 15:59:41

まるまるです。春がきてますね。東京はだいぶ暖かくなってきました。

先週(3/17〜3/20)行われた言語処理学会第20回年次大会(NLP2014)において「文法圧縮入門:超高速テキスト処理のためのデータ圧縮」というタイトルでチュートリアル講義をさせて頂きました。

講義資料はSlideShareで公開しています。

文法圧縮入門:超高速テキスト処理のためのデータ圧縮(NLP2014チュートリアル) from marugorithm

続きを読む »

のび太とインターネット・オブ・シングス

hido
Chief Research Officer

2014-03-20 14:55:55

卒業式シーズンですね。比戸です。

今回はIoT (Internet of Things)やM2M(Machine-to-Machine)の話をします。

この2つの単語を日経記事やITニュースサイトで目にすることが増えました。将来PCやケータイ以外の様々なモノやセンサーデバイスがインターネットに繋がって情報を送り合って賢く連携することで、家が、オフィスが、街が、そして社会システム全体が便利で最適になる世の中が実現されると言われています。一方で、言葉やコンセプトは昔から存在しており、一時流行ったものの下火になっていたこともあって懐疑的な見方もあります。

「ドラえも~ん、ジャイアンが『そんなの俺も10年前に考えてた、のび太のくせに生意気だ!』っていじめてくるよ〜」

「スネオのやつも、『僕らが昔やってダメだったのにのび太にできるわけないだろ!』って言うんだ〜」

かわいそうなのび太くん、さて実際のところはどうなのでしょうか。

続きを読む »

顔認証技術: DeepFace と Pyramid CNN

beam2d
リサーチャー

2014-03-20 14:55:54

得居です。3月下旬とは思えない寒さに凍えています。

Facebook が CVPR2014 に投稿しアクセプトされていた顔認証に関する論文 [1] が MIT Technology Review にて紹介されたことで注目を集めています。DeepFace と名付けられた手法で、同社が集めた4030人の顔写真440万枚を用いた大規模学習によってほぼ人間並の人物識別性能を達成しているということで、なかなかキャッチーな話題です。一方、Face++ という顔認証・分類のプラットフォームを展開する Megvii社 がつい先日公開したプレプリント [2] でも DeepFace と同程度の性能を達成しています。今日はこの2つの論文を解説します。

deepface

続きを読む »

機械学習CROSSをオーガナイズしました

hido
Chief Research Officer

2014-02-03 17:08:14

もう豆まきしましたか?比戸です。

1月17日に、エンジニアサポートCROSSで機械学習のセッションをオーナーとして主催させて頂きました。今回はその報告と内容のまとめをさせて頂きます。

エンジニアサポートCROSSは今年で3回目を迎える、主にWeb系のエンジニアが集まる技術イベントで、今年も800人以上が集まったそうです。すごいですね。

並列開催されるパネルディスカッションを基本とするイベントで、有名なWeb関連サービスを持っているわけではないPFIの私がオーナーということで、持てる人脈をフル活用してパネリストをお願いしたところ、お声がけした方全員にご登壇いただけることになりました。

続きを読む »

第2回全脳アーキテクチャ勉強会でDeep Learningについて講演しました

beam2d
リサーチャー

2014-01-31 17:01:43

得居です。1月30日にリクルートGINZA8ビルで開催された第2回全脳アーキテクチャ勉強会にて、Deep Learningについて講演しました。

Deep Learning技術の今 from Seiya Tokui

続きを読む »

NIPS2013読み会を開催しました

hido
Chief Research Officer

2014-01-31 10:08:27

もう花粉飛んでるらしいですね。比戸です。

昨年開いたICML2013読み会に続き、NIPS2013の論文を紹介する会を開きました。平日夜にも関わらず60名以上の申し込み、50名以上の参加があり、改めて機械学習への興味の高さを裏付けるものとなりました。会場提供にご協力頂いた東大の武田朗子先生、中川裕志先生、および発表者の皆さんありがとうございました。

ここで特筆したいのが、@mooopanさんが選んだ”Playing Atari with Deep Reinforcement Learning“です。

話題のDeep Neural Networkと強化学習を組み合わせて、テレビゲームで人間にも勝ったという、この日唯一のワークショップ論文紹介だったのですが、なんと著者の所属するDeepMind TechnologiesがGoogleに500億円以上で買収されたというニュースが3日前飛び込んできました。買収交渉がいつからあったのかわかりませんが、多くのDeepMindとGoogle関係者がNIPS会場にいたわけで、Deep Learningそして機械学習を取り巻くホットな状況を感じられる一件でした。

以下に改めて発表論文と資料へのリンクを掲載させて頂きます。
続きを読む »

データ解析作業の救世主! 超絶☆実験ビルドシステムmafをOSS公開しました

beam2d
リサーチャー

2013-12-25 13:39:24

Photo by midiman. Used following a Creative Commons License. Taken from https://www.flickr.com/photos/midiman/90232391/
Photo by midiman under Creative Commons License (original)

メリークリスマフ!

得居です。今日はクリスマスですね。皆様昨日はいかがお過ごしでしたでしょうか?

クリスマスということで、今日は私たちから皆様に、特にデータ解析や論文執筆、手法の比較検証のために計算機上で様々な実験をしている方々に、プレゼントがあります!

Github – pfi/maf

今日、実験結果を「ビルドする」ためのツールmafを公開しました!

mafは、PFIでもよく使われているPythonベースのビルドツールwafを実験に使うための拡張です。大まかな使い方を学ぶために、ドキュメントとサンプルも公開しています。

maf — maf 0.1 documentation
サンプル

実験手順をビルドだと思って宣言的に書くこと自体はwaf等既存のビルドツールで可能です。mafはこの手順のうち、パラメータだけが違うという部分をまとめて書くための仕組みや、実験特有の手順(プロットなど)をサポートするようなライブラリを提供しています。

例えば5-foldの交差検証を行う例は以下のような雰囲気で書けます。なんとなく何をやる実験なのかわかるでしょうか? 正確な書き方はドキュメントやサンプルを参照してください。

...  # import等

def experiment(exp):
    # 5-foldの交差検証のためにデータセットを5通りに分割
    NUM_FOLD = 5
    exp(source='dataset',
        target='train test',
        # parametersを指定することで、パラメータ付けられたタスクや
        # パラメータ付けられた出力ファイルを作ることができる
        parameters=[{'fold': i} for i in range(NUM_FOLD)}],
        # 1行1データの形式のデータセットを5通りのtrain testに分割する
        # 出力されるtrain, testは'fold'パラメータでパラメータ付けられる
        rule=maflib.rules.segment_by_line(NUM_FOLD, 'fold'))

    # 分割した各foldに対して実験
    exp(source='train',
        target='model',
        parameters=maflib.util.product({  # 全組合せを実行
            'param1': [1, 2, 3, 4],
            'param2': ['a', 'b', 'c']
        }),  # 'fold'はもう指定しなくて良い (trainに紐付いている)
        rule='my-train ${SRC} ${TGT}')

    # ここにはもうfold, param1, param2などのパラメータを指定する必要はない
    # (modelとtestに紐付いているので)
    exp(source='model test',
        target='result',
        rule='my-eval ${SRC} ${TGT}')

    # 各foldにおける実験結果における'accuracy'値の最大値を取る
    exp(source='result',
        target='max_accuracy_result',
        aggregated_by('fold'),  # foldパラメータを「潰す」
        rule=maflib.rules.max('accuracy'))

    # 結果を可視化
    exp(source='max_accuracy_result',
        target='result.png',
        rule=my_plot_fun)

# 結果をプロットする方法はmatplotlibを使って書ける
@maflib.plot.plot_by
def my_plot_fun(figure, plotdata, parameter):
    ...

my-trainとmy-evalという学習・評価コマンドさえあれば、データサイエンティストや研究者の方なら誰でもforループを使って書いたことのある面倒くさい、そして意外とややこしい交差検証が実質3行で書けます。my-trainやmy-evalのコマンド部分はpython関数で書いて指定することもできます。

maf開発の背景は、実験の複雑さです。データを解析したりアルゴリズムの比較を行う際に、実験手順をスクリプト(shell, python, ruby…)でよく書くと思います。最初は単一のデータに単一のアルゴリズムを一回適用して結果を見るだけだったりするので、直接スクリプトを書くので十分なのですが、他のデータに適用したり、他のアルゴリズムや異なる設定(パラメータ)と比べたりし始めると、実験手順と実験結果の管理に割くコストが上がっていきます。機械学習の実験だとさらにデータを複数通りに分割する必要もあったりして、データの管理も必要になります。これを最初のスクリプトの延長で書き続けると書いた本人にしか読み解けない複雑な実験スクリプトができあがったり、実験に必要な手操作が本人にしかわからなくなったりします。メンテナンス性を上げるために実験のためのドキュメントを書き始めると、管理コストはさらに上がります。

様々な設定での実験手順と実験結果、およびそれらの集約と可視化、これらを宣言的に記述して途中で生成されるファイル群の管理をうまく隠蔽することができれば、実験とそのメンテナンスにかかるコストは大幅に下がると期待できます。mafはこれらを実現することを目指して開発されました。

mafは辛い実験生活をサポートしてくれる縁の下の力持ち的な存在です。ぜひ一度試してみてください。フィードバックやPull Reqなどもお待ちしております!

...34567...