(57)【特許請求の範囲】
【請求項１】
複数の文を含むテキストを受け付ける受付手段と、
前記受付手段で受け付けたテキストに含まれる複数の文から要約を構成する文として選択される文の部分集合に対するスコア、及び前記要約に含まれる内容語毎の数及び重みを示すスコアを用いた目的関数であって、前記要約に含まれる内容語の数に関する制約に対するペナルティを、前記要約に含まれる内容語毎の数及び重みを示すスコアに対して、ラグランジュ乗数として加えた目的関数を、動的計画法により最大化させるように、前記複数の文を含むテキストから前記文の部分集合を選択することにより、前記テキストの要約を生成する生成手段と、
を含むテキスト要約装置。
【請求項２】
前記生成手段は、選択された前記文の部分集合に含まれる内容語の数が予め定めた上限値を超える場合には、前記ペナルティを付与する方向に前記ラグランジュ乗数を更新し、前記内容語の数が前記上限値以下の場合には、前記ペナルティを減少させる方向に前記ラグランジュ乗数を更新しながら、前記目的関数を最大化する処理を繰り返す請求項１記載のテキスト要約装置。
【請求項３】
受付手段と、生成手段とを含むテキスト要約装置におけるテキスト要約方法であって、
前記受付手段は、複数の文を含むテキストを受け付け、
前記生成手段は、前記受付手段で受け付けたテキストに含まれる複数の文から要約を構成する文として選択される文の部分集合に対するスコア、及び前記要約に含まれる内容語毎の数及び重みを示すスコアを用いた目的関数であって、前記要約に含まれる内容語の数に関する制約に対するペナルティを、前記要約に含まれる内容語毎の数及び重みを示すスコアに対して、ラグランジュ乗数として加えた目的関数を、動的計画法により最大化させるように、前記複数の文を含むテキストから前記文の部分集合を選択することにより、前記テキストの要約を生成する
テキスト要約方法。
【請求項４】
前記生成手段は、選択された前記文の部分集合に含まれる内容語の数が予め定めた上限値を超える場合には、前記ペナルティを付与する方向に前記ラグランジュ乗数を更新し、前記内容語の数が前記上限値以下の場合には、前記ペナルティを減少させる方向に前記ラグランジュ乗数を更新しながら、前記目的関数を最大化する処理を繰り返す請求項３記載のテキスト要約方法。
【請求項５】
コンピュータを、請求項１または請求項２記載のテキスト要約装置を構成する各手段として機能させるためのテキスト要約プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はテキスト要約装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、電子化されたテキストが大量に流通するようになってきたことを背景として、それらのテキストに記述されている情報を迅速に把握するために、コンピュータ等の機械によってテキストを要約させる(要約を生成させる)技術に対するニーズが高まっている。
【０００３】
現在、機械によって一つ以上のテキストを要約させる技術では、一般に、要約の対象となるテキストから、その内容を代表していると思われる文(重要文)、或いは、そのような文の集合(重要文集合)を一つ以上選び出し、それらを連結することで要約が生成されることが多い。
【０００４】
要約の対象となるテキストから重要文集合を選び出す際には、まず、入力されたテキストを文に分解し、それぞれの文にスコアを与える。そして、与えられた要約サイズを満たし、要約を構成する文のスコアの和が最大となるように文を選ぶ手法が提案されている（例えば、非特許文献１参照）。要約を構成する文のスコアの和を最大化する際には、動的計画法を用いることで、スコアを最大化する文の組み合わせを効率的に探索することができる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】平尾努、鈴木潤、磯崎秀樹、「最適化問題としての文書要約」、人工知能学会論文誌、Ｖｏｌ．２４、Ｎｏ．２、ｐｐ．２２３−２３１、２００９．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、二つ以上のテキストから一つの要約を作成しようとする場合、個別の文にスコアを与え、それらの和を最大化するように要約を生成すると、冗長な要約が生成される場合がある。これは入力された二つのテキストに類似した文が含まれていた場合、それらは同じようなスコアを得る可能性が高く、結果としていずれも要約に含まれる可能性が高いからである。類似した文が含まれる要約、すなわち冗長な要約は、冗長な情報が要約中に含まれることによって、他の情報が要約から脱落する場合がある、という問題がある。
【０００７】
また、冗長な情報が要約に含まれることを防ぐためには、一例として、要約に同じユニグラムやバイグラムが２回以上含まれてはいけないといった、冗長性を削減する制約を加えることが考えられる。しかし、そのような制約を加えた場合、動的計画法で問題を解くことができなくなる。そのため、最適解を得るためには、整数計画問題として定式化を行い、汎用的なソルバーで問題を解くといったことをしなければならず、求解に多大な時間を要することになる。
【０００８】
本発明は上記事実を考慮して成されたもので、冗長性が削減された要約を高速に得ることができるテキスト要約装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明のテキスト要約装置は、複数の文を含むテキストを受け付ける受付手段と、前記受付手段で受け付けたテキストに含まれる複数の文から要約を構成する文として選択される文の部分集合に対するスコア、及び前記要約に含まれる内容語毎の数及び重みを示すスコアを用いた目的関数であって、前記要約に含まれる内容語の数に関する制約に対するペナルティを、前記要約に含まれる内容語毎の数及び重みを示すスコアに対して、ラグランジュ乗数として加えた目的関数を、動的計画法により最大化させるように、前記複数の文を含むテキストから前記文の部分集合を選択することにより、前記テキストの要約を生成する生成手段と、を含んで構成されている。
【００１０】
本発明のテキスト要約装置によれば、受付手段が、複数の文を含むテキストを受け付ける。そして、生成手段が、受付手段で受け付けたテキストに含まれる複数の文から要約を構成する文として選択される文の部分集合に対するスコア、及び要約に含まれる内容語毎の数及び重みを示すスコアを用いた目的関数であって、前記要約に含まれる内容語の数に関する制約に対するペナルティを、前記要約に含まれる内容語毎の数及び重みを示すスコアに対して、ラグランジュ乗数として加えた目的関数を、動的計画法により最大化させるように、複数の文を含むテキストから文の部分集合を選択することにより、テキストの要約を生成する。
【００１１】
このように、要約を構成する文の部分集合を選択するための目的関数に、内容語の数に関する制約に対するペナルティをラグランジュ乗数として加えることで、要約に含まれる内容語の数を制限しつつ、動的計画法を用いることが可能となるため、冗長性が削減された要約を高速に得ることができる。
【００１２】
また、前記生成手段は、選択された前記文の部分集合に含まれる内容語の数が予め定めた上限値を超える場合には、前記ペナルティを付与する方向に前記ラグランジュ乗数を更新し、前記内容語の数が前記上限値以下の場合には、前記ペナルティを減少させる方向に前記ラグランジュ乗数を更新しながら、前記目的関数を最大化する処理を繰り返すことができる。
【００１３】
また、本発明のテキスト要約方法は、受付手段と、生成手段とを含むテキスト要約装置におけるテキスト要約方法であって、前記受付手段は、複数の文を含むテキストを受け付け、前記生成手段は、前記受付手段で受け付けたテキストに含まれる複数の文から要約を構成する文として選択される文の部分集合に対して与えられるスコア、及び前記要約に含まれる内容語毎の数及び重みを示すスコアの少なくとも一方を用いた目的関数であって、前記要約に含まれる内容語の数に関する制約に対するペナルティをラグランジュ乗数として加えた目的関数を、動的計画法により最大化させるように、前記複数の文を含むテキストから前記文の部分集合を選択することにより、前記テキストの要約を生成する方法である。
【００１４】
また、本発明のテキスト要約プログラムは、コンピュータを、上記のテキスト要約装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００１５】
本発明のテキスト要約装置、方法、及びプログラムによれば、要約を構成する文の部分集合を選択するための目的関数に、内容語の数に関する制約に対するペナルティをラグランジュ乗数として加えることで、要約に含まれる内容語の数を制限しつつ、動的計画法を用いることが可能となるため、冗長性が削減された要約を高速に得ることができる、という効果を有する。
【図面の簡単な説明】
【００１６】
【図１】本実施の形態のテキスト要約装置の機能的構成を示すブロック図である。
【図２】入力されるテキストの一例を示す図である。
【図３】パラメタデータベースの一例を示す図である。
【図４】本実施の形態のテキスト要約装置におけるテキスト要約処理ルーチンの内容を示すフローチャートである。
【図５】要約生成処理ルーチンの内容を示すフローチャートである。
【図６】ラグランジュ乗数λ更新処理ルーチンの内容を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１８】
本実施の形態に係るテキスト要約装置１０は、ＣＰＵと、ＲＡＭと、後述するテキスト要約処理ルーチンを実行するためのプログラム及び各種データを記憶したＲＯＭとを備えたコンピュータで構成されている。また、記憶手段としてＨＤＤを設けてもよい。
【００１９】
このコンピュータは、機能的には、図１に示すように、要約の対象となるテキストを受け付けるテキスト受付部１１と、受け付けたテキストの各文及び各内容語に関するスコアを与えるためのパラメタを格納したパラメタデータベース１２と、テキスト受付部１１で受け付けた要約対象のテキストとパラメタデータベース１２に格納されたパラメタとを入力として、要約を生成する要約生成部１３と、生成された要約を出力する要約出力部１４とを含んだ構成で表すことができる。
【００２０】
テキスト受付部１１は、要約の対象となるテキストを受け付ける。入力されるテキストの形式の一例を図２に示す。図２の例は、文に分割され、更に形態素解析されたテキストが入力として与えられた場合である。図２の表の各行がそれぞれ一形態素に対応しており、各形態素は、表記、品詞、読み、及び標準形の情報を有する。なお、この形態素解析結果は一例であり、他の情報を含んでもよい。
【００２１】
パラメタデータベース１２には、要約対象の各文の重要度を計算するためのパラメタが格納される。パラメタデータベース１２の一例を図３に示す。一例として、パラメタデータベース１２には、後述するベクトルｖ及びベクトルｗの値が格納される。ベクトルｖの各要素は、例えば、要約対象のテキストを構成する文集合のそれぞれの文の重要度を示し、重要度としては、対応する文の言語尤度などを用いることができる。ベクトルｗの各要素は、例えば、要約対象のテキストを構成する文集合に含まれる各内容語及びその重みからなる。例えば、内容語「道路」を含んでいるという特徴の重みは−０．０３であるということを示している。
【００２２】
なお、図３の例のように、それぞれの文や内容語に対して直接スコアを定義するのではなく、それぞれの文や内容語に対して素性関数を定義し、その素性関数と機械学習等で予め求めたパラメタとの内積を計算することで、文や内容語の重みを求めることもできる。また、ベクトルｗの各要素に対応するものとして、内容語だけでなく、入力文書に含まれるユニグラムやバイグラムなどを用いることもできる。
【００２３】
パラメタデータベース１２は、ＲＯＭまたはＨＤＤの所定の記憶領域に記憶される。
【００２４】
要約生成部１３は、テキスト受付部１１で受け付けた要約対象のテキスト、及びパラメタデータベース１２に格納されたパラメタを入力として、受け付けたテキストの要約を生成する。具体的には、要約対象のテキストが、文分割済のｎ文の文集合からなり、また、ｍ個の異なる内容語を含んでいるとする。なお、上述したように内容語を用いることは一例であって、他に内容語のバイグラムや、全ての語彙のユニグラムやバイグラムなどを用いてもよい。
【００２５】
上記のような要約対象のテキストに対して、一例として、下記（１）式〜（５）式に示す要約モデルを考える。
【００２６】
【数１】
0005604465.tif 000002
（１）式は目的関数であり、この目的関数を最大化するように、要約対象のテキストを構成する文集合から文の部分集合を選び出すことによって、要約を生成する。（１）式第１項はベクトルｖとベクトルｘとの内積であり、要約を構成する文の部分集合に対して与えられるスコアである。ｎ次元のベクトルｖの各要素は、要約対象のテキストを構成する各文のスコアを格納する。文のスコアとしては、例えば言語尤度などを利用することができ、パラメタデータベース１２から取得される。
【００２７】
（１）式第２項は、ベクトルｗとベクトルｚとの内積であり、要約を構成する内容語の集合に対して与えられるスコアである。ｍ次元のベクトルｗの各要素は、要約対象のテキストに含まれる各内容語のスコアを格納する。内容語のスコアは、パラメタデータベース１２から取得される。
【００２８】
（２）式の制約が示すように、ベクトルｘはｎ次元のバイナリベクトルであり、要約に文ｉが含まれるときｘｉ＝１となり、含まれないときはｘｉ＝０となるｎ個の決定変数からなる。従って、ベクトルｖとベクトルｘとの内積により、要約を構成する文の部分集合のスコアが与えられる。また、（３）式の制約が示すように、ベクトルｚはｍ次元のベクトルであり、０から最大ｒまでの自然数Ｎ０を要素とするベクトルである。要約に内容語ｊが１つ含まれるときｚｊ＝１となり、１つも含まれないときはｚｊ＝０となる。従って、ベクトルｗとベクトルｚとの内積により、要約を構成する内容語の集合のスコアが与えられる。それぞれの内容語が要約にｒ個までしか含まれないようにするこの制約によって、要約の冗長性を削減することができる。なお、全ての内容語に一律にｒ個以内という制約をかけるのではなく、内容語ｊについてはｒｊ個以内までというように、内容語毎に個別に要約に含まれてよい数を制約として与えることもできる。
【００２９】
また、（４）式の制約は、要約長の制限を示している。ベクトルｌはｎ次元のベクトルであり、それぞれの文の長さを格納している。ベクトルｌとベクトルｘとの内積によって要約の長さを得ることができ、要約の長さがＫを越えてはならないことを制約（４）式は示している。また、（５）式の制約は、文と文が含む内容語との包含関係を示す制約である。ｍ×ｎ行列Ａの各要素ａｊｉは、文ｉに含まれる内容語ｊの個数を示す。例えば、文ｉが内容語ｊを２つ含んでいる場合には、ａｊｉ＝２となり、内容語ｊを１つも含んでいない場合には、ａｊｉ＝０となる。この制約（５）によって、要約を構成する文と、それらの文が含む内容語の個数との整合性が保たれる。
【００３０】
なお、要約生成部１３の入力に、文短縮などの処理を行った文の集合を加えてもよく、文短縮の方法の一例としては、非特許文献２（平尾努、鈴木潤、磯崎秀樹、「構文情報に依存しない文短縮手法」、情報処理学会論文誌データベース（ＴＯＤ）、Ｖｏｌ．２、Ｎｏ．１、ｐｐ．１−−９、２００９．）記載の方法を用いることができる。この場合、文のスコアｖｉとして文短縮器が出力するスコアを用いることもできる。
【００３１】
また、（１）式の第１項を加味せず、単に要約が含む内容語の集合だけに対するスコアのみを目的関数として要約を生成することもできる。逆に、（１）式の第２項を加味せず、第１項のみで要約を生成することもできる。
【００３２】
ここで、上記（１）式〜（５）式で表される要約モデルは、制約（３）が障害となって動的計画法で解くことができない。そこで、本実施の形態では、制約（３）を緩和し目的関数に組み込んだ下記（６）式〜（１０）式の要約モデルを考える。
【００３３】
【数２】
0005604465.tif 000003
（６）式に含まれるラグランジュ乗数λは、ｍ次元のベクトルであり、制約（８）が破られている際にペナルティを与える。例えば、内容語ｚｊが制約（８）で定められたｒより多く要約に含まれている場合、λｊに正の値を与え、ｗｊからλｊを引くことによって、内容語ｚｊに対してペナルティを与える。これにより、内容語ｚｊが要約に含まれづらくなり、結果として制約（８）が満たされる可能性が高まる。
【００３４】
要約出力部１４は、要約生成部１３で生成された要約を出力する。
【００３５】
次に、本実施の形態のテキスト要約装置１０に作用について説明する。要約対象のテキストがテキスト要約装置１０に入力されると、ＣＰＵがＲＯＭに記憶されたテキスト要約処理ルーチンを実行するためのプログラムを実行する。以下に、図４を参照して、テキスト要約処理ルーチンについて説明する。
【００３６】
ステップ１００で、要約の対象となるテキストを受け付ける。次に、ステップ２００で、後述する要約生成処理を実行して、上記ステップ１００で受け付けたテキストの要約を構成する文の部分集合を示すベクトルｘを出力する。次に、ステップ３００で、上記ステップ２００で出力されたベクトルｘが示す文の部分集合で構成される要約を出力して、処理を終了する。
【００３７】
ここで、図５を参照して、上記ステップ２００で実行される要約生成処理ルーチンについて説明する。要約生成処理ルーチンでは、上記（６）式の目的関数を最大化するような文の部分集合を選択することにより、要約を生成する。
【００３８】
まず、ステップ２０２で、予め定めた文と内容語との包含関係を表す行列Ａ、及び要約長Ｋを取得する。また、上記ステップ１００で取得したテキストから、各文の長さを格納したベクトルｌ、内容語の数ｍ、及び文の数ｎを取得する。また、パラメタデータベース１２から、文のスコアを格納したベクトルｖ、及び内容語のスコアを格納したベクトルｗを取得する。
【００３９】
次に、ステップ２０４で、予め定めたラグランジュ乗数λを更新する際の更新幅を指定するパラメタα、及び各内容語が要約に含まれても良い個数の上限を指定したベクトルｒを取得する。
【００４０】
次に、ステップ２０６で、ラグランジュ乗数を格納するベクトルλ、各文のスコアｖと各内容語のスコアｗとの両方を加味した各文のスコアを格納するベクトルｓ、要約に含まれる文を示すベクトルｘ、要約に含まれる内容語及びその数を示すベクトルｚを初期化（λ＝０、ｓ＝０、ｘ＝０、ｚ＝０）する。
【００４１】
次に、ステップ２０８で、上記ステップ２０２で取得した文と内容語との包含関係を表す行列Ａ、内容語の数ｍ、文の数ｎ、文のスコアを格納したベクトルｖ、及び内容語のスコアを格納したベクトルｗを用いて、各文のスコアｖと各内容語のスコアｗとの両方を加味した各文のスコアを格納するベクトルｓを求める。
【００４２】
次に、ステップ２１０で、動的計画法を用いて、所定の要約長Ｋ以内での最適解ｘを得る。このアルゴリズムとしては、例えば、非特許文献１記載のアルゴリズムを利用することができる。
【００４３】
次に、ステップ２１２で、上記ステップ２１０で得た最適解ｘによって得られる要約に含まれる内容語及びその数を格納したベクトルｚを得る。
【００４４】
次に、ステップ２１４で、後述するラグランジュ乗数λ更新処理を実行する。
【００４５】
次に、ステップ２１６で、最適解を取得するための繰り返し処理を終了するか否かを判定する。この判定は、最適解が得られたときに終了と判定してもよいし、所定回数繰り返しても最適解が得られない場合を想定して、予め何回まで処理を繰り返すか指定しておき、その回数を上回った際に繰り返し処理を終了すると判定してもよい。終了しない場合には、ステップ２０８へ戻って処理を繰り返す。終了する場合には、ステップ２１８へ移行し、上記ステップ２１０で取得した最適解ｘを、要約を構成する文の部分集合を示すベクトルｘとして出力し、図４の処理へリターンする。
【００４６】
次に、図６を参照して、上記ステップ２１４で実行されるラグランジュ乗数λ更新処理について説明する。
【００４７】
ステップ２１４２で、上記ステップ２０２で取得した内容語の数ｍ、上記ステップ２０４で取得したラグランジュ乗数λの更新幅を指定するパラメタα、及び各内容語が要約に含まれても良い個数の上限を指定したベクトルｒ、現時点でのラグランジュ乗数を格納するベクトルλ、並びに上記ステップ２１２で取得された内容語及びその数を格納したベクトルｚを入力として受け取る。
【００４８】
次に、ステップ２１４４で、変数ｊに１をセットする。次に、ステップ２１４６で、内容語ｊの個数ｚｊがｒｊを上回るか否かを判定する。ｚｊ＞ｒｉの場合には、（８）式の制約を満たしていないため、ステップ２１４８へ移行して、パラメタαに従ってペナルティを与えるようにλｊを更新する（λｊ←λｊ＋α）。一方、ｚｊ≦ｒｉの場合には、ステップ２１５０へ移行して、パラメタαに従ってペナルティを減少させるようにλｊを更新する（λｊ←λｊ−α）。
【００４９】
次に、ステップ２１５２で、変数ｊがｍとなったか否かを判定することにより、全ての内容語について、すなわちベクトルｚの全ての要素について上記処理を終了したか否かを判定する。ｊ≠ｍの場合には、ステップ２１５４へ移行して、変数ｊを１インクリメントして、ステップ２１４６へ戻る。ｊ＝ｍとなった場合には、ステップ２１５６へ移行する。
【００５０】
ステップ２１５６では、各要素が更新されたラグランジュ乗数λを出力して、リターンする。
【００５１】
なお、ここで述べた方法とは別の、ラグランジュ緩和問題を解くアルゴリズムを用いて要約を生成することもできる。
【００５２】
以上説明したように、本実施の形態のテキスト要約装置によれば、冗長性を削減する制約をラグランジュ緩和した問題を動的計画法によって繰り返し解き、ラグランジュ乗数を劣勾配法によって求めることによって、冗長性が削減された要約を高速に生成することができる。
【００５３】
また、本実施の形態では、パラメタデータベース１２が、テキスト要約装置を構成するコンピュータに設けられたＲＯＭまたはＨＤＤの所定の記憶領域に記憶されている態様を説明したが、本発明はこれに限定されるものではない。パラメタデータベース１２は、通信回線を介してコンピュータと接続された別のコンピュータに設けられた記憶部に記憶されていてもよい。この場合、通信回線を介して前記別のコンピュータからパラメタデータベース１２を受信するようにするとよい。
【００５４】
また、本実施の形態では、ＣＰＵがテキスト要約プログラムを実行することで、コンピュータがテキスト要約装置１０として機能する態様を説明したが、本発明はこれに限定されるものではなく、図１に示した各機能ブロックは、それぞれハードウェアで構成することも可能である。
【００５５】
また、本実施の形態では、テキスト要約プログラムがＲＯＭに予め記憶（インストール）されている態様を説明したが、本発明に係るテキスト要約プログラムは、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の記録媒体に記録されている形態で提供することも可能である。
【符号の説明】
【００５６】
１０   テキスト要約装置
１１   テキスト受付部
１２   パラメタデータベース
１３   要約生成部
１４   要約出力部
【図１】
0005604465.tif 000004
【図２】
0005604465.tif 000005
【図３】
0005604465.tif 000006
【図４】
0005604465.tif 000007
【図５】
0005604465.tif 000008
【図６】
0005604465.tif 000009