Mit navn er Pavel Parkhomenko, jeg er ML-udvikler. I denne artikel vil jeg gerne tale om strukturen af Yandex.Zen-tjenesten og dele tekniske forbedringer, hvis implementering har gjort det muligt at øge kvaliteten af anbefalingerne. Fra dette indlæg lærer du, hvordan du finder de mest relevante for brugeren blandt millioner af dokumenter på få millisekunder; hvordan man laver en kontinuerlig nedbrydning af en stor matrix (bestående af millioner af kolonner og titusinder af rækker), så nye dokumenter modtager deres vektor på ti minutter; hvordan man genbruger brugerartikel-matrix-nedbrydningen for at få en god vektorrepræsentation til video.
Vores anbefalingsdatabase indeholder millioner af dokumenter i forskellige formater: tekstartikler oprettet på vores platform og taget fra eksterne websteder, videoer, fortællinger og korte indlæg. Udviklingen af en sådan service er forbundet med en lang række tekniske udfordringer. Her er nogle af dem:
- Opdel computeropgaver: lav alle tunge operationer offline, og udfør kun hurtig anvendelse af modeller i realtid for at være ansvarlig for 100-200 ms.
- Tag hurtigt hensyn til brugerhandlinger. For at gøre dette er det nødvendigt, at alle hændelser øjeblikkeligt leveres til anbefaleren og påvirker resultaterne af modellerne.
- Lav feedet, så det for nye brugere hurtigt tilpasser sig deres adfærd. Folk, der lige har tilsluttet sig systemet, bør føle, at deres feedback påvirker anbefalinger.
- Forstå hurtigt, hvem du skal anbefale en ny artikel til.
- Reager hurtigt på den konstante fremkomst af nyt indhold. Titusindvis af artikler udgives hver dag, og mange af dem har en begrænset levetid (f.eks. nyheder). Det er det, der adskiller dem fra film, musik og andet langlivet og dyrt indhold at skabe.
- Overfør viden fra et domæneområde til et andet. Hvis et anbefalingssystem har trænede modeller til tekstartikler, og vi tilføjer video til det, kan vi genbruge de eksisterende modeller, så den nye type indhold rangerer bedre.
Jeg vil fortælle dig, hvordan vi løste disse problemer.
Udvælgelse af kandidater
Hvordan reducerer man antallet af dokumenter, der er under overvejelse, tusindvis af gange på få millisekunder, uden praktisk talt nogen forringelse af kvaliteten af rangeringen?
Antag, at vi trænede mange ML-modeller, genererede funktioner baseret på dem og trænede en anden model, der rangerer dokumenter for brugeren. Alt ville være fint, men du kan ikke bare tage og beregne alle tegnene for alle dokumenter i realtid, hvis der er millioner af disse dokumenter, og anbefalinger skal bygges på 100-200 ms. Opgaven er at vælge en bestemt delmængde blandt millioner, som vil blive rangeret for brugeren. Denne fase kaldes normalt kandidatudvælgelse. Der er flere krav til det. For det første skal udvælgelsen ske meget hurtigt, så der er så meget tid som muligt tilbage til selve rangeringen. For det andet, efter at have reduceret antallet af dokumenter til rangering kraftigt, skal vi bevare dokumenter, der er relevante for brugeren, så fuldstændigt som muligt.
Vores princip om kandidatudvælgelse har udviklet sig, og i øjeblikket er vi nået frem til en flertrinsordning:
Først er alle dokumenter opdelt i grupper, og de mest populære dokumenter tages fra hver gruppe. Grupper kan være websteder, emner, klynger. For hver bruger udvælges de grupper, der er tættest på ham, baseret på hans historie, og de bedste dokumenter tages fra dem. Vi bruger også kNN-indekset til at udvælge dokumenter, der er tættest på brugeren i realtid. Der er flere metoder til at konstruere et kNN-indeks; vores fungerede bedst (Hierarkiske Navigable Small World-grafer). Dette er en hierarkisk model, der giver dig mulighed for at finde de N nærmeste vektorer for en bruger fra en database med millioner på få millisekunder. Vi indekserer først hele vores dokumentdatabase offline. Da søgning i indekset fungerer ret hurtigt, kan du, hvis der er flere stærke indlejringer, oprette flere indekser (et indeks for hver indlejring) og få adgang til hver af dem i realtid.
Vi har stadig titusindvis af dokumenter for hver bruger. Dette er stadig meget at tælle alle funktionerne, så på dette stadie bruger vi light ranking - en letvægts tung ranking model med færre funktioner. Opgaven er at forudsige, hvilke dokumenter en tung model vil have i toppen. Dokumenter med den højeste prædiktor vil blive brugt i den tunge model, det vil sige på den sidste fase af rangeringen. Denne tilgang giver dig mulighed for at reducere databasen med dokumenter, der tages i betragtning for brugeren, fra millioner til tusinder på titusinder af millisekunder.
ALS trin i runtime
Hvordan tager man højde for brugerfeedback umiddelbart efter et klik?
En vigtig faktor i anbefalinger er responstiden på brugerfeedback. Dette er især vigtigt for nye brugere: Når en person lige begynder at bruge anbefalingssystemet, modtager han et ikke-personligt feed med dokumenter om forskellige emner. Så snart han laver det første klik, skal du straks tage højde for dette og tilpasse dig hans interesser. Hvis du beregner alle faktorerne offline, bliver en hurtig systemrespons umulig på grund af forsinkelsen. Så det er nødvendigt at behandle brugerhandlinger i realtid. Til disse formål bruger vi ALS-trinnet ved kørsel til at bygge en vektorrepræsentation af brugeren.
Lad os antage, at vi har en vektorrepræsentation for alle dokumenter. For eksempel kan vi bygge indlejringer offline baseret på teksten i en artikel ved hjælp af ELMo, BERT eller andre maskinlæringsmodeller. Hvordan kan vi opnå en vektorrepræsentation af brugere i samme rum baseret på deres interaktioner i systemet?
Generelt princip for dannelse og nedbrydning af brugerdokumentmatricenLad os have m brugere og n dokumenter. For nogle brugere er deres forhold til visse dokumenter kendt. Så kan denne information repræsenteres som en mxn-matrix: rækker svarer til brugere, og kolonner svarer til dokumenter. Da personen ikke har set de fleste dokumenter, vil de fleste af matrixcellerne forblive tomme, mens andre vil blive udfyldt. For hver begivenhed (like, dislike, click) er der angivet en værdi i matrixen - men lad os overveje en forenklet model, hvor et like svarer til 1, og et dislike svarer til -1.
Lad os dekomponere matricen i to: P (mxd) og Q (dxn), hvor d er dimensionen af vektorrepræsentationen (normalt et lille tal). Så vil hvert objekt svare til en d-dimensionel vektor (for en bruger - en række i matrixen P, for et dokument - en kolonne i matrixen Q). Disse vektorer vil være indlejring af de tilsvarende objekter. For at forudsige, om en bruger vil kunne lide et dokument, kan du blot multiplicere deres indlejringer.
En af de mulige måder at dekomponere en matrix på er ALS (Alternating Least Squares). Vi vil optimere følgende tabsfunktion:
Her er rui interaktionen mellem bruger u og dokument i, qi er vektoren af dokument i, pu er vektoren af bruger u.
Derefter findes den optimale brugervektor ud fra den gennemsnitlige kvadratiske fejl (for faste dokumentvektorer) analytisk ved at løse den tilsvarende lineære regression.
Dette kaldes "ALS-trinnet". Og selve ALS-algoritmen er, at vi skiftevis fikser en af matricerne (brugere og artikler) og opdaterer den anden, så vi finder den optimale løsning.
Heldigvis er det en ret hurtig operation at finde brugerens vektorrepræsentation, som kan udføres under kørsel ved hjælp af vektorinstruktioner. Dette trick giver dig mulighed for straks at tage brugerfeedback i betragtning i rangeringen. Den samme indlejring kan bruges i kNN-indekset for at forbedre kandidatudvælgelsen.
Distribueret kollaborativ filtrering
Hvordan laver man inkrementel distribueret matrixfaktorisering og hurtigt finder vektorrepræsentationer af nye artikler?
Indhold er ikke den eneste kilde til anbefalingssignaler. En anden vigtig kilde er samarbejdsinformation. Gode rangeringsfunktioner kan traditionelt opnås fra dekomponeringen af brugerdokumentmatrixen. Men da vi forsøgte at lave en sådan nedbrydning, stødte vi på problemer:
1. Vi har millioner af dokumenter og titusinder af brugere. Matrixen passer ikke helt på én maskine, og nedbrydning vil tage meget lang tid.
2. Det meste af indholdet i systemet har en kort levetid: Dokumenter forbliver kun relevante i et par timer. Derfor er det nødvendigt at konstruere deres vektorrepræsentation så hurtigt som muligt.
3. Hvis du opbygger en nedbrydning umiddelbart efter, at dokumentet er offentliggjort, vil et tilstrækkeligt antal brugere ikke have tid til at evaluere det. Derfor vil dens vektorrepræsentation højst sandsynligt ikke være særlig god.
4. Hvis en bruger kan lide eller ikke lide, vil vi ikke umiddelbart kunne tage højde for dette i nedbrydningen.
For at løse disse problemer implementerede vi en distribueret dekomponering af brugerdokumentmatricen med hyppige trinvise opdateringer. Hvordan virker det helt præcist?
Antag, at vi har en klynge af N maskiner (N er i hundredvis), og vi vil lave en distribueret dekomponering af en matrix på dem, som ikke passer på én maskine. Spørgsmålet er, hvordan man udfører denne dekomponering, så der på den ene side er nok data på hver maskine og på den anden side, så beregningerne er uafhængige?
Vi vil bruge ALS-nedbrydningsalgoritmen beskrevet ovenfor. Lad os se på, hvordan man udfører et ALS-trin på en distribueret måde - resten af trinene vil ligne hinanden. Lad os sige, at vi har en fast matrix af dokumenter, og vi vil bygge en matrix af brugere. For at gøre dette vil vi opdele det i N dele for linjer, hver del vil indeholde omtrent det samme antal linjer. Vi sender til hver maskine ikke-tomme celler i de tilsvarende rækker, såvel som matrixen af dokumentindlejringer (helt). Da dens størrelse ikke er særlig stor, og brugerdokumentmatrixen normalt er meget sparsom, vil disse data passe på en almindelig maskine.
Dette trick kan gentages over flere epoker, indtil modellen konvergerer, alternerende den faste matrix én efter én. Men selv da kan matrixnedbrydning tage flere timer. Og dette løser ikke problemet med, at du hurtigt skal modtage indlejringer af nye dokumenter og opdatere indlejringerne af dem, som der var lidt information om, når du bygger modellen.
Introduktionen af hurtige trinvise modelopdateringer hjalp os. Lad os sige, at vi har en i øjeblikket uddannet model. Siden hendes uddannelse er der kommet nye artikler, som vores brugere har interageret med, samt artikler, der havde lidt interaktion under træningen. For hurtigt at få indlejringer af sådanne artikler, bruger vi brugerindlejringer opnået under den første store træning af modellen og laver et ALS-trin for at beregne dokumentmatricen givet en fast brugermatrix. Dette giver dig mulighed for ret hurtigt at modtage indlejringer - inden for få minutter efter, at dokumentet er publiceret - og ofte opdatere indlejringer af nyere dokumenter.
For at komme med anbefalinger straks tage hensyn til menneskelige handlinger, i runtime bruger vi ikke brugerindlejringer opnået offline. I stedet laver vi et ALS-trin og får den faktiske brugervektor.
Overfør til et andet domæneområde
Hvordan bruger man brugerfeedback på tekstartikler til at bygge en vektorrepræsentation af en video?
I starten anbefalede vi kun tekstartikler, så mange af vores algoritmer er skræddersyet til denne type indhold. Men da vi tilføjede andre typer indhold, stod vi over for behovet for at tilpasse modellerne. Hvordan løste vi dette problem ved hjælp af et videoeksempel? En mulighed er at omskole alle modeller fra bunden. Men dette tager lang tid, og nogle af algoritmerne stiller krav til størrelsen af træningsprøven, som endnu ikke er tilgængelig i den nødvendige mængde til en ny type indhold i de første øjeblikke af dens liv på tjenesten.
Vi gik den anden vej og genbrugte tekstmodellerne til videoen. Det samme ALS-trick hjalp os med at skabe vektorrepræsentationer af videoer. Vi tog en vektorrepræsentation af brugere baseret på tekstartikler og udførte et ALS-trin ved hjælp af videovisningsoplysninger. Så vi fik nemt en vektorrepræsentation af videoen. Og ved runtime beregner vi simpelthen nærheden mellem brugervektoren opnået fra tekstartikler og videovektoren.
Konklusion
At udvikle kernen i et realtidsanbefalingssystem indebærer mange udfordringer. Du skal hurtigt behandle data og anvende ML-metoder for effektivt at bruge disse data; bygge komplekse distribuerede systemer, der er i stand til at behandle brugersignaler og nye indholdsenheder på et minimumstidspunkt; og mange andre opgaver.
I det nuværende system, hvis design jeg beskrev, vokser kvaliteten af anbefalinger til brugeren sammen med hans aktivitet og varighed af ophold på tjenesten. Men her ligger selvfølgelig hovedvanskeligheden: det er svært for systemet umiddelbart at forstå interesserne hos en person, der har lidt interaktion med indholdet. At forbedre anbefalinger til nye brugere er vores vigtigste mål. Vi vil fortsætte med at optimere algoritmerne, så indhold, der er relevant for en person, kommer hurtigere ind i hans feed, og irrelevant indhold ikke vises.
Kilde: www.habr.com