Tree-based Model, Bagging

랜덤포레스트가 뭐길래? 회의에서 당당하게, 수식없이 알아보자

$ f(X) = \sum_{m} c_m * I(x \in R_m) $
Objective function : $ \sum_{J} \sum_{i \in R_j} (y_i-\hat{y}_{R_j})^2 $

• 설명변수 공간, $ X_1, \ldots, X_p $ 에 대한 가능한 값들의 집합 → J개의 다르고 겹치지 않는 영역 $ R_1, \ldots, R_j $ 로 분할
• 영역 $ R_j $ 에 속하는 모든 관측치들에 대해 동일한 예측, 예측값은 $ R_j $ 의 training 관측치들에 대한 반응변수 값의 평균

분할의 모든 경우 다 고려하는 것은 현실적으로 불가능 : top-down greedy 방법 사용
다음 식을 최소로 하는 j와 s 값 :
$ \sum_{i:x_i \in R1=\{X|X_j<s\}}(y_i-\hat{y}_{R_1})^2 + \sum_{i:x_i \in R2=\{X|X_j\geq s\}}(y_i-\hat{y}_{R_2})^2 $

cost complexity prunning (weakest link prunning) 가지치기
Cost Function = Err(T) + $ \alpha $ |T| , |T| : 터미널 노드 수
Full Tree에서 hyperparameter $ \alpha $ 에 의해서 비용함수를 최소로 하는 SubTree 선택 (0이면 Full Tree)
$ \alpha $ 는 검증셋 또는 교차검증 사용해서 선택

https://ratsgo.github.io/machine%20learning/2017/03/26/tree/
https://danbi-ncsoft.github.io/study/2018/12/06/entropy.html
그냥 오분류율은 충분히 민감하지 않아 다른 measure(불순도)가 선호됨.
분할전 Gini Index $ \sum_{j=1}^{J} p_j(1-p_j) $ , j:변수가 가지는 Class 수
분할후 $Gini.Index(A) = \sum _{ i=1 }^{ d }{ { \left( { R }_{ i }\left( 1-\sum _{ k=1 }^{ m }{ { p }_{ ik }^{ 2 } } \right) \right) } } $
분할전 Entropy $ -\sum _{ k=1 }^{ m }{ { p }_{ k }\log _{ 2 }{ { (p }_{ k }) } } $
분할후 $ Entropy(A)=\sum _{ i=1 }^{ d }{ { R }_{ i } } \left( -\sum _{ k=1 }^{ m }{ { p }_{ k }\log _{ 2 }{ { (p }_{ k }) } } \right) $ (Ri=분할 전 레코드 가운데 분할 후 i 영역에 속하는 레코드의 비율)
분할전 → 분할후 줄어드는 양이 큰 변수분할 선택

• 심지어 선형회귀보다 설명하기 쉽다
• 인간의 의사결정 과정을 더 밀접하게 반영한다고 생각된다 (적어도 일부 사람들에게)
• 그래픽으로 나타내기 쉽고, 비전문가도 쉽게 해석할 수 있다.
• 가변수들을 만들지 않고 질적 설명변수들을 쉽게 처리할 수 있다.
• 변수 정규화, 표준화 등 안해도 된다

예측 정확도가 낮다.
trees are inherently high-variance,
the bushier they are, the higher the variance.

분산이 각각 $ \sigma^2 $ 인 n개의 독립적인 관측치 $ Z_1, \ldots , Z_n $ 의 평균 $ \bar{Z} $ 의 분산은 $ \sigma^2/n $. 즉, 관측치들의 집합은 평균하는 것은 분산을 줄인다.

• 자연스러운 방법은 모집단으로부터 많은 수의 training 셋을 취하고, 각 training 셋으로 별도의 예측 모델을 만들어 예측 결과들을 평균하는 것
  • 하지만 다수의 training set을 일반적으로 가질 수 없다
• 단일 훈련자료로부터 반복하여 표본들을 샘플링함으로써 bootstrap.

$ \hat{f}_{bag}(x) = {1\over B} \sum \hat{f}^{*b}(x) $ (평균 or voting)

with positive pairwise correlation $ \rho $, the variance of the average is $ \rho \sigma^2 + {{(1-\rho)}\over{B}} \sigma^2 $

하지만 각각 독립인 것은 어떻게? → Random Forest

트리들의 correlation을 줄여줌. 상관성을 제거(decorrelate) 간단한 방법으로 배깅된 트리들보다 더 나은 성능을 제공
배깅에서와 마찬가지로 Bootstrap된 훈련 표본들에 대해 다수의 Decision Tree를 만든다. 그러나 트리 내에서 분할이 고려될 때마다 p개 설명변수들의 전체 집합에서 m개 설명변수들로 구성된 랜덤표본이 분할 후보로 선택된다.

• tree 수 B, 각각 나무에서 선택하는 feature 수 m < p
  • 트리의 수 B는 배깅에서 결정적(critical) 파라미터는 아님. 아주 큰 B 값을 사용해도 과적합이 일어나지 않을 것.
  • m = p 를 사용하여 만들면 단순히 배깅.
  • 보통 $ m \approx \sqrt{p} $ 를 사용. (regression의 경우 p/3)
  • 자료 하나의 매우 강한 설명변수가 다수의 적당히 강한 설명변수와 함께 있다고 해보자. 그러면, 배깅된 트리들의 컬렉션에서 대부분 또는 모든 트리들이 이 강한 설명 변수를 맨 위의 분할(top split)에서 사용할 것. 그 결과 배깅된 트리들은 모두 서로 상당히 유사하게 보일 것.
• Bootstrap : 보통 전체 데이터세트 크기의 80%, 기술적으로 세번째 hyperparameter
• minimum node size (terminal node의 data수) : classification 1, regression 5 (R randomForest PKG의 기본 값)

각각의 배깅된 트리는 평균적으로 관측치들의 약 2/3을 이용. ''5장 2번 연습문제?''
limit 설명
각 Bootstrap 표본의 개수가 n 일 때, j번째 관측치가 Bootstrap 표본에 있지 않을 확률은 $ (1-1/n)^n $
$ (1-1/n)^n \to 1/e $
나머지 1/3을 Out-Of-Bag (OOB) 관측치 → OOB에 대한 오차. → B가 충분히 큰 경우 OOB오차는 LOOCV 오차와 사실상 동일

• by random permutation (p번 더 계산) : OOB prediction (j-th 변수 random permutation 후 prediction → tree들의 MSE차이의 평균)
• 회귀트리들을 배깅하는 경우, 주어진 설명변수에 대한 분할 때문에 RSS가 감소되는 총량을 모든 B개 트리에 대해 평균한 값. 분류는 지니 지수가 감소되는 총량의 평균.

Random Seed 따라 결과 값이 달라질 수 있다.
변수의 수가 늘어나면, 특히 예측과 크게 상관없는 변수들이 많으면, 성능 저하
학습 뿐 아니라, 실제 예측 시간. Many Tree 계산 필요
High Dimension, Sparse Data (text) 에 약함

adaptive nearest-neighbor estimator 로 해석될 수 있음