Learning Markov graphs up to edit distance
Learning Markov graphs up to edit distance
复制标题
DOI：
10.1109/isit.2012.6284018
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
A. Das;Praneeth Netrapalli;S. Sanghavi;S. Vishwanath
中科院分区：
文献类型：
--
作者：
A. Das;Praneeth Netrapalli;S. Sanghavi;S. Vishwanath
提出了一种基于率失真的马尔可夫图学习方法。它提供了任何算法学习概率分布的马尔可夫图结构所需的样本数量的下限，直到编辑距离。我们首先证明了一个一般的结果，任何概率分布，然后专门为伊辛和高斯模型。特别是，对于度最多为d的p个变量的伊辛和高斯模型，我们证明了任何算法都需要至少Ω（（d-s/p）log p）个样本来学习编辑距离s的图结构。我们的边界代表一个强匡威;即，我们表明，对于较低数量的样本，随着问题大小的增加，错误的概率变为1。这些结果表明，在不付出编辑距离误差的显著代价的情况下，样本复杂性的实质性增益可能是不可能的。
This paper presents a rate distortion approach to Markov graph learning. It provides lower bounds on the number of samples required for any algorithm to learn the Markov graph structure of a probability distribution, up to edit distance. We first prove a general result for any probability distribution, and then specialize it for Ising and Gaussian models. In particular, for both Ising and Gaussian models on p variables with degree at most d, we show that at least Ω((d - s/p)log p) samples are required for any algorithm to learn the graph structure up to edit distance s. Our bounds represent a strong converse; i.e., we show that for a lower number of samples, the probability of error goes to 1 as the problem size increases. These results show that substantial gains in sample complexity may not be possible without paying a significant price in edit distance error.