(57)【要約】【課題】確率的な有限状態遷移モデルの探索空間における枝刈りで候補集合内に残る状態仮説が当該探索空間において偏在することを避け、適切な間引きを可能とする探索装置を提供する。【解決手段】更新部４００は、入力される信号の所定単位ごとに、モデルを参照して前記候補集合内の各状態仮説を遷移させると共に、その累積尤度を入力信号の特徴パラメータ及びその所定の確率モデルに基づいて更新する。ペナルティ算出部４１０は、遷移された各状態仮説に対して、所定の近傍範囲にある状態仮説との間で累積尤度の比較を行い、累積尤度の低い方の状態仮説に対するペナルティを算出して減算する。枝刈り部４２０は、遷移された各状態仮説に対して、ペナルティを考慮した累積尤度が低い側の所定条件を満たすものを、候補集合内から除外する。【選択図】図１
2014174199.tif 000002
【特許請求の範囲】
【請求項１】
逐次入力される信号から抽出された特徴パラメータに対する最尤な状態遷移パスを、確率的な有限状態遷移モデル内を遷移する状態仮説の候補集合から探索する探索装置において、
前記入力される信号の所定単位ごとに、前記モデルを参照して前記候補集合内の各状態仮説を遷移させると共に、その累積尤度を前記特徴パラメータに基づいて更新する更新部と、
前記遷移された各状態仮説に対して、所定の近傍範囲にある状態仮説との間で累積尤度の比較を行い、累積尤度の低い方の状態仮説に対するペナルティを算出して当該低い方の状態仮説の累積尤度から減算を行うことで、各状態仮説に対するペナルティを考慮した累積尤度を求めるペナルティ算出部と、
前記遷移された全状態仮説のうち、前記ペナルティを考慮した累積尤度が所定条件を満たすものを、前記候補集合内から除外する枝刈り部と、を備えることを特徴とする探索装置。
【請求項２】
前記ペナルティ算出部は、累積尤度を2つの状態仮説間で比較する都度、累積尤度の低い方の状態仮説に対するペナルティを算出し、各状態仮説はペナルティが算出される都度、その値を累積して保持することを特徴とする請求項１に記載の探索装置。
【請求項３】
前記ペナルティ算出部は、状態仮説間の距離に基づく値として前記ペナルティを算出することを特徴とする請求項１または２に記載の探索装置。
【請求項４】
前記ペナルティ算出部は、状態仮説間の距離の非増加関数として前記ペナルティを算出することを特徴とする請求項３に記載の探索装置。
【請求項５】
前記ペナルティ算出部は、隣接する状態仮説間のみを対象としてペナルティの算出を行うことを特徴とする請求項１ないし４のいずれかに記載の探索装置。
【請求項６】
前記ペナルティ算出部は、分岐元に位置する状態仮説については、当該分岐元の所定の近傍範囲にある状態仮説で且つ当該分岐元の分岐先以降に該当する状態仮説の全てとの間で累積尤度の比較を行い、当該比較結果の全てにおいて当該分岐元の累積尤度が低い場合にのみ、当該分岐元のペナルティを算出することを特徴とする請求項１ないし５のいずれかに記載の探索装置。
【請求項７】
前記ペナルティ算出部は、各状態仮説に対して、前記所定の近傍範囲にある状態仮説のうち、当該状態仮説と枝分かれの関係にあるものを、ペナルティの算出対象から除外することを特徴とする請求項１ないし６のいずれかに記載の探索装置。
【請求項８】
前記確率的な有限状態遷移モデルが隠れマルコフモデル又は重み付き有限状態トランスデューサであることを特徴とする請求項１ないし７のいずれかに記載の探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音声認識システムなどのパターン認識システムに利用可能な、確率的な有限状態遷移モデル（隠れマルコフモデルや重み付き状態トランスデューサなど）における探索装置に関する。
【背景技術】
【０００２】
音声認識は、音声波形の背後にある音素シンボルの時系列、ひいては単語の時系列を、予め定義された連鎖可能な単語の繋がりの中から、事後確率最大の基準により選択するプロセスとして定式化されている。
【０００３】
こうした時系列データからその背後にあるシンボル系列を推定・認識する問題には、隠れマルコフモデル（Hidden Markov Model、以降HMMと呼ぶ）や重み付き有限状態トランスデューサ（Weighted Finite State Transducer、以降WFSTと呼ぶ）などの確率的な有限状態遷移モデルが一般的に利用されている。
【０００４】
例として、単純なHMMを図６に示す。時系列データの背後にあるシンボルを有限個の「状態」（図中、「状態１」、「状態２」及び「状態３」を例示）で表現し、各状態は変数として時系列データの特徴量に対する確率密度分布と状態遷移確率を有する。状態遷移は、同一の状態への自己遷移（「状態１」から「状態１」への遷移など）と、異なる状態へのL-R遷移（「状態１」から「状態２」への遷移など）からなるため、時系列データの時間方向の伸縮に柔軟に対応することができる。音声認識を例にとれば、人による声質のばらつきは各状態が有する特徴量に対する確率密度分布によって吸収され、話速のばらつきは自己遷移の回数によって吸収される。
【０００５】
以下、確率的な有限状態遷移モデルとその探索について、HMMに基づく音声認識を例に説明する。図７は、周知の従来技術における音声認識エンジン（音声認識システム）の一例に係る機能ブロック図であり、音声認識エンジン100は図示される各部及び辞書などを備える。
【０００６】
音声認識処理の要旨は次の通りである。パワーなどに基づいて音声区間検出部102によって切り出された音声区間に対して、音響分析部103がMFCC (Mel Frequency Cepstrum Coefficients)などの音響特徴量を抽出する。さらに、単語を単位として文を構成する単語系列を探索する文法／言語モデル探索部106と、音響尤度を累積して尤もらしさ（確率）を算出しながら探索を行う単語辞書探索部105と、が連携動作して、もっとも確率の高い単語系列を求める。ここで、音響尤度については、言語モデルの構成要素である様々な単語を対象として、音響特徴量を用いて音響尤度計算部104が計算しておく。以下、各部の個別処理を説明する。
【０００７】
入力音声取込部101は、マイクから波形信号を取り出し、音声区間検出部102へと出力する。
【０００８】
音声区間検出部102は、時系列の波形信号を入力として、短時間のパワーや零交差数を逐次計算し、閾値処理などによって一発声の音声区間を切り出して、音声区間の波形信号を音響分析部103へと出力する。
【０００９】
音響分析部103は、音声区間の波形信号を入力として、音響分析を行い、MFCCなどの音響特徴量の時系列データを音響尤度計算部104へと出力する。当該時系列データの各時点における値をフレームと呼ぶこととすると、音声認識エンジン100では当該フレームごとに、逐次的に認識処理が実行される。
【００１０】
音響尤度計算部104は、音響特徴量を入力として、音響モデル114が状態毎に定義する音響特徴量空間中の確率密度分布と照合し、音響尤度を単語辞書探索部105へと出力する。
【００１１】
探索に関しては、文法／言語モデル探索部106と単語辞書探索部105との２段階が存在して、以下のように当該２段階が連携しながら探索が実行される。
【００１２】
第一に、文法／言語モデル探索部106が、文法もしくは確率言語モデル116を参照して、文頭の無音から単語系列の探索を行う。当該探索結果によって単語辞書探索部105に対して探索対象の単語を指定し、単語辞書探索部105から指定単語の探索終了の通知を受けると、次の時刻に後続する単語の探索を単語辞書探索部105に指示する。
【００１３】
図１０は、文法の例である。文法の場合は、図１０のように単語の並びが与えられる。確率言語モデルの場合は、単語の並びの替わりに、先行単語のもとでの後行単語の条件付き確率という形で与えられる。なお、「sil」は無音を表しており、その他の図（後述の図８及び９）においても同様とする。
【００１４】
なお、上記確率言語モデルを用いた場合の音声認識ではさらに、文法／言語モデル探索部106及び単語辞書探索部105の連動処理として、以下説明する累積尤度に確率言語モデルの尤度が加算されることとなるが、図７に関する以下の説明では煩雑となるので、その旨への言及は省略する。
【００１５】
第二に、単語辞書探索部105は、文法／言語モデル探索部106に指定された単語について、音響尤度計算部104が出力する状態毎の音響尤度を累積しながら木構造辞書115内の探索を行う。一定時間の後、単語終端の状態まで探索が進むと、単語の探索の終了とその累積尤度を文法／言語モデル探索部106に通知して、前述のように新たな単語の指示を受ける。
【００１６】
認識結果出力部107は、一連の音声区間の探索処理が終わると、文法／言語モデル探索部106にて得られている結果のうち、累積尤度がもっとも高い単語系列を認識結果として出力する。
【００１７】
以下、単語辞書探索部105による木構造辞書115内の単語探索と、その課題について説明する。
【００１８】
当該探索の際、各単語は状態系列として表現される。多くの場合、単語をその読みに従って音素系列に分解し、それぞれの音素について用意された音素HMMを連結して単語の状態系列を構成する。こうすると、図８に示すような各単語について一直線状の状態系列となる。これをリニア辞書という。図８では、音素HMMの自己遷移は描くのを省略している。
【００１９】
単語の探索は、状態系列に対するビタービ（Viterbi）アルゴリズムによって実行される。認識結果の候補の1つである仮説が、開始時刻（1つ前の単語の終了時刻の次の時刻）に状態系列の先頭の状態に入り、ある時刻（終了時刻）に状態系列の末尾の状態から出る。ビタービアルゴリズムは、仮説が状態系列に入った時刻から出た時刻までの、音響特徴量の系列と状態系列の音響的特徴との一致度を、確率値として出力する。
【００２０】
正確には、この確率値は対数化した尤度（L = log P）で表現される。これを「音響尤度」と呼び、前述の音響尤度計算部104にて計算される。認識処理の途中において、単語は確定でないから、様々な単語の状態系列に対して同時並行してビタービアルゴリズムが実行される。すなわち、様々な単語の状態系列の状態のそれぞれに、その時点までの音響尤度を保存した仮説が一時記憶される。この仮説を「状態仮説」と呼ぶ。
【００２１】
実際の音声認識では、膨大な種類に及ぶ単語系列を探索するために状態仮説の数は膨大になる。しかし、探索処理に要する演算量および時間は、状態仮説の数に比例するため、探索の効率性を向上するには精度を落とさずに状態仮説の数を削減することが求められる。状態仮説の数を節約するために、異なる単語間で先頭から共通の部分状態系列をマージする。異なる単語間でも同時刻に共通の部分状態系列の探索を開始すれば、共通部分の各状態の音響尤度は等しいからである。
【００２２】
このマージにより、図９に示すような木構造辞書が形成される。単語辞書探索部105が探索する木構造辞書115は、このように木構造としてマージされたものである。なお、図９の例は、図８の例に対応しており、同じく音素HMMの自己遷移については描くのを省略している。
【００２３】
認識対象語彙の木構造辞書化を行ってもなお、そのままでは音声が逐次入力されていくにつれて、状態仮説数は爆発的に増大してしまう。そこで、単語辞書探索部105は通常、毎時刻全状態仮説の尤度を比較し、尤度の高い状態仮説だけを次の時刻の探索に残し、尤度の低い状態仮説は探索途中で破棄する「仮説枝刈り」の処理を行う。
【００２４】
代表的な仮説枝刈り手法としては、全状態仮説中の最大尤度から一定の尤度幅以内にある状態仮説を残す尤度幅による枝刈り、尤度の高い状態仮説から一定個数の状態仮説を残すために、全状態仮説を尤度に基づいてヒストグラムの階級に分類し、尤度の高い階級から累積個数が一定値を超えるまで残すヒストグラムによる枝刈りがある。一般的には両手法を併用し、これをビーム探索と呼ぶ。
【００２５】
非特許文献1には、HMMにおける代表的な仮説枝刈り手法とその効果が、dynamic network decoderにおける仮説枝刈りとして解説されている。
【００２６】
非特許文献2は、木構造辞書の探索効率を改善するために、仮説が木構造辞書上で到達しうる単語の数に応じて枝刈りの厳しさを制御する手法を提案している。具体的には、木構造辞書のルートに近い状態にある状態仮説に対して枝刈を甘く、リーフに近い状態にある状態仮説に対して枝刈りを厳しくするため、状態仮説の累積尤度に木構造辞書における到達可能単語数に応じた報酬値を一時的に加算した値を用いてビーム探索を行う。
【先行技術文献】
【非特許文献】
【００２７】
【非特許文献１】D. Nolden, R. Schluter and H. Ney, "Extended Search Space Pruning in LVCSR," Proceedings of ICASSP 2012 (2012)
【非特許文献２】T. Kato, K. Fujita and N. Nishizawa, "An Efficient Beam Pruning with a Reward Considering the Potential to Reach Various Words on a Lexical Tree" Proceedings of ICASSP 2010 (2010)
【発明の概要】
【発明が解決しようとする課題】
【００２８】
上記のような従来技術に係る枝刈りにより、確率的な有限状態遷移モデルの探索空間における状態仮説総数は削減され、探索の効率化は進められている。ただし、結果的に残った状態仮説は探索空間の限られた部分に偏在することが多い。偏在する状態仮説は結果的に同一の単語終端に似たような時刻に辿りつく可能性が高く、これは更なる探索効率改善の余地がある。
【００２９】
当該課題に鑑み、本発明は、いわば密集した状態仮説を適度に間引くことによって、探索のさらなる効率化を達成することができる、確率的な有限状態遷移モデルにおける探索装置を提供することを目的とする。
【課題を解決するための手段】
【００３０】
上記目的を達成するため、本発明は、逐次入力される信号から抽出された特徴パラメータに対する最尤な状態遷移パスを、確率的な有限状態遷移モデル内を遷移する状態仮説の候補集合から探索する探索装置において、前記入力される信号の所定単位ごとに、前記モデルを参照して前記候補集合内の各状態仮説を遷移させると共に、その累積尤度を前記特徴パラメータに基づいて更新する更新部と、前記遷移された各状態仮説に対して、所定の近傍範囲にある状態仮説との間で累積尤度の比較を行い、累積尤度の低い方の状態仮説に対するペナルティを算出して当該低い方の状態仮説の累積尤度から減算を行うことで、各状態仮説に対するペナルティを考慮した累積尤度を求めるペナルティ算出部と、前記遷移された全状態仮説のうち、前記ペナルティを考慮した累積尤度が所定条件を満たすものを、前記候補集合内から除外する枝刈り部と、を備えることを特徴とする。
【発明の効果】
【００３１】
本発明によれば、候補集合内の状態仮説を更新する各段階において、各状態仮説に対してその近傍範囲にある状態仮説と累積尤度の比較を行い、低い側にペナルティを算出し、累積尤度から算出されたペナルティを減じたものを枝刈り用のスコアとして用いて、枝刈りを実施する。従って、近傍にあって累積尤度の低いものが、状態仮説の密集箇所に存在し且つ間引くのに適切なものとして自動的に枝刈り対象として選定されることとなり、より少ない状態仮説数で最尤の状態系列を発見する探索効率性を向上することができる。
【図面の簡単な説明】
【００３２】
【図１】一実施形態に係る探索装置を含む音声認識システムの機能ブロック図である。
【図２】一実施形態に係る探索装置の処理のフローチャートである。
【図３】状態遷移の例を示す図である。
【図４】状態遷移の例を示す図である。
【図５】状態遷移の例を示す図である。
【図６】HMM(隠れマルコフモデル)の例を示す図である。
【図７】従来技術における音声認識エンジンの一例に係る機能ブロック図である。
【図８】リニア辞書の例を示す図である。
【図９】木構造辞書の例を示す図である。
【図１０】文法を説明するための図である。
【発明を実施するための形態】
【００３３】
以下、本発明の探索装置の要旨を説明してから、具体的な実施形態の説明を行うこととする。
【００３４】
仮説枝刈りの基本的な考え方は、探索途中の各時刻において見込みの高い状態仮説を次の時刻の探索に残し、見込みの低い状態仮説を次の時刻の探索対象から外すことである。ここで、見込みとして累積尤度を用いている。本発明では、この仮説枝刈りに、状態仮説の密集度に応じた仮説の間引き効果を導入するために、状態仮説の密集度に応じたペナルティを導入する。仮説枝刈りの手法自体は、上記従来技術の各種のものを利用することができるが、本発明ではその際に見込みとして用いる累積尤度に、さらにペナルティが付与される。
【００３５】
すなわち、本発明における確率的な有限状態遷移モデルの探索装置では、その枠組みとしては従来技術のビタービアルゴリズムに従って、認識対象信号の毎フレーム全状態仮説について自己遷移とL-R遷移を行い、累積尤度を更新する。このとき、本発明では特に、探索候補として残っている各状態仮説において、近くの状態に位置する状態仮説と累積尤度を比較し、低い方の状態仮説の累積尤度にペナルティを算出しておく。こうして、枝刈りの際に、周囲の状態仮説に較べて累積尤度が相対的に低い状態仮説には多くのペナルティが与えられるようになるため、枝刈り対象になりやすく、間引き効果がもたらされる。
【００３６】
ただし、ペナルティが与えられた累積尤度（ペナルティを考慮した累積尤度）はあくまで仮説枝刈りの専用のスコアと位置付け、状態仮説の累積尤度とは別に格納する。これによって、確率的な探索のフレームワーク（ビタービアルゴリズムの枠組み）自体は崩されずに保たれる。当該ペナルティの詳細は、以下の実施形態において説明する。
【００３７】
図１は、一実施形態として、探索装置を音声認識システムに利用する場合の、当該音声認識システムの機能ブロック図である。音声認識システム10は、音声信号入力部1、音響分析部2、文法／確率言語モデル探索部3、探索装置4、単語仮説出力部5、バックトレース部6、認識結果表示部7、記述文法／確率言語モデル30、木構造辞書40、音響モデル45及び単語仮説集合50を備える。
【００３８】
探索装置4は、一実施形態では、更新部400、ペナルティ算出部410及び枝刈り部420を備え、更新部400は音響尤度計算部401、自己遷移部402、LR遷移部403、言語尤度加算部404及びビタービ処理部405を含む。別の実施形態では、探索装置4は当該音声認識システム10内のその他の機能ブロックをさらに含んで構成されていてもよい。
【００３９】
以下、当該音声認識システム10内の探索装置4として本発明を説明するが、音声以外のその他一般の認識対象であっても、確率的な有限状態遷移モデルの探索過程を有する任意の対象について、探索装置4を適用することができる。例えば、音声以外の信号を認識する場合は、音響分析部2、音響尤度計算部401及び音響モデル45を当該信号に対応するものに置き換え、その他の確率的な有限状態遷移モデル関連の構成も、当該信号に対応するものに置き換えればよい。なおまた、探索装置4は各認識対象に応じた付随構成をさらに含んでいてもよい。
【００４０】
音声信号入力部1は、図7の入力音声取込部101及び音声区間検出部102の機能を有し、音響分析部2は、図7の音響分析部2と同様であるので、これらの説明は省略する。こうして、文法／確率言語モデル探索部3以降へと、入力音声より抽出された特徴ベクトル等の音響特徴パラメータが時系列（当該時系列の各要素をフレームと称する）として、順次入力されることとなる。
【００４１】
文法／確率言語モデル探索部3及び記述文法／確率言語モデル30は、図7の文法／言語モデル探索部106及び文法／確率言語モデル116と同様である。文法／確率言語モデル探索部3は、単語仮説出力部5の出力する単語を単位として、文を構成する単語系列を記述文法／確率言語モデル30（文法モデル又は確率言語モデル）より探索して、探索装置4へ渡す。
【００４２】
探索装置4は、図7の音響尤度計算部104及び単語辞書探索部105の処理を、本発明におけるペナルティを交えながら担う。更新部400は、音響分析部2から逐次入力されるフレームに対して、ビタービアルゴリズムによる探索過程の中で状態仮説集合の更新（状態仮説の遷移及びその累積尤度の更新）を逐次行う。
【００４３】
音響尤度計算部401は、音響モデル45及び木構造辞書40（図７の音響モデル114及び木構造辞書115と同様）を参照して、状態仮説の当該時点におけるフレームの音響特徴量に対する音響尤度を計算する。
【００４４】
自己遷移部402は、当該フレームごとの探索過程にて各状態仮説を自己遷移させると共に、上記音響尤度を加算することで累積尤度を更新する。LR遷移部403は、当該フレームごとの探索過程にて各状態仮説をLR遷移させると共に、上記音響尤度を加算することで累積尤度を更新する。こうして、t番目のフレームの時点にて状態jにある状態仮説の累積尤度をαj(t)とすると、以下の式のように累積尤度がその前の(t−1)番目の値から更新される。
【００４５】
【数１】
2014174199.tif 000003
【００４６】
なお、上記(式1)において、ai,jは木構造辞書40を参照して得られる状態iから状態jへの遷移確率であって、i=jの場合が自己遷移に対応する。bj(ot)は状態jが音響特徴量otを出力する確率であり、尤度として音響尤度計算部401が算出する。
【００４７】
なおまた、記述文法／確率言語モデル30において、確率言語モデルを利用する場合には、言語尤度加算部404がさらに当該モデルにおける尤度の加算を行うことで累積尤度が更新される。
【００４８】
ビタービ処理部405は、上記自己遷移及びLR遷移して累積尤度を更新された状態仮説において、上記自己遷移又はLR遷移の結果同じ状態jに至ったものがある場合、以下の(式2)に従って累積尤度の最も高い状態仮説を残すビタービ探索の処理を行う。なお、(式2)は(式1)の場合の累積尤度に対応している。
【００４９】
【数２】
2014174199.tif 000004
【００５０】
ペナルティ算出部410は、当該t番目のフレームにおいて上記更新部400が更新を行った後の状態仮説に対して、詳しくは後述するペナルティを算出する。枝刈り部420は、当該t番目のフレームにおいて上記更新部400が更新を行った後の状態仮説集合において、ペナルティ算出部410が算出したペナルティを加味して、枝刈りを実施し、当該枝刈りを逃れた状態仮説の集合が、次のt+1番目のフレームの入力に対して、継続して探索装置4での処理対象となる。
【００５１】
単語仮説出力部5は、上記探索装置4のフレームtにおける枝刈り後の状態仮説集合を当該フレームtにおいて監視し、単語末尾まで進んだ状態仮説の単語仮説を、単語仮説集合50を参照して出力する。当該末尾まで進んだ状態仮説は、文法／確率言語モデル探索部3によって新たに探索を開始する単語を決定し、次のt+1番目のフレームにおいて上記探索装置4で探索する状態仮説を設定する。
【００５２】
バックトレース部6は、無音状態の継続などにより一連のフレーム入力が終了した旨が判定された場合に、単語仮説集合50のうち文法上の最後のノードまで到達したものの中から累積尤度の最も高い単語仮説を基点にバックトレースを実行して認識結果を判定する。認識結果表示部7は当該認識結果を表示する。
【００５３】
図２は、一実施形態に係る探索装置4の探索処理のフローチャートである。まず、当該フローの全体構造として、ステップS110〜S145が、制御ステップS150によって、探索装置4に逐次読み込まれるフレームt（t=1, 2, 3, ...）ごとに実行される。当該全体構造自体は、ビタービアルゴリズムの枠組みに即したものであり、最初のフレームt=1より、当該フローが開始される。
【００５４】
また、当該フローに従って、木構造辞書40内において到達している状態仮説の集合が順次更新されるので、その旨を明示すべく、当該順次更新される状態仮説集合41を図２において併記して描いている。状態仮説集合41に対する点線の矢印はフローの流れではなく、各ステップにおける状態仮説集合41の更新／参照処理の存在を表している。単語仮説集合50の併記も同様である。
【００５５】
ステップS110では、集合内の状態仮説に対して、自己遷移部402により自己遷移が行われると共に、当該フレームtの当該自己遷移後の音響尤度を音響尤度計算部401が算出し、自己遷移部402はさらに、(式1)のように当該音響尤度を加算してその累積尤度を更新する。ステップS115では、ステップS110の処理が集合内の全状態仮説について完了したか判断され、未完了であれば未処理の状態仮説を対象としてステップS110を継続し、完了していればステップS120に移る。
【００５６】
ステップS120では、集合内の状態仮説に対して、LR遷移部403によりL-R遷移が行われると共に、当該フレームtの当該L-R遷移後の音響尤度を音響尤度計算部401が算出し、LR遷移部403はさらに、(式1)のように当該音響尤度を加算してその累積尤度を更新し、ステップS125へ移る。
【００５７】
ステップS125は、確率言語モデルを使用する場合に実行されるステップであり、言語尤度加算部404が確率言語モデル30を参照して、ステップS120の累積尤度に、到達可能な単語のうち最大の言語尤度を加算することで更新し、ステップS130へ移る。確率言語モデル未使用時は、ステップS120からただちにステップS130へ移る。
【００５８】
ステップS130では、当該ステップS120(及びS125)で処理対象となった当該LR遷移後の状態仮説について、当該フレームtにおけるステップS110での自己遷移後の状態仮説と一致するものが存在する場合に、ビタービ処理部405によって累積尤度を比較し、大きい方を集合内に残し、ステップS135へ移る。
【００５９】
ステップS135では、当該ステップS120〜S130で処理対象となった状態仮説について、ペナルティ算出部410が、当該状態仮説に近い距離にある集合内の状態仮説との間で累積尤度を比較し、低い側の状態仮説に対するペナルティを算出すると共に当該低い側の累積尤度から減算して、ステップS140へ移る。ステップS140では、集合内の全状態仮説につき、以上のステップS120〜S135の処理が完了したか判断され、未完了であればステップS120に戻って未処理の状態仮説を対象として処理が継続され、完了であればステップS145へ移る。
【００６０】
なお、当該ステップS135における累積尤度の比較及び低い側へのペナルティ算出・減算の処理は、各フレームtの全ての２つの状態仮説の間において、1回のみ行えばよい。例えば状態仮説i及びjがあり、iを対象としたステップS135にてiから見て近い距離にあるjにつき当該処理がなされた場合、その後のjを対象としたステップS135にてjから見て近い距離にiがある場合には、同じペナルティが重複することとなるため、当該iを対象とした処理を省略してよい。
【００６１】
ステップS145では、集合内の各状態仮説に対して、その累積尤度より、自身に対してステップS135で算出されたペナルティを減じた値を、当該状態仮説を枝刈り対象とするか否かの評価値として定義して利用することにより、枝刈り部420が枝刈りを実施して、集合を更新し、ステップS150へと進む。枝刈りの対象となった状態仮説は、集合から除外される。
【００６２】
なお、ペナルティが算出されなかった状態仮説においては、その累積尤度がそのまま、枝刈りの際の評価値となるので、ペナルティの値がゼロであるとみなしてもよい。こうして、本発明では、ペナルティを考慮した累積尤度（ペナルティが算出されれば累積尤度から減算した値、算出されなければ減算しない値）を評価値として、枝刈りが実施される。また前述のように、当該ペナルティはビタービアルゴリズムの探索枠組みにおいては利用されない。
【００６３】
ステップS150では、当該フレームtの次の処理対象フレームt+1の有無が判定され、次の対象が存在すれば、ステップS110に戻って処理は継続される。なお、当該戻る際に、前述の単語仮説出力部5及び文法／確率言語モデル探索部3の処理も行われ、単語終端に達した状態仮説があった場合は集合が更新されるが、図2は主に探索装置4における処理フローであるので、当該処理は描くのを省略している。無音状態の継続などで、次の対象フレームが存在しなければ、ステップS155へ移り、前述のバックトレース部6の処理によって、最終的な認識結果を得て、フローは終了する。
【００６４】
以上の図2のフローの別の実施形態として、ステップS135がステップS140とS145との間に配置されていてもよい。（当初の位置からステップS135は削除され、ステップS130後はステップS140へ移る。）この場合も、集合内の全状態仮説について処理が完了するまで、当該別配置されたステップS135が継続して実行される。
【００６５】
以下、ステップS135にてペナルティ算出部410が算出するペナルティの詳細に関し、特に、その値と、累積尤度を比較する範囲と、の各種の実施形態について説明する。いずれかを択一的に適用する関係にない実施形態同士については、適宜組み合わせが可能である。図3〜図５は当該説明のための状態仮説間の状態遷移の例であり、適宜参照する。
【００６６】
枝刈りの際の評価スコアに、累積尤度からペナルティを減じたものが利用される。従って、当該ペナルティの値は、状態仮説の密集度の高い場所に高いペナルティを付与するという意味では、累積尤度を比較している状態仮説間の距離dに応じた正の値p(d)とし、dに関する単調減少関数（あるいは非増加関数）として与えてもよい。
【００６７】
すなわち、p(1)≧p(2)≧p(3)≧…である。状態仮説間の距離dとは、2つの状態仮説が位置する状態間を移動するのに必要なL-R遷移の(最小)回数とし、本来のL-R遷移を逆に辿る場合も含めてよい。例えば、図５のような状態仮説（の位置する状態）f,g,hであれば、f−g間の距離は1、f−h間の距離は1、g−h間の距離は2となる。
【００６８】
あるいは、状態仮説間の距離dによらず、一定の正の値p(d)＝pをペナルティの値として用いてもよい。
【００６９】
各状態仮説につき、自身の所定の近傍範囲にある状態仮説との間で、累積尤度を比較して、低い側に対してペナルティが算出される。当該近傍範囲の設定については、上記定義の距離dが所定値以内であるものとしてもよい。自身の所定近傍に状態仮説がn個(n≧2)ある場合は、自身と、所定近傍のn個の状態仮説の各々の間で、合計n回の累積尤度比較処理及び低い側へのペナルティ算出処理が、その都度なされる。従って、各状態仮説においては、ペナルティが算出される都度、ペナルティ値を累積して保持することとなる。
【００７０】
例えば、距離d=1の近傍、すなわち隣接する状態仮説間のみで累積尤度を比較するものとし、図4のような状態仮説c,d,eがあって、dが当該3者の中で最低の累積尤度であったとすると、dには次のように累積したペナルティが付与される。すなわち、cと比較された1回と、eと比較された1回と、合計2回のペナルティが付与される。従って、当該距離1のペナルティ値をPとすると、この場合の状態仮説cのペナルティ値は2Pとなる。
【００７１】
このような累積ペナルティ付与によって、状態仮説の密集箇所に自動的に高いペナルティが与えられる効果がある。特に、距離1や2の近い状態に同じ終端状態に辿り着く状態仮説が密集する部分では、1つの状態仮説について近傍の複数の状態仮説と累積尤度の比較が行われ、累積尤度の低い状態仮説にはその度にペナルティが与えられることとなる。
【００７２】
ただし、当該累積ペナルティは、図２で説明したような各フレームtの枝刈り実施においてのみ有効である。フレームtにおける状態仮説が自己遷移又はLR遷移してフレームt+1における状態仮説となる際に、当該過去フレームtで算出されていたペナルティの情報は消失する。
【００７３】
また、本発明は、似た時刻に同一の終端状態に辿り着く可能性があるものを間引くことを目的としている。従って、一実施形態においては、異なる終端状態に辿り着くものとの間では、ペナルティを算出しないようにしてもよい。例えば、図５の状態仮説gにおいて距離2以内の近傍にある状態仮説同士との間で累積尤度を比較する場合に、状態仮説hは距離2の近傍に存在しているが、状態仮説gとは異なる終端状態に向かうものであるため、ペナルティ算出対象から除外する。
【００７４】
なお、状態仮説i,j間の距離を求める際に、LR遷移を逆に辿る箇所が存在する場合は、当該状態仮説i,jは何らかの状態仮説から異なるLR遷移で枝分かれしたものであり、異なる終端に辿り着くものであることを意味している。従って、当該枝分かれの情報またはLR遷移を逆行して辿り着く関係にある情報に基づいて、上記ペナルティ算出対象からの除外判断を行うことができる。
【００７５】
上記枝分かれ（分岐）に関しては、有限状態遷移モデルにおいてよく現れるものである。この場合に、分岐の片方での状態仮説間の累積尤度比較で、分岐元の状態仮説が枝刈り対象となると、仮説が分岐のもう片方に発展する可能性を不適切に失ってしまい、探索精度を落としてしまう可能性がある。すなわち、本来は間引いてはならない箇所を間引いてしまう可能性がある。
【００７６】
例えば、図５のようなfからg及びhに分岐する関係において、信号認識の途中における枝刈り処理によってh側へ至った以降の状態仮説のみが残ったとすると、信号全体での本来の状態系列がg側への分岐であったとしても、もはや正解は得られないこととなる。
【００７７】
従って、一実施形態においては、このように分岐している場合に、分岐の全てのL-R遷移について近い距離の状態仮説間の累積尤度比較を行い、全てのL-R遷移について遷移元の累積尤度が小さい場合のみ、遷移元の累積尤度にペナルティを与えてもよい。
【００７８】
すなわち、分岐箇所に該当する状態仮説については、自身と、その所定近傍に属し且つ自身からの分岐後の状態仮説であるものの各々(分岐後さらにLR遷移するものも含む)n個と、の累積尤度比較を行い、当該n個の比較結果が全て、自身の累積尤度が低いという結果であった場合のみに、通常の実施形態と同様にして当該分岐箇所の状態仮説のペナルティを算出する。
【００７９】
上記n個の比較結果のうち１つでも自身の累積尤度が高いという結果があった場合は、当該分岐箇所に該当する状態仮説については、他の状態仮説から見て近傍範囲として比較される場合を含め、一切のペナルティを付与しないようにする。
【００８０】
さらに、近傍範囲を限定する実施形態として、次がある。近傍を定める距離dが大きいと、近い距離にある状態仮説の数が膨大となり、当該状態仮説を見つけ出すこと自体に時間を要することとなり、状態仮説数削減の意味がなくなるため、あまり離れた距離にある状態仮説は比較対象としない。すなわち、近傍を定める距離dは小さいほうがよい。
【００８１】
もっとも単純な実施形態として、d=1として、隣接する状態仮説間のみに限定してもよい。すなわち、図３に示すように、L-R遷移の遷移元の状態aと遷移先の状態bの更新後の累積尤度を比較して、低い方の累積尤度にペナルティを与えるようにしてもよい。この場合のペナルティの値は、距離1に対応するペナルティである。この場合には、ペナルティを与えるために近い距離にある仮説を探索する処理が省けるので、演算量の増加がほとんどなく、従来のビタービアルゴリズムの枠組みの中で非常に簡素な付随処理として実施することが可能である。
【００８２】
以上のような各実施形態により算出されたペナルティを用いて、枝刈り部420は枝刈りを実施することができる。各状態仮説の累積尤度から、累積算出されたペナルティ(算出されず、ゼロである場合を含む)を減じて得られる、ペナルティを考慮した累積尤度を枝刈り用のスコアとして、当該スコアの低い側の所定条件を満たすものを枝刈り対象として選定する際には、従来技術の各種の枝刈り手法が適用可能である。
【符号の説明】
【００８３】
10…探索装置、400…更新部、410…ペナルティ付与部、420…枝刈り部
【図１】
2014174199.tif 000005
【図２】
2014174199.tif 000006
【図３】
2014174199.tif 000007
【図４】
2014174199.tif 000008
【図５】
2014174199.tif 000009
【図６】
2014174199.tif 000010
【図７】
2014174199.tif 000011
【図８】
2014174199.tif 000012
【図９】
2014174199.tif 000013
【図１０】
2014174199.tif 000014