NIPSDec, 2014

反铁磁伊辛模型的结构学习

PDF
TL;DR本文研究了从 i.i.d 样本中学习离散无向图结构的计算复杂性。首先，我们指出学习带有噪声的奇偶校验可以作为学习图模型的一个特殊情况。其次，我们提出一个有关统计算法的条件，它们无法在 $p$ 最大度数为 $d$ 的一般图模型上有效学习，因此需要限制模型类的大小。除了对图的结构性假设之外，我们还引入相关性衰减度量，研究了反铁磁模型。我们提供了一个性能介于 $O (p^2)$ 和 $O (p^{d+2})$ 之间的算法。
graphical modelscomputational complexitylearningcorrelation decayantiferromagnetic models
发现论文，激发创造
  • 在任意图上高效学习 Ising 模型

    本文探讨了如何通过简单的贪心算法来学习任意边界度数的 Ising 模型，在保证模型可辨识度的情况下，仅需用时 O (p^2) 即可还原图结构，并且该结构性质可独立运用于其他相关研究。

    Nov, 2014

  • 关于学习伊辛模型的信息论极限

    本文提出了一种计算 Ising 模型底层图形恢复的样本复杂性下界的通用框架，其中隔离出两个关键图形结构成分，可以用于指定样本复杂度下界。

    Nov, 2014

  • 哪些图形模型难以学习？

    我们研究了从独立同分布采样中学习 Ising 模型（成对二元 Markov 随机场）的结构问题。通过分析多个具体例子，我们发现当 Markov 随机场发展为远程相互关系时，具有低复杂度算法的方法的系统性失效。更具体地说，这种现象似乎与 Ising 模型的相变有关（但并不与之重合）。

    Oct, 2009

  • 具潜变量的循环图模型学习：高效方法与保证

    研究了隐变量图模型中的结构估计问题，提出了一种计算高效且保证正确性的方法，并应用于局部树状结构的模型及相关衰减的模型，特别地，对于伊辛模型，该方法能与采样要求的下界接近。

    Mar, 2012

  • 交互筛选：高效和样本最优学习 Ising 模型

    提出了一种新的，具有物理解释的统计估计量来学习未知 Ising 模型的基础图，该估计量使用凸优化计算速度快，并且在适当的正则化下，可以以对数的速度回复基础图。

    May, 2016

  • 学习伊辛模型动力学的样本复杂性指数降低

    该研究探讨了如何从动态过程的相关样本中重构二值图形模型，并分析了基于交互筛选目标和条件似然损失的两个估计器的样本复杂性。我们发现，对于来自远离平衡的动态过程的样本，样本复杂度与混合速度快的动态过程相比呈指数级下降。

    Apr, 2021

  • 马尔可夫网络结构的贪婪学习

    提出了一种新的自然算法，用于从样本中学习一般离散图形模型（即马尔可夫随机场）的图结构，它是一种贪心的算法，并且具有较低的计算复杂度，并且通过节点度数、图大小以及因子图的环来表征其样本复杂度，在此基础上将其专门用于 Ising 模型。

    Feb, 2012

  • Ising 模型的高维结构估计：局部分离准则

    本文提出了一种基于经验条件变差距离阈值处理的简单算法，针对高维 Ising (图形) 模型选择问题。对于具有稀疏局部分离器的图形族，该方法将是有效的，被用来作为结构估计的基准。我们在该文章中还建立了结构估计的非渐近必要和充分条件。

    Jul, 2011

  • Ising 模型的最优结构和参数学习

    本文介绍一种名为 Interaction Screening 的新方法，使用本地优化问题准确估计模型参数，这个算法在信息论上优化样本数量的条件下可以实现完美的图形结构恢复，证明了 Interaction Screening 方法是一种准确、可行和最优的通用逆向 Ising 问题解决技术。

    Dec, 2016

  • 多项式时间与样本复杂度内学习线性结构方程模型

    本文研究了从观察数据中学习线性结构方程模型（SEMs）的算法问题，旨在实现计算和统计效率，解决较一般的识别问题并没有考虑 “信仰” 假设的情形，提供了一个高效的算法，能够在不同噪声分布的情况下恢复 SEM 的有向无环图结构。

    Jul, 2017