\documentclass[japanese]{jnlp_1.4}
\usepackage{jnlpbbl_1.3}
\usepackage[dvips]{graphicx}
\usepackage{amsmath}
\usepackage{hangcaption_jnlp}
\usepackage{udline}
\setulminsep{1.2ex}{0.2ex}
\let\underline
\usepackage{array}

\usepackage{amssymb}
\usepackage{algorithm,algorithmic}

\newcommand{\argmax}{}
\newcommand{\argmin}{}




\Volume{20}
\Number{4}
\Month{September}
\Year{2013}

\received{2013}{3}{11}
\revised{2013}{6}{3}
\accepted{2013}{7}{9}

\setcounter{page}{585}

\jtitle{冗長性制約付きナップサック問題に基づく複数文書要約モデル}
\jauthor{西川　　仁\affiref{Author_1}\affiref{Author_2} \and 平尾　　努\affiref{Author_3} \and 牧野　俊朗\affiref{Author_1} \and 松尾　義博\affiref{Author_1} \and 松本　裕治\affiref{Author_2}}
\jabstract{
本論文では，複数文書要約を冗長性制約付きナップサック問題として捉える．
この問題に基づく要約モデルは，ナップサック問題に基づく要約モデルに対し，冗長性を削減するための制約を加えることで得られる．
この問題は NP 困難であり，計算量が大きいことから，高速に求解するための近似解法として，ラグランジュヒューリスティックに基づくデコーディングアルゴリズムを提案する．
ROUGE に基づく評価によれば，我々の提案する要約モデルは，モデルの最適解において，最大被覆問題に基づく要約モデルを上回る性能を持つ．
要約の速度に関しても評価を行い，我々の提案するデコーディングアルゴリズムは最大被覆問題に基づく要約モデルの最適解と同水準の近似解を，整数計画ソルバーと比べ100倍以上高速に発見できることがわかった．
}
\jkeywords{自動要約，複数文書要約，ナップサック問題，最大被覆問題，ラグランジュ緩和}

\etitle{Multi-Document Summarization Model Based on Redundancy-Constrained Knapsack Problem}
\eauthor{Hitoshi Nishikawa\affiref{Author_1}\affiref{Author_2} \and Tsutomu Hirao\affiref{Author_3} \and Toshiro Makino\affiref{Author_1} \and \\
	Yoshihiro Matsuo\affiref{Author_1} \and Yuji Matsumoto\affiref{Author_2}} 
\eabstract{
\vspace*{-5pt}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.
}
\ekeywords{Automatic Summarization, Multi-Document Summarization, Knapsack Problem, Maximum Coverage Problem, Lagrange Relaxation}

\headauthor{西川，平尾，牧野，松尾，松本}
\headtitle{冗長性制約付きナップサック問題に基づく複数文書要約モデル}

\affilabel{Author_1}{日本電信電話株式会社 NTTメディアインテリジェンス研究所}{NTT Media Intelligence Laboratories, Nippon Telegraph and Telephone Corporation}
\affilabel{Author_2}{奈良先端科学技術大学院大学情報科学研究科}{Graduate School of Information Science, Nara Institute of Science and Technology}
\affilabel{Author_3}{日本電信電話株式会社 NTTコミュニケーション科学基礎研究所}{NTT Communication Science Laboratories, Nippon Telegraph and Telephone Corporation}



\begin{document}
\maketitle


\section{はじめに}

現在の自動要約の多くは文を単位にした処理を行っている \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 節では本論文についてまとめる．



\section{関連研究}
\label{relatedwork}

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

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

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

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

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

単一文書要約に目を向けると，単一文書要約は冗長性が問題となる恐れが少ないため，冗長性を加味しない手法を利用することができる．
単一文書要約は，ナップサック問題として定式化できる \cite{mcdonald07,hirao09b}．
ナップサック問題による要約モデルも文の集合と要約長を入力とする．
最大被覆問題と異なり，ナップサック問題はそれぞれの文が直接重要度を持っている．
ナップサック問題の最適解は，合計の長さが要約長を超えない文の集合のうち，集合を構成する文の重要度の和が最大となるものである．
ナップサック問題の最適解は動的計画法の一種である動的計画ナップサックアルゴリズムによって擬多項式時間で求めることができる \cite{korte08}．
そのため，ナップサック問題の最適解は高速に求めることができる．
しかし，ナップサック問題は文に対して直接重要度を定義し，その和を最大化するものであるため，冗長性を削減する仕組みを持たない．
従って，複数文書要約に適用した場合，冗長な要約が生成される恐れがある．

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



\section{最大被覆モデルとナップサックモデル}

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

\subsection{最大被覆モデル}

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

式 (1) が目的関数であり，式 (2)\footnote{本論文では，$ n $ 次元のベクトル $ {\bf a} $ と $ {\bf b} $ に大小関係 $ {\bf a} \geq {\bf b} $ が成り立つのは，ベクトル $ {\bf a} $ の要素 $ a_{i} $ とベクトル $ {\bf b} $ の要素 $ b_{i} $ に $ a_{i} \geq b_{i} ( \forall i ) $ が成り立つときとする．}から 式 (5) が制約である．
式 (4) が示すように $ {\bf z} $ の要素は0あるいは1である．
もし概念 $ z_{j} $ が要約に含まれれば，$ z_{j} = 1 $ となり，その重要度 $ w_{j} $ は目的関数に加算される．
可能であれば全ての概念を要約に含めたいが，要約長の制限によってはそれは許されない．
式 (2) が示すように，概念 $ z_{j} $ を要約に含めるためには，$ z_{j} $ を含むいずれかの文が要約として選択されていなければならない．
仮に文 $ x_{i} $ が要約に含まれた場合，式 (5) の左辺の値は $ l_{i} $ だけ増える．
式 (5) によって要約として選択された文の長さの合計は $ K $ を超えることが許されない．
式 (3) の示すように $ {\bf x} $ の要素は0あるいは1である．
このことは1つの文は一度しか要約に含めないことを示す．

これらのことから，最大被覆モデルの最適解は，要約長を満たす文の組み合わせを全て試し，全ての組み合わせに対して $ {\bf z} $ を計算し，$ {\bf w} $ とかけあわせ，かけあわせた値が最大となる文の組み合わせを探し出せば見つけられるとわかる．
しかし，一部の組み合わせは要約長を満たさない場合があるものの，文の組み合わせの数は $ 2^{n} $ にもなる．
そのため，全ての組み合わせを列挙することは困難である．



\subsection{ナップサックモデル}

次に，ナップサック問題に目を向けることにする．
$ {\bf x} $ を文 $ i $ が要約に含まれる際に $ x_{i} = 1 $ となる決定変数を要素とするベクトルとする．
$ {\bf z} $ を概念 $ j $ が要約に含まれる際に $ z_{j} = 1 $ となる決定変数を要素とするベクトルとする．
上述した最大被覆モデルと同様の記法に従ってナップサックモデルを記述すると以下のようになる．
\begin{align}
\max_{{\bf z}} & \quad {\bf w}^{\top} {\bf z} \\
s.t. & \quad  {\bf Ax} = {\bf z} \\
& \quad {\bf x} \in \{0, 1\}^{n} \\
& \quad {\bf z} \in ( \mathbb{N}^{0} )^{m} \\
& \quad {\bf l}^{\top} {\bf x} \leq K
\end{align}

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

式 (4) ではベクトル $ {\bf z } $ は0と1を要素とするベクトルであったが，式 (9) ではベクトル $ {\bf z } $ は0以上の自然数を要素とするベクトルである．
\pagebreak
最大被覆モデルでは要約に同じ概念が何個含まれていようともそれぞれの概念について目的関数において一度しかその重要度を加算しなかった．
それに対してナップサックモデルでは要約に同じ概念が複数含まれていた場合その数だけ重要度を目的関数において加算する．
この性質のため，ナップサックモデルを用いて複数文書要約を行った場合には冗長な要約ができる可能性が高く，したがって，ナップサックモデルの複数文書要約における性能は芳しいものではない．

式 (7) は，式 (2) と異なり，文が含む概念の数をそのままベクトル $ {\bf 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つ含まれることになる．



\section{冗長性制約付きナップサックモデル}

\subsection{ナップサックモデルへの冗長性制約の付与}

前節で述べたように，最大被覆問題が冗長性に強い理由は式 (4) にあり，ナップサックモデルが冗長性に弱い理由は式 (9) であった．
そこで，式 (9) に工夫を施すことでナップサックモデルの冗長性を抑制することを考える．
すなわち，ある単語が要約に含まれる回数を直接制御することで，ナップサックモデルの冗長性を削減する．
本論文の主たる貢献はここにある．
\begin{align}
\max_{{\bf z}} & \quad {\bf w}^{\top} {\bf z} \\
s.t. & \quad {\bf Ax} = {\bf z} \\
& \quad {\bf x} \in \{0, 1\}^{n} \\
& \quad {\bf z} \in \{ z_{j} | \mathbb{N}^{0} \cap [0, r_{j}] \}^{m} \\
& \quad {\bf l}^{\top} {\bf x} \leq K
\end{align}

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

このモデルは最大被覆モデルと等価ではない．
最大被覆モデルは，要約に概念が複数含まれることを許す．
ただし，目的関数を計算する上では1つの概念の重要度は一度しか加えない．
それに対し，冗長性制約付きナップサックモデルは，
\pagebreak
ある概念が要約に含まれる数を直接制限する\footnote{なお，文の間に，ベクトル $ {\bf r } $ を通じて排他的な制約が与えられているものとみなすと，冗長制約付きナップサックモデルは，排他制約付きナップサックモデル \cite{yamada02} とみなせる．例えば，上に述べた文1と文2は概念5のためにいずれか一方しか要約に含めることができないという制約は，$ x_{1} + x_{2} \leq 1 $ と記述することができる．}．

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


ナップサックモデルに式 (14) が示す冗長性に関する制約（以下，冗長性制約と呼ぶ）を加えることで冗長性を削減することができるが，動的計画ナップサックアルゴリズムで擬多項式時間で最適解を求めることはできなくなる\footnote{正確には，$ n $ に関しては擬多項式時間であるが，$ m $ に関しては指数時間となるため，素早い求解ができない．}．
冗長性制約付きナップサックモデルを動的計画法で解くことは可能だが\footnote{もちろん，冗長性制約付きナップサックモデルを整数計画ソルバーで解くことも可能である．本論文では，冗長性制約付きナップサックモデルを整数計画ソルバーで解くことでその最適解を求める．}，冗長性制約を考慮するためには，探索の過程において，ある時点での要約に含まれる概念の数を記録しておかなければならない．
ある時点において要約に含まれる概念の数の組み合わせは複数存在するため，これによって探索空間が増大してしまい，素早い求解ができなくなる．



\subsection{冗長性制約のラグランジュ緩和}

この冗長性制約付きナップサックモデルから冗長性制約を除去すれば，元のナップサックモデルが得られる．
そこで，この冗長性制約をラグランジュ緩和 \cite{korte08} する．
以下は，式 (14) を緩和し，ベクトル $ {\bf r} $ による冗長性制約を目的関数に組み込んだものである．
\begin{align}
\max_{{\bf z}} & \quad {\bf w}^{\top} {\bf z} + \mbox{\boldmath $\lambda$}({\bf r} - {\bf z})  \\
s.t. & \quad {\bf Ax} = {\bf z} \\
& \quad {\bf x} \in \{0, 1\}^{n} \\
& \quad {\bf z} \in ( \mathbb{N}^{0} )^{m} \\
& \quad \boldsymbol{\lambda} \in ( \mathbb{R}^{+} )^{m} \\
& \quad {\bf l}^{\top} {\bf x} \leq K&
\end{align}

$ \boldsymbol{\lambda} = (\lambda_{1}, \lambda_{2}, \ldots, \lambda_{m}) $ は非負のラグランジュ乗数ベクトルである．
式 (16) から式 (21) は，目的関数である式 (16) の2つ目の項 $\boldsymbol{\lambda}({\bf r} - {\bf z}) $ および式 (20) を除いてナップサックモデルと同じである．
このラグランジュ緩和問題は，要約に含まれる概念 $j$ の個数 $z_{j}$ が $r_{j}$ を超えた際に，非負のラグランジュ乗数 $ \lambda_{j} $ を通じて目的関数に罰を与える．
例えば，あるとき，概念5が要約に3つ含まれている ($z_{5} = 3$) が，ベクトル $ {\bf r} $ によって要約に2つまでしか含めてはならないと制限されている ($ r_{5} = 2 $) とする．
また，ラグランジュ乗数 $ \lambda_{5} $ が1だったとする．
このとき $ \lambda_{j} (r_{5} - z_{5}) = 1 (2 - 3) = -1 $ となり，目的関数は低下する．
$ \boldsymbol{\lambda}$ の調整は，この緩和問題のラグランジュ双対問題 $ L(\boldsymbol{\lambda}) = \min_{\lambda} \{\max_{{\bf z}} {\bf w}^{\top} {\bf z} + \boldsymbol{\lambda}({\bf r} - {\bf z})\} $ を解くことで行う．

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



\section{デコーディング}

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

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

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

下界はなんらかのヒューリスティックによって得られる実行可能解である．
本論文では，Haddadi による方法 \cite{haddadi97} と同様に，貪欲法 \cite{khuller99}を用いて実行可能解を復元する．
詳細については次節で述べる．

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

\begin{algorithm}[b]
\caption{ラグランジュヒューリスティックによるデコーディングアルゴリズム}
\begin{algorithmic}[1]
\STATE{$\boldsymbol{\lambda} \leftarrow {\bf 0} ,\ {\bf s} \leftarrow {\bf 0},\ {\bf x} \leftarrow {\bf 0},\ {\bf z} \leftarrow {\bf 0} $}
\FOR{$ t=1 $ to $ T $}
	\STATE{$ {\bf s} \leftarrow \mathit{sentence}({\bf A}, \ \boldsymbol{\lambda}, \ m, \ n, \ {\bf w}) $}
	\STATE{$ {\bf x} \leftarrow \mathit{dpkp}(K, \ {\bf l}, \ n, \ {\bf s}) $}
	\IF{$ \mathit{score}({\bf A}, m, n, {\bf x}, {\bf w}) \leq b_{u} $}
		\STATE{$ b_{u} \leftarrow \mathit{score}({\bf A}, m, n, {\bf x}, {\bf w}) $}
	\ENDIF
	\STATE{$ {\bf z} \leftarrow \mathit{count}({\bf A}, \ m, \ n, \ {\bf x}) $}
	\IF{$ {\bf z} $ violates ${\bf r}$}
		\STATE{$ {\bf x} \leftarrow \mathit{heuristic}({\bf A}, K, {\bf l}, m, n, {\bf w}) $}
		\IF{$ \mathit{score}({\bf A}, m, n, {\bf x}, {\bf w}) \geq b_{l} $}
			\STATE{$ b_{l} \leftarrow \mathit{score}({\bf A}, m, n, {\bf x}, {\bf w}) $}
			\STATE{$ {\bf x}_{l} \leftarrow {\bf x} $}
		\ENDIF
		\STATE{$\boldsymbol{\lambda} \leftarrow update(\alpha, \ b_{l},\ b_{u},\ \boldsymbol{\lambda},\ m,\ {\bf r},\ {\bf z}) $}
	\ELSE
		\RETURN{$ {\bf x} $}
	\ENDIF
\ENDFOR
\RETURN{$ {\bf x}_{l} $}
\end{algorithmic}
\end{algorithm}

\begin{enumerate}
\item ラグランジュ乗数ベクトル $\boldsymbol{\lambda}$ を適当な値に初期化する．
\item 以下の手続きを既定回数だけ繰り返す．
\begin{enumerate}
\item 動的計画ナップサックアルゴリズムで式 の最適解を得る．
\item a で得た最適解が制約を満たしているときはそれを下界とし，(3) へ．そうでなければヒューリスティックを用いて実行可能解を得る．
\item b で得た実行可能解がこれまでの下界を上回るものであれば，下界を更新する．
\end{enumerate}
\item 下界を出力して終了する．
\end{enumerate}

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

ラグランジュ緩和問題の劣勾配ベクトル $ {\bf d} = (d_{1}, d_{2}, \ldots, d_{m}) $ は以下のようになる．
\begin{equation}
d_{j} = r_{j} - z_{j}
\end{equation}


ラグランジュ緩和された集合被覆問題に対する Umetani らの更新式に基づき \cite{umetani07}，ラグランジュ乗数は以下の更新式によって更新する．
\begin{equation}
 \lambda_{j}^{new} \leftarrow \max \left( \lambda_{j}^{old} + \alpha \frac{ b_{u} - b_{l} }{||{\bf d}||^{2}} (z_{j} - r_{j}), 0 \right)
\end{equation}

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



\subsection{貪欲法による実行可能解の復元}

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

\begin{enumerate}
\item 制約に違反している概念を含む文のうち，最も重要度が低いものを要約から除去する．
\item 要約がまだ制約を満たさない場合は (1) へ．要約が制約を満たした場合は，要約に含まれていない文と，要約長 $ K $ と制約を満たした要約の長さの差から，部分問題を生成し，これを貪欲法で解く．
\end{enumerate}

例えば，要約長が300文字であったとする．
制約に違反する文を除去し，制約を満たした要約の長さが200文字だったとすると，100文字分まだ要約に文を含めることができる．
そこで，まだ要約に含まれていない文を，100文字分，貪欲法 \cite{khuller99} を用いて要約に含めることで，実行可能解を求める．



\subsection{動的計画ナップサックアルゴリズム}

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

\begin{algorithm}[t]
\caption{動的計画ナップサックアルゴリズム}
\begin{algorithmic}[1]
\STATE{$ {\bf x} \leftarrow {\bf 0} $}
\FOR{$ k = 0 $ to $ K $}
	\STATE{$ T[0][k] \leftarrow 0 $}
\ENDFOR
\FOR{$ i = 1 $ to $ n $}
	\FOR{$ k = 0 $ to $ K $}
		\STATE{$ T[i][k] \leftarrow T[i-1][k] $}
		\STATE{$ U[i][k] \leftarrow 0 $}
	\ENDFOR
	\FOR{$ k = l_{i} $ to $ K $}
		\IF{$ T[i-1][k - l_{i}] + s_{i} \geq T[i][k] $}
			\STATE{$ T[i][k] \leftarrow T[i-1][k - l_{i}] + s_{i} $}
			\STATE{$ U[i][k] \leftarrow 1 $}
		\ENDIF
	\ENDFOR
\ENDFOR
\STATE{$ k \leftarrow K $}
\FOR{$ i = n $ to $ 1 $}
	\IF{$ U[i][k] = 1 $}
		\STATE{$ x_{i} \leftarrow 1 $}
		\STATE{$ k \leftarrow k - l_{i} $}
	\ENDIF
\ENDFOR
\RETURN{$ {\bf x} $}
\end{algorithmic}
\end{algorithm}

動的計画ナップサックアルゴリズムでは，$ (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] $ に到達するまでの過程を逆にたどることで，ナップサックモデルの最適解を得ることができる．



\section{実験}

本節では提案した手法の性能を評価した結果について報告する．
本節では，\ref{methods} で述べる手法を用いて，\ref{corpora} で述べる文書集合を要約し，生成された要約を \ref{measures} で述べる評価手法で評価する．
\ref{methods} で述べる手法が必要とするパラメータの設定については \ref{parameters} で述べる．
結果とその考察については \ref{results} で述べる．


\subsection{比較手法}\label{methods}
以下の手法を比較した．

\begin{enumerate}
\item {\bf RCKM}\hspace{1zw}
提案手法．冗長性制約付きナップサックモデルを整数計画ソルバーを用いてデコードしたもの．
冗長性制約付きナップサックモデルの最適解における性能を示す．
ソルバーは {\tt lp\_solve}\footnote{http://lpsolve.sourceforge.net/5.5/}を用いた\footnote{商用のソルバーを用いればより高速にデコードできる可能性があるが，それらは有償であるため，今回は広く利用されており無料で利用することができる {\tt lp\_solve} を用いた．}．
\item {\bf RCLM-LH}\hspace{1zw}
提案手法．
冗長性制約付きナップサックモデルを本論文で提案するラグランジュヒューリスティックを用いてデコードしたもの．
提案するデコーディングアルゴリズムによって得られる近似解の性能を示す．
\item {\bf MCM}\hspace{1zw}
ベースライン．
最大被覆モデルをソルバーを用いてデコードしたもの．
\item {\bf MCM-GR}\hspace{1zw}
ベースライン．
最大被覆モデルを貪欲法を用いてデコードしたもの．
\item {\bf KM}\hspace{1zw}
ベースライン．
ナップサックモデルを動的計画ナップサックアルゴリズムでデコードしたもの．
\item {\bf HUMAN}\hspace{1zw}
達成しうる性能の上限を調べるため，複数の参照要約を用いて，性能の上限を求める．
\ref{corpora} 節で述べるコーパスのうち，レビューコーパスは1つの評価セットに対して4つの参照要約が付与されているため，参照要約同士を比較することで性能の上限を示すことが可能である．
4つの参照要約があるため，それらの6つの組み合わせのうち，\ref{measures} 節で述べる評価尺度 ROUGE の値が最も高いものを性能の上限として採用する\footnote{値が最も高いものを利用する理由については \ref{measures} 節で述べる．}．
なお，\ref{corpora} 節で述べるコーパスのうち，TSC-3 は1つの評価セットに対して1つの参照要約しか付与されていないため，これを計算できるのはレビューのみである．
\end{enumerate}

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



\subsection{コーパス}
\label{corpora}

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

\begin{enumerate}
\item {\bf TSC-3}\hspace{1zw}
TSC-3 コーパス \cite{hirao04} は自動要約のシェアード・タスク Text Summarization Challenge 3\footnote{http://lr-www.pi.titech.ac.jp/tsc/tsc3.html}で用いられたコーパスで，複数文書要約の評価セットを含む．
要約の対象となる文書は新聞記事であり，記事は毎日新聞および読売新聞から収集されている．
それぞれの評価セットは企業買収やテロなど特定のトピックに関する新聞記事から構成されている．
評価セットは30セットからなる．
1セットは新聞記事10記事前後からなり，1つの評価セットに含まれる記事の文字数の和は平均して約6,564文字である．
評価セット全体では352記事3,587文が含まれる．
それぞれの評価セットに対しては人間の作業者が短い要約と長い要約の2種類の参照要約を付与している．
Hirao らによれば，参照要約の付与に際し，作業者は要約の対象となる記事を全て読んだのち，当該記事集合にふさわしい要約を作成した \cite{hirao04}．
短い要約は平均して約413文字であり，要約率\footnote{要約率は，参照要約の長さを入力文書集合の長さの和で割ったものである \protect \cite{okumura05}．例えば参照要約が400文字，入力文書集合の長さの和が8000文字である場合，要約率は $ 5\% = \frac{400}{8000} $ となる．}にして約6\%，長い要約は平均して約801文字であり，要約率にして約12\%である\footnote{Hirao らによれば，参照要約の作成時には作業者に対して，短い要約については要約率5\%程度の要約を，長い要約については要約率10\%程度の要約を作成するように指示を与えたとしている \cite{hirao04}．本論文で計測した値とは多少の差があるものの，5\%，10\%という値はあくまで目処として与えたものであると述べられているため，作業者はこれらの指示より多少長い要約を作成したものと思われる．}．
本実験では短いものを用いて評価を行った．
評価セットごとに参照要約の長さが異なるため，要約を生成する際には参照要約と同じ長さを要約長として与え要約を生成した．
すなわち，本コーパスを用いた際には，平均として，約12記事からなる約6,564文字の記事集合を入力とし，約413文字の要約を生成する，要約率約6\%の要約タスクとなる．
\item {\bf レビュー}\hspace{1zw}
新聞記事とは異なるドメインで提案する要約モデルを評価するため，レビュー記事を用いて評価を行った．
インターネット上のレビューサイトから飲食店30店舗に関するレビュー記事を収集し，これを30セットの複数文書要約の評価セットとした．
1セットはレビュー記事15記事前後からなり，1つの評価セットに含まれる記事の文字数の和は平均して約2,472文字である．
評価セット全体では468記事2,275文が含まれる．
それぞれの評価セットに対しては4人の作業者が参照要約を付与しており，作業者は要約の対象となる記事を全て読んだのち，当該記事集合にふさわしい要約を作成した．
要約長はすべて200文字を上限とした．
そのため，実験において要約を生成する際には一律200文字を要約長として要約を生成した．
従って，要約率は平均して8\%である．
本コーパスを用いた際には，平均として，約16記事からなる約2,472文字の記事集合を入力とし，200文字の要約を生成する，要約率約8\%の要約タスクとなる．
\end{enumerate}

表 \ref{tb:statistics} にコーパスに関する統計量をまとめておく．

\begin{table}[t]
\caption{評価に用いたコーパスの統計量}
\label{tb:statistics}
\input{03table02.txt}
\end{table}


\subsection{評価尺度}
\label{measures}

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

\begin{enumerate}
\item {\bf 要約品質}\hspace{1zw}
\pagebreak
要約の品質の評価には要約の自動評価尺度である ROUGE \cite{lin04} を用いた．
ROUGE の亜種のうち，ROUGE-1 および ROUGE-2 を評価に利用した．
なお，平尾らは，参照要約の ROUGE 値を計算する際には，文を構成するすべての単語ではなくて，内容語\footnote{名詞，動詞，形容詞および未知語．}のみを用いて計算を行った方が人間による評価と相関が高い結果が得られると報告している \cite{hirao06}．
そのため，本論文でも ROUGE 値を計算する際には内容語のみを用いた．
生成された要約を単語に分割し品詞を付与する際には Fuchi らによる形態素解析器 \cite{fuchi98} を利用した．
ROUGE 値を算出するプログラムは Lin の文献 \cite{lin04} に従い独自に実装した．
なお，レビューコーパスについては1セットに対して複数の参照要約が付与されているため，評価の際には，当該セットに付与されているすべての参照要約に対して ROUGE 値を求め，最も高い ROUGE 値をその要約の ROUGE 値とした．
この ROUGE 値の計算方針は Lin の提案によるものである \cite{lin04}．
これは，ある入力文書集合に対して妥当な要約は複数存在し得ると考えられることから，参照要約の中で機械による要約にとって最も近いものとの ROUGE 値をもってその要約の評価とするためである\footnote{なお，別途，すべての参照要約に対する ROUGE 値の平均と，最も低い ROUGE 値も求めたが，表 \ref{tb:quality} と同様の傾向を示したため，本論文では割愛する．}．

\item {\bf 要約速度}\hspace{1zw}
要約の生成までの速度を計測した．
いずれのコーパスでも，30セットすべてを要約するまでの時間を計測した．
\end{enumerate}

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



\subsection{パラメータ}
\label{parameters}

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


\subsubsection{概念重要度}

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

\begin{enumerate}
\item {\bf TSC-3}\hspace{1zw}概念 $ j $ は内容語とし，その重み $ w_{j} $ は tf-idf \cite{filatova04,clarke07} に基づき，$ w_{j} = tf_{j} log (\frac{N}{df_{j}}) $ とした．
ここで，$ tf_{j} $ は要約の対象となる入力文書集合中での内容語 $ j $ の出現頻度，$ df_{j} $ は新聞記事コーパス中で内容語 $ j $ を含む記事の数，$ N $ は新聞記事コーパスに含まれる記事の総数である．
新聞記事コーパスとして，2003年と2004年の毎日新聞コーパス\footnote{http://www.nichigai.co.jp/sales/corpus.html}を利用した．
文を単語に分割し品詞を付与する際にはFuchi らによる形態素解析器 \cite{fuchi98} を利用した．

\item {\bf レビュー}\hspace{1zw}レビューを要約の対象としたため，概念 $ j $ として評価情報を利用した．
評価情報の定義とその抽出方法は西川らによるもの \cite{nishikawa13} に従った\footnote{詳細は付録に示す．}．
概念 $ j $ の重み $ w_{j} $ は当該評価情報の入力文書集合中での出現頻度を利用した．
評価情報を文中から抽出する際，形態素解析には Fuchi らによる形態素解析器 \cite{fuchi98} を，係り受け解析には Imamura らによる係り受け解析器 \cite{imamura07} を，評価表現辞書は浅野らによる評価表現辞書 \cite{asano08a} をそれぞれ利用した．
\end{enumerate}

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

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


\subsubsection{概念冗長性}

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

\begin{enumerate}
\item {\bf ON }\hspace{1zw}
概念冗長性を1とする．
これは，同じ概念が2回以上要約に出現することを禁じる．
すなわち $ r_{j} = 1 $ である．
この制約を用いた場合，同一の概念は一度しか要約中に出現することができず，そのため最大被覆問題と同様に冗長性が削減されることが期待される．
最大被覆問題とこの制約を用いた冗長性制約付きナップサックモデルの差異は，前者は目的関数を利用して冗長性を削減するのに対し，後者は制約を用いて冗長性を削減することにある．
\item {\bf KL }\hspace{1zw}
概念 $ j $ の入力文書集合中の出現頻度に，要約長 $ K $ と入力文書集合のサイズ $ L = \sum^{n}_{i=1} l_{i} $ の比をかけたものとする．
ただし，値が小数となることが多いため，その場合は値を切り上げることとした．
すなわち $ r_{j} = \lceil tf_{j} \frac{K}{L} \rceil $ である．
この制約を用いた場合，入力文書集合中での概念の出現頻度の分布が，要約長を加味した上で要約にも同程度再現されることが期待される．
\item {\bf SR }\hspace{1zw}概念冗長性を，各単語の入力文書集合中での出現回数の平方根とする．
{\bf KL } と同様，値が小数となることが多いが，その場合は値を切り下げることとした．
これは {\bf KL } では $ r_{j} $ の値が 1 未満になることがあるのに対し，平方根を取る場合はその恐れがないためである．
すなわち $ r_{j} = \lfloor \sqrt{tf_{j}} \rfloor $ である．
この制約は {\bf KL } と異なり要約長の影響を受けない．
また，{\bf KL } に比べ冗長性に寛容である．
\item {\bf RF}\hspace{1zw}
概念冗長性を，参照要約に含まれる概念の数とした．
これは，概念冗長性が理想的に設定された場合の性能を示している．
なお，レビューコーパスについては複数の参照要約が存在するため，同一の概念については複数の参照要約の平均を取り，小数となった場合は値を切り上げることとした．
\end{enumerate}

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


\subsubsection{ステップサイズ}

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

\subsubsection{イテレーション}

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


\subsection{結果と考察}
\label{results}

要約品質の評価を表 \ref{tb:quality} に，要約時間の評価を表 \ref{tb:speed} に示す．

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

\begin{table}[p]
\caption{要約品質の評価}
\label{tb:quality}
\input{03table03.txt}
\end{table}
\begin{table}[p]
\caption{要約時間の評価}
\label{tb:speed}
\input{03table04.txt}
\end{table}


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

\begin{figure}[b]
\input{03fig01.txt}
\caption{TSC-3 コーパスに含まれる参照要約の1つ}
\label{fg:exref}
\small
2回以上出現する内容語はゴシック体として示した．他の処理と同様に，単語境界および品詞の同定は Fuchi らによる形態素解析器 \protect \cite{fuchi98} によった．
\end{figure}

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

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

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

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

ナップサックモデルのような過度の冗長性は複数文書要約において問題となる一方，同一の単語，あるいは関連する単語が前後の文に出現する性質は，自動要約の分野において Lexical chain と呼ばれており，重要文抽出の際の重要な手がかりとして利用されている \cite{barzilay97,clarke07}．
{\bf RCKM } はこの性質を捉えることができたということもできよう．

テキスト一貫性に関する研究においても，人手によって書かれたテキストにおいて同一の単語が同一のテキストに複数回出現するという性質は利用されている．
テキストの一貫性を評価する手法の1つである Entity grid は，連続する2つの文における，単語の意味役割の変化を特徴量として用いており \cite{barzilay05,barzilay08,yokono10}，同一の単語が同一のテキストに複数回出現するという仮定を置いている．
参照要約は人手によって書かれたものであるため，テキスト一貫性の観点からこの性質を持っていると考えることができる．
このことから，冗長性パラメータ $ {\bf r} $ はテキスト一貫性の観点から設定することもできよう．

次に，冗長性パラメータについて述べる．
{\bf RCKM} の中では {\bf RF} が最も良好な性能を示し，ついで {\bf SR}，{\bf KL}，{\bf ON} となった．

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

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

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

一方，Const-SR は全体的に高い冗長性を許すものとなっているが，実際に生成された要約の冗長性 Summ-SR は参照要約の冗長性に近い．
{\bf SR} によって生成された要約を確認すると，高い冗長性の原因となり要約の品質の低下を招く概念の冗長性を抑制しつつ，概念重要度に従って他の概念を要約に組み込んでおり，これが良好な ROUGE 値を得た理由と考えられる．

次にレビューにおける評価の結果について述べる．
{\bf RCKM} と {\bf MCM}，{\bf KM} の差異について目を向けると，{\bf KM} は {\bf MCM} と比べ有意に ROUGE 値が低かった．
TSC-3 での評価と異なり，{\bf MCM} と {\bf MCM-GR} の間に有意な差はなかった．
また，{\bf MCM} と {\bf RCKM} の全ての手法の間にも有意な差はなかった．
{\bf RCKM } の中でも，冗長性パラメータによる有意な差はなかった．
一方，TSC-3 での評価と同様に，表 \ref{tb:speed} が示すように提案するデコーディング法はソルバーと比べ高速に要約を生成できており，{\bf MCM} と同水準の要約を高速に生成できることがわかる．

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

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

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

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

\begin{figure}[p]
\begin{center}
\includegraphics{20-4ia3f3.eps}
\end{center}
\caption{ レビューコーパスを用いた実験における冗長性の分布}
\label{fg:dist_review}
\small
縦軸に評価情報の種類，横軸に同一の参照要約中での出現頻度をとりプロットした．縦軸は対数スケールとなっていることに注意されたい．凡例の Reference は，レビューコーパスの参照要約に含まれる内容語の冗長性の分布である．すなわち，レビューコーパスの参照要約に含まれる内容語のうち，509種類は同一の参照要約に1回だけ出現し，6種類は2回，1種類は3回出現することがある．凡例の Const-ON，Const-KL および Const-SR はそれぞれ \ref{parameters} 節で述べた冗長性パラメータ {\bf ON}，{\bf KL} および {\bf SR} に従って計算された概念冗長性の分布である．凡例の Summ-ON，Summ-KL，Summ-SR，Summ-RF，Summ-MCM および Summ-KM はそれぞれ実際に生成された要約における冗長性の分布である．Summ-ON，Summ-KL，Summ-SR および Summ-RF は冗長性制約付きナップサックモデル {\bf RCKM} にそれぞれ冗長性パラメータ {\bf ON}，{\bf KL}，{\bf SR} および {\bf RF} を与え，ソルバーを用いてデコードし生成された要約の冗長性である．Summ-MCM は最大被覆モデル {\bf MCM} をソルバーを用いてデコードし生成された要約の冗長性である．Summ-KM はナップサックモデルを動的計画ナップサックアルゴリズムを用いてデコードし生成された要約の冗長性である．
\end{figure}
\begin{table}[p]
\caption{近似精度}
\label{tb:approximation}
\input{03table05.txt}
\end{table}



\section{まとめ}

本論文では，
複数文書要約において重要なモデルである最大被覆モデルのデコーディングを高速化することを企図し，要約に含めるべき単語数を直接制御する冗長性制約付きナップサック問題に基づく要約モデルを提案した．
本論文の新規性および貢献を以下にまとめる．

\begin{itemize}
\item 冗長性制約付きナップサック問題に基づく要約モデルは，その最適解において，最大被覆問題を用いた要約モデルに対して，ROUGE \cite{lin04} において同等以上の性能を持つことを示した．
\item ラグランジュヒューリスティクスに基づくデコーディング法によって得られる近似解は，最大被覆問題の最適解と ROUGE において同等であることを示した．
\item 提案手法のデコーディング速度は，整数計画ソルバーによる最大被覆問題のデコーディング速度より100倍以上高速であることを示した．
\end{itemize}

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


\acknowledgment

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


\bibliographystyle{jnlpbbl_1.5}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{浅野\JBA 平野\JBA 小林\JBA 松尾}{浅野 \Jetal
  }{2008}]{asano08a}
浅野久子\JBA 平野徹\JBA 小林のぞみ\JBA 松尾義博 \BBOP 2008\BBCP.
\newblock Web上の口コミを分析する評判情報インデクシング技術.\
\newblock \Jem{NTT技術ジャーナル}, {\Bbf 20}  (6), \mbox{\BPGS\ 12--15}.

\bibitem[\protect\BCAY{Barzilay \BBA\ Elhadad}{Barzilay \BBA\
  Elhadad}{1997}]{barzilay97}
Barzilay, R.\BBACOMMA\ \BBA\ Elhadad, M. \BBOP 1997\BBCP.
\newblock \BBOQ Using Lexical Chains for Text Summarization.\BBCQ\
\newblock In {\Bem Proceedings of the Intelligent Scalable Text Summarization
  Workshop (ISTS)}, \mbox{\BPGS\ 10--17}.

\bibitem[\protect\BCAY{Barzilay \BBA\ Lapata}{Barzilay \BBA\
  Lapata}{2005}]{barzilay05}
Barzilay, R.\BBACOMMA\ \BBA\ Lapata, M. \BBOP 2005\BBCP.
\newblock \BBOQ Modeling Local Coherence: An Entity-based Approach.\BBCQ\
\newblock In {\Bem Proceedings of the 43rd Annual Meeting on Association for
  Computational Linguistics (ACL)}, \mbox{\BPGS\ 141--148}.

\bibitem[\protect\BCAY{Barzilay \BBA\ Lapata}{Barzilay \BBA\
  Lapata}{2008}]{barzilay08}
Barzilay, R.\BBACOMMA\ \BBA\ Lapata, M. \BBOP 2008\BBCP.
\newblock \BBOQ Modeling Local Coherence: An Entity-based Approach.\BBCQ\
\newblock {\Bem Computational Linguistics}, {\Bbf 34}  (1), \mbox{\BPGS\
  1--34}.

\bibitem[\protect\BCAY{Clarke \BBA\ Lapata}{Clarke \BBA\
  Lapata}{2007}]{clarke07}
Clarke, J.\BBACOMMA\ \BBA\ Lapata, M. \BBOP 2007\BBCP.
\newblock \BBOQ Modelling Compression with Discourse Constraints.\BBCQ\
\newblock In {\Bem Proceedings of the 2007 Joint Conference on Empirical
  Methods in Natural Language Processing and Computational Natural Language
  Learning (EMNLP-CoNLL)}, \mbox{\BPGS\ 1--11}.

\bibitem[\protect\BCAY{Filatova \BBA\ Hatzivassiloglou}{Filatova \BBA\
  Hatzivassiloglou}{2004}]{filatova04}
Filatova, E.\BBACOMMA\ \BBA\ Hatzivassiloglou, V. \BBOP 2004\BBCP.
\newblock \BBOQ A Formal Model for Information Selection in Multi-Sentence Text
  Extraction.\BBCQ\
\newblock In {\Bem Proceedings of Coling 2004}, \mbox{\BPGS\ 397--403}.

\bibitem[\protect\BCAY{Fuchi \BBA\ Takagi}{Fuchi \BBA\ Takagi}{1998}]{fuchi98}
Fuchi, T.\BBACOMMA\ \BBA\ Takagi, S. \BBOP 1998\BBCP.
\newblock \BBOQ Japanese Morphological Analyzer Using Word Co-occurrence:
  JTAG.\BBCQ\
\newblock In {\Bem Proceedings of the 36th Annual Meeting of the Association
  for Computational Linguistics and the 17th International Conference on
  Computational Linguistics (ACL-COLING)}, \mbox{\BPGS\ 409--413}.

\bibitem[\protect\BCAY{Gillick \BBA\ Favre}{Gillick \BBA\
  Favre}{2009}]{gillick09}
Gillick, D.\BBACOMMA\ \BBA\ Favre, B. \BBOP 2009\BBCP.
\newblock \BBOQ A Scalable Global Model for Summarization.\BBCQ\
\newblock In {\Bem Proceedings of the Workshop on Integer Linear Programming
  for Natural Language Processing}, \mbox{\BPGS\ 10--18}.

\bibitem[\protect\BCAY{Haddadi}{Haddadi}{1997}]{haddadi97}
Haddadi, S. \BBOP 1997\BBCP.
\newblock \BBOQ Simple Lagrangian Heuristic for the Set Covering Problem.\BBCQ\
\newblock {\Bem European Journal of Operational Research}, {\Bbf 97},
  \mbox{\BPGS\ 200--204}.

\bibitem[\protect\BCAY{Higashinaka, Minami, Nishikawa, Dohsaka, Meguro,
  Kobashikawa, \mbox{Masataki}, Yoshioka, Takahashi, \BBA\ Kikui}{Higashinaka
  et~al.}{2010}]{higashinaka10b}
Higashinaka, R., Minami, Y., Nishikawa, H., Dohsaka, K., Meguro, T.,
  Kobashikawa, S., \mbox{Masataki}, H., Yoshioka, O., Takahashi, S., \BBA\
  Kikui, G. \BBOP 2010\BBCP.
\newblock \BBOQ Improving HMM-based Extractive Summarization for Multi-Domain
  Contact Center Dialogues.\BBCQ\
\newblock In {\Bem Proceedings of the IEEE Workshop on Spoken Language
  Technology (SLT)}, \mbox{\BPGS\ 61--66}.

\bibitem[\protect\BCAY{平尾\JBA 奥村\JBA 磯崎}{平尾 \Jetal }{2006}]{hirao06}
平尾努\JBA 奥村学\JBA 磯崎秀樹 \BBOP 2006\BBCP.
\newblock 拡張ストリングカーネルを用いた要約システム自動評価法.\
\newblock \Jem{情報処理学会論文誌}, {\Bbf 47}  (6), \mbox{\BPGS\ 1753--1766}.

\bibitem[\protect\BCAY{平尾\JBA 鈴木\JBA 磯崎}{平尾 \Jetal }{2009a}]{hirao09a}
平尾努\JBA 鈴木潤\JBA 磯崎秀樹 \BBOP 2009a\BBCP.
\newblock 構文情報に依存しない文短縮手法.\
\newblock \Jem{情報処理学会論文誌：データベース}, {\Bbf 2}  (1), \mbox{\BPGS\
  1--9}.

\bibitem[\protect\BCAY{平尾\JBA 鈴木\JBA 磯崎}{平尾 \Jetal }{2009b}]{hirao09b}
平尾努\JBA 鈴木潤\JBA 磯崎秀樹 \BBOP 2009b\BBCP.
\newblock 最適化問題としての文書要約.\
\newblock \Jem{人工知能学会論文誌}, {\Bbf 24}  (2), \mbox{\BPGS\ 223--231}.

\bibitem[\protect\BCAY{Hirao, Fukushima, Okumura, Nobata, \BBA\ Nanba}{Hirao
  et~al.}{2004}]{hirao04}
Hirao, T., Fukushima, T., Okumura, M., Nobata, C., \BBA\ Nanba, H. \BBOP
  2004\BBCP.
\newblock \BBOQ Corpus and Evaluation Measures for Multiple Document
  Summarization with Multiple Sources.\BBCQ\
\newblock In {\Bem Proceedings of Coling 2004}, \mbox{\BPGS\ 446--452}.

\bibitem[\protect\BCAY{Holm}{Holm}{1979}]{holm79}
Holm, S. \BBOP 1979\BBCP.
\newblock \BBOQ A Simple Sequentially Rejective Multiple Test Procedure.\BBCQ\
\newblock {\Bem Scandinavian Journal of Statistics}, {\Bbf 6}  (2),
  \mbox{\BPGS\ 65--70}.

\bibitem[\protect\BCAY{Imamura, Kikui, \BBA\ Yasuda}{Imamura
  et~al.}{2007}]{imamura07}
Imamura, K., Kikui, G., \BBA\ Yasuda, N. \BBOP 2007\BBCP.
\newblock \BBOQ Japanese Dependency Parsing Using Sequential Labeling for
  Semi-spoken Language.\BBCQ\
\newblock In {\Bem Proceedings of the 45th Annual Meeting of the Association
  for Computational Linguistics Companion Volume Proceedings of the Demo and
  Poster Sessions}, \mbox{\BPGS\ 225--228}.

\bibitem[\protect\BCAY{Jelinek}{Jelinek}{1969}]{jelinek69}
Jelinek, F. \BBOP 1969\BBCP.
\newblock \BBOQ Fast Sequential Decoding Algorithm Using a Stack.\BBCQ\
\newblock {\Bem IBM Journal of Research and Development}, {\Bbf 13}  (6),
  \mbox{\BPGS\ 675--685}.

\bibitem[\protect\BCAY{Khuller, Moss, \BBA\ Naor}{Khuller
  et~al.}{1999}]{khuller99}
Khuller, S., Moss, A., \BBA\ Naor, J. \BBOP 1999\BBCP.
\newblock \BBOQ The Budgeted Maximum Coverage Problem.\BBCQ\
\newblock {\Bem Information Processing Letters}, {\Bbf 70}  (1), \mbox{\BPGS\
  39--45}.

\bibitem[\protect\BCAY{Korte \BBA\ Vygen}{Korte \BBA\ Vygen}{2008}]{korte08}
Korte, B.\BBACOMMA\ \BBA\ Vygen, J. \BBOP 2008\BBCP.
\newblock {\Bem Combinatorial Optimization\/} (3rd \BEd).
\newblock Springer-Verlag.

\bibitem[\protect\BCAY{Lin}{Lin}{2004}]{lin04}
Lin, C.-Y. \BBOP 2004\BBCP.
\newblock \BBOQ ROUGE: A Package for Automatic Evaluation of Summaries.\BBCQ\
\newblock In {\Bem Proceedings of ACL Workshop Text Summarization Branches
  Out}, \mbox{\BPGS\ 74--81}.

\bibitem[\protect\BCAY{McDonald}{McDonald}{2007}]{mcdonald07}
McDonald, R. \BBOP 2007\BBCP.
\newblock \BBOQ A Study of Global Inference Algorithms in Multi-document
  Summarization.\BBCQ\
\newblock In {\Bem Proceedings of the 29th European Conference on Information
  Retrieval (ECIR)}, \mbox{\BPGS\ 557--564}.

\bibitem[\protect\BCAY{西川\JBA 長谷川\JBA 松尾\JBA 菊井}{西川 \Jetal
  }{2013}]{nishikawa13}
西川仁\JBA 長谷川隆明\JBA 松尾義博\JBA 菊井玄一郎 \BBOP 2013\BBCP.
\newblock 文の選択と順序付けを同時に行う評価文書要約モデル.\
\newblock \Jem{人工知能学会論文誌}, {\Bbf 28}  (1), \mbox{\BPGS\ 88--99}.

\bibitem[\protect\BCAY{奥村\JBA 難波}{奥村\JBA 難波}{2005}]{okumura05}
奥村学\JBA 難波英嗣 \BBOP 2005\BBCP.
\newblock \Jem{テキスト自動要約}.
\newblock オーム社.

\bibitem[\protect\BCAY{高村\JBA 奥村}{高村\JBA 奥村}{2008}]{takamura08}
高村大也\JBA 奥村学 \BBOP 2008\BBCP.
\newblock 最大被覆問題とその変種による文書要約モデル.\
\newblock \Jem{人工知能学会論文誌}, {\Bbf 23}  (6), \mbox{\BPGS\ 505--513}.

\bibitem[\protect\BCAY{Umetani \BBA\ Yagiura}{Umetani \BBA\
  Yagiura}{2007}]{umetani07}
Umetani, S.\BBACOMMA\ \BBA\ Yagiura, M. \BBOP 2007\BBCP.
\newblock \BBOQ Relaxation Heuristics for the Set Covering Problem.\BBCQ\
\newblock {\Bem Journal of the Operations Research Society of Japan}, {\Bbf
  50}, \mbox{\BPGS\ 350--375}.

\bibitem[\protect\BCAY{Wilcoxon}{Wilcoxon}{1945}]{wilcoxon45}
Wilcoxon, F. \BBOP 1945\BBCP.
\newblock \BBOQ Individual Comparisons by Ranking Methods.\BBCQ\
\newblock {\Bem Biometrics Bulletin}, {\Bbf 1}  (6), \mbox{\BPGS\ 80--83}.

\bibitem[\protect\BCAY{Yamada, Kataoka, \BBA\ Watanabe}{Yamada
  et~al.}{2002}]{yamada02}
Yamada, T., Kataoka, S., \BBA\ Watanabe, K. \BBOP 2002\BBCP.
\newblock \BBOQ Heuristic and Exact Algorithms for the Disjunctively
  Constrained Knapsack Problem.\BBCQ\
\newblock {\Bem Journal of Information Processing}, {\Bbf 43}  (9),
  \mbox{\BPGS\ 2864--2870}.

\bibitem[\protect\BCAY{Yih, Goodman, Vanderwende, \BBA\ Suzuki}{Yih
  et~al.}{2007}]{yih07}
Yih, W.-t., Goodman, J., Vanderwende, L., \BBA\ Suzuki, H. \BBOP 2007\BBCP.
\newblock \BBOQ Multi-document Summarization by Maximizing Informative
  Content-words.\BBCQ\
\newblock In {\Bem IJCAI'07: Proceedings of the 20th international joint
  conference on Artifical intelligence}, \mbox{\BPGS\ 1776--1782}.

\bibitem[\protect\BCAY{横野\JBA 奥村}{横野\JBA 奥村}{2010}]{yokono10}
横野光\JBA 奥村学 \BBOP 2010\BBCP.
\newblock テキスト結束性を考慮したentity gridに基づく局所的一貫性モデル.\
\newblock \Jem{自然言語処理}, {\Bbf 17}  (1), \mbox{\BPGS\ 161--182}.

\end{thebibliography}



\appendix
\section{評価情報の抽出方法}

まず，評価情報について述べる．
西川らの提案 \cite{nishikawa13} と同様に，本論文では，評価情報を評価属性 $\mathit{aspect}$ と評価極性 $\mathit{polarity}\in \{-1,0,1\} $  の組 $ e = (\mathit{aspect}, \mathit{polarity})$ として考える．
評価属性は，何らかの対象が評価される際の観点を示す．
評価極性は，対象が評価属性に関してポジティブな評価をされているときに $ 1 $，ネガティブな評価をされているときに $ -1 $，どちらとも言えないときに $ 0 $ の3 値を取るものとする．
一例として，「このデジタルカメラは画質がよい」という表現を考える．
この表現の評価属性は「画質」である．
また，評価表現「よい」はポジティブな評価であることから，評価極性は $ 1 $ となる．
そのため，この表現から評価情報 $ e = (\text{画質}, 1) $ が得られる．

評価情報は以下のように抽出する．
\begin{enumerate}
\item 文に係り受け解析を行う．
\item 評価表現とその評価極性の組を格納した辞書（評価表現辞書）と係り受け解析の結果を照合し，評価表現とその評価極性を得る．
\item 係り受け木で，評価表現に係っている名詞を評価属性とする．
\item 得られた評価属性と評価極性を出力する．
\end{enumerate}



\begin{biography}
\bioauthor{西川　　仁}{
2006年慶應義塾大学総合政策学部卒業．2008年同大学大学院政策・メディア研究科修士課程修了．同年日本電信電話株式会社入社．現在NTTメディアインテリジェンス研究所研究員．2012年より奈良先端科学技術大学大学院博士後期課程在学中．自然言語処理の研究開発に従事．言語処理学会，情報処理学会，人工知能学会，ACL各会員．
}
\bioauthor{平尾　　努}{
1995年関西大学工学部電気工学科卒業．1997年奈良先端科学技術大学院大学情報科学研究科博士前期課程修了．同年株式会社NTTデータ入社．2000年よりNTTコミュニケーション科学基礎研究所に所属．博士（工学）．自然言語処理の研究に従事．言語処理学会，情報処理学会，ACL各会員．
}
\bioauthor{牧野　俊朗}{
1987年東京大学工学部電子工学科卒業，1992年同大学院博士課程修了．同年日本電信電話株式会社入社．現在NTTメディアインテリジェンス研究所主幹研究員．博士（工学）．知識獲得，推論手法，自然言語処理などに関する研究開発に従事．
}
\bioauthor{松尾　義博}{
1988年大阪大学理学部物理学科卒業．1990年同大学大学院研究科博士前期課程修了．同年日本電信電話株式会社入社．現在NTTメディアインテリジェンス研究所音声・言語基盤技術グループリーダ．機械翻訳，自然言語処理の研究に従事．言語処理学会，情報処理学会各会員．
}
\bioauthor{松本　裕治}{
1977年京都大学工学部情報工学科卒業．1979年同大学大学院工学研究科修士課程情報工学専攻修了．同年電子技術総合研究所入所．1984〜85年英国インペリアルカレッジ客員研究員．1985〜87年財団法人新世代コンピュータ技術開発機構に出向．京都大学助教授を経て，1993年より奈良先端科学技術大学院大学教授，現在に至る．工学博士．専門は自然言語処理．言語処理学会，情報処理学会，人工知能学会，認知科学会，AAAI，ACL，ACM各会員．情報処理学会フェロー．ACL Fellow．
}
\end{biography}



\biodate


\end{document}
