Collaborative Place Models

1 Introduction 1

During the last couple of years, positioning devices that measure and record our locations have become ubiquitous. The most common positioning device, the smartphone, is projected to be used by a billion people in the near future [Davie, 2012]. This surge in positioning devices has increased the availability of location data, and provided scientists with new research opportunities, such as building location-based recommendation systems [Hao et al., 2010; Zheng et al., 2010; 2009], analyzing human mobility patterns [Brockmann et al., 2006; Gonzalez et al., 2008; Song et al., 2010], and modeling the spread of diseases [Eubank et al., 2004].

A fundamental problem underlying many location-based tasks is modeling users' spatiotemporal patterns. For example, a navigation application that has access to traffic conditions can warn the user about when to depart, without requiring any input from the user, as long as the application can accurately model user's destination. Similarly, a restaurant application can provide a list of recommended venues, even reserve them while space is still available, by modeling the probable locations the user might visit for lunch.

One of the challenges in building such models is the sparsity of location datasets. Due to privacy considerations [Wernke et al., 2012] and high energy consumption of positioning hardware [Oshin et al., 2012], location datasets con-

1 Supplements are available at http://www.berkkapicioglu.com.

David S. Rosenberg

YP Mobile Labs

david.davidr@gmail.com

Tony Jebara

Columbia University jebara@cs.columbia.edu

Number of observations per user (dense dataset) Mean: 1172.2, Median: 1114.0

Number of observations per user (sparse dataset) Mean: 107.3, Median: 74.0

0

200

400

600

800

1000

Number of observations

Figure 1: Number of observations per user. The left plot represents a dense mobile carrier dataset and the right plot represents a sparse mobile ad exchange dataset. The dense dataset has 15 times more observations per user than the sparse dataset.

tinue to grow larger while remaining relatively sparse per user. For example, most mobile phone operating systems only allow applications to log users' locations when the application is active, but not when it is running in the background. As a result, many location datasets have very little information per user. In Figure 1, we compare a sparse dataset that is retrieved from a mobile ad exchange and a dense dataset that is retrieved from a cellular carrier. The sparse dataset has 15 times less observations per user than the dense dataset, which makes it harder to infer its spatiotemporal patterns.

In the past, there has been some work on spatiotemporal modeling as it pertains to location prediction. Cho et al. [Cho et al., 2011] proposed a two-state mixture of Gaussians that leverages the social relationships between users, but they limited their model to only represent "home" and "work". Gao et al. [Gao et al., 2012] designed a Markov model that takes temporal context into account in order to predict the user's location in the immediate future. De Domenico et al. [De Domenico et al., 2012] presented a location prediction algorithm where the dataset consisted of tens of thousands of GPS observations, collected every few minutes and over the span of a year. Their algorithm exploited the high density of the location dataset, as well as the social relationships between users, by predicting the user's geographic coordinates in the immediate future based on the similarities between the user's most recent trajectory and all of his previous trajectories.

In most of these studies, the proposed models were designed for near-term forecasts, and they relied on making

Number of users

4000

3000

2000

1000

0

predictions based on the most recent observations. However, there are many real-world applications where the test example and the most recent training example are temporally apart, and for all purposes, statistically independent. For such predictions, a model that relies on the most recent observations would not suffice; instead, the model would need to make predictions based on the user's global spatiotemporal patterns.

In addition to the work listed above, researchers have also studied spatiotemporal modeling as it pertains to the detection of significant places and routines. Eagle and Pentland [Eagle and Pentland, 2009] applied eigendecomposition to the Reality Mining dataset, where all locations were already labeled as "home" or "work", and extracted users' daily routines. Farrahi and Gatica-Perez [Farrahi and Perez, 2011] used the same dataset, but extracted the routines using Latent Dirichlet Allocation (LDA) instead of eigendecomposition. Liao et al. [Liao et al., 2005; 2007] proposed a hierarchical conditional random field to identify activities and significant places from the users' GPS traces, and since their algorithm was supervised, it required locations to be manually labeled for training. In contrast to previous work, our model does not require labeled data; instead, it relies only on user IDs, latitudes, longitudes, and time stamps.

In this paper, we propose a new Bayesian probabilistic graphical model, called Collaborative Place Model (CPM), which recovers the latent spatiotemporal structure underlying unsupervised location data by analyzing patterns shared across all users. CPM is a generalization of the Bayesian Gaussian mixture model (GMM), and assumes that each user is characterized by a varying number of place clusters, whose spatial characteristics, such as their means and covariances, are determined probabilistically from the data. However, unlike GMM, CPM also assigns users weakly similar temporal patterns; ones which do not force different users to have the same place distribution during the same weekhour.

The spatiotemporal patterns extracted by CPM are helpful in leveraging both sparse and dense datasets. In case of sparse data, the model infers a user's place distribution at a particular weekhour, even if the user has not been observed during that weekhour before. In case of dense data, sampling bias usually yields fewer observations for certain hours (e.g. users make more phone calls during day time than after midnight), and the model successfully infers the user's behavior during these undersampled hours. In both cases, the model combines the globally shared temporal patterns with user's own spatiotemporal patterns and constructs a customized, complete, and time-dependent profile of the user's locations.

Aside from its quantitative benefits, CPM also provides qualitative insights about the universal temporal patterns of human populations. Even though the model is given no prior information about the relationship between weekhours, it successfully extracts temporal clusters such as the hours spent during morning commute, work, evening commute, leisure time after work, and sleeping at night.

The paper proceeds as follows. In Section 2, we provide a formal description of CPM. In Section 3, we derive the inference algorithms. In Section 4, we demonstrate our model on two real location datasets. We conclude in Section 5.

2 Collaborative Place Model

In this section, we provide a formal description of CPM and describe its generative process. CPM comprises a spatial part, which represents the inferred place clusters, and a temporal part, which represents the inferred place distributions for each weekhour. The model is depicted on the right side of Figure 2.

The temporal part of CPM assumes that, for each user u and weekhour w, the corresponding place distribution is a convex combination of F factorized place distributions, each of which is represented by θfu . These factorized place distributions are dependent on the user, but they are independent of the weekhour. In contrast, the coefficients of the convex combination, represented by γw, are shared across all users. Using this factorization, CPM combines global temporal patterns with user-specific spatiotemporal patterns and infers each user's place distribution even for weekhours where the user has not been observed before. Furthermore, by not restricting each user to have the same number of places or each weekhour to have the same distribution over places, CPM allows a realistic and flexible representation of the users' location profiles.

The flexible temporal representation provided by CPM turns out to be essential for our problem. Early in the project, we have built a simpler prototype, depicted on the left side of Figure 2, which constrained all users to have the same weekhour distribution. However, it performed even worse than the baseline model with respect to the usual metrics (i.e. held-out log-likelihood), so we abandoned it. In contrast to this prototype, CPM allows us both to share temporal information across users and to provide a more flexible temporal representation for each user.

Let u represent a user, ranging from 1 to U, and let f represent a factor index, ranging from 1 to F. For each user u and factor index f, let θfu ∈ RKu denote the Dirichlet random variable that represents the corresponding factorized place distribution, where Ku denotes the number of places for each user u. Intuitively, θfu ∈ RKu describes the building blocks of user's place preferences. Furthermore, let w denote a weekhour, ranging from 1 to W. The Dirichlet random variable γw ∈ RF denotes the factor weights, which when combined with the user's factorized place distributions, yields the user's place distribution for weekhour w.

At a high level, the generative process proceeds as follows. The variable γw generates yu,w,n, the factor assignment for user u and observation n at weekhour w, and the factor assignment generates the place assignment zu,w,n from the factorized place distribution θyu,w,n u . The place assignment is in turn used to sample the observed coordinates ℓu,w,n from the corresponding place cluster.

The place clusters, whose means and covariances are unique to each user, are modeled by the spatial part of CPM. Intuitively, we expect each place cluster to correspond to locations such as "home", "work", and "gym". Given a user u and a place index k, each place cluster is characterized by a bivariate normal distribution, with mean φku and covariance Σku . The observed coordinates ℓ are considered to be noisy observations sampled from these place clusters.

Our model uses conjugate priors because of the computational advantages they provide in Bayesian inference. For the random variables θfw and γw, the prior is a symmetric Dirichlet with concentration parameter α > 0, where DirichletK (α) denotes the K-dimensional distribution. For the random variables associated with the place clusters, φku and Σku , the prior is a normal-inverse-Wishart (NIW) distribution. Λ ∈ R2×2 is a positive definite scale matrix, ν>1 indicates the degrees of freedom, and together they define the distribution over the covariance matrix. The parameter µu is customized for each user u and is computed as the mean of the user's historical locations. The parameter puk is set such that the prior covariance of the place mean (i.e. prior covariance of φku ) is very large.

In location datasets, a user sometimes logs locations that are one-offs and are not representative of the user's regular location profile. To ensure that such outliers do not affect how the model infers the user's regular place clusters, we designate the last place, place Ku, as a special outlier place and set its covariance's prior mean (i.e. prior mean of ΣKu u ), as determined by ΛKu , to be very large. As for the covariance of regular clusters, we set the remaining scale matrices, Λ-Ku , such that each coordinate of the covariance's prior mean has a standard deviation of 150 meters. This is a reasonable size for a place cluster, as it is large enough to encapsulate both the potential inaccuracies of location hardware and the inherent noise in the users' locations, but small enough to ensure that each place cluster corresponds to a single intuitive place, such as "home" or "work".

Let N denote the normal distribution and IW denote the inverse-Wishart distribution. Let DirichletK (·) denote a symmetric Dirichlet if its parameter is a scalar and a general Dirichlet if its parameter is a vector. The generative process of CPM is described in more formal terms below. Further technical details about the distributions we use in our model can be found in the supplement.

1. For each weekhour w, draw a distribution over factors γw ∼ DirichletF (β).
2. For each user u and factor f, draw a factorized place distribution θfu ∼ DirichletKu (α).
3. For each user u and place k,
4. (a) Draw a place covariance Σku ∼ IW (Λk, ν).
5. (b) Draw a place mean φku ∼ N (µu, Σku puk ).
6. For each user u, weekhour w, and observation index n,
7. (a) Draw a factor assignment yu,w,n ∼ Categorical(γw).
8. (b) Draw a place assignment zu,w,n ∼ Categorical(θyu,w,n u ).
9. (c) Draw a location ℓu,w,n ∼ N (φzu,w,n u ,Σzu,w,n u ).

3 Inference

In this section, we derive our inference algorithm, and we present our derivation in multiple steps. First, we derive a collapsed Gibbs sampler to sample from the posterior distribution of the categorical random variables conditioned on the observed geographic coordinates. Second, we derive the conditional likelihood of the posterior samples, which we use to determine the sampler's convergence. Third, we derive formulas for approximating the posterior expectations of the non-categorical random variables conditioned on the posterior samples. Finally, in the last step, we combine all the previous derivations to construct a simple algorithm for efficient posterior inference. We state the main results below. The proofs are provided in the supplement.

In Lemmas 1 and 2, we describe the collapsed Gibbs sampler for variables z and y, respectively. Given a vector x and an index k, let x-k indicate all the entries of the vector excluding the one at index k. We assume that i = (u,w, n) denotes the index of the variable that will be sampled. First, we state the posterior probability of z.

Lemma 1. The unnormalized probability of zi conditioned on the observed location data and remaining categorical variables is

The parameters ˜ vu k , ˜µuk , ˜Λku , and ˜ puk are defined in the proof. t denotes the bivariate t-distribution and ˜mk,f u,· denotes counts, both of which are defined in the supplement.

Next, we state the posterior probability of y.

Lemma 2. The unnormalized probability of yi conditioned on the observed location data and remaining categorical variables is

where the counts ˜mk,f u,· , ˜m·,f u,·, and ˜m·,f ·,w are defined in the supplement.

In Lemma 3, we describe the conditional log-likelihoods of the posterior samples conditioned on the observed geographical coordinates. We use these conditional log-likelihoods to determine the sampler's convergence. Later in the paper, when we present the algorithm for posterior inference, we will use these conditional likelihoods to determine the algorithm's convergence. Let Γ denote the gamma function, let Γ2 denote the bivariate gamma function, and let |·| denote the determinant.

Lemma 3. The log-likelihood of the samples z and y conditioned on the observations ℓ is

where C denotes the constant terms. The counts m·,f ·,w, m·,f u,· , mk,· u,·, and mk,f u,· are defined in the supplement. The parameters ˆ vu k , ˆΛku , and ˆ puk are defined in the proof.

In Lemmas 1 and 2, we described a collapsed Gibbs sampler for sampling the posteriors of the categorical random variables. In Lemma 4, we show how these samples, denoted as y and z, can be used to approximate the posterior expectations of γ, θ, φ, and Σ.

Lemma 4. The expectations of γ, θ, φ, and Σ given the observed geographical coordinates and the posterior samples are

Counts m·,f ·,w, mk,f u,· , and m·,f u,· are defined in the supplement. Parameters ˆµuk , ˆΛku , and ˆ vu k are defined in the proof.

Finally, we combine our results to construct an algorithm for efficient posterior inference. The algorithm uses Lemmas Algorithm 1 Collapsed Gibbs sampler for CPM.

Input: Number of factors F , number of places Ku, hyperparameters α, β, ν, pk, Λk, and µu.

• 1: Initialize y and z uniformly at random.
• 2: Initialize mk,f u,· , m·,f u,·, m·,f ·,w, mk,· u,·, Suk , and P uk based on y and z.
• 3: while the log-likelihood in Lemma 3 has not converged do
• 4: Choose index i = (u,w, n) uniformly at random.
• 5: mzi,yi u,· ←mzi,yi u,· -1, m·,yi u,· ←m·,yi u,· -1, m·,yi ·,w ←m·,yi ·,w - 1.
• 6: Sample yi with respect to Lemma 2.
• 7: mzi,yi u,· ←mzi,yi u,· +1, m·,yi u,· ←m·,yi u,· +1, m·,yi ·,w ←m·,yi ·,w + 1.
• 8: Choose index i = (u,w, n) uniformly at random.
• 9: mzi,yi u,· ←mzi,yi u,· -1, mzi,· u,· ←mzi,· u,· -1, Suzi ←Suzi - ℓi, P uzi ←P uzi - ℓiℓTi .
• 10: Sample zi with respect to Lemma 1.
• 11: mzi,yi u,· ←mzi,yi u,· +1, mzi,· u,· ←mzi,· u,· +1, Suzi ←Suzi + ℓi, P uzi ←P uzi + ℓiℓTi .
• 12: Compute ˆγ, ˆθ, ˆφ, and ˆΣ using Lemma 4.
• 13: return ˆγ, ˆθ, ˆφ, and ˆΣ.

1 and 2 to implement the collapsed Gibbs sampler, Lemma 3 to determine convergence, and Lemma 4 to approximate the posterior expectations. The sufficient statistics are defined in the supplement.

4 Experiments

In this section, we demonstrate the performance of CPM on two real-world location datasets, a dense cellular carrier dataset and a sparse mobile ad exchange dataset, both of which are depicted in Figure 1.

We start by describing how we set up the experiments. Each data point consists of a user ID, a local time, and geographic coordinates represented as latitudes and longitudes. First, we check if a user has logged multiple observations during the same hour, and if so, we replace these observations with their geometric median, computed using Weiszfeld's algorithm. Since geometric median is a robust estimator, this step removes both noisy and redundant observations. Then, we sort the datasets chronologically, and for each user, split the user's data points into 3 partitions: earliest 60% is added to the training data, middle 20% to the validation data, and final 20% to the test data. After preprocessing, both datasets contain approximately 2 million data points, the dense dataset contains 1394 users, and the sparse dataset contains 19247 users. Furthermore, since the temporal gap between the training data and the test data ends up being at least a week apart, our datasets become inappropriate for models that make nearterm forecasts based on the most recent observations.

We train our model in two stages. In the first stage, we determine both the optimal number of places for each user (i.e. Ku) and the optimal setting for each spatial hyperparameter (i.e. ν, pk, Λk, and µu). To do so, we extract the spatial part of CPM into a GMM and train a different GMM for all combinations of users, number of places, and spatial hyperparameter settings. Then, for each hyperparameter setting, we iterate over all users, and assign each user to a number of place that minimizes the user's validation log-likelihood. The final spatial hyperparameter setting we output is the one that minimizes the total validation log-likelihood summed across all users.

In the second stage, we use the assignments obtained in the previous stage, train a different CPM for each non-spatial hyperparameter setting (i.e. F, α, β), and again use the validation log-likelihood to select the best model. We set the hyperparameters by choosing the number of factors from F ∈ {1, . . . , 10} and the Dirichlet parameters from α, β ∈ {0.01, 0.1, 1, 10}.

We evaluate how well our model fits the data by measuring the held-out test log-likelihood. The results for GMM and CPM are displayed in Figure 3. Since GMM is equivalent to a CPM with a single factor, the log-likelihood plots compare the held-out performance of the two models and demonstrate the advantages of temporal factorization. As the number of factors increases, the held-out log-likelihood also increases, illustrating how CPM can represent increasingly complex temporal patterns without overfitting. Once we convert log-likelihood to likelihood, we observe that CPM improves performance by 8% for both sparse and dense datasets.

An alternative way to evaluate model performance is to measure the distance between predicted coordinates and observed coordinates. Let ˆγ, ˆθ, ˆφ, and ˆΣbe the posterior expectations computed in Section 3. Both GMM and CPM can use these posteriors to estimate a maximum a posteriori (MAP) location for user u at weekhour w. In Figure 3, we use these location estimates to plot the percentage of predictions that have distance errors less than a given threshold. Again, CPM outperforms GMM, and the difference in accuracy grows as the distance threshold increases. Note that compared to evaluations based on log-likelihoods, evaluations based on point estimates do not capture the full extent of information encoded by our models, since they ignore the probabilities assigned to places other than the highest weighted ones.

The spatiotemporal patterns extracted by CPM not only fit the data well, but also provide qualitative insights about location data. In Figure 4, we plot ˆγ, which represents the time-dependent posterior weights associated with the factorized place distributions. Intuitively, we would expect these weights to capture the latent temporal patterns that are shared across all users. CPM has no prior notion of how weekhours are related to one another, nor does it have any explicit sequential constraints; nevertheless, it is able to extract these temporal patterns from raw location data alone. Furthermore, even though it looks like we haven't encoded any temporal dependencies in our model, an application of Bayes ball algorithm reveals that γw are actually dependent on one another conditioned on the observed data. In fact, we observe this temporal dependency in Figure 4.

The left plot in Figure 4 corresponds to the dense dataset, and it roughly clusters days into four groups: monday through thursday, friday, saturday, and sunday. Factor 1 approximates time spent at home, which is the dominant factor except between 8am and 8pm monday through thursday, between 8am and 11pm friday, between noon and 10pm saturday, and between 1pm and 8pm sunday. The weekday hours between 8am and 6pm, which typically correspond to work hours, are partitioned into three factors: factor 5 roughly corresponds to a morning commute, factor 4 to an evening commute, and factor 3 to the work hours in between. Leisure time after work is approximately represented by factor 2, and other than home, it is the only factor which dominates a time segment during each day: between 5pm and 8pm monday through thursday, between 6pm and 11pm on friday, between 5pm and 10pm on saturday, and between 4pm and 8pm on sunday. Factor 6 only appears during weekends and dominates couple hours in the early afternoon. All of these temporal patterns correspond to intuitive temporal clusters and they are extracted from all users in an unsupervised fashion.

The right plot in Figure 4 corresponds to the sparse dataset, and due to scarcity of information per user, CPM chooses a coarser temporal pattern: a split between work and nonwork hours with smooth transitions between them. As we will demonstrate later, this temporal factorization allows us to make predictions for weekhours where we have not observed any data.

These temporal patterns do not necessarily mean that all users are constrained to the same routine. In fact, one of the key benefits of our model compared to the earlier prototype in Figure 2 is that it allows each user a certain level of flexibility, by allowing everyone to have their own distinct factorized place distributions. In Figure 5, we show the final place distribution of an arbitrarily chosen user from the dense dataset, computed by combining the global factor weights in the left plot of Figure 4 with user's own factorized place distributions. In Figure 5, the left plot is the place distribution inferred by CPM and the right plot is the empirical place distribution computed using a GMM. The difference in the temporal patterns between left plots of Figures 4 and 5 demonstrates how CPM successfully customizes global patterns to each user. Furthermore, the distribution inferred by CPM is much smoother than the empirical distribution computed using GMM, making it easier to visually inspect the user's temporal patterns.

In Figure 6, we continue analyzing the same user. The left plot shows some of the places inferred by CPM. The circles represent the training data, the colors represent the place assignments, and the pins represent the place cluster means. A visual inspection of the temporal patterns in Figure 5 reveals that Place 1 is user's home. The right plot shows the empirical and inferred probability distributions over the weekhours, assuming that the user is already at Place 1. The empirical distribution is very noisy, and due to sampling bias, it shows that user is not at home between midnight and 8am! The distribution inferred by CPM corrects that bias.

Lastly, in Figure 7, we show the final place distribution of an arbitrarily chosen user from the sparse dataset, computed by combining the global factor weights in the right plot of Figure 4 with user's own factorized place distributions. In Figure 7, the left plot is the place distribution inferred by CPM and the right plot is the empirical place distribution computed using a GMM. In contrast to the sparse distribution computed using GMM, CPM clearly delineates the temporal cycles associated with home and work and is able to make predictions for all weekhours.

5 Conclusion

In this paper, we present the Collaborative Place Model, which recovers the latent spatiotemporal structure underlying unsupervised location data by analyzing patterns shared across all users. CPM combines population-wide inferences with user-specific ones, allows users to have different number of places or weekhours to have different distributions over places, and constructs a realistic and flexible representation of users' location profiles. We apply CPM to two real datasets, one sparse and one dense, and demonstrate how it both improves location prediction performance and provides new insights into users' spatiotemporal patterns.

For future work, we are interested in generalizing our model using the hierarchical Dirichlet process, such that training is simplified and the number of places for each user is learned more efficiently.