NETFLIX PRIZE 진행과정에 대한 마지막 포스트인 (3)편 입니다.
드디어 마지막 편이네요. 지난 (1)편과 (2)편은 사실 본 (3)편의 내용을 포스팅 하고 싶어서 작성했었던 예고편과 같은 포스팅이었다고 할 수 있습니다. 🙂 (2)편에서 이미 말씀 드린 것처럼 백만달러의 상금이 걸린 Final Grand Prize 우승팀은 첫 해 AT&T Research Labs 소속 연구원이 주축으로 시작된 “BellKor’s Pragmatic Chaos” 팀 입니다. 하지만 저는 우승팀의 이야기 보다 다른 팀들이 어떻게 경쟁했는지가 더 흥미로웠습니다. 백만달러가 걸린 이제부터가 본 게임이라고 할 수 있겠죠.
2009 : 대연합의 시대
Netflix Progress Prize 2008 결과 우승 팀의 최종 성능은 Cinematch 대비 9.44%로 백만달러를 받을 수 있는 10% 향상까지 0.56% 만 더 향상시키면 되었습니다. 2007, 2008 중간 진행과정에서의 우승 상금은 5만달러에 불과했기 때문에 사실 Grand Prize가 진정한 의미의 우승이라고 할 수 있습니다. 이미 우수한 알고리즘들은 모두 공개된 상황이었기 때문에 여러 알고리즘을 효율적으로 배합하고 변수를 컨트롤하면서 다양한 결과를 실험해보면 이제는 Grand Prize를 노려볼 수 있는 시기가 되었음을 여러 참가자들은 본능적으로 알게 되었습니다. 이미 2007년부터 “BellKor” 팀은 100개 이상의 알고리즘으로 얻어진 결과를 배합하여 최종 예측을 한다고 발표했었고, 여러 결과를 배합하는 데 있어 단순히 좋은 성능을 보이는 결과들의 합보다 새로운 발상으로 접근한 결과들을 배합할 때 성능이 올라간다는 것이 이론적으로 증명되었기 때문에 기존의 팀들은 본인팀과는 다른 새로운 시도를 한 팀과의 연합이 필수적인 상황이 되었습니다.
정보이론을 통해 기계학습(Machine Learning) 분야에서 단일 알고리즘이 아닌 여러 알고리즘을 잘 섞는 알고리즘의 중요성이 대두되어 ensemble method로 발전하였고, 최근 단일 알고리즘이 충분히 고도화 되면서 그 중요성이 계속 높아지고 있습니다.
GPT : Open Collaboration
2007 대회에서 마지막에 연합까지 했었지만 결국에는 우승을 코앞에서 놓쳤던 “Gravity” 와 “Dinosaurs Planet”팀을 기억하시죠? 이 연합팀은 새롭게 팀을 정비하여 2009년 2월, Gravity R&D의 Gabor Takacs를 리더로 “Grand Prize Team (GPT)”으로서 새롭게 출범합니다. 새롭게 출범하면서 새로운 전략은 Open Collaboration 이었습니다. 이미 연합을 통해 알고리즘을 잘 배합하면 (“blending”이라고 표현합니다) 더 좋은 성능이 나올 수 있음을 체득하였기 때문에 팀이 연합하면 CineMatch 대비 10% 성능 향상을 하여 Grand Prize 수상이 가능할 수 있다는 생각이었습니다.
Grand Prize Team Offer : GPT 팀은 이미 CineMatch 기준 9%의 성능을 향상시켰고 단 1%만 더 향상시키면 되는 상황이었습니다. 그들은 만약 우승상금 백만달러를 받게되면 상금의 1/3인 $333,333 USD만을 GPT에서 차지하고 나머지 $666,666 USD 는 기여자들에게 기존 약 9%에서 성능을 향상 시킨 비율 만큼 상금을 배분하겠다는 조건을 제안하였습니다.
또한 Gravity team 소속 Bottyan Nemeth은 참가자들이 쉽게 본인의 모델을 GPT에 추가로 배합시키면 얼마나 성능이 향상되는지 확인 할 수 있도록 별도의 웹서버를 만들어 빠르게 수치를 확인할 수 있도록 제공했습니다.
어차피 Winner-take -all 인 대회규정에 따라 우승이 어려울 것이라고 생각되는 팀들은 GPT의 제안에 관심을 가지고 본인의 데이터를 GPT 서버에 제출하여 GPT보다 얼마나 성능 향상에 기여하는지 바로 확인할 수 있었기 때문에 제공하는 팀들이 많았지만 실제 GPT 기준보다 더 높은 데이터는 많지 않았습니다.
그럼에도 불구 몇 명의 지원자는 눈에 띄는 성능 향상을 보이며 GPT 팀에 합류하기 시작했는데요, Leaderboard Top 10에서 오래 머물던 샌디애고의 엔지니어 Ces Bertino는 GPT 기준보다 0.21% 향상시키는 결과를 제공하며 제일 먼저 합류하게 됩니다. 그리고 점차 미국 외에 여러 다른 나라에서도 합류를 시작합니다. 그리고 결국 RMSE 0.8597로 당시 RMSE 0.8596으로 공동 1위를 하고 있던 “BellKor in Big Chaos” 팀과 “Pragmatic Theory” 팀에 이어 3위까지 올라가게 됩니다. 하지만 Grand Prize를 달성하기 위한 RMSE 스코어 0.8563까지 내려가려면 아직도 0.36% 수준의 향상이 필요했습니다.
Grand Prize Open
BellKor’s Pragmatic Chaos
2009년 6월까지 1위를 달리고 있던 팀도 백만달러가 걸린 Grand Prize 기준인 CineMatch 기준 10% 향상에는 미치지 못하고 있었는데요, 1위를 달리고 있던“BellKor in Big Chaos” 팀과 “Pragmatic Theory” 팀이 결국 연합하면서 “BellKor’s Pragmatic Chaos” 팀으로서 6월 28일 CineMatch 대비 10.05% 성능을 향상시키는데 성공합니다. 드디어 최종 우승 상금 백만달러가 걸린 Grand Prize가 열린 것이죠. “BellKor’s Pragmatic Chaos” 팀이 10%를 넘는 성능이 제출한 순간 부터 30일의 시간이 주어지고 30일이 지난 2009년 7월 26일 18:42:37 UTC 까지 최고 성능을 제출한 팀이 우승하게 되는 것 입니다. “Pragmatic Theory” 팀은 캐나다 통신회사에서 근무하는 2명의 직원으로 구성되어 있었고 그래서 “BellKor’s Pragmatic Chaos”팀은 7명으로 늘어나게 됩니다.
Vandelay Industries
팀들간의 Collaboration 전략으로 팀들을 흡수하며 키우는 것과 유사한 전략을 가진 팀은 Grand Prize Team (GPT)팀만이 아니었습니다. 2009년 2월, GPT팀과 거의 같은 시기에 소프트웨어 개발자 Greg McAlpin은 “Greg’s Probe File Exchange” 웹사이트를 런칭하고 Netflix Prize Forum커뮤니티에서 열성적으로 활동하는 참가자를 대상으로 초대장을 발송했습니다. “Greg’s Probe File Exchange” 웹사이트는 Invitation Only로 초대된 참가자만 이용할 수 있게 되어 있었고, Netflix 데이터에 정답이 공개된 Probe Set 예측결과를 업로드하면 기존에 Greg이 보유한 결과와 배합(blending)하여 예측성능이 얼마나 향상되는지 확인할 수 있게 만들었습니다. 재미있던 사실은 당시 호스팅 서버 업체 중 dreamhost.com이 그해 95% 할인 프로모션을 보고 할인 된 가격에 서버운영이 가능했던 것이 사이트를 만든 계기가 되었다는 것입니다.
“Greg’s Probe File Exchange”웹사이트에 초대된 Bo Yang이 먼저 합류하기 시작하며 8.8%수준의 성능 향상을 보이기 시작합니다. 아직 10%까지는 갈길이 멀지만 2009년 본격적으로 시작된 팀으로서 빠르게 Top tier에 따라가기 시작한 것이죠. 이후 팀원이 늘며 5명까지 늘어나게 됩니다. 이때까지만 해도 여러 팀원들의 결과 예측을 배합하는 데 있어 선형 회귀(linear regression)방법을 사용하였다면, 다섯 번째 합류한 Chris Hefele는 비선형 회귀(Nonlinear regression)으로 배합하는 방법을 “Greg’s Probe File Exchange”웹사이트에 제안하여 성능을 끌어올리는 공을 세우게 됩니다. Chris는 이후에도 배합하는 blending 기술을 개선시키며 블랜더(blender)를 발전시켜 나가게 됩니다. 이 때부터 이 팀은 “Vandelay Industries”로 팀명을 개선하고 대부분의 시간을 알고리즘을 개선시키는데 할애하였으며 2009년 5월에는 Netflix Prize에 순위표인 Leader Board상에 15위까지 올라가게 됩니다. 그리고 Netflix LeaderBoard 와 Forum 에서 적극적으로 합류 요청 메일을 보내고 대화를 걸기 시작합니다. 순위권의 참가자들은 아직 “Vandelay Industries”가 우승 가능성이 높아보이지 않아 합류에 대해 적극적으로 검토하지는 않았지만 몇몇은 시험삼아 블랜딩 해본 후 함께할 때 성능이 향상될 수 있음을 보면서 팀원으로 합류하게 됩니다. 마침내 6월이 되서 “Vandelay Industries”팀은 Top 10안에 들어가게 됩니다. 이 때, “BellKor’s Pragmatic Chaos”팀이 CineMatch 대비 10.05% 향상시키며 최종 Grand Prize 까지 30일이 남은 상황인 last call에 돌입하게 됩니다.
The Ensemble team
2009년 7월 26일 18:42:37 UTC 까지 30일의 시간이 주어졌고, 이제 “BellKor’s Pragmatic Chaos”팀을 제외한 다른 팀들 중 CineMatch 기준 10% 성능향상을 시킨 팀은 아무도 없었습니다. Top 10 안에 있던 팀들인 “Grand Prize Team”, “Vandeley Industries”, “Opera Solutions” 등이었고 각 팀은 남은 기간동안 최선을 다해 성능을 끌어올렸지만 한계에 직면한 것 같았습니다.
2009년 7월 24일, 최종 제출 마감 2일 전 “Vandeley Industries”의 팀원들은 “Grand Prize Team”에 조인해야 한다고 의견을 함께합니다. 그 때 팀원들이 이야기 합니다.
“백만달러는 우리가 지금까지 이렇게 열심히 달려온 이유가 아니야. 대회가 시작되었을 때 대부분의 사람들은 10%의 목표가 불가능하다고 이야기 했었어. 하지만 우린 지금 6개월간 불가능을 이뤄 내고 있어. 우리의 목표는 10%의 성능향상을 만들어 내는 것이야.”
대회 마감 하루 전 우승 후보인 “BellKor’s Pragmatic Chaos”팀을 제외한 “Grand Prize Team”, “Vandeley Industries”, “Opera Solutions”이 모두 조인하며 통합을 의미하면서 동시에 기계학습의 배합알고리즘을 의미하는 “The Ensemble”팀이 만들어 집니다.
“우리 The Ensemble 팀의 성공은 단순히 기술적으로 데이터를 통합시키는 것만을 의미하는 것이 아니다. 30일도 안되는 짧은 시간동안 여러 사람들을 통합시키고, 함께 만들어 가는 팀이 될 수 있었기에 성공이었다.”
최종 제출 카운트다운
본 최종 제출 카운트다운 의 내용은 “The Ensemble”팀의 블로그 포스팅 “Final Submission Countdown”의 내용을 작성자인 Lester Mackey의 허락을 받아 번역한 것 입니다. 화자의 입장을 최대한 살리기 위해 구어체를 섞어 작성하였습니다. 본 챕터에서는 “Lester Mackey”의 화자 시점으로 The Ensemble팀의 최종 제출 직전의 상황을 묘사하고 있습니다.
Ensemble팀 리더 Gabor에게 내가(Lester Mackey) 최종 결과를 제출하는 순간, 대회 마감 시한 11:42 AM 을 불과 16분 남겨두고 있었다. 우리 팀원들은 밤새 일하면서 전날 스코어였던 RMSE 0.8554를 뛰어넘길 원했다. 우리는 놀랍게도 Last call 29일 동안 1위를 차지하고 있었던 “BellKor’s Pragmatic Chaos (BPC)” 연합팀을 불과 24시간 전에 물리치고 현재 1위를 달리고 있었다. BPC 팀이 쉽게 물러나지 않을 것이 확실했기 때문에, 기뻐할 시간은 없었고 남은 시간 더 훌륭한 결과를 내기 위해 노력해야 했다. 넷플릭스에서 최종 제출 공지가 다시 발표된 후 200개에 가까운 새로운 결과들이 제출되었다. 이 중 몇몇은 과거 저조한 실적을 뛰어넘는 것이었고, 마지막 순간까지 누구든 더 높은 결과를 제출할 수 있는 상황이었다. 우리에게 마법이 필요한 순간이었다.
11:26 AM
Me (Lester Mackey) : gabor(팀장)~ 최고치를 경신한 새로운 결과가 나왔어.
Me : 이게 어떻게 가능했는지 나도 모르겠지만 RMSE 0.8553 이야.
11:27 AM
Gabor : Blender 수치는 어떻게 나왔어?
Me : 0.855345926622, 지금까지중 최고수치야!
우리가 결과파일을 제출 시작하려는 시한 9분 전에 제출할 수 있는 창이 떳다. Gabor는 구글 챗으로 제출 예정까지 남은 시간을 계속 알려달라고 했었다.
11:28 AM
Me : 5분 전.
제출까지 더 할일이 있지는 않았지만 일부러 기다렸다.
11:29 AM
Me : 4분 남았어
Me : BPC는 우리와 현재까지 동점이야. 으~~~
사실, 조금 전 BPC 팀이 우리가 어제 제출한 1등 결과와 동점인 결과를 제출 한 상태였다. 나는 동료들의 리액션을 확인했고 David W.는 계속적으로 왜 아직 최종결과를 제출하지 않았냐고 성화였다. (David W.의 시계가 13분 빨랐다.)
11:30 AM
Me : 3분.
11:31 AM
Me : 2분전.
11:32 AM
Me : 잠깐,
Me : Peng이 0.8552 결과를 얻었대!!
그랬다. 1분을 남겨두고 Peng 이 마지막 블렌딩 결과가 올라온 것을 봤다. 0.85525 였다. 이 수치는 우리가 제출해야 할 수 있는 최고의 결과였다. 서버에 접속해서 재빨리 결과파일을 찾아보았지만 수백개 파일 중 어떤 파일을 받아야 할지 알수 없었다.
11:33 AM
Me : Peng, 어떤 파일이야! 빨리!
대답이 없었다. Peng 은 내 채팅창에는 보이지 않았거나 그의 인터넷이 끊긴거 같았고 다시 블랙베리로 문자를 보냈다.
11:34 AM
Me : 어떤 파일이야!
Jacob : 이게 지금 최고의 RMSE 결과 맞지? 우리는 이걸로 반드시 제출 해야해!
Gabor : 1분, 지금 제출해야해!
11:35 AM
Me : 우린 지금 어떤 파일인지 몰라!!! 빨~~~~~~리~~~~!!!
Ces : 우리 지금 제출해야 되지 않아?!
Gabor : Lester!!!!!!!
내가 얼마나 좌절했는지 상상이 가나요? 현재 우리가 정해둔 제출 시한에서 이미 2분이 지났고 대회 제출 마감까지는 7분이 남아있었다. 나는 미친 듯이 폴더의 파일을 뒤지며 0.85525 이름을 가진 파일이 있는지 살폈지만 찾을 수 없었다.
11:36 AM
Gabor : !!!
Me : 모르겠어!! 못찾겠어!
Gabor : OK
Gabor : 난 그냥 네가 준걸로 제출하겠어.
그 순간, 나는 파일을 찾았다.
11:37 AM
Me : 잠깐!
Me : 찾았어. opera_est_0.855259.txt.gz
11:38 AM
Gabor : 업로딩 중..
Me : OK, AWESOME
Gabor : 우리가 마감보다 늦어지지 않을지 조금 걱정돼는데.
Me : 음. 어. 아직 11:42은 아니야.
11:39 AM
Gabor : 그치만 업로딩이 너무 느려.
Me : 4분 여유가 있어. 될거야.
Gabor : OK, 제출 성공 🙂
Yes, 제출에 성공했다.
Me : 이건 정말 우리 팀에 대한 모든 것이야, 아슬아슬 사는 구나 🙂
20 minutes
마침내, 대회는 종료되었습니다. 그리고 Netflix Grand Prize의 최종 우승팀은 “The Ensemble”팀의 예상과는 다르게 “BellKor’s Pragmatic Chaos”팀이 수상하게 되었습니다. 본 블로그 (1)편 포스팅에서 소개했던 대회의 최종 규칙과 같이 실제 최종 결과는 quiz set이 아닌 test set데이터를 통해 나온 RMSE Score로 산출합니다. test set의 점수는 공개되지 않아 넷플릭스가 최종 발표하기 전에는 알 수가 없었지만 quiz set과 거의 유사한 경향이 나타나는데요, 그러나 test set의 최종 결과는 아래 그림 처럼 동점이었습니다.
최종 제출 결과는 동점이었기 때문에, Netflix 주최측에서는 대회 규정에 따라 20분 먼저 제출한 “BellKor’s Pragmatic Chaos”팀의 우승한 것으로 발표하게 되었습니다. 당시 넷플릭스의 CEO Reed Hastings는 수상자 선정 결과에 대해서 “That 20 minutes was worth a million dollars”라는 코멘트를 남겼습니다.
대회가 굉장히 아슬아슬하게 진행되었고 결국 성공적으로 마무리 되면서 당시 대부분의 주요 언론사에서 기사들이 게제되었고, 넷플릭스는 큰 홍보효과를 누리게 됩니다.
마치며
처음에 가볍게 대회 진행 과정을 서술하면 재미있겠다 싶어 작성한 글이 꽤 길게 이어졌네요. 데이터 예측 알고리즘 경쟁 대회가 스포츠 만큼이나 아슬아슬하고 드라마틱하게 전개될 수 있다는 것을 잘 보여주는 사례라고 생각되어 굉장히 흥미로웠는데 읽는 분들도 그렇게 느껴지셨다면 좋겠습니다.
이러한 데이터 마이닝 경진대회는 Kaggle에 많이 올라오고 있고, “KDD Cup”으로 학회 차원에서도 매년 진행되고 있는데요. 언어의 장벽이 별로 없고 대회 규칙이 명료하기 때문에 수학에 뛰어난 우리나라에서도 많은 사람들이 도전해 볼만한 대회인 것 같습니다.
한편으로 유독 Netflix Prize가 이러한 경진대회에서 크게 주목을 받을 수 있었던 이유는 실제 사용자의 빅데이터를 제공한 첫 대회라는 점이라고 볼 수 있습니다. 하지만 저는 대회 진행과정을 보면서 그것만이 아닌 하나의 “운”과 같은 요소가 있다고 보여졌는데요. Netflix 참가자들도 언급을 많이 한 것처럼 Grand Prize 기준을 10%라는 수치를 설정하였는데 이 수치가 불가능한 것 같으면서도 결국 달성 가능했다는 것은 운이 따른 것이 아닌가 싶은 생각도 듭니다. 대회 규칙에서도 5년동안 10% 달성팀이 나오지 않으면 대회는 거기서 종료된다고 밝히고 있는데요. 그만큼 10% 목표가 과연 가능할지, 또는 너무 쉬운 목표는 아닌지 가늠하는 것은 주최측도 몰랐던 것 같습니다. 우연히도 이 목표가 굉장히 적절했기에 결국 마지막에”BellKor’s Pragmatic Chaos”팀과 “The Ensemble” 두 팀만이 이 목표를 넘어서면서 대회가 성황리에 마무리 될 수 있었습니다.
또한, 대회가 진행되는 과정에서 연구에서의 “Crowdsourcing”이 가져올 수 있는 가능성을 증명했습니다. 참가자들이 서로 협력하는 과정에서 성능이 지속적으로 좋아지고 새로운 방법들이 개발되면서 추천 시스템분야의 발전에 큰 성과가 있었습니다.
저는 알고리즘 분야야 말로 소수의 천재들이 성과를 달성할 수 있는 분야라고 생각해 왔는데, 대회 과정을 통해 여럿이 함께 연구하는 것이 얼마나 중요한 지 잘 와 닿았습니다. 보다 많은 분야에서 이와 같은 사례가 계속 나올 수 있으면 좋겠습니다.
관련된 정보가 스닙팟 에서도 #주제 별로 공유되고 있어요.
🔗 #인공지능 정보 모음 팟
🔗 #인공지능 대회 정보 모음 팟
🔗 #넷플릭스 콘텐츠 정보 모음 팟
