1632
правки
Изменения
м
Пользовательские оценкиДанные, необходимые для составления матрицы предпочтенийсообщающие предпочтения пользователя, можно получить двумя способами:
[[Файл:2.png|300px|thumb|right|Визуализация градиентного спуска.]]
<tex> J(\Theta) = \sum_{(u,i) \in D}{(r^T_u - r_{ui})^2} + \lambda (\sum_u{||p_u||^2} + \sum_i{||q_i||^2}) </tex>Чтобы найти оптимальные параметры построенной модели необходимо оптимизировать следующий функционал:
Необходимо оптимизировать данный функционал. Множество параметров: для каждого объекта и пользователя есть свой вектор<tex> J(\Theta) = \sum_{(u, который нужно оптимизировать. Дабы найти минимум функции воспользуемся градиентом i) \in D}{(p^T_uq_i - r_{ui})^2} + \lambda (\sum_u{---||p_u||^2}+ \sum_i{||q_i||^2} вектор из частных производных по каждому параметру) </tex>.
<tex> \nabla J(\Theta) = (\dfrac{\partial J}Множество параметров: для каждого объекта и пользователя есть свой вектор, который нужно оптимизировать. Чтобы найти минимум функции можно использовать [[ Стохастический градиентный спуск | метод градиентного спуска]]. Для этого нам понадобится градиент {\partial \theta_1}, \dfrac{\partial J---}{\partial \theta_2}вектор из частных производных по каждому параметру,\dots,\dfrac{\partial J}{\partial \theta_n})^T </tex>который в нашем случае будет выглядеть так:
Можно воспользоваться градиентным бустингом:<tex> \nabla J(\Theta) = (\dfrac{\partial J}{\partial \theta_1}, \dfrac{\partial J}{\partial \theta_2},\dots,\dfrac{\partial J}{\partial \theta_n})^T </tex>.
Было предложено измерять Зачастую качество рекомендаций при помощи измеряется с помощью функции ошибки [[ Оценка_качества_в_задачах_классификации_и_регрессии#.D0.9A.D0.BE.D1.80.D0.B5.D0.BD.D1.8C_.D0.B8.D0.B7_.D1.81.D1.80.D0.B5.D0.B4.D0.BD.D0.B5.D0.B9_.D0.BA.D0.B2.D0.B0.D0.B4.D1.80.D0.B0.D1.82.D0.B8.D1.87.D0.BD.D0.BE.D0.B9_.D0.BE.D1.88.D0.B8.D0.B1.D0.BA.D0.B8_.28.D0.B0.D0.BD.D0.B3.D0.BB._Root_Mean_Squared_Error.2C_RMSE.29 | RMSE]]:
rollbackEdits.php mass rollback
== Обзор и постановка задачи ==
Основная задача рекомендательных систем <ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D0%BE%D0%BC%D0%B5%D0%BD%D0%B4%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0 Рекомендательные системы]</ref> {{---}} проинформировать пользователя о товарах или услугах, которые будут для него наиболее интересными и актуальными. Разнообразие таких систем можно проиллюстрировать основными характеристиками:
* предмет рекомендации;
* прозрачность рекомендации.
В центре таких систем лежит матрица предпочтений. В этой матрице одна из осей отвечает за пользователей, вторая за объекты рекомендации. Заполнена же эта матрица значениями по заданной шкале (например от <tex>1</tex> до <tex>5</tex>). Каждый клиент с малой долей вероятности оценивал все объекты рекомендацииТак как каждый пользователь обычно может оценить только небольшую часть объектов, поэтому задача то данная матрица очень разрежена. Задача системы {{---}} это обобщение информации и предсказание: какое отношение отношения пользователя к рекомендуемому объекту будет у пользователя(заполнение пропущенных значений матрицы).
* явно (англ. ''explicit feedback'', ''explicit ratings'');* неявно (англ. ''implicit feedback'', ''implicit ratings'').
При явном оценивании пользователь сам показывает, насколько ему интересно интересен тот или иной объект. Типичным примером данных, полученных при явном оценивании, являются рейтинги, проставленные пользователями объектам. На практике таких данных обычно мало.
Гораздо больше имеется информации о неявных предпочтениях пользователя: просмотры, клики, добавления в закладки. Однако по таким данным не всегда можно сделать явный вывод об отношении пользователя к объекту. Например, если пользователь посмотрел фильм, то это означает, что до просмотра он ему был интересен, но сделать вывод о том, понравился ли ему фильм, нельзя.
В большинстве рекомендательных систем эти два подхода используются вместе, тем самым минимизируются недостатки каждого из них в отдельности.
Формализуем задачу. Имеется множество пользователей <tex> u \in U </tex>, множество объектов <tex> i \in I </tex> и множество событий <tex> (r_{ui}, u, i,\dots) \in D </tex> (действия, которые совершают пользователи с объектами). Каждое событие задается пользователем <tex> u </tex>, объектом <tex> i </tex>, своим результатом <tex> r_{ui} </tex> и, возможно, но не обязательно, другими характеристиками. По итогу от рекомендательной системы требуется:
'''Первый способ.''' Предлагается показывать не среднее значение, а сглаженное среднее (англ. ''damped mean''). Смысл таков: при малом количестве оценок отображаемый рейтинг больше тяготеет к некому безопасному «среднему» показателю, а как только набирается достаточное количество новых оценок, «усредняющая» корректировка перестает действовать.
'''Второй способ.''' Для объекта считается средний рейтинг, затем определяется доверительный интервал достоверности (англ. ''сonfidence interval'') этого рейтинга. Математически, чем больше оценок, тем меньше вариация среднего и, значит, больше уверенность в его корректности. А в качестве рейтинга объекта можно выводить, например, нижнюю границу интервала (англ. ''low CI bound''). При этом понятно, что такая система будет достаточно консервативной, с тенденцией к занижению оценок по новым товарамобъектам.
== User-based и item-based алгоритмы ==
=== User-based алгоритм ===
Заменим жесткую кластеризацию на предположение, что объект понравится пользователю, если он понравился его друзьямпохожим пользователям.Тогда предпочтение пользователя <tex>u</tex> к объекту <tex>i</tex> можно записать следующим образом:
<tex> \hat{r}_{ui} = \bar{r}_u + \dfrac{\sum_{v \in U_i}{}{sim(u, v)(r_{vi} - \bar{r}_v)}}{\sum_{v \in {U_i}}{}{sim(u, v)}} </tex>, где <tex>\bar{r}_u</tex> {{---}} средняя оценка, проставленная пользователем <tex> u </tex>, а <tex> sim(u,v) </tex> {{---}} мера схожести пользователей <tex>u</tex> и <tex>v</tex>.
Однако у этого алгоритма есть недостатки:
=== Item-based алгоритм ===
Также имеется абсолютно симметричный алгоритм. Теперь будем считать, что объект понравится пользователю, если ему понравились похожие объекты.Предпочтение пользователя <tex>u</tex> к объекту <tex>i</tex> запишется так:
<tex> \hat{r}_{ui} = \bar{r}_i + \dfrac{\sum_{j \in I_u}{}{sim(i, j)(r_{uj} - \bar{r}_j)}}{\sum_{j \in {I_u}}{}{sim(i, j)}} </tex>, где <tex>\bar{r}_i</tex> {{---}} средняя оценка, проставленная объекту <tex> i </tex>, а <tex> sim(i, j) </tex> {{---}} мера схожести объектов <tex>i</tex> и <tex>j</tex>.
У такого подхода остается недостаток в виде холодного старта и при этом рекомендации становятся тривиальными.
Применяя усеченное разложение, получим следующее:
<tex> R'_{n \times m} = U'_{n \times d} \times \Sigma '_{d \times d} \times V'^T_{d \times m} </tex>.
Из свойств сингулярного разложения мы знаем, что матрица <tex> R'_{n \times m} </tex> является наилучшим низкоранговым приближением с точки зрения средне-квадратичного отклонения. Несколько упростим запись выражения: запишем произведение первых двух матриц <tex> \tilde{U}_{n \times d} = U'_{n \times d} \times \Sigma '_{d \times d} </tex>, а матрицу <tex> V'^T_{d \times m} </tex> обозначим как <tex> \tilde{V}_{d \times m} </tex>. Получим формулу <tex> R'_{n \times m} = \tilde{U}_{n \times d} \times \tilde{V}_{d \times m} </tex>. Интерпретировать полученную формулу стоит следующим образом: приближенная матрица оценок может быть вычислена как произведение усеченных матриц пользователей и оценок.
Благодаря использованию такого усечения можно решить одну из главных проблем всех ранее упомянутых алгоритмов: ресурсоемкость вычислений.
[[Файл:3RecommendSVD.png|400px450px|thumb|right|SVD для рекомендательных систем.]]
Чтобы предсказать оценку пользователя <tex> u </tex> для объекта <tex> i </tex>, берём некоторый вектор <tex> p_u </tex> для данного пользователя и вектор данного объекта <tex> q_i </tex>. Получаем необходимое предсказание: <tex> \hat{r}_{ui} = \langle p_u,q_i \rangle </tex>.
Для решения проблем, связанных с матрицей оценок <tex>R</tex>, будем строить некоторую построим модель.
Модель будет зависеть от следующих параметров: вектор пользователей и вектор объектов. Для заданных параметров <tex> u </tex> и <tex>v i</tex> возьмем вектор пользователя <tex> p_u </tex> и вектор объекта <tex>q_i</tex>, а затем для предсказания оценки получим их скалярное произведение, как и в алгоритме SVD:
<tex> \hat{r}_{ui}(\Theta) = p^T_uq_i </tex>, где <tex> \Theta = \{p_u, q_i \mid u \in U, i \in I\} </tex>.
Но вектора пока не известны, их нужно получить. Имеются оценки пользователей, при помощи которых можно найти оптимальные параметры, при которых модель предскажет оценки наилучшим образом:
<tex> E_{(u,i)}(\hat{r}_{ui}(\Theta) - r_{ui})^2 \to min_{\Theta} </tex>.
То есть, нужно найти такие параметры <tex> \Theta </tex>, чтобы квадрат ошибки был наименьшим. Однако ситуация следующая: оптимизация приведет к наименьшим ошибкам в будущем, но как именно оценки будут спрашивать {{---}} неизвестно. Следовательно, это нельзя оптимизировать. Однако, так как оценки, уже проставленные пользователями, известны, постараемся минимизировать ошибку на тех данных, что у нас уже есть. Также воспользуемся [[Регуляризация | регуляризацией]]. В качестве регуляризатора будет выступать слагаемое <tex>\lambda \sum_{\theta \in \Theta}{\theta^2}</tex>. Получим следующее:
<tex> \sum_{(u,i) \in D}{(\hat{r}_{ui}(\Theta) - r_{ui})^2} + \lambda \sum_{\theta \in \Theta}{\theta^2} \to min_{\Theta} </tex>.
==Численная оптимизация==
Шаг градиентного спуска можно записать следующим образом: <tex> \Theta_{t+1} = \Theta_t - \eta \nabla J(\Theta) </tex> Проблема же заключается в том, что алгоритм работает медленно, а минимумы которые он находит где <tex> \eta </tex> {{---}} локальные, а не глобальныекоэффициент скорости обучения.
==Измерение качества рекомендаций==
<tex> RMSE = \sqrt{\dfrac{1}{|D|} \sum_{(u,i) \in D}{(\hat{r}_{ui} - r_{ui})^2}} </tex>.
Данный способ, хоть и является стандартным для измерением качества, имеет ряд недостатков:
* [[Оценка качества в задаче кластеризации]]
* [[Оценка качества в задачах классификации и регрессии]]
== Примечания ==<references/>
== Источники информации==
* [https://habr.com/ru/company/yandex/blog/241455/ Как работают рекомендательные системы.]
[[Категория: Машинное обучение]]
[[Категория: Рекомендательные системы]]
