Predicting Activity and Location with Multi-task Context Aware Recurrent Neural Network

1 Introduction

Nowadays, location based services (LBS) have become indispensable in our daily life. The user mobility prediction, as an important role in intelligence and personalization of LBS, sheds light on POI recommendation, travel planning and targeted advertising. Besides, it is also academic valuable and industrial applicable to properly answer the question like "How to utilize large volume mobility data collected in LBS for user activity and location prediction?".

Considering that users' activity and location preferences interplay with each other, many scholars tried to figure out the relationship between users' activities and locations for improving prediction performance. Some researchers believe that users' activity purpose determines where they go [Ye et al., 2013; Liao et al., 2017], so that they firstly modeled users' activities and then predicted locations given activities. Other scholars hold the opposite opinion that users' activities are influenced by where users stay [Yuan et al., 2013; Yang et al., 2015], thus their method inferred users' activity preferences based on users' spatial information.

However, the relationship between user's activities and locations is more complicated than that one decides the other. Actually, people usually begin with a rough idea about what activities and which regions they prefer. After that, activities and spatial regions become interrelated factors for making a decision. For example, Alice wants relaxation near home after a whole day work, so she would prefer a leisure place in the neighborhood. Bob plans to have a party with friends in popular recreation centers on weekends, so he may choose a downtown restaurant or hub. From these inspirations, we introduce the spatial-activity topic to describe the interplay of users' activity and location preferences. We believe that users' activity and location preferences are decided by their latent spatial-activity topics. In the activity aspect, the topic represents high-level abstract of the activity purpose, such as work or relaxation. In the spatial aspect, the topic controls which regions users are willing to go. In above examples, "relaxation near home" and "party in recreation centers" are Alice and Bob's spatial-activity topics. What's more, two comprehensive principles of individual mobility [Liao et al., 2017] potentially apply to spatial-activity topics:

• Sequential dependency: Users' spatial-activity topics depend on previous topics. For example, a whole-day work usually follows leisure and recreation topics, rather than any laborious topics. However, the sequential dependency could be vanished, due to the check-in data sparsity [Feng et al., 2015].
• Temporal regularity: Users' spatial-activity topics are influenced by the specific temporal context. For example, party topics are usually performed at weekends instead of work hours.

From these two principles, we develop our modeling techniques. For modeling sequential dependency, gated Recurrent Neural Networks (RNN), such as Long Short Term Memory (LSTM) and Gated Recurrent Unit (GRU), have achieved the best performance in many sequence model applications [Yao et al., 2013; Graves et al., 2013]. However, there are some technical challenges for integrating temporal context into RNNs. When check-ins are very sporadic and sparse, the sequential feature should be "forgotten" due to vanishing of sequential dependency while the temporal context should play an active role for prediction. Thus it is infeasible to feed sequential and temporal contexts together into gated RNN and control them with a single sigmoid gate.

Motivated by these findings, we propose a Multi-task Context Aware Recurrent Neural Network (MCARNN) to leverage the spatial-activity topic for improving the activity and location prediction. As the activity and location prediction share the same inputs and are both influenced by spatialactivity topics, we adopt a multi-task learning neural network to predict users' activities and locations simultaneously. To integrate the context information and sequential pattern, and elevate sequential and temporal regularity of spatial-activity topics, we propose a novel Context Aware Recurrent Unit (CARU) as hidden layer unit. CARU calculates the sequential hidden state to capture the sequential dependency and takes the temporal context as an extra input. After a nonlinear activation function, the temporal context is integrated with sequential hidden state dynamically by a sigmoid gate. Through evaluation on real-world public datasets, the proposed model shows a considerable improvement of prediction performance, demonstrating the validity and superiority of spatial-activity topics and CARU.

Our main contributions are summarized as follows:

• We introduce the spatial-activity topic to capture the interplay of user's activity and location preferences. In addition, a multi-task neural network utilizing the spatialactivity topic is leveraged to improve the activity and location prediction.
• We propose a novel Context Aware Recurrent Unit to integrate context information and sequential pattern dynamically.
• Experimental results demonstrate that proposed model significantly outperforms state-of-the-art methods. Besides, a case study vividly explain the learned spatial activity topics.

2 RelatedWork

2.1 Mobility Prediction

Human mobility prediction has drawn great attentions for decades. Scholars handled this task with two-broad-category approaches: temporal context model and sequential model. The temporal context model focused on users' behavior under a certain time information. A time-aware Gaussian Mixture model was proposed to combine the periodic behavior and social relationship for mobility prediction [Cho et al., 2011]. RCH (Regularity, Conformity and Heterogeneous) model [Wang et al., 2015] predicted locations at specific time, considering both regularity and conformity. As for sequential modeling, the fallback Markov achieved the best performance on location prediction of WiFi mobility data [Song et al., 2004]. Recently, rather than merely modeling sequential pattern, many extensions have been developed for exploiting additional information, such as Factorizing Personalized Markov Chain [Cheng et al., 2013] and Personalized Ranking Metric Embedding [Feng et al., 2015]. However, the user activity preference, an important part of their mobility that affecting location preference, was ignored in above works.

Viewing that users' activity and location preferences interplay with each other, more and more scholars leveraged both activity and location information of check-ins for mobility prediction. Some researchers believed that activity purpose controls location preference, so that they modeled users' activities at first and then predicted locations given specific activities [Ye et al., 2013; Liao et al., 2017]. However, this kind of assumption is simplistic to model the interplay of user's activity and location preference. W 4 (Who, When, What and Where) model [Yuan et al., 2013] and Periodic & Social Mobility Model (PSMM) [Cho et al., 2011] introduced "spatial temporal topic" and user's "latent state" respectively. In PSMM, user's "latent states" are spatial regions without regard to the activity information. In W 4 model, the "spatial temporal topic" represents user's activity preference under specific spatial and temporal contexts. In contrast, our proposed spatial-activity topic involves both activity and spatial aspects, which is a more reasonable way to capture the complex relationship between user's activities and locations.

2.2 Recurrent Neural Networks

Recurrent Neural Networks have achieved great success in many sequential applications, such as natural language processing [Yao et al., 2013], speech recognition [Graves et al., 2013], and GPS trajectories modeling [Wu et al., 2017]. Most RNNs are designed for the fine-gained sequential data and assumes that elements of nearby time steps are correlated, which are not applicable for the sporadic and sparse checkin sequence. JNTM (Joint Network and Trajectory Model) [Yang et al., 2017b] and ST-RNN (Spatial Temporal RNN) [Liu et al., 2016] applied RNNs as mobility models on checkin data. These two models ignored the impact of the temporal context and failed to integrate activity information. SERM (Semantics-Enriched Recurrent Models) [Yao et al., 2017] captured temporal regularity, activity semantics and user preference in a unified RNN model. SERM took sequential context (i.e. user's last location and acitivity) and temporal information together into LSTM and control them with a single input gate. However, when check-ins are very sporadic and sparse, sequential and temporal contexts should be controlled separately. Thus SERM is not a feasible method for modeling the spatial-activity topic.

3 ProblemFormulation

Our objective is to predict future locations and activities of users. Without loss of generality, we normalize the activity information into the keyword representation. Given the activity keyword set A = {a(1) , a(2) , . . . , a(|A|) }, user set U = {u(1) , u(2) , . . . , u(|U|) } and location set L = {l(1) , l(2) , . . . , l(|L|) }, the check-in data can be defined as a quadruple r = (u, l, a, t), indicating that user u visits location l for activity a at time t. Here, for the ease of calculation, we discretize continuous time t to hour of day and day of week. With these notations, our problem can then be formulated as: Our goal is to predict user u's next location ln and next activity an, given the next check-in time tn and the historical check-in sequence τ u n-1 = {ru 1 , ru 2 , . . . , ru n-1 } .

4 Model

4.1 Overview

In this section, we introduce the Multi-task Context Aware Recurrent Neural Network (MCARNN). The overall framework is presented in Fig. 1. We employ a multi-task learning framework to capture the spatial-activity topic in shared hidden layers for activity and location prediction.

Considering the sequential dependency and temporal regularity of spatial-activity topics, we extract five features from check-in sequence: the user u, the latest activity an-1, the latest location ln-1, the current time tn and the timespan sn. Here, timespans are measured by hours with a threshold. If the timespan of two check-ins is larger than the threshold, we think these check-ins have no sequential dependency and denote this timespan as "infinity". Then, all these discrete features are mapped into dense continuous vectors as embedding, denoted as u, an-1, ln-1, tn, sn.

Based on these features, we adopt gated RNN as the shared hidden layer for modeling spatial-activity topics. As we have discussed, it is infeasible to take all five features together as the input of existing gated RNNs. Thus we decompose input features into sequential features xSn-1 (linear combination of u, an-1 and ln-1) and temporal context xTn (linear combination of u, tn and sn). Then we propose a novel Context Aware Recurrent Unit (CARU) to integrate sequential feature xSn-1 and temporal context xTn dynamically. Details of CARU are shown in Sec. 4.2.

With the CARU layer, we capture the spatial-activity topic, which is then fed into task-specific layers. After task-specific GRU and softmax layers, we get the activity prediction and location prediction results, i.e. an and ln. In addition, to exploit the geo-distance of locations and the correspondence of locations and activity keywords, we employ graph embedding methods [Perozzi et al., 2014; Tang et al., 2015] to learn better embedding of locations and activity keywords. Embedding learning benefits the forward calculation and backward derivation of our model, so that we adopt it as a auxiliary task of the activity and location prediction. Details of the embedding learning will be discussed in Sec.4.3.

4.2 Context Aware Recurrent Unit

As mentioned before, the spatial-activity topics are influenced by not only the sequential feature but also the temporal context. What's more, the sequential feature and temporal context cannot be controlled by a single sigmoid gate. For example, when timespans of consecutive check-ins are as long as several days, the sequential feature should be "forgotten" due to decayed sequential dependency, while the temporal context should play an active role for prediction. Therefore, we propose the Context Aware Recurrent Unit (shown in Fig. 2) to integrate temporal and sequential contexts dynamically.

Specifically, to capture the sequential pattern, we calculate the sequential hidden state as follows:

where n denotes the time step, h is the hidden state of CARU, hS is called as sequential hidden state, and i, f are sigmoid gates. Here, W, U, V and b represent the weight matrices and bias vectors, ∗ represents the element-wise product of two vectors, σ(·) denotes the sigmoid function and g(·) is the activation function (the hyperbolic tangent function in our work). The calculation of the sequential hidden state is similar to the calculation of memory state of LSTM cell. Here, the major difficulty in our problem is not the long-term dependency but the vanishing of sequential dependency. Instead of the output gate in LSTM, we integrate the sequential hidden state and temporal context via a sigmoid gate iTn as follows:

The sigmoid unit iTn sets the weight of the sequential hidden state and the temporal context to a value between 0 and 1. Especially, the proposed gated RNN cell degenerates to a simplified LSTM cell when iTn = 0, or a common non-linear neuron with temporal context as the input when iTn = 1. Note that when calculating spatial activity topic with time step n, the sequential feature xS only involves time step n-1, while the temporal context xT depends on time step n. That is why we call xT as "context". Generally, the context can be any information associated with time step n.

4.3 Embedding Learning

Representing similar items as similar embedding vectors is conducive to the forward calculation and the backward derivation of neural network [Mikolov et al., 2013]. To learn the location embedding, we leverage both the geo-spatial distance and activity semantic of locations to represent the location similarity. We build a location-location graph Gl. Two locations are connected if they share same activity keywords or they are closer than a distance threshold. Then we employ the graph embedding method [Perozzi et al., 2014], which generates "sentences" by random walk on the graph and applies Skipgram [Mikolov et al., 2013] to learn embedding.

The similarity of activity keywords is difficult to define. Instead, we map activity keywords to correlative embedding vectors with corresponding locations in the same vector space, which is beneficial to learning shared parameters. We construct a bipartite activity-location graph Ga with the corresponding of activity and location as edges. A bipartite network embedding method [Tang et al., 2015] is adopted for learning activity embedding. This method randomly selects a activity keyword as "input word", and locations linked to this activity as "context" in each step for implementing Skipgram.

5 Alternative Training

The overall loss of MCARNN is the total loss of the activity prediction, location prediction and embedding learning.

where J is the overall loss, Ja and Jl are the losses of activity and location prediction, JGl and JGa are the losses of the auxiliary task, and λ1, λ2, λ3 are the weighting factors. For activity and location prediction tasks, the training goal is minimizing the divergence between the predicted distribution and the true distribution. Thus we adopt Ja and Jl as the crossentropy loss. Then we can minimize Ja and Jl by mini-batch Stochastic Gradient Descent (SGD). As for the auxiliary embedding learning task, we follow the training process of the article [Yang et al., 2017a], defining the loss of Skipgram models with the negative sampling [Mikolov et al., 2013] and minimizing it with Adam [Kingma and Ba, 2014].

Because the input, loss function and optimizer of the auxiliary task are different with those of major tasks, we perform an alternative training algorithm shown in Alg. 1. The weighting factors λ1, λ2 and λ3 are approximated by sampling one loss function to update from a categorical distribution with probability p1, p2 and p3 in each step, where pi = λi/ ∑j λj. When optimizing Ja and Jl, we generate a batch of check-in sequences and adopt the SGD with decayed learning rate α. When optimizing JGl and JGa , we sample a batch of (w, c) for Skipgram model from locationlocation graph and activity-location graph, and update parameters with Adam algorithm. Here, w and c are both locations in location-location graph Gl, while w is activity and c is location in activity-location graph Ga.

Algorithm 1 Alternative Training of MCARNN

Input: Ba,Bl,BG, p1, p2, p3, α 1: repeat 2: Sample op fromCat{a : p1, l : p2, G : p3} 3: if op = a then 4: Generate a check-in batch Ba with size Ba 5: for ϑ in {θa , θ, u, a, l, t, s} do 6: ϑ←ϑ-α ∗ ∂Ja ∂ϑ 7: end for 8: else if op = l then 9: Generate a check-in batch Bl of with size Bl 10: for ϑ in {θl , θ, u, a, l, t, s} do 11: ϑ←ϑ-α ∗ ∂Jl ∂ϑ 12: end for 13: else 14: Sample a batch BG for Skipgram with size BG 15: for ϑ in {a, l, φN } do 16: Compute ∆ϑ by Adam step 17: ϑ ← ϑ + ∆ϑ 18: end for 19: end if

6 Experiments

6.1 Experiment Settings

Datasets

We evaluate our model on public Foursquare check-in datasets collected from two big cities, New York (NYC) and Tokyo (TKY) [Yang et al., 2015]. The check-ins last from April 2012 to February 2013. We take the 400 categories of POIs in Foursquare 1 as activity keywords. The overall statistics is shown in Table 1. In following experiments, for each user, we take the first 80% check-ins as the training set, the latter 10% as the evaluation set, and the last 10% as the validation set for the hyper-parameters study.

Metrics

We adopt three metrics to evaluate the performance of our model. Accuracy of top K (Acc@K) is the percentage of accurate predictions for a list of predictions with length K. Mean Average Precision of top K (MAP@K) is a widely used global evaluation for ranking task. Negative Log-Likelihood (NLL) measures the likelihood between predicted distribution and the true distribution. To make results more convincing, we repeat each experiment 10 times and take the average value of metrics into comparison.

Baselines

We compare the MCARNN model with following baselines:

1 http://developer.foursquare.com/categorytree

• MF. Most Frequent method assigns the most frequent activity and location of user u at time t as prediction.
• CAH. Context-Aware Hybrid model [Liao et al., 2017] predicts activities firstly and then predicts locations given activities.
• ST-RNN. Spatial Temporal RNN [Liu et al., 2016] is a RNN model for location prediction based on check-in data without regard to user's activity preference.
• SERM. Semantics-Enriched Recurrent Models [Yao et al., 2017] is a LSTM model taking activity semantics and spatial-temporal context as inputs for location prediction.
• MTGRU. Multi-Task GRU replaces the proposed CARU with GRU as the shared hidden layer for modeling spatial-activity topics.
• SCARNN. Single-Task Context Aware RNNs predict activities or locations separately with the same inputs and hidden layers as proposed model.

Parameter settings

The weights in RNN are initialized with Xavier initialization [Glorot and Bengio, 2010]. Embeddings and initial hidden state are initialized with a random initializer over uniform distribution (0.1, -0.1). The learning rate α starts with 2.00 and decays to one quarter every 4 epochs until it is less than 0.02. We set batch sizes Ba,Bl as 16 and BG as 64. The timespan threshold is set as 48 hours and the distance threshold is set as 2km. We set the embedding size of u, a and l as the optimal hidden size 256 for convenient calculation. As the value space of time t and timespan s are much smaller, their embedding size is set to a practically effective value, 32. The setting of hidden size of RNN and weighting factors of loss function λ1, λ2, λ3 are studied in Sec. 6.4.

6.2 Results

The performance comparison by Acc@K, NLL and MAP@K is shown in Table 2. We can observe that the proposed MCARNN achieves the best result in both prediction tasks.

MF is a naive method without any insight of activity and location prediction, so that it is not surprising of getting the worst results. CAH is a two-stage method based on the intuition that the users' activity purpose determines the location preferences. Comparing with CAH, the proposed spatialactivity topic is more appropriate to leverage the interplay of users' activity and location preferences. SERM and STRNN are two RNN models for location prediction of checkins. SERM can not handle the vanishing of sequential dependency and ST-RNN ignored the temporal context and activity information. Thus our MCARNN significantly outperforms these state-of-the-art methods. Concretely, in location prediction, MCARNN shows an increase of 20.92% on the NYC dataset and 39.15% on the TKY dataset improvement of top-1 accuracy. In activity prediction, the proposed model outperforms CAH by 10% on the NYC dataset and 36% on the TKY dataset of top-1 accuracy.

The proposed model is also superior to its two variants (i.e. MTGRU and SCARNN). For one thing, as we have discussed, GRU is unsuitable for highly sparse check-in data, while the proposed CARU can handle the decayed sequential dependency and integrate the temporal context. As expected, MCARNN performs much better than MTGRU. For another, SCARNN integrates temporal context and sequential pattern by CARU. However, the hidden layers of singletask network only learn the latent regularity in single aspects, instead of spatial-activity topics. Actually, single-task networks may suffer the overfitting problem, which is illustrated by the learning curves on the NYC dataset shown in Fig. 3(a). Learning curves on the TKY dataset show similar trends thus we omit them due to the space limit. The multi-task learning fashion can not only model users' latent topics in both activity and spatial aspects, but also improve generalization because each task can be seen as a regularization for other tasks. The MCARNN-M in Fig. 3(a) is another simplified version of MCARNN without the auxiliary embedding learning task. It can be observed that the auxiliary representation learning task has a sizable promotion of convergence rate for location and activity prediction.

Table 3: Effect of λ1, λ2, λ3

6.3 Parameter Study

The size of hidden state determines the capacity of RNN. The performance comparison with the varying hidden size is displayed in Fig. 3(b). When the hidden layer size grows from 64 to 256, the model capacity increases with validation loss becoming smaller gradually. However, when the hidden layer size grows from 256 to 1024, overfitting occurs and validation loss becomes larger gradually due to excessive model capacity. Thus we set the hidden layer size as 256.

Alternate training can easily become biased towards a specific task, thus we need to carefully select the weighting factors λ1, λ2 and λ3. In this study, we fix the λ1 as 1, and adjust λ2, λ3 one after the other. Table 3 shows the performance of the location prediction NLL, activity prediction NLL and total NLL on the NYC validation set. For one thing, as the λ2 decrease, the location prediction performance gets better. However, when λ2 is smaller than 0.5, the model become biased to the location prediction task so that the activity prediction performance degenerates dramatically. For another, we fix the λ2 as 0.5 and increase λ3 from 0 to 0.2. With the embedding learning task, the location prediction performance is further enhanced. When λ3 comes up to 0.1, the prediction performance gets even worse due to the same bias issue. Thus the best setting of λ1, λ2 and λ3 is 1, 0.5 and 0.05.

6.4 Case Study of Spatial-Activity Topic

To intuitively interpret the spatial-activity topic, we select one random user with fruitful check-ins in NYC dataset as an example. We feed all this user's check-ins into a fine-trained MCARNN, and cluster outputs of the CARU layer with Kmeans, representing spatial-activity topics of this user.

Figure 3(c) shows the clustering result with dimension reduction by Principal Components Analysis. It is obvious that the appropriate cluster number is three. Figure 3(d) shows the spatial distribution of these topics. The percentage of activity categories of each topic is shown in Fig 3(e). Here, we classify activities by 9 root categories in Foursquare: transport, food, residence, college, nightlife, arts, shop, recreation and professional. It is difficult to exactly understand this user's behavior from only one aspect. From the spatial aspect, topic 1 and topic 2 check-ins locate in overlapped areas, while show a great difference in activity distribution. From the activity aspect, topic 2 and topic 3 are both about outdoor categories, but locate in completely different regions. In contrast, considering both two aspects, these topics can easily be interpreted as "stay in the residence", "recreation in the neighborhood" and "travel to Manhattan". This is why we state the spatialactivity topic is a reasonable way to capture the complex relationship between user's activities and locations.

(d) Spatial Distribution of Topics

7 Conclusion

In this paper, we have proposed a novel activity and location prediction method called MCARNN. The multi-task learning fashion is implemented for utilizing the spatial-activity topics. To integrate the temporal context and sequential pattern, we introduce a Context Aware Recurrent Unit in the shared hidden layer. The experimental results on two public datasets show that MCARNN outperforms the state-of-art methods in terms of both activity and location prediction.