Разъяснение путаницы между этими методами

Недавно, посмотрев курс рекомендательных систем Курса машинного обучения профессора Эндрю Нг, я почувствовал себя очень смущенным, не понимая, как работает матричная факторизация.

Иногда я знаю, что математика в машинном обучении очень непонятна. Лучше, если мы будем думать о нем как о черном ящике, но эта модель была очень «волшебной» по моим меркам.

В таких ситуациях я обычно пытаюсь найти в Google больше ссылок, чтобы лучше понять концепцию. На этот раз я запутался еще больше. В то время как профессор Нг назвал алгоритм матричной факторизацией (низко-факторной), я нашел в Интернете другую номенклатуру: разложение по сингулярным значениям.

Больше всего меня смутило то, что разложение по сингулярным значениям сильно отличалось от того, чему учил профессор Нг. Люди продолжали утверждать, что это одно и то же.

В этом тексте я обобщу свои выводы и попытаюсь прояснить некоторую путаницу, которую могут вызвать эти термины.

Рекомендательные системы

Рекомендательные системы (RS) - это просто автоматизированные способы порекомендовать что-то кому-то. Такие системы широко используются компаниями электронной коммерции, потоковыми сервисами и новостными веб-сайтами. Это помогает уменьшить трение пользователей, пытающихся найти то, что им нравится.

РС определенно не новинка: они появились как минимум с 1990 года. Фактически, часть недавнего ажиотажа в области машинного обучения можно объяснить интересом к RS. В 2006 году Netflix произвел фурор, когда они спонсировали конкурс на лучший RS для своих фильмов. Как мы вскоре увидим, это событие связано с последовавшей за этим путаницей с номенклатурой.

Матричное представление

Есть много способов порекомендовать кому-то фильм. Одна из стратегий, которая оказалась очень удачной, - рассматривать рейтинги фильмов как матрицу Users x Movies следующим образом:

В этой матрице вопросительные знаки представляют фильмы, которые пользователь не оценил. Стратегия состоит в том, чтобы как-то спрогнозировать эти рейтинги и рекомендовать пользователям фильмы, которые им, вероятно, понравятся.

Факторизация матрицы

Ребята, принявшие участие в конкурсе Netflix (в частности, Саймон Фанк), сделали действительно умное осознание того, что рейтинги пользователей - это не просто случайные догадки. Оценщики, вероятно, следуют некоторой логике, когда они сравнивают то, что им нравится в фильме (конкретная актриса или жанр), с тем, что им не нравится (длительная продолжительность или плохие шутки), а затем выставляют оценку.

Этот процесс можно представить линейной формулой следующего вида:

где xₘ - вектор-столбец со значениями характеристик фильма m, а θᵤ - другой вектор-столбец с весами, которые пользователь u дает каждой функции. У каждого пользователя свой набор весов, и каждый фильм имеет свой набор значений для своих характеристик.

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

Используя таблицу, которую я привел в качестве примера выше, в результате задачи оптимизации будет сгенерирована следующая новая матрица:

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

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

Чтобы было понятнее, мы можем отделить θ ' и x' и поместить их в их собственные матрицы (скажем, P и Q). Фактически это матричная факторизация, отсюда и название, используемое профессором Нг.

Факторизация матрицы - это в основном то, что сделал Фанк. Он занял третье место в конкурсе Netflix, привлекая много внимания (что является интересным случаем, когда третье место было более известным, чем победители). С тех пор его подход был воспроизведен и усовершенствован и до сих пор используется во многих приложениях.

Разложение по сингулярным значениям

Введите разложение по сингулярным значениям (SVD). SVD - это интересный способ разложить матрицу на три другие матрицы (A = UΣVᵀ). Способ выполнения SVD гарантирует, что эти 3 матрицы несут некоторые приятные математические свойства.

Есть много приложений для СВД. Одним из них является анализ главных компонентов (PCA), который просто сокращает набор данных измерения n до измерения k (k ‹n).

Я не буду подробно рассказывать о СВД, потому что сам не знаю. Дело в том, что это не то же самое, что мы сделали с матричной факторизацией. Самым большим доказательством является то, что SVD создает 3 матрицы, в то время как матричная факторизация Funk создает только 2.

Так почему же SVD продолжает появляться каждый раз, когда я ищу рекомендательные системы? Мне пришлось немного покопаться, но в конце концов я нашел несколько скрытых драгоценных камней. По данным Луиса Аргериха:

Алгоритмы матричной факторизации, используемые для рекомендательных систем, пытаются найти две матрицы: P, Q, например P * Q, соответствует ИЗВЕСТНЫМ значениям матрицы полезности.

Этот принцип появился в знаменитой статье SVD ++ «Факторизация встречает соседство», в которой, к сожалению, использовалось название «SVD ++» для алгоритма, который абсолютно не связан с SVD.

Для протокола, я думаю, что Функ, а не авторы SVD ++, первым предложил упомянутую матричную факторизацию для рекомендательных систем. Фактически, SVD ++, как следует из названия, является продолжением работы Фанка.

Ксавье Аматриан дает нам более широкую картину:

Начнем с того, что отметим, что метод, обычно называемый «SVD», который используется в контексте рекомендаций , строго говоря, не является математическим разложением по сингулярным значениям матрицы, а скорее приближенным способом вычисления низкоранговая аппроксимация матрицы за счет минимизации квадрата потерь ошибок. Более точный, хотя и более общий способ назвать это матричной факторизацией. Первоначальная версия этого подхода в контексте премии Netflix Prize была представлена ​​Саймоном Функом в его знаменитом блоге «Попробуйте это дома». Важно отметить, что подход «истинной SVD» действительно применялся к той же задаче несколько лет назад, но с не большим практическим успехом.

В Википедии также есть похожая информация, похороненная в статье Факторизация матриц (рекомендательные системы):

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

Обобщить:

1. SVD - это довольно сложный математический метод, который факторизует матрицы на основе трех новых матриц и имеет множество приложений, включая PCA и RS.

2. Саймон Функ применил очень умную стратегию в конкурсе Netflix в 2006 году, разложив матрицу на две другие и используя градиентный спуск, чтобы найти оптимальные значения характеристик и весов. Это не СВД, но он все равно использовал этот термин для описания своей техники.

3. Более подходящий термин для обозначения того, что сделал Funk, - это матричная факторизация.

4. Из-за хороших результатов и последовавшей известности люди до сих пор называют эту технику СВД, потому что, ну, автор так назвал ее.

Надеюсь, это поможет немного прояснить ситуацию.