Sequential data analysis, a relatively young and interdisciplinary field of computer science, is the process of extracting patterns from large sequence data sets by combining methods from statistics and artificial intelligence with database management.

With recent tremendous technical advances in processing power, storage capacity, and Internet, sequential data analysis is seen as an increasingly important approach by modern business. This is because it can give an informational advantage by transforming unprecedented quantities of sequence data into business intelligence. It is currently used in a wide range of profiling practices, such as marketing, surveillance, fraud detection, and scientific discovery. Since sequential data analysis can bring real value for real applications, demand for novel technologies in sequential data analysis is growing these days.

The Hidden Markov Model (HMM) is a ubiquitous tool for representing probability distributions over sequences of observations. The basic theory of HMM was developed in the late 1960s. Since HMMs, which assess sequential data as sequences of state transitions, are robust against noise, significant applications that use HMMs have emerged, including sequence labeling, speech recognition, mental task classification, biological analysis, traffic monitoring, and anomaly detection. This thesis mainly handles three research problems; The first problem is exact and efficient states sequence detection for single HMM and static sequence of arbitrary length, and the second problem is efficient identification of the model whose state sequence has the highest likelihood for the given query sequence, exactly (i.e., an HMM that actually has a high-probability path for the given sequence is never missed by the algorithm.). The third problem is efficient monitoring of streaming data sequences to find the best model without exception. And, to show the generality of the proposed approach for other data structure, I applied the proposed approach for the problem to monitoring best centrality nodes of time-evolving graphs.

I propose Staggered decoding for the first problem, SPIRAL for the second and third problem, and Sniper for the fourth problem. The proposed approach is based on two ideas; approximation and pruning. Approximation is an idea that aggregates several state to discard unlikely states or models. And pruning is an idea that computes exact likelihood of viable states/models by pruning unlikely state transition. The proposed approach has the following attractive characteristics:

-High-speed: Solutions based on previous approaches are prohibitively expensive for large HMM data. The proposed approach uses carefully designed approximations to efficiently identify the most likely model.

-Exact: The proposed approach does not sacrifice accuracy; it returns the highest likelihood model without any omission.

-Applicability: The proposed approach can be applied not only for HMM but other data structures such as time-evolving graphs.

In order to achieve high performance and to find the exact answer, the proposed approach first prunes many states/models with approximate likelihoods at low computation cost. The exact likelihood computations are limited to the minimum necessary, which yields a dramatic reduction in the total search cost. Experiments compared the proposed method with the method based on the previous approaches. As expected, the experiments demonstrate the superiority of the proposed approach.

本論文は「Efficient Sequence Data Analysis with Hidden Markov Models(隠れマルコフモデルによる高速な系列データの解析手法)」と題し、英文7章から構成されている。自然言語処理、バイオインフォマティクス、音声認識等の系列データの解析に広く用いられている隠れマルコフモデル(HMM)の復号には、最適解を与えるビタビアルゴリズムや、様々な近似アルゴリズムが適用されているが、ビタビアルゴリズムは状態数やデータ量の大きい問題に対して非効率であり、近似アルゴリズムには誤り限界を保証できないという問題点が存在する。本論文では、HMMの復号、モデル選択、ストリームモニタリングという3つの問題設定において、複数の状態をまとめ上げた粗粒度の状態遷移における近似尤度を算出し、最適の尤度を取り得ないパスやモデルを効果的に枝刈りする手法を提案し、ビタビアルゴリズムより高速に最適解を求められることを示している。

第1章は、「Introduction(序章)」であり、本論文の背景および目的について概観し、本論文の構成を述べている。

第2章は、「Preliminary and Related Work(基本事項及び関連研究)」と題し、隠れマルコフモデル及びビタビアルゴリズムの基本的な解説を行い、その高速化及び応用に関する関連研究をまとめている。

第3章は、「Efficient Likelihood Computation for HMM(HMMのための効率的な尤度計算手法)」と題し、単一のHMMを高速かつ最適に復号するアルゴリズムを提案している。本アルゴリズムは縮退ラティスと呼ばれるデータ構造を用いて効果的な枝刈りを行うものである。自然言語処理における系列ラベリングタスクによる評価実験を行い、ビタビアルゴリズムと比較して最大で約400倍の高速化が可能であることを示している。

第4章は、「Efficient Search Method for HMM Data Set(HMMデータセットの効率的な探索手法)」と題し、与えられたデータ系列に対し、多数のHMMから最大の尤度を持つモデルを効率的に探索するアルゴリズムを提案している。ゲノムデータ、DNAデータ、交通量データ等を用いた評価実験を行い、提案アルゴリズムが、状態数、モデル数の大きな問題に対し、ビタビアルゴリズムと比較して数十から数百倍高速であることを示した。

第5章は、「Fast Data Stream Monitoring with HMM Data Set(HMMデータセットを用いた高速なデータストリームモニタリング手法)」と題し、与えられたデータストリームをモニタリングし、多数のHMMから最近のウィンドウ幅のデータ系列に関して最も尤度の高いモデルを効率的に探索する手法を提案している。DNAデータ、交通量データ等を用いた評価実験を行い、状態数、モデル数の大きな問題に対し静的な解法及びビタビアルゴリズムと比較して、数十から数百倍高速であることを示した。

第6章は、「Efficient Centrality Monitoring for Time-evolving Graphs(時系列グラフグラフにおける効率的な中心性モニタリング手法)」と題し、これまでに提案してきた高速なHMMアルゴリズムが、時間によって変化する時系列グラフのモニタリング問題に対しても有効であることを示している。変化するグラフをモニタリングし、中心性と呼ばれる尺度の計算を更新し続ける問題に対して、これまでと同様の縮退、枝刈りの手法を適用したアルゴリズムを提案している。P2Pネットワーク、ソーシャルネットワーク、Webのリンク構造を用いた評価実験を行い、10万から50万ノード規模のグラフにおいて既存手法と比較して最大で約100倍の高速化が可能なことを示している。

第7章「Conclusions(結論)」では、本論文の成果と今後の課題について総括している。

以上これを要するに、本論文は、隠れマルコフモデルを用いた復号、モデル選択、及びストリームモニタリング問題に対して、最適解を保証しながらビタビアルゴリズムよりも高速なアルゴリズムを構築する手法を提案するものであり、様々な実データを用いた評価実験によりその有効性を明らかにすると共に、同様の手法が時系列グラフの中心性モニタリングにも適用可能であることを示しており、情報理工学上貢献するところが少なくない。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。