안녕하세요. SK planet Code Sprint 2014 Round 1에서 1위에 입상한 류원하입니다. 2012년 1회 대회때 Round 1에서 우승한 뒤로 두 번째로 우승하게 되어 감격스럽습니다. 무엇보다 매년 좋은 상품과 더불어 국내에서 흔치 않은 대회를 열어 주시는 점에 대해 SK planet 측에 진심으로 감사의 말씀을 드립니다.
저는 이 글을 통해 제가 어떻게 문제를 풀었는지에 대해 많은 분들이 이해하실 수 있도록 가능하면 문턱을 낮춰 설명하려 합니다. 제가 알기로는 저를 포함해 1위부터 4위까지의 접근은 큰 틀에서 비슷한데요, 전체적인 기본 접근 방법을 스케치하고 고득점을 하기 위해 제가 특별히 신경쓴 부분이 무엇이 있는지 하나씩 살펴보도록 하겠습니다.
문제: Text Segmentation
우선 문제에 대해 간략히 짚고 넘어가겠습니다. 이번 문제를 제 표현으로 다시 풀어 쓰자면:
우리는 (가상의) 검색 엔진에서의 검색을 위해 띄어쓰기 없이 입력된 문자열을 적절한 단어의 나열으로 구분하고자 한다.
다시 말해, "yummychickenrice"라는 문자열을 "yummy chicken rice"로 분리하고자 한다.
해당 검색 엔진은 영문을 바탕으로 하지만, 일부 아시아권 식당과 음식을 검색하기 위한 특수한 목적으로 활용될 예정이다.
따라서 구분 알고리즘은 일반적인 영어 지식을 활용하는 것이 아닌 해당 문제 도메인에 맞게 조율될 필요가 있다.
예를 들어, "jiaxiangkuching"은 "jia xiang kuching"으로 구분되어야 한다.
또한, 구분하는 방법이 여러 개 있을 때에는 그 구분 방법에 따라 검색 품질이 달라질 수 있으므로 적절한 것을 취해야 한다. 이를테면,
"cheeseburger"는 "cheese burger"가 되어야 하며,
"beancurd"는 "bean curd"가 되어서는 안 된다.
이러한 구분 방법을 학습하기 위해 다음과 같은 내용이 주어진다.
문제 도메인에서 얻은 영어 평문 더미(corpus)
약 1만건의 문자열에 대한 이상적인 구분 결과
우리가 구분해야 할 1만건의 공백 없는 문자열
이렇게 구분한 결과는 네 가지 채점 기준에 25%씩 반영된다.
QA: 각 문자열마다 맞으면 1점, 틀리면 0점으로 전체의 비율을 계산
CA: 두 문자의 사이마다 공백이 있어야 할 때 있고 없어야 할 때 없다면 1점, 틀리면 0점으로 전체의 비율을 계산
WR: 모든 정답 단어 중 맞춘 것의 비율
WP: 모든 제출한 단어 중 맞춘 것의 비율
위와 같은 문자열 구분 문제는 일반적으로는 Text Segmentation이라 불리는 이름이 있습니다. 그러니 여러 가지 방법에 대해 연구된 바가 많겠죠? 하지만 이 문제의 경우 다음 이유로 기존의 방법을 그대로 적용하기 어렵습니다:
제공된 데이터의 크기가 매우 작습니다. 7MB 가량의 corpus 텍스트 파일과 1만건의 쿼리로는, 우리가 세상에 존재하는 단어들을 웬만큼 알아낼 방법이 없습니다. 그 중 극히 일부분만 알아낼 수 있겠죠. 또한 도메인에 특화된 문제를 해결해야 하는 취지에 걸맞게 외부의 자료나 문법 지식 등의 활용이 엄격히 금지되었습니다.
일반적이지 않은 고유명사들이 매우 많습니다. 도메인이 아시아권 식당과 음식에 주로 걸쳐져 있어서 그렇습니다.
위와 같은 이유로 기존의 방법을 어느 정도 이해하고 적용하는데다가 문제의 취지에 맞는 여러 개선 방법을 택해야 좋은 결과를 얻을 수 있었으리라 생각합니다.
쉽게 변형한 문제 먼저 풀기
만약 세상에 있는 단어들을 전부 다 안다고 가정하면 어떻게 해결할 수 있을까요? "realityours"라는 문자열을 예시로, 이 문자열이 구분가능한지 불가능한지를 먼저 어떻게 풀 수 있는지 보도록 하겠습니다. 이 문자열을 구분했을 때, 첫번째 단어는 분명 다음 중 하나일 것입니다.
r
re
rea
real
...
reality
...
realityours
이들 중에서 올바른 단어인 것도 있고, 올바르지 않은 단어인 것도 있고, 긴가민가 하는 단어도 있을 것입니다. 일단은 당장의 문제에 집중하기 위해 온 세상에 있는 단어가 {real, reality, it, ours} 뿐이라고 생각해 봅시다. 그렇다면 저 11가지 후보들 중에서 실제로 가능한 것은:
real
reality
이 둘 뿐이겠지요? 그런데, 실제로 "real"로 시작하는 분리 방법이 있으려면 나머지 부분인 "ityours" 를 구분할 방법이 있어야 합니다. 다시 말해 우리는 "realityours"라는 문자열을 구분하는 문제를 풀기 위해서 "ityours"라는 부분 문제를 풀어야 하는 것이죠. 그러므로 만약 우리가 어떤 문자열을 쪼개는 올바른 방법이 있는지 없는지를 알아내는 segmentable?(x)라는 함수와 올바른 단어인지 판단하는 word?(x)가 존재한다고 가정하면, segmentable?("realityours")는 이런 식으로 계산할 수 있을 것입니다:
이들 중 word?()가 참인 것은 둘 뿐이었으므로 결과적으로 segmentable?("ityours") 와 segmentable?("ours")를 알 수 있으면 됩니다. 같은 방식으로 생각하면 우리의 올바른 선택은 "reality ours"뿐임을 알 수 있죠. 빈 문자열이 구분가능한지는 참으로 둔다는 사실을 기억하시기 바랍니다 (segmentable?("")은 참)
생각해 보면, segmentable? 함수의 인자는 항상 "realityours"라는 최초 문자열의 접미 문자열(suffix)일 것입니다. 앞에서부터 단어를 하나씩 빼가고 있으니까요. 이를 조금 더 직관적으로 계산하기 위해 우리는 D라는 수열을 하나 잡아서, D_i가 segmentable?("realityours"[i..end])라고 할 수 있습니다. 이렇게 하면,
와 같이 표현할 수 있겠지요. 보통 프로그래밍 언어에서는 배열을 활용해 이런 수열을 저장할 수 있으므로, 배열 D가 있다면 아래와 같은 형태가 되겠죠?
D[0]
D[1]
D[2]
D[3]
D[4]
...
D[7]
...
D[11]
True
False
False
False
False
...
True
...
True
우리가 위에서 보았듯 D[i]를 계산하기 위해서 D[i+1]부터 D[11]까지 알아야 했기 때문에, 뒤에서부터 거꾸로 계산하면 모든 값을 구할 수 있습니다. 이와 같이 문제를 작은 부분 문제로 나누고, 순서대로 잘 계산해서 목표로 하는 원래 문제를 푸는 패러다임을 동적 계획법이라 합니다.
실은 우리가 "realityours"가 구분가능한지 불가능한지만 알아낸 상태이고, 어떻게 구분하는지에 대한 방법은 아직 알아내지 않았습니다. 조금만 생각해 보면 크게 어려운 문제는 아니지요. D[0]이 참인 까닭은 word?("reality")와 D[7]이 모두 참이었기 때문입니다. D[7]이 참인 까닭은 word?("ours")와 D[11]이 모두 참이었기 때문이고요. D[11], 빈 문자열은 그냥 그 자체로 참이라고 두었습니다. 따라서 이와 같이 무엇 때문에 참이 되었는지를 기록해 두거나 다시 계산해 알아낸다면 결과가 "reality ours"임을 역추적해나갈 수 있습니다.
현실적인 문제 풀기
아쉽지만 실제로는 위의 이상적인 경우와는 조금 차이가 있습니다.
올바르게 분리하는 방법이 여러 가지일 수 있습니다. 사실 스크래블 같은 단어 게임을 해 보면, 세상엔 참 많은 알파벳 조합이 단어가 됨을 알 수 있습니다.
우리가 세상에 존재하는 모든 단어를 알 방법이 없습니다.
1번의 경우를 좀 더 생각해 봅시다. 우리가 온 세상에 {real, reality, it, ours}의 네 단어밖에 없다고 가정했었는데, 여기에 "yours"라는 단어가 신조어로 등장하였다 하면 골치가 아파집니다:
reality ours
real it yours
이것들 중 어떤 것이 맞을까요? 둘 다 맞기는 하지만, 어느 것이 더 "적절"할까요?
이러한 문제를 해결하기 위한 방법 중 하나는 각각의 확률을 생각하는 것입니다. 온 세상에 "reality ours"라는 텍스트가 등장할 확률과, "real it yours"라는 텍스트가 등장할 확률을 각각 구하고, 그들 중 큰 것을 택하기로 하는 것입니다. 물론 이 확률을 구하는 것은 무지하게 어렵습니다. 단순히 데이터에서 빈도를 센 것이 확률이냐고 물을 수도 있을 테고요.
사실 정확한 확률이란 있을 수가 없습니다만, 대충 그럴듯하게 구하기만 해도 데이터가 많다면 충분히 좋은 결과를 얻을 수 있습니다. 예를 들어 우리가 어떤 텍스트 x가 등장할 확률을 p(x)라고 하고, 각 단어는 전부 독립적이어서 실제로 각 단어가 등장할 확률을 전부 곱해서 얻을 수 있다고 근사한다고 생각해 봅시다. 다시 말해, 우리가 {real, reality, it, ours, yours} 각각의 단어에 대해 등장할 확률을 알고 있다면, 이걸 곱해서 두 구분 방법 중 어느 것이 더 그럴듯한지를 알아낼 수 있겠죠. (사실 확률들에 로그를 씌우면 곱셈이 덧셈으로 바뀌는데, 단어들에 그럴듯한 "점수"가 있고 이 점수를 더해서 가장 큰 점수를 얻는 구분 방법이 무엇이냐? 라는 문제로도 생각할 수 있습니다. 각색하자면 수평선 위에 집들이 몇 개 있는데, 이 수평선을 몇 조각으로 나누어 각 조각마다 하나씩 그 조각 안의 집들을 관리하는 소방서를 짓는다고 생각하는 문제와 같습니다.)
아무튼 이런 생각에는 근거가 아주 없는 것은 아니고, 실제로 텍스트가 생성되는 것이 마치 사전에 단어별 출현 빈도를 별표로 표시해 두고(별 세개는 아주 자주 나오니 중학교 수준 단어 하는 식으로요) 그 출현 빈도에 따라 단어를 랜덤하게 추출한다고 가정하는 모델을 바탕으로 하고 있습니다. 이러한 모델을 현실적으로 반영할 수 있다면 품질이 당연히 올라가겠죠?
당연하게도, 위와 같은 모델은 현실과는 거리가 있어서 우리의 최종 문제를 해결하는 데 약간의 장애가 있습니다. 도입부에서 문제를 설명할 때에 말씀드렸듯, "cheeseburger"는 "cheese burger"여야 하고 "beancurd"는 "bean curd"가 아니어야 하니, 각 단어를 독립적으로 가정해서는 안 됩니다. 앞선 방법을 조금만 비틀면 생각을 달리할 수 있습니다. "real it yours"라는 텍스트가 등장할 확률은 "real"이 등장할 확률, "real it"이 등장할 확률과 "it yours"가 등장할 확률의 곱이라고 보는 것입니다. 왜 이런 가정을 할 수 있을까요?
이론적으로 말해서, 이것은 우리의 확률 프로세스를 마르코프 프로세스라고 보는 것입니다. 쉽게 말하자면, 다음 단어는 그 전 단어가 무엇이냐에 따라 다르게 결정된다고 생각하는 것인데요, "beer"라는 단어나 "burger"라는 단어가 나올 확률이 어떻든 간에, "cheese" 다음에는 "beer"보다는 "burger"가 나올 확률이 훨씬 높다고 보는 것입니다. 이렇게 보더라도 현실과는 거리가 어느 정도 있지만, 충분히 좋은 근사가 됩니다.
이 이상의 모델이 좋은 결과를 내는 것은 쉽지 않을 것으로 생각됩니다. 우리가 세상에 있는 텍스트를 전부 다 알고 있다면 기존 두 개의 단어에 의존한다고 가정한다거나 하는 식으로 여러 가지 다양한 모델을 시험해 볼 수 있겠지만, 데이터가 매우 작은 관계로 빈도를 세어서 확률을 계산하는 것은 매우 위험합니다.
확률 모델
실제로, corpus에 등장하지 않은 단어라고 해서 세상에 없는 단어인 것은 아닙니다. 또 x라는 단어가 corpus에 두 번 나오고, y라는 단어가 한 번 나왔다고 해서 x가 y보다 두 배 많다고 이야기하는 것도 무척 위험한 일이지요. 따라서 단순히 빈도를 세는 것으로 끝나는 것이 아니라 그것이 실제로는 어떤 값에 가까울지 적절히 뭉개는 것이 매우 중요합니다.
앞에서 이야기했듯 이러한 모델이 확률에 대한 이야기이기는 합니다만 그냥 점수를 정해 놓고 최대화/최소화하는 것이나 다를 바 없기 때문에 확률론에서의 중요한 가정들(다 더하면 1이어야 한다던가)을 잘 지킬 필요는 없습니다. 다만 너무 어긋나면 문제가 되겠죠?
그래서, 저는 우선 단어의 길이에 대한 분포를 적극적으로 활용했습니다. 우리가 언어에 대한 사전 지식을 활용할 수는 없지만, corpus와 트레이닝 데이터에서 단어의 길이별 분포를 잰다면 그것은 빈도가 충분히 많으니 실제 세계에서의 분포와 매우 유사할 것입니다. 이를 통해 각 단어가 일단 한번 등장하기만 했다면 실제 등장할 확률은 텍스트에서 빈도를 잰 것보다 압도적인 비중으로 단어 길이에 대한 확률에 가깝도록 조정했습니다.
모르는 단어의 경우 역시, 기본적으로 단어의 길이별 등장 확률에다가 26자의 알파벳을 임의로 추출하는 경우의 수, 두 가지 요인을 감안하여 계산하였습니다. 모르는 단어의 길이별 확률을 조정하는 것은 매우 조심스럽게 취해야 하는데요, 이것을 너무 약하게 주면 "theconservationarea"와 같은 문자열에서 "conservation"이라는 단어를 모를 때, "the conserv at ion area"와 같이 아는 단어들로 쪼개버리고 맙니다. 이러한 구분은 이 문제의 평가 규칙대로라면 아주 큰 페널티를 받게 됩니다. 평가 항목 중에 QA는 쿼리가 맞고 틀리고이므로 손댈 수 없는 것이라 치고, CA는 문자열로 검토하다보니 점수에 큰 영향을 미치지 않아서 WR와 WP가 중요한 요인입니다. 그런데 잘게 자르게 되면 단어 개수 분모가 커져서 점수에 손해를 보게 됩니다.
게다가 도메인이 워낙 특이하고 데이터에는 정제되지 않은 내용이 많아서 이 확률 조정의 중요성이 더욱 큽니다. 예를 들어 "man v food", "bi hun", "los primos taberna y tapas" 같은 텍스트가 트레이닝 데이터에 있는데요, 저런 단어들이 존재한다고 해서 "v", "y" 같은 단어가 존재하니 좋은 확률을 주어 버리면 잘게 쪼개지는 참사가 일어납니다.
특별히 연속된 숫자로 이루어진 문자열의 경우, 길이 분포를 따로 계산해서 간단한 모델을 따로 적용하였습니다. 이 때문에 "1st"같이 잘 알려진 문자열은 그대로 넘어가지만, "738northbridge"같은 문자열은 대부분 "738 north bridge"와 같이 분리하게 됩니다.
지금까지 한 단어의 확률에 대해 주로 언급했습니다만 앞에서 언급했듯 우리가 두 단어까지의 확률을 계산해 두기로 했는데요, 이 경우는 존재하지 않는 경우가 훨씬 많아서 조심스럽게 접근해야 합니다. 일단 잘 존재하는 경우의 확률은 기본적으로 앞 단어가 정해져 있을 때의 조건부 확률, 수학적으로 말해 p(w_i | w_{i-1})일텐데요, 실제로는 w_{i-1}과 w_i라는 두 문자열이 인접한 덩어리가 두 단어 이하로 나올 확률을 곱해 보정합니다. 이러한 순서쌍이 존재하지 않아 p(w_i | w_{i-1})를 추측해야 할 때는 대충 p(w_i)로 두되 w_i라는 단어가 우리의 사전에 존재한다면 페널티를 적게 줍니다.
전처리와 후처리
트레이닝 쿼리는 잘 가공되어 그대로 적용할 수 있지만, corpus의 경우 그대로 긁어서 제공한 것이므로 쓸만한 데이터로 만들기 위해서는 전처리를 수행해야 합니다. 다음은 이 어려움을 보여주는 corpus의 일부입니다.
No one should really miss out on this ice-cream+espresso+honeycomb crunch.
They also have a FB account!http://www.facebook.com/home.php#!/
Filetto Di Mento ($32.90) - For a change, I ordered my steak medium instead of medium rare this time round and it came as per instructions.
Mmmmmmmmmmmmmm...
Koung's Wan Tan Mee
이러한 다양한 토큰들은, 대강 공백을 기준으로 구분하되 토큰의 가운데 부분에 알파벳이나 숫자를 끼고 다른 종류의 문자가 있는 경우 그냥 버리는 정책을 취했습니다. 따라서 위의 "ice-cream"같은 토큰은 그냥 버렸습니다. 이 경우 영문 소유격들, 이를테면 "customer's"이나, "isn't", "they're" 같은 줄임들이 전부 버려지게 되는 문제가 있는데, 이런 것들이 검색 쿼리로 들어오는 경우는 사실상 없을 것이므로 걱정 없이 포기했습니다. 그 외에도 대소문자는 같은 것으로 처리하는 등 몇가지 처리를 했구요.
한편, 이를테면 corpus에 "delicious cheeseburger"라는 문자열이 등장했고, "delicious cheese"라는 문자열은 등장한 적이 없다고 가정해 봅시다. 이 경우 실제로는 위 문제에서 언급하였듯 "delicious cheese burger"가 되어야 함에도, "delicious cheese"와 "cheese burger"의 확률을 계산하게 되면 페널티를 상당히 먹기 때문에 "delicious cheeseburger"처럼 붙여서 나타나게 됩니다. 이 문제를 해결하기 위해 확률을 최대화하는 조합을 구한 뒤에, 각 단어별로 해당 단어를 두 단어로 쪼개는 것이 월등히 올바른 것으로 드러난다면 쪼개도록 했습니다.
결론 및 후기
위와 같은 방법으로, 처음에는 받은 트레이닝 쿼리의 절반을 쪼개서, 5000개의 트레이닝 쿼리로 5000개의 테스트 쿼리를 맞춰야 한다고 가정하고 작업을 했습니다. 첫날 바로 올바른 방향으로 작업을 시작한 덕분에, 주말 동안에는 점수를 약간 올리기 위해 후처리나 각종 상수 보정 등만 수행했습니다. 다른 참가자들에게 점수를 알리지 않고자 제출할 때는 4000개의 쿼리를 일부러 분리하지 않고 제출했습니다. 마지막 제출 당시 사용한 알고리즘으로 로컬에서 약 5000/5000개로 나누어 테스팅했을 때의 점수는 96.12%(QA 93.4%) 입니다. 트레이닝 쿼리 약 10000개를 전부 사용해 돌린 테스트 쿼리에 대한 최종 점수는 96.53%(QA 94.1%)이니, 트레이닝 쿼리의 활용이 어느 정도 영향을 미쳤겠지요.
출제자님께서도 말씀해 주셨지만, 저 역시 생각보다 품질이 좋은 결과가 나와 처음부터 놀랐습니다. 물론 여러가지 점수를 개선하기 위한 노력들을 위에서 설명드렸던 바 있지만, 그것은 사실 소수점 아래 몇 점이라도 더 받기 위한 노력들에 가깝다고 생각합니다. 위에서도 말씀드렸듯 WP 점수를 손해보지 않기 위해서 단어들을 소극적으로 나누었는데, 제 WP가 96.3이고 2위, 3위 분들의 WP가 96.1, 95.9이고 점수 차이가 매우 적은 것을 보면 이런 치사한(?) 전략으로 인해 운 좋게 우승할 수 있었던 것으로 생각합니다. 그보다는 저나 다른 분들이 사용한, 기본적인 확률 모델에 기반한 분리 전략이 매우 적은 데이터에서도 얼마나 좋은 결과를 낼 수 있는지를 느꼈습니다.
마지막으로 다시금 출제와 준비 및 진행에 애쓰신 SK planet 홍금원 매니저님, 김남구 부장님 및 여러 분들께 진심으로 감사드립니다. 특히나 올해의 경우 현실적인 문제 출제와 좋은 접근성 유지와 같은 동시에 만족하기 어려운 여러 조건을 놓고 고민하신 것이 느껴졌습니다. 앞으로도 이런 대회가 지속적으로 진행되고 해마다 더 많은 분들이 참여하는 모습을 볼 수 있기를 기대합니다. 감사합니다.
방학동안에 갔던 모 교육에서, 하루는 TSP 문제가 나왔습니다.
자신이 알고있는 휴리스틱 및 각종 최적화를 최대한 써서, 소숫점 단위로 올라가는 점수를 보면서 조마조마하던 선배들이 생각나네요.
'전체적인 큰 틀 속에서 조금씩 고득점을 위한 전략을 세우는' 이런 문제 유형 진짜 좋은것같아요. 알아보기 쉽게 단계를 나눠서 자세히 설명해주셔서 감사합니다.
Being
안녕하세요. SK planet Code Sprint 2014 Round 1에서 1위에 입상한 류원하입니다. 2012년 1회 대회때 Round 1에서 우승한 뒤로 두 번째로 우승하게 되어 감격스럽습니다. 무엇보다 매년 좋은 상품과 더불어 국내에서 흔치 않은 대회를 열어 주시는 점에 대해 SK planet 측에 진심으로 감사의 말씀을 드립니다.
저는 이 글을 통해 제가 어떻게 문제를 풀었는지에 대해 많은 분들이 이해하실 수 있도록 가능하면 문턱을 낮춰 설명하려 합니다. 제가 알기로는 저를 포함해 1위부터 4위까지의 접근은 큰 틀에서 비슷한데요, 전체적인 기본 접근 방법을 스케치하고 고득점을 하기 위해 제가 특별히 신경쓴 부분이 무엇이 있는지 하나씩 살펴보도록 하겠습니다.
문제: Text Segmentation
우선 문제에 대해 간략히 짚고 넘어가겠습니다. 이번 문제를 제 표현으로 다시 풀어 쓰자면:
위와 같은 문자열 구분 문제는 일반적으로는 Text Segmentation이라 불리는 이름이 있습니다. 그러니 여러 가지 방법에 대해 연구된 바가 많겠죠? 하지만 이 문제의 경우 다음 이유로 기존의 방법을 그대로 적용하기 어렵습니다:
위와 같은 이유로 기존의 방법을 어느 정도 이해하고 적용하는데다가 문제의 취지에 맞는 여러 개선 방법을 택해야 좋은 결과를 얻을 수 있었으리라 생각합니다.
쉽게 변형한 문제 먼저 풀기
만약 세상에 있는 단어들을 전부 다 안다고 가정하면 어떻게 해결할 수 있을까요? "realityours"라는 문자열을 예시로, 이 문자열이 구분가능한지 불가능한지를 먼저 어떻게 풀 수 있는지 보도록 하겠습니다. 이 문자열을 구분했을 때, 첫번째 단어는 분명 다음 중 하나일 것입니다.
이들 중에서 올바른 단어인 것도 있고, 올바르지 않은 단어인 것도 있고, 긴가민가 하는 단어도 있을 것입니다. 일단은 당장의 문제에 집중하기 위해 온 세상에 있는 단어가 {real, reality, it, ours} 뿐이라고 생각해 봅시다. 그렇다면 저 11가지 후보들 중에서 실제로 가능한 것은:
이 둘 뿐이겠지요? 그런데, 실제로 "real"로 시작하는 분리 방법이 있으려면 나머지 부분인 "ityours" 를 구분할 방법이 있어야 합니다. 다시 말해 우리는 "realityours"라는 문자열을 구분하는 문제를 풀기 위해서 "ityours"라는 부분 문제를 풀어야 하는 것이죠. 그러므로 만약 우리가 어떤 문자열을 쪼개는 올바른 방법이 있는지 없는지를 알아내는
segmentable?(x)라는 함수와 올바른 단어인지 판단하는word?(x)가 존재한다고 가정하면,segmentable?("realityours")는 이런 식으로 계산할 수 있을 것입니다:segmentable?("realityours") = word?("r") && segmentable?("ealityours") || word?("re") && segmentable?("alityours") || word?("rea") && segmentable?("lityours") || word?("real") && segmentable?("ityours") ... || word?("reality") && segmentable?("ours") ... || word?("realityours") && segmentable?("")이들 중 word?()가 참인 것은 둘 뿐이었으므로 결과적으로
segmentable?("ityours")와segmentable?("ours")를 알 수 있으면 됩니다. 같은 방식으로 생각하면 우리의 올바른 선택은 "reality ours"뿐임을 알 수 있죠. 빈 문자열이 구분가능한지는 참으로 둔다는 사실을 기억하시기 바랍니다 (segmentable?("")은 참)생각해 보면,
segmentable?함수의 인자는 항상 "realityours"라는 최초 문자열의 접미 문자열(suffix)일 것입니다. 앞에서부터 단어를 하나씩 빼가고 있으니까요. 이를 조금 더 직관적으로 계산하기 위해 우리는 D라는 수열을 하나 잡아서, D_i가segmentable?("realityours"[i..end])라고 할 수 있습니다. 이렇게 하면,D_0 = word?("r") && D_1 || word?("re") && D_2 || word?("rea") && D_3 || word?("real") && D_4 ... || word?("reality") && D_7 ... || word?("realityours") && D_11와 같이 표현할 수 있겠지요. 보통 프로그래밍 언어에서는 배열을 활용해 이런 수열을 저장할 수 있으므로, 배열
D가 있다면 아래와 같은 형태가 되겠죠?D[0]D[1]D[2]D[3]D[4]D[7]D[11]우리가 위에서 보았듯
D[i]를 계산하기 위해서D[i+1]부터D[11]까지 알아야 했기 때문에, 뒤에서부터 거꾸로 계산하면 모든 값을 구할 수 있습니다. 이와 같이 문제를 작은 부분 문제로 나누고, 순서대로 잘 계산해서 목표로 하는 원래 문제를 푸는 패러다임을 동적 계획법이라 합니다.실은 우리가 "realityours"가 구분가능한지 불가능한지만 알아낸 상태이고, 어떻게 구분하는지에 대한 방법은 아직 알아내지 않았습니다. 조금만 생각해 보면 크게 어려운 문제는 아니지요.
D[0]이 참인 까닭은word?("reality")와D[7]이 모두 참이었기 때문입니다.D[7]이 참인 까닭은word?("ours")와D[11]이 모두 참이었기 때문이고요.D[11], 빈 문자열은 그냥 그 자체로 참이라고 두었습니다. 따라서 이와 같이 무엇 때문에 참이 되었는지를 기록해 두거나 다시 계산해 알아낸다면 결과가 "reality ours"임을 역추적해나갈 수 있습니다.현실적인 문제 풀기
아쉽지만 실제로는 위의 이상적인 경우와는 조금 차이가 있습니다.
1번의 경우를 좀 더 생각해 봅시다. 우리가 온 세상에 {real, reality, it, ours}의 네 단어밖에 없다고 가정했었는데, 여기에 "yours"라는 단어가 신조어로 등장하였다 하면 골치가 아파집니다:
이것들 중 어떤 것이 맞을까요? 둘 다 맞기는 하지만, 어느 것이 더 "적절"할까요?
이러한 문제를 해결하기 위한 방법 중 하나는 각각의 확률을 생각하는 것입니다. 온 세상에 "reality ours"라는 텍스트가 등장할 확률과, "real it yours"라는 텍스트가 등장할 확률을 각각 구하고, 그들 중 큰 것을 택하기로 하는 것입니다. 물론 이 확률을 구하는 것은 무지하게 어렵습니다. 단순히 데이터에서 빈도를 센 것이 확률이냐고 물을 수도 있을 테고요.
사실 정확한 확률이란 있을 수가 없습니다만, 대충 그럴듯하게 구하기만 해도 데이터가 많다면 충분히 좋은 결과를 얻을 수 있습니다. 예를 들어 우리가 어떤 텍스트 x가 등장할 확률을 p(x)라고 하고, 각 단어는 전부 독립적이어서 실제로 각 단어가 등장할 확률을 전부 곱해서 얻을 수 있다고 근사한다고 생각해 봅시다. 다시 말해, 우리가 {real, reality, it, ours, yours} 각각의 단어에 대해 등장할 확률을 알고 있다면, 이걸 곱해서 두 구분 방법 중 어느 것이 더 그럴듯한지를 알아낼 수 있겠죠. (사실 확률들에 로그를 씌우면 곱셈이 덧셈으로 바뀌는데, 단어들에 그럴듯한 "점수"가 있고 이 점수를 더해서 가장 큰 점수를 얻는 구분 방법이 무엇이냐? 라는 문제로도 생각할 수 있습니다. 각색하자면 수평선 위에 집들이 몇 개 있는데, 이 수평선을 몇 조각으로 나누어 각 조각마다 하나씩 그 조각 안의 집들을 관리하는 소방서를 짓는다고 생각하는 문제와 같습니다.)
아무튼 이런 생각에는 근거가 아주 없는 것은 아니고, 실제로 텍스트가 생성되는 것이 마치 사전에 단어별 출현 빈도를 별표로 표시해 두고(별 세개는 아주 자주 나오니 중학교 수준 단어 하는 식으로요) 그 출현 빈도에 따라 단어를 랜덤하게 추출한다고 가정하는 모델을 바탕으로 하고 있습니다. 이러한 모델을 현실적으로 반영할 수 있다면 품질이 당연히 올라가겠죠?
당연하게도, 위와 같은 모델은 현실과는 거리가 있어서 우리의 최종 문제를 해결하는 데 약간의 장애가 있습니다. 도입부에서 문제를 설명할 때에 말씀드렸듯, "cheeseburger"는 "cheese burger"여야 하고 "beancurd"는 "bean curd"가 아니어야 하니, 각 단어를 독립적으로 가정해서는 안 됩니다. 앞선 방법을 조금만 비틀면 생각을 달리할 수 있습니다. "real it yours"라는 텍스트가 등장할 확률은 "real"이 등장할 확률, "real it"이 등장할 확률과 "it yours"가 등장할 확률의 곱이라고 보는 것입니다. 왜 이런 가정을 할 수 있을까요?
이론적으로 말해서, 이것은 우리의 확률 프로세스를 마르코프 프로세스라고 보는 것입니다. 쉽게 말하자면, 다음 단어는 그 전 단어가 무엇이냐에 따라 다르게 결정된다고 생각하는 것인데요, "beer"라는 단어나 "burger"라는 단어가 나올 확률이 어떻든 간에, "cheese" 다음에는 "beer"보다는 "burger"가 나올 확률이 훨씬 높다고 보는 것입니다. 이렇게 보더라도 현실과는 거리가 어느 정도 있지만, 충분히 좋은 근사가 됩니다.
이 이상의 모델이 좋은 결과를 내는 것은 쉽지 않을 것으로 생각됩니다. 우리가 세상에 있는 텍스트를 전부 다 알고 있다면 기존 두 개의 단어에 의존한다고 가정한다거나 하는 식으로 여러 가지 다양한 모델을 시험해 볼 수 있겠지만, 데이터가 매우 작은 관계로 빈도를 세어서 확률을 계산하는 것은 매우 위험합니다.
확률 모델
실제로, corpus에 등장하지 않은 단어라고 해서 세상에 없는 단어인 것은 아닙니다. 또 x라는 단어가 corpus에 두 번 나오고, y라는 단어가 한 번 나왔다고 해서 x가 y보다 두 배 많다고 이야기하는 것도 무척 위험한 일이지요. 따라서 단순히 빈도를 세는 것으로 끝나는 것이 아니라 그것이 실제로는 어떤 값에 가까울지 적절히 뭉개는 것이 매우 중요합니다.
앞에서 이야기했듯 이러한 모델이 확률에 대한 이야기이기는 합니다만 그냥 점수를 정해 놓고 최대화/최소화하는 것이나 다를 바 없기 때문에 확률론에서의 중요한 가정들(다 더하면 1이어야 한다던가)을 잘 지킬 필요는 없습니다. 다만 너무 어긋나면 문제가 되겠죠?
그래서, 저는 우선 단어의 길이에 대한 분포를 적극적으로 활용했습니다. 우리가 언어에 대한 사전 지식을 활용할 수는 없지만, corpus와 트레이닝 데이터에서 단어의 길이별 분포를 잰다면 그것은 빈도가 충분히 많으니 실제 세계에서의 분포와 매우 유사할 것입니다. 이를 통해 각 단어가 일단 한번 등장하기만 했다면 실제 등장할 확률은 텍스트에서 빈도를 잰 것보다 압도적인 비중으로 단어 길이에 대한 확률에 가깝도록 조정했습니다.
모르는 단어의 경우 역시, 기본적으로 단어의 길이별 등장 확률에다가 26자의 알파벳을 임의로 추출하는 경우의 수, 두 가지 요인을 감안하여 계산하였습니다. 모르는 단어의 길이별 확률을 조정하는 것은 매우 조심스럽게 취해야 하는데요, 이것을 너무 약하게 주면 "theconservationarea"와 같은 문자열에서 "conservation"이라는 단어를 모를 때, "the conserv at ion area"와 같이 아는 단어들로 쪼개버리고 맙니다. 이러한 구분은 이 문제의 평가 규칙대로라면 아주 큰 페널티를 받게 됩니다. 평가 항목 중에 QA는 쿼리가 맞고 틀리고이므로 손댈 수 없는 것이라 치고, CA는 문자열로 검토하다보니 점수에 큰 영향을 미치지 않아서 WR와 WP가 중요한 요인입니다. 그런데 잘게 자르게 되면 단어 개수 분모가 커져서 점수에 손해를 보게 됩니다.
게다가 도메인이 워낙 특이하고 데이터에는 정제되지 않은 내용이 많아서 이 확률 조정의 중요성이 더욱 큽니다. 예를 들어 "man v food", "bi hun", "los primos taberna y tapas" 같은 텍스트가 트레이닝 데이터에 있는데요, 저런 단어들이 존재한다고 해서 "v", "y" 같은 단어가 존재하니 좋은 확률을 주어 버리면 잘게 쪼개지는 참사가 일어납니다.
특별히 연속된 숫자로 이루어진 문자열의 경우, 길이 분포를 따로 계산해서 간단한 모델을 따로 적용하였습니다. 이 때문에 "1st"같이 잘 알려진 문자열은 그대로 넘어가지만, "738northbridge"같은 문자열은 대부분 "738 north bridge"와 같이 분리하게 됩니다.
지금까지 한 단어의 확률에 대해 주로 언급했습니다만 앞에서 언급했듯 우리가 두 단어까지의 확률을 계산해 두기로 했는데요, 이 경우는 존재하지 않는 경우가 훨씬 많아서 조심스럽게 접근해야 합니다. 일단 잘 존재하는 경우의 확률은 기본적으로 앞 단어가 정해져 있을 때의 조건부 확률, 수학적으로 말해 p(w_i | w_{i-1})일텐데요, 실제로는 w_{i-1}과 w_i라는 두 문자열이 인접한 덩어리가 두 단어 이하로 나올 확률을 곱해 보정합니다. 이러한 순서쌍이 존재하지 않아 p(w_i | w_{i-1})를 추측해야 할 때는 대충 p(w_i)로 두되 w_i라는 단어가 우리의 사전에 존재한다면 페널티를 적게 줍니다.
전처리와 후처리
트레이닝 쿼리는 잘 가공되어 그대로 적용할 수 있지만, corpus의 경우 그대로 긁어서 제공한 것이므로 쓸만한 데이터로 만들기 위해서는 전처리를 수행해야 합니다. 다음은 이 어려움을 보여주는 corpus의 일부입니다.
이러한 다양한 토큰들은, 대강 공백을 기준으로 구분하되 토큰의 가운데 부분에 알파벳이나 숫자를 끼고 다른 종류의 문자가 있는 경우 그냥 버리는 정책을 취했습니다. 따라서 위의 "ice-cream"같은 토큰은 그냥 버렸습니다. 이 경우 영문 소유격들, 이를테면 "customer's"이나, "isn't", "they're" 같은 줄임들이 전부 버려지게 되는 문제가 있는데, 이런 것들이 검색 쿼리로 들어오는 경우는 사실상 없을 것이므로 걱정 없이 포기했습니다. 그 외에도 대소문자는 같은 것으로 처리하는 등 몇가지 처리를 했구요.
한편, 이를테면 corpus에 "delicious cheeseburger"라는 문자열이 등장했고, "delicious cheese"라는 문자열은 등장한 적이 없다고 가정해 봅시다. 이 경우 실제로는 위 문제에서 언급하였듯 "delicious cheese burger"가 되어야 함에도, "delicious cheese"와 "cheese burger"의 확률을 계산하게 되면 페널티를 상당히 먹기 때문에 "delicious cheeseburger"처럼 붙여서 나타나게 됩니다. 이 문제를 해결하기 위해 확률을 최대화하는 조합을 구한 뒤에, 각 단어별로 해당 단어를 두 단어로 쪼개는 것이 월등히 올바른 것으로 드러난다면 쪼개도록 했습니다.
결론 및 후기
위와 같은 방법으로, 처음에는 받은 트레이닝 쿼리의 절반을 쪼개서, 5000개의 트레이닝 쿼리로 5000개의 테스트 쿼리를 맞춰야 한다고 가정하고 작업을 했습니다. 첫날 바로 올바른 방향으로 작업을 시작한 덕분에, 주말 동안에는 점수를 약간 올리기 위해 후처리나 각종 상수 보정 등만 수행했습니다. 다른 참가자들에게 점수를 알리지 않고자 제출할 때는 4000개의 쿼리를 일부러 분리하지 않고 제출했습니다. 마지막 제출 당시 사용한 알고리즘으로 로컬에서 약 5000/5000개로 나누어 테스팅했을 때의 점수는 96.12%(QA 93.4%) 입니다. 트레이닝 쿼리 약 10000개를 전부 사용해 돌린 테스트 쿼리에 대한 최종 점수는 96.53%(QA 94.1%)이니, 트레이닝 쿼리의 활용이 어느 정도 영향을 미쳤겠지요.
출제자님께서도 말씀해 주셨지만, 저 역시 생각보다 품질이 좋은 결과가 나와 처음부터 놀랐습니다. 물론 여러가지 점수를 개선하기 위한 노력들을 위에서 설명드렸던 바 있지만, 그것은 사실 소수점 아래 몇 점이라도 더 받기 위한 노력들에 가깝다고 생각합니다. 위에서도 말씀드렸듯 WP 점수를 손해보지 않기 위해서 단어들을 소극적으로 나누었는데, 제 WP가 96.3이고 2위, 3위 분들의 WP가 96.1, 95.9이고 점수 차이가 매우 적은 것을 보면 이런 치사한(?) 전략으로 인해 운 좋게 우승할 수 있었던 것으로 생각합니다. 그보다는 저나 다른 분들이 사용한, 기본적인 확률 모델에 기반한 분리 전략이 매우 적은 데이터에서도 얼마나 좋은 결과를 낼 수 있는지를 느꼈습니다.
마지막으로 다시금 출제와 준비 및 진행에 애쓰신 SK planet 홍금원 매니저님, 김남구 부장님 및 여러 분들께 진심으로 감사드립니다. 특히나 올해의 경우 현실적인 문제 출제와 좋은 접근성 유지와 같은 동시에 만족하기 어려운 여러 조건을 놓고 고민하신 것이 느껴졌습니다. 앞으로도 이런 대회가 지속적으로 진행되고 해마다 더 많은 분들이 참여하는 모습을 볼 수 있기를 기대합니다. 감사합니다.
10년 전