论文标题
吉布斯分布的参数估计
Parameter estimation for Gibbs distributions
论文作者
论文摘要
我们考虑Gibbs分布，它们是离散空间$ω$的概率分布的家族，具有$μ^ω_β（ω）\ propto e^e^{βH（ω）} $ $β$在间隔$中的$β$的概率函数\ cup [1，n] $。分区函数是归一化因子$ z（β）= \ sum_ {ω\inΩ} e^{βH（ω）} $。 这些分布的两个重要参数是log分区比率$ q = \ log \ tfrac {z（β_ {\ max}）}} {z（β_ {\ min}）} $，计数$ c_x = | h^{ - 1}（x）（x）| $。这些与许多物理应用和采样算法中的系统参数相关。 我们的第一个主要结果是使用大约$ \ tilde o（\ frac {q} {\ varepsilon^2}）$示例估算计数$ c_x $（\ frac {q} {\ varepsilon^2}）$样品，用于一般吉布斯分布，$ \ tilde o（\ frac {n^2} {\ varepsilon^2} {\ varepsilon^2} $ section in inst in in section in in Integer（参数），我们证明这是对数因素的最佳选择。我们用改进的算法来计算连接子图，独立集和完美匹配的算法。 作为关键子例程，我们还开发了使用$ \ tilde o（\ frac {q} {\ varepsilon^2}）$示例来计算分区函数$ z $的算法，用于一般的Gibbs分布，并使用$ \ tilde o（\ frac {\ frac {n^2} {n^2} {n^2} {\ varepsilon^2}
We consider Gibbs distributions, which are families of probability distributions over a discrete space $Ω$ with probability mass function of the form $μ^Ω_β(ω) \propto e^{βH(ω)}$ for $β$ in an interval $[β_{\min}, β_{\max}]$ and $H( ω) \in \{0 \} \cup [1, n]$. The partition function is the normalization factor $Z(β)=\sum_{ω\inΩ}e^{βH(ω)}$. Two important parameters of these distributions are the log partition ratio $q = \log \tfrac{Z(β_{\max})}{Z(β_{\min})}$ and the counts $c_x = |H^{-1}(x)|$. These are correlated with system parameters in a number of physical applications and sampling algorithms. Our first main result is to estimate the counts $c_x$ using roughly $\tilde O( \frac{q}{\varepsilon^2})$ samples for general Gibbs distributions and $\tilde O( \frac{n^2}{\varepsilon^2} )$ samples for integer-valued distributions (ignoring some second-order terms and parameters), and we show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs, independent sets, and perfect matchings. As a key subroutine, we also develop algorithms to compute the partition function $Z$ using $\tilde O(\frac{q}{\varepsilon^2})$ samples for general Gibbs distributions and using $\tilde O(\frac{n^2}{\varepsilon^2})$ samples for integer-valued distributions.
