Necessary conditions for consistent set-based graphical model selection
Necessary conditions for consistent set-based graphical model selection
复制标题
一致的基于集合的图模型选择的必要条件
DOI：
10.1109/isit.2011.6034133
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
José M. F. Moura
中科院分区：
文献类型：
--
作者：
Divyanshu Vats;José M. F. Moura
图模型选择的目标是估计分布背后的图，这是一个已知的NP-Hard问题。一个重要的问题是研究图形模型选择算法性能的理论极限。特别是，在给定基本分布的参数的情况下，我们希望找到精确图估计所需样本数量的下限。在推导这些理论界限时，通常将学习问题视为通信问题，其中观测对应于噪声消息，并且解码问题从观测推断图。当前对图形模型选择算法的分析仅限于研究输出唯一图形的图形估计器。在本文中，我们考虑输出一组图的图估值器，从而导致基于集合的图模型选择(SB-GMS)。这与列表解码有关，在列表解码中，解码器输出可能的码字列表而不是单个码字。我们的主要贡献是为各种类型的图形模型推导出精确SB-GMS的必要条件，并显示一致性估计所需的样本数量的减少。在给定图参数的情况下，我们得到了基于集合估计的基数的必要条件。
Graphical model selection, where the goal is to estimate the graph underlying a distribution, is known to be an NP-hard problem. An important issue is to study theoretical limits on the performance of graphical model selection algorithms. In particular, given parameters of the underlying distribution, we want to find a lower bound on the number of samples required for accurate graph estimation. When deriving these theoretical bounds, it is common to treat the learning problem as a communication problem where the observations correspond to noisy messages and the decoding problem infers the graph from the observations. Current analysis of graphical model selection algorithms is limited to studying graph estimators that output a unique graph. In this paper, we consider graph estimators that output a set of graphs, leading to set-based graphical model selection (SB-GMS). This has connections to list-decoding where a decoder outputs a list of possible codewords instead of a single codeword. Our main contribution is to derive necessary conditions for accurate SB-GMS for various classes of graphical models and show reduction in the number of samples required for consistent estimation. Further, we derive necessary conditions on the cardinality of the set-based estimates given graph parameters.
影响因子：
2.7
作者：
Guo, Jian;Levina, Elizaveta;Zhu, Ji
通讯作者：
Zhu, Ji