システム系論文輪読会を開きました

kashihara
エンジニア

2014-08-07 11:55:18

柏原です。PFIでは夏季インターンシップがついに始まりました。

インターンとは関係ないのですが、昨日の2014年8月6日(水)、PFIオフィスにてシステム系論文輪読会を開きました。
趣旨としては参加者が好みのカンファレンスなどからシステム系の論文を読んできて発表するものです。
システム系といっても分野は絞りきれず幅広いのですが、普段PFI社内では話題にあがらないであろうテーマを期待して、参加者を募って開催しました。
普段の日常生活では扱わない分野のシステムについて見識を広めることができたら幸いです。

今回は5名の方に参加、発表していただきました。私からは非中央集権型のストリーム処理系について話をしました。参加者の方からは発表順に、Infinibandを用いた高速なKVSの実装、PaaS向けx86コードのsandbox手法、Facebookにおける画像キャッシュのアーキテクチャ、SDNにおけるネットワーク構成変更の最適化に関する論文について紹介して頂きました。
以下、発表された論文へのリンクと発表資料(アップされたのもののみ)です。

@suma90h ELF: Efficient Lightweight Fast Stream Procesing at Scale(USENIX ATC’14)
ELF 輪読/発表メモ

@syoyo HERD(Using RDMA Efficiently for Key-Value Services)

Herd from Syoyo Fujita

@ntddk MiniBox: A Two-Way Sandbox for x86 Native Code(USENIX ATC’14)

@wbcchsyn Bitcoin: A Peer-to-Peer Electronic Cash System

@syu_cream An Analysis of Facebook Photo Caching(SOSP’13)

@eagle_raptor Dynamic scheduling of network updates(SIGCOMM’14)

システム系論文輪講会20140806 from Hiroya Kaneko

実験ビルドシステムmafのv0.2をリリースしました

beam2d
リサーチャー

2014-08-04 14:12:31

こんにちは、得居です。先週末からインターンシップの3名を迎え、これからの二ヶ月間が楽しみです。

さて、昨年末に公開した実験用環境のmaf (Github)ですが、先週こっそりと v0.2 をリリースいたしました。今日は何が変わったのかをお伝えしたいと思います。

その前に、まずmafについて紹介します。mafは主に機械学習を用いた実験を書くための環境で、アルバイトの能地さん @nozyh と私の2人で開発しています。ビルドツールのwafを拡張する形で書かれていて、データセットから実験結果をビルドする過程を記述することができます。基本的な紹介は昨年末のブログ記事をご参照ください。特徴としては、学習や評価などの処理に付随するハイパーパラメータを管理する仕組みがあることです。詳細はmafのドキュメントをご参照ください。

それでは、v0.2で入った主な変更を紹介していきます。

続きを読む »

ACL2014読み会を開きました

海野 裕也
リサーチャー

2014-07-14 16:12:00

ワールドカップで寝不足の海野です。ドイツ強かったですね。
先週末の7/12(土)に、PFIオフィスにてACL2014読み会を開きました。ACLとは最もメジャーな自然言語処理の国際学会で、先月2014年の会議が行われたので、その論文を読んで発表しあいました。

狭い部屋でしたが、およそ30人の方に参加いただき、発表11件でした。質問も沢山飛んで盛況だったように思います。参加者も、大学や研究機関の先生から、企業の研究員、エンジニア、学生まで幅広くバランスよく参加していただけたようです。そのままオフィスで懇親会を行いましたが、実務で自然言語処理を活用されている方が多く、技術交流が進んだのであれば幸いです。

続きを読む »

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の私がオーナーということで、持てる人脈をフル活用してパネリストをお願いしたところ、お声がけした方全員にご登壇いただけることになりました。

続きを読む »

...34567...