22
правки
Изменения
→Алгоритм SVD
Пользовательские оценки, необходимые для составления матрицы предпочтений, можно получить двумя способами:
* явно (''explicit ratings'')* неявно (''implicit ratings'')
Очевидно, что явное оценивание лучше, так как сам пользователь определяет насколько ему интересен тот или иной объект, однако из-за непостоянства в получении явных оценок от пользователей, на практике используется оба подхода.
Формализуем задачу. Имеется множество пользователей <tex> u \in U </tex>, множество объектов <tex> i \in I </tex> и множество событий <tex> (r_{ui}, u, i, ...) \in D </tex> (действия, которые совершают пользователи с объектами). Каждое событие задается пользователем <tex> u </tex>, объектом <tex> i </tex>, своим результатом <tex> r_{ui} </tex> и, возможно, но не обяхательно, другими харакетристиками. По итогу требуется:
* предсказать предпочтение: <tex> \hat{r_r}_{ui}} = Predict(u, i, ...) \approx r_{ui} </tex>
* персональные рекомендации: <tex> u \mapsto (i_1, ..., i_k) = Recommend_k(u, ...) </tex>
* похожие объекты: <tex> u \mapsto (i_1, ..., i_M) = Similar_M(i) </tex>
* Выберем условную меру схожести пользователей по истории их оценок <tex> sim(u, v) </tex>
* Объеденим пользователей в группы так, чтобы похожие пользователи оказывались в одном кластере <tex> u \mapsto F(u) </tex>
* Оценку пользователя предскажем как среднюю оценку кластера этому объекту <tex> \hat{r_r}_{ui}} = \frac{1}{|F(u)|}\sum_{u \in F(u)}{}{r_{ui}} </tex>
Проблемы алгоритма:
* Не учитывается контекст и специфика пользователя.
* Если в кластере нет оценки объекта, то предсказание невозможно.
== Холодный старт ==
{{Определение
|definition=
'''Холодный старт''' {{---}} ситуация, когда ещё не накоплено достаточное количество данных для корректной работы рекомендательной системы.
}}
Данная проблема актуальна для новых объектов или объектов, которые редко покупают. Если средний рейтинг посчитан по оценкам всего трёх пользователей, такая оценка явно не будет достоверной, и пользователи это понимают. Часто в таких ситуациях рейтинги искусственно корректируют.
Первый способ – показывать не среднее значение, а сглаженное среднее (''Damped Mean''). Смысл таков: при малом количестве оценок отображаемый рейтинг больше тяготеет к некому безопасному «среднему» показателю, а как только набирается достаточное количество новых оценок, «усредняющая» корректировка перестает действовать.
Другой подход – рассчитывать по каждому рейтингу интервалы достоверности (''Confidence Intervals''). Математически, чем больше оценок, тем меньше вариация среднего и, значит, больше уверенность в его корректности. А в качестве рейтинга можно выводить, например, нижнюю границу интервала (''Low CI Bound''). При этом понятно, что такая система будет достаточно консервативной, с тенденцией к занижению оценок по новым товарам.
== User-based и item-based алгоритмы ==
Заменим жесткую кластеризацию на предположение, что фильм понравится пользователю, если он понравился его друзьям.
<tex> \hat{r_r}_{ui}} = \bar{r_ur} _u + \frac{\sum_{v \in U_i}{}{sim(u, v)(r_{vi} - \bar{r_vr}_v)}}{\sum_{v \in {U_i}}{}{sim(u, v)}} </tex>
Однако у этого алгоритма есть недостатки:
Так же имеется абсолютно симметричный алгоритм. Теперь будем считать, что фильм понравится пользователю, если ему понравились похожие фильмы.
<tex> \hat{r_r}_{ui}} = \bar{r_ir} _i + \frac{\sum_{j \in I_u}{}{sim(i, j)(r_{uj} - \bar{r_jr}_j)}}{\sum_{j \in {I_u}}{}{sim(i, j)}} </tex>
У такого подхода остается недостаток в виде холодного старта и при этом рекомендации становятся тривиальными.
}}
[[Файл:3.png|400px|thumb|right|SVD для рекомендательных систем.]]
<tex> UU^T = I_n</tex>, <tex>VV^T = I_m</tex>
Получаем наилучшее низкоранговое приближение с точки зрения средне-квадратичного отклонения.
Чтобы предсказать оценку пользователя <tex> U </tex> для объекта <tex> I </tex>, берём некотрый вектор <tex> p_u </tex> для данного пользователя и вектор данного объекта <tex> q_i </tex>. Получаем необходимое предсказание: <tex> \hat{r_r}_{ui}} = \langle p_u,q_i \rangle </tex>.
Помимо предсказания оценок, алгоритм позволяет выявлять скрытые признаки объектов и интересы пользователей.
==Решение проблемы матрицы оценок==
Модель будет зависить от ногих параметров - вектора пользователей и вектора объектов. Для заданных парметров, возьмем вектор пользователя, вектор объекта и получим их скалярное произведение, чтобы предсказать оценку:
<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 </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>
{{Определение
|definition=
'''Регуляризация''' (англ. ''regularization'') в статистике, машинном обучении, теории обратных задач — метод добавления некоторых дополнительных ограничений к условию с целью решить некорректно поставленную задачу или предотвратить переобучение. Чаще всего эта информация имеет вид штрафа за сложность модели.
}}
Регуляризация заключается в том, что минимизируется не только ошибка, но и некоторая функция параметров (например, норма вектора параметров). Это позволяет ограничить размер параметров в решении, уменьшает степень свободы модели.
==Численная оптимизация==
[[Файл:2.png|200px|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> \nabla J(\Theta) = (\frac{\partial J}{\partial \theta_1}, \frac{\partial J}{\partial \theta_2},...,\frac{\partial J}{\partial \theta_n})^T </tex>
Можно воспользоваться градиентным бустингом:
<tex> \Theta_{t+1} = \Theta_t - \eta \nabla J(\Theta) </tex>
Проблема же заключается в том, что алгоритм работает медленно, а минимумы которые он находит - локальные, а не глобальные.
==Измерение качества рекомендаций==
Было предложено измерять качество рекомендаций при помощи RMSE:
<tex> RMSE = \sqrt{\frac{1}{|D|} \sum_{(u,i) \in D}{(\hat{r}_{ui} - r_{ui})^2}} </tex>
Однако она также обладает недостатками, хоть и является стандартом измерения качества:
* Пользователи с большим разбросом оценок будут влиять на значение метрики больше, чем остальные.
* Ошибка в предсказании высокой оценки имеет такой же вес, что и ошибка в предсказании низкой оценки.
* Есть риск плохого ранжирования при почти идельаной RMSE и наоборот.
Существуют при этом и другие метрики - метрики ранжирования, на основе полноты и точности. Однако они не так популярны и используются значительно реже.
== Источники информации==
* [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/ Анатомия рекомендательных систем.]
* [http://www.mathnet.ru/links/4d5ff6f460c0d9409ce16b558725408d/ista26.pdf Рекомендательные системы: обзор основных постановок и результатов.]
