(57)【要約】【課題】長文に対する依存構造のような分岐数が多い構文木に対しても、効率よく並べ替えを行うことができる並べ替え装置、並べ替え方法、及び並び替えプログラムを提供する。【解決手段】入力した原言語文の構文解析を行って、原言語文を表す構文木を生成し、構文木の兄弟ノードの二個組の各々について、兄弟ノードの二個組の現在の順序を維持すべきか反転すべきかを判定するための予め定められた二値分類並べ替えモデルに基づいて、判定スコアを計算し、構文木の兄弟ノード群の各々について、計算された判定スコアに基づいて兄弟ノードの二個組の現在の順序を維持するか反転することにより、兄弟ノード群を並べ替え、兄弟ノード群の順序が決定不可能な場合、分枝限定法により兄弟ノード群の最適な順序を探索することにより兄弟ノード群を並べ替え、並べ替えられた構文木に基づいて、原言語文の単語を並べ替える。【選択図】図２
2018081460.tif 000002
【特許請求の範囲】
【請求項１】
入力した原言語文の構文解析を行って、前記原言語文を表す構文木を生成する構文解析部と、
前記生成された構文木の兄弟ノードの二個組の各々について、兄弟ノードの二個組の現在の順序を維持すべきか反転すべきかを判定するための予め定められた二値分類並べ替えモデルに基づいて、判定スコアを計算する二値分類並べ替えスコア計算部と、
前記生成された構文木の兄弟ノード群の各々について、前記二値分類並べ替えスコア計算部により計算された判定スコアに基づいて兄弟ノードの二個組の現在の順序を維持するか反転することにより、前記兄弟ノード群を並べ替え、
前記兄弟ノード群の順序が決定不可能な場合、分枝限定法により前記兄弟ノード群の最適な順序を探索することにより前記兄弟ノード群を並べ替え、前記並べ替えられた前記構文木に基づいて、前記原言語文の単語を並べ替える最適順序決定部と、
を含む並べ替え装置。
【請求項２】
学習用の原言語文と学習用の目的言語文との間の単語の対応関係を表す単語対応データと、前記学習用の原言語文を表す構造木とに基づいて、前記構文木の兄弟ノード二個組の各々について現在の順序を維持すべきか反転すべきかを示す二値分類正解を決定する二値分類正解決定部と、
前記二値分類正解、及び前記構文木の兄弟ノード二個組の各々について抽出される素性に基づいて、前記二値分類並べ替えモデルを学習する二値分類並べ替え学習部と、
を更に備えた請求項１記載の並べ替え装置。
【請求項３】
前記最適順序決定部は、前記生成された構文木の兄弟ノード群の各々について、前記二値分類並べ替えスコア計算部により計算された判定スコアに基づいて、トポロジカルソートにより前記兄弟ノード群を並べ替える
請求項１又は２記載の並び替え装置。
【請求項４】
構文解析部、二値分類並べ替えスコア計算部、及び最適順序決定部を備えた並べ替え装置が行う並べ替え方法であって、
前記構文解析部が、入力した原言語文の構文解析を行って、前記原言語文を表す構文木を生成するステップと、
前記二値分類並べ替えスコア計算部が、前記生成された構文木の兄弟ノードの二個組の各々について、兄弟ノードの二個組の現在の順序を維持すべきか反転すべきかを判定するための予め定められた二値分類並べ替えモデルに基づいて、判定スコアを計算するステップと、
前記最適順序決定部が、前記生成された構文木の兄弟ノード群の各々について、前記二値分類並べ替えスコア計算部により計算された判定スコアに基づいて兄弟ノードの二個組の現在の順序を維持するか反転することにより、前記兄弟ノード群を並べ替え、
前記兄弟ノード群の順序が決定不可能な場合、分枝限定法により前記兄弟ノード群の最適な順序を探索することにより前記兄弟ノード群を並べ替え、前記並べ替えられた前記構文木に基づいて、前記原言語文の単語を並べ替えるステップと、
を行う並べ替え方法。
【請求項５】
コンピュータを、請求項１〜３の何れか１項記載の並べ替え装置の各部として機能させるための並べ替えプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、言語文に含まれる単語の並び替えを行う並べ替え装置、並べ替え方法、及び並び替えプログラムに関する。
【背景技術】
【０００２】
原言語の文書から目的言語の文書への翻訳を自動的に行うための機械翻訳の技術において、日本語と英語のように語順の違いが大きい言語の翻訳は難しいと言われており、その解決のための様々な技術が提案されている。
【０００３】
近年提案された技術の一つに、「事前並べ替え」と称する、語句の翻訳を実行する前に原言語の語順を目的言語の語順に近づくように並べ替えることで、前述の語順の違いの問題を軽減させる技術が提案されている（例えば、非特許文献１、非特許文献２、非特許文献３、及び非特許文献４を参照）。
【０００４】
非特許文献１に記載の技術は、英語から日本語への翻訳において、日本語の主辞後置性と呼ばれる文法上の特性に基づいて英語を日本語に近い語順に変換する規則を利用することを特徴としている。また、非特許文献２に記載の技術は、日本語から英語への翻訳において、日本語を英語の語順に近づけるためにどう変換を行うかを統計的なモデルで学習することを特徴としている。
【０００５】
このように、非特許文献１に記載の技術、及び非特許文献２に記載の技術は、原言語の文を構文解析し、二分句構文木を構築した後、句の構成要素（子ノード）の順序の入れ替えを規則あるいは統計的なモデルで表現するものである。
【０００６】
一方、非特許文献３に記載の技術、及び非特許文献４に記載の技術は、非特許文献２と同様に統計的なモデルを利用して語順の変換を行うが、前提となる構文木が依存構文木と呼ばれ、一般には（３以上の分岐を伴う）多分木であって、３個以上の構成要素（子ノード）の順序を入れ替えている。
【０００７】
非特許文献３に記載の技術は、ランキングＳＶＭと呼ばれる順序学習の技術を用いて順序入れ替えによる語順変換を実現する技術である。また、非特許文献４に記載の技術は、３個以上の要素の順序付けの問題を、すべての要素二個組の順序（どちらが前でどちらが後ろか）を求める二値分類の問題とし、各要素二個組の順序付け確率に基づいて、３個以上の要素を並べたときの合計順序スコアを最大化するような要素の順序を分枝限定法を用いて効率的に求める技術である。
【０００８】
非特許文献４には、精度の面で、非特許文献３に記載の技術より優れていると記載されている。しかしながら、非特許文献４に記載の要素並べ替え方法は、構文木の分岐数が多くなると計算量が指数的に増大する可能性があり、非特許文献４においても分岐数が１２以上の場合は並べ替えを行わないと記載されている。また、分岐数が１２に満たない場合においても分岐数が多い場合の処理に時間を要することは避けられない。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Hideki Isozaki, Katsuhito Sudoh, Hajime Tsukada, and Kevin Duh, 2010. Head Finalization: A Simple Reordering Rule for SOV Languages. In Proceedings of the Joint Fifth Workshop on Statistical Machine Translation and MetricsMATR, pages 244-251.
【非特許文献２】Sho Hoshino, Yusuke Miyao, Katsuhito Sudoh, Katsuhiko Hayashi, and Masaaki Nagata. 2015. Discriminative Preordering Meets Kendall’s τ Maximization. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), pages 139-144.
【非特許文献３】Nan Yang, Mu Li, Dongdong Zhang, and Nenghai Yu. 2012. A Ranking-based Approach to Word Reordering for Statistical Machine Translation. In Proceedings of the 50th Annual Meeting of the Association for Computa- tional Linguistics (Volume 1: Long Papers), pages 912-920.
【非特許文献４】Laura Jehl, Adria‘ de Gispert, Mark Hopkins, and Bill Byrne. 2014. Source-side Preordering for Translation using Logistic Regression and Depth-first Branch-and-Bound Search. In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 239-248.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記非特許文献４に記載の技術は、上述したように、精度の面では優れているが、構文木の分岐数が多くなると計算量が指数的に増大する可能性があるため、分岐数が多い場合の並べ替え計算量を削減できることが望ましい。長文に対する依存構造のような分岐数が多い構文木に対しても、効率よく並べ替えを行えることが望ましい。
【００１１】
本発明は、以上のような事情に鑑みてなされたものであり、長文に対する依存構造のような分岐数が多い構文木に対しても、効率よく並べ替えを行うことができる並べ替え装置、並べ替え方法、及び並び替えプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明の並び替え装置は、入力した原言語文の構文解析を行って、前記原言語文を表す構文木を生成する構文解析部と、前記生成された構文木の兄弟ノードの二個組の各々について、兄弟ノードの二個組の現在の順序を維持すべきか反転すべきかを判定するための予め定められた二値分類並べ替えモデルに基づいて、判定スコアを計算する二値分類並べ替えスコア計算部と、前記生成された構文木の兄弟ノード群の各々について、前記二値分類並べ替えスコア計算部により計算された判定スコアに基づいて兄弟ノードの二個組の現在の順序を維持するか反転することにより、前記兄弟ノード群を並べ替え、前記兄弟ノード群の順序が決定不可能な場合、分枝限定法により前記兄弟ノード群の最適な順序を探索することにより前記兄弟ノード群を並べ替え、前記並べ替えられた前記構文木に基づいて、前記原言語文の単語を並べ替える最適順序決定部と、を含む。
【００１３】
なお、学習用の原言語文と学習用の目的言語文との間の単語の対応関係を表す単語対応データと、前記学習用の原言語文を表す構造木とに基づいて、前記構文木の兄弟ノード二個組の各々について現在の順序を維持すべきか反転すべきかを示す二値分類正解を決定する二値分類正解決定部と、前記二値分類正解、及び前記構文木の兄弟ノード二個組の各々について抽出される素性に基づいて、前記二値分類並べ替えモデルを学習する二値分類並べ替え学習部と、を更に備えるようにしても良い。
【００１４】
なお、前記最適順序決定部は、前記生成された構文木の兄弟ノード群の各々について、前記二値分類並べ替えスコア計算部により計算された判定スコアに基づいて、トポロジカルソートにより前記兄弟ノード群を並べ替えるようにしても良い。
【００１５】
上記目的を達成するために、本発明の並び替え方法は、構文解析部、二値分類並べ替えスコア計算部、及び最適順序決定部を備えた並べ替え装置が行う並べ替え方法であって、
前記構文解析部が、入力した原言語文の構文解析を行って、前記原言語文を表す構文木を生成するステップと、前記二値分類並べ替えスコア計算部が、前記生成された構文木の兄弟ノードの二個組の各々について、兄弟ノードの二個組の現在の順序を維持すべきか反転すべきかを判定するための予め定められた二値分類並べ替えモデルに基づいて、判定スコアを計算するステップと、前記最適順序決定部が、前記生成された構文木の兄弟ノード群の各々について、前記二値分類並べ替えスコア計算部により計算された判定スコアに基づいて兄弟ノードの二個組の現在の順序を維持するか反転することにより、前記兄弟ノード群を並べ替え、前記兄弟ノード群の順序が決定不可能な場合、分枝限定法により前記兄弟ノード群の最適な順序を探索することにより前記兄弟ノード群を並べ替え、前記並べ替えられた前記構文木に基づいて、前記原言語文の単語を並べ替えるステップと、を行う。
【００１６】
上記目的を達成するために、本発明の並び替えプログラムは、コンピュータを、上記並び替え装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１７】
本発明によれば、長文に対する依存構造のような分岐数が多い構文木に対しても、効率よく並べ替えを行うことが可能となる。
【図面の簡単な説明】
【００１８】
【図１】実施形態に係る翻訳システムの構成を示す機能ブロック図である。
【図２】実施形態に係る並び替え装置の構成を示す機能ブロック図である。
【図３】実施形態に係る翻訳装置の構成を示す機能ブロック図である。
【図４】実施形態に係る翻訳装置により実行される並び替えモデル作成処理の流れを示すフローチャートである。
【図５】実施形態に係る翻訳装置により実行される並べ替え処理の流れを示すフローチャートである。
【図６】実施形態に係る翻訳装置により実行される機械翻訳モデル作成処理の流れを示すフローチャートである。
【図７】実施形態に係る翻訳装置により実行される翻訳処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態について図面を用いて説明する。
【００２０】
＜構文解析＞
【００２１】
原言語の並べ替えのための構造として構文木を利用する。本実施形態では、特定の構文解析手法に依存しないが、依存構造木や多分句構造木など、多分木を出力する形態の構文解析器を利用することが好適である。
【００２２】
＜並べ替え用二値分類モデルの学習＞
【００２３】
上記非特許文献４と同様の方法により、並べ替え用二値分類モデルを学習する。多分構文木の各要素（ノード）に対し、兄弟ノードとの順序を維持するか反転するかを決定し、各ノード組の順序付けの正解とする。この順序の決定は、原言語の構文木中の単語と目的言語の単語との対応情報を利用して、単語対応が最も交差しない、すなわち、並べ替えた原言語の単語と対応する目的言語の単語の語順が最大限一致するように行うことが一般的である（上記非特許文献２、３、４参照）。
【００２４】
なお、この単語対応の情報は学習用の原言語と目的言語の単語列データから下記参考文献１に記載のような方法によって得ることもできるし、人手で対応を与えたデータを追加して与えてもよい。
【００２５】
［参考文献１］Philipp Koehn, Franz J. Och, and Daniel Marcu, 2003. Statistical Phrase-Based Translation. In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pages 48-54.
【００２６】
ここで、兄弟ノードの順序を維持しても反転しても単語対応の交差の度合いが変化しない場合は正解順序が決定できないため、そのようなノード組は学習データから取り除くものとする。
【００２７】
＜二値分類の実行＞
【００２８】
並べ替えを行いたい原言語の構文木に対して、構文木の各兄弟ノード二個組について上述した並べ替え用二値分類モデルを適用し、二値分類を実行する。後段の要素順決定のスコアとして利用するため、二値分類の結果は、非負かつ和が１となるような実数値スコアの組として保持する。
【００２９】
すなわち、ノードＡ及びノードＢ（ノードＡはノードＢより前にあるものとする）の順序を維持するという判断に対するスコアが“ｓ”であるとしたとき、ノードＡ及びノードＢの順序を反転するという判断に対するスコアは“１−ｓ”であるとする。
【００３０】
このようなスコアはロジスティック回帰による二値分類のような確率的な手法であればこの条件を満たすものがそのまま結果として得ることができるし、サポートベクタマシン（ＳＶＭ）のような非確率的な手法であれば、シグモイド関数を利用して０から１の範囲に正規化して“s” を得ることができるため、本実施形態では、特定の計算方法に依存しない。
【００３１】
＜最適順序決定＞
【００３２】
上記非特許文献４に記載されている方法では、全要素に対して分枝限定法を適用して最適な順序を決定している。すなわち、ある要素の並べ替え結果に対して計算できる上記ノード組の順序の維持/反転判断の合計スコア（確率的なスコアを前提とするならば確率の積）が最大となるように、全ての可能な要素の並べ替えを適宜探索の枝刈りを行いながら求めている。
【００３３】
本実施形態では、まず前端と後端の順序をトポロジカルソートで決定する。上記二値分類のスコアでノードＡとノードＢの順序が維持されるスコア（確率）が０．５より大きい場合は“Ａ＜Ｂ”、スコア（確率）が０．５より小さい場合、すなわちノードＡ及びノードＢの順序が反転されるスコア（確率）が０．５より大きい場合は、“Ｂ＜Ａ”、という関係があるものとする。
【００３４】
ここで、スコア（確率）が０．５となった場合は両者の順序決定ができないことになるが、上記二値分類の実行プロセスの結果でスコアが厳密に０．５となることは非常に稀であると考えられるため、そのような場合について本実施形態は特に考慮しない。
【００３５】
上述したような手続きで得られた各ノードの二個組間の順序関係（ノード数がｎ個であるときに｛｛ｎ（ｎ＋１）｝／２｝個の順序関係が定義される）から、前端および後端となる要素を順に決定していく。
【００３６】
前端となるノードとは、その他すべてのノードＸに対して“Ｆ＜Ｘ”という関係が成り立つノードＦであり、後端となるノードとは、その他すべてのノードＸに対して“Ｘ＜Ｔ”という関係が成り立つノードＴである。このような関係を満たすノードが見つかった場合は、そのノードを取り除いて同じ処理を繰り返し行う。この手続きによってすべてのノードの順序が決定された場合は、それが最適順序であり、三すくみのような関係が含まれることで“＜”の関係だけでは順序が定まらない場合は、上記非特許文献４の分枝決定法を用いて当該ノード群のみ実際のスコアを用いて最適な順序を探索する。
【００３７】
本実施形態の方法によって最適な順序が得られることは、ノードの順序の維持/反転のスコアが非負で和が１であって、その他すべてのノードＸに対して“Ｆ＜Ｘ”なるノードＦを前端でない箇所に並べ替えたとすると、必ずスコアが小さくなることから自明である。
【００３８】
＜翻訳の実行＞
【００３９】
このように、最適順序の決定を構文木の各兄弟ノード群に対して適用すると、文全体の並べ替えが定まるため、その並べ替えに従って並べ替えた原言語の単語列を利用して機械翻訳を行う。機械翻訳の方式は公知の統計的機械翻訳の方法が利用できる（たとえば上記参考文献１）。
【００４０】
その際、原言語の単語列の並べ替えは、翻訳実行時のみならず、統計的機械翻訳モデルの学習のための学習データの原言語文に対しても適用される。すなわち、本実施形態によって並べ替えられた原言語が「新しい原言語」であるという想定で統計的機械翻訳を行う。
【００４１】
＜翻訳システムの構成＞
【００４２】
図１に示すように、本実施形態に係る翻訳システム１０は、並び替え装置１２、及び、機械翻訳装置１４を含んで構成される。
【００４３】
また、図２に示すように、並び替え装置１２は、構文解析部２０、二値分類正解決定部２２、二値分類並べ替えモデル学習部２４、二値分類並べ替えモデル記憶部２６、二値分類並べ替えスコア計算部２８、及び、最適順序決定部３０を有している。
【００４４】
また、図３に示すように、機械翻訳装置１４は、機械翻訳モデル学習部４０、統計的機械翻訳モデル記憶部４２、及び、機械翻訳実行部４４を備えている。
【００４５】
なお、本実施形態では、並び替え装置１２には、原言語文記憶部１６、単語対応記憶部１８ａ、及び、目的言語文記憶部１８ｂが接続されていると共に、機械翻訳装置１４には、目的言語文記憶部１８ｂ、及び、対訳データ記憶部３２が接続されている。
【００４６】
原言語文記憶部１６は、翻訳前の言語で記された学習用の複数の原言語文を示す原言語文データを記憶している。
【００４７】
単語対応記憶部１８ａは、学習用の翻訳前の原言語文の単語と、学習用の翻訳後の目的言語文の単語との対応関係を表す単語対応データを記憶している。
【００４８】
目的言語文記憶部１８ｂは、翻訳後の言語で記された学習用の複数の目的言語文を示す目的言語文データを記憶している。
【００４９】
対訳データ記憶部３２は、原言語文と目的言語文とが組になった対訳データを記憶している。
【００５０】
構文解析部２０は、学習用の原言語文データと、原言語の構文解析モデルとを読み込み、読み込んだ原言語文の構文解析を行って、原言語文を表す構文木を生成する。
【００５１】
また、構文解析部２０は、並び替え対象となる原言語文データと、原言語の構文解析モデルとを読み込み、並び替え対象となる原言語文の構文解析を行って、原言語文を表す構文木を生成する。
【００５２】
なお、言語によっては、原言語の構文解析を行う前段の処理として単語分割を要する場合があり、その場合には、構文解析部２０は、原言語の構文解析を行う前に、あるいは原言語の構文解析と同時に、単語分割を行うものとする。
【００５３】
二値分類正解決定部２２は、単語対応記憶部１８ａに記憶された、学習用の原言語文と学習用の目的言語文との間の単語の対応関係を表す単語対応データと、構文解析部２０によって生成された、学習用の原言語文を表す構造木とに基づいて、前記構文木の兄弟ノード二個組の各々について現在の順序を維持すべきか反転すべきかを示す二値分類正解を決定する。
【００５４】
具体的には、まず、二値分類正解決定部２２は、原言語文を表す構文木データを読み込む。
【００５５】
また、二値分類正解決定部２２は、原言語と目的言語の単語対応データを読み込む。データの形態は特に規定しないが、原言語のｎ番目の単語と目的言語のｍ番目の単語が対応する、というような情報を表現したデータ形式であることが望ましい。
【００５６】
また、二値分類正解決定部２２は、単語対応記憶部１８ａから単語対応データを取得できず、学習用の原言語文データと学習用の目的言語文データを用いて単語の対応関係を推定する必要がある。この場合には、単語対応の推定方法については特に規定しないが、上記参考文献１に記載されている方法が代表的である。ただし、本実施形態では、構成上は単語対応データで目的言語の何番目の単語に対応するかが分かれば十分であるため、単語対応データを取得できず、目的言語データを用いて単語の対応関係を推定する必要がある場合を除き、単語の対応関係の推定処理を省略可能である。
【００５７】
さらに、二値分類正解決定部２２は、原言語の構文木の各兄弟ノード群に対して、単語対応データに基づいて、兄弟ノードの各二個組がその順序を維持すべきか、反転すべきかを決定し、二値分類正解とする。決定方法には上記非特許文献２に記載されているケンドールの順位相関係数が好適であるが、目的言語の語順との一致度合いを測ることができるような尺度であればこれに限るものではない。
【００５８】
二値分類並べ替えモデル学習部２４は、二値分類正解、及び学習用の原言語文を表す構文木の兄弟ノード二個組の各々について抽出される素性に基づいて、兄弟ノードの二個組の現在の順序を維持すべきか反転すべきかを判定するための二値分類並べ替えモデルを学習する。
【００５９】
まず、二値分類並べ替えモデル学習部２４は、学習用の原言語文を表す構文木から、各兄弟ノード二個組について素性を抽出する。本実施形態では、特定の素性の構成によるものではないが、上記非特許文献２、上記非特許文献４に記載されているノード組に対する素性が好適である。
【００６０】
また、二値分類並べ替えモデル学習部２４は、二値分類の正解（維持／反転のラベル）と抽出した素性に基づいて二値分類並べ替えモデルを学習する。本実施形態では、維持／反転の確率的な（非負かつ和が１）スコアであることが前提となるため、上述した通り、ロジスティック回帰による二値分類モデルが好適であるが、後述する二値分類スコア（判定スコア）を計算する段階において判定スコアの正規化を行うことにより、ＳＶＭ等も利用可能である。こうしたモデルの学習を行う公知のソフトウェアとしては、ＬＩＢＳＶＭ、ＬＩＢＬＩＮＥＡＲ等が挙げられる。
【００６１】
二値分類並べ替えモデル記憶部２６は、二値分類並べ替えモデル学習部２４により学習された二値分類並べ替えモデルを記憶する。
【００６２】
二値分類並べ替えスコア計算部２８は、並び替え対象の原言語文を表す構文木の兄弟ノードの二個組の各々について、二値分類並べ替えモデル記憶部２６に記憶された二値分類並べ替えモデルに基づいて、順序の維持／反転のスコアである判定スコアを計算する。
【００６３】
まず、二値分類並べ替えスコア計算部２８は、二値分類並べ替えモデル学習部２４が各兄弟ノード二個組について素性を抽出する場合と同様の方法で、並び替え対象の原言語文を表す構文木の各兄弟ノード二個組について素性を抽出する。
【００６４】
また、二値分類並べ替えスコア計算部２８は、素性が抽出された、並び替え対象の原言語文を表す構文木の各兄弟ノード二個組に対して、抽出される素性と二値分類並べ替えモデルとに基づいて、ノード順序の維持／反転のスコアである判定スコアを計算する。上述した通り、判定スコアの正規化が必要な場合はここで判定スコアを非負かつ和が１になるように調整する。
【００６５】
最適順序決定部３０は、並び替え対象の原言語文を表す構文木の兄弟ノード群の各々について、二値分類並べ替えスコア計算部２８により計算された判定スコアに基づいて兄弟ノードの二個組の現在の順序を維持するか反転することにより、兄弟ノード群を並べ替え、兄弟ノード群の順序が決定不可能な場合、分枝限定法により前記兄弟ノード群の最適な順序を探索することにより兄弟ノード群を並べ替え、並べ替えられた前記構文木に基づいて、前記原言語文の単語を並べ替える。
【００６６】
具体的には、まず、最適順序決定部３０は、各兄弟ノード群に対して、兄弟ノードの二個組の各々について、上述した判定スコアを読み込むと同時に、前述の判定スコア０．５を境界とした順序関係を定義する（兄弟ノード群のノード数がｎ個であるときに｛｛ｎ（ｎ＋１）｝／２｝個の順序関係が定義される）。
【００６７】
また、最適順序決定部３０は、各兄弟ノード群に対し、上述した順序関係を用いて、例えば兄弟ノードのトポロジカルソートを行い、前端、及び後端に並べ替えられるノードの順次を決定する。この際、前端部と後端部を別々のステップとして実行してもよいし、同時に行ってもよい。本実施形態では、最適順序決定部３０は、少なくとも一部のノードの順序がトポロジカルソートにより確定できなかった兄弟ノード群について、判定スコアに基づいて、分枝限定法を用いた分枝限定探索を行う。
【００６８】
最適順序決定部３０が分枝限定探索を行う際には、トポロジカルソートを行っても順序が決定できなかった兄弟ノード群に対して、上記非特許文献４に記載されている分枝限定法によって最適な順序を探索する。分枝限定法では、各兄弟ノード群を複数の集合に分割する分枝操作と、判定スコアが最適となる兄弟ノードの順序を決定する限定操作とを再帰的に繰り返すことにより、兄弟ノード群の順序関係を決定する。
【００６９】
また、最適順序決定部３０は、決定された最適な並べ替えに基づき、並び替え対象の原言語文を表す構文木を並べ替え、原言語文の単語並べ替え結果を出力する。
【００７０】
機械翻訳モデル学習部４０は、並べ替え装置１２により並べ替えられた学習用の原言語文と、学習用の目的言語文との組から、統計的機械翻訳モデルを学習する。
【００７１】
まず、機械翻訳モデル学習部４０は、並べ替え装置１２により並べ替えられた学習用の原言語文と、学習用の目的言語文とが組になった対訳データを読み込む。また、機械翻訳モデル学習部４０は、必要であれば目的言語の単語列データも追加で読み込む。
【００７２】
次に、機械翻訳モデル学習部４０は、統計的機械翻訳モデルを学習する。上記参考文献１に記載されている方法を用いた場合には、句翻訳モデル、句並べ替えモデル、及び言語モデルを学習する。他にもニューラル機械翻訳と呼ばれる、下記参考文献２に記載されている方法もある。本実施形態では、統計的機械翻訳の方法については特に規定せず、原言語の単語列が目的言語の語順に近づくように並べ替えられていることのみを規定する。
【００７３】
［参考文献２］Thang Luong, Hieu Pham, and Christopher D. Manning. 2015. Effective approaches to attention-based neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1412-1421.
【００７４】
そして、機械翻訳モデル学習部４０は、学習された統計的機械翻訳モデルを統計的機械翻訳モデル記憶部４２へ出力する。
【００７５】
統計的機械翻訳モデル記憶部４２は、機械翻訳モデル学習部４０により学習された統計的機械翻訳モデルが記憶される。
【００７６】
機械翻訳実行部４４は、並べ替え装置１２により並べ替えられた翻訳対象の原言語文について、統計的機械翻訳モデル記憶部４２に記憶された、学習された統計的機械翻訳のモデルを利用して機械翻訳を実行し、目的言語文に翻訳する。
【００７７】
具体的には、まず、機械翻訳実行部４４は、並べ替え装置１２により並べ替えられた翻訳対象の原言語文を読み込むと共に、二値分類並べ替えモデル記憶部２６に記憶された二値分類並び替えモデルを読み込む。
【００７８】
また、機械翻訳実行部４４は、統計的機械翻訳モデルを利用し、原言語文の翻訳結果候補の探索を行い、翻訳結果を出力する。
【００７９】
このように、本実施形態によれば、長文に対する依存構造のような非常に分岐数が多い構文木に対しても、効率よく並べ替えを行うことができるようになる。上記非特許文献４に記載されている方法では、分枝限定法によって探索するノード数を１２までとしていたが、本実施形態においては、トポロジカルソートによって順序決定ができなかったノードのみを分枝限定法によって探索するため、分枝限定法によって探索するノード数を１２までとしても、より分岐数の多い構文木の並べ替えを実現することができるとともに、分枝限定法による探索ノード数が抑えられることで最適な順序の探索が非常に効率的になる。
【００８０】
なお、本実施形態に係る並び替え装置１２及び機械翻訳装置１４は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、各種プログラムを記憶するＲＯＭ（Read Only Memory）を備えたコンピュータ装置で構成される。また、並び替え装置１２及び機械翻訳装置１４を構成するコンピュータは、ハードディスクドライブ、不揮発性メモリ等の記憶部を備えていても良い。本実施形態では、ＣＰＵがＲＯＭ、ハードディスク等の記憶部に記憶されているプログラムを読み出して実行することにより、上記のハードウェア資源とプログラムとが協働し、上述した機能が実現される。
【００８１】
＜翻訳システムの作用＞
【００８２】
本実施形態に係る並び替え装置１２による並べ替えモデル作成処理の流れを、図４に示すフローチャートを用いて説明する。本実施形態では、並べ替え装置１２に、並べ替えモデル作成処理の実行を開始するための予め定めた情報が入力されたタイミングで並べ替えモデル作成処理が開始されるが、並べ替えモデル作成処理が開始されるタイミングはこれに限らず、例えば、少なくとも１文以上の原言語文が入力されたタイミングで並べ替えモデル作成処理が開始されても良い。
【００８３】
ステップＳ１０１では、構文解析部２０は、原言語文記憶部１６から、二値分類並べ替えモデルを学習するために用意された原言語文データを読み込むことにより、原言語文データを取得する。
【００８４】
ステップＳ１０３では、構文解析部２０は、原言語の構文解析モデルを取得する。
【００８５】
ステップＳ１０５では、構文解析部２０は、取得した構文解析モデルに基づき、取得した原言語文データについて原言語文の構文解析を行い、原言語文を表す構造木を作成する。
【００８６】
ステップＳ１０７では、二値分類正解決定部２２は、作成された原言語文を表す構文木のデータを取得する。
【００８７】
ステップＳ１０９では、二値分類正解決定部２２は、単語対応記憶部１８ａに記憶されている単語対応データを読み出すことにより、単語対応データを取得する。
【００８８】
なお、ステップＳ１０９で単語対応記憶部１８ａに記憶されている単語対応データの代わりに、目的言語文記憶部１８ｂに記憶されている目的言語文データを取得する場合には、原言語文と目的言語文との単語対応を、例えば上記参考文献１に記載の方法で推定する。
【００８９】
ステップＳ１１１では、二値分類正解決定部２２は、二原言語の構文木の各兄弟ノード集合に対して、兄弟ノードの各二個組がその順序を維持すべきか反転すべきかを示す二値分類正解を決定する。
【００９０】
ステップＳ１１３では、二値分類並べ替えモデル学習部２４は、原言語文を表す構文木から各兄弟ノード二個組について素性を抽出する。
【００９１】
ステップＳ１１５では、二値分類並べ替えモデル学習部２４は、各兄弟ノード二個組についての素性に基づき、二値分類並べ替えモデルを学習する。
【００９２】
ステップＳ１１７では、二値分類並べ替えモデル学習部２４は、学習した二値分類並べ替えモデルを二値分類並べ替えモデル記憶部２６に記憶させ、本並び替えモデル作成処理のプログラムの実行を終了する。
【００９３】
次に、本実施形態に係る並べ替え装置１２による並べ替え処理の流れを、図５に示すフローチャートを用いて説明する。本実施形態では、並べ替え装置１２に、並べ替え処理の実行を開始するための予め定めた情報が入力されたタイミングで並べ替え処理が開始されるが、並べ替え処理が開始されるタイミングはこれに限らず、例えば、少なくとも１文以上の原言語文が入力されたタイミングで並べ替え処理が開始されても良い。
【００９４】
ステップＳ１１９では、構文解析部２０が、並べ替えの対象とする原言語文データを取得する。
【００９５】
ステップＳ１２１では、二値分類並べ替えスコア計算部２８は、ステップＳ１１３と同様の手法で、原言語文を表す構文木から各兄弟ノード二個組について素性を取得する。
【００９６】
ステップＳ１２３では、二値分類並べ替えスコア計算部２８は、各兄弟ノード二個組の二値分類正解と、各兄弟ノード二個組についての素性に基づき、上述した判定スコアを計算する。
【００９７】
ステップＳ１２５では、最適順序決定部３０は、各兄弟ノード集合に対して、判定スコアを取得すると共に、取得した判定スコアに基づき予め定めた値（例えば、０．５）を境界とした順序関係を定義する。
【００９８】
ステップＳ１２７では、最適順序決定部３０は、定義した順序関係に基づき、兄弟ノードの順序関係を用いて、兄弟ノードのトポロジカルソートを行い、前端及び後端に並べ替えられる兄弟ノードの順序を決定する。
【００９９】
ステップＳ１２９では、最適順序決定部３０は、トポロジカルソートにより順序が決定できなかった兄弟ノード群（例えば、上述した三すくみの関係にある兄弟ノード群）に対して、分枝限定法を実行して、兄弟ノードの順序を決定する。
【０１００】
ステップＳ１３１では、最適順序決定部３０は、決定された兄弟ノードの順序を出力して、本並べ替え処理のプログラムの実行を終了する。
【０１０１】
次に本実施形態に係る機械翻訳装置１４による機械翻訳モデル作成処理の流れを、図６に示すフローチャートを用いて説明する。本実施形態では、機械翻訳装置１４に、機械翻訳モデル作成処理の実行を開始するための予め定めた情報が入力されたタイミングで機械翻訳モデル作成処理が開始されるが、機械翻訳モデル作成処理が開始されるタイミングはこれに限らず、例えば、少なくとも１文以上の原言語文が入力されたタイミングで機械翻訳モデル作成処理が開始されても良い。
【０１０２】
ステップＳ２０１では、機械翻訳モデル学習部４０は、並べ替え装置１２により各単語が並べ替えられた原言語文データであって、統計的機械翻訳モデルを学習するために用意された原言語文データを取得する。
【０１０３】
ステップＳ２０３では、機械翻訳モデル学習部４０は、取得した、各単語が並べ替えられた原言語文データに基づき、統計的機械翻訳モデルを学習する。
【０１０４】
ステップＳ２０５では、機械翻訳モデル学習部４０は、学習した統計的機械翻訳モデルを出力し、本機械翻訳モデル作成処理のプログラムの実行を終了する。なお、本実施形態では、学習した統計的機械翻訳モデルを統計的機械翻訳モデル記憶部４２に出力することにより、統計的機械翻訳モデル記憶部４２に記憶させる。
【０１０５】
次に本実施形態に係る機械翻訳装置１４による翻訳処理の流れを、図７に示すフローチャートを用いて説明する。本実施形態では、機械翻訳装置１４に、翻訳処理の実行を開始するための予め定めた情報が入力されたタイミングで翻訳処理が開始されるが、翻訳処理が開始されるタイミングはこれに限らず、例えば、少なくとも１文以上の原言語文が入力されたタイミングで翻訳処理が開始されても良い。
【０１０６】
ステップＳ３０１では、機械翻訳実行部４４は、並べ替え装置１２により各単語が並べ替えられた原言語文データであって、翻訳の対象とする原言語文データを取得する。
【０１０７】
ステップＳ３０３では、機械翻訳実行部４４は、統計的機械翻訳モデル記憶部４２に記憶されている統計的機械翻訳モデルを読み出すことにより、統計的機械翻訳モデルを取得する。
【０１０８】
ステップＳ３０５では、機械翻訳実行部４４は、統計的機械翻訳モデルを用いて、並べ替え装置１２により各単語が並べ替えられた原言語文データの翻訳結果の候補を探索する。
【０１０９】
ステップＳ３０７では、機械翻訳実行部４４は、翻訳結果の候補を出力し、本翻訳処理のプログラムの実行を終了する。なお、本実施形態では、翻訳結果の候補をディスプレイ等の表示手段に表示させたり、スピーカ等の音声出力手段に音声出力させたりすることにより、翻訳結果の候補を出力する。
【０１１０】
このようにして、並べ替え装置１２は、入力した原言語文の構文解析を行って、原言語文を表す構文木を生成し、生成された構文木の兄弟ノードの二個組の各々について、兄弟ノードの二個組の現在の順序を維持すべきか反転すべきかを判定するための予め定められた二値分類並べ替えモデルに基づいて兄弟ノードの二個組の現在の順序を維持するか反転することにより、兄弟ノードの二個組の順序を決定する。また、生成された構文木の兄弟ノード群の各々について、二個組順序決定部による決定結果に基づいて、兄弟ノード群を並べ替え、兄弟ノード群の順序が決定不可能な場合、分枝限定法により兄弟ノード群の最適な順序を探索することにより兄弟ノード群を並べ替え、並べ替えられた構文木に基づいて、原言語文の単語を並べ替える。
【０１１１】
なお、本実施形態では、図１乃至図３に示す機能の構成要素の動作をプログラムとして構築し、翻訳システム１０として利用されるコンピュータにインストールして実行させるが、これに限らず、ネットワークを介して流通させても良い。
【０１１２】
また、構築されたプログラムをハードディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールしたり、配布したりしても良い。
【符号の説明】
【０１１３】
１０  翻訳システム
１２  並べ替え装置
１４  機械翻訳装置
２０  構文解析部
２２  二値分類正解決定部
２４  二値分類並べ替えモデル学習部
２６  二値分類並べ替えモデル記憶部
２８  二値分類並べ替えスコア計算部
３０  最適順序決定部
４０  機械翻訳モデル学習部
４２  統計的機械翻訳モデル記憶部
４４  機械翻訳実行部
【図１】
2018081460.tif 000003
【図２】
2018081460.tif 000004
【図３】
2018081460.tif 000005
【図４】
2018081460.tif 000006
【図５】
2018081460.tif 000007
【図６】
2018081460.tif 000008
【図７】
2018081460.tif 000009