机器学习基石：05 Training versus Testing
2024-08-26 19:06:27
train：A根据给定训练集D在H中选出g，使得Ein(g)约等于0；
test：g在整个输入空间X上的表现要约等于在训练集D上的表现，使得Eout(g)约等于Ein(g)。
如果|H|小，更易保证test（不等式右式小），难保证train（选择少）；
如果|H|大，更易保证train（选择多），难保证test（不等式右式大）。
如果|H|无限呢？2Mexp(...)可能大于1了，对于概率值上限来说失去意义。那能否用个有限值代替|H|呢？
看一下2Mexp(...)这个上限的来源。
本质是求并集，但是得出2Mexp(...)这个式子是默认无交集的情况下求的并集，
实际上，A确定后，H形式也确定，
给定D，在H里存在相似的h，这些h在D上的表现一致，即存在交集，所以2Mexp(...)这个式子作为上限来说过大了。
给定D，可通过将H里相似h分到同类里（同类里h的数目可能是无限的），将|H|变为类数，就可能将无限的|H|变为有限的类数。
定义给定D下，将|H|分得的类为dichotomies，每一个dichotomy在D上表现相同。
假设D里有2个样本点，将D分为OO、OX、XO、XX的h分别归为一类，共有4类。
可以发现dichotomies的数量是依赖于具体D和H的，但是dichotomies的数量的最大值只依赖与D里样本点的个数N和H，
例如感知器算法里，N=2时，最大值不超过2的N次方，这里是4。
定义dichotomies的数量的最大值为N的成长函数，记为mH(N)。------只和H、N有关。
即给定样本数N，H里假设类数是小于等于mH(N)的。
对于2维感知机，mH(1)=2，mH(2)=4，mH(3)=8，mH(4)=14。
可以看出，成长函数可能是多项式型的（好的，能保证只要N足够大，2mH(N)exp(...)小），也可能是指数型的（坏的）。
对于2维及以上维数的感知机，成长函数是多项式型的吗？
shatter：如果H里的假设能够保证k个输入能够输出任意标签的组合，称H能shatter这k个输入。
break point k：H不能shatter这k个输入，称k为断点。
猜想，只要存在断点，就能保证成长函数是多项式型，进而保证了test。
最新文章
- 【转】C#中如何实现左截取和右截取字符串
- 读《程序员的SQL金典》[2]--函数
- [转] 字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽
- RabbitMQ 原文译04--路由
- Java基础知识强化之IO流笔记56：IO流练习之 登录注册IO版
- [Android]Dalvik的BOOTCLASSPATH和dexopt流程
- 设计模式——辛格尔顿（Singleton）
- C++指针和引用简介
- pcommlite串口通讯库使用
- Java经典案例之-判断兔子的数量（斐波那契数列）
- js调试模式控制台输出信息
- python+selenium运行时，提示元素不可见
- json-gson：.isJsonNull()问题-堆栈溢出
- 原生Ajax GET+POST请求无刷新实现文本框用户名是否被注册
- 洛谷P5219 无聊的水题 I [prufer序列，生成函数，NTT]
- Python全栈学习_day004作业
- Error - SqlDateTime overflow. Must be between 1/1/1753 12:00:00 AM and 12/31/9999 11:59:59 PM
- maven的安装以及问题
- 【Alpha】第九次Scrum meeting
- MT【175】刚刚凑巧