Sketch the Storyline with CHARCOAL: A Non-Parametric Approach

1 Introduction

Massive amounts of information about news stories are published on the Internet every day. When retrieve news articles from search engines such as Google by keywords, the large volumes of unstructured search results returned by search engines make it hard to track the evolution and narrative threads of each news story. A storyline is a development path that reveal the hidden relationships of a set of relevant news articles in a given story. For examples, the news articles about Malaysia Airlines Flight 370 story are developed around the "search thread" and the "investigation thread", which are two separate but parallel storylines. The description of a given story in terms of appropriate storylines illustrates a big picture to help readers grasp the evolution and the development of the given story. Only a few studies [Kumar et al., 2004; Lin et al., 2012] have been reported on storyline generation, they are focusing on developing systems or frameworks for storyline extraction.

∗Corresponding author

Here we are particularly interested in creating a probabilistic model to reveal and exploit the chain link between news articles about a news story, and simultaneous detect the topic that each news story is assigned to, e.g., MH370 story belongs to the aircraft accident topic.

In this paper, we propose the CHARCOAL model (abbreviated for "a hybird ddCRP based HierARChical tOpic model for news Article cLustering") from the perspective of unsupervised non-parametric modeling. Benefits from the proposed new hybrid distant-dependent CRP (hddCRP) prior, CHARCOAL adaptively achieves three goals simultaneously: 1) aggregates the news articles into coherent clusters (i.e., stories); 2) reveal the directed hidden connections between news articles about the same news story (i.e., the storylines); 3) assign each new story to its belonging news topic.

2 the CHARCOALModel

Before introducing our CHARCOAL model, we first make a few assumptions. We assume that each news article merely remarks the progress of a news story, which represents a cell in a storyboard. We can trace the evolution of each story on the storyboard by linking article to its most relevant progress (i.e., another article), and these links are defined as storylines. Therefore, each news story in our model is defined as collections of linked articles, and each news topic is defined as the collection of similar stories. Storylines, stories and topics are three kinds of latent variables, which will be discerned by the proposed CHARCOAL model.

In CHARCOAL, we first decompose entities from news articles and utilize them as well as news contents as clues to reveal the storylines between articles. Then, these lines (storylines) and their connected dots (articles) gradually form a Directed Acyclic Graph during the model estimation, which from another perspective composes a story sketch for us. Finally our model creates story collections (i.e., topics) to enclose similar stories. We will present the details of each step in the next subsections, and show how we combine them into a flexible and unified model. Some useful notations are shown in Table 1.

2.1 hddCRP and its relationship to CRP and ddCRP

The goal of CHARCOAL could be formally defined as follows: Given a bunch of news articles X = {x1:D}, we are going to jointly model three types of unobserved random variables, namely the discrete scalars ci indicating the hidden connections from article i to its most related article j in the past, underlying news story Sm, and potential topic Tk. It should be noted here that the three kinds of unobserved random variables are in a hierarchy (i.e., news articles, stories, and topics). In order to make this feasible, we proposed a novel prior distribution over hierarchical document partitions, which is named as hybrid distant-dependent CRP (hddCRP) here.

hddCRP is a stochastic process which has strong relationships to CRP [Pitman and others, 2002] and distance dependent CRP [Blei and Frazier, 2011]. The CRP exhibits the clustering property of the Dirichlet Process. It was named under a metaphor of a table assignment strategy for a sequence of customers that arrive in a Chinese restaurant with infinite number of tables. Each customer (data point) xi in X (dataset) sits at a previously occupied table (cluster) k with a probability proportional to the number of the customers Nk already sitting there, and at a new table with a probability proportional to a concentration parameter α. This can be interpreted as that each customer xj(j̸=i) in table k contributes 1 weight to Nk.

ddCRP generalizes CRP by introducing a changeable weight on xj, and the weight is decided by two things: a distance measure dxi,xj between xi and xj; and a decay function F(d), which satisfies F(∞) = 0. Moreover, instead of assigning table k to xi directly, ddCRP assigns xj to xi. Such assignments create directed links between customers, and customers that are reachable from each other through customers assigned to the same table. This yields a non-exchangeable distribution over partitions, since table assignments may change when a new customer assignment is observed.

Although ddCRP allows to model the (directed) connections between news articles, it does not provide a nature of the hierarchy between news articles. This limitation makes ddCRP inappropriate for our initial goal (i.e., the hierarchical modeling of three kinds of unobserved random variables); therefore, we attempt to extend ddCRP hierarchically. There are two types of extensions. Hierarchical dirichlet process (HDP) [Teh et al., 2006] demonstrates the first type. HDP groups data into a pre-defined hierarchical structure, where each level is associated with a Dirichlet process, whose base measure is sampled from a higher-level Dirichlet process. Another type is to create nested priors, such as nested CRP [Blei et al., 2010], nDP [Rodriguez et al., 2008], and TSSB [Ghahramani et al., 2010]. They introduce nested DP or nested CRP prior on topics, which organize the topics according to a tree structure, in which more abstract topics are near the root and more concrete topics are near the leaves.. They can be described in a fragmentation process, where each group in a higher-level is further divided into small groups, and each fragmentation is governed by CRPs/DPs with a shared concentration parameter. However, due to the nonexchangeable property of ddCRP, in most cases, it is not feasible to build nested ddCRP priors, nor is associated each level with a ddCRP prior as HDP does. (However, creating a hierarchical model with a mixture of a single ddCRP layer and CRP/DP layers may be feasible.)

Our proposed hddCRP hierarchically extend ddCRP in a different way. hddCRP not only creates a hierarchy of temporal data (e.g., news articles), but also embeds knowledge of connections from different aspects to each hierarchy, which is crucial to many applications of practical interest. As we observe, ddCRP only allows one single self customer assignment (self-link) for each table (cluster). Under a given ddCRP prior, if a customer assignment is not a self-link, two tables are merged. Only a self-link assignment can stop the table merging, and completes a cluster. However, the discovered clusters may continue to merge given other ddCRP priors. Introducing a new ddCRP prior with a new distance measure and a decay function may lead clustering of tables by assigning the current table to other tables. Every time when we introduce a new prior, a new level of hierarchy is created. By combining different ddCRP priors, we may assign probability distributions to ensembles of forests, where each tree in the forests has the same depth, but an unbounded branching. If we consider a hddCRP with 3 depths, its structure can be interpreted as follows: the leaf nodes of all the trees in a forest are news articles (customers); the second level nodes are stories (tables); and the top level nodes are topics (restaurants). We need to specify dxi,xj (distance measure) and F(d)

(decay function) for each non-leaf level to complete this hddCRP prior.

2.2 Distance and Decay Functions

As described above, to complete the hddCRP prior for our CHARCOAL model, we need to specify distance measures and decay functions for both article link assignment and story link assignment.

For article link assignments, we adopt a shared entity appearance based distance dSi,j. We define entities as names of persons, organizations, or locations, which can be extracted by name entity recognition (NER) tools in OpenNLP[Baldridge, 2005], or the Stanford Named Entity Recognizer 1 . More recent developed Named Entity Extraction (NEE) services, such as AlchemyAPI 2 , and DBpediaspotlight [Mendes et al., 2011], offered even better solutions, since they not only identify entities, but also link them to related semantic resources.

With extracted entities, the distance between document i and j is defined as follows: dSi,j △= fS(i, j) = 12 ( eij |i|e + eji |j|e ) and eij represents the number of times when the shared entities have appeared in document i, and |i|e represents the number of the discovered entities in total in document i. The decay function we use for dSi,j is a weighted window decay, which is specified as follows. FS(i, j, dSi,j) = 1[0 < ti - tj < a]dSi,j, where 1[ ] is an indicator function, ti is the time-stamp of document i, and a is an integer indicating a window size.

For story link assignments, since stories with similar contents belong to the same topic, and all the stories S in CHARCOAL are represented as probabilistic distributions, we may adopt the relative entropy based approaches to measure the story similarity. Therefore, their distance dTm,n △= fT (m, n) may be defined by any symmetric relative entropy based distance measures, such as symmetric KL divergence, i.e., KL(Sm,Sn)+KL(Sm,Sn) 2 , or Jensen-Shannon divergence. For these measurements higher similarities actually yield shorter distances; therefore, a new decay function FT (d) is defined to ensure the positive correlation between similarities and distances, where FT (m, n, dTm,n) =

cay function satisfies a normalization requirement that ∑ m̸=n FT (m, n, dTm,n) = 1 - π. (π is the concentration pa-

rameter of the ddCRP at the current level.)

2.3 Generative Process

With the help of the fully specified hddCRP prior, we now build our CHARCOAL model and describe the generative process of the proposed CHARCOAL model.

In CHARCOAL, the topic hierarchy is modeled sightly differently from the most traditional topic models. First, article i in text corpus is represented as a V dimensional vector xi. xi is a collection of words from the same article, where each dimension of xi indicates the frequency of a particular word in article i. Therefore, xi is viewed as a collection of word samples, and we assume that these word samples are generated from a Multinomial distribution Sm(m=1:M). Sm is also a V dimensional vector, and can be viewed as the underlying story representation of a article collection XSm . We then further assume that S = {S1:M} is the collection of the samples from higher K Dirichlet distributions with their corresponding base measures T = {T1:K}, and each Tk(k=1:K) in T is also a V dimensional Multinomial distribution which represents the underlying topic of a story collection STk . In this model, the story/topic assignment of each article/story is controlled by both their similarities and our defined hddCRP prior.

1 http://nlp.stanford.edu/software/CRF-NER.shtml

2 http://alchemyapi.com

The pseudo graphic model representation of CHARCOAL is shown in Figure 1. The representation is pseudo because the underlying story assignment of article xi depends on the story assignments of other document X-i, and the topic assignment of story Sm depends on the topic assignments of other stories S-m. It is impossible to present such irregular and unobserved dependencies by the traditional plate notation. Therefore, we make a small extension to the traditional plate notation, where one-to-many dashed links are used to represent such dependencies.

If we denote ηS as a collection of story level distances and decay function ηS = {FS, dS}, and ηT as a collection of topic level distances and decay function ηT = {FT , dT}. The generative process of CHARCOAL is described as follows:

1. For each i ∈ {1, ...,D}, draw a customer assignment ci ∼ ddCRP(ηS; α) for article xi. If ci is a self link, then continue to draw a story assignment zfc(ci) ∼ ddCRP(ηT ; π), otherwise assign zfc(ci) = zfs(fc(ci))
2. For each k ∈ {1, ...}, draw a topic T ∗ k ∼Dir(β)
3. Draw Sfc(ci) ∼Dir(Tfc(zi))
4. For each i ∈ {1, ...,D}, draw article xi ∼ Dir(Sfc(ci))
5. For each n ∈ {1, ..., |xi|}, draw word wn ∼ Multi(xi)

where Function fc(l) returns the cluster index of customer assignment l, and fs(c) returns the self assignment link of cluster c. Multi() represents a Multinomial distribution; Dir(δ) represents a Dirichlet distribution with a base measure δ; ddCRP(ηS; α) and ddCRP(ηT ; π) represent story and topic level ddCRP priors, respectively; |xi| represents the total number of words in article xi. Other notations may be found in Table 1.

3 Approximate Inference

An exact inference in topic models is often intractable and many approximate inference methods are adopted in practice. In this paper, we resort to collapsed Gibbs sampling for model learning and hyper-parameter inference.

3.1 Posterior Sampling

Collapse S and T: Given a collection of data points X, if we define XS as a group of data governed by a Multinomial distribution S, where S is a latent variable generated from a Dirichlet distributed with a base measure β, then the variable S could be collapsed due to the Dirichlet-multinomial conjugacy, and the marginal likelihood of XS given β, could be written as:

where n(.) is the total number of the terms in XS, nv is the number of the times term v appeared in XS, |δ| indicates the number of dimensions of δ, and Γ() is the gamma function.

Similarly, in CHARCOAL latent variables S = {S1:M} and T = {T1:K} are in multinomial distributions, which represent topic and story, respectively. They can be integrated out according to the Eq. 1. Therefore, we only need to sample story link z = {z1:M} and article link c = {c1:D}.

Sample c: For each article link assignment (i.e., storyline) ci in c, its marginal distribution on given all documents X = {x1:D}, and the rest document assignments without ci, may be factorized into two parts:

The first part is the prior distribution. Since FS yields temporally sequential distances in order, according to the hddCRP definition, this distribution may be written as:

While the second part is empirical likelihood, if we denote θ = Tfc(zfs(fc(j))), it can be written as:

Since any p(XS(.) |θ) may be computed easily according to Eq.(1), we now sample ci according to following equations:

Sample z: Story level link assignments z = {z1:M}, which connects stories to topics, may be sampled similarly; their marginal distribution is given as:

where β is the Dirichlet smooth of topics T

3.2 Sampling Hyper-parameters

Sample α: Given all the article links (i.e., stroylines) c, the posterior of α, p(α|c) = p(c|α)p(α). Its likelihood part is calculated as follows:

since the prior α is continuous, it is difficult to sample exactly from the posterior distribution p(α|c); as mentioned in the literature [Blei and Frazier, 2011], we may use the GriddyGibbs approach for sampling approximately.

Sample π: Similarly, according to the posterior of π, p(π|z) = p(z|π)p(π). Its likelihood part p(z|π) is actually quite simple to calculate, due to the constraint that ∑ n̸=m FT (m, n, dTm,n) = 1 - π.

If we make π beta distributed, that is p(π|a0, b0) = Beta(a0, b0), then the posterior of π, p(π|z, a0, b0) ∝ B(a0+K,b0) B(a0,b0) Beta(a0 +K, b0) = E(πK )Beta(a0 +K, b0), where K is the number of the topics, B(a, b) is the beta function B(a, b) = Γ(a)Γ(b) Γ(a,b) , E(πK ) is the Kth raw moments of π, and E(πK ) = a(1,K) 0 (a0+b0)(1,K) ; note that a(1,K) = a(a + 1) · · · [a + (K - 1)] is the ascending power of base a and order K.

3.3 Model Estimation

The model estimation procedure is shown in Algorithm 1.

Algorithm 1 Model Estimation of CHARCOAL

Input: a set of documents X= {x1:D}; Output: article link assignments c, story link assignments z; 1: For each article xi, we set its article/story link assignment to itself, i.e., ci = i, zfc(ci) = fc(ci); 2: for each i in {1, ...,D} do 3: Detach article i from the state by setting ci = i; 4: for each j in {1, ...,D} do 5: Compute distance dSi,j, and then the posterior p(ci = j|c-i, X, θ, α, ηS) according to Eq.(2); 6: end for 7: Sample a new ci from the posterior distribution; 8: if ci = i then 9: for each n in {1, ...,M} do 10: Compute distance dTci,n, and then the posterior p(zfc(ci) = n|z-fc(ci), c, S, β, π, ηT ) according to Eq.(3); 11: end for 12: Sample a new zfc(ci) from the posterior distribution; 13: else 14: Assign zfc(ci) = zfs(fc(ci)); 15: end if 16: end for 17: Update hyper-parameters every 50 iterations; 18: Repeats step 2 until convergence;

hddCRP can be decomposed into multiple ddCRPs, resulting in a more complex sampling process. The computational complexity of CHARCOAL is highly dependent on the data and distance/decay functions defined at each hddCRP level. In the worst case, each data point has non-zero distance with other data points (fully connected), but its table assignment is a self link; the complexity of our algorithm in such case is O(n2 ) ∗ O(Eq.(1)) for one iteration. In the best case, in which all the data points are unreachable from each other, the complexity is O(n) for each iteration. While in the most cases, due to the existence of decay function, the connections among data points are quite sparse, and we only have to calculate Eq.(1) when table assignment triggered table splitting or merging. Therefore, the computational cost of CHARCOAL is affordable in practice.

4 Model Evaluation

In this section, we employ CHARCOAL to analyze some challenging text corpra of different news categories, and analysis its clustering performance with two comparison studies. We also demonstrate its effectiveness by visualizing a few CHARCOAL topics.

4.1 Compare CHARCOAL with the Two Stage Clustering Methods

CHARCOAL jointly models the stories and topics as well as their inner connections. In this section, we verify that this joint modelling yields a better result than the two stage clustering by evaluating the document clustering results on a real world news corpus.

The data corpus we use to diagnose our model contains 4,908 news articles from the New York Times International News section and covers a time period from Jan 2014 to Aug 2014. We have removed the low frequency words and stop words, yielding a corpus of 4,780 unique terms and 1.63M observed words. Each article has a region tag, which is extracted through an analysis of its URL and is served as the ground truth during the diagnosis. Entities are extracted by AlchemyAPI. Since location tags are used as the ground truth, we therefore only employ the shared person names to calculate article distances dS. After removing non-shared entities, 45,868 entities are identified, and they belong to 3,326 unique (but may ambiguous) names.

In this experiment, we first degrade CHARCOAL to a single level model, which only contains one document-story clustering (this could be simply achieved by setting π=1). After the model convergence, we then apply complete-linkage clustering (CLC) [Brian S. Everitt, 2001] and k-means on the generated stories to further create hierarchical topics. CLC and k-means require a distance measure between pair of stories; we adopts the same distance measure and decay function that we apply to CHARCOAL for the story level clustering (for distance measure, Symmetric KL (SKL) and JSD are used respectively). On the other hand, we control the number of the topics that are estimated by CHARCOAL indirectly by tuning the topic level concentration parameter π (to achieve this the update of π is prohibited). CHARCOAL and the two stage clustering models are initialised with story level concentration parameter α = 0.5, topic smooth β = 0.05, and time window size α = 8 days. For CHARCOAL, π varies from 0.05 to 0.95 with an interval of 0.05, and its topic level distance dT is measured by JSD.

The clustering results are evaluated under three well known metrics [Manning et al., 2008]; they are the percentage of correct classification (Purity), the normalized mutual information (NMI), and the Rand Index. Figure 2 illustrates the model performances as a function of the number of the topics. As shown in Figure 2, by tuning π, CHARCOAL produces the number of the topics from 176 to 476, which outperforms all the three other approaches in all the three metrics all the time.

4.2 Compare CHARCOAL with other Non-parametric Hierarchical Topic Models

As mentioned in Section 2.1, there are two major ways of building the hierarchy on CRP; they are HDP and hLDA. It is important to make a quantitative comparison with these models, since they are the state-of-the-art topic models, and they are both non-parametric and hierarchical. The experiments are performed on collections of annotated news articles from New York Times with different major categories. Their characteristics are documented in Table 2 below:

The experiment setup is as follows:

1) the HDP inference is performed through a collapsed Gibbs sampler, with a burn-in of 500 samples; its hyperparameters are updated every 50 iterations. For evaluation purpose, articles are assigned to the topics that occupy the largest proportion in their topic mixture. 2) the hLDA inference is also performed by Gibbs sampling with a burnin period of 500 samples; its hyper-parameters are fixed and initialized as follows: topic smooth α = 0.1, word smooth η = 0.1, and nCRP concentration parameter λ = 1. Similar to CHARCOAL, hLDA creates hierarchical partitions on article collections. If we set the depth of nCRP prior to 4, hLDA generates trees with 4 depths, which are root, topic clusters, story clusters, and articles, respectively. In this experiment, topic clusters are used to evaluate hLDA performance. 3) CHARCOAL is initialized with story level concentration parameter α = 0.5, topic smooth β = 0.05, and time window size a = 8 days. We use JSD to measure dT, and hyperparameter π is updated every 50 iterations. Similarly, topic clusters are used to evaluate model performance.

For each experiment samples for the evaluation are collected a few iterations apart after the model convergence (after the burn-in period). The experiments' results are presented in Table 3. According to Table 3, CHARCOAL outperforms HDP and hLDA in all datasets, which indicated that our method could effectively improve clustering performance for many different news categories. This may be partially due to the storyline prior (i.e., shared entity appearance) serves as a useful feature on characterizing the development of a real world news story, which creates a solid foundation for topic level clustering.

4.3 Qualitative analysis with data visualization

In order to understand the CHARCOAL outputs more intuitively, we visualized a few CHARCOAL topics detected from NYT data corpus in Figure 3. For a close look at these discovered topics, we presented their story fragments, storylines as well as the top five words in each topic/story.

The upper part of Figure 3 presents two stories from a flood topic. They are two different floods happened in Australia and Brazil. CHARCOAL splits them into separated stories due to the weak/no evidences from the appearances of name entities, but the stories later are grouped into the same topic because of their similarities in contents.

The lower part of Figure 3 presents another story from topic "search, plane, flight". It is a story that records the progress of searching the missing flight MH370. Its storyline revealed the parallel development of the MH370 story. As shown in Figure 3, the main thread of MH370 splits up into two separated threads, one is concentrated on searching the lost fight, while the other one is focused on the investigation of the possible causes of the disappearance.

5 Conclusion and Future work

In this paper, we have presented CHARCOAL, a novel nonparametric probabilistic model via a hddCRP prior, which jointly models news storylines, stories, and topics. CHARCOAL produces a structural output of a set of news articles, which may help readers who are overwhelmed by information overload, to explore the big picture of popular news topics. The improvement of our proposed hddCRP prior is nontrivial because hddCRP gives the possibility to model document hierarchy from a new perspective, where ddCRPs are "stacked" to form a multi-layer model. In such model, the higher-level clusters server as priors to its lower-level offspring clusters. By redefining appropriate distance measures, it is easy to apply our hddCRP prior to other applications such as document summarization or evolution analysis[Tang et al., 2013b]. Some other extensions such as introducing domain information[Gao et al., 2012], or leveraging the importance between different types of measures[Tang et al., 2013a] may be considered as our future work.

Acknowledgments

This work was supported in part by the 973 Program (No. 2012CB316400), the NSFC (No. 61402401), the 863 Program (No. 2012AA012505), the China Knowledge Centre for Engineering Sciences and Technology (CKCEST), and the Zhejiang Provincial NSFC (No. LQ14F010004).