다변수 정규화 상호정보량과 연어 추출

예전 포스팅에서 상호정보량과 점별 상호정보량에 대해 정리해보았었는데요, 두 사건이 함께 발생할 정도를 판단하는데 유용하게 사용됩니다. NLP에서는 연어(Collocation, 연속된 2개 이상의 단어가 한 덩어리로 쓰이는 것) 추출에서 유용하게 사용하지요. 다만 점별 상호정보량은 그 값이 (-∞, ∞) 범위에 속하고, 서로 정보량이 다른 사건을 비교할때 그 값의 스케일이 다르기 때문에 제대로된 비교가 어렵다는 점이 있습니다. 따라서 범위를 [-1, 1]로 일정하게 정규화할 필요가 있습니다. 이를 정규화 점별 상호정보량(Normalized Pointwise Mutual Information, NPMI)라고 부릅니다.

또한 일반적으로 상호정보량은 2개의 사건에 대해서만 정의되기에, 3개 이상의 사건이 함께 발생할 경향을 판단하는 데에는 사용하기 어려운데요, 이를 위해서 상호정보량은 3개 이상의 변수에 대해 일반화한 것을 다변수 상호정보량(Multivariate Mutual Information)라고 합니다. 본 포스팅에서는 다음 3개의 논문에서 제시된 방법을 종합하고 확장하여 2단어 이상의 연어를 추출하기 위해 상호정보량을 다변수로 확장하고 정규화하는 방법에 대해서 정리해보았습니다.

• 이재윤. (2003). 상호정보량의 정규화에 대한 연구. 한국문헌정보학회지, 37(4), 177-198.
• Bouma, G. (2009, September). Normalized (pointwise) mutual information in collocation extraction. In Proceedings of the Biennial GSCL Conference (Vol. 156).
• Van de Cruys, T. (2011, June). Two multivariate generalizations of pointwise mutual information. In Proceedings of the Workshop on Distributional Semantics and Compositionality (pp. 16-20). Association for Computational Linguistics.

정보량과 상호정보량

먼저 기본 개념부터 살펴봅시다. 어떤 사건 X가 일어날 확률을 p(X)라고 할때, X의 정보량 I(X)은 다음과 같이 정의됩니다:

그리고 두 사건 X와 Y가 함께 일어날 경향성인 상호정보량 PMI(X,Y)는 다음과 같이 정의됩니다:

그리고 용어의 혼란을 방지하기 위해서 (정보) 엔트로피와 상호정보량의 관계에 대해서 정리하도록 할게요.

정보 엔트로피(=평균 정보량)는 한 사건이 발생하는 모든 경우에 대해 그 경우의 확률과 정보량을 모두 곱해서 더한 값입니다. 즉 사건 X의 엔트로피 H(X)는 다음과 같이 정의됩니다:

두 사건에 대한 평균 상호정보량은 두 사건이 발생하는 모든 경우에 대해 그 경우의 확률과 점별 상호정보량을 모두 곱해서 더한 값입니다. X, Y에 대해 다음과 같이 정의되겠죠.

즉 정보량과 엔트로피의 관계와 점별 상호정보량과 상호정보량의 관계는 같습니다. 하지만 사용하는 맥락에 따라 상호정보량을 평균 상호정보량이라 쓰기도 하고, 점별 상호정보량을 그냥 상호정보량이라 쓰기도 합니다... (으아악!)

	한 가지 경우에 대해 계산	모든 경우에 대해 계산해 평균
한 사건	정보량 I	평균 정보량(=엔트로피) H
두 사건	상호정보량(or 점별 상호정보량) PMI	평균 상호정보량(or 상호정보량) MI

(왜 이렇게 용어가 난장판이 되었을까요 헷갈리게...)

여기에서는 상호정보량이라는 표현을 위의 정의한 PMI(X,Y)의 뜻으로 사용하도록 하겠습니다. 혼란이 없으시길 바래요.

상호정보량의 정규화

앞서 밝혔듯, 상호정보량의 값은 그 사건에 따라 천차만별이 됩니다. 항상 같이 일어나는 두 사건이라도 두 사건의 발생확률에 따라 그 값이 1이 될수도 10이 될수도 있죠. 따라서 절대적인 척도로 얼마나 같이 일어나는지 경향이 있는지 비교 용도로 사용하기에는 곤란한 점이 있습니다. 좀 더 수학적으로 볼까요?

사건 X와 Y가 일어날 확률을 p(X), p(Y), 그리고 X와 Y가 동시에 일어날 확률을 p(X∩Y)라고 해봅시다. 그리고 설명의 간편함을 위해 p(X) >= p(Y)라고 합시다. (아닌 경우에는 X와 Y를 뒤바꾸면 되겠죠?)

이 경우 항상 다음과 같은 부등식이 성립합니다.

자, 이때 PMI(X,Y)의 범위를 계산해봅시다. 자명하게도 PMI(X,Y)의 값이 최대가 되기 위해서는 p(X∩Y) = p(Y) = p(X)여야 한다는 것을 알수 있습니다. 따라서

p(X∩Y)의 최솟값은 0이지만, 이 경우는 두 사건이 절대 같이 일어나지 않는 경우이고, log값이 정의되지 않으므로 대게 이 경우의 PMI값은 정의하지 않거나 -∞로 정의합니다. 따라서 PMI의 최솟값을 고려할때는 이 경우는 제외하도록 할게요. p(X∩Y) > 0인 경우에 PMI(X,Y)가 최소가 되기 위해서는 p(X)와 p(Y)가 최대가 되면 됩니다. 즉 1이 되면 되겠죠. 

-2017.12.10 추가-

그러나 이 두값이 동시에 1이 되면 P(X) + P(Y) > 1이 되므로 이런 경우는 존재하지 않습니다. 따라서

따라서 PMI값은 항상 다음 범위에 들게 됩니다.

그렇기 때문에

입니다. 

상호정보량을 두 사건의 교집합의 정보량으로 나눈 값을 사용하게 되면 항상 (-1, 1] 범위에 값이 존재하게 되고, 1일 경우 항상 같이 발생, -1에 가까울수록 경우 거의 따로 발생한다고 볼수 있게되겠죠. 따라서 이 값은 정규화된 상호정보량으로 자주 사용합니다. 물론 I(X∩Y)로 나누는것 말고도 I(X)와 I(Y)로 각각 나눈것의 산술평균 or 기하평균을 구하는 등 다양한 방법이 있지만, IR분야에서 이 방법이 제일 무난한 성능을 보인다고 합니다.(이재윤, 2003)

따라서 정규화 상호정보량을 다음과 같이 정의하겠습니다.

또한 이렇게 정의할때의 장점은 p(X∩Y) = 0일때도 그 값을 정의할 수 있다는 점도 있습니다. p(X∩Y)를 간단히 t라고 쓰면 다음과 같습니다. 

t가 0에 가까워질수록 log t는 -∞로 발산하므로 log t가 있는 항은 0에 수렴하고, 그 결과 NPMI 값은 -1에 수렴합니다. 따라서 위의 빠진 -1 부분을 채워서 NPMI의 범위는 [-1, 1]이고, 1일때 항상 같이 발생, -1일때 절대 같이 발생하지 않는다고 해석할 수 있죠.

상호정보량의 일반화

앞서 언급한 상호정보량의 경우는 2개의 사건을 대상으로만 정의되었습니다만, 실제로 이를 3개 이상의 사건에 대해서 일반화하는 것이 가능합니다. 근데 일반화하는 방법이 2가지라고 하네요. 3변수 상호정보량에 대해 Van de Cruys가 제시한 2가지 방법을 살펴보도록 하죠.

왜 이렇게 이 2가지 방법이 나오게 되었을까요? 이는 세 사건의 관계를 바라보는 관점의 차이에서 나옵니다. 상호정보량이라는 개념은 원래 사건 Y가 일어났을때 X가 일어날 확률(조건부확률 P(X|Y))과 그냥 X가 일어날 확률(P(X))의 차이를 보는데에서 기인했습니다. 그리고 이는 다시 쓰면 다음과 같이 되죠.

PMI(X,Y) = I(X) + I(Y) - I(X∩Y)

포함배제의 원리를 생각해서 확장해보면 PMI(X,Y,Z)에 대해서도 유사하게 공식을 세워볼수가 있겠죠.

PMI(X,Y,Z) = I(X) + I(Y) + I(Z) - I(X∩Y) - I(Y∩Z) - I(Z∩X) + I(X∩Y∩Z)

(물론 이 논증은 쉬운 설명을 위해 간략화한거에요. 엄밀한 증명은 Van de Cruys, T. (2011, June)를 참조하세요.)

SI1번 식은 위와 같은 일반화를 통해서 얻어진거죠.

하지만 이게 유일한 일반화는 아니고, 항상 좋은 성능을 내는 것은 아닙니다. 연어 추출의 관점에서 볼때는 좀 다르거든요. 예를 들어 연속된 단어열 X-Y-Z가 등장하는 경향을 파악하고 싶다고 합시다. 이 때 우리는 X-Y가 함께 등장할 확률은 PMI(X,Y)를 통해 쉽게 계산할 수 있습니다. 그리고 X-Y를 묶어서 한 덩어리로 보고 (X-Y) - Z 가 함께 등장하는 경향을 계산할 수 있겠죠. PMI(XY, Z)를 계산하면 되니까요. 그래서 그 둘을 합하면 전체 X-Y-Z가 함께 등장하는 경향을 계산할 수 있겠죠.

즉 다음과 같이 됩니다.

즉, 두 일반화의 관점이 다르다고 볼수 있습니다. SI1의 경우 X, Y, Z를 모두 독립으로 보고 X-Y, Y-Z, Z-X가 동시에 일어날 확률과 X-Y-Z가 동시에 일어날 확률을 모두 고려하는 일반화 관점이라고 볼수 있겠죠. 그렇기에 순서에 의존성 없이 발생하는 사건들의 동시 발생 경향을 따질때 유용할 것입니다.

반면 SI2의 경우 X, Y, Z가 동시에 일어나지만 그 순서가 반영된다고 볼 수 있겠습니다. 즉 X-Y가 일어나고 Z가 일어나는 경우를 계산하는것이죠. 그 결과 X-Y-Z가 순서대로 발생하는 경향을 따질때 유용합니다. 자연언어처리에서 연어를 추출하는데 사용한다고 했을때는 이쪽 일반화가 좀더 적합하다는 것은 자명합니다.

다변수 상호정보량의 정규화

다변수의 경우 정규화는 어떻게 할까요? SI1의 경우 위에서 한것처럼듯이 I(X∩Y∩Z)로 나누면 [-1, 1] 범위로 정규화가 됩니다. (증명은 한 번 해보시길. 어렵지 않습니다.)

근데 SI2의 경우는 조금 재미있습니다. 그냥 I(X∩Y∩Z)로 나누면 [-1, 2]의 범위에 들어옵니다.

이거는 같이 증명을 해봅시다. 일반성을 잃지 않고 다음과 같이 가정할 수 있습니다.

당연히 SI2(X,Y,Z)가 최대가 되려면 분자에 있는 p(X∩Y∩Z)가 최대가 되어야하고 이경우는 p(X∩Y∩Z) = p(X) = p(Y) = p(Z)이어야 합니다. 따라서 SI2의 최댓값은

최솟값의 경우는 위와 같은 방법으로 증명가능합니다.

그래서 최댓값을 같은 선상에 두고 비교하려면 2로 더 나눠주는게 바람직합니다. (대게 상호정보량이 큰 쌍을 다루지 작은 쌍을 다루지는 않기 때문에 2로 나눠주는게 더 적합할 때가 많습니다.) 만약 n변수를 대상으로 SI2를 사용한다면 정규화시 (n-1)로 나눠주면 됩니다.

연어를 추출해보자

그래서 SI2 버전으로 정규화를 해서 2개와 3개짜리 연어를 실제 신문기사 코퍼스에서 추출해보았습니다. (먹는 연어 아닙니다.) 

단어	NPMI
허경영/NNP 롤스로이스/NNP 운전법/NNG	0.957582
America/SL Great/SL Again/SL	0.895846
내동/NNP 댕/MAG	0.983278
캐스팅/NNG 보트/NNG	0.978813

(예시가 좀 이상한거같지만) 보다시피 함께 등장하는 경향이 높은 단어들이 잘 뽑혀나오는것을 확인할 수 있습니다.

구현 코드는 http://bab2min.tistory.com/594를 참조하시면 되겠습니다.