Mitt navn er Pavel Parkhomenko, jeg er en ML-utvikler. I denne artikkelen vil jeg snakke om strukturen til Yandex.Zen-tjenesten og dele tekniske forbedringer, hvis implementering har gjort det mulig å øke kvaliteten på anbefalingene. Fra dette innlegget lærer du hvordan du finner de mest relevante for brukeren blant millioner av dokumenter på bare noen få millisekunder; hvordan gjøre kontinuerlig dekomponering av en stor matrise (bestående av millioner av kolonner og titalls millioner rader) slik at nye dokumenter mottar sin vektor i løpet av titalls minutter; hvordan gjenbruke brukerartikkelmatrisedekomponeringen for å få en god vektorrepresentasjon for video.
Vår anbefalingdatabase inneholder millioner av dokumenter i ulike formater: tekstartikler laget på plattformen vår og hentet fra eksterne nettsteder, videoer, fortellinger og korte innlegg. Utviklingen av en slik tjeneste er forbundet med en lang rekke tekniske utfordringer. Her er noen av dem:
- Del opp databehandlingsoppgaver: gjør alle tunge operasjoner offline, og utfør kun rask bruk av modeller i sanntid for å være ansvarlig for 100-200 ms.
- Ta raskt hensyn til brukerhandlinger. For å gjøre dette er det nødvendig at alle hendelser umiddelbart leveres til anbefaleren og påvirker resultatene av modellene.
- Lag feeden slik at den for nye brukere raskt tilpasser seg oppførselen deres. Folk som nettopp har sluttet seg til systemet bør føle at tilbakemeldingene deres påvirker anbefalinger.
- Forstå raskt hvem du skal anbefale en ny artikkel til.
- Reager raskt på den konstante fremveksten av nytt innhold. Titusenvis av artikler publiseres hver dag, og mange av dem har begrenset levetid (f.eks. nyheter). Det er dette som skiller dem fra filmer, musikk og annet langvarig og dyrt innhold å lage.
- Overfør kunnskap fra ett domeneområde til et annet. Hvis et anbefalingssystem har opplærte modeller for tekstartikler og vi legger til video, kan vi gjenbruke de eksisterende modellene slik at den nye typen innhold rangeres bedre.
Jeg vil fortelle deg hvordan vi løste disse problemene.
Valg av kandidater
Hvordan redusere antall dokumenter som vurderes med tusenvis av ganger på noen få millisekunder, med praktisk talt ingen forringelse av kvaliteten på rangeringen?
Anta at vi trente mange ML-modeller, genererte funksjoner basert på dem, og trente en annen modell som rangerer dokumenter for brukeren. Alt ville være bra, men du kan ikke bare ta og beregne alle tegnene for alle dokumenter i sanntid, hvis det er millioner av disse dokumentene, og anbefalinger må bygges på 100-200 ms. Oppgaven er å velge en viss delmengde fra millioner, som vil bli rangert for brukeren. Dette stadiet kalles vanligvis kandidatutvelgelse. Det er flere krav til det. For det første må utvelgelsen skje veldig raskt, slik at mest mulig tid er igjen til selve rangeringen. For det andre, etter å ha redusert antall dokumenter for rangering kraftig, må vi bevare dokumenter som er relevante for brukeren så fullstendig som mulig.
Prinsippet vårt for kandidatutvelgelse har utviklet seg, og for øyeblikket har vi kommet frem til en flertrinnsordning:
Først er alle dokumenter delt inn i grupper, og de mest populære dokumentene hentes fra hver gruppe. Grupper kan være nettsteder, emner, klynger. For hver bruker, basert på hans historie, velges gruppene nærmest ham og de beste dokumentene hentes fra dem. Vi bruker også kNN-indeksen til å velge dokumenter som er nærmest brukeren i sanntid. Det finnes flere metoder for å konstruere en kNN-indeks; vår fungerte best (Hierarkiske navigerbare små verden-grafer). Dette er en hierarkisk modell som lar deg finne de N nærmeste vektorene for en bruker fra en database på millioner på noen få millisekunder. Vi indekserer først hele dokumentdatabasen vår offline. Siden søk i indeksen fungerer ganske raskt, hvis det er flere sterke innebygginger, kan du opprette flere indekser (en indeks for hver innbygging) og få tilgang til hver av dem i sanntid.
Vi har fortsatt titusenvis av dokumenter for hver bruker. Dette er fortsatt mye å telle alle funksjonene, så på dette stadiet bruker vi lett rangering - en lettvekts tung rangeringsmodell med færre funksjoner. Oppgaven er å forutsi hvilke dokumenter en tung modell vil ha i toppen. Dokumenter med den høyeste prediktoren vil bli brukt i den tunge modellen, det vil si på siste trinn i rangeringen. Denne tilnærmingen lar deg redusere databasen med dokumenter som vurderes for brukeren fra millioner til tusenvis på titalls millisekunder.
ALS trinn i kjøretid
Hvordan ta hensyn til tilbakemeldinger fra brukere umiddelbart etter et klikk?
En viktig faktor i anbefalinger er responstiden på tilbakemeldinger fra brukere. Dette er spesielt viktig for nye brukere: når en person nettopp begynner å bruke anbefalingssystemet, mottar han en ikke-personlig feed med dokumenter om forskjellige emner. Så snart han gjør det første klikket, må du umiddelbart ta hensyn til dette og tilpasse deg hans interesser. Hvis du beregner alle faktorene offline, vil en rask systemrespons bli umulig på grunn av forsinkelsen. Så det er nødvendig å behandle brukerhandlinger i sanntid. For disse formålene bruker vi ALS-trinnet ved kjøretid for å bygge en vektorrepresentasjon av brukeren.
La oss anta at vi har en vektorrepresentasjon for alle dokumenter. For eksempel kan vi bygge embeddings offline basert på teksten i en artikkel ved å bruke ELMo, BERT eller andre maskinlæringsmodeller. Hvordan kan vi få en vektorrepresentasjon av brukere i samme rom basert på deres interaksjoner i systemet?
Generelt prinsipp for dannelse og dekomponering av brukerdokumentmatrisenLa oss ha m brukere og n dokumenter. For noen brukere er deres forhold til visse dokumenter kjent. Da kan denne informasjonen representeres som en mxn-matrise: rader tilsvarer brukere, og kolonner tilsvarer dokumenter. Siden personen ikke har sett de fleste dokumentene, vil de fleste matrisecellene forbli tomme, mens andre vil bli fylt. For hver hendelse (liker, misliker, klikk) er det gitt en verdi i matrisen - men la oss vurdere en forenklet modell der et like tilsvarer 1, og en misliker tilsvarer -1.
La oss dekomponere matrisen i to: P (mxd) og Q (dxn), der d er dimensjonen til vektorrepresentasjonen (vanligvis et lite tall). Da vil hvert objekt tilsvare en d-dimensjonal vektor (for en bruker - en rad i matrisen P, for et dokument - en kolonne i matrisen Q). Disse vektorene vil være innebyggingen av de tilsvarende objektene. For å forutsi om en bruker vil like et dokument, kan du ganske enkelt multiplisere innebyggingene deres.
En av de mulige måtene å dekomponere en matrise på er ALS (Alternating Least Squares). Vi vil optimere følgende tapsfunksjon:
Her er rui interaksjonen mellom bruker u og dokument i, qi er vektoren til dokument i, pu er vektoren til bruker u.
Deretter finner man den optimale brukervektoren med tanke på middelkvadratfeilen (for faste dokumentvektorer) analytisk ved å løse den tilsvarende lineære regresjonen.
Dette kalles "ALS-trinnet". Og selve ALS-algoritmen er at vi vekselvis fikser en av matrisene (brukere og artikler) og oppdaterer den andre, og finner den optimale løsningen.
Heldigvis er det å finne brukerens vektorrepresentasjon en ganske rask operasjon som kan gjøres under kjøring ved hjelp av vektorinstruksjoner. Dette trikset lar deg umiddelbart ta brukertilbakemeldinger i betraktning i rangeringen. Den samme innebyggingen kan brukes i kNN-indeksen for å forbedre kandidatutvelgelsen.
Distribuert samarbeidsfiltrering
Hvordan gjøre inkrementell distribuert matrisefaktorisering og raskt finne vektorrepresentasjoner av nye artikler?
Innhold er ikke den eneste kilden til anbefalingssignaler. En annen viktig kilde er samarbeidsinformasjon. Gode rangeringsfunksjoner kan tradisjonelt oppnås fra dekomponeringen av brukerdokumentmatrisen. Men når vi prøvde å gjøre en slik dekomponering, møtte vi problemer:
1. Vi har millioner av dokumenter og titalls millioner brukere. Matrisen passer ikke helt på én maskin, og nedbrytning vil ta svært lang tid.
2. Det meste av innholdet i systemet har kort levetid: dokumenter forblir relevante i bare noen få timer. Derfor er det nødvendig å konstruere deres vektorrepresentasjon så raskt som mulig.
3. Hvis du bygger en dekomponering umiddelbart etter at dokumentet er publisert, vil et tilstrekkelig antall brukere ikke ha tid til å evaluere det. Derfor vil vektorrepresentasjonen mest sannsynlig ikke være særlig god.
4. Hvis en bruker liker eller misliker, vil vi ikke umiddelbart kunne ta hensyn til dette i dekomponeringen.
For å løse disse problemene implementerte vi en distribuert dekomponering av brukerdokumentmatrisen med hyppige inkrementelle oppdateringer. Hvordan fungerer det egentlig?
Anta at vi har en klynge av N maskiner (N er i hundrevis) og vi ønsker å gjøre en distribuert dekomponering av en matrise på dem som ikke passer på én maskin. Spørsmålet er hvordan man utfører denne dekomponeringen slik at det på den ene siden er nok data på hver maskin og på den andre slik at beregningene er uavhengige?
Vi vil bruke ALS-dekomponeringsalgoritmen beskrevet ovenfor. La oss se på hvordan du utfører ett ALS-trinn på en distribuert måte - resten av trinnene vil være like. La oss si at vi har en fast matrise av dokumenter og vi ønsker å bygge en matrise av brukere. For å gjøre dette vil vi dele den inn i N deler for linjer, hver del vil inneholde omtrent like mange linjer. Vi vil sende til hver maskin ikke-tomme celler i de tilsvarende radene, samt matrisen av dokumentinnbygging (helt). Siden størrelsen ikke er veldig stor, og brukerdokumentmatrisen vanligvis er veldig sparsom, vil disse dataene passe på en vanlig maskin.
Dette trikset kan gjentas over flere epoker til modellen konvergerer, og alternerer den faste matrisen én etter én. Men selv da kan matrisenedbrytning ta flere timer. Og dette løser ikke problemet med at du raskt trenger å motta innebygginger av nye dokumenter og oppdatere innebyggingene til de som det var lite informasjon om når du bygde modellen.
Innføringen av raske inkrementelle modelloppdateringer hjalp oss. La oss si at vi har en for tiden trent modell. Siden opplæringen hennes har det kommet nye artikler som brukerne våre har interagert med, samt artikler som har hatt lite interaksjon under treningen. For raskt å få tak i innbygginger av slike artikler, bruker vi brukerinnbyggingene som ble oppnådd under den første store opplæringen av modellen og gjør ett ALS-trinn for å beregne dokumentmatrisen gitt en fast brukermatrise. Dette gjør at du kan motta innbygginger ganske raskt - i løpet av få minutter etter at dokumentet er publisert - og ofte oppdatere innbygginger av nyere dokumenter.
For å gi anbefalinger umiddelbart ta hensyn til menneskelige handlinger, i løpet av kjøretiden bruker vi ikke brukerinnbygginger hentet offline. I stedet gjør vi et ALS-trinn og får den faktiske brukervektoren.
Overfør til et annet domeneområde
Hvordan bruke tilbakemeldinger fra brukere på tekstartikler for å bygge en vektorrepresentasjon av en video?
I utgangspunktet anbefalte vi kun tekstartikler, så mange av algoritmene våre er skreddersydd for denne typen innhold. Men når vi la til andre typer innhold, ble vi møtt med behovet for å tilpasse modellene. Hvordan løste vi dette problemet ved å bruke et videoeksempel? Et alternativ er å omskolere alle modellene fra bunnen av. Men dette tar lang tid, og noen av algoritmene krever størrelsen på treningsutvalget, som ennå ikke er tilgjengelig i nødvendig mengde for en ny type innhold i de første øyeblikkene av livet på tjenesten.
Vi gikk den andre veien og gjenbrukte tekstmodellene til videoen. Det samme ALS-trikset hjalp oss med å lage vektorrepresentasjoner av videoer. Vi tok en vektorrepresentasjon av brukere basert på tekstartikler og gjorde et ALS-trinn ved å bruke videovisningsinformasjon. Så vi fikk enkelt en vektorrepresentasjon av videoen. Og ved kjøretid beregner vi ganske enkelt nærheten mellom brukervektoren hentet fra tekstartikler og videovektoren.
Konklusjon
Å utvikle kjernen i et sanntidsanbefalingssystem innebærer mange utfordringer. Du må raskt behandle data og bruke ML-metoder for å effektivt bruke disse dataene; bygge komplekse distribuerte systemer som er i stand til å behandle brukersignaler og nye innholdsenheter på minimum tid; og mange andre oppgaver.
I det nåværende systemet, hvis utforming jeg beskrev, vokser kvaliteten på anbefalingene for brukeren sammen med hans aktivitet og oppholdstid på tjenesten. Men selvfølgelig, her ligger hovedproblemet: det er vanskelig for systemet å umiddelbart forstå interessene til en person som har lite interaksjon med innholdet. Å forbedre anbefalinger for nye brukere er vårt hovedmål. Vi vil fortsette å optimalisere algoritmene slik at innhold som er relevant for en person kommer raskere inn i feeden hans, og irrelevant innhold ikke vises.
Kilde: www.habr.com