[KIWI] 좋아, 형태소 분석기를 만들어봅시다. - 3

(이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949)

속도를 향상시키기

한 어절이 A B C D E F와 같이 6개의 형태로 쪼개질 수 있고 A,B,C,D,E,F 각각에 일치가능한 형태소가 4개씩 있다고 하면 전체 가능한 형태소 조합은 4^6 = 4096가지입니다. 각각의 조합마다 6개의 형태소 등장확률 계산 및 6개의 품사 간 전이확률을 계산해야 하니 12회의 확률 계산이 필요하네요. 즉 4096 * 12 = 49152회의 연산이 필요합니다. 이 모든 조합을 계산하기에는 시간이 너무 아깝습니다. 어차피 이 중에서 우리가 알고싶은건 가장 등장확률이 높은 조합 1개인걸요.

만약에 A B C D E F를 A B C / D E F 로 두 덩이로 나눈다면 어떨까요. 앞의 덩어리에서 나오는 조합은 4^3 = 64가지, 뒤의 덩어리에서 나오는 조합 역시 4^3 = 64가지입니다. 단 앞의 덩어리는 크기가 3이므로 3번의 형태소 등장확률, 3번의 품사 간 전이확률을 계산하면 되니 64*6번 연산을 하면 됩니다. 뒤의 덩어리 역시 64*6번만의 연산이 필요하구요. 즉 덩어리별 모든 조합의 확률을 계산하는데에는 384회의 연산만이 필요합니다. 그리고 이 두 덩어리를 합치는 경우의 수는 64*64 = 4096번이니, 384*2 + 4096 = 4864회의 연산이 필요하겠죠. 별로 대단한 일을 한건 아니고, 다뤄야할 조합을 큰 덩어리에서 작은 덩어리 둘로 나눴더니 해야할 연산이 1/10로 줄어버렸습니다.

이를 컴퓨터과학자들은 Divide and Conquer(분할 정복)이라고 부릅니다. 합쳐져있을때는 너무 커다래서 계산하기 힘들던 연산을 잘게 쪼개서 쉽게 처리한 뒤 합쳐서 전체 결과를 얻어내는 문제 해결 방식이죠. 

추가 꼼수

그리고 꼼수를 좀더 써볼까 합니다. 사실 아까 A B C / D E F 덩어리에서 각 덩어리마다 64가지의 조합이 나오는데, 최종 조합을 계산할때 64*64 경우를 모두 다룰 필요는 없습니다. 어차피 우리는 가장 확률값이 높은 1개의 조합만 알면 되고, 전체 조합의 순위를 알 필요는 없잖아요. 그러니 애초에 A B C에서 가장 확률이 높은 조합 5개 정도, D E F에서 가장 확률이 높은 조합 5개 정도를 뽑아내서, 5*5가지 경우만 봐도 되지 않을까요? 

(사실 이 생각은 약간의 위험성을 안고 있습니다. A B C 또는 D E F에서 낮게 나오는 조합이 A B C D E F로 합쳐졌을때 높게 나올수도 있기 때문이죠. 그런 경우가 많지는 않겠지만 종종 등장할 수 있으므로, 이렇게 상위 조합만 다루는 방식은 속도를 향상시킬수 있지만 약간의 정확도 희생을 감수해야합니다.) 

만약 이 방식대로라면 우리가 최종 계산해야할 연산 횟수는 384*2 + 4096 이 아니라 384*2 + 25 = 793회가 됩니다.

분할정복 알고리즘을 사용할때 유의해야할 점은 무조건 잘게 쪼개는게 능사가 아니라는 것입니다. 너무 잘개 쪼개게 되면 쪼개서 얻는 이득보다 쪼개고 합치는데 사용하는 비용이 높아져서 결국에는 손해를 보게 되기 때문이죠. 그래서 대게 크기는 실험적으로 정하게 됩니다. 저의 경우는 덩어리 내의 형태소 조합 경우의 수가 6~16 건이 넘어가게 되면 덩어리르 쪼개도록 했습니다. 하지만 이에 대해서는 좀더 실험을 통해서 정확한 이득/손해를 계산해볼 필요가 있겠네요.

두번째 방법은 Caching(캐싱, 했던 연산 저장해놓기)입니다. 일단 현재 모델에서는 분석 결과는 독립적이므로 자주 분석하는 어절의 결과를 메모리에 저장해두면 다음번에 재사용할 수 있습니다. 다행히도 한국어의 어절 분포 역시 지프의 법칙을 따르므로(하지만 그 경향이 어절=단어인 영어에 비해서는 약하긴 합니다.) 자주 사용하는 어절은 정말 자주 쓰여서 캐싱의 효과를 톡톡히 볼 수 있습니다. 경우에 따라서는 20~30%의 속도 향상도 가능하더라구요.

평가해보기

이렇게 고생고생(사실 큰 고생을 하지는 않았지만)해서 만든 Kiwi가 어느정도의 성능을 보이는지 어떻게 평가해볼 수 있을까요? 세종 계획 코퍼스 중 몇 개를 골라서 테스트 문제로 만들어보았습니다. 그래서 직접 Kiwi보고 풀어보라고 하고 얼마나 빨리 푸는지, 얼마나 많이 맞추는지 확인해보면 되겠죠. 

문제와 답안은 다음과 같은 형태로 주어집니다.

프랑스의 세계적인 의상 디자이너 엠마누엘 웅가로가 실내 장식용 직물 디자이너로 나섰다.

프랑스/NNP 의/JKG 세계/NNG 적/XSN 이/VCP ㄴ/ETM 의상/NNG 디자이너/NNG 엠마누엘/NNP 웅가로/NNP 가/JKS 실내/NNG 장식/NNG 용/XSN 직물/NNG 디자이너/NNG 로/JKB 나서/VV 었/EP 다/EF ./SF

Kiwi가 풀어서 낸 답안은 다음과 같이 나옵니다.

프랑스/NNP 의/JKG 세계/NNG 적/XSN 이/VCP ㄴ/ETM 의상/NNG 디자이너/NNG 엠마누에/UN ㄹ/ETM 웅/NNP 가로/NNG 가/JKS 실내/NNG 장식/NNG 용/XSN 직물/NNG 디자이너/NNG 로/JKB 나서/VV 었/EP 다/EF ./SF

확률값: -104.6

(처음보는 고유명사를 자기맘대로 쪼개버리는 Kiwi님의 위엄..!!!)

점수는 자카드 유사도를 이용해서 매깁니다. 

점수 = (일치하는 형태소의 갯수) / (정답의 형태소 갯수 + Kiwi가 낸 형태소의 갯수 - 일치하는 형태소의 갯수)

일치하는 형태소의 갯수는 19개, 정답의 형태소는 21개, Kiwi의 형태소는 23개이므로 19 / (21+23-19) = 0.76. 이 문제에 대한 Kiwi의 점수는 76점입니다. 이렇게 모든 문제에 대한 점수를 평균내면 그게 Kiwi의 성능이라고 볼수 있겠죠. 몇개 문서 집합에 대한 Kiwi의 성능을 살펴보아요.

비문학(신문기사)	문학작품
0.781	0.811

블로그나 SNS 등 다양한 글 유형에 대해서도 해보고 싶은데 아직 정답셋을 구하지 못해서 평가를 못하고 있네요.

일단 여기까지

아직 간신히 80%의 정확도를 보이는 녀석이라 기존의 훌륭한 형태소 분석기를 뛰어넘기에는 좀 멀어보이긴 합니다. 그래도 c++로 개발되고, 다른 외부 라이브러리에 의존하지 않기 때문에 JVM이나 기타 군더더기 라이브러리 없이도 필요한 곳에 찰싹 붙여 쓸수 있어요. 그런 점에서 가능성이 있다고 보며 바이너리와 소스 코드를 공개합니다. 소스 코드는 LGPL 라이센스를 따릅니다.

Kiwi_0.1x64.zip

Kiwi_0.1x64_Linux.zip

Kiwi_0.1x86.zip

https://github.com/bab2min/Kiwi

그리고 웹에서 테스트해볼 수 있는 페이지를 하나 만들어 두었습니다. 과도한 부하를 거는일만 없다면 잘 작동할 겁니다. 

시간 날때마다 틈틈히 개선해나가면 재미 있을거 같네요.