zbMATH — the first resource for mathematics

The combinatorial substantiation of learning algorithms. (Russian, English) Zbl 1075.93049
Zh. Vychisl. Mat. Mat. Fiz. 44, No. 11, 2099-2112 (2004); translation in Comput. Math. Math. Phys. 44, No. 11, 1997-2009 (2004).
Summary: Combinatorial cross-validation functionals that characterize the generalization performance of learning algorithms are considered. Upper bounds are derived that are tighter than those in the Vapnik-Chervonenkis statistical theory. The initial data set is not assumed to be independent, identically distributed, or even random. The effect of localization of an algorithm family is described, and the concept of a local growth function is introduced. The basic principles of statistical theory are revised by using the combinatorial approach. The basic causes of complexity bound overestimation are analyzed.

94A15 Information theory (general)
05A16 Asymptotic enumeration
60C05 Combinatorial probability
68T05 Learning and adaptive systems in artificial intelligence
Full Text: Link