File size: 3,836 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
"""Downstream use: the centroids as the coarse quantizer of an IVF index (the use case e-means targets).

For each method and seed, train k centroids on DEEP* 1M, build IndexIVFFlat over the same 1M rows
with those centroids, and measure on the 10K public DEEP1B queries (exact ground truth on the 1M rows):
  - recall@1 and recall@10 (10-NN found among the 10 returned) at nprobe in NPROBES,
  - distance computations per query (sum of probed list sizes), the real cost of an IVF search,
  - list imbalance factor k * sum(n_i^2) / n^2 (1 = perfectly balanced).

Usage: python benchmarks/ivf_downstream.py DATA/deep1b OUT.jsonl --epochs 3 --seeds 10 11 12 --methods official pisces
"""
import argparse, json, os, sys, time
import numpy as np
import faiss

ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
sys.path.insert(0, ROOT)
sys.path.insert(0, os.path.join(ROOT, "benchmarks"))
from paper_protocol import METHODS, make_variant  # noqa: E402

NPROBES = [1, 2, 4, 8, 16, 32, 64, 128]


def read_fbin(path):
    n, d = np.fromfile(path, dtype="int32", count=2)
    return np.fromfile(path, dtype="float32", offset=8).reshape(n, d)


def main():
    ap = argparse.ArgumentParser()
    ap.add_argument("data"); ap.add_argument("out")
    ap.add_argument("--k", type=int, default=16384)
    ap.add_argument("--epochs", type=float, nargs="+", default=[3])
    ap.add_argument("--seeds", type=int, nargs="+", default=[10, 11, 12])
    ap.add_argument("--methods", nargs="+", default=["official", "pisces"])
    ap.add_argument("--threads", type=int, default=4)
    a = ap.parse_args()
    faiss.omp_set_num_threads(a.threads)
    x = np.ascontiguousarray(np.load(os.path.join(a.data, "train_1M.npy")))
    q = np.ascontiguousarray(read_fbin(os.path.join(a.data, "query.public.10K.fbin")))
    _, gt = faiss.knn(q, x, 10)
    from aries.pemeans import PISCES
    METHODS["pisces"] = make_variant(PISCES, len(x))
    done = set()
    if os.path.exists(a.out):
        done = {(r["method"], r["epochs"], r["seed"]) for r in map(json.loads, open(a.out))}
    for T in a.epochs:
        for s in a.seeds:
            init = x[np.random.RandomState(s).permutation(len(x))[:a.k]].copy()
            for m in a.methods:
                if (m, T, s) in done:
                    continue
                t0 = time.time()
                c, _ = METHODS[m](x.shape[1], T, s).train(x, init_centroids=init.copy())
                sec = time.time() - t0
                c = np.ascontiguousarray(c, dtype="float32")
                quant = faiss.IndexFlatL2(x.shape[1]); quant.add(c)
                ivf = faiss.IndexIVFFlat(quant, x.shape[1], a.k); ivf.is_trained = True; ivf.add(x)
                sizes = np.array([ivf.invlists.list_size(i) for i in range(a.k)], dtype="float64")
                imb = float(a.k * (sizes ** 2).sum() / sizes.sum() ** 2)
                r = dict(method=m, epochs=T, seed=s, k=a.k, train_seconds=sec, imbalance=imb,
                         empty_lists=int((sizes == 0).sum()), curve=[])
                for npb in NPROBES:
                    ivf.nprobe = npb
                    _, Dq = quant.search(q, npb)
                    ndis = float(sizes[Dq].sum(1).mean())
                    t1 = time.time(); _, I = ivf.search(q, 10); qs = time.time() - t1
                    r1 = float((I[:, 0] == gt[:, 0]).mean())
                    r10 = float(np.mean([len(set(I[i]) & set(gt[i])) / 10 for i in range(len(q))]))
                    r["curve"].append(dict(nprobe=npb, recall1=r1, recall10=r10, ndis=ndis, seconds=qs))
                with open(a.out, "a") as f:
                    f.write(json.dumps(r) + "\n")
                print(m, T, s, f"imb {imb:.3f}", " ".join(f"{c_['nprobe']}:{c_['recall1']:.3f}/{c_['ndis']:.0f}" for c_ in r["curve"]), flush=True)


if __name__ == "__main__":
    main()