On the Difficulty of Selecting Ising Models With Approximate Recovery
On the Difficulty of Selecting Ising Models With Approximate Recovery
复制标题
论近似回收率Ising模型的选取困难
DOI：
10.1109/tsipn.2016.2596439
复制
发表时间：
2016
影响因子：
3.2
通讯作者：
V. Cevher
中科院分区：
文献类型：
--
作者：
J. Scarlett;V. Cevher
在本文中，我们考虑的问题，估计与伊辛模型的基本图给定的独立和同分布的样本数。我们采用了近似的恢复标准，允许一些错过的边缘或不正确的边缘，与广泛研究的精确恢复问题。我们的主要研究结果提供了信息理论的下界的样本复杂性的图类施加限制的边缘，最大程度，和其他属性的数量。我们确定了广泛的情况下，无论是常数因子或对数因子，我们的下限匹配最好的已知下限的确切恢复标准，其中几个是已知的紧或近紧。因此，在这些情况下，近似恢复在极大极小意义上具有与精确恢复类似的困难。通过对Fano不等式的修改，沿着适当设计的图系综，我们得到了近似恢复准则的界，这些图系综大致可以分为两类：1）包含多个孤立边或团的图，因此很难与空图区分开; 2）包含某些节点组高度相关的图，因此难以精确确定哪些边连接它们。我们支持我们的理论结果，这些合奏与数值实验。
In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt an approximate recovery criterion that allows for a number of missed edges or incorrectly included edges, in contrast with the widely studied exact recovery problem. Our main results provide information-theoretic lower bounds on the sample complexity for graph classes imposing constraints on the number of edges, maximal degree, and other properties. We identify a broad range of scenarios where, either up to constant factors or logarithmic factors, our lower bounds match the best known lower bounds for the exact recovery criterion, several of which are known to be tight or near-tight. Hence, in these cases, approximate recovery has a similar difficulty to exact recovery in the minimax sense. Our bounds are obtained via a modification of Fano's inequality for handling the approximate recovery criterion, along with suitably designed ensembles of graphs that can broadly be classed into two categories: 1) those containing graphs that contain several isolated edges or cliques and are thus difficult to distinguish from the empty graph; 2) those containing graphs for which certain groups of nodes are highly correlated, thus making it difficult to determine precisely which edges connect them. We support our theoretical results on these ensembles with numerical experiments.