Machine learning에 도전해보기!

안녕하세요, 2014 SK planet Code Sprint Round 1에서 2위에 입상한 송은진이라고 합니다.
문제의 설명이나 의도는 출제자 분의 해설에 잘 설명되어 있어, 제가 해답을 구한 과정을 설명하고자 합니다. Round 1 에서 제가 문제를 해결했던 모든 과정이나 수치를 적는 것은 무리가 있어, 대략적인 방법 위주로 봐주시길 바랍니다.

Day 1-2: 준비

Machine Learning을 제대로 공부해 본 적도 없고, 비슷한 문제를 다뤄본 적도 없어서 우선은 유사한 문제에 대한 방법을 찾아보기로 하였습니다. “Query Segmentation”, “Word Segmentation”, “Word Spacing” 등의 검색어를 조합해서 검색해보니, 독일어나 중국어 등을 Spacing하는 자료만 계속 나와서 어떻게 할까 하다가, “Corpus” 등의 검색어를 추가해서 좀 더 찾아보니 Round 1 문제에 적용할 수 있을 것 같이 보이는 자료를 찾게 되어 일단은 구현을 해보기로 하고 C++로 구현을 시작하였습니다.

Day 3-4: 전반

자료에서는 대회에서보다 훨씬 더 크고, 충분한 양의 corpus를 기반으로 하기 때문에, corpus에서 일정한 수 이하의 빈도를 가지는 token은 버리게 되어있지만, 약 10만 라인의 대회 corpus에서 그런 부분을 버리기에는 데이터가 충분하지 않아, 저는 버리는 루틴은 적용하지 않았습니다. 자료에 나오는 “memo”(memoization)를 구현하는 것에는 C++11에 적용된 `unordered_map<string, int>`를 이용하여 쉽게 구현하였습니다. Memory도 bigram까지 구현하기에 부족하지 않아서, 사실 처음에는 학습을 진행하는 코드와 테스트를 진행하는 코드가 하나의 프로그램으로 작성되어 한번에 동작하도록 되어 있었습니다. 나중에는 대회 규정(학습시간, 실행시간 규정)을 따르기 위해 분리도 하고, 각각을 따로 튜닝 하기도 했습니다.

Bigram까지 구현을 한 뒤에, train.txt에 대해서만 학습을 진행하여 train.qry를 테스트하니 QA가 88% 정도 나왔던 것으로 기억합니다.

그 이후로는, 추가로 사용한 자료 없이 train.txt만 이용해서 train.qry의 QA를 높이는 쪽으로 튜닝을 진행했습니다. train.qry도 “정책”을 학습하기 위해 자료로 사용해야 하지만, 출제자 분께서 데이터를 만들 때 train.qry의 데이터를 학습하지 않고 진행하였을 것이라 생각되어 train.qry는 학습대상에서 일단 제외 하였습니다.

튜닝을 진행했던 방법을 간략히 설명하면, 틀린 데이터만 따로 뽑아내서 자주 보이는 루틴이나 corpus에서 많이 등장함에도 틀리게 되는 부분을 찾아 해당 데이터가 정답이 나오면서 전체적인 점수가 나빠지지 않는 쪽으로 진행했습니다. 예를 들어, “I” 같은 경우 정상적으로 적용한다면, 한번도 등장하지 않은 단어에 i가 등장할 경우 높은 확률로 공백이 들어가게 됩니다. 그 외에 문장의 구성요소로 자주 등장하는 문자열 같은 경우에도, corpus내에 빈도 수를 그대로 적용한다면 당연하게 쪼개지게 됩니다. 이런 부분을 해결하기 위해 빈도수의 Cap을 지정하고, 등장하지 않은 단어의 가중치를 조정하는 식으로 조금씩 개선해 나갔습니다.

시간을 많이 두고 튜닝을 계속 진행한 결과 train.txt로만 학습한 train.qry의 점수가 94~95점쯤 나왔던 것 같습니다.
첫 번째 제출은 train.qry의 정답 부분을 따로 가중치를 더 주는 등의 처리를 하지 않고 corpus 데이터와 같은 방식으로 학습하여 나온 결과를 제출한 것이었는데, 의외로 결과가 나쁘지 않았습니다.

Day 5-6: 후반

Corpus 데이터를 따르지 않는 “정책”을 적용하기 위해 train.qry를 학습시키는 루틴을 추가하였습니다. 여기서 train.qry의 정답의 unigram과 bigram의 가중치를 얼마로 할 것인가가 문제였는데, 5일째에 이 부분만 바꾸어 세 개의 답을 제출하기도 하고, 여러 가지 테스트도 해보면서 결정하였습니다.

그리고 여전히 모르는 단어의 경우 사정없이 쪼개지고 있는 문제를 해결해야 했습니다. 길이가 5인 문자열이 공백 2개가 들어가 세 부분으로 쪼개지고 있는 그런 상황이었는데, corpus가 순수한 영어가 아니다 보니 다른 언어의 두 글자로 되어있는 문자열들이 원인이 되는 것 같았습니다. 그렇다고 그런 부분을 무시하기에는 query에 해당 문자열이 아예 등장하지 않는 것도 아니었고, 기존 코드에서 모르는 단어의 가중치를 조절하는 것만으로는 해결할 수가 없었습니다. 이것을 해결하기 위해 train.qry의 정답 부분에서, 길이가 l인 문자열이 n개로 쪼개지는 빈도 데이터를 추출하여 가중치를 적용하는 부분에 적용함으로써 답의 품질을 향상할 수 있었습니다. 또한 train.qry에 등장한 정답이 test에서 쪼개지는 것을 막기 위해서 unigram의 빈도가 일정한 수 이상인 경우, 해당 unigram에 공백을 추가해서 만들어진 bigram의 데이터를 아예 취급하지 않도록 작성한 부분도 있습니다.

숫자의 경우도 쿼리에 간간히 등장하고 있는 것을 확인할 수 있는데, 저의 경우는 숫자끼리는 전부 붙이는 정책만 간단하게 사용하였습니다. 또 영어 문장에서 자주 등장하는 (‘ `) 의 경우에는 그냥 무시하고 다 붙여서 쓰는 것으로(I’am=>Iam) 하였는데, corpus에 (A’s B)로 등장하는 문자열이 train.qry에 (asb, as b) 이렇게 나뉘어져서 그렇게 결정했던 것 같습니다.

한 개였던 프로그램을 학습을 진행하는 부분과 테스트를 진행하는 두 개의 프로그램으로 나누고, 나뉘면서 발생한 중복코드에 각각 다시 상수 튜닝을 진행하여 제출하였습니다.

후기

마지막 2,3위 점수가 거의 같아 놀라기도 했고, 또 이렇게 입상한 것이 오랜만이기도 해서 기쁘기도 했습니다.  출제자 분 말씀대로 모두가 가볍게 Machine learning을 접해볼 수 있었던 문제였던 것 같고, 아마 데이터가 충분히 많거나 실제 query 데이터가 공개되지 않았다면 결과가 달랐을 것 같습니다.
제가 튜닝 된 상수나 더해진 모듈에 대해 별다른 이론적 지식을 가지고 있는 것은 아니지만, 점수를 높게 받는 것이 대회의 목적이고, 점수를 채점해 볼 수 있는 데이터와 채점 방식이 제공되었기 때문에, 시간과 노력을 들여 꾸준히 점수를 올림으로써 다른 분들 사이에서 제가 입상할 수 있었던 것 같습니다. 출제자 분과 다른 참가하신 분들 모두 수고하셨습니다!

송은진

서울대학교 컴퓨터공학부 대학원에서 석사과정을 하고 있습니다.

공유하기