Bayesian Ising Graphical Model for Variable Selection

In this article, we propose a new Bayesian variable selection (BVS) approach via the graphical model and the Ising model, which we refer to as the “Bayesian Ising graphical model” (BIGM). The BIGM is developed by showing that the BVS problem based on the linear regression model can be considered as a complete graph and described by an Ising model with random interactions. There are several advantages of our BIGM: it is easy to (i) employ the single-site updating and cluster updating algorithm, both of which are suitable for problems with small sample sizes and a larger number of variables, (ii) extend this approach to nonparametric regression models, and (iii) incorporate graphical prior information. In our BIGM, the interactions are determined by the linear model coefficients, so we systematically study the performance of different scale normal mixture priors for the model coefficients by adopting the global-local shrinkage strategy. Our results indicate that the best prior for the model coefficients in terms of variable selection should place substantial weight on small, nonzero shrinkage. The methods are illustrated with simulated and real data. Supplementary materials for this article are available online.     

The bivariate Ising polynomial of a graph

In this paper we discuss the two variable Ising polynomials in a graph theoretical setting. This polynomial has its origin in physics as the partition function of the Ising model with an external field. We prove some basic properties of the Ising polynomial and demonstrate that it encodes a large amount of combinatorial information about a graph. We also give examples which prove that certain properties, such as the chromatic number, are not determined by the Ising polynomial. Finally we prove that there exist large families of non-isomorphic planar triangulations with identical Ising polynomial.     

A new approach to solving three combinatorial enumeration problems on planar graphs

The purpose of this paper is to show how the technique of delta-wye graph reduction provides an alternative method for solving three enumerative function evaluation problems on planar graphs. In particular, it is shown how to compute the number of spanning trees and perfect matchings, and how to evaluate energy in the Ising “spin glass” model of statistical mechanics. These alternative algorithms require O(n²) arithmetic operations on an n-vertex planar grapha, and are relatively easy to implement.     

Frozen 1-RSB structure of the symmetric Ising perceptron

We prove, under an assumption on the critical points of a real-valued function, that the symmetric Ising perceptron exhibits the ‘frozen 1-RSB’ structure conjectured by Krauth and Mézard in the physics literature; that is, typical solutions of the model lie in clusters of vanishing entropy density. Moreover, we prove this in a very strong form conjectured by Huang, Wong, and Kabashima: a typical solution of the model is isolated with high probability and the Hamming distance to all other solutions is linear in the dimension. The frozen 1-RSB scenario is part of a recent and intriguing explanation of the performance of learning algorithms by Baldassi, Ingrosso, Lucibello, Saglietti, and Zecchina. We prove this structural result by comparing the symmetric Ising perceptron model to a planted model and proving a comparison result between the two models. Our main technical tool towards this comparison is an inductive argument for the concentration of the logarithm of number of solutions in the model.     

Sampling Schemes for Bayesian Variable Selection in Generalized Linear Models

Bayesian approaches to prediction and the assessment of predictive uncertainty in generalized linear models are often based on averaging predictions over different models, and this requires methods for accounting for model uncertainty. When there are linear dependencies among potential predictor variables in a generalized linear model, existing Markov chain Monte Carlo algorithms for sampling from the posterior distribution on the model and parameter space in Bayesian variable selection problems may not work well. This article describes a sampling algorithm based on the Swendsen-Wang algorithm for the Ising model, and which works well when the predictors are far from orthogonality. In problems of variable selection for generalized linear models we can index different models by a binary parameter vector, where each binary variable indicates whether or not a given predictor variable is included in the model. The posterior distribution on the model is a distribution on this collection of binary strings, and by thinking of this posterior distribution as a binary spatial field we apply a sampling scheme inspired by the Swendsen-Wang algorithm for the Ising model in order to sample from the model posterior distribution. The algorithm we describe extends a similar algorithm for variable selection problems in linear models. The benefits of the algorithm are demonstrated for both real and simulated data.     

Proof of the local REM conjecture for number partitioning. I: Constant energy scales

In this article we consider the number partitioning problem (NPP ) in the following probabilistic version: Given n numbers X₁,…,X_n drawn i.i.d. from some distribution, one is asked to find the partition into two subsets such that the sum of the numbers in one subset is as close as possible to the sum of the numbers in the other set. In this probabilistic version, the NPP is equivalent to a mean‐field antiferromagnetic Ising spin glass, with spin configurations corresponding to partitions, and the energy of a spin configuration corresponding to the weight difference. Although the energy levels of this model are a priori highly correlated, a surprising recent conjecture of Bauke, Franz, and Mertens asserts that the energy spectrum of number partitioning is locally that of a random energy model (REM): the spacings between nearby energy levels are uncorrelated. More precisely, it was conjectured that the properly scaled energies converge to a Poisson process, and that the spin configurations corresponding to nearby energies are asymptotically uncorrelated. In this article, we prove these two claims, collectively known as the local REM conjecture. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Metastability in the dilute Ising model

Consider Glauber dynamics for the Ising model on the hypercubic lattice with a positive magnetic field. Starting from the minus configuration, the system initially settles into a metastable state with negative magnetization. Slowly the system relaxes to a stable state with positive magnetization. Schonmann and Shlosman showed that in the two dimensional case the relaxation time is a simple function of the energy required to create a critical Wulff droplet. The dilute Ising model is obtained from the regular Ising model by deleting a fraction of the edges of the underlying graph. In this paper we show that even an arbitrarily small dilution can dramatically reduce the relaxation time. This is because of a catalytic effect—rare regions of high dilution speed up the transition from minus phase to plus phase.     

Classification of brain activation via spatial Bayesian variable selection in fMRI regression

Functional magnetic resonance imaging (fMRI) is the most popular technique in human brain mapping, with statistical parametric mapping (SPM) as a classical benchmark tool for detecting brain activity. Smith and Fahrmeir (J Am Stat Assoc 102(478):417–431, 2007) proposed a competing method based on a spatial Bayesian variable selection in voxelwise linear regressions, with an Ising prior for latent activation indicators. In this article, we alternatively link activation probabilities to two types of latent Gaussian Markov random fields (GMRFs) via a probit model. Statistical inference in resulting high-dimensional hierarchical models is based on Markov chain Monte Carlo approaches, providing posterior estimates of activation probabilities and enhancing formation of activation clusters. Three algorithms are proposed depending on GMRF type and update scheme. An application to an active acoustic oddball experiment and a simulation study show a substantial increase in sensitivity compared to existing fMRI activation detection methods like classical SPM and the Ising model.     

Optimizing over the first Chvátal closure

How difficult is, in practice, to optimize exactly over the first Chvátal closure of a generic ILP? Which fraction of the integrality gap can be closed this way, e.g., for some hard problems in the MIPLIB library? Can the first-closure optimization be useful as a research (off-line) tool to guess the structure of some relevant classes of inequalities, when a specific combinatorial problem is addressed? In this paper we give answers to the above questions, based on an extensive computational analysis. Our approach is to model the rank-1 Chvátal-Gomory separation problem, which is known to be NP-hard, through a MIP model, which is then solved through a general-purpose MIP solver. As far as we know, this approach was never implemented and evaluated computationally by previous authors, though it gives a very useful separation tool for general ILP problems. We report the optimal value over the first Chvátal closure for a set of ILP problems from MIPLIB 3.0 and 2003. We also report, for the first time, the optimal solution of a very hard instance from MIPLIB 2003, namely nsrand-ipx, obtained by using our cut separation procedure to preprocess the original ILP model. Finally, we describe a new class of ATSP facets found with the help of our separation procedure.     

Bootstrap percolation,and other automata

Many fundamental and important questions from statistical physics lead to beautiful problems in extremal and probabilistic combinatorics. One particular example of this phenomenon is the study of bootstrap percolation, which is motivated by a variety of ‘real-world’ cellular automata, such as the Glauber dynamics of the Ising model of ferromagnetism, and kinetically constrained spin models of the liquid–glass transition.In this review article, we will describe some dramatic recent developments in the theory of bootstrap percolation (and, more generally, of monotone cellular automata with random initial conditions), and discuss some potential extensions of these methods and results to other automata. In particular, we will state numerous conjectures and open problems.     

Nonexistence of Markovian time dynamics for graphical models of correlated default

Filiz et al. (in arXiv:0809.1393 (2008)) proposed a model for the pattern of defaults seen among a group of firms at the end of a given time period. The ingredients in the model are a graph G=(V,E), where the vertices V correspond to the firms and the edges E describe the network of interdependencies between the firms, a parameter for each vertex that captures the individual propensity of that firm to default, and a parameter for each edge that captures the joint propensity of the two connected firms to default. The correlated default model can be rewritten as a standard Ising model on the graph by identifying the set of defaulting firms in the default model with the set of sites in the Ising model for which the {±1}-valued spin is +1. We ask whether there is a suitable continuous-time Markov chain (X _t ) _t??0 taking values in the subsets of V such that X ₀=?, X _r ?X _s for r??s (that is, once a firm defaults, it stays in default), the distribution of X _T for some fixed time T is the one given by the default model, and the distribution of X _t for other times t is described by a probability distribution in the same family as the default model. In terms of the equivalent Ising model, this corresponds to asking if it is possible to begin at time 0 with a configuration in which every spin is ?1 and then flip spins one at a time from ?1 to +1 according to Markovian dynamics so that the configuration of spins at each time is described by some Ising model and at time T the configuration is distributed according to the prescribed Ising model. We show for three simple but financially natural special cases that this is not possible outside of the trivial case where there is complete independence between the firms.     

The energy density in the planar Ising model

We study the critical Ising model on the square lattice in bounded simply connected domains with + and free boundary conditions. We relate the energy density of the model to a discrete fermionic correlator and compute its scaling limit by discrete complex analysis methods. As a consequence, we obtain a simple exact formula for the scaling limit of the energy field one-point function in terms of the hyperbolic metric. This confirms the predictions originating in physics, but also provides a higher precision.     

Multi-funnel optimization using Gaussian underestimation

In several applications, underestimation of functions has proven to be a helpful tool for global optimization. In protein–ligand docking problems as well as in protein structure prediction, single convex quadratic underestimators have been used to approximate the location of the global minimum point. While this approach has been successful for basin-shaped functions, it is not suitable for energy functions with more than one distinct local minimum with a large magnitude. Such functions may contain several basin-shaped components and, thus, cannot be underfitted by a single convex underestimator. In this paper, we propose using an underestimator composed of several negative Gaussian functions. Such an underestimator can be computed by solving a nonlinear programming problem, which minimizes the error between the data points and the underestimator in the L ¹ norm. Numerical results for simulated and actual docking energy functions are presented.     

A scaling and energy equality preserving approximation for the 3D Navier-Stokes equations in the finite energy case

We discuss a new model (inspired by the work of Vishik and Fursikov) approximating the 3D Navier-Stokes equations, which preserves the scaling as in the Navier-Stokes equations and thus allows the study of self-similar solutions. Using some energy estimates and Leray’s limiting process, we show the existence of a solution of this model in the finite energy case, and the energy equality and inequality fulfilled by it. This approximation can be shown to converge to the Navier-Stokes equations using a mild approach based on the approximated pressure, and the solution satisfies Scheffer’s local energy inequality, an essential tool for proving Caffarelli, Kohn and Nirenberg’s regularity criterion. We also give a partial result of self-similarity satisfied by the approximated solution in the infinite energy case.     

Phenomenological theory of surface effects in ferroelectrics and its relationship with transverse Ising model

The relationship between the transverse field Ising model and the Landau phenomenological theory for ferroelectrics is analyzed, and the Landau free energy expression for ferroelectrics having surfaces is derived. It is pointed out that the traditional expression in which the surface integral has only a term of the square polarization is valid only for special cases, in general a term of the polarization to the four should be included as well. By use of the newly derived free energy expression, the thickness-dependence of the spontaneous polarization and Curie temperature of ferroelectric films is calculated; thereby some experimental results incompatible with the traditional phenomenological theory are successfully explained.     

Reservoir operations optimization via fuzzy criterion decision processes

In this paper, we propose the treatment of complex reservoir operation problems via our newly developed tool of fuzzy criterion decision processes. This novel approach has been shown to be a more flexible and useful analysis tool especially when it is desirable to incorporate an expert’s knowledge into the decision models. Additionally, it has been demonstrated that this form of decision models will usually result in an optimal solution, which guarantees the highest satisfactory degree. We provide a practical exemplification procedure for the models presented as well as an application example.     

An introduction to infinite particle systems

In 1970, Spitzer wrote a paper called “Interaction of Markov processes” in which he introduced several classes of interacting particle systems. These processes and other related models, collectively referred to as infinite particle systems, have been the object of much research in the last ten years. In this paper we will survey some of the results which have been obtained and some of the open problems, concentrating on six overlapping classes of processes: the voter model, additive processes, the exponential family, one dimensional systems, attractive systems, and the Ising model.