(57)【特許請求の範囲】
【請求項１】
入力された、要約元文書から少なくとも１つの文字列単位を選択して予め生成された参照要約と、前記要約元文書とに基づいて、前記要約元文書から少なくとも１つの前記文字列単位を選択して生成される複数の要約候補から、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置であって、
前記参照要約と、前記要約候補とを入力として、前記要約候補の評価スコアを計算するスコア計算手段と、
前記参照要約と、前記要約候補とを入力として、前記要約候補に、前記要約候補に後続する少なくとも１つの前記文字列単位を追加した場合に得られる要約候補の評価スコアの上限値を計算する上限値計算手段と、
オラクル要約候補、及び前記要約候補の評価スコアの下限値を初期化する初期設定手段と、
ルートノード、前記要約元文書に含まれる前記文字列単位の各々に対応するノードの各々、及び前記ルートノードから前記ノードの各々までのパスの各々が前記要約候補の各々を表すようにノード間を結んだエッジからなる探索木に基づいて、前記ルートノードから深さ優先探索により前記ノードの各々を辿って着目ノードとし、
前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、かつ、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出された評価スコアが、前記評価スコアの下限値を超える場合には、前記評価スコアの下限値を、前記パスＶが表す要約候補を入力として前記算出された評価スコアに更新すると共に、前記オラクル要約候補を、前記パスＶが表す要約候補に更新し、深さ優先探索により前記着目ノードの次のノードを探索し、
前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出される評価スコアが、前記評価スコアの下限値以下であって、かつ、前記パスＶが表す要約候補を入力として前記上限値計算手段によって算出された前記評価スコアの上限値が、前記評価スコアの下限値を超える場合には、深さ優先探索により前記着目ノードの次のノードを探索し、
前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さより長い場合、又は、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出された評価スコアが、前記評価スコアの下限値以下であって、かつ、前記パスＶが表す要約候補を入力として前記上限値計算手段によって算出された前記評価スコアの上限値が、前記評価スコアの下限値以下である場合には、前記着目ノードを削除した前記パスＶに続く次のノードを深さ優先探索により探索する探索手段と、
前記探索手段によって更新された前記オラクル要約候補を、オラクル要約として出力する出力手段と、
を含むオラクル要約探索装置であって、
前記上限値計算手段は、
前記要約候補に後続する前記文字列単位の各々について、前記参照要約から前記要約候補を除いて得られる仮想文書と、前記要約候補に後続する前記文字列単位とに基づいて、評価スコアを算出し、
前記参照要約の長さ以下となるように、前記要約候補に後続する前記文字列単位の少なくとも１つを前記要約候補に追加したときの、前記追加された前記文字列単位の各々について算出された評価スコアと、前記要約候補を入力として前記スコア計算手段によって算出された評価スコアとの総和の最大値を、前記要約候補に後続する少なくとも１つの前記文字列単位を前記要約候補に追加した場合に得られる要約候補の評価スコアの上限値として算出する
オラクル要約探索装置。
【請求項２】
前記初期設定手段は、前記参照要約と、前記要約元文書とに基づいて、貪欲法により、最高値に近い評価スコアが得られる要約候補である近似オラクル要約を探索し、前記探索した近似オラクル要約を入力として前記スコア計算手段によって算出された評価スコアを、前記評価スコアの下限値の初期値として設定する請求項１記載のオラクル要約探索装置。
【請求項３】
入力された、要約元文書から少なくとも１つの文字列単位を選択して予め生成された参照要約と、前記要約元文書とに基づいて、前記要約元文書から少なくとも１つの前記文字列単位を選択して生成される複数の要約候補から、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置であって、前記参照要約と、前記要約候補とを入力として、前記要約候補の評価スコアを計算するスコア計算手段と、前記参照要約と、前記要約候補とを入力として、前記要約候補に、前記要約候補に後続する少なくとも１つの前記文字列単位を追加した場合に得られる要約候補の評価スコアの上限値を計算する上限値計算手段とを含むオラクル要約探索装置におけるオラクル要約探索方法であって、
初期設定手段によって、オラクル要約候補、及び前記要約候補の評価スコアの下限値を初期化し、
探索手段によって、ルートノード、前記要約元文書に含まれる前記文字列単位の各々に対応するノードの各々、及び前記ルートノードから前記ノードの各々までのパスの各々が前記要約候補の各々を表すようにノード間を結んだエッジからなる探索木に基づいて、前記ルートノードから深さ優先探索により前記ノードの各々を辿って着目ノードとし、
前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、かつ、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出された評価スコアが、前記評価スコアの下限値を超える場合には、前記評価スコアの下限値を、前記パスＶが表す要約候補を入力として前記算出された評価スコアに更新すると共に、前記オラクル要約候補を、前記パスＶが表す要約候補に更新し、深さ優先探索により前記着目ノードの次のノードを探索し、
前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出される評価スコアが、前記評価スコアの下限値以下であって、かつ、前記パスＶが表す要約候補を入力として前記上限値計算手段によって算出された前記評価スコアの上限値が、前記評価スコアの下限値を超える場合には、深さ優先探索により前記着目ノードの次のノードを探索し、
前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さより長い場合、又は、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出された評価スコアが、前記評価スコアの下限値以下であって、かつ、前記パスＶが表す要約候補を入力として前記上限値計算手段によって算出された前記評価スコアの上限値が、前記評価スコアの下限値以下である場合には、前記着目ノードを削除した前記パスＶに続く次のノードを深さ優先探索により探索し、
出力手段によって、前記探索手段によって更新された前記オラクル要約候補を、オラクル要約として出力する、
オラクル要約探索方法であって、
前記上限値計算手段は、
前記要約候補に後続する前記文字列単位の各々について、前記参照要約から前記要約候補を除いて得られる仮想文書と、前記要約候補に後続する前記文字列単位とに基づいて、評価スコアを算出し、
前記参照要約の長さ以下となるように、前記要約候補に後続する前記文字列単位の少なくとも１つを前記要約候補に追加したときの、前記追加された前記文字列単位の各々について算出された評価スコアと、前記要約候補を入力として前記スコア計算手段によって算出された評価スコアとの総和の最大値を、前記要約候補に後続する少なくとも１つの前記文字列単位を前記要約候補に追加した場合に得られる要約候補の評価スコアの上限値として算出する
オラクル要約探索方法。
【請求項４】
前記初期設定手段によって前記評価スコアの下限値を初期化することは、前記参照要約と、前記要約元文書とに基づいて、貪欲法により、最高値に近い評価スコアが得られる要約候補である近似オラクル要約を探索し、前記探索した近似オラクル要約を入力として前記スコア計算手段によって算出された評価スコアを、前記評価スコアの下限値の初期値として設定する請求項３記載のオラクル要約探索方法。
【請求項５】
コンピュータを、請求項１又は２記載のオラクル要約探索装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オラクル要約探索装置、方法、及びプログラムに係り、特に、要約元文書から少なくとも１つの文字列単位を選択して生成される要約候補から、オラクル要約を探索するオラクル要約探索装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
要約の品質を評価手法として、参照要約とシステム要約との間で共通するＮグラム数に着目した評価法であるＲｏｕｇｅスコア(非特許文献１参照)が広く用いられる。
【０００３】
いま、Ｒを参照要約に出現するＮグラムの多重集合、Ｓを任意のテキストユニット集合とした時、ＲとＳとの間のＲｏｕｇｅnスコアは、以下の式で定義される。
【０００４】
【数１】
0005964791.tif 000002
【０００５】
ｔnは、長さｎのＮグラムを表し、関数countは、ｔnの多重集合内での頻度を返す関数であり、ＵＮＱは、多重集合をその要素からなる集合へと変換する関数である。さらに、テキストユニット集合を受けとり、それをＮグラムの多重集合へと変換する関数をＢとする。
【０００６】
Ｄをすべてのテキストユニットの集合とした時、２|D|通りのユニットの組合せから、参照要約の長さＬR(単語数、文字数、バイト数など)を超えない、かつ、Ｒｏｕｇｅスコアが最大となる組合せを探索することでオラクル要約を得ることができる。しかし、この探索は計算量の観点からは現実的ではない。
【０００７】
そこで、厳密オラクルではなく近似オラクルを求める方法がいくつか知られている。非特許文献２では、参照要約中のテキストユニット(文)と似たユニット(単語の重なりが多い文)のみをテキストユニット集合から取り出し、それらの組合せを全探索する手法が提案されている。非特許文献３では、貪欲法によりＲｏｕｇｅスコアのゲインが最大となるテキストユニット(文)を逐次的に選択する手法が提案されている。
【０００８】
非特許文献２では予め探索対象となるテキストユニット集合を絞り込んでおき、現実的な時間で全探索できるようにしている。非特許文献３ではテキストユニットの絞り込みは行わないが、逐次的にＲｏｕｇｅスコアのゲインが最大となるユニットを選択することで計算量を抑えている。しかし、先に述べたとおり、これらの手法で求めたオラクル要約は近似オラクルでしかない。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Ｌｉｎ  Ｃｈｉｎ−Ｙｅｗ．  ２００４．  ＲＯＵＧＥ：  Ａ  Ｐａｃｋａｇｅ  ｆｏｒ  Ａｕｔｏｍａｔｉｃ  Ｅｖａｌ−ｕａｔｉｏｎ  ｏｆ  Ｓｕｍｍａｒｉｅｓ．  Ｉｎ  Ｐｒｏｃ．  ｏｆ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｔｅｘｔ  Ｓｕｍｍａｒｉｚａｔｉｏｎ  Ｂｒａｎｃｈｅｓ  Ｏｕｔ，  ｐａｇｅｓ  ７４―８１．
【非特許文献２】平尾努，鈴木潤，磯崎秀樹，「最適化問題としての自動要約」，人工知能学会論文誌，Ｖｏｌ．２４，Ｎｏ．２，ｐｐ．２２３−２３１（２００９）
【非特許文献３】Ｓｉｐｏｓ  Ｒｕｂｅｎ，  Ｓｈｉｖａｓｗａｍｙ  Ｐａｎｎａｇａ，  Ｊｏａｃｈｉｍｓ  Ｔｈｏｒｓｅｎ，Ｌａｒｇｅ−Ｍａｒｇｉｎ  Ｌｅａｒｎｉｎｇ  ｏｆ  Ｓｕｂｍｏｄｕｌａｒ  Ｓｕｍｍａｒｉｚａｔｉｏｎ  Ｍｏｄｅｌｓ”，Ｐｒｏｃ  ｏｆ  ｔｈｅ  １３ｔｈ  ＥＡＣＬ，ｐｐ．２２４−２３３（２０１２）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
たとえば、要約システムのパラメタチューニングにおいては、現在のパラメタで出力したシステム要約とオラクル要約との間のＲｏｕｇｅスコアの差を損失関数として用いる。しかし、近似オラクルを用いた場合、正しい損失関数になるとは限らないため、最適なパラメタを得られる保証がない。
【００１１】
また、要約システムのエラー分析に用いる場合でも、オラクル要約としてのユニット集合が組合せとして正しい保証がないため正確なエラー分析ができない。
【００１２】
本発明は、上記の事情を鑑みてなされたもので、計算量の増大を抑制して、厳密なオラクル要約を探索することができるオラクル要約探索装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の目的を達成するために本発明に係るオラクル要約探索装置は、入力された、要約元文書から少なくとも１つの文字列単位を選択して予め生成された参照要約と、前記要約元文書とに基づいて、前記要約元文書から少なくとも１つの前記文字列単位を選択して生成される複数の要約候補から、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置であって、前記参照要約と、前記要約候補とを入力として、前記要約候補の評価スコアを計算するスコア計算手段と、前記参照要約と、前記要約候補とを入力として、前記要約候補に、前記要約候補に後続する少なくとも１つの前記文字列単位を追加した場合に得られる要約候補の評価スコアの上限値を計算する上限値計算手段と、オラクル要約候補、及び前記要約候補の評価スコアの下限値を初期化する初期設定手段と、ルートノード、前記要約元文書に含まれる前記文字列単位の各々に対応するノードの各々、及び前記ルートノードから前記ノードの各々までのパスの各々が前記要約候補の各々を表すようにノード間を結んだエッジからなる探索木に基づいて、前記ルートノードから深さ優先探索により前記ノードの各々を辿って着目ノードとし、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、かつ、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出された評価スコアが、前記評価スコアの下限値を超える場合には、前記評価スコアの下限値を、前記パスＶが表す要約候補を入力として前記算出された評価スコアに更新すると共に、前記オラクル要約候補を、前記パスＶが表す要約候補に更新し、深さ優先探索により前記着目ノードの次のノードを探索し、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出される評価スコアが、前記評価スコアの下限値以下であって、かつ、前記パスＶが表す要約候補を入力として前記上限値計算手段によって算出された前記評価スコアの上限値が、前記評価スコアの下限値を超える場合には、深さ優先探索により前記着目ノードの次のノードを探索し、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さより長い場合、又は、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出された評価スコアが、前記評価スコアの下限値以下であって、かつ、前記パスＶが表す要約候補を入力として前記上限値計算手段によって算出された前記評価スコアの上限値が、前記評価スコアの下限値以下である場合には、前記着目ノードを削除した前記パスＶに続く次のノードを深さ優先探索により探索する探索手段と、前記探索手段によって更新された前記オラクル要約候補を、オラクル要約として出力する出力手段と、を含むオラクル要約探索装置であって、前記上限値計算手段は、前記要約候補に後続する前記文字列単位の各々について、前記参照要約から前記要約候補を除いて得られる仮想文書と、前記要約候補に後続する前記文字列単位とに基づいて、評価スコアを算出し、前記参照要約の長さ以下となるように、前記要約候補に後続する前記文字列単位の少なくとも１つを前記要約候補に追加したときの、前記追加された前記文字列単位の各々について算出された評価スコアと、前記要約候補を入力として前記スコア計算手段によって算出された評価スコアとの総和の最大値を、前記要約候補に後続する少なくとも１つの前記文字列単位を前記要約候補に追加した場合に得られる要約候補の評価スコアの上限値として算出する。
【００１４】
本発明に係るオラクル要約探索方法は、入力された、要約元文書から少なくとも１つの文字列単位を選択して予め生成された参照要約と、前記要約元文書とに基づいて、前記要約元文書から少なくとも１つの前記文字列単位を選択して生成される複数の要約候補から、評価スコアが最高値となる要約候補であるオラクル要約を探索するオラクル要約探索装置であって、前記参照要約と、前記要約候補とを入力として、前記要約候補の評価スコアを計算するスコア計算手段と、前記参照要約と、前記要約候補とを入力として、前記要約候補に、前記要約候補に後続する少なくとも１つの前記文字列単位を追加した場合に得られる要約候補の評価スコアの上限値を計算する上限値計算手段とを含むオラクル要約探索装置におけるオラクル要約探索方法であって、初期設定手段によって、オラクル要約候補、及び前記要約候補の評価スコアの下限値を初期化し、探索手段によって、ルートノード、前記要約元文書に含まれる前記文字列単位の各々に対応するノードの各々、及び前記ルートノードから前記ノードの各々までのパスの各々が前記要約候補の各々を表すようにノード間を結んだエッジからなる探索木に基づいて、前記ルートノードから深さ優先探索により前記ノードの各々を辿って着目ノードとし、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、かつ、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出された評価スコアが、前記評価スコアの下限値を超える場合には、前記評価スコアの下限値を、前記パスＶが表す要約候補を入力として前記算出された評価スコアに更新すると共に、前記オラクル要約候補を、前記パスＶが表す要約候補に更新し、深さ優先探索により前記着目ノードの次のノードを探索し、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出される評価スコアが、前記評価スコアの下限値以下であって、かつ、前記パスＶが表す要約候補を入力として前記上限値計算手段によって算出された前記評価スコアの上限値が、前記評価スコアの下限値を超える場合には、深さ優先探索により前記着目ノードの次のノードを探索し、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さより長い場合、又は、前記ルートノードから前記着目ノードまでのパスＶが表す要約候補の長さが、前記参照要約の長さ以下であって、前記パスＶが表す要約候補を入力として前記スコア計算手段によって算出された評価スコアが、前記評価スコアの下限値以下であって、かつ、前記パスＶが表す要約候補を入力として前記上限値計算手段によって算出された前記評価スコアの上限値が、前記評価スコアの下限値以下である場合には、前記着目ノードを削除した前記パスＶに続く次のノードを深さ優先探索により探索し、出力手段によって、前記探索手段によって更新された前記オラクル要約候補を、オラクル要約として出力する、オラクル要約探索方法であって、前記上限値計算手段は、前記要約候補に後続する前記文字列単位の各々について、前記参照要約から前記要約候補を除いて得られる仮想文書と、前記要約候補に後続する前記文字列単位とに基づいて、評価スコアを算出し、前記参照要約の長さ以下となるように、前記要約候補に後続する前記文字列単位の少なくとも１つを前記要約候補に追加したときの、前記追加された前記文字列単位の各々について算出された評価スコアと、前記要約候補を入力として前記スコア計算手段によって算出された評価スコアとの総和の最大値を、前記要約候補に後続する少なくとも１つの前記文字列単位を前記要約候補に追加した場合に得られる要約候補の評価スコアの上限値として算出する。
【００１５】
本発明に係るプログラムは、コンピュータを、上記のオラクル要約探索装置の各手段として機能させるためのプログラムである。
【発明の効果】
【００１６】
以上説明したように、本発明のオラクル要約探索装置、方法、及びプログラムによれば、参照要約の長さ以下となるように、要約候補に後続する文字列単位の少なくとも１つを要約候補に追加したときの、追加された文字列単位の各々について算出された評価スコアと、要約候補を入力としてスコア計算手段によって算出された評価スコアとの総和の最大値を、要約候補に後続する少なくとも１つの文字列単位を追加した場合に得られる要約候補の評価スコアの上限値として算出し、算出された評価スコアの上限値が、評価スコアの下限値を超えるか否か、及び着目ノードまでのパスＶが表す要約候補の評価スコアが、評価スコアの下限値を超えるか否かに応じて、深さ優先探索により着目ノードの次のノードを探索することにより、計算量の増大を抑制して、厳密なオラクル要約を探索することができる、という効果が得られる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１の実施の形態に係るオラクル要約探索装置の構成を示す概略図である。
【図２】探索木の一例を示す図である。
【図３】ＲＯＵＧＥスコアの上限値を求めるアルゴリズムを示す図である。
【図４】ＲＯＵＧＥスコアの下限値を求めるアルゴリズムを示す図である。
【図５】オラクル要約を探索するアルゴリズムを示す図である。
【図６】本発明の第１の実施の形態に係るオラクル要約探索装置におけるオラクル要約探索処理ルーチンの内容を示すフローチャートである。
【図７】本発明の第１の実施の形態に係るオラクル要約探索装置におけるオラクル要約探索処理ルーチンの内容を示すフローチャートである。
【図８】オラクル要約を探索するアルゴリズムを示す図である。
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１９】
＜第１の実施の形態＞
＜システム構成＞
本発明の第１の実施の形態に係るオラクル要約探索装置１００は、要約元文書から少なくとも１つのテキストユニットを選択して予め生成された参照要約と、要約元文書とが入力され、複数の要約候補から、オラクル要約を探索する。このオラクル要約探索装置１００は、ＣＰＵと、ＲＡＭと、後述するオラクル要約探索処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には次に示すように構成されている。図１に示すように、オラクル要約探索装置１００は、入力部１０と、演算部２０と、出力部３０を備えている。
【００２０】
入力部１０は、入力されたデータとして、要約元文書から少なくとも１つのテキストユニットを選択して予め生成された参照要約と、当該要約元文書とを受け付ける。参照要約は、テキストユニットに分割された文書である。
【００２１】
演算部２０は、ユニット分割部２１、多重集合生成部２２、下限値計算部２３、スコア計算部２４、上限値計算部２５、及び探索部２６を備えている。
【００２２】
ユニット分割部２１は、要約元文書を入力として受け取り、要約元文書を、文法的に意味のあるテキストユニット（例えば、文、節、句など）に分割する。文法的なテキストユニットの認定は、既存の文分割器、節分割器、句分割器などを利用すれば良い。また、文分割に関しては、句点を手がかりとするだけでも良い。
【００２３】
なお、参照要約がテキストユニットに分割されていない場合には、ユニット分割部２１によって、参照要約をテキストユニットに分割すればよい。また、テキストユニットが、文字列単位の一例である。
【００２４】
多重集合生成部２２は、テキストユニットに分割された要約元文書を入力として受け取り、要約元文書を、Ｎグラムの多重集合へと変換する。本実施の形態では、Ｎグラムとは、長さＮの連続した単語列、すなわち、連続したＮ個の単語からなる単語列を示す。なお、Ｎが２以上の場合、テキストユニットを超えたＮグラムは考えない。
【００２５】
また、多重集合生成部２２は、テキストユニットに分割された参照要約を入力として受け取り、参照要約を、Ｎグラムの多重集合へと変換する。
【００２６】
下限値計算部２３は、多重集合生成部２２によって生成された要約元文書のＮグラムの多重集合、及び参照要約のＮグラムの多重集合に基づいて、貪欲法により、近似オラクルを探索し、近似オラクルのＲＯＵＧＥスコアを、ＲＯＵＧＥスコアの下限値の初期値として設定する。また、オラクル要約候補を初期化する。
【００２７】
スコア計算部２４は、多重集合生成部２２によって生成された参照要約のＮグラムの多重集合と、要約候補のＮグラムの多重集合とを入力として、上記（１）式に従って、当該要約候補のＲＯＵＧＥスコアを計算する。
【００２８】
次に、ＲＯＵＧＥスコアの上限値を計算する原理について説明する。
【００２９】
まず、テキストユニットの多重集合を、Ｄ＝{ｓ１,ｓ２,...,ｓ５}としたとき、全てのテキストユニットの組合せは、図２に示す探索木として表現できる。この探索木は、ｒｏｏｔ、要約元文書に含まれるテキストユニットの各々に対応するノードの各々、及びｒｏｏｔから任意のノードの各々までのパスの各々が要約候補（テキストユニットの組合せ）の各々を表すようにノード間を結んだエッジからなる探索木である。
【００３０】
ここで、探索木のｒｏｏｔから任意のノード（着目ノード）までを探索した際、それよりも下のノードを探索した際に得ることのできるＲＯＵＧＥスコアの上限値を知ることができれば、探索が効率的になる。例えば、図２において、ｒｏｏｔからノードｓ１、ｓ２まで辿った際、そこに至るまでに分かったＲＯＵＧＥスコアの下限値、ｒｏｏｔから現在の着目ノードまでのパスが表す要約候補のＲＯＵＧＥスコア、現在の着目ノード以降を深さ優先で探索して得ることのできるＲＯＵＧＥスコアの上限値を知ることができれば、現在のノードまでのＲＯＵＧＥスコア、あるいは上限値が、下限値を超える場合に、着目ノードｓ２の次のノードｓ３以降の探索を続け、そうでない場合は、着目ノードｓ２以下の探索を打ち切り、ノードｓ１、ｓ３という別のパスの探索に移れば良い。
【００３１】
つまり、探索木のｒｏｏｔから現在の着目ノードまでを辿った履歴（パス）をＶ、Ｖに格納されている履歴の最後のノード（現在のノード）に直接接続可能なノードの集合（テキストユニット集合）をΩとするとき、ＲＯＵＧＥスコアの上限＾ＲＯＵＧＥ（Ｒ；Ｂ（Ｖ∪Ｗ））＝ｍａｘＷ⊆Ω{ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））：ｌｅｎ（Ｖ∪Ｗ）≦ＬＲ}が分かれば良い。図２の場合、Ｖ＝{ｓ１，ｓ２}の時、Ω＝{ｓ３，ｓ４，ｓ５}となる。なお、ｌｅｎ（）は、テキストユニット集合の長さ（単語数、文字数、バイト数）を測る関数である。
【００３２】
ここで、ＲＯＵＧＥｎ（Ｒ、Ｂ（Ｖ∪Ｗ））は以下の式で定義される。
【００３３】
【数２】
0005964791.tif 000003
【００３４】
ただし、ＲＯＵＧＥ'ｎを以下の式で定義する。
【００３５】
【数３】
0005964791.tif 000004
【００３６】
よって、履歴Ｖに後続するノード以降を探索した際に得ることのできるＲＯＵＧＥｎスコアの上限値＾ＲＯＵＧＥｎ（Ｒ；Ｂ（Ｖ∪Ｗ））は、以下の式で定義される。
【００３７】
【数４】
0005964791.tif 000005
【００３８】
上記（４）式の右辺第２項の最適解を求めることはＮＰ困難であるが、Ｒｏｕｇｅ’ｎ（Ｒ,Ｒ＼Ｂ（Ｖ）,Ｂ（Ｗ））≦Σｗ∈ＷＲＯＵＧＥ’ｎ（Ｒ,Ｒ＼Ｂ（Ｖ）,Ｂ（{ｗ}））が成り立つことに注意すると、上記（４）式の右辺第２項に対し以下の不等式が成り立つ。
【００３９】
【数５】
0005964791.tif 000006
【００４０】
上記（５）式の右辺はいわゆる０−１整数計画問題、ナップサック問題となる。この厳密解はＩＬＰソルバ、動的計画法を用いて得ることができるが、Ω、ＬＲ−ｌｅｎ（Ｖ）の値によっては計算コストが高い。そこで、この整数計画問題を線形計画問題に緩和し、図３のＡｌｇｏｒｉｔｈｍ１に示す貪欲法にて解を求める。Ａｌｇｏｒｉｔｈｍ１では、Ωの各要素（テキストユニット）を、単位長さあたりのＲＯＵＧＥ’スコアで降順にソートしておき、単位長さ当たりのＲＯＵＧＥ’スコアの先頭から、ちょうど長さＬまでだけテキストユニットを選択した際のＲＯＵＧＥ’スコアの和を求める。０−１ナップサック問題の緩和問題の厳密解はもとの問題の厳密解よりも大きくなることが保証されている。さらに、貪欲法で厳密解が得られるため計算量が少ないという利点がある。最終的に、ルートからの履歴をＶとしたとき、それ以上探索を続けて得ることのできるＲＯＵＧＥｎスコアの上限値は、以下の式で定義される。
【００４１】
【数６】
0005964791.tif 000007
【００４２】
以上説明したように、上限値計算部２５は、参照要約のＮグラムの多重集合と、要約候補を表す履歴ＶのＮグラムの多重集合と、履歴Ｖの最後のテキストユニットに直接接続されるテキストユニットの各々についてのＮグラムの多重集合と、を入力として、履歴Ｖの最後のテキストユニットに直接接続されるテキストユニットｗの各々について、参照要約のＮグラムの多重集合から、履歴ＶのＮグラムの多重集合を除いた多重集合と、履歴Ｖの最後のテキストユニットに直接後続されるテキストユニットｗのみのＮグラムの多重集合とに基づいて、単位長さあたりのＲＯＵＧＥ’スコアを算出し、参照要約の長さＬR以下となるように、履歴Ｖの最後のテキストユニットに直接接続されるテキストユニットの少なくとも１つを履歴Ｖに追加したときの、追加されたテキストユニットｗの各々について算出されたＲＯＵＧＥ’スコアと、履歴ＶについてのＲＯＵＧＥスコアとの総和の最大値を、履歴Ｖより下に探索したときに得られるＲＯＵＧＥスコアの上限値として算出する。なお、参照要約のＮグラムの多重集合から、履歴ＶのＮグラムの多重集合を除いた多重集合が、参照要約から要約候補を除いて得られる仮想文書の一例である。
【００４３】
次に、オラクル要約を探索する原理について説明する。
【００４４】
本実施の形態では、近似オラクルを求めるのではなく、厳密なオラクル要約を現実的な計算時間で探索する。探索を効率的に行うため、探索の各ステップにおいて、ＲＯＵＧＥスコアを計算すると共に、ＲＯＵＧＥスコアの上限値を見積もり、それ以上の探索を続行するか否かを、ＲＯＵＧＥスコア、ＲＯＵＧＥの上限値、及びＲＯＵＧＥの下限値に基づき決定する。
【００４５】
τを、現時点の着目ノードにおいて分かっているＲＯＵＧＥスコアの下限値とする。下限値計算部２３により、図４に示すＡｌｇｏｒｉｔｈｍ２の貪欲法で求めた近似オラクルのＲＯＵＧＥスコアで、ＲＯＵＧＥスコアの下限値は初期化される。探索を続けていく間に、ＲＯＵＧＥスコアの下限値よりも大きなＲＯＵＧＥスコアを記録すれば、その値で下限値を更新する。なお、上記図４のＡｌｇｏｒｉｔｈｍ２では、ＲＯＵＧＥスコアのゲインが最大となるテキストユニットをオラクルに逐次追加していく方法である。また、ＲＯＵＧＥｎは劣モジュラ関数であることから、Ａｌｇｏｒｉｔｈｍ２で求めたオラクルのＲＯＵＧＥｎスコアは最適値の１−１／ｅの値が保証される。
【００４６】
ここで、ｒｏｏｔから現在の着目ノードまで辿った後の探索戦略は、以下の（１）〜（３）に示す条件に応じた３通りになる。
【００４７】
【数７】
0005964791.tif 000008
【００４８】
上記（１）の条件を満たす場合、オラクル候補を履歴Ｖに更新し、下限値τをＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））で上書きし、深さ優先探索を続ける。上記（２）の条件を満たす場合、履歴Ｖの最後に格納されているノード以降の探索を打ち切る。上記（３）の条件を満たす場合、ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））は下限値τを超えないが、＾ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））が下限値τを超えることから、それ以降を深さ優先で探索した際、現在のオラクル候補を超えるテキストユニット集合が存在する可能性がある。よって、オラクル候補の更新は行わず、探索のみを続ける。
【００４９】
上記の３通りの探索戦略に基づくオラクル探索のアルゴリズムを、図５のＡｌｇｏｒｉｔｈｍ３に示す。
【００５０】
Ａｌｇｏｒｉｔｈｍ３では、参照要約のＮグラムの多重集合、要約元文書のＮグラムの多重集合、及び長さ制約ＬＲを読み込み、オラクル候補を格納するプライオリティキューＯ、探索木を辿った履歴を保持するプライオリティキューＣを初期化し、Ａｌｇｏｒｉｔｈｍ２で求めた下限値をτに初期値としてセットする。次に、要約元文書の各テキストユニットのＲＯＵＧＥスコアを計算した後、それらを降順にソートし、プライオリティキューＳに格納する。そして、手続きＦＩＮＤＯＲＡＣＬＥに引数として、プライオリティキューＳとＣを与え、手続きの再帰呼び出しにて深さ優先探索を行う。ＦＩＮＤＯＲＡＣＬＥでは、第一引数のプライオリティキューＱから先頭のテキストユニットを取り出し、第二引数のプライオリティキューＶに追加する（図５の１２、１３行目）。
【００５１】
そして、Ｓの先頭の要素であるテキストユニットからＶの最後の要素であるテキストユニットまでを削除したものをΩとする（１４行目）。長さ制約は、全体の長さ制約ＬＲからＶに格納されているテキストユニットの長さの和を引いたものとし、これがゼロ以上の場合に、上記（１）〜（３）の条件の何れを満たすかに応じて、オラクル候補の更新、探索を続けるか否かを判断する。
【００５２】
最後に、Ｖの最後の要素を削除し、再帰手続きの先頭に戻る。
【００５３】
以上のように、探索部２６は、ｒｏｏｔ、要約元文書に含まれるテキストユニットの各々に対応するノードの各々、及びｒｏｏｔからノードの各々までのパスの各々が要約候補の各々を表すようにノード間を結んだエッジからなる探索木に基づいて、ｒｏｏｔから深さ優先探索によりノードの各々を辿って着目ノードとする。
【００５４】
ｒｏｏｔから着目ノードまでのパスＶが表す要約候補の長さが、参照要約の長さＬR以下であって、かつ、スコア計算部２４によって当該パスＶのＮグラムの多重集合を入力として算出されたスコアＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））が、ＲＯＵＧＥスコアの下限値τを超える場合には、ＲＯＵＧＥスコアの下限値τを更新すると共に、オラクル要約候補を、パスＶが表す要約候補に更新する。
【００５５】
ｒｏｏｔから着目ノードまでのパスＶが表す要約候補の長さが、参照要約の長さＬR以下であって、スコア計算部２４によって当該パスＶのＮグラムの多重集合を入力として算出されるスコアＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））が、ＲＯＵＧＥスコアの下限値τ以下であって、かつ、上限値計算部２５によって当該パスＶのＮグラムの多重集合を入力として算出されるＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））が、ＲＯＵＧＥスコアの下限値τを超える場合には、深さ優先探索により着目ノードの次のノードを探索する。
【００５６】
ｒｏｏｔから着目ノードまでのパスＶが表す要約候補の長さが、参照要約の長さＬRより長い場合、又は、ｒｏｏｔから着目ノードまでのパスＶが表す要約候補の長さが、参照要約の長さＬR以下であって、スコア計算部２４によって当該パスＶのＮグラムの多重集合を入力として算出されるスコアＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））が、ＲＯＵＧＥスコアの下限値τ以下であって、かつ、上限値計算部２５によって当該パスＶのＮグラムの多重集合を入力として算出されるＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））が、ＲＯＵＧＥスコアの下限値τ以下である場合には、着目ノードを削除したパスＶに続く次のノードを深さ優先探索により探索する。
【００５７】
探索部２６によって最終的に更新されたオラクル要約候補を、オラクル要約として出力部３０により出力する。
【００５８】
＜オラクル要約探索装置の作用＞
次に、第１の実施の形態に係るオラクル要約探索装置１００の作用について説明する。まず、要約元文書から予め生成され、かつ、テキストユニットに分割された参照要約と、当該要約元文書とが、オラクル要約探索装置１００に入力されると、オラクル要約探索装置１００によって、図６、７に示すオラクル要約探索処理ルーチンが実行される。
【００５９】
まず、ステップＳ１０１において、入力された要約元文書を、テキストユニットに分割する。そして、ステップＳ１０２において、上記ステップＳ１０１でテキストユニットに分割された要約元文書に基づいて、Ｎグラムの多重集合を生成する。また、入力された参照要約に基づいて、Ｎグラムの多重集合を生成する。
【００６０】
次のステップＳ１０３では、上記ステップＳ１０２で生成された参照要約のＮグラムの多重集合に基づいて、参照要約の長さＬRを計算する。ステップＳ１０４では、上記ステップＳ１０２で生成された要約元文書のＮグラムの多重集合、及び参照要約のＮグラムの多重集合と、上記ステップＳ１０３で計算された参照要約の長さＬRとに基づいて、上記図４に示す貪欲法により、近似オラクル要約を探索し、近似オラクル要約のＲＯＵＧＥスコアを、ＲＯＵＧＥスコアの下限値τの初期値として設定する。
【００６１】
そして、ステップＳ１０５において、上記ステップＳ１０２で生成された要約元文書のＮグラムの多重集合、及び参照要約のＮグラムの多重集合に基づいて、要約元文書の各テキストユニットｓのスコアＲＯＵＧＥｎ（Ｒ,Ｂ（｛ｓ｝））を計算し、ノード（テキストユニット）を示す情報と共に、プライオリティキューＳに格納する。ステップＳ１０６では、ＲＯＵＧＥスコアの降順に、プライオリティキューＳをソートし、プライオリティキューＳの先頭のテキストユニットに対応するノードを、着目ノードとする。
【００６２】
ステップＳ１０７では、ｒｏｏｔから現在の着目ノードｓまでのパスを、プライオリティキューＶに設定する。そして、ステップＳ１０８において、プライオリティキューＳ、Ｖに基づいて、着目ノードｓに直接接続可能なノードの集合Ωを抽出する。
【００６３】
そして、ステップＳ１０９において、プライオリティキューＶのパスの長さｌｅｎ（Ｖ）が、上記ステップＳ１０３で計算された参照要約の長さＬR以下であるか否かを判定する。プライオリティキューＶのパスのｌｅｎ（Ｖ）が、参照要約の長さＬR以下である場合には、ステップＳ１１０において、上記ステップＳ１０２で生成された参照要約のＮグラムの多重集合と、プライオリティキューＶのパスが表す要約候補のＮグラムの多重集合に基づいて、上記（１）式に従って、プライオリティキューＶのパスが表す要約候補のスコアＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））を計算する。
【００６４】
ステップＳ１１１では、上記ステップＳ１１０で計算されたプライオリティキューＶのパスが表す要約候補のスコアＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））が、下限値τを超えるか否かを判定する。計算されたプライオリティキューＶのパスが表す要約候補のスコアＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））が、下限値τを超える場合には、ステップＳ１１２で、プライオリティキューＶのパスが表す要約候補を、オラクル用のプライオリティキューＯに格納すると共に、上記ステップＳ１１０で計算されたプライオリティキューＶのパスが表す要約候補のスコアＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））で、下限値τを更新する。
【００６５】
ステップＳ１１３において、深さ優先探索で、着目ノードの次のノードを選択し、着目ノードとする。ステップＳ１１４で、次のノードが選択された否かを判定する。次のノードがなかった場合には、オラクル要約探索処理ルーチンを終了する。一方、次のノードが選択された場合には、上記ステップＳ１０７へ戻り、新たに選択された着目ノードで、ステップＳ１０７以降の処理を繰り返す。
【００６６】
一方、上記ステップＳ１１１で、上記ステップＳ１１０で計算されたプライオリティキューＶのパスが表す要約候補のスコアＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））が、下限値τを超えないと判定された場合には、ステップＳ１１５で、プライオリティキューＶのパスの次のノード以降を探索した場合に得られるＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））を計算する。具体的には、上記ステップＳ１０２で生成された要約元文書のＮグラムの多重集合及び参照要約のＮグラムの多重集合と、上記ステップ１０８で抽出された着目ノードｓに直接接続可能なノードの集合Ωと、プライオリティキューＶと、参照要約の長さＬRと、プライオリティキューＶのパスのｌｅｎ（Ｖ）とを用いて、上記図３に示すＡｌｇｏｒｉｔｈｍ１で、ＵＰＰＥＲ（Ｖ、Ω、ＬR−ｌｅｎ（Ｖ））を計算する。そして、計算されたＵＰＰＥＲ（Ｖ、Ω、ＬR−ｌｅｎ（Ｖ））の値と、上記ステップＳ１１０で計算されたプライオリティキューＶのパスが表す要約候補のＲＯＵＧＥスコアとを用いて、上記（６）式に従って、ＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））を計算する。
【００６７】
ステップＳ１１６で、上記ステップＳ１１５で計算されたＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））が、下限値τを超えるか否かを判定する。計算されたＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））が、下限値τを超える場合には、上記ステップ１１４へ移行し、深さ優先探索で、着目ノードの次のノードを選択し、着目ノードとする。
【００６８】
一方、上記ステップＳ１１６で、計算されたＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））が、下限値τを超えないと判定された場合には、ステップＳ１１７において、プライオリティキューＶのパスから、現在の着目ノード（最後のノード）を削除した上で、深さ優先探索で、次のノードを選択し、着目ノードとする。ステップＳ１１８では、次のノードが選択された否かを判定する。次のノードがなかった場合には、オラクル要約探索処理ルーチンを終了する。一方、次のノードが選択された場合には、上記ステップＳ１０７へ戻り、新たに選択された着目ノードで、ステップＳ１０７以降の処理を繰り返す。
【００６９】
また、上記ステップＳ１０９において、プライオリティキューＶのパスの長さｌｅｎ（Ｖ）が、上記ステップＳ１０３で計算された参照要約の長さＬRを超えると判定された場合には、上記ステップＳ１１７へ移行する。
【００７０】
そして、最終的にプライオリティキューＯに格納されたパスが表す要約候補を、オラクル要約として、出力部３０により出力する。出力されたオラクル要約は、自動要約システムのパラメタチューニングや自動要約システムのエラー分析などに用いられる。
【００７１】
以上説明したように、第１の実施の形態に係るオラクル要約探索装置によれば、参照要約の長さＬR以下となるように、要約候補Ｖに後続するテキストユニットの少なくとも１つを要約候補Ｖに追加したときの、追加されたテキストユニットｗの各々について算出されたスコアＲＯＵＧＥ’ｎ（Ｒ,Ｒ＼Ｂ（Ｖ）,Ｂ（{ｗ}））と、要約候補Ｖについて算出されたＲＯＵＧＥスコアとの総和の最大値を、要約候補Ｖに後続する少なくとも１つのテキストユニットを追加した場合に得られるＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ；Ｂ（Ｖ∪Ｗ））として算出し、算出されたＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ；Ｂ（Ｖ∪Ｗ））が、ＲＯＵＧＥスコアの下限値τを超えるか否か、及び着目ノードまでのパスＶが表す要約候補のスコアＲＯＵＧＥｎ（Ｒ；Ｂ（Ｖ））が、ＲＯＵＧＥスコアの下限値τを超えるか否かに応じて、深さ優先探索により着目ノードの次のノードを探索することにより、計算量の増大を抑制して、効率的に、厳密なオラクル要約を探索することができる。
【００７２】
また、排他的なテキストユニット集合Ｖ、Ｗの和集合に対するＲＯＵＧＥスコアを、ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ∪Ｗ））＝ＲＯＵＧＥｎ（Ｒ,Ｂ（Ｖ））＋ＲＯＵＧＥ’ｎ（Ｒ,Ｒ＼Ｂ（Ｖ）,Ｂ（Ｗ））と定義し、ＲＯＵＧＥ’ｎ（Ｒ,Ｒ＼Ｂ（Ｖ）,Ｂ（Ｗ））の上限値を、貪欲法にて求めることにより、要約候補Ｖに後続する少なくとも１つのテキストユニットを追加した場合に得られるＲＯＵＧＥスコアの上限値＾ＲＯＵＧＥｎ（Ｒ；Ｂ（Ｖ∪Ｗ））を、少ない計算量で算出することができる。
【００７３】
＜第２の実施の形態＞
次に、第２の実施の形態について説明する。なお、第２の実施の形態に係るオラクル要約探索装置は、第１の実施の形態と同様の構成であるため、同一符号を付して説明を省略する。
【００７４】
第２の実施の形態では、ＲＯＵＧＥスコアが高いものから順に上位ｋ個のオラクル要約を探索している点が、第１の実施の形態と異なっている。
【００７５】
第２の実施の形態におけるオラクル探索のアルゴリズムを、図８のＡｌｇｏｒｉｔｈｍ４に示す。
【００７６】
Ａｌｇｏｒｉｔｈｍ４では、下限値τ＝０を初期値とすることと（４行目）、オラクルを格納するプライオリティキューの大きさをｋとし、ｋ番目のオラクルのＲＯＵＧＥスコアを対象として、上記（１）〜（３）の探索戦略を適用する点で、上記第１の実施の形態で適用されるＡｌｇｏｒｉｔｈｍ３と異なっている。
【００７７】
＜オラクル要約探索装置の作用＞
【００７８】
第２の実施の形態に係るオラクル要約探索処理ルーチンでは、上記図６のステップＳ１０４で、ＲＯＵＧＥスコアの下限値τを０に設定する。
【００７９】
上記ステップＳ１１２では、プライオリティキューＯに格納されているパスの個数がＫ個未満である場合には、プライオリティキューＶのパスが表す要約候補を、大きさがＫのプライオリティキューＯに格納すると共に、ＲＯＵＧＥスコアの降順に、プライオリティキューＯをソートする。そして、プライオリティキューの最後の要素に格納されたパスが表す要約候補のＲＯＵＧＥスコアで、下限値を更新する。
【００８０】
プライオリティキューＯに格納されているパスの個数がＫ個である場合には、プライオリティキューの最後の要素に格納されたパスを削除した上で、プライオリティキューＶのパスが表す要約候補を、大きさがＫのプライオリティキューＯに格納すると共に、ＲＯＵＧＥスコアの降順に、プライオリティキューＯをソートする。そして、プライオリティキューの最後の要素に格納されたパスが表す要約候補のＲＯＵＧＥスコアで、下限値τを更新する。
【００８１】
なお、第２の実施の形態に係るオラクル要約探索装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【００８２】
このように、計算量の増大を抑制して、効率的に、上位ｋ個の厳密なオラクル要約を探索することができる。
【００８３】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００８４】
例えば、要約の評価関数として、ＲＯＵＧＥ以外を用いてもよい。単調かつ減少のない集合関数（たとえば再現率）であれば、ＲＯＵＧＥの代わりに利用可能である。
【００８５】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００８６】
１０   入力部
２０   演算部
２１   ユニット分割部
２２   多重集合生成部
２３   下限値計算部
２４   スコア計算部
２５   上限値計算部
２６   探索部
３０   出力部
１００ オラクル要約探索装置
【図１】
0005964791.tif 000009
【図３】
0005964791.tif 000010
【図４】
0005964791.tif 000011
【図５】
0005964791.tif 000012
【図６】
0005964791.tif 000013
【図７】
0005964791.tif 000014
【図８】
0005964791.tif 000015
【図２】
0005964791.tif 000016