Interdisciplinary Workshop on Inference
Information processing in complex systems with applications to traffic forecasting
June 12th 2012
|
|
Interdisciplinary Workshop on InferenceInformation processing in complex systems with applications to traffic forecasting June 12th 2012 |
This workshop brings together researchers from statistics, statistical mechanics and machine learning interested in the development of methods and algorithms to process data emerging from complex systems. It is an informal continuation of a preceding meeting (PEPS) held in 2009 in Orsay on similar topics, at the interface between statistical physics and computer science. Some recent convergence of interest between statistical mechanics and machine learning resides in particular in the fact that mean-field methods of statistical mechanics have found their counterpart in terms of powerful message passing algorithms in machine learning. Theoretical questions concerning inverse problem, high dimensional data reduction, compression and restoration will be discussed, to confront complementary viewpoints from the statistics, machine learning and statistical mechanics communities. As a guideline, a special attention will be paid on applications concerning road traffic forecast on large scale networks.
This workshop is organized in the context of the Travesti project, supported by the grant ANR-08-SYSC-017 from the French National Research Agency (ANR).
Bayesian image modeling is given for based on a generalized sparse prior probability. Our prior include a sparsity in each interaction term between every pair of neighbouring pixels in Markov random fields. A new scheme for hyperparameter estimations is given from the standpoint of the conditional maximization for entropy in our generalized sparse prior. Moreover, the criteria of the optimal value for sparseness in interactions is also given by using the maximization of marginal likelihood. Our practical algorithm is constructed by using the loopy belief propagation.
In this presentation, I will talk about parametric estimation for Gaussian fields indexed by graphs. I will first introduce a model for covariance operators of regular fields indexed by an infinite graph G: we will build covariance operators as functions of the adjacency operator of the graph. This model seems very simple, but corresponds to a natural extension of the cases of the discrete line (G= Z), the square lattice (G= Zd) or the homogeneous tree.
From this model, observing a realization of a Gaussian field (Xi)i∈G of covariance Kθ0 (taken in a parametric model), we can estimate θ0 consistently by a maximum likelihood method. Furthermore, the likelihood contrast can be approximated following Whittle's ideas, leading to another consistent estimator.
As in the case of Zd, we need further assumptions on the graph to build a kind of tapered periodogram, overcome edge effects, and obtain asymptotic normality and efficiency.
Compressed sensing is triggering a major evolution in signal acquisition that changes completely the way we think about experiments and measurements. It indicates that most data, signals and images, that are usually compressible and have redundancy, can be reconstructed from much fewer measurements than what was usually considered necessary, resulting in a drastic gain of time, cost, and measurement precision.
Currently used reconstruction techniques are however limited to acquisition rates still higher than the true density of the signal. By using a mapping to a statistical physics problem, and motivated by the theory of crystal nucleation, I will introduce a new algorithm, and new measurement protocols, that achieves exact reconstruction of the signal up to the lowest possible ones in compressed sensing.
Inference in Markov random fields is one of the most important problem in information science and physics. Susceptibility propagation is a message passing type of algorithm formulated in terms of the belief propagation and linear response formulas. It successfully gives approximate schemes to compute covariances in Markov random fields, and has been applied to a wide range of applications, for example learning and inference in Boltzmann machines. In this talk, we propose a new scheme to make improvements to susceptibility propagation. Our proposed scheme gives better results with the same order of computational cost as the conventional one.
Probing road networks with moving sensors is becoming a major subject in the domain of congestion monitoring and traffic forecasting, thanks to the development of modern communications systems. In the Travesti project, we propose to adapt ideas from statistical physics to model the statistical information provided by floating car data. In particular, we run the belief propagation algorithm on an Ising type model to perform real time travel time reconstruction and prediction on large scale networks.
I will discuss in this talk how we encode the joint probability measure of travel time attached to each segment of the whole network into a Markov random field, in order to associate belief propagation fixed points to traffic congestion patterns. This involves various approximate solutions to the Inverse Ising problem based on mean field considerations, in connection to the Bethe approximation that will be described.
We present here a model performing a minimal encoding between real valued variables for real-time inference purpose on large network. The target application is a traffic network where a small proportion of nodes is observed and for which we wish to predict the unobserved part. Instead of encoding dependencies directly on the space where the predictions are performed, we propose to use a lightweight method to encode them in a binary latent space. We use a message passing algorithm (such as Belief Propagation) to perform the inference in the latent space. We focus here particularly on the way to define the binary latent variable associated to a real valued variable, the determination of the correlations in the latent space and on the modifications to BP needed to take observations into account.
In a large-scale urban transportation network, the global traffic state provides a general view of the spatial configurations of congestion over the whole network. Analysis of specific global traffic patterns provide an overall description of vehicles' traveling behavior in the network, which can be used as a prior global consistency constraint during estimation and predicting local traffic dynamics. Besides, such global view of traffic flow configurations can also help management departments to know about the bottlenecks of the network and improve control strategies.
Despite plentiful progresses in traffic state prediction and modeling, there is still little sound work on mining global traffic states explicitly. In our work, we attack this issue by performing data analysis of traffic configurations over an entire large-scale network simultaneously. We define the global traffic state as a multi-dimensional vector containing traffic states of local links of the traffic network. We propose to use matrix/tensor factorization method to project the high-dimensional global traffic states into a compact low-dimensional space. Based on this procedure, we achieve two benefits. On one hand, we are able to perform clustering and prediction of the global traffic states on the derived low-dimensional projections, in order to obtain the typical spatial configurations of congestion and avoid curse-of-dimensionality. On the other hand, because of the underlined sparsity constraint of matrix/tensor factorization, the spatial configuration of the projection bases learned from the factorization procedure presents a part-based decomposition of the whole network, indicating the groups of correlated links.