Outlier Path: A Homotopy Algorithm for Robust SVM

Abstract

In recent applications with massive but less re-liable data (e.g., labels obtained by a semi-supervised learning method or crowdsourcing), non-robustness of the support vector machine (SVM) often causes considerable performance deterioration. Although improving the robust-ness of SVM has been investigated for long time, robust SVM (RSVM) learning still poses two major challenges: obtaining a good (local) solution from a non-convex optimization prob-lem and optimally controlling the robustness-eciency trade-o. In this paper, we address these two issues simultaneously in an integrated way by introducing a novel homotopy approach to RSVM learning. Based on theoretical in-vestigation of the geometry of RSVM solutions, we show that a path of local RSVM solutions can be computed eciently when the influence of outliers is gradually suppressed as simulated annealing. We experimentally demonstrate that our algorithm tends to produce better local so-lutions than the alternative approach based on the concave-convex procedure, with the ability of stable and ecient model selection for con-trolling the influence of outliers. 1.