Perturbation stability for approximate MAP inference

The MAP inference problem in discrete graphical models has found widespread applications in machine learning and statistical physics over the past few decades. However, for many useful model classes, this combinatorial optimization problem is NP-hard to solve efficiently. Approximation algorithms, which typically come with theoretical worst-case guarantees on their approximation ratios, are commonplace. On real-world data, however, these algorithms far outperform their worst-case guarantees, often returning solutions that are extremely close to optimal. This thesis asks, and partially answers, the question: "What structure is present in real-world data that makes MAP inference easy?" We propose stability conditions under which we prove that popular approximation algorithms work provably well, and we evaluate these conditions on real-world instances.

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

2018

Author dc:creator

• Lang, Hunter(Hunter J.)

Advisor dc:contributor.advisor

• David A. Sontag and Aravindan Vijayaraghavan.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/121627

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/121627