# Cap. 3: Neighborhood Based Collaborative Filtering

### Explain the fundamental concept of Neighborhood-Based Collaborative Filtering and its alternative name. What is the underlying principle of neighborhood-based collaborative filtering methods?

I modelli Neighborhood-based collaborative filtering (detti anche algoritmi *memory-based*) partono dall'assunzione di avere una (o più) matrici (molto sparse) che associa tutti gli utenti a tutti gli item da raccomandare.

In ogni cella piena, si ha un rating dato dall'utente $i$ all'item $j$. Siccome non tutti gli utenti hanno valutato tutti gli item, molte celle sono vuote.

L'obiettivo di un sistema N.B. può essere definito in due modi:
- predirre i rating mancanti $\hat r_{ij}$;
- oppure, trovare i top k utenti simili ad un utente (o dualmente, i top k item simil ad un item), partendo dall'assunzione che utenti simili mostreranno pattern di comportamento simili e quindi item simili riceveranno valutazioni simili.

### What are the two main types of Neighborhood-Based Collaborative Filtering, and how do they differ in terms of focus? How does item-based collaborative filtering differ from user-based collaborative filtering?
I due tipi di NBCF sono:

1) lo **user-based**, che, dato un utente:
- ricerca i top k utenti più simili (cioè, che hanno dato rating simili)
- a partire da essi, ricava i ranting mancanti per l'utente target (e può quindi raccomandare quelli per cui si prevede un valore più elevato)
2) l'**item-based**, invece, dato uno (o più) item target (tipicamente degli item che piacciono all'utente):
- ricerca i top k item più simili per rating ricevuti (cioè che sono stati valutati in maniera simile da molti utenti) e li raccomanda

L'*item-based* può essere visto come il problema duale dell'*user-based*.

### Describe the process of determining the neighborhood of a target user in user-based collaborative filtering.

1) Dati i vettori degli utenti (le righe della matrice), posso computare per ciascuna coppia $(u,v)$ la loro similarità attraverso una versione modificata del coefficiente di pearson (che ignora i valori nulli e considera soltanto i rating degli item $k \in I_u \cap I_v$ valutati da entrambi gli utenti)
- NOTA: nel calcolo può essere utile avere un vettore dei rating medi degli utenti
2) Spiegazione della formula:

$$ Pearson(u,v) = \frac{\sum_{k \in I_u \cap I_v} (r_{uk} - \mu_u)(r_{v_k} - \mu_v)}{\sqrt{\sum_{k \in I_u \cap I_v} (r_{uk} - \mu_u)^2}\sqrt{\sum_{k \in I_u \cap I_v} (r_{vk} - \mu_v)^2}} $$

- il prodotto scalare tra due vettori è una misura della loro similitudine
- i singoli valori dei vettori degli utenti vengono "aggiustati" sottraendo il rating medio dell'utente
- la parte sotto della formula serve a normalizzare
- in generale, Pearson tiene conto del fatto che due utenti possano avere "scale diverse"

3) Per stimare un rating mancante di un utente $u$ ad un item $j$, posso:
- selezionare i **top k** utenti più simili che hanno valutato $j$ (quindi quelli con coefficiente di Pearson più alto) $P_u(j)$
- prendere il loro rating aggiustato all'item $j$ $s_{uj} = r_{uj} - \mu_{u}$
- fare una somma pesata di tali rating con le similarità
- normalizzare dividendo per una somma pesata dei valori assoluti delle similarità (così si ottiene una media pesata sul coefficiente di Pearson)
- riportare il risultato nella scala dell'utente target sommando il rating medio $\mu_u$

Formula:

$$\hat r_{uj} = \mu_u + \frac{\sum_{v \in P_u(j)}Pearson(u,v)*s_{vj}}{\sum_{v \in P_u(j)}|Pearson(u,v)|} $$

4) Per fare le raccomandazioni (online), posso selezionare i **top k'** elementi non ancora valutati con rating stimato $\hat r_{uj}$ più elevato.

Si noti che la parte offline ha complessità quadratica sul numeri di utenti ($O(m^2n)$), mentre la parte online è lineare sul numero di item ($O(k'n)$).

Sono possibili varianti del problema che utilizzano diverse funzioni per il calcolo della similarità (al posto del coefficiente di Pearson) o per predire i rating (al posto della mean normalization).

### What is the "long tail" distribution of rating frequencies, and how does it impact recommendation systems? How can you fix the Pearson similarity formula to deal with that?

Il problema della long tail consiste nel fatto che tipicamente si hanno tantissimi item "visti" e valutati poche volte, mentre pochi item molto popolari valutati un numero di volte magnitudinalmente superiore. La distribuzione di frequenza del numero di rating sugli item, solitamente non è né uniforme, né normale, ma tende ad essere una power law (esponeziale inversa $f(x)= \alpha x^{-\gamma}$, dove $x$ è il numero di rating ricevuti da un item e $f(x)$ è il numero di item che hanno ricevuto $x$ rating).

Nei RS questo è un problema perché:

- per gli item popolari si hanno più dati, pertanto si avranno raccomandazioni migliori per gli item più popolari e raccomandazioni peggiori per quelli meno popolari,

- la formula di Pearson lavora solo sulle intersezioni dei rating, e per probabilità quelle intersezioni saranno fatte prevalentemente da item popolari, pertanto gli item popolari influenzeranno di più le similarità e quindi le raccomandazioni, con il rischio di creare discriminazioni di categorie di utenti e/o item.

Un modo per gestire questo nel user-based NCF è correggere la formula aggiungendo a ciascun termine delle sommatorie un prodotto per un peso $w_j = log(\frac{m}{m_j})$ (l'inverso della frazione degli utenti che hanno valutato $j$).

### Describe the characteristics of different types of rating scales, including nominal, ordinal, interval, and binary ratings.
I rating possono essere classificati secondo due dimensioni:
- il tipo di scala
- nominale: categoriale puro
- ordinale: categoriale con ranking delle categorie
- intervallo: ordinale con equidistanza dei valori di scala
- ratio: come per l'intervallo, ma con uno zero "naturale"
- il tipo di rating
- continuo: un numero con precisione arbitraria
- intervallo: un numero discreto
- ordinale: un numero discreto con valore qualitativo
- binario: like/dislike
- unario: solo preferenze positive oppure azioni svolte

### Explain the concept of implicit and explicit feedback in the context of recommender systems.

- Feedback implicito:
- facile da ottenere
- deriva dal comportamento dell'utente
- molto informativi ma vanno interpretati
- Feedback esplicito:
- difficile da ottenere
- non necessariamente contiene più informazioni di uno implicito

### Compare and contrast user-based and item-based collaborative filtering methods in terms of their strengths and weaknesses.

#### User-based CF
- Complessità quadratica nel tempo e nello spazio sul *numero di utenti*
- Soffre il problema della sovrapposizione dei gusti (il modello parte dall'assunzione che utenti simili hanno anche gusti simili, ma non è detto che questo sia vero per tutti i gusti)

#### Item-based CF
- Complessità quadratica nel tempo e nello spazio sul *numero di item*
- In generale più precisi, stabili e meno soggetti a variazioni casuali (solitamente il numero di utenti che valutano un item è più alto rispetto al numero di item che un utente valuta)
- Maggiormente "self-explanatory" (per il fattore di affinità)
- Tendono a mostrare item simili (quindi penalizzando maggiormente novelty e serendipity).

#### Pro e contro dei NBCF
- Semplicità, intuitività e stabilità del modello
ma
- poca scalabilità (per l'elevata complessità computazionale)
- sparsità della matrice (c'è tanto da calcolare)

### How do user-based and item-based methods handle the issue of offline computational complexity?
Per ridurre la complessità dei modelli NBCF si divide la computazione in due fasi:
- fase offline in cui svolgo le computazioni più costose (aggregazioni, calcolo dei rating, ecc.)e viene svolta solo periodicamente
- fase online in cui calcolo le raccomandazioni sulla base delle informazioni calcolate in fase offline (es. calcolo dei top k).

Altri metodi utilizzati sono quelli di riduzione delle dimensionalità.

### Describe the idea of an "unified view" in collaborative filtering and how it combines the strengths of user-based and item-based methods.
Per "vista unificata" si intende l'unione di user-based e item-based collaborative filtering e consiste sostanzialmente nel combinare le similarità tra righe e colonne della matrice di interazione per generare le predizioni (es. facendo una media pesata).

Questa operazione è computazionalmente fattibile perchè la maggior parte dei calcoli tra i due metodi è in comune.

### What challenges arise in applying dimensionality reduction techniques like PCA/SVD to collaborative filtering? How are these challenges addressed?

Data l'elevata sparsità della matrice (il numero medio di item valutati per utente $n'$ è molto minore di $n$), le computazioni quadratiche (specie quelle sul numero di utenti) possono diventare particolarmente pesanti.

Un modo per affrontare il problema è tentare una riduzione della matrice da $m\times n$ a $m\times d$ (con $d <<< n$). Cioè, si mappano i vettori utente in uno spazio latente meno sparso e si calcolano le similarità su questi vettori densi.

Le tecniche più comuni per fare ciò sono il clustering, la PCA, ecc.

Un problema tipico che si incontra quando si prova ad applicare queste tecniche è che necessitano comunque matrici non sparse. Tipicamente, ciò che si fa per gestire il problema è:

- una soluzione naive (che comunque funziona abbastanza bene) è stimare i buchi con le valutazioni medie degli utenti e poi fare M.F. (con PCA, ad esempio, tali valori verranno ignorati);
- utilizzare tecniche probabilistiche per ottere una matrice di co-varianza (maximum likehood estimation).

### Explain the concept of regression modeling in the context of neighborhood-based collaborative filtering.
I modelli N.B. possono essere anche generalizzati come un problema di regressione, quindi con un approccio **model based** (vedi cap. successivo).

In particolare possiamo considerare il NBCF come una variante euristica della regressione lineare in cui i pesi equivalgono allo score di similarità per i "vicini" considerati rilevanti, 0 per gli altri.

Ciò si può fare riscrivendo la formula sostituendo le similarità con dei "pesi" ricavabili tramite una qualche forma di **training** (cioè, considerando le sim. come **parametri** da apprendere). $$\hat r_{uj} = \mu_u + \sum_{v\in P_u(j)} W_{v,u}^{USER} (r_{vj} - \mu_v)$$

A questo punto si può immaginare l'apprendimento di questi pesi come la minimizzazione di un costo. E.g., *MSE*: $J_u = \sum (r_{uj} - \hat r_{uj})^2$

### What are the potential advantages of using learned weights in neighborhood-based collaborative filtering models? How does regularization play a role in improving regression modeling for neighborhood-based collaborative filtering?

Questa generalizzazione permette di introdurre a piacimento nuovi parametri per gestire aspetti potenzialmente problematici. Per esempio, nella formula di stima dei rating si possono sostituire i rating medi con dei ulteriori parametri da apprendere:

- $m$ parametri $b_u^{USER}$ per i bias sugli utenti;
- $n$ parametri $b_i^{ITEM}$ per i bias sugli item.

La formula diventerebbe quindi qualcosa tipo: $$\hat r_{uj} = b_u^{USER} + b_j^{ITEM} + \frac{\sum_{v\in P_u(j)} W_{v,u}^{USER} (r_{vj} - b_v^{USER} + b_j^{ITEM})}{\sqrt{|P_u(j)|}}$$

Per gli item-based si potrebbe fare qualcosa di analogo: $$ \hat{r}_{ut} = b_u^{USER} + b_t^{ITEM} + \frac{\sum_{v\in Q_t(u)} W_{j,t}^{ITEM} (r_{uj} - b_u^{USER} + b_t^{ITEM})}{\sqrt{|Q_t(u)|}} $$

Volendo si potrebbe poi unire le due formule in un unico modello che incorpora già sia la parte user-based che quella item-based, addestrata come un modello unico con $m^2+n^2+m+n$ parametri.