Weird Function Learned by A Simple Rule

(Proof of Problem 6.3 of (Devroye, Györfi, & Lugosi, 1997)

On Page 92 of (Devroye, Györfi, & Lugosi, 1997), the authors give an example of hard to learn function as follows.

On the interval $[0,1]$, let the distribution spit out rational numbers and irrational numbers with equal probability. List all the rational numbers as a sequence $\{r_n\}$. The probability over irrational numbers is uniform, and the probability over rational numbers is given by the sequence $\{1/2^{n+1}\}$. And the labels of rational numbers are 1, and irrational numbers -1.

Since the labels are deterministic, the Bayes classifier can achieve 0 risk. In practice, we can never justify the rationality of a number. Nonetheless, we assume that we can get arbitrarily accurate digits of the number. It is surprising that we can find a consistent rule to learn this function. And the rule is very simple, it just assigns the same label of the closest sample to the test point!

To show the consistency of the closest neighbor rule, we only need to show that for sufficiently many samples, the probability of making mistakes can be arbitrarily small. The key of the proof is to note that under the setup given above, the rational numbers are very likely to repeat in the sample set. So when the test point is a rational number, it repeats some sample point with high probability; when it is an irrational number, it is more likely between two irrational sample points.

Assume we have $m$ samples $\{(X_i,Y_i)\}$ and a test point $X$ with corresponding label $Y$. In the first part, we assume $X$ is a rational number. Then

$$\begin{equation} \mathbb{P}\left(\forall i\,,X\ne X_i\mid Y=1\right)=\sum_{n=1}^\infty\mathbb{P}\left(\forall i\,,X_i\ne r_n\wedge X=r_n\mid Y=1\right)=\sum_{n=1}^\infty\left(1-\frac{1}{2^n}\right)^m\frac{1}{2^n}\,. \end{equation}$$

It is not hard to see that this probability can be arbitrarily small when $m$ is sufficiently large. It means that when $X$ is rational, its closest neighbor will be itself in the sample set with high probability.

For the second part, we assume that $X$ is irrational. Denote the number of distinct rationals in the sample set by $K$. We want to show that with a high probability, $K$ in the sample set will be less than $2\log_2 m$.

$$\begin{equation} \mathbb{P}\left(K\ge2\log_2 m\right)\le\mathbb{P}\left(\exists i\,s.t.\,X_i=r_n\wedge n\ge2\log_2 m\right)=1-\left(1-\frac{1}{2^{2\log_2 m}}\right)^m\,. \end{equation}$$

On the other hand, denote the number of irrationals in the sample set by $L$. Then

$$\begin{equation} \mathbb{P}\left(L<\frac{m}{4}\right)\le\exp\left(-\frac{m}{8}\right)\,, \end{equation}$$

by Hoeffding’s inequality.

Therefore, by union bound we have

$$\begin{equation} \mathbb{P}\left(K<2\log_2m\wedge L\ge\frac{m}{4}\right)\ge1-\mathbb{P}(K\ge2\log_2m)-\mathbb{P}(L<\frac{m}{4})\,, \end{equation}$$

which is further greater than

$$\begin{equation} \left(1-\frac{1}{2^{2\log_2 m}}\right)^m-\exp\left(-\frac{m}{8}\right)\to 1\quad\text{as m}\to\infty\,. \end{equation}$$

So, when $m$ is sufficiently large, with high probability, $L\gg K$. Now among $L+1$ irrationals, the position of $X$ is uniform, then the chance that $X$ is next to a rational sample is less than $\frac{2K}{L+1}$, which can be arbitrarily small as $m$ is large. If its left and right neighbors are both irrational samples, it will be labeled correctly.

Combining the results of both parts, we get the conclusion that, as $m\to\infty$, the probability of labeling the test point correctly approaches to 1. Clearly, this is only a consistency result instead of a learning rate. In general, there exists learning method that is consistent for any problem, but there does not exist learning method with the universal learning rate.

Reference

1. Devroye, L., Györfi, L., & Lugosi, G. (1997). A Probabilistic Theory of Pattern Recognition. Springer New York.