DEIM Forum 2017 F3-4

Discovering Typical Histories of Entities
Yijun DUAN† , Adam JATOWT† , and Katsumi TANAKA††† Graduate School of Informatics, Kyoto University36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501 Japan††
E-mail: †{yijun,adam,tanaka}@dl.kuis.kyoto-u.ac.jp
Abstract Categorization is a common solution used for organizing entities like persons or places. For example,
there are over 1.13 million categories in Wikipedia which group various types of entities. What is however often
lacking is a general, shared information about the entities with a category, for example, information on typical
histories of the category entities. We propose in this paper a novel task of automatically creating summaries ofshared histories of entities within their categories (e.g., a typical history of a Japanese city). The output summaryis in the form of key representative events of entities together with the information on their typical dates. We introduce 4 methods for the aforementioned task and evaluate them on Wikipedia categories containing several types ofcities and persons. The summaries we generate can provide information on the common evolution of entities falling
into the same category as well as they can be compared with the summaries of related categories for generating
contrastive type of knowledge.
Key words entity summarization, digital history, typicality, Wikipedia

1. Introduction
Categorization is a common strategy applied for organizing

tial knowledge of history of much effort.
Straightforward approach to automatically extracting suchhistorical knowledge would be to formulate it as a stan-and understanding entities. Wikipedia, which is considereddard multi-document summarization task.

the most comprehensive encyclopedia these days, contains

ditional multi-document summarization techniques are notover 1.13 million categories [1]. Each category typically con-suited well for our scenario. The first problem is that thesists of multiple related members that share some common

input documents in multi-document summarization are as-traits (e.g., list of cities in Japan, list of American scientists

sumed to be similar to each other (e.g., news articles aboutborn in 19th century, etc.). To obtain a good understanding

the same event). This assumption is not guaranteed in theof a given category, one needs to know much about its mem-

entity history summarization as entity histories can be quitebers, which is definitely a difficult task especially for larger

different from each other. For example, while we expect tocategories. For example to understand about the category offind some common events and tendencies within a group ofJapanese cities a user would need to at least read about 500

Japanese cities, each individual city may have many uniqueof Japanese city instances.

events in its history. Another problem stems from the strong

However, tra-In this paper we focus in particular on historical knowl-

temporal character of documents in our task. Entity histo-

edge. Wikipedia abounds in knowledge about entity or con-ries (e.g., biographies) typically have a sequential charac-

cept histories. Nearly every article such as one about a per-ter and abound in multiple dates used to mark importantson or place contains history section. In fact, many enti-

events in time, delineate key periods, support explanation ofties cannot be properly understood without the knowledge

causal-effect relationships and, in general, to provide logicalof their histories. Same observation applies to categories ofprogression and coherent account of entity’s history.

these entities.

A uniting feature of traditional multi-document summa-

What is the history of Japanese cities? How is it different

rization techniques is an implicit assumption that the impor-from, e.g., the history of Chinese or UK cities? Which eventstance of a sentence can be estimated based on its similarity

frequently occurred during the life of French scientists? Howto other sentences within the input document set. For in-different was the life of a French scientist in 19th century

stance, in MEAD system [2] a sentence is judged importantfrom that of an American scientist? Questions of this typeif it is similar to the centroid sentence, or if it is similar to

are not easy to be answered as they usually require substan-

many important sentences as in LexRank method [4].

Considering the unique characteristics of our task, it is（ 3 ） The effectiveness of our methods is demonstrated inclear that the common approach of sentence selection used inexperiments on 7 Wikipedia category datasets about cities

multi-document summarization is not appropriate. To pro-and persons.

vide effective means for capturing common traits in entity
histories we make use of the following observations:

2. Related Work（ 1 ） Histories of many types of entities (e.g., countries,

Our research is related to the following types of tasks:

persons) can be often divided into particular eras. For ex-

Multi-Document Summarization.

Multi-document

ample, the history of Japan as well as the one of Japanesesummarization is the process of creating a summary thatcities covers several dynasties, while a person’s life can beretains the most important information from many docu-

divided into stages such as childhood, early education, earlyments. Summarization methods can be coarsely divided into

career, etc.

extractive summarization or abstractive summarization tech-（ 2 ） Documents describing histories of entities often con-niques.

tain underlying themes. These themes may be also corre-

based method MEAD [2] scores sentences based on sentence-

lated. For example, a biochemist’s biography is more likely

level and inter-sentence features including cluster centroid,

to be about genetics than about x-ray astronomy, and ge-

position, and TF-IDF, etc. Graph-based ranking methods,

netics’ theme may correlate strongly with genetics withinsuch as LexRank [4], have been developed to estimate sen-the dataset.

tence importance using random walks and eigenvector cen-（ 3 ） Themes as well as eras are usually not equally im-

trality. In order to remove redundancy in final summaries,

portant. An event contained in an important era and being

Maximal Marginal Relevance (MMR) technique [6] is com-part of important topics can be regarded more salient than

monly used. Wan et al. have improved the graph-ranking

one in less important era or belonging to trivial topics.

algorithm by utilizing sentence-to-sentence and sentence-to-（ 4 ） It is usual to consider some entities as better repre-

topic relationships [7]. In contrast, abstractive methods cre-sentatives of a category than others. This is known as theate summary containing words not explicitly present in the

As example of extractive methods, the centroid-

graded structure [5] of a category. An event belonging to aoriginal.

typical entity is then deemed to be more salient than ones ofcompression [9] and reformulation [10] may be needed.

a trivial entity.

In this process, information fusion [8], sentence

Timeline Summarization. Timeline Summarization de-

To reflect the above observations we rely on graph analy-

fined as the summarization of sequences of documents (typi-sis. Graph based summarization approaches have been suc-cally news articles about the same event), have been actively

cessfully used for multi-document summarization. In thisstudied in the recent years. In [11], Yan et al. proposed

work, we adapt Markov Random Walk (MRW) [3] model tothe evolutionary timeline summarization (ETS) to computeour scenarios. To address the limitations of traditional tech-evolution timelines consisting of a series of time-stamped

niques we propose one model for exemplar-based summary

summaries. David et al. presented a method for discov-

generation and another model for prototype-based summary

ering biographical structure based on a probabilistic latent

generation which are based on MRW and incorporate addi-

variable model [12]. His method summarizes timestamped

tional information about documents, eras, topics and topic

biographies to a set of event classes along with the typicalcorrelation. Our experiments are performed on 7 Wikipedia

times in a person’s life when those events occur.

category datasets containing 3 cities datasets and 4 persons

The above mentioned methods can not be simply applied

datasets with the results demonstrating high effectivenessto our task. While each document is timestamped in theof our methods when compared to common multi-document

timeline summarization task, in the task of category summa-

summarization techniques.

rization, each document spans over a certain range of time.

To sum up, we make the following contributions in thisDue to this the timeline summarization techniques are un-paper:

able to estimate the representativeness of a document and（ 1 ） We introduce a new research problem of character-correlation between sentences, which are important factors

izing entity categories by generating their typical histories.

considered in our task.

（ 2 ） We propose 2 different models to discover typical

histories of entities utilizing information about sentences,

3. Problem Statement

eras, topics and topic correlation between sentences. All our

3. 1 Input

models work in an unsupervised way, which is important con-

The input to the summarization task are document con-sidering the lack of manually created summaries for most oftaining histories of entities within the same category. Eachthe categories.

history-related document spans over a certain range of timeand each sentence refers to some historical event. The dates

stemming and retaining the most frequent 5,000 unigramsof events can be either explicitly mentioned in the sentence

and bigrams. In the recent years, word2vec [13] was widelyor can be estimated based on surrounding sentences.

utilized for automatically learning the meaning behind the

We note that naturally, sometimes categories can consist

words and the relationships between the words based on neu-of entities with very diverse histories. The summarization

ral networks. We use the distributed vector representation

task becomes then more difficult in those cases.

to represent terms and events. The vector representation of

3. 2 Research Problem

an event is a weighted combination of vectors of terms con-

Given a set of history-related documents [d1 , d2 , ..., dn ]tained in the normalized sentence. The corresponding weight

each about particular entity within the same category and a

for a term is its TF-IDF value calculated from the originaltime window [tbegin , tend ], the task is to select k most typ-corpus.

ical historical events [e1 , e2 , ..., ek ] to form a summarized
timeline reflecting typical history of the entities. Each eventin the summary is represented by i words [w1 , w2 , ..., wi ].
The events selected for inclusion into the summary shouldbe:

5. Prototype Summary Generation
5. 1 Eras Detection
Given a sequence of atomic time units ξ = (t1 , t2 , ..., tn ),the task is to select a proper segmentation Θ containing（ 1 ） typical: we want to retain typical information ofm eras of the entire time span [t1 , tn ], where each era Ti

the category history;

is expressed by two time points representing its beginning（ 2 ） diverse: events contained in the summary shoulddate τbi and the ending date τbi of the era. Formally, letbe both diverse in their content and in terms of its occurringΘ = (T1 , T2 , ..., Tm ), and Ti = [τbi , τei |τbi ∈ ξ, τei ∈ ξ]. In ordertime to cover more content and time span;to perform era detection we state two hypotheses:（ 3 ） comprehensible: events contained in the sum-mary should be understandable to users.

Hypothesis 1 A statistically significant increase or de-

3. 3 Types of Output Summary

crease in the number of events in two adjacent time units

Cognitive science studies suggest two modes in which peo-can be an indicator of the emergence of a new era.

ple understand categories: prototype view [18] and exemplar

Hypothesis 2 Events occurring in the same era tend toview [19]. The first one suggests that a category be repre-

be more similar to each other than events occurring in othersented by a constructed prototype (sometimes called cen-eras.

troid), such that entities closer to the prototype are considered to be better examples of the associated category. The
exemplar view is an alternative to the prototype view that

The above hypotheses are the reason for the two step process of era detection. We discuss both the steps below:

proposes using real entities as exemplars instead of abstract

Chi-Square Test. The initial set of unit segments of the

prototypes that might actually not exist. Based on this di-

category history is ξ = (t1 , t2 , ..., tn ), where each time unit

vision, we propose two types of summaries approaches:ti represents a year. A chi-square test of independence is a

Prototype-based summarization. In the prototype-significance test widely used to determine a significant as-based summarization, events may come from the history ofsociation between two categorical variables. We test for thearbitrary entity within the category. The prototype-based

independence of adjacent time units, and the lack of indepen-summary represents the category by constructing an imagi-

dence allows the adjacent time units to be combined. Morenary prototype.

concretely, the chi-square test is used to determine whether
In the exemplar-

two neighboring time units exhibit a statistically significant

based summarization, events are drawn from a relatively

association based on the number of contained events. The

small set of typical representatives among all entities. The

value for each initial time unit is calculated by the following

size of the set depends on the size of summary.

equation:

Exemplar-based summarization.

The

exemplar-based summary uses a few typical representative
instances to describe the whole category.

4. Event Representation

χ2 =X (O − E)2(1)
E
The observed value O is the number of events in an initial
segment, while the expected value E is found by calculat-

A historical event is represented by a sentence and is associated with a date of its occurrence. As not all words of theoriginal sentence are meaningful, each sentence is first normalized by pre-processing steps such as removing stopwords,

ing the average of O in the two adjacent time units. The
default significance level is set to 0.05, thus a statisticallysignificant change is defined where the χ2 value exceeds thecritical cut-off of 3.84.

conduct topic detection for better representing event impor=tance. Note that the topics are usually not equally impor-(µ1 , µ2 , ..., µk ), where µi = [ηbi , ηei |ηbi ∈ ξ, ηei ∈ ξ], is created

The second set of segments ςtant. Events referring to important topics will be deemed

after some of initial time units are combined. We next use

more salient than events referring to trivial ones.

Optimization.

an optimization formula to determine the final eras based

Clustering algorithms like K-means are popular techniques

Given the present number of final pe-

to detect topics. However, these are not appropriate as eachriods, m, every possible combination Θ of segments fromevent is expected to belong to only one topic. Latent Dirich-the second set will be explored iteratively.

on hypothesis 2.

Formally, letlet Allocation (LDA) allows for soft topic to event associa-

Θ = (T1 , T2 , ..., Tm ), and Ti = [τbi , τei |τbi ∈ ς, τei ∈ ς]. In

tion, yet, LDA does not explicitly computes topic-topic asso-

particular, we prefer the combination, in which the eras tociation which could constitute another useful signal for topic

be selected are characterized by high intra-similarity, low

importance estimation.

inter-similarity, and, in addition, they have high abundancy

We construct topics with Correlated Topic Model (CTM)

defined as the number of instances having their events in a[16], which captures both topic-event relations and topic-

given era.

topic relations. Given a set of documents D=[d1 , d2 , ..., dN ]Θ ≡argmax[ω1and its vocabulary W =[w1 , w2 , ..., wM ], CTM assumes amX

set of latent topics Z=[z1 , z2 , ..., zK ] (K is pre-specified).

IntraSimilarity(Ti )Each document dj is viewed as arising from the mixture of

i=1

− ω2

m−1
X

InterSimilarity(Ti , Ti+1 )(2)

topics in Z, each of which is a distribution over the vocabulary W . In addition, the covariance structure among topics

i=1

Z (which is a K-dimensional covariance matrix) is estimated+ (1 − ω1 − ω2 )Abundancy(Ti )]Here, the intra-similarity measures the similarity between
events within a era:

via adopting the logistic normal distribution to model thelatent topic proportions of a document.
Given CTM, we are able to obtain the per-document

X X Simcosine (ei , ej )IntraSimilarity(Ti ) =|Ti |2e ∈T e ∈Tiij

topic distributions P (Z|dj ), the per-topic word distributions(3)

P (W |zk ) and the topic-topic correlations Corr(zi ,zj ). We
then incorporate this information to event importance cal-i

The inter-similarity measures the similarity between events

culation, as detailed next.
5. 3 Prototype-based MRWof neighboring eras:

The Markov Random Walk Model (MRW) has been sucInterSimilarity(Ti , Ti+1 ) =X

X

ei ∈Ti ej ∈Ti+1

Simcosine (ei , ej )|Ti | · |Ti+1 |(4)

The abundancy of a era indicates how many category instances have at least one of their events located in this era.
Let di be the instance entity that an event ei is located in,and D be the set of documents in D. The abundancy is

cessfully exploited in multi-document summarization. MRW
is a way of calculating the importance of a vertex withina graph based on global information recursively drawn fromthe entire graph. As discussed previously, the underlying correlated topic themes as well as detected eras are not equallyimportant. An event contained in an important era and being part of important topics is deemed more salient than one
in less important era or belonging to trivial topics. Thus informed as follows:order to calculate event importance with the prototype-view
Abundancy(Ti ) = |D|(5)

based MRW, we state four hypotheses for determining important events:

Finally, the era combination that has the highest score by
applying Eq. (2) is adopted.（ 注 1）

Hypothesis 3 An important event is similar to the im-

5. 2 Topic Detection

portant era that the event is contained in.

Different entities may share similar historical events which
are not confined to the same eras.

For instance, many

Japanese cities once have been hit by earthquakes in different years. Thus, in addition to detecting eras we also

Hypothesis 4 An important event is similar to important
topics.
Hypothesis 5 An important event is similar to other important events.
Hypothesis 6 An important event is correlated to other（ 注 1）： We experimentally set weights for ω1 , ω2 and ω3 in Eq. (2) tobe 0.4, 0.4 and 0.2, respectively.

important events.

Formally, let G = (Vs , Vt , Vz , Qss , Qst , Qsz ) be agraph with three types of sets of vertices {Vs , Vt , Vz } andthree types of edge sets {Qss , Qst , Qsz }. Let Vs =V ={vi },Corr(vi , vj ) =X X Sim(vi , zi ) · Sim(vj , zj ) · Corr(zi , zj )|Z|2

zi ∈Z zj ∈Z

Vt =T ={tj }, Vz =Z={zk } denote the sets of events, de-(13)tected eras and that of detected topics, respectively. Let

The transition probability pij from vi to vj is then com-

Qss = {qij |vi , vj ∈ Vs }, Qst = {qij |vi ∈ Vs , tj ∈ Vt andputed by normalizing the corresponding affinity weight to

tj = era(vi )}, Qst = {qik |vi ∈ Vs , zk ∈ Vz } represent theensure convergence:

sets of links between events, links between an event and anera, links between an event and a topic, respectively.
Graph G contains two layers. The upper layer consists of

pij = Pwij
vk ∈Vs wik(14)

era vertices Vt and topic vertices Vz , while the lower layer

Based on the transition probability, the importance score

represents event vertices Vs . Below we are going to explain

Score(vi ) for an event vi can be deduced from all other events

the way to assign initial scores to vertices and the way toin a way similar to PageRank algorithm by iteratively com-compute edge weights.

puting the following formula until convergence:First we compute importance score of an era ti denoted by
I(ti ) as follows:

X

Score(vi ) = (1 − d) + d ·pji · Score(vj ) (15)vj ∈Vs ,vj =v| i

I(ti ) = Sim(ti , D)Sim(ti , D) =(6)

X X Simcosine (vi , vj )|ti | · |D|v ∈t v ∈Diicomputation ends when the difference between the scores(7)jan importance of a topic zi :I(zi ) =computed at two successive iterations for any events is lessthan 0.0001. α in Eq. (12) is empirically set to be 0.6.

where D is the document set. On the other hand, I(zi ) isP

where d is a damping factor set by default to 0.85. The

5. 4 Exemplar-based MRW
In this method we decide the importance of entities usingd∈D P (zi |d)|D|

MRW with the following hypothesis:(8)

Sim(vi , tj ) denotes the similarity between an event vi andthe era tj that vi is contained in, it is denoted as follows:1
Sim(vi , tj ) =· Simcosine (vi , vj |vj ∈ tj )|tj |Hypothesis 11 An entity is important if it shares similar
history to other important entities.
Formally, let G = (V , Q) be an undirected graph, where(9)

V ={vi } and Q = qij |vi , vj ∈ V } denote the sets of entities
and the links between entities respectively.

Sim(vi , zk ) denotes the similarity between an event vi anda topic zk , it is denoted as follows:
Sim(vi , zk ) =PConsidering the above hypothesis regarding entity importance, the affinity weight wij of edge qij between the two en-w∈vi P (w|zk )|vi |tities vi and vj is computed using the similarity Sim(vi , vj )(10)

Let Score(vi ) be the score of a vertex vi . We then compute

between the histories of vi and vj .
Each entity history is a sequence of events.

Since co-sine similarity is not a proper similarity measure for tem-0

the initial score Score (vi ) of vertices as follows:

poral sequences, we propose to use Dynamic Time WarpScore0 (vi ) = I(ti ) · Sim(vi , ti ) ·X

ing (DTW) for measuring similarity between two entities’I(zk ) · Sim(vi , zk )

zk ∈Z

(11)
Each edge qij in Qss is associated with an affinity weightwij between events vi and vj . Considering hypothesis 5 andhypothesis 6, the weight is computed using both the similarity Sim(vi , vj ) and correlation Corr(vi , vj ) between the two
events:histories. DTW calculates an optimal match between two
sequences. Hence, entities’ histories can be ”warped” nonlinearly in the time dimension so as their similar events arealigned. The advantage of DTW is that the order of events
is considered when computing the similarity. Thus, histories
containing identical events yet, positioned in different order
are not judged to be identical.
wij = SimDT W (vi , vj )wij = α · Simcosine (vi , vj ) + (1 − α) · Corr(vi , vj ) (12)=1
DT W (vi , vj ) + 1(16)

The transition probability pij from vi to vj is computed

words referring to the same event.

using Eq. (14), and the importance score Score(vi ) for an

More concretely, for each sentence indicating an event in

event vi is deduced by iteratively computing Eq. (15) until

the summary, we seek for m most similar sentences in theconvergence.

corpus and build up a cluster of m + 1 sentences. Sentences

After entity importance scores are calculated, top m im-within each cluster are semantically similar and each cluster

portant entities are selected. Let the expected summary size

represents an event. Then we run Term Frequency-Inverse

be k events and the number of events in history of the ith

Cluster Frequency (TF-ICF) on clusters and extract a set of

ranked entity vi be size(vi ). m is then decided as follows:meaningful words for each cluster. Those sets of words are

m−1X

size(vi ) < k,

i=1

m
X

used as final representation of events in summarized timeline.
size(vi ) > k(17)

We set the number of events used for building the event clusters to be 10.

i=1

We next merge histories of the selected m entities and pickup the top k important events from the merged history using
MRW-based ranking method called LexRank [4].

|C|
ni,j
· log
tf icfi,j = P|c:c ∋ ti |
n
k k,j

(19)

7. Experiments

6. Post-Processing

In this section, we introduce the experiments conducted to
6. 1 Redundancy Removal
After historical events of a certain category are ranked byimportance, we apply a modified version of MMR (Maximal Marginal Relevance) [6] denoted as T-MMR (TemporalMaximal Marginal Relevance) to minimize redundancy. TMMR tries to avoid extracting similar (both semanticallysimilar and temporally close) events in a summary by considering penalty based on the similarity between a newly extracted event and the already extracted events. T-MMR allows extracting the events which have high importance scoreand are not similar to the already extracted ones.

evaluate the effectiveness of our proposed methods.
7. 1 Datasets
In this study, we validate our methods on entities separated by both time and space dimensions. In particular,
we perform experiments on 7 Wikipedia categories including
3 city categories and 4 person categories. The city categories are Japanese cities, Chinese cities and English cities(denoted by C1 , C2 , C3 respectively), while for the person
categories we have selected American scientists, French scientists, Japanese Prime Ministers till 1945 (i.e., the end ofWW2) and Japanese Prime Ministers after WW2 (denotedby P1 , P2 , P3 , P4 , respectively). Note that our methods are

T-MMR ≡argmax[αscore(si ) − βmaxSimcosine (si , sj )− (1 − α − β)min

not bound to Wikipedia categories as any listing of entities
can form an input, provided the historical data about each1]|ti − tj | + 1

instance is made available. In this work, we use Wikipedia(18)

Here, si denotes a sentence in the set of candidate sentences which have not been extracted, while sj represents a
sentence in the set of already extracted sentences. The values of α and β are experimentally assigned to be 0.5 and 0.4,
respectively.
6. 2 Generalization
Each event in the summarized timeline should be represented by a set of meaningful words. However, our models
only produce summary in which each event is in the format
of a certain sentence from the history of one entity. The sentence representation may in addition contain too specific details which are true only for the city from which the sentence
has been extracted. For example, many cities in Japan havesuffered from earthquakes, and the sentence ”earthquake hitcity” would be a good general description instead of longer
sentences giving additionally detailed descriptions of particular damages in particular cities. Thus we choose to generalize
those sentences in summary to a set of more representative

categories as a convenient data source.
For city categories, each city history is extracted from the”History” section in the corresponding Wikipedia article. To
retain historical events, we then extract all sentences in whicha single date is mentioned. As further preprocessing, we reduce inflected words to their word stem and retain only theterms in each sentence that are among the most frequent
5,000 unigrams, excluding stopwords and all numbers. Eachhistorical event is then represented the the bag of unigrams
extracted from a sentence along with a corresponding date.
For person categories, we utilize a dataset of 242,970 biographies publicly released by Bamman et al. [12]. Each biography consists of several life events represented by bag ofunigrams with a timestamp in a way similar to ours. Contrastingly, the timestamp is measured as the difference between the observed date in the event and the date of birthof the entity, namely age. In other words, the timestamp ofan event can be either absolute time or relative time. Both

types make sense in different cases.

Saliency. It measures how sound and important the ex-Some basic statistics about our datasets is shown as follows.

tracted events are.
Comprehensibility. It measures how easily the bag of

Table 1 Summary of datasets (The time range of datasets
C1 , C2 , C3 are based on absolute time, while of datasetswords representing the event can be associated with real historical events.

P1 , P2 , P3 , P4 are based on relative time.)# Entity Time Range

Besides, each summary is graded in terms of:DatasetCategory

C1

Japanese Cities532

40 - 2016

C2

Chinese Cities357

12 - 2016

Diversity. It measures how varying or diverse the events

C3

UK Cities

68

1 - 2016

in the summary are, both semantically diverse and tempo-

P1

American Scientists

141

0 - 103

rally diverse should be taken into consideration.

P2

French Scientists

41

0 - 101

P3

Japanese PMs (pre WW2)

32

0 - 98P4Japanese PMs (post WW2)30

0 - 93Coverage. It measures the extent to which important
events in category history are included in summary.
Interestingness. It measures how interesting the results
are and, implicitly, it represents the degree to which the ex-

7. 2 Baselines

tracted events were novel to annotators.

We describe 2 baselines as follows:(1) LexRank + MMR(LexRank) LexRank methods

We have 4 methods to be tested (2 proposed methods andhas been widely adopted in multi-document summarization

2 baseline methods). The annotators were asked to evaluate

task. It constructs a sentence connectivity matrix and com-the 28 different summary (4 methods, each with 7 datasets).

putes sentence importance based on the algorithm similar to

We have 5 annotators in total (4 males, 1 female) who have

PageRank. We also use MMR to remove redundancy. Fi-

significant interest in history. Each summary is ensured to benally, selected events are generalized from sentences to theevaluated by 3 annotators. During the assessment, the an-sets of words.

notators were allowed to utilize any external resources, such(2) K-Means Clustering(K-Means) K-Means cluster-as Wikipedia, Web search engines, books, etc. All of theing is a popular method for cluster analysis in data mining.

scores were given in the range from 1 to 5 (1: not at all, 2:

It partitions all events into k clusters in which each event

rather not, 3: so so, 4: rather yes, 5: definitely yes). Afterbelongs to the cluster with the nearest mean (given k as theannotation scores have been completed we average saliency

size of summary). Then, within each cluster, we experimen-

and comprehensibility scores per each summary. Lastly, wetally pick up 10 sentences closest to the cluster centroid toaverage individual scores given by annotators to obtain final

build up an event cluster. Then TF-ICF is applied to extractscores per each summary.

meaningful words for each event cluster.

7. 5 Evaluation Results

7. 3 Experiment Settings

Below we discuss the key experimental results.

We set the parameters as follows:

Average results. Fig. 1 shows the average scores of sum-(1) size of summary: we experimentally set the summary size

maries generated from all the datasets in 5 criteria by all theof city datasets to be 20 events, and of person datasets to becompared methods. We first note that our proposed methods

10 events considering the size of categories.

outperform the baselines based on almost all criteria. On av-(2) parameters in the prototype-based methods: we empiri-erage, our proposed methods outperform LexRank by 12.0%

cally let the number of eras for the city dataset to be 10, andand K-Means by 15.8% across all the metrics. Especially,

for the person datasets to be 5 considering the length of thein terms of saliency, the proposed methods are better than

span of category history. In addition, the number of topics

LexRank by 24.1% and than K-Means by 23.4%. Thisare experimentally set to be identical to the size of summary.

proves that incorporating importance of eras, topics and entities all help to improve the saliency of events contained in

7. 4 Evaluation Criteria
Manually creating summaries of typical histories of certain

summary.
7. 6 Additional Observations

categories is a difficult task. Thus to text our methods we

we have some additional observations as follows.

conduct a qualitative evaluation based on the following five

Diversity. We find that the proposed methods work bet-

criteria.
Each event in the summary is graded in terms of:ter on the city datasets than on the person datasets. It may
be because city histories have longer time span hence theirevents may be characterized by higher diversity.

Average
4

3

2

1

0

Saliency
P-MRW

Comprehensibility
E-MRW

Diversity

LexRank (baseline 1)

Coverage

Interestingness

K-Means (baseline 2)

Figure 1 Average Results of All Datasets.

Coverage. The prototype-based method achieve muchbetter performance with regards to the coverage than the
exemplar-based method.

It may be because events in

exemplar-view based summaries are extracted from a small
set of typical representatives, which may lose some important
information.

8. Conclusions
It is natural for humans to categorize entities into meaningful groups based on their common traits. One way tobetter understand categories is by learning histories of theirmembers. In this paper we have introduced a novel type ofsummarization task consisting in generating gists of multiple
entity histories. We then proposed 4 methods for this task
which utilize diverse kinds of information such as information about documents, eras, topics and correlation between
events and incorporate them into graph-ranking models. The
output summary is in the form of key representative events
represented by sets of meaningful words and approximate
event dates. The effectiveness of our models has been demonstrated by experiments on 7 Wikipedia category datasets.
In the future, we plan to incorporate abstractive summarization strategies for improving the readability of the generated summaries. The next step is to improve and extend
methods for extracting and representing temporal information from input documents using techniques similar to theone by [17]. We will also investigate differences of entity types
in terms of their impact on the summary quality.
References[1] Bairi, R. B., Carman, M., & Ramakrishnan, G. (2015,
April). On the Evolution of Wikipedia: Dynamics of Categories and Articles. In Ninth International AAAI Conference on Web and Social Media.
[2] Radev, D. R., Jing, H., Sty, M., & Tam, D. (2004).
Centroid-based summarization of multiple documents. Information Processing & Management, 40(6), 919-938.
[3] Lovsz, L. (1993). Random walks on graphs. Combinatorics,
Paul erdos is eighty, 2, 1-46.
[4] Erkan, Gnes, and Dragomir R. Radev. ”LexRank: Graphbased lexical centrality as salience in text summarization.”
Journal of Artificial Intelligence Research 22 (2004): 457479.

[5] E. Rosch. On the internal structure of perceptual and semantic categories. Cognitive Development and Acquisitionof Language, pages 111144, 1973.
[6] Carbonell, Jaime, and Jade Goldstein. ”The use of MMR,
diversity-based reranking for reordering documents and producing summaries.” Proceedings of the 21st annual international ACM SIGIR conference on Research and development
in information retrieval. ACM, 1998.
[7] Wan, Xiaojun, and Jianwu Yang. ”Multi-document summarization using cluster-based link analysis.” Proceedingsof the 31st annual international ACM SIGIR conference on
Research and development in information retrieval. ACM,
2008.
[8] Barzilay, Regina, Kathleen R. McKeown, and Michael
Elhadad. ”Information fusion in the context of multidocument summarization.” Proceedings of the 37th annual
meeting of the Association for Computational Linguistics on
Computational Linguistics. Association for Computational
Linguistics, 1999.
[9] Knight, Kevin, and Daniel Marcu. ”Summarization beyond
sentence extraction: A probabilistic approach to sentencecompression.” Artificial Intelligence 139.1 (2002): 91-107.
[10] McKeown, Kathleen, et al. ”Towards multidocument summarization by reformulation: Progress and prospects.”
AAAI/IAAI. 1999.
[11] Yan, Rui, et al. ”Evolutionary timeline summarization:a balanced optimization framework via iterative substitution.” Proceedings of the 34th international ACM SIGIR
conference on Research and development in Information Retrieval. ACM, 2011.
[12] Bamman, David, and Noah A. Smith. ”Unsupervised discovery of biographical structure from text.” Transactionsof the Association for Computational Linguistics 2 (2014):
363-376.
[13] Mikolov, Tomas, et al. ”Efficient estimation of word representations in vector space.” arXiv preprint arXiv:1301.3781(2013).
[14] Berndt, Donald J., and James Clifford. ”Using Dynamic
Time Warping to Find Patterns in Time Series.” KDD workshop. Vol. 10. No. 16. 1994.
[15] Blei, David M., Andrew Y. Ng, and Michael I. Jordan. ”Latent dirichlet allocation.” Journal of machine Learning research 3.Jan (2003): 993-1022.
[16] Blei, David, and John Lafferty. ”Correlated topic models.” Advances in neural information processing systems 18(2006): 147.
[17] Jatowt, A., Au Yeung, C. M., & Tanaka, K. (2013, October). Estimating document focus time. In Proceedings of the
22nd ACM international conference on Conference on information & knowledge management (pp. 2273-2278). ACM.
[18] E. Rosch. Cognitive representations of semantic categories.
Journal of Experimental Psychology: General, 104:192233,
1975.
[19] L. R. Brooks. Nonanalytic concept formation and memory
for instances. In Cognition and categorization, 1973. Hillsdale.