VC维理论

机器学习 斯坦福

给定一个集合$S=\lbrace x^{(i)},\dots,x^{(d)}\rbrace$，我们说一个假设类$H$能够分散集合$S$，如果$H$能够实现该集合的任意一种标记方式。即，如果对于任意标记集合$\lbrace y^{(1)},\dots,y^{(d)}\rbrace$，都存在$h\in H$能够使得$h(x^{(i)})=y^{(i)}$对于任意$i = 1,\dots,d$成立。