从选拔赛说起——泛化误差分析

      机器学习模型的泛化误差用于描述模型推理能力,即从样品数据中推导出的规则能够适用于新的数据的能力。光看上面的说明,泛化误差概念不是很好理解。那么怎么通俗易懂地理解泛化误差呢?这篇博客用选拔赛做例子解释泛化误差的基本知识。

1. 为啥要有泛化误差分析

      假设有一场竞赛, 百科全书中抽取很多很多条目(几乎可以看成百科全书的全部)做题目,答错最少的选手获胜。某学校为了从该校学生中选择一名学生参加这个竞赛,举行了一场选拔赛。因为条件限制,学校只能从百科全书随机抽出一部分条目做题目。这些题目中错误最少的学生将胜出。

      这所学校希望选择对百科全书全部条目答错最少的学生。因为条件限制,学校只能选择答错选拔赛题目最少的学生。但我们心里是没有底的,万一选拔赛获胜的学生只是运气好,选拔赛的题目碰巧是他会做的,怎么办。

      这个选拔赛场景和分类器训练过程很像。为了解决一个分类问题,学习算法期望找到在该问题的所有实例最少错误的分类器。但因为条件限制不能用所有实例训练,学习算法用一部分实例做训练样本,选择最小训练误差的分类器。但我们心里也是没有底的,万一得到分类器只是在训练样本上表现好,怎么办。泛化误差分析将回答我们这些担心。

2. 泛化误差分析的基本框架

      假设\(\pmb{S}\)是所有k个学生的集合。一个学生\(s\)对百科全书中条目是否答错为随机变量z ( 答错为1 ), z以概率\(p(s)\)为1。选拔赛样本的大小为m, 学生在选拔赛中的错误率为\(\hat p(s)\)。\(\hat{p}(s)\)是m个随机变量z的平均值,根据Hoeffding不等式:\(z_1,z_2,..z_m\)是m个独立地服从相同贝努利分布Bernouli(\(p(s)\))随机变量,又\(\hat p(s) = \frac{\sum_{i}^{n}z_i}{m}\),则有对于任意\(\gamma>0\),有
\begin{equation}
p(|p(s)-\hat{p} (s)| > \gamma) \le 2\exp(-2\gamma^2m)
\end{equation}
让事件\(A_i\)为第i个学生的泛化误差和训练误差之间的差值大于\(\gamma\),
\begin{eqnarray}
\label{eq2}
p(\exists s \in S, |p(s)-\hat{p} (s)| > \gamma) &=& p(A_1 \cup …\cup A_k) \nonumber\\
& \le & \sum_{i=1}^{k}p(A_i) \nonumber\\
& \le & 2k\exp(-2\gamma^2m)
\end{eqnarray}
转换下得
\begin{eqnarray}
p(\forall s \in S |p(s)-\hat{p} (s)| < \gamma) \ge 1-2k\exp(-2\gamma^2m)
\label{eq3}
\end{eqnarray}
令\(\delta=2k\exp(-2\gamma^2n)\),则有\(\gamma = \sqrt{\frac{1}{2m}log\frac{2k}{\delta}}\)。可得,对于所有学生\(s \in S\),下列式子以概率\(1-\delta\)成立
\begin{equation}
\label{eq:gap}
p(s) \le \hat{p}(s) + \sqrt{\frac{1}{2m}log\frac{2k}{\delta}}
\end{equation}
其中k为学生数目,m为选拔赛题目个数。直观地解释公式上面的公式:k越大,各种各样的学生数越多,p(s)和\(\hat{p}(s)\)的差距越大;m越大,选拔赛的题目越多,越能反映学生真实水平,p(s)和\(\hat{p}(s)\)的差距越小。

      假设对百科全书中条目答错最少的同学为\(st\),而选拔赛胜出的同学为\(sc\)。那么这两位学生泛化误差的差值是多少呢?我们有
\begin{eqnarray}
p(sc) \le \hat{p}(sc)+\sqrt{\frac{1}{2m}log\frac{2k}{\delta}} \nonumber \\
\le \hat{p}(st)+\sqrt{\frac{1}{2m}log\frac{2k}{\delta}} \nonumber \\
\le p(st)+2\sqrt{\frac{1}{2m}log\frac{2k}{\delta}}
\label{con}
\end{eqnarray}

      上面的式子说明,学习算法得到分类器的真实错误率和所有分类器中最小错误率之间的差值,不超过泛化误差的2倍。

      以上就是泛化误差分析最基本的知识。大家很容易看出缺陷来,1.上述情况只是对二分类问题(答对或者答错百科全书中的条目)进行分析, 2).分类器个数还是有限的(学生数\(k\)是有限的。实践中,候选分类器的个数一般是无限的, 因此第2点尤为致命。对于分类器无限的情况,就得利用到vc维的知识去刻画其中的k。

3. 附录

Hoeffding不等式
\(z_1,z_2,..z_m\)是m个服从相同贝努利分布Bernouli(\(\phi\))的独立同分布的随机变量。\(p(z_i=1)=\phi\)。让\(\hat \phi = \frac{\sum_{i}^{n}z_i}{m}\)。则有对于任意对于\(\gamma>0\),有
\begin{equation}
p(|\phi-\hat \phi| > \gamma) \le 2exp(-2\gamma^2m)
\end{equation}

      文章结尾欢迎关注我的公众号,每周日的更新就会有提醒哦~

weixin_saomiao

      

此条目发表在算法荟萃分类目录,贴了标签。将固定链接加入收藏夹。

从选拔赛说起——泛化误差分析》有 9 条评论

  1. cannon0101说:

    印象中记得那条不等式不是从大数定理推导的 是hoeffding不等式?

  2. Doraemon说:

    一点小笔误,δ=2exp(−2γ2n), 应该是 δ=2k*exp(−2γ2n),少了k

  3. 匿名说:

    有个地方说的不是很严谨,
    “可得,对于所有学生s∈S,下列式子以概率1−δ成立”,
    应该为”下列式子成立的概率大于1−δ”

    相应的后面的结论,也应该改为发生的概率大于1−δ

  4. 匿名说:

    还有就是 Hoeffding不等式 成立的条件并不需要 i.i.d., 只需要随机变量间满足相互独立且每个随机变量都是有界的条件即可[1]

    [1] https://zh.wikipedia.org/wiki/Hoeffding%E4%B8%8D%E7%AD%89%E5%BC%8F

发表评论

电子邮件地址不会被公开。