文章目录
  1. 1. 机器学习9—学习理论的基础知识
    1. 1.1. 基本符号
    2. 1.2. 基本公式
    3. 1.3. 两个引理
    4. 1.4. $H$为有限的
    5. 1.5.
      1. 1.5.1. shatters的定义
      2. 1.5.2. VC维的定义:
      3. 1.5.3. 最终我们得到学习理论中的重要理论:
        1. 1.5.3.1. 1、定理:得到 $\gamma$ 的值
        2. 1.5.3.2. 2、推论:得到$m$的值
      4. 1.5.4. 总结

机器学习9—学习理论的基础知识

基本符号

  • $\epsilon$ 泛化误差:
    • 从训练样本数据中推导的规则,能够适用于新的样本的能力。
    • 对服从分布D的样本,分类错误的概率
  • $\hat{\epsilon}$ 训练误差
    • 训练误差在训练样本中训练出的规则,能够适用于训练样本的能力。
    • 对训练样本,分类错误的部分,在总的训练集中所占比例**
  • $h$
  • $\hat{h }$
    • $\theta$ 和 $\hat{\theta }$关系:ERM风险最小化$\theta$的过程:
  • $h$和 $\hat{h }$关系:ERM风险最小化$h$的过程:
  • $\epsilon$和$\hat{\epsilon}$关系:误差随着模型复杂度(VC维)的增加的变化趋势。模型复杂度过低:欠拟合;过大:过拟合。其中,模型复杂度为假设类$\left| H\right|$的大小,比如:某一个值为多项式多次。

  • $H$:假设类。对于先行分类器:

  • $D$: 某一种分布。

基本公式

1、
2、
3、

两个引理

1、联合界引理:

2、Hoeffding不等式

利用中心极限定理进行推导。其物理意义如下图所示。其中,表示阴影的概率,即错误的上届概率。当m增大时,钟形图收缩,误差下降。

$H$为有限的

即:
其中,H为:
1、
2、
即:

表示:

  • $m$很大时,右边很小,两个误差很接近。
  • 是人为给定的值。

3、对于任意h:

4、对于任意非h:

$m$很大时,右边很小,两个误差很接近。称为:一致收敛

5、我们关心的是m(样本大小), (两个误差的差值)和概率(两个误差接近的概率)三者的值。下面,我们对其进行求解。
6、令,当时,我们得到样本的大小:

7、进一步,我们得到的值:

8、对7进行展开:

9、最终得到我们的定理:得到 $\gamma$ 的值

物理意义:我们可以近似地认为:为假设类H的偏差bias;为假设的方差variance。偏差表示误差的大小,随着模型复杂度增大而减小;方差表示拟合得有多好,随着模型复杂度增大,而先减小后增大。如下图:

10、最终,我们还得到另外一个定理,简而言之,固定,求m:

两个误差收敛的概率

下面开始为第10j

$H$为无限的—更实用

当H有无限值时,即:$|H|=\infty=k $。则上面公式10中,k将趋于无穷大;则m将无穷大。显然,这样是不行的。为了解决这种问题我们引入VC维。从而得到我们的理论。

shatters的定义

VC维的定义:

结论:对于n维线性分类器:$VC(H)=n+1$
eg. 时:$VC(H)=3$

最终我们得到学习理论中的重要理论:

1、定理:得到 $\gamma$ 的值

  • m为样本数目;
  • 从而我们可以得到$\gamma$的值。

2、推论:得到$m$的值

总结

通过学习本节我们可以大概知道:SVM和LR都不是直接的ERM算法,都是对其近似。本章推荐的理论给出了这两种算法的直观含义的一种解释。如下图:

文章目录
  1. 1. 机器学习9—学习理论的基础知识
    1. 1.1. 基本符号
    2. 1.2. 基本公式
    3. 1.3. 两个引理
    4. 1.4. $H$为有限的
    5. 1.5.
      1. 1.5.1. shatters的定义
      2. 1.5.2. VC维的定义:
      3. 1.5.3. 最终我们得到学习理论中的重要理论:
        1. 1.5.3.1. 1、定理:得到 $\gamma$ 的值
        2. 1.5.3.2. 2、推论:得到$m$的值
      4. 1.5.4. 总结