오늘은 좀 재미없는, 혹은 매우 흥미로운 연구들에 대한 글을 써보려한다. 제목은 PAC Bayes analysis이다.
PAC는 팩맨을 연상시키지만, 다음 매우 이상한 단어들의 약자이다.
Probabilistic Approximately Correct (PAC)
이게 도대체 무슨 말인가? 이는 사실 Probabilistic + Approximately Correct의 합쳐진 말이다.
이를 제대로 이해하기 위해선 우리가 지금 다루고 있는 문제에 대해서 조금 알아야 한다. 현재 우리가 다루는 문제는 다음과 같다.
나한테 어떤 labeling된 데이터가 있다고 하자. 예를 들면 자동차만 들어있는 사진과 자동차가 아닌 사진이 있을 때, 이 사진들을 통해서 자동차 분류기를 학습 시켰다고 하자. 이렇게 학습된 분류기가 과연 "새로운", 혹은 "한 번도 본 적이 없는" 자동차가 들어왔을 때 옳게 분류할 수 있을 것일까? 에 대한 문제이다.
우리는 막연히 이렇게 될 것을 가정하고 있다. 만약 세상이 이렇지 않다면 Machine Learning이라는 학문이 생길 수 없었을 것이다. 하지만 이를 수학적으로 나타내야만 할 것이다.
이러한 문제를 다루는 가장 대표적인 방법은 VC dimension일 것이다. VC는 Vapnik–Chervonenkis의 약자로 두 러시안 통계학자들의 이름을 딴 것이다. VC dimension의 또 다른, 혹은 수학적 정의는 maximum non-break point이다. 무슨 의미인가 하면, 우리에게 어떤 분류기의 집합이 주어졌다고 하자. 예를 들면 perceptron과 같이 선형 분류기가 주어졌다고 하자. 입력 데이터의 차원은 2로 가정하자.
이때 2차원 perceptron의 VC dimension은 3이다. 무슨 의민고 하니 오른쪽 그림과 같이 네 점이 배치되었다면 이는 perceptron으로 분류할 수 없기 때문에 (세 점은 무조건 분류 가능) maximum non-break point는 3이 되는 것이다. 이렇게 분류한다는 것을 shatter라고 하고, dichotomy의 수라고도 한다. 즉 몇 개로 나눌 수 있냐는 것이다.
하지만 이 VC dimension 자체만 가지고는 의미가 없고 이는 generalization error라는 개념 속에서 이해되어야 한다.
이 generalization error라는 것이 바로 위에서 말한 한 번도 본 적이 없는 새로운 데이터를 얼마나 잘 분류할 수 있을지에 대한 개념이다. 먼저 중간 결론부터 보고 넘어가자.
$$ P( |E_{IN}(g) - E_{OUT}(g)| > \epsilon ) \le 2Me^{-2\epsilon^2N}$$
위의 식은 유명한 Hoeffding inequality의 약간 변형이라고 볼 수 있다. 위의 식에서 '$E_{IN}$'과 '$E_{OUT}$'은 각각 in-sample error와 out-sample error로 내가 가지고 있는 분류기가 있을 때, 학습에 사용된 데이터에 적용시켰을 때 결과와 새로운 데이터에 적용시켰을 때의 결과 차이의 평균을 "확률적"으로 bound 시키는 것이다.
여기서 N은 데이터의 수이고, M은 union bound에 따른 Hypothesis의 수이다. 문제는 우리의 Hypothesis의 수가 무한대로 간다는데 있다. 그럼 결국 bound가 무의미해진다. 그리고 VC dimension은 M을 대체할 수 있는 finite한 수이다. 결국 generalization error를 bound할 수 있는 값인 것이다. 또한 한 가지 주요한 것은 이 모든것이 확률로 표현된다는 것이다. 즉 '$\epsilon$'이라는 확률이 주어기고, 이 확률만큼은 우리의 generalization error가 틀릴 수 있음을 나타낸다. 하지만 모든지 정의가 가장 중요하듯이 이러한 statement에선 가정이 중요하다. Hoeffding bound의 가정은 다음과 같다.
Training data와 Test data는 모두 같은 분포에서 파생되었고, 모두 Independent and Identically distributed (IID) 관계를 갖는다.
당연해 보일 수도 있는 이 가정은 사실 Frequentist의 가장 기본적인 가정이고, 유일한 가정이기도 하다. 사실 그렇기 때문에 이 bound는 매우 loose하고, 실제로 써먹긴 좀 부족한 감이 있다. 물론 개념적으로 Machine learning이 왜 동작하는지에 대한 설명을 하기엔 이보다 좋은 것이 없는듯하고, 현재까지도 중요하게 언급되는 개념이다.
PAC 얘기 하다가 많이 돌아왔는데 이 PAC 역시 VC Dimension과 비슷한 (혹은 거의 같은) 개념이라고 보면 된다.
Machine Learning에는 크게 두 학파가 있다. 하나는 Frequentist이고, 다른 하나는 Bayesian이다. 이 둘의 큰 차이점 중 하나는 다음 특성이다.
Bayesian은 classifier function에 대한 distribution을 가정하고, Frequentist는 Input space에 대한 distribution을 가정한다.
이러한 관점에서 봤을 때 VC dimension과 PAC analysis는 Frequentist 입장에서 바라본 현상이라고 볼 수 있을 것이다. 하지만 이 posting에서 다루는 PAC Bayes는 그 이름에서도 알 수 있듯이 이 둘을 결합하려는 연구이다.
자 그럼 시작해보자. (?)
Frequentist approach
- 일반적인 결과는 '$1-\delta$'의 확률로 현재 학습된 분류기는 낮는 generalization error를 갖을 것이다. 라는 것이다. 즉 처음의 확률 때문에 (probably) 란 단어가 나왔고, 낮을 generalization error를 갖을 것이다 에서 (approximately correct)가 나와서 PAC란 단어가 처음 등장하게 되었다.
- 여기서 문제는 어떻게 새로운 test data에 잘 동작할지를 보장하는 것인데, 이는 train과 test에 사용된 데이터가 같은 분포를 따른다고 가정하고, 우리가 충분한 수의 training data를 모았을 경우 해당 분포를 충분히 모델할 수 있을 것이라는 가정에서 출발한다. 그리고 '$\delta$'라는 부분이 우리가 운이 없게 별로인 데이터를 가지고 학습을 할 확률을 나타낸다.
Bayesian approach
- Bayes theorem으로부터 유도(?)된 것이다.
- 여기서는 prior distribution over functions or classifier를 가정한다. 이 부분이 Frequentist와 다른 부분이다.
- 그리고 어떤 데이터에 대해서 얼마나 잘 분류하느냐에 따라 classifier의 likelihood를 정의하고, Bayes rule에 따라 posterior distribution을 구할 수 있다. 이는 데이터를 본 이후에 각 classifier에 대한 확률이다. 물론 이는 prior에 biased되어있다.
- 주의할 점은 input에 대한 distribution은 없다는 것이다.
- 우리가 한 가지 할 수 있는 것은 특정 모델이 주어졌을 때 데이터들에 대한 likelihood '$p(data|model)$'이다. 그리고 이를 이용해서 각 model에 대한 evidence '$p(model)$'를 구할 수 있다. 무엇이 모델인가? set of function with prior distributions?
- 이를 version space(: subset of all hypotheses that are consistent with the observed training examples)에서 volume으로 연상할 수 있다.. (?)
위 그림에서 공간은 weight vector들이 살고 있는 공간이고, 각 선은 각 training data를 잘 분류할 수 있는 경계면을 의미한다. 예츨 들어서 weight 들이 가운데 있는 공들 속에만 있으면 모든 training data를 잘 분류할 수 있는 것이 된다. 이 때 이 공간의 넓이 (weight space)를 통해서 evidence의 lower bound를 구할 수 있다.
- Gaussian process 역시 이러한 관점에서 표현될 수 있다. GP prior over function은 '$N(0, K(X, X))$'로 표현된다.
Evidence and generalization
- 이 둘은 Bayesian과 Frequentist를 잘 잇는다.
PAC-Bayes Analysis
- 먼저 우리는 분류기가 살고 있는 공간 C 에 대한 prior P와 posterior Q를 정의한다. Posterior는 데이터 dependent하다.
- 또한 train과 test는 같은 distribution에서 drawn with iid 되었다고 가정한다.
- '$c_D$'는 generalization error이고, '$\hat{c}_S$'는 empirical error이다.
Bayesian Classifier
- 우리가 갖고 있는 bound는 어떤 특정 classifier에 대한 bound가 아니라, 확률적 분류기에 대한 bound이다.
- 확률적 분류기는 어떤 test data가 들어왔을 때 classifier 중에서 posterior가 가장 높은 놈을 뽑아서 해당 분류기를 이용해서 분로를 하는 것을 의미한다. 다른 논문에선 Gibbs classifier라고도 하는 것 같다.
- 이 부분이 Bayesian과는 조금 다른게, Bayesian은 이러한 classifier의 결과의 posterior mean을 취할 것이기 때문이다. 모 사실 MAP이라고 보면 비슷할 수도 있을 거 같은데..?
- 이는 우리가 일반적으로 사용하는 SVM과는 매우 다르다.
- 그래서 우리가 추가적으로 필요한 것은 이러한 확률적 분류기와 일반적인 분류기를 연결하는 것이다!
Definitions for main result Assessing the posterior
- 우리가 관심 있는 것은 다음 두 값이다.
- 1. '$ Q_D = E_{c~Q}[c_D] $'
- 2. '$ \hat{Q}_S = E{c~Q}[\hat{c}_S] $'
- 첫 번째 값은 expected generalization error이고, 두 번째 값은 expected empirical error이다. (given posterior)
- 이 expectation 때문에 Bayesian이 된다.
이 때 posterior average에 대한 bound는 다음과 같이 구할 수 있다.
$$ Pr_{(x, y)}(sgn(E_{c~Q}[c(x)])\ne y) \le 2Q_D $$
즉 이것은 Bayesian이 원하는 classifier의 결과에 대한 posterior mean의 성능에 대한 bound이다. 그리고 이 값은 앞에서 구한 '$Q_D$'에 두 배를 곱한 것과 같다. 왜 두배가 되느냐면 모든 '$x$'에 대해서 '$c~Q$'은 classifier '$c$'의 성능은 최소 0.5일 것이다? 이 부분은 좀 더 생각해 봐야 할 것 같다.
PAC-Bayes Theorem (★★★★★)
이 포스팅의 목적인 PAC-Bayes Theorem은 다음과 같다.
먼저 어떤 임의의 공간 '$D$'가 있고, classifier의 prior '$P$', confidence '$\delta$'가 있을 때,
'$1-\delta$'의 확률로, 데이터 '$S~D^m$', 그리고 classifier의 posterior '$Q$'에 대해서 다음을 만족한다.
$$KL(\hat{Q}_S || Q_D) \le \frac{ KL(Q||P + ln((m+1)/\delta)) }{m}$$
위의 식을 사실 보기에 쉽지는 않다. 하나씩 차근차근 봐보자.
먼저 왼쪽의 '$KL(\hat{Q}_S || Q_D)$' 은 expected empirical error와 expected generalization error의 분포에 대한 KL-divergence이다. KL-divergence는 measure of closeness이고, VC dimension에서 봤던 generalization error에 대응되는 개념이라고 할 수 있을 것이다.
'$ KL(Q||P) = E_{c~Q}[ln \frac{Q(c)}{P(c)}] $' 로 두 분포가 얼마나 비슷한지 나타낸다.
오른쪽항을 보자. 이는 두 항으로 이뤄져 있다. 왼쪽의 '$KL(Q||P)$'는 우리가 처음 가정한 function에 대한 prior와 어떤 데이터에 대한 해당 function에 대한 posterior이다. 오른쪽은 당연한 소리인데, 데이터의 dimension에 비례하고 confidence에 반비례하는 term이다. 직관적으로 설명하자면 curse of dimensionality 와도 이어지는 개념이라고 볼 수 있겠다. 결국 우리가 probabilistic classifier를 사용한다면, 해당 classifier의 prior와 posterior를 최대한 비슷하게 할 필요가 있다는 당연한 소리를 수학적으로 증명한 것이라고 할 수 있을 것이다.
Finite Classes
만약 function space가 finite cardinality를 갖는다고 할 때, '$h_1, h_2, ..., h_N$' with prior distribution '$p_1, p_2, ..., p_N$', 그리고 이 posterior가 single function (즉 어떤 데이터가 들어오면 posterior는 singleton)이라고 하자. 이때 generalization bound는 다음과 같다.
$$KL( \hat{err}(h_i) || err(h_i) ) \le \frac{-log(p_i) + ln((m+1)/\delta)}{m}$$
결국 function의 posterior를 prior와 비슷하게 잡는 것이 중요하다.?
증명 파트... <video 1 50분>
Other applications
- Gaussian process
- PAC-Bayes version of VC dimension
- Structured output learning
- and so on..
Linear classifiers and SVMs
- Focus in on linear function applications
- How the application is made
- Extensions to learning the prior
- Some UCI datasets! - non trivial bound!
PAC-Bayes Bound for SVM
- 56분.. 어렵다 몬소리지?
2. PAC-Bayes Analysis: Background and Applications (Video Lecture 2)
두 번째 video lecture이다. 어렵다.
General perspective
- Try to connect Bayesian and frequentist
- Bayesian: more probabilistic prediction
- Frequentist: only iid
Frequentist approach
- Pioneered in Russia by Vapnik and Chervonenkis
- Introduced in the west by Valiant under the name of 'probably approximately correct (PAC)'
- 결과는 최소 '$1-\delta$'의 확률로 우리가 학습시킨 분류기는 낮은 generalization error를 가질 것이다.
Bayesian approach
- Bayesian은 분류기 (혹은 regressor) 에 대한 prior에 대한 가정을 한다.
- 그리고 Lik를 정의하고, 가지고 있는 학습 데이터에 대해서 posterior를 정한다. (Bayes rule을 이용해서)
- 그리고 에러에 대한 분포 (예를 들면 가우시안)를 가정해서, 이를 종합해서 우리의 분류기를 학습시킨다.
- 그리고 결과를 expected classification under the posterior에 따라서 학습시킨다. (SVM과는 다르다.)
- Gaussian process regression은 이를 통해서 분석될 수 있다.
Version space: evidence
- 가운데 있는 원이 version space로 우리가 갖는 데이터를 모두 옳게 분류할 수 있는 분류기의 공간을 의미한다.
3. Some PAC-Bayesian Theorems (by David Mc Allester)
- 사람들은 machine learning에서 recipes를 배우는 것이다. 예를 들면 SVM, kernel methods 등등이다.
PAC-Bayes bound
- Given prior distribution '$P$' and posterior distribution on '$Q$' on the weight vector (or the classifier),
- Generalization error of the Gibbs sampler '$err(Q)$' is bounded by some bound '$B(Q)$' on '$Q$'.
- 그리고 이 bound는 다음과 같이 정의된다.
$$B(Q) = \hat{err}(Q) + \sqrt{\hat{err}(Q)c(Q)} + c(Q) $$
$$c(Q) = \frac{2(KL(Q, P)+ln\frac{n+1}{\delta})}{n} $$
의미를 좀 살펴보면, 결국 bound '$B(Q)$'는 empirical error를 의미하는 '$\hat{err}(Q)$'와 prior '$P$'와 posterior '$Q$'사이의 거리를 뜻하는 KL divergence로 표현이 된다.
그리고 geometric mean이 arithmetic mean으로 bound가 된다는 성질을 이용하면, '$B(Q)$'는 다음으로 bound된다.
$$B(Q) \le \frac{3}{2}(\hat{err}(Q)+c(Q)) $$
Video Lecture
[1] http://videolectures.net/aop07_shawe_taylor_pba/
[2] http://videolectures.net/mlss09us_shawe-taylor_pacbaba/
[3] http://videolectures.net/pacbayesian_mcallester_spbt/
[4] http://videolectures.net/pacbayesian_laviolette_pbts/
'Enginius > Machine Learning' 카테고리의 다른 글
| PAC-Bayes bound 발표자료 (0) | 2014.04.19 |
|---|---|
| Some properties in Regression using Conditional Independency (0) | 2014.04.16 |
| Sparse Distributed Memory Framework (0) | 2014.04.09 |
| Generative vs. Discriminative model (0) | 2014.03.28 |
| Gaussian process related papers (Songhwai Oh) (0) | 2014.02.27 |
