Estimating Structurally Similar Graphical Models

Saurabh Sihag; Ali Tajer

首页> 外文期刊>IEEE Transactions on Information Theory >Estimating Structurally Similar Graphical Models

【24h】

Estimating Structurally Similar Graphical Models

机译：Estimating Structurally Similar Graphical Models

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

This paper considers the problem of estimating the structure of structurally similar graphical models in high dimensions. This problem is pertinent in multi-modal or multi-domain datasets that consist of multiple information domains, each modeled by one probabilistic graphical model (PGM), e.g., in brain network modeling using different neuroimaging modalities. Induced by an underlying shared causal source, the domains, and subsequently their associated PGMs, can have structural similarities. This paper focuses on Gaussian and Ising models and characterizes the information-theoretic sample complexity of estimating the structures of a pair of PGMs in the degree-bounded and edge-bounded subclasses. The PGMs are assumed to have $p$ nodes with distinct and unknown structures. Their similarity is accounted for by assuming that a pre-specified set of $q$ nodes form identical subgraphs in both PGMs. Necessary and sufficient conditions on the sample complexity for a bounded probability of error are characterized. The necessary conditions are information-theoretic (algorithm-independent), delineating the statistical difficulty of the problem. The sufficient conditions are based on deploying maximum likelihood decoders. While the specifics of the results vary across different subclasses and parameter regimes, one key observation is that in specific subclasses and regimes, the sample complexity varies with $p$ and $q$ according to $Theta (log (p-q))$ . For Ising models, a low complexity, online structure estimation (learning) algorithm based on multiplicative weights is also proposed. Numerical evaluations are also included to illustrate the interplay among different parameters on the sample complexity when the structurally similar graphs are recovered by a maximum likelihood-based graph decoder and the proposed online estimation algorithm.

著录项

来源
《IEEE Transactions on Information Theory》 |2023年第2期|1093-1124|共32页
作者
Saurabh Sihag; Ali Tajer;
展开▼
作者单位

Department of Electrical, Computer, Systems Engineering, Rensselaer Polytechnic Institute, Troy, NY, USA;

Department of Neurology, University of Pennsylvania, Philadelphia, PA, USA;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类通信;
关键词
Complexity theory; Graphical models; Random variables; Inference algorithms; Data models; Brain modeling; Probabilistic logic;

Estimating Structurally Similar Graphical Models

摘要

著录项

相关主题

期刊订阅