We propose a framework for approximate resolution of MDPs with factored state space, factored action space and additive reward, based on (i) considering stochastic factored policies (SFPs) with a given structure, (ii) using variational approximations to estimate SFP values and (iii) using local continuous optimization algorithms to compute “good” SFPs. We have implemented and tested an algorithm (CA-LBP), involving a loopy belief propagation algorithm and a coordinate ascent procedure. Experiments show that CA-LBP performs as well as a state-of-the-art algorithm dedicated to a specific sub-class of FA-FMDPs, and that CA-LBP can be applied to general FA-FMDPs with up to 100 binary state variables and 100 binary action variables.

Computation of the Most Probable Explanation (MPE) when probabilistic knowledge is expressed as a factored distribution is a classical AI reasoning problem: complete evidence is available about the values of some of the variables which are observed, and the problem consists in finding the most probable assignment of the remaining variables given the evidence. However, optimising the choice of the variables to observe (the sample) in order to maximise the MPE probability is a less classical and more difficult problem. In this article we tackle this question of optimal sampling in structured problems under limited budget, within the framework of Hidden Markov Random Fields (HMRF). The value of a sample (which we seek to optimise) is the expectation, over all possible sample outputs (observations), of the MPE probability. The contributions of this article are: i) an original probabilistic model for optimal sampling in HMRF ii) computational complexity results about this problem, leading in particular to approximability/inapproximability results and iii) an exact solution algorithm and two approximate solution algorithms of decreasing time complexity, which we empirically evaluate on a problem of spatial sampling for occurrence map restoration.

We consider the problem of specifying the joint distribution of a collection of variables with maximum entropy when a set of marginals are fixed. One can easily derive that the structure of the solution joint distribution is that of a graphical model. The potential functions are then marginals at some power. We address the following question, Under which conditions on the set of constraints is it possible to fully identify the canonical exponents in the maximum entropy solution as functions of the problem structure? Literature related to this topic is somewhat scattered in disciplines such as statistical mechanics, information theory, graph theory, and inference in graphical models. In this article we gather and link results from these different fields. From this, we show that for a particular class of constraints set on marginals, the chordal maximal coherent sets of constraints, it is possible to derive the canonical exponents of the graphical model solution of the maximum entropy problem as the numbers of occurrences of separators in an associated join tree. Conversely, we present sufficient conditions to ensure that a graphical model is a solution of a maximum entropy problem.

We present a supervised method for the detection and retrieval of relevant events in videos according to dynamic content. We adopt a statistical representation where residual and camera motion informations are characterized by probabilistic models. In an off-line stage, the models associated to pre-identified classes of meaningful dynamic events are learned from a given training set of video samples. Then, a classification and selection algorithm is applied on each segment of a temporal segmentation of the video to process, by exploiting this statistical framework. Only the segments associated to classes defined as relevant in terms of dynamic event can then be selected. The efficiency of the proposed method is evaluated on sport videos for which categories of relevant events can be explicitly defined.

We present a method for motion-based video segmentation and segment classification as a step towards video summarisation. The sequential segmentation of the video is performed by detecting changes in the dominant image motion, assumed to be related to camera motion. It is achieved by analysing the temporal variations of coefficients of the global 2D affine motion model (robustly) estimated. The obtained video segments supply reasonable temporal regions to apply a classification algorithm. To this end, we adopt a statistical representation of the residual motion content of the video scene, relying on the distribution of temporal cooccurrences of local motion-related measurements. Pre-identified classes of dynamic events are learned off-line from a training set of video samples of the genre of interest. Each video segment is then classified according to a maximum likelihood (ML) principle. Finally, excerpts of the relevant classes can be selected for video summarisation.

Hidden Markov random fields appear naturally in problems such as image segmentation, where an unknown class assignment has to be estimated from the observations at each pixel. Choosing the probabilistic model that best accounts for the observations is an important first step for the quality of the subsequent estimation and analysis. A commonly used selection criterion is the Bayesian Information Criterion (BIC) of Schwarz (1978), but for hidden Markov random fields, its exact computation is not tractable due to the dependence structure induced by the Markov model. We propose approximations of BIC based on the mean field principle of statistical physics. The mean field theory provides approximations of Markov random fields by systems of independent variables leading to tractable computations. Using this principle, we first derive a class of criteria by approximating the Markov distribution in the usual BIC expression as a penalized likelihood. We then rewrite BIC in terms of normalizing constants, also called partition functions, instead of Markov distributions. It enables us to use finer mean field approximations and to derive other criteria using optimal lower bounds for the normalizing constants. To illustrate the performance of our partition function-based approximation of BIC as a model selection criterion, we focus on the preliminary issue of choosing the number of classes before the segmentation task. Experiments on simulated and real data point out our criterion as promising: It takes spatial information into account through the Markov model and improves the results obtained with BIC for independent mixture models.

We present in this paper an original approach for content-based video segmentation using motion information. The method is generic and does not require any knowledge about the type of the processed video. Its relies on the analysis of the temporal evolution of the dynamic content of the video.