Рекомендательные системы: оверфиттинг и регуляризация

    Постоянно падающая популярность предыдущих публикаций побуждает предпринимать поступки, помогающие популярность поддержать. Приметил – популярность первых публикаций порядочно превышает последующие; поэтому попробую перезагрузиться.

    На протяжении предыдущих серий мы тщательно рассмотрели метод SVD и даже довели его до программного кода; начиная с этого текста, я буду рассматривать более общие вещи. Вещи эти, конечно, всегда будут тесно связаны с рекомендательными системами, и я буду рассказывать о том, как они в рекомендательных системах возникают, но постараюсь делать упор на более общих концепциях машинного обучения. Сегодня – об оверфиттинге и регуляризации.



    Начну с классического, но от этого не менее показательного примера. Давайте откроем R (если кто не знает, R – это один из лучших в мире инструментов для всевозможной статистики, машинного обучения и вообще обработки данных; очень рекомендую) и сгенерируем себе какой-нибудь маленький простенький датасет. Я возьму простой кубический многочлен и добавлю к его точкам нормально распределённый шум.
    > x <- c(0:6) / 2
    > y_true <- -.5*x^3 + 2*x^2 + x – 3
    > err <- rnorm( 7, mean=0, sd=0.4 )
    > y <- y_true + err
    > y
    [1] -2.3824664 -2.1832300 -0.7187618  1.7105423  2.1338531  4.7356023  5.0291615
    


    Эти точки теперь можно нарисовать вместе с идеальной кривой.
    > curve(-.5*x^3 + 2*x^2 + x - 3, -1, 4, ylim=c(-5,6) )
    > points(x, y, pch=21, bg="red")
    

    Получится как на рисунке:


    А теперь давайте попробуем обучить многочлен по этим данным. Мы будем минимизировать сумму квадратов отклонений точек от многочлена (будем делать самую обычную классическую регрессию), то есть будем искать такой многочлен p(x), который минимизирует .

    Разумеется, в R это делается одной командой. Сначала обучим и нарисуем линейный многочлен:
    > m1 <- lm ( y ~ poly(x, 1, raw=TRUE) )
    > pol1 <- function(x) m1$coefficients[1] + m1$coefficients[2] * x
    > curve(pol1, col="green", lwd=2, add=TRUE)
    



    Потом многочлен второй степени:
    > m2 <- lm ( y ~ poly(x, 2, raw=TRUE) )
    > pol2 <- function(x) m2$coefficients[1] + m1$coefficients[2] * x + m1$coefficients[3] * (x^2)
    > curve(pol2, col="blue", lwd=2, add=TRUE)
    



    Многочлен третьей степени, как и ожидалось, уже вполне себе похож:


    Но что произойдёт, если увеличивать степень дальше? На практике ведь мы, скорее всего, не будем знать «истинной степени многочлена», т.е. истинной сложности модели. Может показаться, что мы будем, усложняя модель, всё лучше приближать имеющиеся точки, и результаты будут всё лучше и лучше, просто обучить модель будет всё сложнее и сложнее. Посмотрим, так ли это на самом деле.

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


    Начиная с шестой степени, мы видим уже несомненный epic fail нашего подхода. Ошибка, которую мы хотели минимизировать, теперь строго равна нулю – ведь через семь точек можно точно провести многочлен шестой степени! Но вот польза от получившейся модели тоже, пожалуй, строго равна нулю – многочлен теперь не только плохо экстраполирует за пределы имеющихся точек, но даже интерполирует между ними чрезвычайно странно, далеко убегая на локальные экстремумы там, где этого из точек трудно ожидать.


    Что же произошло? Произошло то, что в машинном обучении называется словом оверфиттинг (overfitting): мы взяли модель, в которой было слишком много параметров, и модель слишком хорошо обучилась по данным, а главное – предсказательная сила – от этого, наоборот, пострадала.

    Что же делать? Я в следующих сериях расскажу, как это может получиться более концептуально, а сейчас давайте просто примем на веру: оверфиттинг в данном случае проявляется в том, что в получающихся многочленах слишком большие коэффициенты. Например, вот многочлен третьей степени, который мы обучили:
    ,
    а вот – почувствуйте разницу – шестой степени:
    .

    Соответственно, и бороться с этим можно довольно естественным способом: нужно просто добавить в целевую функцию штраф, который бы наказывал модель за слишком большие коэффициенты:
    .

    Именно такой оверфиттинг сплошь и рядом происходил бы в SVD, если бы мы позволили ему происходить. Действительно, мы вводим на каждого пользователя и каждый продукт число свободных параметров, равное числу факторов (т.е. минимум несколько, а может быть, и несколько десятков). Поэтому SVD без регуляризации совершенно неприменимо – обучится, конечно, хорошо, но для предсказаний, скорее всего, будет практически бесполезно.

    Регуляризаторы в SVD работают точно так же, как в обычной регрессии – мы добавляем штраф, который тем больше, чем больше размеры коэффициентов; в одной из предыдущих серий я сразу с регуляризаторами и выписывал целевую функцию:

    Формулы градиентного подъёма приведены там же – за регуляризацию в них отвечает коэффициент λ.

    Однако пока это всё выглядит довольно загадочно – с какой стати вдруг большие коэффициенты хуже маленьких? В дальнейшем я буду рассказывать о том, как можно смотреть на этот вопрос с более концептуальной байесовской стороны.
    Surfingbird 59,46
    Компания
    Поделиться публикацией
    Похожие публикации
    Комментарии 17
    • 0
      Спасибо. Когда читал и пробовал коллаборативную фильтрацию, эта лямбда нигде не обьяснялась (достаточно понятно, чтобы я понял).
      Вообще, ваша серия постов — самое понятное практическое описание этих механизмов, что я встречал (а на русском так чуть ли не единственное). Потомки вас не забудут =)
      Скажите, а вы тот Сергей Николенко, которого я иногда вижу в ЧГК? Или однофамилец?
      • 0
        Эх, надо тогда как-то шире рекламировать, а то потомки не забудут потому, что не узнают никогда. :)

        Да, тот самый.
        • 0
          Шире рекламировать, я боюсь, не поможет. Скажем, в гугле ваши статьи и так уже на первых местах по тематическим словам, по которым люди наиболее вероятно будут такие статьи искать.

          Просто тема эта не настолько популярна пока. 99,9% читателей хабра с этой информацией просто нечего делать. Да, она интересная и хорошо описанная, но практического применения, тем более прямо сейчас, нет. Даже потрогать нечего (кроме предыдущей вашей статьи, но и там это требует усилий).

          Могу предложить 2 вещи:
          1. Сделайте общее оглавление у ваших статей, чтобы их проще было найти и прочитать вместе. Это было бы удобно.
          2. Постарайтесь найти тему, которая имела бы практическое применение для большего числа людей.

          У многих читателей хабра есть сайты/сервисы, над которыми они работают. Расскажите, как добавить коллаборативную фильтрацию на их проект. Это было бы очень интересно. А предыдущие ваши статьи помогли бы подробнее разобраться в механизмах и подтюнить решение при желании.

          На основе того, что вы описали, конечно, можно при некотором усилии написать систему рекомендаций для сайта, но пока что эти усилия слишком велики — преобразовывать сложные формулы в код мало кто умеет.

          Вот лично меня очень интересуют подходы к модификации вышеприведённых алгоритмов на случай большого количества данных, когда человеку нужно дать рекомендации, а сделать прогноз для всех имеющихся элементов невозможно из-за их количества — нужно как-то подбирать кандидатов, нужно повсюду бороться с квадратичной сложностью и т.п. Статей на эту тему мало (вероятно, из-за того, что тут много специфичного для каждой задачи).
          • 0
            Оглавление – это отличная мысль! Вы не знаете, на хабре можно сделать заглавный пост, который будет всегда висеть сверху?

            Про практическое применение не очень понял – то есть я вроде бы стараюсь, даже вот работающий код запостил. Понятно, конечно, что я не могу для каких-то неизвестных мне проектов конкретные решения предлагать, а могу только объяснять общую механику происходящего. Но вот код, который был в прошлый раз, действительно лёг в основу одной из стратегий, которые реально работают в surfingbird (там, конечно, в production код слегка посложнее :), но по сути именно такой).

            На случай большого количества данных – вообще-то это и есть алгоритмы для большого количества данных. :) Вряд ли у вас база рейтингов больше, чем у Netflix и Amazon. Разложение матриц – алгоритм как раз для того, чтобы от O(M*N) перейти к O(M+N); про скорость сходимости так сразу с ходу не скажу, надо посмотреть, но в любом случае вероятностное разложение матриц хорошо параллелизуется – когда-нибудь обязательно расскажу о параллельной реализации на GraphLab. Так что да, именно эти алгоритмы и работают для больших массивов данных, и именно их и надо реализовывать в первую очередь.
            • 0
              Я имел в виду более практическое применение, буквально рецепты вида:
              1. Экспортируем из вашей базы данных csv в формате <id пользователя>,<оценка>
              2. Берём такой-то скрипт/программу/библиотеку, скармливаем ему данные
              3. Получившийся результат загружаем в вашу БД
              4. При отображении элемента на вашем сайте делаем запрос вида «SELECT ...», чтобы получить список похожих элементов и вывести их рядом.
              Такого рода статья, я думаю, была бы популярнее.

              Насчёт многоданных. Да, я понимаю, что на большом количестве данных только такие алгоритмы и будут работать. Но при практической реализации возникают проблемы.
              * Длительность расчёта факторов пропорциональна количеству оценок, т.е. будет расти линейно с ростом их количества. А ресурсы не бесконечны, а значит нужно каким-то образом приближать её к O(1). Как?
              * Расчёт качественных факторов длительный процесс. Что делать с пользователями, которые только пришли, и которым уже нужно давать рекомендации, а пересчёт факторов запланирован на завтра?
              * Мы расчитали факторы и нужно найти 10 рекомендаций для пользователя. А элементов в базе 10 миллионов. Как найти 10 лучших из них, не расчитывая прогноз для всех
              *… таких проблем возникает много, и без хорошего понимания математических методов и одновременно программирования их качественно решать сложно.
              • 0
                Да, ну так ведь предыдущий скрипт так и делает: кушает данные в формате
                <id пользователя>; <id продукта>; <оценка>
                и выдаёт ответ в виде
                <id пользователя>; <список факторов>
                и
                <id продукта>; <список факторов>
                Чтобы затем сделать рекомендацию, нужно взять вектор факторов пользователя и умножить его скалярно на вектор факторов продукта (и даже это, кажется, в скрипте тоже было). Обращение к базам данных, каюсь, не вписывал, но это уж совсем не по теме.

                Спасибо за отличные вопросы! На них, безусловно, ответы уже существуют. :) Например, особенно интересный вопрос – про «только что пришедших», особенно если его чуть обобщить: пользователь пришёл на сайт, сделал двадцать лайков и хочет, чтобы что-нибудь тут же изменилось, а пересчёт запланирован на завтра. Это так называемые онлайн-рекомендации, алгоритмы есть, постараюсь про них рассказать. Но вообще я планировал переходить к частностям чуть позже, когда разберусь с концептуальными вопросами – уже шесть статей было, а я ещё, чёрт возьми, про теорему Байеса не рассказал. :)
                • 0
                  Чтобы применить ваш скрипт из предыдущего поста для реального проекта — нужно приложить много усилий, чтобы понять его и использовать в своём проекте, даже в самом простом случае. Плюс вы ничего не писали насчёт того, что «возьмите это и используйте у себя». А значит никто этого делать и не будет.
                  Я этим не хочу сказать, что статья бесполезна. Для меня она была полезна, чтобы как минимум сравнить ваш скрипт с тем, что я писал, основываясь на одной статье, чтобы лучше понять как это работает. Но полученную из неё информацию для большинства всё-таки сложно применить на практике, а значит она скоро забудется, а значит статья автоматически квалифицируется мозгом как «неинтересная».

                  Насчёт моих вопросов. Если вы напишите про них статьи — они будут очень интересны для меня, но, боюсь, для большинства это будет ещё более специализированные статьи, чем ваши последние, что не добавит им популярности. Вы ведь заметили, что оценка ваших статей обратно пропорциональна широте описываемоей темы? Про рекомендации в целом — статьи оценены выше, про более узкие темы — ниже.
                  • 0
                    Как следует из предисловия к этому тексту, заметил. :)
                    И именно поэтому собираюсь писать более общо и концептуально.
              • 0
                Заглавный пост, кажется, нельзя сделать. Не тот формат сайта.
              • 0
                P.S. Кстати, я пока поддерживал оглавление на своей страничке:
                logic.pdmi.ras.ru/~sergey/index.php?page=popular
                хотя это, конечно, тоже трудно назвать хорошей рекламой. :)
          • 0
            Сергей, спасибо, статьи очень в тему и невероятно вовремя!
            И да, хорошо бы все это масштабировать на «очень дофига данных». Ведь насколько я понимаю, рекомендательные системы наиболее часто работают именно с большими коллекциями.
            • 0
              Я пока могу просто ссылку дать: graphlab.org
              Там есть прямо примеры кода сильно параллельных рекомендательных систем.
              Подробно пока руки не дошли описывать, но когда-нибудь текст о рекомендациях на графлабе обязательно будет.
            • 0
              Большое спасибо за подробное описание. В русскоязычном сегменте сети информации по коллаборативной фильтрации очень мало, а ведь она применима едва ли не для каждого второго веб-сервиса. Для одних это «секрет фирмы», для остальных «тормоз» в развитии. Так что ещё раз спасибо.

              Два вопроса:
              Вы изучали опубликованные алгоритмы победителей Netflix Prize?
              Какой у вас средний процент ошибки предсказаний или СКО на SurfingBird (если не секрет)?

              • 0
                (1) Изучали, конечно. Это отдельная интересная тема – как совместить несколько алгоритмов.
                (2) Боюсь, секрет. :)
                • 0
                  Рад, что интересно!

                  (1) Конечно, изучали. Это отдельный интересный вопрос: главный урок Netflix Prize — в том, как объединять кучу разных моделей в одну рекомендацию; когда-нибудь и до него дойдём.
                  (2) Боюсь, секрет. :)
                • 0
                  Отличные статьи, Сергей! Продолжайте писать, пожалуйста.

                  Очень ясно все — даже спросить нечего, особенно видео про SVD порадовало.

                  За рейтингом не гонитесь, долгосрочный эффект есть — вы уже для широких масс персона #1 в отрасли!
                  • 0
                    Спасибо, Сергей, очень наглядно все.

                    Но все-таки, откуда лямбду-то брать? Смысл ее понятен. А вот численное значение, например, для скрипта из предыдущей статьи какое должно быть?

                    И, кстати, у того скрипта какая лицензия? Ну, если его «взять и использовать у себя»?

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

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