2008 Cuts3vmaFastSemiSupervisedSvmAl

• (Zhao et al., 2008) ⇒ Bin Zhao, Fei Wang, and Changshui Zhang. (2008). “Cuts3vm: A Fast Semi-supervised Svm Algorithm.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2008). doi:10.1145/1401890.1401989

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Cuts3vm%3A+a+fast+semi-supervised+svm+algorithm%22+2008
• http://portal.acm.org/citation.cfm?doid=1401890.1401989&preflayout=flat#citedby

Quotes

Abstract

Semi-supervised support vector machine (S3VM) attempts to learn a decision boundary that traverses through low data density regions by maximizing the margin over labeled and unlabeled examples. Traditionally, S3VM is formulated as a non-convex integer programming problem and is thus difficult to solve. In this paper, we propose the cutting plane semi-supervised support vector machine (CutS3VM) algorithm, to solve the S3VM problem. Specifically, we construct a nested sequence of successively tighter relaxations of the original S3VM problem, and each optimization problem in this sequence could be efficiently solved using the constrained concave-convex procedure (CCCP). Moreover, we prove theoretically that the CutS3VM algorithm takes time O(sn) to converge with guaranteed accuracy, where n is the total number of samples in the dataset and s is the average number of non-zero features, i.e. the sparsity. Experimental evaluations on several real world datasets show that CutS3VM performs better than existing S3VM methods, both in efficiency and accuracy.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 Cuts3vmaFastSemiSupervisedSvmAl	Changshui Zhang Bin Zhao Fei Wang			Cuts3vm: A Fast Semi-supervised Svm Algorithm				10.1145/1401890.1401989