Chance constrained uncertain classification via robust optimization

This paper studies the problem of constructing robust classifiers when the training is plagued with uncertainty. The problem is posed as a Chance-Constrained Program (CCP) which ensures that the uncertain data points are classified correctly with high probability. Unfortunately such a CCP turns out...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2011-03, Vol.127 (1), p.145-173
Main Authors: Ben-Tal, Aharon, Bhadra, Sahely, Bhattacharyya, Chiranjib, Saketha Nath, J.
Format: Article
Language:English
Subjects:
Algorithms
Artificial intelligence
Automation
Calculus of Variations and Optimal Control
Optimization
Chebyshev approximation
Classification
Classifiers
Combinatorics
Computer science
Data points
Full Length Paper
Industrial engineering
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical models
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Optimization
Performance evaluation
Studies
Support vector machines
Theoretical
Uncertainty
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper studies the problem of constructing robust classifiers when the training is plagued with uncertainty. The problem is posed as a Chance-Constrained Program (CCP) which ensures that the uncertain data points are classified correctly with high probability. Unfortunately such a CCP turns out to be intractable. The key novelty is in employing Bernstein bounding schemes to relax the CCP as a convex second order cone program whose solution is guaranteed to satisfy the probabilistic constraint. Prior to this work, only the Chebyshev based relaxations were exploited in learning algorithms. Bernstein bounds employ richer partial information and hence can be far less conservative than Chebyshev bounds. Due to this efficient modeling of uncertainty, the resulting classifiers achieve higher classification margins and hence better generalization. Methodologies for classifying uncertain test data points and error measures for evaluating classifiers robust to uncertain data are discussed. Experimental results on synthetic and real-world datasets show that the proposed classifiers are better equipped to handle data uncertainty and outperform state-of-the-art in many cases.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-010-0415-1