Call for Papers
Maximum Margin Structured Labeling:
Optimization Algorithms, Generalization Bounds, and Consistency
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.
Toyota Technological Institute