Hur vi arbetar med kvaliteten och hastigheten i urvalet av rekommendationer

Jag heter Pavel Parkhomenko, jag är en ML-utvecklare. I den här artikeln skulle jag vilja prata om strukturen för Yandex.Zen-tjänsten och dela tekniska förbättringar, vars genomförande har gjort det möjligt att öka kvaliteten på rekommendationerna. Från det här inlägget kommer du att lära dig hur du hittar de mest relevanta för användaren bland miljontals dokument på bara några millisekunder; hur man gör kontinuerlig nedbrytning av en stor matris (som består av miljoner kolumner och tiotals miljoner rader) så att nya dokument får sin vektor på tiotals minuter; hur man återanvänder användarartikelmatrisuppdelningen för att få en bra vektorrepresentation för video.

Vår rekommendationsdatabas innehåller miljontals dokument i olika format: textartiklar skapade på vår plattform och hämtade från externa webbplatser, videor, berättelser och korta inlägg. Utvecklingen av en sådan tjänst är förknippad med ett stort antal tekniska utmaningar. Här är några av dem:

• Dela upp beräkningsuppgifter: gör alla tunga operationer offline, och i realtid utför bara snabb tillämpning av modeller för att vara ansvarig för 100-200 ms.
• Ta snabbt hänsyn till användaråtgärder. För att göra detta är det nödvändigt att alla händelser omedelbart levereras till rekommenderaren och påverkar resultaten av modellerna.
• Gör flödet så att det för nya användare snabbt anpassar sig till deras beteende. Människor som precis har anslutit sig till systemet bör känna att deras feedback påverkar rekommendationer.
• Förstår snabbt vem du ska rekommendera en ny artikel till.
• Svara snabbt på den ständiga uppkomsten av nytt innehåll. Tiotusentals artiklar publiceras varje dag, och många av dem har en begränsad livslängd (säg, nyheter). Det är detta som skiljer dem från filmer, musik och annat långlivat och dyrt innehåll att skapa.
• Överför kunskap från ett domänområde till ett annat. Om ett rekommendationssystem har utbildade modeller för textartiklar och vi lägger till video till det, kan vi återanvända de befintliga modellerna så att den nya typen av innehåll rankas bättre.

Jag ska berätta hur vi löste dessa problem.

Urval av kandidater

Hur minskar man antalet övervägda dokument med tusentals gånger på några millisekunder, med praktiskt taget ingen försämring av kvaliteten på rangordningen?

Anta att vi tränade många ML-modeller, genererade funktioner baserat på dem och tränade en annan modell som rangordnar dokument för användaren. Allt skulle vara bra, men du kan inte bara ta och beräkna alla tecken för alla dokument i realtid, om det finns miljontals av dessa dokument, och rekommendationer måste byggas på 100-200 ms. Uppgiften är att välja en viss delmängd från miljoner, som kommer att rankas för användaren. Detta skede brukar kallas kandidaturval. Det finns flera krav på det. För det första måste urvalet ske mycket snabbt, så att så mycket tid som möjligt finns kvar för själva rankningen. För det andra, efter att ha minskat antalet dokument för rankning avsevärt, måste vi bevara dokument som är relevanta för användaren så fullständigt som möjligt.

Vår princip för kandidaturval har utvecklats, och för tillfället har vi kommit fram till ett flerstegsschema:

Först delas alla dokument in i grupper, och de mest populära dokumenten tas från varje grupp. Grupper kan vara webbplatser, ämnen, kluster. För varje användare, baserat på hans historik, väljs grupperna närmast honom ut och de bästa dokumenten tas från dem. Vi använder även kNN-indexet för att välja ut dokument som ligger närmast användaren i realtid. Det finns flera metoder för att konstruera ett kNN-index, vår fungerade bäst HSW (Hierarkiska navigerbara småvärldsgrafer). Detta är en hierarkisk modell som låter dig hitta de N närmaste vektorerna för en användare från en databas med miljoner på några millisekunder. Vi indexerar först hela vår dokumentdatabas offline. Eftersom sökningen i indexet fungerar ganska snabbt, om det finns flera starka inbäddningar kan du skapa flera index (ett index för varje inbäddning) och komma åt vart och ett av dem i realtid.

Vi har fortfarande tiotusentals dokument för varje användare. Detta är fortfarande mycket för att räkna alla funktioner, så i detta skede använder vi lätt ranking - en lätt tung rankingmodell med färre funktioner. Uppgiften är att förutsäga vilka dokument en tung modell kommer att ha i toppen. Dokument med den högsta prediktorn kommer att användas i den tunga modellen, det vill säga i det sista steget av rangordningen. Detta tillvägagångssätt låter dig minska databasen med dokument som anses för användaren från miljoner till tusentals på tiotals millisekunder.

ALS steg i körtid

Hur tar man hänsyn till användarfeedback direkt efter ett klick?

En viktig faktor i rekommendationer är svarstiden på användarfeedback. Detta är särskilt viktigt för nya användare: när en person precis börjar använda rekommendationssystemet får han ett icke-personifierat flöde med dokument av olika ämnen. Så fort han gör det första klicket måste du omedelbart ta hänsyn till detta och anpassa dig efter hans intressen. Om du beräknar alla faktorer offline, kommer ett snabbt systemsvar att bli omöjligt på grund av förseningen. Så det är nödvändigt att bearbeta användaråtgärder i realtid. För dessa ändamål använder vi ALS-steget vid körning för att bygga en vektorrepresentation av användaren.

Låt oss anta att vi har en vektorrepresentation för alla dokument. Till exempel kan vi bygga inbäddningar offline baserat på texten i en artikel med hjälp av ELMo, BERT eller andra maskininlärningsmodeller. Hur kan vi få en vektorrepresentation av användare i samma utrymme baserat på deras interaktioner i systemet?

Allmän princip för bildande och nedbrytning av användardokumentmatrisenLåt oss ha m användare och n dokument. För vissa användare är deras relation till vissa dokument känd. Sedan kan denna information representeras som en mxn-matris: rader motsvarar användare och kolumner motsvarar dokument. Eftersom personen inte har sett de flesta dokumenten kommer de flesta av matriscellerna att förbli tomma, medan andra kommer att fyllas. För varje händelse (gilla, ogilla, klicka) finns ett värde i matrisen - men låt oss överväga en förenklad modell där en gilla motsvarar 1 och en ogillar motsvarar -1.

Låt oss dekomponera matrisen i två: P (mxd) och Q (dxn), där d är dimensionen på vektorrepresentationen (vanligtvis ett litet tal). Då kommer varje objekt att motsvara en d-dimensionell vektor (för en användare - en rad i matrisen P, för ett dokument - en kolumn i matrisen Q). Dessa vektorer kommer att vara inbäddningar av motsvarande objekt. För att förutsäga om en användare kommer att gilla ett dokument, kan du helt enkelt multiplicera deras inbäddningar.

Ett av de möjliga sätten att dekomponera en matris är ALS (Alternating Least Squares). Vi kommer att optimera följande förlustfunktion:

Här är rui interaktionen mellan användare u och dokument i, qi är vektorn för dokument i, pu är vektorn för användare u.

Sedan hittas den optimala användarvektorn med tanke på medelkvadratfelet (för fasta dokumentvektorer) analytiskt genom att lösa motsvarande linjära regression.

Detta kallas "ALS-steget". Och själva ALS-algoritmen är att vi växelvis fixar en av matriserna (användare och artiklar) och uppdaterar den andra för att hitta den optimala lösningen.

Lyckligtvis är det en ganska snabb operation att hitta användarens vektorrepresentation som kan göras under körning med hjälp av vektorinstruktioner. Detta trick låter dig omedelbart ta hänsyn till användarfeedback i rankningen. Samma inbäddning kan användas i kNN-indexet för att förbättra kandidaturvalet.

Distribuerad kollaborativ filtrering

Hur gör man inkrementell distribuerad matrisfaktorisering och snabbt hitta vektorrepresentationer av nya artiklar?

Innehåll är inte den enda källan till rekommendationssignaler. En annan viktig källa är information om samarbete. Bra rankningsfunktioner kan traditionellt erhållas från nedbrytningen av användardokumentmatrisen. Men när vi försökte göra en sådan nedbrytning stötte vi på problem:

1. Vi har miljontals dokument och tiotals miljoner användare. Matrisen passar inte helt på en maskin, och nedbrytningen kommer att ta mycket lång tid.
2. Det mesta av innehållet i systemet har en kort livslängd: dokument förblir relevanta i bara några timmar. Därför är det nödvändigt att konstruera deras vektorrepresentation så snabbt som möjligt.
3. Om du bygger en nedbrytning direkt efter att dokumentet har publicerats kommer ett tillräckligt antal användare inte att ha tid att utvärdera det. Därför kommer dess vektorrepresentation med största sannolikhet inte att vara särskilt bra.
4. Om en användare gillar eller ogillar kommer vi inte att omedelbart kunna ta hänsyn till detta i nedbrytningen.

För att lösa dessa problem implementerade vi en distribuerad nedbrytning av användardokumentmatrisen med frekventa inkrementella uppdateringar. Hur exakt fungerar det?

Anta att vi har ett kluster av N maskiner (N är i hundratal) och vi vill göra en distribuerad nedbrytning av en matris på dem som inte passar på en maskin. Frågan är hur man utför denna nedbrytning så att det å ena sidan finns tillräckligt med data på varje maskin och å andra sidan så att beräkningarna är oberoende?

Vi kommer att använda ALS-sönderdelningsalgoritmen som beskrivs ovan. Låt oss titta på hur man utför ett ALS-steg på ett distribuerat sätt - resten av stegen kommer att vara liknande. Låt oss säga att vi har en fast matris av dokument och vi vill bygga en matris av användare. För att göra detta kommer vi att dela upp det i N delar för rader, varje del kommer att innehålla ungefär samma antal rader. Vi kommer att skicka till varje maskin icke-tomma celler i motsvarande rader, såväl som matrisen av dokumentinbäddningar (helt). Eftersom dess storlek inte är särskilt stor och användardokumentmatrisen vanligtvis är väldigt sparsam, kommer dessa data att passa på en vanlig maskin.

Detta trick kan upprepas över flera epoker tills modellen konvergerar, alternerar den fasta matrisen en efter en. Men även då kan matrisnedbrytning ta flera timmar. Och detta löser inte problemet med att du snabbt behöver ta emot inbäddningar av nya dokument och uppdatera inbäddningarna av de som det fanns lite information om när du bygger modellen.

Införandet av snabba inkrementella modelluppdateringar hjälpte oss. Låt oss säga att vi har en för närvarande utbildad modell. Sedan hennes utbildning har det kommit nya artiklar som våra användare har interagerat med, samt artiklar som haft lite interaktion under träningen. För att snabbt få inbäddningar av sådana artiklar använder vi de användarinbäddningar som erhållits under den första stora utbildningen av modellen och gör ett ALS-steg för att beräkna dokumentmatrisen givet en fast användarmatris. Detta gör att du kan ta emot inbäddningar ganska snabbt - inom några minuter efter att dokumentet publicerats - och ofta uppdatera inbäddningar av senaste dokument.

För att ge rekommendationer omedelbart ta hänsyn till mänskliga handlingar, under körning använder vi inte användarinbäddningar som erhållits offline. Istället gör vi ett ALS-steg och får den faktiska användarvektorn.

Överför till ett annat domänområde

Hur använder man feedback från användare på textartiklar för att bygga en vektorrepresentation av en video?

Till en början rekommenderade vi endast textartiklar, så många av våra algoritmer är skräddarsydda för den här typen av innehåll. Men när vi lade till andra typer av innehåll stod vi inför behovet av att anpassa modellerna. Hur löste vi det här problemet med ett videoexempel? Ett alternativ är att skola om alla modeller från grunden. Men detta tar lång tid, och vissa av algoritmerna kräver storleken på utbildningsprovet, som ännu inte är tillgängligt i den mängd som krävs för en ny typ av innehåll under de första ögonblicken av dess liv på tjänsten.

Vi gick åt andra hållet och återanvände textmodellerna för videon. Samma ALS-trick hjälpte oss att skapa vektorrepresentationer av videor. Vi tog en vektorrepresentation av användare baserat på textartiklar och gjorde ett ALS-steg med hjälp av videovisningsinformation. Så vi fick lätt en vektorrepresentation av videon. Och vid körning beräknar vi helt enkelt närheten mellan användarvektorn som erhålls från textartiklar och videovektorn.

Slutsats

Att utveckla kärnan i ett rekommendationssystem i realtid innebär många utmaningar. Du måste snabbt bearbeta data och tillämpa ML-metoder för att effektivt använda dessa data; bygga komplexa distribuerade system som kan behandla användarsignaler och nya innehållsenheter på kort tid; och många andra uppgifter.

I det nuvarande systemet, vars utformning jag beskrev, växer kvaliteten på rekommendationerna för användaren tillsammans med hans aktivitet och vistelsetid på tjänsten. Men här ligger naturligtvis den största svårigheten: det är svårt för systemet att omedelbart förstå intressen hos en person som har lite interaktion med innehållet. Att förbättra rekommendationerna för nya användare är vårt huvudmål. Vi kommer att fortsätta att optimera algoritmerna så att innehåll som är relevant för en person kommer in i hans flöde snabbare, och irrelevant innehåll inte visas.

Källa: will.com