Name
Abstract | ||
|---|---|---|
We consider the estimation problem in Gaussian graphical models with arbitrary structure. We analyze the Embedded Trees algorithm, which solves a sequence of problems on tractable subgraphs thereby leading to the solution of the estimation problem on an intractable graph. Our analysis is based on the recently developed walk-sum interpretation of Gaussian estimation. We show that non-stationary it- erations of the Embedded Trees algorithm using any sequence of subgraphs con- verge in walk-summable models. Based on walk-sum calculations, we develop adaptive methods that optimize the choice of subgraphs used at each iteration with a view to achieving maximum reduction in error. These adaptive procedures pro- vide a significant speedup in convergence over stationary iterative methods, and also appear to converge in a larger class of models. We describe a rich class of iterative algorithms for estimation in Gaussian graphical models with arbitrary structure. Specifically, we discuss the Embedded Trees (ET) iteration (4) that solves a sequence of estimation problems on trees, or more generally tractable subgraphs, leading to the so- lution of the original problem on the intractable graph. We analyze non-stationary iterations of the ET algorithm that perform inference calculations on an arbitrary sequence of subgraphs. Our anal- ysis is based on the recently developed walk-sum interpretation of inference in Gaussian graphical models (5). We show that in the broad class of so-called walk-summable models, the ET algorithm converges for any arbitrary sequence of subgraphs used. The walk-summability of a model is easily tested (5, 6), thus providing a simple sufficient condition for the convergence of such non-stationary algorithms. Previous convergence results (6, 7) analyzed stationary or "cyclo-stationary" iterations that use the same subgraph at each iteration or cycle through a fixed sequence of subgraphs. The focus of this paper is on analyzing, and developing algorithms based on, arbitrary non-stationary iterations that use any (non-cyclic) sequence of subgraphs, and the recently developed concept of walk-sums appears to be critical to this analysis. |
Year | Venue | Keywords |
|---|---|---|
2007 | NIPS | iteration method,iterative algorithm |
Field | DocType | Citations |
Convergence (routing),Graph,Mathematical optimization,Iterative method,Computer science,Algorithm,Theoretical computer science,Gaussian,Artificial intelligence,Graphical model,Machine learning,Speedup | Conference | 2 |
PageRank | References | Authors |
0.38 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Venkat Chandrasekaran | 1 | 716 | 37.92 |
| Jason K. Johnson | 2 | 201 | 14.07 |
| Alan S. Willsky | 3 | 7466 | 847.01 |