Abstract
dc:description.abstractGraphical 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 𝐺.
Degree
thesis:*- Name thesis:degree_name
- Master
- Department dc:contributor.department
- Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
- Grantor dc:publisher
- Massachusetts Institute of Technology
- Year dc:date.issued
- 2021
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Cosson, Romain
- Advisor dc:contributor.advisor
-
- Shah, Devavrat
Rights
dc:rights- Statement dc:rights
-
- In Copyright - Educational Use Permitted
- Copyright MIT
- Licence dc:rights.uri
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1721.1/139223
- OAI identifier oai:identifier
- oai:dspace.mit.edu:1721.1/139223