\section{The HER Model}\label{Model}


\begin{figure*}[!htbp]
    \centering
    \includegraphics[width=15cm,height=5cm]{figure/model2.eps}
    \caption{The overall framework of HER is formulated as a contextual bandit and can be divided into a two-stage process containing rough reading and careful reading.
    }%\vspace{-2mm}
\label{fig:model}
\end{figure*}

In this section, we introduce the overall framework of our model, HER.
We formulate extractive summarization as a contextual bandit~\cite{langford2007epoch} trained using policy gradient reinforcement learning.

As illustrated in Figure~\ref{fig:model}, the framework can be divided into two stages: rough reading and careful reading.
During rough reading, a document with $N$ sentences is encoded into sentence vectors $\{S_1,S_2,\dots,S_N\}$ as well as a set of  features denoted as $F$, which includes one global feature $\bar S$ representing the whole documentary information and $K$ local features $\{L_1,L_2,\dots,L_K\}$ depicting paragraphical contents%\footnote{Although pre-trained models such as BERT~\cite{devlin2018bert} or Skip-thought~\cite{kiros2015skip} are proved to be effective encoders, they are inappropriate in this work since the policy gradients from our model may contribute little to the update of these large models.
%as the update taken by policy gradients from our model may make little difference on these large pre-trained models.}.
%  they may be ineffienct in training as the encoder is updated by policy gradient which may make little difference on large pre-trained models
In careful reading, sentence vectors are decoded into real-valued scores called sentence affinities~$\{\mu_1,\mu_2,\dots,\mu_N\}$,
which can be considered as an estimation of sentence correlation to cover the context.
Then a bandit policy is used to repeatedly choose unique sentence until the termination mechanism is triggered.
% We train an agent using policy gradient reinforcement learning which takes a to-be-selected sentence set as action and then receives a reward afterwards.

We will detail the preliminaries in Sec.~\ref{form}, the rough reading stage in Sec.~\ref{rough}, and the careful reading stage in Sec.~\ref{careful}. The training process is illustrated in Sec.~\ref{train}.


\subsection{Summarization as Contextual-Bandit}\label{form}

% \textcolor{blue}{[Yan]: perhaps `Preliminaries' is a better title for this subsection}

Contextual-bandit~\cite{langford2008epoch,li2010contextual,pan2019policy} is the multi-armed bandit~\cite{auer2002nonstochastic} problem with featured contexts. At each step, the agent observes a context, selects an action based on the context, and then receives a reward.
The agent's goal is to quickly find a decision making policy to maximize its return.

In extractive summarization, the goal of the task is to extract an undetermined number of sentences from the original document as summary.
We show that it can be formulated as a contextual bandit problem if we select the sentences sequentially.
Specifically, for each document, the \textit{context} includes its documentary representation learned through rough reading.
At each step $t=1,2,\dots$, we define the \textit{action} as the index of the next sentence to select.
The agent keeps selecting sentences until it reaches the termination condition (detailed in Sec. \ref{terminal}).
Finally, the selected sentences $\textrm{SUM}=(S_{a_1},\dots,S_{a_M})$ corresponding to the selected actions $(a_1,\dots,a_M)$ form an extractive summary. The agent will receive a reward $R(\textrm{SUM};G)$. 
% \redfont{So a sequential sentence indices $a=a_1,\dots,a_M$ can be considered as an action where $a_t \in [1,N],t\in[1,M]$ and there are $2^N-1$ optional actions in total.
% After an action $a$ is taken, which means $\{S_{a_1},\dots,S_{a_M}\}$ is formed as the extractive summary implemented through careful reading, the agent will receive a reward $R(\textrm{SUM};G)$.}\reminder{???????????}
Note that $G$ is the manually-labeled gold-standard summary of the document $D$, and the reward $R(\textrm{SUM};G)$ measures the correlation between $G$ and the predicted summary $\textrm{SUM}$. 
% We accomplish such procedure by the careful reading in HER.
%Under such perspective, the problem for us is to train an agent which is based on document features from rough reading and takes actions to form extractive summarization in careful reading.

\subsection{Rough Reading}\label{rough}
%$f_{\theta1}(\cdot|D)$
In rough reading, we aim to form a general cognition on a given document which encodes the document into sentence embeddings as well as produces the feature set $F$ including global and local features. 
%$F$ is considered as the contextual information in our framework.

Specifically, bidirectional LSTMs~(BiLSTMs) on word- and sentence-level are first used to encode a document with $N$ sentences into $d_s$-dimentional sentence embeddings $\{S_1,S_2,\dots,S_N\}$, $S_i \in \mathbb{R}^{d_s}$.
Second, a global feature $\bar S\in \mathbb{R}^{d_s}$ is computed as an average of all the sentence vectors.
% \redfont{which can also be represented by the last hidden unit of the sentence-level BiLSTM.}\reminder{which one is actually used?}
Third, we use a convolutional neural network to refine gist of different paragraphs and generate multiple local features on the sentence level, which is different from previous methods~\cite{kim2014convolutional,narayan2017neural,yao2018deep} processing on the word level.
In detail, a stacking of $N$ sentence vectors is represented as,
\begin{equation}
    S_{1:N} = [S_1, S_2, \cdots, S_N] \in  \mathbb{R}^{N\times d_s},
\end{equation}
We apply 1-D convolutional neural networks on $S_{1:N}$ followed with a max-over-time pooling so that a final document-level representation can be extracted.
Specifically, we altogether used $K$ convolutional nets with $K$ different window sizes to summarize different gists of paragraphs. Finally, by stacking the outputs together, we get the final document-level representation for local features $L_{1:K}\in\mathbb{R}^{K\times d_s}$.

\subsection{Careful Reading}\label{careful}
% $g_{\theta2}$
%During careful reading, $N$ sentences are decoded into real-number scores called sentence affinities $\{\mu_1,\mu_2,\dots,\mu_N\}$, where $\mu_t\in[0,1]$ and it represents the probability of sentence $S_t$ to be included in the summary.
%Afterwards, $\epsilon$-greedy is used as the bandit policy to select one sentence at each step until termination mechanism is triggered.
%In this section, we present the sentence decoder in Sec.\ref{decoder}, the bandit policy in Sec.\ref{selection} and the termination mechanism in Sec.\ref{terminal}.

%For careful reading, the goal of the extractive neural model denoted as $p_{\theta}(\cdot|D)$ is to select a sentence sequence $\textrm{SUM} = \{S_{a_1},\dots,S_{a_M}\}$ to form a summary, where $M\in [1,N]$ and $N$ is the document length.
Now that we have the sentence vectors and  document-level features given by rough reading, we can perform careful reading to select the sentences one by one to form the summary. 


\subsubsection{Sentence Decoder}\label{decoder}
% \reminder{What do you mean by saying ``decoder''? as far as im concerned, a decoder means a model that generates the data (e.g. an image in image generation) from a latent code. What is $q$? If it is a score, you can use ``score function'' or ''value function'', not ``decoder''.}
% \textbf{Sentence Decoder}
%In order to extract high-quality summaries, the decoder generates sentence affinities by considering:
%(1) The selected summary cannot deviate the main idea represented as $\bar S$.
In order to extract high-quality summaries, we first compute the sentence affinities by a \textit{sentence decoder}, which is observed effective in \citet{dong2018banditsum}. The sentence affinities are calculate by the following principles: 
(1) \textit{Salience}~(The sentences whose meanings are close to the central idea should be emphasized);
(2) \textit{Coverage}~(The sentences that match different paragraphical information should be encouraged);
(3) \textit{Redundancy}~(The unselected sentences which are similar to already extracted ones should be inhibited).

As we need to learn the relations between each sentence and the rest of the document, we update the sentence representations by,
\begin{equation}
S'_t = S_t \oplus \bar S \oplus L_{1:K}, t=1,\dots,N.
\end{equation}

Then, we utilize a decoder $\mathrm{Dec_1}$ to score the Salience and Coverage for each sentences, and a secondary score function $\mathrm{Dec_2}$ to screen the sentences that might have Redundancy. % by lowering the sentence affinity values whose meanings are close to those likely to be extracted earlier.
Specifically,
\begin{align}
\bm{\mu}_1 &= (\mu_{11}, \dots, \mu_{1N})^\top = \mathrm{Dec_1} (S'_{1:N}),\label{Dec_1}\\
\bm{\mu}_2 &= \mathrm{Dec_2}(S'_{1:N}\circ(1-\bm{\mu}_1)),\label{Dec_2}
\end{align}
We implement $\mathrm{Dec_1}$ and $\mathrm{Dec_2}$ as multi-layered perceptrons.
% with a tanh unit, another multi-layer perceptron and a final sigmoid unit.
% $Pos^t$ is the position embedding of sentence $S_t$.
Finally, we average the two scores as the final sentence affinities. 
\begin{equation}
\bm{\mu} = (\bm{\mu}_1+\bm{\mu}_2)/2.
\end{equation}

\subsubsection{Bandit Policy}\label{selection}
The overall decision making process goes as follows. The agent selects one sentence at each step based on the contextual information provided by the rough reading and sentence affinities computed by the sentence decoder. It stops taking actions once the termination mechanism is triggered. After that, all the selected sentences are formed as a summary, and a final reward can be calculated by comparing to the labeled golden summary. As there is no intermediate reward before termination, the goal of the agent is to find a policy to maximize its expected long-term return.
%After obtaining sentence affinities, the agent should include one sentence at a time until they think the summary formed by all the selected sentences is good enough to cover the context and then take it as an action.

% Recall that a sequence of selected sentences which form an extractive summary is considered as an action.

It is an intuitive choice to select sentences with the highest affinities as summary,
which is similar to training data selection \cite{song-etal-2012-entropy,liu-etal-2019-reinforced}.
%
However, such an \textit{argmax} policy is prone to only learn the easy patterns since it lacks exploration.
We will show an example in  Section~\ref{human}.
They should be explored to form the summary as well.
%Although exploiting sentences satisfying the above rules may cover the main parts of the contexts, exploring low-score ones may discover information which is important but .
Since the search space for summarization is extremely large, we must explicitly address the tradeoff between exploration and exploitation for fast learning, which is an active research area in reinforcement learning and applications \cite{pan2019policy,pan2019pome}. 
In our work, we find the use of $\epsilon$-greedy with stochastic policy works well enough to encourage exploration. 
Specifically, with a probability of $1-\epsilon$, the agent chooses the sentence following the current policy, i.e., to sample an index $a_t\in [1,N]$ from the multinomial distribution with sentence affinities $\{\mu_1,\mu_2,\dots,\mu_N\}$ as probabilities.
% Here we use sampling from the multinomial distribution instead of choosing the sentence with the highest affinity, which raises the probability of low-value sentences to be extracted.
Otherwise, with a small probability of $\epsilon$, the agent randomly picks one available sentence as an exploration. 
Note that such exploration is only used during training.

\subsubsection{Termination Mechanism}\label{terminal}
%How many sentences to be extracted as summary is based on the contexts and varied from different documents.
%Intuitively, the agent should stops selecting other sentences when the future reward takes on negative growth.
%However, it would cause mismatch between training and test because there is no gold-standard summary to obtain feature rewards during testing. In addition, it would compute rewards $M+1$ times before an action $a=a_i,\dots,a_M$ is taken to induce extractive summary.
% we only compute the reward once when action  is taken while it would take $M+1$ times long to see if this is a proper action with better future reward.
In HER, we propose a termination mechanism that is independent on future rewards to make our model flexible in extracting summary with various numbers of sentences.
%The first is probability termination mechanism, 
This mechanism is defined as follows 
\begin{equation}
\textrm{Done} \sim \textrm{Bernoulli}(\min(\frac{\mu_{\min} }{\mu_{\max} },1-\mu_{\max})),\label{term}
% r \in \{0,1\},
\end{equation}
%\begin{equation}
%\hat{p} = \frac{max(\mu_{1:N})-min(\mu_{1:N})}{max(\mu_{1:N})} < \xi,
%\end{equation}
%where $\xi$ is a constant and determined by evaluation, and $\mu_{1:N}$ represents the affinity set.
where $\mu_{\max}$ and $\mu_{\min}$ denotes the maximal and minimal value in $\bm{\mu}$ for all the remained sentences, respectively. Thus $\textrm{Done}=1$ terminates the sentence extraction when there is no key sentences left. 
%$\lambda$ is a hyper parameter fine-tuned during evaluation.
With this mechanism, the agent will stop extraction with high probability as long as the differences among remaining affinities are small enough or the remaining sentence affinities are very low.
%The second mechanism sample a result from the binomial distribution $r\sim B(1,\lambda \hat{p})$,
%where $r \in \{0,1\}$ and $\lambda$ is a hyper parameter fine-tuned during evaluation.
%Notice that $r=0$ represents the termination of sentence extraction which makes our propose model not only explore on the sentence selection process but on the termination decision.
%with the computed probability ${p}$ above.

%%%%%%  ------不一定要这个termination mechanism ------ %%%%%%
% The second one is sentence termination mechanism. We insert a special sentence representation to a random position of original context. Termination is triggered as long as this sentence is extracted. Notice that we only use Eq.~\ref{Dec_1} to compute sentence affinity when using this termination mechanism.

\subsection{Training}\label{train}
%As the reading process finishes, summary induced by action $a$ has been extracted out of document $D$. 
After the agent sequentially takes an action $a_t$ until terminated,
% that selects a set of sentences, 
we can derive an summary induced by $a$ out of a document $D$. Then the agent would receive a reward $R(\textrm{SUM};G)$ where $G$ is the gold-standard summary of $D$. $R(\textrm{SUM};G)$ is computed by the average of three variants of ROUGE \cite{lin2004rouge}. To balance precision and recall, we use $F$-score here,
\begin{equation}\small \label{reward}
\begin{split}
&R(\textrm{SUM};G) = \frac{1}{3}(\mbox{ROUGE-1}_f(\textrm{SUM};G)\\
&+\mbox{ROUGE-2}_f(\textrm{SUM};G)+\mbox{ROUGE-L}_f(\textrm{SUM};G)).
\end{split}
\end{equation}
% % {\small
% \begin{align}\label{reward}
% &R(\textrm{SUM};G) = \frac{1}{3}(\mbox{ROUGE-1}_f(\textrm{SUM};G)\\
% &+\mbox{ROUGE-2}_f(\textrm{SUM};G)+\mbox{ROUGE-L}_f(\textrm{SUM};G)).
% \end{align}}
We represent the whole extractive neural network as $p_{\theta}(\cdot|D)$ containing the encoder in rough reading and the decoder in careful reading. The goal of our model is to find parameters $\theta$ of $p_{\theta}$ to produce high-quality summary and maximize the rewards~(c.f. Eq.~(\ref{j})).
But we cannot obtain gradient to maximize Eq.~(\ref{j}) with gradient ascent as it is discretely sampled.
So we use the likelihood ratio gradient estimator, also known as REINFORCE \cite{williams1992simple,sutton2000policy}, to acquire the gradient by Eq.~(\ref{gradient}).

We use $Q(D)$ in Eq.~(\ref{ptheta}) to construct $p_{\theta}(a|D)$ following~\citet{dong2018banditsum}, where $z(D)=\sum_t\mu_t(D)$ and $\epsilon$ is the exploration probability of the $\epsilon$-greedy denoted in Sec.~\ref{selection}.
$M$ is the number of extracted sentences this is determined jointly by the termination mechanism and the document context. $Q(D)^{\frac{1}{M}}$ is adopted to present $p_{\theta}(a|D)$ to avoid extracting fewer or more sentences when maximizing the objective function.
%$Q(D)^{\frac{1}{M}}$ to present $p_{\theta}(a|D)$. 
Hence, $\bigtriangledown_{\theta}\mbox{log}p_{\theta}(a|D)$ in Eq.~(\ref{gradient}) can be easily computed.

{\small %
\begin{align}
J(\theta) &= E[R(\textrm{SUM};G)]\label{j}\\
\bigtriangledown_{\theta}J(\theta) &= E[\bigtriangledown_{\theta}\mbox{log}p_{\theta}(a|D)R(\textrm{SUM};G)]\label{gradient}\\
Q(D) &= \prod_{j=1}^{M} (\frac{\epsilon}{N-j+1}+ \frac{(1-\epsilon)\mu_{a_j}(D)}{z(D) - \sum_{k=1}^{j-1}\mu_{a_k}(D)})\label{ptheta}
\end{align}}\relax
%Given a $N$-length document $D$, our extractive model encodes it into sentence vectors and generates rough information $F$. Then sentences are decoded into sentence affinities $\{\mu_1,\mu_2,\dots,\mu_N\}$ which is chosen step by step with $\epsilon$-greedy technique to form summary.
However, the exact document distribution is unknown and we cannot evaluate the expected value in Eq.~(\ref{gradient}). So we use sampling to estimate it instead. Given a document-summary pair $(D,G)$, our HER samples $B$ summaries induced by $a^1,\dots,a^B$ from $p_{\theta}(\cdot|D)$ and obtain all the gradients, then the average value is considered as the estimation. As sample-based gradient estimate may have high variance, we use a baseline for variance reduction. The gradient of the objective function is finally represented as,
\begin{equation}\small
\bigtriangledown_{\theta}J(\theta) \approx \frac{1}{B} \sum_{b=1}^{B} \bigtriangledown_{\theta}\mbox{log}p_{\theta}(a^b|D)(R(a^b,G)-\bar{r})
\end{equation}
where we choose self-critical reinforcement learning to acquire the baseline $\bar{r}$ following~\citet{ranzato2015sequence,rennie2017self,paulus2017deep,dong2018banditsum} computed by greedy encoding $\bar{r}=R(a_{greedy};G)$.
More concretely, $a_{greedy}={\mbox{argmax}}p_{\theta}(a|D)$ and this baseline satisfies that the probability of a sampled sequence would be increased when the summary it induces is better than what is obtained by greedy decoding.
%
The procedure of HER is shown in Algorithm~\ref{alg}.

\begin{algorithm}[t]\small
\caption{HER: training}
\hspace*{\algorithmicindent} \textbf{Input} 
   $\{(D_i,G_i)\}$, a dataset of document-summary pairs\\
\hspace*{\algorithmicindent} \textbf{Output} 
   $\theta$, the updated parameters in $p_{\theta}$
\begin{algorithmic}[1]
% \Procedure{Euclid}{$D,G$}\Comment{Sample a $(D,G)$ pair}
% \State Randomly sample a $(D,G)$ pair
\For{each document-summary pair $(D, G)$}
\State $S_{1:N},\bar S,L_{1:K}=\mbox{Encoder}(D)$
\Comment{\begin{scriptsize} Rough Reading \end{scriptsize}}
\State $\mu_{1:N}=\mbox{Decoder}(S_{1:N},\bar S,L_{1:K})$
\Comment{\begin{scriptsize} Careful Reading\end{scriptsize}}
% \State Initialize $loss_{1:B}=0,sumloss=0$
% \State Empty the to-be-selected sentence indices $a=[]$

\For{each trail $b=1,\dots,B$}
\State Initialize the action set $A=\{1,\dots,N\}$
\For{time step $t=1,\dots,N$}
\State Sample $u\sim U(0,1)$
\If{$u<\epsilon$}
\State Uniformly sample $a_{t}$ from $A$
\Else
\State $a_{t} \sim \textrm{Categorical}(\bm{\mu}_{A})$
\EndIf
\State Get termination flag by Eq.(\ref{term})
\State Let $M=t$
\If{Done}
\State Break the inner loop
\Else
\State Update the action set $A = A$ \textbackslash $\{a_t\}$
\EndIf
\EndFor
\State Generate summary $\textrm{SUM}_b=(S_{a_1}, \dots, S_{a_M})$
\State $l_{b} = \frac{1}{M}\sum_{t=1}^M \log(\frac{\epsilon}{N-t+1}+\frac{(1-\epsilon)\mu_{a_t}}{\sum_j\mu_j -\sum_{k=1}^{t-1}\mu_{a_k}})$

\State Compute reward $r_b = R(\textrm{SUM}_b;G)$
\EndFor
% \Comment{Careful Reading End}

% \State Loop $4-12$ steps, obtain $C$ sample results: $\{loss_{1},\dots,loss_{B}\}$, $\{R_{1},\dots,R_{B}\}$ 
% \Comment{Training Begin} 
\State $\bar{r}=R(\textrm{SUM}_{greedy};G)$

\State $l = \frac{1}{B}\sum_{b=1}^{B} l_b(\bar{r}-r_{b}) $\Comment{\begin{scriptsize} Surrogate loss \end{scriptsize}}
\State $\theta \gets \theta-\lambda \bigtriangledown_{\theta}l$\Comment{\begin{scriptsize} Update \end{scriptsize}}
% \State Perform gradient descent on $sumloss$ with respect to parameters of extractive neural network $p_\theta$
% \Comment{Training End}
\EndFor
\end{algorithmic}
\label{alg}
\end{algorithm}
