Code Sprint 2014 Round 1 – query segmentation 출제 후기

안녕하세요, Text Analytics 팀 홍금원 매니저입니다. 이번 Code Sprint Round 1의 문제를 출제하면서 느꼈던 점과 있었던 일을 공유하고자 합니다.

query segmentation

Round1 문제는 쿼리를 정확히 분리하는 query segmentation문제입니다. 사용자는 검색을 할 때 여러 가지 이유로 띄어 써야 할 것을 붙여 쓰거나, 붙여 써야 할 것을 띄어 쓰는 경우가 많습니다. 이런 경우 검색을 성공시키기 위해 필요한 작업이 query segmentation입니다. 예컨대, kung fu는 kung과 fu를 띄어 써야 하지만 많은 경우에 붙어서 나타나고, pancake은 pan과 cake을 붙여 써야 하지만, 떼어져 나타나는 경우도 빈번합니다. 이러한 문제를 해결하기 위해서는 일단 검색 query로 들어온 모든 단어에 대해 띄어 쓰기를 검사해야 할 필요가 있습니다. 아래 그림은, 다음 예는, 사용자가 “coffeebean”을 질의에 붙여서 입력을 하더라도, 적합한 검색결과를 제공하는 것을 보여주는 예시입니다.

그림 1. coffeebean 검색 결과

이런 의미에서 본 문제는 우리말의 띄어쓰기 문제와 거의 유사하다고 할 수 있습니다. 하지만 단순히 우리말 띄어쓰기로 문제를 출제할 경우, 한글 및 한국어 처리에 관한 특별한 경험을 가진 분들이 비교적 유리 할 수 있다고 판단하여, 비교적 처리가 간단하고 모두가 함께 참여가 가능한 영어로 문제를 변경하였습니다. 하지만 언어가 영어로 바뀌었을 뿐, 문제를 접근하기 위한 핵심 아이디어는 변함이 없습니다. 또한, 곳곳에 수작업 교정이 가능하지 못하도록 fake word를 추가하여 출제를 했습니다. 종종 참가자 분들이 숨겨진 단어를 발견하여 facebook에 올려주기도 하셨습니다.

본 문제에 접근하는 가장 효과적인 방법은 “통계적 언어처리” 방법이라고 생각했습니다. 입상을 하신 세 분 모두 음절(영어의 letter 및 character)과 단어(영어의 word)정보를 n-gram의 형태로 표현을 하고, 이를 이용한 통계정보를 활용하여 segmentation에 적용을 했습니다. 통계정보의 예를 들면, n개의 character가 단어를 구성할 확률 또는 1개 또는 그 이상의 단어가 연속적으로 출연하여 문장을 구성할 확률 등을 사용하였습니다.

본 문제에 접근하기 위해 널리 알려진 방법이 궁금하시다면, “Beautiful Data”의 14장, 또는 “AI: A Modern Approach”의 22장을 참조하시면 좋을 것 같습니다.

Round 1에서는 73명의 참가자들이 답안을 제출했고, 총 답안은 133개였습니다. 따라서 참가자 1인당 약 2개의 답안을 제출했습니다. 정상적으로 평가한 62명의 평점 평균은 88.86으로 상당히 높은 편이라고 생각이 듭니다. 아마 train.txt만 사용하지 않고 train.qry도 함께 사용을 하여 tuning을 유도한 것이 성능 향상의 원인이지 않을까 생각해봅니다. 참가자 중 11분은 제출 답안 규정에 어긋나서 평가가 되지 않았습니다. 이 부분에 대해서 궁금하신 분들은 연락을 주시면 개인적으로 답변을 드리도록 하겠습니다.

입상하신 세분 모두 C++11을 사용하셨고, 상위 입상자 열 분을 놓고 보았을 때 개발 툴은 C++11과 Python이 거의 반 반을 차지한 것 같습니다. 아마도 속도 제한이라는 조건을 제가 달아 놓아서 학습과 테스팅에 소요되는 시간을 개발 툴로 풀고자 고민하신 것 같은데요, 사실은 이 부분은 크게 중요하지 않았다고 생각합니다. 상위 입상 열 분 모두 학습 시간이 평균 20초 이내, 테스팅 시간은 1초 이내였습니다.

문제를 준비하며

문제를 준비하며 가장 어려웠던 부분 중 하나는 데이터를 준비하는 일이었습니다. Text Mining과 관련된 많은 문제들은 정제된 학습 데이터와 평가 데이터가 필요한데요. 본 대회는 출제자가 이러한 것들을 함께 준비해야 하는 어려움도 가지고 있었습니다. 한국어로는 이미 많은 종류의 데이터를 보유하고 있었지만, 개인정보나 저작권 등의 문제로 데이터를 쉽게 제공하기 힘들 수 있어서 다른 차원에서 새롭게 데이터를 준비하게 되었습니다. 본 문제에 사용된 데이터는 해외 리뷰어들의 리뷰 글들이 많이 포함되어 있으며, 이들을 그대로 사용하는 대신, 문서, 문장, 단어들을 삽입, 삭제, 수정, 정렬의 과정을 거쳐 재 가공하였습니다.

또한, 자동으로 학습/평가 데이터를 생성하고, 다행스럽게 사내 많은 분들의 자발적인 도움으로 짧은 시간에 정제할 수 있었습니다. (일반적으로 규모가 있는 대회를 위해 학습 및 평가 데이터를 수작업으로 준비하는데 많은 시간과 비용이 소모됩니다.)

문제의 특징

Round 1의 특징 중 하나는, 기계학습 기법을 적용하고 평가하는 여느 대회와는 달리 training corpus외에 training query를 제공하여 training corpus와 training query사이의 연관성을 측정할 수 있도록 유도를 했다는 점입니다. 예를 들어 단순히 “단어 X와 Y가 띄어 쓸 확률이 붙여 쓸 확률보다 크면 띄어 써라” 라는 일반적인 규칙이 아니라, 좀더 실용적으로 접근합니다. 즉, training query나 test query를 만들 때 사용한 띄어 쓰기 확률은 19% 이었는데, 이는 대용량의 corpus에서 X와 Y사이의 띄어쓰기 확률이 19%이상이면 “XY”가 아닌 “X Y”를 정답이라고 가정했다는 의미입니다. 그리고, 이 threshold값을 활용하여 자동으로 training query 및 testing query를 생성할 수 있었습니다. 여기서 19%라는 수치는 저희가 사용한 약 100만 문장의 영어권 리뷰 corpus를 대상으로 한 검색의 품질을 성능을 높일 수 있도록 설정한 숫자입니다.

본 대회를 준비하면서 제가 가지고 있던 생각은, 텍스트 마이닝이라는 분야는 뭔가 생소하고 언어적 지식을 가지고 있는 제한된 사람들만이 하는 것이 아니라, 다양한 분야의 개발자들이 쉽게 접근하고 고민하면 비교적 빨리 정답을 구할 수 있다는 점을 보여드리고 싶었습니다. 그러면서도, 동시에 본 문제처럼 아주 간단히 단어를 분리하기만 하는 문제도 막상 직접 도전을 해 보면 생각처럼 쉽지는 않다는 사실도 깨달으셨을 것 같습니다.

마지막으로 올해로 세 번째를 맞이한 Code Sprint에 참여해 주신 모든 개발자 분들께 깊은 감사를 드립니다. 내년에는 “재미”의 요소가 보다 강조가 된 참신한 문제가 출제 되었으면 하는 바램이 있습니다. 모두 고생하셨습니다.

홍금원 Text Analytics팀

Text Mining 활용 시스템 발굴 및 적용 업무를 담당하고 있습니다.
Digital Contents 추천시스템 개발을 담당하고 있습니다.

공유하기