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

相关文章

来自专栏媒矿工厂

【AI视频编码】IEEE ISCAS2018 相关研究进展

ISCAS 2018于2018年5月26日到5月30日在意大利佛罗伦萨举行,会议主题为Art of Circuits and Systems,与佛罗伦萨-欧洲文...

1162
来自专栏机器之心

ICML 2018 | 再生神经网络:利用知识蒸馏收敛到更优的模型

2047
来自专栏思影科技

思影数据处理业务一:功能磁共振(fMRI)数据处理

3114
来自专栏PPV课数据科学社区

【学习】机器学习中的数据清洗与特征处理综述

背景 随着美团交易规模的逐步增大,积累下来的业务数据和交易数据越来越多,这些数据是美团做为一个团购平台最宝贵的财富。通过对这些数据的分析和挖掘,不仅能给美团业务...

2635
来自专栏人工智能头条

贝叶斯深度学习——基于PyMC3的变分推理

4044
来自专栏机器之心

学界 | Jeff Dean等人提出ENAS:通过参数共享实现高效的神经架构搜索

2756
来自专栏Coco的专栏

谈谈一些有趣的CSS题目(十七)-- 不可思议的颜色混合模式 mix-blend-mode

1467
来自专栏瓜大三哥

matlab GUI基础11

神经网络工具 人工神经网络,是对人类大脑系统的一阶特性的一种描述。它是一个数学模型,可以用电子线路来实现,也可以用计算机程序来模拟,是人工智能研究的一种方法。在...

2188
来自专栏机器之心

从1维到6维,一文读懂多维数据可视化策略

4608
来自专栏华章科技

从1维到6维,一文读懂多维数据可视化策略

本文经机器之心(微信公众号:almosthuman2014)授权转载,禁止二次转载

714

扫码关注云+社区