DEIM Forum 2016 A7-2

確率的データストリームにおける情報利得に基づいたパターン照合手法
杉浦 健人†

石川 佳治†

佐々木勇和†,††† 名古屋大学情報科学研究科†† 名古屋大学未来社会創造機構
E-mail: {sugiura,yuya}@db.ss.is.nagoya-u.ac.jp, ishikawa@is.nagoya-u.ac.jp
あらまし

センサ技術や機械学習技術の発展により，情報が確率で表されるデータストリームが増加している．本稿

ではそれら確率的データストリームからの情報検出として，複合イベント処理の一つであるパターン照合に注目する．
パターン照合結果（マッチ）を評価する際，一般には生起確率が評価指標として用いられるが，生起確率には多数のイベントから構成されるマッチを過小評価してしまうという問題がある．そこで，イベントの生起の傾向を表す確率モデ
ルを背景知識として使用し，情報利得に基づいたパターン照合を行う手法を提案する．情報利得を用いた際のパター
ン照合アルゴリズムについて述べるとともに，実データを用いた実験により検出されるマッチの傾向などを評価する．
キーワード

複合イベント処理, パターン照合, 確率的データストリーム, 情報利得

1. は じ め に
センサ技術や無線通信技術の発展に伴い，確率で表される
不確かな情報（確率的データストリーム）が増加している．近年では，スマートフォンやウェアラブルデバイスが持つセンサだけでなく，スマートホームなどでは家具や家電に取り付けた

時刻

1

2

3

4

5

6

7

8

a 0.95 0.03 0.02

0

0.5 0.4 0.2 0.2

イベント b 0.05 0.95 0.95 0.05 0.3 0.5 0.5 0.3

0c0.02 0.03 0.95 0.2 0.1 0.3 0.5

図 1 確率的データストリーム

センサからも情報を計測し，得た情報をコンピュータに転送できるようになった．そうして得られる情報を利用することで，ユーザの位置や動作などの推測が可能となっている [3, 10]．しかし，センサから得られる情報には計測誤差などのノイズが含まれるため，一般に得られる情報は不確実な確率的データスト
リームとなる．たとえば，図 1 は三つのイベント {a, b, c}を観測した確率的データストリームの例であり，各時刻で各イベントが生起した確率を表している．なお，ここでは抽象化したイベントを示しているが，実際にはユーザの位置や行動など，対象となるドメインに応じたイベントが観測される．
本稿では，そのような確率的データストリームからの情報検出としてパターン照合に注目する．確率的データストリームが増加したことで確率的データストリームからの情報検出が重要となってきており，データベースにおける処理（結合，集約など）の適用 [13, 14] や Top-k 問合せの実行 [7]，頻出アイテムの検出 [18] など様々な研究が行われている．しかし，非確率的データストリームに対する情報検出としてよく用いられている
パターン照合に基いた複合イベント処理 [4, 5, 9, 15] を行う研究は少なく，その技術はまだ発展途上である．
確率的データストリームに対してパターン照合を行う場合，
パターン照合の結果（マッチ）として様々な可能性が考えられるという点が問題になる．たとえば，以下の様な非確率的デー
タストリーム DS に対してパターン ⟨a+ b+ ⟩ で照合を行った場
合，適合するマッチは ⟨a1 , b2 , b3 ⟩, ⟨a5 , b6 , b7 ⟩ の二つしかない．
なお，イベントの添字は生起した時刻を表す．

一方で，図 1 の確率的データストリームに対して同様にパター
ン照合を行った場合，マッチには全部で 44 個の可能性が考えられる．さらに，それらの中には ⟨a2 , a3 , b4 ⟩ などのようにほとんど検出する意味のないマッチも含まれるため，すべてを単純に検出するのではなく，検出する意義のあるマッチを適切に選択する必要がある．
マッチを選択する指標としてはマッチの生起確率や各イベン
トの生起確率の幾何平均などが考えられるが，それらの指標では検出されるマッチに偏りが生じるという問題がある．まず，既存研究 [8] でも使用されているマッチの生起確率には，多くのイベントから成るマッチを過小評価するという問題がある．
マッチの生起確率はマッチ中の全イベントの同時確率で表されるため，各時刻のイベントの生起が独立であると仮定する場合，
各イベントの生起確率の総乗がマッチの生起確率となる．つまり，マッチ中のイベント数が多いほどマッチの生起確率は小さくなる．そのため，指標に生起確率を用いる場合イベント数の少ないマッチに出力が偏ってしまう．各イベントの生起確率の幾何平均を用いる場合このような問題は起きないが，代わりに似た系列ばかりが検出されるという問題を持つ．たとえば，
図 1 では ⟨a1 , b2 , b3 ⟩ が最大の幾何平均を持つが，平均を使用しているために，似た系列である ⟨a1 , b2 ⟩, ⟨a1 , b2 , b3 , b4 ⟩ なども高い幾何平均を持つ．そのため，図 1 のようにイベントの生起確率に差がある場合，生起確率が大きい時区間のマッチに出力が偏ってしまう．
そこで，マッチを検出することで得られる情報量（情報利DS = ⟨a1 , b2 , b3 , c4 , a5 , b6 , b7 , c8 ⟩.

得）に注目する．情報利得は，ある事実を得たことで減少した情報量（エントロピー）を示し，得た事実の価値を表す．確率トリームにおけるパターン照合はまだ成熟しておらず，そのよ的なパターン照合においては，実際に得られたマッチの生起確

うな無限のデータストリームや曖昧なパターンに対する厳密な率が，ユーザの予測するマッチの生起確率と比較してどのよ

議論はまだ行われていない．そこで本稿も，有限のデータスト

うな値を持つかで情報利得が考えられる．例として，図 1 のリームおよび記述に制限を加えたパターンのみを対象に議論をデータストリームに対してユーザが何の情報も持っていない

行い，それら無限のデータストリームやより柔軟なパターン記

場合，つまりすべてのイベントの生起確率が等しい（= 1/3）

述への拡張は今後の課題とする．

と予測している場合について考える．このとき，たとえばマッチ ⟨a1 , b2 , b3 ⟩ の生起確率は 1/33 ≃ 0.037 であると予測できるが，実際の生起確率は 0.953 ≃ 0.857 と非常に大きい．一方で，マッチ ⟨a2 , a3 , b4 ⟩ の予測される生起確率が約 0.037 であるのに

3. 準

備

議論の準備として，確率的データストリーム，パターンの記述方法と対応するマッチ，確率モデルの定義を行う．

対して，実際の生起確率は 3.0 × 10−5 と非常に小さい．つま

本稿における確率的データストリームを定める．まず，確率り，⟨a1 , b2 , b3 ⟩ は情報利得が大きい検出する価値のあるマッチ，的データストリームの構成要素となる確率的イベントを以下の⟨a2 , a3 , b4 ⟩ は情報利得が小さい検出する価値のないマッチだとように定める．

考えられる．また，⟨a1 , b2 ⟩ の持つ情報利得も大きいが，この［定義 1］ 確率的イベント et は，イベントの各属性値 α ∈ E

マッチが持つ情報は ⟨a1 , b2 , b3 ⟩ とほとんど重複している．そのに対して生起確率 P (et = α) を持つ時刻 t のイベントである．

ため，幾何平均などを用いる場合と違い，いずれか一つを検出

ただし，E はイベントの離散的なドメインであり，イベントのすれば十分であることも情報理論に基づいて推測できる．

生起確率 P (et = α) は以下を満たす．

本稿では，マッチの集合から得られる情報利得を定義し，パターン照合の結果として情報利得が最大となるマッチの集合を検出する手法を提案する．本稿の構成は以下のとおりである．
まず，2. で関連研究について述べた後，3. で入力となる確率的
データストリームの定義など，提案手法についての議論するた∀α ∈ E, 0 <= P (et = α) <= 1.
∀α, β ∈ E, α =| β → P (et = α ∧ et = β) = 0.
∑
P (et = α) = 1.

2

α∈Eめの準備を行う．4. ではマッチの集合を検出することで得られる情報利得を定義し，5. で適切なマッチの集合を検出するため

なお，これ以降 et = α は αt と略記する．確率的イベントを用のアルゴリズムについて述べる．最後に，6. で実験結果に基づいて確率的データストリームを以下のように定義する．

き提案手法を評価し，7. で本稿のまとめを述べる．

［定義 2］ 確率的データストリーム P DS = ⟨e1 , e2 , ..., en ⟩ は，

2. 関 連 研 究
確率的データストリームに対してパターン照合を行う手法はまだ少ない [8, 10, 16, 17]．[10] では，イベント生起の時間に対する相関（マルコフ過程）を考慮した確率的データストリーム

確率的イベントの系列である．各時刻のイベントの生起は独立であり，P DS 中の任意の異なる二つのイベント ei , ej に対して以下の式が成り立つ．

∀α, β ∈ E, P (αi ∧ βj ) = P (αi ) × P (βj ).

2

上でのパターン照合を行っている．しかし，求めているのは各

たとえば，図 1 はドメインが E = {a, b, c} である確率的デー

時刻でマッチが受理される確率のみであり，受理したマッチがタストリーム P DS = ⟨e1 , e2 , ..., e8 ⟩ として表せる．なお，本

いつ開始したのか，およびマッチが各時刻でいずれのイベント

稿では議論を簡潔にするために各時刻のイベントの生起が独立を選択したのかという情報は得られない．[8] では確率的デーであることを想定するが，本手法はイベントの生起に相関があ

タストリームに対し滑り窓を適用し，窓内で Top-k の生起確率

る場合にも拡張できる．

を持つマッチを検出する手法を提案している．ただし，断続的

次に，パターンの記述方法と対応するマッチを定める．まず，なイベントの生起を前提としているため，本稿で扱う連続的なパターンの記述方法を以下のように定める．

イベント生起やクリーネ閉包で表されるイベントの繰り返しを［定義 3］ パターンは確率的データストリーム中に含まれるイ

適当に検出できない．[16, 17] では生起時間が不確実なデータ

ベント α ∈ E といくつかの演算子を用いて記述する．演算子

ストリームに対するパターン照合手法を提案しているが，各イにはクリーネ閉包（∗ ,+ ），および優先順位を指定するための括

ベントの生起自体は確実な情報として考えられており，本稿で弧を使用する．

扱う確率的データストリームとは根本的に異なっている．

たとえば，ドメインが E = {a, b, c} であるとき，パターン2

非確率的データストリームに対するパターン照合は複雑な条⟨a+ (b c)∗ ⟩ はイベント a が一回以上生起した後に，b と c の連件を持つ問合せへの対応 [1] やイベントの生起頻度に基づいた

続した生起が任意の回数起きるという事象を表す．次に，マッ

効率的な照合の提案 [9] など，この十年で活発に議論されていチの定義を示す．

る [4, 5, 15]．また，近年では無限に続くデータストリームに対［定義 4］ マッチ m は指定されたパターンに適合するイベント

して正規表現に基づく曖昧なパターンの照合を行った際に，照の系列である．マッチの生起確率 P (m) は以下のように各イベ

合結果を一意に決定するためのセマンティクスについても提案ントの同時確率として定める．

が行われている [11]．しかし，前述したとおり確率的データス

4. 1 マッチ単体の情報利得イベント 生起確率0.3

情報利得は，ある事実を得たことで減少した情報量（エントb0.4

ロピー）を示す．事象 x の生起確率 Q(x) がある事実を得たこ

c

0.3とで P (x) になったとき，得られた情報利得 IG は次の式で表aせる．

図 2 図 1 に対応する確率モデル(
P (m) = P∧

IG = (− log Q(x)) − (− log P (x)) = log

)
α .

2

α∈m

P (x)
.
Q(x)

つまり，情報利得はある事実を得る前と得た後の確率の比から計算できる．また，事実を得たことで生起確率が大きくなった

たとえば，図 1 においてマッチ m = ⟨a1 , b2 , b3 ⟩ であれば，生とき正の情報利得が，小さくなったときには負の情報利得が得起確率 P (m) は以下のようになる．

られ，変化しないとき情報利得は 0 となる．
本稿では，事実を得る前の確率として確率モデルから推測

P (m) = P (a1 ∧ b2 ∧ b3 )されるマッチの生起確率を，事実を得た後の確率として実際の= 0.95 × 0.95 × 0.95

マッチの生起確率を用いる．あるマッチ m を検出したとき，得≃ 0.857.

られる情報利得 IG(m) を次の式で表す．

また，二つのマッチの生起が排反であるかないかを以下のように定義する．
［定義 5］ マッチ m1 , m2 の同時確率 P (m1 ∧ m2 ) が 0 のとき，

m1 , m2 の生起は排反であると呼ぶ．一方で，P (m1 ∧ m2 ) > 0のとき m1 , m2 の生起は排反でないと呼び，特に P (m1 ∧m2 ) =P (m1 ) × P (m2 ) が成り立つとき m1 , m2 の生起は独立であると2呼ぶ．

直感的には，ある時刻で異なるイベントの生起を示している
マッチは生起が排反となる．たとえば，m1 = ⟨a1 , b2 , b3 ⟩, m2 =

⟨a2 , b3 ⟩ は，時刻 2 で異なるイベントの生起を示しているため，生起が排反なマッチである．

IG(m) = log

P (m).
P M (m)つまり，実際の生起確率が確率モデルから予測される生起確率よりも大きいとき，正の情報利得が得られる．たとえば，m = ⟨a1 , b2 , b3 ⟩ の持つ情報利得 IG(m) は以下のようになる．
P (a1 ∧ b2 ∧ b3 )P M (a1 ∧ b2 ∧ b3 )0.95 × 0.95 × 0.95
= log
0.3 × 0.4 × 0.4

IG(m) = log≃ 4.16.
4. 2 マッチ集合の情報利得

最後に確率モデルを定める．確率モデルは，入力されるデー

マッチの集合が持つ情報利得を定める．まず，二つのマッチ

タストリーム中のイベントがどのような傾向で生起するかを示からなる集合の持つ情報利得について考え，次に三つ以上の場

す背景知識であり，定義自体は確率的イベントを定めた定義 1

合に拡張する．

と等しい．つまり確率モデルは，対象となる確率的データスト

4. 2. 1 二つのマッチが持つ情報利得

リーム中の確率的イベントが持つ確率分布の傾向を示している

マッチの集合が持つ情報利得を考える上で，マッチの生起がと言える．たとえば，図 2 は図 1 の確率的データストリームに排反であるかないかが重要となる．前節で示したとおり，マッ

対応する確率モデルの例である．マッチの生起確率を確率モデ

チが持つ情報利得はマッチの生起確率，つまりマッチを構成す

ルに基づいて考える場合，各イベントの生起確率として確率モる全イベントの同時確率で求められる．マッチが複数ある場合

デルが示す値を使用する．たとえば，マッチ m = ⟨a1 , b2 , b3 ⟩も同様に同時確率を用いればよいと考えられるが，二つのマッの確率モデル（図 2）に基づいた生起確率 P M (m) は以下のよチ m1 , m2 の生起が排反な場合，同時確率 P (m1 ∧ m2 ) およびうになる．

P M (m1 ∧ m2 ) は常に 0 であり情報利得を定義できない．そP M (m) = P M (a1 ∧ b2 ∧ b3 )こで，生起が排反でない二つのマッチからはパターンに適合するイベントが二回生起したという情報が，生起が排反な二つの= 0.3 × 0.4 × 0.4

マッチからはパターンに適合するイベントがいずれか一つだけ= 0.048.

生起したという情報が得られるものと考え，情報利得を定める．
まず，二つのマッチ m1 , m2 の生起が排反でない場合は，同4. マッチの情報利得

時確率 P (m1 ∧ m2 ) から情報利得を計算する．すなわち，パターンに適合するイベントが二回生起したという情報が得られマッチを検出することで得られる情報利得を定義する．まず，マッチ一つが持つ情報利得を定義し，次にマッチの集合が持つ情報利得を定める．なおこれ以降，特に記載がない限り対数のると考え，そのような事象が起きる確率から情報利得を求める．
生起が排反でないマッチ m1 , m2 の情報利得を，同時確率を用いて以下のように定める．

底には 2 を，確率的データストリームと確率モデルにはそれぞれ図 1，図 2 を用いる．

IG(m1 ∧ m2 ) = log

P (m1 ∧ m2 ).
P M (m1 ∧ m2 )

m1に適合するイベントの生起は最大で二回であり，マッチの生起

時刻

マッチ

1

2

3

a

b

b

a

b

m2

4

5

6

7

8

の組合せとして三つの候補が考えられることがわかる．言い換
えれば，これがマッチ集合 M を検出することで得られる情報bである．そこで，排反なマッチに対してそのいずれかが生起す

b

m3

a

a

b

る確率を用いて情報利得を定義したように，排反でないマッチ

m4

a

b

b

の集合のうちいずれかが生起する確率を用いて情報利得を定め

図 3 マッチ集合 M = {m1 , m2 , m3 }る．以下に，マッチの集合 M の情報利得 IG(M ) の式を示す．
なお，Ce (M ) は M の部分集合のうち排反でない極大なマッチ

たとえば，m1 = ⟨a1 , b2 , b3 ⟩, m2 = ⟨a5 , b6 ⟩ である場合，情報利得は以下のようになる．

P ((a1 ∧ b2 ∧ b3 ) ∧ (a5 ∧ b6 ))P M ((a1 ∧ b2 ∧ b3 ) ∧ (a5 ∧ b6 ))0.95 × 0.95 × 0.95 × 0.5 × 0.5= log
0.3 × 0.4 × 0.4 × 0.3 × 0.4

IG(m1 ∧ m2 ) = log≃ 5.22.
一方で，二つのマッチ m1 , m2 の生起が排反である場合は，いずれかのマッチが生起する確率 P (m1 ∨ m2 ) から情報利得

集合の全集合を表すとする．
∨∧
P ( Me ∈Ce (M ) ( m∈Me m))∨∧.
IG(M ) = log
P M ( Me ∈Ce (M ) ( m∈Me m))(1)

たとえば，図 3 のマッチ集合 M の場合，情報利得は以下のよ
うになる．

IG(M ) = log

P ((m1 ∧ m3 ) ∨ (m1 ∧ m4 ) ∨ m2 )P M ((m1 ∧ m3 ) ∨ (m1 ∧ m4 ) ∨ m2 )≃ 3.06.

を計算する．マッチの生起が排反である場合，二つのマッチがなお，(1) はこれまで述べてきた情報利得の式を一般化したも同時に生起することはなく，いずれかのマッチしか生起できなのであり，任意のマッチの集合に対して情報利得が計算できる．

い．したがって，パターンに適合するイベントとしていずれかのマッチが生起したという情報が得られると考える．生起が排反なマッチ m1 , m2 の情報利得を，いずれかのマッチが生起する確率を用いて以下のように定める．

IG(m1 ∨ m2 ) = log

P (m1 ∨ m2 ).
P M (m1 ∨ m2 )5. 情報利得に基づくパターン照合
情報利得に基いたマッチの検出手法について述べる．まず，問題定義について述べた後，マッチの集合を単純に検出する手法と，マッチの集合を一つの系列とみなして検出する手法について述べる．

たとえば，m1 = ⟨a1 , b2 , b3 ⟩, m2 = ⟨a2 , b3 ⟩ の場合，情報利得

5. 1 問 題 定 義は以下のようになる．

確率的データストリームに対するパターン照合の結果として

P ((a1 ∧ b2 ∧ b3 ) ∨ (a2 ∧ b3 ))P M ((a1 ∧ b2 ∧ b3 ) ∨ (a2 ∧ b3 ))0.95 × 0.95 × 0.95 + 0.03 × 0.95
= log
0.3 × 0.4 × 0.4 + 0.3 × 0.4

情報利得が最大となるマッチの集合を得ることを目指し，問題≃ 2.40.

ため，マッチ集合 {m2 }, {m1 , m2 } の持つ情報利得は等しい．

IG(m1 ∨ m2 ) = log

4. 2. 2 三つ以上のマッチが持つ情報利得マッチが三つ以上の集合について考える場合も，すべてのマッチが互いに排反でない（もしくは排反である）場合は同様に情報利得が計算できる．つまり，マッチ集合 M に対して，M 中の∧マッチが互いにすべて排反でなければ IG(M ) = IG( m∈M m)∨
で，互いにすべて排反であれば IG(M ) = IG( m∈M m) で情報利得を求められる．
問題は，排反なマッチと排反でないマッチがともに存在する場合である．たとえば，図 3 のマッチ集合 M であれば，m2 は他のすべてのマッチと，m3 , m4 はそれぞれ互いと生起が排反であり，他のマッチとの生起は排反でない．ここで，生起が排反でないマッチをそれぞれ集合 Ce = {{m1 , m3 }, {m1 , m4 }, {m2 }} にまとめたとき，集合単位で見ると Ce 中のマッチ集合の生起がすべて排反である点に注目する．たとえば，{m1 , m3 }, {m1 , m4 }は m3 と m4 の生起が排反であるため，これらの集合が同時に生起することはない．つまり，パターン照合の結果としてマッチ集合 M に含まれる四つのマッチを検出したとき，パターンを定義する．ただし，同じ情報利得を持つマッチ集合が複数存在する点に注意する．たとえば，マッチ m1 = ⟨a1 , b2 ⟩, m2 =

⟨a1 , b2 , b3 ⟩ であるとき，m1 ∧ m2 = m2 = a1 ∧ b2 ∧ b3 である
この点に注意して，本稿で扱う問題定義を以下に示す．
［定義 6］ 確率的データストリーム P DS ，パターン p，確率モ
デル P M が入力されたとき，得られる情報利得 IG(M ) が最大となるマッチの集合 M ⊂=Um を検出する．なお，Um は p でP DS に対してパターン照合を行った際に得られるマッチの全集合を表す．ただし，最大の情報利得を持つ集合が複数存在す
る場合はマッチの数が最も少ない集合を検出する．

2

情報利得が最大となるマッチの集合を検出することで，確率的データストリームから偏りなくマッチが検出できる．提案した情報利得を用いる場合，以下の定理 1 が成り立つことに注目する．なお，証明は付録に示す．
［定理 1］ マッチ集合 M を二分した集合 M1 , M2 (M1 ∪ M2 =M, M1 ∩ M2 = ∅) が以下の式を満たすとき，つまりマッチ集合の生起が独立なとき，情報利得 IG(M ) は各集合の情報利得の和 IG(M1 ) + IG(M2 ) で求められる．

∀m1 ∈ M1 , ∀m2 ∈ M2 , P (m1 ∧ m2 ) = P (m1 ) × P (m2 ). 2

定理 1 を用いることで，マッチの全集合 Um を互いに独立a.

な集合 Um1 , ..., Umk に分割したとき，Um の持つ情報利得は0

Σki=1 IG(Umi ) で表せる．したがって，情報利得が最大となる部分集合 M ⊂=Um を発見するという問題は，分割した各集合に

a

1

b
b

2

図 4 ⟨(. | a+ b+ )∗ ⟩ に対応する状態遷移図

おいて情報利得が最大となる部分集合 Mi ⊂=Umi を発見するという問題に等しい．マッチ集合の生起が独立であるかは生起しinitialた時間に依存するため，分割した各集合 Umi から情報利得が0最大となる部分集合 Mi を検出することで，確率的データスト
リームから満遍なくマッチが検出できる．

1

5. 2 複数のマッチを集合として検出する手法

t=1
.

0

a
a

1

b

分割統治法と幅優先探索を用いて最適解を発見する手法につ2

いて述べる．最も単純に考える場合，最適解は検出したマッチ

a

0

a
a

1

b

b

2

とで求められる．しかし，部分集合の数は検出されるマッチの
数 |Um | に対して O(2

a

b

t=3
.

…

1

b
b

2

2

状態

t

) で増加するため，単純にすべてを01

列挙するのは効率が悪い．そこで，定理 1 を用いて問題をいく

initial⟨⟩

つかの部分問題に分割する．上述したように，Um を生起が互

1

⟨.1 ⟩

⟨a1 ⟩

2

⟨.1 , .2 ⟩, ⟨a1 , b2 ⟩⟨.1 , a2 ⟩, ⟨a1 , a2 ⟩いに独立な集合 Um1 , ..., Umk に分割したとき，各集合で情報利得が最大となる部分集合 Mi ⊂=Umi を発見することで全体の情報利得も最大化できる．つまり，各集合 Umi の部分集合を幅優0

図 5 Viterbi アルゴリズムによる系列の検出の全集合 Um のすべての部分集合の持つ情報利得を計算するこ
|Um |

t=2
.

図6

2

⟨a1 , b2 ⟩t = 2 までの Viterbi アルゴリズムの処理過程（下線は各状態で最も情報利得が大きい系列を示す）

先で探索し，得た解の和集合を求めることで最適解が発見できる．分割後の各集合 Umi に対する探索は，頻出アイテム集合からの最尤系列の検出でよく知られる Viterbi アルゴリズム [6]を発見する手法である Apriori アルゴリズム [2] を参考に行う．

を用いることで実現できる．Viterbi アルゴリズムは動的計画

ただし，探索効率を上げるために以下の定理 2 を用いて探索空法の一種であり，現在時刻において状態遷移図の各状態に到達間の削減を行う．なお，定理の証明は付録に示す．

する最尤の系列を，一単位時刻前の状態から計算する．なお，［定理 2］ 情報利得が最大となるマッチ集合は，互いに生起が⟨(. | p)∗ ⟩ に対応する状態遷移図は以下の手続きによって得る．

2（ 1 ） Thompson 法 [12] を用いて，パターン p に対応する

つまり，Umi の部分集合 Mi を要素数 1 のものから探索したと

ϵ-遷移付きの非決定性有限オートマトン（ϵ-NFA）を生成する．

き，生起が排反なマッチを含む Mi およびその上位集合は探索（ 2 ） 生成した ϵ-NFA から ϵ-遷移を削除する．

排反でないマッチのみからなる．

空間から除外できる．
しかし，Um を k 個の集合に分割したとしても，探索する部（ 3 ） 初期状態に任意のイベント “.” による自身への遷移を，全受理状態に ϵ-遷移による初期状態への遷移を加え，受理分集合の総数は O(Σki=1 2|Umi | ) であり最悪の場合の計算量は大状態を初期状態のみにする．

きい．特に，パターンがクリーネ閉包を含む場合 |Umi | は多項

たとえば，p = ⟨a+ b+ ⟩ に対応する状態遷移図は図 4 のように

式関数的に増加するため，定理 2 を用いて探索空間を削減したなる．この状態遷移図に対して Viterbi アルゴリズムを適用し，としてもそのようなパターンに対して最適解を発見するのは困受理状態に到達した情報利得が最大となる系列を検出すること難である．そこで，次節ではマッチの集合を一つの系列としてで，情報利得が最大となるマッチの集合が得られる．

捉え，効率良く最適解を検出する手法について提案する．

例 と し て ，図 1 の 確 率 的 デ ー タ ス ト リ ー ム P DS ，p =5. 3 複数のマッチを一つの系列として検出する手法⟨a

マッチの集合を一つの系列とみなすことで最適解を検出するて考える．Viterbi アルゴリズムの処理は図 5 に示す図に基づ手法について述べる．定理 2 は，言い換えれば，任意のイベン

いて行われる．なお，生成した状態遷移図が ϵ-遷移を含むた

トを示す “.” を使うことで，情報利得が最大となるマッチの集め，同時刻における状態遷移が含まれる点に注意する．図 6 に合を一続きの系列で表せることを示す．たとえば，図 3 のマッ

t = 2 までに各状態に到達する系列の一覧を示す．まず，開始時

チ集合 M に対して情報利得が最大となる部分集合は {m1 , m3 }点（initial）では初期状態 0 のみが空の系列 ⟨⟩ を持つ．そのたであるが，これは一続きの系列 ⟨a1 , b2 , b3 , .4 , a5 , a6 , b7 , .8 ⟩ としめ，初期状態 0 からの遷移のみが実行され，t = 1 の時点では初て表せる．つまり，あるパターン p に対して情報利得が最大期状態 0 が系列 ⟨.1 ⟩ を，状態 1 が系列 ⟨a1 ⟩ を持つ．t = 1 からとなるマッチの集合を求めるという問題は，生起が排反でない

t = 2 への遷移は状態 0, 1 で行われ，初期状態 0 には ⟨.1 , .2 ⟩ が，マッチのみからなる系列を示すパターン ⟨(. | p)∗ ⟩ に適合する

状態 1 には ⟨.1 , a2 ⟩, ⟨a1 , a2 ⟩ が，状態 2 には ⟨a1 , b2 ⟩ が到達する．

系列の中で，情報利得が最大となる系列を求める問題として考さらに，ϵ-遷移によって状態 2 に到達した系列 ⟨a1 , b2 ⟩ が初期状えられる．

態 0 にも到達する．最終的に t = 2 の時点で状態 0, 1 にそれぞ⟨(. | p)∗ ⟩ に適合する系列の情報利得の最大化は，状態遷移図+b+ ⟩，図 2 の確率モデル P M が入力された場合についれ二つの系列が到達するが，⟨a1 , b2 ⟩ は ⟨.1 , .2 ⟩ よりも，⟨a1 , a2 ⟩

マッチを示す．
0.8

0.8
0.2

a
y : 0.05
z : 0.20
a : 0.50
b : 0.20
c : 0.05bz : 0.05
a : 0.20
b : 0.50
c : 0.20
d : 0.05

0.2
0.2

…

0.2

0.8

Pgeo (ml ) = (Pgeo (ml−1 ))l−1/l × (P (αl ))1/l .

z
x : 0.05
y : 0.20
z : 0.50
a : 0.20
b : 0.05

図 7 人工データ生成に使用したマルコフモデル

漸化式はマッチにイベントを追加したときの幾何平均の変化がl が大きくなるほど小さくなることを示している．したがって，
Viterbi アルゴリズムにおいて幾何平均の上下関係が保証されるのは，状態遷移図の同じ状態で同じ長さ l を持つマッチの集合のみであることを示す．

6. 1 検出性能の評価
は ⟨.1 , a2 ⟩ よりも情報利得が大きいため，各状態で情報利得の大提案手法により検出されるマッチを評価する．性能の評価にきい系列一つのみが保持される．同様の処理は t = 3 以降も行は適合率，再現率，F 値の三つを用いる．適合率は一般に，検われ，t = 8 の時点で受理状態 0 には ⟨a1 , b2 , b3 , .4 , a5 , a6 , b7 , .8 ⟩出結果集合 M が含む正解データ集合 C の割合を示し，検出のが保持される．したがって，情報利得が最大となるマッチの集合

正確性を表す．しかし，確率的なパターン照合において検出結は，この系列に含まれる二つのマッチ {⟨a1 , b2 , b3 ⟩, ⟨a5 , a6 , b7 ⟩}果と正解データが完全に一致することは稀であるため，単純にとなる．

適合率を計算した場合ほとんど 0 になってしまう．そこで，検6. 評 価 実 験

出結果と正解データの類似度を基に適合率を考える．たとえば，

sim(m, c) を検出結果 m ∈ M と正解データ c ∈ C が完全一致実験により提案手法を評価する．実データを用いて提案手法

するときのみ 1，それ以外の場合 0 となる類似度の関数とし，によって検出されるマッチの有効性を，人工データを用いて処検出結果 m の正解データ集合 C に対する類似度を各正解デー

理速度を評価する．まず，実験で使用したデータセットと比較

タに対する類似度の最大値 max(sim(m, c)|c ∈ C) とする．こ

手法について述べる．

のとき，一般的な適合率は，検出結果集合から無作為に選んだ

実データには Lahar プロジェクト [10] で公開されている屋内検出結果が持つ類似度の期待値として以下のように表せる．な

位置の確率的データストリームを使用した．このデータは屋内

お，P (m, M ) は m が無作為抽出時に選ばれる確率であり，一構造をグラフで表しており，被験者が各ノードにいる確率と実

般的な適合率では 1/|M | が用いられる．

際に被験者がいた正解ノードの情報を一秒ごとに持つ．実験では 797 秒間のデータ，つまり 797 個のイベントからなる確率的
データストリームを入力として使用した．また，被験者はある
部屋への入退出を繰り返し行っているため，部屋の中にいることを Room で，部屋の扉付近にいることを Door で，部屋のすぐ外の廊下にいることを Hall で表しパターンを記述する．人工
データは，26 個のイベントからなるドメイン E = {a, b, ..., z}に対し図 7 のマルコフモデルを設計し，このモデルに基づいてデータを生成した．なお，いずれのデータセットにおいても背景知識となる確率モデル P M には一様分布を使用した．

precision(M, C) =を用いる．なお，k の値には提案手法により検出されたマッチ

P (m, M )×max(sim(m, c)|c ∈ C).

m∈M

つまり，無作為抽出時にマッチが選ばれる確率 P (m, M ) と正
解データとの類似度 sim(m, c) を定めることで適合率は計算できる．本稿では以下のように，P (m, M ) にはマッチの各指標（情報利得・生起確率・幾何平均）の大きさに基づいた値を，sim(m, c) にはマッチの時間的な重複の度合いを用いる．なお，
m.ts , m.te でマッチの開始時刻と終了時刻を表す．
P (m, M ) = ∑比較手法として，マッチの生起確率に基づく Top-k 問合せと，各イベントの生起確率の幾何平均に基づく Top-k 問合せの二つ∑

sim(m, c) =IG(m)′m′ ∈M IG(m ).

min(m.te , c.te ) − max(m.ts , c.ts ) + 1.
max(m.te , c.te ) − min(m.ts , c.ts ) + 1の数を用い，マッチ m = ⟨α1 , ..., αl ⟩ の幾何平均 Pgeo (m) は以

再現率は検出された正解データの割合であり，検出の網羅性を下の式で定める．

表す．再現率も，適合率の場合と同様に，正解データ集合から

Pgeo (m) = (l∏

無作為に選んだ正解データが持つ類似度の期待値として以下のP (αi ))1/l .

i=1ように表せる．なお，検出結果を無作為抽出する場合と違い，
正解データの無作為抽出は常に一様分布に従う点に注意する．

生起確率・幾何平均ともに，Top-k 問合せの解は Viterbi アル
ゴリズムを拡張することで求められる．生起確率に基づく場合
は，Thompson 法によって構築された NFA 上での Viterbi ア
ルゴリズムにおいて，保持するマッチの数を一個から k 個にrecall(M, C) =∑ 1
× max(sim(c, m)|m ∈ M ).
|C|c∈C

F 値は適合率と再現率の調和平均であり，検出の全体的な性能

拡張することで実装できる．一方，幾何平均では NFA の各状を表す．本稿では適合率と再現率を一対一の割合で評価し，F態で異なるマッチの長さ l 毎に k 個のマッチを保持する必要が値を以下の式で計算する．

ある．これは，幾何平均が以下のような漸化式で表せるためである．なお，ml−1 は ml から末尾のイベント αl を取り除いたF -measure(M, C) =2 × precision(M, C) × recall(M, C).
precision(M, C) + recall(M, C)

1

提案手法

1,000,000
Top-k (生起確率)

0.6
0.4
0.2

100,000
10,000
1,000
100

0
適合率

再現率

10

F値

1

図 8 p = ⟨Room+ Door+ Hall+ ⟩ に対する適合率・再現率・F 値
図 10
1

提案手法

0.8

Top-k (生起確率)

提案手法
Top-k（生起確率）
Top-k（幾何平均）

Top-k (幾何平均)

実行時間 [ms]

0.8

6

11
16
21
|p| : パターンの長さ26パターンの長さ |p| を変化させた際の実行時間

Top-k (幾何平均)

100,000

0.4
0.2
0
適合率

再現率

F値

実行時間 [ms]0.6

10,0001,000100

図 9 p = ⟨Room+ ⟩ に対する適合率・再現率・F 値

図 8 に ⟨Room+ Door+ Hall+ ⟩ を 入 力 し た 際 の ，図 910110,000

図 11

提案手法
Top-k（生起確率）
Top-k（幾何平均）

40,00070,000|PDS| : イベント数 [個]100,000

イベント数 |P DS| を変化させた際の実行時間に ⟨Room ⟩ を 入 力 し た 際 の 実 験 結 果 を 示 す．な お ，+⟨Room+ Door+ Hall+ ⟩ を入力したとき正解データ 9 個に対化させた際の実行時間を図 10 に示す．パターンの長さは，して 18 個のマッチが，⟨Room+ ⟩ を入力したとき正解データ 9⟨a+ ⟩, ⟨a+ b+ ⟩ のように，ドメイン E 中のイベントを順に追加個に対して 23 個のマッチが提案手法で検出されたため，それぞすることで調整している．なお，確率的データストリームのイ

れを k の値として用いている．結果から，提案手法は適合率・ベント数は 50, 000 とし，実行時間が 1, 000 秒を超えるような再現率・F 値すべてにおいて優れていることがわかる．これは，結果は図から省略した．また，提案手法ではマッチが 376 個検

各 Top-k 問合せで検出されるマッチが偏っているのに対し，提出されるため，各 Top-k 問合せも k = 376 で実行している．結案手法では適当なマッチを満遍なく検出できているためであ果から，Top-k 問合せに基づく手法の実行時間が大きく増加しる．マッチの生起確率は定義 4 で表されるため，生起確率の大ているのに対し，提案手法の実行時間の増加が緩やかであるこきさに注目すると乗算回数の少ない短いマッチ，今回の実験でとがわかる．これは，パターンの長さが大きくなり状態遷移図

は生起時間が 3–5 秒ほどのマッチばかりが検出される．実際のにおける状態数が増加したときに，Top-k 問合せでは保持しな

正解データは 20–40 秒ほどにわたって生起しているため，適合ければならないマッチ数が大きく増加するのに対し，提案手法率が非常に小さくなる．また，生起確率に注目する場合，ノイでは状態数と同じ個数の系列のみを保持すればよいためである．

ズによって生起確率が下がっている区間のマッチも検出されに本章のはじめで述べたとおり，生起確率に基づく Top-k 問合せ

くいため，再現率も小さい．幾何平均ではマッチを構成するイ

では各状態ごとに k 個のマッチを，幾何平均に基づく Top-k 問

ベントの生起確率の平均的な高さに注目するため，マッチの生合せでは各状態で各マッチの長さ l 毎に k 個のマッチを保持し，起確率にのみ注目する場合よりも適合率は高くなる．しかし，次状態への遷移処理を行わなければならない．つまり，単純に⟨Room+ ⟩ などの単純なパターンが入力された場合，⟨Roomi ⟩ な

考えて各 Top-k 問合せでは提案手法の k ないし kl 倍の処理がどのイベント一つから構成されるマッチの幾何平均が最も大き必要となるため，このような実行時間の差が生まれている．なくなるため，適合率が非常に小さくなる．また，マッチの生起

お，図 10 ではパターンが短いときそれほど大きな差が開いて確率を用いた場合と同様，ノイズの大きい区間のマッチがほといないが，これはパターンが単純なとき一度に生成されるマッんど検出されないため再現率は小さい．一方で，提案手法で用チの数が k 個未満であることが原因である．そのため，パター

いるマッチの情報利得は，各イベントの生起確率が大きければンが長くなり一度に生成されるマッチの数が増えるにつれ，実マッチが長いほど大きくなる．そのため，正解データとの類似

行時間の差が予測されたものに近づいていく．

度が大きいマッチが検出されやすく，適合率が高い．また，5.

次に，入力となる確率的データストリームの持つイベント数で述べたとおり，マッチ集合の情報利得を最大化するときマッ|P DS| を 10, 000 から 100, 000 まで変化させた際の実行時間

チが存在する可能性のある区間すべてからマッチが検出されるを図 11 に示す．なお，入力パターンには ⟨a+ b+ c+ ⟩ を使用

ため，再現率も高い．

している．結果から，いずれの手法においてもイベント数の増

6. 2 処理速度の評価

加に対する実行時間の増加が緩やかであることがわかる．これ提案手法の処理速度を評価する．評価は，入力した確率的は，データストリームのイベント数が Viterbi アルゴリズムにデータストリームからマッチをすべて検出するまでにかかる実おける更新回数にしか影響を及ぼさないためである．つまり，

行時間に基づいて行う．

Viterbi アルゴリズムに基づいた手法においてイベント数の増

まず，入力となるパターンの長さ |p| を 1 から 26 まで変加が実行時間に与える影響は小さく，提案手法が多数のイベン

トからなるデータストリームにも適用可能であることを示している．

7. お わ り に
本稿では，確率的データストリーム上でのパターン照合において，検出したマッチの新たな評価指標として情報利得を提案した．検出したマッチの集合が持つ情報利得を定義し，Viterbi
アルゴリズムに基づいて効率的に解を検出する手法を提案した．
また，実データを用いた実験によって提案手法により検出されstreams. In Proc. ACM SIGMOD, pages 159–170, 2010.
[15] E. Wu, Y. Diao, and S. Rizvi. High-performance complex
event processing over streams. In Proc. ACM SIGMOD,
pages 407–418, 2006.
[16] H. Zhang, Y. Diao, and N. Immerman. Recognizing patterns in streams with imprecise timestamps. Proc. VLDB
Endow., 3(1-2):244–255, 2010.
[17] H. Zhang, Y. Diao, and N. Immerman. On complexity andoptimization of expensive queries in complex event processing. In Proc. ACM SIGMOD, pages 217–228, 2014.
[18] Q. Zhang, F. Li, and K. Yi. Finding frequent items in probabilistic data. In Proc. ACM SIGMOD, pages 819–832, 2008.

るマッチが既存の評価指標（生起確率・幾何平均）に基づいた付

場合よりも優れていることを示し，人工データを用いた実験によって実行時間においても優れていることを示した．
今後の課題としては，パターンの記述における選言演算子への対応，入力イベントが動的に追加される確率的データスト

録

定理 1 の証明∨(1) で示したように，M の情報利得を求めるための事象は∧Me ∈Ce (M ) ( m∈Me m) で表せる．Me ∈ Ce (M ) は排反でなリームのための連続的問合せへの拡張が挙げられる．また，現いマッチの組合せであるため，定理内で示した M1 , M2 が存在

在は確率的データストリームの情報源が一つであることを想定するとき，Ce (M ) は直積を用いて Ce (M1 ) × Ce (M2 ) で表せしているが，複数情報源への拡張も今後の課題である．

る．したがって，分配法則を用いて適当に式変形することによ文

献[1] J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. Efficient pattern matching over event streams. In Proc. ACM
SIGMOD, pages 147–160, 2008.
[2] R. Agrawal and R. Srikant. Fast algorithms for mining association rules in large databases. In Proc. VLDB, pages
487–499, 1994.
[3] L. Chen, C. Nugent, and H. Wang. A knowledge-driven
approach to activity recognition in smart homes. IEEE
TKDE, 24(6):961–974, 2012.
[4] G. Cugola and A. Margara. Processing flows of information: From data stream to complex event processing. ACM
Comput. Surv., 44(3):15:1–15:62, 2012.
[5] A. Demers, J. Gehrke, and B. Panda. Cayuga: A general
purpose event monitoring system. In Proc. CIDR, pages
412–422, 2007.
[6] G. D. Forney, Jr. The viterbi algorithm. Proceedings of theIEEE, 61(3):268–278, 1973.
[7] C. Jin, K. Yi, L. Chen, J. X. Yu, and X. Lin. Sliding-window
top-k queries on uncertain streams. Proc. VLDB Endow.,
1(1):301–312, 2008.
[8] Z. Li, T. Ge, and C. X. Chen. ε-matching: Event processing
over noisy sequences in real time. In Proc. ACM SIGMOD,
pages 601–612, 2013.
[9] Y. Mei and S. Madden. ZStream: A cost-based query processor for adaptively detecting composite events. In Proc.
ACM SIGMOD, pages 193–206, 2009.
[10] C. Ré, J. Letchner, M. Balazinska, and D. Suciu. Eventqueries on correlated probabilistic streams. In Proc. ACM
SIGMOD, pages 715–728, 2008.
[11] S. Santini. Querying streams using regular expressions:some semantics, decidability, and eﬃciency issues. The
VLDB Journal, 24(6):801–821, 2015.
[12] K. Thompson. Programming techniques: Regular expression search algorithm. Commun. ACM, 11(6):419–422,
1968.
[13] T. T. L. Tran, A. McGregor, Y. Diao, L. Peng, and A. Liu.
Conditioning and aggregating uncertain data streams: Going beyond expectations. Proc. VLDB Endow., 3(1-2):1302–
1313, 2010.
[14] T. T. L. Tran, L. Peng, B. Li, Y. Diao, and A. Liu. PODS:
A new model and processing algorithms for uncertain dataり，以下の式が導ける．



∨
∧

P
m  =Me ∈Ce (M )


P 

m∈Me



∨



Me ∈Ce (M1 )

∧





m ∧ m∈Me∨

Me ∈Ce (M2 )




∧


m .

m∈Me

M1 , M2 が定理内で示した式を満たす（生起が互いに独立である）ことを考慮すると，マッチ集合 M の情報利得の式は以下のように変形できる．なお，簡略化のため各積和事象は対応するマッチの集合で表す．

IG(M ) = log

P (M1 ∧ M2 )P M (M1 ∧ M2 )= log

P (M1 ) × P (M2 )P M (M1 ) × P (M2 )= log

P (M1 )P (M2 )+ log
P M (M1 )P M (M2 )= IG(M1 ) + IG(M2 ).

2

定理 2 の証明(1) に し た がって 情 報 利 得 を 計 算 す る と き ，マッチ 集 合Me ∈ Ce (M ) は互いに生起が排反であるため，対数内の式∧
は以下のように表せる．なお， m∈Me m を Me で表す．
∨
P ( Me ∈Ce (M ) Me )
ΣMe ∈Ce (M ) P (Me )∨=.
P M ( Me ∈Ce (M ) Me )
ΣMe ∈Ce (M ) P M (Me )この式の示す値が最大となるとき情報利得も最大となるが，ここで以下の式が成り立つことに注目する．

xx′xx + x′x′x x′< ′ → <<.
∀ , ′ ∈ R,
y y
y
y
y
y + y′y′
つまり，生起が互いに排反な集合 Me ∈ Ce (M ) を複数検出す
るよりも，最も情報利得の大きい Me のみを検出する方が情報
利得は大きい．すべての Me には生起が排反でないマッチしか含まれないため，情報利得が最大となるマッチ集合には生起が排反なマッチは含まれない．

2