Robust formulations for clusteringbased largesca

Authors: Saketha Nath Jagarlapudi Aharon BenTal Chiranjib Bhattacharyya

Publish Date: 2011/09/24

Volume: 14, Issue: 2, Pages: 225-250

PDF Link

Abstract

Chebyshevinequalitybased convex relaxations of ChanceConstrained Programs CCPs are shown to be useful for learning classifiers on massive datasets In particular an algorithm that integrates efficient clustering procedures and CCP approaches for computing classifiers on large datasets is proposed The key idea is to identify high density regions or clusters from individual class conditional densities and then use a CCP formulation to learn a classifier on the clusters The CCP formulation ensures that most of the data points in a cluster are correctly classified by employing a Chebyshevinequalitybased convex relaxation This relaxation is heavily dependent on the secondorder statistics However this formulation and in general such relaxations that depend on the secondorder moments are susceptible to moment estimation errors One of the contributions of the paper is to propose several formulations that are robust to such errors In particular a generic way of making such formulations robust to moment estimation errors is illustrated using two novel confidence sets An important contribution is to show that when either of the confidence sets is employed for the special case of a spherical normal distribution of clusters the robust variant of the formulation can be posed as a secondorder cone program Empirical results show that the robust formulations achieve accuracies comparable to that with true moments even when moment estimates are erroneous Results also illustrate the benefits of employing the proposed methodology for robust classification of largescale datasets

Keywords: