Search

Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain. In general, logit dynamics might converge slowly to the Gibbs distribution, but beyond that, not much is known about their algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: i) Is there an efficient algorithm for sampling from the Gibbs distribution? ii) If yes, do there also exist natural randomized dynamics that converges quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics (in which we in addition are allowed to randomly interchange the strategies of two players) that converges quickly to the Gibbs distribution in such games. This answers both questions above affirmatively. We also address the first question for the class of so-called capacitated $k$-uniform congestion games. To prove our results, we rely on the recent breakthrough work of Anari, Liu, Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the base of a matroid according to strongly log-concave probability distribution., Accepted at the 22nd ACM Conference on Economics and Computation (EC 2021)

Theoretical Computer Science, 745, ISSN:0304-3975

We show that under a low complexity condition on the gradient of a Hamiltonian, Gibbs distributions on the Boolean hypercube are approximate mixtures of product measures whose probability vectors are critical points of an associated mean-field functional. This extends a previous work by the first author. As an application, we demonstrate how this framework helps characterize both Ising models satisfying a mean-field condition and the conditional distributions which arise in the emerging theory of nonlinear large deviations, both in the dense case and in the polynomially-sparse case.

We prove that a stochastic process of pure coagulation has at any time t ≥ 0 a time-dependent Gibbs distribution if and only if the rates ψ(i, j) of single coagulations are of the form ψ(i; j) = if(j) + jf(i), where f is an arbitrary nonnegative function on the set of positive integers. We also obtain a recurrence relation for weights of these Gibbs distributions that allow us to derive the general form of the solution and the explicit solutions in three particular cases of the function f. For the three corresponding models, we study the probability of coagulation into one giant cluster by time t > 0.

We construct an integrated probabilistic model to capture interactions between atoms of a nanocomponent. We then use this model to assess reliabilities of nanocomponents with different structures. Several properties of our proposed model are also described under a sparseness condition. The model is an extension of our previous model based on Markovian random field theory. The proposed integrated model is flexible in that pairwise relationship information among atoms as well as features of individual atoms can be easily incorporated. An important feature that distinguishes the integrated probabilistic model from our previous model is that the integrated approach uses all available sources of information with different weights for different types of interaction. In this paper we consider the nanocomponent at a fixed moment of time, say the present moment, and we assume that the present state of the nanocomponent depends only on the present states of its atoms.

A vast literature has recently been concerned with the analysis of variation in disease counts recorded across geographical areas with the aim of detecting clusters of regions with homogeneous behavior. Most of the proposed modeling approaches have been discussed for the univariate case and only very recently spatial models have been extended to predict more than one outcome simultaneously. In this paper we extend the standard finite mixture models to the analysis of multiple, spatially correlated, counts. Dependence among outcomes is modeled using a set of correlated random effects and estimation is carried out by numerical integration through an EM algorithm without assuming any specific parametric distribution for the random effects. The spatial structure is captured by the use of a Gibbs representation for the prior probabilities of component membership through a Strauss-like model. The proposed model is illustrated using real data.

In this paper, we propose a model for image segmentation based on a finite mixture of Gaussian distributions. For each pixel of the image, prior probabilities of class memberships are specified through a Gibbs distribution, where association between labels of adjacent pixels is modeled by a class-specific term allowing for different interaction strengths across classes. We show how model parameters can be estimated in a maximum likelihood framework using Mean Field theory. Experimental performance on perturbed phantom and on real benchmark images shows that the proposed method performs well in a wide variety of empirical situations.

Image modeling using Gibbs priors was shown to be effective in image reconstruction problems. This motivated us to evaluate three techniques for estimating the priors: the heuristic method, the histogram method and Borges' method. We found that both the histogram and Borges' method accurately recovered the parameters needed to specify four different Gibbs distributions from training sets consisting of random sample images from those distributions. This was not the case for the heuristic method. We evaluated the usefulness of the estimated distributions as priors for binary tomography in two experiments: in one the images for the training set were taken from a Gibbs distribution determined by five parameters, and they were typical cardiac phantom images for the second one. We estimated the parameters using both the heuristic and Borges' method in both experiments. We used a modified Metropolis algorithm for the reconstructions. In the first experiment both estimation methods gave rise to excellent reconstructions, but this was not the case for the second experiment; however, even in this case typically less than four percent of the pixels were mis-classified in the reconstructions.

Wavelet threshold algorithms replace small magnitude wavelet coefficients with zero and keep or shrink the other coefficients. This is basically a local procedure, because wavelet coefficients characterize the local regularity of a function. Although a wavelet transform has decorrelating properties, structures in images, like edges, are never decorrelated completely, and these structures appear in the wavelet coefficients: a classification based on a local criterion-like coefficient magnitude is not the perfect method to distinguish important, uncorrupted coefficients from coefficients dominated by noise. We therefore introduce a geometrical prior model for configurations of important wavelet coefficients and combine this with local characterization of a classical threshold procedure into a Bayesian framework. The local characterization is incorporated into the conditional model, whereas the prior model describes only configurations, not coefficient values. More precisely, local characterization favors configurations with clusters of important coefficients. In this way, we can compute, for each coefficient, the posterior probability of being "sufficiently clean." This article proposes and motivates the particular and original choice of the conditional model. Instead of introducing this Bayesian framework, we could also apply heuristic image processing techniques to find clustered configurations of large coefficients. This article also explains the benefits of the Bayesian approach compared to these simple techniques. The parameter of the prior model is estimated on an empirical basis using a pseudolikelihood criterion.

International audience; This paper presents different recursive formulas for computing the marginals and the normalizing constant of a Gibbs distribution \pi . The common thread is the use of the underlying Markov properties of such processes. The procedures are illustrated with several examples, particularly the Ising model.

When analyzing motion observations extracted from image sequences one notes that the histogram of the velocity magnitude at each pixel shows a large probability mass at zero velocity, while the rest of the motion values may be appropriately modeled with a continuous distribution. This suggests the introduction of mixed-state random variables that have probability mass concentrated in discrete states, while they have a probability density over a continuous range of values. In the first part of the chapter, we give a comprehensive description of the theory behind mixed-state statistical models, in particular the development of mixed-state Markov models that permits to take into account spatial and temporal interaction. The presentation generalizes the case of simultaneous modeling of continuous values and any type of discrete symbolic states. For the second part, we present the application of mixed-state models to motion texture analysis. Motion textures correspond to the instantaneous apparent motion maps extracted from dynamic textures. They depict mixed-state motion values with a discrete state at zero and a Gaussian distributionfor the rest. Mixed-state Markov random fields and mixed-state Markov chains are defined and applied to motion texture recognition and tracking. Fil: Crivelli, Tomás. Universidad de Buenos Aires. Facultad de Ingeniería. Departamento de Electronica; Argentina Fil: Bouthemy, Patrick. No especifíca; Fil: Cernuschi Frias, Bruno. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Saavedra 15. Instituto Argentino de Matemática Alberto Calderón; Argentina Fil: Yao, Jian Feng. No especifíca

International audience; We present a recursive algorithm for the calculation of the marginal of a Gibbs distribution $\pi$. A direct consequence is the calculation of the normalizing constant of$\pi$.

We study fragmentation trees of Gibbs type. In the binary case, we identify the most general Gibbs-type fragmentation tree with Aldous' beta-splitting model, which has an extended parameter range $\beta>-2$ with respect to the ${\rm beta}(\beta+1,\beta+1)$ probability distributions on which it is based. In the multifurcating case, we show that Gibbs fragmentation trees are associated with the two-parameter Poisson--Dirichlet models for exchangeable random partitions of $\mathbb {N}$, with an extended parameter range $0\le\alpha\le1$, $\theta\ge-2\alpha$ and $\alpha, Comment: Published in at http://dx.doi.org/10.3150/08-BEJ134 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

We introduce and study a new concept of a weak elliptic equation for measures on infinite dimensional spaces. This concept allows one to consider equations whose coefficients are not globally integrable. By using a suitably extended Lyapunov function technique, we derive a priori estimates for the solutions of such equations and prove new existence results. As an application, we consider stochastic Burgers, reaction-diffusion, and Navier-Stokes equations and investigate the elliptic equations for the corresponding invariant measures. Our general theorems yield a priori estimates and existence results for such elliptic equations. We also obtain moment estimates for Gibbs distributions and prove an existence result applicable to a wide class of models.

Suppose n particles xi in a region of the plane (possibly representing biological individuals such as trees or smaller organisms) have a joint density proportional to exp{-∑i

Depth from defocus (DFD) problem involves calculating the depth of various points in a scene by modeling the effect that the focal parameters of the camera have on images acquired with a small depth of field. In this paper, we propose a MAP-MRF-based scheme for recovering the depth and the focused image of a scene from two defocused images. The space-variant blur parameter and the focused image of the scene are both modeled as MRFs and their MAP estimates are obtained using simulated annealing. The scheme is amenable to the incorporation of smoothness constraints on the spatial variations of the blur parameter as well as the scene intensity. It also allows for inclusion of line fields to preserve discontinuities. The performance of the proposed scheme is tested on synthetic as well as real data and the estimates of the depth are found to be better than that of the existing window-based DFD technique. The quality of the space-variant restored image of the scene is quite good even under severe space-varying blurring conditions.

This paper presents a reduced-complexity deterministic annealing (DA) approach for vector quantizer (VQ) design by using soft information processing with simplified assignment measures. Low-complexity distributions are designed to mimic the Gibbs distribution, where the latter is the optimal distribution used in the standard DA method. These low-complexity distributions are simple enough to facilitate fast computation, but at the same time they can closely approximate the Gibbs distribution to result in near-optimal performance. We have also derived the theoretical performance loss at a given system entropy due to using the simple soft measures instead of the optimal Gibbs measure. We use thederived result to obtain optimal annealing schedules for the simple soft measures that approximate the annealing schedule for the optimal Gibbs distribution. The proposed reduced-complexity DA algorithms have significantly improved the quality of the final codebooks compared to the generalized Lloyd algorithm and standard stochastic relaxation techniques, both with and without the pairwise nearest neighbor (PNN) codebook initialization. The proposed algorithms are able to evade the local minima and the results show that they are not sensitive to the choice of the initial codebook. Compared to the standard DA approach, the reduced-complexity DA algorithms can operate over 100 times faster with negligible performance difference. For example, for the design of a 16-dimensional vector quantizer having a rate of 0.4375 bit/sample for Gaussian source, the standard DA algorithm achieved 3.60 dB performance in 16 483 CPU seconds, whereas the reduced-complexity DA algorithm achieved the same performance in 136 CPU seconds. Other than VQ design, the DA techniques are applicable to problems such as classification, clustering, and resource allocation.