Problem $9$ Let $g_n$ be an arbitrary $($data$-$dependent$)$ classifier. The leave$-$one$-$out error estimate

is defined as

$R_n^{(D)}(g_n)=\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{}}}{1}_{\{g_{n-1}(x_i,D_{n,i}))}{Y}_i$

where $D_{n,i}=((x_1,Y_1),$dots,$(x_{i-1},Y_{i-1}),(x_{i+1},Y_{i+1}),$dots,$(x_n,Y_n)).$ Show that the estimate is

nearly unbiased in the sense that

$E{R}_n^{(D)}(g_n)=ER(g_{n-1}).$

Use this to derive a bound for the expected risk of a perceptron classifier when the data are linearly

separable $($i$.$e$.,L^{**}=0$ and the Bayes classifier is linear$).$ In particular, prove that if $g_n$ is the linear

classifier obtained by running the perceptron algorithm, then

$ER(g_{n-1})\frac{1}{n}E[(\frac{R}{}{)}^2],$

where $R=ma{x}_{i}n-1||x_i||$ and $$ is the margin.