現在の自動要約の多くは文を単位にした処理を行っている\cite{okumura05}．具体的には，まず入力された文書集合を文分割器を用いて文集合に変換する．次に，文集合から，要約長を満たす文の組み合わせを，要約としての善し悪しを与える何らかの基準に基づいて選び出す．最後に，選び出された文に適当な順序を与えることによって要約は生成される．近年では，複数文書の自動要約は最大被覆問題の形で定式化されることが多い\cite{filatova04,yih07,takamura08,gillick09,higashinaka10b,nishikawa13}．これは，入力文書集合に含まれる単語のユニグラムやバイグラムといった単位を，与えられた要約長を満たす文の集合によってできる限り被覆することによって要約を生成するものである．最大被覆問題に基づく要約モデル\footnote{本論文では，自動要約のために設計された，何らかの目的関数と一連の制約によって記述される数理計画問題を特に要約モデルと呼ぶことにする．これは自動要約のための新しい要約モデル（数理計画問題）の開発と，何らかの要約モデルに対する新しい最適化手法の提案を陽に切り離して議論するためである．また，特定の要約モデルとその要約モデルに対する具体的な一つの最適化手法を合わせたものを要約手法と呼ぶことにする．}（以降，最大被覆モデルと呼ぶ）は，複数文書要約において問題となる要約の冗長性をうまく取り扱うことができるため，複数文書要約モデルとして高い能力を持つことが実証されている\cite{takamura08,gillick09}．しかし，その計算複雑性はNP困難である\cite{khuller99}ため，入力文書集合が大規模になった場合，最適解を求める際に多大な時間を要する恐れがある．本論文で後に詳述する実験では，30種類の入力文書集合を要約するために1週間以上の時間を要した．平均すると，1つの入力文書集合を要約するために8時間以上を要しており，これではとても実用的とは言えない．一方，ナップサック問題として自動要約を定式化した場合，動的計画法を用いることで擬多項式時間で最適解を得ることができる\cite{korte08,hirao09b}．ナップサック問題に基づく要約モデル（以降，ナップサックモデルと呼ぶ）では，個別の文に重要度を与え，与えられた要約長内で文の重要度の和を最大化する問題として自動要約は表現される．この問題は個別の文にスコアを与え，文のスコアの和を最大化する形式であるため，要約に含まれる冗長性が考慮されない．そのため，最大被覆モデルとは異なり冗長な要約を生成する恐れがある．最大被覆モデルとナップサックモデルを比較すると，前者は複数文書要約モデルとして高い性能を持つものの求解に時間を要する．一方，後者は複数文書要約モデルとしての性能は芳しくないものの高速に求解できる．本論文では，このトレードオフを解決する要約モデルを提案する．本論文の提案する要約モデルは，動的計画法によって擬多項式時間で最適解を得られるナップサック問題の性質を活かしつつ，要約の冗長性を制限する制約を陽に加えたものである．以降，本論文ではこの複数文書要約モデルを冗長性制約付きナップサックモデルと呼ぶことにする．冗長性を制限する制約をナップサックモデルに加えることで冗長性の少ない要約を得ることができるが，再び最適解の求解は困難となるため，本論文では，ラグランジュヒューリスティック\cite{haddadi97,umetani07}を用いて冗長性制約付きナップサックモデルの近似解を得る方法を提案する．ラグランジュヒューリスティックはラグランジュ緩和によって得られる緩和解から何らかのヒューリスティックを用いて実行可能解を得るもので，集合被覆問題において良好な近似解が得られることが知られている\cite{umetani07}．本論文の貢献は，新しい要約モデル（冗長性制約付きナップサックモデル）の開発，および当該モデルに対する最適化手法の提案（ラグランジュヒューリスティックによるデコーディング）の両者にある．冗長性制約付きナップサックモデルの，最大被覆モデルおよびナップサックモデルに対する優位性を表\ref{tb:comp}に示す．提案する要約モデルを提案する最適化手法でデコードすることで，最大被覆モデルの要約品質を，ナップサックモデルの要約速度に近い速度で得ることができる．\begin{table}[t]\caption{冗長性制約付きナップサックモデルの優位性}\label{tb:comp}\input{03table01.txt}\end{table}以下，2節では関連研究について述べる．3節では提案する要約モデルについて述べる．4節では，デコーディングのためのアルゴリズムについて述べる．5節では提案手法の性能を実験によって検証する．6節では本論文についてまとめる．