Как я могу использовать SVD в совместной фильтрации?

30

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

Предположим, что мой социальный график соответствует Instagram, и мне было поручено рекомендовать пользователей в сервисе, основываясь только на социальном графике. Сначала я построю матрицу смежности , возьму SVD, , выберу первые собственных значений, а затем что?A A = U s V k(m×m)Aзнак равноUsВК

Предположительно я бы создал новый набор матриц: тогда что делать?

UNевес~м×КsNевес~К×КВNевес~К×м

Я посмотрел в Интернете, и большинство ссылок сосредоточены на расчете SVD, но никто не говорит вам, что с этим делать. Так что я должен делать?

Вишал
источник
1
Это может ответить на ваш вопрос: datascience.stackexchange.com/a/16523
Avli

Ответы:

7

Однако: с чистым ванильным SVD могут возникнуть проблемы с воссозданием исходной матрицы, не говоря уже о прогнозировании значений для пропущенных элементов. Полезное эмпирическое правило в этой области - вычисление среднего рейтинга по каждому фильму и вычитание этого среднего для каждой комбинации пользователь / фильм, то есть вычитание смещения фильма у каждого пользователя. Затем рекомендуется запустить SVD, и, конечно, вам придется где-то записывать эти значения смещения, чтобы воссоздать рейтинги или прогнозировать для неизвестных значений. Я прочитал статью Саймона Фанка о SVD для рекомендаций - он изобрел постепенный подход SVD во время соревнования Netflix.

http://sifter.org/~simon/journal/20061211.html

Я предполагаю, что унизительная матрица A до SVD имеет смысл, так как PCA близкого родственника SVD также работает аналогичным образом. Что касается инкрементальных вычислений, Функ сказал мне, что, если вы не унизите, первое направление градиента доминирует над остальными вычислениями. Я видел это не понаслышке, в принципе без унизительных вещей ничего не получается.

BBDynSys
источник
24

Я хотел бы предложить особое мнение:

Недостающие края как недостающие значения

В проблеме совместной фильтрации несуществующие соединения (пользователь не оценил элемент , человек не имеет друга ) обычно обрабатываются как пропущенные значения, которые должны быть предсказаны, а не как нули. То есть, если пользователь не оценил пункт , мы хотим , чтобы догадаться , что он мог бы оценить его , если бы он был оценил его. Если человек не подружился с , мы хотим догадаться, насколько вероятно, что он захочет подружиться с ним. Рекомендации основаны на восстановленных значениях.J х у я J х уяJИксYяJИксY

Когда вы берете SVD социального графа (например, подключаете его svd()), вы в основном вменяете нули во всех этих пропущенных местах. То, что это проблематично, более очевидно в настройке пользовательского рейтинга элементов для совместной фильтрации. Если бы у меня был способ надежно заполнить пропущенные записи, мне бы вообще не пришлось использовать SVD. Я просто дал бы рекомендации, основанные на заполненных записях. Если у меня нет способа сделать это, тогда я не должен заполнять их, прежде чем я сделаю SVD. *

СВД с отсутствующими ценностями

Конечно, svd()функция не знает, как справиться с пропущенными значениями. Итак, что именно ты должен делать? Ну, есть способ переосмыслить проблему как

«Найти матрицу ранга ближайшую к исходной матрице»К

Это действительно проблема, которую вы пытаетесь решить, и которую вы не собираетесь использовать svd()для ее решения. Способ, который сработал для меня (по призовым данным Netflix), заключался в следующем:

  • Попробуйте добавить записи в простую модель, например, . Это на самом деле делает хорошую работу.Икс^я,Jзнак равноμ+αя+βJ

  • Назначают каждому пользователю с -векторных и каждый пункт -векторных . (В вашем случае каждый человек получает правый и левый векторы). В конечном итоге вы будете предсказывать невязки как точечные произведения:К U я J K v J K Σ U я м v J мяКUяJКvJКΣUямvJм

  • Используйте некоторый алгоритм, чтобы найти векторы, которые минимизируют расстояние до исходной матрицы. Например, используйте эту бумагу

Удачи!

*: То, что рекомендует Tenali, это в основном ближайшие соседи. Вы пытаетесь найти пользователей, которые похожи, и давать рекомендации на этот счет. К сожалению, проблема разреженности (~ 99% матрицы пропускает значения) затрудняет поиск ближайших соседей, используя косинусное расстояние или подобие jaccard или что-то еще. Поэтому он рекомендует использовать SVD матрицы (с вмененными нулями при пропущенных значениях), чтобы сначала сжать пользователей в меньшем пространстве признаков, а затем провести сравнение там. Работать с SVD-ближайшими соседями - это хорошо, но я все равно рекомендую делать SVD правильным образом (я имею в виду ... мой путь). Не нужно делать бессмысленные вменения стоимости!

Пупси Джо Пит
источник
Это был ответ, который я искал и хотел услышать :) Большое спасибо!
Вишал
Как ни странно, вопрос задавался: «Я смотрел в Интернете, и большинство ссылок фокусируется на расчете SVD, но никто не говорит вам, что с ним делать. Так что мне делать?» или в этом отношении заголовок говорит: «Как я могу использовать SVD в совместной фильтрации?»
TenaliRaman
Да, и мой ответ суммировал, как я использую это в совместной фильтрации.
Stumpy Джо Пит
1
+1, насколько я понимаю, вы рассчитываете не матрицу низкого ранга с использованием SVD, а итеративный метод минимизации квадрата ошибки, верно? Однако, если я хочу использовать SVD, я должен заполнить пропущенные записи некоторыми значениями, прежде чем выполнять факторизацию матрицы, верно?
авокадо
1
Поэтому, когда они говорят, что используют svd, они не имели в виду использовать для матричной факторизации? Причина, по которой они говорят svd, заключается в том, что результат или основная идея этого итеративного решения напоминает svd? svd()
авокадо
14

Причина, по которой никто не говорит вам, что с этим делать, заключается в том, что если вы знаете, что делает SVD, то совершенно очевидно, что с ним делать :-).

Поскольку ваши строки и столбцы совпадают, я объясню это с помощью другой матрицы A. Пусть матрица A будет такой, что строки - это пользователи, а столбцы - это элементы, которые ему нравятся. Обратите внимание, что эта матрица не обязательно должна быть симметричной, но в вашем случае, я думаю, она оказывается симметричной. Один из способов думать о SVD заключается в следующем: SVD находит скрытое пространство объектов, где пользователи и элементы, которые им нравятся, имеют векторы функций, которые тесно выровнены.

Таким образом, когда мы вычисляем , матрица представляет векторы объектов, соответствующие пользователям в скрытом пространстве признаков, а матрица представляет векторы объектов, соответствующие элементам в пространстве скрытых объектов.U VAзнак равноU×s×ВUВ

Теперь, если я дам вам два вектора из одного и того же пространства признаков и попрошу вас выяснить, похожи ли они, какова простейшая вещь, о которой вы можете подумать для достижения этой цели? Скалярное произведение.

жяJяUJ

TenaliRaman
источник
Два вопроса: 1) Заполняете ли вы пропущенные значения нулем (элемент j не проверен пользователем i) перед запуском SVD? 2) Как вы рассчитываете, если новому пользователю понравится элемент j?
B_Miner
1
@B_Miner Привет, извините за задержку ответа. Ответы: 1) Ну, да, мы обычно заполняем пропущенные значения нулями перед запуском SVD. Однако я обычно рекомендую заполнять его ненулевым рейтингом - например, вы можете заполнить пропущенные значения средним рейтингом, который пользователь дал до сих пор. 2) Подход на основе SVD предназначен только для известных пользователей и известных предметов. Он не может обрабатывать новых пользователей или новые элементы. И как это может случиться, если придет новый пользователь, мы ничего не знаем о нем в этой структуре, чтобы предсказать.
TenaliRaman
1
@B_Miner Если вы хотите работать с новыми пользователями / элементами, мы должны предположить, что у нас есть доступ к некоторым функциям пользователя и элементам. Затем вы можете использовать более сложную модель, такую ​​как PDLF (модель прогнозирующего дискретного скрытого фактора). Это позволит вам обрабатывать новых пользователей / элементы, потому что он работает с известным пространством функций.
TenaliRaman
@TenaliRaman Не уверен, что вы увидите это, но здесь идет. Поэтому я использую тематические модели (LDA) для создания функций для пользователей (буквально пользователей) на основе документов, которые они прочитали. Я просто усредняю ​​векторы темы, чтобы получить «вектор темы пользователя». Я хочу сделать что-то подобное с SVD (или, возможно, ALS). Допустим, я вычисляю SVD с использованием данных известных пользовательских элементов, а затем у меня появляются новые пользователи, которые «посещают» несколько известных элементов. В этом случае векторы элементов известны, но векторы пользователей неизвестны. Могу ли я использовать векторы элементов для вычисления вектора пользователя или мне нужно снова вычислять SVD, используя все данные?
thecity2
отличный ответ тенали. очень полезно для понимания концепции
Нихал
3

Это попытка ответить на вопрос «как» для тех, кто хочет практически реализовать рекомендации с разреженным SVD или проверить исходный код на предмет деталей. Вы можете использовать готовое программное обеспечение FOSS для моделирования SVD. Так , например, vowpal wabbit, libFM, или redsvd.

vowpal wabbitимеет 3 реализации "SVD-подобных" алгоритмов (каждый выбирается одним из 3 параметров командной строки). Строго говоря, их следует называть «приближенной, итеративной, факторизацией матрицы», а не чистой «классической» SVD, но они тесно связаны с SVD. Вы можете думать о них как об очень эффективной в вычислительном отношении приближенной SVD-факторизации разреженного (в основном нули) матрица.

Вот полный, рабочий рецепт для выполнения рекомендаций по фильму в стиле Netflix с vowpal wabbitего --lrqопцией «квадратичного ранга низкого ранга» ( ), которая, кажется, работает лучше всего для меня:

Файл формата набора данных ratings.vw(каждая оценка в одной строке по пользователю и фильму):

5 |user 1 |movie 37
3 |user 2 |movie 1019
4 |user 1 |movie 25
1 |user 3 |movie 238
...

Где 1-е число - это рейтинг (от 1 до 5 звезд), за которым следует идентификатор пользователя, который оценил, и идентификатор фильма, который был оценен.

Тестовые данные в том же формате, но могут (необязательно) опустить столбец оценок:

 |user 1 |movie 234
 |user 12 |movie 1019
...

необязательно, потому что для оценки / проверки прогнозов нам нужны рейтинги для сравнения прогнозов. Если мы опускаем рейтинги, vowpal wabbitвсе равно будем прогнозировать рейтинги, но не сможем оценить ошибку прогноза (прогнозные значения против фактических значений в данных).

Для обучения мы просим vowpal wabbitнайти набор Nскрытых факторов взаимодействия между пользователями и фильмами, которые им нравятся (или не нравятся). Вы можете думать об этом, как о поиске общих тем, где похожие пользователи оценивают подмножество фильмов подобным образом, и об использовании этих общих тем, чтобы предсказать, как пользователь оценит фильм, который он еще не оценил.

vw Параметры и аргументы, которые мы должны использовать:

  • --lrq <x><y><N> находит «квадратичные» ранговые факторы низкого ранга.
  • <x><y>: "um" означает пересечение пространств имен u [sers] и m [ovie] в наборе данных. Обратите внимание, что только 1-я буква в каждом пространстве имен используется с --lrqопцией.
  • <N>: N=14ниже приведено количество скрытых факторов, которые мы хотим найти
  • -f model_filename: напишите окончательную модель в model_filename

Таким образом, простая команда полного обучения будет:

    vw --lrq um14 -d ratings.vw -f ratings.model

Получив ratings.modelфайл модели, мы можем использовать его для прогнозирования дополнительных рейтингов для нового набора данных more_ratings.vw:

    vw -i ratings.model -d more_ratings.vw -p more_ratings.predicted

Прогнозы будут записаны в файл more_ratings.predicted.

Используя demo/movielensв vowpalwabbitисходном дереве, я получаю ~ 0,693 MAE (средняя абсолютная ошибка) после обучения 1 миллиону пользователей / рейтингов фильмов ml-1m.ratings.train.vwс 14 скрытыми факторами (это означает, что средняя матрица SVD представляет собой матрицу 14х14 строк x столбцов) и тестирование на независимой тест-набор ml-1m.ratings.test.vw. Насколько хорошо 0,69 MAE? Для полного диапазона возможных прогнозов, включая случай без оценки (0) [от 0 до 5], ошибка 0,69 составляет ~ 13,8% (0,69 / 5,0) от полного диапазона, то есть точность около 86,2% (1 - 0,138).

Вы можете найти примеры и полную демонстрацию для подобного набора данных (movielens) с документацией в vowpal wabbitдереве исходников на github:

Заметки:

  • movielensДемо использует несколько вариантов я опущенные (для простоты) из моего примера: в частности --loss_function quantile, --adaptiveи--invariant
  • --lrqРеализация в vwгораздо быстрее , чем --rank, в частности , при хранении и загрузке моделей.

Кредиты:

  • --rank опция vw была реализована Джейком Хофманом
  • --lrq Опция vw (с необязательным выпадением) была реализована Полом Минеро
  • vowpal wabbit (он же vw) - детище мозга Джона Лэнгфорда
arielf
источник
1

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

Подробности SVDи SVD++алгоритмы для рекомендательной системы можно найти в разделах 5.3.1и 5.3.2в книге Francesco Ricci, Lior Rokach, Bracha Shapira, and Paul B. Kantor. Recommender Systems Handbook. 1st edition, 2010.

В Python есть хорошо известный пакет, в котором реализованы эти алгоритмы surprise. В своей документации они также упоминают детали этих алгоритмов.

lenhhoxung
источник