(57)【要約】【課題】劣モジュラ最大化問題を用いて、高速に、文書を要約することができる。【解決手段】探索部３６が、劣モジュラ最大化問題の要素の各々を含む集合と、集合の部分集合に対する情報量を定義する劣モジュラ関数と、文書の依存構造を表す依存構造木と、依存構造木における根を含むパスの集合と、要素の各々の長さと、部分集合の長さの上限と、を受け付け、劣モジュラ関数を最大化するように貪欲法を用いてパスを選択することを繰り返すことにより、依存構造木の根付き部分木に含まれる部分集合であって、かつ、部分集合の要素の長さの総和が上限以下であるという制約を満たす部分集合から、情報量が最大となる部分集合を求め、文書の要約として出力する。【選択図】図４
2019144845.tif 000002
【特許請求の範囲】
【請求項１】
文書の単語を要素とする集合から非冗長な部分集合を探索することにより前記文書を要約する劣モジュラ最大化問題において、
前記劣モジュラ最大化問題の要素の各々を含む集合と、前記集合の部分集合に対する情報量を定義する劣モジュラ関数と、前記文書の依存構造を表す依存構造木と、前記依存構造木における根を含むパスの集合と、前記要素の各々の長さと、前記部分集合の長さの上限と、を受け付け、
前記劣モジュラ関数を最大化するように貪欲法を用いて前記パスを選択することを繰り返すことにより、前記依存構造木の根付き部分木に含まれる部分集合であって、かつ、前記部分集合の要素の長さの総和が前記上限以下であるという制約を満たす部分集合から、前記情報量が最大となる部分集合を求め、前記文書の要約として出力する探索部、
を含む文書要約装置。
【請求項２】
前記探索部は、貪欲法を用いて、前記パスを選択することによる前記部分集合の要素の長さの総和の増加分に対する、前記パスを選択することによる前記劣モジュラ関数の増加分の比が最大となるパスを選択することを繰り返す請求項１に記載の文書要約装置。
【請求項３】
文書の単語を要素とする集合から非冗長な部分集合を探索することにより前記文書を要約する劣モジュラ最大化問題において、
探索部が、前記劣モジュラ最大化問題の要素の各々を含む集合と、前記集合の部分集合に対する情報量を定義する劣モジュラ関数と、前記文書の依存構造を表す依存構造木と、前記依存構造木における根を含むパスの集合と、前記要素の各々の長さと、前記部分集合の長さの上限と、を受け付け、
前記劣モジュラ関数を最大化するように貪欲法を用いて前記パスを選択することを繰り返すことにより、前記依存構造木の根付き部分木に含まれる部分集合であって、かつ、前記部分集合の要素の長さの総和が前記上限以下であるという制約を満たす部分集合から、前記情報量が最大となる部分集合を求め、前記文書の要約として出力するステップ、
を含む文書要約方法。
【請求項４】
前記探索部は、貪欲法を用いて、前記パスを選択することによる前記部分集合の要素の長さの総和の増加分に対する、前記パスを選択することによる前記劣モジュラ関数の増加分の比が最大となるパスを選択することを繰り返す請求項３に記載の文書要約方法。
【請求項５】
コンピュータを、請求項１又は請求項２に記載の文書要約装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書要約装置、方法、及びプログラムに係り、特に、情報量の多い要約を作成する文書要約装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
文書要約とは、大規模な文書データが与えられたもとで、その文書の中の重要な内容をできるだけ網羅する、より短い文章（要約）を作成するという取り組みである。
【０００３】
文書要約装置の開発のために頻繁に用いられる手法の一つに、文抽出要約と呼ばれるものがある。この手法では、与えられた文書の中から重要な文をいくつか選ぶことで、要約を作成する。この手法に基づく要約装置としては非特許文献１に記載のものなどがある。
【０００４】
一方で、要約すべき文書に含まれる文は、しばしば一文一文が長いことがあり、そのような文には冗長な部分が含まれることが多い。このような場合に文抽出要約を用いると、冗長で長い文を少数選んだだけで長さ制約の上限に達してしまい、情報量の多い要約を得ることができなかった。このような状況に対する有効な手法として、文圧縮要約がある。文圧縮要約では、もとの文を圧縮することで重要な部分だけを含んだ短い文を取り出し、その短い文たちを用いて要約を作成する。そのため、要約の長さ制約が厳しい場合においても、情報量の多い要約を作成することができる。このような文圧縮要約の既存技術としては、非特許文献２や非特許文献３に記載のものがある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Hui Lin and Jeff Bilmes. 2010. Multi-document summarization via budgeted maximization of submodular functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. pages 912-920.
【非特許文献２】Taylor Berg-Kirkpatrick, Dan Gillick, and Dan Klein. 2011. Jointly learning to extract and compress. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Linguistics.pages 481-490.
【非特許文献３】Hajime Morita, Ryohei Sasano, Hiroya Takamura, and Manabu Okumura. 2013.Subtree extractive summarization via submodular maximization. In Proceedings of the 51stAnnual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).pages 1023-1032.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
既存の文圧縮要約法の課題は、以下の２点である。
【０００７】
第１に、既存手法は、適用可能な目的関数の種類が限られている。そのため、目的関数を適切に設計することで、より良い要約を得るというアプローチを取ることができないという問題がある。
【０００８】
第２に、既存手法は、要約を得るために計算コストの大きな処理（整数計画法や動的計画法など）が必要となる。そのため、大規模な文書データの要約作成に適用することは難しいという問題がある。
【０００９】
本発明は、上記問題点を解決するために成されたものであり、劣モジュラ最大化問題を用いて、高速に、文書を要約することができる文書要約装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、第１の発明に係る文書要約装置は、文書の単語を要素とする集合から非冗長な部分集合を探索することにより前記文書を要約する劣モジュラ最大化問題において、前記劣モジュラ最大化問題の要素の各々を含む集合と、前記集合の部分集合に対する情報量を定義する劣モジュラ関数と、前記文書の依存構造を表す依存構造木と、前記依存構造木における根を含むパスの集合と、前記要素の各々の長さと、前記部分集合の長さの上限と、を受け付け、前記劣モジュラ関数を最大化するように貪欲法を用いて前記パスを選択することを繰り返すことにより、前記依存構造木の根付き部分木に含まれる部分集合であって、かつ、前記部分集合の要素の長さの総和が前記上限以下であるという制約を満たす部分集合から、前記情報量が最大となる部分集合を求め、前記文書の要約として出力する探索部、を含んで構成されている。
【００１１】
第２の発明に係る文書要約方法は、文書の単語を要素とする集合から非冗長な部分集合を探索することにより前記文書を要約する劣モジュラ最大化問題において、探索部が、前記劣モジュラ最大化問題の要素の各々を含む集合と、前記集合の部分集合に対する情報量を定義する劣モジュラ関数と、前記文書の依存構造を表す依存構造木と、前記依存構造木における根を含むパスの集合と、前記要素の各々の長さと、前記部分集合の長さの上限と、を受け付け、前記劣モジュラ関数を最大化するように貪欲法を用いて前記パスを選択することを繰り返すことにより、前記依存構造木の根付き部分木に含まれる部分集合であって、かつ、前記部分集合の要素の長さの総和が前記上限以下であるという制約を満たす部分集合から、前記情報量が最大となる部分集合を求め、前記文書の要約として出力するステップ、を含んで実行することを特徴とする。
【００１２】
第３の発明に係るプログラムは、コンピュータを、第１の発明に係る文書要約装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１３】
本発明の文書要約装置、方法、及びプログラムによれば、劣モジュラ最大化問題の要素の各々を含む集合と、集合の部分集合に対する情報量を定義する劣モジュラ関数と、文書の依存構造を表す依存構造木と、依存構造木における根を含むパスの集合と、要素の各々の長さと、部分集合の長さの上限と、を受け付け、劣モジュラ関数を最大化するように貪欲法を用いてパスを選択することを繰り返すことにより、依存構造木の根付き部分木に含まれる部分集合であって、かつ、部分集合の要素の長さの総和が上限以下であるという制約を満たす部分集合から、情報量が最大となる部分集合を求め、文書の要約として出力することにより、劣モジュラ最大化問題を用いて、高速に、文書を要約することができる、という効果が得られる。
【図面の簡単な説明】
【００１４】
【図１】依存構造木である、２つのsentence treeのＴ１およびＴ２からなるdocument treeの一例を示す図である。
【図２】document treeに対応するパスの集合の一例を示す図である。
【図３】貪欲法によるアルゴリズムの一例を示す図である。
【図４】本発明の実施の形態に係る文書要約装置の構成を示すブロック図である。
【図５】本発明の実施の形態に係る文書要約装置における文書要約処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１６】
＜本発明の実施の形態に係る原理＞
【００１７】
まず、本発明の実施の形態における原理を説明する。本発明の実施の形態では、最終的に得られる要約の長さ（合計の単語数、または文字数）が、事前に決められた上限値以下になるように要約を作成する。
【００１８】
文を圧縮する際には，単に情報量の大きい単語や句を取り出し繋げるだけでは，もとの文の修飾・被修飾などの構造（依存構造）が保存されないため、結果として可読性の低い要約が出力されてしまう。そのような問題を回避する手段として、依存構造木と呼ばれる木構造を各文に対して構成し、その木の一部を取り出すことで圧縮された文を作成する、という方針がしばしば用いられる（例えば、非特許文献４参照）。本発明の実施の形態でも、そのような方針に従って文圧縮要約を行う。
[非特許文献４]Katja Filippova and Michael Strube. 2008. Dependency tree based sentence compression. In Proceedings of the 5th International Natural Language Generation Conference.pages 25-32.
【００１９】
任意の正整数ｋに対し、［ｋ］＝｛１,２,...,ｋ｝とする。今、Ｎ個の文からなる文書を、文圧縮要約によって要約することを考える。ｉ番目の文（ｉ∈［Ｎ］）に対する依存構造木をｉ番目のsentence treeと呼び、Ｔｉ＝（Ｖｉ,Ｅｉ）と書く。Ｖｉはｉ番目の文に含まれる単語（あるいはチャンク）の集合であり、これらはＴｉの頂点集合を成す。ＥｉはＶｉ内の要素のペアの依存関係を表しており、Ｔｉの辺集合を成す。このような各文に対する依存構造木は、非特許文献４に記載されている方法で得られる。さらに、Ｔ１,...,ＴＮをまとめた木構造として、document treeと呼ばれる木構造を定義し、
2019144845.tif 000003
と書く。ただし、
2019144845.tif 000004
はsentence treeの各々をひとまとめにするために便宜的に導入したdocument treeの根であり、ＶとＥとはそれぞれ以下（１）式のように定義されるdocument treeの頂点集合および辺集合である。
【００２０】
【数１】
2019144845.tif 000005
・・・（１）
【００２１】
上記のsentence treeとdocument treeの例を図１に示す。図１は２つのsentence treeのＴ１およびＴ２からなるdocument tree
2019144845.tif 000006
を表している。
2019144845.tif 000007
が与えられた時、要約に含まれる単語（あるいはチャンク）の部分集合Ｓ⊆Ｖおよび
2019144845.tif 000008
が、
2019144845.tif 000009
における
2019144845.tif 000010
を根とした部分木を成しているならば、要約Ｓは依存構造を保存していることになる。また、Ｖの各要素ｖには長さｌｖ≧０が割り当てられている。ｌｖは例えば単語の文字数などに相当する。要約Ｓに含まれるｖの長さの合計は、ある上限値Ｌ以下でなければならない。すなわち、
2019144845.tif 000011
が満たされなくてはならない。したがって、
【００２２】
2019144845.tif 000012
上で
2019144845.tif 000013
を根とする部分木を成し、かつ長さがＬ以下であるという制約のもとで、より情報量の大きな要約Ｓ⊆Ｖを取り出すことが、文圧縮要約における目標となる。
【００２３】
要約Ｓ⊆Ｖの情報量の多さは、何らかの関数
2019144845.tif 000014
を用いて評価することとなる。この関数の値ｇ(Ｓ)が大きくなるようなＳを見つけることで、より情報量の多い要約を得ることができる。この関数ｇのことを目的関数と呼ぶ。本発明の実施の形態では、目的関数ｇとして単調劣モジュラ関数を用いる。ただし、ｇが単調劣モジュラであるとは、任意のＸ⊆Ｙに対して以下の関係が成り立つということを意味する。
【００２４】
2019144845.tif 000015
2019144845.tif 000016
【００２５】
要約の評価のために用いられる目的関数の多くは上記の単調劣モジュラ関数の性質を満たすため、本発明の実施の形態の手法は、要約のために用いられる様々な目的関数に適用することができる。
【００２６】
以上を踏まえると、文圧縮要約によって要約を得るためには、以下（２）式の問題を解けば良いことがわかる。
【００２７】
【数２】
2019144845.tif 000017
・・・（２）
【００２８】
本発明の実施の形態の提案手法では、この問題を後述する（３）式のような別の問題に定式化し直し、その上で動作する高速なアルゴリズムを用いることで要約を得る、という手段をとる。アルゴリズムとしては図３に示す貪欲法(Algorithm 1)を用いる。
【００２９】
document treeの各頂点に対応する各要素ｖ∈Ｖに対し、ｖと
2019144845.tif 000018
とを結ぶパスを考え、それらのパスの集合を
2019144845.tif 000019
と書く。すなわち、各要素ｖ∈Ｖに対して、対応するパス
2019144845.tif 000020
がただ一つ存在することになり、
2019144845.tif 000021
が成り立つ。図２は、図１のdocument tree
2019144845.tif 000022
から作られるパスの集合
2019144845.tif 000023
を表している。図２に示すように、各要素ｖ及び根に接続される節ｒに対応するパスの各々によりパスの集合が表される。また、Ｖｐ⊆Ｖをｐに含まれる頂点の集合とし、任意の
2019144845.tif 000024
に対して
2019144845.tif 000025
と定義する。以上を用いると、上記の問題（２）は次の（３）式ように書き換えることができる。
【００３０】
【数３】
2019144845.tif 000026
・・・（３）
【００３１】
ここで、
2019144845.tif 000027
上の二項演算＋、−を、以下のように定義する。
【００３２】
2019144845.tif 000028
【００３３】
これらはそれぞれ、
2019144845.tif 000029
上で和集合、差集合をとることを表している。さらに、任意の
2019144845.tif 000030
に対し、以下のように定義する。
【００３４】
【数４】
2019144845.tif 000031
・・・（４）
【００３５】
ｆ（Ｘ｜Ｙ）は劣モジュラ関数における部分集合の増加分を表し、ｃ（Ｘ｜Ｙ）は部分集合の要素の長さの総和の増加分を表す。提案手法では、上記（３）式の問題に対し、図３のAlgorithm 1に示した貪欲法を適用することで解
2019144845.tif 000032
を得る。
【００３６】
この解から要約ＶＹ⊆Ｖが得られ、ＶＹは上述の要約長の制約と、
2019144845.tif 000033
の根付き部分木になるという制約を満たしている。また、各sentence treeの葉となっている頂点の数をｉとし、
2019144845.tif 000034
と定義すると、ＶＹは（２）式の問題に対する
2019144845.tif 000035
近似解となっている。すなわち、上記の貪欲法で得られた解が必ずある程度良い要約になるということを、理論的に保証することができる。
【００３７】
＜本発明の実施の形態に係る文書要約装置の構成＞
【００３８】
次に、本発明の実施の形態に係る文書要約装置の構成について説明する。図４に示すように、本発明の実施の形態に係る文書要約装置１００は、ＣＰＵと、ＲＡＭと、後述する文書要約処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この文書要約装置１００は、機能的には図４に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００３９】
入力部１０は、文書データ、文書データの要約に対する情報量を定義する劣モジュラ関数ｇ、及び要約長の上限Ｌを受け付ける。文書データは、単語を要素とする、劣モジュラ最大化問題の要素の各々を含む集合である。要約は、劣モジュラ関数において情報量が最大となる部分集合である。要約長の上限Ｌは、劣モジュラ関数において情報量が最大となる部分集合の長さの上限である。
【００４０】
演算部２０は、主制御部３０を含んで構成されている。
【００４１】
主制御部３０は、構築部３２と、記憶部３４と、探索部３６とを含んで構成されている。
【００４２】
構築部３２は、入力部１０で受け付けた文書データから、非特許文献４の方法を用いて依存構造木であるdocument tree
2019144845.tif 000036
を作成し、依存構造木に含まれる集合の各要素ｖ∈Ｖの長さｌｖを計算して記憶部３４に格納する。
【００４３】
探索部３６は、文書データと、劣モジュラ関数ｇと、要約長の上限Ｌと、記憶部３４に格納されている、依存構造木
2019144845.tif 000037
における根
2019144845.tif 000038
を含むパスの集合
2019144845.tif 000039
と、要素の各々の長さｌｖと、を受け付け、（２）式に示す劣モジュラ関数を定式化し直した（３）式の劣モジュラ関数を最大化するように貪欲法を用いてパスを選択することを繰り返すことにより、依存構造木の根付き部分木に含まれる部分集合であって、かつ、部分集合の要素ｌｖの長さの総和が上限Ｌ以下であるという制約を満たす部分集合から、情報量が最大となる部分集合を求め、文書の要約Ｓ⊆Ｖとして出力部５０に出力する。探索は、図３のAlgorithm 1に示す貪欲法を用いて、パスを選択することによる部分集合の要素の長さの総和の増加分ｃ（{p'}|Ｘ）に対する、パスを選択することによる劣モジュラ関数の増加分ｆ（{p'}|Ｘ）の比が最大となるパスを選択すること（図３の３行目）を繰り返す。
【００４４】
このように、本実施の形態の手法は、任意の単調劣モジュラ関数ｇに対して動作する。そのため、与えられた要約タスクに応じてｇを適切に設計し、より良い要約を得るというアプローチを取ることができる。また、本実施の形態の手法で用いられるAlgorithm 1の貪欲法は、非特許文献２で用いられる整数計画法や非特許文献３の動的計画法よりも高速に動作するため、既存法よりも高速に要約を得ることができる。
【００４５】
＜本発明の実施の形態に係る文書要約装置の作用＞
【００４６】
次に、本発明の実施の形態に係る文書要約装置１００の作用について説明する。入力部１０において、文書データと、劣モジュラ関数ｇと、要約長の上限Ｌとを受け付けると、文書要約装置１００は、図５に示す文書要約処理ルーチンを実行する。
【００４７】
まず、ステップＳ１００では、入力部１０で受け付けた文書データから、非特許文献４の方法を用いて依存構造木であるdocument tree
2019144845.tif 000040
を作成し、各要素ｖ∈Ｖの長さｌｖを計算して記憶部３４に格納する。
【００４８】
次に、ステップＳ１０２では、文書データと、劣モジュラ関数ｇと、要約長の上限Ｌと、記憶部３４に格納されている、依存構造木
2019144845.tif 000041
における根
2019144845.tif 000042
を含むパスの集合
2019144845.tif 000043
と、要素の各々の長さｌｖと、を受け付け、（２）式に示す劣モジュラ関数を定式化し直した（３）式の劣モジュラ関数を最大化するように貪欲法を用いてパスを選択することを繰り返すことにより、依存構造木の根付き部分木に含まれる部分集合であって、かつ、部分集合の要素ｌｖの長さの総和が上限Ｌ以下であるという制約を満たす部分集合から、情報量が最大となる部分集合を求め、文書の要約Ｓ⊆Ｖとして出力部５０に出力する。
【００４９】
以上説明したように、本発明の実施の形態に係る文書要約装置によれば、劣モジュラ最大化問題の要素の各々を含む集合と、集合の部分集合に対する情報量を定義する劣モジュラ関数と、文書の依存構造を表す依存構造木と、依存構造木における根を含むパスの集合と、要素の各々の長さと、部分集合の長さの上限と、を受け付け、劣モジュラ関数を最大化するように貪欲法を用いてパスを選択することを繰り返すことにより、依存構造木の根付き部分木に含まれる部分集合であって、かつ、部分集合の要素の長さの総和が上限以下であるという制約を満たす部分集合から、情報量が最大となる部分集合を求め、文書の要約として出力することにより、劣モジュラ最大化問題を用いて、高速に、文書を要約することができる。
【００５０】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００５１】
例えば、上述した実施の形態では、構築部３２により依存構造木を作成し、各要素の長さを計算する場合について説明したが、これに限定されるものでなく、構築部３２を設けずに、予め作成した依存構造木、及び予め計算した各要素の長さｌｖを受け付けるようにしてもよい。
【符号の説明】
【００５２】
１０   入力部
２０   演算部
３０   主制御部
３２   構築部
３４   記憶部
３６   探索部
５０   出力部
１００ 文書要約装置
【図１】
2019144845.tif 000044
【図２】
2019144845.tif 000045
【図３】
2019144845.tif 000046
【図４】
2019144845.tif 000047
【図５】
2019144845.tif 000048