Cold Start

In four lessons the recommendation was always produced from existing interactions: the content-based approach from the features of the item, collaborative filtering from the history of neighboring subscribers, matrix factorization from latent factors. All three had a silent common condition: the subscriber has a filled row. What to do for a subscriber whose row is entirely empty and an item whose column is entirely empty was never asked.

What this lesson measures is not accuracy but warming: how many subscribers and how many items are cold, and how many of them each solution makes able to produce a recommendation. Every warming has a price, and the price is counted on the same line.

• RS41. The setup is the same block built in the first lesson and gives the same numbers: 360 subscribers, 24 service items, 8,640 cells, seed 20260218; 3,002 impressions, 577 interactions, 218 scores.
• RS42. A cold subscriber is a subscriber with no interaction in the training set. A cold item is an item never selected in the training set.
• RS43. The cold protocol changes the split. A subscriber with no interaction has no correct answer either and cannot enter the measure. For a subscriber with a single interaction that single interaction is hidden: the row is emptied and the correct answer is known. The remaining interactions are the training set.
• RS44. The baseline is offering the five items most chosen in training to everyone. This is the baseline built in the first lesson; since nothing else is at hand for a cold subscriber, it is the one chosen here too.
• RS45. Warming is a solution making a cold subscriber or a cold item able to produce a recommendation, and its number is how many subscribers, how many items.
• RS46. The price is written with three numbers: the number of questions asked, the number of subscribers left unanswered and the number of distinct items the recommendations spread over.
• RS47. The three-question intake is fictional: the domain you are interested in, the second domain, application frequency. The answer rate is 0.62 and is a parameter of the setup.
• RS48. The measure is the top-five hit rate; its definition was built in the first lesson and is not repeated here.

Counting What Is Cold

# 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()
log = {}
for (a, j), stamp in INTERACTIONS.items():
    log.setdefault(a, []).append((stamp, j))
ZERO_SUBS = [a for a in SUBSCRIBERS if a not in log]
SINGLE_SUBS = sorted(a for a in log if len(log[a]) == 1)
MULTI_SUBS = [a for a in log if len(log[a]) >= 2]
HIDDEN = {a: log[a][0][1] for a in SINGLE_SUBS}      # COLD PROTOCOL: the single interaction is hidden
TRAIN = dict(((a, j), 1) for a in MULTI_SUBS for _, j in log[a])
chosen = [0] * N_ITEMS
for (a, j) in TRAIN:
    chosen[j] += 1
COLD_ITEMS = [j for j in range(N_ITEMS) if chosen[j] == 0]
FEWEST = sorted(range(N_ITEMS), key=lambda j: (chosen[j], j))
RANKED = sorted(range(N_ITEMS), key=lambda j: (-chosen[j], j))
print(f"{N_SUBSCRIBERS} subscribers: {len(ZERO_SUBS)} zero interactions, {len(SINGLE_SUBS)} single interaction, "
      f"{len(MULTI_SUBS)} two or more")
print(f"cold subscribers {len(ZERO_SUBS) + len(SINGLE_SUBS)}; measurable {len(SINGLE_SUBS)} subscribers, "
      f"training set {len(TRAIN)} interactions")
print(f"cold items {len(COLD_ITEMS)}: {', '.join(ITEMS[j][0] for j in COLD_ITEMS)}; "
      f"below five interactions {sum(1 for j in range(N_ITEMS) if chosen[j] < 5)} items")
print("baseline list (five most chosen items in training):")
for j in RANKED[:5]:
    print(f"  {ITEMS[j][0]:26s} {chosen[j]:3d}")

360 subscribers: 80 zero interactions, 113 single interaction, 167 two or more
cold subscribers 193; measurable 113 subscribers, training set 464 interactions
cold items 1: mobile_access_permission; below five interactions 8 items
baseline list (five most chosen items in training):
  e_invoice_switch            76
  payment_reminder_sms        71
  auto_payment_instruction    58
  installment_plan            46
  remote_reading_application  31

Three numbers describe three separate groups of subscribers. 80 subscribers have no interaction; for them there is neither a history nor a correct answer, so they cannot enter any measure, yet they arrive at the system every day. 113 subscribers have a single interaction, and the cold protocol hides that single interaction: their rows are emptied and their correct answers stay at hand. The total of cold subscribers is 193, a little more than half of the 360 subscribers; the measurable part is 113.

The item side is much narrower: 1 item was never selected in the training set, and 8 items remain below five interactions. The baseline list reflects the skew of the catalog as it is: five items collect 282 of the 464 interactions. Being cold and not being recommended are separate things: the previous lessons measured that the baseline list recommended 15 of the 24 items to no subscriber, yet those items have interactions and are not cold; they merely never enter the ranking. The two faces of cold start do not carry the same weight either: in this setup the cold subscriber problem is much larger than the cold item problem.

Warming the Item: The Feature Bridge

A cold item has no interaction but has features: which domain it belongs to, which channel it runs through, whether it is paid, whether it asks for a commitment, whether it needs an appointment. The bridge uses these features to connect the cold item to its warm neighbors, and the item enters the list of the subscribers who have interacted with those neighbors.

import math

DOMAINS = ["billing", "meter", "subscription", "alert", "technical"]
CHANNELS = ["online", "field", "branch"]


def features(j):
    """Item features: domain, channel and three binary flags. Needs no interaction."""
    name, domain, channel, paid, commitment, appointment, p = ITEMS[j]
    return ([1.0 if domain == x else 0.0 for x in DOMAINS]
            + [1.0 if channel == x else 0.0 for x in CHANNELS]
            + [float(paid), float(commitment), float(appointment)])


def similar(i, j):
    x, y = features(i), features(j)
    return sum(p * q for p, q in zip(x, y)) / (
        math.sqrt(sum(p * p for p in x) * sum(q * q for q in y)) + 1e-9)


warm = [j for j in range(N_ITEMS) if chosen[j] > 0]
print("content-based bridge; last column number of subscribers who interacted with its neighbors")
for j in FEWEST[:4]:
    nbrs = sorted(warm, key=lambda t: (-similar(j, t), t))[:2]
    if j in nbrs:
        nbrs = [t for t in nbrs if t != j] + [sorted(warm, key=lambda t: (-similar(j, t), t))[2]]
    reach = set(a for (a, t) in TRAIN if t in nbrs)
    print(f"  {ITEMS[j][0]:32s}{chosen[j]:2d}  neighbors: {ITEMS[nbrs[0]][0]}, "
          f"{ITEMS[nbrs[1]][0]} -> {len(reach):>3}")
print(f"bridge puts {len(COLD_ITEMS)}/{len(COLD_ITEMS)} cold items into the recommendation pool, "
      f"warms 0/{len(ZERO_SUBS) + len(SINGLE_SUBS)} cold subscribers")

content-based bridge; last column number of subscribers who interacted with its neighbors
  mobile_access_permission         0  neighbors: e_invoice_switch, payment_reminder_sms -> 114
  installation_compliance_report   1  neighbors: pressure_regulator_mounting, installation_maintenance_package ->  10
  late_interest_waiver             1  neighbors: invoice_dispute_record, installment_plan ->  53
  extra_line_installation          1  neighbors: installation_maintenance_package, pressure_regulator_mounting ->  10
bridge puts 1/1 cold items into the recommendation pool, warms 0/193 cold subscribers

The bridge solves the cold item problem: 1/1. The width of the reach depends on who the neighbor is, and this is the hidden price of the bridge. mobile_access_permission reaches 114 subscribers because its closest neighbors are online alert items; installation_compliance_report and extra_line_installation reach 10 subscribers each because they neighbor field technical items. The bridge warms an item only as much as the prevalence of its own neighbors: a cold item with a prevalent neighbor warms at once, one with a sparse neighbor stays cold. Warming an item borrows not the popularity of the column itself but that of its neighbor.

The last line writes the real limit: the bridge warms 0/193 cold subscribers. In the setup the item has features, the subscriber does not; the only thing known about a subscriber is their history, and the history of a cold subscriber is empty. The content-based approach sees only one face of cold start.

Warming the Subscriber: The Three-Question Intake

On the subscriber side two options remain: to fall back to the baseline, offering everyone the same five items, or to ask the subscriber. The second produces data that is not in the log, and its price is the question.

SEGMENT_OF = dict((20001 + i, SEGMENT_NAMES[int(rng(SEED + 7919 * i)() * 4)])
                  for i in range(N_SUBSCRIBERS))
ANSWERS = {}
for a in SINGLE_SUBS:                               # three questions: domain, second domain, activity
    q = rng(SEED + 555000 + a)
    if q() < 0.62:                                  # the answer rate is fictional
        s = sorted(SEGMENT[SEGMENT_OF[a]], key=lambda x: -SEGMENT[SEGMENT_OF[a]][x])
        ANSWERS[a] = (s[0], s[1], 0.35 + 1.15 * rng(SEED + 7919 * (a - 20001))() ** 1.6)


def baseline(a):
    return RANKED[:5]


def intake(a, third=False):
    """Domain order if answered, baseline list if not. THE MODEL."""
    if a not in ANSWERS:
        return RANKED[:5]
    d1, d2, activity = ANSWERS[a]
    mult = activity if third else 1.0               # the third answer multiplies every item equally
    return sorted(range(N_ITEMS), key=lambda j: (
        -mult * (chosen[j] + 1) ** 0.35 * (3.0 if ITEMS[j][1] == d1 else
                                           1.8 if ITEMS[j][1] == d2 else 1.0), j))[:5]


print(f"three-question intake: {3 * len(SINGLE_SUBS)} questions asked, {len(ANSWERS)} subscribers answered, "
      f"{len(SINGLE_SUBS) - len(ANSWERS)} subscribers fell to the baseline list")
for name, f in (("baseline (popularity)", baseline), ("intake, two answers", intake),
                ("intake, three answers", lambda a: intake(a, True))):
    hit = sum(1 for a in SINGLE_SUBS if HIDDEN[a] in f(a)) / len(SINGLE_SUBS)
    cov = len(set(j for a in SINGLE_SUBS for j in f(a)))
    print(f"  {name:<22} hit rate@5 {hit:.4f}  coverage {cov:>2}/{N_ITEMS}")

three-question intake: 339 questions asked, 71 subscribers answered, 42 subscribers fell to the baseline list
  baseline (popularity)  hit rate@5 0.5752  coverage  5/24
  intake, two answers    hit rate@5 0.5487  coverage 13/24
  intake, three answers  hit rate@5 0.5487  coverage 13/24

What the three solutions warm can now be read side by side. The popularity fallback warms 193/193 subscribers and 0/1 items; the feature bridge 0/193 subscribers and 1/1 items; the three-question intake 71 of the 113 measurable subscribers and 0/1 items. None warms both faces at once. Cold start is not a single problem; it is two separate problems and asks for two separate solutions.

The prices also stand side by side. For the intake 339 questions were asked and 42 subscribers gave no answer and fell back to the baseline; the answer rate being 0.62 is a choice of the setup, and a lower rate pulls the number of warmed subscribers down directly. The price of the third question is of a special kind: since the application frequency answer multiplies every item by the same coefficient, it does not change the ranking at all, and both hit rate and coverage come out exactly the same as in the setup with two answers. In return for this third question asked of each of 113 subscribers, the system gets no change in ranking. Whether an answer carries information depends on whether it separates the options from one another.

The price of the baseline is not in the question but in the uniformity: a total of 5 distinct items were recommended to 113 subscribers. The intake raises this number to 13. In return, the top-five hit rate read from the log is 0.5752 at the baseline and 0.5487 at the intake: when the question is asked, the measure falls. It matters which log these numbers are read from: the single hidden interaction is the one interaction that subscriber had with a shown item, and the impression order largely presented the top end of the catalog. The baseline recommends exactly that top end.

Summary

• Cold start is two separate problems: in the fictional matrix 80 subscribers have no interaction and 113 have a single one, and once the single interaction is hidden 193 subscribers count as cold; on the item side, in the training set of 464 interactions 1 item was never selected and 8 items are below five.
• The popularity fallback warms 193/193 subscribers, warms no item and gives all of them the same 5 items; the feature bridge warms 1/1 items, warms no cold subscriber and carries the item only as far as the prevalence of its neighbor: 114 subscribers against 10.
• The three-question intake warms 71 subscribers for 339 questions, 42 subscribers stay unanswered and coverage rises from 5 to 13 items; since the third question multiplies every item by the same coefficient, it does not change the ranking at all.
• The top-five hit rate read from the log is 0.5752 at the baseline and 0.5487 at the intake; this log consists only of interactions with shown items.

Next Step

The last table of this lesson says something odd: asking the cold subscriber questions and turning the recommendations toward the domain they themselves named lowered the number read from the log. There are two explanations. Either the questions do not work, or the measure is read from the wrong place, because every interaction in the log was born at a moment when the decision was made not by the system but by the impression order, and the interaction of an item that was not shown never appears in the log. The next lesson builds ranking measures: top k, the cutoff and positional discount. Then it measures the same ranking twice, once on this log and once while the ranking itself decides what is shown. The two numbers are printed side by side.