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

Рекомендательные системы - программы, которые пытаются предсказать, какие объекты будут интересны пользователю, имея определенную информацию о его профиле.

Обзор и постановка задачи

Основная задача рекомендательных систем - проинформировать пользователя о товаре или услуге, которая будет для него наиболее инетерсной и акутальной. Разнообразие таких систем можно проиллюстрировать основными характеристиками:

• Предмет рекомендации.
• Цель рекомендации.
• Контекст рекомендации.
• Источник рекомендации.
• Степень персонализации.
• Прозрачность.
• Формат рекомендации.
• Алгоритмы.

В центре таких систем лежит матрица предпочтений. В этой матрице одна из осей отвечает за пользователей, вторая за обхекты рекомендации. Заполнена же эта матрица значениями по заданной шкале (например от 1 до 5). Каждый клиент с малой долей вероятностью оценивал все объекты рекомендации, поэтому задача системы - это обобщение информации и предсказание, какое отношение к рекомендуемому обхекту будет у пользователя.

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

• явно (explicit ratings)
• неявно (implicit ratings)

Очевидно, что явное оценивание лучше, так как сам пользователь определяет насколько ему интересен тот или иной объект, однако из-за непостоянства в получении явных оценок от пользователей, на практике используется оба подхода.

Формализуем задачу. Имеется множество пользователей [math] u \in U [/math], множество объектов [math] i \in I [/math] и множество событий [math] (r_{ui}, u, i, ...) \in D [/math] (действия, которые совершают пользователи с объектами). Каждое событие задается пользователем [math] u [/math], объектом [math] i [/math], своим результатом [math] r_{ui} [/math] и, возможно, но не обяхательно, другими харакетристиками. По итогу требуется:

• предсказать предпочтение: [math] \hat{r_{ui}} = Predict(u, i, ...) \approx r_{ui} [/math]
• персональные рекомендации: [math] u \mapsto (i_1, ..., i_k) = Recommend_k(u, ...) [/math]
• похожие объекты: [math] u \mapsto (i_1, ..., i_M) = Similar_M(i) [/math]

Кластеризация пользователей

Определение:

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

Основная идея метода - похожим пользователям нравятся похожие объекты.

Алгоритм можно разбить на следующие шаги:

• Выберем условную меру схожести пользователей по истории их оценок [math] sim(u, v) [/math]
• Объеденим пользователей в группы так, чтобы похожие пользователи оказывались в одном кластере [math] u \mapsto F(u) [/math]
• Оценку пользователя предскажем как среднюю оценку кластера этому объекту [math] \hat{r_{ui}} = \frac{1}{|F(u)|}\sum_{u \in F(u)}{}{r_{ui}} [/math]

Проблемы алгоритма:

• Нечего рекомендовать новым пользователям, их невозможно определить к какому-нибудь кластеру,а значит и рекомендовать им нечего.
• Не учитывается контекст и специфика пользователя.
• Если в кластере нет оценки объекта, то предсказание невозможно.

User-based и item-based алгоритмы

Заменим жесткую кластеризацию на предположение, что фильм понравится пользователю, если он понравился его друзьям.

[math] \hat{r_{ui}} = \bar{r_u} + \frac{\sum_{v \in U_i}{}{sim(u, v)(r_{vi} - \bar{r_v})}}{\sum_{v \in {U_i}}{}{sim(u, v)}} [/math]

Однако у этого алгоритма есть недостатки:

• Холодный старт.
• Нечего рекомендовать новым/нетипичным пользователям.

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

[math] \hat{r_{ui}} = \bar{r_i} + \frac{\sum_{j \in I_u}{}{sim(i, j)(r_{uj} - \bar{r_j})}}{\sum_{j \in {I_u}}{}{sim(i, j)}} [/math]

У такого подхода остается недостаток в виде холодного старта и при этом рекомендации становятся тривиальными.

Так же стоит отметить ресурсоемкость вычислений такими методами. Для предсказаний необходимо держать в памяти все оценки всех пользователей.

Алгоритм SVD

Определение:

SVD (Single Value Decomposition) — у любой матрицы [math] A [/math] размера [math] n \times m [/math] существует разложение трех матриц: [math] U, \Sigma, V^T [/math]. Матрицы [math] U, V [/math] ортогональные, а [math] \Sigma [/math] - диагональная. [math] A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} [/math]

[math] UU^T = I_n[/math], [math]VV^T = I_m[/math]

[math] \Sigma = diag(\lambda_1, ..., \lambda_{min(n, m)})[/math], [math]\lambda_1 \geq ... \geq \lambda_{min(n, m)} \geq 0 [/math]

Обратить внимание же стоит на усеченное разложение, когда из лямбд, остаются только первые [math] d [/math] чисел, а остальные полагаем, что равны нулю.

[math] \lambda_{d+1}, ..., \lambda_{min(n,m)} := 0 [/math]

Значит у матриц [math] U [/math] и [math] V [/math] остаются только первые [math] d [/math] столбцов, а матрица [math] \Sigma [/math] становится квадратной размером [math] d \times d [/math].

[math] A'_{n \times m} = U'_{n \times d} \times \Sigma'_{d \times d} \times V'^T_{d \times m} [/math]

Получаем наилучшее низкоранговое приближение с точки зрения средне-квадратичного отклонения.

Чтобы предсказать оценку пользователя [math] U [/math] для объекта [math] I [/math], берём некотрый вектор [math] p_u [/math] для данного пользователя и вектор данного объекта [math] q_i [/math]. Получаем необходимое предсказание: [math] \hat{r_{ui}} = \langle p_u,q_i \rangle [/math].

Помимо предсказания оценок, алгоритм позволяет выявлять скрытые признаки объектов и интересы пользователей.

Одна есть и свои проблемы:

• [math] R [/math] матрица оценок полностью не известна, поэтому просто взять SVD разложение не получится.
• SVD разложение не единственное, поэтому даже если какое-то разложение будет найдено, нет гарантии, что первая координата в нем будет соответствовать некоторым выбранным характеристикам пользователя.

Решение проблемы матрицы оценок

Модель будет зависить от ногих параметров - вектора пользователей и вектора объектов. Для заданных парметров, возьмем вектор пользователя, вектор объекта и получим их скалярное произведение, чтобы предсказать оценку:

[math] \hat{r_{ui}}(\Theta) = p^T_uq_i [/math],

[math] \Theta = {p_u,q_i | u \in U, i \in I} [/math]

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

[math] E_{(u,i)}(\hat{r_{ui}}(\Theta) - r_{ui})^2 \to min_{\Theta} [/math]

То есть, нужно найти такие параметры [math] \Theta [/math], чтобы квадрат ошибки был наименьшим. Однако ситуация следующая: оптимизация приведет к наименьшим ошибкам в будущем, но как именно оценки будут спрашивать - неизвестно. Следовательно, это нельзя оптимизировать. Однако, так как оценки уже проставленные пользователями известны, постараемся минимизировать ошибку на тех данных, что у нас уже есть. Так же добавим регуляризатор.

[math] \sum_{(u,i) \in D}{(\hat{r_{ui}}(\Theta) - r_{ui})^2} + \lambda \sum_{\theta \in \Theta}{\theta^2} \to min_{\Theta} [/math]

Определение:

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

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

Численная оптимизация

[math] J(\Theta) = \sum_{(u,i) \in D}{(r^T_u - r_{ui})^2} + \lambda (\sum_u{||p_u||^2} + \sum_i{||q_i||^2}) [/math]

Необходимо оптимизировать данный функционал. Множество параметров: для каждого объекта и пользователя есть свой вектор, который нужно оптимизировать. Дабы найти минимум функции воспользуемся градиентом - вектор из частных производных по каждомц параметру.

[math] \nabla J(\Theta) = (\frac{\partial J}{\partial \theta_1}, \frac{\partial J}{\partial \theta_2},...,\frac{\partial J}{\partial \theta_n})^T [/math]

Можно воспользоваться градиентным бустингом:

[math] \Theta_{t+1} = \Theta_t - \eta \nabla J(\Theta) [/math]

Проблема же заключается в том, что алгоритм работает медленно, а минимумы которые он находит - локальные, а не глобальные.

Измерение качества реомендаций

Было предложено измерять качество рекомендаций при помощи RMSE:

[math] RMSE = \sqrt{\frac{1}{|D|} \sum_{(u,i) \in D}{(\hat{r_{ui}} - r_{ui})^2}} [/math]

Однако она также обладает недостатками, хоть и является стандартом измерения качества:

• Пользователи с большим разбросом оценок будут влиять на значение метрики больше, чем остальные.
• Ошибка в предсказании высокой оценки имеет такой же вес, что и ошибка в предсказании низкой оценки.
• Есть риск плохого ранжирования при почти идельаной RMSE и наоборот.

Существуют при этом и другие метрики - метрики ранжирования, на основе полноты и точности. Однако они не так популярны и используются значительно реже.