Collaborative Filtering

The previous lesson produced the recommendation from the features of the item. The domain, channel and whether it was paid for were written in the catalog for every item. A profile was extracted from the subscriber’s history and the items were ranked by their similarity to it. In that setup every subscriber is on their own: whatever is in their own file is looked at, and no other subscriber’s file is looked at. Yet there is a table of 360 subscribers at hand, and inside it is information that was never used: subscribers resemble one another. If two subscribers have both applied for an installment plan and debt restructuring, a third item that one applied for is a candidate for the other as well, and this prediction can be made without looking at the features of the items at all.

This is collaborative filtering: the recommendation is produced not from what the item is but from who uses it together with whom. This lesson measures how much the number of neighbors moves the ranking, and where the neighborhood breaks as the matrix gets sparser: between two subscribers with no common item the similarity is not defined, and sparsity produces exactly this.

• RS21. The setup, the dataset, the split rule and the measure carry on exactly from the first lesson: 360 subscribers, 24 service items, seed 20260218, and the last interaction of a subscriber with at least two interactions goes to the held-out set. The code is rebuilt here and the numbers do not change.
• RS22. From the item catalog only the domain and the base share are read in this lesson; collaborative filtering never looks at the features.
• RS23. The measure is hit rate@5 and next to it the mean rank. Larger is better for the first, smaller for the second. The candidate set is the items the subscriber has not seen in training.
• RS24. The baseline is the order of the most chosen item from the first lesson; it makes no distinction between subscribers and is the threshold a method has to pass.
• RS25. Similarity is the number of common items of two binary vectors divided by the square root of the product of their lengths. A pair with no common item never enters the similarity list; a zero similarity is not recorded, and this is the definition of having no neighbor.
• RS26. The number of neighbors $K$ is a hyperparameter. 7 candidates were tried on the user-based side and 6 on the item-based side; no separate hyperparameter-selection set was set aside, because what is measured is not the best setting but how much the setting moves the ranking.
• RS27. Among items with equal scores the order is resolved by the catalog index. The catalog is in decreasing order of base share, so for a subscriber whose scores are all zero the ranking silently falls to the popularity order. The last section measures this.
• RS28. The number of items shown is the union of the top fives of the held-out subscribers and is the third number of the course: an item that is never shown is never selected.
• RS29. In the sparsity sweep a share of the training interactions is kept and the held-out items never change; this way the five rows are read on the same 167 subscribers.

No Neighbor Without a Common Item

The first block builds the setup, the split and the baseline.

# The setup catalog comes from the first lesson; here only the item's domain and base share are needed.
SEED, M32, N_SUBSCRIBERS = 20260218, 0xFFFFFFFF, 360
ITEMS = [("billing", 0.90), ("alert", 0.85), ("alert", 0.78), ("billing", 0.62),
         ("meter", 0.55), ("alert", 0.50), ("billing", 0.44), ("subscription", 0.40),
         ("meter", 0.36), ("alert", 0.32), ("billing", 0.28), ("subscription", 0.25),
         ("meter", 0.22), ("technical", 0.19), ("meter", 0.16), ("subscription", 0.14),
         ("technical", 0.12), ("subscription", 0.10), ("meter", 0.09), ("subscription", 0.08),
         ("technical", 0.07), ("billing", 0.06), ("alert", 0.05), ("technical", 0.04)]
SEGMENT = {
    "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, N_ITEMS = list(SEGMENT), len(ITEMS)


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


SUBSCRIBERS, INTERACTIONS = [], {}
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, (domain, share) in enumerate(ITEMS):
        propensity = min(0.95, SEGMENT[segment][domain] * share * activity * 0.55)
        if r() < min(0.95, share ** 0.55 * 0.72):     # was it shown
            if r() < propensity:                       # was it selected
                INTERACTIONS[(a, j)] = r()             # value: sequence stamp
                if r() < 0.32:
                    r()                                # a score was left; not used here
        else:
            r(), r(), r()

LOG, TRAIN, HELD_OUT = {}, {}, {}
for (a, j), stamp in INTERACTIONS.items():
    LOG.setdefault(a, []).append((stamp, j))
SEEN = {a: set() for a in SUBSCRIBERS}
for a, entries in LOG.items():
    entries.sort()
    if len(entries) >= 2:                                # the split rule is from the first lesson
        HELD_OUT[a] = entries[-1][1]
        entries = entries[:-1]
    for stamp, j in entries:
        TRAIN[(a, j)] = 1
        SEEN[a].add(j)

EVAL_SUBS = sorted(HELD_OUT)
N_CHOSEN = [sum(1 for (a, j) in TRAIN if j == jj) for jj in range(N_ITEMS)]


def measure(score, seen=None, who=None, k=5):
    seen, who = seen or SEEN, who or EVAL_SUBS
    hit, rank, shown = 0, 0, set()
    for a in who:
        s = score(a)
        candidates = sorted((j for j in range(N_ITEMS) if j not in seen[a]),
                            key=lambda j: (-s[j], j))
        shown.update(candidates[:k])
        p = candidates.index(HELD_OUT[a])
        hit, rank = hit + (p < k), rank + p + 1
    return hit / len(who), rank / len(who), len(shown)


print("interaction", len(INTERACTIONS), "-- training", len(TRAIN), "-- held-out subscribers", len(HELD_OUT))
print("sparsity of the training matrix",
      round(1 - len(TRAIN) / (N_SUBSCRIBERS * N_ITEMS), 4))
print("baseline -- most chosen item: hit rate@5 %.4f, mean rank %.2f, shown %d/24"
      % measure(lambda a: N_CHOSEN))

interaction 577 -- training 410 -- held-out subscribers 167
sparsity of the training matrix 0.9525
baseline -- most chosen item: hit rate@5 0.6527, mean rank 4.74, shown 9/24

Once the held-out items are removed, the sparsity of the training matrix rises to 0.9525. Three hundred sixty rows, twenty-four columns and 410 filled cells: all the material the method has for neighborhoods.

User-Based: The Number of Neighbors Moves the Ranking

The similarity routine is written once: given the item sets of the subscribers it yields subscriber similarity, and given the subscriber sets of the items it yields item similarity. A subscriber’s score for an item is the sum of the similarities of those among their $K$ most similar neighbors who have that item.

def similarities(sets, keys):
    n = {u: max(1e-9, len(sets[u])) ** 0.5 for u in keys}
    result = {}
    for u in keys:
        b = [(len(sets[u] & sets[v]) / (n[u] * n[v]), v)
             for v in keys if v != u and sets[u] & sets[v]]
        b.sort(key=lambda t: (-t[0], t[1]))
        result[u] = b
    return result


def user_based(B, seen, K):
    def score(a):
        s = [0.0] * N_ITEMS
        for w, v in B[a][:K]:
            for j in seen[v]:
                s[j] += w
        return s
    return score


def top_k(score, a, seen, k=5):
    s = score(a)
    return set(sorted((j for j in range(N_ITEMS) if j not in seen[a]),
                      key=lambda j: (-s[j], j))[:k])


SIM = similarities(SEEN, SUBSCRIBERS)
BASE5 = {a: top_k(lambda x: N_CHOSEN, a, SEEN) for a in EVAL_SUBS}
print(f"{'K':>4} {'hit rate@5':>10} {'mean rank':>9} {'items shown':>11} "
      f"{'prev K':>9} {'overlap':>8}")
previous = None
for K in (3, 5, 10, 20, 40, 80, 160):
    p = user_based(SIM, SEEN, K)
    h, s, cov = measure(p)
    cur = {a: top_k(p, a, SEEN) for a in EVAL_SUBS}
    o = ("%.2f" % (sum(len(cur[a] & previous[a]) for a in EVAL_SUBS) / len(EVAL_SUBS))
         if previous else "--")
    t = sum(len(cur[a] & BASE5[a]) for a in EVAL_SUBS) / len(EVAL_SUBS)
    print(f"{K:>4} {h:>10.4f} {s:>9.2f} {cov:>11} {o:>9} {t:>8.2f}")
    previous = cur

   K hit rate@5 mean rank items shown    prev K  overlap
   3     0.6946      4.66          16        --     4.07
   5     0.6886      4.64          18      4.89     4.01
  10     0.6707      4.80          19      4.71     3.85
  20     0.6168      5.25          20      4.51     3.62
  40     0.5988      5.54          20      4.14     3.49
  80     0.6467      5.28          18      4.08     3.96
 160     0.6647      5.18          14      4.72     4.12

The best setting is 0.6946 at three neighbors, 0.0419 above the baseline. But the worst candidate of the same column is 0.5988 at forty neighbors, that is 0.0539 below the baseline. The movement across the seven candidates is 0.0958 and is more than twice the margin by which the method beats the baseline at its best setting. The number of neighbors here is not a detail of the method but the thing that determines its result: with a badly chosen $K$, collaborative filtering is worse than a list that makes no distinction between subscribers.

The sixth column says how narrow the gain is. At the best setting 4.07 of the top-five list is already an item of the baseline list; the method gains 0.0419 by changing only one of five items. At forty neighbors the overlap drops to 3.49, the most personalized list, and the hit rate is lowest there. At one hundred sixty the overlap climbs back to 4.12, because with neighbors near half the subscribers the weighted sum converges to the average of the whole set, that is to popularity. The hyperparameter goes up to the baseline at both ends.

The fifth column counts the volatility directly: when the number of neighbors changes by one step, 4.89 of the top five stay in place in the best case and 4.08 in the worst — on average one item changes place at every step.

The place where the gain is actually seen is the fourth column. The baseline showed only 9 distinct items to all 167 subscribers. The user-based setup shows 16 items at its best setting and 20 at twenty neighbors. While gaining 0.0419 in hit rate the method nearly doubles the visible part of the catalog, and since an item that is not shown does not enter the next period’s data either, this second number is longer-lived than the first.

Item-Based: The Same Routine, the Other Edge of the Matrix

The same similarity routine is applied to the columns of the matrix: every item is represented by the set of subscribers who selected it, and two items resemble each other by the number of their common subscribers. A subscriber’s score is distributed to the $K$ most similar neighbors of their own items. This count uses the same raw material as the lift measured in the Unsupervised Learning course, the number of times two items are seen together, but there a rule was being extracted, here a ranking is being produced, and the rule extraction routine is not repeated.

ITEM_SEEN = {j: set(a for a in SUBSCRIBERS if j in SEEN[a]) for j in range(N_ITEMS)}
ITEM_SIM = similarities(ITEM_SEEN, list(range(N_ITEMS)))


def item_based(K):
    def score(a):
        s = [0.0] * N_ITEMS
        for i in SEEN[a]:
            for w, j in ITEM_SIM[i][:K]:
                s[j] += w
        return s
    return score


print(f"{'K':>4} {'hit rate@5':>10} {'mean rank':>9} {'items shown':>11} {'overlap':>8}")
for K in (2, 3, 5, 8, 12, 23):
    h, s, cov = measure(item_based(K))
    cur = {a: top_k(item_based(K), a, SEEN) for a in EVAL_SUBS}
    t = sum(len(cur[a] & BASE5[a]) for a in EVAL_SUBS) / len(EVAL_SUBS)
    print(f"{K:>4} {h:>10.4f} {s:>9.2f} {cov:>11} {t:>8.2f}")

   K hit rate@5 mean rank items shown  overlap
   2     0.6467      5.20          18     3.37
   3     0.6467      5.21          18     3.32
   5     0.5329      5.75          21     2.93
   8     0.5329      6.03          21     3.00
  12     0.5329      6.50          21     2.95
  23     0.5449      6.48          21     2.92

The best candidate of the item-based setup is 0.6467, that is below the baseline. None of the six candidates exceeds 0.6527. This is the reverse of the user-based result, and its cause can be counted: the held-out subscribers have on average 1.78 items in the training set. The item-based score is distributed over the neighborhoods of these one or two items, so the sum is almost the neighbor list of a single item, while the user-based sum adds up the whole history of three subscribers. In a sparse matrix the edge with more observations decides the order of the methods, and here that edge is the rows.

The place where the setup wins is again the fourth column: it shows 21 items and its overlap with the baseline list does not exceed 3.37 at any setting. The item-based ranking is more personalized and has wider coverage, and pays for that in hit rate. On the same data, two setups move in two separate directions on the same measure.

As Sparsity Grows, No Neighbor Is Left

Both setups rest on a single thing: the direct common observation of two subscribers or two items. A share of the training interactions is kept and the rest is thrown away, which pulls the sparsity up; the held-out items do not change, so the five rows are read on the same 167 subscribers. The number of neighbors is fixed at its best setting, that is at three.

PAIRS = sorted(TRAIN)
print(f"{'share':>5} {'train':>7} {'sparsity':>10} {'neighborless':>12} "
      f"{'hit rate@5':>10} {'neighbored':>10} {'neighborless':>12} {'baseline':>8}")
for frac in (1.00, 0.75, 0.55, 0.40, 0.25):
    r = rng(SEED + 9100)
    G = {a: set() for a in SUBSCRIBERS}
    for a, j in PAIRS:
        if r() < frac:
            G[a].add(j)
    B = similarities(G, SUBSCRIBERS)
    counts = [sum(1 for a in SUBSCRIBERS if j in G[a]) for j in range(N_ITEMS)]
    ub = user_based(B, G, 3)
    with_nbrs = [a for a in EVAL_SUBS if B[a]]
    without = [a for a in EVAL_SUBS if not B[a]]
    t = sum(len(v) for v in G.values())
    wh = "%.4f" % measure(ub, G, without)[0] if without else "--"
    print(f"{frac:>5.2f} {t:>7} {1 - t / (N_SUBSCRIBERS * N_ITEMS):>10.4f} {len(without):>12} "
          f"{measure(ub, G)[0]:>10.4f} {measure(ub, G, with_nbrs)[0]:>10.4f} {wh:>12} "
          f"{measure(lambda a: counts, G)[0]:>8.4f}")

share   train   sparsity neighborless hit rate@5 neighbored neighborless baseline
 1.00     410     0.9525            0     0.6946     0.6946           --   0.6527
 0.75     308     0.9644           20     0.6886     0.6803       0.7500   0.6467
 0.55     221     0.9744           52     0.6587     0.6783       0.6154   0.6347
 0.40     167     0.9807           75     0.6587     0.6739       0.6400   0.6407
 0.25      97     0.9888          105     0.6407     0.6613       0.6286   0.6347

As the sparsity goes from 0.9525 to 0.9888, the number of held-out subscribers left with no neighbor goes from zero to 105, more than half of the 167 subscribers. The score vector of these subscribers is zero from end to end: collaborative filtering produces nothing for them.

In spite of this, the fifth column goes down only from 0.6946 to 0.6407. The measure dropping this little does not show that the method is robust to sparsity; the seventh column gives the reason. The hit rate among the neighborless subscribers is 0.6286, only 0.0327 below the 0.6613 among those with neighbors. Yet the method did not work at all for those subscribers. The number comes from the tie resolution written in RS27: when all scores are zero the ranking falls to the catalog index, and the catalog is in decreasing order of base share. So the neighborless subscriber silently receives the same list as the baseline, and the measure prints the number of a baseline that looks like the number of the method.

This is another face of the rule of the course. If for how many subscribers it really works is not written when reading the number of a method, the measure is produced not by the method but by the measurement setup. When the columns are printed separately the loss becomes visible: at the 0.25 share the method works for 62 of the 167 subscribers and gives 0.6613 there, and for the remaining 105 the catalog order gives 0.6286. The baseline stays between 0.6527 and 0.6347 across the five rows.

Summary

• Collaborative filtering produces the recommendation not from the features of the item but from the subscribers who select the items together; a single similarity routine works on both edges of the matrix.
• The training matrix is 0.9525 sparse with 410 interactions; the baseline, the order of the most chosen item, gives 0.6527 hit rate@5 and shows only 9 of the 24 items.
• The user-based setup gives 0.6946 with three neighbors, 0.0419 above the baseline; but 4.07 of its top five already belongs to the baseline list, and the real gain is showing 16 items instead of 9.
• The number of neighbors is a hyperparameter: seven candidates move between 0.5988 and 0.6946, and this band of 0.0958 is more than twice the margin by which the method beats the baseline.
• The item-based setup stays at 0.6467 at its best setting and falls below the baseline, because the average number of training items per held-out subscriber is 1.78; in return it shows 21 items.
• When the sparsity is raised from 0.9525 to 0.9888 the neighborless subscribers go from 0 to 105; the measure staying at 0.6407 comes not from the method but from the catalog order that comes into play when the scores are zeroed.

Next Step

The neighborhood rests on a single thing: the direct common observation of two subscribers or two items. If there is none, the similarity never enters the list, and the last table showed the price of this. Yet two subscribers with no common item need not be truly dissimilar: if one has applied for an installment plan and the other for debt restructuring, both stand in the billing domain, but their similarity comes out zero. To capture this commonality the similarity has to be read through a representation that places every subscriber and every item on a few latent factors. The next lesson writes the matrix as the product of two such small matrices, and the decision to be measured is this: will the unobserved cells enter the computation as zero, or not at all. The two setups produce two separate rankings on the same data.