Netflix Prize

Netflix Prize — открытое соревнование на лучший алгоритм предсказания оценки, которую зритель поставит фильму, на основе предыдущих оценок этого и других зрителей. Соревнование проводит Netflix, крупная фирма по аренде DVD. За некоторыми исключениями^[1], участвовать могут все желающие. Главный приз составляет $1,000,000. Для его получения надо улучшить алгоритм фирмы Netflix на 10 %.^[2]

Приз выдан команде BellKor’s Pragmatic Chaos 21 сентября 2009 года.

Общая информация

Netflix — фирма по аренде DVD с годовым оборотом 996 млн долларов (2006), основанная в 1997 году. Клиенты заказывают DVD через интернет и получают (и отправляют) по почте. Клиенты могут выставлять фильмам оценки от 1 до 5. С течением времени Netflix накопила огромную базу данных, содержащую более миллиарда оценок ^[3], выставленныx фильмам клиентами. На основе этой базы данных Netflix рекомендует клиентам фильмы, которые им с большой вероятностью понравятся. Алгоритм, предсказывающий, насколько тот или иной фильм понравится клиенту, основан на линейной регрессии ^[3] и называется Cinematch.

Тривиальный алгоритм, ставящий каждому фильму его среднюю оценку, даёт среднеквадратичное отклонение (СКО) 1,0540. Алгоритм Cinematch, использующий те данные, которые доступны участникам соревнования, даёт СКО 0,9525 на тестовом множестве, то есть он примерно на 10 % лучше тривиального алгоритма. Фирма заплатит главный приз команде, которая сможет улучшить результат ещё на 10 %.

Данные

Все участники (и вообще все желающие) могут скачать следующие 4 файла:

• Тренировочные данные (training data set) содержат более 100 млн оценок, которые более 480 тыс. клиентов поставили 17.770 фильмам. Каждая оценка представляет собой квадруплет <номер клиента, номер фильма, дата оценки, оценка>. Номера клиентов и фильмов — целые числа, оценка — целое число от 1 до 5 (низшая оценка 1, высшая 5).^[4] Таким образом, в среднем каждый клиент поставил около 200 оценок, а каждый фильм получил около 5000. Однако количество оценок сильно варьируется: так, некоторые фильмы получили всего 3 оценки,^[5], а один клиент оценил более 17 тыс. фильмов^[6].
• Квалификационные данные (qualifying data set) содержат 2,8 млн триплетов <пользователь, фильм, дата оценки>. Оценки известны только жюри и будут опубликованы по окончании соревнования.
• Названия и годы выхода в прокат всех 17.770 фильмов.
• Фрагмент тренировочной базы данных, распределённый так же, как квалификационные данные. Этот фрагмент может использоваться, например, для оценки алгоритмов до посылки их на сайт.

Никакой информации о клиентах в базе данных нет.

Для защиты конфиденциальности клиентов, «некоторые данные из тренировочного и квалификационного намеренно искажены одним или более из следующих способов: стирание оценок; вставка альтернативных оценок и дат; модификация дат».^[2]

Каждый участник должен отправить файл с предсказаниями оценок из квалификационного набора данных. Предсказания могут быть и вещественными. В ответ сообщается среднеквадратичное отклонение (СКО) предсказаний, округлённое до 4-го знака после запятой. Список СКО лучших участников также вывешивается на сайте. Сами предсказания держатся в секрете.

Участник может отправлять предсказания не чаще раза в день. Учитывается лучший набор предсказаний каждого участника.

Для того чтобы участник не мог использовать СКО для угадывания оценок, квалификационный набор данных разделён на двое. Участникам сообщаются результаты одной из половинок, называемой quiz set, но для получения приза (любого) учитываются результаты другой половинки — test set. Участники не знают, какая из записей к какой половинке относится.

Были споры по поводу выбора метрики. Действительно ли уменьшение ошибки на 10 % поможет пользователям? По мнению одного из участников соревнования, улучшение ошибки даже на 0,01 существенно изменит список 10 рекомендованных фильмов.^[7].

Призы

Cinematch, используя только те данные, которые доступны участникам, достигает СКО 0,9514 на quiz set и 0,9525 на test set. Это примерно на 10 % лучше тривиального алгоритма, ставящего каждому фильму его среднюю оценку. Для получения главного приза, в 1 млн долларов необходимо улучшить СКО ещё на 10 %, получив 0,8572 на test set. (Такое улучшение соответствует СКО 0,8563 на quiz set.)

До тех пор пока главный приз не будет завоёван, ежегодно лучшей команде будет присуждаться приз за прогресс (progress prize) в размере 50 тыс. долларов. Но для того, чтобы получить этот приз, команда должна улучшить СКО не менее чем на 1 % по сравнению с предыдущим лауреатом приза (в первый год — по сравнению с Cinematch).

Чтобы получить любой приз, команда должна в течение недели предоставить исходный код алгоритма, его описание и неисключительную лицензию на использование его алгоритма компанией Netflix. Исходный код и описание проверяются. Netflix публикует описание, но не исходный код. Сами предсказания также остаются секретными. Команда может отказаться от приза для того, чтобы сохранить в секрете свой алгоритм. Тогда приз получает следующая команда, если её СКО достаточно хорош.

После того, как одна из команд сумеет улучшить СКО на 10 % или больше, жюри даёт всем участникам ещё 30 дней, чтобы послать свои результаты. Затем у команды, пославшей лучший набор предсказаний, запрашиваются описание алгоритма, исходный код и неисключительная лицензия, и, в случае успешной проверки, команда объявляется победителем и получает главный приз. На этом соревнование завершается.

История и результаты

Соревнование началось 2 октября 2006 года. Уже 8 октября команда WXYZConsulting превзошла результаты Cinematch.^[8] К 15 октября было уже 3 компании с результатами лучшими, чем Cinematch. Одна из них превзошла Cinematch на 1,06 %, этого достаточно, чтобы получить приз за прогресс.^[9] К июню 2007 для участия в соревновании зарегистрировались более 20 тысяч команд из более чем 150 стран. 2000 команд послали 13 тысяч наборов предсказаний.

В первый год соревнования лидерами гонки были следующие команды:

• Gravity, группа из 4 учёных из Будапештского технологического университета.
• ML@UToronto A, команда из университета Торонто, возглавляемая проф. Джеффри Хинтоном.
• анонимная команда, называющая себя ICMLsubmission
• BellKor, группа учёных из AT&T

2007

12 августа 2007 многие участники собрались на конференцию «KDD Cup and Workshop 2007».^[10] в Сан-Хосе, Калифорния. На конференции все четыре ведущих группы представили свои техники.

2 сентября 2007 участникам осталось 30 дней до присуждения приза за прогресс 2007 года. В начале этого срока лучший результат был у BellKor с её СКО 0,8728 (улучшение на 8,26 %), за которой следовали Dinosaur Planet (СКО=0.8769; улучшение на 7,83 %) и Gravity (СКО=0.8785; улучшение на 7,66 %). В последний час перед присуждением приза первое место занял KorBell. Как оказалось, это другое имя команды BellKor.

13 ноября 2007, KorBell был объявлен лауреатом приза за прогресс в размере $50,000.^[11] с СКО 0.8712 (улучшение на 8,43 %). Команда состояла из трёх исследователей из AT&T: Иегуды Корена (Yehuda Koren), Роберта Белла (Robert Bell) и Криса Волински (Chris Volinsky).^[12] Как и требуется правилами, они опубликовали описание своего алгоритма.^[13]

2008

BellCor объединился с BigChaos. Объединённая команда «BellKor in BigChaos» достигла улучшения в 9,44 % (СКО=0.8616) и получила приз за прогресс.^[14] Участники команды опубликовали описание использованного алгоритма.^[15][16]

2009

26 июня команда «BellKor’s Pragmatic Chaos», образованная слиянием команд «BellKor in BigChaos» и «Pragmatic Theory», достигла улучшения в 10,05 % (СКО=0.8558) по сравнению с Cinematch^[17], и таким образом соревнование перешло в завершающую фазу. С этого момента всем участникам отводилось 30 дней для отправки окончательных решений.

25 июля, за день до конца соревнования, команда «The Ensemble», образованная слиянием команд «Grand Prize Team» и «Opera Solutions and Vandelay United», опередила «BellKor’s Pragmatic Chaos», достигнув улучшения в 10,09 % (СКО=0.8554).^[18]

26 июля 2009 года, в 18:42:37 UTC приём решений прекращён. В этот момент верхушка таблицы результатов выглядела следующим образом:^[19]

№	Команда	СКО	Улучшение в %	Время отправки
1	The Ensemble	0.8553	10.10	2009-07-26 18:38:22
2	BellKor’s Pragmatic Chaos	0.8554	10.09	2009-07-26 18:18:28

По информации от участников команд на форуме соревнования^[20] и австрийской газеты «Kurier»^[21], на секретной половине данных алгоритм команды «BellKor» превосходил алгоритм «The Ensemble», так что ожидалось, что победителем официально будет признана команда «BellKor’s Pragmatic Chaos».

Согласно правилам, участники победившей команды должны были предоставить компании Netflix описания использованных алгоритмов и исходный код, и только потом Netflix официально объявила победителя соревнования. Им действительно оказалась команда «BellKor’s Pragmatic Chaos». Официальное объявление результатов и церемония награждения состоялись 21 сентября 2009. В тот же день были опубликованы секретные оценки. ^[22]

Как оказалось, на секретной половине данных обе команды улучшили результаты на 10,06 %, но команда «BellKor’s Pragmatic Chaos» прислала свои результаты на 20 минут раньше (см. таблицу).

Примечания

1. ↑ В соревновании запрещено участвовать тем, кто связан с фирмой (нынешние и бывшие сотрудники, агенты, контракторы, близкие родственники перечисленных и т. д.), жителям Квебека, жителям Ирана, Кубы, Мьянмы, Северной Кореи, Сирии и Судана. Кроме того, Netflix оставляет за собой право дисквалифицировать любого участника.
2. ↑ ^{1 2} "The Netflix Prize Rules". Архивировано из первоисточника 3 марта 2012. Проверено 21 августа 2007.
3. ↑ ^{1 2} Netflix Prize: FAQ
4. ↑ James Bennett; Stan Lanning (August 12, 2007). "The Netflix Prize". Proceedings of KDD Cup and Workshop 2007. Проверено 2008-08-25. 
5. ↑ Sigmoid Curve "Miss Congeniality". Netflix Prize Forum (8 октября 2006). Архивировано из первоисточника 3 марта 2012. Проверено 25 августа 2008.
6. ↑ prodigious "A single customer that rated 17,000 movies". Netflix Prize Forum (6 октября 2006). Архивировано из первоисточника 3 марта 2012. Проверено 25 августа 2008.
7. ↑ YehudaKoren How useful is a lower RMSE?. Netflix Prize Forum (18 декабря 2007). Архивировано из первоисточника 3 марта 2012.
8. ↑ "Netflix Prize Rankings". Hacking NetFlix (October 9, 2006). Архивировано из первоисточника 3 марта 2012. Проверено 21 августа 2007.
9. ↑ "Netflix Prize (I tried to resist, but...)". Juho Snellman's Weblog (October 15, 2006). Архивировано из первоисточника 3 марта 2012. Проверено 21 августа 2007.
10. ↑ The KDD Cup and Workshop 2007. Архивировано из первоисточника 3 марта 2012.
11. ↑ Prizemaster Netflix Progress Prize 2007 awarded to team KorBell. Netflix Prize Forum (13 ноября 2007). Архивировано из первоисточника 3 марта 2012.
12. ↑ $50,000 Progress Prize is Awarded on First Anniversary of $1 Million Netflix Prize.(недоступная ссылка — история)
13. ↑ R. Bell, Y. Koren, C. Volinsky "The BellKor solution to the Netflix Prize" (2007). Архивировано из первоисточника 3 марта 2012.
14. ↑ Prizemaster Netflix Progress Prize 2008 to Team BellKor in BigChaos. Netflix Prize Forum (10 декабря 2008). Архивировано из первоисточника 3 марта 2012.
15. ↑ A. Töscher, M. Jahrer "The BigChaos solution to the Netflix Prize 2008" (2008). Архивировано из первоисточника 3 марта 2012.
16. ↑ R. Bell, Y. Koren, C. Volinsky "The BellKor solution to the Netflix Prize 2008" (2008). Архивировано из первоисточника 3 марта 2012.
17. ↑ BellKor's Pragmatic Chaos (26 июня 2009). Архивировано из первоисточника 3 марта 2012.
18. ↑ The Ensemble (25 июля 2009). Архивировано из первоисточника 3 марта 2012.
19. ↑ The Netflix Prize Comes To A Buzzer-Beater, Nailbiting Finish (26 июля 2009). Архивировано из первоисточника 3 марта 2012.
20. ↑ Netflix Prize forum post (26 июля 2009). Архивировано из первоисточника 3 марта 2012.
21. ↑ Die Eine-Million-Dollar-Formel (28 июля 2009). Архивировано из первоисточника 3 марта 2012.
22. ↑ UCI Machine Learning Repository: Data Set

Внешние ссылки

• Официальный сайт
• The $1 million Netflix challenge. Интервью Кейт Грин с вице-президентом Netflix Джимом Беннетом. Technology Review, 6 октября 2006.
• Решения
  • The BellKor Solution to the Netflix Grand Prize
  • The Big Chaos Solution to the Netflix Grand Prize
  • The Pragmatic Theory Solution to the Netflix Grand Prize
• Официальный набор данных, со всеми оценками