PISCES / aries /pisces.py
Nabidnur's picture
PISCES (ARIES #1): code, paper, notebooks, results and figures
c09a3f4 verified
Raw History Blame Contribute Delete
2.76 kB
"""PISCES — Principal-axis Informed Splitting with Consistent closing, Early revival and
Sparse assignment. First algorithm of the ARIES series.
Two fish swimming in opposite directions: every split places two children at
c ± sqrt(2/pi)·sigma_1·u_1, symmetric along the cluster's principal axis.
`pisces()` is the public entry point. It wraps `PEmeans` (a subclass of faiss's official
`NumpyEmeans`) with the frozen configuration, applies the re-fitted step law, and optionally grows
the codebook coarse-to-fine: start with k / 2^g centroids and double them g times by splitting
every cluster along its principal axis, then train at k.
"""
import math
import numpy as np
from aries.pemeans import PEmeans, PISCES as PISCES_CONFIG
_HALF_GAUSS = math.sqrt(2.0 / math.pi)
def _recipe(n, k, T, alpha_scale):
from faiss.contrib.e_means.base import _resolve_recipe, _step_law
B, _ = _resolve_recipe(n, k, max(T, 1e-3), "throughput", None, None)
return dict(batch_size=B, alpha0=min(1.0, _step_law(n, k, max(T, 1e-3), B) * alpha_scale))
def _train(x, k, T, seed, init, cfg):
cfg = dict(cfg)
a = cfg.pop("alpha_scale", 1.0)
km = PEmeans(x.shape[1], k, nepochs=T, seed=seed, batch_law="throughput", **_recipe(len(x), k, T, a), **cfg)
c, _ = km.train(x, init_centroids=np.ascontiguousarray(init, dtype="float32"))
return c, km
def split_all(c, axis, lam):
"""Double the codebook: every centroid becomes two children at c ± sqrt(2/pi)·sqrt(lambda)·u."""
delta = (_HALF_GAUSS * np.sqrt(np.maximum(lam, 0.0)))[:, None] * axis
return np.concatenate([c + delta, c - delta]).astype("float32")
def pisces(x, k, nepochs=3, seed=0, init=None, grow=0, grow_epochs=0.5, config=None):
"""Train PISCES on the rows of x (n, d) and return (centroids (k, d), model, info).
init: optional (k, d) starting centroids (default: k random rows, as faiss e-means does).
grow: number of coarse-to-fine doublings before reaching k (0 = none; iteration 13 found it worse)."""
cfg = dict(PISCES_CONFIG if config is None else config)
x = np.ascontiguousarray(x, dtype="float32")
rng = np.random.RandomState(seed)
info = {"stages": []}
if grow <= 0:
if init is None:
init = x[rng.permutation(len(x))[:k]]
c, km = _train(x, k, nepochs, seed, init, cfg)
return c, km, info
k_s = k >> grow
c = x[rng.permutation(len(x))[:k_s]]
per = grow_epochs / grow
for g in range(grow):
c, km = _train(x, k_s, per, seed + 101 * (g + 1), c, cfg)
c = split_all(c, km.final_axis, km.final_lam)
info["stages"].append(dict(k=k_s, epochs=per))
k_s *= 2
c, km = _train(x, k, nepochs - grow_epochs, seed, c, cfg)
return c, km, info