The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

2E1-02

A Clustering Based Approach to Sentence Orderingfor Multidocument Summarization and its Evaluation
Danushka Bollegala

Naoaki Okazaki

Mitsuru Ishizuka

Graduate School of Information Science and Technology, The University of Tokyo
Ordering information is a diﬃcult but a important task for natural language generation applications. A wrong
order of information does not only make it diﬃcult to understand, but also conveys an entirely diﬀerent idea tothe reader. This paper proposes an algorithm that learns orderings from a set of human ordered texts. We cluster
sentences into locally coherent blocks and use a hierarchical clustering algorithm which merge these blocks tocreate a complete summary. Our experimental results show a signiﬁcant improvement over the existing methodsof sentence ordering.

1.

Introduction

All the above mentioned strategies to sentence ordering
has a top-down approach and tries to ﬁnd a total orderamong sentences. However, in some cases it is impossible
to decide the order between two sentences simply by considering those two sentences only. First we need to consider
the sentences which are more clear in their order and thenorder the rest of the sentences to ﬁx into this framework.
Marcu [7] argues that global coherence can be achieved bysatisfying local coherence constraints. He combines the locally coherent blocks in a tree (discourse tree) such thatthe adjacent nodes satisfy some rhetorical relation. Thenthe problem of planning a coherent text becomes a one ofsearching for the discourse tree that best satisﬁes the rhetorical relations. He uses Cocke-Kasami-Younger (CYK) parsing algorithm to generate all the valid trees and proposes
greedy searching techniques to speed up the search.
However, in a set of sentences extracted from diﬀerent
documents, identifying the rhetorical relations is a diﬃculttask. Therefore, we deﬁne a ﬁtness measure for two blocks
of texts to be cohesive based on chronology, topical relevance, precedence and succedence and use this ﬁtness measure to merge the blocks in a hierarchical clustering manner.
According to Halliday and Hasan [6] sentences are bound together by various cohesion relations. We should retain suchblocks of texts in our summary for it to be comprehensible.
Therefore, we take a bottom-up approach and ﬁrst groupthe sentences which are locally coherent and then merge
these groups to build a complete summary.

With the popularity of the internet, information available
in electronic formats have grown rapidly. It has become impossible for users to go through all these information to ﬁnd
what they need. Therefore, eﬃcient searching and summarization algorithms are a must. However, extracting information is not suﬃcient and we need to properly organize
the extracted information. For example, in multidocument
summarization (MDS), a summary is generated from a setof documents. The documents may belong to diﬀerent topics and written by diﬀerent authors. The information they
contain may be contradictory or repetitive. Sentences extracted from such a diverse set of documents need to beproperly ordered to create a coherent summary. Barzilay [1]shows that proper ordering of sentences improves readability of a summary.
In the case of news summarization, ordering the sentences
according to their publication date is an eﬀective heuristic [5, 8]. News events have the tendency to occur in achronological order. Barzilay [1] proposes an improved version of this chronological ordering by grouping the sentences
according to their topics. Without a proper pretext certain
sentences are incomprehensible. Such constraints among
sentences are called precedence relations. Okazaki [9] proposes a sentence ordering algorithm that use precedence relations among sentences to improve the chronological ordering. In addition to these studies which make use of chronological ordering, Lapata [4] proposes a probabilistic modelof text structuring and its application to the sentence ordering. Her system calculates the conditional probabilities
between sentences from a corpus and uses a greedy ordering
algorithm to arrange sentences according to the conditional
probabilities. Even though these previous studies proposed
diﬀerent strategies to decide the sentence ordering, the appropriate way to combine these diﬀerent methods to obtain more robust and coherent text remains unknown. In
our previous work [2] we proposed succedence as anotherstrategy for sentence ordering and combined it with all theexisting heurstics for the task of sentence ordering using
Cohen’s [3] hedge based ordering model.

2.

MethodWe deﬁne the ﬁtness of merging two blocks of texts using
four diﬀerent values; chronology, topical relatedness, precedence and succedence. Then we partition the human-madeorderings into blocks and calculate the individual ﬁtness
values for each pair of blocks. We then train a two class support vector machine(SVM) [10] using these training blocks.
We consider the class probability of support vector machineas the integrated ﬁtness for a given pair of blocks. Using
the trained SVM, we hierarchically cluster the blocks toconstruct a complete summary.

Contact: {danushka,okazaki,ishizuka}@miv.t.u-tokyo.ac.jp1

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

:

:

2

$NQEM#l:R$NQEM#:R;&QEWOGPV &Figure 2: Precedence$NQEM$constraints that must be satisﬁed by sentences are called
precedence relations [9]. For example let us consider thesituation illustrated in ﬁgure 2. Here, we are interested in
the case where block A precedes block B as in ﬁgure 1. Sentence l ∈ B, is preceded by a block of text P in the source
document D from which sentence l was extracted. The author of document D assumes that the block P is necessary
to properly understand sentence l. Therefore, in our summary too we need to ﬁnd a block A that matches best with
P if we are to connect block B after block A. The similarity
between block A and P is deﬁned as precedence of sentencel and it is written as pre(l).

;S
Figure 1: Comparing two blocks of texts

2.1

Chronology

Figure 1 shows two blocks of texts. Block A consists of pnumber of sentences (X1 , . . . , Xp ) and block B has q numberof sentences (Y1 , . . . , Yq ). The two blocks can be ordered B
after A or A after B. We use the notation (A,B) to denotethe ordering where block B comes after block A. Then, thechronological ﬁtness of (A,B) is deﬁned as follows.

pre(l) = max sim(l, x)x∈A

Fchro (A, B)


1



1
=

 0.5
0

(1)
We deﬁne the precedence ﬁtness of (A,B) as follows.

T (Xp ) < T (Y1 )[D(Xp ) = D(Y1 )] ∧ [N (Xp ) < N (Y1 )][T (Xp ) = T (Y1 )] ∧ [D(Xp ) = D(Y1 )]otherwise

Fpre (A, B) =2.4

Topical Relevance

Succedence:$NQEM#x∈A

Here, we take the cosine similarity of the word vectors assim(l, x). Using equation 2 we deﬁne the topical relevanceof blocks (A,B) as follows.
1
topic(y)
q

:R

:R

;

-

;S

&QEWOGPV&$NQEM$(3)
Figure 3: succedence

y∈B

2.3

(5)

When summarizing a set of documents which belong to
the same event, there may be more than one sentences
which convey the same information. In order to avoid repetition of information, most summarization algorithms select
only one sentence out of these multiple candidates to be included in the summary. However, the left out candidates
provide valuable information to decide the sentence order.
Succedence [2] is a measure of cross-document similarity
which helps to recognize such hidden orderings.

Grouping sentences according to their topics improves coherence of a text [6]. Motivated by this fact, we deﬁned a
topical relevance function for extract sentences [2]. We extend this concept to cover blocks of sentences by averaging
the topical relevance of each sentence in the block. First we
extract the nouns, verbs and connection words for each sentence and create the word vector for that sentence. Then,for each sentence l ∈ B, we deﬁne its topical relevance asfollows.
topic(l) = max sim(l, x)(2)

Ftopic (A, B) =1pre(y)qy∈B

Therein: T (u) is the publication date of sentence u; D(u)presents the unique identiﬁer of the document to which sentence u belongs; N (u) denotes the line number of sentenceu in the original document.

2.2

(4)

Precedence

Let us consider the situation illustrated in ﬁgure 3 where
block A is being placed ahead of block B. Xp is the last sentence of block A and it comes from document D. Succedenceof sentence y ∈ B , succ(y), is calculated as the similarity
between y and the block K of text that appears after thesentence Xp in document D. succ(y) deﬁned by equation 6.

When placing a sentence in the summary it is importantto check whether the preceding sentences convey the necessary background information for this sentence to be clearly
understood. Placing a sentence without its context being
stated in advanced, makes an unintelligible summary. Such

2

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

succ(y) = max sim(l, y)l∈K1succ(y)q(KVPGUU

We deﬁne the succedence of a block of text as the averageof each sentence’s succedence.
Fsucc (A, B) =

$
#
%
&

(6)

(7)

y∈B

Therein; succ(y) is the succedence of sentence y andFsucc (A, B) is the succedence of block B appearing after
block A.

2.5

%

$

#

Training&

Figure 5: Clustering process

C
D
E
F

Table 1: Comparison with Human Ordering
Sp
K
Cont
WK
AC
RO
-0.127 -0.069 0.127 0.025 0.011
PO
0.076
0.068
0.126 0.065 0.037
ChO
0.583
0.587
0.576 0.634 0.356
HeO
0.585
0.589
0.639 0.639 0.402
ClO
0.603
0.612
0.694 0.669 0.459
HO
1.000
1.000
1.000 1.000 1.000

Figure 4: Generating training examples

We partition each human-ordered summary into continuous blocks. For example, in the case illustrated in ﬁgure 4,
the summary consists of four sentences a,b,c and d. Wethen generate the following six pairs of blocks from thissummary by excluding sentences from the end of the summary; a|bcd, ab|cd, abc|d, a|bc, ab|c, a|b. Usually, a summaryis read from top to bottom and sentences appearing at the
top of the summary are more important than the ones thatappear to the end of the summary. Therefore, we decided toretain the top sentences in our blocks and remove from theend. For a summary of length n this partition process generates (n − 1)(n − 2)/2(= O(n2 )) number of pairs of blocks.
Although there are other partitioning methods to generate blocks, one must consider the complexity issues whenlearning with lots of training data. Moreover, the paritioning method we propose yields continuous blocks in pairs
and such blocks are more reliable than discontinous blocks.
We create training data vectors with label +1 for the casewhere the two blocks are ordered as in the human-orderedsummary and label -1 for its reverse. In our example, wehave the following two cases for the pair of blocks ab|cd.

have diﬀerent integrated ﬁtness values in our model. We
use arrows to state this fact in ﬁgure 5.

3.

41


21

%J1

*G1

%N1

2TGEKUKQP


















UGPVGPEGPITCONGPIVJ

Figure 6: Precision vs sentence n-gram length[Fchro (ab, cd), Ftopic (ab, cd), Fpre (ab, cd), Fsucc (ab, cd), +1][Fchro (cd, ab), Ftopic (cd, ab), Fpre (cd, ab), Fsucc (cd, ab), −1]

We used the 3rd Text Summarization Challenge (TSC)
corpus for our experiments. TSC∗1 corpus contains news
articles taken from two leading Japanese newspapers;
Mainichi and Yomiuri. TSC-3 corpus contains extracted
sentences for 30 summaries of diﬀerent topics. However, in
the TSC corpus the extracted sentences are not ordered tomake a readable summary. Therefore, we ﬁrst prepared 30
summaries by ordering the extraction data of TSC-3 corpus
by hand. We then compared the orderings by the proposed
algorithm against these human ordered summaries using

We train a two-class linear-kernel SVM using these training
vectors.

2.6

Results

Clustering

Initially, we create a block per each extract sentence.
Then we repeatedly merge two blocks at a time in a hierarchical manner until we are left with a single block oftext as depicted in ﬁgure 5. At each step we ﬁnd the pair ofblocks which has the highest integrated ﬁtness value. The
integrated ﬁtness value is the class probability returned by
the trained SVM in section 2.5. Note that (A,B) and (B,A)∗1 http://lr-www.pi.titech.ac.jp/tsc/index-en.html

3

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
ﬁve evaluation metrics: Spearman rank correlation coefﬁcient (Sp), Kendall’s coeﬃcient (K), Continuity (C) [9],Weighted Kendall’s coeﬃcient (WK) [2] and Average Continuity (AC) [2]. Weighted Kendall Coeﬃcient is an exponentially weighted version of the discordants in Kendall’s
coeﬃcient. Average Continuity is deﬁned by equation 9. It
is the logarithmic average of the sentence continuity precision, Pn deﬁned by equation 8, where N is the summary
length and n is the length of sentence n-gram.
Pn =number of matched n-grams.
N −n+11
log(Pn ))3[2] Danushka Bollegala, Naoaki Okazaki, and Mitsuru
Ishizuka. A machine learning approach to sentence ordering for multidocument summarization and its evaluation. Proceedings of the Natural Language Processiong
society of Japan, pages 000–000, 2005.
[3] W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to order things. Journal of Artificial Intelligence
Research, 10:243–270, 1999.
[4] Mirella Lapata. Probabilistic text structuring: Experiments with sentence ordering. Proceedings of the annual meeting of ACL, 2003., pages 545–552, 2003.

(8)

4

Average Continuity = exp(

[5] C.Y. Lin and E. Hovy. Neats:a multidocument summarizer. Proceedings of the Document Understanding
Workshop(DUC), 2001.

(9)

n=2

We compared the proposed clustering order algorithm(ClO) with Random Order (RO), Probabilistic Order(PO) [4], Chronology Order (ChO), Hedge learning based
Order (HeO) [2] and Human-made Order (HO). Resultsfrom our experiments are shown in table 1 and ﬁgure 6.
ANOVA test shows a statistically signiﬁcant diﬀerence
among the methods compared in table 1. Moreover, student t-tests performed between chronological order andclustering order showed a statistically signiﬁcant improvement when compared by Average Continuity and Continuity metric [9]. However, we could not ﬁnd any statisticalsigniﬁcance when compared by the other evaluation metrics. According to ﬁgure 6, clustering order has the highest
precision values among all the methods for all lengths ofsentence continuities.

4.

[6] M.A.K.Halliday and Ruqaiya Hasan. Cohesion in English. Longman, 1976.
[7] Daniel Marcu. From local to global coherence: A
bottom-up approach to text planning. In Proceedingsof the 14th National Conference on Artificial Intelligence, pages 629–635, Providence, Rhode Island, 1997.
[8] Kathleen McKeown, Judith Klavans, Vasileios Hatzivassiloglou, Regina Barzilay, and Eleazar Eskin. Towards multidocument summarization by reformulation: Progress and prospects. AAAI/IAAI, pages 453–
460, 1999.
[9] Naoaki Okazaki, Yutaka Matsuo, and Mitsuru
Ishizuka. An integrated summarization system withsentence ordering using precedence relation. ACMTALIP, to appear in 2005., 2005.

Conclusion

We proposed a clustering based approach to sentence ordering for multidocument summarization. Our experimental results showed a satisfactory improvement over the existing methods for sentence ordering. However, we need toperform a human evaluation on the readability of our ordered summaries. Ordering the sentences is only the ﬁrst
step towards creating a readable summary. We need to perform amendments to sentences and smoothen the transition
from a sentence to the next. Moreover, our algorithm does
not take into account the cohesion relations suggested byHalliday and Hasan [6]. In our future work, we plan toextend the algorithm to cover these issues.

[10] V. Vapnik. Statistical Learning Theory. Wiley, Chichester, GB, 1998.

Acknowledgment
We made use of Mainichi Newspaper and Yomiuri Newspaper articles and summarization test collection of TSC-3.
We wish to thank reviewers for valuable comments on ourpaper.

References[1] Regina Barzilay, Noemie Elhadad, and Kathleen McKeown. Inferring strategies for sentence ordering in multidocument news summarization. Journal of Artificial
Intelligence Research, 17:35–55, 2002.

4