Stochastic processes on graphs with cycles : geometric and variational approaches
Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/8371 |
| _version_ | 1826198334772084736 |
|---|---|
| author | Wainwright, Martin J. (Martin James), 1973- |
| author2 | Alan S. Willsky and Tommi S. Jaakkola. |
| author_facet | Alan S. Willsky and Tommi S. Jaakkola. Wainwright, Martin J. (Martin James), 1973- |
| author_sort | Wainwright, Martin J. (Martin James), 1973- |
| collection | MIT |
| description | Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002. |
| first_indexed | 2024-09-23T11:03:14Z |
| format | Thesis |
| id | mit-1721.1/8371 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:03:14Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/83712019-04-12T14:12:13Z Stochastic processes on graphs with cycles : geometric and variational approaches Wainwright, Martin J. (Martin James), 1973- Alan S. Willsky and Tommi S. Jaakkola. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002. Includes bibliographical references (leaves 259-271). Stochastic processes defined on graphs arise in a tremendous variety of fields, including statistical physics, signal processing, computer vision, artificial intelligence, and information theory. The formalism of graphical models provides a useful language with which to formulate fundamental problems common to all of these fields, including estimation, model fitting, and sampling. For graphs without cycles, known as trees, all of these problems are relatively well-understood, and can be solved efficiently with algorithms whose complexity scales in a tractable manner with problem size. In contrast, these same problems present considerable challenges in general graphs with cycles. The focus of this thesis is the development and analysis of methods, both exact and approximate, for problems on graphs with cycles. Our contributions are in developing and analyzing techniques for estimation, as well as methods for computing upper and lower bounds on quantities of interest (e.g., marginal probabilities; partition functions). In order to do so, we make use of exponential representations of distributions, as well as insight from the associated information geometry and Legendre duality. Our results demonstrate the power of exponential representations for graphical models, as well as the utility of studying collections of modified problems defined on trees embedded within the original graph with cycles. The specific contributions of this thesis include the following. We develop a method for performing exact estimation of Gaussian processes on graphs with cycles by solving a sequence of modified problems on embedded spanning trees. (cont.) We introduce the tree-based reparameterization framework for approximate estimation of discrete processes. This perspective leads to a number of theoretical results on belief propagation and related algorithms, including characterizations of their fixed points and the associated approximation error. Next we extend the notion of reparameterization to a much broader class of methods for approximate inference, including Kikuchi methods, and present results on their fixed points and accuracy. Finally, we develop and analyze a novel class of upper bounds on the log partition function based on convex combinations of distributions in the exponential domain. In the special case of combining tree-structured distributions, the associated dual function gives an interesting perspective on the Bethe free energy. by Martn J. Wainwright. Ph.D. 2005-08-23T19:35:25Z 2005-08-23T19:35:25Z 2002 2002 Thesis http://hdl.handle.net/1721.1/8371 50556375 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 271 leaves 21824527 bytes 21824286 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Wainwright, Martin J. (Martin James), 1973- Stochastic processes on graphs with cycles : geometric and variational approaches |
| title | Stochastic processes on graphs with cycles : geometric and variational approaches |
| title_full | Stochastic processes on graphs with cycles : geometric and variational approaches |
| title_fullStr | Stochastic processes on graphs with cycles : geometric and variational approaches |
| title_full_unstemmed | Stochastic processes on graphs with cycles : geometric and variational approaches |
| title_short | Stochastic processes on graphs with cycles : geometric and variational approaches |
| title_sort | stochastic processes on graphs with cycles geometric and variational approaches |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/8371 |
| work_keys_str_mv | AT wainwrightmartinjmartinjames1973 stochasticprocessesongraphswithcyclesgeometricandvariationalapproaches |