XGBoost 작동 원리: 정규화 손실함수·2차 테일러 근사·병렬 분할 탐색 정리

핵심 메시지

• XGBoost는 대규모 정형(테이블) 데이터에서 별다른 튜닝 없이도 최적에 가까운 성능을 내, 한때 사실상 표준 모델로 자리 잡았다.
• 일반 그래디언트 부스팅처럼 트리를 하나씩 추가해 이전 트리의 오차를 보정하되, 손실함수에 트리 복잡도(잎 개수·예측값 크기) 항을 더해 편향과 분산을 동시에 줄인다.
• 새 트리를 학습할 때 손실함수를 2차 테일러 전개로 근사해 기울기(gradient)와 곡률(hessian)만으로 분할을 평가한다.
• 분할은 부모와 자식 노드의 손실 차이(이득)를 최대로 만드는 열·값을 찾는 방식이며, 곡률이 큰 분할을 피해 일반 부스팅보다 보수적이다.
• 트리 생성 자체는 순차적이라 병렬화가 어렵지만, 각 열의 최적 분할 탐색을 스레드로 나눠 병렬 처리해 학습 속도를 끌어올린다.

쉽게 이해하기

XGBoost는 큰 정형 데이터셋에서 다른 알고리즘을 굳이 시도할 이유가 없을 만큼 손쉽게 최적에 가까운 결과를 내, 한 시대를 풍미한 모델이다. 기본 골격은 결정 트리를 하나씩 추가해 이전 트리들의 오차를 보정해 나가는 그래디언트 부스팅이다. 트리는 각 노드에서 특정 열의 값을 기준으로 데이터를 재귀적으로 둘로 나누고, 샘플 수가 너무 적거나 깊이 한계에 도달하는 등의 조건을 만나면 잎(leaf)에서 분할을 멈춘다.

XGBoost의 핵심은 손실함수에 정규화 항을 넣었다는 점이다. 손실함수는 두 부분으로 나뉜다. 하나는 예측값과 실제 목표값의 오차를 줄이는 샘플 단위 항으로 편향을 낮추고, 다른 하나는 트리의 복잡도를 합산하는 정규화 항 Ω로 분산을 제어한다. Ω는 다시 잎 개수에 비례하는 γT 항과 잎의 예측값(가중치)을 작게 누르는 항으로 나뉘어, 앞은 과소적합을, 뒤는 과적합을 막는 역할을 한다.

새 트리를 학습할 때는 손실함수를 2차 테일러 전개로 근사한다. 이렇게 하면 이전 예측에 대한 1차 미분인 기울기(gradient)와 2차 미분인 헤시안(hessian)으로 손실을 표현할 수 있고, 이미 학습된 이전 트리들의 손실은 상수라 버릴 수 있다. 또 샘플에 대한 합을 잎에 대한 합과 각 잎 안 샘플에 대한 합으로 바꾸면, 미분을 0으로 두고 각 잎의 최적 가중치를 기울기·헤시안·복잡도(λ)로 깔끔하게 풀어낼 수 있다.

분할은 이 손실함수로 평가한다. 부모 노드의 손실은 상수이므로, 어떤 분할이 왼쪽·오른쪽 자식의 손실 합을 가장 크게 줄이는지(이득이 최대인지)를 본다. 최적 손실 식은 분자에 기울기 제곱 합, 분모에 헤시안 합과 λ가 오는 형태라, XGBoost는 기울기는 키우고 곡률은 줄이는 분할을 선호한다. 곡률을 무시하고 기울기 감소만 좇는 일반 그래디언트 부스팅보다 보수적인 분할을 택하는 이유다.

실제 분할 탐색은 각 열에 대해 데이터를 정렬하고 가능한 분할마다 이득을 계산해 최댓값을 고른다. 트리는 순차적으로 쌓이므로 병렬화는 트리가 아니라 열별 분할 탐색을 스레드로 나누는 방식으로 이뤄진다. 결측치는 해당 샘플을 왼쪽·오른쪽에 각각 넣어보고 이득이 큰 쪽을 노드별 기본 방향으로 학습한다. 이 밖에 열을 미리 정렬해 원래 인덱스를 포인터로 보관하기, 압축 열 포맷, 캐시 인지 prefetch, 히스토그램 기반 근사 분할 등으로 속도를 더 끌어올린다.

주요 인사이트

• 정규화를 사후 가지치기가 아니라 학습 목표(손실함수)에 직접 통합해, 편향과 분산을 동시에 최소화하도록 설계했다.
• 1차 미분만 쓰는 일반 부스팅과 달리 2차 미분(곡률)까지 활용해, 곡률이 큰 불안정한 분할을 피한다.
• 결측치를 버리거나 임의 대체하지 않고, 노드마다 왼/오른쪽 기본 방향을 데이터로부터 학습한다.
• 병렬화의 대상은 트리가 아니라 분할 탐색이며, presort·압축 열 포맷·캐시 prefetch가 이를 뒷받침한다.
• 히스토그램으로 샘플을 묶어 후보 분할 수를 줄이는 근사 탐색으로 대규모 데이터에서도 빠르게 학습한다.

자주 묻는 질문

관련 AI 소식