记录第一遍没看懂的
记录觉得有用的
其他章节：
        第一章
        第三章
        第五章
        第六章
        第七章
        第八章
        第九章
        第十章
        十一章
        十二章
        十三章
        十四章
        十五章
        十六章

基础知识

        泛化误差：$E(h;D)=p_{xD}(h(x)\ne y)$
        经验误差：$\bar{E}(h;D)=\frac{1}{m}{\sum }_{i=1}^{m}I(h(x_i)\ne y_i)$
        Jensen不等式：对任意凸函数$f(x)$：$f(\mathrm{E}(x))\le \mathrm{E}(f(x))$（其实就是凸函数的定义）
        HoefIding 不等式：

        McDiarmid 不等式：

PAC学习

        PAC-Probably(可能)，Approximaly(近似)，Correct(正确)-概率近似正确。
        PAC辨识：错误率小于一定程度的概率大于一定程度

        PAC可学习：规定数据点个数到什么程度比较好(样本复杂度)
        PAC学习算法：在PAC可学习之上，引入时间复杂度的考虑。
        PAC学习给出的是一个抽象地刻画机器学习能力的框架。

有限假设空间

        有限假设空间都是 PAC 可学习的，所需的样例数目如(12.14) 所示，输出假设的泛化误差随样例数目的增多而收敛到0，收敛速率为$O(\frac{1}{m})$ .

VC维

         VC维的概念是为了研究学习过程一致收敛的速度和推广性。它的定义是：假设空间$\mathrm{H}$的VC维是能被$\mathrm{H}$打散的最大示例集的大小，即 V C ( H ) = m a x { m : ∏ H ( m ) = 2 m } VC(\Eta)=max\{m:\prod_{\Eta}(m)=2^m\} VC(H)=max{m:∏H​(m)=2m}，$VC(\mathrm{H})=d$表明存在大小为$d$的示例集能被假设空间$\mathrm{H}$打散。

下面的定理等，个人感觉，理解需要实际参考，看一遍总感觉懵懵懂懂QWQ，所以从网上又搜了些，感觉这个博客写的比较好：机器学习：VC维的概念和用途

Rademacher复杂度

        Rademacher复杂度是另一种刻画假设空间复杂度的途径，与VC维不同的是，它在一定程度上考虑了数据分布。
        经验误差最小的假设是：然而，由于现实的数据有误差，所以选择假设空间在训练集上表现最好的假设，有时还不如选择事先己考虑了随机噪声影响的假设。

        因此，我们需要考虑随机噪声：

        考虑所有假设，求取期望：

        写的更规范数学一点：

        不止在经验上，定义更大的空间上：

        基于Rademacher复杂度的泛化误差界：对于回归问题：


        对于二分类问题：

稳定性

        引入稳定性的原因：无论基于VC维还是Rademacher复杂度推导泛化误差界，结果都与具体算法无关。虽然这样能够脱离学习算法设计考虑学习问题本质，但仍希望获得算法有关分析结果，就要引用稳定性
         稳定性考察的是算法在输入发生变化时，输出是否会随之发生较大的变化。均匀稳定性的定义为：

         稳定性与可学习性的关系：ERM（经验风险最小化）稳定性与ERM可学习性的等价关系，若学习算法L是ERM且稳定的，则假设空间H可学习