Timezone: »

Exact inference in structured prediction
Kevin Bello · Jean Honorio

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #221

Structured prediction can be thought of as a simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise and unary potentials. The above is naturally modeled with a graph, where edges and vertices are related to pairwise and unary potentials, respectively. We consider the generative process proposed by Globerson et al. (2015) and apply it to general connected graphs. We analyze the structural conditions of the graph that allow for the exact recovery of the labels. Our results show that exact recovery is possible and achievable in polynomial time for a large class of graphs. In particular, we show that graphs that are bad expanders can be exactly recovered by adding small edge perturbations coming from the \Erdos-\Renyi model. Finally, as a byproduct of our analysis, we provide an extension of Cheeger's inequality.

Author Information

Kevin Bello (Purdue University)
Jean Honorio (Purdue University)

More from the Same Authors