# estimating_latent_people_flow_without_tracking_individuals__cfa23c02.pdf

Estimating Latent People Flow without Tracking Individuals

Yusuke Tanaka1, Tomoharu Iwata2, Takeshi Kurashima1, Hiroyuki Toda1, Naonori Ueda2,3

1 NTT Service Evolution Laboratories, Kanagawa 239-0847, Japan 2 NTT Communication Science Laboratories, Kyoto 619-0237, Japan 3 RIKEN Center for AIP, Tokyo 103-0027, Japan {tanaka.y, iwata.tomoharu, kurashima.takeshi, toda.hiroyuki, ueda.naonori}@lab.ntt.co.jp

Analyzing people ﬂows is important for better navigation and location-based advertising. Since the location information of people is often aggregated for protecting privacy, it is not straightforward to estimate transition populations between locations from aggregated data. Here, aggregated data are incoming and outgoing people counts at each location; they do not contain tracking information of individuals. This paper proposes a probabilistic model for estimating unobserved transition populations between locations from only aggregated data. With the proposed model, temporal dynamics of people ﬂows are assumed to be probabilistic diffusion processes over a network, where nodes are locations and edges are paths between locations. By maximizing the likelihood with ﬂow conservation constraints that incorporate travel duration distributions between locations, our model can robustly estimate transition populations between locations. The statistically signiﬁcant improvement of our model is demonstrated using real-world datasets of pedestrian data in exhibition halls, bike trip data and taxi trip data in New York City.

1 Introduction

With recent advances in wireless and mobile networks, location information of people can be recorded in a variety of spaces such as exhibition halls, shopping malls, amusement parks, and urban cities. It is important to understand people s mobility patterns in these spaces, because it provides useful knowledge for optimizing navigation systems [Huang and Gartner, 2010], travel route recommendation [Kurashima et al., 2010], location-based mobile advertising [Dhar and Varshney, 2011], urban planning [Yuan et al., 2012], and disaster management [Song et al., 2014]. For example, analyzing the routes of people helps to guide them to the locations of interest, and determine which advertisement to serve to the visitors to suit their current locations. Many statistical methods that analyze trajectory data have been proposed to understand people s mobility patterns [Gi-

Incoming count Outgoing count

Figure 1: Aggregated data targeted. Observes only incoming and outgoing counts at each location and each time step (blue). The next location of each individual is unobserved (red).

annotti et al., 2007; Monreale et al., 2009; Zhuang et al., 2017]. Trajectory data is a set of location points with time stamps for each individual (e.g., pedestrian, car, bike). However, since privacy concerns are increasing, location information of people is often aggregated, making the tracking of individuals impossible [Chow and Mokbel, 2011]. Aggregated data can also be obtained directly from people counting systems that use various sensors such as video cameras [Chan et al., 2008] and inductive-loop trafﬁc detectors [Klein, 2001]. These systems have been recently developed for low-cost and large-scale people count data collection. Giving the preference for data aggregation, existing methods that analyze trajectory data are inapplicable. Therefore, estimating latent people ﬂows, i.e., transition populations between locations, from only aggregated data is of critical importance in understanding people s mobility patterns while protecting privacy. The aggregated data considered consist of incoming and outgoing counts at each location and each time step as shown in Figure 1. For example, in an exhibition hall, we may be able to obtain only counts of pedestrians entering or leaving each event booth, and we cannot know the history of locations visited by each pedestrian. Other examples include pedestrian data for each attraction in an amusement park [Du et al., 2014], each store in a shopping mall [Senior et al., 2007], and trafﬁc data for intersections [Kumar et al., 2013]. The collective ﬂow diffusion model (CFDM) was proposed to estimate transition populations between locations from ag-

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

gregated data [Kumar et al., 2013]. CFDM is learned by maximizing a likelihood subject to constraints that represent people ﬂow conservation. The constraint states that all people who leave a location at time step t always arrive at another location at the next time step, t+1. However, this assumption is too restrictive for many real-world applications, mainly because we do not always have a large enough number of sensor devices to cover large-scale spaces: People might be moving through passages where no sensor devices are placed at an observation time step. In that case, the people are not observed in any location, and CFDM fails to estimate transition populations accurately as it assumes that everyone is in one or other of the observed locations at the next time step. The purpose of this paper is to robustly estimate unobserved transition populations between locations in practical situations, that is, the observation range is limited and some people are not observed in any location in some time periods. In order to achieve our purpose, we propose a new probabilistic model that incorporates people s travel duration between locations. This is, however, quite challenging to implement, because travel duration between locations is not present in the aggregated data, and, moreover, people are heterogeneous so travel duration depends on the individual. For example, in an exhibition hall, some people might directly visit their next location, but others might take a rest before arriving at another location; in an urban city, moving speeds might depend on the means of transport (e.g., walking, bike, car). With the proposed model, the temporal dynamics of people ﬂows are assumed to be probabilistic diffusion processes over a network, where the nodes are locations (e.g., booths and shops) and the edges are paths between these locations (e.g., passages and roads). People diffuse from node to node according to transition probabilities that depend on their locations. Since the transition populations between locations are not observed, we treat them as latent variables. Our key idea is to treat travel duration as random variable that follows a probability distribution. This enables us to capture the heterogeneity in travel duration among individuals. The distributions of travel duration are incorporated into the constraints that represent ﬂow conservation; they aim to model that people who left one location in one time step and arrived at another location after some delay. We develop an efﬁcient inference algorithm to estimate the transition probabilities, the transition populations, and the travel duration distributions. We show the effectiveness of our model on real-world datasets, pedestrian location logs from large-scale exhibition halls, and bike trip data and taxi trip data in New York City. First, we show that our model achieves high estimation performance for the transition populations between locations. Second, we show that our model precisely captures the travel duration distributions between locations. Third, by using the estimated transition populations, we show that our model can analyze the routes of pedestrians in exhibition halls that are likely to be chosen by visitors without tracking individuals. The major contributions of this paper include: We propose a probabilistic model that incorporates travel duration distributions for robustly estimating unobserved transition populations between locations from only aggregated data.

We develop an efﬁcient inference algorithm to learn the transition probabilities, the transition populations, and the travel duration distributions.

Experiments on multiple real-world datasets show that our proposed model achieves statistically signiﬁcant improvement over baseline methods.

2 Related Work

A number of works have been published recently that use the latest trends (e.g., deep learning) for analyzing aggregated data such as population or inﬂow and outﬂow at each location [Hoang et al., 2016; Zhang et al., 2017; Yao et al., 2018]. These works can predict the population or inﬂow and outﬂow in the future with consideration of some external factors (e.g., weather). They cannot, however, estimate the transition populations between locations from inﬂow and outﬂow, which is the task considered in this paper. The task of estimating the transition populations between locations is important for better understanding people s mobility patterns; for example, it is useful for ﬁnding the popular routes of pedestrians in exhibition halls. While the method of [Xu et al., 2017] can recover user trajectories given aggregated data and transition probabilities. The transition probabilities must be manually set by using other information such as distances between locations. In other words, the method cannot estimate the transition populations between locations from only aggregated data. Different from that method, our model can estimate not only the transition populations but also transition probabilities from only aggregated data. What is more, our model also enables us to estimate the travel duration distributions, a function not considered in the previous method. Collective graphical models (CGMs) [Sheldon and Dietterich, 2011] have been recently developed as a general framework for analyzing aggregated data. The models have been applied for modeling contingency tables [Sheldon and Dietterich, 2011] and bird migration [Sheldon et al., 2008]. Prior works provide efﬁcient inference techniques for CGMs based on maximum a posteriori [Sheldon et al., 2013], MCMC sampler [Sheldon and Dietterich, 2011], message passing [Sun et al., 2015], and variational Bayesian inference [Iwata et al., 2017]. The collective ﬂow diffusion model (CFDM) [Kumar et al., 2013] is the ﬁrst application of efﬁcient inference techniques developed for CGMs to the transportation domain. By maximizing a likelihood subject to constraints that represent people ﬂow conservation, this model can estimate transition populations between locations from only aggregated data [Kumar et al., 2013; Du et al., 2014]. However, CFDM does not consider people s travel duration between locations, which is important for modeling the temporal dynamics of people ﬂows. The proposed model is an extension of CFDM, and incorporates travel duration distributions into the constraints that represent ﬂow conservation. Our model can estimate the transition populations between locations with consideration of the travel duration. Therefore, our model more precisely estimates transition populations between locations than previous models. Information diffusion models are related to our work, because their main goal is to estimate latent ﬂows of a piece of

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Symbol Description V set of locations i location, i V Ei set of locations that are accessible from location i T #observation time steps N out t,i #outgoing people from location i at time step t, N out t,i 0 N in t,i #incoming people to location i at time step t, N in t,i 0 Mtij transition population who leave location i at time step t and whose next location is j, Mtij 0 θij transition probability that people leave location i and move to location j, θij 0,

j Ei θij = 1 αji parameter of travel duration distribution from location j to i, αji > 0 λ hyperparameter for controlling the penalty, λ 0

Table 1: Notation

information over a network. These models have been used for analyzing the spread of information [Rodriguez et al., 2011; Kurashima et al., 2014] and user inﬂuence [Iwata et al., 2013; Tanaka et al., 2016] over social networks. These models incorporate a continuous time distribution to model the temporal dynamics of information ﬂows, with the aim of describing the spread of information from node to node with delays over time. However, in analyzing information ﬂows, it is not necessary to consider ﬂow conservation, a critical factor in modeling the temporal dynamics of people ﬂows based on aggregated data. Our model can infer latent people ﬂows from only aggregated data by considering the ﬂow conservation constraints that incorporate travel duration distributions.

3 Problem Formulation

In this section, we detail the aggregated data considered here, and deﬁne our problem of estimating latent people ﬂows. The notations used in this paper are listed in Table 1. Aggregated data: We illustrate an example of aggregated data for the three locations in the upper part of Figure 2. The data consist of incoming and outgoing counts at each location and each time step. Let N out t,i be the count of outgoing people from location i at time step t, and N in t,i be the count of incoming people to location i at time step t. Suppose that we are given a set of outgoing counts Nout = {N out t,i |t = 0, . . . , T 1, i V} and a set of incoming counts Nin = {N in t,i|t = 1, . . . , T, i V}, where T is the number of observation time steps and V is the set of locations. The aggregated data of individuals (e.g., pedestrians, cars, bikes) can be gathered using various methods such as Wi-Fi [Musa and Eriksson, 2012], Bluetooth [Kotanen et al., 2003], and video-based people counting systems [Chan et al., 2008]. Problem: Our problem of estimating latent people ﬂows, i.e., transition populations between locations, is formulated as follows. Figure 2 illustrates the studied problem for the case of three locations. Suppose that we have a set of incoming and outgoing counts at each location and each time step. We would like to estimate the transition population between locations at each time step, Mtij, which is the number of peo-

incoming count outgoing count

location 1 location 2 location 3

time step time step time step time step

location 1 location 1

location 2 location 3 location 2 location 3 t=0 t=1

transition population

Figure 2: Illustration of the studied problem. (Upper ﬁgures) The aggregated data at each location. (Lower ﬁgures) Visualization of the estimated transition populations between locations at each time step, where arrow width is proportional to the transition population.

ple who left location i at time step t and whose next location was j. Our goal is to infer a set of transition populations M = {Mtij|t = 0, . . . , T 1, i V, j Ei}, where Ei is the set of locations that are accessible from location i; people in location i can move only to the linked locations j Ei.

4 Model We propose a probabilistic model that incorporates people s travel duration between locations for estimating unobserved transition populations between locations from only aggregated data. Modeling the travel duration between locations is expected to estimate the transition populations more robustly in practical situations, that is, the observation range is limited and some people are not observed in any location in some time periods. In the proposed model, the temporal dynamics of people ﬂows are assumed to be probabilistic diffusion processes over a network, where the nodes are locations and the edges are paths between these locations. If the network structure such as road networks or a set of neighbor information is unknown, our model works by assuming a complete graph among locations. We assume that people diffuse from node to node in accordance with location-dependent transition probabilities. Let θij 0 be the transition probability that people leave location i and move to location j, where j Ei θij = 1. Given the outgoing count N out t,i and the transition probabilities θi = {θij|j Ei}, transition population Mti = {Mtij|j Ei} is given by the following multinomial distribution,

P(Mti|N out t,i , θi) = N out t,i ! j Ei Mtij!

j Ei θMtij ij . (1)

Since we cannot obtain the tracking information of individuals in our aggregated data setting, Mti is unobserved. Therefore, we treat it as a latent variable. Transition population

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Mti satisﬁes the following two relations that represent outgoing and incoming ﬂow conservation:

N out t,i =

j Ei Mtij, (2)

τ=0 F( t,τ; αji)Mτji. (3)

The outgoing ﬂow conservation (2) indicates that the sum of people leaving location i at time step t equals the observed outgoing count at the same time step. The incoming ﬂow conservation (3) indicates that the weighted sum of people leaving location j before time step t equals the observed incoming count at time step t. Weight F( t,τ; αji) is travel duration probability, which is the probability that people who left location j at time step τ arrive at location i at time step t. Here, t,τ = t τ is travel duration and αji is a parameter of the probability distribution. Details of F( t,τ; αji) are given in the following paragraphs. The travel duration is treated as a random variable that follows the probability distribution; it is not a point estimate. This enables us to capture the heterogeneity in travel duration among individuals. To derive the travel duration probability F( t,τ; αji), we ﬁrst introduce continuous travel duration distribution f( ; αji) as the probability density function of travel duration from location j to i given parameter αji, where > 0 is a continuous random variable. Note that our model does not depend on the particular choice of the travel duration distribution. The travel duration probability F( t,τ; αji) is calculated by the following integral of f( ; αji) over the interval from t,τ 1 to t,τ:

F( t,τ; αji) = t,τ

t,τ 1 f( ; αji)d . (4)

Though our model can use any distribution as f( ; αji), for simplicity we consider the well-known one-parameter distribution, i.e., Rayleigh distribution, which is widely used for assessing the duration time in various ﬁelds such as user modeling [Wang et al., 2008] and information diffusion modeling [Rodriguez et al., 2011]. Figure 3 illustrates an example when using the Rayleigh distribution. The travel duration distribution is as follows:

f( ; αji) =

α2 ji exp ( 2

the red line in Figure 3. Here, αji > 0. The travel duration probability is given by

F( t,τ; αji) = exp ( ( t,τ 1)2

) exp ( ( t,τ)2

(6) the red area in Figure 3: The probability that people who left location j at time step τ arrive at location i at time step t.

5 Inference Given outgoing counts Nout and incoming counts Nin, we estimate the latent transition populations M, the transition

travel duration Δ

Figure 3: Travel duration probability from location j to i, where t,τ is the time difference between outgoing time τ and incoming time t. The gray vertical lines are spaced by unit time steps.

probabilities Θ = {θi|i V}, and the parameters of travel duration distributions A = {αji|j V, i Ej} by maximizing the likelihood with the ﬂow conservation constraints. The log-likelihood of M is given by

log P(M|Nout, Θ)

( log Mtij! + Mtij log θij )

( (1 + log θij)Mtij Mtij log Mtij ) , (7)

where log Nti! is omitted since it does not depend on M, and we employ Stirling s approximation, log n! n log n n, in order to calculate log Mtij! efﬁciently [Sheldon et al., 2013]. The parameters are estimated by maximizing the approximate log-likelihood (7) subject to constraints (2) and (3). The constraints might not strictly hold in real-world data, because the observations are noisy. To handle noisy observations, we treat the constraints as soft constraints, where the squared difference between the leftand right-hand sides in each of (2) and (3) are minimized. Then, the objective function to be maximized is described as follows:

J (M, Θ, A)

( (1 + log θij)Mtij Mtij log Mtij )

2 N out t,i

j Ei Mtij 2

2 N in t+1,i

τ=0 F( t+1,τ; αji)Mτji 2 ]

Here, λ 0 is a hyperparameter that controls the penalty for violating the constraints and is the Euclidean norm. We update each parameter M, Θ and A alternately as described in the following paragraphs. Update of M: Given current estimates ˆΘ and ˆA, we arrive

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Algorithm 1: Inference procedure for our model.

Input : Nin, Nout, V, {Ei}i V, T, λ Output: M, Θ, A 1: Initialize M, Θ, A 2: repeat 3: Update M by solving (9) 4: for i V do 5: for j Ei do 6: Update θij by (10) 7: end for 8: end for 9: Update A by solving (11) 10: until Convergence

at the following optimization problem:

maximize M J (M, ˆΘ, ˆA)

subject to Mtij 0, t = 0, . . . , T 1, i V, j Ei. (9) We solve the optimization problem by using the L-BFGS-B method [Byrd et al., 1995]. Update of Θ: The estimates of Θ are obtained in closed form by maximizing (8) given current estimates ˆM as follows:

θij = T 1 t=0 ˆ Mtij T 1 t=0 j Ei ˆ Mtij . (10)

Update of A: Given current estimates ˆM and ˆΘ, we solve the following optimization problem:

maximize A J ( ˆM, ˆΘ, A)

subject to αji > 0, j V, i Ej, (11)

by using the L-BFGS-B method [Byrd et al., 1995]. We iteratively update each parameter until the value of (8) converges. Our inference procedure is shown in Algorithm 1, which always converges and guarantees that the local optima of the respective parameters are obtained by setting λ to a ﬁxed value. Validation of λ: Hyperparameter λ can be determined by the following validation procedure: (a) learn the model parameters by Algorithm 1 with each candidate value of λ; (b) predict the incoming counts at the next time step; (c) choose the value based on prediction performance in the training data. Given the preceding outgoing counts, the predicted incoming counts in location i at the next time step are given by

ˆN in t+1,i =

τ=0 F( t,τ; ˆαji)ˆθji N out τ,j . (12)

6 Experiments

6.1 Data Description We evaluated the proposed model using real-world pedestrian location logs collected in exhibition halls. The data was collected at an event that attracted large crowds, Niconico

Data Pedestrian data Bike trip data Taxi trip data Area/Date Hall 1 Hall 2 Hall 3 Hall 4 Mar. 1 Jun. 1 Mar. 1 Jun. 1 #outgoing 30,606 34,750 15,448 10,990 14,366 18,961 201,440 196,101 #incoming 30,606 34,750 15,448 10,990 14,640 19,312 204,476 199,232

Table 2: The total sum of incoming and outgoing counts

Chokaigi 2016 1, held at Makuhari Messe located near Tokyo, Japan from 10:00 to 18:00 on April 29th. The event site was composed of four exhibition halls, Hall 1, Hall 2, Hall 3 and Hall 4 with sizes of 186.3m 124.8m, 183.2m 124.8m, 127.6m 124.8m, and 190.9m 108.3m, respectively. The number of event booths, |V |, in Hall 1, Hall 2, Hall 3 and Hall 4 were 38, 27, 10, and 9, respectively. We gathered pedestrian location logs using Bluetooth beacons which were placed at each booth. The technology enables us to observe the times at which each user entered or left the observation range (at most 10 15 meters). The data consist of 3,727 mobile users who agreed to provide detailed information of location over time. The original data contains time stamps of arrival and departure at booths for each user; users can be tracked over time. Note that the tracking information of users was used only for evaluating the estimation performance for transition populations and travel duration probabilities; we did not use the tracking information in the inference process. In this experiment, we created aggregated incoming and outgoing pedestrian counts at each booth, where the time interval was 3 minutes. The number of observation time steps was 160. Ei was a set of edges assuming a complete graph for all datasets. The total sum of incoming and outgoing pedestrians at all booths in each hall are shown in Table 2. To additionally validate the performance of our model, we used two public datasets, bike trip data 2 and taxi trip data 3 in New York City. The data is a set of trip records consisting of: trip id, pickup location, dropoff location, pickup date and time, and dropoff date and time. Note that the data consist of location information only when people started and ﬁnished the trips; the trajectories during the trips are not recorded. We used the data from 8:00 to 24:00 on March 1st and June 1st, and created gridded incoming and outgoing count data, where the time interval in both datasets was 10 minutes. The number of observation time steps was 96. The grid sizes in the bike trip data and taxi trip data were 2km 2km (12 12 grid cells) and 3km 3km (18 18 grid cells), respectively. Here, we omitted grid cells if their incoming and outgoing counts were lower than a threshold. Then, bike trip data and taxi trip data held 11 and 14 grid cells, respectively. Ei was a set of edges assuming a complete graph for all datasets. The total sum of incoming and outgoing bikes/taxis at overall grid cells on each date are shown in Table 2.

6.2 Quantitative Evaluation

Transition Population Estimation We evaluated our model in terms of its performance in estimating the transition populations M. The evaluation metric

1http://www.chokaigi.jp/2016/en/ 2https://www.citibikenyc.com/system-data 3http://www.nyc.gov/html/tlc/html/about/trip record data.shtml

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Data Pedestrian data Bike trip data Taxi trip data Area/Date Hall 1 Hall 2 Hall 3 Hall 4 Mar. 1 Jun. 1 Mar. 1 Jun. 1 Proposed 1.237 0.024 1.028 0.014 0.784 0.034 0.675 0.030 0.621 0.015 0.704 0.021 0.443 0.006 0.454 0.006 CFDM 1.370 0.030 1.140 0.013 0.828 0.038 0.709 0.030 0.648 0.015 0.740 0.021 0.463 0.006 0.469 0.006 Popularity 1.751 0.012 1.594 0.013 1.180 0.019 0.848 0.025 0.724 0.016 0.790 0.021 0.510 0.009 0.520 0.008 Uniform 1.835 0.011 1.676 0.012 1.210 0.019 1.221 0.024 1.031 0.013 1.081 0.018 0.983 0.010 0.987 0.009

Table 3: NMAE L1 and standard errors for the estimation of transition populations in the real-world datasets.

is the following normalized mean absolute error (NMAE) in transition populations:

i V j Ei |M tij ˆ Mtij| i V j Ei M tij , (13)

where M tij is the true transition population leaving location i at time step t and whose next location is j; ˆ Mtij is its estimate. We compared our proposed model with the collective ﬂow diffusion model (CFDM) [Kumar et al., 2013]. Different from our model, CFDM does not consider travel duration between locations. In addition, we compared our proposed model with the following two baseline methods: Popularity and Uniform methods. Popularity assumes that people move to other locations in proportion to location popularity regardless of current locations; the estimated transition population is given by

ˆ Mtij = N out t,i

T 1 t=0 N in t+1,j T 1 t=0 j Ei N in t+1,j . (14)

Uniform estimates transition populations using a discrete uniform distribution; it assumes that people move to neighbor locations with equal probability 1/|Ei|. For our model, hyperparameter λ was set to the best value based on the validation procedure described in Section 5; λ was chosen from 0.1, 0.2, 0.5, 1, 2, and 5. We used a Rayleigh distribution for modeling travel duration distribution as shown in Section 4. Table 3 shows NMAE L1 of the proposed model, CFDM, Popularity and Uniform. For all datasets, the proposed model performed better than the other methods, and the differences between our model and CFDM were signiﬁcant (t-test, p < 0.01). We found similar results using other evaluation metrics (e.g., MAE, RMSE). The upper parts of Figure 4(a) and 4(b) provide a heatmap visualization of the transition matrix for the bike trip data (Jun.1) and taxi trip data (Jun.1), respectively. The transition matrix is the total number of bikes/taxis that moved between each pair of origin and destination locations; its elements were calculated as follows: Mij = T 1 t=0 Mtij. The true matrix is shown on the left and the estimate of our model is shown on the right. As shown, our model accurately estimated the transition populations between locations. Qualitative comparisons of the estimated transition populations in pedestrian data are described at length in Section 6.3.

Travel Duration Probability Estimation We evaluated the performance of estimating travel duration probabilities. We used the mean Kullback-Leibler (KL) divergence between the true and estimated travel duration prob-

destination

origin probability

travel duration (time step)

(a) Bike trip data (Jun. 1)

destination

origin probability

travel duration (time step)

(b) Taxi trip data (Jun. 1)

Figure 4: (Upper ﬁgures) Heatmap visualization of transition matrix. The true matrix is shown on the left and the estimate by our model is shown on the right. (Lower ﬁgures) Travel duration probability speciﬁed by white asterisk ( ) in the corresponding upper ﬁgure. Red line represents the estimated travel duration distribution.

abilities over all pairs of locations as the evaluation metric:

=1 P ( ) log P ( ) F( ; ˆαji), (15)

where P ( ) and F( ; ˆαji) are the true travel duration probability and the estimate of our model, respectively. Table 4 shows the mean KL divergence L2 of the proposed model and CFDM. In CFDM, the travel duration probability equals 1 if = 1 and 0 otherwise. As shown in Table 4, the proposed model achieved lower mean KL divergence values for all datasets. The results show that our model precisely estimated the travel duration probabilities. The lower parts of Figure 4(a) and 4(b) show visualization examples of travel duration probability, F( ; αji), speciﬁed by white asterisk ( ) in the corresponding upper heatmap. Red line represents the travel duration distribution, f( ; αji), estimated by our model. As shown, our model well estimated the travel duration distributions and so allows us to capture the heterogeneity in travel duration among individuals. As shown in Table 3 and 4, our model achieved better performance in estimating both transition populations and travel duration probabilities. These results indicate that incorporating the people s travel duration into the model is important in estimating latent people ﬂows.

6.3 Qualitative Evaluation Figure 5 visualizes the estimated pedestrian ﬂows in Hall 1 and Hall 2 from the pedestrian data. We illustrate the true pedestrian ﬂow on the left in Figure 5, and the estimates of the proposed model, CFDM, Popularity and Uniform on the

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

True Proposed CFDM Popularity Uniform True Proposed CFDM Popularity Uniform

True Proposed CFDM Popularity Uniform

Figure 5: Comparison of pedestrian ﬂow visualizations in Hall 1 and Hall 2. The true pedestrian ﬂow is shown on the left, and the estimates of the proposed model, CFDM, Popularity and Uniform on the right. Red dots represent the locations of booths, and the directed edges represent the pedestrian ﬂows. The edge widths are proportional to the total numbers of pedestrians that moved between each pair of booths.

Data Pedestrian data Bike trip data Taxi trip data Area/Date Hall 1 Hall 2 Hall 3 Hall 4 Mar. 1 Jun. 1 Mar. 1 Jun. 1 Proposed 1.629 2.243 1.492 1.841 2.656 2.560 2.109 2.033 CFDM 1.802 2.748 2.217 2.961 3.370 3.325 3.352 3.256

Table 4: Mean KL divergence L2 for the estimations of travel duration probabilities in the real-world datasets.

right in Figure 5. Here, the red dots represent the locations of booths, and the directed edges represent the pedestrian ﬂows between locations. The edge widths are proportional to the total numbers of pedestrians that moved between each pair of booths. Note that we omitted those edges whose transition populations were lower than a threshold, and bidirectional edge widths are proportional to the average of the transition populations between the pair of locations. As shown in Figure 5, the proposed model better discerned the pedestrian ﬂows than the other methods. CFDM tends to output some false ﬂows. This is reasonable because, as was explained earlier, CFDM is based on the unreal assumption that all pedestrians who left a location at one time step should arrive at another location at the next time step. In other words, CFDM fails to estimate the pedestrian ﬂows between locations when travel duration is signiﬁcant. Our model, on the other hand, could more precisely estimate the pedestrian ﬂows because it considers travel duration. The visualization results are useful for optimizing navigation systems and strategies of locationbased advertising. For example, discovering popular routes of pedestrians yields better route recommendations.

7 Conclusion This paper proposed a probabilistic model that incorporates people s travel duration between locations for estimating latent people ﬂows, i.e., transition populations between locations, from only aggregated data. Incorporating the travel duration into the model enables us to robustly estimate transition populations in practical situations, that is, the observation range is limited and some people are not observed in any location in some time periods. Since travel duration is treated as a random variable that follows a probability distribution, our model can capture the heterogeneity in travel duration among individuals. The inference algorithm presented herein allows us to infer transition probabilities, transition populations, and travel duration distributions. We used three real-world datasets, pedestrian data, bike trip data, and taxi trip data, to conﬁrm that our model can precisely estimate the transition populations between locations. Our future work is to conduct extended experiments considering temporal factors (e.g., time-of-day) and external factors (e.g., weather).

References [Byrd et al., 1995] Richard H. Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comput., 16:1190 1208, 1995. [Chan et al., 2008] Antoni B. Chan, Zhang-Sheng J. Liang, and Nuno Vasconcelos. Privacy preserving crowd monitoring: Counting people without people models or tracking. In CVPR 08, pages 1 7, 2008.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

[Chow and Mokbel, 2011] Chi-Yin Chow and Mohamed F. Mokbel. Trajectory privacy in location-based services and data publication. ACM SIGKDD Explorations Newsletter, 13(1):19 29, 2011. [Dhar and Varshney, 2011] Subhankar Dhar and Upkar Varshney. Challenges and business models for mobile location-based services and advertising. Communications of the ACM, 54(5):121 129, 2011. [Du et al., 2014] Jiali Du, Akshat Kumar, and Pradeep Varakantham. On understanding diffusion dynamics of patrons at a theme park. In AAMAS 14, pages 1501 1502, 2014. [Giannotti et al., 2007] Fosca Giannotti, Mirco Nanni, Fabio Pinelli, and Dino Pedreschi. Trajectory pattern mining. In KDD 07, pages 330 339, 2007. [Hoang et al., 2016] Minh Hoang, Yu Zheng, and Ambuj Singh. FCCF: Forecasting citywide crowd ﬂows based on big data. In SIGSPATIAL 16, pages 1 10, 2016. [Huang and Gartner, 2010] Haosheng Huang and Georg Gartner. A survey of mobile indoor navigation systems. Cartography in Central and Eastern Europe, pages 305 319, 2010. [Iwata et al., 2013] Tomoharu Iwata, Amar Shah, and Zoubin Ghahramani. Discovering latent inﬂuence in online social activities via shared cascade poisson processes. In KDD 13, pages 266 274, 2013. [Iwata et al., 2017] Tomoharu Iwata, Hitoshi Shimizu, Futoshi Naya, and Naonori Ueda. Estimating people ﬂow from spatio-temporal population data via collective graphical mixture models. ACM Transactions on Spatial Algorithms and Systems, 3(1):1 18, 2017. [Klein, 2001] Lawrence A. Klein. Sensor Technologies and Data Requirements for ITS. Artech House, 2001. [Kotanen et al., 2003] Antti Kotanen, Marko H annik ainen, Helena Lepp akoski, and Timo H am al ainen. Experiments on local positioning with bluetooth. In ICIT 03, pages 297 303, 2003. [Kumar et al., 2013] Akshat Kumar, Daniel Sheldon, and Biplav Srivastava. Collective diffusion over networks: Models and inference. In UAI 13, pages 351 360, 2013. [Kurashima et al., 2010] Takeshi Kurashima, Tomoharu Iwata, Go Irie, and Ko Fujimura. Travel route recommendation using geotags in photo sharing sites. In CIKM 10, pages 579 588, 2010. [Kurashima et al., 2014] Takeshi Kurashima, Tomoharu Iwata, Noriko Takaya, and Hiroshi Sawada. Probabilistic latent network visualization: Inferring and embedding diffusion networks. In KDD 14, pages 1236 1245, 2014. [Monreale et al., 2009] Anna Monreale, Fabio Pinelli, Roberto Trasarti, and Fosca Giannotti. Where Next: A location predictor on trajectory pattern mining. In KDD 09, pages 637 646, 2009. [Musa and Eriksson, 2012] A. B. M. Musa and Jakob Eriksson. Tracking unmodiﬁed smartphones using wi-ﬁmonitors. In Sen Sys 12, pages 281 294, 2012.

[Rodriguez et al., 2011] Manuel G. Rodriguez, David Balduzzi, and Bernhard Sch olkopf. Uncovering the temporal dynamics of diffusion networks. In ICML 11, pages 561 568, 2011. [Senior et al., 2007] Andrew W. Senior, Lisa M. Brown, Arun Hampapur, Chiao-Fe Shu, Yun Zhai, Rog erio Schmidt Feris, Ying li Tian, Sergio Borger, and Christopher R. Carlson. Video analytics for retail. In AVSS 07, pages 423 428, 2007. [Sheldon and Dietterich, 2011] Daniel Sheldon and Thomas G. Dietterich. Collective graphical models. In NIPS 11, pages 1161 1169, 2011. [Sheldon et al., 2008] Daniel Sheldon, M. A. Saleh Elmohamed, and Dexter Kozen. Collective inference on markov models for modeling bird migration. In NIPS 08, pages 1321 1328, 2008. [Sheldon et al., 2013] Daniel Sheldon, Tao Sun, Akshat Kumar, and Thomas G. Dietterich. Approximate inference in collective graphical models. In ICML 13, pages 1004 1012, 2013. [Song et al., 2014] Xuan Song, Quanshi Zhang, Yoshihide Sekimoto, and Ryosuke Shibasaki. Prediction of human emergency behavior and their mobility following largescale disaster. In KDD 14, pages 5 14, 2014. [Sun et al., 2015] Tao Sun, Daniel Sheldon, and Akshat Kumar. Message passing for collective graphical models. In ICML 15, pages 853 861, 2015. [Tanaka et al., 2016] Yusuke Tanaka, Takeshi Kurashima, Yasuhiro Fujiwara, Tomoharu Iwata, and Hiroshi Sawada. Inferring latent triggers of purchases with consideration of social effects and media advertisements. In WSDM 16, pages 543 552, 2016. [Wang et al., 2008] Longhao Wang, Yu Zheng, Xing Xie, and Wei-Ying Ma. A ﬂexible spatio-temporal indexing scheme for large-scale GPS track retrieval. In MDM 08, pages 1 8, 2008. [Xu et al., 2017] Fengli Xu, Zhen Tu, Yong Li, Pengyu Zhang, Xiaoming Fu, and Depeng Jin. Trajectory recovery from ash: User privacy is not preserved in aggregated mobility data. In WWW 17, pages 1241 1250, 2017. [Yao et al., 2018] Huaxiu Yao, Fei Wu, Jintao Ke, Xianfeng Tang, Yitian Jia, Siyu Lu, Pinghua Gong, Jieping Ye, and Zhenhui Li. Deep multi-view spatial-temporal network for taxi demand prediction. In AAAI 18, 2018. [Yuan et al., 2012] Jing Yuan, Yu Zheng, and Xing Xie. Discovering regions of different functions in a city using human mobility and POIs. In KDD 12, pages 186 194, 2012. [Zhang et al., 2017] Junbo Zhang, Yu Zheng, and Dekang Qi. Deep spatio-temporal residual networks for citywide crowd ﬂows prediction. In AAAI 17, 2017. [Zhuang et al., 2017] Chenyi Zhuang, Nicholas Jing Yuan, Ruihua Song, Xing Xie, and Qiang Ma. Understanding people lifestyles: Construction of urban movement knowledge graph from GPS trajectory. In IJCAI 17, pages 3616 3623, 2017.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)