Hoe wij werken aan de kwaliteit en snelheid van selectie van aanbevelingen

Mijn naam is Pavel Parkhomenko, ik ben een ML-ontwikkelaar. In dit artikel wil ik het hebben over de structuur van de Yandex.Zen-service en technische verbeteringen delen, waarvan de implementatie het mogelijk heeft gemaakt om de kwaliteit van de aanbevelingen te verhogen. In dit bericht leert u hoe u in slechts enkele milliseconden de meest relevante voor de gebruiker kunt vinden tussen miljoenen documenten; hoe je een grote matrix (bestaande uit miljoenen kolommen en tientallen miljoenen rijen) continu kunt ontleden, zodat nieuwe documenten hun vector binnen tientallen minuten ontvangen; hoe je de matrixontleding van gebruikersartikelen kunt hergebruiken om een ​​goede vectorrepresentatie voor video te krijgen.

Onze aanbevelingsdatabase bevat miljoenen documenten in verschillende formaten: tekstartikelen die op ons platform zijn gemaakt en afkomstig zijn van externe sites, video's, verhalen en korte berichten. De ontwikkeling van een dergelijke dienst gaat gepaard met een groot aantal technische uitdagingen. Hier zijn er een aantal:

• Verdeel computertaken: voer alle zware handelingen offline uit en voer in realtime alleen snelle toepassing van modellen uit om verantwoordelijk te zijn voor 100-200 ms.
• Houd snel rekening met gebruikersacties. Om dit te doen is het noodzakelijk dat alle gebeurtenissen onmiddellijk aan de adviseur worden doorgegeven en de resultaten van de modellen beïnvloeden.
• Maak de feed zo dat deze zich voor nieuwe gebruikers snel aanpast aan hun gedrag. Mensen die net bij het systeem zijn aangesloten, moeten het gevoel hebben dat hun feedback de aanbevelingen beïnvloedt.
• Begrijp snel aan wie u een nieuw artikel moet aanbevelen.
• Reageer snel op de constante opkomst van nieuwe inhoud. Elke dag worden er tienduizenden artikelen gepubliceerd, en veel ervan hebben een beperkte levensduur (bijvoorbeeld nieuws). Dit is wat hen onderscheidt van films, muziek en andere langlevende en dure inhoud om te creëren.
• Breng kennis over van het ene domeingebied naar het andere. Als een aanbevelingssysteem getrainde modellen voor tekstartikelen heeft en we daar video aan toevoegen, kunnen we de bestaande modellen hergebruiken zodat het nieuwe type content beter scoort.

Ik zal je vertellen hoe we deze problemen hebben opgelost.

Selectie van kandidaten

Hoe kan het aantal onderzochte documenten in enkele milliseconden met duizenden keren worden verminderd, zonder dat dit ten koste gaat van de kwaliteit van de rangschikking?

Stel dat we veel ML-modellen hebben getraind, op basis daarvan functies hebben gegenereerd en een ander model hebben getraind dat documenten voor de gebruiker rangschikt. Alles zou in orde zijn, maar je kunt niet zomaar alle tekens voor alle documenten in realtime nemen en berekenen, als er miljoenen van deze documenten zijn en aanbevelingen binnen 100-200 ms moeten worden gebouwd. De taak is om uit miljoenen een bepaalde subset te selecteren, die voor de gebruiker wordt gerangschikt. Deze fase wordt gewoonlijk kandidatenselectie genoemd. Er zijn verschillende vereisten voor. Ten eerste moet de selectie heel snel gebeuren, zodat er zoveel mogelijk tijd overblijft voor de rangschikking zelf. Ten tweede moeten we, nu we het aantal documenten voor de rangschikking sterk hebben verminderd, de documenten die relevant zijn voor de gebruiker zo volledig mogelijk behouden.

Ons principe van kandidatenselectie is geëvolueerd en op dit moment zijn we tot een meerfasig schema gekomen:

Eerst worden alle documenten in groepen verdeeld en uit elke groep worden de populairste documenten gehaald. Groepen kunnen sites, onderwerpen of clusters zijn. Voor elke gebruiker worden op basis van zijn geschiedenis de groepen geselecteerd die het dichtst bij hem staan ​​en daaruit worden de beste documenten gehaald. Daarnaast gebruiken we de kNN-index om realtime documenten te selecteren die het dichtst bij de gebruiker staan. Er zijn verschillende methoden om een ​​kNN-index samen te stellen; de onze werkte het beste HNSW (Hierarchische navigeerbare kleine wereldgrafieken). Dit is een hiërarchisch model waarmee u in een paar milliseconden de N dichtstbijzijnde vectoren voor een gebruiker kunt vinden uit een database van miljoenen. We indexeren eerst onze volledige documentendatabase offline. Omdat het zoeken in de index vrij snel werkt, kunt u, als er meerdere sterke insluitingen zijn, meerdere indexen maken (één index voor elke insluiting) en deze in realtime openen.

We hebben nog steeds tienduizenden documenten voor elke gebruiker. Dit is nog steeds veel om alle functies te tellen, dus in dit stadium gebruiken we light ranking - een lichtgewicht zwaar rankingmodel met minder functies. De taak is om te voorspellen welke documenten een zwaar model bovenaan zal hebben. Documenten met de hoogste voorspeller zullen worden gebruikt in het zware model, dat wil zeggen in de laatste fase van de rangschikking. Met deze aanpak kunt u de database met documenten die voor de gebruiker in aanmerking komen, in tientallen milliseconden terugbrengen van miljoenen naar duizenden.

ALS-stap in runtime

Hoe kan ik direct na een klik rekening houden met gebruikersfeedback?

Een belangrijke factor bij aanbevelingen is de responstijd op feedback van gebruikers. Dit is vooral belangrijk voor nieuwe gebruikers: wanneer iemand het aanbevelingssysteem net begint te gebruiken, ontvangt hij een niet-gepersonaliseerde feed met documenten over verschillende onderwerpen. Zodra hij de eerste klik maakt, moet je hier meteen rekening mee houden en je aanpassen aan zijn interesses. Als u alle factoren offline berekent, wordt een snelle reactie van het systeem vanwege de vertraging onmogelijk. Het is dus noodzakelijk om gebruikersacties in realtime te verwerken. Voor deze doeleinden gebruiken we de ALS-stap tijdens runtime om een ​​vectorrepresentatie van de gebruiker op te bouwen.

Laten we aannemen dat we een vectorrepresentatie hebben voor alle documenten. We kunnen bijvoorbeeld offline embeddings bouwen op basis van de tekst van een artikel met behulp van ELMo, BERT of andere machine learning-modellen. Hoe kunnen we een vectorrepresentatie van gebruikers in dezelfde ruimte verkrijgen op basis van hun interacties in het systeem?

Algemeen principe van vorming en ontleding van de gebruikersdocumentmatrixLaten we m gebruikers en n documenten hebben. Voor sommige gebruikers is hun relatie tot bepaalde documenten bekend. Vervolgens kan deze informatie worden weergegeven als een mxn-matrix: rijen komen overeen met gebruikers en kolommen komen overeen met documenten. Omdat de persoon de meeste documenten niet heeft gezien, zullen de meeste matrixcellen leeg blijven, terwijl andere gevuld zullen zijn. Voor elke gebeurtenis (like, dislike, click) wordt een bepaalde waarde in de matrix gegeven - maar laten we een vereenvoudigd model bekijken waarin like overeenkomt met 1, en dislike correspondeert met -1.

Laten we de matrix in tweeën ontbinden: P (mxd) en Q (dxn), waarbij d de dimensie is van de vectorrepresentatie (meestal een klein getal). Dan komt elk object overeen met een d-dimensionale vector (voor een gebruiker - een rij in de matrix P, voor een document - een kolom in de matrix Q). Deze vectoren zullen de inbedding zijn van de overeenkomstige objecten. Om te voorspellen of een gebruiker een document leuk zal vinden, kunt u eenvoudigweg de insluitingen ervan vermenigvuldigen.

Eén van de mogelijke manieren om een ​​matrix te ontbinden is ALS (Alternating Least Squares). We zullen de volgende verliesfunctie optimaliseren:

Hier is rui de interactie van gebruiker u met document i, qi is de vector van document i, pu is de vector van gebruiker u.

Vervolgens wordt de optimale gebruikersvector vanuit het oogpunt van de gemiddelde kwadratische fout (voor vaste documentvectoren) analytisch gevonden door de overeenkomstige lineaire regressie op te lossen.

Dit wordt de "ALS-stap" genoemd. En het ALS-algoritme zelf is dat we afwisselend een van de matrices (gebruikers en artikelen) repareren en de andere bijwerken, om zo de optimale oplossing te vinden.

Gelukkig is het vinden van de vectorrepresentatie van de gebruiker een redelijk snelle handeling die tijdens runtime kan worden uitgevoerd met behulp van vectorinstructies. Met deze truc kun je meteen rekening houden met gebruikersfeedback in de ranking. Dezelfde inbedding kan in de kNN-index worden gebruikt om de kandidatenselectie te verbeteren.

Gedistribueerde samenwerkingsfiltering

Hoe kun je incrementeel gedistribueerde matrixfactorisatie uitvoeren en snel vectorrepresentaties van nieuwe artikelen vinden?

Content is niet de enige bron van aanbevelingssignalen. Een andere belangrijke bron is gezamenlijke informatie. Goede rangschikkingskenmerken kunnen traditioneel worden verkregen door de ontleding van de gebruiker-documentmatrix. Maar toen we een dergelijke ontleding probeerden uit te voeren, kwamen we problemen tegen:

1. We hebben miljoenen documenten en tientallen miljoenen gebruikers. De matrix past niet helemaal op één machine en de ontbinding zal erg lang duren.
2. Het merendeel van de content in het systeem heeft een korte levensduur: documenten blijven slechts enkele uren relevant. Daarom is het noodzakelijk om hun vectorrepresentatie zo snel mogelijk te construeren.
3. Als u onmiddellijk nadat het document is gepubliceerd een decompositie opbouwt, heeft een voldoende aantal gebruikers geen tijd om deze te evalueren. Daarom zal de vectorweergave ervan hoogstwaarschijnlijk niet erg goed zijn.
4. Als een gebruiker het leuk of niet leuk vindt, kunnen we daar bij de ontleding niet meteen rekening mee houden.

Om deze problemen op te lossen, hebben we een gedistribueerde decompositie van de gebruikersdocumentmatrix geïmplementeerd met frequente incrementele updates. Hoe werkt het precies?

Stel dat we een cluster van N machines hebben (N is in de honderden) en we willen een gedistribueerde ontleding van een matrix daarop uitvoeren die niet op één machine past. De vraag is hoe deze decompositie moet worden uitgevoerd, zodat er enerzijds voldoende gegevens op elke machine staan ​​en anderzijds zodat de berekeningen onafhankelijk zijn?

We zullen het hierboven beschreven ALS-decompositiealgoritme gebruiken. Laten we eens kijken hoe we één ALS-stap op een gedistribueerde manier kunnen uitvoeren - de rest van de stappen zullen vergelijkbaar zijn. Laten we zeggen dat we een vaste matrix van documenten hebben en dat we een matrix van gebruikers willen bouwen. Om dit te doen, verdelen we het in N delen per lijn, elk deel zal ongeveer hetzelfde aantal lijnen bevatten. We sturen naar elke machine niet-lege cellen van de overeenkomstige rijen, evenals de matrix van documentinsluitingen (geheel). Omdat de omvang niet erg groot is en de gebruikersdocumentmatrix meestal erg schaars is, passen deze gegevens op een gewone machine.

Deze truc kan over verschillende tijdperken worden herhaald totdat het model convergeert, waarbij de vaste matrix één voor één wordt afgewisseld. Maar zelfs dan kan de ontleding van de matrix enkele uren duren. En dit lost het probleem niet op dat u snel insluitingen van nieuwe documenten moet ontvangen en de insluitingen moet bijwerken van documenten waarover weinig informatie bestond bij het bouwen van het model.

De introductie van snelle incrementele modelupdates heeft ons geholpen. Laten we zeggen dat we een momenteel getraind model hebben. Sinds haar training zijn er nieuwe artikelen geweest waarmee onze gebruikers interactie hebben gehad, evenals artikelen die weinig interactie hadden tijdens de training. Om snel de insluitingen van dergelijke artikelen te verkrijgen, gebruiken we de gebruikersinsluitingen verkregen tijdens de eerste grote training van het model en voeren we één ALS-stap uit om de documentmatrix te berekenen op basis van een vaste gebruikersmatrix. Hierdoor kunt u vrij snel insluitingen ontvangen (binnen een paar minuten nadat het document is gepubliceerd) en vaak de insluitingen van recente documenten bijwerken.

Om aanbevelingen te doen, moet u onmiddellijk rekening houden met menselijke acties. In runtime gebruiken we geen offline verkregen gebruikersinsluitingen. In plaats daarvan voeren we een ALS-stap uit en verkrijgen we de daadwerkelijke gebruikersvector.

Verhuizing naar een ander domeingebied

Hoe gebruik je gebruikersfeedback op tekstartikelen om een ​​vectorrepresentatie van een video te maken?

In eerste instantie adviseerden we alleen tekstartikelen, dus veel van onze algoritmen zijn afgestemd op dit soort inhoud. Maar bij het toevoegen van andere soorten inhoud werden we geconfronteerd met de noodzaak om de modellen aan te passen. Hoe hebben we dit probleem opgelost met behulp van een videovoorbeeld? Eén optie is om alle modellen helemaal opnieuw te trainen. Maar dit duurt lang en sommige algoritmen stellen hoge eisen aan de omvang van de trainingssteekproef, die nog niet in de vereiste hoeveelheid beschikbaar is voor een nieuw type inhoud in de eerste momenten van zijn levensduur op de dienst.

We gingen de andere kant op en hergebruikten de tekstmodellen voor de video. Dezelfde ALS-truc hielp ons vectorrepresentaties van video's te maken. We hebben een vectorrepresentatie van gebruikers gemaakt op basis van tekstartikelen en een ALS-stap uitgevoerd met behulp van videoweergave-informatie. We kregen dus gemakkelijk een vectorweergave van de video. En tijdens runtime berekenen we eenvoudigweg de nabijheid tussen de gebruikersvector verkregen uit tekstartikelen en de videovector.

Conclusie

Het ontwikkelen van de kern van een realtime aanbevelingssysteem brengt veel uitdagingen met zich mee. U moet gegevens snel verwerken en ML-methoden toepassen om deze gegevens effectief te kunnen gebruiken; complexe gedistribueerde systemen bouwen die in staat zijn om gebruikerssignalen en nieuwe inhoudseenheden in een minimum van tijd te verwerken; en vele andere taken.

In het huidige systeem, waarvan ik het ontwerp heb beschreven, groeit de kwaliteit van de aanbevelingen voor de gebruiker mee met zijn activiteit en verblijfsduur op de dienst. Maar hier ligt natuurlijk de grootste moeilijkheid: het is moeilijk voor het systeem om onmiddellijk de interesses te begrijpen van iemand die weinig interactie heeft met de inhoud. Het verbeteren van de aanbevelingen voor nieuwe gebruikers is ons belangrijkste doel. We zullen de algoritmen blijven optimaliseren, zodat inhoud die voor een persoon relevant is, sneller in zijn feed terechtkomt en irrelevante inhoud niet wordt getoond.

Bron: www.habr.com