Time-evolving Text Classification with Deep Neural Networks

1 Introduction

Text classification is a fundamental problem in data mining. Traditional classification algorithms are based on the assumption that data are independent and identically distributed. However, in many real applications like news topic classification [Allan et al., 1998; Kim and Hovy, 2006], event detection and tracing [Yang et al., 1998; Atefeh and Khreich, 2015], the data to be learned are not static. For example, topics in online social media and news media are usually observed sequentially from a series of time periods, and their distribution changes smoothly over time. Very often, such change mainly consists of two parts: long-term evolution due to concept drift and short-term fluctuation due to noise disturbance. For example, the concept of topic "media" commonly meant traditional print media like newspaper before 1960s, and after that it slowly drifted with the emergence of Internet, and today it more refers to the emerging new media including microblogs, podcasts, etc. Meanwhile, it is natural to expect that the overall interests of social media may fluctuate temporarily due to some emergency events during the long-term evolution.

These non-stationary scenarios create what we call timeevolving data or evolutionary data, which raises new challenges to traditional text classification. First, it is undesirable to simply use a single static classifier for all time periods. Otherwise, as the data distribution changes over time, the classifier may only learn some over-generalized features, thus fail to either reflect the nuances between different periods or fit the data of a specific time period. Second, divergences even contradictions lie between data of different time periods due to long-term evolution and short-term fluctuation. Thus, incorporating all the historical and current data to train a current classifier makes little sense in non-stationary scenarios. Even in stationary or non-evolutionary scenarios, training with simple combination of all historical data is also worthless and inapplicable due to the computation cost. Third, it is also unfavorable to obtain a series of completely independent classifiers for each time period, since in this way we may lose extensive valuable information from adjacent time periods. What's worse, when only a slice of all time periods is considered, the classifier may overly fit the slice data of the corresponding time period and not be able to distinguish between long-term data changes and short-term data fluctuations.

In this paper, we propose two neural network frameworks to learn a chain of evolving classifiers for time-evolving data. In the first framework, we introduce the temporal smoothness into learning process to train evolutionary neural network classifiers. In the second framework, we design a diachronic propagation mechanism to incorporate the historical impact into currently learned features. In both frameworks, the classifier can fit the corresponding slice data in each time period as much as possible, thus maintaining high sensitivity to the long-term data changes. In addition, the classifier can also take recent periods into account and not deviate too much to fit the historical data, thus maintaining high robustness to the short-term data fluctuations. Experiments on real-world news data demonstrate that our methods clearly and consistently outperform traditional neural network models in both accuracy and stability. Our main contributions are as follows:

1. We introduce the basic formulation of evolutionary classification with neural networks. To our best knowledge, it is the first time that the evolutionary case of neural network learning is explored to classify time-evolving data.
2. We introduce a basic evolutionary approach based on temporal smoothness framework and propose a diachronic propagation framework to extend arbitrary neural networks to evolutionary learning.

1. We conduct extensive experiments and case studies on two real-world news datasets and three synthetic datasets. The empirical results demonstrate that our approaches clearly and consistently improve the current start-of-the-art neural network models.

The code is available at https://github.com/RingBDStack/ Time-evolving-Classification.

2 RelatedWork

As traditional static machine learning algorithms are incapable for the goal to reflect long-term data evolution and maintain robustness against short-term data fluctuations, a new topic of evolutionary learning is introduced to deal with time-evolving data [Chakrabarti et al., 2006] and has attracted significant attention in recent years. For the unsupervised case of evolutionary learning problem, multiple classical clustering algorithms have been extended to evolutionary versions, such as k-means clustering [Chakrabarti et al., 2006], spectral clustering [Chi et al., 2007; Ning et al., 2007; Tang et al., 2008], Gaussian mixture model [Zhang et al., 2009], etc. Moreover, Wang et al. [2012] proposed a general model for clustering large-scale evolutionary data based on low-rank kernel matrix factorization. Xu et al. [2014] proposed an adaptive evolutionary clustering method by tracking the time-varying proximities between objects followed by static clustering. Furthermore, Jia et al. [2009] first considered the semi-supervised evolutionary learning problem, and proposed a general framework based on the Reproducing Kernel Hilbert Space. However, up to now, the work on the supervised case of evolutionary learning is still limited, especially on the time-evolving text classification. 1

Relevantly, deep learning models have proven to be stateof-the-art methods in various applications including text classification [Liu et al., 2017]. Particularly, recurrent neural networks (RNN, LSTM, GRU, etc.), which use feedback loops to exhibit dynamic temporal behavior, have shown promising results on sequential data classification issues such as speech recognition [Graves et al., 2013; Graves and Jaitly, 2014] and document classification [Tang et al., 2015; Yang et al., 2016]. However, they are still traditional methods dealing with static data with identical distribution, with the difference that each sample is a sequence of data (e.g., each document consists of a sequence of words). To our best knowledge, deep learning models have not been explored for evolutionary learning scenario to reflect the long-term changes of dynamically distributed data, which is our focus in this article.

Online learning is also related to our work, which is used to update the decision model continuously as new data arrives [Gama et al., 2014] and has been extensively studied recently [Crammer et al., 2006; Masnadi-Shirazi and Vasconcelos, 2010; Duchi et al., 2011]. Although online learning targets the similar problem setting as evolutionary learning, they are essentially different. On the one hand, online learning is mostly used in areas where it is computationally infeasible to train over the entire dataset and is under the same assumption that data are independent and identically distributed as traditional static machine learning. On the other hand, although there are also some studies on online learning in nonstationary scenarios such as concept drift [Gama et al., 2014; Ghazikhani et al., 2014], they mainly focus on the snapshot changes between old data and new data to improve adaptability to new data and to reduce learning costs, while do not concern about the long-term data trends and interactions, which is one of the core requirements of evolutionary learning.

1 Here we distinguish the concept of evolutionary classification on time-evolving data from evolutionary algorithms (EAs) motivated by biological evolution. Up to now, EAs are still traditional optimization algorithms to perform evolutionary computation on static data, which is unrelated to the problem discussed in this paper.

3 Time-evolving Text Classification

In this section, we first introduce the basic formulation of supervised evolutionary classification problem and then propose two evolutionary neural network (NN) frameworks.

3.1 ProblemFormulation

Unlike traditional static classification, in which the data are assumed independent and identically distributed, the goal for evolutionary classification is to train a chain of evolving classifiers on time-evolving data to reflect the long-term evolution and to maintain robustness against the short-term fluctuation.

In evolutionary classification applications, time is regularly sliced into a sequence of steps according to certain periods, which presents a sequence of sliced data, and the distribution of these data usually changes over time. Assuming there are T consecutive time steps, we are given a set of sequential data sets X = {X1 ,X2 , ...,XT}, and each subset Xt contains nt data points generated in time step t with an unknown data distribution P(x; t): Xt = {xt1 , xt2 , ..., xtnt }(t = 1, 2, ..., T), along with a corresponding set of class labels Yt = {yt1 , yt2 , ..., ytnt } where yt i represents the class label of data point xti . As the posterior distribution P(y|x; t) usually changes smoothly over time, the classification functions of different time steps are time-evolving. That is, the classifier ft is not only reflected from the mapping relationship between Xt and Yt which sampled in time step t, but also evolved from previous classifiers {fi}t-1 i=1 . More generally, the task of time-evolving data classification is to find T consecutive time-evolving classifiers {f, f, ..., fT} to reflect the mapping relationships {ft : Xt → Yt}Tt=1 for all time steps. As for neural networks, it is to train the corresponding T sets of evolving model parameters {θ, θ, ..., θT } on time-evolving data sets X.

3.2 NNwith Temporal Smoothness Framework

Temporal smoothness framework was first proposed by Chakrabarti et al. [2006] in evolutionary clustering problem, which is also applicable for the general learning problem on time-evolving data. Based on the smoothness assumption of time-evolving data, this framework aims to smooth the learning results over time as much as possible while remaining faithful to the current data. Following this framework, classifiers in evolutionary classification task should not change dramatically from one time step to the next. In other words, the classifiers ft1 and ft2 are expected to be more similar when time step t1 and t2 are closer. As for neural network models, since these models at different time steps only differ in model parameters and share the same model structure, we could ensure the similarity by preventing large deviation of model parameters during the training process.

Therefore, for evolutionary classification problem, we propose to seek the optimal classifier ft at each time step t(2 ≤ t ≤ T) by minimizing the following objective function:

where the first termCt is the current cost function defined on current data, and the second termHt is the historical distance penalty derived from the distance between current and historical classifiers. Specifically, we use negative log-likelihood losses to measure the cost on each data point (x, y):

where L is the class labels set of the whole data, ℓ(l, y) refers to the true probability that the class label of data point x is l, and f(l |x, θ) is the predicted likelihood produced by the neural network classifier f with parameters θ. Then the whole cost function in time step t is like following:

Using θi to denote the model parameters of classifier fi at time step i, Ht could be expressed as follows:

where the historical parameters θi(1 ≤ i ≤ t - 1) are known and fixed, which have been well-trained in an earlier time; αit is the weight to reflect user's emphasis on current cost and historical distance penalty. Generally, αit is exponentially decaying over time as follows:

where a is the initial decay factor to control the scale of historical distance penalty.

Following this way, we finally obtain a basic evolutionary approach to extend an arbitrary neural network model to seek a chain of evolving classifiers on time-evolving data, and we call it NNwith temporal smoothness (NN-TS).

3.3 NNwith Diachronic Propagation Framework

In general, a neural network classifier contains two components [Ganin et al., 2016], feature extractor to extract the high-level representation of the samples and label predictor to predict the probability of each sample belonging to a label. Specially, for evolutionary classification problem, as classifiers are usually trained successively for each time step, there are a chain of evolving extractors and predictors, and these components only differ in model parameters and share the same network structure at different time steps. In this case, for a data point x, there is a chain of features extracted from those time-evolving extractors, and these features are usually not independent of each other. Thus, we propose a diachronic propagation framework to incorporate these sequential features produced by evolving extractors.

A neural network with diachronic propagation framework usually contains more than one row (as shown in Figure 1), corresponding to successive time steps on time-evolving data. It starts with a traditional row without any specialties: a feature extractor E1 to extract sample's feature representation and a label predictor P1 to predict the probability based on the feature extracted. When we shift to a second time step, E1 and P1 have been trained well and their model parameters are frozen and immutable, and a new row of feature extractor E2 and label predictor P2 will be trained. But different from the first row, a diachronic connection layer is added and trained, it combines the features extracted by E1 and E2 and generates a new feature with the same dimension. We use hi to denote the feature extracted by extractor Ei and its dimension is k, then the diachronic propagation process via the diachronic connections could be expressed as follows:

where W2 ∈ Rk×2k is the weight matrix of diachronic connections in second row, [h2, h1] is the concatenation of h2 and h1 and is as the input of the diachronic connections, h∗2 is the output of the diachronic connections, g is an element-wise activation function such as RELU [Nair and Hinton, 2010].

Similarly, when switching to a deeper time step, a deeper row shall be appended and only that row is trainable. Then a deeper diachronic propagation occurs by recursively combining the extracted features via deep diachronic connection layers. A deep diachronic neural network with t (t ≥ 3) rows is shown in Figure 1, and the deep diachronic propagation could be recursively expressed as follows:

where Wi ∈ Rk×2k is the weight matrix of diachronic connections in layer i. The last h∗t is the composited feature produced by the deep diachronic connection layers, which is propagated to the last predictor Pt. Finally, Pt produces a probability distribution to perform classification similar to traditional neural networks.

In this diachronic propagation framework, we can find that features will propagate diachronically along successive time steps while forward propagating along the current time step. By combining currently and previously learned features in this manner, this framework achieves a richer compositionality, which is beneficial to learn the dynamic characteristic in non-stationary scenarios and to reflect long-term changes on time-evolving data. Moreover, the diachronic connections could naturally transfer prior knowledge across different time steps, making it more capable of keeping robust to temporary noise by incorporating historical information.

Following this framework, the output probability distribution predicted by neural networks not only represents the current data feature by forward propagation, but reflects the impact of historical information. By incorporating the current features and historical impact, the final evolving classifier function could be expressed as follows:

of word2vec [Mikolov et al., 2013] to train 100-dimensional word embeddings from Wikipedia corpus based on CBOW model. For training neural network models, we use minibatch stochastic gradient descent (SGD) optimizer to minimize the corresponding objective functions, and the common parameters are empirically set, such as batch size as 128 and moving average as 0.999, etc.

To reduce error, we repeat each experiment five times independently and use the mean value as the final experiment result. We also try our best to tune the models for both our methods and baseline methods. As a result, all the experiments of each method produce best results to our best efforts.

4.3 Results and Analysis

We compared state-of-the-art neural models (TextCNN, RCNN, HAN) and their evolutionary versions based on temporal smoothness framework (suffixed by TS) and diachronic propagation framework (suffixed by DP) proposed in this paper, and Table 3 and Table 4 are their experimental results for multi-class classification in different time steps on NYTimes and RCV1 datasets. We evaluate each dataset with two metrics, accuracy (higher is better) including a single value in each time step and an average value in all time steps, and Std (Standard Deviation, lower is better) among all time steps.

From the experimental results, it is observed that the evolutionary methods clearly and consistently outperform the standard neural network models on different datasets and different time steps, especially for RCNN-DP, which achieves the best performance compared with other methods (averagely 3% improvement on NYTimes and 2% improvement on RCV1). Generally, by applying evolutionary frameworks on different neural network models, we improve the classification accuracies in different time steps by 1%-6% on NYTimes and by 1%-3% on RCV1. The results prove the effectiveness of the proposed evolutionary frameworks.

The experimental results demonstrate the advantage of the evolutionary methods in two aspects. First, by considering the long-term data changes and interactions within consecutive time steps, evolutionary models can effectively capture the evolutionary information of features compared with traditional neural network models, and clearly help to increase the classification accuracies on time-evolving data. Second, over the whole time steps of each dataset, we can observe that it can maintain a more stable and smooth result by applying evolutionary frameworks, which suggests that the evolutionary methods are more robust against noise and more suitable for handling the data fluctuations in non-stationary scenarios. In addition, we can find the diachronic propagation framework achieves better performances than temporal smoothness framework in most cases, which indicates that the diachronic connection is more effective to adaptively learn the evolution characteristic than a simple regularization term of parameter distance. We also find that the evolutionary methods bring about more improvements on the NYTimes dataset than the RCV1 dataset. The reason could be that the NYTimes dataset has a much longer time period, and hence has a stronger long-term evolution, making it more conducive to evolutionary learning. Overall, the proposed evolutionary frameworks have good adaptability and efficacy, and can be easily extended to different neural network models and achieve much better classification performances on both long-term and short-term time-evolving data.

4.4 Case Study

To better understand the effectiveness of proposed methods on different evolutionary scenarios, we conduct more experiments on three synthetic datasets introduced in Section 4.1, and the results are shown in Figure 2-(a)(b)(c).

From the classification results of RCNN and its evolutionary versions on RCV1-org, RCV1-noise, and RCV1-drift, we can consistently conclude the efficacy and stability of proposed methods as analyzed in section 4.3. Moreover, compared with the results on RCV1-org and RCV1-noise, we can see that the standard RCNN is very sensitive to noise, and the accuracy declines sharply as the noise ratio σ increases. In contrast, by incorporating historical information to current decision, the evolutionary versions RCNN-TS and RCNNDP are quite robust against noise. Compared with the results on RCV1-org and RCV1-drift, it is easy to find that data drift greatly affects the performance of text classification. When there is a stronger drift between different time steps, the standard RCNN performs much worse, especially near the inflection point of the data drift curve with maximum drift (time step = 6). Whereas, RCNN-TS and RCNNDP can still achieve meaningful results, which proves that the proposed methods are quite effective to reduce the impact of drift and to reflect the long-term data changes.

It is worth mentioning that RCNN-TS does not perform as well on the RCV1-drift dataset as it does on the RCV1noise dataset. We believe the main cause is that the temporal smoothness framework focuses on smoothing the classifiers by preventing large deviation of model parameters, thus it is more robust against the data fluctuations. However, the downside is it may also become insensitive with the data drift. In contrast, the diachronic propagation framework achieves a richer compositionality by incorporating the historical impact into currently learned features through diachronic connections, which is more beneficial to adaptively reflecting the long-term changes while maintaining robustness to noise.

Acknowledgments

The corresponding author is Jianxin Li. This work is supported by China 973 Fundamental R&D Program (No.2014CB340300) and NSFC program (No.61472022, 61421003). The co-author Yangqiu Song is supported by China 973 Fundamental R&D Program (No.2014CB340304) and the Early Career Scheme (ECS, No.26206717) from Research Grants Council in Hong Kong.