Ensemble and Random Forest

Ensemble and Random Forest

직접 투표 hard voting

• 각 분류기 예측 모아서 가장 많이 선택된 클래스 예측

간접 투표 soft voting

• 모든 분류기가 클래스의 확률을 예측할 수 있으면, 개별 분류기의 예측을 평균 내어 확률이 가장 높은 클래스를 예측
• 확률이 높은 투표에 비중을 더 두기 때문에 직접 투표 방식보다 성능이 높다.

약한학습기¹ weak learner일지라도 큰 수의 법칙 law of large numbers에 의해 앙상블은 강한 학습기 strong learner가 될 수 있다.

결정주분류 Decision-Making Classifier

• \(d\)차원 입력 변수 \(x = (x^{(1)}, \dots, x^{(d)})^\top\) 중 하나를 골라 그 값이 어떤 역치를 초과하는지 여부로 클래스 분류를 행하는 선형 분류기
  • 하드 보팅은 앙상블(Ensemble) 내에서 각 구성원이 예측한 결과를 직접적으로 비교하여 다수결로 최종 예측 결과를 결정하는 방식입니다. 이때, 결정 주 분류기는 앙상블 내에서 최종 예측 결과를 결정하는 데에 있어서 중요한 역할을 수행할 수 있습니다.
  • 예를 들어, 앙상블 내에 여러 개의 분류기가 있을 때, 결정 주 분류기는 다수결 방식으로 최종 예측 결과를 도출할 때, 다른 구성원들의 예측 결과보다 더 가중치를 더할 수 있습니다.

배깅

배깅bagging²

• 중복을 허용하여 샘플링하는 방식
• 통계학에서 말하는 부트스트랩이란, n개의 훈련 표본\(\{x_i, y_i)\}^n_{i=1}\)으로부터 중복을 포함하여 무작위로 n개를 골라 원래의 훈련 표본 집합과 약간 다른 훈련 표본 집합을 생성하는 기법이다.
• 부트스트래핑으로 유사 훈련 표본 집합을 생성한 뒤 이렇게 얻어진 훈련 표본 집합으로 학습시키는 과정

배깅 알고리즘

1. \(j=1,\dots ,b\)에 대하여 아래와 같은 처리를 반복한다.

   • 1. n개의 훈련 표본 \(\{x_i, y_i)\}^n_{i=1}\)으로부터, 중복을 포함하여 n개를 무작위로 선택한다.
   • 2. 이렇게 얻어진 표본을 이용하여 약 학습기\(\psi_i\)를 구한다.

2. 모든 약 학습기 \(\{ \psi_j\}^b_{j=1}\)의 평균을 강 학습기 \(f\)로서 출력한다.

3. \(f(x)\leftarrow \frac{1}{b} \sum^b_{j=1} \psi_j (x)\)

페이스팅 pasting

• 중복을 허용하지 않고 샘플링 하는 방식

-> 배깅과 페이스팅의 확장성 : CPU 코어나 서버 병렬 학습 가능, 예측 병렬 수행 가능

oob샘플 out-of-bag

• 선택되지 않은 훈련 샘플의 나머지³
• 예측기 훈련되는동안 oob 샘플은 사용하지 않으니까 oob 샘플으로 평가를 평균내서 앙상블 평가의 결과를 얻을 수 있다.

랜덤 패치 방식 random patches method

• 훈련 샘플과 샘플을 모두 샘플링하는 것

랜덤 서브스페이스 방식 random subspace method

• 훈련 샘플을 모두 사용하고 특성은 샘플링하는 것

랜덤 포레스트

• 배깅 방법(또는 페이스팅)을 적용한 결정 트리의 앙상블
• 무작위로 선택한 특성 후보 중에서 최적의 특성을 찾는 식으로 무작위성 더 주입
• 트리를 다양하게 만들고 편향을 손해보는 대신 분산을 낮추어 전체적으로 더 훌륭한 모델을 만듦

엑스트라 트리extremely randomized trees 앙상블 = 엑스트라 트리 estra-tree

• 후보 특성을 무작위로 분할하고 그 중에서 최상의 분할을 선택
• 모든 노드에서 특성마다 가장 최적의 임계값을 찾는 것이 트리 알고리즘에서 가장 시간이 많이 소요되는 작업 중 하나이므로 일반적인 랜덤 포레스트보다 엑스트라 트리가 훨씬 빠르다.

무작위성이 주입된 랜덤 포래스트 분류는 거의 모든 특성에 대해 평가할 기회를 가지지만, 결정 트리 분류는 일부 특성을 완전히 배제시킨다.

부스팅

부스팅boosting⁴

에이다부스트

에이다부스트AdaBoost⁵

• 과소적합했던 훈련 샘플의 가중치를 더 높여 새로운 예측기 만들기
• 가중치 부여: 이전 모델에서 잘못 분류된 샘플에 더 높은 가중치를 부여하여 다음 모델에서 이 샘플이 더 중요하게 처리되도록 합니다.
• 재샘플링: 이전 모델에서 잘못 분류된 샘플을 더 많이 선택하여 다음 모델에서 이 샘플이 더 많이 등장하도록 합니다.
• 특성 선택: 이전 모델에서 잘못 분류된 샘플과 관련이 높은 특성을 더 많이 사용하여 다음 모델을 학습시킵니다.
• 학습률을 줄여 해당 분류기가 전체 모델에 기여하는 확률을 줄임

에이다부스트를 통해 학습을 수행하는 알고리즘⁶

1. 각 훈련 표본 \(\{x_i, y_i)\}^n_{i=1}\)에 대응하는 가중치 \(\{ w_i\}^n_{i=1}\)을 모두 같은 값으로, 강분류기 \(f\)는 0으로 초기화한다.

• \(w_1,\dots, w_n \leftarrow 1/n, f \leftarrow 0\)

2. \(j=1,\dots,b\)에 대하여 아래의 과정을 반복한다.

   • 1. 표본의 현재 가중치 \(\{ w_i\}^n_{i=1}\)에 대하여 가중 오분류율(0/1손실⁷에 가중치를 곱한 합)\(R(\psi)\)가 최소가 되도록 약 분류기\(\psi_j\)를 학습시킨다.
     • \(\psi_j = argmin_{\psi} R(\psi), R(\psi) = \sum^n_{i=1} \frac{w_i}{2}(1-\psi(x_i)y_i)\)
   • 2. 약 분류기 \(\psi_j\)의 가중치 \(\theta_j\)를 다음 식과 같이 결정한다.
     • \(\theta_j = \frac{1}{2} log\frac{1-R(\psi_j)}{R(\psi_j)}\)
   • 3. 강 분류기 \(f\)를 다음 식과 같이 업데이트 한다.
     • \(f \leftarrow f+\theta_j\psi_j\)
   • 4. 표본의 가중치 \(\{ w_i\}^n_{i=1}\)을 다음 식과 같이 업데이트 한다.
     • \(w_i \leftarrow \frac{exp(-f(x_i)y_i)}{\sum^n_{i'=1}exp(-f(x_{i'})y_{i'})}, \forall i = 1,\dots, n\)

그레이디언트 부스팅

• 그레이디언트 부스팅 gradient boosting
  • 이전 예측기가 만든 잔여 오차에 새로운 예측기 학습
  • 그레디언트 트리 부스팅 gradient tree boosting = 그레디언트 부스티드 회귀 트리 gradient boosted regression tree(GBRT)
    • 결정 트리를 기반 예측기로 사용
  • 확률적 그레디언트 부스팅 stochastic gradient boosting
    • 트리가 훈련할 때 사용할 훈련 샘플의 비율 지정 -> 분산 낮아질 것

Note

에이다부스트(AdaBoost)는 처음에는 지수 손실 최소화를 통해 분류기를 학습합니다. 그러나 이후에는 분류 오차를 최소화하기 위해 다른 손실 함수나 분류기 학습 알고리즘을 사용하기도 합니다.

예를 들어, 로지스틱 회귀(Logistic Regression)를 사용하여 분류기를 학습하면 로지스틱 손실 함수를 최소화하는 방향으로 학습됩니다. 또한, 그레디언트 부스팅(Gradient Boosting)을 사용하여 분류기를 학습할 수도 있습니다. 이 경우, 분류 오차를 최소화하는 방향으로 학습됩니다.

따라서, 에이다부스트는 지수 손실 최소화 학습 관점에서만 볼 수 있는 것은 아니며, 다른 손실 함수나 학습 알고리즘을 사용하여 분류기를 학습할 수 있습니다. 그러나 초기에는 지수 손실 함수를 사용하여 가중치를 부여하는 방식으로 분류기를 학습하는 것이 일반적입니다.

스태킹

스태킹stacking⁸

• 앙상블에 속한 모든 예측기의 예측을 취합하는 모델 사용 -> 블렌더blender 또는 메타학습기meta leaner

Footnotes

1. 랜덤 추측보다 조금 더 높은 성능을 내는 분류기

2. bootstrap aggregating의 줄임말

3. 예측기마다 남겨진 훈련의 샘플은 모두 다르다.

4. 원래는 가설 부스팅 hypothesis boosting

5. 적응적 부스팅adaptive boosting의 줄임말

6. 해당 업데이트는 지수손실 최소화 관점에서 봄

7. 0/1 손실(0/1 Loss)은 분류 문제에서 사용되는 손실 함수 중 하나로, 분류 결과가 정확하게 일치하는 경우 손실을 0으로, 그렇지 않은 경우에는 1로 표현하는 손실 함수입니다.

8. stacked generation의 줄임말