목차
1. 소개
2. XGBOOST 흐름
3. 논문속 수식으로 이해
4. 참고자료
1 . 소개
앙상블(ensemble) 방법이란
티끌 모아 태산이라는 아이디어를 담고있다.
성능이 좋지 않은 분류기를 여러개 모아서 합치면 좋은 성능을 낸다는 것이다.
자세히 말하면, 분류기 하나(A Decision Tree)는 특정 몇개의 특성에 대해서 판단할 수 있지만,
분류기 여러개(Decision Trees)를 사용해 나온 결과를 종합해서 최종 결과를 낸다면
=> 모든 분류기에서 사용된 특성 판단 조건들(Decision Nodes)을 모두 어느 정도 사용을 할 수 있어서
=> 차원 높은 분류가 가능해진다.
이런 앙상블 방법에는
1. Bagging
2. Boosting
등이 있다.
1. Bagging (bootstrap aggregating의 줄임말)
Bagging이란 각 Decision Tree를 학습할 때, 전체 학습데이터 중에 일정량 만큼 임의로 뽑은 데이터를 사용하는 것이다.
(학습 데이터를 뽑을 때는 매번 전체 학습데이터 중에서 일정량을 임의로 뽑는다.)
=> 샘플을 임의로 뽑기 때문에 Tree의 다양성이 증가한다.
( 더 깊히 말하자면, 모델이 학습하려는 데이터의 의미없는 sequence 경향성을 학습하는 것을 방지할 수 있다.)
2. Boosting
Boosting이란 약한 분류기(weak learners(classifier)) 여러개들을 합쳐서 높은 차원의 분류를 해내는 것이다.
=> 그리고 Boosting은 새로운 분류기를 만들기 위해 약한 분류기들을 합쳐 나갈수록 점점 성능이 올라가게 된다는 뜻에서 Boosting이라는 이름이 붙었다.
그 중에서 AdaBoost(Adaptive Boost)를 그림으로 보면 다음과 같다.
boosting 과정을 따라가보면 다음과 같다.
맨 처음 데이터에 대하여 분류를 한다.
파란색은 '-'를, 빨간색은 '+'를 포함하는 영역으로 분류하는 것인데,
오류값인 '-' 두개와, '+' 하나가 보인다. => 이 값에 가중치를 부여한다.
=> 다음 분류를 할 때, 강한 영향력을 갖는 샘플이 된다.
가중치 부여 처리가 된 샘플들에 대해 다시 분류를 한다.
이번에는 '-' 3개가 오류값이 되었다 => 이 값에 가중치 부여
마지막으로 분류를 해보니 오류값이 없다.
=> 최종적으로 앞서 분류했던 분류기들을 모두 합친다. => 고차원의 분류기가 완성된다.
: 이와 같이 이전 값에 따라 현재의 학습 방식에 변화를 계속 주는 것을 adaptive하다고 한다.
+ Boosting 알고리즘은 분류 후에 가중치를 다시 부여하는 방식에 따라 여러개로 나뉜다.
1. AdaBoost
2. GBM
3. XGBM
등..
글의 제목인 XGBM을 이해하려면, GBM(Gradient Boost Machine)을 먼저 알아야 한다.
2022.10.10 - [머신러닝(기계학습)] - GBM(Gradient Boost Machine)이란? +학습이 되는 원리 자세히 설명
GBM이란 실제값과 예측값의 차이(잔차)를 예측해서 => 차이와 차이의 예측값이 점점 줄어들게 되고 => 차이가 0으로 수렴하게 되는 성질을 이용해
예측과정에서 사용했던 Tree들을 매번 예측할 때 마다 결합하면서 Tree의 성능을 향상(Boost)시켜나가는 것이다.
하지만 문제가 있다.
1. 느리다.(GD의 단점..)
2. 과적합( GBM에서는 과적합을 막기 위한 스킬이 들어가지만 부족하다.)
이를 보완하는 XGBOOST가 나왔다.
1. GBM보다 빠르고
2. 손실함수에 과적합 방지를 위한 파라미터 존재
3. CART(Classification And Regression Tree) 기반이므로 분류와 회귀 모두 가능
이제부터 논문과 공식 사이트를보며 완벽하게 이해해보자.
<논문>
https://arxiv.org/pdf/1603.02754.pdf
<공식 사이트>
https://xgboost.readthedocs.io/en/latest/tutorials/model.html#tree-boosting
Introduction to Boosted Trees — xgboost 1.7.0-dev documentation
XGBoost stands for “Extreme Gradient Boosting”, where the term “Gradient Boosting” originates from the paper Greedy Function Approximation: A Gradient Boosting Machine, by Friedman. The gradient boosted trees has been around for a while, and there
xgboost.readthedocs.io
2. XGBOOST 흐름
흐름을 요약해보면 다음과 같다.
1. CART이므로 조건에 따라 이진 분류가 될 텐데,
leaf node안에 들어있는 샘플들의 특정 값 두개(이 값에 대해서는 잠시 뒤에 말하겠다.)를 사용해
각각의 leaf node에 prediction score라는 값(=가중치)을 계산하고
그 값를 leaf안의 샘플들에게 전달한다.
=> 위의 그림에서는 왼쪽 leaf node에는 파란옷과 분홍옷을 입은 사람들의 특정 값 두개를 사용해서 +2라는 값을 구했는데 이 +2라는 값(가중치 w)이 두 사람에게 전달된다. 오른쪽 leaf node도 같은 방식으로 -1이라는 값이 구해져서 세 사람에게 전달된다.
2. 이제 각각의 샘플에 대한 예측값을 찾아야 하는데,
이때 2번에서 샘플에 전달된 prediction score(가중치)를 사용한다.
샘플 하나하나당,
1. 예측값(prediction score)과 실제값(우리가 원하는 샘플의 label: 0 or 1)의 차이를 줄이고,
2. 추가적으로 과적합을 막기 위한 규제(Regularization)를 담은
손실함수(모든 샘플에 대한)를 찾으면
하나의 샘플에 대한 손실함수가 생긴다.
이제 모든 샘플들에 대한 손실함수를 합해서 만든
최종 손실함수의 값은 현재 Tree의 성능을 나타내는 지표가 된다(impurity 점수처럼)
즉, 낮은 값일수록 좋은 Tree인 것이다.
3. 새로운 조건에 대해 1번을 수행한다.
4. 2번을 수행해야 하는데, 샘플의 예측값을 결정하는 과정에서
이번에 만든 Tree의 leaf node에 부여된 가중치만 사용하는 것이 아닌,
이전에 만들었던 모든 Tree에서 해당 샘플에 부여되었던 가중치들까지 모두 더한 값이
해당 샘플의 예측값이 된다.
그래서 만약 파란옷을 입은 남자의 가중치를 계산하고 싶다면,
이전에 Tree1에서 전달받은 가중치 '+2'와 현재 Tree2에서 전달받은 가중치 '+0.9'를 더한 값을
파란옷을 입은 남자(샘플)의 예측값로 설정하고, 이 예측값과
파란옷을 입은 남자가 가져야 하는 실제 값(label : 0 or 1)사이의 차이를 줄여주는 동시에
과적합을 막아주는 손실함수를 최적화하는 손실함수를 구하고, 모든 샘플에 대한 손실함수를 더한 손실함수를 가지고 이번에 만든 Tree를 평가한다.
5. 원하는 Tree의 개수만큼 3~4번 과정을 반복해서 트리들을 만들고 새로 만든 Tree를 평가한다.
6. 하지만, 문제가 있다. 가능한 모든 Tree를 생성해 놓고 계산을 하는것은 계산량 때문에 불가능하다.
그래서 각 나무마다 가지들을 분기할 때,
Gain(분기 전 하나의 손실함수 - 분기 후 두 손실함수 합)이 특정 값을 넘지 못하면(성능 향상이 약하면)
분기를 중단시킨다.(=가지치기 한다:pruning)=> 계산량 감소
가능한 모든 구조를 만들면 위와 같지만, 파란옷과 분홍옷을 분리하는 작업의 Gain이 크지 않다는 것을 발견한다면
다음과 같이 저 (is male?) 이라는 Decision node를 없에고,
파란옷과 분홍옷을 분리하지 않는 가지치기를 할 수 있다.
이를 통해 가장 효율적인 분류를 해낼 수 있다.
3. 논문 속 수식을 보며 이해
이제 앞서 설명한 흐름을 수식으로 정확히 이해해보자.
1. 예측값 구하는 과정
예측값은 K개의 Tree들에 대한 fk를 더한 값이라고 한다.
즉, k=1인 경우에는 하나의 Tree에 대해서
i라는 샘플이 들어있는 leaf node의 가중치 w(=f1)값 하나를 뜻한다.
만약 k=K인 경우에는 K개의 Tree에 대해서
i라는 샘플이 들어있는 leaf node들의 K개의 가중치 w(=fk,k=1,2, ... , K)들의 합이 되는 것이다.
그리고 그에 대한 손실함수는
n개의 sample에 대해 생기는
예측값과 실제값의 차이에 대한 합 + 트리의 복잡도(=규제 :Regularization)
가 된다.
이 값은 트리의 성능을 나타내는 지표가 된다.(impurity와 유사하다)
2. 예측값을 구하는 과정은 Additive Training이다.
0번째 예측값을 0으로 둔다면,
특정 Tree에서의 한 샘플의 예측값은
이전 Tree에서 구한 가중치들의 합들에다가 현재 가중치만을 더함으로써 완성되기 때문에
additive하다고 말할 수 있다. (변화에 적응하면서 학습한다.)
이 additive 하다는 성격 덕분에,
만약 t번째 Tree의 성능(손실함수)를 구할 때라면
i라는 샘플의 t번째 Tree의 예측값 y hat (t)는
i라는 샘플의 t-1번째 Tree의 예측값 y hat (t-1)에다가 현재 가중치 ft(xi)를 더한 값이라고 할 수 있다.
3. 손실함수를 풀어 해쳐보자(근사).
만약 저 차이를 계산하는 함수인 l이 MSE(Mean Squared Error)라면
수식은 다음과 같이 변할 것이다. 하지만 위와 같이 깔끔한 형태로 사용할 수 있는 경우는 제한적이므로,
일반화를 해주기 위해 아까 손실함수
의 l 속의 yi hat (t-1) + ft(xi)를 l이라는 함수 밖으로 꺼내보자. => 테일러 전개를 이용한다. (2차까지 근사)
위를 이용해 꺼내면
다음과 같이 나오게 된다. g는 f'을 뜻하고, h는 f''을 뜻한다.
(정확히는, t-1번번째 예측값 y에 대한 편미분이기는 하다)
yi hat (t-1)은 이전 Tree를 계산할 때 이미 구했으므로, MSE를 나타내는 l함수와 constant는 모두 상수이므로 없에준다.(손실함수를 최적화 하는 변수가 아니므로)
=> 그럼 위와 같은 깔끔한 식이 완성된다.
4. 과적합을 막기위한 규제(Regularization term)
여기서 앞에서 말한 ft(x)=wq(x)라는 벡터가 나온다.( (T : leaf node)의 개수만큼의 차원을 가진다)
+q(x) : x가 Tree를 따라 내려갔을때 위치하는 leaf node에 해당하는 index 값(1부터 T까지,T : leaf node 개수)
왜 벡터인가? 시각화 하면 이해하기 쉽다.
만약 A,B,C,D,E라는 샘플이 2개의 leaf node로 분리되었다고 치자,
우리는 연산을 할 때 계산 단순화를 위해 행렬을 사용한다.
행렬 덕분에 우리는 예측값을 Xw라는 행렬 곱으로 간단하게 나타낼 수 있다.
<X행렬 (nxT 행렬 n :샘플 개수, T :leaf node 개수)>
-행벡터는 leaf node 개수만큼의 차원을 가지며, 샘플이 포함된 leaf node의 위치를 나타내는 hot 벡터이다.
-그리고 각 행은 샘플을 나타낸다.
<w벡터 (Tx1행렬 T: leaf node 개수)>
-각 leaf node가 가져야 하는 가중치 w가 계산된 채로 각 열로 저장이 된다.
이제 이 행렬을 곱하면 모든 샘플에 대한 예측값이 하나의 열벡터로 반환된다.
+ 추가적인 이해에 도움을 주는 답변
How does gradient boosting calculate probability estimates?
I have been trying to understand gradient boosting reading various blogs, websites and trying to find my answer by looking through for example the XGBoost source code. However, I cannot seem to fin...
stats.stackexchange.com
그리고 Regularization부분을 보면
과적합을 줄이기 위해서, 일단 w의 제곱을 넣어줌으로써 L2 Regularization을 적용함과 동시에
γT라는 항을 추가해준다. (γ : hyperparameter , T : leaf node의 개수)
5. 최종 손실함수 및 가중치w(leaf node의 prediction score)계산 방법
이때 아래와 같은 손실함수 식은
다음과 같은 손실함수 식으로 쓸 수 있다.
그 이유는 하나의 leaf node 에 존재하는 샘플들은 같은 가중치 wj (= ft(xi)) 를 공유하기 때문이다.
즉, 시그마를 통해 샘플 하나하나를 접근하면서 가중치와 그 샘플의 g,h를 곱하는 것이 아니라,
시그마를 통해 leaf node를 하나하나씩 접근하면서 해당 leaf node의 가중치에 대해 그 샘플들의 g,h를 곱하고자 하는 것이다.
수식의 gf 부분만 보면 다음과 같이 변환되는 것이다.
그림으로 보면
각 leaf node는 w1,w2라는 가중치를 가지며,
샘플 x1,x2의 g1,g2 에는 w1이 곱해지고 더하고,
샘플 x3의 g3에는 w2가 곱해지고 더하기 때문에
하나의 샘플마다 가중치가 무엇인지 찾아서 곱해서 모두 더하는 것 보다는
가중치가 같은 leaf node 단위로 접근해서 그 가중치에 대해 leaf node 안에 있는 모든 g와h를 합한 것을 사용하는 것이 더 간결하고 다음에 다룰 예정인 wj의 극소값을 찾는데 도움을 줄 수 있다.
이때 손실함수를 최소화 하는 최적의(Optimal) wj*는 다음과 같다.
그 이유는 시그마 안의 수식인
는, wj의 이차식이므로, ax2+bx+c=0의 극솟점은
x = -b/2a 이므로, (이번의 경우 a=1/2(시그마 h+람다) , b=시그마 g)
극솟점 wj는 위와 같은 값이 된다.
최종적으로 대괄호 [ ] 안의 값을 optimal wj*에 대하여 정리하면 다음과 같은 손실함수가 나온다.
=> 즉, 하나의 Tree의 성능(손실함수) 점수는 차이 함수(L)의 편미분 g, h 에 의해서 결정된다는 것을 알 수 있다.
6. 가지치기를 위한 Gain(Lsplit) 구하기
앞서 말했다 싶이, 모든 특성에 대해 가지를 내리는 것이 효율적이지 않을 수 있다.
그래서 다음과 같이 분기를 할 때 마다
(분기 이전 손실함수 - 분기 이후 두개의 손실함수) - 규제(γ)
라는 Lsplit을 구해서 만약 Gain이 규제(γ)값보다 크지 않다면,
Lsplit(Gain)가 음수가 나올 것이고, 이러면 분기하지 않는것이 더 효율적이다.
4. 가중치는 mean(평균)이 아니라 특정 수식(차이를 구하는 함수 l 의 편미분값들로 만든 값)을 통해 나오는 값이다.
In XGboost are weights estimated for each sample and then averaged
The weights in XGBoost are determined by gradient boosting. So, each sample gets a weight and as each leaf has multiple samples, initially each leaf has multiple weights. But, as a single weight is
stats.stackexchange.com
'머신러닝(기계학습)' 카테고리의 다른 글
| GBM(Gradient Boost Machine)이란? +학습이 되는 원리 자세히 설명 (0) | 2022.10.10 |
|---|---|
| Decision Tree(의사결정나무) (0) | 2022.10.10 |