Semi-Supervised Learning with Max-Margin Graph Cuts

Branislav Kveton, Michal Valko, Ali Rahimi, Ling Huang
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:421-428, 2010.

Abstract

This paper proposes a novel algorithm for semi-supervised learning. This algorithm learns graph cuts that maximize the margin with respect to the labels induced by the harmonic function solution. We motivate the approach, compare it to existing work, and prove a bound on its generalization error. The quality of our solutions is evaluated on a synthetic problem and three UCI ML repository datasets. In most cases, we outperform manifold regularization of support vector machines, which is a state-of-the-art approach to semi-supervised max-margin learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v9-kveton10a, title = {Semi-Supervised Learning with Max-Margin Graph Cuts}, author = {Kveton, Branislav and Valko, Michal and Rahimi, Ali and Huang, Ling}, booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics}, pages = {421--428}, year = {2010}, editor = {Teh, Yee Whye and Titterington, Mike}, volume = {9}, series = {Proceedings of Machine Learning Research}, address = {Chia Laguna Resort, Sardinia, Italy}, month = {13--15 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v9/kveton10a/kveton10a.pdf}, url = {https://proceedings.mlr.press/v9/kveton10a.html}, abstract = {This paper proposes a novel algorithm for semi-supervised learning. This algorithm learns graph cuts that maximize the margin with respect to the labels induced by the harmonic function solution. We motivate the approach, compare it to existing work, and prove a bound on its generalization error. The quality of our solutions is evaluated on a synthetic problem and three UCI ML repository datasets. In most cases, we outperform manifold regularization of support vector machines, which is a state-of-the-art approach to semi-supervised max-margin learning.} }
Endnote
%0 Conference Paper %T Semi-Supervised Learning with Max-Margin Graph Cuts %A Branislav Kveton %A Michal Valko %A Ali Rahimi %A Ling Huang %B Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2010 %E Yee Whye Teh %E Mike Titterington %F pmlr-v9-kveton10a %I PMLR %P 421--428 %U https://proceedings.mlr.press/v9/kveton10a.html %V 9 %X This paper proposes a novel algorithm for semi-supervised learning. This algorithm learns graph cuts that maximize the margin with respect to the labels induced by the harmonic function solution. We motivate the approach, compare it to existing work, and prove a bound on its generalization error. The quality of our solutions is evaluated on a synthetic problem and three UCI ML repository datasets. In most cases, we outperform manifold regularization of support vector machines, which is a state-of-the-art approach to semi-supervised max-margin learning.
RIS
TY - CPAPER TI - Semi-Supervised Learning with Max-Margin Graph Cuts AU - Branislav Kveton AU - Michal Valko AU - Ali Rahimi AU - Ling Huang BT - Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics DA - 2010/03/31 ED - Yee Whye Teh ED - Mike Titterington ID - pmlr-v9-kveton10a PB - PMLR DP - Proceedings of Machine Learning Research VL - 9 SP - 421 EP - 428 L1 - http://proceedings.mlr.press/v9/kveton10a/kveton10a.pdf UR - https://proceedings.mlr.press/v9/kveton10a.html AB - This paper proposes a novel algorithm for semi-supervised learning. This algorithm learns graph cuts that maximize the margin with respect to the labels induced by the harmonic function solution. We motivate the approach, compare it to existing work, and prove a bound on its generalization error. The quality of our solutions is evaluated on a synthetic problem and three UCI ML repository datasets. In most cases, we outperform manifold regularization of support vector machines, which is a state-of-the-art approach to semi-supervised max-margin learning. ER -
APA
Kveton, B., Valko, M., Rahimi, A. & Huang, L.. (2010). Semi-Supervised Learning with Max-Margin Graph Cuts. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 9:421-428 Available from https://proceedings.mlr.press/v9/kveton10a.html.

Related Material