# Tag Info

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 ...