[CS229] [10] Lecture 10 - Decision Trees and Ensemble Methods

1. Decision Tree

- 시간과 위치가 주어지면 스키를 탈 수 있는지 없는지 알려주는 classifier가 있다고 가정해보자.

- 즉, O or X라고 말하는 Binary Classifier이다.

- 다음과 같이, 위도와 달에 따른 스키를 탈 수 있는지 없는지 나타내는 dataset이 주어져 있다고 해보자.

- 여기서 positive인 부분만 얻어내고 싶다면 어떻게 해야할까?

- 만일 linear classifier로 classification한다고 생각하면 어려움이 있을것이다.

- 또는 SVM을 사용해야겠다라는 생각이 들수도 있을 것이다.

- 하지만 이는 Decision tree를 사용하면 더욱 수월하게 수행가능하다.

 

- Decision tree는 Greedy, topdown,recursive partitional하다.

- Decision tree가 무엇인지 직관적으로 알아보자.

- 우선 Decision tree를 쉽게 설명하면 스무고개처럼 질문을 통해 데이터를 유추하는 방식이라고 생각하면 된다.

- 기존의 데이터를 "위도가 30이상이냐?"라는 질문에 다음과 같이 데이터셋을 classification할 수 있다.

 

- 그 후, 3월보다 빠르냐? 라는 질문에 다음과 같이 데이터셋을 classification할 수 있다.

- 이걸 계속 질문을 반복하여 다음과 같이 seperation해주는 게 decision tree이다.

 

- 그러면 우리가 목표하고자 하는건, 이걸 분할하는 함수를 찾는 것이다.

- 즉, Region을 정의하는 함수를 찾는 것이다.

- 만약 Region R_p가 있고 split function S_p를 다음과 같이 정의해보자.

- S_p(j,t) = (R_1 = {x | x_j < t, x -> R_p }, R_2 = {x | x_j >= t, x-> R_p} )

 

- 그러면 어떻게 split을 할 수 있을까?

- Region의 Loss를 구하여 Optimer한 split을 할 수 있을 것이다.

- 이를 위해 L(R) == Loss on R 이라고 정의해보자.

- 그리고 p^hat_c 를 class c에 대한 R의 Loss률 이라고 정의하자. 

- 그렇다면 L_c = 1 - max p^hat_c 가 된다.

- Loss에 대해 define하였기에, 이 loss를 줄이는 분할을 선택해야한다.

- 즉, 기존 Parent Region의 Loss보다 child Region Loss가 더 작아야 되는 것을 의미한다.

- 즉 margin이 커야 된다는것을 의미한다.

- 그러면 다음과 같은 식이 만족해야한다는 것을 알 수 있다.

" max{L(R_p) - (L(R_1) + L(R_2)}"

- 하지만 해당 Loss는 잘못된 Loss이다.

- 그 이유는 다음 예시를 보며 이해해보자.

- 다음과 같이 분류가 된다고 했을 때,

- 우리는 오른쪽 tree가 더 좋다고 말할 수 있을 것이다.

- 하지만, 실제 loss값을 구해보면 다음과 같다.

- L(R_p) = 100 , L(R_1 + R_2) = 100 이다. 즉 차이가 없다.

- 이를 해결하기 위해 나오게 된 방법이 cross entropy로 Loss function을 두는 것이다.(여기선 Binary corss entropy)

- 이를 이용해 다음과 같이 Parent와 child의 평균지점의 거리를 대신해서 사용하게 된다.

 

2. Regression Tree

- 이번엔 스키를 탈 수 있는지의 여부가 아닌 강설량을 예측하고자 한다고 해보자.

 

- 마찬가지로 지역을 다음과 같이 나눌 수 있을것이다.

 

- 우리가 예측하고자 하는건 이렇게 나눈 지역의 강설량의 평균이라고 해보자.

- 여기서 Loss Function을 MSE을 사용하여 나타낸다고 한다.

 

cf) 어떤한 학생의 질문인데, 어떻게 분할을 찾을것인가의 질문에 BruteForce Algorithms을 이용한다고 한다.

+ categorical Variables로도 모델을 만들수 있다.

 

3. Regularization of Decision Trees

- 여기서 모델을 극한까지 훈련시킨다면 데이터 한개를 하나의 Region이라고 생각해버리는 경우가 발생한다.

- 이때 우리는 Overfitting이 일어난다고 판단할 수 있는데, 이렇기에 Decision tree는 high variance model이라고 불린다.

- 따라서 이를 Regularization을 해줘야한다. 그 방식은 다음과 같다.

i) min leaf size를 정한다.

ii) max depth

iii) max number of nodes

iv) min decrease in Loss

v) Pruning (misclassification with val dataset)

 

4. Decision Tree의 장단점

4.1. 장점

1) 설명하기 쉽다.

2) Categorical Variables에 유용하다.

3) 아주 빠르다.

 

4.2. 단점

1) High Variance model이다.

2) Bad at additive

3) Low predictive accuracy를 갖는다.

 

- 사실 이러한 단점이 많은 Decision tree를 알아야하는 이유가 뭘까?

- 그 답은 Ensemble을 통해 dicision tree를 더 개선할 수 있다는 것이다.

 

5. Ensemble

 - Ensemble이 도움이 되는 이유가 뭘까?

- 우선 X_i라는 random variables(RV)가 있다고 해보자.(iid 하다고 가정하자)

- Var(x_i) = sigma^2 이라고 하자.

 

- 만일 independence를 제외한다면 어떻게 될까? 

- 즉 x_i are id라고 가정하자

- 즉 x_i간의 상관관계가 있다고 가정하는 것인데, 이때의 상관계수를 p라고 두면 다음과 같은 식이 나오게 된다.

- 해당 식을 보면, n이 커지면 커질수록 분산이 작아지게 되는데, 이 이론을 적용한게 ensemble 기법이다.

- 이러한 ensemble기법은 여러 종류가 존재한다.

1) different algorithms (여러 기법을 적용해 평균내기)

2) different training sets(각기 다른 훈련데이터 사용)

3) Bagging (Random Forests)

4) Boosting(Adaboost, xgboost)

 

- 보통 3),4)를 많이사용하게 된다고 한다.

- 그 이유는 새로운 알고리즘을 적용하거나 데이터셋을 더 많이 불러오는 것보다 효율적이기 때문이다.

5.1. Bagging 

- Bagging은 다른 말로 Boostrap Aggregation이라고 한다.

- Boostrap이란 통계에서 추정치의 불확실성을 측정하는 데 일반적으로 사용되는 방법이다.

- Bagging을 이해하기 위해 다음 예시를 들어보자.

- 우리는 모집단 P에서 sample S를 뽑아 train set으로 사용한다.

- 이때 우리는 S == P 라고 가정하고 모델을 만든다.

- 이때 bootstrap이라는 테크닉을 추가하는데, 이것은 S에서 또다시 sample을 추출하는 것을 의미한다.

- 즉, S에서 Z라는 sample을 뽑아 이것을 train으로 이용하는 것이다. (해당 sample을 Bootstrap sample이라고 한다.)

- Bootstrap Sample이 Z_1,...Z_m까지 있다고 해보자.

- G_m이라는 모델로 학습한다고 할때, 다음과 같이 평균을 내게 된다.

- 이러한 bagging은 다음 식에 의해 분산을 낮춰주는 역할을 하게 된다는 것을 알 수 있다.(n이 커지기 때문)

 

- Dicision tree가 high variance이라는 단점이 있었는데 bagging이 그 단점을 커버하는 것을 확인할 수 있다.

- 그래서 bagging과 dicision tree는 잘 맞는 쌍이라고 한다.

- 그래서 Dicision tree와 bagging이 합쳐진 알고리즘을 random forest라고 한다.

 

5.2. Boosting

- 앞서 Bagging이 분산을 낮춰주는 아이였다면,

- Boosting은 bias를 낮춰주는 아이다.

- Boosting은 Weak Learner들을 순차적으로 결합하여 Strong Learner로 만드는 Ensemble기법이다.

- Boosting은 데이터의 반복적 학습 과정을 통해 약한 학습기의 오류를 보완한다.

-- 약한 학습기를 순차적으로 학습

-- 각 학습기가 학습하지 못한 오류에 더 많은 가중치를 둠

-- 최종적으로 여러 학습기를 결합하여 성능을 높인다.