결정 트리에서 부스팅까지

저번 위클리 페이퍼에서 결정 트리와 부스팅 알고리즘을 다룬 적이 있었다. 그런데 조금 더 자세하게 하나씩 검색해보고 또 정리해보면 좋을 것 같아서 이렇게 써 본다. 여담이지만 오늘 딥러닝을 배웠는데 절반 정도만 머리에 들어오고 나머지는 흘러나갔다. 특히 수식이나 심화 동작은 강의 자료나 코드잇 강의를 다시 보면서 복습하는 게 중요하다. 지난 내용을 다시 꺼내는 것이 마치 딥러닝의 학습 과정처럼 역전파를 통해 시냅스와 뉴런을 발달시키는 과정이지 않을까 하는 엉뚱한 생각도 해봤다.

아무튼, 각설하고 정리에 들어가보겠다!

결정 트리는 스무고개처럼 질문을 하나씩 던지면서 답을 찾는다. 어떤 질문을 거쳐 결과가 나왔는지 따라가기는 쉬운 대신, 처음에 고른 질문이 달라지면 그 뒤의 질문과 최종 결과도 크게 달라질 수 있다.

그래서 하나의 모델에만 판단을 맡기지 않고 여러 모델의 답을 모아서 최종 결과를 정하는 방법이 나왔고, 이를 앙상블 학습이라고 한다. 여러 사람이 같은 문제를 풀고 답을 맞춰보는 것과 비슷하다.

다만 답을 모으는 방식은 서로 다르다. Voting은 여러 모델이 각자 문제를 푼 뒤 투표하고, Bagging은 같은 종류의 모델을 조금씩 다른 데이터로 학습시킨 뒤 결과를 합친다. Boosting에서는 첫 번째 모델이 틀린 문제를 다음 모델이 집중해서 풀고, 또 남은 오답을 그다음 모델이 이어서 보완한다. 이번 글에서는 이 차이를 결정 트리부터 하나씩 정리했다.

조건을 따라 내려가는 결정 트리

결정 트리(Decision Tree)는 데이터의 특성에 조건을 걸어 영역을 나눈다. 예를 들어 대출 심사 데이터라면 소득이 일정 금액 이상인지, 연체 이력이 있는지 같은 질문을 차례대로 만들고, 마지막에 도착한 리프 노드에서 승인 여부를 예측할 수 있다.

가장 위의 노드는 루트 노드이고, 중간에서 조건을 검사하는 노드는 내부 노드, 최종 결과를 내는 노드는 리프 노드다. 하나의 데이터는 루트에서 출발해 조건에 맞는 가지를 따라 내려가며 예측값을 얻는다.

트리를 학습할 때는 데이터를 가장 잘 나눌 수 있는 특성과 기준값을 찾는다. 대출 심사라면 소득 5,000만 원 이상인지, 연체 횟수가 1회 이상인지처럼 가능한 질문을 하나씩 시험해보고, 승인과 거절을 가장 깔끔하게 나누는 질문을 선택한다.

지니 불순도로 섞인 정도 계산하기

분류 트리에서는 한 노드 안에 서로 다른 정답이 얼마나 섞여 있는지를 불순도(impurity)로 나타낸다. 지니 불순도(Gini Impurity)는 각 클래스가 차지하는 비율을 이용해 다음처럼 계산한다.

\operatorname{Gini}(t) = 1-\sum_{k=1}^{K}p_k^2

여기서 $t$ 는 현재 노드, $K$ 는 클래스의 수, $p_k$ 는 노드 안에서 $k$ 번째 클래스가 차지하는 비율이다.

노드에 승인 데이터만 있다면 승인 비율은 1이고 거절 비율은 0이므로 지니 불순도는 0이다.

1-1^2-0^2=0

반대로 승인과 거절이 절반씩 섞여 있다면 다음과 같이 0.5가 된다. 두 클래스를 다루는 경우에는 0.5가 가장 많이 섞인 상태다.

1-0.5^2-0.5^2=0.5

승인 6건과 거절 4건이 섞인 부모 노드의 지니 불순도는 0.48이다.

\operatorname{Gini}(\text{parent}) = 1-\left(\frac{6}{10}\right)^2-\left(\frac{4}{10}\right)^2 = 0.48

어떤 조건으로 데이터를 나눴더니 왼쪽 노드에는 승인 4건만 들어가고, 오른쪽 노드에는 승인 2건과 거절 4건이 들어갔다고 하자. 왼쪽 노드의 불순도는 0이고, 오른쪽 노드의 불순도는 약 0.444다.

\operatorname{Gini}(L)=0

\operatorname{Gini}(R) = 1-\left(\frac{2}{6}\right)^2-\left(\frac{4}{6}\right)^2 \approx 0.444

두 자식 노드의 불순도를 비교할 때는 데이터 개수만큼 가중치를 준다. 데이터 4건이 들어간 왼쪽 노드와 6건이 들어간 오른쪽 노드를 합치면 분기 후의 지니 불순도는 약 0.267이다.

\operatorname{Gini}_{\text{split}} = \frac{n_L}{n}\operatorname{Gini}(L) + \frac{n_R}{n}\operatorname{Gini}(R)

여기서 $n$ 은 부모 노드의 전체 데이터 수이고, $n_L$ 과 $n_R$ 은 각각 왼쪽과 오른쪽 노드로 나뉜 데이터 수다.

\operatorname{Gini}_{\text{split}} = \frac{4}{10}\times0 + \frac{6}{10}\times0.444 \approx 0.267

부모 노드의 0.48에서 분기 후의 0.267을 빼면 불순도가 약 0.213만큼 줄었다. 결정 트리는 이런 계산을 여러 특성과 기준값에 반복하고, 불순도를 가장 많이 줄이는 질문을 현재 노드의 분기로 선택한다.

\Delta\operatorname{Gini} = \operatorname{Gini}(\text{parent}) - \operatorname{Gini}_{\text{split}}

\Delta\operatorname{Gini} = 0.48-0.267 = 0.213

엔트로피(Entropy)도 클래스가 얼마나 섞였는지 계산하는 기준이다. 계산식은 다르지만, 분기 전보다 분기 후의 엔트로피를 가장 많이 줄이는 질문을 선택한다는 원리는 같다.

H(t) = -\sum_{k=1}^{K}p_k\log_2p_k

회귀 트리는 승인과 거절 같은 클래스를 나누는 대신 각 노드의 평균값으로 숫자를 예측한다. 이때는 평균제곱오차(MSE)를 사용해 실제값이 노드의 평균에서 얼마나 떨어져 있는지 계산할 수 있다.

\operatorname{MSE}(t) = \frac{1}{n_t} \sum_{i=1}^{n_t} \left(y_i-\bar{y}_t\right)^2

여기서 $n_t$ 는 현재 노드의 데이터 수, $y_i$ 는 각 데이터의 실제값, $\bar{y}_t$ 는 현재 노드에 들어 있는 실제값의 평균이다.

분류 트리가 불순도를 가장 많이 줄이는 조건을 찾는다면, 회귀 트리는 분기 후의 가중 평균제곱오차를 가장 많이 줄이는 조건을 찾는다.

데이터 몇 개만 바뀌어도 트리 전체가 달라지는 이유

결정 트리의 장점은 예측 과정을 설명하기 쉽다는 데 있다. 어떤 조건을 통과해 결과가 나왔는지 경로를 따라갈 수 있고, 특성 사이의 비선형 관계도 별도의 수식으로 만들어 넣지 않아도 학습하며, 거리 계산을 기준으로 삼는 모델이 아니어서 일반적으로 특성 스케일링도 필요하지 않다.

결정 트리는 각 노드에서 지금 당장 불순도나 오차를 가장 많이 줄이는 질문을 선택한다. 예를 들어 소득을 기준으로 나눴을 때의 불순도 감소량이 0.213이고 연체 횟수로 나눴을 때가 0.210이라면, 소득 조건이 첫 번째 질문으로 선택된다.

그런데 훈련 데이터 한두 건이 추가되거나 빠지면서 두 값이 0.211과 0.216으로 바뀌면 첫 질문이 연체 횟수로 교체될 수 있는데, 첫 질문이 달라지면 왼쪽과 오른쪽 노드에 들어가는 데이터도 달라져 그 아래에서 다시 계산하는 모든 질문의 후보와 점수까지 바뀐다. 이처럼 데이터의 작은 변화가 트리 전체의 구조를 크게 바꿀 수 있어서 결정 트리는 분산이 높은 모델로 분류된다.

그렇다고 데이터 하나가 바뀔 때마다 모든 예측이 반드시 달라진다는 뜻은 아니다. 다만 점수가 비슷한 분기 후보가 있을 때는 작은 데이터 변화가 상위 노드의 선택을 바꿀 수 있고, 상위 노드의 변화는 아래쪽 가지 전체에 영향을 준다.

트리가 깊어질수록 과적합되는 이유

결정 트리는 불순도나 오차가 줄어드는 동안 계속 질문을 추가할 수 있어서, 깊이 제한이 없다면 처음에는 많은 데이터에 공통으로 적용되는 조건을 찾다가 나중에는 몇 개의 데이터만 구분하기 위한 세세한 조건까지 만들게 된다.

예를 들어 훈련 데이터에 소득과 연체 이력이 거의 같은 두 사람이 있는데 한 명만 대출 승인을 받았다면, 트리는 그 한 명을 구분하려고 나이나 계좌 잔액 같은 다른 특성에 추가 조건을 걸 수 있다. 계속 분기하면 마지막에는 리프 노드에 데이터가 한두 건만 남고, 각 리프의 지니 불순도를 0에 가깝게 만들 수도 있다.

훈련 데이터의 정답을 거의 전부 맞히더라도 그 조건이 새로운 고객에게 반복된다는 보장은 없는데, 우연히 포함된 특이한 사례나 잘못 기록된 값, 잡음까지 규칙으로 외웠기 때문이다. 훈련 성능은 높지만 새로운 데이터의 성능이 떨어지는 이 상태가 과적합이다.

트리의 최대 깊이를 제한하면 지나치게 세세한 질문이 만들어지는 것을 막을 수 있다. 리프 노드에 필요한 최소 데이터 수를 정하거나 분기했을 때 불순도가 충분히 줄어들지 않으면 멈출 수 있고, 이미 만든 트리에서 효과가 작은 가지를 제거하는 가지치기(pruning)도 같은 목적으로 사용한다.

이런 제한은 한 트리의 복잡도를 줄이는 방법이다. Bagging과 Random Forest는 학습 데이터와 특성을 조금씩 다르게 사용해 여러 트리를 만들고, 결과를 투표하거나 평균 내어 특정 트리 하나의 변화가 최종 예측에 미치는 영향을 줄인다.

여러 모델을 합치는 세 가지 방식

앙상블(Ensemble)은 여러 모델의 예측을 결합해 하나의 결과를 만드는 방법이다. Voting, Bagging, Boosting은 모두 앙상블에 속하지만 모델을 학습시키는 관계가 다르다.

Voting은 여러 모델을 같은 문제에 독립적으로 학습시킨 뒤 결과를 합친다. 흔히 로지스틱 회귀, SVM, 결정 트리처럼 서로 다른 종류의 모델을 사용하며, 최종 분류 결과 중 다수결로 클래스를 정하면 Hard Voting이고 각 모델이 예측한 클래스별 확률을 평균 내어 결정하면 Soft Voting이다.

Bagging은 같은 종류의 모델을 여러 개 사용하되, 원본 데이터에서 복원 추출한 서로 다른 훈련 세트를 각 모델에 제공한다. 각 모델은 독립적으로 학습할 수 있어서 병렬 처리가 가능하고, 분류에서는 투표, 회귀에서는 평균으로 결과를 합친다. 데이터 변화에 민감한 결정 트리를 여러 개 만들어 평균을 내면 한 트리의 높은 분산을 줄일 수 있다.

Random Forest는 Bagging을 결정 트리에 적용하면서 각 분기에서 사용할 특성도 무작위로 일부만 선택한다. 모든 트리가 늘 같은 강한 특성부터 고르면 서로 비슷한 구조가 만들어질 수 있는데, 특성 선택에도 무작위성을 넣어 트리 사이의 상관관계를 낮춘다.

Boosting은 앞의 두 방식과 달리 모델을 순서대로 학습한다. 앞 모델이 잘 맞히지 못한 데이터나 남긴 오차를 다음 모델이 보완하고, 이렇게 만든 약한 학습기들을 합쳐 최종 예측을 만든다. 앞 단계의 결과가 다음 단계에 필요하므로 모델 전체를 완전히 독립적으로 학습할 수는 없다.

구분	모델 사이의 관계	결과를 합치는 방식	주로 보완하는 부분
Voting	여러 모델을 독립적으로 학습	다수결 또는 확률 평균	모델마다 다른 판단의 결합
Bagging	같은 종류의 모델을 서로 다른 표본으로 독립 학습	투표 또는 평균	단일 모델의 높은 분산
Boosting	앞 모델의 오차를 참고해 순차 학습	약한 학습기의 가중 합	앞 모델이 남긴 오차

틀린 데이터에 집중하는 AdaBoost

AdaBoost는 처음에는 모든 훈련 데이터에 같은 가중치를 준다. 첫 번째 약한 학습기가 예측을 마치면 잘못 분류한 데이터의 가중치를 높이고, 다음 학습기는 그 데이터를 더 중요하게 보며 학습한다.

마지막에는 성능이 좋은 학습기의 의견을 더 크게 반영해 예측을 합친다. 작은 결정 트리 여러 개로 하나의 트리보다 나은 결과를 만들 수 있지만, 잘못된 라벨이나 이상치도 계속 틀리는 데이터로 취급하므로 잡음에 지나치게 집중할 수 있다.

손실을 줄이는 방향으로 가는 Gradient Boosting

Gradient Boosting은 현재 모델이 남긴 오차를 줄이는 방향으로 새로운 약한 학습기를 추가한다. 회귀 문제에서는 앞 모델의 예측과 실제값 사이에 남은 잔차를 다음 트리가 학습한다고 먼저 이해할 수 있다. 더 일반적으로는 손실 함수가 감소하는 방향인 음의 그래디언트를 새 트리가 근사한다.

새 트리의 예측을 한 번에 전부 반영하지 않고 학습률만큼 더하는 과정은 다음처럼 나타낼 수 있다.

F_m(x) = F_{m-1}(x) + \eta h_m(x)

여기서 $F_{m-1}(x)$ 는 지금까지 만든 모델이고, $h_m(x)$ 는 새로 추가하는 약한 학습기이며, $\eta$ 는 새 학습기의 반영 정도를 조절하는 학습률이다. 학습률을 낮추면 한 번에 수정하는 폭이 작아지는 대신 더 많은 트리가 필요할 수 있다.

트리를 차례대로 추가하므로 Bagging보다 학습 시간이 길어질 수 있고, 트리 수와 깊이, 학습률을 함께 조절해야 한다. 모델을 지나치게 복잡하게 만들면 부스팅도 잡음까지 학습할 수 있다.

같은 출발점에서 갈라진 부스팅 모델들

XGBoost, LightGBM, CatBoost는 Gradient Boosting의 기본 흐름을 공유하지만, 계산을 줄이는 방법과 과적합을 제어하는 방식, 다루기 편한 데이터에서 차이가 난다.

XGBoost는 손실 함수의 1차 미분뿐 아니라 2차 미분 정보도 활용하고, 목적 함수에 트리 복잡도를 제한하는 규제 항을 포함한다. 결측값과 희소 데이터를 다루는 기능, 가지치기, 병렬 계산 같은 구현상의 최적화도 제공한다. 조절할 수 있는 값이 많은 만큼 처음부터 적절한 설정을 찾는 일은 단순하지 않다.

LightGBM은 연속적인 특성값을 여러 구간으로 묶은 히스토그램을 사용해 분기 후보를 빠르게 계산한다. 같은 깊이의 노드를 차례대로 확장하기보다 현재 손실을 가장 많이 줄일 수 있는 리프를 먼저 나누는 leaf-wise 방식을 사용하므로, 큰 데이터에서 학습 속도와 메모리 사용량에 강점이 있다. 다만 한쪽 가지가 빠르게 깊어질 수 있어서 데이터가 작을 때는 리프 수와 최대 깊이를 제한하지 않으면 과적합되기 쉽다.

CatBoost는 범주형 특성을 많이 포함한 데이터에 강점이 있다. 범주형 값을 모두 원-핫 인코딩하지 않고 내부에서 통계값으로 변환하며, 현재 데이터의 정답이 변환 과정에 미리 섞이는 문제를 줄이기 위해 데이터 순서를 활용한다. 범주형 데이터의 전처리 부담은 줄어들지만, 데이터와 설정에 따라 학습 시간이 길어질 수 있다.

세 모델 중 하나가 언제나 가장 좋은 것은 아니다. 데이터 크기, 범주형 특성의 비중, 학습 시간과 메모리 제한, 설명 가능성, 하이퍼파라미터를 조정할 여유를 함께 보고 선택해야 한다.

한 번에 다 이해하기는 어렵다

처음 XGBoost, LightGBM, CatBoost라는 이름을 연달아 봤을 때는 솔직히 비슷한 모델이 왜 이렇게 많은지부터 헷갈렸다. 각각의 설명을 따로 읽을 때는 XGBoost와 LightGBM은 빠르고, CatBoost는 범주형 데이터에 좋다는 내용까지는 알겠는데, 이 모델들이 기존 부스팅 방식을 어떻게 바꿨는지는 잘 연결되지 않았다.

결정 트리부터 다시 따라가니 Bagging과 Boosting의 차이는 조금 분명해졌다. Bagging은 서로 따로 학습한 트리의 결과를 모아 한 트리의 흔들림을 줄이고, Boosting은 앞 트리가 남긴 오차를 다음 트리가 이어서 보완한다. XGBoost, LightGBM, CatBoost도 완전히 별개의 모델이라기보다 이 부스팅 과정을 각자 다른 방향으로 개선한 모델이었다.

물론 어떤 데이터에서 어떤 모델을 골라야 하는지, 하이퍼파라미터를 어떻게 조정해야 하는지는 아직 직접 부딪혀봐야 알 것 같다. 오늘 배운 딥러닝도 아마 한 번에 이해되지는 않을 텐데, 이렇게 묵은 내용을 다시 꺼내 쓰다 보면 따로 흩어져 있던 개념들이 하나씩 연결되지 않을까 생각해 본다.