隠れマルコフモデル探索装置及び方法及びプログラム
【課題】 離散型隠れマルコフモデルの探索コストを低減する。
【解決手段】 本発明は、シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れマルコフモデルについて、近似の粒度を固定して、それぞれの粒度に対する尤度を計算し、計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算を繰り返し、該閾値より小さくなった尤度を新たな解候補として探索結果記憶手段に格納する。
【解決手段】 本発明は、シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れマルコフモデルについて、近似の粒度を固定して、それぞれの粒度に対する尤度を計算し、計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算を繰り返し、該閾値より小さくなった尤度を新たな解候補として探索結果記憶手段に格納する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、隠れマルコフモデル探索装置及び方法及びプログラムに係り、特に、与えられた問い合わせシーケンスまたはデータストリームのサブシーケンスに対して、隠れマルコフモデルのデータ集合の中からモデルを探索するための隠れマルコフモデル探索装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
隠れマルコフモデル（HMM: Hidden Morkov Model）の基礎的理論は主として１９６０年代に研究されている。HMMはシーケンスを確率的密度関数に従う発生モデルを有する状態の遷移として表現するデータモデルであり、ノイズに強い特長がある。このためＨＭＭは音声認識、自然言語処理、遺伝子解析などの多くのアプリケーションにおいて使われている。
【０００３】
HMMにおける探索手法、特に問い合わせシーケンスに対する探索手法としては、モデルを並び替えてからひとつひとつを粒度を細かくして探索する方法がある（例えば、特許文献１、非特許文献１参照）。
本発明は、与えられた問い合わせシーケンスまたはデータストリームのサブシーケンスに対してデータ集合の中からモデルを探索する問題を対象とする。探索はモデルによって推定される尤度によって行われる。
【０００４】
本発明を適用可能なビデオメタデータサービスについて述べる。近年、ＰＳＰ（Play Station Portable）（登録商標）、iPod（登録商標）、ＡＶ５００などが双方向型のビデオ再生のためのプラットフォームになりつつある。ビデオがデジタルの形でローカルのハードディスクに格納されたり、インターネット上で配信されれば、今までにない新しいビデオの視聴の仕方が可能になる。例えば、視聴者は好きな部分でビデオを停止し、また再生することができる。また、ローカルにビデオを格納することにより、ランダムアクセスにビデオを再生することができる。さらに、ビデオに関連付けられたメタデータと視聴者の興味を用いることにより更に進んだ視聴が可能となる。例えば、２時間のニュース番組にメタデータが関連付けられていれば、その中の１０分間の天気予報だけを視聴することができ、大きな時間の節約になる。また、サッカー番組にメタデータが関連付けられていれば、ゲームの最も盛り上がるゴールシーンのみを視聴することもできる。過去の研究に見られるようにモデルを尤度によって選択することによってビデオシーンにメタデータを関連付けることができる。ビデオの内容と視聴者の興味によりパーソナライズされたメタデータは、視聴者のビデオデバイスの中で関連付けられる。
【０００５】
連続型ＨＭＭの探索問題は音声認識の分野で多く研究されてきた。それは音声認識の処理時間の多く（３０〜７０％）が連続型ＨＭＭの尤度の計算にかかるからである。連続型ＨＭＭの状態は典型的に８〜６４個のガウス関数で構成され、尤度計算するにはそれぞれのガウス関数を別々に計算しなければならない。計算コストを落とすためにHuntらは線形判別分析によりガウス関数の数を減らす手法を提案した。また、尤度が既に計算されたガウス関数の部分セットのみ用いる手法も示されている。嵯峨山らやRamachandrulaらは連続型ＨＭＭを離散型ＨＭＭに置き換える手法を提案した。離散型ＨＭＭの尤度はスカラ量子化された確率のテーブルを引くことで計算できる。これらの研究は発明の手法と併用することにより、より効果的かつ高速な探索が可能となる。
【０００６】
また、隠れマルコフモデルにおける探索手法として、問い合わせシーケンスに対する探索手法がある。この手法はモデルを並び替えてから一つ一つを粒度を細かくして探索するものである（例えば、特許文献1、非特許文献1参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−９６７４２号公報
【非特許文献】
【０００８】
【非特許文献１】Yasuhiro Fujiwara, Yasushi Sakurai, Masashi Yamamuro: "Special: Efficient and Exact Model Identification for Hidden Markov Models", In Proceeding of the 14th ACM SIGKDD International Conference on Knowledge discovery and Data Mining.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
一般的に離散型ＨＭＭであっても尤度計算するには、状態の数が多くまたデータ集合の規模が大きいため、多くの処理時間がかかる。そこで、離散型ＨＭＭの探索コスを低減することが必要となる。
【００１０】
本発明は、上記の点に鑑みなされたもので、以下の２つの点を解決し、上記の特許文献１、非特許文献1の手法よりさらに高速な隠れマルコフモデル探索装置及び方法及びプログラムを提供することを目的とする。
【００１１】
（１）離散型ＨＭＭのデータセットと問い合わせシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）が与えられたとき、シーケンスＸに対して最も高い尤度を与えるモデルを検索する。
【００１２】
（２）離散型ＨＭＭのデータセットとデータストリームから切り出されたサブシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）（ｘｎは最新のシーケンスの値とする）が与えられたとき、サブシーケンスＸに対して最も高い尤度を与えるモデルを検索する。
【課題を解決するための手段】
【００１３】
図１は、本発明の原理を説明するための図である。
【００１４】
本発明（請求項１）は、問い合わせシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索装置であって、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段１２０と、
データ記憶手段１２０から読み出された検索対象である隠れマルコフモデルについて、与えられた粒度に対する尤度を計算する尤度計算手段１１２と、
近似の粒度を固定して、それぞれの粒度における尤度を尤度計算手段１１２に計算させ、計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算手段１１２を実行させ、得られた尤度を新たな解候補として探索結果記憶手段１１３に格納する計算判定手段１１１と、を有する。
【００１５】
本発明（請求項２）は、データストリームのサブシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索装置であって、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段と、
データ記憶手段から読み出された検索対象である隠れマルコフモデルについて、与えられた粒度に対する尤度を計算する尤度計算手段と、
探索におけるはじめの解の候補として1時刻前の解を探索結果記憶手段に格納し、それぞれのモデルの１時刻前の粒度より１つ荒い粒度に対する尤度を尤度計算手段に計算させ、該尤度計算手段で計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算手段を実行させ、得られた尤度を新たな解候補として該探索結果記憶手段に格納する計算判定手段と、を有する。
【００１６】
図２は、本発明の原理を説明するための図である。
【００１７】
本発明（請求項３）は、問い合わせシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索方法において、
コンピュータが、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れマルコフモデルについて、近似の粒度を固定して、それぞれの粒度における尤度を計算し（ステップ１，２）、
計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算を繰り返し（ステップ３）、得られた尤度を新たな解候補として探索結果記憶手段に格納する（ステップ４）。
【００１８】
本発明（請求項４）は、データストリームのサブシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索方法において、
コンピュータが、
１時刻前の解を始めの解の候補として探索結果記憶手段に格納しておき、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れマルコフモデルについて、それぞれのモデルに対する1時刻前の粒度より１つ荒い粒度に対する尤度を計算し、
計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで尤度の計算を繰り返し、得られた尤度を新たな解候補として探索結果記憶手段に格納する。
【００１９】
本発明（請求項５）は、請求項1または２に記載の隠れマルコフモデル探索装置を構成する各手段としてコンピュータを機能させるための隠れマルコフモデル探索プログラムである。
【発明の効果】
【００２０】
上記のように本発明によれば、以下のような効果を奏する。
【００２１】
・高速処理：モデルのデータ集合が大きくても高速に探索が可能である。
【００２２】
・探索漏れ無し：本発明の手法により探索されたモデルは厳密に正確である。
【００２３】
・モデルの構造に制限なし：モデルには複数の構造があるが、どの構造でも探索が可能である。
【００２４】
本発明では、高速な探索を探索結果の厳密性を両立させるために、尤度を近似して探索の解候補を絞り込んでから厳密な尤度を計算する。本発明では、データ集合の中から必要最低限のものに対してのみ厳密な尤度を計算するので、高速処理が可能となる。
【図面の簡単な説明】
【００２５】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の一実施の形態における隠れマルコフモデル探索装置の構成図である。
【図４】本発明の一実施の形態における探索部の構成図である。
【図５】ＨＭＭの種類を示す図である。
【図６】トレリス構造を示す図である。
【図７】本発明における手法の概要である。
【図８】本発明の一実施の形態における尤度の計算アルゴリズムである。
【図９】本発明の一実施の形態における問い合わせシーケンスに対する探索処理のアルゴリズムである。
【図１０】本発明の一実施の形態におけるデータストリームに対する探索処理のアルゴリズムである。
【図１１】関連文献における探索手法との比較である。
【図１２】実験におけるデータストリームに対する探索処理時間を示す図である。
【発明を実施するための形態】
【００２６】
以下、図面と共に本発明の実施の形態を説明する。
【００２７】
本発明は、与えられた問い合わせシーケンスまたはデータストリームのサブシーケンスに対してデータ集合の中からモデルを探索する問題を対象とする。探索はモデルによって推定される尤度によって行われる。
【００２８】
本発明を適用可能なビデオメタデータサービスについて述べる。近年、ＰＳＰ（Play Station Portable）（登録商標）、iPod（登録商標）、ＡＶ５００などが双方向型のビデオ再生のためのプラットフォームになりつつある。ビデオがデジタルの形でローカルのハードディスクに格納されたり、インターネット上で配信されれば、今までにない新しいビデオの視聴の仕方が可能になる。例えば、視聴者は好きな部分でビデオを停止し、また再生することができる。また、ローカルにビデオを格納することにより、ランダムアクセスにビデオを再生することができる。さらに、ビデオに関連付けられたメタデータと視聴者の興味を用いることにより更に進んだ視聴が可能となる。例えば、２時間のニュース番組にメタデータが関連付けられていれば、その中の１０分間の天気予報だけを視聴することができ、大きな時間の節約になる。また、サッカー番組にメタデータが関連付けられていれば、ゲームの最も盛り上がるゴールシーンのみを視聴することもできる。過去の研究に見られるようにモデルを尤度によって選択することによってビデオシーンにメタデータを関連付けることができる。ビデオの内容と視聴者の興味によりパーソナライズされたメタデータは、視聴者のビデオデバイスの中で関連付けられる。
【００２９】
連続型ＨＭＭの探索問題は音声認識の分野で多く研究されてきた。それは音声認識の処理時間の多く（３０〜７０％）が連続型ＨＭＭの尤度の計算にかかるからである。連続型ＨＭＭの状態は典型的に８〜６４個のガウス関数で構成され、尤度計算するにはそれぞれのガウス関数を別々に計算しなければならない。計算コストを低減するためにHuntらは線形判別分析によりガウス関数の数を減らす手法を提案した。また、尤度が既に計算されたガウス関数の部分セットのみ用いる手法も示されている。嵯峨山らやRamachandrulaらは連続型ＨＭＭを離散型ＨＭＭに置き換える手法を提案した。離散型ＨＭＭの尤度はスカラ量子化された確率のテーブルを引くことで計算できる。これらの研究は発明の手法と併用することにより、より効果的かつ高速な探索が可能となる。本発明では、これらの手法を併用し、
（１）モデルの状態を結合し、尤度の上限値により高速に解候補を絞り込み、
（２）モデルを様々な近似の粒度で探索し、
（３）モデルの尤度計算を打ち止めて、尤度の低いモデルを高速に枝刈りする。
【００３０】
以下に、本発明の詳細について述べる。
【００３１】
図３は、本発明の一実施の形態における隠れマルコフモデル探索装置の構成を示す。
【００３２】
隠れマルコフモデル探索装置１００は、探索部１１０とデータ格納部１２０を有する。
【００３３】
データ格納部１２０は、探索対象となる隠れマルコフモデルが格納されたデータベース等の記憶媒体である。探索部１１０は、隠れマルコフモデルの探索を行う。図４に示すように、探索部１１０は、計算判定部１１１、尤度計算部１１２、探索結果保存部１１３から構成される。計算判定部１１１は、与えられた粒度で尤度計算部１１２に尤度を計算させ、所定の閾値と計算された近似尤度を比較して、その結果に基づいて尤度計算部１１２に再計算させる、または、再計算を終了させる。計算された尤度と探索結果保存部１１３に格納されている解の候補と比較して、計算された尤度が格納されている解の候補より高い尤度であれば、探索結果保存部１１３の解の候補を更新する。尤度計算部１１２は、計算判定部１１１における判定結果を受けて、隠れマルコフモデルの近似尤度または正確な尤度を計算する。なお、尤度計算部１１２は図示しないが、途中の解を格納するためのメモリを具備するものとする。探索結果保存部１１３は、メモリやハードディスク装置等の記憶媒体であり、探索処理における解候補の保存を行う。
【００３４】
ＨＭＭはシーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現するデータモデルである。
【００３５】
以下に、本明細書で用いる主な記号とその定義を示す。
【００３６】
Ｋ：k-近傍探索のパラメータ；
ｘｔ：時刻ｔ（ｔ＝１，…，ｎ）のシーケンスＸの値；
ｕｉ：ＨＭＭのｉ（ｉ＝１，…，ｍ）番目の状態
ｎ：シーケンスＸの長さ；
ｍ：状態の数；
α＝｛αｉ｝：ｕｉの初期遷移確率；
β＝｛βｉ｝：ｕｉからｕｊの状態遷移確率；
γ（ｖｊ）＝｛γｉ（ｖｊ｝：状態ｕｉにおけるシンボルｖｊ（ｊ＝１，…，ｓ）のシンボル出力確率；
Φ：正確な尤度；
Ψ：近似尤度
本発明は、以下の２つの問題を対象とする。
【００３７】
問題１：離散型ＨＭＭのデータセットと問い合わせシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）が与えられたとき、シーケンスＸに対して最も高い尤度を与えるモデルを検索する。
【００３８】
問題２： 離散型ＨＭＭのデータセットとデータストリームから切り出されたサブシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）（ｘｎは最新のシーケンスの値とする）が与えられたとき、サブシーケンスＸに対して最も高い尤度を与えるモデルを検索する。
【００３９】
本発明の手法を説明する前に簡単にＨＭＭについて説明する。ＨＭＭは以下の要素で構成される。
【００４０】
初期状態確率：α＝｛αｉ｝時刻１において状態がｕｉ（ｉ＝１，…，ｍ）である確率。
【００４１】
状態遷移確率：β＝｛βij｝時刻が１つ進んだときに状態ｕｉから状態ｕｊへ遷移する確率。
【００４２】
シンボル出力確率：γ（ｖｊ）＝｛γｉ（ｖｊ）｝状態ｕｉにおいてシンボルｖｊを出力する確率（ｊ＝１，…，ｓ）。
【００４３】
ＨＭＭを説明するために壷とボールの例を用いる。
【００４４】
赤や青などの色のついたボールが入っている壷が複数あることを考える。はじめにある確率によって壷を選ぶ。そしてボールを一つ取り出し、その色を記録する。次の壷は現在の壷の選択によって関連付けされた確率に従って選択する。そしてボールの色の記録を繰り返す。これらの操作によってボールの色の系列が得られる。
【００４５】
この例において、壷は状態に対応し、色の系列はシーケンスに対応する。すなわち初期状態確率は初めに選択する壷の確率であり、状態遷移確率は次の壷の選択確率であり、シンボル出力確率はどの色のボールを選択するかの確率である。
【００４６】
ＨＭＭは図５のように状態遷移確率βの構造によって分類することができる。図５において白い円は「状態」を表し、矢印は「遷移」を表す。全ての状態から他の全ての状態へ遷移できるタイプとして全結合ＨＭＭとエルゴディックＨＭＭ（図５（ａ））がある。エルゴディックＨＭＭは全結合ＨＭＭを包含し、全ての状態が他の全ての状態へ有限であるが、非周期的な回数で遷移できる特徴がある。１回で任意の状態に遷移できるエルゴディックＨＭＭや全結合ＨＭＭにおいて状態遷移確率βは、正の係数βijを用いて以下のようになる。
【００４７】
【数１】
また、他のタイプとしてleft-right HMM（図５（ｂ））がある。left-right HMMは状態を並べたときに左から右へ遷移する特徴がある。状態遷移確率の係数はj＜ｉのときβij＝０となり、ｉ≠１でαｉ＝０となる。また、left-right HMMにおいては状態間を多く遷移しないように制約が課せられていることがあり、状態遷移確率の係数はｊ＞ｉ＋△―１のときβij＝０となる。例えば、状態遷移確率βは△＝３のときβijを用いて以下のようになる。
【００４８】
【数２】
シーケンスＸの尤度Φは、Viterbiアルゴリズムにより計算される。先の壷とボールの例では尤度の計算は、ボールの系列が与えられた時にそれを出力する。壷の遷移の最大確率を計算することに対応する。尤度は以下のように求める。
【００４９】
【数３】
Viterbiアルゴリズムでは、図６のように状態を縦軸に、時間を横軸に並べたときに構成されるトレリス構造において、各状態における確率の最大値を動的計画法によって求めている。
【００５０】
以下に、探索部１１０の具体的な動作を説明する。
【００５１】
［例１］
モデルとシーケンスが以下のようであるとする。
【００５２】
【数４】
Viterbiアルゴリズムは以下のように計算される。
【００５３】
φ11＝1，φ12＝0.5， φ13＝0， φ14＝0
φ21＝0，φ22＝0.75・0.5，φ23＝(0.5)2。・0.25， φ25＝0
φ31＝0，φ32＝0， φ33＝0， φ34＝(0.5)2・(0.25)2
結果的に尤度はΦ＝(0.5)3・(0.25)2となり、その尤度を与える状態遷移はｕ１，ｕ１，ｕ２，ｕ３となる。尤度計算部１１２は、上記のようにして求めた尤度と状態遷移を計算判定部１１１に渡す。これにより、計算判定部１１１は、探索結果保存部１１３に格納されている解の候補と計算された尤度とを比較して、尤度が解の候補より大きい場合には、当該尤度で探索結果保存部１１３の値を更新する。
【００５４】
ＨＭＭの構造に制約がない場合、すなわちエルゴディックＨＭＭの場合のViterbiアルゴリズムの計算量はＯ（nm2）となる。これは全ての状態において、前の時刻の状態全てから遷移する確率を計算するからである。そのためナイーブに全てのモデルの尤度を計算するには、特にモデルの状態数が多くまたモデルの数が多いと莫大な計算コストがかかる。ナイーブに解く手法を今後「Naive Viterbi」と表現する。
【００５５】
探索部１１０の計算判定部１１１は、以下の３つの機能を有する。まず、概要を示し、その後に各々の詳細について述べる。
【００５６】
●トレリス構造の縮退：
先に述べたとおり、トレリス構造が大きい場合Viterbiアルゴリズムは高い計算コストを必要とする。そこで、図７に示すように、計算判定部１１２では、状態をクラスタリングし、結合することによって状態の数を削減する。この状態数の削減により、トレリス構造は縮退され、高速に尤度を計算することが可能になる。トレリス構造を縮退させるために粒度ｑが与えられたとき、ｍ個の状態はｍ／ｇ個に削減される。この結果、尤度計算部１１２の尤度の計算量はＯ（nm2/g2）に低減化される。
【００５７】
トレリス構造を縮退することには２つのメリットがある。まずはじめのメリットはトレリス構造を縮退して探索を行っても探索漏れは発生しないことが保証されることである。これは後に示すとおり縮退後の近似尤度は厳密な尤度より小さくならないためである。そのため近似尤度を計算するのみで、探索結果の候補を少ない計算コストで得ることができる。
【００５８】
２番目のメリットとして、どのようなタイプのモデルにも適用できることが挙げられる。これは状態をクラスタリングするときにモデルの確率の制約を用いないからである。
【００５９】
●複数の近似粒度：
トレリス構造を縮退することで計算される近似尤度により高速な探索が可能になるが、近似計算には近似精度と計算時間のトレードオフが存在する。すなわちトレリス構造を過度に縮退させると、尤度計算部１１２の近似尤度の計算コストは小さくなるが、近似尤度の上限値は大きくなってしまう。そのため、本発明では、探索処理において徐々にトレリス構造のサイズを大きくしていき、近似尤度の精度を上げていく。
【００６０】
複数の近似粒度を用いることでモデルの厳密な尤度に応じた近似粒度で計算させることができる。尤度が小さいモデルは低い粒度の近似で枝刈りすることができるが、尤度が大きいモデルは高い粒度の近似でないと枝刈りができない。言い換えれば低い粒度で枝刈りした結果として高い尤度のモデルを得られる。そのため本発明では、低い粒度の結果のみに対して高い粒度の近似を計算する。結果として相反する近似精度と計算時間のバランスをとることができる。
【００６１】
●状態遷移の枝刈り：
本発明は、探索結果の厳密性を保証している。トレリス構造を縮退することにより高速な探索が可能になるが、厳密に正確な探索結果は近似尤度からは求めることができない。そのため、本発明では、近似尤度で求めた候補に対して厳密な尤度を求めている。しかし、厳密な尤度を計算するには大きなコストがかかる。
【００６２】
本発明では、尤度計算の中には探索処理として必要のないものも含まれるため、図７のようにトレリス構造における尤度計算を高速に打ち切る。例えば、後段の［例１］において探索途中の解の候補の尤度が0.2５であるときに、時刻１における状態ｕ２とｕ３の尤度は0.25より小さいため、時刻２においてこれらの状態から遷移する確率は計算する必要はない。同じように時刻３において状態ｕ３からの確率は計算する必要はない。時刻３において全ての状態の確率は0.25より小さいため、尤度計算を打ち切ることができる。
【００６３】
探索途中のＫ番目に高い尤度が大きくなるほど、より効果的に計算を打ち切ることができる。ここで、Ｋ番目に高い尤度は探索処理が進むほど大きくなるので、結果的にモデルの数が多くても効果的に探索することができる。
【００６４】
また、計算の途中では尤度は単調減少するため、問い合わせのシーケンスが長くなるほど状態遷移の打ち切りは効果的になる。これは、ユーザやアプリケーションによって問い合わせの長さが異なることを考えると、非常に有効な性質である。
【００６５】
また、状態遷移の打ち切りは厳密なトレリス構造のみに対してではなく、縮退後のトレリス構造に対しても適用できる。すなわち、状態遷移を打ち切ることで、近似計算を高速化できる。
【００６６】
●トレリス構造の縮退：
本発明ではモデルのオリジナルの状態を結合することによりトレリス構造を縮退して、尤度計算部１１２に近似尤度を計算させる。近似尤度で枝刈りを行っても探索漏れは発生しないことが保証される。
【００６７】
粒度ｇが与えられたとき、状態をクラスタリングし結合することで、ｍ・ｎのトレリス構造をｍ／ｇ・ｎに縮退する。状態ｕｉとｕｊが同じクラスタになった場合、結合によって得られた状態uｉ´の確率を各要素の確率の中で最大値を用いて以下のように定義する。
【００６８】
［定義１］
状態uｉとuｊが同じクラスタになった場合、結合後の確率は
α´i＝max（αi，αj）；
β´ii＝max（βii，βij，βji，βjj），
β´ik＝max（βik，βjk），
β´ki＝max（βki，βkj）（k≠i，k≠j）；
γ´i (ｖk)=max（γi (ｖk)，γj (ｖk)）
となる。
【００６９】
［例１］
例1のＨＭＭにおいて状態ｕ１とｕ２が同じクラスタになった後の確率は以下のようになる。
【００７０】
【数５】
上記の例において、確率はそれぞれ、
α´1=max(α1，α2)，
β´11=max(β11，β12，β21，β22)，
β´12=max(β13，β23)，
β´21=max(β31，β32)，
γ´1(1)=max(γ1(1)，γ2(1))，
γ´1(2)=max(γ1(2)，γ2)(2))，
γ´1(3)=max(γ1(3)，γ2(3))
と計算する。２つの状態が同じクラスタになる場合について説明したが、３つ以上の場合でも同様に計算する。
【００７１】
クラスタリングを行うために、状態の特徴量Ｆiを以下のように定義する。
【００７２】
［定義２］
Fｉ=（αi：βi1,…，βim，β1i，…，βmi；γi (ｖ1)，…，γi (ｖｓ)）． （４）
状態をクラスタリングするため、k-means法（文献：J. MacQueen, Some methods for classification and analysis of multivariate observations., 1967）を用いる。トレリス構造を縮退する手法は、クラスタリング方法の選択とは完全に独立したものであるため、他のクラスタリング方法（例えば、BIRCH： Tian Zhang and Raghu Ramakrishnan and Miron Livny， BIRCH： An Efficient Data Clustering Method for Very Large Databases, SIGMOD Conference, 1996）を用いることも可能である。
【００７３】
状態を結合することにより厳密なトレリス構造の縦のサイズを減らすことができる。すなわち、［例１］のトレリス構造の縦のサイズは"３"であるが、［例１］のサイズは"２"である。トレリス構造の横のサイズを減らすには、後述するように、状態遷移の枝刈りを用いる。
【００７４】
尤度計算部１１２は、近似尤度Ψを、結合後の状態数ｍ´（=m/g）と確率α´、β´、γ´（ｖ）を用いて以下のように計算する。
【００７５】
【数６】
近似尤度の計算量はＯ(nm2/g2)となる。これはViterbiアルゴリズムと同様にｎ個の各時刻においてｍ／ｇ個の状態の中から最大の確率を有するものを選択するからである。
【００７６】
Ψは厳密なトレリス構造による尤度Φの上限値となる。
【００７７】
［補助定理１］
状態を結合後のモデルとシーケンスが与えられたとき、以下の関係が成立する。
【００７８】
Φ≦Ψ （６）
［証明１］
オリジナルの状態ｕi(1≦ｉ≦ｍ)が状態ｕ´i(1≦ｉ≦ｍ´)へクラスタリングされたとすると、
φi1≦α´i・γ´i(ｘ1)＝ψi1
となるので、２≦ｔ≦ｎのとき、
【００７９】
【数７】
よって、
【００８０】
【数８】
が成り立つ。
【００８１】
上記の［補助定理１］の性質を用いて探索漏れなくモデルを探索することができる。
【００８２】
［補助定理２］
Ψを用いて探索することは、探索漏れが発生しないことの十分条件である。
【００８３】
［証明２］
解の尤度をεとしたとき、探索漏れが発生しないことを保証するためには、Φ≧εであるときΨ≧εでなければならない。ところで式（６）より、
ε≦Φ≦Ψ
となるので探索漏れは発生しない。
【００８４】
●複数の近似尤度：
これまでは一つの粒度でトレリス構造を縮退し近似尤度を計算することを前提に説明した。しかし、近似の粒度が低ければ近似精度も低くなるなど、近似の粒度が異なればその精度も異なるため、モデル毎の厳密な尤度に応じて近似の粒度が異なることが望ましい。そのため、本発明では一つの粒度ではなく、複数の粒度の近似を用いてモデルを探索する。すなわち、計算判定部１１１は、探索において徐々に近似粒度を上げて尤度計算部１１２に尤度計算させていく。
【００８５】
本発明では、ｈ個の粒度を用いる。レベルｉ（１≦ｉ≦ｈ）の近似においては粒度ｇｉを用いて、ｍ個の状態を
【００８６】
【数９】
個に結合する。最も粗い粒度をｇ1とすると、レベルが上がるにつれてｇ1も大きくなり、近似尤度の精度も上がっていく。
【００８７】
尤度計算部１１２は、まずレベル1の
【００８８】
【数１０】
個に状態を結合した近似尤度を全てのモデルに対して計算する。近似尤度によって解の候補を求めて、その厳密な尤度εを計算する。εより小さい近似尤度を持つモデルは枝刈りできる。そうでないモデルに対しては、尤度計算部１１２でレベル２の近似尤度を計算し、計算判定部１１１において、同様に近似尤度がεより小さいか調べる。この操作をレベルがｈになるまで行う。結果的にモデルを厳密な尤度に従った近似の尤度に従った近似の粒度によって枝刈りすることができる。複数の近似尤度によるアルゴリズムは探索アルゴリズムと共に後述する。
【００８９】
●状態遷移の枝刈り：
本発明では、状態遷移の枝刈りに関しては２つの重要な性質を用いる。第一に尤度を計算するときに、各状態の尤度は既に遷移した過去の時刻の全ての状態の尤度より大きくならない。これは各状態の尤度は以前の時刻の尤度を用いて計算されるためである。
【００９０】
第二に、探索処理においては解候補を保持し、新たにεより高い尤度のモデルが見つかったとき解候補を更新するため、εは大きくなり続ける。
【００９１】
この２つの性質を用いて尤度の計算において枝刈りを行うが、枝刈りするための推定値ψitを以下のように導入する。
【００９２】
【数１１】
ここで、βmaxとγmax(v)は以下のように状態遷移確率とシンボル出力確率の最大値である。
【００９３】
【数１２】
推定値ψitはViterbiパスが時刻ｔで状態ｕiを通るとしたときの尤度の上限値となる。
【００９４】
［定理１］
φin≦ψit （９）
尤度の計算において枝刈りは推定値ψitを用いて行う。すなわち、εより推定値が小さい状態からの遷移は計算しない。厳密なトレリス構造に対する状態遷移の枝刈りのアルゴリズムを図８に示す。状態遷移の枝刈りでは遷移集合を用いて処理を行う。遷移集合はトレリス構造のそれぞれの時刻毎に設定される。時刻ｔの状態ｕiの推定値がε以上であれば、時刻ｔの遷移集合に状態ｕiが加えられる。尤度を計算するときは時刻ｔ−１の遷移集合に含まれる状態からの遷移のみを用いる。もしある時刻における遷移集合が空集合であれば、そのモデルは解集合となりえないため、尤度計算を打ち切る。近似尤度の計算においても同様のアルゴリズムで処理を行う。
【００９５】
●探索処理：
前述の通り、Naive Viterbiを処理するには大きな計算量を要する。本発明では高速に解を求めるために近似尤度を用いて尤度の低い殆どのモデルの枝刈りを行う。計算コストのかかる厳密な尤度計算は必要最低限に限定される。
【００９６】
問い合わせシーケンスに対する探索処理と、データストリームに対する探索処理は以下の通りである。
【００９７】
（１）問い合わせシーケンスに対する探索処理：
探索処理においては、計算判定部１１１において近似の粒度を固定し、尤度計算部１１２においてそれぞれの粒度における解の候補を計算する。具体的には探索処理ではまず全てのモデルに対して最も粗い近似尤度を計算する。最も高い近似尤度を与えるモデルを解の候補として、そのモデルの厳密な尤度を計算する。その厳密な尤度によってモデルの枝刈りを行い、残ったモデルに対して２番目の粒度の近似尤度を計算する。最も高い近似尤度を与えるモデルの厳密な尤度を計算し、もし、計算判定部１１１は、探索結果保存部１１３に格納されている1番目の粒度による解の候補より高い尤度だったら、当該探索結果保存部１１３の解の候補を更新する。同様の処理を粒度を細かくしながら続けていく。
【００９８】
探索処理のアルゴリズムを図９に示す。同図において、Φiは粒度giの尤度を示す。なお、ここでΦ0は厳密な尤度とする。また、Mはモデルの集合を表す。
【００９９】
（２）データストリームに対する探索処理：
データストリームは時々刻々と変化していくが、その変化の割合はそれほど多くはないことに着目した処理を行う。具体的には、計算判定部１１１は、それぞれのモデルに対する近似の粒度を1時刻前の粒度より１つ荒い粒度にし、また、探索におけるはじめの解の候補として1時刻前の解を用いる。その他の処理は問い合わせシーケンスに対する探索処理と同様であるので、その説明を省略する
当該データストリームに対する探索処理のアルゴリズムを図１０に示す。同図において、Miは粒度ｇiの尤度を計算するモデルの集合を示し、M´iは1つ前の時刻において計算した最も細かい粒度がｇiであるモデルの集合とする。
【０１００】
≪評価実験≫
本発明の有効性を示すために実験を行った。実験はエルゴディックＨＭＭとleft-right HMMに対して行った。実験では探索におけるＣＰＵの計算時間を比較した。
【０１０１】
実験は、Intel Xeon quad CPU 3.33 GHz、メインメモリが３２GBのマシンで行った。
【０１０２】
実験データは以下のものを用いた。
【０１０３】
・ＥＥＧ：
このデータセットはＥＥＧとアルコール依存症の関係を調べるために行われた大規模な実験で得られたものであり、ＵＣＩのＷｅｂサイトからダウンロードすることができる（http://www.ncbi.nlm.nih.gov）。
【０１０４】
・Chromosome：
人間の第2，18，21，22番遺伝子のデータであり、NCBIのＷｅｂサイトから得ることができる（http://archive.ics.uci.edu/ml/）。
【０１０５】
・Traffic：
このデータセットはＵＣＩのＷｅｂサイトから得たフリーウェイ交通量の測定値である（http://www.ncbi.nlm.nih.gov）。
【０１０６】
・ＵＮＩＸ：
このデータセットはＵＣＩのＷｅｂサイトから得たＵＮＩＸの操作履歴である（http://www.ncbi.nlm.nih.gov）。
【０１０７】
状態数を変化させて実験を行った。実験ＩＣおいてシーケンスの長さｍ＝２５６とした。
【０１０８】
（１）問い合わせシーケンスに対する従来技術との比較：
隠れマルコフモデルにおける探索手法、特に、問い合わせシーケンスに対する探索手法として、前述の特許文献１、非特許文献1に記載の技術がある。これらの文献における手法は、モデルを並び替えてから一つ一つ粒度を細かくし探索する特徴がある。
【０１０９】
本発明の手法の優位性を示すためにそれぞれの手法における探索処理の時間の比較実験を行った。実験結果を図１１に示す。実験において状態数を１００とし、モデルの数を１００００とした。図１１において「SPIRAL」とあるのは本発明による手法、「Sort」とあるのは特許文献１、非特許文献1による手法とする。
【０１１０】
本発明の手法は、特にエルゴディックHMMに対して有効であることがわかる。O(nm2)だけのコストが誘導を計算する時に必要になるが、粒度毎に解候補を計算することでその計算コストを低減することができることがわかる。本発明による手法は、特許文献１、非特許文献1による手法に対して３０倍まで高速な探索を行うことができた。
【０１１１】
（２）データストリームに対する探索処理時間：
本実験ではストリームに対応したアルゴリズムと問い合わせシーケンスに対応したアルゴリズム、及びViterbiアルゴリズムとの比較を行った。それぞれのアルゴリズムの実験結果をStream-SPIRAL、SPIRAL、Viterbiとして図12に示す。実験において状態数を１００とし、モデルの数を１００００とした。
【０１１２】
ストリームに対応したアルゴリズムはその他のアルゴリズムに対して優位であり、特にViterbiアルゴリズムに対しては４９０倍高速であることが確認された。ストリームに対応したアルゴリズムは問い合わせシーケンスに対応したアルゴリズムとおおよそ同様であるが、解候補と粒度の決定方法が異なる。これらの決定方法が探索処理時間に大きな影響を与えることがわかる実験結果になった。
【０１１３】
また、上記の探索部１１０の動作をプログラムとして構築し、隠れマルコフモデル探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１１４】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１１５】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１１６】
本発明は、ビデオメタサービスに適用可能である。
【符号の説明】
【０１１７】
１００ 隠れマルコフモデル探索装置
１１０ 探索部
１１１ 計算判定手段、計算判定部
１１２ 尤度計算手段、尤度計算部
１１３ 探索結果記憶手段、探索結果保存部
１２０ データ記憶手段
【技術分野】
【０００１】
本発明は、隠れマルコフモデル探索装置及び方法及びプログラムに係り、特に、与えられた問い合わせシーケンスまたはデータストリームのサブシーケンスに対して、隠れマルコフモデルのデータ集合の中からモデルを探索するための隠れマルコフモデル探索装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
隠れマルコフモデル（HMM: Hidden Morkov Model）の基礎的理論は主として１９６０年代に研究されている。HMMはシーケンスを確率的密度関数に従う発生モデルを有する状態の遷移として表現するデータモデルであり、ノイズに強い特長がある。このためＨＭＭは音声認識、自然言語処理、遺伝子解析などの多くのアプリケーションにおいて使われている。
【０００３】
HMMにおける探索手法、特に問い合わせシーケンスに対する探索手法としては、モデルを並び替えてからひとつひとつを粒度を細かくして探索する方法がある（例えば、特許文献１、非特許文献１参照）。
本発明は、与えられた問い合わせシーケンスまたはデータストリームのサブシーケンスに対してデータ集合の中からモデルを探索する問題を対象とする。探索はモデルによって推定される尤度によって行われる。
【０００４】
本発明を適用可能なビデオメタデータサービスについて述べる。近年、ＰＳＰ（Play Station Portable）（登録商標）、iPod（登録商標）、ＡＶ５００などが双方向型のビデオ再生のためのプラットフォームになりつつある。ビデオがデジタルの形でローカルのハードディスクに格納されたり、インターネット上で配信されれば、今までにない新しいビデオの視聴の仕方が可能になる。例えば、視聴者は好きな部分でビデオを停止し、また再生することができる。また、ローカルにビデオを格納することにより、ランダムアクセスにビデオを再生することができる。さらに、ビデオに関連付けられたメタデータと視聴者の興味を用いることにより更に進んだ視聴が可能となる。例えば、２時間のニュース番組にメタデータが関連付けられていれば、その中の１０分間の天気予報だけを視聴することができ、大きな時間の節約になる。また、サッカー番組にメタデータが関連付けられていれば、ゲームの最も盛り上がるゴールシーンのみを視聴することもできる。過去の研究に見られるようにモデルを尤度によって選択することによってビデオシーンにメタデータを関連付けることができる。ビデオの内容と視聴者の興味によりパーソナライズされたメタデータは、視聴者のビデオデバイスの中で関連付けられる。
【０００５】
連続型ＨＭＭの探索問題は音声認識の分野で多く研究されてきた。それは音声認識の処理時間の多く（３０〜７０％）が連続型ＨＭＭの尤度の計算にかかるからである。連続型ＨＭＭの状態は典型的に８〜６４個のガウス関数で構成され、尤度計算するにはそれぞれのガウス関数を別々に計算しなければならない。計算コストを落とすためにHuntらは線形判別分析によりガウス関数の数を減らす手法を提案した。また、尤度が既に計算されたガウス関数の部分セットのみ用いる手法も示されている。嵯峨山らやRamachandrulaらは連続型ＨＭＭを離散型ＨＭＭに置き換える手法を提案した。離散型ＨＭＭの尤度はスカラ量子化された確率のテーブルを引くことで計算できる。これらの研究は発明の手法と併用することにより、より効果的かつ高速な探索が可能となる。
【０００６】
また、隠れマルコフモデルにおける探索手法として、問い合わせシーケンスに対する探索手法がある。この手法はモデルを並び替えてから一つ一つを粒度を細かくして探索するものである（例えば、特許文献1、非特許文献1参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−９６７４２号公報
【非特許文献】
【０００８】
【非特許文献１】Yasuhiro Fujiwara, Yasushi Sakurai, Masashi Yamamuro: "Special: Efficient and Exact Model Identification for Hidden Markov Models", In Proceeding of the 14th ACM SIGKDD International Conference on Knowledge discovery and Data Mining.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
一般的に離散型ＨＭＭであっても尤度計算するには、状態の数が多くまたデータ集合の規模が大きいため、多くの処理時間がかかる。そこで、離散型ＨＭＭの探索コスを低減することが必要となる。
【００１０】
本発明は、上記の点に鑑みなされたもので、以下の２つの点を解決し、上記の特許文献１、非特許文献1の手法よりさらに高速な隠れマルコフモデル探索装置及び方法及びプログラムを提供することを目的とする。
【００１１】
（１）離散型ＨＭＭのデータセットと問い合わせシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）が与えられたとき、シーケンスＸに対して最も高い尤度を与えるモデルを検索する。
【００１２】
（２）離散型ＨＭＭのデータセットとデータストリームから切り出されたサブシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）（ｘｎは最新のシーケンスの値とする）が与えられたとき、サブシーケンスＸに対して最も高い尤度を与えるモデルを検索する。
【課題を解決するための手段】
【００１３】
図１は、本発明の原理を説明するための図である。
【００１４】
本発明（請求項１）は、問い合わせシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索装置であって、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段１２０と、
データ記憶手段１２０から読み出された検索対象である隠れマルコフモデルについて、与えられた粒度に対する尤度を計算する尤度計算手段１１２と、
近似の粒度を固定して、それぞれの粒度における尤度を尤度計算手段１１２に計算させ、計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算手段１１２を実行させ、得られた尤度を新たな解候補として探索結果記憶手段１１３に格納する計算判定手段１１１と、を有する。
【００１５】
本発明（請求項２）は、データストリームのサブシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索装置であって、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段と、
データ記憶手段から読み出された検索対象である隠れマルコフモデルについて、与えられた粒度に対する尤度を計算する尤度計算手段と、
探索におけるはじめの解の候補として1時刻前の解を探索結果記憶手段に格納し、それぞれのモデルの１時刻前の粒度より１つ荒い粒度に対する尤度を尤度計算手段に計算させ、該尤度計算手段で計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算手段を実行させ、得られた尤度を新たな解候補として該探索結果記憶手段に格納する計算判定手段と、を有する。
【００１６】
図２は、本発明の原理を説明するための図である。
【００１７】
本発明（請求項３）は、問い合わせシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索方法において、
コンピュータが、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れマルコフモデルについて、近似の粒度を固定して、それぞれの粒度における尤度を計算し（ステップ１，２）、
計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算を繰り返し（ステップ３）、得られた尤度を新たな解候補として探索結果記憶手段に格納する（ステップ４）。
【００１８】
本発明（請求項４）は、データストリームのサブシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索方法において、
コンピュータが、
１時刻前の解を始めの解の候補として探索結果記憶手段に格納しておき、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れマルコフモデルについて、それぞれのモデルに対する1時刻前の粒度より１つ荒い粒度に対する尤度を計算し、
計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで尤度の計算を繰り返し、得られた尤度を新たな解候補として探索結果記憶手段に格納する。
【００１９】
本発明（請求項５）は、請求項1または２に記載の隠れマルコフモデル探索装置を構成する各手段としてコンピュータを機能させるための隠れマルコフモデル探索プログラムである。
【発明の効果】
【００２０】
上記のように本発明によれば、以下のような効果を奏する。
【００２１】
・高速処理：モデルのデータ集合が大きくても高速に探索が可能である。
【００２２】
・探索漏れ無し：本発明の手法により探索されたモデルは厳密に正確である。
【００２３】
・モデルの構造に制限なし：モデルには複数の構造があるが、どの構造でも探索が可能である。
【００２４】
本発明では、高速な探索を探索結果の厳密性を両立させるために、尤度を近似して探索の解候補を絞り込んでから厳密な尤度を計算する。本発明では、データ集合の中から必要最低限のものに対してのみ厳密な尤度を計算するので、高速処理が可能となる。
【図面の簡単な説明】
【００２５】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の一実施の形態における隠れマルコフモデル探索装置の構成図である。
【図４】本発明の一実施の形態における探索部の構成図である。
【図５】ＨＭＭの種類を示す図である。
【図６】トレリス構造を示す図である。
【図７】本発明における手法の概要である。
【図８】本発明の一実施の形態における尤度の計算アルゴリズムである。
【図９】本発明の一実施の形態における問い合わせシーケンスに対する探索処理のアルゴリズムである。
【図１０】本発明の一実施の形態におけるデータストリームに対する探索処理のアルゴリズムである。
【図１１】関連文献における探索手法との比較である。
【図１２】実験におけるデータストリームに対する探索処理時間を示す図である。
【発明を実施するための形態】
【００２６】
以下、図面と共に本発明の実施の形態を説明する。
【００２７】
本発明は、与えられた問い合わせシーケンスまたはデータストリームのサブシーケンスに対してデータ集合の中からモデルを探索する問題を対象とする。探索はモデルによって推定される尤度によって行われる。
【００２８】
本発明を適用可能なビデオメタデータサービスについて述べる。近年、ＰＳＰ（Play Station Portable）（登録商標）、iPod（登録商標）、ＡＶ５００などが双方向型のビデオ再生のためのプラットフォームになりつつある。ビデオがデジタルの形でローカルのハードディスクに格納されたり、インターネット上で配信されれば、今までにない新しいビデオの視聴の仕方が可能になる。例えば、視聴者は好きな部分でビデオを停止し、また再生することができる。また、ローカルにビデオを格納することにより、ランダムアクセスにビデオを再生することができる。さらに、ビデオに関連付けられたメタデータと視聴者の興味を用いることにより更に進んだ視聴が可能となる。例えば、２時間のニュース番組にメタデータが関連付けられていれば、その中の１０分間の天気予報だけを視聴することができ、大きな時間の節約になる。また、サッカー番組にメタデータが関連付けられていれば、ゲームの最も盛り上がるゴールシーンのみを視聴することもできる。過去の研究に見られるようにモデルを尤度によって選択することによってビデオシーンにメタデータを関連付けることができる。ビデオの内容と視聴者の興味によりパーソナライズされたメタデータは、視聴者のビデオデバイスの中で関連付けられる。
【００２９】
連続型ＨＭＭの探索問題は音声認識の分野で多く研究されてきた。それは音声認識の処理時間の多く（３０〜７０％）が連続型ＨＭＭの尤度の計算にかかるからである。連続型ＨＭＭの状態は典型的に８〜６４個のガウス関数で構成され、尤度計算するにはそれぞれのガウス関数を別々に計算しなければならない。計算コストを低減するためにHuntらは線形判別分析によりガウス関数の数を減らす手法を提案した。また、尤度が既に計算されたガウス関数の部分セットのみ用いる手法も示されている。嵯峨山らやRamachandrulaらは連続型ＨＭＭを離散型ＨＭＭに置き換える手法を提案した。離散型ＨＭＭの尤度はスカラ量子化された確率のテーブルを引くことで計算できる。これらの研究は発明の手法と併用することにより、より効果的かつ高速な探索が可能となる。本発明では、これらの手法を併用し、
（１）モデルの状態を結合し、尤度の上限値により高速に解候補を絞り込み、
（２）モデルを様々な近似の粒度で探索し、
（３）モデルの尤度計算を打ち止めて、尤度の低いモデルを高速に枝刈りする。
【００３０】
以下に、本発明の詳細について述べる。
【００３１】
図３は、本発明の一実施の形態における隠れマルコフモデル探索装置の構成を示す。
【００３２】
隠れマルコフモデル探索装置１００は、探索部１１０とデータ格納部１２０を有する。
【００３３】
データ格納部１２０は、探索対象となる隠れマルコフモデルが格納されたデータベース等の記憶媒体である。探索部１１０は、隠れマルコフモデルの探索を行う。図４に示すように、探索部１１０は、計算判定部１１１、尤度計算部１１２、探索結果保存部１１３から構成される。計算判定部１１１は、与えられた粒度で尤度計算部１１２に尤度を計算させ、所定の閾値と計算された近似尤度を比較して、その結果に基づいて尤度計算部１１２に再計算させる、または、再計算を終了させる。計算された尤度と探索結果保存部１１３に格納されている解の候補と比較して、計算された尤度が格納されている解の候補より高い尤度であれば、探索結果保存部１１３の解の候補を更新する。尤度計算部１１２は、計算判定部１１１における判定結果を受けて、隠れマルコフモデルの近似尤度または正確な尤度を計算する。なお、尤度計算部１１２は図示しないが、途中の解を格納するためのメモリを具備するものとする。探索結果保存部１１３は、メモリやハードディスク装置等の記憶媒体であり、探索処理における解候補の保存を行う。
【００３４】
ＨＭＭはシーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現するデータモデルである。
【００３５】
以下に、本明細書で用いる主な記号とその定義を示す。
【００３６】
Ｋ：k-近傍探索のパラメータ；
ｘｔ：時刻ｔ（ｔ＝１，…，ｎ）のシーケンスＸの値；
ｕｉ：ＨＭＭのｉ（ｉ＝１，…，ｍ）番目の状態
ｎ：シーケンスＸの長さ；
ｍ：状態の数；
α＝｛αｉ｝：ｕｉの初期遷移確率；
β＝｛βｉ｝：ｕｉからｕｊの状態遷移確率；
γ（ｖｊ）＝｛γｉ（ｖｊ｝：状態ｕｉにおけるシンボルｖｊ（ｊ＝１，…，ｓ）のシンボル出力確率；
Φ：正確な尤度；
Ψ：近似尤度
本発明は、以下の２つの問題を対象とする。
【００３７】
問題１：離散型ＨＭＭのデータセットと問い合わせシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）が与えられたとき、シーケンスＸに対して最も高い尤度を与えるモデルを検索する。
【００３８】
問題２： 離散型ＨＭＭのデータセットとデータストリームから切り出されたサブシーケンスＸ＝（ｘ１，ｘ２，…，ｘｎ）（ｘｎは最新のシーケンスの値とする）が与えられたとき、サブシーケンスＸに対して最も高い尤度を与えるモデルを検索する。
【００３９】
本発明の手法を説明する前に簡単にＨＭＭについて説明する。ＨＭＭは以下の要素で構成される。
【００４０】
初期状態確率：α＝｛αｉ｝時刻１において状態がｕｉ（ｉ＝１，…，ｍ）である確率。
【００４１】
状態遷移確率：β＝｛βij｝時刻が１つ進んだときに状態ｕｉから状態ｕｊへ遷移する確率。
【００４２】
シンボル出力確率：γ（ｖｊ）＝｛γｉ（ｖｊ）｝状態ｕｉにおいてシンボルｖｊを出力する確率（ｊ＝１，…，ｓ）。
【００４３】
ＨＭＭを説明するために壷とボールの例を用いる。
【００４４】
赤や青などの色のついたボールが入っている壷が複数あることを考える。はじめにある確率によって壷を選ぶ。そしてボールを一つ取り出し、その色を記録する。次の壷は現在の壷の選択によって関連付けされた確率に従って選択する。そしてボールの色の記録を繰り返す。これらの操作によってボールの色の系列が得られる。
【００４５】
この例において、壷は状態に対応し、色の系列はシーケンスに対応する。すなわち初期状態確率は初めに選択する壷の確率であり、状態遷移確率は次の壷の選択確率であり、シンボル出力確率はどの色のボールを選択するかの確率である。
【００４６】
ＨＭＭは図５のように状態遷移確率βの構造によって分類することができる。図５において白い円は「状態」を表し、矢印は「遷移」を表す。全ての状態から他の全ての状態へ遷移できるタイプとして全結合ＨＭＭとエルゴディックＨＭＭ（図５（ａ））がある。エルゴディックＨＭＭは全結合ＨＭＭを包含し、全ての状態が他の全ての状態へ有限であるが、非周期的な回数で遷移できる特徴がある。１回で任意の状態に遷移できるエルゴディックＨＭＭや全結合ＨＭＭにおいて状態遷移確率βは、正の係数βijを用いて以下のようになる。
【００４７】
【数１】
また、他のタイプとしてleft-right HMM（図５（ｂ））がある。left-right HMMは状態を並べたときに左から右へ遷移する特徴がある。状態遷移確率の係数はj＜ｉのときβij＝０となり、ｉ≠１でαｉ＝０となる。また、left-right HMMにおいては状態間を多く遷移しないように制約が課せられていることがあり、状態遷移確率の係数はｊ＞ｉ＋△―１のときβij＝０となる。例えば、状態遷移確率βは△＝３のときβijを用いて以下のようになる。
【００４８】
【数２】
シーケンスＸの尤度Φは、Viterbiアルゴリズムにより計算される。先の壷とボールの例では尤度の計算は、ボールの系列が与えられた時にそれを出力する。壷の遷移の最大確率を計算することに対応する。尤度は以下のように求める。
【００４９】
【数３】
Viterbiアルゴリズムでは、図６のように状態を縦軸に、時間を横軸に並べたときに構成されるトレリス構造において、各状態における確率の最大値を動的計画法によって求めている。
【００５０】
以下に、探索部１１０の具体的な動作を説明する。
【００５１】
［例１］
モデルとシーケンスが以下のようであるとする。
【００５２】
【数４】
Viterbiアルゴリズムは以下のように計算される。
【００５３】
φ11＝1，φ12＝0.5， φ13＝0， φ14＝0
φ21＝0，φ22＝0.75・0.5，φ23＝(0.5)2。・0.25， φ25＝0
φ31＝0，φ32＝0， φ33＝0， φ34＝(0.5)2・(0.25)2
結果的に尤度はΦ＝(0.5)3・(0.25)2となり、その尤度を与える状態遷移はｕ１，ｕ１，ｕ２，ｕ３となる。尤度計算部１１２は、上記のようにして求めた尤度と状態遷移を計算判定部１１１に渡す。これにより、計算判定部１１１は、探索結果保存部１１３に格納されている解の候補と計算された尤度とを比較して、尤度が解の候補より大きい場合には、当該尤度で探索結果保存部１１３の値を更新する。
【００５４】
ＨＭＭの構造に制約がない場合、すなわちエルゴディックＨＭＭの場合のViterbiアルゴリズムの計算量はＯ（nm2）となる。これは全ての状態において、前の時刻の状態全てから遷移する確率を計算するからである。そのためナイーブに全てのモデルの尤度を計算するには、特にモデルの状態数が多くまたモデルの数が多いと莫大な計算コストがかかる。ナイーブに解く手法を今後「Naive Viterbi」と表現する。
【００５５】
探索部１１０の計算判定部１１１は、以下の３つの機能を有する。まず、概要を示し、その後に各々の詳細について述べる。
【００５６】
●トレリス構造の縮退：
先に述べたとおり、トレリス構造が大きい場合Viterbiアルゴリズムは高い計算コストを必要とする。そこで、図７に示すように、計算判定部１１２では、状態をクラスタリングし、結合することによって状態の数を削減する。この状態数の削減により、トレリス構造は縮退され、高速に尤度を計算することが可能になる。トレリス構造を縮退させるために粒度ｑが与えられたとき、ｍ個の状態はｍ／ｇ個に削減される。この結果、尤度計算部１１２の尤度の計算量はＯ（nm2/g2）に低減化される。
【００５７】
トレリス構造を縮退することには２つのメリットがある。まずはじめのメリットはトレリス構造を縮退して探索を行っても探索漏れは発生しないことが保証されることである。これは後に示すとおり縮退後の近似尤度は厳密な尤度より小さくならないためである。そのため近似尤度を計算するのみで、探索結果の候補を少ない計算コストで得ることができる。
【００５８】
２番目のメリットとして、どのようなタイプのモデルにも適用できることが挙げられる。これは状態をクラスタリングするときにモデルの確率の制約を用いないからである。
【００５９】
●複数の近似粒度：
トレリス構造を縮退することで計算される近似尤度により高速な探索が可能になるが、近似計算には近似精度と計算時間のトレードオフが存在する。すなわちトレリス構造を過度に縮退させると、尤度計算部１１２の近似尤度の計算コストは小さくなるが、近似尤度の上限値は大きくなってしまう。そのため、本発明では、探索処理において徐々にトレリス構造のサイズを大きくしていき、近似尤度の精度を上げていく。
【００６０】
複数の近似粒度を用いることでモデルの厳密な尤度に応じた近似粒度で計算させることができる。尤度が小さいモデルは低い粒度の近似で枝刈りすることができるが、尤度が大きいモデルは高い粒度の近似でないと枝刈りができない。言い換えれば低い粒度で枝刈りした結果として高い尤度のモデルを得られる。そのため本発明では、低い粒度の結果のみに対して高い粒度の近似を計算する。結果として相反する近似精度と計算時間のバランスをとることができる。
【００６１】
●状態遷移の枝刈り：
本発明は、探索結果の厳密性を保証している。トレリス構造を縮退することにより高速な探索が可能になるが、厳密に正確な探索結果は近似尤度からは求めることができない。そのため、本発明では、近似尤度で求めた候補に対して厳密な尤度を求めている。しかし、厳密な尤度を計算するには大きなコストがかかる。
【００６２】
本発明では、尤度計算の中には探索処理として必要のないものも含まれるため、図７のようにトレリス構造における尤度計算を高速に打ち切る。例えば、後段の［例１］において探索途中の解の候補の尤度が0.2５であるときに、時刻１における状態ｕ２とｕ３の尤度は0.25より小さいため、時刻２においてこれらの状態から遷移する確率は計算する必要はない。同じように時刻３において状態ｕ３からの確率は計算する必要はない。時刻３において全ての状態の確率は0.25より小さいため、尤度計算を打ち切ることができる。
【００６３】
探索途中のＫ番目に高い尤度が大きくなるほど、より効果的に計算を打ち切ることができる。ここで、Ｋ番目に高い尤度は探索処理が進むほど大きくなるので、結果的にモデルの数が多くても効果的に探索することができる。
【００６４】
また、計算の途中では尤度は単調減少するため、問い合わせのシーケンスが長くなるほど状態遷移の打ち切りは効果的になる。これは、ユーザやアプリケーションによって問い合わせの長さが異なることを考えると、非常に有効な性質である。
【００６５】
また、状態遷移の打ち切りは厳密なトレリス構造のみに対してではなく、縮退後のトレリス構造に対しても適用できる。すなわち、状態遷移を打ち切ることで、近似計算を高速化できる。
【００６６】
●トレリス構造の縮退：
本発明ではモデルのオリジナルの状態を結合することによりトレリス構造を縮退して、尤度計算部１１２に近似尤度を計算させる。近似尤度で枝刈りを行っても探索漏れは発生しないことが保証される。
【００６７】
粒度ｇが与えられたとき、状態をクラスタリングし結合することで、ｍ・ｎのトレリス構造をｍ／ｇ・ｎに縮退する。状態ｕｉとｕｊが同じクラスタになった場合、結合によって得られた状態uｉ´の確率を各要素の確率の中で最大値を用いて以下のように定義する。
【００６８】
［定義１］
状態uｉとuｊが同じクラスタになった場合、結合後の確率は
α´i＝max（αi，αj）；
β´ii＝max（βii，βij，βji，βjj），
β´ik＝max（βik，βjk），
β´ki＝max（βki，βkj）（k≠i，k≠j）；
γ´i (ｖk)=max（γi (ｖk)，γj (ｖk)）
となる。
【００６９】
［例１］
例1のＨＭＭにおいて状態ｕ１とｕ２が同じクラスタになった後の確率は以下のようになる。
【００７０】
【数５】
上記の例において、確率はそれぞれ、
α´1=max(α1，α2)，
β´11=max(β11，β12，β21，β22)，
β´12=max(β13，β23)，
β´21=max(β31，β32)，
γ´1(1)=max(γ1(1)，γ2(1))，
γ´1(2)=max(γ1(2)，γ2)(2))，
γ´1(3)=max(γ1(3)，γ2(3))
と計算する。２つの状態が同じクラスタになる場合について説明したが、３つ以上の場合でも同様に計算する。
【００７１】
クラスタリングを行うために、状態の特徴量Ｆiを以下のように定義する。
【００７２】
［定義２］
Fｉ=（αi：βi1,…，βim，β1i，…，βmi；γi (ｖ1)，…，γi (ｖｓ)）． （４）
状態をクラスタリングするため、k-means法（文献：J. MacQueen, Some methods for classification and analysis of multivariate observations., 1967）を用いる。トレリス構造を縮退する手法は、クラスタリング方法の選択とは完全に独立したものであるため、他のクラスタリング方法（例えば、BIRCH： Tian Zhang and Raghu Ramakrishnan and Miron Livny， BIRCH： An Efficient Data Clustering Method for Very Large Databases, SIGMOD Conference, 1996）を用いることも可能である。
【００７３】
状態を結合することにより厳密なトレリス構造の縦のサイズを減らすことができる。すなわち、［例１］のトレリス構造の縦のサイズは"３"であるが、［例１］のサイズは"２"である。トレリス構造の横のサイズを減らすには、後述するように、状態遷移の枝刈りを用いる。
【００７４】
尤度計算部１１２は、近似尤度Ψを、結合後の状態数ｍ´（=m/g）と確率α´、β´、γ´（ｖ）を用いて以下のように計算する。
【００７５】
【数６】
近似尤度の計算量はＯ(nm2/g2)となる。これはViterbiアルゴリズムと同様にｎ個の各時刻においてｍ／ｇ個の状態の中から最大の確率を有するものを選択するからである。
【００７６】
Ψは厳密なトレリス構造による尤度Φの上限値となる。
【００７７】
［補助定理１］
状態を結合後のモデルとシーケンスが与えられたとき、以下の関係が成立する。
【００７８】
Φ≦Ψ （６）
［証明１］
オリジナルの状態ｕi(1≦ｉ≦ｍ)が状態ｕ´i(1≦ｉ≦ｍ´)へクラスタリングされたとすると、
φi1≦α´i・γ´i(ｘ1)＝ψi1
となるので、２≦ｔ≦ｎのとき、
【００７９】
【数７】
よって、
【００８０】
【数８】
が成り立つ。
【００８１】
上記の［補助定理１］の性質を用いて探索漏れなくモデルを探索することができる。
【００８２】
［補助定理２］
Ψを用いて探索することは、探索漏れが発生しないことの十分条件である。
【００８３】
［証明２］
解の尤度をεとしたとき、探索漏れが発生しないことを保証するためには、Φ≧εであるときΨ≧εでなければならない。ところで式（６）より、
ε≦Φ≦Ψ
となるので探索漏れは発生しない。
【００８４】
●複数の近似尤度：
これまでは一つの粒度でトレリス構造を縮退し近似尤度を計算することを前提に説明した。しかし、近似の粒度が低ければ近似精度も低くなるなど、近似の粒度が異なればその精度も異なるため、モデル毎の厳密な尤度に応じて近似の粒度が異なることが望ましい。そのため、本発明では一つの粒度ではなく、複数の粒度の近似を用いてモデルを探索する。すなわち、計算判定部１１１は、探索において徐々に近似粒度を上げて尤度計算部１１２に尤度計算させていく。
【００８５】
本発明では、ｈ個の粒度を用いる。レベルｉ（１≦ｉ≦ｈ）の近似においては粒度ｇｉを用いて、ｍ個の状態を
【００８６】
【数９】
個に結合する。最も粗い粒度をｇ1とすると、レベルが上がるにつれてｇ1も大きくなり、近似尤度の精度も上がっていく。
【００８７】
尤度計算部１１２は、まずレベル1の
【００８８】
【数１０】
個に状態を結合した近似尤度を全てのモデルに対して計算する。近似尤度によって解の候補を求めて、その厳密な尤度εを計算する。εより小さい近似尤度を持つモデルは枝刈りできる。そうでないモデルに対しては、尤度計算部１１２でレベル２の近似尤度を計算し、計算判定部１１１において、同様に近似尤度がεより小さいか調べる。この操作をレベルがｈになるまで行う。結果的にモデルを厳密な尤度に従った近似の尤度に従った近似の粒度によって枝刈りすることができる。複数の近似尤度によるアルゴリズムは探索アルゴリズムと共に後述する。
【００８９】
●状態遷移の枝刈り：
本発明では、状態遷移の枝刈りに関しては２つの重要な性質を用いる。第一に尤度を計算するときに、各状態の尤度は既に遷移した過去の時刻の全ての状態の尤度より大きくならない。これは各状態の尤度は以前の時刻の尤度を用いて計算されるためである。
【００９０】
第二に、探索処理においては解候補を保持し、新たにεより高い尤度のモデルが見つかったとき解候補を更新するため、εは大きくなり続ける。
【００９１】
この２つの性質を用いて尤度の計算において枝刈りを行うが、枝刈りするための推定値ψitを以下のように導入する。
【００９２】
【数１１】
ここで、βmaxとγmax(v)は以下のように状態遷移確率とシンボル出力確率の最大値である。
【００９３】
【数１２】
推定値ψitはViterbiパスが時刻ｔで状態ｕiを通るとしたときの尤度の上限値となる。
【００９４】
［定理１］
φin≦ψit （９）
尤度の計算において枝刈りは推定値ψitを用いて行う。すなわち、εより推定値が小さい状態からの遷移は計算しない。厳密なトレリス構造に対する状態遷移の枝刈りのアルゴリズムを図８に示す。状態遷移の枝刈りでは遷移集合を用いて処理を行う。遷移集合はトレリス構造のそれぞれの時刻毎に設定される。時刻ｔの状態ｕiの推定値がε以上であれば、時刻ｔの遷移集合に状態ｕiが加えられる。尤度を計算するときは時刻ｔ−１の遷移集合に含まれる状態からの遷移のみを用いる。もしある時刻における遷移集合が空集合であれば、そのモデルは解集合となりえないため、尤度計算を打ち切る。近似尤度の計算においても同様のアルゴリズムで処理を行う。
【００９５】
●探索処理：
前述の通り、Naive Viterbiを処理するには大きな計算量を要する。本発明では高速に解を求めるために近似尤度を用いて尤度の低い殆どのモデルの枝刈りを行う。計算コストのかかる厳密な尤度計算は必要最低限に限定される。
【００９６】
問い合わせシーケンスに対する探索処理と、データストリームに対する探索処理は以下の通りである。
【００９７】
（１）問い合わせシーケンスに対する探索処理：
探索処理においては、計算判定部１１１において近似の粒度を固定し、尤度計算部１１２においてそれぞれの粒度における解の候補を計算する。具体的には探索処理ではまず全てのモデルに対して最も粗い近似尤度を計算する。最も高い近似尤度を与えるモデルを解の候補として、そのモデルの厳密な尤度を計算する。その厳密な尤度によってモデルの枝刈りを行い、残ったモデルに対して２番目の粒度の近似尤度を計算する。最も高い近似尤度を与えるモデルの厳密な尤度を計算し、もし、計算判定部１１１は、探索結果保存部１１３に格納されている1番目の粒度による解の候補より高い尤度だったら、当該探索結果保存部１１３の解の候補を更新する。同様の処理を粒度を細かくしながら続けていく。
【００９８】
探索処理のアルゴリズムを図９に示す。同図において、Φiは粒度giの尤度を示す。なお、ここでΦ0は厳密な尤度とする。また、Mはモデルの集合を表す。
【００９９】
（２）データストリームに対する探索処理：
データストリームは時々刻々と変化していくが、その変化の割合はそれほど多くはないことに着目した処理を行う。具体的には、計算判定部１１１は、それぞれのモデルに対する近似の粒度を1時刻前の粒度より１つ荒い粒度にし、また、探索におけるはじめの解の候補として1時刻前の解を用いる。その他の処理は問い合わせシーケンスに対する探索処理と同様であるので、その説明を省略する
当該データストリームに対する探索処理のアルゴリズムを図１０に示す。同図において、Miは粒度ｇiの尤度を計算するモデルの集合を示し、M´iは1つ前の時刻において計算した最も細かい粒度がｇiであるモデルの集合とする。
【０１００】
≪評価実験≫
本発明の有効性を示すために実験を行った。実験はエルゴディックＨＭＭとleft-right HMMに対して行った。実験では探索におけるＣＰＵの計算時間を比較した。
【０１０１】
実験は、Intel Xeon quad CPU 3.33 GHz、メインメモリが３２GBのマシンで行った。
【０１０２】
実験データは以下のものを用いた。
【０１０３】
・ＥＥＧ：
このデータセットはＥＥＧとアルコール依存症の関係を調べるために行われた大規模な実験で得られたものであり、ＵＣＩのＷｅｂサイトからダウンロードすることができる（http://www.ncbi.nlm.nih.gov）。
【０１０４】
・Chromosome：
人間の第2，18，21，22番遺伝子のデータであり、NCBIのＷｅｂサイトから得ることができる（http://archive.ics.uci.edu/ml/）。
【０１０５】
・Traffic：
このデータセットはＵＣＩのＷｅｂサイトから得たフリーウェイ交通量の測定値である（http://www.ncbi.nlm.nih.gov）。
【０１０６】
・ＵＮＩＸ：
このデータセットはＵＣＩのＷｅｂサイトから得たＵＮＩＸの操作履歴である（http://www.ncbi.nlm.nih.gov）。
【０１０７】
状態数を変化させて実験を行った。実験ＩＣおいてシーケンスの長さｍ＝２５６とした。
【０１０８】
（１）問い合わせシーケンスに対する従来技術との比較：
隠れマルコフモデルにおける探索手法、特に、問い合わせシーケンスに対する探索手法として、前述の特許文献１、非特許文献1に記載の技術がある。これらの文献における手法は、モデルを並び替えてから一つ一つ粒度を細かくし探索する特徴がある。
【０１０９】
本発明の手法の優位性を示すためにそれぞれの手法における探索処理の時間の比較実験を行った。実験結果を図１１に示す。実験において状態数を１００とし、モデルの数を１００００とした。図１１において「SPIRAL」とあるのは本発明による手法、「Sort」とあるのは特許文献１、非特許文献1による手法とする。
【０１１０】
本発明の手法は、特にエルゴディックHMMに対して有効であることがわかる。O(nm2)だけのコストが誘導を計算する時に必要になるが、粒度毎に解候補を計算することでその計算コストを低減することができることがわかる。本発明による手法は、特許文献１、非特許文献1による手法に対して３０倍まで高速な探索を行うことができた。
【０１１１】
（２）データストリームに対する探索処理時間：
本実験ではストリームに対応したアルゴリズムと問い合わせシーケンスに対応したアルゴリズム、及びViterbiアルゴリズムとの比較を行った。それぞれのアルゴリズムの実験結果をStream-SPIRAL、SPIRAL、Viterbiとして図12に示す。実験において状態数を１００とし、モデルの数を１００００とした。
【０１１２】
ストリームに対応したアルゴリズムはその他のアルゴリズムに対して優位であり、特にViterbiアルゴリズムに対しては４９０倍高速であることが確認された。ストリームに対応したアルゴリズムは問い合わせシーケンスに対応したアルゴリズムとおおよそ同様であるが、解候補と粒度の決定方法が異なる。これらの決定方法が探索処理時間に大きな影響を与えることがわかる実験結果になった。
【０１１３】
また、上記の探索部１１０の動作をプログラムとして構築し、隠れマルコフモデル探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１１４】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０１１５】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１１６】
本発明は、ビデオメタサービスに適用可能である。
【符号の説明】
【０１１７】
１００ 隠れマルコフモデル探索装置
１１０ 探索部
１１１ 計算判定手段、計算判定部
１１２ 尤度計算手段、尤度計算部
１１３ 探索結果記憶手段、探索結果保存部
１２０ データ記憶手段
【特許請求の範囲】
【請求項１】
問い合わせシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索装置であって、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段と、
前記データ記憶手段から読み出された検索対象である隠れマルコフモデルについて、与えられた粒度に対する尤度を計算する尤度計算手段と、
近似の粒度を固定して、それぞれの粒度における尤度を前記尤度計算手段に計算させ、計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算手段を実行させ、所定の閾値より小さくなった尤度を新たな解候補として探索結果記憶手段に格納する計算判定手段と、
を有することを特徴とする隠れマルコフモデル探索装置。
【請求項２】
データストリームのサブシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索装置であって、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段と、
前記 データ記憶手段から読み出された検索対象である隠れマルコフモデルについて、与えられた粒度に対する尤度を計算する尤度計算手段と、
探索におけるはじめの解の候補として1時刻前の解を探索結果記憶手段に格納し、それぞれのモデルの１時刻前の粒度より１つ荒い粒度に対する尤度を前記尤度計算手段に計算させ、該尤度計算手段で計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算手段を実行させ、得られた尤度を新たな解候補として該探索結果記憶手段に格納する計算判定手段と、
を有することを特徴とする隠れマルコフモデル探索装置。
【請求項３】
問い合わせシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索方法において、
コンピュータが、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れマルコフモデルについて、近似の粒度を固定して、それぞれの粒度に対する尤度を計算し、
計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算を繰り返し、得られた尤度を新たな解候補として探索結果記憶手段に格納することを特徴とする隠れマルコフモデル探索方法。
【請求項４】
データストリームのサブシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索方法において、
コンピュータが、
１時刻前の解を始めの解の候補として探索結果記憶手段に格納しておき、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れ隠れマルコフモデルについて、それぞれのモデルに対する1時刻前の粒度より１つ荒い粒度に対する尤度を計算し、
計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで尤度の計算を繰り返し、得られた尤度を新たな解候補として探索結果記憶手段に格納することを特徴とする隠れマルコフモデル探索方法。
【請求項５】
請求項1または２に記載の隠れマルコフモデル探索装置を構成する各手段としてコンピュータを機能させるための隠れマルコフモデル探索プログラム。
【請求項１】
問い合わせシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索装置であって、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段と、
前記データ記憶手段から読み出された検索対象である隠れマルコフモデルについて、与えられた粒度に対する尤度を計算する尤度計算手段と、
近似の粒度を固定して、それぞれの粒度における尤度を前記尤度計算手段に計算させ、計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算手段を実行させ、所定の閾値より小さくなった尤度を新たな解候補として探索結果記憶手段に格納する計算判定手段と、
を有することを特徴とする隠れマルコフモデル探索装置。
【請求項２】
データストリームのサブシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索装置であって、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段と、
前記 データ記憶手段から読み出された検索対象である隠れマルコフモデルについて、与えられた粒度に対する尤度を計算する尤度計算手段と、
探索におけるはじめの解の候補として1時刻前の解を探索結果記憶手段に格納し、それぞれのモデルの１時刻前の粒度より１つ荒い粒度に対する尤度を前記尤度計算手段に計算させ、該尤度計算手段で計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算手段を実行させ、得られた尤度を新たな解候補として該探索結果記憶手段に格納する計算判定手段と、
を有することを特徴とする隠れマルコフモデル探索装置。
【請求項３】
問い合わせシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索方法において、
コンピュータが、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れマルコフモデルについて、近似の粒度を固定して、それぞれの粒度に対する尤度を計算し、
計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで該尤度計算を繰り返し、得られた尤度を新たな解候補として探索結果記憶手段に格納することを特徴とする隠れマルコフモデル探索方法。
【請求項４】
データストリームのサブシーケンスに対して最も尤度の高いモデルを探索する隠れマルコフモデル探索方法において、
コンピュータが、
１時刻前の解を始めの解の候補として探索結果記憶手段に格納しておき、
シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現する探索対象となる隠れマルコフモデルを格納するデータ記憶手段から読み出された探索対象である隠れ隠れマルコフモデルについて、それぞれのモデルに対する1時刻前の粒度より１つ荒い粒度に対する尤度を計算し、
計算された尤度と所定の閾値とを比較して該尤度が該閾値より小さくなるまで尤度の計算を繰り返し、得られた尤度を新たな解候補として探索結果記憶手段に格納することを特徴とする隠れマルコフモデル探索方法。
【請求項５】
請求項1または２に記載の隠れマルコフモデル探索装置を構成する各手段としてコンピュータを機能させるための隠れマルコフモデル探索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１１−２８３２０（Ｐ２０１１−２８３２０Ａ）
【公開日】平成２３年２月１０日（２０１１．２．１０）
【国際特許分類】
【出願番号】特願２００９−１７０３５１（Ｐ２００９−１７０３５１）
【出願日】平成２１年７月２１日（２００９．７．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年２月１０日（２０１１．２．１０）
【国際特許分類】
【出願日】平成２１年７月２１日（２００９．７．２１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]