Filtre col·laboratiu

Podem definir el filtre col·laboratiu com la sinergia que es duu a terme entre individus o grups d'individus que, mitjançant una dinàmica de treball adequada, assoleixen millor uns objectius determinats, que possiblement no haurien assolit per separat, o bé que ho fan optimitzant més els propis recursos.

El sistema de recomanació basat en algorismes de filtrat col·laboratiu utilitza les valoracions dels usuaris sobre certs elements del conjunt total per predir valoracions en la resta dels elements i recomanar els de major valoració predita.

Història i situació actual

Deixant al marge el mètode Delphi creat en 1953 i el fallit experiment Firefly gestat en l'Institut Tecnològic de Massachusetts per Patti Maes. En un començament els sistemes de recomanació eren coneguts tan sols com a filtres col·laboratius i els primers treballs daten de principis dels anys 90. El terme va ser encunyat en 1992 per a un sistema de filtrat de correu electrònic no automatitzat. En 1994 es va desenvolupar el primer "workshop" en Berkeley on es va veure la utilitat en diverses àrees dels primers algorismes simples d'aquest tipus. També es van identificar algunes qüestions importants per desenvolupar d'aquests algorismes: Escalabilidad, Viabilitat econòmica, puntuacions implícites i explicites... Un dels grups d'investigació pioners en el desenvolupament del filtrat col·laboratiu va ser el projecte GroupLens de la universitat de Minesota que encara roman molt actiu i que ha proporcionat una gran part de la base algorítmica de molts sistemes de recomanació. Van ser els primers a introduir el filtre col·laboratiu automàtic usant un algorisme de recerca de veïns per proporcionar prediccions en els grups de notícies de Usenet. D'aquest grup d'investigació va partir també la iniciativa empresarial NetPerceptions, buidant gran part dels dubtes sobre la viabilitat econòmica d'aquests projectes. En l'actualitat és un camp que es troba molt actiu i genera un gran nombre de publicacions i congressos tots els anys. I és que el filtrat col·laboratiu és un aspecte de gran importància dins de les xarxes socials i la petita revolució que ha suposat l'anomenada "Web 2.0".

Metodologia

L'objectiu és suggerir nous elements a un usuari basant-se en les seves eleccions anteriors i en eleccions de gent amb similar historial de ratings o valoracions. Existeixen dues formes de recollir aquestes valoracions. Una és de forma explícita, és a dir l'usuari assigna una puntuació a cada element que seria un valor numèric discret entre un màxim i un mínim. La segona forma és recollir les valoracions implícitament, extraient la informació pertinent de les accions de l'usuari. Per exemple el temps que passa llegint una determinada pàgina web, els enllaços que segueix, el nombre de vegades que s'escolta una cançó, aquesta seria una aproximació més clàssica de mineria de dades. Una vegada que es té suficient informació de l'usuari es passa a la fase de predicció i recomanació. Predicció fa referència a estimar que valoració donaria l'usuari a cada element mentre que recomanació es refereix a extreure els N elements més recomanables (Top-N recommendation).

Tipus

Algorismes de filtrat col·laboratiu basats en memòria, o algorismes de veïns propers (Nearest Neighbour)

Utilitzen tota la base de dades d'elements i usuaris per generar prediccions. Primerament empren tècniques estadístiques per trobar a veïns, és a dir usuaris amb un historial de valoracions sobre els elements similar a l'usuari actual. Una vegada que s'ha construït una llista de veïns es combinen les seves preferències per generar una llista amb els N elements més recomanables per a l'usuari actual. Entre els seus inconvenients es troba la necessitat de disposar d'un nombre mínim d'usuaris amb un nombre mínim de prediccions cadascun, inclòs l'usuari pel qual es pretén realitzar la recomanació.

Existeixen diverses mesures per a aquest càlcul, sent les més usades el Coeficient de correlació de Pearson i el Vector de Similitud o Cosinus.

Explicació de l'algoritme basat en memòria

Quan l'usuari actiu sol·licita una recomanació, la idea general en aquest tipus d'algorismes consisteix a vincular-ho amb altres usuaris del sistema. El criteri per vincular dos usuaris és que tots dos hagin puntuat elements en comú. Al conjunt d'usuaris amb què s'aconsegueix vincular a l'usuari actiu ho anomenem conjunt de veïns o veïnat.

Són veïns de l'usuari actiu aquells que tenen un conjunt d'ítems puntuats en comú amb ell, sense importar que les preferències sobre aquests siguin molt variades. El concepte de similitud s'expressa mitjançant un valor, que es calcula considerant els elements puntuats en comú. Si tots dos puntuen de manera similar aquests elements, s'obté un valor alt de similitud, mentre que si expressen valoracions oposades s'obté un valor de similitud baix.

La idea en un algorisme basat en memòria és calcular les prediccions sobre aquells elements que els veïns coneixen, però que són desconeguts per a l'usuari actiu. A aquest conjunt d'elements l'anomenarem conjunt d'ítems recomanables, atès que són potencialment els elements que poden arribar a ser recomanats.

Per realitzar la recomanació es calcula la predicció del valor per a cada element del conjunt d'ítems recomanables. Una vegada calculats tots aquests valors pren una quantitat arbitrària d'elements, els quals tenen associats els majors valors dels valors de predicció.

La fórmula general utilitzada per al càlcul de la predicció dels valors és la presentada en la Formula A. Es defineix un vot Vi,j com el valor brindat per l'usuari i per a l'ítem j. Es considera a més vj com el valor mitjà dels vots de l'usuari j, i w(a, i) com el valor de similitud entre l'usuari a i l'usuari i.

$p_{a,j}={\bar {v_{a}}}+k\sum _{i=1}^{n}w(a,i)(v_{i,j}-{\bar {v_{i}}})$

En aquesta fórmula, n representa la quantitat de veïns en el sistema i k és un factor de normalització de l'equació. Analitzant la fórmula, es pot observar que el primer terme és el valor mitjana de votació de l'usuari actiu i el segon representa la variació del valor a predir pel que fa a aquesta mitjana. Aquesta variació es calcula considerant tots els usuaris que tenen elements en comú amb l'usuari actiu i que a més han puntuat l'element j.

Pel que fa a la sumatòria present en a Fórmula A es desglossa per a la seva explicació en major detall. En primer lloc és necessari determinar si els vots dels veïns són positius o negatius pel que fa a l'ítem j. Una possibilitat és comparar aquest vot amb el valor mitjà de l'escala de votació. En tal cas no es consideren les diferents personalitats dels usuaris. Si en comptes d'utilitzar el valor mitjà s'utilitza la mitjana de les votacions registrades de l'usuari com a valor neutre, s'assumeix que els vots superiors a la mitjana són positius i els menors negatius (Fórmula B). D'aquesta forma es té en compte la tendència o personalitat de l'usuari en votar, atès que l'escala de valor dels usuaris és variada i un vot acceptable per a un usuari pot estar contingut en un rang de valors diferent al d'un altre usuari. Per exemple, considerant una escala de valor d'1 a 5, la mitjana de votacions de l'usuari u1 igual a 2 i la mitjana de l'usuari u2 igual a 4. Es vol saber el grat o desgrat d'una cançó que tant l'usuari u1 com l'u2 li associa un valor igual a 3. Si comparem contra la mitjana de votacions de cada usuari es conclou que a l'usuari u1 li agrada més la cançó que a l'usuari u2, atès que per u1 el valor de 3 supera la seva mitjana de votació (2) mentre que per u2 no aconsegueix la seva mitjana (4). No obstant això en cas de considerar la mitjana de l'escala de votacions (3) en comptes de la mitjana de cada usuari, es conclouria que als dos usuaris li agrada de la mateixa forma, la qual cosa no seria real.

Aquest terme es multiplica en la sumatòria pel valor de similitud entre l'usuari actiu a, i el veí i, w(a, i), el qual és positiu en cas de ser similars, i negatiu si són diferents.

La multiplicació d'aquests dos membres de la sumatòria provoca que cada terme d'ella sigui positiu si l'usuari i va votar positivament a l'element j i a més és similar a l'usuari actiu, o bé, si tots dos usuaris són diferents i l'element j va ser valorat negativament per l'usuari i. Anàlogament s'obtindrà en la sumatòria un terme negatiu quan tots dos usuaris són similars i l'usuari i va valorar negativament l'element en qüestió. Això succeeix també quan l'usuari i valora positivament l'element però tots dos usuaris són diferents.

$(v_{i,j}-{\bar {v_{i}}})$

Normalitzant el valor obtingut per la sumatòria i sumant-ho a la mitjana de vots de l'usuari actiu, s'obté la predicció de vot de l'usuari actiu sobre l'element j.

Per determinar la similitud entre dos usuaris, w(a, i), un dels mecanismes més utilitzat és el Coeficient de correlació de Pearson.

Si bé en el càlcul de predicció presentat en la Fórmula A es consideren tots els usuaris que tenen vots en comú amb l'usuari actiu, una de les idees més utilitzades en filtrat col·laboratiu és la dels veïns més propers (K nearest neighbors, KNN). Això implica la selecció d'un subconjunt d'usuaris que compleixin una condició respecte a la similitud amb l'usuari actiu per ser considerats en el càlcul de la predicció. La raó de considerar un conjunt reduït de veïns és augmentar l'eficiència de l'algorisme, disminuint el temps de còmput en el càlcul de predicció. Per exemple es consideren, o es prenen els k veïns amb menor distància.

En el cas de decidir utilitzar un subconjunt dels veïns possibles, queda per determinar quin és la quantitat màxima de veïns que hauria de seleccionar-se. S'han realitzat estudis que demostren que en variar el valor del k, varia la precisió dels resultats. A més aquest valor depèn de grandària del conjunt de dades, per tant s'estudia en cada cas el k més adequat per al conjunt de dades considerat.

Algorismes de filtrat col·laboratiu basats en Model

Desenvolupen primer un model dels ratings de l'usuari. Tracten el problema com un problema de predicció estadística i calculen el valor esperat per a cada ítem en funció dels ratings anteriors. Per a això s'utilitzen diferents algorismes d'aprenentatge basats en classificació (Clustering), Xarxa bayesiana i mètodes basats en normes. Per exemple utilitzant clustering es tracta de classificar a un usuari en particular dins d'una classe d'usuaris i a partir d'aquí s'estimen les probabilitats condicionades d'aquesta classe cap als elements a avaluar.

En general, davant les consultes responen més ràpid que els basats en memòria, però per contra necessiten un procés d'aprenentatge intensiu.

Explicació de l'algoritme basat en Model

Des de la perspectiva probabilística, la tasca del filtrat col·laboratiu pot ser vist com el càlcul del valor esperat d'un vot, donada la informació dels valors brindats pels usuaris. Per a l'usuari actiu, s'intenta predir el vot per a un ítem no avaluat per ell. Si es pren una escala de valors de 0 a m, es pot veure en la Fórmula C com es planteja la predicció del valor considerant el valor esperat del vot de l'usuari a sobre l'ítem j.

$p_{a,j}=E(v_{a,j})=\sum _{i=0}^{m}Pr(v_{a,j}=i/v_{a,k},k\in I_{a})i$

Dues de les alternatives d'implementació més usades per a aquest mètode són el model de clusters i el model de xarxes bayesianes. Segons l'estudi realitzat per Breese, Heckermann i Kadie, el qual és de referència en la majoria dels treballs realitzats sobre aquest tema, el model de xarxes bayesianes resulta més efectiu que el model de clusters. Aquest model consisteix a formar xarxes, on els nodes es corresponen amb cada ítem del domini d'aplicació, i els estats dels nodes, amb els possibles valors de vots sobre els ítems. S'aplica l'algorisme sobre el conjunt de dades d'entrenament per trobar dependències entre els elements i construir les xarxes. A partir del model construït es calculen les prediccions de vots. Cada taula de probabilitat condicional pot ser representada per un arbre de decisió que codifica les probabilitats condicionals per a aquest node.

Per exemple, en un domini de sèries de televisió es vol predir la probabilitat que a l'usuari actiu li interessi mirar la sèrie "Melrose Place". Després d'entrenar el model es troba que "Melrose Place" està relacionat amb els ítems "Beverly Hills, 90210" i "Friends" i l'arbre de decisió per a aquest ítem és el que es mostra en la Figura D. Les barres que estan en la part més baixa de la figura indiquen la probabilitat de mirar "Melrose Place" condicionat al fet que va veure els programes pares. Per determinar la preferència de l'usuari actiu es navega a la xarxa i es calcula la probabilitat de preferència de l'usuari actiu sobre l'ítem "Melrose Place".

Cal observar que aquest model compta amb alguns desavantatges importants. En primer lloc, és necessari disposar d'una gran quantitat de dades d'entrenament per poder aconseguir un model de gran grandària que permeti realitzar bones prediccions. No obstant això, comptar amb un conjunt de dades important, pot ocasionar que el model sigui extremadament gran, requerint molt temps d'entrenament. Això es veu agreujat quan s'aplica aquest model en sistemes de filtrat col·laboratiu on l'escala de votació pot tenir molts valors, a diferència de l'exemple on es considera una escala binària (mirar o no mirar). Això es deu al fet que els estats possibles dels nodes són precisament els valors possibles de valors d'usuaris sobre ítems. Per aquesta raó es recomana utilitzar aquest model en sistemes on la valoració de l'usuari sobre l'ítem és binària o amb una grandària reduïda de valors. Si bé té aquests desavantatges, com a avantatge important s'esmenta la rapidesa en el càlcul d'una predicció després de tenir un model entrenat.

Híbrids

Combinen algorismes basats en memòria i en model. Aquests milloren l'actuació de predicció. I molt important, venç els problemes de densitat i pèrdua d'informació. Tanmateix, augmenta la complexitat i s'encareix la implementació.

Altres aspectes

El consum de memòria i de CPU de qualsevol sistema de filtrat i informació és molt elevat al tractar amb moltes dades. L'optimització dels algorismes per millorar el seu rendiment és un dels principals camps d'investigació dins del filtrat col·laboratiu. Algunes característiques desitjables en aquests sistemes suposen una modificació constant de les dades, la qual cosa fa necessaris algorismes que tinguin un cost d'actualització baix. Per exemple els nous elements han d'aparèixer en el sistema al més aviat possible. També es requereix una millora contínua del perfil de l'usuari. És a dir, que l'usuari percebi que ”l'esforç” d'avaluar nous elements es vegi compensat amb unes millores en les recomanacions que s'obtenen.

A més dels aspectes tècnics, la implantació de sistemes de recomanació pot plantejar problemes socials com la privadesa dels usuaris. És un assumpte delicat, ja que per tenir un bon funcionament és necessari conèixer la màxima informació possible de l'usuari. Una primera solució és mantenir tan sols la informació relacionada amb les votacions i conèixer de l'usuari només un pseudònim, però això xoca amb el model de negoci basat en publicitat que s'utilitza abundantment en l'actualitat.

Esmentar també que existeixen investigacions dirigides a comprendre la relació entre els usuaris i els sistemes de recomanació. Psicològicament és conegut des de fa temps com l'opinió dels altres modifica l'opinió pròpia. També es percep com el mostrar prediccions del vot d'un usuari influencia el mateix vot futur.

Exemples

Logotip d'Amazon, un exemple de filtre col·laboratiu.

Logotip de Facebook, un exemple de filtre col·laboratiu.

Amazon.com (Pàgina de compra per internet)
Amie Street (Serveis de música)
Baynote (Servei de recomanació via web)
ChoiceStream (Sistema de recomanació de productes)
Collarity (Plataforma multimèdia de recomanació)
Daily Me (Sistema de recomanació de notícies)
Genius (Servei de música, forma part de la tenda online d'iTunes)
Last.fm (Sistema de música)
Facebook (Xarxa social)
Strands (Tecnologia de recomanació social)
Netflix (Servei de lloguer de DVD amb recomanació segons gustos)
Pandora (servei de música)
Reddit (Sistema de recomanació de notícies)
Slacker (servei de música)
StumbleUpon (Recomanació pàgines web)
StyleFeeder (Cerca personalitzada de compres)
WeScoreGames (Recomanació de jocs)
FilmAffinity (Recomanació de pel·lícules)