ИТМО Machine Learning 2016. Рекомендательные системы
Download as PPTX, PDF1 like330 views
Рассказ про рекомендательные системы в целом, о том, какие они бываю и какие данные используют. Краткий разбор kNN-модели и SVD, рассказ о том, как применять SGD и ALS для обучения SVD. Обучение implicit SVD через iALS. Методы построения объяснений к рекомендациям. Обзор основных метрик качества Модель Personalized Bayesian Ranking в качестве примера learning to rank framework.
![Alternating Least Squares
P-step: обновление при фиксированных векторах item-ов
pu = lnuI + Au( )
-1
du
Au = Q[u]T
Q[u]= qiqi
T
i: u,i( )ÎR
å
du = Q[u]T
ru = ruiqi
i: u,i( )ÎR
å
Q-step: обновление при фиксированных векторах пользователей
qi = lniI + Ai( )
-1
di
Ai = P[i]T
P[i]= pu pu
T
u: u,i( )ÎR
å
di = P[i]T
ri = rui pu
u: u,i( )ÎR
å](https://image.slidesharecdn.com/recsys-itmo-autumn-2016-161121110047/85/Machine-Learning-2016-24-320.jpg)
More Related Content
What's hot (20)
Viewers also liked (7)
Similar to ИТМО Machine Learning 2016. Рекомендательные системы (6)
ИТМО Machine Learning 2016. Рекомендательные системы
- 5. 5
- 6. 6
- 8. F. Ricci “Recommender Systems Handbook” │ Recommender Systems are software tools and techniques providing suggestions for items to be of use to a user 8
- 11. Классификация RS Available data User history Content Collaborative Content-based Hybrid Tags & Metadata
- 12. Данные • Рейтинги (explicit feedback) • унарные (like) • бинарные (like/dislike) • числовые (stars) • История действий пользователя (implicit feedback) • Тэги, метаданные • Комментарии, отзывы • Друзья 12
- 13. Рекомендательные задачи 1. Predict 2. Recommend 3. Similar 13
- 14. Как построить простую рекомендательную систему? 14
- 15. User-based kNN Как продукт оценили похожие пользователи? ˆrui = 1 Ni u( ) rvi vÎNi (u) å Взвесим вклад каждого ˆrui = wuvrvi vÎNi (u) å wuv vÎNi (u) å И нормализуем рейтинги ˆrui = h-1 wuvh rvi( ) vÎNi (u) å wuv vÎNi (u) å æ è ç ç ç ö ø ÷ ÷ ÷
- 16. Как посчитать расстояние? Косинусное расстояние Корреляция Пирсона cos(u,v) = ruirvi iÎIuv å r2 ui iÎIu å rvj 2 jÎIv å PC(u,v) = (rui - ru )(rvi - rv ) iÎIuv å (rui - ru )2 iÎIu å (rvj - rv )2 jÎIv å Поправленное косинусное расстояние (adjusted cosine) AC(u,v) = (rui - ri )(rvi - ri ) iÎIuv å (rui - ri )2 iÎIu å (rvj - rj )2 jÎIv å
- 17. Как нормализовать рейтинги? 17 h rui( )= rui -ru h rui( ) = rui - ru su h rui( ) = j Î Iu :ruj £ rui{ } Iu Mean centering Z-score Percentile score
- 18. Как выиграть Netflix Prize?
- 20. Singular Value Decomposition Теорема: если в матрице λ оставить k наибольших элементов, то полученное произведение A’ будет наилучшим среди всех матриц ранга k приближением матрицы A.
- 21. Baseline predictors Модель: ˆruiu = m +bu +bi argmin b* ruiu -m -bu -bi( ) (u,i)ÎR å 2 +l bu 2 + uÎU å bi 2 iÎI å æ è ç ö ø ÷ Функция ошибки:
- 22. SVD Модель: Функция ошибки: ˆrui = m +bu +bi + pu T qi argmin p*q*b* rui -m -bu -bi - pu T qi( ) (u,i)ÎR å 2 +l pu 2 + qi 2 +bu 2 +bi 2 ( )
- 23. Optimization by SGD Модель: Функция ошибки: ˆrui = m +bu +bi + pu T qi argmin p*q*b* rui -m -bu -bi - pu T qi( ) (u,i)ÎR å 2 +l pu 2 + qi 2 +bu 2 +bi 2 ( ) bu ¬ bu +g1 eui - l1bu( ) bi ¬ bi +g1 eui - l1bi( ) pu ¬ pu +g2 euiqi - l2 pu( ) qu ¬ qi +g2 eui pu - l2qi( ) Шаг стохастического градиентного спуска:
- 24. Alternating Least Squares P-step: обновление при фиксированных векторах item-ов pu = lnuI + Au( ) -1 du Au = Q[u]T Q[u]= qiqi T i: u,i( )ÎR å du = Q[u]T ru = ruiqi i: u,i( )ÎR å Q-step: обновление при фиксированных векторах пользователей qi = lniI + Ai( ) -1 di Ai = P[i]T P[i]= pu pu T u: u,i( )ÎR å di = P[i]T ri = rui pu u: u,i( )ÎR å
- 25. Что делать с implicit feedback?
- 26. Как использовать implicit feedback? Идея: rating => (preference, confidence) pui Î {0,1} cui Î Â+ "(u,i) Î R cui =1+arui pui =1 pui = 0 иначе или cui =1+a log 1+rui b( )
- 27. Обучение модели argmin x*y* cui pui - xu T yi( ) (u,i) å 2 + l xu 2 u å + yi 2 i å æ è ç ö ø ÷ Функция ошибки: xu = lI +YT Cu Y( ) -1 YT Cu p(u) yi = lI + XT Ci X( ) -1 XT Ci p(i) Это сводится к уравнениям для ALS:
- 28. Обучение модели argmin x*y* cui pui - xu T yi( ) (u,i) å 2 + l xu 2 u å + yi 2 i å æ è ç ö ø ÷ Функция ошибки: xu = lI +YT Cu Y( ) -1 YT Cu p(u) yi = lI + XT Ci X( ) -1 XT Ci p(i) Это сводится к уравнениям для ALS: Но есть проблема!
- 29. в матрице всего ненулевых элементов, В матрице всего ненулевых элементов, Ускорение iALS Идея: YT Cu Y =YT Y +YT Cu - I( )Y Cu - I Cu p(u) YT Y O f 2 N + f 3 U( ) nu nu а не зависит от пользователя! Итого: обновляем вектора пользователей за
- 30. Интуиция iALS xu = lI +YT Cu Y( ) -1 YT Cu p(u) = lI + Au( ) -1 du A0 = c0yi T yi i å d0 = c0 p0yi i å Au = A0 + (cui -c0 )yi T yi (u,i)ÎN(u) å du = d0 + cui pui -c0 p0( )yi u,i( )ÎN(u) å Введем «нулевого» пользователя без фидбека: Тогда для остальных пользователей выводим: Выпишем ALS-шаг в упрощенной форме:
- 31. Как выбирать c0 и p0? "(u,i) Î N cui =1+arui pui =1 pui = 0 иначе Как и раньше:
- 32. Как выбирать c0 и p0? "(u,i) Î N cui =1+arui pui =1 pui = 0 иначе Как и раньше: c0 =1 p0 = 0
- 34. Если вам нравится X, то попробуйте Y… Вам понравится Y!
- 35. Item-based model explanation Модель: ˆrui = wijrui jÎNu k å Вклад в рейтинг:wijrui Выберем j с максимальными вкладами — это и есть объяснение! j
- 36. ALS explanation Модель:ˆrui = yi T xu = yi T lI +YT Y( ) -1 YT r u( ) ˆrui = sij u u,i( )ÎR å ruj Wu = YT Y + lI( ) -1 sij u = yi T Wu yj Выберем j с максимальными вкладами — это и есть объяснение! Тогда перепишем модель как Вклад в рейтинг:sij u rujj
- 37. iALS explanation Модель:ˆpui = yi T xu = yi T lI +YT Cu Y( ) -1 YT Cu p(u) ˆpui = sij u pui>0 å cuj puj Wu = YT Cu Y + lI( ) -1 sij u = yi T Wu yj Выберем j с максимальными вкладами — это и есть объяснение! Тогда перепишем модель как Вклад в рейтинг:sij u cuj puj = sij u cujj
- 39. Prediction quality RMSE = 1 | R | rui - ˆrui( ) u,iÎR å 2 MAE = 1 R rui - ˆrui u,iÎR å
- 40. Classification quality Истинный ответ 0 Истинный ответ 1 Предсказали 0 TN FN Предсказали 1 FP TP Confusion matrix: P = TP TP + FP R = TP TP + FN F1 = 2 1 P + 1 R Precision: Recall:
- 41. More on classification quality AP = P(k)Dr(k) k=1 n å MAP = AP(q) qÎQ å Q Average precision: Mean average precision: MAP — средняя точность на позициях, где есть попадания в top k.
- 42. Ranking quality (NDPM) C+ = sgn rui - ruj( )sgn ˆrui - ˆruj( ) ij å C- = sgn rui - ruj( )sgn ˆruj - ˆrui( ) ij å Cu = sgn2 rui - ruj( ) ij å Cs = sgn2 ˆrui - ˆruj( ) ij å Cu0 = Cu - C+ +C- ( ) NDPM = C- + 1 2 Cu0 Cu
- 43. Ranking quality (NDCG) DCGu = r1 + ri log2 ii=2 n å NDCGu = DCGu IDCGu NDCG = NDCGu U Пусть для каждого пользователя и item-а задана «релевантность» r
- 45. │Давайте смотреть на порядок пар!
- 46. BPR: problem setting Для пользователей u из U и фильмов i из I составим обучающее множество как тройки: DS ={(u,i, j):i Î Iu + ^ j Î I Iu + } где Iu + — фильмы с implicit feedback для данного пользователя >u — полный порядок на фильмах, причем выполняются свойства: "i, j Î I :i ¹ j Þ i >u jÚ j >u i "i, j Î I :i >u j ^ j >u i Þ i = j "i, j,k Î I :i >u j ^ j >u k Þ i >u k полнота антисимметричность транзитивность
- 47. Байесовская формулировка p Q|>u( )µ p >u|Q( )p Q( ) Тогда для всех пользователей запишем: Тогда по свойствам порядка это можно упростить: 𝑢∈𝑈 𝑝 > 𝑢 Θ = 𝑢,𝑖,𝑗∈𝐷𝑠 𝑝(𝑖 > 𝑢 |Θ 𝑢∈𝑈 𝑝 > 𝑢 Θ = 𝑢,𝑖,𝑗∈𝑈×𝐼×𝐼 𝑝(𝑖 > 𝑢 |Θ 𝛿((𝑢,𝑖,𝑗 ∈𝐷𝑠 ∙ 1 − 𝑝 𝑖 > 𝑢 𝑗 Θ 𝛿((𝑢,𝑖,𝑗 ∉𝐷𝑠
- 48. Preference model p i >u j |Q( )=s( ˆxuij (Q)) Окончательно определим модель как: Здесь ˆxuij — «встроенная» модель, которая отслеживает связь между u, i и j. Например, - матричное разложение - модель kNN
- 49. BPR-Opt p Q( )= N(0,SQ ) Предположим, наконец, априорное распределение параметров: Тогда весь алгоритм: BPR -Opt := ln p Q |>u( ) = ln p >u|Q( ) p(Q) = ln s ˆxuij Q( )( )p Q( ) (u,i, j)ÎDs Õ = ln (u,i, j)ÎDs å s ˆxuij Q( )( )+ ln p Q( ) = ln (u,i, j)ÎDs å s ˆxuij Q( )( )- lQ Q 2
- 50. LearnBPR 1. Инициализируем параметры Θ 2. Пока не достигнута сходимость: 1. Выберем пример из Ds 3. Вернем финальные параметры Q¬ Q+a exp(- ˆxuij ) 1+exp(- ˆxuij ) × ¶ ¶Q ˆxuij +lQQ æ è çç ö ø ÷÷2.
- 51. Еще раз о модели рейтинга Распишем ˆxuij = ˆxui - ˆxuj В случае разложения матриц ˆxui = wu,hi = wuf hif f =1 k å Тогда производные распишутся как ¶ˆxuij ¶q = (hif - hjf ) wuf -wuf 0 если q = wuf если q = hif если q = hjf иначе
- 52. А разве что-то еще осталось?
- 53. If you like this lecture you will like these books
- 55. Контакты danilchenko@yandex-team.ru Удачи! Андрей Данильченко Группа технологий рекомендаций, Яндекс mir_nomer_nol
Editor's Notes
- #35: Делает более быстрые итерации, сходится туда же
- #36: Делает более быстрые итерации, сходится туда же
- #37: Делает более быстрые итерации, сходится туда же
- #38: Делает более быстрые итерации, сходится туда же
- #43: Normalized Distance-based Performance Measure C+ правильное ранжирование C- неправильное ранжирование C_u — сколько пар можем отранжировать С_s — сколько пар система смогла отранжировать C_u0 — сколько пар, где реально нет ранжирования, а система его ввела NDPM — 0 там где перевернули все рейтинги, 1 там где правильно все. предсказание отсутствия разницы штрафуется в половину меньше, чем переворот ранжирования. Где не знаем ранжирование — не штрафуем.
- #44: Normalized discounted cumulative gain