CS Seminar - Ivor W. Tsang, Hong Kong University of Science & Technology - Department of Computer Science & Engineering

Title:  Kernel Methods Meet Minimum Enclosing Balls

Speaker: Ivor W. Tsang
  Department of Computer Science and Engineering
  Hong Kong University of Science and Technology
  Hong Kong

Date:  Monday, December 11th, 2006

Time:  2:30 pm to 4:00 pm

Room:  ASB 9705

Abstract:

Kernel methods, such as support vector machines (SVMs), have been
successfully used in various aspects of machine learning problems,
such as classification, regression, and ranking.  Many of them are
formulated as quadratic programming (QP) problems, which take O(m3)
time and O(m2) space complexities, where m is the training set
size.  It is, thus, computationally infeasible on massive data sets.

First, I show that SVM classification problems can be equivalently
formulated as minimum enclosing ball (MEB) problems in computational
geometry.  Then, by adopting an efficient approximate MEB algorithm,
I obtain provably approximately optimal solutions with the idea of
core-sets.  My proposed Core Vector Machine (CVM) algorithm can be
used with nonlinear kernels and has a time complexity that is linear
in m and a space complexity that is independent of m.  Experiments
on large toy and real-world data sets demonstrate that the CVM is
as accurate as existing SVM implementations but is much faster and
can handle much larger data sets than existing scale-up methods.

By generalizing the underlying MEB problem as the center-constrained
minimum enclosing ball (CCMEB) problem, we extend the CVM algorithm
to the regression and ranking setting.  Moreover, the condition on
the kernel function is relaxed.  Thus, the enhanced CVM algorithm
can be used with any linear/nonlinear kernels.  Besides supervised
problems, we recently integrate manifold regularization in the
semi-supervised setting with the CVM by using a sparsified manifold
regularizer and formulating as the CCMEB problem, the proposed
method also produces sparse solutions with low time and space
complexities.

Biography:

Ivor W. Tsang received his B.Eng. degree and M.Phil. degree in the
Computer Science and Engineering in 2001 and 2003, respectively, from
the Hong Kong University of Science and Technology (HKUST).  He is
currently pursuing the PhD. degree in the HKUST.  He was the Honor
Outstanding Student in 2001.  He was awarded the Microsoft Fellowship
in 2005, IEEE Transactions on Neural Networks Outstanding 2004 Paper
Award, and the Best Paper Award at the IEEE Hong Kong Chapter of
Signal Processing Postgraduate Forum in 2006.  His scientific
interests include machine learning, kernel methods, large scale
convex optimization and semi-supervised learning.