(57)【要約】【課題】従来よりも探索誤りの危険性が小さい経路探索技術、音声認識装技術を提供する。【解決手段】仮説更新部６が仮説の枝刈をする際に、仮説素性抽出部６１が各仮説についての素性を抽出する。仮説枝刈判別値算出部６２が素性を入力として仮説を排除するか否かの指標を出力する判別関数に抽出された素性を入力した場合の出力値を算出してその各仮説についての判別値とする。仮説枝刈判定部６３が判別値が所定の閾値より大きいかどうかを判定して、大きい場合には、上記判別値に対応する仮説を仮説の集合から除く。仮説の累積重み以外の属性、例えばどのノードに到達したか、どのアークを通ったか等の素性を用いることでより正確な枝刈判定を行うことができ、探索誤りの危険性を従来よりも小さくすることができる。【選択図】図１
2011048255.tif 000002
【特許請求の範囲】
【請求項１】
始点ノード及び終点ノードを含む複数のノードと、ノードを結び、重みとラベルが付されたアークとにより構成される有向グラフの上記始点ノードから上記終点ノードに至る複数の経路の中で、有限長の入力系列に適合する経路を見つける経路探索装置において、
始点ノードからあるノードに至る１つの経路を仮説として、最初に始点ノードに到達した仮説を仮説の集合とする初期仮説生成部と、
上記入力系列の要素を順次読み込む入力系列読込部と、
仮説の集合に含まれる各仮説に、その各仮説の到達した最後のノードから遷移可能な各アークと、その各アークの遷移先のノードとを加えて、その各仮説から複数の新たな仮説を生成し、その各仮説の累積重みと、その各アークの重みと、その各アークのラベルと読み込まれた入力系列の要素との距離とを加えた値を上記新たな仮説の累積重みとして、上記仮説の集合を上記新たな仮説を仮説の集合で置き換える仮説更新部と、
更新された仮説の集合の中で累積重みが大きい又は小さい仮説をその集合から除く仮説枝刈部と、
終点ノードに到達している仮説を完全仮説として、上記入力系列の読み込む要素がなくなった後に、仮説の集合に含まれる完全仮説の中で累積重みが小さい又は大きい１つ以上の完全仮説を出力する完全仮説出力部と、を含み、
上記仮説枝刈部は、その各仮説についての素性を抽出する仮説素性抽出部と、素性を入力として仮説を排除するか否かの指標を出力する判別関数に上記抽出された素性を入力した場合の出力値を算出してその各仮説についての判別値とする仮説枝刈判別値算出部と、上記判別値が所定の閾値より大きいかどうかを判定して大きい場合には上記判別値に対応する仮説を仮説の集合から除き、又は、上記判別値が所定の閾値より小さいかどうかを判定して小さい場合には上記判別値に対応する仮説を仮説の集合から除く仮説枝刈判定部と、を含む、
ことを特徴とする経路探索装置。
【請求項２】
請求項１に記載の経路探索装置において、
累積重みの小さな完全仮説ほど完全仮説の経路上の仮説についての判別値が小さくなるように、又は、累積重みの大きな完全仮説ほど完全仮説の経路上の仮説についての判別値が大きくなるように、上記判別関数を更新する仮説枝刈判別関数更新部を更に含む、
ことを特徴とする経路探索装置。
【請求項３】
請求項１又は２に記載の経路探索装置において、
上記仮説の素性は、その仮説の累積重みとその仮説が含まれる仮説の集合における最小又は最大の累積重みに一定値を加えた又は引いた値との差と、その仮説の上記現在の仮説の集合における累積重みが小さい又は大きい順の順位から一定値を減算した値と、その仮説が到達した最後のノード番号と、その仮説が到達した最後のアーク番号とを示す素性ベクトルであり、
上記判別関数は、素性ベクトルと、素性ベクトルと同じ次元のパラメータベクトルとの内積を求める関数である、
ことを特徴とする経路探索装置。
【請求項４】
請求項１から３の何れかに記載の経路探索装置を含み、
上記入力系列の要素は、音声信号の短時間スペクトル解析によって与えられる特徴ベクトルであり、
上記ラベルは、音素や隠れマルコフモデルの状態等の音響パターンに相当するラベルであり、
上記ラベルと上記入力系列の要素との距離は、ラベルに対応する音素の平均的な特徴ベクトルからのユークリッド距離又は隠れマルコフモデルの状態に割り当てられた確率密度関数から算出される対数尤度であり、
言語として許される音素のつながりを表現する有向グラフから、入力音声に最も適合する経路を探索し、その結果として得られる経路上のラベル列を音声認識の結果とする、
ことを特徴とする音声認識装置。
【請求項５】
始点ノード及び終点ノードを含む複数のノードと、ノードを結び、重みとラベルが付されたアークとにより構成される有向グラフの上記始点ノードから上記終点ノードに至る複数の経路の中で、有限長の入力系列に適合する経路を見つける経路探索方法において、
初期仮説生成部が、始点ノードからあるノードに至る１つの経路を仮説として、最初に始点ノードに到達した仮説を仮説の集合とする初期仮説生成ステップと、
入力系列読込部が、上記入力系列の要素を順次読み込む入力系列読込ステップと、
仮説更新部が、仮説の集合に含まれる各仮説に、その各仮説の到達した最後のノードから遷移可能な各アークと、その各アークの遷移先のノードとを加えて、その各仮説から複数の新たな仮説を生成し、その各仮説の累積重みと、その各アークの重みと、その各アークのラベルと読み込まれた入力系列の要素との距離とを加えた値を上記新たな仮説の累積重みとして、上記仮説の集合を上記新たな仮説を仮説の集合で置き換える仮説更新ステップと、
仮説枝刈部が、更新された仮説の集合の中で累積重みが大きい又は小さい仮説をその集合から除く仮説枝刈ステップと、
完全仮説出力部が、終点ノードに到達している仮説を完全仮説として、上記入力系列の読み込む要素がなくなった後に、仮説の集合に含まれる完全仮説の中で累積重みが小さい又は大きい１つ以上の完全仮説を出力する完全仮説出力ステップと、を含み、
上記仮説枝刈ステップは、その各仮説についての素性を抽出する仮説素性抽出ステップと、素性を入力として仮説を排除するか否かの指標を出力する判別関数に上記抽出された素性を入力した場合の出力値を算出してその各仮説についての判別値とする仮説枝刈判別値算出ステップと、上記判別値が所定の閾値より大きいかどうかを判定して大きい場合には上記判別値に対応する仮説を仮説の集合から除き、又は、上記判別値が所定の閾値より小さいかどうかを判定して小さい場合には上記判別値に対応する仮説を仮説の集合から除く仮説枝刈判定ステップ部と、を含む、
ことを特徴とする経路探索方法。
【請求項６】
請求項５に記載の経路探索方法において、
累積重みの小さな完全仮説ほど完全仮説の経路上の仮説についての判別値が小さくなるように上記判別関数を更新し、又は、累積重みの大きな完全仮説ほど完全仮説の経路上の仮説についての判別値が大きくなるように上記判別関数を更新する仮説枝刈判別関数更新ステップを更に含む、
ことを特徴とする経路探索方法。
【請求項７】
請求項５又は６に記載の経路探索方法において、
上記仮説の素性は、その仮説の累積重みとその仮説が含まれる仮説の集合における最小又は最大の累積重みに一定値を加えた又は引いた値との差と、その仮説の上記現在の仮説の集合における累積重みが小さい又は大きい順の順位から一定値を減算した値と、その仮説が到達した最後のノード番号と、その仮説が到達した最後のアーク番号とを示す素性ベクトルであり、
上記判別関数は、素性ベクトルと、素性ベクトルと同じ次元のパラメータベクトルとの内積を求める関数である、
ことを特徴とする経路探索方法。
【請求項８】
請求項５から７の何れかに記載の経路探索方法を含み、
上記入力系列の要素は、音声信号の短時間スペクトル解析によって与えられる特徴ベクトルであり、
上記ラベルは、音素や隠れマルコフモデルの状態等の音響パターンに相当するラベルであり、
上記ラベルと上記入力系列の要素との距離は、ラベルに対応する音素の平均的な特徴ベクトルからのユークリッド距離又は隠れマルコフモデルの状態に割り当てられた確率密度関数から算出される対数尤度であり、
言語として許される音素のつながりを表現する有向グラフから、入力音声に最も適合する経路を探索し、その結果として得られる経路上のラベル列を音声認識の結果とする、
ことを特徴とする音声認識方法。
【請求項９】
請求項１から３の何れかに記載された経路探索装置又は請求項４に記載された音声認識装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、有向グラフと入力系列が与えられたとき、有向グラフの始点ノードから終点ノードに至る複数の経路のうち、入力系列に適合する経路を見つける技術に関する。また、この経路を見つける技術を用いた音声認識技術に関する。
【背景技術】
【０００２】
系列データのモデルを有向グラフで表現し、ある入力系列が与えられたとき、その入力系列がモデルに適合しているか否かを判定するために、有向グラフ中の様々な経路の中から、累積重みが最小又は最大になる経路を探索し、その探索された累積重みをもって適合度を測る方法がある。累積重みとは、経路上のノードやアークに割り当てられた重み、および経路上のアークに割り当てられたラベルと入力系列の要素との距離（又は類似度）を順に累積した値である。また、その探索された経路上のラベル列をもって、入力系列がどんな系列であるかを推測する方法もある。このような方法は、あるカテゴリに属する系列データの特徴をモデル化し、多数の系列データからそのカテゴリの特徴を持つ系列データを自動的に検出したり、ある系列データがどのようなラベル系列で構成されるかを判別する目的に利用されている。ただし、この発明における経路とはあるノードからあるノードへの遷移過程を表し、同じアークを何度通っても良いものとする。
【０００３】
例えば、音声認識では、音素や単語の並び方などのルールを有向グラフで表し、音素や単語の連鎖確率（の対数値）を重みとしてアークに付与し、音素や単語の音響パターンやその分布関数を表すラベル（例えば音素／ａ／の短時間スペクトルパターンの分布関数を指す）を対応する各アークに割り当てる。入力された音声の短時間スペクトルパターンを表す特徴ベクトルとラベルとの類似度は、ラベルに対応する分布関数にその特徴ベクトルを入力したときの値とする。また、音素や単語の並び方のルールに従って始点ノードと終点ノードも設定する。このように用意された音声認識のための有向グラフの中から、入力された音声の短時間スペクトルパターンの時系列に対して、始点ノードから終点ノードに至る累積重みが最小又は最大となる経路を求めることで、経路上のラベル列（音素列）を音声認識結果として出力できる。
【０００４】
しかし、大きな有向グラフの中には多数の経路が存在し、その中から累積重みが大きい、又は小さい経路を探索することは簡単ではない。例えば、あらゆる可能な経路を列挙して累積重みを計算しようとすると、列挙される経路の数は長さに応じて指数的に増加する。例えば、図７に示すような簡単な有向グラフを考える。図７の丸はノード、矢印付きの弧は向きを持ったアークを表し、各アークの近くに配置されたアルファベットはそのアークのラベルを表すものとする。このとき、長さ１０の入力系列が与えられたとすると、経路の総数はアーク数５の１０乗（＝９７６５６２５）になる。このように簡単な有向グラフであっても異なる経路の数は膨大になる。
【０００５】
そこで、入力系列の要素を順に読み込み、その読み込みに合わせて経路を始点ノードから１アークずつ伸ばして行き、その都度累積重みに基づいて見込みの少なくなった経路を排除しながら処理を進めるビーム探索がよく用いられる。ここで見込みの少ない経路とは、累積重みの小さな経路を探索しているときは他の経路と比べて累積重みが大きい経路、累積重みの大きな経路を探索しているときは他の経路と比べて累積重みが小さい経路を指すものとする。
【０００６】
一般的なグラフ探索問題におけるビーム探索法は、例えば非特許文献１に記載されている。また、有向グラフに入力系列を与えたときのビーム探索方法は、例えば非特許文献２に記載されている。
【０００７】
以下、図８を用いて、従来のビーム探索の手順を説明する。以降、探索するのは累積重みの小さな経路であることを前提とする。累積重みの大きな経路を探索する場合は、重みの符号を反転する、アークのラベルと入力要素との距離の符号を反転するかそれらの類似度を用いる、最小値計算は最大値計算に置き換えるなどの簡単な変更で実現できる。また説明の中では探索途中の一つの経路を仮説と呼ぶ。また、始点ノードから終点ノードに到達した仮説を完全仮説と呼ぶ。
【０００８】
図８に示すように、まず読み込む入力系列があるかどうかを判定し（ステップＳ１）、読み込む入力系列があれば、最初に始点ノードに到達した長さ０の仮説のみを含む仮説の集合を現在の仮説の集合として用意する（ステップＳ２）。次に、入力系列を読み込み（ステップＳ３）、その入力系列から読み込める要素があるかどうかを判定する（ステップＳ４）。入力系列に読み込む要素があった場合は仮説更新（ステップＳ５）及び仮説枝刈（ステップＳ６）を行う。
【０００９】
ステップＳ５では、現在の仮説の集合に含まれる各仮説に、その各仮説の到達した最後のノードから遷移可能な各アークと、その各アークの遷移先のノードとを加えて、新たな仮説とする。また、仮説の累積重みと、遷移可能なアークの重みと、現在の入力要素とその遷移可能なアークのラベルとの距離を加えた値とを新たな仮説の累積重みとする。このようにして、現在の仮説の集合を生成された新たな仮説の集合で置き換えることで、仮説の更新を行う。
【００１０】
ステップＳ６では、更新された新たな仮説の集合の中で累積重みが大きい仮説をその集合から排除することで、仮説の数を削減する。
【００１１】
入力系列に読み込む要素が無かった、つまり入力要素の最後まで読み終えている場合は完全仮説の選択及び出力を行う（ステップＳ７）。すなわち、現在の仮説の集合の中にある完全仮説の内、累積重みが小さい順に一つ以上の完全仮説を選び、これらを前記始点ノードから前記終点ノードに至る経路の候補として出力する（ステップＳ７）。その後、ステップＳ１に戻る。ステップＳ１において、次に読み込む入力系列がなければ、処理を終了する。
【００１２】
仮説の枝刈り（ステップＳ６）には、一般に、着目している仮説の累積重みが、現在の仮説の集合の中で最も小さな累積重みに正の定数（ビーム幅とも呼ばれる）を加えた値よりも大きい場合にその仮説を排除する方法や、着目している仮説の現在の仮説の集合の中での累積重みにおける順位がある正の定数（累積重みに対するビーム幅と区別して、個数ビーム幅とも呼ばれる）よりも大きい場合にその仮説を排除する方法がある。
【００１３】
探索の途中で見込みの少ない仮説、すなわち、将来この仮説を伸ばして行っても累積重みの小さな完全仮説になる可能性が小さい仮説を排除することは、一般に仮説の枝刈と呼ばれている。
【００１４】
ビーム探索法で累積重みの小さい完全仮説を探索するとき、仮説の枝刈りにおいて仮説の集合から多数の仮説を枝刈した方が計算量を少なく抑えることができる。なぜなら、計算の大半を占める仮説の更新では、現在の仮説の集合に含まれる個々の仮説に対し、その仮説が到達したノードから遷移可能なアークの数だけ新たな仮説を生成するので、集合に含まれる仮説の数は少なければ少ないほど計算量は少なくなるためである。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】Xuedong Huang, Alex Acero, Hsiao-Wuen Hon, “Spoken Language Processing”, Prentice Hall, Upper Saddle River, NJ 07458, Chapter 12, Basic Search Algorithms, 12.1.3.2節, pp.606-608
【非特許文献２】Takaaki Hori, Chiori Hori, Yasuhiro Minami, Atsushi Nakamura, ”Efficient WFST-based one-pass decoding with on-the-fly hypothesis rescoring in extremely large vocabulary continuous speech recognition”, IEEE Transactions on Audio, Speech, and Language Processing, Vol.15, No.14, pp.1352-1365, 2007, IV節B(pp. 1357-1359)
【発明の概要】
【発明が解決しようとする課題】
【００１６】
ビーム幅又は個数ビーム幅を小さくして仮説をより枝刈されやすくすることで仮説の数を削減することはできるが、将来その仮説を伸ばして行ったときに累積重みの小さな完全仮説になり得る仮説を枝刈してしまい、目的の完全仮説が得られなくなる探索誤りを引き起こす。つまり、ビーム幅を狭くすると探索処理の計算量は小さくなるが探索誤りの危険性が増す。
【００１７】
この発明は、従来よりも探索誤りの危険性が小さい経路探索装置、音声認識装置、これらの方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
仮説の枝刈をする際に、各仮説についての素性を抽出する。素性を入力として仮説を排除するか否かの指標を出力する判別関数に抽出された素性を入力した場合の出力値を算出してその各仮説についての判別値とする。判別値が所定の閾値より大きいかどうかを判定して大きい場合には上記判別値に対応する仮説を仮説の集合から除き、又は、判別値が所定の閾値より小さいかどうかを判定して小さい場合には上記判別値に対応する仮説を仮説の集合から除く。
【発明の効果】
【００１９】
仮説の累積重み以外の属性、例えばどのノードに到達したか、どのアークを通ったか等の素性を用いることでより正確な枝刈判定を行うことができ、探索誤りの危険性を従来よりも小さくすることができる。
【図面の簡単な説明】
【００２０】
【図１】経路探索装置の例の機能ブロック図。
【図２】音声認識装置の例の機能ブロック図。
【図３】経路探索方法の例の流れ図。
【図４】音声認識方法の例の流れ図。
【図５】音声認識用の有向グラフの一例を示す図
【図６】従来法とこの発明の認識処理時間の比較評価結果を示す図。
【図７】有向グラフを例示する図
【図８】従来の経路探索方法の例の流れ図。
【発明を実施するための形態】
【００２１】
［経路探索装置及び方法］
図１に経路探索装置の例の機能ブロック図を示す。図３に経路探索方法の例の流れ図を示す。
この発明の経路探索装置及び方法は、主に仮説枝刈部６の処理及び必要に応じて仮説枝刈判別関数更新部８を含む点で従来と異なる。以下では、従来とは異なる部分を主に説明をして、従来と同様の部分については重複説明を略する場合がある。
経路探索装置１００は、記憶部１、制御部２、初期仮説生成部３、入力系列読込部４、仮説更新部５、仮説枝刈部６、完全仮説出力部７及び仮説枝刈判別関数更新部８を例えば含む。
【００２２】
制御部２は、読み込む入力系列があるかどうかを判定する（ステップＳ１）。
読み込む入力系列があれば、初期仮説生成部３は、最初に始点ノードに到達した長さ０の仮説のみを含む仮説の集合を現在の仮説の集合として、記憶部１に格納する（ステップＳ２）。最初に始点ノードに達した長さ０の仮説の累積重みは例えば０とする。
入力系列読込部４は、入力系列を読み込み（ステップＳ３）、その入力系列から読み込める要素があるかどうかを判定する（ステップＳ４）。
入力系列に読み込む要素があった場合は、仮説更新部５は仮説の更新を行い（ステップＳ５）、仮説枝刈部６が仮説の枝刈を行う（ステップＳ６）。
【００２３】
仮説更新部５は、記憶部１から読み込んだ現在の仮説の集合に含まれる各仮説に、その各仮説の到達した最後のノードから遷移可能な各アークと、その各アークの遷移先のノードとを加えて、新たな仮説とする。また、仮説の累積重みと、遷移可能なアークの重みと、現在の入力要素とその遷移可能なアークのラベルとの距離を加えた値とを新たな仮説の累積重みとする。このようにして、現在の仮説の集合を生成された新たな仮説の集合で置き換えることで、仮説の更新を行う。新たに生成された仮説の集合は記憶部１に格納される。
【００２４】
仮説枝刈部６は、更新された新たな仮説の集合の中で累積重みが大きい仮説をその集合から排除することで、仮説の数を削減する。
【００２５】
入力系列に読み込む要素が無かった、つまり入力要素の最後まで読み終えている場合は、完全仮説出力部７は、完全仮説の選択及び出力を行う（ステップＳ７）。すなわち、現在の仮説の集合の中にある完全仮説の内、累積重みが小さい順に一つ以上の完全仮説を選び、これらを前記始点ノードから前記終点ノードに至る経路の候補として出力する。その後、ステップＳ１に戻る。ステップＳ１において、次に読み込む入力系列がなければ、処理を終了する。
【００２６】
以下、仮説枝刈部６について詳細に説明する。仮説枝刈部６は、図２に例示するように、各仮説についての素性を抽出する仮説素性抽出部６１と、素性を入力として仮説を排除するか否かの指標を出力する判別関数に上記抽出された素性を入力した場合の出力値を算出してその各仮説についての判別値とする仮説枝刈判別値算出部６２と、上記判別値が所定の閾値より大きいどうか又は小さいかどうかを判定して、大きい又は小さい場合には、上記判別値に対応する仮説を仮説の集合から除く仮説枝刈判定部６３と、を含む。
【００２７】
仮説素性抽出部６１では、現在の仮説の集合に含まれる個々の仮説について素性を抽出する（ステップＳ６１）。仮説をｈ、現在の仮説の集合をＨ、仮説ｈの累積重みをｗ［ｈ］、仮説ｈの累積重みの集合Ｈの中での順位をｒａｎｋ（ｈ）と表すと、仮説ｈから例えば次のような素性ベクトルを抽出することができる。
【００２８】
【数１】
2011048255.tif 000003
【００２９】
素性ベクトルφ（ｈ，Ｈ）の１次元目の素性ｗ［ｈ］−（ｍｉｎｇ∈Ｈｗ［ｇ］＋Ｂ）は、集合Ｈ内の仮説の累積重みの最小値に正の定数Ｂ（ビーム幅に相当）を加えた値を仮説ｈの累積重みｗ［ｈ］から引いた値であり、この素性が正であれば従来のビーム幅Ｂに従って仮説ｈを枝刈する、負になれば枝刈しない、という判別値を与える。
【００３０】
次の２次元目の素性ｒａｎｋ（ｈ，Ｈ）−Ｒは、仮説ｈの累積重みの集合Ｈの中での順位から正の定数Ｒ（個数ビーム幅に相当）を引いた値であり、この素性が正になれば個数ビーム幅Ｒに従って仮説ｈを枝刈する、負になれば枝刈しない、という判別値を与える。
【００３１】
これら二つの素性は、従来のビーム探索でも利用されていたが、この発明では更に仮説ｈが最後に到達したノードｎ［ｈ］やアークａ［ｈ］等のより多くの素性を利用する。前述の素性ベクトルφ（ｈ，Ｈ）の例では、ｆｎｏｄｅ［ｉ］（ｎ［ｈ］）はノードｎ［ｈ］が有向グラフのｉ番目のノードであれば１、そうでなければ０を返すような関数であり、同様にｆａｒｃ［ｊ］（ａ［ｈ］）はａ［ｈ］が有向グラフのｊ番目のアークであれば１、そうでなければ０を返すような関数である。ここで、有向グラフの個々のアークやノードには固有の番号が割り当てられているものとし、有向グラフのノードの総数をＮ、アークの総数をＡとしている。よって、１≦ｉ≦Ｎ、１≦ｊ≦Ａである。他にも素性として、仮説ｈの長さ（経路上のアーク数）やアークａ［ｈ］のラベル等を同様の関数として導入することも可能である。
【００３２】
次に、仮説枝刈判別値算出部６２では、仮説素性抽出部６１において抽出された素性ベクトルφ（ｈ，Ｈ）に基づいて、仮説を枝刈するか否かを判定する判別関数の値を算出する（ステップＳ６２）。判別関数はパラメータベクトルΛを持ち、Λを変化させることで判別基準をさまざまに変化させることができるものとする。例えば線形判別関数を用いた場合、素性ベクトルφ（ｈ，Ｈ）の各次元に対する係数ベクトル（以後、素性重み係数ベクトルと呼ぶ）がパラメータベクトルΛとなり、線形判別関数はΛとφ（ｈ，Ｈ）の内積Λ・φ（ｈ，Ｈ）によって表わされる。例えばΛは次のようなベクトルとなる。
【００３３】
【数２】
2011048255.tif 000004
【００３４】
ここで、λｗｅｇｈｔ，λｒａｎｋ，λｎｏｄｅ［１］，λｎｏｄｅ［２］，…，λｎｏｄｅ［Ｎ］，λａｒｃ［１］，λａｒｃ［２］，…，λａｒｃ［Ａ］，は、式（１）の素性ベクトルφ（ｈ，Ｈ）の各次元に対する素性重み係数である。この判別関数のパラメータは、予め学習データを用いて求めておくことができる。
式（１）と式（２）の例において、これらの内積は次のように計算できる。
【００３５】
【数３】
2011048255.tif 000005
【００３６】
続いて、仮説枝刈判定部６３ではこのような判別関数の値がある閾値（例えば０）より大きい場合は仮説を枝刈し、小さい場合は枝刈しないと判別する。式（３）の例は、従来の枝刈判定基準であるビーム幅や個数ビーム幅に基づく判定に加えて、その仮説が最後に到達したノードｎ［ｈ］やアークａ［ｈ］に応じたλｎ［ｈ］やλａ［ｈ］の値が判定に影響を与える。このように仮説の到達したノードやアークに応じて異なる判定基準で仮説の枝刈判定を行うため、より正確な枝刈判定が可能になる。
式（２）、式（３）の例で示した線形判別関数は一次式であるが、何らかの判別値を与える関数であればより高次の多項式を用いても良いし、何らかの非線形関数を用いても良い。
【００３７】
次に、判別関数のパラメータを更新する仮説枝刈判別関数更新部８について説明する。仮説ｈの素性ベクトルφ（ｈ，Ｈ）の判別関数をｄ（φ（ｈ，Ｈ）；Λ）とする。線形判別関数のときは、ｄ（φ（ｈ，Ｈ）；Λ）＝Λ・φ（ｈ，Ｈ）である。
また、判別関数の値に応じて探索誤りの起こる可能性を表す探索誤りリスク関数ｒｉｓｋ（ｄ（φ（ｈ，Ｈ）；Λ））を定義する。この関数はｄ（φ（ｈ，Ｈ）；Λ）が小さいときは仮説ｈが枝刈される可能性が小さいので０に近い値、ｄ（φ（ｈ，Ｈ）；Λ）が大きいときは仮説ｈが枝刈りされ探索誤りが起こるリスクが高まるので、０より大きな値を取るものとする。
【００３８】
この探索誤りリスク関数としては、例えば式（４）のシグモイド関数や、式（５）のヒンジ関数等を用いることができる。
【００３９】
【数４】
2011048255.tif 000006
【００４０】
ここで、ｘ＝ｄ（φ（ｈ，Ｈ）；Λ）、ｃは定数を表す。いずれもｘが小さいときは０に近づき、大きいときは０よりも大きな値を取る。
より探索誤りリスクの少ないパラメータを求めるには、累積重みの小さな完全仮説の経路上の仮説の素性に対する探索誤りリスクの総和
【００４１】
【数５】
2011048255.tif 000007
【００４２】
を小さくするようにパラメータを更新する。ここで、Ｋは入力系列Ｏを最後まで読み込んで得られた完全仮説の集合、Ｇ（ｋ｜Ｋ，Ｏ）は、Ｋの中にある完全仮説ｋの重要度を表し、累積重みが小さいほど０以上の大きな値を取るものとする。例えば、有向グラフのアークの重みやアークのラベルと入力系列の各要素との距離が、負の対数確率として計算されている場合は、Ｇ（ｋ｜Ｋ，Ｏ）を
【００４３】
【数６】
2011048255.tif 000008
【００４４】
のようなｋの事後確率としても良い。一方、ＨｔはＯのｔ番目の要素によって更新された現在の仮説の集合、条件「ｈがｋの一部」は、始点ノードから仮説ｈの経路がｋの経路とｈが到達したノードまで一致していることを意味する。つまり、探索途中で将来完全仮説に至った仮説についてのみ和を取っている。
【００４５】
Ｌ（Λ，Ｏ）を小さくするようなΛは、例えば、Λの個々の要素でＬ（Λ，Ｏ）を偏微分し、その値に学習係数（正の定数）を乗じてΛの各要素から減算することで、Ｌ（Λ，Ｏ）を小さくすることができる。これは、確率的降下法の原理である。
式（６）をパラメータベクトルΛの要素λｘ（ｘは任意の素性を指す）で偏微分すると、
【００４６】
【数７】
2011048255.tif 000009
【００４７】
となる。λｘはＬ（Λ，Ｏ）のλｘによる偏微分を用いて
【００４８】
【数８】
2011048255.tif 000010
【００４９】
のように更新する。ここで、ηは学習係数を表す正の定数である。
例えば、式（３）の線形判別関数を用い、探索誤りリスク関数として式（４）のシグモイド関数を用いた場合、Ｌ（Λ，Ｏ）を、素性重みλｗｅｉｇｈｔ、λｒａｎｋ、および、ノードｎの素性重みλｎ、アークａの素性重みλａでそれぞれ偏微分すると、
【００５０】
【数９】
2011048255.tif 000011
【００５１】
のように計算できる。
また、予め用意したＹ個の入力系列からなる学習データＯ＝｛Ｏ１，Ｏ２，…，ＯＹ｝を用いて、学習データＯに対する枝刈誤りリスクの総和
【００５２】
【数１０】
2011048255.tif 000012
【００５３】
を減少させるため、パラメータベクトルの要素λｘを
【００５４】
【数１１】
2011048255.tif 000013
【００５５】
のように更新することもできる。
【００５６】
また、パラメータベクトルΛと学習データＯを用いて探索処理を行い式（８）の微分値の和を求めるステップと、式（９）のΛを更新するステップとを繰り返しても良い。この繰り返しにより、Ｌ（Λ，Ｏ）を更に減少させることができる。
しかし、繰り返しＬ（Λ，Ｏ）を減少させていくと、全体として枝刈判定は甘くなるので、枝刈されない仮説の数が増え、計算量は徐々に増加していく。そこで、繰り返しによるＬ（Λ，Ｏ）の単調減少を避けるペナルティ項を導入しても良い。
例えば、式（６）にペナルティ項を導入し、
【００５７】
【数１２】
2011048255.tif 000014
【００５８】
のような式を利用することができる。右辺のペナルティ項（第二項）はΛの２乗ノルムで、Λの各要素を二乗してから全要素について和を取った値である。このペナルティ項はΛの要素がすべて０のとき最小になるので、Λの更新による第一項の減少分と、Λの要素が非０を取ることによる第二項の増加分が一致したとき微分が０になり、Ｌ＾（Λ，Ｏ）が最小値をとる。すなわち、計算量の増加を抑制しながら、探索誤りリスクの総和を減少させることができる。ただし、γはペナルティ項の重み係数であり、第一項と第二項のバランスをとる正の定数である。
また、次式のように判別関数の値を反映したペナルティ項を用いても良い。
【００５９】
【数１３】
2011048255.tif 000015
【００６０】
式（１３）は、判別関数の値の総和が０に近付くように働くペナルティである。つまり、全体として正や負に偏らず、計算量を一定に抑える効果が期待できる。
このようなペナルティ項を持つ枝刈誤りリスクの総和に対しても式（９）と同様に、
【００６１】
【数１４】
2011048255.tif 000016
【００６２】
のようにパラメータを更新できる。式（１１）の微分は、
【００６３】
【数１５】
2011048255.tif 000017
【００６４】
式（１３）の微分は、判別関数が線形判別関数の場合、
【００６５】
【数１６】
2011048255.tif 000018
【００６６】
となる。ただし、φｘ（ｈ，Ｈｔ）は素性ベクトルの要素ｘの値を表している。
Ｙ個の入力系列からなる学習データＯ＝｛Ｏ１，Ｏ２，…，ＯＹ｝を用いる場合も、式（１１）と同様に、
【００６７】
【数１７】
2011048255.tif 000019
【００６８】
をもってパラメータを更新する。
【００６９】
［音声認識装置及び方法］
経路探索装置及び方法を、音声認識装置及び方法に適用することができる。
図２は音声認識装置の例の機能ブロック図であり、図４は音声認識方法の例の流れ図である。
音声認識装置は、音響モデル格納部１１、有向グラフ格納部１２、音声信号入力部１３、音声特徴ベクトル抽出部１４、経路探索装置１００、認識結果出力部１５及び学習用データ１６を例えば含む。
【００７０】
経路探索装置１００の制御部２は、入力系列の要素と有向グラフのアークのラベルとの距離を計算するための音響モデルを音響モデル格納部１１から読み込む（ステップＡ１）。ここで、音響モデルとは、例えば、音声固定単位（例えば音素）の標準的な音声特徴ベクトル又はその分布と、ある入力された特徴ベクトルとを比較して、その特徴ベクトルがその音声固定単位としてどの程度もっともらしいかを距離や確率などの数値で返すものである。
【００７１】
種々の音声固定単位（例えば音素）の音声特徴ベクトルの集合を表す音響モデルとしては、例えば、音声固定単位の音声特徴ベクトル時系列の集合を確率・統計理論に基づいてモデル化する隠れマルコフモデル法（Hidden Markov Model、以後ＨＭＭと呼ぶ）が主流である。このＨＭＭ法の詳細は、例えば、社団法人電子情報通信学会編、中川聖一著「確率モデルによる音声認識」に開示されている。
【００７２】
つぎに、経路探索装置１００の制御部２は、音声認識用の有向グラフを有向グラフ格納部１２から読み込む（ステップＡ２）。
【００７３】
音声認識用の有向グラフを構成する方法は、例えば、単語発音辞書や言語モデルを重み付き有限状態トランスデューサ（英訳  Weighted Finite-State Transducer: WFST）によって記述し、それらを合成して一つの重み付き有限状態トランスデューサを構成する方法は、例えば、学術論文、M. Mohri、 F. Pereira、 M. Riley著 “Weighted finite-state transducers in speech recognition”, Computer Speech and Language, Vol. 16, No. 1, pp. 69--88 (2002)に開示されている。重み付き有限状態トランスデューサは有向グラフの一種である。
【００７４】
音声認識用の有向グラフの個々のアークには、一般に、ＨＭＭの一つの状態を示すラベルが付与される。ＨＭＭの状態は、ある音素のその音素内におけるおおまかな位置（例えば、前半、中盤、後半）に対応する音声固定単位であり、各状態は音声特徴ベクトルの確率密度分布（例えば、多次元混合正規分布）を持っている。この実施形態では、仮説の累積重みに加える音声特徴ベクトルとアークのラベルとの距離を、そのラベルに対応する状態の確率密度分布を用いて計算された音声特徴ベクトルの確率密度の対数の符号を反転させた値として計算している。
【００７５】
音声認識のための有向グラフは、例えば図５のように構成されている。始点ノードは黒丸、終点ノードは二重丸、それら以外のノードは丸で表されている。ノードを結ぶアークにラベルが付与されており、音素名とその音素内での位置を表すような表記になっている。例えば、ａ２は音素ａのＨＭＭの２番目の状態の確率密度分布を指すものとする。
【００７６】
また、“ａ１：赤”のように”：”で二つのラベルが書いてあるときは、ラベルと入力ベクトルの距離は”：”の前のａ１に基づいて計算し、”：”の後の”赤”は、このアークを通る完全仮説が探索結果として選ばれたときに、認識結果となるラベルである。図５の例では、上を通る経路と下を通る経路があり、上を通る完全仮説が選ばれたときは、“赤です”が認識結果となり、下を通る完全仮説が選ばれたときは、“青です”が認識結果となる。
【００７７】
音声信号入力部１３は音声を入力し、音声特徴ベクトル抽出部１４は音声信号入力部１３から送られた音声信号の短時間スペクトルパターンの特徴ベクトルの時系列を抽出する（ステップＡ３）。音声認識に用いる特徴ベクトルとしては、短い時間（例えば１０ミリ秒）ごとに音声信号を分析することにより得られるメルケプストラム（mel-frequency cepstral coefficients、MFCCと呼ばれる）、デルタＭＦＣＣ、ＬＰＣケプストラム、対数パワーなどがある。
【００７８】
経路探索装置１００は、入力系列として音声特徴ベクトル抽出部１４から得られる特徴ベクトルの時系列を用いる。経路探索装置１００は、音響モデル格納部１１から読み込んだ音響モデルと有向グラフ格納部１２から読み込んだ音声認識用の有向グラフを用いて、音声特徴ベクトル抽出部１４から送られた特徴ベクトルの時系列を読み込み、累積重み最小の完全仮説を求め、認識結果出力部１５に送る。
【００７９】
経路探索装置１００の機能構成及び処理（ステップＳ１からステップＳ８）は、上記［経路探索装置及び方法］の欄で説明したものと同様であるためここでは重複説明を省略する。なお、ラベルは、音素や隠れマルコフモデルの状態等の音響パターンに相当するラベルとし、ラベルと入力系列の要素との距離は、ラベルに対応する音素の平均的な特徴ベクトルからのユークリッド距離又は隠れマルコフモデルの状態に割り当てられた確率密度関数から算出される対数尤度とする。
認識結果出力部１５は、完全仮説に対応するラベルを音声認識結果として出力する（ステップＡ３）。
【００８０】
［実験結果］
図２に示す形態で音声認識装置を構築した。音響モデルには、４３種類の音素に対するＨＭＭを用意し、各音素ごとに３つの状態があり、各状態にはその音素のコンテキスト（前にある音素は何か、後ろに続く音素は何か）に応じて３０６４種類ある確率密度分布の内の一つが割り当てられている。
【００８１】
有向グラフは、２０、０００単語からなる発音辞書と、単語の３連鎖確率を与えるトライグラム言語モデルとを用いて、文献１に示される方法で構築した重み付き有限状態トランスデューサを用いた。有向グラフのノード数７２４６９、アーク数は１０２０７３となった。
【００８２】
音声の特徴ベクトル時系列は、１０ミリ秒ごとに音声信号を分析することにより得られるＭＦＣＣ１２次元、ＭＦＣＣの各次元の時系列方向に前後２フレーム見たきの一次回帰係数であるデルタＭＦＣＣ１２次元、各次元の時系列方向に前後２フレーム見たきの一次回帰係数であるデルタデルタＭＦＣＣ１２次元、および対数パワーを合わせた３９次元のベクトルを要素とする入力系列として抽出する。
【００８３】
また、事前に男性話者が読み上げた３３８２０文を学習データとして、仮説枝刈判別関数更新部８（図１）により仮説枝刈判別関数のパラメータを１００回更新した。このとき仮説ｈの素性ベクトルとして、
【００８４】
【数１８】
2011048255.tif 000020
【００８５】
を用いた。
前述したように、１次元目の素性ｗ［ｈ］−（ｍｉｎｇ∈Ｈｗ［ｇ］＋Ｂ）は、集合Ｈ内の仮説の累積重みの最小値に正の定数Ｂ（ビーム幅に相当）を加えた値をｈの累積重みｗ［ｈ］から引いた値であり、この素性が正であれば従来のビーム幅Ｂに従ってｈを枝刈する、負になれば枝刈しない、という判別値を与える。２次元目以降のｆａｒｃ［ｊ］（ａ［ｈ］）はａ［ｈ］が有向グラフのｊ番目のアークであれば１、そうでなければ０を返すような関数である。
仮説枝刈判別関数のパラメータである素性重みとして
【００８６】
【数１９】
2011048255.tif 000021
【００８７】
を用いた。仮説枝刈判別関数は線形判別関数Λ・φ（ｈ，Ｈ）とし、リスク関数としてはシグモイド関数式（４）を用いた。パラメータの更新は、式（１３）の探索誤りリスクの総和に基づき、式（１５）の微分と式（１６）の更新式を用いて行った。
【００８８】
この音声認識装置を用いて、被験者が新聞記事中の１００文章を読み上げた音声を入力したときの、音声認識処理に要した処理時間を図６に示す。ただし、処理時間は、音声認識に要した処理時間を実際に発話された時間で割った値（実時間比）とする。また、単語誤り率とは、正解の文と認識結果とを比べたときの単語あたりの誤りの割合であり、通常次のように計算される。
【００８９】
【数２０】
2011048255.tif 000022
【００９０】
置換誤り数は正解文の単語が認識結果の中で別の単語に認識された回数、挿入誤り数は正解文には存在しない単語が認識結果に挿入された回数、削除誤り数は正解文に含まれる単語が認識結果に含まれなかった回数を表している。単語誤り率が小さいほど、認識精度が高いことを意味する。
【００９１】
従来のビーム探索法では、前述のｗ［ｈ］−（ｍｉｎｇ∈Ｈｗ［ｇ］＋Ｂ）のみによる枝刈判定を行っている。
【００９２】
図６の結果より、従来のビーム探索法とこの実験例では実時間比（処理時間）が同等で、この実験例の方が単語誤り率が小さくなった。これより、この実験例による音声認識では、探索誤りを削減できていることが示された。実時間比が同一なのは、式（１３）の探索誤りリスクの総和を用いているためで、ペナルティ項の効果により、判別関数の値が全体として正や負に偏よるのを抑え、計算量を一定に保っているためである。
【００９３】
［変形例等］
図１，図２では、各部でデータが直接やり取りされているが、図示されていない記憶部を介してデータの受け渡しが行われてもよい。すなわち、各部で生成された又は受信したデータは記憶部に記憶され、各部は記憶部からそのデータを読み込んでもよい。
【００９４】
経路探索装置及び音声認識装置のそれぞれは、コンピュータによって実現することができる。この場合、各装置がそれぞれ有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、これらの装置における各処理機能が、コンピュータ上で実現される。
【００９５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、これらの装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００９６】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【符号の説明】
【００９７】
１     記憶部
２     制御部
３     初期仮説生成部
４     入力系列読込部
５     仮説更新部
６     仮説枝刈部
６１   仮説素性抽出部
６２   仮説枝刈判別値算出部
６３   仮説枝刈判定部
７     完全仮説出力部
８     仮説枝刈判別関数更新部
１１   音響モデル格納部
１２   有向グラフ格納部
１３   音声信号入力部
１４   音声特徴ベクトル抽出部
１５   認識結果出力部
１６   学習用データ
１００ 経路探索装置
【図１】
2011048255.tif 000023
【図２】
2011048255.tif 000024
【図３】
2011048255.tif 000025
【図４】
2011048255.tif 000026
【図５】
2011048255.tif 000027
【図６】
2011048255.tif 000028
【図７】
2011048255.tif 000029
【図８】
2011048255.tif 000030