从样本中重建马尔科夫随机场:一些简单的观察和算法
通过建立适当的零和游戏,采用概念上的方法来证明相互信息的下限,进而推广到具有高阶交互作用的任意马尔科夫随机场,从而获得在 n 个节点上学习具有 r 阶相互作用的有界次数图上的马尔科夫随机场的算法,样本复杂度为 log (n),时间复杂度为 n^r。
May, 2017
提出了一种新的自然算法,用于从样本中学习一般离散图形模型(即马尔可夫随机场)的图结构,它是一种贪心的算法,并且具有较低的计算复杂度,并且通过节点度数、图大小以及因子图的环来表征其样本复杂度,在此基础上将其专门用于 Ising 模型。
Feb, 2012
研究二元马尔可夫随机场中,图形选择问题在高维情况下的信息论局限性,为具有最多 k 条边的 p 个定点图的类 $Gpk$ 以及最高 degree 不超过 d 的 p 个定点图的类 $Gpd$,提出了正确图形选择的必要和充分条件,并建立了一个图形译码器,该译码器适用于样本量 n>c'k² log (p) 和 n>c'd³ log (p)。
May, 2009
研究了最小二乘线性回归的问题,其中数据点依赖于并从马尔可夫链中采样。在不同的噪声设置下,建立了关于底层马尔可夫链混合时间 $\tau_{mix}$ 的尖锐信息理论极小值下界来解决此问题。我们发现,与独立数据的优化相比,具有马尔可夫数据的优化通常更加困难,一个只在大约 $ ilde {\Theta}(\tau_{mix})$ 个样本中工作的平凡算法 (SGD-DD) 是极小化最优的。此外,我们还研究了实践中出现的结构化数据集,例如高斯自回归动态,它们能否拥有更高效的优化方案。令人惊讶的是,即使在这个特定的自然环境下,具有一定步长的随机梯度下降法与常数并没有比 SGD-DD 算法更好。相反,我们提出了一种基于体验复盘的算法 —— 一种流行的强化学习技术 —— 它可以实现更好的误差率。我们的改进速率是第一个在有趣的马尔可夫链上优于 SGD-DD 的算法之一,也为在实践中支持使用经验回放提供了首个理论分析。
Jun, 2020
本文探讨了在高维场景下,从样本中学习成对图模型的结构问题。我们首先讨论了向前向后贪心算法在一般统计模型中应用的稀疏性一致性(稀疏模式恢复)特性。然后,我们将此算法特化到通过邻域估计学习离散图模型的结构问题上。我们的结果保证了样本数 n 随着问题规模 p 的增加而缩放,并且算法仅需要具有受限强凸性条件,这通常比不可表示性假设容易得多。
Jul, 2011
研究了隐变量图模型中的结构估计问题,提出了一种计算高效且保证正确性的方法,并应用于局部树状结构的模型及相关衰减的模型,特别地,对于伊辛模型,该方法能与采样要求的下界接近。
Mar, 2012
提出一种基于马尔科夫随机场的方法,考虑了相互依赖的二元标签,实现了对相关数据的统计有效估计, 并在逻辑回归、稀疏逻辑回归和神经网络等多个领域进行了探究。结果表明该方法可以更准确地估计参数,比传统的回归方法效果更好。在 Cora、Citeseer 和 Pubmed 等数据集中验证了该方法的有效性。
Jul, 2021
给出一种用于学习 Markov 随机场(MRF)或无向图模型的简单的、乘性权重更新算法 ——Sparsitron 算法,特别适用于学习 t 阶 MRFs 结构,并具有近乎最优的样本复杂度和多项式的运行时间。同时,该算法还可以学习 Ising 模型上的参数,生成接近真实 MRF 的统计距离假设,并给出了学习稀疏广义线性模型(GLMs)的解决方案。
Jun, 2017