Negative Sampling (Implicit Feedback)

Background

Implicit-feedback recommendation systems see only positives (clicked, watched). The model needs negative examples to learn from - usually sampled from the impressions that didn't convert, at a fixed positive:negative ratio.

Problem statement

Implement sample_negatives(impressions, positives, ratio=4, seed=0). impressions is the set of (user, item) pairs the user saw; positives is the subset that converted. Sample ratio * len(positives) negatives uniformly without replacement from impressions - positives. Return a list of pairs in random (seeded) order.

Input

• impressions - list of (user, item) tuples.
• positives - list of (user, item) tuples (subset of impressions).
• ratio - int >= 1, negatives per positive (default $4$).
• seed - RNG seed.

Output

• list[tuple] of length $\min(\text{ratio}\cdot|\text{positives}|,\ |\text{impressions}-\text{positives}|)$.

Examples

Input: impressions=10 pairs, positives=2 pairs, ratio=4
Output: 8 distinct negatives drawn from the 8 non-positive impressions

Constraints

• ratio >= 1. Without replacement: if there aren't enough negatives, return all available.
• Use random.Random(seed) so output is reproducible.

Notes

• Position bias. Production setups weight each negative by the inverse propensity of its slot to de-bias for click position. The IPW problem in this set covers that.