JP 4006297 B2 2007.11.14(57)【 特 許 請 求 の 範 囲 】【請求項１】
部分出力文ＷT 、出力文の各単語が入力文のどの単語のインデックスに対応するかを示す ア ラ イ メ ン ト Ａ 、 既 に 処 理 さ れ た 入 力 文 の イ ン デ ッ ク ス の 集 合 Ｃ 、 ス コ ア ｓ 、 お よ び op
enな 仮 説 と close な 仮 説 と の 識 別 子 open/ close を 要 素 と す る 仮 説 ｈ ＝ （ Ｗ T ， Ａ ， Ｃ ，ｓ ， open/ close ） と 、 入 力 文 の 単 語 の イ ン デ ッ ク ス の 各 部 分 集 合 に 対 応 し た 複 数 の ス タ
ックとを用いてデコーディングを行なう統計的機械翻訳装置において、入力文を入力させる第１手段、
部 分 出 力 文 Ｗ T が 存 在 せ ず か つ 識 別 子 open/ close が close を 表 す 値 に 設 定 さ れ た 初 期
仮説を生成して空集合に対応するスタックに格納するとともに、変数ｃを０に設定する第

10

２手段、
要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在するか否かを判別する第３手段、要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在する場合には、そのうちの１つのスタックを選択する第４手段、第４手段によって選択したスタック内にまだ読み出されていない仮説が存在するか否かを判別する第５手段、第５手段において、選択したスタック内にまだ読み出されていない仮説が存在すると判別した場合には、まだ読み出されていない仮説を１つ読み出して仮説生成処理を実行した
後、第５手段による処理に戻る第６手段、

20

(2)

JP 4006297 B2 2007.11.14

第５手段において、選択したスタック内にまだ読み出されていない仮説が存在しないと判別した場合には、第３手段による処理に戻る第７手段、ならびに第３手段において、要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在しないと判別した場合には、変数ｃを１だけインクリメントし、インクリメント後のｃの値が入力文の単語数に達した場合には、今回のデコーディングを終了させ、インクリメント後のｃの値が入力文の単語数に達していない場合には、第３手段
による処理に戻る第８手段を備えており、第６手段によって実行される仮説生成処理は、第６手段によって読み出された仮説ｈを入力するとともに、変数ｊに１を設定する第１
ステップ、

10

変数ｊが入力文の単語数より大きいか否かを判別し、変数ｊが入力文の単語数より大きい場合には今回の仮説生成処理を終了し、変数ｊが入力文の単語数以下の場合には変数ｊが入力仮説ｈ内のＣに含まれていないか否かを判別する第２ステップ、
第２ステップにおいて、変数ｊが入力文の単語数以下であり、かつ変数ｊが入力仮説ｈ
内 の Ｃ に 含 ま れ て い な い と 判 別 し た 場 合 に は 、 入 力 仮 説 ｈ 内 の 識 別 子 open/ close に 対 応
した仮説生成処理を実行し、生成した仮説をその仮説中のＣに対応するスタックに格納する第３ステップ、ならびに第２ステップにおいて、変数ｊが入力文の単語数以下であり、かつ変数ｊが入力仮説ｈ内のＣに含まれていると判別した場合および第３ステップの処理が終了した場合には、変数ｊを１だけインクリメントした後、第２ステップに戻る第４ステップを備えており、

20

第 ３ ス テ ッ プ は 、 入 力 仮 説 ｈ 内 の 識 別 子 open/ close が close を 表 す 値 で あ る 場 合 に は、 既 に 得 ら れ た 部 分 出 力 文 に 対 し て 単 語 列 を 追 加 す る 操 作 を 行 っ て close に 対 応 し た 仮 説
を 生 成 す る ス テ ッ プ 、 お よ び 入 力 仮 説 ｈ 内 の 識 別 子 open/ close が openを 表 す 値 で あ る 場
合には、入力文の単語を既に得られた部分出力文のある単語に対応付ける操作を行なってopenに 対 応 し た 仮 説 を 生 成 す る ス テ ッ プ を 備 え て お り 、close に 対 応 し た 仮 説 を 生 成 す る ス テ ッ プ に お い て は 、 出 力 文 を 文 末 か ら 生 成 す る た めに、入力仮説ｈ内の部分出力文ＷT の左側に新しい文字列を挿入することにより新しい部
分出力文を生成するとともに入力文のインデックスｊにある単語を新しく生成した部分出
力 文 に お け る 最 初 の 単 語 に 対 応 付 け し 、 openに 対 応 し た 仮 説 を 生 成 す る ス テ ッ プ で は 、 出
力文を文末から生成するために、入力文のインデックスｊにある単語を入力仮説ｈ内の部

30分出力文ＷT における最初の単語に対応付けることを特徴とする統計的機械翻訳装置。
【発明の詳細な説明】【０００１】【発明の属する技術分野】
この発明は、統計的機械翻訳装置に関する。
【０００２】【従来の技術】
近年、コーパスを用いた手法の一つである統計的機械翻訳システムの研究が盛んに行われるようになってきた。この統計的機械翻訳においては、原言語が与えられたときに目的言語へと翻訳する問題を、最大尤度の解を発見する問題として扱われるようになった。この

40

問題はベーズルールにより最大事後確率の問題としてとらえられ、統計的機械翻訳システ
ムは、翻訳モデルというチャネルソース言語をチャネルターゲット言語へと翻訳する確率、チャネルソース言語の尤度を表した言語モデル、さらに、入力文が与えられたときに出力を発見するデコーダの３つの要素で構成されるようになった（文献１参照）。
【０００３】
文 献 １ ： Brown,P.F., Pietra, S.A.D., V.L.D. and Mercer, R.L.: The

Mathematics ofStatistical Machine Translation: Parameter Estimation, Computational Linguistics, Vol.19, No.2,pp.263‑311(1993).
【０００４】
翻訳モデルでは、確率値を推定する効率的なアルゴリズムが知られているが、デコーディ

50

(3)

JP 4006297 B2 2007.11.14

ン グ は NP＿ Completeで あ る こ と が 知 ら れ て い る （ 文 献 ２ 参 照 ） 。
【０００５】
文 献 ２ ： Knight,K.: Decoding Complexity in Word‑Replacement Translation Models,Computational Linguistics, Vol.25, No.4, pp.607‑615(1999).
【０００６】
デコーディングアルゴリズムとして、現在まで様々なアルゴリズム、例えばスタックデコーディングアルゴリズム（文献３参照）、Ａ*

探索アルゴリズム（文献４，５参照）、Ｄ

Ｐアルゴリズム（文献６，７参照）が提唱されてきた。
【０００７】
文 献 ３ ： Berger,A., Brown,P., Pietra,S., Pietra,V., Gillett,J., Kehler,A. and Me

10

rcer,R.: Language Tlanslation Apparatus and Method of Using Context‑Based Transl
ation Models, Technical report, United States Patent, Patent Number 5510981(1996).
文 献 ４ ： Och,F.J., Ueffing,N. and Ney,H.: An Efficient A*

Search Algorithm for S

tatistical Machine Translation, Proc. of the ACL‑2001 Workshop on

Data‑Driven M

achine Translation, Toulouse, France, pp.55‑62(2001).
文 献 ５ ： Wang,Y.‑Y. and Waibel, A.: Decoding Algorithm in Statistical Machine Tra
nslation, Proceedings of the 35th Annual Meeting of the Association for Computat
ional Linguistics(1997).
文 献 ６ ： Garcia‑Varea, I. and Casacuberta, F.: Seach Algorithms for Statistical

20

Machine Translation Based on Dynamic Programming and Pruning Techniques, MT Summ
it VIII, Santiago de Compostela, Galicia, Spain (2001).
文 献 ７ ： Tillmann,C. and Ney, H.: Word Re‑ordering and DP‑based Search in Station
al Machine Translation, Proc. of the COLING 2000(2000).
【０００８】
これらは、入力文に対して出力文を文頭から生成し、原言語文と目的言語文とがほぼ線形に対応づけられることを仮定したプルーニング戦略を取り入れたものであった。このようなアルゴリズムにおいては、例えば日本語と英語のように、性質の異なる言語の翻訳には対応できなかった。
【０００９】30

ま た 、 Germamm ら は ヒ ル ク ラ イ ミ ン グ ア ル ゴ リ ズ ム と イ ン テ ジ ャ ー 解 を 示 し て い る （ 文 献８参照）。前者の手法では、満足な解が得られないことが分かっており、また、後者の手法では現実的に処理速度の問題で、解を得ることができない。
【００１０】
文 献 ８ ： German,U., Jahr,M., Knight,K., Marcu,D. and Yamada,K.: FastDecoding andOptimal Decoding for Machine Translation, Proc. of ACL‑01, Toulouse, France(2001).
【００１１】
この発明は、文末に語順の制約が強いという性質をもつ言語が目的言語である場合に、好適な翻訳結果が得られる統計的機械翻訳装置を提供することを目的とする。

40【００１２】【課題を解決するための手段】
この発明による統計的機械翻訳装置は、部分出力文ＷT 、出力文の各単語が入力文のどの単語のインデックスに対応するかを示すアライメントＡ、既に処理された入力文のイン
デ ッ ク ス の 集 合 Ｃ 、 ス コ ア ｓ 、 お よ び openな 仮 説 と close な 仮 説 と の 識 別 子 open/ closeを 要 素 と す る 仮 説 ｈ ＝ （ Ｗ T ， Ａ ， Ｃ ， ｓ ， open/ close ） と 、 入 力 文 の 単 語 の イ ン デ ックスの各部分集合に対応した複数のスタックとを用いてデコーディングを行なう統計的機
械翻訳装置において、入力文を入力させる第１手段、
部 分 出 力 文 Ｗ T が 存 在 せ ず か つ 識 別 子 open/ close が close を 表 す 値 に 設 定 さ れ た 初 期

50

(4)

JP 4006297 B2 2007.11.14

仮説を生成して空集合に対応するスタックに格納するとともに、変数ｃを０に設定する第２手段、要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在するか否かを判別する第３手段、要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在する場合には、そのうちの１つのスタックを選択する第４手段、第４手段によって選択したスタック内にまだ読み出されていない仮説が存在するか否かを判別する第５手段、第５手段において、選択したスタック内にまだ読み出されていない仮説が存在すると判別した場合には、まだ読み出されていない仮説を１つ読み出して仮説生成処理を実行した

10後、第５手段による処理に戻る第６手段、第５手段において、選択したスタック内にまだ読み出されていない仮説が存在しないと判別した場合には、第３手段による処理に戻る第７手段、ならびに第３手段において、要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在しないと判別した場合には、変数ｃを１だけインクリメントし、インクリメント後のｃの値が入力文の単語数に達した場合には、今回のデコーディングを終了させ、インクリメント後のｃの値が入力文の単語数に達していない場合には、第３手段
による処理に戻る第８手段を備えており、第６手段によって実行される仮説生成処理は、第６手段によって読み出された仮説ｈを入力するとともに、変数ｊに１を設定する第１

20

ステップ、
変数ｊが入力文の単語数より大きいか否かを判別し、変数ｊが入力文の単語数より大きい場合には今回の仮説生成処理を終了し、変数ｊが入力文の単語数以下の場合には変数ｊが入力仮説ｈ内のＣに含まれていないか否かを判別する第２ステップ、
第２ステップにおいて、変数ｊが入力文の単語数以下であり、かつ変数ｊが入力仮説ｈ
内 の Ｃ に 含 ま れ て い な い と 判 別 し た 場 合 に は 、 入 力 仮 説 ｈ 内 の 識 別 子 open/ close に 対 応
した仮説生成処理を実行し、生成した仮説をその仮説中のＣに対応するスタックに格納する第３ステップ、ならびに第２ステップにおいて、変数ｊが入力文の単語数以下であり、かつ変数ｊが入力仮説ｈ内のＣに含まれていると判別した場合および第３ステップの処理が終了した場合には、変30

数ｊを１だけインクリメントした後、第２ステップに戻る第４ステップを備えており、第 ３ ス テ ッ プ は 、 入 力 仮 説 ｈ 内 の 識 別 子 open/ close が close を 表 す 値 で あ る 場 合 に は、 既 に 得 ら れ た 部 分 出 力 文 に 対 し て 単 語 列 を 追 加 す る 操 作 を 行 っ て close に 対 応 し た 仮 説
を 生 成 す る ス テ ッ プ 、 お よ び 入 力 仮 説 ｈ 内 の 識 別 子 open/ close が openを 表 す 値 で あ る 場
合には、入力文の単語を既に得られた部分出力文のある単語に対応付ける操作を行なってopenに 対 応 し た 仮 説 を 生 成 す る ス テ ッ プ を 備 え て お り 、close に 対 応 し た 仮 説 を 生 成 す る ス テ ッ プ に お い て は 、 出 力 文 を 文 末 か ら 生 成 す る た めに、入力仮説ｈ内の部分出力文ＷT の左側に新しい文字列を挿入することにより新しい部
分出力文を生成するとともに入力文のインデックスｊにある単語を新しく生成した部分出
力 文 に お け る 最 初 の 単 語 に 対 応 付 け し 、 openに 対 応 し た 仮 説 を 生 成 す る ス テ ッ プ で は 、 出

40

力文を文末から生成するために、入力文のインデックスｊにある単語を入力仮説ｈ内の部
分出力文ＷT における最初の単語に対応付けることを特徴とする。
【００１３】【発明の実施の形態】
以下、図面を参照して、この発明の実施の形態について説明する。
【００１４】〔１〕統計的機械翻訳の概要についての説明【００１５】
統計的機械翻訳においては、ある原言語のテキストＷS が与えられているときにある目的
言語のテキストＷT へと翻訳する問題を、最大尤度の出力（翻訳結果）を発見する問題と

50

(5)

JP 4006297 B2 2007.11.14

してとらえられ、次式（１）のように表現される。
【００１６】【数１】【００１７】
上記式（１）にベーズルールを適用することにより、上記の問題は、次式（２）に示すよ
うに、チャネルモデルにおける最大事後確率の解を求める問題に置き換えられる。

10【００１８】【数２】【００１９】
このため、翻訳とは、図１（ａ）に示すように「翻訳家の知識Ｐ（ＷT ｜ＷS ）を基にして原言語のテキストＷS を翻訳」する問題として扱われるのではなく、図１（ｂ）に示すように「ある確率Ｐ（ＷT ）で起こりうる目的言語のテキストＷT が、チャネルにより20、( Ｐ（ＷS ｜ＷT ) ）、ＷS として出力された」と仮定して、目的言語のテキストＷT
を原言語のテキストＷS から推測する問題として扱われるようになった（上記文献１参照）。
【００２０】
Ｐ（ＷT ) は言語モデル（事前確立）であり、目的言語のテキストＷT の尤度を示す。
Ｐ（ＷS ｜ＷT ）は翻訳モデル（事後確立）であり、目的言語のテキストＷT が原言語のテキストＷS へと翻訳される確率を表す。また、翻訳モデルに、目的言語のテキストＷTの各単語が原言語のテキストＷS のどの単語のインデックスに対応するかを表すアライメ
ントＡという概念が導入されることにより、翻訳モデルは、次式（３）のように表される。

30【００２１】【数３】【００２２】
図 ２ は 、 目 的 言 語 の テ キ ス ト Ｗ T で あ る 英 語 の 文 " Could you recommend another hotel"と 、 原 言 語 の テ キ ス ト Ｗ S で あ る 日 本 語 文 の 「 他 の ホ テ ル を 紹 介 し て い た だ け ま す か 」とにおける、アライメントの例を示している。例えば、日本語文におけるインデックス１

40の 「 他 」 と イ ン デ ッ ク ス ２ の 「 の 」 が 、 英 語 文 の イ ン デ ッ ク ス ４ の " another"へ と 対 応 づ
けられている。
【００２３】ま た 、 英 語 文 の イ ン デ ッ ク ス ０ に あ る NULLシ ン ボ ル も 単 語 の 一 つ で あ り 、 「 ま す 」 や 「 か」のように、原言語のテキストＷS である日本語文に対応する単語がない場合に対応づけられている。
【００２４】〔１．１〕翻訳モデルの構成【００２５】
アライメントを介した翻訳モデルＰ（ＷS ，Ａ｜ＷT ）はさらに分解され、例えば、次式

50

(6)

JP 4006297 B2 2007.11.14（４）で示すように、以下のように４つのモデルから構成される（上記文献１参照）。
【００２６】【数４】

10【００２７】（ １ ） Lexical モ デ ル ： t(Ｗ S A i ｜ Ｗ T i )ある目的言語の単語ＷT i が原言語の単語ＷS A i へと翻訳される確率。
【００２８】（ ２ ） Fertility モ デ ル ： n(φ i ｜ Ｗ T i )ある目的言語の単語ＷT i がφi 個の原言語の単語と対応される確率。

20【００２９】（ ３ ） Distortionモ デ ル ： d(Ａ ｜ Ｗ T ， Ｗ S ）ＷT とＷS が与えられたときのアライメントがＡである確率。歪みモデルをさらに分解した複雑なモデルも定義されている（上記文献１参照）。
【００３０】（ ４ ） NULLモ デ ル ： 上 記 式 （ ４ ） の 右 辺 の 最 後 の 項
あ る 原 言 語 の φ 0 個 の 単 語 が NULL へ と 対 応 づ け ら れ る 確 率 。
【００３１】〔１．２〕探索問題【００３２】

30

統計機械翻訳における探索問題は、入力文ＷS が与えられたときに、翻訳モデルＰ（ＷS｜ＷT ）＝ΣＰ（ＷS ，Ａ｜ＷT ）と言語モデルＰ（ＷT ）とから最大尤度の出力文ＷTを発見する問題として扱われる。ただし、可能なＡの空間は、次式（５）で示されるように、非常に大きく、翻訳を決定する場合、その近似値、Ｐ（ＷS ｜ＷT ）≒Ｐ（ＷS ，Ａ｜ＷT ）が用いられる。

【００３３】【数５】

40【００３４】
統計機械翻訳における探索問題は、単語の単位の翻訳だけでなく、並び替えの問題も含ん
で い る こ と か ら NP＿ Completeで あ る こ と が 知 ら れ て い る （ 上 記 文 献 ２ 参 照 ） 。 過 去 の 研 究においては、出力を文頭から生成する制約を加え、プルーニング（剪定）を行うことによりデコーディングアルゴリズムを実現している（上記文献３〜８参照）。ただし、プルー
ニングも原言語と目的言語とがほぼ線形に対応づけられていることを仮定しており、日本
語と英語間の翻訳といった語順の相違が大きい言語間の翻訳を想定していない。
【００３５】
以下、出力の方向を考慮したデコーディングアルゴリズムについて説明する。
【００３６】50

(7)JP 4006297 B2 2007.11.14〔２〕デコーディングアルゴリズム【００３７】
本 発 明 に よ る デ コ ー デ ィ ン グ ア ル ゴ リ ズ ム は 、 Tillman （ 上 記 文 献 ７ 参 照 ） や Och （ 上 記
文献４参照）らによるビームサーチアルゴリズムに基づいており、また、仮説に適用される 操 作 は Berger（ 上 記 文 献 ３ 参 照 ） 、 Och （ 上 記 文 献 ４ 参 照 ） や Germann （ 上 記 文 献 ８ 参照）らに基づいている。
【００３８】
まず、デコーディングアルゴリズムで用いられる仮説およびマルチスタックについて説明する。
【００３９】

10

仮 説 ｈ は 、 （ Ｗ T ， Ａ ， Ｃ ， ｓ ， open/close) の よ う に 表 現 さ れ る 。 仮 説 の 各 要 素 は 次 のように定義される。
【００４０】
ＷT ：部分出力文
Ａ：部分的に決定されたアライメント

Ｃ：既に処理された入力文のインデックスの集合

ｓ

：スコア

open/close： openな 仮 説 と close な 仮 説 と の 識 別 子 で あ り 、 ０ は openな 仮 説 を 表 し 、 １ はclose な 仮 説 を 表 す 。
【００４１】

20

openな 仮 説 で は 、 入 力 文 の 単 語 を 既 に 得 ら れ た 部 分 出 力 文 の あ る 単 語 と 対 応 づ け る こ と に
よ り 、 fertility （ 出 力 文 の １ つ の 単 語 に 対 応 付 け ら れ る 入 力 文 の 単 語 の 数 ） を 増 大 さ せる 操 作 が 行 わ れ る 。 close な 仮 説 で は 、 既 に 得 ら れ た 部 分 出 力 文 に 対 し て 単 語 列 Ｗ T
追加する操作が行われる。この単語列ＷTをは 、 fertility が １ 以 上 の 単 語 １ 個 と fertil

ity が ゼ ロ の 単 語 の 列 か ら 構 成 さ れ る 。
【００４２】
マルチスタックは、スタックの集合であり、入力文の単語のインデックスの各部分集合（
各組み合わせ）に対応したスタックが存在している。例えば、入力文が、インデックス１の単語、インデックス２の単語およびインデックス３の単語の３つの単語から構成されている場合には、入力文の単語のインデックスの各部分集合に応じた、Ｃ＝｛｝、Ｃ＝｛１30｝、Ｃ＝｛２｝、Ｃ＝｛３｝、Ｃ＝｛１，２｝、Ｃ＝｛１，３｝、Ｃ＝｛２，３｝、Ｃ＝｛１，２，３｝の７個のスタックが用意される。
【００４３】
各スタックには、デコーディングアルゴリズムによって生成された仮説が格納される。各スタックにおいては、スコアの高い順に、仮説がソートされる。スタックに格納されている 仮 説 の 数 が 所 定 の 閾 値 （ max‑stack‑size) に 達 し て い る 場 合 に 、 新 た な 仮 説 を 格 納 し ようとする場合には、それらの仮説の中でスコアの最も低い仮説を捨てることにより、常に
max‑stack‑sizeの 数 の 仮 説 を 格 納 す る よ う に し て い る 。
【００４４】〔２．１〕全体フロー40【００４５】
図３は、デコーディングアルゴリズムを示している。
【００４６】
ま ず 、 入 力 文 Ｗ s ＝ Ｗ s1 , Ｗ s2 , … Ｗ s2 m を 入 力 す る （ ス テ ッ プ １ ） 。 入 力 文 Ｗ s の 入 力
長（単語数）はｍである。
【００４７】
次に初期化処理を行う（ステップ２）。初期化処理においては、初期仮説ｈ0 が生成されて、Ｃ＝｛｝のスタックに格納される。初期仮説ｈ0 では、ＷT は存在せず（ＷT ＝）、アライメントＡは−１に設定され、入力分のインデックスの集合Ｃは空（｛｝）に設定 さ れ 、 ス コ ア ｓ は １ ． ０ に 設 定 さ れ 、 open/close識 別 子 は close を 表 す

１

に設定さ

50

(8)

JP 4006297 B2 2007.11.14

れる。したがって、初期仮説ｈ0 は、（ＷT ＝，Ａ＝（−１，…−１），Ｃ＝｛｝，ｓ ＝ １ ． ０ ， open/close＝ １ ） と な る 。 ま た 、 変 数 ｃ が ０ に 設 定 さ れ る 。 な お 、 以 下 の 説
明において、｜Ｃ｜は、入力文の単語のインデックスの各部分集合の要素数を表すものとする。
【００４８】
次に、｜Ｃ｜＝ｃであるスタック（要素数がｃ個である部分集合に対応するスタック）でまだ選択されていないスタックが存在するか否かを判別する（ステップ３）。
【００４９】｜Ｃ｜＝ｃであるスタックでまだ選択されていないスタックが存在する場合には、そのうちの１つのスタックを選択する（ステップ４）。そして、選択したスタック内にまだ読み10出されていない仮説が存在するか否かを判別する（ステップ５）。選択したスタック内にまだ読み出されてない仮説が存在する場合には、まだ読み出されてない仮説ｈを１つだけ読み出す（ステップ６）。そして、仮説生成処理を実行する（ステップ７）。そして、ステップ５に戻る。
【００５０】
上記ステップ３において、｜Ｃ｜＝ｃであるスタックでまだ選択されていないスタックが存在しない場合には、変数ｃの値を１だけインクリメント（＋１）する（ステップ８）。
そして、ｃがｍに達したか否かを判定する（ステップ９）。ｃがｍに達していない場合（
ｃ＜ｍ）には、ステップ３に戻る。
【００５１】

20

上記ステップ５において、上記ステップ４で選択したスタック内にまだ読み出されてない仮説が存在しない場合には、ステップ３に戻る。
【００５２】
上記ステップ９において、ｃがｍに達していると判別した場合（ｃ＝ｍ）には、今回の処理を終了する。この時点において、｜Ｃ｜＝ｍであるスタックの中に解が存在することになる。
【００５３】〔２．２〕仮説生成処理手順【００５４】
図４は、図３のステップ７の仮説生成処理手順を示している。

30【００５５】
以下の説明において、ｊは入力文ＷS の単語のインデックスを表す変数であり、ｉは出力
文ＷT の単語のインデックスを表す変数であるとする。
【００５６】
上記ステップ６で読み出された仮説ｈを入力する（ステップ１１）。変数ｊとして１を設定する（ステップ１２）。
【００５７】
そして、ｊが（ｍ＋１）に達したか否かを判定する（ステップ１３）。ｊが（ｍ＋１）に達していない場合（ｊ≦ｍ）には、ｊが入力仮説ｈ内のＣに含まれていないか否かを判定する（ステップ１４）。

40【００５８】
ｊ が 入 力 仮 説 ｈ 内 の Ｃ に 含 ま れ て い な い 場 合 に は 、 入 力 仮 説 ｈ 内 の open/close識 別 子 が open( ＝ 0)で あ る か 、 close(＝ 1)で あ る か を 判 定 す る （ ス テ ッ プ １ ５ ） 。
【００５９】
入 力 仮 説 ｈ が openで あ る 場 合 に は 、 openに 対 応 し た 仮 説 生 成 処 理 を 行 う （ ス テ ッ プ １ ６ ）。 入 力 仮 説 ｈ が close で あ る 場 合 に は 、 close に 対 応 し た 仮 説 生 成 処 理 を 行 う （ ス テ ッ プ
１ ７ ） 。 openに 対 応 し た 仮 説 生 成 処 理 お よ び close に 対 応 し た 仮 説 生 成 処 理 の 詳 細 に つ いては、後述する。
【００６０】
ステップ１６またはステップ１７によって新たな仮説が生成された場合には、生成された

50

(9)

JP 4006297 B2 2007.11.14

新たな仮説を、その仮説中のＣに対応するスタックに格納する（ステップ１８）。
【００６１】
そして、変数ｊの値を１だけインクリメント（＋１）した後（ステップ１９）、ステップ
１３に移行する。
【００６２】
上記ステップ１４において、ｊがＣに含まれていると判定した場合には、ステップ１９に移行する。
【００６３】
上記ステップ１３において、ｊが（ｍ＋１）に達していると判定した場合（ｊ＝（ｍ＋１））には、今回の仮説生成処理は終了する。つまり、図３のステップ５に戻る。

10【００６４】
以 下 、 openに 対 応 し た 仮 説 生 成 処 理 お よ び close に 対 応 し た 仮 説 生 成 処 理 に つ い て 説 明 する。
【００６５】〔 ２ ． ３ 〕 openに 対 応 し た 仮 説 生 成 処 理【００６６】
openに 対 応 し た 仮 説 生 成 処 理 で は 、 以 下 の よ う な 仮 説 を 、 openと close と の ２ 種 類 生 成 する。
【００６７】
入力文ＷS のうちのインデックスｊにある単語を、インデックスｉにある部分出力文の単20語に対応させる。
【００６８】
こ の 実 施 の 形 態 で は 、 部 分 出 力 文 を 文 末 か ら 生 成 す る （ right‑to‑left デ コ ー デ ィ ン グ )ため、インデックスｉにある出力単語は部分出力文ＷT における最初の単語（ｉ＝１）となる。したがって、図５に示すように、入力文ＷS のうちのインデックスｊにある単語Ｗ
S j が、入力仮説ｈ内の部分出力文ＷTにおける最初の単語ＷT 1 （ｉ＝１）に対応づけられる。
【００６９】
この場合には、仮説の要素である部分出力文ＷT は変更されず、アライメントＡが変更される。つまり、Ａ[ j ] として、ｉ＝１が代入される（Ａ[ j ] ←ｉ（＝１））。また、

30

仮説の要素であるＣとして、Ｃ∪｛ｊ｝が設定される（Ｃ←Ｃ∪｛ｊ｝）。
【００７０】
なお、Ｃ∪｛ｊ｝は、例えば、Ｃが｛｝でかつｊが１であれば、｛｝∪｛１｝＝｛１｝となり、例えば、Ｃが｛１｝でかつｊが２であれば、｛１｝∪｛２｝＝｛１，２｝となり、
例えば、Ｃが｛２，３｝でかつｊが１であれば、｛２，３｝∪｛１｝＝｛１，２，３｝となる。
【００７１】
仮説の要素であるスコアｓは、よく知られているように次式（６）に基づいて算出される。
【００７２】40【数６】【００７３】
こ こ で 、 ｆ を Ｗ T [i] の 新 し い ferrility と す る 。 ま た 、 Distortionモ デ ル ( 歪 み モ デ ル) の確率を再計算する。

50

(10)

JP 4006297 B2 2007.11.14【００７４】
以 上 の よ う な 要 素 を 持 ち 、 か つ open/close識 別 子 が open（ ＝ ０ ） で あ る 仮 説 と 、 open/clo
se識 別 子 が close(＝ １ ） で あ る 仮 説 と が 生 成 さ れ る 。
【００７５】な お 、 従 来 の よ う に 部 分 出 力 文 を 文 頭 か ら 生 成 す る （ left‑to‑right デ コ ー デ ィ ン グ ) に
おいては、インデックスｉにある出力単語は部分出力文ＷT における最後の単語（ｉ＝｜ＷT ｜）となる。したがって、図６に示すように、入力文ＷS のうちのインデックスｊにある単語ＷS j が、入力仮説内の部分出力文ＷT における最後の単語ＷT l （ｉ＝｜ＷT ｜）に対応づけられる。この結果、Ａ[ j ] として、ｉ＝｜ＷT ｜が代入される（Ａ[ j ] ←ｉ（＝｜ＷT ｜）。

10【００７６】〔 ２ ． ４ 〕 close に 対 応 し た 仮 説 生 成 処 理【００７７】
close に 対 応 し た 仮 説 生 成 処 理 で は 、 NULLへ 対 応 さ れ た 仮 説 と 、 文 字 列 の 挿 入 お よ び 挿 入
文字列へ対応づけられた仮説とを生成する。
【００７８】〔 ２ ． ４ ． １ 〕 NULLへ 対 応 さ れ た 仮 説【００７９】
入 力 文 の う ち 、 イ ン デ ッ ク ス ｊ に あ る 単 語 を 、 NULL（ イ ン デ ッ ク ス ０ に あ る 出 力 単 語 ） に対応させる。

20【００８０】
つまり、Ａ[ j ] として、０が代入される（Ａ[ j ] ←０）。また、仮説の要素であるＣと し て 、 Ｃ ∪ ｛ ｊ ｝ が 設 定 さ れ る （ Ｃ ← Ｃ ∪ ｛ ｊ ｝ ） 。 仮 説 の 要 素 で あ る openclose 識 別
子 は close （ ＝ １ ） と す る 。 仮 説 の 要 素 で あ る ス コ ア ｓ は 、 よ く 知 ら れ て い る よ う に 次 式（７）に基づいて算出される。
【００８１】【数７】

30【００８２】
こ こ で 、 ｆ を NULLの 新 し い ferrility と す る 。
【００８３】〔２．４．２〕文字列の挿入および挿入文字列へ対応づけられた仮説【００８４】

40

以 下 の よ う な 仮 説 を 、 openと close と の ２ 種 類 生 成 す る 。
【００８５】
まず、入力仮説内の部分出力文ＷT に新しい文字列ＷTを挿入する。この実施の形態では 、 部 分 出 力 文 を 文 末 か ら 生 成 す る （ right‑to‑left デ コ ー デ ィ ン グ ) た め 、 図 ７ に 示 す
ように、入力仮説内の部分出力文ＷT の左側に新しい文字列ＷT
Tを挿入する（ＷT ←Ｗ＋ＷT ）。

【００８６】
また、入力文ＷS のうち、インデックスｊにある単語ＷS j を、インデックスｉにある出力
単 語 に 対 応 さ せ る 。 こ の 実 施 の 形 態 で は 、 部 分 出 力 文 を 文 末 か ら 生 成 す る （ right‑to‑left デコーディング) ため、図７に示すように、インデックスｉにある出力単語は新しいＷ

50

(11)
T

（図７のＷT＋ＷT ）における最初の単語ＷT 1

JP 4006297 B2 2007.11.14（ｉ＝１）となる。したがって、アライメントＡ[ j ] として、ｉ＝１が代入される（Ａ[ j ] ←ｉ（＝１））。
【００８７】
また、仮説の要素であるＣとして、Ｃ∪｛ｊ｝が設定される（Ｃ←Ｃ∪｛ｊ｝）。仮説の要素であるスコアｓは、よく知られているように次式（８）に基づいて算出される。
【００８８】【数８】

10【００８９】
Ｐ l m は 、 言 語 モ デ ル に よ る ス コ ア で あ り 、 も し 、 Ｗ T [iＷ T [i] において、i≦０の場合、] ＝ Ｂ Ｏ Ｓ (Beggining of Sentence Marker)と な る 。

【００９０】
以 上 の よ う な 要 素 を 持 ち 、 か つ open/close識 別 子 が open( ＝ ０ ） で あ る 仮 説 と 、 open/clo

20

se識 別 子 が close(＝ １ ） で あ る 仮 説 と が 生 成 さ れ る 。
【００９１】
なお、新しい文字列ＷTは複数生成される。そして、新しい文字列毎に、上記のようにして、２つずつ仮説が生成される。新しい文字列ＷTの生成方法については、上記文献

３，４，５に説明されている。
【００９２】
従 来 の よ う に 部 分 出 力 文 を 文 頭 か ら 生 成 す る （ left‑to‑right デ コ ー デ ィ ン グ ) に お い ては、文字列ＷT を挿入する場合、図８に示すように、入力仮説内の部分出力文ＷT の右側に新しい文字列ＷTを挿入する（ＷT ←ＷT ＋ＷT

出力単語は新しいＷT （図８のＷT ＋ＷT）。また、インデックスｉにある）における最後の単語ＷT l（ｉ＝｜ＷT ｜30）となる。この結果、Ａ[ j ] として、ｉ＝｜ＷT ｜が代入される（Ａ[ j ] ←ｉ（＝｜ＷT ｜）。
【００９３】〔２．５〕入力文ＷS の入力長ｍが３の場合の流れについの説明【００９４】
入力文ＷS の入力長ｍが３の場合の、デコーディングアルゴリズムの流れについて簡単に説明しておく。
【００９５】
まず、Ｃ＝｛｝に対応するスタックに、初期仮説ｈ0 ＝（ＷT ＝，Ａ＝（−１，…−

１ ） ， Ｃ ＝ ｛ ｝ ， ｓ ＝ １ ． ０ ， open/close＝ １ ） が 格 納 さ れ る （ 図 ３ の ス テ ッ プ １ 〜 ２ ）40。
【００９６】
そして、図３のステップ６において、Ｃ＝｛｝に対応するスタックから初期仮説ｈ0 が取り 出 さ れ る 。 そ し て 、 図 ４ の ス テ ッ プ １ ７ の close に 対 応 し た 仮 説 生 成 処 理 に よ っ て 、 ｊ＝１，２、３それぞれに対応した新たな仮説が生成され、Ｃ＝｛１｝、Ｃ＝｛２｝、Ｃ＝｛３｝それぞれに対応するスタックに、新たな仮説が格納される。
【００９７】
次に、Ｃ＝｛１｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝２、３それぞれに対応した新たな仮説が生成され、Ｃ＝｛１，２｝、Ｃ＝｛１，３｝それぞれに対応するスタックに、新たな仮説が格納される。

50

(12)

JP 4006297 B2 2007.11.14【００９８】
同様に、Ｃ＝｛２｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１，３に対応した新たな仮説が生成され、Ｃ＝｛１，２｝、Ｃ＝｛２，３｝に対応するスタックに、新たな仮説が格納される。
【００９９】
同様に、Ｃ＝｛３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１，２に対応した新たな仮説が生成され、Ｃ＝｛１，３｝、Ｃ＝｛２，３｝に対応するスタックに、新たな仮説が格納される。
【０１００】
次に、Ｃ＝｛１，２｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づ

10

いて、ｊ＝３に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。
【０１０１】
次に、Ｃ＝｛１，３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝２に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。
【０１０２】
次に、Ｃ＝｛２，３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。

20【０１０３】
この結果、Ｃ＝｛１，２，３｝に対応するスタックに、解（翻訳結果）がスコアの高い順番に格納される。
【０１０４】〔３〕デコーディング方向による影響【０１０５】
従 来 の left‑to‑right デ コ ー デ ィ ン グ ア ル ゴ リ ズ ム に お い て は 、 入 力 単 語 を 処 理 し 、 対 応する翻訳を単語単位に決定して部分出力文を文頭から生成する。このような挙動により、
言語モデルや翻訳モデルは文頭からスコアリングを行うことにより、「良い仮説」と「悪い仮説」とを区別する力が大きくなることが考えられる。

30【０１０６】
例えば、英語やドイツ語、フランス語のように文頭からの語順の制約が強い言語を目的言語として翻訳を行った場合、文頭からのスコアリングによる制約が強くなり、ビームサー
チのプルーニングを行っても出力の質が落ちることがない。逆に、このような言語に対して 本 実 施 の 形 態 の よ う に right‑to‑left デ コ ー デ ィ ン グ 行 う と 、 仮 説 間 の ス コ ア の 差 が 小
さく、仮説数が増大し、プルーニングによる影響が大きくなる。
【０１０７】
日 本 語 の よ う な 文 末 に 語 順 の 制 約 が あ る 場 合 、 そ の よ う な 言 語 を 目 的 言 語 と し て right‑to‑left デ コ ー デ ィ ン グ を 行 う と ス コ ア の 差 が 大 き く な り 、 left‑to‑right に 行 う と ス コ アの差が小さくなると考えられる。したがって、文末に語順の制約がある言語が目的言語で40

あ る 場 合 に は 、 right‑to‑left に デ コ ー デ ィ ン グ を 行 う こ と が 好 ま し い 。
【０１０８】〔４〕実験【０１０９】
今 回 行 っ た 実 験 の コ ー パ ス は 、 大 規 模 旅 行 会 話 集 （ 文 献 ９ 参 照 ） か ら 抽 出 し た 172,481 の
日 英 の 対 訳 文 で あ り 、 そ の 統 計 情 報 を 表 １ に 示 す 。 コ ー パ ス か ら 152,183 文 か ら な る ト レ
ー ニ ン グ セ ッ ト 、 検 証 セ ッ ト を 10,148文 、 さ ら に テ ス ト セ ッ ト 10,150文 を 取 り 出 し た 。
【０１１０】
文 献 ９ ： Takezawa,T., Sumita,E., Sugaya,F., Yamamoto,H. and Yamamoto,S.: Toward a
Broad‑coverage Bilingual Corpus for Speech Translation of Travel Conversations

50

(13)

JP 4006297 B2 2007.11.14

in the Real World, Proc. of LREC 2002, Las Palmas, CanaryIslands, Spain, pp.147‑
152(2002).
【０１１１】【表１】

10【０１１２】
翻 訳 モ デ ル は 日 英 、 英 日 方 向 、 ど ち ら も IBM Model‑1 か ら IBM Model‑4 ま で ブ ー ト ス ト ラ
ッ プ し て ト レ ー ニ ン グ を 行 い 、 途 中 に HMM Model に よ る ト レ ー ニ ン グ を 行 っ て い る （ 文 献１０参照）。また、検証セットによるクロスバリデーションを行いながらトレーニングを
繰 り 返 し た 。 IBM Model‑4 に お い て は 、 品 詞 を 単 語 ク ラ ス と し て 用 い た 。
【０１１３】

20

文 献 １ ０ ： Och,F.J., Tillmann,C. and Ney,H.: Improved Alignment Models for Stati
stical Machine Translation, Proceedings of the Joint Conf. of

Empirical Methods

in Natural Language Processing and Very Large Corpora, University of Maryland,College Park,MD(1999).
【０１１４】
ト レ ー ニ ン グ コ ー パ ス の ビ テ ル ビ ア ラ イ メ ン ト か ら 、 fertility が ゼ ロ と な る 単 語 列 を 取り 出 し 、 頻 度 が 10未 満 の も の を 取 り 除 い た 。 ま た 、 テ ス ト セ ッ ト か ら 文 長 が 6 、 8 、 10で
あ る 、 そ れ ぞ れ 50文 、 合 計 150 の 日 本 語 、 英 語 の 文 を 取 り 出 し 、 上 記 の ２ つ の ア ル ゴ リ ズ
ムによるデコーディングの実験を行った。
【０１１５】

30

翻訳結果を評価するに当たって、以下の基準を用いた。
【０１１６】・ 単 語 誤 り 率 (WER):

挿入、削除、置換に対してペナルティを１として計算。

【０１１７】
・ 位 置 独 立 単 語 誤 り 率 (PER):WER で は 、 実 際 の 翻 訳 に 起 こ り う る 並 び 替 え に 対 し て ペ ナ

ル テ ィ が 大 き く な る 。 従 っ て 、 PER で は 位 置 の 情 報 を 無 視 し 、 出 力 単 語 の 集 合 の 正 し さ の評価を行う（上記文献４参照と文献１１参照）。
文 献 １ １ ： Watanabe,T., Imamura,K. and Sumita,E.: Statistical MachineTranslation
Based on Hierarchical Phrase Alignment, Proc. of TMI 2002,Keihanna, Japan(2002).
【０１１８】

40

・ BLEUス コ ア : 正 解 集 合 の 全 て に 対 し て N‑gramの 正 解 率 を 計 算 す る も の で あ り 、 短 い 出 力に対してペナルティを与えている（文献１２参照）。
文 献 １ ２ ： Papineni,K., Roukos,S., Ward,T. and Zhu,W.J.: Bleu: a Method for Automatic Evaluation of Machine Translation, Proceedings of the 40th Annual Meetingof the Association for Computational Linguistics(ACL),pp.311‑318(2002).
【０１１９】・ NISTス コ ア : BLUEと 同 様 な ス コ ア で あ る が 、 正 解 率 を 正 解 集 合 の N‑gramに 対 す る 平 均 出
力単語情報量として表現している（文献１３参照）。
文 献 １ ３ ： Automatic Evaluation of Machine Translation Quality using N‑gram Co‑O
ccurrence Statistics, http://www.nist.gov/speech/tests/mt/doc/ngram‑study.pdf(20

50

(14)

JP 4006297 B2 2007.11.1402) ．
【０１２０】
・ 主 観 評 価 (SE): 翻 訳 結 果 を 人 手 で Ａ 、 Ｂ 、 Ｃ 、 Ｄ と ４ 段 階 に ラ ン ク 付 け を す る （ 文 献 １
４参照）。
文 献 １ ４ ： Sumita,E., Yamada,S., Yamamoto,K., Paul,M., Kashioka,H., Ishikawa,K.and Shirai,S.: Solutions to Problems Inherent in Spoken‑languageTranslation: The A
TR‑MATRIX Approch, Machine Translation Summit VII, PP.229‑235(1999).
【０１２１】
・ 探 索 誤 り 率 (SER):

翻訳の正さあるいは誤り以外に、各デコーディングアルゴリズムが翻訳モデルと言語モデルから最適解を得られたかどうかを評価した。出力結果のうち、ス10コアが最も高い出力の集合を正解集合として、誤り率を求めた。
【０１２２】
表 ２ は 、 left‑to‑right(LtoR) と right‑to‑left(RtoL) と の デ コ ー デ ィ ン グ ア ル ゴ リ ズ ムの翻訳結果を示す。日英、英日の翻訳例をそれぞれ図９、図１０に示す。
【０１２３】【表２】

20【０１２４】〔５〕考察30

表 ２ に お け る 探 索 誤 り 率 (SER) か ら 、 日 英 翻 訳 に つ い て は 、 right‑to‑left デ コ ー デ ィ ン
グ ア ル ゴ リ ズ ム よ り 、 left‑to‑right デ コ ー デ ィ ン グ ア ル ゴ リ ズ ム が 良 く 、 ま た 、 英 日 翻訳ではその逆の結果が得られた。このことから、言語モデル、翻訳モデルに基づいて翻訳結果を得るに当たって、出力文の言語の特性に合わせて出力の方向を制約する手法の有効性が確認された。
【０１２５】
翻 訳 結 果 の 客 観 評 価 値 （ WER/PER/BLEU/NIST)で は 、 日 英 翻 訳 で ア ル ゴ リ ズ ム 間 に 差 異 が 認
め ら れ な か っ た 。 英 日 翻 訳 に お い て は 、 right‑to‑left デ コ ー デ ィ ン グ ア ル ゴ リ ズ ム は 、WER/PER の 点 に お い て 優 れ て い る こ と が 確 認 さ れ た 。
【０１２６】

40

主 観 評 価 (SE)で は 、 日 英 翻 訳 に お い て 、 left‑to‑right デ コ ー デ ィ ン グ ア ル ゴ リ ズ ム は 、right‑to‑left デ コ ー デ ィ ン グ ア ル ゴ リ ズ ム よ り Ａ ラ ン ク の 文 の 割 合 が 増 加 し て い る 。 ただ し 、 英 日 翻 訳 で は 、 ア ル ゴ リ ズ ム 間 で 主 観 評 価 (SE)は ほ ぼ 変 わ ら な か っ た 。
【０１２７】【発明の効果】
この発明によれば、文末に語順の制約が強いという性質をもつ言語が目的言語である場合に、好適な翻訳結果が得られるようになる。
【図面の簡単な説明】【図１】統計的機械翻訳モデルを説明するための模式図である。
【図２】アライメントの例を示す模式図である。

50

(15)

JP 4006297 B2 2007.11.14【図３】デコーディングアルゴリズムを示すフローチャートである。
【図４】図３のステップ７の仮説生成処理手順を示すフローチャートである。
【図５】

right‑to‑left デ コ ー デ ィ ン グ に よ る 、 openに 対 応 し た 仮 説 生 成 処 理 を 説 明 するための模式図である。
【図６】

left‑to‑right デ コ ー デ ィ ン グ に よ る 、 openに 対 応 し た 仮 説 生 成 処 理 を 説 明 するための模式図である。
【図７】

right‑to‑left デ コ ー デ ィ ン グ に よ る 、 close に 対 応 し た 仮 説 生 成 処 理 を 説 明するための模式図である。
【図８】

left‑to‑right デ コ ー デ ィ ン グ に よ る 、 close に 対 応 し た 仮 説 生 成 処 理 を 説 明するための模式図である。

10【図９】実験によって得られた日英翻訳結果の例を示す模式図である。
【図１０】実験によって得られた英日翻訳結果の例を示す模式図である。

【図１】

【図２】

【図３】

(16)
【図４】

【図５】

【図６】

【図７】

【図８】

【図９】

【図１０】

JP 4006297 B2 2007.11.14