# Write Summary Step-by-Step:
A Pilot Study of Stepwise Summarization

Xiuying Chen∗, Shen Gao∗, Mingzhe Li, Qingqing Zhu, Xin Gao†, Xiangliang
Zhang† Xiuying Chen and Xin Gao are with the Computer, Electrical and
Mathematical Sciences and Engineering division at KAUST, Saudi Arabia, (email:
xiuying.chen@kaust.edu.sa,xin.gao@kaust.edu.sa).Shen Gao is with the
University of Electronic Science and Technology of China, China (email:
<EMAIL_ADDRESS>Mingzhe Li is with Ant Group, China (email:
limingzhe.lmz@antgroup.com). Qingqing Zhu is with Peking university, China
(email: zhuqingqing@pku.edu.cn.).Xiangliang Zhang is with University of Notre
Dame, America and secondly affiliated with KAUST (email:
xzhang33@nd.edu.)*These authors contributed equally to this
work.†Corresponding authors.

###### Abstract

Nowadays, neural text generation has made tremendous progress in abstractive
summarization tasks. However, most of the existing summarization models take
in the whole document all at once, which sometimes cannot meet the needs in
practice. Practically, social text streams such as news events and tweets keep
growing from time to time, and can only be fed to the summarization system
step by step. Hence, in this paper, we propose the task of Stepwise
Summarization, which aims to generate a new appended summary each time a new
document is proposed. The appended summary should not only summarizes the
newly added content but is also coherent with the previous summary, to form an
up-to-date complete summary. To tackle this challenge, we design an
adversarial learning model, named Stepwise Summary Generator (SSG). First, SSG
selectively processes the new document under the guidance of the previous
summary, obtaining polished document representation. Next, SSG generates the
summary considering both the previous summary and the document. Finally, a
convolutional-based discriminator is employed to determine whether the newly
generated summary is coherent with the previous summary. For the experiment,
we extend the traditional two-step update summarization setting to multi-step
stepwise setting, and re-propose a large-scale stepwise summarization dataset
based on a public story generation dataset. Extensive experiments on this
dataset show that SSG achieves state-of-the-art performance in terms of both
automatic metrics and human evaluations. Ablation studies demonstrate the
effectiveness of each module in our framework. We also discuss the benefits
and limitations of recent large language models on this task.

###### Index Terms:

Text generation, abstraction summarization, neural networks.

##  I Introduction

TABLE I: Example of new document-summary pair from our dataset. In the
previous summary, the character Stephanie claims that she can continue to
work, but in the new document, she cannot focus on her work. _Previous
Summary:_ Stephanie concedes that perhaps she did have a little stroke, but
she is fine, still a force to be reckoned with. Nick calls for a meeting and
Stephanie tells Pam that she will be there despite her protests. She needs to
prove she can still do what she does. Nothing will change that. Nick calls her
a one woman dynamo.
---
_Newly added document:_ … Marcus says they were good people but “finding mom
was the greatest thing that could have happened.” Marcus asks if he has any
other kids. Justin says he tried and breaks down as he says Marcus is there
before him. Everyone looks at numbers as Nick says they need to hire a third
shift. Bridget says the Economy still has not recovered. They leave the
decision to Stephanie and tell her to look at page 20. She says she does not
need to look at a page she knows what is best for the company and will go with
her instincts. She says “if there is a problem with that, there’s the door.”
Nick throws Jackie a look of confusion.
_New Summary:_ However, during the meeting Stephanie can not concentrate on
the figures and offers that she will do what she always has done on instinct
and it’s that or show her the door. Marcus wants his question answered.

First, we will answer three possible questions to illustrate the main
contributions of this paper.

###  I-A What is stepwise summarization?

Nowadays, social text streams such as news events and tweets spread throughout
the Internet, and summarization is an ideal solution to provide a condensed,
informative document reorganization for faster and better representation of
information evolution [1]. Most of the existing summarization approaches take
in the whole document and generate the corresponding summary all at once.
However, in practice, text streams come in sequence instead of simultaneously,
and it is important for readers to get the most up-to-date information each
time a new event occurs. Hence, we propose the task of stepwise summarization
task, which aims to generate a new appended summary each time a new document
is proposed. The appended summary should not only summarize the newly added
content but also be coherent with the previous summary, so as to form an up-
to-date complete summary.

In such a scenario, the previous summary, i.e., summary of previous documents
in the stream, is important in two ways. On one hand, the newly generated
summary must be coherent with the previous summary. Considering Table I which
is an episode recap collected from a fan-contributed website, the new document
introduces that the character Stephanie cannot concentrate on her work, while
the previous summary describes that she says she is able to work despite her
protests. Hence, the appended new summary summarizes the new status of
Stephanie with a turning sentence. On the other hand, the previous summary
helps capture the salient part of the new document. To this end, in this
paper, we propose a Stepwise Summary Generator (SSG) which incorporates both
the previous summary and newly added document to generate a more coherent
appended summary, so as to obtain the whole summary of a text stream. We show
an example in Figure 1 to illustrate the task definition of stepwise
summarization.

###  I-B Why not traditional abstractive summarization?

On one hand, if traditional summarization models only take the current newly
added document as input to generate the corresponding summary, they will lose
the information from previous documents that is helpful for current
summarization. The generated summaries may also be incoherent with each other.
On the other hand, if traditional models take all existing documents as input,
it is easy to confuse information between events and provide inaccurate period
division for readers. It is also redundant to repeatedly generate the same
summary for previous documents. The stepwise summarization is related to
stream summarization and update summarization, where we give the comparison in
Figure I and the related work section.

###  I-C How to conduct stepwise summarization?

To begin with, SSG captures the main points in the document with the help of
the previous summary. Concretely, after processing the document and previous
summary through self-attention, we propose a selective recurrent unit to
selectively processes document representation under the guidance from the
previous summary, so that document representation is further polished. Second,
a decoder is used to generate a new summary, incorporating both the polished
representations of documents and the summary. Finally, the training of our
framework is conducted in an adversarial way, where we employ a convolutional
discriminator to distinguish whether the generated summary is coherent with
the previous summary. Extensive experiments demonstrate that SSG significantly
outperforms the state-of-the-art summarization baselines in ROUGE metrics and
human evaluations.

Figure 1: Comparison between stream summarization, update summarization, and
stepwise summarization. Stream summarization [2]: a large number documents are
taken as input, and some of the documents are selected as summary. Update
summarization [3]: the task is to summarize the new document, assuming the
reader already knows about previous documents. Stepwise summarization: This
setting does not require the reader to have any prior knowledge about the text
stream. The generated summary contains all the information about the text
stream, and is kept fluent all the time steps.

Our contributions can be summarized as follows:

$\bullet$ We propose the task of stepwise summarization, which generates an
appended summary each time a new document is generated, considering previous
information.

$\bullet$ To address this task, we introduce a paradigm that leverages the
previous summary to enhance the current one, using an interaction and
coherence discriminator.

$\bullet$ We release a large-scale stepwise summarization dataset.
Experimental results on this dataset demonstrate the effectiveness of our
proposed framework.

##  II Related Work

###  II-A Text summarization.

Text summarization can be classified into extractive and abstractive methods.
Extractive methods [4, 5, 6, 7, 8] directly extract the sentences or text span
from the input document as the summary. Specifically, [9] proposed the joint
sentence scoring and selection framework which directly predicts the relative
sentence importance score according to both sentence content and previously
selected sentences. However, summaries generated by extractive methods always
suffer from redundancy problems and are not as flexible as abstractive
methods. Recently, with the emergence of neural network models for text
generation, a vast majority of efforts have been dedicated to abstractive
summarization [10, 11, 12, 13, 14]. For example, [15] used sentence-level
attention to modulate word-level attention such that words in less attended
sentences are less likely to be generated. [16] used a data-efficient content
selector to emphasize phrases in a source document that should be part of the
summary. To tackle the out-of-vocabulary problem in abstractive summarization
models, some researchers employ a copy mechanism to copy certain words from
the input document to the summary [17, 18].

TABLE II: Corpus bias towards extractive methods in the CNN/DailyMail [19], Newsroom [20], XSum [21], Reddit [22] and SSD datasets. We show the proportion of novel $n$-grams in gold summaries. We also report ROUGE scores for the extractive Lead and abstractive PG baseline. Results are computed on the test set.  Datasets | % of novel n-grams in gold summary | lead | PG | PG/lead
---|---|---|---|---
unigrams | bigrams | trigrams | 4-grams | R1 | R2 | RL | R1 | R2 | RL | Ratio (R-L)
CNN/DailyMail | 19.50 | 56.88 | 74.41 | 82.8 | 39.6 | 17.7 | 36.2 | 36.4 | 15.7 | 33.4 | 0.92x
Newsroom | 19.53 | 48.39 | 59.38 | 64.06 | 30.5 | 21.3 | 28.4 | 26.0 | 13.3 | 22.4 | 0.78x
XSum | 35.76 | 83.45 | 95.50 | 98.49 | 16.3 | 1.6 | 11.9 | 29.7 | 8.8 | 22.6 | 1.89x
Reddit | 48.97 | 84.45 | 94.50 | 97.82 | 3.4 | 0.0 | 3.3 | 18.3 | 6.5 | 17.9 | 5.42x
SSD | 38.31 | 85.35 | 97.20 | 98.86 | 26.31 | 4.79 | 23.56 | 36.83 | 9.07 | 34.37 | 1.45x

###  II-B Timeline summarization.

Timeline summarization was firstly proposed by [23], and it involves
extracting a single sentence from each event within a news topic. Since the
original work, a series of works [24, 25, 26] further investigate this task.
[24] aimed to return the evolution trajectory along the timeline, emphasizing
relevance, coverage, coherence, and cross-date diversity. [27, 28] followed
the style of abstractive timeline summarization. More recently, [29] examined
both the general approaches to this task and its current state of resolution,
and [30] suggested enhancing timeline summarization by generating multiple
summaries.

However, timeline summarization also belongs to the classic static
summarization framework, dealing with a static corpus instead of a dynamic,
continuously growing stream.

###  II-C Streaming summarization.

Stepwise summarization is also similar to the streaming summarization task,
which summarizes a stream of documents aligned on the timeline. Initial works
include [31], where they aim to deal with dynamic, quickly arriving, and
large-scale tweet streams. They proposed a prototype called Sumblr
(SUMmarization By stream cLusteRing) for tweet streams. Following their work,
[32] improved the efficiency of this process. Processing is done in a single
pass, removing the need to save any input data and improving the running time.
[33] further focused on time-aware multi-viewpoint summarization of
multilingual social text streams. Both of timeline and streaming summarization
tasks take stream documents all at once, while in our stepwise summarization
task, the input documents come in sequence.

###  II-D Update summarization.

Our task shares some common features with the update summarization task, which
also aims to summarize key information from documents arriving in a sequence.
Concretely, the setting typically includes two document sets A and B, and the
task is to summarize B assuming the reader already knows about A [3]. The
challenge in update summarization is to deal with multi-document
summarization, handling redundancy between multiple documents, as well as the
redundancy between A and B. This task differs from ours because its generated
summaries do not form a coherent text sequence. This series of update
summarization works mainly focus on TAC dataset [3], where the task is to
extract a summary of a subsequent set of newswire articles for the same topic,
under the assumption that the reader has already read the previous documents.
This dataset contains only 48 topics with 960 documents. Initial works include
[34], which is a scalable sentence scoring method for query-oriented update
summarization. [35] presented an unsupervised probabilistic approach to model
novelty in a document collection and apply it to the generation of update
summaries. MCL [36] is the state-of-the-art extractive work on this dataset,
which examines how integrating a semantic sentence similarity into an update
summarization system can improve its results.

##  III Stepwise Summarization Dataset

Existing large-scale summarization datasets cannot be used for stepwise
summarization, since they only contain information about a single event. In
contrast, a TV show episode recaps usually records the developments of events
over time. Thus, our dataset, named Stepwise Summarization Dataset (SSD), is
re-collected from a public story generation dataset TVMegaSite [37]. As
illustrated in Figure 2, each case in our dataset contains a document stream
and the corresponding streaming summary. Each document stream contains several
documents, and each summary stream contains the corresponding summaries. For
each doc-summ pair in doc-summ stream, we name all summaries and all documents
before this pair as previous summary and previous document, and document in
this pair as new document.

###  III-A Dataset collection.

In each case in the story generation dataset TVMegaSite, there is a detailed
TV show episode recaps and a brief summary of the episode. Since the episode
recap is mostly arranged according to the sequence of events, there is a
strict logic in it. Consequently, the summary often follows the same logical
order as a good-quality summary does. Hence, an episode recap can be regarded
as the streaming data source, and the summary summarizes the stream in order.
To select document-summary pairs that establish such correspondences, we first
use the text segmentation technique to split the summary stream into segments.
The episode recap is separated into paragraphs in the original dataset. Then,
we calculate the mean of ROUGE-1, ROUGE-2, and ROUGE-L scores between each
summary segment and document paragraphs. We choose the section with the
highest ROUGE-L score as the corresponding source document for the summary
segment. For each source paragraph, the summary segment that has the highest
ROUGE score with it is selected as its corresponding summary. A document
stream with less than two paragraphs will also be filtered. Overall, SSD
consists of 29,376 doc-summ pair samples, 5,208 validation samples, and 5,718
test samples. A document consists of 610 words, and a summary contains 87
words on average. Document streams containing 2,3,4, and 5 documents make up
35%, 22%, 18%, and 5% of the total respectively.

Our dataset is notably the first large-scale stepwise summarization dataset
and will be released for further research. Detailed statistics for SSD and a
comparison with other popular text summarization datasets are listed in Table
II. Lead selects the first sentence for Reddit dataset, and the first three
sentences for others. Next, we demonstrate the quality of the dataset and then
discuss some abstractive characteristics of SSD compared to existing
summarization datasets.

Figure 2: Illustration of a sample in the stepwise summarization dataset.
Figure 3: Overview of SSG. We divide our model into three parts: (1) Stream-
aware Encoder (left) selectively processes document under guidance from the
previous summary. (2) Summary generator (middle) generates a summary taking
both factors above into consideration. (3) Coherence discriminator (right)
determines whether the generated summary is coherent with the previous one.

###  III-B Stepwise summarization characteristics.

Human evaluation.  We assess the quality of our stepwise summarization data
from two aspects: whether the source summary corresponds to the document, and
whether the previous summary relates to the new document. The first aspect
reflects the quality of the summarization attribute and the second reflects
the stream attribute. Summarization attribute here means whether the summary
can correctly summarize important information from document, and stream
attribute means whether the previous information relates to current document.
We randomly sample 100 cases from SSD and perform Amazon’s Mechanical Turk
tests, where three annotators are asked to assess the aforementioned aspects
for each selection, i.e., with “yes” and “no”. The result shows that “yes”
accounts for 94.3% and 95.0% of the answers for the summarization attribute
and stream attribute, while “no” only takes up 5.7%, and 5.0%, respectively.
This demonstrates that the dataset does indeed have good summarization and
stream attributes. The kappa statistic is 0.57, which demonstrates moderate
agreement between turkers.

Automatic evaluation.  We also propose an automatic method to evaluate the
dataset, since the original TVMegaSite dataset provides all the mentioned
character names. Ideally, if a character exists in a summary, he/she should
also be included in the source paragraph, and vice versa. Hence, we calculate
the percentage of cases when a character name exists in the paired document
and summary (good case), and the cases when it only exists in the summary (bad
case). The result shows that 89% of cases are good cases. This again
demonstrates the good quality of the dataset.

###  III-C Abstractive characteristics.

SSD has various abstractive characteristics, including strong abstractness and
weak lead bias, as shown in Table II. About 38.31% unigrams and 96.68% 4-grams
in the gold summary are novel n-grams that do not exist in the input document,
indicating strong abstractness in the dataset. This leads to a necessity for
abstractive summarization methods since these n-grams cannot be generated by
extractive models. What is more, SSD has a weak lead bias. The Lead baseline
is to select the first three sentences in the document as a summary, and the
PG baseline corresponds to the strong abstractive summarization baseline [18].
The higher the PG/Lead score, the weaker the lead bias of the dataset. News
datasets such as CNN/DailyMail and Newsroom always have a strong lead bias,
with a PG/Lead ratio of less than one. Datasets such as XSum and Reddit
overcome this problem. Our dataset also has a weak lead bias, where the
PG/Lead ratio is larger than one.

##  IV Problem Formulation

Before presenting our approach for the stepwise summarization, we first
introduce our notations and key concepts.

To begin with, for a document
$X^{d}=\\{x^{d}_{1},x^{d}_{2},\dots,x^{d}_{T^{d}}\\}$, we assume there is a
previous document-summary pair, where the previous summary is
$X^{s}=\\{x^{s}_{1},x^{s}_{2},\dots,x^{s}_{T^{s}}\\}$. $x^{d}_{i}$ denotes the
$i$-th word in document $X^{d}$, and $x^{s}_{i}$ denotes the $i$-th word in
previous summary $X^{s}$. Given the document $X^{d}$ and previous summary
$X^{s}$, the summary generator generates a summary
$\hat{Y}=\\{\hat{y}_{1},\hat{y}_{2},\dots,\hat{y}_{T^{\hat{Y}}}\\}$. Finally,
we use the difference between the generated summary $\hat{Y}$ and the ground
truth summary $Y=\\{y_{1},y_{2},\dots,y_{T^{Y}}\\}$ as the training signal to
optimize the model parameters.

##  V The Proposed SSG Model

###  V-A Overview

In this section, we propose the _Stepwise Summary Generator_ , abbreviated as
SSG. An overview of SSG is shown in Figure 3, which can be split into three
main parts:

$\bullet$ Stream-aware encoder incorporates the previous summary to calculate
the selective reading gate in the gated recurrent unit, further polishing the
document representation.

$\bullet$ Summary generator generates a summary taking both the polished
document and previous summary into consideration.

$\bullet$ Coherence discriminator uses a convolutional neural network (CNN) to
identify whether the generated summary is coherent with the previous summary.

###  V-B Stream-aware Encoder

We first use an embedding matrix $e$ to map a one-hot representation of each
word in $X^{d}$ and ${X^{s}}$ into a high-dimensional vector space. We then
employ the Transformer encoder [38] initialized by BART [39] to model the
temporal interactions between words, and obtain $h^{d}_{t}$ and $h^{s}_{t}$,
denoting the hidden state of the $t$-th word in $X^{d}$, $X^{s}$ respectively.

To further model the interaction between a document and previous summary, we
propose to utilize the previous summary to selectively read and process the
document, in order to emphasize the words that are related to the previous
summary. This is achieved by an RNN made up of Selective Reading Unit (SRU).
Our inspiration comes from [40], which iteratively polished the document
representation using document words. However, in SSG, we use the previous
summary representation to polish the word representations in the document.

We begin by introducing the original GRU cell, which consists of an update
gate vector ${u^{g}_{t}}$ and a reset gate vector ${r^{g}_{t}}$. In our case,
the output is the polished representation of ${h^{d}_{t}}$, which is also the
hidden state in the SRU cell, and we denoted as $h^{g}_{t}$. For each time
step $t$ with the document representation $h^{d}_{t}$ and the previous hidden
state ${h^{g}_{t-1}}$, the updated hidden state
${h^{g}_{t}}=\text{GRU}({h^{d}_{t}},{h^{g}_{t-1}})$ is computed by:

$\displaystyle{u^{g}_{t}}$
$\displaystyle=\sigma({W_{1}}{h^{d}_{t}}+{U_{1}}{h^{g}_{t-1}}+{b_{1}}),$ (1)
$\displaystyle{r^{g}_{t}}$
$\displaystyle=\sigma({W_{2}}{h^{d}_{t}}+{U_{2}}{h^{g}_{t-1}}+{b_{2}}),$ (2)
$\displaystyle{\tilde{h}^{g}_{t}}$
$\displaystyle=\text{tanh}({W_{3}h^{d}_{t}}+{r^{g}_{t}}\circ{U_{3}h^{g}_{t-1}}+{b_{3}}),$
(3) $\displaystyle{h^{g}_{t}}$
$\displaystyle={u^{g}_{t}}\circ{\tilde{h^{g}_{t}}}+(1-{u^{g}_{t}})\circ{h^{g}_{t-1}},$
(4)

where $W$ and $b$ are trainable parameters, $\sigma$ is the sigmoid activation
function, and $\circ$ is element-wise multiplication. Here, due to the way
$u_{t}^{g}$ is calculated, it is sensitive to the position and order of the
current input document, but loses information from the previous summary. In
SRU, we propose to take the previous summary into consideration when
calculating $u_{t}^{g}$:

$\displaystyle{f_{t}}$ $\displaystyle=[h^{d}_{t}\circ{q};{h^{d}_{t}};{q}],$
(5) $\displaystyle{F_{t}}$
$\displaystyle={W_{4}}\text{tanh}({W_{5}}{f_{t}}+{b_{5}})+{b_{4}},$ (6)
$\displaystyle{u^{\prime}_{t}}$
$\displaystyle=\frac{\text{exp}({F_{t}})}{\sum^{T^{d}}_{j=1}\text{exp}({F_{j}})},$
(7)

where $[;]$ denotes concatenation, ${h^{d}_{t}}$ is the $t$-th word
representation, and ${q}$ is the average of the previous summary
representations $h^{s}_{\cdot}$. Equation 4 now becomes:

$\displaystyle{h^{g}_{t}}$
$\displaystyle={u^{\prime}_{t}}\circ{\tilde{h}^{g}_{t}}+(1-{u^{\prime}_{t}})\circ{h^{g}_{t-1}}.$
(8)

In this way, SSG automatically decides the extent to which the information of
each word should be updated based on its relationship with the previous
summary.

###  V-C Summary Generator

The summary generator aims to generate a summary based on the input document
and the previous summary. We also employ the classic Transformer architecture
as the decoder. Generally, each layer in the decoder consists of three parts:
a multi-head self-attention mechanism, a multi-head cross-attention mechanism,
and a fully connected feed-forward network.

For each layer, at the $t$-th decoding step, we first apply the self-attention
on the masked summary embeddings, denoted as $g_{t}$. The self-attention sub-
layer with a masking mechanism is used to encode the decoded information. The
masking mechanism ensures that the prediction of the position $t$ depends only
on the known output of the position before $t$.

$\displaystyle\tilde{g}_{t}=\text{LN
}\left(g_{t}+\text{MSAttn}\left(g_{<t},g_{<t}\right)\right),$ (9)

where LN is the layer normalization operation; MSAttn is the masked multi-head
attention operation. Based on $\tilde{g}_{t}$ we compute the cross-attention
scores over polished document:

$\displaystyle z_{a,t}=\text{ReLU}([\tilde{g}_{t}W_{a}(h^{g}W_{b})^{T}]),$
(10)

where $W_{a},W_{b}\in\mathbb{R}^{d\times d}$, $d$ is the hidden dimension,
$h^{g}$ is the concatenation of all $h^{g}_{i}$ for $i\in[1,T_{d}]$, and
$z_{a,t}\in\mathbb{R}^{T^{d}}$. Similarly, we also calculate the cross-
attention scores over the previous summary:

$\displaystyle z_{b,t}=\text{ReLU}([\tilde{g}_{t}W_{c}(h^{s}W_{d})^{T}]),$
(11)

where $z_{b,t}\in\mathbb{R}^{T^{s}}$.

The attention weights $z_{a,t}$ and $z_{b,t}$ are then used to obtain the
context vectors $c_{a,t}$ and $c_{b,t}$, respectively. Take the document
context vector as an example:

$\displaystyle c_{a,t}=z_{a,t}h^{g}.$ (12)

These context vectors, treated as salient contents summarized from various
sources, are concatenated with the decoder hidden state $\tilde{g}_{t}$ to
produce the distribution over the target vocabulary:

$\displaystyle P_{t}^{\text{vocab
}}=\text{Softmax}\left(W_{o}\left[\tilde{g}_{t};c_{a,t};c_{b,t}\right]\right).$
(13)

All the learnable parameters are updated by optimizing the negative log
likelihood objective function of predicting the target words:

$\displaystyle\mathcal{L}_{s}=-\textstyle\sum_{t=1}^{T^{y}}\log
P_{t}^{\text{vocab}}\left(y_{t}\right).$ (14)

###  V-D Coherence Discriminator

Previous work [41] has found that using a cross-entropy loss alone is not
enough for generating coherent text. Hence, we employ a discriminator to
provide additional training signals for the summary generator. The goal of
this discriminator is to determine whether the new summary is coherent with
the previous one. The generated summary is treated as the negative sample and
the ground truth answer as the positive one.

Similar to before, we use the same embedding matrix and another attention
mechanism to process $\hat{y}$ as $h^{y}_{t}$. Since the ground truth is
encoded by a transformer that is different from the decoder transformer, we
use a linear projection to transform the high-dimensional space of $h^{y}_{t}$
to the same space as the decoder hidden state $g_{t}$:

$\displaystyle d^{y}_{t}$ $\displaystyle=W_{z}h^{y}_{t}+b_{z}.$ (15)

We model the interaction between the previous summary and generated one by
concatenating them as $\hat{d}^{y}_{t}=[h^{s}_{t};d^{y}_{t}]$, and the
previous summary and ground truth summary as
$\hat{d}^{g}_{t}=[h^{s}_{t};g_{t}]$. Then, a convolutional layer convolves
$\hat{d}^{*}_{t}$ with multiple convolutional kernels of different widths,
obtaining a sequence of new features $n^{*}_{t}$:

$\displaystyle n^{*}_{t}$ $\displaystyle=\text{relu}(\hat{d}^{*}_{t}\odot
W_{c}+b_{c}),$ (16)

where $\odot$ denotes the convolution operation. For each convolutional
filter, the max-pooling layer takes the maximal value among the generated
convolutional features $n^{y}$ and $n^{g}$, respectively, resulting in a
fixed-size vector $N^{y}$ and $N^{g}$. Finally, we obtain the classification
result $D(\hat{d}^{*})$:

$\displaystyle D(\hat{d}^{*})$
$\displaystyle=\sigma(W_{h}\text{relu}(N^{*})+b_{h}).$ (17)

The training objective of the discriminator is to maximize the log-likelihood
for classification, while the generator aims to maximize the probability of
assigning the correct label to the generated summary:

$\displaystyle\mathcal{L}_{d}$
$\displaystyle=-\left(\log(D(\hat{d}^{y}))+\log(1-D(\hat{d}^{g}))\right),$
(18) $\displaystyle\mathcal{L}_{g}$ $\displaystyle=\log(1-D(\hat{d}^{g})).$
(19)

Overall, the parameters in the convolutional discriminator are optimized by
the loss function $\mathcal{L}_{d}$, while other parameters are optimized by
$\mathcal{L}_{g}$.

##  VI Experimental Setup

###  VI-A Evaluation Metrics

For evaluation, we adopt ROUGE scores [Lin2004ROUGEAP] which are widely
applied to assess summarization quality [15, 5]. The ROUGE metrics compare a
generated summary with a reference summary by computing overlapping lexical
units. We report unigram and bigram overlap (ROUGE-1 and ROUGE-2) as a means
of assessing the informativeness and the longest common subsequence (ROUGE-L)
as a means of assessing fluency. We then use BERTScore [42] to calculate a
similarity score between the summaries based on their BERT embeddings. Since
only using automatic evaluation metrics can be misleading [43], we also
conduct the human evaluation.

###  VI-B Comparison Methods

To evaluate the performance of our proposed model, we compare it with the
following baselines:

Lead3 selects the first three sentences of a document as the summary.
TextRank: [44] proposes to build a graph, then adds each sentence as a vertex
and uses links to represent semantic similarity. MCL: [36] integrates semantic
sentence similarity into an update summarization system. The proposed model is
based on ILP [45], and is easily adapted to a single-document summarization
setting. Transformer is based on attention mechanism proposed in [38]. PG
combines the sequence-to-sequence framework with the copy mechanism from [18].
SAGCopy: a model proposed by [46], which augments Transformer with self-
attention guided copy mechanism. BART: a denoising autoencoder for pretraining
sequence-to-sequence models [39].  PEGASUS: a model pre-trained with extracted
gap-sentences for abstractive summarization [47]. Our model is implemented
based on PEGASUS and BART due to their better performance. We also propose two
simple but intuitive models based on BART and PEGASUS model, i.e., Concat-
prev-summ (CPS), which concatenates a new document with its previous summary,
and Concat-prev-doc (CPD) which concatenates new document with the previous
document. For human evaluation, we also add the performance of the latest
large language model, GPT-3.5.

###  VI-C Implementation Details

We implement our experiments in PyTorch on an NVIDIA A100 GPU. The model is
finetuned based on BART-base. The encoding step is 1000 for a document and 300
for a previous summary. We chose 1000 as our truncation size as we did not
find significant improvement when increasing the input length from 1000 to
1500 tokens. The minimum decoding step is 100, and the maximum step is 300.
The batch size is set to 32. We use Adam optimizer [48] as our optimizing
algorithm. We also apply gradient clipping [49] with a range of $[-2,2]$
during training. For the test, we employ beam search with a beam size of 4 to
generate more fluent summaries.

##  VII Experimental Results

###  VII-A Overall Performance

TABLE III: ROUGE score comparisons between baselines in doc-summ pair level. All our ROUGE scores have a 95% confidence interval of at most $\pm$0.23 as reported by the official ROUGE script. | RG-1 | RG-2 | RG-L | BS
---|---|---|---|---
_Sentence extraction methods_ |
Lead3 | 26.31 | 4.79 | 23.56 | 86.01
TextRank | 32.71 | 6.49 | 29.06 | 85.90
MCL | 33.57 | 6.73 | 29.96 | 85.88
_Other previous information utilization methods_ |
CPD | 33.67 | 7.89 | 30.60 | 86.57
CPS | 33.97 | 7.94 | 30.75 | 86.65
_Text generation methods_ |
Transformer | 26.24 | 5.56 | 24.79 | 86.04
PG | 27.18 | 5.82 | 25.01 | 86.12
SAGCopy | 28.72 | 6.44 | 25.82 | 86.39
BART | 33.30 | 7.55 | 30.18 | 86.42
PEGASUS | 32.35 | 6.91 | 29.78 | 86.10
GPT3.5 | 33.67 | 6.39 | 31.03 | 86.23
SSG (PEGASUS) | 34.23 | 8.08 | 31.24 | 86.54
SSG (BART) | 34.92 | 8.65 | 31.68 | 86.96

We first examine whether our stepwise summarization model outperforms
traditional summarization models. In this setting, performances are evaluated
in doc-summ pair level (in contrast to doc-summ stream level). Table III lists
the performances of all comparison methods in terms of ROUGE scores. Firstly,
extractive methods are competitive with abstractive baselines in terms of
ROUGE score but underperform in BERTScore. This indicates that the extracted
summaries have lower semantic similarity compared with abstractive summaries.
Secondly, abstractive models equipped with pretrained language models
outperform traditional summarization models. GPT-3.5 is competitive in a text-
pair setting. Finally, SSG achieves consistently better performance, with
4.86% and 4.97% improvements over BART in ROUGE-1 and ROUGE-L.

We next examine how effective is previous information in stepwise
summarization. Performances of these CPS and CPD are relatively higher than
BART but worse than SSG, demonstrating that previous information is indeed
helpful for summary generation even by simple concatenation methods, but this
additional information is not the only reason why SSG can achieve good
performance. CPS gives better results than CPD, which proves the superiority
of using the previous summary over using previous documents.

###  VII-B Ablation Study

TABLE IV: ROUGE scores of different ablation models. | ROUGE-1 | ROUGE-2 | ROUGE-L | BS
---|---|---|---|---
SSG w/o SR | 34.01 | 8.20 | 31.04 | 86.57
SSG w/o GAN | 34.38 | 8.41 | 31.28 | 86.86
SSG | 34.92 | 8.65 | 31.68 | 86.96

Next, we conduct ablation tests to assess the importance of the selective
reading module (w/o SR), as well as the discriminator (w/o GAN), and the ROUGE
score results are shown in Table IV. The discriminator provides the scalar
training signal $\mathcal{L}_{d}$ for generator training. Consequently, there
is an increase in performance of 1.27% from SSG w/o GAN to SSG in terms of
ROUGE-L, which demonstrates the effectiveness of the discriminator. As for the
selective reading module, it improves performance by 2.06% compared with SSG
w/o SR, in terms of ROUGE-L, indicating that a deeper interaction between the
previous summary and document further helps summarization.

###  VII-C Performance on Text Stream

Note that previous experiments are based on generating a single summary,
whereas previous summaries are ground truth summaries. To fully simulate a
real text stream scene, we also conduct experiments where the target is to
generate the whole summary stream, as shown in Figure 2. The difference lies
in that SSG now takes a previously generated summary as the previous summary
rather than the ground truth summary. We select several strong abstractive
models in Table III as baselines. As stated in the introduction, there are two
ways of generating a summary stream for traditional abstractive models. The
first involves taking all documents and generating all summaries together,
while the second generates a summary step-by-step. We denote the variations
following the first fashion as *-Together, and the second as *-Split.

The comparison results are listed in Table V. We can see that overall, the
performance of each model under the stepwise summarization setting is similar
to its performance under the original setting. *-Split methods are better than
*-Together, which may be because *-Together tend to mix the information
between documents, while *-Split models can accurately utilize current
document information, even when they do not have access to knowledge from
previous documents. However, none of these models perform as well as SSG,
since it can utilize current document information, while also capturing the
relationship between the current and previous summary. GPT-3.5 falls behind in
a text-stream setting, likely due to difficulty in handling sequential
information. Note that in this setting, the ROUGE score is calculated in terms
of text stream level, thus the results are not directly comparable to results
in Table III.

###  VII-D Human Evaluation and Case Study

We also assessed system performance on the streaming text by human judgments
on 30 randomly selected instances following [50]. Our first evaluation study
quantified the degree to which summarization models retain key information
from the documents following a question-answering (QA) paradigm. The
evaluation size is 1.5 times larger than the original setting [50]. We created
a set of questions based on the multiple gold ground summaries and examined
whether participants were able to answer these questions by reading system
summaries alone. We created 61 questions in total. Examples of questions and
their answers are given in Table VII. We adopted the same scoring mechanism
used in [51], i.e., correct answers are marked with 1, and 0 otherwise. Our
second evaluation assessed the overall quality of the summaries by asking
participants to rate them taking into account the following criteria:
Informativeness, Consistency, and Succinctness. The rating score of each
system ranges from 1 (worst) to 5 (best).

Both evaluations were conducted by three Ph.D. students. Participants
evaluated summaries produced by SAGCopy-Split, BART-Split, GPT-3.5, and our
SSG. All evaluated systems were variants that achieved high performance in
automatic evaluations. As shown in Table VI, on both evaluations, participants
overwhelmingly prefer our model compared with baselines of similar scales. All
pairwise comparisons among systems are statistically significant using the
paired student t-test for significance at $\alpha$ = 0.01.

TABLE V: ROUGE score comparisons on text stream. ROUGE score comparisons between baselines. All scores have a 95% confidence interval of at most $\pm$0.28.  | RG-1 | RG-2 | RG-L | BS
---|---|---|---|---
_*-Together methods_ |
Transformer-Together | 36.17 | 8.76 | 33.45 | 82.29
PG-Together | 36.36 | 8.79 | 33.95 | 82.41
SAGCopy-Together | 37.89 | 9.50 | 35.54 | 82.74
PEGASUS-Together | 45.05 | 10.76 | 42.74 | 84.22
BART-Together | 45.36 | 11.15 | 43.14 | 85.34
_*-Split methods_ |
Transformer-Split | 36.30 | 8.93 | 33.74 | 82.31
PG-Split | 36.83 | 9.07 | 34.37 | 83.50
SAGCopy-Split | 38.44 | 9.24 | 34.99 | 83.81
PEGASUS-Split | 45.19 | 10.79 | 43.16 | 84.77
GPT-3.5 | 34.20 | 7.11 | 30.85 | 80.06
BART-Split | 45.94 | 11.28 | 43.96 | 84.69
SSG | 47.00 | 12.46 | 44.77 | 85.86

We give two examples of system outputs in Table VII. In the first case, we can
see that our proposed model SSG can generate a coherent, informative, and
accurate summary. Both baselines make some mistakes or miss important
information. In the second case, all baselines and our model make some
mistakes. BART-Split confuses the father and son, and our SSG introduces “the
son goes to the dad” while the fact is “the dad goes to the son”. It’s evident
that GPT-3.5 generally performs comparably to our model, with the exception
being its misinterpretation of “leave Nikolas a widower” as “causing Nikolas’s
death”.

TABLE VI: System scores based on questions answered by human annotators and summary quality rating. | QA(%) | Rating
---|---|---
SAGCopy-Split | 34.42 | 3.26
BART-Split | 40.98 | 3.56
SSG | 45.90 | 3.81
GPT-3.5 | 48.39 | 4.03
TABLE VII: Gold human authored summaries and automatic summaries produced by
several baselines and our SSG.

_Ground Truth Summary:_ Back at home, the not-so-happy newlyweds get into an
argument which prompts Lydia to pick up the phone and call a lawyer so she can
have the marriage annulled. However, Stefan catches her and hangs up the
phone, telling her that the only way she’ll get out of the marriage is by
leaving Nikolas a widower.
---
_QA:_ Question: Who stops Lydia from calling a lawyer? Answer: Stefan.
_SAGCopy-Split:_ Emily and Stefan get into an argument which prompts Lydia to
call a lawyer so she can have the marriage annulled. Stefan catches her and
hangs up the phone, telling her that the only way she’ll get out of the
marriage is by leaving Nikolas a widower.
_BART-Split:_ Lydia and Stefan get into an argument which prompts Lydia to
pick up the phone and call a lawyer so she can have the marriage annulled.
However, Stefan catches her and hangs up.
_GPT-3.5:_ Lydia and Nikolas have a heated argument, leading Lydia to seek an
annulment through a lawyer. Stefan intervenes, insisting that the only way she
can escape the marriage is by causing Nikolas’s death.
_SSG: _ Lydia and Stefan get into an argument which prompts Lydia to call a
lawyer so she can have the marriage annulled. However, Stefan catches her and
hangs up the phone, telling her that the only way she’ll get out of the
marriage is to leave Nikolas a widower.
_Ground Truth Summary:_ Sonny goes to intervene in what could have been an
escalated situation involving Morgan’s confrontation with a guy at the coffee
shop. When it appears his son handled the situation and nothing got out of
hand, Sonny commends and praises him, tells Morgan how proud he is of him and
assures his son all will be well as long as he takes the correct meds that
have proven successful.
_QA:_ Question: Who is the father? Answer: Sonny.
_SAGCopy-Split:_ Sonny talks to Morgan who encourages his son to know that he
did the right thing, reminding him he protected Kiki without losing control.
He tells Morgan he needs to keep doing what he is doing and continue taking
his meds and he will be all right.
_BART-Split:_ At the coffee shop, Sonny talks to his dad who encourages his
son to know that he did the right thing by protecting Kiki without losing
control. He assures his son that the behavior of the guy and the situation was
enough to reasonably provoke and piss anybody off. Sonny assures Morgan he
merely needs to keep doing what he is doing and will be all right.
_GPT-3.5:_ In the article, Sonny advises Morgan to believe he did the right
thing by protecting Kiki from a provoking individual. Sonny reassures Morgan
that as long as he continues taking his medication and stays on the right
path, he will be fine.
_SSG: _ Morgan goes to talk to his dad who encourages his son to know that he
did the right thing by protecting Kiki from the guy who provoked him. They
both affirm that Morgan is successfully fighting his illness and getting his
life back on track.

###  VII-E Influence of Previous Information

Since our stepwise summarization takes the previous information as input, we
conduct an experiment to see the influence of the relatedness between the
previous and current information. Concretely, we calculate the ROUGE score
between the document and generated summary (DS score), and the score between
the document with previous summary (DP score). The result is shown in Figure
4(a). It can be seen that the two scores have a positive correlation with each
other, which means that a closer relationship between the previous and current
information can help improve summarization performance. However, the DS scores
are substantially higher than DP scores, which means that the good performance
of our model does not solely rely on the previous information, but also on the
modeling of the two information sources.

###  VII-F Error Accumulation Analysis

As the text stream gets longer, the errors in the summarization process get
accumulated. Hence, we are interested to see whether the benefits of stepwise
summarization will be diminished as the stream grows. We conduct experiments
to investigate the ROUGE performance on text stream with different lengths,
i.e., document-summary pair number, as shown Figure 4(b). The result shows
that the ROUGE score of SSG increases with the number of input documents to
begin with, which demonstrates that our proposed model is more and more
effective when the text stream begins to grow larger. It can also be seen
that, as the stream gets longer, the improvement of our model compared with
BART-Split is generally consistent. Regardless of the different lengths of the
text stream, our SSG consistently outperforms BART-Split, which is a strong
baseline that achieves good performance in all metrics. The above result
demonstrates that the previous summary is always useful, and our model can
successfully utilize it.

Figure 4: (a) Influence of previous information (DP score) on summarization
performance (DS score). (b) Error accumulation analysis when the text stream
gets longer.

###  VII-G Efficiency and Scale Analysis

From parameter view, both PEGASUS (223M) and our model (149M) introduce more
parameters compared to the baseline BART, leading to increased computational
resources. Secondly, a larger model introduces more training time and
inference time. Hence, it takes a bit longer for our model to decode compared
with BART (5s). Finally, the integration of the GAN mechanism in SSG, despite
adding a modest increase in parameters (3.11M), significantly accelerates
network convergence, and does not introduce more inference time.

Based on the findings in Tables V and VI, it is evident that an increase in
the number of parameters leads to improved model performance. For instance,
GPT-3.5, with its larger parameter scale, achieves a human evaluation rating
of 4.03. At the same time, it is important to note that within the same
parameter range, the design of the model significantly affects its
performance. As an example, our model, which has only 6% more parameters
compared to BART-base, surpasses BART’s performance by 12%. Similarly, it
surpasses PEGASUS by 4% while having 40% fewer parameters.

##  VIII Conclusion

In this paper, we have proposed a model named _Stepwise Summary Generator_
(SSG) which aims to generate summaries for stream document data. Since
previous information is also important when summarizing a current document,
our model used a previous summary to selectively read the current document and
obtained its polished representation, both were combined to generate the
summary. In addition, a convolutional discriminator was employed to provide a
coherence signal to the generator, so as to enhance the coherence between the
previous summary and the newly generated one. SSG outperformed the state-of-
the-art summarization models on our large-scale stepwise summarization dataset
in terms of both human and automatic metrics. In the near future, we will
employ large language models to enhance the performance of the stepwise
summarization models.

## Acknowledgments

We would like to thank the anonymous reviewers for their constructive
comments. The work was supported by King Abdullah University of Science and
Technology (KAUST) through grant awards FCC/1/1976-44-01, FCC/1/1976-45-01,
REI/1/5234-01-01, RGC/3/4816-01-01, REI/1/5414-01-01, REI/1/5289-01-01, and
REI/1/5404-01-01.

## References

  * [1] Alexios Gidiotis and Grigorios Tsoumakas.  A divide-and-conquer approach to the summarization of long documents.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2020.
  * [2] Tao Ge, Lei Cui, Baobao Chang, Sujian Li, Ming Zhou, and Zhifang Sui.  News stream summarization using burst information networks.  In Proc. of EMNLP, 2016.
  * [3] Hoa Trang Dang and Karolina Owczarzak.  Overview of the tac 2008 update summarization task.  In TAC, 2008.
  * [4] Aishwarya Jadhav and Vaibhav Rajan.  Extractive summarization with swap-net: Sentences and words from alternating pointer networks.  In Proc. of ACL, 2018.
  * [5] Shashi Narayan, Shay B. Cohen, and Mirella Lapata.  Ranking sentences for extractive summarization with reinforcement learning.  In Proc. of AACL, 2018.
  * [6] Jiacheng Xu, Zhe Gan, Yu Cheng, and Jingjing Liu.  Discourse-aware neural extractive text summarization.  In Proc. of ACL, 2020.
  * [7] Yue Dong, Yikang Shen, Eric Crawford, Herke van Hoof, and Jackie Chi Kit Cheung.  Banditsum: Extractive summarization as a contextual bandit.  In Proc. of EMNLP, 2018.
  * [8] Ming Zhong, Pengfei Liu, Yiran Chen, Danqing Wang, Xipeng Qiu, and Xuanjing Huang.  Extractive summarization as text matching.  In Proc. of ACL, 2020.
  * [9] Qingyu Zhou, Nan Yang, Furu Wei, Shaohan Huang, Ming Zhou, and Tiejun Zhao.  A joint sentence scoring and selection framework for neural extractive document summarization.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2020.
  * [10] Jiajun Zhang, Yu Zhou, and Chengqing Zong.  Abstractive cross-language summarization via translation model enhanced predicate argument structure fusing.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2016.
  * [11] Jiajun Zhang, Yang Zhao, Haoran Li, and Chengqing Zong.  Attention with sparsity regularization for neural machine translation and summarization.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2018.
  * [12] Asli Celikyilmaz, Antoine Bosselut, Xiaodong He, and Yejin Choi.  Deep communicating agents for abstractive summarization.  In Proc. of AACL, 2018.
  * [13] Kai Wang, Xiaojun Quan, and Rui Wang.  Biset: Bi-directional selective encoding with template for abstractive summarization.  In Proc. of ACL, 2019.
  * [14] Ming-Hsiang Su, Chung-Hsien Wu, and Hao-Tse Cheng.  A two-stage transformer-based approach for variable-length abstractive summarization.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 2020.
  * [15] Wan Ting Hsu, Chieh-Kai Lin, Ming-Ying Lee, Kerui Min, Jing Tang, and Min Sun.  A unified model for extractive and abstractive summarization using inconsistency loss.  In Proc. of ACL, 2018.
  * [16] Sebastian Gehrmann, Yuntian Deng, and Alexander M. Rush.  Bottom-up abstractive summarization.  Empirical Methods in Natural Language Processing, 2018.
  * [17] Jiatao Gu, Zhengdong Lu, Hang Li, and Victor O. K. Li.  Incorporating copying mechanism in sequence-to-sequence learning.  Proceedings of Annual Meeting of the Association for Computational Linguistics, 2016.
  * [18] Abigail See, Peter J. Liu, and Christopher D. Manning.  Get to the point: Summarization with pointer-generator networks.  In Proc. of ACL, 2017.
  * [19] Karl Moritz Hermann, Tomás Kociský, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom.  Teaching machines to read and comprehend.  In Proc. of NeurIPS, 2015.
  * [20] Max Grusky, Mor Naaman, and Yoav Artzi.  Newsroom: A dataset of 1.3 million summaries with diverse extractive strategies.  In Proc. of AACL, 2018.
  * [21] Shashi Narayan, Shay B. Cohen, and Mirella Lapata.  Don’t give me the details, just the summary! topic-aware convolutional neural networks for extreme summarization.  In Proc. of EMNLP, 2018.
  * [22] Byeongchang Kim, Haengkang Kim, and Gunhee Kim.  Abstractive summarization of reddit posts with multi-level memory networks.  In Proc. of AACL, 2018.
  * [23] James Allan, Rahul Gupta, and Vikas Khandelwal.  Temporal summaries of news topics.  In Proc. of SIGIR, 2001.
  * [24] Rui Yan, Xiaojun Wan, Jahna Otterbacher, Liang Kong, Xiaoming Li, and Yan Zhang.  Evolutionary timeline summarization: a balanced optimization framework via iterative substitution.  In Proc. of SIGIR, 2011.
  * [25] Rui Yan, Liang Kong, Congrui Huang, Xiaojun Wan, Xiaoming Li, and Yan Zhang.  Timeline generation through evolutionary trans-temporal summarization.  In Proc. of EMNLP, 2011.
  * [26] Wayne Xin Zhao, Yanwei Guo, Rui Yan, Yulan He, and Xiaoming Li.  Timeline generation with social attention.  In Proc. of SIGIR, 2013.
  * [27] Xiuying Chen, Zhangming Chan, Shen Gao, Meng-Hsuan Yu, Dongyan Zhao, and Rui Yan.  Learning towards abstractive timeline summarization.  In Proc. of IJCAI, 2019.
  * [28] Xiuying Chen, Mingzhe Li, Shen Gao, Zhangming Chan, Dongyan Zhao, Xin Gao, Xiangliang Zhang, and Rui Yan.  Follow the timeline! generating an abstractive and extractive timeline summary in chronological order.  ACM Transactions on Information Systems, 41(1):1–30, 2023.
  * [29] Demian Gholipour Ghalandari and Georgiana Ifrim.  Examining the state-of-the-art in news timeline summarization.  arXiv preprint arXiv:2005.10107, 2020.
  * [30] Yi Yu, Adam Jatowt, Antoine Doucet, Kazunari Sugiyama, and Masatoshi Yoshikawa.  Multi-timeline summarization (mtls): Improving timeline summarization by generating multiple summaries.  In Proc. of ACL, 2021.
  * [31] Lidan Shou, Zhenhua Wang, Ke Chen, and Gang Chen.  Sumblr: continuous summarization of evolving tweet streams.  In Proc. of SIGIR, 2013.
  * [32] Andrei Olariu.  Efficient online summarization of microblogging streams.  In Proc. of ACL, 2014.
  * [33] Zhaochun Ren, Oana Inel, Lora Aroyo, and Maarten De Rijke.  Time-aware multi-viewpoint summarization of multilingual social text streams.  In Conference on Information and Knowledge Management, 2016.
  * [34] Florian Boudin, Marc El-Bèze, and Juan-Manuel Torres-Moreno.  A scalable mmr approach to sentence scoring for multi-document update summarization.  In Proc. of COLING, 2008.
  * [35] Jean-Yves Delort and Enrique Alfonseca.  Dualsum: a topic-model based approach for update summarization.  In Proc. of ACL, 2012.
  * [36] Maali Mnasri, Gaël de Chalendar, and Olivier Ferret.  Taking into account inter-sentence similarity for update summarization.  In IJCNLP, 2017.
  * [37] Mingda Chen and Kevin Gimpel.  Tvrecap: A dataset for generating stories with character descriptions.  arXiv preprint arXiv:2109.08833, 2021.
  * [38] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Proc. of NeurIPS, 2017.
  * [39] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In Proc. of ACL, 2020.
  * [40] Xiuying Chen, Shen Gao, Chongyang Tao, Yan Song, Dongyan Zhao, and Rui Yan.  Iterative document representation learning towards summarization with polishing.  Empirical Methods in Natural Language Processing, 2018.
  * [41] Ari Holtzman, Jan Buys, Maxwell Forbes, Antoine Bosselut, David Golub, and Yejin Choi.  Learning to write with cooperative discriminators.  In Proc. of ACL, 2018.
  * [42] Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q Weinberger, and Yoav Artzi.  Bertscore: Evaluating text generation with bert.  In Proc. of ICLR, 2020.
  * [43] Amanda Stent, Matthew Marge, and Mohit Singhai.  Evaluating evaluation methods for generation in the presence of variation.  In CICLing, 2005.
  * [44] Rada Mihalcea and Paul Tarau.  Textrank: Bringing order into text.  In Proc. of EMNLP, 2004.
  * [45] Dan Gillick and Benoît Favre.  A scalable global model for summarization.  In ILP 2009, 2009.
  * [46] Song Xu, Haoran Li, P. Yuan, Youzheng Wu, Xiaodong He, and Bowen Zhou.  Self-attention guided copy mechanism for abstractive summarization.  In Proc. of ACL, 2020.
  * [47] Jingqing Zhang, Yao Zhao, Mohammad Saleh, and Peter Liu.  Pegasus: Pre-training with extracted gap-sentences for abstractive summarization.  In Proc. of ICML, 2020.
  * [48] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [49] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio.  On the difficulty of training recurrent neural networks.  In ICML, 2013.
  * [50] Yang Liu and Mirella Lapata.  Hierarchical transformers for multi-document summarization.  In Proc. of ACL, 2019.
  * [51] James Clarke and Mirella Lapata.  Discourse constraints for document compression.  Computational Linguistics, 2010.


of views to also incorporate mappings of PDBs that are not defined on a “per
possible world” basis. Before, we have introduced views as functions mapping
database instances to database instances and adopted a semantics based on
possible worlds. Now, we want to discuss _PDB views_ as functions that map
probabilistic databases to probabilistic databases, for which no such
semantics (to be precise, a definition as in in the shape of Section 3.2)
exists. Such “views” naturally arise in a variety of computational problems in
probabilistic databases. For example, consider the following problems or
“queries”:

  * •

_probabilistic threshold queries_ that intuitively return a deterministic
table containing only those facts which have a marginal probability over some
specified threshold [QJSP10];

  * •

_probabilistic top- $k$ queries_ that intuitively return a deterministic table
containing the $k$ most probable facts [RDS07];

  * •

_probabilistic skyline queries_ [PJLY07] that consider how different instances
compare to each other with respect to some notion of _dominance_ ; and

  * •

_conditioning_ [KO08] the probabilistic database to some event.

Note that the way we informally explained the first two queries above is only
sensible if the space of facts is discrete. In a continuous setting, we
interpret these queries with respect to a suitable countable partition of the
fact space into measurable sets.

More such “queries” as the above can be found in [Agg09, WLLW13]. These
queries (or views) still take as input a PDB and produce some output, but
differ from the ones we have seen so far in that they have no reasonable
semantics on _single_ instances (i. e. per possible world). This can be, for
example, because they explicitly take probabilities into account. The goal of
this section is to interpret other kinds of problems on PDBs abstractly as
functions on probability spaces in order fit them into a unified framework.
Developing such an understanding has already been motivated in [WvK15] as
yielding potential insight into common properties of the corresponding
problems.

We now present our formal classification of views that are directly defined on
the probability space level of a PDB (as opposed to the instance level as in
Section 3.2). Let $\bm{\mathsf{PDB}}_{\tau}$ denote the class of probabilistic
databases of schema $\tau$. Note that all PDBs in $\bm{\mathsf{PDB}}_{\tau}$
have the same instance measurable space
$(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}})$.
Queries and, more generally, views of input schema $\tau$ and output schema
$\tau^{\prime}$ are now mappings
$V\colon\bm{\mathsf{PDB}}_{\tau}\to\bm{\mathsf{PDB}}_{\tau^{\prime}}$.

[View Types]

  1. (1)

Every view is _type 1_.

  2. (2)

A view $V$ is _type 2_ , or _pointwise local_ , if (and only if) for every
fixed input PDB
$\mathcal{D}=(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$
there exists a measurable function
$q_{\mathcal{D}}\colon\mathord{\mathbb{D}\mathbb{B}}\to\mathord{\mathbb{D}\mathbb{B}}_{V}$
such that $P_{V}=P\circ q_{\mathcal{D}}^{-1}$.

  3. (3)

A view $V$ is _type 3_ , or _uniformly local_ , if there exists a measurable
function
$q\colon\mathord{\mathbb{D}\mathbb{B}}\to\mathord{\mathbb{D}\mathbb{B}}_{V}$
such that for every input PDB
$\mathcal{D}=(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$,
it holds that $P_{V}=P\circ q^{-1}$.

  4. (4)

A view $V$ is _type 4_ , or _pointwise_ , if (and only if) there exists
measurable function $q\colon\bm{F}_{q}\to\mathbb{F}_{Q}$ such that $V$ is
composed of functions of the shape of $Q$ as in Theorem 14 (where $Q$ depends
on $q$).

We let $\bm{\mathsf{V}}_{\text{I}}$, $\bm{\mathsf{V}}_{\text{II}}$,
$\bm{\mathsf{V}}_{\text{III}}$ and $\bm{\mathsf{V}}_{\text{IV}}$ denote the
classes of views of type 1 throughout 4.

######  Remark 45.

Let us shed some more light on these classes and their names:

  1. (1)

Class $\bm{\mathsf{V}}_{\text{I}}$ does not require further explanation, as it
contains _every_ view.

  2. (2)

The class $\bm{\mathsf{V}}_{\text{II}}$ is described via functions that may
depend on the measurable structure of the input PDB. Specifically, these views
are functions that directly transform input to output PDBs. We dub this
“pointwise local”, because this function is applied per instance (hence,
local) but the function itself depends on the concrete PDB (hence, is only
pointwise local with respect to probability spaces). In general, type 2 views
may take the probability space level into account. For example, probabilistic
threshold or probabilistic top-$k$ queries can be viewed as views of this
class: they transform any input PDB to a single database instance (that is, a
PDB with only one possible world of probability $1$) containing the respective
output tuples along with their probability in a separate attribute. Another
example is conditioning a PDB, as the probability measure of a conditioned PDB
involves a normalization term that depends on the probability mass of an
event.

  3. (3)

The class $\bm{\mathsf{V}}_{\text{III}}$ captures the lifting of typical
database queries to PDBs under the possible worlds semantics. Hence, there is
a _single_ (measurable) function that is applied “locally” on every database
instance. The term “uniformly” expresses that it does not depend on the
concrete PDB. In general, type 3 views only take the instance level into
account. All the views that we investigated in Sections 5, 6 and 7 fall into
this category.

  4. (4)

The class $\bm{\mathsf{V}}_{\text{IV}}$ is the class of views corresponding to
the measurability criterion of the Mapping Theorem. That is, there is a
(measurable) function that is applied “pointwise”777Note that the “pointwise”
in the term “pointwise local” from $\bm{\mathsf{V}}_{\text{II}}$ refers to
probability spaces as “points”, whereas the term “pointwise” alone, as here in
the definition of $\bm{\mathsf{V}}_{\text{IV}}$ refers to facts as “points” on
every fact. This transformation naturally lifts to instances and, thus, to
PDBs. In general, type 4 views only take the fact level into account. We have
seen an example of such a view in Section 4.2.

Recall our running example of temperature measurements. We use this to
introduce an example of a view that performs “out-of-world aggregation”
[WvK15] (and that, in particular, is of type $2$, but not of type $3$). The
relation TempRec stores triples of room numbers (RoomNo), recording dates
(Date) and recorded temperatures (Temp). Assume that the pair
$(\text{RoomNo},\text{Date})$ acts as a key, so that with probability $1$
there is at most one temperature recording per pair. Moreover, assume that the
PDB is modelled with independent tuples $(r,d,\theta)$ where $\theta$ is
Normally distributed per pair $(r,d)$, but such that the existence of an
record belonging to $(r,d)$ is subject to uncertainty. That is, we have a mix
of attribute- and tuple-level uncertainty. A possible representation of such a
PDB is shown in Figure 4. Therein, we have two possible tuples (one recording
for room 4108 and one recording for room 4108a), but the value of the
temperature recording is specified as a Normally distributed random variable,
parameterized with its mean and variance. We assume the existence of tuples
with room 4108 or 4108a to be independent from one another, and that these
events carry probability $0.4$ and $0.8$, respectively.

TempRec RoomNo | Date | Temp [°C] | Prob
---|---|---|---
4108 | 2021-07-12 | $\mathcal{N}(20.5,0.1)$ | $0.4$
4108a | 2021-07-12 | $\mathcal{N}(21.0,0.1)$ | $0.8$

View RoomNo | Date | Temp [°C] | Prob
---|---|---|---
4108 | 2021-07-12 | 20.5 | $0.4$
4108a | 2021-07-12 | 21.0 | $0.8$

Figure 4. Representation of a PDB along with the representation of a view that
goes beyond the instance level.

A possible view could ask to return, per room and date, the _expected_
temperature, under preserving the tuple-level uncertainty. The output of this
view is shown on the right-hand side of Figure 1. (It is here trivially to
obtain, because the expected value was already part of the parametrization.
The idea however also applies to more complicated setups.) The possible worlds
of the input PDB
$\mathcal{D}=(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$
are partitioned into four cases, depending on the presence of a tuple with
room 4108 and 4108a, respectively. Our function $q_{\mathcal{D}}$ (which
depends on $\mathcal{D}$) maps instances $D\in\mathord{\mathbb{D}\mathbb{B}}$
as follows: the tuple $(\text{\small 4108},\text{\small
2021-07-12},\text{\small 20.5})$ is present in the view result if and only if
$D$ contains a tuple with room 4108, and the tuple $(\text{\small
4108},\text{\small 2021-07-12},\text{\small 21.0})$ is present in the view
result if and only if $D$ contains a tuple with room 4108a. Then the output
PDB has probability measure $P\circ q_{\mathcal{D}}^{-1}$ and, in particular,
four possible worlds. This is a so-called _tuple-independent_ PDB with given
marginal probabilities ($0.4$ and $0.8$), hence it can be represented as shown
on the right-hand side of Figure 1.888The input PDB in this case is not tuple-
independent, as any two facts with the same room number are mutually
exclusive. Instead, this is a so-called (uncountable) _block-independent
disjoint_ PDB with two independent blocks, both representing a single random
tuple, such that each block specifies the (probability distribution over)
possible manifestations for this tuple.

Let us come back to the relationships between the classes of views we defined
in Section 8. Clearly,
$\bm{\mathsf{V}}_{\text{I}}\supseteq\bm{\mathsf{V}}_{\text{II}}\supseteq\bm{\mathsf{V}}_{\text{III}}\supseteq\bm{\mathsf{V}}_{\text{IV}}$.
We already informally argued in Section 4.2 that queries that depend on
multiple tuples per instance are not captured by
$\bm{\mathsf{V}}_{\text{III}}$, i. e.
$\bm{\mathsf{V}}_{\text{III}}\not\subseteq\bm{\mathsf{V}}_{\text{IV}}$. We
provide two examples to expose that also the remaining inclusions are strict.

######  Proposition 46.

There exists a view that is not type 2, i. e.
$\bm{\mathsf{V}}_{\text{II}}\subsetneq\bm{\mathsf{V}}_{\text{I}}$.

We demonstrate this using a view that _conditions_ its input PDB on an event.

######  Proof 8.1.

Let $\mathcal{D}$ be a PDB with three possible worlds $D_{1}$, $D_{2}$, and
$D_{3}$, such that

$P(\\{D_{1}\\})=\tfrac{1}{6}\text{,}\quad P(\\{D_{2}\\})=\tfrac{1}{2}\text{,
and}\quad P(\\{D_{3}\\})=\tfrac{1}{3}\text{.}$

Consider the view $V$ that conditions a PDB on the event $\\{D_{1},D_{2}\\}$.
Note that

$P_{V(\mathcal{D})}(\\{D_{1}\\})=\tfrac{1}{6}/\big{(}\tfrac{1}{6}+\tfrac{1}{2}\big{)}=\tfrac{1}{4}\qquad\text{and}\qquad
P_{V(\mathcal{D})}(\\{D_{2}\\})=\tfrac{1}{2}/\big{(}\tfrac{1}{6}+\tfrac{1}{2}\big{)}=\tfrac{3}{4}\text{.}$

Yet, there is no event $\bm{D}$ in $\mathcal{D}$ with the property that
$P(\bm{D})=\tfrac{1}{4}$. Thus, a function $q_{\mathcal{D}}$ as required in
Section 82 does not exist and, hence, $V$ is not type 2.

######  Proposition 47.

There exists a type 2 view that is not type 3, so
$\bm{\mathsf{V}}_{\text{III}}\subsetneq\bm{\mathsf{V}}_{\text{II}}$.

We have already discussed such a view in Section 8, but have not actually
shown that it is not of type $3$. We demonstrate the propoosition in
considering another example, namely that of a probabilistic threshold query.

######  Proof 8.2.

Let $\alpha\in(0,1]$. We consider a function $V_{\alpha}$ that maps an input
PDB
$\mathcal{D}=(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$
to an output PDB $V_{\alpha}(\mathcal{D})$ such that

$D_{\mathcal{D},\alpha}\coloneqq\Big{\\{}f\in\mathbb{F}\colon
P\big{(}\\{D\in\mathord{\mathbb{D}\mathbb{B}}\colon\lvert
D\rvert_{f}>0\\}\big{)}\geq\alpha\Big{\\}}$

has probability $1$ in $V_{\alpha}(\mathcal{D})$. Note that
$D_{\mathcal{D},\alpha}$ is finite for all $\alpha\in(0,1]$, so $V_{\alpha}$
is well-defined. The view $V_{\alpha}$ is a probabilistic threshold query with
threshold $\alpha$. Consider the function $q_{\mathcal{D}}$ with $D\mapsto
D_{\mathcal{D},\alpha}$ for all $D\in\mathord{\mathbb{D}\mathbb{B}}$. Then
$q_{\mathcal{D}}$ is measurable and witnesses that $V_{\alpha}$ is type 2 for
all $\alpha\in(0,1]$.

Now let $\alpha>\frac{1}{2}$ and consider the following two PDBs
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$, with probability measures $P_{1}$ and
$P_{2}$, respectively, over distinct facts $f$ and $g$:

$D$ | $\\{f\\}$ | $\\{g\\}$
---|---|---
$P_{1}(D)$ | $\alpha$ | $1-\alpha$

$D$ | $\\{f\\}$ | $\\{g\\}$
---|---|---
$P_{2}(D)$ | $1-\alpha$ | $\alpha$

Figure 5. Definition of $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$ (given as an
explicit list of the instances together with their probabilities).

Then $D_{\mathcal{D}_{1},\alpha}=\\{f\\}$ and
$D_{\mathcal{D}_{2},\alpha}=\\{g\\}$. Suppose $q$ exists such that
$P_{V}=P\circ q$ for every input PDB
$\mathcal{D}=(\mathord{\mathbb{D}\mathbb{B}},\mathord{\mathfrak{D}\mkern-2.5mu\mathfrak{B}},P)$.
Let $\bm{D}_{f}\coloneqq\\{D\in\mathord{\mathbb{D}\mathbb{B}}_{V}\colon f\in
D\\}$. Then $P_{\mathcal{D}_{1}}\big{(}q^{-1}(\bm{D}_{f})\big{)}=1$ implies
$\\{f\\}\in q^{-1}(\bm{D}_{f})$. On the contrary,
$P_{\mathcal{D}_{2}}\big{(}q^{-1}(\bm{D}_{f})\big{)}=0$, implies
$\\{f\\}\notin q^{-1}(\bm{D}_{f})$, a contradiction. Thus, $V_{\alpha}$ is not
of type 3.

Together, we have that
$\bm{\mathsf{V}}_{\text{I}}\supsetneq\bm{\mathsf{V}}_{\text{II}}\supsetneq\bm{\mathsf{V}}_{\text{III}}\supsetneq\bm{\mathsf{V}}_{\text{IV}}$.
Before closing this section, let us highlight two key insights of the
arguments used in the examples for Propositions 46 and 47. In essence, we
separated type $2$ from type $3$ by arguing about the structure of possible
worlds without really taking probabilities into account. For the separation of
type $1$ from type $2$, we argued about the structure of the probability
measure instead. This highlights again the different levels within the
hierarchical structure of a PDB (fact level—instance level—probability space
level) that the views of the different classes operate on.

##  9\. Conclusions

We introduce the notion of standard PDBs, for which we rigorously describe how
to construct suitable measurable spaces for infinite probabilistic databases,
completing the picture of [GL19]. The viability of this model as a general and
unifying framework for finite _and infinite_ databases is supported by the
well-definedness and compositionality of (typical) query semantics. Other
kinds of PDB queries embed into the framework as well.

It is currently open, whether, and if so, how more in-depth results on point
processes can be used for probabilistic databases, for example, to perform
open-world query answering. Also, while we focused on relational algebra and
aggregation, the queries of Section 8 deserve a systematic treatment in their
own right in infinite PDBs.

## Acknowledgments

We thank Sam Staton, who initially brought the correspondence of probabilistic
databases and finite point processes to our attention in personal
correspondence.

This work is funded by _Deutsche Forschungsgemeinschaft_ (DFG, German Research
Foundation) under grants GR 1492/16-1 and GRK 2236 (UnRAVeL).

## References

  * [ACK+11] Serge Abiteboul, T.-H. Hubert Chan, Evgeny Kharlamov, Werner Nutt, and Pierre Senellart.  Capturing Continuous Data and Answering Aggregate Queries in Probabilistic XML.  ACM Transactions on Database Systems (TODS), 36(4):25:1–25:45, 2011\.  doi:10.1145/1804669.1804679.
  * [Agg09] Charu C. Aggarwal, editor.  Managing and Mining Uncertain Data, volume 35 of Advances in Database Systems.  Springer, Boston, MA, USA, 2009.  doi:10.1007/978-0-387-09690-2.
  * [AHV95] Serge Abiteboul, Richard Hull, and Victor Vianu.  Foundations of Databases.  Addison-Wesley, Boston, MA, USA, 1st edition, 1995.
  * [Alb91] Joseph Albert.  Algebraic Properties of Bag Data Types.  In Proceedings of the 17th International Conference on Very Large Databases (VLDB 1991), pages 211–219, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc.
  * [Ash72] Robert B. Ash.  Real Analysis and Probability.  Probability and Mathematical Statistics: A Series of Monographs and Textbooks. Academic Press, Inc., New York, NY, USA, 1972.  doi:10.1016/C2013-0-06164-6.
  * [AW09] Parag Agrawal and Jennifer Widom.  Continuous Uncertainty in Trio.  In Proceedings of the 3rd VLDB Workshop on Management of Uncertain Data (MUD ’09), pages 17–32, Enschede, The Netherlands, 2009. Centre for Telematics and Information Technology (CTIT).
  * [Bad07] Adrian Baddeley.  Spatial Point Processes and Their Applications.  In Wolfgang Weil, editor, Stochastic Geometry, Lecture Notes in Mathematics, chapter 1, pages 1–75. Springer, Berlin, Heidelberg, Germany, 1st edition, 2007.
  * [BCL17] Stefan Borgwardt, İsmail İlkan Ceylan, and Thomas Lukasiewicz.  Ontology-Mediated Queries for Probabilistic Databases.  In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI ’17), pages 1063–1069, Palo Alto, CA, USA, 2017. AAAI Press.
  * [BCL18] Stefan Borgwardt, İsmail İlkan Ceylan, and Thomas Lukasiewicz.  Recent Advances in Querying Probabilistic Knowledge Bases.  In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI ’18), pages 5420–5426. International Joint Conferences on Artificial Intelligence, 2018.  doi:10.24963/ijcai.2018/765.
  * [BCL19] Stefan Borgwardt, İsmail İlkan Ceylan, and Thomas Lukasiewicz.  Ontology-Mediated Query Answering over Log-Linear Probabilistic Data.  In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, volume 33, Palo Alto, CA, USA, 2019. AAAI Press.  doi:10.1609/aaai.v33i01.33012711.
  * [BDM+05] Jihad Boulos, Nilesh Dalvi, Bhushan Mandhani, Shobhit Mathur, Chris Ré, and Dan Suciu.  MYSTIQ: A System for Finding more Answers by Using Probabilities.  In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data (SIGMOD ’05), pages 891–893, New York, NY, USA, 2005. ACM.  doi:10.1145/1066157.1066277.
  * [Bel20] Vaishak Belle.  Symbolic Logic Meets Machine Learning: A Brief Survey in Infinite Domains.  In Jesse Davis and Karim Tabia, editors, Scalable Uncertainty Management, Lecture Notes in Computer Science, page 3–16. Springer International Publishing, 2020.  doi:10.1007/978-3-030-58449-8\\_1.
  * [BGMP92] Daniel Barbará, Héctor García-Molina, and Daryl Porter.  The Management of Probabilistic Data.  IEEE Transactions on Knowledge and Data Engineering, 4(5):487–502, 1992.  doi:10.1109/69.166990.
  * [BPVDB15] Vaishak Belle, Andrea Passerini, and Guy Van Den Broeck.  Probabilistic Inference in Hybrid Domains by Weighted Model Integration.  In Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI 2015), IJCAI’15, pages 2770–2776. AAAI Press, Jul 2015.
  * [CDVdB16] İsmail İlkan Ceylan, Adnan Darwiche, and Guy Van den Broeck.  Open-World Probabilistic Databases.  In Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning (KR ’16), pages 339–348, Palo Alto, CA, USA, 2016. AAAI Press.
  * [CDVdB21] İsmail İlkan Ceylan, Adnan Darwiche, and Guy Van den Broeck.  Open-World Probabilistic Databases: Semantics, Algorithms, Complexity.  Artificial Intelligence, 295, 2021.  doi:10.1016/j.artint.2021.103474.
  * [CKP03] Reynold Cheng, Dmitri V. Kalashnikov, and Sunil Prabhakar.  Evaluating Probabilistic Queries over Imprecise Data.  In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data (SIGMOD ’03), pages 551–562, New York, NY, USA, 2003. ACM.  doi:10.1145/872757.872823.
  * [CL97] Latha S. Colby and Leonid Libkin.  Tractable Iteration Mechanisms for Bag Languages.  In Proceedings of the 6th International Conference on Database Theory (ICDT 1997), volume 1186 of Lecture Notes in Computer Science, pages 461–475, Berlin, Germany, 1997. Springer-Verlag.  doi:10.1007/3-540-62222-5\\_64.
  * [CP87] Roger Cavallo and Michael Pittarelli.  The Theory of Probabilistic Databases.  In Proceedings of the 13th International Conference on Very Large Data Bases (VLDB ’87), pages 71–81, San Francisco, CA, USA, 1987. Morgan Kaufmann.
  * [CVP+13] Zhuhua Cai, Zografoula Vagena, Luis Perez, Subramanian Arumugam, Peter J. Haas, and Christopher Jermaine.  Simulation of database-valued markov chains using simsql.  In Proceedings of the 2013 international conference on Management of data - SIGMOD ’13, page 637, New York, New York, USA, 2013. ACM Press.  doi:10.1145/2463676.2465283.
  * [Deg17] Christoph Degen.  Finite Point Processes and Their Application to Target Tracking.  PhD thesis, Rheinische Friedrich-Wilhelms-Universität Bonn, 2017.
  * [DGK82] Umeshwar Dayal, Nathan Goodman, and Randy Howard Katz.  An Extended Relational Algebra with Control over Duplicate Elimination.  In Proceedings of the 1st ACM SIGACT-SIGMOD Composium on Principles of Database Systems (PODS ’82), pages 117–123, New York, NY, USA, 1982. ACM.
  * [DGM+04] Amol Deshpande, Carlos Guestrin, Samuel R. Madden, Joseph M. Hellerstein, and Wei Hong.  Model-Driven Data Acquisition in Sensor Networks.  In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB ’04), pages 588–599, St. Louis, 2004. Morgan Kaufmann.  doi:10.1016/B978-012088469-8.50053-X.
  * [DKM10] Daniel Deutch, Christoph Koch, and Tova Milo.  On Probabilistic Fixpoint and Markov Chain Query Languages.  In Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS ’10), pages 215–226, New York, NY, USA, 2010. ACM.
  * [DRKNP16] Luc De Raedt, Kristian Kersting, Sriraam Natarajan, and David Poole.  Statistical Relational Artificial Intelligence: Logic, Probability, and Computation.  Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool, San Rafael, CA, USA, 2016.
  * [DRS09] Nilesh Dalvi, Christopher Ré, and Dan Suciu.  Probabilistic Databases: Diamonds in the Dirt.  Communications of the ACM, 52(7):86–94, 2009.  doi:10.1145/1538788.1538810.
  * [DS96] Debabrata Dey and Sumit Sarkar.  A Probabilisitic Relational Model and Algebra.  ACM Transactions on Database Systems (TODS), 21(3), 1996.  doi:10.1145/232753.232796.
  * [DS07] Nilesh Dalvi and Dan Suciu.  Efficient Query Evaluation on Probabilistic Databases.  The VLDB Journal, 16(4):523–544, 2007.  doi:10.1007/s00778-006-0004-3.
  * [DS20] Swaraj Dash and Sam Staton.  A Monad for Probabilistic Point Processes.  Proceedings 3rd Annual International Applied Category Theory Conference 2020 (ACT 2020), 2020.  To appear.
  * [DVJ03] D. J. Daley and D. Vere-Jones.  An Introduction to the Theory of Point Processes, Volume I: Elementary Theory and Models.  Probability and Its Applications. Springer-Verlag New York, New York, NY, USA, 2nd edition, 2003.  doi:10.1007/b97277.
  * [DVJ08] D. J. Daley and D. Vere-Jones.  An Introduction to the Theory of Point Processes. Volume II: General Theory and Structure.  Probability and Its Applications. Springer Science+Business Media, LLC, New York, NY, USA, 2nd edition, 2008.
  * [FGB02] Anton Faradjian, Johannes Gehrke, and Philippe Bonnett.  GADT: A Probability Space ADT for Representing and Querying the Physical World.  In Proceedings of the 18th International Conference on Data Engineering (ICDE ’02), pages 201––211. IEEE Computing Society, 2002.  doi:10.1109/ICDE.2002.994710.
  * [FHO12] Robert Fink, Larisa Han, and Dan Olteanu.  Aggregation in Probabilistic Databases via Knowledge Compilation.  In Proceedings of the 38th International Conference on Very Large Data Bases (VLDB ’12), volume 5, pages 490–501. VLDB Endowment, 2012.  doi:10.14778/2140436.2140445.
  * [FR97] Norbert Fuhr and Thomas Rölleke.  A Probabilistic Relational Algebra for the Integration of Information Retrieval and Database Systems.  ACM Transactions on Information Systems (TOIS), 15(1):32–66, 1997\.  doi:10.1145/239041.239045.
  * [Fra82] Peter Franken.  Point Process Method in Queueing Theory, page 163–188.  Birkhäuser Boston, Boston, MA, USA, 1982.  doi:10.1007/978-1-4612-5791-2\\_6.
  * [Fuh95] Norbert Fuhr.  Probabilistic Datalog—A Logic for Powerful Retrieval Methods.  In Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’95), pages 282–290, New York, NY, USA, 1995. ACM.
  * [GH86] Erol Gelenbe and George Hebrail.  A Probability Model of Uncertainty in Data Bases.  In 1986 IEEE Second International Conference on Data Engineering, pages 328–333. IEEE, 1986.  doi:10.1109/ICDE.1986.7266237.
  * [GHNR14] Andrew D. Gordon, Thomas A. Henzinger, Aditya V. Nori, and Sriram K. Rajamani.  Probabilistic Programming.  In Future of Software Engineering Proceedings (FOSE 2014), pages 167–181, New York, NY, USA, 2014. Association for Computing Machinery.  doi:10.1145/2593882.2593900.
  * [GKT07] Todd J. Green, Grigoris Karvounarakis, and Val Tannen.  Provenance Semirings.  In Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2007), pages 31–40. Association for Computing Machinery, 2007.  doi:10.1145/1265530.1265535.
  * [GL19] Martin Grohe and Peter Lindner.  Probabilistic Databases with an Infinite Open-World Assumption.  In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’19), pages 17–31, New York, NY, USA, 2019\. ACM.  doi:10.1145/3294052.3319681.
  * [GL20] Martin Grohe and Peter Lindner.  Infinite Probabilistic Databases.  In 23rd International Conference on Database Theory (ICDT 2020), pages 16:1–16:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  doi:10.4230/LIPIcs.ICDT.2020.16.
  * [GLMW96] Stéphane Grumbach, Leonid Libkin, Tova Milo, and Limsoon Wong.  Query Languages for Bags: Expressive Power and Complexity.  ACM SIGACT News, 1996(2):30–44, 1996.  doi:10.1145/235767.235770.
  * [GM96] Stéphane Grumbach and Tova Milo.  Towards Tractable Algebras for Bags.  Journal of Computer and System Sciences, 52(3):570–588, 1996.  doi:10.1006/jcss.1996.0042.
  * [Gre09] Todd J. Green.  Models for Incomplete and Probabilistic Information.  In Charu C. Aggarwal, editor, Managing and Mining Uncertain Data, volume 35 of Advances in Database Systems, chapter 2, pages 9–43. Springer, Boston, MA, USA, 2009.  doi:10.1007/978-0-387-09690-2\\_2.
  * [JXW+11] Ravi Jampani, Fei Xu, Mingxi Wu, Luis Perez, Chris Jermaine, and Peter J. Haas.  The Monte Carlo Database System: Stochastic Analysis Close to the Data.  ACM Transactions on Database Systems (TODS), 36(3):18:1–18:41, 2011\.  doi:10.1145/2000824.2000828.
  * [Kal02] Olav Kallenberg.  Foundations of Modern Probability.  Probability and its Applications. Springer Science+Business Media New York, New York, NY, USA, 2nd edition, 2002.  doi:10.1007/978-1-4757-4015-8.
  * [Kec95] Alexander S. Kechris.  Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics.  Springer-Verlag New York, Inc., softcover reprint of the hardcover 1st edition, 1995.  URL: http://link.springer.com/10.1007/978-1-4612-4190-4, doi:10.1007/978-1-4612-4190-4.
  * [KK10] Oliver Kennedy and Christoph Koch.  PIP: A Database System for Great and Small Expectations.  In Proceedings of the 26th International Conference on Data Engineering (ICDE ’10), pages 157–168, Washington, DC, USA, 2010. IEEE.
  * [Kle14] Achim Klenke.  Probability Theory: A Comprehensive Course.  Universitext. Springer-Verlag London, London, UK, Translation from the German language edition; 2nd edition, 2014.  doi:10.1007/978-1-4471-5361-0.
  * [KLP00] Gabriel Kuper, Leonid Libkin, and Jan Paradaens, editors.  Constraint Databases.  Springer-Verlag, 2000.  doi:10.1007/978-3-662-04031-7.
  * [KO08] Christoph Koch and Dan Olteanu.  Conditioning Probabilistic Databases.  In Proceedings of the 34th International Conference on Very Large Data Bases (VLDB ’08), volume 1, pages 313–325. VLDB Endowment, 2008.  doi:10.14778/1453856.1453894.
  * [Koc08] Christoph Koch.  On Query Algebras for Probabilistic Databases.  ACM SIGMOD Record, 37(4):78–85, 2008.
  * [Koc09] Christoph Koch.  MayBMS: A System for Managing Large Probabilistic Databases.  In Charu C. Aggarwal, editor, Managing and Mining Uncertain Data, volume 35 of Advances in Database Systems, chapter 6, pages 149–184. Springer, Boston, MA, USA, 2009.  doi:10.1007/978-0-387-09690-2\\_6.
  * [KT12] Alex Kulesza and Ben Taskar.  Determinantal Point Processes for Machine Learning.  Foundations and Trends® in Machine Learning, 5(2–3):123–286, 2012.  doi:10.1561/2200000044.
  * [LP17] Günter Last and Matthew Penrose.  Lectures on the Poisson Process.  Institute of Mathematical Statistics Textbook. Cambridge University Press, Cambridge, UK, 2017.  doi:10.1017/9781316104477.
  * [LW97] Leonid Libkin and Limsoon Wong.  Query Languages for Bags and Aggregate Functions.  Journal of Computer and System Sciences, 55(2):241–272, 1997.  doi:10.1006/jcss.1997.1523.
  * [Mac75] Odile Macchi.  The Coincidence Approach to Stochastic Point Processes.  Advances in Applied Probability, 7(1):83–122, 1975.  doi:10.2307/1425855.
  * [Mil06] Brian Christopher Milch.  Probabilistic Models with Unknown Objects.  PhD thesis, University of California, Berkeley, 2006.
  * [MIW11] Raghotham Murthy, Robert Ikeda, and Jennifer Widom.  Making Aggregation Work in Uncertain and Probabilistic Databases.  IEEE Transactions on Knowledge and Data Engineering (TKDE), 23(8):1261–1273, 2011.  doi:10.1109/TKDE.2010.166.
  * [MMR+05] Brian Milch, Bhaskara Marthi, Stuart Russell, David Sontag, David L. Ong, and Andrey Kolobov.  BLOG: Probabilistic Models with Unknown Objects.  In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI ’05), St. Louis, MO, USA, 2005. Morgan Kaufmann.
  * [Moy62] José Enrique Moyal.  The General Theory of Stochastic Population Processes.  Acta Mathematica, 108:1–31, 1962.  doi:10.1007/BF02545761.
  * [MPS19] Paolo Morettin, Andrea Passerini, and Roberto Sebastiani.  Advanced SMT Techniques for Weighted Model Integration.  Artificial Intelligence, 275:1–27, 2019.  doi:10.1016/j.artint.2019.04.003.
  * [Pit94] Michael Pittarelli.  An Algebra for Probabilistic Databases.  IEEE Transactions on Knowledge and Data Engineering (TKDE), 6(2):293–303, 1994.
  * [PJLY07] Jian Pei, Bin Jiang, Xuemin Lin, and Yidong Yuan.  Probabilistic Skylines on Uncertain Data.  In Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB ’07), pages 15–26. VLDB Endowment, 2007.
  * [QJSP10] Yinian Qi, Rohit Jain, Sarvjeet Singh, and Sunil Prabhakar.  Threshold Query Optimization for Uncertain Data.  In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (SIGMOD 2010), pages 315–326. Association for Computing Machinery, 2010.  doi:10.1145/1807167.1807203.
  * [RD06] Matthew Richardson and Pedro Domingos.  Markov Logic Networks.  Machine Learning, 62(1–2):107––136, 2006.  doi:10.1007/s10994-006-5833-1.
  * [RDS07] Christopher Ré, Nilesh Dalvi, and Dan Suciu.  Efficient Top-$k$ Query Evaluation on Probabilistic Data.  In 2007 IEEE 23rd International Conference on Data Engineering (ICDE 2007), pages 886–895. IEEE, 2007.  doi:10.1109/ICDE.2007.367934.
  * [Rei81] Raymond Reiter.  On Closed World Databases, page 119–140.  Morgan Kaufmann, 1981.  doi:10.1016/B978-0-934613-03-3.50014-3.
  * [RSG05] Robert Ross, V. S. Subrahmanian, and John Grant.  Aggregate Operators in Probabilistic Databases.  Journal of the ACM (JACM), 52(1):54–101, 2005.  doi:10.1145/1044731.1044734.
  * [SD07] Parag Singla and Pedro Domingos.  Markov Logic in Infinite Domains.  In Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence (UAI ’07), pages 368–375, Arlington, VA, USA, 2007. AUAI Press.
  * [SMS+08] Sarvjeet Singh, Chris Mayfield, Rahul Shah, Sunil Prabhakar, Susanne Hambrusch, Jennifer Neville, and Reynold Cheng.  Database Support for Probabilistic Attributes and Tuples.  In 2008 IEEE 24th International Conference on Data Engineering (ICDE ’08), pages 1053–1061, Washington, DC, USA, 2008. IEEE Computer Society.  doi:10.1109/ICDE.2008.4497514.
  * [SORK11] Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch.  Probabilistic Databases.  Synthesis Lectures on Data Management. Morgan & Claypool, San Rafael, CA, USA, 1st edition, 2011.  doi:10.2200/S00362ED1V01Y201105DTM016.
  * [Sri98] Shashi Mohan Srivastava.  A Course on Borel Sets.  Graduate Texts in Mathematics. Springer, New York, NY, USA, 1st edition, 1998.  doi:10.1007/b98956.
  * [TPD+12] Thanh T. L. Tran, Liping Peng, Yanlei Diao, Andrew McGregor, and Anna Liu.  CLARO: Modeling and Processing Uncertain Data Streams.  The VLDB Journal, 21(5):651–676, 2012.  doi:10.1007/s00778-011-0261-7.
  * [VdBS17] Guy Van den Broeck and Dan Suciu.  Query Processing on Probabilistic Data: A Survey.  Foundations and Trends® in Databases, 7(3–4):197–341, 2017.  doi:10.1561/1900000052.
  * [Wid09] Jennifer Widom.  Trio: A System for Data, Uncertainty, and Lineage.  In Charu C. Aggarwal, editor, Managing and Mining Uncertain Data, volume 35 of Advances in Database Systems, chapter 5, pages 113–148. Springer, Boston, MA, USA, 2009.  doi:10.1007/978-0-387-09690-2\\_5.
  * [Wil04] Stephen Willard.  General Topology.  Dover Publications, Inc., Mineola, NY, USA, Dover reprint edition, 2004\.
  * [WLLW13] Yijie Wang, Xiaoyong Li, Xiaoling Li, and Yuan Wang.  A Survey of Queries over Uncertain Data.  Knowledge and Information Systems, 37(3):485–530, 2013.  doi:10.1007/s10115-013-0638-6.
  * [Won82] Eugene Wong.  A Statistical Approach to Incomplete Information in Database Systems.  ACM Transactions on Database Systems (TODS), 7(3):470–488, 1982\.  doi:10.1145/319732.319747.
  * [WSH+18] Yi Wu, Siddharth Srivastava, Nicholas Hay, Simon Du, and Stuart Russell.  Discrete-Continuous Mixtures in Probabilistic Programming: Generalized Semantics and Inference Algorithms.  In Proceedings of the 35th International Conference on Machine Learning (ICML 2018), volume 80 of Proceedings of Machine Learning Research, pages 5343–5352. PMLR, 2018.
  * [WvK15] Brend Wanders and Maurice van Keulen.  Revisiting the Formal Foundation of Probabilistic Databases.  In Proceedings of the 2015 Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology (IFSA-EUSFLAT ’15), Advances in Intelligent Systems Research, pages 289–296, Paris, France, 2015. Atlantis Press.
  * [Zim97] Esteban Zimányi.  Query Evaluation in Probabilistic Relational Databases.  Theoretical Computer Science, 171(1):179–219, 1997.  doi:10.1016/S0304-3975(96)00129-6.
  * [ZP97] Esteban Zimányi and Alain Pirotte.  Imperfect Information in Relational Databases.  In Amihai Motro and Philippe Smets, editors, Uncertainty Management in Information Systems, pages 35–87. Springer Science+Business Media, LLC, reprint of 1st edition, 1997.  doi:10.1007/978-1-4615-6245-0\\_3.

##  Appendix A Topologies and Metric Spaces

The brief account of topological notions is based upon [Wil04].

Let $\mathbb{X}$ be some set. A _topology_ on $\mathbb{X}$ is a family
$\mathfrak{O}$ of subsets of $\mathbb{X}$ that contains both $\emptyset$ and
$\mathbb{X}$, and is closed under finite intersections and (arbitrary, i. e.
possibly uncountable) unions. The pair $(\mathbb{X},\mathfrak{O})$ is called a
_topological space_. The sets in $\mathfrak{O}$ are called _open_ sets, and
their complements (with respect to $\mathbb{X}$) are called _closed_ sets.

For $\bm{X}\subseteq\mathbb{X}$, the _closure_ of $\bm{X}$ is the intersection
of all closed sets that contain $\bm{X}$. A set $\bm{X}$ is called _dense_ in
$(\mathbb{X},\mathfrak{O})$ if its closure is $\mathbb{X}$. The topological
space $(\mathbb{X},\mathfrak{O})$ is called _separable_ if there exists a
countable subset of $\mathbb{X}$ that is dense in $(\mathbb{X},\mathfrak{O})$.

Let $\mathbb{X}$ be a non-empty set and let
$d\colon\mathbb{X}\times\mathbb{X}\to\mathbb{R}$ be a function satisfying

  * •

$d(X,Y)\geq 0$ with $d(X,Y)=0$ if and only if $X=Y$;

  * •

$d(X,Y)=d(Y,X)$; and

  * •

$d(X,Z)\leq d(X,Y)+d(Y,Z)$ (the _triangle inequality_)

for all $X,Y,Z\in\mathbb{X}$. Then $d$ is called a _metric_ on $\mathbb{X}$
and the pair $(\mathbb{X},d)$ is called a _metric space_. For $\varepsilon>0$,
the set

$B_{\varepsilon}(X)\coloneqq\big{\\{}Y\in\mathbb{X}\colon
d(X,Y)<\varepsilon\big{\\}}$

is the _open ball of radius $\varepsilon$ around $X$_. The _metric topology_
on $\mathbb{X}$ with respect to $d$ is the topology $\mathfrak{O}$ on
$\mathbb{X}$ that is defined by

$\mathfrak{O}\coloneqq\big{\\{}\bm{X}\subseteq\mathbb{X}\colon\text{ for all
}X\in\bm{X}\text{ there exists some }\varepsilon>0\text{ such that
}B_{\varepsilon}(X)\subseteq\bm{X}\big{\\}}\text{.}$

A sequence $(X_{1},X_{2},\dots)$ of elements in a metric space
$(\mathbb{X},d)$ is called a _Cauchy sequence_ if
$\lim_{i\to\infty}d(X_{i},X_{i+1})=0$. A sequence $(X_{1},X_{2},\dots)$ in
$(\mathbb{X},d)$ _converges_ to an element $X\in\mathbb{X}$ in
$(\mathbb{X},d)$ if for all $\varepsilon\in(0,\infty)$ there exists some $i$,
large enough, such that $d(X,X_{i})<\varepsilon$. A metric $d$ on $\mathbb{X}$
is called _complete_ , if all Cauchy sequences over $(\mathbb{X},d)$ converge
to elements of $\mathbb{X}$. A metric space is called _complete_ , if its
metric is complete. In a metric space, a set $\bm{X}$ is dense (with respect
to the metric topology) if and only if for all $X\in\mathbb{X}$ and all
$\varepsilon>0$ there exists some $Y\in\mathbb{X}$ such that
$d(X,Y)<\varepsilon$.

A topological space $(\mathbb{X},\mathfrak{O})$ is called _metrizable_ if
there exists a metric $d$ on $\mathbb{X}$ such that $\mathfrak{O}$ is the
corresponding metric topology. If such $d$ exists that is additionally
complete, the space is called _completely metrizable_. A _Polish space_ is a
completely metrizable, separable topological space.