[ML/Lecture] 6. Learning from Examples (Part A)

 

 

< Learning from Examples (Part A) >

 

Supervised learning과 Unsupervised learning에 대해서 이야기해 보도록 하자. 

  가설 h가 있을때 이를 학습시키는데에 있어 input과 output pair가 존재하는 것을 supervised-learning이라고 한다. 결과는 classification(분류)를 하여 어느 분류에 속하는 지를 판단할 수도 있고, regression(회귀)를 통해 연속적인 값을 뽑아내기도 한다.  

  만들어낸 모델이 모든 예제 데이터 셋을 만족하면 모델(가설h)는 consistent하다고 이야기한다. 트레이닝 데이터 뿐 아니라 다른 데이터에도 적용이 잘 되는 경우 generalize가 잘 되었다고 이야기한다. ockham's razor는 심플한 모델을 선호한다는 것이다. 따라서 a,b의 모델중에서 a와 같은 모델을 제일 선호한다는 것이다. 보통은 복잡할수록 consistency가 높아지긴 한다. 용어를 좀더 살펴보면, 모든 데이터에 대해서 consistent하다는 것은 gerneralize가 잘 되었다고 말한다. 

  결국 hypothesis의 확률이 될 확률이 제일 높은 hypothesis를 선택하는 것이 바로 supervised learning이라고 할 수 있다. 따라서 bayes's rule에 의해서 분자부분에 해당하는 p(data|h)p(h)가 가장 큰 값을 선택해야 한다. (p(b)에 해당하는 p(data)는 이미 주어진 값이기 때문) . 복잡한 hypothesis일수록 p(h)는 낮다.

  이러한 기법중에 decision tree라는 것이 있다. 기본적으로 사용해볼 법한 모델이다. 위의 데이터는 각각에 해당하는 조건을 부합하는 경우 어떤 결과가 나오는 지를 나타낸 테이블이다. attribute에 해당하는 값은 음식점에서 기다릴지 그냥 갈지를 결정하는 데에 있어서 조건들을 나타내는 것이고, 이런 조건들일 경우 기다릴 것인지, 아니면 그냥 갈지를 labeling을 해놓은 것이다. 이를 tree형식으로 나타내면 다음과같다.

결국 ockham's razor가 여기서도 적용되어 decision tree model에 있어서도 좀더 compact한 모델을 원하는 것이다. 

  물론 decision tree는 여러개가 존재할 수 있다. 우리는 그중에서 가장 slim하고 compact한 모델을 원하는 것이다.  하지만 문제는 이런 tree를 찾는 과정이 np문제에 해당한다는 것이다. attribute가 많으면 많을수록 문제를 해결하는 것은 더 힘들어진다. 지금 이 슬라이드에 나와있는 설명만 보더라도, 고작 6개의 attribute가 주어졌을 뿐인데 1.8x10^19개의 tree가 만들어지게 된다. 

그러면 이 문제를 어떻게 해결할 수 있을까? 결국 모든 tree를 전부 해보는 것은 힘들고, greedy-approach를 사용하게 된다. 뼈대가 되는 아이디어는 제일 중요하다고 생각되는 node(attribute)를 root로 사용하는 것이다. 그러면 어떤 attribute가 중요하다고 할 수 있을까? 

예시를 살펴보자. patron이라는 속성과 type이라는 속성이 있다. 직관적으로 봐도 patron이 좀 더 중요해 보인다. 왜냐하면 true인지 false인지를 명확하게 나누어 주기 때문에 추가적으로 branch를 만들어서 나눌 필요가 없어지기 때문이다. 

  이런 식으로 어느 한쪽으로 많이 치우치는 결과가 나올수록 더 많은 information을 제공한다고 말하는데, 이때 적용되는 개념이 entropy이다. 따라서 반반으로 나누어지는 경우가 최악의 경우이다. <0.5,0.5>의 케이스에서 entropy를 위의 식에 따라 계산하면 -0.5x-1은 0.5이므로 p1,p2가 각각 0.5로 합 1이 된다. 이 1이 type의 경우 4개가 있으므로 총 entropysms 4이다. 하지만 <1,0>혹은 <0,1>과 같은 patron attribute의 경우에는 결과가 0이 된다. 따라서 patron의 entropy가 너 낮아지고, 이 경우에 information-gain이 높아지게 된다. 

따라서 이런식으로 하면 search-space를 확실히 줄일 수 있다. root부분에는 information-gain이 가장 높은것을 위치시켜야 한다. 한쪽으로 몰릴수록, entropy가 낮을수록 information gain이 높을 것이다. 최악의 경우는 entropy가 반반으로 몰리는 경우이다. 

성능을 측정할 때는 test-set은 학습에 사용하지 않는것이 중요하다! supervised learning의 경우에 일부 데이터는 테스트 데이터로 사용하는 것이 중요하다. 또한 마찬가지로, training set size가 크면 클수록 맞을 확률이 높아진다. 하지만 이 set을 확보하는데 역시 상당한 비용이 들기 때문에 set을 무한대로 확보하기는 쉽지않다. 따라서 셋을 조금씩 확보해가면서 그래프를 그려보면 어느정도 데이터가 있으면 괜찮은 모델을 만들 수 있을 지 짐작할 수 있다. 

이 퍼포먼스를 측정하는데에 있어 sample수가 늘어남에 따라 100%에 수렴한다고 하면 realizable, 늘려도 소용이 없는 경우에는 nonrealizable, 비례하면서 증가하는 경우에는 redundant라고 한다. 

 ockham's razor라는 것이 있었다. 비슷한 성능을 내는 모델이 있다고 가정했을 경우에, 좀더 slim하고 simple한 모델을 선호한다는 것이였다. tree를 계속해서 branching해 나가는 것을 fitting 한다고 한다. 이때 fitting이 과도하게 진행되어 consistency는 높아졌지만 test데이터로 확인하는 performance는 오히려 낮아지는 현상도 발생한다. 이를 overfitting이라고 한다. decision-tree에서는 이를 막기 위해 가지를 쳐내는 작업을 하는데 이를 pruning이라고 한다. 만약에 이와 같이 pruning을 한 이후에 성능이 더 좋아졌다고 한다면, 그 모델이 좀더 simple하고 generalized된 모델이라고 할 수 있다. 

pk와 nk는 실제 테스트에서의 positive,negative case의 개수이다. 

  학생번호의 경우는 너무 많아서 학생별로 나눠지게 될 것이다. 이런식으로 split이 지나치게 많이 일어나게 되면 information gain은 넉넉하게 일어나겠지만, 우리가 예측하고자 하는 것은 학생 개개인이 아니므로 오히려 도움이 되지 않은 attribute일 수 있다. 

이처럼 Numeric input data또한 마찬가지인데, 이런 boundary를 잘 잡기 위해서는 gain-ratio가 필요하다. information gain이 가장 높은 곳을 기준으로 잡으면 될 것이다. 

 model tree라는 것은 classification이 아닌 regression model이라고 했을 경우에, 위와같은 방식으로 구현할 수도 있다. 

  제일 중요한 것은 결국 evaluation이다. 이때 우리가 하고싶은 것은 아직 알지 못하는 미래의 데이터에 대해 예측을 잘 하는 모델을 만들고 싶은 것이다.  모델을 만들때와 평가할 때 같은 데이터 셋을 사용하면 안된다. 다르게 적용시키기 위해 가지고 있는 데이터셋을 나누어야 하는데, 이 데이터 셋을 traing set과 test set으로 나눌때 어떻게 나눌것인가? 이를 위한 방법이 바로 cross-validation이다

  이 validation을 좀더 정확하게 하기 위해서, 데이터셋을 k개의 동일한 flod로 나누어서 한개의 fold들 testing으로 사용하고, 나머지 k-1개의 fold를 training set으로 사용하는데, 이를 각 fold가 돌아가면서 학습하고 평가하는 방식을 k-fold cross-validation 방법이라고 한다. 이런식으로 하면 k번의 evaluation을 할 수 있다. 이를 average한다면 한번의 경우에 비해 좀더 error-rate이 참값에 가까울 것이다. 따라서 k가 5~10일때 괜찮은 성과를 내는 것으로 알려져 있다. leave-one-out cross-validation이라는 방법도 있는데, 이는 좀더 극단적으로 1개의 데이터 샘플을 test-set으로 하고, 나머지 k-1개의 데이터를 training-set으로 하는 검증 방식이다.

  여기서 어떤 모델이 좋은지를 선택하기 위해서는 일단 test-set을 고정을 시켜놔야 한다. 그리고 나서 traing-set과 validation-set을 나누어서, 모델이 overfittng되었는지, 혹은 관찰하지 않은 데이터로는 모델이 어느정도 성능을 내는지 알 필요가 있다. 이때는 validation set을 이용하게 된다. 

  decision tree에서 tree-size가 너무 작아버리면 error-rate이 높아진다. 그 이유는 모델이 아직 학습이 덜 되어 under-fitting이 되었기 때문일 것이다. tree-size가 7을 넘어가는 시점부터 training set의 error-rate은 거의 0에 수렴하고 있다. 이는 training data를 잘 학습한 상태라고 볼 수 있다. 그런데 size 7이후로 validation set의 error는 점점 커지고 있는 상태이다. 이런 경우는 모델이 overfitting이 되어서 그렇다고 볼 수 있다. 따라서 underfitting의 여부는 training set으로, overfitting의 여부는 validation set으로 확인할 수 있다. 

  따라서 validation set과 training set의 결과를 보고 underfitting도 안되었고, overfitting도 안된 시점이 최적의 모델이라고 할 수 있다. 상황에 따라서는 validation-set이 충분히 확보되지 않는 경우도 있는데, 그렇더라고 test-set과 training set을 명확히 구분하는 것은 중요하다.

  loss function이란 예측한 값과 실제 값이 얼마나 차이나는 지를 보여주는 함수이다. 그런데 성능척도를 확인할때, 전체 케이스 중에서 특정 케이스를 확인하면 성능측정이 제대로 되지 않을수 있다. 예를 들어 100개의 메일중 1개의 메일만 스팸이라고 가정했을때, 모델이 100개의 메일 전부 스팸이 아니라고 판단했다면 그 모델의 정확도는 99%가 된다. 스팸메일이 계속해서 걸러지지 않음에도 99%의 정확도라고 말할 수 있다는 것이다. 따라서 이는 제대로 성능을 측정했다고 말하기 힘들다. 따라서 스팸메일 중에서 스팸이 아니라고 하는 경우와, 스팸이 아닌 메일들 중에서 스팸이라고 하는 경우를 나누어 살펴야 할 것이다. 따라서 이를 loss-function으로 나타낸다. error-rate자체가 loss-function이 될 수도 있다. 간단하게는 absolute value loss(L1 norm)이라고 한다.  두번째는 L2 norm이라고 한다. 절대치를 쓰는 경우와, 제곱을 쓰는 경우는 어떤 차이가 있을까? 수치적인 미분을 할 때에 L2norm이 유리해보인다. 0/1 loss는 같으면 0, 다르면 1인데 error-rate과 굉장히 유사하다고 볼 수 있다. 

  generalization loss는 얼마나 그 발생빈도가 빈번한지를 나타내기 위해 (x,y)의 발생확률을 붙여서 확인하는 방법이다. 발생확률이 높다면 비중이 커지게 될 것이다. 또한 우리가 하고자 하는 것은 이 generalization loss의 가장 minimun한 값을 가지는 모델을 찾는 것이다. 대부분의 경우에 (x,y)의 발생확률을 아는 것은 쉽지 않다. 따라서 각 케이스의 발생확률이 동일하다고 가정하고, 계산하는 수밖에 없다. 

  unrealizable하다는 말은, 예측하고자 하는 값이 해당 모델로는 설명하기가 힘든 경우를 말한다. variance는 training-set이 달라질때마다 모델이 달라질 수 있다는 말이다. 만약에 예측할려는 모델이 이상적으로 training set의 사이즈가 무한히 많다면, variance값은 0이 될 것이다.  noise는 내가 관찰하고자 하는 값이 내가 수집한 데이터가 아닌 다른 곳에서 영향을 받아 나온 결과라고 한다면, 그것은 noise가 있는 것이다. 사실 hypothesis을 전부 검증하는 것은 쉽지 않은 일이다. 따라서 loss는 생길수 밖에 없다. 

  하지만 단순하게 empirical loss만 줄이는 것보다, ockham's razor에 따라 같은 성능을 보인다면 이왕이면 simple한 모델을 선택하는 것이 generalization이 더 잘 될것이라고 생각하는 것이다. 따라서 같은 empirical loss를 보이는 모델에 대해, complexity가 복잡할 수록 패널티를 준다고 생각하면 좀더 generalization이 잘 되는 모델을 찾기 편할 것이다. 따라서 minimize하고자 할 때에, empirical-loss와 complexity를 동시에 생각하면 좀더 simple한 모델이 되기 쉬울것이다. 이때에 complexity함수를 regularization function이라고 하고, 이 전체를 cost라 한다. 한편 모델과 complexity 등을 bit개념으로 encoding해서 접근하는 것을 minimun description length라고 한다. 또한 L1 norm을 하면 이 L1 norm 자체도 feature selection의 역할을 한다.