Learnability despite noise

Classification noise

Random noise vs Adversarial noise. Getting (x, l) instead of (x, c(x)).

Malicious noise: both x and c(x) corrupted.

Random Classification noise model

Uniform noise $\eta \le {\eta }_0\in [0,.5)$; $L$ given ${\eta }_0$, also polynomial in $\frac{1}{.5-{\eta }_0}$.

Statistical Query (SQ) learning model

(Kearns). A \textbf{statistical query} (criterion, tolerance) = $(\chi ,\tau )$ yields probability $P{r}_x(\chi )$ or $E_x(\chi )$ of $\chi$ over examples. $\chi$ efficiently evaluatable, $\tau$ not very tiny. $L$ forms h using only statistical queries.

Show non-constructive SQ learnability

If $d=sq{d}_D(C)$ and $S_D=\left\{f_i\right\}$ the corr shattered set; $\mathrm{\forall }f\in$C$,\mathrm{\exists }{f}_i\in S_D:|cor{r}_D(f_i,f)|>(d+1{)}^{-1}$. Let \ $g_S=max(|cor{r}_D(f_i,f_j)|)$; $f_i,f_j\in S$; \(g^{} = \min \set{g_{S}: |S| = d}\) : pick such S; if \(g^{} \leq (d+1)^{-1}\) $sq{d}_D\ge d+1$: absurd; so, $g^{\ast }>(d+1{)}^{-1}$; so swapping any $s\in S$ with $s^{\prime }\in S_D$, get result.

Non uniform algorithm

So make SQs: $\mathrm{\forall }{f}_i\in S_D,E[f_{i}c]=?$ to find $f_j:E[f_{j}c]>(d+1{)}^{-1}$; $Pr(f_j\ne c)\ge 2^{-1}+(d+1{)}^{-1}$. So, $\mathrm{\exists }$ weak learning algorithm for C with running time $O(d^t)$, t constant.

Also $\mathrm{\Omega }(d^{t^{\prime }})$: as $sqd=\mathrm{\Omega }(vcd)$.

Simulate SQ learning

Noise absent: Take many examples to find $P_{\chi }$, use Chernoff. \textbf{Classification Noise} present: Sample ${\eta }_i$ from [0,1/2) at sufficiently small intervals; Express $P_{\chi }$ as combo of probabilities over noisy examples, $\eta$; for each ${\eta }_i$ get $h_i$; gauge noisy errors, return h with least noisy error (which grows like actual error).

Efficient PAC learnability with noise

Any C efficiently learnable using SQ is efficiently PAC learnable with classification noise. So, PAC model more powerful than SQ: $\mathrm{\exists }$ C learnable in PAC+noise, but not learnable in SQ. (Find proof.) But, Folk theorem: most existing PAC algs extensible to SQ algs.

(Also using statistical queries): Conjunctions. k-CNF: by feature expansion.

Halfspaces (\why: Blum etal): Important subroutine for various learning algs.

Learning Parity

$c=p_S$; classification noise. Best algorithm: $2^{\frac{n}{\log n}}$. \why

Learning k-PARITY with random noise: Measure errors of all $O(n^k)$ h over a random sample set of size $O(\frac{1}{1-2\eta }k\log n)$.

If parity learnable in polytime, DNFs efficiently learnable under U: see reduction from agnostic parity learning.

\oprob: If you can learn parity when there is constant noise, can you learn it when $\eta =1/n^r$?

Random persistant classification noise

Classification noise model with modification: $\mathrm{\forall }x$: once mq(x) is returned, all future queries mq(x) elicit the same label.

Motivation: Random classification noise can be beaten if MQ(c) oracle present: For each example, make $poly(\frac{1}{.5-{\eta }_0})$ mq and take majority answer.