pulsatrix 1.1.0
Loading...
Searching...
No Matches
nearest_neighbors.hpp File Reference

Nearest neighbors over embeddings or activations, mutual nearest neighbors, and mutual-kNN alignment between two representations. More...

#include <cstdint>
#include <utility>
#include <vector>
#include "pulsatrix/tensor.hpp"
Include dependency graph for nearest_neighbors.hpp:

Go to the source code of this file.

Classes

struct  pulsatrix::NeighborOptions
 Settings for the neighbor searches. More...
 
struct  pulsatrix::Neighbors
 Each query's k nearest points, nearest first. More...
 
struct  pulsatrix::Hubness
 How unevenly points appear in each other's neighbor lists. More...
 

Namespaces

namespace  pulsatrix
 

Enumerations

enum class  pulsatrix::NeighborMetric { pulsatrix::Cosine , pulsatrix::Euclidean }
 How nearness is measured. More...
 

Functions

Neighbors pulsatrix::NearestNeighbors (const Tensor &points, const NeighborOptions &options={})
 Each point's k nearest other points (a point is never its own neighbor).
 
Neighbors pulsatrix::NearestNeighbors (const Tensor &queries, const Tensor &points, const NeighborOptions &options={})
 Each query's k nearest points from another set of the same width, for example new inputs against a reference set. With center, both are centered on the points' mean.
 
std::vector< std::pair< int64_t, int64_t > > pulsatrix::MutualNearestNeighbors (const Tensor &a, const Tensor &b, const NeighborOptions &options={})
 The pairs (i, j), a[i] from a and b[j] from b, where b[j] is among a[i]'s k nearest in b and a[i] is among b[j]'s k nearest in a. Used to match items across two sets in the same space, such as the same concepts in two batches.
 
double pulsatrix::MutualKnnAlignment (const Tensor &a, const Tensor &b, const NeighborOptions &options={})
 Mutual-kNN alignment (Huh et al. 2024): how far two representations of the same inputs agree on which inputs are alike. For each input, the fraction of its k nearest neighbors under a that are also among its k nearest under b, averaged over the inputs.
 
Hubness pulsatrix::MeasureHubness (const Neighbors &neighbors, int64_t num_points)
 Measures hubness in neighbors, which name points 0 to num_points - 1.
 

Detailed Description

Nearest neighbors over embeddings or activations, mutual nearest neighbors, and mutual-kNN alignment between two representations.

The questions these answer: which inputs does a layer treat as alike, which items of two sets pair up, and do two models agree about which inputs are alike (Huh et al., "The Platonic Representation Hypothesis", ICML 2024)? Everything is exact (no approximate index) and computed in double precision on the host, at about n × m × width multiply-adds for n queries and m points.

In high dimensions a few points can turn up in almost everyone's neighbor list ("hubs"), which makes neighbor-based scores mean less. MeasureHubness() says how much that is happening.