# Pac learnable when changing distribution

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

• The usual rule is one question per post. – Yuval Filmus Jun 7 '17 at 19:46
• @YuvalFilmus but it is on the same example, should i copy paste it? – Ayelet Jun 7 '17 at 20:05
• You can wait for the answers. If they answer both questions, then it's ok. – Yuval Filmus Jun 7 '17 at 20:18

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