이번 글에서는 TF-IDF를 설명한 지난 글에 이어 단어에 대한 가중치를 부여하는 방법론 10가지에 대해 다뤄보려고 합니다. 이 가중치들은 문서의 특징을 추출하거나 분류하는 데 쓰입니다. 이번 글 역시 고려대 강필성 교수님 강의를 참고로 했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

단어 가중치 계산 목적

리뷰(Document) 10개, 단어(Term) 10개로 구성된 말뭉치가 주어졌다고 가정해 봅시다. binary Term-Document Matrix는 아래와 같습니다. 여기에서 binary라는 건 특정 단어가 한번 쓰였든 열번 쓰였든 해당 리뷰 안에 등장하면 1, 한번도 나타난 적이 없으면 0으로 표시했다는 뜻입니다. 표 맨 밑에 범주(class) 정보가 있습니다. 첫번째 리뷰(D1)부터 여섯번째 리뷰(D6)까지는 긍정(Positive)적인 문서임을 확인할 수 있네요. 나머지 리뷰는 부정(Negative)인 것 또한 확인 가능합니다.

우리의 목적은 단어 정보만으로 범주(긍정, 부정)를 예측하는 것입니다. 다시 말해 문서를 긍정/부정으로 분류할 때 어떤 단어가 중요한 역할을 하는지 알고 싶은거죠. 딱 보기엔 Term1과 Term2가 중요해 보이네요. Term1은 긍정적인 문서에서만 쓰인 단어이고, Term2는 부정적인 문서에만 나타났거든요. 우리가 범주 정보가 없는 새로운 리뷰를 분류해야 한다면, 우선 해당 리뷰에 Term1이나 Term2가 쓰였는지부터 확인해보면 되겠네요. 반면 모든 리뷰에 등장한 Term3는 같은 이유로 문서 분류에 별 도움이 되지 않을 것 같습니다.

이번 글에서 다루는 단어 가중치 계산 방법 10가지는 이처럼 특정 단어가 문서 분류라는 과업에 얼마나 중요한 역할을 하는지 수치화하는 걸 목적으로 합니다.

Document Frequency (DF)

Document Frequency(DF)는 $w$라는 단어가 몇 개의 문서에 등장했는지 빈도를 나타냅니다. 아래와 같이 정의됩니다.

[DF(w)={ N }_{ D }(w)]

Accuracy(Acc)

Accuracy(Acc)는 $w$라는 단어가 긍정적인 문서에 나타난 빈도, $w$가 부정적인 문서에 나타낸 빈도 간 차이입니다.

[Acc(w)=N(Pos,w)-N(Neg,w)]

Accuracy Ratio(AccR)

$N(Pos,w)/N(Pos)$는 긍정적인 문서가 주어졌을 때 $w$라는 단어가 등장할 조건부 확률입니다. Accuracy Ratio(AccR)은 긍정과 부정 범주의 조건부확률 차이에 절대값을 취한 값입니다.

Probability Ratio (PR)

Probability Ratio(PR)은 AccR와 유사하나 긍/부정 조건부확률 차이의 절대값 대신 두 값 사이의 비율을 계산했습니다.

[PR(w)=\frac { N(Pos,w) }{ N(Pos) } /\frac { N(Neg,w) }{ N(Neg) }]

이상 네 지표를 예시 말뭉치에 적용한 결과는 아래와 같습니다. 값이 높을 수록 해당 단어가 긍/부정 범주 분류에 중요하다는 뜻입니다. PR의 경우 $w$가 부정 범주에 한번도 쓰이지 않았을 경우 PR 식의 분모가 0이 돼 무한대값이 나오는 걸 확인할 수 있습니다.

Odds ratio (OddR)

승산(odds)이란 임의의 사건 $A$가 발생하지 않을 확률 대비 일어날 확률 사이의 비율입니다. $P(A)/(1-P(A))$로 정의됩니다. 그렇다면 ‘긍정적인 문서에 $w$가 등장’한 경우를 사건 $A$라고 정의한다면 $A$에 대한 승산은 아래와 같이 쓸 수 있습니다.

[\begin{align} Odd(A)&=\frac { P(A) }{ 1-P(A) } \ &=\frac { P(w|Pos) }{ 1-P(w|Pos) } \ &=\frac { \frac { N(Pos,w) }{ N(Pos) } }{ 1-\frac { N(Pos,w) }{ N(Pos) } } \ &=\frac { N(Pos,w) }{ N(Pos)-N(Pos,w) } \ &=\frac { N(Pos,w) }{ N(Pos,\bar { w } ) } \end{align}]

위 식 마지막의 분모는 $w$가 포함되지 않은 긍정적인 문서의 개수를 뜻합니다. 한편 사건 $B$를 ‘부정적인 문서에 $w$가 등장’한 경우로 정의하면 사건 B의 승산은 아래와 같이 쓸 수 있습니다. 아래식 마지막의 분모 역시 $w$가 없는 부정적인 문서의 개수입니다.

[Odd(B)=\frac { N(Neg,w) }{ N(Neg,\bar { w } ) }]

사건 $A$의 승산과 사건 $B$의 승산은 사이의 비율, 즉 Odds ratio(OddR)은 아래와 같이 쓸 수 있습니다. OddR이 클수록 긍정 범주 판별에 유용한 단어라는 의미를 지닙니다.

[\begin{align} OddR(w)&=\frac { Odd(A) }{ Odd(B) } \ &=\frac { \frac { N(Pos,w) }{ N(Pos,\bar { w } ) } }{ \frac { N(Neg,w) }{ N(Neg,\bar { w } ) } } \ &=\frac { N(Pos,w) }{ N(Neg,w) } \times \frac { N(Neg,\bar { w } ) }{ N(Pos,\bar { w } ) } \end{align}]

Odds ratio Numerator (OddN)

계산 효율성을 목적으로 OddR에서 분자 부분만 떼어낸 식입니다.

[OddN(w)=N(Pos,W)\times N(Neg,\bar { w } )]

F1-Measure

임의의 단어 $w$에 대해 말뭉치로부터 아래와 같은 표를 만들 수 있습니다. 아래 표에서 ~$w$는 $w$가 포함되지 않은 문서라는 뜻입니다.

위 표를 머신러닝(Machine Learining) 모델의 성능 측정을 위한 혼동행렬(confusion matrix)처럼 생각할 경우 재현율(Recall)은 $a/(a+b)$, 정밀도(precision)는 $a/(a+c)$입니다. F1은 이 둘의 조화평균인데요. 임의의 단어 $w$에 대한 F1 지표는 아래와 같습니다. F1 역시 클수록 긍정 범주 판별에 유용한 단어라는 의미를 가집니다.

[\begin{align} Recall(w)&=\frac { N(Pos,w) }{ N(Pos,w)+N(Pos,\bar { w } ) } \ Precision(w)&=\frac { N(Pos,w) }{ N(Pos,w)+N(Neg,w) } \F1(w)&=\frac { 2\times Recall(w)\times Precision(w) }{ Recall(w)+Precision(w) } \ &=\frac { 2\times N(Pos,w) }{ N(Pos)+N(w) } \end{align}]

이상 세 가지 지표를 예시 말뭉치에 적용한 결과는 아래 표와 같습니다. OddR, OddN, F1 모두 긍정 범주 판별에 유의미한 단어들을 골라내고 있지만, 부정 범주 판별에 쓸모 있는 Term2에 대해선 아무런 스코어를 내고 있지 않다는 점을 확인할 수 있습니다. 다시 말해 세 지표는 긍정 범주 판별에 의미있는 단어들만을 골라냅니다.

Information Gain

정보이론에서 엔트로피(Entropy)란 불확실성 내지 혼잡도의 척도로 쓰입니다. 만약 어떤 데이터의 범주는 두 개인데, 전체 관측치의 절반이 한 범주이고 나머지 절반이 다른 범주라면 엔트로피는 최대값(1)을 가집니다. 반대로 모든 관측치가 하나의 범주로 구성돼 있다면 엔트로피는 최소값(0)이 됩니다. 정보이득(information gain)이란 특정 조건과 비교한 엔트로피 간 차이를 의미합니다. 이와 관련해 위 표를 다시 볼까요?

우리의 목적은 $w$가 문서의 극성을 분류하는 데 얼마나 중요한지를 따지는 것입니다. 그렇다면 이렇게 생각해보면 어떨까요? $w$가 쓰인 문서의 엔트로피(혼잡도)와 $w$가 쓰이지 않은 문서의 엔트로피를 비교해보는거죠. 위 표 기준으로는 $(a, c)$와 $(b,d)$의 엔트로피를 구해보는 것입니다. 여기에서 만약 $(b,d)$로 계산한 엔트로피가 $(a,c)$보다 크다면, $w$가 긍정, 부정 범주의 문서를 가르는 데 유의미하다는 결론을 내게 되는 것입니다. 이를 식으로 쓰면 아래와 같습니다.

[\begin{align} Entropy(absent\quad w)&=\sum _{ c\in { Pos,Neg} }^{ }{ -P(C)\times \log { (P(C)) } } \ Entropy(given\quad w)&=P(w)\left[ \sum _{ c\in { Pos,Neg} }^{ }{ -P(C|w)\times \log { (P(C|w)) } } \right] \ &+P(\bar { w } )\left[ \sum _{ c\in { Pos,Neg} }^{ }{ -P(C|\bar { w } )\times \log { (P(C|\bar { w } )) } } \right] \\ IG(w)=Entropy(absent\quad w)&-Entropy(given\quad w) \end{align}]

Chi-squared Statistic

말뭉치(리뷰 20건)가 아래와 같이 구성돼 있다고 합니다.

우리의 관심은 최고라는 단어가 극성을 나누는 데 의미가 있는지 여부입니다. 이를 통계학의 귀무가설(null hypothesis)과 대립가설(alternative hypothesis)로 표현하면 아래와 같습니다.

$H_0$ : ‘최고’라는 단어 등장 여부와 긍,부정 극성은 서로 독립(independent)이다.

$H_1$ : $H_0$가 참이 아니다.

$H_0$가 참이라면 각 요소의 비율은 아래 표가 될 것입니다. 통계적 독립의 정의에 의해 각 행과 열의 주변확률(marginal probability)을 서로 곱한 값이 각 요소의 결합확률(joint probability)가 되기 때문입니다.

위 표에 전체 문서 수 20을 모두 곱하면 $H_0$ 하에서의 기대값(expected value)이 됩니다. 아래 표와 같습니다.

이렇게 나온 기대값($e_i$)과 실제 관측치($o_i$)를 아래와 같이 계산한 통계량(statistic)은 자유도 $(c-1)(r-1)$인 카이제곱분포(chi-squared distribution)을 따른다고 합니다. 여기에서 $c$는 위 표의 total 열을 제외한 열(column)의 개수, $r$은 total 행을 제외한 행(row)의 개수입니다. 예시 기준으로는 자유도가 1이 됩니다.

[\sum { i=1 }^{ 4 }{ \frac { { ({ o }{ i }-{ e }{ i }) }^{ 2 } }{ { e }{ i } } } \sim { \chi }_{ 1 }^{ 2 }]

여기에서 통계량이 커질 수록 $H_0$를 기각할 가능성 역시 커지게 된다고 합니다. 바꿔 말하면 통계량이 클수록 ‘최고’라는 단어가 긍정, 부정 극성 분리에 중요한 term이라는 이야기입니다. 카이제곱 통계량을 지금까지 우리가 논의한 단어 가중치 부여 방식으로 일반화해서 식을 쓰면 아래와 같습니다.

[{ \chi }^{ 2 }(w)=\frac { N\times { \left[ P(Pos,w)\times P(Neg,\bar { w } )-P(Neg,w)\times P(Pos,\bar { w } ) \right] }^{ 2 } }{ P(w)\times P(\bar { w } )\times P(Pos)\times P(Neg) }]

Bi-Normal Separation (BNS)

Bi-Normal Separation은 아래와 같은 식으로 정의됩니다. 여기에서 F는 정규분포(Normal distribution)의 누적분포함수(cumulative distribution function)입니다.

세 가지 지표를 첫 예시에 맞춰 적용하면 아래 표와 같습니다.

마치며

이상 10가지 방식을 요약하면 아래 표와 같습니다. 각 지표마다 특성이 다르고 일장일단이 있으므로 목적에 맞게 적절히 선택해서 쓰면 좋을 것 같습니다. 의견이나 질문 있으시면 언제든지 이메일이나 댓글로 알려주시기 바랍니다. 여기까지 읽어주셔서 감사합니다.

이번 글에서는 단어(word)에 대해 살펴보겠습니다. 이번 글 역시 이선웅 경희대 교수님 강의와 최형용 이화여대 교수님 저서를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

단어의 정의

19세기 이르러서야 그 개념이 정립된 형태소(morpheme)에 비해 단어는 꽤 오래 전부터 논의된 개념입니다. 형태소는 짧은 역사를 가진 데 반해 그 정의가 의미를 가지는 최소 단위(the minimal unit of meaning)로 깔끔하게 정리되는 편입니다. 하지만 단어는 오랜 연원을 가지고 있지만 지금도 쉽사리 정의내릴 수 없는 언어 단위라고 합니다. 임홍빈 & 장소원(1995)은 지금까지 제시된 단어에 대한 정의를 아래와 같이 세 가지로 정리하고 그 각각의 문제점에 대해서도 언급하고 있습니다.

가. 단일한 의미를 가지는 음(音) 결합체

나. 최소의 자립 형식

다. 휴지(休止)가 개입할 수 없고 내부가 분리되지 않는 형식

가의 경우 ‘애인(愛人)’과 ‘사랑하는 사람’에서 볼 수 있듯 같은 의미를 가지는 형식이 하나는 단어로, 다른 하나는 단어보다 큰 것으로 판명된다는 점에서 문제가 됩니다. 나의 경우 ‘책상’과 같은 예에서 ‘책’과 ‘상’이라는 더 작은 자립 형식이 분석되어 나온다는 점에서 논란이 될 수 있습니다. 다는 휴지가 개입되지 않음에도 하나의 단어가 아닌 ‘철수가’ 같은 예나 단어이면서도 ‘깨끗은 하다’처럼 한 단어 내부가 분리되는 경우가 문제라는 점입니다.

음운론적 단어와 문법적 단어

단어에 대한 정의가 이처럼 어려운 이유는 우리가 일반적으로 단어라고 부르는 대상에 너무 많은 개념들이 포함되어 있기 때문입니다. 이와 관련해 Dixon & Aikhenvald(2002)는 단어라는 개념은 아래와 같이 크게 음운론적 단어와 문법적 단어로 구성돼 있다고 주장했습니다. 박진호(1994) 역시 한국어의 단어 개념을 음운론적 단어와 통사원자(syntactic atom;문법적 단어)로 구분해야 한다고 밝혔습니다.

음운론적 단어란 하나의 호흡단위로써의 단어 개념입니다. 모국어 화자들이 자연스럽게 끊어 읽는 단위가 바로 음운론적 단어라는 것입니다. 이 때문에 음운론적 단어는 대개 어절과 일치합니다. 문법적 단어란 통사론에서 말하는 기초단위들을 뜻합니다. 박진호(1994)에 따르면 명사, 동사, 관형사, 부사, 격조사, 문말어미, 보조사, 선문말어미, 접속사, 감탄사가 여기에 해당합니다. 둘을 구분하면 예컨대 아래와 같습니다.

철수가 밥을 빨리 먹었다.

단어의 존재 양상

Dixon & Aikhenvald(2002)은 이를 토대로 단어의 종류를 아래 네 가지로 나눌 수 있다고 보았습니다.

가. 음운론적 단어와 문법적 단어가 일치하는 경우

나. 음운론적 단어가 두 개 이상의 문법적 단어로 이뤄진 경우

다. 문법적 단어가 두 개 이상의 음운론적 단어로 이뤄진 경우

라. 문법적 단어와 음운론적 단어 사이에 보다 복잡한 관계가 존재하는 경우

‘가’의 경우 분석에 큰 어려움이 없습니다. ‘나’~’라’가 어려운 문제인데요. 대부분의 합성어는 ‘다’에 해당하는 사례가 됩니다. 합성어는 별개로는 음운론적 단어인 것들이 모여 하나의 문법적 단어를 이루는 경우라 할 수 있기 대문입니다. 예컨대 ‘책상’이 여기에 해당하는데요, ‘책상’이라는 명사(문법적 단어)는 ‘책’과 ‘상’이라는 두 개의 음운론적 단어가 모여 만들어진 집합체입니다.

‘먹을 것’과 ‘먹어 보다’ 같은 사례는 ‘나’에 해당합니다. 둘 모두 중간에 끊어 읽는 경우가 많지 않기 때문에 각각 하나의 음운론적 단어라고 볼 수 있습니다. 하지만 동사의 활용형에 의존명사와 보조용언이 각각 붙어있으므로 ‘먹을 것’, ‘먹어 보다’ 모두 두 개의 문법적 단어로 구성되어 있는 셈입니다. 이처럼 단어 개념은 복잡 오묘하기 때문에 분석에 주의를 기울여야 합니다.

이번 포스팅에서는 미국 스탠포드대학에서 2014년 개발한 워드 임베딩 방법론인 GloVe에 대해 알아보도록 하겠습니다. 이번 글은 고려대 강필성 교수님 강의를 참고로 했는데요. 저도 완벽히 이해한 건 아니어서 무림 고수분들의 많은 지적 환영합니다. 그럼 시작하겠습니다.

GloVe의 문제의식

GloVe는 2013년 구글에서 개발한 Word2Vec의 단점을 파고 들었습니다. Word2Vec은 중심단어로 주변단어를, 주변단어로 중심단어를 예측하는 과정에서 단어를 벡터로 임베딩하는 방법론인데요. 임베딩된 단어의 내적(inner product)이 코사인 유사도가 되도록 합니다. 또 GloVe 연구팀은 단어-문맥행렬에 특이값분해(SVD)를 실시해 데이터 차원을 효과적으로 축소하는 한편 노이즈 등을 줄여 내재적인 의미를 이끌어내는 잠재의미분석(LSA)의 단점 또한 언급했습니다. Word2Vec에 관해 좀 더 살펴보시려면 이곳과 이곳을, LSA에 대한 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

어쨌든 GloVe 연구팀은 LSA와 Word2Vec에 관해 다음과 같이 각각 비판하였습니다.

While methods like LSA efficiently leverage statistical information, they do relatively poorly on the word analogy task, indicating a sub-optimal vector space structure. Methods like skip-gram may do better on the analogy ask, but they poorly utilize the statistics of the corpus since they train on separate local context windows instead of on global co-occurrence counts.

위 내용을 제 방식대로 해석하자면 LSA는 말뭉치 전체의 통계적인 정보를 모두 활용하지만, LSA 결과물을 가지고 단어/문서 간 유사도를 측정하기는 어려운 단점을 지닙니다. 반대로 Word2Vec(Skip-Gram)은 저차원 벡터공간에 임베딩된 단어벡터 사이의 유사도를 측정하는 데는 LSA에 비해 좋은 성능을 가지지만, 사용자가 지정한 윈도우(주변 단어 몇개만 볼지) 내에서만 학습/분석이 이뤄지기 때문에 말뭉치 전체의 공기정보(co-occurrence)는 반영되기 어려운 단점을 지닙니다.

이 때문에 GloVe 연구팀은 임베딩된 두 단어벡터의 내적이 말뭉치 전체에서의 동시 등장확률 로그값이 되도록 목적함수를 정의했습니다. (their dot product equals the logarithm of the words’ probability of co-occurrence) “임베딩된 단어벡터 간 유사도 측정을 수월하게 하면서도 말뭉치 전체의 통계 정보를 좀 더 잘 반영해보자”가 GloVe가 지향하는 핵심 목표라 말할 수 있을 것 같습니다.

GloVe의 목적함수

우선 연구팀이 직접 든 예시를 먼저 설명해볼게요. 아래 표를 볼까요? 아래 표는 학습 말뭉치에서 동시에 같이 등장한 단어의 빈도를 각각 세어서 전체 말뭉치의 단어 개수로 나눠준 동시등장확률(the words’ probability of co-occurrence)입니다.

위 표를 보면 ice라는 단어가 주어졌을 때 solid가 등장할 확률은 steam이 주어졌을 때 solid가 나타날 확률보다 높습니다. ‘단단한’이라는 뜻을 가진 solid는 steam보다 ice와 관련성이 높기 때문에 직관적으로 당연한 결과입니다. 그러면 $P(solid$|$ice)/P(solid$|$steam)$은 1보다 훨씬 큰 값(8.9)을 가집니다.

반대로 $P(gas$|$ice)/P(gas$|$steam)$은 1보다 훨씬 작은 값(0.0085)이네요. ice, steam과 관련성이 높거나 별로 없는 water와 fashion은 모두 1 안팎의 값이 나옵니다.

GloVe 연구팀은 특정 단어 $k$가 주어졌을 때 임베딩된 두 단어벡터의 내적이 두 단어의 동시등장확률 간 비율이 되게끔 임베딩하려고 했습니다. 예컨대 solid라는 단어가 주어졌을 때 ice와 steam 벡터 사이의 내적값이 8.9가 되도록 하자는 것이지요. 마찬가지로 gas가 주어졌을 때 ice x steam은 0.0085가 되게끔 합니다.

그런데 말뭉치 전체를 학습시키다보면 ice나 steam이 $k$가 될 수 있고, solid/gas/water/fashion 역시 위 표 기준 ice나 steam 자리에 얼마든지 들어갈 수 있습니다. 이렇게 단어 상호 간 비율 정보를 말뭉치 전체를 놓고 한꺼번에 반영하게 되면 좀 더 정확한 단어 임베딩이 될 것이라고 생각한 게 GloVe 연구팀의 아이디어인 것 같습니다.

그럼 지금까지 설명드렸던 목표를 달성하기 위한 목적함수를 살펴봐야겠네요. GloVe 연구팀은 우선 아래와 같은 식을 정의하고, 이 식을 만족하는 임의의 함수 $F$를 찾고자 했습니다.

[F({ w }{ i },{ w }{ j },\tilde { { w }{ k } } )=\frac { { P }{ ik } }{ { P }_{ jk } }]

GloVe 연구팀은 $P_{ik}$를 $P(k$|$i)$로 정의했습니다. $i$번째 단어 주변(윈도우 크기는 사용자 지정)에 $k$번째 단어가 등장할 조건부확률이라는 뜻입니다. 바꿔 말하면 전체 말뭉치에서 ‘사용자가 미리 정한 윈도우 내에서 $i$번째 단어와 $k$라는 단어가 동시에 등장한 빈도수($X_{ik}$)’를 ‘$X_i$(=$Σ_k{X_{ik}}$)’로 나눠준 값입니다. 위 표 기준으로 예를 들면 $P(solid$|$ice)$ 정도의 의미가 되겠네요.

그렇다면 $P_{ik}/P_{jk}$는 어떤 의미일까요? 마찬가지로 표를 기준으로 설명해드리면 $P(solid$|$ice)/P(solid$|$steam)=8.9$가 될 겁니다. 그럼 위 식을 이렇게 예시로 풀 수 있겠네요. $d$차원 벡터공간에 임베딩된 ice, steam, solid 벡터를 임의의 함수 $F$에 넣으면 8.9를 반환하는 $F$를 찾자는 겁니다.

GloVe 연구팀은 위 식을 아래와 같이 변형하였습니다. 아래 식의 변형 과정을 제 방식대로 해석하면 이렇습니다. 우선 $F$ 안에 집어넣을 $w_i$, $w_j$, $w_k$ 간에 관계를 따져보기 위해 $w_i$와 $w_j$를 뺀 벡터에 $w_k$를 내적합니다. GloVe 연구팀은 임베딩된 두 단어벡터의 내적은 전체 말뭉치의 동시등장확률이 되도록 하려는 목적이 있었으므로 $P_{ik}$를 $F(W_i^TW_k)$로 정의했습니다.

[\begin{align} F({ w }_{ i }-{ w }_{ j },\tilde { { w }_{ k } } )&=\frac { { P }_{ ik } }{ { P }_{ jk } } \ F({ { ({ w }_{ i }-{ w }_{ j }) }^{ T } }\tilde { { w }_{ k } } )&=\frac { { P }_{ ik } }{ { P }_{ jk } } \ F({ { ({ w }_{ i }-{ w }_{ j }) }^{ T } }\tilde { { w }_{ k } } )&=\frac { F({ w }_{ i }^{ T }\tilde { { w }_{ k } } ) }{ F({ w }_{ j }^{ T }\tilde { { w }_{ k } } ) }
F({ w }_{ i }^{ T }\tilde { { w }_{ k } } -{ w }_{ j }^{ T }\tilde { { w }_{ k } } )&=\frac { F({ w }_{ i }^{ T }\tilde { { w }_{ k } } ) }{ F({ w }_{ j }^{ T }\tilde { { w }_{ k } } ) } \end{align}]

그런데 GloVe 연구팀에 따르면 여기까지 도출된 $F$는 다음 세 가지 조건을 만족해야 합니다. 우선 $w_i$와 $w_k$를 서로 바꾸어도 식이 같은 값을 반환해야 합니다. 이미 설명드린 바와 같이 중심 단어 $w_k$는 얼마든지 $w_i$나 $w_j$가 될 수 있기 때문입니다. 또한 말뭉치 전체에서 구한 co-occurrence matrix $X$는 대칭행렬(symmetric matrix)이므로 함수 $F$는 이러한 성질을 포함해야 합니다. 마지막으로 homomorphism 조건을 만족해야 한다고 합니다. 이를 수식으로 쓰면 아래와 같습니다.

[{ w }{ i }\longleftrightarrow \tilde { { w }{ k } } \ X{ \longleftrightarrow X }^{ T }\ F(X-Y)=\frac { F(X) }{ F(Y) }]

이러한 조건을 만족하는 함수는 지수함수이기 때문에 $F$를 $exp$로 치환하고 식을 정리하면 아래와 같습니다.

[\begin{align} exp({ w }_{ i }^{ T }\tilde { { w }_{ k } } -{ w }_{ j }^{ T }\tilde { { w }_{ k } } )&=\frac { exp({ w }_{ i }^{ T }\tilde { { w }_{ k } } ) }{ exp({ w }_{ j }^{ T }\tilde { { w }_{ k } } ) } \ { w }_{ i }^{ T }\tilde { { w }_{ k } } &=\log { { P }_{ ik } } =\log { X_{ ik }-\log { X_{ i } } }
\end{align}]

그런데 여기에서 문제가 하나 있습니다. $w_i$와 $w_k$를 서로 바꾸어도 식이 성립해야 한다고 했는데, 정말 이렇게 되려면 위 식 마지막의 $log(P_{ik})$가 $log(P_{ki})$와 같아야 하는데요. 사실 이를 풀어쓰면 각각 $log(X_{ik}) - log(X_i)$, $log(X_{ki}) - log(X_k)$가 되어서 서로 달라지게 됩니다. 이 때문에 GloVe 연구팀은 $log(X_i)$ 이 부분을 아래와 같이 상수항($b_i$, $b_k$)으로 처리해 이 조건을 만족하도록 식을 한번 더 변환하였습니다.

[\begin{align} { w }_{ i }^{ T }\tilde { { w }_{ k } } &=\log { X_{ ik }-{ b }_{ i }-\tilde { { b }_{ k } } } \ { w }_{ i }^{ T }\tilde { { w }_{ k } } +{ b }_{ i }+\tilde { { b }_{ k } }& =\log { X_{ ik }} \end{align}]

자, 이제 거의 다 왔습니다. 위 식에서 미지수는 좌변이고, 우변의 $log(X_{ik})$는 우리가 이미 알고 있는 값입니다. 특정 윈도우 사이즈를 두고 말뭉치 전체에서 단어별 등장 빈도를 구한 co-occurrence matrix에 로그를 취해준 행렬이기 때문입니다.

그럼 우변과의 차이를 최소로 하는 좌변의 값이 $d$차원 벡터공간에 적절히 임베딩된 단어벡터들일 겁니다. 이를 식으로 정리하면 아래와 같습니다. 아래 목적함수 $J$를 최소화하는 $w_i$, $w_j$, $b_i$, $b_j$가 우리가 원하는 미지수들입니다.

[\begin{align} J&=\sum _{ i,j=1 }^{ V }{ { ({ w }_{ i }^{ T }\tilde { { w }_{ j } } +{ b }_{ i }+\tilde { { b }_{ j } } -\log { X_{ ij } } ) }^{ 2 } } \ \end{align}]

그런데 GloVe 연구팀은 마지막으로 목적함수에 아래와 같은 모양의 $f(x)$를 추가했습니다. $X_{ij}$가 특정 값 이상으로 튀는 경우(학습 말뭉치에서 지나치게 빈도가 높게 나타나는 단어) 이를 방지하고자 하는 장치라고 보여집니다.

\(\begin{align*} J&=\sum _{ i,j=1 }^{ V }{ { f\left( { X }_{ ij } \right) ({ w }_{ i }^{ T }\tilde { { w }_{ j } } +{ b }_{ i }+\tilde { { b }_{ j } } -\log { X_{ ij } } ) }^{ 2 } } \\ &where\quad f(x)=\begin{cases} { (\frac { x }{ { x }_{ max } } ) }^{ \alpha } \\ 1\quad otherwise \end{cases}if\quad x<{ x }_{ max } \end{align*}\)

마치며

GloVe는 우선 학습말뭉치를 대상으로 co-occurrence 행렬 $X$를 만드는 것에서부터 학습을 시작합니다. 단어 개수가 1만개 정도 되는 말뭉치라면 요소 개수가 1억(10000 x 10000)이나 되는 큰 행렬을 만들어야 하는 것이죠. 이후 지금까지 설명드린 목적함수를 최소화하는 임베딩 벡터를 찾기 위해 matrix factorization을 수행해야 합니다. 계산복잡성이 꽤 크다는 이야기이죠.

어쨌거나 GloVe는 Word2Vec과는 다른 관점과 방식으로 단어를 임베딩하는 방법론으로 주목할 만한 것 같습니다. 마지막으로 GloVe의 임베딩 시각화 예시를 인용하는 것으로 설명을 마칠까 합니다. 의견이나 질문 있으시면 언제든지 이메일이나 댓글로 알려주시기 바랍니다. 여기까지 읽어주셔서 감사드립니다.

이번 글에서는 연관규칙분석(A Priori Algorithm)에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

알고리즘 개요 및 입력데이터

연관규칙분석이란 어떤 두 아이템 집합이 번번히 발생하는가를 알려주는 일련의 규칙들을 생성하는 알고리즘입니다. 경영학에서 장바구니 분석(Market Basket Analysis)으로 널리 알려져 있는 방법론인데요, 소비자들의 구매이력 데이터를 토대로 “X 아이템을 구매하는 고객들은 Y 아이템 역시 구매할 가능성이 높다”는 식의 결론을 내는 알고리즘입니다. 인터넷 쇼핑을 할 때 어떤 상품을 고르면 그 상품을 구매한 사람들이 선택한 다른 상품을 제안해준다던지 하는 컨텐츠 기반 추천(contents-based recommendation)의 기본이 되는 방법론입니다.

그럼 연관규칙분석에 쓰는 데이터부터 살펴볼까요? 동네 편의점의 매출이력(transaction)이 다음과 같이 주어졌다고 가정해봅시다.

위 데이터는 이렇게 해석할 수 있습니다. 1번 고객은 편의점에 들러 달걀, 라면, 참치캔을 샀네요. 7번 고객은 라면과 햇반을, 10번 손님은 양파를 구매한 걸 확인할 수 있습니다. 이를 행렬 형태로 표현하게 되면 아래와 같이 대부분의 셀이 0의 값을 갖는 희소행렬(sparse matrix)이 됩니다.

규칙 및 규칙의 효용성 지표

자, 그럼 주어진 데이터로부터 규칙을 만들어볼까요? 사실 무수히 많은 규칙을 만들 수 있을 겁니다. 첫번째 고객 데이터만 가지고도 이렇게 규칙을 만들어낼 수 있습니다. 달걀을 구매하는 사람들은 라면도 함께 산다, 달걀과 라면을 사먹는 사람들은 참치캔도 산다, 참치캔을 구매하는 사람들은 계란도 함께 산다…

우선 용어부터 정의하고 넘어가겠습니다. 조건절(Antecedent)은 위 예시의 규칙에서 ‘만일 ~라면’에 해당하는 부분입니다. 결과절(Consequent)은 그 뒷부분에 해당하는 내용입니다. 아이템 집합(Item set)이란 조건절 또는 결과절을 구성하는 아이템들의 집합입니다.

예컨대 ‘달걀을 구매하는 사람들은 라면도 함께 산다’를 보겠습니다. 여기에서 ‘달걀 구매’가 조건절, ‘라면 구매’가 결과절이며 각각의 아이템 집합은 ‘달걀’, ‘라면’이 되겠습니다. 단 여기에서 조건절 아이템 집합과 결과절 아이템 집합은 말 그대로 집합, 여러개 아이템이 들어가도 되지만 상호배반(mutually exclusive)이어야 합니다. 다시 말해 조건절에 달걀이 들어가 있다면 결과절에는 달걀이 포함되어서는 안된다는 뜻입니다.

그렇다면 무수히 많은 규칙 가운데서도 좋은 규칙이란 무엇일까요? 규칙의 효용성을 드러내주는 지표는 크게 지지도(support)와 신뢰도(confidence), 향상도(lift)가 있습니다. 빈발 아이템 집합을 판별하는 데 쓰는 ‘지지도’는 아래와 같이 ‘조건절($A$)이 일어날 확률’로 정의됩니다.

[For\quad the\quad rule\quad A\rightarrow B,\ support(A)=P(A)]

아이템 집합 간의 연관성 강도를 측정하는 데 쓰는 신뢰도는 아래와 같이 조건절($A$)이 주어졌을 때 결과절($B$)이 일어날 조건부확률로 정의됩니다.

[confidence(A\rightarrow B)=\frac { P(A,B) }{ P(A) }]

생성된 규칙이 실제 효용가치가 있는지를 판별하는 데 사용되는 향상도는 아래와 같이 조건절과 결과절이 서로 독립일 때와 비교해 두 사건이 동시에 얼마나 발생하는지 비율로 나타납니다. 바꿔 말해 향상도가 1이라면 조건절과 결과절은 서로 독립임을 뜻합니다. 규칙 사이에 유의미한 연관성이 없다는 걸로 받아들이면 될 것 같습니다. 향상도가 2라면 두 사건이 독립이라는 걸 가정했을 때 대비 2배로 긍정적인 연관관계를 나타냅니다.

[lift(A\rightarrow B)=\frac { P(A,B) }{ P(A)\cdot P(B) }]

규칙의 효용성은 지지도, 신뢰도, 향상도 세 가지를 모두 반영해 평가하게 됩니다. 임의의 규칙1이 규칙2보다 효과적인 규칙이라는 이야기를 하려면 세 지표 모두 클 경우에만 그렇다고 결론을 내릴 수 있게 된다는 이야기입니다.

규칙 생성

자 그럼 이제 규칙들을 실제로 만들어볼 차례입니다. 가능한 모든 경우의 수를 탐색하여 지지도, 신뢰도, 향상도가 높은 규칙들을 찾아내는 방식이 가장 이상적일 겁니다. 하지만 아이템 수가 증가할 수록 계산에 소요되는 시간이 기하급수적으로 증가하게 됩니다(아이템이 $n$개일 때 탐색해야할 모든 경우의 수 : $n * (n-1)$ ) 이 때문에 빈발 집합(frequent item sets)만을 고려하여 연관 규칙을 생성하는 A priori algorithm이 제안되었습니다. 핵심 아이디어는 이렇습니다.

예컨대 아이템 집합 {$A$}의 지지도, 즉 $P(A)$가 0.1로 나타났다고 가정해봅시다. 그렇다면 아이템 집합 {$A, B$}의 지지도는 아무리 높아도 0.1을 넘지 못할 겁니다. 왜냐하면 $A$가 단독으로 등장할 확률인 $P(A)$는 $A$와 $B$가 동시에 나타날 확률인 $P(A, B)$보다는 크거나 같을 것이기 때문입니다. 이 때 {$A,B$}는 {$A$}, {$B$}의 초월집합(superset)이라고 부릅니다.

다시 규칙을 생성하는 과정을 떠올려 봅시다. 만약 임의의 아이템 집합의 지지도가 일정 기준을 넘지 못한다면 해당 아이템 집합의 초월집합의 지지도는 그 기준보다 명백히 더 작을 것이고, 그렇기 때문에 유용한 규칙으로 인정받을 수가 없게 됩니다. 최소지지도 요건을 만족하지 못하는 아이템집합의 규칙들은 애당초 계산할 필요가 없다는 이야기인데요. 이를 그림으로 나타내면 이와 같습니다.

위 그림을 기준으로 설명해드리면 만일 아이템 집합 {$A, B$}의 지지도가 사용자가 정한 최소 지지도 요건을 충족시키지 못했을 경우 {$A, B$}는 물론 {$A,B$}의 초월집합인 {$A, B, C$}, {$A, B, D$} 등 8가지 경우의 수를 계산에서 제외하게 됩니다. 이로써 계산효율성을 달성하는 셈이지요.

분석 예시

그럼 예시 데이터를 기준으로 연관규칙분석을 수행해보겠습니다. 최소 지지도 요건을 0.2로 설정했다고 칩시다. 지지도는 이렇게 구합니다. 우선 라면은 전체 10개 레코드 가운데 8번 등장했네요. 그럼 라면의 지지도는 0.8입니다. 마찬가지로 달걀(0.5), 콜라(0.5), 햇반(0.3), 참치캔(0.2), 양파(0.1)의 지지도 역시 구할 수 있습니다. 그런데 양파는 최소 지지도 요건을 만족하지 못했으므로 양파가 끼어있는 모든 규칙은 이후 분석에서 제외합니다.

이번에는 앞 단계에서 살아남은 아이템들을 이용하여 최소 지지도 조건을 만족하는 2개짜리 아이템 집합을 생성합니다. 아래 표와 같습니다.

위 표는 이렇게 작성하면 됩니다. 우선 라면과 라면, 달걀과 달걀처럼 중복되는 아이템 숫자는 셀 필요가 없습니다. 따라서 위 행렬의 대각성분은 0으로 놔두면 됩니다. 그럼 라면과 달걀이 한 레코드에 동시에 등장한 빈도를 세어볼까요? 레코드 1, 4, 8, 9, 이렇게 10개 데이터 가운데 네 가지 경우가 있군요. 따라서 라면과 달걀의 지지도는 0.4입니다.

그런데 여기서 아이템 집합 내에서의 순서는 고려하지 않기 때문에 달걀과 라면의 지지도 또한 0.4인데요, 이는 위 행렬이 대칭행렬(symmetric matrix)라는 뜻입니다. 다만 대각성분 아래쪽으로는 중복된 숫자라 따로 적지 않았습니다.

마찬가지로 다른 아이템들의 지지도를 구해서 행렬을 채우면 되는데요, 이번에도 ‘달걀과 햇반’, ‘콜라와 햇반’, ‘콜라와 참치캔’, ‘햇반과 참치캔’은 최소 지지도 요건(0.2)를 채우지 못했으니 다음 분석에서는 이 경우의 수를 고려하지 않습니다.

이러한 방식으로 더 이상 최소 지지도 이상을 나타내는 아이템 집합이 없을 때까지 아이템 집합의 크기를 1씩 증가시키면서 반복 수행합니다. 이렇게 구한 상위 연관규칙 3가지는 아래와 같습니다. 동네 편의점의 매출이력 10건을 토대로 가장 강한 연관규칙은 ‘참치캔을 구매하는 소비자는 달걀과 라면을 동시에 산다’가 되는 셈입니다.

‘문서 요약’에 적용

연관규칙을 문서 요약(document summarization)에도 적용할 수 있습니다. 한 문장을 트랜잭션 데이터로 상정하고, 문장 내 출현한 단어를 아이템으로 놓고 같은 방식으로 분석하는 것입니다. 여기서 도출된 유의미한 규칙은 단어의 co-ouccerrence 정보를 함축할 것입니다. 예컨대 조건절이 {발, 없는, 말이}이라면 결과절은 {간다}가 나온다던지 하는 식입니다. 생각해볼 수록 많은 응용이 가능할 것 같습니다.

이번 글에서는 문서를 네트워크로 표현하는 방법론에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 참고로 했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

네트워크?

네트워크(network)란 간선(edge)으로 연결된 꼭지점(node)들의 집합을 의미합니다. 일반적인 의미에서 그래프(graph)와 유사한 개념입니다. 다양한 분야에서 쓰이는 관련용어를 한번 정리해보겠습니다.

네트워크의 종류는 아래처럼 크게 네 가지로 나눌 수 있습니다. 무방향(Undirected) 네트워크는 간선의 방향성이 없는 네트워크를, 방향(Directed) 네트워크는 방향성이 있는 네트워크를 의미합니다. 간선의 가중치가 있는지 여부에 따라 binary, valued 네트워크로 나뉩니다. 텍스트 마이닝에서는 무방향 네트워크가 더 자주 쓰입니다.

네트워크 표현

위와 같은 무방향 네트워크는 아래와 같이 인접행렬(adjacency matrix)로 표현할 수 있습니다. 인접행렬의 각 요소를 보면 어느 꼭지점들이 간선으로 연결되어 있는지를 알 수 있습니다. binary 네트워크에서는 꼭지점이 간선으로 연결돼 있을 경우 1, 그렇지 않으면 0으로 표시됩니다(Valued 네트워크라면 인접행렬의 요소값이 가중치값이 됩니다). 무방향 네트워크는 방향성이 존재하지 않기 때문에 인접행렬이 대칭행렬(symmetric matrix)입니다.

마찬가지로 아래와 같은 방향 네트워크도 인접행렬로 표현할 수 있습니다. 방향 네트워크는 무방향 네트워크와 달리 인접행렬이 대칭행렬이 아님을 확인할 수 있습니다.

꼭지점의 수가 많아질수록 인접행렬은 0이 많은 희소행렬(sparse matrix) 형태가 됩니다. 그만큼 메모리를 많이 잡아먹는다는 뜻입니다. 이 때문에 상당수 네트워크 처리 라이브러리는 인접행렬 말고 아래와 같이 Adjacency List, Arc List 형태로 네트워크를 분석합니다. 아래는 첫 예시인 무방향 binary 네트워크를 표현한 것입니다.

Adjacency List

a|b

b|a c

c|b d e

d|c e

e|c d

Arc List

a b

b a

b c

c b

c d

c e

d c

d e

e c

e d

네트워크 시각화

네트워크를 시각화하는 방법은 무수히 많이 존재합니다. 예컨대 아래 네 개의 네트워크는 얼핏 보면 다른 것 같지만 동일한 네트워크인 걸 알 수 있습니다.

네트워크를 시각화하는 알고리즘도 많이 제안되었는데요. 이들 알고리즘이 지향하는 큰 원칙은 이렇습니다. 꼭지점이 한쪽으로 쏠리거나 간선이 겹치는 걸 최소화하고, 간선의 길이는 균일하게 맞추며, 전체적인 네트워크의 모양은 가급적 대칭적인 구조가 되게끔 하라 등등입니다.

네트워크의 속성

네트워크의 몇 가지 속성을 살펴보겠습니다.

크기(size) : 간선의 개수

밀도(density) : 실제 간선의 수 / 이론적으로 가능한 모든 간선의 수 (꼭지점이 n개일 경우 n * (n - 1) )

Out-degree : 하나의 꼭지점에서 다른 꼭지점으로 나가는(out) 간선 수의 합 (방향 네트워크에서 정의)

In-degree : 다른 꼭지점에서 하나의 꼭지점으로 들어오는(in) 간선 수의 합 (무방향 네트워크에서 정의)

꼭지점의 속성

개별 꼭지점의 속성을 따지는 지표는 몇 가지 있습니다.

1. 연결성(conectivity)

임의의 한 꼭지점이 다른 꼭지점과 어떻게 연결되어 있는지 나타내는 지표입니다.

도달가능성(reachablity) : 꼭지점과 꼭지점 사이에 간선으로 연결돼 있어야 ‘도달 가능’하다고 정의됩니다.

거리(Distance) : 도달가능할 경우 몇 단계를 거처야 해당 꼭지점에 도달할지를 따지는 지표입니다.

경로 개수(Number of paths) : 도달 가능한 경로가 몇 가지가 있는지를 따지는 지표입니다.

2. 중심성(centrality)

임의의 꼭지점이 네트워크 상에서 얼마나 중심에 위치하고 있는지 나타내는 지표입니다. 대개 중심에 위치한 꼭지점은 중요한 꼭지점으로 인식됩니다. 이 때문에 중심성은 곧 중요도로 받아들여지기도 합니다. 그 정의와 예시 그림은 아래와 같습니다.

중개중심성(degree centrality) : 한 꼭지점에 연결된 간선의 수

근접중심성(closeness centrality) : 특정 꼭지점이 그를 제외한 다른 꼭지점과 얼마나 가까이에 있는지를 나타내는 지표. 해당 꼭지점의 도달 가능 거리 총합의 역수(inverse)로 정의됩니다.

중개중심성(betweenness centrality) : 한 꼭지점의 중개중심성은 그 꼭지점을 제외한 다른 두 꼭지점을 잇는 최단거리에 해당 꼭지점이 얼마나 많이 등장하는지 빈도로 정의됩니다.

고유벡터중심성(eigenvector centrality) : 중요한 꼭지점에 연결된 꼭지점일 수록 그 중요도가 높아지는 지표입니다. 인접행렬 고유벡터(eigenvector)의 각 요소가 각 꼭지점의 고유벡터중심성입니다.