Reward Learning for Efficient Reinforcement Learning in Extractive Document Summarisation

1 Introduction

Extractive document summarization, as a challenging instance of natural language generation (NLG), is a popular summarisation paradigm, which builds summaries by selecting an appropriate sequence of important phrases or sentences from the input document(s). Extractive summarisation can be formulated as a sequential decision-making problem, and hence can be tackled by the Reinforcement Learning (RL) algorithms. RL searches for the (near-)optimal trajectories (i.e. sequences of decisions) by directly optimising the objective functions, e.g. the ROUGE metrics [Lin, 2004]. Such objectives are non-differentiable and therefore difficult to be directly optimised by deep neural networks. In addition, RL alleviates the exposure bias problem faced by sequential supervised learning paradigms in NLG. Combining RL algorithms such as REINFORCE [Williams, 1992] with neural techniques (e.g. sequence-to-sequence) yields state-of-the-art performance in summarisation [Narayan et al., 2018; Yao et al., 2018].

∗Work performed while at UKP-TUDA.

Existing RL-based summarisation systems fall into two categories: cross-input RL and input-specific RL. For cross-input RL (upper part in Fig. 1), at training time, RL agents interact with a ground-truth reward oracle for multiple episodes so as to learn a policy that maximises the accumulated rewards in the episode; at test time, the learnt policy is applied to unseen data to generate the summary. However, learning such cross-input policies is very expensive because of the huge search space. Another issue is the delayed rewards: the ROUGE scores can be calculated only when the complete summary is generated. Such delayed rewards cause RL-based summarisers to take even longer time to converge. Although multiple techniques have been proposed to speed up the training of RL, e.g. memory replay [Mnih et al., 2015], MIXER [Ranzato et al., 2016] and imitation learning [Cheng et al., 2018], training cross-input RL yet requires considerable time, data and parameter tuning.

On the other hand, input-specific RL (middle part in Fig. 1) neither requires parallel data (i.e. input documents and reference summaries for them) nor a reward oracle. Instead, it employs a handcrafted reward function with which the RL agent interacts in order to learn a policy specifically for the given input. By doing so, the size of the search space significantly decreases, which consequently diminishes the training time and computational resources. However, designing such a reward function is highly challenging as it should fit all inputs [Rioux et al., 2014]. This explains the poor performance of input-specific RL summarisers [Ryang and Abekawa, 2012].

To tackle the problems faced by the above two RL-based summarisation paradigms, we propose a novel paradigm called REward Learning for Input-Specific reinforcement learning (RELIS). Instead of learning a cross-input policy, RELIS learns a cross-input reward oracle at training time, and then uses the learnt reward to train an input-specific policy for each input at test time (bottom part in Fig. 1). RELIS is inspired by inverse RL [Abbeel and Ng, 2004], which requires a demonstrator to present optimal trajectories. Because such a demonstrator is hardly available in summarisation, RELIS leverages Learning-to-Rank (L2R) algorithms [Li, 2011] to approximate the ground-truth reward oracle from "weak supervisions", e.g., numeric scores that indicate the quality of the summary or preferences over summary pairs.

Our contributions are threefold: (i) We propose RELIS (§2), a new RL-based summarisation framework that enjoys the strong performance of cross-input RL and the low computational cost of input-specific RL. (ii) Theoretically, we prove that by employing appropriate L2R and RL algorithms, RELIS guarantees to generate near-optimal outputs (§3). (iii) Empirically, we evaluate RELIS in multi-document extractive summarisation (§4). Compared to the state-of-the-art methods, RELIS provides comparable performance but requires much less the training time or data. Because the proof of RELIS is generic, we believe RELIS has the potential to be applied to other NLG tasks, e.g. translation and sentence simplification. Source code and supplementary material are available at https://github.com/UKPLab/ijcai2019-relis.

2 RELIS

We first formally define the summarisaiton task, and then detail the L2R and RL module of RELIS.

2.1 Extractive Summarisation

In line with Peyrard and Eckle-Kohler [2017], we formulate summarisation as a discrete optimisation problem. Let X be the set of all possible input documents and X be the set of inputs available at training time. An input can be either a single document or a cluster of documents on the same topic. For input x ∈ X, let Yx indicate the set of all extractive summaries for x that comply with the length requirement. Then, the task of summarisation is to map each input x to its best summary in Yx with respect to a ranking function σx : Yx → N. For a candidate summary y ∈ Yx, σx returns the number of candidates in Yx that have equal or lower quality than y, including y itself. For example, if y is the highest-quality candidate in Yx, then σx(y) = |Yx|. σx can be obtained from human evaluators, automatic metrics (e.g. ROUGE) or heuristics measuring the quality of outputs. We denote the ground-truth ranking function on Yx by σ∗x .

Given the above definition of summarisation, we define a summariser agent as a tuple (σx,Mx), where Mx is an optimisation model for finding the (near-)optimal summary with respect to σx. In the cross-input paradigm, the RL agent learns a policy that solves the optimisation problem Mx for any x ∈ X at training time. In RELIS, instead, an agent learns a ranking ˆσU x : Yx → N at training time so that ˆσU x is as "close" as possible to σ∗x ("close" will be formally defined in §3). At test time, for each x′ ∈ X \ X, RELIS formulates Mx′ as a Markov Decision Process (MDP) and learns an RL policy specifically for Mx′ .

2.2 Learning to Rank (L2R)

L2R algorithms learn to reconstruct the ranking over objects from an oracle [Li, 2011]. L2R induces the approximated ranking ˆσU x by learning a utility function U from the oracle, such that ˆσU x (y1) > ˆσU x (y2) if and only if U(y1, x) > U(y2, x). L2R can learn from different types of oracles, including pointwise oracles that provide point-based scores for objects, pairwise oracles that provide preferences over pairs of objects, and listwise oracles that provide certain metrics (e.g. accuracy) for candidate rankings. Here, we focus on pointwise and pairwise oracles as humans reliably provide such judgements for short texts [Kreutzer et al., 2018]. Function U can be learnt by any function approximation technique, e.g., neural networks.

In pointwise L2R, for every x ∈ X, we draw N sample summaries from Yx using some sampling strategy, e.g., random sampling without replacement. Then, we query their σ∗x values from the oracle and use a regression algorithm to minimise the averaged mean squared error (MSE) between U and σ∗x . Formally, the loss function is

In pairwise L2R, for every x ∈ X we sample K pairs of summaries from Yx and then query the oracle about their preferences. We denote the collected preferences for input x by Px = {p1(y1,1, y1,2), · · · , pK(yK,1, yK,2)}, where yi,1, yi,2 ∈ Yx are the candidate outputs presented to the oracle in the ith iteration; pi(yi,1, yi,2) equals 1 if the oracle prefers yi,1 over yi,2, and equals 0 otherwise. Different loss functions can be used to learn U from the preferences in Px. First, we consider the cross-entropy loss:

where P(y1, y2) = (1 + exp[U(y2, x) - U(y1, x)])-1 . An alternative is the margin ranking (a.k.a. pairwise hinge) loss:

where ei = 1 if yi,1 is preferred over yi,2, and ei = -1 otherwise. Additionally, we consider an improved margin ranking loss proposed by Agarwal and Collins [2010], which gives large penalties to mis-ranked pairs with wide margins:

Note that the improved margin ranking loss is a mix of pointwise and pairwise L2R as it requires both σ∗x and Px.

2.3 Reinforcement Learning (RL)

RL amounts to algorithms that search for optimal solutions in Markov Decision Processes (MDPs). We formulate the optimisation problems Mx for NLG tasks as episodic MDP [Ryang and Abekawa, 2012; Rioux et al., 2014]. An episodic MDP is a tuple (S,A, P,R, T), where S is a set of states, A is a set of actions, P : S ×A → S is the transition function with P (s, a) giving the next state after performing action a in state s, R: S × A → R is the reward function with R(s, a) giving the immediate reward for performing action a in state s and T ⊆ S is a set of terminal states that mark the end of an episode. Furthermore, to formulate the delayed rewards in summarisation, we let R(s, a) = 0 if P(s, a) ̸∈ T, so as to ensure that non-zero rewards only appear in the last step of each episode.

In extractive summarisation, the components in Mx are defined as follows. S is the set of all possible states, i.e. permutations of sentences from x. Note that Yx is a subset of S because Yx only includes the summaries complying with the length requirement, but S includes all possible extractive summaries. Two types of action constitute A: add a new sentence from the input document cluster x to the current draft summary and terminate the generation. T includes all the over-length summaries and an absorbing state sT . If action a is terminate, P(s, a) = sT regardless of the current state s. The reward function R(s, a) returns σx(s) if action a is terminate, a negative reward if the current state s is an overlength summary and 0 otherwise. We denote this MDP by Mx(σx) to highlight that it uses σx as rewards.

A policy π : S × A → [0, 1] defines how actions are selected: π(s, a) is the probability of selecting action a in state s. In the context of summarisation, we slightly abuse the notation by letting π(y|x) denote the probability of policy π generating y ∈ Yx given input x. We say a policy π is proper if ∑y∈Yx π(y|x) = 1, i.e. π does not generate illegal outputs. Then, the expected reward of performing proper policy π is:

The goal of RL is to find the optimal policy π∗ that has the highest expected reward: π∗ = argmaxπ Rσx (π|x). Note that π∗x is a probability distribution that assigns non-zero probabilities only to the optimal outputs for x, i.e. π∗ (y|x) > 0 only if σx(y) = |Yx|. Hence Rσx (π∗ |x) = |Yx|.

3 Proof of Convergence for RELIS

In this section, we prove that if the errors in both L2R and RL are bounded, the error of the final output of RELIS is a linear polynomial of the errors from the two steps. First, we define convergent L2R, which can learn an approximated ranking ˆσU x "close" to the ground-truth ranking σ∗x .

Definition 1. Let U be the utility function learnt by an L2R algorithm. For x ∈ X, let ˆσU x be the ranking derived from U on Yx. The L2R algorithm is ϵ-convergent with respect to σ∗x if there exists a non-negative integer ϵ such that

Some L2R algorithms are ϵ-convergent under realistic conditions. For example, the quick-sort based L2R algorithm proposed by Maystre and Grossglauser [2017] is ϵ-convergent with respect to pairwise oracles, when it obtains a sufficiently large number of preferences. Next, we define convergent RL algorithms that guarantee to learn near-optimal policies.

Definition 2. Let Mx(σx) denote the episodic MDP for an NLG task given input x ∈ X, which uses a ranking function σx over Yx as its reward function. An RL algorithm is δ-convergent for Mx(σx) if there exists δ ∈ R≥0 such that

where π∗ is the optimal policy for Mx(σx) and πn is the policy of the RL algorithm after n episodes of learning. 1

Many RL algorithms have been proven to be δ-convergent, including value-based RL [Sutton et al., 2009], actor-critic [Sutton et al., 1999] and policy gradient [Fazel et al., 2018].

Recall that for an input x from the test set X \X , our goal is to find the optimal policy π∗ for the NLG tuple (σ∗x , Mx(σ∗x )) (see §2). The theorem below shows that if RELIS uses convergent L2R and RL, its output is near-optimal, i.e. the error between the RELIS output and the optimal output is bounded.

1 Since π∗ is the optimal policy for σx, Rσx (π∗ |x) is always higher than the expected reward of any other policy (cf. Eq. 5).

Theorem 1. For a test input x ∈ X \ X, we denote the optimal NLG agent for x by (σ∗x ,Mx(σ∗x )), and its RELIS approximation by (ˆσU x ,Mx(ˆσU x )), where ˆσU x is the approximation of σ∗x learnt by an ϵ-convergent L2R algorithm. Let π∗ be the optimal policy for Mx(σ∗x ) and ˆπn the proper policy for Mx(ˆσU x ) learnt by a δ-convergent RL algorithm for n episodes. Then, as n approaches positive infinity, Rσ∗x (ˆπn|x) ≥ Rσ∗x (π∗ |x) - δ - ϵ.

Proof. We denote the optimal policy for Mx(ˆσU x ) as ˆπ∗ . Hence from Eq. (7) we have:

For any y ∈ Yx, from Eq. (6) we have

Using Eq. (9), we can bound RˆσU x (ˆπn|x) with any positive n value (see Eq. (5)):

Note that ∑y∈Yx ˆπn(y|x) = 1 in Eq. (10) because ˆπn is a proper policy (see §2). Combining Eq. (8) and (10), we get

Since ˆπ∗ is the optimal policy for MˆσU x , according to Eq. (5), RˆσU x (ˆπ∗ |x) = |Yx|. Similarly, Rσ∗x (π∗ |x) = |Yx|. Hence we can replace RˆσU x (ˆπ∗ |x) in Eq. (11) with Rσ∗x (π∗ |x) and obtain limn→∞ Rσ∗x (ˆπn|x) ≥ Rσ∗x (π∗ |x) - δ - ϵ.

4 Experimental Setup

Task and datasets. We evaluate RELIS for extractive multi-document summarisation on three benchmark datasets from the Document Understanding Conferences (DUC) 2 described in Table 1. Each dataset contains a set of document clusters. For each cluster, the target is to create a summary with at most 100 words. Each cluster is accompanied with several human-generated summaries, denoted as rx, that we use for training and evaluation. To decide the best parameters, we perform 10-fold cross validation on DUC'01.

Ground-truth reward oracle. For x ∈ X, we use a ROUGE-based U ∗ to induce the ground-truth σ∗x . We measure the quality of a summary y ∈ Yx by U ∗ (y, x) = R1(y, rx) +2R2(y, rx), where R1 and R2 denote the average ROUGE-1 and ROUGE-2 recall metrics, respectively. R1 and R2 are arguably the most widely used metrics to approximate human evaluation of summary quality. The R2 scores for optimal extractive summaries are usually half of their R1 scores [Gao et al., 2018], so we multiply R2 by 2 to balance the impact of R1 and R2. Next, we describe how we approximate the ground-truth reward.

2 https://duc.nist.gov/

4.1 Approximated Reward Oracle

Recall that the goal of L2R is to learn the utility function U using pointwise or pairwise preferences (see §2). In pointwise L2R, we sample N = 3000 different summaries for each document cluster in x ∈ X by randomly selecting sentences from x until the length limit is reached. Using larger N does not significantly increase the quality of ˆσU x but increases the training time. We use the ground-truth ranking σ∗x over the |X| · N samples to learn the utility function U by minimising the MSE loss from Eq. (1). In pairwise L2R, we randomly draw K = 105 of the |X| N·(N-1) 2 possible pairs of the |X| · N sampled summaries to compute U by minimising LCE, LMR or LIM from Eq. (2) - (4). Preliminary results suggest that increasing K to 106 does not benefit the performance but significantly slows down the training, while decreasing it to 104 significantly harms the quality of ˆσU x .

We use a linear model to approximate the utility function, i.e. U(y, x) = w · φ(y, x), where φ(y, x) encodes y for input x as a vector by concatenating the following features:

• The negative Jensen-Shannon divergence between unigrams, bigrams and named entities in y and x.
• The summary quality evaluation heuristics proposed by Rioux et al. [2014].
• TFIDF values averaged over all tokens and named entities in y [Peyrard and Gurevych, 2018].
• The average number of document clusters a word or named entity appears in.
• Rate of named entities from x appearing in y.
• The percentage of tokens in y that belong to some named entities in x.
• The redundancy feature proposed by Peyrard and Gurevych [2018], applied to unigrams, bigrams and named entities.

We additionally use two Convolutional Neural Network (CNN) architectures to generate auto-encoded features: StdCNN [Kim, 2014] and PriorSum [Cao et al., 2015]. To train these auto-encoders, we follow Cao et al. [2015] and feed only the embeddings of the words of y into these models. We add a linear layer as the last layer to map the output vector of these models to a U value. Full settings of these models are in the supplementary material. For each x ∈ X \ X, we measure the quality of the approximated ranking ˆσU x by its ranking correlation to the ground-truth σ∗x . We consider two ranking correlation metrics: Spearman's ρ ∈ [-1, 1] and the Normalized Discounted Cumulative Gain (NDCG) on the top

1% items. NDCG ∈ [0, 1] puts more emphasis on the top elements with logarithmic decay weighting . For both metrics, higher values indicate stronger correlations .

We train the utility function U with the loss functions in Eq. (1)-(4) and we find that using different loss functions does not significantly 3 change performance (see supplementary material). However, the cross-entropy loss consistently results in marginally better performance than the others, and hence we use it throughout our experiments. We find that under all examined settings, the CNN-based features underperform the other features. Using the CNN-based features together with other features also worsen the quality of ˆσU x . The reason is because both PriorSum and StdCNN only encode the summaries' document-independent features [Cao et al., 2015]. Encoding document-dependent features requires more sophisticated neural models [Wu and Hu, 2018; Narayan et al., 2018] which require considerable time, data and parameter tuning. This undermines the benefits of RELIS. We leave the research for efficient reward representation learning for future work.

4.2 RELIS Setup

We test RELIS on all three DUC datasets as follows. In line with Cao et al. [2017] and Ren et al. [2018], we split train and test data in the "leave-one-out" manner so that documents from two datasets are used as the training set, X, and documents from the rest as the test set X \ X. In each run in the "leave-one-out" experiments, we randomly select 30% data from the training set as the dev set, and select the model with the best performance on the dev set. We use Adam with initial learning rate 10-2 . The number of epochs is 10 and batch size is 2. As for RL in RELIS, we use the same temporal difference algorithm as Rioux et al. [2014]. Full details of our parameter selection and results of using different loss functions are in the supplementary material.

5 Results

Table 2 compares the quality of our ˆσU x with other widely used rewards for input-specific RL (see §4). ˆσU x has significantly higher correlation to the ground-truth ranking compared with all other approaches, confirming that our proposed L2R method yields a superior reward oracle.

In Table 3, we compare RELIS with non-RL-based and RL-based summarisation systems. For non-RL-based systems, we report ICSI [Gillick and Favre, 2009] maximising the bigram overlap of summary and input using integer linear programming, PriorSum [Cao et al., 2015] learning sentence quality with CNNs, TCSum [Cao et al., 2017] employing text classification of the input documents, the variant of TCSum without the text classification pre-training (TCSum-) and SRSum [Ren et al., 2018], which learns sentence relations with both word- and sentence-level attentive neural networks to estimate salience.

3 In all experiments, we preform statistical significant test by two-tailed t-test and p-value < 0.01.

For RL-based systems, we re-implement REAPER [Rioux et al., 2014] as an input-specific RL, and DeepTD as a cross-input RL. DeepTD is adapted from the DQN-based RL summariser [Yao et al., 2018] and is trained by taking U ∗ as the rewards (see §4). It uses InferSent to represent summaries. To improve the efficiency and performance of DeepTD, we use memory replay and periodic update. Further details and the algorithm of DeepTD are in the supplementary material.

RELIS significantly outperforms the other RL-based systems. Note that RELIS and REAPER use the identical RL algorithm for input-specific policy learning; hence the improvement of RELIS is due to the higher quality of the L2R-learnt reward ˆσU x . RELIS outperforms DeepTD because training cross-input policies requires much more data than available in the DUC datasets. At the same time, RELIS performs on par with neural-based TCSum and SRSum, while it requires significantly less data and time to train, as shown next.

We run RELIS, SRSum, DeepTD and REAPER on the same workstation with a 4-core CPU, 8GB memory and no GPUs. Table 4 compares their average training and test time for each document cluster. RELIS reduces the training time of SRSum by two orders of magnitude. At test time, RELIS takes reasonable time to train the input-specific policy, and we believe that it can be further reduced by using more efficient RL algorithms and employing techniques like memory replay or reward shaping.

Unlike TCSum, RELIS requires no additional training data: TCSum uses 1.8 million news articles from New York Times and their category annotations (e.g. Health, Politics, Business) for training. It is worth noting that without using such a massive extra data for the text classification step, the performance of TCSum significantly drops (see TCSum- in Table 3). The training time of TCSum is unlikely to be shorter than RELIS since TCSum requires to train a CNN-based text classifier before training a CNN-based sentence selector.

To summarise, RELIS significantly outperforms RL-based models, and it yields competitive performance compared with the state-of-the-art neural summarisers, with the benefit of needing less training time and data.

6 Discussion &RelatedWork

RELIS is proposed as a RL-based summarisation paradigm, but it can be applied to other NLG tasks where RL is widely used, e.g., translation, sentence simplification and dialogue generation. For example, to apply RELIS to translation, we just let X (see §2) be the set of texts in the source language and let Yx be the set of all possible translations in the target language for input x; and the error bound of RELIS (Theorem 1) still holds as it is indifferent to the contents in X and Yx. Hence, in this section, we discuss the related work in the context of NLG in general.

Reward learning recently receives increasing interests from the machine learning community [Ibarz et al., 2018; Zheng et al., 2018], but it is largely overlooked in NLG until now. Unlike classic RL applications, e.g. robotics and games, where rewards are provided or easy to design, NLG tasks lack strong metrics to measure the quality of the output. Well-known rewards, e.g. ROUGE, are criticised for their low correlation with human evaluations [Chaganty et al., 2018]. Recent work suggests that improving the reward function boosts the performance of RL-based NLG [Kryscinski et al., 2018].

Besides using metrics such as BLEU and ROUGE as rewards to train RL-based NLG, novel rewards have been designed. Kryscinski et al. [2018] propose a new reward function for encouraging RL-based summarisers to prefer novel words in abstractive summaries. For sentence simplification, Zhang and Lapata [2017] propose a reward function measuring the simplicity, relevance and grammatical correctness of candidate outputs. For machine translation, Nguyen et al. [2017] propose a simulated user, which simulates human's ratings on translations, and they use the simulated user to provide rewards for an RL-based translator. However, all rewards discussed above require reference outputs, unlike our learnt reward function which can be used to provide rewards at test time when no reference outputs are available.

Wu and Hu [2018] and Bosselut et al. [2018] recently propose to use a large volume of unlabelled data to learn a scorer measuring the discourse coherence degree of sentences, and use the scorer as rewards to train cross-input RL. We go beyond their work by proving the soundness of the combination of reward learning and RL, and training input-specific instead of cross-input policies so as to reduce training time and data.

RL-based interactive NLG methods elicit human feedback as rewards. Kreutzer et al. [2018] elicit pointwise and pairwise feedback on candidate translations to train a cross-input policy. Gao et al. [2018] propose using active learning to select appropriate candidate summary pairs and acquire human preferences to improve a heuristics-based reward. However, these methods require much feedback to bring satisfactory results, e.g., at least 50 summary pairs to yield significant improvements [Gao et al., 2018]. RELIS can be used as a pretraining stage for interactive methods, as RELIS first learns a high-quality cross-input reward function and then uses the interactive NLG techniques to elicit a small amount of feedback to fine-tune a user- and input-specific reward function, so at to generate higher-quality and personalised results.

7 Conclusion

We propose a novel RL paradigm called RELIS, which learns a reward function from a reward oracle with learning-to-rank (L2R) algorithms at training time, and then uses the learnt reward to train input-specific RL policies at test time. Compared with the widely employed cross-input RL-based summarisation approaches, RELIS avoids the expensive learning of cross-input policies but, instead, efficiently performs L2R and input-specific RL learning. Moreover, RELIS avoids the arduous reward design required in input-specific RL-based summarisation approaches. We prove that, with proper L2R and RL algorithms, RELIS guarantees to produce near-optimal outputs. Our experiments show that even with linear L2R and standard RL algorithms, RELIS yields performance on par with the state of the art while only requiring a small fraction of data and time to train. Our work lays the theoretical foundation for reward learning in NLG, and we hope it will encourage further research in this direction.

Acknowledgements

This work has been supported by the German Research Foundation (DFG), as part of the QA-EduInf project (GU 798/18-1 and RI 803/12-1) and through the German-Israeli Project Cooperation (DIP, DA 1600/1-1 and GU 798/17-1).