Local Algorithms for Approximate Inference in Minor-Excluded Graphs
We present a new local approximation algorithm for computing MAP and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say G. Our algorithm is based on decomposing G into appropriately chosen small components; computing estimates locally in each of these components and then producing a good global solution. We prove that the algorithm can provide approximate solution within arbitrary accuracy when $G$ excludes some finite sized graph as its minor and G has bounded degree: all Planar graphs with bounded degree are examples of such graphs. The running time of the algorithm is $\Theta(n)$ (n is the number of nodes in G), with constant dependent on accuracy, degree of graph and size of the graph that is excluded as a minor (constant for Planar graphs). Our algorithm for minor-excluded graphs uses the decomposition scheme of Klein, Plotkin and Rao (1993). In general, our algorithm works with any decomposition scheme and provides quantifiable approximation guarantee that depends on the decomposition scheme.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Distribution-Free Inference for the Regression Function of Binary Classification
One of the key objects of binary classification is the regression function, i.e., the conditional expectation of the class labels given the inputs. With the regression function not only a Bayes optimal classifier can be …
Binary ClassificationregressionSemidefinite programs simulate approximate message passing robustly
Approximate message passing (AMP) is a family of iterative algorithms that generalize matrix power iteration. AMP algorithms are known to optimally solve many average-case optimization problems. In this paper, we show th…
LoRAS: An oversampling approach for imbalanced datasets
The Synthetic Minority Oversampling TEchnique (SMOTE) is widely-used for the analysis of imbalanced datasets. It is known that SMOTE frequently over-generalizes the minority class, leading to misclassifications for the m…
General ClassificationProvable Smoothness Guarantees for Black-Box Variational Inference
Black-box variational inference tries to approximate a complex target distribution though a gradient-based optimization of the parameters of a simpler distribution. Provable convergence guarantees require structural prop…
Variational InferenceFully Distributed Resilient State Estimation based on Distributed Median Solver
In this paper, we present a scheme of fully distributed resilient state estimation for linear dynamical systems under sensor attacks. The proposed state observer consists of a network of local observers, where each of th…
State Estimation