Block Stability for MAP Inference
© 2019 by the author(s). Recent work (Lang et al., 2018) has shown that some popular approximate MAP inference algorithms perform very well when the input instance is stable. The simplest stability condition assumes that the MAP solution does not change at all when some of the pairwise potentials ar...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137589 |
| _version_ | 1826201639162216448 |
|---|---|
| author | Lang, Hunter Sontag, David Vijayaraghavan, Aravindan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Lang, Hunter Sontag, David Vijayaraghavan, Aravindan |
| author_sort | Lang, Hunter |
| collection | MIT |
| description | © 2019 by the author(s). Recent work (Lang et al., 2018) has shown that some popular approximate MAP inference algorithms perform very well when the input instance is stable. The simplest stability condition assumes that the MAP solution does not change at all when some of the pairwise potentials are adversarially perturbed. Unfortunately, this strong condition does not seem to hold in practice. We introduce a significantly more relaxed condition that only requires portions of an input instance to be stable. Under this block stability condition, we prove that the pairwise LP relaxation is persistent on the stable blocks. We complement our theoretical results with an evaluation of real-world examples from computer vision, and we find that these instances have large stable regions. |
| first_indexed | 2024-09-23T11:54:48Z |
| format | Article |
| id | mit-1721.1/137589 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:54:48Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1375892023-02-06T20:35:34Z Block Stability for MAP Inference Lang, Hunter Sontag, David Vijayaraghavan, Aravindan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © 2019 by the author(s). Recent work (Lang et al., 2018) has shown that some popular approximate MAP inference algorithms perform very well when the input instance is stable. The simplest stability condition assumes that the MAP solution does not change at all when some of the pairwise potentials are adversarially perturbed. Unfortunately, this strong condition does not seem to hold in practice. We introduce a significantly more relaxed condition that only requires portions of an input instance to be stable. Under this block stability condition, we prove that the pairwise LP relaxation is persistent on the stable blocks. We complement our theoretical results with an evaluation of real-world examples from computer vision, and we find that these instances have large stable regions. 2021-11-05T19:14:28Z 2021-11-05T19:14:28Z 2019 2021-04-12T16:04:12Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137589 Lang, Hunter, Sontag, David and Vijayaraghavan, Aravindan. 2019. "Block Stability for MAP Inference." AISTATS 2019 - 22nd International Conference on Artificial Intelligence and Statistics, 89. en AISTATS 2019 - 22nd International Conference on Artificial Intelligence and Statistics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Proceedings of Machine Learning Research |
| spellingShingle | Lang, Hunter Sontag, David Vijayaraghavan, Aravindan Block Stability for MAP Inference |
| title | Block Stability for MAP Inference |
| title_full | Block Stability for MAP Inference |
| title_fullStr | Block Stability for MAP Inference |
| title_full_unstemmed | Block Stability for MAP Inference |
| title_short | Block Stability for MAP Inference |
| title_sort | block stability for map inference |
| url | https://hdl.handle.net/1721.1/137589 |
| work_keys_str_mv | AT langhunter blockstabilityformapinference AT sontagdavid blockstabilityformapinference AT vijayaraghavanaravindan blockstabilityformapinference |