Введение
Допустим, мы работаем в сервисе рекомендаций фильмов и перед нами стоит задача подобрать для каждого пользователя набор наиболее релевантных фильмов. Пользователь может разными способами провзаимодействовать с фильмом: посмотреть его, оставить отзыв, поставить оценку (например, от 1 до 5).
В этом параграфе мы будем строить рекомендации на основе матрицы оценок user-item. Её строки соответствуют объектам, а столбцы – пользователям. На -й позиции матрицы мы ставим либо пропуск, либо оценку, выставленную -м объекту -му пользователем. Разумеется, не все оценки нам известны: вряд ли каждый пользователь имел возможность ознакомиться с каждым объектом. В процессе решения задачи мы будем пытаться восстановить оценки на местах пропусков. Сделав это, мы сможем, например, порекомендовать пользователю те объекты, которые он ещё не смотрел, но предсказанная оценка которых для этого пользователя максимальна.
Все типы взаимодействия пользователей с объектами мы можем рассматривать как пользовательский фидбек. Обычно различают явный (explicit) и неявный (implicit) виды фидбека. Фидбек называется явным, если он отражает степень интереса пользователя к объекту. Например, к этому типу относят рейтинги, лайки и дизлайки. Такого фидбека обычно мало, он поступает только от тех пользователей, которые соглашаются нам его дать.
Обычно гораздо больше информации имеется о неявных предпочтениях – просмотры, клики, добавление в закладки. Но если пользователь, например, посмотрел фильм, мы ещё не можем сделать вывод, что он ему понравился. Мы можем лишь утверждать, что до просмотра этот фильм казался ему достаточно интересным. Поэтому обычно неявная обратная связь более шумная, чем явная.
Для начала научимся работать с явным фидбеком.
Связь с задачей матричной факторизации
Вернёмся к задаче восстановления матрицы оценок и предположим, что каждый пользователь и объект можно закодировать набором из скрытых признаков, а оценка -го объекта -м пользователем равна скалярному произведению соответствующих векторов скрытых представлений и . Тогда если бы наша матрица оценок была заполнена полностью, её можно было бы представить в виде произведений двух матриц и , составленных по столбцам из скрытых представлений пользователей и объектов:
Правда, в таком случае нам бы и не требовалось ничего решать: мы могли бы просто рекомендовать пользователю объекты с самыми высокими оценками в соответствующей строке. Но суровая реальность такова, что зачастую матрица оценок сильно разрежена. Мы можем поступить следующим образом: восстановить латентные векторы для пользователей и объектов по имеющемуся набору оценок, после чего предсказать оценки для всех отсутствующих позиций. В параграфе, посвящённом матричной факторизации, мы уже обсуждали способы решения данной задачи с помощью SVD и стохастического градиентного спуска. У SVD есть существенные недостатки: из-за большого количества пропусков в матрице полученное решение будет слишком шумным, а кроме того, его придется каждый раз рассчитывать заново при добавлении новых пользователей или объектов. Градиентный спуск не имеет данных проблем, но тоже не очень практичен. В этом параграфе мы рассмотрим более эффективный алгоритм, называемый Alternating Least Squares (ALS).
Постановка задачи
Пусть, как и раньше, – скрытые представления пользователей и объектов соответственно размерности . Запишем эти векторы по строкам в матрицы и размера и соответственно, где – количество пользователей, а – количество объектов.
Обозначим через множество таких пар пользователей и объектов, для которых имеются явно проставленные оценки.
Предсказывать рейтинги мы будем как скалярное произведение скрытых представлений:
В результате мы приходим к следующей задаче оптимизации. Мы хотим научиться как можно лучше приближать известные рейтинги:
Добавив регуляризацию получаем следующую функцию потерь:
Alternating Least Squares (ALS)
Оптимальные параметры можно найти с помощью хорошо знакомого нам градиентного спуска, но есть более быстрые и надёжные способы. Если мысленно заморозить параметры, соответствующие латентным факторам пользователей, задача оптимизации латентных представлений объектов сведётся к задаче наименьших квадратов, для которой мы знаем точное решение.
Итоговый процесс оптимизации функции потерь будет иметь следующий вид.
В цикле до сходимости:
- Фиксируем матрицу (скрытые представления пользователей);
- Решаем задачу L2-регуляризованной регрессии для каждого товара и находим оптимальную матрицу ;
- Фиксируем матрицу (скрытые представления объектов);
- Решаем задачу L2-регуляризованной регрессии для каждого пользователя и находим оптимальную матрицу ;
Решение, получаемое путём попеременного вычисления точных аналитических решений, обычно точнее тех, что получаются с помощью наивного градиентного спуска. Более того, данное решение имеет эффективную реализацию, позволяющую использовать преимущества параллельных вычислений.
Для лучшего понимания распишем каждый шаг данного алгоритма оптимизации:
ALS - шаг по (одному) :
Раскроем квадратичный член:
В первой сумме константы, они уходят. Из второй и третьей возьмём только те слагаемые, в которых участвует . Из четвёртой остается только член с , так как все независимы. Последняя сумма пропадает, так как и независимы:
В первой сумме индекс фиксирован, поэтому можно вынести за знак суммы:
Объединим второй и третий члены формулы, вынесем умножение на за скобки:
Теперь воспользуемся тем, что
и выпишем ответ:
Таким образом, мы получили аналитическое выражение для вычисления каждого на шаге алгоритма. Отметим, что каждый вектор мы можем вычислить независимо от других . Данное наблюдение позволяет нам использовать всю мощь параллельных вычислений для эффективного решения оптимизационной задачи. Распределив данные так, что на каждой вычислительной машине хранятся все для некоторого подмножества , на одной итерации алгоритма мы можем параллельно вычислить все . На следующей итерации аналогичным образом вычисляем все .
IALS (Implicit ALS)
Раньше мы работали с матрицей как с матрицей рейтингов, явно проставленных пользователем. Как мы говорили выше, такого фидбека обычно довольно мало, а куда больше неявного фидбека. При этом количество данных может быть критичным при работе с такими разреженными структурами, как матрицы рейтингов, поэтому хочется научиться работать и с неявным фидбеком тоже.
Неявным фидбеком является в том числе и факт взаимодействия, поэтому мы можем заполнить всю матрицу user-item целиком: на тех позициях, где пользователь положительно взаимодействовал с объектом, поставим , а на тех, где взаимодействие было негативным или его вообще не произошло, поставим . Эта компонента фидбека называется предпочтением (preference):
Тем самым мы избавились от пропусков в матрице, но использовали не всю информацию. Согласитесь, если один пользователь посмотрел часовое видео польностью, а другой выключил после 5 минут, несправедливо считать, что это видео им понравилось в одинаковой степени. Введём ещё степень уверенности (confidence), отражающую уверенность в оценке пользователя:
где – некоторая константа.
На местах пропусков мы явно проставляем . На остальных позициях мы можем сами регулировать степень уверенности в зависимости от фидбека пользователя.
Рассмотрим следующую функцию потерь:
Она позволяет:
- Учитывать неявный фидбек, которого обычно на порядок больше, чем явного,
- Регулировать степень уверенности в действиях пользователей.
IALS: оптимизация
Распишем нашу функцию потерь по аналогии с ALS и приведем к форме :
Разобьём сумму на 2 части. В первой будет сумма по тем элементам, с которыми у пользователя не было положительного взаимодействия. Во второй – сумма по всем остальным элементам. Также заметим, что во втором множителе суммирование имеет смысл только по ненулевым элементам:
Заметим, что в первой сумме все будут равны 1 (так как везде ). Прибавим и вычтем единицу к во второй сумме и разобьем её на две компоненты. Вторый из них будет сумма по всем , где . Объединив её с первой суммой, получим
просто :
Заметим, что произведение никак не зависит от . Мы можем посчитать его один раз для всех перед очередной итерацией. В остальном же мы точно так же, как и в случае с обычным ALS, можем распределить данные так, чтобы на одной машине содержались все , необходимые для обновления , хранящихся на этой машине, и сделать следующий шаг оптимизации нашей функции потерь.
Обобщения ALS и IALS
- Обе модели: и ALS, и Imlicit ALS – можно несколько усложнить, вместо рассмотрев . В таком случае и играют роль некоторых априорных усреднённых оценок пользователя и объекта соответственно, а является глобальной априорной константой.
- В модели IALS мы обычно полагаем элементы равными во всех случаях, когда имело место взаимодействие, но можем использовать и другие значения, в том числе зависящие от того, что ещё нам известно о пользователях и объектах.
- Для уверенности для IALS необязательно использовать в качестве значения по умолчанию. Например, события «пользователь не посмотрел популярный фильм» и «пользователь не посмотрел редкий фильм» могут иметь для нас разный вес.
FunkSVD
Этот подход получил широкую известность после конкурса Netflix Prize в 2006 году. Пост Саймона Фанка про участие в Netflize Prize
Фанк предложил моделировать рейтинг как . Однако, в отличие от ALS, оптимизация производилась с помощью стохастического градиентного спуска. Правила обновления весов выглядели следующим образом:
Этот подход не получил большой популярности, так как градиентный спуск, в отличие от ALS, намного сложнее распараллелить.
Singular Value Decomposition with implicit feedback (SVD++)
Ранее мы отдельно рассматривали факторизации для явного и неявного фидбека. Но, ограничиваясь только одним типом фидбека, мы теряем много информации. Если мы работаем над стриминговым сервисом, то в качестве неявного фидбека мы можем взять, например, историю фильмов, взятых в прокат. Такие данные не предоставляют нам явных оценок пользователей, но позволяют выявить неявные предпочтения. Учесть неявный фидбек в модели можно следующим образом:
В данной модели пользователь представлен скрытым представлением , а также слагаемым, отражающим историю неявных взаимодей с айтемами: .
Важно отметить, что вектора не совпадают с векторами . Это своего рода «неявные» вектора айтемов.
Collaborative Filtering with Temporal Dynamics (timeSVD++)
Особенностью всех рассмотренных на данный момент разложений является отсутствие учёта порядка просмотра объектов.
Однако, как показывает практика, со временем пользователь может менять своё мнение о тех или иных айтемах. Тогда, отсортировав взаимодействия по времени, мы можем разбить события на бакеты и модифицировать приведённую выше функцию потерь, в которой таргет выражается следующим образом:
SLIM (Sparse Linear Methods)
Описанные выше методы демонстрируют хорошее качество, однако требуют больших усилий для эффективной работы в онлайн сервисах. Возникает потребность в лёгких моделях, эффективность которых значительно выше, но качество которых не сильно хуже. Для этого была предложена линейная разреженная модель.
Итак, пусть – бинарная матрица user-item взаимодействий, например, матрица кликов/показов. Будем определять ответ алгоритма как взвешивание событий из истории пользователя:
При этом наложим ограничение . В такой постановке мы будем учить модель находить «похожие» объекты. Добавим ещё условие , которое позволит нам избежать элементарного решения – единичной матрицы .В результате вес выступает в качестве некоторой меры схожести -го и -го объектов. Осталось определиться с методом оптимизации данных параметров.
Для оптимизации используется функция потерь MSE с - и -регуляризаторами:
Можно заметить, что задачу можно разбить на независимых по строкам матрицы :
Данную задачу можно решать покоординатным спуском:
- Фиксируем все строки , кроме одной координаты ;
- переходим в оптимум по ;
- переходим к следующей координате;
- повторять до сходимости.
Применение данной модели выглядит следующим образом:
- Рассчитываем вектор взаимодействий пользователя ;
- Считаем для всех непросмотренных объектов;
- Отбираем топ непросмотренных объектов по .
Так как в задаче оптимизации мы пользуемся -регуляризацией, матрица получается разреженной. Матрица просмотров тоже разреженная (по определению). Эти обстоятельства позволяют заметно улучшить эффективность применения модели.
Итоги
В этом параграфе мы рассмотрели некоторые рекомендательные модели на основе матричных факторизаций. Такие модели редко используется в чистом виде для формирования рекомендательной выдачи. Обычно результаты матричной факторизации используются для генерации кандидатов в рекомендации, когда из сотен тысяч и миллионов объектов необходимо отобрать небольшое количество (например, сотни) самых релевантных. Для генерации кандидатов требуется перемножить вектор пользователя с вектором каждого из сотен тысяч объектов и отобрать топ самых релевантных.
В онлайн-сервисах, когда время формирования рекомендаций составляет несколько сотен миллисекунд, нет возможности при каждом запросе рассчитывать релевантность каждого объекта для данного пользователя. Оптимизировать поиск можно с помощью инструментов для поиска ближайших соседей. Для любой функции близости, в том числе и для скалярного произведения, можно построить индекс – структуру данных, с помощью которой для любого пользователя мы сможем быстро приближённо, но зато быстро искать «ближайшие» объекты. В результате, принцип работы выглядит следующим образом:
- обучаются эмбеддинги объектов и пользователей;
- для представлений эмбеддингов строится индекс;
- в рантайме по вектору пользователя происходит приближённый поиск самых релевантных объектов; таким образом генерируется список кандидатов в рекомендации;
- дальше список кандидатов обрабатывается с помощью более хитрых методов машинного обучения.
Подробнее о том, как быстро искать ближайших соседей, вы можете узнать в параграфе посвященном метрическим методам
Помимо генерации кандидатов, полученные представления можно использовать в качестве признаков в более сложных моделях.
Основной недостаток методов, основанных на матричной факторизации, состоит в том, что они используют лишь информацию о взаимодействии пользователей и объектов, но не о них самих. В следующем параграфе мы рассмотрим контентные методы, которые используют атрибуты объектов и пользователей.