HW$5$ Theory $+$ SVM

PAC Learning and VC dimension $(30$ pts$)$

Let X$=$R$^2.$ Let

C$=$H$=\{$h$($r$\_1,$r$\_2)=\{($x$\_1,$x$\_2)($x$\_1^2+$x$\_2^2>=$r$\_1$@x$\_1^2+$x$\_2^2<=$r$\_2)\}\},$ for $0<=$r$\_1<=$r$\_2,$

the set of all origin$-$centered rings.

$(8$ pts$)$ What is the VC$($H$)?$ Prove your answer.

$(14$ pts$)$ Describe a polynomial sample complexity algorithm L that learns C using H$.$ State the time complexity and the sample complexity of your suggested algorithm. Prove all your steps.

In class we saw a bound on the sample complexity when H is finite.

m$>=1/\backslash$epsi $($ln$|$H$|+$ln$1/\backslash$delta $)$

When $|$H$|$ is infinite, we have a different bound:

m$>=1/\backslash$epsi $(4$ log$\_22/\backslash$delta $+8$VC$($H$)$ log$\_213/\backslash$epsi $)$

$(8$ pts$)$ You want to get with $95\%$ confidence a hypothesis with at most $5\%$ error. Calculate the sample complexity with the bound that you found in b and the above bound for infinite $|$H$|.$ In which one did you get a smaller m$?$ Explain.