(57)【特許請求の範囲】
【請求項１】
データベース、近似尤度計算手段、構造縮退手段、尤度計算手段と、を有する隠れマルコフモデル検索装置における、該データベースに格納された隠れマルコフモデルを、尤度によって検索する隠れマルコフモデル検索方法であって、
前記構造縮退手段において、検索処理の前に、前記データベースの前記隠れマルコフモデル（以下、ＨＭＭと記す）の状態及び出力信号に対して縮退処理を行い、該データベースに格納する構造縮退ステップと、
前記近似尤度計算手段において、検索要求を取得すると、前記データベースから前記構造縮退ステップにより縮退されたＨＭＭを読み出して、該ＨＭＭの近似尤度を計算する近似尤度計算ステップと、
前記尤度計算手段において、前記近似尤度から前記データベースに格納されているＨＭＭの枝刈りに用いる閾値の初期値を計算する初期値計算ステップと、該閾値の初期値と記憶手段に格納された更新された閾値に基づいて、オリジナルのＨＭＭの尤度を計算するかを判定する尤度計算判定ステップと、判定結果に基づいて、前記データベースに格納されている該オリジナルのＨＭＭの尤度を計算するＨＭＭ尤度計算ステップと、前記ＨＭＭを該オリジナルの尤度によって枝刈りする枝刈りステップと、検索を行い、該オリジナルの尤度を尤度記憶手段に記憶すると共に、上位Ｋ番目のＨＭＭの尤度で該記憶手段の閾値を更新する尤度計算ステップからなる処理のうち、該尤度計算判定ステップ以降の処理をＨＭＭ数になるまで繰り返す尤度計算ステップと、
を行うことを特徴とする隠れマルコフモデル検索方法。
【請求項２】
前記近似尤度計算ステップにおいて、
外部から前記検索要求として時系列信号と検索個数を受け取り、また、前記データベースから縮退後のＨＭＭを取得し、縮退後の近似尤度を計算し、近似尤度記憶手段に格納するステップと、
前記近似尤度記憶手段に格納された前記近似尤度を並べ替えるステップと、
前記近似尤度によって検索の解候補を計算するステップと、
を行うことにより前記近似尤度によって検索の解候補を計算する請求項１記載の隠れマルコフモデル検索方法。
【請求項３】
前記構造縮退ステップにおいて、
外部から縮退後のＨＭＭの状態数とオリジナルのＨＭＭの状態を取得し、また、縮退途中の状態を受け取り、状態統合誤差を計算するステップと、
前記状態誤差を取得して、該状態統合誤差の最も小さい状態同士を統合するステップと、
外部から縮退後のＨＭＭの出力信号数とオリジナルのＨＭＭの出力信号を受け取り、また、縮退途中の出力信号を受け取り、該オリジナルのＨＭＭの出力信号と該縮退途中の出力信号から出力信号統合誤差を計算するステップと、
前記出力信号統合誤差の最も小さい出力信号同士を統合するステップと、
を行うことにより統合誤差が小さくなるように状態や出力信号を縮退する請求項１記載の隠れマルコフモデル検索方法。
【請求項４】
前記オリジナルのＨＭＭの尤度を計算するステップにおいて、
前記データベースに格納された前記ＨＭＭのタイプによって尤度を計算する時に用いる遷移集合の初期集合を計算するステップと、
初期の遷移集合と更新後の遷移集合を用いて尤度を計算するステップと、
計算された前記尤度から前記遷移集合を更新し、また、計算された尤度を前記尤度記憶手段に格納するステップと、
を行うことにより検索に影響ない範囲で不要な遷移からの計算を打ち切る請求項１記載の隠れマルコフモデル検索方法。
【請求項５】
データベースに格納された隠れマルコフモデル（以下、ＨＭＭと記す）を、尤度によって検索する隠れマルコフモデル検索装置であって、
オリジナルのＨＭＭと縮退されたＨＭＭを格納するデータベースと、
検索処理の前に、前記データベースの前記ＨＭＭの状態及び出力信号に対して縮退処理を行い、該データベースに格納する構造縮退手段と、
検索要求を取得すると、前記データベースから前記構造縮退手段により縮退されたＨＭＭを読み出して、該ＨＭＭの近似尤度を計算する近似尤度計算手段と、
前記近似尤度から前記データベースに格納された前記ＨＭＭの枝刈りに用いる閾値の初期値を計算する初期値計算手段と、該閾値の初期値と記憶手段から更新された閾値を受け取り、該閾値を用いてオリジナルのＨＭＭの尤度を計算するかの判定を行う計算判定手段と、該計算判定手段の判定結果に基づいて、前記データベースに格納されている該オリジナルのＨＭＭの尤度を計算するＨＭＭ尤度計算手段と、前記ＨＭＭを該オリジナルの尤度によって枝刈りする枝刈り手段と、検索を行い、該オリジナルの尤度を尤度記憶手段に記憶すると共に、上位Ｋ番目のＨＭＭの尤度で該尤度記憶手段の閾値を更新する尤度保存手段と、該計算判定手段、該HMM尤度計算手段、該尤度保存手段の処理を、ＨＭＭ数になるまで繰り返す繰り返し手段と、からなる尤度計算処理手段と、
を有することを特徴とする隠れマルコフモデル検索装置。
【請求項６】
前記近似尤度計算手段は、
外部から前記検索要求として時系列信号と検索個数を受け取り、また、前記データベースから縮退後のＨＭＭを取得し、縮退後の近似尤度を計算し、近似尤度記憶手段に格納する近似尤度算出手段と、
前記近似尤度記憶手段に格納された前記近似尤度を並べ替える近似尤度ソート手段と、
を有する請求項５記載の隠れマルコフモデル検索装置。
【請求項７】
前記構造縮退手段は、状態統合誤差計算手段と、状態統合手段と、出力信号統合誤差計算手段と、出力信号統合手段と、を含み、
前記状態統合誤差計算手段は、
外部から縮退後のＨＭＭの状態数とオリジナルのＨＭＭの状態を取得し、また、前記状態統合手段から縮退途中の状態を受け取り、状態統合誤差を計算し、
前記状態統合手段は、
前記状態誤差を取得して、該状態統合誤差の最も小さい状態同士を統合し、
前記出力信号統合誤差計算手段は、
外部から縮退後のＨＭＭの出力信号数とオリジナルのＨＭＭの出力信号を受け取り、また、前記出力信号統合手段から縮退途中の出力信号を受け取り、該オリジナルのＨＭＭの出力信号と該縮退途中の出力信号から出力信号統合誤差を計算し、
前記出力信号統合手段は、
前記出力信号統合誤差の最も小さい出力信号同士を統合する
請求項５記載の隠れマルコフモデル検索装置。
【請求項８】
前記尤度計算手段は、遷移集合計算手段、尤度算出手段と、遷移集合更新手段と、を有し、
前記遷移集合計算手段は、
前記データベースに格納された前記ＨＭＭのタイプによって尤度を計算する時に用いる遷移集合の初期集合を計算し、
前記尤度算出手段は、
前記遷移集合計算手段で計算された初期の遷移集合と、前記遷移集合更新手段から取得した更新後の遷移集合を用いて尤度を計算し、
前記遷移集合更新手段は、
前記尤度算出手段で計算された前記尤度から前記遷移集合を更新し、また、計算された尤度を前記尤度記憶手段に格納する、
請求項５記載の隠れマルコフモデル検索装置。
【請求項９】
データベースに格納された隠れマルコフモデルを、尤度によって検索する隠れマルコフモデル検索プログラムであって、
コンピュータを、
請求項５乃至８記載の隠れマルコフモデル検索装置として機能させることを特徴とする隠れマルコフモデル検索プログラム。
【請求項１０】
データベースに格納された隠れマルコフモデルを、尤度によって検索する隠れマルコフモデル検索プログラムを格納したコンピュータ読み取り可能な記録媒体であって、
コンピュータを、
請求項５乃至８記載の隠れマルコフモデル検索装置として機能させるプログラムを格納したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、隠れマルコフモデル検索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体に係り、特に、複数のＨＭＭ(Hidden Markov Model)が格納されたデータベースに時系列信号が与えられたときに、尤度の高いＨＭＭを高速かつ漏れなく検索するための隠れマルコフモデル検索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
データの処理時間を短縮される技術として、圧縮された動画像データを使用する方法がある（例えば、特許文献１参照）。しかしながら、上記の動画像データを使用してデータ処理時間を短縮する方法は、ＨＭＭを用いて動画を検索する技術、ＨＭＭの計算そのものを高速化することは考えられていない。
【０００３】
ＨＭＭを扱う技術として、left-rightＨＭＭをハードウェアに実装する技術がある（例えば、特許文献２参照）。しかしながら、当該技術は、検索のアルゴリズムの高速化については考慮されていない。
【０００４】
また、出力信号によりインデックスをデータベースに付与する技術がある（例えば、特許文献３参照）。しかしながら、当該技術は、出力信号によりインデックスを付与しており、探索も例が発生しうる。
【０００５】
時系列データは金融、環境、モバイル、マルチメディア等の様々な分野で発生する汎用的なデータ構造である。そのためデータベースの分野では、事前に時系列データを格納しておき、検索結果により問い合わせの時系列データを分類する研究が多く行われている。
【０００６】
一般的に時系列データを格納する場合、時系列データは時間が経過する毎に発生する性質があるため、時系列データの量は膨大になる。そのため、従来より大量の時系列データに対する高速検索を対象にした研究が多く行われてきた。
【０００７】
時系列データの検索は、類似度によって行われるが、多くの研究において類似度としてユークリッド距離かＤＴＷ(Dynamic Time Warping)が用いられている。ＤＴＷは、ユークリッド距離のノイズやアウトライアー（異常値）等に弱い性質を回避するための類似度であり、時系列データ間の距離を最小にするように時間軸方向に伸長させる時系列データの変換処理である。ＤＴＷの類似度は動的計画法により計算される。
【０００８】
しかし、実際のアプリケーションにおいては時系列データそのものではなく、時系列信号の発生モデルを格納しておいて検索されることが多く行われる。時系列信号の発生モデルによる検索は非常にノイズやアウトライナー等に強いからである。
【０００９】
ＨＭＭは、時系列信号の発生モデルが確率密度関数に従うと仮定し、発生モデルが時間的に変化することを発生モデルを有する状態の遷移として表現するデータ構造である。多くのアプリケーションにおいてHMMが格納されている場合、検索は問い合わせの時系列信号が格納されたＨＭＭによって推定される尤度によって行われる。
【特許文献１】特開平１０−１３８３２号公報
【特許文献２】特開平５−２３３８１７号公報
【特許文献３】特開平８−２３５２２１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上記の問い合わせの時系列信号が格納されたＨＭＭによって推定される尤度により検索する方法において、尤度は動的計画法によって計算するが、一般にＨＭＭの状態数は多く、また、時系列信号は長いため、尤度を計算する計算コストは高くなる。そのため、内部に格納された全てのＨＭＭの尤度を計算して解く手法の計算コストは莫大になってしまう。
【００１１】
本発明は、上記の点に鑑みなされたもので、尤度の高いＨＭＭを高速かつもれなく検索することが可能な隠れマルコフモデル検索方法及び装置及びプログラム及びコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１２】
図１は、本発明の原理を説明するための図である。
【００１３】
本発明（請求項１）は、データベース、近似尤度計算手段、構造縮退手段、尤度計算手段と、を有する隠れマルコフモデル検索装置における、該データベースに格納された隠れマルコフモデルを、尤度によって検索する隠れマルコフモデル検索方法であって、
構造縮退手段において、検索処理の前に、データベースの隠れマルコフモデル（以下、ＨＭＭと記す）の状態及び出力信号に対して縮退処理を行い、該データベースに格納する構造縮退ステップ（ステップ１）と、
近似尤度計算手段において、検索要求を取得すると、データベースから構造縮退ステップにより縮退されたＨＭＭを読み出して、該ＨＭＭの近似尤度を計算する近似尤度計算ステップ（ステップ２）と、
尤度計算手段において、近似尤度からデータベースに格納されているＨＭＭの枝刈りに用いる閾値の初期値を計算する初期値計算ステップと、該閾値の初期値と記憶手段に格納された更新された閾値に基づいて、オリジナルのＨＭＭの尤度を計算するかを判定する尤度計算判定ステップと、判定結果に基づいて、データベースに格納されている該オリジナルのＨＭＭの尤度を計算するＨＭＭ尤度計算ステップと、ＨＭＭを該オリジナルの尤度によって枝刈りする枝刈りステップと、検索を行い、該オリジナルの尤度を尤度記憶手段に記憶すると共に、上位Ｋ番目のＨＭＭの尤度で該記憶手段の閾値を更新する尤度計算ステップからなる処理のうち、該尤度計算判定ステップ以降の処理をＨＭＭ数になるまで繰り返す尤度計算ステップ（ステップ３）と、を行う。
【００１４】
また、本発明（請求項２）は、近似尤度計算ステップ（ステップ２）において、
外部から検索要求として時系列信号と検索個数を受け取り、また、データベースから縮退後のＨＭＭを取得し、縮退後の近似尤度を計算し、近似尤度記憶手段に格納するステップと、
近似尤度記憶手段に格納された近似尤度を並べ替えるステップと、
近似尤度によって検索の解候補を計算するステップと、
を行うことにより近似尤度によって検索の解候補を計算する。
【００１５】
また、本発明（請求項３）は、構造縮退ステップ（ステップ１）において、
外部から縮退後のＨＭＭの状態数とオリジナルのＨＭＭの状態を取得し、また、縮退途中の状態を受け取り、状態統合誤差を計算するステップと、
状態誤差を取得して、該状態統合誤差の最も小さい状態同士を統合するステップと、
外部から縮退後のＨＭＭの出力信号数とオリジナルのＨＭＭの出力信号を受け取り、また、縮退途中の出力信号を受け取り、該オリジナルのＨＭＭの出力信号と該縮退途中の出力信号から出力信号統合誤差を計算するステップと、
出力信号統合誤差の最も小さい出力信号同士を統合するステップと、
を行うことにより統合誤差が小さくなるように状態や出力信号を縮退する。
【００１６】
また、本発明（請求項４）は、オリジナルのＨＭＭの尤度を計算するステップにおいて、
データベースに格納されたＨＭＭのタイプによって尤度を計算する時に用いる遷移集合の初期集合を計算するステップと、
初期の遷移集合と更新後の遷移集合を用いて尤度を計算するステップと、
計算された尤度から遷移集合を更新し、また、計算された尤度を尤度記憶手段に格納するステップと、
を行うことにより検索に影響ない範囲で不要な遷移からの計算を打ち切る。
【００１７】
図２は、本発明の原理構成図である。
【００１８】
本発明（請求項５）は、データベースに格納された隠れマルコフモデル（以下、ＨＭＭと記す）を、尤度によって検索する隠れマルコフモデル検索装置１００であって、
オリジナルのＨＭＭと縮退されたＨＭＭを格納するデータベース３０と、
検索処理の前に、データベース３０のＨＭＭの状態及び出力信号に対して縮退処理を行い、該データベース３０に格納する構造縮退手段４０と、
検索要求を取得すると、データベース３０から構造縮退手段４０により縮退されたＨＭＭを読み出して、該ＨＭＭの近似尤度を計算する近似尤度計算手段１０と、
近似尤度からデータベース３０に格納されたＨＭＭの枝刈りに用いる閾値の初期値を計算する初期値計算手段と、該閾値の初期値と記憶手段から更新された閾値を受け取り、該閾値を用いてオリジナルのＨＭＭの尤度を計算するかの判定を行う計算判定手段と、該計算判定手段の判定結果に基づいて、データベースに格納されている該オリジナルのＨＭＭの尤度を計算するＨＭＭ尤度計算手段と、ＨＭＭを該オリジナルの尤度によって枝刈りする枝刈り手段と、検索を行い、該オリジナルの尤度を尤度記憶手段に記憶すると共に、上位Ｋ番目のＨＭＭの尤度で該尤度記憶手段の閾値を更新する尤度保存手段と、該計算判定手段、該HMM尤度計算手段、該尤度保存手段の処理を、ＨＭＭ数になるまで繰り返す繰り返し手段と、からなる尤度計算処理手段２０と、を有する。
【００１９】
また、本発明（請求項６）は、近似尤度計算手段１０において、
外部から検索要求として時系列信号と検索個数を受け取り、また、データベース３０から縮退後のＨＭＭを取得し、縮退後の近似尤度を計算し、近似尤度記憶手段に格納する近似尤度算出手段と、
近似尤度記憶手段に格納された近似尤度を並べ替える近似尤度ソート手段と、を有する。
【００２０】
また、本発明（請求項７）は、構造縮退手段４０は、状態統合誤差計算手段と、状態統合手段と、出力信号統合誤差計算手段と、出力信号統合手段と、を含み、
状態統合誤差計算手段は、
外部から縮退後のＨＭＭの状態数とオリジナルのＨＭＭの状態を取得し、また、状態統合手段から縮退途中の状態を受け取り、状態統合誤差を計算し、
状態統合手段は、
状態誤差を取得して、該状態統合誤差の最も小さい状態同士を統合し、
出力信号統合誤差計算手段は、
外部から縮退後のＨＭＭの出力信号数とオリジナルのＨＭＭの出力信号を受け取り、また、出力信号統合手段から縮退途中の出力信号を受け取り、該オリジナルのＨＭＭの出力信号と該縮退途中の出力信号から出力信号統合誤差を計算し、
出力信号統合手段は、
出力信号統合誤差の最も小さい出力信号同士を統合する。
【００２１】
また、本発明（請求項８）は、尤度計算手段は、遷移集合計算手段、尤度算出手段と、遷移集合更新手段と、を有し、
遷移集合計算手段は、
データベース３０に格納されたＨＭＭのタイプによって尤度を計算する時に用いる遷移集合の初期集合を計算し、
尤度算出手段は、
遷移集合計算手段で計算された初期の遷移集合と、遷移集合更新手段から取得した更新後の遷移集合を用いて尤度を計算し、
遷移集合更新手段は、
尤度算出手段で計算された尤度から遷移集合を更新し、また、計算された尤度を尤度記憶手段に格納する。
【００２２】
本発明（請求項９）は、データベースに格納された隠れマルコフモデルを、尤度によって検索する隠れマルコフモデル検索プログラムであって、
コンピュータを、請求項５乃至８記載の隠れマルコフモデル検索装置として機能させる隠れマルコフモデル検索プログラムである。
【００２３】
本発明（請求項１０）は、データベースに格納された隠れマルコフモデルを、尤度によって検索する隠れマルコフモデル検索プログラムを格納したコンピュータ読み取り可能な記録媒体であって、
コンピュータを、請求項５乃至８記載の隠れマルコフモデル検索装置として機能させるプログラムを格納したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００２４】
上記のように本発明によれば、近似後の尤度を用いて検索結果候補を絞り込んでいるため、厳密な尤度を用いてさらに枝刈りを行う。検索手法では、格納されたＨＭＭの中から必要最低限のものに対してのみ尤度を計算するので、高速処理が可能となる。
【発明を実施するための最良の形態】
【００２５】
以下、図面と共に本発明の実施の形態を説明する。
【００２６】
図３は、本発明の一実施の形態における隠れマルコフモデル検索装置の構成を示す。
【００２７】
同図に示す隠れマルコフ検索装置は、近似尤度計算部１０、尤度計算処理部２０、データベース３０、構造縮退部４０から構成される。
【００２８】
近似尤度計算部１０は、縮退された後のＨＭＭをデータベース３０から取得して、ＨＭＭの近似精度（近似尤度（近似後の尤度）の誤差と真の尤度との割合）を計算する。
【００２９】
尤度計算処理部２０は、データベース３０に格納されたオリジナルのＨＭＭの尤度を計算する。
【００３０】
データベース３０は、縮退されたＨＭＭとオリジナルのＨＭＭを格納する。
【００３１】
構造縮退部４０は、データベース３０に格納されているＨＭＭを縮退させる。
【００３２】
次に、上記の構成について詳細に説明する。
【００３３】
近似尤度計算部１０は、図４に示すように、近似尤度算出部１１、近似尤度保存部１２、近似尤度ソート部１３から構成される。
【００３４】
近似尤度算出部１１は、外部から時系列信号と検索個数を受け取り、また、データベース３０から縮退後のＨＭＭを取得して、これらを用いて近似後の尤度を計算し、近似尤度保存部１２に格納する。
【００３５】
近似尤度保存部１２は、メモリやハードディスク等の記憶手段であり、近似尤度算出部１１で算出された近似尤度を保存する。
【００３６】
近似尤度ソート部１３は、近似尤度保存部１２に保存された近似尤度を高い順に並べ替える。
【００３７】
構造縮退部４０は、図５に示すように、状態統合誤差計算部４１、状態統合部４２、出力信号統合誤差計算部４３、出力信号統合部４４から構成される。
【００３８】
状態統合誤差計算部４１は、外部から縮退後の状態数とオリジナルの状態を受け取り、また状態統合部４２から縮退途中のＨＭＭの状態を受け取り、状態統合誤差を計算する。
【００３９】
状態統合部４２は、状態統合誤差計算部４１から状態統合誤差を受け取り、状態統合誤差の最も小さい状態同士を統合する。
【００４０】
出力信号統合誤差計算部４３は、外部から縮退後の出力信号数とオリジナルのＨＭＭの出力信号を受け取り、また、出力信号統合部４４から縮退途中の出力信号を受け取り、出力信号統合誤差を計算する。
【００４１】
出力信号統合部４４は、出力信号統合誤差を受け取り、出力信号統合誤差の最も小さい出力信号同士を統合する。
【００４２】
尤度計算処理部２０は、図６に示すように、初期閾値計算部２１、計算判定部２２、尤度計算部２３、尤度保存部２４から構成される。
【００４３】
初期閾値計算部２１は、近似尤度計算部１０で計算された近似尤度からデータベース３０に格納されたＨＭＭの枝刈りに用いる閾値の初期値を計算する。
【００４４】
計算判定部２２は、初期閾値計算部２１から初期の閾値と尤度保存部２４から更新された閾値を受け取り、閾値を用いてオリジナルの隠れマルコフモデルの尤度を計算するかの判定を行う。
【００４５】
尤度計算部２３は、オリジナルのＨＭＭの尤度を計算する。尤度計算部２３は、図７に示すように、遷移集合計算部２３１、尤度算出部２３２、遷移集合更新部２３３からなり、遷移集合計算部２３１は、データベース３０に格納された隠れマルコフモデルのタイプによって尤度を計算する時に用いる遷移集合の初期集合を計算する。
【００４６】
尤度算出部２３２は、遷移集合計算部２３１から初期の遷移集合を、遷移集合更新部２３３から更新後の遷移集合を取得し、遷移集合を用いて尤度を計算する。
【００４７】
遷移集合更新部２３３は、尤度算出部２３２で計算された尤度から遷移集合を更新し、また、更新された尤度を尤度保存部２４に転送する。
【００４８】
尤度保存部２４は、メモリやハードディスク等の記憶装置であり、尤度計算部２３で計算された尤度を保存し、また、閾値を更新する。
【００４９】
ここで、以下の説明で用いられる記号について定義する。
【００５０】
ｏi：時系列信号例Ｏの時刻ｉにおける値（ｉ＝１，…，Ｔ）
Ｋ：検索されるＨＭＭの個数
ａi：状態ｕｉの初期状態確率（ｉ＝１，…，Ｎ）
ｂij：状態uｉから状態ｕjへの遷移確率
ｃij：状態ｕｉにおける信号ｖjの信号出力確率（ｊ＝１，…，Ｑ）
Ｐ（Ｘ，Ｏ）：時系列信号ＯのHMM Ｘに対する尤度
【００５１】
【数１】
0004567617.tif 000002
次に、上記の構成における動作を説明する。
【００５２】
図８は、本発明の一実施の形態における隠れマルコフモデル検索装置の概要動作のフローチャートであり、検索解の初期値設定のための動作を示す。
【００５３】
ステップ１００）  検索を行う前の事前処理として、構造縮退部４０において、ＨＭＭの縮退処理を行う。当該縮退処理については、図１０において詳細に説明する。
【００５４】
ステップ１１０）  検索が要求されると、検索解の初期値設定のための処理として、近似尤度計算部１０は、データベース３０から取得した全てのＨＭＭに対して近似尤度を計算する。
【００５５】
ステップ１２０）  尤度計算処理部２０は、縮退後の尤度が上位Ｋ個のＨＭＭに対してのみオリジナルの尤度を計算する。
【００５６】
上記のステップ１１０とステップ１２０の処理は、検索解の初期値設定のための前処理である。
【００５７】
ステップ１３０）  検索解の初期値設定処理として、尤度計算処理部２０において、オリジナルのＨＭＭの尤度を計算したＨＭＭを暫定的な上位Ｋ個とする。そして、オリジナルの尤度で並べ替え、Ｋ番目の値を枝刈りに用いる閾値に代入する。
【００５８】
ステップ１４０）  検索解の精製処理として、尤度計算処理部２０において、オリジナルの尤度により枝刈りの閾値を更新しながら上位Ｋ個を精製していく。ここで、検索解の精製とは、解候補のオリジナルの尤度を検索途中で大きくしていくことを指す。
【００５９】
図９は、本発明の一実施の形態における検索解の精製処理の動作のフローチャートである。
【００６０】
ステップ２００）  ステップ２１０以降の処理の前に、構造縮退部４０において、ＨＭＭの縮退処理を行っておく。詳細については、図１０に示す。
【００６１】
ステップ２１０）  近似尤度計算部１０の近似尤度算出部１１において、データベース３０から取得したすべてのＨＭＭに対して縮退尤度を計算し、近似尤度保存部１２に格納する。詳細については、図１４に示す。
【００６２】
ステップ２２０）  近似尤度計算部１０の近似尤度ソート部１３において、全てのＨＭＭを縮退尤度の降順で並べ替える。なお、並べ替えの方法は既存の方法を用いるものとする。
【００６３】
ステップ２３０）  尤度計算処理部２０の尤度計算部２３は、上位Ｋ個のＨＭＭに対してのみオリジナルの尤度を計算し、尤度保存部２４に格納する。なお、オリジナルの尤度の計算は既存の方法を用いるものとする。
【００６４】
ステップ２４０）  尤度計算処理部２０は、オリジナルの尤度を計算したＨＭＭを暫定的な上位Ｋ個とするＫ個のＨＭＭをステップ２３０で計算された尤度の降順で並べ替える。なお、並び替えの方法は既存の技術を用いるものとする。
【００６５】
ステップ２４１）  尤度計算処理部２０は、εtempにＫ番目の尤度を代入する。
【００６６】
ステップ２４２）  ｉ＝０とする。
【００６７】
ステップ２４３）  尤度計算処理部２０の計算判定部２２は、ｉ≦Ｍ（ＨＭＭの個数）であるかを判断し、そうであれば、ステップ２４４に移行し、そうでなければステップ２４８に移行する。
【００６８】
ステップ２４４）  尤度計算処理部２０の計算判定部２２は、
【００６９】
【数２】
0004567617.tif 000003
であるかを判定し、そうである場合には、ステップ２４５に移行し、そうでない場合はステップ２４８に移行する。このεtempによる枝刈りを行うことで、オリジナルの尤度を計算しなくてもよくなる。
【００７０】
ステップ２４５）  尤度計算処理部２０の計算判定部２２において、計算の打ち切りを判定しながら、尤度計算部２３においてオリジナルの尤度を計算する。詳細については図１６に示す。
【００７１】
ステップ２４６）  尤度計算処理部２０の計算判定部２２は、Ｐ（Ｘ，Ｏ）≧εtempであるかを判定し、そうである場合にはステップ２４７に移行し、そうでない場合はステップ２４８に移行する。
【００７２】
ステップ２４７）  尤度計算処理部２０の尤度保存部２４において、上位Ｋ番目のＨＭＭの尤度を代入してεtempを更新する。このεtempの更新により枝刈りの効果を向上させることができる。
【００７３】
ステップ２４８）  ｉの値をインクリメントし、ステップ２４３に移行する。
【００７４】
次に、構造縮退部４０の動作について説明する。以下の動作は図８のステップ１００と図９のステップ２００に対応する処理である。
【００７５】
図１０は、本発明の一実施の形態における構造縮退部の処理のフローチャートである。
【００７６】
ステップ１０１）  構造縮退部４０の状態統合誤差計算部４１において、データベース３０から取得した全てのＨＭＭの状態に対して統合誤差を以下の計算式により求める。状態ｕｉとｕｊ（１≦ｉ，ｊ≦ｋ）を統合する時の誤差Ｅ（ｕｉ，ｕｊ）は、
【００７７】
【数３】
0004567617.tif 000004
となる。
【００７８】
ステップ１０２）  状態統合部４２において、統合誤差が最も小さくなる状態の組み合わせを求め、統合する。HMMのN個の状態uは、n個の状態
【００７９】
【数４】
0004567617.tif 000005
へ統合する。uはひとつの状態のみに統合される。統合後の状態の確率は各要素の確率の中で最大値を用いる。即ち、統合後の初期状態確率は、
【００８０】
【数５】
0004567617.tif 000006
となり、状態遷移確率は、
【００８１】
【数６】
0004567617.tif 000007
となる。ここで、状態ujが、状態
【００８２】
【数７】
0004567617.tif 000008
へ統合されていることを、
【００８３】
【数８】
0004567617.tif 000009
と表す。
【００８４】
ステップ１０３）  状態統合部４２は、統合した状態の数がｎ個であるかを判定し、ｎ個である場合には、ステップ１０４に移行し、そうでない場合にはステップ１０１に移行し、状態の数がｎ個になるまでステップ１０１以降の処理を繰り返す。
【００８５】
ステップ１０４）  出力信号統合誤差計算部４３は、全ての出力信号に対して統合誤差を計算する。出力信号ｖｉとｖｊ（１≦ｉ，ｊ≦１）を統合するときの統合誤差は以下の計算式により求められる。
【００８６】
【数９】
0004567617.tif 000010
ステップ１０５）  出力信号統合部４４は、統合誤差が最も小さくなる出力信号の組み合わせを求め、統合する。Ｑ個の出力信号ｖはn個の出力信号
【００８７】
【数１０】
0004567617.tif 000011
へ統合する。ｖはひとつの出力信号へのみに統合される。信号出力確率は
【００８８】
【数１１】
0004567617.tif 000012
となる。出力信号ｖｊが出力信号
【００８９】
【数１２】
0004567617.tif 000013
へ統合されていることを
【００９０】
【数１３】
0004567617.tif 000014
と表すこととする。
【００９１】
ステップ１０６）  出力信号統合部４４は、出力信号の数がｑ個であるかを判定し、ｑ個である場合は、処理を終了し、そうでない場合はステップ１０４に移行し、出力信号の数がｑ個になるまでステップ１０４以降の処理を繰り返す。
【００９２】
上記のステップ１０１からステップ１０３までの処理は、状態に対する統合処理であり、近似精度を上げるために、誤差が小さい状態同士を統合している。近似精度が高いほど、枝刈りの回数が増え、高速化の効果がある。
【００９３】
また、上記のステップ１０４からステップ１０６の処理は、出力信号に対する統合処理であり、近似精度を上げるために誤差が小さい出力信号同士を統合している。近似精度が高いほど枝刈りの回数が増え、高速化の効果がある。
【００９４】
なお、上記のステップ１０１からステップ１０６の処理は、図５におけるステップ２００の処理においても同様であるので、ステップ２００の処理については説明を省略する。
【００９５】
次に、近似尤度計算部１０の処理について説明する。
【００９６】
以下に示す処理は、図８のステップ１１０及び図９のステップ２１０の詳細な処理である。
【００９７】
図１１は、本発明の一実施の形態における近似尤度計算部の処理のフローチャート（その１）であり、Trellis Degenerationを用いたものである。
【００９８】
ステップ３０１）  ｊ＝１、ｋ＝１、縮退後の尤度
【００９９】
【数１４】
0004567617.tif 000015
とする。但し、
【０１００】
【数１５】
0004567617.tif 000016
は縮退後のＨＭＭであり、
【０１０１】
【数１６】
0004567617.tif 000017
は、外部から入力された時系列信号Ｏの信号列である。
【０１０２】
ステップ３０２）  近似尤度計算部１０の近似尤度算出部１１は、ｋ≦ｓであるかを判定し、そうであればステップ３０３に移行し、そうでなければ処理を終了する。
【０１０３】
ステップ３０３）  近似尤度算出部１１は、ｊ≦ｉであるかを判定し、そうであればステップ３０４に移行し、そうでなければステップ３０５に移行する。
【０１０４】
ステップ３０４）  近似尤度算出部１１は、ｋ＝ｊであるかを判定し、そうであればステップ３０５に移行し、そうでなければステップ３０６に移行する。
【０１０５】
ステップ３０５）  近似尤度算出部１１は、ｊ＝１であるかを判定し、そうである場合はステップ３０８に移行し、そうでない場合にはステップ３０７に移行する。
【０１０６】
ステップ３０６）  近似尤度算出部１１は、全ての状態に対して、前の時刻の尤度と遷移確率を掛けたものの最大値と、信号の出力確率の最大値を乗算し、状態の尤度を求め、近似尤度保存部１２に格納し、ステップ３０９に移行する。
【０１０７】
ステップ３０７）  近似尤度算出部１１は、全ての状態に対してその状態への遷移確率の最大値と、信号の出力確率の最大値を乗算し、状態の尤度を求め、近似尤度保存部１２に格納し、ステップ３０９に移行する。
【０１０８】
ステップ３０８）  近似尤度算出部１１は、全ての状態に対して、その状態への遷移確率の最大値と初期確率の大きい方と、信号の出力確率の最大値を乗算し、状態の尤度を求め、近似尤度保存部１２に格納し、ステップ３０９に移行する。
【０１０９】
ステップ３０９）  ｊをインクリメントし、ステップ３０３に移行する。
【０１１０】
ステップ３１０）  近似尤度算出部１１は、近似尤度保存部１２に格納されているそれまでに求められた尤度と、各状態における尤度のｒ乗を乗算し、尤度を計算して近似尤度保存部１２に格納する。ステップ３１１に移行する。
【０１１１】
ステップ３１１）  ｋをインクリメントし、ステップ３０２に移行する。
【０１１２】
上記のステップ３０６〜ステップ３１０の尤度の計算は、以下のようになる。
【０１１３】
ここで、縮退後の尤度の計算には、Viterbiアルゴリズムと同様に動的計画法を用いる。縮退後のＨＭＭ
【０１１４】
【数１７】
0004567617.tif 000018
と、信号列
【０１１５】
【数１８】
0004567617.tif 000019
が与えられたとき、
【０１１６】
【数１９】
0004567617.tif 000020
は、以下のように計算する。
【０１１７】
【数２０】
0004567617.tif 000021
上記のステップ３０１，３０２の処理は、時系列信号の長さＴの代わりに長さｔの時系列信号をｓ回計算している。これにより、トレリス構造の時間軸方向の計算量を減らすことができる。
【０１１８】
また、ステップ３０４，３０５の処理は、縮退したトレリス構造の時間軸方向のはじめである場合と、ｓ個の区切りであるときは尤度の初期値を計算する。
【０１１９】
ステップ３０６〜３０８の処理は、状態数Ｎの代わりに縮退後の状態数ｎで計算している。当該計算によりトレリス構造の状態数方向の計算量を減らすことができる。
【０１２０】
ステップ３１０の処理は、縮退後の尤度
【０１２１】
【数２１】
0004567617.tif 000022
を計算しており、ここで必ず、
【０１２２】
【数２２】
0004567617.tif 000023
となる。
【０１２３】
Viterbアルゴリズムでは、図１２のように状態を縦軸に、時間を横軸に並べた時に構成されるＮ・Ｔの大きさのトレリス構造において、各状態における確率の最大値を動的計画法によって求めている。なお、ＨＭＭにおける状態の遷移はトレリス構造をバックトラックすることによって得られる。また、実際にViterbiアルゴリズムを計算機で計算するときは、アンダーフローを防ぐため各要素を対数化する。ＨＭＭの構造に制約がない場合、即ち、エルゴディックＨＭＭの場合、Viterbiアルゴリズムの計算量はＯ（Ｎ２Ｔ）となる。全ての状態から他の全ての状態へ遷移する確率を各時刻において計算するからである。
【０１２４】
Viterbiアルゴリズムの計算コストはトレリス構造の大きさのために膨大になるという問題がある。そのため、Trellis Degenerationは、図１３に示すとおり、トレリス構造を縮退して高速に尤度を近似計算する。Trellis Degenerationによりトレリス構造は、ｓ・ｒ個のｎ・ｔの大きさのトレリス構造に縮退される。縮退後のトレリス構造の尤度の計算は、Ｏ（ｎ（ｎ＋ｒ）ｔ・ａ）となる。Trellis Degenerationには２つのメリットがある。まず、第１のメリットは、Trellis Degenerationによって検索を行っても検索漏れは発生しないことが保証されることでる。これは、縮退後の近似尤度はオリジナルのトレリス構造による尤度より小さくなることはないためである。第２のメリットとして、検索処理の計算処理を大幅に低減できることが挙げられる。すなわち、検索処理において格納されているＨＭＭに対してまず、Trellis Degenerationにより近似尤度を計算し、解候補のＨＭＭに対してのみオリジナルのトレリス構造により尤度を計算すればよい。
【０１２５】
次に、上記の近似尤度計算部１０の別の処理について説明する。
【０１２６】
図１４は、本発明の一実施の形態における近似尤度計算部の処理のフローチャート（その２）であり、Trellis Degenerationを用いた手法である。
【０１２７】
ステップ４０１）  近似尤度計算部１０において、ｊ＝１、ｋ＝１、
【０１２８】
【数２３】
0004567617.tif 000024
とする。
【０１２９】
ステップ４０２）  ｋ≦ｓであるかを判定し、そうであればステップ４０３に移行し、そうでなければ処理を終了する。
【０１３０】
ステップ４０３）  ｊ≦ｔであるかを判定し、そうである場合にはステップ４０４に移行し、そうでない場合にはステップ４１０に移行する。
【０１３１】
上記のステップ４０２，４０３では、時系列信号の長さＴの代わりに、長さｔの時系列信号をｓ回計算することを示している。
【０１３２】
ステップ４０４）  ｋ＝１であるかを判定し、そうであればステップ４０５に移行し、そうでなければステップ４０６に移行する。
【０１３３】
ステップ４０５）  ｊ＝１であるかを判定し、そうであればステップ４０８に移行し、そうでなければステップ４０７に移行する。
【０１３４】
上記のステップ４０４，４０５により、縮退したトレリス構造の時間軸方向のはじめである場合と、ｓ個の区切りであるときは尤度の初期値を計算する。
【０１３５】
ステップ４０６）  近似尤度算出部１１は、全ての状態
【０１３６】
【数２４】
0004567617.tif 000025
に対して、
【０１３７】
【数２５】
0004567617.tif 000026
として尤度を計算する。
【０１３８】
ステップ４０７）  全ての状態
【０１３９】
【数２６】
0004567617.tif 000027
に対して、
【０１４０】
【数２７】
0004567617.tif 000028
を計算する。
【０１４１】
ステップ４０８）  全ての状態
【０１４２】
【数２８】
0004567617.tif 000029
に対して、
【０１４３】
【数２９】
0004567617.tif 000030
を計算する。
【０１４４】
ステップ４０９）  ｊをインクリメントする。
【０１４５】
上記のステップ４０６からステップ４０８の処理では、状態数Ｎの代わりに、縮退後の状態ｎで計算している。これによりトレリス構造の状態数方向の計算量を減らすことができる。
【０１４６】
ステップ４１０）  縮退後の尤度
【０１４７】
【数３０】
0004567617.tif 000031
として計算する。ここで、必ず、
【０１４８】
【数３１】
0004567617.tif 000032
となる。
【０１４９】
上記の図１４に示す処理は、「Quick Break」を用いた手法である。
【０１５０】
Quick Breakは、図１５に示すように、オリジナルのトレリス構造の尤度計算を高速に打ち切る手法である。Trellis Degenerationによってオリジナルのトレリス構造による尤度計算は必要最低限に抑えられるが、Quick Breakによりさらにオリジナルのトレリス構造による尤度計算を高速処理することができる。Viterbiアルゴリズムの計算量の高さの原因のひとつにトレリス構造の状態遷移による計算の多さがある。しかし、この尤度の計算の途中では検索処理として計算する必要のない状態遷移による計算も含まれる。これは、Viterbiアルゴリズムは動的計画法を用いているため、尤度計算の途中で尤度は単調減少するためである。そのため、Quick Breakでは、検索処理途中で求めた暫定的なＫ個の解候補の尤度により尤度計算を高速に打ち切る。
【０１５１】
次に、尤度計算処理部２０の尤度算出部２３の処理として、図８のステップ１４０及び図９のステップ２４５の処理を詳細に説明する。
【０１５２】
図１６は、本発明の一実施の形態における尤度計算部の処理のフローチャートである。
【０１５３】
ステップ５０１）  ｉ＝１，ｊ＝１とする。
【０１５４】
ステップ５０２）  尤度計算部２３の遷移集合計算部２３１は、ＨＭＭの遷移確率が正である全ての状態を初期遷移集合に加える。具体的にはＨＭＭのタイプ（エルゴディック、left-rightなど）に応じて初期遷移集合を決定する。これによりＨＭＭのタイプによらず高速化が可能である。
【０１５５】
ステップ５０３）  尤度計算部２３の尤度算出部２３２は、ｉ≦Ｔ（Ｔは時系列信号の数）であるかを判定し、ｉ≦Ｔであればステップ５０４に移行し、そうでなければ処理を終了する。
【０１５６】
ステップ５０４）  尤度算出部２３２は、ｊ≦Ｎ（Ｎは状態の数）であるかを判定し、ｊ≦Ｎであればステップ５０５に移行し、そうでなければステップ５０３に移行する。
【０１５７】
ステップ５０５）  尤度算出部２３２は、遷移集合に含まれる状態ｕｋからの遷移のみを用いて、尤度ｐｋｊを計算する。このように全ての状態からの遷移によって計算は行わないことにより、計算を高速化させることができる。
【０１５８】
ステップ５０６）  遷移集合更新部２３３は、尤度ｐｉｊと解候補のオリジナルの尤度εtempを比較する。ｐｉｊ＜εtempであればステップ５０７に移行し、そうでない場合はステップ５０８に移行する。
【０１５９】
ステップ５０７）  遷移集合更新部２３３は、全ての状態の初期遷移集合から状態ｕｋを削除する。これにより、検索の解候補となりえない状態を求める。
【０１６０】
ステップ５０８）  ｊをインクリメントする。
【０１６１】
ステップ５０９）  遷移集合更新部２３３は、全ての状態の遷移集合が空集合であるかを判定し、そうであれば、処理を終了し、そうでなければ、ステップ４１０に移行する。これにより、尤度計算中のＨＭＭは検索の解候補になりえないため計算を打ち切り、計算を高速化させることができる。
【０１６２】
ステップ５１０）  ｉをインクリメントし、ステップ５０３に移行する。
【０１６３】
ここで、上記のステップ５０２におけるＨＭＭのタイプについて説明する。
【０１６４】
図１７は、エルゴディックＨＭＭを、図１８は、left-rightＨＭＭを示す。ＨＭＭは図１７、図１８のように状態遷移確率Ｂ（Ｂ＝｛ｂｉｊ｝、時刻が１つ進んだときに状態ｕｉから状態ｕｊへ遷移する確率）の構造によって分類することができる。図１７、図１８において、白い円は状態を表し、矢印は遷移を表す。全ての状態から他の全ての状態へ遷移できるタイプとして全結合ＨＭＭとエルゴディックＨＭＭがある。エルゴディックＨＭＭは
全結合ＨＭＭを包含し、全ての状態が他のすべての状態へ有限であるが非周期的な回数で遷移できる特徴がある。１回で遷移できるエルゴディックＨＭＭや全結合ＨＭＭにおいて状態遷移確率Ｂは例えば、正の係数ｂｉｊを用いて以下のようになる。
【０１６５】
【数３２】
0004567617.tif 000033
また、図１８に示すleft-right ＨＭＭは、状態を並べたときに左から右へ遷移する特徴があり、状態遷移確率の係数はｊ＜ｉのとき、ｂｉｊ＝０となり、初期状態確率の係数はｉ＝１でａｉ＝１となりｉ≠１でａｉ＝０となる。また、left-rightＨＭＭにおいては状態間を多く遷移しないように制約が課せられていることがあり、状態遷移確率の係数はｊ＞ｉ＋△−１のとき、ｂｉｊ＝０となる。例えば、状態遷移確率Ｂは、△＝２のときｂｉｊを用いて以下のようになる。
【０１６６】
【数３３】
0004567617.tif 000034
上記の図１６に示す処理では、検索途中で得られる暫定的なＫ番目の解候補のオリジナルの尤度をεtempとすると、あるＨＭＭ Xに対して、縮退後の尤度が
【０１６７】
【数３４】
0004567617.tif 000035
であっても、Ｐ（Ｘ，Ｏ）＜εtempであればＨＭＭ Xは解候補になりえない。また、Viterbiアルゴリズムは動的計画法により計算されるので、尤度計算の途中においては尤度は単調減少する。そのためQuick Breakでは尤度を計算するときに、εtempより小さい尤度となる状態からの遷移による計算を打ち切る。計算を途中で打ち切っても明らかに検索漏れは発生しない。
【０１６８】
Quick Breakでは、まずＨＭＭのタイプによって遷移集合の初期設定を行う。疝気集合はトレリス構造のそれぞれの時刻と状態毎に設定され、時刻ｉの状態ｊにおいて、bｊｋ＞０であればｕｋは遷移集合に加えられる。尤度を計算するときは遷移集合に含まれる状態からの遷移のみを用いる。もし、ある状態ｕｊにおける尤度ｐｊがεtempより小さければ、その状態からの遷移は解候補となりえないため、遷移集合から状態ｕｊを削除する。また、全ての状態に対して遷移集合が空集合である場合は、そのＨＭＭは解候補となりえないため、尤度計算を打ち切る。
【０１６９】
検出処理では、高速に解を求めるために近似尤度を用いて尤度の低い殆どのＨＭＭの枝刈りを行い、計算コストの係るオリジナルの尤度計算は必要最低限に限定する。検索処理ではまず近似後の尤度による初期の解候補からの初期のεtempを計算する。これは、ｋ−近傍検索のＫ番目の解の尤度をεとしたときに、εにより近いεtempをできるだけ少ないオリジナルの尤度計算の回数で求めるためである。εtempはＨＭＭを枝刈りするかの判定に用いられ、εに近いほど効果的に枝刈りで切る。εtempは更新され続けられているので、検索処理の途中において枝刈りはさらに効果的になっていく。
【０１７０】
本発明は、尤度を求める際に、Trellis Degenerationにより簡易的に粗い計算によりＨＭＭの検索解の目星を付け、また、粗くない尤度計算を行う場合も、Quick Breakにより解になりそうになければ計算を打ち切るという手法をとっている。この際に、検索漏れが生じないようにすることが重要であり、そのため、粗い計算をしたときの尤度が、本来の尤度より小さくなることがあれば検索漏れが発生しないという知見に基づいている。例えば、あるＨＭＭがある閾値以上の尤度を与えるかを調べる場合、粗い計算をしたときの尤度がその閾値より小さければ、そのＨＭＭの本来の尤度がその閾値以上になることはない。そのため、この知見を用いれば不必要なＨＭＭの尤度計算を枝刈りすることができる。
【０１７１】
また、ＨＭＭの計算途中において尤度は単調減少するという知見に基づいている。この知見を用いて、粗くない尤度計算を行う際も検索漏れが発生しない程度に計算を打ち切る。つまり、尤度の計算途中において、全てＨＭＭ状態で尤度が閾値より小さくなったら計算を打ち切る。これは、ＨＭＭにおいて尤度が閾値以上になることがない、ということに基づくものである。
【０１７２】
［評価実験］
上記の本発明の手法の有効性を示すための実験を行った。
【０１７３】
ナイーブに検索を行う手法と比較実験を行った。実験では、ナイーブに検索を行う手法と比較を行った。また、実験はエルゴディックＨＭＭとleft-rightＨＭＭに対して行った。検索処理にかかる時間において、ＣＰＵの計算時間はディスクアクセスにかかる時間よりもはるかに大きいため、実験では検索におけるＣＰＵの計算時間を比較した。
【０１７４】
実験では、ＨＭＭに動画像コンテンツの特徴量をBaum-Welchアルゴリズムにより求めた。動画コンテンツはドラマ、風景画、ＣＧ映画など様々なものを２４個用意し、１０００個のシーンを切り出した。動画像は１秒あたり３０フレームで構成され、特徴量を各フレーム毎に計算した。特徴量にはフレームの輝度ヒストグラムの特定成分を抽出したものを用いた。
【０１７５】
実験におけるパラメータは問い合わせの個数Ｋ＝３，時系列信号の種類の数Ｑ＝１００とし、ＨＭＭの状態数Ｎと時系列信号の長さＴは実験によって変化させ、縮退後の状態数
【０１７６】
【数３５】
0004567617.tif 000036
時系列信号の長さ
【０１７７】
【数３６】
0004567617.tif 000037
とし、ｔ＝２、時系列信号の種類の数
【０１７８】
【数３７】
0004567617.tif 000038
とした。
【０１７９】
また、left-rightＨＭＭにおける遷移の制約は状態数Ｎによって変化させ、△＝０．２−Ｎとした。
【０１８０】
実験は、ＣＰＵがPentium(登録商標）4の３．２GHz、メインメモリが１GBのマシンで行った。
【０１８１】
（１）検索処理時間：
検索処理時間について状態数を変化させた場合と、時系列信号の長さを変化させた場合について実験を行った。
【０１８２】
・状態数を変化させた場合：
状態数を変化させて実験を行った。なお、実験において信号の長さはＴ＝１００とした。実験結果を図１９、図２０に示す。図１９はエルゴディックＨＭＭにおける状態数と検索時間の関係を示し、図２０はleft-rightＨＭＭにおける状態数と検索時間の関係を示す。結果を見ると、本発明の手法は、ナイーブな手法と比較してエルゴディックＨＭＭに対して約３３〜７３倍、left-rightＨＭＭに対して本実験の条件下で約１６〜２９倍高速な検索が行えている。エルゴディックＨＭＭにおいて、Viterbiアルゴリズムの計算量はＯ（Ｎ２Ｔ）なので、ナイーブな手法は状態数Ｎに対して計算量はＯ（Ｎ２）で増加する。しかし、本発明の手法における計算量はTrellis DegenerationとQuick Breakによって大幅に抑えられている。即ち、縮退後の尤度の計算量はＯ（ｎ（ｎ＋ｒ）ｔ・ｓ）であり、
【０１８３】
【数３８】
0004567617.tif 000039
であるので、状態数に対して計算量の増加はＯ（（ｌｏｇＮ）２）に抑えられる。オリジナルの尤度計算を行う場合でも計算量はQuick Breakによって抑えられる。また、left-rightＨＭＭにおいても、Trellis DegenerationとQuick BreakはＨＭＭタイプに依存する手法ではないので、同様に高速化が達成されている。なお、後の実験に示すとおり、left-right ＨＭＭにおいては、エルゴディックＨＭＭよりQuick Breakによる高速化の影響が大きい。
【０１８４】
・時系列信号の長さを変化させた場合：
時系列信号の長さを変化させて実験を行った。なお、実験において状態数はＮ＝５０とした。その実験結果を図２１、図２２に示す。図２１はエルディックＨＭＭにおける信号の長さと検索時間の関係を示し、図２２はleft-right ＨＭＭにおける信号の長さと検索時間の関係を示す。
【０１８５】
結果を見ると本発明の手法は、ナイーブな手法と比較してエルゴディックＨＭＭに対して約３３〜４９倍、left-right ＨＭＭに対して本実験の条件下で約２８〜４３倍高速な検索が行えている。状態数を変化させた場合と同様に、エルゴディックＨＭＭにおいてナイーブな手法は信号の長さに対して計算量がＯ（Ｔ）で増加する。しかし、本発明の手法において縮退後の計算量の増加はＯ（（logＴ））に抑えられ、オリジナルの計算量もQuick Breakによって抑えられる。また、本発明の手法は、ＨＭＭのタイプに依存しないので、left-rightＨＭＭにおいても同様に高速化が達成されている。
【０１８６】
（２）Trellis Degenerationによるオリジナルの尤度計算の削減量：
本発明の手法では、まず、Trellis Degenerationで縮退した後の尤度を計算してから、解候補となるＨＭＭにのみに対してオリジナルの尤度を計算する。そのため、縮退後の尤度で絞り込まれる解候補個数が検索の高速化に影響する。そこで、この実験ではデータベースに格納された１０００個のＨＭＭに対してオリジナルの尤度を計算したものの個数を調べた。実験では時系列信号の長さを変化させ、状態数はＮ＝５０とした。実験結果を図２３に示す。なお、状態数を変化させた場合も同様の結果になったことを確認している。
【０１８７】
結果を見ると、エルゴディックＨＭＭに対しては殆どオリジナルの尤度を計算することなく検索が行えていることがわかる。これはエルゴディックＨＭＭに対しては、Trellis Degenerationによる近似尤度の精度が高いからである。しかし、left-rightＨＭＭの結果を見るとそれほどオリジナルの尤度計算を省けていないことがわかる。これは、left-rightＨＭＭに対しては、Trellis Degenerationによる近似尤度の精度が低いからである。式（７）に示すように、left-rightＨＭＭにおいて状態遷移確率が状態毎に大きく異なるため、式（１）に示すようなTrellis Degenerationで状態を統合するときの誤差が大きくなるためである。しかし、図１９〜図２２にあるとおり、本発明の手法は、left-rightＨＭＭに対しても高速化を達成している。これは、次の実験に示すとおりleft-rightＨＭＭにおいては、Quick Breakによって大幅に計算量の削減ができているためである。
【０１８８】
（３）Quick Breakによるオリジナルの尤度計算の削減量：
本発明の手法では、解候補となるHMMにのみに対してオリジナルの尤度を計算するが、その計算もQuick Breakにより打ち止めされる。オリジナルの尤度を計算するときのトレリス構造の横軸方向において、早期のポイントで計算が打ち止められるほど高速に検索ができる。そこで、この実験では、計算が打ち止められたＨＭＭに対して、計算が打ち切られた横軸方向のポイントの頻度の割合を調べた。なお、オリジナルの尤度を計算することとなったＨＭＭのうち、エルゴディックＨＭＭでは、１２７個の中で１２２個において、left-rightＨＭＭでは５０９個の中で４９４個においてそれぞれ計算の打ち止めが行われた。実験では状態数はＮ＝５０、時系列信号の長さＴ＝１００とした。
【０１８９】
図２４のエルゴディックＨＭＭの結果を見ると、トレリス構造の横軸方向のポイントが増加するほど計算が打ち切られる割合が多くなることがわかる。これは、Viterbiアルゴリズムは動的計画法により計算されるので、尤度計算の途中では尤度は単調減少するため、横軸方向のポイントが増加するほど尤度がεtempより小さくなる状態が増加するためである。
【０１９０】
また、図２５のleft-rightＨＭＭの結果を見ると、トレリス構造の横軸方向のはじめのポイントで殆ど計算が打ち切られていることがわかる。これは、left-rightＨＭＭにおいては初期状態確率の係数は、ｉ＝１でａｉ＝１となり、ｉ≠１でａｉ＝０となるため、トレリス構造の横軸方向の始めのポイントで状態ｖｉの尤度がεtempより小さくなると、計算は打ち止めされるからである。
【０１９１】
また、本発明は、上記の隠れマルコフモデル検索装置の各構成要素の機能をプログラムとして構築し、当該検索装置として利用されるコンピュータにインストールして実行させることが可能である。
【０１９２】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１９３】
本発明は、動画像コンテンツのシーンを高速に識別する技術、音楽コンテンツのフレーズを高速に切り分ける技術、様々な話者が発声した単語を高速に認識する技術に適用可能である。
【図面の簡単な説明】
【０１９４】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における隠れマルコフモデル検索装置の構成図である。
【図４】本発明の一実施の形態における近似尤度計算部の構成図である。
【図５】本発明の一実施の形態における構造縮退部の構成図である。
【図６】本発明の一実施の形態における尤度計算部の構成図である。
【図７】本発明の一実施の形態における尤度計算部の構成図である。
【図８】本発明の一実施の形態における隠れマルコフモデル検索装置の概要動作のフローチャートである。
【図９】本発明の一実施の形態における隠れマルコフモデル検索装置の精製処理のフローチャートである。
【図１０】本発明の一実施の形態における構造縮退部の処理のフローチャートである。
【図１１】本発明の一実施の形態における近似尤度計算部の処理のフローチャート（その１）である。
【図１２】本発明の一実施の形態におけるトレリス構造を説明するための図である。
【図１３】本発明の一実施の形態における縮退されたトレリス構造を説明するための図である。
【図１４】本発明の一実施の形態における近似尤度計算部の処理のフローチャート（その２）である。
【図１５】本発明の一実施の形態における尤度計算打ち切りを説明するための図である。
【図１６】本発明の一実施の形態における尤度計算部の処理のフローチャートである。
【図１７】本発明の一実施の形態におけるエルゴディックＨＭＭを説明するための図である。
【図１８】本発明の一実施の形態におけるleft-rightＨＭＭを説明するための図である。
【図１９】エルゴディックＨＭＭにおける状態数と検索時間の関係を示す図である。
【図２０】left-rightＨＭＭにおける状態数と検索時間の関係を示す図である。
【図２１】エルゴディックＨＭＭにおける信号の長さと検索時間の関係を示す図である。
【図２２】left-rightＨＭＭにおける信号の長さと検索時間の関係を示す図である。
【図２３】Trellis Degenerationによるオリジナルの尤度計算の削減量（ＨＭＭは１０００個）を示す図である。
【図２４】エルゴディックHMMにおけるQuick Breakによる計算削減量を示す図である。
【図２５】left-rightＨＭＭにおけるQuick Breakによる計算削減量を示す図である。
【符号の説明】
【０１９５】
１０  近似尤度計算手段、近似尤度計算部
１１  近似尤度算出部
１２  近似尤度保存部
１３  近似尤度ソート部
２０  尤度計算処理手段、尤度計算処理部
２１  初期閾値計算部
２２  計算判定部
２３  尤度計算部
２４  尤度保存部
３０  データベース
４０  構造縮退手段、構造縮退部
４１  状態統合誤差計算部
４２  状態統合部
４３  出力信号誤差計算部
４４  出力信号統合部
１００  隠れマルコフモデル検索装置
２３１  遷移集合計算部
２３２  尤度算出部
２３３  遷移集合更新部
【図１】
0004567617.tif 000040
【図２】
0004567617.tif 000041
【図３】
0004567617.tif 000042
【図４】
0004567617.tif 000043
【図５】
0004567617.tif 000044
【図６】
0004567617.tif 000045
【図７】
0004567617.tif 000046
【図８】
0004567617.tif 000047
【図９】
0004567617.tif 000048
【図１０】
0004567617.tif 000049
【図１１】
0004567617.tif 000050
【図１２】
0004567617.tif 000051
【図１３】
0004567617.tif 000052
【図１４】
0004567617.tif 000053
【図１５】
0004567617.tif 000054
【図１６】
0004567617.tif 000055
【図１７】
0004567617.tif 000056
【図１８】
0004567617.tif 000057
【図１９】
0004567617.tif 000058
【図２０】
0004567617.tif 000059
【図２１】
0004567617.tif 000060
【図２２】
0004567617.tif 000061
【図２３】
0004567617.tif 000062
【図２４】
0004567617.tif 000063
【図２５】
0004567617.tif 000064