[Machine Learning] XGBoost (3) Optimization technique

본 포스팅은 STATQUEST 유튜브 채널을 Reference하여 만들었습니다.

A. Approximate Greedy Algorithm

Gradient boosting은 Tree의 규칙을 만들 때, Gain을 최대화 하는 방향으로 학습한다.

이 때, Greedy algorithm을 활용하는데, 이는 계산적으로 매우 복잡하다.

예를 들어서, 관측치가 1억개에, 변수가 100개라고 가정한다면, Greedy algorithm을 통해 약 1억의 100제곱 개의 규칙을 만들어 테스트해야 하는 것이다.

이러한 계산적 비용을 줄이기 위한 방법으로 XGBoost는 Approximate Greedy Algorithm을 채택하였음.

Approximate Greedy Algorithm은 Tree 규칙을 Quantile로 사용한다.

위의 케이스는 2 Quantile이 가장 좋은 규칙을 생성할 것으로 보인다.

XGBoost는 default로 33개의 Quantile을 사용한다.

​

B. Parallel Learning

Quantile을 얻기 위해서는 데이터의 Histogram이 필요하다.

데이터가 무지하게 커질 경우, Histogram을 만드는 작업도 계산량이 매우 크다.

XGBoost는 분산 컴퓨팅 기법을 활용해 병렬 작업으로 Histogram을 만든다.

​

C. Weighted Quantile Sketch

일반적으로 Quantile을 계산할 때, 각 구간별로 관측치의 수를 동일하게 유지한다.

하지만 XGBoost는 모든 관측치에 Weight를 주고, 그 Weight들의 합을 구간별로 동일하게 유지하는 방식으로 진행한다.

이 때, 관측치의 Weight는 Cover라고 정의되며, 다음과 같이 계산된다.​

Regression task에서는 Cover는 모든 관측치에 대해서 1의 값을 가진다.

Classification task에서는 Cover는 다음과 같은 값을 가진다.

Cover가 가지는 의미를 살펴보자.

Cover는 애매하게 예측된 관측치에 높은 가중치가 부여된다.

즉, Quantile이 애매하게 예측된 관측치에 집중하여 형성되도록 하는 역할을 한다.

​

D. Sparsity –Aware Split Finding

​

XGBoost는 놀랍게도, X에 Missing value가 있어도 학습이 가능하다.

위의 데이터에서 2,6 번째 관측치의 Dosage는 Missing value이다.

하지만 우리는, Y값이 존재하기 때문에, 초기 예측 (default: 0.5)에 대해서 Residual을 계산할 수 있다.

이제 데이터를 Missing value의 여부에 따라 두 개로 분할하고, Sorting 하자.

우리는 XGBoost의 Tree 구성 알고리즘에 따라, Gain을 최대로 하는 규칙을 찾아야 한다.

이 때, 규칙은 Missing value가 없는 데이터 셋에서 찾는다.

​

​

그리고 Gain은 Missing value를 각 Leaf에 추가해보고, Gain이 큰 경우를 선택한다.

이 경우, Gain이 위쪽 Tree (Missing value를 왼쪽 Leaf에 추가) 가 더 크다.

모든 규칙에 대해서 위와 같이 Gain을 계산하여 최적의 Tree를 구성하자.

모든 경우의 수에 대해서 위와 같은 Tree가 구성되었다.

이렇게 학습이 진행되면, Test dataset에 Missing Dosage가 오더라도 예측 가능하다.

학습된 모델에서, Missing value가 입력된 Leaf의 Output value로 출력되게 진행된다.

​

​

E. Cache-Aware Access

Computer의 CPU는 크게 3개의 메모리 공간이 존재한다.

각 메모리 공간은 계산 속도에 차이가 있다.

XGBoost는 그 중에서 가장 빠른 메모리 공간인 Cache Memory의 활용을 Maximize함.

이를 통해, Similarity Score와 Gain등을 빠르게 계산 가능하다.

​

F. Blocks for Out-of-Core Computation

일반적으로, 용량이 큰 Dataset은 Hard Drive에 저장한다.

Cache Memory에서 Hard Drive에 저장된 Dataset을 불러 오는 것은 시간이 오래 걸림.

이에, Dataset는 여러 개의 Hard Drive에 분산하여, 병렬로 처리한다.