Approximating the Log-Partition Function
Graphical Models are used to represent structural information on a high-dimensional joint probability distribution. Their expressiveness offers simple reductions from a large number of NP-hard problems to inference tasks such as computing the partition function (exact inference) or approximating the...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/139223 |
| _version_ | 1811092378899972096 |
|---|---|
| author | Cosson, Romain |
| author2 | Shah, Devavrat |
| author_facet | Shah, Devavrat Cosson, Romain |
| author_sort | Cosson, Romain |
| collection | MIT |
| description | Graphical Models are used to represent structural information on a high-dimensional joint probability distribution. Their expressiveness offers simple reductions from a large number of NP-hard problems to inference tasks such as computing the partition function (exact inference) or approximating the log-partition function (approximate inference). In this master thesis, we will motivate the need for a general constant-factor approximations of the log-partition function and prove that a variant of the well studied tree-reweighted algorithm [1] achieves constant factor guarantees. We will express the corresponding approximation ratio 𝜅(𝐺) solely as a function of the graph structure 𝐺. |
| first_indexed | 2024-09-23T15:17:13Z |
| format | Thesis |
| id | mit-1721.1/139223 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:17:13Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1392232022-01-15T03:10:26Z Approximating the Log-Partition Function Cosson, Romain Shah, Devavrat Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Graphical Models are used to represent structural information on a high-dimensional joint probability distribution. Their expressiveness offers simple reductions from a large number of NP-hard problems to inference tasks such as computing the partition function (exact inference) or approximating the log-partition function (approximate inference). In this master thesis, we will motivate the need for a general constant-factor approximations of the log-partition function and prove that a variant of the well studied tree-reweighted algorithm [1] achieves constant factor guarantees. We will express the corresponding approximation ratio 𝜅(𝐺) solely as a function of the graph structure 𝐺. S.M. 2022-01-14T14:57:41Z 2022-01-14T14:57:41Z 2021-06 2021-06-24T19:21:49.447Z Thesis https://hdl.handle.net/1721.1/139223 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Cosson, Romain Approximating the Log-Partition Function |
| title | Approximating the Log-Partition Function |
| title_full | Approximating the Log-Partition Function |
| title_fullStr | Approximating the Log-Partition Function |
| title_full_unstemmed | Approximating the Log-Partition Function |
| title_short | Approximating the Log-Partition Function |
| title_sort | approximating the log partition function |
| url | https://hdl.handle.net/1721.1/139223 |
| work_keys_str_mv | AT cossonromain approximatingthelogpartitionfunction |