[Chapter2] Training versus Testing - (2)

2.1.1 Effective Number of Hypotheses

 앞에서는 generalization의 bound에서 hypotheses의 개수 M이 무한으로 많아질 수 있기 때문에, 이를 유한의 값으로 대체할 필요성에 대해 논의했다. 이를 위해 이번에는 growth function을 도입한다. growth function은 hypotheses의 개수를 효율적으로 정형화(formalize)하는데, 다음 2가지를 의미한다.

1) 집합 $H$의 hypotheses가 서로 어느만큼 다른가.

2) 이에 따라 서로 다른 event 사이에 얼마나 많은 overlap이 있는가.

 이제부터 논의할 주제에 대한 전체적인 방향은 다음과 같다. 먼저 growth function을 정의하고 기본적인 성질을 알아본다. 다음으로 growth function의 값을 어떻게 bound할 수 있는지 논의하고, 마지막으로 generalization bound의 $M$을 growth function으로 대체할 수 있음을 보일 것이다. 이렇게 함으로써 무한의(infinite) $H$에 적용할 generalization bound를 찾을 수 있게 된다.  단계를 설명하면서 binary function을 예시로 집중적으로 볼 것이다.( $h \; \in H$ maps to ${-1, 1}$).

 growth function에 대한 정의는 $H$가 나타낼 수 있는 서로 다른 hypotheses의 개수에 근거하지만, input space $\chi$ 전체를 생각하지 않고 유한개의 샘플 데이터만 고려한다. 만약 $h \ in H$를 유한개의 샘플 $x_1, x_2, \dots x_N \in \chi$에만 적용해보면 $\pm1$의 값을 가진 N개의 tuple $h(x_1), \dots, h(x_N)$을 구할 수 있다. 이러한 N-tuple을 dichotomy(뜻 : 이분법; pattern)라고 부르는데, 이는 $x_1, x_2, \dots , x_N$을 두 개의 그릅으로 나누기 때문이다. 각각 $h \in H$마다 샘플 데이터 $x_1, x_2, \dots , x_N$에 대해 dichotomy를 생성하는데, 여기서 중요한 점은 $h$가 달라도 결과로 생성되는 dichotomy는 같을 수 있다는 점이다.

Definition 2.1 샘플 데이터 $x_1, x_2, \dots , x_N \in \chi$가 있을 때, $H$에 의해 생성되는 dichotomies는 다음으로 정의한다.

$H(x_1, x_2, dots, x_N) = \{ \; (h(x_1), \dots, h(x_N)) \; | \; h \in H \}$

 One can think of the dichotomies $H(x_1, \dots, x_N)$ as a set of hypotheses just like $H$ is, except that the hypotheses are seen through the eyes of $N$ points only. 더 큰 $H(x_1, \dots, x_N)$일수록 더 많은, 다양한(diverse) dichotomies를 생성하게 된다. 여기서 growth function은 dichotomies의 개수에 기반한다.

 Definition 2.2 Hypotheses set $H$에 대한 growth function은 다음으로 정의한다.

$m_H(N) = \max_{x_1,  \dots, x_N \in \chi} |H(x_1, \dots, x_N)|$

이 때 $|\cdot|$은 집합의 cardinality( 원소의 개수 )을 의미한다. 다시 말하면 n개의 데이터 포인트로부터 hypotheses를 통해 

$m_H(N)$은 어떠한 $N$개의 데이터를 기반으로 $H$가 생성할 수 있는 maximum number of dichotomies를 의미한다. $m_H(N)$을 계산하기 위해, 우리는 나올 수 있는 가능한 경우의 수(패턴 수)를 최대한 많이 주는 데이터 N개를 고려해야 한다. $m_H(N)$은 집합 $H$에서 전체 데이터 $\chi$가 아닌, 데이터 N개에 대한 hypotheses 수에 대한 measure를 나타낸다. 어떠한 $H$에 대해서라도 $H(x_1, \dots, x_N) \subseteq {-1, +1}^N$이기 때문에, $m_H(N)$은 최대 $|{-1, +1}^N|$이 되고, 따라서 다음과 같이 표현될 수 있다.

$m_H(N) \leq 2^N$

 만약 $H$가 $x_1, \dots, x_N$에 대한 모든 가능한 dichotomies( = patterns)를 생성할 수 있다면, $H(x_1, \dots, x_N) = {-1, +1}^N$이 되고 이를 "H can shatter $x_1, \dots, x_N$"라고 표현한다. 이는 특정 샘플에 대해 $H$의 다양성을 나타낸다.

 Example 2.1 만약 $\chi$가 Euclidean 공간에 있고, $H$는 2차원 perceptron이라 하면, $m_H(3), \; m_H(4)$는 어떤 값을 가지는가? 

위의 그림은 2차원 perceptron에 대한 growth function을 나타낸다.  (a)는 collinear(같은 선상에 있음. 공선)한 3개의 데이터를 나타내며, 이는 perceptron이 생성할 수 없는 데이터이다. 하지만 (b)에서는 perceptron이 각 점의 모든 경우의 수(blue, red인 경우)를 생성할 수 있다. ( 8 dichotomies )반면에 (c)는 4개의 데이터일 때, perceptron이 생성할 수 없는 경우를 나타낸다. 4개의 데이터를 perceptron이 생성할 때는 전체 16 dichotomies 중 최대 14개의 dichotomies를 생성할 수 있다.  따라서 $m_H(3) = 8, \;\; m_H(4) = 14$가 된다.

 Example 2.2 각각의 조건에 따라 $m_H(N)$의 공식을 찾아보자.

1. Positive rays : $H$는 가능한 모든 $h$의 집합을 의미하고, 여기서 보일 $h$의 예제는 다음과 같다. 

$h(x) = sign(x-a), \; h:\mathbb{R}\to{-1, +1}$

hypotheses는 1차원 input space라 가정하고, a를 기준으로 이보다 작으면 -1을 return하고, a보다 크거나 같을 경우 +1을 return한다. $m_H(N)$을 계산하기 위해서 N개의 데이터가 주어졌을 때, N+1개 구역으로 나뉠 수 있다. 구역을 나눌 때 a가 어느 구역이 포함되었는가를 기준으로 dichotomy를 생성할 수 있다. 따라서 N개의 데이터가 주어졌을 경우, 각각의 구역에 a가 포함될 수 있으므로 growth function은 다음과 같이 표현될 수 있다.

$m_H(N) = N+1$

 N개의 데이터 중 중복될 경우에는 $N+1$보다 작은 값이 되지만, $m_H(N)$의 정의는 maximum number of dichotomies이기 때문에 $m_H(N)$에 영향을 주지 못한다.

2. positive intervals : $H$는 1차원상에서 특정 구간에서는 +1을 return하고 나머지 구간에서는 -1을 return하는 hypotheses로 구성되있다고 가정하자.  그림으로 나타내면 아래와 같다.

$m_H(N)$을 계산에 앞서, N개의 점이 주어졌고 선은 $N+1$ 구역으로 나뉠 수 있다는점을 알고 있다. dichotomy는 $N+1$ 구역 중 +1구간의 양 끝 2구역을 택하는 만큼의 경우의 수가 있다. 만약 양 끝 구간이 겹치게 선택되면 어느 구역에 있던 hypotheses가 -1이 되는 상수(constant)가 된다. 이런 경우를 다 합치면 다음과 같이 계산될 수 있다.

$m_H(N) = \binom{N+1}{2} + 1 = \frac{1}{2}N^2 + \frac{1}{2}N + 1$

 $m_H(N)$이 N의 제곱만큼 커지는걸 볼 수 있고, 이는 N이 증가함에 따라 앞서 봤던 positive ray보다 훨씬 빠르게 커짐을 의미한다.

3. convex set : $H$의 hypotheses는 2차원에 있다고 가정한다. ( $h : \mathbb{R}^2 \to {-1 , +1}$) +1은 convex set안에 포함되는 경우, -1은 그 이외의 경우를 의미한다. 

$m_H(N)$을 계산할 때, $N$개의 점을 조심히 선택할 필요가 있다.  원 둘레 위에 있는 $N$개의 포인트를 선택해야 한다. 

점을 선택한 뒤, $\pm1$을 N개의 점에 부여함으로써 임의의 패턴을 만든다. 그런 다음 $+1$부분에 해당되는 점들을 이어주면 다각형을 만들 수 있는데, 이 다각형의 면적이 hypothesis를 구성하는 닫힌 공간이 된다. +1에 해당되는 점이 3개 미만이라면, convex set은 선이 되거나, 점, 혹은 empty set이 된다. 이것은 N개의 점에 대해 어떠한 dichotomy라도 convex hypothesis가 된다는 말이고, 이 때 growth function은 최댓값으로 $2^N$을 가지게 된다.

$m_H(N) = 2^N$

 만약 N개의 점이 원 둘레 위에 있지 않고 평면상에서 random으로 선택된다면, 위의 그림에서 다각형 안에도 점들이 있을 수 있다. 이럴 경우 모든 점들을 convex hypotheses로 분리할 수 없게 되고, 따라서 원 위에 있는 점들로 제약을 두고 $m_H(N)$을 구한 것이다. convex hypotheses로 분리하지 못하는 경우는 생각하지 않아도 되는데, $m_H(N)$의 정의는 maximum possible value이기 때문이다.

 

 Hypothesis마다 $m_H(N)$을 계산할 필요는 없고, 아래의 식에서 $M$을 대체하기 위해 정확한 값보다는 $m_H(N)$의 upper bound를 사용할 것이다.

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

 Definition 2.3 $H$에 의해 분리될 수 있는 크기 $k$의 데이터 집합이 없다면, $k$를 break point for $H$라고 한다.

 만약 $k$가 break point라면, $m_H(k) < 2^k$. 일반적으로 $H$에 대한 break point를 찾는게 growth function을 계산하는것보다 훨씬 쉽다. 이제 break point $k$를 사용해 growth function $m_H(N)$의 모든 $N$의 값에 대해서 bound를 유도할 것이다.