Robustness Certification for Structured Prediction with General Inputs via Safe Region Modeling in the Semimetric Output Space

Many real-world machine learning problems involve structured prediction beyond categorical labels. However, most existing robustness certification works are devoted to the classification case. It remains open for robustness certification for more general outputs. In this paper, we propose a novel framework of robustness certification for structured prediction problems, where the output space is modeled as a semimetric space with a distance function that satisfies non-negativity and symmetry but not necessarily the triangle inequality. We further develop our tailored certification methods for binary, numerical, and hybrid inputs in structured prediction. Experiment results show that our method achieves tighter robustness guarantees than the SOTA structured certification baseline for numerical inputs (for which it only supports) with ℓ2 norm perturbation when outputs are measured by intersection over union (IoU) similarity, total variation distance, and perceptual distance. Moreover, we achieve good robustness certification for binary inputs with ℓ0 norm perturbation and hybrid inputs with corresponding perturbation when outputs are measured by Manhattan distance.