Markov 모델을 이용하여 query segmentation문제 해결하기

안녕하세요. Code Sprint 2014 Round 1에서 3위로 입상한 박주원이라고 합니다. 이 글을 통해 Round 1 문제인 query segmentation을 제가 어떠한 방식으로 접근하고 해결했는지에 대하여 공유하고자 합니다.

초기 접근 전략

본 문제는 제목 그대로 검색 질의를 단어 별로 정확히 분리해내는 문제였는데요, 이를 위해 training corpus와 training query를 이용한 통계적 학습이 필요했습니다. 개인적으로는 이번 기회에 Text Analytics에 대한 기초적인 내용을 공부하면서 어느 정도 유의미한 결과를 내는 query segmentation 프로그램을 작성하는 것을 목표로 하였고 따라서 training corpus와 training query의 연관성을 처음부터 찾기 보다는 training corpus만을 통한 통계학습에 초점을 맞춰 접근하기 시작했습니다.

Markov 모델 이용하기

문제의 예에도 나오듯이 Google에서 coffeebean을 검색했을 때 coffee bean으로 분리하여 처리하는 것을 볼 수 있는데요, 이는 query segmentation이라는 문제가 현실 세계에 적용되어 해결된 하나의 예라고 볼 수 있습니다. 즉, 당연한 얘기겠지만 이러한 문제를 해결하기 위한 방법론들이 이미 존재한다는 것이고 저는 검색을 통해 Markov 모델이라는 것이 이런 류의 문제를 해결하는 데에 종종 사용된다는 것을 알 수 있었습니다. 결과적으로 Markov 모델을 이해하기 위해서 Coursera의 자연어처리 강좌를 보면서 학습을 했고 해당 내용을 응용하여 다음과 같이 임의의 segmentation에 대한 점수를 계산하였습니다.

먼저 thebestyakitorirestaurant 이 입력으로 들어왔다고 가정하겠습니다.

이 쿼리의 정답은 ‘the best yakitori restaurant’ 인데요 해당 segmentation이 등장할 확률이 다음 식을 따른다고 가정하는 것이 제가 사용한 확률모델의 핵심입니다. 물론 이는 엄밀한 정의를 따르는 것이 아닌 통계에 기반하여 근사한 방법이고 어느 정도 좋은 결과를 내려면 충분한 양의 corpus가 확보되어야 함을 전제로 합니다. 당시 이러한 모델링이 어느 정도의 퍼포먼스를 낼지는 전혀 예측하지 못했고 일단 빠른 구현을 통해 결과를 확인해보자는 생각이었습니다.

P(the best yakitori restaurant) = P(the) * P(best | the) * P(yakitori | best) * P(restaurant | yakitori)

P(X) = 단어 X의 출현 확률

P(Y | X) = 단어 X가 출현했을 때 다음 단어로 Y가 출현할 확률

여기서 P(X), P(Y | X)는 다음과 같이 corpus내 단어들을 이용해서 구합니다.

P(X) = X의 출현 빈도 / corpus의 단어 수

P(Y | X) = X Y 의 출현 빈도 / X의 출현 빈도

이제 임의의 segmentation을 평가할 방법을 찾았으니 입력으로 들어온 쿼리를 가능한 모든 방법으로 분리해보고 그 중에서 점수가 가장 큰 segmentation을 출력하면 되겠습니다. 즉, ’th ebes tyakitorirest aurant’, ’thebes ty akitorires ta ur ant’ 등 모든 경우의 수를 보겠다는 전략인데요 사실 꽤나 많은 segmentation 후보가 생성되기 때문에 실제 구현에서는 동적계획법(Dynamic Programming)을 이용하여 성능을 최적화 하였습니다.

등장하지 않는 단어들에 대한 처리

이제 위 모델링으로 실제 프로그램을 작성해야 하는데요, 구현하기에 앞서 큰 문제점을 발견할 수가 있습니다. 그 문제점은 corpus에 등장하지 않는 단어에 대해서는 확률 P를 구할 수가 없다는 사실입니다. ‘th ebes tyakitorirest aurant’를 예로 들어보면 단어 ‘ebes’는 실제 존재하는지 아닌지는 알 수 없지만 어쨌든 corpus에 등장하지 않기 때문에 위의 방법을 이용할 수가 없고 따라서 이 segmentation의 점수를 측정할 수가 없습니다. 이를 처리하기 위해 저는 ‘임의의 단어 X에 대한 타당성’을 평가해주는 함수를 만들어 사용했고 이 또한 통계적 근거를 기반으로 합니다. 예를 들어 corpus에 gooooood이나 woooooooow같은 단어들이 등장한다면 looooooool의 경우 corpus에 등장하지 않더라도 타당성 평가 함수에 의해 높은 점수를 받을 확률이 커지게 됩니다. 이러한 함수를 만들기 위해 이번에는 음절(letter) 기반의 확률모델을 사용합니다. 이는 단지 위에서 설명한 단어 기반 모델의 원리를 한 단어 내에서 음절 단위로 사용한 차이점밖에는 없습니다.

단어 기반의 모델을 음절 단위로 바꾸면 ‘zhejiang’의 경우 다음과 같이 계산이 됩니다.

P(zhejiang) = P(z) * P(h | z) * P(e | z h) * P(j | h e) * … * P(g | a n)

기본적으로 단어 기반의 확률모델과 동일한 형태를 따르고 있지만 trigram까지를 사용하고 있는 것이 차이점입니다. 즉, x y -> z의 transition까지 보는 구조입니다. 위 식에 따르면 zxcvpqqq같은 단어의 경우 P(c | z x)만 봐도 0에 가까운 확률을 가질 것이기 때문에 단어 zxcvpqqq의 존재 가능성은 굉장히 낮을 것이라 예측할 수 있습니다.

최종 모델

실제 구현을 할 때에는 위에서 살펴본 확률모델들을 기반으로 임의의 세그멘테이션 S를 평가해주는 함수 F를 만들어 사용했는데요 대략적인 내용은 다음과 같습니다.

F(S) = F(W1 W2 W3 … Wn) = F(W1) * F(W1 W2) * F(W2 W3) * … * F(Wn-1 Wn)

F(X Y) = C1 * P(Y | X) + F(Y)

F(X) = C2 * P(X) + C3 * G(X)

C1, C2, C3 =  상수

G(X) = 단어 X의 타당성 평가 함수, 단어 X가 단어 Y보다 통계적으로 타당한 문자배열을 가지고 있다면 G(X) > G(Y)의 결과를 가집니다.

프로그램의 기본적인 흐름은 F(S)가 최대가 되는 segmentation을 찾아 출력하는 것이고 초기 구현을 마친 후에는 상수들에 대한 튜닝을 하면서 정답이 나와있는 training query를 이용하여 알고리즘의 성능을 계속적으로 평가하였습니다. 물론 test query에 대한 결과를 제출하기 위해서 training query의 정답들 또한 학습하여 최종 결과를 내는 데에 이용하였고 운이 좋았는지 그 외 추가작업 없이도 꽤나 높은 점수가 나와주었습니다.

후기

처음에는 개인적으로 어느 정도 만족할만한 수준의 query segmentation 알고리즘을 만드는 게 목표였는데 운이 좋았는지 입상까지 하게 되어 영광입니다. 어떻게 보면 간단하다고 할 수 있는 모델로 전체 쿼리의 90%이상을 올바르게 처리할 수 있다는 사실이 굉장히 신기했고 다른 분들의 접근 방법을 보면서 또 많이 배웠습니다.

국내 기업들의 경우 이러한 알고리즘 대회를 개최하는 경우를 거의 보지 못했는데 매년 흥미로운 문제들로 Code Sprint를 준비해주시는 관계자 분들께 참가자 중 한 명으로서 감사의 말씀을 드립니다. 내년에는 더 많은 개발자 분들께서 참여하시면 좋겠다는 바람을 가지고 있습니다. 내년 대회도 기대하겠습니다! 감사합니다.

박주원

리디북스에서 소프트웨어 엔지니어로 일하고 있습니다. 개인화 서비스에 많은 관심을 가지고 있습니다.

공유하기