Implementing a branch-and-bound algorithm for transductive support vector machines

Implementing a branch-and-bound algorithm for transductive support vector machines

0.00 Avg rating0 Votes
Article ID: iaor20106437
Volume: 16
Issue: 1
Start Page Number: 41
End Page Number: 50
Publication Date: Jan 2010
Journal: International Journal of Management Science
Authors:
Keywords: programming: branch and bound
Abstract:

Semi-supervised learning incorporates unlabeled examples, whose labels are unknown, as well as labeled examples into learning process. Although transductive support vector machine (TSVM), one of semi-supervised learning models, was proposed about a decade ago, its application to large-scaled data has still been limited due to its high computational complexity. Our previous research addressed this limitation by introducing a branch-and-bound algorithm for finding an optimal solution to TSVM. In this paper, we propose three new techniques to enhance the performance of the branch-and-bound algorithm. The first one tightens min-cut bound, one of two bounding strategies. Another technique exploits a graph-based approximation to a support vector machine problem to avoid the most time-consuming step. The last one tries to fix the labels of unlabeled examples whose labels can be obviously predicted based on labeled examples. Experimental results are presented which demonstrate that the proposed techniques can reduce drastically the number of subproblems and eventually computational time.

Reviews

Required fields are marked *. Your email address will not be published.