NETFLIX PRIZE – 다이나믹 했던 알고리즘 대회 (2)

NETFLIX PRIZE 진행과정을 담은 포스트 (2)편 입니다.

지난 (1)편은 Netflix Prize가 어떤 대회이고 규칙과 평가기준 등을 살펴보았는데요. 간단한 내용을 복습하시고 (2)편을 보시면 조금 더 내용이 와닿을 것 같습니다. 🙂

Grand Prize Winner : BellKor’s Pragmatic Chaos

최종 우승한  7명의 “BellKor’s Pragmatic Chaos”팀 멤버들

우승 상금 백만달러를 수여받은  2009 Grand Prize의 우승팀은 이름은 좀 긴 “BellKor’s Pragmatic Chaos” Team입니다. 최종 우승 팀의 이름이 왜 이렇게 긴 이름이 되었는지를 보면 3여년에 걸친 대회가 어떻게 진행 되었는지 알 수가 있는데요. 이유는 이 팀의 성장이 사실 Netflix Prize 대회의 성장과 궤를 같이 했기 때문입니다. 처음부터 3년에 걸친 장대한 대회의 결말을 알려드렸지만, 그 과정이 결과보다 흥미진진하기 때문에 기대하셔도 좋습니다. 🙂 그럼 최종 대회 이전의 2007년 대회 진행 상황으로 돌아가 볼까요?

Progress Prize 2007 Winner : BellKor

2007 우승한 AT&T Labs의 BellKor Team (좌부터  Chris Volinsky, Yehuda Koren, Bob Bell)
“BellKor” Team 이름은 팀 멤버의 이름중 “Bell”과 “Koren”의 “Kor”를 조합했습니다. Chris Volinsky 는  AT&T Statistics Research Group 의 Director였는데 아마도 리더라 너그럽게 본인의 이름이 들어가지 않았지만 발음하기 좋은 이름으로 정하지 않았을까 싶습니다.

2006년 10월 2일 넷플리스 대회가 시작 되었고, 초반 두달간은 칭화대 출신 WXYZConsulting 팀이 선두를 달리기 시작하였습니다. 이 두달동안 넷플릭스 Cinematch 알고리즘 보다 약 5% 수준의 성능 향상이 급속히 이뤄지는데요, 이때부터 추천 알고리즘의 대표적인 방법인 SVD (Singular Value Decomposition)가 대부분 참가팀의 메인 알고리즘으로 사용됩니다. 후술하겠지만 추천결과를 만들기 위해 단 하나의 알고리즘이 아닌 100여개 이상의 알고리즘을 통해 결과를 만든 후 이를 다시 통합하여 예측 성능을 향상 시키는 데요, 이 때 단일 알고리즘으로서 SVD가 가장 좋은 성능을 보여줍니다. SVD는 선형대수에서 쓰이는 Matrix Factorization기법 중 하나로 이미 유명했지만 추천 문제와 같이 데이터에 알 수 없는 값들이 대부분인 경우 그대로 적용할 수 없고 기계학습을 통해 추론하는 과정에서도 과적합(Overfitting)등의 문제가 나타나기 쉬워 추천알고리즘으로 구현하는 것에 어려움이 있었습니다.

2006년 12월 Simon Funk라는 이름으로 활동하여 더 잘 알려진 소프트웨어 개발자 “Brandyn Webb”이 Gradient Descent 방법을 통해 어떻게 SVD를 Netflix Prize 문제에 적합하게 SVD를 구현할 수 있는지 코드와 방법을 “Try this at Home”이라는 제목으로 블로그에 상세히 공개합니다. (Simon Funk 의 “Netflix Update: Try This at Home”)

그리고, Simon Funk 가 공개한 SVD 알고리즘은 이후 대부분의 참가 팀이 참고하여 사용하게 됩니다. 우승한 “BellKor”팀도 Simon Funk Blog를 참고하여 적용하였음을 논문에서 언급합니다.

Simon Funk 본인도 대회 중 3위 까지 올라갈 정도로 좋은 결과 (6%대의 성능향상)를 제출했었는데요, 휴가기간에 뉴질랜드에서 비행기에 오르던 중 친구에게 Netflix Prize에 대한 소식을 접하게 되면서 여유있는 시간에 참여한 것 치고는 정말 대단한 것 같습니다. 인터뷰에서 마침 여유가 있던 시기였다고 하는데, 노는 것 보다 더 넷플릭스 대회가 끌렸던 것을 보면 데이터 마이닝에 대한 열정이 대단한 분인 것 같습니다. 친구가 보낸 메일에는 다음과 같이 써 있었다고 하네요.

It looks like someone designed the contest of your dreams.

All you need to develop is the guts of the thing–no UI, no communications stuff, no infrastructure, no ancillary programs, no integration, no hardware or hardware interfaces. No need to recruit, pay, or work with a team. No tedious grant writing. No fund raising. No PR.

2007년 대회 참가자들이 제출한 결과는 Simon Funk가 알고리즘을 공개하면서 상향 평준화 되기 시작하고 150여개국 20,000개가 넘는 팀이 넷플릭스 대회에 등록하여 경쟁하기 시작합니다.  2007년 5월 AT&T Lab의 연구원으로 이뤄진 “BellKor” 팀이 7%이상의 성능을 향상시키며 선두를 차지하게 되고 “Dinosaur Planet”팀과 “Gravity” 팀이 각각 RMSE 0.8769, 0.8785 로 바짝 따라붙습니다.

Gravity & Dinosaur Planet Team

Progress Prize 2007 Final RMSE Score

2007 최종 제출된 결과를 보면 “KorBell” 팀과 “BellKor” 팀이 각각 1,2위를 차지한 것으로 보이지만 사실 같은 팀이 두개의 이름으로 제출한 것이고 (그래서 공식 발표상에서는 “KorBell”팀이 우승한 것으로 나옵니다), 그 뒤로는 “When Gravity and Dinosaurs Unite” 팀이 뒤따르고 있습니다.

Gravity팀은 Gabor Takacs 를 리더로 하는 헝가리 연구원 4명으로 구성된 팀이었으며 Dinosaurs Planet은 프린스턴 대학의 학생 3명으로 구성되어 있었습니다. 이 두 팀은 계속 “BellKor”팀에 필적할만한 성능의 결과를 냈지만, 아쉽게도 약간씩 뒤쳐지다 데드라인인 10월 1일 하루 전 연합하여 “Gravity and Dinosaurs Unite” 팀을 결성하며 1위를 차지하게 됩니다. 하지만 결국 마지막 제출 시간일인 10월 1일 BellKor 팀은 다시  “Gravity and Dinosaurs Unite” 연합팀을 앞지르며 RMSE Score test set 에서 0.8728로 Netflix Cinematch보다 8.26 % 우수한 성능으로 첫해 우승을 차지 합니다.

비록 “Gravity”와 “Dinosaurs Planet”팀은 결국 우승하지 못했지만 개별 팀의 결과를 합하면 우승팀을 위협할 수 있을 정도로 결과가 상승할 수 있음을 직접 경험하게 됩니다.

 

Progress Prize 2008 Winner : BellKor in BigChaos

2008년 “또” 우승한 “BellKor in BigChaos” 팀 로고

2008년 대회가 다시 1년의 긴 장정을 시작하였습니다. 대회 규칙 중 하나는 지난 년도 우승팀이 별다른 큰 성능 향상 없이 쉽게 또 우승을 하지 않도록 하기 위해서 지난 년도 우승 팀 성능에서 최소 1%이상의 성능 향상이 있어야 한다는 추가 규칙이 있었습니다. (1)편 포스팅에서도 언급한 것처럼 백만달러의 상금이 걸린 Grand Prize 는 넷플릭스 Cinetmatch 보다 10% 이상의 성능을 향상시켜야 했는데 이 수치가 거의 불가능에 가까운 결과가 아닌가 에 대한 참가자들의 볼멘소리도 있었습니다. 그만큼 성능 향상이 이제 쉽지 않은 단계에 접어들었지만 “BellKor”팀은 오스트리아의 commendo research and consulting을 창업한 기계학습 분야 연구원 2명으로 이루어진 “Big Chaos”팀과 엽합하여 “Bellkor in BigChaos” 팀으로 확장하며 2008년 9월 30일 Cinematch대비 9.44% 향상된 결과를 제출, 우승하게 됩니다. “BellKor”팀원은 2년 연속 우승하게 된 것이죠. 2008년도에는 원래 AT&T 연구원이었던 “Yahuda Koren”이 이스라엘에 있는 Yahoo Research Lab 으로 이직하면서 AT&T, Yahoo, Commando Research 3개 회사 5명으로 이뤄진 팀이었습니다.

대회가 진행되는 과정 동안 보였던 가장 긍정적인 부분 중 하나는 참가한 사람들이 서로 경쟁자이지만 한편으론 협력자로서 서로 간에 정보를 기꺼이 공유하는데 적극적이었다는 점 입니다. 기본적인 대회 규정 상 매해 우승 팀들은 우승하는 데 사용한 알고리즘을 논문 등의 형태로 발표하여야 했으며(2008 대회 우승팀 solution), 우승 팀 뿐 아니라 대부분의 팀들은 Netflix Prize Forum을 통해 발견한 알고리즘이나 정보를 기꺼이 공유하고 서로 협력하였습니다. 또한 대회 기간 중 “KDD”와 같은 데이터 마이닝 학회에서도 실험결과와 노하우들이 활발히 공유되었습니다. 2009년에는 KDD Best Paper로 “Yahuda Koren”의 Collaborative Filtering with Temporal Dynamics” 논문이 수상하는 등 학술적으로도 큰 성과를 이루었습니다. 그리고 이러한 활동들 덕분에 다음해인 2009년, 처음에는 불가능해 보였던 10% 이상의 성능 향상을 달성하게 됩니다.

Final Grand Prize 2009 대회의 진행 과정은 마지막이 될 것으로 생각되는 (3)편으로 이어집니다. (3)편은 빠르게 업데이트 할 예정입니다~
AT&T 에서 공개한 8분여의 영상에서 Netflix Prize를 아주 잘 요약했네요. 추천드립니다.
본 포스팅의 내용은 “Netflix Prize Forum” 및 관련 뉴스 기사들, 참가팀의 인터뷰 및 홈페이지, 관련 논문, Wikipidea 등을 참고하여 재구성하였습니다.

 

Netflix Prize – 다이나믹 했던 알고리즘 대회 바로가기

(1)편(3)편