0
$\begingroup$

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$?

Can someone please help ?

$\endgroup$
5
  • $\begingroup$ What is $X$ in this case? is it finite? infinite? if its infinite, then which set is it? $\endgroup$
    – nir shahar
    Sep 29 at 19:38
  • $\begingroup$ 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. $\endgroup$
    – baxter8
    Sep 29 at 19:52
  • $\begingroup$ Natural numbers aren't finite. They are infinite. $\endgroup$
    – nir shahar
    Sep 29 at 19:56
  • $\begingroup$ Here we take finite Natural numbers for first part $\endgroup$
    – baxter8
    Sep 29 at 19:57
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 29 at 20:00
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks! One small correction, shouldn't y_i ∈{0,1}? $\endgroup$
    – baxter8
    Oct 2 at 16:55
  • $\begingroup$ Right, thanks for the correction. $\endgroup$ Oct 3 at 8:32
  • $\begingroup$ 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]≤ϵ? $\endgroup$
    – baxter8
    Oct 3 at 22:50
  • $\begingroup$ You can’t be sure. That’s where $\delta$ comes in. $\endgroup$ Oct 4 at 4:53
  • $\begingroup$ Got it, thanks! Can you guide why it fails in set of Real numbers ? $\endgroup$
    – baxter8
    Oct 4 at 23:03
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.