UTIYAMA Masao Communications Research Laboratory 588-2, Iwaoka, Nishi-ku, Kobe, Hyogo 651-2492, Japan mutiyama@crl.go.jp HASIDA Kôiti Electrotechnical Laboratory 1-1-4, Umezono, Tukuba, Ibaraki 305-8568, Japan hasida@etl.go.jp
A bstract
Summarization of multiple documents featur- ing multiple topics is discussed. The exam- ple treated here consists of fifty articles about the Peru hostage incident for December 1996 through April 1997. They include a lot of top- ics such as opening, negotiation, ending, and The method proposed in this paper is so on. based on spreading activation over documents syntactically and semantically annotated with GDA (Global Document Annotation) tags. The method extracts important documents and im- portant parts therein, and creates a network consisting of important entities and relations among them. It also identifies cross-document coreferences to replace expressions with more concrete ones. The method is essentially multi- lingual due to the language-independence of the This tagset can provide a stan- GDA tagset. dard format for the study on the transformation and/or generation stage of summarization pro- cess, among other natural language processing tasks.
Introduction
1
A large event consists of a number of smaller These component events are usually events. related but such relations may not be strong enough to define larger topics. For example, a war may consist of opening, battles, negotia- tions, and so on. These relatively independent events are considered to be topics by themselves and would accordingly be reported in multiple news articles. Summarization of such a large event, or mul- tiple documents about multiple topics, is the concern of this paper. Summarization of multi- ple documents containing multiple topics is an unexplored research issue. Some previous stud- ies on summarization (McKeown and Radev, 1995; Barzilay et al., 1999; Mani and Bloedorn, 1999) deal with multiple documents about a sin- gle topic, but not about multiple topics 1 . In order to summarize multiple documents with multiple topics, one needs a general, semantics-oriented method for evaluating im- portance. Summarization of a single document may largely exploit the document structure. As an extreme example, the first paragraph of a newspaper article often serves as a summary of the entire article. On the other hand, summa- rization of multiple documents in general must be more based on their semantic structures, be- cause there is no overall consistent document structure across them. Selection of multiple important topics (not keywords) for multiple-topic summarization has not yet been really addressed in the previ- ous literature. The present paper proposes a method, based on spreading activation, for ex- tracting important topics and important docu- ments. Another method proposed which is use- ful for grasping the overview of multiple docu- ments is visualization of important entities men- tioned and relationships among them. Visu- alization of relationships among keywords has been studied in the context of information re- trieval (Niwa et al., 1997; Sanderson and Croft, 1999), but to the authors' knowledge the present study is the first to address such visualization in the context of summarization. Of course a con- cise summary of the entire set of multiple docu- ments can be obtained by recovering sentences from important entities and their relationships as demonstrated in section 3.3. The present study assumes documents anno- tated with GDA (Global Document Annota- tion) tags (Hasida, 1997; Nagao and Hasida, 1998). Since the GDA tagset is designed to be independent of any particular natural language, the proposed method is essentially multilingual. Another merit of using annotated documents is that we can separate the analysis phase from the whole process of summarization so that we can focus on the latter, generation phase of sum- marization process. Annotated documents can also be useful for a common input format for the study of summarization, among other nat- ural language processing tasks.
2
The GDA Tagset
GDA is a project to make on-line documents machine-understandable on the basis of a lin- guistic tagset, while developing and spread- ing technologies of content-based presentation, retrieval, question-answering, summarization, translation, among others, with much higher quality than before. GDA thus proposes an integrated global platform for electronic con- tent authoring, presentation, and reuse. The GDA tagset² is an XML (eXtensible Markup Language) instance which allows machines to automatically infer the semantic and pragmatic structures underlying the raw documents. Under the current state of the art, GDA- tagging is semiautomatic and calls for manual correction by human annotators; otherwise an- notation would make no sense.  The cost in- volved here pays, because annotated documents are generic information contents from which to render diverse types of presentations, poten- tially involving summarization, narration, visu- alization, translation, information retrieval, in- formation extraction, and so forth. The present paper concerns summarization only, but the merit of GDA-tagging is not at all restricted to summarization, and that is why it is considered reasonable to assume GDA-tagged input here.
2.1
Syntactic structure
An example of a GDA-tagged sentence is shown in Figure 1. <su> means sentential unit. <np>, <v>, and <adp> stand for noun phrase, verb, and adnominal or adverbial phrase. <su> and the tags whose name end with 'p' (such as <adp> and <vp>) are called phrasal tags. In a sentence, an element (a text span ²http://www.etl.go.jp/etl/nl/GDA/tagset.html from a begin tag to the corresponding end tag) is usually a syntactic constituent. The elements enclosed in phrasal tags are called phrasal ele- ments, which cannot be the head of larger ele- ments.  So in Figure 1 'flies' is specified to be the head of the <su> element and 'like' the head of the <adp> element.
2.2
Coreferences and Anaphora
Each element may have an identifier as the value for the id attribute.  Coreferences, including identity anaphora, are annotated by the eq at- tribute, as follows: <np id="j0">John</np> beats <adp eq="j0">his</adp> dog. When the shared semantic content is not the referent but the type (kind, set, etc.)  of the referents, the eq ab attribute is used like the following: You bought a <np id="c1">car</np>. I bought <np eq.ab="c1">one</np>, too. A zero anaphora is encoded as follows: Tom visited <np id="m1">Mary</np>. He had <v iob="m1">brought</v> a present. iob="m1" means that the indirect object of brought is element whose id value is m1, that is, Mary. Other relations, such as sub and sup, can also be encoded. sub represents subset, part, or ele- ment. An example follows: She has <np id="b1">many books</np>. <namep sub="b1">‘‘Alice’s Adventures in Wonderland '</namep> is her favorite. sup is the inverse of sub, i.e., includer of any sort, which is superset as to subset, whole as to part, or set as to element. Syntactic structures and coreferences are es- sential for the summarization method described in section 3. Further details such as semantics, coordination, scoping, illocutionary act, and so on, are omitted here.
Multi-Document Summarization
3
3.1
Spreading activation
A set of GDA-tagged documents is regarded as a network in which nodes roughly correspond to GDA elements and links represent the syntac- tic and semantic relations among them.  This network is the tree of GDA elements plus cross- reference (via eq, eq.ab, sub, sup, and so on) links among them.  Cross-reference links may encompass different documents. Figure 2 shows a schematic, graphical representation of the net- work. Spreading activation is carried out in this network to assess the importance of the ele- ments. Spreading activation has been applied to summarization of single GDA-tagged docu- ments (Hasida et al., 1987; Nagao and Hasida, 1998). The main conjecture of the present study is that the merit of spreading activation in that it evaluates importances of semantic entities is greater in summarization of multiple docu- ments with multiple topics, because summariza- tion techniques using document structures do not apply here, as mentioned earlier. To fit the semantic interpretation, activations spread under the condition that coreferent ele- ments should have the same activation value. The algorithm³ is shown in Figure 3. Here the external input c(i) to node i represents a pri- ori importance of i, which is set on an empir- ical basis; for instance, an entity 4 referred to in the title of an article tend to be important, and thus c(i) should be relatively large for the corresponding node i . The weight w(i,j) of an- other kind of link from node i to node j may also be set empirically, but it is fixed to a uni- form value in the present work. Let E ( i ) be the equivalence class of node i, that is the set of nodes which are coreferent with i (linked with i via eq relationships). Condition should be satisfied in order for the spreading ac- tivation to converge. This condition is satisfied if we treat each equivalence class of nodes as a virtual node while setting the weights of other types of links to beニ, where D is the maximum degree of equivalence classes: where δ k j is 1 if there is a link between node k and node j , otherwise it is 0. The score score(i) of node i is calculated by summing the activation values of all the nodes under node i in the syntactic tree structure:
where α(i) is the activation value of node i and ch(i) is the set of child nodes of node i. ch(i) is empty if node i is a leaf node, or a word. This score is regarded as the importance of node i.
Extraction of important documents
3.2
and sentences
Extraction of important documents is simple once the scores of the nodes in the network are obtained. Sorting the document nodes accord- ing to their scores and extracting higher-ranked ones is sufficient for the purpose. Similar procedure is used to extract impor- tant sentences from an important document. Extracted sentences are pruned according to their syntactic structures.  Anaphoric expres- sions such as he or she are substituted by their antecedents if necessary. An experiment has been conducted to test the effectiveness of the proposed algorithm.  The ex- ample set contains fifty Japanese articles about the Peru hostage incident which continued over four months from December 1996 to April 1997. They include a lot of topics such as opening, negotiation, settlement, and so on. The GDA- tagging of these articles has involved automatic morphological analysis by JUMAN (Kurohashi and Nagao, 1998), automatic syntactic analysis by KNP (Kurohashi, 1998), and manual anno- tation encompassing morphology, syntax, coref- erence, and anaphora. The types of anaphora identified here are mainly plain coreference and zero anaphora. Cross-document coreferences among entities have been automatically identi- fied by exact string matching. 5 They contained errors but those errors were not corrected for the experiment.  Cross-document coreferences found were 'Peru'(49), 'Japan'(39), 'Peru Pres- ident' (15), 'members of Tupac Amaru'(9), ... and so on, where the numbers indicate the num- bers of documents which contain these expres- sions. The external inputs to nodes have been de- fined according to the corresponding nodes: c(i) = 10 if node i's antecedent dominates sen- tences (e.g., a node coreferring with a para- graph). This sets a preference for nodes which summarize preceding sentences. c(i) = 5 if node i is in the title of an article, because a title is usually important. Otherwise c(i) = 1. These crude parameter values have been set by the au- thors on the basis of the investigation of sum- marizations of various documents. Two important topics, the opening (first at- tack by Tupac Amaru) and the settlement (at- tack by the Peruvian government comman- dos), have been extracted from the four  highest ranked articles, even though temporal informa- tion has not been incorporated in the algorithm. The opening article is the first article of the sample document set. However, the settlement article is the sixth last one. So mere extraction of the last article would miss the settlement. The 25% summaries of the two articles made by extracting and pruning sentences are shown below together with their English translations:日本大使公邸に武装ゲリラ、バーティーに乱入
  銃撃、200人が人賞－－ペルー日本、ベルーの両国関係者多数が人質にとられた．武装グループは約20人で、うち複数が公即
に押し入った．現在、散発的に銃撃戦が展開されているという。 Armed guerrillas broke into a party at Japanese ambassador's residence.  Gunshots. 200 held in hostage. — Peru. Many people from Japanese and Peruvian sides were held in hostage. The armed group consists of about twenty people, several of which broke into the ambassador's residence. It is reported that there are intermittent shootings now. andベルー日本大使公邸占拠事件人賞全員解放権力基盤回復狙い－－フジモリ大統領フジモリ大統領は、強気の政治家であることを日本大使公邸占拠事件の解決でみせつけたジモリ大統領は公邸敷地に入った。公邸訪問は作戦の陣頭指揮を執っていることを印象付けたなぜ、フジモリ大統領は武力行使を選択したか。政治危機の根源にある公邸事件を、解決することで、政治主導権の回復を狙ったといえる: Japanese ambassador's residence possession incident in Peru. All hostages released. Aim at recovering his power basis — President Fu- jimori President Fujimori demonstrated himself as a strong politician by resolving the Japanese ambassador's residence possession incident. He entered the residence site. This visit to the residence impressed that he was leading the operation himself. Why did he choose to resort to arms? We can say that he aimed at recovering his political leadership by re- solving through military power the residence incident, which is at the root of the political crisis.
3.3
Entity-relation graph
The score score(i,j) of a relation between two entities፣and j , is defined by:
where S(E(i)) is the set of sentence nodes which dominate one of the nodes in E ( i ) and | E ( i ) | is the number of nodes in E (i). E(i), a(i), and score(s) have been defined in Section 3.1. |E(i)|a(i) is an analogy of 'tf × idf', which is a measure of term importance widely used in information retrieval. sufficiently large, score(i, j) If is then S(E(i)) ∩ S(E(j)) (the sentences containing both the entities) can constitute a CTOSS- document summary concerning i and j 6 . An entity-relation graph (E-R graph) is made of the relations highly ranked in terms of the score defined in (2).  Figure 4 shows the E-R graph made of the top eleven relations extracted from the articles about Peru hostage incident. The numbers near the lines represent the ranks of the relations. The top-ranked relation was the one be- tween Peru and Japanese ambassador's resi- dence. Three sentences extracted from the eight sentences which contained both of the entities were as follows. 7  They were listed in chrono- logical order which was identified by the date information in the articles.ベルーからの靴道によると、首都リマ市にある日本大使公邸が17日、左翼ゲリラとみられる武装グループに襲撃され、日本、ベルーの両国関係者多数が人質にとられた. According to reports from Peru, on the 17th the Japanese ambassador's residence in Lima, the capi- tal, was attacked by an armed groups, allegedly leftist guerrillas, and many people from both Japanese and Peruvian sides were held in hostage. 2.ベルーの日本大使公邸で発生した武装ゲリラによる人質事件で政府は18日、ベルー政府に対し人質の安全確保を要請するとともに、外務省の堀村隆彦中南米局審議官を同夜、現地に派遣したConcerning t he incident hostage at t he Japanese ambassador's residence caused by armed guerrilla, on the 18th the government requested the Peruvian government to assure the HORIUTI safety of the hostages, and sent Mr. Takahiko, coordinator, Division of Middle and South America. . . 3. 22日、ベルーの日本大使公邸への突入作戦を成功させたことで、フジモリ大統領の政治的威信は再び回復に向かうことになるだろう。 President Fujimori's political authority will recover because he succeeded in the operation to break into the Japanese ambassador's residence in Peru on the 22nd. These sentences, extracted from different ar- ticles, have been paraphrased on the basis of Since the name of the guerilla coreferences. group is not identified in the beginning of the incident, the expression ‘左翼ゲリラとみられる武装グループ’ (armed group which seems to be leftist guerrillas) is used in the first sentence This expression has been replaced with there. ‘左翼ゲリラ(トゥパク・アマル)’ (leftist guerrillas (Tupac Amaru)) by using cross-document coref- erences.  The equivalence of the first sentence and the first noun phrase of the second sentence, ‘ペルーの日本大使公邸で発生した武装ゲリラによる人質事件’ (the hostage incident caused by armed guerrillas at the Japanese ambassador's residence in Peru), were properly detected and was replaced by another expression because the equivalence of events across possibly different documents (McKeown et al., 1999; Barzilay et al., 1999) has been also detected by comparing predicate-argument structures of relevant sen- tences.  Date expressions such as '17日' (the 17th) have been augmented like '1996年12月17日' (Dec. 17, 1996). The resulting passages are below (underlines indicating paraphrases), together with their English translations (bold- face indicating paraphrases):
ある日本大使公邸が  1996年12月17日、左翼ゲリラ(トゥバク・アマル)こに慶撃され、日本、ペルーの両国関係者多数が人質にとられた。 According to news from Peru, on December 17, 1 996 the Japanese ambassador's residence in Lima, the capital, was attacked by leftist guerrillas (Tupac Amaru), and many people from both Japanese and Peruvian sides were held in hostage. 2その人質事件で政府は12月18日、ベルー政府に対し人質の安全確保を要請するとともに、外務省の堀村隆彦中南米局審議官を同夜、現地に派遣した。 Concerning the hostage incident, the govern- ment requested the Peruvian government to assure the hostages’safety on December the 18th, and sent Mr.  HORIUTI Takahiko, coordinator, Divi- sion of Middle and South America, Ministry of In- ternational Affairs, to Peru on that night. 3. 1997年4月22日、ベルーの日本大使公邸への突入作職を成功させたことで、フジモリ大統領の政治的威信
は再び回復に向かうことになるだろう. President Fujimori's political authority will recover because he succeeded in the operation to break into the Japanese ambassador's residence in Peru on April 22, 1997.
Discussion
4
4.1
Evaluation
Evaluation of multi-document summarization calls for far greater cost than that of single- document summarization. Testbeds for evalua- tion of multi-document summarization have not been developed yet. So the present evaluation is limited to the sample set of articles mentioned above, but the obtained results suggest general applicability of the proposed method and sup- ports the conjecture that spreading activation is effective for multi-document multi-topic sum- marization. As discussed in the previous section, the pro- posed method can extract important articles, that is, the opening and settlement articles, from fifty articles about Peru hostage incident. Also, an E-R graph consisting of important rela- tions among important entities, Peru, Japanese ambassadors’ residence, Tupac Amaru, and so on, has been successfully constructed on this basis. The above-mentioned method also uses cross-document coreferences for replacing ex¬ pressions with more concrete ones. All these are archived essentially by using in- formation in the GDA-tagging only, but not domain-dependent knowledge such as embed- ded in templates for information extraction. The proposed method is hence expected to de- tect important documents and sentences and create an appropriate E-R graph when applied to another set of documents about multiple top- ics.
4.2
Transformation
The process of summarization can be decom- posed into three stages (Sparck Jones, 1999):
GDA-tagged documents are regarded as source text representations. The method described above focuses on the transformation stage. Its multi-linguality comes from the multi-linguality of the stage.
Conclusion
5
Summarization of multiple documents about multiple topics has been discussed in this pa- The method proposed here uses spread- per. ing activation over documents syntactically and semantically annotated with GDA tags. It is capable of: ● extraction of the opening and settlement articles from fifty articles about a hostage incident, ● creation of an entity-relation graph of im- portant relations among important entities, ● extraction and pruning of important sen- tences, and ● substitution of expressions with more con- crete ones using cross-document corefer- ences. The method is essentially multilingual because it is based on GDA tags and the GDA tagset is designed to address multilingual coverage. Since this tagset can embed various linguistic information into documents, it could be a stan- dard format for the study of the transformation and/or generation stage of document summa¬ rization, among other natural language process- ing tasks.