Let D be a distribution over X{0,1}, and let S={(x1,y1),,(xm,ym)} be a random sample from D. LD(f)LS(f)=P(x,y)D[f(x)=y],=m1i=1m1[f(xi)=yi], where 1[A] is 1 if A is true and 0 otherwise. Let fS and fbest be the hypotheses in F with minimum training and true error, respectively: fSfbest=fFargminLS(f),=fFargminLD(f). Be sure to keep in mind that, unlike fbest,fS is random because it depends on the random training samples in S. Important: Do not make other assumptions than the ones above! Show that E[LS(fS)]LD(fbest)E[LD(fS)]