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

Posted by 적분 ∫2tdt=t²+c
2017.09.11 02:59 프로그래밍/NLP

속도가 만족할 만큼 나오지 않아서 아쉽길래 한동안 접어두고 있었는데, 갑자기 좋은 아이디어가 떠올라서 업데이트를 해보았습니다. 약간의 알고리즘 수정으로 최소 +50%~200%의 속도 향상을 달성할 수 있었는데, 기록하지 않고 넘어가기에 너무 아까워서 포스팅을 써보았습니다.



0.3버전까지 방법

이전 포스팅에서도 간단히 적었듯이 형태소 분석기의 핵심은 마르코프 연쇄입니다. 각각의 형태소가 등장할 확률 및 한 형태소 다음에 다른 형태소가 등장할 확률을 계산해서, 그 확률이 가장 높은 형태소열을 찾는것이 형태소 분석기의 업무라고 할 수 있습니다. 원활한 이해를 위해 다음 예시를 들어보죠.


먹었다


위 단어를 분석한다고 해봅시다. 어떤 형태소가 들어갈 수 있는지 일단 나열해보자면, 다음과 같을 겁니다.


먹/VV었/EP다/EF

먹/VX

다/EC

먹/NNG

다/MAG


'먹'에 일치될 수 있는 형태소는 크게 3개, '었'은 1개, '다'는 3개가 되겠습니다. 따라서 우리는 다음 6가지의 형태소 조합의 연쇄 확률을 모두 계산해야하지요.

먹/VV + 었/EP + 다/EF

먹/VX + 었/EP + 다/EF

먹/NNG + 었/EP + 다/EF

먹/VV + 었/EP + 다/EC

먹/VX + 었/EP + 다/EC

먹/NNG + 었/EP + 다/EC

먹/VV + 었/EP + 다/MAG

먹/VX + 었/EP + 다/MAG

먹/NNG + 었/EP + 다/MAG


이 경우는 매우 단순한 경우라고 할 수 있습니다. 형태소 조합이 더 복잡한 단어들도 많지요. 단어가 많아질 수록 계산해야할 경우의 수는 기하급수적으로 증가합니다. 그래서 0.3버전까지는 실제로 모든 조합을 다 계산하지 않고 경우가 많아질 경우 단어를 임의로 분해하여 계산한 뒤 합치는 방법을 사용했습니다.


0.4버전의 방법

잘 생각해보면 결국 형태소 조합은 하나의 흐름으로 볼 수 있습니다. 단어를 시작해서 형태소를 고르고 다음 형태소를 고르고... 고르는 작업을 반복해서 단어의 끝까지 도달하는 것이죠. 징검다리를 밟고 강을 건너는 것을 생각해볼 수 있겠습니다. 즉 가장 편하게 강을 건널 수 있는 징검다리를 고르는 작업이라고 보는 겁니다. 우리가 형태소 연쇄의 등장확률을 계산할 때 사용하는 것은 각각의 형태소의 등장확률과 형태소 간의 전이 확률이라고 했습니다. 만약 각각의 형태소를 그래프 상의 정점(node)로 생각한다면 형태소 간 전이 확률은 간선(edge)가 될 수 있겠죠. 즉 한 단어에서 나올 수 있는 형태소 조합은 그래프 형태로 표현이 가능하게 됩니다.


위의 그림처럼 말이죠! 위의 그림에서 파란 원은 각각의 형태소를 나타내고, 주황 원은 시작지점과 끝지점을 나타냅니다. 파란 원 안의 수치는 형태소의 등장확률의 로그값, 녹색 간선의 수치는 형태소 간 전이 확률의 로그값입니다. (물론 값은 설명을 위해 단순히 골랐습니다.)


이렇게 그래프 형태로 바뀌면 형태소 분석기가 해야할 일은 결국 시작지점^ 에서 끝지점$로 이어지는 가장 확률이 높은 경로를 찾는 일이 됩니다. 흔히 하던 최단 경로 찾기 문제가 되어버리는 것이죠. 즉 지나가는 간선과 정점의 숫자들을 더한 값이 가장 큰 경로를 찾으면 되는데, 이는 동적 계획법을 이용해서 중간중간 연산결과를 저장하면 매우 쉽게 풀수 있습니다.

즉, 매번 모든 경로를 탐색할 필요없이 부분 부분 저장해두었단 부분 최단 경로를 재활용하는 것이죠.


예를 위해 끝부분부터 거꾸로 올라가 보겠습니다. 먼저 다/EF - $의 최단 경로는 당연히 다/EF - $ (-0.3)입니다. 마찬가지로 해서 다음 표를 채울 수 있겠죠

시작경로확률값
다/EF$다/EF - $-0.3
다/EC$다/EC - $-0.9
다/MAG$다/MAG - $-0.7


그 다음은 었/EP - $의 최단 경로를 찾는 일입니다. 이미 다/EF, 다/EC, 다/MAG에서 끝으로 이어지는 최단 경로를 전부 찾아두었으니 이 값을 재활용하면 됩니다. 당연히 다/EF - $가 -0.3으로 제일 크므로, 었/EP - $의 최단 경로는 었/EP-다/EF-$ (-0.6)이 됩니다.

시작경로확률값

었/EP

$었/EP - 다/EF - $

-0.6


이제 먹/VV, 먹/VX, 먹/NNG에서 끝으로 이어지는 최단 경로를 계산해봅시다. 이미 었/EP - $의 최단 경로를 알고있으니 이 역시 간단합니다.

시작경로확률값

먹/VV

$먹/VV - 었/EP - 다/EF - $

-0.9

먹/VX

$

먹/VX - 었/EP - 다/EF - $

-1.0

먹/NNG

$

먹/NNG - 었/EP - 다/EF - $

-2.0


이제 시작점 ^에서 끝점$까지의 최단경로를 쉽게 구할 수 있겠죠. ^ - 먹/VV - 었/EP - 다/EF - $ (-0.9)가 됩니다. 이렇게 계산할 경우 3*1*3으로 9가지 경우(각각의 경우는 5번의 덧셈을 계산)를 일일히 계산하는 대신 3+1+3으로 7번(각각의 경우는 2번의 덧셈)의 노드에 대해서 계산함으로써 가장 확률이 높은 형태소 연쇄를 찾아낼 수 있습니다.


지금 소개한 알고리즘이 바로 비터비(Viterbi) 알고리즘입니다. 정확히는 비터비 알고리즘의 단순화된 버전이라고 할 수 있겠죠. 비터비 알고리즘은 루프가 있는 상황에서도 잘 수행되지만, 위의 방법을 루프가 있는 그래프에 적용하려면 약간 수정을 해야할 것입니다.


실제로 얼마나 빨라졌나?

그래서 한 번 버전별 속도를 비교해봤습니다.

시간(ms)v0.2v0.3v0.4v0.3 → v0.4 향상
텍스트A1168056561952190%
텍스트B88644865

3133

55%
텍스트C76704294273057%
텍스트D15808

9073

606250%
텍스트E21126110553466219%
총합651483494317343101%
속도(MB/s)0.0770.143

0.288


평균적으로 2배 정도의 속도 향상이 있었다고 볼 수 있겠습니다. 만약 텍스트에 띄어쓰기 없이 더 긴 단어들이 많다면 속도차이가 더 많이 나겠죠. 그래도 매 버전마다 2배정도씩 속도 향상이 있었네요. 더 속도를 향상시킬 만한 방법이 또 떠오르면 좋겠네요. 


최신 버전의 한국어 형태소 분석기 Kiwi는 https://github.com/bab2min/Kiwi 에서 소스코드 및 바이너리를 다운 받을 수 있고, https://lab.bab2min.pe.kr/kiwi 에서 데모를 실행해볼 수 있습니다.

이 댓글을 비밀 댓글로
    • 이승호
    • 2017.12.07 21:36 신고
    안녕하세요 좋은 게시글 올려주셔서 감사합니다.
    질문이 있는데 node들이 갖는 값들과 간선들이 갖는 값을 음수로 처리하신 특별한 이유가 있을까요?
    • 원래 간선에는 이전 형태소에서 다음 형태소로의 전이 확률이 들어가는게 맞습니다. 다만 실제로 연산시에 확률값을 그대로 넣을 경우, 출발지에서 목적지에까지 도달하기 위한 확률을 구하기 위해 모든 간선의 확률값을 곱해야합니다.

      반면 확률에 로그를 취할경우 곱하기 대신에 더하기로 로그 확률값을 구할 수 있죠. 최종적으로 필요한것은 확률값이 제일 높은 경로인데, 어차피 최댓값은 로그를 취해도 최댓값이기 때문에 계산이 간편한 로그를 취한 값을 사용하는 것입니다.
  1. 안녕하세요 컴퓨터공학을 전공하고있는 학생입니다. 저는 지금 자동자막 번역 기능을 만드는 프로젝트를 진행하고있는데 이에 (말뭉치에 없는 단어를 포함한) 명사를 추출하는 기능이 꼭 필요해서 인터넷을 뒤지다 나온 여타 다른 ㄲㄲㅁ, ㅌㅇㅌ, ㅋㅁㄹ 등등 유명한 형태소 분석기에서는 말뭉치에 없는 전문용어, 고유명사들, 복합명사는 너무 정확하게 분석을 하는 과정에서 나온 것인지 오버피팅때문인지 엉뚱한 분석을 하는 경향이 많았습니다. 그중에 깃허브에서 작성자께서 올리신 코드와 데모를 시연해보고 우수하면서 적합한 프로그램이라고 생각했고 블로그위의 "나의 큰 o는 logx야.."라는 글 밑의 문구에 감동했습니다. 제가 글을 올린 이유는 혹시 이 프로그램의 사용방법에 대해서 올리신 글이 따로 있으신지 여쭈어보려고 이 글을 올리게 되었습니다. 제가 부족한 탓인지 제가 c++을 사용하고 있는 환경에 그대로 실행시켜보니 밑의 빨간줄들과 함께 제대로 실행되지 않아서 말씀드립니다. 라이브러리도 필요없는 간편한 프로그램이었지만 제가 사용하기에 어려움이 있어서 혹시나 사용방법에 대한 글을 적어두신 곳이 있다면 가르쳐주신다면 감사하겠습니다.
    • 부족한 블로그를 찾아주셔서 감사합니다.
      먼저 전문용어, 고유명사, 복합명사의 분할 문제의 경우는 생각보다 어려운 문제입니다. 형태소 분석기를 사용하는 상황에 따라서 필요한 분석 수준이 다르기도 하고, 같은 단어라도 맥락에 따라 고유명사가 되어 분석하면 안될수도 있고, 일반명사로 형태소 분석을 해야하는 경우도 있기 때문입니다.
      Kiwi 역시 이 문제에서 자유롭지 못하다는 점 말씀드리구요, 사용에 앞서 이 점 인지하셔야겠습니다. github에는 조금 불친절하게 코드만 올라가 있는 관계로 사용이 조금 어려우셨을것 같습니다. 사실 1.0 버전이 완성되면 제대로된 문서화와 API 제공을 하려고 했는제 계속 늦어지네요.
      사용법에 관해서는 댓글로 달기 어려우므로 새로운 게시물에 정리해서 올리도록 하겠습니다. 관심가져주셔서 감사합니다!