The Recommendation Problem

In seven lessons the agent chose its own action and learned the result from the environment: what happened when a crew was sent to a subscriber and what happened when it was not was recorded step by step. Now the action changes hands. The only thing the system can do is to offer one option to a subscriber, and the result becomes visible only if that subscriber chooses it. The result of an option that is not offered is never born; why an option that was offered but not chosen was not chosen is not recorded. The collected data is the trace of the system’s own offering decisions.

This lesson builds the data of that setup and produces two numbers: the hit rate at five of the baseline that offers everyone the same item, and how far apart the two rankings are that come from reading the same data implicitly and explicitly. The rule of the course is paid for here for the first time: an item that is not shown is not scored, and an item that is not scored is not shown.

• RS1. The dataset is fictional, seed 20260218: 360 subscribers, 24 service items, 8,640 cells. The items are service applications of the regional measurement network (such as a tariff change, a meter replacement, an installment plan, a remote reading application).
• RS2. Three events are generated separately: impression, selection, score. An item cannot be selected without being shown and cannot be scored without being selected. The chain was put into the setup on purpose.
• RS3. A subscriber’s true propensity toward an item is inside the generator and is read only for measurement; no method sees it.
• RS4. Implicit feedback is the selection itself and is 0/1. Explicit feedback is a score between 1 and 5 and is left in only some of the selections.
• RS5. Which item was shown to whom in the past is biased by its share: an item that is applied for often was offered a lot, a rare one little. This bias was put into the setup on purpose.
• RS6. Held-out set: the last interaction of every subscriber with at least two interactions. The rest is the training set.
• RS7. The measure is the hit rate at k: whether the subscriber’s held-out item is within the first k recommendations. The definitions of precision and recall were set up in the Supervised Learning course and are not repeated here.
• RS8. Two baselines are built: the random order and the order of the items chosen most often in training. The second is the real baseline, because it contains no personalization and still feeds on the curve of the catalog.

The Interaction Matrix and Sparsity

The row of the matrix is a subscriber, the column a service item. A cell being filled says that the subscriber selected that item; being empty is a mixture of two separate things and cannot be told apart: the item may have been offered but not selected, or it may never have been offered. The setup generates the two separately, so during measurement it can be counted how much of each there is.

# 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()

CELLS = N_SUBSCRIBERS * N_ITEMS
counts = {}
for (a, j) in INTERACTIONS:
    counts[a] = counts.get(a, 0) + 1
print("matrix", N_SUBSCRIBERS, "subscribers x", N_ITEMS, "items =", CELLS, "cells")
for name, d in (("impression", IMPRESSIONS), ("interaction", INTERACTIONS), ("score", SCORES)):
    print(f"  {name:12s} {len(d):5d}  fill {len(d)/CELLS:.4f}  sparsity {1-len(d)/CELLS:.4f}")
print("subscribers with no interaction", N_SUBSCRIBERS - len(counts),
      " mean per subscriber", round(len(INTERACTIONS) / N_SUBSCRIBERS, 3),
      " max", max(counts.values()))

matrix 360 subscribers x 24 items = 8640 cells
  impression    3002  fill 0.3475  sparsity 0.6525
  interaction    577  fill 0.0668  sparsity 0.9332
  score          218  fill 0.0252  sparsity 0.9748
subscribers with no interaction 80  mean per subscriber 1.603  max 7

The three fill rates describe three separate problems. The impression matrix is 0.3475 full, the selection matrix 0.0668, the score matrix 0.0252. The sparsity at the selection level is 0.9332: out of every hundred cells, sixty-seven were offered but not selected and twenty-six were never offered. An average of 1.603 interactions falls to each subscriber, and 80 of the 360 subscribers have no interaction at all. Deciding what to recommend to a subscriber in this table means drawing a decision from a matrix in which most rows are almost entirely empty.

Offering Everyone the Same Item

The baseline of the recommendation field is a procedure without personalization: ranking the items chosen most often in the training set and offering everyone the same list. This baseline does not tell any subscriber apart from another, yet it feeds on the skew of the catalog and, surprisingly, climbs high. A second baseline is placed next to it: ordering the items the subscriber has not seen in a random order.

# Split: the LAST interaction of every subscriber with at least two interactions goes to the held-out set.
TRAIN, HELD_OUT, SEEN = {}, {}, {}
log = {}
for (a, j), stamp in INTERACTIONS.items():
    log.setdefault(a, []).append((stamp, j))
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)

n_chosen = [0] * N_ITEMS
for (a, j) in TRAIN:
    n_chosen[j] += 1
ranked = sorted(range(N_ITEMS), key=lambda j: -n_chosen[j])


def hit_rate(recommend, K):
    return sum(1 for a in HELD_OUT if HELD_OUT[a] in recommend(a)[:K]) / len(HELD_OUT)


def baseline_popularity(a):
    return [j for j in ranked if j not in SEEN.get(a, set())]


rg = rng(SEED + 31)


def baseline_random(a):
    candidates = [j for j in range(N_ITEMS) if j not in SEEN.get(a, set())]
    for i in range(len(candidates) - 1, 0, -1):
        t = int(rg() * (i + 1))
        candidates[i], candidates[t] = candidates[t], candidates[i]
    return candidates


print("training", len(TRAIN), "interactions / held-out", len(HELD_OUT), "subscribers")
print("five items chosen most often in training:")
for j in ranked[:5]:
    print(f"  {ITEMS[j][0]:32s} {n_chosen[j]:3d}")
for K in (3, 5):
    p, s = hit_rate(baseline_popularity, K), hit_rate(baseline_random, K)
    print(f"hit rate at {K}: popularity {p:.4f}  random {s:.4f}  ratio {p/s:.2f}")
print("catalog coverage of the popularity baseline",
      len({j for a in HELD_OUT for j in baseline_popularity(a)[:5]}), "/", N_ITEMS)

training 410 interactions / held-out 167 subscribers
five items chosen most often in training:
  payment_reminder_sms              68
  e_invoice_switch                  64
  auto_payment_instruction          47
  installment_plan                  39
  debt_restructuring                27
hit rate at 3: popularity 0.5509  random 0.1437  ratio 3.83
hit rate at 5: popularity 0.6527  random 0.2036  ratio 3.21
catalog coverage of the popularity baseline 9 / 24

The baseline without personalization catches the held-out item of 109 of the 167 subscribers in the first five: hit rate 0.6527. The random order stays at 0.2036 on the same measure, a ratio of 3.21. Going down to the first three, the baseline gives 0.5509 and the ratio rises to 3.83. This number is a threshold for the rest of this course: if a recommendation method does not exceed 0.6527, it is no better than a list that makes no distinction between subscribers.

The price the baseline pays is in the fourth line: a total of 9 distinct items appear in the first-five lists of the 167 subscribers, while there are 24 items in the catalog. Fifteen items are never recommended to any subscriber. The baseline buys its high hit rate by making fifteen items of the catalog completely invisible, and an item that is not visible does not enter the data of the next period either.

Implicit and Explicit Feedback

Implicit feedback is the selection itself: the subscriber applied or did not. Explicit feedback is the score the subscriber left. The two look as if they measure the same catalog, but they count different things. The implicit signal measures volume and carries the impression count inside it; the explicit signal measures satisfaction after selecting and comes only from a part of those who selected.

imp, sel, n_scores, total = ([0] * N_ITEMS for _ in range(4))
for (a, j) in IMPRESSIONS:
    imp[j] += 1
for (a, j) in INTERACTIONS:
    sel[j] += 1
for (a, j), p in SCORES.items():
    n_scores[j] += 1
    total[j] += p
mean_score = [total[j] / n_scores[j] if n_scores[j] else 0.0 for j in range(N_ITEMS)]

rank_implicit = sorted(range(N_ITEMS), key=lambda j: -sel[j])
rank_explicit = sorted([j for j in range(N_ITEMS) if n_scores[j] > 0], key=lambda j: -mean_score[j])
print(f"{'item':32s} {'impressions':>11s} {'selections':>10s} {'scores':>6s} {'average':>9s}")
for j in rank_implicit[:3] + rank_explicit[:3]:
    print(f"{ITEMS[j][0]:32s} {imp[j]:11d} {sel[j]:10d} {n_scores[j]:6d} {mean_score[j]:9.2f}")
print("implicit top 5 and explicit top 5 intersection", len(set(rank_implicit[:5]) & set(rank_explicit[:5])))
print("items never selected", sum(1 for j in range(N_ITEMS) if sel[j] == 0),
      " items with fewer than ten scores", sum(1 for j in range(N_ITEMS) if n_scores[j] < 10))
print("cells never shown", CELLS - len(IMPRESSIONS),
      " their score count", sum(1 for k in SCORES if k not in IMPRESSIONS))
print("subscribers who left no score", N_SUBSCRIBERS - len({a for (a, j) in SCORES}))
rank_score = sorted(range(N_ITEMS), key=lambda j: -mean_score[j])
print(f"hit rate at 5 -- by average score {hit_rate(lambda a: [j for j in rank_score if j not in SEEN.get(a, set())], 5):.4f}")

item                             impressions selections scores   average
e_invoice_switch                         215         93     30      3.27
payment_reminder_sms                     236         89     31      3.06
auto_payment_instruction                 242         73     24      3.83
address_update                           158         37     14      4.79
second_meter_request                      96          9      3      4.33
business_tariff_switch                    91          5      4      4.25
implicit top 5 and explicit top 5 intersection 1
items never selected 1  items with fewer than ten scores 16
cells never shown 5638  their score count 0
subscribers who left no score 205
hit rate at 5 -- by average score 0.1497

The number of items common to the first five of the two rankings is 1. The three items at the top of the implicit ranking each received more than two hundred impressions and their average scores lie between 3.06 and 3.83; two of the items at the top of the explicit ranking have score counts of 3 and 4. Recommending by average score drops the hit rate at five to 0.1497, which is even below the 0.2036 of the random order.

The source of the number is in the third and fourth lines. 16 of the catalog’s 24 items have fewer than ten scores, because an item shown little is selected little, and an item selected little is scored little. The 5,638 cells that were never shown have a score count of zero; this is not a finding but the definition of the chain. 205 of the subscribers left no score at all. Explicit feedback carries a richer signal, but it carries it where it carries it: on the items the system showed before. An item that is not shown is not scored, and a list ranked by average score says nothing about the part of the catalog that is not visible.

The collected data is the third number of this lesson and consists of two parts: the 5,638 cells that were never shown and the 15 items outside the lists the baseline recommends. If these two numbers are not written when a recommendation method is measured, it is not known which catalog the measure belongs to.

Summary

• The fictional matrix meets 360 subscribers and 24 service items in 8,640 cells; the impression fill rate is 0.3475, the selection 0.0668, the score 0.0252. At the selection level the sparsity is 0.9332 and 80 subscribers have no interaction at all.
• The baseline offers everyone, in the same order, the items chosen most often in training; its hit rate at five is 0.6527 and at three 0.5509. The random order gives 0.2036 and 0.1437 on the same measures.
• The price of the baseline is coverage: only 9 distinct items appear in the first-five lists of 167 subscribers, and fifteen items are recommended to no subscriber.
• Implicit and explicit feedback produce two separate rankings in the same catalog; the intersection of their first fives is one, and recommending by average score gives a hit rate of 0.1497.
• The explicit signal is sparse and depends on impressions: 16 of the 24 items have fewer than ten scores, 205 subscribers left no score, and the 5,638 cells that were never shown have a score count of zero.

Next Step

The baseline set a threshold with 0.6527, but it did so by never showing fifteen items of the catalog, and it has no separate word for the 80 subscribers who have no interaction. The first question is this: even when no data has come from the subscriber, is there something known about the item itself. In the catalog each item’s domain, channel, whether it is paid, and whether it requires a commitment and an appointment are written down. The next lesson extracts a profile per subscriber from these features, ranks the recommendations by similarity to the profile, and measures two numbers: for how many subscribers no recommendation can be produced at all, and how similar the recommendations produced are to one another.