We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Revised Loss Bounds for the Set Covering Machine and Sample-Compression Loss Bounds for Imbalanced Data.
- Authors
Hussain, Zakria; Laviolette, François; Marchand, Mario; Shawe-Taylor, John; Brubaker, Spencer Charles; Mullin, Matthew D.
- 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.
- Subjects
MACHINE learning; ALGORITHMS; DATA compression; BOOLEAN algebra; STATISTICS
- Publication
Journal of Machine Learning Research, 2007, Vol 8, Issue 11, p2533
- ISSN
1532-4435
- Publication type
Article