Restriction of Break Point e.g: k=2 说明在所有的dichotomy中，任意两个点不能被shatter(shatter就是能够出现所有种排列组合)，即不能出现这两个点的2^k=4种组合。
Bounding function B(N, k):
maximum possible
when break point is k.
解释这张图：
如果k=1，则不管N等于多少，B都等于1，即H set要满足只有一个点都不能被shatter，即dichotomy set的大小不超过1。所以有＋1就不能有－1，所以dichotomy set最多只能有1个dichotomy。所以B＝1，第一列都为1. 如果N
因此可以看出B是m_H的上限。
现在考虑下三角。 当N=4，k＝3。现在有2^4＝16种不同的dichotomy，从中选择不同的dichotomy set，有2^16种set，看看有没有违反3个点被shatter的set。通过遍历得到set的解为
所以B(4,3)=11 通过整理可得右上图。前4组，头3个点相同，x4不同。 B(4,3)=11=2alpha + beta。现在把x4去掉，只看x1-x3
这里有alpha+beta个dichotomy on x1-x3。 因为k=3，所以在N=4中任意3个x不能被shatter，包括x1-x3，所以alpha+beta<=B(3,3)。
如果只看alpha部分，在x1-x3内找出两个点，如果这两个点shatter了，加上x4，就变成了3个点shatter，这不满足条件，因此任意的在x1-x3内的两个点也不能shatter，所以alpha<=B(3,2) 所以有
所以：
所以B(N,k)有上限。
又因为B(N,k)是用来bound m_H(N)的，然后B(N,k)的上限是一个关于N的多项式，因此如果存在k的话，m_H(N)是有一个多项式的上限。
接下来用m_H(N)去取代Hoeffding里的M:
网友评论