Recommendation Evaluation

The previous lesson asked the cold subscriber questions, turned the recommendations toward the domain the subscriber named, and the number read from the log fell. There were two explanations: either the questions did not work, or the measure was read from the wrong place. This lesson first builds the measure itself, then measures the same ranking in two separate places.

Three things will be built. Hit rate at k counts whether a ranking finds the correct item within its first k recommendations. The cutoff is k itself and is a measurement decision, not a property of the data. Position discount also takes the position within the first k into account: a hit at the first rank is not the same as a hit at the fifth rank.

• RS49. The setup is the same block built in the first lesson and gives the same numbers: 360 subscribers, 24 items, 3,002 impressions, 577 interactions. The split is also the split of the first lesson: for a subscriber with at least two interactions, the interaction with the largest sequence stamp goes to the held-out set.
• RS50. The three compared setups come from the same family and are separated by a single hyperparameter: the score is the product of the item’s selection count in training and the subscriber’s past share in that domain. w = 0 is the pure baseline — there is no personalization; w = 1 and w = 2 weight the domain share lightly and strongly, respectively.
• RS51. The baseline is w = 0, that is, the order of the items most chosen in training. Since the family is single, the difference between the three numbers comes only from the weight.
• RS52. The positional discount weight is 1 / log2(1 + position); the position starts at one. The measure is read over the whole ranking, and the cutoff is not applied.
• RS53. The offline measure is on the log: the setup ranks, and the held-out item counts as the correct answer. The log holds only the interactions of items that were shown.
• RS54. In the online measure the ranking itself decides what is shown. Each setup shows each of the 360 subscribers their own top five, the outcome is drawn from the true propensity of the simulated setup, and the measure is the mean interactions per subscriber over twenty periods. Higher is better.
• RS55. The true propensity of the simulated setup is not a method, it is a ceiling. It is read only for measurement and gives the limit the online number can reach.
• RS56. Experiment design is not done in this lesson. Sample size, early stopping and multiple comparison calculations were built in the Measurement topic of the User Experience and Behavior Design course and in the Applied Statistics course; here only the difference arising from feedback is measured.

Hit Rate at k, the Cutoff and Position Discount

# COMMON -- FICTIONAL. The subscriber x service item interaction matrix is built inside the lesson.
# Impression, selection and score are generated separately: an item is first SHOWN, then
# it can be selected, and only if it is selected can it be scored.
SEED, M32 = 20260218, 0xFFFFFFFF


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


ITEMS = [  # (name, domain, channel, paid, commitment, appointment, base_share)
    ("auto_payment_instruction", "billing", "online", 0, 0, 0, 0.90),
    ("e_invoice_switch", "alert", "online", 0, 0, 0, 0.85),
    ("payment_reminder_sms", "alert", "online", 0, 0, 0, 0.78),
    ("installment_plan", "billing", "branch", 0, 1, 0, 0.62),
    ("remote_reading_application", "meter", "field", 0, 1, 1, 0.55),
    ("outage_alert_subscription", "alert", "online", 0, 0, 0, 0.50),
    ("debt_restructuring", "billing", "branch", 0, 1, 0, 0.44),
    ("address_update", "subscription", "online", 0, 0, 0, 0.40),
    ("meter_replacement", "meter", "field", 1, 0, 1, 0.36),
    ("consumption_report_subscription", "alert", "online", 0, 0, 0, 0.32),
    ("invoice_dispute_record", "billing", "branch", 0, 0, 0, 0.28),
    ("subscription_transfer", "subscription", "branch", 0, 0, 0, 0.25),
    ("illicit_use_check_appointment", "meter", "field", 0, 0, 1, 0.22),
    ("installation_maintenance_package", "technical", "field", 1, 1, 1, 0.19),
    ("second_meter_request", "meter", "field", 1, 0, 1, 0.16),
    ("business_tariff_switch", "subscription", "branch", 0, 1, 0, 0.14),
    ("pressure_regulator_mounting", "technical", "field", 1, 0, 1, 0.12),
    ("garden_irrigation_tariff", "subscription", "branch", 0, 1, 0, 0.10),
    ("meter_relocation", "meter", "field", 1, 0, 1, 0.09),
    ("common_area_sharing_record", "subscription", "branch", 0, 1, 0, 0.08),
    ("installation_compliance_report", "technical", "field", 1, 0, 1, 0.07),
    ("late_interest_waiver", "billing", "branch", 0, 0, 0, 0.06),
    ("mobile_access_permission", "alert", "online", 0, 0, 0, 0.05),
    ("extra_line_installation", "technical", "field", 1, 1, 1, 0.04),
]
SEGMENT = {  # propensity of the segment toward the domains; used only inside the generator
    "saver":    {"billing": 0.5, "meter": 1.7, "subscription": 0.6, "alert": 1.5, "technical": 0.6},
    "payer":    {"billing": 1.9, "meter": 0.5, "subscription": 0.6, "alert": 1.1, "technical": 0.3},
    "business": {"billing": 0.7, "meter": 0.9, "subscription": 1.6, "alert": 0.7, "technical": 1.9},
    "new":      {"billing": 0.8, "meter": 0.7, "subscription": 1.8, "alert": 1.3, "technical": 0.7},
}
SEGMENT_NAMES = list(SEGMENT)
rq = rng(SEED + 101)
QUALITY = [0.25 + 0.70 * rq() for _ in ITEMS]   # the item's own satisfaction

N_SUBSCRIBERS, N_ITEMS = 360, len(ITEMS)
SUBSCRIBERS, IMPRESSIONS, INTERACTIONS, SCORES, PROPENSITY = [], {}, {}, {}, {}
for i in range(N_SUBSCRIBERS):
    r = rng(SEED + 7919 * i)
    a, segment = 20001 + i, SEGMENT_NAMES[int(r() * 4)]
    activity = 0.35 + 1.15 * r() ** 1.6
    SUBSCRIBERS.append(a)
    for j, (name, domain, channel, paid, commitment, appointment, share) in enumerate(ITEMS):
        propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55)
        PROPENSITY[(a, j)] = propensity
        if r() < min(0.95, share ** 0.55 * 0.72):        # was it shown
            IMPRESSIONS[(a, j)] = 1
            if r() < propensity:                          # was it selected
                INTERACTIONS[(a, j)] = r()                # value: sequence stamp
                if r() < 0.32:                            # did it leave a score
                    raw = (0.16 + 0.50 * SEGMENT[segment][domain] / 1.9
                           + 0.42 * QUALITY[j] + 0.26 * (r() - 0.5))
                    SCORES[(a, j)] = max(1, min(5, int(round(raw * 5))))
        else:
            r(), r(), r()
import math

# The split of lesson 01: for a subscriber with at least two interactions, the interaction with the largest sequence stamp is held out.
log = {}
for (a, j), stamp in INTERACTIONS.items():
    log.setdefault(a, []).append((stamp, j))
TRAIN, HELD_OUT, SEEN = {}, {}, {}
for a, entries in log.items():
    entries.sort()
    if len(entries) >= 2:
        HELD_OUT[a] = entries[-1][1]
        entries = entries[:-1]
    for stamp, j in entries:
        TRAIN[(a, j)] = 1
        SEEN.setdefault(a, set()).add(j)
EVAL_SUBS = sorted(HELD_OUT)
chosen = [0] * N_ITEMS
for (a, j) in TRAIN:
    chosen[j] += 1
DOMAIN_OF = [ITEMS[j][1] for j in range(N_ITEMS)]


def make_ranker(w):
    """Popularity x the subscriber's past domain share. w=0 is the pure baseline. THE MODEL."""
    def score(a):
        counts = {}
        for i in SEEN.get(a, set()):
            counts[DOMAIN_OF[i]] = counts.get(DOMAIN_OF[i], 0) + 1
        return [chosen[j] * (1.0 + w * counts.get(DOMAIN_OF[j], 0)) for j in range(N_ITEMS)]
    return score


def rank(score, a):
    s = score(a)
    return sorted((j for j in range(N_ITEMS) if j not in SEEN.get(a, set())),
                  key=lambda j: (-s[j], j))


SETUPS = (("baseline, w=0", make_ranker(0.0)), ("light, w=1", make_ranker(1.0)),
          ("strong, w=2", make_ranker(2.0)))
print(f"training {len(TRAIN)} interactions, held-out {len(EVAL_SUBS)} subscribers; offline on the log")
print("setup         k=1     k=3     k=5     k=10    pos. disc.  coverage@5")
for name, ranker in SETUPS:
    ranked = [rank(ranker, a) for a in EVAL_SUBS]
    hits = [sum(1 for t, a in zip(ranked, EVAL_SUBS) if HELD_OUT[a] in t[:n]) / len(EVAL_SUBS)
            for n in (1, 3, 5, 10)]
    disc = sum(1.0 / math.log2(2 + t.index(HELD_OUT[a])) for t, a in zip(ranked, EVAL_SUBS)) / len(EVAL_SUBS)
    cov = len(set(j for t in ranked for j in t[:5]))
    print(f"{name:<13} {hits[0]:.4f}  {hits[1]:.4f}  {hits[2]:.4f}  {hits[3]:.4f}  {disc:.4f}      "
          f"{cov:>2}/{N_ITEMS}")

training 410 interactions, held-out 167 subscribers; offline on the log
setup         k=1     k=3     k=5     k=10    pos. disc.  coverage@5
baseline, w=0 0.2575  0.5509  0.6527  0.9162  0.5736       9/24
light, w=1    0.2635  0.5569  0.6647  0.9162  0.5766      12/24
strong, w=2   0.2635  0.5090  0.6886  0.9102  0.5727      13/24

The order of the three setups changes with the cutoff. At k = 3 the strong setup is last (0.5090) and the baseline is ahead of it. At k = 5 the strong setup is first (0.6886) and beats the baseline by 0.0359. At k = 10 the three become indistinguishable: 0.9162, 0.9162 and 0.9102. The same three rankings, the same log, three different orders at three different cutoffs. The cutoff is not a part of the reported number but the decision that produces it; unless it is written down, hit rate at k cannot be read.

Position discount gives a fourth order. In this measure the strong setup is last with 0.5727, though at k = 5 it was first. The reason is what hit rate at k does not see: the strong setup does put the correct item into the top five, but places it lower within the five. Hit rate at k counts every position inside the cutoff as equal; positional discount does not. The two measures end the same ranking in two different orders, and neither is wrong — they measure different things.

Beside the fifth column stands a sixth: coverage. The baseline recommends a total of 9 distinct items to 167 subscribers, the strong setup 13. In all three setups at least eleven items of the catalog never appear in the top five of any subscriber.

The Same Ranking, While Collecting Its Own Data

All the numbers so far were read from a single log, and that log was not collected by any of these three setups. Now the decision changes hands: each setup shows its own top five and sees the outcome.

PERIODS = 20


def online(score, k=5):
    """The ranking itself decides what is shown; the outcome is drawn from the setup."""
    total, shown = 0, set()
    for a in SUBSCRIBERS:
        top = rank(score, a)[:k]
        shown.update(top)
        for day in range(PERIODS):
            r = rng(SEED + 880000 + a * 37 + day * 911)
            for j in top:
                if r() < PROPENSITY[(a, j)]:
                    total += 1
    return total / (len(SUBSCRIBERS) * PERIODS), len(shown)


print(f"online: each setup shows its own top five, {PERIODS} periods, {len(SUBSCRIBERS)} subscribers")
for name, ranker in SETUPS:
    e, g = online(ranker)
    expected = sum(sum(PROPENSITY[(a, j)] for j in rank(ranker, a)[:5]) for a in SUBSCRIBERS) / len(SUBSCRIBERS)
    print(f"  {name:<13} interactions per subscriber {e:.4f}  (expected {expected:.4f})  "
          f"items shown {g}/{N_ITEMS}")

online: each setup shows its own top five, 20 periods, 360 subscribers
  baseline, w=0 interactions per subscriber 1.4581  (expected 1.4519)  items shown 9/24
  light, w=1    interactions per subscriber 1.4788  (expected 1.4795)  items shown 12/24
  strong, w=2   interactions per subscriber 1.4563  (expected 1.4560)  items shown 13/24

The offline order was this: baseline 0.6527, light 0.6647, strong 0.6886 — strong first. The online order is this: strong 1.4563, baseline 1.4581, light 1.4788 — strong last and below even the baseline. The setup that was first on the offline log cannot even beat the baseline, which does not personalize at all, once it starts making its own decisions.

The differences are small and it must be written that they are: between the best and the worst online there are 0.0225 interactions per subscriber. What is measured is not the size of the difference but the order not carrying over. Since the number drawn over twenty periods stayed within five parts per thousand of the expected value, this order does not come from sampling noise; it comes from the setups themselves.

What the Log Cannot See

from collections import Counter

held_counts = Counter(HELD_OUT.values())
unshown = sum(1 for a in EVAL_SUBS for j in range(N_ITEMS) if (a, j) not in IMPRESSIONS)
print(f"what the log can see: {len(EVAL_SUBS)} subscribers x {N_ITEMS} items = {len(EVAL_SUBS) * N_ITEMS} "
      f"cells, {unshown} ({unshown / (len(EVAL_SUBS) * N_ITEMS):.4f}) never shown")
top_five = sorted(range(N_ITEMS), key=lambda j: (-chosen[j], j))[:5]
print(f"{sum(held_counts[j] for j in top_five) / len(HELD_OUT):.4f} of the held-out items come from the "
      f"five items most chosen in training; {sum(1 for j in range(N_ITEMS) if held_counts[j] == 0)} items "
      f"never appear in the held-out set")


def setup_propensity(a):
    """Not a method: the true propensity of the simulated setup itself. Gives the online ceiling."""
    return [PROPENSITY[(a, j)] for j in range(N_ITEMS)]


e, g = online(setup_propensity)
ranked = [rank(setup_propensity, a) for a in EVAL_SUBS]
print(f"setup propensity (online ceiling): online {e:.4f}, items shown {g}/{N_ITEMS}")
print(f"  offline hit rate@5 of the same ranking "
      f"{sum(1 for t, a in zip(ranked, EVAL_SUBS) if HELD_OUT[a] in t[:5]) / len(EVAL_SUBS):.4f}")

what the log can see: 167 subscribers x 24 items = 4008 cells, 2527 (0.6305) never shown
0.5868 of the held-out items come from the five items most chosen in training; 3 items never appear in the held-out set
setup propensity (online ceiling): online 1.6606, items shown 13/24
  offline hit rate@5 of the same ranking 0.7485

The divergence comes from here. 0.6305 of the held-out set consists of cells never shown: for those cells the log holds neither a selection nor a rejection, only a blank. The offline measure has to count this blank as a rejection, because it has no other reading at hand. The more never-shown items a setup recommends, the more it is penalized offline — even if that item suits the subscriber.

The second line shows the same thing from the correct-answer side: 0.5868 of the held-out items come from the five items most chosen in training, and 3 items never appear in the held-out set. A setup that recommends those three items can never score offline. The correct answer itself is a trace of past impression decisions.

The third line gives the ceiling of the measure. Ranking by the true propensity of the simulated setup gives 1.6606 online; the baseline stands at 1.4581, the best setup at 1.4788. The best of the three setups closes one tenth of the gap between the ceiling and the baseline. The offline hit rate@5 of the same ranking is 0.7485, so the offline measure cannot take even the ceiling to 1 — the log can score even the best possible ranking only over items that were shown.

Summary

• Hit rate at k cannot be read without the cutoff being written: the strong setup is last at k=3 (0.5090), first at k=5 (0.6886), and at k=10 the three setups are indistinguishable (0.9162 / 0.9162 / 0.9102).
• Position discount sees what the first k does not: the setup that is first at k=5 is last on position weight with 0.5727, because it puts the correct item lower within the top five.
• The setup that is first offline (0.6886) is last online (1.4563) and falls below the baseline that does not personalize at all (1.4581); the order does not carry over.
• The cause of the divergence is the log itself: 0.6305 of the held-out cells were never shown, 0.5868 of the held-out items come from five items, and 3 items never appear in the held-out set.
• The online ceiling is 1.6606; the difference between the baseline at 1.4581 and the best setup at 1.4788 is about one tenth of the gap between the ceiling and the baseline.

Next Step

In this lesson each setup looked at the log once and made its decision once. In a real system the decision repeats: the item shown produces an interaction, the interaction grows the log, and the growing log determines the next impression. The coverage column already says where this loop is going — the baseline shows 9 of 24 items, the strong setup 13, and an item that is not shown will be shown with even fewer reasons in the next round. The next lesson runs this loop for a few dozen periods: how many items end up never shown, how much popularity bias grows, and in which period the short-term cost of increasing diversity and its long-term gain become equal.