テキスト要約装置とその方法とプログラム
【課題】より効率的な厳密解の探索が可能になる整数計画法を用いたテキスト要約装置を提供する。
【解決手段】整数計画部は、要約文章の対象となる複数のテキストを入力とし、文連接モデルパラメータ記録部に記録された任意の二つの文の繋がりの良さを計算するための素性パラメータを参照してテキストを構成する文の集合から情報の重要度を表わす内容性スコアと文の繋がりの良さを表す連接性スコアとの和が、最大となる文の順列を求める目的関数と制約条件を整数計画問題として設定する。目的関数最大化部は、予め設定される制約条件に基づいて目的関数を最大化する一つ以上の文及びそれら文の順列を表す決定変数を求める。テキスト出力部は、その決定変数に基づいて文を連結した要約文章を出力する。
【解決手段】整数計画部は、要約文章の対象となる複数のテキストを入力とし、文連接モデルパラメータ記録部に記録された任意の二つの文の繋がりの良さを計算するための素性パラメータを参照してテキストを構成する文の集合から情報の重要度を表わす内容性スコアと文の繋がりの良さを表す連接性スコアとの和が、最大となる文の順列を求める目的関数と制約条件を整数計画問題として設定する。目的関数最大化部は、予め設定される制約条件に基づいて目的関数を最大化する一つ以上の文及びそれら文の順列を表す決定変数を求める。テキスト出力部は、その決定変数に基づいて文を連結した要約文章を出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、テキスト（文書）を要約するテキスト要約装置とその方法と、プログラムに関する。
【背景技術】
【０００２】
近年、電子化されたテキストが大量に流通するようになった。そのため、それらのテキストに記述されている情報を迅速に把握するため、機械にテキストを要約させる技術が求められている。
【０００３】
現在、テキストを機械に要約させる際には、要約の対象となるテキストの内容を代表していると思われる重要文をテキストから一つ以上選び出し、それらを並び替え連結することで要約文章が作られることが多い。重要文を選択する際には、何らかの方法によって、文が持つ情報に内容性スコアを定義し、そのスコアに従って文を選択することがよく行われる。内容性スコアを定義する要素としては、文を構成する単語の重要度がよく用いられる（非特許文献１）。
【０００４】
重要文を抽出したのち、それらを並び替えることによって、要約の読み易さを向上させることが出来るので、複数の重要文を要約する場合には、文を適切に並び替える手段が必要となる。文を並び替える方法として、例えば非特許文献２に開示された重要文の抽出元のテキストが書かれた時間に従う方法。或いは、大規模なテキスト集合から文の並べ方を事前に学習して置き、学習の結果に従って並び替えるものなどが知られている（非特許文献３）。
【０００５】
また、探索のために、問題を整数計画問題として定式化し、ビームサーチの代わりに例えば非特許文献４に開示された分枝限定法等のアルゴリズムを用いることで、探索を高速に行う方法がある（非特許文献５）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Elena Filatova and Vasileios Hatzivassiloglou. “A formal model for information selection in multi-sentence text extraction”. In Proceedings of the 20thInternational Conference on Computational Linguistics (COLING), 2004.
【非特許文献２】Regina Barzilay, Noemie Elhadad and Kathleen R. McKeown. “Inferring Strategies for Sentence Ordering in Multidocument News Summarization”. In Journal of Artificial Intelligence Research (JAIR), Vol.17, pp.35-55, 2002.
【非特許文献３】Mirella Lapata. “Probabilistic Text Structuring: Experiments with Sentence Ordering”. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL), 2003.
【非特許文献４】今野浩、鈴木久敏（編）「整数計画法と組み合わせ最適化」日科技連出版社，1982.
【非特許文献５】Pawan Deshpande, Regina Barzilay and David R. Karger. “Randomized Decoding for Selection-and-Ordering Problems”. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
学習結果に従って、文を並び替える方法は、厳密解を得るためには、ビームサーチのビーム幅を大きくする必要があり多大な探索時間が必要である。また、ビームサーチの代わりに整数計画問題として定式化して探索を高速化する従来方法は、テキストからヘッドラインを生成するものであり、複数のテキストから一つ以上の文を選択し、並び替えて要約を生成するものではない。
【０００８】
この発明は、このような課題に鑑みてなされたものであり、複数の重要文の順列を探索する整数計画問題として新しい定式化を記述することで、より効率的な厳密解の探索が可能になるテキスト要約装置と、その方法とプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
この発明のテキスト要約装置は、文連接モデルパラメータ記録部と、整数計画部と、目的関数最大化部と、テキスト出力部と、を備える。文連接モデルパラメータ記録部は、任意の二つの文の繋がりの良さを計算するための素性パラメータを記録する。整数計画部は、要約文章の対象となる複数のテキストを入力とし、その素性パラメータを参照して上記テキストを構成する文の集合から情報の重要度を表わす内容性スコアと文の繋がりの良さを表す連接性スコアとの和が最大となる文の順列を求める目的関数と制約条件を、整数計画問題として設定する。目的関数最大化部は、予め設定される制約条件に基づいて目的関数を最大化する一つ以上の文及びそれら文の順列を表す決定変数を求める。テキスト出力部は、その決定変数に基づいて文を連結した要約文章を出力する。
【発明の効果】
【００１０】
この発明のテキスト要約装置は、重要文の選択と並び替えを同時に行う要約文章の探索において、ビームサーチでは無く、整数計画法を用いるため、高速に厳密解を得ることが出来る。
【図面の簡単な説明】
【００１１】
【図１】この発明のテキスト要約装置１００の機能構成例を示す図。
【図２】テキスト要約装置１００の動作フローを示す図。
【図３】素性パラメータの一例を示す図。
【図４】平均化パーセプトロンによる重みパラメータ学習アルゴリズムのフローを示す図。
【図５】整数計画部１０のより具体的な機能構成例を示す図。
【図６】整数計画部１０の動作フローを示す図。
【図７】二つの例文を形態素解析した結果を示す図。
【図８】直積集合と素性ベクトルφ(si,sj)の例を示す図。
【図９】三つのテキストから要約文章が作られる例を有向グラフで示す図。
【図１０】文と情報の包含関係の一例を示す図。
【図１１】二つの例文についての文と情報の包含関係を示す図。
【図１２】閉路の例を示す図。
【発明を実施するための形態】
【００１２】
以下、この発明の実施の形態を図面を参照して説明する。複数の図面中同一のものには
同じ参照符号を付し、説明は繰り返さない。
【実施例１】
【００１３】
図１にこの発明のテキスト要約装置１００の機能構成例を示す。その動作フローを図２に示す。テキスト要約装置１００は、複数のテキストを入力としてそれらのテキストを要約した要約文章を出力するものであり、文連接モデルパラメータ記録部１０と、整数計画部２０と、目的関数最大化部３０と、テキスト出力部４０と、を具備する。テキスト要約装置１００の各部の機能は、例えばＲＯＭ、ＲＡＭ、ＣＰＵ等で構成されるコンピュータに所定のプログラムが読み込まれて、ＣＰＵがそのプログラムを実行することで実現されるものである。
【００１４】
図１は、形態素解析されたテキストが入力される例を示す。形態素解析処理は周知であり、例えば参考文献「特許第３３７９６４３号」に記載されている。形態素解析処理が施されていないテキストが入力される場合には、破線で示すように形態素解析部５０を設ければ良い。
【００１５】
文連接モデルパラメータ記録部１０は、任意の二つの文の繋がりの良さを表す素性パラメータを記録する。素性パラメータについて、詳しくは後述する。
【００１６】
整数計画部２０は、文連接モデルパラメータ記録部１０に記録された素性パラメータを参照して上記テキストを構成する文の集合から内容性スコアと連接性スコアが最大となる文の順列を求める目的関数と制約条件を、整数計画問題として設定する（ステップＳ２０）。整数計画問題とは、線形計画問題において解ベクトルの各要素を整数に限定した問題をいう。
【００１７】
目的関数最大化部３０は、予め設定された制約条件に基づいて上記目的関数を最大化する一つ以上の文及びそれらの順列を表す決定変数を求める（ステップＳ３０）。テキスト出力部４０は、目的関数最大化部３０が出力する決定変数に基づいて文を連結して要約文章を出力する（ステップＳ４０）。
【００１８】
以上のように、テキスト要約装置１００は、整数計画法を用いて内容性スコアと連接性スコアが最大となる文とその順列を求めるので、従来法よりも高速に要約文章の厳密解を得ることが出来る。
【００１９】
次に、各部の機能構成について具体例を示して更に詳しく説明する。先ず、文連接モデルパラメータ記録部１０に記録される素性パラメータについて説明する。
【００２０】
〔素性パラメータ〕
素性パラメータは、二つの文の繋がりの良さを表すパラメータである。その一例を図３に示す。図３の左側の二つの列は、前後二つの文を構成する単語（例えば内容語である名詞、動詞、形容詞等）であり、素性（ソセイ）は前の文に含まれる単語の一つと、後ろの文に含まれる単語の一つの組のことである。１行目は、前の文に含まれる「料理」という単語と、後ろの文に含まれる「夜景」という単語からなる素性の、素性パラメータを表す。「料理」を含む文の後に「友達」を含む文が続く場合に対応する素性は、素性パラメータが他の素性と比較して大きな値を持つので、そのような二つの文の繋がりの良いことを示唆している。逆に、「料理」を含む文の後に「夜景」を含む文が繋がる場合は、素性パラメータの値は小さく、そのような二つの文の繋がりが良くないことを示唆している。
【００２１】
この素性パラメータは、例えば、平均化パーセプトロンによる重みパラメータ学習アルゴリズム（参考文献：Michael Collins, “Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms”. In Proceedings of the 2002 Conference on Empirical Methods on Natural Language Processing (EMNLP), Association for Computational Linguistics, 2002, volume 10, pp.1-8)によって求められる。
【００２２】
図４に、その重みパラメータ学習アルゴリズムを示す。ステップＳ２０１で、各変数を初期化する。そして、現在の素性パラメータの値wを用いて得られる可能な文の並びの内、連接スコアwTφ(x,y)が最大になる文の並びy’を求める（ステップＳ２０２）。
【００２３】
求めた文の並びy’が正解の文の並びyqと等しく無い場合（ステップＳ２０３のｙ）、現在の素性パラメータwでは正しい並びを再現することが出来なかったことになる。その時は素性パラメータwを更新し、正しく文を並び替えることが出来るようにする（ステップＳ２０４）、等しい場合は現在のwを更新しない（ステップＳ２０５）。この処理を、Ｑ個の訓練データに対して行う（ステップＳ２０８のｎ）。更に、Ｑ個の訓練データに対する処理をＮ回繰り返して素性パラメータを更新し、更新した値vを更新した回数（N×Q）で除して平均化した値を素性パラメータwとする。
【００２４】
図５に、より具体的な整数計画部１０の機能構成例を示す。その動作フローを図６に示す。整数計画部１０は、前処理部１５と、連接性スコア関数生成部１１と、内容性スコア関数生成部１２と、目的関数生成部１３と、制約条件生成部１４と、を具備する。
【００２５】
〔前処理部〕
前処理部１５は、更に、文数計数手段１５０と、情報包含検出手段１５１とを備える。文数計数手段１５０は、要約文章を作成する対象となるテキストを構成する文の数nを計数する（ステップＳ１５０）。情報包含検出手段１５１は、文が含む情報を検出して変数mとdi,kを出力する（ステップＳ１５１）。例えば、文s1が情報e1とe3とem-1を含む場合、変数d1,1,d1,3,d1,m-1を１として出力する。変数mは、要約を作成する対象となるテキストが含む情報の数である。
【００２６】
文の数nは、直積集合生成手段１１０と制約条件生成手段１４１に出力される。変数mは情報重み算出手段１２１に、変数di,kは制約条件生成手段１４１に出力される。このように、前処理部１５は整数計画部１０を構成する各機能構成が必要とする変数を取得するものである。
【００２７】
図５では、前処理部１０を他の機能構成から分離した形で示したが、前処理部１０の機能は、複数の文Ｓが入力される各機能構成部に含めても良い。例えば文数計数手段１５０を、連接性スコア関数生成部１１と制約条件生成部１４の中に別々に設けるようにしても構わない。
【００２８】
〔連接性スコア関数生成部〕
連接性スコア関数生成部１１は、更に、直積集合生成手段１１０と、素性ベクトル変換手段１１１と、内積計算手段１１２と、連接性スコア関数生成手段１１３とを備える。直積集合生成手段１１０は、複数の文Ｓを、それぞれの文を構成する単語に分解し、任意の二つの文を構成する単語の直積集合を素性として生成する（ステップＳ１１０）。
【００２９】
素性とは、上記したように、前後の文を構成する単語（例えば名詞、動詞、形容詞等）の組のことである。テキストを形態素解析することで、文を単語に分解することが出来る。図７に、ｓi：「昨日ご飯を食べました。」とｓｊ：「しかしあまりおいしくありませんでした。」の二つの文を、形態素解析した結果を示す。図７の各行が一形態素に対応しており、形態素の表記、品詞、読み、標準形の情報が得られる。＜ＥＯＳ＞は文境界を表す。なお、単語として、内容語以外の文を構成する要素特徴を用いても良い。
【００３０】
この二つの文を例に説明すると、直積集合生成手段１１０は、形態素解析済みの二つの文ｓiとｓｊを、内容語の「昨日」、「ご飯」、「食べ」と、「おいし」、「あ」に分解し、それらの直積集合を生成する（図８参照）。この例の場合、直積集合は、「昨日−おいし」、「昨日−あ」、「ご飯−おいし」、「ご飯−あ」、「食べ−おいし」、「食べ−あ」の６つの要素から成り、この要素それぞれが素性となる。
【００３１】
素性ベクトル変換手段１１１は、入力される直積集合を、その直積集合の要素と対応する要素が文連接モデルパラメータ記録部３０に含まれる場合は１、そうで無い場合は０とする素性ベクトルφ(si,sj)に変換する（ステップＳ１１１、式（１））。
【００３２】
【数１】
【００３３】
内積計算手段１１２は、素性パラメータwを要素とする重みベクトルwＴと、素性ベクトルφ(si,sj)の内積ci,j（式（２））を計算する（ステップＳ１１２）。
【００３４】
【数２】
【００３５】
内積ci,jは、二つの文の繋がりの良さを表す指標となる。
【００３６】
連接性スコア関数生成手段１１３は、要約文章に含まれる文の内積ci,jの累積値を、連接性スコア関数（式（３））として生成する（ステップＳ１１３）。
【００３７】
【数３】
【００３８】
ここでyi,jは、要約文章を構成する文を結ぶ有向辺を示す決定変数であり、この決定変数yi,jについて説明する。図９に、３つのテキストから要約文章が作られる例を有向グラフで示す。テキスト１は３つの文ｓ1，ｓ2，ｓ3から成る。テキスト２は二つの文ｓ4，ｓ5、テキスト３は４つの文ｓ6，ｓ7，ｓ8，ｓ9から成る。また、要約の対象となるテキストを構成する文の数をnとする。この例ではn=9である。
【００３９】
図９は、重要文としてｓ1，ｓ3，ｓ7，ｓ5が選ばれ、それらがその順に並べられて要約文章が構成されることを示している。要約文章を整数計画問題として表現するため、文ｓ1〜snが、それぞれ要約文章に含まれていれば１、含まれていなければ０となる決定変数ｘ1〜ｘnを考える。
【００４０】
ｓ0は要約文章の文の始まりを定義するための仮想の文である。また、s10はこの例において要約文章の終わりを定義するための仮想の文である。ｓ0にはx0、s10にはx10が対応する。この例では、x0，x1，x3，x5，x7，x10が１となる。
【００４１】
そして、文同士の繋がりを有向辺で表現する。文siからsjへの有向辺をai,jで表す。この有向辺に対する決定変数がyi,jである。この例では、要約文章に含まれる文同士を結ぶ有向辺ai,jに対応するy0,1，y1,3，y3,7，y7,5，y5,10が１である。この決定変数yi,jに、上記した内積ci,jが紐付けられている。つまり、連接性スコア関数は、要約文章に含まれる文の繋がりの良さを累積するものである。
【００４２】
〔内容性スコア関数生成部〕
内容性スコア関数生成部１２は、情報重み算出手段１２１と内容性スコア関数生成手段１２２を備え、内容性スコア関数（式（４））を定義する。
【００４３】
【数４】
【００４４】
ここでzｋは、要約文章に何らかの情報ekが含まれることを示す決定変数であり、この決定変数zｋについて説明する。
【００４５】
文s1〜snが、何らかの情報e1，e2，…，em-1，emを含んでいるものとする。そして、ある文siがある情報ekを含んでいることを変数di,kで表現する。例えば、文s1が情報e3を含んでいる場合、d1,3が１になるものとする。
【００４６】
図１０に、文と情報の包含関係の一例を示す。縦方向に文s1〜sn、横方向に情報e1〜emが並べられている。文s1は、情報e1とe3とem-１を含むので、対応する変数d1,1,d1,3,d1,m-1が１となる。ある文において、その文が含まない情報に対応するdは０である。例えば文s1は、情報e2を含まないため、d1,2は０である。例えば、図１０の文s1が要約文章に含まれる場合、情報e1とe3とem-1に対応する決定変数zkのz1,z3,zm-1が１となる。
【００４７】
情報eの単位としては、例えば、テキストを形態素解析した結果の品詞や名詞、動詞語幹や形容詞語幹を用いることが出来る。図１１に、上記した二つの例文についての文と情報の包含関係を示す。図１１に示すように、例えば内容語を情報eの単位にしても良い。
【００４８】
情報ekは、それぞれに対応する何らかの尺度に基づく重要度ukを持っているものとする。重要度は、例えばテキスト中の単語の頻度などを用いることが出来る。
【００４９】
情報重み算出手段１２１は、文に含まれる単語の頻度ukを計数して、その単語（情報）の重要度とする（ステップＳ１２１、図６）。内容性スコア関数生成部１２２は、その重要度と文に含まれる情報を表す変数との積の累積を計算する（ステップＳ１２２）。つまり、内容性スコア関数は、要約文章に含まれる情報を含む文の重要度を累積するものである。
【００５０】
なお、重要度としては、各単語の重みを記録したデータベースを参照して、その重みを累積して求めても良い。また、単語毎では無く、ある程度まとまった文単位で重要度を求めるようにしても良い。
【００５１】
〔目的関数生成部〕
好ましい要約文章は、上記した内容性スコアと連接性スコアとが共に高いものと考えられる。そこで、目的関数生成部１３は、整数計画問題における目的関数を式（５）に示すように設定する。
【００５２】
【数５】
【００５３】
ここでλは、内容性スコアと連接性スコアの重要度を調整するパラメータであり、予め定数として設定して置いても良いし、外部から与えても良い。目的関数SummaryScoreは、要約文章に含まれる情報とその重みとの積の累積した内容性スコアと、素性パラメータを要素とする重みベクトルと素性ベクトルの内積を累積した連接性スコアの重み付き線形和である。
【００５４】
〔制約条件生成部〕
制約条件生成部１４は、決定変数ｘi，yi,j，zkの制約条件を生成する。制約条件生成部１４は、文長計算手段１４０と、制約条件生成手段１４１と、を備える。
【００５５】
文長計算手段１４０は、各文の長さliを計数する（ステップＳ１４０）。文の長さliは、単語の数でも文字数でも良い。制約条件生成手段１４１は、変数di,kと文の長さliと文の数nを入力として、以降に示す制約条件を生成する（ステップＳ１４１）。
【００５６】
【数６】
【００５７】
式（６）は、要約文章の長さに関する制約である。要約文章の最大の長さをKとしたとき、上記した図９の場合、ｌ1+l3+l5+l7の長さがK以内でなければならない。
【００５８】
式（７）は、要約文章に情報ekを含むためには、すなわちzkが１となるには、情報ekを含む文が一つ以上要約に含まれる必要があることを示す制約である。式（８）は、決定変数x,y,zは０又は１の値を取るという制約である。この制約により、文が要約文章に0.5個選ばれるといった要約として適当で無い解を除去することが出来る。
【００５９】
また、文と文を接続する有向辺に関して下記の制約を設定する。
【００６０】
【数７】
【００６１】
式（９）と式（１０）は、要約文章の始点と終点を表すx0とxn+1は必ず要約文章に含まれることを意味する制約である。式（１１）と式（１２）は、始点からは必ず一つの有向辺が出ること及び始点に入って来る有向辺は無いことを示す制約である。
【００６２】
式（１３）と式（１４）は、終点から出る有向辺は無いこと及び終点に入って来る有向辺が必ず一つあることを示す制約である。式（１５）は、要約文章に含まれる文は必ず二つの有向辺を持つことを意味する制約である。式（１６）は、要約文章に含まれる文は必ず入って来る有向辺と出て行く有向辺をそれぞれ持つことを意味する制約である。
【００６３】
式（９）〜式（１６）に示す制約だけでは、閉路の発生を防ぐことが出来ない。図１２に閉路の例を示す。s5とs7に閉路が構成されており適当な要約文章では無い。このような閉路の発生を防ぐためには、次の制約を加える必要がある。
【００６４】
【数８】
【００６５】
式（１７）は、始点からｎ単位のフローが流される制約を示す。式（１８）は、終点に必ず１単位以上のフローが到着する制約を示す。式（１９）は、要約文章に含まれる文は必ず１単位のフローを消費する制約を示す。式（２０）は、要約文章に含まれる有向辺は必ず１単位以上のフローを流す制約を示す。
【００６６】
式（１７）〜式（２０）の制約は、始点からｎ単位の「フロー」ｆが流され、有向辺に従って終点に向かって流れて行き、有向辺を接続する文でそのフローが１単位ずつ消費されて行くことを示している。この制約によって閉路の発生を防止することが出来る。
【００６７】
〔目的関数最大化部〕
目的関数最大化部３０は、上記した目的関数と制約条件の集合を入力として、与えられた制約条件を満たす解の内で目的関数を最大にする決定変数ｘi，yi,j，zｋ，fi,jを探索する（式２１））。探索には、周知の分枝限定アルゴリズム（非特許文献４）を用いることが出来る。
【００６８】
【数９】
【００６９】
〔テキスト出力部〕
テキスト出力部４０は、目的関数を最大にする決定変数yi,j又はfi,jを入力とし、文を連結した要約文章として出力する。その動作を上記した図９の例で説明する。要約文章に含まれる文同士を結ぶ有向辺を表す決定変数yi,jは、y0,1=1,y1,3=1,y3,7=1,y7,5=1,y5,10=1であり、他の、y0,2等は０である。また、有向辺ai,j上を流れるフローの量を表す決定変数fi,jは、f0,1=9，f1,3=8，f3,7=7，f7,5=6，f5,10=5である。これらの決定変数から、テキスト出力部４０は、s1とs3とs7とｓ5の順番に文を並べた要約文章を出力する。
【００７０】
なお、文連接モデルパラメータ記録部１０に記録される素性パラメータは任意の二つの文の繋がりの良さを計算するパラメータとし、連接性スコア関数生成部１１も二つの文の繋がりの良さを累積する方法を説明したが、この発明はこの方法に限定されない。例えば三つ以上の文の間の繋がりの良さを評価して連接性スコアを求めるようにしても良い。また、制約条件生成部１４が生成する制約条件も上記した例以外のものも考えられる。
【００７１】
また、文長計算手段１４０を制約条件生成部１４に含める例で説明したが、文長計算手段１４０を、前処理部１５０に含めても良い。また、上記方法及び装置において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００７２】
また、上記装置における処理手段をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各装置における処理手段がコンピュータ上で実現される。
【００７３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）/ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００７４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記録装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７５】
また、各手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【技術分野】
【０００１】
この発明は、テキスト（文書）を要約するテキスト要約装置とその方法と、プログラムに関する。
【背景技術】
【０００２】
近年、電子化されたテキストが大量に流通するようになった。そのため、それらのテキストに記述されている情報を迅速に把握するため、機械にテキストを要約させる技術が求められている。
【０００３】
現在、テキストを機械に要約させる際には、要約の対象となるテキストの内容を代表していると思われる重要文をテキストから一つ以上選び出し、それらを並び替え連結することで要約文章が作られることが多い。重要文を選択する際には、何らかの方法によって、文が持つ情報に内容性スコアを定義し、そのスコアに従って文を選択することがよく行われる。内容性スコアを定義する要素としては、文を構成する単語の重要度がよく用いられる（非特許文献１）。
【０００４】
重要文を抽出したのち、それらを並び替えることによって、要約の読み易さを向上させることが出来るので、複数の重要文を要約する場合には、文を適切に並び替える手段が必要となる。文を並び替える方法として、例えば非特許文献２に開示された重要文の抽出元のテキストが書かれた時間に従う方法。或いは、大規模なテキスト集合から文の並べ方を事前に学習して置き、学習の結果に従って並び替えるものなどが知られている（非特許文献３）。
【０００５】
また、探索のために、問題を整数計画問題として定式化し、ビームサーチの代わりに例えば非特許文献４に開示された分枝限定法等のアルゴリズムを用いることで、探索を高速に行う方法がある（非特許文献５）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Elena Filatova and Vasileios Hatzivassiloglou. “A formal model for information selection in multi-sentence text extraction”. In Proceedings of the 20thInternational Conference on Computational Linguistics (COLING), 2004.
【非特許文献２】Regina Barzilay, Noemie Elhadad and Kathleen R. McKeown. “Inferring Strategies for Sentence Ordering in Multidocument News Summarization”. In Journal of Artificial Intelligence Research (JAIR), Vol.17, pp.35-55, 2002.
【非特許文献３】Mirella Lapata. “Probabilistic Text Structuring: Experiments with Sentence Ordering”. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL), 2003.
【非特許文献４】今野浩、鈴木久敏（編）「整数計画法と組み合わせ最適化」日科技連出版社，1982.
【非特許文献５】Pawan Deshpande, Regina Barzilay and David R. Karger. “Randomized Decoding for Selection-and-Ordering Problems”. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
学習結果に従って、文を並び替える方法は、厳密解を得るためには、ビームサーチのビーム幅を大きくする必要があり多大な探索時間が必要である。また、ビームサーチの代わりに整数計画問題として定式化して探索を高速化する従来方法は、テキストからヘッドラインを生成するものであり、複数のテキストから一つ以上の文を選択し、並び替えて要約を生成するものではない。
【０００８】
この発明は、このような課題に鑑みてなされたものであり、複数の重要文の順列を探索する整数計画問題として新しい定式化を記述することで、より効率的な厳密解の探索が可能になるテキスト要約装置と、その方法とプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
この発明のテキスト要約装置は、文連接モデルパラメータ記録部と、整数計画部と、目的関数最大化部と、テキスト出力部と、を備える。文連接モデルパラメータ記録部は、任意の二つの文の繋がりの良さを計算するための素性パラメータを記録する。整数計画部は、要約文章の対象となる複数のテキストを入力とし、その素性パラメータを参照して上記テキストを構成する文の集合から情報の重要度を表わす内容性スコアと文の繋がりの良さを表す連接性スコアとの和が最大となる文の順列を求める目的関数と制約条件を、整数計画問題として設定する。目的関数最大化部は、予め設定される制約条件に基づいて目的関数を最大化する一つ以上の文及びそれら文の順列を表す決定変数を求める。テキスト出力部は、その決定変数に基づいて文を連結した要約文章を出力する。
【発明の効果】
【００１０】
この発明のテキスト要約装置は、重要文の選択と並び替えを同時に行う要約文章の探索において、ビームサーチでは無く、整数計画法を用いるため、高速に厳密解を得ることが出来る。
【図面の簡単な説明】
【００１１】
【図１】この発明のテキスト要約装置１００の機能構成例を示す図。
【図２】テキスト要約装置１００の動作フローを示す図。
【図３】素性パラメータの一例を示す図。
【図４】平均化パーセプトロンによる重みパラメータ学習アルゴリズムのフローを示す図。
【図５】整数計画部１０のより具体的な機能構成例を示す図。
【図６】整数計画部１０の動作フローを示す図。
【図７】二つの例文を形態素解析した結果を示す図。
【図８】直積集合と素性ベクトルφ(si,sj)の例を示す図。
【図９】三つのテキストから要約文章が作られる例を有向グラフで示す図。
【図１０】文と情報の包含関係の一例を示す図。
【図１１】二つの例文についての文と情報の包含関係を示す図。
【図１２】閉路の例を示す図。
【発明を実施するための形態】
【００１２】
以下、この発明の実施の形態を図面を参照して説明する。複数の図面中同一のものには
同じ参照符号を付し、説明は繰り返さない。
【実施例１】
【００１３】
図１にこの発明のテキスト要約装置１００の機能構成例を示す。その動作フローを図２に示す。テキスト要約装置１００は、複数のテキストを入力としてそれらのテキストを要約した要約文章を出力するものであり、文連接モデルパラメータ記録部１０と、整数計画部２０と、目的関数最大化部３０と、テキスト出力部４０と、を具備する。テキスト要約装置１００の各部の機能は、例えばＲＯＭ、ＲＡＭ、ＣＰＵ等で構成されるコンピュータに所定のプログラムが読み込まれて、ＣＰＵがそのプログラムを実行することで実現されるものである。
【００１４】
図１は、形態素解析されたテキストが入力される例を示す。形態素解析処理は周知であり、例えば参考文献「特許第３３７９６４３号」に記載されている。形態素解析処理が施されていないテキストが入力される場合には、破線で示すように形態素解析部５０を設ければ良い。
【００１５】
文連接モデルパラメータ記録部１０は、任意の二つの文の繋がりの良さを表す素性パラメータを記録する。素性パラメータについて、詳しくは後述する。
【００１６】
整数計画部２０は、文連接モデルパラメータ記録部１０に記録された素性パラメータを参照して上記テキストを構成する文の集合から内容性スコアと連接性スコアが最大となる文の順列を求める目的関数と制約条件を、整数計画問題として設定する（ステップＳ２０）。整数計画問題とは、線形計画問題において解ベクトルの各要素を整数に限定した問題をいう。
【００１７】
目的関数最大化部３０は、予め設定された制約条件に基づいて上記目的関数を最大化する一つ以上の文及びそれらの順列を表す決定変数を求める（ステップＳ３０）。テキスト出力部４０は、目的関数最大化部３０が出力する決定変数に基づいて文を連結して要約文章を出力する（ステップＳ４０）。
【００１８】
以上のように、テキスト要約装置１００は、整数計画法を用いて内容性スコアと連接性スコアが最大となる文とその順列を求めるので、従来法よりも高速に要約文章の厳密解を得ることが出来る。
【００１９】
次に、各部の機能構成について具体例を示して更に詳しく説明する。先ず、文連接モデルパラメータ記録部１０に記録される素性パラメータについて説明する。
【００２０】
〔素性パラメータ〕
素性パラメータは、二つの文の繋がりの良さを表すパラメータである。その一例を図３に示す。図３の左側の二つの列は、前後二つの文を構成する単語（例えば内容語である名詞、動詞、形容詞等）であり、素性（ソセイ）は前の文に含まれる単語の一つと、後ろの文に含まれる単語の一つの組のことである。１行目は、前の文に含まれる「料理」という単語と、後ろの文に含まれる「夜景」という単語からなる素性の、素性パラメータを表す。「料理」を含む文の後に「友達」を含む文が続く場合に対応する素性は、素性パラメータが他の素性と比較して大きな値を持つので、そのような二つの文の繋がりの良いことを示唆している。逆に、「料理」を含む文の後に「夜景」を含む文が繋がる場合は、素性パラメータの値は小さく、そのような二つの文の繋がりが良くないことを示唆している。
【００２１】
この素性パラメータは、例えば、平均化パーセプトロンによる重みパラメータ学習アルゴリズム（参考文献：Michael Collins, “Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms”. In Proceedings of the 2002 Conference on Empirical Methods on Natural Language Processing (EMNLP), Association for Computational Linguistics, 2002, volume 10, pp.1-8)によって求められる。
【００２２】
図４に、その重みパラメータ学習アルゴリズムを示す。ステップＳ２０１で、各変数を初期化する。そして、現在の素性パラメータの値wを用いて得られる可能な文の並びの内、連接スコアwTφ(x,y)が最大になる文の並びy’を求める（ステップＳ２０２）。
【００２３】
求めた文の並びy’が正解の文の並びyqと等しく無い場合（ステップＳ２０３のｙ）、現在の素性パラメータwでは正しい並びを再現することが出来なかったことになる。その時は素性パラメータwを更新し、正しく文を並び替えることが出来るようにする（ステップＳ２０４）、等しい場合は現在のwを更新しない（ステップＳ２０５）。この処理を、Ｑ個の訓練データに対して行う（ステップＳ２０８のｎ）。更に、Ｑ個の訓練データに対する処理をＮ回繰り返して素性パラメータを更新し、更新した値vを更新した回数（N×Q）で除して平均化した値を素性パラメータwとする。
【００２４】
図５に、より具体的な整数計画部１０の機能構成例を示す。その動作フローを図６に示す。整数計画部１０は、前処理部１５と、連接性スコア関数生成部１１と、内容性スコア関数生成部１２と、目的関数生成部１３と、制約条件生成部１４と、を具備する。
【００２５】
〔前処理部〕
前処理部１５は、更に、文数計数手段１５０と、情報包含検出手段１５１とを備える。文数計数手段１５０は、要約文章を作成する対象となるテキストを構成する文の数nを計数する（ステップＳ１５０）。情報包含検出手段１５１は、文が含む情報を検出して変数mとdi,kを出力する（ステップＳ１５１）。例えば、文s1が情報e1とe3とem-1を含む場合、変数d1,1,d1,3,d1,m-1を１として出力する。変数mは、要約を作成する対象となるテキストが含む情報の数である。
【００２６】
文の数nは、直積集合生成手段１１０と制約条件生成手段１４１に出力される。変数mは情報重み算出手段１２１に、変数di,kは制約条件生成手段１４１に出力される。このように、前処理部１５は整数計画部１０を構成する各機能構成が必要とする変数を取得するものである。
【００２７】
図５では、前処理部１０を他の機能構成から分離した形で示したが、前処理部１０の機能は、複数の文Ｓが入力される各機能構成部に含めても良い。例えば文数計数手段１５０を、連接性スコア関数生成部１１と制約条件生成部１４の中に別々に設けるようにしても構わない。
【００２８】
〔連接性スコア関数生成部〕
連接性スコア関数生成部１１は、更に、直積集合生成手段１１０と、素性ベクトル変換手段１１１と、内積計算手段１１２と、連接性スコア関数生成手段１１３とを備える。直積集合生成手段１１０は、複数の文Ｓを、それぞれの文を構成する単語に分解し、任意の二つの文を構成する単語の直積集合を素性として生成する（ステップＳ１１０）。
【００２９】
素性とは、上記したように、前後の文を構成する単語（例えば名詞、動詞、形容詞等）の組のことである。テキストを形態素解析することで、文を単語に分解することが出来る。図７に、ｓi：「昨日ご飯を食べました。」とｓｊ：「しかしあまりおいしくありませんでした。」の二つの文を、形態素解析した結果を示す。図７の各行が一形態素に対応しており、形態素の表記、品詞、読み、標準形の情報が得られる。＜ＥＯＳ＞は文境界を表す。なお、単語として、内容語以外の文を構成する要素特徴を用いても良い。
【００３０】
この二つの文を例に説明すると、直積集合生成手段１１０は、形態素解析済みの二つの文ｓiとｓｊを、内容語の「昨日」、「ご飯」、「食べ」と、「おいし」、「あ」に分解し、それらの直積集合を生成する（図８参照）。この例の場合、直積集合は、「昨日−おいし」、「昨日−あ」、「ご飯−おいし」、「ご飯−あ」、「食べ−おいし」、「食べ−あ」の６つの要素から成り、この要素それぞれが素性となる。
【００３１】
素性ベクトル変換手段１１１は、入力される直積集合を、その直積集合の要素と対応する要素が文連接モデルパラメータ記録部３０に含まれる場合は１、そうで無い場合は０とする素性ベクトルφ(si,sj)に変換する（ステップＳ１１１、式（１））。
【００３２】
【数１】
【００３３】
内積計算手段１１２は、素性パラメータwを要素とする重みベクトルwＴと、素性ベクトルφ(si,sj)の内積ci,j（式（２））を計算する（ステップＳ１１２）。
【００３４】
【数２】
【００３５】
内積ci,jは、二つの文の繋がりの良さを表す指標となる。
【００３６】
連接性スコア関数生成手段１１３は、要約文章に含まれる文の内積ci,jの累積値を、連接性スコア関数（式（３））として生成する（ステップＳ１１３）。
【００３７】
【数３】
【００３８】
ここでyi,jは、要約文章を構成する文を結ぶ有向辺を示す決定変数であり、この決定変数yi,jについて説明する。図９に、３つのテキストから要約文章が作られる例を有向グラフで示す。テキスト１は３つの文ｓ1，ｓ2，ｓ3から成る。テキスト２は二つの文ｓ4，ｓ5、テキスト３は４つの文ｓ6，ｓ7，ｓ8，ｓ9から成る。また、要約の対象となるテキストを構成する文の数をnとする。この例ではn=9である。
【００３９】
図９は、重要文としてｓ1，ｓ3，ｓ7，ｓ5が選ばれ、それらがその順に並べられて要約文章が構成されることを示している。要約文章を整数計画問題として表現するため、文ｓ1〜snが、それぞれ要約文章に含まれていれば１、含まれていなければ０となる決定変数ｘ1〜ｘnを考える。
【００４０】
ｓ0は要約文章の文の始まりを定義するための仮想の文である。また、s10はこの例において要約文章の終わりを定義するための仮想の文である。ｓ0にはx0、s10にはx10が対応する。この例では、x0，x1，x3，x5，x7，x10が１となる。
【００４１】
そして、文同士の繋がりを有向辺で表現する。文siからsjへの有向辺をai,jで表す。この有向辺に対する決定変数がyi,jである。この例では、要約文章に含まれる文同士を結ぶ有向辺ai,jに対応するy0,1，y1,3，y3,7，y7,5，y5,10が１である。この決定変数yi,jに、上記した内積ci,jが紐付けられている。つまり、連接性スコア関数は、要約文章に含まれる文の繋がりの良さを累積するものである。
【００４２】
〔内容性スコア関数生成部〕
内容性スコア関数生成部１２は、情報重み算出手段１２１と内容性スコア関数生成手段１２２を備え、内容性スコア関数（式（４））を定義する。
【００４３】
【数４】
【００４４】
ここでzｋは、要約文章に何らかの情報ekが含まれることを示す決定変数であり、この決定変数zｋについて説明する。
【００４５】
文s1〜snが、何らかの情報e1，e2，…，em-1，emを含んでいるものとする。そして、ある文siがある情報ekを含んでいることを変数di,kで表現する。例えば、文s1が情報e3を含んでいる場合、d1,3が１になるものとする。
【００４６】
図１０に、文と情報の包含関係の一例を示す。縦方向に文s1〜sn、横方向に情報e1〜emが並べられている。文s1は、情報e1とe3とem-１を含むので、対応する変数d1,1,d1,3,d1,m-1が１となる。ある文において、その文が含まない情報に対応するdは０である。例えば文s1は、情報e2を含まないため、d1,2は０である。例えば、図１０の文s1が要約文章に含まれる場合、情報e1とe3とem-1に対応する決定変数zkのz1,z3,zm-1が１となる。
【００４７】
情報eの単位としては、例えば、テキストを形態素解析した結果の品詞や名詞、動詞語幹や形容詞語幹を用いることが出来る。図１１に、上記した二つの例文についての文と情報の包含関係を示す。図１１に示すように、例えば内容語を情報eの単位にしても良い。
【００４８】
情報ekは、それぞれに対応する何らかの尺度に基づく重要度ukを持っているものとする。重要度は、例えばテキスト中の単語の頻度などを用いることが出来る。
【００４９】
情報重み算出手段１２１は、文に含まれる単語の頻度ukを計数して、その単語（情報）の重要度とする（ステップＳ１２１、図６）。内容性スコア関数生成部１２２は、その重要度と文に含まれる情報を表す変数との積の累積を計算する（ステップＳ１２２）。つまり、内容性スコア関数は、要約文章に含まれる情報を含む文の重要度を累積するものである。
【００５０】
なお、重要度としては、各単語の重みを記録したデータベースを参照して、その重みを累積して求めても良い。また、単語毎では無く、ある程度まとまった文単位で重要度を求めるようにしても良い。
【００５１】
〔目的関数生成部〕
好ましい要約文章は、上記した内容性スコアと連接性スコアとが共に高いものと考えられる。そこで、目的関数生成部１３は、整数計画問題における目的関数を式（５）に示すように設定する。
【００５２】
【数５】
【００５３】
ここでλは、内容性スコアと連接性スコアの重要度を調整するパラメータであり、予め定数として設定して置いても良いし、外部から与えても良い。目的関数SummaryScoreは、要約文章に含まれる情報とその重みとの積の累積した内容性スコアと、素性パラメータを要素とする重みベクトルと素性ベクトルの内積を累積した連接性スコアの重み付き線形和である。
【００５４】
〔制約条件生成部〕
制約条件生成部１４は、決定変数ｘi，yi,j，zkの制約条件を生成する。制約条件生成部１４は、文長計算手段１４０と、制約条件生成手段１４１と、を備える。
【００５５】
文長計算手段１４０は、各文の長さliを計数する（ステップＳ１４０）。文の長さliは、単語の数でも文字数でも良い。制約条件生成手段１４１は、変数di,kと文の長さliと文の数nを入力として、以降に示す制約条件を生成する（ステップＳ１４１）。
【００５６】
【数６】
【００５７】
式（６）は、要約文章の長さに関する制約である。要約文章の最大の長さをKとしたとき、上記した図９の場合、ｌ1+l3+l5+l7の長さがK以内でなければならない。
【００５８】
式（７）は、要約文章に情報ekを含むためには、すなわちzkが１となるには、情報ekを含む文が一つ以上要約に含まれる必要があることを示す制約である。式（８）は、決定変数x,y,zは０又は１の値を取るという制約である。この制約により、文が要約文章に0.5個選ばれるといった要約として適当で無い解を除去することが出来る。
【００５９】
また、文と文を接続する有向辺に関して下記の制約を設定する。
【００６０】
【数７】
【００６１】
式（９）と式（１０）は、要約文章の始点と終点を表すx0とxn+1は必ず要約文章に含まれることを意味する制約である。式（１１）と式（１２）は、始点からは必ず一つの有向辺が出ること及び始点に入って来る有向辺は無いことを示す制約である。
【００６２】
式（１３）と式（１４）は、終点から出る有向辺は無いこと及び終点に入って来る有向辺が必ず一つあることを示す制約である。式（１５）は、要約文章に含まれる文は必ず二つの有向辺を持つことを意味する制約である。式（１６）は、要約文章に含まれる文は必ず入って来る有向辺と出て行く有向辺をそれぞれ持つことを意味する制約である。
【００６３】
式（９）〜式（１６）に示す制約だけでは、閉路の発生を防ぐことが出来ない。図１２に閉路の例を示す。s5とs7に閉路が構成されており適当な要約文章では無い。このような閉路の発生を防ぐためには、次の制約を加える必要がある。
【００６４】
【数８】
【００６５】
式（１７）は、始点からｎ単位のフローが流される制約を示す。式（１８）は、終点に必ず１単位以上のフローが到着する制約を示す。式（１９）は、要約文章に含まれる文は必ず１単位のフローを消費する制約を示す。式（２０）は、要約文章に含まれる有向辺は必ず１単位以上のフローを流す制約を示す。
【００６６】
式（１７）〜式（２０）の制約は、始点からｎ単位の「フロー」ｆが流され、有向辺に従って終点に向かって流れて行き、有向辺を接続する文でそのフローが１単位ずつ消費されて行くことを示している。この制約によって閉路の発生を防止することが出来る。
【００６７】
〔目的関数最大化部〕
目的関数最大化部３０は、上記した目的関数と制約条件の集合を入力として、与えられた制約条件を満たす解の内で目的関数を最大にする決定変数ｘi，yi,j，zｋ，fi,jを探索する（式２１））。探索には、周知の分枝限定アルゴリズム（非特許文献４）を用いることが出来る。
【００６８】
【数９】
【００６９】
〔テキスト出力部〕
テキスト出力部４０は、目的関数を最大にする決定変数yi,j又はfi,jを入力とし、文を連結した要約文章として出力する。その動作を上記した図９の例で説明する。要約文章に含まれる文同士を結ぶ有向辺を表す決定変数yi,jは、y0,1=1,y1,3=1,y3,7=1,y7,5=1,y5,10=1であり、他の、y0,2等は０である。また、有向辺ai,j上を流れるフローの量を表す決定変数fi,jは、f0,1=9，f1,3=8，f3,7=7，f7,5=6，f5,10=5である。これらの決定変数から、テキスト出力部４０は、s1とs3とs7とｓ5の順番に文を並べた要約文章を出力する。
【００７０】
なお、文連接モデルパラメータ記録部１０に記録される素性パラメータは任意の二つの文の繋がりの良さを計算するパラメータとし、連接性スコア関数生成部１１も二つの文の繋がりの良さを累積する方法を説明したが、この発明はこの方法に限定されない。例えば三つ以上の文の間の繋がりの良さを評価して連接性スコアを求めるようにしても良い。また、制約条件生成部１４が生成する制約条件も上記した例以外のものも考えられる。
【００７１】
また、文長計算手段１４０を制約条件生成部１４に含める例で説明したが、文長計算手段１４０を、前処理部１５０に含めても良い。また、上記方法及び装置において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００７２】
また、上記装置における処理手段をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各装置における処理手段がコンピュータ上で実現される。
【００７３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）/ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００７４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記録装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７５】
また、各手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【特許請求の範囲】
【請求項１】
入力されるテキストを要約するテキスト要約装置であって、
任意の二つの文の繋がりの良さを計算するための素性パラメータを記録する文連接モデルパラメータ記録部と、
要約文章の対象となる複数のテキストを入力とし、上記素性パラメータを参照して上記テキストを構成する文の集合から情報の重要度を表わす内容性スコアと文の繋がりの良さを表す連接性スコアとの和が最大となる文の順列を求める目的関数と制約条件を、整数計画問題として設定する整数計画部と、
上記制約条件に基づいて上記目的関数を最大化する一つ以上の上記文及びそれらの順列を表す決定変数を求める目的関数最大化部と、
上記決定変数に基づいて上記文を連結して要約文章を出力するテキスト出力部と、
を具備するテキスト要約装置。
【請求項２】
請求項１に記載したテキスト要約装置において、
上記目的関数は、上記要約文章に含まれる情報とその重みとの積を累積した内容性スコアと、
素性パラメータを要素とする重みベクトルと素性ベクトルの内積を累積した連接性スコアの重み付き線形和であることを特徴とするテキスト要約装置。
【請求項３】
請求項１又は２に記載したテキスト要約装置において、
上記整数計画部は、
上記文に含まれる情報の重みを重要度として算出する情報重み算出手段と、
上記重要度と上記文に含まれる情報を表す変数との積の累積を計算する内容性スコア関数を生成する内容性スコア関数生成手段と、から成る内容性スコア関数生成部と、
上記任意の二つの文を構成する単語に分解し、その二つの文の単語の積を直積集合として生成する直積集合生成手段と、
上記直積集合の要素と対応する要素が上記文連接モデルパラメータ記録部に含まれる場合は１、そうで無い場合は０とする素性ベクトルに変換する素性ベクトル変換手段と、
上記素性ベクトルと上記素性パラメータの内積を計算する内積計算手段と、
二つの文の繋がりの良さを表す値として計算する連接性スコア関数を生成する連接性スコア関数生成手段と、から成る連接性スコア関数生成部と、
上記文と情報の包含関係に応じて当該文の情報の有無を表す有無情報を検出する情報包含検出手段と、
上記文の数を計数する文数計数手段と、から成る前処理部と、
上記有無情報と上記文の数と上記複数の文を入力として、上記文の長さを計算する文長計算手段と、
上記制約条件を生成する制約条件生成手段と、から成る制約条件生成部と、
を備えることを特徴とするテキスト要約装置。
【請求項４】
請求項３に記載したテキスト要約装置において、
上記情報重み算出手段は、上記文に含まれる単語を情報の単位としその頻度を計数して当該単語の重要度とするものであることを特徴とするテキスト要約装置。
【請求項５】
請求項１乃至４の何れかに記載したテキスト要約装置において、
上記制約条件に、要約文章の始点からn単位のフローが流され、有向辺に従って上記要約文章の終点に向かって流れて行き、有向辺を接続する文で上記フローの数が１単位ずつ消費されて行く制約を含むことを特徴とするテキスト要約装置。
【請求項６】
入力されるテキストを要約するテキスト要約方法であって、
要約文章の対象となる複数のテキストを入力とし、文連接モデルパラメータ記録部に記録された任意の二つの文の繋がりの良さを計算するための素性パラメータを参照して上記テキストを構成する文の集合から情報の重要度を表わす内容性スコアと文の繋がりの良さを表す連接性スコアとの和が、最大となる文の順列を求める目的関数と制約条件を整数計画問題として設定する整数計画過程と、
上記制約条件に基づいて上記目的関数を最大化する一つ以上の上記文及びそれらの順列を表す決定変数を求める目的関数最大化過程と、
上記決定変数に基づいて上記文を連結して要約文章を出力するテキスト出力過程と、
を備えるテキスト要約方法。
【請求項７】
請求項６に記載したテキスト要約方法において、
上記目的関数は、上記要約文章に含まれる情報とその重みとの積を累積した内容性スコアと、
素性パラメータを要素とする重みベクトルと素性ベクトルの内積を累積した連接性スコアの重み付き線形和であることを特徴とするテキスト要約方法。
【請求項８】
請求項６又は７に記載したテキスト要約方法において、
上記整数計画過程は、
上記文に含まれる情報の重みを重要度として算出する情報重み算出ステップと、
上記重要度と上記文に含まれる情報を表す変数との積の累積を計算する内容性スコア関数を生成する内容性スコア関数生成ステップと、から成る内容性スコア関数生成過程と、
上記任意の二つの文を構成する単語に分解し、その二つの文の単語の積を直積集合として生成する直積集合生成ステップと、
上記直積集合の要素と対応する要素が上記文連接モデルパラメータ記録部に含まれる場合は１、そうで無い場合は０とする素性ベクトルに変換する素性ベクトル変換ステップと、
上記素性ベクトルと上記素性パラメータの内積を計算する内積計算ステップと、
二つの文の繋がりの良さを表す値として計算する連接性スコア関数を生成する連接性スコア関数生成ステップと、から成る連接性スコア関数生成過程と、
上記文と情報の包含関係に応じて当該文の情報の有無を表す有無情報を検出する包含情報検出ステップと、
上記文の数を計数する文数計数ステップと、から成る前処理ステップと、
上記有無情報と上記文の数と上記複数の文を入力として、上記文の長さを計算する文長計算ステップと、
上記制約条件を生成する制約条件生成ステップと、から成る制約条件生成過程と、
を含むことを特徴とするテキスト要約方法。
【請求項９】
請求項８に記載したテキスト要約方法において、
上記情報重み算出ステップは、上記文に含まれる単語を情報の単位としその頻度を計数して当該単語の重要度とするステップであることを特徴とするテキスト要約方法。
【請求項１０】
請求項１乃至５の何れかに記載したテキスト要約装置としてコンピュータを機能させるためのプログラム。
【請求項１】
入力されるテキストを要約するテキスト要約装置であって、
任意の二つの文の繋がりの良さを計算するための素性パラメータを記録する文連接モデルパラメータ記録部と、
要約文章の対象となる複数のテキストを入力とし、上記素性パラメータを参照して上記テキストを構成する文の集合から情報の重要度を表わす内容性スコアと文の繋がりの良さを表す連接性スコアとの和が最大となる文の順列を求める目的関数と制約条件を、整数計画問題として設定する整数計画部と、
上記制約条件に基づいて上記目的関数を最大化する一つ以上の上記文及びそれらの順列を表す決定変数を求める目的関数最大化部と、
上記決定変数に基づいて上記文を連結して要約文章を出力するテキスト出力部と、
を具備するテキスト要約装置。
【請求項２】
請求項１に記載したテキスト要約装置において、
上記目的関数は、上記要約文章に含まれる情報とその重みとの積を累積した内容性スコアと、
素性パラメータを要素とする重みベクトルと素性ベクトルの内積を累積した連接性スコアの重み付き線形和であることを特徴とするテキスト要約装置。
【請求項３】
請求項１又は２に記載したテキスト要約装置において、
上記整数計画部は、
上記文に含まれる情報の重みを重要度として算出する情報重み算出手段と、
上記重要度と上記文に含まれる情報を表す変数との積の累積を計算する内容性スコア関数を生成する内容性スコア関数生成手段と、から成る内容性スコア関数生成部と、
上記任意の二つの文を構成する単語に分解し、その二つの文の単語の積を直積集合として生成する直積集合生成手段と、
上記直積集合の要素と対応する要素が上記文連接モデルパラメータ記録部に含まれる場合は１、そうで無い場合は０とする素性ベクトルに変換する素性ベクトル変換手段と、
上記素性ベクトルと上記素性パラメータの内積を計算する内積計算手段と、
二つの文の繋がりの良さを表す値として計算する連接性スコア関数を生成する連接性スコア関数生成手段と、から成る連接性スコア関数生成部と、
上記文と情報の包含関係に応じて当該文の情報の有無を表す有無情報を検出する情報包含検出手段と、
上記文の数を計数する文数計数手段と、から成る前処理部と、
上記有無情報と上記文の数と上記複数の文を入力として、上記文の長さを計算する文長計算手段と、
上記制約条件を生成する制約条件生成手段と、から成る制約条件生成部と、
を備えることを特徴とするテキスト要約装置。
【請求項４】
請求項３に記載したテキスト要約装置において、
上記情報重み算出手段は、上記文に含まれる単語を情報の単位としその頻度を計数して当該単語の重要度とするものであることを特徴とするテキスト要約装置。
【請求項５】
請求項１乃至４の何れかに記載したテキスト要約装置において、
上記制約条件に、要約文章の始点からn単位のフローが流され、有向辺に従って上記要約文章の終点に向かって流れて行き、有向辺を接続する文で上記フローの数が１単位ずつ消費されて行く制約を含むことを特徴とするテキスト要約装置。
【請求項６】
入力されるテキストを要約するテキスト要約方法であって、
要約文章の対象となる複数のテキストを入力とし、文連接モデルパラメータ記録部に記録された任意の二つの文の繋がりの良さを計算するための素性パラメータを参照して上記テキストを構成する文の集合から情報の重要度を表わす内容性スコアと文の繋がりの良さを表す連接性スコアとの和が、最大となる文の順列を求める目的関数と制約条件を整数計画問題として設定する整数計画過程と、
上記制約条件に基づいて上記目的関数を最大化する一つ以上の上記文及びそれらの順列を表す決定変数を求める目的関数最大化過程と、
上記決定変数に基づいて上記文を連結して要約文章を出力するテキスト出力過程と、
を備えるテキスト要約方法。
【請求項７】
請求項６に記載したテキスト要約方法において、
上記目的関数は、上記要約文章に含まれる情報とその重みとの積を累積した内容性スコアと、
素性パラメータを要素とする重みベクトルと素性ベクトルの内積を累積した連接性スコアの重み付き線形和であることを特徴とするテキスト要約方法。
【請求項８】
請求項６又は７に記載したテキスト要約方法において、
上記整数計画過程は、
上記文に含まれる情報の重みを重要度として算出する情報重み算出ステップと、
上記重要度と上記文に含まれる情報を表す変数との積の累積を計算する内容性スコア関数を生成する内容性スコア関数生成ステップと、から成る内容性スコア関数生成過程と、
上記任意の二つの文を構成する単語に分解し、その二つの文の単語の積を直積集合として生成する直積集合生成ステップと、
上記直積集合の要素と対応する要素が上記文連接モデルパラメータ記録部に含まれる場合は１、そうで無い場合は０とする素性ベクトルに変換する素性ベクトル変換ステップと、
上記素性ベクトルと上記素性パラメータの内積を計算する内積計算ステップと、
二つの文の繋がりの良さを表す値として計算する連接性スコア関数を生成する連接性スコア関数生成ステップと、から成る連接性スコア関数生成過程と、
上記文と情報の包含関係に応じて当該文の情報の有無を表す有無情報を検出する包含情報検出ステップと、
上記文の数を計数する文数計数ステップと、から成る前処理ステップと、
上記有無情報と上記文の数と上記複数の文を入力として、上記文の長さを計算する文長計算ステップと、
上記制約条件を生成する制約条件生成ステップと、から成る制約条件生成過程と、
を含むことを特徴とするテキスト要約方法。
【請求項９】
請求項８に記載したテキスト要約方法において、
上記情報重み算出ステップは、上記文に含まれる単語を情報の単位としその頻度を計数して当該単語の重要度とするステップであることを特徴とするテキスト要約方法。
【請求項１０】
請求項１乃至５の何れかに記載したテキスト要約装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−４３１００（Ｐ２０１２−４３１００Ａ）
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願番号】特願２０１０−１８２４４０（Ｐ２０１０−１８２４４０）
【出願日】平成２２年８月１７日（２０１０．８．１７）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ・発行者名 言語処理学会 ・刊行物名 言語処理学会第１６回年次大会発表論文集 ・発行年月日 ２０１０年３月８日
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願日】平成２２年８月１７日（２０１０．８．１７）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ・発行者名 言語処理学会 ・刊行物名 言語処理学会第１６回年次大会発表論文集 ・発行年月日 ２０１０年３月８日
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]