🤖 AI

Probabilistic Kernel Function for Fast Angle Testing

Dit paper introduceert twee deterministische, projectie-gebaseerde probabilistische kernfuncties voor hoektesten in hoge dimensies die zonder asymptotische aannames de prestaties van Gaussische methoden overtreffen en in ANNS-taken een 2,5 tot 3 keer hogere doorvoer dan HNSW bereiken.

Oorspronkelijke auteurs: Kejing Lu, Chuan Xiao, Yoshiharu Ishikawa

Gepubliceerd 2026-03-03

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Kejing Lu, Chuan Xiao, Yoshiharu Ishikawa

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Snelle Zoektocht: Hoe je een naald in een hooiberg vindt zonder de hele berg te doorzoeken

Stel je voor dat je in een gigantische bibliotheek zit met miljoenen boeken (data), en je zoekt een specifiek boek dat lijkt op een boek dat je bij je hebt (je zoekopdracht). In de digitale wereld noemen we dit similarity search (gelijksoortigheidszoekopdracht). De boeken zijn hier geen papieren boeken, maar lange lijsten met getallen (vectoren) in een ruimte met duizenden dimensies.

Het probleem? Als je elke boek met je eigen boek moet vergelijken, duurt het eeuwen. Je hebt een slimme manier nodig om snel te zeggen: "Dit boek lijkt erop" of "Nee, dit boek is te ver weg", zonder de hele inhoud te hoeven lezen.

De auteurs van dit paper (Kejing Lu, Chuan Xiao en Yoshiharu Ishikawa) hebben een nieuwe, supersnelle manier bedacht om deze vergelijkingen te maken. Ze noemen het een probabilistische kernfunctie. Klinkt ingewikkeld? Laten we het anders bekijken.

1. Het oude probleem: De willekeurige gok

Vroeger gebruikten wetenschappers een techniek waarbij ze willekeurige lijnen (projectievectoren) door de bibliotheek trokken, alsof ze blindelings met een speer in het donker staken. Als je speer een boek raakte, hoopten ze dat het een boek was dat op jouw zoekopdracht leek.

Het nadeel? Ze moesten duizenden van deze willekeurige speer-worpen doen om zeker te zijn. Het was alsof je zegt: "Als ik maar genoeg willekeurige lijnen trek, zal het wel goed komen." Dit werkt, maar het is traag en niet altijd perfect.

2. De nieuwe oplossing: De "Referentiehoek"

De auteurs zeggen: "Wacht even, waarom gooien we willekeurig? Laten we eerst een vaste, slimme kaart maken."

In plaats van willekeurige lijnen, kiezen ze voor een referentiehoek.

De Analogie: Stel je voor dat je in een donkere kamer staat en een vriend zoekt. De oude methode was: "Ik roep willekeurig 'Hé!' en hoop dat iemand reageert."
De nieuwe methode: De auteurs zeggen: "Laten we eerst een vaste lantaarnpaal (de referentie) neerzetten. Als mijn vriend binnen een bepaalde hoek van die lantaarn staat, weet ik met bijna 100% zekerheid dat hij dichtbij is."

Ze gebruiken geen willekeurige lijnen meer, maar een bepaalde, vaste structuur (zoals een perfect geplaatst raster van lantaarnpalen). Hierdoor hoeven ze niet te wachten tot ze "oneindig veel" lijnen hebben getrokken om een goed resultaat te krijgen. Het werkt direct en betrouwbaarder.

3. Twee soorten tests

Ze hebben twee nieuwe gereedschappen ontwikkeld:

Test A (Vergelijken): "Is boek A dichter bij mijn zoekopdracht dan boek B?"
- Vergelijking: Het is alsof je twee vrienden vraagt: "Wie staat dichter bij de lantaarn?" Omdat je de lantaarn (de referentie) slim hebt geplaatst, kun je dit antwoord geven zonder de exacte afstand te meten. Het is een snelle schatting die bijna altijd klopt.
Test B (Drempel): "Is boek C dichterbij dan een bepaalde afstand?"
- Vergelijking: "Is deze persoon binnen de veiligheidszone?" Als het antwoord "nee" is, gooi je het boek direct weg. Je hoeft het niet eens te bekijken. Dit bespaart enorm veel tijd.

4. Het resultaat: Sneller dan ooit tevoren

Ze hebben deze nieuwe methode getest op een van de populairste zoeksystemen ter wereld, genaamd HNSW (een soort slimme kaart voor zoekopdrachten).

Het resultaat: Hun nieuwe systeem (HNSW+KS2) is 2,5 tot 3 keer sneller dan het oude systeem.
De analogie: Stel je voor dat je normaal 1 uur nodig hebt om een stad te verkennen. Met hun nieuwe methode doe je het in 20 minuten, en je vindt precies dezelfde plekken.
Bijkomend voordeel: Het systeem is ook nog eens iets kleiner (bespaart opslagruimte) en werkt net iets nauwkeuriger dan de vorige beste methoden.

Samenvatting in één zin

De auteurs hebben een manier bedacht om in een enorme, complexe digitale wereld sneller te vinden wat je zoekt, door niet meer blindelings te gokken met willekeurige lijnen, maar door slimme, vaste "landkaarten" te gebruiken die de zoektocht drastisch versnellen.

Waarom is dit belangrijk?
Dit helpt bij alles van het vinden van de juiste foto in een app, het aanbevelen van de juiste video op Netflix, tot het vinden van medische patronen in grote databases. Alles wordt sneller en efficiënter.

Probleemstelling

Het paper richt zich op het probleem van similairheidszoekopdrachten (similarity search) in hoge-dimensionale Euclidische ruimten. De kernuitdaging is het efficiënt vinden van data-punten die het meest lijken op een query-vector, gebaseerd op hoekmetingen (zoals cosinus-ähnelijkheid).

Hoewel het exact berekenen van hoeken kostbaar is ( $O(d)$ per vergelijking), zijn veel toepassingen (zoals Approximate Nearest Neighbor Search - ANNS) niet geïnteresseerd in de exacte hoekwaarde, maar slechts in het resultaat van een vergelijking:

Hoekvergelijking: Welke van twee vectoren ( $v_1$ of $v_2$ ) heeft een kleinere hoek met de query $q$ ?
Hoek-drempeltest: Is de hoek tussen $q$ en $v$ kleiner dan een bepaalde drempel $\theta$ ?

Bestaande methoden, zoals die gebaseerd op Random Projection met vectoren uit een Gaussische verdeling (bijv. CEOs, Falconn, PEOs), vertrouwen op asymptotische aannames (het aantal projectievectoren $m \to \infty$ ). In de praktijk is $m$ echter beperkt door rekentijd, wat leidt tot onnauwkeurigheden en theoretische beperkingen. Het doel is een probabilistische kernel-functie te ontwerpen die deze tests uitvoert met een lagere kost ( $o(d)$ ) en zonder afhankelijkheid van asymptotische limieten.

Methodologie

De auteurs introduceren twee nieuwe probabilistische kernel-functies, $K^1_S$ en $K^2_S$ , die gebaseerd zijn op referentiehoeken in plaats van puur willekeurige Gaussische projecties.

Kernconcept: Referentiehoeken en Deterministische Structuur
- In tegenstelling tot eerdere werken die alleen de projectievector met de grootste inproduct gebruiken, gebruiken de nieuwe functies zowel de referentievector ( $Z_S(v)$ ) als de referentiehoek ( $A_S(v)$ , de hoek tussen de data-vector en de dichtstbijzijnde projectievector).
- De auteurs bewijzen dat de nauwkeurigheid van de schatting direct afhankelijk is van de grootte van deze referentiehoek: hoe kleiner de hoek, hoe nauwkeuriger de test.
- Ze introduceren een deterministische relatie tussen de hoek en de projectiewaarde, wat de noodzaak van de asymptotische aanname ( $m \to \infty$ ) uit de bestaande theorie (Lemma 1.3) verwijdert.
Configuratie van Projectievectoren
- Om de referentiehoek te minimaliseren, worden twee specifieke structuren voor de set projectievectoren $S$ $S$ voorgesteld, die beter presteren dan willekeurige Gaussische verdelingen:
  - Antipodale projecties (Alg. 1): Gebruikt paren van tegenovergestelde vectoren.
  - Meerdere kruispolytope (Alg. 2): Bouwt de set op uit geroteerde kruispolytope (cross-polytopes), wat empirisch leidt tot de kleinste referentiehoeken en een betere dekking van de sfeer.
- Er wordt een multi-level structuur (vergelijkbaar met Product Quantization) gebruikt om de ruimte te partitioneren, wat de referentiehoek verder verkleint en de afweging tussen indexgrootte en zoeknauwkeurigheid regelt.
Twee Specifieke Toepassingen
- $K^1_S$ (Voor vergelijking): Ontworpen voor taken zoals Maximum Inner Product Search (MIPS). Het verbetert de bestaande "CEOs"-techniek door de projectievectoren te vervangen door de geoptimaliseerde structuren ( $S_{sym}$ of $S_{pol}$ ).
- $K^2_S$ (Voor drempeltest): Ontworpen voor probabilistische routing in graf-gebaseerde zoekalgoritmen. Het introduceert de KS2-test, die bepaalt of een buurknooppunt in een similariteitsgraf verder moet worden onderzocht zonder de exacte afstand te berekenen.

Belangrijkste Bijdragen

Nieuwe Theoretische Kaders: De paper levert een strikte theoretische analyse die aantoont dat de nieuwe kernel-functies geldige probabilistische garanties bieden zonder asymptotische aannames. De relatie tussen hoek en projectiewaarde is deterministisch en afhankelijk van de referentiehoek.
Optimalisatie van Projectiestructuren: Het paper toont aan dat Gaussische verdelingen suboptimaal zijn voor dit doel en stelt twee nieuwe, deterministische structuren (antipodale en kruispolytope) voor die de referentiehoek minimaliseren.
KS1 en KS2: De implementatie van twee nieuwe technieken:
- KS1: Een verbeterde projectie-techniek voor MIPS en filtering.
- KS2: Een nieuwe routing-test voor graf-gebaseerde ANNS die complexer is dan bestaande methoden (zoals PEOs) maar eenvoudiger in berekening en opslag.
Open Source: De code en data zijn beschikbaar gesteld.

Resultaten

De auteurs hebben hun methoden geëvalueerd op zes real-world datasets (o.a. SIFT, GIST, GloVe, Word) en vergeleken met state-of-the-art methoden zoals HNSW, ScaNN, en HNSW+PEOs.

Verbetering in Doorvoer (Throughput): De combinatie HNSW+KS2 bereikt een 2,5x tot 3x hogere query-per-second (QPS) doorvoer vergeleken met de standaard HNSW.
Vergelijking met SOTA: HNSW+KS2 is 10% tot 30% sneller dan de huidige state-of-the-art HNSW+PEOs, terwijl het tegelijkertijd de indexgrootte met ongeveer 5% verkleint (door minder opslag van constanten).
Nauwkeurigheid: Voor de vergelijkingstaken (KS1 vs. CEOs) wordt een lichte maar consistente verbetering in recall-rate gezien (tot 0,8%), wat bevestigt dat kleinere referentiehoeken leiden tot betere schattingen.
Efficiëntie: De KS2-test is rekenkundig eenvoudiger dan de PEOs-test en vereist minder opslagruimte voor de index.

Significantie

Deze paper is significant omdat het een fundamentele beperking van bestaande probabilistische projectiemethoden (de afhankelijkheid van asymptotische limieten) oplost. Door over te stappen van willekeurige Gaussische vectoren naar een gestructureerde, referentiehoek-gebaseerde benadering, biedt het:

Theoretische Robuustheid: Resultaten zijn geldig voor een eindig aantal projectievectoren.
Praktische Prestaties: Een aanzienlijke versnelling van de meest gebruikte zoekalgoritmen (HNSW) zonder in te leveren op nauwkeurigheid, wat cruciaal is voor real-time applicaties zoals aanbevelingssystemen en RAG (Retrieval-Augmented Generation).
Efficiëntie: Het biedt een nieuwe route voor het ontwerpen van snellere en compacter indices voor hoge-dimensionale data.

Kortom, het paper introduceert een nieuwe generatie van probabilistische kernel-functies die zowel theoretisch superieur als praktisch effectiever zijn dan de huidige stand van de techniek in het domein van vector-similairheidszoekopdrachten.