Part of Advances in Neural Information Processing Systems 17 (NIPS 2004)
Peter Bartlett, Michael Collins, Ben Taskar, David McAllester
We consider the problem of structured classiﬁcation, where the task is to predict a label y from an input x, and y has meaningful internal struc- ture. Our framework includes supervised training of Markov random ﬁelds and weighted context-free grammars as special cases. We describe an algorithm that solves the large-margin optimization problem deﬁned in , using an exponential-family (Gibbs distribution) representation of structured objects. The algorithm is efﬁcient—even in cases where the number of labels y is exponential in size—provided that certain expecta- tions under Gibbs distributions can be calculated efﬁciently. The method for structured labels relies on a more general result, speciﬁcally the ap- plication of exponentiated gradient updates [7, 8] to quadratic programs.