斯坦福CS229（吴恩达授）学习笔记（6）
CS229-notes4
- 说明
- 正文
-
- Problem Set #2: Kernels, SVMs, and Theory
-
- 5. Uniform convergence
说明
此笔记 是cs229-notes4讲义中的学习内容，与B站上的“09 经验风险最小化”视频对应，主要是该部分对应的习题解答。
课程相关视频、讲义等资料可参照《斯坦福CS229（吴恩达授）学习笔记（1）》 获取。
正文
Problem Set #2: Kernels, SVMs, and Theory
5. Uniform convergence
解答：
问题是说，如果有先验知识得知\mathcal{H}中存在使得min_i\varepsilon(h_i)=0的h_i，那么是可以给\varepsilon(\hat h)求得一个比2\sqrt{\frac{1}{2m}log\frac{2k}{\delta}}更小的上界，即\frac{1}{m}log\frac{k}{\delta}。
可证明\frac{1}{m}log\frac{k}{\delta}\leq2\sqrt{\frac{1}{2m}log\frac{2k}{\delta}}。
\begin{aligned} \frac{\frac{1}{m}log\frac{k}{\delta}}{2\sqrt{\frac{1}{2m}log\frac{2k}{\delta}}}=&\sqrt{\frac{\frac{1}{m^2}(log\frac{k}{\delta})^2}{\frac{4}{2m}log\frac{2k}{\delta}}}=\sqrt{\frac{(log\frac{k}{\delta})log\frac{k}{\delta}}{2m(log\frac{k}{\delta}+log2)}}=\sqrt{\frac{log\frac{k}{\delta}}{2m(1+\frac{log2}{log\frac{k}{\delta}})}} \end{aligned}
因为在实际生活中logx<30，所以可得1
\frac{\frac{1}{m}log\frac{k}{\delta}}{2\sqrt{\frac{1}{2m}log\frac{2k}{\delta}}}\leq1
故说新上界much tighter。
（a）根据题意，这些\hat h_i目前仅满足使得\hat \varepsilon(\hat h_i)=0，并不能保证\varepsilon(\hat h_i)=0。反过来也一样，如果存在h_i^*使得\varepsilon(h_i^*)=0，那么\hat \varepsilon(h_i^*)=0却不一定满足。因为根据讲义，\hat h_i与h_i^*并没有什么关系。此题需要证明的是，这些\hat h_i满足\varepsilon(\hat h_i)\leq\frac{1}{m}log\frac{k}{\delta}。题中的"some hypothesis \hat h"指的是\hat h_i，要求证明的不等式关系也只是针对\hat h_i，并不是所有的h\in\mathcal{H}。在讲义中\hat h定义为了\hat h=\argmin_{h\in \mathcal{H}}\hat \varepsilon(h)，而h^*=\argmin_{h\in \mathcal{H}}\varepsilon(h)。
假定使m个general样本全部预测正确的h_i满足\varepsilon(h_i)>\gamma，那么P('h_i预测general样本正确')\leq1-\gamma。
所以对于m个general样本来说，h_i全部预测正确的概率
\begin{aligned} P('对于m个general样本h_i全部预测正确')\leq(1-\gamma)^m\leq e^{-\gamma m} \end{aligned}
那么在\mathcal{H}中，至少有一个h_i使得对于m个general样本h_i全部预测正确的概率
P(\exists h\in\mathcal{H}使得对于m个general样本h全部预测正确)\leq ke^{-\gamma m}
令\delta=ke^{-\gamma m}，可得\gamma=\frac{1}{m}log\frac{k}{\delta}。
所以P(\neg\exists h\in\mathcal{H}使得对于m个general样本h全部预测正确)> 1-\delta，即with\ probability\ 1-\delta，可推翻假定。也就是说with\ probability\ 1-\delta，h_i满足\varepsilon(h_i)\leq\gamma。(证明过程参考了标准答案。)
（b）据（a），\gamma=\frac{1}{m}log\frac{k}{\delta}，所以m越大\gamma越小，with\ probability\ 1-\delta，\varepsilon(\hat h)\leq\gamma的界也就越小。根据m=\frac{1}{\gamma}log\frac{k}{\delta}，所以m\geq \frac{1}{\gamma}log\frac{k}{\delta}