BriefGPT.xyz
Nov, 2020
图割总能在Potts模型中找到全局最优解(但有一个陷阱)
Graph cuts always find a global optimum (with a catch)
HTML
PDF
Hunter Lang, David Sontag, Aravindan Vijayaraghavan
TL;DR
证明 alpha-expansion 算法在 Potts 二元势场的马尔科夫随机场中总是返回全局最优赋值,但有一个要求:只对原问题实例的微小扰动中的一个赋值具有最优性。
Abstract
We prove that the
alpha-expansion algorithm
for
map inference
always returns a globally optimal assignment for
markov random fields
with <
→