Download benchmarks/mechanism_analysis.py from Nabidnur/PISCES: direct link, hf CLI and curl.
- Browser
- Download file 8.18 kB
-
https://huggingface.co/Nabidnur/PISCES/resolve/main/benchmarks/mechanism_analysis.py
- Command line
-
hf download hf://Nabidnur/PISCES/benchmarks/mechanism_analysis.py
-
curl -L -o mechanism_analysis.py https://huggingface.co/Nabidnur/PISCES/resolve/main/benchmarks/mechanism_analysis.py
8.18 kB
| """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() | |