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

빠르다는 것은 부지런하다는 뜻이 아니다

랜덤 포레스트가 나무 500그루를 3초 만에 키우는 법

빠른 프로그램을 만드는 방법은 놀랍도록 적다. 사실상 세 가지뿐이다.

같은 일을 두 번 하지 않는 것. 정확할 필요가 없는 곳을 알아보는 것. 그리고 기계가 사람처럼 계산하지 않는다는 사실을 잊지 않는 것.

랜덤 포레스트는 나무 수백 그루를 심는 알고리즘이다. 나무 한 그루마다 수천 번의 질문을 만들고, 질문 하나를 고를 때마다 수많은 후보를 저울질한다. 순진하게 짜면 학습이 며칠씩 걸린다. 그런데 실제로는 3초에 끝난다.

그 3초 안에 위의 세 가지 태도가 열한 번 발휘된다. 이 글은 그 열한 번의 이야기다. 계산은 하지 않겠다. 대신 매번 무슨 생각을 한 것인지만 이야기하겠다.

1부. 같은 일을 두 번 하지 않는다

옮겨간 사람만 세면 된다

결혼식 피로연에서 신랑 측과 신부 측 테이블에 하객이 나눠 앉아 있다. 양쪽 축의금 합계를 이미 알고 있다. 그때 한 명이 자리를 옮긴다.

두 테이블을 처음부터 다시 세는 사람은 없다. 그 사람이 낸 금액만 한쪽에서 빼고 다른 쪽에 더한다. 너무 당연해서 말할 가치도 없어 보인다.

그런데 결정 트리가 하는 일이 정확히 이것이다. 나무는 데이터를 크기순으로 세워놓고 칼날을 한 칸씩 옮기면서, 어느 지점에서 자르는 게 가장 깔끔한지 본다. 칼날을 옮길 때마다 양쪽 덩어리가 얼마나 고르게 모였는지 재야 하는데, 재려면 양쪽의 합계가 필요하다.

여기서 순진한 구현은 칼날을 옮길 때마다 양쪽을 처음부터 다시 더한다. 하객 한 명이 자리를 옮겼는데 하객 전체를 다시 세는 것이다. 데이터가 백만 개라면 이 낭비가 백만 번 쌓인다.

반면 옮겨간 값 하나만 더하고 빼면, 칼날을 아무리 여러 번 옮겨도 비용은 데이터를 한 번 훑는 정도로 끝난다. 이 차이 하나가 며칠과 몇 초를 가른다. 결정 트리를 실험실 밖으로 꺼낸 것이 이 아이디어이고, 이름은 증분 갱신 이다.

이 발상은 알고리즘 바깥에서도 흔히 보인다. 매달 재고를 전수 조사하는 창고와 입출고만 기록하는 창고의 차이, 회의록을 매번 새로 쓰는 팀과 변경분만 적는 팀의 차이가 같은 이야기다.

줄을 세우면 답이 저절로 드러난다

"나이 몇 살에서 자를까?"라는 질문에는 무한한 답이 있다. 44.1살일 수도, 44.9살일 수도 있다.

그런데 사람들을 나이순으로 줄 세워보면 이상한 일이 벌어진다. 줄에서 이웃한 두 사람 사이라면, 어디를 자르든 결과가 완전히 똑같다. 그 사이에는 아무도 없기 때문이다. 44.1로 자르나 44.9로 자르나 왼쪽에 서는 사람과 오른쪽에 서는 사람이 동일하다.

그러면 진짜로 다른 결과를 내는 자리는 사람과 사람 사이의 틈뿐이다. 사람이 열 명이면 틈은 아홉 개. 무한했던 후보가 갑자기 손에 꼽힌다.

정렬이 하는 일은 데이터를 예쁘게 정리하는 게 아니라, 무한한 선택지를 유한하게 만드는 것이다. 순서를 한 번 알아내면 그 뒤의 모든 질문이 쉬워진다.

여기에 재미있는 함정이 하나 딸려 있다. 가장 널리 쓰이는 정렬법인 퀵소트는 이미 정렬된 데이터를 만나면 오히려 최악으로 느려진다. 그런데 결정 트리에서는 부모가 정렬해둔 데이터를 자식이 그대로 물려받으니, 이미 정렬된 입력이 계속 들어온다. 최악의 경우가 예외가 아니라 일상인 것이다. 그래서 실무 구현은 상황이 나빠지는 낌새가 보이면 다른 정렬법으로 갈아타는 하이브리드를 쓴다. 도구의 약점이 내 상황과 정확히 겹칠 때 무슨 일이 벌어지는지에 대한 좋은 사례다.

찌그러진 룰렛은 미리 펴둔다

제비뽑기를 하는데 사람마다 당첨 확률이 다르다고 하자. 어떤 사람은 크게, 어떤 사람은 아주 작게. 원판에 그리면 파이 조각들이 제각각인 룰렛이 된다.

이런 룰렛은 돌릴 때마다 바늘이 어느 구간에 떨어졌는지 더듬어 찾아야 한다. 한 번은 괜찮다. 그런데 수억 번 돌려야 한다면 그 더듬는 비용이 전부 쌓인다.

여기서 발상을 뒤집는다. 룰렛을 매번 더듬는 대신, 처음에 딱 한 번 고생해서 조각들을 똑같은 크기의 칸에 재배치해두면 어떨까. 큰 조각을 잘라서 작은 칸의 빈자리를 메우는 식으로 정리하면, 놀랍게도 각 칸에 최대 두 사람의 지분만 담기게 만들 수 있다.

그러고 나면 뽑기가 이렇게 바뀐다. 칸 하나를 균등하게 고르고, 그 칸 안에서 동전을 한 번 던진다. 끝이다. 더듬을 게 없다. 준비에 한 번 든 비용은 수억 번의 뽑기에 나눠지며 사라진다.

랜덤 포레스트가 이런 뽑기를 쓰는 이유는 데이터가 늘 공평하지 않기 때문이다. 사기 거래 탐지처럼 찾으려는 것이 천 건에 한 건뿐이라면, 그 한 건을 천 건처럼 취급해야 모델이 배운다. 그러면 뽑힐 확률이 제각각인 상태로 데이터를 뽑아야 하고, 그때 이 기법이 쓰인다. 이름은 Alias method 다.

한 번의 전처리로 무한한 반복을 싸게 만드는 것. 색인을 만드는 일, 지도를 미리 그려두는 일이 전부 같은 종류의 투자다.

흩어놓지 말고 붙여놓는다

CPU 옆에는 아주 작고 아주 빠른 메모리가 붙어 있다. 책상 위와 창고의 관계라고 보면 된다. 책상 위 자료는 손만 뻗으면 되지만, 창고에 있으면 걸어갔다 와야 한다. 그 왕복이 생각보다 훨씬 비싸다.

그리고 이 책상에는 한 가지 습관이 있다. 창고에 갈 때 필요한 것 하나만 들고 오지 않고, 그 옆에 붙어 있던 것들까지 한 아름 안고 온다. 옆에 있는 건 곧 필요할 거라고 짐작하는 것이다.

교과서대로 트리를 만들면 노드가 하나씩 따로 생겨나 메모리 여기저기 흩어진다. 그러면 노드를 하나 읽을 때마다 창고까지 걸어가야 하고, 같이 안고 온 이웃들은 아무 상관 없는 남의 데이터라 그냥 버려진다. 도서관에서 책 열 권을 찾는데 전부 다른 층 다른 서가에 꽂혀 있는 상황이다.

그래서 실무 구현은 나무를 한 줄로 눕혀 배열에 차곡차곡 담는다. 자식이 어디 있는지는 주소 대신 배열의 몇 번째인지로 가리킨다. 그러면 부모를 읽을 때 자식들이 딸려 들어온다. 계산 내용은 한 글자도 안 바꿨는데 예측 속도가 몇 배 빨라진다.

무엇을 계산하느냐만큼이나 그것을 어디에 두느냐가 중요하다. 자주 같이 쓰는 것을 가까이 두는 일은 부엌 정리에서든 창고 배치에서든 통하는 원리다.

2부. 정확할 필요가 없는 곳을 알아본다

완벽한 스무고개는 존재하지만 찾을 수 없다

결정 트리는 스무고개다. 그렇다면 가능한 모든 질문 순서를 따져보고 제일 좋은 걸 고르면 될 것 같다.

안 된다. 첫 질문 후보가 수만 가지이고, 그걸 고르면 갈라진 양쪽에서 또 수만 가지, 다시 그 아래에서 또 수만 가지다. 깊이가 한 층 늘 때마다 경우의 수가 제곱으로 부풀어서, 몇 층만 내려가도 우주에 있는 원자를 전부 계산기로 써도 못 끝내는 크기가 된다. 최적의 결정 트리를 찾는 일은 이론적으로 감당 불가능한 문제 로 분류되어 있다.

그래서 결정 트리는 일찌감치 포기한다. 앞을 보지 않는다. 지금 이 자리에서 가장 좋아 보이는 질문 하나를 고르고, 뒤돌아보지 않고 계속 간다. 안개 속에서 정상이 안 보이니 발밑에서 가장 가파른 방향으로만 걷는 등산가다. 이 방식을 탐욕적 분할 이라 한다.

당연히 진짜 정상이 아니라 근처 언덕에 멈추곤 한다. 나무 한 그루만 놓고 보면 명백한 결함이다.

그런데 여기서 이 글에서 가장 근사한 반전이 나온다. 앞을 안 보는 등산가는 출발점이 조금만 달라져도 완전히 다른 언덕에 도착한다. 데이터가 조금만 바뀌어도 첫 질문부터 달라지고, 그러면 그 아래 나무 전체가 딴판이 된다. 불안정하다는 뜻이다.

그리고 랜덤 포레스트가 나무를 500그루나 심는 이유가 바로 그 불안정성이다. 나무들이 서로 다르게 틀려야 평균이 힘을 발휘한다. 모두가 같은 방식으로 틀리면 몇 그루를 심든 소용없다.

완벽을 포기했더니, 포기한 것보다 나은 것이 돌아왔다. 이 글의 나머지도 대체로 이런 이야기다.

34.7세와 34.8세를 구분해야 하는가

앞에서 데이터를 줄 세우면 후보가 유한해진다고 했다. 그래도 데이터가 아주 많으면 줄 세우는 일 자체가 부담이다. 나무 500그루가 각각 수천 개의 노드에서 이 짓을 반복하기 때문이다.

여기서 질문을 던져볼 만하다. 우리는 정말로 34.7세와 34.8세를 구분해야 하는가?

거의 언제나 답은 아니오다. 그렇다면 나이를 미리 몇백 개의 서랍에 나눠 담아두자. 이제 자를 수 있는 곳은 서랍과 서랍 사이뿐이다. 후보가 백만 개에서 몇백 개로 줄어든다. 게다가 서랍에 담는 일은 시작할 때 한 번만 하면 되고, 나무 500그루가 같은 서랍을 함께 쓴다.

물론 잃는 게 있다. 서랍 폭 때문에 가장 좋은 자리를 미세하게 놓친다. 그런데 이 손실이 왜 문제가 안 될까?

여기서 앞 장의 반전이 다시 작동한다. 우리는 나무를 500그루 심고 있고, 각 나무가 조금씩 다르게 틀리기를 오히려 바라고 있다. 미세한 부정확은 다양성의 다른 이름이다. 정밀도를 조금 내주고 속도를 크게 받는 거래이며, 여럿을 모으는 구조는 이 거래에서 손해 보지 않는다. 대용량 데이터를 다루는 요즘 알고리즘들이 하나같이 이 방식을 택한 이유다. 이름은 비닝 이다.

전부 보지 않고도 모양은 알 수 있다

서랍을 쓰기로 했다. 그럼 서랍 경계를 어디에 그을까.

가장 단순한 답은 최솟값과 최댓값 사이를 똑같은 폭으로 나누는 것이다. 연봉 데이터에 이걸 적용하면 왜 나쁜지 바로 보인다. 어딘가에 소득이 압도적으로 높은 한 사람이 있으면, 그 사람 때문에 서랍 폭이 터무니없이 넓어지고 나머지 거의 전부가 첫 서랍에 몰린다. 서랍이 수백 개인 줄 알았는데 실제로는 하나다. 나무는 아무것도 배우지 못한다.

옳은 방법은 각 서랍에 들어가는 사람 수 가 비슷해지도록 경계를 긋는 것이다. 그런데 그러려면 누가 몇 번째로 소득이 높은지 알아야 하고, 그건 다시 줄 세우기다. 줄 세우기를 피하려고 서랍을 만들었는데 서랍을 만들려고 줄을 세워야 하는, 뱀이 제 꼬리를 무는 상황이 된다.

이 매듭을 푸는 방법이 근사다. 데이터를 딱 한 번만 훑으면서, 전부 기억하는 대신 순위의 뼈대만 붙잡아둔다. 뼈대가 너무 많아지면 가까운 것끼리 합쳐서 개수를 유지한다. 그렇게 하면 아주 적은 메모리로도 "이쯤이 중간이고 이쯤이 상위 10%다"를 충분히 정확하게 말할 수 있다.

여론조사와 같은 발상이다. 5천만 명 전부에게 묻지 않아도 지지율의 모양은 알 수 있다. 다만 여론조사는 표본의 운에 기대고, 이 알고리즘들은 오차가 얼마 이내라는 것을 수학적으로 보장한다는 점이 다르다. 이런 기법을 근사 분위수 알고리즘 이라 부른다.

3부. 기계는 사람처럼 계산하지 않는다

큰 수를 만들면 작은 차이를 잃는다

컴퓨터가 다룰 수 있는 숫자의 자릿수는 정해져 있다. 그리고 그 자릿수는 맨 앞자리부터 센다. 이 사실에서 사람의 직관과 어긋나는 성질이 하나 나온다.

수가 커질수록 소수점 아래의 정밀도를 잃는다. 작은 수를 다룰 때는 소수점 아래로 한참 정확하던 것이, 수가 커지면 그만큼 뒤가 잘려나간다.

이게 왜 문제가 되는가. 나무가 분할을 채점할 때는 데이터가 얼마나 흩어져 있는지를 재야 한다. 흩어짐을 구하는 공식은 여러 가지인데, 그중 하나가 계산하기에 특히 편리하다. 값들을 제곱해서 다 더한 큰 수를 하나 만들고, 거기서 또 다른 큰 수를 빼는 방식이다. 앞에서 본 증분 갱신과 궁합도 완벽하다.

그런데 이 방법은 거의 같은 두 거대한 수를 빼서 아주 작은 답을 얻어내려는 짓 이다. 63빌딩 두 채의 높이를 각각 재고, 그 차이로 사람 키를 알아내려는 셈이다. 줄자가 아무리 정밀해도 답이 나오지 않는다. 큰 수를 만드는 순간 우리가 원하는 작은 답은 이미 반올림 속에 잠겼기 때문이다.

결과는 조용하고 치명적이다. 흩어짐의 크기는 원래 음수가 될 수 없는 값인데, 음수가 나온다. 그러면 그 뒤의 계산이 전부 의미를 잃고, 분할의 좋고 나쁨을 가리는 판단이 무너진다. 그런데 에러 메시지는 뜨지 않는다. 프로그램은 잘 돌아가고 나무만 이상한 모양으로 자란다. 정확도가 좀 나쁠 뿐이다. 세상에서 가장 찾기 어려운 종류의 고장이다.

해법은 60여 년 전에 나왔고, 발상은 단순하다. 애초에 큰 수를 만들지 않는 것. 데이터를 하나씩 받으면서 평균을 조금씩 옮기고, 새 값과 그 평균의 차이만 누적한다. 다루는 수가 계속 작으니 잃을 정밀도도 없다. 63빌딩을 재는 대신 처음부터 줄자로 사람을 재는 것이다.

여기서 배울 것은 한 문장으로 줄어든다. 수학적으로 같은 두 식이 컴퓨터에서는 전혀 다른 물건이다. 수치해석이라는 학문 전체가 사실상 이 문장의 각주다.

경계 위에 서지 마라

컴퓨터가 소수를 다루는 방식에는 또 하나의 성질이 있다. 사람이 십진법으로 쓰는 간단한 소수 중에 컴퓨터의 이진법에서는 딱 떨어지지 않는 것들이 있다. 우리가 3분의 1을 0.333…으로밖에 못 쓰는 것과 같다. 그래서 컴퓨터의 소수에는 늘 아주 미세한 티끌이 묻어 있다.

평소엔 아무 문제가 없다. 그런데 경계선 위에 정확히 서 있는 값 을 다룰 때 사고가 난다.

나무가 "나이 45 이하는 왼쪽"이라는 기준을 세웠다고 하자. 학습할 때 45살이던 사람은 왼쪽으로 갔다. 그런데 예측할 때 그 사람의 나이가 조금 다른 경로로 계산되어 티끌만큼 45를 넘으면, 오른쪽으로 간다. 같은 사람이 같은 모델에서 다른 답을 받는다.

방어책은 허무할 만큼 간단하다. 경계선을 데이터가 있는 자리가 아니라 데이터와 데이터 사이의 한가운데에 긋는다. 45와 52 사이에 아무도 없다면 굳이 45에 그을 이유가 없다. 가운데인 48.5쯤에 그으면 어느 쪽 데이터에서도 멀찍이 떨어져 있어서, 티끌 정도로는 절대 넘어오지 못한다.

앞에서 줄을 세우면 "틈"이 후보로 드러난다고 했는데, 그 틈의 한가운데를 쓰는 이유가 이것이다. 이런 걸 신경 쓰지 않으면, 같은 데이터로 만든 모델이 돌릴 때마다 미묘하게 다른 답을 낸다.

가짜 무작위가 오히려 축복인 이유

랜덤 포레스트의 '랜덤'은 두 군데서 쓰인다. 나무마다 데이터를 무작위로 뽑을 때, 그리고 질문을 만들 때 후보를 무작위로 추릴 때.

그런데 컴퓨터는 진짜 무작위를 만들 수 없다. 정해진 명령만 따르는 기계니까. 그래서 출발 숫자를 하나 정하고, 거기에 정해진 규칙을 반복 적용해 무작위처럼 보이는 수열을 만들어낸다. 가짜 무작위다.

가짜라는 게 결함처럼 들리지만 실은 축복이다. 같은 출발 숫자를 넣으면 같은 숲이 자란다. 남이 내 결과를 그대로 재현할 수 있고, 어제 모델과 오늘 모델이 다르면 그건 운 탓이 아니라 코드나 데이터가 바뀐 탓이라고 확신할 수 있다. 재현되지 않는 것은 고칠 수도 없다.

그런데 여기 이 글에서 가장 무서운 함정이 숨어 있다.

나무 500그루는 여러 코어가 동시에 나눠서 키운다. 이때 코어들이 무작위 수열 하나를 나눠 쓰면, 순서가 얽혀 서로 비슷한 조각을 받을 수 있다. 그러면 나무 A와 나무 B가 비슷한 데이터를 뽑고 비슷한 질문을 고른다. 즉, 나무들이 서로 닮아진다.

앞선 글에서 확인한 사실이 여기서 되살아난다. 여럿을 모아 얻는 이득은 그들이 서로 다를 때만 생긴다. 나무들이 서로 닮은 만큼의 오차는 나무를 백만 그루로 늘려도 지워지지 않는다. 평균으로 지울 수 있는 건 제각각인 부분뿐이기 때문이다.

그러니 무작위 수열을 잘못 나눠 쓰면, 통계학이 약속했던 성능이 그만큼 깎여나간다. 코드는 잘 돌고 에러도 없다. 그냥 정확도가 이유 없이 낮을 뿐이다. 그래서 제대로 만든 구현은 시작 전에 나무마다 독립적인 출발 숫자를 미리 나눠준다.

구현의 사소한 부주의가 이론의 전제 자체를 무너뜨릴 수 있다. 이 글에서 하나만 가져가야 한다면 이 문장이다.

돌아올 길을 적어두는 메모장

나무를 키우는 코드는 자연스럽게 이런 모양이 된다. "이 노드를 둘로 나눈다. 그리고 왼쪽 자식에 대해 방금 한 일을 그대로 다시 한다. 오른쪽 자식도." 자기가 자기를 부르는 방식이고, 이걸 재귀라 한다. 세 줄이면 나무 전체가 자란다.

문제는 컴퓨터가 이 호출을 관리하는 방식이다. 어떤 일을 하다가 다른 일로 들어가면, 컴퓨터는 "여기까지 하다 왔다"를 메모장에 적어둔다. 나중에 돌아와야 하니까. 파고들수록 메모장에 줄이 쌓인다. 그리고 이 메모장은 크기가 정해져 있다. 넘치면 프로그램이 그냥 죽는다.

나무가 그렇게까지 깊어질 일이 있을까. 좌우로 균형 있게 자란다면 없다. 절반씩 나누면 금방 끝에 닿는다. 그런데 매번 아주 조금씩만 떼어내는 식으로 쪼개지면, 나무는 가지를 치지 못하고 사슬처럼 한 방향으로만 길어진다. 데이터에 순번 성격의 값이 섞여 있으면 실제로 벌어지는 일이다. 몇 시간 학습한 결과와 함께 프로그램이 사라진다.

해법은 재귀를 손으로 굴리는 것 이다. 함수가 자기를 부르게 두지 말고, "아직 처리 못 한 노드" 목록을 직접 들고 다닌다. 목록에서 하나 꺼내 나누고, 생긴 자식 둘을 목록에 넣고, 목록이 빌 때까지 반복한다. 컴퓨터의 메모장을 쓰지 않으니 깊이 제한이 사라진다.

그리고 예상 못 한 선물이 따라온다. 목록에서 어느 것을 먼저 꺼낼지 내가 정할 수 있게 된다.

• 마지막에 넣은 것부터 꺼내면 한 방향으로 끝까지 파고들며 자란다.
• 먼저 넣은 것부터 꺼내면 층별로 고르게 자란다.
• 가장 개선이 클 것 같은 것부터 꺼내면, 자원을 손실이 큰 쪽에 집중한다.

마지막 방식이 요즘 빠른 알고리즘들이 택하는 성장 전략이다. 재귀의 우아함을 포기했더니 알고리즘의 전략을 바꿀 손잡이가 생겼다. 여기서도 같은 이야기다. 무언가를 내려놓았더니 내려놓은 것보다 큰 것이 돌아왔다.

다시, 세 가지 태도

이 열한 가지는 통계학 교과서에 나오지 않는다. 논문에도 대개 생략된다. 그런데 이것들이 없으면 랜덤 포레스트는 칠판 위의 아이디어로 남았을 것이다.

한 가지 흐름이 이 글을 관통한다. 최적의 나무를 포기했더니 여럿을 모으는 데 필요한 다양성을 얻었고, 정밀한 경계를 포기했더니 속도를 얻었고, 전수 조사를 포기했더니 규모를 얻었고, 재귀의 우아함을 포기했더니 전략의 자유를 얻었다.

빠르다는 것은 더 부지런히 계산한다는 뜻이 아니다. 무엇을 하지 않아도 되는지 정확히 안다는 뜻이다.

그러니 이 글을 덮고 나서 당신의 일을 볼 때 던져볼 질문도 세 개다. 나는 지금 방금 한 일을 다시 하고 있지 않은가. 정확할 필요가 없는 곳에 힘을 쓰고 있지 않은가. 내가 쓰는 도구의 성질을 모른 채 쓰고 있지 않은가.

세 번째 질문이 가장 조용하고, 가장 비싸다.