(57)【特許請求の範囲】
【請求項１】
入力信号から抽出された特徴パラメータと、認識パタンが木構造で表現された確率的な状態遷移モデルとを照合し、前記特徴パラメータに対する確率モデルの各状態の尤度を計算しながら状態仮説を遷移させ、最尤な状態遷移パスを認識パタンとするパタン認識装置において、
入力信号の特徴パラメータに基づいて、前記状態遷移モデルの探索空間で尤度計算を実行する探索手段と、
前記探索空間を、確率モデルの状態から分岐して終端の状態に到達するパタン総数に基づいて、仮想的に複数の領域に分割する領域分割手段と、
同一時刻で遷移する状態仮説を前記分割された領域のいずれかに振り分ける状態仮説振分手段と、
前記分割された領域ごとに、同一領域内で尤度の低い状態仮説を探索対象から除外する領域別枝刈り手段とを具備したことを特徴とするパタン認識装置。
【請求項２】
前記分割された領域ごとに枝刈り条件を設定する枝刈り条件設定手段をさらに含むことを特徴とする請求項１に記載のパタン認識装置。
【請求項３】
前記領域分割手段は、探索空間を、各状態が当該状態以降に分岐して終端の状態に到達するパタン総数に基づいて分割することを特徴とする請求項１または２に記載のパタン認識装置。
【請求項４】
前記枝刈り条件設定手段は、分岐するパタン総数が少ない領域ほど枝刈り条件を厳しくすることを特徴とする請求項３に記載のパタン認識装置。
【請求項５】
前記領域分割手段は、木構造の各根から分岐するパタン総数が当該各根の種類に応じて特異的な探索空間を当該根ごとに分割することを特徴とする請求項１または２に記載のパタン認識装置。
【請求項６】
前記枝刈り条件設定手段は、パタン総数が少ない領域ほど枝刈り条件を厳しくすることを特徴とする請求項５に記載のパタン認識装置。
【請求項７】
音声信号からフレーム単位で音響特徴パラメータを抽出する音響分析手段をさらに含み、
前記音響特徴パラメータに基づいて音声認識を行うことを特徴とする請求項１ないし６のいずれかに記載のパタン認識装置。
【請求項８】
コンピュータが、入力信号から抽出された特徴パラメータと、認識モデルが木構造で表現された確率的な状態遷移モデルとを照合し、前記特徴パラメータに対する確率モデルの各状態の尤度を計算しながら状態仮説を遷移させ、最尤な状態遷移パスを認識パタンとするパタン認識方法において、
コンピュータが、入力信号の特徴パラメータに基づいて、前記状態遷移モデルの探索空間で尤度計算を実行する手順と、
コンピュータが、前記探索空間を、確率モデルの状態から分岐して終端の状態に到達するパタン総数に基づいて、仮想的に複数の領域に分割する手順と、
コンピュータが、同一時刻で遷移する状態仮説を前記いずれかの領域に振り分ける手順と、
前記分割された領域ごとに、同一領域内で尤度の低い状態仮説を探索対象から除外する領域枝刈り手順とを含むことを特徴とするパタン認識方法。
【請求項９】
前記請求項８に記載のパタン認識方法を、コンピュータに実行させるためのパタン認識プログラム。
【請求項１０】
前記請求項９に記載したパタン認識プログラムをコンピュータが読み取り可能に記憶した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パタン認識方法および装置ならびにパタン認識プログラムおよびその記録媒体に係り、特に、HMMに代表される確率的な状態遷移モデルを用いて、音声認識などのパタン認識を行うパタン認識方法および装置ならびにパタン認識プログラムおよびその記録媒体に関する。
【背景技術】
【０００２】
音声認識では、入力された音声信号に最も近い単語列が、状態系列として表現される単語との類似度に基づいて判定される。HMM(Hidden Markov Model：隠れマルコフモデル)は、単語や単語を構成する音素を表現するのに適切な確率モデルの１つであり、HMMの各状態は状態遷移確率および出力確率密度関数を持つ。以下、従来の音声認識の手法を、前記HMM を利用した場合を例にして説明する。
【０００３】
音声認識装置では、認識可能な文の集合が単語を単位とするネットワークとして記述された文法と、文を構成する単語の読み（音素列）が記述された単語辞書とに従って認識処理が進行する。図８は、文法の一例を示した図であり、ここでは、「伊藤です」、「糸井です」、「今井です」、「土井です」という４つの音声を識別する場合を例にして説明する。
【０００４】
図８に示された文法は、丸数字１で示した状態「１」を始端（文頭）とし、状態「５」を終端（文末）とする状態遷移図であり、矢印で対応付けられた単語を出力して状態間を遷移する。文法を構成する各単語は、その読み（音素列）に従ってHMMの状態系列として表現され、単語辞書に含まれる単語の集合は、図９に示したような木構造辞書として展開される。
【０００５】
木構造辞書では、各単語が音素列に分解され、単語「糸井」であれば４つの音素「i」，「t」，「o」，「i」の列に展開される。各音素は、通常３つ程度の状態（HMM状態）から構成される。木構造辞書は、HMMの状態系列として表現される単語間で、先頭から共通する部分的な状態系列をマージすることにより、右に進むにつれて分岐が広がる状態遷移図である。図９の木構造辞書では、「伊藤」、「糸井」、「今井」の３単語で、単語先頭の「い」に相当するHMMの状態系列がマージされ、さらに「伊藤」と「糸井」の間で「いと」までに相当するHMMの状態系列がマージされている。また「土井」と「です」との間で、単語先頭の「d」に相当するHMM状態系列がマージされている。図中の「sil」は無音声区間（silence）を表している。
【０００６】
音声認識処理では、図８に示した文法の制約に従って、図９に示した木構造辞書中の単語先頭のHMM状態から、状態仮説と呼ばれるトークンが木構造辞書を左から右へと遷移する。状態仮説が単語終端のHMM状態に到達すると、単語仮説と呼ばれる履歴を残して、図８の文法における該当単語の遷移先状態に遷移する。遷移先状態が文末でなければ、次の時刻から同様に、文法の制約に従って木構造辞書の探索が行われる。
【０００７】
木構造辞書中のHMM状態系列を状態仮説が左から右へと遷移する間に、入力音声に対して、その単語らしさのスコア（累積尤度）が計算される。木構造辞書を構成する各HMM状態は、音響特徴パラメータの入力に対して尤もらしさを出力する確率分布（出力確率密度関数）を有している。また、HMM状態間の遷移について遷移確率（状態遷移確率）が定義されている。これらの確率を時間方向に累積することで累積尤度が計算される。
【０００８】
この累積尤度は、後述する認識結果の確定処理のため、状態仮説が各単語の終端の状態に到達して単語仮説と呼ばれる履歴を残すときに、先行する単語仮説のインデックスとともに単語仮説中に格納される。
【０００９】
音声信号を分析して音響特徴パラメータを得る所定の一定周期ごとに、各HMM状態まで遷移した各状態仮説は、さらに自身のHMM状態への遷移（自己遷移）および右隣のHMM状態への遷移（L-R遷移）とを同時に繰り返す。このとき、t番目のフレームに状態jが存在する累積尤度をαj(t)とすれば、この累積尤度αj(t)は次式(1)で表される。ここで、αijは状態iから状態jへの遷移確率、bj(ot)は状態jが音響特徴量otを出力する確率である。自己遷移は、次式(1)においてi=jの場合として考える。
【００１０】
【数１】
0005309343.tif 000002
【００１１】
T個のフレームから構成される音声信号についてN個のHMM状態からなる単語系列を探索する場合、すなわち、状態仮説がHMM状態系列を遷移していく場合の、自己遷移とL-R遷移との探索空間（トレリス）を図１０に示す。トレリス空間は、横軸を観察系列としてのフレーム、縦軸を状態として可能な状態系列を示す格子グラフであって、それぞれの状態系列は、各時刻における状態を表す点（○印）を線分で結んだ折れ線で表される。
【００１２】
図１０に示したように、t番目のフレームのタイミングで状態jに至るパスは数多く存在するが、音声認識は最も確からしいパス（最尤パス）を求めるのが目的であるので、各フレームの各HMM状態において、次式(2)に従って累積尤度の高い状態仮説を残すViterbi探索が行われる。
【００１３】
【数２】
0005309343.tif 000003
【００１４】
音声認識処理は、文法が許容する全ての単語連鎖を探索する必要があるため、同時刻に数多くの状態仮説が、自分自身のHMM状態への遷移（図１０では、右隣りへの自己遷移）と隣接する他のHMM状態への遷移（図１０では、右下隣りへのL-R遷移）とを行うので、その計算量は膨大になる。この計算量の増大を抑えるために、通常はViterbi探索途中で確率の小さい状態仮説を探索空間から除外する「枝刈り」が行われる。
【００１５】
その後、パワーの低下等、音声の終了を判断する何らかの条件により探索処理が終了すると、終了時刻に文末に到達した単語仮説のうち、音声始端からの累積尤度が最も高いものから、先行する単語の系列（この単語仮説に至るまでの単語の履歴）が導き出され、これが最終的な認識結果の候補となる。この操作はバックトレースと呼ばれる。
【００１６】
上記した枝刈りでは、発声全体の探索を終えた時点で累積尤度が最大になる状態仮説を必ず残すようにしながら、状態仮説数を効率的に削減することが要求される。従来の枝刈りは、Viterbi探索の各フレームで累積尤度の高い状態仮説を残し、累積尤度の低い状態仮説を次フレーム以降の探索対象から取り除くために、以下の２種類の方法が併用されることが多い。
【００１７】
(1)ビーム幅による枝刈り
【００１８】
この枝刈り方法では、処理中の時刻における最大の尤度から、尤度が一定幅以内にある状態仮説を次の時刻の探索空間として残し、尤度が一定幅以上に低い状態仮説は次の時刻の探索空間から除外される。すなわち、時刻t、状態jの尤度が同時刻の全状態仮説中で最大の尤度と比較される。そして、次式(3)が成立する場合は、状態jを次の時刻の探索空間に残し、次式(4)が成立する場合は、状態jを次の時刻の探索空間から除外する。θpruningは枝刈りの閾値であって正の実数であり、ビーム幅と呼ばれる。
【００１９】
【数３】
0005309343.tif 000004
【００２０】
【数４】
0005309343.tif 000005
【００２１】
(2)ヒストグラムによる枝刈り
【００２２】
上記したビーム幅による枝刈りでは、ビーム幅の範囲に多数の状態仮説が残る可能性があり、想定以上に処理時間を増大させてしまうことがある。これに対して、この枝刈り方法では、残す状態仮説が個数により制限される。ただし、厳密に個数により制限するためには状態仮説数をスコア（累積尤度）の順にソーティングする必要があるが、ソーティングのコストを回避するためにヒストグラムによる枝刈りが行われる。
【００２３】
即ち、全状態仮説中最大の対数尤度との差分に対して予め適当な区分を設定しておき、全状態仮説がどの区分に該当するかを記録してヒストグラムを作成し、最後に累積尤度の高い区分から順に度数を累積する。そして、累積度数が一定個数を超える区間までの状態仮説は次フレームの探索対象として残し、それ以降の区間の状態仮説は除外する。個数の閾値は最大許容仮説数と呼ばれる。
【００２４】
特許文献１〜５には、ビーム幅と最大許容仮説数とを適応的に設定する技術（従来技術A）が開示されており、特許文献６には、枝刈りで残される状態仮説の多様性が失われないようにする技術（従来技術B）が開示されている。
【００２５】
特許文献１には、計算量の少ない音響モデルを用いた確率計算部により、未探索部分における順位の変動幅を推定し、推定値によりビーム幅および最大許容仮説数を動的に設定する技術が開示されている。特許文献２には、文法の選択肢の数の指標であるパープレキシティを計算することによりビーム幅および最大許容仮説数を動的に設定する技術が開示されている。
【００２６】
特許文献３には、現行のビーム幅で残される仮説数をカウントし、残される仮説数の大小に応じて、それ以降のビーム幅を適応的に設定する技術が開示されている。特許文献４には、文法における現在の探索位置（深さ）をパラメータとしてニューラルネットで動的にビーム幅を決定する技術が開示されている。
【００２７】
特許文献５には、DPマッチングによる音声認識における仮説数をカウントし、残される仮説数の大小に応じてそれ以降の距離に対する閾値を適応的に設定する技術が開示されている。特許文献６には、複数の音響モデル（即ち、複数の木構造辞書）を併用して探索処理を行う場合に、各々の音響モデルごとに枝刈りを行う技術が開示されている。
【先行技術文献】
【特許文献】
【００２８】
【特許文献１】特開２００１−７５５９６号公報
【特許文献２】特開平１１−１１９７９３号公報
【特許文献３】特開平１０−１５３９９９号公報
【特許文献４】特開平６−２８２２９５号公報
【特許文献５】特開平５−３５２９２号公報
【特許文献６】特開２００５−１０４６４号公報
【発明の概要】
【発明が解決しようとする課題】
【００２９】
枝刈りの目的は、最終的に最尤となるパスを見いだせるように、木構造辞書の広い探索空間を少ない状態仮説で効率的に探索することである。上記した従来の枝刈り方法では、木構造辞書の一部の領域に状態仮説が集中して残り、それ以外の広い領域に状態仮説が残らないことがあり、これでは効率的な探索が行われているといえない。
【００３０】
上記した従来技術Aに属する改良手法を適用しても、上記の問題は根本的に解決されない。従来技術Bに属する技術では、複数の音響モデルを併用する場合の枝刈りが効率化されるものの、単一の木構造辞書における枝刈りを効率化できない。
【００３１】
本発明の目的は、上記した従来技術の課題を解決し、単一の木構造辞書であっても、木構造辞書の構造的な特徴を生かして、認識率を低下させることなく、状態仮説を効率良く枝刈りできるパタン認識方法および装置ならびにパタン認識プログラムおよびその記録媒体を提供することにある。
【課題を解決するための手段】
【００３２】
上記の目的を達成するために、本発明は、入力信号から抽出された特徴パラメータと、認識パタンが木構造で表現された確率的な状態遷移モデルとを照合し、特徴パラメータに対する確率モデルの各状態の尤度を計算しながら状態仮説を遷移させ、最尤な状態遷移パスを認識パタンとするパタン認識装置において、以下のような構成を具備した点に特徴がある。
【００３３】
(1)入力信号の特徴パラメータに基づいて、前記状態遷移モデルの探索空間で尤度計算を実行する探索手段と、前記探索空間を、確率モデルの状態から分岐するパタン総数に基づいて、仮想的に複数の領域に分割する領域分割手段と、同一時刻で遷移する状態仮説を前記分割された領域のいずれかに振り分ける状態仮説振分手段と、前記分割された領域ごとに、同一領域内で尤度の低い状態仮説を探索対象から除外する領域別枝刈り手段とを設けた。
【００３４】
(2)分割された領域ごとに枝刈り条件を設定する枝刈り条件設定手段をさらに設けた。
【発明の効果】
【００３５】
上記の特徴(1)によれば、状態遷移モデルの探索空間が、分岐するパタン総数に基づいて複数の領域に分割され、領域ごとに独立して枝刈りが実行されるので、分岐するパタン総数が多い領域と少ない領域とで独立して累積尤度が上位の状態仮説を残すことができる。したがって、一の領域に属する各状態仮説の累積尤度が他の一の領域に属する各状態仮説の累積尤度よりも相対的に高く、一の領域と他の一の領域とを分割せずに一括して枝刈りしたときには累積尤度が上位とならない他の一の領域の状態仮説も、領域ごとに枝刈りを行うことにより残すことが可能になる。
【００３６】
上記の特徴(2)によれば、状態遷移モデルの探索空間を、各状態から分岐するパタン総数に基づいて複数の領域に分割できるので、分岐するパタン総数が多い領域よりも少ない領域を厳しく枝刈りすれば、パタン総数を抑えながら、将来的に多数のパタンが分岐する状態仮説を確実に残せるようになり、その結果、認識率を低下させることなく、状態仮説をさらに効率良く枝刈りできるようになる。
【図面の簡単な説明】
【００３７】
【図１】本発明の概要を説明するための木構造辞書の一例を示した図である。
【図２】本発明を適用した音声認識装置の主要部の構成を示したブロック図である
【図３】図２に示した探索部の機能ブロック図である。
【図４】本発明を適用した音声認識の手順を示したフローチャートである。
【図５】領域別枝刈り処理の手順を示したフローチャートである。
【図６】本発明の第１実施形態を説明するための図である。
【図７】本発明の第２実施形態を説明するための図である。
【図８】文法の一例を示した図である。
【図９】木構造辞書の一例を示した図である。
【図１０】自己遷移とL-R遷移との空間（トレリス）の一例を示した図である。
【発明を実施するための形態】
【００３８】
以下、図面を参照して本発明の基本的な概念について説明する。ここでは初めに、図１に示した音素列「a」で始まる地名の木構造辞書を例にして説明する。
【００３９】
音素列「ai」で始まる地名のうち、音素列「aio」で始まる地名は「相生(aioi)」に限定されるので、状態仮説が音素列「aio」の探索空間を過ぎれば単語（パタン）が確定する。同様に、音素列「aika」で始まる地名は「秋鹿町」、「相川」および「愛環梅坪」の３つであるが、音素列「aikam」で始まる地名は「秋鹿町」に限定されるので、状態仮説が音素列「aikam」の探索空間を過ぎれば単語が確定する。
【００４０】
ここで、ある時刻で自己遷移またはLR遷移した全N1個の状態仮説を対象に枝刈りを行うとき、従来技術であれば、N1個の全ての状態仮説を対象に枝刈りが行われ、ビーム幅や最大許容仮説数で決まる上位n1個の状態仮説のみが残る。このとき、状態仮説が多くの単語に到達する可能性を残すためには、探索空間の広い範囲にわたって、その状態仮説が上位n1個の中に漏れなく残るようにすることが望ましい。しかしながら、実際には単語が確定する領域の状態仮説のみが上位を占めてしまうような場合があり、このような場合には、多くの単語に到達する可能性が一度に失われてしまう。
【００４１】
これに対して、探索空間を、例えば単語が確定される領域と単語が確定されない領域とに分割し、各領域において別々に枝刈りを行い、領域ごとに上位の状態仮説を残せば上記したような技術課題を解決できる。
【００４２】
すなわち、同一時刻で自己遷移またはLR遷移した全N1個の状態仮説のうち、一方の領域にある全N2個の状態仮説のみを対象に枝刈りを行って、その上位n2個の状態仮説を残すと共に、これとは別に、他方の領域にある全N3個の状態仮説を対象に枝刈りを行って、その上位n3個の状態仮説を残す。このようにすれば、探索空間の一部領域のみに状態仮説が偏在することが無くなるので、認識率を低下させることなく全体の状態仮説数を削減できるようになる。
【００４３】
本発明では、このような考察に基づいて、探索空間を複数の領域に分割し、領域ごとに、同一領域内で同一時刻に遷移する状態仮説間で尤度を計算し、尤度の低い状態仮説を枝刈りすることによって、認識率を低下させることなく全体の状態仮説数を削減できるようにしている。
【００４４】
図２は、本発明のパタン認識方法を適用した音声認識装置の主要部の構成を示したブロック図である。
【００４５】
音声信号入力部１１は、入力された音声信号をデジタル信号に変換する。音響分析部１２は、音声デジタル信号を音響分析して音響特徴パラメータを抽出し、これをパラメータ記憶部１３に記憶する。音響特徴パラメータとは、入力音声を一定時間間隔（例えば１０ms：以下、フレームと表現する）毎に分析して得られる特徴ベクトルである。したがって、音声信号は特徴ベクトルの系列X＝x1,x2,…,xTに変換される。
【００４６】
探索データベース１４には、探索用の文法および木構造辞書（音素モデルの確率的な状態遷移モデル）が予め記憶されている。音響モデルデータベース１７には、予め作成された音響モデルが登録されている。探索部１５は、前記探索用の文法、木構造辞書および音響モデルに音響特徴パラメータの時系列データを照合させて音響的な尤度を算出し、この尤度を時間方向に累積して累積尤度を求める尤度計算部１５１と、探索過程で各状態仮説を自己遷移させる自己遷移部１５２およびLR遷移させるLR遷移部１５３と、探索過程で尤度の低い状態仮説を探索対象から除外する枝刈り部１５４と、単語末尾まで進んだ状態仮説の単語仮説を出力する単語仮説出力部１５５とを含む。
【００４７】
なお、文法の制約から木構造辞書の状態系列が複数に枝分れする場合、探索部１５は枝の数だけ状態仮説を複製し、枝ごとに状態仮説を進行させて尤度を計算する。認識結果判定部１６は、文法上の最後のHMM状態まで到達した全ての状態仮説を累積尤度に基づいてソートし、累積尤度が最も高い状態系列にバックトレースを実行して認識結果を判定する。
【００４８】
図３は、前記枝刈り部１５４の主要部の構成を示した機能ブロック図であり、状態遷移モデルの探索空間を複数の領域に分割する領域分割部１５４ａと、同一時刻で遷移する状態仮説を前記分割された領域のいずれかに振り分ける状態仮説振り分け部１５４ｂと、前記分割された各領域の枝刈り条件を設定する枝刈り条件設定部１５４ｃと、前記分割された領域ごとに、同一領域内で尤度の低い状態仮説を探索対象から除外する領域別枝刈り部１５４ｄとを含む。
【００４９】
前記領域別枝刈り部１５４ｄは、実用時間内での処理が可能ならば、一つの枝刈り部で領域ごとに枝刈りを繰り返すようにしても良いし、複数の枝刈り部を設けて、これらで並列的に枝刈りを行うようにしても良い。
【００５０】
図４は、本発明のパタン認識方法を適用した音声認識の手順を示したフローチャートであり、主に前記探索部１５の動作を示している。
【００５１】
ここでは、音声信号入力部１１に入力された認識対象の音声信号が音響分析部１２でフレームごとに音響分析され、各フレームの音響特徴パラメータがパラメータ記憶部１３に蓄積されている状態から説明を始める。また、前記領域分割部１５４ａにより、図１に示したように、探索空間が、分岐するパタン数が少ない「単語確定領域」および多い「単語未確定領域」に分割されているものとする。
【００５２】
ステップＳ１では、探索処理の初期化として、文法の先頭の単語の先頭の状態に遷移する仮想的な状態仮説が設定される。ステップＳ２では、前記パラメータ記憶部１３に記憶されている音響特徴パラメータが、記音声区間の先頭フレームから正順で取り込まれる。ステップＳ３では、有効な状態仮説の一つが今回の計算対象として選択される。ステップＳ４では自己遷移が実施され、その尤度が計算・更新される。ステップＳ５では、今回のタイミングに対応した全ての状態仮説に関して自己遷移および尤度計算が完了したか否かが判定される。完了していなければステップＳ３へ戻り、今回のタイミングで遷移すべき他の状態仮説についても上記した各処理が繰り返される。
【００５３】
今回のタイミングに対応した全ての状態仮説に関して自己遷移および尤度計算が完了するとステップＳ６へ進み、改めて今回のタイミングに対応した有効な状態仮説の一つが計算対象として選択される。ステップＳ７では各状態仮説がL-R遷移される。ステップＳ８ではViterbi探索が実行される。ステップＳ９では、今回のタイミングで遷移すべき全ての状態仮説に関して、上記したL-R遷移およびViterbi探索が完了したか否かが判定される。完了していなければステップＳ６へ戻り、今回のタイミングで遷移すべき他の状態仮説についても上記した各処理が繰り返される。その後、今回のタイミングで遷移すべき全ての状態仮説について上記した各処理が完了するとステップＳ１０へ進み、領域ごとに枝刈りを独立して行う領域別枝刈り処理が実行される。
【００５４】
図５は、前記領域別枝刈り処理の手順を示したフローチャートであり、ステップＳ１０１では、今回のタイミングに対応した有効な状態仮説の一つが計算対象として選択される。ステップＳ１０２では、前記選択された今回の状態仮説がいずれかの領域に振り分けられる。ステップＳ１０３では、全ての状態仮説に関して前記振り分けが完了したか否かが判定され、完了していなければ、ステップＳ１０１へ戻って上記した振り分け処理が繰り返される。
【００５５】
その後、全ての状態仮説がいずれかの領域に振り分けられると、ステップＳ１０４では、分割された領域の一つが、今回の枝刈り領域として選択される。ステップＳ１０５では、領域内の全ての状態仮説の累積尤度に基づいて枝刈り条件が設定される。ステップＳ１０６では、領域内の状態仮説の一つが今回の枝刈り対象として選択される。ステップＳ１０７では、累積尤度が前記枝刈り条件よりも高い状態仮説のみを残して他の状態仮説を次の探索から除外する枝刈りが行われる。
【００５６】
本実施形態では、時刻t、状態jの各尤度αj(t)を、探索空間の領域ごとに全状態仮説の中で最大の尤度αmax(t)と比較し、次式(7)を満足する状態仮説を次の時刻の探索空間に残し、次式(8)を満足する状態仮説を次の時刻の探索空間から除外する。θpruningはビーム幅であり、前記枝刈り条件設定部１５４ｃは、領域ごとに同一のビーム幅を設定しても良いし、あるいは異なるビーム幅を設定しても良い。
【００５７】
【数５】
0005309343.tif 000006
【００５８】
【数６】
0005309343.tif 000007
【００５９】
なお、上記のように探索空間を、分岐するパタン数が少ない単語確定領域と多い単語未確定領域とに分割するのであれば、単語確定領域の枝刈り条件を単語未確定領域の枝刈り条件よりも厳しくすることにより、認識率を低下させることなく、状態仮説を効率良く枝刈りできるようになる。
【００６０】
ステップＳ１０８では、今回の領域内の全ての状態仮説に関して上記した処理が完了したか否かが判定され、完了していなければ、ステップＳ１０６へ戻って状態仮説を変更しながら上記した各処理が繰り返される。ステップＳ１０９では、全ての領域に関して上記した処理が完了したか否かが判定され、完了していなければステップＳ１０４へ戻り、領域を変更しながら上記した各処理が繰り返される。
【００６１】
図４へ戻り、ステップＳ１１では、枝刈り後に残った状態仮説の一つが選択される。ステップＳ１２では、選択された状態仮説が単語末尾の状態仮説であるか否かが判定され、単語末尾の状態仮説であれば、ステップＳ１３へ進んで単語仮説が出力される。ステップＳ１４では、文法の上の次の単語の先頭の状態に遷移する仮想的な状態仮説が設定される。ステップＳ１５では、枝刈り後に残った全ての状態仮説に関して上記した処理が完了したか否かが判定される。完了していなければ前記ステップＳ１１へ戻り、状態仮説を変更しながら上記した各処理が繰り返される。
【００６２】
ステップＳ１６では、次フレームの有無が判定され、次フレームが存在すればステップＳ２へ戻って次フレームの音響特徴パラメータを取り込んで上記した各処理が繰り返される。
【００６３】
全てのフレームに関して上記した各処理が終了して探索が文末フレームまで到達すると、ステップＳ１７では、これまでに文法上の最後のHMM状態まで到達した全ての状態仮説が、その累積尤度の昇順にソートされる。ステップＳ１８では、累積尤度が上位の複数または唯一の状態仮説にバックトレースが実施され、認識結果が出力される。
【００６４】
なお、上記の実施形態では、本発明を状態仮説がビーム幅に基づいて枝刈りされる場合を例にして説明したが、本発明はこれのみに限定されるものではなく、状態仮説の累積尤度をヒストグラム化し、最大許容仮説数に基づいて枝刈りする場合にも同様に適用できる。
【００６５】
また、上記した実施形態では、本発明を音声認識を例にして説明したが、ゲノム解析におけるタンパク質配列の探索など、他のパタン認識にも同様に適用できる。
【００６６】
さらに、上記の実施形態では探索空間を、分岐するパタン数が少ない単語確定領域および分岐するパタン数が多い単語未確定領域に２分割し、領域ごとに独立して枝刈りを実行するものとして説明したが、本発明はこれのみに限定されるものではなく、探索空間を分岐するパタン数に応じて複数分割できるならば、以下のような規則の一つまたは複数の組み合わせに基づいてに分割しても良い。
【００６７】
(1)図６に示したように、探索空間を、各HMM状態が当該状態以降に分岐して終端の状態に到達するパタンの総数ごとに分割する。このとき、領域ごとに枝刈り条件を異ならせるのであれば、パタン総数が少ない領域ほどビーム幅を狭めて枝刈り条件を厳しくすることが望ましい。図示した例では、第１領域から分岐するパタン総数は７個であり、第２領域から分岐するパタン総数は３個であり、第３領域から分岐するパタン総数は４個である。したがって、ビーム幅や最大許容仮説数が第１領域＞第３領域＞第２領域となり、第２領域の枝刈り条件が最も厳しくなる。
【００６８】
(2)図７に示したように、探索空間を木構造辞書の根の種類（ここでは、単語先頭の音素）に基づいて当該根ごとに複数の領域に分割する。このとき、領域ごとに枝刈り条件を異ならせるのであれば、各グループを同一領域としてグループごとにビーム幅を設定することが望ましい。このような分割方法は、木構造辞書の根の内容に応じて、その後に分岐するパタン総数が特異的であるような場合に有効である。
【符号の説明】
【００６９】
１１…音声信号入力部，１２…音響分析部，１３…パラメータ記憶部，１４…探索データベース，１５…探索部，１６…認識結果判定部，１５１…尤度計算部，１５２…自己遷移部，１５３…LR遷移部，１５４…枝刈り部，１５４ａ…領域分割部，１５４ｂ…状態仮説振り分け部，１５４ｃ…枝刈り条件設定部，１５４ｄ…領域別枝刈り部，１５５…単語仮説出力部
【図１】
0005309343.tif 000008
【図２】
0005309343.tif 000009
【図３】
0005309343.tif 000010
【図４】
0005309343.tif 000011
【図５】
0005309343.tif 000012
【図６】
0005309343.tif 000013
【図７】
0005309343.tif 000014
【図８】
0005309343.tif 000015
【図９】
0005309343.tif 000016
【図１０】
0005309343.tif 000017