목차
3. 선형 분류기 학습 방법 perceptron learning algorithm (PLA)
4. 학습의 가능성 Feasibility of Learning
5. 확률적 학습의 가능성 Feasibility of Learning
8. 일반화 이론 (Theory of Generalization)
기계 학습은 가지고 있는 데이터로 부터 우리에게 유용한 정보를 뽑아낸 후에 새로운 데이터에 적용하는 의미한다. 기계란 말이 들어가긴 하지만 사실 기계와는 큰 상관이 없는 학문이라고 할 수 있다. 개인적으로는 통계학과 확률의 공대스러운 해석이라고 생각된다. 뒤에서 다루겠지만 (혹은 다룰 수도 있지만) 기계 학습을 바라보는 두 개의 시각은 Frequentist와 Bayesian이다. 이들은 각각 통계학과 확률에 기반을 두고 있는 시각이다. 기계 학습에선 이 두 시각을 모두 사용한다. (물론 이 둘을 합치려는 노력도 있었고, 예전 포스팅에 나오는 PAC-Bayesian이 그 중 하나이다.)
기계 학습은 다음 네 가지의 분류로 나눌 수 있을 것 같다.
1. Supervised Learning
: 상황과 해당 결과가 나온다는 것이 주어진다.
: Active Learning과 Online Learning 도 여기에 포함된다.
2. Unsupervised Learning
: 데이터만 잔뜩 주어진다. 즉 문제는 있는데 답은 없다. 우리가 할 수 있는건, 문제 유형 정도 구분할 수 있겠다. 이를 clustering이라고 한다.
3. Reinforcement Learning
: 상황과 좋음의 정도 (grade)가 주어진다. RL에선 이를 reward라고 표현을 하고, 위의 active learning과도 겹치는거 같은데..
4. 그 외?
일단 간단한 예제를 통해서 우리가 다루고자 하는 문제가 어떤 것인지 살펴보자.
우리가 처한 상황은 다음과 같다. 우리는 은행에서, 그 중에서도 대출 담당 부서에서 일한다고 가정하자. 어떤 고객이 다가와서 돈 1억을 빌려달라고 한다. 우리는 빌려줘야 할 것인가 아닌가?
가장 먼저 든 (혹은 들) 생각은
1. 그 사람의 정보를 알아야지! 예를 들면, 나이, 수입, 직장, 자산, 채무 등등
2. 이전에 다른 사람들은 어떤 결정을 내렸을까? 혹은 어떤 사람들이 돈을 안 갚을까?
일 것이다.
위의 상황을 수식적으로 나타내면 다음과 같을 것이다.
우리에게 주어진 것은 해당 고객의 정보이다. 이를
$$x\in X: x =(x_1, x_2, ..., x_d)$$
라고 하자. 즉 '$d$'개의 정보가 있을 것이다. (성별, 나이, 직장, 외모? 등등)
그리고 우리의 결정은 빌려줄지 말지 이므로 다음과 같다.
$$y \in Y: y = (-1, +1)$$
'$+1$'이면 빌려주기 '$-1$'이면 빌려주지 말기 쯤 되겠다.
우리의 결정은 '$x \in X$'가 들어왔을 때 '$y \in Y$' 가 나오는 일종의 함수이다. 즉 다음과 같다.
$$f: X \to Y$$
우리가 갖고 있는 데이터는 어떤 사람과 해당 정보가 있을 때 돈을 잘 갚았는지 안 갚았는지 여부이다. 이를 수식으로 써보면 다음과 같을 것이다.
$$D_N = \{ (x, y)_i | i = 1, 2, ..., N \}$$
즉 이전 '$N$'명의 정보를 알고 있는 것이다.
그렇다면 우리의 목적은 주어진 '$D_N$'을 통해 '$f: X \to Y$'를 찾는 것이다. 과연 어떻게 찾을 수 있을까?
.... 어렵다.
그럼 이렇게 생각을 해보자. 어떤 함수가 담긴 통이 있다고 생각을 해보자. 세상의 온갖 종류의 함수가 다 담겨있는 것이다. 그리고 이 통에서 하나의 함수를 뽑아서 가지고 있는 '$D_N$'을 이용해서 검증해보는 것이다. 그리고 가장 성능이 좋은 함수를 우리의 '$f$'로 쓰겠다.
여기서 한 가지 의문점이 생겨야 하는데, 만약 해당 함수의 통에 적합한 함수가 없으면 어떡하냐는 것이다.
그럼 망하는거다. 세상 사 다 그런 것 아니겠는가..
모 여튼 이러한 상황에서 함수가 담겨 있는 통을 Hypothesis라 한다. 한국말론 가설이라고 한다.
다시 우리의 본업인 은행으로 돌아가보자. 과장이 와선 빨리 내일까지 해당 고객의 대출 여부를 결정하라고 보챈다. 자 그럼 우리는 세상 모든 함수가 담긴 Hypothesis를 다 확인할 수 없을 것이다. 그럼 가장 간단한 함수가 무엇인가
상수 함수! 가 물론 맞지만 이는 출력 값, 즉 우리의 대출 여부가 고객의 정보와 무관하게 결정되므로 쓸 수 없다.
선형 함수! 그렇다. 그게 출제자의 의도를 파악한 답이다.
위의 그림과 같이 정보가 주어졌다고 하자. '$x_1$'은 나이이고, '$x_2$'는 봉급이다. 이 때 각 사람의 정보에 따른 과거 대출 여부 (혹은 대출 상환 여부)에 대한 정보를 보기 쉽게 그림으로 그려보면 오른쪽과 같다. 여기서 알 수 있는 것은 나이에는 큰 상관이 없고, 돈을 많이 벌면 대출을 잘 시켜준 것을 알 수 있다. 그러면 이 정보를 가지고 적절한 선형 함수를 찾아보자. 이를 '$g(x_1, x_2)$'라 하고, 대충 오른쪽 그림의 빨간 선과 같이 구할 수 있다.
저 선을 이용한 선택(분류)를 수식적으로 나타내면 다음과 같다.
$$y = sign(\sum_{i = 1}^{d} w_ix_i + b) $$
즉 선형 함수의 계수가 '$w_i$'와 '$b$' 이다.
여기까지 본 예제가 기계 학습의 가장 기초적이면서도 아직까지도 많이 연구되는 주제이다. 이러한 선형 분류기를 어려운 말로 perceptron이라고 한다. 몬가 트랜스포머에 나와야 할 것 같지만 그 기원은 인간의 뇌에 있는 신경 세포의 동작에서 온 것으로 한다.
3. 선형 분류기 학습 방법 perceptron learning algorithm (PLA)
선형 분류기 학습 방법, 줄여서 PLA는 다음의 간단한 반복을 통해서 수행된다.
$$ \forall~(x_n, y_n)~x_n~s.t.~sign(w^Tx_n) \ne y_n \\ w \leftarrow w + y_nx_n$$
너무 간단하다. 그 의미를 살펴보면 다음과 같다.
잘못 분류된 데이터에 대해서 해당 데이터를 제대로 분류할 수 있도록 선형 분류기의 방향을 틀어주는 것이다. 선형 분류기는 들어온 데이터와 분류기의 방향을 내적한 뒤에 부호를 본다. 즉 선형 분류기의 방향이 '$-1$'에 해당하는 데이터에서 '$+1$'에 해당하는 데이터 쪽으로 향하고 있으면 옳게 분류가 될 것이다.
위의 그림은 '$+1$'과 '$-1$'에 해당하는 데이터가 각각 잘못 분류되었을 때 위의 PLA를 통해서 분류기의 방향이 어떻게 보정되는지를 보여준다.즉 분류기의 방향에 '$y_nx_n$'을 더해주게 되면 해당 데이터을 옳게 분류하는 쪽으로 분류기의 방향을 틀어주는 효과가 있다. 이 PLA는 완벽하게 분류된 데이터에 대해서는 항상 동작을 잘 한다는 것이 증명되어있다.
4. 학습의 가능성 Feasibility of Learning
여기서 다룰 내용은 일반적인 기계학습 수업에서 다뤄져왔던 내용과는 조금 다른다. 무슨 말인고 하니, 기존의 많은 내용들은 recipe를 집중적으로 다뤘다. 예를 들면, SVM, Topic models, ANN 등등. 하지만 이러한 알고리즘들이 왜 잘 동작하는지에 대한 것은 의문으로 남아있었다. 그리고 이제 그 내용들을 하나하나 다뤄보자.
먼저 다음의 그림을 보자.
9개의 binary한 값으로 이뤄진 데이터가 있고, 해당 출력값이 있다고 할 때 맨 밑의 출력값 '$f$'는 무엇일까? 여러가지 조건이 나올 수 있겠다. 대칭성으로 말한다면 +1일테고, 맨 왼쪽 위에 해당하는 값을 이용한다면 -1이 될 것이다. 여기서 말하는 것은 어떤 데이터와 label 이 주어졌을 때 해당 데이터 이면에 있는 target function '$f:X\ to Y$'에 대해서는 우리가 정확히 알 수 없다 이다.
그리고 이것이 사실이라면 요즘 수많은 사람이 관심을 갖는 기계학습이란 분야는 단순히 요행을 바라는 학문일 것이다. 먼저 그렇게 해석 될 수도 있는 (?) 결과를 살펴보자.
먼저 우리의 입력이 세 개의 binary라 가정하자. 그렇다면 각 input의 경우의 수는 '$2^3 = 8$'이다. 그리고 이러한 상황에서 binary output을 갖는 함수의 경우의 수는 '$2^8 = 256$'이다. 쉽게 생각해서 함수는 입력과 출력을 연결해주는 표 같은 건데, 입력이 가질 수 있는 경우의 수가 8가지이고, 각각 '$-1$' 또는 '$+1$'을 가질 수 있으므로 '$2^8$'이 된다.
모 여튼 이런 상황에서 다음과 같은 데이터가 주어졌다고 하자. 여기서 '$x$'는 입력 데이터, '$y$'는 출력 데이터이다. 위에서 부터 5개 (파란색)의 데이터가 학습을 위해 주어진 데이터라 가정하자. 즉 우리에게 5개의 데이터가 주어졌고, 목적은 우리가 못 본 밑에 세 개의 데이터에 대한 출력값을 예측하는 것이 되겠다.
여기서 '$f_1, f_2, ..., f_8$'은 가능한 목적함수의 경우의 수가 된다. 즉 이러한 원래 함수들로부터 우리의 학습 데이터가 주어졌다고 가정하는 것이다. 학습의 목적은 '$f$'와 최대한 비슷한 '$g$'를 찾는 것이다.
자! 그렇다면 다음과 같이 '$g_1, g_2, g_3, g_4$'가 주어졌다고 하자.
그러면 해당 '$g$'를 통해 얻어진 한번도 본 적 없는 데이터에 대한 출력값은 오른쪽 아래 빨간색과 같다. 오른쪽 위에가 비어있는데, 해보면 학습 데이터를 모두 만족하는 것을 알 수 있다.
하지만 과연 이 함수들이 한번도 본 적이 없는 밑에 세 개의 데이터를 옳게 예측할 수 있을까?
문제가 무엇인고 하니, 어떤 출력값을 예측하던지 간에 우리의 목적 함수 '$f$'는 모든 가능한 경우의 수를 다 포함하고 있기 때문에 항상 문제가 생긴다. (우리가 결정한 함수 '$g$'는 본적이 없는 데이터에서 하나의 값 밖에 가질 수 없다.)
그렇다면 기계 학습은 더 이상 믿을 수 없는 것인가? 그렇지 않다.
5. 확률적 학습의 가능성 Feasibility of Learning
앞과 다르게 확률적 학습의 가능성이다. 즉 한번도 본적이 없는 데이터에 얼마나 잘 동작할지에 대한 것을 확률적으로 나타나겠다는 것이다. 그리고 이를 위한 간단한 (혹은 매우 중요한) 가정이 필요한데, 그것은 다음과 같다.
한 번도 본 적이 없는 데이터와 학습 데이터는 같은 분포에서 얻어졌다.
위의 가정은 통계의 시작이라고도 할 수 있다. 즉 우리가 통계적으로 얻은 데이터와 새롭게 얻을 데이터는 우리가 모르는 어떤 같은 분포를 통해서 얻었다고 가정하는 것이다. 만약 이 가정조차 지켜지지 않는다면, 위에서 살펴본 우울한 경우가 생길 것이고 그 어떤 결과도 믿을 수 없을 것이다.
다음과 같은 예시를 통해서 이에 대해서 알아보자.
다음과 같은 통 속에 초록색과 붉은색 공이 무한히 많이 들어있다고 가정하자. 그리고 붉은 색 공을 뽑을 확률을 '$\mu$'라 하고, 자연스럽게 초록색 공을 뽑을 확률은 '$1-\mu$'가 될 것이다.
이 통에서 '$N$' 개의 공을 뽑아냈다고 가정하자. 이렇게 뽑아낸 공에서 붉은색 공의 빈도를 '$\hat{\mu}$'라고 하겠다. 그렇다면 여기서 '$\hat{\mu}$'과 '$\mu$'의 관계는 어떠할까?
그냥 직관적으로 생각해보면 우리가 '$N$'을 키우면, 즉 공을 많이 뽑아내면, '$\hat{\mu}$'과 '$\mu$'이 비슷해질 것이다. 그 이면에는 같은 통에서 공을 뽑아냈기 때문이다. 여기서 통 = 분포이다.
그렇다면 얼마나 비슷해질까? 이를 알려주는 것이 Hoeffding inequality이다.
for any sample size '$N$' and '$\epsilon > 0$'
'$Pr(|\hat{\mu} - \mu|>\epsilon) \le 2e^{-2\epsilon^2N}$'
몬가 복잡해보이긴 하지만 말하고 있는건 상당히 간단하다. 실제 '$\mu$'와 우리가 실험을 통해 얻은 '$\hat{\mu}$'에 대한 bound를 확률적으로 하고 있다. 극단적인 경우로 가서 '$\epsilon$', 실제와 실험의 차이, 이 '$0$'이라면 확률이 2보다 작아진다는 괴이한 결과가 나온다. 즉 그렇게는 bound할 수 없다는 것이다.
이를 해석하는 영어 말은 Probably Approximately Correct (PAC)로 최근에 올렸던 PAC-Bayes에 나오는PAC이다. (링크1 / 링크2)
위의 식에서 과연 random variable은 무엇일까?
'$\mu$'는 실제 붉은 공의 확률이므로 정해진 값이다. (다만 우리가 모를 뿐) '$\epsilon$'은 empirical error, '$N$'은 data의 수로 역시나 deterministic variable이다. 여기선 '$\hat{\mu}$'가 random variable이다. 우리가 probabilistic distribution에서 sample을 통해 얻은 결과이기 때문이다.
그럼 이 실험이 학습의 가능성과 어떻게 연결될까? 즉 우리가 뽑은 공의 색이 현재 가지고 있는 분류기를 통해 얻은 결과 (Right / Wrong)을 의미한다고 볼 수 있다. 그리 이 경우 '$\hat{\mu}$'는 어떤 분류기를 통해 얻은 학습 에러 (Training error)가 될 것이고, '$\mu$'는 실제 이 분류기가 얼마나 잘 동작할지를 나타낼 것이다.
하지만 한 가지 문제가 있다. 우리가 현재까지는 통이 하나로 가정했다. 무슨 말인고 하니, 데이터와 무관한 통이 하나 있는 것이다. 하지만 실제 우리의 학습 과정을 살펴보면, 어떤 데이터를 갖고 최적의 분류기를 학습시킨다. 이는 위에서 묘사된 통 실험과는 다르다. 통 실험은 학습된 분류기가 아닌 어떤 하나의 고정된 분류기에 대한 결과를 나타낸다.
하나의 통은 하나의 분류기를 나타낸다.
최적의 분류기라는 것은 주어진 분류기들이 여러개 있을 때 같은 실험을 하는 것과 같이 생각될 수 있다. 즉 우리 분류기가 가질 수 있는 경우의 수가 '$M$'이라면, '$M$'개의 통에서 위와 같은 통 실험을 했다고 생각될 수 있다.
간단하게 생각하면 하나의 통와 여러 개의 통이 모가 다르냐고 할 수 있겠지만, 실상을 그렇지 않다. 다음의 예를 생각해보자.
실험1. 동전을 10번 던진다고 하자. 이 때 모두 앞이 나올 확률을 얼마인가?
실험2. 위에서 한 실험을 1000번 한다고 하자. 이 때 모두 앞이 나온 실험이 한번이라도 존재할 확률은 얼마인가?
실험 1과 실험 2는 언뜻 보기엔 비슷해보이지만 실상 매우 다르다. 결과부터 보면
실험1의 경우 '$\frac{1}{2^{10}} \simeq 0.1\%$'이고, 실험2의 경우 '$1 - (\frac{2^{10}-1}{2^{10}}) \simeq 63\%$'로 매우 큰 차이가 난다.
이를 어떻게 해석할 수 있을까? 실험2는 기본적으로 실험1과 같은 것을 하고 있지만, 실험2는 1000번 시도 중에서 가장 좋은 값을 의미한다. 즉 위에서 1000개의 통 중에서 제일 잘 나오는 것을 고른 것을 의미하고, 여기서 알 수 있는 것은 우리가 수많은 통 중에서 제일 좋은 결과가 나오는 것을 고르는 것은 하나의 통에서 나오는 값과는 많은 차이가 있다는 것이다.
이럿듯 수많은 Hypothesis를 고려한 Hoeffding bound는 union bound를 사용해야 한다.
for any sample size '$N$', '$\epsilon > 0$', and number of hypothesis '$M$'
'$Pr(|\hat{\mu} - \mu| > \epsilon) \le 2Me^{-2\epsilon^2N}$'
문제는 '$M$'이 매우 클 수 있다는 것이다. 사실 대부분의 경우 무한히 많다. 예들 들어 이차원 공간 속에 있는 선형 함수의 수는 당연히 무한하다. 이 경우 '$M$'이 무한대로 가고 이 bound는 더이상 쓸모가 없다!
먼저 에러에 대해서 생각해보자. 우리는 지금까지 막연하게 어떤 목적함수 '$f$'가 있고, 학습 데이터를 통해서 이와 유사한, 혹은 에러를 최소로하는, 함수 '$h$'를 생성해 내는 것을 목표로 했었다. 하지만 여기서 에러는 어떻게 정의될 수 있을까?
먼저 학습에 대한 에러에 대해 가장 쉽게 생각할 수 있는건 다음과 같을 것이다.
$$E_{in}(h) = \frac{1}{N}\sum_{n=1}^{N}e(h(x_n), f(x_n))$$
즉 모든 학습 데이터에 대해서 각각 출력을 비교해서 평균 오류를 계산하는 것이다. 그리고 사실 이걸 대부분 사용한다.
그렇다면 우리의 실제 목적함수와 학습된 함수 사이의 에러는 어떻게 계산할 수 있을까?
$$E_{out} = E_X[e(h(x), f(x))]$$
모든 가능한 '$x$'에 대해서 에러의 평균으로 정의가 된다. 물론 이 값은 계산할 수 없을 것이다. 우리는 모든 가능한 '$x$'에 대해 계산하기 힘들테니까 말이다.
에러는 다음 두 가지 종류가 있다: false accept.와 false reject이다. 앞서 살펴본 은행원으로 다시 돌아가보면 우리가 내릴 수 있는 결론은 대출 허가 혹은 불허일 것이다. 이 사람을 대출을 해줘야 하는데 안해준 경우를 false reject이라 하고, 대출을 안해줘야 하는데 해준 경우를 false accept라 한다.
이 두 가지 에러에 대해서 각각 다른 페널티를 줄 수 있는데 이런 경우가 왜 생기는지 살펴보자.
먼저 마트에서 지문을 이용해서 멤버쉽 확인을 한다고 생각해보자.
이 경우에 false accept은 그렇게 큰 문제가 되지 않을 것이다. 그리고 굳이 경중을 비교하자면 false reject에 대한 페널티가 더 클 것이다. 즉 내가 고객인데, 내 지문을 갖다 댔더니 인증을 못하는 것이다. 그러면 귀찮다! 짜증난다! 마트를 안온다! 마트가 망한다!
모 이렇게 될 수 있기 때문이다.
위와 같이 페널티를 주면 될 것이다.
만약 국정원에서 (본 포스팅은 정치적 의견을 담고 있지 않습니다.) 지문 확인을 한다고 하자. 이 경우는 false accept에 엄청난 페널티를 줘야 할 것이다. 예를 들면 남파 간첩이 국정원에 들어가려고 하는데 열어주면 안될것 아닌가.
다시 한번 말하지만 이 에러는 우리의 '$h$'를 찾는데 사용되기 때문에 매우 중요하다.
잡음 (혹은 노이즈)에 대해서 생각해보자. 우리가 얻는 데이터는 일반적으로 노이즈가 들어간 데이터이다. 그렇기 때문에 이 노이즈를 고려해서 문제를 풀 필요가 있다. 여기서 중요한 것은 노이즈의 모델이다. 일반적으로 노이즈를 가우시안 분포라 가정하고 문제를 푼다.
교수님께서는 노이즈가 우리의 친구라고 하신다. 즉 세상에 노이즈가 없다면, 수 많은 박사들이 필요 없을 것이란 것이다. 일리가 있는 말이고, 한번 더 생각해보면 노이즈 모델링이 얼마나 중요한 분야인가를 알 수 있게 한다. 최근 연구되는 수 많은 연구 주제들은 서로 다른 노이즈 모델 (가우시안, 라플라시안 등)을 사용해서 같은 문제를 푸는 경우가 많다.
수식을 조금 사용해서 써보면
1. 우리는 지금까지 '$y = f(x)$'에서 학습 데이터가 나왔다고 생각했다.
2. 하지만 이제 노이즈를 추가하기 위해서 '$y~P(y|x)$'라는 확률을 도입한다.
3. '$p(x, y) = p(y|x)p(x)$' 이다.
4. '$p(x)$'는 입력 데이터의 prior distribution이고, 각 데이터의 중요도라고 해석될 수 있다.
8. 일반화 이론 (Theory of Generalization)
매우 중요한 주제이다. 본격적으로 들어가기 전에 Generalization이 무엇인지 짚고 넘어가자. Generalization은 in-sample error와 out-sample error의 차이를 의미한다. 즉 내가 가지고 있는 학습 데이터에 동작하는 성능과, 새롭게 들어올 (한 번도 본 적 없는) 데이터에 동작할 성능의 차이를 나타낸다. 앞서 Hoeffding bound에 나오는 '$|E_{IN} - E_{out}|$'에 해당한다.
앞서 확률적 학습의 가능성에선 union bound를 이용해서 Hypothesis의 공간 속 '$M$'개의 함수가 있을 때 이에 대한 bound를 나타냈었다.
for any sample size '$N$', '$\epsilon > 0$', and number of hypothesis '$M$'
'$Pr(|\hat{\mu} - \mu| > \epsilon) \le 2Me^{-2\epsilon^2N}$'
하지만 '$M$'이 무한대로 가면 이 식은 아무런 의미를 갖지 못한다.
그리고 이를 해결하기 위한 개념들에 대해서 이제 살펴볼 것이다. 다음의 개념에 대해서 안다면 하산해도 좋다. (물론 난 아직 때가 아닌 것 같다...)
1. Shattering / Dichotomy
2. Growth function '$m_H(N)$'
3. Vapnik-Chervonenkis (VC) dimension
4. VC generalization bound
위의 union bound는 각 '$M$'개의 개별 bound들이 독립적이라고 가정을 하고 worst-case에 대한 bound를 준다. 즉 '$M$'개의 확률적 bound가 서로 겹치는 부분이 없어야 한다. 우리의 세팅인 각 hypothesis는 사실 비슷한 결과를 내곤한다. 예를 들어서 선형 분류기에서 기울기를 1%바꾼다 해서 그렇게 큰 결과의 차이는 없을 것이지만, 0~1% 바꾸는 사이에 무한한 숫자의 분류기가 존재한다.
조금 더 확률적으로 생각해보면 확률이란 Sample space에서 해당 sample이 차지하는 면적을 의미한다. 무수히 많은 sample들이 있지만 각 sample이 차지하는 면적은 크지 않은 것이다. 우리의 관심은 '$|E_{in}(h_m)-E_{out}(h_m)|>\epsilon$'인데, 이러한 event에 속하는 sample space의 hypothesis들은 밑의 그림과 같이 엄청나게 겹치는 것이다.
즉 union bound가 loose한 결과를 준다는 것을 직관적으로 깨닫고, 이를 대체할 수 있는 새로운 bound를 제안하게 된다. 큰 틀은 Hoeffding bound를 벗어나지 않고, 다면 '$M$'을 어떤 다른 finite한 수로 바꾸는 것을 목적으로 한다.
먼저 Dichotomy에 대해서 알아보자. 영어 사전엔 양분, 이분이란 단어로 나온다. 이는 주어진 데이터를 '$\{ -1, +1 \}$'로 분류하는 것을 의미한다. '$N$' 개의 데이터와 함수의 모음 (Set of hypothesis '$H$')가 주어졌다고 하자. 이 때 주어진 '$H$'를 이용해서 분류한다고 할 때, '$H$'가 세상 모든 함수의 모음이라면 가능한 Dichotomy의 수는 '$2^N$'일 것이다. 이렇게 나누는 것을 shatter라고 한다. 그리고 이러한 경우라면 VC dimension을 정의할 수 없다. 여기서 주의할 점은 Dichotomy의 수는 주어진 데이터의 수 '$N$'의 함수이다.
이제부터는 예를 들어서 설명해보자. 만약 우리에게 주어진 함수의 모음이 선형 함수이고 입력은 이 차원 데이터라고 하자. 위에서 말했듯 #Dichotomy는 '$N$'의 함수이기 때문에 '$N=3$'의 경우를 생각해보자.
다음과 같이 세 점이 있다고 할 때, 선형 함수를 통해서 만들 수 있는 #Dichotomy는 8개이고, 다음과 같다. 즉 선형 함수는 2차원 공간에서 세 점을 완벽하게 나눌 수 있다.
만약 '$N = 4$'의 경우를 생각해보자. 이 경우 모든 가능한 경우의 수는 아래 그림과 같이 '$2^4 = 16$' 이다. 그런데 아래 그림에서 7번째와 10번째의 경우는 선형 함수로는 분류할 수 없다. 그리고 이렇게 분류 할 수 없는 데이터의 수를 break point라 한다.
즉 이 경우 #Dichotomy는 '$14 < 2^{4}=16$'이고, 이 차원 공간 속에 선형 분류기는 '$4$'개의 점을 분류할 수 없다. 만약 점이 더 많아진다면 어떨까? 우리는 직관적으로 '$2^N$'보다는 훨씬 더 적어질 것을 예상할 수 있다. 그리고 이 값이 union bound에서 '$M$'을 대체할 할 어떤 값이 될 것이다.
앞서 말한 Hoeffding bound의 변수들을 바꿔서 다시 써보자.
for any sample size '$N$', '$\epsilon > 0$', and number of hypothesis '$M$'
'$E_{out}(g) \le E_{in}(g) + \sqrt{\frac{1}{2N}ln\frac{2M}{\delta}}$'
with probability '$\ge 1-\delta$'
위의 식에서 generalization bound는 '$\sqrt{\frac{1}{2N}ln\frac{2M}{\sigma}}$'이고, '$M$'이 커지면 bound가 커지고, '$N$'이 커지면 bound가 내려간다. 학습 데이터가 많으면 잘 학습될 것이라는 것은 우리의 직관과 맞는 것을 알 수 있다.
자 그렇다면 growth function '$m_H(N)$'에 대해서 알아보자. 결과적으로 이 값이 '$M$'을 대체할 것이다.
앞에서 설명한 break point '$k$'가 존재한다면, VC dimension은 '$d_{VC} = k-1$'이고, '$m_H(N)$'은 '$N^{d_{VC}}+1$'의 upper bound를 갖는다.
$$m_H(N) < N^{d_{VC}}+1$$
이를 이용해서 VC generalization bound를 다시 써보면 다음과 같다.
for any tolerance '$\delta > 0$'
'$E_{out}(g) \le E_{in}(g) + \sqrt{\frac{8}{N}ln\frac{4m_H(2N)}{\delta}}$'
with probability '$\ge 1-\delta$'
'$2M$'이 바로 '$2m_H(N)$'로 변경된 것이 아니라 '$4m_H(2N)$'로 변경되고, '$\frac{1}{2N}$'이 '$\frac{8}{N}$'으로 변경된다.
몇 가지 예를 들어서 VC dimension에 대해서 알아보자.
Example 1: positive rays
이 경우에 '$m_H(N) = N+1$'이다. ('$d_{VC} = 1$')
Example 2: positive intervals
이 경우에 '$m_H(N) = {{n}\choose{2}}+1 = \frac{1}{2}N^2+\frac{1}{2}N+1$'이다. 즉 '$N$' 개의 점이 있을 때, '$N+1$' 개의 공간이 생기고, 이 중에서 2개의 점을 고르는 경우의 수 + 모두 -1로 할당하는 경우의 수 하나를 더한다. ('$d_{VC} = 2$')
Example 3: convex sets
convex set의 경우는 '$m_H(N) = 2^N$'이다. 이렇게 되는 이유는 모든 데이터를 원 위에 올려놓을 경우, 어떤 configuration여도 convex set으로 나뉠 수 있다.
Example 4: perceptron in '$d$'-dimension
'$d_{VC} = d+1$' 이다.
VC dimension의 formal definition은 maximum non-break point이다. 그래서 '$d_{VC}$'는 '$m_H(N)$'의 polynomial을 bound한다.
여기까지만 보면 VC dimension으로 많은 것이 해결될 것 같지만, 사실 큰 단점을 갖고 있다. 그것은 바로 이를 이용한 generalization bound가 너무 loose하다는데 있다. 다시 말해서 VC dimension은 모든 가능한 Hypothesis에 대해서 동작을 하기 때문에 어떤 알고리즘으로 학습을 하던지 간에 같은 bound를 준다. 다시 말해서 tight한 bound를 주기엔 너무 범용적으로 쓰일 수 있는 것이다.
예를 들어 앞서 설명한 PLA를 통해서 얻은 bound나 우리가 익히 들어서 아는 linear SVM으로 얻은 결과나 같은 bound를 줄 수 밖에 없다. 왜냐하면 둘 모두 선형 모델을 사용하고 있기 때문이다.
Test-set based approach 역시 이러한 generalization bound 관점에서 해석될 수 있다. generalization은 '$E_{in}$'과 '$E_{out}$'의 차이를 나타낸다. 이는 기본적으로 Hoeffding bound를 통해서 구해지는데, 문제가 #hypothesis가 커지면 union bound때문에 bound가 loose해진다는 것이다. 그래서 '$M$'을 대체할 growth function '$m_H(N)$'가 도입되었다. 즉 애초에 '$M$'이 커지는게 문제였다.
그렇다면 '$E_{test}$'는 어떨까? 이 값을 '$E_{out}$'의 proxy로 사용한다면, 과연 이 둘의 차이는 얼마나 날 것인가? 여기서 중요한 사실은 '$E_{test}$'를 구하는 과정에서 우리에겐 hypothesis가 단 하나 (학습된) 라는 것이다. 우리의 학습은 training data를 이용하지 test data를 이용하지 않는다. 그래서 우리는 다음과 같은 관계를 얻을 수 있다.
for any sample size '$N$' (number of test data), and '$\epsilon > 0$'
'$E_{out}(g) \le E_{test}(g) + \sqrt{\frac{1}{2N}ln\frac{2}{\delta}}$'
with probability '$\ge 1-\delta$'
즉 '$E_{test}$'과 '$E_{out}$' 사이의 차이는 '$E_{in}$'과 '$E_{out}$' 사이의 차이보다 훨씬 적다. ('$M=1$'이므로 '$d_{VC}$'가 필요 없다.)
'Enginius > Machine Learning' 카테고리의 다른 글
| Machine Learning (Regularization) (2) | 2014.05.06 |
|---|---|
| Machine Learning (Linear Models, Logistic Regression, GD, SGD) (0) | 2014.05.05 |
| Gaussian Process Latent Variable Model (GPLVM) (0) | 2014.04.25 |
| Infinite Mixture of Gaussian process experts + Hybrid MCMC (0) | 2014.04.20 |
| PAC-Bayes bound 발표자료 (0) | 2014.04.19 |
