패턴인식 - 8. Ensemble - Bagging

1. Ensemble

- 지난 시간에 학습 데이터로부터 decision tree(분류기)를 만들고 판단의 문제를 tree searching으로 변환하는 것을 공부했다.

- 여러 decision tree를 함께 사용해서 나온 결과를 결합(voting)한 것을 decision forest라고 한다.

- decision tree뿐만 아니라 여러 분류기를 함께 사용해서 성능을 높일 수 있고 이 방법을 ensemble이라고 한다.

- bagging, boosting은 ensemble의 방법중 하나이다.

- bagging : 학습데이터가 많을 때 주로 사용된다.

- boosting : 학습데이터가 적을 때 주로 사용된다.

 

- decision tree를 예를 들면, 데이터, feature가 많을 수록 가지는 많아지기 마련이다. 나무가 커질수록 search 시간은 길어진다.

- 그래서 비효율적인 큰 나무 하나를 만드는 것 보다 효율적인 작은 나무 여러개를 결합시키는 방법을 생각할 수 있다. (속도도 빠르고 variance도 줄임)

- 즉 전체 데이터에 대해서 하나의 나무를 만들지 말고 여러개의 작은 학습 데이터셋들에 대해 모델을 만들고 결과를 합치는 것이 좋을 수 있다.

* 헷갈리지 말아야 할 것 : 같은 모델인데 학습 데이터가 다른건가? 학습 데이터가 다르면 decision tree는 다른 모양이 된다. 즉 데이터가 다르기 때문에 다른 분류기라고 볼 수 있다. DNN도 마찬가지 이다. 학습 데이터에 따라 모델의 weight가 다르기 때문에 다른 분류기라고 볼 수 있다.

2. Bias, Variance

- 앙상블을 본격적으로 배우기 전에 알아야 하는 내용이다.

- variance는 편차, bias는 오차를 말한다. 

- ensemble의 목적은 여러 분류기를 함께 사용하여 bias, variance를 줄이는 것이다.

3. Bias-Variance Decomposition

- 만약 학습데이터의 이상적인 pdf가 위와 같다고 해보자.

- 실제로 서로 다른 독립적인 학습 데이터셋을 뽑았다. 

- 초록 지점에 대해 분류를 수행한 결과를 보면 어떤 지점 y를 누구는 red 누구는 blue로 판단했다. 

- 이때 분류 결과는 training set의 choice에 따른 random variable로 볼 수 있다.

- 결국 분류기의 정확도(y)는 분포를 이룬다.

4. bayse opimality

- 아까 위에서 나눈 training dataset의 수만큼 Loss함수가 나온다.

- loss는 test dataset에  대한 함수로 정의할 수 있다.

- n개의 학습 데이터셋에 대한 랜덤변수 y -> n개의 Loss()가 정의 -> n개의 학습데이터셋에 대한 loss의 평균을 구할 수 있다.

- y - y* : 모든 y가 truth와 일치하면 이 값은 0이 된다.

- var : 이 값은 데이터가 갖는 선천적인 값이다. 분류기와 상관 없이 데이터셋에 대한 truth의 편차를 나타낸다. 이 값이 bayse optimality, 최적화 한계선이다.

- 랜덤변수 loss()의 평균을 다시 정리해보자.

- bias는truth와 분류기 결과의 차이이다. 이 값이 크면 underfitting의 가능성이 있다. (variance는 줄어드는 경향이 있다.)

- variacne는 출력 결과의 편차를 나타낸다. 이 값이 크면 overfitting의 가능성이 있다. (반대로 bias는 줄어든다.)

-ensemble 로 여러 decision tree를 합침으로써 bias, variance중 하나를 낮출 수 있다면 하나의 decision tree를 만드는 것 보다 더 나을 것이다.

5. Bagging

- error는 bias, variance, bayes error 세 종류가 있음을 확인했다.

- 전체 데이터셋에서 m개의 독립적인 학습 데이터 셋들을 나누어 학습한다고 해보자.

- bias는 m개의 독립 학습 데이터 셋으로 나누어서 학습해도 변하지 않는다.

- 하지만 variance는 m개의 학습 셋으로 나누어 학습했을때 1/m로 줄어든다.

 

- 즉 정리하면 전체 학습 데이터 셋을 여러개(n개)로 나눈 다음 각각 학습에 활용한다. n개의 결과를 평균 내보면 bias는 변함이 없지만 variance error는 줄일 수 있다.

- 이 방법을 bagging이라고 한다.

- 만약 전체 dataset에서 무작위로 골라낸 datasets들이 서로 완전히 독립적이지 않으면 1/m까지 줄어든다고 보장할 수 없다.

- datasets 간의 correlation 로우가 1이면 var = 1(로우) * 표준편차^2, 즉 그대로다 같은 데이터 셋에 대해서 학습 시키면 variance error는 줄지 않는다.

- 반면 로우가 0이면 var = 1/m * 표준편차^2, 즉 variance error가 1/m로 줄어든다.

- bagging의 효과를 최대로 얻고 싶으면 전체 데이터셋에서 작은 데이터셋들을 나눌 때 최대한 독립적으로 나눠야 한다.

6. Random Forest

- ensemble - bagging은 특히 random forest에서 강점을 보인다.

- 데이터셋을 나누면 각기 다른 decision trees가 만들어진다. 이 tree들을 병렬로 수행시키면 한개의 매우 큰 tree 보다 훨씬 효율적이다.

- 게다가 1/m만큼 variance도 줄일 수 있다.

- 아예 feature까지 random하게 선택하도록 하면 나눈 datasets들의 correlation을 훨씬 낮출 수 있다.