Jubatus のバースト検知を使ってみた話

はじめまして。

システム開発・コンサルティング部の potter と申します。日頃は smarticA!DMP の運用をしております。

さて、 soonraah ガエルの記事を読んで「自分も何かやりたい!」と思い Jubatus という オンライン機械学習向け分散処理フレームワーク を使ってみました。今回は先月に新機能として追加されたばかりのバースト検知を試してみます。

ではでは、少しの間お付き合い頂けますと幸いです!

バースト検知とは?

バースト検知って何?という方もいらっしゃるかと思いますが、 Jubatus Blog にも記載されているように「特定のキーワードを含むツイートが突然増えたことを検出する」といったことを可能にする技術です。

具体的な例として「金曜ロードショー ラピュタでバルス!現象」1について考えてみます。 Twitter ストリーム上のツイート系列を考えた時、「バルス」という単語を含むツイートは平常時(状態1)ではあまり発生しませんが、ラピュタの放送前後(状態2)では大量発生します。

ここでバースト検知システムに予め「バルス」という単語をキーワードとして登録しておき、 Twitter ストリーム上のツイートを逐次入力していれば、バースト状態が発生したことを検知できます。この検知により、何かしら状態変化を発生させる潜在的な要因(今回の例ではラピュタのテレビ放送)が発生した可能性に気付くことができます。

「バルス」のバーストを検知したい人はあまりいないと思いますが、製品名などの自社ビジネスに関連の深い単語をキーワードとして登録しておくことでそのキーワードの周辺の状態変化を示唆する情報が得られるなど、マーケティング的な用途も考えられます。その他、使い方によっては様々な場面で役立つ技術なのではないでしょうか。

Jubatus を実行する環境の準備

さて、それでは Jubatus のインストールを行いましょう。 今回は Vagrant を用いて Vagrantbox.es に配置されている Ubuntu の Box ファイルから実行環境を準備します。

まずは下記の通り Vagrant で仮想環境を準備してログインします。2

あとは公式のインストール手順の通りに Jubatus と Jubatus クライアント(今回は Python を利用)をインストールします。私が実施した際には手順通りで特に問題なくインストールができました。

Jubatus のインストールが完了したら下記のコマンドを実行してみましょう。

バージョン情報が表示されれば、バースト検知の機能を含んだ Jubatus のインストールに成功しています。

バースト検知を実行してみる

環境の準備が整いましたので Client API のリファレンスを参考に早速 Jubatus でバースト検知を実施してみます。

まずはサーバー側の設定ファイル(burst.json)を作成します。

作成した設定ファイルを指定して jubaburst を実行します。

これでクライアントからの要求を受け付ける準備ができましたので、下記の Python プログラム(burst.py)を実行してバースト検知を実施します。3

実行結果

サンプルプログラムと実行結果について簡単に説明します。

サンプルプログラムでは「バルス」という単語を登録してバースト検知を実施しています。今回は入力する文書リストを下記のように作為的に作成しました。

  • 0.1秒毎に0.9の確率で文書を生成する。
  • 文書を生成する場合、 pos (時系列的な位置)に従って下図の確率でキーワードを含む文書を生成する。

juba_testdata_probability

実行結果では pos = 20 が含まれる Window (pos = 0.0 ~ 60.0の区間)におけるバースト検知結果が得られています。 burst_weight はその Batch におけるバースト強度を示しています。 burst_weight > 0 であることはその Batch がバースト状態であることを意味します。実行結果を見ると pos = 24.0 ~ 38.0 がバースト状態となっており、文書リストに対して納得感のある結果になっていると思います。

バースト検知の仕組みについて

さて、前節でサラッとプログラムを実行してみたわけですが、正直なところこのプログラムを作成して実行結果を理解するだけでもそれなりに苦労しました。それはバースト検知のアルゴリズム自体がわかっていなかったため、リファレンスに出てくる用語やパラメータの意味するところが理解できず、また、既存のサンプルプログラムなども見つけられなかったためです。。

最初にリファレンスを読んだ段階では

  • Window とか Batch って何?
  • スケーリングパラメータとかガンマってどういう意味を持つパラメータなんだ??

・・・といったあり様でした。そこで下記のような情報ソースからバースト検知の仕組みについて調べました。

同じような疑問を持っている方もいらっしゃるかもしれませんので、上記から私が理解した内容をまとめさせて頂きます。少しでもバースト検知をやってみたいと思っている方の参考になれば幸いです。7

下記のイメージ図をご覧下さい。

burst_image

まず Window とはバースト検知を行う際に注目する区間を意味します。また、 Batch は Window 内でバースト状態か否かを判断する文書集合の単位であり、一定の幅の時系列的区間に対応します。図中の Window2 に対してバースト検知を行った場合、 Batch1 ~ Batch4 の中でどの Batch がバースト状態であるかの結果を得ることができます。なお、図は burst.json で指定した window_batch_size =4 , batch_interval = T の想定です。

文書が追加された際、その pos を含む Window がまだ存在しない場合には新たな Window が作成されます。図において Window1 しか存在していない状態で赤星の位置に文書が登録された場合、その pos の直前の区切り時刻(pos = 4T)を中心にして新たに Window2 が作成されます。黄星の文書によって Window3 が作成される際も同様です。

Window2 に対するバースト検知についてさらに見て行きましょう。 Window, Batch が決まったら、各Batchにおいて観測された全文書の数(図中 d)、観測された文書のうちキーワードを含む文書の数(図中 r)を集計します。さらに Window 全体での両文書数(図中 D と R)も集計します。

ここで、バースト検知は図のように Batch を生成する2状態のオートマトンをモデルとして定義することで実施されます。  Q_{base} はバーストしていない状態(本エントリでは Base 状態と呼びます)を、 Q_{burst} はバースト状態(本エントリでは Burst 状態と呼びます)を示します。Kleinberg の手法では Base 状態、 Burst 状態でキーワードを含む文書が出力される確率は下記の通り定義されます。

 P_{base} = R / D
 P_{burst} = P_{base} \times s

この  s が Jubatus でキーワード作成時に指定するスケーリングパラメータになります。つまり、スケーリングパラメータを調節することで、モデルにおいて Base 状態と Burst 状態でキーワードを含む文書が生成される確率がどれぐらい離れているかを調節できることになります。

また、 Base 状態から Burst 状態への状態遷移コスト  \tau は下記の通り定義されます。ただし  n は Window を構成する Batch の数です。 

 \tau = \gamma \times \ln(n)

ここで登場する  \gamma  は Jubatus にキーワードを登録する際に指定する  \gamma  値になります。  \gamma  値が大きいほど Burst 状態への状態遷移コストが大きくなりますので、リファレンスに記述のある通り  \gamma  値が大きいほど「バースト検知の感度が低くなる」ということが言えそうです。

なお、 Burst 状態から Base 状態への状態遷移コストは  0  です。

ここまでで見てきたように、 Window が決まれば各 Batch を生成するモデルとなるオートマトンが決まります。このオートマトンによって Window 内の各 Batch が生成されると考えた時、どのように状態遷移することが最も自然であるかを調べることが、どの Batch がバースト状態であるか否かを調べることになります。

上図を見たとき、感覚的には 「Batch1(Base)->Batch2(Base)->Batch3(Burst)->Batch4(Base)」 となるのが最も自然な感じがします。これは人の感覚的な判断ですが、アルゴリズム的には「どのように状態遷移することが最も自然であるか」はコストが最小になるようなオートマトンの状態遷移系列を求めることで決定されます。とても大雑把な言い方となりますが、状態遷移系列のコストとは Window 内の Batch 系列(における文書数)が生成されたという事実の元での「状態遷移系列の不自然さ」の尺度と考えて頂ければ良いと思います。

コストの演算イメージは下記の通りとなります。

optimal_state_sequence

状態遷移系列のコスト演算では2種類のコストを考える必要があります。1つ目は前述した  \tau  ですね。もう1つは Batch が Base 状態、及び、 Burst 状態であることに対するコスト  \sigma  です。

 \sigma(i,d_t,r_t) = -1 \times \ln({d_t \choose r_t}p_i^{r_t}(1-p_i)^{d_t-r_t})

この式は各 Batch で生成される関連文書数(キーワードを含む文書数)が二項分布に従うという仮定から、二項分布の確率に  -1 をかけた形となっています。 Batch3(d = 32,r = 28) に注目して、 n = 32 における p = 0.3 と p = 0.9 (s = 3.0 を想定)の二項分布を示します。

binomial distribution

k = 28 では Burst 状態の分布による確率の方が大きく、Batch3 に対しては Burst 状態である方が自然であることがわかります。

さて、それでは状態遷移系列のコスト計算に入ります。この例では下記の通り16通りの状態遷移系列が考えられます。

  • base -> base -> base -> base
  • base -> base -> base -> burst
  • ・・・・
  • burst -> burst -> burst -> burst

この中でコストが最小となるものが最適な状態遷移系列として選択されます。8 上図の赤い矢印のパスは「base -> base -> burst -> base」という状態遷移系列になりますが、この系列のコストは下記の通りとなります。

 \sigma(0,d_1,r_1) + 0 + \sigma(0,d_2,r_2) + \tau + \sigma(1,d_3,r_3) + 0 + \sigma(0,d_4,r_4)

この状態遷移系列が最小コストとなる場合、 Batch3 が Burst 状態であり、その他は Base 状態であるということになります。

なお、実行結果に出力されている burst_weight はバースト状態の Batch に対して下記のように Batch3 における Base 状態と Burst 状態のコストの差として算出されます。

 \sigma(0,d_3,r_3) - \sigma(1,d_3,r_3)

長くなりましたが、以上がバースト検知の仕組みに関する説明となります。

まとめ

  • オンライン機械学習向け分散処理フレームワークの Jubatus の実行環境を作ってみた
  • Jubatus を使ってバースト検知を実施してみた
  • バースト検知の仕組みについて考えてみた

以下は感想となりますが、やはりオープンソースでプログラムが公開されているというのは良いですね。論文しかなかったら理解するのにもっと時間がかかったであろう部分もあります。機械学習のアルゴリズムについて勉強する際、こういったオープンソースの機械学習フレームワーク・ライブラリのソースコードも一つの参考情報とするのも良いなと感じました!

やや長い記事となってしまいましたが、ここまでお付き合い頂きましてありがとうございます。初投稿ということで若干ハリキリ過ぎてしまいましたが、次回からはもう少しカジュアルな記事にしたいと思いますので、今後ともよろしくお願い致します。

ではでは、今日はこのあたりで。

Have a nice burst!!!


  1. 金曜ロードショーで「天空の城ラピュタ」が放送された際、作品内の登場人物が「バルス」という呪文を唱えるタイミングと共に、 Twitter に「バルス!」と投稿する人が突発的に増加する現象を指します。なお、もちろん一般用語ではありません。 

  2. Vagrant については詳しい説明を省略します。また、 Windows 環境においては「vagrant ssh」でアクセスすることができず、別途ターミナルからアクセスする必要が生じるかと思います。もちろん別の方法で環境を準備して頂いても問題ありません。 

  3. 今回はサンプルのため文書登録とバースト検知結果取得を一連の流れで行っていますが、実際には文書を登録するプログラムとバースト検知結果を取得するプログラムは別々になると思います。 

  4. Kleinberg の論文です。特に p14 ~ p16 が Jubatus のアルゴリズムと関連が強い部分となります。 

  5. ソースコードが確認できるのはオープンソースの素晴らしいところですね! engine.cpp がアルゴリズムのコア部分の実装かと思いますが、 sigmatau など論文にも出現する数式が実装されているのが確認できて面白いです。 

  6. 株式会社NTTデータ数理システム 知識工学部様の技術レポートページです。英語も C++ も堪能でない自分にとっては貴重な情報でした。ありがとうございます! 

  7. こちらは Jubatus におけるバースト検知について記述したものとなりますが、本エントリに記述した内容は公式の情報ではなく、説明のために簡略化している部分などがございます。あくまで「バースト検知の仕組みを理解するための参考情報として記述したものであり、正確な仕様を伝えるために記述したものではない」ということを予めご承知おき頂けますと幸いです。 

  8. 実際には動的計画法的に計算して最適な状態遷移系列を見つけます。