SP24) Bagging & Boosting (Ensemble)

불성실한 막학기 학생 등장..

이 아니고 사실 복습은 꾸준히 하는데 수식 입력하는 게 너무 귀찮아서ㅜ 공책에다 손으로 했음.. 근데 곧 면접 시즌 다가오니까 전부 다 정리해서 올릴 겁니다.

 

암튼 오늘의 토픽: Bagging & Boosting!

예전에 우리가 Bias-Variance decomposition을 배운 적이 있었지요. 우리가 데이터 $D$로 만든 hypothesis의 예측과 실제값의 분산은, bias, variance, 그리고 불가피한 noise의 세 항으로 나타낼 수 있다는 내용이었어요. 여기서 bias는 예측이 실제와 얼마나 차이가 나는지를 의미하고, variance는 그 모델의 complexity를 내포해요. High bias면 모델의 예측이 꽤나 형편없다는... 거고... High variance면 모델이 상당히 복잡하기 때문에 training error는 작을지 몰라도, 데이터의 feature 값에 조금만 변화가 생겨도 예측이 크게 달라지기 때문에 —$y=x^2$과 $y=x^4$에서, $\Delta x$만큼 값이 변화했을 때 $y$에 얼마나 변화가 생기는지 생각해보기— 우리가 모델을 만들 때 지양해야 할 현상이겠지요.

근데 저 포스트의 제목을 보면 bias와 variance 사이에는 일종의 trade-off가 있다고 합니다ㅠ 그래서 이 현상을 모델의 ensemble로써 해결하고자 하는데, 그 대표적인 두 방법론이 bagging과 boosting이에요.

Bagging

Bagging은 모델의 variance를 줄이는 전략을 취합니다. 이 알고리즘을 쉽게 요약하자면, 데이터를 가지고 여러 개의 모델을 만들어서 각각의 예측을 평균내어 버리는... 아주 심플한 알고리즘입니다. 근데 이게 왜 특이하냐, 아래와 같은 특징을 가지고 있어서 그래요.

• 데이터 $D$에서 feature들을 복원추출하여 subset $D^\prime$을 $m$개 구성 <Bootsrtap>
• 모델 $h_i$를 총 $m$개 만듦
• $\overline{h(x)} = \frac{1}{m}\sum_{i}h_i(x)\qquad (*)$ 

쉽죠~.~ 근데 이게 왜 variance를 줄이는 거냐면,

\begin{equation}
\label{eq1}
\tag{1.a}
Var(\overline{(h(x)}) = \dfrac{\sum_i Var(h_i(x))}{m^2}= \dfrac{m\sigma^2}{m^2} = \dfrac{\sigma^2}{m} \quad (\because (*))
\end{equation}

사실은 모델들이 상관관계가 있기 때문에, 실제로는 딱 $K$만큼 줄어들진 않는다고는 하지만.. 아무튼 줄어들긴 한다~

 

이 대표적인 예시가 Random Forest 알고리즘이에요. Random forest는 decision tree를 bagging한 거라고 할 수 있는데요, 데이터를 샘플링할 때 feature들을 선택한다는 특징이 있습니다. 그렇다면 이때 hyperparameter는 1) decision tree를 몇 개나 만들 것인지 ($\verb|n_estimators|$), 2) 몇 개의 feature를 복원추출할 것인지 ($\texttt{max_features}$) 등이 있겠네요.

아유 간단해라

 

회귀 과제의 경우엔 평균을 취하면 되고, 분류과제일 경우엔 voting을 한다고 해요.

 

Boosting

Bagging은 variance를 줄인 거였고, noise는 불가피하댔으니.. 그럼 bias를 줄이는 전략도 있겠네요! Boosting이 바로 이 전략을 취합니다. 얘는 weighted sum인데,

\begin{equation}
\label{eq2}
\tag{1.b}
\overline{h(x)} = \sum a_ih_i(x)
\end{equation}

모델마다 일종의 가중치가 있다~ 정도로 생각할 수 있겠습니다. 이 가중치는 어떻게 계산하냐면, 한 epoch마다 데이터의 분포를 업데이트해주면서 그에 맞는 모델을 생성한다고 보면 됩니다. 이때, 그 데이터 분포로 도출된 모델의 에러를 계산해 모델에게 가중치를 부여해요. 그 가중치는 데이터의 분포를 업데이트하는 데에도 사용되구요. 

"데이터의 분포를 업데이트한다"는 말은, 분류과제의 경우에, 결과적으로는 모델이 잘못 분류한 데이터에게 높은 가중치(확률밀도?)를 부여하는 느낌이라고 보면 됩니다. 

아래와 같은 알고리즘입니다.

출처: GIST EC4213 기계학습 및 딥러닝 수업자료, by Prof 손진희 교수님

코넬 대학교의 ML수업에서 교수님은 이 알고리즘을 취객의 귀가본능..으로 설명하셨는데ㅋㅋㅋㅋ 취해서 집 가면 걸음걸음이 약간.. 똑바르지 못하잖아요? 근데 너무 오른쪽으로 많이 내디뎠다 싶으면 왼쪽 다리에 힘 빡주고 다음 걸음 내딛고, ... 하다보면 어느 새 집에 와 있는 훌륭한 모델(?)이 되어 있는.. 그런 느낌이라고ㅋㅋㅋ

정확한 표현인 것 같아요ㅋㅋ

 

---

오늘은 여기까지~