Ensemble_Model
Ensemble에 대해 자세히 알아보자 (Bagging, Bootstrap, 그리고 RandomForest)
앙상블 모델에 대해서 공부하기 전에, 그 배경부터 알아볼 필요가 있다.
NFL (No Free Lunch)
No Free Lunch 이론은 David H. Wolpert가 정리한 이론으로 모든 문제에 대해 다른 모든 알고리즘을 능가하는 모델은 없다는 이론이다. ‘어떤 특정 정책에 의해 얼핏 보면 이득을 얻는 것 같지만, 그것은 한 측면의 이득일 뿐이고 반드시 이면에 다른 측면이 있고 그 측면에서 손해가 발생한다.’는 것이 핵심이다.
이 이론에 따라서 혼성모델의 필요성이 대두되었다. 혼성모델이란 여러 알고리즘을 결합하는 모델이다. 이 모델은 특정 문제가 주어진 상황에서 그 문제를 가장 높은 성능으로 풀 수 있는 알고리즘에 대한 필요성에 의해서 제시되었다.
Resampling
리샘플링은 데이터가 부족할 때 같은 샘플을 여러번 사용하는 것을 말한다. 성능 통계치의 신뢰도를 높이기 위해 사용된다. Resample을 하는 이유는 다음과 같다.
- 실제 상황에서는 만족할 만한 큰 샘플을 얻기가 힘들다.
- Bias-Variance Trade off를 통해 큰 샘플이 중요하다는 것을 알 수 있다.
- sample의 집합이 커지면 variance가 감소한다!, MSE도 감소한다!
- 모델의 선택은 별도의 검증이 필요하다.(검증용 데이터, 큰 샘플의 필요성)
Bootstrap, Statistical term for “roll n-face dice n times”
부트스트랩은 Resampling을 이용하여, 분류기의 성능을 측정하는 방법 중 하나이다. 통계에서는 추정치에 대한 검증용(가설 검증)으로 많이 사용된다. 부트스트랩의 장점은 한번도 뽑히지 않은 데이터가 발생한다는 것이다. 이를 통해 데이터를 아낄 수 있게 된다.
Ensemble
앙상블 모델은 혼성모델 중 하나이다. 앙상블은 두가지 방식이 존재한다.
- 같은 문제에 대해 서로 다른 여러 알고리즘이 해를 구하고, 결합 알고리즘이 그들을 결합하여 최종 해를 만드는 방식
- 문제와 유사한 여러 하위 문제들에 대해 하나의 알고리즘이 해를 구하고, 결합 알고리즘이 그들을 결합하여 최종 해를 만드는 방식
앙상블의 동기는 단순히 통계적, 수학적일 뿐만 아니라, 사람들의 심리 등 여러부분을 관통하는 내용이기도 하다.
1 | 어느 도시에서는 소를 광장에 매어 놓고 참가자들에게 체중을 추정하여 적어 내게 하고 실제 체중에 가장 가까운 사람에게 |
사람들은 중요한 결정을 할때 여러 사람의 의견을 들어보고 결정하려는 경향이 있고, 이런 경향은, 통계학이 아닌 다른 분야에서도 사용되는 개념이다.
다양성
앙상블 모델의 핵심은 다양성이다. 앙상블에 참여한 모델이 모두 같은 결과를 낸다면, 그것은 앙상블 모델로써 어떠한 장점도 갖고 있지 않다. 한 분류기가 틀리는 어떤 문제를, 다른 분류기에서는 맞출 수 있어야 앙상블 모델로써 가치가 있을 것이다.
앙상블 분류기 시스템은 앙상블 생성, 앙상블 선택, 앙상블 결합의 단계를 거친다.
앙상블 생성
- Resample을 이용해서 (Bagging, Bootstrap) 샘플 집합들을 생성하고, 분류기를 훈련한다.
- Feature Vector의 subspace를 이용해서 샘플 부분 집합을 생성하고 분류기를 훈련한다.
- 앙상블의 분류기는 요소분류기와 기초분류기로 구분된다.
앙상블 결합
요소 분류기(기초 학습기)들의 출력을 결합하여 하나의 분류 결과를 만드는 과정이다.
요소 분류기의 출력은 세가지의 방식으로 나뉜다.
- Class Label
- Majority Vote : class 라벨이 많이 나온 쪽으로 분류한다.
- Weighted Majority Vote : 성능 좋은 분류기에 가중치를 부여한다.(Adaboost)
- Behavior knowledge space(BKS/행위지식공간) : 경험한 케이스를 테이블로 갖고 분류기 결과를 보고 경험적으로 결정한다(테이블에서 찾아서). 다수결 방법의 성능을 고도화 할때 사용됨
- Class Ranking
- Borda 계수
- Class Probability
- Softmax
Bagging (Bootstrap + Aggregating)
부트스트랩을 다중 분류기 생성 기법으로 확장한 것이다. 부트스트랩 된 샘플 집합에서 훈련을 하고, 입력 값에 대해 분류기들의 평균값이나, 다수결 투표를 취한다. 샘플링은 복원추출하는 방식으로 하고, 훈련된 분류기의 결과를 모두 종합하기 때문에 Bagging이라고 부른다.
- 반복적인 복원 추출 (Bootstrap)
- 결과를 모두 종합 (Aggregation)
Bagging, 배깅은 언제 사용할까?
배깅은 편향이 작고 분산이 높은 모델에 사용하면 효과적이다.
- 트리 분류기와 같이 불안정성을 보이는 분류기에 큰 효과를 발휘
- 훈련 집합이 달라지면 차이가 큰 트리가 생성 ⇒ 다양성 확보
- Bias를 변화시키지 않고 variance를 감소시킨다.(Bias를 쪼오오오오끔 희생한다.)
배깅은 분산을 감소시키기 위해, 훈련데이터에서 많은 샘플링을 하고(Bootstrap), 샘플들로 별도의 Decision Tree를 구성한 후, 회귀나 분류문제를 푸는데 사용된다. 회귀는 분류기 결과의 평균값을 사용하고, 분류는 최빈값을 취한다.
배깅은 이미 저분산 모델인 경우 별로 효과가 없다. Bias-Variance Tradeoff 를조금만 생각해보자. 분산이 이미 줄어있는 상태에서는 더 줄일 분산이 없다. 배깅은 오직 분산을 줄이는 데 효과적이다.
Out-of-Bag (OOB) Error Estimation
샘플에 대해 Bootstrap을 하게 되면 부트스트랩 샘플은 전체 훈련데이터의 약 63.2%를 차지하게 된다.(왜 그러한가에 답은 $\lim_{n\to\infty} (1-{1\over n})^n$을 풀면 답이 나온다. $1\over e$로 0.378이 나온다. 자세한 내용은 링크를 참조하면 된다. [https://www.quora.com/Why-is-the-limit-1-frac-1-n-n-equal-to-frac-1-e])
부트스트랩되지 않은 샘플들은 한번도 사용되지 않은 샘플들로 검증데이터에 활용할 수 있다. 이런 training observations은 out-of-bag observations이라고 불린다.
OOB estimate of test error
- 부트스트랩 샘플을 이용하여 개별 학습기를 학습한 후, OOB에 속하는 샘플들에 대한 예측값을 모두 구한다.
- OOB의 실제 라벨값과 OOB의 예측값을 이용하여 OOB error를 구한다.
- 모든 부트스트랩 샘플 sets에 대하여 위의 과정을 반복하면, 샘플 sets 수 만큼의, errors를 모을 수 있다.
- OOB errors의 평균값을 이용하여 bagging 모델의 최종 테스트 error를 계산한다.
Weakness of Bagging
배깅은 엄청나게 효과적인 것처럼 보이지만 약점이 존재한다. 배깅은 feature를 모두 사용하고, row를 랜덤하게 선택하는 것이다. Decision Tree를 만든다고 해보자, 만약 영향력이 높은, Information Gain이 높은 모델을 사용한다고 했을때, 특정 Feature만 계속 선택되서 트리가 만들어질 가능성이 있다. 즉, 중요한 칼럼들이 트리의 초기 분기때 모든 표본에 그대로 존재하게 된다. 이렇게 되면 만들어진 대다수의 트리들의 결과가 비슷해진다. 이것이 반복되면 트리간의 상관관계가 발생해서 분산 감소의 효과가 줄어들게 된다.
(배깅의 약점은 IID condition이다. IID 조건을 만족하는 경우 분산은 $Var={\sigma^2\over n}$이 되지만, IID를 만족하지 못하는 경우, 상관관계가 발생하여 $Corr = p$이라고 할때, $Var = p\sigma^2$가 된다.)
그래서 혁신적인 아이디어와 함께 등장하게 된 것이 Random Forest이다.
Random Forest
랜덤 포레스트는 일반적으로 bagging 방법(또는 pasting)을 적용한 결정 트리의 앙상블이다.
랜덤 포레스트 알고리즘은 트리의 노드를 분할할 때 전체 특성 중에서 최선의 특성을 찾는 대신 무작위로 선택한 특성 후보 중에서 최적의 특성을 찾는 식으로 무작위성을 더 주입한다. 트리를 더욱 다양하게 생성하고 (트리의 의존성을 낮추고, 다양성을 증가) 편향을 손해 보는 대신 분산을 낮추어 전체적으로 더 훌륭한 모델을 생성한다.
Random Forest는 쉽게 말해 Tree 모델에 Bagging과 Subsampling기법을 사용한 모델이다.
훈련 데이터에서 bootstrap 샘플을 뽑아내고, 노드 분기 시, 모든 Feature가 아니라, 일정 Feature만 사용하는 것이 특징이다. 이를 통해 Tree간의 Correlation을 줄이고, 분산을 감소시킬 수 있다.
Subspace Sampling
샘플링 시에는 일반적으로 전체 변수가 p라고 할 때, $m = \sqrt{p}$를 사용한다.
(m = p이면 Bagging이다. 또한 회귀에서는 경험적으로 $m ={p\over3}$를 사용한다.)
Random Forest 모델의 장단점?
장점 : 굉장히 간편하다. 스케일링도 필요없고 파라미터 튜닝을 많이 안해도 성능이 뛰어나다. 의사결정의 트리의와 배깅의 단점은 극복하고 장점만을 가져온 것이라고 할 수 있다.
단점 : 차원이 높고 매우 희소한 데이터에서는 잘 작동하지 않는다. 이런 희소한 데이터에는 선형 모델이 더 적합할 수 있다.
Ensemble_Model