1. Bagging


1.1 Bagging 이란?

Bagging은 bootstrap aggregating의 약어로 Breiman에 의해 처음 제안된 Ensemble 기법 중 하나이다. Bagging의 구조는 비교적 단순한 편으로, 많은 수의 bootstrap sample들을 만들고 각 bootstrap sample로부터 계산된 추정치를 aggregating 하는것이다. 그렇게 함으로써 분산을 줄이는 효과가 있다. Bootstrap은 통계에서 통계량의 표본 분포를 추정하기 위해 사용하거나 일반화 정확성을 평가하기 위해 사용하지만 bagging은 prediction이나 estimation을 개선하기 위해 사용한다.

훈련 데이터 \(Z = \{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}\)에 대한 regression fit을 한다고 하면, input \(x\)에 대해 예측값 \(\hat{f}(x)\)을 얻을 수 있다. 각 bootstrap sample \(Z^{*b},\; b=1,2,...,B\)라 하면 bagging 추정량은 다음과 정의할 수 있다.

\(\hat{f}_{bag}(x) = \frac{1}{B}*\Sigma^{B}_{b=1}\hat{f^{*b}}(x).\)

Bootstrap 추정량은 \(B\rightarrow\infty\) 일수록 \(\hat{f}_{bag}(x)\rightarrow\hat{f}(x)\)이다. 즉, bootstrap sample의 수 \(B\)가 커질수록 본래의 추정량으로 수렴한다. 이는 ESL 연습문제 8.4의 간단한 증명을 통해 알 수 있다.

\((EX. 8.4)\) \(\hat{f}(x)\)를 \(B-spline \; smoother\) \(\hat{\mu}(x)\)의 추정량이라 하자. 이 추정량치 parametric bootstrap을 적용한다고 할 때, \(B\rightarrow\infty\) 일수록 bagging 추정량 \(\hat{f}_{bag}(x)\)가 본래의 추정량 \(\hat{f}(x)\)에 수렴하는지를 보여라.

\(B-spline \; smoother\)는 다음과 같은 형태로 표현할 수 있다.

\(\hat{f}(x) = S_y = H(H^TH)^{-1}H^Ty\)

이 식에서 \(S\)는 반응 변수 벡터 \(y\)가 아닌 input \(x\)의 함수이다. Parametric bootstrap을 사용하기 위해, fiiting값에 다음과 같이 noise를 추가해 준다.

\(y^*=\hat{f}(x) + \epsilon\)

위의 식을 \(B\)회 적용하고 매 반복 마다 새로운 \(y^*\)를 얻은 후 aggregating 할 것이다. \(y^*\)을 \(B-spline\)식에 대입하면 다음과 같이 쓸 수 있다.

\(\hat{f^*}(x) = S_{y^*} = S(\hat{f}(x)+\epsilon) = S^2y + S\epsilon = Sy + S\epsilon\)

\(H(H^TH)^{-1}H^TH(H^TH)^{-1}H^T = H(H^TH)^{-1}H^T\)이기 떄문에 \(S^2 = S\)이므로, parametric bootstrap \(B-spline\) 추정량은 다음과 같이 쓸 수 있다.

\(\hat{f_{bag}}(x) = \frac{1}{B}\Sigma^{B}_{j=1}\hat{f^{*}_{j}}(x) = Sy + S(\frac{1}{B}\Sigma^{B}_{j=1}\epsilon_{j})\)

위 식에서 \(B\rightarrow\infty\) 일수록, 우변의 2번째 항은 0으로 수렴할 것이다.

따라서 \(\hat{f_{bag}}(x) = Sy = \hat{f}(x)\)임을 알 수 있다.


1.2 Bagging을 하는 이유

Bagging의 핵심 아이디어는 bootstrap sample들의 값을 모아 그들을 평균하므로써 분산을 줄이는것이다. Tree model은 \(variance\)가 큰 것으로 유명하다. Tree model은 데이터가 조금 바뀔때마다 분할 기준이 많이 바뀌는것을 쉽게 확인할 수 있다. Bagging을 활용하면 tree model의 \(variance\)를 크게 낮출 수 있다.

각 bootstrap sample로부터 계산되는 tree들은 가지치기를 하지 않고 그대로 성장시킨다. 일반적으로 가지치기는 variance를 낮추고 일반화 성능을 좋게 하지만, bagging에서는 개별 tree의 \(bias\)가 낮게 (개별 tree는 데이터에 더 fit하게) 해야하고 \(variance\)는 높아도 상관이 없다. \(variance\)는 aggregating으로 낮출 것이기 때문이다. 그래서 가지치기를 하지 않은 tree를 그대로 성장시킨다.

각각 분산 \(\sigma^2\)를 가지는 독립이고 동일한 분포를 따르는 확률 변수 \(B\)의 평균은 \(\frac{1}{B}\sigma^2\)의 분산을 가진다. 만약 동일한 분포를 따르는 확률 변수이고 양수의 쌍별 상관계수 \(\rho\)를 가진다면, 평균의 분산은 다음과 같다. 이는 ESL의 연습문제 15.1, correlated sample들의 평균의 분산을 계산하는 문제를 통해 확인할 수 있다.

\(Var(\frac{1}{B}\Sigma b_i) = \rho\sigma^2+\frac{1-\rho}{B}\sigma^2\)

\((Ex. 15.1)\) \(x_i \sim N(m, \sigma^2), \;i=1, 2, ... B\)이고, 어떤 \(x_i, x_j, i\neq j\)에 대해 상관계수가 양수임을 임을 가정하자 \((\rho > 0)\).

상관계수 \(\rho\)는 다음과 같이 쓸 수 있다.

\(\rho = \frac{1}{\sigma^2}E[(x_i-m)(x_j-m)]\)

\(E[x_i] = m\)이므로, 다음을 유도할 수 있다.

\(E[x_ix_j] = \rho\sigma^2 + m^2\)

평균의 분산은 아래와 같이 쓸 수 있다.

\(Var(\frac{1}{B}\Sigma x_i) = \frac{1}{B^2}[E[ (\Sigma x_i)^2] - E[\Sigma x_i]^2 ]\)

\(E[\Sigma x_i] = Bm\)이므로 우변의 괄호안의 두 번째 항은 \(B^2m^2\)이다.

\((\Sigma_i x_i)^2 = \Sigma_{i,j}x_i x_j\)로 쓸 수 있으므로, 다음의 식을 유도할 수 있다.

\(E[ (\Sigma x_i)^2] = \Sigma_{i,j}E[x_i x_j] = BE[x_i^2] + (B^2 - B)E[x_i x_j]\)

\(\qquad\qquad\;\, = B(\sigma^2+m^2) + B(B-1)(\rho\sigma^2+m^2)\)

\(\qquad\qquad\;\, = B\sigma^2 + B^2\rho\sigma^2 - B\rho \sigma^2 + B^2m^2\)

따라서, \(Var(\frac{1}{B}\Sigma x_i) = \frac{1}{B^2}[E[ (\Sigma x_i)^2] - E[\Sigma x_i]^2 ]\)은 아래와 같이 쓸 수 있다.

\(Var(\frac{1}{B}\Sigma x_i) = \frac {1} {B^2} [ B\sigma^2 + B^2\rho\sigma^2 - B\rho \sigma^2 + B^2m^2 - B^2m^2 ]\)

\(\qquad\qquad\quad\; = \frac{\sigma^2}{B} + \rho\sigma^2 - \frac{\rho\sigma^2}{B}\)

\(\qquad\qquad\quad\; = \rho\sigma^2+\frac{1-\rho}{B}\sigma^2\)

\(B\)가 커질수록 우변의 두 번째 항은 사라지고, 첫 번째 항만 남는다. 즉, 개별 bootstrap sample에서 적합되는 tree들의 분산 \(\sigma^2\)의 일부는 bootstrap sample의 수를 늘릴 수록 줄어들 수 있는것이다. 그러나 양수인 correlation으로 인해 첫 번째 항은 그대로 남아있게 된다.


2. Tuning Parameters


2.1 Tree의 개수?

출처 : The elements of statistical learning

출처 : The elements of statistical learning

Tree의 수는 tuning parameter라고 볼 수 없다. 사용자가 조정하긴 하지만 random forest도 bootstrap 추정의 일종이고 tree의 수는 단순 bootstrap의 반복수에 불과하기 때문이다. Bootstrap 추정량은 반복 수가 커질수록 본래의 추정량으로 수렴하고, overfit에 대한 위험도 없다. 값을 바꿔가며 조정 하기보다는 적절히 큰 값을 주는것이 forest를 성장 시키는것이 좋을 것 같다.


2.2 임의로 선택되는 변수의 개수

위에서 tree간 correlation이 양수이고 개별 tree들의 분산이 크면 bagging으로 분산을 줄일 수 있다는 것을 수식적으로 확인했다. 하지만 tree간 correlation은 bootstrap sample의 수를 늘린다고 해서 줄어들지 않는다.

Random forest에서는 매우 간단하고 직관적인 방법을 사용하여 tree간 correlation은 줄인다. 개별 tree를 적합할 때, 전체 사용 가능 변수 \(p\)개 중 임의의 \(m < p\)을 만족하는 \(m\)개로 축소하여 tree를 만들고 이를 통해 tree간 correlation을 줄인다.

Breiman의 원문에서도 random forest의 오류율은 다음의 2가지에 의존한다고 명시되어있다.

출처 : The elements of statistical learning

출처 : The elements of statistical learning

1. Forest내의 어떤 2개의 tree간 correlation. Correlation이 높을수록 forest의 오류율이 높다.
2. 개별 tree의 strength. Strength가 높은 분류기는 오류율이 낮은 분류기이다. 개별 tree의 오류율을 낮추면 forest의 오류율이 감소한다.

\(m\)을 줄이면, correlation과 strength 둘 다 줄어든다. \(m\)를 증가시키면 둘 다 증가한다. 원문에서는 다양한 데이터셋을 활용하여 경험적으로 이를 예증한다. m의 범위 내의 어딘가에 최적의 값이 있을 것이다. Out of bag 오류율을 참조하면 \(m\)의 범위를 빠르게 찾을 수 있다. 이것이 random forest에서 유일한 조정 가능한 parameter이다. 일반적으로 추천되는 \(m\)의 수는 분류의 경우 \(\sqrt{p}\), 회귀의 경우 \(p/3\)이다.

Bagging의 특징들을 수식적으로 정리해봤다. 어렵지 않은 수학이라 짜깁기가 가능 했다. 사실 random forest는 비교적 간단한 방법이라 수학적인 개념을 보지 않고도 설명이 가능할 것 같다. Bagging의 수렴에 대한 부분은 큰 수의 법칙만 이해하고 있어도 직관적으로 받아들이기 쉽다. Random forest를 위원회(committee)의 예를 들며 설명하는 경우가 많은데, 위원회 구성원들의 다양성을 생각하면 tree간 correlation의 직관적 이해에 도움이 된다. 위원회의 구성원들이 다양한 의견을 가지고 있지 않고 서로 비슷비슷한 경우는 correlation이 높은 경우일 것이다. 이런 경우 투표라는 aggregating 방식은 그다지 큰 효과를 보지 못할 것이다. 반대로 구성원의 성향이 다양하다면 (낮은 correlation) 개개인의 결정보다 투표로 인한 결정이 더 좋을 수 있다.


References

Breiman, Leo. “Random forests.” Machine learning 45.1 (2001): 5-32.

Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. The elements of statistical learning. Vol. 1. No. 10. New York: Springer series in statistics, 2001.