Collective Prediction of Individual Mobility Traces with Exponential Weights

We present and test a sequential learning algorithm for the short-term prediction of human mobility. The experts are individual sequence prediction algorithms constructed from the mobility traces of 10 million roaming mobile phone users in a European country. Average prediction accuracy is significantly higher than that of individual sequence prediction algorithms, namely constant order Markov models derived from the user's own data, that have been shown to achieve high accuracy in previous studies of human mobility prediction. The algorithm uses only time stamped location data, and accuracy depends on the completeness of the expert ensemble, which should contain redundant records of typical mobility patterns. The proposed algorithm is applicable to the prediction of any sufficiently large dataset of sequences. The problem of algorithmic prediction of human mobility has received significant attention in the literature in recent years, for its potential applications and its inherent theoretical value. The problem is posed as asking for a prediction of the short-term future location of an individual, given his or hers previous locations and possibly other side information. One can distinguish the algorithms that have been studied in the mobility prediction literature in two classes. On one hand, we have algorithms that use only the single user's past locations, without any other information, to estimate the next location. This individual sequence prediction is closely related to lossless compression of sequential data [1-3]. The other category comprises methods that take advantage of data beyond the user's own past locations (e.g. the network of connections between devices as a proxy of the user's social interactions [4]).