论文标题
具有硬约束的无向图形模型的参数估计
Parameter Estimation for Undirected Graphical Models with Hard Constraints
论文作者
论文摘要
图形$ g $上的硬核模型，带有参数$λ> 0 $是所有独立集合的$ g $集合的概率度量，它分配给每个独立的集合$ i $ a $ a概率与$λ^{| i |} $成比例。在本文中，我们考虑了估计参数$λ$的问题，给定图形$ g $上的铁杆模型的单个样本。为了绕过最大似然法的计算棘手性，我们使用了最大伪样（MPL）估计器，该估计量对于硬核模型具有令人惊讶的简单封闭形式表达式。我们表明，对于任何图序列$ \ {g_n \} _ {n \ geq 1} $，其中$ g_n $是$ n $ vertices上的图，$λ$的mpl估计值为$ \ sqrt n $ - 一致，只要图形序列具有均匀界限的平均值。然后，我们得出了足够的条件，在该条件下，从一般$ h $颜色模型中的单个样本中，活动参数的MPL估计为$ \ sqrt n $ - 一致，其中相邻颜色之间的限制由约束图$ h $编码。只要图序列具有统一的平均程度，我们就会验证至少有一种不受约束的颜色的模型的足够条件。这适用于许多$ h $颜色的示例，例如Widom-Rowlinson和多状态硬核模型。另一方面，对于$ q $颜色的模型（属于此类），我们表明，即使对于平均水平的图表，一致的估计也是不可能的。尽管如此，我们表明，当$ \ {g_n \} _ {n \ geq 1} $具有有限的平均双邻域时，MPL估算为$ \ sqrt n $ - consistent。与软限制相反，硬约束的存在导致了新的挑战，我们的证据需要对可交换对的方法以及采用概率方法的组合参数进行应用。
The hardcore model on a graph $G$ with parameter $λ>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 $λ^{|I|}$. In this paper we consider the problem of estimating the parameter $λ$ 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 $λ$ is $\sqrt N$-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 $\sqrt N$-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 $\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.
