난이도 자동 추정 알고리즘에 대하여

뜬금없이 이게 무슨 글이냐 하기 전에, 제가 아마존 aws free-tier을 8달 전 쯤에 신청해서 잘 쓰고 있다는 이야기부터 해야겠군요.

현재 여기에 학교 과 공지사항 긁어서 이멜로 날려주는 놈이랑(..) 투덱미 랭크 테이블을 올려두고 쓰고 있는데, 후자의 경우는 사실 제가 꿈꿔오던 모델이 하나 있어서 그걸 구현해보고자 깔아둔 밑밥이었습니다.

그것은 바로 walkure와 stairway인데, 길게 설명하기보다는 직접 보여주는편이 좋겠다는 생각을 해서 이렇게 들고 왔습니다.

각각 추천과 난이도추정 서비스입니다. 빅데이터를 기반으로 자료를 추출하는 프로젝트가 되겠습니다.

이를 산출하는 방법은 어렵게 설명하면 MCMC를 이용한 모델의 MLE이고, 쉽게 설명하면 그냥 무작위로 찍어서 비슷한 값 나올때까지 돌렸다고 보시면 됩니다. 알고보니 정말 별 거 없던 (...)

좀 더 구체적으로, 노래와 플레이어의 데이터를 예를 들어서 설명을 해 보겠습니다.

Graph from https://www.desmos.com/calculator

노래의 예를 먼저 들면, x축을 유저의 실력(레벨), y축을 가중치(클리어:1, 페일:0)라고 하였을 때, 평균 클리어 난이도가 2로 추정되는 어떤 노래의 클리어 분포라고 볼 수 있습니다. 2레벨이 안되는 유저가 이 곡을 선택하면 페일할 가능성이 무척 높은 것이고, 그 반대의 경우 대부분 클리어한다고 볼 수 있는 것입니다.

확실하게 알아보기 위해서 실제 데이터가 있다고 가정하고 점을 찍으면 이런 모습이 될 것입니다.

빨간색은 좀 더 분산이 큰 경우의 모델이 될 수 있음을 알 수 있습니다. 즉, 곡의 경우 모델을 결정하는 요소가 두 가지가 되며(분산과 평균), 이 두 값은 무작위로 추정^[각주:1]되고 그 중 가장 나은 값을 선택하여 지속적으로 더 나은 값으로 갱신해나가게 됩니다. 더 나은 값인지 확인하는 방법은 error sum(보통 제곱합 방식을 이용)이 어느 것이 더 작느냐가 되겠네요.

플레이어의 경우는 노래와 반대의 모습이 될 것입니다. x축을 곡의 레벨이라고 하고 y축을 클리어 상태라고 보면, 자신의 레벨보다 작은 곡은 클리어를 하게 되지만 그 이상의 곡들은 다소 버거운 모습을 보이겠죠.

이러한 점들을 고려하면, 플레이어를 갱신하여 나온 더 나은 값으로 노래를 갱신하고, 노래를 갱신하여 나온 더 나은 값으로 다시 플레이어를 갱신하고 ... 이를 재귀적으로 반복하면 우리가 원하는 해에 근사할 수 있음을 알 수 있습니다. 하지만 임의로 아무 값이나 배정한 후 무턱대고 알고리즘을 구동하기에는 몇 가지 문제점이 있습니다. 아무래도 좋은 값을 줬을 때보다 시간이 더 오래 걸리기도 하거니와, 그래프가 잘못 피팅될 수도 있습니다. 가장 좋은 예는 역시 단계별 엔탈피 그래프...

chemical reaction step으로 검색해서 긁어온 이미지!

x축을 난이도라고 가정하고 y축을 error sum이라고 가정하고 보면, x가 B로 수렴해버리면 D라는 해가 있음에도 불구하고 양옆의 장벽에 막혀서 이동하지 못하게 됩니다. 그렇게 될 경우, 잘못된 난이도가 추정될 수 있습니다. 무작위로 배정된 값의 경우 이러한 위험성이 더 커지게 됩니다.^[각주:2]

저 같은 경우에는 다음과 같은 방식으로 기본값을 배정했습니다.

1. 각 곡의 난이도 = (곡의 기본 난이도) + (하드클리어 비중[많을수록 쉬운 곡이겠죠?])
2. 각 곡의 난이도를 기준으로 MCMC 알고리즘을 돌려서 플레이어의 기본적인 난이도 추측

이렇게 대충 iteration 20번 돌리니 괜찮게 피팅이 되었습니다~ 아무래도 데이터가 많고 수행시간이 길다 보니 테스트 한번한번 해보는 게 참 버거웠던 삽질... ㅠㅠ.

사실 처음에는 많은 곳에서 마르코프 모델을 MCMC 알고리즘의 예제로서 이용하고 있길래, 이를 가지고 구현해보려고 하였습니다. 

from wikipedia

일단 마르코프 모델의 기본적인 모습은 이렇고, 오른쪽이 이전 상태, 왼쪽이 이후 상태가 되며 궁극적으로는 양 변이 같아질 때 수렴한다고 볼 수 있습니다. 여기서는 각 확률을 P(Clear) x P(Fail)로 정했습니다. 사실 수학적으로 별 의미는 없지만... 얘 아니면 수렴할 값이 없더라고요...

그런데 이 방식은 매번 엄청난 양의 데이터베이스(제가 이번에 사용한 것만 해도 40만개^[각주:3])를 쿼리해야 합니다. 실제로 해 봤는데 5초당 한 곡 처리하더랍니다 ... 

정확한 값을 구하는 데 무리가 있으니, 특정 모델에 근사한 마르코프 모델을 이용하는 것이 역시 빅데이터 처리에서는 제일 현명한 선택인 듯 합니다. (이런 느낌으로 구하는 게 맞는지 모르겠네요. 더 나은 답이 생각난다면 다시 이 글 고치러 올 지도.)

휴학하는 동안에 하고 싶었던 일 중 하나를 어떻게 끝내긴 했군요. 사실 2주일밖에 안 걸렸다만 ... (2주일 내내 이것만 한 듯 하다...) 프로젝트는 깃헙에 올려놓았습니다.

프리티어 4개월 남았는데 여기에 뭘 또 올릴까 고민을... 사실 븜스 인코딩 서버같은거 돌리고 싶었는데 생각보다 CPU unit 할당량이 짜더랍니다 눈물...

생각해보면 10분마다 사람이 한명씩은 들어오는 것 같아서 AWS든 어디든 아무래도 서버는 계속 돌려야 할 듯... 돌리고 있는 사이트는 요기입니다.

덤으로 삽질하다가 django 버그인지 뭔지 하나 뜯어고쳐서 issue도 넣었다고 하네요 (...)

1. 자세한 내용은 Markov chain Monte Carlo methods과 Metropolis within Gibbs algorithm 참조 [본문으로]
2. 사실 learning rate를 높이면 해결되는 문제이긴 하지만, 그만큼의 computation cost가 추가적으로 요구되고, 어찌되었든 초기값을 잘 배정해서 나쁠 건 없다! [본문으로]
3. 처음엔 소규모로 시작해서 sqlite으로 썼는데(!), 30만개의 데이터가 들어갈 줄 알았으면 미리 MariaDB로 갈아탈 걸... [본문으로]