Structure learning of antiferromagnetic Ising models
Structure learning of antiferromagnetic Ising models
复制标题
反铁磁伊辛模型的结构学习
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Devavrat Shah
中科院分区：
文献类型：
--
作者：
Guy Bresler;D. Gamarnik;Devavrat Shah
在本文中，我们研究学习的计算复杂性的图结构的离散无向图形模型从i.i.d.样品我们的第一个结果是一个无条件的计算下界Ω（pd/2）的学习一般图形模型的p个节点的最大程度d，为类的所谓的统计算法最近推出的Feldman等人。[1]。该构造与计算学习理论中臭名昭著的困难的噪声学习奇偶校验问题有关。我们的下限表明，在不限制模型类的情况下，Bresler，Mossel和Sly [2]的穷举搜索算法所需的O（pd+2）运行时间不能得到显着改善。
除了对图的结构假设，例如它是树、超树、树状等，最近许多关于结构学习的论文都假设模型具有相关衰减特性。事实上，专注于铁磁伊辛模型，Bento和Montanari [3]表明，当相互作用强度超过与相关衰减阈值相关的数字时，所有已知的低复杂度算法都无法学习简单的图形。我们的第二组结果给出了一类具有相反行为的排斥（反铁磁）模型：非常强的相互作用允许在时间O（p2）内进行有效学习。我们提供了一种算法，其性能根据排斥力的强度在O（p2）和O（pd+2）之间插值。
In this paper we investigate the computational complexity of learning the graph structure underlying a discrete undirected graphical model from i.i.d. samples. Our first result is an unconditional computational lower bound of Ω(pd/2) for learning general graphical models on p nodes of maximum degree d, for the class of so-called statistical algorithms recently introduced by Feldman et al. [1]. The construction is related to the notoriously difficult learning parities with noise problem in computational learning theory. Our lower bound suggests that the O(pd+2) runtime required by Bresler, Mossel, and Sly's [2] exhaustive-search algorithm cannot be significantly improved without restricting the class of models.
Aside from structural assumptions on the graph such as it being a tree, hypertree, tree-like, etc., many recent papers on structure learning assume that the model has the correlation decay property. Indeed, focusing on ferromagnetic Ising models, Bento and Montanari [3] showed that all known low-complexity algorithms fail to learn simple graphs when the interaction strength exceeds a number related to the correlation decay threshold. Our second set of results gives a class of repelling (antiferromagnetic) models that have the opposite behavior: very strong interaction allows efficient learning in time O(p2). We provide an algorithm whose performance interpolates between O(p2) and O(pd+2) depending on the strength of the repulsion.