BPR & Learning-to-Rank · Recommender Systems

01 · Optimise the order, not the value

From pointwise to pairwise

The metric we serve is a ranking — so train a ranking objective.

Every model so far minimised a pointwise error: SLIM fit each rating with MSE. But what we serve is a Top-N list, scored by ranking metrics. Getting each rating numerically close is neither necessary nor sufficient — all that matters is that relevant items end up above irrelevant ones. BPR optimises that directly. It focuses on implicit feedback (1 = interacted, 0 = not), and for a user splits items into positives $i$ (interacted) and negatives $j$ (not). The training signal is a pairwise ranking wish: for every $(u,i,j)$ , $\hat r_{ui} > \hat r_{uj}$ .

Pointwise (MSE · SLIM)

Fit each rating value:

(r_{ui}-\hat r_{ui})^2

. Cares about absolute numbers, not order.

Pairwise (BPR)

Fit each comparison: push

\hat r_{ui}

above

\hat r_{uj}

. Cares only about order.

why

A 0 means not-yet-seen, not disliked

In implicit data a negative item $j$ is simply one the user hasn’t interacted with — it might be a great recommendation. BPR doesn’t claim $j$ is bad; it only claims the known positive $i$ should rank above it. That softer, relative statement is exactly what a ranking needs.

02 · Turning a comparison into a probability

The pairwise probability

Squash the score difference through a sigmoid to get P(i ranks above j).

The hard inequality $\hat r_{ui} > \hat r_{uj}$ isn’t differentiable, so BPR forms the score difference $x_{uij} = \hat r_{ui} - \hat r_{uj}$ and passes it through the sigmoid $\sigma$ to read it as a probability that the order is correct: $P(i \succ_u j) = \sigma(x_{uij})$ . When $x_{uij}>0$ the probability exceeds $\tfrac12$ ; far positive, it saturates near 1.

Hands-on

Sigmoid · probability and loss of one pair

The score gap x squashed through the sigmoid gives P(i ≻ j). Teal = σ(x); red = the BPR loss −log σ(x). The update weight is 1−σ(x).

Score gap x0.0

P(i ≻ j) = σ(x)

0.50

loss = −log σ(x)

0.69

weight 1−σ(x)

0.50

x = −6σ(x)−log σ(x)x = +6

TakeawayBPR spends its effort where it's losing: the gradient weight 1−σ(x) is near 0 for pairs already ordered right and near 1 for badly-wrong ones.

Formal Definition 7.1 — pairwise probability

Pairwise probability

x_{uij} = \hat r_{ui} - \hat r_{uj}, \qquad P(i \succ_u j) = \sigma(x_{uij}) = \frac{1}{1 + e^{-x_{uij}}}, \qquad \sigma(0)=\tfrac12,\ \sigma(+\infty)=1.

03 · From a product of probabilities to a loss

The BPR loss function

Maximise the likelihood of every pair being ordered right — then take a log.

We want all pairs ranked correctly, so we maximise the product of their probabilities (assuming, as the slides admit, that pairs are independent — they aren’t, but it works). Products of small numbers are numerically miserable, so we take the log-likelihood: it turns the product into a sum with the same maximiser. Finally, to minimise a loss, flip the sign and add L2 regularization. Here $\theta$ is whatever model you’re training — the SLIM matrix $S$ , or the latent factors of Chapter 8. BPR is not a model; it is a training objective you bolt onto one.

Formal Definition 7.2 — log-likelihood & loss

BPR loss

\arg\max_{\theta} \prod_{(u,i,j)} \sigma(x_{uij}) = \arg\max_{\theta} \sum_{(u,i,j)} \log\sigma(x_{uij}), \qquad \arg\min_{\theta}\; E(\theta) = -\!\!\sum_{(u,i,j)} \log\sigma(x_{uij}) + \lambda\lVert\theta\rVert^2.

The log is monotonic, so the optimum is identical — we switch to it purely to turn an unwieldy product into an easy-to-differentiate sum (and to avoid floating-point underflow).

04 · One triplet, two nudges

The gradient & the update

Sample a triplet, push the positive item up and the negative item down.

Differentiating $-\log\sigma(x_{uij})$ gives a beautifully simple gradient: the chain rule turns $\tfrac{d}{dx}\log\sigma(x)$ into $1-\sigma(x)$ , so the whole gradient is $-(1-\sigma(x_{uij}))\,\partial x_{uij}/\partial\theta$ . That factor $1-\sigma(x_{uij})$ is “how wrong the model still is about this pair”: near 0 when already ordered right, near 1 when badly wrong. Training is SGD over sampled triplets: pick $u$ , a positive $i$ , a negative $j$ ; one step nudges the positive item’s parameters up and the negative item’s down — note the opposite signs.

Hands-on

One triplet, stepped · watch the gap open

Each Step applies one BPR-SLIM update for this triplet — the positive item up, the negative item down. The gap x opens and σ(x) rises, while the update weight 1−σ shrinks.

positive inegative j

steps 0x = r̂ᵤᵢ−r̂ᵤⱼ = 0.00σ(x) = 0.501−σ = 0.50

r̂(u, Aveng) ▲ positive0.00

r̂(u, Notting) ▼ negative0.00

TakeawaySGD over sampled triplets nudges the positive item's parameters up and the negative item's down — opposite signs. As the gap opens, the steps shrink: the model spends effort where it's still wrong.

Formal Definition 7.3 — gradient & BPR-SLIM update

For BPR-SLIM, $x_{uij}=R_u\,(S_{\cdot i}-S_{\cdot j})$ , so the two columns move in opposite directions:

BPR-SLIM update

\frac{\partial}{\partial\theta}\big[\!-\log\sigma(x_{uij})\big] = -\big(1-\sigma(x_{uij})\big)\,\frac{\partial x_{uij}}{\partial\theta},

S_{\cdot i} \leftarrow S_{\cdot i} + \gamma\,(1-\sigma(x_{uij}))\,R_u, \qquad S_{\cdot j} \leftarrow S_{\cdot j} - \gamma\,(1-\sigma(x_{uij}))\,R_u.

Sample $(u,i,j)$ with $(u,i)\in R^{+}$ , $(u,j)\in R^{-}$ ; apply; repeat (keep $\operatorname{diag}(S)=0$ ).

05 · It maximises the area under the ROC curve

Pairwise correctness is exactly AUC. Plus: WARP, and a serious popularity bias.

Here’s the punchline: counting how many $(i,j)$ pairs are ordered correctly is the AUC — the area under the ROC curve from Chapter 3. So optimising the BPR loss directly maximises AUC. Train it and watch the fraction of correctly-ordered pairs climb from a coin-flip 0.5 toward 1.

Hands-on

Train BPR-SLIM · loss falls, AUC rises

Full-batch BPR over every triplet of the implicit URM. AUC = the fraction of positive–negative pairs ordered correctly. Minimising the BPR loss maximises it.

Iterations80AUC 1.00 · loss 0.03

0AUC →1loss →0120

1Inter0.892Aveng0.653MI0.654TopGun-1.805LoveAct-2.196Martian-4.377LaLa-5.028Notting-5.02

TakeawayPairwise correctness *is* AUC. BPR maximises it — but popular items appear as positives in many triplets and drift high, so it inherits a popularity bias that flatters its own offline AUC.

Two footnotes. WARP (Weighted Approximate-Rank Pairwise) is a smarter sampler: when it draws a triplet already ranked correctly, it throws it back and draws another — spending compute only on violations. And BPR has a notorious popularity bias: popular items appear as positives in many triplets, get sampled constantly, and drift to high scores; rare items barely move.

!

Good offline ≠ good online

Because both train and test splits inherit the same popularity distribution, BPR’s bias toward popular items flatters its offline AUC. The model that wins the offline leaderboard can still disappoint live users who wanted something off the beaten path — a theme we meet again in fairness (Ch. 14).

Formal Definition 7.4 — BPR ⇔ AUC

For one user, AUC is the fraction of positive–negative pairs ranked correctly:

AUC

\text{AUC}_u = \frac{1}{\lvert R^{+}_u\rvert\,\lvert R^{-}_u\rvert} \sum_{i\in R^{+}_u}\sum_{j\in R^{-}_u} \mathbf{1}\!\left[\hat r_{ui} > \hat r_{uj}\right].

BPR’s loss $-\sum\log\sigma(x_{uij})$ is a smooth surrogate for this count, so minimising it maximises AUC.

06 · Exam intel

What the exam tests

Contrast pointwise vs pairwise; write the BPR probability and loss; explain the $(1-\sigma)$ gradient weight and opposite-sign updates; and state what BPR optimises (AUC) plus its popularity bias.

Q

Worked question — probability, loss and step size of one pair

A BPR-SLIM model scores a positive $\hat r_{ui}=1.5$ and a negative $\hat r_{uj}=0.5$ for user $u$ .

(a) $x_{uij}=1.5-0.5=1.0$ ; $\sigma(1)=1/(1+e^{-1})\approx 0.73$ .
(b) loss $=-\log\sigma(1)\approx 0.31$ .
(c) Small. The update weight is $1-\sigma(1)\approx 0.27$ — the pair is already ranked correctly, so BPR barely adjusts it. A wrongly-ranked pair with $x=-1$ would have weight $\approx 0.73$ .

Traps: treating a “0” as a confirmed negative (it’s un-interacted); saying BPR is a model (it’s a loss; the model supplies $\hat r$ ); forgetting the opposite signs.

07 · Exam · past papers

Past-paper questions

Past paper Exam 2020 · 5 pts — BPR idea, generic loss, and the MF loss

Q. BPR’s main idea and assumptions; the loss for a generic predicted rating; the loss for a Matrix-Factorization model.

Model answer. Idea & assumptions. Optimise ranking, not rating value. From implicit, positive-only data, assume each user prefers an observed item $i$ over an unobserved $j$ : $i \succ_u j$ . Build triplets and maximise $P(\hat r_{ui} > \hat r_{uj})$ . Assumes pairwise preferences and independence of triplets. Generic loss. $\text{BPR-OPT} = -\sum_{(u,i,j)} \ln \sigma(\hat r_{ui}-\hat r_{uj}) + \lambda\lVert\Theta\rVert^2$ . For MF. Substitute $\hat r_{ui}=p_u\cdot q_i$ : $-\sum_{(u,i,j)} \ln\sigma\big(p_u\cdot(q_i-q_j)\big) + \lambda(\lVert p_u\rVert^2+\lVert q_i\rVert^2+\lVert q_j\rVert^2)$ .

Past paper FT-Sample · 5 pts — derive the MF gradients

Q. Idea + assumptions; generic loss; derive the parameter gradients for a Matrix-Factorization model.

Model answer. Let $x_{uij}=p_u\cdot(q_i-q_j)$ and $c=1-\sigma(x_{uij})$ (from $\partial(-\ln\sigma(x))/\partial x = -(1-\sigma(x))$ ): $\partial L/\partial p_u = -c\,(q_i-q_j) + \lambda\,p_u$ , $\partial L/\partial q_i = -c\,p_u + \lambda\,q_i$ , $\partial L/\partial q_j = +c\,p_u + \lambda\,q_j$ . SGD per sampled triplet: $\Theta \leftarrow \Theta - \eta\,\partial L/\partial\Theta$ .

Past paper Practice Exam 2 · sampling triplets

Q. BPR’s idea and assumptions; the generic loss; the concept of sampling triplets (user, positive, negative).

Model answer. Pairwise ranking: a user prefers items they interacted with over those they did not. Loss $-\sum_{(u,i,j)}\ln\sigma(\hat r_{ui}-\hat r_{uj})+\lambda\lVert\Theta\rVert^2$ . Sampling. Implicit data has no explicit negatives, so build triplets by drawing an observed pair $(u,i)$ and sampling a “negative” $j$ uniformly from the items $u$ has not interacted with. Bootstrap-sample huge numbers of such triplets (with replacement) and take one SGD step per triplet — far more efficient than user-by-user passes.

08 · Self-check

Three questions before you move on

The core difference between BPR and SLIM's MSE objective is:

In the BPR gradient, the factor (1 − σ(x)) means that a pair already ranked correctly (large positive x):

Minimising the BPR loss is equivalent to maximising:

09 · Recap

One-screen summary

Chapter 07 — load-bearing ideas

Pairwise, not pointwise: BPR trains on implicit data so each positive $i$ outranks each negative $j$ — $P(i\succ_u j)=\sigma(\hat r_{ui}-\hat r_{uj})$ .
The loss & its gradient: minimise $-\sum\log\sigma(x_{uij})$ ; each step is weighted by $1-\sigma(x_{uij})$ and pushes the positive up, the negative down.
BPR maximises AUC: it’s a training objective for any model (SLIM, MF), with a real popularity bias to watch.
A “0” is not-yet-seen, not disliked; negatives are sampled from un-interacted items.

From pointwise to pairwise

Pointwise (MSE · SLIM)

Pairwise (BPR)

The pairwise probability

Sigmoid · probability and loss of one pair

The BPR loss function

The gradient & the update

One triplet, stepped · watch the gap open

What BPR optimises — and its blind spot

Train BPR-SLIM · loss falls, AUC rises

What the exam tests

Past-paper questions

Three questions before you move on

One-screen summary

Chapter 07 — load-bearing ideas