diversity_algorithms_comparison.py

1"""对应正文第 7 章 §7.5「多样性打散」三种算法(MMR / DPP / SSD)的统一对比。23本实现做了什么4----------------5在**同一个**合成候选集、同一目标序列长度上,把 §7.5.1 的 MMR、§7.5.2 的 DPP 快速贪心6(Cholesky 增量)、§7.5.3 的 SSD(one-step MGS)跑在一起,输出可直接横向比较的数值表:71. 每个算法在各自权衡系数(lambda / theta / gamma)上扫描,找出「相关性损失最接近 5%」8   的那一档,形成 **等相关性损失下的多样性对比**(避免拿不同强度的参数做不公平比较);92. 指标口径统一:10   - 相关性损失 = (纯精排 Top-K 的平均融合分 - 本算法的平均融合分) / 纯精排平均融合分11   - ILD      = 平均两两 (1 - cos) ,集合内多样性12   - 类目熵 H = -sum_c p_c log p_c13   - 类目覆盖 = 选中集合出现的类目数14   - 相邻同类 = 序列里相邻两位同类目的对数(正文 §7.6 关心的「连续出现」)15   - log det(S_Y) = DPP 的纯多样性项(行列式体积的对数)163. 耗时随候选规模 N 的增长曲线:复现正文的复杂度结论17   MMR O(K^2 N)、DPP 快速贪心 O(K^2 N)、SSD O(N T d)。1819关键公式(§7.5,三式并列)20--------------------------21    MMR: argmax_i [ lambda * r_i - (1-lambda) * max_{j in S} S_ij ]22    DPP: argmax_i log(d_i^2),  L' = Diag(e^{alpha r}) S Diag(e^{alpha r}),23         alpha = theta / (2(1-theta))24    SSD: argmax_j [ r_j + gamma * ||v_j|| * V ],  v_j <- v_j - (<v_j,v_p>/||v_p||^2) v_p25"""2627import math28import random29import time3031import numpy as np3233CATEGORIES = ["影视", "美食", "萌宠", "游戏", "音乐", "知识"]343536# ---------------------------------------------------------------------------37# [MOCK] 合成候选集:同类目物品围绕同一中心,高分物品集中在两个类目38# ---------------------------------------------------------------------------39def build_candidates(n_items, dim, rng):40    centers = {}41    for c in CATEGORIES:42        v = np.array([rng.gauss(0, 1) for _ in range(dim)])43        centers[c] = v / np.linalg.norm(v)44    cats, embs, rels = [], [], []45    for i in range(n_items):46        cat = CATEGORIES[i % len(CATEGORIES)]47        v = centers[cat] + 0.30 * np.array([rng.gauss(0, 1) for _ in range(dim)])48        embs.append(v / np.linalg.norm(v))49        cats.append(cat)50        bonus = 0.25 if cat in ("影视", "美食") else 0.051        rels.append(min(1.0, max(0.05, 0.5 + 0.3 * rng.gauss(0, 1) + bonus)))52    return cats, np.array(embs), np.array(rels)535455def cos_matrix(embs):56    f = embs / np.linalg.norm(embs, axis=1, keepdims=True)57    return f @ f.T585960# ---------------------------------------------------------------------------61# 三种算法62# ---------------------------------------------------------------------------63def mmr(rels, cos_sim, k, lam):64    n = len(rels)65    sel = [int(np.argmax(rels))]66    rest = [i for i in range(n) if i != sel[0]]67    while len(sel) < k and rest:68        best, best_s = None, -float("inf")69        for i in rest:70            max_sim = max(cos_sim[i][j] for j in sel)71            s = lam * rels[i] - (1.0 - lam) * max_sim72            if s > best_s:73                best, best_s = i, s74        sel.append(best)75        rest.remove(best)76    return sel777879def dpp(rels, embs, k, theta):80    n = embs.shape[0]81    S = (1.0 + cos_matrix(embs)) / 2.082    alpha = 0.0 if theta >= 1.0 else theta / (2.0 * (1.0 - theta))83    w = np.exp(alpha * rels)84    L = w[:, None] * S * w[None, :]85    c = [[] for _ in range(n)]86    d2 = L.diagonal().copy()87    sel = []88    while len(sel) < k:89        mask = np.ones(n, dtype=bool)90        mask[sel] = False91        valid = np.where(mask)[0]92        if valid.size == 0:93            break94        j = int(valid[int(np.argmax(np.maximum(d2[valid], 1e-300)))])95        sel.append(j)96        if len(sel) == k:97            break98        d_j = math.sqrt(max(d2[j], 1e-300))99        cj = np.array(c[j]) if c[j] else None100        for i in range(n):101            if i in sel:102                continue103            dot = float(cj @ np.array(c[i])) if cj is not None and c[i] else 0.0104            e_i = (L[j, i] - dot) / d_j105            c[i].append(e_i)106            d2[i] -= e_i ** 2107    return sel108109110def ssd(rels, embs, k, gamma):111    emb = np.array(embs, dtype=float, copy=True)112    n = emb.shape[0]113    i_t = int(np.argmax(rels))114    sel = [i_t]115    V = float(np.linalg.norm(emb[i_t]))116    for _ in range(1, k):117        pivot = emb[i_t].copy()118        denom = float(pivot @ pivot)119        if denom > 1e-300:120            for j in range(n):121                if j not in sel:122                    emb[j] = emb[j] - (float(emb[j] @ pivot) / denom) * pivot123        cand = [j for j in range(n) if j not in sel]124        if not cand:125            break126        scores = [rels[j] + float(np.linalg.norm(emb[j])) * gamma * V for j in cand]127        i_t = cand[int(np.argmax(scores))]128        sel.append(i_t)129        V = float(np.linalg.norm(emb[i_t])) * V130    return sel131132133# ---------------------------------------------------------------------------134# 统一指标135# ---------------------------------------------------------------------------136def logdet(sub):137    if sub.shape[0] == 0:138        return 0.0139    low = np.linalg.cholesky(sub + 1e-10 * np.eye(sub.shape[0]))140    return 2.0 * float(np.sum(np.log(np.diag(low))))141142143def metrics(cats, embs, rels, S, picked):144    m = len(picked)145    sims = cos_matrix(embs)[np.ix_(picked, picked)]146    ild = sum(1.0 - sims[x, y] for x in range(m) for y in range(x + 1, m))147    ild /= m * (m - 1) / 2148    sc = [cats[i] for i in picked]149    counts = {c: sc.count(c) for c in set(sc)}150    ent = -sum((v / m) * math.log(v / m) for v in counts.values())151    return {152        "rel": float(np.mean(rels[picked])),153        "ild": ild,154        "n_cat": len(counts),155        "entropy": ent,156        "adj_same": sum(1 for t in range(m - 1) if sc[t] == sc[t + 1]),157        "logdet_S": logdet(S[np.ix_(picked, picked)]),158    }159160161def main():162    random.seed(42)163    np.random.seed(42)164165    n_items, dim, k = 60, 16, 12166    cats, embs, rels = build_candidates(n_items, dim, random.Random(42))167    S = (1.0 + cos_matrix(embs)) / 2.0168    cs = cos_matrix(embs)169170    top_rel = list(np.argsort(-rels)[:k])171    base = metrics(cats, embs, rels, S, top_rel)172    print(f"== 统一候选集:N={n_items}, d={dim}, K={k},类目数={len(CATEGORIES)} ==")173    print("基线 = 纯精排 Top-K(不打散)")174    print(f"  avg_rel={base['rel']:.4f}  ILD={base['ild']:.4f}  "175          f"类目数={base['n_cat']}  类目熵={base['entropy']:.4f}  "176          f"相邻同类={base['adj_same']}  log det S_Y={base['logdet_S']:.4f}")177178    # ---------------- (1) 各算法完整参数扫描 ----------------179    sweeps = {180        "MMR": [("lambda", lam, lambda lam=lam: mmr(rels, cs, k, lam))181                for lam in (1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.3, 0.1, 0.0)],182        "DPP": [("theta", th, lambda th=th: dpp(rels, embs, k, th))183                for th in (0.99, 0.95, 0.9, 0.8, 0.7, 0.6, 0.4, 0.2, 0.0)],184        "SSD": [("gamma", g, lambda g=g: ssd(rels, embs, k, g))185                for g in (0.0, 1.0, 3.0, 5.0, 8.0, 10.0, 15.0, 20.0, 50.0)],186    }187188    records = {}189    for algo, entries in sweeps.items():190        print(f"\n== (1.{list(sweeps).index(algo) + 1}) {algo} 参数扫描 ==")191        print(f"{entries[0][0]:>8} {'avg_rel':>8} {'rel损失':>8} {'ILD':>7} "192              f"{'类目数':>6} {'类目熵':>7} {'相邻同类':>8} {'log det S_Y':>12} "193              f"{'耗时ms':>8}")194        rows = []195        for pname, pval, fn in entries:196            t0 = time.perf_counter()197            picked = fn()198            dt = (time.perf_counter() - t0) * 1000199            m = metrics(cats, embs, rels, S, picked)200            loss = (base["rel"] - m["rel"]) / base["rel"] * 100201            rows.append((pval, loss, m, dt, picked))202            print(f"{pval:>8.2f} {m['rel']:>8.4f} {loss:>7.2f}% {m['ild']:>7.4f} "203                  f"{m['n_cat']:>6d} {m['entropy']:>7.4f} {m['adj_same']:>8d} "204                  f"{m['logdet_S']:>12.4f} {dt:>8.2f}")205        records[algo] = rows206207    # ---------------- (2) 等相关性损失(≈5%)下的横向对比 ----------------208    print("\n== (2) 等相关性损失对比(每个算法取 rel 损失最接近 5% 的那一档)==")209    target = 5.0210    print(f"{'算法':>6} {'参数':>14} {'rel损失':>8} {'ILD':>7} {'类目数':>6} "211          f"{'类目熵':>7} {'相邻同类':>8} {'log det S_Y':>12} {'耗时ms':>8}")212    chosen = {}213    for algo, rows in records.items():214        pname = sweeps[algo][0][0]215        pval, loss, m, dt, picked = min(rows, key=lambda r: abs(r[1] - target))216        chosen[algo] = picked217        print(f"{algo:>6} {pname + '=' + format(pval, '.2f'):>14} {loss:>7.2f}% "218              f"{m['ild']:>7.4f} {m['n_cat']:>6d} {m['entropy']:>7.4f} "219              f"{m['adj_same']:>8d} {m['logdet_S']:>12.4f} {dt:>8.2f}")220221    print("\n该档位下三者选出的类目序列:")222    print(f"  {'精排基线':>8}: " + "->".join(cats[i] for i in top_rel))223    for algo, picked in chosen.items():224        print(f"  {algo:>8}: " + "->".join(cats[i] for i in picked))225226    print("\n选中集合的重叠情况(Jaccard):")227    names = list(chosen)228    print(f"{'':>8} " + " ".join(f"{n:>8}" for n in names + ["基线"]))229    for a in names:230        cells = []231        for b in names + ["基线"]:232            sb = set(top_rel) if b == "基线" else set(chosen[b])233            sa = set(chosen[a])234            cells.append(len(sa & sb) / len(sa | sb))235        print(f"{a:>8} " + " ".join(f"{c:>8.3f}" for c in cells))236237    # ---------------- (3) 耗时随 N 增长 ----------------238    print("\n== (3) 耗时随候选规模 N 增长(K=12,单位 ms)==")239    print(f"{'N':>7} {'MMR':>9} {'DPP':>9} {'SSD':>9}  复杂度: MMR/DPP O(K^2 N), SSD O(NTd)")240    for n_probe in (60, 120, 240, 480, 960):241        c_p, e_p, r_p = build_candidates(n_probe, dim, random.Random(7))242        cs_p = cos_matrix(e_p)243        t0 = time.perf_counter(); mmr(r_p, cs_p, k, 0.8); t_m = (time.perf_counter() - t0) * 1000244        t0 = time.perf_counter(); dpp(r_p, e_p, k, 0.9); t_d = (time.perf_counter() - t0) * 1000245        t0 = time.perf_counter(); ssd(r_p, e_p, k, 5.0); t_s = (time.perf_counter() - t0) * 1000246        print(f"{n_probe:>7} {t_m:>9.2f} {t_d:>9.2f} {t_s:>9.2f}")247248    print("\n== (4) 三者定位小结(对应正文 §7.5)==")249    print("  MMR:只看「与已选集合的最大相似度」,实现最简单,但对集合整体结构不敏感;")250    print("  DPP:用 det(L_Y)=Vol^2 度量集合整体多样性,理论最完备,")251    print("       Cholesky 增量把贪心推断降到 O(K^2 N);")252    print("  SSD:用 one-step MGS 的残差模长近似「新增体积」,单步 O(d),")253    print("       整体 O(NTd),最适合长序列信息流场景。")254255256if __name__ == "__main__":257    main()