Mathematical model of the top-N problem for content recommender systems

Abstract

This article discusses content recommender systems which solve the top-N problem. A mathematical model of the content recommender system based on fuzzy sets, the criterion of assessing the quality of recommendations and solution algorithm are presented in the article.

Full Text

Рекомендательная система или сервис (далее РС) - это информационные системы поддержки принятия решений, целью которых является прогноз пользовательских оценок объектов (статьи, книги [1], кинофильмы [2], конкурсные работы и т.п.). Такой прогноз может быть сделан на основании информации о пользователях, объектах и предварительно введенных пользователями оценках. РС могут быть использованы как в коммерческих целях для поиска целевых групп пользователей и продвижения товара в этих группах, так и для организации экспертного оценивания, где РС позволяют существенно снизить нагрузку на экспертов. В статье будут рассматриваться контентные РС [6], которые основаны на анализе информации о характеристиках объекта и пользователя (что и называется контентом), или о том, какие объекты были уже выбраны пользователем. Рассмотрим задачу выделения N объектов с наивысшими прогнозными значениями для каждого пользователя. Такая задача получила название задачи рекоменжации top-N [14]. Во втором разделе производится постановка данной задачи, в третьем разделе описывается математическая модель, в четвертом вводится формальная постановка задачи с алгоритмом ее решения, пятый раздел посвящен практическим результатам. Множество пользователей будем представлять с помощью множества идентификаторов . Множество объектов также будем представлять с помощью множества идентификаторов . Каждому пользователю , задавшему запрос на N рекомендаций, назначается подмножество объектов , где , , - булеан множества . Назовем множество профилем пользователя длины N и обозначим как . Профили не могут формироваться наугад, т.к. каждый пользователь имеет свои предпочтения, а каждый объект - стилистические направленности, и, таким образом, каждый объект соответствует предпочтениям пользователя в какой-то мере. Для определения этой меры будем пользоваться расстоянием между пользователем и объектом . Предположим, что . (1) Множества пар вида , созданных в результате рекомендаций, таких как , назовем распределением Q. Задачу top-N поставим следующим образом: необходимо создать алгоритм, находящий такое распределение Q, что среднее расстояние по Q стремится к минимуму: . (2) Поскольку каждый пользователь имеет свои предпочтения, а объект - стилистические направленности, введем такие множества, элементы которых описывают данную информацию. Введем множество семантик пользователей , , , принимающих значения от 0 до 1 и множество семантик объектов , , , принимающих значения от 0 до 1. . Контент пользователя (или объекта) - это информация о семантиках пользователя (или объекта), которая может быть представлена, к примеру, в векторном виде [5, 6]. Значение семантики представляет степень принадлежности семантики к пользователю или объект, поэтому будем рассматривать контенты как нечеткие множества [17]. Контент пользователя будем представлять в виде нечеткого множества , где множество - универсальное множество, - функция принадлежности элемента контенту; контент объекта - , , где множество - универсальное множество, - функция принадлежности элемента контенту. Также введем две операции: и однозначно сопоставляющие идентификаторам пользователя и объекта их контенты. В дальнейшем нам понадобятся три операции над контентами: 1. Объединение - наименьший контент, содержащий и : , . 2. Пересечение - наибольший контент, содержащийся одновременно в контентах и : , . 3. Два контента и дополняют друг друга ( или ), если: , . Необходимо ввести расстояние между элементами множеств и . Для этого воспользуемся информацией о пользователях и объектах, то есть введем расстояние следующим образом: . (3) Однако множества и имеют разную размерность и являются подмножествами различных универсальных множеств. Поэтому для введения расстояния надо: 1. ввести расстояние между подмножествами множества . 2. ввести отображение такое, что , . Введем расстояние на множестве между элементами , такое, что оно удовлетворяет следующим свойствам: • , если • выполнение условия необязательно • • (неравенство треугольника). Зададим расстояние следующим образом: , где - любая псевдометрическая функция. Введем расстояние на множестве между его элементами и : , , (4) Отображение будем строить на основании информации о контентах: , где . Отображение является нечетким отображением, так как не всегда можно четко определить отношения между предпочтениями пользователя и стилистическими направленностями объекта. Таким образом, контента при нечетком отображении называется контент с функцией принадлежности . Cвойства функции : • - отображение выпуклой оболочки. Следует из определения объединения контентов (минимальный контент, содержащий оба контента): • . Значения функции определяются функцией , так как значения известны (это данные о пользователе). Данная функция может быть задана таблично экспертом. Также функция может быть выведена из исходных данных: установленных зависимостей между харатеристиками пользователей и объектов путем сбора известной информации о том, какие объекты пользователь уже предпочел. Назовем единичным контентом такой контент, значения функции принадлежности которого равны нулю для всех его элементов, кроме одного: , Определим исходные данные как множество единичных контентов. Остальные контенты можно выразить с помощью объединения/пересечения элементов исходных данных. В случае, когда мы располагаем только историей выбора объектов пользователями, не имея исходных данных, их можно получить путем комбинации данных истории и операции пересечения. Но для этого нужно располагать объемной историей, чтобы можно было получить необходимые единичные контенты. Мы ввели способ построения расстояния между пользователем и объектом , реализуемый в 2 шага: 1. построение расстояния на множестве объектов; 2. построение расстояния между пользователем и объектом с использованием функции отображения , т.е. расчет расстояния между подмножеством и объектом [4]. Приведем пример с известной функцией расстояния из информационного поиска - косинус угла между векторами [17]: 1. ; 2. , . Лемма: Если существует мера сходства и отображение , то можно определить функцию расстояния [3]. , (5) причем, если является псевдометрикой, то будет также псевдометрикой. Если отображение не введено, то всегда можно ввести тождественное преобразование. Критерием задачи top-N является значение среднего расстояния по распределению. В терминах, введенных в вышеописанных разделах, формально задачу можно записать так: , (6) где: • - обозначение критерия; • - распределение; • - количество объектов, рекомендованных пользователю . Обозначим решение задачи . Задачей top-N назовем нахождение такого распределения . Зачастую в качестве решения задачи top-N используются следующие критерии: • точность[10, 13]; • полнота[9, 12]; • [9, 12]; • [9, 18]; • [9, 12, 13, 18]; • точность для объектов [6, 10, 19]. Утверждение: Если выполняются условия леммы и решение задачи top-N было получено на основе использования расстояния между пользователем и объектом, то критерий такого решения является частным случаем критерия . Данное утверждение следует из основного свойства критериев: все они монотонно зависят от значения функции расстояния между пользователем и объектом. Так как алгоритм решения данной задачи не может быть найден аналитически, то алгоритм решения был построен на основе метода имитации отжига [4]. Обозначения и определения, принятые в алгоритме: • - выбор случайного распределения; • - выбор случайного числа в интервале ; • - выбор соседнего распределения. Соседним распределением к распределению назовем такое распределение, которое отличается от одним элементом одного профиля, сохраняя длину профиля: • return - результатом работы алгоритма является распределение ; • соседним распределением к распределению назовем такое распределение, которое отличается от одним элементом одного профиля, сохраняя длину профиля. Алгоритм представляет собой стохастическую модификацию алгоритма спуска, в котором переход на каждом шаге является достоверным, если новое положение лучше предыдущего, и случайным в противном случае. Вероятность случайного перехода в худшее положение убывает в течение времени. Пошаговое описание алгоритма: 1. Инициализация a. ; b. : случайным образом выбираем исходное распределение; c. : фиксируем точность алгоритма; d. Присваиваем коэффициентам и начальные значения, в данном алгоритме характеризует интенсивность движения при ухудшении положения, - скорость уменьшения . 2. Вычисление a. ; b. Вычисляем . 3. Переходы a. Если то переходим к шагу 4; b. Иначе: Если то : поскольку мы ищем минимальное значение критерия , то при уменьшении значения критерия переход к новому распределению является достоверным; c. Иначе: Если , то : при увеличении значения критерия переход к новому распределению звисит от реализации случайной величины . d. ; перейти к шагу 2; 4. Вывод результатов a. Выводим значение распределения , алгоритм завершает работу. Для оценки приведенного метода за основу были взяты исследования, опубликованные в статье [5]. В данной статье рассматривается задача рекомендации top-N, которая решается на базе семи различных моделей РС, основанных на семи различных мерах сходства(для данной статьи были взяты четыре меры сходства). Результаты решения сравниваются на основании оценочных мер, которые будут приведены ниже. Для сравнения данные модели тестировались на базе данных LastFm по следующей методологии: создавались обучающие выборки, содержащие 80% от профиля каждого пользователя (где профиль - это множество объектов, уже выбранных пользователем), остальные 20% считались закрытыми данными, используемыми для тестирования моделей. Ниже в таблице приведены опубликованные в [5] результаты тестов по базе данных LastFm: Таблица 1 Результаты исследований статьи на данных LastFm [5] Мера сходства P@5 P@10 P@20 MAP NDCG Tf 0.028 0.021 0.014 0.011 0.085 Cos 0.234 0.109 0.059 0.041 0.202 Tf-idf 0.292 0.221 0.144 0.115 0.350 Bm25 0.226 0.105 0.075 0.051 0.216 Приведенные в [5] меры сходства рассматривались в терминах данной статьи в качестве и использовалось тождественное преобразование . Задачи решалась с помощью алгоритма, описанного выше. Таблица 2 Результаты работы SAACT на данных LastFm Мера сходства P@5 P@10 P@20 MAP NDCG Tf 0.572 0.562 0.532 0.428 0.580 Cos 0.384 0.384 0.354 0.265 0.469 Tf-idf 0.314 0.276 0.208 0.170 0.370 Bm25 0.252 0.228 0.206 0.080 0.296