이번 포스팅에서는 앙상블 기법의 하나인 배깅(Bagging)에 대해서 알아보고자 한다. 여기서 다루는 내용은 다음과 같다.
- 목차 -
본 포스팅에서는 수식을 포함하고 있습니다.
티스토리 피드에서는 수식이 제대로 표시되지 않을 수 있으니
PC 웹 브라우저 또는 모바일 웹 브라우저에서 보시기 바랍니다.
배깅(Bagging)이란 무엇인가?
1. 정의
배깅(Bagging)은 Bootstrap Aggregating의 준말로 다음과 같이 정의할 수 있다.
배깅(Bagging)은 붓스트랩(Bootstrap) 샘플링을 이용하여 주어진 하나의 데이터로 학습된 예측 모형보다 더 좋은 모형을 만들 수 있는 앙상블 기법이다.
이 말의 뜻을 하나하나 살펴보자.
a. 배깅(Bagging)은 붓스트랩(Bootstrap) 샘플링을 이용한 앙상블 기법이다.
먼저 학습데이터학습 데이터 $L=\{(x_i, y_i) | i=1, \ldots, n \}$가 있다고 하자. 이때 학습 데이터 $L$에 대하여 붓스트랩(Bootstrap) 샘플링을 수행하여 $B$개의 붓스트랩 샘플 데이터 셋($L_1, L_2, \ldots, L_B$)을 만들게 된다. $L_b, \;(b=1, \ldots, B)$ 가 갖고 있는 데이터 개수 $n$이며 $L$과 같다. 배깅은 각 셋에 대하여 학습한 모형 $\phi(x, L_b),\; (b=1, \ldots, B)$ 을 얻게 되고 각 모형의 결과를 집계(Aggregation)하는 앙상블 기법인 것이다.
배깅에서 집계 방식은 회귀 문제인 경우
$$\phi_B(x) = \frac{1}{B}\sum_{b=1}^B\phi(x, L_b)$$
분류인 경우
$$ \phi_B(x) = \text{Mode}\;\; \phi(x, L_b)$$
이다. 여기서 $\text{Mode}$는 최빈값을 나타낸다.
아래 그림은 배깅의 과정을 나타낸 것이다.
b. 배깅으로 만든 예측 모형이 주어진 데이터 하나로 학습할 때보다 더 좋은 성능을 낼 수 있다.
배깅은 일반적으로 하나의 원래 학습 데이터 하나 가지고 만든 예측 모형보다 좋은 성능을 낼 수 있다. 특히 회귀 문제에서는 평균 제곱 오차(Mean Squared Error)를 계산하여 이를 확인해볼 수 있다.
학습 데이터 $L$안에 개별 샘플 $(x, y)$가 확률분포 $P$로부터 독립적으로 생성되었다고 하자. 여기서 $y$는 연속형 실수이다. 이때 $L$을 이용한 예측 모형을 $\phi(x, L)$이라 하고 $\phi_A(x) = E_L\phi(x, L)$라 하자. 이때 $\phi_A(x)$의 추정치는 $\phi_B(x)$라 할 수 있다.
이제 $(x, y)$를 고정시키고 평균 제곱 오차(Mean Squared Error)를 계산하면 다음과 같다.
$$E_L(y-\phi(x, L))^2 = y^2-2yE_L\phi(x, L)+E_L\phi^2(x, L)\tag{1}$$
이때 젠센 부등식(Jensen's Inequality)을 통해 $E_L\phi^2(x, L) \geq (E_L\phi(x, L))^2$임을 이용하면 (1)은 다음과 같이 정리할 수 있다.
$$E_L(y-\phi(x, L))^2 \geq (y-\phi_A(x))^2\tag{2}$$
위쪽 양변 기대값 $E_P$를 취하면 $\phi_A(x)$의 평균 제곱 오차가 원래 학습 데이터 하나 가지고 만든 예측 모형(단독 모형이라 하겠다)의 평균 제곱 오차보다 작다는 것을 알 수 있다. $\phi_A(x)$의 추정치는 $\phi_B(x)$라 할 수 있으므로 배깅을 이용한 예측 모형의 평균 제곱 오차가 단독 모형의 평균 제곱 오차보다 작다는 것을 추측할 수 있다.
분류 문제인 경우 성능 측도로 0-1 손실 함수를 고려하는데 위와 같이 나타낼 수 없다. 하지만 Breiman은 좋은 분류기를 가지고 배깅 분류기를 만들면 단독 분류기보다 성능이 더 좋아질 수 있다고 했다.
2. 배깅(Bagging)의 특징
a. 불안정한 모형일수록 더 좋은 성능을 발휘한다.
배깅(Bagging)은 불안정한 모형일 수록 더 좋은 모형을 만들어낼 수 있다. 회귀 문제에서는 (2)를 통하여 배깅의 성능이 일반적으로 좋다는 것을 알아보았다. 이때 성능 향상이 얼마나 되는지는 위에서 증명할 때 사용된 젠센 부등식(Jensen's Inequality)
$$E_L\phi^2(x, L) \geq (E_L\phi(x, L))^2\tag{3}$$
에서 좌변이 우변보다 얼마나 차이가 나는가에 달려있다. 즉, $E_L\phi^2(x, L)$이 $(E_L\phi(x, L))^2$ 보다 많이 크다면 그만큼 성능 향상이 있다는 것이다. 이때 (3)을 다시 쓰면 아래와 같다.
$$0\leq E_L\phi^2(x, L) - (E_L\phi(x, L))^2 = \text{Var}_L(\phi(x, L)) \tag{4}$$
$E_L\phi^2(x, L)$이 $(E_L\phi(x, L))^2$ 보다 많이 크다는 것은 (4)을 통해 $\phi(x, L)$의 분산이 크다는 것이고 이는 학습 데이터 $L$의 약간 변화할 때$\phi(x, L)$의 변동이 크다는 것을 의미한다. 이는 곧 모형이 불안정하다는 뜻이며 배깅의 성능 향상을 도모할 수 있음을 의미한다.
Breiman은 분류 문제에서도 보통은 불안정한 분류기를 배깅(Bagging) 한다면 성능 향상을 도모할 수 있다고 하며 안정적인 분류기를 배깅하는 것은 좋은 아이디어가 아니라고 했다.
사실 배깅의 대상이 되는 기본 학습기(Base Learner)에 제약이 없지만 의사결정나무(Decision Tree)와 같은 불안정한 모형이 배깅으로 인한 성능 효과가 더 좋을 수 있다. 그래서 내 상사님이 알려주시길 기본 학습기로 의사결정나무를 선호하는 것 같다고 이야기해주셨다.
b. 편의(Bias)는 유지하면서 분산(Variance)을 줄인다.
배깅은 (회귀 문제에서) 평균 제곱 오차(Mean Squared Error : MSE)가 단독 모형의 MSE보다 작다고 했다. 일반적으로 MSE는 모형의 편향과 분산으로 합으로 나타낼 수 있다. 이때 배깅은 단독 모형들의 평균을 취하므로 직관적으로 편의는 유지한다고 볼 수 있다. 따라서 배깅의 MSE가 줄어든다는 것은 결국 분산을 줄인다고 생각할 수 있다.
즉, 배깅은 편향(Bias)은 유지하면서 분산(Variance)을 줄인다고 할 수 있다.
c. 별도의 검증 데이터(Validation Set) 없이 Out of Bag 데이터를 Hyper Parameter를 최적화하거나 성능 검증을 할 수 있다.
학습 데이터 $L$의 붓스트랩 샘플 $L_b$는 $L$과 (당연히) 다를 수 있다. 즉, $L$ 포함된 데이터가 $L_b$에 포함되지 않을 수 있는 것이다. 이때 $L - L_b = L\cap L_b^c$를 Out of Bag(OOB) 데이터라고 한다. 이때 Out of Bag 데이터가 얼마나 많을지 궁금할 수 있다.
문제를 단순화하여 알아보자. $L=\{1, \ldots, n \}$에서 $n$개를 복원 추출한 붓스트랩 샘플을 $S = {s_1, \ldots, s_n}$라 하자. 이때 Out of Bag 데이터의 비율을 알기 위해서는 고정된 $m \in \{1, \ldots, n\}$에 대하여 아래의 확률을 계산해야 한다.
$$\begin{align} P(m\in L-S ) &= P(m \notin S) \\ &= P(m \neq s_i \;\;\forall i ) \\ &= \prod_{i=1}^n P(m \neq s_i) \\ &= \left(1-\frac{1}{n}\right)^n \\ &\approx e^{-1} \end{align}$$
즉, 각 붓스트랩 샘플에 대해서 OOB 데이터의 비율은 $e^{-1}\sim 0.368$이고 반대로 원래의 학습 데이터를 포함하는 비율은 $1-e^{-1}\sim 0.632$인 것이다. 이는 모의실험을 통해서도 확인할 수 있다. 아래 파이썬 코드는 $n$의 크기에 따른 OOB 데이터의 비율을 계산하여 그래프로 나타낸 것이다.
import numpy as np
import random
import matplotlib.pyplot as plt
from tqdm import tqdm
random.seed(100)
sample_size = np.linspace(1, 1000, 1000, endpoint=True)
ratio_list = []
for n in tqdm(sample_size, total=len(sample_size)):
lst = range(int(n)) ## original data
bs = random.choices(lst, k = len(lst)) ## boostrap sample data
ratio = len(set(lst)-set(bs))/len(lst)
ratio_list.append(ratio)
fig = plt.figure(figsize=(12,6))
fig.set_facecolor('white')
ax = fig.add_subplot()
ax.plot(sample_size, ratio_list, marker='o', markersize=5)
ax.axhline(np.exp(-1), color='red', linestyle='--')
ax.set_xlabel('Sample Size')
plt.show()
위 그래프에서 빨간 점선은 $e^{-1}$을 나타낸다. 보는 바와 같이 $n$이 커질수록 OOB 데이터 비율은 $e^{-1}$에 수렴하는 것을 알 수 있다.
이를 통해 알 수 있는 것은 한 붓스트랩 샘플에 대해서 36.8%의 데이터를 버리는 셈이 된다는 것이다. 그렇다면 이 데이터를 이용할 수 없을까?
-> 있다.
일종의 성능 지표(테스트 셋이 아닌 검증 데이터 용도)로 사용할 수 있다. 어떻게 활용되는지 살펴보자.
OOB의 활용
$b=1, \ldots, B$에 대하여 $O_b = L-L_b$라 하자. 붓스트랩 샘플 $L_b$를 이용하여 학습한 예측 모형을 $\phi(x, L_b)$라 하자. 이때 $(x, y) \in O_b$을 이용하여 성능 지표를 $e_b$ 계산한다. 회귀의 경우 평균 잔차 제곱, 분류 문제에서는 오분류율이 될 수 있을 것이다.
이제 성능 지표의 평균
$$\bar{e} = \frac{1}{B}\sum_{b=1}^Be_b$$
을 배깅을 통해 얻어진 모형의 성능 지표로 활용한다.
아래 그림은 이러한 과정을 나타낸 것이다.
이러한 성능 지표는 Hyper Parameter를 최적화할 때 사용할 수 있다. 예를 들어 붓스트랩 샘플 개수 $B$를 정한다거나 기본 학습기(Base Learner)가 의사결정나무인 경우 최대 깊이를 정한다거나 하는 것처럼 말이다.
d. 배깅에서는 가지치기가 필요 없다.
앞의 a, b를 종합하면 배깅에서 개별 모형은 편의가 작고 분산이 클수록(불안정성이 클수록) 배깅으로 인한 성능 향상이 커진다는 것을 알 수 있다. 기본 학습기(Base Learner)를 의사결정나무(Decision Tree)로 한다고 생각해보자. 의사결정나무 깊이가 깊어질수록 편의는 작아지지만 분산이 커진다. 따라서 이 자체로 배깅에 유리한 개별 모형이기 때문에 이를 추가적으로 가지치기할 필요가 없어지는 것이다.
3. 그밖에 고려 사항
배깅에서 정해야할 것 중 하나가 붓스트랩 샘플들의 개수(Bootstrap Replicates) $B$일 것이다. OOB를 통하여 $B$를 Hyper Parameter로 놓고 최적화된 $B$를 선택할 수도 있을 것이다. Breiman은 회귀 문제에서는 $B$가 클 필요가 없다고 한다(문맥상 50개 이하인 듯하다).그리고 분류 문제에서는 클래스의 개수가 늘어날 수록 $B$도 크게 하는 것이 좋다고 감각적으로 추측했다. 또한 임계점을 지나고 나서는 $B$를 크게 늘려도 성능 향상이 더 이상 일어나지 않음을 보였다.
4. 장단점
- 장점 -
a. 배깅(Bagging)은 유연하다.
배깅에서 사용할 수 있는 기본 학습기의 종류에는 제한이 없다. 즉, 의사결정나무(Decision Tree) 이 외에도 분류 문제인 경우 로지스틱 회귀 모형, 회귀 문제인 경우 선형 회귀 모형이나 Nearest Neighbor 방법을 써도 좋다.
b. 별도의 검증 데이터 없이 Hyper Parameter를 최적화하거나 성능 평가 가능.
OOB 데이터를 이용하면 굳이 학습 데이터를 쪼개지 않더라도 배깅 모형의 성능을 평가나 Hyper Parameter를 최적화할 수 있다.
c. 구현이 어렵지 않다.
배깅 알고리즘이 어렵지 않아서 구현이 쉬운 편에 속한다.
d. 불안정성 모형을 기본 학습기로 사용하는 경우 성능을 크게 향상할 수 있다.
- 단점 -
a. 해석이 어렵다.
배깅도 앙상블 기법으로써 앙상블의 고질적인 단점은 바로 해석이 어렵다는 것이다.
b. 성능 향상을 항상 보장하는 것은 아니다.
안정적인 모형(예 : Nearest Neighbor)에 대해서는 성능 향상이 어려울 수 있다
배깅(Bagging) 알고리즘
배깅의 알고리즘을 정리하면 다음과 같다.
Algorithm
1. 학습 데이터 $L$, 기본 학습기 $\phi$, 붓스트랩 샘플들의 개수 $B$를 설정한다.
2. $b=1, \ldots, B$에 대하여 (a)~(c)를 반복한다.
(a) 붓스트랩 샘플 $L_b$를 생성한다. 그리고 OOB 데이터 $O_b = L-L_b$를 보관해둔다.
(b) $L_b$를 이용하여 모형 $\phi(x, L_b)$를 학습한다.
(c) $O_b$를 이용하여 성능 지표 $e_b$를 계산한다.
3. 집계(Aggregation)하여 최종 배깅 모형 $\phi(x)$를 만든다. 회귀 문제인 경우
$$\phi(x) = \frac{1}{B}\sum_{b=1}^B\phi(x, L_b)$$
분류 문제인 경우
$$ \phi_B(x) = \text{Mode}\;\; \phi(x, L_b)$$
가 된다. 만약 동률의 클래스가 여러개 나온다면 그 중에서 임의로 또는 라벨 번호가 가장 작은 클래스로 할당한다. 그리고 배깅 모형의 성능 지표
$$\bar{e} = \frac{1}{B}\sum_{b=1}^Be_b$$
를 계산한다.
3. 예제
위 알고리즘을 예제를 통해 알아보자. 여기에서는 회귀 문제만 알아볼 것이며 분류 문제도 비슷하므로 이 예제 하나만 알면 된다.
1. 학습 데이터 $L$, 기본 학습기 $\phi$, 붓스트랩 샘플들의 개수 $B$를 설정한다.
여기서는 연 독서량과 컴퓨터 사용시간에 따른 수학 성적을 예측하는 문제를 생각해보겠다. 데이터는 아래와 같고 기본 학습기는 깊이가 1인 의사결정나무, 붓스트랩 샘플 셋 개수 $B=2$라고 하자.
2. $b=1, \ldots, B$에 대하여 (a)~(c)를 반복한다.
(a) 붓스트랩 샘플 $L_b$를 생성한다. 그리고 OOB 데이터 $O_b = L-L_b$를 보관해둔다.
데이터 개수가 5개이므로 학습데이터로부터 5개를 복원 추출한다. 또한 OOB 데이터도 보관해둔다.
$B=2$이므로 이를 두번 해야한다.
이제 두개의 붓스트랩 샘플 $L_1, L_2$, 두개의 OOB 데이터가 만들어졌다.
(b) $L_b$를 이용하여 모형 $\phi(x, L_b)$를 학습한다.
(c) $O_b$를 이용하여 성능 지표 $e_b$를 계산한다.
이제 각 붓스트랩 샘플에 대해서 의사결정나무를 학습하고 이에 해당하는 OOB 데이터를 이용하여 학습한 의사결정나무의 성능을 평가한다. 아래 그림에서는 잔차제곱평균을 성능 지표로 사용했다.
3. 집계(Aggregation)하여 최종 배깅 모형 $\phi(x)$를 만든다.
최종 배깅 모형은 다음과 같다.
$$\phi(x) = \frac{1}{2}\sum_{b=1}^2\phi(x, L_b)$$
만약 연 독서량이 10권, 일컴퓨터 사용시간이 2시간인 경우, 수학 성적을 배깅 모형으로 예측하면 다음 그림과 72.25인 것을 알 수 있다.
그리고 OOB를 이용한 최종 배깅 모형의 성능은 다음과 같이 계산된다.
$$\bar{e} = \frac{1}{2}\sum_{b=1}^2 e_b= \frac{382.50+40.63}{2} = 211.57$$
이번 포스팅을 준비하면서 배깅에 대해서 어렴풋이 알고 있었던 것을 가슴 깊이 새기게 되었다.
참고자료
1. Bagging Predictors - Leo Breiman
2. R을 이용한 데이터 마이닝 - 박창이, 김용대, 김진석, 송종우, 최호식
'통계 > 머신러닝' 카테고리의 다른 글
| 25. Shapley Value와 SHAP에 대해서 알아보자 with Python (15) | 2022.08.25 |
|---|---|
| 24. 랜덤 포레스트(Random Forest)에 대해서 알아보자 (2) | 2022.08.05 |
| 22. 로지스틱 회귀(Logistic Regression)에 대해서 알아보자. (0) | 2022.07.03 |
| 21. XGBoost에 대해서 알아보자 (0) | 2022.06.26 |
| 20. Gradient Boosting 알고리즘에 대해서 알아보자 with Python (3) | 2022.06.13 |
댓글