Part of Advances in Neural Information Processing Systems 16 (NIPS 2003)
Tijl Bie, Nello Cristianini
The 2-class transduction problem, as formulated by Vapnik , involves ﬁnding a separating hyperplane for a labelled data set that is also maximally distant from a given set of unlabelled test points. In this form, the problem has exponential computational complexity in the size of the working set. So far it has been attacked by means of integer programming techniques  that do not scale to reasonable problem sizes, or by local search procedures . In this paper we present a relaxation of this task based on semi- deﬁnite programming (SDP), resulting in a convex optimization problem that has polynomial complexity in the size of the data set. The results are very encouraging for mid sized data sets, however the cost is still too high for large scale problems, due to the high di- mensional search space. To this end, we restrict the feasible region by introducing an approximation based on solving an eigenproblem. With this approximation, the computational cost of the algorithm is such that problems with more than 1000 points can be treated.