Matrix Factorization In Recommender SystemsYONG ZHENG
油
The document discusses matrix factorization techniques for recommender systems. It begins with an overview of recommender systems and their use of matrix factorization for dimensionality reduction. Principal component analysis and singular value decomposition are described as early linear algebra techniques used for this purpose. The document then focuses on how these techniques evolved into basic and extended matrix factorization methods in recommender systems, using the Netflix Prize competition as an example.
Latent factor models for Collaborative Filteringsscdotopen
油
The document discusses latent factor models for collaborative filtering. It describes how latent factor models (1) map both users and items to a latent factor space to characterize them, (2) approximate ratings as the dot product of user and item vectors, and (3) can be used to predict unknown ratings. It also covers techniques like stochastic gradient descent and alternating least squares for training latent factor models on explicit and implicit feedback data.
Matrix Factorization Techniques For Recommender SystemsLei Guo
油
The document discusses matrix factorization techniques for recommender systems. It begins by describing common recommender system strategies like content-based and collaborative filtering approaches. It then introduces matrix factorization methods, which characterize both users and items by vectors of latent factors inferred from rating patterns. The basic matrix factorization model approximates user ratings as the inner product of user and item vectors in the joint latent factor space. Learning algorithms like stochastic gradient descent and alternating least squares are used to compute the user and item vectors by minimizing a regularized error function on known ratings.
Sintesi automatica di una metrica di similarit tra stringhe tramite tecniche...mfurlanetto
油
Tesi di laurea magistrale che prevede la creazione e analisi di nuove metriche di distanza tra stringhe finalizzata all'estrazione automatica di entit basate su sintassi
Approximate Algorithms for the Network Pricing Problem with Congestion - MS T...Desir辿e Rigonat
油
Presentation for the final dissertation for my MS degree in Computer Science & Engineering.
Subject is Mathematical Optimization in the field of Network Pricing Problems.
This work is the result of a research carried on from September 2011 to August 2012; part of this work has been developed at the Graphes et Optimisation Math辿matique (G.O.M.) group of the Universit辿 Libre de Bruxelles, under the supervision of Professor Martine Labb辿; further development and experimentation have been carried on at the Laboratorio di Ricerca Operativa of the Universit degli studi di Trieste with Professor Lorenzo Castelli as supervisor.
Presentazione della Tesi di Laurea Specialistica : STRUMENTI PER LA GENERAZIO...Boymix81
油
Breve presentazione del lavoro svolto per la tesi : STRUMENTI PER LA GENERAZIONE AUTOMATICA DI TEST STRUTTURALI E FUNZIONALI, scaricabile dal sito web http://boymix81.mynickname.info
Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi d...Stefano Costanzo
油
Lo scopo di questo lavoro di tesi 竪 lo sviluppo di un approccio meta-euristico basato sugli algoritmi genetici per la risoluzione di problemi multi-obiettivo sia di programmazione lineare che di ottimizzazione combinatoria. Alcune tipologie di questi problemi si prestano ad essere risolti mediante algoritmi ad-hoc che fanno leva sulle caratteristiche strutture matematiche delle variabili di ingresso con cui sono modellati, cos狸 come evidenziato nella vasta letteratura esaminata. Il presente lavoro propone invece di generalizzare queste tecniche in modo da poter offrire uno o pi湛 algoritmi che sappiano gestire contemporaneamente il maggior numero di classi di problemi. Inoltre, lintrinseca complessit dovuta alla natura multi-obiettivo dei problemi affrontati, richiede di spostare lattenzione dai metodi deterministici-tradizionali a quelli evolutivi-euristici. Viene quindi delineato il profilo di un algoritmo genetico capace di elaborare problemi multi-obiettivo con vincoli lineari, non lineari, variabili intere e strutture di variabili combinatorie. Particolare attenzione viene dedicata alle fasi precedenti il ciclo puro di ottimizzazione di un algoritmo genetico, introducendo delle procedure di semplificazione dei sistemi di vincoli lineari e un metodo di eliminazione delle uguaglianze, notoriamente ostiche per gli approcci evolutivi. Risultati sperimentali, su molteplici classi di problemi test, vengono confrontati con algoritmi genetici esistenti mostrando dei comportamenti sicuramente incoraggianti per un raffinamento ulteriore della strategia delineata.
This document summarizes mathematical methods of tensor factorization applied to recommender systems. It discusses motivations and contributions, information overload and recommender systems, matrix and tensor factorization techniques in recommender system literature such as matrix factorization, singular value decomposition, high-order singular value decomposition, and parallel factor analysis. It also covers challenges in context-aware recommender systems and proposed solutions to incorporate contextual information.
Approximate Algorithms for the Network Pricing Problem with Congestion - MS T...Desir辿e Rigonat
油
Presentation for the final dissertation for my MS degree in Computer Science & Engineering.
Subject is Mathematical Optimization in the field of Network Pricing Problems.
This work is the result of a research carried on from September 2011 to August 2012; part of this work has been developed at the Graphes et Optimisation Math辿matique (G.O.M.) group of the Universit辿 Libre de Bruxelles, under the supervision of Professor Martine Labb辿; further development and experimentation have been carried on at the Laboratorio di Ricerca Operativa of the Universit degli studi di Trieste with Professor Lorenzo Castelli as supervisor.
Presentazione della Tesi di Laurea Specialistica : STRUMENTI PER LA GENERAZIO...Boymix81
油
Breve presentazione del lavoro svolto per la tesi : STRUMENTI PER LA GENERAZIONE AUTOMATICA DI TEST STRUTTURALI E FUNZIONALI, scaricabile dal sito web http://boymix81.mynickname.info
Definizione e sviluppo di un algoritmo genetico multiobiettivo per problemi d...Stefano Costanzo
油
Lo scopo di questo lavoro di tesi 竪 lo sviluppo di un approccio meta-euristico basato sugli algoritmi genetici per la risoluzione di problemi multi-obiettivo sia di programmazione lineare che di ottimizzazione combinatoria. Alcune tipologie di questi problemi si prestano ad essere risolti mediante algoritmi ad-hoc che fanno leva sulle caratteristiche strutture matematiche delle variabili di ingresso con cui sono modellati, cos狸 come evidenziato nella vasta letteratura esaminata. Il presente lavoro propone invece di generalizzare queste tecniche in modo da poter offrire uno o pi湛 algoritmi che sappiano gestire contemporaneamente il maggior numero di classi di problemi. Inoltre, lintrinseca complessit dovuta alla natura multi-obiettivo dei problemi affrontati, richiede di spostare lattenzione dai metodi deterministici-tradizionali a quelli evolutivi-euristici. Viene quindi delineato il profilo di un algoritmo genetico capace di elaborare problemi multi-obiettivo con vincoli lineari, non lineari, variabili intere e strutture di variabili combinatorie. Particolare attenzione viene dedicata alle fasi precedenti il ciclo puro di ottimizzazione di un algoritmo genetico, introducendo delle procedure di semplificazione dei sistemi di vincoli lineari e un metodo di eliminazione delle uguaglianze, notoriamente ostiche per gli approcci evolutivi. Risultati sperimentali, su molteplici classi di problemi test, vengono confrontati con algoritmi genetici esistenti mostrando dei comportamenti sicuramente incoraggianti per un raffinamento ulteriore della strategia delineata.
This document summarizes mathematical methods of tensor factorization applied to recommender systems. It discusses motivations and contributions, information overload and recommender systems, matrix and tensor factorization techniques in recommender system literature such as matrix factorization, singular value decomposition, high-order singular value decomposition, and parallel factor analysis. It also covers challenges in context-aware recommender systems and proposed solutions to incorporate contextual information.
Presentazione Aggiornamento Agile Club Sviluppatori PugliaGiuseppe Ricci
油
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.
- The document discusses mathematical methods for tensor factorization applied to recommender systems.
- Tensor factorization techniques can model additional contextual information that standard matrix factorization cannot capture. This allows the recommendations to be more personalized.
- Two main tensor factorization methods discussed are Higher-Order Singular Value Decomposition (HOSVD) and PARAllel FACtor analysis (PARAFAC).
- HOSVD generalizes singular value decomposition to tensors. PARAFAC decomposes a tensor into a sum of rank-one tensors. Both aim to discover latent factors between user data.
Tecniche di fattorizzazione applicate ai recommender systems
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.