Login
Talks & Seminars
Title: Robust Classification for Large Datasets: A Chance-Constraint Approach
Dr. Saketha Nath, Post Doctoral Fellow, Technion Institute Israel
Date & Time: July 24, 2008 17:00
Venue: F. C. Kohli Auditorium, 01st Floor, 'B' Block, Kanwal Rekhi Building
Abstract:

In this talk, we present scalable algorithms for large binary classification tasks. As a first step, we derive a maximum-margin formulation which employs chance-constraints for clusters in the training data in order to achieve low empirical risk. Using Chebyshev inequality, the formulation is approximated as a Second Order Cone Program (SOCP) involving means and variances of the clusters. Any online clustering algorithm can be employed to efficiently estimate the moments of the clusters. Experimental results show that the proposed formulation, even when solved using generic SOCP solvers, scales better than state-of-the-art SVM solvers while achieving comparable accuracies.

The proposed classification formulation can be extended to feature spaces and the kernelized dual turns out to be a SOCP with single cone constraint. Exploiting this specialty, we derive a simple co-ordinate descent based algorithm for solving it. Results show that the proposed algorithm outperforms generic SOCP solvers in terms of solving time. Hence, scalability of the proposed formulation further increases by employing this specialized solver.

Since the true moments of clusters are unknown and are estimated using an online clustering algorithm, the proposed formulation is susceptible to moment estimation errors. Using robust optimization methodology and novel confidence sets for the moments, robust counterparts of the original formulation are derived. Interestingly, the robust counterparts also turn out to be SOCPs and hence are tractable.

Speaker Profile:
Saketha Nath is a postdoctoral fellow at the Technion institute, Israel. His main research interests are in the fields of machine learning and data mining. He has done his PhD in Computer Science at the Indian Institute of Science, Bangalore. His current research focuses on the use of advanced optimization techniques for solving problems in learning.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback