ML基石_56_TheoryOfGeneralization

RECAP

机器学习是可行的,如果假设集H是有限的并且统计样本数据(statistical data)很大。

那么,问题来了,PLA算法中,假设集是二维空间中的直线,有无数条,不符合上面的条件,那么还可行么?

SOLUTION

m增长速度受限

将类似的假设集合并,如果是二分类问题,有N个点的话,理论上会有2^N个分类情况mHm_H,但实际上并不会这么多。

mHm_H: max number of dichotomies B(N,K)B(N,K):如果break point在第k个点上,N个数据点最大的dichotomies ∑k−1i=0C(N,k) \sum_{i=0}^{k-1} C(N,k):B(N,K)B(N,K)的上限,增长速度是O(Nk−1)O(N^{k-1})

mH<=B(N,K)<=∑i=0k−1C(N,k)<=2N

m_H<=B(N,K)<= \sum_{i=0}^{k-1} C(N,k) <=2^N

通过上面的公式,我们知道: 如果可以将mHm_H代替原不等式的M,那么多项式函数的增长速度小于指数函数的增长速度,所以误差率的上限是有保证的,也就是说学习是可行的。

注意: 对于converx图,mH=2Nm_H=2^N,这种情况很难比较。

将m带回原式中的M

通过一些数学变换,可以将m带回原式中的M,得到

这表明,随着数据集的增多,如果mHm_H的增长速度受限,或者说其有break point点,那么当N足够大的时候,学习是可行的。

这就是VC维理论。

例子

总结

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习入门与实践

【深度学习系列】CNN模型的可视化

前面几篇文章讲到了卷积神经网络CNN,但是对于它在每一层提取到的特征以及训练的过程可能还是不太明白,所以这节主要通过模型的可视化来神经网络在每一层中是如何训练...

4476
来自专栏机器之心

教程 | 无监督学习中的两个非概率模型:稀疏编码与自编码器

机器之心整理 作者:Ruslan Salakhutdinov 参与:Smith 「无监督学习」(Unsupervised Learning)现在已经成为深度学习...

3077
来自专栏大数据挖掘DT机器学习

机器学习——感知器学习算法

这里开始介绍神经网络方面的知识(Neural Networks)。首先我们会介绍几个监督式学习的算法,随后便是非监督式的学习。 一、感知器学习算法基本介绍 1...

3628
来自专栏梦里茶室

读论文系列:Object Detection ECCV2016 SSD

转载请注明作者:梦里茶 Single Shot MultiBox Detector Introduction 一句话概括:SSD就是关于类别的多尺度RPN...

2986
来自专栏机器之心

资源 | MIT提出Matlab插件mNeuron:实现深度模型神经元的可视化

选自MIT 机器之心编译 参与:黄小天、Smith 近日,麻省理工学院(MIT)Antonio Torralba 等人发表了一篇题为《mNeuron:...

3356
来自专栏目标检测和深度学习

Google发布机器学习术语表 (包括简体中文)

Google 工程教育团队已经发布了多语种的 Google 机器学习术语表,该术语表中列出了一般的机器学习术语和 TensorFlow 专用术语的定义。语言版本...

2706
来自专栏机器之心

资源 | 从全连接层到大型卷积核:深度学习语义分割全指南

选自qure.ai 机器之心编译 参与:路雪、蒋思源 语义分割一直是计算机视觉中十分重要的领域,随着深度学习的流行,语义分割任务也得到了大量的进步。本文首先阐...

3776
来自专栏用户2442861的专栏

卷积神经网络全面解析

最近仔细学习了一下卷积神经网络(CNN,Convolutional Neural Network),发现各处资料都不是很全面,经过艰苦努力终于弄清楚了。为了以后...

441
来自专栏重庆的技术分享区

吴恩达-神经网络和深度学习(第二周神经网络基础)

1254
来自专栏机器之心

深度 | 结合Logistic回归构建最大熵马尔科夫模型

2688

扫码关注云+社区