Parameter Estimation for Undirected Graphical Models with Hard\n Constraints

2020/08/22 by Bhaswar B. Bhattacharya, Bhattacharya, Bhaswar B., Kavita Ramanan +1 · 4 citations
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Bayesian Modeling and Causal Inference #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2008.09925

Abstract

The hardcore model on a graph G with parameter \λ>0 is a probability\nmeasure on the collection of all independent sets of G, that assigns to each\nindependent set I a probability proportional to \λ^|I|. In this\npaper we consider the problem of estimating the parameter \λ given a\nsingle sample from the hardcore model on a graph G. To bypass the\ncomputational intractability of the maximum likelihood method, we use the\nmaximum pseudo-likelihood (MPL) estimator, which for the hardcore model has a\nsurprisingly simple closed form expression. We show that for any sequence of\ngraphs G_{N N\≥ 1}, where G_N is a graph on N vertices, the MPL\nestimate of \λ is \√ N-consistent, whenever the graph sequence has\nuniformly bounded average degree. We then derive sufficient conditions under\nwhich the MPL estimate of the activity parameters is \√ N-consistent given\na single sample from a general H-coloring model, in which restrictions\nbetween adjacent colors are encoded by a constraint graph H. We verify the\nsufficient conditions for models where there is at least one unconstrained\ncolor as long as the graph sequence has uniformly bounded average degree. This\napplies to many H-coloring examples such as the Widom-Rowlinson and\nmulti-state hard-core models. On the other hand, for the q-coloring model,\nwhich falls outside this class, we show that consistent estimation may be\nimpossible even for graphs with bounded average degree. Nevertheless, we show\nthat the MPL estimate is \√ N-consistent in the q-coloring model when\n G_{N N\≥ 1} has bounded average double neighborhood. The presence of\nhard constraints, as opposed to soft constraints, leads to new challenges, and\nour proofs entail applications of the method of exchangeable pairs as well as\ncombinatorial arguments that employ the probabilistic method.\n

Cited by

• Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue
• Estimating Ising Models in Total Variation Distance
• Learning CNF formulas from uniform random solutions in the local lemma regime
• Learning Ising Models under Hard Constraints using One Sample

Related

• Learning Hard-Constrained Models with One Sample
• Hardness of parameter estimation in graphical models
• Maximum likelihood thresholds via graph rigidity
• Information-theoretic limits of selecting binary graphical models in high dimensions
• The Maximum Likelihood Threshold of a Graph