상위어 자동 추출(Hypernym Detection) 기법 정리

우리가 사용하는 단어(그 중 특히 명사)는 어떤 개념을 나타내고 있고, 그 개념들 사이에는 서로 포함관계가 존재하는 경우가 많습니다. '포도'라는 개념은 '과일'이라는 개념에 포함되고, '과일'이라는 개념은 '음식'이라는 개념에 포함됩니다. 이를 수식처럼 표현하면

포도 ⊂ 과일 ⊂ 음식

처럼 쓸 수 있을 겁니다. 이 때 상위 개념에 포함되는 하위 단어를 하위어(Hyponym), 하위 개념을 포함하는 상위 단어를 상위어(Hypernym)이라고 부릅니다. 즉, 위와 같은 개념 간의 포함관계를 예로 들자면, 포도의 상위어는 과일이 되고, 과일의 하위어에는 포도가 들어가겠죠.

상위어, 하위어 관계를 따지는 것은 결국 그 단어가 가리키는 개념 간의 관계를 파악하는 것이고, 이는 인간이 언어로 표현하는, 세상에 대한 지식과 밀접하게 연관되는 작업입니다. 더 나아가서는 언어를 이해할 수 있는 인공지능 개발과도 연결되는 것이구요. 예를 들어

"나는 어제 (포도/포드)를 먹었다."

와 같은 문장이 주어진다면, 포도는 음식이기 때문에 먹는 대상이 될 수 있지만, 포드는 그렇지 않기 때문에 여기에 알맞은 답은 "포도"가 되어야 한다는 걸 사람들은 쉽게 알 수 있죠. 인공지능에게는 아직 어려운 일입니다. (사실 위 경우는 언어 모델을 통해 '포도'와 '먹다'가 함께 등장할 확률과 '포드'와 '먹다'가 함께 등장할 확률을 비교하여 풀 수 있는 문제긴 합니다.)

WordNet과 같이 수작업을 통해 수 많은 단어에 대해 상하위 관계를 구축한 경우도 있지만, 당연히 이는 너무 오랜 시간과 노동력이 필요하고 빠르게 등장하는 신조어들을 반영하는데에는 한계가 있습니다. 따라서 자동적으로 특정 단어에 대한 상위어를 추출하는 기법에 대한 연구가 활발히 이루어졌는데요, 이번 포스팅은 페이스북 AI 연구소에서 발표한 논문^[각주:1]을 바탕으로 다양한 상위어 추출 기법에 대해 살펴보도록 하겠습니다.

Hearst가 쏘아올린 작은 공(패턴 기반의 접근법)

이 분야에 있어 가장 고전적인 접근법은 패턴 매칭을 통해 상위어로 추정되는 단어를 찾는 것입니다. 1992년에 Hearst라는 연구자가 써낸 작은 논문^[각주:2]에서부터 상위어 자동 추출에 대한 연구가 시작되었습니다. Hearst는 다음과 같은 몇 개의 패턴을 제시하며 이런 경우에 일치하는 단어를 추출하여 상위어 자동 추출의 가능성을 보여주었습니다.

패턴	(해석)
X which is a (example|class|kind) of Y	Y의 한 종류인 X는
X (and|or) (any|some) other Y	X와 다른 나머지 Y들은
X which is called Y	Y라고 불리는 X는
Y (such as|including) X1, X2 ...	X1, X2 ...(와 같은|를 포함하는) Y는
...	...

위의 예시를 확인해보면 주로 위와 같은 표현이 등장하면, 이 때 X와 Y는 상하위관계가 성립할 것이라고 쉽게 납득할 수 있습니다. (Y에 과일, X에 포도를 넣고 문장을 읽어보세요.) 다행히도 영어와 같이 어순이 비교적 고정적인 언어에서는 정규표현식과 같이 단순한 방법으로 위와 같은 패턴 매칭을 수행할 수 있습니다. 덕분에 연산력이 지금과 같이 강력하지 않던 당시에도 쉽게 쓰일수 있었겠지요.

전체 말뭉치에서 위와 같은 패턴을 바탕으로 (X, Y)쌍이 추출되었다면 정말 간단하게는 이 쌍의 빈도를 바탕으로 확률을 계산하고, 이를 통해 상위어를 추정해낼 수 있습니다.

(w(x, y)는 (X,Y)쌍들 중 (x, y)의 출현빈도, W는 전체 추출된 모든 (X, Y)쌍의 갯수)

하지만 이 경우 x나 y의 기본적인 등장 빈도에 따라 전체 p(x, y)이 크게 영향을 받는다는 문제가 있습니다. 예를 들어 한국어에서는 '것'이라는 단어의 사용빈도가 굉장히 높기 때문에, (포도, 것)의 빈도가 (포도, 과일)의 빈도보다 훨씬 높을 수 있습니다. 이 경우 포도의 상위어로 '과일' 대신에 '것'을 추출하는 불상사가 일어나게 됩니다.

따라서 이를 상호정보량을 이용해 보정한 ppmi 지수를 사용하기도 합니다. 이는 p(x, y)의 확률을 p(x)의 확률과 p(y)의 확률로 나누고 로그를 취한 것으로 정의됩니다.

(p(x)는 모든 (X, Y)쌍 중에서 (x, ~)가 등장할 확률. p(y)는 모든 (X, Y)쌍 중에서 (~, y)가 등장할 확률)

이 경우 x가 등장할 확률과 y가 등장할 확률에 비해 (x, y) 등장할 확률이 얼마나 더 높은지를 봄으로써, 기대한 값보다 더 높은 확률로 등장하는 (X, Y) 쌍을 추출하는데에 사용할 수 있습니다. 당연히 이 값이 음수가 되면 함께 등장할 확률이 예상보다 더 낮다는 것이므로 상위어 추출에 도움이 안되는 쌍이라는 걸 알 수 있습니다. 따라서 이 경우는 그냥 버리는 셈치고, 음수인 값들은 다 0으로 바꿔치기 해서 쓰기도 합니다.

ppmi는 상호정보량을 통해서 (X, Y)쌍의 빈도를 정보량으로 정규화했기에, 이를 상하위 관계를 포착하는데에 그대로 사용해도 좋지만, 사실 약간의 문제가 있습니다. 단어 기반의 자연언어처리를 하다보면 늘 등장하는 희소성(Sparsity) 문제죠. 전체 가능한 (x, y) 조합 중 대부분이 0이고 일부 몇몇만 0보다 큰 값을 가지기 때문에 생각보다 적은 관계가 추출될 것입니다. 이를 해결하기 위해서 SVD를 사용할 수 있습니다. (SVD(Singular Value Decomposition)에 대해서는 예전에 LSA 기법을 다루면서 짧게 설명한 적이 있습니다.)

(X, Y)쌍에 등장하는 모든 x, y들을 모은 어휘 집합을 V라고 합시다. 그러면 다음과 같은 |V| * |V| 크기의 행렬을 생각해볼 수 있습니다.

(x, y ∈ V)

위에 적은것처럼 이 행렬은 대부분이 0인 희소 행렬이므로, SVD(특이값 분해)를 통해 특징을 추출하고 이를 바탕으로 다시 행렬을 복원하면 좀더 dense한 형태의 행렬을 얻을 수 있습니다.

위와 같이 SVD를 진행하면 Σ는 |V| * |V| 크기의 대각행렬이 될텐데, 이 중 상위 몇개 값을 제외하면 나머지 값들은 대부분 0에 가까울 것입니다. 상위 r개만 냅두고 나머지를 다 0으로 바꾼 행렬을 Σ_r이라고 합시다. 그러면 다음과 같이 M'을 복원할 수 있겠죠.

최종적으로 smooth된 ppmi 값인 spmi값을 위와 같이 얻을 수 있습니다. 논문에 따르면, 적절한 r의 값을 찾는다면, spmi를 통한 상위어 추출이 ppmi보다 좋은 성능을 보인다고 합니다.

분포적 기법을 통한 접근법

Hearst의 논문 이후, 다양한 방법으로 상위어를 추출하려는 시도가 있었습니다. 그 중 많은 기법들이 분포적 포함 가설(Distributional Inclusion Hypothesis, DIH)에 기반하고 있는데요, 이는 X의 상위어가 Y일 경우, X가 등장하는 맥락에서 X를 Y로 바꿔치기해도 큰 차이가 없을 것이라는 생각입니다. 즉 '나는 포도를 먹었어'라는 말에서 포도를 과일로 바꿔치기해도 '나는 과일을 먹었어'가 되고, 이 역시 문제 없는 문장이죠. 따라서 X 주변에 등장하는 단어들은 Y 주변에 등장하는 단어들과 포함관계를 이루고 있을 것이라고 생각할 수도 있겠구요.

이를 이용해 상하위 관계의 척도를 제안한 것이 Weeds의 논문^[각주:3]입니다. 흔히 WeedsPrec이라고 불리는 이 척도는 다음과 같이 계산됩니다.

(F(x)는 x와의 상호정보량이 0이상인 단어들의 집합, I(x, c)는 x와 c의 상호정보량)

수식이 복잡해보이지만, 분자와 분모를 각각 살펴보면 간단합니다. 분모는 X와의 상호정보량이 0이상인 단어들의 상호정보량 값의 총합입니다. 분자는 X와의 상호정보량이 0이상이면서 Y와의 상호정보량이 0이상인 단어들의 상호정보량 값의 총합이구요. 만약에 X의 상위어가 Y라면, X 주변에 자주 등장하는 단어는 Y 주변에도 자주 등장할 것이기 때문에, X와의 상호정보량이 0이상인 단어들은 Y와의 상호정보량도 0 이상일 겁니다. 즉 분자의 값이 분모의 값과 비슷해지겠죠. 완벽히 일치할 경우 WeedsPrec은 최대값인 1이 되고, Y가 X의 상위어라는 강력한 신호가 됩니다. 반면 이 값이 0일 경우 X, Y는 서로 관계가 없을 거구요.

이와 유사한 척도로 invCL^[각주:4]가 있습니다. 이 척도의 경우, 하위어 X가 상위어 Y의 맥락에 포함될 비율과 함께 거꾸로, 상위어 Y가 하위어 X에 포함되지 않을 비율도 계산해 이를 조합합니다.

CL(x,y)의 계산식은 WeedsPrec과 거의 동일합니다. 차이점이 있자면 분자에 들어가는 값이 I(x, c)와 I(y, c) 중 작은값으로 바뀌었다는 것뿐입니다. 이 값 역시 1일때 최대가 되며 이 경우 Y가 X의 상위어일 가능성이 매우 높다는 것을 뜻하며, 0이 되면 상위어가 아닐 가능성이 높다는 것을 드러냅니다. invCL의 경우 정의에 따라 Y가 X의 상위어일 가능성이 높으며, X가 Y의 상위어가 아닐 가능성이 높을 때 높은 값을 갖습니다.

이렇게 식을 확장한 경우는 두 단어 X, Y가 상하위 관계가 아니라 의미적으로 유사한 관계일 경우를 배제하기 위함입니다. DIH가설에 따르면, '과일'라는 단어 주변의 맥락은 '포도'라는 단어 주변의 맥락을 포함할 것입니다. 반대로 '포도'라는 단어 주변의 맥락은 '과일'이라는 단어 주변의 맥락 전체를 커버하지는 못할 것이구요. 이런 경우 CL(포도, 과일)의 값은 높아지지만, CL(과일, 포도)의 값은 낮아질 것입니다. 따라서 invCL(포도, 과일)은 높아지게 되겠죠.

반면 '포도'는 '머루'와 비슷한 의미를 나타내기에, '포도'라는 단어는 '머루'라는 단어와 그 맥락이 유사할 수 있습니다. 하지만 이 둘은 상하위 관계가 아니기 때문에 CL(포도, 머루)도 높지만 CL(머루, 포도)도 높을 것이고, 최종적으로 invCL(포도, 머루)는 낮아지게 됩니다.

이 밖에도 SLQS 등 몇가지 다른 방법도 본논문에서 소개했는데요, 이에 대해서는 생략하도록 하겠습니다.

실험을 통해 승부를 가리자

단도직입적으로 결론부터 말하자면, 패턴 기반 기법의 승리입니다. 그중에서도 spmi가 높은 성능을 보였구요, 분포적 기법 중에서는 invCL이 무난한 성능을 보였습니다. 사실 뭔가 규칙 기반의 방법은 좀 구시대적이고 성능 향상에 한계가 있을거라고 편견을 가지고 있었는데, 상위어 추출 작업에 대해서는 패턴 기반의 추출처럼 정확한게 아직은 없나 봅니다.

본 논문에서는 sparsity를 해결하기 위해 SVD를 사용했었는데, 이 대신 word embedding 등의 기법을 (어떻게든 잘 조합해서) 적용한다면 더 높은 성능을 보일수 있지 않을까 아이디어를 떠올리면서 포스팅을 마무리합니다.

부록. 한국어 데이터를 가지고 실험해보자!

과연 한국어에서도 잘 통할까 궁금해서 Hearst 패턴 몇 개를 번역해서 한국어 패턴을 만들고 이를 가지고 나무위키 전체 텍스트 데이터(약 4기가)에 대해서 실험해보았습니다.

X	Y	w(X, Y)	X의 빈도	Y의 빈도	ppmi(X, Y)
페닐알라닌	아미노산	6	6	14	11.1675
앵두	입술	6	8	11	11.121
엘더	이동버프기	16	16	16	11.034
Taskmaster	휘장	7	7	23	10.671
아스파탐	감미료	6	8	18	10.6285
대부업	등록	9	9	25	10.5877
VMware	가상머신	6	11	14	10.5613
C-130	수송기	10	14	19	10.5256
태모신교	종단	6	18	9	10.5107
태종	묘호	10	18	16	10.4462
신체검사	검사규칙	14	27	15	10.4417
낙원대성	bgm	6	6	35	10.2512
셀룰러	이동통신사	15	19	28	10.2379
수은	중금속	6	15	17	10.057
롯데월드	놀이공원	7	17	18	10.0289
앞마당	멀티	6	19	14	10.0148
사회복무요원	보충역	8	33	11	9.99158
사사	아스카	6	39	7	9.98883
채권	담보	13	40	15	9.97456
용모	신체조건	9	22	19	9.96828
MAME	에뮬레이터	7	9	38	9.91764
노숙인	복지	10	12	41	9.91065
조도	마호네	8	40	10	9.89452
회색	무채색	7	41	9	9.84165
비트코인	암호화폐	14	47	16	9.82286
트럼펫	금관악기	6	27	12	9.81756

위 결과는 추출된 (X,Y)쌍들에 ppmi(X, Y)가 높은 값을 상위 20여개를 보여준 것입니다. 추출에 사용한 패턴이 적어서 그런지, Noisy한 결과가 많습니다. 앵두-입술의 경우 "앵두 같은 입술"이라는 관용적 표현 때문에 뽑힌것 같네요. 납득가능한 결과들은 굵게 처리했습니다.

Y를 고정하면 좀더 깔끔한 결과를 얻을 수 있습니다.

게임의 하위어 목록들

X	Y	w(X, Y)	X의 빈도	Y의 빈도	ppmi(X, Y)
방생	게임	8	9	3191	5.62067
마비노기	게임	15	26	3191	5.1884
소녀전선	게임	8	14	3191	5.17883
MMORPG	게임	12	22	3191	5.13231
GTA	게임	13	25	3191	5.08452
DDR	게임	6	14	3191	4.89115
배틀그라운드	게임	18	43	3191	4.86762
오버워치	게임	51	126	3191	4.83399
테트리스	게임	10	26	3191	4.78294
하스스톤	게임	22	58	3191	4.76905
철권	게임	24	64	3191	4.75762
카트라이더	게임	6	16	3191	4.75762
세븐나이츠	게임	7	19	3191	4.73992
칸코레	게임	7	19	3191	4.73992
스카이림	게임	10	28	3191	4.70883
배틀필드	게임	7	20	3191	4.68863
마인크래프트	게임	15	46	3191	4.61786
와우	게임	14	43	3191	4.61631
컴뱃	게임	6	20	3191	4.53448
스타크래프트	게임	33	114	3191	4.49876

과일의 하위어 목록들

X	Y	w(X, Y)	X의 빈도	Y의 빈도	ppmi(X, Y)
블루베리	과일	6	9	89	8.91244
망고	과일	4	8	89	8.62476
자두	과일	3	12	89	7.93161
복숭아	과일	7	32	89	7.79808
딸기	과일	6	32	89	7.64393
체리	과일	4	23	89	7.5687
포도	과일	6	39	89	7.4461
수박	과일	3	29	89	7.04922
오렌지	과일	4	44	89	6.92001
바나나	과일	4	44	89	6.92001
사과	과일	10	127	89	6.7763
레몬	과일	3	39	89	6.75295
배	과일	3	720	89	3.83726

1. Roller, S., Kiela, D., & Nickel, M. (2018). Hearst Patterns Revisited: Automatic Hypernym Detection from Large Text Corpora. arXiv preprint arXiv:1806.03191. [본문으로]
2. Marti A. Hearst. 1992. Automatic acquisition of hyponyms from large text corpora. In Proceedings of the 1992 Conference on Computational Linguistics, pages 539–545, Nantes, France. [본문으로]
3. Julie Weeds, David Weir, and Diana McCarthy. 2004. Characterising measures of lexical distributional similarity. In Proceedings of the 2004 International Conference on Computational Linguistics, pages 1015–1021, Geneva, Switzerland. [본문으로]
4. Alessandro Lenci and Giulia Benotto. 2012. Identifying hypernyms in distributional semantic spaces. In Proceedings of the First Joint Conference on Lexical and Computational Semantics, pages 75–79, Montr´eal, Canada. Association for Computational Linguistics. [본문으로]