Kneser-Ney 언어 모형을 활용한 한국어 초성체 해석기 개발

사실 초성체 해석기에 대한 생각은 말년 병장 때 할일 없어서 처음 떠올렸었습니다. 세종 말뭉치 통계 자료가 때마침 있었고, (사지방 시간도 꽤 있었고) PHP를 굴릴 수 있는 웹 서버도 하나 가지고 있었기에, 간단하게 단어의 초성을 추출해서 P(단어 | 초성) 을 계산하는 방식을 선택하기로 했죠. 각각의 단어가 다 독립이므로, 문장을 추론하는데에는 하나도 도움이 안되는 단순 멍청한 모델이었다고 할 수 있겠죠. (열악한 환경에서 하루만에 만드려니 어쩔수 없었다고 변명을 대어봅니다.)

 

최근 Modified Kneser Ney Smoothing을 적용한 N-gram Language Model를 공부하면서 이를 초성체 해석에 사용할 수 있다는 걸 깨달았습니다. 시험 삼아 초성체를 해독하는 도구를 짜보았는데, 이것이 근본적으로 전에 개발한 형태소 분석기 Kiwi와 거의 유사했습니다. 도 생각보다 재미있는 결과가 나왔구요. 그래서 이렇게 포스팅을 작성하며 시스템을 공개하게 된 거죠. 본 포스팅에서는 KN Smoothing에 대해서 간략하게 정리하고, 이를 어떻게 웹 시스템에 붙였는지를 공유하도록 하겠습니다.

 

결과부터 봅시다 초성체 해독기! :  https://lab.bab2min.pe.kr/okiwi

 

Modified Kneser Ney Smoothing

N-gram 모델은 활용하기에 정말 쉽습니다. 학습 과정은 연속한 N개의 단어짝이 나오는 횟수를 세면 끝나고, 단어의 조건부 등장 확률을 구하는 것은 빈도수 간의 나눗셈만 수행하면 되니깐요. 예를 들어 A-B-C라는 순서로 단어짝이 총 10번 나왔고, A-B라는 순서로 단어짝이 총 100번 나왔다면, A-B가 등장했을때 다음에 C가 등장할 확률은 10/100 = 0.1이라고 간단하게 계산할 수 있죠.

당연히 더 많은 단어열을 조건으로 둘수록 더 복잡한 언어 패턴을 잡아낼 수 있으므로 성능을 높일 수 있을것 같지만, 치명적인 문제로 학습 코퍼스 내에 아예 등장하지 않는 단어열의 경우 항상 확률이 0이 되는 문제가 있습니다. 따라서 이 문제를 해결하기 위해 확률이 0이 되지 않도록 보간해주는 작업이 필요한데 이를 smoothing이라고 합니다.

 

여러 스무딩 기법 중 성능이 가장 좋은 것으로 밝혀진 것은 Kneser Ney Smoothing입니다. 이전 포스팅에서도 간략하게 설명드렸다시피(http://bab2min.tistory.com/599) Kneser Ney Smoothing은 Absolute Discounting을 통해 하위 차수의 n-gram 모델을 보간에 사용합니다.

 

여기서 대게 $0 \le d < 1$ 로 둡니다. 적절한 d값은 학습 코퍼스에 따라 달라지는데, 대게 MLE기법 등 최적화 기법을 통해 전체 학습 데이터에 대한 Likelihood가 최대로 되는 d값을 찾아서 사용하곤 합니다.

 

이 모형을 간단하게 풀어 설명하자면

• 1번 이상 등장하는 단어들에 대해 조금씩 확률을 걷어와서
• 전체 단어에 대해서 나눠주되, 그 나눠주는 비율은 (n-1)-gram 모델의 확률비를 따른다

가 되겠습니다. 이전 포스팅에서 설명했다시피 n-gram 언어 모델계의 일종의 사회 복지정책입니다.

 

Kneser-Ney Smoothing을 더 강력하게 개량한 기법이 있으니, 그것이 바로 Modified Kneser-Ney Smoothing입니다. 이는 Chen과 Goodman에 의해 1999년에 제안된 것으로^[각주:1] 기존의 KN Smoothing에서는 하나의 d값만을 사용했다면, 개량된 버전에서는 빈도수에 따라 다른 3종류의 d값을 사용해 성능을 더 높인것입니다.

 

 

($N_1(u\cdot)$는 $u\cdot$ 중 등장빈도가 1인 패턴의 수, $N_2(u\cdot)$는 등장빈도가 2인 패턴의 수, $N_{3+}(u\cdot)$는 등장빈도가 3이상인 패턴의 수입니다.)

기존 기법에서는 $C(uw)$가 몇이든간에 1이상이면 d를 뺏어갔다면, 이 기법에서는 $C(uw)$가 1일때는 $d_1$만큼, 2일때는 $d_2$만큼, 3이상일때는 $d_{3+}$ 만큼 뺏어가서 전체 단어들에게 재분배해준다는 것이죠. 그리고 Chen & Goodman은 전체 데이터가 주어졌을때 대체로 최적의 MLE을 보이는 d의 닫힌 해를 구하여 제시했습니다. 이로써 학습 과정에서 MLE를 실시할 필요 없이 더 빠르고 간단하게 학습을 진행할 수 있구요!

 

d의 닫힌 해는 다음과 같이 제시됩니다.

 

(여기서 $N_i(\cdots w)$는 w앞에 등장하는 단어열 패턴 중 등장 빈도가 i인 패턴의 개수입니다.)

 

이 방법을 통해 N-gram 언어모형의 성능을 극한까지 끌어올릴 수 있습니다. 최근 RNN을 활용한 RNN-LM이 등장하면서 N-gram 언어 모형의 정점을 넘어서는 성능을 보이고 있긴 하지만, 현실적으로 거대한 신경망을 가지고 학습을 하는것이 간단하지 않다보니, N-gram 모형도 여전히 실용적으로는 쓸모있는 녀석이라고 볼 수 있겠습니다. 그래서 저는 이걸 쓰기로 한것이구요!

 

참고 자료: http://smithamilli.com/blog/kneser-ney/

 

 

초성체 해석은 결국 단어열 맞추기이다

ㅊㅅㅊ ㅎㅅㅇ ㄱㄱ ㄷㅇㅇ ㅁㅊㄱㅇㄷ. 이 초성체를 어떻게 해석할 수 있을까요? 이는 우리에게 보이는 정보(초성들)를 바탕으로 보이지 않는 정보를 추론하는 작업이므로 근본적으로 Hidden Markov Model과 같습니다. 한글의 초성 하나에 대응하는 글자의 수는 21*28 = 588개이므로 은닉상태가 총 588개인 마르코프 모형을 통해 위의 초성체가 가질수 있는 보이지 않는 글자들의 확률을 계산할 수 있습니다. 다만 이렇게 하게 될 경우 Bigram 모형에서는 588*588가지의 확률 계산을 수행해야 하며, Trigram의 경우 588^3 경우를 따져야합니다. 현재 글자가 바로 앞글자의 영향만 받는다고 모형화하기에는 추론의 성능이 너무 낮을 것이고, 앞의 2글자의 영향을 받는다고 하기엔 이 모든 경우를 따지기가 어렵다는게 문제입니다.

 

그 대신! 초성을 적당히 나누어 단어로 쪼개보면 어떨까요? ㅊㅅㅊ는 ㅊ + ㅅ + ㅊ일수도 있지만 ㅊㅅ + ㅊ일수도 있고, ㅊ + ㅅㅊ일수도 있죠, 혹은 ㅊㅅㅊ 전체가 한 단어일수도 있구요. 해당 초성에 일치하는 실제 존재하는 단어의 갯수는 588^3개보다는 훨씬 적습니다. 따라서 분할 가능한 조합을 찾아서 해당 초성이 나타날 단어를 추려보는게 훨씬 경제적인 방법이죠. 근데 이거 어디서 많이 본 방법입니다? http://bab2min.tistory.com/580 이전에 개발한 형태소 분석기와 정확하게 일치하는 과정입니다.

 

형태소 분석기: 글자 -> 단어로 쪼갬 -> 적절한 형태소 부착

초성체 해석기: 초성 -> 단어로 쪼갬 -> 적절한 단어 부착

 

거의 동일한 과정을 거친다는 것을 확인하실수 있습니다! 따라서 전에 형태서 분석기 개발하던 노하우를 그대로 재활용할 수 있었어요!

 

모델 학습하기

모델 학습에는 세종계획 말뭉치 문어 텍스트(형태정보 부착), 구어 텍스트(형태정보 부착), 2018년자 나무위키 전문서 텍스트(Komoran으로 형태소 분석)을 사용했습니다. Trigram으로 단어 전이확률을 구했고, 이를 바탕으로 Modified Kneser Ney Smoothing을 진행했습니다.

 

품사 태그는 다 버리려고 했으나, 그럴 경우 나다(동사)와 나(대명사)가 구별되지 않는 것처럼 은근히 겹치는 형태가 발생하고 이것들이 같은 단어로 처리되어 확률 계산된다는 게 찜찜해서 최상위 범주(체언 N / 용언 V / 수식언 M / 독립언 I / 조사 J / 어미 E) 구분만 사용했습니다. 또한 문장의 마지막과 쉼표도 반영해야 정확한 초성체 해석이 가능할것 같아 . , ! ? 구두점도 학습 데이터에 넣었구요.

최종 학습 결과, 등장횟수가 적은 단어를 버리고 나니 서로 다른 단어의 수는 약 5만여개였습니다.

 

코드 최적화

실험은 python3로 진행했고, 잘 되는것을 확인하고 c++로 옮겼습니다. 웹 서버에 올려 공개하는 것이 목표였기 때문에 빠른 속도와 적은 메모리 사용량이 필수였습니다. 초성체 해석기의 알고리즘은 다음과 같습니다.

 

1. 추론 모델 로딩
2. 초성체 입력 받음
3. 초성체를 가능한 단어후보로 쪼개어 네트워크 형태로 변경
4. 네트워크 형태에서 가능한 단어 조합을 따져가며 확률 계산
5. 확률이 가장 높은 단어 조합을 가져와, 다시 단어로 이어붙이고 출력
6. Profit!!!

3번은 아호코라식 알고리즘을 통해서 진행됩니다. 이를 위해서 Trie 구축이 필요하구요. 이 Trie는 1번에서 로딩합니다.

4번은 Trigram 버전 Viterbi 알고리즘을 통해서 진행됩니다. 이 때 Trigram의 확률 계산이 필요한데 이는 Modified Kneser Ney Smoothing 된 값이어야 했습니다. 가장 좋은 방법은 전체 가능한 단어 조합 (50000의 3제곱)별로 확률 값을 저장해두었다가 바로 찾아서 이 값을 찾아오면 됩니다. 하지만 이렇게 하기 위해서는 총 500테라바이트의 메모리가 필요할 겁니다... 서로 다른 단어가 50000개라고 할 지라도 실제로 이들의 가능한 모든 조합이 전부 출현하는 것은 아니기에 모든 경우를 다 따져 저장해두는 것은 메모리 낭비! 시간 낭비겠죠

그래서 여기에도 변형된 Trie를 적용했습니다. A-B-C가 등장할 확률이 0.1이라면 A노드의 자식노드 B의 자식노드 C에 0.1이라는 값을 저장하는거죠. 그리고 만약 해당 값이 없을 경우에는 하위 차수의 확률로 가도록 트리를 설계했습니다.

가능하면 64bit 포인터 대신에 32bit나 16bit짜리 relative index 값을 사용하여 Trie의 크기를 줄였구요. 여러 가지 기법을 통해 초기 700MB의 메모리를 잡아먹던 문어체 모델을 190MB만 잡아먹도록 압축시킬수 있었습니다.

 

재미난 결과들!

ㅇㅈ ㅈㅇㅇㄷㅇ ㅁㅇ ㄴㅁ ㅇㄹㄱ ㅎ.(요즘 젊은이들은 말을 너무 어렵게 해.) 를 돌려봤습니다.

구어체에서는 이런 결과가 나왔습니다. 

 

문어체에서는 이런 결과가 나왔구요.

 

가장 많은 데이터를 사용한 나무위키에서는 이런 결과가 나왔습니다. 이게 제일 문장다운 표현이 나오긴 했습니다만 원래 의도한것이라는 좀 딴판이네요.

 

 

위키 데이터를 사용한 모델에서는 나름대로 유행어인 "햄최몇?"도 3위로 잡아내긴했구요 ^^.

 

초성체에 적합할만한 채팅 데이터나 편지류의 말뭉치가 있다면 이걸 학습시켜 사용하는게 참 좋겠습니다.

다시 한번 링크를 소개하며 여기서 끝! https://lab.bab2min.pe.kr/okiwi

1. Chen, S. F., & Goodman, J. (1999). An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4), 359-394. [본문으로]