📊 statistics

Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval

Het artikel introduceert DINOSAUR, een framework dat embedding-onzekerheid integreert in approximate nearest neighbor search door meerdere embeddings te samplen voor zowel gebruikers als items, waardoor de retrieval van diverse long-tail content wordt verbeterend terwijl de compatibiliteit met bestaande infrastructuur behouden blijft en recall-verlies wordt geminimaliseerd.

Oorspronkelijke auteurs: Olivier Jeunen

Gepubliceerd 2026-06-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Olivier Jeunen

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

Stel je voor dat je door een enorme bibliotheek loopt met miljoenen boeken. Je wilt het perfecte boek vinden voor je huidige stemming. In een modern aanbevelingssysteem is deze bibliotheek beheerd door een robot-bibliothecaris die een speciale kaart gebruikt om boeken te vinden die lijken op wat je eerder leuk vond.

Het Probleem: De "Perfecte" Kaart is Te Rigide

Momenteel behandelt de robot-bibliothecaris elk boek en elke lezer als een enkel, vast punt op een kaart.

De Populaire Boeken: Denk aan bestsellers zoals Harry Potter. De bibliothecaris heeft ze duizenden keren gezien. Hun locatie op de kaart is kristalhelder en precies.
De Niche Boeken: Denk nu aan een obscure, zelfgepubliceerde roman over een specifiek type paddenstoel. De bibliothecaris heeft deze slechts een handvol keren gezien. Omdat de data schaars is, is de bibliothecaris eigenlijk vrij onzeker over waar dit boek "echt" thuishoort op de kaart.

De Fout: Omdat de robot geprogrammeerd is om rigide te zijn, kiest hij alleen de boeken die exact het dichtst bij jouw locatie liggen. Als dat obscure paddenstoelenboek zelfs maar iets uit het midden ligt door de onzekerheid van de bibliothecaris, wordt het voor altijd genegeerd. Dit creëert een systeem waarin alleen de beroemde, populaire items worden aanbevolen, terwijl unieke, niche of "long-tail" content wordt verstikt.

De Oplossing: Maak kennis met "Dinosaur"

Het paper stelt een nieuwe methode voor genaamd dinosaur (Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval).

In plaats van een boek te behandelen als een enkel stipje op de kaart, behandelt dinosaur een onzeker boek als een wolk van mogelijkheden.

De Creatieve Analogie: De "Vage Wolk" versus de "Scherpe Stip"

De Oude Manier (Punt-schatting): Stel je voor dat de bibliothecaris de locatie van het paddenstoelenboek markeert met een piepkleine, scherpe speld. Als jouw verzoek zelfs maar een millimeter naast die speld landt, wordt het boek afgewezen.
De Dinosaur-manier (Distributional): Stel je voor dat de bibliothecaris beseft: "Ik weet niet 100% zeker waar dit paddenstoelenboek thuishoort." Dus, in plaats van één speld, laat hij een vage wolk van pennen rond dat algemene gebied achter.
- Voor een populaire bestseller is de wolk klein en compact (omdat de bibliothecaris heel zeker is).
- Voor een niche boek is de wolk groot en verspreid (omdat de bibliothecaris onzeker is).

Wanneer je om een aanbeveling vraagt, controleert de robot niet slechts één plek; hij controleert of jouw verzoek ergens binnen die vage wolken landt. Omdat het niche boek een grotere wolk heeft, heeft het een veel grotere kans om "geraakt" te worden en in jouw lijst opgenomen te worden, zelfs als de bibliothecaris niet precies weet waar het thuishoort.

Hoe het in de praktijk werkt

Het paper legt uit dat dit geen nieuwe bibliotheek vereist of het brein van de robot verandert. Het is een slimme truc:

Sampling: Voordat je arriveert, neemt het systeem de "vage wolk" van het niche boek en maakt er verschillende kopieën van die verspreid over de kaart liggen.
Searching: Wanneer je zoekt, kijkt het systeem naar de dichtstbijzijnde kopieën.
Deductie: Als het drie kopieën van hetzelfde paddenstoelenboek vindt, telt het dit gewoon als één aanbeveling.

Dit is als het uitwerpen van een breder net. Je hebt een grotere kans om de zeldzame vissen (niche items) te vangen zonder de veelvoorkomende vissen (populaire items) te verliezen.

De Resultaten: Meer Variëteit, Bijna Geen Kosten

De auteurs testten dit op een enorme dataset van film-aanbevelingen (MovieLens).

De Trade-off: Meestal, als je probeert meer variëteit te tonen, kun je per ongeluk dingen aan mensen laten zien die ze niet leuk vinden, waardoor je "nauwkeurigheidsscore" daalt.
De Dinosaur-bevinding: Het paper laat zien dat door deze vage wolken te gebruiken, ze de variëteit van de getoonde films aan gebruikers konden verdrievoudigen (de "catalogue coverage" verhogen van ~23% naar ~63%).
De Catch: De "nauwkeurigheid" (hoe vaak ze een film kozen die de gebruiker daadwerkelijk leuk vond) daalde met een minimaal, bijna onzichtbaar beetje (minder dan 0,5%).

Waarom dit ertoe doet

Het paper betoogt dat dit een eerlijkere manier is om een marktplaats te runnen.

Voor Makers: Niche verkopers en makers krijgen een "wiskundige boost". Omdat hun items onzeker zijn, krijgen ze een grotere "wolk", wat hen een eerlijkere kans geeft om gezien te worden zonder dat ze kunstmatig door een menselijke manager hoeven te worden opgevoerd.
Voor Gebruikers: Je ontdekt serendipiteuze, unieke content die een rigide systeem zou hebben weggefilterd.

Samenvatting

Dinosaur is een eenvoudige, slimme manier om de aanbevelingsrobot te vertellen: "Als je niet zeker weet waar dit item thuishoort, negeer het dan niet. Geef het een beetje ruimte om te ademen, zodat het een kans krijgt om gevonden te worden." Het zet de onzekerheid van de robot om in een kans voor ontdekking, waardoor de "long tail" van content kan overleven zonder het systeem te breken.

Technische Samenvatting: Distributional Approximate Nearest Neighbour Search voor Onzekerheidsbewuste Retrieval (dinosaur)

1. Probleemstelling

Moderne grootschalige aanbevelingssystemen vertrouwen op Approximate Nearest Neighbour (ANN) search tijdens de kandidaatgeneratiefase, waarbij miljoenen items worden gefilterd tot een beheersbare set voor ranking. Standaardimplementaties behandelen gebruikers- en itemrepresentaties als deterministische punt-schattingen (enkele vectoren) in een gedeelde latente ruimte.

Het artikel identificeert een fundamenteel gebrek in dit paradigma:

Ingebouwde onzekerheid: Embeddings die zijn geleerd van ijle (sparse) interactiedata zijn inherent onzeker. Deze onzekerheid is tweeledig:
- Epistemische onzekerheid: Hoge variantie voor long-tail items door een gebrek aan interactiedata.
- Aleatorische onzekerheid: Informatieverlies dat inherent is aan low-rank latente factormodellen.
Systematische bias: Deterministische ANN-retrieval creëert rigide geometrische grenzen. Items met een hoge onzekerheid (typisch niche, long-tail content) waarvan de werkelijke relevantie hoog zou kunnen zijn, maar waarvan de punt-schatting van het gemiddelde net iets afwijkt, worden permanent uitgesloten van de top- $k$ kandidaten.
Gevolgen: Dit leidt tot populariteitsbias en een "rich-get-richer"-feedbackloop waarbij head-items de exposure domineren, terwijl long-tail makers en diverse content systematisch worden uitgehongerd van impressies. Bestaande oplossingen (bijv. post-hoc re-ranking of diversiteitsdoelstellingen) zijn vaak heuristisch en losgekoppeld van de kernoorzaak in de retrieval-fase.

2. Methodologie: Het `dinosaur` Framework

De auteurs stellen dinosaur voor (Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval), een framework dat de onzekerheid van embeddings direct integreert in het kandidaatgeneratieproces zonder de onderliggende ANN-infrastructuur of scoremodellen te wijzigen.

Kernmechanisme

In plaats van voor elk item $i$ een enkele punt-schatting $\mu_i$ te indexeren, behandelt dinosaur items als distributies $P(v_i)$ (gekarakteriseerd door gemiddelde $\mu_i$ en covariantie $\Sigma_i$ ).

Indexconstructie (Offline): Voor elk item $i$ trekt het systeem $S_i$ onafhankelijke samples $v_i^{(j)} \sim P(v_i)$ uit de embedding-distributie van het item. De ANN-index wordt gebouwd over deze uitgebreide set vectoren.
Query-uitvoering (Online): Tijdens de serving-tijd wordt een gebruikers-embedding $v_u$ gesampled uit de distributie van de gebruiker $P(v_u)$ . De ANN-index wordt bevraagd om de dichtstbijzijnde buren te vinden van deze gesamplede vector.
Deduplicatie: De opgehaalde vectoren worden teruggekaart naar hun oorspronkelijke item-identificatoren, en duplicaten worden verwijderd totdat precies $k$ unieke items worden geretourneerd.

Belangrijke Eigenschappen

Infrastructuur Compatibiliteit: De methode vereist geen wijzigingen in het ANN-indexalgoritme (bijv. FAISS, HNSW, ScaNN) of het scoremodel. Het vereist alleen een index die in staat is een groter aantal vectoren te verwerken.
Twee-zijdig versus Eenzijdig: Hoewel het framework sampling voor zowel gebruikers als items ondersteunt, richt het paper zich op item-zijde onzekerheid om exploratie te stimuleren. Dit is bijzonder nuttig in dynamische marktplaatsen waar real-time user sampling de latency-restricties kan schenden.
Adaptieve Sampling: Om de geheugenkosten (index-opzwelling) te beheersen, stelt het paper Adaptive Sampling voor, waarbij het sample-budget $S_i$ wordt geconditioneerd op de onzekerheid van het item. High-confidence head-items ontvangen $S_i=1$ , terwijl onzekere long-tail items $S_i > 1$ ontvangen.

Theoretische Fundamenten

Het paper biedt theoretische garanties voor het framework:

Herstel: Wanneer de embedding-variantie verdwijnt ( $\sigma^2 \to 0$ ), convergeert dinosaur naar standaard deterministische punt-schatting retrieval.
Monotone Coverage Expansie: Voor elk item buiten de deterministische top- $k$ neemt de kans op retrieval strikt toe met de variantie van de embedding. Dit garandeert wiskundig dat onzekere items een "retrieval-fase exploratiebonus" ontvangen, wat long-tail content structureel bevoordeelt zonder willekeurige ruis te injecteren.
Verbinding met Thompson Sampling: Het mechanisme is formeel gekoppeld aan Thompson Sampling, waarbij het samplen uit de posterior distributie de balans tussen exploratie en exploitatie beheert.

3. Experimentele Opzet

De auteurs evalueerden dinosaur op de MovieLens-32M dataset (32M interacties, ~200k gebruikers, ~84k items).

Baselines: Exact Inner Product Search (Flat) en Approximate Search (IVFFlat).
Onzekerheidsproxy: Omdat het basismodel (iALS) deterministisch is, hebben de auteurs een synthetische epistemische posterior geconstrueerd waarbij de standaarddeviatie $\sigma_i$ omgekeerd evenredig is aan het aantal interacties van het item ( $n_i$ ): $\sigma_i = \alpha / (1 + n_i)^\gamma$ .
Metrieken:
- Recall@K: Standaard offline utility metriek.
- Catalogue Coverage@K: Het deel van de totale catalogus dat in ten minste één top- $K$ lijst van een gebruiker verschijnt.
- Gestreifieerde Coverage: Analyse per populariteitskwintiel (B0 = meest populair, B4 = minst populair).

4. Belangrijkste Resultaten

Massale Gains in Coverage: Het verhogen van het sample-budget van $S=1$ (baseline) naar $S=5$ verdrievoudigde bijna de globale catalogus-coverage (van 23,52% naar 62,97% bij $K=1000$ ).
Verwaarloosbaar Recall Verlies: Deze expansie in coverage ging gepaard met een minimale kosten voor offline recall, met een reductie van slechts 0,0041 in Recall@1000.
Long-Tail Exposure:
- Standaard IVFFlat behaalde 0,00% coverage voor de minst populaire items (Bucket B4).
- dinosaur ( $S=5$ ) behaalde 81,88% coverage voor Bucket B4, waardoor meer dan 13% van de gebruikers aanbevelingen ontving van de meest obscure items.
Pareto Dominantie: Vergeleken met een $\epsilon$ -greedy heuristiek, domineerde dinosaur de baseline strikt, waarbij het een hogere recall behaalde voor hetzelfde deel aan exploratieve aanbevelingen over verschillende retrieval-dieptes ( $K \in \{100, 500, 1000\}$ ).

5. Betekenis en Claims

Het paper claimt dat dinosaur een geprincipieerde, infrastructuur-compatibele oplossing biedt voor de exploratie-exploitatie trade-off in retrieval.

Verschuiving van Paradigma: Het verlegt de last van het afhandelen van onzekerheid van post-hoc re-ranking of heuristische diversificatie naar de retrieval-fase zelf.
Doorbreken van Feedbackloops: Door onzekere items toe te laten in de kandidaatset, doorbreekt het de algoritmische feedbackloop waarbij deterministische policies voorkomen dat long-tail items ooit worden blootgesteld en dus nooit leren.
Praktiseerbaarheid: De methode vereist geen nieuwe hyperparameters buiten het aantal samples en werkt met bestaande, productie-waardige ANN-libraries.
Erkende Beperkingen: De auteurs merken op dat hun onzekerheidsproxy gebaseerd is op interactie-aantallen in plaats van geleerde distributies, en dat offline metrieken (Recall) vertekend zijn door Missing Not At Random (MNAR) data. Ze suggereren dat toekomstig werk de combinatie moet zoeken van propensity-aware offline evaluatie en online A/B-testen om de werkelijke impact op de marktplaats te meten.

Samenvattend demonstreert dinosaur dat het behandelen van embeddings als distributies in plaats van punten de catalogus-diversiteit en long-tail exposure aanzienlijk kan verbeteren met vrijwel geen degradatie van de standaard retrieval utility.