(57)【特許請求の範囲】
【請求項１】
自然言語の複数の要素からなる複数の系列データに現れる典型的な表現を抽出し、表現テンプレートとして生成する表現テンプレート生成装置であって、
前記複数の系列データのすべての２組の組み合わせごとに、前記要素ごとの類似の度合を示す編集距離であるアライメントコストを算出するアライメントコスト算出手段と、
前記系列データをアライメント列とした２組の組み合わせごとに、前記アライメントコストを対応付けて記憶するアライメントコスト記憶手段と、
このアライメントコスト記憶手段に記憶されているアライメントコストの低いアライメント列から順に、２次元配列テーブルのセルに同一の編集距離となる経路を保持した動的計画法の経路テーブルを生成する経路テーブル生成手段と、
この経路テーブル生成手段で生成された経路テーブルにおいて、前記経路の逆探索を行うことで、複数の新たなアライメント列を生成する経路逆探索手段と、
この経路逆探索手段で生成された複数のアライメント列を、前記要素を頂点とする有向グラフに変換し、前記表現テンプレートとして生成する有向グラフ生成手段と、
を備えることを特徴とする表現テンプレート生成装置。
【請求項２】
前記経路逆探索手段が前記複数の新たなアライメント列を生成する際に、前記編集距離に基づいて、当該アライメント列のアライメントコストを算出し、
前記経路逆探索手段で算出されたアライメントコストに基づいて、前記アライメント列の数を制限するアライメント数制限手段をさらに備えることを特徴とする請求項１に記載の表現テンプレート生成装置。
【請求項３】
前記有向グラフ生成手段で生成された表現テンプレートにおいて、当該表現テンプレートの有効グラフを構成する辺の使用頻度、頂点の数または辺の数の少なくとも１つを基準として、前記有向グラフの枝刈りを行う有向グラフ制限手段をさらに備えることを特徴とする請求項１または請求項２に記載の表現テンプレート生成装置。
【請求項４】
自然言語の複数の要素からなる複数の系列データに現れる典型的な表現を抽出し、表現テンプレートとして生成する表現テンプレート生成方法であって、
前記要素ごとの類似の度合を示す編集距離であるアライメントコストを算出するアライメントコスト算出手段により、前記複数の系列データのすべての２組の組み合わせごとに前記アライメントコストを算出し、前記系列データをアライメント列とした２組の組み合わせごとに、前記アライメントコストを対応付けてアライメントコスト記憶手段に記憶するアライメントコスト算出ステップと、
２次元配列テーブルのセルに同一の編集距離となる経路を保持した動的計画法の経路テーブルを生成する経路テーブル生成手段により、前記アライメントコスト記憶手段に記憶されているアライメントコストの低いアライメント列から順に、前記経路テーブルを生成する経路テーブル生成ステップと、
前記経路テーブルを逆探索する経路逆探索手段により、前記経路テーブル生成ステップで生成された経路テーブルにおいて、前記経路の逆探索を行うことで、複数の新たなアライメント列を生成する経路逆探索ステップと、
前記要素を頂点とする有向グラフを生成する有向グラフ生成手段により、前記経路逆探索ステップで生成された複数のアライメント列を前記有向グラフに変換し、前記表現テンプレートとして生成する有向グラフ生成ステップと、
を含むことを特徴とする表現テンプレート生成方法。
【請求項５】
自然言語の複数の要素からなる複数の系列データに現れる典型的な表現を抽出し、表現テンプレートとして生成するために、コンピュータを、
前記複数の系列データのすべての２組の組み合わせごとに、前記要素ごとの類似の度合を示す編集距離であるアライメントコストを算出し、前記系列データをアライメント列とした２組の組み合わせごとに、前記アライメントコストを対応付けてアライメントコスト記憶手段に記憶するアライメントコスト算出手段、
前記アライメントコスト記憶手段に記憶されているアライメントコストの低いアライメント列から順に、２次元配列テーブルのセルに同一の編集距離となる経路を保持した動的計画法の経路テーブルを生成する経路テーブル生成手段、
この経路テーブル生成手段で生成された経路テーブルにおいて、前記経路の逆探索を行うことで、複数の新たなアライメント列を生成する経路逆探索手段、
この経路逆探索手段で生成された複数のアライメント列を、前記要素を頂点とする有向グラフに変換し、前記表現テンプレートとして生成する有向グラフ生成手段、
として機能させることを特徴とする表現テンプレート生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の系列データ（テキスト文書）から典型的な表現を抽出した表現テンプレートを生成する表現テンプレート生成装置、その方法およびそのプログラムに関する。
【背景技術】
【０００２】
従来、自然言語の文書において、類似した文書群についてアライメント（整列）を行い、その類似した文書群から典型的な表現を抽出することで、種々の文書を分類する手法が知られている（例えば、特許文献１、非特許文献１，２参照）。
【０００３】
これらの手法によれば、複数の類似する文書群に含まれる２つの文書ごとに、例えば、動的計画法（非特許文献３参照）によって文書をアライメントし、複数の文書群から、共通するアライメントのデータを抽出することで、当該文書群の典型的な表現を示す表現テンプレートを生成する。このように、従来の手法によれば、類似する文書群ごとに表現テンプレートを生成するため、文書をその文書内に含まれる表現によって分類することができる。すなわち、従来の手法は、予め表現テンプレートを学習しておくことで、新たに入力される文書を、表現テンプレートとの類似の度合に基づいて分類することが可能になる。
【０００４】
なお、前記した２つ以上の系列データをアライメントする手法は、一般に、マルチプルアライメントと呼ばれている。このマルチプルアライメントは、２つの系列データのアライメントを多数の系列データに拡張したアルゴリズムである。通常、２つの系列データのアライメントは、動的計画法（非特許文献３参照）によって２次元のテーブルを用いて厳密解を求めることができる。しかし、入力される系列データがＭ次元の場合、動的計画法により解決するためには、Ｍ次元のテーブルが必要になるため計算量が膨大になり現実的ではない。そこで、マルチプルアライメントでは、２系列データのアライメントを再帰的に繰り返すことで、近似解を求めることとしている。
【特許文献１】特開２００６−１１３７４６号公報
【非特許文献１】R. Barzilay and L. Lee: “Bootstrapping lexical choice via multiple-sequence alignment”, Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing(EMNLP), pp. 164-171 (2002).
【非特許文献２】R. Barzilay and L. Lee: “Learning to paraphrase: An unsupervised approach using multiple-sequence alignment”, HLT-NAACL 2003: Main Proceedings, pp. 16-23 (2003).
【非特許文献３】コルメン、ライザーソン、リベルト著「アルゴリズムイントロダクション」、１６章「動的計画法」、近代科学社
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来のマルチプルアライメントは、２系列データのアライメントを再帰的に繰り返すため、１回のアライメントにより選択されたアライメントの系列データが、後段のアライメントに影響を及ぼすことになる。
【０００６】
一般に、自然言語の文書をアライメントすると、類似の度合が一致するアライメント列が複数存在することになる。この場合、類似の度合が一致しても、すべてが必ずしも最適なアライメントである保証がないため、従来のように１つのアライメント列を選択すると、最適なアライメント列が選択されるとは限らない。このように、従来のマルチプルアライメントは、必ずしも最適とはいえないアライメントの系列データが選択されるため、再帰的に繰り返された解は、全体として不適切なアライメントとなってしまうという問題がある。
【０００７】
本発明は、以上のような課題を解決するためになされたものであり、自然言語の類似した複数の系列データ（テキスト文書）から、典型的な表現を抽出した表現テンプレートを精度よく生成することが可能な表現テンプレート生成装置、その方法およびそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、前記目的を達成するために創案されたものであり、まず、請求項１に記載の表現テンプレート生成装置は、自然言語の複数の要素からなる複数の系列データに現れる典型的な表現を抽出し、表現テンプレートとして生成する表現テンプレート生成装置であって、アライメントコスト算出手段と、アライメントコスト記憶手段と、経路テーブル生成手段と、経路逆探索手段と、有向グラフ生成手段と、を備える構成とした。
【０００９】
かかる構成において、表現テンプレート生成装置は、アライメントコスト算出手段によって、複数の系列データのすべての２組の組み合わせごとに、要素ごとの類似の度合を示す編集距離であるアライメントコストを算出し、系列データをアライメント列とした２組の組み合わせごとにアライメントコストと対応付けてアライメントコスト記憶手段に記憶する。これによって、アライメントを行うための初期化データが、アライメントコスト記憶手段に記憶されることになる。なお、ここで、編集距離とは、２つの系列データがどの程度異なっているのかを示す数値であって、一方の系列データを要素の挿入、削除、置換によって他方の系列データに変形するための回数を距離とみなした数値である。
【００１０】
そして、表現テンプレート生成装置は、経路テーブル生成手段によって、アライメントコストの低い、すなわち、より類似の度合が高いアライメント列から順に、２次元配列テーブルのセルに同一の編集距離となる経路を保持した動的計画法の経路テーブルを生成する。これによって、経路テーブルには、編集距離が同一である場合に１つの経路に限定されず、複数の経路が保持されることになる。そして、表現テンプレート生成装置は、経路逆探索手段によって、経路テーブル生成手段で生成された経路テーブルにおいて、経路の逆探索を行うことで、複数の新たなアライメント列を生成する。これによって、表現テンプレート生成装置は、マルチプルアライメントにおいて、曖昧性を保持したアライメント列を生成することができる。
【００１１】
そして、表現テンプレート生成装置は、有向グラフ生成手段によって、経路逆探索手段で生成された複数のアライメント列を、要素を頂点とする有向グラフに変換し、表現テンプレートとして生成する。このように、表現テンプレート生成装置は、複数の系列データをアライメントすることで、系列データに現れる典型的な表現が抽出され、テンプレート化することができる。
【００１２】
また、請求項２に記載の表現テンプレート生成装置は、請求項１に記載の表現テンプレート生成装置において、経路逆探索手段が複数の新たなアライメント列を生成する際に、編集距離に基づいて、当該アライメント列のアライメントコストを算出し、この経路逆探索手段で算出されたアライメントコストに基づいて、アライメント列の数を制限するアライメント数制限手段をさらに備える構成とした。
【００１３】
かかる構成において、表現テンプレート生成装置は、経路逆探索手段で探索された複数のアライメント列から、予め定めた基準により、アライメントコストの低いもののみを残す。これによって、再帰的に処理が行われる動的計画法において、複数の経路が探索される場合であっても、その増加を抑えることができる。
【００１４】
さらに、請求項３に記載の表現テンプレート生成装置は、請求項１または請求項２に記載の表現テンプレート生成装置において、有向グラフ制限手段をさらに備える構成とした。
【００１５】
かかる構成において、表現テンプレート生成装置は、有向グラフ制限手段によって、有向グラフ生成手段で生成された表現テンプレートにおいて、当該表現テンプレートの有効グラフを構成する辺の使用頻度、頂点の数または辺の数の少なくとも１つを基準として、有向グラフの枝刈りを行う。これによって、表現として出現頻度が少ない言い回しを有向グラフから削除することができる。
【００１６】
また、請求項４に記載の表現テンプレート生成方法は、自然言語の複数の要素からなる複数の系列データに現れる典型的な表現を抽出し、表現テンプレートとして生成する表現テンプレート生成方法であって、アライメントコスト算出ステップと、経路テーブル生成ステップと、経路逆探索ステップと、有向グラフ生成ステップと、を含む手順とした。
【００１７】
かかる手順において、表現テンプレート生成方法は、アライメントコスト算出ステップで、複数の系列データのすべての２組の組み合わせごとに、要素ごとの類似の度合を示す編集距離であるアライメントコストを算出し、系列データをアライメント列とした２組の組み合わせごとにアライメントコストと対応付けてアライメントコスト記憶手段に記憶する。
【００１８】
そして、表現テンプレート生成方法は、経路テーブル生成ステップで、アライメントコストの低いアライメント列から順に、２次元配列テーブルのセルに同一の編集距離となる経路を保持した動的計画法の経路テーブルを生成する。そして、表現テンプレート生成方法は、経路逆探索ステップで、経路テーブル生成ステップで生成された経路テーブルにおいて、経路の逆探索を行うことで、複数の新たなアライメント列を生成する。そして、表現テンプレート生成方法は、有向グラフ生成ステップで、経路逆探索ステップで生成された複数のアライメント列を、要素を頂点とする有向グラフに変換し、表現テンプレートとして生成する。
【００１９】
また、請求項５に記載の表現テンプレート生成プログラムは、自然言語の複数の要素からなる複数の系列データに現れる典型的な表現を抽出し、表現テンプレートとして生成するために、コンピュータを、アライメントコスト算出手段、経路テーブル生成手段と、経路逆探索手段、有向グラフ生成手段、として機能させる構成とした。
【００２０】
かかる構成において、表現テンプレート生成プログラムは、アライメントコスト算出手段によって、複数の系列データのすべての２組の組み合わせごとに、要素ごとの類似の度合を示す編集距離であるアライメントコストを算出し、系列データをアライメント列とした２組の組み合わせごとにアライメントコストと対応付けてアライメントコスト記憶手段に記憶する。
【００２１】
そして、表現テンプレート生成プログラムは、経路テーブル生成手段によって、アライメントコストの低いアライメント列から順に、２次元配列テーブルのセルに同一の編集距離となる経路を保持した動的計画法の経路テーブルを生成する。そして、表現テンプレート生成プログラムは、経路逆探索手段によって、経路テーブル生成手段で生成された経路テーブルにおいて、経路の逆探索を行うことで、複数の新たなアライメント列を生成する。そして、表現テンプレート生成プログラムは、有向グラフ生成手段によって、経路逆探索手段で生成された複数のアライメント列を、要素を頂点とする有向グラフに変換し、表現テンプレートとして生成する。
【発明の効果】
【００２２】
本発明は、以下に示す優れた効果を奏するものである。
請求項１、請求項４または請求項５に記載の発明によれば、動的計画法のテーブルにおいて、セルに保持する経路を１つに限定せず、同一の編集距離（コスト）の経路を複数保持するため、最適なアライメント列を削除することない。このため、本発明は、微妙に違う表現であっても、従来のように削除せずに表現テンプレートに反映させることができる。
【００２３】
請求項２に記載の発明によれば、動的計画法により生成されるアライメント列の数をアライメントコストにより制限するため、再帰的に生成されるアライメント列の数を抑え、演算コストを抑えることができる。
【００２４】
請求項３に記載の発明によれば、有向グラフの枝刈りを行うことで、複数の系列データで出現する頻度が少ない表現を除去することができる。これによって、本発明は、より典型的な表現のみを抽出することができ、表現を分類する精度が高い表現テンプレートを生成することができる。
【発明を実施するための最良の形態】
【００２５】
［文書分類判別システムの概要］
最初に、図１を参照して、本発明の実施の形態に係る表現テンプレート生成装置を含んだ文書分類判別システムの概要について説明する。図１は、文書分類判別システムの概略構成を示すブロック図である。文書分類判別システムＳは、予め定めた分類項目ごとに類似したテキスト文書群から、当該テキスト文書群内に現れる典型的な表現を表現テンプレートとして学習し、その学習結果である表現テンプレートに基づいて、新たに入力されるテキスト文書が、どの分類項目に属するかを判別するものである。ここでは、文書分類判別システムＳは、表現テンプレート生成装置１と、表現テンプレート記憶装置２と、分類判別装置３とを備える。
【００２６】
表現テンプレート生成装置１は、意見や感想を述べる対象が予め特定されている類似した意見や感想を記述したテキスト文書から、当該テキスト文書内に現れる典型的な表現を表現テンプレートとして生成するものである。例えば、表現テンプレート生成装置１は、書籍、映画、放送等に対する読者、視聴者からの意見を、「感動した」、「考えさせられた」、「意外だ」等に予め人手を介して分類した複数の類似したテキスト文書を対象として、分類項目ごとに表現テンプレートを生成する。
【００２７】
この表現テンプレート生成装置１で生成される表現テンプレートは、図２に示すように、「頂点」を形態素、「辺」を頂点の接続としたグラフ構造で表される。図２の例では、「素晴らしいと思った」、「素晴らしいと思いました」、「すごいと思った」、「すごいと思いました」の４通りの表現が、ある分類項目（例えば、「感動した」の分類項目）について生成されていることを示している。この表現テンプレート生成装置１で生成された表現テンプレートは、分類項目ごとに表現テンプレート記憶装置２に記憶される。
【００２８】
ここでは、表現テンプレート生成装置１は、類似したテキスト文書群Ａ１〜ＡＮから、それぞれのテキスト文書群Ａ１〜ＡＮに対応した表現テンプレートＢ１〜ＢＮを生成し、表現テンプレート記憶装置２に記憶する。例えば、Ｂ１〜ＢＮは、「感動した」、「考えさせられた」、「意外だ」等に対応する表現テンプレートとなる。
【００２９】
表現テンプレート記憶装置２は、表現テンプレート生成装置１で生成された表現テンプレートを、分類項目ごとに学習結果として記憶するものであって、ハードディスク等の一般的な記憶装置である。
【００３０】
分類判別装置３は、表現テンプレート記憶装置２に記憶されている表現テンプレートに基づいて、新たに入力されたテキスト文書が、どの分類項目に属するものであるかを判別するものである。この分類判別装置３は、入力されたテキスト文書に、表現テンプレート記憶装置２に記憶されている表現テンプレートの表現が含まれている場合、例えば、入力された新たなテキスト文書Ｎに、「素晴らしいと思った」という表現が含まれている場合、図２の表現テンプレートに基づいて、当該テキスト文書を「感動した」の分類項目に属する文書であると判別する。
【００３１】
このように、文書分類判別システムＳは、表現テンプレート生成装置１によって、分類項目ごとの表現テンプレートの学習処理を行い、分類判別装置３によって、新たなテキスト文書の判別処理を行う。以下、表現テンプレート生成装置１の構成および動作について詳細に説明する。
【００３２】
［表現テンプレート生成装置の構成］
まず、図３を参照して、本発明の実施の形態に係る表現テンプレート生成装置の構成について説明する。図３は、本発明の実施の形態に係る表現テンプレート生成装置の全体構成を示すブロック図である。
【００３３】
ここでは、表現テンプレート生成装置１は、アライメントコスト算出手段１０と、アライメントコスト記憶手段２０と、アライメント列生成手段３０と、テンプレート生成手段４０とを備える。なお、表現テンプレート生成装置１に入力されるテキスト文書（系列データ）は、予め形態素ごとの要素に分割されているものとする。
【００３４】
アライメントコスト算出手段１０は、複数のテキスト文書のすべての２組の組み合わせごとに、要素ごとの類似の度合を示す編集距離であるアライメントコストを算出するものである。このアライメントコスト算出手段１０は、算出したアライメントコストの低い順に、２組のテキスト文書を対応付けたアライメントコスト一覧をアライメントコスト記憶手段２０に記憶しておく。
【００３５】
ここでＭ系列の系列データ（テキスト文書）の要素の集合をΩ（Ｍ）、空要素（＿）の集合を｛＿｝、ｉ、ｉ′、ｉ″を系列データの要素の順番（空要素を除く）を表す添字とすると、系列データ｛Ｗ（１）｝，｛Ｗ（２）｝およびアライメント列｛ａ（ｊ）｝は、以下の（１）式で表される。
【００３６】
【数１】
0005022252.tif 000002
【００３７】
また、空要素を含む系列データから、要素の順番を維持しながら空要素を取り除く関数をｆｏｍｉｔとしたとき、系列データ｛Ｗ（ｊ）｝は、以下の（２）式で表される。
【００３８】
【数２】
0005022252.tif 000003
ここで、２系列データ（２組のテキスト文書）｛Ｗ（１）｝，｛Ｗ（２）｝のアライメントコストは、各要素の編集距離の和であって、以下の（３）式の関数ｆｃｏｓｔにより求められる値である。
【００３９】
【数３】
0005022252.tif 000004
【００４０】
なお、Ｅｄｉｔは、２つの要素の一致の有無に基づいた編集距離であって、以下の（４）式により予め定義しておくこととする。
【００４１】
【数４】
0005022252.tif 000005
【００４２】
このように、アライメントコスト算出手段１０は、２組のテキスト文書の類似の度合をアライメントコストとして算出する。
【００４３】
アライメントコスト記憶手段２０は、アライメントコスト算出手段１０で算出された２組ごとのテキスト文書のアライメントコストを、テキスト文書対と対応付けたアライメントコスト一覧として記憶するものであって、ハードディスク等の一般的な記憶装置である。このアライメントコスト記憶手段２０には、例えば、図４に示すように、テキスト文書対と、アライメントコストとを表形式に対応付けたアライメントコスト一覧ＴＣとして記憶しておく。なお、アライメントコスト一覧ＴＣは、アライメントコストの小さいものから順にソートされている。
【００４４】
アライメント列生成手段３０は、アライメントコスト記憶手段２０に記憶されているアライメントコストの低い２系列のアライメント列（テキスト文書）から順に、再帰的に動的計画法により１つ以上の新たなアライメント列を生成するものである。
【００４５】
ここでは、アライメント列生成手段３０は、アライメントコスト記憶手段２０に記憶されているアライメント列から空要素を除去して新たな系列データとして、アライメントを行う。すなわち、系列データＷ（１）が｛ａ，ｂ，ａ，ｄ｝、系列データＷ（２）が｛ａ，ｃ，ｄ｝に対応するアライメント列｛ａ（ｊ）｝が、以下の（５）式で表される場合、アライメント列生成手段３０は、以下の（６）式に示した、空要素を除去したアライメント列｛Ｗ｝を入力としてアライメントを行う。
【００４６】
【数５】
0005022252.tif 000006
【００４７】
【数６】
0005022252.tif 000007
【００４８】
なお、アライメント列生成手段３０は、アライメントコスト記憶手段２０から読み出して行うアライメント対象の新たなアライメント列を｛Ｗ（１）｝，｛Ｗ（２）｝として、以下の（７）式により、アライメントコストが最小となるアライメント列をすべて生成する。
【００４９】
【数７】
0005022252.tif 000008
【００５０】
このように、アライメント列生成手段３０は、アライメントコストが最小となるアライメント列を１つに限定しないため、曖昧性を保持したアライメント列を生成することができる。ここでは、アライメント列生成手段３０は、前記（７）式を動的計画法により求めるため、経路テーブル生成手段３１と、経路逆探索手段３２と、アライメント数制限手段３３とを備えて構成している。
【００５１】
経路テーブル生成手段３１は、アライメントコスト記憶手段２０に記憶されているアライメントコストの低いアライメント列から順に、２次元配列テーブルのセルに同一の編集距離となる経路を保持した動的計画法の経路テーブルを生成するものである。ここでは、経路テーブル生成手段３１は、アライメントコスト記憶手段２０から、最もアライメントコストの低い２つのテキスト文書において、アライメント列を選択し、このアライメント列に含まれる２つのアライメントの要素列を２軸とする動的計画法の経路テーブルを生成する。この経路テーブル生成手段３１で生成された動的計画法の経路テーブルは経路逆探索手段３２で使用される。
【００５２】
経路逆探索手段３２は、経路テーブル生成手段３１で生成された動的計画法の経路テーブルにおいて、経路の逆探索（トレースバック）を行うことで、アライメント列を生成するものである。なお、経路逆探索手段３２は、経路の逆探索を行う際に、逐次編集距離を加算することで、当該経路におけるアライメントコストを算出することとする。
【００５３】
ここで、図５および図６を参照（適宜図３参照）して、経路テーブル生成手段３１が行う処理および経路逆探索手段３２が行う処理について具体的に説明する。図５は、経路テーブル生成手段が行う動的計画法の経路テーブルを生成する手法を説明するための説明図である。図６は、経路逆探索手段が行う動的計画法の経路テーブルからアライメント列を生成する手法を説明するための説明図である。
【００５４】
図５に示すように、経路テーブル生成手段３１は、２つのアライメントの要素列（アライメントＡ、アライメントＢ）を２軸とする２次元配列の経路テーブルＴＤＰを、図示を省略したメモリ上に生成する。そして、経路テーブル生成手段３１は、各アライメントの先頭を示す経路テーブルＴＤＰの左上のセルから各アライメントの最後尾を示す経路テーブルＴＤＰの右下のセルまで、順次、経路とその時の編集距離（コスト）とを２次元配列の配列データとしてメモリ上に記憶する。
【００５５】
例えば、図５のセルＣ１において、Ｃ２からの経路（下向矢印）には、アライメントＡの“ｉ”番目およびアライメントＢの“ｊ−１”番目までの系列と、当該系列にアライメントＢの“ｊ”番目の要素を挿入したときの系列との編集距離を対応付ける。また、Ｃ３からの経路（右向矢印）には、アライメントＡの“ｉ−１”番目およびアライメントＢの“ｊ”番目までの系列と、当該系列にアライメントＡの“ｉ”番目の要素を挿入したときの系列との編集距離を対応付ける。
【００５６】
また、Ｃ４からの経路（右下向矢印）には、アライメントＡの“ｉ”番目およびアライメントＢの“ｊ”番目の要素が一致する場合には、アライメントＡの“ｉ−１”番目およびアライメントＢの“ｊ−１”番目までの系列と、当該系列にアライメントＡの“ｉ”番目（アライメントＡの“ｊ”番目）の要素を挿入したときの系列との編集距離を対応付ける。一方、アライメントＡの“ｉ”番目およびアライメントＢの“ｊ”番目の要素が不一致の場合には、アライメントＡの“ｉ−１”番目およびアライメントＢの“ｊ−１”番目までの系列と、当該系列にアライメントＡの“ｉ”番目の要素とアライメントＡの“ｊ”番目の要素とをそれぞれ置換して挿入した系列との編集距離を対応付ける。
【００５７】
なお、経路テーブル生成手段３１は、各経路（図５の下向矢印、右向矢印、右下向矢印）の編集距離（コスト）が異なる場合は、最適（コストが最小）な経路のみを記憶することとして、編集距離が同一である場合は、すべての経路を記憶することとする。
【００５８】
そして、図６に示すように、経路逆探索手段３２は、経路テーブル生成手段３１で生成された動的計画法の経路テーブルＴＤＰにおいて、経路テーブルの終点（右下）のセルＣＥから、順次そのセルに対応付けて記憶されている経路に基づいて、経路テーブルの始点（左上）のセルＣＳまでの経路を探索する。なお、図６に示すように、セルＣ１に２つの経路で同一のコストが対応付けられていたときは、経路逆探索手段３２は、２つの経路で構成されるアライメント列を生成する。これによって、同一コストのアライメント列が１つに限定されず複数生成されることになる。
図３に戻って、表現テンプレート生成装置１の構成について説明を続ける。
【００５９】
アライメント数制限手段３３は、経路逆探索手段３２で生成されたアライメント列について、予め定めた基準に基づいて、生成するアライメント列数を制限するものである。ここでは、アライメント数制限手段３３は、アライメント列生成手段３０が処理する２系列のアライメント列ごとに、生成するアライメント列数を制限することとする。これによって、動的計画法における経路数を制限することができ、再帰処理に伴う指数関数的な経路数の増大を防止することができる。なお、アライメント数制限手段３３は、例えば、以下の４つの基準（基準Ａ１〜基準Ａ４）の少なくとも１つによって、経路数を制限することができる。
【００６０】
＜基準Ａ１  アライメントコストによる制限＞
アライメント数制限手段３３は、経路逆探索手段３２で求められた２系列データのアライメントコストが最小となるアライメント列のみを出力することとする。すなわち、経路逆探索手段３２で生成された複数のアライメント列のうちで、経路のトータルのアライメントコストが最小となるもののみを残し、他を削除することとする。
【００６１】
＜基準Ａ２  空要素の数による制限＞
アライメント数制限手段３３は、経路逆探索手段３２で生成された複数のアライメント列のうちで、空要素の数が最小のアライメント列のみを残し、他を削除することとする。
【００６２】
＜基準Ａ３  最適経路の絶対数による制限＞
アライメント数制限手段３３は、経路逆探索手段３２で生成された複数のアライメント列のうちで、予め定めた経路の絶対数をランダムに選択し、他を削除することとする。
【００６３】
＜基準Ａ４  要素の絶対数による制限＞
アライメント数制限手段３３は、経路逆探索手段３２で生成された複数のアライメント列の要素数を累計し、要素数が予め定めた絶対数を超過した場合、それ以降のアライメント列を削除する。
【００６４】
このように、アライメント列生成手段３０は、２系列のアライメント列から順に、動的計画法により１つ以上の新たなアライメント列を生成する際に、アライメント列数を制限するため、経路逆探索手段３２が複数の経路のアライメント列を生成する場合であっても、指数関数的な経路数の増大を防止することができる。
【００６５】
なお、アライメント列生成手段３０は、２系列のアライメント列から、新たなアライメント列を生成した場合、アライメントコスト記憶手段２０に記憶されている１系列のアライメント列に関するデータを削除することとする。例えば、図４において、テキスト文書対｛Ｗ（１），Ｗ（２）｝をアライメントした後、Ｗ（１）に関するデータ｛Ｗ（１），Ｗ（２）｝、｛Ｗ（１），Ｗ（３）｝、…を削除する。なお、削除するアライメント列は、２系列のアライメント列はいずれか一方であればよい。
【００６６】
そして、すべての２系列のアライメント列から、新たなアライメント列を生成した段階、すなわち、アライメントコスト記憶手段２０に記憶されているアライメント列が１系列のみになるまで、順次、アライメント列を生成し、テンプレート生成手段４０に出力する。
【００６７】
テンプレート生成手段４０は、アライメント列生成手段３０で生成された複数のアライメント系列を、要素を頂点とする有向グラフに変換し、表現テンプレートとして生成するものである。ここでは、テンプレート生成手段４０は、有向グラフ生成手段４１と、有向グラフ制限手段４２とを備える。
【００６８】
有向グラフ生成手段４１は、複数のアライメント列を、当該アライメント列を構成する要素を頂点とする有向グラフに変換するものである。ここでは、有向グラフ生成手段４１は、要素を頂点（ノード）とし、アライメント列で先に出現する要素を始点、次に出現する要素を終点とする方向性を有する辺を定義する。これによって、有向グラフ生成手段４１は、アライメント列から、有向グラフによって定型化した表現テンプレートを生成することができる。
【００６９】
なお、ここでは、有向グラフ生成手段４１は、アライメント列で同一の辺を共有する場合には、その辺に共有する数だけ度数を付与することとする。これによって、要素のつながりの頻度を数値化することができる。
【００７０】
有向グラフ制限手段４２は、有向グラフ生成手段４１で生成されたアライメント列ごとに生成された有向グラフから、予め定めた基準に基づいて、最適な有向グラフ（表現テンプレート）を選択するものである。例えば、有向グラフ制限手段４２は、以下の＜基準Ｂ１〜基準Ｂ３＞のいずれかによって有向グラフを選択する。
【００７１】
＜基準Ｂ１  辺の頻度による選択＞
有向グラフ制限手段４２は、有向グラフ生成手段４１で生成された有向グラフの中から、有向グラフの辺に付与された度数が、予め定めた頻度以下の辺の数が最小となる有向グラフを選択する。これによって、より使用頻度の高い表現テンプレートを生成することができる。
【００７２】
＜基準Ｂ２  頂点数による選択＞
有向グラフ制限手段４２は、有向グラフ生成手段４１で生成された有向グラフの中から、有効グラフの頂点の数が最小となる有向グラフを選択する。これによって、同一の要素が別の頂点となっている可能性を低くすることができる。
【００７３】
＜基準３  辺数による選択＞
有向グラフ制限手段４２は、有向グラフ生成手段４１で生成された有向グラフの中から、有効グラフの辺の数が最小となる有向グラフを選択する。これによって、基準Ｂ２と同様、同一の要素が別の頂点となっている可能性を低くすることができる。
【００７４】
以上説明したように表現テンプレート生成装置１を構成することで、動的計画法を用いたマルチプルアライメントにおいて、複数の最適経路を後段のアライメントへの入力とすることができるため、同一のアライメントコストを有するアライメント列によって再帰的にアライメントが行われることになる。これによって、表現テンプレート生成装置１は、マルチプルアライメントにおいて適切な解を途中で除去せずにアライメントを行うことができるため、複数のテキスト文書から、典型的な表現を示す表現テンプレートを精度よく生成することができる。
【００７５】
また、表現テンプレート生成装置１は、マルチプルアライメントにおいて、動的計画法における経路数を制限するため、指数関数的な経路数の増大を防止し、計算量を抑えることができる。
【００７６】
以上、表現テンプレート生成装置１の構成について説明したが、本発明はこれに限定されるものではない。ここでは、入力されるテキスト文書が予め形態素ごとに分割されていることとしたが、形態素ごとに分割されていないテキスト文書を入力する場合であれば、形態素の読み、品詞、活用型等を記憶した形態素辞書（図示せず）を参照して、形態素解析を行う形態素解析手段（図示せず）をさらに備え、テキスト文書を形態素ごとに分割したものをアライメントコスト算出手段１０への入力とすることとしてもよい。
【００７７】
また、表現テンプレート生成装置１は、図示を省略したＣＰＵやメモリを搭載した一般的なコンピュータで実現することができる。このとき、表現テンプレート生成装置１は、コンピュータを、前記した各手段として機能させる表現テンプレート生成プログラムによって動作する。
【００７８】
［表現テンプレート生成装置の動作］
次に、図７および図８を参照して、本発明の動作について説明する。図７は、本発明の実施の形態に係る表現テンプレート生成装置の全体動作を示すフローチャートである。図８は、本発明の実施の形態に係る表現テンプレート生成装置のアライメント列生成手段におけるアライメント動作を示すフローチャートである。
【００７９】
（全体動作）
最初に、図７を参照（構成については適宜図３参照）して、表現テンプレート生成装置１の全体動作について説明する。
【００８０】
まず、表現テンプレート生成装置１は、アライメントコスト算出手段１０によって、複数のテキスト文書のすべての２組ごとの組み合わせについて、２組ごとのテキスト文書の編集距離に基づいて、テキスト文書間の類似の度合を示すアライメントコストを算出する（ステップＳ１）。
【００８１】
そして、表現テンプレート生成装置１は、アライメントコスト算出手段１０によって、ステップＳ１で生成したアライメントコスト順に、２組のテキスト文書とアライメントコストとを対応付けたアライメントコスト一覧を生成し、アライメントコスト記憶手段２０に記憶する（ステップＳ２）。これによって、Ｍ系列のテキスト文書のすべての２組ごとの組み合わせ（ＭＣ２通り）について、アライメントコストの一覧が生成される。
【００８２】
その後、表現テンプレート生成装置１は、アライメント列生成手段３０によって、アライメントコスト記憶手段２０に記憶されているアライメントコストの低い２系列のテキスト文書から順に、動的計画法によりアライメントを行い、１つ以上の新たなアライメント列を生成する（ステップＳ３）。なお、このステップＳ３の動作については、図８を参照して後で説明することとする。
【００８３】
ステップＳ３の動作後、表現テンプレート生成装置１は、アライメント列生成手段３０によって、アライメントされた２系列のデータの内の一方のデータを、アライメントコスト記憶手段２０から削除する（ステップＳ４）。これによって、アライメント列生成手段３０は、アライメントが終わった一方の系列データを、動的計画法の対象から削除する。
【００８４】
そして、表現テンプレート生成装置１は、アライメントコスト記憶手段２０に記憶されているアライメントコスト一覧のデータの残りが１つになったか否かを判定する（ステップＳ５）。
【００８５】
ここでアライメントコスト一覧のデータの残りが２つ以上の場合（ステップＳ５でＮｏ）、表現テンプレート生成装置１は、ステップＳ３に戻って、次にアライメントコストが低い２系列のアライメント列についてアライメントを行う。
一方、アライメントコスト一覧のデータの残りが１つになった場合（ステップＳ５でＹｅｓ）、表現テンプレート生成装置１は、テンプレート生成手段４０の有向グラフ生成手段４１によって、ステップＳ３〜Ｓ４の動作によって生成された複数のアライメント系列から、要素を頂点とした有向グラフを生成する（ステップＳ６）
【００８６】
その後、表現テンプレート生成装置１は、有向グラフ制限手段４２によって、ステップＳ６で生成された有向グラフから、予め定めた基準に基づいて、最適な有向グラフを選択し、表現テンプレートとして出力する（ステップＳ７）。
【００８７】
以上の動作によって、表現テンプレート生成装置１は、複数の類似したテキスト文書から、典型的な表現を表現テンプレートとして生成することができる。
【００８８】
（アライメント動作）
次に、図８を参照（構成については適宜図３参照）して、表現テンプレート生成装置１のアライメント列生成手段におけるアライメント動作について説明する。この動作は、図７で説明したステップＳ３の動作に相当するものである。
【００８９】
まず、表現テンプレート生成装置１は、アライメント列生成手段３０の経路テーブル生成手段３１によって、アライメントコスト記憶手段２０から、最もアライメントコストの小さい２つのテキスト文書において、アライメント列を選択し、このアライメント列に含まれる２つのアライメントの要素列を２軸とする動的計画法の経路テーブルを生成する（ステップＳ３１）。なお、このとき、アライメント列生成手段３０は、動的計画法の経路テーブルのセルにおいて、各経路の編集距離（コスト）が異なる場合は、最適（コストが最小）な経路のみを当該セルに対応付けて記憶し、編集距離が同一である場合は、編集距離が同一の経路をすべて当該セルに対応付けて記憶する。これによって、トレースバック時に当該セルを経由する経路が１以上となる。
【００９０】
そして、表現テンプレート生成装置１は、経路逆探索手段３２によって、ステップＳ３１で生成された経路テーブルを逆探索（トレースバック）することで、複数のアライメント列を生成する（ステップＳ３２）。
【００９１】
そして、表現テンプレート生成装置１は、アライメント数制限手段３３によって、ステップＳ３２で生成されたアライメント列について、予め定めた基準に基づいて、生成するアライメント列数を制限する（ステップＳ３３）。
【００９２】
以上の動作によって、表現テンプレート生成装置１は、動的計画法において、複数の最適経路を保持する場合であっても、指数関数的な経路数の増大を防止し、典型的な表現として現れる言い回し表現を残したアライメント列を生成することができる。
【００９３】
［従来手法との比較］
最後に、図９を参照して、従来のマルチプルアライメントと、本発明の実施の形態に係る表現テンプレート生成装置１におけるマルチプルアライメントとの比較結果について説明する。なお、ここでは、ある放送番組に対する意見をテキスト文書として入力し、表現テンプレートを生成した比較を行っている。
【００９４】
図９は、有向グラフで表した表現テンプレートを示す図であって、（ａ）は従来手法により生成した表現テンプレート、（ｂ）は本発明の手法により生成した表現テンプレートを示している。図９において、頂点には要素（形態素）が、辺には頂点の接続が対応する。また、辺に付加されている数字は、この接続を通過する意見がいくつあったかを示している。
この図９に示した表現テンプレートに含まれる表現を表形式に表すと、以下の〔表１〕のように複数の表現が抽出される。
【００９５】
【表１】
0005022252.tif 000009
【００９６】
この〔表１〕に示すように、本発明のマルチプルアライメントによれば、文末に現れる「すごい」、「すばらしい」が、抽出されているが、従来の手法においては、これらが抽出されていない。これは、従来の手法では、動的計画法の経路テーブルにおいて、セルに保持する経路が１つであるため、当該経路が削除されたものと考えられる。このように、本発明の実施の形態に係る表現テンプレート生成装置は、従来の手法では抽出できなかった表現を適切に抽出し、表現テンプレートとして生成することができる。
【図面の簡単な説明】
【００９７】
【図１】文書分類判別システムの概略構成を示すブロック図である。
【図２】本発明の実施の形態に係る表現テンプレート生成装置が生成する表現テンプレートの一例を示す図である。
【図３】本発明の実施の形態に係る表現テンプレート生成装置の全体構成を示すブロック図である。
【図４】アライメントコスト記憶手段に記憶されるアライメントコスト一覧のデータ構造を示す構造図である。
【図５】経路テーブル生成手段が行う動的計画法の経路テーブルを生成する手法を説明するための説明図である。
【図６】経路逆探索手段が行う動的計画法の経路テーブルからアライメント列を生成する手法を説明するための説明図である。
【図７】本発明の実施の形態に係る表現テンプレート生成装置の全体動作を示すフローチャートである。
【図８】本発明の実施の形態に係る表現テンプレート生成装置のアライメント列生成手段におけるアライメント動作を示すフローチャートである。
【図９】有向グラフで表した表現テンプレートを示す図であって、（ａ）は従来手法により生成した表現テンプレート、（ｂ）は本発明の手法により生成した表現テンプレートを示している。
【符号の説明】
【００９８】
Ｓ      文書分類判別システム
１      表現テンプレート生成装置
２      表現テンプレート記憶装置
３      分類判別装置
１０    アライメントコスト算出手段
２０    アライメントコスト記憶手段
３０    アライメント列生成手段
３１    経路テーブル生成手段
３２    経路逆探索手段
３３    アライメント数制限手段
４０    テンプレート生成手段
４１    有向グラフ生成手段
４２    有向グラフ制限手段
【図１】
0005022252.tif 000010
【図２】
0005022252.tif 000011
【図３】
0005022252.tif 000012
【図４】
0005022252.tif 000013
【図５】
0005022252.tif 000014
【図６】
0005022252.tif 000015
【図７】
0005022252.tif 000016
【図８】
0005022252.tif 000017
【図９】
0005022252.tif 000018