%0 Journal Article %J IEEE Transactions on Information Theory %D 2001 %T The one-inclusion graph algorithm is near-optimal for the prediction model of learning %A Li,Yi %A Long,P. M %A Srinivasan, Aravind %K Computer science %K concept class %K general-purpose algorithm %K graph theory %K learning prediction model %K learning systems %K near-optimal algorithm %K Neural networks %K one-inclusion graph algorithm %K optimisation %K Prediction algorithms %K prediction theory %K Predictive models %K probability %K Probability distribution %K Upper bound %K Vapnik-Chervonenkis dimension %K Virtual colonoscopy %X Haussler, Littlestone and Warmuth (1994) described a general-purpose algorithm for 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 %B IEEE Transactions on Information Theory %V 47 %P 1257 - 1261 %8 2001/03// %@ 0018-9448 %G eng %N 3 %R 10.1109/18.915700