(57)【要約】【課題】記号変換方法における最小コスト探索を行う際の計算量を低減する。【解決手段】記号列を、記号列変換部の前段と後段のWFSTにおいてそれぞれ適用される状態遷移に対する累積重みが最小となる後段のWFSTの状態遷移過程に対応する出力記号列を出力する記号列変換方法において、記号を順に読み込みながら、前段WFSTの一つの状態遷移過程を表す仮説に対する累積重みを、その仮説の状態遷移過程における出力記号列を後段WFSTの入力記号列としたときの後段WFSTにおいて可能な状態遷移過程の中で累積重みが最小となる状態遷移過程を求め、その累積重みを仮説の累積重みに加算することで補正し、入力記号列がすべて読み込まれた時点で、累積重み最小の仮説とその仮説の状態遷移過程に対応する出力記号列を後段WFSTの入力記号列としたときに後段WFSTにおいて可能な状態遷移過程の中で累積重みが最小となる状態遷移過程に対する出力記号列をもって変換結果とする。【選択図】図１０
2005257910.tif 000002
【特許請求の範囲】
【請求項１】
記号列を順に読み込む記号列入力部と、
状態遷移によって記号列を変換する二つの重み付き有限状態変換器を用いて記号列を２段階で変換するための前段に用いる前段重み付き有限状態変換器と後段に用いる後段重み付き有限状態変換器とを用いて記号列を変換する記号列変換部と、
後段重み付き有限状態変換器による変換結果を出力する記号出力部とを有し、
記号列入力部から記号を順に読み込んで、入力記号列を読み終えた時点で、前記記号列変換部の前段と後段の重み付き有限状態変換器においてそれぞれ適用される状態遷移に対する重みの累積値（累積重み）が最小となる後段の重み付き有限状態変換器の状態遷移過程に対応する出力記号列を記号列出力部から出力する記号列変換方法において、
記号を順に読み込みながら、前段重み付き有限状態変換器の一つの状態遷移過程を表す仮説に対する累積重みを、その仮説の状態遷移過程における出力記号列を後段重み付き有限状態変換器の入力記号列としたときの後段重み付き有限状態変換器において可能な状態遷移過程の中で累積重みが最小となる状態遷移過程を求め、その累積重みを仮説の累積重みに加算することで補正し、
入力記号列がすべて読み込まれた時点で、累積重み最小の仮説とその仮説の状態遷移過程に対応する出力記号列を後段重み付き有限状態変換器の入力記号列としたときに後段重み付き有限状態変換器において可能な状態遷移過程の中で累積重みが最小となる状態遷移過程に対する出力記号列をもって記号列変換結果とすることを特徴とする記号列変換方法。
【請求項２】
入力音声信号をその音響特徴を表す記号列に変換し、その記号列を請求項１に記載の記号列変換方法を用いて、その入力音声信号に対応する出力記号列に変換することを特徴とする音声認識方法。
【請求項３】
記号列を順に読み込む記号列入力部と、
状態遷移によって記号列を変換する二つの重み付き有限状態変換器を用いて記号列を２段階で変換するための前段に用いる前段重み付き有限状態変換器と後段に用いる後段重み付き有限状態変換器とを用いて記号列を変換する記号列変換部と、
後段重み付き有限状態変換器による変換結果を出力する記号出力部とを有し、
記号列入力部から記号を順に読み込んで、入力記号列を読み終えた時点で、前記記号列変換部の前段と後段の重み付き有限状態変換器においてそれぞれ適用される状態遷移に対する重みの累積値（累積重み）が最小となる後段の重み付き有限状態変換器の状態遷移過程に対応する出力記号列を記号列出力部から出力する記号列変換装置において、
記号列変換部は、
記号を順に読み込みながら、前段重み付き有限状態変換器の一つの状態遷移過程を表す仮説に対する累積重みを、その仮説の状態遷移過程における出力記号列を後段重み付き有限状態変換器の入力記号列としたときの後段重み付き有限状態変換器において可能な状態遷移過程の中で累積重みが最小となる状態遷移過程を求め、その累積重みを仮説の累積重みに加算することで補正する手段と、
入力記号列がすべて読み込まれた時点で、累積重み最小の仮説とその仮説の状態遷移過程に対応する出力記号列を後段重み付き有限状態変換器の入力記号列としたときに後段重み付き有限状態変換器において可能な状態遷移過程の中で累積重みが最小となる状態遷移過程に対する出力記号列をもって記号列変換結果とする手段と、を備えたことを特徴とする記号列変換装置。
【請求項４】
入力音声信号をその音響特徴を表す記号列に変換し、その記号列を請求項２に記載の記号列変換装置を用いて、その入力音声信号に対応する出力記号列に変換することを特徴とする音声認識装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、重み付き有限状態変換器によって表現された記号列変換規則によって、入力された記号列に対して生成可能な数多くの出力記号列から、適用される変換規則の重みの累積値が最小となる出力記号列を効率的に見つけることを可能とする記号列変換方法、及びそれを用いた音声認識方法、並びに記号列変換装置、及びその記号列変換装置を用いた音声認識装置に関するものである。
【背景技術】
【０００２】
（ＷＦＳＴ：重み付き有限状態変換器）
重み付き有限状態変換器(英訳 Weighted Finite-State Transducer :WFST)とは、記号列を別の記号列に変換するための規則を、状態と状態遷移の図に表現する方式を言う。
重み付き有限状態変換器については、例えば、非特許文献１に開示されている。以下、この重み付き有限状態変換器をＷＦＳＴと称す。
ＷＦＳＴは、状態と、状態から状態へと遷移できることを表す状態遷移、および、状態遷移において受理される入力記号と、その際に出力される出力記号、および、その状態遷移の重みの集合によって定義される。ＷＦＳＴは、ある入力記号列が与えられたときに、初期状態からその入力記号列の記号を順に受理する状態遷移に従って出力記号を出力しながら状態遷移を繰り返し、終了状態に達すると終了するモデルである。形式的にはＷＦＳＴは次の８つの組（Ｑ，Σ，△，ｉ，Ｆ，Ｅ，λ，ρ）によって定義される。
１．Ｑは有限の状態の集合。
２．Σは入力記号の有限の集合。
３．△は出力記号の有限の集合。
４．ｉ∈Ｑは初期状態。
５．Ｆ∈Ｑは終了状態の集合。
６．Ｅ∈Ｑ×Σ×△×Ｑは、現状態から入力記号により、出力記号を出力して次状態に遷移する状態遷移の集合。
７．λは初期重み。
８．ρ（ｑ）は終了状態ｑの終了重み。ｑ∈Ｆ。
【０００３】
（ＷＦＳＴの例）
ＷＦＳＴの一例を図１に示す。
図１において、１０はマル（“○”）で表された状態を示しており、そのマルの中の数字はその状態の番号を表している。１１は二重マル（“◎”）で表された終了状態を示しており、その二重マルの中の数字は、その終了状態の番号と状態遷移が終了して最後に累積される終了重みが“（状態番号）／（終了重み）”のように表されている。以後、状態の番号を用いて状態を指し示す場合は、単に状態とその番号を用いて“状態０”や“状態３”のように称す。
１２は各状態を結ぶ矢印（“→”）で表された状態遷移を示しており、各々の状態遷移に付与された記号や数字は、その状態遷移に関連付けられた入力記号、出力記号、重みを“（入力記号）：（出力記号）／（重み）”のように表したものである。
図１のＷＦＳＴを表によって定義することもできる。図２は、各行が一つの状態遷移を表し、その状態遷移における遷移元の状態番号と遷移先の状態番号、入力記号、出力記号、重みが記されている。最終状態（図１では状態３）は、遷移先、入力記号、出力記号を空とし、状態遷移終了時に累積される重み（終了重み）を記入する書式となっている。一般に、ＷＦＳＴの初期状態は状態０とされ、初期重みλも省略されることが多い。そのため、本発明でも初期状態は状態０とし、初期重みは省略して明記しないこととする。
【０００４】
（入力記号列ａ，ａ，ｂ，ｃを出力記号列ｄ，ｄ，ｃ，ｂに変換する過程）
図１のＷＦＳＴは、例えば、入力記号列ａ，ａ，ｂ，ｃを出力記号列ｄ，ｄ，ｃ，ｂに変換することができ、その際の状態遷移過程は、状態番号の系列を用いて表すと０，０，１，３であり、重みの累積値（以下「累積重み」と称す）は、０．５＋０．５＋０．３＋１＋０．５＝２．８となる。しかし、図１のＷＦＳＴでは、ａ，ａ，ｂ，ｃという入力記号列に対しては、０，０，１，３と０，０，２，３の２通りの状態遷移過程が考えられる。一般に、ある入力記号列に対して複数の状態遷移の可能性がある場合（これを非決定性という）は、状態遷移過程における累積重みが最小になる状態遷移過程を選択し、その累積重み最小の状態遷移過程に対応する出力記号列を選択する。図１の例においても、ａ，ａ，ｂ，ｃという入力記号列に対して累積重みが最も小さい状態遷移過程０，０，１，３を選んで、変換結果をｄ，ｄ，ｃ，ｂとする。
【０００５】
あるＷＦＳＴ（これをＡとする）があり、このＡに対して記号列Ｘが入力記号列として与えられたとき、累積重みが最小となる出力記号列（すなわち記号列変換結果）を求めるには、次の累積重みの最小値Ｗ（Ｘ）を計算する必要がある。
【数１】
2005257910.tif 000003
ここで、Ｗ（Ｘ→Ｙ；Ａ）は、ＷＦＳＴ Ａによって記号列Ｘが記号列Ｙに変換されるときの状態遷移過程における累積重みを表す。この累積重みＷ（Ｘ→Ｙ；Ａ）の最小値Ｗ（Ｘ）を求めて、その最小値を与えるＹが記号列変換結果となる。
このＷ（Ｘ）を効率的に求めるには、一般にグラフのコスト最小探索の技術の一つである横型探索法を利用する。例えば、グラフの横型探索法の手順は、非特許文献２に開示されている。
ＷＦＳＴによる記号列変換は、入力記号列によって初期状態から終了状態に至るコスト（累積重み）最小の状態遷移過程を探し出すことによって行われる。
【０００６】
（一つのＷＦＳＴを用いた記号列変換）
一つのＷＦＳＴを用いた記号列変換の一実施例を図３に示す。
まず、本明細書において“仮説”とは、ある記号列が順に入力され、現時点までに読み込まれた入力記号列に対して、ＷＦＳＴにおいて初期状態からその入力記号列によって状態遷移を繰り返した場合の可能性のある一つの状態遷移過程を表すものとする。
記号列入力部１０３では記号を順に読み込み、仮説展開部１０４に送る。仮説展開部１０４では、記号列入力部１０３から受け取った記号とＷＦＳＴ格納部１０１から読み込んだＷＦＳＴに従って、これまで読み込んだ記号列に対する仮説の集合を新たに受け取った記号を用いて各仮説の状態遷移過程を更新することにより新たな仮説を生成し、仮説絞込み部１０５に送る。仮説絞込み部１０５では、仮説展開部１０４から受け取った仮説の集合に対し、同じ状態に到達している仮説の中で累積重みが最小の仮説以外の仮説を削除することにより仮説を絞り込む。入力記号列が最後まで読み込まれていれば、累積重み最小の仮説に対応する出力記号列を記号列出力部１０６に送る。入力記号列が最後まで読み込まれていなければ、仮説を仮説展開部１０４に送る。記号列出力部１０６では、仮説絞込み部１０５から受け取った出力記号列を出力する。
【０００７】
（記号列変換手順）
次に、この実施の形態に基づいて記号列を変換する手順の一例を示す。
まず、ＷＦＳＴのある状態遷移をｅと表すとき、ｎ[ｅ]を遷移先の状態（次状態）、ｉ[ｅ]を入力記号、ｏ[ｅ]を出力記号、ｗ[ｅ]を重みと定義する。また、ある仮説をｈと表わすとき、ｓ[ｈ]を到達している状態、Ｗ[ｈ]をその状態遷移過程における累積重み、Ｏ[ｈ]をその状態遷移過程において出力される記号列とする。
この手順において、仮説は仮説のリスト（以後これを仮説リストと呼ぶ）を用いて管理する。仮説リストに対し、仮説を挿入したり、仮説を取り出したりすることができる。但し、仮説リストに仮説を挿入する場合に、仮説リスト内に同じ状態に到達している仮説があれば、累積重みの小さい方だけを仮説リストに残し、仮説を絞り込む。
【０００８】
ＷＦＳＴを用いた記号列変換手順を図４に示す。
以下、図４の手順を、ＷＦＳＴを用いる記号列変換の一実施例（図３）と対比して説明する。
ステップS101より開始し、初期設定として、ステップS102において空の仮説リストＨとＨ’を生成する。ステップS103において、初期の仮説ｈを生成し、ｓ[ｈ]＝０（ＷＦＳＴの初期状態）、Ｗ[ｈ]＝０、Ｏ[ｈ]＝φ（空の記号列）とし、仮説リストＨに挿入する。
ステップS104では、記号列入力部１０３において記号を一つ読み込み、その記号をｘに代入する。次のステップS105からS108は、仮説展開部１０４において実行される。
ステップS105では、仮説リストＨから仮説を一つ取り出しｈに代入し、状態ｓ[ｈ]から入力記号がｘに等しい状態遷移のリストＥを用意する。
ステップS106ではＥ＝φ（空のリスト）であればS110に進む。そうでなければ、S107に進みＥから状態遷移を一つ取り出し、ｅに代入する。
ステップS108で新たな仮説ｆを生成し、ｓ[ｆ]＝ｎ[ｅ]、Ｗ[ｆ]＝Ｗ[ｈ]＋ｗ[e]、Ｏ[ｆ]＝Ｏ[ｈ]・ｏ[ｅ]とする。ここで、“・”は二つの記号または記号列を接続し、一つの記号列にする演算を表す。
【０００９】
ステップS109は、仮説絞込み部１０５で実行され、仮説ｆを仮説リストＨ’に挿入することにより仮説を絞り込む。
ステップS109からS106に戻り、次の状態遷移について仮説を展開する。
ステップS110では、Ｈ＝φ（すべての仮説を展開済み）であればS111に進む。そうでなければS106に戻り、次の仮説を展開する。
ステップS111では、新たに生成された仮説のリストＨ’の要素を、すでに空となったＨにすべて移し、S112に進む。
ステップS112では、記号列入力部１０３において次の入力記号が存在するならばS104に戻り、そうでなければ、入力記号列がすべて読み込まれたと判断しS113に進む。
ステップS113では、仮説リストＨの中で終了状態に到達している仮説の累積重みにその終了状態の終了重みを加えた後で、その終了状態に到達している仮説の中から累積重み（Ｗ[ｈ]）が最小となる仮説ｈを選び、その出力記号列Ｏ[ｈ]を記号列変換結果として、記号列出力部１０６において出力する。
ステップS114にてＷＦＳＴを用いる記号列変換手順を終了する。
【００１０】
（ＷＦＳＴに入力記号列ａ，ａ，ｂ，ｃが与えられた場合の出力記号列を求める過程）
この記号列変換手順に従って、図１のＷＦＳＴに入力記号列ａ，ａ，ｂ，ｃが与えられた場合の出力記号列を求める過程を順を追って説明する。但し、ある仮説（現状態番号ｓ、出力記号列Ｏ、累積重みＷ）がある場合、その仮説を（ｓ，Ｏ，Ｗ）のように表すものとする。また、ＷＦＳＴのある状態遷移（現状態番号ｓ、次状態番号ｎ、入力記号ｘ、出力記号ｙ、重みｗ）を＜ｓ→ｎ，ｘ：ｙ／ｗ＞と表すものとする。
S101から開始し、S102で空のリストＨとＨ’を作る。
S103により仮説リストＨの中の仮説（０，φ，０）を挿入する。
【００１１】
記号“ａ”読み込み
S104で記号ａを読み込み、S105において仮説リストＨから仮説（０，φ，０）を取り出す。この仮説の現状態０から入力記号がａに等しい状態遷移＜０→０，ａ：ｄ／０．５＞を含む状態遷移リストＥを作る。
S106でＥ＝φではないのでS107に進み、状態遷移＜０→０，ａ：ｄ／０．５＞を取り出し、S108で新たな仮説（０，ｄ，０．５）を生成し、S109でＨ’に挿入する。
S106に戻りＥ＝φであるためS110に進み、Ｈ＝φであるためS111に進む。Ｈ’の要素（０，ｄ，０．５）をＨに移し、S112で次の入力記号が存在するのでS104に戻る。
続いて、S104で記号ａを読み込み、S105において仮説リストＨから仮説（０，ｄ，０．５）を取り出す。この仮説の現状態０から入力記号がａに等しい状態遷移＜０→０，ａ：ｄ／０．５＞を含む状態遷移リストＥを生成する。
S106でＥ＝φではないのでS107に進み、Ｅから状態遷移＜０→０，ａ：ｄ／０．５＞を取り出す。S108で新たな仮説（０，ｄｄ，１）を生成し、S109でＨ’に挿入する。
S106に戻りＥ＝φであるためS110に進み、Ｈ＝φであるためS111に進む。Ｈ’の要素（０，ｄｄ，１）をＨに移し、S112で次の入力記号が存在するのでS104に戻る。
【００１２】
記号“ｂ”読み込み
続いて、S104で記号ｂを読み込み、S105において仮説リストＨから仮説（０，ｄｄ，１）を取り出す。この仮説の現状態０から入力記号がｂに等しい状態遷移＜０→１，ｂ：ｃ／０．３＞と＜０→２，ｂ：ｂ／１＞を含む状態遷移リストＥを作る。
S106でＥ＝φではないのでS107に進み、Ｅから状態遷移＜０→１，ｂ：ｃ／０．３＞を取り出す。S108で新たな仮説（１，ｄｄｃ，１．３）を生成し、S109でＨ’に挿入する。
S106に戻りＥ＝φではないのでS107に進み、Ｅから状態遷移＜０→２，ｂ：ｂ／１＞を取り出す。S108で新たな仮説（２，ｄｄｂ，２）を生成して、S109でＨ’に挿入する。
S106に戻りＥ＝φであるためS110に進み、Ｈ＝φであるためS111に進み、Ｈ’の要素（１，ｄｄｃ，１．３）と（２，ｄｄｂ，２）はＨに移され、S112で次の入力記号が存在するのでS104に戻る。
【００１３】
記号“ｃ”読み込み
続いて、S104で記号ｃを読み込み、S105において仮説リストＨから仮説（１，ｄｄｃ，１．３）を取り出す。この仮説の現状態１から入力記号がｃに等しい状態遷移＜１→３，ｃ：ｂ／１＞を含む状態遷移リストＥを作る。
S106でＥ＝φではないのでS107に進み、Ｅから状態遷移＜１→３，ｃ：ｂ／１＞を取り出す。S108で新たな仮説（１，ｄｄｃｂ，２．３）を生成し、S109でＨ’に挿入する。
S106に戻りＥ＝φであるためS110に進み、Ｈ≠φであるためS105に戻り、仮説リストＨから仮説（２，ｄｄｂ，２）を取り出す。この仮説の現状態２から入力記号がｃに等しい状態遷移＜２→３，ｃ：ａ／０．６＞を含む状態遷移リストＥを作る。
S106でＥ＝φではないのでS107に進み、Ｅから状態遷移＜２→３，ｃ：ａ／０．６＞を取り出す。S108で新たな仮説（３，ｄｄｂａ，２．６）を生成し、S109でＨ’に挿入する。このとき、Ｈ’の中には既に仮説（３，ｄｄｃｂ，２．３）が含まれており、仮説（３，ｄｄｂａ，２．６）は同じ状態３に到達しているので、累積重みの小さい仮説（３，ｄｄｃｂ，２．３）を残し、仮説（３，ｄｄｂａ，２．６）はリストから削除する。
S106に戻りＥ＝φであるためS110に進み、Ｈ＝φであるためS111に進みＨ’の要素（３，ｄｄｃｂ，２．３）をＨに移し、S112で次の入力記号が存在しないのでS113に進む。
S113で、Ｈ内の仮説（３，ｄｄｃｂ，２．３）の到達状態３は終了状態であるため、終了重みを加えて（３，ｄｄｃｂ，２．８）とし、この仮説が終了状態に到達した唯一の仮説であり、累積重み最小となるので、その出力記号列ｄｄｃｂを変換結果として出力し、S114で記号列変換処理を終了する。
【００１４】
（二つのＷＦＳＴによる記号列の変換）
次に二つのＷＦＳＴがあって、順に記号列の変換を行う問題を考える。つまり、二つのＷＦＳＴ、ＡとＢがあって、入力記号列Ｘが与えられたときに、初めにＡを用いて記号列Ｘを記号列Ｙに変換し、その記号列ＹをＢの入力記号列として、更に変換して出力記号列Ｚを得ることを意味する。
ＷＦＳＴの理論では、この問題は、ＡによってＸを変換する際にその出力記号列となり得るすべてのＹをＢの入力記号列として考慮し、それら入力記号列に対して可能性のあるＢの出力記号列Ｚの集合の中から、Ａにおける状態遷移過程の累積重みとＢにおける状態遷移過程の累積重みの和が最小となる変換結果を得る問題となる。従って、
【数２】
2005257910.tif 000004
を計算し、このＷ（Ｘ）を与えるＹとＺの組のうちＺを記号列変換結果とする。
【００１５】
（仮名の記号列を漢字の記号列に変換するＷＦＳＴの例と漢字の連接に重みを与えるＷＦＳＴ）
例として、図５と図６に示す二つのＷＦＳＴを考える。図５は、仮名の記号列を漢字の記号列に変換するＷＦＳＴの一例である。ただし、図５に現れる“ε”の記号は“：”の左側にある場合は、入力記号なしで状態遷移し、右側にある場合はその状態遷移において何も出力しないことを表す。
このＷＦＳＴは、例えば、記号列“あ，め”を状態遷移過程０，１，５（累積重み１）によって“雨”に変換し、“あ，め，だ，ま”は状態遷移過程０，１，５，０，４，５（累積重み３）によって“雨，玉”に変換する。しかし、日本語では一般に“あめだま”に対応する漢字は“雨玉”よりも“飴玉”の方が一般的であるが、図５のＷＦＳＴでは、記号列“飴，玉”を出力する状態遷移過程０，２，５，０，４，５の累積重みは４であるのに対し、“雨玉”に変換する累積重みが３であることから、累積重みが小さい場合の“雨，玉”という変換結果になる。
【００１６】
一方、図６は漢字の連接に重みを与えるＷＦＳＴである。このＷＦＳＴでは、すべての状態遷移において入力記号と出力記号が同じ、つまり記号列を変換せずにそのまま出力するが、状態遷移過程において入力記号列（漢字列）の記号の連接が日本語としてもっともらしい場合には重みが小さく、もっともらしくない場合には重みが大きくなっている。例えば、入力記号列“雨，降り”を受理する状態遷移過程０，１，３の累積重みは０となり、入力記号列“飴，降り”を受理する状態遷移過程０，２，３の累積重みは３となり、入力記号列“雨，降り”の方が日本語としてもっともらしく連接された記号列であることを示している。
【００１７】
そして、この図５と図６のＷＦＳＴを用いて記号列を変換する場合、例えば、仮名の記号列“あ，め，だ，ま”を入力すると、図５のＷＦＳＴから得られる出力記号列は、“雨，玉”で累積重みが３と“飴，玉”で累積重みが４の場合がある。これら出力記号列をそれぞれ図６のＷＦＳＴに入力した場合、“雨，玉”に対する累積重み５が、“飴，玉”に対する累積重みが１となり、図５と図６の二つのＷＦＳＴによる累積重みの和を計算すると次のようになる。
“あ，め，だ，ま”→ “雨，玉”における累積重み  ３＋５＝８
“あ，め，だ，ま”→ “飴，玉”における累積重み  ４＋１＝５
これらの累積重みを比較した結果、より累積重みの小さい出力記号列は“飴，玉”となる。このような変換結果を得るには、漢字の連接に関する重みを持つ図６のＷＦＳＴの情報が不可欠である。
【００１８】
（二つのＷＦＳＴを用いた従来の記号列変換）
二つのＷＦＳＴを用いた従来の記号列変換の一実施例を図７に示す。
まず、二つのＷＦＳＴを用いて２段階の記号列変換を行う場合の前段に用いられるＷＦＳＴを前段ＷＦＳＴ、後段に用いられるＷＦＳＴを後段ＷＦＳＴと呼ぶことにする。また、二つのＷＦＳＴを用いる場合の“仮説”とは、ある記号列が順に入力され、現時点までに読み込まれた入力記号列に対して、前段ＷＦＳＴにおいて初期状態からその入力記号列によって状態遷移を繰り返した場合の可能性のある一つの状態遷移過程と、その前段ＷＦＳＴの状態遷移過程に対応する出力記号列を後段ＷＦＳＴの入力記号列としたときのある一つの状態遷移過程の組を表すものとする。
【００１９】
図７の記号列入力部１０３では記号を順に読み込み、仮説展開部１０４に送る。仮説展開部１０４では、記号列入力部１０３から受け取った記号と前段ＷＦＳＴ格納部２０１から読み込んだ前段ＷＦＳＴと後段ＷＦＳＴ格納部２０２から読み込んだ後段ＷＦＳＴに従って、これまで読み込んだ記号列に対する仮説の集合を新たに受け取った記号を用いて各仮説の状態遷移過程を更新することにより新たな仮説を生成し、仮説絞込み部１０５に送る。仮説絞込み部１０５では、仮説展開部１０４から受け取った仮説の集合に対し、同じ状態に到達している仮説の中で累積重みが最小の仮説以外の仮説を削除することにより仮説を絞り込む。入力記号列が最後まで読み込まれていれば、累積重み最小の仮説に対応する出力記号列を記号列出力部１０６に送る。入力記号列が最後まで読み込まれていなければ、仮説を仮説展開部１０４に送る。記号列出力部１０６では、仮説絞込み部１０５から受け取った出力記号列を出力する。
【００２０】
二つのＷＦＳＴを用いた場合も、前述の一つのＷＦＳＴにおける最小コスト探索と同様の手法で計算することができる。図７に示すように、仮説展開部１０４において、前段ＷＦＳＴ格納部２０１から前段ＷＦＳＴ（これをＷＦＳＴ Ａとする）、後段ＷＦＳＴ格納部２０２から後段ＷＦＳＴ（これをＷＦＳＴ Ｂとする）を読み込んで、これら二つのＷＦＳＴに従って仮説を更新し、新たな仮説を生成する。二つのＷＦＳＴ ＡとＢを用いて最小コスト探索を行う手順を示す、ただし、ＷＦＳＴが一つの場合とは異なり、仮説ｈはＷＦＳＴ Ａにおける到達状態ｓA[ｈ]とＷＦＳＴ Ｂにおける到達状態ｓB[ｈ]の組を持つものとする。また、仮説リストに仮説を挿入した場合は、仮説リスト内にＷＦＳＴ Ａにおける到達状態とＷＦＳＴ Ｂにおける到達状態が共に等しい仮説があれば、累積重みの小さい方だけを仮説リストに残し、仮説を絞り込む。
【００２１】
（二つのＷＦＳＴを用いた従来の記号列変換手順）
この二つのＷＦＳＴを用いた従来の記号列変換手順を図８に示す。
以下、図８の手順を、二つのＷＦＳＴを用いる従来の記号列変換の一実施例（図７）と対比して説明する。
ステップS201より開始し、初期設定として、ステップS202において空の仮説リストＨとＨ’を生成する。S203において、初期の仮説ｈを生成し、ｓA[ｈ]＝０（ＷＦＳＴ Ａの初期状態）、ｓB[ｈ]＝０（ＷＦＳＴ Ｂの初期状態）、Ｗ[ｈ]＝０、Ｏ[ｈ]＝φ（空の記号列）とし、仮説リストＨに挿入する。
ステップS204では、記号列入力部１０３において記号を一つ読み込みその記号をｘに代入する。
【００２２】
次のステップS205からS208は、仮説展開部１０４において実行される。
ステップS205では、仮説リストＨから仮説を一つ取り出しｈに代入し、状態ｓA[ｈ]から入力記号がｘに等しい状態遷移ｅAと、状態ｓB[ｈ]から入力記号ｏ[ｅA]に等しい状態遷移ｅBの組（ｅA，ｅB）のリストＰを用意する、但し、ｏ[ｅA]＝εの場合は、ｅB＝φ（空の状態遷移）とする組（ｅA，φ）をリストＰに挿入する。
ステップS206でＰ＝φ（空のリスト）であればS210に進む。そうでなければS207に進みＰから状態遷移の組を一つ取り出し（ｅA，ｅB）に代入する。
ステップS208で新たな仮説ｆを生成し、ｓA[ｆ]＝ｎ[ｅA]とする。更に、もしｅB＝φならば、ｓB[ｆ]＝ｓB[ｈ]、Ｗ[ｆ]＝Ｗ[ｈ]＋ｗ[ｅA]、Ｏ[ｆ]＝Ｏ[ｈ]とし、そうでなければｓA[ｆ]＝ｎ[ｅA]、ｓB[ｆ]＝ｎ[ｅB]、Ｗ[ｆ]＝Ｗ[ｈ]＋ｗ[ｅA]＋ｗ[ｅB]、Ｏ[ｆ]＝Ｏ[ｈ]・ｏ[ｅB]とする（ｅB＝φの場合は、状態遷移ｅAの出力記号がεなので、ＷＦＳＴ Ｂでは状態遷移しないことから、ＷＦＳＴ Ｂにおける到達状態ｓB[ｆ]は変化せずｓB[ｆ]＝ｓB[ｈ]となり、ＷＦＳＴ Ｂからの記号出力が無いので出力記号列も変化せずＯ[ｆ]＝Ｏ[ｈ]となる）。
ステップS209は、仮説絞込み部１０５において、仮説ｆを仮説リストＨ’に挿入することにより仮説を絞り込む。
【００２３】
ステップS206に戻り、次の状態遷移の組について仮説を展開する。
ステップS210では、Ｈ＝φ（すべての仮説を展開済み）であればS211に進む。そうでなければS205に戻り、次の仮説を展開する。
ステップS211では、新たに生成された仮説のリストＨ’の要素を、すでに空となったＨにすべて移し、S212に進む。
ステップS212では、記号列入力部１０３において次の入力記号が存在するならばS204に戻り、そうでなければ、入力記号列がすべて読み込まれたと判断し、S213に進む。
ステップS213では、仮説リストＨの中から終了状態に到達している仮説ｈ（ｓA[ｈ]∈ＦAかつｓB[ｈ]∈ＦB、ＦAはＷＦＳＴ Ａの終了状態の集合、ＦBはＷＦＳＴ Ｂの終了状態の集合を表す）の累積重みＷ[ｈ]に対して終了重み（ρ（ｓA[ｈ]）＋ρ（ｓB[ｈ]））を加え、累積重み（Ｗ[ｈ]）が最小の仮説ｈ’を選び、その出力記号列Ｏ[ｈ’]を変換結果として、記号列出力部１０６において出力する。
ステップS214にて二つのＷＦＳＴを用いる従来の記号列変換手順を終了する。
【００２４】
（入力記号列“あ，め，だ，ま”が与えられた場合の出力記号列を求める過程）
この記号列変換手順に従って、図５のＷＦＳＴ Ａ、図６のＷＦＳＴ Ｂとして、入力記号列“あ，め，だ，ま”が与えられた場合の出力記号列を求める過程を順に追って説明する。但し、ある仮説を（ＷＦＳＴ Ａの現状態番号ｓA、ＷＦＳＴ Ｂの現状態番号ｓB、出力記号列Ｏ、累積重みＷ）がある場合、その仮説を（ｓA，ｓB，Ｏ，Ｗ）のように表すものとする。
S201から開始し、S202で空の仮説リストＨとＨ’を作る。
S203により仮説リストＨの中に仮説（０，０，φ，０）を挿入する。
【００２５】
“あ”読み込み
S204で記号“あ”を読み込み、S205において仮説リストＨから仮説（０，０，φ，０）を取り出す。この仮説のＷＦＳＴ Ａの現状態０から入力記号が“あ”の状態遷移と、ＷＦＳＴ Ｂの現状態０から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組
（＜０→１，あ：雨／０＞，＜０→１，雨：雨／０＞），
（＜０→１，あ：雨／０＞，＜０→３，雨：雨／０＞），
（＜０→２，あ：飴／０＞，＜０→２，飴：飴／０＞），
（＜０→２，あ：飴／０＞，＜０→４，飴：飴／０＞）
を含む状態遷移の組のリストＰを作る。
S206でＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜０→１，あ：雨／０＞，＜０→１，雨：雨／０＞）を取り出し、S207で新たな仮説（１，１，雨，０）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜０→１，あ：雨／０＞，＜０→３，雨：雨／０＞）を取り出し、S208で新たな仮説（１，３，雨，０）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜０→２，あ：飴／０＞、＜０→２，飴：飴／０＞）を取り出し、S208で新たな仮説（２，２，飴，０）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜０→２，あ：飴／０＞、＜０→４，飴：飴／０＞）を取り出し、S208で新たな仮説（２，４，飴，０）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φであるためS210に進む。Ｈ＝φであるためS211に進みＨ’内の仮説
（１，１，雨，０），（１，３，雨，０），（２，２，飴，０） ，（２，４，飴，０）
をＨに移し、S212で次の入力記号が存在するのでS204に戻る。
【００２６】
“め”読み込み
続いて、S204で記号“め”を読み込み、S205において仮説リストＨから仮説（１，１，雨，０）を取り出す。この仮説のＷＦＳＴ Ａの現状態１から入力記号が“め”の状態遷移とＷＦＳＴ Ｂの現状態１から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組
（＜１→５，め：ε／１＞，φ）
を含む状態遷移の組のリストＰを作る。ここで、ＷＦＳＴ Ａの状態遷移＜１→５，め：ε／１＞の出力記号はεであることから、ＷＦＳＴ Ｂの状態遷移はφとなっている。
S206でＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜１→５，め：ε／１＞，φ）を取り出し、S208で新たな仮説（５，１，雨，１）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φであるためS210に進む。Ｈ≠φであるためS205に戻り、仮説リストＨから仮説（１，３，雨，０）を取り出す。この仮説の現状態１から入力記号が“め”の状態遷移と、ＷＦＳＴ Ｂの現状態３から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組
（＜１→５，め：ε／１＞，φ）
を含む状態遷移の組のリストＰを作る。
S206でＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜１→５，め：ε／１＞，φ）を取り出し、S208で新たな仮説（５，３，雨，１）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φであるためS210に進む。Ｈ≠φであるためS205に戻り、仮説リストＨから仮説（２，２，飴，０）を取り出す。この仮説の現状態２から入力記号が“め”の状態遷移と、ＷＦＳＴ Ｂの現状態２から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組
（＜２→５，め：ε／２＞，φ）
を含む状態遷移の組のリストＰを作る。
S206でＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜２→５，め：ε／２＞，φ）を取り出し、S208で新たな仮説（５，２，飴，２）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φであるためS210に進む。S210でＨ≠φであるためS205に戻り、仮説リストＨから仮説（２，４，飴，０）を取り出す。この仮説の現状態２から入力記号が“め”の状態遷移と、ＷＦＳＴ Ｂの現状態２から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組
（＜２→５，め：ε／２＞，φ）
を含む状態遷移の組のリストＰを作る。
S206でＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜２→５，め：ε／２＞，φ）を取り出し、S208で新たな仮説（５，４，飴，２）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φであるためS210に進む。Ｈ＝φであるためS211に進み、Ｈ’内の仮説（５，１，雨，１），（５，３，雨，１），（５，２，飴，２），（５，４，飴，２）をＨに移し、S212で次の入力記号が存在するのでS204に戻る。
【００２７】
“だ”読み込み
続いて、S204で記号“だ”を読み込み、S205において仮説リストＨから仮説（５，１，雨，１）を取り出す。この仮説のＷＦＳＴ Ａの現状態５から入力記号が“だ”の状態遷移と、ＷＦＳＴ Ｂの現状態１から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組
（＜０→４，だ：玉／１＞，＜１→４，玉：玉／５＞）
を含む状態遷移の組のリストＰを作る。ここで、ＷＦＳＴ Ａの現状態５から状態０へは入力記号なしで遷移できるのでＰに含まれるＷＦＳＴ Ａの状態遷移は＜０→４，だ：玉／１＞となる。
S206でＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜０→４，だ：玉／１＞，＜１→４，玉：玉／５＞）を取り出し、S208で新たな仮説（４，４，雨玉，７）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φであるためS210に進む。Ｈ≠φであるためS205に戻り、仮説リストＨから仮説（５，３，雨，１）を取り出す。この仮説のＷＦＳＴ Ａの現状態５から入力記号“だ”の状態遷移とＷＦＳＴ Ｂの現状態３から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組は存在しないのでＰ＝φとする。
S206でＰ＝φであるためS210に進み、Ｈ≠φであるためS205に戻る。
S205において仮説リストＨから仮説（５，２，飴，２）を取り出す。この仮説のＷＦＳＴ Ａの現状態５から入力記号が“だ”の状態遷移と、ＷＦＳＴ Ｂの現状態２からの入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組
（＜０→４，だ：玉／１＞，＜２→４，玉：玉／１＞）
を含む状態遷移の組のリストＰを作る。
【００２８】
S206でＰ＝φではないので  S207に進み、Ｐから状態遷移の組（＜０→４，だ：玉／１＞，＜２→４，玉：玉／１＞）を取り出し、S208で新たな仮説（４，４，飴玉，４）を生成し、S209でＨ’に挿入する。但し、Ｈ’には仮説（４，４，雨玉，７）が存在し、ＷＦＳＴ  Ａにおける到達状態とＷＦＳＴ  Ｂにおける到達状態の組が同一であるため、累積重みの小さい仮説（４，４，飴玉，４）を残し、（４，４，雨玉，７）は削除する。
S206に戻りＰ＝φであるためS210に進む。Ｈ≠φであるためS205に戻り、仮説リストＨから仮説（５，４，飴，２）を取り出す。この仮説の現状態５から入力記号が“だ”の状態遷移と、ＷＦＳＴ Ｂの現状態４から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組は存在しないのでＰ＝φとする。
S206でＰ＝φであるためS210に進み、Ｈ＝φであるためS211に進む。
Ｈ’内の仮説（４，４，飴玉，４）をＨに移し、S212で次の入力記号が存在するのでS204に戻る。
【００２９】
“ま”読み込み
続いて、S204で記号“ま”を読み込み、S205において仮説リストＨから仮説（４，４，飴玉，４）を取り出す。この仮説のＷＦＳＴ Ａの現状態４から入力記号が“ま”の状態遷移と、ＷＦＳＴ Ｂの現状態４から入力記号がＷＦＳＴ Ａの状態遷移の出力記号に等しい状態遷移の組
（＜４→５，ま：ε／１＞，φ）
を含む状態遷移の組のリストＰを作る。ここで、ＷＦＳＴ Ａの状態遷移＜４→５，ま：ε／１＞の出力記号はεであることから、ＷＦＳＴ Ｂの状態遷移はφとなる。
S206でＰ＝φではないのでS207に進み、Ｐから状態遷移の組（＜４→５，ま：ε／１＞，φ）を取り出し、S208で新たな仮説（５，４，飴玉，５）を生成し、S209でＨ’に挿入する。
S206に戻りＰ＝φであるためS210に進む。Ｈ＝φであるためS211に進みＨ’内の仮説（５，４，飴玉，５）をＨに移し、S212で次の入力記号が存在しないのでS213に進む。
S213で、Ｈ内の仮説（５，４，飴玉，５）のＷＦＳＴ Ａにおける到達状態５、ＷＦＳＴ Ｂにおける到達状態４は、共に終了状態であり、それぞれの終了重みを加えて（５，４，飴玉，５）とし、この仮説が終了状態に到達した唯一の仮説であることから、その仮説の出力記号列“飴玉”を変換結果として出力し、S214で記号列変換処理を終了する。
二つのＷＦＳＴを用いて記号列を変換する別の手段として、二つのＷＦＳＴを事前に合成して一つのＷＦＳＴとし、一つのＷＦＳＴに対する記号列変換手順を適用する方法がある。ＷＦＳＴの合成方法に関しては、例えば、非特許文献１に開示されている。
しかし、ＷＦＳＴを合成すると、二つの状態遷移の組合せに対して状態や状態遷移ができることからＷＦＳＴの状態数や状態遷移数が非常に大きくなってしまうことがある。そのためコンピュータでＷＦＳＴを扱う場合に、メモリサイズ等の制約から、記号列変換を実行するのが難しい場合がある。
【非特許文献１】E.Roche and Y.Schabes著、“Finite-State Language Processing,”mit Press,1997の15章“Speech Recognition by Composition of Weighted Finite Automata”
【非特許文献２】長尾真  著“岩波講座  ソフトウェア１４：知識と推論”、岩波書店、１０９〜１１３頁
【発明の開示】
【発明が解決しようとする課題】
【００３０】
二つのＷＦＳＴを用いて最小コスト探索を行う従来の手法では、各々の仮説を更新して新たな仮説を生成する際に、前段のＷＦＳＴにおいて可能な状態遷移と、後段のＷＦＳＴにおいて可能な状態遷移のすべての組合せに対して新たな仮説を生成することから、仮説の数が多くなり計算量が大きくなるという問題があった。
【課題を解決するための手段】
【００３１】
本発明は、
記号列を順に読み込む記号列入力部と、
状態遷移によって記号列を変換する二つの重み付き有限状態変換器を用いて記号列を２段階で変換するための前段に用いる前段重み付き有限状態変換器と後段に用いる後段重み付き有限状態変換器とを用いて記号列を変換する記号列変換部と、
後段重み付き有限状態変換器による変換結果を出力する記号列出力部とを有し、
記号列入力部から記号を順に読み込んで、入力記号列を読み終えた時点で、前記記号列変換部の前段と後段の重み付き有限状態変換器においてそれぞれ適用される状態遷移に対する重みの累積値（累積重み）が最小となる後段の重み付き有限状態変換器の状態遷移過程に対応する出力記号列を記号列出力部から出力する記号列変換方法において、
記号を順に読み込みながら、前段重み付き有限状態変換器の一つの状態遷移過程を表す仮説に対する累積重みを、その仮説の状態遷移過程における出力記号列を後段重み付き有限状態変換器の入力記号列としたときの後段重み付き有限状態変換器において可能な状態遷移過程の中で累積重みが最小となる状態遷移過程を求め、その累積重みを仮説の累積重みに加算することで補正し、
入力記号列がすべて読み込まれた時点で、累積重み最小の仮説とその仮説の状態遷移過程に対応する出力記号列を後段重み付き有限状態変換器の入力記号列としたときに後段重み付き有限状態変換器において可能な状態遷移過程の中で累積重みが最小となる状態遷移過程に対する出力記号列をもって記号列変換結果とすることを特徴とする。
この記号列変換方法によって効率的に記号列を変換する。
【発明の効果】
【００３２】
本発明により二つのＷＦＳＴを用いて記号列と変換する手順では、仮説補正部を除けば前段のＷＦＳＴだけを用いて探索する手順（図４）とほぼ同じ計算手順となり、従来の手順（図８）に比べて計算量を抑えることができる。仮説補正部における計算の負荷はあるが、前段のＷＦＳＴの状態遷移において出力記号がεではない場合だけ仮説補正の計算が入るので、前段のＷＦＳＴの出力記号がεである割合が多いほど、処理量削減の効果は大きくなる。
本発明による音声認識方法を用いて、被験者が新聞記事中の１００文章を読み上げた音声を入力したときの、音声認識処理に要した処理時間を表１に示す。ただし、処理時間は、実際に発話された時間を音声認識処理に要した処理時間で割った値（実時間比）とする。単語発音辞書の語彙サイズは２万である。実験にはＩＢＭ互換機、ＣＰＵはPentium（登録商標）III、クロック数８００MHz相当の計算機を使用した。
【表１】
2005257910.tif 000005
従来の記号変換方法を用いた音声認識装置と比べて、処理時間は約３分の２、記号変換手順の違いに関係のない音響モデルによる音響スコア計算の計算部分を除けば約３分の１に短縮された。また、どちらの方法においても音声認識結果は同一であったことから、本発明を用いた場合の音声認識における精度に劣化はない。
【発明を実施するための最良の形態】
【００３３】
以下、図面を用いて本発明の実施の形態について説明する。
（記号列変換装置）
図９は本発明における一実施例の形態を示す図である。
記号列入力部１０３では、記号列を順に読み込み、仮説展開部１０４に送る。仮説展開部１０４では、記号入力部１０３から受け取った記号と前段ＷＦＳＴ格納部２０１から読み込んだ前段のＷＦＳＴに従って、現時点までに読み込まれた入力記号列に対して可能性のある一つの状態遷移過程を仮説と表すと、現時点で存在する仮説の集合に、新たに受け取った記号を用いて各仮説の状態遷移過程を更新することにより新たな仮説を生成し、仮説補正部３０１に送る。仮説補正部３０１では、後段ＷＦＳＴ格納部２０２から読み込んだ後段のＷＦＳＴに従って、仮説展開部１０４から受け取った仮説の各々について、仮説の状態遷移過程における出力記号列を後段のＷＦＳＴの入力記号列としたときの後段のＷＦＳＴにおいて可能な状態遷移過程の中で累積重みが最小となる状態遷移過程を求め、その累積重みを仮説の累積重みに加えることで補正し、仮説絞込み部１０５に送る。仮説絞込み部１０５では、仮説補正部３０１から受け取った仮説に対し、状態遷移過程が重複している仮説の中で累積重みが最小の仮説だけを残し、その他の仮説を削除することにより仮説を絞り込む。入力記号列が最後まで読み込まれていれば、累積重み最小の仮説とその仮説の状態遷移過程に対応する出力記号列を後段のＷＦＳＴの入力記号列としたときに後段のＷＦＳＴにおいて可能な状態遷移過程の中で累積重みが最小となる状態遷移過程に対する出力記号列を記号列出力部１０５に送る。入力記号列が最後まで読み込まれていなければ、残った仮説を仮説展開部１０４に送る。記号列出力部１０５では、仮説絞込み部１０５から受け取った出力記号列を出力する。
【００３４】
（記号列変換手順）
図１０に本発明の一実施の形態において記号列を変換する具体的な手順を示す。
まず、本発明では、前段のＷＦＳＴにおける“仮説”と、その仮説の状態遷移過程から出力される記号列を後段のＷＦＳＴの入力記号列とした場合に、後段のＷＦＳＴの可能な一つの状態遷移過程を、“仮説”と区別して“補助仮説”と呼ぶことにする。一つの仮説に対して必ず一つ以上の補助仮説が存在するので、本実施の形態では、仮説ｈに対する補助仮説の集合を補助仮説リストＬ[ｈ]で表す。
また、仮説ｈがあるとき、ｓA[ｈ]を仮説ｈの状態遷移過程において最後に到達した状態、Ｗ[ｈ]を仮説ｈの状態遷移過程における（補正された）累積重みとする。一方、仮説ｈに対して補助仮説ｇ（ｇ∈Ｌ[ｈ]）があるとき、ｓB[ｇ]を補助仮説ｇの状態遷移過程において最後に到達した状態、Ｗ[ｇ]を仮説ｈの状態遷移過程における累積重みと補助仮説ｇの状態遷移過程における累積重みの和、Ｏ[ｇ]を補助仮説ｇの状態遷移過程において出力される記号列とする。
【００３５】
以下、図１０の手順を図９の実施の形態と対比して説明する。
ステップS301より開始し、初期設定として、ステップS302で空の仮説リストＨとＨ’を生成し、ステップS303において、初期の仮説ｈを生成し、ｓA[ｈ]＝０、Ｗ[ｈ]＝０、Ｌ[ｈ]＝φ（空のリスト）とし、仮説リストＨに挿入する。
また、補助仮説ｇを生成し、ｓB[ｇ]＝０、Ｗ[ｇ]＝０、Ｌ[ｇ]＝φ（空の記号列）とし、ｈの補助仮説リストＬ[ｈ]に挿入する。
ステップS304では、記号列入力部１０３において記号を一つ読み込み、その記号をｘに代入する。
次のステップS305からS308は、仮説展開部１０４において実行される。
ステップS305では、仮説リストＨから仮説を一つ取り出しｈに代入し、状態ｓA[ｈ]から入力記号ｘで遷移可能な状態遷移のリストＥAを生成する。
ステップS306で、ＥA＝φ（空のリスト）ならばS311に進む。そうでなければS307に進む。
ステップS307では、ＥAから状態遷移を一つ取り出して、ｅAに代入し、
ステップS308で新たな仮説ｆを生成し、ｓA[ｆ]＝ｎ[ｅA]、Ｗ[ｆ]＝Ｗ[ｈ]＋ｗ[ｅA]、Ｌ[ｆ]＝Ｌ[ｈ]とする。
ステップS309は、仮説補正部３０１において、もしｏ[ｅA]≠εならば仮説ｆを補正する手段（この手順の説明の後に別途説明する）を実行する。
ステップS310は、仮説絞込み部１０５において、仮説ｆを仮説リストＨ’に挿入することにより仮説を絞り込む。
【００３６】
ステップS311では、Ｈ＝φ（すべての仮説を展開済み）であればS312に進む。そうでなければS305に戻り、次の仮説を展開する。
ステップS312では、新たに生成された仮説のリストＨ’の要素を、既に空となったＨにすべて移し、S313に進む。
ステップS313では、記号列入力部１０３において次の入力記号が存在するならば  S304に戻り、そうでなければ、入力記号列がすべて読み込まれたと判断し、S314に進む。
ステップS314では、仮説リストＨの中から終了状態に到達している仮説（ｓA[ｈ]∈ＦA）で、かつ累積重み（Ｗ[ｈ]）が最小の仮説ｈを選び、更にその仮説に対応する補助仮説リストＬ[ｈ]の中から、終了状態に達している仮説（ｓB[ｇ]∈ＦB）で、かつ累積重み（Ｗ[ｇ]）が最小の補助仮説ｇ’を選び、その出力記号列Ｏ[ｇ’]を変換結果として記号列出力部１０６において出力する。
ステップS315にて本発明の一実施の形態における記号列変換手順を終了する。
【００３７】
（仮説補正手順）
次に仮説補正部３０１における仮説補正手順について説明する。
本発明における仮説の補正は、前段ＷＦＳＴにおける仮説の状態遷移過程に対する累積重みを、その仮説の状態遷移過程における出力記号列を後段ＷＦＳＴの入力記号列としたときの後段ＷＦＳＴにおいて可能な状態遷移過程の中で累積重みが最小となる状態遷移過程を求め、その累積重みを仮説の累積重みに加算することを意味する。入力記号列Ｘが読み込まれた時点でその記号列Ｘを受理して記号列Ｙを出力する仮説の補正された累積重みは、
【数３】
2005257910.tif 000006
となり、先に述べた式（２）における二つのＷＦＳＴの累積重みの和の最小値と一致する。
従って、補正された累積重みを用いて、それを最小とする前段ＷＦＳＴの出力記号列Ｙを求めて、そのＹを後段ＷＦＳＴの入力記号列としたときの可能な状態遷移過程の中で累積重みが最小となる状態遷移過程に対応する出力記号列を記号列変換結果となる。
【００３８】
本発明では、各仮説に対応付けられた補助仮説リストを利用して仮説の補正を効率的に行う。
補正される仮説をｆとし、その補助仮説リストをＬ[ｆ]、仮説ｆの最後の状態遷移における出力記号をｙとする。
後段ＷＦＳＴの状態ｓB[ｇ]（ｇはＬ[ｆ]に含まれる一つの補助仮説を表す）から、入力記号ｙによる状態遷移ｅBを経て次状態ｎ[ｅB]  に至る補助仮説ｊを生成し、その到達状態をｓ[ｊ]＝ｎ[ｅB]とする。また、仮説ｆの状態遷移過程において、ｆの最後の状態遷移（ｅA）よりも前にあって前回補正計算が行われたときの到達状態をｔとする。
このとき、補助仮説ｊの累積重みＷ[ｊ]は、次の３つの要素を加算することにより計算できる。
（Ａ１）仮説ｆの状態遷移過程における状態ｔにおいて生成された補助仮説ｇの累積重み：
この値はＷ[ｇ]に等しい。つまり、出力記号がεであった状態遷移過程では、補助仮説リストはそのまま後に続く状態遷移過程の仮説に引く継がれるので、状態ｔにおいて生成された補助仮説リストはＬ[ｆ]に等しく、補助仮説リストＬ[ｆ]の個々の補助仮説の累積重みＷ[ｇ]をそのまま用いる。
（Ａ２）状態ｔから状態ｓA[ｆ]までの間に累積された重み：
但し、出力記号がεであった状態遷移過程では、補助仮説リストはそのまま新たに生成された仮説に引き継がれるので、状態ｔに至った仮説の補正された累積重みは、現在の補助仮説リストＬ[ｆ]の中で最小の累積重み、すなわち
【数４】
2005257910.tif 000007
（Ａ３）後段ＷＦＳＴの状態ｓB[ｇ]からｓB[ｊ]への状態遷移ｅBにおける重み：ｗ[ｅB]
従って、補助仮説ｊの累積重みはＷ[ｊ]＝Ｗ[ｇ]＋ＡＷ[ｆ]＋ｗ[ｅB]のように計算する。
そして、仮説ｆの補正は、Ｗ[ｆ]を新たに生成された補助仮説ｊの累積重みＷ[ｊ]の中で最小値
【数５】
2005257910.tif 000008
【００３９】
（仮説の補正手順）
以下、仮説の補正手順を図１１を用いて説明する。
この仮説補正手順は、図１０に示したステップS308において実行される。この手順において補正される仮説をｆ、前段ＷＦＳＴからの出力記号をｙ（＝ｏ[ｅA]）とする。
ステップS401では、仮説ｆを補正する手順を開始する。
ステップS402では、空の補助仮説リストＬ’を生成する。
ステップS403では、重みの補正項ＡＷ[ｆ]をＡＷ[ｆ]＝Ｗ[ｆ]−Ｗ[ｇ’]として求める。但し、ｇ’は、仮説ｆの補助仮説リストＬ[ｆ]の中で累積重みが最小の補助仮説を指す。
ステップS404では、Ｌ[ｆ]から補助仮説を一つ取り出し、ｇに代入する。状態ｓB[ｇ]から入力記号ｙで遷移可能な状態遷移のリストＥBを生成し、ステップS405に進む。
ステップ405では、ＥB＝φ（空のリスト）ならばS406に進む。そうでなければS409に進む。
ステップS406では、リストＥBから状態遷移を一つ取り出し、ｅBに代入する。
ステップS407では、補助仮説ｊを生成し、ｓB[ｊ]＝ｎ[ｅB]、Ｗ[ｊ]＝Ｗ[ｇ]＋ＡＷ[ｆ]＋ｗ[ｅB]、Ｏ[ｊ]＝Ｏ[ｇ]・ｏ[ｅB]とする。
ステップS408では、補助仮説ｊを補助仮説リストＬ’に挿入する。
ステップS405では、ＥBが空（ｓB[ｇ]からのすべての状態遷移に対して補助仮説を展開済み）であればS409に進む。そうでなければS406に戻り、次の状態遷移を調べる。
ステップS409では、Ｌ[ｆ]が空（すべての補助仮説を展開済み）であればS410に進む。そうでなければS404に戻り、次の仮説を展開する。
ステップS410では、新たに生成された補助仮説のリストＬ’の要素を、すでに空となった補助仮説リストＬ’[ｆ]にすべて移し、S411に進む。
ステップS411では、補助仮説リストＬ[ｆ]の中で累積重みが最初の補助仮説ｇ"に対してＷ[ｆ]＝Ｗ[ｇ"]とする。
ステップS412にて本発明の一実施の形態における仮説補正手順を終了する。
【００４０】
また、本発明では、仮説リストに仮説を挿入する場合、従来手法と同様に、仮説リスト内に前段ＷＦＳＴの同じ状態に到達している仮説が存在していれば、累積重みの小さい方を仮説リストに残し、仮説を絞り込む。但し、この仮説絞込みによって補助仮説が失われることがあるので、絞り込まれた仮説の補助仮説リストを、残った仮説の補助仮説リストに連結する。その際、補助仮説リスト内の補助仮説の累積重みを補正する必要がある。これは、仮説ｈと仮説ｆが前段ＷＦＳＴの同じ状態に到達しているとき、補助仮説の累積重みを
【数６】
2005257910.tif 000009
のように補正する。この補正は、先に示した仮説の補正手順における（Ａ１）と（Ａ２）の項を加えたものに等しい。そして、
Ｗ[ｈ]＜Ｗ[ｆ]  ならば  Ｌ[ｈ]＝Ｌ[ｈ]＋Ｌ[ｆ]、ｆを削除
Ｗ[ｈ]＞Ｗ[ｆ]  ならば  Ｌ[ｆ]＝Ｌ[ｈ]＋Ｌ[ｆ]、ｈを削除
のように補助仮説リストを連結する。
【００４１】
本発明による記号変換手順（図１０）は、仮説補正手順（ステップS309）を除けば前段のＷＦＳＴだけを用いて探索する手順（図４）とほぼ同じ計算手順となり、従来の記号列変換手順（図８）と比べて計算量を少なく抑えることができる。仮説補正手順における計算の負荷はあるが、前段のＷＦＳＴの状態遷移において出力記号がεでない場合においてのみ仮説補正手順が実行されるので、前段のＷＦＳＴの出力記号がεである割合が多いほど、処理量削減の効果は大きくなる。
【００４２】
（入力記号列“あ，め，だ，ま”が与えられた場合の出力記号列を求める過程）
次に、本発明の記号列変換手順に従って、図５をＷＦＳＴ Ａ、図６をＷＦＳＴ Ｂとして、入力記号列“あ，め，だ，ま”が与えられた場合の出力記号列を求める過程を順を追って説明する。但し、仮説（ＷＦＳＴ Ａの現状態番号ｓA、累積重みＷ、補助仮説リストＬ）は（ｓA，Ｗ，Ｌ）のように表し、補助仮説（ＷＦＳＴ Ｂの現状態番号ｓB、出力記号列Ｏ、累積重みＷ）は（ｓB，Ｏ，Ｗ）のように表す。また、補助仮説リストＬは｛（ｓB，Ｏ，Ｗ），（ｓ’B，Ｏ’，Ｗ’），・・・｝のように表す。
S301から開始し、S302で空の仮説リストＨとＨ’を作る。
S303により仮説リストＨの中に仮説（０，０，｛０，φ，０｝）を挿入する。
【００４３】
“あ”読み込み
S304で記号“あ”を読み込み、S305において仮説リストＨから仮説（０，０，｛０，φ，０｝）を取り出す。
この仮説のＷＦＳＴ Ａの現状０から入力記号が“あ”の状態遷移
＜０→１，あ：雨／０＞，
＜０→２，あ：飴／０＞
を含むリストＥAを作る。
S306でＥA＝φではないのでS307に進み、ＥAから状態遷移＜０→１，あ：雨／０＞を取り出し、S308で新たな仮説（１，０，｛０，φ，０｝）を生成する。S309で状態遷移＜０→１，あ：雨／０＞の出力記号はεではないので、仮説（１，０，｛０，φ，０｝）を補正する手順S401に進む。
S402で空の補助仮説リストＬ’を生成する。
S403で重みＡＷ＝０となる。
S404で補助仮説リストＬ＝｛（０，φ，０）｝から補助仮説（０，φ，０）を取り出し、ＷＦＳＴ Ｂの状態０から入力記号“雨”で遷移可能な状態遷移
＜０→１，雨：雨／０＞，
＜０→３，雨：雨／０＞
を含むリストＥBを作る。
S405でＥA＝φではないのでS406に進む。ＥAから状態遷移＜０→１，雨：雨／０＞を取り出し、S407で補助仮説（１，雨，０）を生成し、S408で補助仮説（１，雨，０）をＬ’に挿入する。
S405に戻り、ＥB＝φではないのでS406に進む。ＥBから状態遷移 ＜０→３，雨：雨／０＞を取り出し、S407で補助仮説（３，雨，０）を生成し、S408で補助仮説（３，雨，０）をＬ’に挿入する。
S405に戻り、ＥB＝φであるため、S409に進む。補助仮説リストＬ＝φなのでS410に進み、Ｌ’の要素（１，雨，０），（３，雨，０）をＬに移す。
S411において仮説の累積重みは０となり、S412で仮説の補正を終了する。この結果、仮説は｛１，０，（１，雨，０），（３，雨，０）｝となる。
【００４４】
S310に戻り、仮説（１，０，｛（１，雨，０），（３，雨，０）｝）をＨ’に挿入する。
S306に戻りＥA＝φではないのでS307に進み、ＥAから状態遷移＜０→２，あ：飴／０＞を取り出し、S308で新たな仮説（２，０，｛０，φ，０｝）を生成し、S309で状態遷移
＜０→２，あ：飴／０＞の出力記号はεではないので、仮説（２，０，｛０，φ，０｝）を補正するためS401に進む。
S402で空の補助仮説リストＬ’を生成する。
S403で重みＡＷ＝０となる。
S404で補助仮説リストＬ＝｛（０，φ，０）｝から補助仮説（０，φ，０）を取り出し、ＷＦＳＴ Ｂの状態０から入力記号“雨”で遷移可能な状態遷移
＜０→２，飴：飴／０＞，
＜０→４，飴：飴／０＞
を含むリストＥBを作る。
S405でＥB＝φではないのでS406に進む。ＥBから状態遷移＜０→２，飴：飴／０＞を取り出し、S407で補助仮説（２，飴，０）を生成し、S408で補助仮説（２，飴，０）をＬ’に挿入する。
S405に戻りＥB＝φではないのでS406に進む。ＥBから状態遷移＜０→４，飴：飴／０＞を取り出し、S407で補助仮説（４，飴，０）を生成し、S408で補助仮説（４，飴，０）をＬ’に挿入する。
S405に戻りＥB＝φであるため、S409に進む。補助仮説リストＬ＝φなのでS410に進み、Ｌ’の要素（２，飴，０），（４，飴，０）をＬに移す。
S411において仮説の累積重みは０となり、S412で仮説の補正を終了する。この結果、仮説は（２，０，｛（２，飴，０），（４，飴，０）｝）となっている。
S310に戻り、仮説（２，０，｛（２，飴，０），（４，飴，０）｝）をＨ’に挿入する。
S306に戻り、ＥA＝φであるため、S311に進む。Ｈ＝φであるためS312に進みＨ’内の仮説（１，０，｛（１，雨，０），（３，雨，０）｝）と（２，０，｛（２，飴，０），（４，飴，０）｝）をＨに移し、S313で次の入力記号が存在するのでS304の戻る。
【００４５】
“め”読み込み
続いて、S304で記号“め”を読み込み、S305において仮説リストＨから仮説（１，０，｛（１，雨，０），（１，１，雨，０）｝）を取り出す。この仮説のＷＦＳＴ Ａの現状態１から入力記号が“め”の状態遷移
＜１→５，め：ε／１＞
を含むリストＥAを作る。
S306でＥA＝φではないのでS307に進み、ＥAから状態遷移＜１→５，め：ε／１＞を取り出し、S308で新たな仮説（５，１，｛（１，雨，０），（１，雨，０）｝）を生成し、、S309に進む。
状態遷移＜１→５，め：ε／１＞の出力記号はεであるため、次のS310に進み仮説（５，１，｛（１，雨，０），（１，雨，０）｝）をＨ’に挿入する。
S306に戻りＥA＝φであるためS311に進む。Ｈ≠φであるためS305に戻り、仮説リストＨから仮説（２，０，｛（２，飴，０），（４，飴，０）｝）を取り出す。この仮説の現状態２から入力記号が“め”の状態遷移
（＜２→５，め：ε／２＞，φ）
を含むリストＥAを作る。
【００４６】
S306でＥA＝φでないのでS307に進み、ＥAから状態遷移＜２→５，め：ε／２＞を取り出し、S308で新たな仮説（５，２，｛（２，飴，０），（４，飴，０）｝）を生成し、S309に進む。
状態遷移＜２→５，め：ε／２＞の出力記号はεであるため、次のS310に進み仮説（５，２，｛（２，飴，０），（４，飴，０）｝）をＨ’に挿入する。
但し、Ｈ’は既に仮説（５，１，｛（１，雨，０），（１，雨，０）｝）が存在し、ＷＦＳＴ Ａにおける到達状態が５であるため累積重みの小さい仮説（５，１，｛（１，雨，０），（１，雨，０）｝）を残し、仮説（５，２，｛（２，飴，０），（４，飴，０）｝）は削除するが、補助仮説リストは連結させて、仮説を（５，１，｛（１，雨，１），（１，雨，１），（２，飴，２），（４，飴，２）｝）のようにする。
S306に戻りＥA＝φであるためS311に進む。Ｈ＝φであるためS312に進みH’内の仮説（５，１，｛（１，雨，１），（１，雨，１），（２，飴，２），（４，飴，２）｝）をＨに移し、S313で次の入力記号が存在するのでS304に戻る。
【００４７】
“だ”読み込み
続いて、S304で記号“だ”を読み込み、S305において仮説リストＨから仮説（５，１，｛（１，雨，１），（１，雨，１），（２，飴，２），（４，飴，２）｝）を取り出す。この仮説のＷＦＳＴ Ａの現状態５から入力記号が“だ”の状態遷移
＜０→４，だ：玉／１＞
を含むリストＥAを作る。ここで、ＷＦＳＴ Ａの現状態５から状態０へは入力記号なしで遷移できるので、ＥAに含まれるＷＦＳＴ Ａの状態遷移は＜０→４，だ：玉／１＞となっている。
S306でＥA＝φではないのでS307に進み、ＥAから状態遷移＜０→４，だ：玉／１＞を取り出し、S308で新たな仮説（４，２，｛（１，雨，１），（１，雨，１），（２，飴，２），（４，飴，２）｝）を生成し、S309で状態遷移＜０→４，だ：玉／１＞の出力記号はεではないので、仮説（４，２，｛（１，雨，１），（３，雨，１），（２，飴，２），（４，飴，２）｝）を補正するためS401に進む。
S402で空の補助仮説リストＬ’を生成する。
S403で重みＡＷ[ｆ]＝２−min（１，１，２，２）＝１となる。
S404で補助仮説リストＬ＝｛（１，雨，１），（３，雨，１），（２，飴，２），（４，飴，２）｝から補助仮説（１，雨，１）を取り出し、ＷＦＳＴ Ｂの状態１から入力記号“玉”で遷移可能な状態遷移
＜１→４，玉：玉／５＞
を含むリストＥBを作る。
【００４８】
S405でＥB＝φではないのでS406に進む。ＥBから状態遷移＜１→４，玉：玉／５＞を取り出し、S407で補助仮説（４，雨玉，７）を生成する。ここで、補助仮説の累積重みは
Ｗ[ｇ]＋ＡＷ[ｆ]＋ｗ[ＥB]＝１＋１＋５＝７
のように計算されている。そして、S408で補助仮説（４，雨玉，７）をＬ’に挿入する。
S405に戻りＥB＝φであるため、S409に進む。
Ｌ＝φではないのでS404に進み、補助仮説（３，雨，１）を取り出し、ＷＦＳＴ Ｂの状態３から入力記号“玉”で遷移可能な状態遷移は存在しないのでＥB＝φとする。
S405に戻りＥB＝φであるためS409に進む。補助仮説リストＬ＝φではないのでS404に進み、補助仮説（２，飴，２）を取り出し、ＷＦＳＴ Ｂの状態２から入力記号“玉”で遷移可能な状態遷移
＜２→４，玉：玉／１＞
を含むリストＥBを作る。
S405でＥB＝φでないのでS406に進む。ＥBから状態遷移＜２→４，玉：玉／１＞を取り出し、S407で補助仮説（４，飴玉，４）を生成する。ここで、補助仮説の累積重みは
Ｗ[ｇ]＋ＡＷ[ｆ]＋ｗ[ＥB]＝２＋１＋１＝４
のように計算されている。
S408で補助仮説（４，飴玉，４）にＬ’に挿入する。このときＬ’には補助仮説（４，雨玉，７）が存在するので累積重みの小さい補助仮説（４，飴玉，４）を残し、（４，雨玉，７）は削除する。
【００４９】
S405に戻りＥB＝φであるため、S409に進む。
Ｌ＝φではないのでS404に進み、補助仮説（４，飴，２）を取り出し、ＷＦＳＴ Ｂの状態４から入力記号“玉”で遷移可能な状態遷移は存在しないのでＥB＝φとする。
S405に戻りＥB＝φであるため、S409に進む。補助仮説リストＬ＝φなのでS410に進み、L’の要素（４，飴玉，３）をＬに移す。
S411において仮説の累積重みは４となり、S412で仮説の補正を終了し、結果として、仮説は（４，４，｛（４，飴玉，４）｝）となる。
S310に戻って仮説（４，４，｛（４，飴玉，４）｝）をＨ’に挿入する。
S306に戻りＥA＝φであるためS311に進む。Ｈ＝φであるためS312に進みＨ’内の仮説（４，４，｛（４，飴玉，４）｝）をＨに移し、S313で次の入力記号が存在するのでS304に戻る。
【００５０】
“ま”読み込み
続いて、S304で記号“ま”を読み込み、S305において仮説リストＨから仮説（４，４，｛（４，飴玉，４）｝）を取り出す。この仮説はＷＦＳＴ Ａの現状態１から入力記号が“ま”の状態遷移
＜４→５，ま：ε／１＞
を含むリストＥAを作る。
S306でＥA＝φではないのでS307に進みＥBから状態遷移＜４→５，ま：ε／１＞を取り出し、S308で新たな仮説（５，５，｛（４，飴玉，４）｝）を生成し、S309に進む。
状態遷移＜４→５，ま：ε／１＞の出力記号はεであるため、次のS310に進み仮説５，５，｛（４，飴玉，４）｝）をＨ’に挿入する。
S306に戻りＥA＝φであるためS311に進む。Ｈ＝φであるためS312に進みＨ’内の仮説（５，５，｛（４，飴玉，４）｝）をＨに移し、S313で次の入力が存在しないのでS314に進む。
S314で、Ｈ内の仮説（５，５，｛（４，飴玉，４）｝）が終了状態に到達した唯一の仮説であり、その仮説の補助仮説の出力記号列“飴玉”を変換結果として出力し、S315で記号列変換処理を終了する。
【００５１】
（音声認識）
一方、本発明を音声認識に適用し、効率的に音声認識を行うこともできる。
図１２は、本発明の一実施の形態である。
音声を入力する音声信号入力部４０１から送られた音声信号はその音声の短時間音響パターンの時系列を記号列として抽出する音声特徴記号列抽出部４０５において音響特徴記号列に変換し、その音響特徴記号列を入力として本発明による記号列変換を行う記号列変換部１０２に送る。続いて、記号列変換部１０２では、音響モデル格納部４０１から音声固定単位（例えば音素）の標準的特徴を音声信号をある短い時間（例えば１０ミリ秒）ごとに分析して得られる音響パターンの系列の照合により与える音響モデルを、単語発音辞書格納部４０２からは種々の単語の発音を前記音声固定単位の系列によって与える単語発音辞書を、音声認識用言語格納部４０３からは発話される単語の連接のしやすさを与える言語モデルを読み出し、音響特徴記号列抽出部４０１から送られた音響特徴記号列を読み込み、累積重み最小の出力記号列を求め、記号列出力部１０６に送る。記号列出力部１０６では、受け取った出力記号列を音声認識結果として出力する。
【００５２】
音声認識用の単語発音辞書や言語モデルをＷＦＳＴによって記述する方法は、例えば、国際会議ＡＳＲ２０００における、M. Mohri, F.Pereira, M. Riley著“Weighted finite-state transducers in speech recognition ”,Proceeding of ASR2000, pp.97-106,2000に開示されている。
種々の音声固定単位（例えば音素）の標準的な音響パターン系列の集合を表す音響モデルとしては、例えば、それら音響パターンの系列の集合を確率・統計理論に基づいてモデル化する隠れマルコフモデル法（Hidden Markov Model,以後ＨＭＭと呼ぶ）が主流である。このＨＭＭ法の詳細は、例えば、社団法人電子情報通信学会、中川聖一著「確率モデルによる音声認識」に開示されている。
音声認識の場合は、前段のＷＦＳＴの重みとして、音響モデルによって計算される音響特徴記号（音響パターン）のスコアを用いる。ただし、このスコアは、大きいほど入力音響パターンが音響モデルによって表される音声固定単位に近いことを表すので、マイナスの音響スコアをもって重みとする。隠れマルコフモデルによる音響スコアの計算では、例えばガウス分布に基づく確率値が用いられる。
音声認識に用いる音響パターンには、短い時間（例えば１０ミリ秒）ごとに音声信号を分析することにより得られるメルケプストラム(mel-frequency cepstral coefficients, ＭＦＣＣと呼ばれる)、デルタＭＦＣＣ、ＬＰＣケプストラム、対数パワーなどがある。
【図面の簡単な説明】
【００５３】
【図１】重み付き有限状態変換器の一例を表す図。
【図２】図１の重み付き有限状態変換器を表によって定義した図。
【図３】重み付き有限状態変換器による記号変換方法の実施の形態を表す図。
【図４】重み付き有限状態変換器による記号変換方法の手順を説明する図。
【図５】仮名の系列を表す記号列を、その仮名に対応する漢字の系列に変換する重み付き有限状態変換器の一例を表す図。
【図６】日本語における漢字の系列の接続の可能性を重みによって与える重み付き有限状態変換器の一例を表す図。
【図７】二つの重み付き有限状態変換器による従来の記号列変換方法の実施の形態を表す図。
【図８】二つの重み付き有限状態変換器による記号列変換方法の手順を説明する図。
【図９】本発明における二つの重み付き有限状態変換器による記号列変換方法の実施の形態を表す図。
【図１０】本発明における二つの重み付き有限状態変換器による記号列変換方法の手順を説明する図。
【図１１】本発明における二つの重み付き有限状態変換器による記号列変換方法における仮説の補正方法を説明する図。
【図１２】本発明における二つの重み付き有限状態変換器による記号列変換方法を音声認識の方法として用いた場合の一実施の形態を表す図。
【符号の説明】
【００５４】
１０    状態
１１    終了状態
１２    状態遷移
１０１    ＷＦＳＴ格納部
１０２    記号列変換部
１０３    記号列入力部
１０４    仮説展開部
１０５    仮説絞込み部
１０６    記号列出力部
２０１    前段ＷＦＳＴ格納部
２０２    後段ＷＦＳＴ格納部
３０１    仮説補正部
４０１    音響モデル格納部
４０２    単語辞書ＷＦＳＴ格納部
４０３    言語モデルＷＦＳＴ格納部
４０４    音声信号入力部
４０５    音声特徴記号列抽出部
【図１】
2005257910.tif 000010
【図２】
2005257910.tif 000011
【図３】
2005257910.tif 000012
【図４】
2005257910.tif 000013
【図５】
2005257910.tif 000014
【図６】
2005257910.tif 000015
【図７】
2005257910.tif 000016
【図８】
2005257910.tif 000017
【図９】
2005257910.tif 000018
【図１０】
2005257910.tif 000019
【図１１】
2005257910.tif 000020
【図１２】
2005257910.tif 000021