(57)【要約】【課題】NグラムモデルおよびバックオフNグラムモデルを従来技術よりも早くWFSTに変換して記号列変換に利用する方法を提供する。【解決手段】記号列変換方法は、入力記号列の記号と現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている記号列モデル格納部を参照して、現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得ステップと、状態遷移集合取得ステップで取得した遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説展開ステップと、を含む。【選択図】図８
2015040864.tif 000002
【特許請求の範囲】
【請求項１】
入力記号列を出力記号列に変換する記号列変換方法であって、
前記入力記号列の先頭から順に１つずつ記号を取得する記号列取得ステップと、
前記記号列取得ステップで取得した記号と現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている記号列モデル格納部を参照して、前記現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得ステップと、
前記状態遷移集合取得ステップで取得した前記遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説展開ステップと、
前記仮説展開ステップで更新した仮説の集合のうち同じ状態に到達している仮説の中で累積重みが最大または最小となるものから所定数の仮説以外の仮説を削除することにより仮説を絞り込み、前記記号列取得ステップにおいて前記入力記号列が最後まで読み込まれていれば、終了状態に到達している仮説の中から前記累積重みが最大または最小となる仮説を前記出力記号列として求める仮説絞り込みステップと、
を含む記号列変換方法。
【請求項２】
請求項１記載の記号列変換方法であって、
前記連鎖確率は、ある記号が生起する確率、及び、１以上の記号からなる記号列に依存してある記号が生起する確率であり、
前記記号列モデル格納部には、前記連鎖確率に加えて、各連鎖確率に対応する記号列のバックオフ係数が対応付けて記憶されており、
前記状態遷移集合取得ステップは、
累積バックオフ係数の初期値を設定する初期値設定ステップと、
前記遷移元の状態に対応する記号列に依存して前記入力された記号が生起する確率に対応する第１確率が前記記号列モデル格納部に存在する場合に、その第一確率を取得する第１確率取得ステップと、
前記第１確率が存在しない場合、または、所定の閾値より小さい場合に、前記遷移元の状態に対応する記号列のバックオフ係数を前記記号列格納部から取得し、取得したバックオフ係数を前記累積バックオフ係数に乗じることにより、前記累積バックオフ係数を更新する累積バックオフ係数更新ステップと、
前記第１確率が存在する場合、または、所定の閾値以上の場合に、前記第１確率と前記累積バックオフ係数との積に対応する値である第２確率を、前記現在の仮説の集合の各仮説が到達している状態から前記入力された記号へ遷移する状態遷移の状態遷移確率として設定する状態遷移確率設定ステップと、
を含む、記号列変換方法。
【請求項３】
請求項１または２記載の記号列変換方法において、
前記記号列モデル格納部に含まれる全ての記号列の情報とその連鎖確率をコンピュータのメモリ上に連続させて格納されており、
各記号列のメモリアドレス番号から任意の起点となるアドレス番号を差し引いた相対アドレス番号に比例する値をもって前記状態情報とする、
記号列変換方法。
【請求項４】
請求項１乃至３の何れかに記載の記号列変換方法において、
前記記号列モデルに対応するWFSTとは別の一つ以上のWFSTを用いて前記入力記号列とは別の入力記号列である第２入力記号列を変換することにより得た仮説の集合に含まれるいずれかの仮説の状態遷移過程から出力される記号列が、前記記号列モデルに対する入力記号列である、
記号列変換方法。
【請求項５】
音声から得られる音響特徴記号列を音声認識結果に変換する音声認識方法であって、
前記音響特徴記号列の先頭から順に１つずつ記号を取得する記号列取得ステップと、
音響モデルによって計算される音響特徴記号のスコアを、重みとして用いる単語辞書WFSTを参照して、現在の仮説の集合の各々に新しい状態遷移を追加する仮説展開ステップと、
前記仮説展開ステップで状態遷移を追加された仮説の集合の各々の状態遷移過程から出力される記号列と、現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている言語モデル格納部を参照して、前記現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得ステップと、
前記状態遷移集合取得ステップで取得した前記遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説補正ステップと、
前記仮説展開ステップで更新した仮説の集合のうち同じ状態に到達している仮説の中で累積重みが最大または最小となるものから所定数の仮説以外の仮説を削除することにより仮説を絞り込み、前記記号列取得ステップにおいて前記入力記号列が最後まで読み込まれていれば、終了状態に到達している仮説の中から前記累積重みが最大または最小となる仮説を前記音声認識結果として求める仮説絞り込みステップと、
を含む音声認識方法。
【請求項６】
入力記号列を出力記号列に変換する記号列変換装置であって、
前記入力記号列の先頭から順に１つずつ記号を取得する記号列取得部と、
前記記号列取得部で取得した記号と現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている記号列モデル格納部を参照して、前記現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得部と、
前記状態遷移集合取得部で取得した前記遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説展開部と、
前記仮説展開部で更新した仮説の集合のうち同じ状態に到達している仮説の中で累積重みが最大または最小となるものから所定数の仮説以外の仮説を削除することにより仮説を絞り込み、前記記号列取得部において前記入力記号列が最後まで読み込まれていれば、終了状態に到達している仮説の中から前記累積重みが最大または最小となる仮説を前記出力記号列として求める仮説絞り込み部と、
を含む記号列変換装置。
【請求項７】
音声から得られる音響特徴記号列を音声認識結果に変換する音声認識装置であって、
前記音響特徴記号列の先頭から順に１つずつ記号を取得する記号列取得部と、
音響モデルによって計算される音響特徴記号のスコアを、重みとして用いる単語辞書WFSTを参照して、現在の仮説の集合の各々に新しい状態遷移を追加する仮説展開部と、
前記仮説展開部で状態遷移を追加された仮説の集合の各々の状態遷移過程から出力される記号列と、現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている言語モデル格納部を参照して、前記現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得部と、
前記状態遷移集合取得部で取得した前記遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説補正部と、
前記仮説展開部で更新した仮説の集合のうち同じ状態に到達している仮説の中で累積重みが最大または最小となるものから所定数の仮説以外の仮説を削除することにより仮説を絞り込み、前記記号列取得部において前記入力記号列が最後まで読み込まれていれば、終了状態に到達している仮説の中から前記累積重みが最大または最小となる仮説を前記音声認識結果として求める仮説絞り込み部と、
を含む音声認識装置。
【請求項８】
請求項１乃至４の何れか記載の記号列変換方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記号列を変換するための記号列変換規則を表す重み付き有限状態変換器(Weighted Finite-State Transducer、以下「WFST」ともいう)を参照しながら、ある入力記号列が与えられたときに、そのWFSTの様々な状態遷移過程の中から、累積重みが最小または最大となる状態遷移過程を探索し、その状態遷移過程の出力記号列を変換結果として出力する記号列変換技術、並びに、入力記号列が音声信号を表す特徴量ベクトルの系列であり、出力記号列が単語列であるような音声認識技術に関する。
【背景技術】
【０００２】
WFSTとは、ある記号列を別の記号列に変換するための規則を、状態と状態遷移の図に表現する方式を言う。
【０００３】
従来、音声認識において、入力音声の音響パターンを表す記号列（特徴量ベクトルの系列）を入力とし、その音響パターンに対応する単語列を出力とするWFSTに、バックオフNグラムモデルで表される言語モデルのWFSTを合成して、記号列変換を行うことで、音響的にも言語的にも妥当な単語列（音声認識結果）を求める方法が知られている（非特許文献１及び特許文献１参照）。
【０００４】
なお、言語モデルとしてのNグラムモデルとは、単語の連接のしやすさをＮ−１重のマルコフ過程で表すモデルであり、登録単語数を|V|とすると|V|N個の確率値を持つ。WFSTで表せば|V|N個の状態遷移が必要となる。そのようなWFSTは非現実的であるため、WFSTによる音声認識においてはバックオフNグラムモデルを用いる。バックオフNグラムモデルとは、Nグラムモデルの一種であって、Nグラム確率が学習データの不足等により精度よく推定できない場合に、より精度よく推定されたN-1グラム確率等を用いるモデルである。例えば、Nグラム確率が０になってしまう場合はN-1グラム確率、N-1グラム確率が０になってしまう場合はN-2グラム確率、というようにバックオフ（後退）する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５-２５７９１０号公報
【非特許文献】
【０００６】
【非特許文献１】堀，塚田，「重み付き有限状態トランスデューサによる音声認識」, 情報処理学会誌 Vol. 45, No.10, Oct. 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１や特許文献１では、WFSTによる記号列変換にバックオフNグラムを用いる場合は、バックオフNグラムモデルを予めWFSTに変換しておく必要がある。そして、そのWFSTを用いて、任意の入力記号列を効率的に変換する。しかし、バックオフNグラムモデルに何らかの修正を施すと、その都度、WFSTに変換し直す必要がある。そのため、バックオフNグラムモデルを予めWFSTに変換するために一定の処理時間が発生する。例えば、音声認識において、特定の話題の単語がよく認識できるように言語モデルのNグラム確率を調整する場合がある。この場合、調整が一部の確率の修正であっても、音声認識を実行する前にその言語モデル全体をWFSTに変換し直さなければならない。これは、音声認識などを実際に利用する際に、即時性を損なう結果となる。
【０００８】
また、言語モデルの確率値を動的に変更したい場合がある。例えば、音声認識を利用する際に、ある特定の話題に関連した単語が話されやすいことが分かった時点で、即座にその情報を音声認識システムに反映したい場合である。
【０００９】
このような動的な言語モデルを用いる場合、確率値が変更されるたびにWFSTの重みに反映する計算コストは大きい。また、WFSTの重みに反映する場合は変更された確率だけでなく、バックオフ係数も改めて計算し直す必要がある。音声認識では、数百万から数千万のNグラム確率を持つ言語モデルを利用するため、この計算は非常に大きく、言語モデルを動的に更新しても、すぐには音声認識を始められないという問題がある。
【００１０】
そして、NグラムモデルおよびバックオフNグラムモデルを瞬時にWFSTに変換して記号列変換に利用する方法は知られていない。
【００１１】
本発明は、NグラムモデルおよびバックオフNグラムモデルを従来技術よりも早くWFSTに変換して記号列変換に利用する方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の課題を解決するために、本発明の第一の態様によれば、記号列変換方法入力記号列を出力記号列に変換する。記号列変換方法は、入力記号列の先頭から順に１つずつ記号を取得する記号列取得ステップと、記号列取得ステップで取得した記号と現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている記号列モデル格納部を参照して、現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得ステップと、状態遷移集合取得ステップで取得した遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説展開ステップと、仮説展開ステップで更新した仮説の集合のうち同じ状態に到達している仮説の中で累積重みが最大または最小となるものから所定数の仮説以外の仮説を削除することにより仮説を絞り込み、記号列取得ステップにおいて入力記号列が最後まで読み込まれていれば、終了状態に到達している仮説の中から累積重みが最大または最小となる仮説を出力記号列として求める仮説絞り込みステップと、を含む。
【００１３】
上記の課題を解決するために、本発明の他の態様によれば、音声認識方法は、音声から得られる音響特徴記号列を音声認識結果に変換する。音声認識方法は、音響特徴記号列の先頭から順に１つずつ記号を取得する記号列取得ステップと、音響モデルによって計算される音響特徴記号のスコアを、重みとして用いる単語辞書WFSTを参照して、現在の仮説の集合の各々に新しい状態遷移を追加する仮説展開ステップと、仮説展開ステップで状態遷移を追加された仮説の集合の各々の状態遷移過程から出力される記号列と、現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている言語モデル格納部を参照して、現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得ステップと、状態遷移集合取得ステップで取得した遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説補正ステップと、仮説展開ステップで更新した仮説の集合のうち同じ状態に到達している仮説の中で累積重みが最大または最小となるものから所定数の仮説以外の仮説を削除することにより仮説を絞り込み、記号列取得ステップにおいて入力記号列が最後まで読み込まれていれば、終了状態に到達している仮説の中から累積重みが最大または最小となる仮説を音声認識結果として求める仮説絞り込みステップと、を含む。
【００１４】
上記の課題を解決するために、本発明の他の態様によれば、記号列変換装置は、入力記号列を出力記号列に変換する。記号列変換装置は、入力記号列の先頭から順に１つずつ記号を取得する記号列取得部と、記号列取得部で取得した記号と現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている記号列モデル格納部を参照して、現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得部と、状態遷移集合取得部で取得した遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説展開部と、仮説展開部で更新した仮説の集合のうち同じ状態に到達している仮説の中で累積重みが最大または最小となるものから所定数の仮説以外の仮説を削除することにより仮説を絞り込み、記号列取得部において入力記号列が最後まで読み込まれていれば、終了状態に到達している仮説の中から累積重みが最大または最小となる仮説を出力記号列として求める仮説絞り込み部と、を含む。
【００１５】
上記の課題を解決するために、本発明の他の態様によれば、音声認識装置は、音声から得られる音響特徴記号列を音声認識結果に変換する。音声認識装置は、音響特徴記号列の先頭から順に１つずつ記号を取得する記号列取得部と、音響モデルによって計算される音響特徴記号のスコアを、重みとして用いる単語辞書WFSTを参照して、現在の仮説の集合の各々に新しい状態遷移を追加する仮説展開部と、仮説展開部で状態遷移を追加された仮説の集合の各々の状態遷移過程から出力される記号列と、現在の仮説の集合の各仮説が到達している状態を特定する情報である状態情報とを入力として、１つ以上の記号からなる記号列の生起確率または連鎖確率が記号列モデルとして記憶されている言語モデル格納部を参照して、現在の仮説が到達している状態を遷移元として、当該遷移元から遷移可能な状態遷移およびその状態遷移確率を取得する状態遷移集合取得部と、状態遷移集合取得部で取得した遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮説を更新する仮説補正部と、仮説展開部で更新した仮説の集合のうち同じ状態に到達している仮説の中で累積重みが最大または最小となるものから所定数の仮説以外の仮説を削除することにより仮説を絞り込み、記号列取得部において入力記号列が最後まで読み込まれていれば、終了状態に到達している仮説の中から累積重みが最大または最小となる仮説を音声認識結果として求める仮説絞り込み部と、を含む。
【発明の効果】
【００１６】
本発明によれば、NグラムモデルおよびバックオフNグラムモデルを従来技術よりも早くWFSTに変換して記号列変換に利用することができる。
【図面の簡単な説明】
【００１７】
【図１】WFSTの一例を示す図。
【図２】WFSTを表によって示す図。
【図３】一つのWFSTを用いた記号列変換の一例を示す図。
【図４】WFSTを用いた記号列変換手順を示す図。
【図５】記号列トライグラムの状態と状態遷移の例を示す図。
【図６】記号列トライグラムのバイグラムへのバックオフを表す状態と状態遷移の例を示す図。
【図７】記号列トライグラムのユニグラムへのバックオフを表す状態と状態遷移の例を示す図。
【図８】第一実施形態に係る記号列変換装置の機能ブロック図。
【図９】状態遷移集合取得手段８０９の処理フローの一例を示す図。
【図１０】第一実施形態に係る記号列変換装置において、記号列トライグラムのバイグラムへのバックオフを表す状態と状態遷移の例を示す図。
【図１１】第一実施形態に係る記号列変換装置において、記号列トライグラムのユニグラムへのバックオフを表す状態と状態遷移の例を示す図。
【図１２】記号列バックオフトライグラムのデータ構造の一例を示す図。
【図１３】第二実施形態に係る音声認識装置の機能ブロック図。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態について説明する。なお、以下の説明に用いる図面では、同じ機能を持つ構成部や同じ処理を行うステップには同一の符号を記し、重複説明を省略する。以下の説明において、テキスト中で使用する記号「^」、「~」、「−」等は、本来直前の文字の真上に記載されるべきものであるが、テキスト記法の制限により、当該文字の直後に記載する。式中においてはこれらの記号は本来の位置に記述している。また、ベクトルや行列の各要素単位で行われる処理は、特に断りが無い限り、そのベクトルやその行列の全ての要素に対して適用されるものとする。
【００１９】
＜第一実施形態のポイント＞
記号列モデルを表すバックオフNグラムモデルのWFSTは事前に構築せず、入力記号列が与えられ、その記号列変換を行う過程で、必要な状態番号や状態遷移を必要な時にバックオフNグラムモデルからWFSTに変換して取り出す。
【００２０】
すなわち、バックオフNグラムモデルからWFSTの初期状態の番号を取得する初期状態取得手段と、WFSTの任意の状態番号と入力記号が与えられたときに、その与えられた状態番号に対応する状態を遷移元とする状態遷移の集合を取得する状態遷移集合取得手段と、WFSTの任意の状態番号が与えられたときに、その与えられた状態番号（状態を特定する情報という意味で状態情報ともいう）に対応する状態がWFSTの終了状態か否かを判定する終了状態判定手段を用意し、記号列変換の際に記号列モデルのWFSTを参照するために、初期状態取得手段、状態遷移集合取得手段、終了状態判定手段を呼び出すことで、記号列モデルのWFSTの必要な状態遷移だけを参照要求に応じて生成し、その生成された状態遷移の集合を用いて記号列を変換する。
【００２１】
＜前提知識＞
第一実施形態について説明する前に、その前提となる知識について説明する。
WFSTは、(1)状態と、(2)状態から状態へと遷移できることを表す状態遷移、(3)状態遷移において受理される入力記号、(4)その際に出力される出力記号、及び、(5)その状態遷移の重みの集合によって定義される。WFSTは、ある入力記号列が与えられたときに、初期状態からその入力記号列の記号を順に受理する状態遷移に従って出力記号を出力しながら状態遷移を繰り返し、終了状態に達すると終了するモデルである。形式的にはWFSTは次の８つの組（Ｑ，Σ，△，ｉ，Ｆ，Ｅ，λ，ρ）によって定義される。
１．Ｑは有限の状態の集合。
２．Σは入力記号の有限の集合。
３．△は出力記号の有限の集合。
４．ｉ∈Ｑは初期状態。
５．Ｆ∈Ｑは終了状態の集合。
６．Ｅ∈Ｑ×Σ×△×Ｑは、現状態から入力記号により、出力記号を出力して次状態に遷移する状態遷移の集合。
７．λは初期重み。
８．ρ（ｑ）は終了状態ｑの終了重み。ｑ∈Ｆ。
【００２２】
WFSTの一例を図１に示す。
図１において、１０は、マル（“○”）で表された状態を示しており、そのマルの中の数字はその状態の番号を表している。１１は、二重マル（“◎”）で表された終了状態を示しており、その二重マルの中の数字は、その終了状態の番号と状態遷移が終了して最後に累積される終了重みが“（状態番号）／（終了重み）”のように表されている。以後、状態の番号を用いて状態を指し示す場合は、単に状態とその番号を用いて“状態０”や“状態３”のように称す。１２は、各状態を結ぶ矢印（“→”）で表された状態遷移を示しており、各々の状態遷移に付与された記号や数字は、その状態遷移に関連付けられた入力記号、出力記号、重みを“（入力記号）：（出力記号）／（重み）”のように表したものである。
【００２３】
図２のように、図１のWFSTを表によって定義することもできる。図２は、各行が一つの状態遷移を表し、その状態遷移における遷移元（現状態）の状態番号と遷移先（次状態）の状態番号、入力記号、出力記号、重みが記されている。最終状態（図１では状態３）は、遷移先、入力記号、出力記号を空とし、状態遷移終了時に累積される重み（終了重み）を記されている。一般に、WFSTの初期状態は状態０とされ、初期重みλも省略されることが多い。そのため、本実施形態でも初期状態を状態０とし、初期重みを省略して明記しないこととする。
【００２４】
図１のWFSTは、例えば、入力記号列ａ，ａ，ｂ，ｃを出力記号列ｄ，ｄ，ｃ，ｂに変換することができ、その際の状態遷移過程は、状態番号の系列を用いて表すと０，０，１，３であり、重みの累積値（以下「累積重み」と称す）は、０．５＋０．５＋０．３＋１＋０．５＝２．８となる。しかし、図１のWFSTでは、ａ，ａ，ｂ，ｃという入力記号列に対しては、０，０，１，３と０，０，２，３の２通りの状態遷移過程が考えられる。一般に、ある入力記号列に対して複数の状態遷移の可能性がある場合（これを非決定性という）は、状態遷移過程における累積重みが最小または最大になる状態遷移過程を選択し、その累積重みが最小または最大の状態遷移過程に対応する出力記号列を選択する。状態遷移の可能性が高いものに対してより大きい重みを設定する場合には、累積重みが最大の状態遷移過程に対応する出力記号列を選択し、状態遷移の可能性が高いものに対してより小さい重みを設定する場合には、累積重みが最小の状態遷移過程に対応する出力記号列を選択すればよい。図１の例においても、ａ，ａ，ｂ，ｃという入力記号列に対して累積重みが最も小さい状態遷移過程０，０，１，３を選んで、変換結果をｄ，ｄ，ｃ，ｂとする。
【００２５】
ある重み付き有限状態変換器Ａがあり、この重み付き有限状態変換器Ａに対して記号列Ｘが入力記号列として与えられたとき、累積重みが最小となる出力記号列（すなわち記号列変換結果）を求めるには、次の累積重みの最小値Ｗ（Ｘ）を計算する必要がある。
【数１】
2015040864.tif 000003
ここで、Ｗ（Ｘ→Ｙ；Ａ）は、重み付き有限状態変換器Ａによって記号列Ｘが記号列Ｙに変換されるときの状態遷移過程における累積重みを表す。この累積重みＷ（Ｘ→Ｙ；Ａ）の最小値Ｗ（Ｘ）を求めて、その最小値を与える記号列Ｙが記号列変換結果となる。この記号列変換結果を求めるには、入力記号列によって初期状態から終了状態に至るコスト（累積重み）が、最小または最大の状態遷移過程を探し出すことによって行われる。この手順は、例えば、特許文献１に開示されている。
【００２６】
一つのWFSTを用いた記号列変換の一例を図３に示す。
まず、本明細書において、“仮説”とは、ある記号列を構成する記号が順に入力され（読み込まれ）、現時点までに読み込まれた入力記号列に対して、WFSTにおいて初期状態からその入力記号列によって状態遷移を繰り返した場合の可能性のある一つの状態遷移過程を表すものとする。
【００２７】
記号列取得部１０３は、入力記号列を構成する記号を先頭から順に一つずつ読み込み（取得し）、仮説展開部１０４に送る。
【００２８】
仮説展開部１０４は、記号列取得部１０３で取得した記号とＷＦＳＴ格納部１０１から読み込んだＷＦＳＴに従って、これまで読み込んだ記号列に対する仮説の集合を新たに受け取った記号を用いて各仮説の状態遷移過程を更新することにより新たな仮説を生成し、仮説絞込み部１０５に送る。
【００２９】
仮説絞込み部１０５は、仮説展開部１０４から受け取った仮説の集合に対し、同じ状態に到達している仮説の中で累積重みが最小または最大の仮説以外の仮説を削除することにより仮説を絞り込む。仮説絞込み部１０５は、入力記号列が最後まで読み込まれていれば、累積重みが最小または最大の仮説に対応する出力記号列を記号列出力部１０６に送る。入力記号列が最後まで読み込まれていなければ、仮説を仮説展開部１０４に送る。
【００３０】
記号列出力部１０６は、仮説絞込み部１０５から受け取った出力記号列を記号列変換結果として出力する。
【００３１】
次に、この実施の形態に基づいて記号列を変換する手順の一例を示す。
まず、WFSTのある状態遷移をｅと表すとき、ｎ[ｅ]を遷移先の状態（次状態）、ｉ[ｅ]を入力記号、ｏ[ｅ]を出力記号、ｗ[ｅ]を重みと定義する。また、ある仮説をｈと表わすとき、ｓ[ｈ]をその状態遷移過程において到達している状態、Ｗ[ｈ]をその状態遷移過程における累積重み、Ｏ[ｈ]をその状態遷移過程において出力されている記号列とする。
【００３２】
この手順において、仮説は仮説のリスト（以後これを「仮説リスト」と呼ぶ）を用いて管理する。仮説リストに対し、仮説を挿入したり、仮説を取り出したりすることができる。但し、仮説リストに仮説を挿入する場合に、仮説リスト内に同じ状態に到達している仮説があれば、累積重みの小さいほうまたは大きいほうだけを仮説リストに残し、仮説を絞り込む。
【００３３】
WFSTを用いた記号列変換手順を図４に示す。
以下、WFSTを用いる記号列変換の例（図３）の各部がどのような手順で処理を行うか、図４を用いて説明する。
【００３４】
ステップＳ１０１より開始し、初期設定として、ステップＳ１０２において空の仮説リストＨとＨ’とを生成する。ステップＳ１０３において、初期の仮説ｈ（ｈは仮説展開部１０４において更新する前の仮説を表す）を生成し、状態ｓ[ｈ]＝０（WFSTの初期状態）、累積重みＷ[ｈ]＝０、出力記号列Ｏ[ｈ]＝φ（ここではφは空の記号列を表す）とし、仮説リストＨに挿入する。
【００３５】
ステップＳ１０４では、記号列取得部１０３は、入力記号列に含まれる記号を一つ読み込み、その記号をｘに代入し、仮説展開部１０４に出力する。次のステップＳ１０５からＳ１０８は、仮説展開部１０４において実行される。
【００３６】
ステップＳ１０５では、仮説リストＨから仮説を一つ取り出し仮説ｈに代入し、状態ｓ[ｈ]から入力記号がｘに等しい状態遷移のリスト（以下、「状態遷移リスト」ともいう）Ｅを用意する。
【００３７】
ステップＳ１０６では、状態遷移リストＥ＝φ（ここではφは空のリストを表す）であればＳ１１０に進む。そうでなければ、Ｓ１０７に進み、状態遷移リストＥから状態遷移を一つ取り出し、ｅに代入する。
【００３８】
ステップＳ１０８で新たな仮説ｆ（ｆは仮説展開部１０４において更新した後の仮説を表す）を生成し、状態ｓ[ｆ]＝ｎ[ｅ]、累積重みＷ[ｆ]＝Ｗ[ｈ]＋ｗ[e]、出力記号列Ｏ[ｆ]＝Ｏ[ｈ]・ｏ[ｅ]とし、仮説絞込み部１０５に出力する。ここで、“・”は二つの記号または記号列を接続し、一つの記号列にする演算を表す。
【００３９】
ステップＳ１０９は、仮説絞込み部１０５で実行され、仮説ｆを仮説リストＨ’に挿入することにより仮説を絞り込む。例えば、仮説リストＨ’内に同じ状態に到達している仮説があれば、累積重みの小さいほうまたは大きいほうだけを仮説リストＨ’に残し、仮説を絞り込む。
【００４０】
ステップＳ１０９からＳ１０６に戻り、次の状態遷移について仮説を展開する。
ステップＳ１１０では、仮説リストＨ＝φ（すべての仮説を展開済み）であればＳ１１１に進む。そうでなければＳ１０６に戻り、次の仮説ｈを展開する。
ステップＳ１１１では、新たに生成された仮説リストＨ’の要素を、すでに空となった仮説リストＨにすべて移し、Ｓ１１２に進む。
【００４１】
ステップＳ１１２では、記号列取得部１０３において次の入力記号が存在するならばＳ１０４に戻り、そうでなければ、入力記号列がすべて読み込まれたと判断しＳ１１３に進む。
ステップＳ１１３では、仮説リストＨの中で終了状態に到達している仮説の累積重みにその終了状態の終了重みを加えた後で、その終了状態に到達している仮説の中から累積重み（Ｗ[ｈ]）が最小となる仮説ｈを選び、その出力記号列Ｏ[ｈ]を記号列変換結果として、記号列出力部１０６が出力する。
ステップＳ１１４にてWFSTを用いる記号列変換手順を終了する。
【００４２】
[記号列変更例]
この記号列変換手順に従って、図１のWFSTに入力記号列ａ，ａ，ｂ，ｃが与えられた場合の出力記号列を求める過程を順を追って説明する。但し、ここでは、現状態番号ｓ、出力記号列Ｏ、累積重みＷの仮説がある場合、その仮説を（ｓ，Ｏ，Ｗ）のように表すものとする。また、WFSTのある状態遷移（現状態番号ｓ、次状態番号ｎ、入力記号ｘ、出力記号ｙ、重みｗ）を＜ｓ→ｎ，ｘ：ｙ／ｗ＞と表すものとする。また、この例では、累積重みが最小の状態遷移過程に対応する出力記号列を記号列変換結果として選択するものとする。
【００４３】
Ｓ１０１から開始し、Ｓ１０２で空の仮説リストＨ及びＨ’を作る。
Ｓ１０３により仮説リストＨの中の仮説（０，φ，０）を挿入する。
【００４４】
（記号“ａ”読み込み）
Ｓ１０４で記号ａを読み込みｘと置く。Ｓ１０５において仮説リストＨから仮説（０，φ，０）を取り出す。この仮説の現状態０から入力記号がａに等しい状態遷移＜０→０，ａ：ｄ／０．５＞を含む状態遷移リストＥを作る（図１参照）。
Ｓ１０６で状態遷移リストＥ＝φではないのでＳ１０７に進み、状態遷移＜０→０，ａ：ｄ／０．５＞を取り出し、Ｓ１０８で新たな仮説（０，ｄ，０．５）を生成し、Ｓ１０９で仮説リストＨ’に挿入する。
Ｓ１０６に戻り、状態遷移リストＥ＝φであるためＳ１１０に進み、仮説リストＨ＝φであるためＳ１１１に進む。仮説リストＨ’の要素（０，ｄ，０．５）を仮説リストＨに移し、Ｓ１１２で次の入力記号が存在するのでＳ１０４に戻る。
【００４５】
続いて、Ｓ１０４で記号ａを読み込みｘと置く。Ｓ１０５において仮説リストＨから仮説（０，ｄ，０．５）を取り出す。この仮説の現状態０から入力記号がａに等しい状態遷移＜０→０，ａ：ｄ／０．５＞を含む状態遷移リストＥを生成する。
Ｓ１０６でＥ＝φではないのでＳ１０７に進み、状態遷移リストＥから状態遷移＜０→０，ａ：ｄ／０．５＞を取り出す。Ｓ１０８で新たな仮説（０，ｄｄ，１）を生成し、Ｓ１０９で仮説リストＨ’に挿入する。
Ｓ１０６に戻り、状態遷移リストＥ＝φであるためＳ１１０に進み、仮説リストＨ＝φであるためＳ１１１に進む。仮説リストＨ’の要素（０，ｄｄ，１）を仮説リストＨに移し、Ｓ１１２で次の入力記号が存在するのでＳ１０４に戻る。
【００４６】
（記号“ｂ”読み込み）
続いて、Ｓ１０４で記号ｂを読み込みｘと置く。Ｓ１０５において仮説リストＨから仮説（０，ｄｄ，１）を取り出す。この仮説の現状態０から入力記号がｂに等しい状態遷移＜０→１，ｂ：ｃ／０．３＞と＜０→２，ｂ：ｂ／１＞とを含む状態遷移リストＥを作る。
Ｓ１０６で状態遷移リストＥ＝φではないのでＳ１０７に進み、状態遷移リストＥから、一つ目の状態遷移＜０→１，ｂ：ｃ／０．３＞を取り出す。Ｓ１０８で新たな仮説（１，ｄｄｃ，１．３）を生成し、Ｓ１０９で仮説リストＨ’に挿入する。
Ｓ１０６に戻り、状態遷移リストＥ＝φではないのでＳ１０７に進み、状態遷移リストＥから二つ目の状態遷移＜０→２，ｂ：ｂ／１＞を取り出す。Ｓ１０８で新たな仮説（２，ｄｄｂ，２）を生成して、Ｓ１０９で仮説リストＨ’に挿入する。
Ｓ１０６に戻り状態遷移リストＥ＝φであるためＳ１１０に進み、仮説リストＨ＝φであるためＳ１１１に進み、仮説リストＨ’の要素（１，ｄｄｃ，１．３）と（２，ｄｄｂ，２）とは仮説リストＨに移され、Ｓ１１２で次の入力記号が存在するのでＳ１０４に戻る。
【００４７】
（記号“ｃ”読み込み）
続いて、Ｓ１０４で記号ｃを読み込みｘと置く。Ｓ１０５において仮説リストＨから一つ目の仮説（１，ｄｄｃ，１．３）を取り出す。この仮説の現状態１から入力記号がｃに等しい状態遷移＜１→３，ｃ：ｂ／１＞を含む状態遷移リストＥを作る。
Ｓ１０６でＥ＝φではないのでＳ１０７に進み、状態遷移リストＥから状態遷移＜１→３，ｃ：ｂ／１＞を取り出す。Ｓ１０８で新たな仮説（１，ｄｄｃｂ，２．３）を生成し、Ｓ１０９で仮説リストＨ’に挿入する。
【００４８】
Ｓ１０６に戻り、状態遷移リストＥ＝φであるためＳ１１０に進み、仮説リストＨ≠φであるためＳ１０５に戻り、仮説リストＨから二つ目の仮説（２，ｄｄｂ，２）を取り出す。この仮説の現状態２から入力記号がｃに等しい状態遷移＜２→３，ｃ：ａ／０．６＞を含む状態遷移リストＥを作る。
Ｓ１０６で状態遷移リストＥ＝φではないのでＳ１０７に進み、状態遷移リストＥから状態遷移＜２→３，ｃ：ａ／０．６＞を取り出す。Ｓ１０８で新たな仮説（３，ｄｄｂａ，２．６）を生成し、Ｓ１０９で仮説リストＨ’に挿入する。このとき、仮説リストＨ’の中には既に仮説（３，ｄｄｃｂ，２．３）が含まれており、仮説（３，ｄｄｂａ，２．６）は同じ状態３に到達しているので、累積重みの小さい仮説（３，ｄｄｃｂ，２．３）を残し、仮説（３，ｄｄｂａ，２．６）は仮説リストＨ’から削除する。
【００４９】
Ｓ１０６に戻り、状態遷移リストＥ＝φであるため、Ｓ１１０に進み、仮説リストＨ＝φであるためＳ１１１に進む。Ｓ１１１で仮説リストＨ’の要素（３，ｄｄｃｂ，２．３）を仮説リストＨに移し、Ｓ１１２で次の入力記号が存在しないのでＳ１１３に進む。
Ｓ１１３で、仮説リストＨ内の仮説（３，ｄｄｃｂ，２．３）の到達状態３は終了状態であるため、終了重みを加えて（３，ｄｄｃｂ，２．８）とし、この仮説が終了状態に到達した唯一の仮説であり、累積重みが最小となるので、その出力記号列ｄｄｃｂを変換結果として出力し、Ｓ１１４で記号列変換処理を終了する。
【００５０】
（Nグラムモデル）
一方、記号列のＮ個連鎖確率を計算するNグラムモデルをWFSTに変換して、それを記号列変換に利用する方法がある。
まず、記号列w1,w2,…,wLがあるときにこれをw1Lと表すものとする。またj番目からk番目までの記号列wj,…,wkをwjkと表し、特にj=kのときはwjk=wj=wk、j>kのときはwjk=εとする。なお、εは存在しないこと、何もないことを表す記号である。
【００５１】
記号列w1Lの出現確率P(w1L)は、次式のように個々の記号の生起確率の積として計算できる。
【数２】
2015040864.tif 000004
【００５２】
そして、個々の記号の出現確率が直前のＮ−１個の記号列だけに依存するとして近似したモデルが次のNグラムモデルである。
【数３】
2015040864.tif 000005
ここで、P(wi│wi-N+1i-1)は記号wiが直前のＮ−１個の記号列wi-N+1i-1に依存して生起するNグラム確率を表す。特に、Ｎ＝１のときをユニグラムモデル、Ｎ＝２のときをバイグラムモデル、Ｎ＝３のときをトライグラムモデルと呼び、P(wi|ε)、P(wi│wi-1)、P(wi│wi-2i-1)をそれぞれユニグラム確率、バイグラム確率、トライグラム確率と呼ぶ。なお、ユニグラム確率はある記号wiが生起する確率ともいえる。
【００５３】
例えば、記号列が自然言語である場合、個々の記号は単語、記号列は文を表すものとする。このときNグラムモデルによって、ある単語列が文らしいか否かをP(w1L)として計算することができる。
個々のNグラム確率を推定するには、まず大量の記号列データ（例えば新聞記事コーパスなど）を用意し、それから記号列の連鎖統計を取ることで予め求めておくことができる。
【００５４】
例えば、ある記号列データから記号列abの後に記号cが続くトライグラム確率を推定するには
【数４】
2015040864.tif 000006
のように求めることができる。ここでC(abc)およびC(ab)は、それぞれ記号列データ内での記号列abcおよび記号列abの出現回数を表している。
【００５５】
しかし、記号列データの分量は有限であることから、記号列の並びとしては妥当であるにも関わらず、偶然その記号列データに出現しなかったN個の記号からなる記号列に対してはNグラム確率が０になってしまう問題（ゼロ頻度問題）がある。
【００５６】
（バックオフNグラムモデル）
そこで、Nグラム確率がゼロにならないよう、N個の記号からなる記号列のNグラム確率が０になってしまう場合は、N-1グラム確率を用い、さらに、N-1グラム確率が０になってしまう場合は、N-2グラム確率、というようにバックオフ（後退）する方法が用いられる。このようなNグラムモデルはバックオフNグラムモデルと呼ばれている。ただし、記号列の頻度が０でなくても、極端に小さい場合（例えば、10,0003通りの記号列に対して、頻度が１や２の場合）は(4)式で推定される確率値の信頼性が低下することから、記号列の頻度をあえて０と見なし（これをカットオフと言う）、強制的にバックオフさせる場合もある。
【００５７】
記号列wi-N+1i-1の後にwiが生起するバックオフNグラム確率は次のように計算される。
【数５】
2015040864.tif 000007
ここで、P*(wi│wi-N+1i-1)は、式(4)のように頻度から推定されるNグラム確率を少し小さくした値である。このように確率を小さく見積もることをディスカウントと呼ぶ。本来、確率が０であるNグラムに対してバックオフによるN-1グラム確率を割り当てると、確率の総和が１を超えてしまう。そこで、確率の総和を１にするため、Nグラム確率をディスカウントし、ディスカウントによって生じた確率の残りをバックオフ用に割り当てる。そして、α(wi-N+1i-1)はバックオフする際にN-1グラム確率に掛けるバックオフ係数である。ディスカウントされた確率とバックオフ係数を求める方法として、Good-Turing法、Witten-Bell法、Kneser-Ney法などが知られている。
【００５８】
記号列w1,…,wmに対するバックオフ係数α(w1m)は次のように計算される。但しm=N-1を仮定している。
【数６】
2015040864.tif 000008
分子は記号列w1mの後に続くあらゆる記号vについてディスカウントされたNグラム確率P*(v│w1m)の総和を求め、１から減算した値であり、これはディスカウントによってバックオフのために確保された確率を表す。一方、分母は、バックオフしたときに使われるN-1グラム確率P*(v│w2m)の総和であり、１−（バックオフで使われないN-1グラム確率の総和）として計算されている。つまり、バックオフ係数α(w1m)は、バックオフによって確保された確率を、バックオフに使われるN-1グラムで、その元々のN-1グラム確率に比例した割合で分け合うための係数である。バックオフ係数をこのように求めることで、バックオフNグラム確率は、確率の性質（０以上１以下、総和が１）を保証している。
【００５９】
Nグラムモデルをコンピュータで扱う場合は、N個の記号の順列とその確率値を記憶している必要がある。しかし、記号の種類が多くなるとその順列の種類数はNに対して指数的に大きくなる。例えば、記号の種類数が１万個あるとき、そのトライグラムの種類数は１万の３乗個に上る。これはあまりに大きく、コンピュータで扱う場合には膨大な記憶容量を必要とする。しかし、実際に記号列データに出現する順列はこれよりも遥かに少ないため、ほとんどのNグラム確率は０である。そこで、Nグラム確率が０よりも大きな順列とそのNグラム確率とだけを保持しておけば良い。さらに、バックオフNグラムモデルでは、確率が０より大きな１〜Ｎ個の記号からなる順列（記号列）とその確率、およびバックオフ係数を保持しておけば良い。
【００６０】
（バックオフNグラムモデルをWFSTに変換する方法）
次に、バックオフNグラムモデルをWFSTに変換する方法を示す。
基本的にはバックオフNグラムモデルが保持するN-1個の記号からなる順列の各々をWFSTの一つの状態に割り当て、各状態遷移にはN-1個の記号からなる順列の次に生起する可能性のある記号を入力記号および出力記号とし、そのNグラム確率（の対数の負値）を重みとして、対応する遷移先の状態に接続する。例えば、トライグラムモデルにおいて記号列abに対応する状態から記号列bcに対応する状態への状態遷移は、入力記号および出力記号がc、重みが-logP*(c│ab)となる（図５参照）。
【００６１】
またＮ個の記号からなるある順列が存在しない、すなわちそのNグラム確率が０の場合は、バックオフ用の状態遷移を用意して、バックオフ係数（の対数の負値）の重みを割り当て、記号列を一つ短くしたＮ−２個の記号からなる順列に対応する状態へ遷移させる。例えば、トライグラムモデルにおいて３個の記号の順列（記号列）abcが存在しない、すなわちP*(c│ab)=0の場合は、バックオフ用の状態遷移を作る。これは遷移元である記号列abに対応する状態から記号bに対応する状態に、重み-logα(ab)で遷移する。そして、記号bに対応する状態から記号列bcに対応する状態へ、入力記号と出力記号をc、重みをバイグラム確率(の対数の負値)-logP*(c│b)を持つ状態遷移を作る（図６参照）。これにより、式(5)のバックオフに基づく計算α(ab)P*(c│b)を状態遷移に埋め込む形でWFSTが構築される。更に、２個の記号からなる順列bcも存在しない、すなわちP*(c│b)=0の場合には、記号bに対応する状態から記号εに対応する状態へ、重み-logα(b)の状態遷移を作る。そして、記号εに対応する状態から記号cに対応する状態へ、入力記号と出力記号をc、重みをユニグラム確率(の対数の負値)-logP*(c)を持つ状態遷移を作る（図７参照）。但し、記号εに対応する状態は構築されるWFSTの中でただ一つ用意するものとする。
【００６２】
このようなバックオフNグラムモデルのWFSTは、次の手順に従って構築することができる。
ステップ１：記号εに対応する状態S(ε)を作り、i=S(ε)とし、状態集合Q、終了状態集合Fに加える。
ステップ２：n=1,…,N-1について、ステップ３を繰り返す。
ステップ３：登録されたnグラム確率P(wn│w1n-1)の各々について、ステップ3.1〜3.3
を繰り返す。
【００６３】
ステップ3.1：記号列w1n-1に対応する状態S(w1n)を作り、状態集合Qに加える。
ステップ3.2：状態遷移＜S(w1n-1)→S(w1n),wn：wn／-logP(wn│w1n-1)＞を作る。
ステップ3.3：バックオフ用の状態遷移＜S(w1n)→S(w2n),ε：ε／-logα(w1n)＞を作る。
ステップ４：登録されたNグラム確率P(wN│w1N-1)の各々について、状態遷移＜S(w1N-1)→S(w2N),wN：wN／-logP(wN│w1N-1)＞を作る。
但し、S(x)は記号列xを対応する状態番号に写像する関数である。
この手順で構築されたWFSTを用いれば、図４の手順に従って記号列を変換することができる。
【００６４】
以上の前提知識を元に、第一実施形態について説明する。
〔第一実施形態〕
図８は第一実施形態に係る記号列変換装置１００の機能ブロック図を示す。
【００６５】
第一実施形態に係る記号列変換装置１００は、記号列取得部１０３、仮説展開部８０４、仮説絞込み部１０５、記号列出力部１０６、記号列モデル格納部８０７、初期状態取得手段８０８、状態遷移集合取得手段８０９及び終了状態判定手段８１０を含む。記号列取得部１０３、仮説展開部８０４、仮説絞込み部１０５及び記号列出力部１０６の処理内容は図４の各部と同じである。前述の通り、本実施形態では、記号列モデルを表すバックオフNグラムモデルのWFSTは事前に構築しないので、WFST格納部１０１に代えて、記号列モデル格納部８０７、初期状態取得手段８０８、状態遷移集合取得手段８０９及び終了状態判定手段８１０を含む。このような構成により、WFSTを参照する代わりに、状態遷移集合取得手段８０９によって記号列モデル格納部８０７から必要な部分のWFSTの状態および状態遷移を取得する処理に置き換えられている点が、図４の構成とは異なる。これにより、事前に記号列モデルをすべてWFSTに変換してWFST格納部１０１に記憶しておくことなく記号列変換が可能である。
【００６６】
＜記号列モデル格納部８０７＞
記号列モデル格納部８０７には、Lグラム確率と、各記号列w1L'に対するバックオフ係数α(w1L')とが対応付けて記憶されている。ただし、L＝1,2,…,N、L'=1,2,…,N-1である。各記号列w1L'は、L'グラム確率に対応するものである。例えば、N=3のとき、トライグラム確率P(wi│wi-2i-1)、バイグラム確率P(wi│wi-1)及びユニグラム確率P(wi)と、バイグラム確率P(wi│wi-1)に対応するバックオフ係数α(wwi-2i-1)及びユニグラム確率P(wi)に対応するバックオフ係数α(wi)とが記憶されている。Lグラム確率は、N個（Nは正整数）以下の記号からなる記号列w1L(1≦L≦N)の出現確率P(w1L)を用いて式(4)により計算することができる（ただし、式(4)において出現回数に代えて出現確率を用いる）。また、バックオフ係数α(w1L')は、式(6)により求めることができる。例えば、図１２のようなテーブル形式で記憶されているものとする。図１２については後で詳述する。なお、図１２では、記号列wi-L+1i-1に依存して記号wiが生起する確率P(wi│wi-L+1i-1)を少し小さくした（補正した）値P*(wi│wi-L+1i-1)が格納されているが、P*(wi│wi-L+1i-1)の代わりにP(wi│wi-L+1i-1)が記憶されていてもよい。P(wi│wi-L+1i-1)及びP*(wi│wi-L+1i-1)を、遷移元の状態qに対応する記号列wi-L+1i-1に依存して入力された記号wiが生起する確率に対応する第１確率ともいう。
【００６７】
＜仮説展開部８０４＞
仮説展開部８０４は、記号列取得部１０３から記号xを受け取り、状態遷移集合取得部で取得した遷移元から遷移可能な状態遷移の集合を用いて、現在の仮説の集合の各仮設を更新し、その累積重みとともに仮説絞込み部１０５に出力する。
【００６８】
仮説展開部８０４は、まだ仮説を生成していない場合（最初に実行するとき）には、初期状態取得手段８０８を実行し、WFSTの初期状態の状態番号を取得する。そして、初期状態取得手段８０８で取得した初期状態の状態番号と記号列取得部１０３から受け取った記号xとを状態遷移集合取得手段８０９に送り、初期状態から記号xにより遷移可能な状態の集合を取得する。そして、受け取った状態遷移の集合を用いて新たな仮説の集合を生成する。
【００６９】
仮説展開部８０４は、既にこれまでに入力された記号に対応する仮説が生成されている場合、記号列取得部１０３から受け取った記号xと、現在の仮説が到達している状態に対応する状態番号qとを状態遷移集合取得手段８０９に送り、状態遷移集合取得手段８０９から現在の仮説が到達している状態qから、記号列取得部１０３から受け取った新たな記号xにより遷移可能な状態の集合を取得する。そして、状態遷移集合取得手段８０９から取得した遷移可能な状態の集合を用いて、現在の仮説の状態遷移過程を更新することにより新たな仮説の集合を生成する。
【００７０】
仮説展開部８０４は、生成した仮説の集合の各仮説についての累積重みを算出する。そして、生成した仮説の集合を終了状態判定手段８１０へ送り、各仮説の到達している状態が終了状態であるか否かを判定する。仮説展開部８０４は、終了状態判定手段８１０から判定結果を受け取り、終了状態である場合には、その仮説の累積重みに、その終了状態の終了重みを加えることで、仮説の累積重みを更新する。そして、生成した仮説の集合とその累積重みを仮説絞込み部１０５へ送る。
【００７１】
＜初期状態取得手段８０８＞
初期状態取得手段８０８は、仮説展開部８０４の求めに応じてWFSTの初期状態を生成し、仮説展開部８０４に出力する。これは、図４のＳ１０３における初期状態の要求s[h]=iに対応する処理であり、一つの状態番号（例えばi=0）を返す。そして、生成した初期状態の状態番号s[h]を仮説展開部８０４に送る。また、記号列wを状態番号qに一意に写像する関数q=S(w)およびその逆関数w=S-1(q)を用意し、S(ε)=0およびS-1(0)=εとする。なお、この関数S及びS-1は予め外部から与えられていてもよい。関数の例は後述する。
【００７２】
＜状態遷移集合取得手段８０９＞
状態遷移集合取得手段８０９は、入力された状態番号qと入力記号xと受け取り、これらの値を用いて、状態番号qから入力記号xで遷移可能な状態遷移の集合Eを図９の手順に従って求める。
【００７３】
まずステップＳ９０１より開始し、ステップＳ９０２で状態番号qと入力記号xを受け取る。ステップＳ９０３では、状態qに対応する記号列w1kをw1k=S-1(q)として求める。ここでは、k=0,1,…，N-1である。
【００７４】
ステップＳ９０４では、バックオフ係数を累積する変数α（累積バックオフ係数）の初期値を設定する。例えばα=1とする。また、もしk<N-1ならj=1、そうでない（k≧N-1）ならj=2と置く。このｊ=2と置くのは、確率P*(x│wjk)を計算する際に、記号列wjkの長さがN-1より大きくならないように最も順番が若い記号を切り詰め、確率P*(x│wjk)がLグラム確率(1≦L≦N)になることを保証している。
【００７５】
ステップＳ９０５では、記号列モデル格納部１３０１に、記号列wjkに依存して記号列xが生起するNグラム確率P(x│wjk)に対応した確率値P*(x│wjk)（ディスカウントされたNグラム確率）が存在するならステップＳ９０７へ、存在しない場合はＳ９０６へ進む。なお、P*(x│wjk)は、上述の式(4)により（ただし、式(4)において出現回数に代えて出現確率を用いる）、記号列モデル格納部８０７に記憶された記号列w1kxと記号列w1kの出現確率に基づいて計算することができる。なお、確率値P*(x│wjk)が存在していても所定の閾値よりも小さい値の場合にはＳ９０６へ進む処理を行っても良い。これは、確率値が特に小さいとき（10,0003通りの記号列に対して、頻度が１や２の場合等）にその確率値は信用できない可能性があるため、強制的にバックオフさせた方が精度が良くなる場合があるからである。
【００７６】
ステップＳ９０６では確率P*(x│wjk)が存在しない場合にバックオフをするため、αにバックオフ係数（補正係数）α(wjk)を掛けた値を新たな累積バックオフ係数αとする(α←α×α(wjk))。さらに、記号列wjkの最も順番が若い記号を切り詰めるために（バックオフをするために）jを1増やす(j←j+1)。例えば、記号列abcのディスカウントされたトライグラム確率P*(c│ab)が存在しない場合には、(α←α×α(ab))とし、記号列abcの最も順番が若い（一番最初の）記号aを切り詰め、記号列bcとし、Ｓ９０５の判定処理を繰り返す。なお、バックオフ係数α(wjk)は記号列モデル格納部８０７から取得することができる。
【００７７】
ステップＳ９０７では、確率P*(x│wjk)が存在するので、状態遷移＜q→S(wjkx),x:x/-log(αP*(x│wjk))＞を作り、これを唯一の状態遷移としてもつ状態遷移リスト（状態遷移の集合）Eを生成する。なお、確率P*(x│wjk)と累積バックオフ係数αとの積に対応する値-log(αP*(x│wjk)を第２確率ともいう。この第２確率を現在の仮説の集合の各仮説が到達している状態から入力された記号xへ遷移する状態遷移の状態遷移確率として設定する。
【００７８】
最後にステップＳ９０８に進み、取得した状態遷移リストEを仮説展開部８０４に出力して状態遷移集合取得手段８０９の処理を終了する。
【００７９】
図９の手順に従えば、従来法で図５の状態遷移が作られる場合には、本実施形態でも同じ状態遷移が作られる。従来法で図６の状態遷移が作られる場合には、図１０のような状態遷移が作られる（但し、破線の部分は図６との比較のために書かれており、本実施形態では作成されない）。従来法で図７の状態遷移が作られる場合には、図１１のような状態遷移が作られる（但し、破線の部分は図７との比較のために書かれており、本実施形態では作成されない）。図６における状態ab,b,bcの状態遷移が図１０では一つにまとめられているが、どちらも入力記号、出力記号、および累積重みは一致する。図７も同様に、状態遷移ab,b,ε,cの状態遷移が図１１では一つの遷移にまとめられているが、入力記号、出力記号、および累積重みは一致する。
【００８０】
＜終了状態判定手段８１０＞
終了状態判定手段８１０は、仮説展開部８０４で生成された仮説リスト（仮説の集合）Hを受け取り、仮説の集合Hの中の個々の仮説hが到達した状態s[h]が終了状態か否か、すなわちs[h]∈Fか否かを判定する。例えば状態S(ε)=0が唯一の終了状態とするなら、s[h]=0なら終了状態、s[h]≠0なら終了状態ではない、という判定をしても良い。これは、図４のＳ１１３の処理に相当する。終了状態判定手段８１０は、判定結果を仮説展開部８０４に出力する。
【００８１】
記号列モデル格納部８０７、初期状態取得手段８０８、状態遷移集合取得手段８０９及び終了状態判定手段８１０により、事前に記号列モデルからWFSTを作成しておくのではなく、入力記号を読み込むごとに、記号列モデルを参照して現在の状態から入力記号により変換可能な変換規則だけ（つまり部分的なWFSTのみ）を生成し、これを用いて記号列変換を行うことができる。これにより、記号列変換の途中に記号列モデルに記憶されている内容（確率値や補正係数の値）を更新しても、WFSTを再構成することなく記号列変換を行うことができる。従来よりも高速に動的にWFSTを生成し記号列変換を行うことができる。
【００８２】
＜仮説絞込み部１０５＞
仮説絞込み部１０５は、仮説展開部８０４で生成された仮説の集合を受け取り、同じ状態に到達している仮説の中で累積重みが最小または最大となる仮説から所定数の仮説以外の仮説を削除することにより仮説を絞り込む。そして、入力記号列が最後まで読み込まれていれば、その終了状態に到達している仮説の中から累積重み(W[h])が最小または最大となる仮説hを選び、その出力記号列O[h]を記号列変換結果として、記号列出力部１０６に送る。入力記号列が最後まで読み込まれていない場合には、絞り込み後の仮説の集合を仮説展開部８０４へ送る。
【００８３】
＜記号列出力部１０６＞
記号列出力部１０６では、仮説絞込み部１０５から受け取った出力記号列を記号列変換結果として出力する。
【００８４】
＜記号列を状態番号に写像する関数の例＞
次に、記号列w1kに対応する状態S(w1k)を効率的に求める方法を説明する。例えば、記号列モデルの個々の確率が図1２（バックオフトライグラムの場合）のようにコンピュータのメモリ上に配置されていると仮定する。ここで、ユニグラム確率のテーブルには、M個の記号vm(m=1〜M)が登録されており、その各エントリには、記号のid番号m、ユニグラム確率P(vm)、バックオフ係数α(vm)および後に続くバイグラムが格納されたエントリの先頭を指すポインタnextが含まれている。図１２の例では、ユニグラムの各ポインタは矢印で後に続くバイグラムが格納されたエントリの先頭を指している。またバイグラムのテーブルには同様に、記号のid番号n、バイグラム確率P(vn|vm)、バックオフ係数α(vmvn)および後に続くトライグラムが格納されたエントリの先頭を指すポインタnextが含まれている。但し、後に続く記号がない場合は、nextにnullを代入する。これは図１２では矢印のないエントリはこの場合に相当する。更に、トライグラムのテーブルには、記号のid番号rとトライグラム確率P(vr|vmvn)が含まれている。従って、任意の３つの記号のid番号m,n,rの順列が与えられた場合は、ユニグラムのm番目のエントリからそのnextが指すバイグラムテーブルのエントリからm+1番目のユニグラムエントリのnextが指すバイグラムテーブルのエントリの手前まで、id番号nに一致するバイグラムエントリを探す。id番号nに一致するバイグラムエントリが見つかれば、そのnextが指すトライグラムテーブルのエントリからn+1番目のバイグラムエントリのnextが指すトライグラムテーブルのエントリの手前まで、id番号rに一致するトライグラムエントリを探す。もしユニグラムから順に辿る過程で一致するid番号が見つからない場合は、３つのid番号m,n,rからなる順列(m,n,r)を２つのid番号からなる順列(n,r)にして、ユニグラムテーブルのエントリからid番号nに一致するユニグラムエントリのnextが指すバイグラムテーブルのエントリからid番号nに一致するユニグラムエントリの次のユニグラムエントリのnextが指すバイグラムテーブルのエントリの手前まで、id番号rに一致するバイグラムエントリを探す。見つかればその確率に累積バックオフ係数を掛けた値をトライグラム確率として返す。見つからなければ、２つのid番号からなる順列(n,r)を1つのid番号からなる順列(r)にして、ユニグラムエントリテーブルからid番号rに一致するユニグラムエントリを探索し、その確率に累積バックオフ係数を掛けた値をトライグラム確率として返す。
【００８５】
例えば、３つのid番号1,2,4の順列(1,2,4)が与えられた場合、ユニグラムエントリの１からnextのリンクを辿って、バイグラムエントリの2までは見つかるが、後に続くトライグラムエントリは1,9,13なので、4は見つからない。そこでバックオフのために、まず到達したバイグラムエントリv1v2のバックオフ係数α(v1v2)を記憶する。次に、最初のid番号1を削って、２つのid番号2,4の順列(2,4)を用いてユニグラムエントリの2からnextのリンクを辿って、バイグラムエントリの4を見つける。ここでバックオフトライグラム確率は、α(v1v2)P(v4|v2)として計算される。仮に、バックオフして２つのid番号2,4の順列(2,4)も見つからなかった場合は、更にid番号2を削って、id番号4のユニグラムまでバックオフする。ここでバックオフトライグラム確率は、α(v1v2)α(v2)P(v4)として計算される。
【００８６】
このデータ構造を利用して、例えば状態S(w1k)は、w1kに対応するid番号列を利用してユニグラムテーブルからid番号が一致するエントリを辿って、kグラムまで一致するid番号が見つかった場合は、ユニグラムの最初のエントリが格納されているメモリ上の位置（アドレス）を起点として、その見つかったエントリが格納されているメモリ上の相対位置をその状態番号として割り当てることができる。但し、Lグラムのエントリ（Lグラム確率と、各記号列w1L'に対するバックオフ係数α(w1L')等）はメモリ上で連続して配置されているものとする。つまり、記号列モデル格納部８０７に含まれる全ての記号列の情報とその連鎖確率をコンピュータのメモリ上に連続させて格納する。そうすることで、各記号列のメモリアドレス番号から任意の起点となるアドレス番号を差し引いた相対アドレス番号に比例する値をもって状態番号とする。状態番号０は記号εに割り当てるとすれば、
状態番号＝(見つかったエントリのアドレス − ユニグラムの最初のエントリのアドレス)
÷(N-1グラムまでのエントリ１個分のメモリサイズ) +１
・・・（１）
として求めることができる。これが関数Sの例である。逆に、状態番号に対応するエントリは、エントリのアドレス＝（状態番号−１）
×（N-1グラムまでのエントリ１個分のメモリサイズ）
＋ユニグラムの最初のエントリのアドレス
・・・（２）
で求められる。これにより、任意の状態番号ｑに対応する記号列S-1(q)も効率的に求めることができる。
【００８７】
＜変形例＞
記号列モデル格納部８０７には、Lグラム確率に代えて記号列の出現確率（生起確率）を記憶しておいてもよい。Lグラム確率を必要とする各部は、記号列の出現確率を用いて、式(4)により、Lグラム確率を計算すればよい。
【００８８】
〔第二実施形態〕
第二実施形態では、本発明を音声認識に適用する例を説明する。
記号列モデルはバックオフトライグラム言語モデルとし、図１２に示すようなデータ構造でメモリに格納される。
【００８９】
図１３は、第二実施形態の音声認識装置２００の機能ブロック図である。従来法（特許文献１参照）の言語モデルWFST格納部の代わりに、バックオフトライグラム言語モデル格納部１３０７、初期状態取得手段１３０８、状態遷移集合取得手段１３０９、終了状態判定手段１３１０とからなる言語モデルWFST生成部１３０を有する点が異なる。
【００９０】
すなわち、バックオフトライグラム言語モデル格納部１３０７、初期状態取得手段１３０８、状態遷移集合取得手段１３０９、および終了状態判定手段１３１０を用いて、言語モデルWFSTの状態遷移集合を必要に応じて生成することで、言語モデルWFSTが存在するかのように記号列変換を行う。
【００９１】
なお、バックオフトライグラム言語モデル格納部１３０７、初期状態取得手段１３０８、状態遷移集合取得手段１３０９、および終了状態判定手段１３１０以外の各部の処理については、特許文献１に詳細が記載されているため、ここでは概要のみを説明する。
【００９２】
＜音声信号入力部１３０３及び音声特徴記号列抽出部１３０４＞
音声を入力する音声信号入力部１３０３から送られた音声信号はその音声の短時間音響パターンの時系列を記号列として抽出する音声特徴記号列抽出部１３０４において音響特徴記号列に変換し、その音響特徴記号列を入力として記号列変換を行う記号列変換部１３０５に送る。
【００９３】
＜記号列変換部１３０５＞
記号列変換部１３０５は、仮説展開部１３０６、仮説補正部１３１１及び仮説絞込み部１３１２を含む。
【００９４】
記号列変換部１３０５は、音響モデル格納部１３０１から音声固定単位（例えば音素）の標準的な音響パターン系列の特徴を保持し、個々の音声固定単位と任意の音響パターンの間の類似度を与える音響モデルを読みだす。
【００９５】
音声認識に用いる音響パターンには、短い時間（例えば１０ミリ秒）ごとに音声信号を分析することにより得られるメルケプストラム(mel-frequency cepstral coefficients,
ＭＦＣＣと呼ばれる)、デルタＭＦＣＣ、ＬＰＣケプストラム、対数パワーなどがある。
【００９６】
種々の音声固定単位（例えば音素）の標準的特徴を保持する音響モデルとしては、例えば、それら音響パターンの系列の集合を確率・統計理論に基づいてモデル化する隠れマルコフモデル法（Hidden Markov Model,以後ＨＭＭと呼ぶ）が主流である。このＨＭＭ法の詳細は、例えば、社団法人電子情報通信学会、中川聖一著「確率モデルによる音声認識」に開示されている。音響モデルとして他の従来技術を用いてもよい。
【００９７】
さらに、仮説展開部１３０６は、単語辞書WFST格納部１３０２から前記音声固定単位の系列からその発音を持つ単語の系列に変換する単語辞書WFSTを読み出す。さらに、記号列変換部１３０５は、言語モデルWFST格納部の代わりに、言語モデルWFST生成部１３０を用いて、言語モデルWFSTの状態遷移集合を必要に応じて生成し、音響特徴記号列抽出部１３０４から送られた音響特徴記号列を読み込み、累積重み最小の出力記号列を求め、記号列出力部１３１に送る。
【００９８】
（仮説展開部１３０６）
仮説展開部１３０６は、音響特徴記号列抽出部１３０４から送られた音響特徴記号列の記号を一つずつ読み込む。次に、仮説展開部１３０６は、単語辞書WFSTを用いて、現在の仮説の集合の各々に新しい状態遷移を追加する。
【００９９】
なお、単語辞書WFSTの重みとして、音響モデルによって計算される音響特徴記号（音響パターン）のスコアを用いる。ただし、このスコアは、大きいほど入力音響パターンが音響モデルによって表される音声固定単位に近いことを表すので、マイナスの音響スコアをもって重みとする。隠れマルコフモデルによる音響スコアの計算では、例えばガウス分布に基づく確率値が用いられる。
【０１００】
（仮説補正部１３１１）
仮説補正部１３１１は、新しい状態遷移を追加された仮説の集合を受け取る。仮説補正部１３１１は、バックオフトライグラム言語モデル格納部１３０７のバックオフトライグラム言語モデルを参照しながら、初期状態取得手段１３０８、状態遷移集合取得手段１３０９、終了状態取得手段１３１０によって、仮説展開部１３０６から受け取った個々の仮説の累積重みを補正する。
【０１０１】
具体的には、仮説展開部１３０６から受け取った個々の仮説の状態遷移過程から出力される記号列を入力記号列として、第一実施形態と同様の処理を行って出力される出力記号列に対応する累積重み、すなわち、可能な状態遷移過程の中で累積重みが最小となる状態遷移過程の累積重み、をその仮説の累積重みに加算することにより、各仮説の累積重みを更新する。言い換えると、仮説補正部１３１１は、言語モデルWFST生成部１３０により部分的に生成される、バックオフトライグラム言語モデルに対応するWFSTとは別の単語辞書WFSTを用いて、音響特徴記号列（バックオフトライグラム言語モデルに対応するWFSTに対する入力記号列とは別の記号列である）を変換することにより得た仮説の集合に含まれる仮説の状態遷移過程から出力される記号列を、バックオフトライグラム言語モデルに対応するWFSTに対する入力記号列として、第一実施形態と同様の処理を行う。
【０１０２】
（仮説絞込み部１３１２）
仮説絞込み部１３１２は、仮説補正部１３１１で生成された仮説の集合を受け取り、同じ状態に到達している仮説の中で累積重みが最小または最大となる仮説から所定数の仮説以外の仮説を削除することにより仮説を絞り込む。そして、入力記号列が最後まで読み込まれていれば、その終了状態に到達している仮説の中から累積重みが最小または最大となる仮説を選び、その出力記号列を記号列変換結果として、記号列出力部１３１３に送る。入力記号列が最後まで読み込まれていない場合には、累積重みの大きい所定数の仮説を削除して、絞り込んだ後、残った仮説の集合を仮説展開部１３０６へ送る。
【０１０３】
仮説展開部１３０６は、音響特徴記号列の次の記号を読み込み、記号列変換部１３０５は、入力された音声特徴記号列をすべて読み終えるまで、同様の処理を繰り返す。
最後の音声特徴記号を読み込んだ後に、仮説絞込み部１３１２において累積重み最小の仮説とその出力記号列を求め、記号列出力部１３１３に送る。
【０１０４】
＜記号列出力部１３１３＞
記号列出力部１３１３は、受け取った出力記号列を音声認識結果として出力する。
このような構成により、本発明を音声認識に利用することができる。
【０１０５】
〔変形例〕
第一実施形態の状態遷移集合取得手段８０９において確率値P(x│wjk)を計算する際に、現在の話題に依存したユニグラム確率分布PT(x)を導入し、この確率分布に基づいて例えば、
P^'(x│wjk)=λPT(x)+(1-λ)P(x│wjk)                       (7)
のように確率値を現在の話題に応じて動的に更新してもよい。例えば、最近話された単語の頻度からユニグラム確率分布PT(x)を推定しても良い。ここで、λは、話題に依存したユニグラム確率と話題に依存しないNグラム確率のバランスを取る係数であり、0≦λ≦1とする。
【０１０６】
あるいは、第一実施形態の記号列モデル格納部８０７や第二実施形態のバックオフトライグラム言語モデル格納部１３０７に格納された記号列の出現確率を更新する確率値更新部を備え、記号列変換や音声認識処理の途中で、記号列モデルやバックオフトライグラム言語モデル格納部に格納された一部の記号列の出現確率が更新されても良い。
【０１０７】
〔実験例〕
図１３に示す形態で音声認識システムを構築した。音響モデルには、43種類の音素に対するHMMを用意し、各音素ごとに3つの状態があり、各状態にはその音素のコンテキスト（前にある音素は何か、後ろに続く音素は何か）に応じて3011種類ある音響パターンの確率密度分布の内の一つが割り当てられている。これら確率密度分布のId番号を音声固定単位とした。
【０１０８】
音声信号の音響パターンの系列は、１０ミリ秒ごとに音声信号を分析することにより得られるMFCC12次元、MFCCの各次元の時系列方向に前後２フレームを見たときの一次回帰係数であるデルタMFCC12次元、各次元の時系列方向に前後２フレームを見たときの一次回帰係数であるデルタデルタMFCC12次元、および対数パワーを合わせた39次元のベクトルを要素とする入力系列として抽出する。
【０１０９】
辞書として１０万単語とその発音を用い、音声固定単位の系列から単語列に変換するWFSTを構築した。
【０１１０】
バックオフトライグラム言語モデルは、「日本語話し言葉コーパス」の2762講演を書き起こした単語列から、バックオフトライグラム確率を推定し、図１２に示すようなデータ構造に格納して用いた。
【０１１１】
更に、講演音声を認識する際に、（７）式にある話題依存のユニグラムを導入し、このユニグラム確率を講演音声を認識しながら、すでに得られた音声認識結果から推定し、同じ講演の中で、そこから先の未来の音声を認識するために利用する方法も評価した。これはキャッシュ言語モデルと呼ばれる方法で、（７）式のPT(wi)を次のように計算する。
PT(wi)=Pcache(wi│w1(i-1))=(CK(wi))/K                （８）
【０１１２】
ここで、Kはすでに認識した単語の中で過去何単語分を遡って考慮するかを表す自然数、CK(wi)は最近認識したK単語の中でのwiの出現回数を表す。このキャッシュ言語モデルは、ある人があるテーマで話をするとき「一度話された単語はもう一度話されやすい」という経験則に基づくモデルである。キャッシュ言語モデルについては、非特許文献１及び２や、参考文献１に開示されている。
（参考文献１）R. Kuhn and R. De Mori著, “A cache-based natural language model for speech recognition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no.6, pp. 570-583, 1990
【０１１３】
表１は従来法と本実施形態の認識処理時間と、認識誤り率を表している。本実施形態の場合は、キャッシュ言語モデルを利用した場合も併せて示している。実時間比は、認識処理時間を実際に話された時間で割った値であり、小さいほど高速であることを示す。認識処理時間は、Intel Xeon(登録商標) X5570 2.93GHzプロセッサを用いて音声認識を動作させ、10講演(各12分)を認識させたときの時間を計測して求めた。単語誤り率は、実際に話された単語の中で誤って認識した単語の割合を表しており、小さいほど音声認識の精度が高いことを表す。
【０１１４】
【表１】
2015040864.tif 000009
【０１１５】
表1の結果において、従来法では、バックオフトライグラム言語モデルを予めWFSTに変換して音声認識を行っている。本実施形態では、バックオフトライグラム言語モデルから状態遷移を必要に応じて生成し、音声認識を行っている。これらを比較すると単語誤り率は同一で、処理時間を表す実時間比もほぼ同じであることが分かる。但し、従来法ではバックオフトライグラム言語モデルをWFSTに変換するために、Intel Xeon(登録商標) X5570 2.93GHzプロセッサを用いて約８秒を要した。
【０１１６】
キャッシュ言語モデルを用いる際は１発話(約５秒〜10秒)を認識して PT(wi)を更新するたびにWFSTを作り直すと音声認識全体の処理量は大きく増加する。１講演に100発話あったと仮定すると、800秒の処理時間が上乗せされ、実際の発話時間が12分=720秒とすれば、実時間比は1.2〜1.3になると予想される。
【０１１７】
表１の本実施形態（キャッシュ言語モデルあり）の場合は、WFSTを作り直さずにキャッシュ言語モデルを利用でき、処理時間の増加は無く、実時間比は0.31であった。また、キャッシュ言語モデルの効果により、単語誤り率は18.4%に削減された。
【０１１８】
＜その他の変形例＞
本発明は上記の実施形態及び変形例に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【０１１９】
＜プログラム及び記録媒体＞
また、上記の実施形態及び変形例で説明した各装置における各種の処理機能をコンピュータによって実現してもよい。その場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１２０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させてもよい。
【０１２２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶部に格納する。そして、処理の実行時、このコンピュータは、自己の記憶部に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実施形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよい。さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、プログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２３】
また、コンピュータ上で所定のプログラムを実行させることにより、各装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2015040864.tif 000010
【図２】
2015040864.tif 000011
【図３】
2015040864.tif 000012
【図４】
2015040864.tif 000013
【図５】
2015040864.tif 000014
【図６】
2015040864.tif 000015
【図７】
2015040864.tif 000016
【図８】
2015040864.tif 000017
【図９】
2015040864.tif 000018
【図１０】
2015040864.tif 000019
【図１１】
2015040864.tif 000020
【図１２】
2015040864.tif 000021
【図１３】
2015040864.tif 000022