Skip to main content
Tweeted twitter.com/#!/StackCSTheory/status/458206427434459136
fixed typo
Link
Suresh Venkat
  • 32.2k
  • 4
  • 97
  • 272

Testing is Is testing easier/headerharder than learning?

Source Link
Ram
  • 639
  • 3
  • 14

Testing is easier/header than learning?

How is the Property testing is related to PAC model of learning?

More precisely,

Let we have given a property tester, $\mathcal{A}$, for the (concept) class of function $\mathcal{F_n}$ which receives as input a size parameter $n$ (labeled input $(x_1,f(x_1)), (x_2,f(x_2)),...,(x_n,f(x_n))$), distance parameter $0<\epsilon<1$, confidence interval $0<\delta<1/2$, and does the following:

-if $f\in \mathcal{F_n}$, then with probability probability $(1-\delta)$ (over the choice of $x_i$'s) $\mathcal{A}$ accepts $f$.

-if $f$ is $\epsilon$-far from $\mathcal{F_n}$, then with probability probability $(1-\delta)$ (over the choice of $x_i$'s) $\mathcal{A}$ rejects $f$.

Now, I have following two questions:

  1. Now, how this tester $\mathcal{A}$ can be used to generate learning algorithm (under PAC learning model) for the concept class $\mathcal{F_n}$, and vice versa. And how does VC-dim of $\mathcal{F_n}$ plays role in the reduction.

  2. Can we give some sort of characterization (for example, on the basis of VC-dim) over the concept class for which testing is easier/harder than learning?

Pls let me know if I am not able to put the question clearly.

Thanks.