Bauer A. Universal exact algorithm for globally augmented MAP inference in structured prediction

Technical University of Berlin, 2017. — 129 p.The main goal of the thesis is to address the computational difficulties inherent in a family of discrete optimization problems which we here refer to as augmented MAP inference. In particular, our main focus is on the exact inference, which is known to be NP-hard in general. As the main result, I define a large class of tractable problem instances within the framework of graphical models and derive an exact message passing algorithm which always finds an optimal solution in polynomial time. The latter is universal in a sense that its applicability does not explicitly depend on the graph structure of a corresponding model but rather on the intrinsic properties like treewidth and number of states of the auxiliary variables. Moreover, it leaves the global interactions between the energy of the underlying model and the sufficient statistics of the global terms largely unspecified.