Distribution-free inequalities for the deleted and holdout error estimates
- 1 March 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 25 (2) , 202-207
- https://doi.org/10.1109/tit.1979.1056032
Abstract
In the discrimination problem the random variable\theta, known to take values in{1 ,\ldots ,M}, is estimated from the random vectorXtaking values in{\bfR}^{d}. Ali that is known about the joint distribution of(X,O)is that which can be inferred from a sample(X_{1} , \theta_{1}, \ldots , (X_{n}, \theta_{n})of sizendrawn from that distribution. A discrimination rule is any procedure which determines a decision\hat{\theta}for\thetafromXand(X_{1},\theta_{1}) , \ldots , (X_{n}, \theta_{n}). The rule is calledk-local if the decision\hat{\theta}depends only onXand the pairs(X_{i}, \theta_{i}),for whichX_{i}is one of thekclosest toXfromX_{1} , \ldots ,X_{n}. IfL_{n}denotes the probability of error for ak-local rule given the sample, then estimates\hat{L}_{n}ofL_{n}, are determined for whichP {| \hat{L}_{n} - L_{n} \geq \epsilon} \exp (- Bn), whereAandBare positive constants depending only ond,M, and\epsilon.Keywords
This publication has 6 references indexed in Scilit:
- Distribution-free performance bounds with the resubstitution error estimate (Corresp.)IEEE Transactions on Information Theory, 1979
- A Finite Sample Distribution-Free Performance Bound for Local Discrimination RulesThe Annals of Statistics, 1978
- A distribution-free performance bound in error estimation (Corresp.)IEEE Transactions on Information Theory, 1976
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967
- Covering a sphere with spheresMathematika, 1963
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963