Random Forests

-
04_4 : Ensemble Learning : Random-Forests

Random Forest는 이전 글에서 공부했던 Bagging 방법의 특수한 형태로써 Decision Tree를 Base Learner로 사용한다. Random하게 변수를 선택하여 여러개의 Decision Tree들(Forest)을 학습시키는 방법을 사용한다.

우선 Decision Tree에 대하여 알아보자.

Decision Tree

$d$개의 변수를 가지는 Data가 주어졌다고 가정하자. 이때 하나의 data point $v$는 아래와 같이 정의된다.
$$v = (x_1,x_2,\cdots ,x_d) \in \mathbb{R}^d $$
각 $x_i$는 변수 하나하나를 나타내는 스칼라 값이다. 변수가 매우 많은 경우, 앞서 배운 차원축소와 같은 방법을 사용하거나 이후에 다룰 Random Forest처럼 임의로 변수를 추출하여 사용한다. 변수의 추출은 $\phi (v)$ 함수에 의해서 이루어진다.
$$\phi\;:\;\mathbb{R}^d \rightarrow \mathbb{R}^{d^\prime},\;\;\;\;d > d^\prime$$

  • Training
Training 단계에서는 초록색 end node에 대응하는 정답 Label($y$)을 사용하여 각 노드를 분할하는 Split function의 매개변수를 최적화 한다. 각 노드에 대응되는 Data set을 $S$라고 하자. 그렇다면, 해당 집합은 Split function에 의하여 $S^L,\;S^R$ 두개의 집합으로 분할된다. 
$$S_i = S_i^L \cup S_i^R,\;\;S_i^L \cap S_i^R = \emptyset $$
이렇게 Data를 분할하는 Split function은 데이터를 정보 획득량(information gain : $I$)이 최대화 되도록 분리한다.
$$I = H(S) - \sum_{i\in\{L,R\}} \frac{|S^i|}{|S|} H(S^i),\;\;\;\;H(S) = -\sum_{c\in C}p\log (p(c))$$
$|\cdot |$은 각 집합에 속한 원소의 개수를, $H$는 섀넌 엔트로피(Shannon entropy)를 의미한다. 정보 획득량 $I$를 최대화 하기 위해서는 섀넌 엔트로피가 최소화 되어야 한다. 

  • Test
학습이 완료된 Decision Tree에 새로운 Data $v$가 주어지면, 이전에 학습된 Split function에 따라 $v$를 특정 end node로 보낸다. 그렇다면 해당 end node에 지정된 label $y$가 $v$에 대한 예측 결과이다.


Decision Tree는 Complexity가 높고, Overfitting의 위험 또한 높다. 이러한 단점을 보완하는 Random Forest 방법을 살펴보자.


Random Forest

Random forest 방법의 알고리즘을 살펴보자.
  • Algorithm
                                                                                                                  
1. For $b = 1$ to $B$ :
            (a) Draw a bootstrap sample $Z^*$ of size $N$ from the training data.
            (b) Grow a random-forest tree $T_b$ to the bootstrapped data, by recursively repeating the following
                  steps for each terminal node of the tree, until the minimum node size $n_{min}$ is reached.
                          i. Select $m$ variables at random from the $p$ variables.
                         ii. Pick the best variable/split-point among the $m$.
                        iii. Split the node into two child nodes.

2. Output the ensemble of trees $\{T_b\}_1^B$.

To make a prediction at a new point $x$:
Regression : $\hat{f}_{rf}^B (x) = \frac{1}{B}\sum_{b=1}^B T_b(x)$.
Classification : Let $\hat{C}_b(x)$ be the clas prediction of the $b$th random-forest tree. 
                         Then $\hat{C}_{rf}^B(x) = majority\;\,vote\;\{\hat{C}_b(x)\}_1^B$.
                                                                                                                  
위의 알고리즘이 어떤 뜻인지 한번 살펴보자.
1. 우선, $B$는 base learner $T$의 개수이다. 
    (a) 각 base learner가 사용할 bootstrap $Z^*$를 만들어준다. (Bagging)
    (b) 아래 i, ii, iii의 순서에 따라 $T_b$를 학습시킨다. (Randomized node optimization)
            i. $p$개의 변수 중 $m$개의 변수를 random하게 선택한다. ($m<p$)
            ii. $m$개의 변수를 사용하여 최적의 split point(function)을 만든다.
            iii. node를 2개의 child node로 split한다.
        위 과정을 재귀적으로 minimum node size $n_{min}$에 도달할 때까지 반복한다.

2. 각각의 학습된 Tree를 합치는 과정은 아래와 같다.
Regression의 경우 평균을 사용하고, Classification의 경우 Majority voting을 사용한다. (물론 꼭 이 방법을 사용해야 하는 것은 아니다)

Random Forest의 특징은 Bagging 방법을 사용하여 Bootstrap을 구성하는 것에 추가적으로 Decision tree에 적용할 변수를 Random하게 선택한다는 점이다. 이를 통해 Tree들의 예측이 최대한 Decorrelation(비상관화) 되도록 하고, Generalization 성능을 향상시킨다.



Random Forest (Cont.)

  • Generalization Error
Random Forest의 다른 특징 중 하나로, Generalization error의 Bound를 계산할 수 있다. (일반화 성능의 상한을 계산 가능하다)
Population size $T$가 충분히 크다면 아래의 식으로 나타난다.
$$Generalization\;\;Error\leq \frac{\bar{\rho} (1-s^2)}{s^2} $$
$\hat{\rho}$ is the mean value of the correlation coefficients between individual trees.
$\hat{\rho}$은 개별 tree들의 상관관계의 평균이다. tree들 간의 correlation이 적을수록 $\hat{\rho}$은 작아지게 되고, 상한은 작아질 것이다.

$s^2$ is the margin function. (for binary classification, it is simply the average difference proportion between the correct and incorrect trees over all training data)
$s^2$는 정답과 오답 사이 차이의 평균이다. 알고리즘이 정확할수록 $s^2$은 1에 가까워지게 커지게 되고, 상한은 작아질 것이다.


  • Variable Importance
Random Forest의 유용한 특징 중 하나로, model에서 변수의 중요도를 계산할 수 있다.

    Step1. Compute the OOB error for the original dataset($e_i$)
    Step2. Compute the OOB error for the dataset which the variable $x_i$ is permuted ($p_i$)
    Step3. Compute the variable importance based on the mean and standard deviation of ($p_i-e_i$)
                over all trees in the population.

Step1. 가장 먼저 Bootstrap을 사용해 학습한 Tree에 대하여 OOB error $e_i$를 계산한다. 
Step2. 그리고 OOB data에 대하여 중요도를 알고싶은 변수 $x_i$에 해당하는 값을 무작위로 뒤섞는다.
            뒤섞은 data에 대한 OOB error $p_i$를 계산한다.
Step3. 모든 Tree에 대하여 $e_i$와 $p_i$의 차이를 계산하고 평균과 분산을 구한다.

$x_i$가 split에 자주 사용된 중요한 변수라면, $p_i$ 보다 $e_i$가 작고, 차이가 많이 날 것이고, 개별 tree마다 차이의 편차가 작을 것이다. 하지만 $x_i$가 split에 자주 사용되지 않은 별로 중요하지 않은 변수라면, $p_i$와 $e_i$의 차이가 크지 않을 것이다.

$m$번째 tree에서 변수 $i$에 대한 Random permutation 전후 OOB error의 차이, 평균, 분산, 중요도는 아래와 같이 정의된다.
 차이  : $d_i^m = p_i^m - e_i^m$

 평균  : $\overline{d}_i = \frac{1}{m} \sum_{i=1}^m d_i^m$

 분산  : $s_i^2 = \frac{1}{m-1} \sum_{i=1}^m (d_i^m-\overline{d}_i)^2$

중요도 : $v_i = \frac{\overline{d}_i}{s_i}$

변수의 중요도가 높을수록 평균은 클 것이고, 분산은 작을 것이다.
여기서 주의할 점은 $v_i$의 값이 어느 정도로 중요한지를 표현할 뿐이지, 그 값이 어떤 의미를 가지지 않는다는 점이다.



※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 정리하고, 공부한 내용을 추가하여 작성되었습니다.



댓글

댓글 쓰기

이 블로그의 인기 게시물

One-Class SVM & SVDD

-
이미지
03_6 : Anomaly Detection : Auto-Encoder, 1-SVM, SVDD MoG와 같은 밀도기반 방법론들은 특정 객체가 정상범주에 속할 확률을 구했다. 반면 Support vector 기반 방법론들은 normal과 abnormal을 구분하는 분류경계면을 찾는다. 이번 글에서는 Support vector 기반의 Anomaly detection 방법 중 one-class SVM과 SVDD를 알아보자. One-class Support Vector Machine (1-SVM, OCSVM) 1-SVM의 목표는 Data를 feature space로 mapping 한 뒤, 분류경계면을 통해 mapping된 Data 중 normal data들이 원점으로부터 최대한 멀어지게 만드는 것이다. 위 그림에서 파란색 분류경계면이 (+1) normal data들을 구분하는 것을 확인할 수 있다. 이 목표를 수식화 한 Optimization problem부터 살펴보자. Optimization Problem $$\min_{\textbf{w}}\;\;\;\frac{1}{2}||\textbf{w}||^2 + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho$$ $$s.t.\;\;\;\textbf{w}\cdot \Phi (x_i) \geq \rho - \xi_i\;\;\;\;(i=1,2,\cdots,l),\;\;\xi_i\geq 0$$ $\frac{1}{2}||\textbf{w}||^2$ term은 SVR과 같이 $x$의 변화에 따른 변동이 크지 않도록 Regularization을 하는 term이다. $\rho$는 위 그림에서 주황 직선을 나타내는데, 원점과 분류경계면 Hyperplane과의 거리를 나타낸다. 이 값을 뺌으로써 최소화 문제를 만족하는 최적해일때 $\rho$가 최대가 되도록 한다. (원점에서 Hyperplane이 최대한 멀어지게 만든다) $\frac{1}{\nu l} \sum_{i=1}^l \xi_i$ term은 제약식에 따라 Hyp...
자세한 내용 보기

Support Vector Regression (SVR)

-
이미지
02_4 : Kernel based learning : Support Vector Regression (SVR) 앞에서 공부했던 SVM은 binary classification을 하기 위한 방법이었다. 이번 글에서 알아볼 SVR은 함수를 추정하여 연속적인 수치변수를 예측하는 회귀 방법이다.  SVR을 알아보기에 앞서 우리가 하려는 함수추정의 목적을 살펴보자. Fitting function 함수를 추정하고 싶을 때 우리의 목적은 크게 2가지로 나뉜다. Minimize an error measure (Loss function) 한마디로 error를 최소화 하여야 한다. (잘 맞춰야 한다) Function to be simple 같은 성능이라면, 함수는 최대한 단순해야 한다. 함수가 단순하다는 뜻은 아래의 조건들을 의미한다. Fewest basis functions Simplest basis functions Flatness is desirable Support Vector Regression (SVR) 위에서 살펴보았던 Loss function과 Flatness를 반영하도록 목적함수를 만들 것이다. SVR에도 여러 종류가 있는데, 우선 $\varepsilon$-SVR에 대하여 알아보자. 현실의 Data들은 어쩔 수 없이 발생하는 noise가 존재한다. 아래 식에서 noise는 $\varepsilon$이다. $$y = f(x)+\varepsilon$$ $\varepsilon$-SVR에서 핵심 아이디어는 $\varepsilon$ 보다 작은 noise에 대해서는 Loss를 주지 말자는 것이다.  왼쪽 그림에서 색이 칠해진 영역을 Epsilon-tube 라고 하는데, 이 영역안에 있는 객체들에게는 Loss를 부여하지 않는다. 이를 위한 Loss function은 오른쪽에 표현된다. 이 Loss function은 hinge를 닮았다고 해서, Hinge Loss 라고 불린다. 차이가 $\varepsilon$ 보다 작은 경우 loss는 0이고, $\vareps...
자세한 내용 보기

Self-Training & Co-Training

-
이미지
 05_2 : Semi-Supervised Learning : Self-Training and Co-Training 우선 가장 기본적인 준지도학습 방법 Self-Training에 대하여 알아보자.  Self-Training 우리에게 주어진 정보는 Labeled data $(\mathbf{X}_l,y_l)$과 Unlabeled data $\mathbf{X}_u$이다. Self-training과정은 다음과 같이 진행된다.  1. 우선 주어진 Labeled data $(\mathbf{X}_l,y_l)$를 사용하여 예측함수 $f$를 학습시킨다. $$y_l = f(x_l)$$ 2. 학습이 완료되면, 예측함수 $f$를 사용해 Unlabeled data $\mathbf{X}_u$의 예측값 $\hat{y}_u$를 구한다. $$\hat{y}_u = f(x_u)$$ $$\Downarrow$$ 3. 이제 기존의 Labeled data와 예측함수에 의해 labeling이 된 Unlabeled data를 합치고, 이 data를 사용해 예측함수 $g$를 학습한다. 이때 어떻게 Unlabeled data를 합치는지에 따라서 많은 variation이 있다. 대표적으로 Add all $(x_u,\hat{y}_u)$ to labeled data Add a few most confident $(x_u,\hat{y}_u)$ to labeled data Add all $(x_u,\hat{y}_u)$ to labeled data, weight each by confidence. 모든 Unlabeled data를 합치는 방법, 몇몇개의 가장 예측 confidence가 높은 data만을 합치는 방법, 모든 data를 합치치만 예측 confidence에 따라서 weight를 지정하는 방법 등이 있다. 4. 위와 같은 과정을 Unlabeled data가 없어지거나, 수렴할 때 까지 반복한다. Propagating 1-Nearest Neighbor 다른 예시로 Propagating ...
자세한 내용 보기