Parameter Estimation for Undirected Graphical Models With Hard Constraints.

The hardcore model on a graph $G$ with parameter $\lambda > 0$ is a probability measure on the collection of all independent sets of $G$ , that assigns to each independent set $I$ a probability proportional to $\lambda ^{|I|}$. In this paper we consider the problem of estimating the parameter $\lambda $ given a single sample from the hardcore model on a graph $G$. To bypass the computational intractability of the maximum likelihood method, we use the maximum pseudo-likelihood (MPL) estimator, which for the hardcore model has a surprisingly simple closed form expression. We show that for any sequence of graphs $\{G_{N}\}_{N \geq 1}$ , where $G_{N}$ is a graph on $N$ vertices, the MPL estimate of $\lambda $ is $\sqrt {N}$ -consistent (that is, it converges to the true parameter at rate $1/\sqrt {N}$), whenever the graph sequence has uniformly bounded average degree. We then extend our methods to obtain estimates for the vector of activity parameters in general $H$ -coloring models, in which restrictions between adjacent colors are encoded by a constraint graph $H$. These constitute an important class of Markov random fields that includes all hard-constraint models, which arise in a broad array of fields including combinatorics, statistical physics, and communication networks. Given a single sample from an $H$ -coloring model, we derive sufficient conditions under which the MPL estimate is $\sqrt {N}$ -consistent. Moreover, we verify the sufficient conditions for $H$ -coloring models for which there is at least one ‘unconstrained’ color (that is, there exists at least one vertex in the constraint graph $H$ that is connected to all vertices), as long as the graph sequence has uniformly bounded average degree. This applies to many $H$ -coloring examples such as the Widom-Rowlinson and multi-state hard-core models. On the other hand, for the $q$ -coloring model, which falls outside this class, we show that the condition can fail and consistent estimation may be impossible even for graphs with bounded average degree. Nevertheless, we show that the MPL estimate is $\sqrt {N}$ -consistent in the $q$ -coloring model when $\{G_{N}\}_{N \geq 1}$ has bounded average double neighborhood. The presence of hard constraints, as opposed to soft constraints, leads to new challenges, and our proofs entail applications of the method of exchangeable pairs as well as combinatorial arguments that employ the probabilistic method. [ABSTRACT FROM AUTHOR]