Search

A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We consider sampling problems coming from Gibbs distributions, which are families of probability distributions over a discrete space \(\Omega\) with probability mass function of the form \(\mu^{\Omega}_{\beta}(\omega)\propto e^{\beta H(\omega)}\) for \(\beta\) in an interval \([\beta_{\min},\beta_{\max}]\) and \(H(\omega)\in\{0\}\cup[1,n]\). Two important parameters are the partition function, which is the normalization factor \(Z(\beta)=\sum_{\omega\in\Omega}e^{\beta H(\omega)}\) and the vector of pre-image counts \(c_{x}=|H^{-1}(x)|\). We develop black-box sampling algorithms to estimate the counts using roughly \(\tilde{O}(\frac{n^{2}}{\varepsilon^{2}})\) samples for integer-valued distributions and \(\tilde{O}(\frac{q}{\varepsilon^{2}})\) samples for general distributions, where \(q=\log\frac{Z(\beta_{\max})}{Z(\beta_{\min})}\) (ignoring some second-order terms and parameters). We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs, independent sets, and perfect matchings. As a key subroutine, we estimate all values of the partition function using \(\tilde{O}(\frac{n^{2}}{\varepsilon^{2}})\) samples for integer-valued distributions and \(\tilde{O}(\frac{q}{\varepsilon^{2}})\) samples for general distributions. This improves over a prior algorithm of Huber (2015) which computes a single point estimate \(Z(\beta_{\max})\) and which uses a slightly larger amount of samples. We show matching lower bounds, demonstrating this complexity is optimal as a function of \(n\) and \(q\) up to logarithmic terms. [ABSTRACT FROM AUTHOR]

The author considers a practical algorithm for estimating an unknown parameter of the mathematical model of a Markov process with local interaction based on the Gibbs distribution. It is proposed to apply the stochastic quasi-gradient method to the maximum likelihood function, which is constructed from the observations of the realizations of the Gibbs field. The obtained results have a wide application scope in the modeling of stochastic processes. [ABSTRACT FROM AUTHOR]

The author considers a practical algorithm for estimating an unknown parameter of a mathematical model of a Markov process with local interaction based on the Gibbs distribution. It is proposed to apply the method of stochastic quasi-gradients to the maximum likelihood function, which is constructed from the observations of the implementations of the Gibbs field. The obtained results have a wide application in the modeling of stochastic processes. [ABSTRACT FROM AUTHOR]

Logit dynamics is a form of randomized game dynamics in which players have a bias toward strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converge to the so-called Gibbs distribution over the set of all strategy profiles when interpreted as a Markov chain. In general, logit dynamics can converge slowly to the Gibbs distribution, but beyond that, not much is known about its 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, does there also exist natural randomized dynamics that converge 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 that converges quickly to the Gibbs distribution in such games. We also address the first question for the class of so-called capacitated uniform congestion games and the second question for max cut games played on a complete graph. To prove our results, we rely on the recent breakthrough work of Anari et al. (2019) regarding the approximate sampling of a base of a matroid according to a strongly log-concave probability distribution. [ABSTRACT FROM AUTHOR]

The author considers a practical algorithm for estimating an unknown parameter of the mathematical model of a Markov process with local interaction based on the Gibbs distribution. It is proposed to apply the stochastic quasi-gradient method to the maximum likelihood function, which is constructed from the observations of the realizations of the Gibbs field. The obtained results have a wide application scope in the modeling of stochastic processes. [ABSTRACT FROM AUTHOR]

In this paper, we show that the methods of mathematical statistical physics can be successfully applied to random fields in finite volumes. As a result, we obtain simple necessary and sufficient conditions for the existence and uniqueness of a finite random field with a given system of one-point conditional distributions. Using the axiomatic (without the notion of potential) definition of Hamiltonian, we show that any finite random field is Gibbsian. We also apply the proposed approach to Markov random fields. [ABSTRACT FROM AUTHOR]

This paper focuses on entropic regularization and its multiscale extension in neural network learning. We leverage established results that characterize the optimizer of entropic regularization methods and their connection with generalization bounds. To avoid the significant computational complexity involved in sampling from the optimal multiscale Gibbs distributions, we describe how to make measured concessions in optimality by using self-similar approximating distributions. We study such scale-invariant approximations for linear neural networks and further extend the approximations to neural networks with nonlinear activation functions. We then illustrate the application of our proposed approach through empirical simulation. By navigating the interplay between optimization and computational efficiency, our research contributes to entropic regularization theory, proposing a practical method that embraces symmetry across scales. [ABSTRACT FROM AUTHOR]

Abstract polymer models are systems of weighted objects, called polymers, equipped with an incompatibility relation. An important quantity associated with such models is the partition function, which is the weighted sum over all sets of compatible polymers. Various approximation problems reduce to approximating the partition function of a polymer model. Central to the existence of such approximation algorithms are weight conditions of the respective polymer model. Such conditions are derived either via complex analysis or via probabilistic arguments. We follow the latter path and establish a new condition—the clique dynamics condition—, which is less restrictive than the ones in the literature. We introduce a new Markov chain where the clique dynamics condition implies rapid mixing by utilizing cliques of incompatible polymers that naturally arise from the translation of algorithmic problems into polymer models. This leads to improved parameter ranges for several approximation algorithms, such as a factor of at least 2 1 / α for the hard-core model on bipartite α -expanders. [ABSTRACT FROM AUTHOR]

We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood growth. In particular, in graphs with subexponential neighborhood growth like ℤd, our algorithm achieves linear running time as long as Gibbs sampling is rapidly mixing. As concrete applications, we obtain the currently best perfect samplers for colorings and for monomer‐dimer models in such graphs. [ABSTRACT FROM AUTHOR]

Markov random fields (MRFs) are well studied during the past 50 years. Their success are mainly due to their flexibility and to the fact that they gives raise to stochastic image models. In this work, we will consider a stochastic differential equation (SDE) driven by Lévy noise. We will show that the solution $ X_v $ of the SDE is a MRF satisfying the Markov property. We will prove that the Gibbs distribution of the process $ X_v $ can be represented graphically through Feynman graphs, which are defined as a set of cliques, then we will provide applications of MRFs in image processing where the image intensity at a particular location depends only on a neighborhood of pixels.

The authors consider an algorithm for estimating the unknown parameters of the infection spread model based on the Markov field tools using the maximum likelihood method. It is assumed that each state of the Markov chain represents some configuration of a finite random Markov field, and the probability distribution of the chain states is the same as general probability distribution of the states of elements of the Gibbs random field. [ABSTRACT FROM AUTHOR]

It is shown that there are three characteristic time scales for the establishment of thermodynamic equilibrium: the time for the thermalization of the system; the time for establishing a uniform temperature in the system after contact with the thermostat; and, finally, the time for establishing full ergodicity in the system. The first time is determined by particle collisions (in fluids) or multiphonon processes (in condensed media) and lies in the range from tens of picoseconds (in dense fluids) to microseconds (in pure crystals at low temperatures). The second time is determined by the thermal diffusivity and the size of the system and, for millimeter-sized samples, lasts for seconds. The third time is determined by the particle diffusion rates and can vary from hundreds of picoseconds (in gases and liquids) to astronomical times (in solids at low temperatures). The concept of ergodicity as applied to crystals and glasses is discussed. [ABSTRACT FROM AUTHOR]

A Gibbs distribution based combinatorial optimization algorithm for joint antenna splitting and user scheduling problem in full duplex massive multiple-input multiple-output (MIMO) system is proposed in this paper. The optimal solution of this problem can be determined by exhaustive search. However, the complexity of this approach becomes prohibitive in practice when the sample space is large, which is usually the case in massive MIMO systems. Our algorithm overcomes this drawback by converting the original problem into a Kullback-Leibler (KL) divergence minimization problem, and solving it through a related dynamical system via a stochastic gradient descent method. Using this approach, we improve the spectral efficiency (SE) of the system by performing joint antenna splitting and user scheduling. Additionally, numerical results show that the SE curves obtained with our proposed algorithm overlap with the curves achieved by exhaustive search for user scheduling. [ABSTRACT FROM AUTHOR]

In image classification, deriving robust image representations is a key process that determines the performance of vision systems. Numerous image features and descriptors have been developed manually over the years. As an alternative, however, deep neural networks, in particular convolutional neural networks (CNNs), have become popular for learning image features or representations from data and have demonstrated remarkable performance in many real-world applications. But CNNs often require huge amount of labelled data, which may be prohibitive in many applications, as well as long training times. This paper considers an alternative, data-independent means of obtaining features for CNNs. The proposed framework makes use of the Markov random field (MRF) and self-organising map (SOM) to generate basic features and model both intra- and inter-image dependencies. Various MRF textures are synthesized first, and are then clustered by a convolutional translation-invariant SOM, to form generic image features. These features can be directly applied as early convolutional filters of the CNN, leading to a new way of deriving effective features for image classification. The MRF framework also offers a theoretical and transparent way to examine and determine the influence of image features on performance of CNNs. Comprehensive experiments on the MNIST, rotated MNIST, CIFAR-10 and CIFAR-100 datasets were conducted with results outperforming most state-of-the-art models of similar complexity. [ABSTRACT FROM AUTHOR]

The world’s first 2 $\times $ 30k-spin multi-chip CMOS annealing processor (AP)—based on the processing-in-memory approach for solving large-scale combinatorial optimization problem—was developed. To expand the bit width of coefficients and enhance the scalability of the AP, it has three key features: an expandable and high-accuracy spin operator for local communication, a highly integrated spin circuit using direct access to SRAM, and a low-latency inter-chip interface that does not affect the runtime or results of the annealing process. The AP is fabricated on the basis of 40-nm CMOS technology. It was experimentally demonstrated that the spin-flip ratio of the processor agrees well with theoretical values based on the Gibbs distribution over a wide temperature range. As a result, under two-chip operation with 2 $\times $ 30k spins, the AP achieves an annealing time of 22 $\mu \text{s}$ , which is 455 times and 2.6 $\times $ 104 times faster than those achieved by our previous CMOS-AP and a conventional CPU, respectively. Moreover, its energy efficiency is 1.75 $\times $ 105 times higher than that of a conventional CPU-based algorithm. [ABSTRACT FROM AUTHOR]

We investigate a probabilistic model for routeing in a multihop ad hoc communication network, where each user sends a message to the base station. Messages travel in hops via other users, used as relays. Their trajectories are chosen at random according to a Gibbs distribution, which favors trajectories with low interference, measured in terms of signal-to-interference ratio. This model was introduced in our earlier paper, where we expressed, in the limit of a high density of users, the typical distribution of the family of trajectories in terms of a law of large numbers. In this paper, we derive its qualitative properties. We analytically identify the emerging typical scenarios in three extreme regimes. We analyze the typical number of hops and the typical length of a hop and the deviation of the trajectory from the straight line, regime 1 in the limit of a large communication area and large distances and regime 2 in the limit of a strong interference weight. In both the regimes, the typical trajectory approaches a straight line quickly, in regime 1 with equal hop lengths. Interestingly, in regime 2, the typical length of a hop diverges logarithmically in the distance of the transmitter to the base station. We further analyze (regime 3) local and global repulsive effects of a densely populated subarea on the trajectories. [ABSTRACT FROM AUTHOR]

Synthetic aperture radar (SAR) provides rich information about the Earth’s surface under all-weather and day-and-night conditions, and is applied in many relevant fields. SAR imagery semantic segmentation, which can be a final product for end users and a fundamental procedure to support other applications, is one of the most difficult challenges. This paper proposes an encoding-decoding network based on Deeplabv3+ to semantically segment SAR imagery. A new potential energy loss function based on the Gibbs distribution is proposed here to establish the semantic dependence among different categories through the relationship among different cliques in the neighborhood system. This paper introduces an improved channel and spatial attention module to the Mobilenetv2 backbone to improve the recognition accuracy of small object categories in SAR imagery. The experimental results show that the proposed method achieves the highest mean intersection over union (mIoU) and global accuracy (GA) with the least running time, which verifies the effectiveness of our method.

Abstract Most real world combinatorial optimization problems are affected by noise in the input data, thus behaving in the high noise limit like large disordered particle systems, e.g. spin glasses or random networks. Due to uncertainty in the input, optimization of such disordered instances should infer stable posterior distributions of solutions conditioned on the noisy input instance. The maximum entropy principle states that the most stable distribution given the noise influence is defined by the Gibbs distribution and it is characterized by the free energy. In this paper, we first provide rigorous asymptotics of the difficult problem to compute the free energy for two combinatorial optimization problems, namely the sparse Minimum Bisection Problem (sMBP) and Lawler's Quadratic Assignment Problem (LQAP). We prove that both problems exhibit phase transitions equivalent to the discontinuous behavior of Derrida's Random Energy Model (REM). Furthermore, the derived free energy asymptotics lead to a theoretical justification of a recently introduced concept [3] of Gibbs posterior agreement that measures stability of the Gibbs distributions when the cost function fluctuates due to randomness in the input. This relatively new stability concept may potentially provide a new method to select robust solutions for a large class of optimization problems. [ABSTRACT FROM AUTHOR]

Distributed link scheduling algorithms based on carrier sense multiple access and Gibbs sampling are known to achieve throughput optimality, if certain parameters called the fugacities are appropriately chosen. However, the problem of computing these fugacities is NP-hard. Further, the complexity of the existing stochastic gradient descent-based algorithms that compute the exact fugacities scales exponentially with the network size. In this paper, we propose a general framework to estimate the fugacities using regional free energy approximations. In particular, we derive explicit expressions for approximate fugacities corresponding to any feasible service rate vector. We further prove that our approximate fugacities are exact for the class of chordal graphs. A distinguishing feature of our work is that the regional approximations that we propose are tailored to conflict graphs with small cycles, which is a typical characteristic of wireless networks. Numerical results indicate that the proposed methods are quite accurate, and significantly outperform the existing approximation techniques. [ABSTRACT FROM AUTHOR]

Image segmentation plays a fundamental role in many computer vision applications . It is challenging because of the vast variety of images involved and the diverse segmentation requirements in different applications. As a result, it remains an open problem after so many years of study by researchers all over the world. In this paper, we propose to segment the image by combing its global and local properties. The global properties of the image are characterized by the mean values of different pixel classes and the continuous boundary of the object or region. The local properties are characterized by the interactions of neighboring pixels and the image edge. The proposed approach consists of four basic parts corresponding to the global or local property of the image respectively: (1) The slope difference distribution that is used to compute the global mean values of different pixel classes; (2) Energy minimization to remove inhomogeneity based on Gibbs distribution that complies with local interactions of neighboring pixels; (3) The Canny operator that is used to detect the local edge of the object or the region; (4) The polynomial spline that is used to smooth the boundary of the object or the region. These four basic parts are applied one by one and each of them is indispensable for the achieved high accuracy. A large variety of images are used to validate the proposed approach and the results are favorable. [ABSTRACT FROM AUTHOR]

We consider a carrier sense multiple access (CSMA)-based scheduling algorithm for a single-hop wireless network under a realistic signal-to-interference-plus-noise ratio model for the interference. We propose two local optimization-based approximation algorithms to efficiently estimate certain attempt rate parameters of CSMA called fugacities. It is known that adaptive CSMA can achieve throughput optimality by sampling feasible schedules from a Gibbs distribution, with appropriate fugacities. Unfortunately, obtaining these optimal fugacities is an NP-hard problem. Furthermore, the existing adaptive CSMA algorithms use a stochastic gradient descent-based method, which usually entails an impractically slow (exponential in the size of the network) convergence to the optimal fugacities. To address this issue, we first propose an algorithm to estimate the fugacities, that can support a given set of desired service rates. The convergence rate and the complexity of this algorithm are independent of the network size, and depend only on the neighborhood size of a link. Furthermore, we show that the proposed algorithm corresponds exactly to performing the well-known Bethe approximation to the underlying Gibbs distribution. Then, we propose another local algorithm to estimate the optimal fugacities under a utility maximization framework, and characterize its accuracy. Numerical results indicate that the proposed methods have a good degree of accuracy, and achieve extremely fast convergence to near-optimal fugacities, and often outperform the convergence rate of the stochastic gradient descent by a few orders of magnitude. [ABSTRACT FROM AUTHOR]

We propose and analyze a potential induced random walk and its modification called random teleportation on finite graphs. The transition probability is determined by the gaps between potential values of adjacent and teleportation nodes. We show that the steady state of this process has a number of desirable properties. We present a continuous time analogue of the random walk and teleportation, and derive the lower bound on the order of its exponential convergence rate to stationary distribution. The efficiency of proposed random teleportation in search of global potential minimum on graphs and node ranking are demonstrated by numerical tests. Moreover, we discuss the condition of graphs and potential distributions for which the proposed approach may work inefficiently, and introduce the intermittent diffusion strategy to overcome the problem and improve the practical performance. [ABSTRACT FROM AUTHOR]

Synthetic aperture radar (SAR) provides rich information about the Earth's surface under all-weather and day-and-night conditions, and is applied in many relevant fields. SAR imagery semantic segmentation, which can be a final product for end users and a fundamental procedure to support other applications, is one of the most difficult challenges. This paper proposes an encoding-decoding network based on Deeplabv3+ to semantically segment SAR imagery. A new potential energy loss function based on the Gibbs distribution is proposed here to establish the semantic dependence among different categories through the relationship among different cliques in the neighborhood system. This paper introduces an improved channel and spatial attention module to the Mobilenetv2 backbone to improve the recognition accuracy of small object categories in SAR imagery. The experimental results show that the proposed method achieves the highest mean intersection over union (mIoU) and global accuracy (GA) with the least running time, which verifies the effectiveness of our method. [ABSTRACT FROM AUTHOR]