<style> .reveal section img { background:none; border:none; box-shadow:none; } .reveal { font-size: 30px; } .reveal p { text-align: left; } .reveal ul { display: block; } .reveal ol { display: block; } </style> <h1>Recomanadors (Part I)</h1> ## Taller Nous Usos de la Informàtica <h1><img width="150" src="https://i.imgur.com/vvZMy0I.png"></h1> --- ### Objectiu d'un recomanador Un **recomanador** és un sistema de filtrat d'informació que té per objectiu posar en correspondència un *usuari* amb *ítems* (que possiblement no coneix) en funció d'una **estimació** de les seves preferències i interesos a partir d'una *mostra* (expressats de forma directa o indirecta). Poden servir per trobar informació/notícies, assistir en una compra, reservar una habitació d'hotel, escollir un programa de TV, etc. --- ### Exemple <center><img width="500" src="https://i.imgur.com/SubhSJI.jpg"></center> --- ### Exemple <center><img width="650" src="https://i.imgur.com/fJmd32j.png"></center> --- ### Exemple **MovieLens**: 25 million ratings and one million tags applied to 62,000 movies by 162,000 users. <center><img width="550" src="https://i.imgur.com/yJtLOv0.jpg"></center> --- ### Descobriment La frontera entre recomanadors i cercadors no és clara, però els recomanadors es poden veure com un pas més enllà dels **cercadors** en la direcció del **descobriment**. La *cerca* és el que fas quan busques alguna cosa que saps que existeix; el *descobriment* és quan alguna cosa que tu no sabies que existia (o no sabies com cercar) et troba. --- ### El problema de la recomanació Definicions: + $C$ és el conjunt de tots els usuaris i $S$ és el conjunt de tots els ítems que es poden recomanar (p.e. llibres, restaurants o compres). Els espais $C$ i $S$ poden tenir una cardinalitat molt gran! + $u: C \times S \rightarrow \mathbb{R}$ és una funció (desconeguda, però de la qual tenim una petita mostra) que assigna el grau d'utilitat o d'interès que pot tenir un determinat ítem per un determinat usuari. --- ### El problema de la recomanació El *problema de la recomanació* és determinar, per a cada usuari $c \in C$, l'ítem $s'_c \in S$ ($s'_c$ ha de formar part dels ítems que $c$ no coneix) que maximitza la funció d'utilitat: $$\forall c \in C, s'_c=\arg\max_{s \in S} u(c,s)$$ A la pràctica, els recomanadors seleccionen i presenten a l'usuari els $k$ primers ítems d'una llista ordenada segons $u(c,s)$. --- ### La matriu del recomanador La funció d'utilitat (que és discreta) es pot representar com una matriu $U$: <h1><img width="650" src="https://i.imgur.com/Ifp1Apk.png"></h1> --- *Have you ever wondered what you look like to Amazon? Here is the cold, hard truth: You are a very long row of numbers in a very, very large table. This row describes everything you've looked at, everything you've clicked on, and everything you've purchased on the site; the rest of the table represents the millions of other Amazon shoppers.* <small> **Deconstructing Recommender Systems**. Joseph Konstan, John Riedl. IEEE Spectrum, 24 September 2012. </small> --- ### Les dades + Els elements de $C$ es també es poden caracteritzar amb un perfil, que inclou característiques definitòries de l'usuari (característiques demogràfiques, les seves preferències, etc.). + Els elements de $S$ també es poden caracteritzar amb un conjunt de característiques (p.e. per una pel·lícula, tota la informació associada: director, gènere, etc.). + $U$ no està definida per tot els els elements, sinó que només en tenim una *mostra* (corresponents a les interaccions històriques entre usaris i ítems) i per tant hem d'**inferir** els seus valors: estimar quin valors d'utilitat tenen els ítems que són desconeguts per cada usuari. --- ### Recomanació i optimització <center><img width="450" src="https://i.imgur.com/lat5Lzm.png"></center> --- ### Recomanació i optimització + Les inferències (estimar un valor per cada $?$ a la matriu) es poden fer de diverses maneres, però la més important és **estimant una funció/model d'utilitat** $u'(C,S)$ de manera que optimitzi algun criteri relacionat amb l'error sobre la part de $U$ que coneixem. + Aquest tipus d'error s'anomena **error empíric**. :::info :bulb: Aquest problema té una formulació natural en termes d'optimització que veurem a la següent sessió. En aquesta sessió plantejarem una solució "heurística", no basada en optimització però amb el mateix objectiu. ::: --- <center><img width="450" src="https://i.imgur.com/lat5Lzm.png"></center> El nostre plantejament serà: Volem que la diferència (l'error) entre els valors $u_{ij}$ que coneixem i el valor que prediu la funció/model que construirem, $u'_{ij}$, sigui mínima per aquests elements i que també **generalitzi** bé pels que no coneixem (és un problema d'aprenentage!). --- ### Tipus de recomanadors A l'hora de construïr $U'$ podem adoptar tres enfocaments: + **Recomanacions col·laboratives**: Recomanarem a un usuari els ítems útils, entenent que la utilitat és construeix a partir de l'**anàlisi de la matriu** $U$. Podem construir solucions **heurístiques** o basades en **optimització**. + **Recomanacions no col·laboratives, basades en el contingut**: Recomanarem a l'usuari ítems útils, entenent que la utilitat és construeix a partir de la descripció del **contingut** dels ítems. P.e. recomanar llibres de temàtica semblant o del mateix autor. + **Models Híbrids**, que combinen els dos anteriors. --- ### Recomanacions col·laboratives Poden distingir dos tipus de recomanacions col·laboratives: + Mètodes col·laboratius basats en la *semblança d'usuaris* (basada en l'anàlisi d'$U$). + Mètodes col·laboratius basats en la *semblança d'ítems* (basada en l'anàlisi d'$U$). --- ## Mètodes col·laboratius (heurístics) basats en la *semblança d'usuaris*. --- ### Mètode col·laboratiu basat en la *semblança d'usuaris*. La utilitat $u'(c,s)$ de l'ítem $s$ per l'usuari $c$ és: 1. $u(c,s)$, si l'usuari l'ha valorat (i tenim el valor $u(c,s)$ a $U$). 2. Sinó, una estimació construida a partir de les utilitats $u(c_i, s)$ assignades a l'ítem $s$ pels usuaris $c_i$ de la nostra base de dades que l'han valorat, ponderades segons la *semblança* entre els $c_i$ i $c$. En aquest cas el problema és definir què entenem per semblança entre usuaris! --- ### Mètode col·laboratiu basats en la *semblança d'usuaris*. :::info :bulb: La solució "heurística" que proposarem inicialment es basa en la aquesta hipòtesi: la suma (model lineal) ponderada (a partir de la semblança entre usuaris) de les avaluacions que tenim d'un ítem és una bona manera d'aproximar el seu valor. ::: --- ### Semblança entre usuaris Si volem saber la utilitat $u'(c_q,s_p)$ de l'ítem $s_p$ per l'usuari $c_q$, analitzem la columna $s_p$ de la matriu $U$ i fem una suma ponderada: <h1><img width="350" src="https://i.imgur.com/qMAKs25.png"></h1> $$ u'(c_q,s_p) = \sum_{j=1}^m \alpha_{c_q c_j} u(c_j,s_p) $$ on $\alpha_{c_q c_j}$ és $0$ si $u(c_j,s_p) == \mbox{?}$ i un valor que depèn de la semblança entre els usuaris $c_q$ i $c_j$ en el cas contrari. --- ### Com calculem la **semblança** entre dos usuaris? En aquest tipus de recomanadors, la **semblança** entre dos usuaris $c_q, c_j$ es pot definir en funció de les files que els representen a la matriu $U$: + Intuïtivament, direm que dos usuaris són semblants si tendeixen a valorar els ítems de la mateixa manera, i són diferents si tendeixen a valorar els ítems de manera diferent. Per això, la mesura de semblança entre dos usuaris està definida **sobre el conjunts d'ítems que ambdós han valorat** (i que segurament té una cardinalitat diferent per cada parella d'usuaris). Llavors, la mesura de semblança es pot definir com una distància entre vectors (els vectors de les puntuacions en comú). --- ### Limitacions Les limitacions principals del model col·laboratiu són: + El problema dels nous usuaris o **cold start**: per a ser útil per l'usuari, hem de tenir una bona quantitat d'ítems valorats en comú amb altres usuaris. En cas contrari la funció de semblança entre usuaris serà poc precisa. + El problema del **nou ítem**: fins que no tenim prous valoracions de l'ítem, no serà recomanat! + El problema dels **ítems poc freqüents**: hi ha molts ítems que estaran, per definició, recomanats per poca gent (usuaris amb gustos no massius!). --- I els ítems poc freqüents no es poden despreciar! <center><img width="550" src="https://i.imgur.com/A3jV18Q.png"></center> El negoci generat pels darrers 200.000 ítems (minoritaris) pot ser més gran que els dels primers 1000! --- ### Implementació d'un recomanador col·laboratiu Suposem que tenim un fitxer amb dades sobre les preferències (en una escala de 1 a 5) d'un conjunt d'usuaris sobre les pel·licules que han vist. <h1><img width="350" src="https://i.imgur.com/4MROxu9.png)"></h1> Com podem calcular la similitud entre dos usuaris? --- ### Distàncies + Representarem l'usuari $i$ amb el vector $(u_{i1},u_{i2},\dots,u_{im})$ on $m$ és el nombre d'ítems a la nostra base de dades. Algunes d'aquestes dades són numèriques ($u_{ij}=4$) i altres són desconegudes ($u_{ij}=$`?`). + Donats dos usuaris, per calcular la seva semblança considerarem només les components *compartides* dels seus vectors, és a dir, aquells ítems que han estat valorats per tots dos. Sinó, tindriem valors desconeguts. + Les dues mesures més importants (entre les moltes possibles) per avaluar la similitud entre aquests vectors són: + la *distància euclidiana* i + el *coeficient de correlació de Pearson*, --- ### Espai de preferències Cada usuari és un punt en un espai de dimensió $m$ que anomenem *l'espai de preferències*. <h1><img width="350" src="https://i.imgur.com/5gCQzxG.png"></h1> A la figura podem veure un conjunt d'usuaris que han valorat dos ítems i la distància entre ells. --- ### Distància Euclidiana + Per calcular la distància entre els vector que representen dos usuaris $X=(x_1,\dots,x_m)$, $Y=(y_1,\dots,y_m)$, la **distància euclidiana** calcula l'arrel quadrada de la suma dels quadrats de les diferències entre cada una de les components: \begin{equation} d(X,Y)= \sqrt{(x_1-y_1)^2+ \dots + (x_m-y_m)^2} = \sqrt{\sum^{m}_{i=1}(x_i-y_i)^2} \end{equation} + A vegades és considera $\frac{1}{d(X,Y)}$, per tenir tenir un nombre que sigui més gran com més semblants. --- ### Correlació de Pearson + Alternativament, també podem analitzar la semblança entre dos usuaris $X,Y$ calculant el **Coeficient de correlació de Pearson** del conjunt $$\{(x_1, y_1), (x_2, y_2), \dots, (x_m, y_m)\}$$ + El coeficient de correlació de Pearson calcula una mesura de l'ajust d'un conjunt de punts a una recta. Funciona millor que la distància euclidiana *si les components no estan ben calibrades*. La seva fòrmula és: \begin{equation} r(X,Y)= \frac{\sum_{i=1}^m(x_i-\hat{x_i})(y_i-\hat{y_i})}{\sqrt{\sum_{i=1}^m(x_i-\hat{x_i})^2}\sqrt{\sum_{i=1}^m(y_i-\hat{y_i})^2}} \end{equation} --- <h1><img width="550" src="https://i.imgur.com/JbRVfhW.png"></h1> --- ### Calibració Direm que una mesura de "distància" entre dos vectors està calibrada si una distància de 2 representa dues vegades una distància de 1. + Si parlem de Km. en un mapa, la distància està calibrada perquè un viatge de 40Km és el doble de llarg que un viatge de 20Km. + Si parlem de les valoracions d'un llibre, no podem fer l'assumció anterior. L'única cosa que assumirem és que un llibre valorat amb 40 és millor que un llibre valorat amb 20. En el nostre cas hi ha un problema afegit: no podem considerar que tots els usuaris valorin de forma idèntica! --- ### El problema de la inflació En els gràfics es pot veure com correlació de Pearson és insensible al fet que hi pot haver usuaris que puntuïn més alt (o més baix) de forma sistemàtica (**inflació de puntuació**): en `Jack Mathews` puntua més alt que la `Lisa Rose`, però correlacionen perfectament els seus gustos. <h1><img width="350" src="https://i.imgur.com/2P3gO3d.png"></h1> --- ### Correlació negativa Les correlacions negatives també són interessants! Ens indiquen que aquells a qui agrada un ítem (`Superman`) tendeixen a no sentir-se atrets per un altre (`Just My Luck`). <h1><img width="350" src="https://i.imgur.com/6BGhCCW.png"></h1> --- ### Recomanacions heurístiques basades en la *semblança entre usuaris* Donada una definició de distància entre usuaris, podriem pensar en una proposta inicial (molt simple) de recomanació a un usuari $A$: + Podem buscar un usuari semblant a $A$, $A'$, i recomanar alguna pel·licula que hagi agradat a $A'$ i que $A$ no hagi vist. **Observació**: Aquesta estratègia no és perfecte, atès que podríem recomanar pel·lícules que tothom a puntuat malament excepte $A'$. Una possible solució a aquest problema és fer una ponderació de les puntuacions amb tots els usuaris. Aquesta serà la nostra primera proposta de recomanador, que és **heurística**! --- ### Exemple  --- ### Exemple  --- :::info :bulb: **Compte**! El mètode que hem proposat no està basat en optimitzar numèricament l'error empíric. És només una aproximació heurística que "per construcció" probablement ens dóna uns ítems que poden interessar a l'usuari. A continuació veurem com aplicar mètodes d'optimització a la recomanació. ::: --- ## Recomanacions col·laboratives *basades en ítems* --- ### Recomanacions col·laboratives *basades en ítems* Anem ara a veure una alternativa al mètode anterior que ens permet fer recomanacions col·laboratives basades en la **semblança entre ítems**. + Això és especialment útil quan no tenim molta informació de l'usuari a la matriu $U$ (a la pràctica és més normal tenir informació abundant sobre un ítem que sobre un usuari). --- ### Mètodes col·laboratius basats en ítems La utilitat $u'(c,s$) de l'ítem $s$ per l'usuari $c$ s'estima a partir de les utilitats $u(c,s_i)$ assignades per l'usuari $c$ als ítems $s_i$, ponderades segons la **semblança entre els ítems**. En aquest cas el problema és definir què entenem per semblança entre items: + La idea intuïtiva és que dos ítems seran semblants si han estat valorats de la mateixa forma per un nombre important d'usuaris. --- ### Mètodes col·laboratius basats en ítems Si volem saber la utilitat $u'(c_j,s_p)$ de l'ítem $s_p$ per l'usuari $c_q$, analitzem la fila $c_q$ de la matriu: <h1><img width="350" src="https://i.imgur.com/yDt8CZS.png"></h1> $$ u'(c_q,s_p) = \sum_{j=1}^n \alpha_{s_p s_j} u(c_q,s_j) $$ on $\alpha_{s_p s_j}$ és $0$ si no coneixem $u_{c_q s_j}$ i un pes que depèn de la semblança entre els items $s_p$ i $s_j$ en el cas contrari. --- ### Implementació + Si calculem la matriu $U^t$, llavors, aplicant els meteixos mètodes que hem vist pels usuaris podem fer una recomanació basada en ítems i no en usuaris. + La gran diferència entre els dos mètodes que hem vist és que, tot i que els dos casos hem de processar tota la taula (i això és costós!), les comparacions entre ítems canvien en el temps més lentament que les comparacions entre usuaris i per tant es més estable (però una mica menys precís des del punt de vista de l'error empíric). + A nivell d'implementació al món real, ens permet crear de forma *off-line* una llista ponderada amb els ítems més afíns a cada ítem, i quan fem una recomanació a un usuari només cal mirar aquesta llista, independentment de qui és l'usuari. --- ### Resum sobre recomanació col·laborativa Recomanació col·laborativa basada en usuaris: 1. Identificar $I$, el conjunt d'items que ha valorat l'usuari objectiu. 2. Identificar $N$, el conjunt d'usuaris que han valorat 1 o més items del conjunt $I$. 3. Calcular la semblança de cada usuari d'$N$ a l'usuari objectiu. 4. Predir les valoracions de l'usuari objectiu per $I^c$, el conjunt d'items que no ha valorat. 5. Recomanar els $n$ productes de $I^c$ amb valoració més alta. --- Recomanació col·laborativa basada en ítems: + Identificar $U$, el conjunt d'usuaris que han valorat l'ítem objectiu. + Identificar $N$, el conjunt d'ítems que han estat valorat pels usuaris de $U$. + Calcular la semblança entre cada element de $N$ i l'ítem objectiu. + Predir la valoració de l'ítem objectiu. --- ### El problema de la recol·lecció de dades Quan construïm la base de dades podem usar dos estratègies: l'explícita i la implícita. + La **recol·lecció explícita** de dades pot ser: demanar a un usuari avaluar un ítem segons una escala numèrica, demanar a un usuari una ordenació d'un conjunt d'ítems segons les seves preferències, presentar a l'usuari dos ítems i preguntar-li quin prefereix, demanar a l'usuari que faci una llista dels ítems que li agraden, etc. + La **recol·lecció implícita** de dades pot ser: anotar els ítems que consulta a la base de dades, analitzar els periodes de temps d'aquestes consultes, analitzar la xarxa social de l'usuari i descobrir gustos semblants, etc. --- ### El problema de la recol·lecció de dades + La **recol·lecció explícita** permet una millor *personalització* però no sempre és possible obtenir aquest tipus de dades. L'obtenció d'aquest tipus de dades és percebuda com massa intrussiva per part dels usuaris i moltes vegades és voluntaria. + La **recol·lecció explícita** està biaixada cap a usuaris polaritzats. + La **recol·lecció implícita** és més simple i és menys intrussiva amb l'usuari, però no permet afinar la personalització com en el cas anterior. + La **recol·lecció implícita** no té el problema de la polarització. --- ### Recomanació (no col·laborativa) basada en el contingut + Els sistemes col·laboratius purs usen exclusivament la matriu de puntuacions dels usuaris, però és evident que podem millorar-ho si tenim informació de l'usuari (p.e. dades demogràfiques) i dels ítems (director de la pel·lícula, gènere, etc.). + Els mètodes no col·laboratius basats en el contingut recomanen ítems a partir de comparar descripcions del contingut de cada ítem a representacions dels continguts dels ítems que sabem interessen a l'usuari. + Per a certs ítems pot ser difícil, però per *ítems textuals* (llibres, noticies, pàgines web, blogs, etc.) és un camp bastant explotat. --- ### Models Híbrids + Els models col·laboratius i els no col·laboratius es poden combinar de moltes maneres. + La més òbvia és que cada model produeixi el seu ranking i llavors produir un ranking agregat. + També podem calcular un ranking agregat ponderat, en el que el pes del component col·laboratiu s'incrementa a mesura que creix el nombre d'usuaris que accedeixen a l'item. --- ### Mètriques d'avaluació + La qualitat d'un sistema de recomanació es pot avaluar comparant les recomanacions que fa el mètode desenvolupat amb les avaluacions d'un conjunt de test (amb avaluacions conegudes d'usuaris) que no s'han fet servir per la construcció del sistema. + **Mètrica de precisió de la predicció**: La mètrica més usada és l'**error absolut mig**, que es defineix com la diferència absoluta mitja entre les avaluacions predites i les reals: \begin{equation} MAE = \frac{\sum_{\{i,j\}} |u'(i,j)-u(i,j)|}{N} \end{equation} on $u'(i,j)$ és l'avaluació predita de l'usuari $i$ per l'item $j$, $u(i,j)$ és l'avaluació real, i $N$ és el nombre d'avaluacions del conjunt de test. --- ### Conclusions + La recomanació col·laborativa basada en ítems és més estable que la recomanació col·laborativa basada en usuaris, però és menys precisa des del punt de vista de l'error empíric. + El mètode col·laboratiu basat en ítems funciona millor que el basat en usuaris en bases de dades esparses i el basat en usuaris funciona millor en bases de dades denses. + La recomanació basada en el contingut pot ajudar, sobretot en escenaris amb poques dades. + El principal problema és com tractar els nous usuaris i els nous ítems (**cold start problem**). + Els sistemes de recomanació són un objectiu clar per la manipulació fraudulenta (penseu en un recomanador de noticies) i generen problemes ètics importants! --- ### Exemple no estàndard de recomanació <center><img width="550" src="https://i.imgur.com/C9LMmVE.jpg"></center> --- ## Problemes pràctics + Com fer que els usuaris revelin les seves preferències? + Com aconseguir puntuacions per tots els productes (no només aquells que els usuaris odien o estimen!) + Com actualitzo el recomanador amb el pas del temps? Quin és el temps de vida de les valoracions dels usuaris? --- ## Problemes ètics + Com evito la difusió de contingut inapropiat? + Privacitat: + Quines dades personals és ètic demanar? + Quin control li dono a l'usuari sobre les seves dades? + Opacitat: Com li explico a l'usuari "perquè" li he fet una certa recomanació? + Justícia: discrimino algun grup sociodemogràfic (raça, gènere, etc.)? + Quins efectes socials pot tenir el meu recomanador?