Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models
Graphical models are a general-purpose tool for modeling complex distributions in a way which facilitates probabilistic reasoning, with numerous applications across machine learning and the sciences. This thesis deals with algorithmic and statistical problems of learning a high-dimensional graphical...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/139373 |
| _version_ | 1826210717674504192 |
|---|---|
| author | Koehler, Frederic |
| author2 | Mossel, Elchanan |
| author_facet | Mossel, Elchanan Koehler, Frederic |
| author_sort | Koehler, Frederic |
| collection | MIT |
| description | Graphical models are a general-purpose tool for modeling complex distributions in a way which facilitates probabilistic reasoning, with numerous applications across machine learning and the sciences. This thesis deals with algorithmic and statistical problems of learning a high-dimensional graphical model from samples, and related problems of performing inference on a known model, both areas of research which have been the subject of continued interest over the years. Our main contributions are the first computationally efficient algorithms for provably (1) learning a (possibly ill-conditioned) walk-summable Gaussian Graphical Model from samples, (2) learning a Restricted Boltzmann Machine (or other latent variable Ising model) from data, and (3) performing naive mean-field variational inference on an Ising model in the optimal density regime. These different problems illustrate a set of key principles, such as the diverse algorithmic applications of “pinning” variables in graphical models. We also show in some cases that these results are nearly optimal due to matching computational/cryptographic hardness results. |
| first_indexed | 2024-09-23T14:54:04Z |
| format | Thesis |
| id | mit-1721.1/139373 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:54:04Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1393732022-01-15T03:14:25Z Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models Koehler, Frederic Mossel, Elchanan Massachusetts Institute of Technology. Department of Mathematics Graphical models are a general-purpose tool for modeling complex distributions in a way which facilitates probabilistic reasoning, with numerous applications across machine learning and the sciences. This thesis deals with algorithmic and statistical problems of learning a high-dimensional graphical model from samples, and related problems of performing inference on a known model, both areas of research which have been the subject of continued interest over the years. Our main contributions are the first computationally efficient algorithms for provably (1) learning a (possibly ill-conditioned) walk-summable Gaussian Graphical Model from samples, (2) learning a Restricted Boltzmann Machine (or other latent variable Ising model) from data, and (3) performing naive mean-field variational inference on an Ising model in the optimal density regime. These different problems illustrate a set of key principles, such as the diverse algorithmic applications of “pinning” variables in graphical models. We also show in some cases that these results are nearly optimal due to matching computational/cryptographic hardness results. Ph.D. 2022-01-14T15:07:44Z 2022-01-14T15:07:44Z 2021-06 2021-05-25T12:47:02.199Z Thesis https://hdl.handle.net/1721.1/139373 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Koehler, Frederic Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models |
| title | Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models |
| title_full | Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models |
| title_fullStr | Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models |
| title_full_unstemmed | Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models |
| title_short | Provable Algorithms for Learning and Variational Inference in Undirected Graphical Models |
| title_sort | provable algorithms for learning and variational inference in undirected graphical models |
| url | https://hdl.handle.net/1721.1/139373 |
| work_keys_str_mv | AT koehlerfrederic provablealgorithmsforlearningandvariationalinferenceinundirectedgraphicalmodels |