"""Why PISCES works: revival timeline, cluster-size balance, and an empirical check of Lemma 2. For one seed on DEEP* 1M (k = 16,384, 3 epochs), train official e-means and PISCES from the same starting rows and record: * every revival (training step, number of clusters re-seeded), * the final cluster sizes on the 1M training rows and per-cluster distortion, * Lemma 2 on real clusters: for 400 random clusters with >= 20 rows, the distortion removed by the best split along the top principal axis (2-means restricted to the axis, 10 Lloyd iterations started at c +/- sqrt(2 lambda_1 / pi) u_1) against the prediction (2/pi) N lambda_1, and against an unrestricted 2-means of the cluster (faiss, 5 restarts). Writes one JSON file used by paper/make_data.py. Usage: python benchmarks/mechanism_analysis.py DATA/deep1b OUT.json [--seed 10] """ import argparse, json, math, os, sys, time import numpy as np import faiss ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__))) sys.path.insert(0, ROOT) from faiss.contrib.e_means import NumpyEmeans # noqa: E402 from aries.pemeans import PEmeans, PISCES # noqa: E402 K = 16384 def recorder(cls): class Rec(cls): def _apply_splits(self, source, target): n = super()._apply_splits(source, target) self.split_log.append((int(self._step), int(len(source)))) return n return Rec def sizes_and_distortion(x, c): D, I = faiss.knn(x, c, 1) cnt = np.bincount(I[:, 0], minlength=len(c)) dist = np.bincount(I[:, 0], weights=D[:, 0].astype("float64"), minlength=len(c)) return cnt, dist, I[:, 0] def lemma_check(x, c, lab, rng, m=400): out = [] cnt = np.bincount(lab, minlength=len(c)) pool = np.flatnonzero(cnt >= 20) for j in rng.choice(pool, min(m, len(pool)), replace=False): X = x[lab == j].astype("float64") N = len(X); mu = X.mean(0); E = X - mu before = float((E ** 2).sum()) w, V = np.linalg.eigh(E.T @ E / N) lam, u = float(w[-1]), V[:, -1] pred = 2 / math.pi * N * lam # split restricted to the axis: Lloyd on the projections, started at the Lemma 1 positions p = E @ u; a, b = math.sqrt(2 * lam / math.pi), -math.sqrt(2 * lam / math.pi) for _ in range(10): s = p > (a + b) / 2 if s.all() or (~s).all(): break a, b = p[s].mean(), p[~s].mean() s = p > (a + b) / 2 A, B = X[s], X[~s] axis_after = float(((A - A.mean(0)) ** 2).sum() + ((B - B.mean(0)) ** 2).sum()) if len(A) and len(B) else before km = faiss.Kmeans(X.shape[1], 2, niter=20, nredo=5, seed=int(j), max_points_per_centroid=10**9) km.train(X.astype("float32")) Dd, _ = km.index.search(X.astype("float32"), 1) free_after = float(Dd.sum()) out.append(dict(N=N, lam1=lam, trace=float(np.trace(E.T @ E / N)), predicted=pred, axis_split=before - axis_after, free_2means=before - free_after)) return out def swap_audit(x, c, lab, D1): """How many global split-merge moves would still pay off? A move deletes cluster t (its rows go to their runner-up centroid, cost = sum of d2 - d1) and splits cluster j along its top axis (gain (2/pi) N_j lambda_1,j, Lemma 2). Greedy pairing of the richest donors with the cheapest clusters, never deleting a cluster that absorbs the rows of another deleted one.""" D2, I2 = faiss.knn(x, c, 2) l2 = I2[:, 1] cost = np.bincount(lab, weights=(D2[:, 1] - D2[:, 0]).astype("float64"), minlength=len(c)) e = x - c[lab] u = np.random.RandomState(0).standard_normal(c.shape).astype("float32") order = np.argsort(lab, kind="stable"); uniq, start = np.unique(lab[order], return_index=True) for _ in range(5): u /= np.maximum(np.linalg.norm(u, axis=1, keepdims=True), 1e-12) p = np.einsum("ij,ij->i", e, u[lab]) V = np.zeros_like(c); V[uniq] = np.add.reduceat((e * p[:, None])[order], start, axis=0); u = V u /= np.maximum(np.linalg.norm(u, axis=1, keepdims=True), 1e-12) p = np.einsum("ij,ij->i", e, u[lab]) gain = 2 / math.pi * np.bincount(lab, weights=p.astype("float64") ** 2, minlength=len(c)) rich, cheap = np.argsort(-gain), np.argsort(cost) blocked = np.zeros(len(c), bool); moves, total, ci = 0, 0.0, 0 for j in rich: if blocked[j]: continue while ci < len(cheap) and (blocked[cheap[ci]] or cheap[ci] == j): ci += 1 if ci >= len(cheap) or gain[j] <= cost[cheap[ci]]: break t = cheap[ci]; ci += 1; moves += 1; total += gain[j] - cost[t] blocked[j] = blocked[t] = True; blocked[np.unique(l2[lab == t])] = True return dict(profitable_moves=moves, predicted_gain_per_row=total / len(x), gain_quantiles=np.quantile(gain, [0.5, 0.9, 0.99, 1.0]).tolist(), cost_quantiles=np.quantile(cost, [0.0, 0.01, 0.1, 0.5]).tolist()) def split_examples(x, c, lab, rng, m=3, cap=1500): """Real clusters for the split-geometry figure: rows projected onto the top two principal axes, with the Lemma 1 children, the e-means children (on the centroid) and an exact 2-means.""" cnt = np.bincount(lab, minlength=len(c)) out = [] for j in np.argsort(-cnt)[:m]: X = x[lab == j].astype("float64"); mu = X.mean(0); E = X - mu w, V = np.linalg.eigh(E.T @ E / len(X)); u1, u2 = V[:, -1], V[:, -2] P = np.stack([E @ u1, E @ u2], 1) km = faiss.Kmeans(X.shape[1], 2, niter=25, nredo=5, seed=int(j), max_points_per_centroid=10**9) km.train(X.astype("float32")) K2 = (km.centroids.astype("float64") - mu) @ np.stack([u1, u2], 1) sub = rng.choice(len(X), min(cap, len(X)), replace=False) out.append(dict(N=int(len(X)), lam1=float(w[-1]), lam2=float(w[-2]), points=P[sub].round(4).tolist(), pisces=[[math.sqrt(2 * w[-1] / math.pi), 0.0], [-math.sqrt(2 * w[-1] / math.pi), 0.0]], kmeans2=K2.round(4).tolist())) return out def main(): ap = argparse.ArgumentParser() ap.add_argument("data"); ap.add_argument("out") ap.add_argument("--seed", type=int, default=10); ap.add_argument("--epochs", type=float, default=3) ap.add_argument("--threads", type=int, default=4) a = ap.parse_args() faiss.omp_set_num_threads(a.threads) sys.path.insert(0, os.path.join(ROOT, "benchmarks")) from paper_protocol import make_variant # noqa: E402 x = np.ascontiguousarray(np.load(os.path.join(a.data, "train_1M.npy"))) init = x[np.random.RandomState(a.seed).permutation(len(x))[:K]].copy() res = {"seed": a.seed, "epochs": a.epochs, "k": K} for name in ["official", "pisces"]: if name == "official": km = recorder(NumpyEmeans)(x.shape[1], K, nepochs=a.epochs, seed=a.seed, batch_law="throughput") else: build = make_variant(PISCES, len(x)) km = build(x.shape[1], a.epochs, a.seed) # PEmeans with the PISCES configuration km.__class__ = recorder(PEmeans) km.split_log = [] t0 = time.time(); c, _ = km.train(x, init_centroids=init.copy()); sec = time.time() - t0 cnt, dist, lab = sizes_and_distortion(x, c) res[name] = dict(seconds=sec, total_steps=int(getattr(km, "recipe", None)["total_steps"]) if getattr(km, "recipe", None) else None, split_log=km.split_log, sizes=cnt.tolist(), distortion=dist.tolist(), train_mse=float(dist.sum() / len(x)), lemma=lemma_check(x, c, lab, np.random.RandomState(a.seed)), swaps=swap_audit(x, c, lab, None), split_examples=split_examples(x, c, lab, np.random.RandomState(a.seed))) print(name, f"{sec:.0f}s", "splits", sum(n for _, n in km.split_log), "train mse", round(res[name]["train_mse"], 5), "empty", int((cnt == 0).sum()), "profitable swaps", res[name]["swaps"]["profitable_moves"], flush=True) json.dump(res, open(a.out, "w")) if __name__ == "__main__": main()