分散深層学習を支える技術:AllReduceアルゴリズム

kfukuda

2018-07-10 11:49:43

本記事は、2017年インターンシップを経て現在はアルバイトとして勤務されている上野さんによる寄稿です


みなさんはじめまして。Preferred Networksの2017夏季インターンに参加し、現在アルバイトをしている上野裕一郎です。普段は東京工業大学でHigh-Performance Computingに関する研究を行っており、分散・並列計算に興味があります。

今回は、分散深層学習を行う際に使用されるAllReduceという通信パターンについて調査・実装・評価を行いましたので、それについてご説明いたします。

分散深層学習とは

現在、ディープニューラルネットワークを用いた学習には長い時間がかかることが知られています。そして、様々な種類のモデルや、大量のデータを組み合わせて学習を試すためには、学習にかかる時間を短縮する必要があります。そのために、多数のプロセスに分散して計算を行うことで、学習にかかる時間を短縮することを目的とするのが分散深層学習です。分散深層学習の詳細については、Preferred ResearchのChainerMN 公開に関する記事[1] をご参照ください。

弊社では、深層学習の研究開発や関連技術の迅速な実用化のために、スーパーコンピュータ MN-1 を運用しています。これは、民間企業のプライベートな計算環境としては国内最大級で、NVIDIA(R)製 Tesla(R) P100 GPUを1,024基、Mellanox(R) InfiniBand FDRを搭載しています。これを用いて、ImageNetの画像分類データセットを利用したResNet-50の学習を15分で完了することができました[2]。

しかし、このような多数のGPUを用いて効率的に計算を行うのは多くの困難が伴います。そのうちの1つとして、データ並列型分散深層学習において、GPU同士の通信にかかる時間がボトルネックとなっていることが挙げられます。

分散深層学習では、どのような通信が発生し、なぜ時間がかかるのか、もう少し詳しくご説明します。

分散深層学習におけるAllReduceの重要性

データ並列型分散深層学習では、異なるデータでモデルのパラメータでの損失関数の勾配を求めたあと、プロセス間で勾配の平均を求め、求めた平均を得られた勾配とみなして、モデルに適用を行います。この勾配の平均を求める操作として、多対多の通信を行う集団通信アルゴリズム:AllReduceが用いられています。

このとき、最もよく用いられているのが、NVIDIA社が提供しているNCCL[3] (NVIDIA Collective Communications Library)です。NCCLは、並列・高性能計算の分野の標準であるMPIと比較して、圧倒的に高速な通信を実現しています。前述のImageNet15分実験においても、NCCLが実現する高速通信は、記録の達成には不可欠なものでした。現在、ChainerMNでデータ並列型分散深層学習を実行するにあたっては、NCCLは必須のライブラリとなっています。

さて、NCCLの高い性能の秘密はどこにあるのか、社内でも多くのリサーチャーやエンジニアが興味を持ちました。今回は、実験的にAllReduce通信プログラムを作成し、最適化することによって、NCCLの性能にどこまで迫れるかを試してみました。

AllReduceのアルゴリズム

では、分散深層学習のスループットに大きな影響を与えるAllReduceについて詳しく見ていきます。
AllReduceとは、すべてのプロセスが持っている配列データを集約(Reduce)したうえで、すべてのプロセスがその結果を等しく取得する操作です。まず、総プロセス数を \(P\), そして、それぞれのプロセスには\(1\)から\(P\)までの番号\(p\)がついているとします。そして、各プロセス\(p\)が長さ\(N\)の配列\(A_{p}\)を持っているとしましょう。さらに、プロセスpが持つi番目のデータを \(A_{p,i}\) とします。このとき、最終的に得られる配列を \(B\)とすると、

$$ B_{i}~~=~~A_{1,i}~~Op~~A_{2,i}~~Op~~…~~Op~~A_{P,i} $$

となります。ここで、\(Op\) は2項演算子で、SUM(合計)、MAX/MIN(最大値/最小値)などがよく用いられます。つまり、ここでいう集約(Reduce)とは、配列の要素 \(A_{p,i}\) を、\(p=1,…,P\)までの全プロセスにわたって \(Op\)を用いて畳み込み計算することになります。分散深層学習においては損失関数の勾配の平均が必要であるため、勾配の要素ごとにSUMを用いて合計を計算します。以降では、集約操作に用いる演算はSUMだと仮定します。図1に、\(P=4\), \(N=4\)のAllReduceを実行する模式図を示しています。

図1. AllReduceの模式図

このようなAllReduce処理を実装する方法として、複数の方法が考えられます。

例えば、最も単純な方法として、代表となるプロセスを1つ決め、そこに全ての配列を集め、そのプロセスが全てのReductionを行い、計算結果を全プロセスに配布する、というアルゴリズムを考えることができます。しかし、このアルゴリズムは、プロセス数が増えると代表プロセスの通信量、Reduceの計算量、メモリ使用量がそれに比例して増え、処理量に不均衡があります。

このようにプロセス間の処理量に不均衡が存在しないよう、うまく通信や計算を全てのプロセスに分散させたアルゴリズムが提案されています。代表的なものとして以下のものが挙げられます。

  • Ring-AllReduce
  • Rabenseifnerのアルゴリズム[4]

本稿では、Ring-AllReduceアルゴリズムについて紹介します。NCCLも、Ring-AllReduceを用いて実装されています[5]。

Ring-AllReduce

まず、総プロセス数を\(P\), そして、それぞれのプロセスには\(1\)から\(P\)までの番号がついているとします。そして、各プロセスが図2のようにリングを構成するとしましょう。

図2. リングの構成例

ここで、プロセスpに着目して処理の流れを見ていきます。

まず、プロセスpは、自分の配列をP個に分割し、この分割された配列のp個目をチャンク[p]と表記するとします。そして、プロセスpは、チャンク[p]を次のプロセスp+1に送信します。この時、同時にプロセスp-1はチャンク[p-1]の送信を行っているので、プロセスpはこれを受信することができます(図3)。

図3. 各プロセスpがチャンク[p]を送信する

そして、プロセスpは、受信したチャンクに自分のチャンク[p-1]を足し込み(Reduceし)、計算結果を次のプロセスに転送します(図4)。

図4. 各プロセスがReduce後のチャンク[p-1]を送信する

これをP-1ステップ繰り返すことで、それぞれのプロセスが、Reduce済みのチャンクを1つ手に入れることができます(図5)。

図5. P-1ステップの繰り返しが終了し、Reduce済みのチャンクを1つ手に入れる

言い換えれば、各々のプロセスが、リングの上をまわるチャンクに、自分のチャンクを少しずつ足しこんでいきます。そして、チャンクがリングに沿って全プロセスを1度ずつ訪問した時点で、そのチャンクは、全てのプロセスのチャンクの集約の結果になっています。つまり、最終的には、それぞれのプロセスが、チャンクごとの集約の結果を1つ保持していることになります。

そして、それぞれのプロセスが持つ集約済みチャンクを、さらにリング上で一周回すことで、全てのプロセスが集約済みチャンクを全て取得でき、AllReduceが完了したことになります。

では、このアルゴリズムの通信量を、先程挙げた単純なアルゴリズムと比較してみましょう。

単純なアルゴリズムの場合、代表プロセスが受信するデータの量は、代表プロセスでない全てのプロセスからデータを受信する必要があるので、\((P-1) * N\)となります。その後、代表プロセスでない全てのプロセスにデータを送信する必要があります。これは、Pに対して代表プロセスの受信量が比例しています。

対して、Ring-AllReduceにおける1プロセスあたりの送信(受信)したデータの量は、以下のように求めることができます。最初に、P個に分割した配列をReduceしながらP-1回送信しました。そして、全プロセスにそのReduce済みチャンクを配布するために、P-1回送信しました。よって、1プロセスあたりの送信量はこの合計である \(2(P-1)/P * N\)となり、1プロセスあたりの送信量はPに関して定数であることが分かりました。

よって、2つのアルゴリズムを比べると、Ring-AllReduceは代表プロセスに集中していた送信・受信量を各プロセスにうまく分散させたアルゴリズムになっていることが分かります。このような特徴から、多くのAllReduceの実装でRing-AllReduceアルゴリズムが用いられています。

実装と最適化

Ring-AllReduceのアルゴリズムそのものは、GPU対GPUの通信を行う送受信関数を用いれば、簡単に実装することができます。Baidu社によるbaidu-allreduce[6]は、MPIのライブラリ上で実装済みの MPI_Send, MPI_Recv関数を用いてこれを実現しています。

今回は、MPIではなく、InfiniBandを直接扱うことができるInfiniBand Verbsを用いて実装し、より進んだ最適化を試みました。まず、InfiniBand、GPU、CPUのそれぞれのハードウェアリソースのアイドル時間を可能な限り削減して性能を引き出すために、アルゴリズムの処理をRegistration, Send, Reduction, Receive, Deregistrationなどのステージに分割し、パイプライン化を行っています。ここで、Registration, Deregistrationは、メモリ領域をDMAを用いて転送する際に必要な前処理、後処理を表しています。これらは、MPIを用いて実装すると、 分割してパイプラインに組み込むことができません。
さらに、配列を分割したものであるチャンクを、パイプラインの粒度をより細かくするために更に分割しました。また、メモリ確保は低速であることが知られているので、メモリプールを導入してコストを隠蔽しています。

性能評価

本稿で実装したプロトタイプ(PFN-Proto)の性能を、他の既存実装(詳細は付録に記載)と比較しました。比較対象を、スーパーコンピュータで広く用いられている通信ライブラリであるOpen MPI[7]、Baidu社によるbaidu-allreduce[6]、NVIDIA社によるNCCL[3]です。

なお、今回の我々のプロトタイプ実装は、ノード間通信に焦点を当てて開発しており、ノード内でのGPU間のDMA通信や共有メモリを使った通信最適化は実装されていません。実験では、1ノードに1プロセスを実行する条件でのみ測定しています。また、Open MPIについては、最新シリーズであるバージョン3.xではGPU Directに関係するバグがあり、弊社内ではまだ導入していないため、2.1.3を測定対象としています。

総プロセス数を8として、1ノードに1プロセスを起動することとし、256MBの配列のAllReduceをそれぞれ10回ずつ実行して測定を行いました。実験環境は、MN-1を用いています。実験環境の詳細は付録「実験環境」をご参照ください。図6に性能評価の結果を示します。

図6. AllReduceの実行時間の評価

この棒グラフは実行時間を示しており、低いほうが良い結果を示します。各棒は、それぞれのライブラリの10回の実行時間の中央値、エラーバーは実行時間の95%信頼区間を表しています。各実装の名前の意味、バージョンなどは、付録「比較対象ソフトウェア」をご参照ください。

まず、実行時間の中央値について見てみましょう。一番右側に示されているPFN-Protoが、最も高い性能を示しています。これは、ompi, ompi-cuda, Baidu, NCCLと比較して、それぞれ約82%, 286%, 28%, 1.6% 高速となっています。なお、グラフ上には示されていませんが、10回試行中の最速は、baidu-allreduceで0.097 [s] となりました。

次に、実行時間の分布について見てみましょう。中央値を基準にした実行時間の最大値と最小値は、PFN-Protoが +/-3%、NCCLが+/- 6%以内に収まっています。一方、baidu-allreduceは最大値が中央値の7.5倍という大きな数字となりました。これは、初回実行時に大幅に時間がかかるためです。なお、初回の試行を除いた最大値も中央値の+9.6%となっており、依然としてNCCLおよびPFN-Protoよりもばらつきが大きいことがわかります。

MPI、およびMPIをベースにした実装でこのように性能にばらつきが出る原因としては、MPIが内部で行っているメモリ領域の扱い方に関連していると推測しています。MPIは、InfiniBandによる送受信に必要となるメモリ領域の確保とRegistrationなどを抽象化したインターフェイスを提供しています。これにより、Ring-AllReduceの実装から、それらの発生タイミングを精密に制御することができないため、性能にばらつきが出ると考えられます。

関連研究

今回は、分散深層学習の中のAllReduce操作の高速化についてご説明しました。それ以外にも、分散深層学習の通信部分を高速化する方法として様々なものが考えられています。例えば、

  • 勾配の送受信を1イテレーション遅延させて、Forward, Backwardと通信をオーバーラップする方法(例:ChainerMNにおけるDouble Buffering[8])
  • データの浮動小数点精度を下げることによって通信量を削減する方法(例:ChainerMNにおけるFP16通信[8])
  • 勾配の値の重要度によって送受信するデータを間引いて通信量を削減する方法[9]

などがあります。特に、InfiniBandを持たないような環境(例えばAWS)では、このようなテクニックを用いることで学習を高速化することができます。

まとめ

本記事では、分散深層学習を支える技術である、AllReduceという通信パターン、特にRing-AllReduceという通信アルゴリズムについて説明しました。

そして、このアルゴリズムを実装し、今回の実験環境・実験条件では、NCCLと同等の性能まで最適化することができました。そのためには、InfiniBand Verbsを使用し、徹底的なパイプライン化を行うことが必要であったことが分かりました。これにより、高いハードウェアの性能と並行性を十分に活用することができました。これからも、より高速で、高い信頼性を持つ通信にはどのようなアルゴリズムやチューニングが最適か、調査・開発を進めていきたいと考えています。

ただし、今回の実装は、社内のクラスタを使用して開発・最適化しており、社内のクラスタのみに最適化された実装になっている可能性があります。それに対してNCCLは、幅広い環境で安定して利用できる高速な集団通信ライブラリであり、依然として、NVIDIA製GPUを用いて分散深層学習を行うためには、NCCLを使用するべきであると考えています。

謝辞

最後に、インターンの頃からメンターの方々やチームの方々には手厚いサポートをしていただきながら、大量の計算資源のもとでプロジェクトを進めることができており、非常に貴重な経験をさせていただいています。本当にありがとうございます。


おまけ:メンターより

上野さんのインターンシップメンターを務めています、PFN 大規模分散計算チームの福田(@keisukefukuda) です。今回は、NCCLの高い通信性能はどのように実現されているのだろうか?という疑問からスタートした実験的なプロジェクトでしたが、上野さんの高い技術力によってNCCLに近い性能を出すことに成功しました。

PFNでは、機械学習/深層学習そのものの研究だけでなく、ソフトウェアからハードウェアまで、広い分野で研究開発を進めています。

HPC・高性能計算に興味を持っている学生の皆さんは、ぜひ来年のPFNインターンシップへの応募をご検討ください(このブログ記事の公開時点では、残念ながら2018年の夏季インターンの募集は終わってしまいました)。

また、もちろん中途・新卒の人材募集も通年で行っています。興味のある方はぜひご検討ください!PFNの人材募集のページはこちら https://www.preferred-networks.jp/ja/jobs です。

参考文献

[1] 分散深層学習パッケージ ChainerMN 公開
[2] Akiba, et al., “Extremely Large Minibatch SGD: Training ResNet-50 on ImageNet in 15 Minutes”
[3] NVIDIA Collective Communications Library
[4] Rabenseifner, “Optimization of Collective Reduction Operations”, ICCS 2004
[5] Jeaugey, “Optimized Inter-GPU Collective Operations with NCCL”, GTC 2017
[6] baidu-allreduce
[7] Open MPI
[8] ChainerMNのクラウド環境向け新機能とAWSにおける性能評価
[9] Tsuzuku, et al., “Variance-based Gradient Compression for Efficient Distributed Deep Learning”, In Proceedings of ICLR 2018 (Workshop Track)

付録

比較対象ソフトウェア

Implementation Version Note
MPI (ompi) Open MPI 2.1.3 CPUメモリからCPUメモリへの転送
(他の実装はすべてGPUメモリからGPUメモリへの転送)
CUDA-aware MPI Open MPI 2.1.3
baidu-allreduce (baidu) A customized version of baidu-allreduce, based on commit ID 73c7b7f https://github.com/keisukefukuda/baidu-allreduce
NCCL 2.2.13

実験環境

  • Intel(R) Xeon(R) CPU E5-2667 x 2
  • Mellanox(R) ConnectX(R)-3 InfiniBand FDR (56Gbps) x 2
  • NVIDIA(R) Tesla(R) P100 GPU (with NVIDIA Driver Version 375.20)

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

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

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

maruyama
リサーチャー

2014-03-24 15:59:41

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

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

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

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

続きを読む »

異常検知の世界へようこそ

hido
Chief Research Officer

2013-01-17 16:22:38

比戸です。

先週Jubatusの最新0.4.0がリリースされましたが、外れ値検知機能の追加が目玉の一つとなっています(jubaanomaly)。昨年PFIへ入社して初めて手がけた仕事が公開されたということで感慨ひとしおですが、便乗してあまり語られることのない異常検知の世界について書きたいと思います。以下の資料は昨年のFIT2012で使ったものです。

続きを読む »

ウェーブレット木の世界

岡野原 大輔

2013-01-09 20:43:44

岡野原です。ウェーブレット木の解説を統数研チャンネルにて行いました。

統数研チャンネル(プレミアム会員ならしばらくタイムシフト視聴可能)。

ウェーブレット木は万能のデータ構造であり、系列データ、全文検索、グラフ、二次元情報、フィンガープリントなど様々なデータに対して多くの操作をサポートします。

本解説では大規模データの背景、ウェーブレット木の作り方、使い方、様々なデータへの適用、最前線(ウェーブレット行列)などを紹介しています。本解説は拙著「高速文字列解析の世界」とあわせてみていただけたらと思います。

機械学習と自然言語処理とビッグデータ

岡野原 大輔

2012-12-25 11:06:59

岡野原です。

情報処理学会主催の連続セミナー「ビッグデータとスマートな社会」での機械学習の回、自然言語処理の回での講演資料を公開しました。

今年はビッグデータという言葉が広まったということで、このテーマで話す機会が多かったです。今はビッグデータというとそれを支えるインフラ、クラウド、DBなどがまず注目されていますが、我々としては実際それを使って何をするのか、何が実現できるのかというところを注目しています。

PFIは元々こうしたデータを分析して価値を提供する(検索エンジンとかもその範疇に入ると思います)ことをずっと続けてきたわけですが、ビッグデータという言葉が広まってくれたおかげでこの考えがより受け入れられ様々な業界の方と随分と話がしやすくなったと思います。

以下の講演資料では、今ビッグデータの中でも機械学習と自然言語処理の分野において我々がどこに注目しているのかを話をしました。

bigdata2012ml okanohara from Preferred Infrastructure Inc,
  • リアルタイム分析が重要な事例の紹介、
  • それを支えるオンライン機械学習の多値分類の技術例
    (昨年のIBIS2011のチュートリアルからの抜粋、雰囲気がわかれば)
  • 大規模リアルタイム解析Jubatusについて

bigdata2012nlp okanohara from Preferred Infrastructure Inc,
  • 自然言語処理を取り巻く世界の変化(多言語化・大規模リアルタイム化)
  • 情報フィルタリングの重要性の増加
  • 業界における自然言語処理
  • 次の自然言語処理を支えるツール

Centroid Path Decompositionを使ったトライでダブル配列と勝負してみた

preferred

2012-06-04 10:58:23

釣りタイトルを付けたかったのですがさっぱり思いつかないのでもう諦めました。徳永です。

今回はCentroid Path Decomposition(以下CPD)についての話を書きます。直訳すると重心パス分解となるでしょうか。Trieを実現するためのテクニック(普通のツリーにも使えるのかな?なかなか難しそうですが…)の一つです。CPDは一年前の弊社岡野原の記事に出てきますが、私のような素人にはあれだけでは理解できない部分があったので、今回はちょっと論文を読んでみました。

続きを読む »

空間木を利用した関連事例の抽出技術

preferred

2012-01-27 19:56:31

はじめまして伊藤です。1月から PFI で働いてます。

今回は関連事例の抽出技術についてお話しします。関連事例の抽出は推薦(レコメンド)サービス等で利用される技術です。ここで事例は扱う対象によって異なります。対象が文書集合であれば、事例は文書を表しますし、E-コマースサービスのログデータであれば、サービスを利用するユーザを表します。
続きを読む »

大規模データ処理勉強会でJubatusに関する発表をしました

海野 裕也
リサーチャー

2011-12-11 23:18:01

金曜日はしっかりバルスしました、海野です。先週の木曜日に、NTTデータ様で行われた大規模データ処理勉強会に出席し、Jubatusに関する発表を行いました。実は、前のポストの @tanakh さんの PFI Seminar と、発表時間が完全にかぶってしまいましたw 資料はこちらです。

当日のUSTREAMもあるようです。

11月のJubatus Workshopでの発表の内、機械学習に関する部分をまとめ直したような内容です。こちらにご参加くださった方には物足りない内容だったかもしれません。オンラインかつ分散という設定での機械学習の理論はまだまだ萌芽的で、今後の大規模データ時代に花開くのかもしれないなぁ、ということを最近思うのでした。

文書解析のための簡潔データ構造

岡野原 大輔

2011-12-02 18:41:30

岡野原です。

12/1〜12/2に高松で開催されたALSIP2011で文書解析のための簡潔データ構造の最近の進展について話をしてきました。

ここの業界の進展は速く毎年様々な方法が出てきますが、要点だけを上げると

– Wavelet Treeがアルファベットサイズが大きい場合のRank/Select操作だけではなく、2D矩形探索、最頻要素列挙など様々な問題を効率的に解けることが分かってきて非常に重要なデータ構造であることが分かってきた。2D探索も、もはや数億 x数億とかでも解けてしまうので2D探索を利用するような様々な手法が全部現実的になった。

– Top-K Queryが盛り上がっている。検索などデータ構造に問い合わせをする際に、該当する結果を全部を列挙することの高速化は理論的にも難しいが、スコアが高い順(例えばterm frequencyやPageRankなど)にk個だけ列挙するだけなら非常に高速にできる。この場合も大体Wavelet TreeのGreedy Searchが使われるが、Top-Kを効率的に実現するためのデータ構造(グリット上の優先度付キュー)も研究が盛ん

– CFG (Straight Line Program)をベースにしたGrammer Compressionが実用的になって、いろいろなところで使われ始めている。元々Navarroらのグループが多く利用していたRePairだけではなく、九大の研究グループが中心となってやっている方法などはかなり実用的になってきた。現実的な時間での文法抽出だけでなく、抽出した後のデータに対する簡潔データ構造表現も盛ん。

ちなみに高松ということで、ご飯は、うどん、うどん、鍋+うどん、徳島ラーメンでした。

12