Parameter Estimation for Undirected Graphical Models With Hard Constraints

DOI10.1109/TIT.2021.3094404MaRDI QIDQ5032537zbMATH OpenOpenAlexFDO

Authors Bhaswar B. Bhattacharya, Kavita Ramanan

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.09925

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random fields (60G60) Parametric inference (62F99) Inference from stochastic processes (62M99)

Abstract: 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 $lambd{a}^{|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}_{Ngeq1}$, where $G_N$ is a graph on $N$ vertices, the MPL estimate of $lambda$ is $sqrtN$-consistent, whenever the graph sequence has uniformly bounded average degree. We then derive sufficient conditions under which the MPL estimate of the activity parameters is $sqrtN$-consistent given a single sample from a general $H$-coloring model, in which restrictions between adjacent colors are encoded by a constraint graph $H$. We verify the sufficient conditions for models where there is at least one unconstrained color 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 consistent estimation may be impossible even for graphs with bounded average degree. Nevertheless, we show that the MPL estimate is $sqrtN$-consistent in the $q$-coloring model when ${G_N}_{Ngeq1}$ 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.

Recommendations

• Constrained parameter estimation with uncertain priors for Bayesian networks
• Parameterization and fitting of a class of discrete graphical models
• Constrained likelihood for reconstructing a directed acyclic Gaussian graph
• Estimation of graphical models through structured norm minimization
• scientific article; zbMATH DE number 7085065
• Estimation of graphical models using the L1,2 norm
• Parameter priors for directed acyclic graphical models and the characterization of several probability distributions
• Graphical models for imprecise probabilities
• A constrained \(\ell1\) minimization approach for estimating multiple sparse Gaussian or nonparanormal graphical models

Cited in

(3)

• Constrained likelihood for reconstructing a directed acyclic Gaussian graph
• One-shot learning for k-SAT
• One-shot learning for \(k\)-SAT

This page was built for publication: Parameter Estimation for Undirected Graphical Models With Hard Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032537)