(57)【特許請求の範囲】
【請求項１】
文書群から要約を生成する文書要約装置であって、
入力された文書群の各文書内の単語の区切りを決定する文書解析手段と、
文毎の第１の調整値を取得し、文に出現する単語に基づき、事前に定められた所定の第１の計算式により文の第１の重要度を求め、求めた該第１の重要度に取得した当該文の第１の調整値を加えることで、前記文書群の各文について第１のスコアを計算し、計算した該第１のスコアに基づいて文を選択する第１の文選択手段と、
文毎の第２の調整値を取得し、文に出現する単語に基づき、事前に定められた所定の第２の計算式により文の第２の重要度を求め、求めた該第２の重要度に取得した当該文の第２の調整値を加えることで、前記文書群の各文について第２のスコアを計算し、計算した該第２のスコアに基づいて文を選択する第２の文選択手段と、
前記第１の文選択手段に対して前記第１の調整値を与え、前記第２の文選択手段に対して前記第２の調整値を与え、該第１の文選択手段および該第２の文選択手段から取得した結果が一致すれば、該結果を最終解として出力し、一致しなければ、該第１の調整値を調整して該第１の文選択手段に与え、該第２の調整値を調整して該第２の文選択手段に与え、所定の回数繰り返しても一致しない場合は、該第１の文選択手段により最後に選択された文を最終解とする要約生成手段と、
前記要約生成手段により出力された前記最終解を並び替えて結合して出力する文並び替え手段と、
を有し、
前記要約生成手段は、
前記第１の文選択手段により文が選択され、かつ、前記第２の文選択手段により当該文が選択されない場合には、当該文の第１の調整値を減少する方向に調整し、当該文の第２の調整値を増加する方向に調整し、
前記第１の文選択手段により文が選択されず、かつ、前記第２の文選択手段により当該文が選択された場合には、当該文の第１の調整値を増加する方向に調整し、当該文の第２の調整値を減少する方向に調整する、
ことを特徴とする文書要約装置。
【請求項２】
文書群から要約を生成する文書要約方法であって、
文書解析手段と、第１の文選択手段と、第２の文選択手段と、要約生成手段と、文並び替え手段と、を有する装置において、
前記文書解析手段が、入力された文書群の各文書内の単語の区切りを決定する文書解析ステップと、
前記第１の文選択手段が、文毎の第１の調整値を取得し、文に出現する単語に基づき、事前に定められた所定の第１の計算式により文の第１の重要度を求め、求めた該第１の重要度に取得した当該文の第１の調整値を加えることで、前記文書群の各文について第１のスコアを計算し、計算した該第１のスコアに基づいて文を選択する第１の文選択ステップと、
前記第２の文選択手段が、文毎の第２の調整値を取得し、文に出現する単語に基づき、事前に定められた所定の第２の計算式により文の第２の重要度を求め、求めた該第２の重要度に取得した当該文の第２の調整値を加えることで、前記文書群の各文について第２のスコアを計算し、計算した該第２のスコアに基づいて文を選択する第２の文選択ステップと、
前記要約生成手段が、前記第１の調整値を与えて前記第１の文選択ステップを実行させ、前記第２の調整値を与えて前記第２の文選択ステップを実行させ、該第１の文選択ステップおよび該第２の文選択ステップによる結果が一致すれば、該結果を最終解として出力し、一致しなければ、該第１の調整値を調整して該第１の文選択ステップを実行させ、該第２の調整値を調整して該第２の文選択ステップを実行させ、所定の回数繰り返しても一致しない場合は、該第１の文選択ステップにより最後に選択された文を最終解とする要約生成ステップと、
前記文並び替え手段が、前記最終解を並び替えて結合して出力する文並び替えステップと、
を行い、
前記要約生成ステップにおいて、
前記第１の文選択ステップにより文が選択され、かつ、前記第２の文選択ステップにより当該文が選択されない場合には、当該文の第１の調整値を減少する方向に調整し、当該文の第２の調整値を増加する方向に調整し、
前記第１の文選択ステップにより文が選択されず、かつ、前記第２の文選択ステップにより当該文が選択された場合には、当該文の第１の調整値を増加する方向に調整し、当該文の第２の調整値を減少する方向に調整する、
ことを特徴とする文書要約方法。
【請求項３】
コンピュータを、
請求項１に記載の文書要約装置の各手段として機能させるための文書要約プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書要約装置及び方法及びプログラムに係り、特に、文書群からその内容を端的に示すための要約を作成するための文書要約装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
従来より、文書あるいは文書群から計算機により自動的に要約を生成する技術が知られている。例えば、文中の単語の頻度に基づく重みや、文の位置、タイトルと文との密度、重要語の密度といった特徴により文の重要度を判定し、重要な文を抽出することによる自動要約方法が提案されている(例えば、非特許文献1参照)。
【０００３】
また、別の観点からの品質の向上の取り組みとして、単にスコアが上位の文を順に選択するのではなく、各文の長さを考慮し、限られた長さの中で最もスコアの高い要約を得るために、組み合わせ最適化問題として解くことが提案されている（例えば、非特許文献2参照）。
【０００４】
各文について、他の文とは独立に文のスコアが定義可能であり、各文のスコアの和として要約のスコアが定義可能な場合については、各文の長さを重さとし、スコアを価値とするようなナップサック問題と捉えることができる。ここで、各文の長さは整数であり、重さが整数のナップサック問題は動的計画法により効率的に最適解を得るための計算を行うことができることが知られており、従来から要約生成において用いられている。
【０００５】
一方、高品質な要約を生成するためには、必ずしも要約のスコアを文のスコアの和として定義できない要因を考慮することが有効であると考えられている。例えば、スコアは高くても互いに同じ単語を含んでいるような文同士は冗長なので排除することにより高品質な要約を生成するといったことが考えられる。しかし、そのような各文のスコアとして要約のスコアが定まらないよう要因を考慮した要約生成方法は整数重みのナップサック問題として効率的に解くことはできず、一般の整数計画問題となってしまい効率的な計算が困難である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】平尾努、磯崎秀樹、前田英作、松本裕治、"Support Vector Machineを用いた重要文抽出方法"，情報処理学会論文誌，44-8, pp. 2230-2243, 2003.
【非特許文献２】Ryan McDonald.  A Study of Global Inference Algorithms in Multi-Document Summarization.  In European Conference on Information Retrieval (ECIR-2007), pp. 557-564, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述のように、従来の方法によれば、要約のスコアを要素のスコアの和として定義できないような要因を考慮しようとすれば、膨大な計算時間が必要となってしまうという問題があり、一方で、現実的な計算時間で収めようとすれば、要約のスコアを要素のスコアの和として定義できなくなるような要因を考慮しないか、最適解を得られない近似的な方法によって解くことになり、必ずしも要約の品質が良くないという問題があった。
【０００８】
本発明は、上記の点に鑑みなされたもので、語頻度や文の位置といった要約に用いる通常の要因のみならず、要約のスコアを文のスコアの和として定義できないような、要約に用いたい各種要因が存在する場合でも高品質で効率的な要約生成を行うことが可能な文書要約装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明（請求項１）は、文書群から要約を生成する文書要約装置であって、
入力された文書群の各文書内の単語の区切りを決定する文書解析手段と、
文毎の第１の調整値を取得し、文に出現する単語に基づき、事前に定められた所定の第１の計算式により文の第１の重要度を求め、求めた該第１の重要度に取得した当該文の第１の調整値を加えることで、前記文書群の各文について第１のスコアを計算し、計算した該第１のスコアに基づいて文を選択する第１の文選択手段と、
文毎の第２の調整値を取得し、文に出現する単語に基づき、事前に定められた所定の第２の計算式により文の第２の重要度を求め、求めた該第２の重要度に取得した当該文の第２の調整値を加えることで、前記文書群の各文について第２のスコアを計算し、計算した該第２のスコアに基づいて文を選択する第２の文選択手段と、
前記第１の文選択手段に対して前記第１の調整値を与え、前記第２の文選択手段に対して前記第２の調整値を与え、該第１の文選択手段および該第２の文選択手段から取得した結果が一致すれば、該結果を最終解として出力し、一致しなければ、該第１の調整値を調整して該第１の文選択手段に与え、該第２の調整値を調整して該第２の文選択手段に与え、所定の回数繰り返しても一致しない場合は、該第１の文選択手段により最後に選択された文を最終解とする要約生成手段と、
前記要約生成手段により出力された前記最終解を並び替えて結合して出力する文並び替え手段と、
を有し、
前記要約生成手段は、
前記第１の文選択手段により文が選択され、かつ、前記第２の文選択手段により当該文が選択されない場合には、当該文の第１の調整値を減少する方向に調整し、当該文の第２の調整値を増加する方向に調整し、
前記第１の文選択手段により文が選択されず、かつ、前記第２の文選択手段により当該文が選択された場合には、当該文の第１の調整値を増加する方向に調整し、当該文の第２の調整値を減少する方向に調整する。
【発明の効果】
【００１３】
本発明では、効率的な計算方法ができない要因を取り入れたとしても、全てを近似的に解くのではなく、最適解を現実的な速度で得られる要因についてはここに最適解を得て、そうでない要因についてはその要因についての近似解を得て、これらの要因間での合意をとり、合意が取れなければ調整項を調整するという方法を採ることにより、複数の要因を考慮する要約生成において、計算量のオーダを増大させることなく、高品質な要約を生成することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施の形態における文書要約装置の構成図である。
【図２】本発明の一実施の形態における処理概要のフローチャートである。
【図３】本発明の一実施の形態における要約生成部のフローチャートである。
【発明を実施するための形態】
【００１５】
以下、図面と共に本発明の実施の形態を説明する。
【００１６】
本実施の形態では、要約生成に使う要因として、最適解を現実的な計算時間で得ることができる語頻度による要因と、最適解を現実的な計算時間で得ることが困難な冗長度の排除による要因を用いて説明する。なお、本発明の利用方法は、これら２つの要因に限るものではなく、複数の要因の組み合わせとして実現することが可能である。
【００１７】
また、本実施の形態では、スコア付けの単位要素として文を用いるものを説明するが、単語の連なり（単語n-gram）や固定サイズの部分文字列等で実現することも可能である。
【００１８】
装置１０の入力は文書群Ｄ、要約結果の上限文字数Ｌである。
【００１９】
図１は、本発明の一実施の形態における文書要約装置の構成を示す。
【００２０】
同図に示す文書要約装置１０は、文書解析部１１、要約生成部１２、語頻度による文選択部１３、冗長文排除による文選択部１４、文並び替え部１５から構成される。
【００２１】
なお、本実施の形態では、文選択部として、語頻度による要因により文を選択する語頻度による文選択部１３と、互いに同じ単語を含んでいるような文を排除する冗長文排除による文選択部１４を用いるものとするが、語頻度による要因と冗長度の排除による要因以外の要因を利用する場合、以下の機能を満たしている文選択部であればよい。
【００２２】
・装置全体で利用する文選択部のうち、少なくとも一つは選択した文に含まれる文字の総数がＬ文字以下であること；
・文毎にスコアを決定でき、文のスコアに対する調整値（スコア調整ベクトル）を受け取ること；
図２は、本は詰めの一実施の形態における処理概要をフローチャートを示す。
【００２３】
最初に文書解析部１１により、入力された文書集合の各文書を単語毎に区切る(ステップ１)。次に、文選択部（語頻度による文選択部１３、冗長文排除による文選択部１４）により、要約生成部１２から取得した調整値に基づいて要約に含む文を選択し、要約生成部１２に渡す。複数の文選択部から取得した文の一致を比較し、一致する文を出力する文並び替え部１５に出力する（ステップ２）。文並び替え部１５において、文を並び替えて（ステップ３）出力する(ステップ４)。
【００２４】
以下に、文書要約装置１０の各構成要素について詳細に説明する。
【００２５】
文書解析部１１は、文書集合を入力として、文書内の単語の区切りを決定する。これには、既存の形態素解析技術を用いることができる。
【００２６】
語頻度による文書選択部１３は、文集合と、上限文字数Ｌと、入力文書中の文の総数を次元数とするスコア調整値ベクトルｕを入力として受け取る。
【００２７】
まず、文書群中の各単語ｔについて、その当該文書群内での出現頻度tf(t)を計数する。
【００２８】
次に、文集合中の、各文ｓのスコアを以下の式で求める。
【００２９】
【数１】
0005702744.tif 000002
ここで、t∈ｓは文ｓ中の語とする。
【００３０】
Ｌ文字以下で選択した文のスコアの和が最も大きくなるような文の選択方法は、score(s)に関して最適な文の組み合わせを得る問題であり、これは整数重みのナップサック問題と捉えることができる。整数重みのナップサック問題は当業者に公知の手法である動的計画法を用いて、効率的に最適組み合わせを計算することが可能なので、この最適組み合わせを求め、語頻度による文選択部１３の出力とする。
【００３１】
冗長文排除による文選択部１４は、文集合と、上限文字数Ｌと、文の数次元のスコア調整値ベクトルｕを入力として受け取る。
【００３２】
まず、文を一つ選択する。この選択は任意であるが、事前に順序を定めてもよい。例えばこの順序として、文の長さや、事前に指定したキーワードの出現数あるいは、文書内での文の出現位置等を用いてもよい。
【００３３】
以後、２文目以降の選択は、以下の式によって求めたscore(s)の値が最も大きくなるような文を、選択した文の合計の長さがＬを超えない範囲で繰り返し選択する。
【００３４】
【数２】
0005702744.tif 000003
要約生成部１２は、語頻度による文選択部１３と冗長文排除による文選択部１４に対してスコア調整値ベクトルｕを渡し、文選択結果を取得して、当該文選択結果が一致する場合は当該文選択結果を出力し、一致しなければｕの値を更新して、再度文選択部１３，１４に渡す処理を繰り返すことにより、要約文を選択する。
【００３５】
なお、本実施例では文選択部１３に対するスコア調整ベクトルの符号はマイナスとする。
図３は、本発明の一実施の形態における要約生成部のフローチャートである。
【００３６】
入力文書群中の文の集合をＶと表す。要約として選択する文の集合（すなわち入力文書群中の文の部分集合)を、｜Ｖ｜次元の二値ベクトルｘを用いて表す。ｘによって示される要約にｉ番目の文が含まれているならxi＝１、そうでないならxi＝０と表す。
【００３７】
文選択部の数をＮとする。本実施の形態では、Ｎ＝２である。また、1番目の文選択部を語頻度による文選択部１３とする。
【００３８】
まず、Ｎ個の｜Ｖ｜次元、すなわち入力文書中の文の総数次元の調整値の実数ベクトル
【００３９】
【数３】
0005702744.tif 000004
を全て０に初期化する（ステップ３０）。ここで、
【００４０】
【数４】
0005702744.tif 000005
は繰り返し回数0回目におけるベクトルuのi番目の要素を意味する。
【００４１】
繰り返し回数ｋを０に初期化する(ステップ３１)。
【００４２】
それぞれの文選択部に対して、ｊ番目の文選択部（本実施の形態では、文選択部１３，１４）への調整値を
【００４３】
【数５】
0005702744.tif 000006
とし、文選択結果
【００４４】
【数６】
0005702744.tif 000007
を得る(ステップ３３)。ここで、もし、
【００４５】
【数７】
0005702744.tif 000008
すなわち、全ての結果が一致するならば(ステップ３５、Yes)、
【００４６】
【数８】
0005702744.tif 000009
を解として出力し（ステップ４１）、処理を終了する。そうでないならば（ステップ３５，No）、
【００４７】
【数９】
0005702744.tif 000010
を求め(ステップ３６)、
【００４８】
【数１０】
0005702744.tif 000011
を求める(ステップ３８)。すなわち、1番目の文選択部に対するスコア調整値ベクトルuの符号はプラス、2番目以降(本実施例では文選択部１４)の符号はマイナスとする。この処理をｉがＮになるまで繰り返し、ｉ＞Ｎになれば（ステップ３９）、ｋ＝ｋ＋１として上記の処理をｋ＞Ｋになるまで繰り返し（ステップ４０）、事前に定めた回数(Ｋ＋１回)繰り返しても処理が終了しなければ、1番目の文選択部（本実施例では語頻度による文選択部１３）のK回目の結果である
【００４９】
【数１１】
0005702744.tif 000012
を出力する(ステップ４２)。
【００５０】
最後に、文並び替え部１５は、要約対象文書群と要約文生成部１２からの出力である文の集合を入力として、文を要約対象文書群に沿って並び替え、結合した文字列を出力する。
【００５１】
上記のように、本発明は、複数の要因を考慮する要約生成において、組み合わせた場合には最適解が得られなくとも、できる限り個々の文選択部において最適解を求め、それらの要因間で合意が得られなければパラメータベクトルｕを調整して、そのパラメータがある条件下で最適解を得られるようにする。これにより、計算は速いながらも、全てを近似で解く必要がなくなるため、要約の品質が向上する。
【００５２】
なお、本発明は、図1に示す文書要約装置の各構成要素の動作をプログラムとして構築し、文書要約装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５３】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５４】
１０  文書要約装置
１１  文書解析部
１２  要約生成部
１３  語頻度による文選択部
１４  冗長文排除による文選択部
１５  文並び替え部
【図１】
0005702744.tif 000013
【図２】
0005702744.tif 000014
【図３】
0005702744.tif 000015