notes/machine_learning/recommender_systems.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы"
]
},
"source": [
"## Введение в задачу выдачи рекомендаций\n",
"\n",
"#### Постановка\n",
"\n",
"Задачи выдачи рекомендаций предполагает, что имеются:\n",
"* множество $U$, составленное из элементов, для которых или к которым делаются рекомендации;\n",
"* множество $I$, составленное из элементов, которые могут быть порекомендованы;\n",
"* множество $\\Omega$, составленное из различных контекстов, в которых могут делаться рекомендации.\n",
"\n",
"В зависимости от ситуации дать рекомендации для $u \\in U$ при условии контекста $\\omega \\in \\Omega$ может означать:\n",
"* отранжировать всё множество $I$;\n",
"* отобрать $k$ элементов из множества $I$, где $k$ — заранее заданная константа;\n",
"* вернуть отранжированный список из $k$ элементов множества $I$ (т.е. это комбинация двух предыдущих вариантов).\n",
"\n",
"Довольно часто в качестве множества $U$ берётся множество пользователей. Из исключений можно отметить так называемые item2item-рекомендации, где множество $U$ совпадает со множеством $I$. Впрочем, если говорить про персонализированные item2item-рекомендации, то там $U$ всё-таки будут составлять пользователи, а текущий объект, к которому подбираются рекомендации, является частью контекста $\\omega$. Так или иначе, далее ради наглядности элементы множества $U$ будут называться пользователями.\n",
"\n",
"Множество $I$ может состоять, например, из товаров в интернет-магазине, фильмов в онлайн-кинотеатре или публикаций для ленты в соцсети. Далее эти объекты будут называться предметами по аналогии с англоязычным «items», хотя они и не обязаны быть материальными. Такое обозначение выбрано, потому что слово «объект» применительно к машинному обучению означает элемент обучающей выборки (т.е. строку матрицы признакового описания $X$) и не хочется его перегружать.\n",
"\n",
"Контекст позволяет учитывать признаки, относящиеся к ситуации, в которой делаются рекомендации: например, тип рекомендательного блока. Но контекста может и не быть — тогда используются только признаки пользователей и предметов. В частности, если вернуться к примеру с типом блока, то можно обойтись без контекста, построив по отдельной рекомендательной системе для каждого типа.\n",
"\n",
"Рекомендательные системы нужны, чтобы автоматизировать или хотя бы облегчить пользовательский выбор, а также чтобы направить его в нужное русло. Выбирать самостоятельно пользователи могут не желать по целому ряду причин. В случае с выбором трека на стриминговой платформе это отвлекает от непрерывного прослушивания музыки; в случае с покупкой дорогой бытовой техники качественный выбор может требовать поиска и анализа определённого количества информации; в случае заказа в сервисе доставки продуктов необходимо ничего не забыть из десятков позиций.\n",
"\n",
"Хорошие рекомендательные системы не просто подбирают наиболее подходящие варианты, но и имеют дополнительные эффекты в виде открытия для пользователей новых предметов, о которых те сами навряд ли бы узнали.\n",
"\n",
"#### Этапы, на которые разбивается выдача рекомендаций\n",
"\n",
"В общем случае генерация рекомендаций для текущего пользователя $u \\in U$ при текущем контексте $\\omega \\in \\Omega$ может включать следующие стадии:\n",
"* легковесное извлечение кандидатов (retrieval); этот этап нужен, если количество предметов $\\vert I \\vert$ слишком большое, чтобы их все можно было полноценно обработать;\n",
"* фильтрация кандидатов, то есть удаление тех кандидатов, которые не подходят по каким-либо требованиям, налагаемым предметной областью;\n",
"* ранжирование (или отбор top-$k$ финальных кандидатов, если их нужно лишь отобрать);\n",
"* переранжирование; на этом этапе в сортировку предметов по убыванию предсказаний ранжирующей модели вносятся корректировки; примеры таких внешних правок:\n",
" - обеспечение [разнообразия](__home_url__/notes/Разнообразие через DPP (Determinantal Point Processes)) (diversity),\n",
" - продвижение предметов, которые нехарактерны для пользователя (user-based exploration),\n",
" - продвижение предметов, реакцию на которые было бы [полезно узнать](__home_url__/tags/активное_обучение) для улучшения модели (system-based exploration),\n",
" - адаптивная подстройка в режиме реального времени под результаты взаимодействия пользователя с предыдущими рекомендациями.\n",
" \n",
"#### Методы ранжирования\n",
"\n",
"В число методов, которыми можно провести ранжирование, входят:\n",
"* [подсчёт простого показателя](__home_url__/notes/Рекомендации по убыванию показателя) и [поиск баланса между изучением и применением](__home_url__/notes/Баланс между изучением и применением в задаче о многоруком бандите);\n",
"* [коллаборативная фильтрация](__home_url__/notes/Коллаборативная фильтрация):\n",
" - классическая,\n",
" - SLIM (Sparse Linear Models);\n",
"* [матричные разложения и факторизационные машины](__home_url__/notes/Матричные разложения и факторизационные машины);\n",
"* [нейросетевые методы для заполнения кросс-табуляционной матрицы](__home_url__/notes/Нейросетевые методы для заполнения кросс-табуляционной матрицы):\n",
" - нейросетевые разложения,\n",
" - очищающий от шума автокодировщик;\n",
"* [обучение на матрице признакового описания](__home_url__/notes/Обучение ранжирующей модели на матрице признакового описания):\n",
" - градиентного бустинга,\n",
" - нейронных сетей:\n",
" - адаптации [DSSM](__home_url__/notes/DSSM (Deep Semantic Similarity Model)) под рекомендательные системы,\n",
" - [BERT4Rec](__home_url__/notes/Трансформерные модели в рекомендациях), [SASRec](__home_url__/notes/Трансформерные модели в рекомендациях), etc.\n",
"\n",
"Некоторые из перечисленных вариантов могут быть использованы и для извлечения кандидатов, если они достаточно быстры в рантайме. Действительно, top-$k$ товаров, отранжированных каким-либо методом, можно рассматривать в качестве кандидатов для более сложного метода.\n",
"\n",
"Также оценки релевантности предмета пользователю, полученные каким-либо методом, можно использовать как признаки в мета-модели, обучаемой с учителем (разумеется, при условии, что используется разделение по времени и/или пользователям, чтобы избежать перетекания целевой переменной в эти признаки).\n",
"\n",
"#### Открытые практические вопросы\n",
"\n",
"Перечисленные выше методы ранжирования предполагают, что рекомендации получаются сортировкой по убыванию возвращённых моделью степеней соответствия предметов пользователю. Очевидно, что методы, способные напрямую генерировать список рекомендаций, оптимизированный как единое целое, работали бы лучше, чем методы с отдельными оценками для каждого предмета. Однако работоспособные методы, сразу выдающие списки предметов, пока не являются общеизвестными (если вообще существуют). Недостатки сортировки по предсказаниям пытаются исправить переранжированием. Некоторые проблемы (скажем, нехватка разнообразия) могут быть решены таким образом. Но остаются следующие проблемы:\n",
"* влияние одних рекомендаций на другие (например, кликбейтный предмет может увести пользователя в сторону и не дать посмотреть следующие рекомендации);\n",
"* внесение так называемого «аплифта» (с наиболее очевидными предметами пользователи могли бы провзаимодействовать и без рекомендаций);\n",
"* расхождения между релевантностью и метриками, которые должны оптимизироваться (в любом достаточно зрелом сервисе метрик много, и нельзя просто взять и заложить в целевую переменную их комбинацию);\n",
"* максимизация долгосрочных исходов взаимодействия с рекомендациями (иногда бывает связь между тем, что пользователь увидел в моменте, и тем, вернётся ли он ещё и как долго будет листать рекомендации в следующий раз). "
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы"
]
},
"source": [
"## Рекомендации по убыванию показателя\n",
"\n",
"В этой заметке рассматривается один из наиболее простых способов получения рекомендаций. Он устроен так:\n",
"* для каждого «предмета» (того, что ранжируется) вычисляется некий показатель;\n",
"* «предметы» ранжируются по убыванию показателя или какой-либо статистики его предполагаемого распределения. \n",
"\n",
"Для примера возьмём в качестве предметов товары в интернет-магазине. Тогда вышеописанным показателем могут быть:\n",
"* конверсия из просмотра информации о товаре в его покупку или в его откладывание в корзину;\n",
"* произведение какой-либо конверсии на маржу (наценку магазина);\n",
"* средние за день продажи (в штуках или денежном выражении), подсчитанные по $D$ последним дням или по всем дням, когда товар был в наличии;\n",
"* средняя оценка пользователей, купивших данный товар.\n",
"\n",
"Что именно брать в качестве такого показателя, зависит от особенностей задачи и целей внедрения рекомендательной системы. Скорее всего, знание предметной области позволит включить в формулу для показателя и дополнительные факторы. Например, если разрабатывается система, посетителю новостного агрегатора рекомендующая новости, необходимо учитывать время с момента публикации, чтобы не рекомендовать устаревшие материалы.\n",
"\n",
"Теперь перейдём к тому, как можно давать рекомендации.\n",
"\n",
"Наивное решение заключается в том, что предметы можно просто отранжировать по значениям их показателя. Главный недостаток этого решения — риск выдачи некачественных рекомендаций из-за нехватки данных по части предметов. Например, предположим, что рекомендации даются на основании пользовательских оценок и один товар получил среднюю оценку 4,9 по тысяче отзывам, а другой товар получил всего один отзыв с оценкой 5. Формально говоря, второй товар имеет более высокий показатель и, значит, рекомендован должен быть он, однако ясно, что надёжнее было бы рекомендовать первый.\n",
"\n",
"Для решения обозначенной проблемы можно посмотреть на задачу как на задачу о «многоруком бандите» и применить соответствующий [аппарат](__home_url__/notes/Баланс между изучением и применением в задаче о многоруком бандите). Правда, есть одно отличие: возможности проводить изучение нет (в примере с пользовательскими оценками они уже как-то проставлены) и теперь осталось лишь применение в условиях неопределённости. Это означает, что теперь неопределённость должна влиять в отрицательную сторону. Для метода оптимистичных начальных значений нужно, наоборот, заменить их на пессимистичные, а в методе доверительной границы вместо верхней границы брать нижнюю. \n",
"\n",
"К плюсам рассматриваемого подхода (неважно, наивного или модифицированного) относятся:\n",
"* простота и прозрачность (актуально, если есть высокие требования к интерпретируемости);\n",
"* отсутствие высоких требований к данным (можно использовать сразу же на старте проекта);\n",
"* лёгкость в реализации (просто добавить в качестве ещё одного бейзлайна).\n",
"\n",
"К минусам же относятся:\n",
"* неперсонализированность (все пользователи видят одно и то же);\n",
"* тривиальность рекомендаций (возможно, о том, что рекомендуется, пользователи и так знают)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы"
]
},
"source": [
"## Обучение ранжирующей модели на матрице признакового описания\n",
"\n",
"В этой заметке речь пойдёт о формировании рекомендаций по убыванию предсказаний модели, которая была обучена на матрице признакового описания (design matrix), то есть на том, что обычно используют при обучении с учителем. Как это проговаривалось во [введении в рекомендательные системы](__home_url__/notes/Введение в задачу выдачи рекомендаций), предполагается, что рекомендации делаются для пользователей, а рекомендуемые сущности называются предметами, хотя они и не обязаны быть материальными.\n",
"\n",
"Объектами (в терминологии машинного обучения) будем считать ситуации, благодаря которым некоторый пользователь провзаимодействовал с некоторым предметом. Например, такой ситуацией может быть:\n",
"* просмотр информации о предмете (скажем, посещение страницы с товаром в интернет-магазине);\n",
"* простановка предмету оценки;\n",
"* показ предмета пользователю в рекомендациях (желательно, фактический показ, то есть показ там, где пользователь увидел рекомендацию, а не мог бы увидеть, если бы пролистал вниз или вбок).\n",
"\n",
"Эти ситуации или выливаются в какие-нибудь целевые действия пользователя с предметом, или нет. От подобных действий (или их отсутствия) зависит целевая переменная, ассоциированная с объектом. Она может быть вещественной или категориальной (в частности, бинарной). Как следствие, задача может быть сформулирована как задача регресии или как задача классификации. Однако и в том, и в другом случае задачу можно переформулировать и как задачу [ранжирования](__home_url__/tags/ранжирование). Для ранжирования в примерах с просмотром информации о предмете и с простановкой оценки разбиение на группы может делаться по пользователю, а в примере с показами в рекомендациях группы могут быть образованы всеми объектами, относящимися к одному заходу пользователя на страницу с рекомендациями.\n",
"\n",
"У задач регрессии и классификации есть то преимущество, что предсказания модели проще интерпретировать: например, в задаче регрессии при использовании MSE предсказания имеют ту же размерность, что и целевая переменная, а в задаче классификации предсказанные вероятности можно [откалибровать](__home_url__/notes/Калибровка предсказанных вероятностей). Однако даже если задача не была поставлена как задача ранжирования, рекомендательная система всё равно будет проводить ранжирование по убыванию предсказаний, возвращаемых моделью. Поэтому у функций потерь, предназначенных для ранжирования, больше преимуществ с точки зрения оптимизации [метрик качества ранжирования](__home_url__/notes/Метрики качества ранжирования).\n",
"\n",
"Убедимся в этом на примерах. В задаче классификации с бинарной целевой переменной, кодирующей, будет ли товар куплен пользователем, логарифмическая функция потерь чувствительна к тому, отличает ли модель тех, кто более склонен покупать всё подряд, от тех, кто в принципе не склонен к покупкам. Однако для задачи ранжирования это не важно, и поэтому функции потерь для ранжирования сфокусированы лишь на том, как расставлены объекты внутри каждой из групп. Или вот иной пример. Если пользователи оценивают предметы по пятибалльной шкале, то с этой оценкой в качестве целевой переменной задача может быть задачей регрессии. Но если для одной и той же группы для всех объектов ошибиться на одну и ту же константу, то ранжирование объектов не изменится, а, значит, и штрафовать за такую ошибку не надо. Это соображение отражено в функциях потерь для задачи ранжирования, таких как QueryRMSE.\n",
"\n",
"Любопытно, что выбор между оптимизацией метрик качества и интерпретируемостью не всегда является компромиссным. В статье [Bai et al., 2023](https://arxiv.org/pdf/2211.01494.pdf) показывается, что логарифмическую функцию потерь можно бесконфликтно оптимизировать совместно с некоторой модификацией функции потерь QuerySoftmax.\n",
"\n",
"Что касается признаков, много что можно придумать, но одной из идей, с которых стоит начать, являются счётчики. Под счётчиком имеется в виду количество определённых действий, совершённых:\n",
"* текущим пользователем со всеми предметами;\n",
"* текущим пользователем только с текущим предметом;\n",
"* текущим пользователем с предметами, относящимися к той же категории, что и текущий;\n",
"* всеми пользователями с текущим предметом;\n",
"* всеми пользователями с предметом, относящимся к той же категории, что и текущий;\n",
"* пользователями, относящимися к той же группе, что и текущий, со всеми предметами;\n",
"* пользователями, относящимися к той же группе, что и текущий, с текущим предметом;\n",
"* пользователями, относящимися к той же группе, что и текущий, с предметами, относящимися к той же категории, что и текущий.\n",
"\n",
"К сильным сторонам обучения на матрице «объекты-признаки» относятся:\n",
"* разносторонность (т.е. способность учитывать данные разной природы);\n",
"* универсальность (в принципе, при помощи данного подхода можно строить мета-модели, дающие рекомендации по оценкам от других рекомендательных систем);\n",
"* поддержка предсказаний для новых пользователей или предметов без предварительного накопления истории по взаимодействиям с их участием;\n",
"* возможность отражать в признаках сиюминутный контекст, из-за которого релевантность предмета может меняться. \n",
"\n",
"К слабым сторонам данного подхода стоит отнести такие:\n",
"* при обучении для вычисления целевой переменной обязательно требуются данные, детализированные до отдельных взаимодействий пользователей с предметами, а агрегированные статистики не подойдут;\n",
"* детализация постановки задачи машинного обучения может включать неочевидные места, как, скажем, такие:\n",
" - как подбирать значения целевой переменной, соответствующие разным видам действий (в примере с интернет-магазином это могут быть добавление в корзину, добавление в избранное и заказ).\n",
" - каким брать максимальный интервал времени между первичной ситуацией и целевым действием (за секунду после просмотра рекомендации пользователь не успеет заказать товар, но если он закажет его через год, то навряд ли это заслуга той рекомендации)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы"
]
},
"source": [
"## Кросс-табуляционная матрица\n",
"\n",
"#### Введение\n",
"\n",
"Многие методы, используемые в [рекомендательных системах](__home_url__/notes/Введение в задачу выдачи рекомендаций) для решения задач извлечения кандидатов или ранжирования, настраиваются на данных, хранящихся в специальном формате. Этот формат называется кросс-табуляционной матрицей.\n",
"\n",
"Пусть $U$ — множество пользователей, а $I$ — множество предметов (от англоязычного «items», хотя они и могут не быть материальными). Тогда кросс-табуляционная матрица $R$ имеет размер $\\vert U \\vert \\times \\vert I \\vert$, а на пересечении $i$-й строки и $j$-го столбца в ней стоит число $R_{ij}$, прямо или косвенно показывающее степень соответствия $j$-го предмета $i$-му пользователю. При этом важно отметить, что матрица $R$ может содержать пропущенные значения. На практике она оказывается сильно разреженной, а такие методы, как [коллаборативная фильтрация](__home_url__/notes/Коллаборативная фильтрация) или [факторизационные машины](__home_url__/notes/Матричные разложения и факторизационные машины), как раз тем и занимаются, что заполняют пропуски. Как только все ячейки станут заполнены, рекомендации для $i$-го пользователя можно будет получать, сортируя предметы по убыванию их $R_{i\\cdot}$. \n",
"\n",
"В матрице $R$ могут храниться оценки предметов, проставляемые пользователями. Тогда матрица $R$ содержит информацию, прямо указывающую на степени соответствия предметов пользователям (в англоязычной литературе это называют explicit feedback). Но может быть и так, что в матрице $R$ хранится количество покупок пользователем какого-либо предмета или бинарный индикатор того, что пользователь хотя бы раз покупал предмет. Тогда информация из матрицы $R$ лишь косвенно указывает на степени соответствия предметов пользователям, а именно делает это лишь в той мере, в какой можно считать, что всё, что пользователь приобретает, ему нравится (это называют implicit feedback).\n",
"\n",
"При косвенной релевантности может всплыть проблема подбора отрицательных примеров. Например, если в $R$ хранится бинарный индикатор покупки, то все значения $R$ или равны 1, или не заполнены. В этом случае обучение только на заполненных ячейках бессмысленно. Но даже если бы в $R$ было количество покупок, важнее научиться отличать то, что пользователь никогда не купит, от того, что он может купить, так что и тут только от заполненных ячеек пользы мало. Разумеется, в незаполненные ячейки можно вписывать 0 (так называемый positive-unlabeled learning). Метод [IALS](https://www.researchgate.net/publication/220765111_Collaborative_Filtering_for_Implicit_Feedback_Datasets) (Implicit Alternating Least Squares) делает так со всеми пустыми ячейками и обучается на полной матрице $R$ за приемлемое время. Однако в общем случае при большом $\\vert I \\vert$ для $i$-го пользователя в качестве отрицательных примеров приходится использовать лишь часть незаполненных ячеек из строки $R_{i\\cdot}$. При этом есть смысл не ограничиваться случайным сэмплированием, а подбирать более сложные отрицательные примеры. \n",
"\n",
"Если же матрица $R$ хранит явные оценки релевантности, заполненных ячеек может оказаться достаточно, особенно если для большинства пользователей встречается почти весь диапазон возможных значений. Но, например, в случае с товарами пользователи гораздо чаще ставят одну звезду, когда им что-то не понравилось, чем пять звёзд, когда всё понравилось. Чтобы выправить это смещение, можно добавить в качестве положительных примеров те товары, у которых оценки нет, но которые пользователь покупал (желательно, несколько раз).\n",
"\n",
"В идеале, при явной обратной связи значения ячеек $R$ должны содержать унифицированную количественную меру того, подошёл ли предмет пользователю или нет, но на практике субъективная интерпретация шкалы может вносить искажения. Поэтому лучше или использовать бинарную шкалу («понравилось» и «не понравилось»), или уделить достаточно внимания сбору данных (например, разместить над формой отправки оценки краткую инструкцию).\n",
"\n",
"#### Сравнение с матрицей признакового описания\n",
"\n",
"В задаче выдачи рекомендаций альтернативой кросс-табуляционной матрице может быть [матрица «объекты-признаки»](__home_url__/notes/Обучение ранжирующей модели на матрице признакового описания) (design matrix; то, что обычно используют при обучении с учителем). Вот некоторые варианты таких матриц:\n",
"* положительными примерами являются предметы, с которыми пользователь органически совершил целевое действие (скажем, заказал товар), отрицательные примеры сэмплируются случайно, а признаки рассчитываются на момент перед соответствующим целевым действием;\n",
"* примерами являются фактические показы в рекомендациях, признаки рассчитываются на момент таких показов (возможно, с задержкой, имитирующей задержку данных в реальном сервисе), а целевая переменная зависит от того, привёл ли показ к совершению каких-либо целевых действий.\n",
"\n",
"Главное отличие кросс-табуляционной матрицы от матрицы признакового описания связано с тем, что именно она ожидается на вход многими методами, успешно работающими с идентификаторами пользователей и предметов. А вот в матрице признакового описания эти идентификаторы являются категориальными признаками, имеющими большое количество уникальных значений, каждое из которых встречается не так много раз. С такими признаками классические методы обучения на табличных данных работают не очень хорошо. \n",
"\n",
"Ещё одно отличие в том, что в кросс-табуляционной матрице пара из пользователя и предмета не может встретиться более одного раза. Стало быть, степень соответствия $j$-го предмета $i$-му пользователю всего одна, и можно считать, что она берётся по состоянию на текущий момент. Напротив, в матрицах «объекты-признаки» может получиться так, что в один момент времени некий предмет был отрицательным примером для пользователя, а позже стал положительным, но противоречия тут нет, потому что и признаки должны были поменяться. Отсюда вытекает, что только модели ранжирования, обученные на матрице «объекты-признаки», могут в режиме реального времени перестраивать рекомендации под текущие цели пользователя."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы"
]
},
"source": [
"## Коллаборативная фильтрация\n",
"\n",
"#### Введение\n",
"\n",
"В этой заметке будет описан один из способов [выдавать рекомендации](__home_url__/notes/Введение в задачу выдачи рекомендаций). Как всегда, пользователями называются те, для кого делаются рекомендации (или то, к чему делаются рекомендации), а предметами называется то, что рекомендуется, даже если оно нематериально.\n",
"\n",
"Коллаборативная фильтрация — способ выдавать рекомендации, отталкиваясь от сходства между пользователями или предметами. Прилагательное «коллаборативная» в данном контексте как раз и указывает на то, что информация о разных сущностях совмещается. Альтернативой коллаборативности является так называемая контентность, то есть использование характеристик пользователей и предметов. В коллаборативной фильтрации эти признаки игнорируются. Ну а слово «фильтрация» восходит к тому, что изначально этот метод использовался для отбора top-$k$ кандидатов из всех возможных.\n",
"\n",
"Коллаборативная фильтрация бывает двух типов:\n",
"* «пользователь-пользователь» (она же коллаборативная фильтрация от пользователя, user-based collaborative filtering);\n",
"* «предмет-предмет» (она же коллаборативная фильтрация от предмета, item-based collaborative filtering).\n",
"\n",
"Оба типа используют [кросс-табуляционную матрицу](__home_url__/notes/Кросс-табуляционная матрица) $R$, и оба сводятся к тому, что пропущенные значения в этой матрице заполняются, а потом рекомендуется то, что имеет наибольшее оценённое значение. Разница только в том, как это делается.\n",
"\n",
"#### Тип «пользователь-пользователь»\n",
"\n",
"В варианте «пользователь-пользователь» формула для заполнения матрицы $R$ имеет вид:\n",
"$$\\hat{R}_{ij} = \\frac{\\sum_{i' \\in U_j} w_{ii'} R_{i'j}}{\\sum_{i' \\in U_j} |w_{ii'}|},$$\n",
"где $U_j$ — множество всех пользователей $i'$, для которых известно $R_{i'j}$, а веса $w_{ii'}$ показывают степень схожести $i$-го пользователя и $i'$-го пользователя. Эти веса могут быть как положительными, так и отрицательными, причём большие по модулю отрицательные значения говорят о том, что пользователи противоположны друг другу по своим предпочтениям и что поэтому действия одного из них всё равно проливают свет на предпочтения другого. Один из вариантов, как можно определить веса, таков:\n",
"$$w_{ii'} = \\frac{(1 / |I_{ii'}|) \\sum_{j \\in I_{ii'}} (R_{ij} - \\overline{R}_{i\\cdot})(R_{i'j} - \\overline{R}_{i'\\cdot})}{\\sqrt{(1 / |I_{i}|) \\sum_{j \\in I_i} (R_{ij} - \\overline{R}_{i\\cdot})^2} \\sqrt{(1 / |I_{i'}|) \\sum_{j \\in I_i'} (R_{i'j} - \\overline{R}_{i'\\cdot}})^2},$$\n",
"где $I_i$ — множество предметов, для которых есть значение в $i$-й строке матрицы $R$, $I_{ii'}$ — множество предметов, для которых есть значения и в $i$-й, и в $i'$-й строках матрицы $R$, а $\\overline{R}_{i\\cdot}$ — среднее (разумеется, без учёта пропусков) $i$-й строки матрицы $R$. По сути, так определённый вес $w_{ii'}$ — это коэффициент корреляции Пирсона между $i$-й и $i'$-й строками матрицы $R$, модифицированный для случая, когда часть значений пропущена.\n",
"\n",
"На практике формулу для $w_{ii'}$ немного меняют. Во-первых, можно положить $w_{ii'} = 0$, если множество $I_{ii'}$ содержит слишком мало элементов. Тогда из формирования рекомендаций для $i$-го пользователя будут исключены те пользователи, о схожести или несхожести которых с $i$-м недостаточно информации. Во-вторых, для увеличения скорости работы веса $w_{ii'}$ можно предрассчитать заранее, а потом для каждого $i$ оставить только сколько-то из них с наибольшими модулями, положив остальные равными нулю.\n",
"\n",
"#### Тип «предмет-предмет»\n",
"\n",
"Вариант «предмет-предмет» довольно похож на вариант «пользователь-пользователь»:\n",
"$$\\hat{R}_{ij} = \\frac{\\sum_{j' \\in I_i} w_{jj'} R_{ij'}}{\\sum_{j' \\in I_i} |w_{jj'}|},$$\n",
"где $I_i$ — множество всех предметов $j'$, для которых известно $R_{ij'}$, а веса $w_{jj'}$ могут быть вычислены как поддерживающие пропуски модификации коэффициента корреляции Пирсона между $j$-м и $j'$-м столбцами матрицы $R$. С точки зрения интерпретации это означает, что если в варианте «пользователь-пользователь» рекомендовались предметы, которые предпочитают похожие пользователи, то в варианте «предмет-предмет» рекомендуются предметы, похожие на те, что предпочитаются пользователем.\n",
"\n",
"#### Сравнение\n",
"\n",
"Строгих доказательств того, что какой-то один тип коллаборативной фильтрации имеет более высокое качество, нет. В некоторых [экспериментах](http://www.diva-portal.org/smash/get/diva2:1111865/FULLTEXT01.pdf) вариант «пользователь-пользователь» победил.\n",
"\n",
"Впрочем, помимо качества важно ещё и быстродействие на стадии выдачи рекомендаций. Тут, введя дополнительные предположения, можно получить строгие результаты. Например, если предположить, что пользователей сильно больше, чем предметов, а ещё предположить, что каждый пользователь провзаимодействовал лишь с малым количеством предметов, то для варианта «предмет-предмет» вполне можно заранее предрассчитать матрицу схожести между предметами. Если даже появится какое-либо новое взаимодействие, из-за большой длины столбцов матрицы $R$ оно не сильно изменит результаты. Однако для варианта «пользователь-пользователь» может потребоваться каждый раз заново рассчитывать матрицу схожести между пользователями, потому что любое новое взаимодействие способно сильно изменить веса для пользователя, совершившего это взаимодействие.\n",
"\n",
"#### Sparse Linear Models (SLIM)\n",
"\n",
"В статье [Ning, Karypis, 2011](http://glaros.dtc.umn.edu/gkhome/node/774) предложена модификация коллаборативной фильтрации типа «предмет-предмет». Формула предсказания упрощается:\n",
"$$\\hat{R}_{ij} = \\sum_{j' \\in I_i} w_{jj'} R_{ij'},$$\n",
"а веса $w_{jj'}$ становятся обучаемыми параметрами с ограничением, что $w_{jj} = 0$, чтобы $\\hat{R}_{ij}$ не строилась по $R_{ij}$. Обучение весов проводится численной оптимизацией функции потерь, являющейся среднеквадратичной ошибкой (MSE) с $L_1$- и и $L_2$-[регуляризациями](__home_url__/notes/Регуляризация штрафом, накладываемым на норму обучаемых параметров)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы"
]
},
"source": [
"## Матричные разложения и факторизационные машины\n",
"\n",
"#### Матричные разложения\n",
"\n",
"Как правило, для выдачи рекомендаций раскладывают на множители [кросс-табуляционную матрицу](__home_url__/notes/Кросс-табуляционная матрица) $R$. Искать её разложение можно, в частности, в следующих видах:\n",
"* $R \\approx WV^T$, где $W$ — матрица размера $\\vert U \\vert \\times k$, $V$ — матрица размера $\\vert I \\vert \\times k$, $U$ — множество пользователей (то есть тех, для кого делаются рекомендации, или, что реже, того, к чему делаются рекомендации), $I$ — множество так называемых предметов (то есть того, что может быть порекомендовано), а $k$ — гиперпараметр (как правило, $k$ берут много меньше, чем и $\\vert U \\vert$, и $\\vert I \\vert$). Эта форма разложения интерпретируется так. В матрице $W$ находятся $k$ скрытых признаков пользователей, в матрице $V$ находятся $k$ скрытых признаков предметов, а чем больше скалярное произведение вектора скрытых признаков пользователя на вектор скрытых признаков предмета, тем выше для этого пользователя должен быть отранжирован этот предмет.\n",
"* $R \\approx WV^T + b + c + m$, где $m$ — среднее значение известных ячеек матрицы $R$, $b$ — вектор-столбец размера $\\vert U \\vert \\times 1$, $c$ — вектор-строка размера $1 \\times \\vert I \\vert$, а операция сложения матрицы с вектором, одна из размерностей которого меньше, определена через бродкастинг. По сравнению с предыдущей формой интерпретация меняется так. Предполагается, что каждый пользователь дополнительно имеет свой собственный сдвиг, выраженный в $b$, каждый предмет имеет свой собственный сдвиг, выраженный в $c$, и есть глобальный сдвиг $m$.\n",
"\n",
"Чтобы найти $W$, $V$ и, если они есть, $b$ и $c$ ($m$ находится по своему определению), можно ввести какую-либо функцию потерь (чаще всего берут MSE или MSE с $L_2$-[регуляризацией](__home_url__/notes/Регуляризация штрафом, накладываемым на норму обучаемых параметров)), а потом, считая эти неизвестные величины оптимизируемыми параметрами, применить какой-нибудь численный метод:\n",
"* градиентный спуск (или его модификации);\n",
"* покоординатный спуск (в контексте выдачи рекомендаций часто называемый alternating least squares): значения $W$, $V$, $b$ и $c$ как-то инициализируются, а затем по очереди все эти переменные кроме одной рассматриваются как константы и ищется значение одной незафиксированной, минимизирующее функцию потерь, после чего её старое значение заменяется на найденное, очередь переходит к следующей переменной и так далее вплоть до выполнения некоторого критерия остановки.\n",
"\n",
"Иногда находимое таким образом разложение матрицы $R$ называют её сингулярным разложением (SVD). Более того, некоторые конкретные спецификации обсуждаемого метода получили названия FunkSVD и SVD++. На самом деле, если понимать под SVD ровно [то](__home_url__/notes/Применение SVD в задачах анализа данных), что понимается под этим термином в линейной алгебре, то никакого отношения к SVD это не имеет. В частности, линейно-алгебраическое SVD не может работать, если в раскладываемой матрице есть пропущенные значения, а эти методы работают. Поэтому в контексте таких методов правильнее говорить просто о матричном разложении, а не о сингулярном разложении.\n",
"\n",
"#### Факторизационные машины\n",
"\n",
"Обобщением разложений матрицы $R$ являются факторизационные машины. Начнём с частного случая факторизационной машины, который эквивалентен матричному разложению.\n",
"\n",
"По матрице $R$ строится матрица признакового описания как для задачи обучения с учителем. Каждая заполненная ячейка $R_{ij}$ сопоставляется объекту, у которого есть $\\vert U \\vert + \\vert I \\vert$ признаков, из которых все нули кроме двух, которые равны единице и стоят на позициях, соответствующих индексу пользователя $i$ и индексу предмета $\\vert U \\vert + j$. Целевой переменной для такого объекта является $R_{ij}$. Нелишне отметить, что стандартные методы обучения с учителем с получившейся матрицей признакового описания не справились бы, потому что в ней слишком много признаков, каждый из которых почти всегда нулевой.\n",
"\n",
"Пусть предсказания делаются по следующей формуле:\n",
"$$\\hat{R_{ij}} = w_0 + \\left( \\sum_{l=1}^{\\vert U \\vert + \\vert I \\vert} w_l X_{rl} \\right) + W_{i\\cdot} (V_{j\\cdot})^T,$$\n",
"где $X$ — матрица обучающих данных из предыдущего абзаца, $r$ — индекс строки в матрице $X$, соответствующей $R_{ij}$ (нельзя считать, что $r = (i-1) \\vert I \\vert + j$, потому что в матрице $R$ есть ячейки с пропусками), а вектор $w$ размера $1 + \\vert U \\vert + \\vert I \\vert$, матрица $W$ размера $\\vert U \\vert \\times k$ и матрица $V$ размера $\\vert I \\vert \\times k$ — обучаемые параметры. Настраиваются они, как и в матричных факторизациях, градиентным спуском или покоординатным спуском. Видно, что матрицы $W$ и $V$ играют ту же роль, что и одноимённые матрицы в матричном разложении, $w_0$ соответствует $m$, а элементы $w$ с первого по $\\vert U \\vert$-й соответствуют $b$ и с $(\\vert U \\vert + 1)$-го по $(\\vert U \\vert + \\vert I \\vert)$-й — $c$. То есть просто задача матричного разложения оказалась переформулированной в терминах немного других переменных. \n",
"\n",
"Теперь ту же самую формулу для предсказаний перепишем в более громоздком виде:\n",
"$$\\hat{R_{ij}} = w_0 + \\sum_{l=1}^{\\vert U \\vert + \\vert I \\vert} w_l X_{rl} + \\sum_{p=1}^{\\vert U \\vert} \\sum_{q=1}^{\\vert I \\vert} W_{p\\cdot} (V_{q\\cdot})^T X_{rp} X_{r(\\vert U \\vert + q)}.$$\n",
"В двойной сумме среди всех слагаемых ненулевое только одно: при $p = i$ и $q = j$, потому что так была определена матрица $X$. Это и доказывает, что суть не изменилась. Зато теперь на правую часть можно посмотреть под другим углом: каждый признак вносит линейный вклад, а ещё есть взаимодействия признаков второго порядка, но только между такими парами признаков, где один относится к идентификатору пользователя, а другой — к идентификатору предмета.\n",
"\n",
"Более общие версии факторизационных машин возникают, когда матрица обучающих данных $X$ помимо one-hot encoded идентификаторов пользователя и предмета содержит ещё какие-либо признаки. Они могут быть как вещественными, так и категориальными, представленными в виде one-hot encoded идентификаторов своих значений (то есть вместо одного исходного признака далее будет рассматриваться столько признаков, сколько у него было уникальных значений). Пусть $L$ — множество индексов тех признаков, которые вносят линейный вклад, а $Q$ — множество, составленное из пар множеств индексов признаков, таких что вклад вносят взаимодействия второго порядка между парами признаков из их декартова произведения. В частности, для матричного разложения $Q$ выглядит так:\n",
"$$Q = \\left\\{(\\{1, \\dots, \\vert U \\vert \\}, \\{ \\vert U \\vert + 1, \\dots, \\vert U \\vert + \\vert I \\vert \\} )\\right\\}.$$\n",
"Или вот ещё иллюстрация. Пусть рассматривается сервис музыкальных рекомендаций и предметы — это треки. В матрицу $X$ можно включить также среднюю оценку трека и идентификатор жанра. Тогда $Q$ может включать в себя любые пары, составленные из следующих групп: идентификатор пользователя, идентификатор трека, оценка, идентификатор жанра. При этом для оценки её матрица будет иметь размер $1 \\times k$, потому что это одиночный вещественный признак, а не совокупность бинарных признаков, получающихся после one-hot кодирования.\n",
"\n",
"Общая формула для предсказаний принимает вид:\n",
"$$\\hat{R_{ij}} = w_0 + \\sum_{l \\in L} w_l X_{rl} + \\sum_{(P_1, P_2) \\in Q} \\sum_{p \\in P_1} \\sum_{q \\in P_2} W^{(P_1, P_2)}_{p\\cdot} (V^{(P_1, P_2)}_{q\\cdot})^T X_{rp} X_{rq},$$\n",
"где вместо одной пары обучаемых матриц $W$ и $V$ этих пар теперь столько, сколько элементов в $Q$ (на что указывает их верхняя индексация этими элементами).\n",
"\n",
"Таким образом, факторизационные машины образуют семейство моделей, сочетающих способность поддерживать разнообразные признаки (как при обучении с учителем на матрице признакового описания) со способностью работать с разреженной матрицей $R$ (как её разложения)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы",
"нейронные_сети"
]
},
"source": [
"## Нейросетевые методы для заполнения кросс-табуляционной матрицы\n",
"\n",
"#### Введение\n",
"\n",
"В этой заметке речь пойдёт о том, как при помощи нейронных сетей можно заполнять пропуски в [кросс-табуляционной матрице](__home_url__/notes/Кросс-табуляционная матрица) $R$. Однако эти же методы легко обобщаются на обучение на [матрице признакового описания](__home_url__/notes/Обучение ранжирующей модели на матрице признакового описания). Дело в том, что нейронные сети являются одним из немногих методов машинного обучения, способных эффективно работать с идентификаторами, а поэтому для них нет нужды ограничиваться кросс-табуляционной матрицей.\n",
"\n",
"#### Нейросетевые разложения с поздним связыванием\n",
"\n",
"Рассмотрим нейронную сеть со следующей [архитектурой](https://dl.acm.org/doi/pdf/10.1145/2959100.2959190):\n",
"* есть два входа:\n",
" - на первый вход подаётся вектор длины $\\vert U \\vert$, являющийся one-hot encoded вектором $i$-го пользователя,\n",
" - на второй вход подаётся вектор длины $\\vert I \\vert$, являющийся one-hot encoded вектором $j$-го предмета;\n",
"* за входным слоем идёт слой получения обучаемого вложения по индексу (embedding lookup):\n",
" - one-hot encoded вектор пользователя преобразуется в непрерывный вектор фиксированной размерности $k$,\n",
" - one-hot encoded вектор предмета преобразуется в непрерывный вектор той же размерности $k$;\n",
"* скалярное произведение этих векторов интерпретируется как $\\hat{R}_{ij}$, оценка $R_{ij}$.\n",
"\n",
"По сути, просто задача поиска [матричного разложения](__home_url__/notes/Матричные разложения и факторизационные машины) вида $R \\approx WV^T$ была переформулирована в терминах нейронных сетей, но содержательно ничего не поменялось.\n",
"\n",
"Однако в такую архитектуру можно добавлять произвольные вещественные и one-hot encoded категориальные признаки. Вся информция о пользователе представляется в виде единого вещественного вектора, являющегося конкатенацией вещественных признаков и обучаемых вложений категориальных признаков (включая идентификатор пользователя). Далее этот вектор прогоняется через сколько-то полносвязных слоёв, а на выходе последнего из них получается векторное представление пользователя размерности $k$. Аналогично вся информация о предмете представляется в виде единого вектора, который тоже прогоняется через сколько-то полносвязных слоёв, на выходе последнего из которых получается векторное представление предмета размерности $k$. Как и ранее, их скалярное произведение становится $\\hat{R}_{ij}$.\n",
"\n",
"Подобную архитектуру называют «двубашенной», потому что есть две отдельные «башни» для пользователя и предмета. А поскольку взаимодействие информации о пользователе с информацией о предмете происходит лишь в скалярном произведении под самый конец, говорят, что используется позднее связывание.\n",
"\n",
"#### Нейросетевые разложения с ранним связыванием\n",
"\n",
"Рассмотрим модификацию предыдущей архитектуры (ради краткости в виде, где из признаков есть только идентификаторы пользователя и предмета):\n",
"* снова есть два входа, принимающих one-hot encoded векторы пользователя и предмета;\n",
"* снова за каждым входом идёт слой получения обучаемого вложения по индексу (embedding lookup), но размерности вложений пользователя и предмета могут отличаться;\n",
"* векторные вложения пользователя и предмета конкатенируются;\n",
"* далее идёт сколько-то полносвязных слоёв;\n",
"* выходом является одно число, интерпретирующееся как $\\hat{R}_{ij}$.\n",
"\n",
"Образно говоря, тут ищется разложение матрицы $R$, где вместо матричного умножения используется операция, задаваемая многослойным перцептроном. Так как информация о пользователе и предмете начинает использоваться совместно ещё в слоях, близких к входным, говорят, что в этой архитектуре применяется раннее связывание.\n",
"\n",
"#### Сравнение раннего и позднего связываний\n",
"\n",
"При позднем связывании финальные вложения пользователей или предметов, получившиеся после прогона через соответствующую «башню», можно рассчитать один раз, а для заполнения матрицы $R$ вычислять лишь скалярные произведения между ними и сами «башни» не использовать. Более того, если интересуют лишь top-$n$ предметов для каждого пользователя (как это бывает при извлечении кандидатов), то на вложениях предметов можно построить kNN-индекс (например, HNSW или ScaNN) и даже полный перебор не делать.\n",
"\n",
"Платой за это является потенциально меньшая выразительная сила, ведь вложения пользователя и предмета теперь взаимодействуют друг с другом лишь под самый конец в скалярном произведении. Впрочем, сказывается ли это на практике — вопрос дискуссионный. С одной стороны, было [показано](https://arxiv.org/pdf/2005.09683.pdf), что многослойным перцептронам сложно выучить скалярное произведение, а то, что они выучивают вместо него, как правило, хуже. Таким образом, второе отличие может даже повышать качество предсказаний. С другой стороны, раннее связывание выбирают чаще, если признаков много, среди них есть недавняя история пользовательских действий, а вместо многослойных перцептронов используются [трансформеры](__home_url__/notes/Трансформер).\n",
"\n",
"#### Очищающий от шума автокодировщик\n",
"\n",
"Ещё один из [подходов](http://users.cecs.anu.edu.au/~u5098633/papers/www15.pdf) предполагает обучение очищающего от шума автокодировщика. В обучающих данных объектами являются пользователи, представленные в виде строк матрицы $R$. Шумом же считается замена каких-либо значений на пропуски (или на плэйсхолдер пропуска, если пропуски не поддерживаются конкретным программным инструментом). Получив на вход строку с искусственно добавленными пропусками, автокодировщик должен вернуть строку без этих пропусков (но с исходно существовавшими пропусками)."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы",
"нейронные_сети",
"трансформеры"
]
},
"source": [
"## Трансформерные модели в рекомендациях\n",
"\n",
"#### BERT4Rec\n",
"\n",
"Задача выдачи рекомендаций на основании последовательности действий (sequential recommendation) ставится как предсказание следующего «предмета», с которым у пользователя будет положительное взаимодействие, исключительно по упорядоченному списку «предметов», с которыми до этого были положительные взаимодействия. Для решения этой задачи в статье [Sun et al., 2019](https://arxiv.org/pdf/1904.06690) модель [BERT](__home_url__/notes/BERT (Bidirectional Encoder Representations from Transformers)) адаптируется под предметную область рекомендательных систем.\n",
"\n",
"В целом, переход от обработки текстов к рекомендациям достаточно прямолинеен. Так, например, вместо токенов используются идентификаторы «предметов», а задача классификации пар предложений отсутствует, так как она не имеет смысла в контексте рекомендаций.\n",
"\n",
"Единственное нетривиальное место связано с задачей восстановления скрытых токенов. По построению BERT является двунаправленной моделью, то есть он способен учитывать информацию о более поздних взаимодействиях при формировании векторного представления текущего «предмета». Чтобы двунаправленность не осталась чисто номинальной и чтобы её потенциал был раскрыт, на этапе предварительного обучения задача восстановления скрытых токенов ставится в том же виде, что и для обработки текстов. Иными словами, токен \\<MASK\\> может возникать в произвольных местах последовательности. Однако в задаче последовательных рекомендаций встречаются только такие последовательности, где токен \\<MASK\\> есть лишь в самом конце. Поэтому в качестве этапа дообучения ещё раз ставится задача восстановления скрытых токенов, но на этот раз всегда скрывается исключительно последний токен.\n",
"\n",
"#### SASRec\n",
"\n",
"Более ранний вариант BERT4Rec описан в статье [Kang et al., 2018](https://arxiv.org/abs/1808.09781) и называется Self-Attentive Sequential Recommender (SASRec). В нём задача восстановления скрытых токенов не нуждается в модификациях, потому что вместо этого модифицированы связи между трансформерными блоками. Модель сделана однонаправленной, то есть $i$-й в истории действий пользователя «предмет» может повлиять на векторное представление $j$-го, только если $i \\le j$.\n",
"\n",
"#### Учёт признаков\n",
"\n",
"Очевидно, что история действий пользователя не описывает его целиком, ведь есть и другие пользовательские признаки. Также есть и признаки «предметов». Чтобы их учитывать, можно ввести нейронную сеть с [двубашенной архитектурой](__home_url__/notes/Нейросетевые методы для заполнения кросс-табуляционной матрицы).\n",
"\n",
"Пользовательская «башня» состоит из трансформерных блоков, где в качестве входов берутся:\n",
"* исторические действия, представленные как сумма трёх векторов размерности $d$:\n",
" - вложение «предмета» (обучаемое или заготовленное заранее на основании его контентных признаков, таких как название, описание, изображение и т.д.),\n",
" - обучаемое вложение типа действия, которое было совершено (клик, заказ и т.п.),\n",
" - вложение позиции в истории действий;\n",
"* любые иные признаки, сгруппированные по векторам размерности $d$, чтобы их можно было обрабатывать в том же трансформере;\n",
"* произвольное вложение \\<CLS\\>-токена.\n",
"\n",
"Выходом пользовательской «башни» является векторное представление \\<CLS\\>-токена.\n",
"\n",
"Для «предметов» же «башня» является многослойным перцептроном, как-либо обрабатывающим их признаки, а её выход имеет размерность $d$. Скалярное произведение этого вектора на выход пользовательской «башни» можно считать оценкой степени соответствия «предмета» пользователю.\n",
"\n",
"#### Индуктивность\n",
"\n",
"Ещё одна точка роста связана с тем, что BERT4Rec и SASRec работают с идентификаторами «предметов». Во-первых, из-за этого они трансдуктивны, то есть не способны ни делать предсказания для новых «предметов», ни учитывать их появление в истории пользователя. Во-вторых, количество обучаемых параметров как минимум пропорционально количеству «предметов», из-за чего для маркетплейсов, видеоплатформ и социальных сетей оно становится слишком большим. Действительно, если есть $l$ «предметов» и для каждого на входе в трансформер есть получение вложения размерности $d$ по его индексу (embedding lookup), то это уже $l \\times d$ обучаемых параметров.\n",
"\n",
"Способы решения этой проблемы таковы:\n",
"* использовать только заранее обученные векторные вложения (но тогда не будет возможности влиять на них),\n",
"* обучать вложения не для «предметов», а для токенов, входящих в их названия; это имеет смысл, если токенов меньше, чем «предметов» — тогда уменьшение количества обучаемых параметров также окажет регуляризационный эффект; и тут есть варианты:\n",
" - в качестве вложения «предмета» взять сумму вложений его токенов, то есть «предмет» рассматривается как «мешок токенов»,\n",
" - каждый токен считать самостоятельным элементом истории, который подаётся в трансформер (может оказаться вычислительно затратным, если история бывает длинной).\n",
"\n",
"#### Графовые нейронные сети\n",
"\n",
"Помимо истории действий текущего пользователя есть история действий всех пользователей с текущим «предметом». Чтобы учитывать и её, позволив похожим пользователям обмениваться информацией друг о друге, можно применить [графовые нейронные сети](__home_url__/tags/графы) к двудольному графу, вершинами которого являются пользователи и «предметы», а рёбрами являются взаимодействия. Трансформеры будут применяться в свёрточных слоях для агрегации вложений соседних вершин."
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": [
"рекомендательные_системы"
]
},
"source": [
"## Разнообразие через DPP (Determinantal Point Processes)\n",
"\n",
"#### Введение\n",
"\n",
"В задаче выдачи рекомендаций ранжирующая модель в том или ином виде предсказывает степень соответствия «предмета» (то есть того, что ранжируется, даже если оно нематериально) пользователю. Если рекомендации сформировать просто по убыванию предсказаний модели, результат может получиться однообразным и избыточным. Это означает, что если положительный отклик на рекомендации будет, то для него было бы достаточно нескольких первых «предметов», а все остальные лишь занимают место, которое можно было бы отдать иным «предметам» на тот случай, когда первые всё-таки окажутся неинтересны пользователю.\n",
"\n",
"Для решения вышеописанной проблемы после ранжирования можно проводить переранжирование. В нём так называемые определительные поточечные процессы (DPP) могут быть использованы, чтобы сбалансировать в выдаче релевантность и разнообразие.\n",
"\n",
"#### Базовые понятия\n",
"\n",
"Поточечным процессом на множестве $\\mathbb{S}$ называют вероятностное распределение на множестве $2^\\mathbb{S}$, то есть множестве подмножеств $\\mathbb{S}$. Положим, что $\\mathbb{S} = \\{1, 2, \\dots, n\\}$. Тогда любой поточечный процесс на $\\mathbb{S}$ является дискретным распределением, задающимся $2^n$ вероятностями каждого из подмножеств.\n",
"\n",
"Рассмотрим некую положительно полуопределённую матрицу $L$ размера $n \\times n$. Для подмножества $Y \\subseteq \\mathbb{S}$ матрицей $L_Y$ назовём матрицу, получающуюся из $L$ оставлением только тех строк и столбцов, индексы которых входят в $Y$. Тогда можно ввести поточечный процесс, параметризованный матрицей $L$ и выглядящий так:\n",
"$$\\mathbb{P}(Y) = \\frac{\\det(L_Y)}{\\sum_{Y^\\prime \\subseteq \\mathbb{S}} \\det(L_{Y^\\prime})} = \\frac{\\det(L_Y)}{\\det(L + I_n)},$$\n",
"где $I_n$ — тождественная матрица размера $n \\times n$, последнее равенство доказывается как теорема 2.1 в обзоре [Kulesza, Taskar, 2013](https://arxiv.org/pdf/1207.6083.pdf), а вероятность любого подмножества неотрицательна в силу положительной полуопределённости матрицы $L$.\n",
"\n",
"Поточечный процесс, заданый вышеописанным образом через матрицу $L$, называется «определительным», что по-английски звучит как Determinantal Point Process.\n",
"\n",
"#### Архитектура\n",
"\n",
"Переранжирование через DPP принимает два входа:\n",
"* предсказания модели $s_i \\in \\mathbb{R}_{\\ge 0}$;\n",
"* векторные представления «предметов» $v_i \\in \\mathbb{R}^l$.\n",
"\n",
"В простейшем случае матрица $L$ может быть построена так:\n",
"$$L_{ij} = (s_i v_i)^T (s_j v_j).$$\n",
"Тут предполагается, что $\\Vert v_i \\Vert_2 = 1$, а косинусная мера близости $v_i^T v_j$ отражает сходство между $i$-м и $j$-м «предметами». Положительная полуопеделённость вытекает из того, что это матрица Грама для векторов $s_i v_i$.\n",
"\n",
"На примере данной $L$ можно увидеть, за счёт чего происходит балансирование между релевантностью и разнообразием. Напомним, что определитель матрицы равен ориентированному объёму $n$-мерного параллелепипеда, натянутого на её строки. С одной стороны, чем выше некое $s_i$, тем больше стороны параллелепипеда, соответствующего $L_Y$, где $i \\in Y$. С другой стороны, чем выше по модулю $v_i^T v_j$, тем более параллельными становятся некоторые прилегающие стороны параллелепипеда, соответствующего $L_Y$, где $\\{i, j\\} \\subseteq Y$.\n",
"\n",
"Если в рамках одного просмотра страницы с рекомендациями пользователь редко имеет более одного положительного отклика, то вышеприведённая матрица $L$ хороша тем, что у неё нет обучаемых параметров. Например, в интернет-магазине пользователь мало когда заказывает сразу несколько товаров, которые ему показали в рекомендациях. Однако бывает и так, что пользователь активно взаимодействует с рекомендациями. Скажем, в приложениях с короткими видео пользователи кликают на значительную часть того, что им предлагается в ленте. Благодаря этому появляется возможность настраивать некоторые параметры матрицы $L$ по данным.\n",
"\n",
"В статье [Wilhelm et al., 2018](https://dl.acm.org/doi/pdf/10.1145/3269206.3272018) предложено семейство матриц $L$, параметризованных величинами $\\alpha > 0$ и $\\sigma > 0$:\n",
"* $L_{ii} = s_i^2$,\n",
"* $L_{ij} = \\alpha \\, s_i s_j \\, \\exp\\left(-\\frac{D_{ij}}{2\\sigma^2}\\right)$ при $i \\ne j$, где $D_{ij} \\in \\mathbb{R}_{\\ge 0}$ — некое расстояние между $v_i$ и $v_j$, как, допустим, $D_{ij} = \\Vert v_i - v_j \\Vert_2$.\n",
"\n",
"При $0 \\le \\alpha \\le 1$ матрица $L$ точно будет положительно полуопределённой, а вот при $\\alpha > 1$ это не гарантировано.\n",
"\n",
"#### Обучение\n",
"\n",
"Объектом в терминологии машинного обучения (то есть не «предметом», а примером из обучающей выборки) считается фактический просмотр пользователем в рекомендациях не менее чем $t$ «предметов», где $t$ — некий порог достаточности данных. Целевой переменной на этом объекте является множество $Y$, состоящее из индексов тех «предметов», с которыми у пользователя были положительные взаимодействия.\n",
"\n",
"Поскольку речь идёт о переранжировании, предполагается, что ранжирующая модель зафиксирована, то есть обучающие данные собирались с использованием той же ранжирующей модели, которая предсказывает $s_i$. В противом случае возникает смещение обучающей выборки. Впрочем, выборка всё равно является смещённой с той точки зрения, что в неё попадают лишь объекты с более высокими $s_i$, ведь низкие $s_i$ препятствуют фактическим просмотрам. Такое смещение можно подправить, если некоторые высокие позиции отдавать случайным «предметам».\n",
"\n",
"Вектор обучаемых параметров (в разобранном ранее примере это $\\alpha$ и $\\sigma$) обозначим за $w$, а матрицу $L$, получающуюся с ним для $j$-го объекта, обозначим за $L(w, j)$ (зависимость от объекта важно подчеркнуть, потому что предсказания $s_i$ для одного и того же «предмета» меняются от объекта к объекту). Эта матрица $L(w, j)$ имеет размер $n \\times n$, где $n$ — количество «предметов», но для «предметов», у которых не было фактического показа, оценки релевантности заменяются на 0.\n",
"\n",
"Поиск оптимального $w$ делается путём максимизации правдоподобия обучающей выборки (как всегда, это эквивалентно минимизации отрицательного логарифма от правдоподобия):\n",
"$$\\min_{w} \\: - \\sum_{j=1}^m \\log \\mathbb{P}_{L(w, j)} Y_j,$$\n",
"где $m$ — размер обучающей выборки, а $Y_j$ — целевая переменная на $j$-м объекте.\n",
"\n",
"Если длина вектора $w$ мала, оптимизацию можно провести перебором по сетке и заодно пересечь эту сетку с ограничениями на допустимые значения параметров. Если же длина вектора $w$ достаточно велика, можно использовать градиентный спуск, а ограничения внести в оптимизационную задачу.\n",
"\n",
"#### Применение\n",
"\n",
"После ранжирования есть список из $n^{\\prime} \\le n$ «предметов» (до ранжирования могли дойти не все «предметы», плюс можно исключить те, которые получили нулевые оценки релевантности). Переранжирование проводится итеративно с некоторым шагом $k$, то есть сначала заполняются позиции с первой по $k$-ю, потом позиции с $(k+1)$-й по $2k$-ю и так далее. Если у матрицы $L$ нет обучаемых параметров, то $k$ формально можно брать любым, но слишком низкие $k$ могут привести к недостаточному разнообразию (в частности, при $k=1$ от переранжирования вообще ничего не изменится), да и слишком большие тоже (при $k=n^{\\prime}$ все «предметы» попадут в топ-$k$). Если же обучаемые параметры есть, то желательно брать $k \\le t$, чтобы корректнее оценивались вероятности подмножеств размера $k$.\n",
"\n",
"Из формулы для вероятности подмножества теперь интересует только числитель, потому что нормирующий знаменатель одинаков для всех подмножеств. Если за $\\mathbb{S}_i$ обозначить множество индексов, для которых «предметы» не были выбраны к началу $i$-й итерации, то на этой итерации будет решаться задача:\n",
"$$\\max_{Y \\in \\mathbb{S}_i, \\vert Y \\vert = k} \\det(L_Y).$$\n",
"Всего потребуется перебрать $C_{n^{\\prime} - (i-1)k}^k$ вариантов, что может оказаться вычислительно неподъёмным. В таких случаях используют жадный алгоритм, итеративно строящий множество $Y$ элемент за элементом на основании максимизации текущего $\\det(L_Y)$. Кстати, порядок, в котором в $Y$ добавлялись элементы, можно считать тем порядком, в котором будут стоять эти $k$ элементов после переранжирования. Если же множество $Y$ было найдено по-честному, порядок внутри него можно по-прежнему выводить из $s_i$."
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.12"
}
},
"nbformat": 4,
"nbformat_minor": 2
}