[ML] Tree-based Methods 2편 (Bagging, Random Forests, Boosting)

본 게시글은

서울대학교 데이터사이언스대학원 오민환 교수님의

데이터사이언스를 위한 머신러닝 및 딥러닝1 수업을

학습을 목적으로 재구성하였습니다

---

 

지난 시간에 이어서 오늘은 tree-based method 

bagging, random forests, boosting에 대해서 배워본다

 

 

 

 

우선 bagging에 대해서 살펴보자

 

지난 시간에 tree-based method들의 장단점에 대해서 배웠었는데

단점부터 살펴보자면 우선 decision tree는

prediction accuracy가 그렇게 썩 좋지 않았다

bagging은 이러한 낮은 성능을 극복하기 위한 방법이다

 

bagging을 지금은 decision tree에 적용할 수 있는 방법으로 배우고있지만

bagging은 굉장히 general한 method이다

 

bagging에 대해서 쉽게 표현하자면

bootstrap으로 생성한 데이터로 학습시킨 각각의 모델들을

aggregate 시킨 것이다

 

우리가 이전에 한 번 배웠는데 어떤 데이터셋을 평균을 내면

variance도 데이터 개수만큼 나눠지기 때문에

variance가 낮아진다는 장점이 있다

 

따라서 observation들을 잘 averaging 한다면

variance를 낮춰주기 때문에 prediction이 더 좋아질수가 있다

 

따라서 평균을 내서 variance를 낮춰주기 위해서

bootstrap을 사용을 하는 것이다

 

 

 

bootstrap은 우리가 이전에도 잠깐 배웠는데

training data 자체는 1개지만 마치 여러 개인 것처럼 만드는 것이었다

따라서 bagging은 이렇게 bootstrap으로 만든 여러 개의 training dataset에

각각의 decision tree를 fit 시키고

그런 다음 각 decision tree들의 aggregate한 prediction 값을 가져오는 것이다

 

다시 한 번 정리하면 bagging을 한다는 것은 

training dataset에서 sample들을 여러 개를 만들어내서 

bootstrap dataset을 만든다

 

그렇게 총 B개의 training data copy를 생성하면

각각의 bootstrap data에서 학습된 모델을 f^b(x)라고 한다

그래서 각 f^b(x) 모델에서 나온 prediction의 평균값을

이 bagging의 output으로 보는 것이다

 

한 마디로 training data에서 B개를 bootstrap으로 만든 다음

각각의 bootstrap dataset에서 seperate한 function들을 만들고

그 function들의 전체의 평균값을 전체 bagging된 function의 output으로 보는 것이다

 

 

 

 

 

그렇다면 bagging에서 classification은?

regression은 우리가 위에서 말한 것처럼 그냥 평균값으로 하면 되는데

classification은 어떻게 할 수 있을까?

 

동일하게 각각의 bootstrap dataset에서 classification을 위한

decision tree들을 학습시킨 다음

전체에서 가장 표를 많이 받은

즉, majority vote를 선택하면 되는 것이다

 

한 마디로 bagging은 bootstrap을 활용해서

여러 개의 decision tree를 묶는 것이다

 

 

 

 

 

 

bagging을 활용해서 performance가 얼마나 좋아졌는지 한 번 보자

위 그래프에서 x는 number of trees이고

y는 error rate이다

heart data라서 classification task이다

 

까만색 실선이 bagging

노란색 실선은 우리가 뒤에 배울 random forests

초록색과 파란색도 각각 bagging과 random forests인데

test가 아니고 out of bagging으로 측정한 값이다

 

잠깐 out of bagging(oob)에 대해 설명을 하자면

우리가 bootstrap할 때 bootstrap copy로 가는 것이

실제 데이터의 3분의 2정도가 간다고 했다

그럼 bootstrap copy로 가지 않는 데이터는 3분의 1정도일텐데

얘네들을 prediction하는 것을 out of bagging이라고 한다

근데 그냥 cross-validation으로 해도 된다고한다..

 

아무튼 위 그래프를 보면 bagging에서 tree가 증가하면 증가할수록

에러가 조금씩 낮아지는 것을 확인할 수 있다

우리가 뒤에서 볼 random forests도 마찬가지

 

그럼 bagging에서 tree가 300개 있다는 것은

bootstrap을 총 몇 번 했다는 뜻인가?

당연히 300번 했다는 뜻이다

 

그럼 여기서 한 번 생각해볼만한게 있다

이게 tree의 개수가 증가하면 overfit이 발생할까?

위 그래프를 슥 봤을 때는 딱히 tree의 개수가 증가할 때마다

딱히 overfit이 되고있다는 생각은 들지 않는다

 

결론부터 얘기하자면 bagging도

뒤에서 배울 random forests도

tree의 개수가 증가한다고해서 overfit이 발생하지 않는다

이걸 이해하려면 overfit이 정확하게 뭔지를 이해해야한다

overfit이란 training data의 noise마저 fit을 시키는 것을 의미한다

하지만 bagging도 random forests도

tree를 여러 개 만든다고 해서 각각의 training data의 noise에

fit을 시키는 것이 아니기 때문이다

 

 

 

 

 

이제 random forests에 대해서 살펴보자

 

random forests는 bagging에서 아주 조금 modification을 한 것이다

bagging에서 여러 개의 tree들이 나오는데

random forests는 각 tree들의 correlation을 감소하고자 한 것이다

tree들의 correlation을 감소함으로써 variance를 감소시키는 것이다

 

random forests도 bagging과 동일하게

bootstrap training sample을 만들어서

각각의 deicision tree를 fit 시킨다

여기까지는 똑같은데 decision tree를 build하는 과정이 조금 다르다

 

우리가 decision tree를 build 할 때 계속해서 split을 하는데

이때 random forests는 전체 predictor의 개수 p개에서

전체 p개의 Predictor를 모두 활용하는 것이 아니고

p개 중에서 randomly m개의 subset을 나눈다음 거기서만 split을 한다

 

다시 한 번 정리하자면

예를 들어서 100개의 predictor가 있다고 하자

어떤 predictor를 어디서 자를지 결정하는게 decision tree인데

split을 할 때 전체 100개를 대상으로 하는 것이 아니고

m=10이라고 한다면 100개 중에서 10개만 randomly sample 한 다음

그 10개 중에서만 split을 수행하겠다는 뜻이다

그리고 또 다음 split에서는 새로 10개를 뽑고 그 안에서 split을 수행한다

그리고 그걸 계속해서 반복하는 것이다 

우리가 bagging을 수행할 때는 각각의 트리들이 비슷할 수가 있는데

random forests에서는 이 트리들을 덜 비슷하게하고자 하는 것이다

 

전체 predictor p개 중에서 m개를 선택하는거니까

m은 p보다 작아야하고 m=p이면 결국 그냥 bagging이 되는 것이다

m<p인 경우가 random forests이다

그런데 보통 m은 루트p 정도로 설정한다고한다

 

즉, random forests는 bagging과 크게 다르지 않은데

random forests의 가장 큰 차이점은 split할 때

m개의 subset 안에서만 수행한다는 점이다

이로 인해 각 tree들이 조금씩 달라지게 되고 correlation이 작아지면서

variance가 작아진다

 

 

 

 

그렇다면 위 gene data로 예시를 한 번 살펴보자

349명의 환자로부터 얻은 4718개의 gene 데이터가 있고

이는 15개의 class로 classification 될 수가 있다

 

우선 y값은 보지 않고 training set에서 variance가 높은

500개의 gene data만 일단 가져왔다

training dataset과 test dataset은 randomly 나누었고

training set에서 m을 여러가지로 바꿔가며

random forests를 수행했다

 

 

 

 

test data에서 error를 측정한 것이다

 

class가 15개인 task인데 사실 이게 되게 어려운 task이다

이걸 random forests로 수행했다

 

그리고 위 데이터에 사실 predictor가 되게 많은데

그 중에서 500개만 뽑았다고 한다

그 다음에 계속해서 m값을 바꿔가면서 random forests를 수행했다

 

m=p인건 그냥 bagging이고 25% 정도의 error rate를

보이고 있는 것을 확인할 수 있다

 

그리고 p/2도 어느정도 비슷한 error rate을 보이는데

루트 p정도가 확실히 다른거에 비해서 error rate이 낮은 것을 알 수 있다

그럼 여기서의 메세지가 뭘까?

일단 루트 p가 가장 성능이 좋았다는 것인데

m이 무조건 작다고 좋다는게 아니라는 뜻이다

 

적당한 제약을 두니까 tree간의 correlation이 작아졌고

그래서 variance가 감소해서 prediction이 더 좋아진 것이다

이걸 single decision tree로 했을 때는 0.45정도가 나온다고한다

 

15개의 class를 classification 하는 것은

굉장히 어려운 task라서 이정도 error rate은 굉장히 잘하는 것이다

 

random forests도 역시 tree 개수 증가에 따라

overfitting은 발생하지 않는다

overfitting은 트리의 개수보다는 깊이와 더 관련이 있다

 

tree의 개수가 증가하면 계산량이 증가하긴 하겠지만

그렇게 sensitive하지 않다

그래서 그냥 tree의 개수는 적당히 잘..하면 된다고한다 ㅋㅋ

 

 

 

boosting에 대해서도 배워보자

boosting도 마찬가지로 bagging처럼 general한 메소드이다

 

random forests는 bagging을 적절히

tree라는 구조에 잘 맞게 한 테크닉인거고

bagging 자체는 general approach이다

꼭 decision tree에서만 사용되는 것은 아니다

 

우리 앞에서 배운 bagging을 잘 생각해보면

오리지널 데이터셋을 multiple copy로 만든 다음에

각각의 seperate한 decision tree들을 잘 합쳐서 평균내는 거였다

여기서 잘 생각해보면 각각의 bootstrap에서

학습된 tree들은 다 독립적으로 해당 데이터셋에 학습이 된 것이다

다른 tree들이 어떻게 학습했냐에 영향을 받지 않는다

각각의 주어진 bootstrap 데이터에 독립적으로 학습을 하는데

이건 bagging, random forests가 모두 동일하다

 

그런데 boosting은 여러 개의 트리를 만드는 것은 맞는데

얘네들이 sequentially tree가 grow한다는 점이 다르다

즉, 여러 개의 트리를 만드는 것은 맞지만

트리를 만드는 과정이 전의 트리가 어떻게 학습이 되었느냐를 바탕으로

다음 트리가 생성되게 된다

이게 fundamental한 차이점이다

 

 

 

 

 

앞의 bagging과 random forests가 너무 간단했어서

boosting은 상대적으로 복잡하게 느껴질 수 있다

차근차근 한 번 살펴보자

 

boosting은 training dataset 1개가 우선 있다고 한다

다른 bagging이나 random forest처럼 training dataset을 여러개 만들지 않는다

그리고 몇 개의 트리를 만들지 정하는 B라는 하이퍼파라미터가 있다

여기서 중요한 점은 bagging과 random forests와는 달리

한 개의 데이터셋만 존재한다는 점이다

 

처음에 우리는 initial model을 만들거다

그런데 이 initial model은 모든 input에 대해서

output을 0으로 내뱉은 그냥 constant function을 한 개 잡을거다

 

여기에다 residual인 r을 define하는데

맨 처음은 그냥 모든 output에 대해서 0으로 뱉는 function이기 때문에

각 데이터포인트 i에 대한 residual ri는 yi와 동일하다

다시 정리하면 initial model의 prediction은 모두 0이기 때문에

residual r도 그냥 y 라벨 값이 되고

모든 observation에 대해서 그렇게 세팅을 한다

 

그런 다음 우리가 B번 iteration을 반복하는데

B의 small b인 b번째 모델에서 tree를 fit 시키는데

tree를 fit 시킬 때 몇 번을 split할건지 정하는 하이퍼파라미터 d를 정의한다

일반적으로 d는 되게 작은 수가 된다

정말 extreme한 경우는 d=1일때도 있다

즉, 한번만 split한다는 뜻이다

split을 우리가 d번 한다는 것은

terminal node가 d+1개가 된다는 뜻이다

 

아무튼 우리가 이 boosting은 순차적으로 트리모델을 fit 시킨다고 했는데

데이터 {xi, yi}로 fit을 시키는게 아니고

우리가 아까 정의한 residual ri를 사용해서

{xi, ri}로 만들어진 surrogate dataset에다가 tree를 fit 시킨다

 

첫 번째 iteration에서는 residual이 그냥 y label이니까

첫번째 iteration에서만 original dataset에 fit을 시키는 것이다

그 이후부터는 residual ri는 계속해서 변하기 때문이다

 

 

그 다음 2.2를 보면 위 식처럼 f^을 update 한다고 나와있다

우리가 surrogate dataset으로 fit 시킨 f^b(x) 모델을

람다를 이용해서 살짝만 shrink 시킨 뒤에 다시 f^(x)에 update한다

따라서 initial에는 그냥 0이었기 때문에 shrink된 모델만 update되는 것이다

이런 방식으로 계속해서 fit시킨 모델들이 add가 된다

 

매번 모델 fit을 수행시킬때마다 residual도 update된다

방금 우리가 학습해서 update한 f^b(x)를 가지고

현재 residual에 빼주면서 update 시킨다

 

그렇다면 initial model을 예시로 순서를 한 번 정리해보자

 

1. 모든 output이 0인 constant function f^(x) 정의

2. 첫 번째 iteration에서 residual은 y label과 동일하므로 {xi, yi}로 모델 fitting

3. 새로 fitting한 모델*람다를 기존 f^(x)에 더해서 update

4. 기존 residual에서 새로 update된 모델의 prediction값을 빼주며 residual update

5. 이 과정을 B번 반복

 

 

boosting에서 모델 update를 시켜줄 때

이전까지의 모델에서 계속해서 새로 fitting시킨 모델 * 람다를 더해주는데

그럼 이게 최종적으로는

그냥 모든 B개의 모델에 람다만큼 shrink한 것을 더해준 형태가 된다

 

최종 bagging 모델의 output은 위와 같이 되는 것이다

 

그럼 이게 정확하게 어떤 의미를 가지냐?

의미론적으로 기존의 base tree들이 이전에서 학습된 것만큼은 제외하고

나머지 학습되지 못한 부분들을 계속 보완하면서

sequentially building을 수행하는 것이다

 

즉, boosting에서 residual이 갖는 의미는

이전 모델들이 제대로 학습한 것은 학습이 잘 되었으니까 덜어내고

이전 모델들이 틀리는 부분, 학습이 잘 되지 못한 부분을

그 다음 tree가 학습을 할 수 있도록 계속해서 보완을 하는 것이다

 

그리고 매번 모델을 update하는 과정에서

람다를 곱해서 모델을 shrink 해주는 이유는

학습을 천천히 시키기 위함이다

 

아무튼 개념적으로는 연속적으로 가면서

이전 모델이 못했던 것을 다음 모델을 이용해서 보완하겠다는 뜻이고

람다만큼 shrink 시키면서 그 학습을 천천히 수행하겠다는 뜻이다

그래서 일반적인 람다는 보통 0.001 이정도로 매우 작다

 

사실 람다가 1이면 그냥 shrink 없이

이전 모델이 학습못한 부분을 모두 다 보완하겠다는 것인데

이런 방식보다는 천천히 조금씩 보완해나가는 것이 좋다고 한다

 

그리고 람다가 너무 작으면 모델 성능이 안좋을 수 있기 때문에

거기에 맞춰서 충분히 학습할 수 있게끔 B도 커져야한다

 

 

 

 

 

결국 boosting이 하고자하는 것은

우리가 엄청 큰 트리를 가지고 데이터를 한 번에 학습시키자는게 아니고

작은 트리를 가지고 천천히 학습시키자는 것이다

 

즉, 큰 트리를 가지고 hard하게 한번에 확 학습시키는게 아니고

작은 트리를 가지고 slowly softly하게 학습시키는 것이다

 

여기서 또 중요한 점은 base model이 되는 트리에서

d번 split 할 때의 이 d가 매우 작다

심지어는 딱 1번만 split하는 경우도 있는데

이렇게 하는게 실제로 performance가 매우 좋다고 한다

작은 tree를 조금씩 조금씩 fit을 시키게 만드는 것이다

 

 

 

 

boosting에서의 classification도 알아보자

 

classification도 regression과 학습 과정을 동일하다

하지만 조금 더 복잡한 것은 residual의 개념이

regression처럼 단순히 prediction에서 빼버리는 것이 아니기 때문이다

 

일단 개념적으로는 true label에서 estimate된 probability를 빼는 방식인데

이건 그냥 알아만 두면 좋다고 한다

 

 

 

앞의 bagging과 random forests는

tree의 개수인 B가 커진다고해서 overfitting이 발생하지 않는다고 했다

그러나 boosting같은 경우는 순차적으로 모델 fitting을 하기 때문에

B가 너무 늘어나게 되면 overfit이 될 수도 있다

하지만 우리가 생각하는 것보다 엄청 커져야한다고한다

 

람다가 크면 B가 조금만 커도 overfit이 될 수 있는데

람다가 작으면 천천히 학습되기 때문에

B가 커도 overfit이 금방 생기지는 않는다고 한다

 

결국 람다가 작아질 때 이게 학습이 잘 되려면

베이스모델의 개수인 B가 커져야하는 것인데

이 두개의 균형이 잘 맞아야한다

 

boosting에서 우리가 정해야하는 하이퍼파라미터는 d, B, 람다인데

d는 1인 경우가 굉장히 많이 쓰인다고 한다

딱 한번만 split 하겠다는 것인데 이걸 stump라고 한다고 한다

왜 굳이 d=1로 해주냐?

어차피 다 slowly 학습할 것이기 때문이다

 

그럼 여기서 적당한 하이퍼파라미터들을 찾기 위해서는

우리가 이전에도 그랬던 것처럼 cross-validation을 수행해주면된다

 

그런데 이 3개의 하이퍼파라미터들을 다 찾아주는게 쉽지않을 것 같은데 괜찮을까?

 

 

 

 

 

다행인건 이 하이퍼파라미터들이

그정도로 sensitive하지는 않다

 

아까봤던 gene 데이터에서 class가 15개가 있는데

이 performance를 랜덤포레스트와 비교한것이다

random forest에 비해서 boosting으로 한게 성능이 현저히 좋은 것을 알 수 있다

 

위에서 boosting을 했을 때 d를 1과 2로 한 것을 알 수 있는데

d가 1인 경우가 성능이 더 좋다

트리 개수가 적당히 한 1000개 정도 일 때는

d=2인게 조금 더 좋아보였는데

충분히 tree개수를 키우니까 d가 1인 boosting의 error rate이

거의 뭐 0.1보다도 작아졌다

 

이 15개의 class에 대해서 classification 한다는 것이

굉장히 어려운 task인데도 불구하고 error rate이 10%보다 작다는 것이다

베이스 모델들은 굉장히 simple한데 퍼포먼스가 굉장히 좋다

그리고 B와 람다 하이퍼파라미터에 그렇게 sensitive하지않다

 

B가 너무 커지면 overfitting이 일어날 수 있는데

람다가 작으면 어느정도는 보완이 된다

위 예시에서도 트리가 5000개나 있었는데도 overfitting은 일어나지 않았다

 

이렇게 여러 개의 tree를 학습시키는게 오래 걸리지 않냐는 질문이 나왔는데

depth가 작기 때문에 트리 한 개를 학습시키는 속도가 매우 빠르다고한다

 

 

 

 

 

다른 데이터셋의 경우도 한 번 살펴보자

random forests와 boosting의 예시이다

 

트리가 적당한 사이즈였을 때는 performance reduction이

굉장히 빠른 것을 확인할 수 있다

그러다가 시간이 지나면 어느정도 평평해진다

 

gradient boosting method들은 depth가 4나 6정도 됐을 때

랜덤포레스트보다 잘되는 것을 볼 수 있다

depth가 크면 크면 클수록, B가 커질수록 overfitting이 생길 수 있다

 

 

 

 

다른 데이터에서도 이메일 스팸여부를 가지고

bagging, random forest, boosting을 수행했다

 

위 3개 중에서는 역시 boosting이 가장 error rate가 낮다

맨 처음에는 random forests가 가장 성능이 좋은가 싶더니

tree 개수가 증가하면서 천천히 boosting이 성능이 높아지는 것을 볼 수 있다

 

boosting 모델의 단점을 꼽자면

어떻게든 얘네들은 순차적으로 학습을 시켜야하기 때문에

parallel하게 수행하는 것이 불가능하다

하지만 bagging과 random forests는 parallel이 가능하다

 

보통 현업에서는 퍼포먼스를 끌어올리기 위해서

대부분 boosting을 많이 사용한다고 한다

XGBoost나 이런 모델들이 현업에서 보통 SOTA를 찍는다고 한다

 

그리고 boosting은 꼭 tree-based model이 아닌

다른 모델들을 사용해도 상관없다

 

 

 

 

bagging을 하건 random forests를 하건

우리가 이 variable들 중에서 어떤게 더 중요한지 알고싶을 수 있다

 

우리가 얘네들을 split 할 때마다 RSS의 reduction이 있을 것이고

그럼 해당 predictor을 잘랐을 때 RSS reduction이 커지면

그 predictor가 중요하다고 볼 수 있다

 

학습하면서 그런것들을 계속해서 체킹할 수 있고

어떤 variable을 잘랐을 때 퍼포먼스가 어떻게 가장 향상이 되었는지 볼 수 있다

그래서 그런 것들을 keep해서 variable의

importance measure을 수행할 수 있다

 

classification의 경우 variable의 gini index reduction이

가장 컸던 것을 중요하다고 볼 수 있다

 

아무튼 그래서 우리는 어떤 feature를 잘랐을 때

가장 효과가 좋았는지를 위처럼 나열할 수 있다

 

 

 

그렇다면 오늘 배운 것을 정리해보자

 

decision tree는 굉장히 simple한데 비해서

prediction performance는 상대적으로 좋지 않다

 

bagging이나 random forests만 봐도 

simple decision tree보다는 성능이 훨씬 좋다

 

random forests나 boosting같은 경우는

supervised learning에서는 대부분 SOTA를 찍는 방법론들이라서 알아두면 좋다

하지만 이렇게 갈수록 decision tree가 갖고있던 장점인

해석력은 점점 떨어지게 된다

 

우리가 랜덤포레스트로 위에서 봤던 variable importance는 구할 수 있어도

모델의 해석 자체는 어려워지게 되는 것이다