심화 스터디/논문 리뷰 스터디

[논문 리뷰 스터디] XGBoost- A Scalable Tree Boosting System

빵지0 2023. 5. 4. 17:27

작성자: 17기 안영지

💡 이 논문은 XGBoost 알고리즘에 대한 설명과 성능 분석을 다루고 있다. 이 알고리즘은 기계 학습에서 널리 사용되는 트리 부스팅 알고리즘 중 하나로, 대규모 데이터셋에서도 뛰어난 성능과 확장성을 제공한다. XGBoost는 Gradient Boosting 프레임워크를 기반으로 하며, 여러 개의 의사 결정 트리를 조합하여 강력한 예측 모델을 형성한다.

1. Introduction

XGBoost는 확장성이 가장 큰 특징임. 새로운 트리 학습 알고리즘과 가중 분위수 스케치 절차를 포함한 시스템 및 알고리즘 최적화로 인해 분산 또는 메모리 제한 설정에서도 수십억 개의 예제로 확장됨. 병렬 및 분산 컴퓨팅을 활용하여 데스크톱에서 수억 개의 예제를 처리할 수 있도록 지원하며, 최소한의 클러스터 리소스로 훨씬 더 큰 데이터로 확장할 수 있는 end-to-end 시스템을 만들 수 있음

2. TREE BOOSTING IN A NUTSHELL

2.1 Regularized Learning Objective

모델에 사용되는 함수 집합을 학습하기 위해 위와 같은 정규화된 목표를 최소화함.

l은 예측값 yˆi와 목표 yi 사이의 차이를 측정하는 미분 가능한 볼록 손실 함수

Ω라는 Regularization term이 사용됨. T(leaf 개수)가 작고 (모형의 복잡성(즉, 회귀 트리 함수)에 불이익을 줌)

||w||2(L2 norm)이 작아 오버피팅이 방지되는 방향으로 학습이 되게 함.

2.2 Gradient Tree Boosting

전통적인 최적화 방법대신, 모델은 additive 방식으로 훈련됨. yˆ(t)를 t번째 반복에서 i번째 인스턴스의 예측이라고 하면, 목표를 최소화하기 위해 ft를 추가해야 함.

→ 매 iteration마다 트리에 가지를 하나씩 늘려가는 방식(additive manner)

ft를 greedily 하게 추가함. 2차 근사를 사용하여 일반 설정에서 빠르게 최적화 할 수 있음

앙상블 학습을 진행하는 과정에서 이전 iteration에서 잘 학습하지 못한 부분에 가중치를 두고 학습하는 방식인 Gradient Boosting의 일종임을 알 수 있음

일반적인 손실 함수 하에서 최적화하기 좋은 형태로 만들기 위해 테일러 확장(Taylor Expansion)을 통한 2차 근사(Second-order approximation)를 진행

테일러 급수 계산을 통해 최종적으로 t번 째 iteration마다 최적화할 손실함수 식을 위와 같이 얻을 수 있음. t번 째 iteration에서 최종 손실함수가 gi,hi 에 의존하여 최적화할 수 있기 때문에, 손실함수의 종류와 관계없이 간단하게 계산할 수 있음.

모든 가능한 트리를 나열하여 최적 트리를 찾는 것은 거의 불가능하기 때문에, 단일 leaf에서 시작하여 매 iteration마다 반복적으로 트리에 분기를 추가하는 그리디 알고리즘이 효율적.

가지를 늘렸을 때 손실 함수가 최대한 감소하도록 하는 split point를 찾는 것이 XGBoost의 목표

가지를 늘렸을 때, 왼쪽과 오른쪽으로 분류되는 sample들의 집합을 각각 IL,IR이라 하고, I=IL∪IR 라 하면, 가지를 늘렸을 때 손실함수 값의 감소량 Lsplit은 위와 같이 나타남.

이는 가지를 나누기 전의 손실함수에서 가지를 나눈 후의 손실함수를 뺀 식.

 

2.3 Shrinkage and Column Subsampling

습 알고리즘 수행 과정에서 오버피팅을 방지하는 방법

  • Shrinkage 매 iteration마다, 직전 iteration까지 학습된 Tree들의 모든 leaf의 weight에 파라미터 η∈(0,1)를 곱해줌. iteration이 지날수록 생성되는 트리들의 영향을 줄여, 이후 생성될 트리들이 모델을 개선할 여지를 남기는 방식으로 오버피팅을 방지.
  • Column Subsampling Subsampling한 일부의 Column들만을 활용한 병렬학습을 통해 오버피팅을 방지

3. SPLIT FINDING ALGORITHMS

3.1 Basic Exact Greedy Algorithm

가능한 모든 경우를 나열하여 Split Point를 찾는 과정

  1. score에 0 입력
  2. 위의 Lsplit 식을 통해 Split 이후 손실함수 값의 감소량을 계산하기 위해, Split 이전의 그래디언트 값들을 G,H에 입력
  3. m개의 feature들에 대해서, 가능한 모든 Split point로 GL,HL,GR,HR을 계산하고, score에 손실함수 값의 감소량 입력
  4. score가 가장 높았던 Split point 선택

3.2 Approximate Algorithm

Split point 후보군을 선정하여, 그 후보군 내에서 가장 좋은 Split point를 찾는 과정

Global Variant: 한 번에 모든 Split point 후보군을 제시

Local Variant: 매 iteration마다 Split point 후보군을 제시 → 더 많은 계산량

eps: Approximate Algorithm의 파라미터 값. eps가 작을수록 더 많은 후보군을 제시

Exact Greedy Algorithm이 가장 우수하지만, 낮은 eps(0.05)의 Global Variant 방식과 eps 0.3 수준의 Local Variant 방식이 비슷한 성능을 보임.

 

3.3 Weighted Quantile Sketch

Quantile Sketch로 데이터를 Split하는 과정.

Weighted Quantile Sketch는 샘플마다 서로 다른 Gradient값을 일종의 weight로 간주하고 이를 고려하여 Split point 후보군을 찾는 것

"merge(합치기)"와 "prune(쳐내기)" operation 활용

  • Merge: Approximation error , ε1, ε2 수준에서의 두 Summary를 합치는 작업. 합쳐진 Summary는 , max(ε1, ε2)의 Approximation error를 가짐
  • Prune: Summary에 있는 element를 삭제하고, 그에 맞춰 Approximation error를 로 변경
  • ε→ε+1/b

3.4 Sparsity-aware Split Finding

데이터에 결측값의 존재, 0값이 빈번하게 나옴, 원핫 인코딩 등으로 인해 데이터 값이 sparse한 경우가 많은데, 이를 Sparsity-aware Split Finding을 통해 해결할 수 있음

결측치가 있는 데이터들을 분류할 Default 방향을 결정하는 알고리즘.

모든 결측치를 한 번은 전부 오른쪽에, 한 번은 전부 왼쪽에 배치하고, Split Point를 찾음

강필성교수님 유튜브 강의자료

위 예시에서는 모든 결측치를 왼쪽에 배치하였을 때 더 좋은 Split point를 찾을 수 있으므로, 해당 가지(branch)에서 결측치 데이터를 분류할 Default 방향을 왼쪽 leaf로 설정

 

 

XGBoost의 주요 특징

  1. 규제 기법: L1 및 L2 정규화와 같은 규제 기법을 사용하여 모델의 복잡성을 제어함. 이를 통해 과적합을 방지하고 일반화 성능을 향상시킴.
  2. 자동적인 가지치기: 트리의 최대 깊이를 설정하거나 트리 분할을 중단하는 등의 자동 가지치기 기능을 제공함. 이를 통해 모델이 더 간단해지고 예측 성능이 향상될 수 있음.
  3. 병렬 처리: 병렬 처리를 통해 대규모 데이터셋에서도 빠른 속도와 높은 확장성을 제공함. 데이터의 특성과 부스팅 단계 간에 병렬 계산을 수행하여 학습 속도를 향상시킴.
  4. 결측값 처리: 결측값을 자체적으로 처리함. 결측값이 있는 특성을 분할하는 전략을 학습하고, 결측값을 따로 처리하지 않고 트리 구조에 포함시켜 예측을 수행함.
  5. 유연한 사용성: 다양한 성능 평가 지표와 함께 사용할 수 있음. 사용자는 자신의 목적에 맞는 평가 지표를 선택하여 모델 학습을 진행할 수 있음.