Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
PyNNDescent: Fast Approximate Nearest Neighbors...
Search
Leland McInnes
July 16, 2021
Programming
1.1k
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
PyNNDescent: Fast Approximate Nearest Neighbors with Numba
A PDF version of slides for my SciPy 2021 talk on PyNNDescent.
Leland McInnes
July 16, 2021
Transcript
87 slides
Fast Approximate Nearest Neighbour Search with Numba
What are Nearest Neighbours?
Given a set of points with A distance measure between
them…
… and a new “query point” …
Find the closest points to the query point
Why Nearest Neighbors?
Nearest Neighbour computations are at the heart of many machine
learning algorithms
KNN-Classi fi ers KNN-Regressors
Clustering https://commons.wikimedia.org/wiki/File:DBSCAN-Illustration.svg by Chire https://www. fl ickr.com/photos/trevorpatt/41875889652/in/photostream/ by Trevor Patt
HDBSCAN DBSCAN Single Linkage Clustering Spectral Clustering
Dimension Reduction http://lvdmaaten.github.io/tsne/ http://www-clmc.usc.edu/publications/T/tenenbaum-Science2000.pdf t-SNE Isomap Spectral Embedding UMAP
Recommender Systems Query Expansion
Why Approximate Nearest Neighbours?
Finding exact nearest neighbours is hard
Approximate nearest neighbour search trades accuracy for performance
How Do You Find Nearest Neighbors?
Using Trees
Hierarchically divide up the space into a tree
Bound the search using the tree structure (And the triangle
inequality)
KD-Tree
Ball Tree
Random Projection Tree
Using Graphs
How do you search for nearest neighbours of a query
using a graph? Malkov and Yashunin, 2018 Dong, Moses and Li, 2011 Iwasaki and Miyazaki, 2018
Start with a nearest neighbour graph of the training data
Assume we now want to fi nd neighbours of a query point
Choose a starting node in the graph (potentially randomly) as
a candidate node
None
Look at all nodes connected by an edge to the
best untried candidate node in the graph Add all these nodes to our potential candidate pool
None
Sort the candidate pool by closeness to the query point
Truncate the pool to the k best candidates
None
Return to the Expansion step unless we have already tried
all the candidates in the pool
Stop when there are no untried candidates in the pool
None
None
None
None
Looks inef fi cient Scales up well
None
Graph adapts to intrinsic dimension of the data
But how do we build the graph?!
The algorithm works (badly) even on a bad graph
Run one iteration of search for every node Update the
graph with new better neighbours Search is better on the improved graph
None
None
None
None
None
Perfect accuracy of neighbours is not assured We can get
an approximate knn-graph quickly
How Do You Make it Fast?
Algorithm tricks
Query node Expansion node Current neighbour
Neighbour A Neighbour B Common node
Hubs have a lot of neighbours!
None
None
Sample neighbours when constructing the graph Prune away edges before
performing searches
Necessary to fi nd green’s nearest neighbour Necessary to fi
nd blue’s nearest neighbour Not required since we can traverse through blue
For search remove the longest edges of any triangles in
the graph
Initialize with Random Projection Trees
Implementation tricks
None
Pro fi le and inspect llvm code for innermost functions
Type declarations and code choices can help the compiler a lot!
@numba.jit def euclidean(x, y): return np.sqrt(np.sum((x - y)**2)) Query benchmark
took 12s
@numba.jit(fastmath=True) def euclidean(x, y): result = 0.0 for i in
range(x.shape[0]): result += (x[i] - y[i])**2 return np.sqrt(result) Query benchmark took 8.5s
@numba.njit( numba.types.float32( numba.types.Array( numba.types.float32, 1, "C", readonly=True ), numba.types.Array( numba.types.float32,
1, "C", readonly=True ), ), fastmath=True, locals={ "result": numba.types.float32, "diff": numba.types.float32, "i": numba.types.uint16, }, ) def squared_euclidean(x, y): result = 0.0 dim = x.shape[0] for i in range(dim): diff = x[i] - y[i] result += diff * diff return result Query benchmark took 7.6s
Custom data structure implementations to help numba for often called
code
@numba.njit( "i4(f4[ :: 1],i4[ :: 1],f4,i4)", ) def simple_heap_push(priorities, indices,
p, n): ...
Numba has signi fi cant function call overhead with large
parameters Use closures over static data instead
@numba.njit() def frequently_called_function(param, large_readonly_data): ... val = access(large_readonly_data, param) ...
def create_frequently_called_function(large_readonly_data): @numba.njit() def closure(param): ... val = access(large_readonly_data, param) ... return closure
How Does it Compare?
Performance
We can test query performance using ann-benchmarks https://github.com/erikbern/ann-benchmarks
Consider the whole accuracy / performance trade-off space
vs
None
None
None
None
Caveats: •Newer algorithms and implementations •Hardware can makes a big
difference •No GPU support for pynndescent
Features
Out of the box support for a wide variety of
distance measures: Euclidean Cosine Hamming Manhattan Minkowski Chebyshev Jaccard Haversine Dice Wasserstein Hellinger Spearman Correlation Mahalanobis Canberra Bray-Curtis Angular TSSS +20 more measures https://towardsdatascience.com/9-distance-measures-in-data-science-918109d069fa By Maarten Grootendorst
Custom metrics in Python (using numba)
Support for sparse data
Drop-in replacement for sklearn KNeighborsTransformer
Summary
pip install pynndescent conda install pynndescent https://github.com/lmcinnes/pynndescent
[email protected]
@leland_mcinnes
Questions?
[email protected]
@leland_mcinnes
More Decks by Leland McInnes
See All by Leland McInnes
Word and Document Embeddings
lmcinnes
0
190
Topological Data Analysis
lmcinnes
1
400
Ensemble Topic Modelling
lmcinnes
1
520
Learning Topology: topological methods for unsupervised learning
lmcinnes
2
3.7k
A Guide to Dimension Reduction
lmcinnes
3
1.5k
UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
lmcinnes
2
2.8k
Other Decks in Programming
See All in Programming
Augmenting AI with the Power of Jakarta EE
ivargrimstad
0
390
AI駆動開発4年目の現在地(『あなたはFDEになるべきか?』イベント資料)
kumaiu
0
680
はじめてのPLATEAU
nokonoko1203
1
660
Growing PicoRuby's Ecosystem on ESP32
yuuu
2
150
[DroidKnights 2026] Workflow AX 적용기 — 자동 정책 정리부터 E2E까지
dayeon
0
120
Python Lambdaにおけるテストしやすい設計とAI支援の活用 / Designing Testable Python Lambda Functions with AI
kitano_yuichi
1
350
学びを記事・スライド・Xへ高速展開する― AI-assisted Learning Loopで回すコンテンツ生成術
ochtum
0
220
クラウドエージェントは、 何がそんなに便利なのか / what makes cloud agents so useful
rkaga
5
950
React Native에 현대적인 빌드 도구 더하기: Rollipop 구현기
leegeunhyeok
0
190
Kotlin JVM用に作られたライブラリのKMPを前提とした再設計
jsoizo
0
220
AI時代のIaC入門 〜なぜインフラをコードで管理したいのか?〜 / Introduction to IaC in the AI Era
akihisaikeda
6
1.6k
地方こそサーバーレス — 10年続けた、顔が見えるチームで確かな基盤を / Serverless Matters Most in Regional Areas — 10 Years of Building Reliable Foundations with Close-Knit Teams
seike460
PRO
2
500
Featured
See All Featured
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
35
2.6k
Bioeconomy Workshop: Dr. Julius Ecuru, Opportunities for a Bioeconomy in West Africa
akademiya2063
PRO
1
460
Understanding Cognitive Biases in Performance Measurement
bluesmoon
32
3.1k
The Invisible Side of Design
smashingmag
301
52k
Facilitating Awesome Meetings
lara
57
7.2k
More Than Pixels: Becoming A User Experience Designer
marktimemedia
3
630
Impact Scores and Hybrid Strategies: The future of link building
tamaranovitovic
0
490
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
234
18k
Leo the Paperboy
mayatellez
11
2.5k
The Power of CSS Pseudo Elements
geoffreycrofte
82
6.6k
Writing Fast Ruby
sferik
630
63k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
35
2.9k