機械翻訳装置、機械翻訳方法、およびそのプログラム
【課題】高い翻訳精度の機械翻訳技術を提供する。
【解決手段】本発明は、部分仮説を拡張する手法によって、翻訳元言語の単語列から翻訳先言語の単語列を生成する機械翻訳装置２であって、（ａ）翻訳候補となる翻訳先言語の単語列だけでなく、少なくとも、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列、および、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列、のいずれかを考慮して部分仮説の評価値を示す部分仮説スコアを算出することで、翻訳精度を向上させることができる。
【解決手段】本発明は、部分仮説を拡張する手法によって、翻訳元言語の単語列から翻訳先言語の単語列を生成する機械翻訳装置２であって、（ａ）翻訳候補となる翻訳先言語の単語列だけでなく、少なくとも、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列、および、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列、のいずれかを考慮して部分仮説の評価値を示す部分仮説スコアを算出することで、翻訳精度を向上させることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械翻訳装置、機械翻訳方法、およびそのプログラムに関する。
【背景技術】
【０００２】
従来、統計モデルを用いて機械翻訳を実現する技術（統計的機械翻訳）が知られている（例えば、非特許文献１〜４）。
統計的機械翻訳では、翻訳元言語の単語列（文）が与えられたとき、翻訳確率を最大化するような翻訳先言語の単語列（文）を探索する問題として定式化される。ここで、翻訳確率を対数線形モデルで表現すると、最終的に統計的機械翻訳は式（１）で定式化される。
【０００３】
【数１】
【０００４】
ここで、翻訳元言語の単語列には、各単語位置に整数「１」〜「Ｊ」の識別符号が付与されている。すなわち、翻訳元言語の単語列は、「Ｊ」個の単語から構成される。なお、翻訳元言語が日本語の場合には、翻訳元言語の単語列は、「Ｊ」個の自立語、付属語、句読点（「。」「、」）から構成されることとなる。また、翻訳先言語の単語列には、各単語位置に整数「１」〜「Ｉ」の識別符号が付与されている。すなわち、翻訳先言語の単語列は、「Ｉ」個の単語から構成される。また、ｍ（１≦ｍ≦Ｍ）は、素性関数を識別するための整数を示し、Ｍは、素性関数の個数を示す。また、各素性関数は、翻訳としての確からしさを表すものや、翻訳先言語としての確からしさを表すもの等である。単語列集合Ｅは、翻訳先言語の単語のあらゆる組合せで生成可能なすべての単語列集合を表す。各素性重みλmは、誤り最小化学習法等を用いて素性重み学習用対訳コーパスにおける翻訳精度の値が最大になるように設定される（例えば、非特許文献１参照）。
【０００５】
翻訳元言語の文から翻訳先言語の文への翻訳に対して、重み付き同期文脈自由文法（weighted synchronous context-free grammar）を利用して、翻訳元言語の文と翻訳先言語の文との対応付けをモデル化する方法が知られている（例えば、非特許文献２参照）。
重み付き同期文脈自由文法は、式（２）に示すルールに、重みが付いたものの集合からなるものである。
【０００６】
【数２】
【０００７】
ここで、矢印の左辺のＸは、非終端記号を示す。矢印の右辺のγは、終端記号または非終端記号から構成された記号列であって翻訳元言語に対応している。また、αは、終端記号または非終端記号から構成された記号列であって翻訳先言語に対応している。また、「〜」は、記号列γに含まれる非終端記号と、記号列αに含まれる非終端記号との一対一の対応関係を表している。ここでは、記号列γに含まれる非終端記号の個数と、記号列αに含まれる非終端記号の個数とは同じものとする。
【０００８】
式（２）に示したルールの具体例を表１に示す。ここで、Ｘ(k)は、非終端記号であり、ｋ（ｋ＝１，２，…）は、翻訳元言語の非終端記号の配置と、翻訳先言語の非終端記号の配置との対応関係を示している。
【０００９】
【表１】
【００１０】
非特許文献２に記載された方法の特殊な形として、式（３）に示す形式のルールだけを用いた方法も知られている（非特許文献３参照）。非特許文献３に記載された方法は、句単位で統計的機械翻訳を行うものであり、フレーズペアに基づく翻訳方法である。この方法では、抽出されたフレーズペアの集合から同期文脈自由文法を生成する際に、式（３）に示す形式のルールだけ用いる。このルールの形式に依存して解探索を行う場合には、効率的なビームサーチの手法が利用可能である（非特許文献４参照）。非特許文献４に記載の方法では、解探索において、翻訳された単語範囲を、翻訳済みの単語の位置をマークしたビット列で表現してメモリに保持している。
【００１１】
【数３】
【００１２】
重み付き同期文脈自由文法を利用した従来のモデル化では、重み付き同期文脈自由文法の導出Ｄを用いて、翻訳元言語の単語列と翻訳先言語の単語列とをそれぞれｆ（Ｄ）、ｅ（Ｄ）と記述する。ここで、例えば、翻訳元言語の単語列ｆ（Ｄ）の「ｉ」番目の単語から「ｊ」番目の単語を被うルールをｒとすると、導出Ｄは、三つ組＜ｒ，ｉ，ｊ＞の集合で表される。
【００１３】
そして、非特許文献２のモデル化では、統計的機械翻訳を定式化した式（１）を導出ベースに修正した式（４）を用いる。この定式化では、翻訳元言語の単語列が与えられたとき、素性関数と素性重みとの積の線形和が最大となるような導出Ｄ＾を求めたときに、それに対応するｅ（Ｄ＾）が翻訳結果となる。ここで、記号「＾（ハット）」は、文字「Ｄ」の上に付される記号を示し、本明細書では、以下、記号「＾（ハット）」を同様な意味で使用する。
【００１４】
【数４】
【００１５】
式（４）に示す各素性関数の値ｈm（Ｄ）に何を用いるかについては、様々なバリエーションが考えられる。例えば、以下の６つの関数の値の自然対数loge（以下、lnと表記する）を用いる場合がある（例えば、非特許文献３参照）。これら６つの関数の値とは、式（５）に示す翻訳確率Ｐe｜f（Ｄ），Ｐf｜e（Ｄ）と、式（６）に示すレキシカル重みLexe｜f（Ｄ），Lexf｜e（Ｄ）と、n-gram言語モデルの確率ＰLM（ｅ（Ｄ））と、フレーズペナルテイexp（length（ｅ（Ｄ）））である。ここで、length（・）は、単語数を返す関数を示す。
【００１６】
【数５】
【数６】
【００１７】
翻訳確率Ｐe｜f（Ｄ），Ｐf｜e（Ｄ）と、レキシカル重みLexe｜f（Ｄ），Lexf｜e（Ｄ）とは、翻訳としての確からしさを評価するための値であり、翻訳モデルとも呼ばれている。詳細には、例えば、翻訳確率Ｐe｜f（Ｄ）は、式（５）に示すように、導出Ｄに含まれるルールｒごとの確率Ｐ（α｜γ）をルールごとのスコアとして、導出Ｄに含まれるすべてのルールｒについてルールごとのスコアを積算したものである。
【００１８】
例えば、非特許文献２に記載された方法では、翻訳における解探索を次の手順で行う。まず、ＣＫＹ（Cocke-Kasami-Younger）法に基づくボトムアップ構文解析において、同期文脈自由文法の翻訳元言語側のルールを、翻訳元言語の単語列に適用し、翻訳元言語の構文解析木を得る。そして、翻訳元言語の構文解析木に対応する同期文脈自由文法の最適な導出Ｄ＾を、前記した式（４）に基づいて求め、その最適な導出Ｄ＾に基づいて翻訳先言語の単語列を生成する。ただし、統計的機械翻訳の解探索において解の候補（以下、仮説と称する。）は膨大であるため、計算量の観点から、全探索をして真の最適解を求めることは事実上不可能となっている。そこで、従来、解探索の過程で部分的に構成された、同期文脈自由文法の部分木の導出Ｄに対して所定の枝刈りを実行しながら処理をすすめて準最適解を求めることとしている。
【００１９】
また、非特許文献５では、ＣＫＹ法に基づくボトムアップ構文解析のアルゴリズムを基に、cube pruningという手法で効率的に準最適解を求める方法を提案している。
【００２０】
また、特許文献１では、解探索において副作用の少ない枝狩りを実現するべく、非特許文献５とは別の方法を提案している。副作用の少ない枝刈りを実現するためには、前記した式（４）に示される導出Ｄの仮説の尤度を正確に見積もることが必要である。その際に、翻訳精度を向上させるために、素性関数の１つとして、翻訳先言語のn-gram言語モデルを用いることが重要である。そのため、仮説のもととなる部分仮説のスコアとして、n-gram言語モデルのスコアを有効利用するために、特許文献１では、翻訳先言語の文頭から文末にかけて逐次的に生成されることを保障する、解探索方法を提案している。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００８−１５８４４号公報
【非特許文献】
【００２２】
【非特許文献１】Franz Josef Och, “Minimum Error Rate Training in Statistical Machine Translation”, In Proc. of ACL 2003, p. 160-167, Sapporo, Japan, July 2003
【非特許文献２】David Chiang, “A Hierarchical Phrase-Based Model for Statistical Machine Translation”, In Proc. of ACL 2005, p. 263-270, Ann Arbor, Michigan, June 2005
【非特許文献３】Philipp Koehn, Franz Josef Och, and Daniel Marcu, “Statistical Phrase-Based Translation” In Proc. of NAACL 2003, p. 48-54、Edmonton, Canada, 2003
【非特許文献４】Philipp Koehn, “Pharaoh: A Beam Search Decoder for Phrase-Based Statistical Machine Translation Models”, In Proc. of the 6th Conference of the Association for Machine Translation in the Americas(AMTA), p. l15-124, September-October 2004
【非特許文献５】David Chiang, “Hierarchical Phrase-Based Translation”, Computational Linguistics, Vol. 33, No. 2, pages 201-228, 2007.
【発明の概要】
【発明が解決しようとする課題】
【００２３】
従来技術では、単語の並び替えの尤もらしさと訳語選択の尤もらしさの両方を、式（２）のルールに対する重みという形でモデル化している。しかし、これだけでは単語の並び替えに関するモデル化が弱いため、日本語から英語などのように語順の大きく異なる言語間の翻訳精度が十分でないという問題がある。
【００２４】
そこで、本発明では、前記した問題を解決し、高い翻訳精度の機械翻訳技術を提供することを課題とする。
【課題を解決するための手段】
【００２５】
前記課題を解決するために、本発明は、同期文脈自由文法を用いて翻訳元言語の単語列から翻訳先言語の単語列を生成するルールが複数格納されたルールテーブルを利用して、入力された翻訳元言語の単語列の翻訳結果である前記入力に対応する翻訳先言語の単語列として、所定の部分仮説からそれよりも長い新たな部分仮説を順次作成して前記所定の部分仮説を拡張することによって最終的に生成された部分仮説である仮説を出力する機械翻訳装置である。前記部分仮説は、（ａ）翻訳候補となる翻訳先言語の単語列と、少なくとも、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列、および、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列、のいずれかと、を考慮して作成されるものである。機械翻訳装置は、前記所定の部分仮説を拡張するために適用可能なルールを前記ルールテーブルからそれぞれ探索するルール探索手段と、前記探索されたルールの翻訳元言語側に対して、前記入力された翻訳元言語の単語列を構成する単語の単語数と単語位置とに基づいて、前記探索されたルールの非終端記号が被う翻訳元言語の単語列の範囲を示す単語範囲を付加して、適用可能な単語範囲付きルールをそれぞれ生成する単語範囲付きルール生成手段と、前記適用可能なルールを適用し前記新たな部分仮説を拡張し、前記ルールごとにそれぞれ予め求められた、翻訳の確からしさを表す翻訳モデルのスコアと、前記（ａ）の単語列としての確からしさを表す言語モデルのスコアと、少なくとも、前記(ｂ)の単語列としての確からしさを表す言語モデルのスコア、および、前記(ｃ)の単語列としての確からしさを表す言語モデルのスコア、のいずれかと、に基づいて、前記作成された部分仮説の評価値を示す部分仮説スコアを算出する部分仮説スコア算出手段と、前記入力された翻訳元言語の単語列に対して適用可能な所定の部分仮説を探索し、前記所定の部分仮説を拡張することによって最終的に生成された部分仮説のうちで、前記部分仮説スコアが最大となる部分仮説を、前記仮説として探索する仮説探索手段と、を備える。
【００２６】
かかる発明によれば、入力された翻訳元言語の単語列において未翻訳の部分に対して部分仮説を順次拡張する際に、（ａ）翻訳候補となる翻訳先言語の単語列だけでなく、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列や、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列も用いて部分仮説を評価する。このため、翻訳元言語の翻訳先言語の語順への並び替えの尤もらしさや、翻訳先言語の翻訳元言語の語順への並び替えの尤もらしさを、部分仮説の評価に活用することができ、翻訳の精度や速度を向上させることができる。
【００２７】
また、本発明は、前記（ａ）の単語列、前記(ｂ)の単語列、および、前記(ｃ)の単語のそれぞれについて、所定の評価モデルを用いて、当該単語列とその正解との近さを考慮して、素性の重みを予め生成する重み学習モジュールを、さらに備える。
【００２８】
かかる発明によれば、より精度の高い機械翻訳を行うための準備として、素性の重みを予め生成することができる。
【００２９】
また、本発明は、前記部分仮説スコア算出手段が、前記重みを用いて前記部分仮説スコアを算出する。
【００３０】
かかる発明によれば、部分仮説スコア算出手段は、前記重みを用いることで、部分仮説スコアをより高い精度で算出することができる。
【００３１】
また、本発明は、コンピュータを機械翻訳装置として機能させるためのプログラムである。これにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【発明の効果】
【００３２】
本発明によれば、高い翻訳精度の機械翻訳技術を提供することができる。
【図面の簡単な説明】
【００３３】
【図１】本発明の実施形態に係るルール作成装置の構成を示す機能ブロック図である。
【図２】日英の対訳の単語対応の例を示す図である。
【図３】図１に示したルールテーブルの例を示す図である。
【図４】図１に示したルール作成装置の動作を示すフローチャートである。
【図５】本発明の実施形態に係る機械翻訳装置の構成を示す機能ブロック図である。
【図６】図５に示した機械翻訳装置の動作を示すフローチャートである。
【図７】部分仮説から仮説への拡張例を示す図である。
【図８】部分仮説から仮説への拡張例を示す図である。
【発明を実施するための形態】
【００３４】
以下、図面を参照して本発明の機械翻訳装置および機械翻訳方法、ならびにルール作成装置およびルール作成方法を実施するための形態（以下「実施形態」と称する。）について詳細に説明する。以下では、ルール作成装置およびルール作成方法と、機械翻訳装置および機械翻訳方法とに分けて順次説明を行う。
【００３５】
［ルール作成装置の構成］
ルール作成装置は、翻訳元言語の単語列（文）を翻訳先言語の単語列（文）に機械的に翻訳する機械翻訳装置で利用するルールを作成するものである。以下では、翻訳元言語を日本語、翻訳先言語を英語として説明する。
【００３６】
図１に示すように、ルール作成装置１は、入出力手段１０と、記憶手段１１と、単語対応作成モジュール１２と、制御手段１３と、単語並び替えモデル学習手段１４とを備え、これらは、例えば、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、ＨＤＤ（Hard Disk Drive）と、入出力インタフェース等から構成される。
【００３７】
入出力手段１０は、対訳コーパス１５０を単語対応作成モジュール１２に入力したり、演算処理の結果や記憶手段１１に記憶されたデータ等を出力装置Ｄに出力したりするものである。また、入出力手段１０は、入力装置Ｋから、所定のコマンド（モード選択コマンドや動作コマンド等）を制御手段１３に入力する。本実施形態では、モード選択コマンドは、「単語対応作成」モードを選択するコマンドと、「ルールテーブル作成」モード、「並び替えモデル作成」モードを選択するコマンドとを含む。
対訳コーパス１５０は、互いに同じ意味を有する翻訳元言語の単語列と翻訳先言語の単語列との組合せのデータを複数備える。
【００３８】
記憶手段１１は、例えば、ＣＰＵによる演算処理等に利用されるＲＡＭや、例えば、所定のプログラム、各種データベース、処理結果等を格納するＲＯＭやＨＤＤを備えている。例えば、記憶手段１１には、処理結果として、単語対応１１１と、フレーズペア１１２と、ルール１１３と、ルールテーブル１１４と、翻訳元言語並び替えモデル１１５（所定の評価モデル）とが格納される。なお、翻訳先言語並び替えモデル１１６（所定の評価モデル）については、本実施形態の変形例の項で説明する。
【００３９】
単語対応作成モジュール１２は、「単語対応作成」モードを選択するコマンドが入力されたときに、対訳コーパス１５０から得られる単語共起に関する統計量を活用し、多対多（翻訳元言語または翻訳先言語の単語がどこにも対応付かないことを含む）の単語対応１１１を自動的に求めるものである。単語対応作成モジュール１２は、多対多の単語対応１１１を求めるために、例えば、単語単位の翻訳モデルを活用して、文全体で最適な１対多対応と多対１対応とを求め、その両者を組合せる。組合せ方の一例としては、１対多対応と多対１対応とのインターセクションを使い、それに隣接する１対多対応と多対１対応とのユニオンの要素を追加する方法がある（非特許文献３参照）。
【００４０】
なお、単語単位の翻訳モデルについては、「Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. “The mathematics of statistical machine translation: Parameter estimation”, Computational Linguistics, 19(2):263-311, 1993」に記載されている。また、対訳コーパス１５０自体が単語対応１１１の情報を保持している場合には、単語対応作成モジュール１２を省略した構成としてもよい。
【００４１】
図２に、日英（日本語と英語）の対訳の単語対応の例を示す。８個の単語および句点（ピリオド）を示す黒丸が単語対応である。日本語は、「違憲 の 問題 について は 、 連邦 憲法 裁判所 が 決定 する 。」である。その対訳である英語は、「The Federal Constitutional Court decides on the question of unconstitutionality .」である。
【００４２】
図１に戻って、制御手段１３は、モード判定手段１３１と、フレーズペア抽出手段１３２と、ルール作成手段１３３と、翻訳スコア計算手段１３４とを備えている。
【００４３】
モード判定手段１３１は、入力装置Ｋから入出力手段１０を介して入力したモード選択コマンドの示すモードを判定するものである。モード判定手段１３１は、モードが「単語対応作成」モードの場合には、単語対応作成モジュール１２に対して対訳コーパス１５０を入力するように指示する。また、モード判定手段１３１は、モードが「並び替えモデル作成」モードの場合には、単語並び替えモデル学習手段１４に対して翻訳元言語並べ替えモデル１１５を作成するように指示する。また、モード判定手段１３１は、モードが「ルールテーブル作成」モードの場合には、フレーズペア抽出手段１３２に対して対訳コーパス１５０を入力するように指示する。
【００４４】
フレーズペア抽出手段１３２は、翻訳元言語の単語と翻訳先言語の単語との単語対応１１１に基づき、対訳コーパス１５０から、翻訳元言語と翻訳先言語において互いに同じ意味を有する単語または句の組合せをフレーズペア１１２として抽出するものである。抽出されたフレーズペア１１２は記憶手段１１に格納される。フレーズペア抽出手段１３２は、式（１）に示した翻訳元言語の単語列と翻訳先言語の単語列との対訳文に対して、ある単語対応ａが計算されたとき、式（７）に示すフレーズペアを抽出する。ここで、単語対応ａは、翻訳先言語の単語位置と翻訳元言語の単語位置の組の集合である。式（７）の「ｉ，ｍ，ｊ，ｎ」は整数を示し、単語対応ａとの間で式（８）の関係を満たすものである。
【００４５】
【数７】
【００４６】
【数８】
【００４７】
例えば、図２に示した対訳文の単語対応からは、以下のようなフレーズペアが抽出されることとなる。
【００４８】
【表２】
【００４９】
ルール作成手段１３３は、対訳コーパス１５０の中の対訳文ペア（対訳文の組合せ）ごとに、その対訳文ペアから抽出されフレーズペア１１２内に格納されたフレーズペアのリストをもとに、同期文脈自由文法のルールを作成し、ルール１１３に格納するものである。
【００５０】
つまり、非特許文献２、非特許文献５、特許文献１などの従来法では、「Ｘ→<γ,α,〜>」という形式の同期文脈自由文法のルールを用いていた。
それに対し、本実施形態では、「Ｘ→<γ,γ´,α,〜>」という形式のルールを用いる。
【００５１】
ここで、γおよびγ´は翻訳元言語の終端記号もしくは非終端記号の列、αは翻訳先言語の終端記号もしくは非終端記号の列を表す。γ、αはそれぞれ翻訳元言語、翻訳先言語の単語列を表現するが、γ´は翻訳元言語の単語列を翻訳先言語の語順に並び替えたものを表す。〜は、記号列γ、γ´、αに含まれる非終端記号の対応を表す。
【００５２】
一例として、非特許文献２、非特許文献５、特許文献１などの従来法で「Ｘ → <X1 を X2 に つなげる, connect X1 to X2 >」と表されるルールが、本実施形態のルール作成装置１ではどうなるかを説明する。ここで、(connect, つなげる), (to, に)という単語対応（単語対応１１１）があり、「を」に対応する英単語がないと仮定する。この場合、英単語に対応しない日本語単語の扱いにより、Ｘ→<γ,γ´,α,〜>の形のルールとして３つの形態が考えられる。
【００５３】
一つ目は、元の語順を保持しつつ先頭に移すという形態である。この場合、ルールは次のようになる。
Ｘ→<X1 を X2 に つなげる, に つなげるX1 を X2, connect X1 to X2 >
【００５４】
二つ目は、対応しない日本語単語を、左側の終端記号もしくは非終端記号に付随させるという形態である。この場合、ルールは、「を」を「X1」に付随させて次のようになる。
Ｘ→<X1 を X2 に つなげる, つなげるX1 を X2 に, connect X1 to X2 >
【００５５】
三つ目は、対応しない日本語単語を右側の終端記号もしくは非終端記号に付随させるという形態である。この場合、「を」を「つなげる」に付随させて次のようになる。
Ｘ→<X1 を X2 に つなげる, に つなげるX1 を X2, connect X1 to X2 >
この例では結果的に一つ目の形態と同一のルールとなっているが、一般的には、異なったルールがつくられる。
【００５６】
通常、機械翻訳は、「翻訳元言語の単語列Ｓを翻訳先言語の単語列Ｔに変換する問題」ととらえられている。それに対し、本実施形態では、新たに導入した同期文脈自由文法ルールにより、「翻訳元言語の単語列Ｓを、『翻訳元言語の文を翻訳先言語の語順に並び替えた単語列Ｓ´』および『翻訳先言語の単語列Ｔ』に同時に変換する問題」ととらえる。
【００５７】
以下では、特許文献１の拡張形態を記す。特許文献１にならい、ルール作成手段１３３に格納されるルールの翻訳先言語側は、終端記号で始まるものとする。また、ルール１１３に格納するルールは、重複を許すものとする。
【００５８】
ルール作成手段１３３は、フレーズペア
に対応して、式（９）〜式（９ｄ）のルールを生成する。このうち、式（９ａ）〜式（９ｄ）のルールは、式（９）のルールから自動的に生成することができる。また、式（９ａ）〜式（９ｄ）のルールに付与されるスコアについても、式（９）のルールと同一値を用いることができる。このような理由から、実装上は、式（９ａ）〜式（９ｄ）のルールは明示的にストレージに格納する必要がない。式（９ａ）〜式（９ｄ）のルールは、非特許文献２で用いられるグルー規則の非終端記号Ｘを、Ｘを左辺とする個々の規則で１回書き換えたものに対応している。
【００５９】
【数９】
【００６０】
ルール作成手段１３３は、式（９）および式（１０）で示すルールが生成され、かつ、式（１１）の関係を満たす場合、式（１２）で示すルールを生成する。
【００６１】
【数１０】
【００６２】
【数１１】
【００６３】
【数１２】
【００６４】
ここで、γ1、γ2およびγ´は翻訳元言語の終端記号もしくは非終端記号の列、αは翻訳先言語の終端記号もしくは非終端記号の列を表す。γ´は、γ1X（ｋ）γ2とα1X(k)α2の単語対応および非終端記号の対応をもとに、γ1X（ｋ）γ2をα1X(k)α2の終端記号・非終端記号の順番に並び替えたものである。
【００６５】
ここで、αには終端記号で始まらなければならないという制約を設ける。なお、本実施形態に必須のものではないが、ルール作成手段１３３は、例えば、以下の制約も採用する。第１に、γとαの両方とも、少なくとも１つの終端記号を含まなければならない。第２に、ルールは、最大２つの非終端記号を有することができる。しかし、翻訳元言語側のγで、非終端記号は隣接してはならない。
【００６６】
翻訳スコア計算手段１３４は、ルール１１３に重複を許して格納されているルールを数え上げ、各ルールｒに対応する翻訳確率Ｐe｜f（ｒ），Ｐf｜e（ｒ）と、レキシカル重みLex e｜f（ｒ），Lex f｜e（ｒ）とを計算し、それらを各ルールｒに対応づけてルールテーブル１１４に格納する。図３に、ルールテーブル１１４の一例を示す。また、表３にルールｒに対応した各翻訳確率、レキシカル重みの計算式を示す。このスコア計算は非特許文献２に倣ったものである。
【００６７】
【表３】
［具体例］
具体的には、ルール作成手段１３３は、図２に示した対訳文から表４に示すような規則（右辺だけ示す）を生成する。この例では、対応しない日本語単語を、左側の終端記号もしくは非終端記号に付随するものとしている。
【００６８】
【表４】
なお、モード判定手段１３１と、フレーズペア抽出手段１３２と、ルール作成手段１３３と、翻訳スコア計算手段１３４とは、ＣＰＵが記憶手段１１のＨＤＤ等に格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【００６９】
なお、単語並び替えモデル学習手段１４および翻訳元言語並べ替えモデル１１５の構成については、図４とともに後述する。
【００７０】
［ルール作成装置の動作］
次に、図１に示したルール作成装置１の動作について、図４を参照（適宜図１等参照）して説明する。図４に示すように、ルール作成装置１は、モード判定手段１３１によって、モードを判定する（ステップＳ１）。判定の結果、モードが「単語対応作成」モードの場合には（ステップＳ１で「単語対応作成」）、ルール作成装置１は、入出力手段１０を介して、対訳コーパス１５０を単語対応作成モジュール１２に入力し（ステップＳ２）、単語対応作成モジュール１２によって、単語対応を作成する（ステップＳ３）。作成された単語対応１１１は、記憶手段１１に格納される。
【００７１】
判定の結果、モードが「並び替えモデル作成」モードの場合には（ステップＳ１で「並び替えモデル作成」）、ルール作成装置１は、入出力手段１０を介して、対訳コーパス１５０を単語並び替えモデル学習手段１４に入力し（ステップＳ４）、対訳コーパス１５０と単語対応１１１を用いて、単語並び替えモデル学習手段１４によって、翻訳元言語並び替えモデルを作成する（ステップＳ５：評価モデル作成ステップ）。作成された翻訳元言語並び替えモデル１１５は、記憶手段１１に格納される。なお、後述する変形例では、さらに翻訳先言語並び替えモデル１１６も同時に記憶手段１１に格納される。
【００７２】
翻訳元言語並び替えモデル１１５としては、例えば、
を用いる。
【００７３】
ここでB[fi, fj]は実数値を返す関数で、単語fiがfjに先行するときに値が高くなり、逆のときに値が小さくなるようなもの（単語の並び順によって返す実数値が異なる関数）である。このような関数として、種々のものが考えられるが、例えば、「R. Tromble and J. Eisner, “Learning Linear Ordering Problems for Better Translation”, In Proc. the 47th ACL, p. 1007-1016, 2009.」に記載の手法（以下、「R. Trombleらの手法」と称する。）を用いて、対訳コーパスから自動的に学習することができる。このB[fi, fj]を用いて、翻訳元言語の文を翻訳先言語の語順に並び替えた単語の並びf1...fNを評価することができる。
【００７４】
このほかにも、翻訳元言語の文を翻訳先言語の語順に並び替えた単語列を評価するモデルとして、n-gramを用いることもできる。R. Trombleらの手法により、対訳コーパスの翻訳元言語の単語を翻訳先言語の語順にあらかじめ自動的に並び替え、その並び替えたものでn-gramを学習する。これは、R. Trombleらの手法で、B[fi, fj]の学習に用いたものと同じである。このように学習したn-gramで単語列Ｓ´の部分単語列fを評価する関数をh7(f)とし、これを式（４）の素性関数の一つとして用いる。
【００７５】
一方、判定の結果、モードが「ルールテーブル作成」モードの場合には（ステップＳ１で「ルールテーブル作成」）、ルール作成装置１は、入出力手段１０を介して、対訳コーパス１５０を制御手段１３に入力し（ステップＳ６）、フレーズペア抽出手段１３２によって、対訳コーパス１５０からフレーズペアを抽出する（ステップＳ７：フレーズペア抽出ステップ）。抽出されたフレーズペア１１２は、記憶手段１１に格納される。
【００７６】
続いて、ルール作成装置１は、ルール作成手段１３３によって、フレーズペア１１２に基づいて、同期文脈自由文法のルールを作成する（ステップＳ８：ルール作成ステップ）。作成されたルール１１３は、記憶手段１１に格納される。そして、ルール作成装置１は、翻訳スコア計算手段１３４によって、ルール１１３の各ルールから計算した各翻訳スコアを各ルールに対応付ける（ステップＳ９）。対応付けられたルールと翻訳スコアとは、ルールテーブル１１４として記憶手段１１に格納される。
【００７７】
なお、ルール作成装置１は、一般的なコンピュータに、前記した各ステップを実行させるルール作成プログラムを実行することで実現することもできる。このプログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００７８】
本実施形態のルール作成装置１により、翻訳元言語の単語列Ｓから、翻訳先言語の単語列Ｔ、および、それと同時に翻訳元言語の文を翻訳先言語の語順に並び替えた単語列Ｓ´の両方の語順を評価するモデル（翻訳元言語並べ替えモデル１１５）を合わせて導入することにより、翻訳先言語の語順をモデル化することができるようになる。
【００７９】
[機械翻訳装置の構成]
次に、機械翻訳装置について説明する。機械翻訳装置２は、ルール作成装置１（図１参照）で作成されたルールテーブル１１４を利用して、入力された翻訳元言語の単語列を、入力に対応する翻訳先言語の単語列に機械的に翻訳するものである。
【００８０】
図５に示すように、機械翻訳装置２は、入出力手段２０と、記憶手段２１と、素性重み学習モジュール２２（重み学習モジュール）と、単語情報抽出モジュール２３と、制御手段２４とを備え、これらは、例えば、ＣＰＵと、ＲＡＭと、ＲＯＭと、ＨＤＤと、入出力インタフェース等から構成される。
【００８１】
入出力手段２０は、入力装置Ｋから翻訳元言語の単語列を制御手段２４に入力したり、制御手段２４から、翻訳結果である翻訳先言語の単語列を出力装置Ｄに出力したりするものである。また、入出力手段２０は、単語対応付き素性重み学習用対訳コーパス２５０を素性重み学習モジュール２２に入力する。
なお、単語対応付き素性重み学習用対訳コーパス２５０は、ルール作成装置１（図１参照）がルールを作成する際に利用する対訳コーパス１５０とは別に用意するものである。
【００８２】
記憶手段２１は、例えば、ＣＰＵによる演算処理等に利用されるＲＡＭや、所定のプログラム、各種データベース、処理結果等を格納するＲＯＭやＨＤＤを備えている。例えば、記憶手段２１には、処理結果として、素性重み２１１と、単語情報２１２と、単語範囲付きルール２１３と、部分仮説２１４と、部分仮説スコア２１６とが格納される。
【００８３】
また、記憶手段１１には、ルール作成装置１（図１参照）で作成されたルールテーブル１１４と、翻訳元言語並べ替えモデル１１５と、別に予め作成された言語モデル２１５とが格納される。言語モデル２１５は、翻訳先言語としての確からしさを表すn‐gramを格納したものである。このn-gramは別途、膨大な量の翻訳先言語のコーパスから学習される。
【００８４】
素性重み学習モジュール２２は、単語対応付き素性重み学習用対訳コーパス２５０と、ルールテーブル１１４と、翻訳元言語並べ替えモデル１１５と、言語モデル２１５とに基づいて、各素性関数の値に対応した重みを学習し、学習結果を素性重み２１１として記憶手段２１に格納するものである。学習法としては、非特許文献１で提案されている方法が利用できる。
【００８５】
単語情報抽出モジュール２３は、入出力手段２０を介して入力装置Ｋから入力する翻訳元言語の文を単語単位に分割して、翻訳元言語の文を構成する単語についての情報（単語情報）を抽出するものである。単語情報は、例えば、単語列、単語位置、単語数等を含む。抽出された単語情報２１２は記憶手段２１に格納される。なお、入力装置Ｋから入力する翻訳元言語の文が単語分割済みの場合には、単語情報抽出モジュール２３を省略することもできる。
【００８６】
制御手段２４は、後記する手順で部分仮説を展開しながら文全体を被う仮説を求め、その中で最適（実際は準最適）なものを求めるものであり、ルール探索手段２４１と、単語範囲付きルール生成手段２４２と、部分仮説スコア算出手段２４３と、仮説探索手段２４４とを備えている。
【００８７】
ルール探索手段２４１は、所定の部分仮説を拡張するために適用可能なルールをルールテーブル１１４からそれぞれ探索するものである。
【００８８】
単語範囲付きルール生成手段２４２は、ルール探索手段２４１で探索されたルールに対して、入力された翻訳元言語の単語列を構成する単語の単語数と単語位置とに基づいて、探索されたルールの非終端記号が被う翻訳元言語の単語列の範囲を示す単語範囲を付加して、適用可能な単語範囲付きルールをそれぞれ生成するものである。
【００８９】
ここでは、入力された翻訳元言語の単語列の変換対象部分（非終端記号が被う範囲）を、その単語位置の左端（left）と右端（right）で、［ｌ，ｒ］のように表記することとする。初期段階では、例えば、入力が１１単語であれば、[ｌ，ｒ]＝[１，１１]となる。この場合、ルールの翻訳元言語側の各非終端記号の単語範囲（未翻訳の単語範囲）を［ｌ1，ｒ1］，［ｌ2，ｒ2］，…のように表記する。例えば、［ｌ1，ｒ1］＝[１，２]等となる。なお、あるルールの翻訳元言語側の非終端記号が２つあれば、単語範囲も２つ設定される。また、あるルールの翻訳元言語側の非終端記号に対して、「ｌ1」の値や「ｒ1」の値として、複数の可能性がある。
【００９０】
部分仮説スコア算出手段２４３は、単語範囲付きルールに含まれる翻訳先言語側の翻訳済み単語と単語範囲とを、新たな部分仮説として作成すると共に、適用可能なルールをトップダウンに適用し、且つ、適用可能なルールにおいて翻訳先言語側の非終端記号が文頭から文末に亘って並べられた順序で、新たな部分仮説を拡張し、ルールごとにそれぞれ予め求められた、翻訳の確からしさを表す翻訳モデルのスコアと、翻訳先言語の単語列としての確からしさを表す言語モデルのスコアと、翻訳元言語の文を翻訳先言語の語順に並び替えた単語列としての確からしさを表す言語モデルのスコアなどに基づいて、作成された部分仮説Ｈ′の評価値を示す部分仮説スコアを算出するものである。
【００９１】
具体的には、部分仮説スコア算出手段２４３は、「（ａ）翻訳先言語の文頭からの単語列」と「（ｂ）翻訳元言語の文を翻訳先言語の語順に並び替えた単語列」と、「翻訳元言語の単語列のうち未翻訳の単語の範囲を保持するスタック」の三つ組みからなる部分仮説Ｈをもとに、適用可能な単語範囲付きルールを使って、新たな部分仮説Ｈ′を作成することを繰り返す。
【００９２】
なお、ＨをもとにＨ′を作成することを部分仮説の拡張と呼ぶ。部分仮説が拡張されるのに従い、部分仮説中の翻訳先言語の文頭からの単語列は文頭から文末にかけて逐次的に追加される。また、部分仮説スコア算出手段２４３は、メモリを節約するため、他の部分仮説との間で単語列の共有を行う。なお、翻訳元言語の単語数がＪの場合、初期部分仮説（部分仮説の初期値）は、「空列」と、「［１，Ｊ］だけが積まれたスタック」とからなる。
【００９３】
部分仮説スコア算出手段２４３は、部分仮説Ｈ′の翻訳元言語の翻訳されている単語数をｍ（０≦ｍ≦Ｊ）とすると、優先度付きキューＱ0，Ｑ1，…，ＱJに部分仮説Ｈ′を入れる。つまり、部分仮説スコア算出手段２４３は、Ｑ0＝｛初期部分仮説｝から始めて、翻訳された翻訳元言語の単語数に同期して優先度付きキューＱmに格納する部分仮説を拡張していく。
【００９４】
部分仮説スコア算出手段２４３は、ある部分仮説を拡張するとき、そのスタックの先頭から（積まれた上方から）翻訳されていない翻訳元言語の単語範囲［ｌ，ｒ］をポップする。翻訳元言語の入力文に対応するルールはEarley法のチャート構造で管理する。チャート構造を用いることにより、部分仮説に対して適用可能なルールを効率良く見つけることが可能となる。例えば、部分仮説スコア算出手段２４３は、前記した式（９ｄ）から生成された式（１３）に示すような単語範囲つきルールから部分仮説を抽出する場合には、単語範囲［ｌ2，ｒ2］，［ｌ1，ｒ1］の順序でスタックにプッシュして、［ｌ1，ｒ1］が先に処理されるようにする。こうして、翻訳先言語側は、常に文頭から翻訳が生成されることが保証されることになる。
【００９５】
【数１３】
【００９６】
部分仮説スコア算出手段２４３は、もととなった部分仮説ＨのスコアＳ（Ｈ）に差分スコアを加算することで、式（１４）に示すような、拡張された部分仮説Ｈ′のスコアＳ（Ｈ′）を算出する。
【００９７】
【数１４】
ここで、ｍ（１≦ｍ≦Ｍ）は素性関数の値の識別番号を示す。本実施形態では、部分仮説スコア算出手段２４３は、Ｍ＝７として、表５に示す７つの素性関数の値ｈm（Ｈ′）と、そのｈm（Ｈ′）に対して対応する素性重みλm（Ｈ′）とを用いる。また、仮説を生成する際に、部分仮説の展開により新たに生成された翻訳先言語の単語列を、
と表記する。ここで、生成された翻訳先言語の単語列は、「ｉ」番目の単語から「ｉ＋ε」番目の単語で構成されている。また、ｈ７（Ｈ´）におけるＰＬＭ´は、対訳コーパスの翻訳元言語の文を翻訳先言語の語順に並び替えたものから学習するn-gram言語モデルである。
【００９８】
ここで、表５において、初期の仮説H0に対するhi(H0)は0であるものとする。
【表５】
【００９９】
表５で、ｈ７(・)は単語の並び替えモデル（翻訳元言語並べ替えモデル１１５）となっている。単語の並び替えモデルは、別な方法で表現することも可能である。以下、具体的に説明する。翻訳元言語の単語列Ｓを翻訳先言語の語順に並び替えた単語列をＳ´とする。また、fi,fjを単語列ＳおよびＳ´の単語であるとする。この仮定のもと、B[fi,fj]は、単語列Ｓ´において単語fiがfjに先行するときに大きな実数を、逆のときに小さな実数を返す関数とする。これを利用して翻訳元言語の単語並び替えをモデル化することができる。このような関数として、種々のものが考えられるが、例えば、R. Trombleらの手法を用いて、対訳コーパスから自動的に作成することができる。
【０１００】
このB[fi, fj]を用いることにより、表５に示すｈ７(・)と同様の働きをするｈ８(・)を次の式（１５）のように定義することができる。
【数１５】
ここで、ｆｋ（i+ε<k）は仮説のＳ´にまだ生成されていないＳの単語のことである。なお、ｈ８（Ｈ´）は、ｈ７（Ｈ´）の代わりに利用しても良いし、ｈ７（Ｈ´）と併用することもできる。
【０１０１】
また、表５において、ここで、Ｐe｜f（ｒ）、Ｐf｜e（ｒ）、Lexe｜f（ｒ）、Lexf｜e（ｒ）は、記憶手段２１のルールテーブル１１４に規定されているルールｒに対応した素性関数の値である。また、素性重みλmは、記憶手段２１に格納された素性重み２１１に予め規定されているものとする。
【０１０２】
つまり、本実施形態では、式（１４）と表５とから、部分仮説スコア算出手段２４３は、最終的に、部分仮説Ｈ′のスコアＳ（Ｈ′）を、次に示す式（１６）で算出する。式（１６）はh7(・)を用いた場合の例である。この式（１６）の２番目の等号の右辺は、もととなった部分仮説ＨのスコアＳ（Ｈ）に、差分スコアを加算することを示している。また、部分仮説スコア算出手段２４３は、優先度付きキューＱ0，Ｑ1，…，ＱJには、最大Ｙ個（例えば、1000個）の部分仮説しか保持しない。また、部分仮説スコア算出手段２４３は、部分仮説スコアＳ（Ｈ′）が優先度付きキューＱ0，Ｑ1，…，ＱJ内の最大の部分仮説スコアとある定数との積よりも小さい場合、その部分仮説Ｈ′を捨てる。これにより、部分仮説スコア算出手段２４３は、優先度付きキューＱ0，Ｑ1，…，ＱJに格納される各部分仮説に対して効果的な枝刈りを行うことができる。
【０１０３】
【数１６】
仮説探索手段２４４は、入力された翻訳元言語の単語列に対して適用可能な所定の部分仮説を探索し、所定の部分仮説を拡張することによって最終的に生成された翻訳元言語の文全体に対応する部分仮説（これを仮説と呼ぶ）のうちで、部分仮説スコアが最大となる仮説を探索するものである。具体的には、仮説探索手段２４４は、翻訳元言語の文全体から得られる所定数の仮説のうちで、仮説スコアが最大となる仮説Ｈ＾を、次の式（１７）の関係から探索する。式（１７）に示す仮説Ｈは、優先度付きキューＱJに含まれる部分仮説Ｈのことなので、式（１７）で求める仮説Ｈ＾は、部分仮説スコアＳ（Ｈ）の値を最大とする部分仮説Ｈ（つまり仮説Ｈ）として求めることができる。
【０１０４】
【数１７】
【０１０５】
また、仮説探索手段２４４は、求めた仮説に対応する翻訳先言語の文頭から文末までの単語列を翻訳結果として、入出力手段２０を介して出力装置Ｄに出力する。
【０１０６】
なお、ルール探索手段２４１、単語範囲付きルール生成手段２４２、部分仮説スコア算出手段２４３および仮説探索手段２４４は、ＣＰＵが記憶手段２１のＨＤＤ等に格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【０１０７】
［機械翻訳装置の動作］
図５に示した機械翻訳装置２の動作について、図６を参照（適宜図５参照）して説明する。図６に示すように、予め、機械翻訳装置２は、素性重み学習モジュール２２によって、単語対応付き素性重み学習用対訳コーパス２５０と、言語モデル２１５と、ルールテーブル１１４と、翻訳元言語並べ替えモデル１１５とに基づいて、素性関数の値の重みを学習し、学習結果である素性重み２１１を記憶手段２１に格納しておく。
【０１０８】
そして、機械翻訳装置２は、入力装置Ｋから入出力手段２０を介して入力された翻訳元言語の文を単語情報抽出モジュール２３に入力する（ステップＳ１１）。機械翻訳装置２は、単語情報抽出モジュール２３によって、入力された翻訳元言語の文（入力文）を単語に分割し、単語列、単語数Ｊやそれぞれの単語の単語位置を抽出する（ステップＳ１２）。抽出された単語列、単語数Ｊや単語位置は、単語情報２１２として記憶手段２１に格納される。
【０１０９】
機械翻訳装置２は、仮説探索手段２４４によって、初期部分仮説Ｈ0を作成し、入力単語数Ｊに合わせて、Ｊ＋１個の優先度付きキューＱ0，…，ＱJを空にして、そのうちの優先度付きキューＱ0に初期部分仮説Ｈ0を格納する（ステップＳ１３）。そして、機械翻訳装置２は、仮説探索手段２４４によって、初期部分仮説Ｈ0に対する部分仮説スコアＳ（Ｈ0）と、優先度付きキューの識別変数ｍとを初期化する。すなわち、Ｓ（Ｈ0）＝０，ｍ＝０とする（ステップＳ１４）。
【０１１０】
続いて、機械翻訳装置２は、ルール探索手段２４１によって、ｍ番目の優先度付きキューＱmから、そこに格納されている適用可能なそれぞれの部分仮説Ｈを順次ポップし、それぞれの部分仮説Ｈを拡張できるような適用可能なそれぞれのルールｒをルールテーブル１１４から探索する。そして、探索結果であるそれぞれのルールｒの翻訳元言語側に記述されている翻訳済単語の個数（翻訳済単語個数）Ｖ（ｒ）を取得し、現在の優先度付きキューの識別変数ｍの値に加算することによって、処理対象の部分仮説Ｈに対する翻訳済単語数ｎの値を更新する。すなわち、ｎ＝ｍ＋Ｖ（ｒ）とする（ステップＳ１５：ルール探索ステップ）。
【０１１１】
そして、機械翻訳装置２は、単語範囲付きルール生成手段２４２によって、探索したルールに対して適用可能なそれぞれの単語範囲付きルールｒ′を生成する（ステップＳ１６：単語範囲付きルール生成ステップ）。そして、機械翻訳装置２は、部分仮説スコア算出手段２４３によって、処理対象の部分仮説Ｈを、それぞれの単語範囲付きルールｒ′で展開して部分仮説Ｈ′をそれぞれ作成し、作成した部分仮説Ｈ′について前記した式（１６）に基づいて、式（１４）に示す部分仮説スコアＳ（Ｈ′）を算出する。式（１４）の右辺にｈｍがあり、表５にｈ７（Ｈ′）があることから、この部分仮説スコアには、翻訳元言語の単語列Ｓを翻訳先言語の語順を並び替えた単語列Ｓ´の部分単語列が影響していることがわかる。
【０１１２】
そして、作成した部分仮説Ｈ′を、ｎ番目の優先度付きキューＱnに格納し、所定の枝刈りを行う（ステップＳ１７：部分仮説スコア算出ステップ）。ここで、枝刈りによって不要となった部分仮説Ｈ′は、優先度付きキューＱnから削除される。また、算出された部分仮説スコアＳ（Ｈ′）は記憶手段２１の部分仮説スコア２１６に格納されるが、枝刈りによって削除された部分仮説Ｈ′に対する部分仮説スコアＳ（Ｈ′）は削除されることとなる。
【０１１３】
そして、機械翻訳装置２は、仮説探索手段２４４によって、適用可能な単語範囲付きルールｒ′をすべて選択したか否かを判別する（ステップＳ１８）。適用可能なｒ′がまだ存在する場合（ステップＳ１８：Ｎｏ）、機械翻訳装置２は、ステップＳ１６に戻る。
一方、ｒ′をすべて選択した場合（ステップＳ１８：Ｙｅｓ）、仮説探索手段２４４は、適用可能なルールｒをすべて選択したか否かを判別する（ステップＳ１９）。適用可能なｒがまだ存在する場合（ステップＳ１９：Ｎｏ）、機械翻訳装置２は、ステップＳ１５に戻る。
【０１１４】
一方、ｒをすべて選択した場合（ステップＳ１９：Ｙｅｓ）、仮説探索手段２４４は、適用可能な部分仮説Ｈをすべて選択したか否かを判別する（ステップＳ２０）。適用可能なＨがまだ存在する場合（ステップＳ２０：Ｎｏ）、機械翻訳装置２は、ステップＳ１５に戻る。一方、Ｈをすべて選択した場合（ステップＳ２０：Ｙｅｓ）、仮説探索手段２４４は、現在の優先度付きキューの識別変数ｍの値が入力単語数Ｊと等しい（ｍ＝Ｊ）か否かを判別する（ステップＳ２１）。ｍ≠Ｊである場合（ステップＳ２１：Ｎｏ）、機械翻訳装置２は、仮説探索手段２４４によって、優先度付きキューの識別変数ｍをインクリメントする。すなわち、ｍ＝ｍ＋１とする（ステップＳ２２）。続いて、ステップＳ１５に戻る。
【０１１５】
一方、ｍ＝Ｊである場合（ステップＳ２１：Ｙｅｓ）、Ｊ番目の優先度付きキューＱJには、翻訳元言語の文全体を被う部分仮説Ｈが複数格納されている。これら部分仮説Ｈは、翻訳元言語の文に対する仮説Ｈとみなすことができる。同様に、優先度付きキューＱJに格納された部分仮説Ｈに対する部分仮説スコアＳ（Ｈ）は、この意味で、仮説スコアＳ（Ｈ）と呼ぶ。そして、この場合、機械翻訳装置２は、仮説探索手段２４４によって、Ｊ番目の優先度付きキューＱJから仮説スコアＳ（Ｈ）の値が最大となる仮説Ｈを探索する（ステップＳ２３：仮説探索ステップ）。そして、機械翻訳装置２は、仮説探索手段２４４によって、探索された仮説を翻訳先言語の文として出力する（ステップＳ２４）。これにより、探索された仮説に対応する翻訳先言語の文頭から文末までの単語列が出力装置Ｄに出力される。
【０１１６】
なお、機械翻訳装置２は、一般的なコンピュータに、前記した各ステップを実行させる機械翻訳プログラムを実行することで実現することもできる。このプログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【０１１７】
［具体例］
図７と、表６と、表７と、表８とを参照して具体例について説明する。
図７は、図５に示した部分仮説から仮説への拡張例を示す図である。表６は、１１単語からなる翻訳元言語文を示し、表７は、表６に示した翻訳元言語文に対応して適用可能なルールを示す。なお、表７中の「ルールの種類」とは、前記した式（９）〜式（９ｄ）のいずれに対応するかを示すものである。表８は、表７に示したルールの適用順とそれに基づく単語範囲付きルールを示すものである。
【０１１８】
【表６】
【０１１９】
【表７】
【０１２０】
【表８】
初期状態において、部分仮説スコア算出手段２４３は、スタックを空にし、図７に示すように、状態「０」で翻訳元言語の単語列（文）全体を被う単語範囲［１，１１］をプッシュする。状態「０」では、部分仮説Ｈ′（０）は、初期部分仮説なので、スタックにプッシュした単語範囲［１，１１］と空列との組である。部分仮説Ｈ′（０）の部分仮説スコアＳ（Ｈ′）は「０」とする。
【０１２１】
次に、状態「１」で、部分仮説スコア算出手段２４３は、スタックから範囲［１，１１］をポップし、ルール探索手段２４１は、表７から、ポップされた範囲に適用可能なルールｒ（３）を選択する。ルールｒ（３）における翻訳解「The」に対応した「は」の入力文における単語位置は、「３」なので、単語範囲付きルール生成手段２４２は、表８に示すように、ルールｒ（３）における非終端記号Ｘ(1)および非終端記号Ｘ(2)の単語範囲が、それぞれ［１，２］、［４，１１］となるような単語範囲付きルールｒ′（３）を生成する。
【０１２２】
この単語範囲付きルールｒ′（３）では、翻訳先言語側において非終端記号Ｘ(1)が非終端記号Ｘ(2)より先に処理されなければならない。そのため、部分仮説スコア算出手段２４３は、図７に示すように、単語範囲付きルールｒ′（３）において、非終端記号Ｘ(2)に対応する単語範囲［４，１１］をスタックにプッシュしてから、非終端記号Ｘ(1)に対応する単語範囲［１，２］をプッシュする。部分仮説スコア算出手段２４３は、スタックにプッシュした単語範囲［１，２］、［４，１１］と、翻訳先言語の文頭からの単語列としての翻訳解「The」とを部分仮説Ｈ′（１）とする。部分仮説スコア算出手段２４３は、部分仮説Ｈ′（１）について部分仮説スコアを算出する。
【０１２３】
次に、状態「２」で、部分仮説スコア算出手段２４３は、スタックから単語範囲［１，２］をポップし、ルール探索手段２４１は、表７から、この単語範囲に適用可能なルールｒ（１）を選択する。ルールｒ（１）における翻訳解「international」に対応した「国際」の入力文における単語位置は、「１」なので、単語範囲付きルール生成手段２４２は、表８に示すように、ルールｒ（１）における非終端記号Ｘ(1)の単語範囲が［２，２］となるような単語範囲付きルールｒ′（１）を生成する。部分仮説スコア算出手段２４３は、図７に示すように、単語範囲付きルールｒ′（１）において、単語範囲［２，２］をスタックにプッシュする。部分仮説スコア算出手段２４３は、スタックにプッシュした単語範囲［２，２］と、以前プッシュした単語範囲［４，１１］と、翻訳先言語の文頭からの単語列としての翻訳解「The international」とを部分仮説Ｈ′（２）とする。部分仮説スコア算出手段２４３は、部分仮説Ｈ′（２）について部分仮説スコアを算出する。
【０１２４】
次に、状態「３」で、部分仮説スコア算出手段２４３は、スタックから単語範囲［２，２］をポップし、ルール探索手段２４１は、表７から、この単語範囲に適用可能なルールｒ（２）を選択する。ルールｒ（２）には「テロ」に対応した翻訳解「terrorism」が記述されているが、非終端記号が無いので、単語範囲付きルール生成手段２４２は、ルールｒ（２）をそのまま単語範囲付きルールｒ′（２）とする。部分仮説スコア算出手段２４３は、単語範囲付きルールｒ′（２）において単語範囲が指定されていないのでスタックに対する操作を行わない。部分仮説スコア算出手段２４３は、図７に示すように、スタックに以前プッシュした単語範囲［４，１１］と、翻訳先言語の文頭からの単語列としての翻訳解「The international terrorism」とを部分仮説Ｈ′（３）とする。部分仮説スコア算出手段２４３は、部分仮説Ｈ′（３）について部分仮説スコアを算出する。
【０１２５】
以下、同様にして、表８に記載した適用順に、状態「４」から状態「９」に対応する操作を行うと、スタックが空になるので、部分仮説スコア算出手段２４３は、部分仮説の展開を終了し、仮説を生成する。このとき、翻訳先言語の文頭からの単語列としての翻訳解は、以下のように、１０単語の単語列となる。
「The international terrorism also is a possible threat in Japan」
【０１２６】
ここで、ルールｒ（９）は、２つの終端記号（単語）「で ある，is a」を有しているため、部分仮説スコア算出手段２４３は、９回の状態遷移で１０単語を訳出する。図７では、部分仮説展開の過程で、翻訳先言語側が文頭から文末にかけて生成されたことが示されている。
【０１２７】
本実施形態の機械翻訳装置２によれば、入力された翻訳元言語の単語列において未翻訳の部分に対して部分仮説を順次拡張する際に、翻訳元言語の単語列を翻訳先言語の語順に並び替えたものを同時に生成する。そのため、翻訳元言語の単語列の翻訳先言語の語順への並び替えの尤もらしさを、部分仮説の評価に活用することができて、副作用の少ない仮説の枝狩りが可能となる。その結果、翻訳速度を向上させることや、翻訳先言語の単語列の翻訳精度を向上させることが可能となる。換言すれば、翻訳元言語並べ替えモデル１１５を考慮してスコアを算出することで、高い翻訳精度を実現することができる。
【０１２８】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。以下、変形例について説明する。
【０１２９】
〔変形例〕
次に、ルール作成装置１と機械翻訳装置２の変形例について説明する。例えば、ルール作成装置１の単語並び替えモデル学習手段１４において、翻訳元言語並び替えモデル１１５の代わりに翻訳先言語の語順を並び替えた翻訳先言語並び替えモデル１１６を作成し、式（１０）〜式（１２）のｒ´の代わりにα´（翻訳先言語の単語列を翻訳元言語の語順に並び替えた単語列）に置き換えたルールを利用することができる。
【０１３０】
この場合、機械翻訳装置２では、翻訳先言語の単語列を翻訳元言語の語順に並び替えた単語列の部分単語列e´に対して表５のｈ７(・)や式（１５）のｈ８（・）に相当する素性関数を定義し（ｈ７´(・)，ｈ８´（・）とおく）、これを素性関数として活用することができる。
【０１３１】
ただし、部分仮説H´に対するｈ８´（H´）の計算は、e´が文頭から文末にかけて単調に生成されないため、やや異なった処理が必要となる。e´の生成例を図８に示す。図８に示すように、スタックからポップされた単語範囲が一部、単語列に置き換わり、新たな単語範囲がスタックにプッシュされるということを繰り返す。状態５の仮説Hが状態６の仮説H´に展開されたときのｈ８´（H´）の計算には、次の式（１８）を用いる。
【０１３２】
【数１８】
【０１３３】
さらに、状態４の仮説Hが状態５の仮説H´に展開されたときのｈ８´（H´）の計算には、次の式（１９）を用いる。
【０１３４】
【数１９】
これらの例のように、仮説展開に伴うｈ８´（H´）の差分は、仮説展開に伴って具体化した単語列内と、その単語列とすでに具体化している単語列の間でB[・,・]を計算することで求めることができる。
【０１３５】
ｈ７´（H´）の計算は、e´が左から右に単調に生成されるわけでないため、自明ではないが、非特許文献５にある言語モデル・スコアの計算方法により実現できる。
さらなる変形例として、（ｂ）翻訳元言語の文を翻訳先言語の語順に並び替えた単語並びモデル（翻訳元言語並べ替えモデル１１５）と、（ｃ）翻訳先言語の文を翻訳元言語の語順に並び替えた単語並びモデル（翻訳先言語並べ替えモデル１１６）の両方を活用することも可能である。この場合、Ｘ→<γ,γ´,α´,α,〜>の形式のルールを用い、ｈ７´（H´）とｈ８´（H´）の両方を素性関数として用いる。
【０１３６】
〔その他の変形例：非特許文献２の拡張形態〕
以上で説明したルール作成装置および機械翻訳装置の代わりに、非特許文献２のアルゴリズムを採用したルール作成装置および機械翻訳装置も可能である。この場合、ルールはボトムアップに適用される。
【０１３７】
翻訳元言語の文を翻訳先言語の語順に並び替えたものと、翻訳先言語の文を翻訳元言語の語順に並び替えたものの両方を利用するために、ルールは次の形式のものを用いる。
Ｘ→＜γ,γ´,α´,α,〜＞
γは翻訳元言語の終端記号もしくは非終端記号の列を、αは翻訳先言語の終端記号もしくは非終端記号の列を、γ´は翻訳元言語の終端記号もしくは非終端記号の列を翻訳先言語の語順に並び替えたものを、α´は翻訳先言語の終端記号もしくは非終端記号の列を翻訳元言語の語順に並び替えたものを表す。
【０１３８】
このボトムアップアルゴリズムでは、仮説Ｈは、
X:[i,j]→<f´,e´,e>
のように表される。Xは非終端記号、[i, j]はそれが覆う翻訳元言語の文の単語範囲、f´は翻訳元言語の単語列を翻訳先言語の語順に並び替えた単語列、e´は翻訳先言語の単語列を翻訳元言語の語順に並び替えた単語列、eは翻訳先言語の単語列を表す。
【０１３９】
ボトムアップな仮説の展開の様子を例で示す。仮説Hはルール
X→< X1 で ある, で ある X1, X1 is a, is a X1>
によって展開され、より広い範囲をカバーする仮説H´を生成する。例えば、次の通りである。
H: X:[7,9]→<起こり うる 脅威, possible threat, possible threat>
H´: X:[7,11]→<で ある 起こり うる 脅威, possible threat is a, is a possible threat>
f´およびe´を利用して、ｈ７, ｈ８やｈ´７, ｈ´８を展開前の仮説の値からの差分を計算することで、展開後の仮説の値を計算することができる。
【０１４０】
〔eとe´を用いた素性重み学習の形態〕
非特許文献１は、素性重み学習用対訳コーパス（単語対応付き素性重み学習用対訳コーパス２５０に対応）中の翻訳元の文と正解翻訳文のペアを利用し、素性重みを学習する「素性重み学習モジュール（素性重み学習モジュール２２に対応）」の実現法について記述している。この手法では、目的関数を最適化するように重みが学習される。通常、目的関数としては、翻訳した文章（複数の文の列）eと正解文章reとの近さを表す関数が使われ、具体的には前記したＢＬＥＵ(e, re)などが広く利用されている。
【０１４１】
本実施形態の機械翻訳装置２では、翻訳文章eと同時に、翻訳元言語の文を翻訳先言語の語順に並び替えた文からなる文章f´と、翻訳先言語の文を翻訳元言語の語順に並び替えた文からなる文章e´が同時に得られる。f´の正解をrf´、e´の正解をre´とすると、l1BLEU(f´, rf´) + l2BLEU(e´, re´) + l3BLEU(e, re) （l1+l2+l3 = 1）を目的関数として、素性hi(・)の素性重みλiを学習する。
【０１４２】
パラメータli（i=1,2,3)の求め方は様々な方法が考えられるが、あらかじめ開発用対訳データで翻訳実験を行い、そこでの翻訳精度（ＢＬＥＵ（「K. Papineni, S. Roukos, T. Ward and W-J. Zhu, “BLEU: a Method for Automatic Evaluation of Machine Translation”, In Proc. of the 40thACL, 2002」参照）で測定）が高くなるように設定する。
【０１４３】
f´の正解であるrf´は、文fとreの対応する文reとの単語対応を求め、それをもとに、文fを文reの言語の語順に並び替えることで求めることができる。もし、文fの単語で文reに対応するものがなければ、語順を保持しつつ文頭に移す、右側の語に付随させる、左側の語に付随させるなどの形態がある。e´の正解であるre´についても、同様に求めることができる。
【０１４４】
なお、本実施形態では、日英の翻訳を例に説明したが、これに限定されるものではない。ルール作成装置によりルールを作成すれば、任意の多言語間でこの翻訳装置を使用することが可能である。
【実施例】
【０１４５】
非特許文献２の技術を実装したシステム(baseline)に、式（１５）のｈ８(・)を素性として加えた。ルール中の対応のとれない単語について、元の語順を保持しつつ先頭に移した形態のシステムを”Baseline+move-to-front”、左側の終端記号もしくは非終端記号に付随させる形態のシステムを”Baseline+attach”とする。
【０１４６】
約20万文の対訳コーパス１５０からルールテーブル１１４を学習し、約1000文の単語対応付き素性重み学習用対訳コーパス２５０を用いて、機械翻訳装置２の素性重み学習モジュール２２が素性重みを学習した。機械翻訳装置２によって約1000文のテスト用対訳コーパスの翻訳元言語の文を翻訳した結果を、そのテスト用対訳コーパスの翻訳先言語の文を正解としてＢＬＥＵで評価した結果を表９に示す。
【０１４７】
ＢＬＥＵの値が大きいほど、良い翻訳であることを示す。表９に示したように
【表９】
、素性ｈ８(・)の追加は翻訳精度の向上に有効であった。
【符号の説明】
【０１４８】
１ ルール作成装置
２ 機械翻訳装置
１０ 入出力手段
１１ 記憶手段
１１１ 単語対応
１１２ フレーズペア
１１３ ルール
１１４ ルールテーブル
１２ 単語対応作成モジュール
１３ 制御手段
１３１ モード判定手段
１３２ フレーズペア抽出手段
１３３ ルール作成手段
１３４ 翻訳スコア計算手段
１５０ 対訳コーパス
２０ 入出力手段
２１ 記憶手段
２１１ 素性重み
２１２ 単語情報
２１３ 単語範囲付きルール
２１４ 部分仮説
２１５ 言語モデル
２１６ 部分仮説スコア
２２ 素性重み学習モジュール
２３ 単語情報抽出モジュール
２４ 制御手段
２４１ ルール探索手段
２４２ 単語範囲付きルール生成手段
２４３ 部分仮説スコア算出手段
２４４ 仮説探索手段
２５０ 素性重み学習用対訳コーパス
Ｋ 入力装置
Ｄ 出力装置
【技術分野】
【０００１】
本発明は、機械翻訳装置、機械翻訳方法、およびそのプログラムに関する。
【背景技術】
【０００２】
従来、統計モデルを用いて機械翻訳を実現する技術（統計的機械翻訳）が知られている（例えば、非特許文献１〜４）。
統計的機械翻訳では、翻訳元言語の単語列（文）が与えられたとき、翻訳確率を最大化するような翻訳先言語の単語列（文）を探索する問題として定式化される。ここで、翻訳確率を対数線形モデルで表現すると、最終的に統計的機械翻訳は式（１）で定式化される。
【０００３】
【数１】
【０００４】
ここで、翻訳元言語の単語列には、各単語位置に整数「１」〜「Ｊ」の識別符号が付与されている。すなわち、翻訳元言語の単語列は、「Ｊ」個の単語から構成される。なお、翻訳元言語が日本語の場合には、翻訳元言語の単語列は、「Ｊ」個の自立語、付属語、句読点（「。」「、」）から構成されることとなる。また、翻訳先言語の単語列には、各単語位置に整数「１」〜「Ｉ」の識別符号が付与されている。すなわち、翻訳先言語の単語列は、「Ｉ」個の単語から構成される。また、ｍ（１≦ｍ≦Ｍ）は、素性関数を識別するための整数を示し、Ｍは、素性関数の個数を示す。また、各素性関数は、翻訳としての確からしさを表すものや、翻訳先言語としての確からしさを表すもの等である。単語列集合Ｅは、翻訳先言語の単語のあらゆる組合せで生成可能なすべての単語列集合を表す。各素性重みλmは、誤り最小化学習法等を用いて素性重み学習用対訳コーパスにおける翻訳精度の値が最大になるように設定される（例えば、非特許文献１参照）。
【０００５】
翻訳元言語の文から翻訳先言語の文への翻訳に対して、重み付き同期文脈自由文法（weighted synchronous context-free grammar）を利用して、翻訳元言語の文と翻訳先言語の文との対応付けをモデル化する方法が知られている（例えば、非特許文献２参照）。
重み付き同期文脈自由文法は、式（２）に示すルールに、重みが付いたものの集合からなるものである。
【０００６】
【数２】
【０００７】
ここで、矢印の左辺のＸは、非終端記号を示す。矢印の右辺のγは、終端記号または非終端記号から構成された記号列であって翻訳元言語に対応している。また、αは、終端記号または非終端記号から構成された記号列であって翻訳先言語に対応している。また、「〜」は、記号列γに含まれる非終端記号と、記号列αに含まれる非終端記号との一対一の対応関係を表している。ここでは、記号列γに含まれる非終端記号の個数と、記号列αに含まれる非終端記号の個数とは同じものとする。
【０００８】
式（２）に示したルールの具体例を表１に示す。ここで、Ｘ(k)は、非終端記号であり、ｋ（ｋ＝１，２，…）は、翻訳元言語の非終端記号の配置と、翻訳先言語の非終端記号の配置との対応関係を示している。
【０００９】
【表１】
【００１０】
非特許文献２に記載された方法の特殊な形として、式（３）に示す形式のルールだけを用いた方法も知られている（非特許文献３参照）。非特許文献３に記載された方法は、句単位で統計的機械翻訳を行うものであり、フレーズペアに基づく翻訳方法である。この方法では、抽出されたフレーズペアの集合から同期文脈自由文法を生成する際に、式（３）に示す形式のルールだけ用いる。このルールの形式に依存して解探索を行う場合には、効率的なビームサーチの手法が利用可能である（非特許文献４参照）。非特許文献４に記載の方法では、解探索において、翻訳された単語範囲を、翻訳済みの単語の位置をマークしたビット列で表現してメモリに保持している。
【００１１】
【数３】
【００１２】
重み付き同期文脈自由文法を利用した従来のモデル化では、重み付き同期文脈自由文法の導出Ｄを用いて、翻訳元言語の単語列と翻訳先言語の単語列とをそれぞれｆ（Ｄ）、ｅ（Ｄ）と記述する。ここで、例えば、翻訳元言語の単語列ｆ（Ｄ）の「ｉ」番目の単語から「ｊ」番目の単語を被うルールをｒとすると、導出Ｄは、三つ組＜ｒ，ｉ，ｊ＞の集合で表される。
【００１３】
そして、非特許文献２のモデル化では、統計的機械翻訳を定式化した式（１）を導出ベースに修正した式（４）を用いる。この定式化では、翻訳元言語の単語列が与えられたとき、素性関数と素性重みとの積の線形和が最大となるような導出Ｄ＾を求めたときに、それに対応するｅ（Ｄ＾）が翻訳結果となる。ここで、記号「＾（ハット）」は、文字「Ｄ」の上に付される記号を示し、本明細書では、以下、記号「＾（ハット）」を同様な意味で使用する。
【００１４】
【数４】
【００１５】
式（４）に示す各素性関数の値ｈm（Ｄ）に何を用いるかについては、様々なバリエーションが考えられる。例えば、以下の６つの関数の値の自然対数loge（以下、lnと表記する）を用いる場合がある（例えば、非特許文献３参照）。これら６つの関数の値とは、式（５）に示す翻訳確率Ｐe｜f（Ｄ），Ｐf｜e（Ｄ）と、式（６）に示すレキシカル重みLexe｜f（Ｄ），Lexf｜e（Ｄ）と、n-gram言語モデルの確率ＰLM（ｅ（Ｄ））と、フレーズペナルテイexp（length（ｅ（Ｄ）））である。ここで、length（・）は、単語数を返す関数を示す。
【００１６】
【数５】
【数６】
【００１７】
翻訳確率Ｐe｜f（Ｄ），Ｐf｜e（Ｄ）と、レキシカル重みLexe｜f（Ｄ），Lexf｜e（Ｄ）とは、翻訳としての確からしさを評価するための値であり、翻訳モデルとも呼ばれている。詳細には、例えば、翻訳確率Ｐe｜f（Ｄ）は、式（５）に示すように、導出Ｄに含まれるルールｒごとの確率Ｐ（α｜γ）をルールごとのスコアとして、導出Ｄに含まれるすべてのルールｒについてルールごとのスコアを積算したものである。
【００１８】
例えば、非特許文献２に記載された方法では、翻訳における解探索を次の手順で行う。まず、ＣＫＹ（Cocke-Kasami-Younger）法に基づくボトムアップ構文解析において、同期文脈自由文法の翻訳元言語側のルールを、翻訳元言語の単語列に適用し、翻訳元言語の構文解析木を得る。そして、翻訳元言語の構文解析木に対応する同期文脈自由文法の最適な導出Ｄ＾を、前記した式（４）に基づいて求め、その最適な導出Ｄ＾に基づいて翻訳先言語の単語列を生成する。ただし、統計的機械翻訳の解探索において解の候補（以下、仮説と称する。）は膨大であるため、計算量の観点から、全探索をして真の最適解を求めることは事実上不可能となっている。そこで、従来、解探索の過程で部分的に構成された、同期文脈自由文法の部分木の導出Ｄに対して所定の枝刈りを実行しながら処理をすすめて準最適解を求めることとしている。
【００１９】
また、非特許文献５では、ＣＫＹ法に基づくボトムアップ構文解析のアルゴリズムを基に、cube pruningという手法で効率的に準最適解を求める方法を提案している。
【００２０】
また、特許文献１では、解探索において副作用の少ない枝狩りを実現するべく、非特許文献５とは別の方法を提案している。副作用の少ない枝刈りを実現するためには、前記した式（４）に示される導出Ｄの仮説の尤度を正確に見積もることが必要である。その際に、翻訳精度を向上させるために、素性関数の１つとして、翻訳先言語のn-gram言語モデルを用いることが重要である。そのため、仮説のもととなる部分仮説のスコアとして、n-gram言語モデルのスコアを有効利用するために、特許文献１では、翻訳先言語の文頭から文末にかけて逐次的に生成されることを保障する、解探索方法を提案している。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００８−１５８４４号公報
【非特許文献】
【００２２】
【非特許文献１】Franz Josef Och, “Minimum Error Rate Training in Statistical Machine Translation”, In Proc. of ACL 2003, p. 160-167, Sapporo, Japan, July 2003
【非特許文献２】David Chiang, “A Hierarchical Phrase-Based Model for Statistical Machine Translation”, In Proc. of ACL 2005, p. 263-270, Ann Arbor, Michigan, June 2005
【非特許文献３】Philipp Koehn, Franz Josef Och, and Daniel Marcu, “Statistical Phrase-Based Translation” In Proc. of NAACL 2003, p. 48-54、Edmonton, Canada, 2003
【非特許文献４】Philipp Koehn, “Pharaoh: A Beam Search Decoder for Phrase-Based Statistical Machine Translation Models”, In Proc. of the 6th Conference of the Association for Machine Translation in the Americas(AMTA), p. l15-124, September-October 2004
【非特許文献５】David Chiang, “Hierarchical Phrase-Based Translation”, Computational Linguistics, Vol. 33, No. 2, pages 201-228, 2007.
【発明の概要】
【発明が解決しようとする課題】
【００２３】
従来技術では、単語の並び替えの尤もらしさと訳語選択の尤もらしさの両方を、式（２）のルールに対する重みという形でモデル化している。しかし、これだけでは単語の並び替えに関するモデル化が弱いため、日本語から英語などのように語順の大きく異なる言語間の翻訳精度が十分でないという問題がある。
【００２４】
そこで、本発明では、前記した問題を解決し、高い翻訳精度の機械翻訳技術を提供することを課題とする。
【課題を解決するための手段】
【００２５】
前記課題を解決するために、本発明は、同期文脈自由文法を用いて翻訳元言語の単語列から翻訳先言語の単語列を生成するルールが複数格納されたルールテーブルを利用して、入力された翻訳元言語の単語列の翻訳結果である前記入力に対応する翻訳先言語の単語列として、所定の部分仮説からそれよりも長い新たな部分仮説を順次作成して前記所定の部分仮説を拡張することによって最終的に生成された部分仮説である仮説を出力する機械翻訳装置である。前記部分仮説は、（ａ）翻訳候補となる翻訳先言語の単語列と、少なくとも、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列、および、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列、のいずれかと、を考慮して作成されるものである。機械翻訳装置は、前記所定の部分仮説を拡張するために適用可能なルールを前記ルールテーブルからそれぞれ探索するルール探索手段と、前記探索されたルールの翻訳元言語側に対して、前記入力された翻訳元言語の単語列を構成する単語の単語数と単語位置とに基づいて、前記探索されたルールの非終端記号が被う翻訳元言語の単語列の範囲を示す単語範囲を付加して、適用可能な単語範囲付きルールをそれぞれ生成する単語範囲付きルール生成手段と、前記適用可能なルールを適用し前記新たな部分仮説を拡張し、前記ルールごとにそれぞれ予め求められた、翻訳の確からしさを表す翻訳モデルのスコアと、前記（ａ）の単語列としての確からしさを表す言語モデルのスコアと、少なくとも、前記(ｂ)の単語列としての確からしさを表す言語モデルのスコア、および、前記(ｃ)の単語列としての確からしさを表す言語モデルのスコア、のいずれかと、に基づいて、前記作成された部分仮説の評価値を示す部分仮説スコアを算出する部分仮説スコア算出手段と、前記入力された翻訳元言語の単語列に対して適用可能な所定の部分仮説を探索し、前記所定の部分仮説を拡張することによって最終的に生成された部分仮説のうちで、前記部分仮説スコアが最大となる部分仮説を、前記仮説として探索する仮説探索手段と、を備える。
【００２６】
かかる発明によれば、入力された翻訳元言語の単語列において未翻訳の部分に対して部分仮説を順次拡張する際に、（ａ）翻訳候補となる翻訳先言語の単語列だけでなく、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列や、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列も用いて部分仮説を評価する。このため、翻訳元言語の翻訳先言語の語順への並び替えの尤もらしさや、翻訳先言語の翻訳元言語の語順への並び替えの尤もらしさを、部分仮説の評価に活用することができ、翻訳の精度や速度を向上させることができる。
【００２７】
また、本発明は、前記（ａ）の単語列、前記(ｂ)の単語列、および、前記(ｃ)の単語のそれぞれについて、所定の評価モデルを用いて、当該単語列とその正解との近さを考慮して、素性の重みを予め生成する重み学習モジュールを、さらに備える。
【００２８】
かかる発明によれば、より精度の高い機械翻訳を行うための準備として、素性の重みを予め生成することができる。
【００２９】
また、本発明は、前記部分仮説スコア算出手段が、前記重みを用いて前記部分仮説スコアを算出する。
【００３０】
かかる発明によれば、部分仮説スコア算出手段は、前記重みを用いることで、部分仮説スコアをより高い精度で算出することができる。
【００３１】
また、本発明は、コンピュータを機械翻訳装置として機能させるためのプログラムである。これにより、このプログラムをインストールされたコンピュータは、このプログラムに基づいた各機能を実現することができる。
【発明の効果】
【００３２】
本発明によれば、高い翻訳精度の機械翻訳技術を提供することができる。
【図面の簡単な説明】
【００３３】
【図１】本発明の実施形態に係るルール作成装置の構成を示す機能ブロック図である。
【図２】日英の対訳の単語対応の例を示す図である。
【図３】図１に示したルールテーブルの例を示す図である。
【図４】図１に示したルール作成装置の動作を示すフローチャートである。
【図５】本発明の実施形態に係る機械翻訳装置の構成を示す機能ブロック図である。
【図６】図５に示した機械翻訳装置の動作を示すフローチャートである。
【図７】部分仮説から仮説への拡張例を示す図である。
【図８】部分仮説から仮説への拡張例を示す図である。
【発明を実施するための形態】
【００３４】
以下、図面を参照して本発明の機械翻訳装置および機械翻訳方法、ならびにルール作成装置およびルール作成方法を実施するための形態（以下「実施形態」と称する。）について詳細に説明する。以下では、ルール作成装置およびルール作成方法と、機械翻訳装置および機械翻訳方法とに分けて順次説明を行う。
【００３５】
［ルール作成装置の構成］
ルール作成装置は、翻訳元言語の単語列（文）を翻訳先言語の単語列（文）に機械的に翻訳する機械翻訳装置で利用するルールを作成するものである。以下では、翻訳元言語を日本語、翻訳先言語を英語として説明する。
【００３６】
図１に示すように、ルール作成装置１は、入出力手段１０と、記憶手段１１と、単語対応作成モジュール１２と、制御手段１３と、単語並び替えモデル学習手段１４とを備え、これらは、例えば、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、ＨＤＤ（Hard Disk Drive）と、入出力インタフェース等から構成される。
【００３７】
入出力手段１０は、対訳コーパス１５０を単語対応作成モジュール１２に入力したり、演算処理の結果や記憶手段１１に記憶されたデータ等を出力装置Ｄに出力したりするものである。また、入出力手段１０は、入力装置Ｋから、所定のコマンド（モード選択コマンドや動作コマンド等）を制御手段１３に入力する。本実施形態では、モード選択コマンドは、「単語対応作成」モードを選択するコマンドと、「ルールテーブル作成」モード、「並び替えモデル作成」モードを選択するコマンドとを含む。
対訳コーパス１５０は、互いに同じ意味を有する翻訳元言語の単語列と翻訳先言語の単語列との組合せのデータを複数備える。
【００３８】
記憶手段１１は、例えば、ＣＰＵによる演算処理等に利用されるＲＡＭや、例えば、所定のプログラム、各種データベース、処理結果等を格納するＲＯＭやＨＤＤを備えている。例えば、記憶手段１１には、処理結果として、単語対応１１１と、フレーズペア１１２と、ルール１１３と、ルールテーブル１１４と、翻訳元言語並び替えモデル１１５（所定の評価モデル）とが格納される。なお、翻訳先言語並び替えモデル１１６（所定の評価モデル）については、本実施形態の変形例の項で説明する。
【００３９】
単語対応作成モジュール１２は、「単語対応作成」モードを選択するコマンドが入力されたときに、対訳コーパス１５０から得られる単語共起に関する統計量を活用し、多対多（翻訳元言語または翻訳先言語の単語がどこにも対応付かないことを含む）の単語対応１１１を自動的に求めるものである。単語対応作成モジュール１２は、多対多の単語対応１１１を求めるために、例えば、単語単位の翻訳モデルを活用して、文全体で最適な１対多対応と多対１対応とを求め、その両者を組合せる。組合せ方の一例としては、１対多対応と多対１対応とのインターセクションを使い、それに隣接する１対多対応と多対１対応とのユニオンの要素を追加する方法がある（非特許文献３参照）。
【００４０】
なお、単語単位の翻訳モデルについては、「Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. “The mathematics of statistical machine translation: Parameter estimation”, Computational Linguistics, 19(2):263-311, 1993」に記載されている。また、対訳コーパス１５０自体が単語対応１１１の情報を保持している場合には、単語対応作成モジュール１２を省略した構成としてもよい。
【００４１】
図２に、日英（日本語と英語）の対訳の単語対応の例を示す。８個の単語および句点（ピリオド）を示す黒丸が単語対応である。日本語は、「違憲 の 問題 について は 、 連邦 憲法 裁判所 が 決定 する 。」である。その対訳である英語は、「The Federal Constitutional Court decides on the question of unconstitutionality .」である。
【００４２】
図１に戻って、制御手段１３は、モード判定手段１３１と、フレーズペア抽出手段１３２と、ルール作成手段１３３と、翻訳スコア計算手段１３４とを備えている。
【００４３】
モード判定手段１３１は、入力装置Ｋから入出力手段１０を介して入力したモード選択コマンドの示すモードを判定するものである。モード判定手段１３１は、モードが「単語対応作成」モードの場合には、単語対応作成モジュール１２に対して対訳コーパス１５０を入力するように指示する。また、モード判定手段１３１は、モードが「並び替えモデル作成」モードの場合には、単語並び替えモデル学習手段１４に対して翻訳元言語並べ替えモデル１１５を作成するように指示する。また、モード判定手段１３１は、モードが「ルールテーブル作成」モードの場合には、フレーズペア抽出手段１３２に対して対訳コーパス１５０を入力するように指示する。
【００４４】
フレーズペア抽出手段１３２は、翻訳元言語の単語と翻訳先言語の単語との単語対応１１１に基づき、対訳コーパス１５０から、翻訳元言語と翻訳先言語において互いに同じ意味を有する単語または句の組合せをフレーズペア１１２として抽出するものである。抽出されたフレーズペア１１２は記憶手段１１に格納される。フレーズペア抽出手段１３２は、式（１）に示した翻訳元言語の単語列と翻訳先言語の単語列との対訳文に対して、ある単語対応ａが計算されたとき、式（７）に示すフレーズペアを抽出する。ここで、単語対応ａは、翻訳先言語の単語位置と翻訳元言語の単語位置の組の集合である。式（７）の「ｉ，ｍ，ｊ，ｎ」は整数を示し、単語対応ａとの間で式（８）の関係を満たすものである。
【００４５】
【数７】
【００４６】
【数８】
【００４７】
例えば、図２に示した対訳文の単語対応からは、以下のようなフレーズペアが抽出されることとなる。
【００４８】
【表２】
【００４９】
ルール作成手段１３３は、対訳コーパス１５０の中の対訳文ペア（対訳文の組合せ）ごとに、その対訳文ペアから抽出されフレーズペア１１２内に格納されたフレーズペアのリストをもとに、同期文脈自由文法のルールを作成し、ルール１１３に格納するものである。
【００５０】
つまり、非特許文献２、非特許文献５、特許文献１などの従来法では、「Ｘ→<γ,α,〜>」という形式の同期文脈自由文法のルールを用いていた。
それに対し、本実施形態では、「Ｘ→<γ,γ´,α,〜>」という形式のルールを用いる。
【００５１】
ここで、γおよびγ´は翻訳元言語の終端記号もしくは非終端記号の列、αは翻訳先言語の終端記号もしくは非終端記号の列を表す。γ、αはそれぞれ翻訳元言語、翻訳先言語の単語列を表現するが、γ´は翻訳元言語の単語列を翻訳先言語の語順に並び替えたものを表す。〜は、記号列γ、γ´、αに含まれる非終端記号の対応を表す。
【００５２】
一例として、非特許文献２、非特許文献５、特許文献１などの従来法で「Ｘ → <X1 を X2 に つなげる, connect X1 to X2 >」と表されるルールが、本実施形態のルール作成装置１ではどうなるかを説明する。ここで、(connect, つなげる), (to, に)という単語対応（単語対応１１１）があり、「を」に対応する英単語がないと仮定する。この場合、英単語に対応しない日本語単語の扱いにより、Ｘ→<γ,γ´,α,〜>の形のルールとして３つの形態が考えられる。
【００５３】
一つ目は、元の語順を保持しつつ先頭に移すという形態である。この場合、ルールは次のようになる。
Ｘ→<X1 を X2 に つなげる, に つなげるX1 を X2, connect X1 to X2 >
【００５４】
二つ目は、対応しない日本語単語を、左側の終端記号もしくは非終端記号に付随させるという形態である。この場合、ルールは、「を」を「X1」に付随させて次のようになる。
Ｘ→<X1 を X2 に つなげる, つなげるX1 を X2 に, connect X1 to X2 >
【００５５】
三つ目は、対応しない日本語単語を右側の終端記号もしくは非終端記号に付随させるという形態である。この場合、「を」を「つなげる」に付随させて次のようになる。
Ｘ→<X1 を X2 に つなげる, に つなげるX1 を X2, connect X1 to X2 >
この例では結果的に一つ目の形態と同一のルールとなっているが、一般的には、異なったルールがつくられる。
【００５６】
通常、機械翻訳は、「翻訳元言語の単語列Ｓを翻訳先言語の単語列Ｔに変換する問題」ととらえられている。それに対し、本実施形態では、新たに導入した同期文脈自由文法ルールにより、「翻訳元言語の単語列Ｓを、『翻訳元言語の文を翻訳先言語の語順に並び替えた単語列Ｓ´』および『翻訳先言語の単語列Ｔ』に同時に変換する問題」ととらえる。
【００５７】
以下では、特許文献１の拡張形態を記す。特許文献１にならい、ルール作成手段１３３に格納されるルールの翻訳先言語側は、終端記号で始まるものとする。また、ルール１１３に格納するルールは、重複を許すものとする。
【００５８】
ルール作成手段１３３は、フレーズペア
に対応して、式（９）〜式（９ｄ）のルールを生成する。このうち、式（９ａ）〜式（９ｄ）のルールは、式（９）のルールから自動的に生成することができる。また、式（９ａ）〜式（９ｄ）のルールに付与されるスコアについても、式（９）のルールと同一値を用いることができる。このような理由から、実装上は、式（９ａ）〜式（９ｄ）のルールは明示的にストレージに格納する必要がない。式（９ａ）〜式（９ｄ）のルールは、非特許文献２で用いられるグルー規則の非終端記号Ｘを、Ｘを左辺とする個々の規則で１回書き換えたものに対応している。
【００５９】
【数９】
【００６０】
ルール作成手段１３３は、式（９）および式（１０）で示すルールが生成され、かつ、式（１１）の関係を満たす場合、式（１２）で示すルールを生成する。
【００６１】
【数１０】
【００６２】
【数１１】
【００６３】
【数１２】
【００６４】
ここで、γ1、γ2およびγ´は翻訳元言語の終端記号もしくは非終端記号の列、αは翻訳先言語の終端記号もしくは非終端記号の列を表す。γ´は、γ1X（ｋ）γ2とα1X(k)α2の単語対応および非終端記号の対応をもとに、γ1X（ｋ）γ2をα1X(k)α2の終端記号・非終端記号の順番に並び替えたものである。
【００６５】
ここで、αには終端記号で始まらなければならないという制約を設ける。なお、本実施形態に必須のものではないが、ルール作成手段１３３は、例えば、以下の制約も採用する。第１に、γとαの両方とも、少なくとも１つの終端記号を含まなければならない。第２に、ルールは、最大２つの非終端記号を有することができる。しかし、翻訳元言語側のγで、非終端記号は隣接してはならない。
【００６６】
翻訳スコア計算手段１３４は、ルール１１３に重複を許して格納されているルールを数え上げ、各ルールｒに対応する翻訳確率Ｐe｜f（ｒ），Ｐf｜e（ｒ）と、レキシカル重みLex e｜f（ｒ），Lex f｜e（ｒ）とを計算し、それらを各ルールｒに対応づけてルールテーブル１１４に格納する。図３に、ルールテーブル１１４の一例を示す。また、表３にルールｒに対応した各翻訳確率、レキシカル重みの計算式を示す。このスコア計算は非特許文献２に倣ったものである。
【００６７】
【表３】
［具体例］
具体的には、ルール作成手段１３３は、図２に示した対訳文から表４に示すような規則（右辺だけ示す）を生成する。この例では、対応しない日本語単語を、左側の終端記号もしくは非終端記号に付随するものとしている。
【００６８】
【表４】
なお、モード判定手段１３１と、フレーズペア抽出手段１３２と、ルール作成手段１３３と、翻訳スコア計算手段１３４とは、ＣＰＵが記憶手段１１のＨＤＤ等に格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【００６９】
なお、単語並び替えモデル学習手段１４および翻訳元言語並べ替えモデル１１５の構成については、図４とともに後述する。
【００７０】
［ルール作成装置の動作］
次に、図１に示したルール作成装置１の動作について、図４を参照（適宜図１等参照）して説明する。図４に示すように、ルール作成装置１は、モード判定手段１３１によって、モードを判定する（ステップＳ１）。判定の結果、モードが「単語対応作成」モードの場合には（ステップＳ１で「単語対応作成」）、ルール作成装置１は、入出力手段１０を介して、対訳コーパス１５０を単語対応作成モジュール１２に入力し（ステップＳ２）、単語対応作成モジュール１２によって、単語対応を作成する（ステップＳ３）。作成された単語対応１１１は、記憶手段１１に格納される。
【００７１】
判定の結果、モードが「並び替えモデル作成」モードの場合には（ステップＳ１で「並び替えモデル作成」）、ルール作成装置１は、入出力手段１０を介して、対訳コーパス１５０を単語並び替えモデル学習手段１４に入力し（ステップＳ４）、対訳コーパス１５０と単語対応１１１を用いて、単語並び替えモデル学習手段１４によって、翻訳元言語並び替えモデルを作成する（ステップＳ５：評価モデル作成ステップ）。作成された翻訳元言語並び替えモデル１１５は、記憶手段１１に格納される。なお、後述する変形例では、さらに翻訳先言語並び替えモデル１１６も同時に記憶手段１１に格納される。
【００７２】
翻訳元言語並び替えモデル１１５としては、例えば、
を用いる。
【００７３】
ここでB[fi, fj]は実数値を返す関数で、単語fiがfjに先行するときに値が高くなり、逆のときに値が小さくなるようなもの（単語の並び順によって返す実数値が異なる関数）である。このような関数として、種々のものが考えられるが、例えば、「R. Tromble and J. Eisner, “Learning Linear Ordering Problems for Better Translation”, In Proc. the 47th ACL, p. 1007-1016, 2009.」に記載の手法（以下、「R. Trombleらの手法」と称する。）を用いて、対訳コーパスから自動的に学習することができる。このB[fi, fj]を用いて、翻訳元言語の文を翻訳先言語の語順に並び替えた単語の並びf1...fNを評価することができる。
【００７４】
このほかにも、翻訳元言語の文を翻訳先言語の語順に並び替えた単語列を評価するモデルとして、n-gramを用いることもできる。R. Trombleらの手法により、対訳コーパスの翻訳元言語の単語を翻訳先言語の語順にあらかじめ自動的に並び替え、その並び替えたものでn-gramを学習する。これは、R. Trombleらの手法で、B[fi, fj]の学習に用いたものと同じである。このように学習したn-gramで単語列Ｓ´の部分単語列fを評価する関数をh7(f)とし、これを式（４）の素性関数の一つとして用いる。
【００７５】
一方、判定の結果、モードが「ルールテーブル作成」モードの場合には（ステップＳ１で「ルールテーブル作成」）、ルール作成装置１は、入出力手段１０を介して、対訳コーパス１５０を制御手段１３に入力し（ステップＳ６）、フレーズペア抽出手段１３２によって、対訳コーパス１５０からフレーズペアを抽出する（ステップＳ７：フレーズペア抽出ステップ）。抽出されたフレーズペア１１２は、記憶手段１１に格納される。
【００７６】
続いて、ルール作成装置１は、ルール作成手段１３３によって、フレーズペア１１２に基づいて、同期文脈自由文法のルールを作成する（ステップＳ８：ルール作成ステップ）。作成されたルール１１３は、記憶手段１１に格納される。そして、ルール作成装置１は、翻訳スコア計算手段１３４によって、ルール１１３の各ルールから計算した各翻訳スコアを各ルールに対応付ける（ステップＳ９）。対応付けられたルールと翻訳スコアとは、ルールテーブル１１４として記憶手段１１に格納される。
【００７７】
なお、ルール作成装置１は、一般的なコンピュータに、前記した各ステップを実行させるルール作成プログラムを実行することで実現することもできる。このプログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００７８】
本実施形態のルール作成装置１により、翻訳元言語の単語列Ｓから、翻訳先言語の単語列Ｔ、および、それと同時に翻訳元言語の文を翻訳先言語の語順に並び替えた単語列Ｓ´の両方の語順を評価するモデル（翻訳元言語並べ替えモデル１１５）を合わせて導入することにより、翻訳先言語の語順をモデル化することができるようになる。
【００７９】
[機械翻訳装置の構成]
次に、機械翻訳装置について説明する。機械翻訳装置２は、ルール作成装置１（図１参照）で作成されたルールテーブル１１４を利用して、入力された翻訳元言語の単語列を、入力に対応する翻訳先言語の単語列に機械的に翻訳するものである。
【００８０】
図５に示すように、機械翻訳装置２は、入出力手段２０と、記憶手段２１と、素性重み学習モジュール２２（重み学習モジュール）と、単語情報抽出モジュール２３と、制御手段２４とを備え、これらは、例えば、ＣＰＵと、ＲＡＭと、ＲＯＭと、ＨＤＤと、入出力インタフェース等から構成される。
【００８１】
入出力手段２０は、入力装置Ｋから翻訳元言語の単語列を制御手段２４に入力したり、制御手段２４から、翻訳結果である翻訳先言語の単語列を出力装置Ｄに出力したりするものである。また、入出力手段２０は、単語対応付き素性重み学習用対訳コーパス２５０を素性重み学習モジュール２２に入力する。
なお、単語対応付き素性重み学習用対訳コーパス２５０は、ルール作成装置１（図１参照）がルールを作成する際に利用する対訳コーパス１５０とは別に用意するものである。
【００８２】
記憶手段２１は、例えば、ＣＰＵによる演算処理等に利用されるＲＡＭや、所定のプログラム、各種データベース、処理結果等を格納するＲＯＭやＨＤＤを備えている。例えば、記憶手段２１には、処理結果として、素性重み２１１と、単語情報２１２と、単語範囲付きルール２１３と、部分仮説２１４と、部分仮説スコア２１６とが格納される。
【００８３】
また、記憶手段１１には、ルール作成装置１（図１参照）で作成されたルールテーブル１１４と、翻訳元言語並べ替えモデル１１５と、別に予め作成された言語モデル２１５とが格納される。言語モデル２１５は、翻訳先言語としての確からしさを表すn‐gramを格納したものである。このn-gramは別途、膨大な量の翻訳先言語のコーパスから学習される。
【００８４】
素性重み学習モジュール２２は、単語対応付き素性重み学習用対訳コーパス２５０と、ルールテーブル１１４と、翻訳元言語並べ替えモデル１１５と、言語モデル２１５とに基づいて、各素性関数の値に対応した重みを学習し、学習結果を素性重み２１１として記憶手段２１に格納するものである。学習法としては、非特許文献１で提案されている方法が利用できる。
【００８５】
単語情報抽出モジュール２３は、入出力手段２０を介して入力装置Ｋから入力する翻訳元言語の文を単語単位に分割して、翻訳元言語の文を構成する単語についての情報（単語情報）を抽出するものである。単語情報は、例えば、単語列、単語位置、単語数等を含む。抽出された単語情報２１２は記憶手段２１に格納される。なお、入力装置Ｋから入力する翻訳元言語の文が単語分割済みの場合には、単語情報抽出モジュール２３を省略することもできる。
【００８６】
制御手段２４は、後記する手順で部分仮説を展開しながら文全体を被う仮説を求め、その中で最適（実際は準最適）なものを求めるものであり、ルール探索手段２４１と、単語範囲付きルール生成手段２４２と、部分仮説スコア算出手段２４３と、仮説探索手段２４４とを備えている。
【００８７】
ルール探索手段２４１は、所定の部分仮説を拡張するために適用可能なルールをルールテーブル１１４からそれぞれ探索するものである。
【００８８】
単語範囲付きルール生成手段２４２は、ルール探索手段２４１で探索されたルールに対して、入力された翻訳元言語の単語列を構成する単語の単語数と単語位置とに基づいて、探索されたルールの非終端記号が被う翻訳元言語の単語列の範囲を示す単語範囲を付加して、適用可能な単語範囲付きルールをそれぞれ生成するものである。
【００８９】
ここでは、入力された翻訳元言語の単語列の変換対象部分（非終端記号が被う範囲）を、その単語位置の左端（left）と右端（right）で、［ｌ，ｒ］のように表記することとする。初期段階では、例えば、入力が１１単語であれば、[ｌ，ｒ]＝[１，１１]となる。この場合、ルールの翻訳元言語側の各非終端記号の単語範囲（未翻訳の単語範囲）を［ｌ1，ｒ1］，［ｌ2，ｒ2］，…のように表記する。例えば、［ｌ1，ｒ1］＝[１，２]等となる。なお、あるルールの翻訳元言語側の非終端記号が２つあれば、単語範囲も２つ設定される。また、あるルールの翻訳元言語側の非終端記号に対して、「ｌ1」の値や「ｒ1」の値として、複数の可能性がある。
【００９０】
部分仮説スコア算出手段２４３は、単語範囲付きルールに含まれる翻訳先言語側の翻訳済み単語と単語範囲とを、新たな部分仮説として作成すると共に、適用可能なルールをトップダウンに適用し、且つ、適用可能なルールにおいて翻訳先言語側の非終端記号が文頭から文末に亘って並べられた順序で、新たな部分仮説を拡張し、ルールごとにそれぞれ予め求められた、翻訳の確からしさを表す翻訳モデルのスコアと、翻訳先言語の単語列としての確からしさを表す言語モデルのスコアと、翻訳元言語の文を翻訳先言語の語順に並び替えた単語列としての確からしさを表す言語モデルのスコアなどに基づいて、作成された部分仮説Ｈ′の評価値を示す部分仮説スコアを算出するものである。
【００９１】
具体的には、部分仮説スコア算出手段２４３は、「（ａ）翻訳先言語の文頭からの単語列」と「（ｂ）翻訳元言語の文を翻訳先言語の語順に並び替えた単語列」と、「翻訳元言語の単語列のうち未翻訳の単語の範囲を保持するスタック」の三つ組みからなる部分仮説Ｈをもとに、適用可能な単語範囲付きルールを使って、新たな部分仮説Ｈ′を作成することを繰り返す。
【００９２】
なお、ＨをもとにＨ′を作成することを部分仮説の拡張と呼ぶ。部分仮説が拡張されるのに従い、部分仮説中の翻訳先言語の文頭からの単語列は文頭から文末にかけて逐次的に追加される。また、部分仮説スコア算出手段２４３は、メモリを節約するため、他の部分仮説との間で単語列の共有を行う。なお、翻訳元言語の単語数がＪの場合、初期部分仮説（部分仮説の初期値）は、「空列」と、「［１，Ｊ］だけが積まれたスタック」とからなる。
【００９３】
部分仮説スコア算出手段２４３は、部分仮説Ｈ′の翻訳元言語の翻訳されている単語数をｍ（０≦ｍ≦Ｊ）とすると、優先度付きキューＱ0，Ｑ1，…，ＱJに部分仮説Ｈ′を入れる。つまり、部分仮説スコア算出手段２４３は、Ｑ0＝｛初期部分仮説｝から始めて、翻訳された翻訳元言語の単語数に同期して優先度付きキューＱmに格納する部分仮説を拡張していく。
【００９４】
部分仮説スコア算出手段２４３は、ある部分仮説を拡張するとき、そのスタックの先頭から（積まれた上方から）翻訳されていない翻訳元言語の単語範囲［ｌ，ｒ］をポップする。翻訳元言語の入力文に対応するルールはEarley法のチャート構造で管理する。チャート構造を用いることにより、部分仮説に対して適用可能なルールを効率良く見つけることが可能となる。例えば、部分仮説スコア算出手段２４３は、前記した式（９ｄ）から生成された式（１３）に示すような単語範囲つきルールから部分仮説を抽出する場合には、単語範囲［ｌ2，ｒ2］，［ｌ1，ｒ1］の順序でスタックにプッシュして、［ｌ1，ｒ1］が先に処理されるようにする。こうして、翻訳先言語側は、常に文頭から翻訳が生成されることが保証されることになる。
【００９５】
【数１３】
【００９６】
部分仮説スコア算出手段２４３は、もととなった部分仮説ＨのスコアＳ（Ｈ）に差分スコアを加算することで、式（１４）に示すような、拡張された部分仮説Ｈ′のスコアＳ（Ｈ′）を算出する。
【００９７】
【数１４】
ここで、ｍ（１≦ｍ≦Ｍ）は素性関数の値の識別番号を示す。本実施形態では、部分仮説スコア算出手段２４３は、Ｍ＝７として、表５に示す７つの素性関数の値ｈm（Ｈ′）と、そのｈm（Ｈ′）に対して対応する素性重みλm（Ｈ′）とを用いる。また、仮説を生成する際に、部分仮説の展開により新たに生成された翻訳先言語の単語列を、
と表記する。ここで、生成された翻訳先言語の単語列は、「ｉ」番目の単語から「ｉ＋ε」番目の単語で構成されている。また、ｈ７（Ｈ´）におけるＰＬＭ´は、対訳コーパスの翻訳元言語の文を翻訳先言語の語順に並び替えたものから学習するn-gram言語モデルである。
【００９８】
ここで、表５において、初期の仮説H0に対するhi(H0)は0であるものとする。
【表５】
【００９９】
表５で、ｈ７(・)は単語の並び替えモデル（翻訳元言語並べ替えモデル１１５）となっている。単語の並び替えモデルは、別な方法で表現することも可能である。以下、具体的に説明する。翻訳元言語の単語列Ｓを翻訳先言語の語順に並び替えた単語列をＳ´とする。また、fi,fjを単語列ＳおよびＳ´の単語であるとする。この仮定のもと、B[fi,fj]は、単語列Ｓ´において単語fiがfjに先行するときに大きな実数を、逆のときに小さな実数を返す関数とする。これを利用して翻訳元言語の単語並び替えをモデル化することができる。このような関数として、種々のものが考えられるが、例えば、R. Trombleらの手法を用いて、対訳コーパスから自動的に作成することができる。
【０１００】
このB[fi, fj]を用いることにより、表５に示すｈ７(・)と同様の働きをするｈ８(・)を次の式（１５）のように定義することができる。
【数１５】
ここで、ｆｋ（i+ε<k）は仮説のＳ´にまだ生成されていないＳの単語のことである。なお、ｈ８（Ｈ´）は、ｈ７（Ｈ´）の代わりに利用しても良いし、ｈ７（Ｈ´）と併用することもできる。
【０１０１】
また、表５において、ここで、Ｐe｜f（ｒ）、Ｐf｜e（ｒ）、Lexe｜f（ｒ）、Lexf｜e（ｒ）は、記憶手段２１のルールテーブル１１４に規定されているルールｒに対応した素性関数の値である。また、素性重みλmは、記憶手段２１に格納された素性重み２１１に予め規定されているものとする。
【０１０２】
つまり、本実施形態では、式（１４）と表５とから、部分仮説スコア算出手段２４３は、最終的に、部分仮説Ｈ′のスコアＳ（Ｈ′）を、次に示す式（１６）で算出する。式（１６）はh7(・)を用いた場合の例である。この式（１６）の２番目の等号の右辺は、もととなった部分仮説ＨのスコアＳ（Ｈ）に、差分スコアを加算することを示している。また、部分仮説スコア算出手段２４３は、優先度付きキューＱ0，Ｑ1，…，ＱJには、最大Ｙ個（例えば、1000個）の部分仮説しか保持しない。また、部分仮説スコア算出手段２４３は、部分仮説スコアＳ（Ｈ′）が優先度付きキューＱ0，Ｑ1，…，ＱJ内の最大の部分仮説スコアとある定数との積よりも小さい場合、その部分仮説Ｈ′を捨てる。これにより、部分仮説スコア算出手段２４３は、優先度付きキューＱ0，Ｑ1，…，ＱJに格納される各部分仮説に対して効果的な枝刈りを行うことができる。
【０１０３】
【数１６】
仮説探索手段２４４は、入力された翻訳元言語の単語列に対して適用可能な所定の部分仮説を探索し、所定の部分仮説を拡張することによって最終的に生成された翻訳元言語の文全体に対応する部分仮説（これを仮説と呼ぶ）のうちで、部分仮説スコアが最大となる仮説を探索するものである。具体的には、仮説探索手段２４４は、翻訳元言語の文全体から得られる所定数の仮説のうちで、仮説スコアが最大となる仮説Ｈ＾を、次の式（１７）の関係から探索する。式（１７）に示す仮説Ｈは、優先度付きキューＱJに含まれる部分仮説Ｈのことなので、式（１７）で求める仮説Ｈ＾は、部分仮説スコアＳ（Ｈ）の値を最大とする部分仮説Ｈ（つまり仮説Ｈ）として求めることができる。
【０１０４】
【数１７】
【０１０５】
また、仮説探索手段２４４は、求めた仮説に対応する翻訳先言語の文頭から文末までの単語列を翻訳結果として、入出力手段２０を介して出力装置Ｄに出力する。
【０１０６】
なお、ルール探索手段２４１、単語範囲付きルール生成手段２４２、部分仮説スコア算出手段２４３および仮説探索手段２４４は、ＣＰＵが記憶手段２１のＨＤＤ等に格納された所定のプログラムをＲＡＭに展開して実行することにより実現されるものである。
【０１０７】
［機械翻訳装置の動作］
図５に示した機械翻訳装置２の動作について、図６を参照（適宜図５参照）して説明する。図６に示すように、予め、機械翻訳装置２は、素性重み学習モジュール２２によって、単語対応付き素性重み学習用対訳コーパス２５０と、言語モデル２１５と、ルールテーブル１１４と、翻訳元言語並べ替えモデル１１５とに基づいて、素性関数の値の重みを学習し、学習結果である素性重み２１１を記憶手段２１に格納しておく。
【０１０８】
そして、機械翻訳装置２は、入力装置Ｋから入出力手段２０を介して入力された翻訳元言語の文を単語情報抽出モジュール２３に入力する（ステップＳ１１）。機械翻訳装置２は、単語情報抽出モジュール２３によって、入力された翻訳元言語の文（入力文）を単語に分割し、単語列、単語数Ｊやそれぞれの単語の単語位置を抽出する（ステップＳ１２）。抽出された単語列、単語数Ｊや単語位置は、単語情報２１２として記憶手段２１に格納される。
【０１０９】
機械翻訳装置２は、仮説探索手段２４４によって、初期部分仮説Ｈ0を作成し、入力単語数Ｊに合わせて、Ｊ＋１個の優先度付きキューＱ0，…，ＱJを空にして、そのうちの優先度付きキューＱ0に初期部分仮説Ｈ0を格納する（ステップＳ１３）。そして、機械翻訳装置２は、仮説探索手段２４４によって、初期部分仮説Ｈ0に対する部分仮説スコアＳ（Ｈ0）と、優先度付きキューの識別変数ｍとを初期化する。すなわち、Ｓ（Ｈ0）＝０，ｍ＝０とする（ステップＳ１４）。
【０１１０】
続いて、機械翻訳装置２は、ルール探索手段２４１によって、ｍ番目の優先度付きキューＱmから、そこに格納されている適用可能なそれぞれの部分仮説Ｈを順次ポップし、それぞれの部分仮説Ｈを拡張できるような適用可能なそれぞれのルールｒをルールテーブル１１４から探索する。そして、探索結果であるそれぞれのルールｒの翻訳元言語側に記述されている翻訳済単語の個数（翻訳済単語個数）Ｖ（ｒ）を取得し、現在の優先度付きキューの識別変数ｍの値に加算することによって、処理対象の部分仮説Ｈに対する翻訳済単語数ｎの値を更新する。すなわち、ｎ＝ｍ＋Ｖ（ｒ）とする（ステップＳ１５：ルール探索ステップ）。
【０１１１】
そして、機械翻訳装置２は、単語範囲付きルール生成手段２４２によって、探索したルールに対して適用可能なそれぞれの単語範囲付きルールｒ′を生成する（ステップＳ１６：単語範囲付きルール生成ステップ）。そして、機械翻訳装置２は、部分仮説スコア算出手段２４３によって、処理対象の部分仮説Ｈを、それぞれの単語範囲付きルールｒ′で展開して部分仮説Ｈ′をそれぞれ作成し、作成した部分仮説Ｈ′について前記した式（１６）に基づいて、式（１４）に示す部分仮説スコアＳ（Ｈ′）を算出する。式（１４）の右辺にｈｍがあり、表５にｈ７（Ｈ′）があることから、この部分仮説スコアには、翻訳元言語の単語列Ｓを翻訳先言語の語順を並び替えた単語列Ｓ´の部分単語列が影響していることがわかる。
【０１１２】
そして、作成した部分仮説Ｈ′を、ｎ番目の優先度付きキューＱnに格納し、所定の枝刈りを行う（ステップＳ１７：部分仮説スコア算出ステップ）。ここで、枝刈りによって不要となった部分仮説Ｈ′は、優先度付きキューＱnから削除される。また、算出された部分仮説スコアＳ（Ｈ′）は記憶手段２１の部分仮説スコア２１６に格納されるが、枝刈りによって削除された部分仮説Ｈ′に対する部分仮説スコアＳ（Ｈ′）は削除されることとなる。
【０１１３】
そして、機械翻訳装置２は、仮説探索手段２４４によって、適用可能な単語範囲付きルールｒ′をすべて選択したか否かを判別する（ステップＳ１８）。適用可能なｒ′がまだ存在する場合（ステップＳ１８：Ｎｏ）、機械翻訳装置２は、ステップＳ１６に戻る。
一方、ｒ′をすべて選択した場合（ステップＳ１８：Ｙｅｓ）、仮説探索手段２４４は、適用可能なルールｒをすべて選択したか否かを判別する（ステップＳ１９）。適用可能なｒがまだ存在する場合（ステップＳ１９：Ｎｏ）、機械翻訳装置２は、ステップＳ１５に戻る。
【０１１４】
一方、ｒをすべて選択した場合（ステップＳ１９：Ｙｅｓ）、仮説探索手段２４４は、適用可能な部分仮説Ｈをすべて選択したか否かを判別する（ステップＳ２０）。適用可能なＨがまだ存在する場合（ステップＳ２０：Ｎｏ）、機械翻訳装置２は、ステップＳ１５に戻る。一方、Ｈをすべて選択した場合（ステップＳ２０：Ｙｅｓ）、仮説探索手段２４４は、現在の優先度付きキューの識別変数ｍの値が入力単語数Ｊと等しい（ｍ＝Ｊ）か否かを判別する（ステップＳ２１）。ｍ≠Ｊである場合（ステップＳ２１：Ｎｏ）、機械翻訳装置２は、仮説探索手段２４４によって、優先度付きキューの識別変数ｍをインクリメントする。すなわち、ｍ＝ｍ＋１とする（ステップＳ２２）。続いて、ステップＳ１５に戻る。
【０１１５】
一方、ｍ＝Ｊである場合（ステップＳ２１：Ｙｅｓ）、Ｊ番目の優先度付きキューＱJには、翻訳元言語の文全体を被う部分仮説Ｈが複数格納されている。これら部分仮説Ｈは、翻訳元言語の文に対する仮説Ｈとみなすことができる。同様に、優先度付きキューＱJに格納された部分仮説Ｈに対する部分仮説スコアＳ（Ｈ）は、この意味で、仮説スコアＳ（Ｈ）と呼ぶ。そして、この場合、機械翻訳装置２は、仮説探索手段２４４によって、Ｊ番目の優先度付きキューＱJから仮説スコアＳ（Ｈ）の値が最大となる仮説Ｈを探索する（ステップＳ２３：仮説探索ステップ）。そして、機械翻訳装置２は、仮説探索手段２４４によって、探索された仮説を翻訳先言語の文として出力する（ステップＳ２４）。これにより、探索された仮説に対応する翻訳先言語の文頭から文末までの単語列が出力装置Ｄに出力される。
【０１１６】
なお、機械翻訳装置２は、一般的なコンピュータに、前記した各ステップを実行させる機械翻訳プログラムを実行することで実現することもできる。このプログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【０１１７】
［具体例］
図７と、表６と、表７と、表８とを参照して具体例について説明する。
図７は、図５に示した部分仮説から仮説への拡張例を示す図である。表６は、１１単語からなる翻訳元言語文を示し、表７は、表６に示した翻訳元言語文に対応して適用可能なルールを示す。なお、表７中の「ルールの種類」とは、前記した式（９）〜式（９ｄ）のいずれに対応するかを示すものである。表８は、表７に示したルールの適用順とそれに基づく単語範囲付きルールを示すものである。
【０１１８】
【表６】
【０１１９】
【表７】
【０１２０】
【表８】
初期状態において、部分仮説スコア算出手段２４３は、スタックを空にし、図７に示すように、状態「０」で翻訳元言語の単語列（文）全体を被う単語範囲［１，１１］をプッシュする。状態「０」では、部分仮説Ｈ′（０）は、初期部分仮説なので、スタックにプッシュした単語範囲［１，１１］と空列との組である。部分仮説Ｈ′（０）の部分仮説スコアＳ（Ｈ′）は「０」とする。
【０１２１】
次に、状態「１」で、部分仮説スコア算出手段２４３は、スタックから範囲［１，１１］をポップし、ルール探索手段２４１は、表７から、ポップされた範囲に適用可能なルールｒ（３）を選択する。ルールｒ（３）における翻訳解「The」に対応した「は」の入力文における単語位置は、「３」なので、単語範囲付きルール生成手段２４２は、表８に示すように、ルールｒ（３）における非終端記号Ｘ(1)および非終端記号Ｘ(2)の単語範囲が、それぞれ［１，２］、［４，１１］となるような単語範囲付きルールｒ′（３）を生成する。
【０１２２】
この単語範囲付きルールｒ′（３）では、翻訳先言語側において非終端記号Ｘ(1)が非終端記号Ｘ(2)より先に処理されなければならない。そのため、部分仮説スコア算出手段２４３は、図７に示すように、単語範囲付きルールｒ′（３）において、非終端記号Ｘ(2)に対応する単語範囲［４，１１］をスタックにプッシュしてから、非終端記号Ｘ(1)に対応する単語範囲［１，２］をプッシュする。部分仮説スコア算出手段２４３は、スタックにプッシュした単語範囲［１，２］、［４，１１］と、翻訳先言語の文頭からの単語列としての翻訳解「The」とを部分仮説Ｈ′（１）とする。部分仮説スコア算出手段２４３は、部分仮説Ｈ′（１）について部分仮説スコアを算出する。
【０１２３】
次に、状態「２」で、部分仮説スコア算出手段２４３は、スタックから単語範囲［１，２］をポップし、ルール探索手段２４１は、表７から、この単語範囲に適用可能なルールｒ（１）を選択する。ルールｒ（１）における翻訳解「international」に対応した「国際」の入力文における単語位置は、「１」なので、単語範囲付きルール生成手段２４２は、表８に示すように、ルールｒ（１）における非終端記号Ｘ(1)の単語範囲が［２，２］となるような単語範囲付きルールｒ′（１）を生成する。部分仮説スコア算出手段２４３は、図７に示すように、単語範囲付きルールｒ′（１）において、単語範囲［２，２］をスタックにプッシュする。部分仮説スコア算出手段２４３は、スタックにプッシュした単語範囲［２，２］と、以前プッシュした単語範囲［４，１１］と、翻訳先言語の文頭からの単語列としての翻訳解「The international」とを部分仮説Ｈ′（２）とする。部分仮説スコア算出手段２４３は、部分仮説Ｈ′（２）について部分仮説スコアを算出する。
【０１２４】
次に、状態「３」で、部分仮説スコア算出手段２４３は、スタックから単語範囲［２，２］をポップし、ルール探索手段２４１は、表７から、この単語範囲に適用可能なルールｒ（２）を選択する。ルールｒ（２）には「テロ」に対応した翻訳解「terrorism」が記述されているが、非終端記号が無いので、単語範囲付きルール生成手段２４２は、ルールｒ（２）をそのまま単語範囲付きルールｒ′（２）とする。部分仮説スコア算出手段２４３は、単語範囲付きルールｒ′（２）において単語範囲が指定されていないのでスタックに対する操作を行わない。部分仮説スコア算出手段２４３は、図７に示すように、スタックに以前プッシュした単語範囲［４，１１］と、翻訳先言語の文頭からの単語列としての翻訳解「The international terrorism」とを部分仮説Ｈ′（３）とする。部分仮説スコア算出手段２４３は、部分仮説Ｈ′（３）について部分仮説スコアを算出する。
【０１２５】
以下、同様にして、表８に記載した適用順に、状態「４」から状態「９」に対応する操作を行うと、スタックが空になるので、部分仮説スコア算出手段２４３は、部分仮説の展開を終了し、仮説を生成する。このとき、翻訳先言語の文頭からの単語列としての翻訳解は、以下のように、１０単語の単語列となる。
「The international terrorism also is a possible threat in Japan」
【０１２６】
ここで、ルールｒ（９）は、２つの終端記号（単語）「で ある，is a」を有しているため、部分仮説スコア算出手段２４３は、９回の状態遷移で１０単語を訳出する。図７では、部分仮説展開の過程で、翻訳先言語側が文頭から文末にかけて生成されたことが示されている。
【０１２７】
本実施形態の機械翻訳装置２によれば、入力された翻訳元言語の単語列において未翻訳の部分に対して部分仮説を順次拡張する際に、翻訳元言語の単語列を翻訳先言語の語順に並び替えたものを同時に生成する。そのため、翻訳元言語の単語列の翻訳先言語の語順への並び替えの尤もらしさを、部分仮説の評価に活用することができて、副作用の少ない仮説の枝狩りが可能となる。その結果、翻訳速度を向上させることや、翻訳先言語の単語列の翻訳精度を向上させることが可能となる。換言すれば、翻訳元言語並べ替えモデル１１５を考慮してスコアを算出することで、高い翻訳精度を実現することができる。
【０１２８】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。以下、変形例について説明する。
【０１２９】
〔変形例〕
次に、ルール作成装置１と機械翻訳装置２の変形例について説明する。例えば、ルール作成装置１の単語並び替えモデル学習手段１４において、翻訳元言語並び替えモデル１１５の代わりに翻訳先言語の語順を並び替えた翻訳先言語並び替えモデル１１６を作成し、式（１０）〜式（１２）のｒ´の代わりにα´（翻訳先言語の単語列を翻訳元言語の語順に並び替えた単語列）に置き換えたルールを利用することができる。
【０１３０】
この場合、機械翻訳装置２では、翻訳先言語の単語列を翻訳元言語の語順に並び替えた単語列の部分単語列e´に対して表５のｈ７(・)や式（１５）のｈ８（・）に相当する素性関数を定義し（ｈ７´(・)，ｈ８´（・）とおく）、これを素性関数として活用することができる。
【０１３１】
ただし、部分仮説H´に対するｈ８´（H´）の計算は、e´が文頭から文末にかけて単調に生成されないため、やや異なった処理が必要となる。e´の生成例を図８に示す。図８に示すように、スタックからポップされた単語範囲が一部、単語列に置き換わり、新たな単語範囲がスタックにプッシュされるということを繰り返す。状態５の仮説Hが状態６の仮説H´に展開されたときのｈ８´（H´）の計算には、次の式（１８）を用いる。
【０１３２】
【数１８】
【０１３３】
さらに、状態４の仮説Hが状態５の仮説H´に展開されたときのｈ８´（H´）の計算には、次の式（１９）を用いる。
【０１３４】
【数１９】
これらの例のように、仮説展開に伴うｈ８´（H´）の差分は、仮説展開に伴って具体化した単語列内と、その単語列とすでに具体化している単語列の間でB[・,・]を計算することで求めることができる。
【０１３５】
ｈ７´（H´）の計算は、e´が左から右に単調に生成されるわけでないため、自明ではないが、非特許文献５にある言語モデル・スコアの計算方法により実現できる。
さらなる変形例として、（ｂ）翻訳元言語の文を翻訳先言語の語順に並び替えた単語並びモデル（翻訳元言語並べ替えモデル１１５）と、（ｃ）翻訳先言語の文を翻訳元言語の語順に並び替えた単語並びモデル（翻訳先言語並べ替えモデル１１６）の両方を活用することも可能である。この場合、Ｘ→<γ,γ´,α´,α,〜>の形式のルールを用い、ｈ７´（H´）とｈ８´（H´）の両方を素性関数として用いる。
【０１３６】
〔その他の変形例：非特許文献２の拡張形態〕
以上で説明したルール作成装置および機械翻訳装置の代わりに、非特許文献２のアルゴリズムを採用したルール作成装置および機械翻訳装置も可能である。この場合、ルールはボトムアップに適用される。
【０１３７】
翻訳元言語の文を翻訳先言語の語順に並び替えたものと、翻訳先言語の文を翻訳元言語の語順に並び替えたものの両方を利用するために、ルールは次の形式のものを用いる。
Ｘ→＜γ,γ´,α´,α,〜＞
γは翻訳元言語の終端記号もしくは非終端記号の列を、αは翻訳先言語の終端記号もしくは非終端記号の列を、γ´は翻訳元言語の終端記号もしくは非終端記号の列を翻訳先言語の語順に並び替えたものを、α´は翻訳先言語の終端記号もしくは非終端記号の列を翻訳元言語の語順に並び替えたものを表す。
【０１３８】
このボトムアップアルゴリズムでは、仮説Ｈは、
X:[i,j]→<f´,e´,e>
のように表される。Xは非終端記号、[i, j]はそれが覆う翻訳元言語の文の単語範囲、f´は翻訳元言語の単語列を翻訳先言語の語順に並び替えた単語列、e´は翻訳先言語の単語列を翻訳元言語の語順に並び替えた単語列、eは翻訳先言語の単語列を表す。
【０１３９】
ボトムアップな仮説の展開の様子を例で示す。仮説Hはルール
X→< X1 で ある, で ある X1, X1 is a, is a X1>
によって展開され、より広い範囲をカバーする仮説H´を生成する。例えば、次の通りである。
H: X:[7,9]→<起こり うる 脅威, possible threat, possible threat>
H´: X:[7,11]→<で ある 起こり うる 脅威, possible threat is a, is a possible threat>
f´およびe´を利用して、ｈ７, ｈ８やｈ´７, ｈ´８を展開前の仮説の値からの差分を計算することで、展開後の仮説の値を計算することができる。
【０１４０】
〔eとe´を用いた素性重み学習の形態〕
非特許文献１は、素性重み学習用対訳コーパス（単語対応付き素性重み学習用対訳コーパス２５０に対応）中の翻訳元の文と正解翻訳文のペアを利用し、素性重みを学習する「素性重み学習モジュール（素性重み学習モジュール２２に対応）」の実現法について記述している。この手法では、目的関数を最適化するように重みが学習される。通常、目的関数としては、翻訳した文章（複数の文の列）eと正解文章reとの近さを表す関数が使われ、具体的には前記したＢＬＥＵ(e, re)などが広く利用されている。
【０１４１】
本実施形態の機械翻訳装置２では、翻訳文章eと同時に、翻訳元言語の文を翻訳先言語の語順に並び替えた文からなる文章f´と、翻訳先言語の文を翻訳元言語の語順に並び替えた文からなる文章e´が同時に得られる。f´の正解をrf´、e´の正解をre´とすると、l1BLEU(f´, rf´) + l2BLEU(e´, re´) + l3BLEU(e, re) （l1+l2+l3 = 1）を目的関数として、素性hi(・)の素性重みλiを学習する。
【０１４２】
パラメータli（i=1,2,3)の求め方は様々な方法が考えられるが、あらかじめ開発用対訳データで翻訳実験を行い、そこでの翻訳精度（ＢＬＥＵ（「K. Papineni, S. Roukos, T. Ward and W-J. Zhu, “BLEU: a Method for Automatic Evaluation of Machine Translation”, In Proc. of the 40thACL, 2002」参照）で測定）が高くなるように設定する。
【０１４３】
f´の正解であるrf´は、文fとreの対応する文reとの単語対応を求め、それをもとに、文fを文reの言語の語順に並び替えることで求めることができる。もし、文fの単語で文reに対応するものがなければ、語順を保持しつつ文頭に移す、右側の語に付随させる、左側の語に付随させるなどの形態がある。e´の正解であるre´についても、同様に求めることができる。
【０１４４】
なお、本実施形態では、日英の翻訳を例に説明したが、これに限定されるものではない。ルール作成装置によりルールを作成すれば、任意の多言語間でこの翻訳装置を使用することが可能である。
【実施例】
【０１４５】
非特許文献２の技術を実装したシステム(baseline)に、式（１５）のｈ８(・)を素性として加えた。ルール中の対応のとれない単語について、元の語順を保持しつつ先頭に移した形態のシステムを”Baseline+move-to-front”、左側の終端記号もしくは非終端記号に付随させる形態のシステムを”Baseline+attach”とする。
【０１４６】
約20万文の対訳コーパス１５０からルールテーブル１１４を学習し、約1000文の単語対応付き素性重み学習用対訳コーパス２５０を用いて、機械翻訳装置２の素性重み学習モジュール２２が素性重みを学習した。機械翻訳装置２によって約1000文のテスト用対訳コーパスの翻訳元言語の文を翻訳した結果を、そのテスト用対訳コーパスの翻訳先言語の文を正解としてＢＬＥＵで評価した結果を表９に示す。
【０１４７】
ＢＬＥＵの値が大きいほど、良い翻訳であることを示す。表９に示したように
【表９】
、素性ｈ８(・)の追加は翻訳精度の向上に有効であった。
【符号の説明】
【０１４８】
１ ルール作成装置
２ 機械翻訳装置
１０ 入出力手段
１１ 記憶手段
１１１ 単語対応
１１２ フレーズペア
１１３ ルール
１１４ ルールテーブル
１２ 単語対応作成モジュール
１３ 制御手段
１３１ モード判定手段
１３２ フレーズペア抽出手段
１３３ ルール作成手段
１３４ 翻訳スコア計算手段
１５０ 対訳コーパス
２０ 入出力手段
２１ 記憶手段
２１１ 素性重み
２１２ 単語情報
２１３ 単語範囲付きルール
２１４ 部分仮説
２１５ 言語モデル
２１６ 部分仮説スコア
２２ 素性重み学習モジュール
２３ 単語情報抽出モジュール
２４ 制御手段
２４１ ルール探索手段
２４２ 単語範囲付きルール生成手段
２４３ 部分仮説スコア算出手段
２４４ 仮説探索手段
２５０ 素性重み学習用対訳コーパス
Ｋ 入力装置
Ｄ 出力装置
【特許請求の範囲】
【請求項１】
同期文脈自由文法を用いて翻訳元言語の単語列から翻訳先言語の単語列を生成するルールが複数格納されたルールテーブルを利用して、入力された翻訳元言語の単語列の翻訳結果である前記入力に対応する翻訳先言語の単語列として、所定の部分仮説からそれよりも長い新たな部分仮説を順次作成して前記所定の部分仮説を拡張することによって最終的に生成された部分仮説である仮説を出力する機械翻訳装置であって、
前記部分仮説は、（ａ）翻訳候補となる翻訳先言語の単語列と、少なくとも、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列、および、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列、のいずれかと、を考慮して作成されるものであり、
前記所定の部分仮説を拡張するために適用可能なルールを前記ルールテーブルからそれぞれ探索するルール探索手段と、
前記探索されたルールの翻訳元言語側に対して、前記入力された翻訳元言語の単語列を構成する単語の単語数と単語位置とに基づいて、前記探索されたルールの非終端記号が被う翻訳元言語の単語列の範囲を示す単語範囲を付加して、適用可能な単語範囲付きルールをそれぞれ生成する単語範囲付きルール生成手段と、
前記適用可能なルールを適用し前記新たな部分仮説を拡張し、前記ルールごとにそれぞれ予め求められた、翻訳の確からしさを表す翻訳モデルのスコアと、前記（ａ）の単語列としての確からしさを表す言語モデルのスコアと、少なくとも、前記(ｂ)の単語列としての確からしさを表す言語モデルのスコア、および、前記(ｃ)の単語列としての確からしさを表す言語モデルのスコア、のいずれかと、に基づいて、前記作成された部分仮説の評価値を示す部分仮説スコアを算出する部分仮説スコア算出手段と、
前記入力された翻訳元言語の単語列に対して適用可能な所定の部分仮説を探索し、前記所定の部分仮説を拡張することによって最終的に生成された部分仮説のうちで、前記部分仮説スコアが最大となる部分仮説を、前記仮説として探索する仮説探索手段と、
を備えることを特徴とする機械翻訳装置。
【請求項２】
前記（ａ）の単語列、前記(ｂ)の単語列、および、前記(ｃ)の単語列のそれぞれについて、所定の評価モデルを用いて、当該単語列とその正解との近さを考慮して、素性の重みを予め生成する重み学習モジュールを、さらに備える
ことを特徴とする請求項１に記載の機械翻訳装置。
【請求項３】
前記部分仮説スコア算出手段は、前記重みを用いて前記部分仮説スコアを算出する
ことを特徴とする請求項２に記載の機械翻訳装置。
【請求項４】
同期文脈自由文法を用いて翻訳元言語の単語列から翻訳先言語の単語列を生成するルールが複数格納されたルールテーブルを利用して、入力された翻訳元言語の単語列の翻訳結果である前記入力に対応する翻訳先言語の単語列として、所定の部分仮説からそれよりも長い新たな部分仮説を順次作成して前記所定の部分仮説を拡張することによって最終的に生成された部分仮説である仮説を出力する機械翻訳装置による機械翻訳方法であって、
前記部分仮説は、（ａ）翻訳候補となる翻訳先言語の単語列と、少なくとも、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列、および、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列、のいずれかと、を考慮して作成されるものであり、
前記機械翻訳装置は、
前記所定の部分仮説を拡張するために適用可能なルールを前記ルールテーブルからそれぞれ探索するルール探索ステップと、
前記探索されたルールの翻訳元言語側に対して、前記入力された翻訳元言語の単語列を構成する単語の単語数と単語位置とに基づいて、前記探索されたルールの非終端記号が被う翻訳元言語の単語列の範囲を示す単語範囲を付加して、適用可能な単語範囲付きルールをそれぞれ生成する単語範囲付きルール生成ステップと、
前記適用可能なルールを適用し前記新たな部分仮説を拡張し、前記ルールごとにそれぞれ予め求められた、翻訳の確からしさを表す翻訳モデルのスコアと、前記（ａ）の単語列としての確からしさを表す言語モデルのスコアと、少なくとも、前記(ｂ)の単語列としての確からしさを表す言語モデルのスコア、および、前記(ｃ)の単語列としての確からしさを表す言語モデルのスコア、のいずれかと、に基づいて、前記作成された部分仮説の評価値を示す部分仮説スコアを算出する部分仮説スコア算出ステップと、
前記入力された翻訳元言語の単語列に対して適用可能な所定の部分仮説を探索し、前記所定の部分仮説を拡張することによって最終的に生成された部分仮説のうちで、前記部分仮説スコアが最大となる部分仮説を、前記仮説として探索する仮説探索ステップと、
を有することを特徴とする機械翻訳方法。
【請求項５】
前記機械翻訳装置は、重み学習モジュールをさらに備えており、
前記重み学習モジュールは、
前記（ａ）の単語列、前記(ｂ)の単語列、および、前記(ｃ)の単語列のそれぞれについて、所定の評価モデルを用いて、当該単語列とその正解との近さを考慮して、素性の重みを予め生成する
ことを特徴とする請求項４に記載の機械翻訳方法。
【請求項６】
前記部分仮説スコア算出手段は、前記重みを用いて前記部分仮説スコアを算出する
ことを特徴とする請求項５に記載の機械翻訳方法。
【請求項７】
コンピュータを請求項１から請求項３までのいずれか一項に記載の機械翻訳装置として機能させるためのプログラム。
【請求項１】
同期文脈自由文法を用いて翻訳元言語の単語列から翻訳先言語の単語列を生成するルールが複数格納されたルールテーブルを利用して、入力された翻訳元言語の単語列の翻訳結果である前記入力に対応する翻訳先言語の単語列として、所定の部分仮説からそれよりも長い新たな部分仮説を順次作成して前記所定の部分仮説を拡張することによって最終的に生成された部分仮説である仮説を出力する機械翻訳装置であって、
前記部分仮説は、（ａ）翻訳候補となる翻訳先言語の単語列と、少なくとも、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列、および、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列、のいずれかと、を考慮して作成されるものであり、
前記所定の部分仮説を拡張するために適用可能なルールを前記ルールテーブルからそれぞれ探索するルール探索手段と、
前記探索されたルールの翻訳元言語側に対して、前記入力された翻訳元言語の単語列を構成する単語の単語数と単語位置とに基づいて、前記探索されたルールの非終端記号が被う翻訳元言語の単語列の範囲を示す単語範囲を付加して、適用可能な単語範囲付きルールをそれぞれ生成する単語範囲付きルール生成手段と、
前記適用可能なルールを適用し前記新たな部分仮説を拡張し、前記ルールごとにそれぞれ予め求められた、翻訳の確からしさを表す翻訳モデルのスコアと、前記（ａ）の単語列としての確からしさを表す言語モデルのスコアと、少なくとも、前記(ｂ)の単語列としての確からしさを表す言語モデルのスコア、および、前記(ｃ)の単語列としての確からしさを表す言語モデルのスコア、のいずれかと、に基づいて、前記作成された部分仮説の評価値を示す部分仮説スコアを算出する部分仮説スコア算出手段と、
前記入力された翻訳元言語の単語列に対して適用可能な所定の部分仮説を探索し、前記所定の部分仮説を拡張することによって最終的に生成された部分仮説のうちで、前記部分仮説スコアが最大となる部分仮説を、前記仮説として探索する仮説探索手段と、
を備えることを特徴とする機械翻訳装置。
【請求項２】
前記（ａ）の単語列、前記(ｂ)の単語列、および、前記(ｃ)の単語列のそれぞれについて、所定の評価モデルを用いて、当該単語列とその正解との近さを考慮して、素性の重みを予め生成する重み学習モジュールを、さらに備える
ことを特徴とする請求項１に記載の機械翻訳装置。
【請求項３】
前記部分仮説スコア算出手段は、前記重みを用いて前記部分仮説スコアを算出する
ことを特徴とする請求項２に記載の機械翻訳装置。
【請求項４】
同期文脈自由文法を用いて翻訳元言語の単語列から翻訳先言語の単語列を生成するルールが複数格納されたルールテーブルを利用して、入力された翻訳元言語の単語列の翻訳結果である前記入力に対応する翻訳先言語の単語列として、所定の部分仮説からそれよりも長い新たな部分仮説を順次作成して前記所定の部分仮説を拡張することによって最終的に生成された部分仮説である仮説を出力する機械翻訳装置による機械翻訳方法であって、
前記部分仮説は、（ａ）翻訳候補となる翻訳先言語の単語列と、少なくとも、(ｂ)翻訳元言語の文を翻訳先言語の語順に並び替えた単語列、および、(ｃ)翻訳先言語の文を翻訳元言語の語順に並び替えた単語列、のいずれかと、を考慮して作成されるものであり、
前記機械翻訳装置は、
前記所定の部分仮説を拡張するために適用可能なルールを前記ルールテーブルからそれぞれ探索するルール探索ステップと、
前記探索されたルールの翻訳元言語側に対して、前記入力された翻訳元言語の単語列を構成する単語の単語数と単語位置とに基づいて、前記探索されたルールの非終端記号が被う翻訳元言語の単語列の範囲を示す単語範囲を付加して、適用可能な単語範囲付きルールをそれぞれ生成する単語範囲付きルール生成ステップと、
前記適用可能なルールを適用し前記新たな部分仮説を拡張し、前記ルールごとにそれぞれ予め求められた、翻訳の確からしさを表す翻訳モデルのスコアと、前記（ａ）の単語列としての確からしさを表す言語モデルのスコアと、少なくとも、前記(ｂ)の単語列としての確からしさを表す言語モデルのスコア、および、前記(ｃ)の単語列としての確からしさを表す言語モデルのスコア、のいずれかと、に基づいて、前記作成された部分仮説の評価値を示す部分仮説スコアを算出する部分仮説スコア算出ステップと、
前記入力された翻訳元言語の単語列に対して適用可能な所定の部分仮説を探索し、前記所定の部分仮説を拡張することによって最終的に生成された部分仮説のうちで、前記部分仮説スコアが最大となる部分仮説を、前記仮説として探索する仮説探索ステップと、
を有することを特徴とする機械翻訳方法。
【請求項５】
前記機械翻訳装置は、重み学習モジュールをさらに備えており、
前記重み学習モジュールは、
前記（ａ）の単語列、前記(ｂ)の単語列、および、前記(ｃ)の単語列のそれぞれについて、所定の評価モデルを用いて、当該単語列とその正解との近さを考慮して、素性の重みを予め生成する
ことを特徴とする請求項４に記載の機械翻訳方法。
【請求項６】
前記部分仮説スコア算出手段は、前記重みを用いて前記部分仮説スコアを算出する
ことを特徴とする請求項５に記載の機械翻訳方法。
【請求項７】
コンピュータを請求項１から請求項３までのいずれか一項に記載の機械翻訳装置として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−２４２８９５（Ｐ２０１１−２４２８９５Ａ）
【公開日】平成２３年１２月１日（２０１１．１２．１）
【国際特許分類】
【出願番号】特願２０１０−１１２６３９（Ｐ２０１０−１１２６３９）
【出願日】平成２２年５月１４日（２０１０．５．１４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年１２月１日（２０１１．１２．１）
【国際特許分類】
【出願日】平成２２年５月１４日（２０１０．５．１４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]