UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Revised loss bounds for the set covering machine and sample-compression loss bounds for imbalanced data

Hussain, Z; Laviolette, F; Marchand, M; Shawe-Taylor, J; Brubaker, SC; Mullin, MD; (2007) Revised loss bounds for the set covering machine and sample-compression loss bounds for imbalanced data. J MACH LEARN RES , 8 2533 - 2549. Gold open access

Abstract

Marchand and Shawe-Taylor (2002) have proposed a loss bound for the set covering machine that has the property to depend on the observed fraction of positive examples and on what the classifier achieves on the positive training examples. We show that this loss bound is incorrect. We then propose a loss bound, valid for any sample-compression learning algorithm (including the set covering machine), that depends on the observed fraction of positive examples and on what the classifier achieves on them. We also compare numerically the loss bound proposed in this paper with the incorrect bound, the original SCM bound and a recently proposed loss bound of Marchand and Sokolova (2005) (which does not depend on the observed fraction of positive examples) and show that the latter loss bounds can be substantially larger than the new bound in the presence of imbalanced misclassifications.

Type:Article
Title:Revised loss bounds for the set covering machine and sample-compression loss bounds for imbalanced data
Open access status:An open access publication
Publisher version:http://www.jmlr.org/
Keywords:set covering machines, sample-compression, loss bounds
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record