(57)【特許請求の範囲】
【請求項１】
学習用入力部、パラメータ学習部、及び反復判定部を含むパラメータ学習装置におけるパラメータ学習方法であって、
前記学習用入力部が、複数の学習用文書の各々について、前記学習用文書内の文字列単位の各々と、ルートノードが前記学習用文書の全体を表し、かつ前記学習用文書のうちの少なくとも１つの文字列単位の系列の各々を各ノードとした階層構造を表し、かつ、前記文字列単位の系列間の修飾関係及び関係ラベルを表した、前記学習用文書の文字列単位の系列の各々の修辞構造に基づく修辞構造木であって、かつ前記学習用文書に対応する正解の前記修辞構造木の各々とを受け付けると、
前記パラメータ学習部が、
複数の学習用文書の各々について、
前記正解の修辞構造木に含まれる部分木の列と、前記部分木の列から抽出される特徴量ベクトルに対する重みベクトルを用いて選択される、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアのうち、前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアの差分が最大となる、前記正解の修辞構造木に含まれる部分木の列と、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアに含まれる前記部分木の列の各々から抽出される特徴ベクトルに基づいて、前記重みベクトルを更新するステップと、
前記反復判定部が、予め定められた回数だけ、前記パラメータ学習部による更新を繰り返すステップと、
を含むパラメータ学習方法。
【請求項２】
前記パラメータ学習部が前記重みベクトルを更新するステップは、
前記正解の修辞構造木に含まれる部分木の列に対して、前回選択された部分木の列において隣り合う部分木のペアを結合して生成される、前記正解の修辞構造木に含まれる部分木の列の集合のうち、前記部分木の列から抽出される前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアが最大となる部分木の列を選択し、
前記学習用文書に対応する前記修辞構造木の部分木の列に対して、前回選択された部分木の列の各々において、隣り合う部分木のペアを結合して生成される部分木の列の集合のうち、前記部分木の列から抽出される前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアが上位ｋ個となる部分木の列を選択し、
前記正解の修辞構造木に含まれる部分木の列に対して選択された部分木の列と、前記学習用文書に対応する前記修辞構造木の部分木の列に対して選択された上位ｋ個となる部分木の列の各々とのペアを生成することを繰り返し、
前記生成されたペアのうち、前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアの差分が最大となる、前記正解の修辞構造木に含まれる部分木の列と、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアに含まれる前記部分木の列の各々から抽出される特徴ベクトルに基づいて、前記重みベクトルを更新する請求項１記載のパラメータ学習方法。
【請求項３】
複数の学習用文書の各々について、前記学習用文書内の文字列単位の各々と、ルートノードが前記学習用文書の全体を表し、かつ前記学習用文書のうちの少なくとも１つの文字列単位の系列の各々を各ノードとした階層構造を表し、かつ、前記文字列単位の系列間の修飾関係及び関係ラベルを表した、前記学習用文書の文字列単位の系列の各々の修辞構造に基づく修辞構造木であって、かつ前記学習用文書に対応する正解の前記修辞構造木の各々とを受け付ける入力部と、
複数の学習用文書の各々について、
前記正解の修辞構造木に含まれる部分木の列と、前記部分木の列から抽出される特徴量ベクトルに対する重みベクトルを用いて選択される、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアのうち、前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアの差分が最大となる、前記正解の修辞構造木に含まれる部分木の列と、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアに含まれる前記部分木の列の各々から抽出される特徴ベクトルに基づいて、前記重みベクトルを更新するパラメータ学習部と、
予め定められた回数だけ、前記パラメータ学習部による更新を繰り返す反復判定部と、
を含むパラメータ学習装置。
【請求項４】
コンピュータを、請求項３に記載のパラメータ学習装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パラメータ学習方法、装置、及びプログラムに関する。
【背景技術】
【０００２】
修辞構造理論（Rhetorical Structure Theory：RST）とは文書の論理構造（修辞構造）を捉えるための理論である（例えば、非特許文献１）。ＲＳＴに基づく修辞構造を表わした木のことを修辞構造木（Rhetorical Structure Theory based Discourse Tree：ＲＳＴ−ＤＴ）と呼ぶ。ＲＳＴ−ＤＴの例を図９に示す。また、アノテーションが付与されていない生テキストに修辞構造木を付与することを談話構造解析と呼ぶ。与えられた文書は談話構造における最小の単位（Elementary Discourse Unit：ＥＤＵ）に分割される（図９ではｅ１からｅ１０までがそれに対応)。各ＥＤＵには衛星（Satellite：Ｓ）または核（Nuclues：Ｎ）というラベルが付与され、Ｓは必ずＮを修飾するという関係がある。また、ＳとＮ、ＮとＮの間には修辞関係を表わすラベルが付与される。例えば、ｅ１とｅ２の間には「Background」という関係ラベルが付与される。
【０００３】
ＲＳＴ−ＤＴでは文書全体が一つのノードになるまで、ノード間に付与されたＮまたはＳのラベル、修辞関係のラベルを一つのノードとし、ラベルの付与とノードの生成を再帰的に行なう。Ｒｏｏｔは文書全体を表わす仮想的なノードである。
【０００４】
文書が与えられた際にＲＳＴ−ＤＴへと解析するアルゴリズムの代表的なものとしてＨＩＬＤＡ（例えば、非特許文献２）がある。ＨＩＬＤＡは貪欲法を用いた最易優先探索手法の一つであり、以下の手続きを用いて与えられた文をＲＳＴ−ＤＴへと解析する。
【０００５】
（ステップ１）与えられた文書をＥＤＵに区切る。
【０００６】
（ステップ２）隣り合うノードの中でどれが最も結合しやすいかSupport Vector Machine を用いて決定し、ラベルを付与した上で隣り合うノードを一つのノードに結合する。
【０００７】
（ステップ３）全体が一つのノードであれば結合された木を返し、そうでなければステップ２へ戻る。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】William C，Mann and Sandra A. Thompson、“Rhetorical structure theory: Toward a functional theory of text organization”、1988、Text,8(3)、ｐ.243―281
【非特許文献２】H. Hernault, H. Prendinger, David A. duVerle, and M. Ishizuka、“HILDA: A Discourse Parser Using Support Vector Machine Classification”、2010、In Dialogue & Discourse, 2010(3)、p.1-33
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、ＨＩＬＤＡに代表される従来の談話構造解析技術は、探索誤りにあまり頑健ではない。例えば、上記図９においてｅ５とｅ６との間の関係を「Elaboration」と付与してしまうと、さらにｅ４と結合した際に修辞構造ラベル「Contrast」を正しく付与できなくなる恐れがある。
【００１０】
本発明は、上記の事情を鑑みてなされたもので、談話構造解析を精度よく行うためのパラメータを得ることができるパラメータ学習方法、装置、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために本発明のパラメータ学習方法は、学習用入力部、パラメータ学習部、及び反復判定部を含むパラメータ学習装置におけるパラメータ学習方法であって、前記学習用入力部が、複数の学習用文書の各々について、前記学習用文書内の文字列単位の各々と、ルートノードが前記学習用文書の全体を表し、かつ前記学習用文書のうちの少なくとも１つの文字列単位の系列の各々を各ノードとした階層構造を表し、かつ、前記文字列単位の系列間の修飾関係及び関係ラベルを表した、前記学習用文書の文字列単位の系列の各々の修辞構造に基づく修辞構造木であって、かつ前記学習用文書に対応する正解の前記修辞構造木の各々とを受け付けると、前記パラメータ学習部が、複数の学習用文書の各々について、前記正解の修辞構造木に含まれる部分木の列と、前記部分木の列から抽出される特徴量ベクトルに対する重みベクトルを用いて選択される、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアのうち、前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアの差分が最大となる、前記正解の修辞構造木に含まれる部分木の列と、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアに含まれる前記部分木の列の各々から抽出される特徴ベクトルに基づいて、前記重みベクトルを更新するステップと、前記反復判定部が、予め定められた回数だけ、前記パラメータ学習部による更新を繰り返すステップと、を含む。
【００１２】
本発明のパラメータ学習装置は、複数の学習用文書の各々について、前記学習用文書内の文字列単位の各々と、ルートノードが前記学習用文書の全体を表し、かつ前記学習用文書のうちの少なくとも１つの文字列単位の系列の各々を各ノードとした階層構造を表し、かつ、前記文字列単位の系列間の修飾関係及び関係ラベルを表した、前記学習用文書の文字列単位の系列の各々の修辞構造に基づく修辞構造木であって、かつ前記学習用文書に対応する正解の前記修辞構造木の各々とを受け付ける入力部と、複数の学習用文書の各々について、前記正解の修辞構造木に含まれる部分木の列と、前記部分木の列から抽出される特徴量ベクトルに対する重みベクトルを用いて選択される、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアのうち、前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアの差分が最大となる、前記正解の修辞構造木に含まれる部分木の列と、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアに含まれる前記部分木の列の各々から抽出される特徴ベクトルに基づいて、前記重みベクトルを更新するパラメータ学習部と、予め定められた回数だけ、前記パラメータ学習部による更新を繰り返す反復判定部と、を含んで構成されている。
【００１３】
また、本発明の前記パラメータ学習部は、前記正解の修辞構造木に含まれる部分木の列に対して、前回選択された部分木の列において隣り合う部分木のペアを結合して生成される、前記正解の修辞構造木に含まれる部分木の列の集合のうち、前記部分木の列から抽出される前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアが最大となる部分木の列を選択し、前記学習用文書に対応する前記修辞構造木の部分木の列に対して、前回選択された部分木の列の各々において、隣り合う部分木のペアを結合して生成される部分木の列の集合のうち、前記部分木の列から抽出される前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアが上位ｋ個となる部分木の列を選択し、前記正解の修辞構造木に含まれる部分木の列に対して選択された部分木の列と、前記学習用文書に対応する前記修辞構造木の部分木の列に対して選択された上位ｋ個となる部分木の列の各々とのペアを生成することを繰り返し、前記生成されたペアのうち、前記特徴量ベクトルと前記重みベクトルとを用いて算出されるスコアの差分が最大となる、前記正解の修辞構造木に含まれる部分木の列と、前記学習用文書に対応する前記修辞構造木の部分木の列とのペアに含まれる前記部分木の列の各々から抽出される特徴ベクトルに基づいて、前記重みベクトルを更新するようにすることができる。
【００１４】
本発明のプログラムは、コンピュータを、本発明の談話構造解析装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１５】
以上説明したように、本発明のパラメータ学習方法、装置、及びプログラムによれば、複数の学習用文書の各々について、正解の修辞構造木に含まれる部分木の列と、部分木の列から抽出される特徴量ベクトルに対する重みベクトルを用いて選択される、学習用文書に対応する修辞構造木の部分木の列とのペアのうち、特徴量ベクトルと重みベクトルとを用いて算出されるスコアの差分が最大となる、正解の修辞構造木に含まれる部分木の列と、学習用文書に対応する修辞構造木の部分木の列とのペアに含まれる部分木の列の各々から抽出される特徴ベクトルに基づいて、重みベクトルを更新することにより、談話構造解析を精度よく行うためのパラメータを得ることができる、という効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態の談話構造解析装置の一構成例を示すブロック図である。
【図２】談話構造解析のアルゴリズムの一例を示す図である。
【図３】本発明の実施の形態のパラメータ学習装置の一構成例を示すブロック図である。
【図４】スコアが最大となるペアを生成するアルゴリズムの一例を示す図である。
【図５】重みベクトルｗを学習するアルゴリズムの一例を示す図である。
【図６】本発明の実施の形態のパラメータ学習装置における学習処理ルーチンの内容を示すフローチャートである。
【図７】本発明の実施の形態のパラメータ学習装置における最大ペア算出処理ルーチンの内容を示すフローチャートである。
【図８】本発明の実施の形態の談話構造解析装置における解析処理ルーチンの内容を示すフローチャートである。
【図９】修辞構造に基づく修辞構造木（ＲＳＴ−ＤＴ）を説明するための説明図である。
【発明を実施するための形態】
【００１７】
＜概要＞
まず、本発明の実施の形態の概要について説明する。本発明の実施の形態は、与えられた文書中の文法的な要素間の談話構造の解析に関する。この技術はアノテーションが付与されていない文書全体の文法的な要素の間の談話構造を木として解析する技術である。本発明の実施の形態のポイントは、談話構造解析における最易優先探索をビーム探索に拡張し、探索誤りに頑健にした点と、最易優先探索をビーム探索に拡張してパラメータを学習する点である。
【００１８】
本発明に係る実施の形態は、談話構造をより正確に捉えるためにビーム探索を用いた談話構造解析を行なう。既存手法であるＨＩＬＤＡは貪欲法に基づいた方法であり、ある時点での決定（例えば、上記図９におけるｅ５とｅ６とを結合し、「Evidence」のラベルを付与する、など） を誤るとそれ以降の決定にも悪影響を及ぼす恐れがある。そこで本発明の実施の形態では、貪欲法であるＨＩＬＤＡにビーム探索を用いることで探索誤りを減らす。本発明の実施の形態は、最適なパラメータを学習する段階と、最適なパラメータを使って入力された文書の談話構造を解析する段階との二つに分かれる。
【００１９】
まず、最適なパラメータを学習する段階について説明する。この段階では、談話構造アノテーション済みの文書から抽出された特徴量ベクトルと初期パラメータをパラメータ学習部の入力とする。パラメータ学習部では談話構造解析を行なうのに最適なパラメータを学習し、そのパラメータを学習済みパラメータとして出力する。
【００２０】
次に、最適なパラメータを使って入力された文書の談話構造を解析する段階について説明する。この段階では、入力された文書を、ＥＤＵの単位に分割する。次にＥＤＵの列から特徴量ベクトルを抽出し、前段階で得られた学習済みパラメータと共に談話構造解析部に渡される。談話構造解析部では、それらを元に入力された文書に対し、談話構造解析の結果として、ＲＳＴ−ＤＴを出力する。
【００２１】
ここで、ＲＳＴ−ＤＴとは、ルートノードが文書の全体を表し、かつ文書のうちの少なくとも１つの文字列単位の系列の各々を各ノードとした階層構造を表し、かつ、文字列単位の系列間の修飾関係及び関係ラベルを表した、文書の文字列単位の系列の各々の修辞構造に基づく修辞構造木である。
また、ＲＳＴ−ＤＴの文字列単位は、文書中の最小の単位（Elementary Discourse Unit：ＥＤＵ）に対応する。
【００２２】
＜談話構造解析装置のシステム構成＞
以下、図面を参照して本発明の実施の形態を詳細に説明する。図１は、本発明の実施の形態の談話構造解析装置１００を示すブロック図である。談話構造解析装置１００は、ＣＰＵと、ＲＡＭと、談話構造解析処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【００２３】
本実施の形態の談話構造解析装置１００は、図１に示すように、入力部１０と、パラメータデータベース２０と、演算部３０と、出力部４０とを備えている。
【００２４】
談話構造解析装置１００では、解析対象の文書が入力されると、当該文書の談話構造解析を行う。
【００２５】
入力部１０は、解析対象の文書の入力を受け付ける。なお、入力される文書は、少なくとも１文を含む文書である。
【００２６】
パラメータデータベース２０には、後述するパラメータ学習装置２００によって学習された重みベクトルｗが格納されている。
【００２７】
演算部３０は、入力部１０により受け付けた、解析対象の文書について談話構造解析を行う。また、演算部３０は、ＥＤＵ分割部３２と、特徴抽出部３４と、談話構造解析部３６とを備えている。
【００２８】
ＥＤＵ分割部３２は、入力部１０により受け付けた解析対象の文書をＥＤＵに分割する。例えば、ＥＤＵ分割部３２は、文書中の各単語間でＳＶＭなどの分類器を用いて、区切れるか区切れないかを判断させ、文書をＥＤＵに分割したものを出力する。
【００２９】
特徴抽出部３４は、ＥＤＵ分割部３２によって得られたＥＤＵの列である部分木の列、又は後述する談話構造解析部３６によって生成された部分木の列から、特徴量ベクトルを抽出する。例えば、特徴抽出部３４は、ＲＳＴ−ＤＴの部分木の列Ｓから２つのＲＳＴ−ＤＴの部分木Ｓｉ、Ｓｉ＋１を結合する際の特徴量ベクトルをｆ（Ｓ）とする。特徴量ベクトルのうち、代表的なものを以下に挙げる。
【００３０】
（１）ＲＳＴ−ＤＴの部分木Ｓｉに含まれる単語数が５以下であるか。
（２）ＲＳＴ−ＤＴの部分木Ｓｉ、Ｓｉ＋１が同じ文に含まれるか。
（３）ＲＳＴ−ＤＴの部分木Ｓｉの先頭が「Because」で始まるか。
（４）ＲＳＴ−ＤＴの部分木Ｓｉ、Ｓｉ＋１が含むＥＤＵの個数。
（５）ＲＳＴ−ＤＴの部分木Ｓｉの主辞の品詞が動詞であるか。
（６）ＲＳＴ−ＤＴの部分木Ｓｉ＋１の一番上のノードの修辞関係ラベルが「Evidence」であるか。
【００３１】
例えば、上記図９において、ＲＳＴ−ＤＴの部分木の列［ｅ１,ｅ２,ｅ３,ｅ４,ｅ５−６,ｅ７,ｅ８,ｅ９,ｅ１０］をＳとし、ｅ４とｅ５−６を結合する際の特徴量がどのようなものになるかを説明する。ここで、ｅ５−６はｅ５とｅ６とを修辞構造ラベル「Evidence」で結合したノードを表わす。ｅ４の実際のテキストは「Only the midday sun at tropical latitudes is warm enough to thaw ice on occasion,」、ｅ５−６の実際のテキストは「but any liquid water formed that way would evaporate almost instantly because of the low atmospheric pressure.」であるとする。このとき、ｅ４とｅ５−６を結合する際の特徴量（関係ラベルは「Contrast」）は
【００３２】
（１）ｅ４に含まれる単語数は１６個なので、単語数は５個より大きい。
（２）ｅ４とｅ５−６は同じ文に含まれる。
（３）ｅ４の先頭は「Because」で始まらない。
（４）ｅ４とｅ５−６が含むＥＤＵの個数は３個。
（５）ｅ４の主辞の品詞が動詞である。
（６）ｅ５−６の一番上のノードの修辞関係ラベルは「Evidence」である。
であることからｆ（Ｓ）＝［０，１，０，３，１，１]となる。
【００３３】
談話構造解析部３６は、ＥＤＵの列である部分木の列又は前回生成された部分木の列に基づき生成される、複数の部分木の列の各々について、パラメータデータベース２０に格納された重みベクトルｗと、特徴抽出部３４によって抽出された特徴量ベクトルｆ（Ｓ）とに基づいて、部分木の列に対するスコアを算出する。そして、談話構造解析部３６は、複数の部分木の列の各々に対するスコアの各々に基づいて、スコアが上位ｋ個となる部分木の列の各々を配列ｂｅａｍに格納する。
【００３４】
具体的には、談話構造解析部３６は、以下の式（１）に示す関数ｅｘｐａｎｄに従って、ＲＳＴ−ＤＴの部分木の列から新たにＲＳＴ−ＤＴの部分木の列を列挙する。
【００３５】
【数１】
0006291440.tif 000002
【００３６】
ここで、修辞関係ラベルの集合をＬ、ＲＳＴ−ＤＴの部分木を含む列をＳ、核または衛星のペアの集合をＮＳ＝｛（Nucleus，Satellite），（Satellite，Nucleus），（Nucleus，Nucleus）｝と定義する。関数ｂｕｉｌｄは入力として、Ｓとインデックスｉ∈｛１，…，length(S)−１｝、修辞関係ラベルｌ∈Ｌ，核または衛星のペア（ｎｓ１，ｎｓ２）∈ＮＳを受け取る。また、関数ｂｕｉｌｄは出力として、２つのＲＳＴ−ＤＴの部分木Ｓｉ、Ｓｉ＋１を結合した新たなＲＳＴ−ＤＴの部分木を返す。その際に修辞関係ラベルｌと核または衛星とのペアを付与する。
【００３７】
談話構造解析部３６の具体的な処理の内容を表す擬似コードを図２に示す。関数ｔｏｐｋ（Ｚ）はＲＳＴ−ＤＴの部分木の列の集合（Ｚ）から、スコア上位ｋ個の候補を保持する関数である。それぞれのＲＳＴ−ＤＴの部分木の列ｚ∈Ｚは、重みベクトルｗと、ｚから抽出された特徴量ベクトルとの内積をスコアとして保持する。
【００３８】
上記図２に示すＡｌｇｏｒｉｔｈｍ１は重みベクトルｗとＥＤＵに分割された文書ｘ＝［ｅ１，ｅ２，・・・，ｅｎ］を入力とする。談話構造解析部３６では、関数ｅｘｐａｎｄで部分木の列の候補を展開しながら、以下の式（２）に従って、配列ｂｅａｍに、スコア上位ｋ個の部分木の列の候補を保持する。なお、配列ｂｅａｍは２次元配列であり、ｂｅａｍ［ｉ］には、スコアが上位ｉ番目の部分木の列が格納された配列が格納される。すなわち、ｂｅａｍ［ｉ］［ｊ］には、スコアが上位ｉ番目の部分木の列のうち、ｊ番目の部分木が格納される。
【００３９】
【数２】
0006291440.tif 000003
【００４０】
最終的に得られたｂｅａｍ［０］［０］に、最もスコアが高い１つの木、すなわちＲＳＴ−ＤＴが格納される。また、談話構造解析部３６は、最終的に得られたｂｅａｍ［０］［０］を、解析結果となるＲＳＴ−ＤＴとして出力する。
【００４１】
出力部４０は、談話構造解析部３６で出力されたＲＳＴ−ＤＴを解析結果として出力する。
【００４２】
重みベクトルｗが既知であれば、上記図２に示したＡｌｇｏｒｉｔｈｍ１を用いてビーム探索を用いた最易探索に基づく談話構造解析を行なうことができる。しかし、重みベクトルｗは既知ではない。そこで、本実施の形態では、構造化パーセプトロンに基づき、重みベクトルｗを求める。構造化パーセプトロンは学習アルゴリズムの一例である。
【００４３】
＜パラメータ学習装置のシステム構成＞
図３は、本発明の実施の形態のパラメータ学習装置２００を示すブロック図である。このパラメータ学習装置２００は、ＣＰＵと、ＲＡＭと、後述するパラメータ学習処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。
【００４４】
学習用入力部５０は、複数の学習データの入力を受け付ける。具体的には、学習用入力部５０は、複数の学習用文書の各々について、当該学習用文書内のＥＤＵの各々と、当該学習用文書に対応する正解のＲＳＴ−ＤＴとの組み合わせを、学習データとして受け付ける。
【００４５】
学習用演算部６０は、学習用入力部５０により受け付けた複数の学習データに基づいて、談話構造解析をするための重みベクトルｗを学習する。学習用演算部６０は、学習データベース６２と、学習用特徴抽出部６４と、パラメータ学習部６６と、反復判定部６８とを備えている。
【００４６】
学習データベース６２には、学習用入力部５０により受け付けた複数の学習データが格納される。
【００４７】
学習用特徴抽出部６４は、学習データベース６２に格納された複数の学習データの各々に含まれるＥＤＵの列である部分木の列、又は後述するパラメータ学習部６６によって生成された部分木の列から、特徴抽出部３４と同様に、特徴量ベクトルを抽出する。
【００４８】
パラメータ学習部６６は、学習データについて、正解のＲＳＴ−ＤＴに含まれる部分木の列と、部分木の列から抽出される特徴量ベクトルに対する重みベクトルｗを用いて選択される、当該学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアを生成する。そして、パラメータ学習部６６は、生成されたペアの各々のうち、特徴量ベクトルと重みベクトルｗとを用いて算出されるスコアの差分が最大となる、正解のＲＳＴ−ＤＴに含まれる部分木の列と、学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアに含まれる部分木の列の各々から抽出される特徴ベクトルに基づいて、重みベクトルｗを更新する。パラメータ学習部６６は、上記の処理を、複数の学習データの各々について繰り返す。
【００４９】
ここで、パラメータ学習部６６の処理の詳細について説明する。まず、パラメータ学習部６６は、図４に示すＡｌｇｏｒｉｔｈｍ２に従って、特徴量ベクトルと重みベクトルｗとを用いて算出されるスコアの差分が最大となる、正解のＲＳＴ−ＤＴに含まれる部分木の列と、学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアを選択する。
【００５０】
具体的には、パラメータ学習部６６は、以下の式（３）に従って、正解のＲＳＴ−ＤＴに含まれる部分木の列に対して、パラメータ学習部６６によって前回選択された部分木の列において隣り合う部分木のペアを１つだけ結合して生成される、正解のＲＳＴ−ＤＴに含まれる部分木の列の集合のうち、学習用特徴抽出部６４によって部分木の列から抽出される特徴量ベクトルｆ（ｏ）と、重みベクトルｗとを用いて算出されるスコアが最大となる部分木の列を選択する。ここで、正解のＲＳＴ−ＤＴに含まれる部分木の列をオラクルｏと称する。
【００５１】
【数３】
0006291440.tif 000004
【００５２】
次に、パラメータ学習部６６は、上記式（２）に従って、学習用文書に対応するＲＳＴ−ＤＴの部分木の列に対して、前回選択された部分木の列の各々において、隣り合う部分木のペアを結合して生成される部分木の列の集合のうち、部分木の列から抽出される特徴量ベクトルｆ（Ｓ）と重みベクトルｗとを用いて算出されるスコアが上位ｋ個となる部分木の列を選択する。
【００５３】
次に、パラメータ学習部６６は、以下の式（４）に従って、正解のＲＳＴ−ＤＴに含まれる部分木の列に対して選択された部分木の列と、学習用文書に対応するＲＳＴ−ＤＴの部分木の列に対して選択された上位ｋ個となる部分木の列の各々とのペアを生成する。
【００５４】
【数４】
0006291440.tif 000005
【００５５】
パラメータ学習部６６は、正解のＲＳＴ−ＤＴに含まれる部分木の列が、１つの木となるまで、上記の処理を繰り返す。
【００５６】
そして、パラメータ学習部６６は、以下の式（５）に従って、生成されたペアのうち、特徴量ベクトルと重みベクトルｗとを用いて算出されるスコアの差分が最大となる、正解のＲＳＴ−ＤＴに含まれる部分木の列と、学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアを選択する。
【００５７】
【数５】
0006291440.tif 000006
【００５８】
そして、パラメータ学習部６６は、上記式（５）に従って選択された正解のＲＳＴ−ＤＴに含まれる部分木の列と、学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアに含まれる部分木の列の各々から抽出される特徴ベクトルに基づいて、重みベクトルｗを更新する。パラメータ学習部６６における更新処理を、図５のＡｌｇｏｒｉｔｈｍ３に示す。
【００５９】
本実施の形態で用いる構造化パーセプトロンでは、１つの正解のＲＳＴ−ＤＴ（ｔ）が与えられる度に、オラクルｏと予測したＲＳＴ−ＤＴ（Ｓ）との組を元に重みを更新していく。オラクルｏと予測したＲＳＴ−ＤＴ（Ｓ）との組は、上記図４のＡｌｇｏｒｉｔｈｍ２に記した関数ｍａｘ−ｖｉｏｌａｔｉｏｎ−ｐａｉｒによって得られる。関数ｍａｘ−ｖｉｏｌａｔｉｏｎ−ｐａｉｒはオラクルとビーム探索で得られた予測したＲＳＴ−ＤＴの組をｐａｉｒｓに格納し、オラクルｏとビーム探索で得られた予測したＲＳＴ−ＤＴ（Ｓ）のスコアの差が最大になるような組を返す関数である。また、関数ｍａｘ−ｖｉｏｌａｔｉｏｎ−ｐａｉｒ内で使用されている関数ｅｘｐａｎｄ−ｏｒａｃｌｅは、関数ｅｘｐａｎｄ同様に候補を展開するが正解のＲＳＴ−ＤＴ（ｔ）に含まれている候補のみを返す関数である。構造化パーセプトロンでは、関数ｍａｘ−ｖｉｏｌａｔｉｏｎ−ｐａｉｒから得られる組を用いて重みベクトルｗを更新していく。また、構造化パーセプトロンでは、得られたＲＳＴ−ＤＴの部分木の組（ｏ，Ｓ）それぞれから抽出される特徴量ベクトルｆ（ｏ），ｆ（Ｓ）∈ＲＭの差分を足して重みベクトルを更新する。
【００６０】
反復判定部６８は、予め定められた回数だけ、上記パラメータ学習部６６による更新を繰り返す。パラメータ学習部６６は、予め定められた回数更新を繰り返した場合には、更新された重みベクトルｗをパラメータデータベース７０に格納する。
【００６１】
パラメータデータベース７０には、パラメータ学習部６６で更新された重みベクトルｗが格納される。
【００６２】
＜パラメータ学習装置の作用＞
次に、本実施の形態のパラメータ学習装置２００の作用について説明する。まず、複数の学習データがパラメータ学習装置２００に入力されると、パラメータ学習装置２００によって、入力された複数の学習データが、学習データベース６２へ格納される。そして、パラメータ学習装置２００によって、図６に示す学習処理ルーチンが実行される。
【００６３】
まず、ステップＳ１００において、学習データベース６２に格納された複数の学習データから１つの学習データを読み込み、設定する。
【００６４】
次に、ステップＳ１０２において、パラメータ学習部６６は、上記ステップＳ１００で設定された学習データについて、正解のＲＳＴ−ＤＴに含まれる部分木の列と、学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアを生成する。なお、学習用文書に対応するＲＳＴ−ＤＴの部分木の列は、部分木の列から抽出される特徴量ベクトルに対する重みベクトルｗを用いて選択される。当該ステップＳ１０２は、図７に示す最大ペア算出処理ルーチンによって実現される。
【００６５】
＜最大ペア算出処理ルーチン＞
まず、ステップＳ２００において、配列ｐａｉｒｓを初期化し、ｏｒａｃｌｅ及び配列ｂｅａｍに、上記ステップＳ１００で設定された学習データに含まれるＥＤＵの各々を格納した配列を格納する。
【００６６】
次に、ステップＳ２０２において、上記ステップＳ２００で設定されたｏｒａｃｌｅ又は前回のステップＳ２０６で更新されたｏｒａｃｌｅに格納されている配列の要素が１つであるか否かを判定する。ｏｒａｃｌｅに格納されている配列の要素が１つでない場合には、ステップＳ２０４へ進む。一方、後述するステップＳ２０４〜Ｓ２０６の処理によって最もスコアが高い１つの木が生成され、ｏｒａｃｌｅに格納されている配列の要素が１つである場合には、ステップＳ２１４へ進む。
【００６７】
ステップＳ２０４において、関数ｅｘｐａｎｄ−ｏｒａｃｌｅによって、学習データの正解のＲＳＴ−ＤＴに含まれる部分木の列に対して、前回のステップＳ２０６で更新されたｏｒａｃｌｅに格納されている部分木の列から、正解のＲＳＴ−ＤＴに含まれる、新たな部分木の列の各々を生成する。そして、学習用特徴抽出部６４は、新たに生成された部分木の列の各々から、特徴量ベクトルｆ（ｏ）を抽出する。
【００６８】
ステップＳ２０６において、上記ステップＳ２０４で生成された新たな部分木の列から、上記式（３）に従って、上記ステップＳ２０４で抽出された特徴量ベクトルｆ（ｏ）と、重みベクトルｗとを用いて算出されるスコアが最大となる部分木の列を選択し、ｏｒａｃｌｅに格納する。
【００６９】
ステップＳ２０８において、関数ｅｘｐａｎｄによって、学習データの学習用文書に対応するＲＳＴ−ＤＴの部分木の列に対して、前回のステップＳ２１０で更新されたｂｅａｍに格納された部分木の列の各々から、部分木の列の集合を生成する。そして、学習用特徴抽出部６４は、新たに生成された部分木の列の集合に含まれる部分木の列Ｓの各々について、特徴量ベクトルｆ（Ｓ）を抽出する。
【００７０】
ステップＳ２１０において、上記ステップＳ２０８で生成された部分木の列の集合から、上記式（２）に従って、上記ステップＳ２０８で抽出された特徴量ベクトルｆ（Ｓ）と重みベクトルｗとを用いて算出されるスコアが上位ｋ個となる部分木の列を選択し、配列ｂｅａｍに格納する。
【００７１】
ステップＳ２１２において、上記式（４）に従って、上記ステップＳ２０６で更新されたｏｒａｃｌｅに格納された部分木の列と、上記ステップＳ２１０で更新された配列ｂｅａｍに格納された部分木の列とのペアを各々生成し、配列ｐａｉｒｓに格納し、上記ステップＳ２０２へ戻る。
【００７２】
ステップＳ２１４において、上記式（５）に従って、上記ステップＳ２１２で配列ｐａｉｒｓに格納されたペアのうち、特徴量ベクトルと重みベクトルｗとを用いて算出されるスコアの差分が最大となる、正解のＲＳＴ−ＤＴに含まれる部分木の列と、学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアを出力して、最大ペア算出処理ルーチンを終了する。
【００７３】
次に学習処理ルーチンに戻り、ステップＳ１０４において、パラメータ学習部６６は、上記ステップＳ１０２で出力されたペアに基づいて、当該ペアに含まれる部分木の列の各々から抽出される特徴ベクトルに基づいて、重みベクトルｗを更新する。
【００７４】
ステップＳ１０６において、学習データベース６２に格納された複数の学習データの全てについて、上記ステップＳ１００〜ステップＳ１０４の処理を実行したか否かを判定する。学習データベース６２に格納された複数の学習データの全てについて、上記ステップＳ１００〜ステップＳ１０４の処理を実行した場合には、ステップＳ１０８へ進む。一方、上記ステップＳ１００〜ステップＳ１０４の処理を実行していない学習データが存在する場合には、ステップＳ１００へ戻る。
【００７５】
ステップＳ１０８において、上記ステップＳ１００〜ステップＳ１０６の処理を予め定められた回数繰り返したか否かを判定する。上記ステップＳ１００〜ステップＳ１０６の処理を予め定められた回数繰り返した場合には、ステップＳ１１０へ進む。一方、上記ステップＳ１００〜ステップＳ１０６の処理を予め定められた回数繰り返していない場合には、ステップＳ１００へ戻る。
【００７６】
そして、ステップＳ１１０において、上記ステップＳ１０４の処理で得られた重みベクトルｗをパラメータデータベース７０へ格納して、学習処理ルーチンを終了する。
【００７７】
＜談話構造解析装置の作用＞
次に、本実施の形態の談話構造解析装置１００の作用について説明する。まず、パラメータ学習装置２００のパラメータデータベース７０に記憶されている重みベクトルｗが、談話構造解析装置１００に入力されると、パラメータデータベース２０に格納される。そして、解析対象としての入力文書が談話構造解析装置１００に入力されると、談話構造解析装置１００によって、図８に示す解析処理ルーチンが実行される。
【００７８】
まず、ステップＳ３００において、入力部１０によって、解析対象の入力文書を受け付ける。
【００７９】
次に、ステップＳ３０２において、ＥＤＵ分割部３２によって、上記ステップＳ３００で受け付けた解析対象の入力文書をＥＤＵに分割する。
【００８０】
ステップＳ３０４において、談話構造解析部３６は、パラメータデータベース２０に格納された重みベクトルｗを読み込む。
【００８１】
ステップＳ３０６において、談話構造解析部３６は、上記ステップＳ３０２で得られたＥＤＵの各々を格納した配列を配列ｂｅａｍに格納する。
【００８２】
ステップＳ３０８において、談話構造解析部３６は、上記ステップＳ３０６で設定された配列ｂｅａｍ[０]又は前回のステップＳ３１２で更新された配列ｂｅａｍ[０]に格納されている配列の要素が１つであるか否かを判定する。配列ｂｅａｍ[０]に格納されている配列の要素が１つでない場合には、ステップＳ３１０へ進む。一方、後述するステップＳ３１０〜Ｓ３１２の処理によって配列ｂｅａｍ[０]に格納されている配列の要素が１つである場合には、ステップＳ３１４へ進む。
【００８３】
ステップＳ３１０において、談話構造解析部３６は、関数expandによって、上記ステップＳ３０６で設定された配列ｂｅａｍ又は前回のステップＳ３１２で更新された配列ｂｅａｍに格納された部分木の列の各々から、部分木の列の集合を生成する。そして、特徴抽出部３４は、生成された部分木の列の集合に含まれる部分木の列Ｓの各々について、特徴量ベクトルｆ（Ｓ）を抽出する。
【００８４】
ステップＳ３１２において、談話構造解析部３６は、上記式（２）に従って、上記ステップＳ３１０で抽出された特徴量ベクトルｆ（Ｓ）と重みベクトルｗとを用いて算出されるスコアが上位ｋ個となる部分木の列を選択し、配列ｂｅａｍに格納し、上記ステップ３０８へ戻る。
【００８５】
ステップＳ３１４において、上記ステップＳ３１２で更新された配列ｂｅａｍのうち、ｂｅａｍ［０］［０］に格納されているＲＳＴ−ＤＴを出力部４０により解析結果として出力し、解析処理ルーチンを終了する。
【００８６】
以上説明したように、本実施の形態のパラメータ学習装置によれば、複数の学習用文書の各々について、正解のＲＳＴ−ＤＴに含まれる部分木の列と、部分木の列から抽出される特徴量ベクトルに対する重みベクトルｗを用いて選択される、学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアのうち、特徴量ベクトルと重みベクトルｗとを用いて算出されるスコアの差分が最大となる、正解のＲＳＴ−ＤＴに含まれる部分木の列と、学習用文書に対応するＲＳＴ−ＤＴの部分木の列とのペアに含まれる部分木の列の各々から抽出される特徴ベクトルに基づいて、重みベクトルｗを更新することにより、談話構造解析を精度よく行うための重みベクトルｗを得ることができる。
【００８７】
本実施の形態の談話構造解析装置によれば、パラメータ学習装置によって得られた重みベクトルｗを用いて談話構造解析を行うことにより、談話構造解析を精度よく行うことができる。
【００８８】
また、本実施の形態のパラメータ学習装置及び談話構造解析装置を用いることで、ビーム探索に基づいた最易優先探索を行なうことで探索誤りに頑健な解析が可能となり、より高精度な談話構造解析が可能になる。
【００８９】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００９０】
例えば、本実施の形態では、文書中のＥＤＵをＲＳＴ−ＤＴの各ノードとした場合を例に説明したが、各ノードをＥＤＵ以外の文字列単位として表わすこともできる。その場合には、ＥＤＵ分割部３２によって、文書を当該文字列単位に分割し、当該文字列単位をノードとして表したＲＳＴ−ＤＴを構築する。
【００９１】
また、本実施の形態のパラメータ学習装置及び談話構造解析装置は、英語だけでなく日本語等の他の言語にも適用可能である。
【００９２】
また、学習データベース６２及びパラメータデータベース７０は、パラメータ学習装置の外部に設けられ、パラメータ学習装置とネットワークで接続されていてもよい。また、パラメータデータベース２０は、談話構造解析装置の外部に設けられ、談話構造解析装置とネットワークで接続されていてもよい。
【００９３】
また、入力部１０に入力される文書は、既に文又はＥＤＵに分割された形態であってもよい。その場合には、ＥＤＵ分割部３２の処理については省略する。
【００９４】
また、上記実施の形態では、パラメータ学習装置と談話構造解析装置とを別々の装置として構成する場合を例に説明したが、パラメータ学習装置と談話構造解析装置とを１つの装置として構成してもよい。
【００９５】
上述のパラメータ学習装置及び談話構造解析装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００９６】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００９７】
１０   入力部
２０，７０    パラメータデータベース
３０   演算部
３２   ＥＤＵ分割部
３４   特徴抽出部
３６   談話構造解析部
４０   出力部
５０   学習用入力部
６０   学習用演算部
６４   学習用特徴抽出部
６２   学習データベース
６６   パラメータ学習部
６８   反復判定部
１００ 談話構造解析装置
２００ パラメータ学習装置
【図１】
0006291440.tif 000007
【図２】
0006291440.tif 000008
【図３】
0006291440.tif 000009
【図４】
0006291440.tif 000010
【図５】
0006291440.tif 000011
【図６】
0006291440.tif 000012
【図７】
0006291440.tif 000013
【図８】
0006291440.tif 000014
【図９】
0006291440.tif 000015