Header logo is

Deterministic annealing for semi-supervised kernel machines


Conference Paper


An intuitive approach to utilizing unlabeled data in kernel-based classification algorithms is to simply treat the unknown labels as additional optimization variables. For margin-based loss functions, one can view this approach as attempting to learn low-density separators. However, this is a hard optimization problem to solve in typical semi-supervised settings where unlabeled data is abundant. The popular Transductive SVM algorithm is a label-switching-retraining procedure that is known to be susceptible to local minima. In this paper, we present a global optimization framework for semi-supervised Kernel machines where an easier problem is parametrically deformed to the original hard problem and minimizers are smoothly tracked. Our approach is motivated from deterministic annealing techniques and involves a sequence of convex optimization problems that are exactly and efficiently solved. We present empirical results on several synthetic and real world datasets that demonstrate the effectiveness of our approach.

Author(s): Sindhwani, V. and Keerthi, SS. and Chapelle, O.
Book Title: ICML 2006
Journal: Proceedings of the 23rd International Conference on Machine Learning (ICML 2006)
Pages: 841-848
Year: 2006
Month: June
Day: 0
Editors: Cohen, W. W., A. Moore
Publisher: ACM Press

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

DOI: 10.1145/1143844.1143950
Event Name: 23rd International Conference on Machine Learning
Event Place: Pittsburgh, PA, USA

Address: New York, NY, USA
Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Deterministic annealing for semi-supervised kernel machines},
  author = {Sindhwani, V. and Keerthi, SS. and Chapelle, O.},
  journal = {Proceedings of the 23rd International Conference on Machine Learning (ICML 2006)},
  booktitle = {ICML 2006},
  pages = {841-848},
  editors = {Cohen, W. W., A. Moore},
  publisher = {ACM Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {New York, NY, USA},
  month = jun,
  year = {2006},
  month_numeric = {6}