TY - JOUR

T1 - On reoptimizing multi-class classifiers

AU - Bourke, Chris

AU - Deng, Kun

AU - Scott, Stephen D.

AU - Schapire, Robert E.

AU - Vinodchandran, N. V.

N1 - Funding Information:
Acknowledgements The authors thank Nicolas Lachiche for helpful correspondence. We also thank the anonymous reviewers for helpful suggestions and feedback. This work was supported in part by NSF grants CCR-0325463, CCR-0092761 and CCF-0430991.

PY - 2008/6

Y1 - 2008/6

N2 - Significant changes in the instance distribution or associated cost function of a learning problem require one to reoptimize a previously-learned classifier to work under new conditions. We study the problem of reoptimizing a multi-class classifier based on its ROC hypersurface and a matrix describing the costs of each type of prediction error. For a binary classifier, it is straightforward to find an optimal operating point based on its ROC curve and the relative cost of true positive to false positive error. However, the corresponding multi-class problem (finding an optimal operating point based on a ROC hypersurface and cost matrix) is more challenging and until now, it was unknown whether an efficient algorithm existed that found an optimal solution. We answer this question by first proving that the decision version of this problem is NP-complete. As a complementary positive result, we give an algorithm that finds an optimal solution in polynomial time if the number of classes n is a constant. We also present several heuristics for this problem, including linear, nonlinear, and quadratic programming formulations, genetic algorithms, and a customized algorithm. Empirical results suggest that under both uniform and non-uniform cost models, simple greedy methods outperform more sophisticated methods.

AB - Significant changes in the instance distribution or associated cost function of a learning problem require one to reoptimize a previously-learned classifier to work under new conditions. We study the problem of reoptimizing a multi-class classifier based on its ROC hypersurface and a matrix describing the costs of each type of prediction error. For a binary classifier, it is straightforward to find an optimal operating point based on its ROC curve and the relative cost of true positive to false positive error. However, the corresponding multi-class problem (finding an optimal operating point based on a ROC hypersurface and cost matrix) is more challenging and until now, it was unknown whether an efficient algorithm existed that found an optimal solution. We answer this question by first proving that the decision version of this problem is NP-complete. As a complementary positive result, we give an algorithm that finds an optimal solution in polynomial time if the number of classes n is a constant. We also present several heuristics for this problem, including linear, nonlinear, and quadratic programming formulations, genetic algorithms, and a customized algorithm. Empirical results suggest that under both uniform and non-uniform cost models, simple greedy methods outperform more sophisticated methods.

KW - Classifier reoptimization

KW - Multi-class classification

KW - Receiver operator characteristic (ROC)

UR - http://www.scopus.com/inward/record.url?scp=43049101059&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=43049101059&partnerID=8YFLogxK

U2 - 10.1007/s10994-008-5056-8

DO - 10.1007/s10994-008-5056-8

M3 - Article

AN - SCOPUS:43049101059

VL - 71

SP - 219

EP - 242

JO - Machine Learning

JF - Machine Learning

SN - 0885-6125

IS - 2-3

ER -