(57)【要約】【課題】新たにシーケンスが入力された場合に、計算時間とメモリ使用量とを削減して、階層構造の隠れマルコフモデルを更新することができるようにする。【解決手段】入力されたシーケンスについて、最上層のＨＭＭから最下層のＨＭＭまでＨＭＭを選択して、選択された最下層のＨＭＭに入力されたシーケンスを挿入すると共に、重みを求める（Ｓ１０３）。新たなシーケンスのための空きがない場合、選択されたＨＭＭを、２つのＨＭＭに分割すると共に、選択されたＨＭＭに属する１つ下の層の複数のＨＭＭ、又は選択されたＨＭＭに属する複数のシーケンスを、分割された２つのＨＭＭに割り振り（Ｓ１０６）、分割された２つのＨＭＭの各々のパラメータを推定する（Ｓ１０９）。分割された２つのＨＭＭが最下層のＨＭＭであって、シーケンスのＨＭＭに対する尤度に基づく値が、不適切な値であると判定される場合（Ｓ１１１）、シーケンスを再挿入する（Ｓ１１３）。【選択図】図４
2014016731.tif 000002
【特許請求の範囲】
【請求項１】
階層構造で定められた複数の隠れマルコフモデル（ＨＭＭ）の各々のパラメータ、及び最下層のＨＭＭの少なくとも１つに属し、かつ、属する最下層のＨＭＭの各々に対する重みが付された複数のシーケンスを記憶する記憶手段と、
入力されたシーケンスについて、階層構造に従って、最上層のＨＭＭから最下層のＨＭＭまで、各ＨＭＭに対する尤度に基づいて前記ＨＭＭを選択して、前記入力されたシーケンスが属する少なくとも１つの最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記入力されたシーケンスを挿入すると共に、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みを求めるシーケンス挿入手段と、
前記シーケンス挿入手段によって選択された最上層のＨＭＭから最下層のＨＭＭまでの各ＨＭＭについて、新たなシーケンスのための空きがある場合、前記選択された前記ＨＭＭのパラメータを、前記入力されたシーケンスに基づいて更新する更新手段と、
前記シーケンス挿入手段によって選択された最上層のＨＭＭから最下層のＨＭＭまでの各ＨＭＭについて、新たなシーケンスのための空きがない場合、前記選択された前記ＨＭＭを、２つのＨＭＭに分割すると共に、前記選択されたＨＭＭに属する１つ下の層の複数のＨＭＭ、又は前記選択されたＨＭＭに属する複数のシーケンスを、分割された２つのＨＭＭに割り振る分割手段と、
前記分割手段によって分割された２つのＨＭＭの各々のパラメータを、前記ＨＭＭに割り振られたＨＭＭの配下のシーケンス、又は前記ＨＭＭに割り振られたシーケンスに基づいて推定する推定手段と、
前記分割手段によって分割された２つのＨＭＭが最下層のＨＭＭであって、前記最下層のＨＭＭに属するシーケンスの前記ＨＭＭに対する尤度に基づく値が、閾値と比較して不適切な値であると判定される場合、前記シーケンスを、前記最下層のＨＭＭに属するシーケンスから削除して、前記シーケンスに対応する前記最下層のＨＭＭから最上層のＨＭＭまでの各ＨＭＭのパラメータを更新すると共に、前記シーケンスについて、階層構造に従って、最上層のＨＭＭから最下層のＨＭＭまで、各ＨＭＭに対する尤度に基づいて前記ＨＭＭを選択して、前記シーケンスが属する少なくとも１つの最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記シーケンスを再挿入すると共に、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みを求めるシーケンス再挿入手段と、
を含むデータ更新処理装置。
【請求項２】
前記分割手段によって前記選択されたＨＭＭが２つのＨＭＭに分割された場合に、前記分割された２つのＨＭＭの各々について、階層構造に従って、前記分割されたＨＭＭから最下層のＨＭＭまで、前記ＨＭＭに属する１つ下の層のＨＭＭ又は前記ＨＭＭに属するシーケンスをサンプリングにより選択するサンプリング手段を更に含み、
前記推定手段は、前記分割手段によって分割された２つのＨＭＭの各々のパラメータを、前記サンプリング手段により選択された前記ＨＭＭの配下のシーケンスに基づいて推定する請求項１記載のデータ更新処理装置。
【請求項３】
前記更新手段は、前記シーケンス挿入手段によって選択されたＨＭＭの各々について、新たなシーケンスのための空きがある場合、前記選択されたＨＭＭのパラメータを、前記入力されたシーケンスのみに基づいて更新する請求項１又は２記載のデータ更新処理装置。
【請求項４】
前記シーケンス挿入手段は、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みの合計値が閾値を超えるまで、前記入力されたシーケンスについて、最上層のＨＭＭから最下層のＨＭＭまで前記ＨＭＭを選択して、前記入力されたシーケンスが属する最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記入力されたシーケンスを挿入することを繰り返す請求項１〜請求項３の何れか１項記載のデータ更新処理装置。
【請求項５】
前記入力されたシーケンスが挿入された結果、前記ＨＭＭの配下の全てのシーケンスに付された重みの合計値が閾値以上である場合に、新たなシーケンスのための空きがないと判断される請求項１〜請求項４の何れか１項記載のデータ更新処理装置。
【請求項６】
所定個のＨＭＭが要求されたときに、前記記憶手段に記憶された、階層構造で定められた前記複数のＨＭＭの各々のパラメータに基づいて、前記所定個のＨＭＭの各々のパラメータを提示する提示手段を更に含む請求項１〜請求項５の何れか１項記載のデータ更新処理装置。
【請求項７】
階層構造で定められた複数の隠れマルコフモデル（ＨＭＭ）の各々のパラメータ、及び最下層のＨＭＭの少なくとも１つに属し、かつ、属する最下層のＨＭＭの各々に対する重みが付された複数のシーケンスを記憶する記憶手段、シーケンス挿入手段、更新手段、分割手段、推定手段、及びシーケンス再挿入手段を含むデータ更新処理装置におけるデータ更新処理方法であって、
前記シーケンス挿入手段によって、入力されたシーケンスについて、階層構造に従って、最上層のＨＭＭから最下層のＨＭＭまで、各ＨＭＭに対する尤度に基づいて前記ＨＭＭを選択して、前記入力されたシーケンスが属する少なくとも１つの最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記入力されたシーケンスを挿入すると共に、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みを求め、
前記更新手段によって、前記シーケンス挿入手段によって選択された最上層のＨＭＭから最下層のＨＭＭまでの各ＨＭＭについて、新たなシーケンスのための空きがある場合、前記選択された前記ＨＭＭのパラメータを、前記入力されたシーケンスに基づいて更新し、
前記分割手段によって、前記シーケンス挿入手段によって選択された最上層のＨＭＭから最下層のＨＭＭまでの各ＨＭＭについて、新たなシーケンスのための空きがない場合、前記選択された前記ＨＭＭを、２つのＨＭＭに分割すると共に、前記選択されたＨＭＭに属する１つ下の層の複数のＨＭＭ、又は前記選択されたＨＭＭに属する複数のシーケンスを、分割された２つのＨＭＭに割り振り、
前記推定手段によって、前記分割手段によって分割された２つのＨＭＭの各々のパラメータを、前記ＨＭＭに割り振られたＨＭＭの配下のシーケンス、又は前記ＨＭＭに割り振られたシーケンスに基づいて推定し、
前記シーケンス再挿入手段によって、前記分割手段によって分割された２つのＨＭＭが最下層のＨＭＭであって、前記最下層のＨＭＭに属するシーケンスの前記ＨＭＭに対する尤度に基づく値が、閾値と比較して不適切な値であると判定される場合、前記シーケンスを、前記最下層のＨＭＭに属するシーケンスから削除して、前記シーケンスに対応する前記最下層のＨＭＭから最上層のＨＭＭまでの各ＨＭＭのパラメータを更新すると共に、前記シーケンスについて、階層構造に従って、最上層のＨＭＭから最下層のＨＭＭまで、各ＨＭＭに対する尤度に基づいて前記ＨＭＭを選択して、前記シーケンスが属する少なくとも１つの最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記シーケンスを再挿入すると共に、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みを求める
データ更新処理方法。
【請求項８】
コンピュータを、請求項１〜請求項６の何れか１項記載のデータ更新処理装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ更新処理装置、方法、及びプログラムに係り、特に、入力されたシーケンスに基づいて、隠れマルコフモデルを更新するデータ更新処理装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
隠れマルコフモデル(HMM;Hidden Markov Model)は不確定な時系列のデータをモデル化するための有効な統計的手法である。HMMはノイズにロバストであり、話者認識や自然言語処理、たんぱく質やDNAを含む遺伝子列解析等多くのアプリケーションにおいて使用されている。HMMは、初期状態確率π=｛πi｝、状態遷移確率A=｛ａij｝、シンボル出力確率B=｛ｂi(v)｝から構成される。
【０００３】
モデルΘとシーケンスｘが与えられたとき、これらの尤度L(x｜Θ)は、Viterbiアルゴリズムにより、以下の（１）式のように計算できる。
【０００４】
【数１】
2014016731.tif 000003
【０００５】
ここで、δt(i)は、時刻tにおける状態iの最大確率を示す。
【０００６】
また、EMアルゴリズムは、欠損値があるようなデータに対し、観測不可能な潜在変数の確率モデルのパラメータを最尤法に基づいて推定する手法である。EMアルゴリズムは反復法の一種であり、Eステップ(Expectation)とMステップ(Maximization)を交互に繰り返すことで計算が進行する。
【０００７】
Eステップ:  HMMにおいて、Baum-WelchアルゴリズムはEステップにおける効率的な期待値計算の手法である。Baum-WelchアルゴリズムはHMMのパラメータΘ=｛π,A,B｝に基づき、期待値を計算する。γt(i)は、シーケンスが与えられた上での時刻tにおける状態iの確率を示し、以下の（２）式のように計算される。
【０００８】
【数２】
2014016731.tif 000004
【０００９】
ここで、αt(i)=P(x1,...,xt,qt=i|Θ),βt(i)=P(xt+1,...,xm｜ｑt=i,Θ)である。qtは時刻tにおける最適な状態を示す。ξt(i,j)は、時刻tにおける状態iと、時刻t+1における状態jの遷移確率であり、以下の（３）式で表わされる。
【数３】
2014016731.tif 000005
【００１０】
Mステップ:  アルゴリズムは、期待値γt(i),ξt(i,j)とシーケンスxに基づき、尤度を最大化する新たなモデルパラメータ~Θを計算する。モデルパラメータの更新式は、以下の（４）式〜（６）式である。
【００１１】
【数４】
2014016731.tif 000006
【００１２】
ここで、xtは時刻tにおけるxのシンボルを示す。
【００１３】
また、階層型隠れマルコフモデル(Hierarchical Hidden Markov Model)は階層構造を持つシーケンスを表現するためにHMMを拡張したものである（非特許文献１）。隠れ状態を階層化、すなわち木構造に基づいており、EMアルゴリズムを用いて各階層のモデルパラメータの推定を行なう。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Fine,S.,Singer,Y.and Tishby,N. ”The Hierarchical Hidden Markov Model”, Analysis and Applications, Machine Learning, Vol.32, No.1, pp.41-62(1998).
【発明の概要】
【発明が解決しようとする課題】
【００１５】
本発明で扱う問題が大量のシーケンス集合から任意の数のモデルを決定することにあるのに対し、上記の階層型HMMはシーケンス全体を様々な長さに分割し、階層的なモデル構造を構築することにある。階層型HMMを本発明の問題に適用することは可能であるが、モデル推定に多大な計算コストを必要とする。特に、新たにシーケンスデータが与えられると、過去に蓄積された全てのシーケンスを用いてモデル推定を行う必要がある。
【００１６】
本発明は、上記の事情を鑑みてなされたもので、新たにシーケンスが入力された場合に、計算時間とメモリ使用量とを削減して、階層構造の隠れマルコフモデルを更新することができるデータ更新処理装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１７】
上記の目的を達成するために本発明に係るデータ更新処理装置は、階層構造で定められた複数の隠れマルコフモデル（ＨＭＭ）の各々のパラメータ、及び最下層のＨＭＭの少なくとも１つに属し、かつ、属する最下層のＨＭＭの各々に対する重みが付された複数のシーケンスを記憶する記憶手段と、入力されたシーケンスについて、階層構造に従って、最上層のＨＭＭから最下層のＨＭＭまで、各ＨＭＭに対する尤度に基づいて前記ＨＭＭを選択して、前記入力されたシーケンスが属する少なくとも１つの最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記入力されたシーケンスを挿入すると共に、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みを求めるシーケンス挿入手段と、前記シーケンス挿入手段によって選択された最上層のＨＭＭから最下層のＨＭＭまでの各ＨＭＭについて、新たなシーケンスのための空きがある場合、前記選択された前記ＨＭＭのパラメータを、前記入力されたシーケンスに基づいて更新する更新手段と、前記シーケンス挿入手段によって選択された最上層のＨＭＭから最下層のＨＭＭまでの各ＨＭＭについて、新たなシーケンスのための空きがない場合、前記選択された前記ＨＭＭを、２つのＨＭＭに分割すると共に、前記選択されたＨＭＭに属する１つ下の層の複数のＨＭＭ、又は前記選択されたＨＭＭに属する複数のシーケンスを、分割された２つのＨＭＭに割り振る分割手段と、前記分割手段によって分割された２つのＨＭＭの各々のパラメータを、前記ＨＭＭに割り振られたＨＭＭの配下のシーケンス、又は前記ＨＭＭに割り振られたシーケンスに基づいて推定する推定手段と、前記分割手段によって分割された２つのＨＭＭが最下層のＨＭＭであって、前記最下層のＨＭＭに属するシーケンスの前記ＨＭＭに対する尤度に基づく値が、閾値と比較して不適切な値であると判定される場合、前記シーケンスを、前記最下層のＨＭＭに属するシーケンスから削除して、前記シーケンスに対応する前記最下層のＨＭＭから最上層のＨＭＭまでの各ＨＭＭのパラメータを更新すると共に、前記シーケンスについて、階層構造に従って、最上層のＨＭＭから最下層のＨＭＭまで、各ＨＭＭに対する尤度に基づいて前記ＨＭＭを選択して、前記シーケンスが属する少なくとも１つの最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記シーケンスを再挿入すると共に、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みを求めるシーケンス再挿入手段と、を含んで構成されている。
【００１８】
本発明に係るデータ更新処理方法は、階層構造で定められた複数の隠れマルコフモデル（ＨＭＭ）の各々のパラメータ、及び最下層のＨＭＭの少なくとも１つに属し、かつ、属する最下層のＨＭＭの各々に対する重みが付された複数のシーケンスを記憶する記憶手段、シーケンス挿入手段、更新手段、分割手段、推定手段、及びシーケンス再挿入手段を含むデータ更新処理装置におけるデータ更新処理方法であって、前記シーケンス挿入手段によって、入力されたシーケンスについて、階層構造に従って、最上層のＨＭＭから最下層のＨＭＭまで、各ＨＭＭに対する尤度に基づいて前記ＨＭＭを選択して、前記入力されたシーケンスが属する少なくとも１つの最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記入力されたシーケンスを挿入すると共に、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みを求め、前記更新手段によって、前記シーケンス挿入手段によって選択された最上層のＨＭＭから最下層のＨＭＭまでの各ＨＭＭについて、新たなシーケンスのための空きがある場合、前記選択された前記ＨＭＭのパラメータを、前記入力されたシーケンスに基づいて更新し、前記分割手段によって、前記シーケンス挿入手段によって選択された最上層のＨＭＭから最下層のＨＭＭまでの各ＨＭＭについて、新たなシーケンスのための空きがない場合、前記選択された前記ＨＭＭを、２つのＨＭＭに分割すると共に、前記選択されたＨＭＭに属する１つ下の層の複数のＨＭＭ、又は前記選択されたＨＭＭに属する複数のシーケンスを、分割された２つのＨＭＭに割り振り、前記推定手段によって、前記分割手段によって分割された２つのＨＭＭの各々のパラメータを、前記ＨＭＭに割り振られたＨＭＭの配下のシーケンス、又は前記ＨＭＭに割り振られたシーケンスに基づいて推定し、前記シーケンス再挿入手段によって、前記分割手段によって分割された２つのＨＭＭが最下層のＨＭＭであって、前記最下層のＨＭＭに属するシーケンスの前記ＨＭＭに対する尤度に基づく値が、閾値と比較して不適切な値であると判定される場合、前記シーケンスを、前記最下層のＨＭＭに属するシーケンスから削除して、前記シーケンスに対応する前記最下層のＨＭＭから最上層のＨＭＭまでの各ＨＭＭのパラメータを更新すると共に、前記シーケンスについて、階層構造に従って、最上層のＨＭＭから最下層のＨＭＭまで、各ＨＭＭに対する尤度に基づいて前記ＨＭＭを選択して、前記シーケンスが属する少なくとも１つの最下層のＨＭＭを選択し、前記選択された最下層のＨＭＭの各々に属するシーケンスとして、前記シーケンスを再挿入すると共に、前記選択された最下層のＨＭＭの各々に対する前記シーケンスの重みを求める。
【００１９】
本発明に係るプログラムは、コンピュータを、上記のデータ更新処理装置の各手段として機能させるためのプログラムである。
【発明の効果】
【００２０】
以上説明したように、本発明のデータ更新処理装置、方法、及びプログラムによれば、入力された新たなシーケンスについて、階層構造で定められた複数の隠れマルコフモデル（ＨＭＭ）に対して、最上層のＨＭＭから最下層のＨＭＭまでＨＭＭを選択して、最下層のＨＭＭに、入力されたシーケンスを挿入し、ＨＭＭに新たなシーケンスのための空きがない場合に、ＨＭＭを分割して、下の層のＨＭＭ又はシーケンスを割り振り、分割した結果、不適切なシーケンスの割り振りが発生した場合には、当該シーケンスについて、最上層のＨＭＭから最下層のＨＭＭまで、ＨＭＭを選択して、最下層のＨＭＭに、再挿入することにより、新たにシーケンスが入力された場合に、計算時間とメモリ使用量とを削減して、階層構造の隠れマルコフモデルを更新することができる、という効果が得られる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施の形態に係るデータ更新処理装置の構成を示す概略図である。
【図２】階層モデル構造を例示した図である。
【図３】階層モデル構造の更新を例示した図である。
【図４】本発明の第１の実施の形態に係るデータ更新処理装置における階層モデル更新処理ルーチンの内容を示すフローチャートである。
【図５】本発明の第２の実施の形態に係る近似データ更新処理装置の構成を示す概略図である。
【図６】本発明の第２の実施の形態に係る近似データ更新処理装置における階層型サンプリング処理ルーチンの内容を示すフローチャートである。
【図７】モーションキャプチャデータにおける左右の足の運動エネルギーを表現したシーケンスの例を示した図である。
【図８】比較手法及び本発明の手法によってシーケンスを分類した結果を示した図である。
【図９】計算コストに関する実験結果を示した図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２３】
〔第１の実施の形態〕
＜発明の概要＞
X をn 個の時系列シーケンスデータとする（すなわちX=｛x1,...,xn｝）。本発明の目的は、Xの特徴を統計的に表現するようなc個のHMMを決定することである。全てのシーケンスxi(i=1,...,n) は、c個のモデルの中で1つもしくは複数のモデルに確率w(すなわち重み0≦w≦1)で属しているものとみなす。そこで、本発明が解決する問題は次の通りである。
【００２４】
（問題1）：n個のシーケンスからなる時系列データ集合X=｛x1,...,xn｝が定間隔で与えられるとき、尤度の合計Σni=1Σcj=1wi,jL(xi｜Θj)が最大化するようなモデルΘj(j=1,...,c)を発見する。
【００２５】
モデル推定のための学習用データ集合が時間に伴い増加する、すなわちシーケンスの個数nが増加するような動的な状況下においては、上記の問題を解決するために工夫が必要である。入力シーケンスを連続的に学習し、どの時刻においてもユーザが要求した時点で任意のc個のモデルを提示する方法が必要となる。具体的に、理想的な解決策として次の3つの要求を満たす必要がある。
【００２６】
適用性:入力シーケンスを自動的に判別、グループ化し、HMMのパラメータを推定する。このとき、各グループに関する知識は事前に有していないものとする。
【００２７】
拡張性:モデルの更新のための処理は、シーケンスの個数に対して線形時間よりも短い計算コスト(sub-linear)を実現する。
【００２８】
即時性: シーケンスを学習する際にモデルの個数c は事前に与えられないものとし、このような事前知識なしで、ユーザがc個のモデルを求めた時点で即時にユーザに提示する。
【００２９】
既存のデータ学習では、オリジナルのシーケンス集合を全て利用しモデルの推定を行なう方法が主流である。しかし、データは断続的に生成され続けるような動的な状況下では、モデル推定にアーカイブされた過去の大量のデータ全てを用いると計算コストが膨大になってしまう点が問題となる。そこで、本発明では、計算時間とメモリ使用量を大幅に削減し、モデルを任意の粒度で推定することができる、階層モデルのデータ更新処理装置について述べる。
【００３０】
＜システム構成＞
図１に示すように、本発明の第１の実施の形態に係るデータ更新処理装置１００は、ＣＰＵと、ＲＡＭと、後述する階層モデル更新処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。図１に示すように、データ更新処理装置１００は、入力部１０と、処理部２０と、出力部３０とを備えている。
【００３１】
入力部１０は、ネットワークを介して受信した時系列データの入力を受け付ける。また、入力部１０は、キーボードなどの入力装置から、問い合わせデータとして、任意のモデル数の入力を受け付ける。
【００３２】
処理部２０は、時系列データ蓄積部２１、階層モデルデータ記憶部２２、及び時系列データ処理部２３から構成される。なお、時系列データ蓄積部２１及び階層モデルデータ記憶部２２が、記憶手段の一例であり、時系列データ処理部２３が、シーケンス挿入手段、更新手段、分割手段、推定手段、シーケンス再挿入手段、及び提示手段の一例である。
【００３３】
時系列データ蓄積部２１は、入力部１０により受け付けた時系列データを記憶する。階層モデルデータ記憶部２２は、階層構造の複数のＨＭＭのモデルパラメータを記憶する。時系列データ処理部２３は、入力部１０により時系列データを受け付けると、階層モデルデータ記憶部２２に記憶されているモデルパラメータを更新する。この際、時系列データ処理部２３は、時系列データ蓄積部２１に蓄積された全てのシーケンスにアクセスすることなくモデルパラメータを更新する。また、時系列データ処理部２３は、重み付きモデル推定、ノード分割、および再挿入処理を有することを特徴とするモデルパラメータの更新処理を行う。また、入力された時系列データは時系列データ蓄積部２１のディスク空間に格納されるものの、メモリ空間からは破棄され、データ更新処理装置１００におけるメモリ量を節約することができる。
【００３４】
また、利用者から入力された問合せデータとしてのモデル数cを受け付けると、時系列データ処理部２３は、時系列データの特徴を表現するようなc個のモデルを、出力部３０により利用者に出力する。
【００３５】
次に、時系列データ処理部２３によるデータ更新処理の原理について説明する。
【００３６】
まず、階層モデルの構造について説明する。
【００３７】
本発明は、階層構造を用いてモデルの推定を行なう。階層構造を用いることにより、新たなシーケンスの挿入を行う際にその時点で蓄積されている過去のすべてのシーケンスにアクセスすることなく必要最小限のコストでモデルパラメータの更新処理が可能である。これが階層構造を用いる利点の1つである。第２の利点として、シーケンスのグループ化の処理過程をインクリメンタルに行なうことが可能で、事前に全てのシーケンスの集合を解析しておく必要がないことが挙げられる。これらの特徴により、シーケンスの数に対して線形時間を下回るコストでモデルの更新を行なうことができる。さらに、非常に重要な第3の利点として、任意の粒度でHMMのパラメータの集合を得ることができる点が挙げられる。すなわち、ユーザがc個のモデルを要求した際、本発明により素早くc個のモデルパラメータを提示することができる。これによりユーザの要求に対し柔軟な対応をすることができる。
【００３８】
＜モデル構造＞
図２に本発明のモデル構造の例を示す。図２は2階層のモデル構造(すなわちh=2)を示している。モデル構造のl階層目には、bh-l個の要素(この場合b=4)があり、各要素はその下層のb個の部分要素を含んでいる。l階層目のj番目の要素は、その配下にある部分要素の要約情報を保持しており、以下の（７）式のように定義される。
【００３９】
【数５】
2014016731.tif 000007
【００４０】
ここでnl;jとΘl,jはそれぞれ、要素Nl,jの配下の部分要素に属している全てのシーケンスの個数、そしてそれらのシーケンスを表現しているモデルパラメータを示す。ただし上記の要素と異なり、最下層(すなわちl=1)ではnl,jとΘl,jの他に、さらにシーケンスのリストを保持する。l=1におけるj番目の要素は次のように定義される。
【００４１】
【数６】
2014016731.tif 000008
【００４２】
ここで、シーケンスのリストDjは、(xi,wi,j)の2つ組で表現されるエントリの集合であり、各エントリにはシーケンスxiへのポインタと、xiがN1,jに属している確率(すなわち重み)の2つの情報が管理されている。重みwi,jは入力シーケンスxiが挿入される際に計算される。各シーケンスのリストにおける重みの合計は、最大b とする(すなわちb≧Σiwi,j)。階層モデル構造は、ユーザが要求した任意の数のモデルを提示するため有効であるが、入力されるシーケンスをグループ化し要約する用途に対しても非常に有効である。階層構造の中でシーケンスの要約情報(すなわちモデルのパラメータ) を扱い管理することは、シーケンスに関する全ての情報を扱うことに比べ非常に効率的であり、さらに階層構造の更新をする際には、各要素で管理されているモデルと入力シーケンスとの間の尤度を計算することにより、即座にシーケンスのグループ化処理を行なうことができる。ここで、図２を用いて階層構造の例を示す。
【００４３】
（例1）：｛x1,...,x6｝を階層構造に蓄積されているシーケンスの集合とする。各要素(N2,1,N1,1,N1,2)は、それぞれモデルパラメータΘ2,1,Θ1,1,Θ1,2を保持している。各要素のモデルは配下で管理されているシーケンス集合の特徴を表現している。具体的に、Θ1,1はシーケンス集合｛x1,x2,x6｝を、重みw1,1,w2,1,w6,1で学習したモデルのパラメータである。同様に、Θ1,2は｛x3,...,x6｝を重みw3,2,w4,2,w5,2,w6,2で学習したモデルである。そしてΘ2,1は全てのシーケンスの集合｛ x1,...,x6｝の特徴を表現している。
【００４４】
＜モデルの提示＞
階層構造を用いることにより、任意の時刻に任意の個数のモデルを提示することができる。ここで、ユーザがc個の代表的モデルを要求した場合を考える。まずはじめにアルゴリズムは、充分な数(≧c)の要素を構造の中から取り出す。次に、それらの要素を、尤度を用いてc個のシーケンスのグループに統合する。最後に、c個にグループ化されたシーケンス集合のモデルのパラメータを再推定し、ユーザへ提示する。
【００４５】
＜挿入＞
次に、入力シーケンスの階層構造への挿入方法について述べる。
【００４６】
本発明で提案した階層構造は従来のデータ構造と異なり、格納されているエントリ（シーケンス）各々に対して確率(重み)が考慮されているという特徴を持つ。したがって、本発明で提案した階層構造については、従来の挿入手法を用いることができない。そこで、本発明ではこの問題を解決するために新たなアルゴリズムを提案する。提案する挿入アルゴリズムでは、入力データは重みの値によって複数個の要素の中に挿入される。すなわち、従来の挿入手法と異なり、本発明では複数の挿入パスを扱う必要がある。本発明において挿入アルゴリズムを設計するにあたり、我々は深さ優先探索のアプローチをとり、全てのパスに対する挿入処理を行うことを考える。
【００４７】
入力シーケンスxiが与えられたとき、アルゴリズムは以下の（１）〜（３）の順序で挿入処理を行なう。
【００４８】
（１）最上層のＨＭＭから開始し、入力シーケンスの当該ＨＭＭに対する尤度に従い適切な要素（ＨＭＭ）を選択しながら最下層まで降下する。ここで、計算された尤度は入力シーケンスの重みの計算にも利用される。この重みは、挿入パス（最上層から最下層までの選択されたＨＭＭ）上にある全ての要素のモデルと入力シーケンスの間の確率を表現している(（９）式参照)。アルゴリズムが最下層(l=1)の要素N1,jに到達したのち、新たなエントリ(xi,wi,j)、すなわちxiへのポインタとxiのN1,jに対する重み(すなわち、xiをN1,jに挿入するにあたっての重み)が、N1,j内のシーケンスのリストDjに追加される。
【００４９】
（２）要素N1,jの中にxiが挿入されたのち、アルゴリズムでは挿入パス上にある各要素の情報の修正を行なう。すなわち、もし新たな入力(xi,wi,j)に対し各要素において分割が起きない場合には、単純に、挿入パス上の各要素のモデルパラメータを、xiを用いて更新する。もし各要素で新たな挿入に対しスペースがない場合(すなわちΣiwi,j≧b)は、要素の分割が生じ、分割された要素においてモデルのパラメータが再推定される。
【００５０】
（３）要素の分割操作が起きた際、もし最下層の各要素において不適切なエントリが生じた場合には、アルゴリズムでは、それらのエントリを適切な要素へ再挿入する。再挿入の操作では、挿入操作と同様の処理を行ない、階層構造で管理されるシーケンスをより適切な要素の配下に移動することで、シーケンス集合をより正しく表現するモデル構造を構築することができる。
【００５１】
ここで、重要な点について言及する。理論的には、i番目のシーケンスxiにおける重みの値の合計はΣjwi,j=1である。しかし構造内で管理される要素の数は、とりわけ大規模なデータを扱う場合には非常に大きいものとなる。一方で、主要な挿入パス以外に係る重みの値は非常に小さく、無視できる程度のものである。そこで、本発明では大きな重みが係っている要素に対してのみ挿入を行ない、その他の細かな重みが付いている要素に対しては挿入を行なわないものとする。具体的には、挿入を繰り返す際に重みの合計値が閾値wth(例えばwth=0.9)を超えたら挿入を停止する。
【００５２】
次に、挿入操作における重みの計算について述べる。最下層のj番目の要素N1,jにおけるxiの重みwi,jはxiの尤度を用いて、以下の（９）式のように計算される。
【００５３】
【数７】
2014016731.tif 000009
【００５４】
なおhは階層構造の高さを示し、l番目の層におけるbl(bl≦b)は、挿入パス上にある兄弟要素の個数である。
【００５５】
＜重みつきモデル推定＞
本発明は入力シーケンスに対して重みを保持し、その重みを用いてシーケンスのモデル推定を行なう。そこで、本発明では既存のEMアルゴリズムを改良し、重みを伴うモデルの推定を実現する。入力シーケンスxとその重みwが与えられたとき、本発明ではxの重みつき期待値γt(i)を、以下の（１０）式、（１１）式のように計算する。
【００５６】
【数８】
2014016731.tif 000010
【００５７】
Mステップでは、重みつき期待値を利用し、上記（４）式〜（６）式に基づきモデルパラメータの更新を行なう。
【００５８】
（例2）：ここで、図２に示すように、新たなシーケンスx6を挿入する例について説明を行なう。始めの挿入として、アルゴリズムでは最上部から開始し各層において最も適切なモデルΘ2,1,Θ1,1を発見する。さらに（９）式を用いて重みw6,1を計算する。要素N1,1にはこの新たなエントリの挿入スペースがあるので、要素の分割は発生せず、そのままN1,1にエントリが追加される。エントリ追加ののち、アルゴリズムは挿入パス上にあるモデルΘ2,1,Θ1,1を、エントリ(x6,w6,1)を用いて更新する。次の処理として、挿入パスΘ2,1,Θ1,2を2番目に近いモデルとして発見し、N1,2にx6を追加する。ここでも要素の分割は生じない。続いて重みw6,2を計算する。これらの2つの挿入操作ののち、x6の重みの合計が閾値を超えたら(すなわちw6,1+w6,2>wth)、アルゴリズムは挿入操作を終了する。
【００５９】
＜分割操作＞
続いて分割操作の詳細について述べる。要素Nが与えられたとき、分割は以下の（１）〜（５）の手順で行なわれる。
【００６０】
（１）要素Nに属する全ての部分要素の中からランダムに2つの部分要素を選択し、それらのモデルΘ1、Θ2を得る。
【００６１】
（２）Nに属する各部分要素を、モデルΘ1とΘ2のより近いグループに割り振る。ここでグループへの割り振りには、各モデルΘ1、Θ2に対する各部分要素に属するシーケンスxiの尤度の合計ΣiL(xi｜Θ1)(もしくは、ΣiL(xi｜Θ1))を類似指標として用いる。
【００６２】
（３）部分要素の割り振りがなされたそれぞれのグループに対し、ランダムに新たなモデルを1つずつ選択しΘ1、Θ2を得る。
【００６３】
（４）各グループ間の移動がなくなるまで上記（２）〜（４）の手順を繰り返す。
【００６４】
（５）新たに生成された2つのグループに対し、それぞれのグループに属している全てのシーケンスを用いて、モデルパラメータΘ1、Θ2を推定する。最後に、現在の要素Nを削除し、新たに分割され生成された要素Ｎ1、Ｎ2とそのモデルパラメータΘ1、Θ2を追加する。また、新たに分割され生成された要素Ｎ1、Ｎ2の各グループに割り振られた部分要素を、新たに分割され生成された当該要素に属する部分要素とする。
【００６５】
なお、要素Ｎが最下層の要素である場合には、要素Ｎに属する部分要素を、シーケンスに置き換えて、上記の（１）〜（５）の手順で分割操作が行われる。また、各シーケンスについて、分割された２つの要素のうちの割り振られた要素に対する重みを計算する。
【００６６】
（例3）：図３に示すように、x7を挿入する例を考える。最上層から挿入を開始し、各層において最も近いモデルΘ2,1、Θ1,2を発見する。ここで、最下層の要素N1,2にx7を挿入しようとするが、新たな挿入をするためのスペースがないため(すなわちΣiwi,2≧b)、アルゴリズムではN1,2を2つの要素N1,2、N1,3に分割し、現在管理されているエントリ集合｛x3、x4、x6｝に対し、｛x5、x7｝をN1,2へ、｛x5、x7｝をN1,3へ割り振る。要素の分割が行なわれたのち、Θ1,2はN1,2によって、そしてΘ1,3はN1,3によって再推定がなされる。同様にして、挿入パス上のΘ2,1も更新される。
【００６７】
＜再挿入操作＞
アルゴリズムでは、各入力シーケンスに対して1度しか挿入操作を行なわない。このためモデル構造の更新に従い、過去に挿入されたシーケンスの重みの値が適切でない値となる可能性がある。ここで問題となるのが、分割操作が生じた際にモデルのパラメータが大幅に変化し、配下に属するシーケンスの重みが不適切になるような状況である。この問題の解決案として妥当なのは、最下層の要素で分割が起こった際に、それら要素において不適切となった過去のシーケンスを削除し、新たに挿入操作を行なうことにより、適した要素にシーケンスを移動することである。ここで、不適切となったシーケンスは、以下の（１２）式に示す尤度比検定を用いて検出することができる。
【００６８】
【数９】
2014016731.tif 000011
【００６９】
なお、Θiはxiから推定されたモデルパラメータ、Θ1,jはN1,jにおいて保持されているモデルパラメータを示す。もし尤度比ρiが特定の閾値ρth(ρth=0.8等)以下である場合、アルゴリズムは現在のエントリ(xi、wi,j)をN1,jから削除し、このエントリを新たに挿入する。このような再挿入操作によって、シーケンスをよりモデル構造に適した位置に移動することができる。
【００７０】
＜データ更新処理装置の作用＞
次に、データ更新処理装置１００の具体的な処理について説明する。まず、データ更新処理装置１００に、シーケンス集合が入力されると、データ更新処理装置１００は、時系列データ蓄積部２１に格納する。そして、データ更新処理装置１００は、シーケンス集合に基づいて、階層構造のＨＭＭを構築し、階層モデルデータ記憶部２２に格納する。
【００７１】
そして、データ更新処理装置１００に、新たなシーケンスが入力されると、データ更新処理装置１００は、図４に示す階層モデル更新処理ルーチンを実行する。
【００７２】
まず、ステップＳ１０１において、入力部１０は、入力されたシーケンスｘiを受け付ける。次のステップＳ１０２では、時系列データ処理部２３は、シーケンスｘiの付与する重みの合計ｗsumに初期値０を設定する。
【００７３】
その後、時系列データ処理部２３は、重みの合計ｗsumが、予め定められた閾値ｗthより大きくなるまで、ステップＳ１０３〜Ｓ１１３の処理を繰り返す。
【００７４】
ステップＳ１０３において、時系列データ処理部２３は、最上層から最下層まで、要素に対する尤度に基づいて選択して、適切な最下層の要素を選択し、選択した要素に属するシーケンスとして、入力されたシーケンスｘiを挿入し、選択した当該要素に対する重みｗを計算する。なお、ステップＳ１０３の処理が２回目以降である場合には、前回までに選択された最下層の要素を除いて、適切な最下層の要素を選択する。
【００７５】
そして、時系列データ処理部２３は、上記ステップＳ１０３で選択された最上層から最下層までの要素からなる挿入パス上の全ての要素Ｎについて、ステップＳ１０４〜Ｓ１１３を繰り返す。
【００７６】
ステップＳ１０４において、時系列データ処理部２３は、要素Ｎに、新たなエントリのための空きがあるか否かを判定する。当該要素の配下の部分要素に属するシーケンスの重みの合計が閾値ｂ未満である場合には、要素Ｎに、新たなエントリのための空きがあると判定され、ステップＳ１０５において、時系列データ処理部２３は、入力されたシーケンスｘiを用いて、上記（１０）式、（１１）式と上記（４）式〜（６）式とに従って、要素ＮのＨＭＭのモデルパラメータΘを更新し、上記ステップＳ１０３又はステップＳ１０４へ戻るか、処理ルーチンを終了する。
【００７７】
一方、当該要素の配下の部分要素に属するシーケンスの重みの合計が閾値ｂ以上である場合には、要素Ｎに、新たなエントリのための空きがないと判定され、ステップＳ１０６において、時系列データ処理部２３は、上記の分割操作により、要素Ｎを、Ｎ1とＮ2に分割する。ステップＳ１０７では、時系列データ処理部２３は、Ｎ1に割り振られたシーケンス集合を、Ｘ1とし、ステップＳ１０８において、時系列データ処理部２３は、Ｎ2に割り振られたシーケンス集合を、Ｘ2とする。
【００７８】
次のステップＳ１０９では、時系列データ処理部２３は、シーケンス集合Ｘ1を用いて、要素Ｎ1のＨＭＭのモデルパラメータΘ1を更新すると共に、シーケンス集合Ｘ2を用いて、要素Ｎ2のＨＭＭのモデルパラメータΘ2を更新する。
【００７９】
ステップＳ１１０では、時系列データ処理部２３は、要素Ｎ1、Ｎ2が、最下層の要素であるか否かを判定する。要素Ｎ1、Ｎ2が、最下層の要素ではない場合には、上記ステップＳ１０３又はステップＳ１０４へ戻るか、処理ルーチンを終了する。
【００８０】
一方、要素Ｎ1、Ｎ2が、最下層の要素である場合には、時系列データ処理部２３は、要素Ｎ1、Ｎ2に属する全てのシーケンスｘjについて、ステップＳ１１１〜Ｓ１１３を繰り返す。
【００８１】
ステップＳ１１１では、時系列データ処理部２３は、シーケンスｘjについて、上記（１２）式に従って尤度比ρjを計算し、計算した尤度比ρjが、閾値ρth以下であるか否かを判定する。計算した尤度比ρjが、閾値ρthより大きい場合には、シーケンスｘjの重みが適切であると判断し、上記ステップＳ１０３、ステップＳ１０４、ステップＳ１１１へ戻るか、処理ルーチンを終了する。一方、計算した尤度比ρjが、閾値ρth以下である場合には、シーケンスｘjの重みが不適切であると判断し、ステップＳ１１２において、時系列データ処理部２３は、シーケンスｘjを、要素Ｎ1又はＮ2に属するシーケンスから除去して、当該要素Ｎ1又はＮ2から最上層の要素までの、シーケンスｘjに対するパス上の各要素のＨＭＭのモデルパラメータΘを、シーケンスｘjを除去したシーケンス集合に基づいて更新する。
【００８２】
ステップＳ１１３では、時系列データ処理部２３は、上記ステップＳ１０３と同様に、最上層から最下層まで、要素に対する尤度に基づいて、適切な最下層の要素を選択し、選択した要素に属するシーケンスとして、シーケンスｘjを再挿入し、選択した当該要素に対する重みｗを計算する。また、上記ステップＳ１０４〜ステップＳ１１３までの処理と同様の処理も行う。
【００８３】
そして、上記ステップＳ１０３、ステップＳ１０４、ステップＳ１１１へ戻るか、処理ルーチンを終了する。
【００８４】
以上説明したように、本発明の第１の実施の形態にデータ更新処理装置によれば、入力された新たなシーケンスについて、階層構造で定められた複数の隠れマルコフモデル（ＨＭＭ）に対して、最上層のＨＭＭから最下層のＨＭＭまでＨＭＭを選択して、最下層のＨＭＭに、入力されたシーケンスを挿入し、ＨＭＭに新たなシーケンスのための空きがない場合に、ＨＭＭを分割して、下の層のＨＭＭ又はシーケンスを割り振り、分割した結果、不適切なシーケンスの割り振りが発生した場合には、当該シーケンスについて、最上層のＨＭＭから最下層のＨＭＭまで、ＨＭＭを選択して、最下層のＨＭＭに、再挿入することにより、新たにシーケンスが入力された場合に、全てのシーケンスにアクセスせずに、計算時間とメモリ使用量とを削減して、階層構造の隠れマルコフモデルを更新することができる。
【００８５】
また、階層モデルのデータ更新処理に要する計算時間とメモリ使用量を大幅に削減することが可能となり、動的な環境においてモデルを任意の粒度で推定することができる。
【００８６】
〔第２の実施の形態〕
次に、第２の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【００８７】
第２の実施の形態では、シーケンスのサンプリング結果を用いて、モデルパラメータを更新している点と、新たに追加されるシーケンスのみを用いて、モデルパラメータを更新している点とが第１の実施の形態と異なっている。
【００８８】
＜発明の概要＞
上記の第１の実施の形態において説明したデータ更新処理装置１００においては、階層モデルの構造内で分割処理が発生してモデルの再推定が必要となった際、分割する要素に属する全てのシーケンスを用いる必要がある。これに対して、第２の実施の形態における図2に示す近似データ更新処理装置２００は、上記の第１の実施の形態のデータ更新処理装置１００を改良したものであり、近似時系列データ処理部２２３において階層型のサンプリングを行うことにより、モデル再推定のための計算時間を節約することができる。
【００８９】
＜システム構成＞
図５に示すように、第２の実施の形態に係る近似データ更新処理装置２００は、
【００９０】
ＣＰＵと、ＲＡＭと、後述する処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。図５に示すように、近似データ更新処理装置２００は、入力部１０と、処理部２２０と、出力部３０とを備えている。
【００９１】
処理部２２０は、時系列データ蓄積部２１、階層モデルデータ記憶部２２、及び近似時系列データ処理部２２３から構成される。近似時系列データ処理部２２３が、シーケンス挿入手段、更新手段、分割手段、推定手段、シーケンス再挿入手段、提示手段、及びサンプリング手段の一例である。
【００９２】
第２の実施の形態における近似時系列データ処理部２２３による更新処理方法の原理について説明する。
【００９３】
＜高速化処理＞
HMMのパラメータを推定するための最も単純な方法は、階層モデル構造で管理されている過去のシーケンスを全て使用することである。しかし全てのシーケンスを利用することは、ストリーミングの状況下ではボトルネックとなってしまう。そこで、本実施の形態では、次の（１）、（２）のアイデアを用いる。
【００９４】
（１）階層構造内で分割処理が生じ新たにモデルの再推定が必要となった際、分割する要素に属する全てのシーケンスを使用する代わりに、サンプリングのアプローチを用いてシーケンス集合の1部のみを利用する。
【００９５】
（２）モデル推定のコストを削減するため、インクリメンタルにモデル推定を行う。EMアルゴリズムを拡張し、新たな入力データのみを用いてシーケンスのモデルパラメータを更新する。
【００９６】
上記の第１の実施の形態で説明した階層モデル更新処理ルーチンでは、入力シーケンスxiを受け取る毎に挿入操作を実行する。要素の分割操作が生じない場合はxiを利用しモデルを更新する。分割操作が生じる場合には、ステップＳ１０７、Ｓ１０８の前に、階層型サンプリングを実行し、シーケンスのサンプル集合を取り出す。そして、ステップＳ１０９では、シーケンスのサンプル集合を用いて、新たな要素のモデルパラメータΘ1、Θ2を推定する。
【００９７】
＜階層型サンプリング＞
本実施の形態では、スタックを用いたサンプリングアルゴリズムを提案する。最初に、要素Nと、サンプリングに要求されたシーケンスの個数ε(例えばε=b×b)をスタックに格納する。サンプリングアルゴリズムでは、各ステップにおいて2つ組(Np、εp)をスタックから取り出し、取り出された要素Npに属する各部分要素Ncに対して局所的なサンプルの個数εcを決定し、新たな2つ組(Nc、εc)がスタックに格納される。ここで、要素Npに属する全てのシーケンスの個数npと各部分要素Ncに属するシーケンスの個数ncを用いて、部分要素Ncがサンプルとして選択されるか否かが、確率nc/npで決定され、各部分要素に対する選択結果に基づいて、サンプルの個数εcが決定される。
【００９８】
この処理過程は、階層構造の最下層に到達するまで行なわれ、最終的なシーケンスのサンプル集合が得られる。ここで、もし部分要素Ncがサンプルとして選択されなかった場合、(すなわちεc=0)、Nc配下の全ての部分要素は枝刈りされる。
【００９９】
＜インクリメンタルモデル推定＞
上記の第１の実施の形態で説明した重みつきモデル推定(上記（１０）式〜（１１）式参照)は重要な要素技術ではあるが、重みつき期待値を計算するために全ての入力シーケンスを必要とするため、これだけではストリーミングの状況下では充分とは言えない。そこで、本実施の形態では、新たなインクリメンタルなモデル推定方法を導入する。シーケンス集合｛x1、...xn｝を表現するモデルパラメータΘと、新たに追加される入力シーケンスxn+1が与えられたとき、新たなモデルパラメータ~Θは次の方法を用いてインクリメンタルに計算することができる。まずEステップでは、全てのデータセットの期待値を計算する代わりに、新しい入力シーケンスxn+1に対してのみ期待値を計算する。次にMステップでは、以下の（１３）式によって効率的にモデルパラメータを更新する。
【０１００】
【数１０】
2014016731.tif 000012
【０１０１】
ここで、Nγ1=Σnr=1Σkj=1γ(r)1(j)となる。同様にして~aijと~bi(v)も新たな期待値を用いて更新することができる。なお、このインクリメンタルなモデル推定は、既存の手法に比べ、より早く収束に近づく。さらに重要な点として、本発明の計算コストはシーケンスの総数によらないという利点がある。
【０１０２】
＜近似データ更新処理装置の作用＞
次に、第２の実施の形態に係る近似データ更新処理装置２００の作用について説明する。まず、近似データ更新処理装置２００に、シーケンス集合が入力されると、近似データ更新処理装置２００は、時系列データ蓄積部２１に格納する。そして、近似データ更新処理装置２００は、シーケンス集合に基づいて、階層構造のＨＭＭを構築し、階層モデルデータ記憶部２２に格納する。
【０１０３】
そして、近似データ更新処理装置２００に、新たなシーケンスが入力されると、近似データ更新処理装置２００は、上記図４に示す階層モデル更新処理ルーチンと同様の処理ルーチンを実行する。
【０１０４】
このとき、上記ステップＳ１０６において近似時系列データ処理部２２３による分割操作が行われた後に、図６に示す、階層型サンプリング処理ルーチンが実行される。
【０１０５】
まず、ステップＳ２０１において、近似時系列データ処理部２２３は、上記ステップＳ１０６で分割して生成した要素Ｎ1と、サンプリング対象となるシーケンスの個数ε（要素Ｎ1の配下の部分要素に属する全てのシーケンスの個数）との組（Ｎ1、ε）をスタックに入れる。
【０１０６】
そして、近似時系列データ処理部２２３は、スタックが空になるまで、ステップＳ２０２〜ステップＳ２０７までの処理を繰り返す。
【０１０７】
ステップＳ２０２では、近似時系列データ処理部２２３は、スタックから、組（Ｎp、εp）を取り出す。次のステップＳ２０３では、近似時系列データ処理部２２３は、Ｎpが最下層の要素であるか否かを判定し、Ｎpが最下層の要素でない場合には、Ｎpの配下の全ての部分要素Ｎcについて、ステップＳ２０４〜ステップＳ２０６までの処理を繰り返す。
【０１０８】
ステップＳ２０４では、近似時系列データ処理部２２３は、確率nc/npで、部分要素Ｎcに対して局所的なサンプルの個数εcを決定する。ステップＳ２０５では、近似時系列データ処理部２２３は、上記ステップＳ２０４で決定したサンプルの個数εcが、０より大きいか否かを判定する。サンプルの個数εcが、０より大きい場合には、ステップＳ２０６において、組（Ｎc、εc）をスタックに入れて、上記ステップＳ２０４又はステップＳ２０２へ戻るか、あるいは後述するステップＳ２０８へ移行する。
【０１０９】
一方、サンプルの個数εcが、０以下である場合には、部分要素Ｎcがサンプルとして選択されなかったと判断し、上記ステップＳ２０４又はステップＳ２０２へ戻るか、あるいは後述するステップＳ２０８へ移行する。
【０１１０】
また、上記ステップＳ２０３で、Ｎpが最下層の要素であると判定された場合には、ステップＳ２０７において、近似時系列データ処理部２２３は、Ｎpに属するシーケンスの集合から、ランダムにεp個のサンプルを選択し、Ｎ1の配下の全てのシーケンス集合Ｘsに加え、上記ステップＳ２０２へ戻るか、あるいは後述するステップＳ２０８へ移行する。
【０１１１】
ステップＳ２０８では、Ｘsを、Ｎ1の配下の全てのシーケンス集合のサンプリング結果として出力する。
【０１１２】
また、近似時系列データ処理部２２３は、上記ステップＳ１０６で分割して生成した要素Ｎ2について、上記の階層型サンプリング処理ルーチンを同様に実行する。
【０１１３】
そして、上記ステップＳ１０７では、近似時系列データ処理部２２３は、Ｎ1の配下の全てのシーケンス集合のサンプリング結果を、Ｘ１とし、上記ステップＳ１０８では、Ｎ2の配下の全てのシーケンス集合のサンプリング結果を、Ｘ2とする。近似時系列データ処理部２２３は、ステップＳ１０９以降の処理を、同様に実行する。
【０１１４】
また、上記ステップＳ１０５では、近似時系列データ処理部２２３は、上記（１０）式、（１１）式に従って、入力されたシーケンスｘiに対してのみ期待値を計算し、上記（１３）式、及び（１３）式と同様に（４）式、（５）式を変更した式に従って、要素ＮのＨＭＭのモデルパラメータΘを更新する。
【０１１５】
以上説明したように、第２の実施の形態に係る近似データ更新処理装置によれば、分割された要素のモデルパラメータを更新する際に、シーケンスのサンプル集合を用いて更新するため、計算時間とメモリ使用量とを更に削減することができる。
【０１１６】
また、挿入パス上の各要素について、入力された新たなシーケンスのみを用いて、モデルパラメータを更新することにより、計算時間とメモリ使用量とを更に削減することができる。
【０１１７】
＜実施例＞
本発明の有効性を示すために実データを用いた実験を行った。実験は、4GBのメモリ、Intel（Ｒ） Core 2 Duo 1.86GHz のCPUを搭載したLinux（登録商標）マシン上で実施した。なお、推定するHMMはk=20と設定する。Mocapは、1秒120フレームでヒトの動きを計測したモーションキャプチャのデータセットである(http://mocap.cs.cmu.edu/)。図7は、モーションキャプチャデータにおける左右の足の運動エネルギーのシーケンスを例として示しており、それぞれのシーケンスは異なるモーション(walking, squatting, jumping,balancing)を示している。シーケンス集合を用いて、4つのモーションそれぞれに対しHMMのパラメータ推定を行うことを考える。ただし、これらの4つのグループに関する情報は事前に与えられないものとし、アルゴリズムが独自にシーケンス群の中から類似パターンを発見、グループ化し、それらのグループについて個別にパラメータの推定を行うものとする。実験で利用したデータは、2次元のデータを100のグリッドに分割し離散データとして扱った。学習用のデータには、上記の4種類の動き(walking, squatting, jumping,balancing)を使用した。
【０１１８】
図8は、MoCapにおける分類結果を示している。テストセットには、上記4種類の動きに属する2×4個のシーケンス(#1-#8)と、学習データに含まれないrunningのモーションに属する2個のシーケンス(#9and#10)の計10個を用いた。本発明によって、最初の8個のテストセット(#1-#8)に対し、適切なモデルを発見することができた。ここで興味深いことに、本発明ではsquattingとjumpingのモーションが類似していることも示した。実際に、上記図7に示す通り、これらのシーケンスは両者とも、両足を同時に曲げる動きであり、非常に似ている動きであるといえる。同様にして、runningのモーション(#9and #10)がwalkingのモーションと類似していることも示した。学習処理における計算時間を検証するため、本発明を従来技術であるHHMMと比較する。ここでは、次に挙げる2つのバーションのHHMMを比較対象とする。１つは、完全2分木による階層構造を使用する方法（図９のHHMM(b=2)参照）であり、もう一つは、完全4分木による階層構造を使用する方法（図９のHHMM(b =4)参照）である。さらに、本発明についても2つのバーションについて比較を行った。１つは、本発明におけるストリーミング処理による学習方法（図９のHEART参照）であり、もう１つは、本発明におけるベーシックなアイデアに基づく学習方法(サンプリング法を使用しない場合であり、図９のHEART(offline)を参照)である。本実験において、本発明における計算時間にはディスクアクセスによる時間も含まれている。図9は、HHMMと本発明の計算コストを示している。データセットのサイズ(すなわち全てのシーケンスの合計長)は1,000から200,000まで変動させた。本実験では、シーケンスの長さをm=100に固定した。図に示す通り、本発明は従来技術に比べ大幅な高速化を達成している。
【０１１９】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１２０】
例えば、時系列データは、映像や音楽配信、バイオインフォマティックス、ロボットなど様々な分野で発生する。本発明はこれら全ての分野に適用可能である。
【０１２１】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１２２】
１０   入力部
２０、２２０  処理部
２１   時系列データ蓄積部
２２   階層モデルデータ記憶部
２３   時系列データ処理部
３０   出力部
１００ データ更新処理装置
２００ 近似データ更新処理装置
２２３ 近似時系列データ処理部
【図１】
2014016731.tif 000013
【図２】
2014016731.tif 000014
【図３】
2014016731.tif 000015
【図４】
2014016731.tif 000016
【図５】
2014016731.tif 000017
【図６】
2014016731.tif 000018
【図７】
2014016731.tif 000019
【図８】
2014016731.tif 000020
【図９】
2014016731.tif 000021