1
Every $f \in F$ is mapped to $f' \in F'$ defined as follows: $f'|_{\Omega \times \{0\}} = f$ and $f'|_{\Omega \times \{1\}} = 1 - f$.
Let us call a subset of $\Omega'$ mixed if it contains both $(\omega,0)$ and $(\omega,1)$ for some $\omega \in \Omega$.
For $S' \subseteq \Omega'$, let $S'|_{\Omega} = \{ \omega \in \Omega : (\omega,0) \in S' \text{ or } (\...
1
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. ...
1
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible