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 = {Suzumura, Shinya and Ogawa, Kohei and Sugiyama, Masashi and Takeuchi, Ichiro}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1098--1106}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, 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 = {https://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 %P 1098--1106 %U https://proceedings.mlr.press/v32/suzumura14.html %V 32 %N 2 %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 DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-suzumura14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1098 EP - 1106 L1 - http://proceedings.mlr.press/v32/suzumura14.pdf UR - https://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 Proceedings of Machine Learning Research 32(2):1098-1106 Available from https://proceedings.mlr.press/v32/suzumura14.html.

Related Material