이번 글에서는 전사함수(全射函數;surjection)와 단사함수(單射函數;injection)를 선형대수학의 선형변환 관점에서 살펴보도록 하겠습니다. 이번 글 역시 고려대 박성빈 교수님 강의를 참고로 했습니다. 그러면 시작하겠습니다.

선형변환과 표준행렬

$V$와 $W$를 벡터공간이라고 하고, 벡터공간 $V$의 원소 $A$, $B$와 실수 $k$에 대하여 아래 두 가지 성질을 모두 만족할 때 $T$를 $V$에서 $W$로의 선형변환(linear transformation)이라고 합니다.

$T(A+B) = T(A) + T(B)$

$T(kA) = kT(A)$, 즉 $k=0$일 때 $T(0)=0$

여기서 모든 선형변환은 행렬 곱의 형태로 나타낼 수 있는데요, 임의의 선형변환 $T$가 $n$차원 벡터공간에서 $m$차원으로 사상(mapping)한다고 할 때 선형변환 $T$는 위 정의에 의해 아래와 같이 다시 쓸 수 있습니다.

[\begin{align} x&=\begin{bmatrix} { x }_{ 1 } \ { x }_{ 2 } \ … \ { x }_{ n } \end{bmatrix}={ x }_{ 1 }\begin{bmatrix} 1 \ 0 \ … \ 0 \end{bmatrix}+{ x }_{ 2 }\begin{bmatrix} 0 \ 1 \ … \ 0 \end{bmatrix}+…+{ x }_{ n }\begin{bmatrix} 0 \ 0 \ … \ 1 \end{bmatrix}\ &={ x }_{ 1 }{ e }_{ 1 }+{ x }_{ 2 }{ e }_{ 2 }+…+{ x }_{ n }{ e }_{ n }

T(x)&={ x }_{ 1 }T({ e }_{ 1 })+{ x }_{ 2 }T({ e }_{ 2 })+…+{ x }_{ n }T({ e }_{ n })\ &=\begin{bmatrix} T({ e }_{ 1 }) & T({ e }_{ 2 }) & … & T({ e }_{ n }) \end{bmatrix}\begin{bmatrix} { x }_{ 1 } \ { x }_{ 2 } \ … \ { x }_{ n } \end{bmatrix}\ &=Ax \end{align}]

위 식에서 행렬 $A$를 선형변환 $T$를 나타내는 표준행렬(standard matrix)이라 부르고, $T$는 $A$에 의해서 표현된 선형변환이라고 부릅니다.

$T$에 대응하는 표준행렬은 유일합니다. 증명해보겠습니다. 만약 표준행렬이 $A$, $B$ 이렇게 두 개 있다고 가정해 보겠습니다. 선형변환 T에 임의의 기본벡터 $e_i$를 넣으면 아래와 같은 식이 됩니다.

[T({ e }{ i })=A{ e }{ i }=B{ e }_{ i }]

여기에서 $Ae_i$는 행렬 $A$의 $i$번째 열벡터와 같고, $Be_i$는 행렬 $B$의 $i$번째 열벡터입니다. 위 식이 성립한다는 건 행렬 $A$, $B$의 열이 서로 같다는 의미이기 때문에 $A$와 $B$는 동일한 행렬이라 말할 수 있습니다. 따라서 $T$에 대응하는 표준행렬은 유일합니다.

전사함수

수학에서 전사함수 또는 위로의 함수(onto)는 공역(codomain)과 치역(range)이 일치하는 함수입니다. $n$차원 벡터공간의 벡터 $x$를 $m$차원 벡터공간의 벡터 $b$로 사상하는 선형변환 $T$를 $Ax=b$라고 둡시다.

전사함수는 $b$에 대응하는 $x$가 적어도 하나 존재하는 경우를 말합니다. 이를 그림으로 설명하면 아래와 같습니다.

위 그림의 왼쪽은 전사함수가 아닌 경우를 말합니다. 정육면체가 $m$차원 공간이라고 상상해 봅시다. 선형변환 $T$는 정의역(domain)에 있는 원소들을 정육면체를 둘로 가르는 하늘색 평면에 옮기고 있는 모습을 확인할 수 있습니다. 여기에서 $m$차원 벡터 $b$가 정육면체 안에 있으나 하늘색 평면 바깥에 존재한다고 가정해봅시다. 이 경우 $b$에 대응하는 $x$는 존재하지 않는다는 사실 또한 알 수 있습니다. (공역>치역)

반대로 오른쪽 그림의 경우 어떤 $b$를 상정하더라도 그에 대응하는 $x$가 존재합니다. 이게 바로 전사함수입니다. (공역=치역)

단사함수

그럼 단사함수 또는 일대일(one-to-one) 함수를 살펴볼까요? 전사함수 설명 때와 동일하게, $n$차원 벡터공간의 벡터 $x$를 $m$차원 벡터공간의 벡터 $b$로 사상하는 선형변환 $T$를 $Ax=b$라고 둡시다.

단사함수란 $b$에 대응하는 $x$가 최대 한 개 존재하는 경우를 일컫습니다. 이를 그림으로 도시하면 아래와 같습니다.

위 그림의 왼쪽은 단사함수가 아닌 경우를 말합니다. $m$차원 벡터 $b$에 대응하는 $n$차원 벡터 $x$가 여러개이기 때문입니다. 반대로 오른쪽 그림의 경우 $b$에 대응하는 $x$는 단 하나 존재합니다. 이 경우 단사함수라고 부릅니다.

전단사와 선형 연립방정식 (1)

4차원 벡터공간에서 3차원 공간으로 사상하는 선형변환 $T$에 대응하는 표준행렬 $A$는 다음과 같다고 둡시다.

[A=\begin{bmatrix} 1 & -4 & 8 & 1 \ 0 & 2 & -1 & 3 \ 0 & 0 & 0 & 5 \end{bmatrix}]

우선 $T$가 전사함수인지를 살펴보겠습니다. 정의역(4차원) 벡터를 $x$, 공역(3차원) 벡터를 $b$라고 두면 $T$는 아래와 같이 쓸 수 있습니다.

[Ax=b]

$T$가 전사함수인가 아닌가라는 질문은 임의의 $b$에 대해 해가 적어도 하나 존재하는가라는 질문과 동일합니다. 이 문제를 풀기 위해 선형 연립방정식 관련 네 가지 명제를 소개합니다. 이들은 하나가 참이면 모두 참이고, 하나가 거짓이면 모두 거짓인 동치(equivalent) 관계입니다. 자세한 내용은 이곳을 참고하시기 바랍니다.

(1) $Ax=b$가 해를 갖는다.

(2) $b$는 계수행렬 $A$의 열벡터 간 선형결합으로 표시된다.

(3) 계수행렬 $A$의 열벡터는 $m$차원 벡터공간을 생성(span)한다.

(4) $A$는 모든 행에 pivot positon을 하나 가진다.

표준행렬 $A$는 가우스행렬(echelon form) 형태입니다. $A$의 행 개수는 3개인데, pivot position(선도 원소가 영이 아닌 행) 또한 3개(요소값 기준 : 1,2,5)이므로 위 네 가지 동치명제에 의해 해가 존재함을 알 수 있습니다. 따라서 $T$는 전사함수입니다.

$T$가 단사함수인지 가려볼까요? A의 세번째 열($[8,-1,0]^T$)은 추축열(pivot column;pivot position에 대응하는 열)이 아니군요. $A$를 선형 연립방정식의 계수행렬로 상정해 본다면 이 열에 대응하는 $x_3$은 어떤 값을 가지든 상관없는 자유변수(free variable)입니다. 바꿔 말하면 $b$에 대응하는 $x$가 유일하지 않다는 이야기입니다. 따라서 $T$는 단사함수가 아닙니다.

전단사와 선형 연립방정식 (2)

$n$차원 벡터를 $m$차원 벡터로 사상하는 임의의 선형변환 $T$에 관해 세 가지 정리를 하고 넘어가겠습니다.

(a) 표준행렬 $A$의 열벡터가 $m$차원 벡터공간을 생성(span)할 때 $T$는 전사함수이다.

(b) $T(x)$가 단사함수이면 $T(x)=0$은 자명해($x=0$)를 유일해로 갖는다. 그 역도 성립한다.

(c) 표준행렬 $A$의 열벡터가 서로 선형독립일 때 $T$는 단사함수이다. 그 역도 성립한다.

우선 (a)를 살펴보겠습니다. $T$를 $Ax=b$ 꼴로 둘 때 $b$는 $A$의 열벡터와 $x$의 선형결합인데요. $A$의 열벡터가 생성하는 벡터집합이 $m$차원 벡터공간을 모두 채우고 있다면(=$A$의 열벡터가 $m$차원 공간을 생성) $x$가 어떤 값을 갖더라도 $Ax=b$가 성립합니다. 다시 말해 임의의 $b$에 대응하는 $x$가 적어도 하나 존재합니다.

(b)와 관련해 $T$는 선형성(linearity) 조건을 만족하기 때문에 $T(0)=0$입니다. $T(x)$가 단사함수라면 $Ax=b$ 형식에서 단 하나의 해만 존재해야 합니다. 따라서 $T(x)$가 단사함수라면 $T(x)=0$은 자명해($x=0$)를 유일한 해로 갖습니다.

한편 $T$가 단사함수가 아니어서 임의의 $b$에 대응하는 $x$가 서로 다른 벡터 $u$, $v$가 존재한다고 가정해 봅시다. 즉, $T(u)=b, T(v)=b$가 성립한다는 이야기입니다. $T$는 선형성 조건을 만족하므로 $T(u-v)=T(u)-T(v)=b-b=0$입니다. 그런데 $u-v≠0$이므로 $T(x)=0$은 하나 이상의 비자명해를 갖습니다. 이 말은 $T(x)=0$이 자명해를 유일해로 갖는다면 $T(x)$가 단사함수이라는 명제와 동치입니다.

이번엔 (c)를 보겠습니다. $A$의 열벡터가 선형독립이라는 얘기는 $T$를 $Ax=b$ 꼴의 연립방정식으로 생각할 때 해가 영벡터뿐이라는 얘기와 같습니다. 따라서 (c)는 명제 (b)에 의해 참입니다.

이제 예를 들어보겠습니다. 선형변환 $T$가 아래와 같습니다.

[T({ x }{ 1 },{ x }{ 2 })=(3{ x }{ 1 }+{ x }{ 2 },5{ x }{ 1 }+7{ x }{ 2 },{ x }{ 1 }+3{ x }{ 2 })\ T(x)=\begin{bmatrix} 3{ x }{ 1 }+{ x }{ 2 } \ 5{ x }{ 1 }+7{ x }{ 2 } \ { x }{ 1 }+3{ x }{ 2 } \end{bmatrix}=\begin{bmatrix} 3 & 1 \ 5 & 7 \ 1 & 3 \end{bmatrix}\begin{bmatrix} { x }{ 1 } \ { x }{ 2 } \end{bmatrix}=Ax]

우선 단사함수 여부를 가려보겠습니다. 표준행렬 $A$의 열벡터는 임의의 스칼라곱을 해서 비교해도 같아지지 않으므로 서로 선형독립임을 알 수 있습니다. (c)에 의해 $T$는 단사함수입니다.

하지만 $A$의 행 개수는 세 개 인데 열 개수는 두 개뿐이므로 모든 행에 pivot position이 있는 건 아닙니다. 전챕터 (1)~(4) 정리에 의해 $A$의 열벡터는 3차원 공간을 생성할 수 없습니다. $T$는 전사함수가 아닙니다.

이 문제를 가우스소거법에 의한 연립방정식($Ax=b$) 풀이로도 접근해서 풀어보겠습니다. 확대행렬(augmented matrix)로 나타내 기본행 연산을 한 결과는 아래와 같습니다.

[\begin{bmatrix} 3 & 1 & { b }{ 1 } \ 5 & 7 & { b }{ 2 } \ 1 & 3 & { b }{ 3 } \end{bmatrix} \sim \begin{bmatrix} 1 & 3 & { b }{ 3 } \ 0 & -8 & { b }{ 2 }-5{ b }{ 3 } \ 0 & 0 & { b }{ 1 }-{ b }{ 2 }+2{ b }_{ 3 } \end{bmatrix}]

$b_1-b_2+2b_3=0$이면 해가 있지만, 0이 아니면 해가 존재하지 않습니다. 따라서 전사함수가 아닙니다. $T$를 그림으로 나타내면 아래와 같습니다.

위 그림을 보시면 $T$에 의해 2차원 평면이 3차원으로 사상(mapping)되는 걸 확인할 수 있습니다. 변환 후 3차원 공간 전체를 채우지 못하는 것 또한 볼 수 있는데요, 여기서도 역시 우리는 이 변환이 전사함수가 아님을 알 수 있습니다. 다만 이렇게 그림으로 이해할 수 있는 건 3차원까지이고요, 그보다 높은 차원의 선형변환 $T$가 전사, 단사임을 확인하려면 지금까지 말씀드렸던 정리와 절차에 대해 확인하는 과정을 거쳐야 합니다.

마치며

지금까지 전사함수와 단사함수를 선형대수학의 선형변환 관점에서 살펴보았습니다. 임의의 선형변환이 전사이면서 단사함수이려면 사상 전후의 차원이 같아야 합니다(2차원=>2차원, 3차원=>3차원).

그런데 사상 후 차원이 커질 경우 단사함수 조건을 만족하지만 전사함수이진 않습니다. 바꿔 말해 일대일 대응 성질은 만족하지만 치역이 공역보다 작다는 이야기입니다.

반대로 차원을 줄일 경우 전사함수이지만 단사함수는 아닙니다. 공역을 빠짐없이 채우게 돼 치역과 일치하지만, 그에 대응하는 정의역 벡터 $x$가 여러 개가 될 수 있기 때문입니다.

이를 상식적으로 이해해보면 큰 공간을 작은 공간으로 줄일 때 빽빽해지고, 작은 공간을 큰 공간으로 늘릴 때 듬성듬성해진다고 이해하셔도 좋을 것 같다는 생각입니다.

선형변환은 선형 연립방정식의 해를 찾는 과정과 본질적으로 다르지 않기 때문에 선형대수학이라는 학문이 하나의 체계를 이루는 것 같다는 느낌도 듭니다. 질문이나 의견 있으시면 이메일이나 댓글로 알려주시면 감사하겠습니다. 여기까지 읽어주셔서 진심으로 감사드립니다.

이번 포스팅에서는 최근 인기를 끌고 있는 단어 임베딩(embedding) 방법론인 Word2Vec에 대해 살펴보고자 합니다. Word2Vec은 말 그대로 단어를 벡터로 바꿔주는 알고리즘입니다. Neural Network Language Model(NNLM)을 계승하면서도 학습 속도와 성능을 비약적으로 끌어올려 주목을 받고 있습니다. 이번 포스팅은 Word2Vec의 기본 내용은 이미 알고 있다고 전제하고 학습 과정을 중심으로 설명하려고 하는데요, 일반적인 내용을 보시려면 이곳을, Word2Vec을 활용한 어플리케이션 사례를 보시려면 이곳을, Word2Vec의 전신 격인 NNLM을 보시려면 이곳을 참고하시면 좋을 것 같습니다. 이번 글은 고려대 강필성 교수님 강의와 이곳을 참고했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

word2vec 학습 파라메터

Word2Vec의 아키텍처(skip-gram)를 도시하면 아래 그림과 같습니다. 은닉층이 하나인 간단한 뉴럴네트워크 구조입니다.

위 구조에서 핵심은 가중치행렬 $W$, $W’$ 두 개입니다. Word2Vec의 학습결과가 이 두 개의 행렬이거든요. 그림을 자세히 보시면 입력층-은닉층, 은닉층-출력층을 잇는 가중치 행렬의 모양이 서로 전치(transpose)한 것과 동일한 것을 볼 수 있습니다. 그런데 전치하면 그 모양이 같다고 해서 완벽히 동일한 행렬은 아니라는 점에 주의할 필요가 있습니다(저는 이것 때문에 엄청 헷갈렸어요). 물론 두 행렬을 하나의 행렬로 취급(tied)하는 방식으로 학습을 진행할 수 있고, 학습이 아주 잘되면 $W$와 $W’$ 가운데 어떤 걸 단어벡터로 쓰든 관계가 없다고 합니다.

그럼 입력층과 은닉층을 잇는 가중치행렬 $W$을 좀 더 자세히 살펴보겠습니다. 위 그림과 아래 그림을 비교하면서 보시면 좋을 것 같은데요, $V$는 임베딩하려는 단어의 수, $N$은 은닉층의 노드 개수(사용자 지정)입니다. Word2Vec은 최초 입력으로 one-hot-vector를 받는데요, $1×V$ 크기의 one-hot-vector의 각 요소와 은닉층의 $N$개 각 노드는 1대1 대응이 이뤄져야 하므로 가중치행렬 $W$의 크기는 $V×N$이 됩니다. 예컨대 학습 말뭉치에 단어가 1만개 있고 은닉층 노드를 300개로 지정했다고 칩시다. 그럼 가중치행렬 $W$는 좌측 하단의 오렌지색 행렬 형태가 됩니다.

Word2Vec 아키텍처는 중심단어로 주변단어를 맞추거나, 주변단어로 중심단어를 더 잘 맞추기 위해 가중치행렬인 $W$, $W’$을 조금씩 업데이트하면서 학습이 이뤄지는 구조입니다. 그런데 여기서 흥미로운 점은 $W$가 one-hot-encoding된 입력벡터와 은닉층을 이어주는 가중치행렬임과 동시에 Word2Vec의 최종 결과물인 임베딩 단어벡터의 모음이기도 하다는 사실입니다.

아래와 같이 단어가 5개뿐인 말뭉치에서 Word2Vec을 수행한다고 가정해 봅시다. 사전 등장 순서 기준으로 네번째 단어를 입력으로 하는 은닉층 값은 아래처럼 계산됩니다. 보시다시피 Word2Vec의 은닉층을 계산하는 작업은 사실상 가중치행렬 $W$에서 해당 단어에 해당하는 행벡터를 참조(lookup)해 오는 방식과 똑같습니다.

학습이 마무리되면 이 $W$의 행벡터들이 각 단어에 해당하는 임베딩 단어벡터가 됩니다.

Word2Vec 입력과 Skip-Gram

Word2Vec의 Skip-Gram(중심단어로 주변단어 예측)이 말뭉치로부터 어떻게 입력값과 정답을 만들어내는지 살펴보겠습니다. ‘The quick brown fox jumps over the lazy dog.’ 문장으로 시작하는 학습말뭉치가 있다고 칩시다. 윈도우(한번에 학습할 단어 개수) 크기가 2인 경우 아키텍처가 받는 입력과 정답은 아래와 같습니다.

자, 그럼 학습의 첫번째 스텝(첫째줄)을 볼까요? 중심단어는 처음 등장하는 단어인 ‘The’입니다. 윈도우 크기가 2이기 때문에 중심단어 앞뒤로 두개씩 봐야 하지만, ‘The’를 기준으로 이전 단어가 존재하지 않으므로 어쩔 수 없이 중심단어 뒤에 등장하는 두 개 단어(quick, brown)만 학습에 써야겠네요.

그런데 여기서 주의할 것은 학습할 때 ‘quick’과 ‘brown’을 따로 떼어서 각각 학습한다는 점입니다. 부연하자면 중심단어에 ‘The’를 넣고 ‘quick’을 주변단어 정답으로 두어서 한번 학습하고, 또 다시 ‘The’를 중심단어로 하고 ‘brown’을 주변단어로 해서 한번 더 학습한다는 얘기입니다.

이렇게 첫번째 스텝이 끝나면 중심단어를 오른쪽으로 한칸 옮겨 ‘quick’을 중심단어로 하고, ‘The’, ‘brown’, ‘fox’를 각각 주변단어 정답으로 두는 두번째 스텝을 진행하게 됩니다. 이런 식으로 말뭉치 내에 존재하는 모든 단어를 윈도우 크기로 슬라이딩해가며 학습을 하면 iteration 1회가 마무리됩니다.

주변단어로 중심단어를 예측하는 CBOW에 비해 Skip-gram의 성능이 좋은 이유가 바로 여기에 있습니다. 언뜻 생각하기에는 주변의 네 개 단어(윈도우=2인 경우)를 가지고 중심단어를 맞추는 것이 성능이 좋아보일 수 있습니다. 그러나 CBOW의 경우 중심단어(벡터)는 단 한번의 업데이트 기회만 갖습니다.

반면 윈도우 크기가 2인 Skip-gram의 경우 중심단어는 업데이트 기회를 4번이나 확보할 수 있습니다. 말뭉치 크기가 동일하더라도 학습량이 네 배 차이난다는 이야기이죠. 이 때문에 요즘은 Word2Vec을 수행할 때 Skip-gram으로 대동단결하는 분위기입니다.

Word2Vec의 학습

Word2Vec의 Skip-gram은 아래 식을 최대화하는 방향으로 학습을 진행합니다. 아래 식 좌변은 중심단어(c)가 주어졌을 때 주변단어(o)가 나타날 확률이라는 뜻입니다. 식을 최대화하려면 우변의 분자는 키우고 분모는 줄여야 합니다.

우선 우변의 $v$는 입력층-은닉층을 잇는 가중치 행렬 $W$의 행벡터, $u$는 은닉층-출력층을 잇는 가중치 행렬 $W’$의 열벡터입니다.

우변 분자의 지수를 키우는 건 중심단어(c)에 해당하는 벡터와 주변단어(o)에 해당하는 벡터의 내적값을 높인다는 뜻입니다. 벡터 내적은 코사인이므로 내적값 상향은 단어벡터 간 유사도를 높인다는 의미로 이해하면 될 것 같습니다.

분모는 줄일 수록 좋은데요, 그 의미는 윈도우 크기 내에 등장하지 않는 단어들은 중심단어와의 유사도를 감소시킨다는 정도로 이해하면 될 것 같습니다.

아래는 Word2Vec의 학습파라메터인 중심단어 벡터 업데이트 과정을 수식으로 정리한건데요, 저도 정리 용도로 남겨 두는 것이니 수식이 골치 아프신 분들은 스킵하셔도 무방할 것 같습니다. 중심단어 벡터의 그래디언트는 아래와 같습니다.

[\begin{align} \frac { \partial }{ \partial { v }_{ c } } \ln { P(o|c) } &=\frac { \partial }{ \partial { v }_{ c } } \ln { \frac { exp({ u }_{ o }^{ T }{ v }_{ c }) }{ \sum _{ w=1 }^{ W }{ exp({ u }_{ w }^{ T }{ v }_{ c }) } } } \ &=\frac { \partial }{ \partial { v }_{ c } } { u }_{ o }^{ T }{ v }_{ c }-\frac { \partial }{ \partial { v }_{ c } } \ln { \sum _{ w=1 }^{ W }{ exp({ u }_{ w }^{ T }{ v }_{ c }) } } \ &={ u }_{ o }^{ T }-\frac { 1 }{ \sum _{ w=1 }^{ W }{ exp({ u }_{ w }^{ T }{ v }_{ c }) } } (\sum _{ w=1 }^{ W }{ exp({ u }_{ w }^{ T }{ v }_{ c }) } \cdot { u }_{ w })\ &={ u }_{ o }^{ T }-\sum _{ w=1 }^{ W }{ \frac { exp({ u }_{ w }^{ T }{ v }_{ c }) }{ \sum _{ w=1 }^{ W }{ exp({ u }_{ w }^{ T }{ v }_{ c }) } } } \cdot { u }_{ w }\ &={ u }_{ o }^{ T }-\sum _{ w=1 }^{ W }{ P(w|c)\cdot } { u }_{ w } \end{align}]

이렇게 구한 중심단어 그래디언트의 반대 방향으로 조금씩 중심단어 벡터를 업데이트합니다. (여기서 알파는 사용자가 지정하는 학습률=learning rate)

Word2Vec의 학습 트릭

subsampling frequent words

Word2Vec의 파라메터는 앞서 설명드린대로 $W$, $W’$입니다. 각각 크기가 $V$ x $N$, $N$ x $V$인데요. 보통 말뭉치에 등장하는 단어수가 10만개 안팎이라는 점을 고려하면 $N$(임베딩 차원수, 사용자 지정)이 100차원만 되어도 2000만개(2 x 10만 x 100)나 되는 많은 숫자들을 구해야 합니다. 단어 수가 늘어날 수록 계산량이 폭증하는 구조입니다.

이 때문에 Word2Vec 연구진은 말뭉치에서 자주 등장하는 단어는 학습량을 확률적인 방식으로 줄이기로 했습니다. 등장빈도만큼 업데이트 될 기회가 많기 때문입니다.

Word2Vec 연구진은 i번째 단어($w_i$)를 학습에서 제외시키기 위한 확률은 아래와 같이 정의했습니다.

[P({ w }{ i })=1-\sqrt { \frac { t }{ f({ w }{ i }) } }]

위 식에서 $f(w_i)$는 해당 단어가 말뭉치에 등장한 비율(해당 단어 빈도/전체 단어수)를 말합니다. $t$는 사용자가 지정해주는 값인데요, 연구팀에선 0.00001을 권하고 있습니다.

만일 $f(w_i)$가 0.01로 나타나는 빈도 높은 단어(예컨대 조사 ‘은/는’)는 위 식으로 계산한 $P(w_i)$가 0.9684나 되어서 100번의 학습 기회 가운데 96번 정도는 학습에서 제외하게 됩니다. 반대로 등장 비율이 적어 $P(w_i)$가 0에 가깝다면 해당 단어가 나올 때마다 빼놓지 않고 학습을 시키는 구조입니다. subsampling은 학습량을 효과적으로 줄여 계산량을 감소시키는 전략입니다.

negative sampling

Word2Vec은 출력층이 내놓는 스코어값에 소프트맥스 함수를 적용해 확률값으로 변환한 후 이를 정답과 비교해 역전파(backpropagation)하는 구조입니다.

그런데 소프트맥스를 적용하려면 분모에 해당하는 값, 즉 중심단어와 나머지 모든 단어의 내적을 한 뒤, 이를 다시 exp를 취해줘야 합니다. 보통 전체 단어가 10만개 안팎으로 주어지니까 계산량이 어마어마해지죠.

이 때문에 소프트맥스 확률을 구할 때 전체 단어를 대상으로 구하지 않고, 일부 단어만 뽑아서 계산을 하게 되는데요. 이것이 바로 negative sampling입니다. negative sampling은 학습 자체를 아예 스킵하는 subsampling이랑은 다르다는 점에 유의하셔야 합니다.

negative sampling의 절차는 이렇습니다. 사용자가 지정한 윈도우 사이즈 내에 등장하지 않는 단어(negative sample)를 5~20개 정도 뽑습니다. 이를 정답단어와 합쳐 전체 단어처럼 소프트맥스 확률을 구하는 것입니다. 바꿔 말하면 윈도우 사이즈가 5일 경우 최대 25개 단어를 대상으로만 소프트맥스 확률을 계산하고, 파라메터 업데이트도 25개 대상으로만 이뤄진다는 이야기입니다.

윈도우 내에 등장하지 않은 어떤 단어($w_i$)가 negative sample로 뽑힐 확률은 아래처럼 정의됩니다. $f(w_i)$는 subsampling 챕터에서 설명한 정의와 동일합니다.

[P({ w }{ i })=\frac { { f({ w }{ i }) }^{ { 3 }/{ 4 } } }{ \sum { j=0 }^{ n }{ { f({ w }{ j }) }^{ { 3 }/{ 4 } } } }]

참고로 subsampling과 negative sampling에 쓰는 확률값들은 고정된 값이기 때문에 학습을 시작할 때 미리 구해놓게 됩니다.

Word2Vec 학습 시각화

아래는 Word2Vec 학습 과정을 예쁘게 시각화한 사이트입니다. 이곳에 방문하시면 단어벡터의 업데이트 과정을 실시간으로 눈으로 확인하실 수 있습니다.

마치며

이상으로 Word2Vec의 학습 과정을 전반적으로 살펴보았습니다. Word2Vec은 중심단어와 주변단어 벡터의 내적이 코사인 유사도가 되도록 단어벡터를 벡터공간에 임베딩합니다. 학습 말뭉치를 만드는 방식이나 subsampling, negative sampling 등의 기법을 통해 성능은 끌어올리고 계산복잡성은 낮추었습니다. 은닉층이 하나인 뉴럴네트워크 구조이나 하이퍼볼릭탄젠트, 시그모이드 등 비선형 활성함수를 사용하지 않아서 사실상 선형모델인 점도 눈여겨볼 점인 것 같습니다. 성능과 계산복잡성 두 마리 토끼를 모두 잡는 데 성공했기 때문에 요즘 들어 많은 관심을 받고 있다고 생각합니다. 의견이나 질문 있으시면 언제든지 이메일이나 댓글로 알려주시기 바랍니다. 여기까지 읽어주셔서 진심으로 감사드립니다.

이번 포스팅에선 단어의 분산표상(distributed representation) 방식 가운데 하나인 Neural Probabilistic Language Model(NPLM)에 대해 살펴보도록 하겠습니다. NPLM은 Bengio(2003)에서 제안된 모델인데요, 단어를 벡터로 바꾸는 뉴럴네트워크 기반 방법론으로 주목을 받았습니다. 이번 글은 고려대 강필성 교수님 강의와 네이버랩스 박은정 박사의 발표원고를 바탕으로 정리했음을 먼저 밝힙니다. 자 그럼 시작해볼까요?

Distributed representation

컴퓨터에게 단어를 가르쳐 주려면 어떻게 해야 할까요? 참으로 어려운 문제이지요. 컴퓨터는 그저 사칙연산 수행을 잘 하는 계산기일 뿐이니까요. 단어를 숫자로 바꿔서 입력해야 컴퓨터는 그제야 연산을 수행할 수 있습니다. 대표적인 방법론이 바로 one-hot-encoding입니다. ‘코끼리’, ‘사자’, ‘뱀’ 세 개 단어로 이뤄진 사전이 있다고 쳐보겠습니다. 이걸 one-hot-vector로 표현(representation)하면 아래와 같습니다.

코끼리 : [1, 0, 0]

사자 : [0, 1, 0]

뱀 : [0, 0, 1]

one-hot-vector는 가장 간단하고 직관적인 표현법입니다. 어떤 단어가 해당하는 요소만 1이고 나머지는 0으로 채워 넣으면 끝입니다. 그런데 사전에 등재된 단어 수가 100개, 1000개 이렇게 늘어난다면 어떻게 될까요? 각각의 단어 벡터들은 100차원, 1000차원을 갖게 될 겁니다. 실제 대다수 자연어들은 단어 수가 10만개 안팎이기 때문에 한 언어의 모든 단어들을 one-hot-vector로 바꾸면 그 차원수가 어마어마하게 클 겁니다. 이런 큰 차원의 벡터는 제 아무리 뛰어난 성능을 가진 컴퓨터라도 메모리 등 문제 때문에 계산복잡성이 크게 늘어나게 되겠죠. 게다가 이 벡터들은 딱 하나의 요소만 1이고 나머지는 모두 0인 sparse vector 형태를 갖습니다.

one-hot-vector의 단점은 또 있습니다. 바로 두 단어의 내적(inner product)이 0입니다. 위 예시에서 코끼리라는 단어 벡터([1, 0, 0])와 사자 벡터([0, 1, 0])를 내적하면 0이 된다는 사실을 알 수 있습니다. 길이가 1인 두 벡터의 내적은 두 벡터 사이의 각도(cosine)가 되므로 내적값이 0이라는 말은 두 벡터가 직교(orthogonal)한다는 의미인데요, 이를 확장해서 생각해보면 모든 one-hot-vector는 서로 독립(independent)이라는 사실 또한 추론해낼 수 있습니다. 하지만 현실에서는 단어들끼리 관련성이 전혀 없는 건 아닙니다. 유의어, 반의어 같이 단어들은 다른 단어들과 의미적으로 특정한 관계를 맺고 있거든요. 이러한 문제를 해결하기 위해 등장한 개념이 바로 분산표상(distributed representations)이라고 보시면 될 것 같습니다.

분산표상이 추구하는 바는 위 식과 같습니다. W는 단어벡터를 의미하는데요, one-hot-vector의 차원수는 사전의 전체 단어수(V)입니다. 이를 V보다 훨씬 작은 n차원 벡터로 바꿔보자는 것입니다. one-hot-vector는 그 요소가 0 혹은 1인 binary 구조이지만, 분산표상으로 표현된 단어벡터의 요소는 연속형의 실수값입니다. 듬성듬성한(sparse) 벡터를 빽빽한(dense) 벡터로 바꿔 표현한 것이라고 이해해도 좋을 것 같습니다. 뭔가 알 수 있을듯 없을듯 하지요? 분산표상을 그림으로 이해해보겠습니다.

왼쪽 그림을 보시면 총 9개 개체가 있습니다. 이를 one-hot-vector로 표현한다면 9차원짜리 벡터 9개가 나올 겁니다. 그런데 자세히 보면 9개 그림은 2개의 속성, 즉 색상(color)과 모양(shape)으로 설명할 수가 있겠네요. 즉 녹색이면서 해 모양이라면 첫번째 개체라는 걸 특정할 수가 있습니다. 그렇다면 9개 개체는 [색상, 모양]이라는 2차원짜리 벡터로도 충분히 표현할 수가 있습니다. 이것이 바로 분산표상 개념입니다.

분산표상은 데이터의 차원수를 줄이려는 것이 1차적 목적이지만, 그 효과는 실로 대단합니다. 위 예시처럼 색상이나 모양 기준으로 개체간 유사성을 잴 수 있듯이, 단어 벡터도 그 요소값이 연속적이기 때문에 단어 벡터 간에 거리나 유사도를 잴 수가 있게 됩니다. 의미가 유사한 단어는 벡터공간에서 가깝게, 반대의 경우는 멀게 배치하는 것이 분산표상의 목표입니다. 바로 아래 그림처럼요.

Neural Probabilistic Language Model 개요

NPLM은 단어들의 연쇄가 주어졌을 때 다음 단어가 무엇인지 맞추는 과정에서 분산표상된 단어벡터들을 만드는 방법론입니다. 뭔가 알쏭달쏭하죠? 한번 예를 들어 보겠습니다.

발 없는 말이 천리 __

위와 같이 ‘발’, ‘없는’, ‘말이’, ‘천리’ 네 개 단어가 주어졌다고 합시다. 그 다음에 올 단어는 무엇일까요? 수많은 동사가 올 수 있겠지만 ‘간다’라는 단어가 등장할 확률이 높을 겁니다. 우리는 ‘발 없는 말이 천리 간다’는 속담을 자주 쓰는 편이니까요. 이를 수식으로 쓰면 아래와 같습니다.

NPLM은 위 식의 조건부확률을 최대화하는 방향으로 학습을 하게 됩니다. 즉, $P(간다$|$발,없는,말이,천리)$를 높이고 싶은거죠. 바꿔 말하면 ‘발’, ‘없는’, ‘말이’, ‘천리’ 네 개 단어로 ‘간다’를 맞추자는 겁니다. 이처럼 NNLM은 직전까지 등장한 $n-1$개 단어들로 $n$번째 단어를 맞추는 N-gram 모델이 그 본질입니다.

NPLM의 입출력

다음 값을 최대화하려면 우변의 분자는 키우고 분모는 줄여야할 겁니다.

$y_{w_t}$는 $w_t$라는 단어에 해당하는 점수 벡터입니다. 그 크기는 말뭉치 전체의 단어수($V$)에 해당하는 차원을 가졌습다. 만약 $V$가 3이라면 $y_{w_t}$는 $[1.2, 3.4, 2.1]$ 이런 식의 벡터가 됩니다.

NNLM 구조 말단의 출력은 $V$차원의 스코어 벡터 $y_{w_t}$에 소프트맥스 함수를 적용한 $V$차원의 확률 벡터입니다. NNLM은 확률값이 가장 높은 요소의 인덱스에 해당하는 단어가 실제 정답 단어와 일치하도록 학습을 진행하게 됩니다.

요컨대 정답 인덱스에 해당하는 스코어(분자)를 높이고, 나머지 인덱스에 해당하는 스코어(분모)는 낮춰야 위 식에 정의된 조건부확률을 높일 수 있습니다.

모델의 출력을 알아봤으니 이번엔 입력벡터 $x_t$를 만드는 과정을 살펴보겠습니다. 다음 식과 같습니다.

[{ x }{ t }=C\cdot { w }{ t }]

우선 $m$ x |$V$| 크기를 갖는 커다란 매트릭스를 우선 만듭니다. $m$은 $x_t$의 차원수로, $C$의 모든 요소 값은 초기에 랜덤 설정합니다. $w_t$는 $t$번째 단어에 대한 One-hot-Vector입니다. $t$번째 요소만 1이고 나머지는 0인 벡터이죠. $C$와 $w_t$의 내적은 $C$라는 행렬에서 $t$번째 열만 참조(lookup)하는 것과 본질적으로 같습니다.

NPLM의 구조

이번엔 NPLM 구조를 전체적으로 살펴보겠습니다.

입력부터 천천히 살펴보겠습니다. 처음 말씀드렸던 것처럼 우리는 ‘발’, ‘없는’, ‘말이’, ‘천리’ 이렇게 네 개 단어가 주어졌을 때 ‘간다’라는 단어를 예측하고 싶은 겁니다. 우선 네 개의 각각의 단어에 해당하는 인덱스값을 불러옵니다. 이 인덱스에 해당하는 $C$ 행렬의 열벡터를 불러옵니다. 이렇게 네 개 단어에 해당하는 열벡터를 $C$에서 참조해 묶어주면 $x_t$가 됩니다.

입력층(Input Layer)에서 은닉층(Hidden Layer)을 거쳐 출력층(Output Layer)으로 보내는 연산은 다음과 같습니다. 우선 $x_t$와 $H$를 내적한 뒤 bias term ‘d’를 더해 은닉층을 만듭니다. 여기에 $U$를 내적한 뒤 bias term $b$를 더해주면 스코어벡터 $y_{w_t}$가 나오게 됩니다.

[{ y }{ { w }{ t } }=b+U\cdot tanh(d+H{ x }_{ t })]

마지막으로 $y_{w_t}$에 소프트맥스 함수를 적용한 뒤 이를 정답 단어인 ‘간다’의 인덱스와 비교해 역전파(backpropagation)하는 방식으로 학습이 이루어지게 됩니다.

NPLM의 학습 parameter

NPLM의 parameter 차원수는 아래와 같습니다.

$x_t$는 모델이 예측해야 하는 마지막 단어를 제외한 $n-1$개의 $m$차원 단어 벡터들입니다. 여기에 입력층에서 은닉층으로 보내주는 가중치 매트릭스 $H$를 곱하면 은닉층은 사용자가 지정하는 $h$차원 벡터가 됩니다. 여기에 같은 차원의 bias 벡터 $d$를 더해주고, 이후 은닉층에서 출력층으로 보내주는 가중치 매트릭스 $U$를 내적한 뒤 bias 벡터 $b$를 더해주면 말뭉치 단어 개수인 $V$차원의 스코어 벡터가 생성되는 구조입니다.

마치며

NPLM의 최종 목적은 단어벡터들의 모음이기도 한 $C$를 얻어내는 데 있습니다. 직전 $n-1$개 단어들이 주어졌을 때 마지막 $n$번째 단어를 맞추는 데 최적화된 단어벡터들의 모음이 바로 단어를 분산표상으로 임베딩한 결과물이라는 것이죠. 다만 NPLM은 C외에 H, U, b, d 등 다른 파라메터들도 업데이트해야 하기 때문에 계산복잡성이 높습니다. 이러한 문제점을 극복하기 위해 학습파라메터를 확 줄이는 방향으로 제안된 모델이 바로 최근 각광받고 있는 Word2Vec입니다.

이번 포스팅에선 단어 가중치 할당 방법론인 TF-IDF에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 참고했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

TF, IDF

TF(Term Frequency)는 어떤 단어가 특정 문서에 얼마나 많이 쓰였는지 빈도를 나타냅니다. 많이 쓰인 단어가 중요하다는 가정을 전제로 한 수치입니다. 예컨대 A라는 단어가 doc1에서 10번, doc3에서 5번 쓰였다면 doc1-단어A의 TF는 10, doc3-단어A의 TF는 5가 됩니다. DF(Document Frequency)란 특정 단어가 문서에 등장한 횟수를 뜻하는데요, 만약 A라는 단어가 doc1, doc3에 등장했다면 DF는 2가 됩니다. DF가 클수록 다수 문서에 쓰이는 범용적인 단어라고 볼 수 있겠네요. 이미 눈치채셨겠지만 TF는 같은 단어라도 문서마다 다른 값을 갖고요, DF는 문서가 달라지더라도 동일한 값을 지니게 됩니다.

IDF(Inverse Document Frequency)는 전체 단어수를 해당 단어의 DF로 나눈 뒤 로그를 취한 값입니다. 그 값이 클수록 특이한 단어라는 뜻이 됩니다. 예컨대 아래 표를 보시죠. 전체 문서 수(N)는 100만개입니다.

calpurnia는 줄리어스 시저의 세번째 아내(B.C. 59~44)의 이름이라고 합니다. 그만큼 희귀한 단어겠죠. 위 예시 기준으로 보시면 100만개 전체 문서 가운데 단 하나의 문서에만 등장했군요. 역시 idf값도 높습니다. 반대로 정관사 ‘the’를 볼까요? 100만개 모든 문서에 모두 등장한 흔한 단어이군요. 이를 idf 식에 넣어서 계산해봤더니 가장 낮은 1이 됩니다. 다시 한번 말씀드리면 idf는 클 수록 특이한 단어라는 뜻입니다.

TF-IDF

TF-IDF는 TF와 IDF를 곱해 두 지표를 동시에 고려하는 가중치 산출 방법입니다. 다시 말해 어떤 단어가 얼마나 많이 쓰였는지, 그 단어가 얼마나 특이한지를 모두 반영한 수치란 뜻입니다. 그 식은 아래와 같이 정의됩니다.

[TF-IDF(w)=tf(w)\times \log { (\frac { N }{ df(w) } ) }]

문서가 3개, 단어가 5개 있는 학습말뭉치를 예로 들어보겠습니다. 문서1의 TF, IDF, TF-IDF는 각각 아래와 같이 계산됩니다.

위 표를 기준으로 할때 doc1을 가려내는 데 가장 중요한 역할을 하는 단어는 무엇일까요? 그 후보는 term1과 term2가 될 겁니다. 둘 모두 doc1에만 쓰였기 때문입니다. 그런데 이 중에서도 term1이 term2보다 많이 쓰였기 때문에 term1이 가장 중요한 단어가 될 겁니다. doc1의 term1에 대응하는 TF-IDF가 가장 높음을 역시 확인할 수 있습니다. 그렇다면 반대로 모든 문서에 비슷하게 많이 쓰인 term3, term4는 어떨까요? 이들에 대응하는 TF-IDF 값은 0입니다. 바꿔 말하면 term3과 term4는 모두 doc1이라는 문서를 특징짓는 데 아무런 정보를 가지고 있지 않다는 이야기입니다.

TF-IDF 변형들

오래 전 제안돼 그 성능 또한 검증된 방식인 만큼 여러 변형들이 존재합니다. 대표적으로 아래와 같은 방식들이 있는데요, 붉은색 표시가 된 방식이 가장 많이 쓰인다고 합니다.

이번 포스팅에선 한번에 하나씩의 설명변수를 사용하여 예측 가능한 규칙들의 집합을 생성하는 알고리즘인 의사결정나무(Decision Tree)에 대해 다뤄보도록 하겠습니다. 이번 글은 고려대 강필성 교수님 강의와 김성범 교수님 강의를 참고했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

모델 소개

의사결정나무는 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타내며, 그 모양이 ‘나무’와 같다고 해서 의사결정나무라 불립니다. 질문을 던져서 대상을 좁혀나가는 ‘스무고개’ 놀이와 비슷한 개념입니다. 한번 예를 들어볼까요?

위 예시는 운동경기가 열렸다면 PLAY=1, 그렇지 않으면 PLAY=0으로 하는 이진분류(binary classification) 문제입니다. 모든 사례를 조사해 그림으로 도시하면 위와 같은 그림이 되는 것입니다. 그림을 한번 해석해볼까요? 날씨가 맑고(sunny), 습도(humidity)가 70 이하인 날엔 경기가 열렸습니다. 해당 조건에 맞는 데이터들이 ‘경기가 열렸다(play 2건)’고 말하고 있기 때문입니다. 반대로 비가 오고(rain) 바람이 부는(windy) 날엔 경기가 열리지 않았습니다. 의사결정나무를 일반화한 그림은 아래와 같습니다.

전체적으로 보면 나무를 뒤집어놓은 것과 같은 모양입니다. 아시다시피 초기지점은 root node이고 분기가 거듭될 수록 그에 해당하는 데이터의 개수는 줄어듭니다. 각 terminal node에 속하는 데이터의 개수를 합하면 root node의 데이터수와 일치합니다. 바꿔 말하면 terminal node 간 교집합이 없다는 뜻입니다. 한편 terminal node의 개수가 분리된 집합의 개수입니다. 예컨대 위 그림처럼 terminal node가 3개라면 전체 데이터가 3개의 부분집합으로 나눠진 셈입니다.

의사결정나무는 분류(classification)와 회귀(regression) 모두 가능합니다. 범주나 연속형 수치 모두 예측할 수 있다는 말입니다. 의사결정나무의 범주예측, 즉 분류 과정은 이렇습니다. 새로운 데이터가 특정 terminal node에 속한다는 정보를 확인한 뒤 해당 terminal node에서 가장 빈도가 높은 범주에 새로운 데이터를 분류하게 됩니다. 운동경기 예시를 기준으로 말씀드리면 날씨는 맑은데 습도가 70을 넘는 날은 경기가 열리지 않을 거라고 예측합니다.

회귀의 경우 해당 terminal node의 종속변수(y)의 평균을 예측값으로 반환하게 되는데요, 이 때 예측값의 종류는 terminal node 개수와 일치합니다. 만약 terminal node 수가 3개뿐이라면 새로운 데이터가 100개, 아니 1000개가 주어진다고 해도 의사결정나무는 딱 3종류의 답만을 출력하게 될 겁니다.

그렇다면 데이터를 분할한다는 건 정확히 어떤 의미를 지니는걸까요? 설명변수(X)가 3개짜리인 다변량 데이터에 의사결정나무를 적용한다고 가정하고 아래 그림을 보시면 좋을 것 같습니다.

아무런 분기가 일어나지 않은 상태의 root node는 A입니다. 변수가 3개짜리이니 왼쪽 그래프처럼 3차원 공간에 있는 직육면체를 A라고 상정해도 좋을 것 같네요. A가 어떤 기준에 의해 B와 C로 분할됐다고 생각해 봅시다. 그렇다면 두번째 그림처럼 A가 두 개의 부분집합으로 나뉘었다고 상상해 볼 수 있겠습니다. 마지막으로 B가 D와 C로 분할됐다면, 3번째 줄의 그림처럼 될 겁니다. 이 예시에서 terminal node는 C, D, E 세 개 인데요, 이를 데이터 공간과 연관지어 생각해보면 전체 데이터 A가 세 개의 부분집합으로 분할된 것 또한 알 수 있습니다. D 특성을 갖고 있는 새로운 데이터가 주어졌을 때 의사결정나무는 D 집합을 대표할 수 있는 값(분류=최빈값, 회귀=평균)을 반환하는 방식으로 예측합니다.

불순도/불확실성

의사결정나무는 한번 분기 때마다 변수 영역을 두 개로 구분하는 모델이라고 설명을 드렸는데요, 그렇다면 대체 어떤 기준으로 영역을 나누는 걸까요? 이 글에서는 타겟변수(Y)가 범주형 변수인 분류나무를 기준으로 설명하겠습니다.

결론부터 말씀드리면 분류나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행합니다. 순도가 증가/불확실성이 감소하는 걸 두고 정보이론에서는 정보획득(information gain)이라고 합니다. 이번 챕터에서는 어떤 데이터가 균일한 정도를 나타내는 지표, 즉 순도를 계산하는 3가지 방식에 대해 살펴보겠습니다. 우선 그림을 보시죠.

먼저 설명드릴 지표는 엔트로피(entropy)입니다. m개의 레코드가 속하는 A영역에 대한 엔트로피는 아래와 같은 식으로 정의됩니다. (Pk=A영역에 속하는 레코드 가운데 k 범주에 속하는 레코드의 비율)

[Entropy(A)=-\sum { k=1 }^{ m }{ { p }{ k }\log { 2 }{ { (p }{ k }) } }]

이 식을 바탕으로 오렌지색 박스로 둘러쌓인 A 영역의 엔트로피를 구해보겠습니다. 전체 16개(m=16) 가운데 빨간색 동그라미(범주=1)는 10개, 파란색(범주=2)은 6개이군요. 그럼 A 영역의 엔트로피는 다음과 같습니다.

[Entropy(A)=-\frac { 10 }{ 16 } \log _{ 2 }{ (\frac { 10 }{ 16 } ) } -\frac { 6 }{ 16 } \log _{ 2 }{ (\frac { 6 }{ 16 } ) } \approx 0.95]

여기서 A 영역에 빨간색 점선을 그어 두 개 부분집합(R1, R2)으로 분할한다고 가정해 봅시다. 두 개 이상 영역에 대한 엔트로피 공식은 아래 식과 같습니다. 이 공식에 의해 분할 수 A 영역의 엔트로피를 아래와 같이 각각 구할 수 있습니다. (Ri=분할 전 레코드 가운데 분할 후 i 영역에 속하는 레코드의 비율)

[Entropy(A)=\sum { i=1 }^{ d }{ { R }{ i } } \left( -\sum { k=1 }^{ m }{ { p }{ k }\log { 2 }{ { (p }{ k }) } } \right)]

[Entropy(A)=0.5\times \left( -\frac { 7 }{ 8 } \log _{ 2 }{ (\frac { 7 }{ 8 } ) } -\frac { 1 }{ 8 } \log _{ 2 }{ (\frac { 1 }{ 8 } ) } \right) +0.5\times \left( -\frac { 3 }{ 8 } \log _{ 2 }{ (\frac { 3 }{ 8 } ) } -\frac { 5 }{ 8 } \log _{ 2 }{ (\frac { 5 }{ 8 } ) } \right) \approx 0.75]

그럼 분기 전과 분기 후의 엔트로피가 어떻게 변화했는지 볼까요? 분기 전 엔트로피가 0.95였는데 분할한 뒤에 0.75가 됐군요. 0.2만큼 엔트로피 감소(=불확실성 감소=순도 증가=정보획득)한 걸로 봐서 의사결정나무 모델은 분할한 것이 분할 전보다 낫다는 판단 하에 데이터를 두 개의 부분집합으로 나누게 됩니다. 다시 한번 말씀드리지만 의사결정나무는 구분 뒤 각 영역의 순도(homogeneity)가 증가/불확실성(엔트로피)가 최대한 감소하도록 하는 방향으로 학습을 진행합니다.

순도와 관련해 부연설명을 드리면 A 영역에 속한 모든 레코드가 동일한 범주에 속할 경우(=불확실성 최소=순도 최대) 엔트로피는 0입니다. 반대로 범주가 둘뿐이고 해당 개체의 수가 동일하게 반반씩 섞여 있을 경우(=불확실성 최대=순도 최소) 엔트로피는 1의 값을 갖습니다. 엔트로피 외에 불순도 지표로 많이 쓰이는 지니계수(Gini Index) 공식은 아래와 같습니다.

[G.I(A)=\sum { i=1 }^{ d }{ { \left( { R }{ i }\left( 1-\sum { k=1 }^{ m }{ { p }{ ik }^{ 2 } } \right) \right) } }]

아래는 범주가 두 개일 때 한쪽 범주에 속한 비율(p)에 따른 불순도의 변화량을 그래프로 나타낸 것입니다. 보시다시피 그 비율이 0.5(두 범주가 각각 반반씩 섞여 있는 경우)일 때 불순도가 최대임을 알 수가 있습니다. 오분류오차(misclassification error)는 따로 설명드리지 않은 지표인데요, 오분류오차는 엔트로피나 지니계수와 더불어 불순도를 측정할 수 있긴 하나 나머지 두 지표와 달리 미분이 불가능한 점 때문에 자주 쓰이지는 않는다고 합니다.

모델 학습

의사결정나무의 학습 과정은 입력 변수 영역을 두 개로 구분하는 재귀적 분기(recursive partitioning)와 너무 자세하게 구분된 영역을 통합하는 가지치기(pruning) 두 가지 과정으로 나뉩니다. 우선 재귀적 분기 먼저 살펴보겠습니다.

재귀적 분기

아래와 같이 24개 가정을 대상으로 소득(income), 주택크기(Lot size), 잔디깎기 기계 구입 여부(Ownership)를 조사한 데이터가 있습니다. 이를 토대로 소득과 주택크기를 설명변수(X), 기계 구입 여부를 종속변수(Y)로 하는 분류나무 모델을 학습시켜 보겠습니다.

우선 이를 한 변수 기준(예컨대 주택 크기)으로 정렬합니다. 이후 가능한 모든 분기점에 대해 엔트로피/지니계수를 구해 분기 전과 비교해 정보획득을 조사합니다. 예컨대 아래 표 기준으로 보시면 분기지점을 첫 레코드와 나머지 23개 레코드로 두고, 1번 레코드와 2~24번 레코드 간의 엔트로피를 구한 뒤 이를 분기 전 엔트로피와 비교해 정보획득을 조사합니다. 그 결과는 아래와 같습니다.

[\begin {align} 분기\quad전\quad 엔트로피&=-\frac { 1 }{ 2 } \log _{ 2 }{ (\frac { 1 }{ 2 } ) } -\frac { 1 }{ 2 } \log _{ 2 }{ (\frac { 1 }{ 2 } ) } =1\분기\quad후\quad엔트로피 &=\frac { 1 }{ 24 } \left( -\log _{ 2 }{ 1 } \right) +\frac { 23 }{ 24 } \left( -\frac { 12 }{ 23 } \log _{ 2 }{ (\frac { 12 }{ 23 } ) } -\frac { 11 }{ 23 } \log _{ 2 }{ (\frac { 11 }{ 23 } ) } \right) \approx 0.96\ 정보획득&=1-0.96=0.04 \end{align}]

이후 분기 지점을 두번째 레코드로 두고 처음 두 개 레코드와 나머지 22개 레코드 간의 엔트로피를 계산한 뒤 정보획득을 알아봅니다. 이렇게 순차적으로 계산한 뒤, 이번엔 다른 변수인 소득을 기준으로 정렬하고 다시 같은 작업을 반복합니다. 모든 경우의 수 가운데 정보획득이 가장 큰 변수와 그 지점을 택해 첫번째 분기를 하게 됩니다. 이후 또 같은 작업을 반복해 두번째, 세번째… 이렇게 분기를 계속 해 나가는 과정이 바로 의사결정나무의 학습입니다.

그렇다면 1회 분기를 위해 계산해야 하는 경우의 수는 총 몇 번일까요? 개체가 $n$개, 변수가 $d$개라고 할 때 경우의 수는 $d(n-1)$개가 됩니다. 분기를 하지 않는 경우를 제외하고 모든 개체와 변수를 고려해 보는 것입니다.

가지치기

의사결정나무 모델 학습의 또다른 축은 가지치기(pruning)입니다. 모든 terminal node의 순도가 100%인 상태를 Full tree라고 하는데요. 이렇게 Full tree를 생성한 뒤 적절한 수준에서 terminal node를 결합해주어야 합니다. 왜냐하면 분기가 너무 많아서 학습데이터에 과적합(overfitting)할 염려가 생기기 때문입니다.

의사결정나무의 분기 수가 증가할 때 처음에는 새로운 데이터에 대한 오분류율이 감소하나 일정 수준 이상이 되면 오분류율이 되레 증가하는 현상이 발생한다고 합니다. 이러한 문제를 해결하기 위해서는 검증데이터에 대한 오분류율이 증가하는 시점에서 적절히 가지치기를 수행해줘야 합니다.

마치 나뭇가지를 잘라내는 것과 같다는 의미에서 이러한 용어가 붙었습니다. 매우 직관적이죠. 가지치기 개념도는 아래와 같습니다. 다만 가지치기는 데이터를 버리는 개념이 아니고 분기를 합치는(merge) 개념으로 이해해야 합니다.

재귀적 분기를 설명해 드릴 때 들었던 잔디깎기 기계 구입 여부 데이터를 의사결정나무로 학습한 결과물입니다. 왼쪽이 Full tree, 오른쪽이 가지치기를 한 결과를 시각화한 것입니다. 왼쪽 그림을 보시면 모든 terminal node의 불순도는 0임을 확인할 수 있습니다.

하지만 terminal node가 너무 많으면 새로운 데이터에 대한 예측 성능인 일반화(generalization) 능력이 매우 떨어질 염려가 있습니다. terminal node를 적절하게 합쳐주면 오른쪽 그림과 같은 결과가 나오는 걸 확인할 수 있습니다.

마지막으로 가지치기의 비용함수(cost function)를 살펴보겠습니다. 의사결정나무는 이 비용함수를 최소로 하는 분기를 찾아내도록 학습됩니다. 아래와 같이 정의됩니다.

[CC(T)=Err(T)+\alpha \times L(T)]

CC(T)=의사결정나무의 비용 복잡도(=오류가 적으면서 terminal node 수가 적은 단순한 모델일 수록 작은 값)

ERR(T)=검증데이터에 대한 오분류율

L(T)=terminal node의 수(구조의 복잡도)

Alpha=ERR(T)와 L(T)를 결합하는 가중치(사용자에 의해 부여됨, 보통 0.01~0.1의 값을 씀)

마치며

이상으로 의사결정나무에 대해 살펴보았습니다. 의사결정나무는 계산복잡성 대비 높은 예측 성능을 내는 것으로 정평이 나 있습니다. 아울러 변수 단위로 설명력을 지닌다는 강점을 가지고 있습니다. 다만 의사결정나무는 결정경계(decision boundary)가 데이터 축에 수직이어서 특정 데이터에만 잘 작동할 가능성이 높습니다.

이같은 문제를 극복하기 위해 등장한 모델이 바로 랜덤포레스트인데요, 같은 데이터에 대해 의사결정나무를 여러 개 만들어 그 결과를 종합해 예측 성능을 높이는 기법입니다.

의사결정나무든 랜덤포레스트는 R이나 Python 등 주요 언어에서 모두 패키지 형태로 쉽고 간편하게 사용을 할 수가 있으니 한번쯤은 실험을 해보시면 좋을 것 같습니다. 질문이나 의견 있으시면 이메일이나 댓글로 부탁드립니다. 여기까지 읽어주셔서 감사드립니다.