# Cap. 4: Model-Based Collaborative Filtering

### Explain the key differences between model-based collaborative filtering and neighborhood-based collaborative filtering methods.

I metodi neighborhood-based prevedono di lavorare attraverso le similarità tra righe e/o colonne di una matrice associativa, per individuare e pesare i rating da aggregare per stimare i valori mancanti. I N.B. methods possono essere visti come una ricerca dei k-nearest-neighbors (una sorta di clustering, quindi tecniche non supervionate).

I metodi model-based invece usano l'approccio del machine learning supervisionato, cioè:

- i dati si dividono in un training set e un test set
- i dati del training set si usano per derivare (attraverso l'apprendimento automatico) dei valori per i parametri di un modello
- il modello (parametrizzato) viene validato sui dati del test set

Si noti (proprio che nel M.L. in generale) che molti algoritmi di classificazione hanno dei corrispondenti collab. filtering, ma non tutti.

### How do model-based collaborative filtering methods address the issues of space efficiency and computational efficiency compared to neighborhood-based methods?

Un vantaggio dei M.B. è che i modelli tipicamente:

- richiedono meno spazio per essere memorizzati (si memorizzano i parametri appresi invece che tutti i dati)
- sono più veloci da computare

### Describe the concept of Naive Bayes Collaborative Filtering. How does it handle the estimation of unobserved ratings?

Assumendo che i rating siano categoriali, si può modellare il problema di stima dei rating mancanti con un classificatore Naive Bayes:

- ci sono $l$ possibili valori distinti per i rating $v_1, ... , v_l$
- è data una matrice $R \in \{v_1, ... , v_l\}^{m \times n}$ e per ogni utente si ha un insieme $I_u$ degli item valutati
- dato un item non valutato $j\notin I_u$, si vuole stimare per ogni classe $s \in \{1, ..., l\}$ la probabilità che il valore mancante sia quello. Applicando il teorema di Bayes:

$$P(r_{uj} = v_s | I_u) = \frac{P(r_{uj} = v_s)P(I_u | r_{uj} = v_s)}{P(I_u)}$$
- visto che l'obiettivo è confrontare le probabilità associate alle varie classi, e il denominatore $P(I_u)$ è uguale per tutti, si può rimuovere
- Assumendo l'indipendenza dei rating che compongono $P_u$, si può scomporre nella produttoria delle probabilità di osservare ciascun rating che l'utente ha già dato

$$P(I_u | r_{uj} = v_s) = \prod_{k\in I_u} P(r_{uk} | r_{uj} = v_s)$$

Si ottiene quindi un confronto tra le varie

$$P(r_{uj} = v_s | I_u) \sim P(r_{uj} = v_s) \prod_{k\in I_u} P(r_{uk} | r_{uj} = v_s)$$
- $P(r_{uj} = v_s)$ si stima come la frazione degli utenti che hanno dato rating $v_s$ a $j$, mentre ciascun $P(r_{uk} | r_{uj} = v_s)$ si stima come la frazione degli utenti che hanno dato rating $r_{uk}$ a $k$, tra quelli che hanno dato rating $v_s$ a $j$.
- In altre parole: dato l'insieme degli utenti che hanno dato una certa valutazione all'item considerato, prendo per ogni elemento di cui l'utente ha dato la valutazione la frazione di utenti (tra quelli considerati) che hanno dato la stessa valutazione.

- Il rating mancante finale si può calcolare con una media pesata dei vari valori (assumendo una scala almeno ad intervalli):

$$\hat r_{uj} = \frac{\sum_{s=1}^l v_l * P(r_{uj} = v_s) \prod_{k\in I_u} P(r_{uk} | r_{uj} = v_s)}{\sum_{s=1}^l P(r_{uj} = v_s) \prod_{k\in I_u} P(r_{uk} | r_{uj} = v_s)}$$

Si noti che ciò che si fa assomiglia molto all'approccio item-based. Potenzialmente, si possono definire anche le versioni equivalenti user-based e quella unificata.

TODO: forse aggiungi v. unificata

### What is Laplacian smoothing, and how does it address the issue of overfitting in Naive Bayes Collaborative Filtering?

E' noto che Naive Bayes soffre del problema dell'overfitting, in quanto le stime di probabilità $P(r_{uj} = v_s)$ e $P(r_{uk} | r_{uj} = v_s)$ sono poco robuste nel caso che l'item $j$ abbia pochi rating, oppure $|{v | r_{uj}=v_s}|$ è piccola. Nel concreto, visto che è tutto messo in produttoria basta una frazione a zero per azzerare la pseudo-probabilità finale calcolata.

Per prevenire questo problema, una possibile soluzione è lo Smoothing di Laplace, che permette di fissare un valore minimo $\neq 0$ per le prob. stimate.

### Explain the geometric intuition behind latent factor models in collaborative filtering.

> V. Alternative:
> - How does the low-rank intuition apply to latent factor models in collaborative filtering?
> - What is the basic idea behind matrix factorization in collaborative filtering?
> - Describe the terms "latent components" and "latent factors" in the context of matrix factorization.

L'idea del modello a fattori latenti nasce dall'intuizione geometrica che la varianza di una matrice $m\times n$ molto sparsa (rango $k << \min(n,m)$), può essere espressa con meno basi. Cioè, tutta la varianza dei rating può essere spiegata in un sottospazio di dimensione $k$.

Nel caso concreto, posso decidere di modellare gli utenti e gli item come vettori nello spazio di dimensione $k$ (ottenendo due matrici $U$ di dimensione $m \times k$ e V di dimensione $n\times k$). I rating reali e mancanti, sono quindi ricavabili dal prodotto $\hat R = U V^T$ (int quanto $R\approx U V^T$).

Il vantaggio della tecnica nasce dal fatto che ricavate le due matrici, i singoli rating si possono ricavare online come il prodotto scalare tra due vettori $\hat r_{ij} \approx u_{i\cdot} v_{j\cdot}$, evitando quindi di memorizzare una matrice intera $m\times n$ e occupando quindi solo $O(k*(m+n))$ invece di $O(m*n)$.

Lo spazio latente di dimensione $k$ è visibile come una serie di feature non esplicite non sempre interpretabili; le matrici $U$ e $V$ rappresentano l'affinità di utenti e item con tali feature.

Per il calcolo delle matrici esistono diversi algoritmi che differiscono per la funzione obiettivo e/o per eventuali vincoli sulle matrici.

### What is unconstrained matrix factorization, and how is it related to singular value decomposition (SVD)?

La variante senza vincoli è il modo più semplice di fare M.F. La funzione obiettivo potrebbe essere una minimizzazione degli errori quadratici: $$\min J = \frac{1}{2} ||R-UV^T||^2$$

SVD è questo, a cui si aggiunge il vincolo che le basi di $U$ e $V$ siano ortogonali, unconstrained invece non ha questo vincolo.

In entrambi i casi si può utilizzare Gradient Descend per effettuare la minimizzazione.

### How does regularization play a role in matrix factorization for collaborative filtering?

Siccome la matrice $R$ è molto sparsa e nulla garantisce che le matrici $U$, $V$ ricavate siano a loro volta composte prevalentemente da zeri (andando quindi in overfitting e ottenendo comunque uno scarto medio molto basso), alla funzione obiettivo solitamente si aggiunge una regolarizzazione: $$\min J = \frac{1}{2} ||R-UV^T||^2 + \frac{\lambda}{2}(||U||^2 + ||V||^2)$$

### Explain how user and item biases are incorporated into matrix factorization models and their significance.

In tale algoritmo di minimizzazione è possibile incorporare anche l'user bias e l'item bias che si hanno nei classici algoritmi neighborhood based:

- un rating si stima come $\hat r_{uj} = o_u + p_j + u_{u\cdot}v_{j\cdot}$ (si aggiungono i bias utente e item)
- si aggiungono due nuovi vettori dei bias
- tra i rating reali e quelli stimati, si possono ricavare degli errori $e_{uj}=r_{uj} - \hat r_{uj}$
- la funzione obiettivo può essere ulteriormente modificata per incorporare anche tutte queste componenti $$\min J = \frac{\lambda}{2}(||U||^2 + ||V||^2) + \frac{1}{2}\sum_{r_{uj}\;noti}e_{uj}^2 + \frac{\lambda}{2}\sum_{u=1}^m o_u^2 + \frac{\lambda}{2}\sum_{j=1}^n p_j^2$$

Dal punto di vista delle matrici i bias vengono incorporati aggiungendo due colonne alla User Latent Factor Matrix (una contenente i bias e una colonna di 1) e due righe alla Item Latent Factor Matrix (una riga di 1 e una contentente i bias).

### What is Singular Value Decomposition (SVD), and how does it contribute to matrix factorization in collaborative filtering?

La SVD è un tipo particolare di matrix factorization, dove invece di scomporre in due matrici $m \times k$ e $n \times k$ mutualmente ortogonali, se ne aggiunge una intermedia quadrata diagonale $k \times k$.

Nel contesto dei RS:

- la prima matrice rappresenta l'affinità tra utenti e topic astratti,
- la terza rappresenta l'affinità tra tra item e topic astratti
- la seconda serve a fare da mapping tra i topic astratti delle due matrici (che in questo modo possono essere differenti) $$R \approx Q_k \Sigma_k P_k$$

### How does non-negative matrix factorization (NMF) differ from other matrix factorization methods? Discuss the interpretability and applications of non-negative matrix factorization in collaborative filtering.

NMF è una variante di matrix factorization che aggiunge dei vincoli di non negatività sulle matrici U e V.

Nel contesto dei RS è utile per migliorare l'interpretabilità, soprattutto nei casi di scale unarie (azioni che non hanno il loro equivalente negativo).

### What is a baseline estimator in collaborative filtering, and how does it relate to user and item biases? Explain the concept of a baseline estimator as a non-personalized bias-centric model in collaborative filtering.

Una baseline di comparazione di sistemi basati sul collaborative filtering può essere una variante non personalizzata, dove:

- si assume che i rating siano incentrati sulla media,
- si assume che i rating sono spiegati soltato dal bias utente e dal bias dell'item.

La stima di un rating si ricava quindi calcolando $r_{uj} = b_u^{USER} + b_j^{ITEM}$, mentre il training di un modello che apprende i bias minimizza una funzione obiettivo con solo la componente dei bias quadratici.

### How can latent factor models be integrated with other optimization models, and what benefit does this integration offer? How can latent factor models be integrated with arbitrary models, and what kind of hybrid recommender systems does this integration lead to?

I modelli basati sulla fattorizzazione possono essere integrati con altri modelli attraverso la solita somma pesata degli output.