[Kiwi] 지능형 한국어 형태소 분석기 0.6버전 업데이트

최근 Kiwi 형태소 분석기 0.6 버전 업데이트를 실시했습니다. 사실 엄청 바뀐건 없고, 이전 버전에서 사용하던 최적화를 좀더 한 단계 끌어올리는 작업을 수행했습니다. 0.4버전에서 도입한 그래프 기반 경로 탐색 알고리즘의 경우, 이상하게도 끝쪽에서 앞쪽으로 분석을 진행했습니다. 당시에 왜 이렇게 설계했는지 모르겠는데, 개발하고 보니, 역방향으로 추적을 진행하더라구요.

사실 경로 탐색을 진행하는게 순방향인지 역방향인지 자체는 성능에 영향을 미치지 않습니다만, n-gram 언어모델을 캐싱하는데에는 순방향이 훨씬 유리합니다. 0.5버전에서 Kneser-Ney smoothing을 적용한 n-gram 언어 모델을 바탕으로 형태소가 출현할 확률을 계산하도록 알고리즘을 교체하였는데요, 이게 약 2만 여개의 형태소를 대상으로 trigram을 계산해야하는 작업이었습니다. 가능한 총 조합의 수는 최대 20000^3이므로, 이 전체가 메모리에 올라갈 수는 없습니다. 따라서 trie를 활용하여 trigram의 KN smoothing 값을 계산하도록 구현했습니다. 

trigram을 trie로 표현하는건 메모리를 아낄 순 있지만, 전반적인 탐색 속도는 느려지게 된다는 문제가 있습니다. 이 때문에 형태소 분석의 속도를 좌우하는게 이 trie의 순회 속도였는데, 이를 최적화하는게 이번 업데이트의 핵심이었습니다.

이번 포스팅에서는 간략하게 그 최적화 방법에 대해서 설명하도록 하겠습니다.

Trie와 Trigram 확률 계산

Trigram 언어모델이라 함은 어떤 단어가 등장할 확률은 이전 두 단어에 영향을 받는다는 가정하에 다음 단어를 예측하도록 생성한 모델이라고 설명할 수 있습니다. 즉 AB 뒤에 C가 나올 확률을 보는 식이죠. 이는 AB가 등장하는 전체 빈도 대비 ABC가 등장하는 빈도를 계산함으로써 알 수 있습니다. 앞서 설명했다시피, 단어의 수가 수 만에 육박할때, 조합이 가능한 전체 trigram 수는 단어 수의 세제곱배가 되므로, 이 모든 경우를 배열에 저장할 수는 없습니다. 따라서 위와 같이 tree의 형태로 각 경우를 표현하는 방법을 쓰게됩니다. tree의 각 노드가 단어(혹은 글자)이고, 각 노드가 어떤 문자열(prefix)를 나타내게 될 경우 이를 trie라고 부릅니다. 위의 경우 A, B, C가 각 단어가 될것이고, 이 Trie는 A, B, AA, AB, AC, BA, BC, AAA, AAB, ABA, ACC, BAA, BAB, BCC 라는 문자열을 표현하게 됩니다.

이 Trie의 각 노드에 확률값을 저장해두면, 쉽게 Trigram 언어모델을 계산하는데에 쓸 수가 있습니다. 위의 그림을 보시면 이해가 쉽습니다. 만약 ABA라는 문자열이 연속해서 등장할 확률을 이 Trie를 가지고 계산한다면, 먼저 Root노드에서 시작해서 A노드를 찾습니다. A노드는 P(A)값을 가지고 있겠죠. 그 다음 B노드를 찾습니다. 이 노드는 P(B|A)값을 갖고 있습니다. 마지막으로 A노드를 찾습니다. 이 노드는 P(A|AB) 값을 가지고 있습니다. A, B, A를 차례로 순회하면서 얻은 이 확률값들을 모두 곱하면 P(A) * P(B|A) * P(A|AB) = P(ABC)를 얻을 수 있는거죠.

꽤 효율적인 방법입니다. 다만 각 노드가 가지는 자식이 수 만개가 될 경우 생각보다 다음 노드를 찾는게 어려워집니다. 각 노드가 자식 노드 수 만개를 다 가지고 있지는 않을테니 이를 vector(array)가 아닌 map(dictionary) 형태로 저장할텐데, 이를 탐색하는데에는 O(log(N)) 시간이 소요됩니다. (당연히 이때 N은 전체 어휘의 수겠죠.) Trigram이므로 최소 3번의 탐색을 거쳐야 원하는 확률을 얻을 수 있을 것이므로 평균적으로 탐색에 걸리는 시간은 3*log(N)이 될것이구요.

이제 여기서 ABAAB 문자열이 등장할 확률을 계산한다고 가정해봅시다. trigram이므로 P(ABAAB) = P(A) * P(B|A) * P(A|AB) * P(A|BA) * P(B|AA)가 될텐데요, P(A), P(B|A), P(A|AB)는 자식 노드를 따라가며 한번에 발견할 수 있지만 (총 3회의 탐색), P(A|BA), P(B|AA)는 앞의 경로와는 연결된게 없으므로, root부터 시작해서 다시 탐색해야하므로 각각 3회의 탐색이 필요합니다. 총 9회의 탐색이 필요한거죠. 이게 기존 0.5버전의 알고리즘이었습니다.

0.6버전에서는 상위 노드를 가리키는 빨간선이 추가되었습니다. abc라는 문자열이 있을때 앞의 a를 제거한 bc라는 문자열을 표현하는 노드를 가리키도록 한 것입니다. 예를 들어 ABA의 경우, 빨간선이 BA를 가리키도록 했고, BAA의 경우 AA를 가리키도록 했습니다. 이 빨간선은 자신의 부모노드를 가리키는 것과는 다릅니다. 자신이 가리키는 제일 앞의 문자를 제거하여 연속적으로 다음 문자가 등장할 확률을 탐색할 수 있도록 한것입니다.

위와 같이 ABAAB라는 문자열을 탐색한다고 가정해봅시다. ABA까지 왔을 때 포인터는 P(A|AB) 지점을 가리키고 있을겁니다. 이제 다음문자로 A를 찾아야하는데, A에 해당하는 자식 노드가 없으므로 빨간선을 따라 상위 노드로 이동합니다. 그러면 P(A|B)노드에 도달하는데 이 노드는 A에 해당하는 자식을 가지고 있으므로 P(A|BA)를 얻을 수 있습니다. 이제 그 다음 B에 해당하는 자식 노드를 찾아야하는데, 역시 자식 노드가 없으므로 다시 빨간선을 타고 P(A|A)에 도달하면 자식 노드 B를 찾아서 P(B|AA)를 찾을 수 있습니다. 즉 연속하는 단어열을 검색할때 Root에서부터 찾지 않고 계속해서 빨간선과 파란선만 이동하면서 모든 확률값을 찾을 수 있게 된 것이죠. 따라서 다음 단어 한 개를 찾는데 평균적인 시간은 log(N)이 걸리게 됩니다. (3*log(N)이 아니라. 즉 이론상으로 3배 빨라질 수 있다는겁니다.)

실제 성능 개선 결과는?

이를 적용해 Kiwi의 성능을 끌어올렸는데요, 이유는 모르겠지만 정확도도 같이 상승했습니다. 아마 0.5버전 구현 어딘가에 사소한 실수가 있었거나, 속도를 보장하기 위해서 이런저런 트릭을 사용한게 정확도를 낮추는 문제가 있었나 봅니다. 0.6버전으로 넘어오면서 그런 트릭들 없이도 충분한 성능이 나와서 트릭들은 다 제거했기에 정확도도 상승한것 같구요.

이건 실행 속도를 비교한 결과를 그래프로 나타낸 것입니다. 이전버전보다 속도가 (3배까지는 아니고) 약 1.5~2배 정도 상승하여서 다른 분석기들과 비교해도 꿀리지 않는 속도를 보이고 있습니다. (Mecab이 제일 빠른 속도를 보인다고 알고 있는데, macOS가 아니라 구동이 불가한 관계로 속도 평가에서 제외됐습니다. 아마 다른 벤치마킹 결과들을 종합해볼때 Kiwi가 Mecab보다는 느릴것으로 예상됩니다.)

정확도의 경우 사전에 데이터가 없는 단어가 많은 비문학, 신문 기사 등에서는 평균 92%, 문학 작품에서는 96%를 보이는 것으로 측정되었구요. 자세한 결과는 Github 리포지터리에서 확인하실 수 있습니다. (실행 데모는 여기에서!)

처음에 개발을 시작했을때는, Kiwi는 c++로 개발할 것이므로 당연히 java로 만든 분석기들은 쉽게 따라잡을 수 있을거라고 생각했었습니다. 그런데 무려 1년이 넘게 개발해도 java로 짠 녀석들을 따라잡을 수 없었습니다... Java가 생각보다 느리지 않다는 것과 언어보다는 효율적인 알고리즘이 더 중요하다는 것을 다시 한 번 깨닫는 나날이었죠. 그래도 드디어 Java로 만든 분석기들을 따라잡게 되어 매우 기쁘네요. 아직 정확도 및 기능 면에서 부족한 점이 많지만, 당분간 Kiwi 개발에는 잠시 여유를 두고 다른 공부들을 더 진행해보려 합니다.

물론 버그 제보나 기능 제안은 언제든지 환영이니, 메일이나 github을 통해서 전달 부탁드려요!