Рекомендательные системы: SVD, часть I

    Продолжаем разговор о рекомендательных системах. В прошлый раз мы сделали первую попытку определить схожесть между пользователями и схожесть между продуктами. Сегодня мы подойдём к той же задаче с другой стороны – попытаемся обучить факторы, характеризующие пользователей и продукты. Если Васе из предыдущего поста нравятся фильмы о тракторах и не нравятся фильмы о поросятах, а Петру – наоборот, было бы просто замечательно научиться понимать, какие фильмы «о поросятах», и рекомендовать их Петру, а какие фильмы – «о тракторах», и рекомендовать их Васе.

    image

    Напоминаю ещё раз (и, видимо, буду напоминать до конца времён), что у нас есть матрица, состоящая из рейтингов (лайков, фактов покупки и т.п.), которые пользователи (строки матрицы) присвоили продуктам (столбцы матрицы). Давайте присмотримся к матрице image, в которой записаны известные нам рейтинги. Как правило, один пользователь не сможет оценить значительную долю продуктов, и вряд ли будет много продуктов, которые готова оценить значительная доля пользователей. Это значит, что матрица R разреженная (sparse); нельзя ли этим как-нибудь воспользоваться?

    Главным инструментом для нас станет так называемое сингулярное разложение матрицы R:
    image
    Сингулярное разложение – это достаточно простой, но очень мощный инструмент. Собственно, это один из главных с практической точки зрения результатов линейной алгебры, и результат уже весьма не новый (свойства SVD были изучены самое позднее в 1930-х годах), – и тем удивительнее бывает, когда университетские курсы линейной алгебры, довольно подробные в каких-то других аспектах, совершенно обходят SVD стороной.

    Если у вас есть три минуты, можете насладиться ярким образчиком математического юмора; юмор, конечно, математический, так что не то чтобы смешно, но суть изложена доходчиво, а музыка наверняка понравится любителям… хм, на хабре, наверное, лучше будет сказать, что понравится любителям Fallout:


    На случай, если трёх минут всё-таки не нашлось, я выделю главное для нас свойство: если R – матрица большого размера image, но малого ранга f (в частности, разреженные матрицы часто бывают малого ранга), её можно разложить в произведение матрицы image и матрицы image, тем самым резко сократив число параметров, c NM до (N+M)f (чтобы понять, что это большой прогресс, представьте, что, как это обычно бывает на практике, N и M измеряются сотнями тысяч и миллионами, а f меньше десятка).

    SVD очень широко употребляется в машинном обучении; фактически, если вы хотите что-то чем-то приблизить, не исключено, что вам где-то по дороге встретится SVD. Классический пример применения SVD – шумоподавление, например, в изображениях. Рассмотрим (чёрно-белое) изображение как матрицу X размера image, элементы которой – интенсивности каждого пикселя. Теперь попробуем выбрать f столбцов пикселей из изображения, счесть их «репрезентативными» и представить каждый из оставшихся столбцов в виде линейной комбинации этих. Я не буду сейчас углубляться в математику, но в результате, когда вы найдёте оптимальные представления каждого столбца, получится, что вы представили исходную матрицу в виде произведения image матриц размера image и image, то есть как раз приблизили матрицу X матрицей малого ранга f.

    Основное же свойство SVD – в том, что SVD даёт оптимальное такое приближение, если в матрице D просто оставить ровно f первых диагональных элементов, а остальные занулить:
    image
    В диагональной матрице D, которая в середине сингулярного разложения, элементы упорядочены по размеру: image, так что обнулить последние элементы – это значит обнулить наименьшие элементы.

    Если хорошо подобрать f, то в результате изображение и в весе потеряет, и шума на нём станет меньше. А f в данном случае можно подбирать, исходя из размера сингулярных значений матрицы, т.е. тех самых диагональных элементов матрицы D: желательно отбрасывать как можно больше, но при этом как можно более маленьких таких элементов.

    Но мы отвлеклись. В случае рекомендательных систем получается, что мы представляем каждого пользователя вектором из f факторов image и представляем каждый продукт вектором из f факторов image, а потом, чтобы предсказать рейтинг пользователя i товару j, берём их скалярное произведение image. Можно сказать, что вектор факторов пользователя показывает, насколько пользователю нравится или не нравится тот или иной фактор, а вектор факторов продукта показывает, насколько тот или иной фактор в продукте выражен. Линейная же алгебра подсказывает нам, что для разреженной матрицы рейтингов такое разложение часто возможно и имеет содержательный смысл.

    Может оказаться, кстати, что некоторые факторы легко будет понять человеческим умом: для фильмов может выделиться что-нибудь в духе «комедия–драма», «доля action'а», «доля романтики» и т.п., а факторы пользователей, соответственно, будут показывать, насколько соответствующие характеристики фильма им по вкусу. Но может и не выделиться ничего содержательного – тут гарантий нет, формально мы просто жонглируем цифрами.

    В следующий раз мы превратим эту базовую идею – приблизить матрицу рейтингов матрицей малого ранга посредством SVD – в хорошо поставленную задачу оптимизации и научимся её решать.
    • +13
    • 40.1k
    • 5
    Surfingbird
    77.76
    Company
    Share post

    Comments 5

      –1
      отлично! молодцы, блин, вы замечательный мне кажется старап, даром, что идея уже была.
        0
        спасибо большое. идей рекомендательных систем вообще очень много) самое интересное это реализация
        +1
        А по каким метрикам оценивается качество рекомендательных систем?

        В одной из своих презентаций Роман Зыков приводил показатель доли заказов, сделанных на основе рекомендаций, а еще есть?
          +1
          Чего вы хотите добиться рекомендациями — то и меряете.

          В нашем случае нам интересно, чтобы пользователю рекомендованная ссылка понравилась, так что мы смотрим долю лайков.
            0
            Обычно – RMSE (root mean squared error). Если придётся к слову, мы обязательно поговорим об этом как-нибудь.

          Only users with full accounts can post comments. Log in, please.