File size: 4,705 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
"""Correctness tests for PE-means. Run: python -m pytest -q tests"""
import os, sys
import numpy as np
import faiss
import pytest

sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
from faiss.contrib.e_means import NumpyEmeans  # noqa: E402
from aries.pemeans import PEmeans  # noqa: E402

faiss.omp_set_num_threads(1)


def data(n=20000, d=16, comps=64, seed=0):
    r = np.random.default_rng(seed)
    c = r.normal(0, 4, (comps, d))
    return (c[r.integers(0, comps, n)] + r.standard_normal((n, d))).astype("float32")


@pytest.mark.parametrize("seed", [0, 1, 2])
def test_identity_with_official_when_switches_off(seed):
    """split='faiss', gain='usage' must reproduce faiss's NumpyEmeans bit for bit."""
    x = data(seed=seed); k = 128
    init = x[np.random.RandomState(seed).permutation(len(x))[:k]].copy()
    a, _ = NumpyEmeans(16, k, nepochs=2, seed=seed).train(x, init_centroids=init.copy())
    b, _ = PEmeans(16, k, nepochs=2, seed=seed, split="faiss", gain="usage").train(x, init_centroids=init.copy())
    assert np.array_equal(a, b)


def test_principal_axis_converges_on_elongated_cluster():
    """One elongated Gaussian: the tracked axis must align with its long direction."""
    r = np.random.default_rng(0)
    x = (r.standard_normal((20000, 8)) * np.array([5, 1, 1, 1, 1, 1, 1, 1])).astype("float32")
    km = PEmeans(8, 1, nepochs=2, seed=0)
    km.train(x, init_centroids=x[:1].copy())
    assert abs(km._axis[0, 0]) > 0.95


def test_principal_split_places_children_symmetrically():
    km = PEmeans(4, 2, nepochs=1, seed=0)
    x = np.random.default_rng(0).standard_normal((64, 4)).astype("float32")
    km.begin(len(x), x[:2].copy())
    km._centroids[0] = 0.0
    km._usage[:] = [10.0, 0.0]
    km._axis[0] = [1, 0, 0, 0]
    km._proj_sq[0] = 40.0                      # lambda = 4  -> sigma = 2
    km._apply_splits(np.array([0]), np.array([1]))
    delta = np.sqrt(2 / np.pi) * 2.0
    assert np.allclose(km._centroids[0], [delta, 0, 0, 0], atol=1e-5)
    assert np.allclose(km._centroids[1], [-delta, 0, 0, 0], atol=1e-5)
    assert np.allclose(km._usage, [5.0, 5.0])


def test_pemeans_not_worse_on_mixture():
    x = data(n=40000, d=16, comps=256, seed=3); k = 256
    errs = {}
    for name, mk in [("off", lambda s: NumpyEmeans(16, k, nepochs=2, seed=s)),
                     ("pe", lambda s: PEmeans(16, k, nepochs=2, seed=s))]:
        vals = []
        for s in range(3):
            init = x[np.random.RandomState(s).permutation(len(x))[:k]].copy()
            c, _ = mk(s).train(x, init_centroids=init)
            vals.append(faiss.knn(x, c, 1)[0].mean())
        errs[name] = np.mean(vals)
    assert errs["pe"] <= errs["off"] * 1.01


def test_fused_stats_matches_numpy():
    """The fused Numba kernel computes the same per-cluster statistics as the NumPy path."""
    from aries._kernels import fused_stats
    rng = np.random.default_rng(0)
    k, d, n = 37, 12, 3000
    X = rng.standard_normal((n, d)).astype("float32"); C = rng.standard_normal((k, d)).astype("float32")
    U = rng.standard_normal((k, d)).astype("float32"); U /= np.linalg.norm(U, axis=1, keepdims=True)
    lab = rng.integers(0, k - 3, n)
    sums = np.zeros((k, d), "float32"); cnt = np.zeros(k); ax = np.zeros((k, d), "float32"); pj = np.zeros(k)
    fused_stats(X, lab, C, U, sums, cnt, ax, pj)
    e = X.astype("float64") - C[lab]; p = (e * U[lab]).sum(1)
    ref_sums = np.zeros((k, d)); np.add.at(ref_sums, lab, X)
    ref_ax = np.zeros((k, d)); np.add.at(ref_ax, lab, e * p[:, None])
    assert np.allclose(sums, ref_sums, atol=1e-3) and np.allclose(cnt, np.bincount(lab, minlength=k))
    assert np.allclose(ax, ref_ax, atol=1e-3) and np.allclose(pj, np.bincount(lab, weights=p ** 2, minlength=k), rtol=1e-5)


@pytest.mark.parametrize("d", [96, 100])
def test_sq8r_assignment_any_dimension(d):
    """8-bit scan + exact re-rank returns the float32 IVF answer, also when d % 8 != 0 (zero-padded scan)."""
    rng = np.random.default_rng(1)
    k = 4096                                   # the sparse rule applies from APPROX_MIN_K = 4,096
    C = (rng.standard_normal((k, d)) * 10).round().astype("float32")    # integer-valued, like SPACEV
    X = (C[rng.integers(0, k, 4000)] + rng.standard_normal((4000, d)) * 3).astype("float32")
    labels = {}
    for codec in ("flat", "sq8r"):
        m = PEmeans(d, k, nepochs=1, seed=0, approx="auto", codec=codec)
        m._coarse = None; m._epoch = 0; m._step = 0; m.recipe = {"total_steps": 1}
        labels[codec] = m._approx_assign(X, C)[1]
    assert PEmeans(d, 1024, approx="auto").approx is None         # small k: exact assignment
    assert (labels["flat"] == labels["sq8r"]).mean() > 0.999