(57)【要約】【課題】  大規模コーパスに基づく換言を可能にする装置を提供する。【解決手段】  換言装置１４はリンクされたサブツリー対（フラグメント）の組を記憶するための第一の記憶部２４を含む。サブツリー対の各々は、ソースサブツリーとターゲットサブツリーとを含む。装置１４はさらに、入力文３０をパーズするためのパーザ３２と、パーザ３２により出力されたサブツリーに合成演算子を適用して文の集合を導出するための導出ユニット３４とを含む。合成演算子は記憶部２４に記憶されたリンクされたサブツリー対の集合によって規定される。装置１４はさらに、導出された文のうち一つを入力文３０の換言４２として選択するセレクタ４０を含む。【選択図】        図３
2005071291.tif 000002
【特許請求の範囲】
【請求項１】
リンクされたサブツリー対の集合を記憶するための第一の記憶手段を含み、前記サブツリー対の各々はソースサブツリーとターゲットサブツリーとを含み、
入力文をパーズして入力文のパーズツリーを出力するためのパーズ手段と、
前記パーズ手段によって出力された入力文のパーズツリーのサブツリーに合成演算子を適用して文の集合を導出するための導出手段とをさらに含み、前記合成演算子は第一の記憶手段に記憶された、リンクされたサブツリー対の集合に対し定義され、
前記導出手段によって導出された文の集合中の文のうち、予め定められた条件を満たすものを入力文の換言として選択するための選択手段をさらに含む、換言装置。
【請求項２】
前記リンクされたサブツリー対の尤度を記憶するための第二の記憶手段と、
前記導出手段によって導出された文の各々の尤度を、文を導出するのに用いられた前記サブツリー対の各々の尤度に基づいて計算するための計算手段と、
同じ表現を生成する、導出された文の尤度の総和を求めるための総和手段とをさらに含み、
前記選択手段は、前記導出手段によって導出された文の集合中の文から、総和手段によって求められた尤度の総和が最も高いものを前記入力文の換言として選択するための手段を含む、請求項１に記載の換言装置。
【請求項３】
前記導出手段が、
リンクされたサブツリーの対を検索するための、ツリーノード照合アルゴリズムを含む手段と、
入力文のパーズツリーと、前記入力文のパーズツリーのそれぞれのサブツリーと一致するソースサブツリーにそれぞれ対応するターゲットサブツリーとに、前記合成演算子を適用するための手段とを含む、請求項１に記載の換言装置。
【請求項４】
サブツリー対の尤度は、前記リンクされたサブツリー対の集合に現れるサブツリー対のカウントと、前記リンクされたサブツリーの集合内の、サブツリー対と同じルートノードラベルを備えたすべてのサブツリーのカウントの総和との関数である、請求項２または請求項３に記載の換言装置。
【請求項５】
前記サブツリー対の尤度は、前記リンクされたサブツリーの集合にある当該サブツリー対のカウントを、前記リンクされたサブツリーの集合内の、前記サブツリー対と同じルートノードラベルを備えた全てのサブツリーのカウントの総和で除したものである、請求項４に記載の換言装置。
【請求項６】
コンピュータ上で実行されると、コンピュータを請求項１から請求項５のいずれかに記載の換言装置として動作させる、コンピュータプログラム。
【請求項７】
文の対を準備する方法であって、
予め定められた言語の文のコーパスを準備するステップと、
コーパス内の文を、コーパス内の文間の編集距離に応じてクラスタリングするステップと、
所望の粒度に応じて文のクラスタを抽出するステップと、
抽出したクラスタ内で文を対にするステップとを含む、文の対を準備する方法。
【請求項８】
前記クラスタリングするステップは、
前記コーパス内の各文をそれ自身のクラスタに割当てるステップと、
可能なクラスタ対の各々について、当該クラスタ対の間の距離を計算するステップと、
距離が最も近い２個のクラスタをマージするステップと、
クラスタが１個だけになるまで、前記計算するステップ及び前記マージするステップを繰返すステップとを含む、請求項７に記載の方法。
【請求項９】
リンクされたサブツリーを準備する方法であって、
文の対を準備するステップと、
文の対の各々の文をパーズするステップと、
文の対の各々のソース文とターゲット文とにおけるノード間の双射マッピングを定義するステップと、
１）リンクされたサブツリーのリンクされたノードの各々について、両方のノードが子を持たないか、または両方のノードが対応する元のツリーからの全ての子を有し、
２）リンクされたサブツリーの両方のサブツリーにおいて、リンクされていないノードはいずれも、対応する元のツリーからの全ての子を持ち、かつ、
３）リンクされたサブツリーの両方のサブツリーが２以上のノードを含む、
という条件を満たす、前記双射マッピングにより定義された連結サブグラフの全ての対を収集することにより、文の対の各々のソース文とターゲット文とのツリーから、リンクされたサブツリーの対を抽出するステップとを含む、リンクされたサブツリーを準備する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は換言システムに関し、特に、文を自動的に換言する換言システムに関する。
【背景技術】
【０００２】
ＮＬＰ（自然言語処理）の応用には、換言が得られれば非常に有用な情報となるような問題が多く存在する。詳細なパージングまたは機械翻訳のような作業は、文によってはしばしば失敗したり、困難であったりするが、これは、それら文の長さと、文そのものの性質との組合せによる。換言が利用できれば、このようなシステムにもう一度チャンスが与えられるであろうし、または、元のソース文のみを用いては考慮されなかったような可能性を生出すチャンスが与えられるかもしれない。
【０００３】
テキストが換言可能であれば、例えばテキストの要約、正規化、パージング、機械翻訳等の分野で多くの実際的な応用が考えられる。
【０００４】
以下に挙げる特許文献１が開示する換言装置は、最初に文を形態素に分解し、分解された文の中の異なる部分と同じ部分とを検出することにより、換言表を生成する。異なる部分のうち予め規定された条件を満たすものが換言として特定され、抽出され、換言表に記憶される。
【０００５】
異なる部分は以下の場合に換言であるとされる。すなわち、
１）その部分がかなり稀な表現の対に挟まれており、かつ
２）その部分がコーパス中の異なる場所にしばしば現れる場合である。
【０００６】
【特許文献１】特開2003-131679
【発明の開示】
【発明が解決しようとする課題】
【０００７】
この発明の目的の一つは、大規模コーパスに基づく換言を可能にする方法と装置とを提供することである。
【０００８】
この発明の別の目的は、大規模コーパスに基づき、自然な換言を生成することができる方法と装置とを提供することである。
【課題を解決するための手段】
【０００９】
この発明に係る換言装置は、リンクされたサブツリー対の集合を記憶するための第一の記憶手段を含む。サブツリー対の各々はソースサブツリーとターゲットサブツリーとを含む。換言装置は、入力文をパーズして入力文のパーズツリーを出力するためのパーズ手段と、パーズ手段によって出力された入力文のパーズツリーのサブツリーに合成演算子を適用して文の集合を導出するための導出手段とをさらに含む。合成演算子は第一の記憶手段に記憶されたリンクされた、リンクされたサブツリー対の集合に対し定義される。換言装置は、導出手段によって導出された文の集合内の文のうち、予め定められた条件を満たすものを、入力文の換言として選択するための選択手段をさらに含む。
【００１０】
この換言装置はさらに、リンクされたサブツリー対の尤度を記憶するための第二の記憶手段と、導出手段によって導出された文の各々の尤度を、文を導出するのに用いられたサブツリー対の各々の尤度に基づいて計算するための計算手段と、同じ表現を生成する、導出された文の尤度の総和を求めるための総和手段とを含んでもよく、選択手段は、導出手段によって導出された文の集合中の文から、総和手段によって求められた尤度の総和が最も高いものを、入力文の換言として選択するための手段を含む。
【００１１】
好ましくは、導出手段が、リンクされたサブツリーの対を検索するための、ツリーノード照合アルゴリズムを含む手段と、入力文のパーズツリーと、入力文のパーズツリーのそれぞれのサブツリーと一致するソースサブツリーにそれぞれ対応するターゲットサブツリーとに、合成演算子を適用するための手段とを含む。
【００１２】
サブツリー対の尤度は、リンクされたサブツリー対の集合に現れるサブツリー対のカウントと、リンクされたサブツリーの集合内の、サブツリー対と同じルートノードラベルを備えたすべてのサブツリーのカウントの総和との関数であってもよい。
【００１３】
特に、サブツリー対の尤度は、リンクされたサブツリーの集合にある当該サブツリー対のカウントを、リンクされたサブツリーの集合内の、サブツリー対と同じルートノードラベルを備えた全てのサブツリーのカウントの総和で除したものであってもよい。
【００１４】
この発明の第２の局面に従ったコンピュータプログラムは、コンピュータ上で実行されると、コンピュータを上述の換言装置として動作させる。
【００１５】
この発明の第３の局面に従った文の対を準備する方法は、予め定められた言語の文のコーパスを準備するステップと、コーパス内の文を、コーパス内の文間の編集距離に応じてクラスタリングするステップと、所望の粒度に応じて文のクラスタを抽出するステップと、抽出したクラスタ内で文を対にするステップとを含む。
【００１６】
クラスタリングするステップは、コーパス内の各文をそれ自身のクラスタに割当るステップと、可能なクラスタ対の各々について、当該クラスタ対の間の距離を計算するステップと、距離が最も近い２個のクラスタをマージするステップと、クラスタが１個だけになるまで、計算するステップ及びマージするステップを繰返すステップとを含んでもよい。
【００１７】
この発明の第４の局面に従ったリンクされたサブツリーを準備する方法は、文の対を準備するステップと、文の対の各々の文をパーズするステップと、文の対の各々のソース文とターゲット文におけるノード間の双射マッピングを定義するステップと、
１）リンクされたサブツリーのリンクされたノードの各々について、両方のノードが子を持たないか、または両方のノードが対応する元のツリーからの全ての子を有し、
２）リンクされたサブツリーの両方のサブツリーにおいて、リンクされていないノードはいずれも、対応する元のツリーからの全ての子を持ち、かつ、
３）リンクされたサブツリーの両方のサブツリーが２以上のノードを含む、
という条件を満たす、双射マッピングにより定義された連結サブグラフの全ての対を収集することにより、文の対の各々のソース文とターゲット文とのツリーから、リンクされたサブツリーの対を抽出するステップとを含む。
【発明を実施するための最良の形態】
【００１８】
以下の記載中で言及する文献については、明細書の最後に掲げてある。
【００１９】
-データ指向翻訳（Ｄａｔａ  Ｏｒｉｅｎｔｅｄ  Ｔｒａｎｓｌａｔｉｏｎ：ＤＯＴ）-
この発明の一実施例の自動データ指向換言器（ｄａｔａ−ｏｒｉｅｎｔｅｄ  ｐａｒａｐｈｒａｓｅｒ：ＤＯＰＰ）は、データ指向翻訳（ＤＯＴ）（文献１）の原理に基づいている。ＤＯＴモデルはデータ指向パーズ（ｄａｔａ−ｏｒｉｅｎｔｅｄ  ｐａｒｓｉｎｇ：ＤＯＰ）（文献２）に基づいている。データ指向のパーザの元となる原理は、それまでに見たことのない文のパーズでも、ツリーバンクコーパス内の文から抽出したパーズツリーのフラグメントを組合わせることで確率論的に構築できる、というものである。
【００２０】
それらフラグメントは、実際上、パーズツリーを構築できる文法を形成する。各パーズには多くの導出があり得るので、パーズの尤度はその導出の各々の尤度の総和である。最新のＤＯＰパーザは、最先端の統計的パーザ（文献３）に匹敵する性能を有している。
【００２１】
データ指向翻訳技術の動作方法は、ＤＯＰと同様である。しかしこの場合には、２個のツリーが同時に構築される。ソース言語のツリーと、ターゲット言語でのその文に対応するツリーとである。この場合のフラグメントは、ソースフラグメントのノードとターゲットフラグメントのノードとにおいて意味的に等価なもの同士のリンクを含み、その思想は、意味を失うことなくリンクされたノード同士を相互に交換可能である、というものである。図１の上部に示された対により、リンクされたツリーの対を示す。
【００２２】
図１を参照して、リンクされたツリー１１０は、ノードが互いにリンクされているツリー１１２及び１１４を含む。例えば、ツリー１１２のノードＮＰはツリー１１４のノードＮＰにリンクされ、ツリー１１２のノードＮＮはツリー１１４のノードＮＮにリンクされ、以下同様である。
【００２３】
図１の下部の対は、リンクされたサブツリー（フラグメント）を示す。例えば、フラグメント１２０は、ノード同士がリンクされたサブツリー１２２及び１２４を含む。別のフラグメント１３０はサブツリー１３２及び１３４を含む。
【００２４】
-自動句アライメント-
文献１では、サブツリーの中で互いに等価なノードには手作業でラベルが付される。しかし、これらのリンクに手作業でラベルを付すのは非常に手間がかかる。これに対して、この実施の形態では、サブツリー中の等価なノード間のリンクには、文献４に基づく技術を用いて自動的にラベル付けがされる。リンクに自動的にラベルを付すことができるので、多大な労力をかけることなく大規模なコーパスを生成することができる。
【００２５】
ここで目標とするのは、τs＝{νs，εs}で表されるソースパーズツリーを、ターゲットツリー、τt＝{νt，εt}のノードにマッピングすることである。ここでνs＝{ν1s，ν2s，…νns}、及びνt＝{ν1t，ν2t，…νnt}はそれぞれ、ソースツリー及びターゲットツリーの頂点集合であり、εt及びεtはそれらのエッジ集合である。
【００２６】
このアルゴリズムはソースツリー及びターゲットツリーにおけるノード間の双射マッピングψ: νs→εsを定義するものであり、以下のように進む。
【００２７】
１．文をパーズする。今回の実験の目的では、広く入手可能なパーザを用いる（文献５）。
【００２８】
２．文中の語をアラインする。ここでは、広く入手可能なＥＧＹＰＴ機械翻訳ソフトウェアによる語アライメントの出力を用いることとした。リンクされた語の対の集合Ｌが生成される。
【００２９】
３．全てのリンクから、ｉ（０＜ｉ＜｜Ｌ｜）個の語のリンクを選択し、これらリンクを含む全ての統語的ノード（終端でないシンボル）を収集し、パーズされたツリーから、葉ノード中で他の全ての語のリンクを排除する。
【００３０】
４．プロセス３で見出された全てのノードの統語的カテゴリを比較する。同一のノードカテゴリが見出された場合には、そのノードの葉を等価な句とみなす。もし文または助動詞句カテゴリの候補が複数見出されたときには、最大の領域をカバーする候補が選択される。他の曖昧な事例では、最小の領域をカバーする候補が選択される。
【００３１】
５．全ての語のリンクの組合わせについて、ステップ３及び４を繰返す。
【００３２】
-リンクされたサブツリーの抽出-
ツリーがリンクされた後の次のステップは、換言を導出する文法として用いられるリンクされたサブツリーの対（すなわちフラグメント）を抽出することである。コーパス中のリンクされたツリーの各対について、以下の条件全てを満たす連結サブグラフ（リンクを保存しているもの）の対全てを収集する。すなわち、
１．フラグメント中のリンクされたノード対の各々について、両方のノードに子がないか、または対応する元のツリーからの全ての子を持ち、
２．フラグメントの両方のサブツリーにおいて、リンクされていないノードはいずれも、対応する元のツリーからの全ての子を持ち、
３．フラグメントのサブツリーの両方が２以上のノードからなる。
【００３３】
コーパスから全てのフラグメントを収集したものを、「リンクされたサブツリー対の集合」Ｂと呼ぶ。各フラグメントｆiは、コーパス中でそのフラグメントが生じた回数を表すカウントを持つ。パーズを導出する際には、導出の次のステップとして、このカウントを用いて集合からこのフラグメントを選択する尤度ｐ（ｆi）を計算する。尤度は単に、このカウント｜ｆi｜を、リンクされた全てのサブツリーの集合内で、同じルートノードラベルを持つ全てのサブツリーの数の総和で除したものである（ツリーｆiのルートノードのラベルをｒ（ｆi）で示す。）。
【００３４】
【数１】
2005071291.tif 000003
-換言の導出-
換言の導出は、リンクされたサブツリーの集合を用いて、合成演算子によって構築される。直観的には、この演算子はフラグメントを組合わせるための条件を定義するものであり、図２に示されている。
【００３５】
図２を参照して、フラグメント１４０はサブツリー１１２および１１４を含む。サブツリー１１２はノード１５２を有し、これはサブツリー１１４のノード１５４とリンクされる。フラグメント１４２はサブツリー１６２及び１６４を含む。これらのフラグメント１４０及び１４２を組合わせることにより、合成演算子によりサブツリー（文）の対１７０が生成される。
【００３６】
正式には、演算子は、２個のフラグメントｆ1=＜τs1，τt2＞及びｆ2=＜τs2，τt2＞について、ｒ（ｆ2）がτs1の最も左側の、語でない葉ノードのラベルと同じであるときのみ定義される。この合成の結果はリンクされたツリー対＜τs3，τs3＞である。ここでτs3は、τs1の最も左の語でない葉ノードνis1をｆ2のソースサブツリーτs2で置換えたものである。フラグメントの構成の性質により、この最も左の語でない葉は、フラグメントのターゲットサブツリー内のノードにリンクされる。すなわち、ψ(νis1) =νjt1。ノードνjt1はターゲットサブツリーτt2で置換えられ、τt3が得られる。この合成を、＜τs1, τt1＞○＜τs2, τt2＞＝＜τs3, τt3＞、またはより簡潔にｆ1○ｆ2＝ｆ3と表記する。導出ｆ1○ｆ2 ○…○ｆNの尤度は以下の式で与えられる。
【００３７】
【数２】
2005071291.tif 000004
図５において、ノード１５２は、サブツリー１１２の最も左側の語でない葉ノードであるが、このノード１５２は、フラグメント１４２からのサブツリー１６２で置換され、これに対応して、サブツリー１１４のノード１５４がフラグメント１４２からのサブツリー１６４で置換される。この結果得られるサブツリー対１７０は、サブツリー１７２及び１７４を含む。こうして、フラグメント１４０及び１４２から、換言句「Ｉ  ｅｎｊｏｙ  ｔｅｎｎｉｓ」が導出される。
【００３８】
１個のターゲット文ｗtは、ソース文ｗsからの多くの導出を有することがある。可能な全ての導出の総和をとることで、換言の尤度が得られる。ここでは、最善の換言として、最も高いＰ（ｗt｜ｗs）を持つものを選択する。
【００３９】
-明確化-
ソース文から生じる全ての導出に対し、最も可能性の高い換言を見出す必要がある。実際には、全てのリンクされたサブツリーの集合内のフラグメントのうちのソースフラグメントにより規定されるツリーフラグメントの文法に従ったチャートパーザを用いてソース文がパーズされるので、当然、ターゲット換言のための（必ずしも正確でない）パーズツリーを生成する。
【００４０】
同じ文について多くの導出が可能なので、最も可能性の高い導出を見出すだけでは不充分であり、ターゲット換言についての全ての導出の尤度の総和を全て調べなければならない。ここでは、換言の尤度を推定するために、モンテカルロ法による導出のサンプリングという通常の手法を採用した（文献１）。その考え方は、十分に大きいサンプルであれば基となる分布を正確に近似するだろう、というものである。
【００４１】
-実務的考察-
ＤＯＴ技術を大規模に試験する場合、作業の規模による問題が生じるであろう。全体的にも、また長い文からも、生成可能なフラグメントの数が多いので、重大な問題が引起こされる可能性がある。これを克服するために、どの一文についても、そこから得られるフラグメントの数を適当に制限することが実際的かも知れない。コーパス中での発生回数がしきい値（例えば、５）より少ないフラグメントは捨てることも有効であろう。
【００４２】
未知の語を取扱う場合に備えて、またシステムが少なくとも一つは確実に換言を出力するように、ソース文をそれ自身と対にすることで生成されたフラグメントの集合を、文を換言する前にトレーニングセットに付加してもよい。
【００４３】
-構造-
図３は上述の換言方法を実現するこの実施例の換言システムの構造を示す。図３を参照して、このシステムは、換言コーパス２０から、フラグメントの集合と、その集合内のフラグメントの各々についての尤度の集合とを生成するフラグメント生成ユニット２２を含む。
【００４４】
システムはさらに、フラグメント生成ユニット２２によって生成されたフラグメントの集合を記憶する換言記憶部２４と、フラグメントの各々についてフラグメント生成ユニットによって計算された尤度を記憶する尤度記憶部２６と、換言された文４２を生成する換言器１４とを含む。この換言文は換言記憶部２４に記憶されたフラグメントと、尤度記憶部２６に記憶されたそれらのそれぞれの尤度とを用いて得られた、入力文３０の換言である。
【００４５】
換言器１４は、入力文３０をパーズして、パーズツリーを生成するパーザ３２と、換言記憶部２４に記憶されたフラグメントとパーザ３２によって生成された入力文３０のパーズツリーとを用いて入力文３０の換言を導出し、尤度記憶部２６に記憶された尤度に基づき、導出のそれぞれの尤度を計算するための導出ユニット３４と、導出ユニット３４から出力された導出と、導出のそれぞれの尤度とを記憶するための導出記憶部３６とを含む。
【００４６】
換言器１４はさらに、同じ換言を生じさせるような導出の尤度の総和を求める総和ユニット３８と、総和ユニット３８によって計算された尤度の総和が最も高い換言を選択し選択された換言を換言された文４２として出力するためのセレクタ４０とを含む。なお、セレクタ４０は、換言文のうち、入力文３０とは異なるものを選択する。
【００４７】
この実施例の換言コーパス２０は出願人が作成した換言コーパスのサブセットである。このコーパスは、旅行者用に作られた一種のフレーズ集から引いた約５０，０００の換言文（５００，０００語）からなる。このデータを生成するために、約１０００のシーズ文を換言した。
【００４８】
図４はフラグメント生成ユニット２２の詳細なブロック図である。図４を参照して、フラグメント生成ユニット２２は換言コーパス２０内の文をクラスタリングしてクラスタ化されたコーパス７２を生成するためのクラスタリングユニット７０を含む。
【００４９】
クラスタリングユニット７０は、以下の凝集的クラスタリングアルゴリズムに従って換言コーパス２０内の文をクラスタリングする。
【００５０】
１．換言された文の組の各文にそれ自身のクラスタを割当てる。
【００５１】
２．可能なクラスタ対の各々について、それらの距離（クラスタのメンバ間の平均編集距離）を計算する。
【００５２】
３．最も近い２個のクラスタをマージする。
【００５３】
４．クラスタが１個だけになるまで、ステップ２及び３を繰返す。
【００５４】
これを行なうのは、トレーニングに用いられる文の対が、編集距離に関して互いに比較的近いものであるようにしながら、トレーニングセットのサイズを削減するためである。ここで編集距離とは、一つの文を別の文に変換するのに必要とされる挿入、削除、または単語の置換動作の数を示す。
【００５５】
クラスタリングの結果得られるのはツリーすなわち樹形図であり、クラスタ化されたコーパス７２として記憶される。このツリーの葉ノードは文である。ツリー内で互いに近い葉は、編集距離という点でも類似している。こうしたやり方を採るのは、編集距離が類似する文は機械翻訳装置のトレーニングにおいて良好な文の対を形成するはずである、と考えられるためである。
【００５６】
図４を再び参照して、フラグメント生成ユニット２２はさらに、外部信号７３によって指定される粒度で樹形図のサブツリーの葉である文を選択することによって文のクラスタ７６を抽出するためのクラスタ抽出ユニット７４と、抽出された文のクラスタ７６内の文を対にし、文の対８０を出力するための対形成ユニット７８とを含む。
【００５７】
フラグメント生成ユニット２２はさらに、チャルニアックのパーザ（文献５）で文の対８０をパーズし、パーズツリー８４を生成するためのパーザ８２と、パーズツリー８４の各々のソースパーズツリー内のノードをターゲットツリーのノードにマッピングし、マップされたサブツリー８８を生成するためのマッピングユニット８６とを含む。
【００５８】
フラグメント生成ユニット２２はさらに、換言を導出するための文法として用いられることとなるリンクされたサブツリーの対を抽出するリンクされたサブツリー抽出ユニット９０と、コーパス中で各フラグメントが発生する回数を計数するためのカウンタ９２と、以下により、フラグメントの尤度２６を計算する尤度計算ユニット９４とを含む。
【００５９】
【数３】
2005071291.tif 000005
ここで、Ｐ（ｆi）はｉ番目のフラグメントｆiの尤度を示し、｜ｆi｜はフラグメントｆiの回数のカウントを示し、Ｂは全てのリンクされたサブツリーの集合を示し、ｒ（ｆi）及びｒ（ｆj）はフラグメントｆiのツリーのルートノードのラベルを示す。要するに、尤度はフラグメントのカウントを、同じルートノードラベルを備えた全てのサブツリーのカウントの総和で除したものである。
【００６０】
-動作-
この実施例に従ったシステムは以下のように動作する。
【００６１】
このシステムの動作には２つのフェーズがある。第一フェーズでは、換言記憶部２４と尤度記憶部２６とが、フラグメント生成ユニット２２により換言コーパス２０から作られる。第二フェーズでは、入力文３０が換言器１４に与えられ、換言記憶部２４と尤度記憶部２６とに基づき、換言された文４２が生成される。
【００６２】
第一フェーズはさらに、２個のサブフェーズに分けられる。クラスタリングユニット７０、クラスタ抽出ユニット７４及び対形成ユニット７８により、換言コーパス２０から文の対８０（図３）を生成することと、パーザ８２、マッピングユニット８６、リンクされたサブツリー抽出ユニット９０、カウンタ９２、及び尤度計算ユニット９４により、文の対８０から換言記憶部２４及び尤度記憶部２６を生成することとである。
【００６３】
クラスタリングユニット７０は換言コーパス２０の文を、凝集的クラスタリングアルゴリズムによってクラスタリングする。その結果得られるクラスタ化されたコーパス７２はクラスタ抽出ユニット７４に与えられる。クラスタ抽出ユニット７４に外部から与えられる粒度信号７３に応答して、クラスタ抽出ユニット７４は文のクラスタ７６を抽出し、これらを対形成ユニット７８に与える。クラスタ抽出ユニット７４はこのようなサブツリーを、それらのルートノードの平均クラスタ内編集距離のしきい値に従って選択する。対形成ユニット７８はクラスタ内の文を対にし、文の対８０を生成する。
【００６４】
第二のサブフェーズでは、パーザ８２が対の各々の文をパーズし、パーズツリー８４を出力する。マッピングユニット８６は対の文の各々のパーズツリー内のノードをマッピングする。その結果得られるマッピングされたサブツリー８８はリンクされたサブツリー抽出ユニット９０に与えられる。
【００６５】
リンクされたサブツリー抽出ユニット９０はリンクされたサブツリー（またはフラグメント２４）をマッピングされたサブツリー８８から抽出する。このとき、カウンタ９２はフラグメントが換言コーパス２０内で発生する回数をそれぞれカウントする。カウントに基づき、尤度計算ユニット９４がフラグメントの尤度を計算する。
【００６６】
第二フェーズでは、換言器１４が入力文３０から換言された文４２を生成する。最初に、パーザ３２が入力文３０をパーズし、その結果得られる入力文３０のパーズツリーを導出ユニット３４に与える。導出ユニット３４は、換言記憶部２４に基づき、３２から与えられたサブツリーに合成演算子を適用して、入力文３０の導出３６を導出する。同時に、導出それぞれの尤度が、式（２）に従い、尤度記憶部２６に記憶されたフラグメントの尤度を用いて計算される。
【００６７】
同じ文に多くの導出が可能であるため、総和ユニット３８はターゲット換言の各々について全ての導出の総和を計算する。セレクタ４０は最良の換言を最も高い尤度を備えたものとして選択し、これを換言された文４２として出力する。
【００６８】
-評価-
４個のソースからの換言を評価した。人間の換言、英語についてのこの実施例によるＤＯＰＰシステム、統計的機械翻訳ベースのシステム、及び単純なベースラインモードである。
【００６９】
人間がラベル付けした出力は、コーパスから適当に取り出した、人間が換言した文のサンプルであった。自動的に生成した出力の場合、元の入力文とは異なる文で、最も尤度の高い文を評価した。
【００７０】
ベースラインモデルは、ターゲット文の最大単語バイグラム尤度に基づく。
【００７１】
統計的機械翻訳（ＳＭＴ）ベースのシステムは、換言コーパスからの文の対でトレーニングされた統計的機械翻訳システムを用いて換言を生成する。ＳＭＴベースのシステムは文献６に開示のシステムと類似しており、英文を直接換言する。このシステムは広く利用可能なＥＧＹＰＴソフトウェアと、出願人の開発したマルチスタックデコーダとからなる。このシステムは、本実施例のＤＯＰＰシステムと同じデータでトレーニングされた。
【００７２】
図５の文はシステムの入出力の例を示す。換言を機械翻訳の出力として、適切性試験（ａｄｅｑｕａｃｙ  ｔｅｓｔ）（文献７）を用いてスコアリングした。文には、英語を母国語とする３人の評価者により、１から５までの順位を付けた。評点５は、ソース文の表す全ての意味が換言に存在することを示す。評点１は、意味が全く保たれていないことを示す。
【００７３】
ソースの各々からの４０個の文をランダムに混ぜ、３人の判定者に同時に順位付けさせたが、判定者には、これらの文はすべて自動的に生成されたものであると説明してある。結果を表１の左から２番目の欄に示す。
【００７４】
【表１】
2005071291.tif 000006
すべての判定者が、システムを、ベースライン＜ＳＭＴ＜ＤＯＰＰ＜人間の順で評価した。結果をＴテストにかけ、これら技術の評点間の差異全てが有意か否かを判定した。試験では、ｐ＜０．０５であればこれが当てはまることが示された。
【００７５】
これら事例のうち、４７％で、全ての判定者が換言について同じ評点を割当てた。カッパ統計によって測定した判定者間の平均一致率は０．６３であり、一致のレベルがそれほど高くはないことから、分類作業の曖昧さを示すものとなった。
【００７６】
さらに、各試験文について人間による他の１３個の換言からなる基準換言のセットに対し、４個の換言ソースからの出力をスコアリングした。この評価では、人による評価に用いられた試験セットに対する、２００文のスーパーセットが用いられた。ソース文自体は基準セットから除外された。出力は、ＮＩＳＴ（Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄ  ＆  Ｔｅｃｈｎｏｌｏｇｙ）及びＢＬＥＵの両者について、広く入手可能なＭＴＥＶＡＬ−ＫＩＴ評価ソフトウェア（文献８）のバージョン０．９ｃを用いてスコアリングした。これらのスコアも表１の右２欄に示してある。
【００７７】
表１からわかるように、３つの自動システムは全て、人間にくらべＢＬＥＵスコアがかなり低い。しかし、ＤＯＰＰシステムは最も高いＮＩＳＴスコアを達成した。
【００７８】
上述の実施例は単なる例示であって制限的なものと解してはならない。例えば、この発明の実施例の記載に照らして、当業者であればこの発明が汎用コンピュータ上で実行されるソフトウェアで実現され得ること、このようなソフトウェアでプログラムされたコンピュータが上述の換言装置として動作することを理解するであろう。
【００７９】
本発明の範囲は、発明の詳細な説明の記載を参酌した上で、特許請求の範囲の各請求項によって示され、そこに記載された文言と均等の意味及び範囲内でのすべての変更を含む。
【００８０】
‐参考文献‐
[1]ポウツマ．1998．データ指向翻訳、「オランダにおける第９回計算機的言語学会議」、リューベン、ベルギー
[2]ボッド．1998．「文法を超えて：経験ベースの言語理論、ＣＳＬＩ講義ノート、第８８号」ＣＬＳＩ出版、スタンフォード、カリフォルニア
[3]ボッド．2001．「最大のパーズ精度を達成する最小のフラグメントセットは何か？」ＡＣＬ‐2001予稿集、ツールーズ、フランス
[4]イマムラ．2001．「パーズとハーモナイズした階層的句アライメント」、第６回自然言語処理環太平洋シンポジウム(NLPRS-2001)、第377‐384頁
[5]チャルニアック．1999．「最大エントロピー直観パーザ」技術レポートCS-99-12、ブラウン大学
[6]フィンチ、Ｔ．ワタナベ、Ｅ.スミタ．2002．「統計的機械翻訳による換言」ＦＩＴ2002  予稿集、東京、日本
[7]ドヨン、Ｋ．テイラー及びＪ．Ｓ．ホワイト．1998．「ＤＡＲＰＡ  ＭＴ評価方法：過去と現在」ＡＴＭＡカンファレンス、フィラデルフィア、ＰＡ．
[8]ドジントン．2002．「Ｎ−グラム同時発生統計を用いた機械翻訳品質の自動評価」ＨＬＴカンファレンス予稿集、サンディエゴ、カリフォルニア
【図面の簡単な説明】
【００８１】
【図１】リンクされたサブツリーの例を示す図である。
【図２】「Ｉ  ｌｉｋｅ  ｔｅｎｎｉｓ」からの換言「Ｉ  ｅｎｊｏｙ  ｔｅｎｎｉｓ」の１つの導出を概略的に示す図である。
【図３】この発明の１実施例による換言システムのブロック図である。
【図４】図３に示されたフラグメント生成ユニット２２の詳細なブロック図である。
【図５】この発明の実施例の実験結果を表形式で示す図である。
【符号の説明】
【００８２】
１４  換言器、２０  換言コーパス、２２  フラグメント生成ユニット、２４  換言記憶部、２６  尤度記憶部、３０  入力文、３２  パーザ、３４  導出ユニット、３８  総和ユニット、４０  セレクタ、４２  換言された文、７０  クラスタリングユニット、７４  クラスタ抽出ユニット、７８  対形成ユニット、８２  パーザ、８６  マッピングユニット、９０  リンクされたサブツリー抽出ユニット、９２  コンピュータ、９４  尤度計算ユニット
【図１】
2005071291.tif 000007
【図２】
2005071291.tif 000008
【図３】
2005071291.tif 000009
【図４】
2005071291.tif 000010
【図５】
2005071291.tif 000011
【手続補正書】
【提出日】平成16年7月30日(2004.7.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
リンクされたサブツリー対の集合を記憶するための第一の記憶手段を含み、前記サブツリー対の各々はソースサブツリーとターゲットサブツリーとを含み、
入力文をパーズして入力文のパーズツリーを出力するためのパーズ手段と、
前記パーズ手段によって出力された入力文のパーズツリーのサブツリーに合成演算子を適用して文の集合を導出するための導出手段とをさらに含み、前記合成演算子は第一の記憶手段に記憶された、リンクされたサブツリー対の集合に対し定義され、
前記導出手段によって導出された文の集合中の文のうち、予め定められた条件を満たすものを入力文の換言として選択するための選択手段をさらに含む、換言装置。
【請求項２】
前記リンクされたサブツリー対の尤度を記憶するための第二の記憶手段と、
前記導出手段によって導出された文の各々の尤度を、文を導出するのに用いられた前記サブツリー対の各々の尤度に基づいて計算するための計算手段と、
同じ表現を生成する、導出された文の尤度の総和を求めるための総和手段とをさらに含み、
前記選択手段は、前記導出手段によって導出された文の集合中の文から、総和手段によって求められた尤度の総和が最も高いものを前記入力文の換言として選択するための手段を含む、請求項１に記載の換言装置。
【請求項３】
前記導出手段が、
リンクされたサブツリーの対を検索するための、ツリーノード照合アルゴリズムを含む手段と、
入力文のパーズツリーと、前記入力文のパーズツリーのそれぞれのサブツリーと一致するソースサブツリーにそれぞれ対応するターゲットサブツリーとに、前記合成演算子を適用するための手段とを含む、請求項１に記載の換言装置。
【請求項４】
サブツリー対の尤度は、前記リンクされたサブツリー対の集合に現れるサブツリー対のカウントと、前記リンクされたサブツリー対の集合内の、サブツリー対と同じルートノードラベルを備えたすべてのサブツリー対のカウントの総和との関数である、請求項２または請求項３に記載の換言装置。
【請求項５】
前記サブツリー対の尤度は、前記リンクされたサブツリー対の集合にある当該サブツリー対のカウントを、前記リンクされたサブツリー対の集合内の、前記サブツリー対と同じルートノードラベルを備えた全てのサブツリー対のカウントの総和で除したものである、請求項４に記載の換言装置。
【請求項６】
コンピュータ上で実行されると、コンピュータを請求項１から請求項５のいずれかに記載の換言装置として動作させる、コンピュータプログラム。
【請求項７】
文の対を準備する方法であって、
予め定められた言語の文のコーパスを準備するステップと、
コーパス内の文を、コーパス内の文間の編集距離に応じてクラスタリングするステップと、
所望の粒度に応じて文のクラスタを抽出するステップと、
抽出したクラスタ内で文を対にするステップとを含む、文の対を準備する方法。
【請求項８】
前記クラスタリングするステップは、
前記コーパス内の各文をそれ自身のクラスタに割当てるステップと、
可能なクラスタ対の各々について、当該クラスタ対の間の距離を計算するステップと、
距離が最も近い２個のクラスタをマージするステップと、
クラスタが１個だけになるまで、前記計算するステップ及び前記マージするステップを繰返すステップとを含む、請求項７に記載の方法。
【請求項９】
リンクされたサブツリーを準備する方法であって、
文の対を準備するステップと、
文の対の各々の文をパーズするステップと、
文の対の各々のソース文とターゲット文とにおけるノード間の双射マッピングを定義するステップと、
１）リンクされたサブツリーのリンクされたノードの各々について、両方のノードが子を持たないか、または両方のノードが対応する元のツリーからの全ての子を有し、
２）リンクされたサブツリーの両方のサブツリーにおいて、リンクされていないノードはいずれも、対応する元のツリーからの全ての子を持ち、かつ、
３）リンクされたサブツリーの両方のサブツリーが２以上のノードを含む、
という条件を満たす、前記双射マッピングにより定義された連結サブグラフの全ての対を収集することにより、文の対の各々のソース文とターゲット文とのツリーから、リンクされたサブツリーの対を抽出するステップとを含む、リンクされたサブツリーを準備する方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
この発明に係る換言装置は、リンクされたサブツリー対の集合を記憶するための第一の記憶手段を含む。サブツリー対の各々はソースサブツリーとターゲットサブツリーとを含む。換言装置は、入力文をパーズして入力文のパーズツリーを出力するためのパーズ手段と、パーズ手段によって出力された入力文のパーズツリーのサブツリーに合成演算子を適用して文の集合を導出するための導出手段とをさらに含む。合成演算子は第一の記憶手段に記憶された、リンクされたサブツリー対の集合に対し定義される。換言装置は、導出手段によって導出された文の集合内の文のうち、予め定められた条件を満たすものを、入力文の換言として選択するための選択手段をさらに含む。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
サブツリー対の尤度は、リンクされたサブツリー対の集合に現れるサブツリー対のカウントと、リンクされたサブツリー対の集合内の、サブツリー対と同じルートノードラベルを備えたすべてのサブツリー対のカウントの総和との関数であってもよい。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
特に、サブツリー対の尤度は、リンクされたサブツリー対の集合にある当該サブツリー対のカウントを、リンクされたサブツリー対の集合内の、サブツリー対と同じルートノードラベルを備えた全てのサブツリー対のカウントの総和で除したものであってもよい。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
データ指向翻訳技術の動作方法は、ＤＯＰと同様である。しかしこの場合には、２個のツリーが同時に構築される。ソース言語のツリーと、ターゲット言語でのその文に対応するツリーとである。この場合のフラグメントは、ソースフラグメントのノードとターゲットフラグメントのノードとにおいて意味的に等価なもの同士のリンクを含み、その思想は、リンクされたノード同士を相互に意味を失うことなく交換可能である、というものである。図１の上部に示された対により、リンクされたツリーの対を示す。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
【数２】
2005071291.tif 000012
図２において、ノード１５２は、サブツリー１１２の最も左側の語でない葉ノードであるが、このノード１５２は、フラグメント１４２からのサブツリー１６２で置換され、これに対応して、サブツリー１１４のノード１５４がフラグメント１４２からのサブツリー１６４で置換される。この結果得られるサブツリー対１７０は、サブツリー１７２及び１７４を含む。こうして、フラグメント１４０及び１４２から、換言句「Ｉ  ｅｎｊｏｙ  ｔｅｎｎｉｓ」が導出される。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００３９
【補正方法】変更
【補正の内容】
【００３９】
-曖昧性解消-
ソース文から生じる全ての導出に対し、最も可能性の高い換言を見出す必要がある。実際には、全てのリンクされたサブツリーの集合内のフラグメントのうちのソースフラグメントにより規定されるツリーフラグメントの文法に従ったチャートパーザを用いてソース文がパーズされるので、当然、ターゲット換言のための（必ずしも正確でない）パーズツリーを生成する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００６２
【補正方法】変更
【補正の内容】
【００６２】
第一フェーズはさらに、２個のサブフェーズに分けられる。クラスタリングユニット７０、クラスタ抽出ユニット７４及び対形成ユニット７８により、換言コーパス２０から文の対８０（図４）を生成することと、パーザ８２、マッピングユニット８６、リンクされたサブツリー抽出ユニット９０、カウンタ９２、及び尤度計算ユニット９４により、文の対８０から換言記憶部２４及び尤度記憶部２６を生成することとである。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
クラスタリングユニット７０は換言コーパス２０の文を、凝集的クラスタリングアルゴリズムによってクラスタリングする。その結果得られるクラスタ化されたコーパス７２はクラスタ抽出ユニット７４に与えられる。クラスタ抽出ユニット７４に外部から与えられる外部信号７３に応答して、クラスタ抽出ユニット７４は文のクラスタ７６を抽出し、これらを対形成ユニット７８に与える。クラスタ抽出ユニット７４はこのようなサブツリーを、それらのルートノードの平均クラスタ内編集距離のしきい値に従って選択する。対形成ユニット７８はクラスタ内の文を対にし、文の対８０を生成する。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
リンクされたサブツリー抽出ユニット９０はリンクされたサブツリー（すなわちフラグメント）をマッピングされたサブツリー８８から抽出する。このとき、カウンタ９２はフラグメントが換言コーパス２０内で発生する回数をそれぞれカウントする。カウントに基づき、尤度計算ユニット９４がフラグメントの尤度を計算する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
第二フェーズでは、換言器１４が入力文３０から換言された文４２を生成する。最初に、パーザ３２が入力文３０をパーズし、その結果得られる入力文３０のパーズツリーを導出ユニット３４に与える。導出ユニット３４は、換言記憶部２４に基づき、パーザ３２から与えられたサブツリーに合成演算子を適用して、入力文３０の導出を導き出し、導出記憶部３６に記憶させる。同時に、導出それぞれの尤度が、式（２）に従い、尤度記憶部２６に記憶されたフラグメントの尤度を用いて計算される。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００６７
【補正方法】変更
【補正の内容】
【００６７】
同じ文に多くの導出が可能であるため、総和ユニット３８はターゲット換言の各々について全ての導出の総和を計算する。セレクタ４０は最も高い尤度を備えたものを最良の換言として選択し、これを換言された文４２として出力する。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００６８
【補正方法】変更
【補正の内容】
【００６８】
-評価-
４個のソースからの換言を評価した。人間の換言、英語についてのこの実施例によるＤＯＰＰシステム、統計的機械翻訳ベースのシステム、及び単純なベースラインである。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
ベースラインは、ターゲット文の最大単語バイグラム尤度に基づく。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００８０
【補正方法】変更
【補正の内容】
【００８０】
‐参考文献‐
[1]ポウツマ．1998．データ指向翻訳、「オランダにおける第９回計算機的言語学会議」、リューベン、ベルギー
[2]ボッド．1998．「文法を超えて：経験ベースの言語理論、ＣＳＬＩ講義ノート、第８８号」ＣＬＳＩ出版、スタンフォード、カリフォルニア
[3]ボッド．2001．「最大のパーズ精度を達成する最小のフラグメントセットは何か？」ＡＣＬ‐2001予稿集、ツールーズ、フランス
[4]イマムラ．2001．「パーズとハーモナイズした階層的句アライメント」、第６回自然言語処理環太平洋シンポジウム(NLPRS-2001)、第377‐384頁
[5]チャルニアック．1999．「最大エントロピー直観パーザ」技術レポートCS-99-12、ブラウン大学
[6]フィンチ、Ｔ．ワタナベ、Ｅ.スミタ．2002．「統計的機械翻訳による換言」ＦＩＴ2002  予稿集、東京、日本
[7]ドヨン、Ｋ．テイラー及びＪ．Ｓ．ホワイト．1998．「ＤＡＲＰＡ  ＭＴ評価方法：過去と現在」ＡＴＭＡカンファレンス予稿集、フィラデルフィア、ＰＡ．
[8]ドジントン．2002．「Ｎ−グラム同時発生統計を用いた機械翻訳品質の自動評価」ＨＬＴカンファレンス予稿集、サンディエゴ、カリフォルニア
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
１４  換言器、２０  換言コーパス、２２  フラグメント生成ユニット、２４  換言記憶部、２６  尤度記憶部、３０  入力文、３２  パーザ、３４  導出ユニット、３８  総和ユニット、４０  セレクタ、４２  換言された文、７０  クラスタリングユニット、７４  クラスタ抽出ユニット、７８  対形成ユニット、８２  パーザ、８６  マッピングユニット、９０  リンクされたサブツリー抽出ユニット、９２  カウンタ、９４  尤度計算ユニット
【手続補正１７】
【補正対象書類名】図面
【補正対象項目名】図４
【補正方法】変更
【補正の内容】
【図４】
2005071291.tif 000013
【手続補正１８】
【補正対象書類名】図面
【補正対象項目名】図５
【補正方法】変更
【補正の内容】
【図５】
2005071291.tif 000014
【外国語明細書】
2005071291000001.pdf
2005071291000002.pdf
2005071291000003.pdf
2005071291000004.pdf