Netflix Prize

Netflix предоставила обучающий набор данных, включающий 100 480 507 оценок, поставленных 480 189 пользователями 17 770 фильмам. Каждая оценка в обучающем наборе представляет собой кортеж из четырёх элементов: <пользователь, фильм, дата оценки, оценка>. Поля пользователя и фильма указывались как целочисленные идентификаторы, а оценки принимали значения от 1 до 5 (целое число) звёзд^[3].

Проверочный (qualifying) набор данных содержал свыше 2 817 131 тройки вида <пользователь, фильм, дата оценки>, причём значения оценок были известны только жюри. Задача алгоритма участвующей команды заключалась в прогнозировании оценок по всему проверочному набору, однако участникам сообщался результат только по половине данных: так называемому quiz-набору из 1 408 342 оценок. Вторая половина — test-набор из 1 408 789 оценок — использовался жюри для определения потенциальных победителей. Только организаторы знали, какие оценки относятся к quiz, а какие — к test-набору, что препятствовало подбору решения только под test-набор. Итоговая оценка производилась сравнением прогнозов и фактических оценок с помощью метрики корня из среднеквадратичной ошибки (RMSE), и целью было минимизировать это отклонение. При этом реальные оценки были целыми числами от 1 до 5, но предсказываемые значения могли быть произвольными числами в этом диапазоне. Также Netflix выделила так называемый probe-набор из 1 408 395 оценок внутри обучающего набора. Probe, quiz и test наборы отбирались так, чтобы их статистические характеристики были сопоставимыми.

Итогово, наборы данных для Netflix Prize имели следующую структуру:

• Обучающий набор (99 072 112 оценок без учёта probe; 100 480 507 с учётом probe)
  • Probe-набор (1 408 395 оценок)
• Проверочный набор (2 817 131 оценка), включающий:
  • Test-набор (1 408 789 оценок) — определял победителей
  • Quiz-набор (1 408 342 оценки) — рассчитывался для онлайн-рейтинга

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

Обучающий набор был сконструирован так, что в среднем один пользователь оценивал более 200 фильмов, а каждый фильм получал оценки от более чем 5000 пользователей. Однако разброс был весьма велик: некоторые фильмы были оценены всего тремя пользователями^[4], а один пользователь оценил более 17 000 фильмов^[5].

Выбор RMSE в качестве основной метрики вызывал определённые дискуссии. Некоторые утверждали, что даже улучшение RMSE на 1 % значительно меняет топ-10 рекомендаций для пользователя^[6].

Призы начислялись за улучшение результата относительно собственного алгоритма Netflix, известного как Cinematch, либо по отношению к результату предыдущего года (если команда улучшила результат выше определённого порога). Базовый («тривиальный») алгоритм — прогнозирование для каждого фильма средней оценки по обучающему набору — давал RMSE 1,0540. Cinematch использовал «простые статистические линейные модели с обработкой данных»^[7] и по состоянию на 2006 год его результат не улучшался^[8].

Cinematch показывал на тестах RMSE 0,9514 по quiz-набору, что примерно на 10 % лучше тривиального алгоритма. Аналогичный результат был на test-наборе: 0,9525. Чтобы выиграть главный приз (1 000 000 долларов США), команда должна была улучшить этот показатель ещё на 10 % — до 0,8572 на test-наборе^[2]. Для quiz-набора это соответствовало бы RMSE 0,8563.

До того, как кто-либо бы получил главный приз, ежегодно вручался промежуточный progress-приз в размере 50 000 долларов США за лучший на тот момент результат. Однако, чтобы получить этот приз, нужно было улучшить RMSE по quiz хотя бы на 1 % относительно результата предыдущего лауреата progress-приза (или по сравнению с Cinematch в первый год). Если ни одна заявка не преуспевала, в этом году progress-приз не вручался.

Для получения промежуточного или главного приза участник должен был в течение недели после вызова со стороны жюри предоставить исходный код и описание алгоритма. После проверки победитель обязан был выдать Netflix неисключительную лицензию на решение. Описание алгоритма, а не исходный код, публиковалось компанией Netflix (алгоритм и исходный код можно было не предоставлять, пожертвовав призом). Предсказания алгоритмов других участников не раскрывались. От команд принималось неограниченное количество заявок. Изначально установлено ограничение — не чаще одного раза в неделю, вскоре пересмотрено до одной попытки в день. В качестве текущего результата учитывалась лучшая из всех заявок команды.

После достижения командой 10%-ного улучшения RMSE объявлялся last call — финальный этап длительностью 30 дней для всех участников, после чего запрос описания и исходников направлялся только лидеру; после верификации команда объявлялась победителем.

Конкурс продолжался до объявления победителя или, если главный приз не был завоёван, длился не менее пяти лет (до 2 октября 2011 года). После этой даты Netflix имела право объявить о завершении конкурса в любой момент.

Соревнование стартовало 2 октября 2006 года. Уже 8 октября команда WXYZConsulting превзошла результат Cinematch^[9].

К 15 октября уже три команды улучшили результат по сравнению с Cinematch, одна из них — на 1,06 %, что позволило претендовать на ежегодный progress-приз^[10]. К июню 2007 года свыше 20 000 команд из более чем 150 стран зарегистрировались на участие; 2 000 команд отправили более 13 000 наборов предсказаний^[3].

В первый год соревнования несколько команд сменяли друг друга на первой позиции. К числу заметных лидеров относились:^[11]

• WXYZConsulting (Вэй Сюй и И Чжан) — лидировали в ноябре—декабре 2006;
• ML@UToronto A — команда из Торонто, под руководством профессора Геоффри Хинтона, лидировала осенью-зимой 2006;
• Gravity — команда четырёх венгерских учёных из Будапештского технологического университета, в числе лидеров в январе—мае 2007;
• BellKor — группа из AT&T Labs в лидерах с мая 2007;
• Dinosaur Planet — три студента из Принстона, лидировали на один час 3 сентября 2007 года, пока BellKor не вернули себе первое место.

Ведущие команды, как правило, применяли ансамблевые методы — сингулярное разложение матриц, метод k-ближайших соседей, нейронные сети и другие.^[12]

12 августа 2007 года многие участники встретились на конференции KDD Cup and Workshop 2007 в Сан-Хосе, Калифорния^[13]. Все четыре команды-лидера на тот момент представили свои методы. Третье место (задача 1) и первое место (задача 2) заняла команда IBM Research: Янь Лю, Сахарон Россе, Клаудия Перлих и Чжэньчжэнь Коу.

На втором году соревнования на вершине рейтинга оказывались:

• BellKor — AT&T Labs (май 2007 — сентябрь 2008);
• BigChaos (Австрия, Commendo Research & Consulting) — единоличный лидер с октября 2008;
• BellKor in BigChaos — объединённая команда этих двух (сентябрь 2008 и далее).

2 сентября 2007 года был объявлен 30-дневный финальный этап («last call») к progress-призу 2007 года. В конкурсе участвовало уже более 40 000 команд из 186 стран. На старте лидировала BellKor (RMSE 0,8728, улучшение 8,26 %), далее — Dinosaur Planet (0,8769; 7,83 %)^[14] и Gravity (0,8785; 7,66 %). В последний час финального этапа под именем «KorBell» появилось новое первое место; выяснилось, что это альтернативное имя команды BellKor^[15].

13 ноября 2007 года победителем промежуточного приза ($50 000) объявлена команда KorBell (бывшая BellKor) с RMSE 0,8712 (улучшение на 8,43 %)^[16]. В неё вошли сотрудники AT&T Labs: Яхуда Корен, Роберт Белл и Крис Волинский^[17]. Как того требовали правила, опубликовано подробное описание их алгоритма.

В 2008 году progress-приз вновь достался BellKor: их объединённая с BigChaos заявка достигла RMSE 0,8616, используя 207 индивидуальных предсказаний^[18]. Совместная команда состояла из двух сотрудников австрийской компании Commendo Research & Consulting GmbH (Андреас Тёшер и Михаэль Ярер, изначально BigChaos) и трёх сотрудников AT&T Labs (Яхуда Корен, Роберт Белл и Крис Волинский, изначально BellKor)^[19]. Как того требовали правила, опубликованы их описания алгоритмов^[20][21].

Это был последний progress-приз, так как улучшение хотя бы на 1 % над результатом 2008 года означало победу в финале. Все выигранные средства были переданы выбранным командой благотворительным организациям.

26 июня 2009 команда «BellKor’s Pragmatic Chaos» (слияние «BellKor in BigChaos» и «Pragmatic Theory») достигла 10,05%-го улучшения над Cinematch (Quiz RMSE 0,8558), после чего был объявлен 30-дневный финальный этап для главного приза^[22].

25 июля 2009 команда «The Ensemble» (объединение Grand Prize Team и Opera Solutions & Vandelay United) чуть превзошла данный результат (RLSE 0,8554, улучшение 10,09 %)^[23][24].

26 июля 2009 Netflix прекратила приём новых заявок на конкурс^[25]. В итоговой таблице оказалось две команды, соответствующие условиям главного приза: «The Ensemble» (улучшение 10,10 %, RMSE 0,8553) и «BellKor’s Pragmatic Chaos» (улучшение 10,09 %, RMSE 0,8554)^[26][27]. Победителя определяло сравнение результатов на test-наборе.

18 сентября 2009 Netflix объявила, что победителем стала «BellKor’s Pragmatic Chaos» (Test RMSE 0,8567), а награждение прошло 21 сентября^[28]. «The Ensemble» повторила результат, но команда BellKor отправила решение на 20 минут раньше^[24][29].

Объединённая команда «BellKor’s Pragmatic Chaos» включала двух австрийцев из Commendo Research & Consulting (А. Тёшер и М. Ярер, ранее BigChaos), двух сотрудников AT&T Labs (Р. Белл, К. Волинский), Яхуду Корена из Yahoo! (ранее BellKor), а также Мартина Пьотта и Мартина Шаббера из Pragmatic Theory^[30]. Описание их алгоритма опубликовано как требовал регламент^[31].

Антилидер по худшим значениям RMSE на quiz- и test-наборах был «Lanterne Rouge» под руководством J. M. Линакра — он же участвовал в «The Ensemble». По словам Линакра, результат был специально сделан заведомо плохим, что соответствовало духу названия Lanterne rouge^[32].

По завершении конкурса Netflix объявила о планах проведения продолжения: участникам предполагалось предоставить демографические и поведенческие данные (возраст, пол, индексы местности, жанровые предпочтения и просмотренные фильмы, но не оценки), а задачей бы стало прогнозирование предпочтений пользователей. Победитель определялся бы не абсолютной точностью, а лидерством на соответствующем этапе: $500 000 по итогам 6 месяцев и ещё $500 000 по завершении 18 месяцев^[29].

12 марта 2010 года Netflix официально объявила об отказе от проведения второго конкурса, ссылаясь на судебные и регуляторные претензии, связанные с приватностью данных^[33]. Первый progress-призёр Волинский высказал разочарование отменой^[12].

Несмотря на попытки анонимизации, конкурс вызвал критику со стороны защитников приватности. В 2007 году двое исследователей из Техасский университет в Остине (Виталий Шматиков и Арвинд Нараянан) смогли идентифицировать отдельных пользователей, сопоставив данные Netflix Prize с открытыми пользовательскими оценками на Internet Movie Database^[34][35].

17 декабря 2009 года четверо пользователей Netflix подали коллективный групповой иск против компании — утверждая, что Netflix нарушила законы США о честной торговле и закон о приватности записей о видео-просмотрах (Video Privacy Protection Act), опубликовав соответствующие наборы данных^[36]. Это вызвало публичные дебаты о приватности участников исследований. 19 марта 2010 Netflix заключила мировое соглашение с истцами, и те добровольно отозвали иск.