Article

Unsupervised and semi-supervised multi-class support vector machines

Authors:

Dale SchuurmansAuthors Info & Claims

AAAI'05: Proceedings of the 20th national conference on Artificial intelligence - Volume 2

Pages 904 - 910

Published: 09 July 2005 Publication History

Abstract

We present new unsupervised and semi-supervised training algorithms for multi-class support vector machines based on semidefinite programming. Although support vector machines (SVMs) have been a dominant machine learning technique for the past decade, they have generally been applied to supervised learning problems. Developing unsupervised extensions to SVMs has in fact proved to be difficult. In this paper, we present a principled approach to unsupervised SVM training by formulating convex relaxations of the natural training criterion: find a labeling that would yield an optimal SVM classifier on the resulting training data. The problem is hard, but semidefinite relaxations can approximate this objective surprisingly well. While previous work has concentrated on the two-class case, we present a general, multi-class formulation that can be applied to a wider range of natural data sets. The resulting training procedures are computationally intensive, but produce high quality generalization results.

References

[1]

Altun, Y.; Tsochantaridis, I.; and Hofmann, T. 2003. Hidden Markov support vector machines. In Proceedings International Conference on Machine Learning (ICML-03).

[2]

Bansal, N.; Blum, A.; and Chawla, S. 2002. Correlation clustering. In Conference on Foundations of Computer Science (FOCS-02).

Digital Library

[3]

Bennett, K., and Demiriz, A. 1998. Semi-supervised support vector machines. In Advances in Neural Information Processing Systems 11 (NIPS-98).

Digital Library

[4]

Boyd, S., and Vandenberghe, L. 2004. Convex Optimization . Cambridge U. Press.

Digital Library

[5]

Crammer, K., and Singer, Y. 2001. On the algorithmic interpretation of multiclass kernel-based vector machines. Journal of Machine Learning Research 2.

Digital Library

[6]

De Bie, T., and Cristianini, N. 2003. Convex methods for transduction. In Advances in Neural Information Processing Systems 16 (NIPS-03).

[7]

Goemans, M., and Williamson, D. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. JACM 42:1115-1145.

Digital Library

[8]

Graepel, T., and Herbrich, R. 2003. Invariant pattern recognition by semidefinite programming machines. In Advances in Neural Information Processing Systems 16 (NIPS-03).

[9]

Helmberg, C. 2000. Semidefinite programming for combinatorial optimization. Technical Report ZIB-Report ZR-00-34, Konrad-Zuse-Zentrum Berlin.

[10]

Joachims, T. 1999. Transductive inference for text classification using support vector machines. In International Conference on Machine Learning (ICML-99).

Digital Library

[11]

Lanckriet, G.; Cristianini, N.; Bartlett, P.; Ghaoui, L.; and Jordan, M. 2004. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research 5.

Digital Library

[12]

Laurent, M., and Poljak, S. 1995. On a positive semidefinite relaxation of the cut polytope. Linear Algebra and its Applications 223/224.

[13]

Nesterov, Y., and Nimirovskii, A. 1994. Interior-Point Polynomial Algorithms in Convex Programming. SIAM.

[14]

Ng, A.; Jordan, M.; and Weiss, Y. 2001. On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems 14 (NIPS-01).

[15]

Schoelkopf, B., and Smola, A. 2002. Learning with Kernels: Support Vector Machines. Regularization. Optimization. and Beyond. MIT Press.

Digital Library

[16]

Strang, G. 1998. Introduction to Linear Algebra. Wellesley-Cambridge Press.

[17]

Taskar, B.; Guestrin, C.; and Koller, D. 2003. Max-margin Markov networks. In Advances in Neural Information Processing Systems 16 (NIPS-03).

[18]

Tsochantaridis, I.; Hofmann, T.; Joachims, T.; and Altun, Y. 2004. Support vector machine learning for interdependent and structured output spaces. In Proceedings International Conference on Machine Learning (ICML-04).

Digital Library

[19]

Vanderbei, R. 1996. Linear Programming: Foundations and Extensions. Kluwer.

[20]

Xu, L.; Neufeld, J.; Larson, B.; and Schuurmans, D. 2004. Maximum margin clustering. In Advances in Neural Information Processing Systems 17 (NIPS-04).

Cited By

Liu RZhang X(2018)Generating machine-executable plans from end-user's natural-language instructionsKnowledge-Based Systems10.1016/j.knosys.2017.10.023140:C(15-26)Online publication date: 15-Jan-2018
https://dl.acm.org/doi/10.1016/j.knosys.2017.10.023
Fang JLiu QQin Z(2018)Alternating Relaxed Twin Bounded Support Vector ClusteringWireless Personal Communications: An International Journal10.1007/s11277-017-5147-6102:2(1129-1147)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11277-017-5147-6
Saha SBanerjee BMerchant SBatra DBrown MNatarajan V(2016)Unsupervised domain adaptation without source domain training samplesProceedings of the Tenth Indian Conference on Computer Vision, Graphics and Image Processing10.1145/3009977.3010033(1-8)Online publication date: 18-Dec-2016
https://dl.acm.org/doi/10.1145/3009977.3010033
Show More Cited By

Unsupervised and semi-supervised multi-class support vector machines
1. Computing methodologies

Recommendations

Unsupervised and Semi-supervised Lagrangian Support Vector Machines
ICCS '07: Proceedings of the 7th international conference on Computational Science, Part III: ICCS 2007

Support Vector Machines have been a dominant learning technique for almost ten years, moreover they have been applied to supervised learning problems. Recently two-class unsupervised and semi-supervised classification problems based on Bounded C -...
Unsupervised and Semi-Supervised Two-class Support Vector Machines
ICDMW '06: Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops

Support VectorMachines have been a dominant learning technique for almost ten years, moreover they have been applied to supervised learning problems. Recently twoclass unsupervised and semi-supervised classification problems based on Bounded C-Support ...
Help-Training for semi-supervised support vector machines

In this paper, we propose to reinforce the Self-Training strategy in semi-supervised mode by using a generative classifier that may help to train the main discriminative classifier to label the unlabeled data. We call this semi-supervised strategy Help-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

AAAI'05: Proceedings of the 20th national conference on Artificial intelligence - Volume 2

July 2005

1035 pages

ISBN:157735236x

Editor:
Anthony Cohn
University of Leeds

Sponsors

Association for the Advancement of Artificial Intelligence

Publisher

AAAI Press

Publication History

Published: 09 July 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu RZhang X(2018)Generating machine-executable plans from end-user's natural-language instructionsKnowledge-Based Systems10.1016/j.knosys.2017.10.023140:C(15-26)Online publication date: 15-Jan-2018
https://dl.acm.org/doi/10.1016/j.knosys.2017.10.023
Fang JLiu QQin Z(2018)Alternating Relaxed Twin Bounded Support Vector ClusteringWireless Personal Communications: An International Journal10.1007/s11277-017-5147-6102:2(1129-1147)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11277-017-5147-6
Saha SBanerjee BMerchant SBatra DBrown MNatarajan V(2016)Unsupervised domain adaptation without source domain training samplesProceedings of the Tenth Indian Conference on Computer Vision, Graphics and Image Processing10.1145/3009977.3010033(1-8)Online publication date: 18-Dec-2016
https://dl.acm.org/doi/10.1145/3009977.3010033
Cong YWang SFan BYang YYu H(2016)UDSFSNeurocomputing10.1016/j.neucom.2015.10.130196:C(150-158)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1016/j.neucom.2015.10.130
Wang ZYang YChang SLi JFong SHuang T(2015)A joint optimization framework of sparse coding and discriminative clusteringProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832747.2832797(3932-3938)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832747.2832797
Gieseke F(2015)An Efficient Many-Core Implementation for Semi-Supervised Support Vector MachinesRevised Selected Papers of the First International Workshop on Machine Learning, Optimization, and Big Data - Volume 943210.1007/978-3-319-27926-8_13(145-157)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-27926-8_13
Chen TChen YGuo QZhou ZLi LXu Z(2014)Effective and efficient microprocessor design space exploration using unlabeled design configurationsACM Transactions on Intelligent Systems and Technology10.1145/2542182.25422025:1(1-18)Online publication date: 3-Jan-2014
https://dl.acm.org/doi/10.1145/2542182.2542202
Zhu XSchleif FHammer B(2014)Adaptive conformal semi-supervised vector quantization for dissimilarity dataPattern Recognition Letters10.1016/j.patrec.2014.07.00949:C(138-145)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.patrec.2014.07.009
Gieseke FAirola APahikkala TKramer O(2014)Fast and simple gradient-based optimization for semi-supervised support vector machinesNeurocomputing10.1016/j.neucom.2012.12.056123(23-32)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.neucom.2012.12.056
Shang FJiao LLiu YTong H(2013)Semi-supervised learning with nuclear norm regularizationPattern Recognition10.1016/j.patcog.2013.01.00946:8(2323-2336)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.patcog.2013.01.009
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents