(57)【要約】【課題】訓練データがなくても、精度よく、文書を表す木構造を構築できる。【解決手段】木構造推定部３２が、各文について、ＥＤＵベクトルの系列に基づいて、文に含まれるＥＤＵ系列を二つのスパンに分割することを再帰的に繰り返し、基本単位を単位とした木構造を出力し、各段落について、文ベクトルの系列に基づいて、段落に含まれる文系列を二つのスパンに分割することを再帰的に繰り返し、文を単位とした木構造を出力し、段落ベクトルの系列に基づいて、文書に含まれる段落系列を二つのスパンに分割することを再帰的に繰り返し、段落を単位とした木構造を出力する。木結合部３８が、基本単位を単位とした木構造と、文を単位とした木構造と、段落を単位とした木構造とを最終的に結合する。【選択図】図４
2020140464.tif 000002
【特許請求の範囲】
【請求項１】
文書について、前記文書の段落の系列への分割と、各段落に含まれる文の系列への分割と、各文に含まれる基本単位の系列への分割とを行う部分構造解析部と、
各文について、前記文に含まれる前記基本単位の系列の各基本単位を表すＥＤＵ（Ｅｌｅｍｅｎｔａｒｙ  Ｄｉｓｃｏｕｒｓｅ  Ｕｎｉｔ）ベクトルの系列に基づいて、前記文に含まれる前記基本単位の系列を二つのスパンに分割することを、前記スパンの各々が前記基本単位となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、基本単位を単位とした木構造を出力し、
各段落について、前記段落に含まれる前記文の系列の各文を表す文ベクトルの系列に基づいて、前記段落に含まれる前記文の系列を二つのスパンに分割することを、前記スパンの各々が前記文となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、文を単位とした木構造を出力し、
前記文書に含まれる前記段落の系列の各段落を表す段落ベクトルの系列に基づいて、前記文書に含まれる前記段落の系列を二つのスパンに分割することを、前記スパンの各々が前記段落となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、段落を単位とした木構造を出力する木構造推定部と、
前記基本単位を単位とした木構造と、前記文を単位とした木構造と、前記段落を単位とした木構造とを結合した木構造を出力する木結合部と、
を含む木構造解析装置。
【請求項２】
前記木構造推定部は、前記文に含まれる前記基本単位の系列を二つのスパンに分割する位置を決定する際に、前記分割する位置より左側の前記基本単位の系列に対するベクトルと、前記分割する位置より右側の前記基本単位の系列に対するベクトルとに基づいて計算される分割スコアに応じて、前記分割する位置を決定し、
前記段落に含まれる前記文の系列を二つのスパンに分割する位置を決定する際に、前記分割する位置より左側の前記文の系列に対するベクトルと、前記分割する位置より右側の前記文の系列に対するベクトルとに基づいて計算される分割スコアに応じて、前記分割する位置を決定し、
前記文書に含まれる前記段落の系列を二つのスパンに分割する位置を決定する際に、前記分割する位置より左側の前記段落の系列に対するベクトルと、前記分割する位置より右側の前記段落の系列に対するベクトルとに基づいて計算される分割スコアに応じて、前記分割する位置を決定する請求項１記載の木構造解析装置。
【請求項３】
前記文に含まれる前記基本単位の系列を二つのスパンに分割する位置を決定する際に計算される前記分割スコアは、前記分割する位置より左側の前記基本単位の系列に含まれる各基本単位のＥＤＵベクトルに基づいて計算されるベクトルと、前記分割する位置より右側の前記基本単位の系列に含まれる各基本単位のＥＤＵベクトルに基づいて計算されるベクトルとの類似度に基づいて計算され、
前記段落に含まれる前記文の系列を二つのスパンに分割する位置を決定する際に計算される前記分割スコアは、前記分割する位置より左側の前記文の系列に含まれる各文の文ベクトルに基づいて計算されるベクトルと、前記分割する位置より右側の前記文の系列に含まれる各文の文ベクトルに基づいて計算されるベクトルとの類似度に基づいて計算され、
前記文書に含まれる前記段落の系列を二つのスパンに分割する位置を決定する際に計算される前記分割スコアは、前記分割する位置より左側の前記段落の系列に含まれる各段落の段落ベクトルに基づいて計算されるベクトルと、前記分割する位置より右側の前記段落の系列に含まれる各段落の段落ベクトルに基づいて計算されるベクトルとの類似度に基づいて計算される請求項２記載の木構造解析装置。
【請求項４】
部分構造解析部が、文書について、前記文書の段落の系列への分割と、各段落に含まれる文の系列への分割と、各文に含まれる基本単位の系列への分割とを行い、
各文について、前記文に含まれる前記基本単位の系列の各基本単位を表すＥＤＵ（Ｅｌｅｍｅｎｔａｒｙ  Ｄｉｓｃｏｕｒｓｅ  Ｕｎｉｔ）ベクトルの系列に基づいて、前記文に含まれる前記基本単位の系列を二つのスパンに分割することを、前記スパンの各々が前記基本単位となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、基本単位を単位とした木構造を出力し、
各段落について、前記段落に含まれる前記文の系列の各文を表す文ベクトルの系列に基づいて、前記段落に含まれる前記文の系列を二つのスパンに分割することを、前記スパンの各々が前記文となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、文を単位とした木構造を出力し、
木構造推定部が、前記文書に含まれる前記段落の系列の各段落を表す段落ベクトルの系列に基づいて、前記文書に含まれる前記段落の系列を二つのスパンに分割することを、前記スパンの各々が前記段落となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、段落を単位とした木構造を出力し、
木結合部が、前記基本単位を単位とした木構造と、前記文を単位とした木構造と、前記段落を単位とした木構造とを結合した木構造を出力する
木構造解析方法。
【請求項５】
前記木構造推定部が、前記文に含まれる前記基本単位の系列を二つのスパンに分割する位置を決定する際に、前記分割する位置より左側の前記基本単位の系列に対するベクトルと、前記分割する位置より右側の前記基本単位の系列に対するベクトルとに基づいて計算される分割スコアに応じて、前記分割する位置を決定し、
前記段落に含まれる前記文の系列を二つのスパンに分割する位置を決定する際に、前記分割する位置より左側の前記文の系列に対するベクトルと、前記分割する位置より右側の前記文の系列に対するベクトルとに基づいて計算される分割スコアに応じて、前記分割する位置を決定し、
前記文書に含まれる前記段落の系列を二つのスパンに分割する位置を決定する際に、前記分割する位置より左側の前記段落の系列に対するベクトルと、前記分割する位置より右側の前記段落の系列に対するベクトルとに基づいて計算される分割スコアに応じて、前記分割する位置を決定する請求項４に記載の木構造解析方法。
【請求項６】
前記文に含まれる前記基本単位の系列を二つのスパンに分割する位置を決定する際に計算される前記分割スコアは、前記分割する位置より左側の前記基本単位の系列に含まれる各基本単位のＥＤＵベクトルに基づいて計算されるベクトルと、前記分割する位置より右側の前記基本単位の系列に含まれる各基本単位のＥＤＵベクトルに基づいて計算されるベクトルとの類似度に基づいて計算され、
前記段落に含まれる前記文の系列を二つのスパンに分割する位置を決定する際に計算される前記分割スコアは、前記分割する位置より左側の前記文の系列に含まれる各文の文ベクトルに基づいて計算されるベクトルと、前記分割する位置より右側の前記文の系列に含まれる各文の文ベクトルに基づいて計算されるベクトルとの類似度に基づいて計算され、
前記文書に含まれる前記段落の系列を二つのスパンに分割する位置を決定する際に計算される前記分割スコアは、前記分割する位置より左側の前記段落の系列に含まれる各段落の段落ベクトルに基づいて計算されるベクトルと、前記分割する位置より右側の前記段落の系列に含まれる各段落の段落ベクトルに基づいて計算されるベクトルとの類似度に基づいて計算される請求項５に記載の木構造解析方法。
【請求項７】
コンピュータに、
文書について、前記文書の段落の系列への分割と、各段落に含まれる文の系列への分割と、各文に含まれる基本単位の系列への分割とを行い、
各文について、前記文に含まれる前記基本単位の系列の各基本単位を表すＥＤＵ（Ｅｌｅｍｅｎｔａｒｙ  Ｄｉｓｃｏｕｒｓｅ  Ｕｎｉｔ）ベクトルの系列に基づいて、前記文に含まれる前記基本単位の系列を二つのスパンに分割することを、前記スパンの各々が前記基本単位となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、基本単位を単位とした木構造を出力し、
各段落について、前記段落に含まれる前記文の系列の各文を表す文ベクトルの系列に基づいて、前記段落に含まれる前記文の系列を二つのスパンに分割することを、前記スパンの各々が前記文となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、文を単位とした木構造を出力し、
前記文書に含まれる前記段落の系列の各段落を表す段落ベクトルの系列に基づいて、前記文書に含まれる前記段落の系列を二つのスパンに分割することを、前記スパンの各々が前記段落となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、段落を単位とした木構造を出力し、
前記基本単位を単位とした木構造と、前記文を単位とした木構造と、前記段落を単位とした木構造とを結合した木構造を出力する
ことを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造解析装置、方法、及びプログラムに係り、特に、文書の木構造を解析するための木構造解析装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
従来の文書構造解析技術は、Ｒｈｅｔｏｒｉｃａｌ Ｓｔｒｕｃｔｕｒｅ Ｔｈｅｏｒｙ （ＲＳＴ）に基づき、文書を、Ｅｌｅｍｅｎｔａｒｙ Ｄｉｓｃｏｕｒｓｅ Ｕｎｉｔ（ＥＤＵ）と呼ばれる文よりも小さい、節に相当するテキストユニットを終端記号(葉) とし、２つ以上のＥＤＵで構成されるスパンの役割を示すＮ/Ｓラベルを非終端記号とする２分木として表現する(図１)。なお、Ｎは系列の核であり、Ｓは系列の衛星をあらわす。こうした木構造を得るため、従来の多くの方法は、文書をＥＤＵの系列データとみなし、ＥＤＵをボトムアップに組み上げていくことで文書全体の木を構築する（たとえば、非特許文献１など）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】duVerle, David and Prendinger, Helmut, "A Novel Discourse Parser Based on Support Vector Machine Classification", Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pp 665-673, 2009
【発明の概要】
【発明が解決しようとする課題】
【０００４】
従来の方法は、文書中の文、段落といった明示的に利用できる構造を利用していない。さらに、正解の木構造を訓練データとして木の構築に必要なパラメタを学習している。
【０００５】
本発明は、上記事情を鑑みて成されたものであり、訓練データがなくても、精度よく、文書を表す木構造を構築できる木構造解析装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、第１の態様に係る木構造解析装置は、文書について、前記文書の段落の系列への分割と、各段落に含まれる文の系列への分割と、各文に含まれる基本単位の系列への分割とを行う部分構造解析部と、各文について、前記文に含まれる前記基本単位の系列の各基本単位を表すＥＤＵ（Ｅｌｅｍｅｎｔａｒｙ  Ｄｉｓｃｏｕｒｓｅ  Ｕｎｉｔ）ベクトルの系列に基づいて、前記文に含まれる前記基本単位の系列を二つのスパンに分割することを、前記スパンの各々が前記基本単位となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、基本単位を単位とした木構造を出力し、各段落について、前記段落に含まれる前記文の系列の各文を表す文ベクトルの系列に基づいて、前記段落に含まれる前記文の系列を二つのスパンに分割することを、前記スパンの各々が前記文となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、文を単位とした木構造を出力し、前記文書に含まれる前記段落の系列の各段落を表す段落ベクトルの系列に基づいて、前記文書に含まれる前記段落の系列を二つのスパンに分割することを、前記スパンの各々が前記段落となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、段落を単位とした木構造を出力する木構造推定部と、前記基本単位を単位とした木構造と、前記文を単位とした木構造と、前記段落を単位とした木構造とを結合した木構造を出力する木結合部と、を含んで構成されている。
【０００７】
第２の態様に係る木構造解析方法は、部分構造解析部が、文書について、前記文書の段落の系列への分割と、各段落に含まれる文の系列への分割と、各文に含まれる基本単位の系列への分割とを行い、各文について、前記文に含まれる前記基本単位の系列の各基本単位を表すＥＤＵ（Ｅｌｅｍｅｎｔａｒｙ  Ｄｉｓｃｏｕｒｓｅ  Ｕｎｉｔ）ベクトルの系列に基づいて、前記文に含まれる前記基本単位の系列を二つのスパンに分割することを、前記スパンの各々が前記基本単位となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、基本単位を単位とした木構造を出力し、各段落について、前記段落に含まれる前記文の系列の各文を表す文ベクトルの系列に基づいて、前記段落に含まれる前記文の系列を二つのスパンに分割することを、前記スパンの各々が前記文となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、文を単位とした木構造を出力し、木構造推定部が、前記文書に含まれる前記段落の系列の各段落を表す段落ベクトルの系列に基づいて、前記文書に含まれる前記段落の系列を二つのスパンに分割することを、前記スパンの各々が前記段落となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、段落を単位とした木構造を出力し、木結合部が、前記基本単位を単位とした木構造と、前記文を単位とした木構造と、前記段落を単位とした木構造とを結合した木構造を出力する。
【０００８】
第３の態様に係るプログラムは、コンピュータに、文書について、前記文書の段落の系列への分割と、各段落に含まれる文の系列への分割と、各文に含まれる基本単位の系列への分割とを行い、各文について、前記文に含まれる前記基本単位の系列の各基本単位を表すＥＤＵ（Ｅｌｅｍｅｎｔａｒｙ  Ｄｉｓｃｏｕｒｓｅ  Ｕｎｉｔ）ベクトルの系列に基づいて、前記文に含まれる前記基本単位の系列を二つのスパンに分割することを、前記スパンの各々が前記基本単位となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、基本単位を単位とした木構造を出力し、各段落について、前記段落に含まれる前記文の系列の各文を表す文ベクトルの系列に基づいて、前記段落に含まれる前記文の系列を二つのスパンに分割することを、前記スパンの各々が前記文となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、文を単位とした木構造を出力し、前記文書に含まれる前記段落の系列の各段落を表す段落ベクトルの系列に基づいて、前記文書に含まれる前記段落の系列を二つのスパンに分割することを、前記スパンの各々が前記段落となるまで再帰的に繰り返し、前記スパンの各々をノードとした二分木で表される、段落を単位とした木構造を出力し、前記基本単位を単位とした木構造と、前記文を単位とした木構造と、前記段落を単位とした木構造とを結合した木構造を出力することを実行させるためのプログラムである。
【発明の効果】
【０００９】
本発明の一態様に係る木構造解析装置、方法、及びプログラムによれば、訓練データがなくても、精度よく、文書を表す木構造を構築できる、という効果が得られる。
【図面の簡単な説明】
【００１０】
【図１】一般的な木構造の一例を示す図である。
【図２】ＥＤＵの系列、文の系列、及び段落の系列を２分割して木構造を構築する方法を説明するための図である。
【図３】非終端記号を用いない木構造の一例を示す図である。
【図４】本発明の実施の形態に係る木構造解析装置の構成を示すブロック図である。
【図５】ＥＤＵの系列を２分割して、ＥＤＵを葉とする木構造を構築する方法を説明するための図である。
【図６】文の系列を２分割して、文を葉とする木構造を構築する方法を説明するための図である。
【図７】段落の系列を２分割して、段落を葉とする木構造を構築する方法を説明するための図である。
【図８】木構造推定部の具体的な内部構成を示す図である。
【図９】分割スコアが最小となる分割点で系列を分割する方法を説明するための図である。
【図１０】木構造を結合する方法を説明するための図である。
【図１１】木構造解析装置として機能するコンピュータの一例の概略ブロック図である。
【図１２】本発明の実施の形態に係る木構造解析装置の木構造解析処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１２】
＜本発明の実施の形態の概要＞
本発明の実施の形態では、文、段落という構造を利用し、文書は段落の系列、段落は文の系列、文はＥＤＵの系列としてとらえ、それぞれの系列を独立に２分割していくことで文書全体の構造木を構築する(図２)。系列の分割は、分割点に対する左右の系列間の類似スコアに基づくため、訓練データを必要としない。なお、本発明の実施の形態の目的は木構造の推定であり(図３)、木の非終端記号ラベル(Ｎ/Ｓ)の推定を明示的に行わない。ラベル推定は既存のテキスト分類手法などを利用すれば推定可能である。
【００１３】
＜本発明の実施の形態に係る木構造解析装置の構成＞
次に、本発明の実施の形態に係る木構造解析装置の構成について説明する。図４に示すように、本発明の実施の形態に係る木構造解析装置１００は、機能的には、入力部１０と、演算部２０と、出力部５０とを備えている。
【００１４】
入力部１０は、解析対象となる文書を受け付ける。
【００１５】
演算部２０は、部分構造解析部３０と、木構造推定部３２と、木結合部３８とを含んで構成されている。
【００１６】
木構造解析装置１００の処理の概要を説明する。木構造解析装置１００は、入力として文書を受け取ると、部分構造解析部３０にて文書を段落系列、段落を文系列、文をＥＤＵ系列に分割する。次に、木構造推定部３２のベクトル変換部４２にて、段落系列をベクトル系列へと変換し（図５）、文系列をベクトル系列へと変換し（図６）、ＥＤＵ系列をベクトル系列へと変換する（図７）。いま、系列の長さをnとし、スコア計算部４４にて受け取った系列の１番目のユニットからｋ番目のユニットの系列と、ｋ＋１番目のユニットからｎ番目のユニットの系列との間の分割スコアを計算し、それが最小となるｋ(１≦ｋ≦ｎ−１)で入力系列を２分割する。分割したそれぞれの系列に対しても同様にスコア計算部４４で分割スコアを計算しそれが最小となる位置で系列を２分割することを再帰的に繰り返す。この分割は分割結果が系列を構成する最小ユニット(段落、文、ＥＤＵ)になるまで繰り返す。これにより、ＥＤＵを葉とする木構造（図５）と、文を葉とする木構造（図６）と、段落を葉とする木構造（図７）とを構築する。木結合部３８は、これらの木構造を結合し、最終的な木構造を出力する。ＥＤＵが基本単位の一例である。
【００１７】
以下、木構造解析装置１００の各処理部について説明する。
【００１８】
部分構造解析部３０は、入力部１０で受け付けた文書について、文書の段落の系列（段落系列）への分割と、各段落に含まれる文の系列（文系列）への分割と、各文に含まれるＥＤＵの系列（ＥＤＵ系列）への分割とを行う。
【００１９】
具体的には、部分構造解析部３０は、以下に説明するように、文書から、文、段落、文書の３つの構造に分割し、それぞれを、ＥＤＵ系列、文系列、段落系列として出力する。ＥＤＵ系列への分割は、ＥＤＵ境界を認定する既存技術を用いればよい。文系列への分割は、句点を手がかりに文境界を認定すればよいし、既存の文境界認定技術を利用してもよい。また、段落系列への分割は、空行、字下げなどを手がかりとして分割すればよい。手がかりの情報がない場合には既存技術を用いて段落境界を認定すればよい。
【００２０】
木構造推定部３２は、各文について、文に含まれるＥＤＵ系列を表すＥＤＵベクトルの系列に基づいて、当該文に含まれるＥＤＵ系列を二つのスパンに分割することを、スパンの各々がＥＤＵとなるまで再帰的に繰り返し、スパンの各々をノードとした二分木で表される、ＥＤＵを単位とした木構造を出力する。
【００２１】
また、木構造推定部３２は、各段落について、段落に含まれる文系列の各文を表す文ベクトルの系列に基づいて、当該段落に含まれる文系列を二つのスパンに分割することを、スパンの各々が文となるまで再帰的に繰り返し、スパンの各々をノードとした二分木で表される、文を単位とした木構造を出力する。
【００２２】
また、木構造推定部３２は、文書に含まれる段落系列の各段落を表す段落ベクトルの系列に基づいて、文書に含まれる段落系列を二つのスパンに分割することを、スパンの各々が段落となるまで再帰的に繰り返し、スパンの各々をノードとした二分木で表される、段落を単位とした木構造を出力する。
【００２３】
具体的には、木構造推定部３２は、図８に示すように、単語ベクトルデータベース４０と、ベクトル変換部４２と、スコア計算部４４とを備えている。
【００２４】
単語ベクトルデータベース４０には、各単語について、単語を表す単語ベクトルが格納されている。
【００２５】
ベクトル変換部４２は、入力された系列をベクトル系列に変換する。ここで、入力された系列における最小ユニットのベクトルを、当該最小ユニットに含まれる単語のベクトルの加重平均とする。たとえば、ＳＩＦ（ｓｍｏｏｔｈ ｉｎｖｅｒｓｅ ｆｒｅｑｕｅｎｃｙ）などを用いればよい（非特許文献２参照）。
【００２６】
［非特許文献2］Arora, Sanjeev, Liang, Yingyu and Ma, Tengyu, "A Simple But Tough-to-best Baseline for Sentence Embeddings" on Support Vector Machine Classification", Proceedings of the ICLR-2017, 2017.
【００２７】
例えば、入力された系列が、段落系列の場合は、各段落を段落ベクトルに変換して、段落ベクトルの系列を出力する。入力された系列が、文系列の場合は、各文を文ベクトルに変換して、文ベクトルの系列を出力する。入力された系列が、ＥＤＵ系列の場合は、各ＥＤＵをＥＤＵベクトルに変換して、ＥＤＵベクトルの系列を出力する。
【００２８】
スコア計算部４４は、文に含まれるＥＤＵ系列を二つのスパンに分割する位置を決定する際に、分割する位置より左側のＥＤＵ系列に対するベクトルと、分割する位置より右側のＥＤＵ系列に対するベクトルとに基づいて、分割スコアを計算する。
【００２９】
具体的には、系列の長さをｎとすると系列を２分割するための分割候補はｎ−１箇所ある。つまり、1番目のＥＤＵの直後からn−1番目のＥＤＵの直後が分割候補となる。ここで、任意の分割点ｋ(１≦ｋ≦ｎ−１)に対して、左側の系列のベクトル、右側の系列のベクトルを以下の式で定義する。
【００３０】
【数１】
2020140464.tif 000003
(1)
2020140464.tif 000004
(2)
【００３１】
ここで、u(ei)はＥＤＵのベクトルである。vleft(k)とvright(k)を用いて分割点ｋにおける分割スコアを以下の式で定義する。
【００３２】
【数２】
2020140464.tif 000005
(3)
【００３３】
上記の分割スコアは、左側の系列のベクトルと、右側の系列のベクトルとの類似度を表している。
【００３４】
木構造推定部３２は、以下の式にて可能な分割点ｋのうち分割スコアが最小となる分割点ｋにてＥＤＵ系列を分割する(図９)。
【００３５】
【数３】
2020140464.tif 000006
(4)
【００３６】
上記のように分割スコアが最小となる分割点ｋにてＥＤＵ系列を分割することにより、左側の系列のベクトルと、右側の系列のベクトルとの類似度が最小となる分割点ｋにてＥＤＵ系列を分割することができる。
【００３７】
この手続きを分割後のＥＤＵ系列に対しても再帰的に行い、分割したＥＤＵ系列のすべてがＥＤＵになるまで繰り返し、ＥＤＵを単位とした木構造を出力する。
【００３８】
なお、上記手続きは貪欲法と呼ばれる手法に基づいており、木全体での総分割スコアを最大化するとは限らない。そこで、木全体での総分割スコアを最大化する方法を以下に示す。上記同様ＥＤＵ系列に対して木構造を推定する方法を例として説明する。
【００３９】
いま、任意の系列ｅl:m(ｌ番目のＥＤＵからｍ番目のＥＤＵまでの系列)をｋ（ｌ≦ｋ≦ｍ−１）番目のＥＤＵの直後で分割することを考える場合、その分割スコアの最大値Ｖ[ｌ][ｍ]はｌ番目のＥＤＵからｋ番目のＥＤＵで構成されるスパンの分割スコアの最大値Ｖ[ｌ][ｋ]、ｋ番目のＥＤＵでスパンを分割する際の分割スコアscore(k)、k+1番目のＥＤＵからｍ番目のＥＤＵで構成されるスパンの分割スコアの最大値Ｖ[ｋ＋１][ｍ]を用いて以下の式で定義される。
【００４０】
【数４】
2020140464.tif 000007
（5）
【００４１】
ｌ、ｍとして木構造を推定したいＥＤＵ系列を与え、テーブルＶをボトムアップに埋めていくと最終的には、Ｖ[ｌ][ｍ]が求まる。Ｖ[ｌ][ｍ]が求まったならＥＤＵ系列ｅl:mを２分割する最適な分割点ｋが式(5)より定まっているので、分割点ｋにてＥＤＵ系列を分割する。分割後のＥＤＵ系列に対してもテーブルＶを埋める過程で最適な分割が式(5)より定まっているのでそれに従い分割を繰り返す。このようにテーブルＶをボトムアップに埋めていけば可能なすべての木から総分割スコアが最大となる木を獲得できる。計算量に関しては、貪欲法の方が少ないので利用する状況に応じて２つの手法を使い分ければ良い。
【００４２】
スコア計算部４４は、ＥＤＵ系列と同様に、段落に含まれる文系列を二つのスパンに分割する位置を決定する際に、分割する位置より左側の文系列に対するベクトルと、分割する位置より右側の文系列に対するベクトルとに基づいて、上記式（１）〜式（３）に従って、分割スコアを計算する。このとき、u(ei)は文のベクトルである。
【００４３】
木構造推定部３２は、上記式（４）にて可能な分割点ｋのうち分割スコアが最小となる分割点ｋにて文系列を分割する。この手続きを分割後の文系列に対しても再帰的に行い、分割した文系列のすべてが文になるまで繰り返し、文を単位とした木構造を出力する。
【００４４】
スコア計算部４４は、ＥＤＵ系列と同様に、文書に含まれる段落系列を二つのスパンに分割する位置を決定する際に、分割する位置より左側の段落系列に対するベクトルと、分割する位置より右側の段落系列に対するベクトルとに基づいて、上記式（１）〜式（３）に従って、分割スコアを計算する。このとき、u(ei)は段落のベクトルである。
【００４５】
木構造推定部３２は、上記式（４）にて可能な分割点ｋのうち分割スコアが最小となる分割点ｋにて段落系列を分割する。この手続きを分割後の段落系列に対しても再帰的に行い、分割した段落系列のすべてが段落になるまで繰り返し、段落を単位とした木構造を出力する。
【００４６】
木結合部３８は、木構造推定部３２で推定した、ＥＤＵを単位とした木構造、文を単位とした木構造、及び段落を単位とした木構造を結合して、出力部５０により出力する。具体的には、段落を単位とした木構造の葉と、当該葉が表している段落について得られた、文を単位とした木構造の根とを結合し、文を単位とした木構造の葉と、当該葉が表している文について得られた、ＥＤＵを単位とした木構造の根とを結合する。
【００４７】
例えば、図１０に示すように、段落p1を表す葉と、段落p1について得られた、文s1から文s5で構成される木構造の根とを結合し、文s1を表す葉と、文s1について得られた、ＥＤＵe1からＥＤＵe6で構成される木構造の根を結合している。このように、すべての段落pに対して文sを葉とする木構造を結合した後、すべての文sに対してＥＤＵeを葉とする木構造を結合する。
【００４８】
木構造解析装置１００の各々は、一例として、図１１に示すコンピュータ８４によって実現される。コンピュータ８４は、ＣＰＵ８６、メモリ８８、プログラム８２を記憶した記憶部９２、モニタを含む表示部９４、及びキーボードやマウスを含む入力部９６を含んでいる。ＣＰＵ８６、メモリ８８、記憶部９２、表示部９４、及び入力部９６はバス９８を介して互いに接続されている。
【００４９】
記憶部９２はＨＤＤ、ＳＳＤ、フラッシュメモリ等によって実現される。記憶部９２には、コンピュータ８４を木構造解析装置１００として機能させるためのプログラム８２が記憶されている。ＣＰＵ８６は、プログラム８２を記憶部９２から読み出してメモリ８８に展開し、プログラム８２を実行する。なお、プログラム８２をコンピュータ可読媒体に格納して提供してもよい。
【００５０】
＜本発明の実施の形態に係る木構造解析装置の作用＞
次に、本発明の実施の形態に係る木構造解析装置１００の作用について説明する。入力部１０において文書を受け付けると、木構造解析装置１００は、図１２に示す木構造解析処理ルーチンを実行する。
【００５１】
まず、ステップＳ１００では、部分構造解析部３０は、入力部１０で受け付けた文書について、段落系列への分割と、文系列への分割と、ＥＤＵ系列への分割とを行う。
【００５２】
次に、ステップＳ１０１では、ベクトル変換部４２は、ＥＤＵ系列に基づいて、各ＥＤＵをＥＤＵベクトルに変換して、ＥＤＵベクトルの系列を出力する。
【００５３】
ステップＳ１０２では、木構造推定部３２は、可能な分割点ｋのうち分割スコアが最小となる分割点ｋにてＥＤＵ系列を分割することを、再帰的に行い、分割したＥＤＵ系列のすべてがＥＤＵになるまで繰り返し、ＥＤＵを単位とした文の木構造を出力する。
【００５４】
次に、ステップＳ１０３では、ベクトル変換部４２は、文系列に基づいて、各文を文ベクトルに変換して、文ベクトルの系列を出力する。
【００５５】
ステップＳ１０４では、木構造推定部３２は、可能な分割点ｋのうち分割スコアが最小となる分割点ｋにて文系列を分割することを、再帰的に行い、分割した文系列のすべてが文になるまで繰り返し、文を単位とした段落の木構造を出力する。
【００５６】
次に、ステップＳ１０５では、ベクトル変換部４２は、段落系列に基づいて、各段落を段落ベクトルに変換して、段落ベクトルの系列を出力する。
【００５７】
ステップＳ１０６では、木構造推定部３２は、可能な分割点ｋのうち分割スコアが最小となる分割点ｋにて段落系列を分割することを、再帰的に行い、分割した段落系列のすべてが段落になるまで繰り返し、段落を単位とした文書の木構造を出力する。
【００５８】
ステップＳ１０８では、木結合部３８は、上記ステップＳ１０２、Ｓ１０４、Ｓ１０６で推定した、ＥＤＵを単位とした木構造、文を単位とした木構造、及び段落を単位とした木構造を結合して、出力部５０により出力し、木構造解析処理ルーチンを終了する。
【００５９】
以上説明したように、本発明の実施の形態に係る木構造解析装置によれば、各文について、ＥＤＵベクトルの系列に基づいて、文に含まれるＥＤＵ系列を二つのスパンに分割することを再帰的に繰り返し、基本単位を単位とした木構造を出力し、各段落について、文ベクトルの系列に基づいて、段落に含まれる文系列を二つのスパンに分割することを再帰的に繰り返し、文を単位とした木構造を出力し、段落ベクトルの系列に基づいて、文書に含まれる段落系列を二つのスパンに分割することを再帰的に繰り返し、段落を単位とした木構造を出力し、基本単位を単位とした木構造と、文を単位とした木構造と、段落を単位とした木構造とを最終的に結合することにより、訓練データがなくても、精度よく、文書を表す木構造を構築できる。
【００６０】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００６１】
１０   入力部
２０   演算部
３０   部分構造解析部
３２   木構造推定部
３８   木結合部
４０   単語ベクトルデータベース
４２   ベクトル変換部
４４   スコア計算部
５０   出力部
８２   プログラム
８４   コンピュータ
１００ 木構造解析装置
【図１】
2020140464.tif 000008
【図２】
2020140464.tif 000009
【図３】
2020140464.tif 000010
【図４】
2020140464.tif 000011
【図５】
2020140464.tif 000012
【図６】
2020140464.tif 000013
【図７】
2020140464.tif 000014
【図８】
2020140464.tif 000015
【図９】
2020140464.tif 000016
【図１０】
2020140464.tif 000017
【図１１】
2020140464.tif 000018
【図１２】
2020140464.tif 000019