A Bayesian Method to Incorporate Background Knowledge during Automatic Text Summarization

Important facts in a new text are those which deviate from previous knowledge on the topic. When people create summaries, they use their knowledge about the world to decide what content in an input document is informative to include in a summary. Understandably in automatic summarization as well, it is useful to keep a background set of documents to represent general facts and their frequency in the domain.

For example, in the simplest setting of multi-document summarization of news, systems are asked to summarize an input set of topically-related news documents to reflect its central content. In this generic task, some of the best reported results were obtained by a system [] which computed importance scores for words in the input by examining if the word occurs with significantly higher probability in the input compared to a large background collection of news articles. Other specialized summarization tasks explicitly require the use of background information. In the update summarization task, a system is given two sets of news documents on the same topic; the second contains articles published later in time. The system should summarize the important updates from the second set assuming a user has already read the first set of articles.

In this work, we present a Bayesian model for assessing the novelty of a sentence taken from a summarization input with respect to a background corpus of documents.

Our model is based on the idea of Bayesian Surprise []. For illustration, assume that a user’s background knowledge comprises of multiple hypotheses about the current state of the world and a probability distribution over these hypotheses indicates his degree of belief in each hypothesis. For example, one hypothesis may be that the political situation in Ukraine is peaceful, another where it is not. Apriori assume the user favors the hypothesis about a peaceful Ukraine, i.e. the hypothesis has higher probability in the prior distribution. Given new data, the evidence can be incorporated using Bayes Rule to compute the posterior distribution over the hypotheses. For example, upon viewing news reports about riots in the country, a user would update his beliefs and the posterior distribution of the user’s knowledge would have a higher probability for a riotous Ukraine. Bayesian surprise is the difference between the prior and posterior distributions over the hypotheses which quantifies the extent to which the new data (the news report) has changed a user’s prior beliefs about the world.

In this work, we exemplify how Bayesian surprise can be used to do content selection for text summarization. Here a user’s prior knowledge is approximated by a background corpus and we show how to identify sentences from the input set which are most surprising with respect to this background. We use the method to do two types of summarization tasks: a) generic news summarization which uses a large random collection of news articles as the background, and b) update summarization where the background is a smaller but specific set of news documents on the same topic as the input set. We find that our method performs competitively with a previous log-likelihood ratio approach which identifies words with significantly higher probability in the input compared to the background. The Bayesian approach is more advantageous in the update task, where the background corpus is smaller in size.

Computing new information is useful in many applications. The TREC novelty tasks [] tested the ability of systems to find novel information in an IR setting. Systems were given a list of documents ranked according to relevance to a query. The goal is to find sentences in each document which are relevant to the query, and at the same time is new information given the content of documents higher in the relevance list.

For update summarization of news, methods range from textual entailment techniques [] to find facts in the input which are not entailed by the background, to Bayesian topic models [] which aim to learn and use topics discussed only in background, those only in the update input and those that overlap across the two sets.

Even for generic summarization, some of the best results were obtained by by using a large random corpus of news articles as the background while summarizing a new article, an idea first proposed by . Central to this approach is the use of a likelihood ratio test to compute topic words, words that have significantly higher probability in the input compared to the background corpus, and are hence descriptive of the input’s topic. In this work, we compare our system to topic word based ones since the latter is also a general method to find surprising new words in a set of input documents but is not a bayesian approach. We briefly explain the topic words based approach below.

Computing topic words: Let us call the input set $I$ and the background $B$. The log-likelihood ratio test compares two hypotheses:

$H_1$: A word $t$ is not a topic word and occurs with equal probability in $I$ and $B$, i.e. $p\left(t\right|I)=p\left(t\right|B)=p$

$H_2$: $t$ is a topic word, hence $p\left(t\right|I)=p_1$ and $p\left(t\right|B)=p_2$ and $p_1>p_2$

A set of documents $D$ containing $N$ tokens is viewed as a sequence of words $w_1$$w_2$…$w_N$. The word in each position $i$ is assumed to be generated by a Bernoulli trial which succeeds when the generated word $w_i=t$ and fails when $w_i$ is not $t$. Suppose that the probability of success is $p$. Then the probability of a word $t$ appearing $k$ times in a dataset of $N$ tokens is the binomial probability:

The likelihood ratio compares the likelihood of the data $D=\left\{B,I\right\}$ under the two hypotheses.

$p$, $p_1$ and $p_2$ are estimated by maximum likelihood. $p=c_t/N$ where $c_t$ is the number of times word $t$ appears in the total set of tokens comprising $\left\{B,I\right\}$. $p_1=c_t^I/N_I$ and $p_2=c_t^B/N_B$ are the probabilities of $t$ estimated only from the input and only from the background respectively.

A convenient aspect of this approach is that $-2\log \lambda$ is asymptotically ${\chi }^2$ distributed. So for a resulting $-2\log \lambda$ value, we can use the ${\chi }^2$ table to find the significance level with which the null hypothesis $H_1$ can be rejected. For example, a value of 10 corresponds to a significance level of 0.001 and is standardly used as the cutoff. Words with $-2\log \lambda >10$ are considered topic words. ’s system gives a weight of 1 to the topic words and scores sentences using the number of topic words normalized by sentence length.

First we present the formal definition of Bayesian surprise given by without reference to the summarization task.

Let H be the space of all hypotheses representing the background knowledge of a user. The user has a probability $P\left(H\right)$ associated with each hypothesis $H\in$ H. Let $D$ be a new observation. The posterior probability of a single hypothesis $H$ can be computed as:

The surprise $S\left(D,𝐇\right)$ created by $D$ on hypothesis space H is defined as the difference between the prior and posterior distributions over the hypotheses, and is computed using KL divergence.

Note that since KL-divergence is not symmetric, we could also compute $\text{KL}(P\left(H\right),P\left(H\right|D))$ as the surprise value. In some cases, surprise can be computed analytically, in particular when the prior distribution is conjugate to the form of the hypothesis, and so the posterior has the same functional form as the prior. (See for the surprise computation for different families of probability distributions).

We consider the hypothesis space H as the set of all the hypotheses encoding background knowledge. A single hypothesis about the background takes the form of a multinomial distribution over word unigrams. For example, one multinomial may have higher word probabilities for ‘Ukraine’ and ‘peaceful’ and another multinomial has higher probabilities for ‘Ukraine’ and ‘riots’. $P\left(H\right)$ gives a prior probability to each hypothesis based on the information in the background corpus. In our case, $P\left(H\right)$ is a Dirichlet distribution, the conjugate prior for multinomials. Suppose that the vocabulary size of the background corpus is $V$ and we label the word types as ($w_1$, $w_2$, … $w_V$). Then,

where ${\alpha }_{1:V}$ are the concentration parameters of the Dirichlet distribution (and will be set using the background corpus as explained in Section 4.2).

Now consider a new observation $I$ (a text, sentence, or paragraph from the summarization input) and the word counts in $I$ given by ($c_1$, $c_2$, …, $c_V$). Then the posterior over $H$ is the dirichlet:

The surprise due to observing $I$, $S\left(I,𝐇\right)$ is the KL divergence between the two dirichlet distributions. (Details about computing KL divergence between two dirichlet distributions can be found in and ).

Below we propose a general algorithm for summarization using surprise computation. Then we define the prior distribution $P\left(H\right)$ for each of our two tasks, generic and update summarization.

We compare against three types of systems, (i) those which similarly to surprise, use a background corpus to identify important sentences, (ii) a system that uses information from the input set only and no background, and (iii) systems that combine scores from the input and background.

${\text{𝐊𝐋}}_{\text{𝐛𝐚𝐜𝐤}}$: represents a simple baseline for surprise computation from a background corpus. A single unigram probability distribution $B$ is created from the background using maximum likelihood. The summary is created by greedily adding sentences which maximize KL divergence between $B$ and the current summary. Suppose the set of sentences currently chosen in the summary is $S$. The next step chooses the sentence $s_l=\arg {max}_{s_i}\text{KL}\left(\{S\cup s_i\}\right|\left|B\right)$ .

${\text{𝐓𝐒}}_{\text{𝐬𝐮𝐦}}$, ${\text{𝐓𝐒}}_{\text{𝐚𝐯𝐠}}$: use topic words computed as described in Section 2 and utilizing the same background corpus for the generic and update tasks as the surprise-based methods. For the generic task, we use a critical value of 10 (0.001 significance level) for the ${\chi }^2$ distribution during topic word computation. In the update task however, the background corpus A is smaller and for most inputs, no words exceeded this cutoff. We lower the significance level to the generally accepted value of 0.05 and take words scoring above this as topic words. The number of topic words is still small (ranging from 1 to 30) for different inputs.

The ${\text{TS}}_{\text{sum}}$ system selects sentences with greater counts of topic words and ${\text{TS}}_{\text{avg}}$ computes the number of topic words normalized by sentence length. A greedy selection procedure is used. To reduce redundancy, once a sentence is added, the topic words contained in it are removed from the topic word list before the next sentence selection.

${\text{𝐊𝐋}}_{\text{𝐢𝐧𝐩}}$: represents the system that does not use background information. Rather the method creates a summary by optimizing for high similarity of the summary with the input word distribution.

Suppose the input unigram distribution is $I$ and the current summary is $S$, the method chooses the sentence $s_l=\arg {min}_{s_i}\text{KL}\left(\{S\cup s_i\}\right|\left|I\right)$ at each iteration. Since $\left\{S\cup s_i\right\}$ is used to compute divergence, redundancy is implicitly controlled in this approach. Such a KL objective was used in competitive systems in the past [].

Input $\mathrm{+}$ background: These systems combine (i) a score based on the background (${\text{KL}}_{\text{back}}$, TS or SR) with (ii) the score based on the input only (${\text{KL}}_{\text{inp}}$). For example, to combine ${\text{TS}}_{\text{sum}}$ and ${\text{KL}}_{\text{inp}}$: for each sentence, we compute its scores based on the two methods. Then we normalize the two sets of scores for candidate sentences using z-scores and compute the best sentence as $\arg {max}_{s_i}$ (${\text{TS}}_{\text{sum}}\left(s_i\right)$ - ${\text{KL}}_{\text{inp}}\left(s_i\right)$). Redundancy control is done similarly to the TS only systems.

For evaluation, we compare each summary to the four manual summaries using ROUGE []. All summaries were truncated to 100 words, stemming was performed and stop words were not removed, as is standard in TAC evaluations. We report the ROUGE-1 and ROUGE-2 recall scores (average over the inputs) for each system. We use the Wilcoxon signed-rank test to check for significant differences in mean scores. Table 1 shows the scores for generic summaries and 2 for the update task. For each system, the peer systems with significantly better scores (p-value ) are indicated within parentheses.

We refer to the surprise-based summaries as ${\text{𝐒𝐑}}_{\text{𝐬𝐮𝐦}}$ and ${\text{𝐒𝐑}}_{\text{𝐚𝐯𝐠}}$ depending on the type of composition function (Section 4.1).

First, consider generic summarization and the systems which use the background corpus only (those above the horizontal line). The ${\text{KL}}_{\text{back}}$ baseline performs significantly worse than topic words and surprise summaries. Numerically, ${\text{SR}}_{\text{sum}}$ has the highest ROUGE-1 score and ${\text{TS}}_{\text{sum}}$ tops according to ROUGE-2. As per the Wilcoxon test, ${\text{TS}}_{\text{sum}}$, ${\text{SR}}_{\text{sum}}$ and ${\text{SR}}_{\text{avg}}$ scores are statistically indistinguishable at 95% confidence level.

Systems below the horizontal line in Table 1 use an objective which combines both similarity with the input and difference from the background. The first line here shows that a system optimizing only for input similarity, ${\text{KL}}_{\text{inp}}$, by itself has higher scores (though not significant) than those using background information only. This result is not surprising for generic summarization where all the topical content is present in the input and the background is a non-focused random collection. At the same time, adding either TS or SR scores to ${\text{KL}}_{\text{inp}}$ almost always leads to better results with ${\text{KL}}_{\text{inp}}+{\text{TS}}_{\text{avg}}$ giving the best score.

In update summarization, the surprise-based methods have an advantage over the topic word ones. ${\text{SR}}_{\text{avg}}$ is significantly better than ${\text{TS}}_{\text{avg}}$ for both ROUGE-1 and ROUGE-2 scores and better than ${\text{TS}}_{\text{sum}}$ according to ROUGE-1. In fact, the surprise methods have numerically higher ROUGE-1 scores compared to input similarity (${\text{KL}}_{\text{inp}}$) in contrast to generic summarization. When combined with ${\text{KL}}_{\text{inp}}$, the surprise methods provide improved results, significantly better in terms of ROUGE-1 scores. The TS methods do not lead to any improvement, and ${\text{KL}}_{\text{inp}}+{\text{TS}}_{\text{avg}}$ is significantly worse than ${\text{KL}}_{\text{inp}}$ only. The limitation of the TS approach arises from the paucity of topic words that exceed the significance cutoff applied on the log-likelihood ratio. But Bayesian surprise is robust on the small background corpus and does not need any tuning for cutoff values depending on the size of the background set.

Note that these models do not perform on par with summarization systems that use multiple indicators of content importance, involve supervised training and which perform sentence compression. Rather our goal in this work is to demonstrate a simple and intuitive unsupervised model.

We have introduced a Bayesian summarization method that strongly aligns with intuitions about how people use existing knowledge to identify important events or content in new observations.

Our method is especially valuable when a system must utilize a small background corpus. While the update task datasets we have used were carefully selected and grouped by NIST assesors into initial and background sets, for systems on the web, there is little control over the number of background documents on a particular topic. A system should be able to use smaller amounts of background information and as new data arrives, be able to incorporate the evidence. Our Bayesian approach is a natural fit in such a setting.

The author was supported by a Newton International Fellowship (NF120479) from the Royal Society and the British Academy.

/thesis.