Abstract

Previous analysis of binary support vector machines (SVMs) has demonstrated a deep connection between robustness to perturbations over uncertainty sets a regularization of the weights. In this paper, we ex the problem of learning robust models for structure prediction problems. We first formulate the problem of learning robust structural SVMs when there are p turbations in the sample space, and show how we can construct corresponding bounds on the perturbations in the feature space. We then show that robustness perturbations in the feature space is equivalent to ditional regularization. For an ellipsoidal uncerta set, the additional regularizer is based on the dua of the norm that constrains the ellipsoidal uncerta For a polyhedral uncertainty set, the robust optimi tion problem is equivalent to adding a linear regul izer in a transformed weight space related to the l ear constraints of the polyhedron. We also show tha these constraint sets can be combined and demonstra a number of interesting special cases. This represe the first theoretical analysis of robust optimizati structural support vector machines. Our experimental results show that our method outperforms the no robust structural SVMs on real world data when the test data distribution has drifted from the trainin distribution.