1
$\begingroup$

Is it true that for a finite or a countably infinite hypothesis class $\mathcal{H}$, then it is going to be PAC-learnable (and vice-versa)? And what about if we change the cardinality of the hypothesis space to be an uncountably infinite? Does that mean it will not be PAC learnable?

Please correct me if I'm wrong, thank you so much.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ A hypothesis class is PAC-learnable iff it has finite VC dimension. That's all you need to know. $\endgroup$
    – Yuval Filmus
    Oct 6, 2021 at 6:58
  • $\begingroup$ For a singleton class $\mathcal{H}$ with VC-dim = 0 and $\mathcal{X}=\mathbb{N}$, it implies that $\mathcal{H}$ is PAC-learnable. So what happens when $\mathcal{X} = \mathbb{R}$? It feels like the VC-dimension is still 0, correct (since it can't shatter a single point in the $\mathbb{N}$, pretty sure it can't shatter a single point either in $\mathbb{R}$)? Yet, I read from somewhere that $\mathcal{H}$ is not PAC-learnable anymore because of some contradiction in the proof for PAC-learnability. So what happened? I always thought that PAC-learnability $\Longleftrightarrow$ finite VC-dim? $\endgroup$
    – M. Fire
    Oct 6, 2021 at 14:34
  • $\begingroup$ Every singleton class is learnable, by a learner which just outputs the singleton. $\endgroup$
    – Yuval Filmus
    Oct 6, 2021 at 15:02
  • $\begingroup$ Ah I see. Are there any hypothesis classes that exist where the status of its PAC-learnability changes when the domain space changes (for example, if $\mathcal{X}$ changes from natural to real numbers, then $\mathcal{H}$ no longer becomes PAC-learnable)? $\endgroup$
    – M. Fire
    Oct 6, 2021 at 15:13
  • $\begingroup$ If the domain changes then the hypothesis class changes, so I don't really understand the question. One way to understand it is: consider a class of functions over a domain $X$, and its restriction to a class of function to some subdomain $Y \subset X$. Can the restriction have smaller VC dimension? Yes. You can easily construct such examples. $\endgroup$
    – Yuval Filmus
    Oct 6, 2021 at 15:14

1 Answer 1

Reset to default
1
$\begingroup$

Every finite hypothesis class $\mathcal{H}$ is PAC-learnable. Indeed, $VCdim(\mathcal{H})\le |\mathcal{H}|<\infty$ (one can even create a more strict bound, but this is irrelevant for now). Hence, $\mathcal{H}$ is PAC-learnable.

Infinite classes however, can either be PAC-learnable or not. Being a countable, or an uncountable class does not matter here. For example, the class of all rectangles centered at the origin of $\mathbb{R}^2$ is PAC-learnable (has VCdim $2$ if I remember correctly), while it is an uncountable class.

Another example, of a countable class being not PAC-learnable, is the following:

$$\mathcal{H}:=\{f:\mathbb{N}\rightarrow \{0,1\}\mid \text{the number of $1$'s in $f$ is finite}\}$$

Which I will leave for you to verify that it is countably infinite, still has an infinite VCdim: Any finite $C\subset \mathbb{N}$ can be shattered, since we can "extend" every $f\in C\rightarrow \{0,1\}$ into a function $f_{\mathbb{N}}:\mathbb{N}\rightarrow \{0,1\}$ in the following way:

$$f_\mathbb{N}(n)=\begin{cases}f(n)&n\in C\\0&n\notin C\end{cases}$$

And indeed when we restrict $f_{\mathbb{N}}$ into $C$, we get $f$. But $f_{\mathbb{N}}\in \mathcal{H}$, and thus we showed that every finite $C\subset \mathbb{N}$ is shattered by $\mathcal{H}$ - which means that $VCdim(\mathcal{H})=\infty$.

To summarize, we do know that being finite means that we are PAC-learnable, but when we are infinite - countably, or uncountably - we cannot be sure.

Additionally, this means that if you know that $\mathcal{H}$ is PAC-learnable, you cannot conclude anything about its size - it could be finite, countably infinite, or even uncountably infinite.

Improve this answer
$\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.