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], выставленных фильмам клиентами. На основе этой базы данных Netflix рекомендует клиентам фильмы, которые им с большой вероятностью понравятся. Алгоритм, предсказывающий, насколько тот или иной фильм понравится клиенту, основан на линейной регрессии^[3] и называется Cinematch.

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

Данные

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

• Обучающие данные (training data set) содержат 100.480.507 оценок, которые 480.189 клиентов поставили 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 оставляет за собой право дисквалифицировать любого участника. https://www.netflixprize.com/assets/rules.pdf Архивная копия от 10 мая 2020 на Wayback Machine
2. "The Netflix Prize Rules"  (неопр.). Дата обращения: 21 августа 2007. Архивировано 3 марта 2012 года.
3. Netflix Prize: FAQ Архивировано 21 августа 2007 года.
4. James Bennett (12 августа 2007). "The Netflix Prize" (PDF). Proceedings of KDD Cup and Workshop 2007. Архивировано из оригинала (PDF) 27 сентября 2007. Дата обращения: 25 августа 2008. {{cite conference}}: Неизвестный параметр |coauthors= игнорируется (|author= предлагается) (справка) Источник  (неопр.). Дата обращения: 20 января 2008. Архивировано из оригинала 27 сентября 2007 года.
5. Sigmoid Curve. "Miss Congeniality"  (неопр.). Netflix Prize Forum (8 октября 2006). Дата обращения: 25 августа 2008. Архивировано из оригинала 3 марта 2012 года.
6. prodigious. "A single customer that rated 17,000 movies"  (неопр.). Netflix Prize Forum (6 октября 2006). Дата обращения: 25 августа 2008. Архивировано из оригинала 3 марта 2012 года.
7. YehudaKoren. How useful is a lower RMSE?  (неопр.) Netflix Prize Forum (18 декабря 2007). Архивировано из оригинала 3 марта 2012 года.
8. "Netflix Prize Rankings"  (неопр.). Hacking NetFlix (9 октября 2006). Дата обращения: 21 августа 2007. Архивировано из оригинала 3 марта 2012 года.
9. "Netflix Prize (I tried to resist, but...)"  (неопр.). Juho Snellman's Weblog (15 октября 2006). Дата обращения: 21 августа 2007. Архивировано из оригинала 3 марта 2012 года.
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  (неопр.). Архивировано из оригинала 17 декабря 2007 года.
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  (неопр.). Дата обращения: 22 сентября 2009. Архивировано 25 сентября 2009 года.

Ссылки

• Официальный сайт
• 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
• Официальный набор данных, со всеми оценками — в настоящий момент не доступен.