On Robustness and Regularization of Structural Support Vector Machines
Mohamad Ali Torkamani, Daniel Lowd · 2014
Previous analysis of binary support vector machines (SVMs) has demonstrated a deep connection between robustness to perturbations over uncertainty sets and regularization of the weights. In this paper, we explore the problem of learning robust models for structured prediction problems. We first formulate the problem of learning robust structural SVMs when there are per-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 to perturbations in the feature space is equivalent to ad-ditional regularization. For an ellipsoidal uncertainty set, the additional regularizer is based on the dual norm of the norm that constrains the ellipsoidal uncertainty. For a polyhedral uncertainty set, the robust optimiza-tion problem is equivalent to adding a linear regular-izer in a transformed weight space related to the lin-ear constraints of the polyhedron. We also show that these constraint sets can be combined and demonstrate a number of interesting special cases. This represents the first theoretical analysis of robust optimization of structural support vector machines. Our experimen-tal results show that our method outperforms the non-robust structural SVMs on real world data when the test data distribution has drifted from the training data distribution. 1.