배깅(Bagging)
19 Mar 2021 | Machine-Learning
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
Bagging
이번 게시물에서는 앙상블의 방법 중 하나인 배깅(Bagging, Bootstrap aggregating)에 대해서 알아보도록 하겠습니다. 앙상블의 목적은 여러 모델을 결합시켜 다양성을 확보하기 위함입니다. 다양성을 확보하는 방법에는 ‘데이터셋을 다양화하기’와 ‘모델을 다양화하기’의 2가지 방법이 있습니다. 이 중 배깅은 전자에 해당하는 ‘데이터셋을 다양화하기’에 속하는 방법입니다.
Bootstrap
배깅의 풀네임은 Bootstrap aggregating 입니다. 말 그대로 부트스트랩(Bootstrap)을 통해서 다양한 데이터셋을 만들고 이를 학습시킨 모델을 모으는(Aggregating) 방법이지요. 먼저 부트스트랩에 대해서 알아보도록 하겠습니다.
Sampling with replacement
부트스트랩은 모집단으로부터 표본을 추출하는 방식입니다. 중요한 특징은 복원 추출(Sampling with replacement)을 한다는 점인데요. 아래 그림을 보며 설명을 이어나가도록 하겠습니다.
이미지 출처 : stats.stackexchange.com
원래 데이터셋으로부터 3회 부트스트래핑한 결과를 나타낸 이미지입니다. 표본 집단의 크기는 모집단의 크기와 같습니다. 위처럼 모집단의 크기가 5라면 표본 집단의 크기가 5가 되지요. 각 인스턴스는 균일한(uniformly) 확률로 선택됩니다. 그러다 보니 어떤 인스턴스는 중복되어 선택될 수도 있고, 어떤 인스턴스는 선택되지 못할 수도 있습니다. 가장 오른쪽 부트스트랩 결과를 보면 파랑색, 보라색으로 표시된 인스턴스는 중복되어 선택되었습니다. 노랑과 초록으로 표시된 인스턴스는 선택되지 못했네요.
OOB
각 부트스트랩에서 선택되지 못한 인스턴스를 OOB(Out of Bag)라고 합니다. 특정 인스턴스가 OOB가 될 확률은 아래 식을 통해 구할 수 있습니다.
\[p = \bigg(1-\frac{1}{N}\bigg)^N\]
$N$ 이 커질수록 아래의 식에 의해서 이 값은 약 $37\%$ 정도에 가까워집니다.
\[\begin{aligned}
\lim_{N \rightarrow 0}\bigg(1-\frac{1}{N}\bigg)^N &= \lim_{N \rightarrow 0}\bigg[\bigg(1-\frac{1}{N}\bigg)^{-N}\bigg]^{-1} \\
&= e^{-1} \qquad \bigg(\because e = \lim_{n \rightarrow 0}\bigg(1+\frac{1}{n}\bigg)^n \bigg) \\
&= 0.3679
\end{aligned}\]
즉 $N$이 일정 수준 이상으로 커지면 매 표본집단에 모집단의 약 $2/3$는 포함되고, 나머지 $1/3$ 은 OOB가 됩니다. OOB는 각 모델의 학습 데이터로 사용되지 않으므로 따로 빼두었다가 검증 데이터로 사용하게 됩니다.
Effect
부트스트랩은 데이터의 분포를 변형하는 효과가 있습니다. 원래 데이터의 노이즈 $\epsilon$ 가 특정 분포를 따르고 있다면 이를 통해 만드는 모델은 분포에 종속될 수 밖에 없는데요. 부트스트랩을 통해 분포를 다양하게 만들어 주면 특정 분포에 종속된 모델이 만들어지는 것을 방지함으로써 다양성을 확보할 수 있습니다.
게다가 OOB 데이터를 검증에 사용하면 모든 샘플을 학습과 검증에 활용하여 높은 검증력을 확보할 수 있다는 효과도 있습니다.
Learning
지도학습 알고리즘이라면 어떤 것도 배깅에 적용할 수 있습니다. 하지만 배깅의 목적이 데이터셋을 다양화하여 분산(Variance)을 줄이기 위함이기에 일반적으로는 복잡도(Complexity)가 높은 모델을 선택합니다. 복잡도가 높은 모델은 분산에 의한 오차가 높기 때문에 배깅을 적용했을 때 의미있는 성능 향상 확률이 높기 때문입니다. 복잡도가 높은 모델로는 의사 결정 나무(Decision Tree), 인공 신경망(ANN), 서포트 벡터 머신(SVM) 등이 있습니다.
Result Aggregating
학습이 끝났으니 이제 결과를 취합할(Aggregating) 차례입니다. 수많은 취합 방법이 있지만 본 게시물에서는 대표적인 3가지를 알아보도록 하겠습니다.
Majority Voting
첫 번째는 가장 간단한 방법인 다수결(Majority voting) 입니다. $N$개의 모델 중에서 가장 많이 선택된 레이블을 최종 결과로 도출합니다. 레이블이 ${0,1}$ 인 이진 분류일 때 다수결 방식을 수식으로 나타내면 아래와 같습니다.
\[\hat{y}_\text{Ensemble} = \underset{i}{\mathrm{argmax}} \bigg(\sum^n_{i=1} \delta(\hat{y}_j = i), i \in {0,1} \bigg)\]
아래는 $N=10$ 일 때의 결과를 예를 들어 나타내었습니다. 가장 왼쪽은 OOB를 사용하여 얻어낸 검증 정확도(Validation accuracy), 3번째는 테스트 인스턴스의 레이블을 1로 판단할 확률입니다. 이 값이 임계값(threshold)인 $0.5$ 를 넘길 경우 1로 레이블링합니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
다수결을 적용하여 결과를 취합하면 1로 레이블링한 모델은 1,2,3,6,9,10 으로 6개이며 0으로 레이블링한 모델은 4,5,8,9 로 4개가 되어 최종 결과는 더 많은 $(6 > 4)$ 1로 결정됩니다.
Weighted Voting (at Validation Accuracy)
두 번째는 검증 정확도에 가중치를 두어 투표(Weighted voting)하는 방법입니다. 기본적인 아이디어는 ‘검증 정확도가 높은 모델이 테스트 데이터에 대해서도 잘 판단할 것’에서 시작되었습니다. 가중치 투표 방식을 수식으로 나타내면 아래와 같습니다.
\[\hat{y}_\text{Ensemble} = \underset{i}{\mathrm{argmax}} \bigg(\frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = i)}{\sum^n_{i=1} (\text{Val_Acc}_j)}, i \in {0,1} \bigg)\]
위에서 사용했던 예시에 가중치 투표를 적용해보겠습니다. $j$ 번째 모델의 검증 정확도에 가중치를 부여합니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
검증 정확도에 가중치를 두어 값을 구하면 다음과 같습니다.
\[\begin{aligned}
\frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = 1)}{\sum^n_{i=1} (\text{Val_Acc}_j)} = \frac{4.69}{8.14} &=0.576 \\
\frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = 0)}{\sum^n_{i=1} (\text{Val_Acc}_j)} = \frac{3.45}{8.14} &=0.424
\end{aligned}\]
위 계산의 결과에서 레이블 1일 때의 값이 더 크기 때문에 $(0.576 > 0.424)$ 최종 결과를 1로 레이블링합니다. 위 예시에서는 다수결과 가중치 투표 방식의 결과가 동일합니다. 하지만 만약 1로 레이블링한 6개 모델의 검증 정확도가 $(0.51, 0.63, 0.54, 0.55, 0.62, 0.55)$이고, 0으로 레이블링한 4개 모델의 검증 정확도가 $(0.91, 0.89, 0.93, 0.94)$ 라면 결과가 달라집니다. 다수결로는 6개 모델이 선택한 1을 최종 레이블로 결정하게 되지만, 가중치 투표 결과는 아래와 같이 $(0.481 < 0.519)$ 가 되어 0을 최종 레이블로 결정합니다.
\[\begin{aligned}
\frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = 1)}{\sum^n_{i=1} (\text{Val_Acc}_j)} = \frac{3.40}{7.07} &=0.481 \\
\frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = 0)}{\sum^n_{i=1} (\text{Val_Acc}_j)} = \frac{3.67}{7.07} &=0.519
\end{aligned}\]
Weight voting (at Predicted probability)
세 번째는 테스트의 인스턴스의 레이블을 판단하는 확률에 가중치를 두는 방식입니다. 각 모델의 검정력은 동일하다고 보되 ‘더 강하게 주장하는 모델의 결과에 가중치를 주자’라는 아이디어에서 시작되었습니다. 이 방법을 수식으로 나타내면 다음과 같습니다.
\[\hat{y}_\text{Ensemble} = \underset{i}{\mathrm{argmax}} \bigg(\frac{1}{n}\sum^n_{i=1} P(y_j = i), i \in {0,1} \bigg)\]
위에서 사용했던 예시에 가중치 투표를 적용해보겠습니다. $j$ 번째 모델의 확률에 가중치를 부여합니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
가중치 투표를 사용하여 값을 구하면 다음과 같습니다. 레이블을 0으로 판단할 확률은 1에서 각 확률을 빼준 값입니다.
\[\begin{aligned}
\frac{1}{n}\sum^n_{i=1} P(y_j = 1) = \frac{1}{10} (6.25) &= 0.625 \\
\frac{1}{n}\sum^n_{i=1} P(y_j = 0) = \frac{1}{10} (3.75) &= 0.375
\end{aligned}\]
이 값이 레이블이 1일 때가 더 크므로 $(0.625 > 0.375)$ 최종 레이블을 1로 판단합니다.
Selection?
결과 취합 방법에는 위에서 소개한 3가지 외에도 수많은 방법이 존재합니다. 한 가지 예를 들면, 검증 데이터와 예측 레이블 확률 모두에 가중치를 두어 곱할 수도 있지요. 그렇다면 어떤 방법을 선택하는 것이 좋을까요? ‘공짜 점심은 없다’ 이론은 여기에도 적용됩니다. 절대적으로 좋은 결과 취합 방법이 없다는 말이지요. 경우에 따라 적절한 취합 방법을 선택해야 합니다.
캐글과 같은 경진대회(Competition)에서는 더 높은 성능을 위하여 스태킹(Stacking)이라는 방법을 선택하기도 합니다. 스태킹이란 결과 취합을 위한 분류기(Meta-classifier)를 추가하는 방식입니다. 데이터셋 $\mathbf{x}$ 를 부트스트랩 하여 만들어낸 데이터셋으로 학습한 결과값이 $f_1(\mathbf{x}),f_2(\mathbf{x}), \cdots, f_B(\mathbf{x})$ 라고 하겠습니다. 추가적인 분류기는 이 결과값을 받아 최종 레이블 $\hat{y}$ 를 내는 함수 $g(f_1(\mathbf{x}),f_2(\mathbf{x}), \cdots, f_B(\mathbf{x}))$ 이며, 이 값이 정답 레이블 $y$ 와 같아지도록 학습합니다.
이미지 출처 : www.researchgate.net
Conclusion
부트스트랩을 통해 다양한 데이터셋을 만들어 다양성을 확보하는 앙상블 방법인 배깅에 대해서 알아보았습니다. 다음 게시물에서는 의사 결정 나무를 기본 모델로 하여 배깅과 랜덤 변수 선택법을 적용한 랜덤 포레스트(Random forest)에 대해서 알아보도록 하겠습니다.
해당 게시물은 고려대학교 강필성 교수님의 강의를 바탕으로 작성한 것입니다.
Bagging
이번 게시물에서는 앙상블의 방법 중 하나인 배깅(Bagging, Bootstrap aggregating)에 대해서 알아보도록 하겠습니다. 앙상블의 목적은 여러 모델을 결합시켜 다양성을 확보하기 위함입니다. 다양성을 확보하는 방법에는 ‘데이터셋을 다양화하기’와 ‘모델을 다양화하기’의 2가지 방법이 있습니다. 이 중 배깅은 전자에 해당하는 ‘데이터셋을 다양화하기’에 속하는 방법입니다.
Bootstrap
배깅의 풀네임은 Bootstrap aggregating 입니다. 말 그대로 부트스트랩(Bootstrap)을 통해서 다양한 데이터셋을 만들고 이를 학습시킨 모델을 모으는(Aggregating) 방법이지요. 먼저 부트스트랩에 대해서 알아보도록 하겠습니다.
Sampling with replacement
부트스트랩은 모집단으로부터 표본을 추출하는 방식입니다. 중요한 특징은 복원 추출(Sampling with replacement)을 한다는 점인데요. 아래 그림을 보며 설명을 이어나가도록 하겠습니다.
이미지 출처 : stats.stackexchange.com
원래 데이터셋으로부터 3회 부트스트래핑한 결과를 나타낸 이미지입니다. 표본 집단의 크기는 모집단의 크기와 같습니다. 위처럼 모집단의 크기가 5라면 표본 집단의 크기가 5가 되지요. 각 인스턴스는 균일한(uniformly) 확률로 선택됩니다. 그러다 보니 어떤 인스턴스는 중복되어 선택될 수도 있고, 어떤 인스턴스는 선택되지 못할 수도 있습니다. 가장 오른쪽 부트스트랩 결과를 보면 파랑색, 보라색으로 표시된 인스턴스는 중복되어 선택되었습니다. 노랑과 초록으로 표시된 인스턴스는 선택되지 못했네요.
OOB
각 부트스트랩에서 선택되지 못한 인스턴스를 OOB(Out of Bag)라고 합니다. 특정 인스턴스가 OOB가 될 확률은 아래 식을 통해 구할 수 있습니다.
\[p = \bigg(1-\frac{1}{N}\bigg)^N\]$N$ 이 커질수록 아래의 식에 의해서 이 값은 약 $37\%$ 정도에 가까워집니다.
\[\begin{aligned} \lim_{N \rightarrow 0}\bigg(1-\frac{1}{N}\bigg)^N &= \lim_{N \rightarrow 0}\bigg[\bigg(1-\frac{1}{N}\bigg)^{-N}\bigg]^{-1} \\ &= e^{-1} \qquad \bigg(\because e = \lim_{n \rightarrow 0}\bigg(1+\frac{1}{n}\bigg)^n \bigg) \\ &= 0.3679 \end{aligned}\]즉 $N$이 일정 수준 이상으로 커지면 매 표본집단에 모집단의 약 $2/3$는 포함되고, 나머지 $1/3$ 은 OOB가 됩니다. OOB는 각 모델의 학습 데이터로 사용되지 않으므로 따로 빼두었다가 검증 데이터로 사용하게 됩니다.
Effect
부트스트랩은 데이터의 분포를 변형하는 효과가 있습니다. 원래 데이터의 노이즈 $\epsilon$ 가 특정 분포를 따르고 있다면 이를 통해 만드는 모델은 분포에 종속될 수 밖에 없는데요. 부트스트랩을 통해 분포를 다양하게 만들어 주면 특정 분포에 종속된 모델이 만들어지는 것을 방지함으로써 다양성을 확보할 수 있습니다.
게다가 OOB 데이터를 검증에 사용하면 모든 샘플을 학습과 검증에 활용하여 높은 검증력을 확보할 수 있다는 효과도 있습니다.
Learning
지도학습 알고리즘이라면 어떤 것도 배깅에 적용할 수 있습니다. 하지만 배깅의 목적이 데이터셋을 다양화하여 분산(Variance)을 줄이기 위함이기에 일반적으로는 복잡도(Complexity)가 높은 모델을 선택합니다. 복잡도가 높은 모델은 분산에 의한 오차가 높기 때문에 배깅을 적용했을 때 의미있는 성능 향상 확률이 높기 때문입니다. 복잡도가 높은 모델로는 의사 결정 나무(Decision Tree), 인공 신경망(ANN), 서포트 벡터 머신(SVM) 등이 있습니다.
Result Aggregating
학습이 끝났으니 이제 결과를 취합할(Aggregating) 차례입니다. 수많은 취합 방법이 있지만 본 게시물에서는 대표적인 3가지를 알아보도록 하겠습니다.
Majority Voting
첫 번째는 가장 간단한 방법인 다수결(Majority voting) 입니다. $N$개의 모델 중에서 가장 많이 선택된 레이블을 최종 결과로 도출합니다. 레이블이 ${0,1}$ 인 이진 분류일 때 다수결 방식을 수식으로 나타내면 아래와 같습니다.
\[\hat{y}_\text{Ensemble} = \underset{i}{\mathrm{argmax}} \bigg(\sum^n_{i=1} \delta(\hat{y}_j = i), i \in {0,1} \bigg)\]아래는 $N=10$ 일 때의 결과를 예를 들어 나타내었습니다. 가장 왼쪽은 OOB를 사용하여 얻어낸 검증 정확도(Validation accuracy), 3번째는 테스트 인스턴스의 레이블을 1로 판단할 확률입니다. 이 값이 임계값(threshold)인 $0.5$ 를 넘길 경우 1로 레이블링합니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
다수결을 적용하여 결과를 취합하면 1로 레이블링한 모델은 1,2,3,6,9,10 으로 6개이며 0으로 레이블링한 모델은 4,5,8,9 로 4개가 되어 최종 결과는 더 많은 $(6 > 4)$ 1로 결정됩니다.
Weighted Voting (at Validation Accuracy)
두 번째는 검증 정확도에 가중치를 두어 투표(Weighted voting)하는 방법입니다. 기본적인 아이디어는 ‘검증 정확도가 높은 모델이 테스트 데이터에 대해서도 잘 판단할 것’에서 시작되었습니다. 가중치 투표 방식을 수식으로 나타내면 아래와 같습니다.
\[\hat{y}_\text{Ensemble} = \underset{i}{\mathrm{argmax}} \bigg(\frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = i)}{\sum^n_{i=1} (\text{Val_Acc}_j)}, i \in {0,1} \bigg)\]위에서 사용했던 예시에 가중치 투표를 적용해보겠습니다. $j$ 번째 모델의 검증 정확도에 가중치를 부여합니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
검증 정확도에 가중치를 두어 값을 구하면 다음과 같습니다.
\[\begin{aligned} \frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = 1)}{\sum^n_{i=1} (\text{Val_Acc}_j)} = \frac{4.69}{8.14} &=0.576 \\ \frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = 0)}{\sum^n_{i=1} (\text{Val_Acc}_j)} = \frac{3.45}{8.14} &=0.424 \end{aligned}\]위 계산의 결과에서 레이블 1일 때의 값이 더 크기 때문에 $(0.576 > 0.424)$ 최종 결과를 1로 레이블링합니다. 위 예시에서는 다수결과 가중치 투표 방식의 결과가 동일합니다. 하지만 만약 1로 레이블링한 6개 모델의 검증 정확도가 $(0.51, 0.63, 0.54, 0.55, 0.62, 0.55)$이고, 0으로 레이블링한 4개 모델의 검증 정확도가 $(0.91, 0.89, 0.93, 0.94)$ 라면 결과가 달라집니다. 다수결로는 6개 모델이 선택한 1을 최종 레이블로 결정하게 되지만, 가중치 투표 결과는 아래와 같이 $(0.481 < 0.519)$ 가 되어 0을 최종 레이블로 결정합니다.
\[\begin{aligned} \frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = 1)}{\sum^n_{i=1} (\text{Val_Acc}_j)} = \frac{3.40}{7.07} &=0.481 \\ \frac{\sum^n_{i=1} (\text{Val_Acc}_j) \cdot \delta(\hat{y}_j = 0)}{\sum^n_{i=1} (\text{Val_Acc}_j)} = \frac{3.67}{7.07} &=0.519 \end{aligned}\]Weight voting (at Predicted probability)
세 번째는 테스트의 인스턴스의 레이블을 판단하는 확률에 가중치를 두는 방식입니다. 각 모델의 검정력은 동일하다고 보되 ‘더 강하게 주장하는 모델의 결과에 가중치를 주자’라는 아이디어에서 시작되었습니다. 이 방법을 수식으로 나타내면 다음과 같습니다.
\[\hat{y}_\text{Ensemble} = \underset{i}{\mathrm{argmax}} \bigg(\frac{1}{n}\sum^n_{i=1} P(y_j = i), i \in {0,1} \bigg)\]위에서 사용했던 예시에 가중치 투표를 적용해보겠습니다. $j$ 번째 모델의 확률에 가중치를 부여합니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-IME654
가중치 투표를 사용하여 값을 구하면 다음과 같습니다. 레이블을 0으로 판단할 확률은 1에서 각 확률을 빼준 값입니다.
\[\begin{aligned} \frac{1}{n}\sum^n_{i=1} P(y_j = 1) = \frac{1}{10} (6.25) &= 0.625 \\ \frac{1}{n}\sum^n_{i=1} P(y_j = 0) = \frac{1}{10} (3.75) &= 0.375 \end{aligned}\]이 값이 레이블이 1일 때가 더 크므로 $(0.625 > 0.375)$ 최종 레이블을 1로 판단합니다.
Selection?
결과 취합 방법에는 위에서 소개한 3가지 외에도 수많은 방법이 존재합니다. 한 가지 예를 들면, 검증 데이터와 예측 레이블 확률 모두에 가중치를 두어 곱할 수도 있지요. 그렇다면 어떤 방법을 선택하는 것이 좋을까요? ‘공짜 점심은 없다’ 이론은 여기에도 적용됩니다. 절대적으로 좋은 결과 취합 방법이 없다는 말이지요. 경우에 따라 적절한 취합 방법을 선택해야 합니다.
캐글과 같은 경진대회(Competition)에서는 더 높은 성능을 위하여 스태킹(Stacking)이라는 방법을 선택하기도 합니다. 스태킹이란 결과 취합을 위한 분류기(Meta-classifier)를 추가하는 방식입니다. 데이터셋 $\mathbf{x}$ 를 부트스트랩 하여 만들어낸 데이터셋으로 학습한 결과값이 $f_1(\mathbf{x}),f_2(\mathbf{x}), \cdots, f_B(\mathbf{x})$ 라고 하겠습니다. 추가적인 분류기는 이 결과값을 받아 최종 레이블 $\hat{y}$ 를 내는 함수 $g(f_1(\mathbf{x}),f_2(\mathbf{x}), \cdots, f_B(\mathbf{x}))$ 이며, 이 값이 정답 레이블 $y$ 와 같아지도록 학습합니다.
이미지 출처 : www.researchgate.net
Conclusion
부트스트랩을 통해 다양한 데이터셋을 만들어 다양성을 확보하는 앙상블 방법인 배깅에 대해서 알아보았습니다. 다음 게시물에서는 의사 결정 나무를 기본 모델로 하여 배깅과 랜덤 변수 선택법을 적용한 랜덤 포레스트(Random forest)에 대해서 알아보도록 하겠습니다.
Comments