[XSTB] XGBoost: A Scalable Tree Boosting System

XGBoost: A Scalable Tree Boosting System

저자: Tianqi Chen, Carlos Guestrin

발행년도: 2016년

인용수: 45000회

논문 링크: https://arxiv.org/abs/1603.02754

arXiv ID: 1603.02754

---

XGBoost: 대규모 데이터를 위한 확장 가능한 트리 부스팅 시스템

문제 정의 (Problem Definition)

머신러닝이 산업 전반에 활용되면서 처리해야 할 데이터의 규모가 기하급수적으로 증가했다. 특히 웹 검색, 광고 추천, 이상 탐지와 같은 실제 응용에서는 수백만에서 수십억 개의 샘플을 다뤄야 하는 상황이 일상이 되었다. 이런 환경에서 그레이디언트 부스팅 트리(Gradient Boosting Trees)는 여전히 가장 효과적인 알고리즘 중 하나였지만, 기존 구현체들은 대규모 데이터에서 심각한 확장성 문제를 보였다.

실제 환경에서 그레이디언트 부스팅의 가장 큰 문제는 학습 시간이었다. 수백만 개의 데이터로 모델을 학습하는 데 몇 시간에서 며칠이 걸리는 것은 흔한 일이었고, 이는 빠른 실험과 개선을 요구하는 실무 환경에서 치명적인 단점이었다. 더욱이 메모리 사용량도 데이터 크기에 비례해 증가해서, 단일 머신으로는 처리가 불가능한 경우가 많았다.

또 다른 중요한 문제는 희소 데이터(sparse data) 처리였다. 실제 데이터에서는 결측값이나 0이 대부분인 희소 특징이 흔하게 나타난다. 원-핫 인코딩된 범주형 변수, 텍스트 데이터의 BoW 표현, 사용자-아이템 상호작용 행렬 등이 대표적인 예다. 기존 부스팅 알고리즘들은 이런 희소성을 효율적으로 활용하지 못해 불필요한 계산과 메모리 낭비가 발생했다.

마지막으로 실무에서는 과적합 방지가 항상 중요한 이슈였다. 부스팅 알고리즘은 본질적으로 약한 학습기를 순차적으로 결합하는 방식이라 과적합에 취약할 수 있다. 특히 노이즈가 많은 실제 데이터에서는 정규화 없이는 일반화 성능을 보장하기 어려웠다.

기존 방법의 한계 (Motivation)

기존의 그레이디언트 부스팅 구현체들을 살펴보면 크게 세 가지 접근 방식이 있었다. 첫 번째는 scikit-learn의 GradientBoostingClassifier와 같은 순차적 구현이었다. 이 방식은 알고리즘을 충실하게 구현했지만, 모든 계산을 순차적으로 수행하기 때문에 대규모 데이터에서는 실용적이지 못했다. 트리 하나를 만드는 데만 수십 분이 걸리는 경우도 있었고, 메모리 사용도 비효율적이었다.

두 번째는 R의 gbm 패키지처럼 일부 최적화를 시도한 구현들이었다. 이들은 히스토그램 기반 분할 같은 근사 방법을 도입해 속도를 개선했지만, 여전히 단일 머신의 한계를 벗어나지 못했다. 또한 희소 데이터를 밀집 형식으로 변환해 처리하는 비효율성도 있었다.

세 번째는 분산 머신러닝 플랫폼들이었다. Spark MLlib이나 H2O 같은 플랫폼들은 분산 처리를 지원했지만, 그레이디언트 부스팅의 순차적 특성 때문에 병렬화 효율이 떨어졌다. 네트워크 통신 오버헤드가 크고, 각 노드에서 중복 계산이 발생하는 문제도 있었다.

> 저자들이 지적한 기존 방법의 한계는 타당하지만, 2016년 당시 상황임을 고려해야 한다. LightGBM이나 CatBoost 같은 경쟁 알고리즘들이 아직 등장하지 않은 시점이라 비교 대상이 제한적이었다. 또한 딥러닝의 부상으로 GPU 활용이 주목받던 시기인데, XGBoost가 CPU 중심 최적화에 집중한 점은 흥미롭다.

무엇보다 기존 구현체들은 정규화를 체계적으로 다루지 못했다. 대부분 트리 깊이나 리프 노드 수를 제한하는 단순한 방법에 의존했고, 목적 함수 수준에서의 정규화는 거의 고려하지 않았다. 이는 복잡한 데이터에서 과적합을 제대로 제어하지 못하는 원인이 되었다.

제안 방법의 핵심 아이디어 (Key Idea)

XGBoost의 핵심 아이디어는 "시스템 최적화와 알고리즘 혁신의 결합"이었다. 단순히 기존 알고리즘을 빠르게 구현하는 것이 아니라, 그레이디언트 부스팅의 수학적 구조를 재해석하고 이를 현대적인 컴퓨터 시스템에 최적화된 방식으로 구현하는 것이 목표였다.

가장 중요한 혁신은 정규화된 목적 함수의 도입이었다. 기존 부스팅이 손실 함수만 최소화했다면, XGBoost는 모델 복잡도를 명시적으로 패널티로 추가했다. 이는 Ridge 회귀가 선형 모델에 정규화를 추가한 것과 유사한 접근이었다. 트리의 리프 노드 수와 리프 값의 크기에 패널티를 부여함으로써 과적합을 원천적으로 방지했다.

Obj = Loss + Ω(tree)
where Ω(tree) = γT + ½λ||w||²

두 번째 혁신은 희소성 인지 분할 알고리즘이었다. 희소 데이터에서 결측값이나 0을 별도로 처리하는 대신, 이들을 하나의 방향으로 몰아서 처리하는 방식을 제안했다. 이를 통해 희소 행렬의 비영 원소만 탐색하면서도 최적 분할을 찾을 수 있었다.

세 번째는 가중치 분위수 스케치(weighted quantile sketch)를 통한 근사 분할이었다. 모든 가능한 분할점을 탐색하는 대신, 데이터 분포를 고려한 후보 분할점을 효율적으로 선택했다. 특히 각 샘플의 중요도(헤시안)를 가중치로 반영해 더 정확한 근사가 가능했다.

> 정규화 항의 도입은 확실히 혁신적이었지만, 저자들이 주장하는 것처럼 완전히 새로운 개념은 아니었다. Friedman의 stochastic gradient boosting에서도 유사한 아이디어가 있었고, 트리 프루닝 기법들도 암묵적으로 정규화 효과를 가지고 있었다. XGBoost의 진짜 기여는 이를 명시적이고 수학적으로 엄밀하게 정식화한 것이라고 봐야 한다.

아키텍처 설명 (Architecture)

XGBoost의 전체 아키텍처는 크게 네 개의 계층으로 구성되었다. 최하단에는 데이터 추상화 계층이 있어 희소/밀집 데이터를 통합적으로 처리했다. 그 위에 트리 학습 엔진이 있고, 이를 관리하는 부스팅 제어기, 그리고 최상단에 API 계층이 위치했다.

트리 학습 과정은 다음과 같은 단계로 진행되었다:

# Pseudo-code for tree learning
def grow_tree(data, depth):
    if depth >= max_depth or data.size < min_samples:
        return create_leaf(data)
    
    # Find best split using approximate algorithm
    candidates = quantile_sketch(data.features)
    best_gain = -inf
    
    for feature in features:
        for split_point in candidates[feature]:
            gain = calculate_gain_with_regularization(
                data, feature, split_point
            )
            if gain > best_gain:
                best_gain = gain
                best_split = (feature, split_point)
    
    # Apply sparsity-aware split
    left_data, right_data = sparse_split(data, best_split)
    
    return Node(
        split=best_split,
        left=grow_tree(left_data, depth+1),
        right=grow_tree(right_data, depth+1)
    )

희소성 인지 분할은 특히 영리한 설계였다. 각 노드에서 결측값의 방향(왼쪽/오른쪽)을 데이터 기반으로 학습했다. 이는 단순히 결측값을 평균으로 대체하는 것보다 훨씬 유연하고 효과적이었다.

병렬화는 두 수준에서 이루어졌다. 특징 수준 병렬화에서는 각 스레드가 서로 다른 특징의 최적 분할점을 찾았고, 데이터 수준 병렬화에서는 데이터를 블록으로 나누어 처리했다. 특히 컬럼 블록 구조를 사용해 캐시 효율성을 극대화했다.

Data Layout:
[Block 1: Features 1-100]  → Thread 1
[Block 2: Features 101-200] → Thread 2
[Block 3: Features 201-300] → Thread 3

메모리 최적화도 세심하게 설계되었다. 데이터를 압축된 컬럼 형식으로 저장하고, 각 블록을 CPU 캐시에 맞게 조정했다. 또한 out-of-core 계산을 지원해 메모리보다 큰 데이터도 처리할 수 있었다.

> 아키텍처 설계는 확실히 잘 되어 있지만, 논문에서는 각 최적화 기법의 상대적 중요도를 명확히 제시하지 않았다. 캐시 최적화가 얼마나 중요한지, 병렬화가 실제로 선형적 속도 향상을 가져오는지 등에 대한 구체적인 분석이 부족했다.

접근 방법의 특징 및 설계 의도 (Design Choices)

XGBoost의 설계 선택들을 자세히 살펴보면 "실용성"이라는 일관된 철학이 보인다. 가장 대표적인 예가 근사 알고리즘의 사용이었다. 정확한 그리디 알고리즘 대신 분위수 기반 근사를 선택한 것은 정확도를 약간 희생하더라도 확장성을 확보하기 위함이었다.

가중치 분위수 스케치의 설계는 특히 주목할 만했다. 단순히 데이터를 균등하게 나누는 것이 아니라, 각 샘플의 헤시안(2차 미분값)을 가중치로 사용했다. 이는 손실 함수의 곡률이 큰 지점에서 더 세밀한 분할을 가능하게 했다. 수학적으로 타당할 뿐 아니라 실제 성능 향상으로도 이어졌다.

정규화 설계에서도 실용적 고려가 엿보인다. L2 정규화(`λ`)는 리프 값의 크기를 제한하고, L0 정규화(`γ`)는 트리 복잡도를 제한했다. 이 두 파라미터만으로도 대부분의 과적합 상황을 제어할 수 있었다. 더 복잡한 정규화를 추가할 수도 있었겠지만, 사용자 입장에서 이해하고 조정하기 쉬운 형태를 선택했다.

Column Block 구조는 현대 CPU 아키텍처를 고려한 선택이었다. 데이터를 컬럼 단위로 압축 저장하면서도, 각 블록이 L3 캐시에 들어갈 수 있도록 크기를 조정했다. 이는 메모리 접근 패턴을 예측 가능하게 만들어 CPU의 프리페칭 성능을 극대화했다.

분산 학습 설계에서는 통신 비용을 최소화하는 데 중점을 뒀다. 각 노드가 로컬 히스토그램을 계산하고, 이를 취합해 전역 히스토그램을 만드는 방식을 사용했다. 이는 raw 데이터를 주고받는 것보다 훨씬 효율적이었다.

> 설계 선택들은 대체로 합리적이지만, 몇 가지 의문점이 있다. 첫째, 왜 GPU 가속을 초기 버전에서 고려하지 않았는지 명확하지 않다. 둘째, 정규화 파라미터가 단 두 개인 것이 정말 충분한지, 더 세밀한 제어가 필요한 경우는 없는지 검증이 부족했다. 셋째, 분산 환경에서의 fault tolerance에 대한 고려가 거의 없었다.

실험 결과 분석

논문의 실험은 크게 세 가지 측면을 검증했다. 첫째는 확장성, 둘째는 정확도, 셋째는 각 최적화 기법의 효과였다.

확장성 실험에서 XGBoost는 기존 구현체들보다 10배 이상 빠른 속도를 보였다. 특히 데이터 크기가 커질수록 성능 차이가 더 벌어졌는데, 이는 캐시 최적화와 병렬화가 효과적으로 작동했음을 시사한다. 1억 개 샘플 데이터에서도 선형에 가까운 확장성을 보인 것은 인상적이었다.

정확도 측면에서는 Kaggle 대회들에서의 성공 사례를 제시했다. 29개 대회 중 17개에서 XGBoost를 사용한 솔루션이 우승했다는 점은 알고리즘의 실용성을 잘 보여준다. 다만 이는 알고리즘 자체의 우수성인지, 빠른 속도로 인한 실험 용이성 때문인지는 명확하지 않다.

Ablation study에서는 각 최적화 기법을 하나씩 제거하며 성능 변화를 측정했다. 희소성 인지 분할을 제거했을 때 희소 데이터에서 3-5배 속도 저하가 발생했고, 컬럼 블록을 사용하지 않았을 때 2배 정도 느려졌다. 정규화를 제거했을 때는 특히 작은 데이터셋에서 과적합이 심하게 발생했다.

> 실험 설계에 몇 가지 아쉬운 점이 있다. 첫째, 대부분의 비교가 2016년 이전 구현체들과 이루어져 있어 공정성이 떨어진다. 둘째, 메모리 사용량에 대한 체계적인 분석이 부족하다. 셋째, 하이퍼파라미터 튜닝에 얼마나 민감한지에 대한 분석이 없다. 넷째, 정규화 효과를 보여주는 실험이 너무 단순하다. 다양한 노이즈 수준에서의 robustness 테스트가 필요했다.

분산 학습 실험도 포함되었지만, 노드 수가 늘어날 때의 효율성(efficiency) 분석이 부족했다. 통신 오버헤드가 어느 정도인지, 노드 수가 많아질 때 성능이 어떻게 변하는지 구체적인 수치가 없었다.

총평: 개인적 해석과 후속 연구 방향

XGBoost는 엔지니어링과 알고리즘의 균형잡힌 결합이라는 점에서 큰 의미를 가진다. 단순히 빠른 구현을 만든 것이 아니라, 그레이디언트 부스팅의 수학적 구조를 재해석하고 이를 현대적 하드웨어에 최적화했다. 정규화된 목적 함수의 도입은 이론적으로도 의미 있는 기여였다.

실무 적용 관점에서 XGBoost의 가장 큰 장점은 사용 편의성과 성능의 균형이다. 하이퍼파라미터가 직관적이고, 대부분의 경우 기본값만으로도 좋은 성능을 낸다. 또한 다양한 프로그래밍 언어와 플랫폼을 지원해 접근성이 높다.

하지만 한계도 분명하다. 여전히 순차적 학습이라는 부스팅의 근본적 한계를 완전히 극복하지는 못했다. 또한 메모리 사용량이 데이터 크기에 비례해 증가하는 문제도 남아있다. 딥러닝처럼 미니배치 학습이 불가능한 점도 제약이다.

만약 내가 이 연구를 발전시킨다면 다음과 같은 방향을 고려하겠다:

첫째, GPU 가속을 본격적으로 도입하겠다. 히스토그램 계산과 분할점 탐색은 충분히 병렬화 가능하므로, GPU의 대규모 병렬성을 활용할 수 있다. 실제로 XGBoost도 후속 버전에서 GPU 지원을 추가했다.

둘째, 온라인/증분 학습을 지원하는 방법을 연구하겠다. 스트리밍 데이터 환경에서는 전체 데이터를 메모리에 올릴 수 없으므로, 새로운 데이터로 기존 모델을 업데이트하는 방법이 필요하다. 이는 부스팅의 순차적 특성과 충돌하므로 창의적인 접근이 필요할 것이다.

셋째, 자동 하이퍼파라미터 튜닝을 통합하겠다. XGBoost가 사용하기 쉽다고는 하지만, 최적 성능을 위해서는 여전히 수동 튜닝이 필요하다. 베이지안 최적화나 메타러닝을 활용한 자동 튜닝 기능을 내장한다면 더욱 실용적일 것이다.

> 결론적으로 XGBoost는 "실용적 머신러닝 시스템"의 모범 사례다. 완벽하지는 않지만, 현실적 제약 조건 하에서 최선의 균형점을 찾았다. 이후 LightGBM, CatBoost 등의 경쟁자들이 등장했지만, XGBoost가 제시한 기본 프레임워크는 여전히 유효하다. 다만 딥러닝의 발전으로 정형 데이터에서도 신경망의 성능이 향상되고 있어, 부스팅 알고리즘의 미래는 불확실하다. 그럼에도 해석가능성과 훈련 효율성 측면에서 트리 기반 앙상블은 당분간 중요한 도구로 남을 것이다.