[Data Science] 앙상블(Ensemble) 1. 배깅(Bagging), 랜덤 포레스트(Random Forest)

Ensemble

“No Free Lunch Theorem”

‘No Free Lunch Theorem’은 간단히 말해 특정한 문제에 최적화된 알고리즘은 다른 문제에서는 그렇지 않다는 것을 수학적으로 증명한 정리이다.

성공으로 가는 지름길은 없고 어떤 알고리즘도 모든 상황에서 우월할 수 는 없다는 것을 의미한다. 즉, 우리는 문제의 목적, 데이터 형태 등을 종합적으로 고려하여 최적의 알고리즘을 선택할 필요가 있다.

Ensemble

프랑스어로 ‘함께, 동시에, 한꺼번에, 협력하여’ 등을 의미하는 부사로 머신러닝에서는 단일 알고리즘보다 여러 알고리즘을 결합하여 성능을 향상시킬 때 사용한다.

Point

1. 편향과 분산

실제 데이터는 항상 노이즈가 존재하기 때문에 지도학습의 관점에서 주어진 데이터 $\mathbf{x}$를 통해 $F^*$라는 정답함수가 존재한다고 하면, 우리가 알 수 있는 값 $y$는 항상 정답 함수 $F^(\mathbf{x})$에 $\epsilon$이 더해진 값이 된다.

그래서 모델학습은 노이즈($\epsilon$)가 첨가된 데이터셋($\mathbf{x}$)으로부터 실제 데이터 생성함수(정답함수, $F^*(\mathbf{x})$)를 추론하는 것이라고 할 수 있다.

이 모델에 의한 오류는 아래와 같이 나타낼 수 있다.

\[\begin{align} Err(\mathbf{x}_0) & = E[y-\hat{F}(\mathbf{x})|\mathbf{x}=\mathbf{x}_0]^2 \\ & = \color{blue}{[\hat{F}^*(\mathbf{x}_0)-\bar{F}(\mathbf{x}_0)]^2}+\color{red}{E[\bar{F}(\mathbf{x}_0)-\hat{F}(\mathbf{x}_0)]^2}+\sigma^2 \\ & = \color{blue}{Bias^2(\hat{F}(\mathbf{x}_0))}+\color{red}{Var(\hat{F}(\mathbf{x}_0))} + \sigma^2 \end{align}\]

즉, 모델에 의한 오류는 편향(Bias)과 분산(Variance)로 구분될 수 있다. 편향(Bias)은 실제 정답값에서 여러번 모델링으로 얻어낸 정답의 평균값을 뺀 것으로 반복적인 모델 학습 시 평균적으로 얼마나 정확한 추정이 가능한가에 대한 측정 지표이고 분산(Variance)은 반복적으로 수행했을 때의 평균값에서 개별적인 추정값을 뺀 것으로 반복적인 모델 학습 시 개별 추정이 얼마나 차이가 크게 나타나는지에 대한 측정 지표이다.

편향(Bias)는 반복적인 추정식이 평균과 얼마나 가까운가를 의미하고 분산(Variance)는 흩어진 정도를 의미한다. 분산이 높은 모델 A, B는 노이즈에 의해 추정값이 민감하고 크게 변화하는 모델이고 분산이 낮은 모델 C, D는 노이즈가 바뀌어도 추정되는 값이 크게 변하지 않는 모델이 된다.

우리는 B, C와 같은 모델을 D로 만드는 과정을 수행하게 되는데 B와 같이 편향이 낮고 분산이 높은 모델은 모델 복잡도가 높다고 표현하고 DT, ANN, SVM, k값이 작은 k-NN등이 속한다. 이런 모델들은 데이터에 민감하게 반응하며 분류 경계면을 생성하기 때문에 Overfitting 될 가능성이 높다. B → D의 과정을 Bagging이라고 한다.

C는 편향이 높고 분산이 낮은, 모델 복잡도가 낮은 모델이다. Logistic Regression, LDA, k값이 큰 K-NN 등 이 있고 Underfitting될 가능성이 있다. C → D 과정을 Boosting이라고 한다.

앙상블은 다수의 모델을 학습하여 오류의 감소를 추구한다. 그렇기 때문에 분산의 감소에 의한 오류 감소를 원할 땐 Bagging과 Bagging의 특수한 형태인 Random Forest 등을 사용하고, 편향의 감소에 의한 오류 감소를 위해선 Boosting을 사용한다.

2. 앙상블의 다양성

앙상블의 효과를 보려면 동일한 모델을 여러개 사용하는 것이 아닌 적절하게 다른 개별 모델을 사용해야한다. 개별적으로는 어느 정도 좋은 성능을 지니면서, 앙상블 내에서 각각의 모델은 서로 다양한 형태를 나타내는 것이 가상 이상적인 방법이다.

다양성을 주는 방법으로는 주어진 데이터셋을 다르게 구성하여 여러 sub training data를 구성하고 각 모델을 학습시키는 Implicit Diversity와 한 모델을 우선적으로 학습시키고 그 모델이 부족한 부분을 다른 모델을 통해 보완해나가는 Explicit Diversity가 있다.

첫번째 Implicit Diversity는 병렬처리가 가능한 Bagging이 속하고 Explicit Diversity는 병렬처리가 불가능한 Boosting이 속한다.

Bagging

Implicit Diversity에 대해 계속 나아가보면, 주어진 하나의 데이터 셋을 적잘한 조치를 취해 마치 다른 데이터 셋인 것 처럼 모델이 (긍정적으로) 착각하게 하는, 다르게 취급하도록 데이터를 부풀려서 개별적인 데이터 셋으로부터 모델을 학습시키고 최종적으로 결과물을 취합하자!는 목표를 가지고 있다.

가장 처음으로 시도 된 비복원 추출을 통한 앙상블 기법은 K-fold data split

K-fold data split은 전체 데이터를 k개의 block으로 나누고 개별 모델을 서로 다른 (k-1)개의 subset에 대해 학습한 뒤 최종 결과를 결합한다.

\[\hat{y}=\delta\Big(f_1(\mathbf{x}),f_2(\mathbf{x}), \cdots, f_{k-1}(\mathbf{x}), f_k(\mathbf{x})\Big)\]

하지만, k-fold는 임의의 두 데이터 셋을 뽑았을 때, 항상 $k-2$개의 fold가 겹치게 된다. 데이터의 많은 부분이 겹쳐서 충분한 다양성 확보가 어렵다.

Bagging은 k-fold와 비슷하게 앙상블의 각 모델은 서로 다른 학습 데이터 셋을 이용한다는 점은 동일하지만 k-fold는 비복원 추출을 사용하고 Bagging은 복원 추출을 사용한다는 데서 차이가 있다.

여기서 복원 추출로 생겨난 개별 데이터 셋을 붓스트랩(Bootstrap)이라고 하고 각 데이터 셋은 복원 추출(sampleing with replacement)을 통해 원래 데이터의 수만큼의 크기를 갖도록 샘플링한다.

동일한 객체가 반복적으로 포함될 수 있고 어떤 객체는 포함되지 않을 수 도 있다. 이러한 과정은 데이터의 분포를 임의로 왜곡시켜 다양성을 확보하고 노이즈를 주는 효과를 준다. 그렇기 때문에, 앞에서 다루었던, Bias가 큰 모형, 노이즈에 민감하게 반응하는(분산은 높고 편향이 낮은, 모델 복잡도가 높은) 모형과 잘 어울린다.

복원 추출로 bootstrap을 샘플링할 때, 이론적으로 한 개체가 하나의 bootstrap에 포함되지 않을 확률은 아래와 같다.

\[p=\left(1-\frac{1}{N}\right)^N \rightarrow \lim_{N\rightarrow\infty}\left(1-\frac{1}{N}\right)^N=e^{-1}=0.368\]

원래 데이터의 63%는 한 bootstrap에 포함되고 37%는 한번도 포함되지 않는 것을 의미하고 이렇게 포함되지 않은 데이터들을 Out of Bag Data라고 한다.

“하나의 데이터 셋이 주어지면 복원 추출을 통해서 원하는 갯수만큼의 bootstrap을 생성 → 각각의 bootstrap들에 대해 모델들이 학습 → 개별적인 모델에 test data 투입, 예측 수행 → 예측 결과 결합”

위의 과정을 통해 bootstrap을 생성하면서 다양성을 확보하고 결과 취합을 통해 핵심 아이디어를 챙긴다. 위의 사진 예시에서는 Decision Tree 모델을 사용했지만, 지도학습 알고리즘 모두 사용할 수 있다.

Result Aggregating

결과를 취합하는 방법은 여러가지가 있다. 가장 처음 생각해볼 수 있는 방법은 다수결일 것이다.

10개의 모델에 대한 훈련데이터 정확도, 새로운 데이터 $x_{new}$가 들어왔을 때 각 모델이 제시한 예측 확률과 예측범주

Majority voting은 가장 단순한 방법으로 10개의 모델들이 더 많이 예측한 범주로 결과를 내놓는 방법이다.

\[\hat{y}_{Ensemble}=\arg \max_i(\sum_{j=1}^n \delta(\hat{y}_i=i), i\in\{0, 1\})\]

하지만, 여러개의 모델들이 검증용 데이터 셋에 대해 서로 다른 퍼포먼스를 내고 있다면 과연 개별 모델에 동등한 가중치를 주는 것이 옳은 방식인가에 대한 의문을 해결하기 위해 학습 데이터 정확도에 가중치를 두어 투표하는 방식(Weighted voting)을 사용할 수 있다.

model 7은 95%의 정확도를 가지고 있고, model 6은 65%의 정확도를 가지고 있는 것을 볼 수 있다. 새로운 데이터가 들어왔을 때, model 7의 결과를 더 신뢰하는 것이 맞기에 더 큰 가중치를 부여하는 결과 취합방식이다.

\[\hat{y}_{Ensemble}=\arg \max_i(\frac{\sum_{j=1}^n(TrnAcc_j)\cdot\delta(\hat{y_i=i})}{\sum_{j=1}^n(TrnAcc_j)}, i\in\{0, 1\})\]

Majority voting과 결과는 같지만 확률이 달라졌다. 만약, 아주 작은 확률로 판별을 하는 경우라면 사용하는 방식에 따라 결과가 달라질 수 있다.

또한, test instance 정확도에 가중치를 두어 투표하는 방식을 사용할 수 도 있다. 해당하는 객체가 새로운 데이터에 대해서 얼마만큼의 강한 신뢰도를 가지고 있는가에 포커스를 둔 방식이다.

\[\hat{y}_{Ensemble}=\arg \max_i(\frac{1}{n}\sum_{j=1}^n p(y=i), i\in\{0, 1\})\]

새로운 데이터 $x_{new}$가 1번 범주일 확률을 모두 더한 평균과 0번 범주일 확률을 모두 더한 평균을 비교해 결과를 취합하는 방식이다.

결과물을 취합하는 방식은 30-40가지가 넘기 때문에, 무엇이 가장 좋은 방법인지 정해져있지 않다. 기본적으로 Majority voting을 사용하고 성능을 향상시켜나가는 방법을 사용해 볼 수 있다.

결과를 취합하는 방식의 최고봉으로는 Staking이 있다.

우리는 Bagging을 진행하면서 여러개의 모델을 학습하는 과정에서 개별 모델에 대한 개별 예측값을 알게 된다. Staking은 이 개별 예측값을 바탕으로 정답을 추정하는 방식이다. predictions이 새로운 input값이 되고 최종적으로 찾고 싶은 Final prediction인 target 둘 사이의 관계식 $f(x)$, Meta-Classifier을 찾는 방식이다.

OOB

보통은 모델링을 할 때 Data set을 training data set, validation data set, test data set으로 나눠서 training data set은 모델을 만드는데 사용하고, validation data set을 통해 Hyperparameter을 최적화 한 뒤, test data set으로 모델의 성능을 평가한다.

하지만, Bagging은 training set과 test set으로 나눈 뒤, 학습데이터로 bagging을 수행하면 bootstrap이 생성되고 OOB data가 생기게 된다. 즉, 한번도 선택되지 않은 out of bag data를 validation set으로 사용할 수 있다.

Random Forest

Random Forest는 의사결정나무 기반 앙상블의 특수한 형태이다. 앙상블 기법이기 때문에 Diversity를 확보해야하는데, Random Forest는 Bagging과 Randomly chosen predictor variables를 통해 다양성을 확보한다. 또한, 변수의 중요도를 함께 제공하는 역량도 가지고 있다.

1. Bagging

복원 추출 기법으로 원래 학습 데이터 개체 수 만큼 샘플링한다.

2. Randomly Chosen Predictor Variables

의사결정나무는 split을 할 때, 모든 변수에 대해 모든 split point를 탐색하는 과정을 통해 최적점을 찾아가지만 Random Forest는 변수를 일부로 제한한다. 전체 변수가 아닌 사전에 랜덤으로 정의된 몇 개의 변수들에 대해서만 split point를 탐색한다.

즉, 의사결정나무의 분기점을 탐색할 때, 원래 변수보다 적은 수 ($\sqrt{D}$)의 변수를 임의로 선택하여 해당 변수들만을 고려 대상으로 한다.

임의의 bootstrap i 의 변수가 25개이므로, 파란색 parent node에 대해 랜덤하게 split할 때, 전체 변수 개수인 25개를 모두 탐색하는 것이 아닌 $\sqrt{25}=5$개의 랜덤한 변수에 대해 split point 탐색이 이루어진다.

그렇게 나누어진 녹색의 child node에서는 parents node에서 사용도니 변수를 그대로 사용하는 것이 아닌 또 랜덤한 변수 5개에 대한 split point 탐색이 이루어지는 과정을 거친다.

이렇게 해도 정확성이 높은 이유는 무엇일까?

평균은 1반이 높지만 대표점수는 2반 학생들이 더 높다. 변수의 수를 제한하여 학습된 의사결정나무가 모든 변수를 사용한 의사결정나무에 비해서 1:1로 비교할 경우 정확도가 상대적으로 낮지만, 집단간 비교 시 다양성 확보로 인해 시너지 효과를 낼 수 있음을 의미한다.

Random Forest는 우리가 아직 테스트 하지 않은 데이터에 대한 일반화 오차를 계산할 수 있다. 랜덤 포레스트는 개별 의사결정나무에 대한 가지치기를 수행하지 않기 때문에 앙상블 규모가 충분히 클 경우, Random Forest의 일반화 오류를 계산할 수 있다.

\[Generalization\ Error \le \frac{\bar{\rho}(1-s^2)}{s^2}\]

$\bar{\rho}$는 개별 의사결정나무 모델들의 상관계수 평균값이고, $s^2$은 마진 함수이다. 즉, 개별적인 모델들의 상관관계가 낮을수록, 개별적인 방법론이 최대한 정확하게 예측할수록 일반화 오류율은 낮아진다.

3개의 모델 A, B, C로 구성된 Random Forest에 대한 예시를 살펴보면

• Average correlation $=0.9027$, ($A\&B\rightarrow0.8229, A\&C\rightarrow 0.9413, B\&C\rightarrow 0.9438$)
• Average margin $=0.7460$
• Generalization Error $\le 0.3074$

여기서 Generalization Error은 3개의 모델로 구성된 Random Forest에 새로운 테스트 데이터가 들어왔을 때, 가장 최악의 예측을 한다하더라도 오류율이 30%이라는 것을 의미한다.

Random Forest의 더 큰 장점은 상대적으로 높은 예측을 하는 것 뿐만 아니라 개별적인 변수의 중요도를 산출할 수 있다는 점이다. Random Forest는 다중선형 회귀분석과 로지스틱 회귀분석과 다르게 개별 변수가 통계적으로 유의한지에 대한 정보를 제공하는 대신 Random Forest는 간접적인 방식으로 변수의 중요도를 추정한다.

ramdom permutation은 수행할 때 임의로 값을 변경하는 것이 아니라 순서를 랜덤하게 변경하는 것이다. 변수 $i$가 tree를 split하는데 한번도 사용되지 않았다면, tree는 변수 %i%가 섞였는지 안 섞였는지 모르기 때문에 $e_i=p_i$가 된다.

하지만 변수 $i$가 중요하게 사용되었다면 random permutation된 데이터의 Error는 높게 나올 수 밖에 없다.

이러한 이유로 Random Forest에서 변수 중요도가 높다면, Random Forest 전-후의 OOB Error 차이가 크게 나야하며, 하나의 tree에서만 차이가 큰 것이 아닌, 모든 모델(tree)에서 차이가 균일해야 한다.

Random Forest는 예측만 잘하는 것이 아니라 그 에측을 하는 과정에서 영향을 미치는 중요 인자를 판별해서 제조업이나, 관련 도메인에서 그 인자를 따로 집중 관리하는 방식으로 개선할 수 있다.