(57)【要約】【課題】微分可能で、かつ、解釈性が高い動的計画法の演算を実現する。【解決手段】入力された第１のデータＸをニューラルネットワークにより第２のデータＹに変換する変換装置であって、前記第１のデータＸに対して所定の前処理を行うことで得られた第３のデータθと、ｍａｘ関数に対して強凸正則化関数Ωを導入したｍａｘΩ関数を用いて再帰的に定義されるＤＰΩ関数とを用いて、重み付き有向非巡回グラフＧで表される問題を対象とした動的計画法の解の近似ＤＰΩ（θ）を計算する計算手段と、前記計算手段により計算された前記ＤＰΩ（θ）と、該ＤＰΩ（θ）の勾配∇ＤＰΩ（θ）との少なくとも一方を前記第２のデータＹとして出力する出力手段と、を有することを特徴とする。【選択図】図２
2020009178.tif 000002
【特許請求の範囲】
【請求項１】
入力された第１のデータＸをニューラルネットワークにより第２のデータＹに変換する変換装置であって、
前記第１のデータＸに対して所定の前処理を行うことで得られた第３のデータθと、ｍａｘ関数に対して強凸正則化関数Ωを導入したｍａｘΩ関数を用いて再帰的に定義されるＤＰΩ関数とを用いて、重み付き有向非巡回グラフＧで表される問題を対象とした動的計画法の解の近似ＤＰΩ（θ）を計算する計算手段と、
前記計算手段により計算された前記ＤＰΩ（θ）と、該ＤＰΩ（θ）の勾配∇ＤＰΩ（θ）との少なくとも一方を前記第２のデータＹとして出力する出力手段と、
を有することを特徴とする変換装置。
【請求項２】
前記ＤＰΩ関数は、
【数６６】
2020009178.tif 000068
で定義される前記ｍａｘΩ関数を用いて、ｉ＝１，・・，Ｎに対して、
【数６７】
2020009178.tif 000069
で再帰的に定義されるｖｉ（θ）によって、ＤＰΩ（θ）＝ｖＮ（θ）と定義される、ことを特徴とする請求項１に記載の変換装置。
【請求項３】
前記強凸正則化関数Ωは、
γ＞０として、
【数６８】
2020009178.tif 000070
又は
【数６９】
2020009178.tif 000071
のいずれかである、ことを特徴とする請求項１又は２に記載の変換装置。
【請求項４】
入力された第１のデータＸを第２のデータＹに変換するニューラルネットワークの学習を行う学習装置であって、
前記第１のデータＸに対して所定の前処理を行うことで得られた第３のデータθと、ｍａｘ関数に対して強凸正則化関数Ωを導入したｍａｘΩ関数を用いて再帰的に定義されるＤＰΩ関数とを用いて、重み付き有向非巡回グラフＧで表される問題を対象とした動的計画法の解の近似ＤＰΩ（θ）を計算する計算手段と、
前記計算手段により計算された前記ＤＰΩ（θ）と、該ＤＰΩ（θ）の勾配∇ＤＰΩ（θ）との少なくとも一方を前記第２のデータＹとして出力する出力手段と、
前記出力手段により出力された前記ＤＰΩ（θ）又は前記∇ＤＰΩ（θ）と、前記第１のデータＸに対する正解データＹｔｒｕｅとを用いた損失関数の微分値に基づいて、前記ニューラルネットワークのパラメータである前記θを更新する更新手段と、
を有することを特徴とする学習装置。
【請求項５】
前記損失関数は、
前記出力手段により前記ＤＰΩ（θ）が出力された場合は、ＤＰΩ（θ）−＜Ｙｔｒｕｅ，θ＞であり、
前記出力手段により前記∇ＤＰΩ（θ）が出力された場合は、ダイバーバージェンスΔ（Ｙｔｒｕｅ，∇ＤＰΩ（θ））である、ことを特徴とする請求項４に記載の学習装置。
【請求項６】
入力された第１のデータＸをニューラルネットワークにより第２のデータＹに変換するコンピュータが、
前記第１のデータＸに対して所定の前処理を行うことで得られた第３のデータθと、ｍａｘ関数に対して強凸正則化関数Ωを導入したｍａｘΩ関数を用いて再帰的に定義されるＤＰΩ関数とを用いて、重み付き有向非巡回グラフＧで表される問題を対象とした動的計画法の解の近似ＤＰΩ（θ）を計算し、
計算された前記ＤＰΩ（θ）と、該ＤＰΩ（θ）の勾配∇ＤＰΩ（θ）との少なくとも一方を前記第２のデータＹとして出力する、
処理を実行することを特徴とする変換方法。
【請求項７】
入力された第１のデータＸを第２のデータＹに変換するニューラルネットワークの学習を行うコンピュータが、
前記第１のデータＸに対して所定の前処理を行うことで得られた第３のデータθと、ｍａｘ関数に対して強凸正則化関数Ωを導入したｍａｘΩ関数を用いて再帰的に定義されるＤＰΩ関数とを用いて、重み付き有向非巡回グラフＧで表される問題を対象とした動的計画法の解の近似ＤＰΩ（θ）を計算し、
計算された前記ＤＰΩ（θ）と、該ＤＰΩ（θ）の勾配∇ＤＰΩ（θ）との少なくとも一方を前記第２のデータＹとして出力し、
出力された前記ＤＰΩ（θ）又は前記∇ＤＰΩ（θ）と、前記第１のデータＸに対する正解データＹｔｒｕｅとを用いた損失関数の微分値に基づいて、前記ニューラルネットワークのパラメータである前記θを更新する、
処理を実行することを特徴とする学習方法。
【請求項８】
コンピュータを、請求項１乃至３の何れか一項に記載の変換装置における各手段、又は、請求項４又は５に記載の学習装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、変換装置、学習装置、変換方法、学習方法及びプログラムに関する。
【背景技術】
【０００２】
ニューラルネットワークと呼ばれる数学モデルが従来から知られている。古典的なニューラルネットワークは、ベクトルで表現される入力データを、ベクトルやスカラー等で表現される出力データに変換する計算を行う。このようなニューラルネットワークにおける計算は、各層をそれぞれ表す関数を入れ子にした形式で記述することができる。
【０００３】
ところで、近年では、ニューラルネットワークが様々な分野に応用されるようになってきており、複雑な問題をニューラルネットワークで扱うことも多くなってきている。このような複雑な問題をニューラルネットワークで扱う場合には、入力データや出力データが構造化されたデータ（以降、「構造化データ」とも表す。）であることが多い。ここで、構造化データとは、単なるベクトル等のデータではなく、何等かの構造を有するデータのことであり、例えば、データに含まれる要素間に構造的な関係性があるデータや、他のデータとの間に構造的な関係性があるデータ等のことである。構造化データの具体例としては、例えば、テキスト文書を構成する単語系列や、複数の時系列データ間の対応関係を表すベクトル又は行列等が挙げられる。
【０００４】
このような構造化データをニューラルネットワークで扱うために、動的計画法（Dynamic Programming）の演算をニューラルネットワークの層として用いる方法が知られている。動的計画法の演算は、対象となる問題を再帰的に複数の部分問題に分割し、分割問題を順次解いていくことで解を求める手法である。ただし、動的計画法の演算は、その多様な表現力ゆえに、微分不可能な演算となることが多い。
【０００５】
ここで、ニューラルネットワークのパラメータを誤差逆伝播法等により学習する場合、ニューラルネットワークの予測出力と正解データとに基づいて、所定の損失関数の微分値が計算される。このため、ニューラルネットワークの各層で行われる演算は微分可能である必要がある。
【０００６】
しかしながら、動的計画法の演算は微分不可能な演算となる場合が多いため、動的計画法を行う層を有するニューラルネットワークでは、パラメータの学習が困難になることがある。これに対して、条件付き確率場（ＣＲＦ：Conditional Random Field）を用いて、動的計画法の演算を微分可能な演算に変換する方法が提案されている（例えば、非特許文献１及び２）。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Lample, Guillaume, Ballesteros, Miguel, Subramanian, Sandeep, Kawakami, Kazuya, and Dyer, Chris. Neural architectures for named entity recognition. In Proc. of NAACL, pp. 260-270, 2016.
【非特許文献２】Cuturi, Marco and Blondel, Mathieu. Soft-DTW: a Differentiable Loss Function for Time-Series. In Proc. of ICML, pp. 894-903, 2017.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献１及び２で提案されている方法では、動的計画法の演算を行う層の出力データのスパース性が失われてしまうため、出力データの解釈性が低下する場合があった。
【０００９】
動的計画法が対象とする問題では、入力された構造化データ（以降、「構造化入力データ」とも表す。）と、出力された構造化データ（以降、「構造化出力データ」とも表す。）との解釈性が重要になる場合が多い。例えば、テキスト文書を構成する単語系列を構造化入力データ、当該単語系列に含まれる各単語へのタグ（例えば、単語の品詞やカテゴリ等を表すタグ）付けを表す行列を構造化出力データとした場合、１つの単語に対して１つのタグが対応付けられた構造化出力データが得られることが好ましいことが多い。しかしながら、非特許文献１及び２で提案されている方法では、動的計画法の演算を行う層の出力データのスパース性が失われてしまうため、例えば、１つの単語に対して複数のタグが対応付けられた構造化出力データが得られる場合がある。このため、例えば、１つの単語に対して１つの品詞を特定するといった解釈が困難になることがある。
【００１０】
本発明の実施の形態は、上記の点に鑑みてなされたもので、微分可能で、かつ、解釈性が高い動的計画法の演算を実現することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明の実施の形態は、入力された第１のデータＸをニューラルネットワークにより第２のデータＹに変換する変換装置であって、前記第１のデータＸに対して所定の前処理を行うことで得られた第３のデータθと、ｍａｘ関数に対して強凸正則化関数Ωを導入したｍａｘΩ関数を用いて再帰的に定義されるＤＰΩ関数とを用いて、重み付き有向非巡回グラフＧで表される問題を対象とした動的計画法の解の近似ＤＰΩ（θ）を計算する計算手段と、前記計算手段により計算された前記ＤＰΩ（θ）と、該ＤＰΩ（θ）の勾配∇ＤＰΩ（θ）との少なくとも一方を前記第２のデータＹとして出力する出力手段と、を有することを特徴とする。
【発明の効果】
【００１２】
本発明の実施の形態によれば、微分可能で、かつ、解釈性が高い動的計画法の演算を実現することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施の形態における変換装置の機能構成の一例を示す図である。
【図２】本発明の実施の形態における学習装置の機能構成の一例を示す図である。
【図３】ビタビアルゴリズムを実現する場合の有向非巡回グラフの一例を示す図である。
【図４】動的時間伸縮法を実現する場合の有向非巡回グラフの一例を示す図である。
【図５】本発明の効果の一例を示す図である。
【図６】本発明の実施の形態における変換装置及び学習装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について説明する。本発明の実施の形態では、構造化入力データを構造化出力データに変換する変換装置１００について説明する。このとき、本発明の実施の形態における変換装置１００は、微分可能な動的計画法の演算により、構造化入力データを、解釈性が高い構造化出力データに変換する。本発明の実施の形態における変換装置１００が実行する動的計画法の演算は、ニューラルネットワークの層として実現される。
【００１５】
また、本発明の実施の形態では、上記の動的計画法の演算が層として実現されているニューラルネットワークの学習を行う学習装置２００についても説明する。
【００１６】
ここで、構造化入力データを構造化出力データに変換するタスクとしては、例えば、品詞タグ付け（Part-of-Speech Tagging）が挙げられる。品詞タグ付けでは、例えば、テキスト文書を構成する単語系列が構造化入力データ、当該単語系列に含まれる各単語へのタグ（例えば、単語の品詞を表すタグ）付けを表す行列が構造化出力データとなる。この場合、本発明の実施の形態における変換装置１００は、テキスト解析装置として機能することになる。
【００１７】
構造化入力データを構造化出力データに変換する別のタスクとしては、例えば、翻訳が挙げられる。翻訳では、例えば、原言語のテキスト文書を構成する単語系列が構造化入力データ、当該単語系列を目的言語に翻訳した単語系列が構造化出力データとなる。この場合、本発明の実施の形態における変換装置１００は、翻訳装置として機能することになる。
【００１８】
構造化入力データを構造化出力データに変換する別のタスクとしては、例えば、複数の時系列データ間のアラインメントが挙げられる。アラインメントでは、例えば、複数の時系列データを表すデータが構造化入力データ、これら複数の時系列データ間の対応関係（例えば、複数の時系列データにそれぞれ含まれる各要素間の類似度等）を表すベクトル又は行列等が構造化出力データとなる。この場合、本発明の実施の形態における変換装置１００は、時系列データのアラインメント装置として機能することになる。
【００１９】
なお、構造化入力データとしては、上述した単語系列や複数の時系列データ等に限られない。構造化入力データとしては、系列や配列等で表される任意のデータを用いることができる。例えば、画像データ、映像データ、音響信号を表すデータ、生体信号を表すデータ等も構造化入力データとして用いることができる。
【００２０】
＜理論的背景＞
以降では、本発明の実施の形態における変換装置１００及び学習装置２００が実行する動的計画法を用いた変換や学習等の理論的背景について説明する。本発明の実施の形態では、構造化入力データをＸ、構造化出力データをＹで表す。また、構造化出力データＸの集合を
【００２１】
【数１】
2020009178.tif 000003
、構造化出力データＹの集合を
【００２２】
【数２】
2020009178.tif 000004
で表す。
【００２３】
構造化入力データＸを構造化出力データＹに変換する何等かのタスクを行う際には、例えば、以下の式（１）や式（２）に示す手順が行われる。
【００２４】
【数３】
2020009178.tif 000005
【００２５】
【数４】
2020009178.tif 000006
ここで、θは実数を要素とする行列又はテンソルであり、Θはθの集合である。また、「太字のＲ」は実数全体を表す。以降では、明細書における表記の便宜上、実数全体を単に「Ｒ」とも表す。
【００２６】
前処理（preprocessing）は、動的計画法が対象とする問題に応じて、構造化入力データＸをθに変換（射影）するものであり、例えばニューラルネットワークにより実現される。具体的には、例えば、上述した品詞タグ付け（Part-of-Speech Tagging）を行う問題であれば、この前処理は双方向長短期記憶（ＢＬＳＴＭ：bi-directional long short-term memory）により実現される。
【００２７】
上記の式（１）は動的計画法が対象とする問題の目的関数の最適解（ｖａｌｕｅ）を求めるものであり、上記の式（２）は当該最適解を与える目的関数の引数（Ｙ＊）を求めるものである。上記の式（１）では、動的計画法が対象とする問題の目的関数を解くことにより最適解（ｖａｌｕｅ）が得られる。一方で、上記の式（２）では、当該最適解（Ｖａｌｕｅ）を得た後に、バックトラッキングを行うことで目的関数の引数（Ｙ＊）が得られる。
【００２８】
目的関数の最適解（ｖａｌｕｅ）又は最適解を与える目的関数の引数（Ｙ＊）の何れが必要となるかは、動的計画法が対象とする問題によって異なる。例えば、上述した品詞タグ付け（Part-of-Speech Tagging）を行う問題や複数の時系列データ間のアラインメントを行う問題であれば、最適解を与える目的関数の引数（Ｙ＊）が必要となる。なお、目的関数の最適解（ｖａｌｕｅ）と最適解を与える目的関数の引数（Ｙ＊）との両方が必要になる場合もある。
【００２９】
一般に、構造化入力データＸから構造化出力データＹを得たい場合には上記の式（２）の手順により、最適解を与える目的関数の引数（Ｙ＊）を得ることが行われる。このとき、構造化出力データＹ＝Ｙ＊である。一方で、構造化入力データＸから構造化出力データＹ＝Ｙ＊が得られた場合における何等かの値（例えば、Ｙ＊が得られた場合における品詞タグ付けの精度等）を得たい場合には上記の式（１）の手順により、目的関数の解（ｖａｌｕｅ）を得ることが行われる。
【００３０】
また、一般に、動的計画法が対象とする問題の目的関数の最適解（ｖａｌｕｅ）を「動的計画法の解」と呼ぶ場合が多いが、最適解を与える目的関数の引数（Ｙ＊）を「動的計画法の解」と呼ぶ場合もある。本発明の実施の形態では、動的計画法が対象とする問題の目的関数の最適解（ｖａｌｕｅ）を「動的計画法の解」と呼ぶこととする。
【００３１】
ここで、上述した前処理によってθが得られたと仮定すると、動的計画法が対象とする問題の目的関数の最適解（ｖａｌｕｅ）を求める処理は、重み付き有向非巡回グラフ（ＤＡＧ：Directed Acyclic Graph）上の開始ノードから終了ノードまでの経路のうち、所定のスコアが最大となる経路を見つける問題に定式化することができる。
【００３２】
そこで、Ｇ＝（ν，ε）をノード集合νとエッジ集合εとで構成される重み付き有向非巡回グラフとする。また、ノード数Ｎは、Ｎ＝｜ν｜≧２であるものとする。エッジ集合εに含まれる各エッジは有向エッジであり、或るノードから別の或るノードへの有向エッジが存在する場合、当該或るノードが「親ノード」、当該別の或るノードが「子ノード」となる。
【００３３】
一般性を欠くことなく、何れのノードも子ノードよりも小さい番号となるように、各ノードに対して順番に番号（ＩＤ）を付与し、各ノードを順序付けることができる。ＩＤが１のノードを開始ノード、ＩＤがＮのノードを終了ノードとする。これにより、
【００３４】
【数５】
2020009178.tif 000007
と表すことができる。以降では、ＩＤがｎのノードを「ノードｎ」と表す。なお、「＝の上に△が付与された記号」は、この記号の左辺を右辺で定義することを意味する。
【００３５】
重み付き有向非巡回グラフＧにおいて、ノード１は親ノードを持たない唯一のノードであり、ノードＮは子ノードを持たない唯一のノードである。また、重み付き有向非巡回グラフＧにおいて、親ノードｊから子ノードｉへの有向エッジ（ｉ，ｊ）は、重みθｉ，ｊ∈Ｒを持つものとする。
【００３６】
重み付き有向非巡回グラフＧの各重みθｉ，ｊを要素とする行列をθ∈Θ⊆ＲＮ×Ｎとする。ただし、エッジ集合εに含まれない有向エッジ（ｉ，ｊ）に関する重みθｉ，ｊは、θｉ，ｊ＝−∞とする。
【００３７】
重み付き有向非巡回グラフＧにおいてノード１からノードＮに至る全ての経路（パス）の集合を
【００３８】
【数６】
2020009178.tif 000008
とすれば、任意の経路
【００３９】
【数７】
2020009178.tif 000009
は、Ｎ×Ｎのバイナリ行列で表すことができる。すなわち、経路Ｙ´は、（ｉ，ｊ）成分の要素をｙ´ｉｊとした場合に、経路Ｙ´が有向エッジ（ｉ，ｊ）を通る場合にｙ´ｉｊ＝１、通らない場合にｙ´ｉｊ＝０となる要素ｙ´ｉｊで表される行列である。このように表現された経路Ｙ´は、構造化出力データＹと１対１に対応する。したがって、以降では、経路Ｙ´を構造化出力データＹと同一視して、「経路Ｙ」（経路Ｙの（ｉ，ｊ）成分の要素はｙｉｊ）と表す。同様に、経路Ｙの集合と構造化出力データＹの集合とは同一視される。
【００４０】
このとき、Ｙとθとのフロベニウス内積を＜Ｙ，θ＞と表した場合、＜Ｙ，θ＞は経路Ｙに沿って各エッジ（ｉ，ｊ）の重みθｉ，ｊを足し合わせた総和に相当する。したがって、フロベニウス内積＜Ｙ，θ＞をスコアとして、全ての経路Ｙの中からスコアが最大となる経路Ｙ＝Ｙ＊を求めるには、以下の組み合わせ問題ＬＰ（θ）を計算することになる。
【００４１】
【数８】
2020009178.tif 000010
ここで、
【００４２】
【数９】
2020009178.tif 000011
の大きさはＮに対して指数関数的に増大するが、ＬＰ（θ）は、動的計画法を用いて、重み付き有向非巡回グラフＧ上の１つの順序付けられた経路Ｙについて計算することができる。そこで、重み付き有向非巡回グラフＧにおけるノードｉの親ノードの集合を
【００４３】
【数１０】
2020009178.tif 000012
として、ｖｉ（θ）を以下の式（３）により再帰的に定義する。
【００４４】
【数１１】
2020009178.tif 000013
そうすると、最終的に計算されるｖＮ（θ）がＤＰ（θ）となる。すなわち、
【００４５】
【数１２】
2020009178.tif 000014
である。
【００４６】
動的計画法により計算される解が最適であることは証明することができるため、任意のθ∈Θに対して、ＤＰ（θ）＝ＬＰ（θ）が成り立つ。すなわち、再帰的に定義された上記の式（３）を計算することで、動的計画法の解（上記の式（１）におけるｖａｌｕｅ）を求めることができる。
【００４７】
ここで、上記の式（２）のように、動的計画法の解（目的関数の最適解）が得られた場合に、この最適解を与える目的関数の引数（Ｙ＊）を求める問題は、最大スコアを与える経路Ｙに対して、
【００４８】
【数１３】
2020009178.tif 000015
を求める問題であると言える。上記の式（４）に示す引数（Ｙ＊）は、まず、上記の式（３）の再帰的な計算を行った後、バックトラッキングを行うことで求めることができる。
【００４９】
しかしながら、ＤＰ（θ）は微分不可能であり、Ｙ＊（θ）は不連続関数である。このため、ニューラルネットワークの層として動的計画法の演算を実現する場合、誤差逆伝播法等による微分値（所定の損失関数の微分値）の計算を行うことができないため、例えば勾配降下法（gradient descent）等を用いたニューラルネットワークの学習を行うことができない。
【００５０】
そこで、本発明の実施の形態では、上記の式（１）及び式（２）に示す手順の代わりに、以下の式（１´）及び式（２´）に示す手順を用いる。
【００５１】
【数１４】
2020009178.tif 000016
【００５２】
【数１５】
2020009178.tif 000017
ここで、ＤＰΩはＤＰの近似であり、ＤＰΩ以降に続く処理（すなわち、ニューラルネットワークにおいて、動的計画法の演算を行う層以降の層が行う処理）も、ＤＰを用いた場合と同様に正確に定義することができる。また、∇ＤＰΩはＤＰΩの勾配であり、
【００５３】
【数１６】
2020009178.tif 000018
である。この凸包は、
【００５４】
【数１７】
2020009178.tif 000019
で定義される。また、ΔＤはＤ次元の単体（simplex）であり、
【００５５】
【数１８】
2020009178.tif 000020
で定義される。
【００５６】
ここで、ＤＰΩ及び∇ＤＰΩは、ＤＰ及びＹ＊と異なり、微分可能である。また、任意の精度をγ（言い換えれば、ＤＰΩとＤＰとの誤差をγ）とすれば、ＤＰΩ及びＤＰの関係と、∇ＤＰΩ及びＹ＊の関係とは、それぞれ以下のように表される。
【００５７】
【数１９】
2020009178.tif 000021
上記の式（１´）及び式（２´）により近似した手順を用いて動的計画法の問題を扱うため、ｍａｘ関数を、以下で定義されるｍａｘΩ関数で置き換えることを考える。
【００５８】
【数２０】
2020009178.tif 000022
ここで、Ω：ΔＤ→Ｒ は強凸正則化関数（strongly-convex regularization function）である。
【００５９】
また、
【００６０】
【数２１】
2020009178.tif 000023
に関するｍａｘΩ関数として、便宜的に以下の表記を導入する。
【００６１】
【数２２】
2020009178.tif 000024
そして、上記の式（３）をｍａｘΩ関数で置き換えることで、以下の式（５）を再帰的に定義することができる。
【００６２】
【数２３】
2020009178.tif 000025
以降では、上記の式（５）を、便宜的に、
【００６３】
【数２４】
2020009178.tif 000026
とも表す。
【００６４】
上記の式（５）により最終的に計算されるｖＮ（θ）がＤＰΩ（θ）となる。すなわち、
【００６５】
【数２５】
2020009178.tif 000027
である。
【００６６】
以上により、動的計画法の演算を行う層は、以下の２つの層（Ｖａｌｕｅ  ｌａｙｅｒ及びＧｒａｄｉｅｎｔ  ｌａｙｅｒ）で表現することができる。
【００６７】
【数２６】
2020009178.tif 000028
なお、動的計画法の解を得たい場合には、ニューラルネットワークの層として、Ｖａｌｕｅ  ｌａｙｅｒを用いれば良い。一方で、動的計画法の解を与える目的関数の引数を得たい場合には、ニューラルネットワークの層として、Ｇｒａｄｉｅｎｔ  ｌａｙｅｒを用いれば良い。
【００６８】
Ｖａｌｕｅ  ｌａｙｅｒであるＤＰΩ（θ）は、ＤＰ（θ）の微分可能な近似として利用することができる。例えば、ＤＰΩ（θ）は、ニューラルネットワークの学習時に、正解出力Ｙｔｒｕｅと、当該ニューラルネットワークの予測出力∇ＤＰΩ（θ）とがどの程度近付いたかを表す損失関数（この損失関数をＬ１と表す。）を定義する際に用いることができる。損失関数Ｌ１は、例えば、以下の式（６）により定義される。
【００６９】
【数２７】
2020009178.tif 000029
この損失関数Ｌ１の値が小さい程、正解出力Ｙｔｒｕｅにより近い予測出力∇ＤＰΩ（θ）が得られたことを表している。
【００７０】
ニューラルネットワークの或る層としてＶａｌｕｅ  ｌａｙｅｒ（すなわち、ＤＰΩ（θ）の演算を行う層）を用いた場合、このニューラルネットワークのパラメータを学習するためにＤＰΩ（θ）の勾配∇ＤＰΩ（θ）を計算する必要がある。この勾配∇ＤＰΩ（θ）は、上記の式（５）を用いて誤差逆伝播法により計算することができる。より具体的には、Ｅ＝（ｅｉｊ）∈ＲＮ×Ｎ，Ｑ＝（ｑｉｊ）∈ＲＮ×Ｎ，ｈ＝（ｈ１，・・・，ｈＮ）∈ＲＮとして、以下のＳｔｅｐ１−１〜Ｓｔｅｐ１−３の手順によりＥ＝∇ＤＰΩ（θ）∈ＲＮ×Ｎを得ることができる。なお、θ∈ＲＮ×Ｎは所与であるものとする。
【００７１】
Ｓｔｅｐ１−１：初期化手順として、ｖ１←０∈Ｒ，ｈＮ←１∈Ｒ，Ｑ←０∈ＲＮ×Ｎ，Ｅ←０∈ＲＮ×Ｎとする。なお、「←」は、左辺に右辺を代入することを意味する。
【００７２】
Ｓｔｅｐ１−２：順方向手順として、ｉ＝２，・・・，Ｎに対して、順に、以下の計算及び代入をそれぞれ行う。
【００７３】
【数２８】
2020009178.tif 000030
Ｓｔｅｐ１−３：逆方向手順として、ｊ＝Ｎ−１，・・・，１に対して、順に、以下の計算及び代入をそれぞれ行う。
【００７４】
【数２９】
2020009178.tif 000031
以上の手順により最終的に得られたＥが∇ＤＰΩ（θ）である。
【００７５】
一方で、Ｇｒａｄｉｅｎｔ  ｌａｙｅｒである∇ＤＰΩ（θ）は、上記の式（４）により定義されるＹ＊（θ）の微分可能な近似として利用することができる。例えば、∇ＤＰΩ（θ）は、ニューラルネットワークの学習時に、正解出力Ｙｔｒｕｅと、当該ニューラルネットの予測出力∇ＤＰΩ（θ）とがどの程度近付いたかを表す損失関数（この損失関数をＬ２と表す。）を定義する際に用いることができる。損失関数Ｌ２は、例えば、以下の式（７）により定義される。
【００７６】
【数３０】
2020009178.tif 000032
ここで、Δは、例えば、ユークリッド距離やカルバック・ライブラー情報量（Kullback-Leibler divergence）等のダイバージェンスである。この損失関数Ｌ２の値が小さい程、正解出力Ｙｔｒｕｅにより近い予測出力∇ＤＰΩ（θ）が得られたことを表している。
【００７７】
ニューラルネットワークの或る層としてＧｒａｄｉｅｎｔ  ｌａｙｅｒ（すなわち、∇ＤＰΩ（θ）の演算を行う層）を用いた場合、このニューラルネットワークのパラメータを学習するために、∇ＤＰΩ（θ）のヤコビアン∇∇ＤＰΩ（θ）（すなわち、ヘッセ行列（Hessian）∇２ＤＰΩ（θ））と、与えられた行列Ｚ∈ＲＮ×Ｎとの積を計算する必要がある。これは、以下の参考文献１に開示されているＰｅａｒｌｍｕｔｔｅｒ'ｓ  ｍｅｔｈｏｄにより計算することができる。
【００７８】
［参考文献１］
Pearlmutter, Barak A. Fast exact multiplication by the Hessian. Neural computation, 6(1):147-160, 1994.
なお、Ｇｒａｄｉｅｎｔ  ｌａｙｅｒである∇ＤＰΩ（θ）を、ニューラルネットワークの注意機構（attention mechanism）として用いることもできる。
【００７９】
ここで、ＤＰΩ（θ）及び∇ＤＰΩ（θ）に用いられるｍａｘΩ関数は、動的計画法が対象とする問題に応じて適宜に設定されれば良いが、以下にｍａｘΩ関数の具体例を２つ示す。
【００８０】
・ｍａｘΩ関数の具体例１
ｍａｘΩ関数の具体例１は、強凸正則化関数Ωとしてｎｅｇａｔｉｖｅ  ｅｎｔｒｏｐｙを用いたものである。
【００８１】
γ＞０として、
【００８２】
【数３１】
2020009178.tif 000033
とする。すると、ｍａｘΩ関数、勾配∇ｍａｘΩ及びヘッセ行列∇２ｍａｘΩは、それぞれ以下で表される。
【００８３】
【数３２】
2020009178.tif 000034
ここで、
【００８４】
【数３３】
2020009178.tif 000035
である。また、ｄｉａｇ（ｑ）は、対角成分がｑの各要素で与えられる正方行列である。なお、γ＝１とすれば、∇ｍａｘΩはｓｏｆｔｍａｘと一致する。
【００８５】
・ｍａｘΩ関数の具体例２
ｍａｘΩ関数の具体例２は、強凸正則化関数Ωとしてｓｑｕａｒｅｄ  ２−ｎｏｒｍを用いたものである。
【００８６】
γ＞０として、
【００８７】
【数３４】
2020009178.tif 000036
とする、すると、ｍａｘΩ関数、勾配∇ｍａｘΩ及びヘッセ行列∇２ｍａｘΩは、それぞれ以下で表される。
【００８８】
【数３５】
2020009178.tif 000037
ここで、
【００８９】
【数３６】
2020009178.tif 000038
である。また、ｓ∈｛０，１｝Ｄは、ベクトルｑをサポートするベクトルである。なお、∇ｍａｘΩは、単体上へのユークリッド射影である。
【００９０】
具体例２における∇ｍａｘΩは、以下の参考文献２に記載されている「ｓｐａｒｓｅｍａｘ」と一致する。このため、具体例２におけるｍａｘΩ関数を用いた場合、スパース性の高い構造化出力データＹを得られることが期待できる。
【００９１】
［参考文献２］
Martins, Andre F.T. and Astudillo, Ramoon Fernandez. From softmax to sparsemax: A sparse model of attention and multi-label classification. In Proc. of ICML, pp. 1614-1623, 2016.
＜機能構成＞
以降では、本発明の実施の形態における変換装置１００及び学習装置２００の機能構成について説明する。
【００９２】
（変換装置１００）
まず、本発明の実施の形態における変換装置１００の機能構成について、図１を参照しながら説明する。図１は、本発明の実施の形態における変換装置１００の機能構成の一例を示す図である。
【００９３】
図１に示すように、本発明の実施の形態における変換装置１００は、前処理部１０１と、変換処理部１０２とを有する。これら各機能部は、例えば、変換装置１００にインストールされた１以上のプログラムが、ＣＰＵ（Central Processing Unit）等の演算装置に実行させる処理により実現される。
【００９４】
前処理部１０１及び変換処理部１０２は、構造化入力データＸを構造化出力データＹ（＝∇ＤＰΩ（θ））に変換する。又は、前処理部１０１及び変換処理部１０２は、構造化入力データＸを、動的計画法の解（＝ＤＰΩ（θ））に変換する。なお、上述したように、ＤＰΩ（θ）は、正確には動的計画法の解ＤＰ（θ）の近似である。
【００９５】
前処理部１０１及び変換処理部１０２は、１以上のニューラルネットワークにより実現される。例えば、上述したように、前処理部１０１は、双方向長短期記憶（ＢＬＳＴＭ）等のニューラルネットワークで実現され、変換処理部１０２は、動的計画法の演算を行う層を有するニューラルネットワークにより実現される。
【００９６】
なお、前処理部１０１及び変換処理部１０２は、前処理部１０１を実現するニューラルネットワークと、変換処理部１０２を実現するニューラルネットワークとを組み合わせたニューラルネットワークにより実現されていても良い。この場合、前処理部１０１及び変換処理部１０２を実現するニューラルネットワークは、構造化入力データＸをθに変換する層（前処理部１０１の演算を行う層）と、θを構造化出力データＹ（＝∇ＤＰΩ（θ））又は動的計画法の解（＝ＤＰΩ（θ））に変換する層（変換処理部１０２の演算を行う層）とを有することになる。
【００９７】
前処理部１０１は、学習済のニューラルネットワークにより、上記の式（１´）又は式（２´）における前処理（preprocessing）を行う。すなわち、前処理部１０１は、構造化入力データＸをθに変換する。この前処理は、動的計画法が対象とする問題に応じて決定される所定の前処理である。例えば、上述したように、動的計画法が対象とする問題が品詞タグ付け（Part-of-Speech Tagging）である場合、この前処理は、双方向長短期記憶（ＢＬＳＴＭ）により実現される。
【００９８】
なお、変換装置１００が前処理部１０１を有する代わりに、変換装置１００とは異なる別の装置が前処理部１０１を有しても良い。この場合、当該別の装置の前処理部１０１で構造化入力データＸをθに変換した後、このθを変換装置１００に入力するようにしても良い。
【００９９】
変換処理部１０２は、学習済のニューラルネットワークにより、上記の式（１´）又は式（２´）におけるＤＰΩ又は∇ＤＰΩに相当する演算を行う。すなわち、変換処理部１０２は、前処理部１０１による前処理で得られたθを、構造化出力データＹ（＝∇ＤＰΩ（θ））又は動的計画法の解（＝ＤＰΩ（θ））に変換する。この変換結果（ＤＰΩ（θ）又は∇ＤＰΩ（θ））は、所定の出力先に出力される。所定の出力先としては、例えば、ディスプレイ等の表示装置、補助記憶装置等の記憶装置、他のプログラム、他の装置、ニューラルネットワークにおける次の層等が挙げられる。
【０１００】
ＤＰΩに相当する演算を行う場合、変換処理部１０２は、上記の式（５）で再帰的に定義された演算を行えば良い。これにより、ＤＰΩ（θ）＝ｖＮ（θ）が得られる。
【０１０１】
一方で、∇ＤＰΩに相当する演算を行う場合、変換処理部１０２は、上記のＳｔｅｐ１−１〜Ｓｔｅｐ１−３の手順で示される演算を行えば良い。これにより、∇ＤＰΩ（θ）が得られる。
【０１０２】
なお、上述したように、変換処理部１０２による変換結果として、ＤＰΩ（θ）又は∇ＤＰΩ（θ）の何れを求めたいかは、動的計画法の対象とする問題に応じて決定される。なお、変換処理部１０２による変換結果として、ＤＰΩ（θ）と∇ＤＰΩ（θ）との両方を求めても良い。
【０１０３】
（学習装置２００）
次に、本発明の実施の形態における学習装置２００の機能構成について、図２を参照しながら説明する。図２は、本発明の実施の形態における学習装置２００の機能構成の一例を示す図である。
【０１０４】
図２に示すように、本発明の実施の形態における学習装置２００は、学習用データ入力部２０１と、前処理部１０１と、変換処理部１０２と、パラメータ更新部２０２とを有する。これら各機能部は、学習装置２００にインストールされた１以上のプログラムが、ＣＰＵ等の演算装置に実行させる処理により実現される。
【０１０５】
なお、学習装置２００の前処理部１０１及び変換処理部１０２は、上述した変換装置１００の前処理部１０１及び変換処理部１０２と同様である。ただし、学習装置２００の前処理部１０１及び変換処理部１０２を実現するニューラルネットワークのパラメータには、例えば、予め決められた初期値が設定されている。これらのパラメータが学習によって更新される。
【０１０６】
学習用データ入力部２０１は、学習用データセットを入力する。学習用データセットとは、学習に用いられる構造化入力データＸｔｒａｉｎと、この構造化入力データＸｔｒａｉｎに対応する正解出力Ｙｔｒｕｅとの組で構成される学習用データの集合である。
【０１０７】
前処理部１０１及び変換処理部１０２は、学習用データ入力部２０１が入力した学習用データに含まれる各構造化入力データＸｔｒａｉｎに対して前処理（preprocessing）及び変換処理（ＤＰΩに相当する演算又は∇ＤＰΩに相当する演算）をそれぞれ行って、変換結果として、ＤＰΩ（θ）又は∇ＤＰΩ（θ）を計算する。
【０１０８】
パラメータ更新部２０２は、変換処理部１０２による変換結果ＤＰΩ（θ）又は∇ＤＰΩ（θ）と、前処理及び変換処理を行った構造化入力データＸｔｒａｉｎに対応する正解出力Ｙｔｒｕｅとに基づいて、所定の損失関数の微分値を計算し、この計算結果を用いてニューラルネットワークのパラメータを更新する。損失関数の微分値は、例えば、誤差逆伝播法等を用いて計算される。また、損失関数は、変換処理部１０２による変換結果がＤＰΩ（θ）である場合には上記の式（６）が、変換処理部１０２による変換結果が∇ＤＰΩ（θ）である場合には上記の式（７）が用いられる。
【０１０９】
このとき、パラメータ更新部２０２は、所定の条件を満たすまで、ニューラルネットワークのパラメータを繰り返し更新する。この所定の条件は、ニューラルネットワークの学習が収束したか否かを判定するものであり、例えば、損失関数の値が所定の閾値以下となったか否か、所定の繰り返し回数に達したか否か等である。
【０１１０】
パラメータ更新部２０２は、所定の条件を満たした場合、例えば、ニューラルネットワークのパラメータの値を出力して処理を終了する。
【０１１１】
＜変換装置１００の動作の具体例１＞
以降では、変換装置１００の動作の具体例１として、変換処理部１０２がビタビアルゴリズム（Viterbi Algorithm）に相当する演算を行う場合について説明する。ビタビアルゴリズムは、動的計画法に用いられるアルゴリズムの中で最も有名な例の１つであり、各時刻において或る状態から別の状態に所定の確率で遷移するような状態遷移モデルの下で、入力系列に対する状態系列のうち、尤もらしい状態系列を出力系列として求めるアルゴリズムである。各状態をノード、状態から状態への遷移を有向エッジ、状態から状態に遷移する確率を重みとすれば、上記の状態遷移モデルは、重み付き有向非巡回グラフ（ＤＡＧ）で表すことができる。この場合、状態系列は、重み付き有向非巡回グラフ上の開始ノードから終了ノードまでの経路として表すことができる。
【０１１２】
したがって、構造化入力データＸを入力系列Ｘ＝（ｘ１，ｘ２，・・・，ｘＴ）とした場合、ビタビアルゴリズムでは、例えば、この入力系列Ｘに対する状態系列ｙ＝（ｙ１，ｙ２，・・・，ｙＴ）のうち、尤もらしい状態系列ｙ（すなわち、有向非巡回グラフ上の尤もらしい経路ｙ）を解（出力系列）として求めることになる。ここで、各ｘｔ（ｔ＝１，２，・・・，Ｔ）はＤ次元の実ベクトル、各ｙｔ（ｔ＝１，２，・・・，Ｔ）は［Ｓ］の元であるとする。なお、［Ｓ］は、集合｛１，・・・，Ｓ｝を表す。
【０１１３】
具体的には、例えば、入力系列Ｘとして各ｘｔの各々が単語である単語系列Ｘを、出力系列ｙとして各ｘｔに対応するタグｙｔの系列を考えることができる。この場合、ビタビアルゴリズムは、入力系列Ｘに対して品詞タグ付け（Part-of-Speech Tagging）を行う処理と考えることができる。
【０１１４】
ここで、時刻ｔにおいてノードｊからノードｉへ遷移する場合をｙｔ，ｉ，ｊ＝１、それ以外の場合をｙｔ，ｉ，ｊ＝０とすれば、状態系列ｙは、（ｔ，ｉ，ｊ）成分の要素がｙｔ，ｉ，ｊであるＴ×Ｓ×ＳのバイナリテンソルＹで表すことができる。
【０１１５】
また、時刻ｔにおいてノードｊからノードｉに遷移する確率をθｔ，ｉ，ｊとして、（ｔ，ｉ，ｊ）成分の要素がθｔ，ｉ，ｊであるＴ×Ｓ×Ｓの実テンソルをθとする。このθは、例えばＢＬＳＴＭ等を用いて前処理部１０１により求められる。すなわち、この場合、変換装置１００の前処理部１０１は、例えばＢＬＳＴＭによりＴ×Ｓ×Ｓの実テンソルθを求めることになる。
【０１１６】
すると、フロベニウス内積＜Ｙ，θ＞は、状態系列ｙが表す経路に沿って各エッジの重みθｔ，ｉ，ｊを足し合わせた総和に相当する。この様子を図３に示す。図３に示す例では、入力系列をＸ＝（ｘ１，ｘ２，ｘ３）＝（ｔｈｅ，ｂｏａｔ，ｓａｎｋ）、状態系列をｙ＝（ｙ１，ｙ２，ｙ３）、ｙｔ∈｛ＮＯＵＮ，ＶＥＲＢ，ＤＥＴ｝とした場合に、この入力系列Ｘに対する状態系列ｙのうち、時刻ｔ＝１でノード１からノード３、時刻ｔ＝２でノード３からノード１、時刻ｔ＝３でノード３からノード２に遷移したときの状態系列ｙを表している。このとき、図３に示すように、フロベニウス内積＜Ｙ，θ＞は、＜Ｙ，θ＞＝θ１，３，１＋θ２，１，３＋θ３，２，１と表される。
【０１１７】
ここで、このフロベニウス内積＜Ｙ，θ＞＝θ１，３，１＋θ２，１，３＋θ３，２，１が最大スコアであれば、図３に示す経路ｙが最尤経路（すなわち、ビタビアルゴリズムの解となる出力系列）であり、このときの経路ｙは、単語ｘ１＝「ｔｈｅ」に対して品詞ｙ１＝「ＤＥＴ」（限定詞）、単語ｘ２＝「ｂｏａｔ」に対して品詞ｙ２＝「ＮＯＵＮ」（名詞）、単語ｘ３＝「ｓａｎｋ」に対して品詞ｙ３＝「ＶＥＲＢ」（動詞）が対応付けられることを表している。
【０１１８】
なお、Ω＝−Ｈ（ｎｅｇａｔｉｖｅ  ｅｎｔｒｏｐｙ）とすれば、以下の参考文献３に開示されているｌｉｎｅａｒ−ｃｈａｉｎ  ＣＲＦｓ（conditional random fields）を復元することができる。
【０１１９】
［参考文献３］
Lafferty, John, McCallum, Andrew, and Pereira, Fernando CN. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. of ICML, pp. 282-289, 2001.
ビタビアルゴリズムの解を求めるためには、変換装置１００の変換処理部１０２は、前処理部１０１で求めたＴ×Ｓ×Ｓの実テンソルθに基づき、以下に定義されるＶｉｔΩ（θ）と、このＶｉｔΩ（θ）から計算される∇ＶｉｔΩ（θ）とを計算すれば良い。
【０１２０】
【数３７】
2020009178.tif 000039
ここで、ｖｔ（θ）（ｔ＝１，・・・，Ｔ）は、ｖｔ（θ）＝（ｖｔ，１（θ），・・・，ｖｔ，Ｓ（θ））である。また、ｖｔ（θ）のｉ番目の要素ｖｔ，ｉ（θ）は、以下で定義される。
【０１２１】
【数３８】
2020009178.tif 000040
なお、ＶｉｔΩ（θ）は、任意のΩに対して凸関数となる。
【０１２２】
ここで、ＶｉｔΩ（θ）は、以下のＳｔｅｐ２−１〜Ｓｔｅｐ２−３の手順（順方向の手順）により計算することができる。また、∇ＶｉｔΩ（θ）は、以下のＳｔｅｐ２−１〜Ｓｔｅｐ２−３の手順が行われた後に、以下のＳｔｅｐ３−１〜Ｓｔｅｐ３−２の手順（逆方向の手順）により計算することができる。なお、以下のＳｔｅｐ２−１〜Ｓｔｅｐ２−３及びＳｔｅｐ３−１〜Ｓｔｅｐ３−２では、Ｑを（Ｔ＋１）×Ｔ×Ｓのテンソル、Ｕを（Ｔ＋１）×Ｓの行列、すなわち、
【０１２３】
【数３９】
2020009178.tif 000041
とする。また、θ∈ＲＴ×Ｎ×Ｎは所与であるものとする。
【０１２４】
Ｓｔｅｐ２−１：ｖ０＝０∈ＲＳとする。
【０１２５】
Ｓｔｅｐ２−２：ｔ＝１，・・・，Ｔに対して、順に、各ｉ∈［Ｓ］に対する以下の計算を行う。
【０１２６】
【数４０】
2020009178.tif 000042
Ｓｔｅｐ２−３：上記で計算されたｖＴ＝（ｖＴ，１，・・・，ｖＴ，Ｓ）を用いて、ｍａｘΩ（ｖＴ）を計算する。このｍａｘΩ（ｖＴ）がＶｉｔΩ（θ）である。また、後述するＳｔｅｐ３−１〜Ｓｔｅｐ３−３のために、
【０１２７】
【数４１】
2020009178.tif 000043
とする。
【０１２８】
Ｓｔｅｐ３−１：ｕＴ＋１＝（１，０，・・・，０）∈ＲＳとする。
【０１２９】
Ｓｔｅｐ３−２：ｔ＝Ｔ，・・・，０に対して、順に、各ｊ∈［Ｓ］に対する以下の計算を行う。
【０１３０】
【数４２】
2020009178.tif 000044
ここで、○は要素積（アダマール積）を表す。
【０１３１】
以上の手順により
【０１３２】
【数４３】
2020009178.tif 000045
が得られる。
【０１３３】
また、上記のＳｔｅｐ３−１〜Ｓｔｅｐ３−３の手順を行った後、以下のＳｔｅｐ４−１〜Ｓｔｅｐ４−５の手順により、与えられたＺ∈ＲＴ×Ｓ×Ｓに対して、＜∇ＶｉｔΩ（θ），Ｚ＞及び∇２ＶｉｔΩ（θ）Ｚを計算することができる。なお、Ｓｔｅｐ４−１〜Ｓｔｅｐ４−３が順方向の手順、Ｓｔｅｐ４−４〜Ｓｔｅｐ４−５が逆方向の手順である。
【０１３４】
Ｓｔｅｐ４−１：まず、
【０１３５】
【数４４】
2020009178.tif 000046
とする。
【０１３６】
Ｓｔｅｐ４−２：ｔ＝１，・・・，Ｔに対して、順に、各ｉ∈［Ｓ］に対する以下の計算を行う。
【０１３７】
【数４５】
2020009178.tif 000047
Ｓｔｅｐ４−３：そして、以下を計算する。
【０１３８】
【数４６】
2020009178.tif 000048
Ｓｔｅｐ４−４：次に、
【０１３９】
【数４７】
2020009178.tif 000049
とする。
【０１４０】
Ｓｔｅｐ４−５：ｔ＝Ｔ，・・・，０に対して、順に、各ｉ∈［Ｓ］に対する以下の計算を行う。
【０１４１】
【数４８】
2020009178.tif 000050
以上の手順により
【０１４２】
【数４９】
2020009178.tif 000051
が得られる。
【０１４３】
＜変換装置１００の動作の具体例２＞
以降では、変換装置１００の動作の具体例２として、変換処理部１０２が動的時間伸縮法（ＤＴＷ：Dynamic Time Wrapping）に相当する演算を行う場合について説明する。動的時間伸縮法は、２つの時系列データの相関（類似度）を分析する場合等に用いられる。
【０１４４】
ＮＡを時系列データＡの系列長、ＮＢを時系列データＢの系列長とする。また、時系列データＡのｉ番目の観測値をａｉ、時系列データＢのｊ番目の観測値をｂｊとする。
【０１４５】
そして、ａｉとｂｊとが類似する場合はｙｉｊ＝１、そうでない場合はｙｉｊ＝０として、ｙｉｊを要素とするＮＡ×ＮＢのバイナリ行列Ｙを考えた場合、このバイナリ行列Ｙは、時系列データＡと時系列データＢとの対応関係（類似関係）を表すアラインメントＹである。
【０１４６】
また、θをＮＡ×ＮＢの行列として、θの各要素をθｉ，ｊとする。古典的な例としては、或る微分可能な距離尺度ｄを用いて、θｉ，ｊ＝ｄ（ａｉ，ｂｊ）である。このθは、変換装置１００の前処理部１０１により求められる。なお、θは、距離行列とも呼ばれる。
【０１４７】
すると、観測値の組（ａｉ，ｂｊ）をノードとして、アラインメントＹは、重み付き有向非巡回グラフ（ＤＡＧ）上の経路（パス）を表す。
【０１４８】
ここで、全ての単調アラインメント行列の集合を
【０１４９】
【数５０】
2020009178.tif 000052
とする。単調アラインメント行列とは、行列の左上（１，１）成分から右下（ＮＡ，ＮＢ）に至る後戻りしないパス、すなわち（ｉ，ｊ）ノードからは右、下、右下の何れかの成分へ向かうパスのみが許容されるような行列である。つまり、ｙｉｊ＝１である場合、ｙｉ＋１，ｊ，ｙｉ，ｊ＋１，ｙｉ＋１，ｊ＋１の少なくともいずれかは１となる。ＮＡ＝４及びＮＢ＝３とした場合における或る単調アラインメント行列Ｙが表す経路（パス）を図４に示す。図４に示す経路は、ａ１及びｂ１、ａ２及びｂ２、ａ３及びｂ２、ａ４及びｂ３がそれぞれ類似している場合を示している。すなわち、この場合の単調アラインメント行列Ｙは、ｙ１１、ｙ２２、ｙ３２及びｙ４３がそれぞれ１で、他の要素が０である行列で表される。
【０１５０】
上記の単調アラインメント行列Ｙを用いることで、フロベニウス内積＜Ｙ，θ＞は、単調アラインメント行列Ｙが表す経路に沿って各エッジの重みθｉ，ｊを足し合わせた総和に相当する。すなわち、このフロベニウス内積＜Ｙ，θ＞をアラインメントのコストに用いることができる。図４に示す経路では、フロベニウス内積＜Ｙ，θ＞は、＜Ｙ，θ＞＝θ１，１＋θ２，２＋θ２，３＋θ３，３＋θ３，４と表される。
【０１５１】
ここで、ｖｉ，ｊ（θ）をアラインメントの（ｉ，ｊ）成分（セル）のコストであるとすれば、ｖｉ，ｊ（θ）は、
【０１５２】
【数５１】
2020009178.tif 000053
と表すことができる。
【０１５３】
また、ｍｉｎΩ関数、勾配∇ｍｉｎΩ及びヘッセ行列∇２ｍｉｎΩをそれぞれ以下で定義及び導入する。
【０１５４】
【数５２】
2020009178.tif 000054
すると、尤もらしいアラインメントＹを求めるためには、変換装置１００の変換処理部１０２は、前処理部１０１で求めたＮＡ×ＮＢの距離行列θに基づき、以下に定義されたＤＴＷΩ（θ）と、このＤＴＷΩ（θ）から計算される∇ＤＴＷΩ（θ）とを計算すれば良い。
【０１５５】
【数５３】
2020009178.tif 000055
ここで、ＤＴＷΩ（θ）は、以下のＳｔｅｐ５−１〜Ｓｔｅｐ５−２の手順（順方向の手順）により計算することができる。また、∇ＤＴＷΩ（θ）は、以下のＳｔｅｐ６−１〜Ｓｔｅｐ６−２の手順（逆方向の手順）により計算することができる。なお、以下のＳｔｅｐ５−１〜Ｓｔｅｐ５−２及びＳｔｅｐ６−１〜Ｓｔｅｐ６−２では、Ｑを（ＮＡ＋１）×（ＮＢ＋１）×３のテンソル、Ｅを（ＮＡ＋１）×（ＮＢ＋１）の行列、すなわち、
【０１５６】
【数５４】
2020009178.tif 000056
とする。また、
【０１５７】
【数５５】
2020009178.tif 000057
は所与であるものとする。
【０１５８】
Ｓｔｅｐ５−１：ｖ０，０＝０とする。また、ｉ＝１，・・・，ＮＡ、ｊ＝１，・・・，ＮＢに対して、ｖｉ，０＝ｖ０，ｊ＝∞とする。
【０１５９】
Ｓｔｅｐ５−２：ｉ＝１，・・・，ＮＡ，ｊ＝１，・・・，ＮＢに対して、順に、以下の計算を行う。
【０１６０】
【数５６】
2020009178.tif 000058
Ｓｔｅｐ６−１：次に、ｉ＝１，・・・，ＮＡ，ｊ＝１，・・・．ＮＢに対して、
【０１６１】
【数５７】
2020009178.tif 000059
とする。
【０１６２】
Ｓｔｅｐ６−２：ｊ＝ＮＢ，・・・，１，ｉ＝ＮＡ，・・・，１対して、順に、以下の計算を行う。
【０１６３】
【数５８】
2020009178.tif 000060
以上の手順により
【０１６４】
【数５９】
2020009178.tif 000061
が得られる。
【０１６５】
また、上記のＳｔｅｐ５−１〜Ｓｔｅｐ５−２の手順を行った後、以下のＳｔｅｐ７−１〜Ｓｔｅｐ７−４の手順により、与えられた
【０１６６】
【数６０】
2020009178.tif 000062
に対して、＜∇ＤＴＷΩ（θ），Ｚ＞及び∇２ＤＴＷΩ（θ）Ｚを計算することができる。なお、Ｓｔｅｐ７−１〜Ｓｔｅｐ７−２が順方向の手順、Ｓｔｅｐ７−３〜Ｓｔｅｐ７−４が逆方向の手順である。
【０１６７】
Ｓｔｅｐ７−１：まず、ｉ＝０，・・・，ＮＡ、ｊ＝１，・・・，ＮＢに対して、
【０１６８】
【数６１】
2020009178.tif 000063
とする。
【０１６９】
Ｓｔｅｐ７−２：ｉ＝１，・・・，ＮＢ，ｊ＝１，・・・，ＮＡに対して、順に、以下の計算を行う。
【０１７０】
【数６２】
2020009178.tif 000064
Ｓｔｅｐ７−３：次に、ｉ＝０，・・・，ＮＡ，ｊ＝１，・・・，ＮＢに対して、
【０１７１】
【数６３】
2020009178.tif 000065
とする。
【０１７２】
Ｓｔｅｐ７−４：ｊ＝ＮＢ，・・・，１，ｉ＝ＮＡ，・・・，１に対して、順に、以下の計算を行う。
【０１７３】
【数６４】
2020009178.tif 000066
以上の手順により
【０１７４】
【数６５】
2020009178.tif 000067
が得られる。
【０１７５】
＜本発明の効果＞
ここで、本発明の一例として上記の具体例２を用いた場合における効果について、図５を参照しながら説明する。図５は、本発明の効果の一例を示す図である。
【０１７６】
図５（ａ）は、Ωとしてｎｅｇａｔｉｖｅ  ｅｎｔｒｏｐｙを用いた場合におけるＤＴＷΩ（θ）＝−７．４９と、∇ＤＴＷΩ（θ）のヒートマップとを示している。一方で、図５（ｂ）は、Ωとしてｓｑｕａｒｅｄ  ２−ｎｏｒｍを用いた場合におけるＤＴＷΩ（θ）＝９．６１と、∇ＤＴＷΩ（θ）のヒートマップとを示している。ヒートマップは、セルの色が濃い程その値が大きいことを表し、セルが存在しない場所は値が０であることを表している。また、図５（ａ）及び図５（ｂ）におけるラインＬは、ｍａｘΩ関数ではなく、ｍａｘ関数を用いた場合におけるＤＴＷ（θ）に対応するアラインメントを表している。
【０１７７】
図５（ａ）及び図５（ｂ）に示すように、いずれの∇ＤＴＷΩ（θ）も、ＤＴＷ（θ）に対応するアラインメントを高い精度で近似できており、高い解釈性が得られていることがわかる。また、図５（ｂ）では、図５（ａ）と比べて、より高いスパース性も得られている。したがって、本発明の実施の形態では、微分可能で、かつ、解釈性が高い動的計画法の演算が実現できていることがわかる。
【０１７８】
なお、図５（ａ）及び図５（ｂ）でヒートマップとして示されている∇ＤＴＷΩ（θ）は、上述したように、誤差逆伝播法によって得られる。これにより、距離行列θの学習が可能となる。
【０１７９】
＜ハードウェア構成＞
最後に、本発明の実施の形態における変換装置１００及び学習装置２００のハードウェア構成について、図６を参照しながら説明する。図６は、本発明の実施の形態における変換装置１００及び学習装置２００のハードウェア構成の一例を示す図である。なお、変換装置１００及び学習装置２００は同様のハードウェア構成で実現可能であるため、以降では、主に、変換装置１００のハードウェア構成について説明する。
【０１８０】
図６に示すように、本発明の実施の形態における変換装置１００は、入力装置３０１と、表示装置３０２と、外部Ｉ／Ｆ３０３と、ＲＡＭ（Random Access Memory）３０４と、ＲＯＭ（Read Only Memory）３０５と、演算装置３０６と、通信Ｉ／Ｆ３０７と、補助記憶装置３０８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【０１８１】
入力装置３０１は、例えば、キーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置３０２は、例えば、ディスプレイ等であり、変換装置１００の処理結果を表示する。なお、変換装置１００及び学習装置２００は、入力装置３０１及び表示装置３０２の少なくとも一方を有していなくても良い。
【０１８２】
外部Ｉ／Ｆ３０３は、外部装置とのインタフェースである。外部装置には、記録媒体３０３ａ等がある。変換装置１００は、外部Ｉ／Ｆ３０３を介して、記録媒体３０３ａ等の読み取りや書き込みを行うことができる。記録媒体３０３ａには、変換装置１００が有する各機能部や学習装置２００が有する各機能部を実現する１以上のプログラム等が記録されていても良い。
【０１８３】
記録媒体３０３ａとして、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等が挙げられる。
【０１８４】
ＲＡＭ３０４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ３０５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ３０５には、例えば、ＯＳ（Operating System）に関する設定や通信ネットワークに関する設定等が格納されている。
【０１８５】
演算装置３０６は、例えば、ＣＰＵやＧＰＵ（Graphics Processing Unit）等であり、ＲＯＭ３０５や補助記憶装置３０８等からプログラムやデータをＲＡＭ３０４上に読み出して処理を実行する演算装置である。
【０１８６】
通信Ｉ／Ｆ３０７は、変換装置１００を通信ネットワークに接続するためのインタフェースである。変換装置１００が有する各機能部や学習装置２００が有する各機能部を実現する１以上のプログラムは、通信Ｉ／Ｆ３０７を介して、所定のサーバ装置等が取得（ダウンロード）されても良い。
【０１８７】
補助記憶装置３０８は、例えば、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置３０８に格納されているプログラムやデータには、例えば、ＯＳ、変換装置１００が有する各機能部や学習装置２００が有する各機能部を実現する１以上のプログラム等がある。
【０１８８】
本発明の実施の形態における変換装置１００及び学習装置２００は、図６に示すハードウェア構成を有することにより、上述した各種処理を実現することができる。
【０１８９】
本発明は、具体的に開示された上記の実施の形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１９０】
１００        変換装置
１０１        前処理部
１０２        変換処理部
２００        学習装置
２０１        学習用データ入力部
２０２        パラメータ更新部
【図１】
2020009178.tif 000072
【図２】
2020009178.tif 000073
【図３】
2020009178.tif 000074
【図４】
2020009178.tif 000075
【図５】
2020009178.tif 000076
【図６】
2020009178.tif 000077