|
Download docs/DERIVATIONS.md from Nabidnur/PISCES: direct link, hf CLI and curl.
- Browser
- Download file 6.96 kB
-
https://huggingface.co/Nabidnur/PISCES/resolve/main/docs/DERIVATIONS.md
- Command line
-
hf download hf://Nabidnur/PISCES/docs/DERIVATIONS.md
-
curl -L -o DERIVATIONS.md https://huggingface.co/Nabidnur/PISCES/resolve/main/docs/DERIVATIONS.md
6.96 kB
| # PE-means: principal-axis, gain-ranked revival for e-means | |
| Technical note. Code: [`aries/pemeans.py`](../aries/pemeans.py). Benchmark: | |
| [`benchmarks/paper_protocol.py`](../benchmarks/paper_protocol.py). | |
| ## 1. Where the gain can come from | |
| e-means (Bessa et al., arXiv:2611.09501) streams mini-batches, keeps an exponential moving average | |
| of each cluster's mass `N_j` and centroid `c_j`, sets batch size and step from fitted scaling laws, | |
| and every 5 batches revives clusters whose mass falls below `0.1 · mean(N)`. Revival is the | |
| component with the largest effect in the paper's ablation (Table 1: +2.97% train MSE, +2.24% test | |
| MSE without it). It is also busy: on DEEP\* 1M with k = 16,384 we count about 9,000 revivals in the | |
| first epoch and 6,900 over three epochs. | |
| Each revival in faiss picks a donor with probability proportional to `N_j` and places donor and | |
| child at `c_j · (1 ∓ 1e-4 · s)`, with `s` an alternating ±1 vector. The two copies start on top of | |
| each other; only later assignments separate them, and the donor may be a heavy but tight cluster | |
| where a split gains little. | |
| ## 2. Two closed-form answers for a Gaussian cluster | |
| Let a cluster be `x ~ N(c, Σ)` with mass `N`, and split it by the hyperplane through `c` orthogonal | |
| to a unit vector `u`, with `σ_u² = uᵀ Σ u`. | |
| **Lemma 1 (child positions).** The two halves have means `c ± sqrt(2/π) · σ_u · u` (the mean of a | |
| half-normal is `σ sqrt(2/π)`). | |
| **Lemma 2 (distortion removed).** Along `u` each half keeps variance `σ_u² (1 − 2/π)`; orthogonal | |
| directions are unchanged. The split therefore lowers total distortion from `N tr(Σ)` to | |
| `N (tr(Σ) − (2/π) σ_u²)`, a reduction of `(2/π) · N · σ_u²`. This is maximal at `u = u_1`, the top | |
| eigenvector, where it equals `(2/π) · N · λ_1`. | |
| Consequences for revival: put the children at `c ± sqrt(2/π) sqrt(λ_1) u_1`, and give the free | |
| centroid to the cluster with the largest `N · λ_1`, not the largest `N`. | |
| The child placement is the one G-means uses (Hamerly and Elkan, NeurIPS 2003), and principal | |
| direction splitting goes back to PDDP (Boley, 1998) and LBG codebook splitting (Linde, Buzo and | |
| Gray, 1980). What is new here is using it inside e-means' streaming revival, with the axis | |
| estimated online and donors ranked by expected gain. | |
| ## 3. Estimating `u_1` and `λ_1` online, at negligible cost | |
| For every cluster PE-means keeps `V_j ∈ R^d` and a scalar `P_j`. For each assigned row with | |
| residual `e = x − c_j` and projection `p = eᵀ u_j`, the batch accumulates `Σ p e` and `Σ p²`; then, | |
| with the same EMA step `α` e-means uses for the centroids, | |
| ``` | |
| V_j ← (1 − α) V_j + α Σ p e u_j ← V_j / |V_j| | |
| P_j ← (1 − α) P_j + α Σ p² λ_j ≈ P_j / N_j | |
| ``` | |
| `Σ p e = (Σ e eᵀ) u_j`, so each update is one step of power iteration on the cluster's EMA scatter | |
| matrix; `u_j` converges to the top eigenvector at the usual rate `λ_2 / λ_1`. Memory is one extra | |
| `k × d` array (the size of the centroids); compute is O(B·d) per batch, against O(B·k·d) for | |
| assignment. On DEEP\* 1M the measured overhead is 7-10% of wall-clock. | |
| ## 4. Implementation contract | |
| `PEmeans` subclasses the official `faiss.contrib.e_means.NumpyEmeans` and overrides only | |
| `begin`, `_assign_rows` (to accumulate `Σ p e`, `Σ p²`), `_apply_statistics` (EMA of those), | |
| `_choose_splits` and `_apply_splits`. Batch law, step law, cosine schedule, EMA update, revival | |
| threshold and closing means are inherited. With `split="faiss", gain="usage"` it reproduces the | |
| official centroids bit for bit (`tests/test_pemeans.py`). | |
| ## 5. Results so far | |
| See the [README](../README.md) for the table. On DEEP\* 1M (the paper's data and test rows, | |
| k = 16,384, 5 seeds, matched starting centroids, 4 CPU threads), PE-means lowers test MSE by 0.31%, | |
| 0.27% and 0.20% at 1, 3 and 5 epochs (15 of 15 paired wins), and at 3 epochs matches official | |
| e-means at 5 epochs in 0.60× the time. On a smaller proxy (DEEP 200k, k = 2,048) the ablation gives: | |
| principal-axis split alone −0.07%, gain-ranked donor alone −0.12%, both −0.25% (one epoch); the | |
| two parts add up. | |
| ## 6. Limitations | |
| * The optimality argument assumes roughly Gaussian clusters; heavy-tailed clusters may need a | |
| robust axis estimate (planned with o-means). | |
| * Results are on CPU float32; the paper's numbers are on H100 bfloat16. Starting rows are drawn | |
| with NumPy rather than a CUDA generator (shared by both methods). | |
| * Five seeds per budget so far; held-out confirmation on SimSearchNet++ 1M and SPACEV 1M is | |
| running. No claim beyond these datasets is made yet. | |
| * The 7-10% overhead is real; the cross-budget comparison (3 vs 5 epochs, 2.7 vs 3 epochs) is the | |
| fair equal-time view. | |
| ## References | |
| - Bessa, Mazaré, Szilvasy, Touvron, Picard, Douze, Jégou (2026). e-means: outperforming k-means | |
| (in one-tenth the epochs). arXiv:2611.09501. | |
| - Hamerly and Elkan (2003). Learning the k in k-means. NeurIPS. | |
| - Boley (1998). Principal direction divisive partitioning. Data Mining and Knowledge Discovery. | |
| - Linde, Buzo and Gray (1980). An algorithm for vector quantizer design. IEEE Trans. Communications. | |
| - Oja (1982). A simplified neuron model as a principal component analyzer. J. Math. Biology. | |
| ## 7. v2 and v3 additions (iterations 2-11, `docs/EXPERIMENTS.md`) | |
| * **Consistent closing statistics** (`split_pass`). faiss's final centroids are the mean of each | |
| cluster's last-epoch assignments. When a donor is split during that epoch, both children | |
| inherited the parent's pre-split sums; PE-means splits those sums consistently (half the count | |
| each, means at `c ± delta`). Largest effect at one epoch (−0.29% → −0.64% on the proxy). | |
| * **Revival threshold 0.2 and step law × 1.4.** With better splits, more aggressive revival and a | |
| larger EMA step pay off; the larger step alone does not help official e-means (an interaction). | |
| * **Revival every batch during the first 30% of steps** (v3). | |
| * **Approximate early-epoch assignment** (v3). Every epoch but the last assigns rows through an IVF | |
| over the current centroids: √k coarse cells from a 20-iteration k-means on the centroids, √k/8 | |
| probes; the index is rebuilt per batch for O(k·√k·d) work. The last epoch, which builds the closing | |
| means, stays exact. On DEEP\* 1M this makes an epoch 35-50% cheaper and, surprisingly, *improves* | |
| quality relative to exact assignment (−0.34% vs −0.17% vs official at 3 epochs); more probes (more | |
| exact) is worse and fewer probes (8) too noisy. A plausible reading is annealing-like noise early in | |
| training; this is a hypothesis, not a proven mechanism. | |
| * **Negative results kept:** streaming swap moves (deletion cost vs split gain), fresher closing | |
| window, child-mass and threshold schedules, graph-pruned assignment with label memory (21% of rows | |
| have a nearer centroid outside the candidate set one epoch later; a self-verifying variant falls | |
| back to exact on almost every batch). | |