LOWER BOUNDS IN PATTERN-RECOGNITION AND LEARNING

被引：27

作者：

DEVROYE, L ^{[1
]}

LUGOSI, G ^{[1
]}

机构：

[1] TECH UNIV BUDAPEST,DEPT MATH,H-1521 BUDAPEST,HUNGARY

来源：

PATTERN RECOGNITION | 1995年 / 28卷 / 07期

关键词：

LEARNING; NONPARAMETRIC ESTIMATION; VAPNIK-CHERVONENKIS INEQUALITY; LOWER BOUNDS; PATTERN RECOGNITION;

D O I：

10.1016/0031-3203(94)00141-8

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Lower bounds are derived for the performance of any pattern recognition algorithm, which, using training data, selects a discrimination rule from a certain class of rules. The bounds involve the Vapnik-Chervonenkis dimension of the class, and L, the minimal error probability within the class. We provide lower bounds when L = 0(the usual assumption in Valiant's theory of learning) and L > 0.

引用

页码：1011 / 1018

页数：8

共 19 条

[1] PROBABILITY-INEQUALITIES FOR EMPIRICAL PROCESSES AND A LAW OF THE ITERATED LOGARITHM [J].