[Chapter2] Training versus Testing -(3)

2.1.2 Bounding the Growth Function

 

 Growth function에 대한 가장 중요한 점은, 만약 $m_H(N) = 2^N$조건이 어느 특정 점에서 break된다면(break point), 해당 점(break point)을 기반으로 간단한 polynomial으로 $m_H(N)$을 bound할 수 있다는 것이다. bound가 polynomial이라는 점이 핵심이다. break point가 없다면( 예를 들어 convex hypothesis ), 모든 $N$에 대해 $m_H(N) = 2^N$이다. 만약 $m_H(N)$이 식 (2.1)의 $M$을 대신할 수 있다면, generalization bound는 우리가 얼마나 많은 훈련 예제를 가지고 있던 간에 0으로 수렴하지 않을 것이다.

$E_{out}(g) \leq E_{in}(g) + \sqrt{\frac{1}{2N} ln \frac{2M}{\delta}} \tag{2.1}$

 하지만 만약 $m_H(N)$이 어떠한 형태로든 polynomial로 bound된다면, generalization error는 $N \to \infty$하게 될 경우 0으로 수렴할 것이다. 이는 충분한 예제의 수가 주어진다면 학습한 모델에 대해 일반화(generalization)를 잘 할 수 있음을 의미한다.

 polynomial bound를 증명하기 위해, $H$에 대한 특정 가정이나 조건 없이 break point가 주어졌을 때 maximum number of dichotomies를 측정할 방법을 도입할 것이다. 이 bound는 어떠한 $H$에 대해 적용할 것이다.

Definition 2.4 $B(N, k)$는 N개의 점에 대한 maximum number of dichotomies로 정의된다. 이때 N개의 점에 대한 크기 $k$인 부분집합은 또 다른 dichotomies로 나눠질 수 없다.

 $B(N, k)$의 정의는 break point $k$가 있을 때, 다른 어떤 제약조건을 두지 않고 N개의 점에 대해 most dichotomies를 찾겠다는 의미이다. $B(N, k)$가 maximum으로 정의되었기 때문에, break point $k$를 가진 $m_H(N)$는 upper bound가 있을 것이다.

$m_H(N) \leq B(N, k)$ if k is a break point for $H$

 

$B(N, k)$는 'Binomial'이라는 의미이고, 이유는 다음과 같다. $B(N, k)$를 구하기 위해, 먼저 $k=1$, $N=1$인 경우부터 시작하자.

$B(N, 1) = 1,$

$B(1, k) = 2$  for  $k > 1$