Research map / Learning theory and algorithms / Combinatorial and search optimization
Exact MAP Inference by Avoiding Fractional Vertices
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use branch-and-bound to prune confounding fractional vertices | 0-1 ILP · 0-1 ILP with M confounding vertices | LP solver calls: 2M | Helped |
| Use branch-and-bound based on fractional singleton marginals | Graphical-model MAP inference · Graphical-model MAP inference | LP solver calls: 2 |S(V_C)| | Helped |
| Add cycle inequalities to remove confounding singleton marginals | Binary pairwise graphical models · Synthetic complete graphs on 12 nodes | confounding singleton marginals removed per constraint | Helped |
| Use branch-and-bound rather than cycle constraints | Binary pairwise graphical models · Synthetic complete graphs on 12 nodes | LP solver calls | Helped |
| Increase connection strength w | Random binary pairwise graphical models · Synthetic complete graphs on 12 nodes | number of confounding singleton marginals | Hurt |
| Enumerate the M-best LP vertices | LP relaxation · M-best LP problem | computational tractability: M = O(n^ε) | Hurt |
Closest papers by meaning
- Exact MAP-Inference by Confining Combinatorial Search With LP Relaxation (AAAI 2018 · similarity 0.92)
- Inference in Graphical Models via Semidefinite Programming Hierarchies (NeurIPS 2017 · similarity 0.87)
- Solving Relaxations of MAP-MRF Problems: Combinatorial In-Face Frank-Wolfe Directions (CVPR 2023 · similarity 0.87)
- Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch) (ICML 2021 · similarity 0.87)
- Continuous Relaxation of MAP Inference: A Nonconvex Perspective (CVPR 2018 · similarity 0.86)
- Maximum A Posteriori Inference in Sum-Product Networks (AAAI 2018 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.