Record Details

Robust formulations for clustering-based large-scale classification

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Robust formulations for clustering-based large-scale classification
 
Creator JAGARLAPUDI, SN
BEN-TAL, A
BHATTACHARYYA, C
 
Subject Confidence sets
Robustness
Large dataset classification
SOCP
Chebyshev inequality
OPTIMIZATION
 
Description Chebyshev-inequality-based convex relaxations of Chance-Constrained 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 Chebyshev-inequality-based convex relaxation. This relaxation is heavily dependent on the second-order statistics. However, this formulation and in general such relaxations that depend on the second-order 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 second-order 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 large-scale datasets.
 
Publisher SPRINGER
 
Date 2014-10-16T12:46:38Z
2014-10-16T12:46:38Z
2013
 
Type Article
 
Identifier OPTIMIZATION AND ENGINEERING, 14(2)225-250
http://dx.doi.org/10.1007/s11081-011-9166-y
http://dspace.library.iitb.ac.in/jspui/handle/100/15583
 
Language en