Gradient Boosting은 단순하고 약한 모델 세트의 추정치를 결합하여 대상 변수를 정확하게 예측하려 시도하는 알고리즘이다. 모델 결합 시 이전 모델의 손실 함수(loss function)를 경사 하강법(gradient descent)을 사용하여 최소화하기 때문에 gradient boosting이라고 부른다.
정확도, 속도, 과적합 방지를 위한 XGBoost, LightGBM, CatBoost 하이퍼파라미터 비교 (https://towardsdatascience.com/catboost-vs-lightgbm-vs-xgboost-c80f40662924#72c7)
eta (default=0.3): 학습률(learning rate). 보통 0.01~0.3
max_depth (default=6): 트리의 최대 깊이. 이 값을 늘리면 모형이 더 복잡해지고 과적합될 가능성이 높음. 0은 제한 없음을 의미.
min_child_weight (default=1): 하위 노드 추가에 필요한 인스턴스 가중치(헤시안)의 최소 합. 트리 파티션 단계에서 리프 노드의 인스턴스 가중치 합이 min_child_weight보다 작은 경우 추가 파티셔닝을 포기한다. 선형 회귀 모델에서 이는 각 노드에 필요한 최소 인스턴스 수를 뜻한다. 값이 클수록 알고리즘이 보수적이 됨(과적합 방지).
Gradient-Based One-Side Sampling(GOSS), Exclusive Feature Bundling(EFB) 기술 사용
데이터 크기가 커질수록 XGBoost의 훈련 시간이 비례해서 늘어나는 반면, LightGBM은 최대 20배 이상 빠르면서도 거의 동일한 정확도를 보여줌
Gradient-Based One-Side Sampling (GOSS)
데이터셋의 샘플 수를 줄이는 알고리즘
기울기(gradient)가 작은 데이터 인스턴스는 이미 잘 훈련된 것으로 보고, 이 인스턴스들에 대해서는 무작위 표본 추출을 수행 (gradient가 큰 데이터 인스턴스는 모두 유지)
이 때, 데이터 분포에 미치는 영향을 보정하기 위해서 정보 획득 계산 시 기울기가 작은 데이터 개체에 승수 상수를 적용한다.
구체적으로, 우선 기울기 절댓값에 따라 데이터 개체를 정렬하고 상위 $a \times 100\%$ 개체를 선택한다. 그런 다음 나머지 데이터에서 $b \times 100\%$ 개체를 무작위 표본 추출한다. 그 후 정보 획득을 계산할 때 기울기가 작은 표본 데이터를 상수 $\frac{1-a}{b}$만큼 증폭시킨다.
이렇게 함으로써 원래의 데이터 분포를 많이 변경하지 않고도 훈련이 덜 된 개체에 초점을 보다 잘 맞출 수 있다.
[알고리즘]
각 instance들의 gradient 계산 및 정렬
gradient 상위 $a \times 100\%$ 만큼의 instance 선택
남은 instance들 중에서 $b \times 100\%$ 만큼을 무작위로 선택하고, 이 instance들에 상수 $\frac{1-a}{b}$을 곱함
이 instance들은 모델이 이미 충분히 학습한 데이터지만, 데이터셋의 분포를 유지하기 위해 일부분을 포함시킵니다
$\frac{1-a}{b}$는 트리 Split 과정에서 information gain을 계산할 때 가중치를 곱해주는 역할을 합니다
$b$의 값이 적을수록 큰 가중치를 곱해주게 됩니다
이를 통해 원래 데이터셋의 분포를 크게 변화시키지 않고 데이터셋의 크기를 줄일 수 있습니다
선택한 instance들로 GBDT 생성
Exclusive Feature Bundling (EFB)
피쳐 수를 줄이는 알고리즘
고차원 데이터는 보통 매우 희소한데, 이는 손실이 거의 없이 하나로 묶을 수 있는 가능성을 제기한다.
희소 피쳐 공간(sparse feature space)에서는 많은 피쳐들이 상호 배타적으로, 0이 아닌 값을 동시에 갖지 않는다.
이 배타적인 피쳐들을 하나의 피쳐로 안전하게 묶을 수 있으며, 이를 exclusive feature bundle이라 한다.
Greedy Bundling 단계에서 기존 피쳐들을 어떻게 새로운 EFB로 묶을지 결정 (알고리즘 3)
먼저 변마다 가중치가 있는 그래프를 구성한다. 이 가중치는 변수 간 총 충돌 횟수에 해당한다.
그 다음 그래프 내 꼭짓점 차수에 따라 내림차순으로 변수를 정렬한다.
마지막으로 정렬시킨 목록의 각 변수를 확인하면서 작은 충돌이 있는 기존 묶음에 할당하거나 새로운 묶음을 만든다.
Merge Exclusive Features 단계에서 기존 피쳐 값들을 병합하여 새로운 데이터를 생성 (알고리즘 4)
히스토그램 기반 알고리즘은 피쳐의 연속적인 값 대신 개별 구간을 저장하기 때문에 배타적 피쳐를 각기 다른 구간에 두어 피쳐 묶음을 구성할 수 있다.
이는 피쳐의 원래 값에 오프셋을 더하여 수행할 수 있다. 예를 들어 피쳐 묶음에 피쳐 두 개가 속한다고 가정하자. 원래의 피쳐 A는 [0, 10] 값을 취하고 피쳐 B는 [0, 20] 값을 취한다. 그렇다면 피쳐 B 값에 오프셋 10을 더하여 가공한 피쳐가 [10, 30]에서 값을 취하게 한다.
그 다음, 피쳐 A와 B를 병합하고 [0, 30] 범위의 피쳐 묶음을 사용하여 원래의 피쳐 A와 B를 안전하게 대체할 수 있다.
아래 데이터셋(피쳐 $x_1 \sim x_5$ 5개, 샘플 10개)에서 $x_1, x_2$ 피쳐는 6개 데이터 인스턴스에서 충돌이 발생 (둘 다 0이 아닌 값을 동시에 가짐)
$x_2, x_3$은 $I_8$ 한 개의 인스턴스만 충돌이 발생
Greedy bundling 알고리즘을 cut-off=0.2로 적용하면 $[(x_5), (x_1, x_4), (x_2, x_3)]$ 3개의 번들로 묶이게 된다.
(알고리즘 4 Merge Exclusive Features)
$(x_1, x_4)$ 번들에서 $x_1$ 피쳐의 최대값은 3이므로, $x_1$ 값이 0인 $I_2$ 인스턴스의 $x_{14}$ 값은 3($x_1$ 최대값) + 1(원래 $x_2$ 값) = 4가 된다.
주요 하이퍼파라미터
정확도, 속도, 과적합 방지를 위한 XGBoost, LightGBM, CatBoost 하이퍼파라미터 비교 (https://towardsdatascience.com/catboost-vs-lightgbm-vs-xgboost-c80f40662924#72c7)
num_leaves (default=31): 한 트리의 초대 리프 개수. 트리 복잡도를 제어하는 메인 파라미터로서, 2^(max_depth)보다 작아야 과적합을 막을 수 있다. 예를 들어, max_depth=7일 때 num_leaves=127 설정은 과적합을 유발하기 쉽고, 70~80 정도일 때 더 나은 정확도를 얻는다.
max_depth (default=-1): 트리 최대 깊이. 데이터 양이 적을 때 과적합을 제어하는 데 사용된다. 0보다 작거나 같으면 깊이 제한 없음을 의미.
min_data_in_leaf (default=20): 한 리프에 있는 최소 데이터 양. 과적합 제어에 사용된다.
feature_fraction (default=1.0): 각 이터레이션(트리)에서 무작위로 선택되는 피쳐 비율. 훈련 속도 향상 및 과적합 방지에 도움을 준다.
bagging_fraction(default=1.0): feature_fraction과 유사하게, 데이터 일부를 무작위로 선택하는 비율.훈련 속도 향상 및 과적합 방지에 도움을 준다.
lambda_l1 (default=0.0): L1 정규화 항.
lambda_l2 (default=0.0): L2 정규화 항.
min_gain_to_split (default=0.0): 노드 분할을 위한 최소 gain 값.
예측 시간 및 훈련 시간 빠름, 정확도 우수 데이터셋 크기가 작고, (GPU 대신) CPU 사용할 경우 XGBoost, LightGBM보다 느릴 수 있다.
Ordered Boosting, Ordered Target Statistics 알고리즘 사용
모든 트리 단계에서 같은 criterion 사용해서 분할하여 대칭(symmetric) 트리 구성
범주형, 테스트 데이터를 인코딩 없이 직접 사용 가능
하이퍼파라미터 튜닝 없이 기본값으로도 높은 성능을 보임
Ordered Boosting
Gradient boosting은 이전 모델의 gradient를 연속해서 줄이는 방향으로 훈련이 이뤄지는데, 이렇게 만들어진 모델은 작고 noisy한 데이터에 대해 과적합이 발생하기 쉬운 단점이 있다. 훈련에 사용되었던 데이터와 테스트 및 실제 예측에 사용하는 데이터의 분포가 다르기 때문에 발생하는 이슈인데, CatBoost 논문에서는 이를 prediction shift라 칭한다.
Prediction shift를 해결하기 위해 CatBoost에서는 "랜덤하게 재배열한 데이터셋을 순차적으로, 서브셋만 사용하여 gradient를 계산"하는 방식을 사용한다.
