이번 글에서는 차원축소(dimensionality reduction)와 군집화(clustering)를 동시에 수행하는 기법인 자기조직화지도(Self-Organizing Map, SOM)를 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

아키텍처 개요

SOM이란 사람이 눈으로 볼 수 있는 저차원(2차원 내지 3차원) 격자에 고차원 데이터의 각 개체들이 대응하도록 인공신경망과 유사한 방식의 학습을 통해 군집을 도출해내는 기법입니다. 고차원의 데이터 원공간에서 유사한 개체들은 저차원에 인접한 격자들과 연결됩니다. 저차원 격자에서의 유사도는 고차원 입력 공간에서의 유사도를 최대한 보존하도록 학습됩니다.

SOM 아키텍처의 핵심은 대략 아래 그림과 같습니다.

위 그림에서 초록색 노드($x_i$)는 $n$차원 입력벡터의 각 요소를 뜻합니다. 주황색 노드($w_j$)는 2차원 격자입니다.

저차원 격자 하나에는 여러 개의 입력벡터들이 속할 수 있습니다. 여기에 속한 입력벡터들끼리는 서로 위치적인 유사도를 가집니다(=가까운 곳에 있음).

그럼 임의의 입력벡터가 주어졌을 때 2차원상 어떤 격자에 속하는지 어떻게 알 수 있을까요? 위 그림 기준으로 $j$번째 격자는 원데이터 공간에 존재하는 $n$차원 벡터 $[w_{j1},w_{j2},…,w_{jn}]$에 대응됩니다.

다시 말해 2차원상 격자가 위 그림처럼 25개라면 그에 해당하는 $n$차원 크기의 격자벡터도 25개 있다는 이야기이죠.

임의의 $n$차원 입력벡터가 들어왔을 때 가장 가까운 격자벡터를 찾습니다. 이것을 Winning node라고 합니다. 이 벡터에 대응되는 2차원상 격자에 해당 입력벡터를 할당하면 이것이 바로 군집화가 되는 것입니다.

같은 격자에 할당된 입력벡터라 하더라도 Winning node와의 거리가 제각기 다를 수 있습니다. 이러한 멀고 가까움 또한 표시를 하게 되면 고차원 공간의 원데이터를 2차원 내지 3차원으로 차원을 축소하는 효과까지 낼 수 있습니다.

SOM의 결과물 예시는 아래 그림과 같습니다. 고차원 공간의 원데이터가 25개 격자에 각각 할당(군집화)돼 있고, 동일한 격자에 할당된 입력값끼리도 그 위치가 서로 다르게 임베딩된 것을 확인할 수 있습니다.

SOM 학습

그렇다면 SOM은 어떻게 학습을 하는 것일까요? 직관적으로 이해해보기 위해 아래 그림을 먼저 살펴보겠습니다. 시각화를 위해 원데이터의 차원수와 격자의 차원수는 모두 2차원으로 두었습니다. 하지만 이는 이해를 돕기 위함일 뿐, 검정색 점이 흩뿌려진 원데이터 공간은 고차원이라고 생각하셔야 합니다.

위 그림에서 연두색 25개 점은 고차원의 원데이터공간에 대응되는 격자벡터입니다. 처음엔 그 위치를 랜덤으로 초기화합니다. 이후 학습데이터 $x$(검정색 점)를 하나씩 추가해가며 격자벡터의 위치를 $x$의 위치와 비슷해지도록 업데이트합니다(instance-based learning).

다만 여기서 주의해야할 것은 격자벡터의 업데이트 폭이 모두 같지는 않다는 점입니다. 현재 주어진 $x$와 그 위치가 가장 가까운 Winning node가 제일 많이 업데이트되고요, 이 노드의 주변 격자벡터들은 그보다 조금 덜 업데이트됩니다. 멀리 떨어진 녀석들은 거의 업데이트가 되지 않도록 합니다.

$t$시점의 $j$번째 격자벡터를 업데이트하는 과정을 수식으로 나타내면 아래와 같습니다.

[{ w }{ j }^{ t+1 }={ w }{ j }^{ t }+{ \mu }{ t }{ \lambda }{ x }^{ j,t }[x-{ w }_{ j }^{ t }]]

여기에서 $μ$는 일종의 learning rate로 반복 횟수가 커지면 학습 속도를 줄이는 역할을 합니다. λ는 Winning node는 가장 크게, 학습데이터와 멀리 떨어진 격자벡터는 작게 업데이트하도록 합니다(가우시안 분포 활용). 마지막으로 괄호 안의 뺄셈으로 된 부분은 학습데이터 $x$와 격자벡터 간 차이를 의미하는데, 벡터의 덧/뺄셈 결과 역시 벡터이므로 격자벡터가 업데이트되는 방향을 결정해줍니다.

이번 글에서는 변형생성문법(transformational generative grammar)에 대해 살펴보도록 하겠습니다. 이 글은 고종석의 언어학 강의 불순한 언어가 아름답다의 56~60페이지를 그대로 옮겨 왔습니다. 개인적인 정리 용도로 타이핑 겸 긁어왔는데요, 저작권법 등 문제가 될 경우 자삭하겠습니다.

변형생성문법?

흔히 촘스키(Noam Chomsky) 언어학을 변형생성문법이라고 합니다. 도대체 변형생성문법이란 뭘까요? 그리고 그것이 극복했다고 주장하는 구조주의 언어학과는 어떻게 다를까요? 다음 두 문장을 봅시다.

(1) 존경하는 선생님께서 감격스럽게도 제게 꽃을 이만큼이나 보내 오셨어요.

(2) 존경하는 제자들이 기특하게도 선생님께 꽃을 이만큼이나 보내 왔어요.

이 두 문장은 구조적으로 완전히 같습니다. 적어도 겉보기에는 말이죠. 전통문법에서 흔히 주부(主部)라고 부르는 부분만 살핍시다. 동사의 현재관형형(존경하는)이 명사(선생님/제자들)를 수식하고, 이렇게 만들어진 명사구에 주격표지(께서/이)가 붙어 주어 노릇을 합니다. 그런데 ‘존경하는 선생님’과 ‘존경하는 제자들’은 정말 같은 구조를 지녔을까요? 그렇기도 하고 그렇지 않기도 합니다.

그렇다는 것은 그 둘 다 현재관형형 동사 뒤에 수식되는 명사가 이어진다는 점에서입니다. 명사(구)를 ‘NP’로 나타내고 동사의 현재관형형을 ‘V-는’으로 나타내면, ‘존경하는 선생님’과 ‘존경하는 제자들’은 둘 다 [V-는 NP]라는 구조를 지닌 NP(명사구)입니다. 이렇게 겉으로 드러나는 구조를 촘스키는 표면구조(surface structure)라고 불렀습니다. 촘스키에 따르면 표면구조는 음성 해석 정보를 지녔습니다.

그런데 촘스키는 이런 표면구조 저 아래에 누워 있는(underlie) 또 하나의 구조를 가정합니다. 촘스키가 심층구조(deep structure)라고 부르는 이 층위에서는 ‘존경하는 선생님’과 ‘존경하는 제자들’의 구조가 서로 다릅니다.

심층구조에서 ‘존경하는 선생님’은 ‘선생님을 존경한다’입니다. 다시 말해 [NP 목적격표지 V-ㄴ다]의 구조를 지닌 S(문장)입니다. 그러나 ‘존경하는 제자들’은 심층구조에서 ‘제자들이 존경한다’입니다. 다시 말해 [NP 주격표지 V-ㄴ다]의 구조를 지닌 S입니다.

즉 심층구조에서 ‘선생님’은 ‘존경하다’의 목적어인 데 반해, ‘제자들’은 ‘존경하다’의 주어입니다. 촘스키에 따르면 심층구조는 의미 해석 정보를 지녔습니다.

서로 다른 심층구조를 지닌 ‘존경하는 선생님’과 ‘존경하는 제자들’이 동일한 표면구조를 지니게 되는 것은, [NP 목적격표지 V-ㄴ다] 구조의 문장과 [NP 주격표지 V-ㄴ다] 구조의 문장을 [V-는 NP]라는 동일한 NP(명사구)로 유도하는 규칙이 한국어에 있기 때문입니다. 심층구조에서 표면구조를 유도하는 과정을 ‘변형’이라고 하고, 그 변형에 쓰인 규칙을 ‘변형규칙(transformation rule)’이라 합니다.

촘스키 문법을 변형생성문법이라고 부르는 것은 그것이 변형규칙이라는 장치를 사용하는 생성문법이기 때문입니다. 그것을 생성문법이라고 부르는 것은 유한한 규칙들의 집합(구조)을 통해서 무한한 적격(well-formed) 문장들을 생성해내는 모국어 화자의 능력에 이 이론이 관심을 쏟기 때문입니다.

촘스키에 따르면 구조주의 언어학자들은 ‘존경하는 선생님’과 ‘존경하는 제자들’의 구조적 다름을 ‘설명’할 수 없습니다. 그들은 잘해봐야 그 다름을 ‘관찰’하거나 ‘기술’할 수 있을 따름입니다. 그런데 일반 언어 이론은 이런 관찰적 타당성(ovservational adequacy)이나 기술적 타당성(descriptive adequacy)을 넘어서는 설명적 타당성(explanatory adequacy)을 지녀야 한다고 촘스키는 말합니다. 물론 자신의 변형생성문법이야말로 그런 설명적 타당성을 지녔다는 거지요.

표면구조와 심층구조

표면구조는 같은데 심층구조는 다른 예로 촘스키가 제시한 가장 유명한 문장은 아래와 같습니다.

(a) John is easy to please (존은 까다롭지 않다)

(b) John is eager to please (존은 남에게 잘 보이려 한다)

명백히 보이듯 이 두 문장의 표면구조는 같지만 심층구조에서 (a)의 John은 please의 목적어이고, (b)의 John은 please의 주어입니다.

표면구조가 다른데 심층구조가 같은 경우도 있습니다.

(ㄱ) 나는 당신이 바보라고 생각했어

(ㄴ) 나는 당신을 바보로 생각했어

(ㄱ) I believed you was an idiot

(ㄴ) I believed you (to be)an idiot

한국어든 영어든 이 문장의 심층구조는 앞쪽 표면구조에 가깝습니다. 그 심층구조에 인상변형(raising transformation)이라는 규칙이 적용되면 뒤쪽 표면구조가 유도됩니다. 또 능동문과 피동문도, 동일한 심층구조가 서로 다른 표면구조로 유도된 대표적 예입니다.

변형생성문법의 의의와 한계

촘스키의 변형생성문법은 초기의 표준이론에서 확대표준이론(EST), 지배결속이론(GB), 최소주의프로그램(MP) 등으로 정교화하면서 한 세대 이상 세계 언어학계를 풍미했습니다. 영어권 학계만이 아니라 서유럽, 일본, 중국, 대만, 한국 등지에서 촘스키는 거의 동시에 읽혔습니다.

촘스키 언어학이 이렇게 큰 영향을 끼칠 수 있었던 이유 가운데 하나는 그 이론의 보편 지향성에 있을 겁니다. 촘스키는 수많은 자연언어들의 문법이 표면구조에서는 달라도 심층구조에서는 같으리라 예상했습니다. 말하자면 그의 두드러진 욕망 하나는 보편문법을 수립하는 것이었지요. 이탈리어어나 프랑스어를, 일본어나 중국어나 한국어를 모국어로 삼은 언어학자들이 촘스키 이론을 자신의 가장 익숙한 언어에 적용해보고 싶어 했던 것이 이해됩니다.

그렇지만 촘스키의 변형생성문법도 ‘사실’이 아니라 하나의 ‘이론’에 불과하다는 점을 강조하고 싶습니다. 사실 언어라는 현상은 너무나 복잡해서, 언어가 이거다, 또는 저거다, 라고 한마디로 규정할 수 없습니다. 언어는 X다, 라는 명제에서 X는 무수히 많을 수도 있고, 하나도 없을 수도 있습니다. 그만큼 언어의 ‘본질’에 대한 견해는 연구자들마다 다르다는 겁니다.

이번 글은 한국어 기본문을 통사원자(syntactic atom)로 구성된 계층구조로 분석하는 파싱(parsing) 방법에 대해 살펴보도록 하겠습니다. 이 글은 국어 기본문의 문법 구조를 밝힌 박진호(1994)를 정리했음을 먼저 밝힙니다. 자연언어처리라는 목적을 위해 원저작의 내용을 상당히 단순화했다는 점 또한 먼저 말씀드립니다. 그럼 시작하겠습니다.

기본 원리

우선 아래 예문을 살펴보겠습니다.

철수가 밥을 먹었다

이 문장을 파싱하려면 어떻게 해야할까요? ‘먹었다’라는 서술어는 의미론적으로 행위주(철수가)와 대상(밥을)을 요구하므로 당장 떠오르는 방법은 아래와 같을 겁니다.

그런데 자세히 살펴보면 선어말어미 ‘-었-‘은 ‘철수라는 사람이 밥을 먹은 행위가 과거에 있었다’는 의미를 나타냅니다. 다시 말해 ‘-었-‘은 어간 ‘먹-‘이 아니라 ‘철수가 밥을 먹-‘이라는 큰 단위와 결합했다고 보는게 자연스럽다는 것이지요. 이는 한국어의 다른 문장도 마찬가지입니다.

ㄱ. 어제 철수는 청소를 하고 영희는 빨래를 하였다.

ㄴ. 지금쯤 철수는 청소를 하고 영희는 빨래를 하겠다.

위 두 문장에서 철수가 청소를 한 시점은 언제일까요? 한국어 화자라면 (ㄱ)은 과거, (ㄴ)은 현재(추측)라는 것을 단번에 알아차릴 수 있을 겁니다.

두 문장 모두 ‘철수는 청소를 하고’라는 동일한 표현을 썼습니다. 그럼에도 이렇게 의미(시점)가 달라지는 이유는 무엇일까요? 선어말어미 ‘-었-‘, ‘-겠-‘이 어간 ‘하-‘가 아니라 ‘철수는 청소를 하고 영희는 빨래를 하-‘라는 큰 단위와 결합했기 때문입니다.

따라서 ‘철수가 밥을 먹었다’는 문장은 다음과 같이 분석할 수 있습니다.

여기에서 핵(head) 개념이 등장합니다. 명사, 동사, 조사, 어미 등 개별 통사원자들이 위 그림처럼 위계적 구조를 가지고 결합한 것이 문장입니다. 두 통사원자가 결합하여 이루는 상위 단위의 통사적(문법적) 성격은 하위 요소의 통사적 성격에 의해 결정됩니다. 대개 둘 중 어느 한 요소가 중심적 역할을 맡게 되는데요, 이 때 중심 역할을 하는 요소를 ‘핵’이라고 합니다.

박진호(1994)에 따르면 위 문장에서 ‘철수’라는 명사는 격조사 ‘-가’와 결합해 (주)격조사구(phrase)가 됩니다. 격조사 ‘-가’가 핵이라는 이야기입니다. 마찬가지로 (목적)격조사구 ‘밥을’에서는 ‘-을’이 핵입니다. ‘밥을 먹-‘이라는 동사구에서는 동사 ‘먹-‘이 핵입니다.

다시 말해 ‘철수가’는 문장의 주어 역할을, ‘밥을’은 목적어 역할을, ‘밥을 먹-‘은 동사 역할을 하는데요, 이렇게 결합 이후의 통사적 성격 결정에 중요한 영향을 끼치는 것이 바로 핵이라고 말할 수 있습니다.

박진호(1994)는 한국어 통사원자의 범주를 8개로 나누고 그 기호를 아래와 같이 정의했습니다. 이후 예시에서 이 표기를 따르도록 하겠습니다.

국어 기본문의 논항 구조

논항(argument)이란 핵과 대비되는 개념으로, 핵이 요구하는 필수적 성분을 일컫는 용어입니다. 예컨대 ‘먹-‘이라는 동사는 ‘밥’ 같은 명사(구)를 반드시 필요로 합니다. 따라서 ‘밥 먹-‘에서 핵은 동사, 논항은 ‘밥’이 되는 것입니다.

선문말어미

선문말어미는 동사구 하나와 결합하며 선행 동사구(철수 밥 먹)가 핵이 됩니다. 다시 말해 선문말어미는 동사구의 논항입니다.

문말어미

동사구가 문말어미와 결합할 때는 문말어미가 핵이 됩니다. 다시 말해 동사구는 문말어미의 논항입니다. 동사구와 문말어미가 결합함으로써 절(節)이 됩니다. 아래와 같이 ‘-다’라는 문말어미는 동사구 한 개를 논항으로 가집니다.

그러나 문말어미가 아래와 같이 연결어미일 경우에는 선행 동사구 하나, 후행 동사구 하나, 이렇게 두 개의 논항을 가집니다. 연결어미는 선행 동사구와 결합할 때는 핵이 되지만 후행 요소와 결합할 때는 비핵이 됩니다.

문말어미가 관형사형어미일 경우 선행 동사구 하나, 후행 명사구 하나, 이렇게 두 개의 논항을 가집니다. 관형사형어미는 선행 동사구와 결합할 때는 핵이 되지만 후행 요소와 결합할 때는 비핵이 됩니다.

조사 (격조사/보조사)

조사는 대체로 개체와 그 개체가 참여하는 사건 사이의 관계를 나타내 줍니다. 관계란 정의상 두 개의 항(term)의 존재를 전제로 하기 때문에 조사는 격조사이든 보조사이든 두 개의 논항을 취합니다.

격조사는 선행 명사구와 결합할 때는 핵이 되지만 후행 동사구와 결합할 때는 비핵이 됩니다.

반면 보조사는 늘 비핵입니다.

관형사와 부사

관형사는 후행 명사구 하나, 부사는 후행 동사구 하나를 논항으로 각각 취합니다. 이들은 모두 후행 요소와 결합할 때 비핵이 됩니다.

동사와 명사

동사와 명사는 다른 범주와 달리 논항의 자릿수(개수)가 일률적으로 정해져 있지 않고, 개별 어휘에 따라 다릅니다. 박진호(1994)에 따르면 한국어 동사의 자릿수는 대체로 하나에서 셋이라고 합니다. 대표적 사례는 아래 표와 같습니다.

명사의 경우 자릿수가 0인 경우가 대다수라고 합니다. 그러나 공부, 연구, 살해 등처럼 행위의 주체와 대상을 논항으로 요구하거나 소문, 사실, 이유처럼 명제를 논항으로 취하는 명사도 꽤 있습니다. 명사와 동사 모두 자신의 논항과 결합할 때 핵이 됩니다.

복잡한 문장 분석하기

이번 항목에서는 지금까지 설명해드린 기본문보다 복잡한 구조를 지닌 문장을 분석해보도록 하겠습니다.

전수

명사구 ‘내가 살던 집’은 아래와 같이 분석할 수 있습니다. 우선 격조사구 ‘내가’에 동사 ‘살-‘이 결합해 동사구가 됩니다. 여기에 문말어미(관형사형어미) ‘-던’이 붙어 절이 됩니다. 마지막으로 ‘집’이라는 명사와 ‘내가 살던’이라는 부가어 절이 결합해 ‘내가 살던 집’이라는 명사구를 이룹니다.

그렇다면 ‘나의 살던 집’은 어떻게 분석해야 할까요? 아래와 같습니다.

‘나의 살던 집’에서 ‘나의’는 관형격이므로 동사 ‘살-‘ 혹은 동사구 ‘살던’과는 결합할 수 없고, 명사구 ‘살던 집’과 결합할 수밖에 없습니다. 동사 ‘살-‘은 행위주역과 장소역을 논항으로 가지는데요, 위 예시에서는 ‘살-‘이 자신의 행위주역 논항에 대한 지배권을 ‘-던’에, 그리고 다시 ‘집’에 전수(inheritance)했기 때문에 가능한 것입니다.

합류

‘철수가 먹은 떡’은 아래와 같이 분석할 수 있습니다.

동사구 ‘철수가 먹-‘은 대상역을 논항으로 가집니다. 문말어미(관형사형어미) ‘-은’은 선행 동사구와 후행 명사구를 논항으로 가집니다. 이 둘이 결합하면서 ‘철수가 먹-‘의 대상역 논항과 ‘-은’의 후행 명사구 논항이 합류(merge)하는 걸 볼 수 있습니다. 다시 말해 ‘떡’은 동사구 ‘철수가 먹-‘의 논항이면서, 동시에 문말어미 ‘-은’의 논항이기도 합니다.

조사 중출

국어에서는 하나의 명사구에 조사가 둘 이상 붙는 것이 가능합니다. 특히 격조사와 보조사가 하나씩 붙는 일은 매우 흔합니다. ‘철수는 영희만을 사랑한다’에서 ‘영희만을 사랑하-‘를 분석하면 아래와 같습니다.

대등 접속

문장 내에서 명사(구)가 연결되는 경우 아래와 같이 분석할 수 있습니다.

명사(구)를 병렬적으로 나열하는 경우 아래와 같이 분석할 수 있습니다.

안긴 문장(내포문)

‘철수는 영수에게 일하라고 명령했다’에서 ‘영수에게 일하라고 명령하-‘를 분석하면 아래와 같습니다.

이어진 문장(접속문)

‘철수는 식사를 마치고 집을 나섰다’에서 ‘식사를 마치고 집을 나서-‘를 분석하면 아래와 같습니다.

tough 구문

안긴 문장 동사의 목적어 논항이 목적격뿐 아니라 주격으로도 나타나는 일이 있습니다. (a)의 경우 안긴 문장 동사 ‘잡-‘의 목적어 논항이 목적격의 ‘파리를’로 실현됐는데, (b)는 주격의 ‘파리가’로 실현됐습니다. 이와 같은 구문을 언어학에서는 tough 구문이라고 부릅니다.

(a) 파리를 잡기가 어렵다

(b) 파리가 잡기가 어렵다

(a)를 분석하면 아래와 같습니다.

(b)를 분석하면 아래와 같습니다.

국어에서는 tough 구문을 허용하는 동사가 많지는 않다고 합니다. ‘쉽-‘, ‘어렵-‘, ‘수월하-‘, ‘힘들-‘ 같이 어렵고 힘듬을 나타내는 동사가 대표적입니다. 심리 동사 가운데 ‘싶-‘과 ‘싫-‘도 이 범주에 포함됩니다.

목적어의 인상 구문

‘영희는 철수를 바보로 생각한다’에서 ‘철수를 바보로 생각하-‘를 분석하면 아래와 같습니다.

이중주어문

아래 예시의 이중주어문은 각각 다음과 같이 분석할 수 있습니다.

(가) 철수의 손이 크다

(나) 철수가 손이 크다

분석 예시

지금까지 논의한 내용을 바탕으로 아래 문장을 다음과 같이 분석해볼 수 있습니다.

철수와 영희가 영수에게만 복종하였다

마치며

이상으로 한국어 파싱의 기본 원칙에 대해 살펴보았습니다. 논문을 읽고 정리하면서 저자의 실력에 여러번 감탄할 수밖에 없었습니다. 영어 파싱에 관해서는 여러 자료들이 많으나 한국어 파싱에 관해서는 이만한 논문이 없다는 생각이 듭니다. 개인적으로 모델만큼 언어학 공부를 많이 해야겠다는 다짐을 또한 하게 됐습니다. 한편 Recursive Neural Networks는 이러한 계층구조의 데이터를 입력으로 받는 대표적인 모델인데요, 자세한 내용을 알아보시려면 이곳 방문을 권해드립니다.

이번 글에서는 데이터 차원축소(dimesionality reduction)와 시각화(visualization) 방법론으로 널리 쓰이는 t-SNE(Stochastic Neighbor Embedding)에 대해 살펴보도록 하겠습니다. 단어 벡터와 같이 고차원 데이터를 시각화하는 데 가장 인기있는 알고리즘이기도 합니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

Stochastic Neighbor Embedding

Stochastic Neighbor Embedding(SNE)란 고차원의 원공간에 존재하는 데이터 $x$의 이웃 간의 거리를 최대한 보존하는 저차원의 $y$를 학습하는 방법론입니다. stochastic이란 이름이 붙은 이유는 거리 정보를 확률적으로 나타내기 때문인데요. 이 설명만 봐서는 제대로 알 수 없으니 일단 수식 먼저 보겠습니다.

첫번째 식의 $p$는 고차원 원공간에 존재하는 $i$번째 개체 $x_i$가 주어졌을 때 $j$번째 이웃인 $x_j$가 선택될 확률을 의미합니다. 두번째 식의 $q$는 저차원에 임베딩된 $i$번째 개체 $y_i$가 주어졌을 때 $j$번째 이웃인 $y_j$가 선택될 확률을 뜻합니다.

SNE의 목적은 $p$와 $q$의 분포 차이가 최대한 작게끔 하고자 합니다. 차원축소가 제대로 잘 이뤄졌다면 고차원 공간에서 이웃으로 뽑힐 확률과 저차원 공간에서 선택될 확률이 비슷할테니까요.

두 확률분포가 얼마나 비슷한지 측정하는 지표로 Kullback-Leibler divergence라는 것이 있습니다. 두 분포가 완전히 다르면 1, 동일하면 0의 값을 갖게 되는데요, SNE는 아래 비용함수를 최소화하는 방향으로 학습을 진행하게 됩니다.

[\begin{align} Cost&=\sum _{ i }^{ }{ KL({ P }_{ i }||{ Q }_{ i }) } \ &=\sum _{ i }^{ }{ \sum _{ j }^{ }{ { p }_{ j|i }\log { \frac { { p }_{ j|i } }{ { q }_{ j|i } } } } } \end{align}]

그런데 SNE 연구진은 계산 속도를 높이기 위해 몇 가지 학습 트릭을 도입했습니다. $σ_i$는 각 개체마다 데이터 밀도가 달라서 이웃으로 뽑힐 확률이 왜곡되는 현상을 방지하기 위한 값인데요, 반복 실험 결과 $p$를 계산할 때 쓰는 $σ_i$는 고정된 값을 써도 성능에 큰 차이를 보이지 않았다고 합니다. $σ_i$ 계산을 생략하게 된 것이죠.

아울러 $i$번째 개체가 주어졌을 때 $j$번째 개체가 이웃으로 뽑힐 확률과 $j$번째 개체가 주어졌을 때 $i$번째 개체가 선택될 확률을 동일하다고 놓고 풀어도 성능이 그리 나쁘지 않았다고 합니다. 그러면 $p$와 $q$를 아래와 같이 다시 쓸 수 있습니다.

새로 쓴 비용함수와 $y_i$의 그래디언트는 아래와 같습니다.

[\begin{align} Cost&=\sum _{ i }^{ }{ KL({ P }_{ i }||{ Q }_{ i }) } \ &=\sum _{ i }^{ }{ \sum _{ j }^{ }{ { p }_{ ij }\log { \frac { { p }_{ ij } }{ { q }_{ ij } } } } } \ \frac { \partial C }{ \partial { y }_{ i } } &=4\sum _{ j }^{ }{ ({ y }_{ j }-{ y }_{ i })({ p }_{ ij }-{ q }_{ ij }) } \end{align}]

우리가 최종적으로 구하고자 하는 미지수는 저차원에 임베딩된 좌표값 $y_i$입니다. SNE는 그래디언트 디센트(gradient descent) 방식으로 $y_i$들을 업데이트합니다. 즉, 처음에 $y_i$를 랜덤으로 초기화해놓고 위에서 구한 그래디언트의 반대방향으로 조금씩 $y_i$들을 갱신해 나가는 것입니다. $y_i$의 그래디언트를 보면 우리가 이미 모두 알고 있는 값들이므로 업데이트를 여러번 반복 수행하기만 하면 됩니다.

Crowding Problem과 t-SNE

SNE가 전제하는 확률분포는 가우시안 분포입니다. 그런데 가우시안 분포는 꼬리가 두텁지 않아서 $i$번째 개체에서 적당히 떨어져 있는 이웃 $j$와 아주 많이 떨어져 있는 이웃 $k$가 선택될 확률이 크게 차이가 나지 않게 됩니다. 이를 crowding problem이라고 합니다.

이들 구분을 좀 더 잘하기 위해 가우시안분포보다 꼬리가 두터운 t분포를 쓴 것이 바로 t-SNE입니다. t-SNE는 $q_{ij}$에만 아래와 같이 t분포를 적용하고, $p_{ij}$는 SNE와 같습니다.

t-SNE 시각화

t-SNE는 보통 word2vec으로 임베딩한 단어벡터를 시각화하는 데 많이 씁니다. 문서 군집화를 수행한 뒤 이를 시각적으로 나타낼 때도 자주 사용됩니다. 저자가 직접 만든 예시 그림은 아래와 같습니다.

이번 글에서는 그래프(graph) 기반 군집화 기법인 Spectral Clustering에 대해 살펴보도록 하겠습니다. 이 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

그래프 인접행렬 구축

Spectral Clustering을 수행하려면 원데이터를 그래프로 변환하기 위해 인접행렬(Adjacency Matrix)을 만들어야 합니다. Spectral Clustering은 무방향 가중치 그래프(Undirected Weighted Graph)를 사용하는데요, 무방향 가중치 그래프와 인접행렬을 직관적으로 비교한 그림은 아래와 같습니다(출처).

원데이터에서 인접행렬을 만들 때는 보통 아래와 같이 가우시안 커널(Gaussian kernel)을 많이 사용합니다. 예컨대 벡터로 표현된 하나의 문서를 노드(node)라고 둘 때, 문서 간 거리가 멀리 떨어져 있을수록(=유사하지 않을수록) 그 가중치는 줄어듭니다. 아울러 가우시안 커널로 만들어진 인접행렬은 대칭행렬입니다.

[{ W }{ ij }=exp\left( -\frac { d{ ({ x }{ i },{ x }_{ j }) }^{ 2 } }{ 2\sigma^{2} } \right)]

문서를 그래프로 표현하는 방법에 대해서는 이곳을, 가우시안 커널로 인접행렬을 만드는 방법에 대해서는 이곳을 참고하시면 좋을 것 같습니다.

그래프 구축

fully connected graph란 모든 노드가 엣지로 연결돼 있는 그래프를 가리킵니다. ε-neighborhood graph란 거리가 $ε$보다 가까운 엣지들만 살리고 나머지 엣지는 끊어버린 그래프입니다. k-nearest neighbor graph는 각 노드 주변 $k$개 이웃들만 엣지로 연결하고 나머지 엣지는 끊어놓은 그래프입니다.

ε-neighborhood graph는 노드의 밀도가 높은 지역에선 엣지가 지나치게 많이 발생하고, 밀도가 낮은 지역에선 엣지가 하나도 없는 노드가 생길 수 있습니다. k-nearest neighbor graph는 끊기는 노드가 발생하진 않지만, 군집이 극단적으로 멀리 떨어져 있는 경우 군집과 군집 사이는 연결되지 않는 경우가 발생할 수 있습니다.

일반적으로 그래프를 구축할 때는 ε-neighborhood graph를 먼저 구축한 뒤 k-nearest neighbor graph를 적용해 엣지가 전혀 없는 노드도 연결해주는 방식을 씁니다. 그럼에도 불구하고 군집 사이가 너무 멀어서 연결 안되는 경우가 발생할 수 있는데 이럴 때는 minimum spanning tree 방법도 자주 사용됩니다.

그래프 컷 지표

그래프 컷은 그래프를 특정 기준에 의해 두 개 이상의 부그래프(subgraph)로 나누는 것입니다. 이 부그래프가 바로 Spectral Clustering 기법의 학습 결과물인 군집이 됩니다. 아래와 같은 무방향 가중치 그래프가 주어졌다고 합시다.

$Cut(A,B)$는 부그래프 $A$에서 $B$로 향하는 엣지들의 가중치 합입니다. 아래 식과 같습니다.

[Cut(A,B)=\sum { i\in A,j\in B }^{ }{ { w }{ ij } } =0.3]

$Cut(A,A)$는 $A$에서 $A$로 향하는 엣지들의, $Cut(B,B)$는 $B$에서 $B$로 향하는 엣지들의 가중치 합입니다.

[Cut(A,A)=\sum { i\in A,j\in A }^{ }{ { w }{ ij } } =2.2]

[Cut(B,B)=\sum { i\in A,j\in B }^{ }{ { w }{ ij } } =2.3]

$Vol(A)$는 $A$에 속한 노드에 연결된 엣지들의 모든 가중치 합입니다. 위 그림에서 1번 노드에 연결된 엣지 세 개(0.8+0.6+0.1), 2번 노드에 연결된 엣지 두 개(0.8+0.8), 3번 노드에 연결된 엣지 세 개(0.8+0.6+0.2)를 모두 더한 값입니다. 따라서 $Vol(A)$는 $Cut(A,A)$의 두 배에 $Cut(A,B)$를 더해준 값과 같습니다. 이는 $Vol(B)$도 마찬가지입니다.

[Vol(A)=\sum { i\in A }^{ }{ \sum _{ j }^{ }{ { w }{ ij } } } =4.7]

[Vol(B)=\sum { i\in B }^{ }{ \sum _{ j }^{ }{ { w }{ ij } } } =4.9]

Minimum Cut method

이 기법은 원그래프를 $A$와 $B$라는 부그래프로 나눌 때 끊어지는 엣지들의 가중치가 최소가 되도록 합니다. 목적함수는 아래와 같습니다.

[MinCut(A,B)=\min { \frac { 1 }{ 4 } { q }^{ T }(D-W)q }]

여기에서 대각행렬 $D$와 벡터 $q$는 아래와 같습니다.

[{ D }{ ii }=\sum _{ j }^{ }{ { w }{ ij } } \quad ,\quad { D }{ ij }=0\quad if\quad i\neq j\ { q }{ i }=\begin{Bmatrix} 1\quad if\quad i\in A \ -1\quad if\quad i\in B \end{Bmatrix}]

$MinCut(A,B)$의 제약조건은 다음과 같습니다. 벡터 ​$q$의 각 요소를 제곱해 모두 더한 ​$q^Tq$가 그래프 전체의 노드수 ​$V$와 일치해야 한다는 겁니다. 벡터 ​$q$의 각 요소는 해당 노드가 ​$A$에 속해 있으면 1, ​$B$에 속해 있으면 -1의 값을 가지기 때문입니다. \({ q }^{ T }q=\left| V \right|\)

이해를 돕기 위해 예를 들어보겠습니다. 아래와 같이 무방향 가중치 그래프가 주어졌고, 붉은색 선을 기준으로 부그래프가 두 개로 나뉜다고 합시다. 노드1와 노드2를 부그래프 $A$, 노드3와 노드4를 부그래프 $B$로 두겠습니다.

가중치 행렬 $W$는 아래와 같습니다.

[W=\begin{bmatrix} { w }{ 11 } & { w }{ 12 } & 0 & { w }{ 14 } \ { w }{ 21 } & { w }{ 22 } & { w }{ 23 } & 0 \ 0 & { w }{ 32 } & { w }{ 33 } & { w }{ 34 } \ { w }{ 41 } & 0 & { w }{ 43 } & { w }{ 44 } \end{bmatrix}]

대각행렬 $D$는 아래와 같습니다.

[D=\begin{bmatrix} { w }{ 11 }+{ w }{ 12 }+{ w }{ 14 } & 0 & 0 & 0 \ 0 & { w }{ 21 }+{ w }{ 22 }+{ w }{ 23 } & 0 & 0 \ 0 & 0 & { w }{ 32 }+{ w }{ 33 }+{ w }{ 34 } & 0 \ 0 & 0 & 0 & { w }{ 41 }+{ w }{ 43 }+{ w }{ 44 } \end{bmatrix}]

$(D-W)q$는 아래와 같습니다.

[\begin{align} (D-W)q&=\begin{bmatrix} { w }_{ 12 }+{ w }_{ 14 } & -{ w }_{ 12 } & 0 & -{ w }_{ 14 } \ -{ w }_{ 21 } & { w }_{ 21 }+{ w }_{ 23 } & { -w }_{ 23 } & 0 \ 0 & -{ w }_{ 32 } & { w }_{ 32 }+{ w }_{ 34 } & -{ w }_{ 34 } \ -{ w }_{ 41 } & 0 & -{ w }_{ 43 } & { w }_{ 41 }+{ w }_{ 43 } \end{bmatrix}\begin{bmatrix} 1 \ 1 \ -1 \ -1 \end{bmatrix}\ &=\begin{bmatrix} 2{ w }_{ 14 } \ 2{ w }_{ 23 } \ -2{ w }_{ 32 } \ -2{ w }_{ 41 } \end{bmatrix} \end{align}]

위 식을 정리하면 아래와 같습니다.

[\frac { 1 }{ 4 } { q }^{ T }(D-W)q=\frac { 1 }{ 4 } \begin{bmatrix} 1 & 1 & -1 & -1 \end{bmatrix}\begin{bmatrix} 2{ w }{ 14 } \ 2{ w }{ 23 } \ -2{ w }{ 32 } \ -2{ w }{ 41 } \end{bmatrix}={ w }{ 14 }+{ w }{ 23 }]

최종적으로 도출된 $w_{14}$와 $w_{23}$은 원그래프에서 두 개 부그래프로 나눠질 때 끊어지는 가중치들입니다. 다시 말해 목적함수에 정의된 $1/4q^T(D-W)q$를 최소화한다는 것은 끊어지는 가중치들을 최소로 하겠다는 의미가 되는 것입니다.

목적함수 $1/4q^T(D-W)q$에 제약조건($q^Tq=V$)을 반영해 라그랑지안 문제로 변환하고, 식을 미지수 $q$로 미분해서 0으로 놓으면 아래와 같이 정리할 수 있습니다. ($q$가 미지수가 되는 이유는 각 노드가 $A$에 속하는지, $B$가 속하는지 정보가 이 벡터에 들어있기 때문입니다)

[\begin{align} \frac { \partial C }{ \partial q } &=\frac { \partial { \frac { 1 }{ 4 } { q }^{ T }(D-W)q-\lambda ({ q }^{ t }q-\left| V \right| )} }{ \partial q } \ &=\frac { 1 }{ 2 } (D-W)q-\lambda q=0\ &(D-W)q=\lambda q \end{align}]

최종 도출된 식을 보면 우리가 찾고자 하는 $q$는 $D-W$ 행렬의 고유벡터(eigenvector)임을 알 수 있습니다. 다만 최소값을 찾는 것이 목적이므로 두번째로 작은 고유값에 해당하는 고유벡터를 취합니다(제일 작은 고유값은 0이기 때문에 무의미한 해입니다). 이 벡터의 각 요소 가운데 양수인 위치의 노드를 부그래프 $A$, 음수인 노드를 $B$로 할당하게 됩니다.

Minimum Cut method 적용 예시

예시 그림의 그래프를 인접행렬로 나타내면 다음과 같습니다.

이로부터 $D-W$를 구합니다. 이를 고유분해한 결과가 아래와 같습니다. $Λ$는 $D-W$의 고유값들로 이뤄진 벡터, $V$는 열벡터가 고유벡터인 행렬입니다.

[{ \Lambda }^{ T }=\begin{bmatrix} 0.0 & 0.3 & 2.2 & 2.3 & 2.5 & 3.0 \end{bmatrix}\ X=\begin{bmatrix} 0.4 & 0.2 & 0.1 & 0.4 & -0.2 & -0.9 \ 0.4 & 0.2 & 0.1 & 0.0 & 0.4 & 0.3 \ 0.4 & 0.2 & -0.2 & 0.0 & -0.2 & 0.6 \ 0.4 & -0.4 & 0.9 & 0.2 & -0.4 & -0.6 \ 0.4 & -0.7 & -0.4 & -0.8 & -0.6 & -0.2 \ 0.4 & -0.7 & -0.2 & 0.5 & 0.8 & 0.9 \end{bmatrix}]

그렇다면 우리가 찾고자 하는 미지수 $q$는 $V$의 두번째 열이 됩니다. 여기에서 양수인 노드1 노드2 노드3은 부그래프 $A$, 음수인 노드4 노드5 노드6은 $B$에 할당하면 Spectral Clustering 절차가 끝납니다.

[{ q }^{ T }=\begin{bmatrix} 0.2 & 0.2 & 0.2 & -0.4 & -0.7 & -0.7 \end{bmatrix}]

다른 방법들

부그래프의 크기를 비슷하게 맞추는 방향으로 자르는 Ratio Cut, 엣지 가중치 합을 비슷하게 하여 부그래프를 자르는 Minmax Cut 기법이 있습니다. 식은 아래와 같습니다. (여기에서 $A$의 절대값 은 $A$의 노드 수를 뜻합니다)

[MinMaxCut(A,B)=\min { { Cut(A,B)(\frac { 1 }{ Cut(A,A) } +\frac { 1 }{ Cut(B,B) } )} }]

Recursive bi-partitioning

지금까지 설명드린 Spectral Clustering은 원그래프를 두 개의 부그래프로 나누는 기법이었습니다. 그렇다면 여러 개 부그래프로 군집화하려면 어떻게 해야할까요? 지금까지 설명드렸던 기법을 반복적으로 수행하면 됩니다.