有效的方程

这是我参与8月更文挑战的第19天，活动详情查看：8月更文挑战

有效的方程 (Effective Number of Hypotheses)

  让我们来回忆下这个M是从哪里来的。记中第m个方程遇到bad sample为事件，则遇到bad sample的概率为其所有方程遇到bad sample概率的联合概率。如果每个方程遇上bad sample这件事是互相独立的，则遇上bad sample的概率是各方程遇上bad sample的概率之和，因此他们的联合概率一定小于等于各个事件单独发生的概率之和。

  但事实上bad event并不是完全独立的。想象两个非常类似的方程，他们遇到bad sample分别为事件与，因为这两个方程很接近，则往往发生时，也会发生，可以说与的重合度很高(overlapping)。

  那么我们就会想，我们能不能把结果接近的那些方程看成一类，譬如有些方程他们的预测结果总是相同或是很接近的。

  假设我们的算法要在平面上挑选一条直线方程作为,，当中有无限多个方程，但我们可以把这些个方程归为两类。一类是把判断成圈圈的，另一类是把判断为叉叉的。

  那如果我们手中有2个数据点和呢？这样的话中无数条直线可以分为4类。用这4类线对和进行预测，一共能产生4种不同的结果。

  那如果我们手中有3个数据点、和呢？

  中最多有8类直线，作用于产生如上8种结果。

  那如果我们手中有4个数据点~，情况又会是怎样。前面的例子中我们基本上把各个数据点的情况用排列组合的方式组合出来即可。但对于4个以上的点而言，就不是那么容易了。

在这16种组合中，就有两种是“直线方程”没有办法产生的结果。因此如果是2维空间中的所有直线，表面上看是在无数条直线方程中去挑，但由于大部分直线方程所产生的结果是一模一样的，结果不一样的直线的类别对应上面的例子分别为2类、4类、8类和14类(Effective Number of Lines)。属于同一类的直线，他们将同时遇到或不遇到bad sample，由于之前那个union bound是基于独立性的假设下的，因此遭遇bad sample的概率明显被夸大了。所以，我们应该把不等式改写为：

作用于能够产生多少不同的结果？ (Dichotomies)

  从中任意选取一个方程，让这个对进行二元分类，输出一个结果向量，比如对4个点进行预测，输出，这样的一个输出向量我们称它为一个dichotomy。不难得出，一个直线方程在中对应一个dichotomy，但一个dichotomy至少对应一个直线方程，我们把一个dichotomy对应的所有直线方程视为一类，则effective number of lines就等于不同中不同的dichotomy的数量。显然这个dichotomy的数量小于等于所有数据点的排列组合数的，例如上图中画大叉的那幅图对应的排列组合，就不能成为一个dichotomy，因为它们无法由任何一条直线方程产生。（当然如果考虑的不是直线方程，则那种排列组合是可以成为一种dichotomy的）
因此我们前面要找的

=平面中能找出多少条不同类的直线
=作用于能产生多少不同的dichotomy。
因为不一定所有排列组合都能成为dichotomy，所以不同的dichotomy的数量一定不会超过排列组合数，上例中如果存在三点共线的情况，则dichotomy的数量会更少，因此：

=作用于“最多”能产生多少不同的dichotomy

成长函数 (Growth Function)

  那么，作用于“最多”能产生多少种不同的dichotomy呢？这个数量与有关，也与数据量有关。用数学式可以表达为：

  上式又称为成长函数（growth function）。在确定的情况下，growth function是一个与N相关的函数。以下是几种常见的Hypothesis Set的成长函数。

1. Positive Rays
   
   输入空间为一维实数空间。大于threshold a的预测+1,否则预测-1。 for example: 当N=4时，Positive Rays作用于~，共能产生5个不同的dichotomies。如下图：
   
   不难去想，4个点，5个可能的切点，最多产生5种dichotomies。因此Positive Rays的成长函数为：
2. Positive Intervals
   
   和前面的类似，只不过Positive Intervals有两个threshold，夹在两个threshold之间的预测为+1，其余预测为-1。 for example: 当N=4时，Positive Intervals作用于~，共能产生11种dichotomies。如下图：
   
   同样不难去想，4个点，5个可能的切点选两个作为threshold，加上两个threshold重合产生的一种，因此Positive Intervals的成长函数为：
3. Convex Sets
   
   任选k个点，在这k个点组成的convex多边形包围内的所有点都预测+1，否则预测-1。前面我们说到成长函数描述的是“最多”能产生的dichotomy种数，因此如果我们这N个input摆成一个圈，则这N个点的任意一种排列组合都能成为一个dichotomy。因此Convex Sets的成长函数为：

坏掉的散弹枪 (Shatter & Break)

  当作用于有N个inputs的时，产生的dichotomies数量等于这N个点的排列组合数时，我们就称这N个inputs被给shatter掉了。或者也可以说产生的个dichotomies把这N个点的种排列组合给shatter了。

  这个shatter的意思似乎不太好理解，这是林老师在讨论区中的回复：

  “大家對 break point 的討論很好，不過注意到 shatter 的原意是「打碎」，在此指「N 個點的所有(碎片般的)可能情形都被產生了」。所以 的情形是「shatter」。”

  我从打游戏过关的角度去理解，shatter作打碎理解：

  “是把散弹枪，在每个关卡(level N)中，他可以有发小子弹（每发小子弹对应一种dichotomy），而你面临的是个敌人。你得一枪打出去shatter掉所有人。对于这把散弹枪来说，第一关和第二关都还好，第三关6发小子弹shatter不掉8个人，于是它就break了。”

  对于给定的成长函数，从出发，N慢慢增大，当增大到k时，出现的情形，则我们说k是该成长函数的break point，对于任何个inputs而言，都没有办法再shatter他们。

  不难根据成长函数得出Positive Rays成长函数的break point为2，Positive Intervals成长函数的break point为3，Convex Sets不管N多大都可以去shatter掉那N个点，因此它的成长函数没有break point。2D Perceptrons的break point为4，因为在N=3时，它都能够shatter，产生种dichotomies，当N=4时，它不能够shatter，最多只能产生14 () 种dichotomies，因此2D Perceptrons成长函数的break point为4。

拿什么来镇镇成长函数 (Restriction of Break Point)

  有些的成长函数很容易找到，比如前面说到的Positive Rays、Positive Intervals以及Convex Sets；有些则没有那么容易，比如2D perceptrons，我们无法直接看出它的成长函数是什么，那么我们对于这样的就没辙了吗？也不完全是，至少我们手上还掌握着它的break point，能不能用这个break point干点事呢？如果没办法得到成长函数，能得到成长函数的upper bound也是不错的。

  先用例子来看看，当我们完全不知道是什么，只知道它的break point k时，作用于“最多最多”可以产生多少这dichotomies。注意这里我用了两个“最多”，由于我们无法确切知道成长函数，因此我们用这个break point推算出的这个dichotomies的数量仍然是个高估值，这个高估值实际上是任何break point为k的作用于所真实产生的dichotomies数量的上界 (upper bound)。

  举例说明，假设我们不知道某个的成长函数，但知道它的break point k=2，那么作用于N=3的时，“最多最多”能产生多少种dichotomies？

  从k=2我们可以知道，任意2个数据点都不能被shatter。还记得shatter的概念吗？意思就是我产生的dichotomies不能完全包含任何2个数据点所有的排列组合。让我们从1个dichotomy开始。

1 dichotomy 

2 dichotomies 

3 dichotomies 

  注意看和这两列，这3个dichotomies已经包含和这两个点所有的4种排列组合中的3种了。再多加一种，、就会被shatter。

4 dichotomies 

  看右边两列，和被shatter了。但之前说了k=2，即任意2个点不能被shatter，因此不可能产生这4种dichotomies。那我们换一个dichotomy试试看。

4 dichotomies 

  换了一个dichotomy之后就行了，右边2列只包含了、所有排列组合4种中的3种，因此那两个点没有被shatter。继续检查任意的两个点(、)，(、)，都没有被shatter，看来这4种dichotomies是可以的。

  5个dichotomies的情形这里就不再画出来了，很容易看出不管增加怎样的dichotomy进去，都会有两个点被shatter掉。因此这里“最多最多”只能有4种dichotomies。因此，时的upper bound是4。我们用来表示break point为k的任意的作用于size为N的任意的所能产生的dichotomies的数量的上限（“最多最多”）。则刚刚得出的结论可以表示为，因为任意2个数据点不能被shatter，因此当时，，因此最多最多有。

  美妙的地方马上就要到了，虽然很多时候我们无法直接得到成长函数，但如果我们知道它的break point是多少，我们似乎还是有办法算出这个的上界的。于是乎我们就有了新的目标，不去直接研究，转而去研究。

  前面我们已知了，。不难知道：

• 时，1个点(2种排列组合)都没有办法shatter，因此恒等于1。
• 时，一定能shatter掉个点，因此它产生的dichotomies的种类等于这个点所有的排列组合数。
• 时，从个排列组合中移除掉一个，剩下的都可以作为dichotomies，因此它产生的dichotomies的数量“最多最多”可以是。

  因此我们可以得到下表：

  表格剩余的部分该如何填补？是否与有关呢？
此时某某实验室帮老师抛硬币的研究生要上场了，他穷举了所有可能的dichotomies，发现，以下是他的研究成果：

  我们把这份结果做个排序：

  发现秘密了没有，橙色的部分是成对出现的，只有紫色的部分是单独出现的：

1. 如果拿掉，只看这3个点：
   
   部分可以成为这3个点的dichotomies，因为，所以任3个点不能够被shatter，因此有：：
2. 再来看剩下一个的部分：
   
   注意是之前成对存在的部分，并且部分不可以shatter掉任意2个点，因为如果部分的dichotomies可以shatter掉任意2个点，他每一行都再搭配的两种情况，这样产生的dichotomies就能shatter掉3个点了，和break point为3相违背。所以不能shatter掉任2个点。因此有：

  综合上面两个不等式，我们可以得到：

  这样就能够把前面那张表给填完整：

  用数学归纳法可以证明：

  当时不等式恒成立，因此只要讨论的情形。时，不等式成立，假设时对于所有的不等式都成立，则我们需要证明当时，不等式也成立。根据前面得到的结论，有：