Distribution-free performance bounds for potential function rules
Luc Devroye, Terry J. Wagner · IEEE Transactions on Information Theory · 1979
In the discrimination problem the random variable\theta, known to take values in{1, \cdots ,M}, is estimated from the random vectorX. All that is known about the joint distribution of(X, \theta)is that which can be inferred from a sample(X_{1}, \theta_{1}), \cdots ,(X_{n}, \theta_{n})of sizendrawn from that distribution. A discrimination nde is any procedure which determines a decision\hat{ \theta}for\thetafromXand(X_{1}, \theta_{1}) , \cdots , (X_{n}, \theta_{n}). For rules which are determined by potential functions it is shown that the mean-square difference between the probability of error for the nde and its deleted estimate is bounded byA/ \sqrt{n}whereAis an explicitly given constant depending only onMand the potential function. TheO(n ^{-1/2})behavior is shown to be the best possible for one of the most commonly encountered rules of this type.
Cited by 226 works. doi:10.1109/tit.1979.1056087
Authors
References
- An introduction to probability theory and its applications
- An Introduction to Probability Theory and Its Applications.
- Theoretical Foundations of the Potential Function Method in Pattern Recognition Learning
- Bibliography on estimation of misclassification
- Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties
- Sums of Independent Random Variables
- Discriminatory analysis: Nonparametric discrimination: Consistency properties
- Patterns in pattern recognition: 1968-1974
- Distribution-Free Consistency Results in Nonparametric Discrimination and Regression Function Estimation
- A distribution-free performance bound in error estimation (Corresp.)