(57)【特許請求の範囲】
【請求項１】
シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフを入力として、前記有向非循環グラフの各エッジの向きに基づいて、前記有向非循環グラフの各ノードを順序付ける整列部と、
前記整列部による各ノードの順序付けと、前記有向非循環グラフの各エッジとに沿って、各ノードに対応する、前記ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、前記エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器であって、かつ、前記ノード用の符号化ユニットは、前段の少なくとも一つの前記エッジ用の符号化ユニットの出力と前記ノードのラベルとを入力とし、前記エッジ用の符号化ユニットは、前段の前記ノード用の符号化ユニットの出力と前記エッジのラベルとを入力とする前記符号器を構築する符号器構築部と、
前記整列部による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、前記符号器構築部によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、前記有向非循環グラフの符号を出力する符号器計算部と、
を含む符号化装置。
【請求項２】
請求項１記載の符号化装置から出力された前記有向非循環グラフの符号を、前記シンボルに復号する復号化ユニットの系列である系列復号器であって、かつ、前記復号化ユニットは、前段の前記復号化ユニットの出力を入力とする前記系列復号器に入力して、順次計算して、前記シンボルの離散系列を出力する復号器計算部
を含む復号化装置。
【請求項３】
シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフを入力として、前記有向非循環グラフの各エッジの向きに基づいて、前記有向非循環グラフの各ノードを順序付ける整列部と、
前記整列部による各ノードの順序付けと、前記有向非循環グラフの各エッジとに沿って、各ノードに対応する、前記ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、前記エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器であって、かつ、前記ノード用の符号化ユニットは、前段の少なくとも一つの前記エッジ用の符号化ユニットの出力と前記ノードのラベルとを入力とし、前記エッジ用の符号化ユニットは、前段の前記ノード用の符号化ユニットの出力と前記エッジのラベルとを入力とする前記符号器を構築する符号器構築部と、
前記整列部による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、前記符号器構築部によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、前記有向非循環グラフの符号を出力する符号器計算部と、
前記符号器計算部から出力された前記有向非循環グラフの符号を、前記シンボルに復号する復号化ユニットの系列である系列復号器であって、かつ、前記復号化ユニットは、前段の前記復号化ユニットの出力を入力とする前記系列復号器に入力して、順次計算して、前記シンボルの離散系列を出力する復号器計算部と、
を含む離散系列変換装置。
【請求項４】
整列部が、シンボルの離散系列を、前記シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフを入力として、前記有向非循環グラフの各エッジの向きに基づいて、前記有向非循環グラフの各ノードを順序付けるステップと、
符号器構築部が、前記整列部による各ノードの順序付けと、前記有向非循環グラフの各エッジとに沿って、各ノードに対応する、前記ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、前記エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器であって、かつ、前記ノード用の符号化ユニットは、前段の少なくとも一つの前記エッジ用の符号化ユニットの出力と前記ノードのラベルとを入力とし、前記エッジ用の符号化ユニットは、前段の前記ノード用の符号化ユニットの出力と前記エッジのラベルとを入力とする前記符号器を構築するステップと、
符号器計算部が、前記整列部による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、前記符号器構築部によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、前記有向非循環グラフの符号を出力するステップと、
を含む符号化方法。
【請求項５】
復号器計算部が、請求項４記載の符号化方法において出力された前記有向非循環グラフの符号を、前記シンボルに復号する復号化ユニットの系列である系列復号器であって、かつ、前記復号化ユニットは、前段の前記復号化ユニットの出力を入力とする前記系列復号器に入力して、順次計算して、前記シンボルの離散系列を出力するステップ
を含む復号化方法。
【請求項６】
整列部が、シンボルの離散系列を、前記シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフを入力として、前記有向非循環グラフの各エッジの向きに基づいて、前記有向非循環グラフの各ノードを順序付けるステップと、
符号器構築部が、前記整列部による各ノードの順序付けと、前記有向非循環グラフの各エッジとに沿って、各ノードに対応する、前記ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、前記エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器であって、かつ、前記ノード用の符号化ユニットは、前段の少なくとも一つの前記エッジ用の符号化ユニットの出力と前記ノードのラベルとを入力とし、前記エッジ用の符号化ユニットは、前段の前記ノード用の符号化ユニットの出力と前記エッジのラベルとを入力とする前記符号器を構築するステップと、
符号器計算部が、前記整列部による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、前記符号器構築部によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、前記有向非循環グラフの符号を出力するステップと、
復号器計算部が、前記符号器計算部から出力された前記有向非循環グラフの符号を、前記シンボルに復号する復号化ユニットの系列である系列復号器であって、かつ、前記復号化ユニットは、前段の前記復号化ユニットの出力を入力とする前記系列復号器に入力して、順次計算して、前記シンボルの離散系列を出力するステップと、
を含む離散系列変換方法。
【請求項７】
コンピュータを、請求項１に記載の符号化装置の各部として機能させるためのプログラム。
【請求項８】
コンピュータを、請求項２に記載の復号化装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化装置、復号化装置、離散系列変換装置、方法、及びプログラムに係り、特に、入力されたシンボルの離散系列に対して符号化又は復号化を行うための符号化装置、復号化装置、離散系列変換装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
自然言語処理分野の問題を題材として背景技術を説明する。計算機により自然言語を処理する技術は、文章に現れる表層的な文字や単語といった離散シンボルの集合を処理する技術と言える。例えば、ある言語の文を入力し、別の言語の文を出力する自動翻訳システムを考える。このシステムでは、入力および出力の文を単語列（文字列）とみなして処理が行われる。よって、システム内の計算機により、離散系列（シンボル列）から別の離散系列へ変換する処理を行っているとみなすことができる。また、文書要約システム、対話システム、文書構成システムなどの言語を入出力とするシステムは、前述の翻訳システム同様、離散系列から別の離散系列へ変換する処理によってシステムが構成されると言える。このように、前述の自然言語処理システム以外の自然言語処理システムでも、自然言語を扱うシステムでは、扱う対象が単語、文、文書といった離散系列であるため、入力から出力へどのような変換を行うかという定義の違いはあるにせよ、処理のフレームワークは同じであり、離散系列から離散系列の変換問題に帰着できる。図１に自然言語処理における変換問題の各種の例を示す。
【０００３】
前述したように、離散系列-離散系列変換問題は、自然言語処理分野において数多くの方法が開発され、様々な方法論が確立されている。古典的には、人間が系列から系列への変換ルールや規則などを記述して変換方法を構築してきた。近年では、正解データを利用したり、最適化法を用いるなど、機械学習技術を活用する方法が主流となっている。最近では、機械学習法の中でもリカレントニューラルネットの枠組みを使い、離散系列を実数値ベクトルへ符号化し、その実数値ベクトルから離散系列を復号するという方法論で離散系列-離散系列変換問題を解く方法が提案されている（非特許文献１）。この方法は、人手による事前知識を全く使わず、可変長の系列構造から系列構造への変換を固定長の実数値ベクトルへの符号化と復号化のみで実現していることが大きな特徴である。図７に符号器による符号化と、復号器による復号化の例を示す。
【０００４】
この「リカレントニューラルネットに基づく離散系列から離散系列への変換器」を、ここでは単純に「離散系列−離散系列変換器」と呼ぶことにする。また、離散系列-離散系列変換器は、離散系列符号器と離散系列復号器の二つの組み合わせにて構築されている。また、符号／復号器のパラメタである固定長の実数値ベクトルは、学習用データから自動的に獲得する。パラメタ学習は、それぞれの変換器の理想的な入力と出力のペアの集合を学習用データとして準備し、その学習用データの入力が正しく出力できるようにパラメタ調整を行うことで学習が進む。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ilya Sutskever, Oriol Vinyals, and Quoc V Le, Sequence to Sequence Learning with Neural Networks. Advances in Neural Information Processing Systems 27, 2014.
【非特許文献２】Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, UlfHermjakob, Kevin Knight,Philipp Koehn, Martha Palmer, and Nathan Schneider, Abstract Meaning Representation for Sembanking.Proceedings of the 7th Linguistic Annotation Workshop and Interoperability with Discourse, 2013.
【非特許文献３】Kai Sheng Tai, Richard Socher and Christopher D. Manning. Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing,2015.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
自然言語処理では、文章を文法や意味的に解析する技術が盛んに研究開発されてきた。こういった、文章の文法や意味的な情報は、主に木構造や有向非循環グラフなどの離散グラフ構造によって記述する場合が多い。図２に系列構造、木構造、及びグラフ構造の一例を示す。
【０００７】
一方、前述したように、離散系列-離散系列変換器は、入力を文字列または単語列であることを想定している。よって、離散グラフ構造によって記述された文章の文法、または、意味的な情報を前述の離散系列-離散系列変換器により扱うことはできない。文法や意味的な情報は、自然言語処理システムにおいて非常に有益な情報源となりえる。つまり、前記、離散系列-離散系列変換器では、こういった有益な情報を扱うのは困難で、単語といった表層の情報しかうまく扱えないという課題がある。
【０００８】
本発明は、上記問題点を解決するために成されたものであり、シンボルの離散系列を表す有向非循環グラフを考慮した符号化を行うことができる符号化装置、離散系列変換装置、方法、及びプログラムを提供することを目的とする。
【０００９】
また、シンボルの離散系列を表す有向非循環グラフを考慮して符号化された符号を復号することができる復号化装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、入力されたシンボルの離散系列を、前記シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフに変換する変換部と、前記変換部により変換された前記有向非循環グラフの各エッジの向きに基づいて、前記有向非循環グラフの各ノードを順序付ける整列部と、前記整列部による各ノードの順序付けと、前記有向非循環グラフの各エッジとに沿って、各ノードに対応する、前記ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、前記エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器であって、かつ、前記ノード用の符号化ユニットは、前段の少なくとも一つの前記エッジ用の符号化ユニットの出力と前記ノードのラベルとを入力とし、前記エッジ用の符号化ユニットは、前段の前記ノード用の符号化ユニットの出力と前記エッジのラベルとを入力とする前記符号器を構築する符号器構築部と、前記整列部による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、前記符号器構築部によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、前記有向非循環グラフの符号を出力する符号器計算部と、を含んで構成されている。
【００１１】
また、第２の発明に係る復号化装置は、第１の発明に係る符号化装置から出力された前記有向非循環グラフの符号を、前記シンボルに復号する復号化ユニットの系列である系列復号器であって、かつ、前記復号化ユニットは、前段の前記復号化ユニットの出力を入力とする前記系列復号器に入力して、順次計算して、前記シンボルの離散系列を出力する復号器計算部を含んで構成されている。
【００１２】
また、第３の発明に係る離散系列変換装置は、入力されたシンボルの離散系列を、前記シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフに変換する変換部と、前記変換部により変換された前記有向非循環グラフの各エッジの向きに基づいて、前記有向非循環グラフの各ノードを順序付ける整列部と、前記整列部による各ノードの順序付けと、前記有向非循環グラフの各エッジとに沿って、各ノードに対応する、前記ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、前記エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器であって、かつ、前記ノード用の符号化ユニットは、前段の少なくとも一つの前記エッジ用の符号化ユニットの出力と前記ノードのラベルとを入力とし、前記エッジ用の符号化ユニットは、前段の前記ノード用の符号化ユニットの出力と前記エッジのラベルとを入力とする前記符号器を構築する符号器構築部と、前記整列部による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、前記符号器構築部によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、前記有向非循環グラフの符号を出力する符号器計算部と、前記符号器計算部から出力された前記有向非循環グラフの符号を、前記シンボルに復号する復号化ユニットの系列である系列復号器であって、かつ、前記復号化ユニットは、前段の前記復号化ユニットの出力を入力とする前記系列復号器に入力して、順次計算して、前記シンボルの離散系列を出力する復号器計算部と、を含んで構成されている。
【００１３】
第４の発明に係る符号化方法は、変換部が、入力されたシンボルの離散系列を、前記シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフに変換するステップと、整列部が、前記変換部により変換された前記有向非循環グラフの各エッジの向きに基づいて、前記有向非循環グラフの各ノードを順序付けるステップと、符号器構築部が、前記整列部による各ノードの順序付けと、前記有向非循環グラフの各エッジとに沿って、各ノードに対応する、前記ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、前記エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器であって、かつ、前記ノード用の符号化ユニットは、前段の少なくとも一つの前記エッジ用の符号化ユニットの出力と前記ノードのラベルとを入力とし、前記エッジ用の符号化ユニットは、前段の前記ノード用の符号化ユニットの出力と前記エッジのラベルとを入力とする前記符号器を構築するステップと、符号器計算部が、前記整列部による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、前記符号器構築部によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、前記有向非循環グラフの符号を出力するステップと、を含んで実行することを特徴とする。
【００１４】
また、第５の発明に係る復号化方法は、復号器計算部が、第４の発明に係る符号化方法において出力された前記有向非循環グラフの符号を、前記シンボルに復号する復号化ユニットの系列である系列復号器であって、かつ、前記復号化ユニットは、前段の前記復号化ユニットの出力を入力とする前記系列復号器に入力して、順次計算して、前記シンボルの離散系列を出力するステップを含んで実行することを特徴とする。
【００１５】
また、第６の発明に係る離散系列変換方法は、変換部が、入力されたシンボルの離散系列を、前記シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフに変換するステップと、整列部が、前記変換部により変換された前記有向非循環グラフの各エッジの向きに基づいて、前記有向非循環グラフの各ノードを順序付けるステップと、符号器構築部が、前記整列部による各ノードの順序付けと、前記有向非循環グラフの各エッジとに沿って、各ノードに対応する、前記ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、前記エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器であって、かつ、前記ノード用の符号化ユニットは、前段の少なくとも一つの前記エッジ用の符号化ユニットの出力と前記ノードのラベルとを入力とし、前記エッジ用の符号化ユニットは、前段の前記ノード用の符号化ユニットの出力と前記エッジのラベルとを入力とする前記符号器を構築するステップと、符号器計算部が、前記整列部による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、前記符号器構築部によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、前記有向非循環グラフの符号を出力するステップと、復号器計算部が、前記符号器計算部から出力された前記有向非循環グラフの符号を、前記シンボルに復号する復号化ユニットの系列である系列復号器であって、かつ、前記復号化ユニットは、前段の前記復号化ユニットの出力を入力とする前記系列復号器に入力して、順次計算して、前記シンボルの離散系列を出力するステップと、を含んで実行することを特徴とする。
【００１６】
また、第７の発明に係るプログラムは、コンピュータを、第１の発明に係る符号化装置、第２の発明に係る復号化装置、又は第３の発明に係る離散系列変換装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１７】
本発明の符号化装置、離散系列変換装置、方法、及びプログラムによれば、シンボルの離散系列を有向非循環グラフに変換し、有向非循環グラフの各エッジの向きに基づいて、有向非循環グラフの各ノードを順序付け、各ノードの順序付けと、有向非循環グラフの各エッジとに沿って、ノード用の符号化ユニットと、エッジ用の符号化ユニットとを接続した符号器を構築し、各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、構築された符号器の、対応する符号化ユニットに入力して順次計算して、有向非循環グラフの符号を出力することにより、シンボルの離散系列を表す有向非循環グラフを考慮した符号化を行うことができる、という効果が得られる。
【００１８】
また、復号化装置、方法、及びプログラムによれば、シンボルの離散系列を表す有向非循環グラフを考慮して符号化された符号を復号することができる、という効果が得られる。
【図面の簡単な説明】
【００１９】
【図１】自然言語処理における変換問題の各種の例を示す図である。
【図２】系列構造、木構造、及びグラフ構造の一例を示す図である。
【図３】有向非循環グラフの一例を示す図である。
【図４】本発明の実施の形態に係る離散系列変換装置の構成を示すブロック図である。
【図５】ノード・エッジラベル付き有向非循環グラフとその符号器の関係の例を示す図である。
【図６】本発明の実施の形態に係る離散系列変換装置における離散系列変換処理ルーチンを示すフローチャートである。
【図７】従来技術における符号器による符号化と、復号器による復号化の例を示す図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２１】
＜本発明の実施の形態に係る概要＞
【００２２】
まず、本発明の実施の形態における概要を説明する。
【００２３】
前述の通り有益な文法・意味的な情報は有向非循環グラフなどの離散グラフ構造によって記述される場合が多いことから、有向非循環グラフの符号器があれば、これらの情報を効率的に扱うことができるということになる。本発明の実施の形態における符号器は、特に、エッジとノードの両方にラベルが付与されている、ノード・エッジラベル付き有向非循環グラフに対する符号器として構築する。
【００２４】
有向非循環グラフは一般に木構造や系列構造を含むグラフのクラスである。つまり、本発明を用いれば、入力が木構造や系列構造であっても扱うことができる。逆に、従来の系列構造-系列構造変換器の場合は、通常エッジにラベルがついている状況を仮定していない。仮に系列構造であったとしても、エッジにラベルを付与して扱いたい場合は、本発明を用いることで利用可能となる。また、本発明はノードとエッジの両方にラベルが付与されていることを想定して記載されているが、ノードまたはエッジにラベルが存在しなくても、単一のラベルが全てのノードまたはエッジに付与されているとみなせば、本発明の枠組みで問題なく扱うことができる。このように、本発明を用いることで、様々な離散グラフ構造を扱うことできる。
【００２５】
＜処理概要＞
【００２６】
次に本発明の実施の形態に係る処理の概要について説明する。
【００２７】
文の意味表現として、abstract meaning representations (ＡＭＲ)と呼ばれる表現方法がある(非特許文献２)。この意味表現では、文の主要な単語に対して意味的な関係を有向非循環グラフ(ＤＡＧ)により記述する。また、単語に対して様々な属性を付与して文内の意味的な役割を記述する。図３に有向非循環グラフの一例を示す。
【００２８】
ここでは、ＡＭＲによるＤＡＧの意味表現から、文を生成する例を使って本発明の最良執行形式を述べる。
【００２９】
まず、問題の定義を述べる。ここで述べる、ノード・エッジラベル付き有向非循環グラフでは、ノードラベルおよびエッジラベルは有限個のラベル集合とする。ノードラベルの集合を
【００３０】
【数１】
0006550677.tif 000002
【００３１】
、エッジラベルの集合をεで表す。また、ノードラベルの種類数を
【００３２】
【数２】
0006550677.tif 000003
【００３３】
、エッジラベルの種類数を｜ε｜で表す。次に、各ノードラベルにそれぞれ一つのＤ１次元ベクトルを割り当てる。同様に、エッジラベルにもそれぞれ一つのＤ２次元ベクトルを割り当てる。例えば、ノードラベル
【００３４】
【数３】
0006550677.tif 000004
【００３５】
に対するＤ１次元ベクトルをラベル付きのベクトルｘｍ、エッジラベル
【００３６】
【数４】
0006550677.tif 000005
【００３７】
に対するＤ２次元ベクトルをラベル付きのベクトルｘｌと表す。
【００３８】
離散系列変換の処理の手順は以下のようになる。
【００３９】
（入力）
【００４０】
シンボルの離散系列である文を受理する。
【００４１】
（前処理）
【００４２】
既存のＡＭＲ解析器を用いて入力文をＡＭＲに変換する。
【００４３】
（処理１）
【００４４】
変換されたＡＭＲについて、有向非循環グラフの性質に則ってトポロジカルソートによるノードの順序付けを行う。
【００４５】
（処理２）
【００４６】
処理１で決定したノードの順序に従ってノード・エッジラベル付き有向非循環グラフ符号器を構成する。
【００４７】
（処理３）
【００４８】
入力文ＡＭＲを構築したノード・エッジラベル付き有向非循環グラフ符号器に代入し符号器を計算する。
【００４９】
（処理４）
【００５０】
処理３で得た符号を系列復号器へ入力し、系列復号器から文を生成する。
【００５１】
（出力）
【００５２】
系列復号器により生成された文を出力する。
【００５３】
＜各符号化ユニットおよび復号化ユニットのパラメタ学習＞
【００５４】
符号化ユニットと復号化ユニット内のパラメタは、従来技術として述べた通り、学習用データを使って決定する。学習後、パラメタは固定される。このパラメタが符号化の精度を決定する。
【００５５】
パラメタ学習法は、従来の系列構造−系列構造変換器と基本的に同じである現在のパラメタで、入力と符号とからなる学習用データの入力部分を符号化し、符号を復号器に入力して出力を得る。その際に、仮に正解データと同じ出力が得られれば、現在のパラメタはうまく調節ができていると言える。一方、正解データと同じでない場合は、正解が出るような方向にパラメタを調整する、といった処理を行うことで、最終的に、学習用データすべて正解ができるような方向にパラメタ探索することでパラメタを調整する。
【００５６】
＜本発明の実施の形態に係る離散系列変換装置の構成＞
【００５７】
次に、本発明の実施の形態に係る離散系列変換装置の構成について説明する。図４に示すように、本発明の実施の形態に係る離散系列変換装置１００は、ＣＰＵと、ＲＡＭと、後述する離散系列変換処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この離散系列変換装置１００は、機能的には図４に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００５８】
入力部１０は、文をシンボルの離散系列として受け付ける。
【００５９】
演算部２０は、変換部３０と、整列部３２と、符号器構築部３４と、符号器計算部３６と、復号器計算部３８とを含んで構成されている。
【００６０】
変換部３０は、入力部１０で受け付けたシンボルの離散系列を、シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフに変換する。変換には既存のＡＲＭ解析器を用いればよい。
【００６１】
整列部３２は、変換部３０により変換された有向非循環グラフの各エッジの向きに基づいて、有向非循環グラフの各ノードを順序付ける。
【００６２】
ここで、有向非循環グラフの各ノードの順序付けについて説明する。有向非循環グラフの場合は、ノードを有向エッジに従ってトポロジカルソートにより半順序で整列させることができる。本発明の実施の形態では、半順序関係によるノード順序未定義の関係に対しては、どのような順番で並べても処理結果には影響を与えないものとする。よって、順序関係が未定義の関係にあるノードの順番は適当（ランダム）に選択すれば良い。
【００６３】
本発明の実施の形態では、整列部３２は、シンボルの離散系列について、トポロジカルソートの逆順でノードを整列する。ノード集合をＶとする。また、エッジ集合をＥで表す。ノード集合Ｖ内の任意の２つのノードをｖｊ，ｖｋとする。このとき、ノードｖｊからノードｖｋに向かって有向エッジが存在する場合、有向エッジをｅｊ，ｋと表記する。ここでは、有向エッジｅｊ，ｋが存在する場合に、この二つのノード間の大小関係をｖｊ＞ｖｋと定義する。よって、ランダムに任意のノードｖｊを選択し、そのノードから有向エッジで辿れるノードをｖｋとすると、ｖｊ＞ｖｋの関係が成り立つ。よって、ノードを半順序で昇順に整列させる場合は、ｖｊから幅優先探索で出現したノードと逆順に並べることで、昇順に整列できる。ただし、重複して探索しないように一度探索したノードは探索空間から削除しながら探索を行う。辿れなかったノード集合に対して、また起点となるノードをランダムに選択し、同様の操作を繰り返すことで、ノードを半順序の昇順に整列できる。
【００６４】
符号器構築部３４は、整列部３２による各ノードの順序付けと、有向非循環グラフの各エッジとに沿って、各ノードに対応する、ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器を構築する。また、符号器は、ノード用の符号化ユニットは、前段の少なくとも一つのエッジ用の符号化ユニットの出力と当該ノードのラベルとを入力とし、エッジ用の符号化ユニットは、前段のノード用の符号化ユニットの出力と当該エッジのラベルとを入力とする。
【００６５】
ここで、符号器の構築の原理を説明する。符号器は、従来の系列構造符号器と同様に、符号化ユニットを連結することで符号器全体を構成する。符号化ユニット内部は様々な構成が考えられるが、ここでは例として、非特許文献３に記載の手法に従って、リカレントニューラルネット（ＲＮＮ）により構成する場合と、長短期記憶メモリ（ＬＳＴＭ）により構築する場合の例をあげる。ただし、σ１（・）とσ２（・）を、ベクトルを入力で受け取り、同じ次元数のベクトルを返す関数とする。また、σ１（・）は、入力されたラベル付きのベクトルｘの各要素に対してシグモイド関数
【００６６】
【数５】
0006550677.tif 000006
【００６７】
を計算し、入力ベクトルと同じ要素番号の出力ベクトルに代入する処理を行う。同様に、σ２（・）は、入力されたラベル付きのベクトルｘの各要素に対してｔａｎｈ関数
【００６８】
【数６】
0006550677.tif 000007
【００６９】
を計算し、入力ベクトルと同じ要素番号の出力ベクトルに代入する処理を行う。
【００７０】
以下に符号化ユニットをＲＮＮにより構築する場合と、ＬＳＴＭにより構築する場合の計算式を下記（１）式、（２）式に示す。本実施の形態では（１）式のＲＮＮによる構築を行うものとする。
【００７１】
【数７】
0006550677.tif 000008
【００７２】
【数８】
0006550677.tif 000009
【００７３】
ここで、
【００７４】
【数９】
0006550677.tif 000010
【００７５】
は、各符号化ユニットに接続する別の符号化ユニットの集合を表すとする。つまり、各符号化ユニットに入力される情報は、通常の入力ラベル付きのベクトルｘと、接続する別の符号化ユニットの中間（符号）状態ｚｋとなる。ここで一つ注意点として、従来の系列構造で使う場合は、各符号化ユニットの入力は一つ、つまり、
【００７６】
【数１０】
0006550677.tif 000011
【００７７】
に必ずなる。よって、上記（１）式、（２）式中のｋで総和を計算する部分は、系列構造符号化の際には、基本的に単一のベクトルの演算となる。
【００７８】
次に、ＲＮＮによる構成とＬＳＴＭによる符号化ユニットの構成の違いを述べる。単純に、ＬＳＴＭの場合は、メモリセル状態ｃと呼ぶ情報も中間状態として接続する符号化ユニットへ受け渡す。ＬＳＴＭにおけるメモリセル状態ｃは、長期の中間状態を保持するメモリの役割を果たす状態記憶場所となっている。なお、これら以外にも様々な符号化ユニットの亜種が考えられる。符号化ユニットの入力がラベル付きのベクトルｘと中間状態ｚｉｎであり、出力がｚｏｕｔの形式で書ける符号化ユニットであれば、基本的に何を用いてもよい。
【００７９】
具体的には、符号器構築部３４では、ノード・エッジラベル付き有向非循環グラフを符号化するために、各ノードに付与されたノードラベルの情報を上記（１）式に従って符号化するノード用の符号化ユニットと、各エッジに付与されたエッジラベルの情報を上記（１）式に従って符号化するエッジ用の符号化ユニットの二種類の符号化ユニットを定義する。このとき、ノード用とエッジ用の符号化ユニットは、符号化ユニット内のパラメタは共有せず、ノード用またエッジ用で別々であるとする。例えば、前述の通り、ノードラベルに割り当てられたベクトルがＤ１次元、エッジラベルに割り当てられたベクトルがＤ２次元、中間状態ｚのベクトルがＤ３次元だとすると、ノード用の符号化ユニット内のパラメタＷは、Ｄ１×Ｄ３行列であり、エッジ用の符号化ユニット内のパラメタＷは、Ｄ２×Ｄ３行列となる。また、符号化ユニット内のパラメタＷは、学習データにより予め学習されているものとする。
【００８０】
そして、符号器構築部３４は、整列部３２で整列したノードとノード間のエッジの構造に従って、ノード用とエッジ用の符号化ユニットを配置するように、それぞれのユニットを接続する。よって、本実施の形態での符号器の中身は、基本的に二層の作りになっており、一つはノード用の符号化ユニットの層、もう一つは、エッジ用の符号化ユニットの層である。また、ノード用の符号化ユニットとエッジ用の符号化ユニットは必ず交互に接続される形になる。
【００８１】
図５にノード・エッジラベル付き有向非循環グラフとその符号器の関係の例を示す。
【００８２】
符号器計算部３６は、整列部３２による各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、符号器構築部３４によって構築された符号器の、対応する符号化ユニットに入力して順次計算して、有向非循環グラフの符号を出力する。
【００８３】
ここで、符号器計算部３６における処理は、符号器構築部３４で構築した符号器を使って、ノード・エッジラベル付き有向非循環グラフを固定長ベクトルへ符号化する処理に相当する。従来法である系列構造符号器と同様に、整列部３２で順序付けたノード昇順に各符号化ユニットを計算し最終的な符号を得る。符号器構築部３４で示したように、本実施の形態では、ノード用の符号化ユニットとエッジ用の符号化ユニットとが交互に接続されるような形式となっている。
【００８４】
ノードｖｊに付与されたノードラベルをｍとし、ノードラベルｍをベクトル化したものを、ベクトルｘｍとする。また、ノードｖｊから出る有向エッジの集合をε（ｖｊ）とする。このとき、ノードｖｊのノードラベルｍを符号化するノード用の符号化ユニットの処理上の入力は、
【００８５】
【数１１】
0006550677.tif 000012
【００８６】
であり、ノードラベルをベクトル化したベクトルと、前段に出力された、エッジ用の符号化ユニットの出力である中間状態とが入力されることになる。ただし、
【００８７】
【数１２】
0006550677.tif 000013
【００８８】
とする。出力は、
【００８９】
【数１３】
0006550677.tif 000014
【００９０】
である。
【００９１】
有向エッジｅｊ，ｋに付与されたエッジラベルを
【００９２】
【数１４】
0006550677.tif 000015
【００９３】
とし、エッジラベル
【００９４】
【数１５】
0006550677.tif 000016
【００９５】
のベクトルを
【００９６】
【数１６】
0006550677.tif 000017
【００９７】
とする。このとき、有向エッジｅｊ，ｋのエッジラベルを符号化するエッジ用の符号化ユニットの処理上の入力は、
【００９８】
【数１７】
0006550677.tif 000018
【００９９】
である。ただし、ｖｋ番目のノードのノードラベルをノード用の符号化用ユニットに入力した際に得られた中間（符号化）状態を
【０１００】
【数１８】
0006550677.tif 000019
【０１０１】
とする。エッジ用の符号化ユニットの入力は本実施の形態の構成上、必ず一つのノード用の符号化ユニットの出力と接続する。
【０１０２】
出力は、
【０１０３】
【数１９】
0006550677.tif 000020
【０１０４】
である。
【０１０５】
最終的に全ての符号化ユニットを接続される順に計算して得られた中間状態が、ノード・エッジラベル付き有向非循環グラフの最終的な符号となる。
【０１０６】
復号器計算部３８は、符号器計算部３６で出力された有向非循環グラフの符号を、シンボルに復号する復号化ユニットの系列である系列復号器に入力して、順次計算して、シンボルの離散系列を出力する。また、系列復号器は、復号化ユニットは、前段の復号化ユニットの出力であるシンボルをベクトル化したもの及び中間状態を入力とする。
【０１０７】
復号器計算部３８では、本実施の形態では、得られた符号を受け取り、系列復号器を用いて文を生成する。この系列復号器における処理は基本的に従来法と同じである。以下に、非特許文献１で利用されている復号化ユニットにおける計算例を挙げる。
【０１０８】
【数２０】
0006550677.tif 000021
【０１０９】
上記（３）式では、符号化ユニットで上記（１）式を用いている場合、上記（１）式と同じ式に従って中間状態ｚｏｕｔが計算される。一方、符号化ユニットで上記（２）式を用いている場合、上記（２）式と同じ式に従って中間状態ｚｏｕｔが計算される。復号器の構成は、上記図７に記載の復号器である。一つ前の復号化ユニットの中間状態ｚｏｕｔを次の復号化ユニットの入力ｚｉｎとし、現在の復号化ユニットの出力ｙｏｕｔを得る。
【０１１０】
出力復号ユニットが一つずつ出力するｙｏｕｔから得られるシンボルを出力順に並べたものが最終的な出力となる。
【０１１１】
＜本発明の実施の形態に係る離散系列変換装置の作用＞
【０１１２】
次に、本発明の実施の形態に係る離散系列変換装置１００の作用について説明する。入力部１０において文をシンボルの離散系列として受け付けると、離散系列変換装置１００は、図６に示す符号化処理ルーチンを実行する。
【０１１３】
まず、ステップＳ１００では、入力部１０において受け付けたシンボルの離散系列を、シンボルの離散系列の意味構造を表し、かつ、各ノード及び各エッジにラベルが付与された有向非循環グラフに変換する。
【０１１４】
次に、ステップＳ１０２では、ステップＳ１００により変換された有向非循環グラフの各エッジの向きに基づいて、有向非循環グラフの各ノードを順序付ける。
【０１１５】
ステップＳ１０４では、ステップＳ１０２により得られた各ノードの順序付けと、有向非循環グラフの各エッジとに沿って、各ノードに対応する、ノードのラベルを符号化するノード用の符号化ユニットと、各エッジに対応する、エッジのラベルを符号化するエッジ用の符号化ユニットとを接続した符号器を構築する。
【０１１６】
ステップＳ１０６では、ステップＳ１０２で得られた各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、ステップＳ１０６で構築された符号器の、対応する符号化ユニットに入力して順次計算して、有向非循環グラフの符号を出力する。
【０１１７】
次のステップＳ１０８では、ステップＳ１０６で出力された有向非循環グラフの符号を復号化ユニットの系列である系列復号器に入力して、順次計算して、シンボルの離散系列を出力する。
【０１１８】
以上説明したように、本発明の実施の形態に係る離散系列変換装置によれば、シンボルの離散系列を有向非循環グラフに変換し、有向非循環グラフの各エッジの向きに基づいて、有向非循環グラフの各ノードを順序付け、各ノードの順序付けと、有向非循環グラフの各エッジとに沿って、ノード用の符号化ユニットと、エッジ用の符号化ユニットとを接続した符号器を構築し、各ノードの順序付けに沿って、各ノードのラベル及び各エッジのラベルを、構築された符号器の、対応する符号化ユニットに入力して順次計算して、有向非循環グラフの符号を出力し、系列復号器に入力して、順次計算することにより、シンボルの離散系列を表す有向非循環グラフを考慮して符号化された符号を復号することができる。
【０１１９】
また、本発明実施の形態に係る手法を用いることにより、自然言語処理の分野でよく用いられる、構文木、意味役割構造、中間意味表現、談話構造といった、文章を文法・意味的な解析を行った結果の構造を直接用いて、離散構造から離散構造への変換が可能となる。その結果、系列構造-系列構造変換器よりも、潤沢な情報が扱えることになるので、復号精度を向上させることが可能となる。
【０１２０】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１２１】
例えば、上述した実施の形態では、離散系列変換装置に本発明を適用する場合を例に説明したが、これに限定されるものではなく、符号化装置と、復号化装置とに分けて構成してもよい。その場合には、符号化装置は、上述した、変換部３０と、整列部３２と、符号器構築部３４と、符号器計算部３６とを含んで構成すればよく、復号化装置は、復号器計算部３８を含んで構成すればよい。
【符号の説明】
【０１２２】
１０   入力部
２０   演算部
３０   変換部
３２   整列部
３４   符号器構築部
３６   符号器計算部
３８   復号器計算部
５０   出力部
１００ 離散系列変換装置
【図１】
0006550677.tif 000022
【図２】
0006550677.tif 000023
【図３】
0006550677.tif 000024
【図４】
0006550677.tif 000025
【図５】
0006550677.tif 000026
【図６】
0006550677.tif 000027
【図７】
0006550677.tif 000028