Online topic modeling allows for the discovery of the underlying latent structure in a real time stream of data. In the evaluation of such approaches it is common that a static value for the number of topics is chosen. However, we would expect the number of topics to vary over time due to changes in the underlying structure of the data, known as concept drift and concept shift. We propose a semi-synthetic dataset generator, which can introduce concept drift and concept shift into existing annotated non-temporal datasets, via user-controlled paramaterization. This allows for the creation of multiple di erent arti cial streams of data, where the \correct" number and composition of the topics is known at each point in time. We demonstrate how these generated datasets can be used as an evaluation strategy for online topic modeling approaches.
Topic modeling is an unsupervised learning task which attempts to discover
the underlying thematic structure of a document corpus. Popular approaches
include probabilistic algorithms such as Latent Dirichlet Allocation [
Online topic modeling is a variant of this task that takes into account the
temporal nature of a text corpus. This often involves working with a real-time
stream of data, such as that found in social media analysis and in analysis
procedures associated with online journalism. In other scenarios, this task involves
retrospectively working with a timestamped corpus which has previously been
collected and divided into distinct time windows. While many sources of text
naturally provide temporal metadata, we are currently unaware of any
readilyavailable source of ground truth text data for the online topic modeling task,
due to the expense and di culty of manually annotating large temporal corpora.
An associated issue is that, when applying online topic modeling approaches to
real-world text streams, the number of topics in the data will naturally vary
and evolve over time. However, for evaluation purposes, many existing works
assume that this number remains xed. This is not a realistic assumption due
to the expected variation in topics over time due to changes in their underlying
composition, known as concept drift and concept shift [
To accurately benchmark new online topic modeling approaches, a quantitative approach is required to determine the extent to which these approaches can correctly identify the number and composition of topics over time. However, to achieve this, a comprehensive set of datasets is required, which provide temporal information along with ground truth topic annotations. With these requirements in mind, in this paper we propose new semi-synthetic dataset generators which can introduce concept drift and concept shift into existing static text datasets in order to create arti cial data streams, where the correct number of ground truth topics at each time point is known a priori. We make a Python implementation of these generators available for further research1.
The paper is structured as follows. In Section 2 we present related work covering existing evaluation strategies for static and online topic modeling. In Section 3 we outline our proposed methodology behind two new synthetic dataset generators, before exploring the use of a number of test generated datasets in Section 4. We present our conclusions and future work in Section 5. 2 2.1
Topic modeling attempts to discover the underlying thematic structure within
a text corpus. These models date back to the early work on latent semantic
indexing [
Considerable research on topic modeling has focused on the use of
probabilistic methods, where a topic is viewed as a probability distribution over
words, with documents being mixtures of topics, thus permitting a topic model
to be considered a generative model for documents [
There are a number of di erent techniques used in the evaluation of traditional
topic modeling algorithms. The coherence of a topic model refers to the quality
1 https://github.com/MarkBelford/dataset-generator
or human interpretability of the topics. Originally a task involving human
annotators [
Online topic modeling is a variant of traditional topic modeling which operates
on a temporal source of text, such as that found in the analysis of social
networking platforms and online news media. There are a number of online approaches
for both LDA and NMF, however these vary greatly between implementation.
Some approaches utilise an initial batch phase to initialize the model and
afterwards update the model by considering one document at a time [
The evaluation of online topic modeling approaches tends to make use of static
annotated datasets, where the number of topics is known in advance. However,
these approaches frequently assume that the number of topics is xed and does
not change over time. In other cases, authors select a high value of k in order
to capture the majority of possible themes. However, this creates an
interpretation problem, as many noisy and irrelevant topics may also be returned by
the algorithm. These evaluation choices are understandable, given that
manually annotating a real-time stream of data is costly and time-consuming. In
other unsupervised tasks, such as dynamic community nding, the provision
of synthetically-generated datasets with prede ned temporal patterns (e.g. the
\birth" and \death" of communities [
The lack of annotated ground truth corpora with temporal information is problematic when evaluating online topic modeling approaches. For instance, how can we determine whether a proposed algorithm can correctly determine the number of topics in the data at a given point in time? Therefore, in this section we explore two di erent ways in which the distribution of topics can vary over time, and then present corresponding methodologies used to implement synthetic dataset generators based on these variations. Through user paramaterization, we can control the characteristics of the resulting datasets and the extent to which they change over time. Both generators contain stochastic elements, so that many di erent datasets can potentially be produced for the same parameter values.
Given the complex structure of natural language corpora, generating realistic
fully-synthetic datasets is extremely challenging. As an alternative, authors have
proposed generating \semi-synthetic" datasets which are derived from existing
real-world corpora [
Both generators also operate on the principle that a single \window" of documents represents one epoch in the overall dataset { i.e. the smallest time unit considered by the algorithm. Depending on the context and source of data, in practice this could range from anywhere between seconds (e.g. in the case of tweets) to years (e.g. in the case of nancial reports). However, for the purpose of discussion, we refer to these generally as time windows. 3.1
Concept shift refers to the change in concept due to a sudden variation in the underlying probabilities of the topics. In the context of online news, a common example might occur where the coverage of already established news stories is reduced greatly after the death of a prominent gure, while the coverage of this latter topic increases rapidly. A visual example of this can be seen in Fig. 1.
We propose a textual data generator, embedding the idea of concept shift, which operates as follows. To commence the process, k topics from the ground truth and window-size number of documents from these topics are randomly selected to form the initial time window. At each subsequent time window, documents are chosen from these topics. There is also a chance that, based on a user de ned probability parameter, shift-prob, a topic is added or removed from the model. The idea is that this event will simulate a concept shift over time. This process of generating time windows continues until the number of remaining topics reaches a minimum threshold, de ned by the parameter min-topics. Algorithm 1 Concept Shift Generator Parameters { input : an existing dataset with ground truth topic annotations. { k : number of starting topics. { window-size: number of documents in each time window. { shift-prob: the probability of a concept shift occurring.
{ min-topics: minimum number of topics present before ending.
Algorithm
2. Randomly select window-size documents from these starting topics. 3. Generate a new time window: { While the number of documents in the window is less than window-size If concept shift is activated, randomly add or remove a topic.
Randomly choose a topic from those already in the model.
Randomly choose a document from this topic.
Add this document to the window. 4. Repeat from Step 3 until min-topics remain in the model.
An overview of the complete process is given in Algorithm 1. The output of the process is a set of time window datasets, each containing documents with ground truth topic annotations.
It is important to note that, unlike a real stream of data, we do not have access to an in nite number of documents. Depending upon the size of the original input dataset, this can lead to situations where a topic that is currently present in the model can run out of documents in the middle of generating a new time window. This is handled by simply removing the topic so that it can no longer be chosen by the generator in subsequent time windows. 3.2
Concept drift refers to the gradual change in the underlying probabilities of topics appearing over time. An example of this is commonly seen in news media, where the coverage of an ephemeral event that is near the end of its news cycle, such as the Summer Olympics or FIFA World Cup, is gradually reduced over time. In contrast, the coverage of other newly-emergent stories may increase during this time. A simple visual example of this trend can be seen in Fig. 2.
The proposed concept drift generator (Algorithm 2) operates as follows. Firstly, k topics and window-size number of documents are are chosen based on randomly-assigned probabilities to form the initial window. For all remaining windows, topics are chosen based on their current probability. There is also a user-de ned parameter, drift-prob, that determines whether a concept drift event will occur in a given window. If this occurs, then the generator will randomly choose one topic to slowly remove by decreasing its probability over a xed number of time windows (determined by the parameter decrease-windows), while simultaneously choosing a new topic to slowly introduce over a xed number of time windows (determined by increase-windows). This process of continues until the number of topics remaining goes below a minimum threshold (min-topics). The output of the process is a set of time window datasets.
However, again there is the issue that we do not have an in nite number of documents, so topics might potentially run out of documents during a drift. Unlike the previous generator we do not simply remove the topic during the middle of the drift. Instead we leave the topic in the model for the remainder of the drift and if the topic is chosen we simply ignore it. Note that this can lead { input : an existing dataset with ground truth topic annotations. { k : number of starting topics, must be less than the total number of topics. { window-size: number of documents in each time window. { increase-topic: topic to be slowly introduced by concept drift. { decrease-topic: topic to be slowly removed by concept drift. { increase-windows: number of windows for a topic to gradually disappear. { decrease-windows: number of windows for a topic to gradually appear. { drift-prob: the probability of a concept drift occurring.
{ min-topics: minimum number of topics present before ending.
2. Randomly select window-size documents from these starting topics. 3. Generate a new time window: { While the number of documents in the window is less than window-size If concept drift is enabled, gradually increase and decrease the probabilities of the increase-topic and decrease-topic over increase-windows and decrease-windows respectively.
Otherwise choose a topic from those already in the model based on their probabilities. 4. Repeat from Step 3 until min-topics remain in the model. to some windows having less than window-size number of documents, depending upon the size of ground truth topics in the original input dataset. 4
In this section we explore sample datasets generated by our two approaches from Section 3, and demonstrate how these can be used to validate the outputs of a dynamic topic modeling approach. Note that our goal here is not to evaluate any individual topic modeling algorithm, but rather to illustrate how the proposed generators might be useful in benchmarking such algorithms. 4.1
As our input corpus for generation, we use the popular 20-newsgroups (20NG) collection2 which contains approximately 20,000 Usenet postings, corresponding to roughly 1,000 posts from each of 20 di erent newsgroups covering a wide range of subjects (e.g. \comp.graphics", \comp.windows.x",\rec.autos"). While this dataset has existing temporal metadata we chose not take this into consideration. We want to ensure that we arti cially induce events to use as our ground 2 Available from http://qwone.com/~jason/20Newsgroups/ truth rather than capturing snippets of temporal events from the original data. We also choose not to utilise these timetsamps as this information is not always available and our goal is to allow the methodology to generalise to any dataset that has ground truth annotations. In the case of both generators, we make use of k k0 of these annotated topics. We use these newsgroups as our ground truth topics. To illustrate the use of our generators, we generated four datasets which exhibit concept shift and four datasets that exhibit concept drift, using a variety of di erent parameter choices. A summary of the parameters and characteristics of these datasets is provided in Table 1. We observe that these sample datasets vary considerably in terms of their size, number of topics, and number of time windows. Note that the number of time windows produced by the generators is a function of the input parameters and the size of the input corpus. 4.2
To illustrate the use of the generated datasets, we apply the window topic
modeling phase from the Dynamic NMF algorithm [
We now illustrate how our proposed generator can produce datasets that can be used for online model evaluation. Again it is important note that the performance of the approaches being applied here is not our main focus, but rather the provision of synthetic datasets that can facilitate the more robust evaluation of online topic modeling algorithms.
N
N 2 3 4 5
6 Time Window 7 8 9
10 (a) shift-1 dataset. 3 5 7 9 11 13 15 17
19
Time Window (b) shift-2 dataset.
Ground Truth k Selected k 8 m u 4 0 1 20 s16 c i p o f12 T o r e b 8 m u N 4 0 20 s16 c i p o f12 T o r e b 8 m u N 4 0 20 s16 c i p o f12 T o r e b 8 m u 4 0 1 8 m u 4 0 1 20 s16 c i p o f12 T o r e b r e b r e b 8 m u 4 0 1 1 3 5 7 9 11 13 15
17 Time Window 1 3 5 7 9 11 13 15 17
19 Time Window (c) shift-3 dataset. (d) shift-4 dataset. 1 3 5 7 9 11 13 15
17
Time Window (e) drift-1 dataset.
1 3 5 7 9 11 13
15
Time Window (f ) drift-2 dataset.
N
N 3 5 7 9 11 13 15 17 3 5 7 9 11 identi ed by the dynamic topic modeling approach for each time window.
Firstly, the sample generated datasets allow us to assess the extent to which the coherence-based model selection approach for NMF correctly identi es the number of topics in each time window, by comparing its selections with the number of ground truth topics in the data. Fig. 3 shows comparisons for each of the eight datasets. For many of the datasets, the selected values of k broadly follow the trend in the ground truth (where either a concept shift or drift is occurring over time), and this is most strongly seen in the concept drift dataset, drift-4, although we see considerable variation at individual time points. However, for the smallest concept shift dataset, shift-1, we see a much poorer correspondence with the ground truth when evaluating this dynamic approach. The provision of the \correct" number of topics in the ground truth potentially allows researchers to develop and benchmark methods that could provide a more useful approximation of the number of topics in these datasets.
Secondly, the generated datasets allow us to evaluate the degree to which the
topics being discovered by NMF over time agree with the ground truth topics,
in terms of their document assignments. To assess the topic models generated at
each time window, we construct a document-topic partition from the
documenttopic memberships produced by NMF. This partition is compared with the
annotated labels for the documents for the ground truth in the corresponding time
window. To perform the comparison, we can use a simple clustering agreement
score such as Normalized Mutual Information (NMI) [
Table 2 summarizes the mean and range of NMI scores across all time windows for the eight generated datasets. It is interesting to see that the performance of NMF varies considerably between the datasets, with an overall maximum value of 0.653. In some cases the level of agreement is quite poor (e.g. the drift-1 dataset). This suggests considerable scope for improving topic models on these generated datasets, where NMI relative to the ground truth could provide researchers with a guideline to measure the level of improvement.
In this paper we have proposed two methods for generating semi-synthetic
dynamic text datasets from an existing static corpus, which incorporate
fundamental temporal trends { concept shift and concept drift. We have demonstrated
that this generator can produce datasets with a range of di erent
characteristics, which can be used in practice to evaluate the output of online and dynamic
topic modeling methods. In particular, the generator provides a mechanism to
evaluate the degree to which these methods can correctly determine the number
of topics at a given point in time, relative to a set of ground truth topics. Here
our focus has been on modeling the evolution of thematic structure as caused by
changes in the probabilities of the underlying topics appearing. However, changes
in concept can also occur due to the content of topics evolving over time [
Acknowledgement. This research was supported by Science Foundation Ireland (SFI) under Grant Number SFI/12/RC/2289.