Cuts3vm: a fast semi-supervised svm algorithm

Wang Zhe Mark, Fei Wang, Changshui Zhang

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.
BibTeX
@inproceedings{mark2008cuts,
  author = {Wang Zhe Mark and Fei Wang and Changshui Zhang},
  title = {{Cuts3vm: a fast semi-supervised svm algorithm}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2008},
  doi = {10.1145/1401890.1401989},
}

Loading related content...

Figure