JP6958417B2

JP6958417B2 - 文書要約装置、方法、及びプログラム

Info

Publication number: JP6958417B2
Application number: JP2018028305A
Authority: JP
Inventors: 晋作坂上; 平尾　努; 正彬西野; 永田　昌明
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2018-02-20
Filing date: 2018-02-20
Publication date: 2021-11-02
Anticipated expiration: 2038-02-20
Also published as: US20200394212A1; WO2019163584A1; JP2019144845A; US11216613B2

Description

本発明は、文書要約装置、方法、及びプログラムに係り、特に、情報量の多い要約を作成する文書要約装置、方法、及びプログラムに関する。

文書要約とは、大規模な文書データが与えられたもとで、その文書の中の重要な内容をできるだけ網羅する、より短い文章（要約）を作成するという取り組みである。

文書要約装置の開発のために頻繁に用いられる手法の一つに、文抽出要約と呼ばれるものがある。この手法では、与えられた文書の中から重要な文をいくつか選ぶことで、要約を作成する。この手法に基づく要約装置としては非特許文献１に記載のものなどがある。

一方で、要約すべき文書に含まれる文は、しばしば一文一文が長いことがあり、そのような文には冗長な部分が含まれることが多い。このような場合に文抽出要約を用いると、冗長で長い文を少数選んだだけで長さ制約の上限に達してしまい、情報量の多い要約を得ることができなかった。このような状況に対する有効な手法として、文圧縮要約がある。文圧縮要約では、もとの文を圧縮することで重要な部分だけを含んだ短い文を取り出し、その短い文たちを用いて要約を作成する。そのため、要約の長さ制約が厳しい場合においても、情報量の多い要約を作成することができる。このような文圧縮要約の既存技術としては、非特許文献２や非特許文献３に記載のものがある。

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と呼ばれる木構造を定義し、

と書く。ただし、

はsentence treeの各々をひとまとめにするために便宜的に導入したdocument treeの根であり、ＶとＥとはそれぞれ以下（１）式のように定義されるdocument treeの頂点集合および辺集合である。

・・・（１）

上記のsentence treeとdocument treeの例を図１に示す。図１は２つのsentence treeのＴ_１およびＴ_２からなるdocument tree

を表している。

が与えられた時、要約に含まれる単語（あるいはチャンク）の部分集合Ｓ⊆Ｖおよび

が、

における

を根とした部分木を成しているならば、要約Ｓは依存構造を保存していることになる。また、Ｖの各要素ｖには長さｌ_ｖ≧０が割り当てられている。ｌ_ｖは例えば単語の文字数などに相当する。要約Ｓに含まれるｖの長さの合計は、ある上限値Ｌ以下でなければならない。すなわち、

が満たされなくてはならない。したがって、

上で

を根とする部分木を成し、かつ長さがＬ以下であるという制約のもとで、より情報量の大きな要約Ｓ⊆Ｖを取り出すことが、文圧縮要約における目標となる。

要約Ｓ⊆Ｖの情報量の多さは、何らかの関数

を用いて評価することとなる。この関数の値ｇ(Ｓ)が大きくなるようなＳを見つけることで、より情報量の多い要約を得ることができる。この関数ｇのことを目的関数と呼ぶ。本発明の実施の形態では、目的関数ｇとして単調劣モジュラ関数を用いる。ただし、ｇが単調劣モジュラであるとは、任意のＸ⊆Ｙに対して以下の関係が成り立つということを意味する。

要約の評価のために用いられる目的関数の多くは上記の単調劣モジュラ関数の性質を満たすため、本発明の実施の形態の手法は、要約のために用いられる様々な目的関数に適用することができる。

以上を踏まえると、文圧縮要約によって要約を得るためには、以下（２）式の問題を解けば良いことがわかる。

・・・（２）

本発明の実施の形態の提案手法では、この問題を後述する（３）式のような別の問題に定式化し直し、その上で動作する高速なアルゴリズムを用いることで要約を得る、という手段をとる。アルゴリズムとしては図３に示す貪欲法(Algorithm 1)を用いる。

document treeの各頂点に対応する各要素ｖ∈Ｖに対し、ｖと

とを結ぶパスを考え、それらのパスの集合を

と書く。すなわち、各要素ｖ∈Ｖに対して、対応するパス

がただ一つ存在することになり、

が成り立つ。図２は、図１のdocument tree

から作られるパスの集合

を表している。図２に示すように、各要素ｖ及び根に接続される節ｒに対応するパスの各々によりパスの集合が表される。また、Ｖ_ｐ⊆Ｖをｐに含まれる頂点の集合とし、任意の

に対して

と定義する。以上を用いると、上記の問題（２）は次の（３）式ように書き換えることができる。

・・・（３）

ここで、

上の二項演算＋、−を、以下のように定義する。

これらはそれぞれ、

上で和集合、差集合をとることを表している。さらに、任意の

に対し、以下のように定義する。

・・・（４）

ｆ（Ｘ｜Ｙ）は劣モジュラ関数における部分集合の増加分を表し、ｃ（Ｘ｜Ｙ）は部分集合の要素の長さの総和の増加分を表す。提案手法では、上記（３）式の問題に対し、図３のAlgorithm 1に示した貪欲法を適用することで解

を得る。

この解から要約Ｖ_Ｙ⊆Ｖが得られ、Ｖ_Ｙは上述の要約長の制約と、

の根付き部分木になるという制約を満たしている。また、各sentence treeの葉となっている頂点の数をｉとし、

と定義すると、Ｖ_Ｙは（２）式の問題に対する

近似解となっている。すなわち、上記の貪欲法で得られた解が必ずある程度良い要約になるということを、理論的に保証することができる。

＜本発明の実施の形態に係る文書要約装置の構成＞

次に、本発明の実施の形態に係る文書要約装置の構成について説明する。図４に示すように、本発明の実施の形態に係る文書要約装置１００は、ＣＰＵと、ＲＡＭと、後述する文書要約処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この文書要約装置１００は、機能的には図４に示すように入力部１０と、演算部２０と、出力部５０とを備えている。

入力部１０は、文書データ、文書データの要約に対する情報量を定義する劣モジュラ関数ｇ、及び要約長の上限Ｌを受け付ける。文書データは、単語を要素とする、劣モジュラ最大化問題の要素の各々を含む集合である。要約は、劣モジュラ関数において情報量が最大となる部分集合である。要約長の上限Ｌは、劣モジュラ関数において情報量が最大となる部分集合の長さの上限である。

演算部２０は、主制御部３０を含んで構成されている。

主制御部３０は、構築部３２と、記憶部３４と、探索部３６とを含んで構成されている。

構築部３２は、入力部１０で受け付けた文書データから、非特許文献４の方法を用いて依存構造木であるdocument tree

を作成し、依存構造木に含まれる集合の各要素ｖ∈Ｖの長さｌ_ｖを計算して記憶部３４に格納する。

探索部３６は、文書データと、劣モジュラ関数ｇと、要約長の上限Ｌと、記憶部３４に格納されている、依存構造木

における根

を含むパスの集合

と、要素の各々の長さｌ_ｖと、を受け付け、（２）式に示す劣モジュラ関数を定式化し直した（３）式の劣モジュラ関数を最大化するように貪欲法を用いてパスを選択することを繰り返すことにより、依存構造木の根付き部分木に含まれる部分集合であって、かつ、部分集合の要素ｌ_ｖの長さの総和が上限Ｌ以下であるという制約を満たす部分集合から、情報量が最大となる部分集合を求め、文書の要約Ｓ⊆Ｖとして出力部５０に出力する。探索は、図３のAlgorithm 1に示す貪欲法を用いて、パスを選択することによる部分集合の要素の長さの総和の増加分ｃ（{p'}|Ｘ）に対する、パスを選択することによる劣モジュラ関数の増加分ｆ（{p'}|Ｘ）の比が最大となるパスを選択すること（図３の３行目）を繰り返す。

このように、本実施の形態の手法は、任意の単調劣モジュラ関数ｇに対して動作する。そのため、与えられた要約タスクに応じてｇを適切に設計し、より良い要約を得るというアプローチを取ることができる。また、本実施の形態の手法で用いられるAlgorithm 1の貪欲法は、非特許文献２で用いられる整数計画法や非特許文献３の動的計画法よりも高速に動作するため、既存法よりも高速に要約を得ることができる。

＜本発明の実施の形態に係る文書要約装置の作用＞

次に、本発明の実施の形態に係る文書要約装置１００の作用について説明する。入力部１０において、文書データと、劣モジュラ関数ｇと、要約長の上限Ｌとを受け付けると、文書要約装置１００は、図５に示す文書要約処理ルーチンを実行する。

まず、ステップＳ１００では、入力部１０で受け付けた文書データから、非特許文献４の方法を用いて依存構造木であるdocument tree

を作成し、各要素ｖ∈Ｖの長さｌ_ｖを計算して記憶部３４に格納する。

次に、ステップＳ１０２では、文書データと、劣モジュラ関数ｇと、要約長の上限Ｌと、記憶部３４に格納されている、依存構造木

における根

を含むパスの集合

と、要素の各々の長さｌ_ｖと、を受け付け、（２）式に示す劣モジュラ関数を定式化し直した（３）式の劣モジュラ関数を最大化するように貪欲法を用いてパスを選択することを繰り返すことにより、依存構造木の根付き部分木に含まれる部分集合であって、かつ、部分集合の要素ｌ_ｖの長さの総和が上限Ｌ以下であるという制約を満たす部分集合から、情報量が最大となる部分集合を求め、文書の要約Ｓ⊆Ｖとして出力部５０に出力する。

以上説明したように、本発明の実施の形態に係る文書要約装置によれば、劣モジュラ最大化問題の要素の各々を含む集合と、集合の部分集合に対する情報量を定義する劣モジュラ関数と、文書の依存構造を表す依存構造木と、依存構造木における根を含むパスの集合と、要素の各々の長さと、部分集合の長さの上限と、を受け付け、劣モジュラ関数を最大化するように貪欲法を用いてパスを選択することを繰り返すことにより、依存構造木の根付き部分木に含まれる部分集合であって、かつ、部分集合の要素の長さの総和が上限以下であるという制約を満たす部分集合から、情報量が最大となる部分集合を求め、文書の要約として出力することにより、劣モジュラ最大化問題を用いて、高速に、文書を要約することができる。

なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。

例えば、上述した実施の形態では、構築部３２により依存構造木を作成し、各要素の長さを計算する場合について説明したが、これに限定されるものでなく、構築部３２を設けずに、予め作成した依存構造木、及び予め計算した各要素の長さｌ_ｖを受け付けるようにしてもよい。

１０入力部
２０演算部
３０主制御部
３２構築部
３４記憶部
３６探索部
５０出力部
１００文書要約装置

Claims

文書の単語を要素とする集合から非冗長な部分集合を探索することにより前記文書を要約する劣モジュラ最大化問題において、
前記劣モジュラ最大化問題の要素の各々を含む集合と、前記集合の部分集合に対する情報量を定義する劣モジュラ関数と、前記文書の依存構造を表す依存構造木と、前記依存構造木における前記要素の各々及び根に接続される節に対応するパスの各々により表されるパスの集合と、前記要素の各々の長さと、前記部分集合の長さの上限と、を受け付け、
前記パスの集合の上で和集合、及び差集合によって定義される前記部分集合の増加分、及び前記部分集合の要素の長さの総和の増加分を用いた問題に対し、前記劣モジュラ関数を最大化するように貪欲法を用いて前記パスを選択することを繰り返すことにより、前記依存構造木の根付き部分木に含まれる部分集合であって、かつ、前記部分集合の要素の長さの総和が前記上限以下であるという制約を満たす部分集合から、前記情報量が最大となる部分集合を求め、前記文書の要約として出力する探索部、
を含む文書要約装置。
前記探索部は、貪欲法を用いて、前記パスを選択することによる前記部分集合の要素の長さの総和の増加分に対する、前記パスを選択することによる前記劣モジュラ関数の増加分の比が最大となるパスを選択することを繰り返す請求項１に記載の文書要約装置。
文書の単語を要素とする集合から非冗長な部分集合を探索することにより前記文書を要約する劣モジュラ最大化問題において、
探索部が、前記劣モジュラ最大化問題の要素の各々を含む集合と、前記集合の部分集合に対する情報量を定義する劣モジュラ関数と、前記文書の依存構造を表す依存構造木と、前記依存構造木における前記要素の各々及び根に接続される節に対応するパスの各々により表されるパスの集合と、前記要素の各々の長さと、前記部分集合の長さの上限と、を受け付け、
前記パスの集合の上で和集合、及び差集合によって定義される前記部分集合の増加分、及び前記部分集合の要素の長さの総和の増加分を用いた問題に対し、前記劣モジュラ関数を最大化するように貪欲法を用いて前記パスを選択することを繰り返すことにより、前記依存構造木の根付き部分木に含まれる部分集合であって、かつ、前記部分集合の要素の長さの総和が前記上限以下であるという制約を満たす部分集合から、前記情報量が最大となる部分集合を求め、前記文書の要約として出力するステップ、
を含む処理をコンピュータに実行させる文書要約方法。
前記探索部は、貪欲法を用いて、前記パスを選択することによる前記部分集合の要素の長さの総和の増加分に対する、前記パスを選択することによる前記劣モジュラ関数の増加分の比が最大となるパスを選択することを繰り返す請求項３に記載の文書要約方法。
コンピュータを、請求項１又は請求項２に記載の文書要約装置の各部として機能させるためのプログラム。