Pac learnable when changing distribution

Question

if H is Pac learnable according to

Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and for every labeling function $f \colon X \mapsto \{0,1\}$, if the realizability assumption holds with respect to $H,D,f$, then when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L_{(D,f)}(h) \leq \varepsilon.$$

and the algorithm returns h* (for specific S of size $m_H(\varepsilon, \delta$) and distribution D) , I can define a distribution D' that gives 0 for each x s.t. h*(x)=f(x) and that will give me $L_{D'}(h*)=1$. I am trying to understand why this is ok (not a contradiction for H being PAC), so I have 2 questions on this: $$$$ 1. my guess is that since the algorithm does not depend on the distribution but does on S (that depends on it), we will probably get with the new distribution D' a different S that will return a different h that keeps us with $L_{(D',f)}(h) \leq \varepsilon.$ with probability $1 - \delta$. Is this the right explanation? $$$$ 2. After defining the new distribution D' is it right to say that (D',f,H) still hold the realizability assumption? I don't see why not but want to be sure.

definition 2.1 (The Realizability Assumption) There exists $h* \in H$ s.t. $L_{(D,f)}(h*) = 0.$. Note that this assumption implies that with probability 1 over random samples, S, where the instances of S are sampled according to D and are labeled by f, we have $L_S(h*) = 0$.

Thank you

Answer 1

I think the definitions in that book are unclear. If you note, the realisability assumption is not stated as an assumption on anything, nor as a standalone definition, so that already is a bit confusing. I have struggled to find one anywhere that is clear actually.

It appears to me that The Realisability Assumption is also dependent on the distribution $D$ and the labelling function $f$. That is the trio ($H, D, f$) can be realisable. $H$ in and of itself cannot be realisable.

It took me some sleuthing to come to this conclusion, and I hope it is the right one. I think you are nearly on the right lines of thinking. Here is my thinking:

As you say, if we choose a distribution that causes problems then perhaps we can prove that $L(h) = Err(h) > 0$. If you assume $H$ is finite, and $f$ is not in $H$, then we can find problematic points $x$s and put positive probabilities on them. Then for every $h$ in $H$, $L(h) > 0$; i.e. $H$ is not actually realisable with respect to any distribution.

We have made an assumption that $H$ is finite, but given that the book later on goes on demonstrate results with realisability, and finite $H$, I think we should assume that realisability and finite $H$ together are a valid consideration, and therefore, we cannot assume that realisability holds across any distribution over the domain set $X$. I think therefore we should assume that that is what they meant when defining realisability.

Similarly for the labelling function $f$. If $H$ and $D$ are realisable, independently of $f$, then in the case where $H$ is finite and contains only one hypothesis $h$, we can choose an $f$ that is different to h on the whole domain, which would result in $Err(h) = 1$.

So here's how I would state the Realisability Assumption:

Definition (The Realisability Assumption) Given a learning problem with distribution $D$ over the domain set, and labelling function $f$, then a set of hypotheses, $H$, is Realisable if there exists $h* \in H$ s.t. $L_{(D,f)}(h*) = 0$.

Note that you do not need to know what $D$ and $f$ are to assume that $H$ is realisable with respect to them. We can just assume that $H$ is realisable with respect to them, whatever they may be.

So, assuming realisability in PAC Learnability also restricts $D$ and $f$ to be those which are realisable w.r.t. $H$.