機械翻訳装置、および機械翻訳方法
【課題】従来、精度の高い機械翻訳ができなかった。
【解決手段】係り受け森を構成する各頂点に対して、１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する翻訳規則取得部と、係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する超辺取得部と、係り受け森を構成する全頂点と、超辺取得部が取得した１以上の超辺とを有する翻訳森を取得する翻訳森取得部と、翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と単語辞書とを用いて、１以上の翻訳候補を取得する翻訳候補取得部と、１以上の翻訳候補のうちいずれか１以上の翻訳候補である翻訳結果を出力する出力部とを具備する機械翻訳装置により、精度の高い機械翻訳が可能となる。
【解決手段】係り受け森を構成する各頂点に対して、１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する翻訳規則取得部と、係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する超辺取得部と、係り受け森を構成する全頂点と、超辺取得部が取得した１以上の超辺とを有する翻訳森を取得する翻訳森取得部と、翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と単語辞書とを用いて、１以上の翻訳候補を取得する翻訳候補取得部と、１以上の翻訳候補のうちいずれか１以上の翻訳候補である翻訳結果を出力する出力部とを具備する機械翻訳装置により、精度の高い機械翻訳が可能となる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、係り受け森を入力とする機械翻訳装置等に関するものである。
【背景技術】
【０００２】
従来、統計的機械翻訳では、構文情報を利用することによる翻訳精度の向上が図られてきた。例えば、非特許文献１では、入力を文字列、出力を構文木にするのに対し、非特許文献２は構文木を入力として文字列を出力している。さらに、非特許文献２では構文解析の間違いや曖昧性を解消するため、複数の解析結果をコンパクトに表現できる圧縮統語森を入力としている。このように、木あるいは森を入出力とした手法では句構造解析が用いられてきた。しかし、句構造では、例えば日本語など自由な語順をとる言語の解析は困難であり、また解析の曖昧性が生じやすい。これに対し、係り受けと呼ばれる依存構造を用いる手法が提案され、例えば、非特許文献３では入出力ともに依存構造であるのに対し、非特許文献４は入力を文字列、出力に依存構造を使用、非特許文献５や６では、入力を句構造、出力に依存構造を使用している。この係り受けでは単語間の依存構造によって文の構造が表現され、句構造での問題が生じにくい。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What's in a translation rule? In Proceedings of HLT-NAACL, pages 273-280.
【非特許文献２】Haitao Mi, Liang Huang, and Qun Liu. 2008. Forest- based translation. In Proceedings of ACL: HLT, Columbus, OH.
【非特許文献３】Yuan Ding and Martha Palmer. 2005. Machine translation using probablisitic synchronous dependency insertion grammars. In Proceedings of the 43rd ACL, Ann Arbor, MI.
【非特許文献４】A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model . 2008. Libin Shen, Jinxi Xu and Ralph Weischedelin Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL).
【非特許文献５】Haitao Mi and Qun Liu. 2010. Constituency to Dependency Translation with Forests. In Proceedings of ACL.
【非特許文献６】Zhaopeng Tu, Yang Liu, Young-Sook Hwang, Qun Liu and Shouxun Lin. 2010. Dependency Forest for Statistical Machine Translation. In Proceedings COLING.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、例えば、非特許文献３に係る技術は、入出力ともに依存構造をとり、モデルがスパースになる問題があり、精度の高い機械翻訳ができなかった。また、非特許文献４から６では、出力に依存構造を使用しているが、これは単に制約として用いており、依存構造解析の利点である曖昧性の少なさを生かしていないために、精度の高い機械翻訳ができなかった。
【課題を解決するための手段】
【０００５】
本第一の発明の機械翻訳装置は、原言語の文を係り受け解析して取得された２以上の係り受けであり、原言語の文を構成する単語とスパンとを含む２以上の頂点を有する２以上の係り受けのうち、同一である内部頂点を共通化し、構成された係り受け森を格納し得る係り受け森格納部と、原言語の係り受けの部分木であり、部分木の内部頂点は単語であり、内部頂点以外の頂点は単語か変数をとる部分木である左辺と、左辺に対応する目的言語の文字列であり、単語と変数を有する文字列である右辺とを対応付けて有し、かつスコアを有する１以上の翻訳規則を格納し得る翻訳規則格納部と、原言語の単語と目的言語の単語とを対応付けた情報である１以上の単語対を格納し得る単語辞書と、係り受け森を構成する各頂点に対して、翻訳規則格納部の１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する翻訳規則取得部と、係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する超辺取得部と、係り受け森を構成する全頂点と、超辺取得部が取得した１以上の超辺とを有する翻訳森を取得する翻訳森取得部と、翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と、単語辞書とを用いて、１以上の翻訳候補を取得する翻訳候補取得部と、翻訳候補取得部が取得した１以上の翻訳候補のうち、いずれか１以上の翻訳候補である翻訳結果を出力する出力部とを具備する機械翻訳装置である。
【０００６】
かかる構成により、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる。
【０００７】
また、本第二の発明の機械翻訳装置は、第一の発明に対して、原言語の文と目的言語の文とを有する１以上の対訳文を有する対訳コーパスと、対訳コーパスにおいて、１以上の各翻訳規則の出現頻度を取得する出現頻度取得部と、各翻訳規則の出現頻度を用いて、スコアを算出するスコア算出部とをさらに具備し、翻訳規則が有するスコアは、スコア算出部が算出したスコアである機械翻訳装置である。
【０００８】
かかる構成により、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる。
【０００９】
また、本第三の発明の機械翻訳装置は、第一または第二の発明に対して、翻訳規則取得部が、係り受け森を構成する頂点に対する翻訳規則を取得できなかった場合、翻訳規則を取得できなかった頂点が有する原言語の単語に対応する目的言語の単語を単語辞書から取得し、頂点を内部頂点とし、頂点のテイルを有する左辺と、左辺に対応する目的言語の文字列であり、目的言語の単語と、頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する翻訳規則生成部をさらに具備し、翻訳規則取得部は、係り受け森を構成する各頂点に対して、翻訳規則生成部が生成した１以上の翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する機械翻訳装置である。
【００１０】
かかる構成により、さらに精度の高い機械翻訳が可能となる。
【００１１】
また、本第四の発明の機械翻訳装置は、第一から第三いずれかの発明に対して、係り受け森が有する各超辺のテイルの数が３以上である場合に、超辺のテイルの数が２以下となるように、超辺の一のテイルと超辺の他の一のテイルの擬似的なヘッドであり、一のテイルと他の一のテイルの元のヘッドのテイルとなるヘッドを生成し、新たな超辺を構成する超辺構成部をさらに具備し、係り受け森格納部の係り受け森は、超辺構成部が構成した新たな超辺を含む係り受け森である機械翻訳装置である。
【００１２】
かかる構成により、さらに精度の高い機械翻訳が可能となる。
【発明の効果】
【００１３】
本発明による機械翻訳装置によれば、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる。
【図面の簡単な説明】
【００１４】
【図１】実施の形態１における機械翻訳装置のブロック図
【図２】実施の形態１における機械翻訳装置の動作について説明するフローチャート
【図３】実施の形態１における係り受け森構成処理の動作について説明するフローチャート
【図４】実施の形態１における翻訳森構成処理の動作について説明するフローチャート
【図５】実施の形態１における翻訳候補取得処理の動作について説明するフローチャート
【図６】実施の形態１における変数代入処理の動作について説明するフローチャート
【図７】実施の形態１における翻訳規則格納部に格納されている翻訳規則の例を示す図
【図８】実施の形態１における係り受けの例を示す図
【図９】実施の形態１における係り受けの例を示す図
【図１０】実施の形態１における係り受け森の例を示す図
【図１１】実施の形態１におけるバイナリゼーションを説明する図
【図１２】実施の形態１における係り受けの例を示す図
【図１３】実施の形態１における一時的な翻訳森の例を示す図
【図１４】実施の形態１における一時的な翻訳森の例を示す図
【図１５】実施の形態１における一時的な翻訳森の例を示す図
【図１６】実施の形態１における一時的な翻訳森の例を示す図
【図１７】実施の形態１における最終的な翻訳森の例を示す図
【図１８】実施の形態１における係り受け解析の精度を示す図
【図１９】実施の形態１における係り受け森のＫ−ｂｅｓｔ数と翻訳規則数の関係を示す図
【図２０】実施の形態１におけるＢＬＥＵによる翻訳精度の差を示す図
【図２１】実施の形態１におけるコンピュータシステムの概観図
【図２２】実施の形態１におけるコンピュータシステムのブロック図
【発明を実施するための形態】
【００１５】
以下、機械翻訳装置等の実施形態について図面を参照して説明する。なお、実施の形態において同じ符号を付した構成要素は同様の動作を行うので、再度の説明を省略する場合がある。
【００１６】
（実施の形態１）
本実施の形態において、係り受け森を入力とする統計的機械翻訳を行う機械翻訳装置について説明する。機械翻訳装置は、２以上の係り受けから係り受け森を自動取得できる。また、機械翻訳装置は、翻訳規則に関する確率値を素性として取得し、当該素性をパラメータとする算出式により、翻訳規則のスコアを算出する。さらに、機械翻訳装置は、係り受け森の頂点に適用できる翻訳規則が無い場合、擬似的な超辺を生成する。
【００１７】
図１は、本実施の形態における機械翻訳装置１のブロック図である。機械翻訳装置１は、対訳コーパス１０１、単語辞書１０２、係り受け森格納部１０４、翻訳規則格納部１０５、係り受け解析部１０６、翻訳規則抽出部１０７、超辺構成部１０８、出現頻度取得部１０９、スコア算出部１１０、翻訳規則取得部１１１、翻訳規則生成部１１２、超辺取得部１１３、翻訳森取得部１１４、翻訳候補取得部１１５、翻訳結果取得部１１６、および出力部１１７を備える。
【００１８】
対訳コーパス１０１は、１以上の対訳文を有する。対訳文は、原言語の文と目的言語の文とを有する。
【００１９】
単語辞書１０２は、１以上の単語対を格納し得る。単語対とは、原言語の単語と目的言語の単語とを対応付けた情報である。
【００２０】
係り受け森格納部１０４は、係り受け森を格納し得る。係り受け森とは、２以上の係り受けのうち、同一である内部頂点を共通化し、構成された情報である。さらに、簡単に説明すれば、係り受け森は、複数の係り受け木のうち共通する解析部分を共有させて森として表しているものである。なお、係り受け森格納部１０４に格納された係り受け森は、後述する係り受け解析部１０６が取得した係り受け森である。なお、頂点を共通化する処理とは、例えば、リンク先を共通にする処理等であり、その処理方法は問わない。
【００２１】
また、形式的に圧縮された（内部頂点を共通化した）係り受け森Ｆは、頂点の集合Ｖと超辺の集合Ｅを持った＜Ｖ，Ｅ＞と表現できる。そして、文をｗ１：ｌ＝ｗ１・・・ｗｌとした場合、各頂点ｖ（∈Ｖ）は単語ｗ１と単語ｗｌが支配する文内のスパンｉ，ｊからｗｉ，ｊと表現できる。超辺ｅは＜ｔａｉｌｓ（ｅ），ｈｅａｄ（ｅ）＞と定義でき、ｈｅａｄ（ｅ）∈Ｖ，ｔａｉｌｓ（ｅ）∈Ｖ＊である。なお、Ｖ＊は、超辺の集合の列である。超辺ｅ１が、例えば、「ｅ１：＜（ｉ０，１，ｇｉｒｌ２，４，ｗｉｔｈ４，７），ｓａｗ０，７＞とすると、かかる超辺ｅ１は、ｓａｗをヘッド（ｈｅａｄ）に持ち、ｉ，ｇｉｒｌ，ｗｉｔｈをテイル（ｔａｉｌ）に持つ。
【００２２】
また、係り受けは、原言語の文を構成する単語とスパンとを含む２以上の頂点を有する。また、係り受けは、単語(または文節)間の依存関係によって、文の構文構造を表したものである。
【００２３】
また、係り受けの構造は、例えば、以下のような構造である。係り受けは、頂点をスパンが付与された単語とし、一つの単語と複数の単語を結ぶ超辺で定義した超グラフで表現される。なお、超辺とは、一の頂点（ヘッドという。）、および当該ヘッドとリンク関係にある１以上の頂点（テイルという。）を有する情報である。
【００２４】
また、係り受けでは、超グラフ上の超辺に、確率を重みをとして割り当てていても良い。例えば、Ｔｕ１０（Z. Tu, Y. Liu, Y. S. Hwang, Q. Liu, and S. Lin. Depen-dency forest for statistical machine translation. In Pro-ceedings of Coling, pages 1092-1100, August 2010.参照）に従って，各超辺に確率を付与しても良い。Ｔｕ１０の手法では、まず、各超辺の出現回数ｃ（ｅ）に、数式１に示すような正の値を割り当てる。数式１において、ｓ（ｖ１，ｖ２）は、ｖ２をヘッド（ｈｅａｄ）、ｖ１をテイル（ｔａｉｌ）としたときの係り受け解析モデルのスコアを返す公知の関数である。また、数式１において、｜tails(e)｜は、超辺ｅをテイルに有する数である。
【数１】
【００２５】
次に、この回数ｃ（ｅ）に基づいて、超辺の確率ｐ（ｅ）を、数式２を用いて算出しても良い。なお、数式２において、e'は、eとは異なる超辺である。
【数２】
【００２６】
翻訳規則格納部１０５は、１以上の翻訳規則を格納し得る。翻訳規則は、左辺と右辺とを対応付けて有する。また、翻訳規則はスコアを有する、とする。また、翻訳規則の左辺は、原言語の係り受けの部分木である。そして、部分木の内部頂点は単語であり、内部頂点以外の頂点は単語か変数をとる。また、右辺は、左辺に対応する目的言語の文字列であり、単語と変数を有する文字列である。なお、翻訳規則が有するスコアは、スコア算出部１１０が算出したスコアである。翻訳規則格納部１０５の翻訳規則は、例えば、ＧＨＫＭアルゴリズム（M. Galley, J. Graehl, K. Knight, D. Marcu, S. DeNeefe,W.Wang, and I. Thayer. Scalable inference and training of context-rich syntactic translation models. In Proceedings of Coling-ACL, pages 961-968, July 2006.，M. Galley, M. Hopkins, K. Knight, and D. Marcu. What's in a translation rule? In HLT-NAACL, pages 273-280,May 2004.参照）により実現され得る。つまり、翻訳規則の取得方法は公知技術であり、以下のように行われる。ＧＨＫＭアルゴリズムでは最小規則と呼ばれる最小単位の取り出し可能な規則を取り出した後、それらを結合することでより大きな単位の規則を作り出す。この操作によって作り出される規則は結合規則と呼ばれる。この結合規則を取り出す際には規則のサイズや規則数の閾値などを設けることで取り出す規則の大きさや数に制限が設けられる。
【００２７】
係り受け解析部１０６は、原言語の文や句などの係り受け解析（依存構造解析）を行い、係り受け森を取得する。係り受け森を取得する技術は公知技術であるので詳細な説明を省略する。なお、係り受け森の取得は、例えば、MST parser(http://www.seas.upenn.edu/~strctlrn/MSTParser/MSTParser.html参照)を利用して、Eisnerのアルゴリズム(http://www.cs.jhu.edu/~jason/papers/eisner.iwptbook00.pdf参照)により行う。ただし、係り受け解析部１０６は、かかる方法以外の方法により、係り受け森を取得しても良い。また、係り受け解析部１０６は、例えば、図示しない入力手段により入力された原言語の文や句などから係り受け森を取得する。
【００２８】
また、係り受け解析部１０６は、対訳コーパス１０１が有する１以上の原言語の文に対して、係り受け解析を行い、１以上の係り受け森を取得する。かかる係り受け森は、翻訳規則の生成に利用される。
【００２９】
翻訳規則抽出部１０７は、係り受け解析部１０６が対訳コーパス１０１から取得した係り受け森と、目的言語の文の単語列に対して、単語単位のアライメントを取得し、１以上の翻訳規則を取得する。なお、係り受け森と、目的言語の文の単語列に対して、単語単位の対応関係（アライメント）を取得する処理は、例えば、ＧＩＺＡ＋＋により行われる。ＧＩＺＡ＋＋では、IBM Model1〜5を用いて翻訳する言語と目的言語における単語のアライメントの確率値を計算する。そして、確率値が所定以上、大きいアライメントが採用される。また、１以上の翻訳規則を取得する処理は、通常、既存のルールマッチングの手法を用いる（例えば、http://www.aclweb.org/anthology/P/P08/P08-1023.pdf参照）。例えば、１以上の翻訳規則を取得する処理は、ＧＨＫＭアルゴリズムを適用することにより行われる。つまり、係り受け森と、目的言語の文の単語列に対して、単語単位のアライメントを取得し、翻訳規則を取得する処理は公知技術であり、いかなる方法を用いて、行われても良い。さらに、翻訳規則抽出部１０７が利用する係り受け森は、後述する超辺構成部１０８により、超辺のテイルの数が２以下となるように処理された係り受け森であることは好適である。
【００３０】
超辺構成部１０８は、係り受け森が有する各超辺のテイルの数が３以上である場合に、超辺のテイルの数が２以下となるように、超辺の一のテイルと超辺の他の一のテイルの擬似的なヘッドであり、一のテイルと他の一のテイルの元のヘッドのテイルとなるヘッドを生成し、新たな超辺を構成する。なお、超辺構成部１０８が行う処理をバイナリゼーション（ｂｉｎａｒｉｚａｔｉｏｎ）という。機械翻訳装置１において、係り受け森から翻訳規則の抽出やデコードを行うことになるが、ある超辺が持つテイルの数が多くなると、翻訳規則の質やデコードの効率に問題が生じる。そこで、係り受け森をバイナリゼーションし、超辺が持つテイルの数に制限を加えることは好適である。ここで、バイナリゼーションとは超辺のテイルのサイズが２以下であるようにすることである。バイナリゼーションは、ある超辺が持つテイルのサイズが３以上である場合、例えば、最も左の要素とその次の要素をヘッドから生成する擬似的な頂点をヘッドとした新たな超辺のテイルとして構成し直すという作業を再帰的に行うことである。
【００３１】
出現頻度取得部１０９は、対訳コーパス１０１において、１以上の各翻訳規則の出現頻度を取得する。
【００３２】
スコア算出部１１０は、各翻訳規則の出現頻度を用いて、スコアを算出する。スコア算出部１１０は、翻訳規則の出現頻度をパラメータとする算出式を用いて、スコアを算出する。つまり、スコア算出部１１０は、翻訳規則の出現の確率値を用いて、スコアを算出する。なお、スコア算出部１１０は、対数線形モデルを用いて、スコアを算出することが好適である。対数線形モデルは、複数の素性を重みで線形結合した形で表される。素性に対する重みは与えられた訓練データ上で翻訳の評価尺度(BLEUなど)を最大化するように学習される。この学習法は誤り率最小化学習法(MERT)と呼ばれており、公知技術であるので、説明を省略する。また、素性は、両方向からの単語翻訳確率、翻訳規則に関する確率（後述する数式３、数式４、数式５により算出される確率値）、係り受け解析スコア、N-gram言語モデル、単語数、規則数などであることは好適である。ただし、スコアの算出式は問わない。また、スコア算出部１１０は、算出式を予め保持している。
【００３３】
翻訳規則取得部１１１は、係り受け森を構成する各頂点に対して、翻訳規則格納部１０５の１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する。
【００３４】
また、翻訳規則取得部１１１は、係り受け森を構成する頂点に対する翻訳規則を取得できなかった場合、翻訳規則生成部１１２に翻訳規則を生成させ、当該翻訳規則生成部１１２が生成した１以上の翻訳規則を、係り受け森を構成する各頂点に対して、合致する１以上の翻訳規則を取得することは好適である。つまり、翻訳規則取得部１１１は、係り受け森を構成する各頂点に対して、翻訳規則生成部１１２が生成した１以上の翻訳規則と翻訳規則格納部１０５の１以上の各翻訳規則とを適用し、頂点ごとに、合致する１以上の翻訳規則を取得することは好適である。なお、頂点が翻訳規則に合致するとは、翻訳規則の左辺が、頂点または頂点を内部頂点とする超辺と一致することである。または、頂点が翻訳規則に合致するとは、翻訳規則の左辺の変数部分を任意の文字列に合致するとした場合に、頂点または頂点を内部頂点とする超辺に合致することでも良い。
【００３５】
翻訳規則生成部１１２は、翻訳規則取得部１１１が、係り受け森を構成する頂点に対する翻訳規則を取得できなかった場合、翻訳規則を取得できなかった頂点が有する原言語の単語に対応する目的言語の単語を単語辞書１０２から取得し、頂点を内部頂点とし、頂点のテイルを有する左辺と、左辺に対応する目的言語の文字列であり、目的言語の単語と、頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する。なお、翻訳規則の生成方法は、他の方法でも良い。
【００３６】
超辺取得部１１３は、係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する。また、超辺取得部１１３は、超辺に、１以上の各の右辺を付与する。ここでの翻訳規則とは、翻訳規則取得部１１１が取得した翻訳規則である。
【００３７】
翻訳森取得部１１４は、翻訳森を取得する。翻訳森とは、係り受け森を構成する全頂点と、超辺取得部１１３が取得した１以上の超辺とを有する情報である。
【００３８】
翻訳候補取得部１１５は、翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と、単語辞書１０２とを用いて、１以上の翻訳候補を取得する。
【００３９】
翻訳結果取得部１１６は、翻訳候補取得部１１５が取得した１以上の翻訳候補のうち、各翻訳候補に対応する翻訳規則のスコアを用いて、一の翻訳結果を取得する。
【００４０】
出力部１１７は、翻訳候補取得部１１５が取得した１以上の翻訳候補のうち、いずれか１以上の翻訳候補である翻訳結果を出力する。なお、出力部１１７は、翻訳結果取得部１１６が取得した一の翻訳結果を出力することは好適である。ただし、出力部１１７は、翻訳候補取得部１１５が取得した１以上の翻訳候補をすべて出力しても良いし、１以上の翻訳候補のうちの一部を出力しても良い。ここで、出力とは、ディスプレイへの表示、プロジェクターを用いた投影、プリンタでの印字、音出力、外部の装置への送信、記録媒体への蓄積、他の処理装置や他のプログラムなどへの処理結果の引渡しなどを含む概念である。
【００４１】
対訳コーパス１０１、単語辞書１０２、係り受け森格納部１０４、および翻訳規則格納部１０５は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。対訳コーパス１０１等に対訳文等が記憶される過程は問わない。例えば、記録媒体を介して対訳文等が対訳コーパス１０１で記憶されるようになってもよく、通信回線等を介して送信された対訳文等が対訳コーパス１０１等で記憶されるようになってもよく、あるいは、入力デバイスを介して入力された対訳文等が対訳コーパス１０１等で記憶されるようになってもよい。
【００４２】
係り受け解析部１０６、翻訳規則抽出部１０７、超辺構成部１０８、出現頻度取得部１０９、スコア算出部１１０、翻訳規則取得部１１１、翻訳規則生成部１１２、超辺取得部１１３、翻訳森取得部１１４、翻訳候補取得部１１５、および翻訳結果取得部１１６は、通常、ＭＰＵやメモリ等から実現され得る。係り受け解析部１０６等の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【００４３】
出力部１１７は、ディスプレイやスピーカー等の出力デバイスを含むと考えても含まないと考えても良い。出力部１１７は、出力デバイスのドライバーソフトまたは、出力デバイスのドライバーソフトと出力デバイス等で実現され得る。
【００４４】
次に、機械翻訳装置１の動作について、図２のフローチャートを用いて説明する。なお、図２のフローチャートにおける処理の前に、翻訳規則格納部１０５には、上述したＧＨＫＭアルゴリズム等により、翻訳規則が蓄積された、とする。
【００４５】
（ステップＳ２０１）係り受け森取得部１０７は、係り受け格納部１０３に格納されている２以上の係り受けを読み出す。
【００４６】
（ステップＳ２０２）係り受け森取得部１０７は、ステップＳ２０１で読み出した２以上の係り受けを用いて、係り受け森を構成する。この係り受け森構成処理については、図３のフローチャートを用いて説明する。
【００４７】
（ステップＳ２０３）翻訳規則取得部１１１は、係り受け森格納部１０４の係り受け森を読み出す。
【００４８】
（ステップＳ２０４）翻訳規則取得部１１１等は、係り受け森から翻訳森を構成する。翻訳森構成処理については、図４のフローチャートを用いて説明する。
【００４９】
（ステップＳ２０５）翻訳候補取得部１１５は、ステップＳ２０４で構成された翻訳森を用いて、１以上の翻訳候補を取得する。この翻訳候補取得処理については、図５のフローチャートを用いて説明する。
【００５０】
（ステップＳ２０６）翻訳結果取得部１１６は、ステップＳ２０５で取得された１以上の翻訳候補から、一の翻訳候補を選択する。かかる一の翻訳候補が一の翻訳結果である。なお、翻訳結果取得部１１６は、通常、各翻訳候補に対応する翻訳規則のスコアを用いて、一の翻訳結果を取得する。翻訳結果取得部１１６は、例えば、各翻訳候補に対応する１以上の翻訳規則のスコアの合計が最大になるような翻訳候補を選択する。
【００５１】
（ステップＳ２０７）出力部１１７は、ステップＳ２０６で取得された翻訳結果を出力し、処理を終了する。
【００５２】
次に、ステップＳ２０２の係り受け森構成処理について、上述したように、係り受け解析部１０６が、原言語の文や句などの係り受け解析を行い、係り受け森を取得する。つまり、係り受け解析部１０６は、例えば、MST parserを利用して、Eisnerのアルゴリズムにより行う。しかし、係り受け解析部１０６は、図３のフローチャートに示す方法により、係り受け森を構成することも可能である。図３のフローチャートの開始前に、係り受け解析部１０６は、原言語の文や句などの係り受け解析を行い、２以上の係り受け（係り受け木）を取得し、バッファ（例えば、図示しない係り受け格納部）に格納している、とする。
【００５３】
（ステップＳ３０１）係り受け解析部１０６は、カウンタｉに１を代入する。
【００５４】
（ステップＳ３０２）係り受け解析部１０６は、係り受け格納部に、ｉ番目の係り受けが存在するか否かを判断する。ｉ番目の係り受けが存在すればステップＳ３０３に行き、存在しなければ上位処理（ステップＳ２０３）にリターンする。
【００５５】
（ステップＳ３０３）係り受け解析部１０６は、係り受け格納部から、ｉ番目の係り受けを読み出す。
【００５６】
（ステップＳ３０４）係り受け解析部１０６は、カウンタｊに１を代入する。
【００５７】
（ステップＳ３０５）係り受け解析部１０６は、ｉ番目の係り受けにおいて、ｊ番目の頂点が存在するか否かを判断する。ｊ番目の頂点が存在すればステップＳ３０６に行き、存在しなければステップＳ３１２に行く。
【００５８】
（ステップＳ３０６）係り受け解析部１０６は、（ｉ＋１）番目以降の係り受けにおいて、ｊ番目の頂点と同一の頂点を検索する。
【００５９】
（ステップＳ３０７）係り受け解析部１０６は、カウンタｋに１を代入する。
【００６０】
（ステップＳ３０８）係り受け解析部１０６は、ステップＳ３０６において、ｊ番目の頂点と同一のｋ番目の頂点が存在するか否かを判断する。ｋ番目の頂点が存在すればステップＳ３０９に行き、存在しなければステップＳ３１１に行く。
【００６１】
（ステップＳ３０９）係り受け解析部１０６は、ｉ番目の係り受けのｊ番目の頂点と、他の係り受けのｋ番目の頂点とを共通化する処理を行う。
【００６２】
（ステップＳ３１０）係り受け解析部１０６は、カウンタｋを１、インクリメントし、ステップＳ３０８に戻る。
【００６３】
（ステップＳ３１１）係り受け解析部１０６は、カウンタｊを１、インクリメントし、ステップＳ３０５に戻る。
【００６４】
（ステップＳ３１２）係り受け解析部１０６は、カウンタｉを１、インクリメントし、ステップＳ３０２に戻る。
【００６５】
次に、ステップＳ２０３の翻訳森構成処理について、図４のフローチャートを用いて説明する。
【００６６】
（ステップＳ４０１）翻訳規則取得部１１１は、カウンタｉに１を代入する。
【００６７】
（ステップＳ４０２）翻訳規則取得部１１１は、係り受け森が有する頂点のうち、ｉ番目の頂点が存在するか否かを判断する。ｉ番目の頂点が存在すればステップＳ４０３に行き、存在しなければ上位処理（ステップＳ２０５）にリターンする。
【００６８】
（ステップＳ４０３）翻訳規則取得部１１１は、カウンタｊに１を代入する。
【００６９】
（ステップＳ４０４）翻訳規則取得部１１１は、翻訳規則格納部１０５に、ｊ番目の翻訳規則が存在するか否かを判断する。ｊ番目の翻訳規則が存在すればステップＳ４０５に行き、存在しなければステップＳ４１１に行く。
【００７０】
（ステップＳ４０５）翻訳規則取得部１１１は、係り受け森が有するｉ番目の頂点が、ｊ番目の翻訳規則に合致するか否かを判断し、判断結果を所定の変数に代入する。
【００７１】
（ステップＳ４０６）所定の変数の値が"合致"であればステップＳ４０６に行き、"合致"でなければステップＳ４１０に行く。
【００７２】
（ステップＳ４０７）超辺取得部１１３は、ｊ番目の翻訳規則の右辺を有する超辺を構成する。
【００７３】
（ステップＳ４０８）翻訳森取得部１１４は、ステップＳ４０７で構成された超辺を、予め決められたバッファに追記する。なお、このバッファは、翻訳森を格納するバッファである。
【００７４】
（ステップＳ４０９）翻訳森取得部１１４は、ｊ番目の翻訳規則の右辺とテイルとなる頂点とを対応付けて記憶する。
【００７５】
（ステップＳ４１０）翻訳規則取得部１１１は、カウンタｊを１、インクリメントし、ステップＳ４０４に戻る。
【００７６】
（ステップＳ４１１）翻訳規則生成部１１２は、係り受け森が有するｉ番目の頂点に対応する翻訳規則を取得できたか否かを判断する。翻訳規則を取得できていた場合はステップＳ４１２に行き、翻訳規則を取得できていない場合はステップＳ４１３に行く。なお、翻訳規則を一つでも取得できた場合は、ステップＳ４１２に行く。
【００７７】
（ステップＳ４１２）カウンタｉを１、インクリメントし、ステップＳ４０２に戻る。
【００７８】
（ステップＳ４１３）翻訳規則生成部１１２は、翻訳規則を取得できなかった頂点が有する原言語の単語に対応する目的言語の単語（翻訳語）を単語辞書１０２から取得する。
【００７９】
（ステップＳ４１４）翻訳規則生成部１１２は、頂点を内部頂点とし、頂点のテイルを有する左辺と、左辺に対応する目的言語の文字列であり、目的言語の単語（翻訳語）と、頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する。
【００８０】
（ステップＳ４１５）翻訳規則生成部１１２は、ステップＳ４１４で生成した１以上の翻訳規則をｊ番目以降の翻訳規則とし、ステップＳ４０４に戻る。なお、ｊ番目以降の翻訳規則とする、とは、１以上の翻訳規則に対して、ｊ番目以降のＩＤを付与し、予め決められたバッファに格納することである。なお、バッファに格納された翻訳規則は、ステップＳ４０４において、翻訳規則取得部１１１により用いられる。
【００８１】
次に、ステップＳ２０４の翻訳候補取得処理について、図５のフローチャートを用いて説明する。
【００８２】
（ステップＳ５０１）翻訳候補取得部１１５は、カウンタｉに１を代入する。
【００８３】
（ステップＳ５０２）翻訳候補取得部１１５は、翻訳森の中に、ｉ番目の頂点が存在するか否かを判断する。ｉ番目の頂点が存在すればステップＳ５０３に行き、存在しなければ上位処理（ステップＳ２０６）にリターンする。
【００８４】
（ステップＳ５０３）翻訳候補取得部１１５は、翻訳森のｉ番目の頂点に対応する１以上の各超辺が有する１以上の翻訳規則の右辺を取得する。
【００８５】
（ステップＳ５０４）翻訳候補取得部１１５は、カウンタｊに１を代入する。
【００８６】
（ステップＳ５０５）翻訳候補取得部１１５は、ステップＳ５０３で取得した１以上の翻訳規則の右辺のうち、ｊ番目の右辺が存在するか否かを判断する。ｊ番目の右辺が存在すればステップＳ５０６に行き、存在しなければステップＳ５１１に行く。
【００８７】
（ステップＳ５０６）翻訳候補取得部１１５は、カウンタｋに１を代入する。
【００８８】
（ステップＳ５０７）翻訳候補取得部１１５は、ｊ番目の右辺の中に、ｋ番目の変数が存在するか否かを判断する。ｋ番目の変数が存在すればステップＳ５０８に行き、存在しなければステップＳ５１０に行く。
【００８９】
（ステップＳ５０８）翻訳候補取得部１１５は、ｊ番目の右辺のｋ番目の変数に翻訳語等を代入する処理である変数代入処理を実行する。変数代入処理について、図６のフローチャートを用いて説明する。
【００９０】
（ステップＳ５０９）翻訳候補取得部１１５は、カウンタｋを１、インクリメントし、ステップＳ５０７に戻る。
【００９１】
（ステップＳ５１０）翻訳候補取得部１１５は、カウンタｊを１、インクリメントし、ステップＳ５０５に戻る。
【００９２】
（ステップＳ５１１）翻訳候補取得部１１５は、カウンタｉを１、インクリメントし、ステップＳ５０２に戻る。
【００９３】
次に、ステップＳ５０８の変数代入処理について、図６のフローチャートを用いて説明する。
【００９４】
（ステップＳ６０１）翻訳候補取得部１１５は、変数に対応するすべての翻訳規則の右辺を取得する。
【００９５】
（ステップＳ６０２）翻訳候補取得部１１５は、カウンタｌに１を代入する。
【００９６】
（ステップＳ６０３）翻訳候補取得部１１５は、ステップＳ６０１で取得した右辺のうち、ｌ番目の右辺が存在するか否かを判断する。ｌ番目の右辺が存在すれば、存在しなければ上位処理（ステップＳ５０９）にリターンする。
【００９７】
（ステップＳ６０４）翻訳候補取得部１１５は、ｌ番目の右辺を変数に代入する。
【００９８】
（ステップＳ６０５）翻訳候補取得部１１５は、カウンタｍに１を代入する。
【００９９】
（ステップＳ６０６）翻訳候補取得部１１５は、変数に代入したｌ番目の右辺に、ｍ番目の変数が存在するか否かを判断する。ｍ番目の変数が存在すればステップＳ６０７に行き、存在しなければステップＳ６０９に行く。
【０１００】
（ステップＳ６０７）翻訳候補取得部１１５は、変数代入処理を行う。つまり、変数代入処理は再帰的に行われる。
【０１０１】
（ステップＳ６０８）翻訳候補取得部１１５は、カウンタｍを１、インクリメントし、ステップ６０６に戻る。
【０１０２】
（ステップＳ６０９）翻訳候補取得部１１５は、カウンタｌを１、インクリメントし、ステップ６０３に戻る。
【０１０３】
以下、本実施の形態における機械翻訳装置１の具体的な動作について説明する。今、機械翻訳装置１は、例えば、英日翻訳を行う装置である、とする。つまり、例えば、原言語は英語、目的言語は日本語である、とする。
【０１０４】
また、対訳コーパス１０１には、英語の文と日本語の文とを有する多数の対訳文が格納されている、とする。そして、単語辞書１０２にも、英語と日本語の多数の単語対が格納されている。
【０１０５】
そして、上述したように、ルールマッチングの手法（例えば、ＧＨＫＭアルゴリズム等）により、翻訳規則が生成され、多数の翻訳規則が、翻訳規則格納部１０５に格納されている。翻訳規則格納部１０５に格納されている翻訳規則の例を、図７に示す。
【０１０６】
なお、図７において、翻訳規則が有するスコアは省略している。また、例えば、スコア算出部１１０は、翻訳規則が有するスコアを、以下のように算出する。スコア算出部１１０は、例えば、各規則の出現頻度の期待値を算出する。スコア算出部１１０は、例えば、以下の数式３から数式７を格納しており、かかる数式を用いて、各規則の出現頻度の期待値を算出する。
【０１０７】
まず、スコア算出部１１０は、数式３を用いて、翻訳規則の右辺が、着目する翻訳規則の右辺である場合、当該翻訳規則が着目する翻訳規則である確率値を算出する。
【０１０８】
また、スコア算出部１１０は、数式４を用いて、翻訳規則の左辺が、着目する翻訳規則の左辺である場合、当該翻訳規則が着目する翻訳規則である確率値を算出する。
【０１０９】
また、スコア算出部１１０は、数式５を用いて、翻訳規則の左辺のｒｏｏｔが、着目する翻訳規則の左辺のｒｏｏｔである場合、当該翻訳規則が着目する翻訳規則である確率値を算出する。なお、左辺のｒｏｏｔとは、係り受け森上の左辺のｒｏｏｔである。
【数３】
【数４】
【数５】
【０１１０】
ここで数式３から５において、ｒは翻訳規則、ｃ（ｒ）は翻訳規則ｒの出現頻度である。なお、ここでの出現頻度において、スコア算出部１１０は、単純に出現を１回と数えるのではなく、内側外側アルゴリズムを用いて、係り受け解析における尤度最大化に基づいた頻度の期待値を計算することは好適である。頂点ｖに対する外側確率をα（ｖ）、内側確率をβ（ｖ）とすると、スコア算出部１１０は、ある翻訳規則ｒに対する内側外側確率αβ（ｖ）を、数式６を用いて計算する。
【数６】
【０１１１】
そして、スコア算出部１１０は、翻訳規則ｒにおける出現頻度の期待値を、数式７を用いて算出する。数式７において、ＴＯＰは係り受け森上のｒｏｏｔを示している。また、ここでは、出現頻度の期待値は、翻訳規則のスコアとなる、とする。
【数７】
【０１１２】
以上により、スコアを有する１以上の翻訳規則が、翻訳規則格納部１０５に格納された。
【０１１３】
なお、統計的機械翻訳では、スコアの算出のために、対数線形モデルを用いることが好適である。対数線形モデルは、複数の素性を重みで線形結合した形で表される。素性に対する重みは与えられた訓練データ上で翻訳の評価尺度(BLEUなど)を最大化するように学習される。この学習法は誤り率最小化学習法(MERT)と呼ばれており、公知技術であるので、説明を省略する。なお、素性は、例えば、両方向からの単語翻訳確率、翻訳規則に関する確率（数式３、数式４、数式５により算出される確率値）、係り受け解析スコア、N-gram言語モデル、単語数、規則数などである。
【０１１４】
かかる状況において、機械翻訳装置１は、原言語文「I saw a girl with a telesscope」を受け付けた、とする。
【０１１５】
次に、係り受け解析部１０６は、原言語文「I saw a girl with a telesscope」に対して、MST parserを利用して、Eisnerのアルゴリズムにより、係り受け解析を行い、係り受け森を取得する。なお、取得した係り受け森は、例えば、図１０である。図１０の係り受け森は、図８に示す係り受け１、および図９に示す係り受け２により構成されている森である。つまり、図１０の係り受け森は、係り受け１と係り受け２とで、同一の頂点「Ｉ０，１」「ａ２，３」「ａ５，６」「ｔｅｌｅｓｃｏｐｅ５，７」「ｗｉｔｈ４，７」「ｓａｗ０，７」を共通化した図１０の係り受け森である。係り受け解析部１０６は、かかる係り受け森を取得し、係り受け森格納部１０４に、少なくとも一時蓄積する。
【０１１６】
なお、超辺構成部１０８が、図１０の係り受け森に対して、以下に説明するバイナリゼーション（ｂｉｎａｒｉｚａｔｉｏｎ）を行うことは好適である。機械翻訳装置１において、係り受け森から翻訳規則の抽出やデコードを行うことになるが、ある超辺が持つテイルの数が多くなると、翻訳規則の質やデコードの効率に問題が生じる。そこで、係り受け森をバイナリゼーションし、超辺が持つテイルの数に制限を加えることは好適である。ここで、バイナリゼーションとは超辺のテイルのサイズが２以下であるようにすることである。バイナリゼーションは、ある超辺が持つテイルのサイズが３以上である場合、最も左の要素とその次の要素をヘッドから生成する擬似的な頂点をヘッドとした新たな超辺のテイルとして構成し直すという作業を再帰的に行うことである。例として、図１０における超辺ｅ１に対してこの操作を行うと、図１１のようにｓａｗ＃２；７を擬似的なｈｅａｄとした新たな超辺が再構成されることになる。係り受け森のｒｏｏｔからトップダウンに各頂点を訪れてこの操作を行うことで、係り受け森をバイナリゼーションすることができる。
【０１１７】
次に、翻訳規則取得部１１１は、係り受け森格納部１０４に格納された図１０の係り受け森を読み出す。
【０１１８】
そして、翻訳規則取得部１１１等は、図７の翻訳規則を用いて、以下のように、翻訳森を構成する。ここで、説明の簡単化のため、図１０の係り受け森の一部である、図１２の係り受けに対して、図７の翻訳規則を用いて翻訳森を構成する処理を説明する。なお、図１０の係り受け森に対しても、以下で説明する同様の処理により、翻訳森を構成できることは言うまでもない。
【０１１９】
翻訳規則取得部１１１は、図１２の頂点のうち、「Ｉ０，１」を読み出す。そして、翻訳規則取得部１１１は、頂点「Ｉ０，１」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「Ｉ → 私」「Ｉ → 私は」を取得する。次に、超辺取得部１１３は、翻訳規則「Ｉ → 私」「Ｉ → 私は」の右辺「私」「私は」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。そして、翻訳森取得部１１４は、図１３に示す一時的な翻訳森を得る。なお、翻訳森取得部１１４は、係り受けの頂点「Ｉ０，１」のスパンを、そのまま翻訳森の頂点のスパンとして使用する。つまり、翻訳森取得部１１４は、頂点「Ｉ０，１」のスパンを取得し、翻訳森の頂点のスパンとして書き込む。
【０１２０】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ａ２，３」を読み出す。そして、翻訳規則取得部１１１は、頂点「ａ２，３」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「ａ → 一つ」を取得する。次に、超辺取得部１１３は、翻訳規則「ａ → 一つ」の右辺「一つ」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。
【０１２１】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ａ５，６」を読み出す。そして、翻訳規則取得部１１１は、頂点「ａ５，６」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「ａ → 一つ」を取得する。次に、超辺取得部１１３は、翻訳規則「ａ → 一つ」の右辺「一つ」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。そして、この段階で、翻訳森取得部１１４は、図１４に示す一時的な翻訳森を得る。
【０１２２】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ｔｅｌｅｓｃｏｐｅ５，７」を読み出す。そして、翻訳規則取得部１１１は、頂点「ｔｅｌｅｓｃｏｐｅ５，７」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「ａ→ｔｅｌｅｓｃｏｐｅ → 望遠鏡」（図７のＩＤ＝４の規則）、「ｘ１→ｔｅｌｅｓｃｏｐｅ → 望遠鏡ｘ１」（図７のＩＤ＝５の規則）を取得する。次に、超辺取得部１１３は、翻訳規則「ａ→ｔｅｌｅｓｃｏｐｅ → 望遠鏡」の右辺「望遠鏡」を有する超辺、および翻訳規則「ｘ１→ｔｅｌｅｓｃｏｐｅ → 望遠鏡ｘ１」の右辺「望遠鏡ｘ１」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された２つの超辺を、予め決められたバッファに追記する。そして、この段階で、翻訳森取得部１１４は、図１５に示す一時的な翻訳森を得る。
【０１２３】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ｗｉｔｈ４，７」を読み出す。そして、翻訳規則取得部１１１は、頂点「ｗｉｔｈ４，７」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「ｘ１→ｗｉｔｈ → ｘ１を持った」（図７のＩＤ＝６の規則）を取得する。次に、超辺取得部１１３は、翻訳規則「ｘ１→ｗｉｔｈ → ｘ１を持った」の右辺「ｘ１を持った」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。そして、この段階で、翻訳森取得部１１４は、図１６に示す一時的な翻訳森を得る。
【０１２４】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ｓａｗ０，７」を読み出す。そして、翻訳規則取得部１１１は、頂点「ｓａｗ０，７」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、図７のＩＤ＝７の翻訳規則を取得する。次に、超辺取得部１１３は、図７のＩＤ＝７の翻訳規則の右辺「ｘ１はｘ２少女を見た」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。そして、翻訳森取得部１１４は、図１７に示す翻訳森を得る。なお、図１７の最終的な翻訳森において、頂点「ａ２，３」を使う森は生成されない。他の頂点と連結しないからである。
【０１２５】
なお、係り受け森を翻訳森へと変換する際、ある頂点に適用できる翻訳規則がない場合、翻訳規則生成部１１２は、疑似的な翻訳森の超辺を生成することは好適である。
【０１２６】
例えば、図１０における頂点（ｓａｗ０，７）の超辺ｅ１に対して、疑似的な翻訳規則を生成することを考える。この場合、翻訳規則生成部１１２は、ｓａｗという単語に対する訳語を単語辞書１０２から辞書引きし、"見た"という単語を得たとする。なお、単語辞書１０２は、ＧＩＺＡ＋＋で学習した翻訳ｔａｂｌｅ（D. Yuan and P. Martha. Machine translation using prob-abilistic synchronous dependency insertion grammars. In ACL, 2005.参照）であることは好適である。
【０１２７】
そして、翻訳規則生成部１１２は、頂点（ｓａｗ０，７）を内部頂点とし、頂点のテイルを有する左辺と、左辺に対応する目的言語の文字列"見た"であり、目的言語の単語"見た"と、頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する。つまり、翻訳規則生成部１１２は、例えば、「＜（ｉ０，１，ｇｉｒｌ２，４，ｗｉｔｈ４，７），ｓａｗ０，７， ｘ１見たｘ２ｘ３＞」という超辺（翻訳規則）を作り出す。
【０１２８】
なお、この規則では出力側言語の並びが考慮されておらず、翻訳精度の悪化をまねく危険性がある。そのため、binarizationを行った場合にのみ、変数（ｂｉｎａｒｉｚａｔｉｏｎ時は多くても２つ）と訳語の並べ方最大６通りを考慮して翻訳森の超辺を生成することは好適である。なお、デコードは、前述したようにlazyな操作とHuang05（L. Huang and D. Chiang. Better k-best parsing. In Pro-ceedings of IWPT, pages 53-64, October 2005.参照）のalgorithm2における超辺の一括処理を行うことは好適である。最大で６つの翻訳規則を生成したとしても効率良く動作するからである。また、binarizationを行っていない場合、出力言語側のあらゆる並びを考慮することは超辺のｔａｉｌサイズが大きくなることがあるため現実的に実行が困難である。つまり、binarizationを行うことは極めて好適である。
【０１２９】
次に、翻訳候補取得部１１５は、図１７の翻訳森を用いて、以下のように翻訳候補を取得する。翻訳候補取得部１１５は、図１７の翻訳森の頂点をボトムアップに訪れながら、超辺に付与した翻訳規則の右辺を使って翻訳候補を作り出す。この際、通常、作り出される仮説は膨大な数に及ぶため、翻訳候補取得部１１５は、ビームサーチを用いることは好適である。なお、ビームサーチは公知技術なので、説明を省略する。また、翻訳候補取得部１１５は、部分的な翻訳候補を組み合わせる際にlazyな操作を行うことで探索の効率化を行うことは好適である。ビームサーチとlazyな操作を行いながら探索する手法は、cube pruning と呼ばれており、公知技術である（D. Chiang. Hierachical phrase-based translation. Compu-tational Linguitics, 33:201-228, 2007.参照）。なお、このcube pruningを1-bestの翻訳結果を得るために用いることは好適である。モデルの訓練を行うためのK-best出力ではcube pruningを全頂点で1-bestを見つけるために動作させた後、Huang05（L. Huang and D. Chiang. Better k-best parsing. In Pro-ceedings of IWPT, pages 53-64, October 2005.参照）で提案されているアルゴリズム３によって高速にK-bestの探索を行うことは好適である。
【０１３０】
さらに具体的には、翻訳候補取得部１１５は、図１７の翻訳森の頂点「Ｉ０，１」に対応する超辺が有する１以上の翻訳規則の右辺「私」「私は」を取得する。
【０１３１】
また、翻訳候補取得部１１５は、図１７の翻訳森の頂点「ａ５，６」に対応する超辺が有する翻訳規則の右辺「一つ」を取得する。
【０１３２】
また、翻訳候補取得部１１５は、図１７の翻訳森の頂点「ｔｅｌｅｓｃｏｐｅ５，７」に対応する超辺が有する翻訳規則の右辺「望遠鏡」「望遠鏡ｘ１」を取得する。次に、翻訳候補取得部１１５は、変数「ｘ１」に「一つ」を代入する。そして、翻訳候補取得部１１５は、「望遠鏡」、「望遠鏡一つ」を得る。
【０１３３】
次に、翻訳候補取得部１１５は、図１７の翻訳森の頂点「ｗｉｔｈ４，７」に対応する超辺が有する翻訳規則の右辺「ｔｅｌｅｓｃｏｐｅ５，７を持った」を得る。そして、翻訳候補取得部１１５は、「ｔｅｌｅｓｃｏｐｅ５，７」に対応する「望遠鏡」、「望遠鏡一つ」を右辺「ｔｅｌｅｓｃｏｐｅ５，７を持った」に代入し、「望遠鏡を持った」、「望遠鏡一つを持った」を得る。
【０１３４】
次に、翻訳候補取得部１１５は、図１７の翻訳森の頂点ｓａｗ０，７」に対応する超辺が有する翻訳規則の右辺「Ｉ０，１はｗｉｔｈ４，７少女を見た」を得る。そして、翻訳候補取得部１１５は、右辺「Ｉ０，１はｗｉｔｈ４，７少女を見た」の「Ｉ０，１」に対して、「私」「私は」を代入し、右辺「Ｉ０，１はｗｉｔｈ４，７少女を見た」「ｗｉｔｈ４，７」に対して、「望遠鏡を持った」、「望遠鏡一つを持った」を代入する。そして、翻訳候補取得部１１５は、「私は望遠鏡を持った少女を見た」「私は望遠鏡一つを持った少女を見た」「私はは望遠鏡を持った少女を見た」「私はは望遠鏡一つを持った少女を見た」を得る。
【０１３５】
次に、翻訳結果取得部１１６は、取得された４つの翻訳候補から、翻訳規則のスコアを用いて、一の翻訳候補「私は望遠鏡を持った少女を見た」を選択する。この「私は望遠鏡を持った少女を見た」が翻訳結果である。なお、４つの翻訳候補から一の翻訳結果を取得する方法は種々あり、公知技術であるので、詳細な説明は省略する。
【０１３６】
次に、出力部１１７は、取得された翻訳結果「私は望遠鏡を持った少女を見た」を出力する。
【０１３７】
以下、機械翻訳装置１の実験結果について説明する。
（実験）
【０１３８】
本実験では、中国語から英語への翻訳で実験を行った。対訳コーパスには、新聞データから作成されたＦＢＩＳコーパスを用いた。中英それぞれ単語数３．５Ｍ，４．３Ｍである。翻訳モデルの学習にはＧＩＺＡ＋＋を用いた。また、言語モデル学習用のデータとしてｅｎｇｌｉｓｈ ｇｉｇａ ｗｏｒｄのｘｉｎｈｕａ部分のデータ（単語数３５０Ｍ）を利用した。Ｎ−ｇｒａｍの学習はｓｒｉｌｍを用いて４−ｇｒａｍ言語モデルを学習した。この翻訳実験ではＮＩＳＴ２００２／２００３Ｏｐｅｎ Ｍａｃｈｉｎｅ Ｔｒａｎｓｌａｔｉｏｎ Ｅｖａｌｕａｔｉｏｎの中英翻訳データを用意し、２００２をＭＥＲＴ、２００３をテストデータとして用いた。中国語の形態素解析にはｓｔａｎｆｏｒｄ ｓｅｇｍｅｎｔｅｒとｓｔａｎｆｏｒｄ ｐｏｓｔａｇｇｅｒを利用した。英語のトークナイゼイションには英語ツリーバンクの処理に使われたツールを用いた。中国語の係り受け解析は１−ｓｔ ｏｒｄｅｒのＥｉｓｎｅｒアルゴリズムによって行った。
【０１３９】
また、ここでは中国語ツリーバンクの全１８，４７２文からｃｔｖ（報道）部分５００文とｃｈｔｂ（新聞）部分５００文を除いたデータ（ａｌｌ）とｃｈｔｂ部分８９８１文から共通のｃｈｔｂ部分５００文を除いたデータ（ｎｅｗｓ）とを用いて２つの係り受け解析モデルを構築した（係り受けフォーマットへはＰｅｎｎ２Ｍａｌｔを用いて変換）。除いたデータはテストデータとして利用した。
【０１４０】
図１８は、係り受け解析の精度（ｕｎｌａｂｅｌｅｄ ａｃｃｕｒａｃｙ）を示す。この結果からは、新聞データをドメインとする解析を行う場合，新聞データのみから学習したモデルを用いる方が良いことがわかる。よって、以下の翻訳実験では新聞をドメインとするデータを用いるため、全新聞データ８９８１文から学習したモデルを用いた。
【０１４１】
機械翻訳装置１で用いる素性は、両方向からの単語翻訳確率、翻訳規則に関する確率（数式３、数式４、数式５により算出される確率値）、係り受け解析スコア、N-gram言語モデル、単語数、規則数の計９つとした。これらの素性に対する対数線形モデルの重みはMERTでBLEUを最大化するように学習した。図１９は、本実験における係り受け森のK-best数と翻訳規則数の関係を示している。また、図１９では、１つの翻訳規則が持つ平均の変数の数も示している。翻訳規則が持つ変数の数は少ない方が効率良くデコードを行うことができる。結果からは、バイナリゼーションには変数の数を減らす効果があると言えるが、その一方で規則の数は大きく増加した。以下の翻訳実験では、テストデータや訓練データに対して使われることのない規則は削除した。機械翻訳装置１との比較には、句に基づくデコーダmosesと階層句に基づくデコーダjoshuaを用いた。対数線形モデルの重み訓練時のK-best数は各システム共に2000-best出力した。また、デコード時の翻訳候補K-best数は、各システム共に500-bestとした。図２０にBLEUによる翻訳精度の差を示す。ここでは、10-bestの係り受け森を用いて抽出した翻訳規則を使って翻訳実験を行った。実験結果から、機械翻訳装置１は、階層句や句に基づいたシステムとほぼ同等の性能を示すことができたが、翻訳精度の著しい向上は得られなかった。しかし、これは、係り受けは単語で超グラフの頂点が表されるため、翻訳規則の適用を行う際、未知語などの影響を大きく受け易いからである。そして、機械翻訳装置１では、森によるアプローチとバイナリゼーションによってこの問題を緩和させることができる。
【０１４２】
以上、本実施の形態によれば、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる。
【０１４３】
また、本実施の形態によれば、複数の依存構造解析結果を、ノードを共有することによりコンパクトに表現した、係り受け森からの翻訳を実現することにより、解析の曖昧性や誤りによるゆらぎを排除することが可能となった。具体的には、翻訳ルールの抽出時に解析の曖昧性を考慮して網羅的に列挙することが可能となり、さらに、翻訳時には解析誤りに対しても翻訳ルールを適用することが可能となった。
【０１４４】
なお、本実施の形態における技術は、音声翻訳、文書翻訳などの機械翻訳分野に適用できる。
【０１４５】
また、本実施の形態における処理は、ソフトウェアで実現しても良い。そして、このソフトウェアをソフトウェアダウンロード等により配布しても良い。また、このソフトウェアをＣＤ−ＲＯＭなどの記録媒体に記録して流布しても良い。なお、このことは、本明細書における他の実施の形態においても該当する。
【０１４６】
また、図２１は、本明細書で述べた機械翻訳装置を実現するコンピュータの外観を示す。上述の実施の形態は、コンピュータハードウェア及びその上で実行されるコンピュータプログラムで実現され得る。図２１は、このコンピュータシステム３４０の概観図であり、図２２は、コンピュータシステム３４０の内部構成を示す図である。
【０１４７】
図２１において、コンピュータシステム３４０は、ＦＤドライブ３４１１、ＣＤ−ＲＯＭドライブ３４１２を含むコンピュータ３４１と、キーボード３４２と、マウス３４３と、モニタ３４４とを含む。
【０１４８】
図２２において、コンピュータ３４１は、ＦＤドライブ３４１１、ＣＤ−ＲＯＭドライブ３４１２に加えて、ＭＰＵ３４１３と、ＣＤ−ＲＯＭドライブ３４１２及びＦＤドライブ３４１１に接続されたバス３４１４と、ブートアッププログラム等のプログラムを記憶するためのＲＯＭ３４１５とに接続され、アプリケーションプログラムの命令を一時的に記憶するとともに一時記憶空間を提供するためのＲＡＭ３４１６と、アプリケーションプログラム、システムプログラム、及びデータを記憶するためのハードディスク３４１７とを含む。ここでは、図示しないが、コンピュータ３４１は、さらに、ＬＡＮへの接続を提供するネットワークカードを含んでも良い。
【０１４９】
コンピュータシステム３４０に、上述した実施の形態の機械翻訳装置の機能を実行させるプログラムは、ＣＤ−ＲＯＭ３５０１、またはＦＤ３５０２に記憶されて、ＣＤ−ＲＯＭドライブ３４１２またはＦＤドライブ３４１１に挿入され、さらにハードディスク３４１７に転送されても良い。これに代えて、プログラムは、図示しないネットワークを介してコンピュータ３４１に送信され、ハードディスク３４１７に記憶されても良い。プログラムは実行の際にＲＡＭ３４１６にロードされる。プログラムは、ＣＤ−ＲＯＭ３５０１、ＦＤ３５０２またはネットワークから直接、ロードされても良い。
【０１５０】
プログラムは、コンピュータ３４１に、上述した実施の形態の機械翻訳装置の機能を実行させるオペレーティングシステム（ＯＳ）、またはサードパーティープログラム等は、必ずしも含まなくても良い。プログラムは、制御された態様で適切な機能（モジュール）を呼び出し、所望の結果が得られるようにする命令の部分のみを含んでいれば良い。コンピュータシステム３４０がどのように動作するかは周知であり、詳細な説明は省略する。
【０１５１】
また、上記各実施の形態において、各処理（各機能）は、単一の装置（システム）によって集中処理されることによって実現されてもよく、あるいは、複数の装置によって分散処理されることによって実現されてもよい。
【０１５２】
本発明は、以上の実施の形態に限定されることなく、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【０１５３】
以上のように、本発明にかかる機械翻訳装置は、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる、という効果を有し、機械翻訳装置等として有用である。
【符号の説明】
【０１５４】
１ 機械翻訳装置
１０１ 対訳コーパス
１０２ 単語辞書
１０４ 係り受け森格納部
１０５ 翻訳規則格納部
１０６ 係り受け解析部
１０７ 翻訳規則抽出部
１０８ 超辺構成部
１０９ 出現頻度取得部
１１０ スコア算出部
１１１ 翻訳規則取得部
１１２ 翻訳規則生成部
１１３ 超辺取得部
１１４ 翻訳森取得部
１１５ 翻訳候補取得部
１１６ 翻訳結果取得部
１１７ 出力部
【技術分野】
【０００１】
本発明は、係り受け森を入力とする機械翻訳装置等に関するものである。
【背景技術】
【０００２】
従来、統計的機械翻訳では、構文情報を利用することによる翻訳精度の向上が図られてきた。例えば、非特許文献１では、入力を文字列、出力を構文木にするのに対し、非特許文献２は構文木を入力として文字列を出力している。さらに、非特許文献２では構文解析の間違いや曖昧性を解消するため、複数の解析結果をコンパクトに表現できる圧縮統語森を入力としている。このように、木あるいは森を入出力とした手法では句構造解析が用いられてきた。しかし、句構造では、例えば日本語など自由な語順をとる言語の解析は困難であり、また解析の曖昧性が生じやすい。これに対し、係り受けと呼ばれる依存構造を用いる手法が提案され、例えば、非特許文献３では入出力ともに依存構造であるのに対し、非特許文献４は入力を文字列、出力に依存構造を使用、非特許文献５や６では、入力を句構造、出力に依存構造を使用している。この係り受けでは単語間の依存構造によって文の構造が表現され、句構造での問題が生じにくい。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What's in a translation rule? In Proceedings of HLT-NAACL, pages 273-280.
【非特許文献２】Haitao Mi, Liang Huang, and Qun Liu. 2008. Forest- based translation. In Proceedings of ACL: HLT, Columbus, OH.
【非特許文献３】Yuan Ding and Martha Palmer. 2005. Machine translation using probablisitic synchronous dependency insertion grammars. In Proceedings of the 43rd ACL, Ann Arbor, MI.
【非特許文献４】A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model . 2008. Libin Shen, Jinxi Xu and Ralph Weischedelin Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL).
【非特許文献５】Haitao Mi and Qun Liu. 2010. Constituency to Dependency Translation with Forests. In Proceedings of ACL.
【非特許文献６】Zhaopeng Tu, Yang Liu, Young-Sook Hwang, Qun Liu and Shouxun Lin. 2010. Dependency Forest for Statistical Machine Translation. In Proceedings COLING.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、例えば、非特許文献３に係る技術は、入出力ともに依存構造をとり、モデルがスパースになる問題があり、精度の高い機械翻訳ができなかった。また、非特許文献４から６では、出力に依存構造を使用しているが、これは単に制約として用いており、依存構造解析の利点である曖昧性の少なさを生かしていないために、精度の高い機械翻訳ができなかった。
【課題を解決するための手段】
【０００５】
本第一の発明の機械翻訳装置は、原言語の文を係り受け解析して取得された２以上の係り受けであり、原言語の文を構成する単語とスパンとを含む２以上の頂点を有する２以上の係り受けのうち、同一である内部頂点を共通化し、構成された係り受け森を格納し得る係り受け森格納部と、原言語の係り受けの部分木であり、部分木の内部頂点は単語であり、内部頂点以外の頂点は単語か変数をとる部分木である左辺と、左辺に対応する目的言語の文字列であり、単語と変数を有する文字列である右辺とを対応付けて有し、かつスコアを有する１以上の翻訳規則を格納し得る翻訳規則格納部と、原言語の単語と目的言語の単語とを対応付けた情報である１以上の単語対を格納し得る単語辞書と、係り受け森を構成する各頂点に対して、翻訳規則格納部の１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する翻訳規則取得部と、係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する超辺取得部と、係り受け森を構成する全頂点と、超辺取得部が取得した１以上の超辺とを有する翻訳森を取得する翻訳森取得部と、翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と、単語辞書とを用いて、１以上の翻訳候補を取得する翻訳候補取得部と、翻訳候補取得部が取得した１以上の翻訳候補のうち、いずれか１以上の翻訳候補である翻訳結果を出力する出力部とを具備する機械翻訳装置である。
【０００６】
かかる構成により、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる。
【０００７】
また、本第二の発明の機械翻訳装置は、第一の発明に対して、原言語の文と目的言語の文とを有する１以上の対訳文を有する対訳コーパスと、対訳コーパスにおいて、１以上の各翻訳規則の出現頻度を取得する出現頻度取得部と、各翻訳規則の出現頻度を用いて、スコアを算出するスコア算出部とをさらに具備し、翻訳規則が有するスコアは、スコア算出部が算出したスコアである機械翻訳装置である。
【０００８】
かかる構成により、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる。
【０００９】
また、本第三の発明の機械翻訳装置は、第一または第二の発明に対して、翻訳規則取得部が、係り受け森を構成する頂点に対する翻訳規則を取得できなかった場合、翻訳規則を取得できなかった頂点が有する原言語の単語に対応する目的言語の単語を単語辞書から取得し、頂点を内部頂点とし、頂点のテイルを有する左辺と、左辺に対応する目的言語の文字列であり、目的言語の単語と、頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する翻訳規則生成部をさらに具備し、翻訳規則取得部は、係り受け森を構成する各頂点に対して、翻訳規則生成部が生成した１以上の翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する機械翻訳装置である。
【００１０】
かかる構成により、さらに精度の高い機械翻訳が可能となる。
【００１１】
また、本第四の発明の機械翻訳装置は、第一から第三いずれかの発明に対して、係り受け森が有する各超辺のテイルの数が３以上である場合に、超辺のテイルの数が２以下となるように、超辺の一のテイルと超辺の他の一のテイルの擬似的なヘッドであり、一のテイルと他の一のテイルの元のヘッドのテイルとなるヘッドを生成し、新たな超辺を構成する超辺構成部をさらに具備し、係り受け森格納部の係り受け森は、超辺構成部が構成した新たな超辺を含む係り受け森である機械翻訳装置である。
【００１２】
かかる構成により、さらに精度の高い機械翻訳が可能となる。
【発明の効果】
【００１３】
本発明による機械翻訳装置によれば、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる。
【図面の簡単な説明】
【００１４】
【図１】実施の形態１における機械翻訳装置のブロック図
【図２】実施の形態１における機械翻訳装置の動作について説明するフローチャート
【図３】実施の形態１における係り受け森構成処理の動作について説明するフローチャート
【図４】実施の形態１における翻訳森構成処理の動作について説明するフローチャート
【図５】実施の形態１における翻訳候補取得処理の動作について説明するフローチャート
【図６】実施の形態１における変数代入処理の動作について説明するフローチャート
【図７】実施の形態１における翻訳規則格納部に格納されている翻訳規則の例を示す図
【図８】実施の形態１における係り受けの例を示す図
【図９】実施の形態１における係り受けの例を示す図
【図１０】実施の形態１における係り受け森の例を示す図
【図１１】実施の形態１におけるバイナリゼーションを説明する図
【図１２】実施の形態１における係り受けの例を示す図
【図１３】実施の形態１における一時的な翻訳森の例を示す図
【図１４】実施の形態１における一時的な翻訳森の例を示す図
【図１５】実施の形態１における一時的な翻訳森の例を示す図
【図１６】実施の形態１における一時的な翻訳森の例を示す図
【図１７】実施の形態１における最終的な翻訳森の例を示す図
【図１８】実施の形態１における係り受け解析の精度を示す図
【図１９】実施の形態１における係り受け森のＫ−ｂｅｓｔ数と翻訳規則数の関係を示す図
【図２０】実施の形態１におけるＢＬＥＵによる翻訳精度の差を示す図
【図２１】実施の形態１におけるコンピュータシステムの概観図
【図２２】実施の形態１におけるコンピュータシステムのブロック図
【発明を実施するための形態】
【００１５】
以下、機械翻訳装置等の実施形態について図面を参照して説明する。なお、実施の形態において同じ符号を付した構成要素は同様の動作を行うので、再度の説明を省略する場合がある。
【００１６】
（実施の形態１）
本実施の形態において、係り受け森を入力とする統計的機械翻訳を行う機械翻訳装置について説明する。機械翻訳装置は、２以上の係り受けから係り受け森を自動取得できる。また、機械翻訳装置は、翻訳規則に関する確率値を素性として取得し、当該素性をパラメータとする算出式により、翻訳規則のスコアを算出する。さらに、機械翻訳装置は、係り受け森の頂点に適用できる翻訳規則が無い場合、擬似的な超辺を生成する。
【００１７】
図１は、本実施の形態における機械翻訳装置１のブロック図である。機械翻訳装置１は、対訳コーパス１０１、単語辞書１０２、係り受け森格納部１０４、翻訳規則格納部１０５、係り受け解析部１０６、翻訳規則抽出部１０７、超辺構成部１０８、出現頻度取得部１０９、スコア算出部１１０、翻訳規則取得部１１１、翻訳規則生成部１１２、超辺取得部１１３、翻訳森取得部１１４、翻訳候補取得部１１５、翻訳結果取得部１１６、および出力部１１７を備える。
【００１８】
対訳コーパス１０１は、１以上の対訳文を有する。対訳文は、原言語の文と目的言語の文とを有する。
【００１９】
単語辞書１０２は、１以上の単語対を格納し得る。単語対とは、原言語の単語と目的言語の単語とを対応付けた情報である。
【００２０】
係り受け森格納部１０４は、係り受け森を格納し得る。係り受け森とは、２以上の係り受けのうち、同一である内部頂点を共通化し、構成された情報である。さらに、簡単に説明すれば、係り受け森は、複数の係り受け木のうち共通する解析部分を共有させて森として表しているものである。なお、係り受け森格納部１０４に格納された係り受け森は、後述する係り受け解析部１０６が取得した係り受け森である。なお、頂点を共通化する処理とは、例えば、リンク先を共通にする処理等であり、その処理方法は問わない。
【００２１】
また、形式的に圧縮された（内部頂点を共通化した）係り受け森Ｆは、頂点の集合Ｖと超辺の集合Ｅを持った＜Ｖ，Ｅ＞と表現できる。そして、文をｗ１：ｌ＝ｗ１・・・ｗｌとした場合、各頂点ｖ（∈Ｖ）は単語ｗ１と単語ｗｌが支配する文内のスパンｉ，ｊからｗｉ，ｊと表現できる。超辺ｅは＜ｔａｉｌｓ（ｅ），ｈｅａｄ（ｅ）＞と定義でき、ｈｅａｄ（ｅ）∈Ｖ，ｔａｉｌｓ（ｅ）∈Ｖ＊である。なお、Ｖ＊は、超辺の集合の列である。超辺ｅ１が、例えば、「ｅ１：＜（ｉ０，１，ｇｉｒｌ２，４，ｗｉｔｈ４，７），ｓａｗ０，７＞とすると、かかる超辺ｅ１は、ｓａｗをヘッド（ｈｅａｄ）に持ち、ｉ，ｇｉｒｌ，ｗｉｔｈをテイル（ｔａｉｌ）に持つ。
【００２２】
また、係り受けは、原言語の文を構成する単語とスパンとを含む２以上の頂点を有する。また、係り受けは、単語(または文節)間の依存関係によって、文の構文構造を表したものである。
【００２３】
また、係り受けの構造は、例えば、以下のような構造である。係り受けは、頂点をスパンが付与された単語とし、一つの単語と複数の単語を結ぶ超辺で定義した超グラフで表現される。なお、超辺とは、一の頂点（ヘッドという。）、および当該ヘッドとリンク関係にある１以上の頂点（テイルという。）を有する情報である。
【００２４】
また、係り受けでは、超グラフ上の超辺に、確率を重みをとして割り当てていても良い。例えば、Ｔｕ１０（Z. Tu, Y. Liu, Y. S. Hwang, Q. Liu, and S. Lin. Depen-dency forest for statistical machine translation. In Pro-ceedings of Coling, pages 1092-1100, August 2010.参照）に従って，各超辺に確率を付与しても良い。Ｔｕ１０の手法では、まず、各超辺の出現回数ｃ（ｅ）に、数式１に示すような正の値を割り当てる。数式１において、ｓ（ｖ１，ｖ２）は、ｖ２をヘッド（ｈｅａｄ）、ｖ１をテイル（ｔａｉｌ）としたときの係り受け解析モデルのスコアを返す公知の関数である。また、数式１において、｜tails(e)｜は、超辺ｅをテイルに有する数である。
【数１】
【００２５】
次に、この回数ｃ（ｅ）に基づいて、超辺の確率ｐ（ｅ）を、数式２を用いて算出しても良い。なお、数式２において、e'は、eとは異なる超辺である。
【数２】
【００２６】
翻訳規則格納部１０５は、１以上の翻訳規則を格納し得る。翻訳規則は、左辺と右辺とを対応付けて有する。また、翻訳規則はスコアを有する、とする。また、翻訳規則の左辺は、原言語の係り受けの部分木である。そして、部分木の内部頂点は単語であり、内部頂点以外の頂点は単語か変数をとる。また、右辺は、左辺に対応する目的言語の文字列であり、単語と変数を有する文字列である。なお、翻訳規則が有するスコアは、スコア算出部１１０が算出したスコアである。翻訳規則格納部１０５の翻訳規則は、例えば、ＧＨＫＭアルゴリズム（M. Galley, J. Graehl, K. Knight, D. Marcu, S. DeNeefe,W.Wang, and I. Thayer. Scalable inference and training of context-rich syntactic translation models. In Proceedings of Coling-ACL, pages 961-968, July 2006.，M. Galley, M. Hopkins, K. Knight, and D. Marcu. What's in a translation rule? In HLT-NAACL, pages 273-280,May 2004.参照）により実現され得る。つまり、翻訳規則の取得方法は公知技術であり、以下のように行われる。ＧＨＫＭアルゴリズムでは最小規則と呼ばれる最小単位の取り出し可能な規則を取り出した後、それらを結合することでより大きな単位の規則を作り出す。この操作によって作り出される規則は結合規則と呼ばれる。この結合規則を取り出す際には規則のサイズや規則数の閾値などを設けることで取り出す規則の大きさや数に制限が設けられる。
【００２７】
係り受け解析部１０６は、原言語の文や句などの係り受け解析（依存構造解析）を行い、係り受け森を取得する。係り受け森を取得する技術は公知技術であるので詳細な説明を省略する。なお、係り受け森の取得は、例えば、MST parser(http://www.seas.upenn.edu/~strctlrn/MSTParser/MSTParser.html参照)を利用して、Eisnerのアルゴリズム(http://www.cs.jhu.edu/~jason/papers/eisner.iwptbook00.pdf参照)により行う。ただし、係り受け解析部１０６は、かかる方法以外の方法により、係り受け森を取得しても良い。また、係り受け解析部１０６は、例えば、図示しない入力手段により入力された原言語の文や句などから係り受け森を取得する。
【００２８】
また、係り受け解析部１０６は、対訳コーパス１０１が有する１以上の原言語の文に対して、係り受け解析を行い、１以上の係り受け森を取得する。かかる係り受け森は、翻訳規則の生成に利用される。
【００２９】
翻訳規則抽出部１０７は、係り受け解析部１０６が対訳コーパス１０１から取得した係り受け森と、目的言語の文の単語列に対して、単語単位のアライメントを取得し、１以上の翻訳規則を取得する。なお、係り受け森と、目的言語の文の単語列に対して、単語単位の対応関係（アライメント）を取得する処理は、例えば、ＧＩＺＡ＋＋により行われる。ＧＩＺＡ＋＋では、IBM Model1〜5を用いて翻訳する言語と目的言語における単語のアライメントの確率値を計算する。そして、確率値が所定以上、大きいアライメントが採用される。また、１以上の翻訳規則を取得する処理は、通常、既存のルールマッチングの手法を用いる（例えば、http://www.aclweb.org/anthology/P/P08/P08-1023.pdf参照）。例えば、１以上の翻訳規則を取得する処理は、ＧＨＫＭアルゴリズムを適用することにより行われる。つまり、係り受け森と、目的言語の文の単語列に対して、単語単位のアライメントを取得し、翻訳規則を取得する処理は公知技術であり、いかなる方法を用いて、行われても良い。さらに、翻訳規則抽出部１０７が利用する係り受け森は、後述する超辺構成部１０８により、超辺のテイルの数が２以下となるように処理された係り受け森であることは好適である。
【００３０】
超辺構成部１０８は、係り受け森が有する各超辺のテイルの数が３以上である場合に、超辺のテイルの数が２以下となるように、超辺の一のテイルと超辺の他の一のテイルの擬似的なヘッドであり、一のテイルと他の一のテイルの元のヘッドのテイルとなるヘッドを生成し、新たな超辺を構成する。なお、超辺構成部１０８が行う処理をバイナリゼーション（ｂｉｎａｒｉｚａｔｉｏｎ）という。機械翻訳装置１において、係り受け森から翻訳規則の抽出やデコードを行うことになるが、ある超辺が持つテイルの数が多くなると、翻訳規則の質やデコードの効率に問題が生じる。そこで、係り受け森をバイナリゼーションし、超辺が持つテイルの数に制限を加えることは好適である。ここで、バイナリゼーションとは超辺のテイルのサイズが２以下であるようにすることである。バイナリゼーションは、ある超辺が持つテイルのサイズが３以上である場合、例えば、最も左の要素とその次の要素をヘッドから生成する擬似的な頂点をヘッドとした新たな超辺のテイルとして構成し直すという作業を再帰的に行うことである。
【００３１】
出現頻度取得部１０９は、対訳コーパス１０１において、１以上の各翻訳規則の出現頻度を取得する。
【００３２】
スコア算出部１１０は、各翻訳規則の出現頻度を用いて、スコアを算出する。スコア算出部１１０は、翻訳規則の出現頻度をパラメータとする算出式を用いて、スコアを算出する。つまり、スコア算出部１１０は、翻訳規則の出現の確率値を用いて、スコアを算出する。なお、スコア算出部１１０は、対数線形モデルを用いて、スコアを算出することが好適である。対数線形モデルは、複数の素性を重みで線形結合した形で表される。素性に対する重みは与えられた訓練データ上で翻訳の評価尺度(BLEUなど)を最大化するように学習される。この学習法は誤り率最小化学習法(MERT)と呼ばれており、公知技術であるので、説明を省略する。また、素性は、両方向からの単語翻訳確率、翻訳規則に関する確率（後述する数式３、数式４、数式５により算出される確率値）、係り受け解析スコア、N-gram言語モデル、単語数、規則数などであることは好適である。ただし、スコアの算出式は問わない。また、スコア算出部１１０は、算出式を予め保持している。
【００３３】
翻訳規則取得部１１１は、係り受け森を構成する各頂点に対して、翻訳規則格納部１０５の１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する。
【００３４】
また、翻訳規則取得部１１１は、係り受け森を構成する頂点に対する翻訳規則を取得できなかった場合、翻訳規則生成部１１２に翻訳規則を生成させ、当該翻訳規則生成部１１２が生成した１以上の翻訳規則を、係り受け森を構成する各頂点に対して、合致する１以上の翻訳規則を取得することは好適である。つまり、翻訳規則取得部１１１は、係り受け森を構成する各頂点に対して、翻訳規則生成部１１２が生成した１以上の翻訳規則と翻訳規則格納部１０５の１以上の各翻訳規則とを適用し、頂点ごとに、合致する１以上の翻訳規則を取得することは好適である。なお、頂点が翻訳規則に合致するとは、翻訳規則の左辺が、頂点または頂点を内部頂点とする超辺と一致することである。または、頂点が翻訳規則に合致するとは、翻訳規則の左辺の変数部分を任意の文字列に合致するとした場合に、頂点または頂点を内部頂点とする超辺に合致することでも良い。
【００３５】
翻訳規則生成部１１２は、翻訳規則取得部１１１が、係り受け森を構成する頂点に対する翻訳規則を取得できなかった場合、翻訳規則を取得できなかった頂点が有する原言語の単語に対応する目的言語の単語を単語辞書１０２から取得し、頂点を内部頂点とし、頂点のテイルを有する左辺と、左辺に対応する目的言語の文字列であり、目的言語の単語と、頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する。なお、翻訳規則の生成方法は、他の方法でも良い。
【００３６】
超辺取得部１１３は、係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する。また、超辺取得部１１３は、超辺に、１以上の各の右辺を付与する。ここでの翻訳規則とは、翻訳規則取得部１１１が取得した翻訳規則である。
【００３７】
翻訳森取得部１１４は、翻訳森を取得する。翻訳森とは、係り受け森を構成する全頂点と、超辺取得部１１３が取得した１以上の超辺とを有する情報である。
【００３８】
翻訳候補取得部１１５は、翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と、単語辞書１０２とを用いて、１以上の翻訳候補を取得する。
【００３９】
翻訳結果取得部１１６は、翻訳候補取得部１１５が取得した１以上の翻訳候補のうち、各翻訳候補に対応する翻訳規則のスコアを用いて、一の翻訳結果を取得する。
【００４０】
出力部１１７は、翻訳候補取得部１１５が取得した１以上の翻訳候補のうち、いずれか１以上の翻訳候補である翻訳結果を出力する。なお、出力部１１７は、翻訳結果取得部１１６が取得した一の翻訳結果を出力することは好適である。ただし、出力部１１７は、翻訳候補取得部１１５が取得した１以上の翻訳候補をすべて出力しても良いし、１以上の翻訳候補のうちの一部を出力しても良い。ここで、出力とは、ディスプレイへの表示、プロジェクターを用いた投影、プリンタでの印字、音出力、外部の装置への送信、記録媒体への蓄積、他の処理装置や他のプログラムなどへの処理結果の引渡しなどを含む概念である。
【００４１】
対訳コーパス１０１、単語辞書１０２、係り受け森格納部１０４、および翻訳規則格納部１０５は、不揮発性の記録媒体が好適であるが、揮発性の記録媒体でも実現可能である。対訳コーパス１０１等に対訳文等が記憶される過程は問わない。例えば、記録媒体を介して対訳文等が対訳コーパス１０１で記憶されるようになってもよく、通信回線等を介して送信された対訳文等が対訳コーパス１０１等で記憶されるようになってもよく、あるいは、入力デバイスを介して入力された対訳文等が対訳コーパス１０１等で記憶されるようになってもよい。
【００４２】
係り受け解析部１０６、翻訳規則抽出部１０７、超辺構成部１０８、出現頻度取得部１０９、スコア算出部１１０、翻訳規則取得部１１１、翻訳規則生成部１１２、超辺取得部１１３、翻訳森取得部１１４、翻訳候補取得部１１５、および翻訳結果取得部１１６は、通常、ＭＰＵやメモリ等から実現され得る。係り受け解析部１０６等の処理手順は、通常、ソフトウェアで実現され、当該ソフトウェアはＲＯＭ等の記録媒体に記録されている。但し、ハードウェア（専用回路）で実現しても良い。
【００４３】
出力部１１７は、ディスプレイやスピーカー等の出力デバイスを含むと考えても含まないと考えても良い。出力部１１７は、出力デバイスのドライバーソフトまたは、出力デバイスのドライバーソフトと出力デバイス等で実現され得る。
【００４４】
次に、機械翻訳装置１の動作について、図２のフローチャートを用いて説明する。なお、図２のフローチャートにおける処理の前に、翻訳規則格納部１０５には、上述したＧＨＫＭアルゴリズム等により、翻訳規則が蓄積された、とする。
【００４５】
（ステップＳ２０１）係り受け森取得部１０７は、係り受け格納部１０３に格納されている２以上の係り受けを読み出す。
【００４６】
（ステップＳ２０２）係り受け森取得部１０７は、ステップＳ２０１で読み出した２以上の係り受けを用いて、係り受け森を構成する。この係り受け森構成処理については、図３のフローチャートを用いて説明する。
【００４７】
（ステップＳ２０３）翻訳規則取得部１１１は、係り受け森格納部１０４の係り受け森を読み出す。
【００４８】
（ステップＳ２０４）翻訳規則取得部１１１等は、係り受け森から翻訳森を構成する。翻訳森構成処理については、図４のフローチャートを用いて説明する。
【００４９】
（ステップＳ２０５）翻訳候補取得部１１５は、ステップＳ２０４で構成された翻訳森を用いて、１以上の翻訳候補を取得する。この翻訳候補取得処理については、図５のフローチャートを用いて説明する。
【００５０】
（ステップＳ２０６）翻訳結果取得部１１６は、ステップＳ２０５で取得された１以上の翻訳候補から、一の翻訳候補を選択する。かかる一の翻訳候補が一の翻訳結果である。なお、翻訳結果取得部１１６は、通常、各翻訳候補に対応する翻訳規則のスコアを用いて、一の翻訳結果を取得する。翻訳結果取得部１１６は、例えば、各翻訳候補に対応する１以上の翻訳規則のスコアの合計が最大になるような翻訳候補を選択する。
【００５１】
（ステップＳ２０７）出力部１１７は、ステップＳ２０６で取得された翻訳結果を出力し、処理を終了する。
【００５２】
次に、ステップＳ２０２の係り受け森構成処理について、上述したように、係り受け解析部１０６が、原言語の文や句などの係り受け解析を行い、係り受け森を取得する。つまり、係り受け解析部１０６は、例えば、MST parserを利用して、Eisnerのアルゴリズムにより行う。しかし、係り受け解析部１０６は、図３のフローチャートに示す方法により、係り受け森を構成することも可能である。図３のフローチャートの開始前に、係り受け解析部１０６は、原言語の文や句などの係り受け解析を行い、２以上の係り受け（係り受け木）を取得し、バッファ（例えば、図示しない係り受け格納部）に格納している、とする。
【００５３】
（ステップＳ３０１）係り受け解析部１０６は、カウンタｉに１を代入する。
【００５４】
（ステップＳ３０２）係り受け解析部１０６は、係り受け格納部に、ｉ番目の係り受けが存在するか否かを判断する。ｉ番目の係り受けが存在すればステップＳ３０３に行き、存在しなければ上位処理（ステップＳ２０３）にリターンする。
【００５５】
（ステップＳ３０３）係り受け解析部１０６は、係り受け格納部から、ｉ番目の係り受けを読み出す。
【００５６】
（ステップＳ３０４）係り受け解析部１０６は、カウンタｊに１を代入する。
【００５７】
（ステップＳ３０５）係り受け解析部１０６は、ｉ番目の係り受けにおいて、ｊ番目の頂点が存在するか否かを判断する。ｊ番目の頂点が存在すればステップＳ３０６に行き、存在しなければステップＳ３１２に行く。
【００５８】
（ステップＳ３０６）係り受け解析部１０６は、（ｉ＋１）番目以降の係り受けにおいて、ｊ番目の頂点と同一の頂点を検索する。
【００５９】
（ステップＳ３０７）係り受け解析部１０６は、カウンタｋに１を代入する。
【００６０】
（ステップＳ３０８）係り受け解析部１０６は、ステップＳ３０６において、ｊ番目の頂点と同一のｋ番目の頂点が存在するか否かを判断する。ｋ番目の頂点が存在すればステップＳ３０９に行き、存在しなければステップＳ３１１に行く。
【００６１】
（ステップＳ３０９）係り受け解析部１０６は、ｉ番目の係り受けのｊ番目の頂点と、他の係り受けのｋ番目の頂点とを共通化する処理を行う。
【００６２】
（ステップＳ３１０）係り受け解析部１０６は、カウンタｋを１、インクリメントし、ステップＳ３０８に戻る。
【００６３】
（ステップＳ３１１）係り受け解析部１０６は、カウンタｊを１、インクリメントし、ステップＳ３０５に戻る。
【００６４】
（ステップＳ３１２）係り受け解析部１０６は、カウンタｉを１、インクリメントし、ステップＳ３０２に戻る。
【００６５】
次に、ステップＳ２０３の翻訳森構成処理について、図４のフローチャートを用いて説明する。
【００６６】
（ステップＳ４０１）翻訳規則取得部１１１は、カウンタｉに１を代入する。
【００６７】
（ステップＳ４０２）翻訳規則取得部１１１は、係り受け森が有する頂点のうち、ｉ番目の頂点が存在するか否かを判断する。ｉ番目の頂点が存在すればステップＳ４０３に行き、存在しなければ上位処理（ステップＳ２０５）にリターンする。
【００６８】
（ステップＳ４０３）翻訳規則取得部１１１は、カウンタｊに１を代入する。
【００６９】
（ステップＳ４０４）翻訳規則取得部１１１は、翻訳規則格納部１０５に、ｊ番目の翻訳規則が存在するか否かを判断する。ｊ番目の翻訳規則が存在すればステップＳ４０５に行き、存在しなければステップＳ４１１に行く。
【００７０】
（ステップＳ４０５）翻訳規則取得部１１１は、係り受け森が有するｉ番目の頂点が、ｊ番目の翻訳規則に合致するか否かを判断し、判断結果を所定の変数に代入する。
【００７１】
（ステップＳ４０６）所定の変数の値が"合致"であればステップＳ４０６に行き、"合致"でなければステップＳ４１０に行く。
【００７２】
（ステップＳ４０７）超辺取得部１１３は、ｊ番目の翻訳規則の右辺を有する超辺を構成する。
【００７３】
（ステップＳ４０８）翻訳森取得部１１４は、ステップＳ４０７で構成された超辺を、予め決められたバッファに追記する。なお、このバッファは、翻訳森を格納するバッファである。
【００７４】
（ステップＳ４０９）翻訳森取得部１１４は、ｊ番目の翻訳規則の右辺とテイルとなる頂点とを対応付けて記憶する。
【００７５】
（ステップＳ４１０）翻訳規則取得部１１１は、カウンタｊを１、インクリメントし、ステップＳ４０４に戻る。
【００７６】
（ステップＳ４１１）翻訳規則生成部１１２は、係り受け森が有するｉ番目の頂点に対応する翻訳規則を取得できたか否かを判断する。翻訳規則を取得できていた場合はステップＳ４１２に行き、翻訳規則を取得できていない場合はステップＳ４１３に行く。なお、翻訳規則を一つでも取得できた場合は、ステップＳ４１２に行く。
【００７７】
（ステップＳ４１２）カウンタｉを１、インクリメントし、ステップＳ４０２に戻る。
【００７８】
（ステップＳ４１３）翻訳規則生成部１１２は、翻訳規則を取得できなかった頂点が有する原言語の単語に対応する目的言語の単語（翻訳語）を単語辞書１０２から取得する。
【００７９】
（ステップＳ４１４）翻訳規則生成部１１２は、頂点を内部頂点とし、頂点のテイルを有する左辺と、左辺に対応する目的言語の文字列であり、目的言語の単語（翻訳語）と、頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する。
【００８０】
（ステップＳ４１５）翻訳規則生成部１１２は、ステップＳ４１４で生成した１以上の翻訳規則をｊ番目以降の翻訳規則とし、ステップＳ４０４に戻る。なお、ｊ番目以降の翻訳規則とする、とは、１以上の翻訳規則に対して、ｊ番目以降のＩＤを付与し、予め決められたバッファに格納することである。なお、バッファに格納された翻訳規則は、ステップＳ４０４において、翻訳規則取得部１１１により用いられる。
【００８１】
次に、ステップＳ２０４の翻訳候補取得処理について、図５のフローチャートを用いて説明する。
【００８２】
（ステップＳ５０１）翻訳候補取得部１１５は、カウンタｉに１を代入する。
【００８３】
（ステップＳ５０２）翻訳候補取得部１１５は、翻訳森の中に、ｉ番目の頂点が存在するか否かを判断する。ｉ番目の頂点が存在すればステップＳ５０３に行き、存在しなければ上位処理（ステップＳ２０６）にリターンする。
【００８４】
（ステップＳ５０３）翻訳候補取得部１１５は、翻訳森のｉ番目の頂点に対応する１以上の各超辺が有する１以上の翻訳規則の右辺を取得する。
【００８５】
（ステップＳ５０４）翻訳候補取得部１１５は、カウンタｊに１を代入する。
【００８６】
（ステップＳ５０５）翻訳候補取得部１１５は、ステップＳ５０３で取得した１以上の翻訳規則の右辺のうち、ｊ番目の右辺が存在するか否かを判断する。ｊ番目の右辺が存在すればステップＳ５０６に行き、存在しなければステップＳ５１１に行く。
【００８７】
（ステップＳ５０６）翻訳候補取得部１１５は、カウンタｋに１を代入する。
【００８８】
（ステップＳ５０７）翻訳候補取得部１１５は、ｊ番目の右辺の中に、ｋ番目の変数が存在するか否かを判断する。ｋ番目の変数が存在すればステップＳ５０８に行き、存在しなければステップＳ５１０に行く。
【００８９】
（ステップＳ５０８）翻訳候補取得部１１５は、ｊ番目の右辺のｋ番目の変数に翻訳語等を代入する処理である変数代入処理を実行する。変数代入処理について、図６のフローチャートを用いて説明する。
【００９０】
（ステップＳ５０９）翻訳候補取得部１１５は、カウンタｋを１、インクリメントし、ステップＳ５０７に戻る。
【００９１】
（ステップＳ５１０）翻訳候補取得部１１５は、カウンタｊを１、インクリメントし、ステップＳ５０５に戻る。
【００９２】
（ステップＳ５１１）翻訳候補取得部１１５は、カウンタｉを１、インクリメントし、ステップＳ５０２に戻る。
【００９３】
次に、ステップＳ５０８の変数代入処理について、図６のフローチャートを用いて説明する。
【００９４】
（ステップＳ６０１）翻訳候補取得部１１５は、変数に対応するすべての翻訳規則の右辺を取得する。
【００９５】
（ステップＳ６０２）翻訳候補取得部１１５は、カウンタｌに１を代入する。
【００９６】
（ステップＳ６０３）翻訳候補取得部１１５は、ステップＳ６０１で取得した右辺のうち、ｌ番目の右辺が存在するか否かを判断する。ｌ番目の右辺が存在すれば、存在しなければ上位処理（ステップＳ５０９）にリターンする。
【００９７】
（ステップＳ６０４）翻訳候補取得部１１５は、ｌ番目の右辺を変数に代入する。
【００９８】
（ステップＳ６０５）翻訳候補取得部１１５は、カウンタｍに１を代入する。
【００９９】
（ステップＳ６０６）翻訳候補取得部１１５は、変数に代入したｌ番目の右辺に、ｍ番目の変数が存在するか否かを判断する。ｍ番目の変数が存在すればステップＳ６０７に行き、存在しなければステップＳ６０９に行く。
【０１００】
（ステップＳ６０７）翻訳候補取得部１１５は、変数代入処理を行う。つまり、変数代入処理は再帰的に行われる。
【０１０１】
（ステップＳ６０８）翻訳候補取得部１１５は、カウンタｍを１、インクリメントし、ステップ６０６に戻る。
【０１０２】
（ステップＳ６０９）翻訳候補取得部１１５は、カウンタｌを１、インクリメントし、ステップ６０３に戻る。
【０１０３】
以下、本実施の形態における機械翻訳装置１の具体的な動作について説明する。今、機械翻訳装置１は、例えば、英日翻訳を行う装置である、とする。つまり、例えば、原言語は英語、目的言語は日本語である、とする。
【０１０４】
また、対訳コーパス１０１には、英語の文と日本語の文とを有する多数の対訳文が格納されている、とする。そして、単語辞書１０２にも、英語と日本語の多数の単語対が格納されている。
【０１０５】
そして、上述したように、ルールマッチングの手法（例えば、ＧＨＫＭアルゴリズム等）により、翻訳規則が生成され、多数の翻訳規則が、翻訳規則格納部１０５に格納されている。翻訳規則格納部１０５に格納されている翻訳規則の例を、図７に示す。
【０１０６】
なお、図７において、翻訳規則が有するスコアは省略している。また、例えば、スコア算出部１１０は、翻訳規則が有するスコアを、以下のように算出する。スコア算出部１１０は、例えば、各規則の出現頻度の期待値を算出する。スコア算出部１１０は、例えば、以下の数式３から数式７を格納しており、かかる数式を用いて、各規則の出現頻度の期待値を算出する。
【０１０７】
まず、スコア算出部１１０は、数式３を用いて、翻訳規則の右辺が、着目する翻訳規則の右辺である場合、当該翻訳規則が着目する翻訳規則である確率値を算出する。
【０１０８】
また、スコア算出部１１０は、数式４を用いて、翻訳規則の左辺が、着目する翻訳規則の左辺である場合、当該翻訳規則が着目する翻訳規則である確率値を算出する。
【０１０９】
また、スコア算出部１１０は、数式５を用いて、翻訳規則の左辺のｒｏｏｔが、着目する翻訳規則の左辺のｒｏｏｔである場合、当該翻訳規則が着目する翻訳規則である確率値を算出する。なお、左辺のｒｏｏｔとは、係り受け森上の左辺のｒｏｏｔである。
【数３】
【数４】
【数５】
【０１１０】
ここで数式３から５において、ｒは翻訳規則、ｃ（ｒ）は翻訳規則ｒの出現頻度である。なお、ここでの出現頻度において、スコア算出部１１０は、単純に出現を１回と数えるのではなく、内側外側アルゴリズムを用いて、係り受け解析における尤度最大化に基づいた頻度の期待値を計算することは好適である。頂点ｖに対する外側確率をα（ｖ）、内側確率をβ（ｖ）とすると、スコア算出部１１０は、ある翻訳規則ｒに対する内側外側確率αβ（ｖ）を、数式６を用いて計算する。
【数６】
【０１１１】
そして、スコア算出部１１０は、翻訳規則ｒにおける出現頻度の期待値を、数式７を用いて算出する。数式７において、ＴＯＰは係り受け森上のｒｏｏｔを示している。また、ここでは、出現頻度の期待値は、翻訳規則のスコアとなる、とする。
【数７】
【０１１２】
以上により、スコアを有する１以上の翻訳規則が、翻訳規則格納部１０５に格納された。
【０１１３】
なお、統計的機械翻訳では、スコアの算出のために、対数線形モデルを用いることが好適である。対数線形モデルは、複数の素性を重みで線形結合した形で表される。素性に対する重みは与えられた訓練データ上で翻訳の評価尺度(BLEUなど)を最大化するように学習される。この学習法は誤り率最小化学習法(MERT)と呼ばれており、公知技術であるので、説明を省略する。なお、素性は、例えば、両方向からの単語翻訳確率、翻訳規則に関する確率（数式３、数式４、数式５により算出される確率値）、係り受け解析スコア、N-gram言語モデル、単語数、規則数などである。
【０１１４】
かかる状況において、機械翻訳装置１は、原言語文「I saw a girl with a telesscope」を受け付けた、とする。
【０１１５】
次に、係り受け解析部１０６は、原言語文「I saw a girl with a telesscope」に対して、MST parserを利用して、Eisnerのアルゴリズムにより、係り受け解析を行い、係り受け森を取得する。なお、取得した係り受け森は、例えば、図１０である。図１０の係り受け森は、図８に示す係り受け１、および図９に示す係り受け２により構成されている森である。つまり、図１０の係り受け森は、係り受け１と係り受け２とで、同一の頂点「Ｉ０，１」「ａ２，３」「ａ５，６」「ｔｅｌｅｓｃｏｐｅ５，７」「ｗｉｔｈ４，７」「ｓａｗ０，７」を共通化した図１０の係り受け森である。係り受け解析部１０６は、かかる係り受け森を取得し、係り受け森格納部１０４に、少なくとも一時蓄積する。
【０１１６】
なお、超辺構成部１０８が、図１０の係り受け森に対して、以下に説明するバイナリゼーション（ｂｉｎａｒｉｚａｔｉｏｎ）を行うことは好適である。機械翻訳装置１において、係り受け森から翻訳規則の抽出やデコードを行うことになるが、ある超辺が持つテイルの数が多くなると、翻訳規則の質やデコードの効率に問題が生じる。そこで、係り受け森をバイナリゼーションし、超辺が持つテイルの数に制限を加えることは好適である。ここで、バイナリゼーションとは超辺のテイルのサイズが２以下であるようにすることである。バイナリゼーションは、ある超辺が持つテイルのサイズが３以上である場合、最も左の要素とその次の要素をヘッドから生成する擬似的な頂点をヘッドとした新たな超辺のテイルとして構成し直すという作業を再帰的に行うことである。例として、図１０における超辺ｅ１に対してこの操作を行うと、図１１のようにｓａｗ＃２；７を擬似的なｈｅａｄとした新たな超辺が再構成されることになる。係り受け森のｒｏｏｔからトップダウンに各頂点を訪れてこの操作を行うことで、係り受け森をバイナリゼーションすることができる。
【０１１７】
次に、翻訳規則取得部１１１は、係り受け森格納部１０４に格納された図１０の係り受け森を読み出す。
【０１１８】
そして、翻訳規則取得部１１１等は、図７の翻訳規則を用いて、以下のように、翻訳森を構成する。ここで、説明の簡単化のため、図１０の係り受け森の一部である、図１２の係り受けに対して、図７の翻訳規則を用いて翻訳森を構成する処理を説明する。なお、図１０の係り受け森に対しても、以下で説明する同様の処理により、翻訳森を構成できることは言うまでもない。
【０１１９】
翻訳規則取得部１１１は、図１２の頂点のうち、「Ｉ０，１」を読み出す。そして、翻訳規則取得部１１１は、頂点「Ｉ０，１」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「Ｉ → 私」「Ｉ → 私は」を取得する。次に、超辺取得部１１３は、翻訳規則「Ｉ → 私」「Ｉ → 私は」の右辺「私」「私は」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。そして、翻訳森取得部１１４は、図１３に示す一時的な翻訳森を得る。なお、翻訳森取得部１１４は、係り受けの頂点「Ｉ０，１」のスパンを、そのまま翻訳森の頂点のスパンとして使用する。つまり、翻訳森取得部１１４は、頂点「Ｉ０，１」のスパンを取得し、翻訳森の頂点のスパンとして書き込む。
【０１２０】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ａ２，３」を読み出す。そして、翻訳規則取得部１１１は、頂点「ａ２，３」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「ａ → 一つ」を取得する。次に、超辺取得部１１３は、翻訳規則「ａ → 一つ」の右辺「一つ」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。
【０１２１】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ａ５，６」を読み出す。そして、翻訳規則取得部１１１は、頂点「ａ５，６」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「ａ → 一つ」を取得する。次に、超辺取得部１１３は、翻訳規則「ａ → 一つ」の右辺「一つ」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。そして、この段階で、翻訳森取得部１１４は、図１４に示す一時的な翻訳森を得る。
【０１２２】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ｔｅｌｅｓｃｏｐｅ５，７」を読み出す。そして、翻訳規則取得部１１１は、頂点「ｔｅｌｅｓｃｏｐｅ５，７」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「ａ→ｔｅｌｅｓｃｏｐｅ → 望遠鏡」（図７のＩＤ＝４の規則）、「ｘ１→ｔｅｌｅｓｃｏｐｅ → 望遠鏡ｘ１」（図７のＩＤ＝５の規則）を取得する。次に、超辺取得部１１３は、翻訳規則「ａ→ｔｅｌｅｓｃｏｐｅ → 望遠鏡」の右辺「望遠鏡」を有する超辺、および翻訳規則「ｘ１→ｔｅｌｅｓｃｏｐｅ → 望遠鏡ｘ１」の右辺「望遠鏡ｘ１」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された２つの超辺を、予め決められたバッファに追記する。そして、この段階で、翻訳森取得部１１４は、図１５に示す一時的な翻訳森を得る。
【０１２３】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ｗｉｔｈ４，７」を読み出す。そして、翻訳規則取得部１１１は、頂点「ｗｉｔｈ４，７」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、翻訳規則「ｘ１→ｗｉｔｈ → ｘ１を持った」（図７のＩＤ＝６の規則）を取得する。次に、超辺取得部１１３は、翻訳規則「ｘ１→ｗｉｔｈ → ｘ１を持った」の右辺「ｘ１を持った」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。そして、この段階で、翻訳森取得部１１４は、図１６に示す一時的な翻訳森を得る。
【０１２４】
次に、翻訳規則取得部１１１は、図１２の頂点のうち、「ｓａｗ０，７」を読み出す。そして、翻訳規則取得部１１１は、頂点「ｓａｗ０，７」に合致する翻訳規則を図７から検索する。そして、翻訳規則取得部１１１は、図７のＩＤ＝７の翻訳規則を取得する。次に、超辺取得部１１３は、図７のＩＤ＝７の翻訳規則の右辺「ｘ１はｘ２少女を見た」を有する超辺を構成する。次に、翻訳森取得部１１４は、構成された超辺を、予め決められたバッファに追記する。そして、翻訳森取得部１１４は、図１７に示す翻訳森を得る。なお、図１７の最終的な翻訳森において、頂点「ａ２，３」を使う森は生成されない。他の頂点と連結しないからである。
【０１２５】
なお、係り受け森を翻訳森へと変換する際、ある頂点に適用できる翻訳規則がない場合、翻訳規則生成部１１２は、疑似的な翻訳森の超辺を生成することは好適である。
【０１２６】
例えば、図１０における頂点（ｓａｗ０，７）の超辺ｅ１に対して、疑似的な翻訳規則を生成することを考える。この場合、翻訳規則生成部１１２は、ｓａｗという単語に対する訳語を単語辞書１０２から辞書引きし、"見た"という単語を得たとする。なお、単語辞書１０２は、ＧＩＺＡ＋＋で学習した翻訳ｔａｂｌｅ（D. Yuan and P. Martha. Machine translation using prob-abilistic synchronous dependency insertion grammars. In ACL, 2005.参照）であることは好適である。
【０１２７】
そして、翻訳規則生成部１１２は、頂点（ｓａｗ０，７）を内部頂点とし、頂点のテイルを有する左辺と、左辺に対応する目的言語の文字列"見た"であり、目的言語の単語"見た"と、頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する。つまり、翻訳規則生成部１１２は、例えば、「＜（ｉ０，１，ｇｉｒｌ２，４，ｗｉｔｈ４，７），ｓａｗ０，７， ｘ１見たｘ２ｘ３＞」という超辺（翻訳規則）を作り出す。
【０１２８】
なお、この規則では出力側言語の並びが考慮されておらず、翻訳精度の悪化をまねく危険性がある。そのため、binarizationを行った場合にのみ、変数（ｂｉｎａｒｉｚａｔｉｏｎ時は多くても２つ）と訳語の並べ方最大６通りを考慮して翻訳森の超辺を生成することは好適である。なお、デコードは、前述したようにlazyな操作とHuang05（L. Huang and D. Chiang. Better k-best parsing. In Pro-ceedings of IWPT, pages 53-64, October 2005.参照）のalgorithm2における超辺の一括処理を行うことは好適である。最大で６つの翻訳規則を生成したとしても効率良く動作するからである。また、binarizationを行っていない場合、出力言語側のあらゆる並びを考慮することは超辺のｔａｉｌサイズが大きくなることがあるため現実的に実行が困難である。つまり、binarizationを行うことは極めて好適である。
【０１２９】
次に、翻訳候補取得部１１５は、図１７の翻訳森を用いて、以下のように翻訳候補を取得する。翻訳候補取得部１１５は、図１７の翻訳森の頂点をボトムアップに訪れながら、超辺に付与した翻訳規則の右辺を使って翻訳候補を作り出す。この際、通常、作り出される仮説は膨大な数に及ぶため、翻訳候補取得部１１５は、ビームサーチを用いることは好適である。なお、ビームサーチは公知技術なので、説明を省略する。また、翻訳候補取得部１１５は、部分的な翻訳候補を組み合わせる際にlazyな操作を行うことで探索の効率化を行うことは好適である。ビームサーチとlazyな操作を行いながら探索する手法は、cube pruning と呼ばれており、公知技術である（D. Chiang. Hierachical phrase-based translation. Compu-tational Linguitics, 33:201-228, 2007.参照）。なお、このcube pruningを1-bestの翻訳結果を得るために用いることは好適である。モデルの訓練を行うためのK-best出力ではcube pruningを全頂点で1-bestを見つけるために動作させた後、Huang05（L. Huang and D. Chiang. Better k-best parsing. In Pro-ceedings of IWPT, pages 53-64, October 2005.参照）で提案されているアルゴリズム３によって高速にK-bestの探索を行うことは好適である。
【０１３０】
さらに具体的には、翻訳候補取得部１１５は、図１７の翻訳森の頂点「Ｉ０，１」に対応する超辺が有する１以上の翻訳規則の右辺「私」「私は」を取得する。
【０１３１】
また、翻訳候補取得部１１５は、図１７の翻訳森の頂点「ａ５，６」に対応する超辺が有する翻訳規則の右辺「一つ」を取得する。
【０１３２】
また、翻訳候補取得部１１５は、図１７の翻訳森の頂点「ｔｅｌｅｓｃｏｐｅ５，７」に対応する超辺が有する翻訳規則の右辺「望遠鏡」「望遠鏡ｘ１」を取得する。次に、翻訳候補取得部１１５は、変数「ｘ１」に「一つ」を代入する。そして、翻訳候補取得部１１５は、「望遠鏡」、「望遠鏡一つ」を得る。
【０１３３】
次に、翻訳候補取得部１１５は、図１７の翻訳森の頂点「ｗｉｔｈ４，７」に対応する超辺が有する翻訳規則の右辺「ｔｅｌｅｓｃｏｐｅ５，７を持った」を得る。そして、翻訳候補取得部１１５は、「ｔｅｌｅｓｃｏｐｅ５，７」に対応する「望遠鏡」、「望遠鏡一つ」を右辺「ｔｅｌｅｓｃｏｐｅ５，７を持った」に代入し、「望遠鏡を持った」、「望遠鏡一つを持った」を得る。
【０１３４】
次に、翻訳候補取得部１１５は、図１７の翻訳森の頂点ｓａｗ０，７」に対応する超辺が有する翻訳規則の右辺「Ｉ０，１はｗｉｔｈ４，７少女を見た」を得る。そして、翻訳候補取得部１１５は、右辺「Ｉ０，１はｗｉｔｈ４，７少女を見た」の「Ｉ０，１」に対して、「私」「私は」を代入し、右辺「Ｉ０，１はｗｉｔｈ４，７少女を見た」「ｗｉｔｈ４，７」に対して、「望遠鏡を持った」、「望遠鏡一つを持った」を代入する。そして、翻訳候補取得部１１５は、「私は望遠鏡を持った少女を見た」「私は望遠鏡一つを持った少女を見た」「私はは望遠鏡を持った少女を見た」「私はは望遠鏡一つを持った少女を見た」を得る。
【０１３５】
次に、翻訳結果取得部１１６は、取得された４つの翻訳候補から、翻訳規則のスコアを用いて、一の翻訳候補「私は望遠鏡を持った少女を見た」を選択する。この「私は望遠鏡を持った少女を見た」が翻訳結果である。なお、４つの翻訳候補から一の翻訳結果を取得する方法は種々あり、公知技術であるので、詳細な説明は省略する。
【０１３６】
次に、出力部１１７は、取得された翻訳結果「私は望遠鏡を持った少女を見た」を出力する。
【０１３７】
以下、機械翻訳装置１の実験結果について説明する。
（実験）
【０１３８】
本実験では、中国語から英語への翻訳で実験を行った。対訳コーパスには、新聞データから作成されたＦＢＩＳコーパスを用いた。中英それぞれ単語数３．５Ｍ，４．３Ｍである。翻訳モデルの学習にはＧＩＺＡ＋＋を用いた。また、言語モデル学習用のデータとしてｅｎｇｌｉｓｈ ｇｉｇａ ｗｏｒｄのｘｉｎｈｕａ部分のデータ（単語数３５０Ｍ）を利用した。Ｎ−ｇｒａｍの学習はｓｒｉｌｍを用いて４−ｇｒａｍ言語モデルを学習した。この翻訳実験ではＮＩＳＴ２００２／２００３Ｏｐｅｎ Ｍａｃｈｉｎｅ Ｔｒａｎｓｌａｔｉｏｎ Ｅｖａｌｕａｔｉｏｎの中英翻訳データを用意し、２００２をＭＥＲＴ、２００３をテストデータとして用いた。中国語の形態素解析にはｓｔａｎｆｏｒｄ ｓｅｇｍｅｎｔｅｒとｓｔａｎｆｏｒｄ ｐｏｓｔａｇｇｅｒを利用した。英語のトークナイゼイションには英語ツリーバンクの処理に使われたツールを用いた。中国語の係り受け解析は１−ｓｔ ｏｒｄｅｒのＥｉｓｎｅｒアルゴリズムによって行った。
【０１３９】
また、ここでは中国語ツリーバンクの全１８，４７２文からｃｔｖ（報道）部分５００文とｃｈｔｂ（新聞）部分５００文を除いたデータ（ａｌｌ）とｃｈｔｂ部分８９８１文から共通のｃｈｔｂ部分５００文を除いたデータ（ｎｅｗｓ）とを用いて２つの係り受け解析モデルを構築した（係り受けフォーマットへはＰｅｎｎ２Ｍａｌｔを用いて変換）。除いたデータはテストデータとして利用した。
【０１４０】
図１８は、係り受け解析の精度（ｕｎｌａｂｅｌｅｄ ａｃｃｕｒａｃｙ）を示す。この結果からは、新聞データをドメインとする解析を行う場合，新聞データのみから学習したモデルを用いる方が良いことがわかる。よって、以下の翻訳実験では新聞をドメインとするデータを用いるため、全新聞データ８９８１文から学習したモデルを用いた。
【０１４１】
機械翻訳装置１で用いる素性は、両方向からの単語翻訳確率、翻訳規則に関する確率（数式３、数式４、数式５により算出される確率値）、係り受け解析スコア、N-gram言語モデル、単語数、規則数の計９つとした。これらの素性に対する対数線形モデルの重みはMERTでBLEUを最大化するように学習した。図１９は、本実験における係り受け森のK-best数と翻訳規則数の関係を示している。また、図１９では、１つの翻訳規則が持つ平均の変数の数も示している。翻訳規則が持つ変数の数は少ない方が効率良くデコードを行うことができる。結果からは、バイナリゼーションには変数の数を減らす効果があると言えるが、その一方で規則の数は大きく増加した。以下の翻訳実験では、テストデータや訓練データに対して使われることのない規則は削除した。機械翻訳装置１との比較には、句に基づくデコーダmosesと階層句に基づくデコーダjoshuaを用いた。対数線形モデルの重み訓練時のK-best数は各システム共に2000-best出力した。また、デコード時の翻訳候補K-best数は、各システム共に500-bestとした。図２０にBLEUによる翻訳精度の差を示す。ここでは、10-bestの係り受け森を用いて抽出した翻訳規則を使って翻訳実験を行った。実験結果から、機械翻訳装置１は、階層句や句に基づいたシステムとほぼ同等の性能を示すことができたが、翻訳精度の著しい向上は得られなかった。しかし、これは、係り受けは単語で超グラフの頂点が表されるため、翻訳規則の適用を行う際、未知語などの影響を大きく受け易いからである。そして、機械翻訳装置１では、森によるアプローチとバイナリゼーションによってこの問題を緩和させることができる。
【０１４２】
以上、本実施の形態によれば、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる。
【０１４３】
また、本実施の形態によれば、複数の依存構造解析結果を、ノードを共有することによりコンパクトに表現した、係り受け森からの翻訳を実現することにより、解析の曖昧性や誤りによるゆらぎを排除することが可能となった。具体的には、翻訳ルールの抽出時に解析の曖昧性を考慮して網羅的に列挙することが可能となり、さらに、翻訳時には解析誤りに対しても翻訳ルールを適用することが可能となった。
【０１４４】
なお、本実施の形態における技術は、音声翻訳、文書翻訳などの機械翻訳分野に適用できる。
【０１４５】
また、本実施の形態における処理は、ソフトウェアで実現しても良い。そして、このソフトウェアをソフトウェアダウンロード等により配布しても良い。また、このソフトウェアをＣＤ−ＲＯＭなどの記録媒体に記録して流布しても良い。なお、このことは、本明細書における他の実施の形態においても該当する。
【０１４６】
また、図２１は、本明細書で述べた機械翻訳装置を実現するコンピュータの外観を示す。上述の実施の形態は、コンピュータハードウェア及びその上で実行されるコンピュータプログラムで実現され得る。図２１は、このコンピュータシステム３４０の概観図であり、図２２は、コンピュータシステム３４０の内部構成を示す図である。
【０１４７】
図２１において、コンピュータシステム３４０は、ＦＤドライブ３４１１、ＣＤ−ＲＯＭドライブ３４１２を含むコンピュータ３４１と、キーボード３４２と、マウス３４３と、モニタ３４４とを含む。
【０１４８】
図２２において、コンピュータ３４１は、ＦＤドライブ３４１１、ＣＤ−ＲＯＭドライブ３４１２に加えて、ＭＰＵ３４１３と、ＣＤ−ＲＯＭドライブ３４１２及びＦＤドライブ３４１１に接続されたバス３４１４と、ブートアッププログラム等のプログラムを記憶するためのＲＯＭ３４１５とに接続され、アプリケーションプログラムの命令を一時的に記憶するとともに一時記憶空間を提供するためのＲＡＭ３４１６と、アプリケーションプログラム、システムプログラム、及びデータを記憶するためのハードディスク３４１７とを含む。ここでは、図示しないが、コンピュータ３４１は、さらに、ＬＡＮへの接続を提供するネットワークカードを含んでも良い。
【０１４９】
コンピュータシステム３４０に、上述した実施の形態の機械翻訳装置の機能を実行させるプログラムは、ＣＤ−ＲＯＭ３５０１、またはＦＤ３５０２に記憶されて、ＣＤ−ＲＯＭドライブ３４１２またはＦＤドライブ３４１１に挿入され、さらにハードディスク３４１７に転送されても良い。これに代えて、プログラムは、図示しないネットワークを介してコンピュータ３４１に送信され、ハードディスク３４１７に記憶されても良い。プログラムは実行の際にＲＡＭ３４１６にロードされる。プログラムは、ＣＤ−ＲＯＭ３５０１、ＦＤ３５０２またはネットワークから直接、ロードされても良い。
【０１５０】
プログラムは、コンピュータ３４１に、上述した実施の形態の機械翻訳装置の機能を実行させるオペレーティングシステム（ＯＳ）、またはサードパーティープログラム等は、必ずしも含まなくても良い。プログラムは、制御された態様で適切な機能（モジュール）を呼び出し、所望の結果が得られるようにする命令の部分のみを含んでいれば良い。コンピュータシステム３４０がどのように動作するかは周知であり、詳細な説明は省略する。
【０１５１】
また、上記各実施の形態において、各処理（各機能）は、単一の装置（システム）によって集中処理されることによって実現されてもよく、あるいは、複数の装置によって分散処理されることによって実現されてもよい。
【０１５２】
本発明は、以上の実施の形態に限定されることなく、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【０１５３】
以上のように、本発明にかかる機械翻訳装置は、係り受け森を入力とすることにより、精度の高い機械翻訳が可能となる、という効果を有し、機械翻訳装置等として有用である。
【符号の説明】
【０１５４】
１ 機械翻訳装置
１０１ 対訳コーパス
１０２ 単語辞書
１０４ 係り受け森格納部
１０５ 翻訳規則格納部
１０６ 係り受け解析部
１０７ 翻訳規則抽出部
１０８ 超辺構成部
１０９ 出現頻度取得部
１１０ スコア算出部
１１１ 翻訳規則取得部
１１２ 翻訳規則生成部
１１３ 超辺取得部
１１４ 翻訳森取得部
１１５ 翻訳候補取得部
１１６ 翻訳結果取得部
１１７ 出力部
【特許請求の範囲】
【請求項１】
原言語の文を係り受け解析して取得された２以上の係り受けであり、前記原言語の文を構成する単語とスパンとを含む２以上の頂点を有する２以上の係り受けのうち、同一である内部頂点を共通化し、構成された係り受け森を格納し得る係り受け森格納部と、
原言語の係り受けの部分木であり、当該部分木の内部頂点は単語であり、前記内部頂点以外の頂点は単語か変数をとる部分木である左辺と、当該左辺に対応する目的言語の文字列であり、単語と変数を有する文字列である右辺とを対応付けて有し、かつスコアを有する１以上の翻訳規則を格納し得る翻訳規則格納部と、
原言語の単語と目的言語の単語とを対応付けた情報である１以上の単語対を格納し得る単語辞書と、
前記係り受け森を構成する各頂点に対して、前記翻訳規則格納部の１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する翻訳規則取得部と、
前記係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、当該各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する超辺取得部と、
前記係り受け森を構成する全頂点と、前記超辺取得部が取得した１以上の超辺とを有する翻訳森を取得する翻訳森取得部と、
前記翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と、前記単語辞書とを用いて、１以上の翻訳候補を取得する翻訳候補取得部と、
前記翻訳候補取得部が取得した１以上の翻訳候補のうち、いずれか１以上の翻訳候補である翻訳結果を出力する出力部とを具備する機械翻訳装置。
【請求項２】
原言語の文と目的言語の文とを有する１以上の対訳文を有する対訳コーパスと、
前記対訳コーパスにおいて、１以上の各翻訳規則の出現頻度を取得する出現頻度取得部と、
前記各翻訳規則の出現頻度を用いて、スコアを算出するスコア算出部とをさらに具備し、
前記翻訳規則が有するスコアは、前記スコア算出部が算出したスコアである請求項１記載の機械翻訳装置。
【請求項３】
前記翻訳規則取得部が、前記係り受け森を構成する頂点に対する翻訳規則を取得できなかった場合、前記翻訳規則を取得できなかった頂点が有する原言語の単語に対応する目的言語の単語を前記単語辞書から取得し、前記頂点を内部頂点とし、前記頂点のテイルを有する左辺と、当該左辺に対応する目的言語の文字列であり、前記目的言語の単語と、前記頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する翻訳規則生成部をさらに具備し、
前記翻訳規則取得部は、
前記係り受け森を構成する各頂点に対して、前記翻訳規則生成部が生成した１以上の翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する請求項１または請求項２記載の機械翻訳装置。
【請求項４】
前記係り受け森が有する各超辺のテイルの数が３以上である場合に、当該超辺のテイルの数が２以下となるように、当該超辺の一のテイルと当該超辺の他の一のテイルの擬似的なヘッドであり、当該一のテイルと当該他の一のテイルの元のヘッドのテイルとなるヘッドを生成し、新たな超辺を構成する超辺構成部をさらに具備し、
前記係り受け森格納部の係り受け森は、前記超辺構成部が構成した新たな超辺を含む係り受け森である請求項１から請求項３いずれか記載の機械翻訳装置。
【請求項５】
記録媒体に、
原言語の文を係り受け解析して取得された２以上の係り受けであり、前記原言語の文を構成する単語とスパンとを含む２以上の頂点を有する２以上の係り受けのうち、同一である内部頂点を共通化し、構成された係り受け森と、
原言語の係り受けの部分木であり、当該部分木の内部頂点は単語であり、前記内部頂点以外の頂点は単語か変数をとる部分木である左辺と、当該左辺に対応する目的言語の文字列であり、単語と変数を有する文字列である右辺とを対応付けて有し、かつスコアを有する１以上の翻訳規則と、
原言語の単語と目的言語の単語とを対応付けた情報である１以上の単語対とを格納しており、
翻訳規則取得部、超辺取得部、翻訳森取得部、翻訳候補取得部、および出力部により実現され得る機械翻訳方法であって、
前記翻訳規則取得が、前記係り受け森を構成する各頂点に対して、前記記録媒体の１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する翻訳規則取得ステップと、
前記超辺取得部が、前記係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、当該各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する超辺取得ステップと、
前記翻訳森取得部が、前記係り受け森を構成する全頂点と、前記超辺取得ステップで取得された１以上の超辺とを有する翻訳森を取得する翻訳森取得ステップと、
前記翻訳候補取得部が、前記翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と、前記単語辞書とを用いて、１以上の翻訳候補を取得する翻訳候補取得ステップと、
前記出力部が、前記翻訳候補取得ステップで取得された１以上の翻訳候補のうち、いずれか１以上の翻訳候補である翻訳結果を出力する出力ステップとを具備する機械翻訳方法。
【請求項１】
原言語の文を係り受け解析して取得された２以上の係り受けであり、前記原言語の文を構成する単語とスパンとを含む２以上の頂点を有する２以上の係り受けのうち、同一である内部頂点を共通化し、構成された係り受け森を格納し得る係り受け森格納部と、
原言語の係り受けの部分木であり、当該部分木の内部頂点は単語であり、前記内部頂点以外の頂点は単語か変数をとる部分木である左辺と、当該左辺に対応する目的言語の文字列であり、単語と変数を有する文字列である右辺とを対応付けて有し、かつスコアを有する１以上の翻訳規則を格納し得る翻訳規則格納部と、
原言語の単語と目的言語の単語とを対応付けた情報である１以上の単語対を格納し得る単語辞書と、
前記係り受け森を構成する各頂点に対して、前記翻訳規則格納部の１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する翻訳規則取得部と、
前記係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、当該各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する超辺取得部と、
前記係り受け森を構成する全頂点と、前記超辺取得部が取得した１以上の超辺とを有する翻訳森を取得する翻訳森取得部と、
前記翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と、前記単語辞書とを用いて、１以上の翻訳候補を取得する翻訳候補取得部と、
前記翻訳候補取得部が取得した１以上の翻訳候補のうち、いずれか１以上の翻訳候補である翻訳結果を出力する出力部とを具備する機械翻訳装置。
【請求項２】
原言語の文と目的言語の文とを有する１以上の対訳文を有する対訳コーパスと、
前記対訳コーパスにおいて、１以上の各翻訳規則の出現頻度を取得する出現頻度取得部と、
前記各翻訳規則の出現頻度を用いて、スコアを算出するスコア算出部とをさらに具備し、
前記翻訳規則が有するスコアは、前記スコア算出部が算出したスコアである請求項１記載の機械翻訳装置。
【請求項３】
前記翻訳規則取得部が、前記係り受け森を構成する頂点に対する翻訳規則を取得できなかった場合、前記翻訳規則を取得できなかった頂点が有する原言語の単語に対応する目的言語の単語を前記単語辞書から取得し、前記頂点を内部頂点とし、前記頂点のテイルを有する左辺と、当該左辺に対応する目的言語の文字列であり、前記目的言語の単語と、前記頂点のテイルに対応する変数とを有する１以上の翻訳規則を生成する翻訳規則生成部をさらに具備し、
前記翻訳規則取得部は、
前記係り受け森を構成する各頂点に対して、前記翻訳規則生成部が生成した１以上の翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する請求項１または請求項２記載の機械翻訳装置。
【請求項４】
前記係り受け森が有する各超辺のテイルの数が３以上である場合に、当該超辺のテイルの数が２以下となるように、当該超辺の一のテイルと当該超辺の他の一のテイルの擬似的なヘッドであり、当該一のテイルと当該他の一のテイルの元のヘッドのテイルとなるヘッドを生成し、新たな超辺を構成する超辺構成部をさらに具備し、
前記係り受け森格納部の係り受け森は、前記超辺構成部が構成した新たな超辺を含む係り受け森である請求項１から請求項３いずれか記載の機械翻訳装置。
【請求項５】
記録媒体に、
原言語の文を係り受け解析して取得された２以上の係り受けであり、前記原言語の文を構成する単語とスパンとを含む２以上の頂点を有する２以上の係り受けのうち、同一である内部頂点を共通化し、構成された係り受け森と、
原言語の係り受けの部分木であり、当該部分木の内部頂点は単語であり、前記内部頂点以外の頂点は単語か変数をとる部分木である左辺と、当該左辺に対応する目的言語の文字列であり、単語と変数を有する文字列である右辺とを対応付けて有し、かつスコアを有する１以上の翻訳規則と、
原言語の単語と目的言語の単語とを対応付けた情報である１以上の単語対とを格納しており、
翻訳規則取得部、超辺取得部、翻訳森取得部、翻訳候補取得部、および出力部により実現され得る機械翻訳方法であって、
前記翻訳規則取得が、前記係り受け森を構成する各頂点に対して、前記記録媒体の１以上の各翻訳規則を適用し、頂点ごとに、合致する１以上の翻訳規則を取得する翻訳規則取得ステップと、
前記超辺取得部が、前記係り受け森を構成する各頂点をヘッドとした１以上の超辺であり、当該各頂点に対応する１以上の翻訳規則の左辺における変数部分に対応する頂点をテイルとした１以上の超辺を取得する超辺取得ステップと、
前記翻訳森取得部が、前記係り受け森を構成する全頂点と、前記超辺取得ステップで取得された１以上の超辺とを有する翻訳森を取得する翻訳森取得ステップと、
前記翻訳候補取得部が、前記翻訳森の各頂点に対応する１以上の各超辺が有する翻訳規則の右辺と、前記単語辞書とを用いて、１以上の翻訳候補を取得する翻訳候補取得ステップと、
前記出力部が、前記翻訳候補取得ステップで取得された１以上の翻訳候補のうち、いずれか１以上の翻訳候補である翻訳結果を出力する出力ステップとを具備する機械翻訳方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１２−１８５６２３（Ｐ２０１２−１８５６２３Ａ）
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願番号】特願２０１１−４７５８９（Ｐ２０１１−４７５８９）
【出願日】平成２３年３月４日（２０１１．３．４）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願日】平成２３年３月４日（２０１１．３．４）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
[ Back to top ]