XGBoost : A Scalable Tree Boodsting System을 읽고 참고하여 작성
XGBoost
eXtreme Gradient Boosting
gradient boosting은 이전 학습기의 결과를 이어받아 순차적으로 학습하기에 시간이 많이 걸리는 게 단점
속도와 정확도면에서 개선한 모델
기존 Gradient Tree Boosting 알고리즘에 과적합 방지를 위한 기법이 추가된 지도학습 알고리즘
기본학습기를 decision tree로 하며 gradient boosting과 같이 잔차를 이용하여 이전 모형의 약점을 보완하는 방식으로 학습
손실함수가 최대한 감소하도록 하는 분할점(split point)를 찾는 모델
Regression, Classification 모두 지원
트리부스팅 방식에 경사하강법을 통해 최적화
XGBoost Algorithm
Gradient Booting사용
2차 근사식이 좋은 이유는, t번 째 iteration에서 최종 손실함수가 gi,hi에 의존하여 최적화할 수 있기 때문에, 손실함수의 종류와 관계없이 간단하게 계산할 수 있다는 점이다.
모든 가능한 트리를 나열하여 최적 트리를 찾는 것은 거의 불가능하기 때문에, 2차 근사식을 바탕으로 한 손실함수를 토대로 매 iteration마다 하나의 leaf로부터 가지를 늘려나가는 것이 효율적입니다. 가지를 늘렸을 때 (7)번 식으로 나타나는손실 함수가 최대한 감소하도록 하는 split point를 찾는 것이 XGBoost의 목표입니다.
L split = 가지를 늘렸을 때 손실함수의 감소량
가지를 나누기 전의 손실함수에서 가지를 나눈 후의 손실함수를 뺀 식 (왼쪽,오른쪽의 score더하고 부모노드점수뺌)
-> 트리를 학습하며 가지를 늘릴때마다 사용되는 식
감마 : 무한히 분기하면 오버피팅됨, 그렇기에 가지를 만들지 말지에 대한 기준이 됨
information gain < 감마 , 가지는 제거
즉, 가지를 먼저 만들고 나서 (information gain - 감마) = 음수면 가지 제거, 양수면 가지 놔둠
람다 : regularization의 파라미터, 람다의 값이 크면 전체 score를 줄여준다는 뜻
람다가 클수록 (information gain - 감마) = 음수가 많아져 제거되는 가지가 많아짐 -> 오버피팅 방지
정규화된 목표외의 과적합 방지하는 2가지 기술
1. Shrinkage
직전 iteration까지 학습된 트리의 모든 leaf의 weight에 η을 곱해줌
itreration지날수록 생성되는 트리 영향력 줄여 이후 생성된 트리들이 모델 개선할 여지를 남기는 방식으로 오버피팅 방지
learning rate와 비슷한 개념, 가중치를 다르게 주는 것
2. Column Subsampling
Random Forest에서 사용
Subsampling한 일부 column들만 활용한 병렬학습통해 방지
각 단계에서 column을 subsampling
컬럼을 다 뽑지 않음으로써 다양성 부여하고 오버피팅 방지
최적의 Split Point찾는 알고리즘 4가지
트리 학습의 핵심 문제 중 하나는 최상의 분할을 하는 것
1. Basic Exact Greedy Algorithm
Exact Greedy Algorithm = 모든 feature에서 가능한 모든 분할을 열거하는 알고리즘
기존 tree model처럼 feature를 split하기 위해 모든 경우의 수를 파악
그러나 데이터가 한꺼번에 로딩되지 않으면 알고리즘 실행불가,
한번에 처리해야해 분산환경에서 처리 될 수 없어 병렬처리 불가
I = split하기 전의 모든 sample의 집합
1. score에 0 입력 (gain = score라 생각)
2. split이후 손실함수의 값의 감소량을 계산하기 위해 split이전의 gradient값을 G,H에 입력
3. m개의 feature에 대해 가능한 모든split point로 GL,HL,GR,HR score에 손실함수 감소량을 입력
4. score가장 높았던 split point선택
특징
1. 데이터를 정렬
2. 미래를 예측하지 않음
즉, 지금 당장 이익되는 길을 선택한다는 의미
-> 분할이 있을 때마다 전체 특성 값을 살펴보고 해당 시점에 가장 적합한 분할을 선
2. Approximate Algorithm
Exact Greedy Algorithm의 데이터로딩문제와 분산환경에서의 처리문제를 극복하기 위한 대안
Exact Greedy는 모든split에 대해 계산했다면, Approximate는 버킷안에서의 split만 계
data를 percentile로 나눔- l개만큼, percentile = feature의 분포를 통해 나누는 방법, 순서대로 정렬하려면 시간이 오래걸려 100개의 Quantile로 나누는 방법 Quantile = 어떤 집단에서의 class
하이퍼파라미터 ϵ을 조정하여 얼마나 잘게 나눌지 결정 일반적을 버킷은 1/ ϵ 만큼 만들어짐, 여기서는 l개만큼의 버킷이 만들어짐
버킷별로 split - 각 버킷은 다른 스레드로 태워서 계산할 수 있어 병렬처리 가능 각 버킷에서 split했을때 information gain이 가장 큰 버킷에서 split이뤄짐
split 한 후 2가지 variant가 있음 - Global variant, Local variant
