[Machine Learning] Aggregating decision trees

Bagging(Bootstrap aggregation)

• 머신러닝 방법의 변동성(variance)을 줄이기 위한 일반적인 방법으로 decision tree 방법에 특히 유용하여 많이 적용됨
• -> 여러 개의 독립적인 데이터셋을 확보하는 것이 어려워 bootstrap 방법 사용

 

OOB(Out-of-Bag Error Estimation)

• Bagging 방법에서는 아주 직관적인 test error 추정 방법이 존재
• Bootstrap은 중복을 허용하므로 하나의 bootstrap training data에서 평균적으로 본래(original) 데이터의 2/3가 샘플링됨
• 나머지 적합에 사용되지 않은 1/3의 데이터를 OOB(out-of-bag)으로 명명
• i번째 데이터가 OOB인 경우의 decision tree에서 i번째 데이터의 response를 구하고 이들을 평균하여  test error의 추정에 사용 -> 이 추정 값은 B가 충분히 크면 LOOCV와 같음

 

Random forests

• Bootstrap에 의해 생성된 트리들의 관계성을 낮춰 성능을 향상하는 방법
• Bagging과 마찬가지로 bootstrap dataset에 대하여 트리를 생성하지만 predictor의 사용방법이 다름

 

Boosting

• Bagging과 유사한 방법이나 트리를 이전에 학습한 트리로부터 순차적으로(sequentially) 천천히 학습(learn slowly)시키는 방식
• 학습(트리 생성) 방법
  1. 아무 정보도 없는 트리 생성
  2. 트리를 response에 적합하는 것이 아닌 residual(적합 후 남은 양)에 적합
  3. Residual에 적합하여 만든 트리를 기존 트리에 업데이트하고 r를 업데이트
  4.   -> 2,3 의 과정을 B회 반복 후 최종 트리를 얻음
• 알고리즘 : 작은 트리(소수의 terminal node)를 더해 가는 방법

 

Boosting 의 tuning parameter

• 트리의 수B
  • B가 크면 과적합 될 수 있으므로 cross-validation으로 정함
• Shrinkage parameter 람다
  • 작은 양수의 값으로 boosting이 얼마나 빠르게 학습되는지를 정함
  • 보통 0.01 또는 0.001 정도로 정하며 값이 작을수록 더 큰 B 필요
• 분기의 수(the number of splits) d 
  • d=1의 경우에도 좋은 성능을 냄