PISCES / aries /_kernels.py
Nabidnur's picture
PISCES (ARIES #1): code, paper, notebooks, results and figures
c09a3f4 verified
Raw History Blame Contribute Delete
7.01 kB
"""Optional compiled kernels (Numba). Falls back to NumPy when Numba is unavailable."""
import numpy as np
try:
from numba import njit, prange
@njit(parallel=True, fastmath=True, cache=True)
def _cand_assign_nb(X, C, cn, G, prev, out_l, out_d):
n, d = X.shape
m = G.shape[1]
for i in prange(n):
p = prev[i]
best = np.inf
bl = -1
xx = 0.0
for t in range(d):
xx += X[i, t] * X[i, t]
for jj in range(m):
c = G[p, jj]
s = cn[c]
for t in range(d):
s -= 2.0 * X[i, t] * C[c, t]
if s < best:
best = s
bl = c
out_l[i] = bl
out_d[i] = max(best + xx, 0.0)
@njit(parallel=True, fastmath=False, cache=True)
def _fused_stats_nb(X, order, starts, labs, C, U, sums, counts, b_axis, b_proj):
"""Per-cluster sums, counts, sum (e.u) e and sum (e.u)^2 over rows sorted by label."""
nseg = len(starts) - 1
d = X.shape[1]
for g in prange(nseg):
j = labs[g]
acc = np.zeros(d, np.float64); ax = np.zeros(d, np.float64); e = np.empty(d, np.float64)
pp = 0.0
for t in range(starts[g], starts[g + 1]):
i = order[t]
p = 0.0
for q in range(d):
v = X[i, q]
acc[q] += v
e[q] = v - C[j, q]
p += e[q] * U[j, q]
for q in range(d):
ax[q] += p * e[q]
pp += p * p
for q in range(d):
sums[j, q] += acc[q]
b_axis[j, q] += ax[q]
counts[j] += starts[g + 1] - starts[g]
b_proj[j] += pp
HAVE_NUMBA = True
except Exception: # pragma: no cover
HAVE_NUMBA = False
def cand_assign(X, C, G, prev):
"""Nearest centroid among G[prev[i]] for every row i. Returns (dist, label)."""
X = np.ascontiguousarray(X, dtype=np.float32)
C = np.ascontiguousarray(C, dtype=np.float32)
cn = (C.astype(np.float64) ** 2).sum(1).astype(np.float32)
L = np.empty(len(X), np.int64); D = np.empty(len(X), np.float32)
if HAVE_NUMBA:
_cand_assign_nb(X, C, cn, np.ascontiguousarray(G, dtype=np.int64), prev.astype(np.int64), L, D)
return D, L
for s0 in range(0, len(X), 4096):
r = slice(s0, s0 + 4096); cand = G[prev[r]]; xr = X[r]
dist = (xr * xr).sum(1)[:, None] - 2 * np.einsum("bd,bmd->bm", xr, C[cand]) + cn[cand]
j = dist.argmin(1); L[r] = cand[np.arange(len(j)), j]; D[r] = np.maximum(dist[np.arange(len(j)), j], 0)
return D, L
def cell_batched_assign(X, C, coarse, nprobe, cell_of=None):
"""Approximate nearest-centroid search with exactly the IVF candidate sets
(each row compares with the centroids of its `nprobe` nearest coarse cells), computed as one
dense BLAS matrix product per cell instead of per-row scans.
X: (n, d) rows; C: (k, d) centroids; coarse: (L, d) coarse cell centres;
cell_of: optional (k,) coarse cell of every centroid. Returns (squared dist, label)."""
import faiss
X = np.ascontiguousarray(X, dtype=np.float32); C = np.ascontiguousarray(C, dtype=np.float32)
coarse = np.ascontiguousarray(coarse, dtype=np.float32)
L = len(coarse)
if cell_of is None:
cell_of = faiss.knn(C, coarse, 1)[1][:, 0]
_, qcell = faiss.knn(X, coarse, nprobe) # (n, nprobe) probed cells
cn = (C * C).sum(1)
xn = (X * X).sum(1)
best = np.full(len(X), np.inf, np.float32); lab = np.full(len(X), -1, np.int64)
flat = qcell.ravel(); rows = np.repeat(np.arange(len(X)), nprobe)
order = np.argsort(flat, kind="stable"); flat, rows = flat[order], rows[order]
qstart = np.searchsorted(flat, np.arange(L + 1))
corder = np.argsort(cell_of, kind="stable"); cstart = np.searchsorted(cell_of[corder], np.arange(L + 1))
for j in range(L):
q = rows[qstart[j]:qstart[j + 1]]; cj = corder[cstart[j]:cstart[j + 1]]
if len(q) == 0 or len(cj) == 0:
continue
d = cn[cj][None, :] - 2.0 * (X[q] @ C[cj].T) # (|q|, |cj|) via BLAS
a = d.argmin(1); v = d[np.arange(len(q)), a]
better = v < best[q]
best[q[better]] = v[better]; lab[q[better]] = cj[a[better]]
miss = lab < 0
if miss.any(): # rows whose cells were empty
d0, l0 = faiss.knn(X[miss], C, 1); best[miss] = d0[:, 0] - xn[miss]; lab[miss] = l0[:, 0]
return np.maximum(best + xn, 0.0), lab
def cell_centric_assign(X, C, coarse, nprobe, cell_of=None):
"""Approximate nearest-centroid search where all rows of a coarse cell share one candidate set:
the centroids in the `nprobe` coarse cells nearest to that cell's centre. One large BLAS product
per cell. Returns (squared dist, label)."""
import faiss
X = np.ascontiguousarray(X, dtype=np.float32); C = np.ascontiguousarray(C, dtype=np.float32)
coarse = np.ascontiguousarray(coarse, dtype=np.float32)
L = len(coarse)
if cell_of is None:
cell_of = faiss.knn(C, coarse, 1)[1][:, 0]
_, near = faiss.knn(coarse, coarse, min(nprobe, L)) # cell -> nearby cells
_, qc = faiss.knn(X, coarse, 1); qc = qc[:, 0]
cn = (C * C).sum(1); xn = (X * X).sum(1)
corder = np.argsort(cell_of, kind="stable"); cstart = np.searchsorted(cell_of[corder], np.arange(L + 1))
qorder = np.argsort(qc, kind="stable"); qstart = np.searchsorted(qc[qorder], np.arange(L + 1))
best = np.empty(len(X), np.float32); lab = np.empty(len(X), np.int64)
for j in range(L):
q = qorder[qstart[j]:qstart[j + 1]]
if len(q) == 0:
continue
cand = np.concatenate([corder[cstart[c]:cstart[c + 1]] for c in near[j]])
d = (X[q] @ C[cand].T); d *= -2.0; d += cn[cand][None, :]
a = d.argmin(1)
best[q] = d[np.arange(len(q)), a]; lab[q] = cand[a]
return np.maximum(best + xn, 0.0), lab
def fused_stats(X, labels, C, U, sums, counts, b_axis, b_proj):
"""One pass over a batch: e-means' cluster sums and counts plus PISCES' axis statistics."""
order = np.argsort(labels, kind="stable")
lab = labels[order]
labs, starts = np.unique(lab, return_index=True)
starts = np.append(starts, len(lab)).astype(np.int64)
if HAVE_NUMBA:
_fused_stats_nb(np.ascontiguousarray(X, dtype=np.float32), order.astype(np.int64), starts,
labs.astype(np.int64), C, U, sums, counts, b_axis, b_proj)
return
e = X - C[labels]; p = np.einsum("ij,ij->i", e, U[labels])
np.add.at(sums, labels, X); counts += np.bincount(labels, minlength=len(C))
b_axis[labs] += np.add.reduceat((e * p[:, None])[order], starts[:-1], axis=0)
b_proj += np.bincount(labels, weights=p.astype(np.float64) ** 2, minlength=len(C))