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 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

集成模型的五个基础问题

引言 如果你曾经参加过数据科学竞赛,你一定意识到集成模型(Ensemble Modeling)举足轻重的作用。事实上,集成模型提供了最有说服力的方式之一,来建立...

1765
来自专栏机器学习之旅

浅入浅出深度学习理论实践前言CNN/RNN理解Attention理解深度学习传统领域的应用关于深度学习一些想法

之前在知乎上看到这么一个问题:在实际业务里,在工作中有什么用得到深度学习的例子么?用到 GPU 了么?,回头看了一下自己写了这么多东西一直围绕着traditio...

752
来自专栏MixLab科技+设计实验室

机器学习的应用

01/20 最近在系统地学习斯坦福大学的机器, 共有20课,这是第一课《机器学习的动机与应用》的学习心得。 一、监督学习 特点:提供标准答案的训练数据 任务...

2928
来自专栏技术翻译

关于AutoML和神经结构搜索,你需要知道这些

AutoML和神经结构搜索(NAS)是深度学习城堡的新国王。它们是一种快速的方法,可以在不需要太多工作的情况下为机器学习任务获得很高的准确性。

250
来自专栏人工智能

从基础知识到实际应用,一文了解机器学习非凸优化技术

选自arXiv 优化技术在科技领域应用广泛,小到航班表,大到医疗、物理、人工智能的发展,皆可看到其身影,机器学习当然也不例外,且在实践中经历了一个从凸优化到非凸...

17710
来自专栏机器学习算法与理论

《白话深度学习与Tensorflow》学习笔记(5)强化学习(reinforcement learning)

强化学习(reinforcement learning)本身是一种人工智能在训练中得到策略的训练过程。 有这样一种比喻:如果你教一个孩子学古筝,他可以躺着,趴着...

4849
来自专栏ATYUN订阅号

DeepMind研究:测试神经网络的抽象推理

机器能学会抽象推理吗?这是谷歌子公司DeepMind发表的一篇新论文的主题,题为“Measuring abstract reasoning in neural ...

914
来自专栏机器之心

从基础知识到实际应用,一文了解「机器学习非凸优化技术」

3378
来自专栏ml

Use of Deep Learning in Modern Recommendation System: A Summary of Recent Works(笔记)

注意:论文中,很多的地方出现baseline,可以理解为参照物的意思,但是在论文中,我们还是直接将它称之为基线, 也就是对照物,参照物. 这片论文中,作者没有...

3679
来自专栏人工智能快报

美MIT研发“数据科学机器”

在2015年10月19至21日召开的电气电子工程师学会(IEEE)数据科学和先进分析方法的国际会议上,美国麻省理工学院(MIT)研究人员James Max Ka...

33311

扫码关注云+社区