Implicit feedback

The iALS objective#

Hu, Koren and Volinsky (2008) replace the sum over observed entries with a sum over all entries, weighted:

$$ \min_{X, Y} \sum_{u \in U} \sum_{i \in I} c_{ui} \left( p_{ui} - \mathbf{x}_u^\top \mathbf{y}_i \right)^2 + \lambda \left( \sum_u |\mathbf{x}_u|^2 + \sum_i |\mathbf{y}_i|^2 \right) $$

Where:

• $p_{ui} = \mathbb{1}[r_{ui} > 0]$ — binary preference derived from any interaction count $r_{ui}$.
• $c_{ui} = 1 + \alpha r_{ui}$ — confidence. The linear form is the paper's default; $c_{ui} = 1 + \alpha \log(1 + r_{ui}/\epsilon)$ is the alternative for heavy-tailed counts.
• $\alpha$ — how much one interaction is worth relative to a non-interaction. Values of 15 to 40 are common.
• $\lambda$ — regularisation, usually scaled by the number of observations per row.

The baseline confidence of $1$ on every cell is the design decision that matters. Unobserved pairs are treated as weak negatives rather than as missing, which converts an unconstrained problem into a well-posed one at the cost of a systematic assumption you should be able to defend.

The closed-form updates#

With $Y \in \mathbb{R}^{n \times k}$ fixed and $C^u = \operatorname{diag}(c_{u1}, \dots, c_{un})$:

$$ \mathbf{x}_u = \left( Y^\top C^u Y + \lambda \mathbf{I}_k \right)^{-1} Y^\top C^u \mathbf{p}_u $$

Computed naively this is $O(n k^2)$ per user, giving $O(mnk^2)$ per sweep — infeasible. The paper's identity

$$ Y^\top C^u Y = Y^\top Y + Y^\top (C^u - \mathbf{I}) Y $$

lets $Y^\top Y$ be computed once per sweep at $O(nk^2)$, while the correction term has support only on ${ i : r_{ui} > 0 }$. Total cost per sweep drops to

$$ O!\left( k^2 N + k^3 (m + n) \right) $$

with $N$ the number of non-zeros, $m = |U|$, $n = |I|$. Linear in the data, cubic only in the small factor dimension, and every row solve is independent, so it distributes without communication.

The alternative: pairwise ranking#

BPR (Rendle et al., 2009) attacks the same data with a different loss. Instead of regressing towards $p_{ui}$, it maximises the probability that an observed item outranks an unobserved one:

$$ \max_\Theta \sum_{(u,i,j) \in D_S} \ln \sigma!\left( \hat{x}{uij}(\Theta) \right) - \lambda |\Theta|^2, \qquad \hat{x}{uij} = \hat{x}{ui} - \hat{x}{uj} $$

$D_S = {(u,i,j) : i \in I_u^+, \, j \notin I_u^+}$, sampled rather than enumerated, and $\sigma$ is the logistic function. The objective is a smoothed AUC, which aligns the loss with the ranking task instead of with a reconstruction task.

The practical difference: iALS uses full-matrix weighted least squares and is exact per sweep; BPR uses sampled SGD and scales to settings where even the weighted formulation is too large. Neither dominates. Rendle, Krichene, Zhang and Anderson (2022), Revisiting the Performance of iALS on Item Recommendation Benchmarks, showed iALS with careful regularisation and enough factors matches or beats far newer models on standard benchmarks — another instance of the tuning-effort asymmetry.

Exposure and position bias#

The missing-not-at-random structure is the deepest problem in this data, and confidence weighting does not address it. Observing $(u,i)$ requires two events: exposure and then interaction.

$$ P(\text{click}{ui} = 1) = \underbrace{P(o{ui} = 1)}{\text{was it shown}} \cdot \underbrace{P(\text{relevant}{ui} = 1 \mid o_{ui} = 1)}_{\text{what you want to model}} $$

Fitting clicks directly estimates the product. Joachims, Swaminathan and Schnabel (2017), Unbiased Learning-to-Rank with Biased Feedback, correct for this by weighting each observed click by the inverse of its propensity $P(o_{ui}=1)$, estimated from a position-bias model fitted with result randomisation or swap experiments.

Two consequences worth internalising:

1. Impressions must be logged. Without them, exposure is unidentifiable and no correction is possible after the fact. This is a data-engineering decision made long before any modelling.
2. Propensity variance is the binding constraint. Rarely shown items have tiny propensities and huge inverse weights. Clipping trades a little bias for a large variance reduction, and is standard.

Liang et al. (2016), Modeling User Exposure in Recommendation, model exposure as a latent variable instead, which avoids needing external propensity estimates at the cost of a harder inference problem.

Papers#

• Hu, Koren and Volinsky (2008), Collaborative Filtering for Implicit Feedback Datasets, ICDM.
• Rendle et al. (2009), BPR: Bayesian Personalized Ranking from Implicit Feedback, UAI — arxiv.org/abs/1205.2618
• He et al. (2016), Fast Matrix Factorization for Online Recommendation with Implicit Feedback (eALS), SIGIR.
• Liang et al. (2016), Modeling User Exposure in Recommendation, WWW — arxiv.org/abs/1510.07025
• Joachims, Swaminathan and Schnabel (2017), Unbiased Learning-to-Rank with Biased Feedback, WSDM — arxiv.org/abs/1608.04468
• Rendle et al. (2022), Revisiting the Performance of iALS on Item Recommendation Benchmarks — arxiv.org/abs/2110.14037

What to learn next#

• Ranking metrics — the evaluation this objective is aiming at.
• Two-tower retrieval models — sampled softmax as the modern successor to BPR sampling.
• A/B testing a recommender — the only way to check whether the proxy still tracks value.