1632
правки
Изменения
м
Пользовательские оценкиДанные, необходимые для составления матрицы предпочтенийсообщающие предпочтения пользователя, можно получить двумя способами:
Очевидно, что явное оценивание лучшеПри явном оценивании пользователь сам показывает, так как сам пользователь определяет насколько ему интересен тот или иной объект. Типичным примером данных, однако из-за непостоянства полученных при явном оценивании, являются рейтинги, проставленные пользователями объектам. На практике таких данных обычно мало.Гораздо больше имеется информации о неявных предпочтениях пользователя: просмотры, клики, добавления в получении явных оценок от пользователейзакладки. Однако по таким данным не всегда можно сделать явный вывод об отношении пользователя к объекту. Например, если пользователь посмотрел фильм, то это означает, на практике используется оба что до просмотра он ему был интересен, но сделать вывод о том, понравился ли ему фильм, нельзя.В большинстве рекомендательных систем эти два подходаиспользуются вместе, тем самым минимизируются недостатки каждого из них в отдельности.
* Выберем условную меру # Выбор условной меры схожести пользователей по истории их оценок <tex> sim(u, v) </tex>.* Объеденим # Объединение пользователей в группы (кластеры) так, чтобы похожие пользователи оказывались в одном кластере <tex> u \mapsto F(u) </tex>.* Оценку # Предсказание оценки пользователя предскажем как среднюю оценку : средняя оценка кластера этому объекту <tex> \hat{r_r}_{ui}} = \fracdfrac{1}{|F(u)|}\sum_{u \in F(u)}{}{r_{ui}} </tex>.
Данная проблема актуальна для новых объектов или объектов'''Первый способ.''' Предлагается показывать не среднее значение, которые редко покупаюта сглаженное среднее (англ. Если средний ''damped mean''). Смысл таков: при малом количестве оценок отображаемый рейтинг посчитан по оценкам всего трёх пользователейбольше тяготеет к некому безопасному «среднему» показателю, такая оценка явно не будет достовернойа как только набирается достаточное количество новых оценок, и пользователи это понимают. Часто в таких ситуациях рейтинги искусственно корректируют«усредняющая» корректировка перестает действовать.
Первый '''Второй способ – показывать не среднее значение, а сглаженное среднее (.''Damped Mean''). Смысл таков: при малом количестве оценок отображаемый Для объекта считается средний рейтинг больше тяготеет к некому безопасному «среднему» показателю, а как только набирается достаточное количество новых оценок, «усредняющая» корректировка перестает действоватьзатем определяется доверительный интервал(англ. Другой подход – рассчитывать по каждому рейтингу интервалы достоверности (''Confidence Intervalsсonfidence interval'')этого рейтинга. Математически, чем больше оценок, тем меньше вариация среднего и, значит, больше уверенность в его корректности. А в качестве рейтинга объекта можно выводить, например, нижнюю границу интервала (англ. ''Low low CI Boundbound''). При этом понятно, что такая система будет достаточно консервативной, с тенденцией к занижению оценок по новым товарамобъектам.
Так же === Item-based алгоритм ===Также имеется абсолютно симметричный алгоритм. Теперь будем считать, что фильм объект понравится пользователю, если ему понравились похожие фильмыобъекты.Предпочтение пользователя <tex>u</tex> к объекту <tex>i</tex> запишется так:
Так же стоит Cтоит отметить , что ресурсоемкость вычислений такими методами. Для высока: для предсказаний необходимо держать в памяти все оценки всех пользователей.
{{ОпределениеПопробуем воспользоваться [[Сингулярное разложение |definition='''сингулярным разложением (SVD''' (''Single Value Decomposition'') {{---}} у любой матрицы <tex> A </tex> размера <tex> n \times m </tex> существует разложение трех матриц: <tex> U, \Sigma, V^T </tex>. Матрицы <tex> U, V </tex> ортогональные, а <tex> \Sigma </tex> - диагональная. <tex> A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} </tex> }} <tex> UU^T = I_n</tex>, <tex>VV^T = I_m</tex> <tex> \Sigma = diag(\lambda_1, ..., \lambda_{min(n, m)})</tex>, <tex>\lambda_1 \geq ... \geq \lambda_{min(n, m)} \geq 0 </tex> Обратить внимание же стоит на усеченное разложение, когда из лямбд, остаются только первые <tex> d </tex> чисел, а остальные полагаем, что равны нулю. <tex> \lambda_{d+1}, ..]] для задачи рекомендации., \lambda_{min(n,m)} := 0 </tex>
Значит у матриц Разложим матрицу оценок <tex> U R </tex> и с использованием сингулярного разложения: <tex> R_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V ^T_{m \times m} </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>. Интерпретировать полученную формулу стоит следующим образом: приближенная матрица оценок может быть вычислена как произведение усеченных матриц пользователей и оценок.
<tex> A'_{n \times m} = U'_{n \times d} \times \Sigma'_{d \times d} \times V'^T_{d \times m} </tex>Благодаря использованию такого усечения можно решить одну из главных проблем всех ранее упомянутых алгоритмов: ресурсоемкость вычислений.
Получаем наилучшее низкоранговое приближение с точки зрения средне-квадратичного отклонения[[Файл:RecommendSVD.png|450px|thumb|right|SVD для рекомендательных систем.]]
Одна есть и свои проблемыОднако данный алгоритм имеет ряд проблем: *матрица оценок <tex> R </tex> матрица оценок полностью не известна, поэтому просто взять SVD разложение не получится.представляется возможным;*SVD Сингулярное разложение не единственное, поэтому даже если какое-то разложение будет найдено, нет гарантии, что первая координата в нем будет соответствовать некоторым выбранным характеристикам пользователя.
Модель будет зависить от ногих параметров - вектора пользователей и вектора объектов. Для заданных парметров, возьмем вектор пользователя, вектор объекта и получим их скалярное произведение, чтобы предсказать оценку:
<tex> \hat{r_{ui}}(\Theta) = p^T_uq_i </tex>,
<tex> \Theta = {p_u,q_i | u \in U, i \in I} </tex>
Но вектора пока не известны, их нужно получить. Имеются оценки пользователей, при помощи которых можно можно найти оптимальные параметры, при которых модель предскажет оценки наилучших образом:
<tex> E_{(u,i)}(\hat{r_{ui}}(\Theta) - r_{ui})^2 \to min_{\Theta} </tex>
То естьДля решения проблем, нужно найти такие параметры связанных с матрицей оценок <tex> \Theta R</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> 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) = (\frac{\partial J}{\partial \theta_1}, \frac{\partial J}{\partial \theta_2}Множество параметров: для каждого объекта и пользователя есть свой вектор,который нужно оптимизировать.Чтобы найти минимум функции можно использовать [[ Стохастический градиентный спуск | метод градиентного спуска]]..,\fracДля этого нам понадобится градиент {{\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]]:
Было предложено измерять качество рекомендаций при помощи <tex> RMSE:= \sqrt{\dfrac{1}{|D|} \sum_{(u,i) \in D}{(\hat{r}_{ui} - r_{ui})^2}} </tex>.
<tex> Данный способ, хоть и является стандартным для измерением качества, имеет ряд недостатков:* пользователи с большим разбросом оценок будут влиять на значение метрики больше, чем остальные;* ошибка в предсказании высокой оценки имеет такой же вес, что и ошибка в предсказании низкой оценки;* есть риск плохого ранжирования при почти идеальной RMSE = \sqrt{\frac{1}{|D|} \sum_{(u,i) \in D}{(\hat{r_{ui}} - r_{ui})^2}} </tex>и наоборот.
Существуют при этом и другие метрики - метрики ранжирования, на основе полноты и точности. Однако они не так популярны и используются значительно реже.[[Категория: Машинное обучение]][[Категория: Рекомендательные системы]]
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> и, возможно, но не обяхательнообязательно, другими харакетристикамихарактеристиками. По итогу от рекомендательной системы требуется:
* предсказать предсказывать предпочтениепользователя <tex> u </tex> к объекту <tex> i </tex>: <tex> \hat{r_r}_{ui}} = Predict(u, i, ...\dots) \approx r_{ui} ; </tex>* выдавать персональные рекомендациидля пользователя <tex> u </tex>: <tex> Recommend_k(u ,\mapsto dots) = (i_1, ...\dots, i_k) = Recommend_k(u, ...) ; </tex>* определять объекты, похожие объектына объект <tex>i</tex>: <tex> u \mapsto Similar_M(i) = (i_1, ...\dots, i_M) = Similar_M(i) . </tex>
==Кластеризация пользователей==
{{Определение
|definition=
'''Коллаборативная фильтрация''' (англ. ''collaborative filtering'') {{---}} это один из методов построения прогнозов (рекомендаций) в рекомендательных системах, использующий известные предпочтения (оценки) группы пользователей для прогнозирования неизвестных предпочтений другого пользователя.
}}
Основная идея метода {{- --}} похожим пользователям нравятся похожие объекты.
Алгоритм можно разбить на следующие шаги:
Проблемы алгоритма:
* Нечего нечего рекомендовать новым пользователям, так как их невозможно определить отнести к какому-нибудь либо кластеру,а значит и рекомендовать им нечего.;* Не не учитывается контекст и специфика пользователя.;* Если если в кластере нет оценки объекта, то предсказание невозможно.
== Холодный старт ==
{{Определение
|definition=
'''Холодный старт''' (англ. ''cold start'') {{---}} это типичная ситуация, когда ещё не накоплено достаточное количество данных для корректной работы рекомендательной системы.
}}
Данная проблема актуальна для новых объектов или объектов, с которыми пользователи редко совершают действия. Если средний рейтинг посчитан по оценкам всего трёх пользователей, такая оценка явно не будет достоверной, и пользователи это понимают. Часто в таких ситуациях рейтинги искусственно корректируют.
== User-based и item-based алгоритмы ==
=== User-based алгоритм ===Заменим жесткую кластеризацию на предположение, что фильм объект понравится пользователю, если он понравился его друзьямпохожим пользователям.Тогда предпочтение пользователя <tex>u</tex> к объекту <tex>i</tex> можно записать следующим образом:
<tex> \hat{r_r}_{ui}} = \bar{r_ur} _u + \fracdfrac{\sum_{v \in U_i}{}{sim(u, v)(r_{vi} - \bar{r_vr}_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>.
Однако у этого алгоритма есть недостатки:
* Холодный холодный старт.— новые объекты никому не рекомендуются;* Нечего нечего рекомендовать новым/нетипичным пользователям.
<tex> \hat{r_r}_{ui}} = \bar{r_ir} _i + \fracdfrac{\sum_{j \in I_u}{}{sim(i, j)(r_{uj} - \bar{r_jr}_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>.
У такого подхода остается недостаток в виде холодного старта и при этом рекомендации становятся тривиальными.
==Алгоритм SVD==
Чтобы предсказать оценку пользователя <tex> U u </tex> для объекта <tex> I i </tex>, берём некотрый некоторый вектор <tex> p_u </tex> для данного пользователя и вектор данного объекта <tex> q_i </tex>. Получаем необходимое предсказание: <tex> \hat{r_r}_{ui}} = \langle p_u,q_i \rangle </tex>.
Помимо предсказания оценок, алгоритм позволяет выявлять скрытые признаки объектов и интересы пользователей.
Например, может так получиться, что на первой координате вектора у каждого пользователя будет стоять число, показывающее, похож ли пользователь больше на мальчика или на девочку, на второй координате — число, отражающее примерный возраст пользователя. У фильма же первая координата будет показывать, интересен ли он больше мальчикам или девочкам, а вторая — какой возрастной группе пользователей он интересен.
==Решение проблемы матрицы оценок==
Модель будет зависеть от следующих параметров: вектор пользователей и вектор объектов. Для заданных параметров <tex> \sum_{(u</tex> и <tex>i</tex> возьмем вектор пользователя <tex> p_u </tex> и вектор объекта <tex>q_i</tex>, затем для предсказания оценки получим их скалярное произведение,i) \in D}{(как и в алгоритме SVD:<tex> \hat{r_r}_{ui}}(\Theta) - r_{ui})= p^2} + T_uq_i </tex>, где <tex> \lambda Theta = \sum_{p_u, q_i \theta mid u \in U, i \Theta}{\theta^2} \to min_{in I\Theta} </tex>.
Но вектора пока не известны, их нужно получить. Имеются оценки пользователей, при помощи которых можно найти оптимальные параметры, при которых модель предскажет оценки наилучшим образом:<tex> E_{(u,i)}(\hat{r}_{Определение|definition='''Регуляризация''' ui}(англ. ''regularization''\Theta) в статистике, машинном обучении, теории обратных задач — метод добавления некоторых дополнительных ограничений к условию с целью решить некорректно поставленную задачу или предотвратить переобучение. Чаще всего эта информация имеет вид штрафа за сложность модели.- r_{ui})^2 \to min_{\Theta}</tex>.
==Численная оптимизация==
Шаг градиентного спуска можно записать следующим образом: <tex> \Theta_{t+1} = \Theta_t - \eta \nabla J(\Theta) </tex>, где <tex> \eta </tex> {{---}} коэффициент скорости обучения.
Существуют при этом и другие метрики {{---}} метрики ранжирования, на основе полноты и точности. Однако она также обладает недостатками, хоть они не так популярны и является стандартом измерения качества:используются значительно реже.
==См. также==* [[Кластеризация]]* [[Регуляризация]]* [[Оценка качества в задаче кластеризации]]* [[Оценка качества в задачах классификации и регрессии]]== Примечания ==<references/>== Источники информации==* [https://habr.com/ru/company/yandex/blog/241455/ Как работают рекомендательные системы.]* Пользователи с большим разбросом оценок будут влиять на значение метрики больше[https://habr.com/ru/company/jetinfosystems/blog/453792/ Рекомендательные системы: идеи, подходы, чем остальныезадачи.]* Ошибка в предсказании высокой оценки имеет такой же вес, что и ошибка в предсказании низкой оценки[https://neurohive.io/ru/osnovy-data-science/rekomendatelnye-sistemy-modeli-i-ocenka/ Анатомия рекомендательных систем.]* Есть риск плохого ранжирования при почти идельаной RMSE [http://www.mathnet.ru/links/4d5ff6f460c0d9409ce16b558725408d/ista26.pdf Рекомендательные системы: обзор основных постановок и наоборотрезультатов.]