Изменения

Основная задача рекомендательных систем <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}_{ui} = Predict(u, i,\dots) \approx r_{ui}; </tex>* выдавать персональные рекомендациидля пользователя <tex> u </tex>: <tex> Recommend_k(u \mapsto (i_1,\dots, i_k) = Recommend_k(ui_1,\dots, i_k); </tex>* определять объекты, похожие объектына объект <tex>i</tex>: <tex> u \mapsto Similar_M(i) = (i_1,\dots, i_M) = Similar_M(i). </tex>

* Выберем условную меру # Выбор условной меры схожести пользователей по истории их оценок <tex> sim(u, v) </tex>;.* Объединим # Объединение пользователей в группы (кластеры) так, чтобы похожие пользователи оказывались в одном кластере <tex> u \mapsto F(u) </tex>;.* Оценку # Предсказание оценки пользователя предскажем как среднюю оценку : средняя оценка кластера этому объекту <tex> \hat{r}_{ui} = \dfrac{1}{|F(u)|}\sum_{u \in F(u)}{}{r_{ui}} </tex>.

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

Данная проблема актуальна для новых объектов или объектов, которые с которыми пользователи редко покупаютсовершают действия. Если средний рейтинг посчитан по оценкам всего трёх пользователей, такая оценка явно не будет достоверной, и пользователи это понимают. Часто в таких ситуациях рейтинги искусственно корректируют.

'''Первый способ – .''' Предлагается показывать не среднее значение, а сглаженное среднее (англ. ''Damped Meandamped mean''). Смысл таков: при малом количестве оценок отображаемый рейтинг больше тяготеет к некому безопасному «среднему» показателю, а как только набирается достаточное количество новых оценок, «усредняющая» корректировка перестает действовать.

Другой подход – рассчитывать по каждому рейтингу интервалы достоверности '''Второй способ.''' Для объекта считается средний рейтинг, затем определяется доверительный интервал(англ. ''Confidence Intervalsсonfidence interval'')этого рейтинга. Математически, чем больше оценок, тем меньше вариация среднего и, значит, больше уверенность в его корректности. А в качестве рейтинга объекта можно выводить, например, нижнюю границу интервала (англ. ''Low low CI Boundbound''). При этом понятно, что такая система будет достаточно консервативной, с тенденцией к занижению оценок по новым товарамобъектам.

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

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

{{Определение|definition='''SVD''' (англ. ''Single Value Decomposition'') {{---}} у любой матрицы <tex> A </tex> размера <tex> n \times m </tex> существует разложение трех матриц: <tex> U, \Sigma, V^T </tex>. <tex> A_{n \times m} = U_{n \times n} \times \Sigma_{n \times m} \times V^T_{m \times m} </tex> Матрицы <tex> U, V </tex> ортогональные, а <tex> \Sigma </tex> {{---}} диагональная.}} Попробуем воспользоваться [[Файл:3.png|400px|thumb|rightСингулярное разложение |сингулярным разложением (SVD )]] для рекомендательных системзадачи рекомендации.]] <tex> UU^T = I_n</tex>, <tex>VV^T = I_m</tex>

Разложим матрицу оценок <tex> R </tex> с использованием сингулярного разложения: <tex> R_{n \Sigma times m} = diag(U_{n \times n} \times \Sigma_{n \times m} \lambda_1,times V^T_{m \dotstimes m} </tex>.Применяя усеченное разложение,получим следующее:<tex> R'_{n \lambda_times m} = U'_{min(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 \lambda_1 times m} </tex> обозначим как <tex> \geq tilde{V}_{d \dots times m} </tex>. Получим формулу <tex> R'_{n \geq times m} = \lambda_tilde{U}_{min(n, \times d} \times \tilde{V}_{d \times m)} \geq 0 </tex>. Интерпретировать полученную формулу стоит следующим образом: приближенная матрица оценок может быть вычислена как произведение усеченных матриц пользователей и оценок.

Обратить внимание же стоит на усеченное разложение, когда Благодаря использованию такого усечения можно решить одну из лямбд, остаются только первые <tex> d </tex> чисел, а остальные полагаем, что равны нулюглавных проблем всех ранее упомянутых алгоритмов: ресурсоемкость вычислений.

<tex> \lambda_{d+1},\dots, \lambda_{min(n,m)} [[Файл:= 0 </tex>RecommendSVD.png|450px|thumb|right|SVD для рекомендательных систем.]]

Значит у матриц <tex> U </tex> и <tex> V </tex> остаются только первые <tex> d </tex> столбцов, а матрица <tex> \Sigma </tex> становится квадратной размером <tex> d \times d </tex>. <tex> A'_{n \times m} = U'_{n \times d} \times \Sigma'_{d \times d} \times V'^T_{d \times m} </tex> Получаем наилучшее низкоранговое приближение с точки зрения средне-квадратичного отклонения. Чтобы предсказать оценку пользователя <tex> U u </tex> для объекта <tex> I i </tex>, берём некотрый некоторый вектор <tex> p_u </tex> для данного пользователя и вектор данного объекта <tex> q_i </tex>. Получаем необходимое предсказание: <tex> \hat{r}_{ui} = \langle p_u,q_i \rangle </tex>.

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

Для решения проблем, связанных с матрицей оценок <tex> \Theta = {p_u,q_i | u \in U, i \in I} R</tex>, построим модель.

Но вектора пока не известныМодель будет зависеть от следующих параметров: вектор пользователей и вектор объектов. Для заданных параметров <tex> u </tex> и <tex>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> \sum_E_{(u,i) \in D}{(\hat{r}_{ui}(\Theta) - r_{ui})^2} + \lambda \sum_{\theta \in \Theta}{\theta^2} \to min_{\Theta} </tex> {{Определение|definition='''Регуляризация''' (англ. ''regularization'') в статистике, машинном обучении, теории обратных задач — метод добавления некоторых дополнительных ограничений к условию с целью решить некорректно поставленную задачу или предотвратить переобучение. Чаще всего эта информация имеет вид штрафа за сложность модели.}}

Регуляризация заключается То есть, нужно найти такие параметры <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}{(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> \Theta_{t+1} = \Theta_t - \eta \nabla J(\Theta) </tex> Проблема же заключается в том, что алгоритм работает медленно, а минимумы которые он находит где <tex> \eta </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>.

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