How Hard is Inference for Structured Prediction
Amir Globerson, Tim Roughgarden, David A. Sontag, Cafer Yildirim · 2015
Structured prediction tasks in machine learning involve the simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decom-poses as a sum of pairwise elements, each de-pending on two specific labels. The goal of this paper is to develop a theoretical explanation of the empirical effectiveness of heuristic inference algorithms for solving such structured prediction problems. We study the minimum-achievable ex-pected Hamming error in such problems, high-lighting the case of 2D grid graphs, which are common in machine vision applications. Our main theorems provide tight upper and lower bounds on this error, as well as a polynomial-time algorithm that achieves the bound. 1.