23.3.1 Summarizing Single Documents

Let's first consider the task of building an extractive summary for a single document. Assuming that the units being extracted are at the level of the sentence, the three summarization stages for this task are:

1. Content Selection: Choose sentences to extract from the document

2. Information Ordering: Choose an order to place these sentences in the summary

3. Sentence Realization: Clean up the sentences, for example by removing non-essential phrases from each sentence, or fusing multiple sentences into a single sentence, or by fixing problems in coherence.

We'll first describe basic summarization techniques with only one of these components: content selection. Indeed, many single document summarizers have no infor-

mation ordering component, simply ordering the extracted sentences in the order they appeared in the original document. In addition, we'll assume for now that sentences are not combined or cleaned up after they are extracted, although we'll briefly mention later how this is done.

Unsupervised Content Selection

The content selection task of extracting sentences is often treated as a classification task. The goal of the classifier is to label each sentence in a document with a binary label: important versus unimportant (or extract-worthy versus not extractworthy). We begin with some unsupervised algorithms for sentence classification and then turn to supervised algorithms in the next section.

The simplest unsupervised algorithm, based on an intuition that dates back to the early summarizer of (Luhn, 1958), is to select sentences that have more \textit{salient} or \textit{informative} words. Sentences that contain more informative words tend to be more extract-worthy. Saliency is usually defined by computing the \textit{topic} signature, a set of \textit{salient} or \textit{signature} terms, each of whose saliency scores is greater than some threshold $ \theta $.

Saliency could be measured in terms of simple word frequency, but frequency has the problem that a word might have a high probability in English in general but not be particularly topical to a particular document. Therefore weighting schemes like tf-idf or log-likelihood ratio are more often used.

Recall from page 8 that the tf-idf scheme gives a high weight to words that appear frequently in the current document, but rarely in the overall document collection, suggesting that the word is particularly relevant to this document. For each term $i$ that occurs in the sentence to be evaluated, we compute its count in the current document $j$ $tf_{i,j}$, and multiply by the inverse document frequency over the whole collection idf;

$$ weight(w_{i})=tf_{i,j}\times idf_{i} $$

A better performing method for finding informative words is log likelihood ratio (LLR). The log likelihood ratio for a word, generally called $ \lambda(w) $, is the ratio between the probability of observing w both in the input and in the background corpus assuming equal probabilities in both corpora, and the probability of observing w in both assuming different probabilities for w in the input and the background corpus. See Dunning (1993), Moore (2004) and Manning and Schütze (1999) for details on log likelihood and how it is calculated.

It turns out for log likelihood ratio that the quantity $ -2\log(\lambda) $ is asymptotically well approximated by the $ \chi^2 $ distribution, which means that a word appears in the input significantly more often than in the background corpus (at $ \alpha = 0.001 $) if $ -2\log(\lambda) > 10.8 $. Lin and Hovy (2000) first suggested that this made log likelihood ratio particularly appropriate for selecting a topic signature for summarization. Thus the word weight with log likelihood ratio is generally defined as follows:

$$ weight(w_{i})=\left\{\begin{array}{ll}1&\text{if}-2\log(\lambda(w_{i}))>10\\ 0&\text{otherwise.}\end{array}\right. $$

Equation (23.26) is used to set a weight of 1 or 0 for each word in the sentence. The score for a sentence $ s_{i} $ is then the average weight of its non-stop words:

$$ weight(s_{i})=\sum_{w\in s_{i}}\frac{weight(w)}{|\{w|w\in s_{i}\}|} $$

The summarization algorithms computes this weight for every sentence, and then ranks all sentences by their score. The extracted summary consists of the top ranked sentences.

The family of algorithms that this thresholded LLR algorithm belongs to is called centroid-based summarization because we can view the set of signature terms as a pseudo-sentence which is the 'centroid' of all the sentences in the document and we are looking for sentences which are as close as possible to this centroid sentence.

A common alternative to the log likelihood ratio/centroid method is to use a different model of sentence centrality. These other centrality based methods resemble the centroid method described above, in that their goal is to rank the input sentences in terms of how central they are in representing the information present in the document. But rather than just ranking sentences by whether they contain salient words, centrality based methods compute distances between each candidate sentence and each other sentence and choose sentences that are on average closer to other sentences. To compute centrality, we can represent each sentence as a bag-of-words vector of length N as described in Ch. 20. For each pair of sentences x and y, we compute the tf-idf weighted cosine as described in Equation (23.12) above.

Each of the k sentences in the input is then assigned a centrality score which is its average cosine with all other sentences:

$$ centrality(x)=\frac{1}{K}\sum_{y}tf-idf-cosine(x,y) $$

Sentences are ranked by this centrality score, and the sentence which has the highest average cosine across all pairs, i.e. is most like other sentences, is chosen as the most 'representative' or 'topical' of all the sentences in the input.

It is also possible to extend this centrality score to use more complex graph-based measures of centrality like PageRank (Erkan and Radev, 2004).

Unsupervised Summarization based on Rhetorical Parsing

The sentence extraction algorithm we introduced above for content extraction relied solely on a single shallow feature, word saliency, ignoring possible higher-level cues such as discourse information. In this section we briefly summarize a way to get more sophisticated discourse knowledge into the summarization task.

The summarization algorithm we'll describe makes use of coherence relations such as the RST (rhetorical structure theory) relations described in Ch. 21. Recall that RST relations are often expressed in terms of a satellite and a nucleus; nucleus sentence are more likely to be appropriate for a summary. For example, consider the following two paragraphs taken from the Scientific American magazine text that we introduced in Fig. ??:

With its distant orbit - from the sun than Earth - and slim atmosphere other conditions. Surface temperature at the

Only the midday sun at tropical latitudes is warm enough to thaw ice on occasion, but any liquid water formed in this way would evaporate almost instantly because of the low atmospheric pressure. Although the atmosphere holds a small amount of water, and water-ice clouds sometimes develop, most Martian weather involves blowing dust or carbon dioxide.

The first two discourse units in this passage are related by the RST JUSTIFICATION relation, with the first discourse unit justifying the second unit, as shown in Fig. 23.15. The second unit (“Mars experiences frigid weather conditions”) is thus the nucleus, and captures better what this part of the document is about.

We can use this intuition for summarization by first applying a discourse parser of the type discussed in Ch. 21 to compute the coherence relations between each discourse unit. Once a sentence has been parsed into a coherence relation graph or parse tree, we can use the intuition that the nuclear units are important for summarization by recursively extracting the salient units of a text.

Consider the coherence parse tree in Fig. 23.16. The salience of each node in the tree can be defined recursively as follows:

Base case: The salient unit of a leaf node is the leaf node itself

• Recursive case: The salient units of an intermediate node are the union of the salient units of its immediate nuclear children

By this definition, discourse unit (2) is the most salient unit of the entire text (since the root node spanning units 1-8 has the node spanning units 1-6 as its nucleus, and unit 2 is the nucleus of the node spanning units 1-6.)

If we rank each discourse unit by the height of the nodes that it is the nucleus of, we can assign a partial ordering of salience to units; the algorithm of Marcu (1995) assigns the following partial ordering to this discourse:

$$ 2>8>3>1,4,5,7>6 $$

See Marcu (1995, 2000) for the details of exactly how this partial order is computed, and Teufel and Moens (2002) for another method for using rhetorical structure in summarization.

Supervised Content Selection

While the use of topic signatures for unsupervised content selection is an extremely effective method, topic signatures is only a single cue for finding extractworthy sentences. Many other cues exist, including the alternative saliency methods discussed above like centrality and PageRank methods, as well as other cues like the position of the sentence in the document (sentences at the very beginning or end of the document tend to be more important), the length of each sentence, and so on. We'd like a method that can weigh and combine all of these cues.

The best principled method for weighing and combining evidence is supervised machine learning. For supervised machine learning, we'll need a training set of documents paired with human-created summary extracts, such as the Ziff-Davis corpus (Marcu, 1999). Since these are extracts, each sentence in the summary is, by definition, taken from the document. That means we can assign a label to every sentence in the document; 1 if it appears in the extract, 0 if it doesn't. To build our classifier, then, we just need to choose features to extract which are predictive of being a good sentence to appear in a summary. Some of the features commonly used in sentence classification are shown in Fig. 23.17.

Each sentence in our training document thus has a label (0 if the sentence is not in the training summary for that document, 1 if it is) and set of extracted feature values like those in Fig. 23.17. We can then train our classifier to estimate these labels for unseen data; for example a probabilistic classifier like naive Bayes or MaxEnt would

be computing the probability that a particular sentence $s$ is extractworthy given a set of features $f_{1}...f_{n}$; then we can just extract any sentences for which this probability is greater than 0.5:

$$ P(extractworthy(s)|f_{1},f_{2},f_{3},...,f_{n}) $$

There is one problem with the algorithm as we've described it: it requires that we have a training summary for each document which consists solely of extracted sentences. If we could weaken this restriction, we could apply the algorithm to a much wider variety of summary-document pairs, such as conference papers or journal articles and their abstracts. Luckily it turns out that when humans write summaries, even with the goal of writing abstractive summaries, they very often use phrases and sentences from the document to compose the summary. But they don't use only extracted sentences; they often combine two sentences into one, or change some of the words in the sentences, or write completely new abstractive sentences. Here is an example of an

extracted sentence from a human summary that, although modified in the final human summary, was clearly a document sentence that should be labeled as extractworthy:

(23.31) Human summary: This paper identifies the desirable features of an ideal multisensor gas monitor and lists the different models currently available.

(23.32) Original document sentence: The present part lists the desirable features and the different models of portable, multisensor gas monitors currently available.

Thus an important preliminary stage is to align each training document with its summary, with the goal of finding which sentences in the document were (completely or mostly) included in the summary. A simple algorithm for alignment is to find the source document and abstract sentences with the longest common subsequences of non-stopwords; alternatively minimum edit distance can be computed, or more sophisticated knowledge sources can be used, such as WordNet. Recent work has focused on more complex alignment algorithms such as the use of HMMs (Jing, 2002; Daumé III and Marcu, 2005, inter alia).

Given such alignment algorithms, supervised methods for content selection can make use of parallel corpora of documents and human abstractive summaries, such as academic papers with their abstracts (Teufel and Moens, 2002).

Sentence Simplification

Once a set of sentences has been extracted and ordered, the final step in single-document summarization is sentence realization. One component of sentence realization is sentence compression or sentence simplification. The following examples, taken by Jing (2000) from a human summary, show that the human summarizer chose to eliminate some of the adjective modifiers and subordinate clauses when expressing the extracted sentence in the summary:

(23.33) Original sentence: When it arrives sometime new year in new TV sets, the V-chip will give parents a new and potentially revolutionary device to block out programs they don't want their children to see.

(23.34) Simplified sentence by humans: The V-chip will give parents a device to block out programs they don't want their children to see.

The simplest algorithms for sentence simplification use rules to select parts of the sentence to prune or keep, often by running a parser or partial parser over the sentences. Some representative rules from Zajic et al. (2007), Conroy et al. (2006), and Vanderwende et al. (2007a) remove the following:

More sophisticated models of sentence compression are based on supervised machine learning, in which a parallel corpus of documents together with their human

summaries is used to compute the probability that particular words or parse nodes will be pruned. See the end of the chapter for pointers to this extensive recent literature.

23.4 MULTI-DOCUMENT SUMMARIZATION

When we apply summarization techniques to groups of documents rather than a single document we call the goal multi-document summarization. Multi-document summarization is particularly appropriate for web-based applications, for example for building summaries of a particular event in the news by combining information from different news stories, or finding answers to complex questions by including components from extracted from multiple documents.

While multi-document summarization is far from a solved problem, even the current technology can be useful for information-finding tasks. McKeown et al. (2005), for example, gave human experimental participants documents together with a human summary, an automatically generated summary, or no summary, and had the participants perform time-restricted fact-gathering tasks. The participants had to answer three related questions about an event in the news; subjects who read the automatic summaries gave higher-quality answers to the questions.

Multi-document summarization algorithms are based on the same three steps we've seen before. In many cases we assume that we start with a cluster of documents that we'd like to summarize, and we must then perform content selection, information ordering, and sentence realization, as described in the next three sections and sketched in Fig. 23.18