JP6301794B2

JP6301794B2 - オートマトン変形装置、オートマトン変形方法およびプログラム

Info

Publication number: JP6301794B2
Application number: JP2014190377A
Authority: JP
Inventors: 学永尾; 貴史益子
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 2014-09-18
Filing date: 2014-09-18
Publication date: 2018-03-28
Anticipated expiration: 2034-09-18
Also published as: US20160086096A1; JP2016061975A; US10452355B2

Description

本発明の実施形態は、オートマトン変形装置、オートマトン変形方法およびプログラムに関する。

有限状態オートマトン（ＦｉｎｉｔｅＳｔａｔｅＡｕｔｏｍａｔｏｎ、ＦＳＡ）は、自然言語処理およびパターン認識等のさまざまな分野で利用されている。例えば、文章中に表れる特定の文字列や文字列のパターンを検索するなどの用途が存在する。ＦＳＡは、有限オートマトン（ＦｉｎｉｔｅＡｕｔｏｍａｔｏｎ、ＦＡ）、または、有限状態機械（ＦｉｎｉｔｅＳｔａｔｅＭａｃｈｉｎｅ、ＦＳＭ）と呼ばれることもある。ＦＳＡの遷移に割り当てられている記号を、以下では入力記号と呼ぶこととする。入力記号は、一般には、単に記号と呼ばれることもある。入力記号は他にも、アルファベット、または、文字と呼ばれることもある。

重みが考慮されているＦＳＡは、重み付き有限状態アクセプタ（ＷｅｉｇｈｔｅｄＦｉｎｉｔｅＳｔａｔｅＡｃｃｅｐｔｏｒ）と呼ばれる。重みと出力記号が考慮されているＦＳＡは、重み付き有限状態トランスデューサ（ＷｅｉｇｈｔｅｄＦｉｎｉｔｅＳｔａｔｅＴｒａｎｓｄｕｃｅｒ、ＷＦＳＴ）と呼ばれる。以下では、重み付き有限状態アクセプタとＷＦＳＴとをまとめて、重み付き有限状態オートマトン（ＷｅｉｇｈｔｅｄＦｉｎｉｔｅＳｔａｔｅＡｕｔｏｍａｔｏｎ、ＷＦＳＡ）と呼ぶこととする。重み付き有限状態アクセプタまたはＷＦＳＴにさらに機能が追加されたモデルも、それらの派生モデルであるとして、ＷＦＳＡに含むものとする。このようなＷＦＳＡは、音声認識、手書き文字認識、および、ＯＣＲ（ＯｐｔｉｃａｌＣｈａｒａｃｔｅｒＲｅｃｏｇｎｉｔｉｏｎ）などで必要となる辞書またはモデルを表現するために用いられたり、統計的機械翻訳で用いられたりすることがある。

辞書またはモデルから変換されたＷＦＳＡは、パターン認識などで用いるために適した構造になっていないことがあるため、変形処理が行われる場合がある。例えば、ＷＦＳＡの変形処理を行った後で、重みを量子化することでＷＦＳＡの記憶に必要となる記憶域のサイズを削減する技術が知られている。

Diamantino Caseiro, "WFST Compression for Automatic Speech Recognition," INTERSPEECH, 2010 "OpenFst Version 1.4.1"、src/include/fst/minimize.h：530行〜580行、［ｏｎｌｉｎｅ］、２０１４年４月２９日、［２０１４年８月２０日検索］、インターネット＜ＵＲＬ：http://www.openfst.org/twiki/pub/FST/FstDownload/openfst-1.4.1.tar.gz＞

しかしながら、従来技術では、変形処理後に重みの量子化を行うため、重みの量子化で発生した不要な経路を取り除けない場合があった。

実施形態のオートマトン変形装置は、変換部と、変形部と、を備える。変換部は、重み付き有限状態オートマトンの遷移に割り当てられた重み、および、重み付き有限状態オートマトンの遷移に割り当てられる重みに変換される値のいずれかである第１値の集合の要素数が減るように、かつ、第１値の順序が維持されるように、第１値を変換した第２値を生成する。変形部は、第２値に応じた重みが遷移に割り当てられた重み付き有限状態オートマトンを変形する。

第１の実施形態のオートマトン変形装置のブロック図。第１の実施形態のオートマトン変形処理のフローチャート。処理前のＷＦＳＡの例を示す図。変形処理のみを実行した結果の例を示す図。重みを変換した後に変形処理を実行した結果の例を示す図。処理前のＷＦＳＡの例を示す図。変形処理のみを実行した結果の例を示す図。重みを変換した後に変形処理を実行した結果の例を示す図。実施形態にかかるオートマトン変形装置のハードウェア図。第２の実施形態のオートマトン変形装置のブロック図。第２の実施形態のオートマトン変形処理のフローチャート。第３の実施形態のオートマトン変形装置のブロック図。第３の実施形態のオートマトン変形処理のフローチャート。

以下に添付図面を参照して、この発明にかかるオートマトン変形装置の好適な実施形態を詳細に説明する。

（第１の実施形態）
第１の実施形態にかかるオートマトン変形装置は、ＷＦＳＡの変形処理前に、変形処理によって取り除かれる不要な経路が増えるように重みを変換する。これにより、従来よりも遷移の数が少ないＷＦＳＡを得ることができる。

図１は、第１の実施形態にかかるオートマトン変形装置１００の構成の一例を示すブロック図である。図１に示すように、オートマトン変形装置１００は、変換部１０１と、変形部１０２と、を備えている。

変換部１０１は、変形処理前に、ＷＦＳＡの遷移に割り当てられる重み（第１値の一例）を変換する。変換部１０１は、重みの集合の要素数が減るように、かつ、重みの順序が維持されるように、重みを変換して変換後の重み（第２値の一例）を生成する。

変形部１０２は、変換後の重みが遷移に割り当てられたＷＦＳＡを変形する。変形部１０２による変形処理は、決定化処理、ｐｕｓｈｉｎｇ処理、最小化処理、ε除去処理、および、合成処理など、従来から用いられている任意の変形処理を含むことができる。

なお変換部１０１および変形部１０２は、例えば、ＣＰＵ（Central Processing Unit）などの処理装置にプログラムを実行させること、すなわち、ソフトウェアにより実現してもよいし、ＩＣ（Integrated Circuit）などのハードウェアにより実現してもよいし、ソフトウェアおよびハードウェアを併用して実現してもよい。

次に、このように構成された第１の実施形態にかかるオートマトン変形装置１００によるオートマトン変形処理について図２を用いて説明する。図２は、第１の実施形態におけるオートマトン変形処理の一例を示すフローチャートである。

変換部１０１は、ＷＦＳＡの重みを変換する（ステップＳ１０１）。変換部１０１は、重みが同じになる経路が増えるようにＷＦＳＡの重みを変換する。言い換えると、遷移に割り当てられている重みの集合をＶとするとき、変換部１０１は、Ｖの要素の数が減るように、かつ、重みの順序が維持（保存）されるように重みを変換する。重みの順序が維持されるとは、変換後の重みの集合をＶ’とし、ＶからＶ’への写像をｆとするとき、Ｖの任意の要素ｘ、ｙに対し、ｘ≦ｙであれば、ｆ（ｘ）≦ｆ（ｙ）が成り立つことをいう。

次に、変形部１０２は、重みを変換したＷＦＳＡを変形する（ステップＳ１０２）。上述のように、変形部１０２による変形処理は、決定化処理、ｐｕｓｈｉｎｇ処理、最小化処理、ε除去処理、および、合成処理などを含むことができる。

次に、ステップＳ１０１の変換部１０１による変換処理の一例を説明する。変換部１０１は、以下の変換処理１〜５のいずれか、または、複数の組み合わせにより重みを変換する。

（変換処理１）
変換部１０１は、浮動小数点数に対して小数点以下の切り捨て、切り上げ、および、四捨五入などを行うことで、浮動小数点形式の数を整数形式の数に変換する。重みが割り当てられている遷移のうち、小数点以下の数が異なっている重みが割り当てられている遷移が２つ以上あれば、この変換によってＶの要素が減る。仮にＶ＝｛１，１．２，２．１｝である場合は、小数点以下を切り捨てると、変換後の重みの集合Ｖ’は｛１，２｝となり、要素の数が減ることがわかる。さらに、１と１．２は１に変換され、２．１は２に変換されており、重みの順序も維持されていることがわかる。

（変換処理２）
変換部１０１は、浮動小数点数（浮動小数点形式の数）を固定小数点数（固定小数点形式の数）へと変換する。固定小数点数では小数点以下の桁数が限られているため、保持できる桁数未満の値は整数化の場合と同様に切り捨て、切り上げ、および、四捨五入などを行う。

（変換処理３）
変換部１０１は、１つの重みを保持するために用いる記憶域のビット数を減らす。すなわち変換部１０１は、変換後の重みを表現するビット数を、変換前の重みを表現するビット数より小さくするように、重みを変換する。記憶域のビット数を減らす方法の例を以下に挙げる。

１つ目は、倍精度浮動小数点型で表されている重みを単精度浮動小数点型に変換する方法である。この変換により有効桁数が少なくなるため、倍精度浮動小数点型ではわずかに異なるが単精度浮動小数点型では同じとなる２つの重みがそれぞれ少なくとも１つ、いずれかの遷移に割り当てられていれば、Ｖの要素が減ることになる。

２つ目は、全ての遷移の重みが整数であるときに、保持に必要なビット数を減らす方法である。変換前の重みがｘビット整数で表されているときにｙビットに減らすには、２の（ｘ−ｙ）乗で割り、小数点以下の切り捨て、切り上げ、および、四捨五入などを行えばよい。下位の（ｘ−ｙ）ビットのみが異なる重みがいずれかの遷移に割り当てられていれば、Ｖの要素が減る。

３つ目は、変換テーブルを用いる方法である。重みの変換のためのテーブルを事前に作成しておき、変換前の値が最も近い値をテーブルから見つけ、その値に変換、または、その値のテーブル上でのインデックスに変換する。これにより、Ｖの要素の数を減らすことができる。テーブル上でのインデックスに変換する場合、見かけ上の重みの順序が維持されない可能性があるが、そのインデックスが示す値においては重みの順序は維持されている。

変換処理３を用いると、ステップＳ１０１のような変換処理を用いない従来技術に比べて遷移の数が少ないＷＦＳＡを得られる効果の他に、ステップＳ１０２のような変形処理における記憶域を削減するという効果も得られる。これは、重みの記憶に必要な記憶域が減るためである。

（変換処理４）
変換部１０１は、重みを定数倍し、その後、変換前の重みの表現形式と異なる表現形式である整数や固定小数点数に変換する。定数をαとするとき、αは０以外の実数であればよい。αが０より大きく１未満であれば、値が零に近づくため、整数や固定小数点に変換したときに、α倍をしない場合に比べてＶの要素の数が少なくなる。一方、αが１より大きければ、整数や固定小数点に変換したときに、α倍をしない場合に比べてＶの要素の数が多くなる。αを負の値としても効果は同じである。この方法を用いると、αによって、ステップＳ１０１の変換処理後の重みの精度と、Ｖの要素の数を制御することができる。α倍することで重みがとりうる値の範囲が変わるため、ステップＳ１０２の変形処理の後に、重みを１／α倍することで、重みをステップＳ１０１の値の範囲に戻すように構成することもできる。別の異なるモデルから生成されたＷＦＳＡと組み合わせて使用する場合に、重みをβ倍して使用するのであれば、β／α倍するように構成することもできる。

（変換処理５）
変換部１０１は、変換処理４でステップＳ１０２の後に重みを１／α倍する代わりに、ステップＳ１０１の時点で重みを１／α倍する方法である。

なお、上記各変換処理で、浮動小数点数を整数へと変換する処理、浮動小数点数を固定小数点数へと変換する処理、および、倍精度浮動小数点型で表されている重みを単精度浮動小数点型に変換する処理などは、変換後の重みの表現形式を、変換前の重みと異なる表現形式に変換する処理の例である。

次に、ステップＳ１０２の変形処理の例についてさらに説明する。上述のように、変形部１０２は、決定化処理、ｐｕｓｈｉｎｇ処理、最小化処理、ε除去処理、および、合成処理などの変形処理を実行する。

決定化処理は、ある状態から出ていく遷移の入力記号が互いに異なるようにＷＦＳＡを変形する処理である。ｐｕｓｈｉｎｇ処理は、重みを移動させる処理である。最小化処理は、入力記号と重みを１つの入力記号であるとみなすことで有限状態オートマトンとし、それを最小化する処理である。ε除去処理は、入力記号が割り当てられていない遷移を取り除く処理である。合成処理は、２つのＷＦＳＴを１つに合成する処理を表す。

これらの変形処理では、重みの計算が半環（ｓｅｍｉｒｉｎｇ）によって抽象化されている。用いられる重みの演算には、（＋）と（×）の２つが存在する。一般的には、（＋）は＋を丸で囲った記号が、（×）は×を丸で囲った記号が用いられる。

例えば、トロピカル半環では、（＋）はｍｉｎ、（×）は＋である。すなわち、１（＋）２＝１、１（×）２＝３となる。対数半環（ｌｏｇｓｅｍｉｒｉｎｇ）では、ｘ（＋）ｙ＝−ｌｏｇ（ｅ^−ｘ＋ｅ^−ｙ）、（×）は＋である。確率半環（ｐｒｏｂａｂｉｌｉｔｙｓｅｍｉｒｉｎｇ）では、（＋）は＋、（×）は×である。

次に、ステップＳ１０１による重みの変換によってステップＳ１０２の遷移の数が減少する具体例を説明する。

（具体例１−１）
具体例１−１は、ステップＳ１０１の変換処理が、浮動小数点数から小数点以下を切り捨てることで整数化する重みの変換処理（上記の（変換処理１））であり、ステップＳ１０２の処理が決定化処理であり、さらに、決定化処理における重みの計算にトロピカル半環を用いた例である。

図３は、処理前のＷＦＳＡ（以下Ａ１とする）を示す図である。丸が状態を表し、矢印が遷移を表す。太線の丸は初期状態を表し、二重丸は終了状態を表す。遷移の付近に記載されているラベルのうち、「／」の左側が入力記号であり、右側が重みである。

図４は、ステップＳ１０１のような変換処理を行わずに、ステップＳ１０２（決定化処理）のみを実行した結果を示す図である。すなわち、図４は、Ａ１を決定化した結果を示す。

図３のＡ１に対し、ステップＳ１０１の変換処理によって重みを変換すると、図３の状態１から状態２への遷移のうち、入力記号がＢ、重みが１．１である遷移の重みは、１に変換される。同様に、状態１から状態３への遷移のうち入力記号がＡ、重みが２．１の遷移の重みは、２に変換される。さらに、状態１から状態３への遷移のうち入力記号がＢ、重みが２．３の遷移の重みは、２に変換される。重みの変換前の重みの集合はＶ＝｛０，１，１．１，２．１，２．３｝であった。変換後はＶ’＝｛０，１，２｝となり、Ｖの要素の数が減っている。

図５は、このように重みを変換した後のＡ１を決定化した結果を示す図である。図４の遷移の数は６本であるが、図５の遷移の数は４本であり、遷移の数が減っていることがわかる。

この具体例１−１のように、ステップＳ１０２の変形処理で用いる重みの計算方法（トロピカル半環を用いた計算など）に応じて、ステップＳ１０１の変換処理を構成してもよい。すなわち、変換部１０１が、変換後の重みの表現形式が、変形処理に応じて定められる表現形式となるように変換処理を実行してもよい。上記例では、トロピカル半環を用いる計算に合わせて、整数化する変換処理を適用している。このように構成することにより、変形処理で用いる重みの計算方法を変更する必要がなくなる。

（具体例１−２）
具体例１−２は、具体例１−１の重みの計算を、対数半環を用いる計算に変えた例である。この場合、１（＋）２．１≒０．７１２７、１．１（＋）２．３≒０．８３６７等となる。従って、ステップＳ１０１のような変換処理を行わずに決定化した結果は、図４の重みを次のように変えたものとなる。
・状態１から状態２への遷移の重み：０．７１２７
・状態１から状態３への遷移の重み：０．８３６７
・状態２から状態４への遷移のうち入力記号がＣの遷移の重み
：０．２８７３
・状態２から状態４への遷移のうち入力記号がＤの遷移の重み
：２．３８７３
・状態３から状態４への遷移のうち入力記号がＣの遷移の重み
：０．２６３３
・状態３から状態４への遷移のうち入力記号がＤの遷移の重み
：２．４６３３

一方、ステップＳ１０１の変換処理により重みを変換した後に決定化した結果は、図５の重みを次のように変えたものとなる。
・状態１から状態２への２つの遷移の重み：（いずれも）０．６８６７
・状態２から状態３への遷移のうち入力記号がＣの遷移の重み
：０．３１３３
・状態２から状態３への遷移のうち入力記号がＤの遷移の重み
：２．３１３３

このように、重みの計算の結果、整数以外の値が得られることになるが、遷移の数は具体例１−１と同様に減る。

ところで、計算結果を単精度浮動小数点数で保持すると、１つの重みを記憶するのに３２ビット必要となる。これを１６ビットの整数値で記憶するようにすれば、重みを保持するために必要な記憶域を減らすことができる。そこで、対数半環の（＋）を以下の（１）式のように変更する。
ｘ（＋）ｙ＝ＦＬＯＯＲ（−ｌｏｇ_ｂ（ｂ^−ｘ＋ｂ^−ｙ））・・・（１）

ここで、ＦＬＯＯＲは小数点以下を切り捨てる関数である。ｂは１を除く正の実数である。このように変更することで、ステップＳ１０２の変形処理に必要な記憶域を削減することができる。このように、変形処理後の重みの表現形式が、ステップＳ１０１の変換処理で得られる重みの表現形式と同じになるように、ステップＳ１０２の変形処理で用いる演算を構成してもよい。表現形式を整数以外とする場合は、上記ＦＬＯＯＲの代わりに、所定の表現形式に変換するための任意の関数ＣＯＮＶを用いればよい。

（具体例１−３）
具体例１−３は、ステップＳ１０１で上記の変換処理５を用いるように構成する例である。より具体的には、ステップＳ１０１の変換処理で整数値をいくつかまとめることで、Ｖの要素の数を減らす例である。ステップＳ１０２の変形処理は、ｐｕｓｈｉｎｇ処理を行った後、オートマトンの最小化処理を行う処理とする。さらに、ｐｕｓｈｉｎｇ処理における重みの計算にトロピカル半環を用いるものとする。この例ではステップＳ１０１の重みの変換処理で、α＝２、すなわち、重みの変換をＦＬＯＯＲ（ｘ／２）×２で計算する方法を用いる。ここで、ｘは重みである。

図６は、この例で用いる処理前のＷＦＳＡ（以下Ａ２とする）である。図７は、Ａ２に対し、ステップＳ１０２の変形処理（ｐｕｓｈｉｎｇ処理を行い、入力記号と重みの組を入力記号とみなしてオートマトンを最小化処理）のみを行った結果を示す図である。

図６のＡ２に対し、ステップＳ１０１で重みの変換を行うと、図６の状態２から状態４への遷移のうち入力記号がＣの遷移の重み９は８となる。また、状態１から状態２への遷移の重み１は０となる。それ以外の重みは元のままである。

図８は、このように重みを変換したＡ２に対してステップＳ１０２の変形処理を行った結果を示す図である。遷移の数が、６本から４本に減っていることがわかる。整数ではなく、浮動小数点数や固定小数点数をいくつかまとめるようにするよう構成することもできる。

なお、この例でのステップＳ１０２の処理のうち、オートマトンの最小化処理は、ＷＦＳＡの遷移に割り当てられる入力記号や重みなどを１つの入力記号として処理する。このため、遷移そのものが削除されることや、遷移の接続先の状態が変更されることはあるが、遷移に割り当てられた重みが変更されることはない。

一方、ｐｕｓｈｉｎｇ処理では遷移に割り当てられた重みが変更される。具体例１−１で挙げた決定化処理においても同様に重みが変更される。ステップＳ１０２で行われるＷＦＳＡの変形処理に伴い、重みが変更される遷移が接続する状態が変化することがある。この場合、変形前のある遷移の重みが、その遷移に対応する変形後の遷移の重みと異なれば、その遷移の重みを変更したと考えることができる。すなわち、重みを変更するステップがＷＦＳＡの変形処理に含まれているということである。

ＷＦＳＡの変形処理の１つであるｐｕｓｈｉｎｇ処理は遷移の接続を変更することはないが、重みを変更するステップを含んでいる。変形前の、ある遷移に対応する変形後の遷移は、変形処理の内容ごとに異なる。

変形処理が決定化処理であれば、ある入力記号列ｘに対応する変形前の初期状態からの経路の最後の遷移は、ｘに対応する変形後の初期状態からの経路の最後の遷移に対応している。

変形処理がε除去処理であれば、変形処理によって、変形前のある状態ｑからε遷移のみで到達できる状態ｑ’から出て行く遷移ｅが、状態ｑから出て行く遷移ｅ’に変更される。このとき、ｅはｅ’に対応している。ｑとｑ’の間のε遷移のみからなる経路を構成する遷移の重みを合わせた値が０でなければ、ｅとｅ’の重みの値は異なることとなる。すなわち、重みが変更される。ここで、ε遷移とは、入力記号がε、すなわち空を表す記号が割り当てられている遷移のことを言う。

（具体例１−４）
具体例１−４は、ステップＳ１０２の処理内容を増やした例である。この例では、単語のつながりを表す言語モデルを表すＷＦＳＴ（以下Ｇとする）と、単語の音素の並びを表すＷＦＳＴ（以下Ｌとする）を用いる。

まず、ステップＳ１０１の変換処理をＧに対して行う。処理後のＧをＧ’とする。ステップＳ１０２では、ＬとＧ’とを合成する合成処理を行い、その後、決定化処理、ｐｕｓｈｉｎｇ処理、および、最小化処理を順に行う。最小化処理の後に、さらにε除去処理を行うように構成してもよい。具体例１−１で用いた決定化処理や、具体例１−３で説明したｐｕｓｈｉｎｇ処理と最小化処理がステップＳ１０２に含まれている。このため、ステップＳ１０１を行わない場合に比べて、ステップＳ１０２の処理後に得られるＷＦＳＡの遷移の数は減少する。

次に、本実施形態にかかるオートマトン変形装置１００のハードウェア構成について図９を用いて説明する。図９は、本実施形態にかかるオートマトン変形装置１００のハードウェア構成例を示す説明図である。

図９に示されるようにオートマトン変形装置１００は、ＣＰＵ（Central Processing Unit）１と、操作部２と、表示部３と、ＲＯＭ（Read Only Memory）４と、ＲＡＭ（Random Access Memory）５と、記憶部６と、バス７とを備えている。各部はバス７により接続されている。

ＣＰＵ１は、ＲＡＭ５の所定領域を作業領域として、ＲＯＭ４または記憶部６に予め記憶された各種制御プログラムとの協働により各種処理を実行し、オートマトン変形装置１００を構成する各部の動作を統括的に制御する。またＣＰＵ１は、ＲＯＭ４または記憶部６に予め記憶された所定のプログラムとの協働により上記各機能部の機能を実現させる。

操作部２は、マウスやキーボード等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、その指示信号をＣＰＵ１に出力する。

表示部３は、ＬＣＤ（Liquid Crystal Display）等の表示装置により構成され、ＣＰＵ１からの表示信号に基づいて、各種情報を表示する。

ＲＯＭ４は、オートマトン変形装置１００の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。

ＲＡＭ５は、ＳＤＲＡＭ等の揮発性の記憶媒体であって、ＣＰＵ１の作業エリアとして機能する。具体的には、ＷＦＳＡの変形処理時において生成される各種変数やパラメータの値等を一時記憶するバッファ等の役割を果たす。

記憶部６は、フラッシュメモリ等の半導体による記憶媒体や、磁気的または光学的に記録可能な記憶媒体を有し、オートマトン変形装置１００の制御にかかるプログラムや各種設定情報等を書き換え可能に記憶する。また記憶部６は、ＷＦＳＡに係る各種の情報を予め記憶したり、ＷＦＳＡの変形処理の処理結果である出現位置付きＷＦＳＡを記録したりする。

本実施形態にかかるオートマトン変形装置で実行されるプログラムは、ＲＯＭ４等に予め組み込まれて提供される。

本実施形態にかかるオートマトン変形装置で実行されるプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供されるように構成してもよい。

さらに、本実施形態にかかるオートマトン変形装置で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施形態にかかるオートマトン変形装置で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。

本実施形態にかかるオートマトン変形装置で実行されるプログラムは、コンピュータを上述したオートマトン変形装置の各機能部として機能させうる。このコンピュータは、ＣＰＵ１がコンピュータ読取可能な記憶媒体からプログラムを主記憶装置上に読み出して実行することができる。

このように、第１の実施形態にかかるオートマトン変形装置では、従来技術よりも遷移の数が少ない重み付き有限状態オートマトンを得ることが可能となる。

（第２の実施形態）
ＷＦＳＡとして取り扱いたいモデルがＷＦＳＡの形式で表現されていないことがある。このような場合は、そのモデルをＷＦＳＡへと変換する必要がある。このとき、ＷＦＳＡへ変換した後に第１の実施形態で述べた重みの変換を行うこともできるが、変換後にＷＦＳＡの重みとなる値をモデルの段階で変換しておく方法も考えられる。第２の実施形態にかかるオートマトン変形装置は、このようにモデルの段階で重みを変換する。

図１０は、第２の実施形態にかかるオートマトン変形装置２００の構成の一例を示すブロック図である。図１０に示すように、オートマトン変形装置２００は、変換部２０１と、変形部１０２とを備えている。変形部１０２の機能は第１の実施形態と同様であるため同一の符号を付し説明を省略する。

変換部２０１は、ＷＦＳＡの遷移に割り当てられた重みではなく、モデルで設定される値でありモデルからＷＦＳＡへの変換時にＷＦＳＡの遷移に割り当てられる重みに変換される値（第１値の一例）を変換する。変換部２０１は、当該値の集合の要素数が減るように、かつ、値の順序が維持されるように、この値を変換して変換後の値（第２値の一例）を生成する。

さらに変換部２０１は、値を変換した後のモデルをＷＦＳＡに変換する機能を備える。モデルからＷＦＳＡへの変換時には、変換後の値（第２値の一例）に応じた値（第３値の一例）が、ＷＦＳＡの重みとして割り当てられる。

次に、このように構成された第２の実施形態にかかるオートマトン変形装置２００によるオートマトン変形処理について図１１を用いて説明する。図１１は、第２の実施形態におけるオートマトン変形処理の一例を示すフローチャートである。

変換部２０１は、モデルからＷＦＳＡへの変換処理（ステップＳ２０３）によってＷＦＳＡの重みとなる、モデルに設定された値を変換する（ステップＳ２０１）。変換部２０１は、値を変換した後のモデルをＷＦＳＡへ変換する（ステップＳ２０２）。ステップＳ２０３は第１の実施形態にかかるオートマトン変形装置１００におけるステップＳ１０２と同様の処理なので、その説明を省略する。

次に、本実施形態のオートマトン変形処理の具体例を説明する。

（具体例２−１）
具体例２−１では、モデルがＮグラム言語モデルである場合について説明する。説明を簡単にするため、Ｎグラム言語モデルはバイグラムであるとする。なお、ＮグラムのＮが２以外の場合でも同様に行うことができる。また、単語ｗ１の後に続く単語ｗ２の出現確率をＰ（ｗ２｜ｗ１）とするとき、ステップＳ２０２の処理によってＷＦＳＡの重みに割り当てられる値は、−ｌｏｇ（Ｐ（ｗ２｜ｗ１））であるとする。

ステップＳ２０１では、モデルに設定された値を、値の集合Ｖの要素数を減少させるように変換する、第１の実施形態の変換部１０１による変換処理１〜５と同様の方法を用いることができる。

ステップＳ２０１の変換処理が、実数値を小数点１桁まで有効な固定小数点数へ四捨五入によって変換する処理であり、モデルに設定された値が−ｌｏｇ（Ｐ（ｗ２｜ｗ１））＝０．１１である場合は、この値は０．１に変換される。モデルに設定された値が−ｌｏｇ（Ｐ（ｗ２｜ｗ１））＝１．３７であれば、この値は１．４に変換される。変換後の各値がステップＳ２０２によりＷＦＳＡの重みに割り当てられる。用途によっては、対数をとらずに出現確率をそのままＷＦＳＡの重みに割り当てることも考えられる。その場合は、出現確率そのものに対してステップＳ２０１の変換処理を実施すればよい。

（具体例２−２）
具体例２−２では、モデルが隠れマルコフモデル（ＨｉｄｄｅｎＭａｒｋｏｖＭｏｄｅｌ、ＨＭＭ）である場合について説明する。ＨＭＭをＷＦＳＡへ変換する場合、ＨＭＭの遷移確率をＷＦＳＡの重みに割り当てることができる。従って、ステップＳ２０１で行われる値の変換は、ＨＭＭの遷移確率に対して行われる。Ｎグラム言語モデルの場合と同じく、対数をとった値に対してステップＳ２０１の変換処理を実施し、変換処理で得られた値を重みに割り当てるようにしてもよい。

（具体例２−３）
具体例２−３では、モデルが単語の発音モデルである場合について説明する。例えば、「ｗａｔｅｒ」の発音は、辞書によると３種類存在する。従って各発音に対して、それぞれの発音のされやすさに応じた値を割り当てることができる。この値を、ＷＦＳＡの重みに割り当てるように、ステップＳ２０２で変換が行われる。この場合、ステップＳ２０１の変換は、発音のされやすさに応じた値に対して行われる。

（具体例２−４）
具体例２−４では、モデルが発音の変形を表すモデル（発音変形モデル）である場合について説明する。例えば、具体例２−３では「ｗａｔｅｒ」の発音が３つ存在すると記載したが、これらのうちの１つの発音を別の発音へと変形するためのモデルを考えることができる。このモデルは、変形のされやすさを表す値を含むことができる。この値をＷＦＳＡの重みに割り当てるように、ステップＳ２０２で変換が行われる。この場合、ステップＳ２０１の変換は、変形のされやすさを表す値に対して行われる。

（具体例２−５）
ＯＣＲや手書き文字認識では、文字を構成する各部分を認識し、それらを組み合わせることで得られる文字のうち、最も尤もらしい文字を選ぶことがある。それらの組み合わせの尤もらしさを表すモデルを文字モデルと呼ぶこととする。具体例２−５では、文字モデルがＷＦＳＡとして取り扱いたいモデルである場合について説明する。文字を構成する各部分の組み合わせの尤もらしさは数値で表される。この値をＷＦＳＡの重みに割り当てるように、ステップＳ２０２で変換が行われる。この場合、ステップＳ２０１で行われる値の変換は、尤もらしさを表す数値に対して行われる。

このように、第２の実施形態にかかるオートマトン変形装置では、従来技術よりも遷移の数が少ない重み付き有限状態オートマトンを得ることが可能となる。

（第３の実施形態）
第３の実施形態にかかるオートマトン変形装置は、第１の実施形態のオートマトン変形処理（例えば図２のステップＳ１０１、Ｓ１０２）の後に、再度重みの形式を変換し、さらにＷＦＳＡの重みの値を変更する処理を加える。重みの値を変更することで、ステップＳ１０１の処理によって重みが同じとなった複数の経路を、重みが異なる経路にすることができる。

図１２は、第３の実施形態にかかるオートマトン変形装置３００の構成の一例を示すブロック図である。図１２に示すように、オートマトン変形装置３００は、変換部３０１と、変形部１０２とを備えている。変形部１０２の機能は第１の実施形態と同様であるため同一の符号を付し説明を省略する。

変換部３０１は、ＷＦＳＡの重みの表現形式を変換する機能、および、表現形式を変換した後の重みの値に微小な変動を加えて値を変更する機能をさらに備える点が、第１の実施形態の変換部１０１と異なる。微小な変動とは、例えば、補正前の値と補正後の値との差分が許容値以内となることを意味する。許容値は、例えば変動によっても値の順序が維持されるような値を用いる。

次に、このように構成された第３の実施形態にかかるオートマトン変形装置３００によるオートマトン変形処理について図１３を用いて説明する。図１３は、第３の実施形態におけるオートマトン変形処理の一例を示すフローチャートである。

ステップＳ３０１およびステップＳ３０２は、第１の実施形態のステップＳ１０１およびステップＳ１０２と同様の処理なので、その説明を省略する。

変換部３０１は、ステップＳ３０２で変形されたＷＦＳＡの重みの表現形式を変換する（ステップＳ３０３）。例えば、ステップＳ３０１の処理後の重みの表現形式が整数であれば、変換部３０１は、整数形式を浮動小数点形式に変換する。ステップＳ３０３では、変換部３０１は、ステップＳ３０１の変換前の形式と同じ形式に変換してもよいし、別の形式に変換してもよい。ただし、ステップＳ３０４の処理結果を反映できる形式でなければならない。

変換部３０１は、形式を変換した後のＷＦＳＡの重みに微小な変動を与える（ステップＳ３０４）。この処理により、重みが同じとなる経路を減少させることができる。

各経路の重みが異なるように変更する利点は、例えば、ＷＦＳＡの初期状態から終了状態までの経路のうち、重みが最も小さい経路の入力記号列を得る処理を行う問題を考えるとわかる。

例えば、ステップＳ３０１の処理前は、重みが最も小さい経路π１が一意に決まっており、その結果、入力記号列も一意に決まっているものとする。また、π１の重みに近い重みとなる経路が１つ以上存在し、その１つをπ２とする。ステップＳ３０１の処理前はπ１の重みとπ２の重みは異なっているが、その差異がステップＳ３０１にとって十分に小さければ、ステップＳ３０１の処理後はπ１の重みとπ２の重みが同じとなる。

その結果、重みが最も小さい経路が、π１とπ２の２つとなる。すなわち、ステップＳ３０１の処理前は一意に決まっていた、重みが最も小さい経路の入力記号列が複数現れることになる。

これは、いずれの入力記号列を結果とするかを、重み以外の別の方法で決める必要が生じることを意味する。本実施形態では、ステップＳ３０３とステップＳ３０４を行うことで、多くの場合、これを解消することができる。

第１の実施形態の変換処理４と同様の方法を本実施形態でも用いることができる。この場合、第１の実施形態の場合と同様に、ステップＳ３０２の直後に、重みを１／α倍する処理を行うこともできるが、ステップＳ３０３の後に行うように構成することもできる。

上記問題について、さらに図３を用いて具体的に説明する。図３でとりうる経路は、以下の４つの経路である。重みが最小の経路の入力記号列はＡＣである。
（Ｐ１−１）入力記号列がＡＣ、重みが１
（Ｐ１−２）入力記号列がＢＣ、重みが１．１
（Ｐ１−３）入力記号列がＡＤ、重みが３．１
（Ｐ１−４）入力記号列がＢＤ、重みが３．３

一方、図５のＷＦＳＡは、ステップＳ３０１とステップＳ３０２によって図３のＷＦＳＡを処理した結果に相当する。図５のＷＦＳＡの経路は、以下の４つの経路となる。
（Ｐ２−１）入力記号列がＡＣ、重みが１
（Ｐ２−２）入力記号列がＢＣ、重みが１
（Ｐ２−３）入力記号列がＡＤ、重みが３
（Ｐ２−４）入力記号列がＢＤ、重みが３

このように、ステップＳ３０１およびステップＳ２０２を実行すると、重みが最小の経路の入力記号列はＡＣまたはＢＣとなる。すなわち、重みが最小の経路は一意に決まらない。

そこで、本実施形態では、上記のように変換部３０１がＷＦＳＡの重みに微小な変動を与えることで、重みが同じとなる経路を減少させる。以下に、微小な変動を重みに与える処理の具体例を説明する。

（具体例３−１）
具体例３−１は、ランダムな変動を重みに与える方法である。変換部３０１は、ＷＦＳＡに含まれる各遷移ｅについて、各遷移の重みｗ（ｅ）をｗ（ｅ）＋ｒａｎｄｏｍ（δ）で置き換える。ここで、δは微小な値であり、上記の許容値に相当する。例えばδは、遷移に割り当てられている重みに比べて十分に零に近い値であるとする。ｒａｎｄｏｍ（δ）は遷移ごとに生成される値であり、［−δ，＋δ］の範囲のランダムな値が生成される関数であるとする。

（具体例３−２）
具体例３−２は、ＷＦＳＡの遷移の入力記号に基づいて重みに変動を与える方法である。入力記号は数字に対応付けることができる。そこで変換部３０１は、その数字の大きい順や小さい順に変動値を決め、その値を、その入力記号があった重みに加える。例えば、入力記号がａからｚまでの英字の小文字で表されている場合、変換部３０１は、ａ＝１３δ、ｂ＝１２δ、ｃ＝１１δ、・・・、ｍ＝δ、ｎ＝−δ、ｏ＝−２δ、・・・、ｘ＝−１１δ、ｙ＝−１２δ、ｚ＝−１３δのように変動値を決定する。なお例えば「ａ＝１３δ」は、入力記号「ａ」に対する変動値を「１３δ」に決定することを意味する。

（具体例３−３）
具体例３−３は、ＷＦＳＡに変換される前のモデルに基づいた方法である。ここではＮグラム言語モデルを用いた例で説明するが、第２の実施形態で例示したモデルや、それ以外のモデルでも同様に処理することができる。Ｎグラムがバイグラムである場合を考える。単語ｗ１の後に単語ｗ２が出現する確率をＰ（ｗ２｜ｗ１）とするとき、変換部３０１は、単語ｗ２が入力記号として割り当てられている遷移ｅの重みに、−δｌｏｇ（Ｐ（ｗ２｜ｗ１））を加える。ｗ１は遷移ｅに到達する経路の入力記号列の最後の単語である。ｗ１となる単語が複数ある場合は、それらの出現確率の平均値をＰ（ｗ２｜ｗ１）として、変動値を計算することができる。ユニグラムＰ（ｗ２）をＰ（ｗ２｜ｗ１）の代わりに用いるようにしてもよい。ＮグラムのＮが３以上の場合も、遷移ｅに到達する経路の入力記号列の最後からＮ−１個の単語を使用すれば、バイグラムの場合と同様に処理することができる。

微小な値δを決める方法には以下のように様々な方法が考えられる。
決定方法１：ＷＦＳＡの遷移の重みのうち、０以外で最も０に近い値よりも小さい値とする方法。
決定方法２：ＷＦＳＡの遷移の重みに関して互いに差分値を求め、差分値のうち０以外で最も０に近い値をδとする方法。
決定方法３：ステップＳ３０１を実施する前の重みと後の重みの差分値を各遷移に対して計算し、差分値のうち０以外で最も０に近い値をδとする方法。δの値が正の値になるよう、絶対値をとってもよいし、さらに、予め定めた固定値を掛けてもよい。
決定方法４：決定方法１〜３などの方法で得られたδの値を遷移の数に基づく値で割り、その値をδとする方法。遷移の数に基づく値とは、例えば、遷移の総数である。遷移の数に基づく値を、初期状態から終了状態までの経路のうち、遷移の数が最も少ない経路の遷移の数とすることもできる。さらに、ＷＦＳＡに循環経路がなければ、初期状態から終了状態までの経路のうち、遷移の数が最も多い経路の遷移の数を、遷移の数に基づく値とすることもできる。

ステップＳ３０３の処理後の重みの表現形式で表現できる範囲であれば、δをさらに小さな値にしてもよい。逆に、大きな値にしてもよい。

このように、第３の実施形態にかかるオートマトン変形装置では、重み等の変換によって重みが同じとなった複数の経路の重みを、異なる重みに変更することで、重みが同じ経路を減らすことが可能となる。これにより、重みが同じ経路から処理結果とする経路を決定する処理を不要とすることが可能となる。

（各実施形態の適用分野）
以上で説明した方法は、ＷＦＳＡを用いる様々な分野で利用することができる。

音声認識の場合には、ＨＭＭ、単語の発音辞書、および、言語モデルなどをＷＦＳＴで表す。これらは、ステップＳ１０２の例として挙げた合成処理、決定化処理、および、最小化処理などにより最適化される。これらの一連の処理の前、または、途中にステップＳ１０１を行うと、第１の実施形態における効果を得ることができる。ＨＭＭ、単語の発音辞書、および、言語モデルをＷＦＳＴに変換する際に、ステップＳ２０１とステップＳ２０２を行うと、第２の実施形態における効果を得ることができる。

ＯＣＲ、手書き文字認識、および、ジェスチャー認識などの系列データ認識に関しても、ＷＦＳＴを用いる手法を用いる場合には、音声認識と同様に第１の実施形態や第２の実施形態による効果を得ることができる。

そのほかにも、統計的な機械翻訳、文章要約、および、文章へのタグ付け（例えば、品詞）などでもＷＦＳＡを用いる手法であれば、第１の実施形態や第２の実施形態による効果を得ることができる。

以上説明したとおり、第１から第３の実施形態によれば、遷移の数がより少ない重み付き有限状態オートマトンを得ることが可能となる。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。

１ＣＰＵ
２操作部
３表示部
４ＲＯＭ
５ＲＡＭ
６記憶部
７バス
１００、２００、３００オートマトン変形装置
１０１、２０１、３０１変換部
１０２変形部

Claims

重み付き有限状態オートマトンの遷移に割り当てられた重み、および、重み付き有限状態オートマトンの遷移に割り当てられる重みに変換される値のいずれかである第１値の集合の要素数が減るように、かつ、前記第１値の順序が維持されるように、前記第１値を変換した第２値を生成する変換部と、
前記第２値に応じた重みが遷移に割り当てられた重み付き有限状態オートマトンを変形する変形部と、
を備えるオートマトン変形装置。
前記第１値は、重み付き有限状態オートマトンの遷移に割り当てられた重みであり、
前記変形部は、前記第２値が重みとして遷移に割り当てられた重み付き有限状態オートマトンを変形する、
請求項１に記載のオートマトン変形装置。
前記第１値は、重み付き有限状態オートマトンへ変換されるモデルで設定される値、かつ、前記モデルを重み付き有限状態オートマトンに変換するときに重み付き有限状態オートマトンの遷移に重みとして割り当てられる値であり、
前記変換部は、さらに、前記第１値を変換した前記第２値が設定された前記モデルを、前記第２値に応じた第３値が遷移の重みとして割り当てられるように重み付き有限状態オートマトンに変換し、
前記変形部は、前記第３値が重みとして遷移に割り当てられた重み付き有限状態オートマトンを変形する、
請求項１に記載のオートマトン変形装置。
前記モデルは、言語モデル、発音モデル、発音変形モデル、文字モデル、および、隠れマルコフモデルのいずれかである、
請求項３に記載のオートマトン変形装置。
前記第２値の表現形式は、前記第１値の表現形式と異なる、
請求項１に記載のオートマトン変形装置。
前記第２値の表現形式は、前記変形部による変形処理に応じて定められる表現形式である、
請求項５に記載のオートマトン変形装置。
前記変形部は、変形後の重みの表現形式が、前記第２値の表現形式と同じ表現形式となるように、前記重み付き有限状態オートマトンを変形する、
請求項５に記載のオートマトン変形装置。
前記変形部は、ＣＯＮＶ（−ｌｏｇ_ｂ（ｂ^−ｘ＋ｂ^−ｙ））を含む変形処理により、前記重み付き有限状態オートマトンを変形する、
請求項５に記載のオートマトン変形装置。
ここで、ｘ、ｙは重み、ｂは１以外の正の実数、ＣＯＮＶは遷移の重みを所定の表現形式に変換する関数である。
前記第２値を表現するビット数は、前記第１値を表現するビット数より小さい、
請求項５に記載のオートマトン変形装置。
前記第１値の表現形式は浮動小数点形式であり、
前記第２値の表現形式は整数形式である、
請求項５に記載のオートマトン変形装置。
前記第１値の表現形式は浮動小数点形式であり、
前記第２値の表現形式は固定小数点形式である、
請求項５に記載のオートマトン変形装置。
前記変換部は、前記第１値を定数倍した後に、表現形式の異なる前記第２値に変換する、
請求項５に記載のオートマトン変形装置。
前記変換部は、さらに、前記変形部により変形された前記重み付き有限状態オートマトンの遷移に割り当てられた重みの表現形式を変換する、
請求項１に記載のオートマトン変形装置。
前記変換部は、さらに、表現形式を変換した重みのうち１つ以上の重みを、補正後の値との差分が許容値以内となるように補正する、
請求項１３に記載のオートマトン変形装置。
前記変換部は、表現形式を変換した重みのうち１つ以上の重みを、補正後の値との差分が許容値以内となるようにランダムに選択された値に補正する、
請求項１４に記載のオートマトン変形装置。
前記重み付き有限状態オートマトンは、単語の出現確率が設定される言語モデルに基づいて生成され、
前記変換部は、表現形式を変換した重みのうち１つ以上の重みを、対応する遷移に割り当てられた単語の出現確率に基づく値であって、補正後の値との差分が許容値以内となる値に補正する、
請求項１４に記載のオートマトン変形装置。
前記変形部は、少なくとも１つの遷移に割り当てられた重みを変更する処理を含む変形処理により、前記第２値に応じた重みが遷移に割り当てられた重み付き有限状態オートマトンを変形する、
請求項１に記載のオートマトン変形装置。
前記変形部は、決定化処理、ｐｕｓｈｉｎｇ処理、合成処理、および、ε除去処理のいずれか１つを含む変形処理により、前記第２値に応じた重みが遷移に割り当てられた重み付き有限状態オートマトンを変形する、
請求項１に記載のオートマトン変形装置。
前記変形部は、前記第２値に応じた重みが遷移に割り当てられた複数の重み付き有限状態オートマトンを前記合成処理によって合成した重み付き有限状態オートマトンに対して、決定化処理、ｐｕｓｈｉｎｇ処理、および、最小化処理を順に行う、
請求項１８に記載のオートマトン変形装置。
変換部が、重み付き有限状態オートマトンの遷移に割り当てられた重み、および、重み付き有限状態オートマトンの遷移に割り当てられる重みに変換される値のいずれかである第１値の集合の要素数が減るように、かつ、前記第１値の順序が維持されるように、前記第１値を変換した第２値を生成する変換ステップと、
変形部が、前記第２値に応じた重みが遷移に割り当てられた重み付き有限状態オートマトンを変形する変形ステップと、
を含むオートマトン変形方法。
コンピュータを、
重み付き有限状態オートマトンの遷移に割り当てられた重み、および、重み付き有限状態オートマトンの遷移に割り当てられる重みに変換される値のいずれかである第１値の集合の要素数が減るように、かつ、前記第１値の順序が維持されるように、前記第１値を変換した第２値を生成する変換部と、
前記第２値に応じた重みが遷移に割り当てられた重み付き有限状態オートマトンを変形する変形部、
として機能させるためのプログラム。