Феерический финал конкурса Netflix

    5100 программистских коллективов из 185 стран приняли участие в сугубо гиковском конкурсе Netflix Prize с главным призом в миллион долларов.

    Конкурс завершился вчера в 18:42:37 UTC, ровно через 30 суток после того, как один из претендентов добился требуемого результата (RMSE меньше 0,8563). Финиш получился поистине феерическим: сразу после первого претендента появился второй, между ними разгорелась жесточайшая борьба. Буквально в последние часы претенденты несколько раз менялись местами друг с другом!

    Многие из нас с азартом следили в реальном режиме времени за развязкой этого увлекательного состязания. В итоге победителя от второго призёра разделило всего 0,0001 балла. Судьба миллиона долларов была решена только за 4 минуты до дедлайна — это при том, что конкурс продолжался с 2 октября 2006 года. Кто сказал, что математические конкурсы не могут быть драматическими?



    Компания Netflix занимается прокатом кинофильмов, как в онлайне, так и в оффлайне. Основой их бизнеса является уникальная система рекомендаций Cinematch. Она предсказывает, какие фильмы могут понравиться человеку на основе его прошлых оценок других фильмов. Как известно, именно системы рекомендаций являются чашей Грааля для современных приложений электронной коммерции.

    По правилам конкурса Netflix, на главный приз в миллион долларов могла претендовать команда разработчиков, которая сможет улучшить эффективность Cinematch минимум на 10%. Для настройки конкурсных алгоритмов был опубликован набор исходных пользовательских данных: это 100 млн оценок (от 1 до 5 баллов) по 18 тыс. фильмам от 480 тыс. случайно выбранных юзеров. Для проверки результатов был опубликован набор из пар пользователей и фильмов, а алгоритм должен был максимально точно предсказать выставленные оценки, при этом подсчитывалась средняя ошибка RMSE (root mean squared error). Она должна была минимум на 10% улучшить показатель алгоритма Cinematch (0,9525). То есть нужно было показать 0,8572 или меньше.

    Конкурс продолжался почти три года. Разработчики демонстрировали всё лучший результат, и в конце концов несколько команд программистов решили объединить усилия и совершить рывок. Так появилась команда BellKor's Pragmatic Chaos, которой 26 июня 2009 года наконец-то удалось улучшить результат на заветные 10,08%. По правилам, после этого у остальных участников было 30 суток, чтобы улучшить результат. И конкуренты воспользовались шансом. Менее чем за 24 часа до дедлайна команда The Ensemble улучшила результат до 10,09%.

    Программисты из BellKor тоже не спали в шапку. Видимо, они были готовы к этому, и за 24 минуты до дедлайна они выложили новую заявку, с результатом таким же, как у конкурента.

    Но и команда The Ensemble подготовила «двухходовку». Они ответили буквально двадцать минут спустя, то есть за четыре (!) минуты до дедлайна, результатом 10,10%, и у BellKor уже банально не оставалось времени.

    Таким образом, конкурс завершился победой команды The Ensemble. После проверки результатов они должны получить свой заслуженный миллион.
    Поддержать автора
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 54

      0
      Наверное у этих команд были специальные бригады, которые судорожно обновляли страницу с результатами последние 30 дней… :p
        +5
        может у них даже такая кнопка была:

        i021.radikal.ru/0907/15/9be79ca0544b.jpg
          +3
          перезалил на другой хостинг: habrahabr.ru/i/comments/bar/refresh.gif
            +1
            спасибо спасибо! но поздно, хабр уже не тот! лого посередине, управление профилем слева… ну вы поняли :)
        +5
        рукоплескаю! а такие результаты, потому что не заходили на хабру и на башорг каждые 10 минут :)
        • НЛО прилетело и опубликовало эту надпись здесь
          • НЛО прилетело и опубликовало эту надпись здесь
          0
          отодвинули бы дедлайн хотябы на год раньше, получили бы результат на год раньше. я не думаю что программисты только этим проектом всё это время и занимались :)
            +1
            дедлайн был ограничен не 3 годами. а формально — 1 месяцем. так что стимул сделать побыстрее был у всех.
            –2
            Наверное все-таки «The Ensemle»?
              –1
              Вспомнилось «последний байт», «минимизация логических функций»…
              А какие ограничения были на модель? Теоретически можно было вогнать все исходные данные в модель. Конечно, это не честно, но это можно было замаскировать. Бывает, сам исследователь этого не замечает.
                0
                Если бы еще знать все исходные данные ;)
                  0
                  а вроде бы после регистрации их можно скачать файлом в 600 MB примерно )
                    +1
                    Скорее всего, скачать можно обучающую выборку Уобуч=Ф(Хобуч) и только Хтест. Утест неизвестен.
                      0
                      хтест тоже нельзя
                        0
                        В статье явно сказано ОПУБЛИКОВАН НАБОР ДЛЯ ПРОВЕРКИ
                        > Для проверки результатов был опубликован набор из пар пользователей и фильмов,
                        > а алгоритм должен был максимально точно предсказать выставленные оценки,
                        > при этом подсчитывалась средняя ошибка
                        … подсчитывалась у заказчика, где были оценки.
                        Теоретически, обратный инжиниринг позволяет восстановить оценки, но подозреваю, количество допустимых расчетов RMSE (у заказчика!!!), скорее всего, недостаточно для этого.

                          0
                          да, действительно я перепутал
                          на самом деле Хтест тоже разбивался на 2 части (неизвестным образом) и демонстрировался только RMSE по первой из них, а для оценки выигрыша использовался RMSE по второй из них
                          так что, не зная этого разбиения, нельзя восстановить оценки
                    +1
                    Перечитал внимательно. Вы правы, была опубликована лишь проекция тестовой выборки.
                  +6
                  Вот не повезло второй команде. Упустить миллион за 20 минут из за 0,0001 балла.
                    0
                    Я думаю эти ребята а) неплохо пропиарились б) получили выгодные предложения от работодателей или уже работают в весьма сладких местах. Не зря нетфликс просто не наняло с десяток человек в R&D департамент, а стала устраивать такой конкурс дабы привлечь специалистов со всего мира, многие из которых не согласились бы идти работать на нетфликс даже на хороших условиях.
                      0
                      да я понимаю что вторая команда тоже в выигрише (отчасти), но все таки обидно им наверное
                      • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          не думал что видеопрокат такой доходный бизнес чтобы раскидываться такими деньгами
                          • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        Вторая команда лидировала в конкурсе практически с самого его начала. Она выиграла оба приза за прогресс (по $50.000), её состав значительно увеличился с первого года. Да и работают они уже в престижных местах — Yahoo! Research, AT&T Research.
                      0
                      Хм… а каким образом конкурс длился так долго, если только спустя 3 года смогли превысить планку в 10%? Я был твердо убежден, что для выигрыша должно пройти не более 30 дней с момента публикации лучшего алгоритма, который минимум на 10 быстрее.
                        +4
                        Ничего не понял. Да, 30 дней с момента публикации алгоритма, который на 10% лучше. Такой алгоритм опубликовали через 3 года от начала конкурса. Потому и так долго
                        +1
                        Я думаю, что у команд были «запасные» улучшения, но одна из команд проиграла тактически. В результате не совсем честное определение победителя.

                        Организаторам надо было разрешить публиковать ответ на ход соперника хотя бы в течении часа, а не устанавливать жесткий «дедлайн».
                          0
                          Поэтому в таких соревнованиях нельзя быть просто хорошим программистом.
                          –1
                          а известно что-то про алгоритм? вообще, они должны будут его выложить на всеобщее обозрение или смогут подло зажать? :)
                            +2
                            им будет владеть netflix, очевидно же.
                              –1
                              ну это да
                              а нетфликс его выложит или зажмет? :)
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  0
                                  надеюсь, что хотя бы в общих чертах расскажут
                                    0
                                    По условиям конкурса — обязаны выложить описание алгоритма в публичный доступ. НО авторы имеют право запатентовать его, при условии передачи лицензии на право пользования патентом компании Netflix.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                        0
                                        Вот, нашел:

                                        Once an algorithm is verified by the judges and the license is granted, Netflix will award the appropriate Contest Prize to the winning Participant. The description of the algorithm, but not the source code, will be published on the Site along with the names of the team members who won the Prize.

                                        Так что почитаем скоро, что они там придумали :)
                                  0
                                  Если команда-победитель согласится.
                                    0
                                    а если не согласится, то и миллон не получит :)
                                –1
                                Интересно, влияют ли на что-то эти 0,0001 кроме приза? :)
                                  +1
                                  на владельца 1 млн долларов. мало? :)
                                    0
                                    я же и говорю, кроме приза

                                    в сфере применения
                                      0
                                      очевидно же, что это дает результаты работы алгоритма отличаются на 0,0001
                                      какой ответ вы хотели услышать на свой вопрос?
                                      0
                                      По-хорошему, нет. Потому что на этот несчастный 0,0001 RMSE ни один человек-пользователь рекомендательной системы не заметит.
                                +5
                                > Буквально в последние часы претенденты несколько раз менялись местами друг с другом!

                                По правилам Netflix команда не может сабмитить больше одного решения в сутки.

                                > Таким образом, конкурс завершился победой команды The Ensemle. После проверки результатов они должны получить свой заслуженный миллион.

                                Вот это еще неизвестно. В публичном Leaderboard команды сортируются не по RMSE на секретном test set, для того чтобы нельзя было «подгонять» решение. Сейчас на форуме Netflix Prize появляются сообщения о том, что победила скорее всего комманда BellKor's Pragmatic Chaos.

                                www.netflixprize.com/community/viewtopic.php?pid=9237#p9237
                                  +1
                                  Стоило начать с того, что программирование тут почти нипричем, т.к. команда BellKor — это команда математиков:

                                    0
                                    Team BellKor is made up of Bob Bell and Chris Volinsky, from the Statistics Research group in AT&T Labs, and Yehuda Koren, who recently left AT&T Labs for Yahoo! Research in Israel. Our team has won the first two $50,000 Progress Prizes awarded by Netflix as part of their $1 Million competition to improve their recommendation algorithm. Check out their current performance on the Netflix leaderboard, and watch this AT&T Tech Channel interview with researchers Bob Bell and Chris Volinsky.

                                    With the best score at the one year anniversary of the competition, they won the coveted Progress Prize. Netflix sent a cool commemorative plaque, although at a square meter in size, and weighing almost 200 pounds it is more like a monument!

                                    Я даже думал димпломную работу писать на тему разбора их алгоритма по прогрессу за 2008 год, но сроки маловаты вышли.

                                    В целом — там довольно много математики, программированием там толком не пахнет вообще.

                                    Кому интересно — может почитать www.research.att.com/~volinsky/netflix/Bellkor2008.pdf — тут много интересного есть :)
                                    0
                                    Жаль узнал о конкурсе только сейчас — файлы с тренировочным набором уже не дают скачать :(
                                    Может у кого-то ещё остались? Поделитесь плиз…

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое