SRL logo

SRL2006: Open Problems in Statistical Relational Learning

Invited Talk

Home

Call for Papers

Schedule

Proceedings

Pointers
Papers
Software
Data

Contact Information
Information
Mailing List

Maximum Margin Structured Labeling:
Optimization Algorithms, Generalization Bounds, and Consistency

David McAllester
Toyota Technological Institute

This talk will review some recent results on max-margin structured classification with an emphasis on both theoretical and empirical open problems. We will start by reviewing the basic polynomial time training and classification algorithms for low tree width problems. We will then discuss various alternative notions of structured hinge loss all of which reduce to classical hinge loss for binary classification. Generalization bounds will be presented which seem to provide some insight into the choice of an appropriate structured hinge loss. It will be shown that Hamming distance plays an important role in generalization bounds independent of the choice of loss function, e.g., even when bounding 0-1 loss. It will be shown that the generalization bounds are consistent but non-convex while all proposed structured forms of hinge loss are convex but inconsistent. Finally, we consider the case of semi-supervised max-margin structured learning.