Random Forests

---

이번 포스팅에서는 랜덤 포레스트를 제안한 Breiman의 Random Forests 논문을 읽고 정리한다.

---

---

본 포스팅에서는 수식을 포함하고 있습니다.

티스토리 피드에서는 수식이 제대로 표시되지 않을 수 있으니

PC 웹 브라우저 또는 모바일 웹 브라우저에서 보시기 바랍니다.

---

---

   Abstract 

랜덤 포레스트의 일반화 오류는 트리의 개수가 커질수록 수렴한다. 그리고 분류 나무로 이루어진 포레스트의 일반화 오류는 개별 나무의 정확도와 나무 사이의 상관성에 따라 달라진다. 분리할 변수들을 랜덤으로 선택하는 경우 오류율이 AdaBoost와 맞먹을 정도가 되며 노이즈의 더 강건하다.

---

   Random Forests

1.1 Introduction

앙상블 나무를 성장시키고 나무들의 분류 결과 중 다수로 뽑힌 클래스를 해당 클래스로 예측하는 방법은 분류 문제에서 정확도를 엄청나게 향상시켰다. 배깅이 대표적인 예이다. 또 다른 예제로는 여러 개 분리 후보 중에서 최적 분리기준이 아닌 랜덤하게 분리 기준을 선택하는 방법이 있다. 이외에도 여러 가지 예를 소개한다.

 

또 하나의 중요한 논문으로서, Amit과 Geman은 최적 분리가 이루어지는 변수를 랜덤하게 선택하는 방법을 정의했다. 이 논문이 저자의 생각에 많은 영향을 끼쳤다고 한다.

 

앞에서 소개한 이 모든 과정의 공통점은 $k$번째 나무에 대하여 랜덤 벡터 $\Theta_k$가 생성된다. 이 벡터는 이전 벡터$\Theta_1, \ldots, \Theta_{k-1}$와는 독립이지만 동일한 분포를 갖는다. 그리고 나무는 학습 데이터와 $\Theta_k$를 이용하여 분류기 $h(x, \Theta_k)$를 만든다.

-> $\Theta_k$가 학습 데이터에서 생성된 건 줄 알았는데 다른 건가?

 

배깅에서는 $\Theta$는 학습 데이터에서 생성된 붓스트랩 샘플이고 랜덤 분리 선택에서는 $\Theta$가 변수를 나타내는 인덱스라고 한다. $\Theta$의 본질과 차원은 나무를 구축할 때 그 쓰임에 따라서 달라진다.

 

이제 랜덤 벡터들을 이용해서 많은 분류 나무를 만들고 이 나무를 이용하여 클래스를 예측한 뒤 다수결로 얻어진 클래스를 최종 라벨로 선정하는 것이다. 이러한 과정을 랜덤 포레스트(Random Forests)라 한다.

1.2 Outline of Paper

각 섹션마다 어떤 내용을 다루는지 소개한다.

---

   Characterizing the Accuracy of Random Forests

2.1 Random Forests Converge

여기서는 마진(Margin)을 정의한다. 분류기 $h_1(x), \ldots, h_K(x)$와 Y, X의 확률 분포로부터 추출된 학습 데이터에 대하여 마진을 다음과 같이 정의한다.

$$mg(X, Y) = av_k I(h_k(X)=Y)-\max_{j\neq Y} av_kI(h_k(x)=j)$$

마진 값이 큰 양수일 수록 예측 결과에 대한 자신감이 상승한다. 그리고 일반화 오류는 다음과 같이 주어진다.

$$PE = P_{X, y}(mg(X, Y)<0)$$

 

정리 1.2는 랜덤 포레스트의 일반화 오류가 수렴하는 것을 보여준다. 즉, 일반화 오류가 1이 아닌 값에 수렴한다면 이는 랜덤 포레스트가 분류기를 추가해도 과적합이 잘 일어나지 않을 수 있음을 보여준다.

2.2 Strength and Correlation

일반화 오류의  상한은 개별 분류기의 정확도와 분류기 간의 상관성 정도 이 2가지로 표현할 수 있다고 한다. 이 2개의 상호작용이 랜덤 포레스트를 이해하기 위한 핵심이다.

 

여기서는 실제로 분류기의 정확도를 측정하는 측도로써 스트렝스(Strength)를 정의하고 일반화 오류의 상한을 이 스트렝스와 두 분류기의 raw 마진의 상관계수를 이용하여 표현한다. 이 상관계수는 이진 분류에서 라벨을 1, -1로 설정한 경우 두 분류기의 상관계수와 같음을 보였다.

---

   Using Random Forests

이 논문이 있기 전에 존재했던 랜덤 포레스트들은 일반화 오류 관점에서 AdaBoost를 뛰어넘지 못했다. 정확도를 향상하기 위해선 랜덤 포레스트에 포함된 Randomness가 개별 분류기의 스트렝스를 유지하면서 분류기들의 상관성을 최소화해야 한다. 여기서 연구되는 랜덤 포레스트는 변수들을 랜덤 하게 선택 또는 그 변수들의 선형 조합을 랜덤하게 선택하는 것으로 구성되어있다. 이렇게 하여 AdaBoost와 견줄만한 포레스트가 만들어진다. 이런 포레스트들은 다음과 같은 특징을 갖고 있다.

 

1. 그들의 정확도는 AdaBoost에 견줄만하며 더 좋을 때도 있다.

2. 잡음이나 이상치에 덜 민감하다.

3. 배깅이나 부스팅보다 빠르다.

4. 내부 추정치를 제공한다고 한다.

5. 단순하고 쉽게 병렬 처리가 가능하다.

3.1 Using out-of-bag Estimates to Monitor Error, Strength, and Correlation

본 논문의 저자는 랜덤 포레스트를 실험할 때 배깅과 랜덤 변수 선택을 같이 사용했다고 한다. 

 

학습 데이터를 붓스트랩 샘플링하고 샘플링된 데이터에 대하여 랜덤 변수 선택을 실시한다. 나무를 성장시키고 가지치기는 수행하지 않는다고 한다.

 

배깅을 사용하는 이유는 랜덤 변수 선택을 할때 배깅을 같이 이용하면 정확도가 더 좋아지는 것 같다고 한다. 두 번째 이유는 배깅이 일반화 오류의 추정치를 계산할 때 필요하다는 것이다. 두 번째 이유에서 배깅이 필요한 것은 배깅 샘플이 아니라 원 데이터에서 배깅 샘플이 되지 않은 Out-of-Bag 샘플을 이용하여 일반화 오류를 계산한다. 

 

여기서 내부 추정치(Internel Estimates)가 나오는데 이는 외부 데이터라 할 수 있는 Test set을 이용하지 않고 학습 데이터 내부의 Out-of-Bag(OOB) 데이터를 이용하여 얻은 추정치인 것 같다. OOB도 결국 학습 데이터의 일부이니까.

---

   4. Random Forests using Random Input Selection

여기서는 변수를 랜덤으로 선택하는 랜덤 포레스트를 가지고 실험한 내용을 소개한다. CART를 이용했고 깊이는 최대로 하며 가지치기는 하지 않는다. 매 분리마다 $F$개의 변수를 랜덤으로 선택하는데 여기서는 $F=1$또는 $\log_2M+1$보다 작은 가장 큰 정수로 설정했다고 한다($M$은 총 변수 개수).

여러 데이터 셋에 대하여 AdaBoost와 랜덤 포레스트의 성능을 비교한 실험이다. 작은 데이터와 큰 데이터에 대하여 다르게 실험했다. 

 

실험 결과 랜덤 포레스트의 일반화 오류가 AdaBoost와 견줄만하다는 것이다. 이때 분리 때마다 한개의 변수를 랜덤하게 뽑은 랜덤포레스트의 성능도 나쁘지 않다는 점이 놀랍다고 했다.

---

   5. Random Forests Using Linear Combinations of Inputs

변수가 많이 없는 상황에서 단순히 변수를 랜덤으로 고르면 나무들 간의 상관성이 높아질 수 있다. 이 경우 다른 방법을 생각해 볼 수 있는데 그것이 바로 랜덤 선형 결합이다. 즉 매 분리 때마다 $L$개의 변수를 랜덤으로 뽑고 각 변수들을 다 더하고 유니폼 분포를 따르는 수를 절편항으로 추가로 더해준다. 이러한 방식으로 $F$개의 선형 결합을 뽑고 그중에서 최적 분리를 찾아낸다.

 

이러한 방식으로 AdaBoost와 비교하여 실험했는데 AdaBoost의 성능이 더 좋았다고 한다.

5.1 Categorical Variables

선형 결합을 할 때 연속형 변수들끼리는 상관없지만 범주형 데이터가 섞여 있는 경우 이를 어떻게 선형 결합해야 하는지가 문제가 된다. One-Hot 코딩을 이용하여 이를 연속형 변수처럼 취급한다.

내용

---

   6. Empirical Results on Strength and Correlation

여기서는 스트렝스와 분류기간 상관성이 일반화 오류에 어떻게 영향을 미치는지 확인하는 실험을 수행하고 그 결과를 정리했다.

 

각 데이터에 대하여 랜덤으로 뽑는 변수의 개수에 따라서 스트렝스와 상관성이 어떻게 변하는지 그리고 Test Error와 OOB Error가 어떻게 변하는지 실험하였다.

 

실험 결과로부터 알 수 있는 것은 좋은 랜덤 포레스트는 분류기간 상관성이 낮고 스트렝스는 높아야 된다는 것이다. 랜덤 포레스트에서 랜덤으로 추출하는 과정은 스트렝스를 유지하면서 상관성을 낮추는 것을 목표로 한다.

---

   7. Conjecture: Adaboost is a Random Forest

AdaBoost가 랜덤포레스트에서 학습 데이터의 가중치를 랜덤으로 선택하는 과정과 같다는 것을 추측한 내용이다.

---

   8. The Effects of Output Noise

Dietterich는 출력 라벨에 노이즈를 가한 비율이 높으면 AdaBoost의 성능은 떨어지지만 배깅과 랜덤 분리 선택 알고리즘은 내성이 강하다고 한다. 따라서 출력 라벨의 노이즈에 대한 강건함(Robustness)는 모형이 가져야 할 굉장히 바람직한 성질이다.

 

AdaBoost는 잘못 분류된 데이터에 대해서 집중하는 성질이 있어서 이 부분이 노이즈에 의한 결과였다면 바로 무시해야 하지만 AdaBoost는 이를 집중적으로 학습하기 때문에 성능이 더 안 좋아진다고 한다. 하지만 랜덤 포레스트는 이러한 노이즈에 대하여 강건함을 실험적으로 증명하였다.

---

   9. Data with Many Weak Inputs

변수가 많고 개수가 많은 데이터에서 y를 확실하게 구분하는 하나의 인자나 소수 몇 개의 인자를 찾기 어렵다.

 

하지만 랜덤 포레스트는 그러한 인자를 찾을 수 있다는 것을 시뮬레이션으로 증명한다. 분리 때마다 랜덤하게 뽑는 변수의 개수를 조절하여 이러한 상황에서 테스트 오류를 줄일 수 있음을 보였다. 흥미로운 점은 개별 분류기의 테스트 오류는 엄청 높았다는 것이다. 하지만 뭉치니까 강한 분류기가 되었다.

---

   10. Exploring the Random Forest Mechanism

랜덤 포레스트는 해석을 어떻게 해야 할지 막막하다. 이러한 점을 보완하기 위해 변수 중요도를 계산하는 과정은 제안하고 이를 실험하여 어떤 변수가 중요한지 알아본다. 이렇게 해서라도 해석을 하고 싶었던 것이다. 한 변수가 중요하다고 나오면 이 변수와 상관성이 높은 변수는 상대적으로 중요하지 않게 나온다는 점도 실험을 통해 밝혔다.

---

   11. Random Forests for Regression

여기서부터는 랜덤 포레스트를 회귀 문제에 적용시키며 일반화 오류에 대한 상한을 제시한다. 이러한 상한도 각 회귀 나무들 간 상관성과 개별 나무들의 에러(실제값과 예측값의 차이 정도)에 의존한다.

---

   12. Empirical Results in Regression

랜덤 포레스트를 실제 회귀용 데이터에 적용한다. 이때 배깅과 랜덤 변수 선택을 적용했다.

 

이때 회귀 문제에서는 최적 테스트 에러를 얻기 위해 랜덤으로 뽑는 변수의 수가 분류 문제에서보다 더 많이 필요하다고 한다.

 

또한 모델 비교 관점에서 랜덤 포레스트는 단순 배깅보다 더 좋았다고 한다. 또한 출력 변수의 노이즈에 대한 강건함도 랜덤포레스트가 배깅에 비해 좋다고 한다.

---

   13. Remarks and Conclusions

랜덤 포레스트는 예측을 위한 효과적인 도구이다. 대수의 법칙으로 인하여 랜덤포레스트는 과적합을 잘 일으키지 않고 랜덤성을 잘이용하면 분류에서든 회귀에서든 좋은 성능을 발휘할 수 있다. 여기서는 배깅과 랜덤 변수 선택에서 랜덤성을 이용했지만 랜덤포레스트 알고리즘 내에서 다른 곳에서도 랜덤성을 이용할 수 있다고 한다. 예를 들면 선형 결합을 위한 변수들의 선택 같은 것 말이다.

---