[패턴인식]Chapter 9.1-3 Algorithm-Independent Machine Learning

(김경환 교수님의 자료와 수업을 통해 제작되었습니다.)

9.1 Introduction

  이전 장까지를 통해 여러 classfier를 살펴보았다. 이 과정에서 어떠한 장점을 갖고, 단점을 갖는지 살펴보았다. 이번 장에서는 여러 문제에 대해 일반적으로 좋은 classifer가 존재하는 지에 대해 문제를 다룬다. 이 책에서는 classfier는 각 문제마다 다른 접근을 이용해야 하며, 일반적으로 모든 문제에 대해 좋은 classfier는 존재하지 않는다고 말한다. 따라서 주어진 문제에 대한 충분한 이해가 필요하며, 그에 맞는 model의 설계가 필요하다. model을 설계하는 것에 있어서는 각 model의 장단점을 확실히 알고 있어야 하며, 문제에 대한 깊은 이해가 필요할 것이다.

9.2 Lack of inherent superiority of any classifier

[No Free Lunch Theorem]

  공짜 점심은 없다는 이론이다. 어떠한 classifier도 일반적으로 좋다고 말할 수 있다고 말하며, 주어진 문제와의 fit된 것만 존재한다고 말한다. 어떠한 classifier가 좋다 나쁘다라는 것을 판정하는 것에도 문제가 생길 수 있으며, 이는 다음에 더 자세히 다루게 된다.

  위 그림 중 위 3개의 사진이 어떤 classifier는 장점과 단점을 갖게된다는 것이며, 아래의 3개의 사진은 장점만 존재하거나, 장점과 거의없는, 평균의 성능을 갖게 되는 classifier를 나타낸 것인데, 이는 impossible한 learning system이라고 말한다.

[MDL Minimum Description Length]

  classifier는 문제를 해결할 수 있는 범위 내에서 가장 간단한 구조를 가져야 한다는 것이다. 이는 overfitting에서도 다루었는데, training data에 대해서 완벽하게 구별하기 위해 높은 차원으로 나타내다 보면 test data에 대해서는 오히려 낮은 정확성을 갖게된다는 것이다. 이에 따라 문제를 다룰 수 있는 정도로 충분히 복잡한 구조를 가져 underfitting을 방지해야 하나, 너무 복잡하게 하여 overfitting이 일어나게 하면 안된다는 것이다.  예로 문제를 설명하는 것에 있어서도 본래 system이 필요로 하는 설명 이상을 붙이면 안된다고 말한다.

9.3 Bias and Variance

  Classifier의 성능을 나타내기 위한 지표가 필요하다고 언급하였다. 이를 위해 bias와 variance 개념이 활용된다. bias는 high bias implies a poor match, high variance implies a weak match 라고 나와있다.

 

  풀어서 말하자면, bias가 높은 경우는 underfitting의 경우와 비슷하다고 볼 수 있다. 주어진 샘플에 대한 classifier의 정확도 자체가 떨어지는 것이다. classifier가 true value와 기대값이 크게 차이나는 경우이다. bias만 고려한다면 낮은 bias를 갖는 classifier를 원하게될 것이다.

 

  variance가 높은 경우는 overfitting과 관련하여 생각하면 될 것이다. 우리는 무한한 샘플을 얻을 수 없으므로, 샘플이 주어질 때마다 classifier가 다르게 학습될 것이다. 다른 샘플이 주어졌을 때마다 classifier가 크게 달라진다면 high variance를 갖는다고 하며, 이는 주어진 샘플에 대해서만 완벽하게 나타낼수록 high variance를 갖는다고 해도 무방할 것이다.

 

  이 두 bias와 variance는 trade-off관계를 갖게 될 것이다. 주어진 training set에 대한 정확도가 높을수록 overfitting이 생길 것이고, 이에 따라 낮은 bias와 높은 variance를 갖게될 것이다. 낮은 차원 혹은 낮은 복잡도로 model을 구성한다면 주어진 샘플에 대한 정확도는 조금 줄어들겠지만, 일반성을 유지함으로써 overfitting되는 부분이 줄어들고, underfitting될 확률이 늘어나면서 bias는 늘어나지만 variance는 줄어들게 될 것이다. 

    이를 수식적으로 살펴보자. $g$는 추정한 함수이고, $F$는 알려지지 않은 true value라고 하자. 이 차이의 제곱에 대한 기대값을 풀어쓰면 bias제곱과 variance의 합으로 나타낼 수 있다. 위에서도 볼 수 있듯이, bias는 기대값과 참값 간의 차이이며, 분산은 training set이 바뀜에 따라 추정함수 $g$가 변하는 정도를 나타내는 것을 알 수 있다.

  (a)와 (b)의 함수는 고정된 선형함수이고, 기울기는 같은 상태에서 평행이동한 관계에 있다. (b)의 함수가 (a)보다 실제 분포와 가까이 있는 것을 볼 수 있고, 이에 따라 bias가 낮은 값을 갖게 된다. 추정함수가 고정되어 있기 때문에 샘플이 바뀌어도 고정되어 있기 때문에 거의 zero variance를 갖게 될 것이다. 

 

  (c)와 (d)의 함수는 샘플에 맞춰지는 함수이고, (c)는 3차함수로, (d)는 1차 함수로 나타낸 것이다. (c)가 training set에 대해 더 정확하게 맞춰질 수 있고, 그에 비해 (d)는 덜 맞춰진 모습을 볼 수 있다. 이에 따라 (c)가 (d)보다 더 낮은 bias값을 갖는다. 반면, 샘플이 바뀜에 따라 3차 함수로 학습한 결과는 더 크게 달라질 것이므로 (c)의 variance가 (d)보다 더 크다.

  

  또한, 주어진 샘플의 개수가 무한하다면 모든 모델의 분산은 0으로 접근하게 될 것이다.

  Covariance metrics를 통해 Gausian problem을 해결하는 Bayes classifier의 decision boundary를 보여준다. 다양한 모양을 가질 수 있는 왼쪽부터 원의 모양만 나타낼 수 있는 오른쪽 열로 나타낸다. 맨 왼쪽의 열은 주어진 set에 대해 제일 잘 맞출 수 있고, 이에 따라 낮은 bias값을 갖는 장점을 가질 수 있게 된다. 하지만, D1, D2, D3에 대해 decision boundary가 크게 달라지는 것을 볼 수 있고, 높은 variance값을 갖는 것을 알 수 있다.

 

  맨 오른쪽 열의 원을 통해서만 training set에 대해 나타낸 것은 주어진 set에 대해 완벽하게 나타내지 못하므로 bias는 높지만, D1, D2, D3에 대한 decision boundary의 결과가 크게 차이나지 않는 것을 볼 수 있다. 따라서 낮은 variance를 갖는 장점을 갖는다.

 

  위에서 언급한 bias와 variance 둘다 적당한 값으로 유지하는 것이 중요하겠지만, 이 책에서는 낮은 variance를 유지하여 overfitting을 막는 것이 더 중요하다고 한다. 0 bias, 0 variance는 존재하지 않기 때문에 문제에 따라 fit하게 모델을 설정해야 한다고 한다. 샘플의 개수가 커질수록 더 많은 파라미터를 이용하여 model을 나타내야 할 것이며, 샘플의 개수가 무한한 개수에 가까워질 수록 variance는 감소하게될 것이다.

---

Reference

• pattern classification by richard o. duda