[이론] 랜덤 포레스트 (1)

숲은 어떻게 나무보다 똑똑해지는가

어설픈 조언자 500명이 최고 전문가 한 명을 이기는 통계학적 이유

1906년, 영국 플리머스의 가축 품평회. 통계학자 프랜시스 골턴은 심드렁한 마음으로 한 가지 실험을 지켜보고 있었다. 관람객 787명이 살찐 황소 한 마리의 무게를 각자 종이에 적어 냈다. 정육점 주인도 있었고, 소를 난생처음 본 사람도 있었다.

골턴은 대중이 얼마나 어리석은지 증명하고 싶었다. 그런데 787개 답의 중앙값을 계산해 보니 1,197파운드. 실제 무게는 1,198파운드였다.

우리는 이 이야기를 "군중의 지혜"라는 낭만적인 제목으로 기억한다. 하지만 여기엔 골턴도 알지 못했던 조건이 하나 숨어 있었다. 그리고 그 조건을 정확히 짚어내 알고리즘으로 만든 사람이, 90년 뒤의 통계학자 레오 브라이만이다. 그가 만든 것이 랜덤 포레스트(Random Forest) 다.

이 글은 랜덤 포레스트에 관한 글이지만, 사실은 당신이 이직을 고민할 때, 두 번째 병원을 찾아갈 때, 면접에서 사람을 뽑을 때 쓰게 될 사고법에 관한 글이다.

1. 나무 한 그루의 딜레마

랜덤 포레스트의 '나무'는 결정 트리(decision tree)다. 스무고개와 똑같다. "연봉이 6천만 원 이상인가?" 예. "재택이 가능한가?" 아니오. 질문을 계속 던져 답에 도달한다.

문제는 나무를 얼마나 깊게 키우느냐다. 여기서 통계학에서 가장 아름다운 항등식 중 하나가 등장한다. 편향-분산 분해(bias-variance decomposition) 다. 예측 오차는 $E[(y-\hat{f}{)}^2]={\text{Bias}}^2+\text{Var}+{\sigma }^2$ 로 쪼개진다.

편향(bias) 은 고집이다. "나는 강남 아파트는 무조건 오른다고 본다"라고 말하는 사람. 어떤 데이터를 보여줘도 결론이 같다. 안정적이지만 체계적으로 틀린다.

분산(variance) 은 변덕이다. 오늘 신문 헤드라인 하나에 투자 전략을 바꾸는 사람. 평균적으로는 맞을지 몰라도, 매번 다른 소리를 한다.

여기서 잔인한 진실이 나온다. 이 둘은 대개 상충한다. 나무를 얕게 치면 편향이 커지고, 끝까지 깊게 키우면 분산이 폭발한다. 학습 데이터는 100% 맞히는데 새 데이터에선 헛소리를 하는 상태, 즉 과적합이다.

전통적인 해법은 타협이었다. 적당히 깊게, 적당히 가지치기. 그런데 브라이만은 다르게 생각했다. 편향은 나무가 알아서 낮추게 두고, 분산만 따로 제거하면 되지 않나?

이게 랜덤 포레스트의 출발점이다. 나무를 가지치기 없이 끝까지 키운다. 편향은 거의 0이 된다. 대신 미친 듯이 날뛰는 분산은 나무를 여러 그루 심어서 잡는다.

실생활 번역. 조언을 구할 때 "적당히 신중한 사람 한 명"을 찾지 마라. 그런 사람은 편향과 분산을 어정쩡하게 반씩 안고 있다. 그보다 주관이 뚜렷하고 자기 경험에 충실한 사람 여럿을 만나라. 개별로는 극단적이어도, 여럿을 모으면 극단이 상쇄된다. 이게 통계적으로 더 낫다.

2. 인생을 여러 번 사는 법: 부트스트랩

문제가 하나 있다. 나무를 500그루 키우려면 데이터가 500세트 필요한데, 우리에겐 딱 한 세트뿐이다.

브라이만의 스승 격인 브래들리 에프론이 1979년에 내놓은 답이 부트스트랩(bootstrap) 이다. 이름은 "자기 신발끈을 잡아당겨 스스로를 들어 올린다"는 허풍 관용구에서 왔다. 말도 안 되는 일을 해낸다는 뜻이다.

방법은 어이없을 만큼 단순하다. 데이터가 1,000개 있다면, 거기서 1,000개를 뽑는다. 단, 뽑은 걸 다시 넣고 뽑는다(복원추출). 결과적으로 어떤 데이터는 세 번 들어가고, 어떤 데이터는 한 번도 안 들어간다. 이렇게 만든 "가짜 데이터셋"은 원본과 비슷하면서도 미묘하게 다르다. 이 짓을 500번 반복하면 500개의 평행우주가 생긴다.

여기서 아름다운 숫자가 하나 튀어나온다. 특정 데이터 하나가 한 번도 뽑히지 않을 확률은 ${\left(1-\frac{1}{n}\right)}^n\stackrel{n\to \infty }{\to }{e}^{-1}\approx 0.368$, 즉 약 36.8% 다. 데이터 크기와 상관없이, 각 나무는 전체 데이터의 대략 3분의 1을 못 보고 자란다. 이 버그처럼 보이는 성질이 나중에 결정적인 선물이 된다.

실생활 번역. 당신은 인생을 한 번밖에 못 산다. 하지만 과거의 경험을 다시 섞어서 곱씹는 것만으로도 "만약 그때 그 사건이 없었다면?"이라는 평행우주를 만들 수 있다. 지난 10년의 실패 사례 중 무작위로 절반씩 골라 세 번 회고해 보라. 세 번의 회고에서 공통으로 나오는 교훈만이 진짜 교훈이다. 한 번만 나오는 건 그 사건에 딸린 우연이다.

3. 평균의 폭력: 배깅과 큰 수의 법칙

500그루가 각자 답을 냈다. 이제 합친다. 회귀 문제면 평균, 분류 문제면 다수결. 이 과정을 배깅(bagging, Bootstrap AGGregatING) 이라 부른다.

왜 평균이 통하는가. 큰 수의 법칙(law of large numbers) 때문이다. 독립적인 확률변수를 평균 내면, 표본이 늘어날수록 참값으로 수렴한다. 개별 나무가 위로 틀리고 아래로 틀리며 요동쳐도, 500개를 평균 내면 요동이 상쇄된다.

이 법칙은 실무적으로 아주 중요한 답을 준다. "나무를 몇 그루 심어야 하나요?" 답은 많을수록 좋지만 수익은 체감한다는 것이다. 10그루에서 100그루로 갈 때의 개선은 극적이고, 500그루에서 5,000그루로 갈 때는 거의 없다. 수렴했기 때문이다. 더 중요한 건, 나무를 늘려서 과적합이 되지는 않는다는 점이다. 이건 부스팅 계열과 결정적으로 다른 성질이다.

4. 진짜 비밀: 다들 똑같이 틀리면 소용없다

자, 여기가 이 글의 심장이다.

골턴의 황소 실험에는 숨은 조건이 있었다고 했다. 만약 787명이 서로 답을 보여주며 상의했다면? 목소리 큰 정육점 주인이 "1,500파운드!"라고 외쳤다면? 평균은 처참하게 빗나갔을 것이다. 군중의 지혜는 군중이 서로 독립적일 때만 작동한다.

이걸 수식으로 쓰면 이렇다. 각 나무의 분산이 ${\sigma }^2$ 이고 나무들 사이의 상관계수 가 $\rho$ 일 때, $B$ 그루를 평균 낸 앙상블의 분산은 ${\text{Var}}_{\text{ensemble}}=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2$ 이 된다.

이 식을 한참 노려보면 소름이 돋는다. 오른쪽 항 $\frac{1-\rho }{B}{\sigma }^2$ 은 나무를 늘리면 0으로 사라진다. 그런데 왼쪽 항 $\rho {\sigma }^2$ 은 $B$ 와 무관하다. 나무를 백만 그루 심어도 없어지지 않는다.

즉, 나무들이 서로 닮았다면 아무리 많이 심어도 소용없다. 상관 0.9짜리 나무 백만 그루는 상관 0.3짜리 나무 30그루보다 못하다.

여기서 랜덤 포레스트의 이름값을 하는 두 번째 '랜덤'이 등장한다. 브라이만은 각 나무가 서로 닮지 않게 하려고, 분기할 때마다 전체 특성 중 무작위로 뽑은 일부만 후보로 허용했다. 전체 특성이 $p$ 개일 때 분류는 $\sqrt{p}$ 개, 회귀는 $p/3$ 개 정도만 본다.

조합론 적으로 계산해 보면 이게 얼마나 강력한지 알 수 있다. 특성이 100개일 때 매 분기마다 10개를 뽑는 방법은 $\left(\genfrac{}{}{0ex}{}{100}{10}\right)\approx 1.7\times 10^{13}$ 가지. 깊이 10짜리 나무 하나가 지날 수 있는 경로의 수는 사실상 무한하다. 같은 데이터를 봐도 두 나무가 똑같이 생길 확률은 0에 가깝다.

얼핏 보면 자해행위다. 가장 좋은 특성을 일부러 안 보여주는 것이니까. 실제로 개별 나무의 성능은 떨어진다. 하지만 나무들 사이의 상관 $\rho$ 가 훨씬 더 크게 떨어진다. 이 거래에서 우리는 이긴다.

실생활 번역. 이건 정말로 당신의 의사결정을 바꿔야 하는 대목이다.

• 이직을 고민할 때 같은 회사 동료 다섯 명에게 묻는 건 한 명에게 다섯 번 묻는 것과 같다. 상관계수가 1에 가깝기 때문이다. 동료 한 명, 다른 업계 친구 한 명, 헤드헌터 한 명, 그 일을 그만둔 사람 한 명에게 물어라. 네 명이 스무 명 몫을 한다.
• 회의에서 의견을 모을 때는 말하기 전에 각자 종이에 먼저 쓰게 하라. 발언 순서대로 의견이 오염되는 순간 $\rho$ 가 치솟는다. 실리콘밸리에서 유행한 "침묵의 브레인스토밍"은 사실 이 수식의 응용이다.
• 뉴스를 볼 때 같은 논조의 매체 열 곳을 읽는 것은 정보량이 한 곳과 다르지 않다.
• 포트폴리오를 짤 때 삼성전자, SK하이닉스, 마이크론을 담는 건 분산투자가 아니다. 종목 수가 아니라 상관계수가 분산을 결정한다.

5. 브라이만의 저울

브라이만은 2001년 논문에서 이 직관을 정리해 일반화 오차의 상한을 증명했다. Breiman 일반화 오차 상한 은 $P{E}^{\ast }\le \frac{\bar{\rho }(1-s^2)}{s^2}$ 로 쓴다. 여기서 $s$ 는 나무의 강도(strength), 즉 개별 나무가 얼마나 정확한가이고, $\bar{\rho }$ 는 나무들 사이의 평균 상관이다.

이 부등식이 말하는 바는 명료하다. 좋은 앙상블은 강한 개체와 낮은 상관의 곱이다. 그리고 둘은 서로 밀고 당긴다. 무작위성을 키우면 $\bar{\rho }$ 는 내려가지만 $s$ 도 같이 내려간다. 무작위성을 줄이면 $s$ 는 올라가지만 $\bar{\rho }$ 도 올라간다. 이 저울의 균형점을 찾는 것이 하이퍼파라미터 튜닝의 본질이다.

또 하나 중요한 함의가 있다. 이 상한은 $B$ 에 의존하지 않는다. 나무를 아무리 늘려도 오차가 어떤 값 이상으로 나빠지지 않는다는 뜻이다. "앙상블은 크게 만들수록 과적합한다"는 오래된 통념을 이 부등식이 깨뜨렸다.

실생활 번역. 팀을 꾸릴 때 두 가지만 보면 된다. 개개인이 유능한가($s$), 그리고 서로 다른가($\bar{\rho }$). 유능하지만 전부 같은 학교 같은 전공 출신인 팀은, 평범하지만 배경이 제각각인 팀보다 못한 판단을 내린다. 브라이만의 부등식이 다양성 채용의 수학적 근거다.

6. 나무는 어떻게 좋은 질문을 고르는가

나무가 "연봉 6천만 원"이라는 기준을 고른 건 어떻게일까. 여기서 불순도 측정(impurity measure) 이 나온다. 분류 문제에서 노드의 지저분함은 지니 지수 $\text{Gini}=1-{\sum }_k{p}_k^2$ 또는 엔트로피 $H=-{\sum }_k{p}_k\log p_k$ 로 잰다.

한 상자에 빨간 공만 있으면 불순도 0으로 완벽하게 순수하다. 빨강과 파랑이 반반이면 최대다. 나무는 가능한 모든 분할 기준을 시험해 보고, 분할 후 자식 노드들의 가중평균 불순도가 가장 많이 줄어드는 질문을 고른다. 좋은 질문이란 애매한 덩어리를 깔끔한 두 덩어리로 쪼개는 질문이다.

회귀 문제에서는 불순도 자리에 분산이 들어간다. 분산 감소 기준 은 $\Delta ={\text{MSE}}_{\text{parent}}-\frac{n_L}{n}{\text{MSE}}_L-\frac{n_R}{n}{\text{MSE}}_R$ 이다. 부모 노드의 흩어짐에서 자식 노드들의 흩어짐을 크기로 가중해 뺀다. 이 값이 클수록 그 질문은 세상을 잘 정리한 것이다.

실생활 번역. 좋은 질문의 정의가 여기 있다. 답을 듣기 전과 후에 당신의 판단이 가장 크게 갈리는 질문이 가장 좋은 질문이다.

면접에서 "성실하신가요?"는 최악의 질문이다. 답이 뻔해서 지원자를 전혀 나누지 못한다. 불순도 감소가 0이다. "지난 프로젝트에서 당신이 틀렸다는 걸 언제 알았나요?"는 다르다. 답이 사람마다 극적으로 갈린다. 의사가 진단할 때, 형사가 심문할 때, 스무고개를 할 때 모두 같은 원리다. 정보량은 답의 내용이 아니라 답의 분산에 있다.

7. 스스로 채점하는 시험지: OOB

2장에서 남겨둔 선물을 회수할 시간이다.

각 나무는 부트스트랩 때문에 데이터의 약 36.8%를 보지 못하고 자랐다. 이 못 본 데이터를 OOB(Out-of-Bag) 샘플 이라 부른다. 그 나무에게 이건 완벽한 '처음 보는 데이터'다.

그래서 이런 채점이 가능하다. 데이터 하나를 집는다. 전체 500그루 중 그 데이터를 학습에 쓰지 않은 나무들만 골라내서, 평균 약 185그루에게만 예측을 시킨다. 이 예측을 실제 값과 비교한다. 모든 데이터에 대해 반복한다.

결과는 사실상 공짜로 얻은 교차검증이다. 검증셋을 따로 떼어놓지 않고도 일반화 성능을 추정할 수 있다. 데이터가 귀한 분야, 그러니까 의료나 소재나 고장진단처럼 샘플 하나 얻는 데 비용이 큰 영역에서 이건 엄청난 특권이다.

실생활 번역. 당신의 판단력을 검증하려면 당신이 그 사건을 알기 전에 남긴 기록이 필요하다. 투자 판단을 내릴 때마다 근거를 적어두고 6개월 뒤에 꺼내 보라. 결과를 알고 나서 회고하는 것은 채점이 아니라 자기 정당화다. OOB의 핵심은 "학습에 쓰지 않았다"는 것이지 "나중에 확인한다"가 아니다.

8. 무엇이 정말 중요했나: 변수 중요도와 순열 검정

랜덤 포레스트는 500그루가 얽힌 검은 상자다. 그런데 놀랍게도 해석할 방법이 있다.

첫 번째 변수 중요도 는 MDI, 즉 불순도 감소 평균이다. 500그루 전체에서 그 특성이 분할에 쓰였을 때 줄어든 불순도를 모두 더한다. 많이 줄인 특성이 중요한 특성이다. 계산이 공짜라 널리 쓰이지만 함정이 있다. 값의 종류가 많은 특성, 이를테면 연속형 변수나 고유 ID 같은 것이 우연히 데이터를 잘 쪼갤 기회를 더 많이 얻어서 실제보다 중요해 보인다. 이걸 카디널리티 편향이라 한다.

그래서 브라이만이 제안한 두 번째 방법이 훨씬 정직하다. 순열 검정(permutation test) 에 기반한 MDA다.

방법은 통쾌할 만큼 단순하다. 그 특성의 값만 무작위로 뒤섞는다. 나이 열을 통째로 셔플해서 20대의 나이가 70대에게 붙게 만든다. 그리고 OOB 오차가 얼마나 나빠지는지 본다.

• 오차가 확 나빠졌다. 그 특성은 진짜로 중요했다.
• 오차가 그대로다. 모델은 애초에 그 특성을 믿지 않았다.

순열 검정은 통계학에서 가장 오래되고 가장 가정이 적은 기법이다. 분포를 가정하지 않는다. "이 관계가 우연이라면 어떤 모습일지" 직접 만들어서 비교할 뿐이다.

실생활 번역. 이건 당장 오늘 써먹을 수 있다. 무언가가 중요한지 알고 싶으면, 그것을 무작위로 망가뜨렸을 때 결과가 얼마나 달라지는지 상상하라. 회의에 참석 안 했다면? 그 광고를 안 했다면? 이 기능을 뺐다면? 결과가 그대로일 것 같다면 그건 중요한 게 아니라 그냥 습관이다. 조직에서 "이 보고서를 아무도 안 읽는다면 무슨 일이 생기나?"라는 질문이 무섭도록 효과적인 이유다.

9. "90% 확신합니다"를 액면 그대로 믿지 마라

마지막 함정. 랜덤 포레스트가 "이 환자가 양성일 확률 90%"라고 말했다면, 실제로 그런 환자 100명 중 90명이 양성일까?

아니다. 여기서 확률은 500그루 중 450그루가 양성이라고 투표했다는 뜻일 뿐이다. 투표 비율과 실제 확률은 다른 것이다.

랜덤 포레스트의 확률 출력은 특유의 왜곡을 갖는다. 다수결 평균이라는 구조 때문에 극단값이 잘 안 나온다. 진짜 확률이 0.02인 사건도 0.10쯤으로, 0.98인 사건도 0.90쯤으로 보고하는 경향이 있다. 어중간한 쪽으로 눌린다.

그래서 확률 보정(calibration) 이 필요하다. 예측 확률이 0.9인 사례들을 모아 실제 비율을 재고, 그 관계를 함수로 학습해 보정한다. 시그모이드 $\sigma (z)=\frac{1}{1+e^{-(az+b)}}$ 를 씌우는 Platt scaling, 단조 증가 함수를 자유롭게 학습하는 Isotonic regression이 대표적이다.

이 단계는 예측의 순위가 중요할 땐 생략해도 된다. 하지만 확률 숫자 자체로 의사결정을 할 때, 그러니까 보험료를 매기거나 수술 여부를 정하거나 재고를 발주할 때 보정 없이 쓰는 건 위험하다.

실생활 번역. 사람의 확신도 보정이 필요하다. 어떤 사람은 "확실해요"가 실제로 70% 맞고, 어떤 사람은 "글쎄요"가 90% 맞는다. 주변 사람의 발언을 몇 번 기록해 보면 각자의 보정 곡선이 보인다. 그 사람의 확신도를 곧이곧대로 받지 말고, 그 사람 전용 환율로 환전해서 받아라. 그리고 당신 자신의 환율도 재보라. 대부분의 사람은 과신 쪽으로 기울어져 있다.

에필로그: 브라이만이 남긴 사고법

레오 브라이만은 2005년에 세상을 떠났다. 그는 통계학계에서 오래 이단아였다. 우아한 수식으로 세상을 설명하려는 주류에 맞서, 예측이 맞으면 그게 좋은 모델이라고 주장했다. 랜덤 포레스트는 그 철학의 결정체다.

그가 남긴 것을 여덟 줄로 줄이면 이렇다.

랜덤 포레스트가 20년 넘게 살아남은 이유는 최첨단이어서가 아니다. 딥러닝이 세상을 뒤덮은 지금도 표 형태 데이터에서는 여전히 강력한 기본기다.

하지만 더 오래 살아남을 것은 알고리즘이 아니라 그 안에 담긴 태도일지 모른다. 자기 판단을 의심하고, 자기와 다른 것을 일부러 찾아 나서고, 확신을 액면가로 받지 않는 태도.

숲은 나무보다 똑똑하다. 단, 나무들이 서로 다르게 자랐을 때만.

참고 문헌: Breiman, L. (2001). "Random Forests." Machine Learning 45(1). / Efron, B. (1979). "Bootstrap Methods: Another Look at the Jackknife." Annals of Statistics 7(1). / Hastie, T., Tibshirani, R. & Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed., Ch. 15.