Numele meu este Pavel Parkhomenko, sunt dezvoltator ML. În acest articol, aș dori să vorbesc despre structura serviciului Yandex.Zen și să împărtășesc îmbunătățiri tehnice, a căror implementare a făcut posibilă creșterea calității recomandărilor. Din această postare veți învăța cum să le găsiți pe cele mai relevante pentru utilizator dintre milioane de documente în doar câteva milisecunde; cum se face descompunerea continuă a unei matrice mari (formată din milioane de coloane și zeci de milioane de rânduri) astfel încât documentele noi să-și primească vectorul în zeci de minute; cum să reutilizați descompunerea matricei utilizator-articol pentru a obține o reprezentare vectorială bună pentru video.
Baza noastră de date de recomandări conține milioane de documente de diferite formate: articole text create pe platforma noastră și preluate de pe site-uri externe, videoclipuri, narațiuni și postări scurte. Dezvoltarea unui astfel de serviciu este asociată cu un număr mare de provocări tehnice. Aici sunt câțiva dintre ei:
- Împărțiți sarcinile de calcul: faceți toate operațiunile grele offline și în timp real executați doar aplicarea rapidă a modelelor pentru a fi responsabil pentru 100-200 ms.
- Luați în considerare rapid acțiunile utilizatorului. Pentru a face acest lucru, este necesar ca toate evenimentele să fie livrate instantaneu recomandatorului și să influențeze rezultatele modelelor.
- Faceți feedul astfel încât pentru utilizatorii noi să se adapteze rapid la comportamentul lor. Persoanele care tocmai s-au alăturat sistemului ar trebui să simtă că feedback-ul lor influențează recomandările.
- Înțelegeți rapid cui să recomandați un articol nou.
- Răspundeți rapid la apariția constantă de conținut nou. Zeci de mii de articole sunt publicate în fiecare zi, iar multe dintre ele au o durată de viață limitată (să zicem, știri). Acesta este ceea ce îi diferențiază de filme, muzică și alte conținuturi de lungă durată și costisitoare de creat.
- Transferați cunoștințele dintr-un domeniu în altul. Dacă un sistem de recomandare are modele antrenate pentru articole text și îi adăugăm video, putem reutiliza modelele existente pentru ca noul tip de conținut să se clasifice mai bine.
Vă voi spune cum am rezolvat aceste probleme.
Selecția candidaților
Cum să reduceți numărul documentelor luate în considerare de mii de ori în câteva milisecunde, practic fără nicio deteriorare a calității clasamentului?
Să presupunem că am antrenat multe modele ML, am generat funcții pe baza acestora și am antrenat un alt model care clasifică documentele pentru utilizator. Totul ar fi bine, dar nu puteți doar să luați și să calculați toate semnele pentru toate documentele în timp real, dacă există milioane de aceste documente, iar recomandările trebuie construite în 100-200 ms. Sarcina este de a selecta un anumit subset din milioane, care va fi clasat pentru utilizator. Această etapă se numește de obicei selecția candidaților. Există mai multe cerințe pentru aceasta. În primul rând, selecția trebuie să aibă loc foarte repede, astfel încât să rămână cât mai mult timp posibil pentru clasarea în sine. În al doilea rând, după ce am redus foarte mult numărul de documente pentru clasare, trebuie să păstrăm cât mai complet documentele relevante pentru utilizator.
Principiul nostru de selecție a candidaților a evoluat, iar în acest moment am ajuns la o schemă în mai multe etape:
În primul rând, toate documentele sunt împărțite în grupuri, iar cele mai populare documente sunt luate din fiecare grup. Grupurile pot fi site-uri, subiecte, clustere. Pentru fiecare utilizator, pe baza istoricului său, sunt selectate grupurile cele mai apropiate de el și din ele sunt preluate cele mai bune documente. De asemenea, folosim indexul kNN pentru a selecta documentele care sunt cele mai apropiate de utilizator în timp real. Există mai multe metode pentru a construi un index kNN; a noastră a funcționat cel mai bine (Grafe Ierarhice Navigabile Lumii Mici). Acesta este un model ierarhic care vă permite să găsiți cei mai apropiați N vectori pentru un utilizator dintr-o bază de date de milioane în câteva milisecunde. Mai întâi indexăm întreaga noastră bază de date de documente offline. Deoarece căutarea în index funcționează destul de repede, dacă există mai multe înglobări puternice, puteți crea mai mulți indici (un index pentru fiecare încorporare) și să accesați fiecare dintre aceștia în timp real.
Mai avem zeci de mii de documente pentru fiecare utilizator. Este încă mult pentru a număra toate caracteristicile, așa că în această etapă folosim clasamentul ușor - un model de clasare greu și ușor, cu mai puține funcții. Sarcina este de a prezice ce documente va avea un model greu în partea de sus. Documentele cu cel mai mare predictor vor fi folosite în modelul greu, adică la ultima etapă de clasare. Această abordare vă permite să reduceți baza de date de documente luate în considerare pentru utilizator de la milioane la mii în zeci de milisecunde.
Pasul ALS în timpul de execuție
Cum să țineți cont de feedbackul utilizatorilor imediat după un clic?
Un factor important în recomandări este timpul de răspuns la feedback-ul utilizatorilor. Acest lucru este deosebit de important pentru utilizatorii noi: atunci când o persoană abia începe să folosească sistemul de recomandare, primește un flux nepersonalizat de documente cu diverse subiecte. De îndată ce face primul clic, trebuie să țineți imediat cont de acest lucru și să vă adaptați intereselor sale. Dacă calculați toți factorii offline, un răspuns rapid al sistemului va deveni imposibil din cauza întârzierii. Deci este necesar să procesăm acțiunile utilizatorului în timp real. În aceste scopuri, folosim pasul ALS în timpul execuției pentru a construi o reprezentare vectorială a utilizatorului.
Să presupunem că avem o reprezentare vectorială pentru toate documentele. De exemplu, putem construi încorporari offline pe baza textului unui articol folosind ELMo, BERT sau alte modele de învățare automată. Cum putem obține o reprezentare vectorială a utilizatorilor în același spațiu pe baza interacțiunilor lor în sistem?
Principiul general de formare și descompunere a matricei utilizator-documentSă avem m utilizatori și n documente. Pentru unii utilizatori, relația lor cu anumite documente este cunoscută. Apoi aceste informații pot fi reprezentate ca o matrice mxn: rândurile corespund utilizatorilor, iar coloanele corespund documentelor. Deoarece persoana nu a văzut majoritatea documentelor, majoritatea celulelor matricei vor rămâne goale, în timp ce altele vor fi umplute. Pentru fiecare eveniment (precum, dislike, click) o anumită valoare este furnizată în matrice - dar să luăm în considerare un model simplificat în care un like corespunde cu 1, iar un dislike corespunde -1.
Să descompunăm matricea în două: P (mxd) și Q (dxn), unde d este dimensiunea reprezentării vectoriale (de obicei un număr mic). Apoi fiecare obiect va corespunde unui vector d-dimensional (pentru un utilizator - un rând în matricea P, pentru un document - o coloană în matricea Q). Acești vectori vor fi înglobările obiectelor corespunzătoare. Pentru a prezice dacă un utilizator îi va plăcea un document, puteți pur și simplu să le multiplicați înglobările.
Una dintre modalitățile posibile de a descompune o matrice este ALS (Alternating Least Squares). Vom optimiza următoarea funcție de pierdere:
Aici rui este interacțiunea utilizatorului u cu documentul i, qi este vectorul documentului i, pu este vectorul utilizatorului u.
Apoi vectorul optim de utilizator din punctul de vedere al erorii pătratice medii (pentru vectori de document fix) este găsit analitic prin rezolvarea regresiei liniare corespunzătoare.
Acesta se numește „pasul ALS”. Iar algoritmul ALS în sine este că fixăm alternativ una dintre matrice (utilizatori și articole) și o actualizăm pe cealaltă, găsind soluția optimă.
Din fericire, găsirea reprezentării vectoriale a utilizatorului este o operație destul de rapidă care poate fi făcută în timpul execuției folosind instrucțiuni vectoriale. Acest truc vă permite să luați imediat în considerare feedbackul utilizatorilor în clasament. Aceeași încorporare poate fi utilizată în indexul kNN pentru a îmbunătăți selecția candidaților.
Filtrare colaborativă distribuită
Cum să faci factorizarea incrementală a matricei distribuite și să găsești rapid reprezentări vectoriale ale articolelor noi?
Conținutul nu este singura sursă de semnale de recomandare. O altă sursă importantă este informația colaborativă. Caracteristicile bune de clasare pot fi obținute în mod tradițional din descompunerea matricei document-utilizator. Dar când am încercat să facem o astfel de descompunere, am întâmpinat probleme:
1. Avem milioane de documente și zeci de milioane de utilizatori. Matricea nu se potrivește în întregime pe o singură mașină, iar descompunerea va dura foarte mult timp.
2. Majoritatea conținutului din sistem are o durată de viață scurtă: documentele rămân relevante doar câteva ore. Prin urmare, este necesar să se construiască reprezentarea vectorială a acestora cât mai repede posibil.
3. Dacă construiți o descompunere imediat după publicarea documentului, un număr suficient de utilizatori nu vor avea timp să o evalueze. Prin urmare, reprezentarea sa vectorială nu va fi foarte bună.
4. Dacă unui utilizator îi place sau nu îi place, nu vom putea lua imediat în considerare acest lucru în descompunere.
Pentru a rezolva aceste probleme, am implementat o descompunere distribuită a matricei utilizator-document cu actualizări incrementale frecvente. Cum funcționează exact?
Să presupunem că avem un grup de N mașini (N este în sute) și dorim să facem o descompunere distribuită a unei matrice pe ele care nu se potrivește pe o singură mașină. Întrebarea este cum se realizează această descompunere astfel încât, pe de o parte, să existe suficiente date pe fiecare mașină și, pe de altă parte, astfel încât calculele să fie independente?
Vom folosi algoritmul de descompunere ALS descris mai sus. Să ne uităm la cum să executați un pas ALS într-o manieră distribuită - restul pașilor vor fi similari. Să presupunem că avem o matrice fixă de documente și dorim să construim o matrice de utilizatori. Pentru a face acest lucru, îl vom împărți în N părți pe linii, fiecare parte va conține aproximativ același număr de linii. Vom trimite fiecărei mașini celule nevide ale rândurilor corespunzătoare, precum și matricea de încorporare a documentelor (în întregime). Deoarece dimensiunea sa nu este foarte mare, iar matricea documentului utilizator este de obicei foarte rară, aceste date se vor potrivi pe o mașină obișnuită.
Acest truc poate fi repetat pe mai multe epoci până când modelul converge, alternând matricea fixă una câte una. Dar chiar și atunci, descompunerea matricei poate dura câteva ore. Și acest lucru nu rezolvă problema că trebuie să primiți rapid înglobări ale documentelor noi și să actualizați înglobările celor despre care au existat puține informații la construirea modelului.
Introducerea actualizărilor incrementale rapide de model ne-a ajutat. Să presupunem că avem un model pregătit în prezent. De la formarea ei, au apărut articole noi cu care utilizatorii noștri au interacționat, precum și articole care au avut o interacțiune redusă în timpul antrenamentului. Pentru a obține rapid înglobările unor astfel de articole, folosim încorporațiile de utilizator obținute în timpul primului antrenament mare a modelului și facem un pas ALS pentru a calcula matricea documentului având în vedere o matrice de utilizator fixă. Acest lucru vă permite să primiți înglobări destul de rapid - în câteva minute după publicarea documentului - și să actualizați adesea înglobările documentelor recente.
Pentru a face recomandări să ținem cont imediat de acțiunile umane, în timpul de execuție nu folosim încorporarea utilizatorilor obținute offline. În schimb, facem un pas ALS și obținem vectorul utilizatorului real.
Transferați într-o altă zonă de domeniu
Cum să utilizați feedbackul utilizatorilor asupra articolelor text pentru a construi o reprezentare vectorială a unui videoclip?
Inițial, am recomandat doar articole text, așa că mulți dintre algoritmii noștri sunt adaptați acestui tip de conținut. Dar la adăugarea altor tipuri de conținut, ne-am confruntat cu nevoia de a adapta modelele. Cum am rezolvat această problemă folosind un exemplu video? O opțiune este recalificarea tuturor modelelor de la zero. Dar acest lucru durează mult timp, iar unii algoritmi solicită dimensiunea eșantionului de antrenament, care nu este încă disponibil în cantitatea necesară pentru un nou tip de conținut în primele momente ale vieții sale pe serviciu.
Am mers invers și am refolosit modelele text pentru videoclip. Același truc ALS ne-a ajutat să creăm reprezentări vectoriale ale videoclipurilor. Am luat o reprezentare vectorială a utilizatorilor pe baza articolelor text și am făcut un pas ALS folosind informațiile de vizualizare video. Deci am obținut cu ușurință o reprezentare vectorială a videoclipului. Și în timpul rulării pur și simplu calculăm proximitatea dintre vectorul utilizatorului obținut din articole text și vectorul video.
Concluzie
Dezvoltarea nucleului unui sistem de recomandare în timp real implică multe provocări. Trebuie să procesați rapid datele și să aplicați metode ML pentru a utiliza eficient aceste date; construiți sisteme complexe distribuite capabile să proceseze semnalele utilizatorului și noi unități de conținut într-un timp minim; și multe alte sarcini.
În sistemul actual, al cărui design l-am descris, calitatea recomandărilor pentru utilizator crește odată cu activitatea și durata șederii acestuia în serviciu. Dar, desigur, aici se află principala dificultate: este dificil pentru sistem să înțeleagă imediat interesele unei persoane care are puțină interacțiune cu conținutul. Îmbunătățirea recomandărilor pentru noii utilizatori este obiectivul nostru cheie. Vom continua să optimizăm algoritmii, astfel încât conținutul care este relevant pentru o persoană să intre mai repede în feedul său și conținutul irelevant să nu fie afișat.
Sursa: www.habr.com