We consider the problem of estimating the parameters of a Markov Random Field
with hard-constraints using a single sample. As our main running examples, we
use the $k$-SAT and the proper coloring models, as well as general $H$-coloring
models; for all of these we obtain both positive and negative results. In
contrast to the soft-constrained case, we show in particular that single-sample
estimation is not always possible, and that the existence of an estimator is
related to the existence of non-satisfiable instances.
Our algorithms are based on the pseudo-likelihood estimator. We show variance
bounds for this estimator using coupling techniques inspired, in the case of
$k$-SAT, by Moitra's sampling algorithm (JACM, 2019); our positive results for
colorings build on this new coupling approach. For $q$-colorings on graphs with
maximum degree $d$, we give a linear-time estimator when $q>d+1$, whereas the
problem is non-identifiable when $q\leq d+1$. For general $H$-colorings, we
show that standard conditions that guarantee sampling, such as Dobrushin's
condition, are insufficient for one-sample learning; on the positive side, we
provide a general condition that is sufficient to guarantee linear-time
learning and obtain applications for proper colorings and permissive models.
For the $k$-SAT model on formulas with maximum degree $d$, we provide a
linear-time estimator when $k\gtrsim 6.45\log d$, whereas the problem becomes
non-identifiable when $k\lesssim \log d$.

使用单个样本估计具有硬约束的马尔可夫随机场的参数，算法基于伪似然估计器，对于 $k$-SAT 和 proper coloring 模型以及一般的 $H$-coloring 模型，不仅获得了正面结果，还获得了负面结果。