杉浦 健人 名古屋大学 大学院情報学研究科 研究員 |
[背景]不確実な情報を表す確率的データストリームが増加
[問題]パターン照合におけるクリーネ閉包(連続的なイベント生起の検出)への非対応
[貢献]クリーネ閉包を考慮したパターン照合手法の提案
[問題]パターン照合におけるクリーネ閉包(連続的なイベント生起の検出)への非対応
[貢献]クリーネ閉包を考慮したパターン照合手法の提案
確率的データストリームは各時刻におけるイベントの生起を離散確率分布で表すデータストリームであり,機械学習による解析結果など,本質的に不確実性を含むデータの有効な表現方法である.近年の機械学習の発達により,スマートフォンのセンシングデータを用いた人の行動モニタリング,監視カメラやドローンの映像を用いた異常イベント検知,サーバログを用いたシステムの状態分析など,機械学習によるイベントの検知(分類)は幅広く行われている.一方で,分類手法の限界やデータ自体のノイズにより,十分な分類精度が得られないことも多い.このような場合,ある1つの分類結果を選ぶよりも,各イベントの生起を確率的に表す方がより正確にイベントの分類結果を表現できる.
本研究では,確率的データストリームから検出したいイベントが正規表現パターンとして与えられることを想定し,確率的データストリームにおける正規表現パターンの照合に取り組んでいる.たとえば,人の行動ログであれば,<(run+ jog+)*>のような正規表現パターンを与えトレーニング(ランニングとジョギングの繰返し)をしている期間の検出を行う.確率的データストリームに対するパターン照合の課題は,先ほどの例でも使用したクリーネ閉包(* or +)である.クリーネ閉包は指定したイベントの0回もしくは1回以上の繰返しを表し,正規表現を構成する重要な要素の1つである.しかし,情報が不確実な確率的データストリームでは多数かつ冗長な照合結果を生成する原因となり,既存研究では実質的に無視されている.つまり,既存研究では複数の時刻にまたがって生起する連続的なイベントを検出できず,単発もしくは飛び飛びなイベントの検出しか行えない.
そこで,本研究では確率的データストリームにおける正規表現パターン照合のために,クリーネ閉包を含む問合せパターンであっても適切に照合可能な手法を提案した.具体的には,1)冗長な照合結果のグループとしての集約,および2)情報理論に基づく指標の定義による適切な照合結果の検出の2つの手法を提案した.1)では,冗長な照合結果を時間的な重複に基づき集約し,照合結果のグループとして出力している.また,グループに対して適切な生起確率を付与することで,照合結果を個別に扱う場合よりも検出精度が向上することを確認した.2)では,照合結果の生起確率を用いた比較では適切な照合結果が得られないことを示し,照合結果の相対的な尤度を表す指標を情報理論に基づき定義した.また,既存の照合セマンティクスに基づき照合アルゴリズムを考案し,提案した指標に基づくTop-kの照合結果を効率よく検出する手法を提案した.
今後は,確率的データストリームからの正規表現パターンの自動抽出(マイニング)や,確率的データストリームのためのインデックス構築など,確率的データストリームからの知識発見に取り組む予定である.
本研究では,確率的データストリームから検出したいイベントが正規表現パターンとして与えられることを想定し,確率的データストリームにおける正規表現パターンの照合に取り組んでいる.たとえば,人の行動ログであれば,<(run+ jog+)*>のような正規表現パターンを与えトレーニング(ランニングとジョギングの繰返し)をしている期間の検出を行う.確率的データストリームに対するパターン照合の課題は,先ほどの例でも使用したクリーネ閉包(* or +)である.クリーネ閉包は指定したイベントの0回もしくは1回以上の繰返しを表し,正規表現を構成する重要な要素の1つである.しかし,情報が不確実な確率的データストリームでは多数かつ冗長な照合結果を生成する原因となり,既存研究では実質的に無視されている.つまり,既存研究では複数の時刻にまたがって生起する連続的なイベントを検出できず,単発もしくは飛び飛びなイベントの検出しか行えない.
そこで,本研究では確率的データストリームにおける正規表現パターン照合のために,クリーネ閉包を含む問合せパターンであっても適切に照合可能な手法を提案した.具体的には,1)冗長な照合結果のグループとしての集約,および2)情報理論に基づく指標の定義による適切な照合結果の検出の2つの手法を提案した.1)では,冗長な照合結果を時間的な重複に基づき集約し,照合結果のグループとして出力している.また,グループに対して適切な生起確率を付与することで,照合結果を個別に扱う場合よりも検出精度が向上することを確認した.2)では,照合結果の生起確率を用いた比較では適切な照合結果が得られないことを示し,照合結果の相対的な尤度を表す指標を情報理論に基づき定義した.また,既存の照合セマンティクスに基づき照合アルゴリズムを考案し,提案した指標に基づくTop-kの照合結果を効率よく検出する手法を提案した.
今後は,確率的データストリームからの正規表現パターンの自動抽出(マイニング)や,確率的データストリームのためのインデックス構築など,確率的データストリームからの知識発見に取り組む予定である.
(2018年5月31日受付)