Combinatorial Inference for Graphical Models
We propose a new family of combinatorial inference problems for graphical models. Unlike classical statistical inference where the main interest is point estimation or parameter testing, combinatorial inference aims at testing the global structure of the underlying graph. Examples include testing the graph connectivity, the presence of a cycle of certain size, or the maximum degree of the graph. To begin with, we develop a unified theory for the fundamental limits of a large family of combinatorial inference problems. We propose new concepts including structural packing and buffer entropies to characterize how the complexity of combinatorial graph structures impacts the corresponding minimax lower bounds. On the other hand, we propose a family of novel and practical structural testing algorithms to match the lower bounds. We provide thorough numerical results on both synthetic graphical models and brain networks to illustrate the usefulness of these proposed methods.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Message Passing and Combinatorial Optimization
Graphical models use the intuitive and well-studied methods of graph theory to implicitly represent dependencies between variables in large systems. They can model the global behaviour of a complex system by specifying o…
ClusteringCombinatorial OptimizationTraveling Salesman ProblemThe Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference
We study the hypothesis testing problem of inferring the existence of combinatorial structures in undirected graphical models. Although there exist extensive studies on the information-theoretic limits of this probl…
Two-sample testingGlobal MAP-Optimality by Shrinking the Combinatorial Search Area with Convex Relaxation
We consider energy minimization for undirected graphical models, also known as MAP-inference problem for Markov random fields. Although combinatorial methods, which return a provably optimal integral solution of the prob…
Hinge-loss Markov Random Fields: Convex Inference for Structured Prediction
Graphical models for structured domains are powerful tools, but the computational complexities of combinatorial prediction spaces can force restrictions on models, or require approximate inference in order to be tractabl…
Structured PredictionA Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing
Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems in natural language processing (NLP). This tu…
Combinatorial Optimization