(57)【特許請求の範囲】
【請求項１】
与えられた入力シンボルの系列（以下、入力系列という）と出力シンボルの系列（以下、出力系列という）を用いた機械学習によって有限状態トランスデューサの構造を推定する装置であって、
有限状態トランスデューサのアークを(ps,k,is,k,os,k,qs,k)として（ただし、ps,k：遷移元の状態、is,k：入力シンボル、os,k：出力シンボル、qs,k：遷移先の状態、(s,k)：アークを示す変数、s：遷移元の状態を特定するための識別子、k：識別子sで特定される遷移元の状態から出ているアーク全てに付与した通し番号）、
(ps,k,is,k,os,k,qs,k)の事前確率を、
基底測度Gsと集中度パラメータαsで定まるディリクレ過程DP(αs,Gs)からサンプルされた離散確率分布であるFs(is,k,os,k,qs,k)と、条件Cが真の時に1を出力しそうでない時に0を出力する指示関数1(C)とを用いて、
P(ps,k,is,k,os,k,qs,k|αs,Gs)=1(ps,k=s)・Fs(is,k,os,k,qs,k;αs,Gs)
と表し、
Nを2以上の予め定められた整数とし、nを1≦n≦Nを満たす整数とし、x=nをn番目の入力系列とし、y=nをn番目の出力系列とし、n番目の入力系列x=nと出力系列y=nとのペアに対応する、有限状態トランスデューサ上の1番目の状態からJn番目の状態までをつなぐ経路を上記(s,k)の系列としてπ=n={(sn,1,kn,1),(sn,2,kn,2),…,(sn,j,kn,j),…,(sn,Jn,kn,Jn)}のように表わすとし、I={is,k|∀s,∀k}とし、O={os,k|∀s,∀k}とし、Q={qs,k|∀s,∀k}とし、I*を1番目の状態になりえる状態の集合とし、f(sn,Jn)を状態sn,Jnに関連付けられている終了状態の重みとして（ただし、状態sn,Jnが終了状態でない場合はf(sn,Jn)=0とする）、
n番目の入力系列x=nと出力系列y=nとのペアに対応する経路π=nが表われる確率を、
【数１０】
0005951562.tif 000011
と表し、
経路π=nに対応するn番目の入力系列x=nと出力系列y=nを、シンボル系列から無為を表すシンボルεを取り除くオペレータR[・]を用いて、
【数１１】
0005951562.tif 000012
と表す、有限状態トランスデューサによるシンボル系列生成モデルを用いて、
N個の入力系列および出力系列を用いて上記シンボル系列生成モデルを学習することによって、有限状態トランスデューサの構造を推定する推定部
を含む有限状態トランスデューサの構造推定装置。
【請求項２】
請求項１に記載の有限状態トランスデューサの構造推定装置であって、
入力シンボルiと出力シンボルoと遷移先の状態qを確率変数とする上記基底測度Gsを、入力シンボルiと出力シンボルoを確率変数とする基底測度G(IO)sと遷移先の状態qを確率変数とする基底測度G(ST)sとを用いて、
Gs(i,o,q)=G(IO)s(i,o)・G(ST)s(q)
と表し、ただし、G(IO)sは基底測度G(IO)0と集中度パラメータβ0で定まるディリクレ過程DP(β0,G(IO)0)からサンプルされた離散確率分布であり、G(ST)sは基底測度G(ST)0と集中度パラメータγ0で定まるディリクレ過程DP(γ0,G(ST)0)からサンプルされた離散確率分布である、
とすることを特徴とする有限状態トランスデューサの構造推定装置。
【請求項３】
請求項１または請求項２に記載の有限状態トランスデューサの構造推定装置であって、
集中度パラメータαsは、ガンマ分布Gam(αs;a0,b0)に従う確率変数である、ただし、a0はガンマ分布の形状パラメータであり、b0はガンマ分布のスケールパラメータである、
ことを特徴とする有限状態トランスデューサの構造推定装置。
【請求項４】
請求項１から請求項３のいずれかに記載の有限状態トランスデューサの構造推定装置であって、
N個の入力系列および出力系列を用いて、入力系列から対応する出力系列への全ての変換においてアークを通った累積回数に比例する確率として重みを算出する
ことを特徴とする有限状態トランスデューサの構造推定装置。
【請求項５】
請求項１から請求項４のいずれかに記載の有限状態トランスデューサの構造推定装置であって、
上記推定部は、マルコフ連鎖モンテカルロ法または統計的モデル推定法によって、上記シンボル系列生成モデルを学習する
ことを特徴とする有限状態トランスデューサの構造推定装置。
【請求項６】
与えられた入力シンボルの系列（以下、入力系列という）と出力シンボルの系列（以下、出力系列という）を用いた機械学習によって有限状態トランスデューサの構造を推定する方法であって、
有限状態トランスデューサのアークを(ps,k,is,k,os,k,qs,k)として（ただし、ps,k：遷移元の状態、is,k：入力シンボル、os,k：出力シンボル、qs,k：遷移先の状態、(s,k)：アークを示す変数、s：遷移元の状態を特定するための識別子、k：識別子sで特定される遷移元の状態から出ているアーク全てに付与した通し番号）、
(ps,k,is,k,os,k,qs,k)の事前確率を、
基底測度Gsと集中度パラメータαsで定まるディリクレ過程DP(αs,Gs)からサンプルされた離散確率分布であるFs(is,k,os,k,qs,k)と、条件Cが真の時に1を出力しそうでない時に0を出力する指示関数1(C)とを用いて、
P(ps,k,is,k,os,k,qs,k|αs,Gs)=1(ps,k=s)・Fs(is,k,os,k,qs,k;αs,Gs)
と表し、
Nを2以上の予め定められた整数とし、nを1≦n≦Nを満たす整数とし、x=nをn番目の入力系列とし、y=nをn番目の出力系列とし、n番目の入力系列x=nと出力系列y=nとのペアに対応する、有限状態トランスデューサ上の1番目の状態からJn番目の状態までをつなぐ経路を上記(s,k)の系列としてπ=n={(sn,1,kn,1),(sn,2,kn,2),…,(sn,j,kn,j),…,(sn,Jn,kn,Jn)}のように表わすとし、I={is,k|∀s,∀k}とし、O={os,k|∀s,∀k}とし、Q={qs,k|∀s,∀k}とし、I*を1番目の状態になりえる状態の集合とし、f(sn,Jn)を状態sn,Jnに関連付けられている終了状態の重みとして（ただし、状態sn,Jnが終了状態でない場合はf(sn,Jn)=0とする）、
n番目の入力系列x=nと出力系列y=nとのペアに対応する経路π=nが表われる確率を、
【数１２】
0005951562.tif 000013
と表し、
経路π=nに対応するn番目の入力系列x=nと出力系列y=nを、シンボル系列から無為を表すシンボルεを取り除くオペレータR[・]を用いて、
【数１３】
0005951562.tif 000014
と表す、有限状態トランスデューサによるシンボル系列生成モデルを用いて、
推定部が、N個の入力系列および出力系列を用いて上記シンボル系列生成モデルを学習することによって、有限状態トランスデューサの構造を推定する推定ステップ
を有する有限状態トランスデューサの構造推定方法。
【請求項７】
コンピュータを、請求項１から請求項５のいずれかに記載の有限状態トランスデューサの構造推定装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限状態トランスデューサの構造を推定する技術に関する。詳しくは、本発明は、入出力例（つまり、学習データ）から直接的に有限状態トランスデューサの構造を推定する技術に関する。
【背景技術】
【０００２】
機械翻訳、音声認識、カナ漢字変換、読み推定などのように、記号(例えば英単語、音響状態、カナ文字、英文字)の列を別の系列(例えば日本語の単語、音声認識結果単語、漢字、音素)に変換する技術全般に利用できる汎用性の高い系列変換技術において、有限状態トランスデューサ(Finite State Transducer; FST)や、その確率的表現である重み付き有限状態トランスデューサ(Weighted FST; WFST)は有用である。FSTやWFSTは記号の列を別の記号の列に変換する処理一般の表現方法である。WFSTはコンピュータでそれを実行したり、等価な処理を行なうハードウェアを設計したりすることが容易なことから、これまでも音声認識や機械翻訳のソフトウェアやハードウェアの設計に使われてきた。
【０００３】
以下、WFSTについて概説する。
WFSTは数学的には7つの集合(Q*,X*,Y*,K*,I*,F*,A*)によって定義される。
Q*は状態集合と呼ばれる集合である。
X*は入力シンボル集合と呼ばれる集合であり、入力系列内で取り得る全要素を網羅する集合である。
Y*は出力シンボル集合と呼ばれる集合であり、出力系列内で取り得る全要素を網羅する集合である。
（具体例：英日翻訳を表現するWFSTであればX*は全英単語集合、Y*は全日本語単語集合であり、英語の読み推定WFSTであればX*はアルファベットの集合、Y*は英語音素の集合となる。）
K*は重み集合と呼ばれる集合であり、演算子(×)，(＋)を用いて半環を構成することができることが要請される(以降、和の単位元を0-、積の単位元を1-と書く)。
I*は初期状態集合と呼ばれる集合であり、Q*の部分集合I*⊂Q*である。
F*は終了状態集合と呼ばれる集合であり、Q*×K*の部分集合F*⊂(Q*×K*)である。ここで記号×は集合の直積操作を表わす。
A*はアーク集合と呼ばれる集合で(Q*×X*~×Y*~×Q*×K*)の部分集合である。すなわち、A*⊂(Q*×X*~×Y*~×Q*×K*)。ここでX*~およびY*~はそれぞれX*~=X*∪{ε}およびY*~=Y*∪{ε}で定義され、それぞれのシンボル集合に無為を表すシンボルεを加えたものである。
【０００４】
重み集合として何を使うかはWFSTの応用分野によって異なるが、多くの応用分野では、重み集合を用いて系列変換の確率的動作を表わす。このため、便宜的に、本明細書でもこのような重みの定義に準じる。すなわち、重み集合K*として正の実数集合R+を用いて、演算子の定義としてw1(×)w2=w1w2; w1(＋)w2=w1+w2を用いる。また1-=1; 0-=0である。
【０００５】
直感的な説明として、WFSTは例えば図4(a)のような状態遷移図を用いて入力系列から出力系列への変換を定義する。図中の丸囲みが状態を表示している。すなわち、この例の場合、Q*={1,2,3}である（数字は状態番号を表している）。また、特に、二重丸囲みで表示されている状態が先頭状態である。すなわちI*={1}である。また、太線で描いた丸囲みで表示されている状態が最終状態であり、スラッシュの後ろに書いてある数値が終了状態に対応する重みである。この例の場合、1が太線の二重丸で囲まれているためF*={(1,0.5)}である。なお、1-=1，0-=0であるが、状態番号の1，0と紛らわしいため、1や0の時に限り、重みであることを明示し1-，0-の表記を使うことにする。このWFSTが変換できる入力シンボルはX*={a,b,c}であり出力シンボルはY*={x,y}である。この例の場合のアーク集合は以下のように表わされる。
A*={(1,a,ε,2,0.5),(2,b,ε,3,1-),(3,ε,x,1,0.5),(3,c,y,1,0.5)}
【０００６】
WFSTは入出力の関係を確率的な状態遷移を通して定義する。上述の例の場合、初期状態を初期状態集合のうちから一つ選ぶ。例では初期状態集合は一つの要素しか持たないため、状態1から変換がスタートする。次の時刻でどの状態に遷移できるかはアーク集合によって決まる。アーク集合内のアーク(p,i,o,q,w)の最初の要素pは遷移元の状態を表わし、4番目の要素qは遷移後の状態を表わす。i,oはその遷移中に入出力されるシンボルを表わし、wはその遷移が起こる確率を表わす。アーク集合A*中、遷移元状態番号が1になる要素は(1,a,ε,2,0.5)のみである。これはすなわち、状態1から次の時刻に到達できる状態は2だけであり、そこに移動する間に入力系列から"a"を読み込まなければならないことを示している。また出力シンボルεはその遷移で何も出力しないことを示している。また、状態1は終了状態でもあるため、遷移が起こらず、そのまま変換処理が終了する場合もある。終了の確率は、終了状態重みによって示され、例の場合、遷移する確率が0.5、終了する確率が0.5である。
同様に、状態2はアーク(2,b,ε,3,1-)のみを持ち、次の時刻で到達できる状態は必ず状態3であり、その遷移の間にはbを読み込み何も出力しない。状態3は複数のアーク(3,ε,x,1,0.5),(3,c,y,1,0.5)を持つ。これは「状態3から何も入力せずに"x"を出力して状態1に至る」確率が0.5であり、「状態3から"c"を読み込んで"y"を出力して状態1に至る」確率が0.5であるということを表わしている。
【０００７】
確率計算の例を示すと、入力系列をx=、出力系列をy=とした時、以下のような確率が導出できる。
（ア）何も遷移せずに終了した場合:
P(x=={};y=={})=0.5
（イ）a:ε→ b:ε→ε:xと遷移した場合:
P(x=={a,b};y=={x})=0.5×1-×0.5×0.5=0.125
（ウ）a:ε→ b:ε→ c:yと遷移した場合:
P(x=={a,b,c};y=={y})=0.5×1-×0.5×0.5=0.125
（エ）a:ε→ b:ε→ε:x → a:ε→ b:ε→ c:yと遷移した場合:
P(x=={a,b,ab,c};y=={x,y})=0.5×1-×0.5×0.5×0.5×1-×0.5×0.5=0.016525
【０００８】
変換処理を表わすWFSTを定めた上で実際の変換処理を実行するには様々な方法があり、これまでも音声認識や機械翻訳の分野で論じられてきたが、その前段階であるWFSTをどのように作成するかについては、WFSTの応用分野を問わず重要なテーマである。
【０００９】
これまで、WFSTを得るために最もよく用いられてきたものは、以下の二つである。
（A）専門家がWFSTを直接設計することによってそれを得る。
（B）WFSTに等価に変換できる統計モデル(HMMやN-gram)の統計的推論を用いて、変換処理の入出力例から学習することにそれをよって得る。
【００１０】
以下、後者（B）の例を説明する。
【００１１】
＜Joint Sequence ModelによるWFST構造の推定＞
入出力例(以降、学習データという)から自動でWFSTの構造を推定する手法について述べる。従来は直接にWFSTを推定する手法が存在しなかったため、Joint Sequence Modelに基づく推定手法では、Joint Sequence Modelと呼ばれる統計モデルを先に推定した後にそれをWFST形式に変換する。他にも様々なWFSTの作成法があるが、既存の学習データから推論するための手法は全て、このJoint Sequence Modelに基づく推定方法と同様、別の統計モデルの推定アルゴリズムを経由したものとなる。
【００１２】
Joint Sequence Modelに基づく手法では、学習データに含まれる入力系列と出力系列が同じ長さを持っていることを仮定する。もし、そうでないようなデータを扱う場合(読み推定の場合など)、あらかじめ他の方法を用いて学習データ中に含まれる各入力系列と出力系列の長さを適切な箇所にεシンボルを挿入することによって同じにしておく必要がある。
【００１３】
学習データはZ*={z=1,z=2,…,z=n,…}のように入出力系列のペアz=nの集合として表わすことができ、各入出力系列ペアz=nは入力系列と出力系列の長さが同じことから、z=n={zn,1=(xn,1,yn,1),zn,2=(xn,2,yn,2),…,zn,j=(xn,j,yn,j),…}のように、各系列中のシンボルのペアzn,j=(xn,j,yn,j)の系列として表わすことができる。この表現の上で、従来より系列データの統計モデルとしてよく用いられてきたN-gramモデルを入出力シンボルのペアを一つのシンボルとみなして適用することを考える。
【００１４】
N-gramモデルを用いた場合、学習データ中の系列ぺアz=nの出現確率を式（１）のように定義することができる。たとえば、Trigram (3-gram) モデルを用いた場合、式（２）のようになる。この確率モデルの推定は、様々な方法によって行なうことができる。
【数１】
0005951562.tif 000002
【００１５】
このJoint Sequence Modelを用いて、等価なWFSTを以下のように作成することができる。全ての観測された入出力シンボルペアの集合をV*(上記のWFSTの表記に合わせて書く場合、V*=(X*~×Y*~)である)と置く。まず、全てのシンボルペアの二つ組(ただし、Trigram の場合；一般のN-gramの場合であれば、(N-1)個の組)の数|V*|N-1個の状態があると考え、Q*={1,…,|V*|N-1}とおく。また、特定の二つ組(z,z′)に対応する状態をS[z,z′]とおくこととする。アーク集合は全てのシンボルペアの三つ組み(z,z′,z″)を考え、以下のように定義される。
A*={S[z″,z′],x,y,S[z′,z],P(z|z′,z″) | ∀(x,y)=z∈V*, ∀z′∈V*, ∀z″∈V*}
【００１６】
Joint Sequence Modelでは、音声認識の言語モデル学習技術などで培われた各種高精度化手法(補完、バックオフなど)が応用可能な反面、パラメータ数(状態数やアーク数)が必要以上に多くなる傾向にあることから、計算資源の面からは適切でない場合が多い。
【００１７】
＜その他の既存技術＞
アークと状態の構造が決まった上で、重みパラメータのみを調整する試みは、以前から広く行なわれてきた。例えば、非特許文献１ではWFSTの重みを最適に調整する手法を提供している。このような試みは全て、WFST中にアークが何個、どの状態からどの状態に向かって存在しているかが定まった上での最適化であり、構造を最適化する枠組みとは異なる。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】M. Lehr, I. Shafran, "Learning a Discriminative Weighted Finite-State Transducer for Speech Recognition," IEEE Transactions on Audio, Speech, and Language Processing, Vol. 19, No.5, July 2011.
【発明の概要】
【発明が解決しようとする課題】
【００１９】
既述の（A）の方法では、特に複雑な変換処理を必要とする場合、例外なく全ての変換処理を表現するために多大な労力(コスト)が必要になるが、もし正しく表現できさえすれば、非常にコンパクトなWFSTを得ることができる。
また、既述の（B）の方法では、学習によってWFSTを得ることのメリットがあるが、構造に関しては変換元の統計モデルの形をそのまま受け継ぐため、構造の意味で変換の処理に適した形になっているとは言いがたい。
【００２０】
したがって、既述の（A）の方法と（B）の方法の良いところを組み合わせた、入力系列と出力系列から機械学習によって系列変換に適したWFSTの構造を直接推定する手法が求められている。つまり、他のモデルを通すことなくWFSTの意味で最適な形になるように学習データからWFSTを得ることが望まれている。
【００２１】
このような観点から、本発明は、与えられた入力系列と出力系列を用いた機械学習によって有限状態トランスデューサの構造を推定する技術を提供することを目的とする。
（なお、WFSTの「構造最適化」という言葉は、与えられたWFSTをより小さくする「最小化」と呼ばれる処理や、計算機上での扱いを容易にするための「決定化」と呼ばれる処理の総称として利用されることがあるが、本発明はそれらとは関係がない。これらの技術はなんらかの別の手法でWFSTを得た後にそれらを良くする方法であって、入出力の例からWFSTを直接構築する方法ではない）
【課題を解決するための手段】
【００２２】
与えられた入力シンボルの系列（入力系列）と出力シンボルの系列（出力系列）を用いた機械学習によって有限状態トランスデューサの構造を推定する技術であって、有限状態トランスデューサのアークを(ps,k,is,k,os,k,qs,k)として（ただし、ps,k：遷移元の状態、is,k：入力シンボル、os,k：出力シンボル、qs,k：遷移先の状態、(s,k)：アークを示す変数、s：遷移元の状態を特定するための識別子、k：識別子sで特定される遷移元の状態から出ているアーク全てに付与した通し番号）、(ps,k,is,k,os,k,qs,k)の事前確率を、基底測度Gsと集中度パラメータαsで定まるディリクレ過程DP(αs,Gs)からサンプルされた離散確率分布であるFs(is,k,os,k,qs,k)と、条件Cが真の時に1を出力しそうでない時に0を出力する指示関数1(C)とを用いて、
P(ps,k,is,k,os,k,qs,k|αs,Gs)=1(ps,k=s)・Fs(is,k,os,k,qs,k;αs,Gs)
と表し、Nを2以上の予め定められた整数とし、nを1≦n≦Nを満たす整数とし、x=nをn番目の入力系列とし、y=nをn番目の出力系列とし、n番目の入力系列x=nと出力系列y=nとのペアに対応する、有限状態トランスデューサ上の1番目の状態からJn番目の状態までをつなぐ経路を上記(s,k)の系列としてπ=n={(sn,1,kn,1),(sn,2,kn,2),…,(sn,j,kn,j),…,(sn,Jn,kn,Jn)}のように表わすとし、I={is,k|∀s,∀k}とし、O={os,k|∀s,∀k}とし、Q={qs,k|∀s,∀k}とし、I*を1番目の状態になりえる状態の集合とし、f(sn,Jn)を状態sn,Jnに関連付けられている終了状態の重みとして（ただし、状態sn,Jnが終了状態でない場合はf(sn,Jn)=0とする）、n番目の入力系列x=nと出力系列y=nとのペアに対応する経路π=nが表われる確率を、
【数２】
0005951562.tif 000003
と表し、経路π=nに対応するn番目の入力系列x=nと出力系列y=nを、シンボル系列から無為を表すシンボルεを取り除くオペレータR[・]を用いて、
【数３】
0005951562.tif 000004
と表す、有限状態トランスデューサによるシンボル系列生成モデルを用いて、N個の入力系列と出力系列とを用いて上記シンボル系列生成モデルを学習することによって、有限状態トランスデューサの構造を推定する。
【００２３】
入力シンボルiと出力シンボルoと遷移先の状態qを確率変数とする上記基底測度Gsを、入力シンボルiと出力シンボルoを確率変数とする基底測度G(IO)sと遷移先の状態qを確率変数とする基底測度G(ST)sとを用いて、
Gs(i,o,q)=G(IO)s(i,o)・G(ST)s(q)
と表すことができる（ただし、G(IO)sは基底測度G(IO)0と集中度パラメータβ0で定まるディリクレ過程DP(β0,G(IO)0)からサンプルされた離散確率分布であり、G(ST)sは基底測度G(ST)0と集中度パラメータγ0で定まるディリクレ過程DP(γ0,G(ST)0)からサンプルされた離散確率分布である）。
【００２４】
また、集中度パラメータαsは、ガンマ分布Gam(αs;a0,b0)に従う確率変数とすることができる（ただし、a0はガンマ分布の形状パラメータであり、b0はガンマ分布のスケールパラメータである）。
【００２５】
また、N個の入力系列および出力系列を用いて、入力系列から対応する出力系列への全ての変換においてアークを通った累積回数に比例する確率として重みを算出することができる。
【００２６】
上記推定処理では、例えば、マルコフ連鎖モンテカルロ法または統計的モデル推定法によって、上記シンボル系列生成モデルを学習することができる。
【発明の効果】
【００２７】
本発明によると、他の統計モデルの構造を介さず、WFSTの構造を入出力系列から直接推定するため、従来法よりコンパクトなWFSTが得られることが期待できる。コンパクトなWFSTを用いた変換は、変換処理の実現に必要な計算資源が小さくて済むことが知られている他、専門家による解釈／改変も容易であり、可用性が高い。
【図面の簡単な説明】
【００２８】
【図１】シンボル系列生成モデルをプレート図。
【図２】実施例の構造推定装置の機能構成図。
【図３】実施例の構造推定処理の処理フロー。
【図４】(a)実験で入出力系列を生成するために用いた状態遷移図。(b)生成された入出力系列を用いて構造推定装置によって推定された状態遷移図。
【図５】実験における音素エラー率とパラメータ数(アーク数)との関係。
【発明を実施するための形態】
【００２９】
本発明は、学習データすなわち、ある系列変換装置の入出力例から、その入出力を実現するために有効なWFSTの構造を推定する技術に関するため、まず入出力例の集合Z*をZ*={(x=1,y=1),(x=2,y=2),…,(x=n,y=n),…}と定義する。ここでx=nはn番目の入力系列例、y=nはn番目の出力系列例である。先述したJoint Sequence Modelの場合と異なり、入力系列x=nと出力系列y=nは同じ長さである必要がない。
【００３０】
本発明では、この学習データからWFSTを表わす7つの集合(Q*,X*,Y*,K*,I*,F*,A*)のうちQ*の要素数S=|Q*|とアーク集合A*を直接推定する。一般的な利用法におけるWFSTでは状態Q*の各要素に特別な意味を持たせず、単に自然数1，…，|Q*|を与えるため、この仮定は自然である。また、I*とF*を直接推定しないことに関しても、任意のWFSTから、その初期状態および終了状態を一つにまとめた等価なWFSTが作れるため、自然な仮定と言える。
【００３１】
《理論》
＜WFSTの生成プロセス＞
本発明はノンパラメトリック・ベイズ理論に基づくWFSTの生成プロセスを通して、データを観測した上でWFSTが従う確率過程をシミュレーションすることによって、適切なWFSTを得る。
【００３２】
最初にWFSTの生成プロセスにおける事前確率過程を定義する。事前確率過程はデータが全く得られなかった場合に、WFSTがどのように生成されているかを示す確率過程である。
WFSTの生成確率過程を考えるにあたり、アークの表現を少し変更する。これまでアークは重みwを含む五つ組(p,i,o,q,w) (ここでpは前状態、iは入力シンボル、oは出力シンボル、qは次状態) として表わしてきたが、wはそのアークを用いて実際にデータが変換される確率であるとも考えることができるので、wに関しては省略し、四つ組(ps,k,is,k,os,k,qs,k)の出現確率を直接考えてもよい(実際のws,kは学習データで(s,k)に対応するアークによる変換が何度使われたかをカウントすることによって推定できる)。なお、以降、アークを示す変数、すなわち前状態ps,k、入力シンボルis,k、出力シンボルos,k、次状態qs,kはどの状態を前状態として持つかを示す添字sとその状態から出ているアーク全てに付与した通し番号kを添字として利用することで区別することとする。
【００３３】
この四つ組の事前確率を式（３）のように定義する。
P(ps,k,is,k,os,k,qs,k|αs,Gs)=1(ps,k=s)・Fs(is,k,os,k,qs,k;αs,Gs)        （３）
【００３４】
ここで1(C)は指示関数の一種であり、条件Cが真の時に1を、そうでない時に0を出力する関数とする。また、ここでFs(is,k,os,k,qs,k)はディリクレ過程からのサンプルとして得られる多項分布であると考え、式（４）の確率分布からのサンプルだと考える。Fsはアーク変数is,k,os,k,qs,kの従う確率分布であり、ディリクレ過程からサンプルされた離散確率分布であると考える。ここで、DPはディリクレ過程を表わし、αsはアークがどの程度多数あるかを示すアーク集中度パラメータである。
P(Fs|αs,Gs)=DP(Fs；αs,Gs)          （４）
【００３５】
このディリクレ過程の基底測度Gs(以降、この基底測度をアーク基底測度と呼ぶ)は式（５）のように表わされることとする。ディリクレ過程における基底測度は、その対象がどれくらいの確率で表われるかを示す。反面、ディリクレ過程からのサンプルは実際に現われたものを表わし、多く現われたものがより多く現われるようなパターンを示すような確率過程となっている。
Gs(i,o,q)=G(IO)s(i,o)・G(ST)s(q)          （５）
【００３６】
この基底測度の定義はG(I)s(i)・G(O)s(o)・G(ST)s(q)のように三つの基底測度の積として表わしても良いが、本実施例では上記の場合を説明する。
【００３７】
上記と同様に、入出力シンボルの基底測度も全状態間で共有されたディリクレ過程からのサンプルであると仮定する。
P(G(IO)s|β0,G(IO)0)=DP(G(IO)s;β0,G(IO)0)          （６）
P(G(ST)s|γ0,G(ST)0)=DP(G(ST)s;γ0,G(ST)0)          （７）
【００３８】
ここで登場したシンボル集中度パラメータβ0、状態集中度パラメータγ0、共有シンボル基底測度G(IO)0、共有状態基底測度G(ST)0は他の変数と同様に確率変数として扱い、推定を行なってもよいが、本実施例ではこれらの値は所与のものとする。
【００３９】
アーク集中度パラメータαsは、式（８）のようにガンマ分布に従う変数であると仮定する。
P(αs)=Gam(αs;a0,b0)          （８）
【００４０】
集中度パラメータはディリクレ過程における各サンプルがどの程度まとまっているかを示すパラメータであり、この値が小さいほど、多く現われたサンプルと同じ値のサンプルが大量に現われるようになる。集中度パラメータそのものを確率変数として表わすことで、状態毎に異なるアークの集中度を持つことが許容される。集中度パラメータ全体が持つ特性は上述のガンマ分布の形状パラメータa0およびスケールパラメータb0によって調整可能である。
【００４１】
ここで、n番目の学習データに対応するWFST上の変換経路(以降、パスともいう)を、アークを示す添字(s,k)の系列としてπ=n={(sn,1,kn,1),(sn,2,kn,2),…,(sn,j,kn,j),…,(sn,Jn,kn,Jn)}のように表わす。
【００４２】
WFSTの構造を集合I={is,k|∀s,∀k}、O={os,k|∀s,∀k}、Q={qs,k|∀s,∀k}で表わす。このうちQがあった時、入力系列x=nおよび出力系列y=nに関連付いたパスπ=nが表われる確率は式（９）のように表すことができる。
【数４】
0005951562.tif 000005
【００４３】
ここで、f(sn,Jn)は状態sn,Jnに関連付いている終了状態重みであり、状態sn,Jnが終了状態でない場合はf(sn,Jn)=0-とする。
【００４４】
パスπ=nが定まった場合、それに対応する入出力系列x=n、y=nは、シンボル系列からεを取り除くオペレータR[・]を用いて式（１０）のように定義することができる。
【数５】
0005951562.tif 000006
【００４５】
これまで説明したシンボル系列生成モデルをプレート図で示すと図1のようになる。
【００４６】
＜WFSTのサンプリング＞
全変数が上述の確率的関係に従うと考えた時、学習データZ*が観測された際のアーク構造を表わす変数の事後分布P(I,O,Q|Z*)を計算することによって、学習データZ*を変換するのに用いることができるWFSTを推定することができる。本発明は前述のモデルに従って、構造変数事後分布P(I,O,Q|Z*)を近似計算する何らかの手法によってWFST構造を推定する技術全般に関するものであるが、ここでは実現法の一例として、マルコフ連鎖モンテカルロ法のアルゴリズムである近似Gibbs SamplingによるWFSTの推論について説明する。近似Gibbs Samplingによる手法では、P(I,O,Q|Z*)を直接計算するのではなく、P(I,O,Q|Z*)に従うサンプルを複数個生成し、それらを併合するか、または単に一つだけ抽出するかによって適切なWFSTを得る。
【００４７】
なお、近似Gibbs Samplingを用いる他にも、変分ベイズ法やExpectation Propagation法などの統計的モデル推定法によって、構造の推定を行なうこともできる。
【００４８】
Gibbs Samplingによる方法では、P(I,O,Q|Z*)からのサンプルを、関連する全ての確率変数、すなわちI,O,Q,α=={αs|∀s},P*={π=n|∀n},G*(IO)={G(IO)s|∀s},G*(ST)={G(ST)s|∀s}を交互に他の変数の確率分布をサンプルされた値で近似してサンプリングしていくことによって得る。実施例ではハイパーパラメータにあたるa0,b0,β0,γ0,G(IO)0,G(ST)0は手動で与えたものを変化させずに使う。ただし、これらに関しても事前分布を与え、さらにサンプリングしても良い。
【００４９】
以降、P(α=|I,O,Q,a0,b0,P*,β0,γ0,G*(IO),G*(ST))のような、α=以外の全ての変数が与えられた上でのα=の確率分布をP(α=|rest)と記述することにする。
【００５０】
アーク集中度αsのサンプリングはアーク集中度以外の変数を固定した上でのアーク集中度の確率分布P(αs|rest)からのサンプリングを行なうことで実行できる。P(αs|rest)は式（１１）のようになる。
【数６】
0005951562.tif 000007
【００５１】
このような分布からのサンプルを生成するには参考文献１に記載されている方法を用いることができる。
（参考文献１）M. West, "Hyperparameter estimation in Dirichlet process mixture models"  （インターネット〈URL: http://www.stat.duke.edu/~mw/.downloads/DP.learnalpha.pdf〉［平成25年8月7日検索］）
【００５２】
P(G(ST)s|rest)のサンプリングについてはStick Breaking Processを途中で打ち切ることによって実現できる。Stick Breaking Processについては例えば参考文献２を参照されたい。
（参考文献２）Sethuraman, J., A constructive definition of Dirichlet priors, Statistica Sinica, 4, 639-650, 1994.
【００５３】
ここでは、特に状態の共有状態基底測度G(ST)sとして無限次元一様分布を用いた場合について説明する。Stick Breaking Processはディリクレ過程(DP)と等価な別表現であり、G(ST)sを式（１２）のように計算することができる。ここで、Betaはベータ分布の確率密度関数を表わす。また、ベータ分布からのサンプルの生成は容易である。c(ST)s′およびc(ST)s″は集合Q中でqs,k=s′およびqs,k=s″となる要素の数である。s″上限数s~は厳密な計算のためにはs~=∞とする必要があるが、これを有限の値で打ち切ってしまうことで式（１２）からのサンプリングを近似計算できる。
【数７】
0005951562.tif 000008
【００５４】
入出力シンボルに関する基底測度G(IO)sは状態に関する基底測度G(ST)sと異なり、シンボルの取り得る通り数は有限個である。よって、ここではディリクレ分布を用いたディリクレ過程の表現を用いることができる。
P(G(IO)s|I,O,β0,G(IO)0)=Dir(η=)          (１３)
【００５５】
ここでDirはディリクレ分布の確率密度関数であり、η=はそのハイパーパラメータを表わす。η=は全ての取り得る入力シンボルi′、出力シンボルo′に関するハイパーパラメータηi′,o′を並べたベクトルであり、各要素ηi′,o′は式（１４）のように計算できる。
ηi′,o′=β0G(IO)0(i′,o′)+c(IO)i′,o′          (１４)
【００５６】
ここで、c(IO)i′,o′は集合I,O中でis,k=i′かつos,k=o′となる(s,k)の数である。ハイパーパラメータが計算できる場合のディリクレ分布からのサンプリングは、例えばガンマ分布からのサンプルを非負で合計が１になるように正規化することによって可能である（例えば参考文献３参照）。
（参考文献３）A. Gelman, J. B. Carlin, H. S. Stern, D.B. Rubin, “Bayesian Data Analysis, Second Edition,” Chapman and Hall, p. 582, 2003.
【００５７】
パスπ=nの効率的なサンプリングのためにはChinese Restaurant Processを援用した近似を導入する。Chinese Restaurant Processについては例えば参考文献４を参照されたい。
（参考文献４）Aldous, D., Exchangeability and Related Topics, Ecole dete de probabilites de Saint-Flour, XIII, 1983, pp.1-198.
【００５８】
π=nを各要素πn,jごとにサンプリングすることも考えられ、この場合、近似は必要ないが、本実施例ではπ=nをまとめてサンプリングすることを考え、その効率的な計算のために近似を導入する。近似を導出するため、本実施例では各パスπ=n={(sn,1,kn,1),(sn,2,kn,2),…}において同じ状態に至ることがない(sn,j≠sn,j′(j≠j′))と仮定した時の分布からサンプルを行なうことを考える。
【００５９】
本実施例におけるChinese Restanrant Processの適用では、π=nのサンプリングのためにまず、各アークの生成確率を記述した離散分布Fsを周辺化によって消去したパス事前確率Q(¬n)(π=n)=P(π=n|Π(¬n),α=,a0,b0,P*,β0,γ0,G*(IO),G*(ST))を考える。ただし、ここでΠ(¬n)はn番目のパスを除く全てのパス変数、すなわちΠ(¬n)={π=n′|∀n′,n′≠n}である。
【００６０】
ここで、先述の仮定(一つのπ=nで同じ状態に至ることがない)を導入すると、パス事前確率Q(¬n)(π=n)を以下のようにq(¬n)(sn,j,kn,j)の積として定義できる。ここでC(¬n)(s,k)はΠ(¬n)中に登場した(s,k)の回数であり、K(¬n)sはΠ(¬n)の中に登場する(s′,k′)の中で、s′=sとなる場合のk′の最大値を示す。すなわち、条件k=K(¬n)s+1は他の観測データを変換するのには登場しなかったアークが新たに登場する確率を示す。
【数８】
0005951562.tif 000009
【００６１】
このようにパス事前確率Q(¬n)(π=n)が各アークに対応する要素毎の積で書ける場合、そのQ(¬n)(π=n)に対応するWFSTを構築することができ、後述の合成演算を用いたサンプリングを実行することができる。
【００６２】
パスの事後確率P(π=n|Π(¬n),rest)は上記のパス事前確率Q(¬n)(π=n)にパスがあった時の入出力系列の確率P(x=n,y=n|π=n)をかけることによって式（１６）のように得られる。
【数９】
0005951562.tif 000010
【００６３】
この計算のためにはWFSTの合成演算を用いることができる。あらかじめパス事前分布によって規定される可能なパスの集合とその上の確率測度をWFSTによって表わしておけば、パス事前分布T(¬n)を表現するWFST[T(¬n)]と入力系列x=を表現するWFST[x=]、出力系列y=を表現するWFST[y=]を、合成演算(・)を用いてx=(・)T(¬n)(・)y=のように合成することによって、パスの事後確率によって規定される可能なパスの集合と、その上の確率測度を表現したWFSTを得ることができる。よって、パスのサンプリングは合成WFST[x=(・)T(¬n)(・)y=]の経路をなんらかの方法でサンプリングすることによって得ることができる。このサンプリングはN-bestを生成し、そこからサンプルすることで近似できる。また、G(IO)0(εε)=0-の場合は、合成WFSTは非循環グラフになることが知られているため、前向き後ろ向きサンプリングと呼ばれる手法（参考文献５参照）を使うことで、高速に厳密なサンプリングを行なうこともできる。
（参考文献５）E. B. Fox, E. B. Sudderth, M. I. Jordan, A. S. Willsky,“A Sticky HDP-HMM with Application to Speaker Diarization,” The Annals of Applied Statistics, Vol. 5, No. 2A, pp. 1020-1056, 2011.
【００６４】
このWFST生成プロセスの性質上、一度P*に登場した(s,k)に対応するI,O,Qの値が変わることはない。よって、I,O,Qの推定には、過去に出現していない(s,k′)の時、すなわち(s,k′=K(¬n)s+1)の時のみを考えればよい。ディリクレ過程に基づくモデリングの場合、新たなアークに関連するアークパラメータis,k′,ss,k′,os,k′は基底測度、すなわち入出力シンボル基底測度G(IO)sと、次状態基底測度G(ST)sに従うと考える。
【００６５】
以上を踏まえ、T(¬n)の構築は以下のように行なう。T(¬n)の状態集合をG(q)s≠0となる最大のqの値q^を用いてQ*={1,…,q^}のように定義する。Q*中の各状態sについて、Π(¬n)中に登場する(s′,k′)について、s′=sの時、アーク集合A*に(s,is′,k′,os′,k′,qs′,k′,q(¬n)(sn,j,kn,j))を追加する。加えて、全ての可能な入出力シンボルと次状態(i′,o′,q′)について、(s,i′,o′,q′,q(¬n)(sn,j,K(¬n)s+1),G(IO)s(i′,o′),G(ST)s(q′))を追加する。
【００６６】
以上のサンプリングプロセスを実現する装置によって、適切なWFSTを推定する装置を構成することができる。
【００６７】
《実施例》
上述した理論を実現するための構造推定装置の機能構成図の例を図2に、構造推定装置における構造推定処理の処理フローを図3に示す。ここでは図3の処理フローのステップ毎に構造推定装置の動作例を示す。構造推定装置は、N個の入力系列と出力系列とを用いて上述のシンボル系列生成モデルを学習することによって、有限状態トランスデューサの構造を推定する推定部を含むが、近似Gibbs Samplingによって推定を行う推定部は、図2に示すように、初期WFST格納部10A、ハイパーパラメータ格納部10B、パス格納部10C、事前分布格納部10D、学習データ格納部10E、初期パス決定部11、乱数発生部12、事前分布計算部13、WFST構築部14、WFST合成部15、パスサンプル部16を含む。
【００６８】
＜S1:WFST初期化／ハイパーパラメータ初期化ステップ＞
WFST初期化ステップでは、初期状態のWFST構造の推定値が特定される。例えば、初期状態のWFST構造の推定値を、入出力シンボル状態基底測度からランダムにサンプリングして作成してもよいし、あるいは、一状態WFST(状態1しか持たないWFST)を考え、アーク集合をA*={(1,i′,o′,1,1-)|∀i′∈X*~,∀o′∈Y*~}としたWFSTを初期状態のWFST構造としてもよい。また、従来技術のように、他の装置によって他の確率モデルの推定結果から変換して得られた構造を初期状態のWFST構造とみなしてもよい。初期状態のWFST構造の推定値は、初期WFST格納部10Aに記憶される。
また、ハイパーパラメータ初期化ステップでは、他の装置で推定した結果や専門家が調整した結果として得られるハイパーパラメータがハイパーパラメータ格納部10Bに記憶される。
これらのステップは初期化処理なので、図2では該当処理を行なう構成要素を図示していない。この例では、初期WFST格納部10Aとハイパーパラメータ格納部10Bの各データはそれぞれ他の装置によって得られたデータを用いるとする。
【００６９】
＜S2:パス初期化＞
パス初期化ステップでは、初期パス決定部11が、各入出力系列x=n,y=nが初期WFSTのどの経路で変換されているかを決定し、それを初期値とする。例えば、初期パス決定部11が、この経路を、乱数発生部12が発生した乱数を用いてランダムに求めてもよいし、初期パス決定部11が、他の装置で計算したものを利用するとしてもよい。この処理の後、パス格納部10Cには学習データ格納部10Eに格納されている入出力例x=n,y=nと同数、すなわちN個のパスπ=nが格納されることになる。つまり、この処理によって、パス格納部10Cのデータが初期化される。
【００７０】
＜S3:ランダムに入出力例を選ぶ＞
乱数発生部12が発生させた乱数を元に、ランダムに1からN（Nは２以上の予め定められた整数）の自然数乱数を生成する。選択された自然数nは、事前分布計算部13、WFST構築部14、WFST合成部15、パスサンプル部16に供給される。
【００７１】
＜S4:事前分布サンプリング＞
事前分布サンプリングステップでは、事前分布計算部13が、パス格納部10Cおよびハイパーパラメータ格納部10Bに格納されている情報と、乱数発生部12によって発生された乱数を用いて、以下のサンプリングを行なった結果を事前分布格納部10Dに格納する。
・式(１１)で示される確率分布関数に基づくアーク集中度のサンプリング
・式(１２)で示される確率分布関数に基づく状態基底測度のサンプリング
・式(１３)で示される確率分布関数に基づく入出力シンボル基底測度のサンプリング
【００７２】
なお、このステップS4の処理は、後述するステップS8の処理によってステップS3以降の各処理が繰り返される場合に、必ず実行されるべきものではなく、また、ステップS4の処理にて必ずしも上記の全てのサンプリングを行なう必要もない。例えば、２回目以降のステップS4の処理の実行では、全く更新を行なわなくてもよいし、あるいは、N回に１回の間隔で上記の全てのサンプリングを行なうようにしてもよい。ただし、初回のみは事前分布格納部10Dの初期化のために、必ず全ての処理を行なう必要がある。
【００７３】
＜S5:WFST構築＞
WFST構築ステップでは、WFST構築部14が、パス格納部10Cに格納されているパスと、事前分布格納部10Dに格納された事前分布と、乱数発生部12によって発生された乱数を用いて、式(１５)の確率分布を表現するWFST[T(¬n)]を構築する。この計算は実際に全通りを計算することによって行なってもよいし、後段のWFST合成ステップS6で必要になる度にWFST構築部14がWFST[T(¬n)]の必要な部分のみを構築するという方法をとってもよい。
【００７４】
＜S6:WFST合成＞
WFST合成ステップでは、WFST合成部15が、WFST構築ステップによって構築されたWFSTと学習データ格納部10Eに格納されているn番目の入出力系列をWFST合成アルゴリズムによって合成することによって、取り得る全てのパスが列挙されたWFST[x=(・)T(¬n)(・)y=]を得る。
【００７５】
＜S7:パスサンプリング＞
パスサンプリングステップでは、パスサンプル部16が、WFST合成ステップの結果として得られたWFST[x=(・)T(¬n)(・)y=]の経路を前向き後ろ向きアルゴリズム(Forward-Backward Algorithm)に基づいてサンプリングする。サンプリングの結果はステップS3で選ばれたnに対応するパスの更新値として、パス格納部10Cに格納されているパスを更新する。
【００７６】
＜S8:収束チェック＞
図示しない制御部は、パス格納部10Cに格納されているパスが長期間変わらなかった場合や、十分な回数が繰り返された場合（例えば、十分に大きな値の閾値を予め定めておき、ステップS8の処理が当該閾値に達したか否かを判定する）、もしくは補助的な外部装置を用いて収束性を推定した結果によって収束したと判定された場合に、ステップS3の処理への遷移を止め、次のステップS9の処理を実行するように制御する。そうでない場合は再度ステップS3以降の処理が繰り返される。
【００７７】
＜S9:最終FST構築＞
最終的な構造推定装置の結果は、WFST構築部14がステップS5の処理を再度実行することによって得られる。ここでのステップS5の処理を行なう際、q(¬n)(sn,j,kn,j)を計算するためのnとしてダミーの値(つまり、nは集合{1,…,N}に属さない整数で例えばn=0とする)を与えることによって、全ての学習データの変換においてアークを通った回数に比例した確率値(q(¬n)(sn,j,kn,j))を重みとして算出できる。またアーク集中度αsを0とすることによって、実際に学習データの変換に利用されなかったアークの生成を抑えることができる。なお、後述の検証実験ではこのようにして得た最終WFSTで評価を行なった。
【００７８】
＜検証実験＞
本発明による構造推定装置の有効性を検証するため、データを生成したWFSTの復元と英単語の読み推定を行なった。
WFSTの復元においては、図4(a)で示されるWFSTをランダムに状態遷移することで100個の入出力系列を得た。こうして得た100個の入出力系列から、本来これらを生成したWFST(図4(a))を復元できるかを評価する。
この実験では、真の状態数は既知であるとし、本発明による構造推定装置によって、どのようなアークを持つWFSTが生成されるかを検証した。結果として得られたWFSTは図4(b)となった。図4(b)のWFSTと図4(a)のWFSTは確率値に少し変動が見られるものの、ほぼ等価である。
英単語の読み推定実験では、英単語の文字列と対応する音素列を10006単語分記述した辞書を用いて、文字の系列と英語音素の系列の間の関係を示すWFSTを推定した。得られたWFSTを用いて、辞書に入っていない単語の読みを推定し、正解と比較することで音素エラー率を評価した結果を図5に示す。図中のJoint sequence modelとなっているものは先述した既存技術のものであり、HDP-WFSTが本発明の装置で作成されたWFSTである。図より、本発明で得られたWFSTのほうが、小さいパラメータ数でより音素エラー率の低いWFSTとなっていることがわかる。
【００７９】
＜構造推定装置のハードウェア構成例＞
上述の実施例に関わる構造推定装置は、ＣＰＵ（Central Processing Unit）〔キャッシュメモリなどを備えていてもよい〕、メモリであるＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）と、ハードディスクである外部記憶装置、並びにこれらのＣＰＵやＤＳＰ、ＲＡＭやＲＯＭ、外部記憶装置間のデータのやり取りが可能なように接続するバスなどを備えている。また必要に応じて、構造推定装置に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【００８０】
構造推定装置の外部記憶装置には、上述の構造推定処理のためのプログラム（所与の入力系列と出力系列とを用いて上述のシンボル系列生成モデルを学習することによって、有限状態トランスデューサの構造を推定するためのプログラム）並びにこのプログラムの処理において必要となるデータなどが記憶されている〔外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい〕。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される場合がある。
【００８１】
構造推定装置では、記憶部に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてＲＡＭに読み込まれて、ＣＰＵで解釈実行・処理される。この結果、ＣＰＵが所定の機能（実施例であれば、初期パス決定部11、乱数発生部12、事前分布計算部13、WFST構築部14、WFST合成部15、パスサンプル部16）を実現することで上述の音声モデルの生成が実現される。
【００８２】
＜補記＞
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００８３】
また、上記実施形態において説明したハードウェアエンティティ（構造推定装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００８４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００８５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0005951562.tif 000015
【図２】
0005951562.tif 000016
【図３】
0005951562.tif 000017
【図４】
0005951562.tif 000018
【図５】
0005951562.tif 000019