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

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

하나의 단어를 형태소로 쪼개다보면 일치하는 패턴이 여러개 등장하는 경우가 많습니다. 예를 들어 '디자인하여' 라는 어절을 쪼개보면

디자인하여 => 디자인 + 하 + 아

가 되는데, 각각의 덩어리에 일치하는 형태소 목록은 다음과 같아요.

디자인	하	아
디자인/NNG	하/VV	아/EC
	하/XSV	아/EF
	하/XSA	아/IC
	하/NNG	...

'하'와 '아'의 경우 일치하는 녀석들이 더 많지만 여기서는 설명의 단순화를 위해 위와 같다고 하겠습니다.

이 경우 조합 가능한 모든 경우의 수는 12가지가 되겠죠. 하지만 디자인하여는 디자인/NNG + 하/XSV + 아/EC로 분석되는게 맞습니다. 그러면 12가지 중에서 NNG + XSV + EC가 가장 적합한지를 어떻게 판단할 수 있을까요?

확률 모델

이를 위해 확률 이론을 사용합니다. 베이즈 정리나 마르코프 체인처럼 복잡한 개념이 잔뜩 있지만, 어려운 이론적 배경은 생략하고 아이디어만 정리해보자면 다음과 같습니다.

디자인/NNG + 하/XSV + 아/EC 가 등장할 확률은

(디자인/NNG가 등장할 확률) * (하/XSV가 디자인/NNG 뒤에 등장할 확률) * (아/EC가 하/XSV 뒤에 등장할 확률)이 되겠죠. 한 형태소는 바로 앞의 형태소로부터만 영향을 받는다고 가정을 한겁니다. (마르코프 모델)

그런데 문제는 학습용 코퍼스에서 (하/XSV가 디자인/NNG 뒤에 등장하는 경우)는 매우 드뭅니다. 거의 몇 건 안될 거에요. 만약 이보다 더 흔치 않게 등장하는 형태소 쌍이 있다면 그 경우는 0에 극도로 가까워지겠죠. 그래서 사실상 한 형태소 뒤에 다른 형태소가 나타날 확률을 소규모의 학습용 코퍼스에서 얻는것은 불가능하다고 봅니다. (하/XSV가 총 1000번 등장했는데 디자인/NNG 뒤에서 등장한 경우는 1~2번이 간신히 될까말까하다는 거죠.)

그러니 하/XSV가 디자인/NNG 뒤에서 등장할 확률이 XSV가 NNG뒤에서 등장할 확률가 비례할거라 가정하고, XSV가 NNG 뒤에서 등장할 확률로 대체해서 사용하도록 합시다. 즉 (하/XSV가 디자인/NNG 뒤에서 등장할 확률) => (하/XSV가 등장할 확률) * (XSV가 NNG 뒤에서 등장할 확률)가 되겠죠. 마찬가지로 아/EC가 하/XSV 뒤에서 등장할 확률도 바꿔치기 할 수 있어요.

한국어 맞춤법 상 어절을 마치는 형태소는 정해져 있습니다. 동사의 경우 먹다, 먹어처럼 어미로 어절이 끝나지, '먹' 만으로 어절이 구성되는 경우는 없습니다. 따라서 '먹'을 보면 먹/NNG로 해석해야지 먹/VV으로 해석하면 안되겠죠. 이를 위해서 해당 품사로 어절이 끝마칠 확률을 덧붙여주면 성능이 더 좋아지겠죠. 이를 위해 어절의 끝에 종결 표식 $를 붙여서 표현할게요.

따라서 디자인/NNG + 하/XSV + 아/EC 가 등장할 확률은

(디자인/NNG가 등장할 확률) * (하/XSV가 등장할 확률) * (아/EC가 등장할 확률) * (XSV가 NNG 뒤에 등장할 확률) * (EC가 XSV 뒤에 등장할 확률) * ($가 EC뒤에 등장할 확률) 로 추정할 수 있습니다.

간단하게 수식으로 정리해보자면 N개의 형태소 배열이 등장할 확률은

(M_1 ~ M_n은 각각의 형태소. T_1 ~ T_n는 해당 형태소의 품사, T_{n+1}은 종결 표식입니다.)

P(M_i)를 형태소 등장확률, P(T_i+1|T_i)를 품사간 전이확률이라고 부르기로 하죠. 이 방식대로 형태소 분석을 하기 위해 우리가 사전에 알고 있어야 하는 확률 모델은 이 2가지입니다. 다행히도 이 값들은 세종 계획에서 구축된 코퍼스를 통해 쉽게 계산될 수 있죠. 약간의 파이썬 코드를 활용하면 어렵지 않게 확률 모델을 구해낼 수 있을겁니다.

양변에 로그를 취해주면 곱셈을 모두 덧셈으로 바꿀 수 있습니다. 빠른 계산을 위해서는 곱셈보다 덧셈을 지향해야겠죠. 따라서 앞으로 모든 확률은 확률 값을 그대로 쓰는게 아니라 로그를 취한 확률값을 쓰는걸로 하겠습니다.

다시 '디자인하여'를 형태소 분석하는 일로 돌아옵시다. 우리는 가장 그럴싸한 형태소 조합을 찾기 위해 12가지 조합의 경우에 대해 모두 확률을 계산하고 그 중 확률이 가장 높은 녀석으로 결과를 골라주면 됩니다. 계산할게 많아서 귀찮겠지만 컴퓨터가 할 계산이니깐 문제 없습니다.

하지만 이렇게 해서 처음 코드를 작성하자 분석에 너무 시간이 오래 걸렸습니다. 어절 내의 형태소가 개수가 늘어날때마다 조합가능한 수는 기하급수적으로 증가하게 되죠. 그 결과 조금만 긴 어절이 나오면 모든 조합을 검사하느라 시간을 너무 많이 낭비하게 되어버린거죠. 하지만 검사하는 조합들 중 상당수는 탈락할 후보들이기에 굳이 검사할 필요가 없는 경우가 있습니다. 이를 사전에 제거하면 성능을 향상시킬 수 있을텐데...

결합 조건 검증

한국어의 조사는 바로 앞 단어의 받침 유무에 따라서 결합여부가 달라집니다. '은,이,을' 은 앞에 받침이 있는 경우, '는, 가, 를'은 받침이 없는 경우만 결합 가능하죠. 비슷하게 어미는 동사의 극성(양성/음성)에 따라서 결합여부가 달라집니다. '었'은 음성인 동사에, '았'은 양성인 동사에 붙어요. 이런 결합조건을 가지고 사전에 결합 불가능한 조합을 배제하면 성능을 향상시킬 수 있을 겁니다.

이런 단어가 얼마나 있을까요? 저도 잘 모르겠네요. 그래서 세종 계획 코퍼스를 분석해서 조사와 어미가 등장하는 양상을 살펴보도록 파이썬 코드를 짰어요. 앞 단어가 받침이 있는 경우 등장하는 비율과 받침이 없는 경우 등장하는 비율, 양성인 경우 등장하는 비율과 음성인 경우 등장하는 비율을 살펴서 한쪽으로 비율이 치우친 경우 (90%이상인 경우) 그 형태소에 표시를 매겨 모델에 포함시켰습니다.

그리고 실제로 분석 시에 그 모든 형태소 조합의 확률을 계산하지 않고 조건을 만족하는 경우만 고려하기로 했죠. 그래서 속도가 얼마나 빨라졌냐구요? 불행히도 크게 빨리 지지 않았습니다. (대신 정확도는 상당히 올라갔네요.) 아직까지도 어절이 길어지면 분석할 형태소 조합이 기하급수적으로 증가해서 알고리즘을 고치지 않고선 해결할 수가 없는 지점에 도달한거죠.

다음 글에서는 알고리즘적인 부분에서 어떤 꼼수를 썼는지 살펴보도록 하겠습니다.