Corrigendum to “Shifting: One-inclusion mistake bounds and sample compression”. (English) Zbl 1201.68103

Summary: H. U. Simon and B. Szörényi have found an error in the proof of Theorem 52 of [B. I. P. Rubinstein, P. L. Barlett and J. H. Rubinstein, “Shifting: One-inclusion mistake bounds and sample compression”, ibid. 75, No. 1, 37–59 (2009; Zbl 1158.68452)]. In this note we provide a corrected proof of a slightly weakened version of this theorem. Our new bound on the density of one-inclusion hypergraphs is again in terms of the capacity of the multilabel concept class. H. U. Simon and B. Szörényi have recently proved an alternate result in [“One-inclusion hypergraph density revisited”, Inf. Process. Lett. 110, No. 8–9, 341–344 (2010; Zbl 1197.68063)].


68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI


[1] Ben-David, Shai; Cesa-Bianchi, Nicolò; Haussler, David; Long, Philip M., Characterizations of learnability for classes of \(\{0, \ldots, n \}\)-valued functions, J. Comput. System Sci., 50, 1, 74-86 (1995) · Zbl 0827.68095
[2] Haussler, David, Sphere packing numbers for subsets of the boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension, J. Combin. Theory Ser. A, 69, 2, 217-232 (1995) · Zbl 0818.60005
[3] Rubinstein, Benjamin I. P.; Bartlett, Peter L.; Rubinstein, J. Hyam, Shifting: One-inclusion mistake bounds and sample compression, J. Comput. System Sci., 75, 1, 37-59 (2009) · Zbl 1158.68452
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.