본 포스팅은 김성범 교수님의 유튜브 강좌, 강필성 교수님의 유튜브 강좌, Kicarus 티스토리를 참고했습니다.

Boosting 개요

• 여러 개의 learning 모델을 순차적으로 구축하여 최종적으로 합침(Ensemble)
• 여기서 사용하는 learning 모델은 매우 단순한 모델: 정확도가 0.5보다 살짝 높음
• 순차적 → 모델 구축에 순서를 고려함
• 각 단계에서 새로운 base learner를 학습하여 이전 단계의 base learner의 단점을 보와
• 단계를 거치면서 모델이 점차 강해짐

Boosting 알고리즘 종류

Adaptive Boosting(AdaBoost)

• 각 단계의 새로운 Base Learner를 학습하여 이전 단계의 Base Learner의 단점을 보완
• Training Error가 큰 관측츠의 선택 확률(가중치)을 높이고, Training Error가 작은 관측치의 선택 확률을 낮춤 → 오분류한 관측치에 보다 집중
• 앞 단계에서 조정된 확률(가중치)을 기반으로 다음 단계에거 사용될 Training Dataset을 구성
• 첫 단계로 돌아감(Recursive)
• 각 모델의 성능 지표를 가중치로 하여 결합(Ensemble)

pseudo code

for i = 1 to n:
	W_i = 1 / n
for j = 1 to m: # m: classifier의 개수
	L_j = 0
	for i = 1 to n:
    	if y_i != h_j(x)
	    	L_j += W_i
    a_j = log((1 - L_j) / L_j)
    for i = 1 to n
    	W_i = W_i * exp(a_j * I(y_i != h_j(x)))
h(x) = sign(sum(a_j * h_j(x)))

초기 가중치는 0.1이 된다 (1/10)

3개를 오분류 했으므로 Loss function 값이 다음과 같이 된다.

이때 $\alpha$값은 최종 모델을 결정할 때 모델 h_i의 가중치가 된다.
따라서 다음과 같이 업데이트 된다.

이러한 동작을 m번 반복한다.

Gradient Boosting Machine(GBM)

• Gradient Boosting = Boosting with Gradient decent
• 첫 번째 단계의 모델 tree 1을 통해 Y를 예측하고, Residual(y - y_hat)을 다시 두 번째 단계 모델 tree 2를 통해 예측하면서 점차 residual을 작아지게 하는 방식

점과 선의 차이가 residual이다.

Gradient: 현재 Euclidean Distance가 Loss function이므로 residual = negative gradient

실제 데이터는 파란 점, 현재 모델은 빨간 선, residual 값은 초록 선이다.

Extreme Gradient Boosting (XGBoost)

• 앙상블 학습을 진행하는 과정에서 이전 iteration에서 잘 학습하지 못한 부분에 가중치를 두고 학습하는 방식
• 손실 함수가 최대한 감소하도록 하는 split point를 찾는 것이 XGBoost의 목표

Split Finding Algorithm

Basic exact greedy algorithm
모든 데이터셋을 탐색하여 최적의 split point를 찾는다.

• pros: 모든 경우의 수를 다 탐색하므로 optimal split을 반드시 찾음
• cons: 데이터가 전부 메모리에 들어가지 않음, 병렬처리 불가

Approximate algorithm
1. 데이터 정렬 뒤 분할(분할될 데이터셋을 bucket이라 함)
2. bucket 별로 split point를 찾음

빨간 선이 bucket 분할이다. exact greedy algorithm은 모든 value-label 쌍을 전부 사용하여 gradient를 계산한다.
위 그림에서 bucket 별로 병렬 처리를 한다면, exact greedy는 39회 연산, approximation은 3회 연산으로 처리 가능하다.

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

Local Variant
매 iteration마다 Split point 후보군을 제시

global eps << local eps 이어야 된다.

Sparsity-Aware Split Finding

• 결측치가 들어간 데이터셋에도 학습이 가능함
• default direction을 직접 찾아서 결측치일 경우 default direction으로 보낸다.

Efficient Computing

• XGBoost에서 가장 많은 시간이 소요되는 것 → 정렬
• 데이터를 컬럼 방향으로 저장하고 정렬 시 인덱스 변화하여 정렬

Cache-aware access

• 데이터를 'Block'으로 저장하고 사전 배열 → Gradient 통계치를 행 인덱스로 가져와야하므로 Cache miss가 자주 발생할 수 있음 → Cache-aware prefetch algorithm 사용
• 각 스레드 내 내부 버퍼 할당 → Gradient 통계를 mini batch 방식으로 가져옴 → 누적 계산

Out-of-core Computation

• 데이터가 메인 메모리에 전부 들어가지 않을 경우 디스크 공간을 활용하는 out-of-core 계산 기능 제공
• 블록 압축: 디스크에서 메모리까지 데이터 전송 속도 감소
• Sharding: 여러 디스크에 데이터를 분산시켜 IO throughput 증가

Light Gradient Boosting Machine(LightGBM)

• 모든 feature로 동작함 → Exclusive Feature Bundling(EFB)
  feature space가 sparse할 경우 거의 exclusive이다.(one-hot encoding) → bundling 해도 퍼포먼스 저하 X

• 모든 데이터 객체로 동작함 → Gradient-based One Side Sampling(GOSS)
  gradient가 크면 중요도도 커진다 → 크면 keep, 작으면 randomly drop

Gradient-based One Side Sampling

a와 b를 어떻게 설정하는지에 따라 성능이 다름

Exclusive Feature Bundling

특징을 뽑아서 하나의 변수로 표현

vertex를 feature, edge를 feature 간 conflict라고 보면 서로 이웃하지 않은 모든 feature를 하나의 bundle로 묶는다.(cut-off가 conflict의 threshold 값)

CatBoost

• 카테고리형 데이터 자동 처리
• 순서 기반 부스팅(order-based boosting) → 과적합(overfitting)을 줄이고 예측 성능 개선
• Target Statistic(TS):

Greedy TS

a, p: 데이터의 노이즈를 줄이기 위한 파라미터

• $\hat{x}^i_k$가 Target value인 $y_k$로부터 산출됨 → target leakage
• train-test 데이터 분포에 따른 오류 발생 가능
• conditional shift → Property 1. 이를 방지하기 위해 train, test의 TS 평균 값이 같아야 한다

Holdout TS

conditional shift를 방지하기 위해 train 데이터를 두개로 나누어 각각 TS 계산과 학습에 이용 → 학습 데이터 양 줄어듦 → Property 2. 모든 학습 데이터를 TS 계산과 학습에 사용해야 한다.

Leave-one-out TS

하나의 데이터를 제외하고 TS 계산

Ordered TS

• 데이터셋에 random permutation 값 부여
• k번째 데이터의 TS: k-1번까지의 TS만 사용 → Property 1, 2 둘 다 만족, CatBoost에서도 해당 TS를 사용함

Prediction Shift

• 정의: target value를 활용하여 생기는 target leakage → 입력 데이터셋과 출력 값의 분포 차이와 overfitting 발생하는 현상
• 해결하기 위해서는 매 스텝마다 다른 데이터셋(independent samples)를 활용해야 함 → 트리를 구성하는 매 스텝마다 임의의 permutation으로 샘플링하여 independent sample 구성

Ordered Boosting

1. permutation 값에 따라 gradient 계산
2. 이전 스텝 트리 leaf에 gradient 평균 할당하면서 permutation 순서에 따라 leaf value 할당
3. 사전에 계산된 gradient와 새로 할당된 leaf value 사이에 cosine similarity 계산 후 가장 작은 부분에서 split point 생성
4. 1 ~ 3 과정 반복

CatBoost는 Oblivious Decision Tree(ODT) 형태 트리 사용(좌우 대칭) → overfitting 방지, 테스팅 소요 시간 감소