(57)【特許請求の範囲】
【請求項１】
入力文書について予め生成された参照要約と、前記入力文書とに基づいて、前記入力文書から少なくとも１つの単語を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置であって、
前記入力文書の単語間の依存構造を解析する依存構造解析部と、
前記入力文書及び前記参照要約に共通する、Ｎ個の連続する単語であるＮグラムの集合に基づいて、前記要約候補の前記評価スコアを表す目的関数を生成する目的関数生成部と、
前記依存構造解析部によって解析された前記単語間の依存構造に基づいて、前記要約候補に含まれる単語間の制約を生成する制約生成部と、
前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である前記要約候補を、前記オラクル要約として探索するオラクル要約探索部と、
を含むオラクル要約探索装置。
【請求項２】
入力文書について予め生成された参照要約と、前記入力文書とに基づいて、前記入力文書から少なくとも１つの文節を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置であって、
前記入力文書の文節間の依存構造を解析する依存構造解析部と、
前記入力文書及び前記参照要約に共通する、Ｎ個の連続する文節であるＮグラムの集合に基づいて、前記要約候補の前記評価スコアを表す目的関数を生成する目的関数生成部と、
前記依存構造解析部によって解析された前記文節間の依存構造に基づいて、前記要約候補に含まれる文節間の制約を生成する制約生成部と、
前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である前記要約候補を、前記オラクル要約として探索するオラクル要約探索部と、
を含むオラクル要約探索装置。
【請求項３】
前記オラクル要約探索部は、前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である要約候補を探索する問題を、整数計画問題として解くことにより、前記オラクル要約を探索する請求項１又は２記載のオラクル要約探索装置。
【請求項４】
前記制約生成部は、前記要約候補に含まれる単語間の制約として、前記要約候補に含まれる単語の、前記依存構造解析部によって解析された前記単語間の依存構造を表す依存構造木における親の単語が含まれる制約を生成し、
前記入力文書及び前記参照要約に共通するＮグラムの集合に含まれるＮグラムｇｊｎの各々について、前記Ｎグラムｇｊｎの前記要約候補における頻度が、前記入力文書における前記Ｎグラムｇｊｎの頻度以下となる制約を生成し、
前記要約候補に含まれる前記入力文書のｕ番目のＮグラムに対応する、前記入力文書の各単語を、前記要約候補に含める制約を生成し、
前記要約候補が、前記要約長以下となる制約を生成する請求項１に記載のオラクル要約探索装置。
【請求項５】
前記制約生成部は、前記要約候補に含まれる文節間の制約として、前記要約候補に含まれる文節の、前記依存構造解析部によって解析された前記文節間の依存構造を表す依存構造木における親の文節が含まれる制約を生成し、
前記入力文書及び前記参照要約に共通するＮグラムの集合に含まれるＮグラムｇｊｎの各々について、前記Ｎグラムｇｊｎの前記要約候補における頻度が、前記入力文書における前記Ｎグラムｇｊｎの頻度以下となる制約を生成し、
前記要約候補に含まれる前記入力文書のｕ番目のＮグラムに対応する、前記入力文書の各文節を、前記要約候補に含める制約を生成し、
前記要約候補が、前記要約長以下となる制約を生成する請求項２に記載のオラクル要約探索装置。
【請求項６】
入力文書について予め生成された参照要約と、前記入力文書とに基づいて、前記入力文書から少なくとも１つの単語を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置におけるオラクル要約探索方法であって、
依存構造解析部が、前記入力文書の単語間の依存構造を解析するステップと、
目的関数生成部が、前記入力文書及び前記参照要約に共通する、Ｎ個の連続する単語であるＮグラムの集合に基づいて、前記要約候補の前記評価スコアを表す目的関数を生成するステップと、
制約生成部が、前記依存構造解析部によって解析された前記単語間の依存構造に基づいて、前記要約候補に含まれる単語間の制約を生成するステップと、
オラクル要約探索部が、前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である前記要約候補を、前記オラクル要約として探索するステップと、
を含むオラクル要約探索方法。
【請求項７】
入力文書について予め生成された参照要約と、前記入力文書とに基づいて、前記入力文書から少なくとも１つの文節を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置におけるオラクル要約探索方法であって、
依存構造解析部が、前記入力文書の文節間の依存構造を解析するステップと、
目的関数生成部が、前記入力文書及び前記参照要約に共通する、Ｎ個の連続する文節であるＮグラムの集合に基づいて、前記要約候補の前記評価スコアを表す目的関数を生成するステップと、
制約生成部が、前記依存構造解析部によって解析された前記文節間の依存構造に基づいて、前記要約候補に含まれる文節間の制約を生成するステップと、
オラクル要約探索部が、前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である前記要約候補を、前記オラクル要約として探索するステップと、
を含むオラクル要約探索方法。
【請求項８】
コンピュータを、請求項１〜請求項５のいずれか１項に記載のオラクル要約探索装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オラクル要約探索装置、方法、及びプログラムに係り、特に、要約候補からオラクル要約を探索するためのオラクル要約探索装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
要約の品質を評価手法として、人間が生成した要約（以降、参照要約と記載する）とシステム要約との間で共通するＮグラム(以降、ＮグラムとはＮ個の連続した単語列をさす)数に着目した評価法であるＲｏｕｇｅスコア(非特許文献１参照）が広く用いられる。
【０００３】
Ｒを参照要約、Ｓをシステム要約、ＧＲを参照要約に出現するＮグラム集合とする。
【０００４】
Ｃ（ｇｊｎ，Ｒ），Ｃ（ｇｊｎ，Ｓ）をそれぞれＧＲ中のｊ番目のＮグラムｇｊｎの参照要約Ｒ、及びシステム要約Ｓの各々における頻度とすると、ＲとＳとの間のＲｏｕｇｅｎスコアは、以下の（１）式で定義される。
【０００５】
【数１】
0006461832.tif 000002
【０００６】
単語抽出のオラクル要約とは、ある長さの制約（要約長の制約）のもと上記（１）式を最大化するように文の文法性を損なうことなく文書から単語を抽出することで生成した要約である。
【０００７】
一方、ある長さ制約のもと上記（１）式を最大化するように文を抽出することで生成した要約である文抽出のオラクル要約に関しては非特許文献２にて解法が提案されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Lin Chin-Yew. 2004. ROUGE: A Package for Automatic Evaluation of Summaries. In Proc. of Workshop on Text Summarization Branches Out, pages 7481.
【非特許文献２】平尾努，西野正彬，鈴木潤，永田昌明, “オラクル要約の列挙”, 第20回言語処理学会年次大会, pp.650-653(2014)
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、単語抽出のオラクル要約を求める問題はＮＰ困難であり、これまでに解を求める手法は提案されていない。
【００１０】
また、非特許文献２において、文抽出と単語抽出では文書から抜き出す単位が異なるため、文抽出オラクルを単語抽出による要約システムのエラー分析やパラメタチューニング用の訓練データに用いることは適切でない。
【００１１】
近年、自動要約の研究分野では文抽出による要約生成から単語抽出による要約生成へとパラダイムが変化しつつある。他の自然言語処理分野と同様、自動要約の研究分野でもシステムのパラメタのチューニングにはいわゆる訓練データが欠かせない。たとえば、要約システムのパラメタチューニングにおいては現在のパラメタで出力したシステム要約とオラクル要約との間のＲｏｕｇｅスコアの差を損失スコアして用いる。しかし、システムが単語抽出であるにもかかわらず、文抽出のオラクル要約を用いて計算した損失スコアが適切であるとは言いがたい。さらに、単語抽出型のシステムのエラー分析に文抽出のオラクル要約を利用することも適切とは言いがたい。
【００１２】
本発明は、上記問題点を解決するために成されたものであり、文の文法性を損なうことなく、文に含まれる単語又は文節を抽出することにより生成したオラクル要約を探索することができるオラクル要約探索装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、第１の発明に係るオラクル要約探索装置は、入力文書について予め生成された参照要約と、前記入力文書とに基づいて、前記入力文書から少なくとも１つの単語を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置であって、前記入力文書の単語間の依存構造を解析する依存構造解析部と、前記入力文書及び前記参照要約に共通する、Ｎ個の連続する単語であるＮグラムの集合に基づいて、前記要約候補の前記評価スコアを表す目的関数を生成する目的関数生成部と、前記依存構造解析部によって解析された前記単語間の依存構造に基づいて、前記要約候補に含まれる単語間の制約を生成する制約生成部と、前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である前記要約候補を、前記オラクル要約として探索するオラクル要約探索部と、を含んで構成されている。
【００１４】
第２の発明に係るオラクル要約探索装置は、入力文書について予め生成された参照要約と、前記入力文書とに基づいて、前記入力文書から少なくとも１つの文節を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置であって、前記入力文書の文節間の依存構造を解析する依存構造解析部と、前記入力文書及び前記参照要約に共通する、Ｎ個の連続する文節であるＮグラムの集合に基づいて、前記要約候補の前記評価スコアを表す目的関数を生成する目的関数生成部と、前記依存構造解析部によって解析された前記文節間の依存構造に基づいて、前記要約候補に含まれる文節間の制約を生成する制約生成部と、前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である前記要約候補を、前記オラクル要約として探索するオラクル要約探索部と、を含んで構成されている。
【００１５】
また、第１及び第２の発明に係るオラクル要約探索装置において、前記オラクル要約探索部は、前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である要約候補を探索する問題を、整数計画問題として解くことにより、前記オラクル要約を探索するようにしてもよい。
【００１６】
また、第１の発明に係るオラクル要約探索装置において、前記制約生成部は、前記要約候補に含まれる単語間の制約として、前記要約候補に含まれる単語の、前記依存構造解析部によって解析された前記単語間の依存構造を表す依存構造木における親の単語が含まれる制約を生成し、前記入力文書及び前記参照要約に共通するＮグラムの集合に含まれるＮグラムｇｊｎの各々について、前記Ｎグラムｇｊｎの前記要約候補における頻度が、前記入力文書における前記Ｎグラムｇｊｎの頻度以下となる制約を生成し、前記要約候補に含まれる前記入力文書のｕ番目のＮグラムに対応する、前記入力文書の各単語を、前記要約候補に含める制約を生成し、前記要約候補が、前記要約長以下となる制約を生成するようにしてもよい。
【００１７】
また、第２の発明に係るオラクル要約探索装置において、前記制約生成部は、前記要約候補に含まれる文節間の制約として、前記要約候補に含まれる文節の、前記依存構造解析部によって解析された前記文節間の依存構造を表す依存構造木における親の文節が含まれる制約を生成し、前記入力文書及び前記参照要約に共通するＮグラムの集合に含まれるＮグラムｇｊｎの各々について、前記Ｎグラムｇｊｎの前記要約候補における頻度が、前記入力文書における前記Ｎグラムｇｊｎの頻度以下となる制約を生成し、前記要約候補に含まれる前記入力文書のｕ番目のＮグラムに対応する、前記入力文書の各文節を、前記要約候補に含める制約を生成し、前記要約候補が、前記要約長以下となる制約を生成するようにしてもよい。
【００１８】
第３の発明に係るオラクル要約探索方法は、入力文書について予め生成された参照要約と、前記入力文書とに基づいて、前記入力文書から少なくとも１つの単語を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置におけるオラクル要約探索方法であって、依存構造解析部が、前記入力文書の単語間の依存構造を解析するステップと、目的関数生成部が、前記入力文書及び前記参照要約に共通する、Ｎ個の連続する単語であるＮグラムの集合に基づいて、前記要約候補の前記評価スコアを表す目的関数を生成するステップと、制約生成部が、前記依存構造解析部によって解析された前記単語間の依存構造に基づいて、前記要約候補に含まれる単語間の制約を生成するステップと、オラクル要約探索部が、前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である前記要約候補を、前記オラクル要約として探索するステップと、を含んで実行することを特徴とする。
【００１９】
第４の発明に係るオラクル要約探索方法は、入力文書について予め生成された参照要約と、前記入力文書とに基づいて、前記入力文書から少なくとも１つの文節を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置におけるオラクル要約探索方法であって、依存構造解析部が、前記入力文書の文節間の依存構造を解析するステップと、目的関数生成部が、前記入力文書及び前記参照要約に共通する、Ｎ個の連続する文節であるＮグラムの集合に基づいて、前記要約候補の前記評価スコアを表す目的関数を生成するステップと、制約生成部が、前記依存構造解析部によって解析された前記文節間の依存構造に基づいて、前記要約候補に含まれる文節間の制約を生成するステップと、オラクル要約探索部が、前記制約生成部によって生成された制約を満たし、かつ、前記目的関数生成部によって生成された前記目的関数の値を最大化する、前記要約長以下である前記要約候補を、前記オラクル要約として探索するステップと、を含んで実行することを特徴とする。
【００２０】
第５の発明に係るプログラムは、コンピュータを、上記第１又は第２のオラクル要約探索装置の各部として機能させるためのプログラムである。
【発明の効果】
【００２１】
本発明のオラクル要約探索装置、方法、及びプログラムによれば、文の文法性を損なうことなく、文に含まれる単語又は文節を抽出することにより生成したオラクル要約を探索することができる、という効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】本発明の第１の実施の形態に係るオラクル要約探索装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態に係るオラクル要約探索装置におけるオラクル要約探索処理ルーチンを示すフローチャートである。
【図３】文分割、及び単語分割された入力文書の一例を示す図である。
【図４】入力文書の文書中の文に対する依存構造木の一例を示す図である。
【図５】文分割、及び単語分割された参照要約の一例を示す図である。
【図６】オラクル要約の一例を示す図である。
【図７】本発明の第２の実施の形態に係るオラクル要約探索装置の構成を示すブロック図である。
【図８】本発明の第２の実施の形態に係るオラクル要約探索装置におけるオラクル要約探索処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２４】
＜本発明の実施の形態の概要＞
【００２５】
本発明の第１の実施の形態は、参照要約とその元となった文書又は文書群が与えられた時、文書から文の文法性を損なうことなく単語を抽出することで要約を生成する手法に基づき、要約の品質を評価する関数であるＲｏｕｇｅを最大化する単語抽出要約（単語抽出のオラクル要約）を探索する技術に関する。また、第２の実施の形態は文節抽出要約（文節抽出のオラクル要約）を探索する技術に関する。本実施の形態の技術は、たとえば、自動要約システムのパラメタチューニング用訓練データや自動要約システムのエラー分析などに用いられる。
＜本発明の第１の実施の形態に係るオラクル要約探索装置の構成＞
【００２６】
まず、本発明の第１の実施の形態に係るオラクル要約探索装置の構成について説明する。
本発明の第１の実施の形態に係るオラクル要約探索装置は、以下に説明する構成により、入力文書について人間が予め生成した参照要約と、入力文書とに基づいて、入力文書から少なくとも１つの単語を選択して生成される、予め定められた要約長以下であって、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置である。
【００２７】
図１に示すように、本発明の第１の実施の形態に係るオラクル要約探索装置１００は、ＣＰＵと、ＲＡＭと、後述するオラクル要約探索処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このオラクル要約探索装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００２８】
入力部１０は、入力文書と、入力文書について人間が予め生成した参照要約とを受け付ける。なお、入力文書群と、入力文書群のそれぞれの入力文書について予め生成された参照要約群を受け付けるようにしてもよい。
【００２９】
演算部２０は、文分割部３０と、単語分割部３２と、Ｎグラム抽出部３４と、依存構造解析部３６と、解探索部３８とを含んで構成されている。
【００３０】
文分割部３０は、入力文書と参照要約との各々を文に分割する。既存の文分割器を利用すればよい。英語の場合にはピリオド、日本語の場合には句点を手がかりとするだけでもよい。
【００３１】
単語分割部３２は、文分割部３０で分割された、入力文書と参照要約との各々の文を入力として受け取り、文の各々を単語へと分割する。英語の場合にはスペース区切りで単語へ分割、日本語の場合には既存のわかち書きツールを利用すればよい。
【００３２】
Ｎグラム抽出部３４は、単語分割部３２で単語に分割された文を受け取り、各文から文を超えない範囲で、Ｎ個の連続する単語であるＮグラムを抽出する。
【００３３】
依存構造解析部３６は、単語分割部３２で単語に分割された入力文書を受け取り、入力文書の各文の単語間の依存構造を解析する。ここで、依存構造解析には既存の解析器を用いて、わかち書きされた文を受け取り単語間の依存構造を反映した木を生成する。なお、依存構造解析部３６によって、入力文書中の単語には先頭から末尾かけてインデックスが割りあてられているものとする。また、入力文書中のＮグラムに対しても同様にインデックスが割りあてられているものとする。
【００３４】
解探索部３８は、目的関数生成部４０と、制約生成部４２と、オラクル要約探索部４４とを含んで構成されている。
【００３５】
解探索部３８は、まず、目的関数生成部４０において、Ｎグラム抽出部３４で抽出した、入力文書及び参照要約に共通する、Ｎ個の連続する単語であるＮグラムの集合に基づいて、要約候補の評価スコアを表す目的関数を生成する。次に、依存構造解析部３６によって解析された単語間の依存構造に基づいて、要約候補に含まれる単語間の制約を生成する。そして、オラクル要約探索部４４において、制約生成部４２によって生成された制約を満たし、かつ、目的関数生成部４０によって生成された目的関数の値を最大化する、要約長以下である要約候補を探索する問題を、整数計画問題として解くことにより、オラクル要約を探索する。
【００３６】
目的関数生成部４０と、制約生成部４２と、オラクル要約探索部４４とは、具体的には以下に説明する処理を行う。
【００３７】
まず、目的関数生成部４０における目的関数の生成処理を説明する。
【００３８】
入力文書と参照要約とに共通するＮグラムの集合を
【００３９】
【数２】
0006461832.tif 000003
【００４０】
とし、ＺｊをＮグラムｇｊｎの要約候補における頻度とする。上記（１）式より、分母は参照要約のＮグラム数であるので、Ｒが与えられた時点で決定する定数であることに注意すると、Ｒｏｕｇｅを最大化するためには分子を最大化すればよいことがわかる。よって、目的関数を以下（２）式に従って生成する。
【００４１】
【数３】
0006461832.tif 000004
【００４２】
ただし、Ｚｊはゼロ以上の整数である。
【００４３】
次に、制約生成部４２の制約生成処理について説明する。制約生成部４２は、次の第１〜第４の制約を生成する。
【００４４】
まず、上記（１）式の分子を最大化するには、（１）式より、Ｎグラムｇｊｎの参照要約における頻度、又は要約候補における頻度のどちらか小さい方の値の和を最大化しなければならない。
【００４５】
そこで、制約生成部４２は、第１の制約として、依存構造解析部３６で解析された単語間の依存構造に基づいて、入力文書及び参照要約に共通するＮグラムの集合に含まれるＮグラムｇｊｎの各々について、Ｎグラムｇｊｎの要約候補における頻度が、入力文書におけるＮグラムｇｊｎの頻度以下となる制約を表す、以下の（３）式に示す制約条件を生成する。
【００４６】
【数４】
0006461832.tif 000005
【００４７】
ただし、入力文書中でｊ番目のＮグラムｇｊｎが出現する文番号とｇｊｎの位置をあらわすインデックスのタプル集合を
【００４８】
【数５】
0006461832.tif 000006
【００４９】
とする。そして、ｉ番目の文のｖ番目のＮグラムを要約候補に含めるか否かをあらわす０又は１の変数をｍｉ，ｖとする。上記（３）式の制約条件により、要約候補のＮグラムｇｊｎの頻度は参照要約における頻度Ｃ（ｇｊｎ，Ｒ）以下となり、また、文集合全体でとることのできる最大頻度は
【００５０】
【数６】
0006461832.tif 000007
【００５１】
以下となる。
【００５２】
上記制約条件はＮグラムに関するものであるが、要約は単語の抽出により生成するため、単語とＮグラムの関係を制約として記述しなければならない。また、ｉ番目の文のｖ番目のＮグラムをオラクル要約に選択する場合には、そのＮグラムに含まれるすべての単語もオラクル要約に含めなければならない。
【００５３】
そこで、制約生成部４２は、第２の制約として、要約候補に含まれる入力文書のｕ番目のＮグラムに対応する、入力文書の各単語を、要約候補に含める制約を表す、以下（４）式に示す制約条件を生成する。
【００５４】
【数７】
0006461832.tif 000008
【００５５】
ここで、ｔｉ，ｕは、ｉ番目文のｕ番目の単語を要約に含めるか否かをあらわす０又は１値変数であり、ｌｅｆｔ（ｉ，ｖ）は、ｉ番目の文のｖ番目のＮグラムの左端の単語インデックスを返し、ｒｉｇｈｔ（ｉ，ｖ）は右端の単語インデックスを返す関数である。
【００５６】
このままでは、単語を要約候補に含めるか否かを他の単語とは無関係に決定できるため、抽出した単語列が文法に適合するとは限らない。
【００５７】
そこで、制約生成部４２は、依存構造解析部３６で解析された単語間の依存構造に基づいて、第３の制約として、要約候補に含まれる単語の、依存構造解析部３６によって解析された単語間の依存構造を表す依存構造木における親の単語が含まれる制約を表す以下（５）式に示す制約条件を生成し、要約候補に含まれる単語間に依存関係が成立するようにする。
【００５８】
【数８】
0006461832.tif 000009
【００５９】
ただし、ｐａｒｅｎｔ（ｉ）は、ｉ番目の文のｕ番目の単語の依存構造木における親の単語のインデックスをあらわす。ｉ番目の文のｕ番目の単語が依存構造木のルートである場合には上記制約は考慮しない。
【００６０】
さらに、制約生成部４２は、依存構造解析部３６で解析された単語間の依存構造に基づいて、第４の制約として、要約候補が、要約長以下となる制約を表す以下（６）式に示す制約条件を生成する。一般的に長さの制約は参照要約の単語数ＬＲに設定する。
【００６１】
【数９】
0006461832.tif 000010
【００６２】
Ｅ（ｉ）は、ｉ番目の文の最終単語の単語インデックス、ｌｉ，ｕはｉ番目の文のｕ番目の単語の長さを表す。要約長を単語数で与える場合にはｌｉ，ｕは常に１となり、文字数やバイト数で与える場合にはそれぞれの単位で与える。
【００６３】
なお、制約生成部４２において、本実施の形態の拡張として、抽出する単語の数をある数Ｋ以上にしたい場合、以下（７）〜（９）式の制約条件を更に生成すればよい。
【００６４】
【数１０】
0006461832.tif 000011
【００６５】
ａｉ，１、ａｉ，２は０又は１の変数であり、（７）式は、ａｉ，１＝１のとき、ｉ番目の文から抽出する単語数がＫ以上であることを保証する制約である。（８）式は、ａｉ，２＝１のとき、ｉ番目の文からは単語を抽出しないことを保証する制約である。（９）式は、ａｉ，１，ａｉ，２のどちらか一方が必ず１をとることで、ｉ番目の文から単語を抽出する際その数がＫ以上であることを保証する制約である。
【００６６】
次に、オラクル要約探索部４４におけるオラクル要約の探索処理を説明する。
【００６７】
上記（２）式の目的関数と上記（３）〜（６）式の制約条件とをまとめると、以下の（１０）式に示す整数計画問題となる。
【００６８】
【数１１】
0006461832.tif 000012
【００６９】
上記（３）〜（６）式により生成した制約条件を満たし、かつ、上記（２）式により求めた目的関数の値を最大化する、要約候補のＮグラムｇｊｎの頻度の集合Ｚ、ｉ番目の文のｖ番目のＮグラムを要約候補に含めるか否かを表す変数の集合ｍ、ｉ番目の文のｕ番目の単語を要約候補に含めるか否かを表す変数の集合ｔを、整数計画ソルバを用いて求める。整数計画ソルバは既存技術を利用する。Ｚより、目的関数スコアが決定され、要約候補であるオラクル要約のＲｏｕｇｅスコアが決定される。変数の集合ｔより、オラクル要約そのものが決定される。
【００７０】
＜本発明の第１の実施の形態に係るオラクル要約探索装置の作用＞
【００７１】
次に、本発明の第１の実施の形態に係るオラクル要約探索装置１００の作用について説明する。入力部１０において入力文書と、入力文書について予め生成された参照要約を受け付けると、オラクル要約探索装置１００は、図２に示すオラクル要約探索処理ルーチンを実行する。
【００７２】
まず、ステップＳ１００では、入力部１０において受け付けた入力文書と参照要約との各々を文に分割する。
【００７３】
次に、ステップＳ１０２では、ステップＳ１００で分割された、入力文書、及び参照要約の文の各々を、単語へと分割する。
【００７４】
ステップＳ１０４では、ステップＳ１０２で単語に分割された入力文書及び参照要約の各々について、各文から文を超えない範囲で、Ｎ個の連続する単語であるＮグラムを抽出する。
【００７５】
ステップＳ１０６では、ステップＳ１０２で単語に分割された入力文書について、入力文書の各文の単語間の依存構造を解析し、依存構造を反映した木を生成する。
【００７６】
ステップＳ１０８では、ステップＳ１０４で抽出した、入力文書及び参照要約に共通する、Ｎ個の連続する単語であるＮグラムの集合Ｇに基づいて、上記（２）式に従って、要約候補の評価スコアを表す目的関数を生成する。
【００７７】
ステップＳ１１０では、上記（３）式に従って、入力文書及び参照要約に共通するＮグラムの集合に含まれるＮグラムｇｊｎの各々について、Ｎグラムｇｊｎの要約候補における頻度が、入力文書におけるＮグラムｇｊｎの頻度以下となる制約を生成する。
【００７８】
ステップＳ１１２では、上記（４）式に従って、要約候補に含まれる入力文書のｕ番目のＮグラムに対応する、入力文書の各単語を、要約候補に含める制約を生成する。
【００７９】
ステップＳ１１４では、ステップＳ１０６で解析された単語間の依存構造に基づいて、上記（５）式に従って、要約候補に含まれる単語の、依存構造解析部３６によって解析された単語間の依存構造を表す依存構造木における親の単語が含まれる制約を生成する。
【００８０】
ステップＳ１１６では、上記（６）式に従って、要約候補が、要約長以下となる制約を生成する。
【００８１】
ステップＳ１１８では、ステップＳ１１０〜Ｓ１１６によって生成された制約を満たし、かつ、ステップＳ１０８によって生成された目的関数の値を最大化する要約候補を探索する問題を、整数計画問題として解くことにより、オラクル要約を探索する。
【００８２】
ステップＳ１２０では、ステップＳ１１８で探索されたオラクル要約を出力部５０に出力し、処理を終了する。
【００８３】
＜第１の実施の形態に係る具体的な実験例＞
【００８４】
第１の実施の形態に係る実験結果を説明する。文分割、及び単語分割された入力文書（図３）、入力文書の文書中の文に対する依存構造木（図４）、文分割、及び単語分割された参照要約（図５）が与えられたとする。いま、Ｎグラムの長さを２とする(バイグラム) と、入力文書と参照要約に共通して出現するバイグラム集合はＧ＝｛ａａ，ａｂ，ｂｂ，ｂｃ｝となる。よって、目的関数生成部４０によって生成される目的関数は次式となる。
【００８５】
【数１２】
0006461832.tif 000013
【００８６】
また、図３より、単語と単語のインデックスとの関係は以下の表１のとおりとなる。
【００８７】
【表１】
0006461832.tif 000014
【００８８】
バイグラムとバイグラムのインデックスとの関係は以下の表２のとおりとなる。
【００８９】
【表２】
0006461832.tif 000015
【００９０】
次に制約生成部４２によって生成される制約を説明する。上記バイグラム「ａａ」の参照要約における頻度は２、入力文書での出現位置（バイグラムインデックス）は（２，１）、「ａｂ」の参照要約における頻度は１、入力文書での出現位置は（１，１）と（１，４）、「ｂｂ」の参照要約における頻度は１、入力文書での出現位置は（２，４）と（３，２）、「ｂｃ」の参照要約における頻度は１、入力文書での出現位置は（１，２）と（２，５）であることから、上記（３）式に従って、以下の制約条件を生成する。
【００９１】
【数１３】
0006461832.tif 000016
【００９２】
さらに、上記（４）式に従って単語とバイグラムに関する以下の制約条件を生成する。
【００９３】
【数１４】
0006461832.tif 000017
【００９４】
また、図４より上記（５）式に従って単語間の依存関係に関する以下の制約条件を生成する。
【００９５】
【数１５】
0006461832.tif 000018
【００９６】
さらに、参照要約の単語数が８単語であることから、上記（６）式に従って以下の制約条件を生成する。
【００９７】
【数１６】
0006461832.tif 000019
【００９８】
以上の制約を満たすように、上記（１１）式に従って生成した目的関数の値を整数計画ソルバを用いて求めると、Ｚ１＝１、Ｚ２＝１、Ｚ４＝１となり、図６に示すように単語はｔ１，４、ｔ１，５、ｔ２，１、ｔ２，２、ｔ２，４、ｔ２，５、ｔ２，６がオラクル要約として選択される。なお、オラクル要約のＲｏｕｇｅスコアは、参照要約のバイグラム数が６であることから、３／６となる。
【００９９】
以上説明したように、第１の実施の形態に係るオラクル要約探索装置によれば、入力文書の単語間の依存構造を解析し、入力文書及び参照要約に共通する、Ｎ個の連続する単語であるＮグラムの集合に基づいて、要約候補の評価スコアを表す目的関数を生成し、単語間の依存構造に基づいて、要約候補に含まれる単語間の制約を生成し、生成された制約を満たし、かつ、目的関数の値を最大化する、要約長以下である要約候補を、オラクル要約として探索することにより、文の文法性を損なうことなく、文に含まれる単語を抽出することにより生成したオラクル要約を探索することができる。
【０１００】
＜本発明の第２の実施の形態に係るオラクル要約探索装置の構成＞
【０１０１】
次に、本発明の第２の実施の形態に係るオラクル要約探索装置の構成について説明する。文節を選択してオラクル要約を探索する点が第１の実施の形態と異なっている。日本語の場合、単語間ではなく文節間に依存関係を定義する場合もあり、文節抽出によるオラクル要約を求めるための整数計画問題を示す必要がある。なお、第１の実施の形態と同様となる箇所については同一符号を付して説明を省略する。
【０１０２】
図７に示すように、本発明の第２の実施の形態に係るオラクル要約探索装置２００は、ＣＰＵと、ＲＡＭと、後述するオラクル要約探索処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このオラクル要約探索装置２００は、機能的には図７に示すように入力部１０と、演算部２２０と、出力部５０とを備えている。
【０１０３】
演算部２２０は、文分割部３０と、文節分割部２３２と、Ｎグラム抽出部２３４と、依存構造解析部２３６と、解探索部２３８とを含んで構成されている。
【０１０４】
文節分割部２３２は、文分割部３０で分割された、入力文書と参照要約との各々の文を入力として受け取り、文の各々を文節へと分割する。
【０１０５】
Ｎグラム抽出部２３４は、文節分割部２３２で文節に分割された文を受け取り、各文から文を超えない範囲で、Ｎ個の連続する文節であるＮグラムを抽出する。
【０１０６】
依存構造解析部２３６は、文節分割部２３２で文節に分割された入力文書を受け取り、入力文書の各文の文節間の依存構造を解析する。
【０１０７】
解探索部２３８は、目的関数生成部２４０と、制約生成部２４２と、オラクル要約探索部２４４とを含んで構成されている。
【０１０８】
解探索部２３８は、まず、目的関数生成部４０において、Ｎグラム抽出部３４で抽出した、入力文書及び参照要約に共通する、Ｎ個の連続する文節であるＮグラムの集合に基づいて、要約候補の評価スコアを表す目的関数を生成する。次に、依存構造解析部２３６によって解析された文節間の依存構造に基づいて、要約候補に含まれる文節間の制約を生成する。そして、オラクル要約探索部４４において、制約生成部４２によって生成された制約を満たし、かつ、目的関数生成部４０によって生成された目的関数の値を最大化する、要約長以下である要約候補を探索する問題を、整数計画問題として解くことにより、オラクル要約を探索する。
【０１０９】
目的関数生成部２４０は、第１の実施の形態と同様の処理により、目的関数を上記（２）式に従って生成する。
【０１１０】
制約生成部２４２と、オラクル要約探索部２４４とは、具体的には以下に説明する処理を行う。
【０１１１】
制約生成部２４２は、第１の実施の形態と同様に、第１〜第４の制約を生成する。ここでは第１の実施の形態と異なる箇所についてのみ述べる。
【０１１２】
次に、制約生成部２４２は、第２の制約として、上記（４）式と同様に、要約候補に含まれる入力文書のｕ番目のＮグラムに対応する、入力文書の各文節を、要約候補に含める制約を表す制約条件を生成する。ここで、上記（４）式におけるｔｉ，ｕをｂｉ，ｕに置き換える。ｂｉ，ｕは入力文書中のｉ番目の文のｕ番目の文節を要約候補に選択するか否かをあらわす２値変数である。第３、第４の制約についても同様にｔｉ，ｕをｂｉ，ｕに置き換える。
【０１１３】
次に、制約生成部２４２は、依存構造解析部２３６で解析された文節間の依存構造に基づいて、上記（５）式と同様に、第３の制約として、要約候補に含まれる文節の、依存構造解析部２３６によって解析された文節間の依存構造を表す依存構造木における親の文節が含まれる制約を表す制約条件を生成し、要約候補に含まれる文節間に依存関係が成立するようにする。
【０１１４】
次に、オラクル要約探索部４４におけるオラクル要約の探索処理を説明する。
【０１１５】
第２の実施の形態において、上記（２）式の目的関数と上記第１の制約〜第４の制約を示す制約条件とをまとめると、以下の（１２）式に示す整数計画問題となる。
【０１１６】
【数１７】
0006461832.tif 000020
【０１１７】
ここで、ｌｉ，ｕはｉ番目の文のｕ番目の文節の単語数である。第１の実施の形態の上記（１０）式との違いは単語ではなく文節を選択して要約を生成することから長さ制約がｂを用いて表されていること（制約１行目）、文節間の依存関係がｂの間に定義されること（制約２行目）、ＮグラムインデックスとＮグラムｇｊｎが出現する文節インデックスの間の関係（制約５行目）が制約となっていることである。Ｂ＿ｌｅｆｔ（ｉ，ｖ）は、ｉ番目の文のｖ番目のＮグラムの左端の単語を含む文節のインデックス、Ｂ＿ｒｉｇｈｔ（ｉ，ｖ）は、ｉ番目の文のｖ番目のＮグラムの右端の単語を含む文節のインデックスを返す。よって、ｉ番目の文のｖ番目のＮグラムをオラクル要約に選択する際、そのＮグラムが出現するすべての文節を選択しなければならないことを示す。
【０１１８】
＜本発明の実施の形態に係るオラクル要約探索装置の作用＞
【０１１９】
次に、本発明の第２の実施の形態に係るオラクル要約探索装置２００の作用について説明する。なお、第１の実施の形態と同様の作用となる箇所については、同一符号を付して説明を省略する。
【０１２０】
入力部１０において入力文書と、入力文書について予め生成された参照要約を受け付けると、オラクル要約探索装置２００は、図８に示すオラクル要約探索処理ルーチンを実行する。
【０１２１】
ステップＳ２０２では、ステップＳ１００で分割された、入力文書、及び参照要約の文の各々を、文節へと分割する。
【０１２２】
ステップＳ２０４では、ステップＳ２０２で文節に分割された入力文書及び参照要約の各々について、各文から文を超えない範囲で、Ｎ個の連続する単語であるＮグラムを抽出する。
【０１２３】
ステップＳ２０６では、ステップＳ２０２で文節に分割された入力文書について、入力文書の各文の文節間の依存構造を解析し、依存構造を反映した木を生成する。
【０１２４】
ステップＳ２０８では、ステップＳ２０４で抽出した、入力文書及び参照要約に共通する、Ｎ個の連続する単語であるＮグラムの集合Ｇに基づいて、上記（２）式に従って、要約候補の評価スコアを表す目的関数を生成する。
【０１２５】
ステップＳ２１０では、上記（３）式に従って、入力文書及び参照要約に共通するＮグラムの集合に含まれるＮグラムｇｊｎの各々について、Ｎグラムｇｊｎの要約候補における頻度が、入力文書におけるＮグラムｇｊｎの頻度以下となる制約を生成する。
【０１２６】
ステップＳ２１２では、上記（４）式に従って、要約候補に含まれる入力文書のｕ番目のＮグラムに対応する、入力文書の各文節を、要約候補に含める制約を生成する。
【０１２７】
ステップＳ２１４では、ステップＳ２０６で解析された文節間の依存構造に基づいて、上記（５）式に従って、要約候補に含まれる文節の、依存構造解析部２３６によって解析された文節間の依存構造を表す依存構造木における親の文節が含まれる制約を生成する。
【０１２８】
ステップＳ２１６では、上記（６）式に従って、要約候補が、要約長以下となる制約を生成する。
【０１２９】
ステップＳ２１８では、ステップＳ２１０〜Ｓ２１６によって生成された制約を満たし、かつ、ステップＳ２０８によって生成された目的関数の値を最大化する要約候補を探索する問題を、整数計画問題として解くことにより、オラクル要約を探索する。
【０１３０】
ステップＳ２２０では、ステップＳ２１８で探索されたオラクル要約を出力部５０に出力し、処理を終了する。
【０１３１】
以上説明したように、第２の実施の形態に係るオラクル要約探索装置によれば、入力文書の文節間の依存構造を解析し、入力文書及び参照要約に共通する、Ｎ個の連続する文節であるＮグラムの集合に基づいて、要約候補の評価スコアを表す目的関数を生成し、文節間の依存構造に基づいて、要約候補に含まれる文節間の制約を生成し、生成された制約を満たし、かつ、目的関数の値を最大化する、要約長以下である要約候補を、オラクル要約として探索することにより、文の文法性を損なうことなく、文に含まれる文節を抽出することにより生成したオラクル要約を探索することができる。
【０１３２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１３３】
例えば、上述した実施の形態では、文分割部と、単語分割部又は文節分割部との各部の処理を行う場合を例に説明したが、予め入力文書、及び参照要約を文を分割し、更に単語又は文節に分割したものを入力部１０で受け付けるようにしてもよい。この場合には、文分割部と、単語分割部又は文節分割部とを省略することができる。
【符号の説明】
【０１３４】
１０   入力部
２０、２２０  演算部
３０   文分割部
３２   単語分割部
３４、２３４  Ｎグラム抽出部
３６、２３６  依存構造解析部
３８、２３８  解探索部
４０、２４０  目的関数生成部
４２、２４２  制約生成部
４４、２４４  オラクル要約探索部
５０   出力部
１００、２００       オラクル要約探索装置
２３２ 文節分割部
【図１】
0006461832.tif 000021
【図２】
0006461832.tif 000022
【図３】
0006461832.tif 000023
【図４】
0006461832.tif 000024
【図５】
0006461832.tif 000025
【図６】
0006461832.tif 000026
【図７】
0006461832.tif 000027
【図８】
0006461832.tif 000028