Изменения

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

Основная задача рекомендательных систем <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>

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

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

* Выберем условную меру # Выбор условной меры схожести пользователей по истории их оценок <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>.

* Нечего нечего рекомендовать новым пользователям, так как их невозможно определить отнести к какому-нибудь либо кластеру,а значит и рекомендовать им нечего.;* Не не учитывается контекст и специфика пользователя.;* Если если в кластере нет оценки объекта, то предсказание невозможно. == Холодный старт =={{Определение|definition='''Холодный старт''' (англ. ''cold start'') {{---}} ситуация, когда ещё не накоплено достаточное количество данных для корректной работы рекомендательной системы.}}Данная проблема актуальна для новых объектов или объектов, с которыми пользователи редко совершают действия. Если средний рейтинг посчитан по оценкам всего трёх пользователей, такая оценка явно не будет достоверной, и пользователи это понимают. Часто в таких ситуациях рейтинги искусственно корректируют. '''Первый способ.''' Предлагается показывать не среднее значение, а сглаженное среднее (англ. ''damped mean''). Смысл таков: при малом количестве оценок отображаемый рейтинг больше тяготеет к некому безопасному «среднему» показателю, а как только набирается достаточное количество новых оценок, «усредняющая» корректировка перестает действовать. '''Второй способ.''' Для объекта считается средний рейтинг, затем определяется доверительный интервал(англ. ''сonfidence interval'') этого рейтинга. Математически, чем больше оценок, тем меньше вариация среднего и, значит, больше уверенность в его корректности. А в качестве рейтинга объекта можно выводить, например, нижнюю границу интервала (англ. ''low CI bound''). При этом понятно, что такая система будет достаточно консервативной, с тенденцией к занижению оценок по новым объектам.

=== 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>.

* Холодный холодный старт.— новые объекты никому не рекомендуются;* Нечего нечего рекомендовать новым/нетипичным пользователям.

Так же === Item-based алгоритм ===Также имеется абсолютно симметричный алгоритм. Теперь будем считать, что фильм объект понравится пользователю, если ему понравились похожие фильмыобъекты.Предпочтение пользователя <tex>u</tex> к объекту <tex>i</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>.

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

Попробуем воспользоваться [[Сингулярное разложение | сингулярным разложением (SVD)]] для задачи рекомендации.  Разложим матрицу оценок <tex> R </tex> с использованием сингулярного разложения: <tex> R_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{Определениеm \times m} </tex>.|definition=Применяя усеченное разложение, получим следующее:<tex> R'_{n \times m} = U'_{n \times d} \times \Sigma 'SVD_{d \times d} \times V''' (''Single Value Decomposition'') ^T_{{---d \times m}} у любой матрицы <tex> A </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 T_{d \times m} </tex>. Матрицы обозначим как <tex> U, \tilde{V }_{d \times m} </tex> ортогональные, а . Получим формулу <tex> R'_{n \Sigma times m} = \tilde{U}_{n \times d} \times \tilde{V}_{d \times m} </tex> - диагональная. Интерпретировать полученную формулу стоит следующим образом: приближенная матрица оценок может быть вычислена как произведение усеченных матриц пользователей и оценок. Благодаря использованию такого усечения можно решить одну из главных проблем всех ранее упомянутых алгоритмов: ресурсоемкость вычислений.

Чтобы предсказать оценку пользователя <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> UU^T = I_n</tex>Помимо предсказания оценок, <tex>VV^T = I_m</tex>алгоритм позволяет выявлять скрытые признаки объектов и интересы пользователей.Например, может так получиться, что на первой координате вектора у каждого пользователя будет стоять число, показывающее, похож ли пользователь больше на мальчика или на девочку, на второй координате — число, отражающее примерный возраст пользователя. У фильма же первая координата будет показывать, интересен ли он больше мальчикам или девочкам, а вторая — какой возрастной группе пользователей он интересен.

Однако данный алгоритм имеет ряд проблем:* матрица оценок <tex> \Sigma = diag(\lambda_1, ..., \lambda_{min(n, m)})R </tex>полностью не известна, <tex>\lambda_1 \geq поэтому просто взять SVD разложение не представляется возможным;* Сингулярное разложение не единственное, поэтому даже если какое-то разложение будет найдено, нет гарантии, что первая координата в нем будет соответствовать некоторым выбранным характеристикам пользователя... \geq \lambda_{min(n, m)} \geq 0 </tex>

Значит у матриц <tex> U </tex> и Для решения проблем, связанных с матрицей оценок <tex> V R</tex> остаются только первые <tex> d </tex> столбцов, а матрица <tex> \Sigma </tex> становится квадратной размером <tex> d \times d </tex>построим модель.

Модель будет зависеть от следующих параметров: вектор пользователей и вектор объектов. Для заданных параметров <tex> A'_u </tex> и <tex>i</tex> возьмем вектор пользователя <tex> p_u </tex> и вектор объекта <tex>q_i</tex>, затем для предсказания оценки получим их скалярное произведение, как и в алгоритме SVD:<tex> \hat{n \times mr} = U'_{n ui}(\times d} Theta) = p^T_uq_i </tex>, где <tex> \times Theta = \Sigma'_{d p_u, q_i \times d} mid u \in U, i \times V'^T_{d in I\times m} </tex>.

Получаем наилучшее низкоранговое приближение с точки зрения среднеНо вектора пока не известны, их нужно получить. Имеются оценки пользователей, при помощи которых можно найти оптимальные параметры, при которых модель предскажет оценки наилучшим образом:<tex> E_{(u,i)}(\hat{r}_{ui}(\Theta) -квадратичного отклоненияr_{ui})^2 \to min_{\Theta} </tex>.

Чтобы предсказать оценку пользователя То есть, нужно найти такие параметры <tex> U </tex> для объекта <tex> I \Theta </tex>, берём некотрый вектор чтобы квадрат ошибки был наименьшим. Однако ситуация следующая: оптимизация приведет к наименьшим ошибкам в будущем, но как именно оценки будут спрашивать {{---}} неизвестно. Следовательно, это нельзя оптимизировать. Однако, так как оценки, уже проставленные пользователями, известны, постараемся минимизировать ошибку на тех данных, что у нас уже есть. Также воспользуемся [[Регуляризация | регуляризацией]]. В качестве регуляризатора будет выступать слагаемое <tex> p_u </tex> для данного пользователя и вектор данного объекта <tex> q_i \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} = \langle p_u,q_i to min_{\rangle Theta} </tex>.

Одна есть и свои проблемыЧтобы найти оптимальные параметры построенной модели необходимо оптимизировать следующий функционал:

*<tex> R 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> матрица оценок полностью не известна, поэтому просто взять SVD разложение не получится.*SVD разложение не единственное, поэтому даже если какое-то разложение будет найдено, нет гарантии, что первая координата в нем будет соответствовать некоторым выбранным характеристикам пользователя.

Модель будет зависить от ногих параметров - вектора пользователей и вектора объектов. Для заданных парметров<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> \hatTheta_{r_{ui}t+1}= \Theta_t - \eta \nabla J(\Theta) = p^T_uq_i </tex>,где <tex> \eta </tex> {{---}} коэффициент скорости обучения.

<tex> \Theta = {p_u,q_i | u \in U, i \in I} </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> E_RMSE = \sqrt{\dfrac{1}{|D|} \sum_{(u,i)\in D}{(\hat{r_r}_{ui}}(\Theta) - r_{ui})^2 \to min_{\Theta}} </tex>.

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

<tex> \sum_Существуют при этом и другие метрики {(u,i) \in D}{(\hat{r_{ui}}(\Theta) - r_{ui--})^2} + \lambda \sum_{\theta \in \Theta}{\theta^2} \to min_{\Theta} </tex>метрики ранжирования, на основе полноты и точности. Однако они не так популярны и используются значительно реже.

{{Определение==См. также==* [[Кластеризация]]* [[Регуляризация]]* [[Оценка качества в задаче кластеризации]]* [[Оценка качества в задачах классификации и регрессии]]== Примечания ==<references/>|definition== Источники информации==* [https://habr.com/ru/company/yandex/blog/241455/ Как работают рекомендательные системы.]'''Регуляризация''' (англ* [https://habr. ''regularization'') в статистикеcom/ru/company/jetinfosystems/blog/453792/ Рекомендательные системы: идеи, машинном обученииподходы, теории обратных задач — метод добавления некоторых дополнительных ограничений к условию с целью решить некорректно поставленную задачу или предотвратить переобучениезадачи.]* [https://neurohive. Чаще всего эта информация имеет вид штрафа за сложность моделиio/ru/osnovy-data-science/rekomendatelnye-sistemy-modeli-i-ocenka/ Анатомия рекомендательных систем.]}}* [http://www.mathnet.ru/links/4d5ff6f460c0d9409ce16b558725408d/ista26.pdf Рекомендательные системы: обзор основных постановок и результатов.]