Restriction of Break Point

四个成长函数与break point:

假设一个hypotheses,它的break point是2.那么当N=1的时候可以取到两个dichotomies。当N≥2的时候就不能取到所有的dichotomies。当N=2的时候就取不到2^2=4个dichotomies,最多只能取到3个。当N=3时，经过下列实验可知最多可以产生4个dichotomies。(因为breakpoint=2,所以对于N=3的时候，从3个点里面任取2个点都不能满足4个dichotomies，否则就违反题意了。shatter意为覆盖了所有的dichotomies。)

经过一系列实现，得出当N=3时的dichotomies最大为4。

发现，当N>k时，break point限制了m_H(N)值的大小，因为会break point 会对未来每一种排列组合上都被限制。m_H(N)与hypotheses有关，研究breakpoint和其后面点的m_H(N)的大小，如果能证明m_H(N)的最大值的上界是多项式，用m_H(N)代替M，也许可以证明机器学习是可行的。

Bounding Function: Basic cases

bounding function(上限函数)，成长函数在break point的时候最多有多少种可能。对于上限函数的值对应的组合，要求如果只看k个维度不能出现shatter。使用上限函数可以不用计较hypothesis的细节(即成长函数是positive intervals还是1D perceptrons)，只关注成长函数的上届即可。

下面，就是能不能证明B(N,k)≤poly(N)。

求解B(N,k):

之前已经求解过的：B(2,2)=3,B(3,2)=4

当k=1的时候，一个圆一个叉就会被shatter，所有最多只有一种dichotomy。

表的右上半部分，N＜k，B(N,k)=2^N。

当N=k,N是第一次不能shatter的值，B(N,k)=2^N-1。

Bounding Function: Inductive Cases

下面填写表剩下的部分。

以B(4,3)为例，也许与B(3,?)有关，将两者建立联系。

先将B(4,3)的所有情况写下来，一共11种。即如果再加一种就会出现任意3个点会被shattered的情况。

将这11种分为橘色orange和紫色purple两种，其中橘色是两两之间的3个点相同只有第四个点不同，如1和5,2和8。紫色是单一的，不存在两两之间3个点相同的情况，如6,7,9。

去掉X₄然后去掉重复项，得到左图，按照orange和purple分成α和β。所以B(4,3)=2α+β。因为B(4,3)不允许任意3个点出现shatter，所以α+β≤B(3,3)。

再只看orange的部分，X₁X₂X₃中任意两个点不能shatter。如果任意两个点被shatter,那么由于X₄是成对的，这两个点加上X₄就会被shatter。所以α≤B(3,2)。

由此可以将B(4,3)表示成B(3,?)的形式：

推导出一般公式：

根据公式将上面的表格填写完整后得到：

根据递推公式，推导出B(N,K)满足下列不等式：

不等式的右边是最高阶为k-1的N多项式。成长函数会被上限函数限制住，上限函数会被上限的上限限制住，而上限的上限是一个与N和k有关的多项式poly(N)。而证明可以得到≤是=。

接着看之前的成长函数和break point的关系，通过使用上限的上限函数计算后得到：

不管一个成长函数多复杂只要能找到break point就可以找到上限的上限这个函数，然后说成长函数最多跟这个函数成长的一样快。

A Pictorial Proof

如果能将m_H(N)代替M，就能得到E_out≈E_in：

事实上，不能简单的替换：

证明步骤：

然后得到定理Vapnik-Chervonenkies(VC)bound：

• replce - 常数2
• decompose H by kind - m_H(2N)
• use Hoeffding without replacement - 1/8

所有我们解决了2D的perceptron,它的break point是4，那么成长函数m_H(N)=O(N³)。,证明2D的机器学习是可行的。

summary