Outlier Path: A Homotopy Algorithm for Robust SVM

Shinya Suzumura, Kohei Ogawa, Masashi Sugiyama, Ichiro Takeuchi
; Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1098-1106, 2014.

Abstract

In recent applications with massive but less reliable 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 robustness 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 problem and optimally controlling the robustness-efficiency trade-off. 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 investigation of the geometry of RSVM solutions, we show that a path of local RSVM solutions can be computed efficiently when the influence of outliers is gradually suppressed as simulated annealing. We experimentally demonstrate that our algorithm tends to produce better local solutions than the alternative approach based on the concave-convex procedure, with the ability of stable and efficient model selection for controlling the influence of outliers.

Cite this Paper


BibTeX
@InProceedings{pmlr-v32-suzumura14, title = {Outlier Path: A Homotopy Algorithm for Robust SVM}, author = {Shinya Suzumura and Kohei Ogawa and Masashi Sugiyama and Ichiro Takeuchi}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1098--1106}, year = {2014}, editor = {Eric P. Xing and Tony Jebara}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/suzumura14.pdf}, url = {http://proceedings.mlr.press/v32/suzumura14.html}, abstract = {In recent applications with massive but less reliable 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 robustness 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 problem and optimally controlling the robustness-efficiency trade-off. 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 investigation of the geometry of RSVM solutions, we show that a path of local RSVM solutions can be computed efficiently when the influence of outliers is gradually suppressed as simulated annealing. We experimentally demonstrate that our algorithm tends to produce better local solutions than the alternative approach based on the concave-convex procedure, with the ability of stable and efficient model selection for controlling the influence of outliers.} }
Endnote
%0 Conference Paper %T Outlier Path: A Homotopy Algorithm for Robust SVM %A Shinya Suzumura %A Kohei Ogawa %A Masashi Sugiyama %A Ichiro Takeuchi %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-suzumura14 %I PMLR %J Proceedings of Machine Learning Research %P 1098--1106 %U http://proceedings.mlr.press %V 32 %N 2 %W PMLR %X In recent applications with massive but less reliable 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 robustness 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 problem and optimally controlling the robustness-efficiency trade-off. 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 investigation of the geometry of RSVM solutions, we show that a path of local RSVM solutions can be computed efficiently when the influence of outliers is gradually suppressed as simulated annealing. We experimentally demonstrate that our algorithm tends to produce better local solutions than the alternative approach based on the concave-convex procedure, with the ability of stable and efficient model selection for controlling the influence of outliers.
RIS
TY - CPAPER TI - Outlier Path: A Homotopy Algorithm for Robust SVM AU - Shinya Suzumura AU - Kohei Ogawa AU - Masashi Sugiyama AU - Ichiro Takeuchi BT - Proceedings of the 31st International Conference on Machine Learning PY - 2014/01/27 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-suzumura14 PB - PMLR SP - 1098 DP - PMLR EP - 1106 L1 - http://proceedings.mlr.press/v32/suzumura14.pdf UR - http://proceedings.mlr.press/v32/suzumura14.html AB - In recent applications with massive but less reliable 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 robustness 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 problem and optimally controlling the robustness-efficiency trade-off. 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 investigation of the geometry of RSVM solutions, we show that a path of local RSVM solutions can be computed efficiently when the influence of outliers is gradually suppressed as simulated annealing. We experimentally demonstrate that our algorithm tends to produce better local solutions than the alternative approach based on the concave-convex procedure, with the ability of stable and efficient model selection for controlling the influence of outliers. ER -
APA
Suzumura, S., Ogawa, K., Sugiyama, M. & Takeuchi, I.. (2014). Outlier Path: A Homotopy Algorithm for Robust SVM. Proceedings of the 31st International Conference on Machine Learning, in PMLR 32(2):1098-1106

Related Material