엔트로피, 정보획득과 분류트리

개인적으로 진행하고 있는 연구 활동에서, 두 종류의 카테고리의 데이터들이 분포하여 있을 때, 이들을 구분할 수 있는 최적의 구분선을 긋는 방법을 고민하고 있다. 처음의 분산 등의 개념에서 착안한, 비용함수적인 접근을 사용하는 시도들은 대칭적인 데이터, 두 카테고리의 데이터 개수가 동일한 경우 정도에만 그럭저럭 동작했기 때문에, 결과적으로 아이디어를 찾기 위해 구글링을 좀 하다가 머신러닝에서의 의사결정나무(Decision Tree) 알고리즘 부분에서 정보과학 분야에 해당하는 정보 엔트로피(Entropy)와 정보획득(Information Gain)에 관한 내용을 찾았기에, 이를 나만의 형태로 알고리즘화하기 전에 여기에 내가 이해한 방식대로 적어두려고 한다.

필자는 아직 고등학생에 불과하므로, 대학생 위주로 맞추어져 있는 설명들을 이해하기 힘들어 한참 고생을 했다. 각종 블로그와 Youtube 동영상 강의를 참조하였는데, 그럭저럭 이해한지는 모르겠지만 일단은 여기에 살펴보거나 참조한 그 페이지 목록을 적어 본다.

1. 의사결정나무(Decision Tree) – ratsgo’s blog
2. 정보이론과 엔트로피 – Bool님의 Tistory 블로그 Untitled
3.#4.0. 정보량을 나타내는 엔트로피 (Entropy) – Terry TaeWoong Um님의 Youtube 강의
4. 정보 엔트로피 (동영상) | 현대 정보 이론 – Khan Academy Labs

미리 경고하지만, 필자는 전공자가 아니고, 단순히 취미나 연구 활동을 위하여 찾아본 결과를 여기에 기록해두는 것이다. 이 기록은 정확한 것이 아닐 가능성이 꽤 있으니, 보다 정확하게 공부하기 위해서는 다른 글들을 참고하기 바란다.

엔트로피(Entropy)

정보량

우선 엔트로피를 설명하기 전에 있어 정보량이란 무엇인지부터 적어두는 것이 나을 것 같다. 정보량은 해당 정보를 기술하기 위하여 필요한 최소의 bit 수라 할 수 있겠다.

예를 들어보자, Khan Academy의 강의 초반에 등장했던 예시인데, 대충 이렇다. A, B, C, D 네 종류의 문자를 랜덤으로 출력하는 두 기계가 있다고 하자. 단, 두 기계는 각 문자를 다음과 같은 확률에 따라 출력한다.

• 기계 1: A 25%, B 25%, C 25%, D 25%
• 기계 2: A 50%, B 25%, C 12.5%, D 12.5%

이 때, 기계가 임의의 한 개의 문자를 출력했을 때, 이 기계가 출력한 문자가 무엇인지 알기 위하여 우리는 최소한 예/아니오의 질문을 몇 번을 해야 하는가를 생각해보자.

보통 예/아니오 질문을 통해 가능한 빨리 정보를 뽑으려면, 한 번의 질문을 통해 가능한 많은 경우를 제끼는 것이 나을 것이다. 따라서, 한 번의 질문을 할 때 그 질문에 대해 ‘예’일 확률과 ‘아니오’일 확률이 각각 50%인 것이 가장 효율적일 것임은 자명하다.

기계 1의 경우를 생각해보자. 모든 문자의 출력 확률이 동일하므로, 맨 처음에 ‘그 문자가 A 또는 B인가요?’라고 묻는다면 예일 확률과 아니오일 확률이 각각 50%로 가장 효율적인 질문이 될 것이다. 그 대답에 예일 경우는 ‘그 문자가 A인가요?’라고 묻는다면 역시 조건부 확률에서 A일 확률과 B일 확률이 각각 50%로서, 또한 효율적이고, 아니오일 경우에도 ‘그 문자가 C인가요?’라고 묻는다면 역시 조건부 확률에서 C일 확률과 D일 확률
이 각각 50%로서 효율적인 질문이 된다.

즉, 기계 1의 경우에서는 출력된 문자가 무엇인지 알아보기 위해서는, A, B, C, D 모든 경우에 대하여 질문을 2번만 하면 알 수가 있다. 이를 컴퓨터가 표현하기 위해서는, 질문에 대한 답이 예라면 1로, 아니오라면 0으로 저장한다고 할 때, 1번째 질문에 대한 답과 2번째 질문에 대한 답을 저장하면 충분하므로, 단지 2개의 bit만 있어도 충분할 것이다. 즉, 문자가 A인 경우는 위의 질문 방식에서는 11, B인 경우는 10, C인 경우는 01, D인 경우는 00 이런 식으로 기술할 수 있는 것이다. 이 때 우리는 A를 기술하기 위해 필요한 정보량은 2, B를 기술하기위해 필요한 정보량은 2, … 이런 식으로 말할 수 있다.

기계 2의 경우를 생각해보자. 이번에는 문자가 출력될 확률이 꽤 다르다. 따라서, 효율적인 질문 방식을 구성하는 절차도 기계 1의 경우와는 다를 것이다. 예 / 아니오에 대한 각각의 확률을 50%로 맞추는 것이 효율적이니, 기계 2에서 출력된 문자가 무엇인지 알기 위해서는 가장 먼저 ‘그 문자가 A인가요?’라고 묻는 것이 가장 효율적일 것이다. A일 확률이 50%, A가 아닐 확률(B or C or D일 확률)이 50%이기 때문이다. 만약 대답이 ‘아니오’라면, 두 번째 질문으로는 ‘그 문자가 B인가요?’라고 묻는 것이 가장 효율적일 것이다. 조건부 확률에서 B일
확률이 50%, B가 아닐 확률(C or D일 확률)이 50%이기 때문이다. 마찬가지로, 이에 대한 대답도 ‘아니오’라면, ‘그 문자가 C인가요?’라고 물으면 된다.

고로, 기계 2의 경우에는 문자에 따라 해야 되는 최소한의 질문의 개수가 다르게 된다. A인지 알아보기 위해서는 단 1개의 질문이, B인지 알아보기 위해서는 단 2개의 질문이면 충분하지만, C, D인지 알아보기 위해서는 질문을 3개 던져야 한다. 마찬가지로, 이를 컴퓨터가 표현하기 위해서는, A의 경우는 1이라고 첫번째 질문에 대한답만 표시해도 충분하며, B의 경우는 11이라고 두 개의 질문에 대한 답을 표시해야 할 것이고, C의 경우는 111, D의 경우는 110이라고 세 개의 질문에 대한 답을 표시해야 할 것이다. 따라서 A를 기술하기 위해 필요한 정보량은 1, B의 경우는 2, C, D의 경우는 3이라고 할 수 있을 것이다.

즉, 정보량은 이런 식의, 어떤 확률 분포를 가지고 나타나는 데이터들 각각에 대해 이들을 기술하는데 필요한 bit 수를 의미한다고 할 수 있겠다.

그렇다면 이를 수식적으로 어떻게 정의할 수 있을까? 분명한 것은 어떤 데이터를 기술하기 위한 정보량은, 그 데이터가 나타날 확률과 관련이 있다는 것이다. 기계 1의 경우는 C가 나타날 확률이 25%, 즉 1/4이라 그 정보량은 2였으나, 기계 2의 경우는 C가 나타날 확률이 12.5%, 즉 1/8이라 그 정보량은 3이었던 점을 기억하자. 뭐가 좀 보이는가?

컴퓨터는 2진법을 사용하여 정보를 기술한다. 어떤 데이터가 나타날 확률이 작을 수록, 그 데이터를 기술하기 위하여 해야 할 질문의 수가 많아지므로 데이터에 대한 정보량은 증가한다. 어떤 데이터 $i$가 나타날 확률이 $P_{i}$인 경우, 그 정보량은 일반적으로 다음과 같은 수식으로 기술될 수 있다.

$I_{i} = -log_{2}(P_{i})$

위 수식은 위의 우리의 논의 결과와 일치한다. 기계 2의 A가 나올 확률은 1/2였는데, 이에 대입하면 A의 정보량은 정확히 1이며, C가 나올 확률 1/8을 대입하면 C의 정보량은 3이다. 물론, 이러한 수식은 1/3 등의 확률에 대해서는 자연수가 아닌 값을 출력하는데, 컴퓨터의 비트 수는 일반적으로 자연수이다. 이 점에 대해서는, 그냥 일반적인 경우에 대해 모두 정의하기 위해 정보량을 실수 범주 모두에 대응시켰다고 생각하는 것이 나을 것 같다.

이 블로그에서는 대략적인 이해만을 위하여 이 글을 쓰고 있으니, 자세한 유도 과정이나 증명 등은 생략한다. 구글링하면 꽤 복잡하게 나오는데, 솔직하게 필자도 아직 이해한 것은 아니라 기술하지 않는 것도 있다.

엔트로피(Entropy)

엔트로피란 어떤 집합을 정보의 형태로 기술하기 위하여 필요할 것으로 예상되는 평균적인 bit 수라고 할 수 있겠다. 우선, 엔트로피의 수식적 정의는 다음과 같다. 어찌 보면 그 집합에 대한 정보량의 기댓값이라 할 수도 있겠다.

$Entropy = – \sum_{k=1}^m p_{k}log_{2}(p_{k})$

이해를 돕기 위해 아까 들었던 예제를 생각해보도록 하겠다. 기계 1에 의해 나오는 결과 집합의 엔트로피를 계산해보자.

기계 1에는 A, B, C, D의 네 종류의 데이터(이들을 보통 레코드라고 칭한다)가 있으며, 그들의 등장 확률은 모두 각각 25%, 1/4로 동일하다. 위의 공식에 넣어 계산해보면, 당연히 기계 1에 의한 결과 집합에 대한 Entropy는 2가 된다.

기계 2의 경우도 생각해보자. 기계 2에도 A, B, C, D의 네 종류의 레코드가 있었으나, 그들의 등장 확률은 각각50%(=1/2), 25%(=1/4), 12.5%(=1/8), 12.5%(=1/8)로 달랐다. 위의 공식에 넣어 계산해보면, 기계 2에 의한 결과 집합에 대한 Entropy는 1.75가 되겠다.

이 엔트로피라는 개념은 좀 색다른 표현이 있다. 마치, 자연과학의 ‘엔트로피’가 무질서의 척도이듯, 정보과학에서도 ‘엔트로피’는 무질서의 척도이다.

보다 정확히 말하자면 엔트로피는 불순도(impurity) 혹은 불확실성(uncertainty)의 척도이다. 무슨 말인지 예시 그림을 보며 설명하겠다.

왼쪽, 오른쪽 영역에서 우리가 임의로 단 한 개의 칸을 선택한다고 생각해보자. 이런 상황은 어떤 확률 분포를 가진 데이터 집합 상에서 어떤 레코드를 기술하는 상황이라는 점에서 앞에서 논의했던 ‘기계’ 상황과 결국 같은 상황이다. 왼쪽 그림 (a)의 경우를 먼저 생각해보면, 모두 검은색으로만 가득 차 있기 때문에, 레코드는 검은색 딱 1개이고, 그 등장 확률은 1이며, 엔트로피를 계산해보면 0이다. 반면 오른쪽 그림 (b)의 경우는, 검은색과 흰색이 섞여 있는데, 검은색은 19개, 흰색은 17개가 있으니 레코드는 흰색과 검은색의 2종류가 있고, 그 등장 확률은 각각 17/36, 19/36이며, 엔트로피는 계산해보면 0.998 정도이다.

무언가 깨달았는가? 어떤 데이터 집합에 대한 엔트로피는 그 데이터 집합이 얼마나 어지럽혀져 있는지, 얼마나 무질서한지를 나타내주는 척도인 셈이다. 혹은, 그 데이터 집합에서 한 레코드가 다른 레코드와 얼마나 많이 섞여 있는지, 즉 불순수한지를 보여주는 척도(불순도)이며, 그 데이터 집합에서 임의로 한 개의 데이터를 선택했을 때 이 데이터가 어떤 종류인지 예측하기 보다 더 힘들다(불확정성)는 것이다.

이러한 엔트로피의 성질은 필자가 연구 중인 ‘영역 구분의 문제’에 유용하게 사용될 수 있다. 머신러닝의 알고리즘 중에는 의사결정트리라는 알고리즘이 있는데, 이 의사결정트리 문제 중 분류 트리의 경우는 어떤 데이터 영역들이 주어졌을 때, 이들을 적절히 두 영역으로 구분하는 과정을 반복해서 두 영역을 잘 나누게 하는 과정으로 이루어져 있다. 이러한 과정은 필연적으로 그은 구분선이 얼마나 영역을 잘 나누었는가를 평가하는 단계를 포함하게 되는데, 이 때 우리의 엔트로피가 사용되는 것이다.

정보획득

분류 트리는 일반적으로 구분 뒤에 구분된 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하는 방향으로 학습을 진행한다고들 말한다. 어떤 데이터 영역의 순도가 증가, 즉 불확실성이 감소하는 것을 정보 이론에서는 정보획득(information gain)이라고 한다.

정보획득의 양은 어떤 행위 이전의 엔트로피에서 행위 이후의 엔트로피를 뺀 값(엔트로피의 변화량)으로 정의할 수 있다. 이를 분류 트리의 과정을 통해 보다 자세히 설명하겠다.

그림과 같이, 주황색 선으로 둘러싸인 어떤 영역 A가 있다고 하자. 영역 A에는 적색, 청색의 2개의 레코드가 있으며, 적색은 10개, 청색은 6개로 총 16개의 데이터가 있다고 하자. 이 때 영역 A의 엔트로피를 계산해보면, 대략 0.95 정도가 나온다.

만약 그림의 붉은 점선과 같은 구분선을 그어 영역을 위쪽 영역 R1, 아래쪽 영역 R2로 구분하였다면, 전체 영역 A에 대한 엔트로피는 정의에 비추어볼 때, 각각의 영역의 비율을 고려하여 계산한 정보량의 기댓값이 될 것이다. 따라서 분할 전의 데이터들 가운데 분할 후, i 영역에 속하는 데이터들의 비율을 Ri라고 할 때, 구분선을 그은 후의 전체 영역 A의 엔트로피는 다음과 같이 계산할 수 있을 것이다.

$Entropy(A) = \sum_{i=1}^d R_i (- \sum_{k=1}^m p_k log_2 (p_k ))$

이에 따라 구분선을 그은 후의 전체 영역 A에 대한 엔트로피를 계산하면 약 0.75가 된다. 이는 영역 A를 나눔으로서 보다 같은 종류의 데이터들이 잘 모이게 되었음을 의미한다. 즉, 0.95-0.75=0.2만큼의 엔트로피가 감소함으로서(=불확실성 감소=순도 증가=정보획득) 이 구분선을 그은 것이 구분선을 긋지 않은 경우보다 훨씬 영역을 잘 나누었다고 판단할 수 있는 것이다.

끝으로

이렇게 해서 일단 필자가 알고 있는 대로 엔트로피, 정보량, 정보획득 등에 관하여 대충 정리한 듯 하다. 다시 한번 강조하지만, 위 내용은 필자가 이해한 내용에 불과하며, 전공생이 아닌 필자의 특성 상 부정확할 가능성이 상당히 있으니, 만약 머신러닝이나 정보과학 기술의 학습을 목적으로 한다면 이 글이 아닌 다른 전문가들이 쓴 글들을 읽기를 권장한다.

글에 질문이나 의견이 있다면 댓글로 남겨주기 바라며, 긴 글을 읽어주신 여러분들께 감사드린다.