NSWI166 — Formula Cheat Sheet

Introduction to Recommender Systems & User Preferences — all formulas covered, by lecture

Collaborative Filtering

Lecture 2 — User- and Item-based Nearest Neighbors

Pearson Correlation Similarity

User-based k-NN — measuring how alike two users' tastes are

$$\text{sim}(a,b) = \frac{\sum_{p \in P}(r_{a,p} - \bar{r}_a)(r_{b,p} - \bar{r}_b)}{\sqrt{\sum_{p \in P}(r_{a,p}-\bar{r}_a)^2}\sqrt{\sum_{p \in P}(r_{b,p}-\bar{r}_b)^2}}$$
  • P — set of items rated by both users $a$ and $b$
  • $\bar r_a, \bar r_b$ — each user's own average rating (corrects for personal rating bias)
  • Range: $[-1,1]$; near $1$ = very similar taste, near $-1$ = opposite taste
Use it when: finding the neighborhood of users most similar to the active user, before aggregating their ratings.

Jaccard Similarity

Simpler alternative — good for implicit / set-based feedback

$$\text{sim}(A,B) = \frac{|A \cap B|}{|A \cup B|}$$
  • A, B — sets of items two users interacted with
Use it when: you only have binary/implicit interaction data, not graded ratings.

Rating Prediction (weighted sum of neighbor deviations)

User-based k-NN — turning similarity into an actual predicted rating

$$\text{pred}(a,p) = \bar{r}_a + \frac{\sum_{b \in N} \text{sim}(a,b)\cdot(r_{b,p}-\bar{r}_b)}{\sum_{b\in N}\text{sim}(a,b)}$$
  • N — the neighborhood (k most similar users who rated item $p$)
  • $\bar r_a$ anchor — re-centers the prediction onto $a$'s own rating scale
  • Denominator — normalizes the weighted sum into a weighted average
Use it when: you need a calibrated numeric rating (e.g. to compute MAE/RMSE). Drop the $\bar r_a$ term if you only need a ranking — it's a per-user constant and doesn't affect order.

Ranking Score (k-NN for ranking, not rating prediction)

Same idea as above, simplified for pure top-N ranking

$$\text{score}(a,p) = \sum_{b\in N}\text{sim}(a,b)\cdot(r_{b,p}-\bar{r}_b)$$
  • Drops the $\bar r_a$ offset (rank-invariant) and the normalization denominator (empirical approximation, not strictly rank-invariant)
Use it when: you only care about item order, not a calibrated rating value.

Cosine Similarity

Item-based k-NN — ratings treated as vectors

$$\text{sim}(\vec{a},\vec{b}) = \frac{\vec{a}\cdot\vec{b}}{|\vec{a}|\cdot|\vec{b}|}$$
Use it when: comparing item rating vectors directly; blind to individual rating-scale bias (use adjusted cosine to fix that).

Adjusted Cosine Similarity

Item-based k-NN — corrects cosine for per-user rating bias

$$\text{sim}(a,b) = \frac{\sum_{u\in U}(r_{u,a}-\bar{r}_u)(r_{u,b}-\bar{r}_u)}{\sqrt{\sum_{u\in U}(r_{u,a}-\bar{r}_u)^2}\sqrt{\sum_{u\in U}(r_{u,b}-\bar{r}_u)^2}}$$
  • U — users who rated both items $a$ and $b$
  • Structurally identical to Pearson correlation, just transposed onto items instead of users
Use it when: computing item-item similarity for item-based CF — the standard production choice over plain cosine.

Matrix Factorization & BPR

Lecture 3 — Model-Based Collaborative Filtering

Matrix Factorization Objective

Decomposing the sparse rating matrix into latent user/item factors

$$\sum_{i,j} \left(m_{i,j} - \sum_{k=0}^{K} u_{i,k}\,v_{k,j}\right)^2 \;+\; \lambda\left(\sum_{i,j} u_{i,j}^2 + \sum_{i,j} v_{i,j}^2\right)$$
  • $M \approx U \times V$ — $M$ is $n\times m$ (users × items), $U$ is $n\times K$, $V$ is $K \times m$, $K\ll n,m$
  • $\lambda$ — regularization strength, controls overfitting
  • Sum only over known matrix entries
Use it when: you need a scalable, model-based alternative to k-NN that generalizes to unseen rating combinations.

SGD Update Rule (for MF)

Optimizing the MF objective above, one known rating at a time

$$u_{i,k} \leftarrow u_{i,k} - \text{lr}\cdot err \cdot v_{k,j} - \lambda\, u_{i,k}$$ $$v_{k,j} \leftarrow v_{k,j} - \text{lr}\cdot err \cdot u_{i,k} - \lambda\, v_{k,j}$$
  • err — $x' - x$, the difference between the current prediction $x'=u_i\cdot v_j$ and the true rating $x$
  • lr — learning rate
Use it when: implementing MF from scratch; hyperparameters to tune are $K$, learning rate, $\lambda$, and stopping criteria.

Factorization Meets the Neighborhood (Koren, 2008)

Merging bias terms + latent factors into one rating-prediction model

$$\hat{r}_{ui} = \mu + b_u + b_i + p_u^T q_i$$ $$\min_{p_*,q_*,b_*} \sum_{(u,i)\in K} \left(r_{ui} - \mu - b_u - b_i - p_u^T q_i\right)^2 + \lambda\left(\|p_u\|^2 + \|q_i\|^2 + b_u^2 + b_i^2\right)$$
  • $\mu$ — global average rating
  • $b_u, b_i$ — user/item bias terms (some users rate harshly, some items are universally liked)
  • $p_u^Tq_i$ — classic latent-factor interaction term
Use it when: you want the de-facto standard MF baseline — became the field's default because the bias terms substantially improve calibration.

Bayesian Personalized Ranking (BPR)

Ranking-oriented MF for binary implicit feedback

$$\hat{r}_{i,j} := u_i \times o_j$$ $$\text{maximize} \sum_{\forall (u,g,b)} \ln \sigma\left(\hat{r}_{u,g} - \hat{r}_{u,b}\right) - \lambda\left(\|U\|^2 + \|O\|^2\right)$$
  • (u,g,b) — training triple: user, a "good" (observed) item, a "bad" (unobserved) item
  • $\sigma$ — sigmoid function
  • Optimizes pairwise ranking correctness, not rating accuracy
Use it when: the goal is a ranked list from implicit feedback rather than a calibrated rating — the standard choice over rating-prediction MF for top-N tasks.

Content-Based & Knowledge-Based RS

Lecture 4

TF-IDF

Weighting item description terms by how distinctive they are

$$\text{TF}(t,d) = \frac{\text{count of } t \text{ in } d}{\text{total terms in } d} \qquad \text{IDF}(t) = \log\frac{N}{|\{d:t\in d\}|}$$ $$w(t,d) = \text{TF}(t,d)\times \text{IDF}(t)$$
  • N — total documents (items) in the collection
  • High weight = frequent in this item, rare across all items (genuinely distinctive)
Use it when: representing text-based item descriptions as vectors for content-based filtering. Largely superseded today by embeddings (BERT/CLIP).

Rocchio's Method (Vector Space Model)

Building/updating a user profile from liked/disliked items

$$Q_{i+1} = \alpha \cdot Q_i + \beta \cdot \frac{1}{|D^+|}\sum_{d^+ \in D^+} d^+ - \gamma \cdot \frac{1}{|D^-|}\sum_{d^- \in D^-} d^-$$
  • $D^+, D^-$ — liked / disliked item sets (TF-IDF vectors)
  • $\alpha,\beta,\gamma$ — weights for old profile, positive centroid, negative centroid
  • Often $\gamma=0$ — negative feedback is rarer and noisier
Use it when: incrementally updating a content-based user profile. Caution: the underlying "distance" intuition partially breaks down in high dimensions.

Knowledge-Based Feature Scoring (Eckhardt)

Scoring items by a learned per-feature utility function rather than similarity

$$@(o) = \frac{2\cdot f_{\text{Price}}(o) + 1\cdot f_{\text{Display}}(o) + 1\cdot f_{\text{RAM}}(o)}{4}$$
  • $f_{\text{Price}}(o)$, etc. — learned trapezoid-shaped utility curves per feature, mapping raw value to a $[0,1]$ desirability score
  • Numerator weights — learned importance of each feature to this user
Use it when: recommending "better" items rather than "similar" ones — the defining move of knowledge-based RS.

Evaluation Metrics

Lecture 6

Precision & Recall

Recommendation as an information-retrieval task

$$\text{Precision} = \frac{tp}{tp+fp} \qquad \text{Recall} = \frac{tp}{tp+fn}$$
  • tp — recommended & actually good  |  fp — recommended but not good  |  fn — good but never recommended
  • Precision = exactness of what you showed; Recall = completeness of what you found
Use them when: establishing a baseline classification view of recommendation quality, before moving to ranking-aware metrics.

Mean Absolute Error / Root Mean Squared Error

Rating-prediction accuracy (largely superseded for ranking-oriented systems)

$$MAE = \frac{1}{n}\sum_{i=1}^{n}|p_i - r_i| \qquad RMSE = \sqrt{\frac{1}{n}\sum_{i=1}^{n}(p_i-r_i)^2}$$
  • $p_i, r_i$ — predicted and true rating
  • RMSE penalizes large individual errors disproportionately more than MAE (squaring)
Caution: low RMSE does not imply good ranking quality — a predictor can preserve relative order perfectly while having huge absolute error, and vice versa.

RankScore

Rewarding hits that occur earlier in the ranked list

$$\text{rankscore} = \sum_{i \in \text{hits}} 2^{-\frac{i-1}{\alpha-1}}$$
  • i — rank position of a hit (1-indexed)
  • $\alpha$ — ranking half-life: the rank where a hit's contribution decays to half its rank-1 value
Use it when: position-sensitivity matters but a hard top-k cutoff feels too rigid.

(n)DCG

The standard rank-sensitive relevance metric

$$DCG_{pos} = \sum_{i=1}^{pos}\frac{rel_i}{\log_2(i+1)} \qquad nDCG_{pos} = \frac{DCG_{pos}}{IDCG_{pos}}$$
  • $rel_i$ — relevance of the item at rank $i$ (binary or graded)
  • IDCG — DCG under the ideal (perfectly sorted) ordering
  • Normalizing by IDCG bounds nDCG to $[0,1]$, making it comparable across users with different amounts of relevant content
Use it when: you need the most standard, comparable ranking-quality metric in RS papers — this is the one to default to.

Average Precision / MAP

Rewards front-loaded hits more than back-loaded ones

$$AP = \frac{1}{|\text{relevant}|}\sum_{i \in \text{hits}} \text{Precision@}i$$
  • Precision is recomputed fresh at each rank where a hit occurs, then averaged
  • MAP = mean of AP across all users/queries
Use it when: you want a single number rewarding lists where good items cluster near the top, not just present anywhere.

Maximal Marginal Relevance (MMR)

Greedy re-ranking to inject list diversity

$$\arg\max_i\;\; \alpha \cdot \text{relevance}(i) - (1-\alpha)\cdot \max_{j \in \text{selected}} \text{sim}(i,j)$$
  • $\alpha$ — accuracy/diversity tradeoff weight
  • Penalizes candidates too similar to anything already chosen
Use it when: post-processing a ranked list to reduce redundancy (the "Harry Potter problem" fix). Doesn't scale well to very long lists.

Hybrid Recommender Systems

Lectures 8–9 — Case Studies

BPR-MCA — Content Alignment Penalty

Pulling content-similar users/items together in BPR's latent space

$$\text{maximize} \sum_{\forall(u,g,b)} \ln\sigma(\hat r_{u,g}-\hat r_{u,b}) - \lambda\left(\|U\|^2+\|O\|^2+\sum_{p}\sum_{u' \in s_{u,p}} \omega_p \cdot s_{p,u,u'} \cdot \|\mathbf{u}_u - \mathbf{u}_{u'}\|^2\right)$$
  • p — a content similarity matrix (knowledge source)
  • $\omega_p$ — learned relevance weight of source $p$
  • $s_{p,u,u'}$ — similarity between $u$ and $u'$ under source $p$
Use it when: mitigating cold-start by folding multiple external content sources directly into a BPR training objective, with automatically learned source trustworthiness.

Spreading Activation

Diffusing relevance energy through a heterogeneous knowledge graph

$$a_{(i+1)}(n) = r_a \cdot a_{(i)}(n) + r_s \sum_{m \in M_n} \frac{a_{(i)}(m)}{|M_n|}$$
  • $r_a$ — retention rate (self-decay)  |  $r_s$ — spreading rate (neighbor uptake)
  • $M_n$ — node $n$'s neighbors in the graph
Use it when: you want a non-learned, purely algebraic graph-diffusion hybrid — works on heterogeneous graphs mixing collaborative and content edges. Notably robust to $r_a$/$r_s$ tuning.

Fuzzy D'Hondt's — Candidate Selection & Vote Update

Fairly aggregating multiple RS strategies' outputs

$$c_{best} = \arg\max_{\forall c_i \in C} \sum_{p_i \in P} v_{curr,i} \times r_{i,j}$$ $$k_i \mathrel{+}= r_{i,best}, \qquad v_{curr,i} = \frac{v_{orig,i}}{k_i+1}$$
  • $v_{curr,i}$ — strategy $i$'s current (discounted) vote weight
  • Discount is proportional to how strongly the winning strategy endorsed the chosen item — the "fuzzy" part vs. classic D'Hondt
Use it when: combining several independently-trained RS strategies and you need proportional, fair representation rather than winner-take-all.

Fuzzy D'Hondt's — Iterative Vote Learning (online SGD)

Learning how much to trust each strategy from live feedback

$$v_i = v_i + \eta_{pos}\Big(r_{i,j} - \sum_{\forall k\neq i} r_{k,j}\Big)\quad\text{(click)} \qquad v_i = v_i - \eta_{neg}\Big(r_{i,j} - \sum_{\forall k\neq i} r_{k,j}\Big)\quad\text{(ignore)}$$
  • $\eta_{pos},\eta_{neg}$ — learning rates (negative feedback weighted much lower — it's a weaker signal)
Use it when: votes aren't known in advance and must be learned online from real click/ignore events.

Deep Learning in RS

Lectures 10–11

Feedforward Network / Backpropagation

General DL foundation

$$F(x) := \sigma(\sigma(\mathbf{W}^1 x)\mathbf{W}^2 \dots)$$
  • $\mathbf{W}^k$ — weight matrix of layer $k$  |  $\sigma$ — activation function
Use it when: describing any deep network's forward pass before specializing to an RS architecture (NeuMF, autoencoders, etc.).

Softmax (Word2Vec / embedding models)

Converting raw scores into a probability distribution over a vocabulary or item set

$$s_i = \frac{e^{r_i}}{\sum_{j=1}^{N}e^{r_j}}$$
  • $r_j$ — raw score for word/item $j$  |  N — vocabulary/item-set size
  • A smooth, differentiable approximation of the max operator
Use it when: training embedding models (Word2Vec, Prod2vec, item2vec) — note the real target is the embedding matrix, not the softmax prediction itself.

Bias Formalization: Exposure / Selection / Position Bias

Why observed implicit-feedback data ≠ true preference distribution

$$p_T(u,i) \neq p_D(u,i) \qquad\qquad p_T(u,i\,|\,r=0) = 0$$
  • $p_T$ — true/target distribution  |  $p_D$ — observed (logged) distribution
  • Second equation: a non-interaction can never be confirmed as a genuine negative — it's consistent with both dislike and never-seen
Use it when: explaining why naive supervised training on implicit logs is biased — connects directly to Lecture 6/7's propensity-score de-biasing.