\documentclass[tombow,japanese]{jnlp_2.3}
\usepackage{jnlpbbl_1.3}
\usepackage[dvipdfm]{graphicx}
\usepackage{gentombow}
\usepackage{amsmath}
\settombowbleed{5mm}
\usepackage{hangcaption_jnlp}
%%%%\usepackage{udline}
%%%%\setulminsep{1.2ex}{0.2ex}
%%%%\let\underline=\ul
\newcommand{\Hyp}{-}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% author's definition
%%%%\usepackage{latexsym}
%%%%\usepackage{amsmath}
\usepackage{multirow}
\usepackage{amssymb}
%%%%\usepackage{algorithm}
%%%%\usepackage{algorithmic}
\usepackage{tabularx}
%%%%\usepackage{booktabs}
%%%%\usepackage{color}
%%%%\usepackage{setspace}
%%%%\usepackage{comment} 
\usepackage{url}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand\UrlFont{\rmfamily}


\Volume{27}
\Number{2}
\Month{June}
\Year{2020}
%%%%\Issuetitle{「　　　　」特集号}

\received{2019}{9}{30}
\revised{2019}{12}{19}
%%%%\rerevised{2006}{5}{6}
\accepted{2020}{2}{4}

\setcounter{page}{169}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\jsubject{一般論文}
\jtitle{抽出型オラクル要約の人手評価}
\jauthor{平尾　　努\affiref{Author_1} \and 西野　正彬\affiref{Author_1} \and 永田　昌明\affiref{Author_1}}
\jabstract{%
本稿では，抽出型要約手法におけるオラクル要約，すなわち自動評価スコアを最大化する要約を生成するための整数計画問題による定式化を示し，抽出型要約システムが到達可能な自動評価スコアの上限値を明らかにする．そして，オラクル要約の妥当性を検証するため，ピラミッド法と Document Understanding Conference (DUC) で利用されたQuality Questions を用いて内容と言語品質の双方の観点から人手評価を行う．文抽出，Elementary Discourse Unit (EDU) 抽出，根付き部分木抽出の3種の抽出型要約手法を対象とし，Text Analysis Conference (TAC) 2009/2011 のデータセットを用いて ROUGEと BasicElements (BE) を最大化するオラクル要約を生成してそれらを評価した．その結果，抽出型オラクル要約の自動評価のスコア，ピラミッド法による評価スコアは現状の要約システムのスコアよりも明らかに優れていることがわかった．一方，言語品質に関しては現状の要約システムと差がない，あるいは劣る結果となった．これらより，抽出だけでもまだ良い要約を生成できる余地がある一方，言語品質を改善する必要が明らかとなった．
}
\jkeywords{オラクル要約，抽出型要約，整数計画問題}

\etitle{Manual Evaluations of Extractive Oracle Summaries}
\eauthor{Tsutomu Hirao\affiref{Author_1} \and Masaaki Nishino\affiref{Author_1} \and Masaaki Nagata\affiref{Author_1}} 
\eabstract{
In this paper, we derive the Integer Linear Programming (ILP) formulations to obtain extractive oracle summaries to reveal the upper bound automatic score of the extractive summarization paradigm. Then, we manually evaluate the oracle summaries in terms of the pyramid method and Quality Questions to assess the validity of the oracle summaries. We evaluated three kinds of extractive oracle summaries, sentence extraction, Elementary Discourse Unit (EDU) extraction, and subtree extraction, against ROUGE and Basic Elements (BE) on Text Analysis Conference (TAC) 2009/2011 data sets. The results demonstrated the pyramid scores and automatic scores of the oracle summaries are quite high, but the linguistic quality of them is not so good. The results imply that we can generate informative summaries by extraction, but we have to improve the linguistic quality of the summaries.
}
\ekeywords{Oracle Summaries, Extractive Summarization, Integer Linear Programming}

\headauthor{平尾，西野，永田}
\headtitle{抽出型オラクル要約の人手評価}

\affilabel{Author_1}{日本電信電話株式会社 コミュニケーション科学基礎研究所}{NTT Communication Science Laboratories}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{はじめに}

流暢な文の生成を可能にするニューラルネットワークによる系列
変換モデル \cite{Sutskever:2014,BahdanauCB14} の発展は，
文生成を利用する自然言語処理タスクに大きな恩恵をもたらした．
文書要約タスクも例外ではなく，\citeA{D15-1044} 以降，
系列変換モデルを用いた生成型要約 (abstractive summarization) の研究が
盛んに行われており，ヘッドライン生成，単一文書要約ではそれが
顕著である．
一方，文書の一部を抜き出すことで要約を生成する
抽出型要約\footnote{本稿では，文抽出と文圧縮を統合した圧縮型要約 (compressive summarization) も抽出型要約とみなす．} (extractive summarization) の研究は脈々と続いている
ものの生成型要約の研究と比較すると数は少なくなってきた．
たとえば，2019年開催の第57回 Association for Computational Linguistics
(ACL) では，抽出型要約手法に関する発表は約5件であったが生成型要約手法に
関する発表は約15件であり，生成型要約手法に注目が集まっていることがよく
わかる．
このように自動要約研究の主流は抽出から生成へと移り変わりつつある．
では，抽出型要約は終わってしまった研究，すなわち，継続する価値のない
研究なのだろうか？
この疑問に答えるためには，
抽出型要約手法の上限，つまり抽出型要約で
どれほど人間の要約に近づけるかを知る必要がある．
抽出型要約手法の上限が十分高い水準にあるのならば，研究を続ける価値が
あるし，そうでないのならば続ける価値はない．
自動要約手法のパラダイムが移りつつあるいまだからこそ，
抽出型要約手法の上限を明らかにすることは
自動要約研究の今後の発展に大きな意味を持つと考える．

本稿では人間が生成した参照要約に
対する自動評価スコアを最大化する抽出による要約，すなわち
抽出型オラクル要約を上限の要約とみなす．
そして，それを得るための整数計画問題による定式化を提案し，
自動評価という観点から
抽出型要約手法の到達点を調べる．
次に，その妥当性をより詳細に検証するため，ピラミッド法
\cite{nenkovau:2004:HLTNAACL,Nenkova:2007}，Document Understanding
Conference (DUC)\footnote{\url{https://duc.nist.gov}} で用いられた
Quality Questions \cite{qqduc06} を用いて内容と言語品質の両側面から
人手で評価し，それが人間にとってどの程度良い要約なのかを検証する．

Text Analysis Conference (TAC)\footnote{\url{https://tac.nist.gov}} 2009/2011 のデータ
セットを用いて，自動評価指標であるROUGE-2 \cite{rouge3}，
Basic Elements (BE) \cite{hovy06} に対する文抽出，Elementary
Discourse Unit (EDU) 抽出，根付き部分木抽出の3種の
抽出型オラクル要約を
生成し，上記の観点でそれらを評価したところ，
(1) 自動評価スコアはいずれの抽出型オラクル要約も
非常に高く，
現状のシステム要約のスコアと比較すると差が大きいことが
わかった．
(2) ピラミッド法による評価結果
から，
要約の内容評価という点でも優れていることがわかった．
(3)しかし，Quality Questions による言語品質
評価の結果は，現状の要約システムと大差ない，
あるいは劣る結果となった．
これらより，抽出型要約手法で重要情報に富んだ要約を
生成できることが明らかとなった．
つまり，抽出型要約は今後も続けていく価値のある研究であることが示された．
その一方，言語品質には改善の余地があること
も明らかとなった．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{抽出型オラクル要約の定義}

オラクル要約とは参照要約にもっとも類似し，かつシステムが生成可能な要約を
指す．生成型要約の場合，その要約生成の仕組みに一切の制約がないため，
実際にそれが生成可能かどうかの議論はあるが，オラクル要約は参照要約そのも
のになる．一方，抽出型要約は原文書中のテキストユニットを切り貼りして要約
を生成するため，参照要約を再現することは基本的には不可能である．よって，
抽出型オラクル要約（以降，オラクル要約）は参照要約との間の類似尺度を最大化
する原文書中のテキストユニットの集合と定義できる．
一般的には，ROUGEやBEなどの自動評価指標が類似尺度として利用されるので，
自動評価指標(ROUGE-2/BE)を$f()$，
参照要約の集合を${\cal R}$，原文書における
テキストユニット集合を${\cal D}$とすると，オラクル要約は以下の定義となる．
\begin{equation}
\label{def:oracle}
\begin{split}
O = & \displaystyle\mathop{\rm argmax}_{S \subseteq {\cal D}} f({\cal R},S),\\
\text{subject~to} \quad & \ell(S) \le L.
\end{split}
\end{equation}
$\ell()$は要約の長さを返す関数であり，$L$はあらかじめ与えられた要約長である．
そして，$f()$ は以下の式で与えられる．
\begin{equation}
\label{rouge}
f({\cal R},S)=
\frac{\sum_{i=1}^{|{\cal R}|}\sum_{j=1}^{|U_{\cal R}|}\min\{N(u_j,R_i),N(u_j,
 S)\}}{\sum_{i=1}^{|{\cal R}|}\sum_{j=1}^{|U_{\cal R}|} N(u_j,R_i)}.
\end{equation}
$U_{\cal R}$は自動評価スコアの計算に利用する基本ユニットの参照要約全体に
おける集合である．ROUGE-2であ
ればバイグラム集合，BEであれば依存関係にある単語対とその関係ラベルからなるタプル集
合をあらわす．$u_j$はその$j$番目の要素である．
$N(u_j,R_i)$は$u_j$の
$R_i$における頻度，$N(u_j,S)$は$u_j$の$S$における頻度である．
式(2)の分母は$S$に依存しないため，分子
を最大化すればオラクル要約を得ることができる．
式(2)より，関数$f()$の分子は$u_j$の重みを$S$にお
ける頻度$N(u_j,S)$と$R_i$における頻度$N(u_j,R_i)$のどちらか小さい方と
して，すべてのユニットに対してその和を計算したものである．
よって式(1)の最適化問題は，$N(u_j,R_i)$があらかじめ決まった値であること
を考慮すると，長さ制約のもと，ユニット$u_j$の被覆
回数を$N(u_j,R_i)$まではカウントしつつその和を最大化するよう${\cal D}$の
部分集合$S$を選択する問題となる．これは一種の Max-$k$-Cover 問題であり，
NP困難であることが示されている \cite{Feige:1998,Feige:2011}\footnote{ROUGEが劣モジュラ関数であることがLin ら \citeyear{hlin11} によって証明されており，劣モジュラ関数の最大化がNP困難であることが Feige ら \citeyear{Feige:2011}によって示されていることから，式(1)の最適化問題がNP困難であるということもできる．}．
そして，この問題に対し疑多項式時間で厳密解を得ることのでき
るアルゴリズムが知られていないことから，
本稿では整数計画問題による定式化を提案し，
ソルバを利用することでオラクル要約を生成する．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{整数計画問題によるオラクル要約の生成の定式化}

本稿では，文抽出，EDU
抽出，根付き部分木抽出の3種の抽出型オラクル要約
を生成するための整数計画問題による定式化を提案する．
オラクル要約を得るための自動評価指標としては，TACの公式指標として
用いられた ROUGE-2 と
BE を利用する．よって，スコア計算の基本ユニットは
バイグラム，係り受け関係にある2つの単語と関係ラベルのタプルとなる．
なお，以下の定式化では原文中の文，EDU，チャンク（依存構造木の
ノード），単語にはユニークなインデックスが割り当てられていることを
想定している（図\ref{ex} 参照）．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 1
\begin{figure}[b]
\begin{center}
\includegraphics{27-2ia1f1.eps}
\end{center}
\caption{単語，チャンク，EDU，文の関係．実線矢印はチャンク間の係り受け関係をあらわす．}
\label{ex}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{文抽出によるオラクル要約}

文抽出型要約は広く利用される要約手法である．
もっとも古典的な手法であり，
1958年よりその研究が始まったと言われている \cite{Luhn:1958}．
文抽出によるオラクル要約を得るための整数計画問題による定式化は
以下となる．
{\allowdisplaybreaks
\begin{eqnarray}
  \text{maximize} &\textstyle \sum_{i=1}^{|{\cal R}|}
  \sum_{j=1}^{|U_{\cal R}|} z_{i,j}& \\
 \text{subject to}  & N(u_j,R_i) \ge z_{i,j}  &\forall i,j\\
 &  \sum_{p \in V_{u_j}} t_p \ge z_{i,j}  &\forall i,j\\
&   s_{\text{id}(p)} \ge t_p  &\forall p \in {V_{u_j}}\\
& \sum_{k=1}^{|{\cal D}|}\ell_k s_k \le L\\
&  s_k \in \{0,1\}  & \forall k \\
&  t_p \in \{0,1\}  & \forall p \\
&  z_{i,j} \in \mathbb{Z}_{\ge 0} & \forall i,j
\end{eqnarray}
}%
式(3)は式(2)の分子を最大化するための目的関数であり，
解として得られる$z_{i,j}$は式(2)における$\min(N(u_j,R_i),N(u_j,S))$と
一致する．
ここで，$z_{i,j}$が$u_j$の$i$番目の参照要約における頻度と
要約$S$における頻度のうち，小さい方の値をとるようにするための
制約が式(4)と(5)である．
式(4)より，
$z_{i,j}$は$u_j$の$i$番目の参照要約における頻度よりも
小さいことが保証され，
式(5)より，$z_{i,j}$は原文書における$u_j$の頻度よりも
小さいことが保証される．したがって，$z_{i,j}$は
$i$番目の参照要約における$u_j$の頻度，
原文書における$u_j$の頻度の双方よりも小さい値をとる．
なお，原文書における$u_j$のすべての出現をその左側の単語の出
現位置をあらわすインデックスと右側の単語の出現位置をあらわすインデックスの
ペアの集合$V_{u_j}$としてあらわす．
$t_p$は0/1変数であり，$t_p=1$のときに
$V_{u_j}$中の単語の出現位置インデックスペア$p$に対応する
基本ユニットがオラクル要約に採用される．
id($p$)は，$p$に対応する基本ユニットが
出現する文番号を返す関数であり，
式(6)は基本ユニットと文の間の依存関係を
あらわす．$t_p=1$のときには，$p$に対応する
基本ユニットを含むid($p$)の文がオラクル要約に採用される．
すなわち任意の文を
オラクル要約に採用するか否かをあらわす
0/1変数$s_{{\rm id}(p)}$が1となる．
式(7)はオラクル要約の長さ制約をあらわし，
$\ell_k$は$k$番目の文の長さ，ここでは単語数を
あらわす．$L$はあらかじめ与えられた単語数の上限をあらわす．
なお，$\mathbb{Z}_{\ge 0}$は非負整数集合をあらわす．

図\ref{ex} の例を用いて説明する．
いま，$u_j$ として ``and live''
というバイグラムを考える．このバイグラムは
単語インデックス
(6,7)と(17,18)に出現しているので
 $V_{u_j}{=}\{(6,7),(17,18)\}$となる．$t_{(6,7)}=1$のときには，
``and$_{6}$ live$_{7}$''
がオラクル要約に採用され，$\text{id}(6,7)=1$より，$s_1$が
オラクル要約に採用される．
同様に，
$t_{(17,18)}=1$のときには，
``and$_{17}$ live$_{18}$''
がオラクル要約に採用され，
$\text{id}(17,18)=2$より，$s_2$がオラクル要約に採用される．
この整数計画問題をソルバを用いて解いた後，
$s_k=1$となる文を集めれば文抽出によるオラクル要約を
得ることができる．

なお，ROUGE-2ではなく BE に対するオラクル要約を得る時には，$u_j$の出現に対応
する単語インデックスペアが
連続するとは限らないだけで，それ以外にROUGE-2の場合との違いはない．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{EDUの抽出によるオラクル要約}


Elementary Discourse Unit (EDU) とは，Rhetorical Structure Theory (RST) \cite{mann88} における
修辞構造木の葉であり，およそ節に相当する．よって EDU は多くの場合
文よりも小さい．
\citeA{W16-3617} はピラミッド法 \cite{Nenkova:2007} における Summary Content 
Unit (SCU) （詳細は後述する）が EDU とよく一致することをヒントに
EDU抽出による要約手法(near-extractive summarizatioon)
を提案し，その有効性を示した．
EDU抽出によるオラクル要約生成は基本的には文抽出によるオラクル要約生成と同じであるが，
それが文よりも小さいテキストユニットであるため，いくつかの制約を追加する必要がある．
EDU抽出によるオラクル要約を得るための整数計画問題による定式化は以下となる．
{\allowdisplaybreaks
\begin{eqnarray}
 \text{maximize} & 
  \textstyle \sum_{i=1}^{|{\cal R}|}\sum_{j=1}^{|U_{\cal R}|}
  z_{i,j}{-}\sum_{k=1}^{|{\cal D}|}s_k&\\
 \text{subject to}  & N(u_j,R_i) \ge z_{i,j}  &\forall i,j\\
&  \sum_{p \in V_{u_j}} t_p \ge z_{i,j} & \forall i,j\\
&  e_{\text{left}_e(p)} \ge t_p & \forall p \in V_{u_j}\\
&  e_{\text{right}_e(p)} \ge t_p & \forall p \in V_{u_j}\\
& e_g \le 1 - t_p &  \forall g \in D_p, ~\forall p \in V_{u_j}\\
& s_{\text{id}(n)} \ge e_n &  \forall n\\
&\sum_{n=1}^{|{\cal E}|}\ell_n e_n \le L\\
  &  \kern-3em t_p \in \{0,1\}~\displaystyle\forall p &    e_n \in \{0,1\}~\displaystyle\forall n\\
  & \kern-3em  s_k \in \{0,1\}~\displaystyle\forall k &   z_{i,j} \in
   \mathbb{Z}_{\ge 0}~\displaystyle\forall i,j
\end{eqnarray}
}%
EDUのような文よりも小さいユニットを抽出することでオラクル要約を
生成する場合，抽出に何らかの制約を導入しなければ，
バイグラム，係り受け関係にある単語対をカバーするよう多くの文から
ばらばらにEDUが抽出される．
すると，ROUGE-2/BE は高いものの断片化された可読性の
低いオラクル要約となってしまう．
これを避けるため，Morita ら \citeyear{moritaACL2013} にならい，目的関数(3)にペナルティを導入し，選択したEDUの元となる文の数が
なるべく少なくなるようにする．式(11) の第2項は抽出したEDUが属する文の異なり数をあらわすので，
多くの文からEDUを抽出する場合には目的関数の値が小さく，少ない文からEDUを抽出する場合には
目的関数の値が大きくなるようになる．
式(12)，(13)は文抽出の場合と同様で式(2)の分子を表現するための制約である．
式(14)，(15)は単語インデックスペアとEDUインデックスとの依存関係を
あらわしており，
$\text{left}_e(p)$，
$\text{right}_e(p)$は，ペアの左側の単語インデックスが
属するEDUのインデックス，
右側の単語インデックスが属するEDUのインデックスである．
すなわち，インデックスペアが$p$であるバイグラムをオラクル要約に
採用するとき，
その左側の単語が属するEDUと
その右側の単語が属するEDUを同時にオラクル要約に採用する
ことを示す．
さらに，EDUという文よりも小さなユニットを抽出するため，
原文書ではスキップのあるバイグラムをオラクル要約では
単なるバイグラムとして採用する
ことができる．
つまり，任意のEDUの最後の単語とそれよりも右側のEDUの最初の単語で
構成される原文書中の
スキップバイグラムはオラクル要約ではバイグラムとして採用可能である．
ただし，その際には左右の単語を含むEDUに挟まれたEDUはオラクル要約に採用できない．
式(16)はその制約をあらわしており，$D_p$は単語インデックスペアの左側の単語が属する
EDUのインデックスと右側の単語が属するEDUのインデックスに挟まれたEDUインデックスの
集合をあらわす．つまり，$D_p=\{\text{left}_e(p)+1,\ldots,\text{right}_e(p)-1\}$である．
式(17)は長さ制約をあらわしており，$\ell_n$は$n$番目のEDUの単語数，${\cal E}$は
原文書中のEDUの集合をあらわす．


図\ref{ex} の例で説明する．$u_j$ として
``amphibians and''というバイグラムを考える．
スキップを許すと図の例では
(2,6)，(12,13)，(12,17)，(22,26)という4つの単語インデックスペアがそれに
該当する．ここで，(2,6)と(12,17)はEDUの最後の単語と最初の単語で構成される
スキップバイグラムではないことからオラクル要約に採用することはできないの
で無視する．
よって，$V_{u_j}{=}\{(12,13),(22,26)\}$となる．``amphibians$_{12}$ and$_{13}$''
をオラクル要約に採用する時，2つの単語を含むEDUは連続して
いるため，
$D_{(12,13)}=\phi$となる．$\text{left}_e(12,13)=3$，$\text{right}_e(12,13)=3$より，
インデックスが3であるEDUのみがオラクル要約に採用される．
そして，id(3)=2より，
$s_2=1$となる．
一方，``amphibians$_{22}$ and$_{26}$''をオラクル要約に
採用するとき，
$\text{left}_e(22,26)=5$，$\text{right}_e(22,26)=7$より，
2つのEDUに挟まれたEDUのインデックスが6であることから，
$D_{(22,26)}=\{6\}$となる．
よって，インデックス5と7のEDUがオラクル要約に同時に採用され，
インデックス6のEDUは採用されない．
また，$\text{id}(5)=\text{id}(7)=3$より，
$s_3=1$となる．
整数計画問題を解いた後，$e_n{=}1$となるEDUを集めることで
EDU抽出によるオラクル要約を得ることができる．

なお，ROUGE-2ではなくBEに対してオラクル要約を生成する時，
係り受け関係にある単語対が連続して出現する必要がないため，
式(16)
を無視すればよい．それ以外はROUGE-2の場合と同じである．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{根付き部分木の抽出によるオラクル要約}

根付き部分木の抽出による要約は圧縮型要約(compressive summarization)
\cite{martins-smith09,kirkpatrick11,Almeida13} とも呼ばれ，文抽出と文圧
縮を統合した要約手法である．文書中の文は
構文木として表現され，その根付き部分木を抽出することで要約を生成する．
構文木としては句構造木，依存構造木の双方とも用いられるが，
本稿では依存構造木を利用する．なお，依存構造木は 
\citeA{filippova:2013} のルールに従い，単語の依存関係でなくフレーズをチャンクとする
チャンク間の依存構造へと変換しておく．
根付き部分木抽出によるオラクル要約生成を得るための
整数計画問題による
定式化は以下の式となる．
{\allowdisplaybreaks
\begin{eqnarray}
\text{maximize}&
\textstyle \sum_{i=1}^{|{\cal R}|}\sum_{j=1}^{|U_{\cal R}|}
  z_{i,j}{-}\sum_{k=1}^{|{\cal D}|}s_k&\\
 \text{subject to}  & N(u_j,R_i) \ge z_{i,j}  &\forall i,j\\
&  \sum_{p \in V_{u_j}} t_p \ge z_{i,j} & \forall i,j\\
&  c_{\text{left}_c(p)} \ge t_p & \forall p \in V_{u_j}\\
&  c_{\text{right}_c(p)} \ge t_p & \forall p \in V_{u_j}\\
& c_g \le 1 - t_p &  \forall g \in D_p, ~\forall p \in V_{u_j}\\
& s_{\text{id}(n)} \ge c_n &  \forall n\\
& c_{\text{parent}(n)} \ge c_n &  \forall n\\
& \sum_{n=1}^{|{\cal C}|}\ell_n c_n \le L\\
  &  t_p \in \{0,1\}~\displaystyle\forall p  &
   c_r \in \{0,1\}~\displaystyle\forall r \\
  &  s_k \in \{0,1\}~\displaystyle\forall k &
     z_{i,j} \in \mathbb{Z}_{\ge 0}~\displaystyle\forall i,j.
\end{eqnarray}
}%
EDU抽出によるオラクル要約生成の定式化とほぼ同等であり，
式(21)--(23)までは同じである．left$_c$($p$)は$p$に
対応するバイグラムの
左側の単語が属するチャンクのインデックス，
right$_c$($p$)は右側の単語が属するチャンクのインデックス
であり，$c_n$は$n$番目のチャンクをオラクル要約に
採用する場合に1，そうでない場合に0をとる0/1変数である．
式(24)，(25)より，$p$に対応するバイグラムをオラクル要約に
採用する場合，左側の単語が属するチャンクと右側の単語が
属するチャンクの双方を同時にオラクル要約に採用しなければ
ならない．そして，2つのチャンクが連続していない場合には
それらに挟まれたすべてのチャンクをオラクル要約に採用しない．
式(26)がその制約であり，
$D_p=\{\text{left}_c(p)+1,\ldots,\text{right}_c(p)-1\}$が
左側の単語が属するチャンクと右側の単語が属するチャンクに
挟まれたチャンクの集合をあらわす．
式(27)はチャンクと文の依存関係をあらわし，$n$番目のチャンクを
オラクル要約に採用すると，それを含む文に対応する
0/1変数$s_{\text{id}(n)}$
が1となる．式(28)は抽出したチャンクが文の依存構造木の
根付き部分木となるための制約である．
$n$番目のチャンクをオラクル要約に採用すると，
その依存構造木における親のチャンクである$c_{\text{parent}(n)}$
もオラクル要約に採用される．式(29)はオラクル要約の長さ
制約をあらわし，$\ell_n$は$n$番目のチャンクの長さ，
${\cal C}$は原文書中のチャンク集合をあらわす．

図\ref{ex} の例を用いて説明する．
 $u_j$ として``amphibians have''という
バイグラムを考える．
スキップ\footnote{EDU抽出と同じく，チャンクの最後の単語とそれより右のチャンクの最初の単語からなるスキップバイグラムのみを考える．}も考慮した上で``amphibians have''となる
単語インデックスペアは(2,3)，(12,15)，(22,28)であるから，
$V_{u_j}{=}\{(2,3),(12,15),(22,28)\}$となる．
``amphibians$_2$ have$_3$''をオラクル要約に採用するとき，
$\text{left}_c(2,3)=1$，
$\text{right}_c(2,3)=2$より，
$D_{(2,3)}=\phi$となるので，$c_1$，$c_2$を同時にオラクル要約に採用するだけでよい．
そして，$\text{id}(1)=\text{id}(2)=1$より，$s_1=1$となる．
また，$\text{parent}(1)=2$，$\text{parent}(2)=\text{Root}$なので，
式(28)の制約によって新たに採用するチャンクは存在しない．
``amphibians$_{12}$ have$_{15}$''をオラクル要約に採用するとき，
$\text{left}_c(12,15)=9$，
$\text{right}_c(12,15)=11$より，
$D_{(12,15)}=\{10\}$となり，$c_{9}$，$c_{11}$を同時にオラクル要約
に採用し，
$c_{10}$を採用しない．
そして，$\text{id}(9)=\text{id}(11)=2$より，$s_2=1$となる．
また，$\text{parent}(12)=15$，$\text{parent}(15)=\text{Root}$であるから
式(28)の制約によって新たに採用するチャンクは存在しない．
``amphibians$_{22}$ have$_{28}$''をオラクル要約に採用するには，
$c_{16}$と$c_{21}$を同時にオラクル要約に採用し，$c_{17}$から
$c_{20}$までを採用しない．
そして，$s_3=1$となり，式(28)の制約によって
新たに採用するチャンクも存在しない．
この整数計画問題を解いた後，$c_n=1$となるチャンクを集めることで
根付き部分木抽出によるオラクル要約を得ることができる．

BE の場合には，EDU抽出によるオラクル要約生成の場合と同じく係り受け関係にある
チャンク
が連続する必要はないため，
ユニットの左側の単語が属するチャンクと右側の単語が属するチャンクに挟まれたチャンク集合を
削除する必要はない．よって，式(26)を無視する．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{人手評価の方法}

オラクル要約の妥当性を
調べるため，内容と言語品質という2つの観点からそれぞれ人手で評価を行う．
以下，内容評価に用いたピラミッド法，言語品質評価に用いた Quality Questionsに
ついて説明する．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ピラミッド法による内容評価}

ピラミッド法 \cite{nenkovau:2004:HLTNAACL,Nenkova:2007} は，要約の内容評価を
評価者の直感に頼らず，根拠をもって評価する手法である．
ピラミッド評価では1つの要約課題に
対して複数の参照要約が与えられることが前提となっており，
それらに基づきピラミッドを構築するステップと
構築したピラミッドに基づき評価対象要約のスコアを決定するステップからなる．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 2
\begin{figure}[b]
\begin{center}
\includegraphics{27-2ia1f2.eps}
\hangcaption{SCUとそれに対応するcontributorsとラベルの例．トピックID``D0928'', ``Trials of Tyco's Dennis Kozlowski''より．}
\label{SCU}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

まず，評価者はそれぞれの参照要約から
Summary Content Unit (SCU)と呼ばれるユニットを同定し，それに言及する
参照要約の数でその重みを決定する．
SCU は参照要約内で言及される事象であり，節相当のユニットである．
図\ref{SCU} にSCUの例を示す．図中のCon.はcontributor と呼ばれ，SCUに対応する
参照要約中の実際の文字列である．
Label はContributorに対して人間が割り当てた
簡潔なラベルである．
図の上段の4つのcontributor，下段の3つのcontributorはそれぞれ
同じ意味を持つ．また，上段のSCUはcontributorの数が4であることから
その重みは4となり，下段のSCUの重みは3である．
つまり，$K$個の参照要約が与えられた場合，SCUが取りうる最大の重みは$K$であり，
最小の重みは1となる．
一般的にSCUの重みが大きくなると異なるSCUの数は少なくなり，
小さくなると異なるSCUの数が多くなる．
これを図示するとピラミッド（三角形）を
想起させることからピラミッド法と名付けられた．

次に，評価対象要約に対しても同様にSCUを同定し，ピラミッドのSCUと
評価対象要約のSCUの対応関係を決定した後，
評価スコアを以下の式で決定する．
\begin{equation}
\text{Pyr}({\cal R},S)=\frac{\sum_{e_r \in {\cal R}} \sum_{e_s \in S}W(e_r) b(e_r,e_s)}{\sum_{e_k \in {\cal R}_{\text{top{-}$M$}}} W(e_k)}    
\end{equation}
$e_r$はピラミッドのSCU，
$e_s$は評価対象要約のSCUをあらわし，
$W()$はSCUの重みを返す関数，
$b(e_r,e_s)$は2つのSCUの間に
対応関係が与えられていれば1，そうでなければ0を返す関数である．
また，${\cal R}_{\text{top{-}$M$}}$は，ピラミッドの重みが上位$M$件の
SCUの集合であり，$M$は，参照要約中の平均SCU数である．
式(32)より，要約の人手評価でよく用いられる5段階評価などとは異なり，
ピラミッドというスコア決定の基準が与えられるため，その評価には
客観性が
期待できる．しかし，何をSCUとするのか，ピラミッド中のSCUと
評価対象要約との間のSCUが意味的に一致するかどうかについては評価者
によって判断が揺れることがありえる．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Quality Questionsによる言語品質評価}

要約の言語品質には，DUC で提案されたQuality Questions \cite{qqduc06} を
利用した．
表\ref{qq} に詳細を示す．Grammaticalityは可読性に影響を与える
文レベルでの文法ミスを評価する．Non-redundancyは，事象の繰り返しや
固有表現の繰り返しなど冗長な表現を評価する．
Referential clarityは，参照表現が指す実体が要約中に含まれるかを
評価する．Focusは要約の焦点が定まっているか，
Structure and Coherence は要約の構成，結束性を評価する．
いずれの観点も5段階（5が最高）で評価する．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 1
\begin{table}[t]
\caption{言語品質評価のための Quality Questions}
\label{qq}
\input{01table01.tex}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{実験}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{設定}

最大化する自動評価指標には，ROUGE-2 と BE を採用し，
TAC-2009/2011 の複数文書要約タスクのデータセットに対し3種の抽出型オラク
ルを生成する．
それぞれのデータセットには44トピック（文書セット）が与えられ，
各トピックには新聞記事が10記事，参照要約が4つ含まれる．
なお，要約システムは各トピックに対し100単語以内で要約を
生成することが求められるのでオラクル要約の長さの上限も
100単語となる．

また，EDU抽出によるオラクル要約を生成するため，
3層の双方向LSTMを用いた
セグメンタを実装し，RST Discourse Treebank (RST DT) \cite{rstdtb} を
用いて訓練した．EDU境界の認定性能はRST DTのテストセットでF値が0.9程度である．
根付き部分木抽出によるオラクル要約の生成のため，Stanford Parser
\cite{stanford06} を用いて単語依存構造木を構築し，
Filippova ら \citeyear{filippova:2013} のルールを用いて
チャンク間の依存構造木へと変換した．

比較評価のため，TAC-2009 で最も良い成績を残した
システム {\tt peer\_40} \cite{gillick:tac:09}\footnote{圧縮型要約要約システム \cite{gillick-favre:2009:ILPNLP} に対し，精度を重視した文圧縮，文境界認定の改善，要約対象候補文の絞り込みを導入したシステム．}，
TAC-2011で最も良い成績を残したシステム {\tt peer\_22} \cite{tac11best}\footnote{単語の被覆に対してある程度の冗長性を許すように拡張した最大被覆問題を解くことで文を抽出するシステム．}を評価対象に含めた．また，
TAC-2009に対しては，人間による文抽出{\sc HexTac}も
評価対象とした．{\sc HexTac}は各トピックに対し5名の被験者が文抽出により
要約を生成した後，それらの多数決で要約を生成する手法である．被験者は
計算機科学分野の研究者である．

なお，ピラミッド評価の際には，TAC-2009/2011 で作成されたピラミッドを再利用し，
評価対象要約におけるSCUの同定および
既存ピラミッドのSCUと評価対象要約のSCUの対応付け
のみを新たに行った．なお，1トピックあたりの参照要約数は4なので，SCU の重みの最
大値は4である．対応付け，スコア計算には
ピラミッド評価ツール {\tt DUCView-1.4.jar} を利用した．
ピラミッド評価，Quality Questions
とも1つのトピックに対し1名の被験者が全ての要約を評価した．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{結果と考察}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{自動評価結果}


人手評価結果を示す前に，自動評価という観点からの抽出型オラクル要約のROUGE-2，BEスコアの
到達点を
表\ref{auto} に示す．
なお，表中の``Best''は
{\tt peer\_40} と {\tt peer\_22} のスコアである．
表より，双方のデータセットともEDU抽出，根付き部分木抽出，
文抽出の順でスコアが高い．
EDU抽出，根付き部分木抽出は文よりも小さな単位を抽出するので，
ある長さの制約のもとで
多くの情報を詰め込むことが可能なことから妥当な結果である．
Best と比較すると
その差は非常に大きく，ROUGE-2では0.1から0.13ポイント，BEでは0.13から0.17ポイントの差である．
なお，TAC-2009/2011のデータセットにおける現在の ROUGE-2 のベストスコアはそれぞれ
0.128 \cite{li-etal-2015-using}，0.144 \cite{li-etal-2013-document} であり\footnote{前者は文抽出による要約システム，後者は圧縮型要約システムである．}，
これらスコアとオラクル要約のスコアを比較してもその差は非常に大きい．
特に，古典的な文抽出型オラクル要約であっても極めて高い
自動評価スコアを獲得していること
から，自動評価という観点ではあるが現在の要約システムは抽出型要約の
上限には程遠いことがわかる．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 2
\begin{table}[b]
\caption{抽出型オラクル要約の自動評価スコア}
\label{auto}
\input{01table02.tex}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 3
\begin{table}[b]
\caption{ピラミッド評価と Qualiry Questions の結果}
\label{res}
\input{01table03.tex}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{ピラミッド評価の結果}

表\ref{res} にピラミッド評価とQuality Questionsの結果を示す．カッコ内の数
値は
分散をあらわす．
オラクル要約間を比較すると自動評価指標の場合と同様の傾向を示しており，
EDU抽出，根付き部分木抽出，文抽出の順にスコアが高い．
TAC参加システムと比較するとこれも自動評価指標の場合と同じくその差は大きい．
この結果をより詳細に分析するため，
各オラクル要約と参照要約に含まれる平均部分文数を調べた．その結果を
表\ref{sent} に示す．
表より，1つの要約に含まれる平均部分文数は，EDU抽出，根付き部分木抽出，文抽出の
順に多い．EDU抽出は3--4文，根付き部分木抽出は2文程度，文抽出よりも
文数が多い．また
参照要約は根付き部分木抽出の場合に比べ1文弱程度，文数が
少ない．
先に述べたとおり，EDUや根付き部分木は，文抽出よりも
より多くの部分文を要約に含めることができる．よって，SCUがうまく
部分文に含まれていれば高いピラミッドスコアを達成できる．Li ら \citeyear{W16-3617} は
SCUとEDUは一致することが多いことを報告しており，この実験結果を
支持している．
これらの結果は，原文書の一部を抽出するだけで，自動評価だけでなく
人手の内容評価も高い要約が生成可能であることを示している．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% table 4
\begin{table}[t]
\caption{各要約の平均部分文数}
\label{sent}
\input{01table04.tex}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

なお，人間による文抽出である{\sc HexTac}のスコアは，要約システムとほぼ変わらず
オラクル要約に対しては大きく劣る結果となった．
{\sc HexTac} はそもそも参照要約を再現するように生成されていないこと，
参照要約はNISTが訓練した情報分析のエキスパートが生成していることに対し，
{\sc HexTac}は計算機科学の研究者が要約を生成していることが
原因であろう．
{\sc HexTac}の5名の要約作成者間の
文抽出に対する一致が低いことも報告されており \cite{hextac}，
非エキスパートによる要約に問題があったのではないかと考える．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection*{Quality Questionsの結果}

自動評価とピラミッド評価においてオラクル要約は非常に高い評価を得たが，
表\ref{res} より，
Quality Questions の結果は既存の要約システムと同等か劣る結果となった．
要約システムがどの項目においても4以上のスコアを得ていることに対し，
オラクル要約のスコアは，TAC-2009の場合にはすべての項目で4未満，
TAC-2011の場合には
文抽出オラクル要約のみがシステムと同等の4程度のスコアである．
TAC-2009/2011とも文抽出オラクル要約のGrammaticalityスコアが要約システムよりも
低く，TAC-2009では4未満である．
TACでは
原文書に対して文区切りは与えられず，何らかの方法で文境界を認定しなければ
ならない．文区切りには Stanford CoreNLP を用いて同定したが，
引用符号やカッコの対応がとれていない文があり，これらが悪影響を与
えた．さらに，原文書に含まれる名詞句だけの短い文（記事の小見出し）を
抽出した際にも Grammaticality スコアが低いと判断された．
EDU抽出，根付き部分木抽出のGrammaticalityスコアはさらに
低く，EDU抽出は2から3程度でしかない．文の一部を抽出することにより
文頭が大文字でない場合があること，EDUセグメンタのエラーにより
非文法的なEDUが生成されること，依存構造解析のエラーにより根付き部分木の
文法性が損なわれることが原因である．
文頭が小文字であればそれを大文字にすることは
自動的にできるが，後者の2つの事象については解析器の性能が完璧
でない限り避けることができない．つまり，部分文を抽出する限りある程度
文法的な誤りが含まれることは避けられない．
Non-redundancy，Referential clarity
が低い原因として，EDU，根付き部分木抽出は
参照要約での出現回数程度，
固有表現を繰り返し抽出するものの，人間のように参照表現を
織り交ぜて表現することができないため，単なる固有表現の繰り返しと
なってしまい冗長に感じること，
そもそも要約生成法に参照表現とその実体を
対応付ける機構がないため，部分文の数が多いと参照表現が
指すものが曖昧になる可能性が高くなることが原因である．
さらに，部分文は接続詞を欠くことが多いこと，
部分文の数が多いことで情報が断片化してしまうことにより
文脈が損なわれる
ことが多々ある．その結果，焦点や結束性という観点で
低い評価となってしまう．

図\ref{sum_ex} に参照要約，各種法によるオラクル要約，{\tt peer\_40}の要
約例を示す．オラクル要約の生成の際に最大化する自動評価スコアには
BE を用いた．
オラクル要約は参照要約との間の BE スコアを最大化しているため，当然である
が，参照要約の内容をよく反映している．
特に，EDU抽出，根付き部分木抽出は文の
数が多いためより多くの内容で参照要約と一致している．
システム要約{\tt peer\_40} は参照要約を考慮せずに作成された要約で
あるため，オラクル要約と比較すると参照要約との間の
内容の一致は高くない．
一方，要約の言語品質に着目すると，EDU抽出，根付き部分木抽出には先
頭が大文字でない文が含まれており，Grammaticality が低い．
また，文抽出と比較すると，固有表現の繰り返し回数が多く人名の参照に対し
て一貫性がない．
たとえば，``L. Dennis Kozlowski''に対し，参照要約では初出時がフルネーム，
2回目以降は姓だけであることに対し，
EDU抽出，根付き部分木抽出は，初出時に姓のみ，2回目がフルネームとなっている．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 3
\begin{figure}[p]
\includegraphics{27-2ia1f3.eps}
\caption{トピックID``D0928'', ``Trials of Tyco's Dennis Kozlowski''に対する要約．}
\label{sum_ex}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% fig. 4
\begin{figure}[p]
\begin{center}
\includegraphics{27-2ia1f4.eps}
\end{center}
\caption{ペナルティの重みを変化させた場合のROUGE-2，部分文数の変化}
\label{rouge_sent}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

なお，部分文の数が多いことが Quality Questions の評価を下げる要因であ
るのなら，それを抑制すればよい．
オラクル要約に採用する部分文の数をさらに抑制するには式(11)，(21)のペナ
ルティ項に対する重みを1よりも大きくすればよいことから，
TAC-2009のデータセットを対象として，EDU抽出，根付き部分木抽出の双方の
ペナルティ項に対する重みを$\alpha$として1から0.5刻みで3.5まで変化
させ，要約あたりの平均文数，ROUGE-2スコアの変化を調べた．
その結果を図\ref{rouge_sent} に示す．図
より，$\alpha$を大きくするにつれて平均文数が減っており Quality Questions
による言語品質の評価が向上することが期待できる．一方，ROUGE-2スコアは低
下してしまう．つまり，単純に部分文の数を抑制しただけでは要約の内容が劣
化することを示している．

以上より，抽出型要約手法により情報に富んだ要約を生成できることがわかった
が，その言語品質は決して高いとは言えず改善が必要であることが明らかとなっ
た．ピラミッド評価で高い評価が期待できるほどの高い自動評価スコアを維持し
つつ言語品質をいかに高めていくかが抽出型要約の重要な研究ポイントとなるで
あろう．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{おわりに}

本稿では文抽出，EDU抽出，根付き部分木抽出という3種の抽出型要約手法による
オラクル要約，すなわち ROUGE-2 あるいは BE スコアを最大化する要約を生成する
ための整数計画問題による定式化を提案し，それらの上限を明らかにした．
オラクル要約の自動評価スコアは現状の要約システムのスコアよりも明らかに高
く，抽出型要約手法にはまだ研究の余地が残されていることが
わかった．そして，オラクル要約の内容評価と言語品質評価をピラミッド評価と
Quality Questionsを用いて人手で評価しその妥当性を検証した結果，
自動評価スコアと同様，オラクル要約のピラミッドスコアは非常に
高いことがわかった．一方，Quality Questions の結果から，
EDU抽出，根付き部分木抽出の場合，解析器の誤りなどにより部分文の文法性が
低下し，それにより要約全体の言語品質が大きく低下することが
明らかとなった．これらの結果より，抽出型要約手法はまだまだ
有望な要約手法であり，今後も研究を続ける価値があることが
明らかとなった．一方，言語品質を担保するための研究が
重要であることも明らかとなった．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\acknowledgment

有益なコメントをくださった査読者，担当編集委員の皆様に感謝いたします．
本研究の一部は
The 15th European Chapter of Association for Computational 
Linguistics (EACL) での発表 \cite{hirao2017:EACL} と
The 55th Association for Computational Linguistics (ACL)
での
発表 \cite{hirao-acl2017} に基づいています．


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\setlength{\baselineskip}{16.5pt}
\bibliographystyle{jnlpbbl_1.5}
\bibliography{01refs}
}%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{biography}
\bioauthor{平尾　　努}{%
1997年奈良先端科学技術大学院大情報科学研究科博士前期課程修了．同年，株式会
 社 NTTデータ入社．2000年より日本電信電話株式会社 コミュニケーション科学
 基礎研究所．博士（工学）．自然言語処理の研究に従事．情報処理学会，言語
 処理学会，ACL各会員．
}
\bioauthor{西野　正彬}{%
2008年京都大学大学院情報学研究科修士課程修了．同年，日本電信電話株式会社
 入社．現在，コミュニケーション科学基礎研究所．博士（情報学）．
自然言語処理，アルゴリズムの研究に従事．情報処理学会，人工知能学会，言語
 処理学会各会員．
}
\bioauthor{永田　昌明}{%
1987年京都大学大学院工学研究科修士課程修了．
同年，日本電信電話株式会社入社．現在，コミュニケーション科学研究所 上席
特別研究員．工学博士．自然言語処理の研究に従事．電子情報通信学会，情報処
 理学会，人工知能学会，言語処理学会，ACL各会員．
}
\end{biography}



\biodate




\end{document}

