(57)【特許請求の範囲】
【請求項１】
トークンの第１及び第２のシーケンスを同時セグメント化するための装置であって、前記第１及び第２のシーケンスの各々はブロックにセグメント化されており、前記第１のシーケンスの前記ブロックと前記第２のシーケンスの前記ブロックとは互いにアライメントされてブロック対を形成しており、
前記第１のシーケンスと前記第２のシーケンスとを記憶する第１の記憶手段と、
前記第１のシーケンス及び前記第２のシーケンスの前記ブロック対の各々を同時セグメント化するための同時セグメント化手段と、
前記同時セグメント化手段によって同時セグメント化された前記ブロック対内の同一のフレーズ対の出現を計数する計数手段と、
前記ブロック対における各フレーズ対の出現の計数を記憶する第２の記憶手段と、
前記同時セグメント化手段によって同時セグメント化された前記ブロック対の一つを、非復元的に、ランダムにサンプリングする第１のサンプリング手段と、
前記第２の記憶手段に記憶された前記サンプリングされたブロック対内のフレーズ対の各々の計数から１を減じる減算手段と、
前記第２の記憶手段に記憶された計数を用いて、前記サンプリングされたブロック対に対する全ての可能な同時セグメント化の確率を計算する計算手段と、
前記計算手段によって計算された確率に従って、前記全ての可能な同時セグメント化のうち一つをサンプリングするための第２のサンプリング手段と、
前記第２のサンプリング手段によってサンプリングされた同時セグメント化に従って、前記第２の記憶手段に記憶される前記計数を更新する更新手段と、
前記第１のサンプリング手段、前記減算手段、前記計算手段、前記第２のサンプリング手段、及び前記更新手段を制御して、予め定められた終了条件が満たされるまで繰返し動作させる、繰返し制御手段と、を含む、装置。
【請求項２】
前記第１のサンプリング手段は、
前記繰返し制御手段によって制御される繰返しの各々のはじめに、前記ブロック対をランダムに並べ替えるための並べ替え手段と、
前記並べ替え手段によって並べ替えられたブロック対から、前記繰返しの各々において一度に１つずつ、前記ブロック対をシリアルにサンプリングするシリアルサンプリング手段と、を含む、請求項１に記載の装置。
【請求項３】
前記トークンの第１のシーケンスは第１の言語で用いられる文字のシーケンスであり、前記トークンの第２のシーケンスは第２の言語で用いられる文字のシーケンスである、請求項１に記載の装置。
【請求項４】
前記第１の言語のブロック及び前記第２の言語のブロックは、前記第１の言語の単語及び前記第２の言語の単語である、請求項３に記載の装置。
【請求項５】
コンピュータを、
第１及び第２のシーケンスの各々がブロックにセグメント化され、前記第１のシーケンスの前記ブロックと前記第２のシーケンスの前記ブロックとが互いにアライメントされてブロック対を形成するような、トークンの第１及び第２のシーケンスを記憶する第１の記憶手段と、
前記第１のシーケンス及び前記第２のシーケンスの前記ブロック対の各々を同時セグメント化するための同時セグメント化手段と、
前記同時セグメント化手段によって同時セグメント化された前記ブロック対内の同一のフレーズ対の出現を計数する計数手段と、
前記ブロック対における各フレーズ対の出現の計数を記憶する第２の記憶手段と、
前記同時セグメント化手段によって同時セグメント化された前記ブロック対の一つを、非復元的に、ランダムにサンプリングする第１のサンプリング手段と、
前記第２の記憶手段に記憶された前記サンプリングされたブロック対内のフレーズ対の各々の計数から１を減じる減算手段と、
前記第２の記憶手段に記憶された計数を用いて、前記サンプリングされたブロック対に対する全ての可能な同時セグメント化の確率を計算する計算手段と、
前記計算手段によって計算された確率に従って、前記全ての可能な同時セグメント化のうち一つをサンプリングするための第２のサンプリング手段と、
前記第２のサンプリング手段によってサンプリングされた同時セグメント化に従って、前記第２の記憶手段に記憶される前記計数を更新する更新手段と、
前記第１のサンプリング手段、前記減算手段、前記計算手段、前記第２のサンプリング手段、及び前記更新手段を制御して、予め定められた終了条件が満たされるまで繰返し動作させる、繰返し制御手段と、として機能させる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明はトークンシーケンスのセグメント化に関し、特に、トークンのソースシーケンス及びターゲットシーケンスを同時にセグメント化するための装置に関する。
【背景技術】
【０００２】
音訳の問題を、文字レベルでの機械翻訳の問題と見ることができる。この枠組では、デコードは通常は一方向へに進行すると仮定されるが、それ以外の技術は本質的に同じであって、異なるのはシステムで用いられるトークンが単語ではなく文字であるということだけである。最近では、フレーズベースの統計的機械翻訳技術が盛んに研究されており、この課題について最先端の性能を達成することができる。このアプローチはデータに関し何ら言語学的仮定を行なわず、何ら中間の音声表現を必要としない。なぜなら、変換が、ある書記系から別の書記系へ直接行なわれるからである。
【０００３】
全てのフレーズベースの統計的機械翻訳(statistical  machine  translation:  SMT）システムの中心となるのはフレーズテーブルである。このテーブルは翻訳を構成するのに用いられる構成要素の基礎的な組である。フレーズベースのＳＭＴシステムのための典型的なトレーニング手順でのフレーズテーブルは以下のステップで生成される。
【０００４】
１．ＵＲＬ＝http://fjoch.com/GIZA++.htmlで入手可能なGIZA++を用いて単語アライメントを行なう。
【０００５】
２．（ＵＲＬ＝http://www.statmt.org/moses/で入手可能なMOSESツールキットのgrow-diag-final-and等の）ヒューリスティクスを用いてフレーズ対の抽出を行なう。
【０００６】
このアプローチは実際上非常にうまく働くが、よりエレガントな解決策であれば、生成モデルから１ステップでバイリンガルのフレーズ対の組を得ることができるだろう。残念ながら、この課題にＥＭアルゴリズムを用いて尤度を最大化する伝統的な方法を適用すると、生成される解はデータを大幅に過学習しかねない。極端な例では、コーパスからフレーズ対へのセグメント化として最もありそうなのは、フレーズ対のサイズに制限が無ければ、コーパス全体が全確率を保持する単一のバイリンガルフレーズ対としてアライメントされるものである。フレーズ対のサイズに制限がある場合でも、最終的に全確率が長いフレーズ対に取られて、同じ問題が起こる。
【０００７】
GIZA++は、単語を１対多でアライメントすることによってこの問題を軽減する。アライメントの一方側の単一の単語が、バイリンガル対のサイズの制約として作用する。音訳においてもしばしば同様のアプローチをとることができる。この場合、一方の言語の単一の文字を他方の言語の多数の文字にアライメントすることができるが、逆は不可である。このアプローチは、中国語の１文字がいくつかの英語の文字にマッピングされると仮定できる、英語−中国語の音訳には合理的である。
【０００８】
GIZA++では、この１対多のアライメントが２回行なわれる。ソースからターゲットへと、ターゲットからソースへと、の両者である。その後、これらアライメントの両方から（典型的には積集合から）、単語対単語のアライメントテーブルが構築される。根拠（ｅｖｉｄｅｎｃｅ）と、ヒューリスティックスとに基づいて、積集合にない付加的な単語のアライメントが追加され、最終的に、アライメントテーブルから、テーブルと一貫した可能なフレーズの全てが抽出される。
【０００９】
D．Marcu及びW．Wongは、「統計的機械翻訳のためのフレーズベースの共確率モデル」、ＥＭＮＬＰ予稿集、２００２、１３３−１３９ページにおいて、さらにM．Bisani及びH．Neyは「書記系対書記系変換のための結合シーケンスモデル」、音声通信、第５０巻第５号、４３４−４５１ページ、２００８において、最大尤度トレーニングを用いて直接に多対多のアライメントを行なっているが、モデルがデータに対し過学習となることを防ぐために、利用可能なトレーニングデータの一部を除外する、根拠によるトリミング（evidence  trimming）ヒューリスティクスが必要とされる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】J．Xu、J．Gao、K．Toutanova、及びH．Ney、「統計的機械翻訳のためのベイズ半教師付き中国語単語セグメント化」ＣＯＬＩＮＧ‘０８：第２２回コンピュータ言語学国際会議予稿集、モリスタウン、ＮＪ、ＵＳＡ：コンピュータ言語学会、２００８年、１０１７−１０２４ページ。
【００１１】
【非特許文献２】D．Mochihashi、T．Yamada、及びN．Ueda、「ネストされたピットマン−ヨー言語モデリングによるベイズ教師なし単語セグメント化」、ＡＣＬ−ＩＪＣＮＬＰ‘０９：第４７回ＡＣＬ年次総会及び第４回ＡＦＮＬＰ自然言語処理国際合同会議、予稿集：第１巻、モリスタウン、ＮＪ、ＵＳＡ：コンピュータ言語学会、２００９年、１００−１０８ページ。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
先行技術のほとんどは、ＩＢＭが開発した単語アライメント手順に基づいている（Brown  et  al,  The  Mathematics  of  statistical  machine  translation:  parameter  estimation.  Computational  Linguistics,  19(2),  263-311）。このアプローチでは、過学習のため、多対多のアライメントを直接行なうことはできない。フレーズのシーケンスの長さに制約がない場合、ソーストークンのシーケンス全体とターゲットトークンのシーケンス全体とがアライメントされてしまう。
【００１３】
このため、この発明の目的は、過学習の問題なしに、トークンのソースシーケンスとターゲットシーケンスとを同時セグメント化するための装置を提供することである。
【００１４】
この発明の別の目的は、データについて何ら言語学的仮定をすることなく、過学習の問題なしに、トークンのソースシーケンスとターゲットシーケンスとを同時セグメント化するための装置を提供することである。
【００１５】
この発明のさらに別の目的は、データについて何ら言語学的仮定をすることなく、さらに何ら中間の音声的表現を必要とせずに、過学習の問題なしに、トークンのソースシーケンスとターゲットシーケンスとを同時セグメント化するための装置を提供することである。
【課題を解決するための手段】
【００１６】
この発明の第１の局面は、トークンの第１及び第２のシーケンスを同時セグメント化するための装置に関する。前記第１及び第２のシーケンスの各々はブロックにセグメント化されている。前記第１のシーケンスの前記ブロックと前記第２のシーケンスの前記ブロックとは互いにアライメントされてブロック対を形成している。装置は、前記第１のシーケンスと前記第２のシーケンスとを記憶する第１の記憶装置と、前記第１のシーケンス及び前記第２のシーケンスの前記ブロック対の各々を同時セグメント化するための同時セグメント化装置と、前記同時セグメント化装置によって同時セグメント化された前記ブロック対内の同一のフレーズ対の出現を計数する計数装置と、前記ブロック対における各フレーズ対の出現の計数を記憶する第２の記憶装置と、前記同時セグメント化装置によって同時セグメント化された前記ブロック対の一つを、非復元的に、ランダムにサンプリングする第１のサンプリング装置と、前記第２の記憶装置に記憶された前記サンプリングされたブロック対内のフレーズ対の各々の計数から１を減じる減算装置と、前記第２の記憶装置に記憶された計数を用いて、前記サンプリングされたブロック対に対する全ての可能な同時セグメント化の確率を計算する計算装置と、前記計算装置によって計算された確率に従って、前記全ての可能な同時セグメント化のうち一つをサンプリングするための第２のサンプリング装置と、前記第２のサンプリング装置によってサンプリングされた同時セグメント化に従って、前記第２の記憶装置に記憶される前記計数を更新する更新装置と、前記第１のサンプリング装置、前記減算装置、前記計算装置、前記第２のサンプリング装置、及び前記更新装置を制御して、予め定められた終了条件が満たされるまで繰返し動作させる、繰返し制御装置と、を含む。
【００１７】
好ましくは、前記第１のサンプリング装置は、前記繰返し制御装置によって制御される繰返しの各々のはじめに、前記ブロック対をランダムに並べ替えるための並べ替え装置と、前記並べ替え装置によって並べ替えられたブロック対から、前記繰返しの各々において一度に１つずつ、前記ブロック対をシリアルにサンプリングするシリアルサンプリング装置と、を含む。
【００１８】
第１のシーケンスと第２のシーケンスとはトークンのどのようなシーケンスであってもよい。例えば、シーケンスは言語データであっても、ＤＮＡシーケンスデータであってもよい。
【００１９】
より好ましくは、前記トークンの第１のシーケンスは第１の言語で用いられる文字のシーケンスであり、前記トークンの第２のシーケンスは第２の言語で用いられる文字のシーケンスである。第１の言語と第２の言語とは、同じ言語であっても、異なる言語であってもよい。
【００２０】
さらに好ましくは前記第１の言語のブロック及び前記第２の言語のブロックは、前記第１の言語の単語及び前記第２の言語の単語である。
【００２１】
この発明の第２の局面はコンピュータを、第１及び第２のシーケンスの各々がブロックにセグメント化され、前記第１のシーケンスの前記ブロックと前記第２のシーケンスの前記ブロックとが互いにアライメントされてブロック対を形成しているような、トークンの第１及び第２のシーケンスを記憶する第１の記憶装置と、前記第１のシーケンス及び前記第２のシーケンスの前記ブロック対の各々を同時セグメント化するための同時セグメント化装置と、前記同時セグメント化装置によって同時セグメント化された前記ブロック対内の同一のフレーズ対の出現を計数する計数装置と、前記ブロック対における各フレーズ対の出現の計数を記憶する第２の記憶装置と、前記同時セグメント化装置によって同時セグメント化された前記ブロック対の一つを、非復元的に、ランダムにサンプリングする第１のサンプリング装置と、前記第２の記憶装置に記憶された前記サンプリングされたブロック対内のフレーズ対の各々の計数から１を減じる減算装置と、前記第２の記憶装置に記憶された計数を用いて、前記サンプリングされたブロック対に対する全ての可能な同時セグメント化の確率を計算する計算装置と、前記計算装置によって計算された確率に従って、前記全ての可能な同時セグメント化のうち一つをサンプリングするための第２のサンプリング装置と、前記第２のサンプリング装置によってサンプリングされた同時セグメント化に従って、前記第２の記憶装置に記憶される前記計数を更新する更新装置と、前記第１のサンプリング装置、前記減算装置、前記計算装置、前記第２のサンプリング装置、及び前記更新装置を制御して、予め定められた終了条件が満たされるまで繰返し動作させる、繰返し制御装置と、として機能させる、コンピュータプログラムに関する。
【図面の簡単な説明】
【００２２】
【図１】単語対におけるフレーズ対の例を示す図である。
【図２】バイリンガルコーパスをアライメントするためのサンプリングプログラムの制御の流れ構造を示す図である。
【図３】選択されたバイリンガル単語対で可能な全ての同時セグメント化の確率分布を計算するためのグラフ図である。
【図４】日本語と英語とのフレーズ対の例を示す図である。
【図５】この発明の１実施例で用いられるアルゴリズムの収束を示す図である。
【図６】コンピュータシステムの正面図である。
【図７】コンピュータシステムのブロック図である。
【発明を実施するための形態】
【００２３】
以下の説明及び図面では、同一の部品には同一の参照番号を付してある。したがって、それらについての詳細な説明は繰返さない。
【００２４】
［方法論]
この実施の形態では、既存のモノリンガル単語セグメント化モデルをバイリンガルセグメント化に拡張し、ベイズモデルを用いて、過学習なしで、バイリンガルのトレーニングコーパスを多対多の様態で直接セグメント化する、より簡単でエレガントな方法を提供する。
【００２５】
最近、自然言語処理の分野では、さまざまな問題に対処するためにベイズモデルが提案されており、特に単語セグメント化では有効であることが分かってきた［非特許文献１及び２］。この実施の形態で用いるモデルはユニグラムDirichletプロセスモデルである。このアプローチを用いて、再順序付けを伴う機械翻訳の一般的な事例についてバイリンガルセグメント化を行なうことは困難な課題であるが、シーケンスの長さが短く再順序付けが無いと仮定される音訳では、特別な最適化又はアニーリングの必要なしにバイリンガルセグメント化の問題に対処することは可能であろう（ここではブロックサンプリングアルゴリズムとダイナミックプログラミングアルゴリズムとを用いる）。
【００２６】
同時ソース−チャネルモデル
ソースシーケンス_s1M=<s1,s2,…,sM>及びターゲットシーケンス_t1N=<t1,t2,…,tN>から成るバイリンガルコーパスがあると仮定する。文字シーケンスは、直前にアンダスコア（＿）を付すことによって単一の文字と区別する。
【００２７】
ここでは、H．Li，M．Zhang及びJ．Suの提案する同時ソース−チャネルモデル（「機械音訳のための同時ソース−チャネルモデル」、ＡＣＬ‘０４：コンピュータ言語学会第４２回年次総会予稿集、ＮＪ、ＵＳＡ：コンピュータ言語学会、２００４、１５９ページ）を基礎となる生成モデルに採用し、さらに、セグメントは互いに独立であると仮定した（このアプローチは何らかの付加的な複雑さを対価として、これらの依存性をモデル化するために容易に拡張可能である。非特許文献２を参照）。このモデルの下では、コーパスはバイリンガルフレーズ対（この出願を通じてこれらのタプルに言及するのにこの用語を繰返し用いるが、『フレーズ』という用語はやや誤解を生じやすい。なぜなら、ここでは、フレーズの要素は単語ではなく文字（トークン）だからである。この用語を採用したのは、フレーズベースの機械翻訳で用いられる同じ用語と類似しているからである。）の結合によって生成される。
【００２８】
バイリンガルフレーズ対は、ソース文字のシーケンスとターゲット文字のシーケンスとから成るタプル(_s,_t)、(_s,_t)=(<s1,s2,…,si>,  <ti,t2,…,tj>)である。
【００２９】
図１はトークンのシーケンスｓ１からｓ６よりなるソース単語２２がフレーズ４０（ｓ１からｓ３）、４２（ｓ４、ｓ５）及び４４（ｓ６）にセグメント化され、トークンｔ１からｔ７よりなるターゲット単語２４がフレーズ５０（ｔ１からｔ４）、５２（ｔ５）及び５４（ｔ６、ｔ７）にセグメント化される例を示す。フレーズ４０と５０、４２と５２、４４と５４とが、それぞれフレーズ対をなす。コーパス全体は図１のようにフレーズ対にセグメント化される。
【００３０】
コーパスの確率は、単純に、バイリンガルフレーズ対の組とその確率とが与えられたときの、コーパスの派生形の全てについての確率である。
【００３１】
【数１】
0005550074.tif 000002
ここでg=((_s1,_t1),…,(_sk,_tk),…,(_sK,_tK))は同時セグメント化によって特徴付けられるコーパスの派生形であり、Γはコーパスの全派生形（同時セグメント化）の組である。
【００３２】
単一の派生形の確率はその構成要素であるバイリンガルフレーズ対の積で与えられる。
【００３３】
【数２】
0005550074.tif 000003
この実験のコーパスはバイリンガル単語対にセグメント化される。従ってここでは、コーパスの派生における各バイリンガルフレーズ対のソース及びターゲット文字シーケンスの両方が、単語セグメント化境界を越えないようにモデルを制約した。従って、式（２）は、コーパス中の全単語対Ｗのシーケンスの単語対ｗの派生形の積として書換えることができる。
【００３４】
【数３】
0005550074.tif 000004
ここで、gｗはバイリンガル単語対ｗの派生形である。
【００３５】
ユニグラムDirichletプロセスモデル
Dirichletプロセスは、集合Ｓ（ここでは、可能な全てのバイリンガルフレーズ対の集合）上に定義される確率論的プロセスであり、そのサンプル経路がＳ上の確率分布であるようなプロセスである。
【００３６】
このアプローチで用いたDirichletプロセスは、S．Goldwaterら（Ｓ．ゴールドウォータ、Ｔ．Ｌ．グリフィス及びＭ．ジョンソン、「教師なし単語セグメント化における文脈依存性」、ＡＣＬ-４４：第２１回コンピュータ言語学国際会議及び第４４回コンピュータ言語学会年次総会予稿集、モリスタウン、ＮＪ，ＵＳＡ：コンピュータ言語学会、２００６、６７３−６８０ページによって提案される言語モデリングで用いられるキャッシュモデルに類似の簡単なモデルである。このモデルには２つの基礎的要素がある。以前に少なくとも一度は生成された結果を生成するためのモデルと、まだ生成されていない結果の確率を割当てる第２のモデルとである。
【００３７】
直感的に考えて、新規なバイリンガルフレーズ対を生成することは、モデルのキャッシュ要素から生成することによって与えられる確率に対し相対的に費用がかかるはずである。これは、バイリンガルフレーズ対の再利用を奨励することが好ましいからである。新規な対を生成するモデルが有用なのは、まだ見たことのない無限の数の対について確率を割当てる能力をモデルに与えるからである。モデルの別の特徴は、プロセスの初期において新たなフレーズ対を生成する優先傾向がある一方で、後になるとその傾向が弱まることである。このように、キャッシュはより信頼性が高まり完全なものとなっていくので、モデルは新たなフレーズ対を生成するよりもむしろ優先的にキャッシュを用いる。これらのバイリンガルフレーズ対（見たことのない無限の数の対を含む）に対する確率分布は、コーパスの隠れた同時セグメント化のベイズ推論によってラベルなしのデータから直接学習することができる。
【００３８】
バイリンガルフレーズ対からなるコーパスの生成のための、基礎となる確率論的プロセスは一般に以下のように書かれる。
【００３９】
【数４】
0005550074.tif 000005
ここでＧは、Ｐ０を基本尺度とし、αを集中パラメータとするDirichletプロセスに従った、全バイリンガルフレーズ対に対する離散確率分布である。集中パラメータα＞０がＧの分散を制御する。直感的に、αが大きければＧ０がＧにより類似する。
【００４０】
中華料理店プロセス
可能なバイリンガルフレーズ対の数が無限であるため、残念ながらＧを直接推定することは不可能である。そこで、代わりにその可能な値を積分する。このために、バイリンガルフレーズ対生成プロセスを、D．J．Aldousの「交換可能性及び関連の話題」（D.  J.  Aldous,  in  “Exchangeability  and  related  topics,”  in  Ecole  d’ete  de  probabilities  de  Saint-Flour,  XIII.  1983,  ser.  Lecture  Notes  in  Math.  Berlin:  Springer,  1985,  vol.  1117,  pp.  1-198）に記載の中華料理店プロセス（Chinese  Restaurant  Process:CRP）の１事例として扱う。この表現によれば、全てのバイリンガルフレーズ対は、中華料理店の潜在的に無限の数のテーブルに供される一皿の料理に相当する。各テーブルについている客の数が、そのバイリンガルフレーズ対の累積的な数に相当する。レストランの新たな客は、すでに人が座っているテーブルに、そのテーブルに座っている客の数に比例した確率で席をとることができるが、そこでそのテーブルにある料理を食べなければならない。又は、この客は、定数に比例した確率で空いたテーブルに席をとることもでき、この場合にはシェフが選んだ一皿の料理（バイリンガルフレーズ対）を食べなければならない（この譬えでは、シェフの選択は基本分布Ｐ０に従う）。
【００４１】
基本尺度
新規な単語の生成を制御する基本尺度として、以下の共分布に従って新規な単語に確率を割当てる共スペリングモデルを用いた。
【００４２】
【数５】
0005550074.tif 000006
ここで|_s|及び|_t|はバイリンガルフレーズ対のソース及びターゲット側の文字の長さであり、ｖｓ及びｖｔはそれぞれソース及びターゲット言語の語彙（アルファベット）サイズである。
【００４３】
このモデルによれば、ソースシーケンスとターゲットシーケンスとは独立して生成される。いずれの場合もシーケンス長さがポアソン分布から選ばれ、その後シーケンスそのものが与えられた長さで生成される。このモデルはソース及びターゲットシーケンスにおいていかなる長さの任意のバイリンガルフレーズ対にも確率を割当てできることに注意すべきだが、いずれの場合も短いシーケンスを好む。なぜなら、語彙サイズｖｓ及びｖｔがそれぞれ-|_s|乗及び-|_t|乗されているからである。
【００４４】
非特許文献１に従って、パラメータλｓ、λｔ及びαにそれぞれ２、２及び０．３を割当てる。理想的にはこれらのパラメータはデータから学習すべきであるが、この実験ではこの設定でトレーニングコーパスに有用な同時セグメント化を与えるに十分であった。さらに、このシステムは一組の試験ではこれらパラメータの変化に特に敏感ではなく、ある範囲のパラメータ設定で、極めて類似した最終的な繰返しサンプルに収束した。
【００４５】
生成モデル
生成モデルは以下の式（６）で与えられる。この式では、それまでの履歴における全ての他のフレーズ対を（_s-k,_t-k）として、コーパスの派生形のｋ番目のバイリンガルフレーズ対（_sk,_tk）に確率を割当てる。ここで−ｋは「ｋまで、ただしｋを含まない」を意味する。
【００４６】
【数６】
0005550074.tif 000007
式中、Ｎはこれまでに生成されたバイリンガルフレーズ対の総数（これまでの客の数）であり、N((_sk,_tk))は履歴においてフレーズ対(_sk,_tk)が起こった数（そのテーブルに席をとった人の数）である。Ｐ０とαとは、上と同様、基本尺度と集中パラメータである。
【００４７】
Gibbsサンプリング
Gibbsサンプル抽出器をブロック化したものを用いてトレーニングを行なった。Goldwaterらは、サンプル抽出器における混合の問題がアニーリングによって克服されたことを報告している。非特許文献２では、この問題はブロック化されたサンプル抽出器とダイナミックプログラミングのアプローチとを用いて克服されている。発明者らのアルゴリズムは、非特許文献２に類似のものであって、このサンプル抽出器が良好に混合を行ないアニーリングなしで迅速に収束したことを確認した（図５を参照）。繰返し数は試験でのアルゴリズムの収束挙動を観察した後、手動で設定した。全実験で、コーパス全体に対する繰返し数を３０とした。
【００４８】
サンプリングプログラムの制御フロー構造は図２に示すとおりであり、繰返し要素は以下のように進む。図２を参照して、プログラムに入力されるのはトレーニングセットのコーパスである（ステップ７０）。ソース文とターゲット文とは単語等のブロックにセグメント化され、単語対にアライメントされる。最初に、バイリンガル単語対のトレーニングセットがステップ７２でランダムなフレーズ対にセグメント化される。フレーズ対はここでは単語境界をまたがってはならないことに注目されたい。ステップ７４で各フレーズ対について、コーパス中の発生数が計数される。計数結果は、図示しないメモリに記憶される。
【００４９】
ステップ７６で、コーパス中の単語対がランダムに並べ替えられ、次のステップ７８がＩ＝１からＩＭＡＸまで繰返される。この実験では、上述のとおり、ＩＭＡＸは３０に設定された。
【００５０】
ステップ７８は、並べ替えられた単語対からバイリンガル単語対ｗを一つずつサンプリングし、サンプリングされた単語対ｗに以下のステップ９２を繰返すステップ９０を含む。サンプリングされた単語対ｗはフレーズ対にセグメント化されることに注目されたい。単語対はステップ７６でランダムに並べ替えられるので、この動作の結果、非復元的に１つの単語対がサンプリングされることになる。
【００５１】
ステップ９２は、サンプリングされた単語対ｗ内のフレーズ対の計数の各々から１を減じるステップ１００と、バイリンガル単語対ｗを含まないモデルに関する確率、その先行するセグメント化情報及びそれぞれの計数結果を獲得することにより、選択されたバイリンガル単語対ｗの可能な全ての同時セグメント化に対する確率分布γを計算するステップ１０２とを含む。音訳の場合にはシーケンス長が短いため、この分布を計算するのに力ずく法を用いることもできる。しかし、効率のため、非特許文献２の前向きフィルタリング／後ろ向きサンプリング（forward  filtering/backward  sampling:  FFBS）ダイナミックプログラミングアルゴリズムを拡張して、バイリンガルセグメント化に対処した。このアルゴリズムをグラフを用いて実現したが、これについては図３を参照して後述する。
【００５２】
図２を参照して、ステップ９２はさらに、ステップ１０２で計算した確率分布を用いてｗの同時セグメント化γｉをサンプリングするステップ１０６と、ステップ１０６でサンプリングされた同時セグメント化におけるフレーズ対の各々に１を加算するステップ１０８とを含む。
【００５３】
図３を参照して、図２のステップ１０２のプロセスの進行を決めるために、セグメント化グラフを用いる。この有向グラフは、バイリンガル単語対の同時セグメント化において可能な方法全てを簡潔に示したものである。他の箇所に記載した「ａｂｂａ／アッバ」をセグメント化する場合、グラフは例えば、６個のノード、１２０、１２２、１２４、１２６、１２８、１３０、１３２及び１３４と、１６個の弧１５０、１５２、１５４、１５６、１５８、１６０、１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６、１７８及び１８０とを含む。各ノードはソース及びターゲットトークンの同じシーケンスを共有する全シーケンスの部分的同時セグメント化仮説の組を表し、各弧は弧の尾部から頭部への遷移に用いられるバイリンガルフレーズ対を表す。
【００５４】
図３において、弧にはそのフレーズ対の対数確率（式６においてモデルによって与えられる）でラベルが付されており、従って完全なセグメント化仮説の対数確率はソースノード「＜ｓ＞」からシンクノード「ａｂｂａアッバ」までのそれぞれの経路上の弧ラベルの和で与えられる。最も有望な同時セグメント化は図３において太い弧で示され、ａ／アｂ／ッｂａ／バというセグメント化に対応する。これは合理的である、なぜなら、「ａ」と「ｂａ」はともにそれらの日本語の音声による等価物と関連しており、日本語の「ッ」はすぐ右の子音を繰返すべきことを示すからである。グラフ中、最も有望でないセグメント化はａｂｂ／アａ／ッバである。グラフ中の対数確率はトレーニングの３回目の繰返しから採られた実の値であり、ここでは最もありそうなセグメント化がすでにそれまでで最もありそうなものになっている。
【００５５】
グラフ中のノードは複数の入次数及び出次数を有することができる。バイリンガルシーケンス対のセグメント化されていない部分が両者について同じ場合には、２つのノードを組合せることができ、これによって簡潔で効率的な表現が与えられる。
【００５６】
ＦＦＢＳアルゴリズムはセグメント化グラフに直接作用し、２つのステップを含む。前向きフィルタリングステップは、グラフの各ノードについて、ノードの左側へのサブグラフ（ノード自身を含む）の確率を計算する。この確率αは、ノード自身に記憶される（これらのαが図３に示されている）。このプロセスは、シンクノードから開始して、右から左へ、グラフの深さ優先帰りがけ順巡回（ｄｅｐｔｈ−ｆｉｒｓｔ  ｐｏｓｔ−ｏｒｄｅｒ  ｔｒａｖｅｒｓａｌ）で再帰的に進行する。その確率がすでに計算されたノードには済のマークが付けられ、そのノードについてαの計算が１回だけ行なわれるようにする。
【００５７】
後ろ向きサンプリングステップは、全ての可能なセグメント化に対する確率分布に従ってバイリンガル対の派生形をサンプリングする。これは前向きフィルタリングプロセスでグラフに記憶された値を用いて容易になされる。後ろ向きサンプリングプロセスもまた、シンクノードから再帰的に進行する。入来する弧の各々について、その弧をサンプルに含める確率が弧の確率と弧の終端のα値との積で与えられる。この値が入来する弧の各々について計算され、組から１個の弧が、弧に対する確率分布に従ってサンプリングされる。このサンプリング手順は、グラフのソースノードに達するまで、サンプリングされた弧の終端で再帰的に呼び出される。巡回された弧のシーケンスは、トレーニングプロセスの今回の繰返しについて、バイリンガル対のサンプリングされた派生形を規定する。
【００５８】
フレーズ対の抽出
典型的なフレーズベースのＳＭＴシステムのフレーズテーブル生成プロセスの間には、GIZA++が２回実行され、ソースからターゲットへと、ターゲットからソースへとの単語レベルのアライメントを生成する。このステップに続いて、grow-diag-final-and手順を用いて２回のGIZA++実行により得られる単語アライメントと一貫する全てのフレーズを抽出する。本発明のGibbsサンプリング手順の最後の繰返しで達成されたアライメントからフレーズテーブルを構築する際には、ずっと簡単なヒューリスティックであって最初の同時セグメント化と一貫したより大きな組のフレーズを派生させるという同じ思想のものを用いる。実験では、これがシステムの性能をかなり向上させる必要なステップであることが分かった。
【００５９】
同時セグメント化を行なったコーパスからのフレーズ抽出に用いたアルゴリズムは、以下のとおりである。単一のバイリンガル単語対の中で、隣接する全てのバイリンガルフレーズ対を可能な全てのやり方でまとめるが、ここでまとめられたソース及びターゲットフレーズのサイズはＳＭＴシステムをトレーニングするのに用いられた最大のフレーズ長さパラメータ（この実験では７に設定）と一致するように制限される。これは厳密に必要なわけではないが、発明者らはこのベイズセグメント化で生成されるフレーズテーブルをベースラインシステムで生成されるものと同程度のものに保つため、このステップを行なった。
【００６０】
［実験］
ベースラインシステム
実験のために、P．Koehnらの導入したフレーズベースの機械翻訳技術（P．Koehn，H．Hoang，A．Birch，C．Callison-Burch，M．Federico，N．Bertoldi，B．Cowa，W．Shen，C．Moran，R．Zens，C．Dyer，O．Bojar，A．Constantin，and  E．Herbst,、「Ｍｏｓｅｓ：統計的機械翻訳のためのオープンソースツールキット」ＡＣＬ２００７、デモ及びポスターセッションのための予稿集、プラハ、チェコ共和国、２００７年６月、１７７−１８０ページ）を用い、発明のモデルを、F．J．Och及びH．Neyの提案する対数線形フレームワーク（「統計的機械翻訳のための識別的トレーニング及び最大エントロピモデル」、コンピュータ言語学会第４０回年次総会予稿集（ＡＣＬ２００２）、２００２年、２９５−３０２ページ）と統合した。GIZA++及びMOSESツールを用いて単語アライメントを行なった。使用したデコーダは出願人において準備したフレーズベースの機械翻訳デコーダであって、公に入手可能なMOSES  SMTデコーダと同じ原理に従って動作するものである。
【００６１】
実験では、Witten-Bell平滑化で構築した５−グラム言語モデルを用いた。システムは、F．J．Ochによって「統計的機械翻訳のための最小誤差率トレーニング」、ＡＣＬ２００３予稿集、で提案された最小誤差率トレーニング（minimum  error  rate  training:  MERT）を用いて、標準的な様態でトレーニングされ、とりのけておいた開発データのＢＬＥＵスコアに対して対数線形モデル重みを最適化した。
【００６２】
Rama及びGaliは「機械翻訳をフレーズベースの統計的機械翻訳問題としてモデル化する」、ＡＣＬ／ＩＪＣＮＬＰ固有表現ワークショップ共有タスク予稿集、２００９において、音訳のためのフレーズ対抽出技術のいくつかを評価し、grow-diag-final-andヒューリスティックが最も有効であると認めている。このため、ここでの実験のベースラインシステムに、この方法を採択した。
【００６３】
デコードの制約
ここで報告される実験は、ビーム幅１００、スタック深さ制限なしで、厳密に一方向のデコードプロセスを用いて行なわれた。
【００６４】
実験データ
トレーニングデータはＮＥＷＳ２０１０ワークショップ音訳共通課題で用いられた、２７９９３個のバイリンガル単一単語対からなる。開発データは同じサンプルから引出された３６０６個のバイリンガル単語対からなる。評価データは他の２つのデータの組には含まれない他の１９３５個のバイリンガル単語対からなる。３つのコーパスについてのコーパス統計をテーブル１に示す。
【００６５】
このデータを用いてフレーズベースのＳＭＴシステムをトレーニングし、英語から日本語への翻訳を行なった。本発明のDirichletプロセスモデルを同じパラレルデータセットで１回トレーニングし、最後の繰返し（繰返し３０）でのコーパスの同時セグメント化から音訳フレーズテーブルを抽出した。
【００６６】
【表１】
0005550074.tif 000008
トレーニング手順
Gibbsサンプリングの為に、コーパスのランダム同時セグメント化からサンプリングを開始することを選択した。すなわち、コーパス中のバイリンガル単語対の各々について、その対に可能な全ての同時セグメント化に対する一様分布から単一の同時セグメント化をサンプリングした。より知的な開始点、例えばGIZA++の前処理パスから導出されるものなどからサンプリングを開始するほうがより有利であり、かつ確実により効率的であると思われる。しかし、このトレーニングでトレーニングコーパスの良好なセグメント化（視覚的検査による）に到達することができ、その有用性は次のセクションの実験結果で裏付けられた。
【００６７】
実験手順
ここで提示する結果は、ＮＥＷＳ２０１０音訳生成共有課題で用いられ、ワークショップ白書で示された公式な評価基準で与えられるものである（M．Z．Haizhou  Li，A．Kumaran及びV．Pervouchine、「ｎｅｗｓ２０１０音訳生成に関する共有課題白書」、ＡＣＬ固有表現ワークショップ共有タスク予稿集２０１０）。結果では、ＡＣＣは最上位１の正確さスコアを指し、これはシステムからの最上位の仮定が基準の１つに正確に一致した回数のパーセンテージを測定するものである。Ｆ−スコアはベスト仮説のその最も近い基準からの距離を測定するものである。
【００６８】
［結果］
トレーニング
トレーニング手順中のアルゴリズムの収束を図５に示し、ここではトレーニングコーパスを通る各パスの終わりでのサンプリングされた派生形の対数確率を、繰返し回数に対してプロットしている。このグラフから、このシステムが初期の貧弱なセグメント化から迅速に向上し、その後連続して徐々に向上していることが分かる。最初のランダムな同時セグメント化の対数確率は−１．５ｅ０６だったので、これは図では省略した。
【００６９】
様々な繰返しでのセグメント化を比較すると、ある知見が得られる。繰返し２９では、コーパス中の全単語の９０％が繰返し３０と同一の様態でバイリンガルにセグメント化されている。これはサンプリングプロセスであるから、１０％の相違はおそらくサンプリング処理中の選択の相違で説明できるであろう。繰返し３で、すでに８７．５％の単語対が繰返し３０と同一の様態でセグメント化されている。
【００７０】
評価
英語から日本語への音訳課題の例を図４に示し、その結果をテーブル２にまとめた。このテーブルから、トレーニング手順の最終の繰返しのサンプルのみからのフレーズを用いると、ベースラインシステムよりも結果が悪化することが明らかである。このようにして導出されたフレーズテーブルは、GIZA++アライメントから抽出されたフレーズテーブルの１４０，０００に対しわずかに３３７２個のフレーズ対を含むのみであった。さらに、これらのフレーズ対は、ベースラインシステムのフレーズテーブルからのものと比較して非常に短い。すなわち、ソース及びターゲットの両者で平均約３文字であり、これに比べベースラインシステムでは約５文字である。
【００７１】
【表２】
0005550074.tif 000009
フレーズの同じ組のまとまりから構築されたフレーズテーブルを用いると、約１００，０００のかなり大きなフレーズテーブルを結果として得ることができ、フレーズのサイズは約５文字であって、ベースラインのそれと匹敵するものであった。音訳課題では、このフレーズテーブルは、約３０％小さいサイズのフレーズテーブルから、ベースラインに比べ約７％の改善が得られた。さらに、フレーズは３３７２個の構成要素フレーズ対の連結であるため、このモデルは必要であれば非常にコンパクトに記憶することができる。まとめられたモデルをベースラインモデルとともに単に補間するだけで、さらなる利得が得られる。この利得は平滑化の効果によるものと思われる。
【００７２】
この実験は、ベースラインモデルに有利になるように設計されている。なぜならシステムはＭＥＲＴ手順を用いてそれ自身のフレーズテーブルでチューニングされるからである。本発明の提案のシステムをそれ自身のフレーズテーブルでチューニングすればより高いスコアが得られたかもしれないが、それは選択しなかった。なぜなら、こうすることによって、２つのＭＥＲＴ検索プロセスの相違からの付加的な分散が結果に導入されると思われたからである。第２の実験では、トレーニングプロセスの多数の繰返しに対し、フレーズ対の計数を収集した。すなわち、繰返し５（バーンイン）から最終繰返しまでである。この結果、フレーズテーブルは３７％大型化したが、驚くべきことに、性能上なんら目立った改善は実現されなかった。
【００７３】
興味深いことに、システムの性能はフレーズをより大きなユニットへと単純にグループ化するだけで劇的に向上した。これはフレーズベースの翻訳アプローチの利点のひとつを強調するものである。まとめられたモデルは、それが構築される方法のために、より簡単なモデルで生成できないものを生成することはできない。しかし、ターゲットシーケンスを構築するためにより大型のフレーズ対を用いると、フレーズ中の文字が、トレーニングコーパスの同じ文脈で全て併せて起こった、フレーズ中の他の文字の文脈を暗黙の内に保持するようになる。まとめられていないフレーズ対を備えたモデルでは、この役割は主に言語モデルによって行なわれる。５−グラムの言語モデルを用いたという事実にも関わらず、システムは基本翻訳単位としてより長いフレーズ対を含むモデルからの利益を明らかに享受している。
【００７４】
デコードの一貫性
システム性能の改善理由を調査するために実験を行なった。ここでの仮説は、ベイズシステムがより一貫性のあるデコードプロセスにつながるフレーズテーブルを生成した、というものであった。これは、Dirichletプロセスモデルが、そのモデルにより発見されたバイリンガルフレーズ対の再使用を強く奨励するだろうという事実への信念に基づく。これは、よりコンパクトなフレーズテーブルを結果としてもたらすはずであり、コーパス中の類似の単語がより均質にデコードされるという結果を生ずるはずである。この仮説をテストするために、機械翻訳デコーダを修正して、評価データをデコードするのに用いられるバイリンガルフレーズ対の種類の数を計数し、性能上最大の利得を示した英語−日本語翻訳実験を再実行した。この発明のベイズモデル（フレーズ対をまとめたもの)から生成したフレーズテーブルを用いたデコードプロセスは合計で３４９６個の独自のフレーズ対を用い、一方で、GIZA++及びgrow-diag-final-andを用いて抽出したフレーズテーブルを用いたデコードではデコードプロセスの間に合計で３９７０個のフレーズ対が必要とされ、われわれの仮説が支持された。ベイズモデルのフレーズテーブルからの３４９６個のフレーズ対をさらに分析して、トレーニングプロセスの終わりで採られたサンプルのセグメント化中に存在していた１２８９個の構成要素バイリンガル対にすることができた。
【００７５】
［コンピュータによる実現］
このように構成されたプログラムは、コンピュータで実行されると、図２から図５に示されるシステムを実現するものであることが当業者には理解されるであろう。
【００７６】
図６を参照して、この実施の形態のハードウェア資源を与えるコンピュータシステム３３０は、コンピュータ３４０と、全てコンピュータ３４０に接続された、モニタ３４２、キーボード３４６及びマウス３４８を含む。さらに、コンピュータ３４０はＤＶＤ３６２からのデータの読出し又はデータの書込みのためのＤＶＤ（ディジタル多用途ディスク）ドライブ３５０と、着脱可能なメモリ３６４からのデータの読出し又はデータの書込みのための半導体メモリポート３５２と、を含む。
【００７７】
図７を参照して、コンピュータ３４０はさらに、ＤＶＤドライブ３５０及び半導体メモリポート３５２に接続されたバス３６６と、上述の装置を実現するコンピュータプログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３５６と、コンピュータ３４０のブートアッププログラムを記憶するＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）３５８と、ＣＰＵ３５６によって用いられる作業領域及びＣＰＵ３５６によって実行されるプログラムの記憶領域を提供するＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３６０と、バイリンガルコーパス及び他のデータを記憶するハードディスクドライブ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ：ＨＤＤ）３５４とを含む。
【００７８】
コンピュータ３４０はさらに、バス３６６に接続され、コンピュータ３４０をネットワーク、典型的にはＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）（図示せず）に接続するネットワークインターフェース（Ｉ／Ｆ）３４４を含む。
【００７９】
上述の実施の形態のシステムを実現するソフトウェアはＤＶＤ３６２又は着脱可能メモリ３６４等の記録媒体に記録されたオブジェクトコードの形で配布されてもよく、ＤＶＤドライブ３５０又は半導体メモリポート３５２等の読出装置によってコンピュータ３４０に提供され、ＨＤＤ３５４に記憶されてもよい。ＣＰＵ３５６がプログラムを実行する際には、プログラムはＨＤＤ３５４から読出され、ＲＡＭ３６０に記憶される。ＣＰＵ３５６内の図示しないプログラムカウンタから指定されるアドレスからＣＰＵ３５６により命令がフェッチされＣＰＵ３５６内で実行される。ＣＰＵ３５６はＣＰＵ３５６、ＲＡＭ３６０又はＨＤＤ３５４内のレジスタの命令のオペランドによって指定されるアドレスから処理すべきデータを読出し、処理の結果をまたＣＰＵ３５６、ＲＡＭ３６０又はＨＤＤ３５４内の命令のオペランドによって指定されるレジスタに記憶する。
【００８０】
コンピュータシステム３３０の一般的な動作は公知であるので、その詳細はここでは説明しない。
【００８１】
ソフトウェア配布の方法については、必ずしも記憶媒体に固定されていなくてもよい。例えば、ソフトウェアは別のシステムからコンピュータ３４０にネットワーク及びネットワークＩ／Ｆ３４４を介して送信されてもよい。ソフトウェアの一部をＨＤＤ３５４に記憶し、ソフトウェアの残りの部分をネットワークからＨＤＤ３５４に取込んで、実行の際に統合してもよい。
【００８２】
典型的には、現代のコンピュータはコンピュータのオペレーティングシステム（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ：ＯＳ）によって提供される機能を利用し、これらの機能を所望の目的にしたがって制御されたやり方で実行する。したがって、これら機能を含まず、ＯＳによって、又は第三者によって提供され、一般的機能の実行の順序の組合せのみを指定するのみのプログラムもまた、そのプログラムが全体として所望の目的を達成する制御構造を有するのであれば、この発明の範囲に含まれる。
【００８３】
［結論］
この出願では、新規なベイズ推論によるバイリンガル同時セグメント化の手法を提示し、これをフレーズベースの統計的機械翻訳による音訳の生成のためのフレーズテーブル生成課題に適用した。フレーズアライメントの伝統的なモデルはＥＭアルゴリズムと組合せた最大尤度トレーニングに依るが、トレーニングデータの過学習という重大な問題がある。これらの問題のために、アライメントは典型的には１対多の形式でソースからターゲットへ、及びターゲットからソースへと行なわれ、フレーズ抽出プロセスはアライメントテーブルからヒューリスティックに行なわれる。本発明のアプローチは、直接ベイズ技術を用いてトレーニングデータを多対多の形式でアライメントする能力を与え、これによって、最大尤度トレーニングに固有の問題に簡潔かつエレガントな解決策を提供する。加えて、本発明のアプローチはソース及びターゲットについて対称であり、さらにコーパスの単語順についても対称である。
【００８４】
教師なしのベイズ同時セグメント化で達成可能なバイリンガルフレーズアライメントの品質を調査し、Gibbsトレーニング手順から生じるサンプルからフレーズテーブルを構築することによって、標準GIZA++／grow-diag-final-andフレーズ抽出手順と直接比較できるような実験を設計した。実験では、ベイズアプローチがより小型のフレーズテーブルを生成可能であり、さらに、このフレーズテーブルが、発明者らの準備したベースラインシステムに匹敵する、またはより高い音訳性能を提供することが示された。
【００８５】
さらに、この技術は他の利点も提供する。一つの例は、これがトレーニングの終わりにトレーニングコーパスの完全な同時セグメント化を提供することであり、これをバイリンガル対のｎ−グラムモデルのトレーニングに直接使用できる。このコンテキスト情報はH．Li，M．Zhang及びJ．Suらが提案するような同時ｎ−グラムベースの音訳モデルの鍵となる特徴であり、現在はフレーズベースのＳＭＴ−ベース音訳システムでは欠落しているものである。この発明のアプローチの別の利点は、Dirichletプロセスがいかなるバイリンガル単語対にも確率を割当て可能であることから由来する。この種のモデル化は翻訳マイニング及びコーパスフィルタリングにおいてかなりの潜在的有用性を有すると信じる。というのは、これが、いかなる潜在的な音訳候補もスコアリングする原則にのっとったやり方を提供するからである。
【００８６】
今回開示された実施の形態は単に例示であって、本発明が上記した実施の形態のみに制限されるわけではない。本発明の範囲は、発明の詳細な説明の記載を参酌した上で、特許請求の範囲の各請求項によって示され、そこに記載された文言と均等の意味及び範囲内での全ての変更を含む。
【符号の説明】
【００８７】
２２  ソース単語
２４  ターゲット単語
１２０、１２２、１２４、１２６、１２８、１３０、１３２、１３４  ノード
１５０、１５２、１５４、１５６、１５８、１６０、１６２、１６４、１６６、１６８、１７０、１７２、１７４、１７６、１７８、１８０  弧
３３０  コンピュータシステム
３４０  コンピュータ
３５０  ＤＶＤドライブ
３５２  メモリＩ／Ｆ
３５４  ＨＤＤ
３５６  ＣＰＵ
３６０  ＲＡＭ
【図１】
0005550074.tif 000010
【図２】
0005550074.tif 000011
【図３】
0005550074.tif 000012
【図４】
0005550074.tif 000013
【図５】
0005550074.tif 000014
【図６】
0005550074.tif 000015
【図７】
0005550074.tif 000016