PAC learner

SSU SMU | [PAC model], [succesful PAC learner]

Let there be $\delta ,\epsilon \in (0,1)$

It is an algorithm, which trains a predictor for given class $\mathcal{H}$. If the following holds, it’s a successful PAC learner. ${\mathbb{P}}_{T_m\sim p^m}(|R(p,h_m)-R(p,h_{\mathcal{H}})|\le \epsilon )\ge 1-\delta$given

• $ϵ$ - error parameter
• $\delta$ - confidence parameter

Introduction to computational learning variant

(The PAC Model, Modified Definition) Let $T_m$ be a representation class over $X_n$ (where $X_n$ is either $\{0,1{\}}^n$ or n-dimensional Euclidean space ${\mathbb{R}}^n$), and let $X=$ $T_m$’

We say that C is PAC learnable if there exists an algorithm L with the following property: for every concept c E C, for every distribution V on X, and for all 0 < E < 1/2 and 0 < D < 1/2, if L is given access to EX(c, ‘D) and inputs f and 6, then with probability at least 1- D, L outputs a hypothesis concept hE C satisfying error (h) � E. This probability is taken over the random examp

we allow the learning algorithm time polynomial in $n$ and $|c|$ (as well as $1/\epsilon$ and $1/\delta$ as before) when learning a target concept $c\in T_m$.