Diversity, rules, and DPP
Goal
Turn concepts into inspectable inputs, operations, gradients, and comparisons.
Evidence: real vectors + numerical checks. Local teaching parameters are not production defaults; mechanism experiments are not full reproductions of the original papers.
English companion. All instructional Markdown is translated. Experiment code, Chinese language examples, execution counts, and saved outputs remain as in the source edition; historical output text may therefore be Chinese. The initial setup cell anchors the working directory and Python import path for this companion's deeper folder; it does not change the experiment. Saved outputs are historical evidence, not a new run. Run from the top after preparing the required data and models.
# English companions live one directory deeper; keep the original experiment code unchanged.
from pathlib import Path as _TranslationPath
import os as _translation_os
import sys as _translation_sys
_translation_root = next((p for p in [_TranslationPath.cwd(), *_TranslationPath.cwd().parents]
if (p / "reclab").is_dir()), None)
if _translation_root is None:
raise RuntimeError("Open this notebook from inside the Search Recommendation Ads Lab checkout.")
_translation_os.chdir(_translation_root)
if str(_translation_root) not in _translation_sys.path:
_translation_sys.path.insert(0, str(_translation_root))
Setup
On the first pass, run from Setup in order: later cells reuse earlier variables. Then change one parameter and rerun that cell and its downstream cells. Constructed data does not establish real business impact.
from pathlib import Path
import sys
import inspect
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from IPython.display import display, Code
PROJECT = next(p for p in [Path.cwd(), *Path.cwd().parents]
if (p / "reclab/models.py").exists())
if str(PROJECT) not in sys.path:
sys.path.insert(0, str(PROJECT))
from reclab.data import Dataset
from reclab.paths import ARTIFACTS, PROCESSED, read_json
plt.rcParams.update({"figure.figsize": (9, 3.8), "font.size": 11,
"axes.spines.top": False, "axes.spines.right": False,
"axes.labelcolor": "#182b2b", "text.color": "#182b2b",
"axes.facecolor": "white", "figure.facecolor": "white",
"grid.color": "#d4ddda", "axes.axisbelow": True})
dataset = Dataset()
print("Project:", PROJECT)
print("Dataset version:", dataset.manifest["dataset_version"])
print("Python:", sys.executable)
assert Path(sys.executable).parent == PROJECT / ".venv/bin", "请选择 Recommendation Lab 内核"Saved notebook output · not executed on this page
Project: /Users/lizuolin/local/recommendation-lab Dataset version: 2772cab0aca8cb81 Python: /Users/lizuolin/local/recommendation-lab/.venv/bin/python
Steps
Lecture references: 06_Rerank_01.pdf, 06_Rerank_02.pdf, 06_Rerank_03.pdf, 06_Rerank_04.pdf, 06_Rerank_05.pdf
ILD, category entropy, and MMR on real vectors
ILD measures distances between collaborative vectors, not independently learned image/text semantics. A changed list is not user feedback.
Predict first: Does a shared category necessarily imply similar vectors?
from reclab.learning.systems import ild,category_entropy,constrained_ranking,greedy_dpp,slow_greedy_dpp,exhaustive_dpp
from reclab.retrieval import mmr
vectors=np.load(ARTIFACTS/"runs/baseline-history32/item_vectors.npy")
scores=vectors@vectors[100];pool=np.argsort(-scores[1:])[:80]+1
rows=[]
for lam in [1.,.8,.5]:
selected,_=mmr(pool.tolist(),scores,vectors,k=10,relevance=lam)
rows.append({"lambda":lam,"mean_similarity":float(scores[selected].mean()),
"ILD":ild(vectors,selected),"category_entropy_bits":category_entropy([dataset.items[i-1]["category"] for i in selected])})
display(pd.DataFrame(rows))Saved notebook output · not executed on this page
| lambda | mean_similarity | ILD | category_entropy_bits | |
|---|---|---|---|---|
| 0 | 1.0 | 0.819358 | 0.191529 | 0.921928 |
| 1 | 0.8 | 0.819279 | 0.198008 | 0.921928 |
| 2 | 0.5 | 0.808305 | 0.277409 | 1.770951 |
Rules and infeasible constraints
If no feasible candidates remain, this implementation explicitly returns a partial list instead of inventing a full list that supposedly satisfies the rules.
Predict first: If every candidate belongs to one category, should the algorithm relax the rule or return fewer items?
categories={i:dataset.items[i-1]["category"] for i in pool}
selected=constrained_ranking(pool.tolist(),categories,k=10,max_consecutive=2)
display(pd.DataFrame({"item":selected,"category":[categories[i] for i in selected]}))
for pos in range(2,len(selected)):
assert not (categories[selected[pos]]==categories[selected[pos-1]]==categories[selected[pos-2]])Saved notebook output · not executed on this page
| item | category | |
|---|---|---|
| 0 | 100 | 819 |
| 1 | 4153 | 819 |
| 2 | 1172 | 405 |
| 3 | 4126 | 532 |
| 4 | 3095 | 819 |
| 5 | 4311 | 819 |
| 6 | 1537 | 1445 |
| 7 | 3424 | 819 |
| 8 | 398 | 819 |
| 9 | 4520 | 1593 |
DPP: volume, slow greedy selection, fast Cholesky updates, and enumeration
Controlled random vectors make numerical checking straightforward. Greedy MAP does not guarantee a global optimum.
Predict first: What happens to the Gram determinant when two candidate vectors are identical?
rng=np.random.default_rng(42)
v=rng.normal(size=(8,8));v/=np.linalg.norm(v,axis=1,keepdims=True)
quality=np.exp(np.linspace(0,1,8));features=v*quality[:,None];kernel=features@features.T
assert np.linalg.eigvalsh(kernel).min()>-1e-8
orthogonal=np.eye(2);duplicate=np.array([[1.,0.],[1.,0.]])
print("Orthogonal/duplicate volume squared:",np.linalg.det(orthogonal@orthogonal.T),np.linalg.det(duplicate@duplicate.T))
display(Code(inspect.getsource(greedy_dpp),language="python"))
fast=greedy_dpp(kernel,3);slow=slow_greedy_dpp(kernel,3)
best_logdet,best_ids=exhaustive_dpp(kernel,3)
assert fast==slow
greedy_logdet=np.linalg.slogdet(kernel[np.ix_(fast,fast)])[1]
assert greedy_logdet<=best_logdet+1e-8
display(pd.DataFrame([{"method":"greedy","items":fast,"logdet":greedy_logdet},{"method":"global exhaustive","items":best_ids,"logdet":best_logdet}]))Saved notebook output · not executed on this page
Orthogonal/duplicate volume squared: 1.0 0.0
def greedy_dpp(kernel, k):
"""Incremental Cholesky greedy MAP. It is an approximation to global MAP."""
n = len(kernel)
k = min(k, n)
residual = kernel.diagonal().copy()
coefficients = np.zeros((k, n))
selected = []
for step in range(k):
item = int(np.argmax(residual))
if residual[item] <= 1e-12:
break
correction = coefficients[:step, item] @ coefficients[:step, :]
update = (kernel[item, :] - correction) / math.sqrt(residual[item])
coefficients[step, :] = update
residual = np.maximum(residual - update**2, 0)
selected.append(item)
residual[selected] = -np.inf
return selected| method | items | logdet | |
|---|---|---|---|
| 0 | greedy | [7, 6, 5] | 4.680314 |
| 1 | global exhaustive | (5, 6, 7) | 4.680314 |
Checks
Every assertion and output is traceable to code. They check operators, data snapshots, or mechanisms, not online gains.
Next steps
Record your prediction, change only one variable, and run the relevant experiment cell. Open reclab/learning/ to inspect helper functions.