Week06. Theory of Generalization

Course_Lin_MLF 2017.12

1. Restriction of Break Point

• 理清一下概念

  • dichotomy

    二分类而言，指hypothesis $h$对样本数据集$\mathcal{D}$可能的一种划分。

  • growth function $m_{\mathcal{H}}(N)$

    max number of dichotomies。

  • scatter

    $\mathcal{H}$可以在数据集$\mathcal{D}$上产生所有的dichotomies，那么就说$\mathcal{H}$能shatter这个数据集$\mathcal{D}$。
    个人认为可以把scatter理解为划分的意思。

  • break point :

    $K$个数据，可以产生的dichotomies小于$2^K$，将这样的最小的$K$叫做break point.

• The Four Break Points

  • positive rays
    break point at 2
  • positive intervals
    at 3
  • convex sets
    no break point
  • 2-D perceptrons
    (普通情况，不考虑三点共线什么的)
    at 4

• Restriction of Break Point

  对于ppt中例子的理解，关键在于其break point = 2，即对于两个数据点的情况，是不能能存在4种合理的划分的。所以当$N=3,k=2$时，通过画图理解的方式得出此时的growth function最大为4.

2. Bounding Function

• bounding function $B(N, k)$
  maximum possible $m_{\mathcal{H}}(N)$when break point = $k$

  • combinatorial quantity
    maximum number of length-$N$ vectors with $(\circ,\times)$ while 'no shatter' any length-k subvectors

  • irrelevent of the details of $\mathcal{H}$
    e.g. $B(N,3)$ bounds both
    positive intervals
    1-D perceptrons

  • $B(N,k) \le 2^N-1$ while $N > k$

3. Bounding Function: Inductive Cases

• Estimating Part of $B(4, 3)$

  $$\begin{align*} B(4, 3) &= 11=2\alpha + \beta \\ \alpha + \beta &\le B(3, 3) \\ \alpha &\le B(3, 2) \\ \Rightarrow B(4, 3) &\le B(3, 3) + B(3, 2) \end{align*}$$

  general
  

  $$\begin{align*} B(4, 3) &= 11=2\alpha + \beta \\ \alpha + \beta &\le B(N-1, k) \\ \alpha &\le B(N-1, k-1) \\ \Rightarrow B(N, k) &\le B(N-1, k) + B(N-1, k-1) \end{align*}$$

• Bounding Function: The Theroem

  $$\begin{align*} B(N, k) \le \sum\limits_{i=0}^{k-1} \left( \begin{array} N N \\ i \end{array} \right ) \end{align*}$$
  从$N$个中选$i$个。
  这里的小于等于其实可以写为等于。
  • $m_{\mathcal{H}}(N)$ is $poly(N)$ if break point exists
    上限函数有上限。

4. A Pictorial Proof

• BAD Bound for general $\mathcal{H}$

  slides的21面，欲求得的公式的转变。

• Vapnik-Chervonenkis(VC) bound

  • 2-D　perceptron
    break point ? 4
    $m_{\mathcal{H}}(N)$？　$O(N^3)$

  这个推导真的没看懂。。。