ML基石_7_VC

recap

之前,讨论了 theory of generation,也就是如果EinE_{in}很小的时候,什么时候可以推至EoutE_{out}也很小。 我们的答案是,如果mH(N)m_H(N)在某些地方出现了一线曙光,也就是出现了break point,造成了不能shatter,增长速度达不到2N2^N的速度的点,那么它的上限是poly多项式,同时如果N也很大的话,可以确定犯错误的上限在一定程度内。

more on growth function

当N>2,K>3N>2,K>3时,mH(N)<=NK−1m_H(N)<=N^{K-1},上限是一个多项式。

more on VC bound

保证了无论演算法做了任何的选择,都被VC bound所支配,保证挑出来的假设hh可以使得Ein≈EoutE_{in} \approx E_{out}。

VC Definition

the formal name of maximum non-break point

比dvcd_{vc} 大1的话,就是break point k。

dvc=mink−1

d_{vc} = \min k -1

好的HsetH_{set},一开始是说增长函数有漏出一线曙光,出现break point的点。现在可以说dvcd_{vc}有限的假设集就是好的假设集。

VC of perceptrons

对于特定的N,shatter的话只举一个例子就可以了,不shatter的话必须保证对于N个点的所有可能分布都不能shatter。

Revisited 2d

dvc>=d+1

只需要证明d+1个点的情况下可以shatter。

dvc<=d+1

只需证明d+2个点的情况下不可以shatter。

linear dependence restricts dichotomy.

physical intuition of VC

d+1d+1就是d个perceptron的维度。

w就是degree of fredom 物理意义大致是:假设集,做二元分类的话有多少自由度(effective)。 举例子来说,二维的感知器有三个自由度(w0,w1,w2)。

powerfulness of H,可以产生多少个dichonomy。

有多少可以调的旋钮。代表H的自由度。

interpreting VC

model越强,vc更高,越能够shatter二分类,需要付出的model complety代价很大。

EinE_{in}做好不一定是最好的选择,可能会付出很大的模型复杂度的代价Ω\Omega。

penalty for model complexity

EoutE_out和EinE_{in}的差距和Ω\Omega有关

VC message

一般来说,我们考虑EoutE_out的容忍上限。

通常,我们希望vc很大,这样的话可以shatter的点很多,假设集的power更强,因此通常可以在EinE_{in}上取得很好的效果。 但是,当模型的复杂度上升的时候,EoutE_{out}的误差上限变大,也就是无法保证测试集外的结果和训练集有同样的高正确率,这样即使训练集内部正确率再高也无用。

因此,需要选择合适的vc,也就是选择合适的假设集,合适的模型复杂度。

sample complexity

一般来说,我们希望将犯错的的bound限制在一定的范围内,但是误差限度是提前制定的,这时候便需要考虑样本集的数量的。

样本集数量和bound的变化趋势如下图所示,因为这个bound的过程中有很多上限化简,因此理论的和实际的有所差异。

looseness of VC bound

理论和实际的差异如下。

有差异也不一定坏啊,这种差异是建立在模型泛化的基础上,从而可以使VC bound的适用条件变宽。

对于之后学习的模型,甚至可以用vc去比较。

summary

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯高校合作

NIPS2018 | 腾讯AI Lab入选20篇论文,含2篇Spotlight

被誉为神经计算和机器学习领域两大顶级会议之一的NIPS于近日揭晓收录论文名单,此次为第32届会议, 12 月 3 日至 8 日在加拿大蒙特利尔举办。 腾讯AI...

401
来自专栏腾讯高校合作

ECCV 2018 | 腾讯AI Lab解读19篇入选论文

901
来自专栏腾讯技术工程官方号的专栏

NIPS2018 | 腾讯AI Lab入选20篇论文,含2篇Spotlight

? 被誉为神经计算和机器学习领域两大顶级会议之一的NIPS于近日揭晓收录论文名单,此次为第32届会议,将于 12 月 3 日至 8 日在加拿大蒙特利尔举办。 ...

13.4K3
来自专栏机器之心

专访MIT教授Tomaso Poggio:表达、优化与泛化——数学视角里的深度学习

机器之心原创 作者:邱陆陆 三月,受腾讯 AI Lab 学术论坛邀请,机器之心在深圳采访了深度学习理论研究著名学者 Tomaso Poggio。他以平直易懂的语...

3376
来自专栏腾讯技术工程官方号的专栏

CVPR 2018 | 腾讯AI Lab入选21篇论文详解

腾讯AI Lab共有21篇论文入选,位居国内企业前列,我们将在下文进行详解,欢迎交流与讨论。

1.9K18
来自专栏AI科技评论

学界 | 腾讯 AI Lab 解读19篇 ECCV 2018 入选论文

计算机视觉欧洲大会(European Conference on Computer Vision,简称ECCV)将于9月8日-14日在德国慕尼黑举办,该会议与C...

542
来自专栏AI科技评论

动态 | 2017年里,哪十篇 arXiv 机器学习论文在 Twitter 上最热门?

AI 科技评论按:随着 2017 年结束、2018 年开始,各个媒体和研究者都撰写了各自的年度总结和新年祝愿。在过去一年的论文动态里,除了研究者们在总结文里根...

4179
来自专栏AI科技评论

大会 | 腾讯AI Lab 21篇CVPR 18录用论文详解

AI 科技评论按:CVPR 2018 日前已公布录用名单,腾讯 AI Lab 共有 21 篇论文入选。本文转载于「腾讯 AI 实验室」, AI 科技评论经授权转...

4165
来自专栏新智元

如何评价周志华深度森林模型,热议会否取代深度学习 DNN

【新智元导读】昨天,新智元报道了南京大学周志华教授和冯霁的论文“深度森林”,引发很多讨论。今天,新智元整理了网上一些评价。中文内容来自知乎,已经取得授权。外网内...

3785
来自专栏AI科技评论

业界 | 谷歌研究院在化学发力:应用机器学习技术预测分子性质

最近,机器学习在化学领域的应用有很大进展,特别是化学搜索问题,从药物筛选、电池设计到OLEDs设计,催化剂的发现。 历史上化学家使用薛定谔方程做数值近似来解决化...

3719

扫码关注云+社区