Presentazione tenuta per l'aggiornamento agile del club sviluppatori Puglia dove ho fatto un po una summa del mio lavoro di dottorato parlando di recommender systems e tecniche di fattorizzazione applicate a questi sistemi.
1 of 20
Download to read offline
More Related Content
Presentazione Aggiornamento Agile Club Sviluppatori Puglia
1. Semantic
Web
Access and Personalization
Research Group
http://www.di.uniba.it/~swap
Dipartimento
di Informatica
Approcci Matematici per
Recommender Systems
Ricci Giuseppe
PhDS student in Computer Science
27 Novembre 2013
Thu Hub Bari
Club degli Sviluppatori Puglia
2. Short CV
2005: Laurea in Matematica
2006: Corso di Formazione Professionale in Tecnico Informatico
(webmaster)
2008: Mater in Tecnologie per il Telerilevamento Spaziale
2009-2010: Assegnista di Ricerca presso CNR-ISAC uos Lecce
2011-2013: PhD presso Dipartimento di Informatica
Collaborazioni con:
PBX Network srl Roma: realizzazione di un social
network/community virtuale
Studio di grafica Angela Di Liso: realizzazione di siti web con
CMS Wordpress
3. Iniziamo..Recommender Systems
Hanno lobiettivo di orientare l'utente in modo
personalizzato verso oggetti (item) utili o interessanti
in un grande spazio di possibili opzioni [Burke02]
Processano in genere una matrice utenti-item in cui 竪
memorizzato il feedback (rating) degli utenti
[Burke02] Burke, R. Hybrid recommender systems: Survey and experiments. User Modeling and UserAdapted Interaction, 12(4): 331370, 2002.
4. Stato dellarte: tecniche per Matrix Factorization 1/2
Matrice dei rating
Ogni riga di P pu嘆 rappresentare il legame delle associazioni tra un
utente e le features.
Le righe di Q possono rappresentare il legame tra un item e le
features.
xij^ = pi * qj
eij = xij - xij^
eij < eps
Varianti: Regularized MF, BRIS MF, Semipositive and positive MF,
Transductive MF.
5. Stato dellarte: tecniche per Matrix Factorization 2/2
MF usata in letteratura: Singular Value Decomposition (SVD) introdotta per la
prima volta da Simon Funk nel NetFlix Prize (*).
Obiettivo SVD: ridurre la dimensionalit, ossia il rango, della matrice utenti-item
R.
La SVD scompone la matrice dei rating, R, nel prodotto di tre matrici:
R
Matrici ortonormali
P
QT
Matrice diagonale
(*) concorso pubblico organizzato dalla compagnia NetFlix (che offre un servizio di
noleggio di DVD e videogiochi via Internet per individuare un sistema in grado di
migliorare del 10% almeno le prestazioni dell'algoritmo di suggerimento dei film. Il 21
settembre 2009, il premio di 1.000.000 di dollari USA 竪 stato vinto dal team BellKors
Pragmatic Chaos, che ha battuto lalgoritmo Cinematch, usato fino ad allora da NetFlix.
6. Approccio multidimensionale
Le matrici e le tecniche di fattorizzazione di matrici presentano un problema:
prendono in considerazione solo le usuali dimensioni di utenti e item. Questo
non permette di integrare informazioni quali possono essere ad esempio quelle
relative al contesto.
items
Tensore
users
context
7. Tensori e Fattorizzazioni Tensoriali
Tensore: una matrice a pi湛 dimensioni.
Anche ai tensori 竪 possibile applicare le tecniche di fattorizzazione che
generalizzano la MF.
In letteratura la tecnica pi湛 utilizzata 竪 quella della High Order Singular Value
Decomposition (HOSVD).
8. HOSVD nei RS
Baltrunas et al. presentano un modello che viene denominato Multiverse
Recommendations: 竪 in grado di integrare le informazioni relative al contesto modellando
i dati come user-item-contesto mediante un tensore N-dimensionale;
Symeonidis et al. HOSVD applicano HOSVD ad un sistema di social tagging.
Social tagging: processo tramite il quale gli utenti inseriscono metadata sottoforma
di keyword (o parole chiave) al fine di classificare e categorizzare gli items. Consigliano
agli utenti dei tags in base ai tag che gli altri utenti hanno usato per gli stessi articoli, al
fine di sviluppare un consenso comune su quali tag descrivono meglio un elemento.
Lalgoritmo proposto dagli autori:
Sviluppa un unico framework
Modella i tre tipi di entit che si riscontrano in un social tagging system: utenti, items e
tags;
Chen et al. propongono CubeSVD: Personalized web search per scoprire le relazioni
latenti tra: user, query, web pages. Tensore ricostruito misura le associazioni tra
utenti, query, pagine web. Elementi: < u, q, p, w>: w misura il gradimento della pagina p
proveniente come risultato della query q fatta dall'utente u.
9. Vantaggi e Svantaggi
Dallanalisi della letteratura sulla HOSVD emergono vantaggi e svantaggi:
Svantaggi Multiverse Reccomendation TF
Risorse computazionali non indifferenti
Applica abbastanza pesantamente lalgoritmo di minimizzazione di una
funzione (Stochastic Gradient Descend, SGD).
Non sempre corretto usare il valore 0 per i valori mancanti
Svantaggi HOSVD applicata al sistema social tagging
Non tiene conto degli aspetti computazionali: ricavare 9 matrici con la
SVD 竪 costoso
Svantaggi CubeSVD
Elevata quantit di dati da gestire
Sparsit del tensore
Nessuna alternativa alluso del valore 0.
10. Altre TF e PARAFAC
Oltre a HOSVD esistono altri tipi di fattorizzazione tensoriale:
PARAFAC o CANDECOMP
TUCKER, PARATUCKER
DEDICOM
.
Esaminiamo PARAFAC.
Dato un tensore X, PARAFAC lo decompone come somma di tensori di rango 1:
PARAFAC poco applicata nellambito dei RS.
11. PARAFAC nella letteratura dei RS e non solo
Lalgoritmo TFMAP usa PARAFAC per il top-N context-aware recommendations
di mobile applications. Tensore di 3 dimensioni fattorizzato: users, items e context
types. Calcola per luser m la preferenza per litem i sotto il context type k.
Luser m preferisce usare una app, litem i , quando 竪 allaperto ma se si trova in un
luogo chiuso (dunque in un contesto diverso) preferirebbe usarne unaltra.
OUTSIDER: Acar et al. usano PARAFAC applicata ai dati di EEG
(electroencephalography) concentrandosi sul problema dei missing values.
Sviluppano un algoritmo, CP-WOPT (CPWeighted OPTimization), che
implementa una fattorizzazione di tipo PARAFAC ma pesata cio竪 modella solo i
valori noti.
Con delle sperimentazioni numeriche gli autori dimostrano come CP-WOPT pu嘆
fattorizzare con successo un tensore con una quantit di dati mancanti pari o
superiore al 70%. CP-WOPT 竪 pi湛 veloce e accurato di altri algoritmi noti in
letteratura.
Yue Shi, Alexandros Karatzoglou, Linas Baltrunas, Martha Larson, Alan Hanjalic, and Nuria Oliver. Tfmap:
optimizing map for top-n context-aware recommendation. In Proceedings of the 35th international ACM SIGIR
conference on Research and development in information retrieval , SIGIR 12, pages 155164, New
York, NY, USA, 2012. ACM.
E. Acar, D. Dunlavy, T. Kolda, M. M淡rup. Scalable Tensor Factorizations with Missing Data. In Proc. of the Tenth
SIAM International Conference on Data Mining, SIAM, 2010.
12. Challenges affrontate
Gestione dellinformazione contestuale: Tensori
tempo
posizione geografica
social context
attivit
weather
emotional state
social network .
Utilizzo delle tecniche di TF PARAFAC
Gestione opportuna dei missing value CPWOPT.
Challenge aperta:
identificare una o pi湛 tecniche che permettono di capire se un fattore
contestuale influenza il rating o meno.
ES.: lutente vede a casa (contesto: posto) il film Matrix, 竪 da solo (contesto:
compagnia), il tempo (contesto: weather) 竪 bello. Il rating 竪 4.
Domanda: se lutente avesse visto il film al cinema o con gli amici il rating
sarebbe cambiato?
13. Sperimentazioni con CP-WOPT 1/3
CP-WOPT 竪 stato sviluppato in Java in modo da avere un algoritmo equivalente.
Con il codice sviluppato sono state condotte diverse sperimentazioni:
1. un caso di studio piccolo
2. Movielens 100k.
Per 1. : 7 utenti reali a cui 竪 stato chiesto di votare un certo numero di film
(appartenti al dataset Movielens) considerando 3 fattori contestuali cio竪 se
preferiscono vedere il film:
(i) a casa o al cinema;
(ii) con gli amici o con il partner;
(iii) con o senza la famiglia.
I rating variano nel range 1-5 nel senso che per ciascun fattore contestuale:
i rating 1 e 2 esprimono un forte e medio interesse per il primo termine
i rating 3 esprime neutralit;
i rating 4 e 5 esprimono un modesto e forte preferenza per il secondo termine.
14. Metriche di Valutazione
Mean Absolute Error (MAE):
1 N
MAE = 奪 yi - ri
N i=1
N
Root Mean Square Error (RMSE):
奪(y - r )
i
RMSE =
Accurancy:
脱 errors 卒100 旦
acc =100 - 巽
歎
竪 known _ values 淡
Coverage:
脱 errors 卒100 旦
cov =100 - 巽
歎
竪 unknown _ values 淡
i=1
N
i
2
15. Sperimentazioni con CP-WOPT 2/3
I risultati sono misurati in termini di accurancy (acc) come la percentuale di
valori correttamente ricostruiti e di coverage (cov) come la percentuale di
elementi non nulli ricostruiti.
Con lipotesi di 100000 iterate massime:
acc = 94.4%
cov = 91.7%.
Da questo studio limitato
Con questo metodo si pu嘆 dedurre:
American Pie 竪 tipicamente guardato
a casa, con gli amici senza la famiglia;
Titanic 竪 visto al cinema
con il partner o la famiglia.
16. Sperimentazioni con CP-WOPT 3/3
Per 2. :
Si tratta di una sperimentazione in vitro che usa CP-WOPT per un set di dati
pi湛 ampio estratto da Movielens 100k.
Input: tensore di dimensioni 100 users, 150 movies, 21 occupations
(informazione contestuale).
Misure di accuratezza:
acc = 92,09%
cov = 99,96%
MAE = 0,60
RMSE = 0,93.
Questi risultati sono in linea con quelli riportati in letteratura.
17. Task: importanza fattore contestuale
I dati di Movielens 100k sono stati usati per capire se un fattore contestuale 竪
importante o meno.
utenti, film, occupazione dellutente capire se gli utenti che svolgono la
stessa professione hanno un genere di film preferito, per es: i poliziotti
preferiscono i film polizieschi? I medici o infermieri preferiscono i film
ambientati in ospedale?
In Movielens 100k ci sono 943 utenti, 1682 film, 19 generi, 21 occupazioni.
CP-WOPT
Tensore sparso rating
Tensore ricostruito
Uso di una tecnica basata sulle medie e una sulla tecnica
dellAnalisi delle Corrispondenze: risultati contrastanti!!!
Smontaggio del tensore
per recuperare i dati
generi/occupazioni
18. Ulteriori Sperimentazioni
ConTexTRS: sistema di suggerimento turistico (www.contextrs.it) presentato
nel corso del Festival dellInnovazione a Maggio 2013 acquisizione di dati.
Ci sono 51 utenti, 63 POI e 4 contesti.
Dataset molto sparso: 246 rating noti su 12852 elementi del tensore.
MAE = 0.4730 e RMSE = 1.0591
acc = 91.8919 e cov = 99.8816
LDOS - CoMoDa dataset: contiene i rating dati dagli utenti per i film ma con
contesto esplicito.
268 utenti, 4381 film, 19 features contestuali (ce ne sono altre, sono state
selezionate solo queste):
Time, Daytype, Season, Location, Weather.
MAE = 0.5456 e RMSE = 0.82
acc = 91.41 e cov = 99.99
19. Tirando le somme.
Lapproccio con i Tensori:
permette di incorporare linformazione contestuale
竪 possibile applicare le tecniche di fattorizzazione.
Lapproccio con CP-WOPT:
risolve bene il problema dei missing values (ottima coverage)
i risultati ottenuti sono in linea con quelli ottenuti in letteratura
permette di elaborare raccomandazioni comunque buone.
Grosso svantaggio:
lalgoritmo risulta essere lento per grossi dataset!
lalgoritmo sviluppato in Java da problemi con lHeap (occupazione
memoria).
Problemi aperti:
context weigthing sperimentazione con Reti Bayesiane.
#2: Picture recolored and blurred with film grain effect(Advanced)To reproduce the picture effects on this slide, do the following:On the Home tab, in the 際際滷s group, click Layout, and then click Blank.On the Insert tab, in the Images group, click Picture.In the Insert Picture dialog box, select a picture and then click Insert.Select the picture. Under PictureTools, on the Format tab, in the Size group, click the Size and Position dialog box launcher. In the Format Picture dialog box, resize or crop the image so that the height is set to 7.5 and the width is set to 10. To crop the picture, click Crop in the left pane, and in the right pane, under Crop position, enter values into the Height, Width, Left, and Top boxes. To resize the picture, click Size in the left pane, and in the right pane, under Size and rotate, enter values into the Height and Width boxes.Also under PictureTools, on the Format tab, in the Adjust group, click ArtisticEffects, and then click ArtisticEffectsOptions. In the FormatPicture dialog box, click ArtisticEffects in the left pane, and in the ArtisticEffects pane, do the following:Click the button next to Artistic Effect and select Blur. (second row, fifth option from the left)In the Radius box, enter 60. Also in the FormatPicture dialog box, click PictureColor in the left pane. Under Recolor, click the button next to Presets, and then click Blue, Accent color 1 Dark (second row).Select the picture. On the Home tab, in the Clipboard group, click Copy. Press DELETE to delete the picture on the slide.Also on the Home tab, in the Clipboard group, click the arrow below Paste, and then click PasteSpecial. In the PasteSpecial dialog box, select Paste, and the under As select Picture (PNG). Select the picture. Under PictureTools, on the Format tab, in the Size group, enter 7.5 into the Height box and 10 into the Width box.Also under PictureTools, on the Format tab, in the Adjust group, click ArtisticEffects, and the click ArtisticEffectsOptions. In the FormatPicture dialog box, click ArtisticEffects in the left pane, and in the ArtisticEffects pane do the following:Click the button next to Presets and select FilmGrain (third row). In the Transparency box, enter 30%. In the Grainsize box, enter 40%.To reproduce the shape effects on the slide, do the following:On the Home tab, in the Drawing group, click Shapes, and the under Rectangles click Rectangle (first option). On the slide, drag to draw a rectangle.Select the rectangle. Under DrawingTools, on the Format tab, in the Size group, enter 2.21 into the Height box and 10 into the Width box.Right-click the rectangle, select EditPoints, and do the following:Select the top left corner point of the rectangle. Drag the top curve handle (blue line) upward.Select the top right corner point of the rectangle. Drag the top curve handle (blue line) downward.Select the bottom left corner point of the rectangle. Drag the bottom curve handle (blue line) upward.Select the bottom right corner point of the rectangle. Drag the bottom curve handle (blue line) downward.(Note: Your shape may not look like the example above.)On theHome tab, in the Clipboard group, click the arrow next to Copy, and then click Duplicate.Select the second shape. Right-click the shape, select EditPoints. Narrow the shape by selecting the bottom points and dragging them towards the top points. (Note: Your shape may not look like the example above.)Select the first shape. On theHome tab, in the Clipboard group, click the arrow next to Copy, and then click Duplicate.Select the third shape. Right-click the shape, select EditPoints, and then do the following:Narrow the shape by selecting the bottom points and dragging them towards the top points. Select the top left corner point of the rectangle. Drag the top curve handle (blue line) downward.Select the top right corner point of the rectangle. Drag the top curve handle (blue line) upward.Select the bottom left corner point of the rectangle. Drag the bottom curve handle (blue line) downward.Select the bottom right corner point of the rectangle. Drag the bottom curve handle (blue line) upward.(Note: Your shape may not look like the example above.)Press and hold CTRL, and then select all three shapes. Under DrawingTools, on the Format tab, in the ShapeStyles group, click the FormatShape dialog box launcher. In the FormatShape dialog box, click Fill in the left pane, and in the Fill pane, do the following:Select Solid fill.Click the button next to Color and select Black, Text 1 (first row, second option from the left).In the Transparency box, enter 90%.Also in the FormatShape dialog box, click LineColor, and in the LineColor pane select Noline. With all three shapes selected, on the Home tab, in the Drawing group, click Arrange, point to Align, and then do the following:Click Align to 際際滷.Click AlignCenter.