(57)【要約】【課題】  決定化演算が出来ないＷＦＳＴに対して、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすような準決定化手法を提案すること。【解決手段】  トランスデューサ処理装置１１は、準決定化の対象となるＷＦＳＴの入力を受け付けるトランスデューサ入力部１０と、入力シンボル列に対して、所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換部３１と、準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する状態結合部３２と、を含めて構成され、所定の条件は、正解シンボル列をもとに変換される所定のＷＦＳＴにより、入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とする。【選択図】      図１
2006031403.tif 000002
【特許請求の範囲】
【請求項１】
状態とその状態間の遷移とで表現される有限状態オートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したＷＦＳＴを準決定化するトランスデューサ処理装置であって、
準決定化の対象となるＷＦＳＴの入力を受け付けるトランスデューサ入力部と、入力シンボル列に対して、所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換部と、前記準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する状態結合部と、を含めて構成され、
前記所定の条件は、前記シンボル列変換部が、前記入力シンボル列および前記入力シンボル列に対応した正解シンボル列をもとに変換される前記所定のＷＦＳＴにより、前記入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とするトランスデューサ処理装置。
【請求項２】
前記シンボル列変換部は、前記準決定化したＷＦＳＴを、シンボル列の変換処理に使用することを特徴とする請求項１に記載のトランスデューサ処理装置。
【請求項３】
前記トランスデューサ処理装置は、前記準決定化の対象となるＷＦＳＴが複数ある場合に、１つのＷＦＳＴに合成するトランスデューサ合成部をさらに含めて構成されることを特徴とする請求項１または請求項２に記載のトランスデューサ処理装置。
【請求項４】
状態とその状態間の遷移とで表現される有限状態オートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したＷＦＳＴを準決定化する機械翻訳モデル作成装置であって、
機械翻訳の対象となるコーパスをもとに準決定化の対象となるＷＦＳＴを作成する機械翻訳データ処理部と、入力シンボル列に対して、所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換部と、前記準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する状態結合部と、を含めて構成され、
前記所定の条件は、前記シンボル列変換部が、前記入力シンボル列および前記入力シンボル列に対応した正解シンボル列をもとに変換される前記所定のＷＦＳＴにより、前記入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とする機械翻訳モデル作成装置。
【請求項５】
状態とその状態間の遷移とで表現される有限状態オートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したＷＦＳＴを準決定化する音声認識モデル作成装置であって、
入力された音声に関するデータをもとに準決定化の対象となるＷＦＳＴを作成する音声データ処理部と、入力シンボル列に対して、所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換部と、前記準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する状態結合部と、を含めて構成され、
前記所定の条件は、前記シンボル列変換部が、前記入力シンボル列および前記入力シンボル列に対応した正解シンボル列をもとに変換される前記所定のＷＦＳＴにより、前記入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とする音声認識モデル作成装置。
【請求項６】
状態とその状態間の遷移とで表現される有限状態オートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したＷＦＳＴをコンピュータが準決定化するトランスデューサ処理方法であって、
前記コンピュータが、準決定化の対象となるＷＦＳＴの入力を受け付ける手順と、入力シンボル列に対して、記憶手段に格納された所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換手順と、前記準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する手順と、を実行し、
前記所定の条件は、前記シンボル列変換手順が、前記入力シンボル列および前記入力シンボル列に対応した正解シンボル列をもとに変換される前記所定のＷＦＳＴにより、前記入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とするトランスデューサ処理方法。
【請求項７】
前記シンボル列変換手順は、前記準決定化したＷＦＳＴを、シンボル列の変換処理に使用することを特徴とする請求項６に記載のトランスデューサ処理方法。
【請求項８】
前記トランスデューサ処理方法は、前記準決定化の対象となるＷＦＳＴが複数ある場合に、１つのＷＦＳＴに合成する手順をさらに含めて実行することを特徴とする請求項６または請求項７に記載のトランスデューサ処理方法。
【請求項９】
請求項６ないし請求項８のいずれか１項に記載されたトランスデューサ処理方法をコンピュータに実行させるためのトランスデューサ処理プログラム。
【請求項１０】
請求項９に記載されたトランスデューサ処理プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トランスデューサ処理装置、機械翻訳モデル作成装置、音声認識モデル作成装置、トランスデューサ処理方法、トランスデューサ処理プログラム、および、記録媒体に関する。
【背景技術】
【０００２】
有限状態オートマトンは、有限個の状態とその状態間の有限個の遷移とで表現される抽象的なモデルである。このオートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したものが、ＷＦＳＴ（Weighted Finite-State Transducer）として知られている（非特許文献１など）。
【０００３】
このＷＦＳＴをシンボル列の変換処理（デコーディングとも呼ばれる）に活用する際には、ＷＦＳＴの各状態から入力シンボルで遷移できる状態数が多くなるほど、コンピュータへの負担（計算量およびメモリ消費量）が増えてしまう。そのため、同じＷＦＳＴの機能を保ちつつ、各状態から入力シンボルで遷移できる状態が一意に決まるような、ＷＦＳＴの変換処理（ある種の最適化処理）が、決定化演算として提案されている（非特許文献１参照）。
【非特許文献１】Mehryar Mohri著、"Finite-State Transducers in Language and Speech Processing"、Computational Linguistics Volume 23, No.2,1997.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来の決定化演算では、全てのＷＦＳＴが決定化できるわけではなく、決定化できないＷＦＳＴも、図１７（ａ）のように、多く存在していた。そのため、決定化演算ができないＷＦＳＴは、そのまま使用すると、計算機資源が、浪費されてしまうこととなる。
【０００５】
よって、従来の決定化が適用できないようなＷＦＳＴに対しても、入力シンボル列に対する遷移数、遷移先状態数を減らし、シンボル列の変換処理の過程で必要となる計算量、メモリ消費量を小さくすることが、求められている。
【０００６】
つまり、決定化できないＷＦＳＴに対しても適用可能な準決定化手法を提案することが求められている。ここで、準決定化とは、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすＷＦＳＴに対する演算をいう。
【０００７】
そこで、本発明は、前記した問題を解決し、決定化演算が出来ないＷＦＳＴに対して、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすような準決定化手法を提案することを主な目的とする。
【課題を解決するための手段】
【０００８】
前記課題を解決するため、本発明は、状態とその状態間の遷移とで表現される有限状態オートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したＷＦＳＴを準決定化するトランスデューサ処理装置であって、準決定化の対象となるＷＦＳＴの入力を受け付けるトランスデューサ入力部と、入力シンボル列に対して、所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換部と、前記準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する状態結合部と、を含めて構成され、前記所定の条件は、前記シンボル列変換部が、前記入力シンボル列および前記入力シンボル列に対応した正解シンボル列をもとに変換される前記所定のＷＦＳＴにより、前記入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とする。これにより、決定化演算が出来ないＷＦＳＴに対して、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすような準決定化が実現できる。
【０００９】
本発明は、前記シンボル列変換部が、前記準決定化したＷＦＳＴを、シンボル列の変換処理に使用することを特徴とする。これにより、準決定化したＷＦＳＴは、任意の入力シンボルに対する状態数および状態遷移数が少なくなるので、シンボル列の変換処理時の計算量を大幅に削減する効果がある。
【００１０】
本発明は、前記トランスデューサ処理装置が、前記準決定化の対象となるＷＦＳＴが複数ある場合に、１つのＷＦＳＴに合成するトランスデューサ合成部をさらに含めて構成されることを特徴とする。これにより、シンボル列変換処理時の計算量の削減を実現できる。
【００１１】
本発明は、状態とその状態間の遷移とで表現される有限状態オートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したＷＦＳＴを準決定化する機械翻訳モデル作成装置であって、機械翻訳の対象となるコーパスをもとに準決定化の対象となるＷＦＳＴを作成する機械翻訳データ処理部と、入力シンボル列に対して、所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換部と、前記準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する状態結合部と、を含めて構成され、前記所定の条件は、前記シンボル列変換部が、前記入力シンボル列および前記入力シンボル列に対応した正解シンボル列をもとに変換される前記所定のＷＦＳＴにより、前記入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とする。これにより、決定化演算が出来ないＷＦＳＴに対して、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすような準決定化が実現できる。
【００１２】
本発明は、状態とその状態間の遷移とで表現される有限状態オートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したＷＦＳＴを準決定化する音声認識モデル作成装置であって、入力された音声に関するデータをもとに準決定化の対象となるＷＦＳＴを作成する音声データ処理部と、入力シンボル列に対して、所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換部と、前記準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する状態結合部と、を含めて構成され、前記所定の条件は、前記シンボル列変換部が、前記入力シンボル列および前記入力シンボル列に対応した正解シンボル列をもとに変換される前記所定のＷＦＳＴにより、前記入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とする。これにより、決定化演算が出来ないＷＦＳＴに対して、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすような準決定化が実現できる。
【００１３】
本発明は、状態とその状態間の遷移とで表現される有限状態オートマトンを拡張し、入力シンボル、出力シンボル、および、重みを定義したＷＦＳＴをコンピュータが準決定化するトランスデューサ処理方法であって、前記コンピュータが、準決定化の対象となるＷＦＳＴの入力を受け付ける手順と、入力シンボル列に対して、記憶手段に格納された所定のＷＦＳＴによって、累積重みが所定のものとなるような出力シンボル列を求めるシンボル列変換手順と、前記準決定化の対象となるＷＦＳＴの状態を所定の条件により結合して、準決定化したＷＦＳＴを作成する手順と、を実行し、前記所定の条件は、前記シンボル列変換手順が、前記入力シンボル列および前記入力シンボル列に対応した正解シンボル列をもとに変換される前記所定のＷＦＳＴにより、前記入力シンボル列を変換する際に、候補管理集合の中に共起する状態の頻度から算出される統計量が、所定の閾値を上回る条件とすることを特徴とする。これにより、決定化演算が出来ないＷＦＳＴに対して、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすような準決定化が実現できる。
【００１４】
本発明は、前記シンボル列変換手順が、前記準決定化したＷＦＳＴを、シンボル列の変換処理に使用することを特徴とする。これにより、準決定化したＷＦＳＴは、任意の入力シンボルに対する状態数および状態遷移数が少なくなるので、シンボル列の変換処理時の計算量を大幅に削減する効果がある。
【００１５】
本発明は、前記トランスデューサ処理方法が、前記準決定化の対象となるＷＦＳＴが複数ある場合に、１つのＷＦＳＴに合成する手順をさらに含めて実行することを特徴とする。これにより、シンボル列変換処理時の計算量の削減を実現できる。
【００１６】
本発明は、前記トランスデューサ処理方法をコンピュータに実行させるためのトランスデューサ処理プログラムである。これにより、決定化演算が出来ないＷＦＳＴに対して、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすような準決定化が実現できる。
【００１７】
本発明は、前記トランスデューサ処理プログラムを記録したコンピュータ読み取り可能な記録媒体である。これにより、決定化演算が出来ないＷＦＳＴに対して、任意の入力シンボルに対する遷移の数および遷移先状態の数を減らすような準決定化が実現できる。
【発明の効果】
【００１８】
本発明のＷＦＳＴの準決定化手法は、決定化できないＷＦＳＴに対しても適用可能であり、機械翻訳、音声認識をはじめとする様々なシンボル列変換に応用できる。そして、これらの実用的なシステムにおいて、シンボル列の変換処理時の計算量を大幅に削減する効果がある。
【００１９】
従来の決定化では、決定化可能である場合でも、その演算処理過程でＷＦＳＴの状態数が膨大になり、計算量、メモリ消費量の両面から、現実問題として計算できないことが多かったが、本発明の準決定化手法を実施したＷＦＳＴは、準決定化前のＷＦＳＴと比べて、遷移数や状態数が増えない特徴がある。このため、計算量やメモリ消費量の問題によって決定化できないようなＷＦＳＴに対しても、本発明の準決定化手法は、計算できる可能性が高い。
【発明を実施するための最良の形態】
【００２０】
以下に、本発明が適用されるトランスデューサ処理装置の一実施形態について、図面を参照して詳細に説明する。まず、本実施形態のトランスデューサ処理装置の構成について、図１を参照して説明する。
【００２１】
図１は、本発明の一実施形態に関するトランスデューサ処理装置１の構成図である。トランスデューサ処理装置１は、入力されたトランスデューサを準決定化する機能を有する。このため、トランスデューサ処理装置１は、準決定化の対象となるトランスデューサの入力を受け付けるトランスデューサ入力部１０と、複数のトランスデューサを１つのトランスデューサに合成するトランスデューサ合成部２０と、トランスデューサの準決定化演算を行う準決定化演算部３０と、を含めて構成される。
【００２２】
そして、準決定化演算部３０は、入力シンボル列に対して、累積重みが所定のもの（例えば、最小の値、最大の値、所定の範囲など）となるような最適または準最適な出力シンボル列を求めるシンボル列変換部３１と、シンボル列変換部３１がシンボル列を変換するときに仮説候補集合に現れる状態の統計をとる統計処理部３１ａと、入カシンボル列とそれに対応した正解の出力シンボル列の組を格納する正解データ記憶部３１ｂと、複数の状態を所定の条件により結合する状態結合部３２と、を含めて構成される。そして、トランスデューサ処理装置１は、準決定化演算部３０により準決定化したトランスデューサ（ＷＦＳＴ）を出力する手段を有する。出力する手段とは、例えば、記憶手段への書き出し、ネットワークを介したデータ配信、紙面への印刷などである。なお、トランスデューサ処理装置１の各構成要素（シンボル列変換部３１など）は、トランスデューサ処理装置１という１つの筐体に納める形態だけでなく、一部の構成要素だけをトランスデューサ処理装置１とは別の装置に構成し、互いにネットワークで接続するようなシステム構成とすることもできる。以下、各構成要素について、後記する処理の説明において、詳細に説明する。
【００２３】
なお、トランスデューサ処理装置１は、演算処理を行う際に用いられる記憶手段としてのメモリと、前記演算処理を行う演算処理装置とを少なくとも備えるコンピュータとして構成される。なお、メモリは、ＲＡＭ（Random Access Memory）などにより構成される。演算処理は、ＣＰＵ（Central Processing Unit）によって構成される演算処理装置が、メモリ上のプログラムを実行することで、実現される。
【００２４】
以上、トランスデューサ処理装置１の構成について、説明した。次に、本実施形態のトランスデューサ処理装置１の動作について、図１を参照しつつ、図２ないし図７に沿って説明する。
【００２５】
図２は、ＷＦＳＴの準決定化処理の概要を説明するフローチャートである。まず、トランスデューサ入力部１０は、準決定化の対象となるＷＦＳＴの入力を受け付ける（Ｓ１）。なお、重み付き有限状態トランスデューサ（ＷＦＳＴ）の定義は以下のとおりである。
【００２６】
Ａ＝（Σ，Δ，Ｑ，Ｋ，Ｅ，Ｉ，Ｆ）：ＷＦＳＴの定義
Σ：入力シンボル
Δ：出力シンボル
Ｑ：状態の有限集合
Ｋ：重みの半環
Ｅ：Ｑ×（Σ∪｛ε｝）×（Δ∪｛ε｝）×Ｋ×Ｑ：遷移の有限集合
λ：Ｉ→Ｋ：初期状態重み関数
ρ：Ｆ→Ｋ：最終状態重み関数
Ｉ：初期状態の集合
Ｆ：最終状態の集合
【００２７】
図８に、ＷＦＳＴの例を示す。数字でラベルの付された丸が状態を表し、状態間を結ぶ矢印が遷移を表す。以下、状態の番号と、図面の符号とを区別するために、状態の番号を、「」（カギ括弧）で括ることにする。始点のない矢印で指された状態（図８では状態「０」）が初期状態、太線で囲まれた状態（図８では状態「５」）が最終状態を表す。コロン「：」の左が入カシンボル、右が出力シンボルを表す。εは特別で、空のシンボルを表す。スラッシュ（／）の右の数字は重みを表す。
【００２８】
説明の簡略化のため、本明細書では「初期状態重み関数」や「最終状態重み関数は」重みの単位元を返すものと仮定して説明する。また、重みもｔｒｏｐｉｃａｌ半環（値は実数値、和はｍｉｎ、積は＋、零元は＋∞、単位元は０）を仮定する。
【００２９】
次に、トランスデューサ合成部２０は、複数のＷＦＳＴを１つのＷＦＳＴに合成する（Ｓ３）。なお、この合成処理は、省略してもよいため、合成を実行することが指定されている場合（Ｓ２、Ｙ）のみ、実行される。
【００３０】
ここで、ＷＦＳＴの合成演算とは、例えば、文献（著者「Fernando C.N.Pereira,Michael Riley」、タイトル「Speech Recognition by Composition of Weighted Finite Automata」、出典「In Emmanuel Roche and Yves Schabes,editors,Finite-State Devices for Natural Language Processing,chapter 15,pp.431-453.MIT Press,Cambridge,Massachusetts,1997.」）などに書かれているような合成演算（つまり、composition演算）であり、２つのＷＦＳＴから１つのＷＦＳＴに変換する演算である。図９に２つのＷＦＳＴ（Ｔ1、Ｔ2）の合成結果を示す。合成されたＷＦＳＴの状態は、合成前のＷＦＳＴの状態の組に対応する。以下、本明細書では、ＷＦＳＴの合成演算を、記号「○」で示す。例えば、２つのＷＦＳＴ（Ｔ1と、Ｔ2）の合成結果は、Ｔ1○Ｔ2で示される。
【００３１】
なお、合成演算の入力となるＷＦＳＴは、例えば、文献（著者「Fernando C.N.Pereira,Michael Riley」、タイトル「Speech Recognition by Composition of Weighted Finite Automata」、出典「In Emmanuel Roche and Yves Schabes,editors,Finite-State Devices for Natural Language Processing,chapter 15,pp.431-453.MIT Press,Cambridge,Massachusetts,1997.」）に記載されている無駄なパスを生成しないようなεのための処理が行われたＷＦＳＴであることが、望ましい。
【００３２】
そして、準決定化演算部３０は、入力されたＷＦＳＴに対して、準決定化演算を行う。ここでの準決定化とは、ＷＦＳＴの所定の状態において、同じ入カシンボルに対する遷移や遷移先の状態の数を減らす（換言すると、入力に対する状態遷移先の曖昧性を削減する）ために、ＷＦＳＴを変換する演算である。しかし、従来技術におけるＷＦＳＴの決定化演算とは異なり、ある入力シンボルに対して遷移する状態の数は、複数でもよい。
【００３３】
従来、決定化ができなかったＷＦＳＴを、決定化しようとすると、無限ループに陥ってしまっていた。しかし、準決定化処理は、決定化ができなかったＷＦＳＴに対しても、準決定化を実行できる点で、従来技術とは異なる。よって、準決定化したＷＦＳＴを用いたシンボル列変換処理は、決定化できないＷＦＳＴを用いた処理に比べて、必要となる計算量、メモリ消費量を小さくすることができる。また、状態のペアの数は高々状態数の２乗オーダーであり、アルゴリズム上、組み合わせ爆発が起こるデータ構造をもたないため、計算量、メモリ消費量も従来技術の決定化より抑えることができる。
【００３４】
以下、準決定化演算の詳細を説明する。まず、シンボル列変換部３１は、入力シンボル列に対して、累積重みが最小となるような最適または準最適な出力シンボル列を求める（Ｓ４）。このシンボル列の変換処理は、デコーディングと呼ばれることもある。シンボル列の変換のアルゴリズムは、図３に示す通りである。つまり、シンボル列の変換は、前向きサーチの仮説候補集合の初期化（Ｓ１０、図４参照）、前向きサーチ（Ｓ３０、図５参照）、後向きＡ*サーチの初期化（Ｓ５０、図６参照）、後向きＡ*サーチ（Ｓ７０、図７参照）、を順に実行することである。これにより、準最適なＮ個の変換候補を出力する。ここで、図４〜図７で使用される変数の定義は、次の通りである。
【００３５】
Ｉ：入力文字列を重みつき有限状態アクセプタに書き換えたもの
Ｃ：１の状態の順序集合
Ｍ：入力のεがないように遷移を書き換えたＷＦＳＴ
【００３６】
図４は、前向きサーチ（前向きビームサーチ）の初期化を説明するフローチャートである。シンボル列変換部３１は、各入力の初期状態をｓ０として、以下の処理を順番に実行する（Ｓ１１）。シンボル列変換部３１は、各Ｍの初期状態をｓ１として、以下の処理を順番に実行する（Ｓ１２）。シンボル列変換部３１は、ｓ０の仮説候補集合に、仮説候補を加える（Ｓ１３）。なお、仮説候補は、モデル状態が「ｓ１」、累積重みが「０．０」、バックポインタが「空集合」である。シンボル列変換部３１は、ｓ１のループを終了し（Ｓ１４）、ｓ０のループを終了する（Ｓ１５）。
【００３７】
図５は、前向きサーチを説明するフローチャートである。シンボル列変換部３１は、各Ｃの要素を小さい順にｓ２として、以下の処理を順番に実行する（Ｓ３１）。シンボル列変換部３１は、ｓ２を始点とする各遷移をｔ０として、以下の処理を順番に実行する（Ｓ３２）。シンボル列変換部３１は、ｓ２の候補集合の各要素をｈ０として、以下の処理を順番に実行する（Ｓ３３）。シンボル列変換部３１は、ｈ０のモデルの各状態を始点とする遷移のうちｔ０のシンボルを入力として遷移可能なものをｔ１とする（Ｓ３４）。シンボル列変換部３１は、ｔ０の終点状態の仮説候補集合に、仮説候補を加える（Ｓ３５）。なお、仮説候補は、入力状態が「ｓ２」、累積重みが「ｈ０の累積重み＋ｔ０の遷移重み＋ｔ１の遷移重み」、バックポインタが「ｔ１の入力シンボル、ｔ１の出力シンボル、ｔ０の遷移重み＋ｔ１の遷移重み、ｈ０のＩＤ」である。但し、すでにｓ２の入力状態の候補がある場合は、累積重みとしては小さい方を採用し、バックポインタは両者の集合のユニオンとする。また、「累積重み＞ｔ０の終点状態の仮説候補集合の中で一番小さな累積重み＋あらかじめ設定されたビーム幅」である場合、ｔ０の終点状態の仮説候補集合は修正しない。シンボル列変換部３１は、ｔ１のループを終了し（Ｓ３６）、ｈ０のループを終了し（Ｓ３７）、ｔ０のループを終了し（Ｓ３８）、ｓ２のループを終了する（Ｓ３９）。
【００３８】
図６は、後向きＡ*サーチの初期化を説明するフローチャートである。シンボル列変換部３１は、優先順位付きキュー（ｑ）を空にする（Ｓ５１）。ここで、優先順位付きキューは、推定重みの小さいものが優先してポップされるようなキューである。シンボル列変換部３１は、Ｉの最終状態の前向きサーチ仮説候補集合の各要素をｈ１として、以下の処理を順番に実行する（Ｓ５２）。シンボル列変換部３１は、キューに仮説候補をプッシュする（Ｓ５３）。なお、仮説候補は、推定重みが「ｈ１の累積重み」、累積重みが「０．０」、バックポインタが「ＮＩＬ」、前向きサーチ仮説候補ＩＤが「ｈ１」である。シンボル列変換部３１は、ｈ１のループを終了する（Ｓ５４）。
【００３９】
図７は、後向きＡ*サーチを説明するフローチャートである。シンボル列変換部３１は、Ｎに０を代入する（Ｓ７１）。シンボル列変換部３１は、ｑが空でない間、以下の処理を繰り返し実行する（Ｓ７２）。シンボル列変換部３１は、ｈ２にキューから要素をポップする（Ｓ７３）。シンボル列変換部３１は、所定の条件を満たしている場合に、後向きサーチ仮説候補のバックポインタをたどり、出力シンボル列を出力する（Ｓ７４）とともに、Ｎに１を追加する。なお、所定の条件は、ｈ２の前向きサーチ仮説候補ＩＤがＩとＭの両者の初期状態に対応するという条件である。また、もし、Ｎがあらかじめ与えられた出力候補数と同数なら、図７の処理を終了する。
【００４０】
シンボル列変換部３１は、ｈ３にｈ２の前向きサーチ仮説候補を代入する（Ｓ７５）。シンボル列変換部３１は、ｈ３のバックポインタ集合の各要素をｂｐとして、以下の処理を順に実行する（Ｓ７６）。シンボル列変換部３１は、ｈ４にｂｐの仮説候補ＩＤを代入する（Ｓ７７）。シンボル列変換部３１は、キューに仮説候補をプッシュする（Ｓ７８）。なお、仮説候補は、累積重みが「ｈ２の累積重み＋ｂｐの遷移重み」、推定重みが「ｈ２の累積重み＋ｂｐの遷移重み＋ｈ４の累積重み」、バックポインタが「（ｂｐ入力シンボル、ｂｐ出力シンボル、ｈ２）」、前向きサーチ仮説候補ＩＤが「ｈ４」である。シンボル列変換部３１は、ｂｐのループを終了し（Ｓ７９）、ｑのループを終了する（Ｓ８０）。
【００４１】
なお、図４〜図７では、Ｉの状態Ｓ1から状態Ｓ2に遷移があるとき、Ｓ1＜Ｓ2で順序を定義する。前向きサーチの仮説候補集合の要素は固有のＩＤ（仮説候補ＩＤ）をもった３つ組からなる。
仮説候補ＩＤ：（モデル状態，累積重み，バックポインタ集合）
【００４２】
前向きサーチ仮説候補における「バックポインタ集合」の要素は以下のとおり。
[入カシンボル，出力シンボル，遷移重み，仮説候補ＩＤ]
【００４３】
後向きサーチの仮説候補は以下のとおり。
仮説候補ＩＤ：（推定重み，累積重み，バックポインタ，前向きサーチ仮説候補ＩＤ）
【００４４】
後向きサーチの「バックポインタ」はＮＩＬ（何も各々の正解指さない場合）もしくは、以下の形式をとる。
（入力シンボル，出力シンボル，後向きサーチ仮説候補ＩＤ）
【００４５】
"ａｃｄ"を入力シンボル列，図８をシンボル列変換に用いるＷＦＳＴとしたとき、図１０に前向きサーチの実行例を、図１１に後向きサーチの優先順位付キューの推移の様子を示す。個々では単一のＷＦＳＴを用いたシンボル列の変換手法を詳説したが、ここのＷＦＳＴは複数の合成であってもまったく同じように扱うことができる。この場合、遷移を求める過程で合成演算を動的に適用し、「モデル状態」は複数のＷＦＳＴの状態の組となる。
【００４６】
なお、後記する状態の結合（Ｓ６）により、同一の遷移（遷移元の状態、入力シンボル、出力シンボル、遷移先状態、の４つ組）が複数現れる場合は、１つの遷移のみを残す。また、後記する状態の結合（Ｓ６）により、始端と終端が同じ状態でεを入力とする遷移（εループと呼ぶ）が、新たに生成される可能性がある。よって、その重みが負の場合はシンボル列の変換の過程で無限ループに陥る可能性があるので０.０に丸める。また出力もεであるようなεループは取り除く。
【００４７】
図２に戻って、説明を続ける。統計処理部３１ａは、シンボル列変換部３１がシンボル列を変換するときに仮説候補集合に現れる状態の統計をとる（Ｓ５）。ただし、この共起の統計量を計る際には，正解シンボル列（Ｏi）に変換されることを前提とした制約を加える。
【００４８】
つまり、各入力シンボル列ｉに対応した正解出力シンボル列ＷＦＳＴをＯi、シンボル列変換モデルをＴ0○Ｔ1○…○Ｔn-1○Ｔnとする。正解シンボル列（例えば“ａｃ”）は、図１２のようなＷＦＳＴに変換される。そして、Ｔ0○Ｔ1○…○Ｔn-1○Ｔn○Ｏiを用いてｉをシンボル列変換し、そのとき同時に仮説候補集合に現れる状態をモデル毎（Ｔiごと）にカウントすることで、統計処理が行われる。
【００４９】
この統計処理を行うために、正解データ記憶部３１ｂは、入カシンボル列とそれに対応した正解の出力シンボル列を大量に記憶する。そして、トランスデューサ処理装置１は、それらのシンボル列の組を、正解出力シンボル列のＷＦＳＴ（Ｏi）に変換する。
【００５０】
さらに、状態結合部３２は、複数の状態を所定の条件により結合する（Ｓ６）。なお、「実際にＷＦＳＴを使ったシンボル列の変換過程（つまり、前向きサーチ（Ｓ３０）の過程）で、候補管理集合（仮説候補集合）の中に頻繁に共起する（一緒に現れる）ＷＦＳＴの状態たちは、区別の必要が少ない」とみなすことができる。よって、すべてのＷＦＳＴの状態のペアに対して、ＷＦＳＴの状態の共起スコア（共起する状態の頻度から算出される統計量）がある値（所定の閾値）より大きいことを前記所定の条件とし、その所定の条件を満たす状態同士を結合する。
【００５１】
そして、状態の結合の基準としては、統計処理（Ｓ５）で説明したシンボル列の変換過程で統計処理部３１ａが算出する統計量φ2値を用いる。
【００５２】
φ2＝（ａｄ−ｂｃ）2／｛（ａ＋ｂ）（ａ＋ｃ）（ｂ＋ｄ）（ｃ＋ｄ）｝
ａ＝ｆｒｅｑ（ｑ1,ｑ2）
ｂ＝ｆｒｅｑ（ｑ1）−ａ
ｃ＝ｆｒｅｑ（ｑ2）−ａ
ｄ＝Ｎ−ａ−ｂ−ｃ
【００５３】
ここで、Ｎは仮説候補集合の数、ｆｒｅｑ（ｑ）は、状態ｑが現れた仮説候補集合の数、ｆｒｅｑ（ｑ1,ｑ2）はｑ1とｑ2が同時に現れた仮説候補集合の数を表す。各Ｔi毎に、このφ2値が所定の閾値以上となる状態同士を結合する。
【００５４】
以上、準決定化演算について、一通り説明した。次に、本明細書が開示する準決定化演算と、従来技術の決定化演算との差異を明確にする説明を行う。図８に、演算対象となるＷＦＳＴを示す。
【００５５】
まず、本明細書が開示する準決定化演算で、図８のＷＦＳＴを準決定化した結果を図１３に示す。ここでは、状態「１」と状態「３」が結合されている。準決定化演算は、所定の状態について、同一の入力シンボルによって遷移する先の状態の数および遷移数を減らすことを特徴としている。しかし、遷移する先の状態の数は、必ずしも１つになるとは限らない。例えば、図１３では、状態「０」から入力シンボル「ａ」によって遷移する先の状態の数は、２つである。
【００５６】
一方、従来技術の決定化演算について、例えば、文献（著者「Mehryar Mohri」、タイトル「Finite-State Transducers in Language and Speech Processing」、出典「Computational Linguistics Volume 23, No.2,1997.」）で提案されている手法で、図８のＷＦＳＴを決定化した結果を図１４に示す。決定化されたＷＦＳＴの状態は「もとのＷＦＳＴの状態」、「未出力シンボル列」、「未出力重み」の３つ組の集合で表される。決定化されたＷＦＳＴは，任意の入カシンボルに対して、遷移先が一意に決まるため，非常に効率のよいシンボル列変換が可能になる。
【００５７】
このように、本明細書が開示する準決定化演算と、従来技術の決定化演算とは、入力に対する状態遷移先の曖昧性を削減するという目的は共通しているが、演算結果が異なる。
【００５８】
ただし，必ずしもすべてのＷＦＳＴが決定化できるわけでない。ＷＦＳＴの種類によっては決定化の過程で生成されるこの３つ組の個数が有限個で抑えられない場合があり、決定化が不可能になることがある。また、決定化したＷＦＳＴの状態はもとのＷＦＳＴの状態の集合に対応するため、決定化が可能な場合であってもこの３つ組は膨大な数になりがちであるため、計算量、メモリ消費料も膨大になるから、現実問題として計算できないことが多い。
【００５９】
例えば、図１７（ａ）のＷＦＳＴは、決定化演算では無限ループが発生してしまうので、決定化が不可能なＷＦＳＴの一例である。このようなＷＦＳＴに対しても、状態遷移先の曖昧性を削減することは、従来技術の決定化演算では、うまくいかなかった。
【００６０】
しかし、本明細書が開示する準決定化演算は、この図１７（ａ）のＷＦＳＴを、図１７（ｂ）のように、準決定化することができる。具体的には、“ａａ”という入力シンボル系列の変換結果の正解として、“ａｂ”が学習データの中に数多く与えられると、本発明の準決定化手法では、状態「１」と状態「２」とが結合され、図１７（ｂ）のような結果が得られる。その結果、準決定化演算は、決定化演算よりも、処理できるＷＦＳＴが多い（つまり、適用範囲の広い）手法であるといえる。
【００６１】
以上説明した本発明は、以下のようにその趣旨を逸脱しない範囲で広く変形実施することができる。
【００６２】
例えば、本実施形態のトランスデューサ処理装置１（図１参照）を、入力されたコーパスから生成されるトランスデューサを準決定化する機械翻訳モデル作成装置１ａとして活用してもよい。つまり、機械翻訳モデル作成装置１ａは、機械翻訳に使用するための準決定化したＷＦＳＴを作成および出力する。そして、機械翻訳の処理は、準決定化したＷＦＳＴに対してシンボル列変換をすることによって、実現される。さらに、機械翻訳モデル作成装置１ａは、準決定化したＷＦＳＴに対してシンボル列変換をする手段を、有する構成としてもよい。または、機械翻訳モデル作成装置１ａとは別の装置が、シンボル列変換をする手段を有する構成としてもよい。図１５に、機械翻訳モデル作成システムの全体構成図を示す。
【００６３】
まず、機械翻訳データ処理部１１は、例えば、文献（著者「塚田元,永田昌明」、タイトル「ＷＦＳＴ全展開モデルに基づく統計的機械翻訳 」、出典「言語処理学会  第10回年次大会,pp.41-44,March 2004.」）に書かれているような方法を用いて、文毎にアライメントのとれた大量の２ヵ国語コーパスおよび辞書から、複数の統計翻訳用のサブモデルを学習し、ＷＦＳＴの形で表現する（Ｓ１）。次に、トランスデューサ合成部２０は、このサブモデルとして表現された複数のＷＦＳＴを、合成演算によって１つのＷＦＳＴに合成する（Ｓ３）。なお、この合成処理は、必須ではない。さらに、準決定化演算部３０は、この合成されたＷＦＳＴを準決定化する。ここで、シンボル列変換部３１は、入力文（単語列もしくは複合語列）を出力文（単語列もしくは複合語列）に変換する（Ｓ４）。
【００６４】
以上、機械翻訳モデル作成装置１ａは、複数のサブモデルを予め合成しておくことと、準決定化処理との相乗効果で、従来の構成と比べて格段に効率的な翻訳処理が可能になる。なお、我々の日英翻訳実験では約２０倍の速度向上が達成できた。
【００６５】
また、本実施形態のトランスデューサ処理装置１（図１参照）を、入力された音声に関するデータから生成されるトランスデューサを準決定化する音声認識モデル作成装置１ｂとして活用してもよい。つまり、音声認識モデル作成装置１ｂは、音声認識に使用するための準決定化したＷＦＳＴを作成および出力する。そして、音声認識の処理は、準決定化したＷＦＳＴに対してシンボル列変換をすることによって、実現される。さらに、音声認識モデル作成装置１ｂは、準決定化したＷＦＳＴに対してシンボル列変換をする手段を、有する構成としてもよい。または、音声認識モデル作成装置１ｂとは別の装置が、シンボル列変換をする手段を有する構成としてもよい。図１６に、音声認識モデル作成システムの全体構成図を示す。
【００６６】
まず、音声データ処理部１２は、例えば文献（著者「Mehryar Mohri,Fernando C.N.Pereira,Michael Riley」、タイトル「Weighted finite-state transducers in speech recognition」、出典「Computer Speech ＆ Language January 2002, vol. 16, no. 1,pp. 69-88(20)」）などに書かれているような方法を用いて、書き起こし音声データ、発音辞書、テキストデータなどからサブモデルを学習し、ＷＦＳＴの形で表現する（Ｓ１）。トランスデューサ合成部２０は、このサブモデルとして表現された複数のＷＦＳＴを、合成演算によって１つのＷＦＳＴに合成する（Ｓ３）。なお、この合成処理は、必須ではない。さらに、準決定化演算部３０は、この合成されたＷＦＳＴを準決定化する。つまり、シンボル列変換部３１は、ＨＭＭ（Hidden Markov Model）の確率分布ＩＤ列を出力単語列（または複合語列）に変換する（Ｓ４）。
【図面の簡単な説明】
【００６７】
【図１】本発明の一実施形態に関するトランスデューサ処理装置の構成図である。
【図２】本発明の一実施形態に関するＷＦＳＴの準決定化処理の概要を説明するフローチャートである。
【図３】本発明の一実施形態に関するシンボル列の変換のアルゴリズムを示す図である。
【図４】本発明の一実施形態に関する前向きサーチの仮説候補集合の初期化を説明するフローチャートである。
【図５】本発明の一実施形態に関する前向きサーチを説明するフローチャートである。
【図６】本発明の一実施形態に関する後向きＡ*サーチの初期化を説明するフローチャートである。
【図７】本発明の一実施形態に関する後向きＡ*サーチを説明するフローチャートである。
【図８】本発明の一実施形態に関するＷＦＳＴの例を示す図である。
【図９】本発明の一実施形態に関する２つのＷＦＳＴの合成結果を示す図である。
【図１０】本発明の一実施形態に関する前向きサーチの実行例を示す図である。
【図１１】本発明の一実施形態に関する後向きサーチの優先順位付キューの推移の様子を示す図である。
【図１２】本発明の一実施形態に関する正解シンボル列を示す図である。
【図１３】本発明の一実施形態に関するＷＦＳＴを準決定化した結果を示す図である。
【図１４】従来の技術に関するＷＦＳＴを決定化した結果を示す図である。
【図１５】本発明の一実施形態に関する機械翻訳モデル作成システムの全体構成図である。
【図１６】本発明の一実施形態に関する音声認識モデル作成システムの全体構成図である。
【図１７】本発明の一実施形態に関する決定化できないＷＦＳＴを準決定化した図である。
【符号の説明】
【００６８】
１      トランスデューサ処理装置
１ａ    機械翻訳モデル作成装置
１ｂ    音声認識モデル作成装置
１０    トランスデューサ入力部
１１    機械翻訳データ処理部
１２    音声データ処理部
２０    トランスデューサ合成部
３０    準決定化演算部
３１    シンボル列変換部
３２    状態結合部
【図１】
2006031403.tif 000003
【図２】
2006031403.tif 000004
【図３】
2006031403.tif 000005
【図４】
2006031403.tif 000006
【図５】
2006031403.tif 000007
【図６】
2006031403.tif 000008
【図７】
2006031403.tif 000009
【図８】
2006031403.tif 000010
【図９】
2006031403.tif 000011
【図１０】
2006031403.tif 000012
【図１１】
2006031403.tif 000013
【図１２】
2006031403.tif 000014
【図１３】
2006031403.tif 000015
【図１４】
2006031403.tif 000016
【図１５】
2006031403.tif 000017
【図１６】
2006031403.tif 000018
【図１７】
2006031403.tif 000019