5D Library › Order-Bump Friction Elasticity, One-Click Upsell Kinetics and Cross-Domain Recommendation Matrices · 中文

Chapter 3. Cross-Fleet Routing by Conditional Mutual Information

A synthetic needs model

The author’s sites fall into four “fleets”: A readings, B health, C sound and mind, D business tools, 30 sites in all (S01 to S30 in the programs). A need a reader reveals on one site is often related to what another site offers. The program uses a synthetic model to show how such relations become recommendation routes: six latent needs (love, money, sleep, stress, health, career), with a shared “strain” factor making money, sleep and stress problems tend to occur together; each site serves one or two needs, for instance S01 love, S03 money, S13 sleep, S15 stress, S23 and S26 business. All parameters are assumptions, not user data.

The mutual information I(Xi;Xj)I(X_i; X_j) between the visit indicators of two sites measures how much knowing that a reader visited ii reduces uncertainty about whether they visit jj (Cover and Thomas 2006). Each site’s routes are the two sites in other fleets with the highest mutual information.

Calculation

# Chapter 3. p05: Cross-sell routing by mutual information - on a
# SYNTHETIC model. 30 sites in four fleets: A divination (S01-S08),
# B health (S09-S16), C sound and mind (S17-S22), D business tools
# (S23-S30). Six latent needs; a shared "strain" factor makes needs
# co-occur (money trouble with poor sleep, and so on). A user visits a
# site with a probability set by the needs the site serves. From
# simulated users we estimate I(X_i; X_j) for every pair of visit
# indicators and route each site to its top two sites in OTHER fleets.
import random
from math import log2

NEEDS = ("love", "money", "sleep", "stress", "health", "career")
FLEET = ["A"] * 8 + ["B"] * 8 + ["C"] * 6 + ["D"] * 8
SERVES = {}
for i in range(30):
    SERVES[i] = {NEEDS[i % 6]: 0.35, NEEDS[(i + 2) % 6]: 0.10}
SERVES[0] = {"love": 0.40, "stress": 0.10}         # S01 relationships
SERVES[2] = {"money": 0.40, "stress": 0.10}        # S03 money trouble
SERVES[12] = {"sleep": 0.45}                        # S13 sleep sound
SERVES[14] = {"stress": 0.40, "sleep": 0.10}       # S15 vagal reset
SERVES[22] = {"money": 0.35, "career": 0.15}       # S23 business game
SERVES[25] = {"career": 0.35, "money": 0.15}       # S26 deal tools

def user(rng):
    strain = rng.random() < 0.3
    base = {"love": 0.2, "money": 0.2, "sleep": 0.15, "stress": 0.2,
            "health": 0.2, "career": 0.2}
    boost = {"money": 0.3, "sleep": 0.35, "stress": 0.4, "love": 0.15}
    return {n: rng.random() < base[n] + (boost.get(n, 0) if strain else 0)
            for n in NEEDS}

def visits(needs, rng):
    out = []
    for i in range(30):
        miss = 1.0
        for n, w in SERVES[i].items():
            if needs[n]:
                miss *= 1 - w
        out.append(rng.random() < 1 - miss * 0.98)
    return out

def mi(a, b, both, n):
    tot = 0.0
    for x in (0, 1):
        for y in (0, 1):
            nxy = both if x and y else (a - both if x else (
                b - both if y else n - a - b + both))
            px, py = (a if x else n - a) / n, (b if y else n - b) / n
            if nxy:
                tot += nxy / n * log2(nxy / n / (px * py))
    return tot

def estimate(n, seed):
    rng = random.Random(seed)
    cnt, pair = [0] * 30, [[0] * 30 for _ in range(30)]
    for _ in range(n):
        v = visits(user(rng), rng)
        on = [i for i in range(30) if v[i]]
        for i in on:
            cnt[i] += 1
            for j in on:
                pair[i][j] += 1
    return cnt, pair

def routes(cnt, pair, n):
    out = {}
    for i in range(30):
        cand = [(mi(cnt[i], cnt[j], pair[i][j], n), j) for j in range(30)
                if FLEET[j] != FLEET[i]]
        out[i] = [j for _, j in sorted(cand, reverse=True)[:2]]
    return out

if __name__ == "__main__":
    N = 60000
    cnt, pair = estimate(N, 78005)
    r = routes(cnt, pair, N)
    for i in (0, 2, 12, 14, 22, 25):
        a, b = r[i]
        ma = mi(cnt[i], cnt[a], pair[i][a], N)
        mb = mi(cnt[i], cnt[b], pair[i][b], N)
        fmt = ("   S{:02d} ({}) -> S{:02d} ({}) {:.4f} bits,"
               " S{:02d} ({}) {:.4f}")
        print(fmt.format(i + 1, FLEET[i], a + 1, FLEET[a], ma, b + 1,
                         FLEET[b], mb))
#    S01 (A) -> S19 (C) 0.0254 bits, S25 (D) 0.0250
#    S03 (A) -> S14 (B) 0.0304 bits, S20 (C) 0.0285
#    S13 (B) -> S27 (D) 0.0353 bits, S21 (C) 0.0337
#    S15 (B) -> S04 (A) 0.0295 bits, S22 (C) 0.0283
#    S23 (D) -> S03 (A) 0.0252 bits, S02 (A) 0.0216
#    S26 (D) -> S06 (A) 0.0214 bits, S18 (C) 0.0207

On 60,000 synthetic users, S01 routes to S19 (fleet C, also serving love) and S25; S03 to S14 and S20; S13 to S27 and S21; S15 to S04 and S22; S23 to S03 and S02. All mutual informations are a few hundredths of a bit (S13 to S27 is 0.0353 bits, for example): visits to the two sites are related, but far from strong predictors of each other.

How many users are needed

Calculation

# Chapter 3. p06: How many users before the top-two routes are stable?
# Same synthetic model as p05. "Truth" = routes estimated from 400,000
# simulated users. For smaller samples (independent seeds) we count the
# share of the 30 sites whose estimated top-two set equals the true one,
# and the mean upward bias of the plug-in mutual information of an
# independent pair (the Miller-Madow bias, about 1/(2 n ln 2) bits).
import importlib.util
from math import log

def load(name):
    spec = importlib.util.spec_from_file_location(name, name + ".py")
    m = importlib.util.module_from_spec(spec)
    spec.loader.exec_module(m)
    return m

m = load("p05_cross_sell_mi")

if __name__ == "__main__":
    cnt, pair = m.estimate(400000, 1)
    truth = m.routes(cnt, pair, 400000)
    print("   users     sites with the true top-two set   (of 30)")
    for n in (2000, 10000, 60000):
        hits = []
        for seed in (11, 12, 13):
            c, p = m.estimate(n, seed)
            r = m.routes(c, p, n)
            hits.append(sum(set(r[i]) == set(truth[i]) for i in range(30)))
        print("   {:6,}    {}".format(n, ", ".join(str(h) for h in hits)))
    for n in (2000, 10000, 60000):
        print("   bias, independent pair, n = {:6,}: {:.6f} bits".format(
            n, 1 / (2 * n * log(2))))
#    users     sites with the true top-two set   (of 30)
#     2,000    10, 14, 10
#    10,000    14, 12, 10
#    60,000    16, 17, 14
#    bias, independent pair, n =  2,000: 0.000361 bits
#    bias, independent pair, n = 10,000: 0.000072 bits
#    bias, independent pair, n = 60,000: 0.000012 bits

Taking the routes estimated from 400,000 synthetic users as “truth” and re-estimating on smaller samples: with 2,000 users only 10 to 14 of the 30 sites have the true top two; with 60,000 users still only 14 to 17. The reason is not estimation bias (for an independent pair the bias is only 0.000361 bits at 2,000 users) but that candidate sites differ so little in mutual information that their order flips back and forth within sampling error.

Note

In practice. When candidates differ very little, the “top two” are no more deserving of recommendation than the third or fourth. It is sturdier to treat sites with close mutual information as a group shown in rotation, and to measure the true increment with the holdout experiment of Chapter 8, rather than fixing one route.

Summary

Conditional mutual information can turn the correlation of needs across sites into recommendation routes; but in the synthetic model all mutual informations are small, and on 60,000 users the top two are still unstable for half the sites. Routes should rotate within groups and be tested with a holdout.

References

Cover, Thomas M., and Joy A. Thomas. 2006. Elements of Information Theory. 2nd ed. Wiley-Interscience.

Fan, Y. (2026). Order-Bump Friction Elasticity, One-Click Upsell Kinetics and Cross-Domain Recommendation Matrices: Zero-Reentry Impulse Attachment, Conditional Mutual Information and Cart-Value Multipliers [结账顺手加购弹性、一键升单动力学与跨领域推荐矩阵] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090207 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).