MapReduce以外の分散処理基盤BSP, Piccolo, Sparkの紹介

preferred

2011-06-17 14:32:34

どうも,実は今年から開発チームにjoinしていた中川です.可愛い犬の写真がなかったので,可愛いマスコットの画像を貼っておきます.

最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました.これはつまり,それだけ大量のデータをなんとか処理したいという要望があるからだと思います.しかし当たり前ですが,MapReduceは銀の弾丸ではありません.

ということで,最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について,社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います. 続きを読む »

多項式フィッティングのワナ

preferred

2011-06-15 20:12:45

Meow

今回は新しい試みとして、かわいい柴犬の画像によっていろいろなことをごまかすことにチャレンジしています。なお、画像はflickrからCCライセンスのものをお借りしております。画像をクリックするともっと大きいのが見れるよ。

続きを読む »

最近のtrieの話(xbwなど)

岡野原 大輔

2011-05-20 19:24:32

岡野原です。
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。
今回はtrie(トライ)の最近の話をしたいと思います。
trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS(Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。
trieは図にあるように、木構造で各枝に文字が付随しており、根から葉へのパス上に付随する文字をつなげた文字が各キーに対応します。
同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下にある葉を全て列挙するだけです。hashはこの操作を効率的に行うことはできません。同様に辞書式順序でxよりも大きく、yよりも小さいキーを全て列挙するといったこともtrieは効率的に実現できますが、hashだとできません。
trieの大きな問題点として、木構造を格納する必要があり作業領域量が大きいという問題がありました。そのまま木構造を素直にポインタベースで実装してしまうと、元のキー集合に対しその数倍の作業領域量を必要とする場合も少なくありません。
この問題は簡潔木を利用することで解決できます。このアイディアを実装したものがtx, uxなどです。私もお世話になっているGoogle IMEもtxのクローンであるrxを利用することで大規模辞書を効率的に管理しています。
木構造を圧縮すると、元のキーをそのまま格納するよりも小さく格納できるようになり、データ圧縮としても利用することができます。trieでは文字列の先頭部分(接頭辞、prefixと呼びます)を一つのパスとして表現することができるためです。しかも、通常のデータ圧縮とは違って、データ全体を復元しなくてもあるキーのみを復元するということができます。
簡潔木を利用したtrieについての情報は既にある程度広まってきているので、今回は簡潔木を利用しないtrieの最新情報についていくつか紹介します。

XBWを利用したtrie

[1] “Structuring labeld trees for optimal succinctness, and beyond”, P. Ferragina, and et. al. FOCS 2005
[2] “Succinct Dictionary Matching With No Slowdown”, D. Belazzougui, CPM 2010
[3] “Faster Compressed Dictionary Matching”, W. K. Hon, and et. al. SPIRE 2010

ラベル付木に対する簡潔データ構造であるxbwは[1]により最初に紹介されました。その後[2], [3]の論文で、さらにxbwはシンプルになり高速化されています。

xbwについて簡単に説明します。

ノードから根に向かって辿った時の文字列をつなげた文字を、そのノードのreverse prefix pathと呼ぶことにします。次に全ノードをreverse prefix pathの辞書式順序でソートします。複数のノードが同じreverse prefix pathを持つ場合がありますが(trieの場合は無いが)、その時は木中の幅優先探索の順序順で順番を決定するとします。最後に各ノードの子に付随する文字をその順に格納します。これがxbwです。先ほどのtrieの場合の例を以下の図に示します。列reverse prefix pathは各ノードから根に向かうパスであり、末尾は特殊文字$がつけてあります。この$は他のどの文字よりも小さいとします。列childrenにそれぞれのノードに対応する子に付随する文字を格納します。ここで#とあるのはそこが終端ノードであることを示しています。この#は他のどの文字よりも大きいとします。children内部での順序は関係ありませんので集合で表すことにします。例えばchildren[1] = {t, i, w}, children[3] = {a, n}です。

結論を先に言うと、このchildrenの列だけを使って先程のtrieを完全に表現することができます(reverse prefix pathはいらない)。

実際に節点をchildrenの情報だけを使って辿ってみましょう。

rank(i, c)をchildren[1…i-1]中に含まれる文字cの出現数と定義します。また、C(c)を全てのchildren中で”c”より小さい文字の出現個数とします。例えばこの図の例ですとですとC(a)=0, C(e)=2, C(i)=4…となります。
まず、図中の根のノードに着目してみます。先程の表では、i=1となります。ここからラベル”t”を辿った場合、次に行くべきノードのreverse prefix pathは”t$”です。このノードは”t”で始まるreverse prefix pathを持つノードの中では最小のはずです。よって”t$”を持つノードはC(t)+1 = 10となります。

では、次にこのノードからラベル”e”を辿るとすると、その節点は”et$”をreverse prefix pathとして持つはずです。”e”で始まるreverse prefix pathを持つノードの数は、children[1…9]の中で”e”を持っている数に一致します。なので、”et$”に対応するノードの番号はC(e)+rank(10, e)+1=3となります。

このように、現在iの位置にいる時に文字cを辿った先のノード番号は

C(c)+rank(i, c)+1

として求められます。C(i, c)+1は文字”c”から始まるreverse prefix pathを持つノードが始まる添字番号であり、rank(i, c)はその中での順番です。

既にお気づきの方も多いと思いますが、これはBWT (Burrows Wheeler Transform, BlockSorting) におけるLF-mappingと同じ考えです。bwt(block sorting)は一本鎖のパスからなる木に対するxbwであり、xbwはbwtの自然な拡張になっています。

さて、このchildrenのテーブルをどのように効率的に格納し、rankを高速に求められるかが問題です。BWTの場合はここが文字列になっていたため、wavelet treeを利用することができました。今回は各位置に複数の文字が存在します。[1]では、ビットベクターと組み合わせることによって、集合を文字列にしてしまい、文字列に対するrank操作の問題に還元しました。[2], [3]では、各文字ごとに、転置ファイルのようにその位置に文字cが出現したかどうかをbit vectorで記録し、bit vectorに対するrank操作としてこれを実現します。どちらも、trieに対するk次経験エントロピーに漸近するサイズで格納できるということが示されています。

さらに、[3]では、このxbwを利用してAC法が実現できることが示されています。

木を潰したtrie

[4] “On searching compressed string collections cache-obliviously”, P. Ferragina, and. et. al. PODS 2008
もう一つ面白いtrieがFerraginaらによって提案されています。
論文にはcache-obliviouslyとありますが、注目すべきはcentroid path decompositionです。従来のtrieは遷移するノード数分だけランダムアクセスが発生しており問題になっていました。特にデータをディスクなどに格納している場合、アクセス回数が操作時間に直結するために問題になります。centroid path decompositionは元々の木を縦方向にぐしゃっとつぶします。
イメージだけでも掴んでもらうために、図を論文から借りてきました。左側の元のtrieの太い線に対応するpathをぐしゃっと一つのノードに潰します。このpathの付随するノードは、このpathの左上から順に右上まで反時計回りの順に大小関係が決まります。そのノードにはheavy pathのラベル列と、そのパスから分岐しているノードが何文字目からどのどの文字で分岐しているかの情報を記録しておきます。この情報により潰した後でも木を辿ることができます。
実際どのようにして潰すpathを決めるかについて説明します。
各ノードについて、その子の中で、最も子孫の葉の数が多い子を、そのノードのheavy childと呼びます。次に、各ノードについて、そのノードから葉までheavy childrenのみを辿っていくpathをheavy pathと呼びます。これを利用したcentroid path decompositionは次のように実行されます。まず最初に根に対応するheavy pathをたどってそのpathを一つのノードに潰します。次にそのpathから分岐して伸びている各ノードについて再帰的に同じようにheavy pathを辿って、そのpathを一つのノードに潰すというのを繰り返します。
この操作により、キーの種類数がK、文字種類数がSの時、木の高さは高々 O(log K)個になり、平均して O(log K / log S)個になります。どんなに高い木でもその順序関係を損なうことなく、木の高さを減らすことができ、アクセス回数を減らすことができます。
各節点での分岐数は増えるため、各節点での計算量は増えますが、アクセス回数が減らせることによりメリットは大きい場合が多いです。
この木に対する簡潔データ構造も論文中に提案されています。

Weak Prefix Search

[5] “Fast prefix search in little space, with applications”, D. Belazzougui, and et. al. ESA 2010
最後に紹介するのがweak prefix searchをサポートしたtrieです。
クエリ文字列pに対し、そのクエリ文字列が辞書中のどれかのキーの接頭辞である場合、そのキーの辞書中の辞書式順序の順位を返す操作をweak prefix searchと呼びます。
もし、クエリ文字列が辞書中のどれかのキーの接頭辞で無い場合、結果は保証せずランダムになります。
よって、weak prefix searchはbloom filterのようにone sided errorを許したデータ構造です。例えば、キー集合が{abc, abef, bcde}の時、abcに対しては1, abeを入力したら2、abcdeならランダムな値が返ってきます。
これまでもweak prefix searchを備えたデータ構造はString B-tree (blind  trie)などがこうした機能を有していました。
weak prefix searchは従来のtrieよりも弱い操作です(従来のtrieであれば、無い場合は無いと返すことができる)が、その分作業領域量は少なく抑えることができます。この論文では、
この問題を解くために必要なデータ構造は、従来のキーを格納するよりはるかに少ない作業領域量だけあればよいことを示しました。具体的にはキーの数がK、キーの平均長がLの時、必要な作業領域料はO(K log L)ビットになります。従来だとK Lビット だったのと比べると大きな違いです。
この論文ではz-fast trieを改良したHollow z-fast prefix trieとrange locatorを組み合わせてweak prefix searchを実現します。2-fattest numberなどいろいろ面白いアイディアを利用しています。

最後に

これまで話してきたtrieは実はいずれも動的なキーの追加・削除をサポートせず、前もって与えられたキー集合を扱っていました。
キーの追加・削除をサポートした上で、データをコンパクトに保ちつつ、高速な操作を実現するようなtrieは実現できるのか? これについてはまた紹介します。

論文輪講:Temporal Diversity in Recommender Systems

preferred

2011-04-18 18:45:06

PFIでは今年の4月から有志で論文の輪講を始めました。有名な学会の論文を毎回二人ぐらいが読んできて、資料を作って発表する、という形になっています。(ちょっと前まではTAPL輪講というものをやっていました。論文輪講が落ち着いたら、次はまた教書に戻るかもしれません。)

私も先日発表をしてきたので、その資料を元にこちらの方でも論文紹介を行いたいと思います。

私が担当したのはSIGIR 2010のFiltering and Recommendationのセッションで、以下の3本の論文を紹介しました。

  • Temporal Diversity in Recommender Systems
  • Social Media Recommendation Based on People and Tags
  • A Network-Based Model for High-Dimensional Information Filtering

この3本の中から、今日は Temporal Diversity in Recommender Systems (N. Latia et al.) を紹介したいと思います。

続きを読む »

東北沖地震震災 リアルタイム情報 QuakeMeme.jp を公開しました

preferred

2011-03-23 10:55:36

iPhoneの充電池付きケースを買ったのに、ケーブルが特殊で1本しかなく、オフィスに忘れて結局充電出来てない事態に悩まされている、太田です。

はじめに

PFIでは、QuakeMeme.jpというサービスを公開致しました。「Twitter」のデータを元に、今回の東北沖地震に関する有用なURLをカテゴリ分けして収集するサービスです。

他の地震関係のサービスと比較したQuakeMemeの特徴は「情報鮮度 (リアルタイム性)」です。例として、大きな余震等が起きた時には、数分後にその余震に関する情報がQuakeMemeの上位に表示されます。

またQuakeMemeの全ての結果は機械的によって抽出されたものです。Twitter上ではデマの様な情報も多い中、割と有用な情報を優先的に抽出出来ているかと思います。

このブログエントリでは、このサービスの裏側を少し紹介したいと思います。主に、以下の3つの処理が行われています。

1) 特定のhashtagから、UserStreamAPIでTweetをクロール

まず人手で、約200個の地震関連hashtag (例: #anpi, #jishin, etc.)を収集しました。それをTwitterのUserStream APIに与えると、地震関連のテーマに絞ったツイートだけが抽出出来ます。これにはRT等も全て含まれます。現在は秒間50ツイート程度を収集しています。

このツイート情報を、弊社の開発している検索エンジンSedueに登録します。Sedueは登録後すぐに検索結果に反映出来るリアルタイム機能を持っています。これによりTwitter検索のような、秒単位で検索結果が変わる検索システムを簡単に構築出来ます。

2) カテゴリに紐づいた単語で検索

次に、人手でカテゴリ情報を整備しました。各カテゴリにはキーワードが紐づいており(例: Home, 安否情報, 原発情報)、このキーワードで検索処理を行います。

キーワードは、人手で登録します。例えば安否情報であれば”anpi|安否”, 原発情報であれば “genpatu|原発” 等のキーワードが使用されています。検索処理を行うと、指定したキーワードを含むツイートがヒットします。

実はこの段階でリアルタイム地震情報検索サービスとしてローンチを考えたのですが、ゴミ情報が多く、どれが有用な情報が分からないという問題が有りました。そこで次の方法を考えました。

3) ヒットしたツイートから、URL情報のみをカウント

最後に、検索にヒットしたツイートの中に含まれる”URL”のみを対象する事にしました。つまり検索にヒットした直近5万件のツイートに含まれるURLを抽出し、かつ登場回数でカウントを行い並び替える事を考えました。

これによって、”カテゴリに付与された単語を含むツイートと、同時に呟かれているURL”が抽出できます。現在のページはこの情報をリスト化して表示しています。

システム構成

その他、具体的なシステム構成としては、以下のような技術を使っています。

  • Twitter UserStream API (Ruby Crawler)
  • Sedueリアルタイム検索エンジン (Search Engine)
  • MySQL (RDBMS)
  • Ruby on Rails 2.3.5 (Web Framework)
  • jQuery (UI)
  • Amazon EC2 (インフラ: c1.medium * 2台)

ソースコード

このサービスのソースコードはgithubにて公開しています。

まとめ

勢いで数日で作ったサービスなので至らない所が有りますが、徐々に改善を行って行きたいと思いますので引き続きよろしくお願いします。

データとしては、Twitter以外にもmixiボイスやamebaなう等も、集めたいです (APIが有れば)。後は、フィードやガラケー/スマホ対応をしたい所。

日本語かな漢字変換における識別モデルの適用とその考察について

preferred

2011-03-15 20:35:41

豊橋で豊橋カレーうどんを食べてきました。徳永です。

金曜日から大変な地震が発生しています。被災地の皆様のご無事と、救助に向かわれた方のご無事をお祈りいたします。

さて、今回は、3/7〜3/11の間、豊橋技科大で行われた2011年の言語処理学会年次大会の参加報告をしたいと思います。私はC4セッション(日本語入力における言語処理(1))で、「C4-6 日本語かな漢字変換における識別モデルの適用とその考察」というタイトルで発表してきました。

続きを読む »

分散並列環境における機械学習

岡野原 大輔

2011-02-24 14:17:27

もうすぐ春ですね。花粉さえ飛ばなければ最高なのに。岡野原です。

先日、Hadoop Conference Japan 2011で、”MapReduceによる大規模データを利用した機械学習”というタイトルで発表しました。

発表内容は三部構成になっています。

最初に、機械学習の基本と、それがMapReduceとどのような関係にあるかを紹介しました。その中でHadoop上で動く機械学習ライブラリMahoutの簡単な紹介をしました。

次に、機械学習の最前線ではどのような問題が解かれているかを紹介し、グラフィカルモデルの例、一般の最適化(教師付き学習におけるパラメータ学習)の分散並列化についての話題をしました。

最後に、MapReduceの補完として使えるようなシステムの例としてdremelを紹介しました。このシステムはMapReduceがバッチ型処理で、全データが処理対象の場合が得意なのに対し、一部のデータのみを参照して簡単な解析をする場合のアドホッククエリが得意なシステムです。このシステムについては登場の時からずっと興味を持っており、いろいろな発展形が考えられると思います。基本的に検索索引と構造は似ているので、そのあたりでの技術の交流ができそうですし、機械学習の高速推論とか新しい問題でも使えそうです。

また先週は、これと関連する形でT-PRIMAL 公開勉強会 NIPS2010読む会で、LCCC2010のワークショップでの発表を紹介しました。上の資料と使い回しの部分が多いのですが、より数式とか機械学習の部分とか突っ込んだ内容になっていますので興味のある方はこちらも参考にしてください。またスライドでは略証しかありませんがIterative Parameter Mixtureの収束証明とかは元論文のを追って見てみると面白いと思います。

LCCC2010:Learning on Cores, Clusters and Cloudsの解説

私自身、1台の限られたリソース上でいかに高速化し効率的に処理をするかが好きで分散並列に興味を持ったのは遅めだったのですが、この世界はこの世界でいろいろやることがあって面白いです。
もしこれらのスライドで少しでも興味を持つ人が増えていただければ幸いです。

Enumerator Package – Yet Another Iteratee Tutorial

preferred

2011-02-10 14:30:18

バレンタインチョコ欲しい! 田中です。

Iterateeの素晴らしいチュートリアルを見つけたので、今回はその翻訳をお届けしようと思います。以前、The Monad Reader Issue 16 のiterateeの記事をベースにした解説記事を書いたのですが、こちらの記事はかなり概念的なところから始まり、結構天下り的にiterateeの定義を受け入れていたのに対して、こちらの記事は、一貫して具体例からの抽象化で話が進み、また易しく書かれているので、比較的理解しやすいと思います。また、実際の実装に即して解説されていますので、読み終えて即実際に使ってみることが出来るでしょう。

このチュートリアルを書かれたMichael Snoymanという方は、現在YesodというHaskellのWebフレームワークを精力的に開発されています。Yesodには実際にiterateeがふんだんに用いられており、それが堅牢でハイパフォーマンスのWebサーバを支えています。このWebフレームワークも大変面白く興味深いものですので、またいずれ紹介したいと思います。

続きを読む »

劣微分を用いた最適化手法について(完)

preferred

2011-02-04 18:27:01

もう2月ですが、新年明けましておめでとうございます。徳永です。残り11ヶ月、頑張ってまいりましょう。

続きを読む »

MinHashによる高速な類似検索

岡野原 大輔

2011-02-02 17:08:17

年が明けてもう一ヶ月経ちましたね.岡野原です.

今日はMinHashと呼ばれる手法を紹介します.これは特徴ベクトルの高速な類似検索に利用することができます(クローラーの文脈だとShingleとして知られている).

続きを読む »