(57)【要約】【課題】離散型ＨＭＭの探索コストを低減する。【解決手段】本発明は、入力されたオリジナルのＨＭＭの状態を初期状態確率、状態遷移確率、または、シンボル出力確率を用いて該ＨＭＭをクラスタリングすることにより状態数を削減し、クラスタリングされたＨＭＭと該オリジナルのＨＭＭをデータ格納手段に格納し、近似尤度による探索結果から閾値の初期値を計算し、閾値を用いて近似尤度または正確な尤度を計算し、正確な尤度を用いて閾値を更新する。正確な尤度を計算する際には閾値を用いて計算するかしないかを判断することにより枝刈りを行う。【選択図】図１
2008096742.tif 000002
【特許請求の範囲】
【請求項１】
隠れマルコフモデル（ＨＭＭ）を尤度によって探索する隠れマルコフモデル探索装置であって、
入力されたオリジナルのＨＭＭの状態をクラスタリングすることにより状態数を削減し、クラスタリングされたＨＭＭと該オリジナルのＨＭＭをデータ格納手段に格納するクラスタリング手段と、
前記データ格納手段に格納されている全ＨＭＭを近似尤度によって枝刈りし、探索する探索手段と、
を有することを特徴とする隠れマルコフモデル探索装置。
【請求項２】
前記クラスタリング手段は、
入力されたオリジナルのＨＭＭの初期状態確率、状態遷移確率、または、シンボル出力確率を用いて該ＨＭＭのクラスタリングを行い、各クラスタの初期状態確率と状態遷移確率とシンボル出力確率をそれぞれの各要素の確率の中の最大値から計算する手段を含む、
請求項１記載の隠れマルコフモデル探索装置。
【請求項３】
前記探索手段は、
探索要求が入力されると、前記データ格納手段に格納されている全てのＨＭＭに対してレベル１の近似尤度を計算し、初期の解候補を求め、該初期の解候補に対して正確な尤度を計算し、閾値を求め閾値記憶手段に格納する初期閾値計算手段と、
レベルを１つずつ上げ解候補でないモデルに対して近似尤度を計算し、該近似尤度と前記閾値を比較することにより、近似尤度または正確な尤度を計算するかを判定する計算判断手段と、
前記計算判断手段で計算された前記近似尤度が前記閾値以上の場合のみ、正確な尤度を計算し、尤度保存手段に格納する尤度計算手段と、
計算された正確な尤度を用いて前記閾値記憶手段の閾値を更新する閾値更新手段と、
を含む請求項１記載の隠れマルコフモデル探索装置。
【請求項４】
隠れマルコフモデル（ＨＭＭ）を尤度によって探索する装置における隠れマルコフモデル探索方法であって、
クラスタリング手段が、入力されたオリジナルのＨＭＭの状態をクラスタリングすることにより状態数を削減し、クラスタリングされたＨＭＭと該オリジナルのＨＭＭをデータ格納手段に格納するクラスタリングステップと、
探索手段が、前記データ格納手段に格納されている全ＨＭＭを近似尤度によって枝刈りし、探索する探索ステップと、
を行うことを特徴とする隠れマルコフモデル探索方法。
【請求項５】
前記クラスタリングステップにおいて、
入力されたオリジナルのＨＭＭの初期状態確率、状態遷移確率、または、シンボル出力確率を用いて該ＨＭＭのクラスタリングを行い、各クラスタの初期状態確率と状態遷移確率とシンボル出力確率をそれぞれの各要素の確率の中の最大値から計算する、
請求項４記載の隠れマルコフモデル探索方法。
【請求項６】
前記探索ステップにおいて、
探索要求が入力されると、前記データ格納手段に格納されている全てのＨＭＭに対してレベル１の近似尤度を計算し、初期の解候補を求め、該初期の解候補に対して正確な尤度を計算し、閾値を求め閾値記憶手段に格納する初期閾値計算ステップと、
レベルを１つずつ上げ解候補でないモデルに対して近似尤度を計算し、該近似尤度と前記閾値を比較することにより、近似尤度または正確な尤度を計算するかを判定する計算判断ステップと、
前記計算判断ステップで計算された前記近似尤度が前記閾値以上の場合のみ、正確な尤度を計算し、尤度保存手段に格納する尤度計算ステップと、
計算された正確な尤度を用いて前記閾値記憶手段の閾値を更新する閾値更新ステップと、
を行う請求項４記載の隠れマルコフモデル探索方法。
【請求項７】
コンピュータに、
請求項１乃至３記載の隠れマルコフモデル探索装置の各手段を実行させることを特徴とするプログラム。
【請求項８】
コンピュータに、
請求項１乃至３記載の隠れマルコフモデル探索装置の各手段を実行させるプログラムを格納したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、隠れマルコフモデル探索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体に係り、特に、与えられた問い合わせシーケンスに対して隠れマルコフモデルのデータ集合の中から離散型ＨＭＭ（Hidden Markov Model）を探索漏れなく探索する隠れマルコフモデル探索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
隠れマルコフモデル（ＨＭＭ）の基礎的理論は主として１９６０年代に研究されている。ＨＭＭはシーケンスを、発生モデルを有する状態の遷移として表現するデータモデルであり、ノイズに強い特長がある。このため、ＨＭＭは音声認識、自然言語処理、遺伝子解析などの多くのアプリケーションにおいて使われている。
【０００３】
以下では、与えられた問い合わせシーケンスに対してデータ集合から離散型ＨＭＭを探索漏れなく探索する問題を対象とする。探索は、モデルによって推定される尤度によって行われる。
【０００４】
ＨＭＭ探索の応用例のひとつであるビデオメタデータサービスについて述べる。近年、ＰＳＰ（登録商標）、ｉＰＡＤ（登録商標）、ＡＶ５００（登録商標）などが双方向型のビデオ再生のためのプラットホームになりつつある。ビデオがデジタルの形でローカルのハードディスクに格納されたり、インターネット上で配信されれば、いままでにない新しいビデオの視聴仕方が可能になる。例えば、視聴者は好きな部分でビデオを停止しまた再生することができる。また、ローカルにビデオを格納することにより、ランダムアクセスにビデオを再生することができる。さらに、ビデオに関連付けられたメタデータと視聴者の興味を用いることにより、さらに進んだ視聴が可能となる。例えば、２時間のニュース番組にメタデータが関連付けられていれば、その中の１０分間の天気予報だけを視聴することができ、大きな時間の節約になる。また、サッカー番組にメタデータが関連付けられていれば、ゲームの最も盛り上がるゴールシーンのみを視聴することもできる。過去の研究に見られるようにモデルを尤度により選択することによってビデオシーンにメタデータを関連付けることができる（例えば、非特許文献１参照）。ビデオの内容と視聴者の興味によりパーソナライズされたメタデータは、視聴者のビデオデバイスの中で関連付けられる。
【０００５】
連続型ＨＭＭの探索問題は、音声認識の分野で多く研究されてきた。それは音声認識の処理時間の多く（３０〜７０％）が連続型ＨＭＭの尤度の計算にかかるからである。連続型ＨＭＭの状態は典型的に８〜６４個のガウス関数で構成され、尤度計算するにはそれぞれのガウス関数を別々に計算しなければならない。計算コストを落とすために連続型ＨＭＭを離散型ＨＭＭに置き換える手法が提案されている（例えば、非特許文献２参照）。離散型ＨＭＭの尤度はスカラ量子化された確率のテーブルを引くことで計算できる。これらの研究の手法は本発明の手法と併用することにより、連続型ＨＭＭをより効果的かつ高速に探索できるようになる。
【非特許文献１】Reede Ren and Joemon M. Jose, Football Video Segmentation Based on Video Production Strategy., ECIR, 2005
【非特許文献２】Sagayama, S. and Knill, K.M. and Takahashi, S., On the use of scalor quantization for fast HMM computation, ICASSP, 1995
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、離散型ＨＭＭであっても尤度計算するには状態の数が多く、また、データ集合の規模が大きいため、多くの処理時間がかかる。
【０００７】
本発明は、上記の点に鑑みなされたもので、離散型ＨＭＭの探索コストを低減することが可能な隠れマルコフモデル探索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００８】
図１は、本発明の原理構成図である。
【０００９】
本発明（請求項１）は、隠れマルコフモデル（ＨＭＭ）を尤度によって探索する隠れマルコフモデル探索装置であって、
入力されたオリジナルのＨＭＭの状態をクラスタリングすることにより状態数を削減し、クラスタリングされたＨＭＭと該オリジナルのＨＭＭをデータ格納手段１２０に格納するクラスタリング手段１１０と、
データ格納手段１２０に格納されている全ＨＭＭを近似尤度によって枝刈りし、探索する探索手段１３０と、を有する。
【００１０】
また、本発明（請求項２）は、クラスタリング手段１１０において、
入力されたオリジナルのＨＭＭの初期状態確率、状態遷移確率、または、シンボル出力確率を用いて該ＨＭＭのクラスタリングを行い、各クラスタの初期状態確率と状態遷移確率とシンボル出力確率をそれぞれの各要素の確率の中の最大値から計算する手段を含む。
【００１１】
また、本発明（請求項３）は、探索手段１３０において、
探索要求が入力されると、データ格納手段に格納されている全てのＨＭＭに対してレベル１の近似尤度を計算し、初期の解候補を求め、該初期の解候補に対して正確な尤度を計算し、閾値を求め閾値記憶手段に格納する初期閾値計算手段と、
レベルを１つずつ上げ解候補でないモデルに対して近似尤度を計算し、該近似尤度と前記閾値を比較することにより、近似尤度または正確な尤度を計算するかを判定する計算判断手段と、
計算判断手段で計算された近似尤度が閾値以上の場合のみ、正確な尤度を計算し、尤度保存手段に格納する尤度計算手段と、
計算された正確な尤度を用いて閾値記憶手段の閾値を更新する閾値更新手段と、を含む。
【００１２】
図２は、本発明の原理を説明するための図である。
【００１３】
本発明（請求項４）は、隠れマルコフモデル（ＨＭＭ）を尤度によって探索する装置における隠れマルコフモデル探索方法であって、
クラスタリング手段が、入力されたオリジナルのＨＭＭの状態をクラスタリングすることにより状態数を削減し（ステップ１）、クラスタリングされたＨＭＭと該オリジナルのＨＭＭをデータ格納手段に格納するクラスタリングステップ（ステップ２）と、
探索手段が、データ格納手段に格納されている全ＨＭＭを近似尤度によって枝刈りし、探索する探索ステップ（ステップ３）と、を行う。
【００１４】
また、本発明（請求項５）は、クラスタリングステップ（ステップ２）において、
入力されたオリジナルのＨＭＭの初期状態確率、状態遷移確率、または、シンボル出力確率を用いて該ＨＭＭのクラスタリングを行い、各クラスタの初期状態確率と状態遷移確率とシンボル出力確率をそれぞれの各要素の確率の中の最大値から計算する。
【００１５】
また、本発明（請求項６）は、探索ステップ（ステップ３）において、
探索要求が入力されると、データ格納手段に格納されている全てのＨＭＭに対してレベル１の近似尤度を計算し、初期の解候補を求め、該初期の解候補に対して正確な尤度を計算し、閾値を求め閾値記憶手段に格納する初期閾値計算ステップと、
レベルを１つずつ上げ解候補でないモデルに対して近似尤度を計算し、該近似尤度と前記閾値を比較することにより、近似尤度または正確な尤度を計算するかを判定する計算判断ステップと、
計算判断ステップで計算された近似尤度が閾値以上の場合のみ、正確な尤度を計算し、尤度保存手段に格納する尤度計算ステップと、
計算された正確な尤度を用いて閾値記憶手段の閾値を更新する閾値更新ステップと、
を行う。
【００１６】
本発明（請求項７）は、コンピュータに、請求項１乃至３記載の隠れマルコフモデル探索装置の各手段を実行させるプログラムである。
【００１７】
本発明（請求項８）は、コンピュータに、請求項１乃至３記載の隠れマルコフモデル探索装置の各手段を実行させるプログラムを格納したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００１８】
上記のように本発明では、
（１）モデルの状態を結合し、尤度の上限値により高速に解候補を絞り込み、
（２）モデルを様々な近似の粒度で探索し、
（３）モデルの尤度計算を打ち止めて、尤度の低いモデルを高速に枝狩りする。
【００１９】
高速な探索と探索結果の厳密性を両立させるために、本発明では、尤度を近似して探索の解候補を絞り込んでから正確な尤度を計算する。本発明では、データ集合の中から必要最低限のものに対してのみ正確な尤度を計算するので、高速処理が可能となる。
【００２０】
つまり、
・高速処理：モデルのデータ集合が大きくても高速に探索が可能である。
【００２１】
・探索漏れなし：提案手法により探索されたモデルは厳密に正確である。
【００２２】
・モデルの構造に制限なし：モデルには複数の構造があるが、どの構造でも探索が可能である。
【発明を実施するための最良の形態】
【００２３】
以下、図面と共に本発明の実施の形態を説明する。
【００２４】
最初に本明細書中で用いる主な記号とその定義を示す。
【００２５】
【表１】
2008096742.tif 000003
次に、隠れマルコフモデル（ＨＭＭ）の定義を説明する。
【００２６】
ＨＭＭは、シーケンスを確率密度関数に従う発生モデルを有する状態の遷移として表現するデータモデルである。ＨＭＭは、以下の要素で構成される。
【００２７】
初期状態確率：α=｛αｉ｝
時刻１において状態がｕｉ（ｉ＝１，…，ｍ）である確率。
【００２８】
状態遷移確率:β=｛βｉｊ｝
時刻が１つ進んだときに状態ｕｉから状態ｕｊへ遷移する確率。
【００２９】
シンボル出力確率:γ（ｖｊ）=｛γｉ（ｖｊ）｝
状態ｕにおいてシンボルｖｊを出力する確率（ｊ＝１，…，ｓ）。
【００３０】
ここで、ＨＭＭを説明するために壷とボールの例を用いる。
【００３１】
赤や青などの色のついたボールが入っている壷が複数あることを考える。はじめにある確率によって壷を選ぶ。そしてボールを一つ取り出し、その色を記録する。次の壷は現在の壷の選択によって関連付けされた確率に従って選択する。そして、ボールの色の記録を繰り返す。これらの操作によってボールの色の系列が得られる。
【００３２】
この例において壷は状態に対応し、色の系列はシーケンスに対応する。すなわち、初期状態確率は初めに選択する壷の確率であり、状態遷移確率は次の壷の選択確率であり、シンボル出力確率はどの色のボールを選択するかの確率である。
【００３３】
ＨＭＭは、図３のように状態遷移確率βの構造によって分類することができる。図３において白い円は状態を示し、矢印は遷移を表す。全ての状態から他の全ての状態へ遷移できるタイプとして全結合ＨＭＭとエルゴティックＨＭＭ（図３（ａ））がある。エルゴティックＨＭＭは全結合ＨＭＭを包含し、全ての状態が他の全ての状態へ有限であるが非周期的な回数で遷移できる特徴がある。１回で任意の状態に遷移できるエルゴティックＨＭＭや全結合ＨＭＭにおいて状態遷移確率βは、正の計数βijを用いて以下のようになる。
【００３４】
【数１】
2008096742.tif 000004
また、他のタイプとしてleft-right ＨＭＭ（図３（ｂ））がある。left-rightＨＭＭは、状態を並べたときに左から右へ遷移する特徴がある。状態遷移確率の計数は、ｊ＜ｉ（ｉはレベル）のときβij＝０となり、ｉ≠１でαｉ＝０となる。また、left-right ＨＭＭにおいては状態間を多く遷移しないように制約が課せられていることがあり、状態遷移確率の係数はｊ>ｉ＋△−１のとき（但し、△はleft-right ＨＭＭにおける遷移の制約数）、βij＝０となる。例えば、状態遷移確率βは△＝３のときβijを用いて以下のようになる。
【００３５】
【数２】
2008096742.tif 000005
シーケンスＸの尤度Φは、Viterbiアルゴリズムにより計算される。先の壷とボールの例では尤度の計算は、ボールの系列が与えられたときにそれを出力する壷の最大確率を計算することに対応する。尤度は以下のように求める。
【００３６】
【数３】
2008096742.tif 000006
Viterbiアルゴリズムでは、図４のように状態を縦軸に、時間を横軸に並べたときに構成されるトレリス構造において、各状態における確率の最大値を動的計画法によって求めている。
【００３７】
以下に尤度の計算例を示す。
【００３８】
モデルとシーケンスが以下のようであるとする。
【００３９】
【数４】
2008096742.tif 000007
Viterbiアルゴリズムは以下のように計算される。
【００４０】
【数５】
2008096742.tif 000008
結果的に尤度はΦ=（０．５）３・（０．２５）２となり、その尤度を与える状態遷移は、ｕ１，ｕ１，ｕ２，ｕ３となる。
【００４１】
ＨＭＭの構造に制約がない場合、すなわちエルゴディックＨＭＭの場合のViterbiアルゴリズムの計算量はＯ（ｎｍ２）となる。これは全ての状態において、前の時刻の状態全てから遷移する確率を計算するからである。そのためナイーブに全てのモデルの尤度を計算するには、特にモデルの状態数が多く、またモデルの数が多いと莫大な計算コストがかかる。ナイーブに解く手法を以下では、「Naive Viterbi」と表現する。
【００４２】
以下に、本発明のＨＭＭ探索装置について説明する。
【００４３】
図５は、本発明の一実施の形態における隠れマルコフモデル探索装置の構成を示す。
【００４４】
同図に示す、隠れマルコフモデル探索装置１００は、状態クラスタリング部１１０、データ格納部１２０、探索部１３０から構成される。
【００４５】
状態クラスタリング部１１０は、入力されたオリジナルの隠れマルコフモデル（ＨＭＭ）の状態をクラスタリングする。当該状態クラスタリング部１１０では、後述するトレリス構造の縮退の処理を行うことにより、ＨＭＭの状態の数を削減する。
【００４６】
データ格納部１２０は、状態クラスタリング部１１０から状態がクラスタリングされた隠れマルコフモデルとオリジナルの隠れマルコフモデルを取得して格納する。
【００４７】
探索部１３０は、ＨＭＭを近似尤度によって枝刈りし、ＨＭＭの探索を行う。
【００４８】
以下に上記の構成における動作を説明する。
【００４９】
まず、本発明の動作の概要の概要を説明する。
【００５０】
図６は、本発明の一実施の形態における動作の概要のフローチャートである。
【００５１】
ステップ１０１）  探索前に、状態クラスタリング部１１０において、各ＨＭＭの状態のクラスタリングを行い、その結果をデータ格納部１２０に格納する。詳細な処理については、図８にて後述する。
【００５２】
ステップ１０２）  探索要求が入力されると、探索部１３０において、全てのＨＭＭに対して近似尤度を計算する。
【００５３】
ステップ１０３）  探索部１３０は、近似尤度が上位Ｋ個のＨＭＭに対してのみ正確な尤度を計算する。
【００５４】
ステップ１０４）  探索部１３０は、正確な尤度を計算したＨＭＭを暫定的な上位Ｋ個のリストとする。リストを正確な尤度で並び替え、Ｋ番目の値を枝刈りに用いる閾値に代入する。
【００５５】
ステップ１０５）  正確な尤度により枝刈りの閾値を更新しながら上位Ｋ'個のリストを生成していき、最終的なリストを記憶手段に格納する。
【００５６】
上記のステップ１０１のクラスタリングは、トレリス構造の縮退を行うものであるが、トレリス構造が大きい場合、Viterbiアルゴリズムは高い計算コストを必要とする。このため、図７（ａ）に示すように、状態をクラスタリングし、結合することによって状態の数を削減する。この状態数の削減によりトレリス構造は縮退され、高速に尤度を計算することが可能になる。トレリス構造を縮退させるために粒度ｇが与えられたとき、ｍ個の状態はｍ／ｇ個に削減される。この結果、尤度の計算量はＯ（ｎｍ２／ｇ２）に低減化される。
【００５７】
トレリス構造を縮退することには２つのメリットがあるがある。まず、第１のメリットは、トレリス構造を縮退して探索を行っても探索漏れは発生しないことが保証されることである。これは、後述するように、縮退後の近似尤度は正確な尤度により小さくならないためである。そのため近似尤度を計算するのみで、探索結果の候補を少ない計算コストで得ることができる。
【００５８】
第２のメリットとして、どのようなタイプのモデルにも適用できることがあげられる。これは状態をクラスタリングするときにモデルの確率の制約を用いないからである。
【００５９】
ここで、上記の探索漏れが発生しないことが保証される理由を述べる。
【００６０】
・補助定理１：状態を結合後のモデルとシーケンスが与えられたとき、以下の関係が成立する。
【００６１】
Φ≦Ψ                        （６）  
証明１：オリジナルのＨＭＭの状態ｕ１（１≦ｉ≦ｍ）が状態ｕ'１（１≦ｉ≦ｍ'）へクラスタリングされたとすると、
【００６２】
【数６】
2008096742.tif 000009
となるので、２≦ｔ≦ｎのとき、
【００６３】
【数７】
2008096742.tif 000010
よって
【００６４】
【数８】
2008096742.tif 000011
が成り立つ。
【００６５】
上記の補助定理１により探索漏れなくモデルを探索することができる。
【００６６】
・補助定理２：Ψを用いて探索することは、探索漏れが発生しないことの十分条件である。
【００６７】
証明２：ｋ-近傍探索のＫ番目の解の尤度をεとしたとき、探索漏れが発生しないことを保証するためには、Φ≧εであるときΨ≧εでなければならない。ところで、式（６）より、
ε≦Φ≦Ψ
となるので探索漏れは発生しない。
【００６８】
図８は、本発明の一実施の形態における状態のクラスタリング処理のフローチャートである。
【００６９】
ステップ２０１）  状態クラスタリング部１１０は、オリジナルのｍ個のＨＭＭと粒度ｇが与えられると、ｍ個のＨＭＭと粒度ｇが与えられると、ｍ個の状態をｍ'ｇ個にクラスタリングし、オリジナルのＨＭＭとクラスタリングされたＨＭＭをデータ格納部１２０に格納する。具体的には、状態クラスタリング部１１０は、状態ｕｉとｕｊが与えられると、ｕｉとｕｊの距離Ｄ（ｕｉ，ｕｊ）を以下にように定義する。
【００７０】
【数９】
2008096742.tif 000012
上記の（１）の定義において、ｄ１は初期状態の確率の差、ｄ２とｄ３は状態遷移確率の差、ｄ４はシンボル出力確率の差を表している。
【００７１】
本実施の形態の状態クラスタリング部１１０では、状態をクラスタリングするためK-means法（例えば、文献「宮本定明"クラスタ分析入門"1999」参照）を用いる。トレリス構造の縮退する方法はクラスタリング方法の選択とは完全に独立したものであるため、他のクラスタリング方法（例えば、文献「Tian Zhang and Raghu Ramakrishnan and Miron Livny, BIRCH: An Efficient Data Clustering Method for Very Large Databases. SIGMOD Conference, 1996」参照）を用いることも可能である。
【００７２】
ステップ２０２）  状態クラスタリング部１１０は、各クラスタの初期状態確率、状態遷移確率、シンボル出力確率を、各要素の確率の中の最大値から計算する。
【００７３】
具体的には、状態ｕｉとｕｊが同じクラスタになった場合、結合後の確率は、
【００７４】
【数１０】
2008096742.tif 000013
となる。
【００７５】
＜例１＞
ＨＭＭにおいて状態ｕ１とｕ２が同じクラスタになった後の確率は以下のようになる。
【００７６】
【数１１】
2008096742.tif 000014
上記の例において、確率はそれぞれ
【００７７】
【数１２】
2008096742.tif 000015
と計算する。２つの状態が同じクラスタになる場合について説明したが、３つ以上の場合でも同様に計算する。
【００７８】
次に、探索部１３０について説明する。
【００７９】
探索部１３０では、高速に解を求めるために近似尤度を用いて尤度の低い殆どのモデルの枝刈りを行う。これにより、計算コストのかかる正確な尤度計算は必要最低限に限定される。
【００８０】
図９は、本発明の一実施の形態における探索部の構成を示す。
【００８１】
探索部１３０は、初期閾値計算部１３１、計算判定部１３２、尤度計算部１３３、尤度保存部１３４から構成される。
【００８２】
初期閾値計算部１３１は、探索要求があったときに探索を行うための閾値の初期値を近似尤度による探索結果から計算し、閾値を格納するための閾値格納部１３５に格納する。
【００８３】
計算判定部１３２は、閾値を用いて近似尤度または正確な尤度を計算するかを判定する。
【００８４】
尤度計算部１３３は、近似尤度または正確な尤度を計算して格納すると共に、当該尤度を用いて閾値を格納するための尤度格納部１３５内の閾値を更新する。
【００８５】
尤度保存部１３４は、尤度計算部１３４で計算された尤度を保存する。
【００８６】
閾値格納部１３５は、求められた閾値εを格納する。
【００８７】
探索部１３０の初期閾値計算部１３１では、まず、データ格納部１２０に格納されている全てのモデルに対して最も粗い近似尤度を計算し、近似尤度の降順によって並び替えを行う。そして、Ｋ番目までのモデル全てに対して正確な尤度を計算し、最も小さい尤度をε（閾値）とし、閾値格納部１３５に格納する。εは複数の近似尤度により枝刈りと状態遷移の枝刈りに用いられるが、εの真のＫ番目の解の尤度に近いほど探索の効率が上がるためである。このはじめに求めたＫ個のモデルはｋ−近傍探索のための初期の解候補となる。
【００８８】
初期閾値計算部１３１では、まず、データ格納部１２０に格納されている全てのモデルに対してレベル１の近似尤度を計算し、初期の解候補を求める。初期の解候補に対して正確な尤度を計算し、εを求める。そしてレベルを１つずつ上げ解候補でないモデルに対して近似尤度を計算し、閾値格納部１３５に格納する。そして、計算判定部１３２において、もし、近似尤度がεより小さいと判断すれば、そのモデルのオリジナル尤度はその近似尤度より大きくなることはないので枝狩りし、尤度計算部１３４における正確な尤度の計算は行わない。計算判定部１３２において全てのレベルの近似尤度がε以上であると判断された場合のみ、尤度計算部１３３において正確な尤度を計算し、尤度保存部１３４に格納する。もし正確な尤度がε以上であれば閾値格納部１３５のεを更新する。εは探索処理の途中において更新され続けられるので、枝狩りはさらに効果的になっていく。
【００８９】
図１０は、本発明の一実施の形態におけるＨＭＭの探索処理のフローチャートである。以下の動作は、図６のステップ１０２〜１０４の処理に対応する。
【００９０】
ステップ３０１）  初期閾値計算部１３１は、データ格納部１２０から取得した全てのＨＭＭに対してレベル１の近似尤度を計算し、閾値格納部１３５に格納する。
【００９１】
ステップ３０２）  初期閾値計算部１３１は、データ格納部１２０全てのＨＭＭをステップ３０１で計算された近似尤度の降順で並び替える。
【００９２】
ステップ３０３）  初期閾値計算部１３１は、データ格納部１２０の上位Ｋ個のＨＭＭに対してのみ正確な尤度を計算する。
【００９３】
ステップ３０４）  初期閾値計算部１３１は、正確な尤度を計算したＨＭＭを暫定的な上位Ｋ個のリストとし、データ格納部１２０に格納する。データ格納部１２０のＫ個のＨＭＭのリストを正確な尤度の降順で並び替える。
【００９４】
ステップ３０５）  閾値格納部１３５のεにＫ番目の尤度を代入する。
【００９５】
ステップ３０６）  ｉ＝１とする。
【００９６】
ステップ３０７）  計算判定部１３２は、ｉ≦ｍ（ＨＭＭの個数）であるかを判定し、そうである場合にはステップ３０８に移行し、そうでない場合は、尤度保存部１３４に格納されている尤度を出力して処理を終了する。
【００９７】
ステップ３０８）  計算判定部１３２は、閾値格納部１３５のεを参照し、レベル１の近似尤度がεより小さいかを判定し、小さい場合はステップ３１０に移行し、そうでない場合はステップ３０９に移行する。
【００９８】
ステップ３０９）  ｉの値をインクリメントし、ステップ３０７に移行する。
【００９９】
ステップ３１０）  レベルをｊ＝２とする。
【０１００】
ステップ３１１）  計算判定部１３２は、ｊ≦ｈ（但し、ｈは近似粒度のレベルの数）であるかを判定し、そうである場合には、ステップ３１２に移行し、そうでない場合はステップ３１５に移行する。
【０１０１】
ステップ３１２）  尤度計算部１３３はレベルｊの近似尤度を計算し、尤度保存部１３４に格納する。
【０１０２】
ステップ３１３）  レベルｊの近似尤度がεより小さい場合は、ステップ３１５に移行し、そうでない場合は、ステップ３１５に移行する。
【０１０３】
ステップ３１４）  計算判定部１３２は、ｊ=ｈであるかを判定し、そうであるならばステップ３１６に移行し、そうでないならばステップ３１５に移行する。
【０１０４】
ステップ３１５）  ｊの値をインクリメントし、ステップ３１１に移行する。
【０１０５】
ステップ３１６）  尤度計算部１３３は、正確な尤度を計算し、尤度保存部１３４に格納する。
【０１０６】
ステップ３１７）  計算判定部１３２は、正確な尤度が閾値格納部１３５のεより小さいかを判定し、小さい場合は、ステップ３０９に移行し、そうでない場合はステップ３１８に移行する。
【０１０７】
ステップ３１８）  尤度計算部１３２は、尤度保存部１３４のリストのＫ番目に計算した尤度を代入する。
【０１０８】
ステップ３１９）  計算判定部１３２は、尤度保存部１３４のリストを尤度の降順で並び替える。
【０１０９】
ステップ３２０）  計算判定部１３２は、閾値格納部１３５のεにＫ番目の尤度を代入し、ステップ３０９に移行する。
【０１１０】
上記のフローチャートのステップ３０１〜３０５では、ｋ−近傍検索のＫ番目の尤度により近いεtempをできるだけ少ない回数の正確な尤度計算で求める。
【０１１１】
ステップ３０８〜３１４では、εにより枝狩りを行うことで正確な尤度を計算しなくて済む。
【０１１２】
ステップ３２０では、閾値格納部１３５のεの更新により枝狩りの効果を上げる。
【０１１３】
次に、上記のステップ３０１における初期閾値計算部１３１における近似尤度計算処理について説明する。
【０１１４】
図１１は、本発明の一実施の形態における初期閾値計算部の近似尤度の計算処理のフローチャートである。
【０１１５】
ステップ４０１）  探索部１３０の初期閾値計算部１３１は、ＨＭＭのカウンタをｉ＝１とする。
【０１１６】
ステップ４０２）  ｉ≦ｎであるかを判定し、そうであればステップ４０３に移行し、そうでなければステップ４０６に移行する。
【０１１７】
ステップ４０３）  ｉが１であるかを判定し、そうであれば、ステップ３０４に移行し、そうでなければステップ４０５に移行する。
【０１１８】
ステップ４０４）  初期閾値計算部１３１は、全ての状態に対して、入力された初期状態確率と、シンボル出力確率を乗算し、状態の尤度を計算し、ｉをインクリメントしてステップ４０２に移行する。具体的には、初期状態確率αとシンボル出力確率γとを用いて
【０１１９】
【数１３】
2008096742.tif 000016
（但し、tは時刻）
により尤度を計算する。
【０１２０】
ステップ４０５）  初期閾値計算部１３１は、全ての状態に対してひと時刻前の状態の尤度とその状態遷移確率の最大値と、シンボル出力確率γを乗算し、状態の尤度を計算し、ｉの値をインクリメントしてステップ４０２に移行する。具体的には、
【０１２１】
【数１４】
2008096742.tif 000017
（但し、ｘはシーケンス）
により計算する。
【０１２２】
ステップ４０６）  ステップ４０２において、ｉ＞ｎとなった場合に、初期閾値計算部１３１は、全ての状態の中から尤度の最大値を求めて近似尤度を計算する。具体的には、
【０１２３】
【数１５】
2008096742.tif 000018
により計算する。
【０１２４】
上記の近似尤度の計算において、一つの粒度ｇでトレリス構造を縮退し近似尤度を計算したが、しかし、近似の粒度が低ければ近似精度も異なるため、モデル毎の正確な尤度に応じて近似の尤度が異なることが望ましい。そのため、本発明では、一つの粒度ではなく、複数の粒度の近似を用いてモデルを探索する。すなわち、探索において徐々に近似粒度を上げていく。
【０１２５】
トレリス構造を縮退することで計算される近似尤度により高速な探索が可能になるが、近似計算には近似精度と時間計算のトレードオフが存在する。すなわち、トレリス構造を過度に縮退させると近似尤度の計算コストは小さくなるが、近似尤度の上限値は大きくなってしまう。そのため、本発明では、探索処理において徐々にトレリス構造のサイズを大きくしていき、近似尤度の精度をあげていく。
【０１２６】
図７（ｂ）に示すように、複数の近似尤度を用いることでモデルの正確な尤度に応じた近似粒度で計算を行うことができる。尤度が小さいモデルは低い粒度の近似で枝刈りすることができるが、尤度が大きいモデルは高い粒度の近似でないと枝刈りできない。言い換えれば低い粒度で枝刈りした結果として高い尤度のモデルを得られる。そのため、本発明では、低い粒度の結果のみに対して高い粒度の近似を計算する。結果として相反する近似精度と計算時間のバランスを取ることができる。
【０１２７】
本発明ではｈ個の粒度を用いる。レベルｉ（１≦ｉ≦ｈ）の近似においては粒度ｇｉを用いて、ｍ個の状態を
【０１２８】
【数１６】
2008096742.tif 000019
個に結合する。最も粗い粒度をｇ１とすると、レベルが上がるにつれてｇｉも大きくなり、近似尤度の精度も上がっていく。
【０１２９】
探索では、まずレベル１の
【０１３０】
【数１７】
2008096742.tif 000020
個に状態を結合した近似尤度を全てのモデルに対して計算する。近似尤度によってＫ個の候補を求めて、その中からＫ番目の正確な尤度εを計算し、尤度保存部１３４に保存する。εより小さい近似尤度を持つモデルは枝刈りできる。そうでないモデルに対しては、レベル２の近似尤度を計算し、同様に近似尤度が尤度保存部１３４のεより小さいか調べる。この操作をレベルがｈになるまで行う。結果的にモデルを正確な尤度に従った近似の粒度によって枝刈りすることができる。
【０１３１】
次に、近似尤度または正確な尤度の計算時における枝刈りについて説明する。
【０１３２】
本発明は、探索結果の厳密性を保証している。トレリス構造を縮退することにより高速な探索が可能になるが、厳密に正確な探索結果は近似尤度からは求めることができない。そのため本発明では、近似尤度で求めた候補に対して正確な尤度を求めている。しかし、正確な尤度を計算するには大きなコストがかかる。
【０１３３】
本発明では、尤度計算の中には探索処理として必要のないものも含まれるため、図７（ｃ）のようにトレリス構造における尤度計算を高速に打ち切る。
【０１３４】
例えば、前述の例１において、探索途中のＫ番目に高い尤度が０．２５であるときに、時刻１における状態ｕ２とｕ３の尤度は０．２５より小さいため、時刻２においてこれらの状態から遷移する確率は計算する必要はない。同じように時刻３において状態ｕ３からの確率は計算する必要はない。時刻３において全ての状態の確率は０．２５より小さいため、尤度計算を打ち切ることができる。
【０１３５】
探索途中のＫ番目に高い尤度が大きくなるほど、より効果的に計算を打ち切ることができる。ここでＫ番目に高い尤度は探索処理が進むほど大きくなるので、結果的にモデルの数が多くても効果的に探索することができる。
【０１３６】
また、計算の途中では尤度は単調減少するため、問い合わせのシーケンスが長くなるほど状態遷移の打ち切りはより効果的になる。これは、ユーザやアプリケーションによって問い合わせの長さが異なることを考えると、非常に有効な性質である。
【０１３７】
また、状態遷移の打ち切りは正確なトレリス構造のみならず、縮退後のトレリス構造に対しても適用できる。すなわち、状態遷移を打ち切ることで近似計算を高速化できる。
【０１３８】
以下の枝刈りの方法は、初期閾値計算部１３１、尤度計算部１３３における近似尤度の計算に用いられる。
【０１３９】
図１２は、本発明の一実施の形態における状態遷移の枝刈りの処理のフローチャートである。同図では、状態遷移の枝刈りを示す。
【０１４０】
ステップ５０１）  尤度計算部１３３は、ｉ＝１とする。
【０１４１】
ステップ５０２）  ｉ≦ｎである場合には、ステップ５０３に移行し、そうでない場合はステップ５０９に移行する。
【０１４２】
ステップ５０３）  尤度計算部１３３は、時刻ｉの遷移集合を空集合にする。
【０１４３】
ステップ５０４）  ｉが１である場合にはステップ５０５に移行し、そうでない場合は、ステップ５０６に移行する。
【０１４４】
ステップ５０５）  尤度計算部１３３は、全ての状態の尤度を初期状態確率を用いて計算し、ステップ５０７に移行する。
【０１４５】
ステップ５０６）  尤度計算部１３３は、ステップ５０４においてｉが１でない場合に、全ての状態の尤度を時刻ｉ−１の遷移集合に含まれる状態からの状態遷移確率を用いて計算する。このように全ての状態からの遷移によって計算を行わないことにより、計算の高速化が図れる。
【０１４６】
ステップ５０７）  尤度計算部１３３は、尤度が閾値ε以上の状態を尤度保存部１３４の時刻ｉの遷移集合に加える。当該処理は、検索の解候補になり得る状態を求めるものである。
【０１４７】
ステップ５０８）  時刻ｉの遷移集合が空集合である場合は、ステップ５０９に移行し、そうでない場合は、ｉの値をインクリメントしてステップ５０２に移行する。これにより、尤度計算中のＨＭＭは検索の解候補になりえないため計算を打ち切ることにより、高速化が図れる。
【０１４８】
ステップ５０９）  尤度計算部１３３は、全ての状態の中から尤度の最大値を求めて尤度を計算する。
【０１４９】
状態遷移の枝刈りでは遷移集合を用いて処理を行う。遷移集合はトレリス構造のそれぞれの時刻毎に設定される。時刻ｔの状態ｕｉの尤度がε以上であれば、時刻ｔの遷移集合に状態ｕｉが加えられる。尤度を計算するときは時刻ｔ−１の遷移集合に含まれる状態からの遷移のみを用いる。もしある時刻における遷移集合が空集合であれば、そのモデルは解候補となりえないため、尤度計算を打ち切る。近似尤度の計算においても同様の処理で高速化を行う。
【０１５０】
［評価実験］
上記のような方法によるＨＭＭの探索の有効性を示すための実験を行った。
【０１５１】
実験は、エルゴディックＨＭＭとleft-right ＨＭＭに対して行った。実験では、探索におけるＣＰＵの計算時間を比較した。実験は、ＣＰＵがPentium4の3.2GHz、メインメモリが１ＧＢのマシンで行った。
【０１５２】
本発明の大きな一つの応用例として、ビデオメタサービスが挙げられるので、実験データとしてビデオデータを用いた。ビデオデータからはオーディオシーケンスやモーションベクトルなどの多くの特徴量が抽出できる。その中で実験では動画フレームのヒストグラムを用いた。ヒストグラムは多くの研究において用いられる特徴量だからである。実験では特にHuangらの研究「Jincheng Huang and Zhu Liu and Yao Wang, Joint scene classification and segmentation based on hidden Markov model. IEEE Transactions on Multimedia, 2005」を参考に特徴量を計算した。
【０１５３】
・実験条件
HuangらのＨＭＭを用いたビデオのシーンのクラスタリングの研究を行った。彼らは特徴量の一つとして色ヒストグラムを用い、特徴量の値として最も優勢なヒストグラムの要素を用いた。本発明の実験では、サッカー、ニュース、ドラマなどのビデオから５０００個のシーンを切り出して特徴量を計算し、実験データとした。動画は１秒あたり３０フレームで構成される。各フレームのヒストグラムを６４個に量子化し、最も高い値の要素を優勢な要素とし特徴量とした。各モデルの確率は特徴量からBuan-Welchアルゴリズム「S.E. Levinson and L. R. Rabiner and M. M. Sondhi, An Introduction to the Application of the Theory of Probabilistic Functions of a Markov Process to Automatic Speech Recognition, Bell Syst. Tech. J, 1982」により求めた。
【０１５４】
実験におけるパラメータは問い合わせの個数Ｋ＝３、複数の近似粒度のレベルの数ｈ＝３、レベルｉにおける粒度ｇｉ=４ｈ−ｉ＋１、left-right ＨＭＭにおける遷移の制約数△＝０．２・ｍとした。
【０１５５】
探索処理時間について状態数を変化させた場合と、モデルの数を変化させた場合について実験を行った。
【０１５６】
状態数を変化させて実験を行った。実験においてシーケンスの長さをｎ＝１０００とした。実験結果を図１３に示す。同図の結果を見ると、本発明はNaive Viterbiと比較して本実験の条件下でエルゴディックＨＭＭに対して約９８５倍まで、left-right ＨＭＭに対して約１２７倍まで高速な探索が行えている。エルゴディックＨＭＭにおいてNaive Viterbiの計算量はＯ（ｎｍ２）であるのに対して、本発明では、複数粒度の近似尤度を計算する計算量はＯ（ｎｍ２／ｇ２）だからである。同様な理由により、left-right ＨＭＭに対しても高速化が達成できている。近似尤度を用いても枝刈りできないモデルに対しては正確な尤度を計算するのでＯ（ｎｍ２）の計算量を要する。しかし後述するようにそのようなモデルの数は少ないので実験結果に影響はなかった。
【０１５７】
モデルの数を変化させて実験を行った。実験において状態数ｍ＝１００とした。実験結果を図１４に示す。結果を見ると本発明はナイーブな手法と比較して本実験の条件下でエルゴディックＨＭＭに対して約９８５倍まで、left-right ＨＭＭに対して約１２７倍まで高速な探索が行えている。これはモデルの数が大きくなるほど、相対的に探索の早期にｋ−近傍探索のＫ番目の解の尤度εが見つかるため、複数の近似粒度による枝刈りと状態遷移の枝刈りがより効果的になるからである。
【０１５８】
本発明では、近似尤度を計算し、枝刈りできなかったモデルにのみ正確な尤度を計算する。そのため、正確な尤度を計算するモデルの数が探索の高速化に影響する。そこで実験では各レベルにおける近似尤度を計算したモデルの数と、正確な尤度を計算したモデルの数を調べた。実験では状態数ｍ＝１００、シーケンスの長さｎ＝１０００とした。実験結果を図１５に示す。図１５において、「Level 1」「Level 2」「Level 3」とあるのは各レベルの近似尤度を計算したモデルの数であり、「Exact」とあるのは正確な尤度を計算したモデルの数である。図１５からエルゴディックＨＭＭに対してもleft-rightＨＭＭに対してもレベルが上がるごとに近似尤度を計算している数が減少していることがわかる。これは小さな尤度をもつモデルは粗い近似でも枝刈りできるからである。結果的に正確な尤度を計算しているモデルの数は、モデルの総数と比較して非常に小さいことがわかる。そのため、本発明では、図１３、図１４に示すような高速化が行えている。
【０１５９】
本発明では探索漏れがないことを保証するために、近似尤度で枝刈りができなかったモデルに対して正確な尤度を計算する。状態遷移の枝刈りにおいては探索途中のＫ番目の尤度εより小さい尤度をもつ状態からの遷移の計算を枝刈りする。そのため多くの状態がεより小さい尤度であるほど、探索の高速化が行われる。状態遷移の枝刈りは近似尤度の計算に対しても適用できるが、実験では正確な尤度の計算においてトレリス構造の縦軸方向に対するεより小さい尤度の状態の割合を調べた。実験では状態数ｍ＝１００、シーケンスの長さｎ＝１０００とした。
【０１６０】
エルゴディックＨＭＭの結果を見ると、トレリス構造の横軸方向のポイントが増加するほどεより小さい尤度の状態の割合が多くなることがわかる。これは、Viterviアルゴリズムは動的計画法により計算されるので、尤度計算の途中においては尤度は単調減少するためである。
【０１６１】
また、left-right ＨＭＭの結果を見ると、トレリス構造の横軸方向のはじめから多くの状態の尤度が小さいことがわかる。これはleft-right ＨＭＭにおいては状態の遷移が必ずｕ１から始まるからである（ｉ＝１でαｉ＝１，ｉ≠１でαｉ＝０）。トレリス構造の横軸方向のはじめのポイントで状態ｕ１の尤度が小さいと、全ての状態の尤度は小さくなる。
【０１６２】
上記のＨＭＭ探索装置の構成要素の動作をプログラムとして構築し、ＨＭＭ探索装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１６３】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、コンピュータにインストールする、または、配布することが可能である。
【０１６４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１６５】
本発明のＨＭＭ探索を、例えばビデオシーンメタデータを関連付けるビデオメタサービス等に適用可能である。
【図面の簡単な説明】
【０１６６】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】ＨＭＭの種類である。
【図４】トレリス構造である。
【図５】本発明の一実施の形態における隠れマルコフモデル探索装置の構成図である。
【図６】本発明の一実施の形態における動作の概要のフローチャートである。
【図７】本発明における手法の概要を説明するための図である。
【図８】本発明の一実施の形態における状態のクラスタリング処理のフローチャートである。
【図９】本発明の一実施の形態における探索部の構成図である。
【図１０】本発明の一実施の形態におけるＨＭＭの探索処理のフローチャートである。
【図１１】本発明の一実施の形態における初期閾値計算部の近似尤度の計算処理のフローチャートである。
【図１２】本発明の一実施の形態における状態遷移の枝刈り処理のフローチャートである。
【図１３】本発明の実験における状態数を変化させた場合の探索時間である。
【図１４】本発明の実験におけるモデルの数を変化させた場合の探索時間である。
【図１５】本発明の実験における尤度の計算回数である。
【図１６】本発明の実験における小さい尤度の状態の割合である。
【符号の説明】
【０１６７】
１００  隠れマルコフモデル探索装置
１１０  クラスタリング手段、クラスタリング部
１２０  データ格納手段、データ格納部
１３０  探索手段、探索部
１３１  初期閾値計算部
１３２  計算判定部
１３３  尤度計算部
１３４  尤度保存部
１３５  閾値格納部
【図１】
2008096742.tif 000021
【図２】
2008096742.tif 000022
【図３】
2008096742.tif 000023
【図４】
2008096742.tif 000024
【図５】
2008096742.tif 000025
【図６】
2008096742.tif 000026
【図７】
2008096742.tif 000027
【図８】
2008096742.tif 000028
【図９】
2008096742.tif 000029
【図１０】
2008096742.tif 000030
【図１１】
2008096742.tif 000031
【図１２】
2008096742.tif 000032
【図１３】
2008096742.tif 000033
【図１４】
2008096742.tif 000034
【図１５】
2008096742.tif 000035
【図１６】
2008096742.tif 000036