Timezone: »

Exact Inference in High-order Structured Prediction
Chuyang Ke · Jean Honorio

Thu Jul 27 01:30 PM -- 03:00 PM (PDT) @ Exhibit Hall 1 #644

In this paper, we study the problem of inference in high-order structured prediction tasks. In the context of Markov random fields, the goal of a high-order inference task is to maximize a score function on the space of labels, and the score function can be decomposed into sum of unary and high-order potentials. We apply a generative model approach to study the problem of high-order inference, and provide a two-stage convex optimization algorithm for exact label recovery. We also provide a new class of hypergraph structural properties related to hyperedge expansion that drives the success in general high-order inference problems. Finally, we connect the performance of our algorithm and the hyperedge expansion property using a novel hypergraph Cheeger-type inequality.

Author Information

Chuyang Ke (Purdue University)
Jean Honorio (Purdue University)

More from the Same Authors