Infinitesimal Annealing for Training Semi-Supervised Support Vector Machines

Kohei Ogawa, Motoki Imamura, Ichiro Takeuchi, Masashi Sugiyama
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):897-905, 2013.

Abstract

The semi-supervised support vector machine (S3VM) is a maximum-margin classification algorithm based on both labeled and unlabeled data. Training S3VM involves either a combinatorial or non-convex optimization problem and thus finding the global optimal solution is intractable in practice. It has been demonstrated that a key to successfully find a good (local) solution of S3VM is to gradually increase the effect of unlabeled data, a la annealing. However, existing algorithms suffer from the trade-off between the resolution of annealing steps and the computation cost. In this paper, we go beyond this trade-off by proposing a novel training algorithm that efficiently performs annealing with an infinitesimal resolution. Through experiments, we demonstrate that the proposed infinitesimal annealing algorithm tends to produce better solutions with less computation time than existing approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-ogawa13a, title = {Infinitesimal Annealing for Training Semi-Supervised Support Vector Machines}, author = {Ogawa, Kohei and Imamura, Motoki and Takeuchi, Ichiro and Sugiyama, Masashi}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {897--905}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/ogawa13a.pdf}, url = {https://proceedings.mlr.press/v28/ogawa13a.html}, abstract = {The semi-supervised support vector machine (S3VM) is a maximum-margin classification algorithm based on both labeled and unlabeled data. Training S3VM involves either a combinatorial or non-convex optimization problem and thus finding the global optimal solution is intractable in practice. It has been demonstrated that a key to successfully find a good (local) solution of S3VM is to gradually increase the effect of unlabeled data, a la annealing. However, existing algorithms suffer from the trade-off between the resolution of annealing steps and the computation cost. In this paper, we go beyond this trade-off by proposing a novel training algorithm that efficiently performs annealing with an infinitesimal resolution. Through experiments, we demonstrate that the proposed infinitesimal annealing algorithm tends to produce better solutions with less computation time than existing approaches. } }
Endnote
%0 Conference Paper %T Infinitesimal Annealing for Training Semi-Supervised Support Vector Machines %A Kohei Ogawa %A Motoki Imamura %A Ichiro Takeuchi %A Masashi Sugiyama %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-ogawa13a %I PMLR %P 897--905 %U https://proceedings.mlr.press/v28/ogawa13a.html %V 28 %N 3 %X The semi-supervised support vector machine (S3VM) is a maximum-margin classification algorithm based on both labeled and unlabeled data. Training S3VM involves either a combinatorial or non-convex optimization problem and thus finding the global optimal solution is intractable in practice. It has been demonstrated that a key to successfully find a good (local) solution of S3VM is to gradually increase the effect of unlabeled data, a la annealing. However, existing algorithms suffer from the trade-off between the resolution of annealing steps and the computation cost. In this paper, we go beyond this trade-off by proposing a novel training algorithm that efficiently performs annealing with an infinitesimal resolution. Through experiments, we demonstrate that the proposed infinitesimal annealing algorithm tends to produce better solutions with less computation time than existing approaches.
RIS
TY - CPAPER TI - Infinitesimal Annealing for Training Semi-Supervised Support Vector Machines AU - Kohei Ogawa AU - Motoki Imamura AU - Ichiro Takeuchi AU - Masashi Sugiyama BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-ogawa13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 897 EP - 905 L1 - http://proceedings.mlr.press/v28/ogawa13a.pdf UR - https://proceedings.mlr.press/v28/ogawa13a.html AB - The semi-supervised support vector machine (S3VM) is a maximum-margin classification algorithm based on both labeled and unlabeled data. Training S3VM involves either a combinatorial or non-convex optimization problem and thus finding the global optimal solution is intractable in practice. It has been demonstrated that a key to successfully find a good (local) solution of S3VM is to gradually increase the effect of unlabeled data, a la annealing. However, existing algorithms suffer from the trade-off between the resolution of annealing steps and the computation cost. In this paper, we go beyond this trade-off by proposing a novel training algorithm that efficiently performs annealing with an infinitesimal resolution. Through experiments, we demonstrate that the proposed infinitesimal annealing algorithm tends to produce better solutions with less computation time than existing approaches. ER -
APA
Ogawa, K., Imamura, M., Takeuchi, I. & Sugiyama, M.. (2013). Infinitesimal Annealing for Training Semi-Supervised Support Vector Machines. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):897-905 Available from https://proceedings.mlr.press/v28/ogawa13a.html.

Related Material