File size: 6,961 Bytes
c09a3f4 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | # 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).
|