Cover–Hart bound
Topic of Nearest neighbours, part of Statistical learning
Cover–Hart bound
| Type | Topic |
| Taught in | Nearest neighbours |
| Part | Statistical learning |
| Questions using it | 1 |
As the training sample grows, the error rate R of the one-nearest-neighbour rule satisfies R^*\le R\le2R^*(1-R^*) for two classes, where R^* is the Bayes error: at most twice the best achievable.
In Nearest neighbours
From Nearest neighbours
where R^*=\mathbb{E}[r(X)] is the Bayes risk, because 1-r\le 1. Jensen’s inequality, using the concavity of u\mapsto u(1-u) on [0,1] together with \mathbb{E}[r(X)]=R^*, gives the sharper Cover–Hart bound
\mathbb{E}\bigl[2r(1-r)\bigr]\le 2R^*(1-R^*).
Used in
- Taught in Nearest neighbours
- Questions that use it (1) — The factor of two (answer)
- All 8 questions on Nearest neighbours
See also
Training set · Bayes classifier · Rank distance · -nearest neighbours · Bayes consistency of -nearest neighbours · Distance and scale in nearest neighbours · Ties and the choice of k · Consistency and the factor of two