Learning Latent Group Dynamics for Prediction of High Dimensional Time Series

"Are you going to the party?"
"Depends, who else is coming?"

Predicting the future has always been one of the ambitions of mankind. But how far along are we really from such a goal? Can machine learning finally address this long standing desire? Here I will give an overview of the Conditional Latent Tree Models (CLTM’s) that are used for predicting the evolution of high dimensional time series. Such high dimensional time series arise in social networks such as Twitter where the goal is to predict who will become friends with whom in the future so that we can make recommendations to the users before hand. Or in online education where the goal is to predict students’ performance or the rate of dropouts in order to give them constructive personalized feedback and increase the chances of their course completion. I will start by naming the challenges in such prediction problems and explain how CLTM’s address each of these challenges and what limitations they impose.
Let’s first see what is high dimensional about all these time series. Consider a Twitter network, for example. As [reported in Statistica
there are currently 302 million monthly active users in Twitter. In order to come up with good predictions of such a large network, one needs to consider the network as a whole or at least consider a subset of the whole. Performing reliable predictions in such a high dimensional setting requires a long period of observation. It is, therefore, “hard” to deal with such problems. Now let’s see what affects the evolution of such time series and how we can take them all into account for prediction.
There are 4 factors that affect the dynamics of high dimensional time series:
Group dynamics
Interdependence among the series
External covariates
State of the previous time points

To make these more clear I will give you some examples of each factor in the context of the Twitter network and students in an online course. As we know, Twitter users tend to participate in different communities. The evolution of each user’s behavior can be captured in part by the dynamics of those communities. in student learning scenarios, for instance, students may be divided into groups of strong and weak learners whose learning curves evolve differently. As for the dependence among the series, a network attendee might wonder who else is attending a social event (e.g. a party) before deciding whether to attend him or herself. Exogeneous factors that I call covariates also affect the dynamics of the series. In weekly social events, e.g., the day of week is a highly predictive factor of the attendance dynamics of the participants. In the online learning context on the other hand, students have topic specific strengths and weaknesses so the topic they are working on affect their performance. It is also very well known that consecutive time points are highly correlated in typical time series.
Conditional Latent Tree Models (CLTM’s) take into account all these effects for prediction of high dimensional time series. The figure below shows the performance of two groups of students grouped by CLTM, that represent strong and weak learners in a Psychology MOOC. The vertical axis illustrates the average performance of the students in each group and the horizontal axis shows days in the semester. The first 60 days were used for model training and the last 20 days are kept for testing. The red curve shows the actual performance of the students in each day and the black curve is the predictions of CLTM. The blue curve is the predictions made by a Chain CRF (Conditional Random Field) that does not take student groupings and their interdependence into account for prediction. Note that the degradation in its performance on the test samples is an indication of overfitting.

Now let’s get a little technical and see how CLTM accounts for the 4 factors for prediction. The interdependence among the series and the groupings are captured by a latent tree whose observed nodes are the network attendees or the students, and whose hidden nodes are the latent groupings in the data. CLTM represents the joint distribution of the observed and latent random variables which factorizes according to the latent tree structure conditioned on the covariates and previous time points. The distribution over the latent tree is given by an exponential family distribution conditioned on the covariates and previous time points. In order to see the details of the distribution and model please refer to our [arXiv submission
.
The structure of the latent tree is learned from the data using our unsupervised learning algorithm conditioned on the covariates and the previous time points. In order to give an intuition about how the algorithm evolves and introduces new hidden nodes I have provided a demo that can be accessed [here
. The nodes of the tree represent concepts covered in a [Psychology MOOC
offered in OLI stanford on Spring 2013. The structure learning algorithm starts from a [Chow Liu tree
and inserts new hidden nodes into the structure whenever needed while maintaining the structure, a tree. You can hit the play button to watch the algorithm in action. You can also zoom into different parts of the learned tree to see how relevant the concepts that are grouped together are.
Once the structure is learned, we factor the joint distribution over the learned tree and find the likelihood of the samples under the model. In order to find the best parameters that represent the evolution of the series, we use maximum likelihood techniques. Here we have latent variables in the structure, therefore, we use the expectation maximization algorithm to maximize the likelihood.
Now that we have the parameters of the model, we can input new unseen samples and report the most likely configuration of the variables as the prediction made by the model. To see the full model and its prediction results on different datasets please see our [arXiv submission
.