I would like to see the proof or a refernce to it. I feel it is obvious but my tutor insists the other way (agnostic PAC is a subset of PAC, and there are problems in PAC that are not angostic PAC).
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
The trivial implication is:
$\mathcal{C}\subseteq 2^\mathcal{X}$ is agnostic PAC learnable $\Rightarrow$ $\mathcal{C}$ is PAC learnable
Intuitively, being agnostic PAC learnable is a stronger condition, since you can, for all distributions on $\mathcal{X}\times\{-1,1\}$, get close to the optimal error (in particular, you can do so when the labels are forced to be consistent with some $c\in\mathcal{C}$).
To see this formally, suppose a concept class $\mathcal{H}\subseteq 2^{\mathcal{X}}$ is agnostic PAC learnable. This means that there exists an algorithm $A$, such that for all $\epsilon,\delta>0$ there exists $m\in\mathbb{N}$ such that for all distributions $\mathcal{D}$ over $\mathcal{X}\times\{-1,1\}$, and a set of labeled samples $(x_i,y_i)_{i=1}^{n\ge m}$ drawn from $\mathcal{D}$, $A$ outputs $h\in\mathcal{H}$ such that:
$err(h)\le err^*(\mathcal{D})+\epsilon$, with probability $\ge 1-\delta$, where $err^*(\mathcal{D})$ is the error rate of the optimal hypothesis relative to $\mathcal{D}$.
To show that $\mathcal{H}$ is PAC learnable, let $h\in\mathcal{H}$ be some target concept, and let $\mathcal{D}$ be any distribution over $\mathcal{X}$. Examine the distribution $\mathcal{D}'$ on $\mathcal{X}\times\{-1,1\}$ obtained by drawing $x\in\mathcal{X}$ according to $\mathcal{D}$, and taking the pair $\left(x,h(x)\right)$. Note that $err^*\left(\mathcal{D}'\right)=0$, which means there exists an algorithm $A$ which produces a hypothesis in $\mathcal{H}$ with small generalization error (you can complete the details yourself, this shows you that all you need to do is unfold the definitions).
The opposite implication (agnostic PAC learnability follows from PAC learnability) is also true, since they are both equivalent to $\mathcal{C}$ having a finite VC dimension, but this is much harder to show.
-
-
1$\begingroup$ $\mathcal{C}$ is your hypothesis class, which is a set of functions from the instance space $\mathcal{X}$ to $\{-1,1\}$, hence I wrote $C\subseteq 2^{\mathcal{X}}$. The property of being PAC learnable relates to such classes (no sense in talking about pac learning before precisely defining what do we want to learn). $\endgroup$– ArielJun 7, 2017 at 17:07
-
1$\begingroup$ Regarding your second question, they are both different characterizations of the same object, and this requires proof (you don't know this in advance). Additionally, this is somewhat like saying, why talk about circles, when I can talk about the equation $x^2+y^2 = r^2$. Sure, as sets of points on the plane, they are equal, but the difference between the representations gives you a new perspective, and allows you to manipulate geometric objects using algebra. $\endgroup$– ArielJun 7, 2017 at 17:08
-
1$\begingroup$ In the standard PAC setting, your samples are labeled according to some $c\in\mathcal{C}$. $D'$ always labels with respect to some concept. $\endgroup$– ArielAug 1, 2020 at 16:26
-
1$\begingroup$ Learnability (realizable or agnostic) is a property of a class of functions, $\mathcal{C}\subseteq 2^\mathcal{X}$. Nowhere am I required to show that a target function exists, this is part of the setting of realizable PAC learning. The claim is, that if $\mathcal{C}$ is such that for every distribution on $\mathcal{X}\times\{0,1\}$ you could get close to the optimal error, then for every target function and distribution on $\mathcal{X}$ you can get close to the target. $\endgroup$– ArielAug 5, 2020 at 0:01