JP3948747B2

JP3948747B2 - ツリー構成確率密度に基づくパターン認識の方法及びシステム

Info

Publication number: JP3948747B2
Application number: JP51005797A
Authority: JP
Inventors: フランクザイデ
Original assignee: Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 1995-08-28
Filing date: 1996-08-26
Publication date: 2007-07-25
Anticipated expiration: 2016-08-26
Also published as: WO1997008686A3; DE69613338T2; EP0788649A2; WO1997008686A2; DE69613338D1; US5857169A; EP0788649B1; JPH10508392A

Description

本発明は、連続的な物理量から得られる入力パターンを認識するための方法に関し、物理量にアクセスし、この物理量から入力パターンを表す一連の入力観測ベクトルを生成し、
複数の基準パターン中に入力パターンと対応する認識された基準パターンを配置し、少なくとも１個の基準パターンを一連の基準ユニットとし、各基準ユニットを基準確率密度の組中の少なくとも１個の関連する基準確率密度で表し、
基準確率密度の選択をツリー構造として表し、このツリー構造において各リーフノードが基準確率密度に対応すると共に非リーフノードがクラスタ確率密度に対応し、クラスタ確率密度は前記非リーフノードのブランチのリーフノードに対応する基準確率密度から得られ、
前記配置を各入力観測ベクトル

について行い、
前記ツリー構造について、対応するクラスタ確率密度が前記入力観測ベクトル

について最適のクラスタ尤度を与える非リーフノードを介して検索することにより複数のリーフノードを選択し、
選択されたリーフノードに対応する各基準確率密度について前記入力観測ベクトル

の観測尤度を計算して連続する物理量から取り出した入力パターンを認識する方法に関するものである。
また、本発明は、連続する物理量から取り出した時間順次する入力パターンを認識するシステムであって、
回帰的に物理量をアクセスし、入力パターンを表す入力観測ベクトル列を発生させる入力手段と、
基準確率密度の組を少なくともＬ＝３の階層レベルを有するツリー構造として表すツリービィルダであって、前記ツリー構造においてツリーのレベル１の各リーフノードが基準確率密度に対応し、各非リーフノードがクラスタ確率密度に対応し、このクラスタ確率密度が非リーフノードよりも下位のブランチのリーフノードに対応する全ての基準確率密度から取り出されるツリービィルダと、
複数の基準パターンを記憶する基準パターンデータベースであって、少なくとも１個の基準パターンが基準ユニット列とされ、各基準ユニットが基準確率密度の組の少なくとも１個の関連する基準確率密度により表され、前記基準確率密度の選択がツリー構造として記憶される基準パターンデータベースと、
前記認識された入力パターンに対応する認識された基準パターンを前記基準パターンデータベースに記憶されている基準パターン中に配置するローカライザと、
認識されたパターンを出力する出力手段とを具え、
前記ローカライザが、各入力観測ベクトル

について、
ルートノードよりも下位のレベルにおいて、前記観測ベクトル

について対応するクラスタ確率密度が最適のクラスタ尤度を与える多数のノードを選択すると共に、ツリーの順次下位のレベルにおいて各選択されたノードをルートノードとして用いることにより選択されたノードがリーフノードとなるまでノード選択を繰り返すことにより、前記基準パターンデータベースに記憶されているツリー構造を検索し、
選択されたリーフノードに対応する各基準確率密度について、前記入力観測ベクトル

の観測尤度を計算し、
前記基準パターンの基準ユニットを表す全ての基準確率密度について計算された観測尤度を組み合わせることにより、各基準パターンについてパターン類似スコアを計算し、
前記認識されたパターンを、パターン類似スコアの最適度が計算された基準パターンとして配置する入力パターン認識システムに関するものである。
音声や画像のような連続する物理量から取り出された時間順次する入力パターンの認識の重要性が増大している。特に、音声認識は電話音声認識遠隔通信（種々の自動化されたサービィス）、オフィス及びビジネスシステム（データエントリ）、製造（製造工程における手を使わない監視）、医療（リポートの注釈の添付）、ゲーム（音声入力）、自動車機能の音声制御及び障害者により用いられる音声制御のような分野において近年広く用いられている。連続する音声認識の場合、Ｌ．Ｒａｂｉｎｅｒ著、「アチュトリアルオンハイデンマルコフモデルスアンドセレクテッドアプリケーションズインスピーチリコグニション」，プリシーディングスオブＩＥＥＥ，第７７巻，Ｎｏ２１９８９年２月の第１図に示すように、以下の信号処理工程が通常用いられている。
特徴分析：音声入力信号をスペクトル及び／又は時間分析して特徴の代表ベクトル

を計算する。典型的な場合、音声信号はデジタル化（例えば、６．６７ｋＨｚのレートでサンプルされる）され、例えば高域強調を適用することにより予備処理される。順次のサンプルは、例えば３２ｍ秒の音声信号に対応するフレームにグループ化（ブロック化）される。順次のフレームは例えば１６ｍ秒で部分的にオーバラップしている。しばしば、リニアプレディクティブコーディング（ＬＰＣ）スペクトラル分析方法が用いられて各フレームについて特徴の代表ベクトル

が計算されている。この特徴ベクトルは例えば２４、３２又は６３個の成分（特徴空間ディメンション）を有することができる。
ユニット整合システム：観測ベクトルは音声認識ユニットの目録に整合される。種々の形態の音声認識ユニットを用いることができる。あるシステムは、単音、二重音声又は音節、及びフェネン（ｆｅｎｅｎｅ）及びフェノン（ｆｅｎｏｎｅ）のような派生的なユニットのような言語学的に基準化されたサブワードユニットを用いている。別のシステムは、ワード全体又はワードのグループをユニットとして用いている。音声信号を確率的にモデル化するため所謂隠れマルコフモデル（ＨＭＭ）が広く用いられている。このモデルを用いると、各ユニットは、パラメータが音声データのトレーニングセットから推定されるＨＭＭにより通常は特徴化される。例えば１００００から６００００ワードを含む大きな語彙音声認識システムの場合、より多くのユニットについてＨＭＭを適切にトレーニングするために多数のトレーニングデータが必要であるので、制限された組の例えば４０個のサブワードユニットが通常用いられている。ユニット整合システムは観測ベクトルを音声認識ユニットの全てのシーケンスに整合させ、ベクトルとシーケンスとの間の整合に関する尤度を与える。例えば以下のようにして整合に制約を課すことができる。
・語彙的なデコーディング：サブワードユニットを用いる場合、発音語彙は、サブワードユニットのワードがどのように構成されるかを表示する。ユニット整合システムにより検討したサブワードユニットの取りうるシーケンスが語彙のシーケンスに対して制約される。
・構文法分析：ユニット整合システムに制約を課し、検討した経路が、ワードを構成し（語彙的デコーディング）ワードがワード文法により特定される適切な順序にある音声ユニットに対応する経路となるようにする。
離散的なマルコフプロセスは、いかなる時においてもＮ個の識別される状態にある組の１つにおけるシステムについて説明している。このシステムは、規則的な時間で状態と関連する確率の組により状態を変更している。離散的なマルコフプロセスの特別な形態が上記文献の第２図に示されている。この所謂左右モデルにおいて、状態は左から右に続いている（又は同一にとどまる）。この方法は、信号の特性が時間に対して変化する音声をモデル化するため広く用いられている。モデル状態は音を表すものとして観測することができる。サブワードユニットとしてのモデルの状態の数は、例えば５又は６個とすることができる。この場合、平均的には状態は観測期間に対応する。上記第２図のモデルの場合状態は同一にとどまることができ、これはゆっくり話すことと関連する。或いは、状態をスキップすることができ、これは速く話すことと関連する（第２図において、平均レートの２倍まで）。離散的なマルコフプロセスの出力は各時間瞬時の状態の組であり、各状態は観測可能な事象に対応している。音声認識システムの場合、離散的なマルコフプロセスの概念は、観測が状態の確率関数となる場合まで拡張される。これにより二重確率過程が生ずる。状態変化の確率過程は隠れており（隠れマルコフモデル、ＨＭＭ）、観測順序を発生する確率過程を介してのみ観測される。
音声の場合、観測は連続する信号を表す。この観測は、例えば３２から２５６個のベクトルから成る有限のアルファベットから選択される離散的な記号に量子化することができる。この場合、モデルの各状態について離散確率密度を用いることができる。量子化と関連する劣化を回避するため、多くの音声認識システムは連続混合密度を用いている。一般的に、この密度はガアウシアン密度（正規分布）又はラプラシアン密度のような対数へこみ密度又は楕円対称密度から取り出される。トレーニング中、トレーニングデータ（トレーニング観測シーケンス）は初期モデルを用いて複数の状態にセグメント化される。これにより、各状態に対してトレーニング観測ベクトル又は基準ベクトルと称される一組の観測が与えられる。次に、各状態についての基準ベクトルがクラスタ化される。システムの複雑さ及びトレーニングデータの量に応じて、各状態について例えば３２から１２０個の要素クラスタが発生する。各要素クラスタは基準確率密度と称するそれ自身の確率密度を有する。結果として生じる状態についての混合密度は、状態についての基準確率密度の重み付けされた和となる。
音声信号（観測シーケンス）から単一の音声認識ユニット（例えば、ワード又はサブワードユニット）を認識するため、観測シーケンスを発生した各音声認識ユニットについて尤度を計算する。最大尤度を有する音声認識を選択する。より多くの観測シーケンスを認識するため、レベル分けされた手法が用いられる。第１のレベルからスタートして前述した尤度を計算する。モデルの最後の状態に到達した時はいつでも、より高いレベルに切り換え、残りの観測について同一の処理を繰り返す。最後の観測が処理されると、最大尤度を有する経路が選択されこの経路を戻って、含まれている音声認識ユニットのシーケンスが決定される。
尤度計算は、各状態においてその状態の各基準確率密度についての観測（特徴ベクトル）の尤度を計算することを含んでいる。特に、例えば４０個のサブワードユニット、サブワード当たり５個の状態並びに状態当たり６４個のクラスタを有する連続する観測密度ＨＭＭを用いる多くの語彙音声認識システムにおいて、上記計算は例えば３２個の次元ベクトルについて１２８００個の尤度計算を含んでいる。これらの計算は各観測ベクトルについて繰り返される。従って、この尤度計算は、計算資源全体の５０〜７５％を占めてしまう。
ツリー構造を用いツリー検索を利用して基準確率密度を構築することにより尤度計算に必要な時間の割合を低減することは、欧州特許出願公開第６２７７２６号から既知である。ツリーの最下位レベル（レベル１）においてリーフノードの各々が実際の基準確率密度に対応する。前述したように、基準確率密度は基準ベクトルの要素クラスタを表す。ツリーのレベル２において、各非リーフノードはクラスタ確率密度に対応し、このクラスタ確率密度は非リーフノードよりも下位のブランチのリーフノードに対応する全ての基準確率密度から取り出される。斯かるレベル２において非リーフノードは基準ベクトルのクラスタを表す。この階層的なクラスタ化は、ツリーの最上位において１個の非リーフノード（ルートノード）が全ての基準ベクトルを表すまで、順次高くなるレベルについて繰り返す。パターン認識中に、各入力観測ベクトルについてツリー検索をルートノードの１レベル下位のレベルから開始する。このレベルで各ノードに対して、対応するクラスタ確率密度を用いて観測ベクトルの尤度を計算する。最大の尤度を有する１個又はそれ以上のノードを選択する。これらのノードについて同一の処理を１レベル下位までで繰り返す。このようにして、最終的に対応する基準確率密度を用いて観測ベクトルの尤度が計算された多数のノードが選択される。選択されなかった各リーフノードについて、その尤度が最後に選択した親ノードの尤度により近似される。
本発明の目的は、冒頭部で述べた形式の方法及びシステムを改善することにある。
この目的を達成するため、本発明の方法は、各基準ユニットと関連する基準確率密度を個別のツリー構造として表し、
前記配置が、各個別のツリー構造について前記検索を行うことにより各個別のツリー構造のリーフノードを選択することを含むことを特徴とする。
全ての基準ベクトルを１個のツリーに組み込む代わりに、各基準ユニット毎に複数の個別のツリーを構築する。その結果、Ｎ１個の基準パターン（例えば、ＨＭＭ）が存在し各々がＮ２個の基準ユニット（状態）を有する場合、Ｎ１×Ｎ２個のツリーが構築され各観測ベクトルについて検索が行われる。既知のシステムにおいて基準確率密度の比較的少ない部分集合が選択された場合、要素クラスタの対応する組は「近い」観測ベクトルである基準ベクトル（音声）により支配される。本発明者は、こうして選択されるのに十分近くないが尤度計算にある重要な貢献が無い程遠く離れてはいない程度関連する基準ベクトルの多数のグループが存在することを確立した。これは、１個の観測ベクトルについてこのグループの基準ベクトルが極めて良好に整合していないが、この基準ベクトルが表す基準パターンが観測ベクトルの全体のシーケンスについて極めて良好に整合することを意味する。従って、このグループの基準ベクトル間で識別できることが重要である。既知のシステムにおいては、このグループの全ての基準ベクトルについてその尤度は、それらが一員であり、かつ、尤度が計算された最下位のブランチの尤度により近似されている。これは、同一の選択されなかったブランチの基準ベクトルにより表される同様な音声を識別することができず、認識の低下が生じてしまう。本発明者は、より正確な認識を行うためには別の識別方法が必要であるとの結論に達した。これは、複数のツリーを用いることにより達成される。パターン全体を認識する場合、各観測ベクトルについてＨＭＭ状態に整合させる観測の尤度を計算する必要がある（及び全体の尤度は累積される必要がある）。これは、各状態について少なくとも１個の基準確率密度が含まれる必要がある（好ましくは、この基準確率密度がその状態についての最高の尤度を与える）ことを意味する。既知のシステムにおいてこれを達成するためには、選択された集合を比較的大きくする必要がある。本発明では、各状態毎に個別のツリーを用い、各状態に少なくとも１個の代表的な基準確率密度を含ませることを確実にする。この結果、高精度の認識を行うために必要な選択されたリーフの組が相当減少する。これにより、最大尤度計算に必要な処理時間が短くなる。
本発明の別の形態として、本発明の方法は、非リーフノードを介してツリー構造を検索することが、ツリー構造の少なくとも１個のレベルにおいて、前記クラスタ尤度の最適値が計算される非リーフノードを介する経路を検索することを含み、前記クラスタ尤度が前記最適のクラスタ尤度の予め定めた範囲内にある非リーフノードを介する経路により補完されることを特徴とする。ツリーにおける各レベルにおいてサブセットが１つだけか又は複数かを決定するために、範囲（閾値）が使用される。ツリーの各レベルにおいて、最高の尤度を有する部分集合（観測ベクトルに最も近い）を決定する。別の部分集合が最高の尤度と同様な尤度を有している場合（すなわち、最高の尤度と他の部分集合の尤度との間の差異が閾値以下の場合）、この別の部分集合についてさらに計算する。このようにして、ツリーのレベル１で最終的に選択された基準確率密度の数がダイナミックに決定される。これは、ある観測ベクトルについて少ない数の基準確率密度が比較的高い尤度を与える場合部分集合が小さくなることが起きやすい利点がある。その場合、観測ベクトルに整合する少ない数の良好な候補だけが存在する場合、一般に認識が高速になる。一方、ある観測ベクトルについて多数の基準確率密度が同様な比較的高い尤度を与える場合、部分集合が大きくなりやすい。そのため、観測ベクトルと整合する多数の良好な候補が存在する場合、一般に認識は一層識別性が高くなり、精度が高くなる。
本発明の別の形態として、本発明の方法は、ツリー構造を、各非リーフノードが４個のノードの最大よりも階層的に１レベル上位にされ、少なくとも１個の非リーフノードが階層的に４個のノードよりも１レベル上位にされている四進ツリーとしたことを特徴とする。原理的に、ツリーの各非リーフノードに多数のブランチを有するツリー構造を用いる場合、認識精度は改善される。この場合、クラスタへの分割は一層正確になり選択されるべき正しいクラスタへの的中が一層高くなる。一方、計算量は、ブランチの量が増大すると増大し、認識の性能が低下する。本発明者は、典型的な大きな語彙音声認識システムについて４進ツリーが精度と性能との間で良好なバランスを発揮することを確立した。
本発明の別の形態として、本発明の方法は、非リーフノードを介するツリー構造の検索が、ツリー構造の同一のブランチ内の同一のレベルの一群の非リーフノードに対して、
選択した非リーフノードの対について、２個の対応するクラスタ確率密度と前記入力観測ベクトル

との間のクラスタ比較スコアを計算し、前記クラスタ比較スコアが２個の対応するクラスタ確率密度のいずれかが入力観測ベクトル

の最高の尤度を与えるかを指示し、
以前に算出されたクラスタ比較スコアが最高の尤度を示す非リーフノードに対するクラスタ比較スコアと、未だクラスタ比較スコアが算出されていないグループの他の非リーフノードに対するクラスタ比較スコアとを、前記グループのすべての非リーフノードについてクラスタ比較スコアが計算されるまで繰り返し算出し、
前記クラスタ比較スコアが最高の尤度を指示する非リーフノードを介する経路を前記検索に含ませることを特徴とする。
各非リーフノードに対して算出されるクラスタ尤度は、ツリーの最低レベルにおいて多数のリーフノードを選択するためにのみ使用される。これらのリーフに対して、パターン認識のために対応する基準確率密度が使用される。これは、クラスタ尤度を完全に計算する代わりに、クラスタの組の間での尤度の差を計算することを可能にする。特定の密度においては、完全な尤度計算より比較計算の方が簡単であるので、これは、どのクラスタが最も起こりやすいかを迅速に決定することを可能にする。
本発明の別の形態として、本発明の方法は、既知の入力パターンを表す一連のトレーニング観測ベクトルから前記確率密度が取り出され、前記基準確率密度の組をツリー構造として表す工程が、前記トレーニング観測ベクトルをクラスタの階層的な組にクラスタ化すること、及び各クラスタについてクラスタ確率密度を計算することを含む方法において、
前記基準確率密度の組をツリー構造として表す前記工程が、
前記一連のトレーニング観測ベクトルを、対応する基準パターン及び対応する基準ユニット列にセグメント化し、
反復的に：
各基準ユニットについて、対応するトレーニング観測ベクトルをクラスタの階層的な組にクラスタ化して、各々が個別の基準ユニットに対応する独立したツリー構造を形成し、
各トレーニング観測ベクトルについて、予め定めた最適基準に基づいて最も類似する対応する基準ユニットを決定する事と、最適なクラスタ尤度を有するクラスタについて対応する基準ユニットのツリー構造を検索して前記クラスタの１つに各トレーニング観測ベクトルを割り当てる事とにより、前記基準ユニット列に基づいて前記トレーニング観測ベクトル列を時間整合させることを有することを特徴とする。
トレーニング期間中にクラスタ化を行い、結果として密度パラメータを推定すると共にトレーニング観測ベクトルを基準ユニットに割り当てることが起きる。これらの操作は反復するように行う。本発明では、このようにして各基準ユニットについて個別のツリー構造を構築する。本発明者は、ツリー構築作業を反復的な処理に一体化することによりパターン認識の精度を改善することを確立した。さらに、トレーニング観測ベクトルは反復中に基準ユニットに再割当てされ、従って適切なクラスタに再割当てされる必要があるので、部分的に構築されたツリーを利用して最も適切なクラスタを決定することによりシステムのトレーニングに必要な時間が大幅に減少することが判明した。
本発明の目的を達成するため、本発明のシステムは、ツリービィルダが、各基準ユニットについて関連する基準確率密度を個別のツリー構造として表すものとして想定され、
前記基準パターンデータベースが、各基準ユニットについて前記個別のツリー構造をさらに記憶し、
前記配置が、各個別のツリー構造についての検索を行うことにより各個別のツリー構造のリーフノードを選択することを含むことを特徴とする。
以下図面を参照して本発明を詳細に説明する。
以下添付図面に基づき本発明を説明する。
図１は連続する音声認識に通常用いられる処理工程を示す。
図２は左右離散的なマルコフ処理の一例を示す。
図３は本発明によるシステムの一実施例のブロック線図である。
図４はツリー構成された確率密度を示す。
図５は４個のリーフを有する二進ツリーの２次元セル境界を示す。
図６は反復トレーニング処理のフロー線図を示す。
図３は、音声又は画像のような連続する物理量から取り出した時間順次する入力パターン２０を認識する本発明によるシステム１０のブロック線図を示す。入力手段３０は物理量を繰り返しアクセスする。音声の場合、これは、通常６．６７ｋＨｚ又は１６ｋＨｚのような規則的な間隔で物理量をサンプリングすること及びサンプルをデジタル化することを含む。この入力手段３０は例えば音声信号の３２ｍ秒に対応する連続的なサンプル群を処理して特徴の代表ベクトル

を発生する。このようにして、入力パターンを表す入力観測ベクトルの時間シーケンスが発生する。典型的には、入力手段３０はマイクロホン、Ａ／Ｄ変換器及びディジタルシグナルプロセッサ（ＤＳＰ）のようなプロセッサを用いて構成することができる。選択的に、入力手段３０は、音声が有効に受信された時だけサンプリングを行う音声検出器で構成することができる。入力信号をサンプリングしデジタル化する変形例として、音声信号をデジタル化された形態でメモリに記憶し又は通信ネットワークを介してデジタルで供給することができる。基準パターンデータベース４０を用いて基準パターンを記憶する。この基準パターンデータベース４０はハードディスク、ＲＯＭ又はＲＡＭのようなメモリに、一体化されたデータベースとして又は個別のデータファイルとして記憶することができる。前述したように、音声認識ユニットは音声を認識する基準パターンとして用いる。各基準パターンは一連の基準ユニットを含むことができる。各基準ユニットは少なくとも１個の関連付けられた基準確率密度により表される。隠れマルコフモデルに基づくパターン認識を用いれば、各基準パターンは隠れマルコフモデルによりモデル化され、このモデルの状態は基準ユニットに対応する。連続観測密度を用いることにより、基準確率密度は通常ガウシアン密度又はラプラシアン密度となる。勿論、ある状態の隠れマルコフモデルを用いて言葉の前又は言葉の間に生ずる無音のパターンのような鮮明な時間順次挙動を有しない特別なパターンをモデル化することは既知であることに留意されたい。本発明の目的のためには、このようなパターンを別個に表すものではない。このようなパターンを本発明のシステムにいかにして一体化するかは当業者にとって明らかであろう。
このシステム１０はさらに、基準ユニットに対応する基準確率密度をツリー構造内に構成するツリービィルダ６０も具える。これは各基準ユニット毎に繰り返す。このツリー構造は基準パターンデータベース４０に記憶する。ツリー構造の各リーフノードは基準確率密度に対応する。このツリー構造の詳細及びその（構造の）構築は後述することにする。ツリービィルダはＤＳＰ又はマイクロプロセッサを用いて構成することができる。有利には、ツリーはシステムのトレーニング中に予め構築する。
このシステム１０はさらに、入力パターンに対応する基準パターンを基準パターンデータベース４０に配置するローカライザ５０も具える。ローカライザ５０はＤＳＰ又はマイクロプロセッサを用いて構成することができる。配置された基準パターンは認識された基準パターンとして参照される。ローカライザ５０は、最下位のツリーレベルにおいて多数のリーフノードが選択されるまで基準ユニットに対応するツリー構造を各観測ベクトル毎にサーチすることにより配置を行うことができる。選択されたリーフノードについて、ローカライザ５０は、この基準ユニットに観測ベクトルがいかに良好に整合するかを決定する。この決定は、各選択されたリーフノードについて、そのリーフノードに対応する基準確率密度を用いて観測ベクトルについての観測尤度を計算することを含む。各基準ユニットについて、ある観測ベクトルについて計算された観測尤度を組み合わせて基準ユニット類似スコアを与える。各基準パターンについて、基準パターンに対応する、基準ユニットの基準ユニット類似スコアを組み合わせてパターン類似スコアを形成する。これは、順次の観測ベクトルについて繰り返す。パターン類似スコアについて最高尤度のような最良のものが計算された基準パターンを認識されたパターンとして配置する。この説明は基準確率密度の配置及び観測尤度の計算に焦点を合わせている。この分野において、この鍵となる要素が、隠れマルコフモデルのような他の技術との関連においてどのように用いられて連続する物理量から取り出された時間順次パターンを認識できるかは良好に理解される。この分野において、レベル分けされた手法のような技術を用いて基準パターンよりも大きな観測ベクトルシーケンスを有するパターンをいかにして認識するかも良好に理解される。例えば、サブワードユニットを基準パターンとしていかに用いてワード又は文章全体を認識するかは既知である。発音語義及び文法のような別の制約がどのようにパターン認識に課されるかも良好に理解される。発音語義のような別の情報は基準パターンデータベースを記憶するために用いたメモリと同一のメモリを用いて記憶することができる。
出力手段７０を用いて認識されたパターンを出力する。この出力手段は、認識されたパターンをスクリーン上にテキストフォーマットとして表示し、認識されたパターンをメモリに記憶し、又は認識されたパターンをコマンドのような入力として用いて次の処理動作を行うような種々の形態をとることができる。
隠れマルコフモデルを用いる場合、各隠れマルコフモデル及び各モデルの状態ｓについて観測ベクトル

の尤度は次式により与えられる。

ここで、ｗ_kはｋ番目の観測混合密度（クラスタ）の重みであり、Ｎは状態に対するクラスタの番号である。簡単にするため、状態インデックスｓは上記式中に表示されていない。音声認識システムは通常ラプラシァン又はガウシアン確率密度を用いてクラスタの確率分布をモデル化する。Ｌ_r ノルムを用いると、以下のように規定されている。

ここで、ラプラシァン確率密度のためにＬ₁ ノルム（距離）を用い、ガウシアン確率密度のためにＬ₂ ノルムを用い、確率について取り得る式として次式がえられる。

ここで、基準ベクトル

はｋ番目の観測混合密度の平均ベクトルである。係数ａ及びｂは観測ベクトル

が全ての取り得る値を取る場合、確率が１まで積分されるようにする。Ｌ_r ノルム以外の他の距離基準を用いることもできる。上記式に対して種々の形態のもの又は拡張したものが既知である。一例として、以下の３個の型式の多変量ガウシアン密度が与えられる。

この式において、ｓは隠れマルコフモデル状態に対するインデックスであり、ｋはこの状態内の密度（基準ベクトル）に対するインデックスである。
スケーリングを用いて、項がプロセッサの精度範囲以下となるのを防止し密度の分散に基づきベクトルを正規化することができる。有利には、対角共分散行列をこれらが結合される（tied）ように用いれば（状態依存共分散行列Ｋ_s,k＝Ｋ_s、又はグランド共分散行列Ｋ_s,k＝Ｋとなるように）、観測ベクトル

及び平均ベクトル

は、尤度計算される前にスケールされることになる。スケーリングはこの技術分野において周知である。有利には、基準ベクトルは予めスケール化され、観測ベクトルは実際の尤度計算が開始する前に１回スケール化されるだけである。
密度の性質により、確率の和は最大値により、すなわち最大確率に寄与する密度により近似することができる。これは、入力パターンに対応する基準パターンの配置における重要な工程は、最も近い観測ベクトルである基準ベクトルを見い出すことである（最も近い隣接する検索）。ここで、‘距離’は尤度の負の対数として規定される。

負の対数をとることにより、この式は以下のようになる。

多変量正規密度の場合、この式は以下のようになる。

ツリー構造
例えば４０個のサブワードユニットを用いる場合、サブワードユニット当たりの５個の状態及び状態当たりの６４個の要素クラスタ（各々が関連する基準確率密度により表わされる）は、例えば３２個の次元ベクトルを含む１２８００個の尤度計算を意味する。これらの計算は各観測毎に繰り返す。全ての尤度を完全に計算する代わりに、ツリー構造を用いて尤度が完全に計算される基準確率密度の部分集合を選択する。ツリー構造は各状態（state）毎に構築する。本例では、これは２００個（４０×５）のツリーを含み、各ツリーは状態に対して混合密度を形成する６４個の基準確率密度をそれぞれ有する。Ｎ個の要素クラスタ及び関連する基準確率密度（例えば、Ｎは３２，６４，１２８又は２５６とする）はこの特徴ベクトル空間をＮ個のセルに分割する（実際には、密度の分散が多く変化する場合、Ｎ個以上のセルが存在することがある。式はこれを黙示的に処理する。）後で詳細に説明するように、基準確率密度はトレーニング観測ベクトルから取り出される。基準確率密度は１個のトレーニング観測ベクトルだけでなく複数のトレーニング観測ベクトルの要素クラスタを表わすことも理解されたい。トレーニング観測ベクトルが１個だけしか含まれない場合でさえ、これは要素クラスタと称する。
Ｎ個のセルはＬレベルを有するＢ分木ツリー構造に構築する。Ｂは各ノードにおける最大数のブランチを示す。有利には、Ｎ＝Ｂ ^Lの場合、完全に平衡したツリーが用いられる。実際には、トレーニング中にあるクラスタ及び関連する基準確率密度が陳腐化したものになる場合がある。結果として、ツリーのあるリーフ又はブランチであっても、このツリーから除去される。トップレベルＬにおいて、ルートノードはセルの全体の集合を表わす。これらのセルはＢ個の部分集合（クラスタとも称する）に分割され、各部分集合はＮ／Ｂ個のセル（又は、ＮがＢの累乗でない場合、それ以下）を有する。各クラスタはレベルＬ−１の中間ノード（非リーフノード）により表される。その順序でこれらクラスタの各々は再びＢ個のサブクラスタ（あるブランチが陳腐化した場合それ以下）に分割され、各部分集合はレベルＬ−２の中間ノードにより表される。このサブクラスタへの分割は、最低レベル（レベル１）において各ノードがトレーニング観測ベクトルの１個の要素クラスタを表すまで繰り返す。各要素クラスタと関連するものは、トレーニング観測ベクトルのクラスタから取り出された基準確率密度である。ガウシアン密度を用いれば、各基準確率密度は平均ベクトル

及び共分散行列Ｋ_i（クラスタについて混合重み付けｗ_iを用いる）で表されることができる。ツリーのレベル２又はこれよりも高いレベルのノードに対応するクラスタはクラスタ確率密度と関連する。このクラスタ確率密度は全ての要素クラスタを表し、これら要素クラスタはノードの下のブランチに階層的に存在する。このように、クラスタ確率密度は要素クラスタと関連する基準確率密度から取り出すことができる。この機構は、より高位のレベル全てに対して繰り返される。
図４は１６個の平均ベクトル

により表される１６個の基準確率密度の混合を示すツリー構造を説明する。ツリーのレベル１のリーフノードｄ₁₆....ｄ₃₁の各々は基準確率密度及び関連する要素クラスタの１つに対応する。レベル２の中間ノードｄ₈...ｄ₁₅はそれぞれ２個のサブクラスタを有するクラスタを表す。一例として、ノードｄ₈ノードｄ₁₆及びｄ₁₇の親ノードである。このノードｄ₈はｄ₁₆及びｄ₁₇により表される２個のクラスタのトレーニング観測ベクトルを有するクラスタを表す。ノードｄ₈に対応するクラスタ確率密度は平均ベクトル

により表される。このクラスタ確率密度は

により表される２個の基準確率密度から取り出される。同様に、ｄ₄はｄ₈及びｄ₉により表される２個のクラスタのトレーニング観測ベクトルを有するクラスタを表し、従って、ｄ₄はｄ₁₆、ｄ₁₇、ｄ₁₈及びｄ₁₉により表される４個のクラスタのトレーニング観測ベクトルを有するクラスタを表す。ｄ₄に対応するクラスタ確率密度は平均ベクトル

により表される。このクラスタ確率密度はクラスタ確率密度

から取り出され、すなわち、

により表される基準確率密度から取り出される。勿論

により表されるクラスタ基準確率密度を用いて、

で表される基準確率密度の組に観測ベクトル

について高い尤度を与える基準確率密度の部分集合を配置する。ガウシアン密度の場合、平均ベクトル

は、以下の方法で重み付けされた平均を計算することにより基準確率密度の平均ベクトル

から取り出すことができる。

ここで、Ｍ₁は、ノードｄ_iにより表わされる部分集合中の基準ベクトルの数である。

により表される各確率密度についての対応する共分散行列Ｋ_iは以下の式で与えられる。

ツリーの構築
各状態について、確率密度の混合を音響トレーニング中に決定する。トレーニングデータ（トレーニング観測ベクトル又は基準ベクトル）の初期セットを用いていかにして適切なモデルを構成するか（例えば、基準ユニットのシーケンスを決定する）及びパターン認識用の観測ベクトルを如何にしてクラスタ化するかは周知である。各クラスタは平均ベクトル及び分散により表わされるクラスタ確率密度と関連する。また、トレーニングを利用してすでにトレーニングされた系をどのように改善するかも既知である。典型的なものとして、周知のｋ平均クラスタ法を用いてトレーニング観測ベクトルをクラスタ化する。Ｌ．ラビナ“ファンダメンタルズオブスピーチリコグニション”プレンティスホール、セクション３．４．４を参照されたい。有利には、このクラスタ法は、クラスタ化（clustering）を記憶することにより（各クラスタ毎に、１レベル低いどの子クラスを含むか）ツリー構造を構築するように構成されている。このように、トレーニング中に各状態についてツリー構造が構築される。一例として、二進ツリー構造は以下のようにして構成することができる。
１．トレーニング観測ベクトルの全体の組についての平均ベクトル（重心）

及び分散を持つ１つの密度を決定する。平均ベクトル

は全てのトレーニング観測ベクトルの平均である。
２．

の基準により２個の新しい重心

（及び分散）を決定することにより、上記密度を２個の密度に分割する。ここで、

は典型的には次数１．０の要素を有する分割ベクトルである。
３．各トレーニング観測ベクトルについて、２個の密度のうちいずれの密度がトレーニング観測ベクトルに最も類似しているかを決定し、この密度にトレーニング観測ベクトルを割り当てる。このようにして、２個のクラスタが形成される。
４．２個のクラスタの密度（重心及び分散）を再計算する。
５．繰り返し：顕著な改善にそれ以上は達しない場合又は予め定めた数の反復を行なった場合のような停止基準に達するまで工程３及び４を繰り返す。
６．繰り返し：所望の数のツリーレベルに到達するまで、ツリー中の１レベル低い各クラスタについて工程２〜５を繰り返す。
工程６おいて、２個のクラスタ間で決定された境界をより低いレベルに維持することにより（したがってツリーのブランチに割り当てられたベクトルが、１レベル低いサブクラスタの形成中に再割当てされない）、二進ツリーが構成される。このツリーのレベルを除外することにより、４分木のような２の累乗のブランチ因子を有する別のツリー構造を構成することができる。工程２の分割を適切に変化させることにより別のブランチ因子を有するツリーをどのようにして構成するかは明らかである。クラスタ化の説明はプールされた（pooled）共分散行列にフォーカスをあてる。別の共分散行列を有する密度を用いていかにしてクラスタ化するかは周知である。
ツリー検索
ツリー検索は、ルートノードよりも低いレベル（レベルＬ−１）で開始し、レベル１の少なくとも１個の基準確率密度（及び対応する要素クラスタ）が配置されるまで行う。レベルＬ−１の非リーフノードそれぞれについて、非リーフノードにより表される基準確率密度の部分集合により観測ベクトル

が作成される尤度を、非リーフノードに対応するクラスタ確率密度を用いて計算する。一例として、密度は式（ａ）により与えることができ、平均ベクトル

についてクラスタ確率密度を表す平均ベクトルをとる。最も大きな尤度が得られたブランチが追加的な検索のため選択される。或いは、規定された基準に基いて１個以上のブランチを選択することができる。選択されたブランチに対しツリーにおいて１レベル低いレベルで同一の処理を繰り返す。このようにして、ツリーのレベル２において少なくとも１個の基準確率密度の部分集合が配置される。配置された部分集合について、観測ベクトル

の尤度が部分集合の各基準確率密度について計算される。前述したように、実際のパターン認識の場合、計算された尤度は維持され、基準パターン毎に組み合わされると共に次の観測ベクトルについて計算された尤度と結合される。
検索中ツリーのトップレベルは用いられないので、このツリーは少なくともＬ＝３個のレベルを有すると理解されたい。完全なバランス木についてこの検索手法を用いれば、全部でＬ＝ｌｏｇ_B（Ｎ）のレベルがチェックされることが必要となり、各ツリーレベルについてＢ回の尤度計算が必要となる。ツリーの各レベルにおいて１個のブランチが選択されれば、選択されたブランチはツリーを通過するための付加的なオーバヘッドと共に全部でＢｌｏｇ_B（Ｎ）回の計算を与える。これは、全てのＮ個のセルの尤度を計算することより優れている。ツリー検索の欠点は、観測ベクトルについて最も高い尤度を与える基準確率密度が常時配置されることが保証されないことである（平均的中割合は１００％以下である）。これを図５に示し、図５は４個のリーフ（ｄ₄〜ｄ₇）を有する二進ツリーについてのセル境界の２次元例を与える。この図５は、トップレベル（レベル３）及びレベル２でのクラスタ化の結果として達成されたセル境界を示す。このクラスタ化は、太いラインにより示すセル境界により分離された４個のセルを与える。セルへの最敵な分割はトップレベル境界から部分的に偏位した細い境界線により示される（このツリーの第２レベルでの割当ては正確である）。ドットが打たれた領域は、ミスアサインされた領域を示す。
この方法をフィリップス自動タイムテーブル情報システムＡＩＳで試験した。
この話者独立認識システムは４０個の隠れマルコフモデルを用いる。これらのモデルは６個の状態を用いて文脈に依存しない音素をそれぞれモデル化する。連続混合密度を用いる。認識語彙は１８５０個のエントリを有する。トレーニング及び試験コーパスはドイツ語の実生活のトレーニングスケジュール照合で構成する（電話回線で記録した自然発声）。このシステムは７．３時間の音声（そのうち４７％は無音としてラベル化されている）を表す８７９３個の発声についてトレーニングが行われた。この試験コーパスは全体とし７０７８個の発声語になる２２７８個の発声（１．５時間の音声）で構成され、その２２４個は用語の範囲外である。以下のテーブルは、６４個のリーフを有するツリー（６分割）を用いて達成された結果を示す。全部で４０個の隠れマルコフモデル全部を用いて４０個のサブワードユニットをモデル化した。各モデルは６個の状態を有する。６個の状態について、３個の異なる混合を用い、連続する２つの状態は同一の混合を共有する（状態１及び２、状態３及び４、状態５及び６）。各混合は６４個の密度で構成される。付加的に、１個の状態だけを有する特別のモデルを用いて無音をモデル化した。これは、原理的に（４０×３＋１）×６４＝７７４４個の密度を与える。トレーニング中数個の密度は陳腐化したものとして識別され、ツリーから一掃され実際には全体として約７６００個の密度を用いた。このテーブルは、二進ツリーを与えるＢ＝２から平坦なツリーを与え事実上の完全サーチとなるＢ＝６４の範囲の種々のブランチィング係数について達成された結果を示す。ツリー中の各レベルにおいて１個のブランチだけを選択した。

このテーブルにおいて、Ｎ_effはこのモデルの各状態について平均的に計算された距離の数を示す。勿論、トレーニング中に数個の基準ベクトルが一掃されたので、Ｎeffは平均として完全ツリーの数よりも僅かに小さくなり、それぞれ１２、１２、１６、２０及び６４である。この的中確率は、完全検索及びツリー検索が同一の基準ベクトルを観測ベクトルに最も近いものとして配置する回数の割合を示す。ワードエラーレート（ＷＥＲ）は発声された語が正しく認識されなかった回数割合を示す。これは、置換（ある語を別の語として誤って認識すること）、挿入（長い語を短い語の列と誤って識別すること）及び削除（短い語の列を長い語として誤って識別すること）を含む。
種々の形式のツリーについて、以下の計算作業が必要である。

結果として、二進ツリーに必要な計算作業は四進ツリーについて必要な計算作業と同一である。以前のテーブルは、四進ツリーが二進ツリーよりも良好な結果を与えることを既に示している（四進ツリーはより少ない数のブランチィングレベルを持ち、全体としてより長い距離の計算が生じ、より高い精度の結果が与えられる）。従って、四進ツリー構造を用いることが有益である。勿論、より多くのブランチを有する、例えばＢ＝８又はＢ＝１６であるツリー構造を用いることにより、同じ理由から一層良好な結果が与えられる。一方、計算作業の増大により、多くのブランチの代わりにより多くのノードを有する四進ツリーを用いるのが有益である。これを以下のテーブルに図示する。

このテーブルは、より多くの密度を用いることに一層良好な結果（ワードエラーレートがより低くなる）が得られることを示す。四進ツリー（Ｂ＝４）を用いる１２８個及び２５６個のノードについての結果をＢ＝８で６４個のノードを有するツリーを用いることにより得られた結果（過去のテーブル）と比較することにより、より多くの密度を用いる四進ツリーはより少ないか又は同一の計算作業で一層良好な結果が得られること明らかである。
このテーブルは、密度の数が多くなると的中確率が低くなることも示している。的中確率は、ツリーの数個又は全てのレベルにおいて丁度１個以上のブランチを選択することにより改善することができる。これを実行する１の方法は、例えば四進ツリーにおいて各レベルにおいて２個のブランチを選択することである。６４個のリーフを有する四進ツリーの場合、この方法は各レベルで１個だけのブランチが選択された場合の１２個の計算と比べて２８個の計算を必要とする。ツリーのあるレベルにおいて４個のブランチのうちの１個のブランチが観測ベクトルについて他の３個のブランチドよりも高い尤度を与える場合、最も高い尤度を与える基準確率密度がそのブランチの一員である可能性が非常に高いことを理解されたい。他方において、１個以上のブランチのグループが観測ベクトルについて同様な又はより高い尤度を与える場合、ブランチを１個だけを選択することは誤った決定をするおそれがある。
従って、別の実施例においては閾値Ｔを用いる。ツリーの各レベルにおいて、最も高い尤度を与えるクラスタ確率密度を有するノード選択する。最良のノードの対数尤度と第２の最良のノードとの間の差異が閾値Ｔよりも低い場合、第２の最良のノードが選択され、両方のブランチがさらに検索される。この方法は、以下のテーブルに示すように、種々のＴ値について試験した。

このテーブルは、６４個のリーフを有するツリー及び２５６個のリーフを有するツリーについての結果を示す。各ツリーについて、第１の行は完全検索を用いる（閾値を用いない）結果を示す。Ｔ＝０のこの行は全てのレベルにおいてブランチが１個だけ選択された場合の結果を与える。より高い閾値の場合、モデル（ＮEFF）の各状態について実際に計算された距離の数により反映されるように、あるレベルにおいて２個のブランチが選択されたときの尤度は増大する。特に、２５６個のリーフのような大きなツリーの場合、精度が低下することなく性能が顕著に増大する。当業者は、このシステムについて最も適切な閾値を選択することができる。必要な場合、この閾値機構を用いて２個以上のブランチを選択することができる。
中間レベルにおいて、観測のクラスタ尤度は、リーフノードにより表される基準確率密度についてだけ実行される実際の尤度計算については実際には用いられない。中間レベルにおいて、どのクラスタ確率密度が観測ベクトルに対して最高の尤度を与えるかを知ることだけが必要であり、実際の尤度がどれだけであるかは必要ではない。
ユークリッドノルム（Ｌ2−ノルム）を用いるガウシアン密度の場合、主としてベクトルスカラー積の計算（内積又はドット積とも称する）を必要とする簡単な計算を用いてどのクラスタ確率密度が最高の尤度を与えるかを決定することができる。ガウシアン密度当たり単一のスカラー変数だけを有するガウシアン密度を用いることにより、
Ｋ_s,k＝Ｉ・σ_s,k ²
式（ａ）は以下の式となる。

以下のように規定することにより、

弁別関数

はどのクラスタ確率密度（平均ベクトル

により表される）が

に対して最高の尤度を与えるかを示す。

の符号だけが重要である。

が正の場合、

で表されるクラスタ確率密度は

に対して最高の尤度を与える。

が負の場合、

で表されるクラスタ確率密度は

に対して最高の尤度を与える。以下の原理を用いると、

について以下の式が与えられる。

この式において、最初の４つの項は例えばトレーニング中に１回で計算することができる。５番目の項について、第１の因子も１度で計算することができる。第２の因子

は各観測ベクトルについて１度だけ計算される必要があり、全ての基準ベクトルについて用いることができる。最後の項だけはベクトルスカラー積であり、各観測ベクトル及び各基準ベクトルについて計算する必要がある。この式を用いると、

を最初に用いてクラスタ確率密度１が

に対してクラスタ確率密度２よりも高い尤度を与えるか否かが決定される。次に、この最高の尤度を与えたクラスタ確率密度をクラスタ確率密度３と比較する。ツリーのこのレベルの全てのクラスタ確率密度が試験されるまで、これを繰り返す。計算についてクラスタ確率密度が選択される順序は重要ではない。
ガウシアン密度についての共分散行列が全ての混合密度に対して結合される場合、すなわち、ｓを隠れマルコフモデルの状態とし、ｋがこの状態の密度を示す場合に、共分散行列Ｋ_s,k＝Ｋ_sとなる場合、同様な技術を適用することができる。この結果、ツリーの異なるブランチにより表わされるクラスタ間の境界は超平面となる。式（ａ）は以下のようになる。

以下のように規定することにより、

弁別関数

は：

で表されるが、さらに

となる。
一般的には、

であり、かつ、Ｋ ^-1 は対称行列であるので、この式は：

となる。
この式において、項１，３及び４は例えばトレーニング中に１度で計算することができる。第２の項について、ベクトル

も予め計算することができ、

を有するベクトルのベクトルスカラー積がオンラインで計算されることを意味する。
トレーニング中のツリーの検索
トレーニング中に隠れマルコフモデルの未知のパラメータが評価される。これは、基準ユニット（状態）の未知のシーケンス及び未知のモデルパラメータ（混合密度パラメータ）の評価を含む。図６は典型的なトレーニングプロセスを示す。音声認識に用いられる音響分析の同一の工程を用いてトレーニング発声をトレーニング観測ベクトルの時間シーケンスに変換する。反復処理において、状態及びモデルパラメータに対するトレーニング観測ベクトルの時間整合を改善する。反復の各ループにおいて、その瞬時に構成されたモデルを用いてトレーニング観測ベクトルを時間整合させる。この処理をいかに行うかは既知であり、例えばビタビアルゴリズムを用いて処理することができる。このビタビアルゴリズムは観測ベクトルの所与のシーケンスに対する最良の状態シーケンスを決定する。時間整合の結果として、各トレーニング観測ベクトルは状態及びその混合密度に割り当てられる。次に、各混合密度の観測ベクトル集めて（クラスタ化）密度のパラメータの再評価に用いる。上述したｋ平均クラスタ化法をこのために用いることができる。明らかなように、時間整合により数個の観測ベクトルは別の状態及び混合密度に割当てられる。同時にツリーのあるレベルが構築されるので（クラスタ化の一部として）、再割当てが既に行われたクラスタ化及びツリーの構築に影響を与える。ツリーのトップレベルで最初からクラスタ化を再開始する代わりに、上述したツリー検索アルゴリズムを用いてトレーニング観測ベクトルのクラスタへの予備割当てを行うことが有益である。これは、１回多い反復レベルとしクラスタ化処理と一体化することができる。一例として、二進ツリー構造を以下のようにして構築する（以下の処理は各状態について並列して行う）。
１．状態に対し、トレーニング観測ベクトルの全体の組についての平均ベクトル（重心）

及び分散を持つ１つの混合密度を決定する。平均ベクトル

は全てのトレーニング観測ベクトルの平均である。
２．各トレーニング観測ベクトルについて最適な状態を決定することにより、このシステムをについて時間整合を行う。
３．混合密度を再計算する。
４．反復：顕著な改善がされず又は予め定めた回数の反復が行われた場合のような停止基準に達するまで工程２及び３を繰り返す。
５．規則

に基づき２個の新しい重心

を決定することにより、混合密度を２個の混合密度（１レベル下位）に分割する。ここで、

は分割ベクトルであり、典型的にはオーダー１．０の成分を有する（２個の新しい密度の分散はここでは元の密度から複写する）。
６．各観測ベクトルについての２個の混合密度のどちらがこの観測ベクトルに近いかを決定し、この観測ベクトルをその密度に割り当てる。このようにして２個のクラスタが形成される。
７．２個のクラスタの混合密度（重心及び分散）を再計算する。
８．反復：顕著な改善がされず又は予め定めた回数の反復が行われた場合のような停止基準に達するまで工程６及び７を繰り返す。
９．各トレーニング観測ベクトルについて最適な状態を決定することにより、このシステムを時間整合させる。
１０．ツリー検索アルゴリズムを用いて各トレーニングベクトルを現在構築されようとするツリーレベルのクラスタに割り当てる。
１１．現在のツリーレベルから上向きに開始して全ての混合密度を再計算する。
１２．反復：顕著な改善がされず又は予め定めた回数の反復が行われた場合のような停止基準に達するまで工程１０及び１１を繰り返す。
１３．反復：顕著な改善がされず又は予め定めた回数の反復が行われた場合のような停止基準に達するまで工程９を繰り返す。
１４．反復：所望のツリーレベルの数に到達するまで、現在最下位のレベル（安定している）の各混合密度について工程５から開始して繰り返す。
図６の反復の開始点として、これらトレーニングセンテンス（観測シーケンス）の各々は、手動で複数の状態にセグメント化すること、又はその代わりに、線形に、若しくは、入手可能な場合には古いモデルを用いて、自動で複数の状態にセグメント化することができる。
トレーニング中にツリー検索を用いることにより、このシステムのトレーニングに必要な時間が大幅に減少する。２９０００個の密度の最大分解能で動作するＡＩＳシステムにおいて、トレーニング時間が１０８時間から２５時間に減少した。勿論、これは認識低下につながる。以下のテーブルは、高い分解能のシステムよりも影響を受ける低い分解能のシステム（ツリー当たり１６個のリーフ、全部で１９００個の密度）の場合相対損失が約２％であることを示している。

Claims

連続する物理量から取り出した入力パターンを認識する方法において、前記物理量にアクセスし、該物理量から前記入力パターンを表す入力観測ベクトルのシーケンスを生成し、
複数の基準パターン中に前記入力パターンと対応する認識された基準パターンを配置し、少なくとも１個の基準パターンが基準ユニットのシーケンスであり、各基準ユニットは基準確率密度の組中の少なくとも１個の関連する基準確率密度で表されており、
前記基準確率密度の選択をツリー構造として表し、該ツリー構造において各リーフノードが基準確率密度に対応すると共に非リーフノードがクラスタ確率密度に対応し、該クラスタ確率密度は前記非リーフノードのブランチのリーフノードに対応する基準確率密度から取り出されることを有し、
前記配置が、各入力観測ベクトル

に対して、
前記対応するクラスタ確率密度が前記入力観測ベクトル

について最適のクラスタ尤度を与える非リーフノードを通る前記ツリー構造を検索することにより複数のリーフノードを選択する事と、
選択されたリーフノードに対応する各基準確率密度について前記入力観測ベクトル

の観測尤度を計算する事とを含み、
前記方法が、各基準ユニットに関連付けられる基準確率密度を個別のツリー構造として表すことを含み、
前記配置が、各個別のツリー構造について前記検索を行うことにより各個別のツリー構造のリーフノードを選択することを含むことを特徴とする方法。
請求項１に記載の方法において、非リーフノードを通る前記ツリー構造の検索が、前記ツリー構造の少なくとも１個のレベルにおいて、前記クラスタ尤度の最適値が計算される１つの非リーフノードを通る経路を検索することを含み、前記クラスタ尤度が前記最適なクラスタ尤度が所定の範囲内にある非リーフノードを通る経路により補完されることを特徴とする方法。
請求項１又は２に記載の方法において、前記ツリー構造が四進ツリーであり、前記四進ツリーにおいて、各非リーフノードは１つ下の階層に最大４つのノードを抱え、かつ、少なくとも１つの非リーフノードが１つ下の階層に４つのノードを抱えることを特徴とする方法。
請求項１、２又は３に記載の方法において、前記非リーフノードを通るツリー構造の検索が、前記ツリー構造の同一のブランチ内かつ前記ツリー構造の同一のレベルにある一群の非リーフノードに対して、
選択された前記非リーフノードの対について、２個の対応するクラスタ確率密度と前記入力観測ベクトル

との間のクラスタ比較スコアを計算し、前記クラスタ確率密度のスコアは２個の対応するクラスタ確率密度のいずれが前記入力観測ベクトル

の最高の尤度を与えるかを示しており、
前記群の全ての非リーフノードについてクラスタ比較スコアが計算されるまで、過去に計算されたクラスタ比較スコアが最高の尤度を示す非リーフノード及びクラスタ比較スコアがまだ計算されていない前記群の別の非リーフノードについて前記クラスタ比較スコアを計算し続け、
前記クラスタ比較スコアが最高の尤度を示す前記非リーフノードを通る経路を前記検索に含めることを有することを特徴とする方法。
請求項１、２、３又は４に記載の方法において、既知の入力パターンを表すトレーニング観測ベクトルのシーケンスから前記確率密度が取り出され、前記基準確率密度の組をツリー構造として表す工程が、前記トレーニング観測ベクトルをクラスタの階層的な組にクラスタ化すること、及び各クラスタについてクラスタ確率密度を計算することを有しており、
前記基準確率密度の組をツリー構造として表す工程は、
前記トレーニング観測ベクトルのシーケンスを、対応する基準パターンと対応する基準ユニットとのシーケンスにセグメント化する工程と、
反復的に、
各基準ユニットについて、前記対応するトレーニング観測ベクトルを、各々が個別の基準ユニットに対応する個別のツリー構造を形成する、クラスタの階層的な組にクラスタ化し、
各トレーニング観測ベクトルについて、予め定めた最適基準に基づいて最も類似する対応する基準ユニットを決定することにより、及び、最適なクラスタ尤度を有するクラスタについて対応する基準ユニットのツリー構造を検索して前記クラスタの１つに各トレーニング観測ベクトルを割り当てることにより、前記基準ユニットのシーケンスに基づいて前記トレーニング観測ベクトルのシーケンスを時間整合させる工程とを有することを特徴とする方法。
連続する物理量から取り出した時間順次する入力パターンを認識するシステムであって、該システムは、
前記物理量にアクセスし、該物理量から前記入力パターンを表す入力観測ベクトルのシーケンスを発生させる入力手段と、
基準確率の組から基準確率密度の選択をツリー構造として表すツリービィルダであって、前記ツリー構造において各リーフノードが基準確率密度に対応し、各非リーフノードがクラスタ確率密度に対応し、このクラスタ確率密度が前記非リーフノードよりも下位のブランチのリーフノードに対応する全ての基準確率密度から取り出されるツリービィルダと、
複数の基準パターンを記憶する基準パターンデータベースであって、少なくとも１個の基準パターンが基準ユニットのシーケンスであり、各基準ユニットが前記基準確率密度の組の少なくとも１個の関連する基準確率密度により表され、前記基準確率密度の選択が前記ツリー構造として記憶される基準パターンデータベースと、
前記入力パターンに対応する、認識された基準パターンを前記基準パターンデータベースに記憶されている前記基準パターン中に配置するローカライザであって、前記配置が、各入力観測ベクトル

に対して、
前記観測入力ベクトル

について前記対応するクラスタ確率密度が最適のクラスタ尤度を与える非リーフノードを通る前記ツリー構造を検索することにより複数のリーフノードを選択する事と、
選択したリーフノードに対応する各基準確率密度について前記入力観測ベクトル

の観測尤度を計算する事とを有するローカライザと、
前記認識されたパターンを出力する出力手段とを有し、
前記ツリービィルダが、各基準ユニットについて前記関連する基準確率密度を個別のツリー構造として表すものとして想定され、
前記基準パターンデータベースが、各基準ユニットについて前記個別のツリー構造をさらに記憶し、
前記配置が、各個別のツリー構造についての前記検索を行うことにより各個別のツリー構造のリーフノードを選択することを有することを特徴とする時間順次する入力パターンを認識するシステム。
請求項６に記載のシステムにおいて、非リーフノードを通る前記ツリー構造の検索が、前記ツリー構造の少なくとも１個のレベルにおいて、前記クラスタ尤度の最適値が計算される非リーフノードの１つを通る経路を検索することを含み、前記クラスタ尤度が前記最適のクラスタ尤度の予め定めた範囲内にある非リーフノードを通る経路により補完されることを含むことを特徴とするシステム。
請求項６又は７に記載のシステムにおいて、前記ツリー構造が四進ツリーであり、前記四進ツリーにおいて、各非リーフノードは１つ下の階層に最大４つのノードを抱え、かつ、少なくとも１つの非リーフノードが１つ下の階層に４つのノードを抱えることを特徴とするシステム。
請求項６、７又は８に記載のシステムにおいて、前記非リーフノードを通るツリー構造の検索が、前記ツリー構造の同一のブランチ内かつ前記ツリー構造にある同一のレベルの一群の非リーフノードに対して、
選択した前記非リーフノードの対について、前記２個の対応するクラスタ確率密度と前記入力観測ベクトル

との間のクラスタ比較スコアを計算し、前記クラスタ比較スコアは、前記２個の対応するクラスタ確率密度のいずれが前記入力観測ベクトル

の最高の尤度を与えるか示しており、
前記群の全ての非リーフノードについてクラスタ比較スコアが計算されるまで、以前に計算されたクラスタ比較スコアが前記最高の尤度を示す非リーフノードとクラスタ比較スコアがまだ計算されていない前記群の別の非リーフノードとに対して前記クラスタ比較スコアを計算し続け、
前記クラスタ比較スコアが最高の尤度を示す前記非リーフノードを通る経路を前記検索に含ませることを有することを特徴とするシステム。
請求項６、７、８又は９に記載のシステムにおいて、前記確率密度が既知の入力パターンを表すトレーニング観測ベクトルのシーケンスから取り出され、前記基準確率密度の組をツリー構造として表す前記工程が、前記トレーニング観測ベクトルをクラスタの階層的な組にクラスタ化すること、及び各クラスタについてクラスタ確率密度を計算することを含んでおり、
前記確率密度の組をツリー構造として表す前記工程は、
前記トレーニング観測ベクトルのシーケンスを、対応する基準パターン及び対応する基準ユニットのシーケンスにセグメント化する工程と、
反復的に、
各基準ユニットについて、前記対応するトレーニング観測ベクトルを、各々が個別の基準ユニットに対応する個別のツリー構造を形成する、クラスタの階層的な組にクラスタ化し、
各トレーニング観測ベクトルについて、所定の最適基準に基づいて最も類似する対応する基準ユニットを決定することにより、及び、最適なクラスタ尤度を有するクラスタについて前記対応する基準ユニットの前記ツリー構造を検索して前記クラスタの１つに各トレーニング観測ベクトルを割り当てることにより、前記基準ユニットのシーケンスに基づいて前記トレーニング観測ベクトルのシーケンスを時間整合させる工程とを有することを特徴とするシステム。