在只观测状态变化的情况下，高效学习伊辛模型的结构与参数。
Better Models and Algorithms for Learning Ising Models from Dynamics
- 仅观测配置变化，而非所有更新尝试，更贴近真实场景。
- 对最大度为d的模型，可在poly(d)·n²log n时间内恢复依赖图。
- 适用于多种马尔可夫链，为动态学习提供新方法，适合统计物理与复杂系统研究者。
我们研究从关联马尔可夫链演化中学习伊辛模型结构与参数的问题。以往工作假设可观测所有站点更新尝试（即使未改变状态），该强观测模型虽有效但不现实。本文首次提出在仅观测配置变化这一更自然、更弱的观测模型下，高效学习伊辛模型的算法。对于最大度为d的模型，算法在poly(d)·n²log n时间内恢复依赖图，并在额外˜O(2^d n)时间内估计参数，性能上接近经典i.i.d.设定下的最优结果。分析还推广至更广泛的可逆单点马尔可夫链，包括流行的Metropolis链，利用可逆链的稳健性质实现理论保证。
原文摘要 · Abstract (English)
We study the problem of learning the structure and parameters of the Ising model, a fundamental model of high-dimensional data, when observing the evolution of an associated Markov chain. A recent line of work has studied the natural problem of learning when observing an evolution of the well-known Glauber dynamics [Bresler, Gamarnik, Shah, IEEE Trans. Inf. Theory 2018, Gaitonde, Mossel STOC 2024], which provides an arguably more realistic generative model than the classical i.i.d. setting. However, this prior work crucially assumes that all site update attempts are observed, \emph{even when this attempt does not change the configuration}: this strong observation model is seemingly essential for these approaches. While perhaps possible in restrictive contexts, this precludes applicability to most realistic settings where we can observe \emph{only} the stochastic evolution itself, a minimal and natural assumption for any process we might hope to learn from. However, designing algorithms that succeed in this more realistic setting has remained an open problem [Bresler, Gamarnik, Shah, IEEE Trans. Inf. Theory 2018, Gaitonde, Moitra, Mossel, STOC 2025]. In this work, we give the first algorithms that efficiently learn the Ising model in this much more natural observation model that only observes when the configuration changes. For Ising models with maximum degree $d$, our algorithm recovers the underlying dependency graph in time $\mathsf{poly}(d)\cdot n^2\log n$ and then the actual parameters in additional $\widetilde{O}(2^d n)$ time, which qualitatively matches the state-of-the-art even in the i.i.d. setting in a much weaker observation model. Our analysis holds more generally for a broader class of reversible, single-site Markov chains that also includes the popular Metropolis chain by leveraging more robust properties of reversible Markov chains.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。