The one-inclusion graph algorithm is near-optimal for the prediction modelof learning

Authors
Li, Y Long, PM Srinivasan, A
Citation
Y. Li et al., The one-inclusion graph algorithm is near-optimal for the prediction modelof learning, IEEE INFO T, 47(3), 2001, pp. 1257-1261
Citations number
8
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
IEEE TRANSACTIONS ON INFORMATION THEORY
ISSN journal
00189448 → ACNP
Volume
47
Issue
3
Year of publication
2001
Pages
1257 - 1261
Database
ISI
SICI code
0018-9448(200103)47:3<1257:TOGAIN>2.0.ZU;2-V
Abstract
Haussler, Littlestone, and Warmuth described a general-purpose algorithm fo r learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1 + o( 1) of the best possible such bound for any algorithm.