# 冗長性制約付きナップサック問題に基づく複数文書要約モデル

本論文では，複数文書要約を壳長性制約付きナップサック問題として捉える。この 問題に基づく要約モデルは, ナップサック問題に基づく要約モデルに対し, 壳長性 を削減するための制約を加えることで得られる。この問題は NP 困難であり, 計算量が大きいことから, 高速に求解するための近似解法として, ラグランジュヒュー リスティックに基づくデコーディングアルゴリズムを提案する． ROUGE に基づく 評価によれば, 我々の提案する要約モデルは, モデルの最適解において, 最大被覆問題に基づく要約モデルを上回る性能を持つ。要約の速度に関しても評価を行い,我々の提案するデコーディングアルゴリズムは最大被覆問題に基づく要約モデルの 最適解と同水準の近似解を, 整数計画ソルバーと比べ 100 倍以上高速に発見できる ことがわかった。

キーワード : 自動要約, 複数文書要約, ナップサック問題, 最大被覆問題, ラグランジュ緩和
## Multi-Document Summarization Model Based on Redundancy-Constrained Knapsack Problem

\author{
Hitoshi Nishikawa ${ }^{\dagger, \dagger}$, Tsutomu Hirao ${ }^{\dagger \dagger}$, Toshiro Makino ${ }^{\dagger}$, \\ Yoshihiro Matsuo $^{\dagger}$ and Yuji Matsumoto ${ }^{\dagger \dagger}$
}

In this study, we regard multi-document summarization as a redundancy-constrained knapsack problem. The summarization model based on this formulation is obtained by adding a constraint that curbs redundancy in the summary to a summarization model based on the Knapsack problem. As the redundancy-constrained knapsack problem is an NP-hard problem and its computational cost is high, we propose a fast decoding method based on the Lagrange heuristic to quickly locate an approximate solution. Experiments based on ROUGE evaluation show that our proposed model outperforms the state-of-the-art text summarization model, the maximum coverage model, in finding the optimal solution. We also show that our decoding method finds a good approximate solution, which is comparable to the optimal solution of the maximum coverage model, more than 100 times faster than an integer linear programming solver.

Key Words: Automatic Summarization, Multi-Document Summarization, Knapsack Problem, Maximum Coverage Problem, Lagrange Relaxation


## 1 はじめに

現在の自動要約の多くは文を単位にした処理を行っている (奥村，難波 2005). 具体的には， まず入力された文書集合を文分割器を用いて文集合に変換する。次に，文集合から，要約長を満たす文の組み合わせを, 要約としての善し悪しを与える何らかの基準に基づいて選び出す.最後に，選び出された文に適当な順序を与えることによって要約は生成される.

近年では, 複数文書の自動要約は最大被覆問題の形で定式化されることが多い (Filatova and Hatzivassiloglou 2004; Yih, Goodman, Vanderwende, and Suzuki 2007; 高村, 奥村 2008; Gillick and Favre 2009; Higashinaka, Minami, Nishikawa, Dohsaka, Meguro, Kobashikawa, Masataki, Yoshioka, Takahashi, and Kikui 2010; 西川, 長谷川, 松尾, 菊井 2013). これは, 入力文書集合に含まれる単語のユニグラムやバイグラムといった単位を，与えられた要約長を満たす文の集合によってできる限り被覆することによって要約を生成するものである. 最大被覆問題に基づ 〈要約モデル ${ }^{1}$ (以降, 最大被覆モデルと呼ぶ）は, 複数文書要約において問題となる要約の冗長性をうまく取り扱うことができるため，複数文書要約モデルとして高い能力を持つことが実証されている (高村，奥村 2008; Gillick and Favre 2009)。しかし，その計算複雑性は NP 困難である (Khuller, Moss, and Naor 1999) ため, 入力文書集合が大規模になった場合, 最適解を求める際に多大な時間を要する恐れがある。本論文で後に詳述する実験では, 30 種類の入力文書集合を要約するために 1 週間以上の時間を要した。平均すると，1つの入力文書集合を要約するために 8 時間以上を要しており，これではとても実用的とは言えない.

一方，ナップサック問題として自動要約を定式化した場合，動的計画法を用いることで擬多項式時間で最適解を得ることができる (Korte and Vygen 2008; 平尾, 鈴木, 磯崎 2009b). ナップサック問題に基づく要約モデル（以降, ナップサックモデルと呼ぶ）では，個別の文に重要度を与え, 与えられた要約長内で文の重要度の和を最大化する問題として自動要約は表現される.この問題は個別の文にスコアを与え, 文のスコアの和を最大化する形式であるため, 要約に含まれる壳長性が考慮されない。そのため, 最大被覆モデルとは異なり冗長な要約を生成する恐れがある。

最大被覆モデルとナップサックモデルを比較すると, 前者は複数文書要約モデルとして高い性能を持つものの求解に時間を要する。一方, 後者は複数文書要約モデルとしての性能は芳しくないものの高速に求解できる.

本論文では，このトレードオフを解決する要約モデルを提案する。本論文の提案する要約モデルは，動的計画法によって擬多項式時間で最適解を得られるナップサック問題の性質を活か

表 1 冗長性制約付きナップサックモデルの優位性

しつつ，要約の朵長性を制限する制約を陽に加えたものである，以降，本論文ではこの複数文書要約モデルを壳長性制約付きナップサックモデルと呼ぶことにする.

冗長性を制限する制約をナップサックモデルに加えることで冗長性の少ない要約を得ることができるが, 再び最適解の求解は困難となるため, 本論文では, ラグランジュヒューリスティック (Haddadi 1997; Umetani and Yagiura 2007) を用いて壳長性制約付きナップサックモデルの近似解を得る方法を提案する。 ラグランジュヒューリスティックはラグランジュ緩和によって得られる緩和解から何らかのヒユーリスティックを用いて実行可能解を得るもので, 集合被覆問題において良好な近似解が得られることが知られている (Umetani and Yagiura 2007).

本論文の貢献は, 新しい要約モデル（㔯長性制約付きナップサックモデル）の開発, および当該モデルに対する最適化手法の提案（ラグランジュヒューリスティックによるデコーディング）の両者にある. 艺長性制約付きナップサックモデルの, 最大被覆モデルおよびナップサックモデルに対する優位性を表 1 に示す。提案する要約モデルを提案する最適化手法でデコードすることで, 最大被覆モデルの要約品質を, ナップサックモデルの要約速度に近い速度で得ることができる.

以下， 2 節では関連研究について述べる。 3 節では提案する要約モデルについて述べる. 4 節では，デコーディングのためのアルゴリズムについて述べる。 5 節では提案手法の性能を実験によって検証する。 6 節では本論文についてまとめる.

## 2 関連研究

複数文書要約においては，要約の冗長性に対する対処が重要な課題の 1 つである (奥村，難波 2005). 複数の文書から 1 つの要約を生成する際に, 複数の文書が類似する情報を含んでいるときには，類似する情報がいずれも要約に含まれる恐れがある．複数文書要約の目的を鑑みると，類似する情報が要約に 2 度含まれることは好ましくないため, この問題に対処する必要がある.

この冗長性に対する対処として, Filatova らによって最大被覆問題による要約モデルが提案された (Filatova and Hatzivassiloglou 2004)。最大被覆問題による要約モデルは文の集合と要約長を入力とする．集合中の文はそれぞれ何らかの概念を含んでおり，この概念はその性質に応じて重要度を持っている。概念はユニグラムやバイグラムなど, 文から抽出できる何らかの単
位である。また，文はそれぞれその単語数や文字数に応じて，長さを持っている．最大被覆問題の最適解は，合計の長さが要約長を超えない文の集合のうち，集合中の文が持っている概念の重要度の和が最大となるものである。ただし，文の集合に含まれる概念の重要度の和を計算するときには，同じ概念は一度しか数えない，例えば，文の集合にある概念が 3 つ含まれていたとしても，最大被覆問題においては，文の集合に含まれる概念の重要度の和は，その概念が 1 つしか含まれないときと同じである.

複数文書の要約を最大被覆問題として考えた場合, 同じ概念は一度しか数えないという性質が重要な役割を果たす。すなわち, 文が含む概念を情報とすると, 同じ情報を 3 つ含んだ要約も同じ情報を 1 つ含んだ要約も解としての良さは同じであり，よりよい解はより多様な情報を含んだ解である.

このような, 多様な情報を含んだ解がより良好な解であるという最大被覆問題の性質は, 複数文書要約に必要なモデルの性質として適切であり，これまで最大被覆問題に基づいた要約モデルがいくつも提案されてきた. Filatova らは単語を概念として, 重要度を tf-idfで与え, これを貪欲法 (Khuller et al. 1999) で解いた. Yih らはスタックデコーダ (Jelinek 1969) を用いてこれを解いた (Yih et al. 2007). 高村らはこれに整数計画問題としての厳密な定式を与え, 近似解法と分枝限定法による結果を報告した (高村, 奥村 2008). Gillick らも同様に整数計画問題としての定式を与え結果を報告した (Gillick and Favre 2009). これらは全て新聞記事を要約の対象としているが，他の領域を対象にした複数文書要約も行われている。東中らはコンタクトセンタログを要約の対象として, 発話を文, 発話に含まれる単語を概念とする要約モデルを提案した (Higashinaka et al. 2010). 西川らはレビュー文書集合を要約の対象として, 商品やサービスに対して評価を行っている記述を概念の単位とする複数文書要約モデルを提案した (西川他 2013).

最大被覆問題は NP 困難である (Khuller et al. 1999) ため, 解の探索が重要な課題である。貪欲法のような単純な探索法を用いた場合，良好な解を得られる可能性は必ずしも高くないものの, 高速に解を得られる. Khuller らによって提案された貪欲法による最大被覆問題の解は, 最悪でも最適解の目的関数値の $(1-1 / e) / 2$ を達成する (Khuller et al. 1999). 高村らはこれを複数文書要約に応用して結果を報告している (高村, 奥村 2008). スタックデコーダのようなより複雑な探索法を用いることによってより良好な解を得られる可能性が高まるが, 探索に要する時間も増加する。分枝限定法を用いることで最適解を得ることができるものの, 問題の規模が増加するにつれて探索に要する時間は著しく増加する.

単一文書要約に目を向けると, 単一文書要約は冗長性が問題となる恐れが少ないため, 兮長性を加味しない手法を利用することができる，単一文書要約は，ナップサック問題として定式化できる (McDonald 2007; 平尾他 2009b). ナップサック問題による要約モデルも文の集合と要約長を入力とする。最大被覆問題と異なり，ナップサック問題はそれぞれの文が直接重要度

を持っている.ナップサック問題の最適解は, 合計の長さが要約長を超えない文の集合のうち,集合を構成する文の重要度の和が最大となるものである.ナップサック問題の最適解は動的計画法の一種である動的計画ナップサックアルゴリズムによって擬多項式時間で求めることができる (Korte and Vygen 2008). そのため, ナップサック問題の最適解は高速に求めることができる。しかし，ナップサック問題は文に対して直接重要度を定義し，その和を最大化するものであるため，壳長性を削減する仕組みを持たない。従って，複数文書要約に適用した場合，䒕長な要約が生成される恐れがある.

先に述べたように，最大被覆問題は複数文書要約に適した性質を持っているものの，良好な解の探索には多大な時間を要する。一方，ナップサック問題は複数文書要約に適さないものの,最適解の探索は容易である。本論文で提案する方法は, このトレードオフを解決するため, ナップサック問題に対して冗長性を削減する制約を加えたものである.

## 3 最大被覆モデルとナップサックモデル

ここでは最大被覆問題に基づいた要約モデル, 最大被覆モデルと, ナップサック問題に基づいた要約モデル, ナップサックモデルを比較する.

## 3.1 最大被覆モデル

$n$ 文の入力および，それらに含まれる $m$ 個の概念を考える。概念は先に述べたよう単語のユニグラムやバイグラムなどであるが，文中から抽出できる他の何らかの情報でもよい． $\mathrm{x}$ を文 $i$ が要約に含まれる際に $x_{i}=1$ となる決定変数を要素とするべクトルとする. $\mathbf{z}$ を概念 $j$ が要約に含まれる際に $z_{j}=1$ となる決定変数を要素とするべクトルとする． $\mathbf{w}$ を概念 $j$ の重要度 $w_{j}$ を要素とするべクトルとする．行列 A の要素 $a_{j, i}$ を文 $i$ に含まれる概念 $j$ の数とする. l を文 $i$ の長さ $l_{i}$ を要素とするべクトルとする． $K$ を要約長とする．このとき，最大被覆問題は以下のように定式化される。

$
\begin{array}{ll}
\max _{\mathbf{z}} & \mathbf{w}^{\top} \mathbf{z} \\
\text { s.t. } & \mathbf{A x} \geq \mathbf{z} \\
& \mathbf{x} \in\{0,1\}^{n} \\
& \mathbf{z} \in\{0,1\}^{m} \\
& \mathbf{l}^{\top} \mathbf{x} \leq K
\end{array}
$
式 (1) が目的関数であり, 式 $(2)^{2}$ から式 (5) が制約である. 式 (4) が示すように $\mathbf{z}$ の要素は 0 あるいは 1 である. もし概念 $z_{j}$ が要約に含まれれば, $z_{j}=1$ となり, その重要度 $w_{j}$ は目的関数に加算される。可能であれば全ての概念を要約に含めたいが，要約長の制限によってはそれは許されない，式 $(2)$ が示すように，概念 $z_{j}$ を要約に含めるためには， $z_{j}$ を含むいずれかの文が要約として選択されていなければならない. 仮に文 $x_{i}$ が要約に含まれた場合, 式 (5)の左辺の値は $l_{i}$ だけ増える。式 (5) によって要約として選択された文の長さの合計は $K$ を超えることが許されない. 式 (3) の示すように $\mathrm{x}$ の要素は 0 あるいは 1 である. このことは 1 つの文は一度しか要約に含めないことを示す。

これらのことから, 最大被覆モデルの最適解は, 要約長を満たす文の組み合わせを全て試し,全ての組み合わせに対して $\mathbf{z}$ を計算し， $\mathbf{w}$ とかけあわせ，かけあわせた値が最大となる文の組み合わせを探し出せば見つけられるとわかる。しかし，一部の組み合わせは要約長を満たさな

することは困難である。

## 3.2 ナップサックモデル

次に，ナップサック問題に目を向けることにする． $\mathbf{x}$ を文 $i$ が要約に含まれる際に $x_{i}=1$ となる決定変数を要素とするべクトルとする。 $\mathbf{z}$ を概念 $j$ が要約に含まれる際に $z_{j}=1$ となる決定変数を要素とするべクトルとする。上述した最大被覆モデルと同様の記法に従ってナップサックモデルを記述すると以下のようになる.

$
\begin{array}{cl}
\max _{\mathbf{z}} & \mathbf{w}^{\top} \mathbf{z} \\
\text { s.t. } & \mathbf{A x}=\mathbf{z} \\
& \mathbf{x} \in\{0,1\}^{n} \\
& \mathbf{z} \in\left(\mathbb{N}^{0}\right)^{m} \\
& \mathbf{l}^{\top} \mathbf{x} \leq K
\end{array}
$

ここで， $\mathbb{N}^{0}$ は， 0 を含む， 0 以上の自然数である. 目的関数である式 (6), 1 つ文は一度しか要約に含めないとする制約である式 (8), 要約の長さに関する制約である式 (10) は最大被覆モデルと変わらないものの, 式 (2) と式 (7), 式 (4) と式 (9) がそれぞれ異なる.

式 (4) ではべクトル z は 0 と 1 を要素とするべクトルであったが, 式 (9) ではべクトル $\mathbf{z}$ は 0 以上の自然数を要素とするべクトルである．最大被覆モデルでは要約に同じ概念が何個含ま
$ と $\mathbf{b}$ に大小関係 $\mathbf{a} \geq \mathbf{b}$ が成り立つのは, ベクトル $\mathbf{a}$ の要素 $a_{i}$ とべクトル $\mathbf{b}$ の要素 $b_{i}$ に $a_{i} \geq b_{i}(\forall i)$ が成り立つときとする.
}

れていようともそれぞれの概念について目的関数において一度しかその重要度を加算しなかった. それに対してナップサックモデルでは要約に同じ概念が複数含まれていた場合その数だけ重要度を目的関数において加算する。この性質のため, ナップサックモデルを用いて複数文書要約を行った場合には冗長な要約ができる可能性が高く，したがって，ナップサックモデルの複数文書要約における性能は芳しいものではない.

式 (7) は，式 (2) と異なり，文が含む概念の数をそのままべクトル $\mathbf{z}$ に反映させる．例えば，文 1 は概念 5 を 2 つ含むとすると， $a_{5,1}=2$ である。文 2 は概念 5 を 1 つ含むとすると， $a_{5,2}=1$ である. 文 1 と文 2 のいずれもが要約に選ばれたとすると（すなわち $x_{1}=1, x_{2}=1$ ）,式 (7) から, $z_{5}=a_{5,1} \times x_{1}+a_{5,2} \times x_{2}=2 \times 1+1 \times 1=3$ となり概念 5 は要約に 3 つ含まれることになる.

## 4 冗長性制約付きナップサックモデル

## 4.1 ナップサックモデルへの冗長性制約の付与

前節で述べたように，最大被覆問題が冗長性に強い理由は式 (4) にあり，ナップサックモデルが冗長性に弱い理由は式 (9) であった。 そこで，式 (9) に工夫を施すことでナップサックモデルの宇長性を抑制することを考える。すなわち，ある単語が要約に含まれる回数を直接制御することで，ナップサックモデルの冗長性を削減する。本論文の主たる貢献はここにある.

$
\begin{array}{ll}
\max _{\mathbf{z}} & \mathbf{w}^{\top} \mathbf{z} \\
\text { s.t. } & \mathbf{A} \mathbf{x}=\mathbf{z} \\
& \mathbf{x} \in\{0,1\}^{n} \\
& \mathbf{z} \in\left.\{z_{j} \mid \mathbb{N}^{0} \cap\left[0, r_{j}\right]\right.\}^{m} \\
& \mathbf{l}^{\top} \mathbf{x} \leq K
\end{array}
$

式 (14) は, ベクトル $\mathrm{z}$ の各要素は 0 以上 $r_{j}$ 以下の自然数であることを示す. すなわち, 各概念が要約に含まれてよい個数を制限するべクトル $\mathbf{r}=\left(r_{1}, r_{2}, \ldots, r_{m}\right)$ を考え，これによって要約の艺長性を削減する。本論文では式 (11) から式 (15) で記述される要約モデルを壳長性制約付きナップサックモデルと呼ぶ.

このモデルは最大被覆モデルと等価ではない，最大被覆モデルは，要約に概念が複数含まれることを許す。ただし，目的関数を計算する上では 1 つの概念の重要度は一度しか加えない。 それに対し，壳長性制約付きナップサックモデルは，ある概念が要約に含まれる数を直接制限

する ${ }^{3}$.

上に述べた例と同じように, 文 1 は概念 5 を 2 つ含み $\left(a_{5,1}=2\right)$, 文 2 は概念 5 を 1 つ含むとする $\left(a_{5,2}=1\right)$. このとき $r_{5}=2$ であったとすると, 文 1 と文 2 を同時に要約に含めることはできない，概念 5 は要約には 2 つしか含めることができないが，文 1 と文 2 いずれも要約に含めてしまうと要約には概念 5 が 3 つ含まれてしまうからである．最大被覆モデルでは，長さの制約に違反しない限り，このような組み合わせも許される。一方，朵長性制約付きナップサックモデルでは式 (14) が示す制約を違反する組み合わせは許されない.

ナップサックモデルに式 (14) が示す冗長性に関する制約（以下，㔯長性制約と呼ぶ）を加えることで冗長性を削減することができるが，動的計画ナップサックアルゴリズムで擬多項式時間で最適解を求めることはできなくなる 4 . 穴長性制約付きナップサックモデルを動的計画法で解くことは可能だが5, 宇長性制約を考慮するためには，探索の過程において，ある時点での要約に含まれる概念の数を記録しておかなけれげならない。ある時点において要約に含まれる概念の数の組み合わせは複数存在するため, これによって探索空間が増大してしまい, 素早い求解ができなくなる.

## 4.2 几長性制約のラグランジュ緩和

この冗長性制約付きナップサックモデルからて長性制約を除去すれば，元のナップサックモデルが得られる。そこで，この壳長性制約をラグランジュ緩和 (Korte and Vygen 2008) する。以下は，式 (14)を緩和し， ベクトル $\mathbf{r}$ による宇長性制約を目的関数に組み込んだものである.

$
\begin{array}{ll}
\max _{\mathbf{z}} & \mathbf{w}^{\top} \mathbf{z}+\boldsymbol{\lambda}(\mathbf{r}-\mathbf{z}) \\
\text { s.t. } & \mathbf{A x}=\mathbf{z} \\
& \mathbf{x} \in\{0,1\}^{n} \\
& \mathbf{z} \in\left(\mathbb{N}^{0}\right)^{m} \\
& \boldsymbol{\lambda} \in\left(\mathbb{R}^{+}\right)^{m} \\
& \mathbf{l}^{\top} \mathbf{x} \leq K
\end{array}
$

$\boldsymbol{\lambda}=\left(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{m}\right)$ は非負のラグランジュ乗数ベクトルである. 式 (16) から式 $(21)$ は, 目的関数である式 (16) の 2 つ目の項 $\boldsymbol{\lambda}(\mathbf{r}-\mathbf{z})$ および式 (20) を除いてナップサックモデルと同じ
$ を通じて排他的な制約が与えられているものとみなすと，㔯長制約付きナップサックモデルは，排他制約付きナップサックモデル（Yamada, Kataoka, and Watanabe 2002) とみなせる。，例えば，上に述べた文 1 と文 2 は概念 5 のためにいずれか一方しか要約に含めることができないという制約は， $x_{1}+x_{2} \leq 1$ と記述することができる。

4 正確には， $n$ に関しては擬多項式時間であるが， $m$ に関しては指数時間となるため, 素早い求解ができない.

5 もちろん, 穴長性制約付きナップサックモデルを整数計画ソルバーで解くことも可能である. 本論文では, 兮長性制約付きナップサックモデルを整数計画ソルバーで解くことでその最適解を求める.
}

である。このラグランジュ緩和問題は, 要約に含まれる概念 $j$ の個数 $z_{j}$ が $r_{j}$ を超えた際に,非負のラグランジュ乗数 $\lambda_{j}$ を通じて目的関数に罰を与える，例えば，あるとき，概念 5 が要約に 3 つ含まれている $\left(z_{5}=3\right)$ が, ベクトル $\mathbf{r}$ によって要約に 2 つまでしか含めてはならないと制限されている $\left(r_{5}=2\right)$ とする。また，ラグランジュ乗数 $\lambda_{5}$ が 1 だったとする. このとき $\lambda_{j}\left(r_{5}-z_{5}\right)=1(2-3)=-1$ となり, 目的関数は低下する. $\boldsymbol{\lambda}$ の調整は, この緩和問題のラグランジュ双対問題 $L(\boldsymbol{\lambda})=\min _{\lambda}\left.\{\max _{\mathbf{z}} \mathbf{w}^{\top} \mathbf{z}+\boldsymbol{\lambda}(\mathbf{r}-\mathbf{z})\right.\}$ を解くことで行う.

このように， $\lambda$ を適切に調整し, 壳長性の原因となりやすい概念の重要度を低下させることで，動的計画ナップサックアルゴリズムによって元のナップサックモデルを解いた際でも複数文書要約として良好な解を得ようとするのが本論文の提案である。具体的なデコーディングの方法については次節で述べる.

## 5 デコーディング

デコーディングで必要になるのは，ラグランジュ乗数ベクトル $\boldsymbol{\lambda}$ の値を適切に設定することである．入の值が適切に設定されていれば，あとはそれを動的計画ナップサックアルゴリズムで解くだけでよい． $\lambda$ は前節で述べたラグランジュ双対問題を解くことで得られる。このラグランジュ双対問題は最小化の中に最大化が入れ子になっており, 最適化が困難であるものの, 劣勾配法 (Korte and Vygen 2008) を用いると良好な近似解が高速に得られることが知られている (Umetani and Yagiura 2007). 劣勾配法は, 初期値として適当な $\boldsymbol{\lambda}$ を設定し， $\boldsymbol{\lambda}$ の値を繰り返し更新していくものである.

このとき, 一度にどの程度 $\lambda_{j}$ の値を動かすか, という点が問題となる. 一度に大きく値を動かせばデコーディングに要する時間が短くなると考えられるものの, 最適解から離れてしまう可能性もある。そこで，本論文ではラグランジュヒューリスティック (Haddadi 1997)を利用する。 ラグランジュヒューリスティックは，ラグランジュ乗数を更新するとき，上界と下界の差を利用してステップサイズを調整する。また，下界を計算する際に，ヒューリスティックを利用する.

上界はある反復におけるラグランジュ緩和問題の解である。壳長性制約が緩和されているため, 穴長性制約付きナップサックモデルの緩和問題の最適解の目的関数値は, 明らかに緩和されていない元問題の最適解の目的関数値より高い. 劣勾配法によってラグランジュ乗数を更新していく過程で，ラグランジュ緩和問題の解は，制約に違反している解，すなわち実行不能解から，徐々に目的関数值を低下させながら実行可能解に近づいてい。

下界はなんらかのヒューリスティックによって得られる実行可能解である。本論文では, Haddadi による方法 (Haddadi 1997) と同様に，貪欲法 (Khuller et al. 1999)を用いて実行可能解を復元する。詳細については次節で述べる。

ラグランジュヒューリスティックによるデコーディングの具体的なアルゴリズムを Algorithm 1 に示す. Algorithm 1 の基本的な手順は以下のようになる.

(1) ラグランジュ乗数ベクトル $\boldsymbol{\lambda}$ を適当な値に初期化する.

（2）以下の手続きを既定回数だけ繰り返す.

(a) 動的計画ナップサックアルゴリズムで式の最適解を得る.

（b）ａで得た最適解が制約を満たしているときはそれを下界とし，(3)へ，そうでなければヒューリスティックを用いて実行可能解を得る.

（c）bで得た実行可能解がこれまでの下界を上回るものであれば，下界を更新する。

(3) 下界を出力して終了する.

$\alpha$ は $\boldsymbol{\lambda}$ のステップサイズを調整するパラメータである. ベクトル $\mathrm{s}=\left(s_{1}, s_{2}, \ldots, s_{n}\right)$ の要素 $s_{i}$ は文 $i$ の重要度をあらわす。各文の重要度は関数 sentence によって計算される。関数 $d p k p$ は動的計画ナップサックアルゴリズムである. 動的計画ナップサックアルゴリズムの詳細は Algorithm 2 に示す. $b_{l}$ と $b_{u}$ はそれぞれ目的関数の下界と上界である. これらは $\boldsymbol{\lambda}$ のステップサイズの調整に利用される。関数 score は要約 $\mathbf{x}$ の重要度を計算する. 関数 count は要約 $\mathrm{x}$ に含まれる概念の数 $\mathbf{z}$ を返す. $\mathbf{x}_{l}$ は下界 $b_{l}$ に対応する解である.

ラグランジュ緩和問題の劣勾配ベクトル $\mathbf{d}=\left(d_{1}, d_{2}, \ldots, d_{m}\right)$ は以下のようになる.

$
d_{j}=r_{j}-z_{j}
$

ラグランジュ緩和された集合被覆問題に対する Umetani らの更新式に基づき (Umetani and Yagiura 2007), ラグランジュ乗数は以下の更新式によって更新する.

$
\lambda_{j}^{\text {new }} \leftarrow \max \left(\lambda_{j}^{\text {old }}+\alpha \frac{b_{u}-b_{l}}{\|\mathbf{d}\|^{2}}\left(z_{j}-r_{j}\right), 0\right)
$

$\alpha$ は更新幅を調整するパラメータである。更新式の基本的な考え方は, 上界 $b_{u}$ と下界 $b_{l}$ の差が大きい際には更新幅を大きくしつつ, 劣勾配べクトルに従ってラグランジュ乗数を更新していくというものである.

## 5.1 貪欲法による実行可能解の復元

ラグランジュヒューリスティックは, 実行不能解から実行可能解を何らかのヒューリスティックを用いて復元するものである。本論文では，以下の手続きで実行可能解を復元する.

(1) 制約に違反している概念を含む文のうち，最も重要度が低いものを要約から除去する。

（2）要約がまだ制約を満たさない場合は (1)へ，要約が制約を満たした場合は，要約に含まれていない文と, 要約長 $K$ と制約を満たした要約の長さの差から, 部分問題を生成し, これを貪欲法で解く。

例えば，要約長が 300 文字であったとする。制約に違反する文を除去し，制約を満たした要約の長さが 200 文字だったとすると， 100 文字分まだ要約に文を含めることができる。そこで， まだ要約に含まれていない文を，100 文字分，貪欲法 (Khuller et al. 1999) を用いて要約に含めることで，実行可能解を求める.

## 5.2 動的計画ナップサックアルゴリズム

ナップサックモデルのデコーディングは動的計画ナップサックアルゴリズムを用いて行う.具体的なアルゴリズムは Algorithm 2 に示す.

動的計画ナップサックアルゴリズムでは， $(n+1) \times(K+1)$ 次元の表 $T$ と $U$ を用意し，これに計算の過程を保存していく。表 $T$ の要素 $T[i][k]$ は，文 1 から文 $i$ までが与えられており，最大要約長が $k$ であったときのナップサックモデルの最適解の目的関数値を格納している。表 $U$ の要素 $U[i][k]$ は， $T[i][k]$ の値を計算する際に，すなわちその時点での最適値を計算する際に文 $i$ を要約に利用している場合は 1 , そうでない場合は 0 を格納している。すなわち， $T[n][K]$ まで計算し終わった時点で，最大要約長が $K$ で文 1 から文 $n$ までが使われた場合にどの文が要約に含まれるか表 $U$ に格納されている。そのため, $U[n][K]$ まで表を埋めたのち, $U[n][K]$ に到達するまでの過程を逆にたどることで，ナップサックモデルの最適解を得ることができる。

## 6 実験

本節では提案した手法の性能を評価した結果について報告する. 本節では, 6.1 で述べる手法を用いて, 6.2 で述べる文書集合を要約し, 生成された要約を 6.3 で述べる評価手法で評価する. 6.1 で述べる手法が必要とするパラメータの設定については 6.4 で述べる。結果とその考察については 6.5 で述べる.

## 6.1 比較手法

以下の手法を比較した。

（1） RCKM 提案手法. 兮長性制約付きナップサックモデルを整数計画ソルバーを用いてデコードしたもの. 艺長性制約付きナップサックモデルの最適解における性能を示す.

ソルバーは lp_solve ${ }^{6}$ を用いた 7 .

（2） RCLM-LH 提案手法. 宇長性制約付きナップサックモデルを本論文で提案するラグランジュヒューリスティックを用いてデコードしたもの．提案するデコーディングアルゴリズムによって得られる近似解の性能を示す.

(3) MCM ベースライン。最大被覆モデルをソルバーを用いてデコードしたもの.

（4） MCM-GR ベースライン。最大被覆モデルを貪欲法を用いてデコードしたもの.

（5） KM年、スライン。ナップサックモデルを動的計画ナップサックアルゴリズムでデコードしたもの.

（6）ＨUMAN 達成しうる性能の上限を調べるため, 複数の参照要約を用いて, 性能の上限を求める. 6.2 節で述べるコーパスのうち, レビューコーパスは 1 つの評価セットに対して 4つの参照要約が付与されているため, 参照要約同士を比較することで性能の上限を示すことが可能である．4つの参照要約があるため，それらの 6 つの組み合わせのうち, 6.3 節で述べる評価尺度 ROUGE の値が最も高いものを性能の上限として採用する 8 . なお， 6.2 節で述べるコーパスのうち， TSC-3 は 1 つの評価セットに対して 1 つの参照要約しか付与されていないため，これを計算できるのはレビューのみである.

RCKM-LH，MCM-GR および KM のデコーダは Perl で実装した．全てのプログラムは Intel Xeon X5560 (Quad Core) $2.8 \mathrm{GHz}$ CPU を 2 つ, $64 \mathrm{G}$ バイトのメモリを搭載した計算機上で動作させた.

## 6.2 コーパス

上の手法を以下の 2 種類のコーパスによって評価した。

(1) TSC-3 TSC-3 コーパス (Hirao, Fukushima, Okumura, Nobata, and Nanba 2004)は自動要約のシェアード・タスク Text Summarization Challenge 39 で用いられたコーパスで,複数文書要約の評価セットを含む。要約の対象となる文書は新聞記事であり, 記事は毎日新聞および読売新聞から収集されている。それぞれの評価セットは企業買収やテロなど特定のトピックに関する新聞記事から構成されている。評価セットは 30 セットからなる. 1 セットは新聞記事 10 記事前後からなり，1つの評価セットに含まれる記事の文字数の和は平均して約 6,564 文字である。評価セット全体では 352 記事 3,587 文が含まれる。それぞれの評価セットに対しては人間の作業者が短い要約と長い要約の 2 種類の参照要約を付与している. Hirao らによれば, 参照要約の付与に際し, 作業者は要約の対象

表 2 評価に用いたコーパスの統計量

平均記事数, 平均文数, 平均文字数は全て 1 つの評価セットあたりの数である.

となる記事を全て読んだのち，当該記事集合にふさわしい要約を作成した (Hirao et al. 2004). 短い要約は平均して約 413 文字であり, 要約率 10 にして約 $6 \%$, 長い要約は平均

価を行った，評価セットごとに参照要約の長さが異なるため，要約を生成する際には参照要約と同じ長さを要約長として与え要約を生成した。すなわち，本コーパスを用いた際には，平均として，約 12 記事からなる約 6,564 文字の記事集合を入力とし，約 413 文字の要約を生成する，要約率約 $6 \%$ の要約タスクとなる。

（2）レビュー新聞記事とは異なるドメインで提案する要約モデルを評価するため, レビュー 記事を用いて評価を行った。インターネット上のレビューサイトから飲食店 30 店舗に関するレビュー記事を収集し，これを 30 セットの複数文書要約の評価セットとした。 1 セットはレビュー記事 15 記事前後からなり，1つの評価セットに含まれる記事の文字数の和は平均して約 2,472 文字である。評価セット全体では 468 記事 2,275 文が含まれる. それぞれの評価セットに対しては 4 人の作業者が参照要約を付与しており, 作業者は要約の対象となる記事を全て読んだのち，当該記事集合にふさわしい要約を作成した．要約長はすべて 200 文字を上限とした。そのため，実験において要約を生成する際には一律 200 文字を要約長として要約を生成した，従って，要約率は平均して $8 \%$ である。本コーパスを用いた際には，平均として，約 16 記事からなる約 2,472 文字の記事集合を入力とし, 200 文字の要約を生成する，要約率約 $8 \%$ の要約タスクとなる.

表 2 にコーパスに関する統計量をまとめておく.

## 6.3 評価尺度

我々の提案する手法を評価するため，以下の 2 つの尺度を用いた。

(1) 要約品質要約の品質の評価には要約の自動評価尺度である ROUGE (Lin 2004) を用い
{8000}$ となる.

11 Hirao らによれば, 参照要約の作成時には作業者に対して, 短い要約については要約率 $5 \%$ 程度の要約を, 長い要約については要約率 $10 \%$ 程度の要約を作成するように指示を与えたとしている (Hirao et al. 2004). 本論文で計測した値とは多少の差があるものの，5\%，10\%という値はあくまで目処として与えたものであると述べられているため, 作業者はこれらの指示より多少長い要約を作成したものと思われる。
}

た. ROUGE の亜種のうち，ROUGE-1 および ROUGE-2 を評価に利用した。なお，平尾らは，参照要約の ROUGE 值を計算する際には，文を構成するすべての単語ではなくて, 内容語 12 のみを用いて計算を行った方が人間による評価と相関が高い結果が得られると報告している (平尾, 奥村, 磯崎 2006). そのため, 本論文でも ROUGE 值を計算する際には内容語のみを用いた。生成された要約を単語に分割し品詞を付与する際には Fuchi らによる形態素解析器 (Fuchi and Takagi 1998) を利用した. ROUGE 値を算出するプログラムは Lin の文献 (Lin 2004) に従い独自に実装した。なお，レビューコーパスについては 1 セットに対して複数の参照要約が付与されているため, 評価の際には,当該セットに付与されているすべての参照要約に対して ROUGE 值を求め, 最も高い ROUGE 值をその要約の ROUGE 値とした。この ROUGE 値の計算方針は Lin の提案によるものである (Lin 2004)。これは，ある入力文書集合に対して妥当な要約は複数存在し得ると考えられることから，参照要約の中で機械による要約にとって最も近いものとの ROUGE 値をもってその要約の評価とするためである ${ }^{13}$.

(2) 要約速度要約の生成までの速度を計測した。いずれのコーパスでも, 30 セットすべてを要約するまでの時間を計測した。

なお，要約品質の検定にはウィルコクソンの符号順位検定 (Wilcoxon 1945) を用いた. 多重比較となるため, 全体の有意水準は 0.05 とした上で， $p$ 値の大きさに従って検定それぞれにおいて有意水準をホルム法 (Holm 1979) で調整した.

## 6.4 パラメータ

本節では要約に際して必要なパラメータの設定について述べる。以下に述べるパラメータのうち，概念重要度は全ての手法が利用する。概念壳長性は RCKM および RCKM-LH が利用する。ステップサイズおよびイテレーションは RCKM-LH のみが利用する.

## 6.4.1 概念重要度

概念 $j$ およびその重要度 $w_{j}$ はコーパスに合わせそれぞれ以下のように設定した。

(1) TSC-3 概念 $j$ は内容語とし, その重み $w_{j}$ は tf-idf (Filatova and Hatzivassiloglou 2004; Clarke and Lapata 2007) に基づき， $w_{j}=t f_{j} \log \left(\frac{N}{d f_{j}}\right)$ とした. ここで， $t f_{j}$ は要約の対象となる入力文書集合中での内容語 $j$ の出現頻度, $d f_{j}$ は新聞記事コーパス中で内容語 $j$ を含む記事の数，N は新聞記事コーパスに含まれる記事の総数である。新聞記事コーパ


付与する際には Fuchi らによる形態素解析器 (Fuchi and Takagi 1998) を利用した.

（2）レビュー レビューを要約の対象としたため，概念 $j$ として評価情報を利用した。評価情報の定義とその抽出方法は西川らによるもの (西川他 2013) に従った ${ }^{15}$. 概念 $j$ の重み $w_{j}$ は当該評価情報の入力文書集合中での出現頻度を利用した。評価情報を文中から抽出する際，形態素解析には Fuchi らによる形態素解析器 (Fuchi and Takagi 1998) を，係り受け解析には Imamura らによる係り受け解析器 (Imamura, Kikui, and Yasuda 2007) を，評洒表現辞書は浅野らによる評価表現辞書 (浅野，平野，小林，松尾 2008)をそれぞれ利用した。

なお，本論文では内容語を概念としてレビューを対象に要約を実施する実験は行わない，西川らは，内容語を概念としてレビューを対象に要約を実施した場合，評価情報を用いた場合と比べ良好な結果を得ることができなかったと報告している (西川他 2013). 彼らはこの結果について, レビューの要約においては焦点となる情報が評価情報であるため, それを被覆の対象としなければ良好な結果が得られないと結論づけており, これは妥当な解釈であると考えられる。

同様に，評価情報を概念として新聞記事を対象に要約を実施する実験も行わない.これは，予備実験として，新聞記事に付録記載の評価情報抽出を行ったところ，ほとんど評価情報が抽出されず，従って評価情報を概念として新聞記事を対象に要約を行っても意味のある結果は期待できないと考えられるためである。新聞記事においては「〜はよかった」「〜は悪かった」というような何らかの評価に関する記述があまり存在しない。そのため評価情報は新聞記事を対象として要約を実施する際に有効な概念であるとは言えない.

## 6.4.2 概念冗長性

冗長性パラメータ $r_{j}$ は以下の 4 種類を設定した。

（1） ON 概念冗長性を 1 とする。これは，同じ概念が 2 回以上要約に出現することを禁じる. すなわち $r_{j}=1$ である. この制約を用いた場合, 同一の概念は一度しか要約中に出現することができず，そのため最大被覆問題と同様に冗㔯長性が削減されることが期待される。最大被覆問題とこの制約を用いた艺長性制約付きナップサックモデルの差異は,前者は目的関数を利用して冗長性を削減するのに対し, 後者は制約を用いて冗長性を削減することにある.

（2） KL 概念 $j$ の入力文書集合中の出現頻度に, 要約長 $K$ と入力文書集合のサイズ $L=\sum_{i=1}^{n} l_{i}$ の比をかけたものとする。ただし，值が小数となることが多いため，その場合は值を切り上げることとした. すなわち $r_{j}=\left.\lceil t f_{j} \frac{K}{L}\right.\rceil$ である. この制約を用いた場合, 入力文書集合中での概念の出現頻度の分布が, 要約長を加味した上で要約にも同程

度再現されることが期待される。

（3） SR 概念冗長性を, 各単語の入力文書集合中での出現回数の平方根とする. KL と同様, 值が小数となることが多いが，その場合は値を切り下げることとした. これは $\mathbf{K L}$ では $r_{j}$ の值が 1 未満になることがあるのに対し, 平方根を取る場合はその恐れがないためである. すなわち $r_{j}=\left.\lfloor\sqrt{t f_{j}}\right.\rfloor$ である.この制約は $\mathbf{K L}$ と異なり要約長の影響を受けない。また，KL に比べ冗長性に寛容である。

（4） RF 概念冗長性を，参照要約に含まれる概念の数とした. これは，概念冗長性が理想的に設定された場合の性能を示している。なお，レビューコーパスについては複数の参照要約が存在するため, 同一の概念については複数の参照要約の平均を取り, 小数となった場合は値を切り上げることとした.

これらは 2 つのコーパスで共通である.

## 6.4.3 ステップサイズ

$\alpha$ は最初は 1 とし, 以降, ラグランジュ乗数がアップデートされた回数の逆数とした。すなわち, 最初のアップデートの際は $\alpha$ は 1 であり, 次のアップデートの際は $\frac{1}{2}$, さらに次のアップデートの際には $\frac{1}{3}$ となる.

## 6.4.4 イテレーション

ラグランジュヒューリスティックによるデコーディングの際にはイテレーションの回数 $T$ を調整することができる。イテレーションの回数は 10 回と 100 回とし, それぞれ RCKM-LH(10) と RCKM-LH(100) として示す.

## 6.5 結果と考察

要約品質の評価を表 3 に，要約時間の評価を表 4 に示す.

TSC-3 コーパスにおける評価の結果から述べる。まず， RCKM と MCM， KM の差異に目を向ける。RCKM の中では RF が最も高いROUGE 值を得ており, 次いで SR という結果となった． RF および $\mathrm{SR}$ はその最適解において MCM を有意に上回っていた. 提案するラグランジュヒューリスティックによるデコーディングを用いた場合 RCKM-LH では，イテレーション回数が 10 回の場合でも 100 回の場でも，RF は MCM を有意に上回っている一方，SR は MCM と有意な差がなかった。表 4 に示すように，提案するデコーディング法はソルバーによるデコーディングと比べ高速に要約を生成できており, MCM と同水準以上の要約を高速に生成できることがわかる．MCM と MCM-GR を比べると, 貪欲法はソルバーに比べ高速にデコーディングを行うことができるものの，MCM-GR の方が有意に ROUGE 值が低く, 探索誤りが生じていることがわかる．KM と MCM の間に有意差はなかったものの,
表 3 要約品質の評価

表 4 要約時間の評価

単位はすべて秒である。
全体として MCM がより高い ROUGE 值を示した.

提案する要約モデル RCKM は，㔯長性パラメータを RF あるいは $\mathrm{SR}$ とした際に MCM に比べ優れている。この理由は，参照要約は単語のレべルにおいてある程度の壳長性を持っているためである。図 1 は，TSC-3コーパスに含まれる参照要約の 1 つである. 同一の内容語はゴシック体として示してある。図 1 から，明らかに参照要約は単語のレベルにおいて壳長性を持つことがわかる.

図 2 は TSC-3コーパスを用いた実験における冗長性の分布である．縦軸に内容語の種類，横軸に同一の参照要約中での出現頻度をとりプロットした。点は, 参照要約, 6.4 節で述べた方法によって設定された艺長性パラメータ，および各手法によって実際に生成された要約における壳長性の分布を示している。例えば，TSC-3 コーパスに含まれる 2093 種類の内容語は同一の参照要約に一度しか出現しない. 一方, 10 種類の内容語は, 同一の参照要約に 10 回以上出現することがある，図 1 および図 2 が示すように，ある 1 つの参照要約において, 同一の単語が複数回出現することは何ら珍しいことではない.

提案する冗長性制約付きナップサックモデル RCKM は，壳長性パラメータを通じ，生成する要約に一定の冗長性を許容することができる。一方，最大被覆モデル MCM は壳長性を忌避する. 実際に図 2 が示すように，MCM が生成する要約は参照要約に比べ冗長性が低い. そのため, 図 1 のように 1 つの参照要約において同一の単語が複数回出現するという現象を十分に捉えることができない。それに対し，ナップサックモデル $\mathbf{K M}$ が生成する要約は高い冗長性を持つ. 図 2 が示すように, 要約中に 4 回以上出現する単語の種類が参照要約に比べて多く, 特に 10 回以上出現する単語が 42 種類存在している.このように過度に壳長な要約を生成する性質は複数文書要約にとっては好ましいものではない.

図 2 を見ると, 朵長性パラメータ SR は参照要約の壳長性に近い艺長性を有する要約を実現

\begin{abstract}
エチオピア北部の約 250 万年前の地層で米国・エチオピア・日本の研究チームが発見した人骨化石が、猿人から原人へ進化する過程にある新種の猿人であることが分かった。現代人の直接の祖先とされる約 200 万年前の原人、ホモ ・ハビリスとそれ以前の猿人の間をつなぐ化石はなく、人類の進化のミッシングリンクとされてきた。この化石は新種の猿人化石として、現地語で「驚き」を意味する言葉から「ガルヒ猿人」と名づけられた。今回発掘された手足の骨は、長さのバランスが約 320 万年前のアファール猿人、約 170 万年前の原人、ホモ・エレクトスの中間にあたる。二足歩行に適するよう脚が長くなっていたとみられる。また、石器で切り取られた跡のある大型動物レイヨウの骨なども見つかった。人類が肉食をしたことを示す最古の証拠で、石器を実際に使用した跡としても最古となる。
\end{abstract}

図 1 TSC-3 コーパスに含まれる参照要約の 1 つ

2 回以上出現する内容語はゴシック体として示した. 他の処理と同様に, 単語境界および品詞の同定は Fuchi らによる形態素解析器 (Fuchi and Takagi 1998) によった.

図 2 TSC-3 コーパスを用いた実験における壳長性の分布

縦軸に内容語の種類, 横軸に同一の参照要約中での出現頻度をとりプロットした. 縦軸は対数スケールとなっていることに注意されたい. 凡例の Reference は, TSC-3 コーパスの参照要約に含まれる内容語の艺長性の分布である。すなわち， TSC-3 コーパスの参照要約に含まれる内容語のうち， 2,093 種類は同一の参照要約に 1 回しか出現しないが, 10 種類は, 同一の参照要約に 10 回以上出現することがある. 凡例の Const-ON, Const-KL および Const-SR はそれぞれ 6.4 節で述べた冗長性パラメータ ON， KL および SR に従って計算された概念冗長性の分布である。例えば， SR は 2,159 種類の単語に同一の要約中において 2 回まで出現することを許している. 凡例の Summ-ON, Summ-KL, Summ-SR, Summ-RF, Summ-MCM および Summ-KM はそれぞれ実際に生成された要約における冗長性の分布である. SummON，Summ-KL，Summ-SR および Summ-RF は冗長性制約付きナップサックモデル RCKM にそれぞれ壳長性パラメータ ON， KL，SR および RF を与え，ソルバーを用いてデコードし生成された要約の壳長性である. Summ-MCM は最大被覆モデル MCM をソルバーを用いてデコードし生成された要約の冗長性である. Summ-KM はナップサックモデルを動的計画ナップサックアルゴリズムを用いてデコー ドし生成された要約の壳長性である.

できている，全体的な傾向として，ナップサックモデルでは，要約中にある回数だけ出現する単語の種類は左から右に向かってなだらかに減少していく.これは, 要約中に 1 度しか出現しない概念の種類と, 何度も出現する概念の種類にあまり差がないことを示しており，すなわち，何度も出現する概念の種類が相対的に多いことを示している。一方, 最大被覆モデルは左から右に向かって急峻な勾配で種類が減少していく。これは, 要約中に 1 度しか出現しない概念の種類が相対的に多いことを示している，参照要約の壳長性は, これらナップサックモデルと最大被覆モデルの中間を取るように推移しており, 艺長性パラメータ SRによって生成された要
約の冗長性も, 参照要約の冗長性に近い位置で推移している。このように参照要約に近い冗長性を再現できたため，SR は良好な性能を示すことができたものと考えられる．

ナップサックモデルのような過度の壳長性は複数文書要約において問題となる一方, 同一の単語，あるいは関連する単語が前後の文に出現する性質は，自動要約の分野において Lexical chain と呼ばれており, 重要文抽出の際の重要な手がかりとして利用されている (Barzilay and Elhadad 1997; Clarke and Lapata 2007). RCKM はこの性質を捉えることができたということもできよう.

テキスト一貫性に関する研究においても，人手によって書かれたテキストにおいて同一の単語が同一のテキストに複数回出現するという性質は利用されている。テキストの一貫性を評価する手法の 1 つである Entity grid は，連続する 2 つの文における，単語の意味役割の変化を特徵量として用いており (Barzilay and Lapata 2005, 2008; 横野, 奥村 2010), 同一の単語が同一のテキストに複数回出現するという仮定を置いている。参照要約は人手によって書かれたものであるため，テキスト一貫性の観点からこの性質を持っていると考えることができる。このことから，壳長性パラメータ r はテキスト一貫性の観点から設定することもできよう.

次に, 壳長性パラメータについて述べる。 RCKM の中では RF が最も良好な性能を示し, ついで $\mathbf{S R}, \mathrm{KL}, \mathrm{ON}$ となった.

参照要約の冗長性を模倣した場合が最良の結果を得たことから, 壳長性の設定は RCKM にとって重要であると言える。壳長性パラメータ $\mathbf{r}$ を正確に設定するためには, 入力文書集合と参照要約の組から回帰モデルを構築し, 各単語の参照要約における適切な出現頻度を予測することも考えられよう。

ON に目を向けると，ON の生成した要約の品質は $\mathrm{SR}$ や $\mathrm{KL}$ に比べて著しく悪い。これは，上に述べたように，テキスト一貫性の観点から説明できる。同一の単語は一度しか要約に出現できないという ON の制約は，上に述べた性質を持ったテキストを生成することを許さない.このため一貫性を欠いたテキストを生成してしまい，これは人間による要約を模倣するという観点からは大きな問題がある.

SR と KL を比較すると, 有意に SR の ROUGE 值が高かった. 図 2 の Const-KL が示すように，KLによる冗長性の制約は参照要約の壳長性をうまく模倣しているものの， 2 回以上の出現を許す単語の種類が参照要約に比べて少ない. TSC-3 コーパスの評価セットの要約率は平均して $6 \%$ 前後であるため, KL は要約長に影響され苍長性について厳しい制約を要約に課す. このため, Summ-KL が示すように，要約に十分な苍長性を許すことができず，SR に比べて ROUGE 值において劣後したものと考えられる.

一方, Const-SR は全体的に高い艺長性を許すものとなっているが，実際に生成された要約の冗長性 Summ-SR は参照要約の壳長性に近い.SRによって生成された要約を確認すると, 高い壳長性の原因となり要約の品質の低下を招く概念の冗長性を抑制しつつ, 概念重要度に従っ

て他の概念を要約に組み込んでおり，これが良好な ROUGE 値を得た理由と考えられる。次にレビューにおける評価の結果について述べる。 RCKM と MCM，KM の差異について目を向けると，KM は MCM と比べ有意に ROUGE 値が低かった，TSC-3 での評価と異なり， MCM と MCM-GR の間に有意な差はなかった。また， MCM と RCKM の全ての手法の間にも有意な差はなかった，RCKM の中でも，壳長性パラメータによる有意な差はなかった，一方，TSC-3 での評価と同様に，表 4 が示すように提案するデコーディング法はソルバーと比べ高速に要約を生成できており，MCM と同水準の要約を高速に生成できることがわかる.

HUMAN に対してはいずれの手法も及ばなかった. これには 2 つ理由があると考えられる. 1 つは概念重要度の設定である。今回は要約対象の文書集合中での評価情報の頻度を概念重要度として用いたが, 参照要約を用いて概念重要度を学習することでより良好な ROUGE 値を得られる可能性がある。もう 1 つは文の選択のみで要約を作成することの限界である。前述したように，レビューコーパスの参照要約は人間によって自由に記述されているため, 文の選択だけでは参照要約と同水準の要約に到達することは難しいと考えられる。この点の解決のためには，文短縮 (平尾，鈴木，磯崎 2009a) など，文を書き換える処理を要約の過程に加える必要があろう.

TSC-3 とレビューを比較すると，前者においては RCKM が MCM を上回る性能を持つものの, 後者においてはそれらの間に差がない.これらは新聞記事の要約とレビュー記事の要約の差異を端的に表している。前者は単語を被覆の対象としているため, 上に示したように, 1 つの要約に複数の単語が含まれることを許すことによって，より高いROUGE 値を得ることができる。一方, 後者が被覆の対象とするものは評価情報であり，ある特定の評価情報は 1 つの要約に 1 つだけ入っていれば十分である。これは，TSC-3 においては劣った要約品質を示した ON が，レビューにおいては他の手法と同水準の要約品質を示していることからもわかる.

図 3 は, レビューコーパスに含まれる評価情報を, 縦軸に評価情報の種類, 横軸に同一の参照要約中での出現頻度をとりプロットしたものである. 図 2 と比較するとその差は明らかであり, レビューでは参照要約においてある特定の評価情報は 1 度しか出現しないことがほとんどである。

最後に, 提案したラグランジュヒューリスティックによる近似解法の近似精度についても述べておく，近似精度を表 5 に示す。数値は，ソルバーによって得られた最適解の目的関数値を 100 としたときの，近似解法による解の目的関数値を百分率で示したものである．計算にあたっては，いずれも朵長性パラメータは SR とし， 30 セットそれぞれの近似精度の平均を取った。表 5 が示すように，提案する近似解法は良好な近似精度を持つことがわかる。

図 3 レビューコーパスを用いた実験における壳長性の分布

縦軸に評価情報の種類, 横軸に同一の参照要約中での出現頻度をとりプロットした. 縦軸は対数スケールとなっていることに注意されたい. 凡例の Reference は, レビューコーパスの参照要約に含まれる内容語の冗長性の分布である。すなわち, レビューコーパスの参照要約に含まれる内容語のうち, 509 種類は同一の参照要約に 1 回だけ出現し， 6 種類は 2 回， 1 種類は 3 回出現することがある. 凡例の Const-ON, Const-KL および Const-SR はそれぞれ 6.4 節で述べた圥長性パラメータ ON， KL および SR に従って計算された概念冗長性の分布である。 凡例の Summ-ON, Summ-KL, Summ-SR, Summ-RF, Summ-MCM および Summ-KM はそれぞれ実際に生成された要約における冗長性の分布である. Summ-ON, Summ-KL, Summ-SR および Summ-RF は壳長性制約付きナップサックモデル RCKM にそれぞれ壳長性パラメー 夕 ON， KL， SR および RF を与え, ソルバーを用いてデコードし生成された要約の壳長性である. Summ-MCM は最大被覆モデル MCM をソルバーを用いてデコードし生成された要約の宇長性である. Summ-KM はナップサックモデルを動的計画ナップサックアルゴリズムを用いてデコードし生成された要約の壳長性である.

表 5 近似精度

## 7 まとめ

本論文では, 複数文書要約において重要なモデルである最大被覆モデルのデコーディングを高速化することを企図し, 要約に含めるべき単語数を直接制御する冗長性制約付きナップサック問題に基づく要約モデルを提案した。本論文の新規性および貢献を以下にまとめる.
- 元長性制約付きナップサック問題に基づく要約モデルは, その最適解において, 最大被覆問題を用いた要約モデルに対して，ROUGE (Lin 2004) において同等以上の性能を持つことを示した。

・ ラグランジュヒューリスティクスに基づくデコーディング法によって得られる近似解は,最大被覆問題の最適解と ROUGE において同等であることを示した。
- 提案手法のデコーディング速度は, 整数計画ソルバーによる最大被覆問題のデコーディング速度より 100 倍以上高速であることを示した.

今後の課題としては, 上で述べたように圥長性パラメータをテキスト一貫性の観点から推定することを検討している．また， 壳長性パラメータを入力文書集合と参照要約の組から推定することも検討している。

## 謝 辞

本論文の執筆にあたり, NTTコミュニケーション科学基礎研究所の西野正彬研究員より有益なご助言を頂戴した，記して感謝する。また，査読者および担当編集委員の方々，編集委員会より様々な有益なご助言を頂戴した。記して感謝する。

## 参考文献

浅野久子, 平野徹, 小林のぞみ, 松尾義博 (2008). Web 上の口コミを分析する評判情報インデクシング技術. NTT 技術ジャーナル, 20 (6), pp. 12-15.

Barzilay, R. and Elhadad, M. (1997). "Using Lexical Chains for Text Summarization." In Proceedings of the Intelligent Scalable Text Summarization Workshop (ISTS), pp. 10-17.

Barzilay, R. and Lapata, M. (2005). "Modeling Local Coherence: An Entity-based Approach."

In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics (ACL), pp. 141-148.

Barzilay, R. and Lapata, M. (2008). "Modeling Local Coherence: An Entity-based Approach." Computational Linguistics, 34 (1), pp. 1-34.

Clarke, J. and Lapata, M. (2007). "Modelling Compression with Discourse Constraints." In Pro-
ceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pp. 1-11.

Filatova, E. and Hatzivassiloglou, V. (2004). "A Formal Model for Information Selection in Multi-Sentence Text Extraction." In Proceedings of Coling 2004, pp. 397-403.

Fuchi, T. and Takagi, S. (1998). "Japanese Morphological Analyzer Using Word Co-occurrence: JTAG." In Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and the 17th International Conference on Computational Linguistics (ACLCOLING), pp. 409-413.

Gillick, D. and Favre, B. (2009). "A Scalable Global Model for Summarization." In Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing, pp. 10-18.

Haddadi, S. (1997). "Simple Lagrangian Heuristic for the Set Covering Problem." European Journal of Operational Research, 97, pp. 200-204.

Higashinaka, R., Minami, Y., Nishikawa, H., Dohsaka, K., Meguro, T., Kobashikawa, S., Masataki, H., Yoshioka, O., Takahashi, S., and Kikui, G. (2010). "Improving HMM-based Extractive Summarization for Multi-Domain Contact Center Dialogues." In Proceedings of the IEEE Workshop on Spoken Language Technology (SLT), pp. 61-66.

平尾努, 奥村学, 磯崎秀樹 (2006). 拡張ストリングカーネルを用いた要約システム自動評価法.情報処理学会論文誌, 47 (6), pp. 1753-1766.

平尾努, 鈴木潤, 磯崎秀樹 (2009a). 構文情報に依存しない文短縮手法. 情報処理学会論文誌： データベース, $2(1)$, pp. 1-9.

平尾努, 鈴木潤, 磯崎秀樹 $(2009 b)$. 最適化問題としての文書要約. 人工知能学会論文誌, $24(2)$, pp. 223-231.

Hirao, T., Fukushima, T., Okumura, M., Nobata, C., and Nanba, H. (2004). "Corpus and Evaluation Measures for Multiple Document Summarization with Multiple Sources." In Proceedings of Coling 2004, pp. 446-452.

Holm, S. (1979). "A Simple Sequentially Rejective Multiple Test Procedure." Scandinavian Journal of Statistics, 6 (2), pp. 65-70.

Imamura, K., Kikui, G., and Yasuda, N. (2007). "Japanese Dependency Parsing Using Sequential Labeling for Semi-spoken Language." In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions, pp. 225-228.

Jelinek, F. (1969). "Fast Sequential Decoding Algorithm Using a Stack." IBM Journal of Research and Development, 13 (6), pp. 675-685.

Khuller, S., Moss, A., and Naor, J. (1999). "The Budgeted Maximum Coverage Problem."

Information Processing Letters, 70 (1), pp. 39-45.

Korte, B. and Vygen, J. (2008). Combinatorial Optimization (3rd edition). Springer-Verlag.

Lin, C.-Y. (2004). "ROUGE: A Package for Automatic Evaluation of Summaries." In Proceedings of ACL Workshop Text Summarization Branches Out, pp. 74-81.

McDonald, R. (2007). "A Study of Global Inference Algorithms in Multi-document Summarization." In Proceedings of the 29th European Conference on Information Retrieval (ECIR), pp. 557-564.

西川仁, 長谷川隆明, 松尾義博, 菊井玄一郎 (2013). 文の選択と順序付けを同時に行う評価文書要約モデル. 人工知能学会論文誌, 28 (1), pp. 88-99.

奥村学，難波英嗣 (2005). テキスト自動要約. オーム社.

高村大也, 奥村学 (2008). 最大被覆問題とその変種による文書要約モデル. 人工知能学会論文誌, $23(6)$, pp. 505-513.

Umetani, S. and Yagiura, M. (2007). "Relaxation Heuristics for the Set Covering Problem." Journal of the Operations Research Society of Japan, 50, pp. 350-375.

Wilcoxon, F. (1945). "Individual Comparisons by Ranking Methods." Biometrics Bulletin, 1 (6), pp. 80-83.

Yamada, T., Kataoka, S., and Watanabe, K. (2002). "Heuristic and Exact Algorithms for the Disjunctively Constrained Knapsack Problem." Journal of Information Processing, 43 (9), pp. 2864-2870.

Yih, W.-t., Goodman, J., Vanderwende, L., and Suzuki, H. (2007). "Multi-document Summarization by Maximizing Informative Content-words." In IJCAI'07: Proceedings of the 20th international joint conference on Artifical intelligence, pp. 1776-1782.

横野光, 奥村学 (2010). テキスト結束性を考慮した entity gridに基づく局所的一貫性モデル. 自然言語処理, $\mathbf{1 7}$ (1), pp. 161-182.

## 付録

## A 評価情報の抽出方法

まず，評洒情報について述べる，西川らの提案 (西川他 2013) と同様に，本論文では，評価情報を評価属性 aspect と評価極性 polarity $\in\{-1,0,1\}$ の組 $e=($ aspect, polarity $)$ として考える。評価属性は, 何らかの対象が評価される際の観点を示す。評価極性は, 対象が評価属性に関してポジティブな評価をされているときに 1 , ネガティブな評価をされているときに -1 , ど

ちらとも言えないときに 0 の 3 値を取るものとする。一例として, 「このデジタルカメラは画質がよい」という表現を考える。この表現の評価属性は「画質」である。また，評価表現「よい」はポジティブな評価であることから，評価極性は 1 となる。そのため, この表現から評価情報 $e=($ 画質, 1$)$ が得られる.

評価情報は以下のように抽出する.

(1) 文に係り受け解析を行う.

（2）評価表現とその評価極性の組を格納した辞書（評価表現辞書）と係り受け解析の結果を照合し，評価表現とその評価極性を得る.

（3）係り受け木で，評価表現に係っている名詞を評価属性とする.

（4）得られた評価属性と評価極性を出力する.

## 略歴

西川仁：2006 年慶應義塾大学総合政策学部卒業. 2008 年同大学大学院政策・

メディア研究科修士課程修了. 同年日本電信電話株式会社入社. 現在 NTT メディアインテリジェンス研究所研究員. 2012 年より奈良先端科学技術大学大学院博士後期課程在学中. 自然言語処理の研究開発に従事. 言語処理学会,情報処理学会, 人工知能学会, ACL 各会員.

平尾努：1995 年関西大学工学部電気工学科卒業. 1997 年奈良先端科学技術大学院大学情報科学研究科博士前期課程修了. 同年株式会社 NTT データ入社. 2000 年より NTTコミュニケーション科学基礎研究所に所属. 博士（工学). 自然言語処理の研究に従事. 言語処理学会, 情報処理学会, ACL 各会員.

牧野俊朗 : 1987 年東京大学工学部電子工学科卒業, 1992 年同大学院博士課程修了. 同年日本電信電話株式会社入社. 現在 NTT メディアインテリジェン丆研究所主幹研究員. 博士 (工学). 知識獲得, 推論手法, 自然言語処理などに関する研究開発に従事.

松尾義博: 1988 年大阪大学理学部物理学科卒業. 1990 年同大学大学院研究科博士前期課程修了. 同年日本電信電話株式会社入社. 現在 NTT メディアインテリジェンス研究所音声・言語基盤技術グループリーダ。機械翻訳，自然言語処理の研究に従事. 言語処理学会, 情報処理学会各会員.

松本裕治：1977 年京都大学工学部情報工学科卒業. 1979 年同大学大学院工学研究科修士課程情報工学専攻修了. 同年電子技術総合研究所入所. 1984 85 年英国インペリアルカレッジ客員研究員. $1985 \sim 87$ 年財団法人新世代コンピュータ技術開発機構に出向. 京都大学助教授を経て, 1993 年より奈良先端科学技術大学院大学教授, 現在に至る. 工学博士．専門は自然言語処理．言
語処理学会, 情報処理学会, 人工知能学会, 認知科学会, AAAI, ACL, ACM 各会員. 情報処理学会フェロー. ACL Fellow.

(2013 年 3 月 11 日受付)

(2013 年 6 月 3 日再受付)

(2013 年 7 月 9 日採録)