# Learnability of singleton in realizable case

I am required to show that the class of singletons $$H_{sing}$$ is learnable in the realizable case (without invoking the VC-dimension).

$$H_{sing}$$ is defined as $$H_{sing} := \{h \in \{0, 1\}^X : |\{x \in X : h(x) = 1\}| \le 1\}$$

Also I need to prove if this class also learnable if $$X = R$$?

• What is $X$ in this case? is it finite? infinite? if its infinite, then which set is it? Sep 29 at 19:38
• Initially X is finite i.e. X has domain as N(Natural numbers) so it is finite. Later or in the second part, we have X as infinite. Sep 29 at 19:52
• Natural numbers aren't finite. They are infinite. Sep 29 at 19:56
• Here we take finite Natural numbers for first part Sep 29 at 19:57
• The point of this exercise is for you to internalize the various definitions. This point would be completely lost if we solved this homework for you. I suggest starting by writing out all the relevant definitions. Sep 29 at 20:00

First, let's see what a learning algorithm looks like. It takes as input samples $$(x_1,y_1),\ldots,(x_m,y_m)$$, where $$x_i \in X$$ and $$y_i \in \{0,1\}$$, with the promise that $$y_i = h(x_i)$$ for some $$h \in H_{\mathit{sing}}$$. It should output some $$h' \in H_{\mathit{sing}}$$.

Second, let's see when a learning algorithm is successful, according to the definition of PAC learning. Here is what we need: for every $$\epsilon,\delta>0$$ we need there to be an $$m = m(\epsilon,\delta)$$ such that for every distribution $$\mathcal{D}$$ on $$X$$ and any $$h \in H_{\mathit{sing}}$$, if we feed the learning algorithm $$m$$ samples $$(x_i,h(x_i))$$, where $$x_i \sim \mathcal{D}$$, then with probability $$1-\delta$$ (over the choice of samples), the algorithm must output $$h' \in H_{\mathit{sing}}$$ such that $$\Pr_{\mathcal{D}}[h' \neq h] \leq \epsilon$$.

What can the learning algorithm do? It depends on what it sees. If $$y_i = 1$$ for some $$i \in [m]$$, then the learning algorithm can recover $$h$$. If $$y_1 = \cdots = y_m = 0$$, then the learning algorithm doesn't know anything about $$h$$, and so it might as well output $$0$$. This is the only reasonable learning algorithm. It remains to prove that for every $$\epsilon,\delta$$ you can find $$m = m(\epsilon,\delta)$$ for which the definition above is satisfied. This is your task.

• Thanks! One small correction, shouldn't y_i ∈{0,1}? Oct 2 at 16:55
• Right, thanks for the correction. Oct 3 at 8:32
• Thanks for the explanation. I am confused with one thing, if the y_1 =...= y_m = 0 then how can we be sure that PrD[h′≠h]≤ϵ? Oct 3 at 22:50
• You can’t be sure. That’s where $\delta$ comes in. Oct 4 at 4:53
• Got it, thanks! Can you guide why it fails in set of Real numbers ? Oct 4 at 23:03

The VC-dim seems to be finite for $$X = N$$ (thus is PAC-learnable). So what about for $$X = R$$? It feels like the VC-dim is still the same in that case, so can we assume it's still PAC-learnable right?