PISCES / benchmarks /mechanism_analysis.py
Nabidnur's picture
PISCES (ARIES #1): code, paper, notebooks, results and figures
c09a3f4 verified
Raw History Blame Contribute Delete
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()