결정 트리와 랜덤 포레스트(Decision trees and random forests)

스무고개처럼 결정 트리⁠(decision tree)⁠는 예/아니오 질문을 차례로 던져 답을 좁힙니다. 'x < −0.5인가?'에 예라면 다음은 'y < 0.6인가?'를 묻는 식입니다. 질문이 끝나는 곳(잎)에서는 거기까지 내려온 학습 자료의 다수결로 답합니다. 질문 하나는 좌표 하나를 문턱⁠(threshold)⁠과 비교하므로 평면은 축에 나란한 직사각형들로 나뉩니다. 아래 점 60개는 비스듬한 직선 위쪽이면 노랑, 아래쪽이면 파랑이 되게 만든 뒤, 점마다 10%의 확률⁠(probability)⁠로 색을 뒤집어 잡음을 넣은 자료입니다(이 60개에서는 8개가 뒤집혔습니다).

첫 질문은 무엇이 좋을까요? 답을 들은 뒤 양쪽의 색이 저마다 한쪽으로 쏠리는 질문입니다. 쏠림은 엔트로피로 잽니다. 노랑의 비율이 p인 무리의 엔트로피는 $H = -p\log_2 p - (1-p)\log_2(1-p)$비트로, 반반이면 1, 한 색뿐이면 0입니다. 질문의 값어치는 질문 전의 엔트로피에서 질문 뒤 두 무리의 엔트로피를 크기로 가중 평균한 것을 뺀 정보 이득입니다. 예를 들어 파랑 30, 노랑 30(1비트)을 '파랑 18, 노랑 2'인 20개와 '파랑 12, 노랑 28'인 40개로 나누면, 두 무리의 엔트로피는 약 0.469와 0.881이고 가중 평균은 $(20 \times 0.469 + 40 \times 0.881)/60 \approx 0.744$이므로 이득은 약 0.256비트입니다.

에 대한 질문의 문턱을 노란 손잡이로 끌어 보세요. 질문 전 엔트로피 비트가, 문턱 아래 , 문턱 위 로 나뉘어 정보 이득⁠(information gain)⁠은 비트입니다. 둘째 그림은 문턱을 옮길 때의 이득이고, 흰검은 점이 가장 좋은 문턱(이득 비트)입니다.

정보 이득은 질문의 답과 색 사이의 상호 정보량⁠(mutual information)⁠과 같습니다. 질문 전 불확실성 $H(Y)$에서 답을 안 뒤의 평균 불확실성 조건부 엔트로피⁠(conditional entropy)⁠ $H(Y \mid \text{답})$를 뺀 것이 곧 $I(\text{답}; Y)$이기 때문입니다. 엔트로피 대신, 무리에서 점 하나를 뽑고 되돌려 놓은 뒤 다시 하나를 뽑을 때 두 색이 다를 확률인 지니 불순도⁠(Gini impurity)⁠ $1 - \sum_c p_c^2$를 쓰기도 하는데, 고르는 질문은 대개 비슷합니다. 문턱 후보는 이웃한 두 점의 한가운데만 보면 됩니다. 두 점 사이에서 문턱을 움직여도 나뉘는 방식이 바뀌지 않기 때문입니다. 둘째 그림의 이득이 계단 모양인 것도 그래서입니다.

나무는 이 일을 되풀이해 자랍니다. 나뉜 두 무리 각각에서 다시 가장 좋은 질문을 고르고, 정한 깊이에 이르거나 한 색만 남으면 멈춥니다. 매 순간 눈앞의 이득만 보는 욕심쟁이 알고리즘⁠(greedy algorithm)⁠이라 전체로 가장 작은 나무를 찾는다는 보장은 없습니다. 자료를 모두 맞히면서 평균 질문 수가 가장 적은 결정 트리를 찾는 문제는, 1976년 하이아필과 리베스트가 NP-완전⁠(NP-complete)⁠임을 보였습니다(P 대 NP). 탐욕의 한계를 보여 주는 예가 XOR입니다. 네 사분면에 노랑과 파랑이 엇갈려 있으면 어떤 첫 질문도 이득이 0에 가깝지만, 깊이 2의 나무는 완벽하게 가릅니다.

깊이 D = , . 학습 자료의 정확도는 , 같은 방법으로 따로 뽑은 시험 자료 1000개의 정확도는 입니다(잎 개). 첫째 그림의 흰검은 점선이 숨은 규칙의 경계이고, 나무 한 그루일 때 흰검은 테두리가 잎마다의 방입니다.

깊이를 올려 보세요. 나무 한 그루는 깊이 2–3에서 시험 정확도가 약 81%로 가장 높고, 깊이 6부터는 학습 자료를 100% 맞히는 대신 시험 정확도가 약 74%로 떨어집니다. 잡음으로 뒤집힌 점 하나하나에까지 작은 방을 만들어 준 결과입니다(과적합⁠, overfitting⁠). 시험 자료도 점마다 10% 확률로 뒤집었으므로 어떤 모형도 기대 정확도가 90%를 넘을 수 없습니다(이 1000개에서는 99개가 뒤집혀 있어, 숨은 규칙 그대로 답해도 90.1%입니다). 깊은 나무는 편향이 작고 분산⁠(variance)⁠이 큰 모형의 대표입니다(편향–분산 분해⁠(bias–variance decomposition)⁠). 자료가 조금만 바뀌어도 첫 질문이 바뀌고, 그 아래가 통째로 달라집니다. 그래서 깊이나 잎의 최소 크기를 제한하거나, 크게 키운 뒤 교차 검증⁠(cross-validation)⁠으로 가지를 쳐냅니다.

다른 해법은 흔들리는 나무를 여럿 길러 평균하는 것입니다. 랜덤 포레스트는 나무마다 학습 자료에서 n개를 복원 추출(부트스트랩⁠, bootstrap⁠)해서 기르고, 질문을 고를 때마다 쓸 수 있는 좌표를 무작위로 제한합니다(여기서는 x와 y 가운데 하나를 무작위로 고릅니다). 복원 추출⁠(sampling with replacement)⁠로 뽑으면 한 나무가 보는 서로 다른 점은 평균적으로 전체의 $1 - (1 - 1/n)^n$입니다. n = 60이면 약 63.5%이고, n이 크면 $1 - 1/e \approx 63.2\%$에 다가갑니다. 분산이 v이고 서로의 상관계수⁠(correlation coefficient)⁠가 ρ인 예측 B개를 평균하면 분산이 $\rho v + (1-\rho)v/B$가 되므로, 무작위성으로 나무들을 덜 닮게 만들수록 평균의 효과가 커집니다. 모델을 '랜덤 포레스트(나무 30그루)'로 바꾸면 배경이 나무들의 득표 비율에 따라 두 색을 섞어 칠해집니다. 이 자료에서는 깊이 8의 나무 30그루가 시험 정확도 약 80%를 내, 같은 깊이의 한 그루(약 74%)보다 낫습니다. 점마다 그 점을 뽑지 않은 나무들(평균 약 37%)만으로 예측해 오차를 재면 따로 떼어 둔 자료 없이도 일반화 오차를 어림할 수 있습니다(OOB 오차⁠, out-of-bag error⁠). 나무를 차례로 더하며 앞 나무들의 오차를 메우게 하는 부스팅⁠(boosting)⁠도 널리 쓰입니다.

결정 트리에는 독특한 장점이 있습니다. 질문이 좌표의 순서만 보므로 특성에 로그를 씌우거나 단위를 바꿔도 나무가 그대로이고, 그래서 정규화와 달리 크기를 맞출 필요가 없습니다. 숫자와 범주⁠(category)⁠가 섞인 자료도 다루기 쉽고, 얕은 나무는 사람이 읽을 수 있습니다. 약점은 비스듬한 경계를 계단으로밖에 흉내 내지 못한다는 것입니다. 첫째 그림의 경계가 바로 그렇습니다. 1963년 모건과 손퀴스트의 AID에서 시작해, 1984년 브라이먼, 프리드먼, 올셴, 스톤의 CART와 1986년 로스 퀸런의 ID3가 오늘날 형태를 만들었습니다. 배깅(1996)과 랜덤 포레스트(2001)도 레오 브라이먼의 작업입니다.

이어지는 곳. 같은 모양의 나무가 정렬의 하한⁠(lower bound)⁠ 증명에도 나옵니다. 비교 정렬⁠(comparison sort)⁠을 비교 질문의 결정 트리로 보면 잎이 적어도 n!개여야 하므로 깊이가 $\log_2 n!$ 이상입니다. 스무고개로 물건 하나를 알아맞힐 때 평균 질문 수는 엔트로피보다 작을 수 없고, 허프만 부호⁠(Huffman coding)⁠의 나무가 그 한계에서 1비트 안쪽까지 다가가는 가장 좋은 질문 순서를 줍니다. 다만 거기서는 질문을 마음대로 고를 수 있고, 여기서는 '좌표 < 문턱' 꼴로 제한되어 있습니다. 좌표 대신 거리로 이웃을 찾는 최근접 이웃 분류⁠(k-nearest neighbors classification)⁠도 자료에서 바로 경계를 만드는 방법이지만, 경계의 모양은 축에 매이지 않습니다. 입력 공간을 영역으로 나눠 영역마다 따로 답하게 한다는 점에서 전문가 혼합⁠(mixture of experts)⁠도 결정 트리를 닮았는데, 거기서는 딱 잘린 문턱 대신 소프트맥스⁠(softmax)⁠ 점수로 몇 개의 '전문가' 신경망⁠(neural network)⁠을 고릅니다. 나무는 그래프 이론⁠(graph theory)⁠의 트리⁠(tree)⁠이기도 해서, 꼭짓점⁠(vertex)⁠ n개에 변이 n − 1개입니다.