Unsupervised Storyline Extraction from News Articles

1 Introduction

With the rapid development of online news media sites, tremendous news reports are generated each day. Moreover, newsworthy events are widely scattered not only on traditional news media but also on social media. It is crucial to develop an automated tool which can provide a temporal summary of related events and their evolutions from web texts. Therefore, storyline extraction, aiming at summarising the development of certain related events, has been extensively studied in recent years.

Considering each storyline as a cluster, storyline extraction can be treated as an evolutionary clustering problem, where documents are ordered as a stream and clustered depending on both similarity in context and closeness in time. Several methods have been proposed, differing in the ways of calculating context similarity and time closeness [Yan et al., 2011; Huang and Huang, 2013; Du et al., 2015]. However, most of the previous approaches do not represent storylines in the form of structured representations. Moreover, in the approaches based on Bayesian nonparametric models [Li and Cardie, 2014; Diao and Jiang, 2014], events are extracted independently from different time periods and are subsequently combined as storylines in a post-processing step. On the contrary, we propose a model which is able to capture the dynamic aspect of storylines from text stream data. In specific, we model each storyline as a joint distribution over some locations l, organizations o, persons p, keywords w and a set of topics z. Each word in a document is discriminated as storyline keyword, background word and global topic word to learn storylines' representations more accurately. Moreover, storyline-keyword, storyline-location, storyline-person and storyline-organization probabilities at epoch t are dependent on their corresponding probabilities in the last M epochs in order to capture the dynamic evolution of different events in the same storyline over time. We further combine this model with the Chinese restaurant process so that the number of storylines in each epoch can be determined automatically without human intervention. Moreover, per-token Metropolis-Hastings sampler based on lightLDA [Yuan et al., 2015] is employed to reduce sampling complexity.

The main contributions of the paper are summarized below:

• ÷ We propose a novel non-parametric generative model to extract structured representations and evolution patterns of storylines simultaneously. The model is combined with the Chinese restaurant process to automatically determine the number of storylines in each epoch without human intervention.
• ÷ Per-token Metropolis-Hastings sampler based on lightLDA is employed to reduce sampling complexity.
• ÷ The proposed approach has been evaluated on three datasets and a significant improvement on F-measure compared to the state-of-the-art approaches is observed.

2 RelatedWork

There have been many studies on storyline extraction from text including news articles. For example, to generate storyline from massive texts on the Internet, [Yan et al., 2011] calculated correlations of individual summaries on each date generated using a text summarization algorithm. [Kawamae, 2011] proposed a trend analysis model by using the difference between temporal words and other words in each document to detect topic evolution over time. [Lin et al., 2012] extracted a storyline by first obtaining relevant tweets and then generating storylines via graph optimization. In [Binh Tran et al., 2013], relevant time points and contents to be included in the storyline summary were chosen based on a linear regression model. [Radinsky and Horvitz, 2013] constructed storylines based on text clustering and entity entropy. [Huang and Huang, 2013] developed a mixture event aspect model to distinguish local and global aspects of events described in sentences and utilized an optimization method to generate storylines. [Huang et al., 2015] first extracted topics from a short text corpus based on word co-occurrence patterns, and then developed an event evolution mining algorithm to discover hot events and their evolutions. [Vossen et al., 2015] proposed a model based on the narratology framework by constructing storylines from events through bridging relations. [Yu et al., 2015] proposed a context-dependent news article storyline detection based on dense subgraph learning, which adaptively learns a set of cross-article link patterns.

With the popularity of using topic models for document clustering [Blei et al., 2003], Bayesian nonparametric models, such as Dirichlet process (DP) [Li and Cardie, 2014] and recurrent Chinese Restaurant process (RCRP) [Diao and Jiang, 2014], attract many research attentions for tackling the storyline extraction task. [Li and Cardie, 2014] proposed a non-parametric multi-level DP model to reconstruct users' life history based on their Twitter streams. [Wang, 2013] proposed a time-dependent hierarchical DP for storyline generation. It can detect different levels of topic information across corpus and the structure is further used for sentence selection. [Zhang et al., 2010] proposed an evolutionary hierarchical DPs to discover interesting cluster evolution patterns from texts by adding time dependencies to the adjacent epochs. In [Li and Li, 2013], an evolutionary hierarchical DP was proposed to capture the topic evolution pattern in storyline summarization. Instead of DP, [Ahmed et al., 2011] proposed a dynamic nonparametric model based on RCRP to group temporally and topically related news articles into same storylines in order to reveal the temporal evolution of events. Following this way, [Tang and Yang, 2012] developed a topic user trend model, which incorporates user interests into the generative process of web contents. [Diao and Jiang, 2014] proposed a probabilistic model to identify both events and topics simultaneously from Twitter by applying a durationbased probability discount to RCRP to capture the character of events on Twitter. [Du et al., 2015] combined Dirichlet processes and Hawkes processes to deal with asynchronous streaming data in an online manner. [Blei and Frazier, 2011] developed the distance dependent Chinese Restaurant process (CRP) to model dependencies between data in infinite clustering models including dependencies across time or space. Following this way, [Tang et al., 2015] proposed a hybrid distance dependent CRP based hierarchical topic model and utilized it as prior for news article clustering.

[Zhou et al., 2015] proposed an unsupervised Bayesian model for storyline extraction. They assumed each document belongs to one storyline s, which is modelled as a joint distribution over some named entities e and a set of topics z. The weighted sum of the storyline distribution of previous epochs is used to set the prior of the storyline distribution in the current epoch. However, the model requires the number of storylines to be preset. In reality, it is impossible to know this information in advance. Furthermore, their model did not distinguish between the global topic words shared by the whole corpus and storyline-specific keywords.

3 Methodology

To model the generation of a storyline in consecutive time periods from a stream of documents, we propose an unsupervised latent variable model, called dynamic storyline extraction Model (DSEM). The graphical model of DSEM is shown in Figure 1. The model has such features: (1) for a certain period of time, we assume that each document could belong to one storyline s and each storyline s is modelled as a joint distribution over some locations l, organizations o, persons p, keywords w and a set of topics z; (2) the story described in the document d at current time t is drawn either from an existing storyline or a new storyline at current time t. The latent random variable xtd acts as a storyline-category switch; (3) to represent the dependency of different stories in the same storyline, storyline-word, storyline-location, storylineperson, storyline-organization probabilities at time t are dependent on the previous corresponding distributions in the last M epochs; (4) each word wd↪n in the document d is drawn either from the storyline key word distribution, or the background word distribution, or the global-topic word distribution shared by the corpus. A switch variable yd↪n is used to control word generation process; (5) the number of storylines is determined automatically by applying CRP at current t. CRP is a non-parametric model which can be used for clustering. To model streaming data, CRP models a restaurant with infinite number of tables and each with infinite capacity. When the i - th customer comes in, she can choose an already occupied table with probability n(i) k ◁(n - 1 + ↵) or a new table with probability ↵◁(n - 1 + ↵), where n(i) k is the number of customers sitting at table k and n is the total number of customers in this restaurant.

The generative process of DSEM is shown as below. For each time period t from 1 to T :

• ÷ Draw a distribution over storyline switch χt ⇠ Beta(⇣ t ), draw a distribution over word switch χtw ⇠ Dirichlet(⇣ tw ).
• ÷ Draw a distribution over prior storylines ⇡ts ⇠ Dirichlet(↵ts ), draw a distribution over global topics ✓t ⇠ Dirichlet(βt ).
• ÷ For each topic k 2 ¶1▷▷▷K♦, draw a word distribution 'tz ⇠ Dirichlet(γ tz ), For background words, draw a word distribution 'tbg ⇠ Dirichlet(γ t bg ).
• ÷ For each existing storyline s 2 ¶1▷▷St♦:
• For storyline keyword, draw a word distribution 'ts ⇠ Dirichlet(γ ts ).
• Draw a distribution over location φts ⇠ Dirichlet("ts ), person !ts ⇠ Dirichlet(✏ts ), organization ts ⇠ Dirichlet(⌘ts ),
• ÷ For each document d 2 ¶1▷▷Dt♦:
• If xtd = 0, choose a new storyline indicator std from CRP; draw Multinomial distribution φ0s ↪ !0 s ↪ '0s respectively for this new storyline,
• Choose xtd ⇠ Multinomial(χt ),
• If xtd = 1, choose a storyline indicator std from Multinomial(⇡ts ),
• For each location l 2 ¶1▷▷Ld♦, Choose a location l ⇠ Multinomial(φts ),
• For each organization o 2 ¶1▷▷Od♦, Choose an organization o ⇠Multinomial( ts ),
• For each person p 2 ¶1▷▷Pd♦, Choose a person p ⇠ Multinomial(!ts ),
• For other word positions n 2 ¶1▷▷Nd♦:
• ⇤ If yd↪n = 0, choose a background word wn↪bg ⇠ Multinomial('tbg ),
• ⇤ Choose yd↪n ⇠ Multinomial(χtw ),
• ⇤ If yd↪n = 1, choose a storyline keyword wn↪s ⇠ Multinomial('ts ),
• ⇤ If yd↪n = 2, choose a global topic zn ⇠ Multinomial(✓t ), choose a word wn↪z ⇠ Multinomial('tz ).

To represent the dependency of stories belonging to the same storyline, we define a vector of M + 1 weights θts = ¶θts↪m♦Mm=0 (θts↪m > 0) that each σts↪m↪ & t s↪m↪ ⌧ t s↪m↪ υts↪m contributes to calculating the priors of 'ts ↪ φts ↪ !ts ↪ ts , where σts↪m denotes the storyline-keyword distribution under storyline s at previous epoch m, & t s↪m denotes the storyline-location distribution under storyline s at previous epoch m, ⌧ t s↪m denotes the storyline-person distribution under storyline s at previous epoch m and υts↪m denotes the storyline-organization distribution under storyline s at previous epoch m.

The priors for storyline-keyword distribution 'ts , storylinelocation distribution φts , storyline-person distribution !ts , storyline-organization distribution ts at epoch t are calculated as γ ts = PMm=0 θts↪mσts↪m↪ "ts = PMm=0 θts↪m& t s↪m↪ ✏ts = PMm=0 θts↪m⌧ t s↪m↪ ⌘ts = PMm=0 θts↪mυts↪m.

In our experiments, the weight parameters are set to be the same regardless of storylines. They are only dependent on the time window using an exponential decay function, θm = exp(-λ ·m) where m stands for the mth epoch counting backwards in the past M epoches. That is, more recent documents would have a relatively stronger influence on the model parameters in the current epoch compared to earlier documents.

The storyline-keyword distribution 'ts , the storylinelocation distribution φts , the storyline-person distribution !ts and the storyline-organization distribution ts at epoch t are generated from the Dirichlet distribution parameterized by γ ts ↪ "ts ↪ ✏ts ↪ ⌘ts , 'ts ⇠ Dir(γ ts )↪ φts ⇠ Dir("ts )↪ !ts ⇠ Dir(✏ts ), and ts ⇠ Dir(⌘ts ), respectively. With this formulation, we can ensure that the mean of the Dirichlet parameter for the current epoch is proportional to the weighted sum of the storyline-keyword, storyline-location, storyline-person, storyline-organization distributions at previous epochs.

4 Inference and Parameter Estimation

We use collapsed Gibbs sampling to infer the parameters of the model, given observed data. Gibbs sampling is a Markov chain Monte Carlo method which allows us to repeatedly sample from a Markov chain whose stationary distribution is the posterior of interest, std and ztd↪n here, from the distribution over that variable given the current values of all other variables and the data. Such samples can be used to empirically estimate the target distribution.

4.1 Storyline Sampling

Letting the subscript -d denote the quantity that excludes counts in document d, the conditional posterior for std is:

where Dt is the total number of documents in current epoch t, ntnew denotes the number of documents assigned to the new storyline generated in current epoch t, ntnew↪j denotes the number of documents assigned to new storyline indicator j in current epoch t, ntpri denotes the number of documents assigned to an existing storyline generated in the past M epochs, ntpri↪j denotes the number of documents assigned to an existing storyline indicator j generated in the past M epochs, nj↪l is the number of times location l assigned with storyline j, nLj denotes the total number of locations with storyline j in the document collection, nj↪o is the number of times organization o assigned with storyline j, nOj denotes the total number of organizations with storyline j in the document collection, nj↪p is the number of times person p assigned with storyline j, nPj denotes the total number of persons with storyline j in the document collection, nj↪k is the number of times words with topic label k with storyline j, nKj denotes the total number of words with global topic with storyline j in the document collection, nk↪v is the number of times the word v with topic k, nVk denotes the total number of words with global topic in the document collection and counts with (d) notation denote the counts relating to the document d only. The terms in the big curly bracket denote the probability of assigning document d to storyline j by incorporating CRP.

4.2 Word Switch Variable and Topic Sampling

For each word token wd↪n in document d, the posterior probability of adding it to background word is derived as:

where nm↪bg denotes the number of words in document m assigned to the background word and nbg↪v denotes the number of word v assigned to the background word.

For each word token wd↪n in document d, the posterior probability of adding it to storyline j key word is derived as:

where nm↪j denotes the number of words in document m assigned to the storyline j key word and nj↪v denotes the number of word v assigned to storyline j key word.

For each word token wd↪n in document d , the posterior probability of adding word to global topic k with storyline j is derived as:

where nm↪z denotes the number of words in document m assigned to the global topic, nk↪v denotes the number of word v assigned to the global topic k and nj↪c denotes the number of words assigned to the global topic c with storyline j.

The hyperparameters of the model are set ↵ = 1↪ λ = 0▷5↪ ↵ts = βt = ⇣ t bg = 0▷1↪ ⇣ tpri = ⇣ tnew = γ tz = γ t bg = 0▷01↪ ⇣ ts = 0▷2↪ ⇣ tz = 0▷7(s 2 1▷▷St↪ t 2 1▷▷T) in our experiment.

5 Reduction of Sampling Complexity

In our model, the Gibbs sampling procedure mainly consists of two steps. The first step is storyline sampling, which scales linearly with the number of words in the document requiring a computation for every existing storyline. To solve this problem, we turn to Metropolis Hastings (MH) and define q(s) as the storyline proposal distribution

whose computation complexity scales linearly with the number of important entities such as location, person and organization. We sample s⇤ from this proposal and compute the acceptance rate r of state std ! s⇤ .

The second step is topic sampling, which needs O(K) per-token complexity. Here, we borrow the idea of LightLDA [Yuan et al., 2015] to reduce sampling complexity, in which a new O(1) per-token MH sampler has been developed. We employ two proposal distributions and combine both proposals to improve mixing. The first proposal is wordproposal:

where nk↪v denotes the number of word v assigned to the global topic k. Once z ⇠ qw(z) is sampled, we can compute the acceptance probability in O(1) time, as long as we keep track of all sufficient statistics n during sampling. To sample from qw in O(1), We use the alias approach, which transforms a non-uniform distribution into a uniform distribution. Furthermore, The building cost of alias table gets amortized to O(1) due to alias table re-used in MH sampling.

The second proposal is storyline-proposal:

where nj↪k denotes the number of words assigned to the global topic k with storyline j. We can sample from nj↪k by simply drawing an integer j uniformly from 1↪ 2↪ ▷▷▷↪ nj, so the storyline-proposal can be sampled in O(1) non-amortized time and we do not need to construct an alias table.

6 Experiments

In this section, we first introduce the datasets we used for our experiments, and then describe the baseline approaches, finally present the experimental results.

6.1 Datasets

We crawled and parsed the GDELT Event Database (http://data.gdeltproject.org/events/index.html) containing news articles published in the month of May in 2014. The whole one-month data contain 526,587 documents, which we called Dataset I. As it is time consuming to identify all the true storylines in such a large dataset, we only report the precision but not recall of the storylines extracted. To fully evaluate the performance of the proposed approach, we manually annotated one-week data extracted from Dataset I, containing 101,654 documents, which we called Dataset II. In dataset II, altogether 77 storylines are identified. In general, storylines can be categorized into four types: (1) long-term storylines which last more than 2 weeks; (2) short-term storylines which last less than 1 week; (3) intermittent storylines which last more than 2 weeks and interrupt in the middle period; (4) new storylines which start in the middle of the period, not the beginning. We found that in Dataset II, not all these types of storylines exist. As the proposed approach aims to identify all types of storylines, we therefore manually construct Dataset III by random selecting all types of storylines from Dataset I. This dataset consists 23,376 documents annotated with 30 storylines.

In our experiments, we used the Stanford Named Entity Recognizer for identifying the named entities. In addition, we removed common stopwords and only kept tokens which are verbs, nouns, or adjectives from these news documents. For the purpose of modelling, we split news documents by their publication dates and consider each day as an epoch.

6.2 Baselines

We chose the following methods as the baselines.

1. K Means+Cosine Similarity (KMCS): It first applies K Means to cluster documents in each epoch, then uses Cosine Similarity to link stories in different epochs to form a storyline.
2. Stan-LDA+Cosine Similarity (LDCS): It first applies standard latent Dirichlet allocation (LDA) to detect latent storyline indicator. Each storyline is modelled as a joint distribution over some named entities and words. Cosine Similarity is used to link stories in different epochs to form a storyline.
3. Dyn-LDA (DLDA): Topic-word distribution and popularity are linked across epochs by make a Markovian assumption in the model.
4. RCRP [Ahmed et al., 2011]: It is a non-parameter model for evolutionary clustering, which assumes that the past story popularity is a good prior for current popularity.
5. SDM [Zhou et al., 2015]: It assumes that the number of storylines is a constant and the storyline is modelled as a joint distribution over entities and keywords. The dependency of different stories of the same storyline at different epochs is captured by the modification of Dirichlet priors.

For SDM, the storyline number is set to 100 on Dataset II and 30 on Dataset III. The topic number is set to 100 on Dataset II and 20 on Dataset III. The number of historical epochs M, which is taken into account for setting the Dirichlet priors for the storyline-keyword, storyline-location, storyline-person, storyline-organization distributions, is set to

7, the same as in our proposed approach. For RCPR, the hyperparamter ↵ is set to 1. Both LDCS and DLDA employ the same storyline number and topic number as SDM. For KMCS, the number of clusters is set to 100 on Dataset II and 30 on Dataset III.

6.3 EvaluationMetrics

To evaluate the performance of the proposed approach, we use precision, recall and F-measure which are commonly used in evaluating information extraction systems. The precision is calculated based on the following criteria: 1) The entities and keywords extracted refer to the same storyline. 2) The duration of the storyline is correct. We assume that the start date (or end date) of a storyline is the publication date of the first (or last) news article about it.

6.4 Experimental Results

The evaluation results of our proposed approach in comparison to the baselines on dataset I, II and III are presented in Table 1. For Dataset I, as it is hard to know the ground-truth of storylines within it, we only report the precision value by manually examining the extracted storylines. It can be observed from Table 1 that simply using K-means to cluster news articles in each day and linking similar stories across different days in hoping of identifying storylines gives the worst results on both dataset II and III. Using LDA (LDCS) to detect stories in each day improves the precision dramatically. The dynamic LDA model (DLDA) assumes topics (or stories) in the current epoch evolve from the previous epoch and further improves the storyline detection results significantly. SDM aims to capture the long distance dependencies in which the statistics gathered in the past M days are taken into account to set the Dirichlet priors of the storyline-topicword, storyline-topic and storyline-entity distributions in the current epoch. However, SDM cannot generate new storylines. While RCRP can generate new storylines automatically, it does not model explicitly the generation of named entities such as persons, locations and organizations. As a result, it failed to identify any intermittent storylines. We also notice that SDM gives better results compared to RCRP on Dataset II but performs worse on Dataset III. One possible reason is the Dataset III contains some storylines happened sometime in the middle of the time period processed. SDM expects all the storylines start around the same time and hence is not able to detect new storylines happened at a later time.

By considering not only the long distance dependencies of storylines but also the new storylines generated in the middle of the time period, our proposed approach gives the best precision value on Dataset I and achieves the best performance on both dataset II and III. In specific, for Dataset II containing 77 storylines, our proposed model extracted 82 storylines among which 60 are correct. For Dataset III consisting of 30 storylines, our proposed model extracted 28 storylines among which 21 are correct. Moreover, the number of correctly extracted storylines by the proposed approach is more than that extracted by SDM. It empirically verifies that the proposed model can handle different types of storylines more effectively compared with the baselines when dealing with big data stream.

6.5 Structured Browsing

We illustrate the evolution of storylines by using structured browsing, from which the structured information (entities, topics, keywords) about storylines, the duration of storylines and the storyline popularity over time can be easily observed. Figure 2 shows the extracted storyline related to "India Election". Six representative epochs are highlighted in Figure 2 with detailed structured representations of the storyline. At the beginning, it can be easily deduced that there will be a prime minister election between Modi and Gandhi in India from the structured representation p "Modi, Gandhi" and w "prime, elect" at day 1. After that, election commission denied Modi's rally at day 9 which can be found from p "Modi", o "commission" and w "deny, rally". Then, at day 13, exit polls predicted that Modi will be next prime minister of India. At day 16, Modi won election to be prime minister of India and attended his swearing ceremony at day 21. Finally, Modi set up the new cabinet at day 26. All these information can be easily found from the structured representations of the storyline generated by our proposed approach. Based on the topic related words shown in Figure 2, we can also easily classify the extracted storyline as "politics".

6.6 Computation Complexity

To explore the efficiency of the Metropolis-Hastings sampler for the reduction of sampling complexity of the proposed model, we conducted an experiment by running the proposed approach with and without using the MetropolisHastings method. We run experiments on the dataset which consists of 500 documents initially. After that, the dataset is enlarged by gradually adding 500 documents each time until it contains 10,000 documents. The topic number is set to 50. Figure 3 illustrates the time consumed in each iteration when trained on the datasets with different sizes. It can be observed that the running time of both approaches increases with the increasing size of the data. But the running time of the proposed approach without Metropolis-Hastings sampler is about 6 times slower compared to the approach using it.

7 Conclusions and FutureWork

In this paper, we have proposed an unsupervised Bayesian model to extract storylines from news corpus. We further combine this model with CRP so that the number of storylines in each epoch can be determined automatically without human intervention. Moreover, per-token MH sampler based on lightLDA is employed to reduce sampling complexity. Experimental results show that our proposed model outperforms a number of baselines. In future work, we will explore the impact of different scales of the dependencies from historical epochs on the performance of storyline extraction.

Acknowledgments

This work was funded by the National Natural Science Foundation of China (61528302, 61472183), the Innovate UK under the grant number 101779 and the Collaborative Innovation Center of Wireless Communications Technology.