Moje ime je Pavel Parkhomenko, ja sam ML programer. U ovom članku želim govoriti o strukturi usluge Yandex.Zen i podijeliti tehnička poboljšanja, čija je implementacija omogućila povećanje kvalitete preporuka. Iz ovog posta ćete naučiti kako pronaći najrelevantnije za korisnika među milionima dokumenata u samo nekoliko milisekundi; kako napraviti kontinuiranu dekompoziciju velike matrice (koja se sastoji od miliona kolona i desetina miliona redova) tako da novi dokumenti dobiju svoj vektor za desetine minuta; kako ponovo koristiti dekompoziciju matrice korisnik-članak da dobijete dobar vektorski prikaz za video.
Naša baza podataka preporuka sadrži milione dokumenata različitih formata: tekstualne članke kreirane na našoj platformi i preuzete sa eksternih sajtova, video zapise, narative i kratke postove. Razvoj ovakve usluge povezan je s velikim brojem tehničkih izazova. Evo nekih od njih:
- Podijelite računske zadatke: obavljajte sve teške operacije van mreže, au realnom vremenu samo brzu primjenu modela kako biste bili odgovorni za 100-200 ms.
- Brzo uzmite u obzir radnje korisnika. Da bi se to postiglo, potrebno je da se svi događaji momentalno isporučuju preporučiocu i utiču na rezultate modela.
- Napravite feed tako da se za nove korisnike brzo prilagođava njihovom ponašanju. Ljudi koji su se tek pridružili sistemu trebali bi osjetiti da njihove povratne informacije utiču na preporuke.
- Brzo shvatite kome preporučiti novi članak.
- Brzo reagirajte na stalnu pojavu novih sadržaja. Svaki dan se objavljuju desetine hiljada članaka, a mnogi od njih imaju ograničen životni vijek (recimo vijesti). To je ono što ih razlikuje od filmova, muzike i drugih dugovječnih i skupih sadržaja za kreiranje.
- Prenesite znanje iz jedne oblasti u drugu. Ako sistem preporuka ima obučene modele za tekstualne članke i dodamo mu video, možemo ponovo koristiti postojeće modele kako bi nova vrsta sadržaja bolje rangirala.
Reći ću vam kako smo riješili ove probleme.
Selekcija kandidata
Kako smanjiti broj dokumenata koji se razmatraju hiljadama puta za nekoliko milisekundi, a da praktično ne dođe do pogoršanja kvaliteta rangiranja?
Pretpostavimo da smo obučili mnoge ML modele, generisali karakteristike na osnovu njih i obučili drugi model koji rangira dokumente za korisnika. Sve bi bilo u redu, ali ne možete samo uzeti i izračunati sve znakove za sve dokumente u realnom vremenu, ako postoje milioni ovih dokumenata, a preporuke se moraju izgraditi za 100-200 ms. Zadatak je odabrati određeni podskup od miliona, koji će biti rangiran za korisnika. Ova faza se obično naziva selekcija kandidata. Za to postoji nekoliko zahtjeva. Prvo, selekcija mora da se desi veoma brzo, kako bi što više vremena ostalo za samo rangiranje. Drugo, pošto smo značajno smanjili broj dokumenata za rangiranje, moramo sačuvati dokumente relevantne za korisnika što je moguće potpunije.
Naš princip selekcije kandidata je evoluirao i trenutno smo došli do višestepene šeme:
Prvo, svi dokumenti su podijeljeni u grupe, a najpopularniji dokumenti su uzeti iz svake grupe. Grupe mogu biti stranice, teme, klasteri. Za svakog korisnika, na osnovu njegove istorije, biraju se grupe koje su mu najbliže i iz njih se uzimaju najbolji dokumenti. Također koristimo kNN indeks za odabir dokumenata koji su najbliži korisniku u realnom vremenu. Postoji nekoliko metoda za konstruisanje kNN indeksa; naša je najbolje funkcionirala (Hijerarhijski navigacijski grafovi malog svijeta). Ovo je hijerarhijski model koji vam omogućava da pronađete N najbližih vektora za korisnika iz baze podataka od miliona za nekoliko milisekundi. Prvo indeksiramo cijelu našu bazu dokumenata van mreže. Pošto pretraživanje u indeksu radi prilično brzo, ako postoji nekoliko jakih ugradnji, možete kreirati nekoliko indeksa (jedan indeks za svako ugrađivanje) i pristupiti svakom od njih u realnom vremenu.
Još uvijek imamo desetine hiljada dokumenata za svakog korisnika. Ovo je još mnogo da se izbroje sve karakteristike, tako da u ovoj fazi koristimo laki rang – lagani model za teško rangiranje sa manje karakteristika. Zadatak je predvidjeti koje će dokumente teži model imati u vrhu. Dokumenti sa najvećim prediktorom će se koristiti u teškom modelu, odnosno u poslednjoj fazi rangiranja. Ovaj pristup vam omogućava da smanjite bazu podataka dokumenata koji se razmatraju za korisnika sa miliona na hiljade u desetinama milisekundi.
ALS korak u vremenu izvođenja
Kako uzeti u obzir povratne informacije korisnika odmah nakon klika?
Važan faktor u preporukama je vrijeme odgovora na povratne informacije korisnika. Ovo je posebno važno za nove korisnike: kada osoba tek počne da koristi sistem preporuka, dobija nepersonalizovani feed dokumenata različitih tema. Čim napravi prvi klik, morate to odmah uzeti u obzir i prilagoditi se njegovim interesima. Ako sve faktore izračunate van mreže, brz odgovor sistema će postati nemoguć zbog kašnjenja. Stoga je potrebno obraditi radnje korisnika u realnom vremenu. U ove svrhe koristimo ALS korak u vremenu izvođenja da izgradimo vektorsku reprezentaciju korisnika.
Pretpostavimo da imamo vektorsku reprezentaciju za sve dokumente. Na primjer, možemo izgraditi ugradnje van mreže na osnovu teksta članka koristeći ELMo, BERT ili druge modele strojnog učenja. Kako možemo dobiti vektorsku reprezentaciju korisnika u istom prostoru na osnovu njihovih interakcija u sistemu?
Opšti princip formiranja i dekompozicije matrice korisnik-dokumentNeka imamo m korisnika i n dokumenata. Nekim korisnicima je poznat njihov odnos prema određenim dokumentima. Tada se ove informacije mogu predstaviti kao mxn matrica: redovi odgovaraju korisnicima, a kolone dokumentima. Pošto osoba nije vidjela većinu dokumenata, većina ćelija matrice će ostati prazna, dok će druge biti popunjene. Za svaki događaj (sviđa mi se, ne sviđa mi se, klik) određena je vrijednost u matrici - ali razmotrimo pojednostavljeni model u kojem lajk odgovara 1, a nesviđanje odgovara -1.
Dekomponirajmo matricu na dva: P (mxd) i Q (dxn), gdje je d dimenzija vektorske reprezentacije (obično mali broj). Tada će svaki objekat odgovarati d-dimenzionalnom vektoru (za korisnika - red u matrici P, za dokument - kolona u matrici Q). Ovi vektori će biti ugrađivanje odgovarajućih objekata. Da biste predvidjeli da li će se korisniku svidjeti dokument, možete jednostavno pomnožiti njegove ugradnje.
Jedan od mogućih načina za razlaganje matrice je ALS (izmjenični najmanji kvadrati). Optimizirat ćemo sljedeću funkciju gubitka:
Ovdje je rui interakcija korisnika u sa dokumentom i, qi je vektor dokumenta i, pu je vektor korisnika u.
Tada se analitički pronalazi optimalni korisnički vektor sa stanovišta srednje kvadratne greške (za fiksne vektore dokumenta) rješavanjem odgovarajuće linearne regresije.
Ovo se zove "ALS korak". A sam ALS algoritam je da naizmjenično popravljamo jednu od matrica (korisnike i članke) i ažuriramo drugu, pronalazeći optimalno rješenje.
Srećom, pronalaženje korisničkog vektorskog prikaza je prilično brza operacija koja se može obaviti u toku rada pomoću vektorskih instrukcija. Ovaj trik vam omogućava da odmah uzmete u obzir povratne informacije korisnika prilikom rangiranja. Isto ugrađivanje se može koristiti u kNN indeksu za poboljšanje selekcije kandidata.
Distributed Collaborative Filtering
Kako napraviti inkrementalnu distribuiranu matričnu faktorizaciju i brzo pronaći vektorske reprezentacije novih članaka?
Sadržaj nije jedini izvor signala preporuke. Drugi važan izvor su informacije o saradnji. Dobre karakteristike rangiranja se tradicionalno mogu dobiti dekompozicijom matrice korisnik-dokument. Ali kada smo pokušali napraviti takvu dekompoziciju, naišli smo na probleme:
1. Imamo milione dokumenata i desetine miliona korisnika. Matrica ne stane u potpunosti na jednu mašinu, a razgradnja će trajati jako dugo.
2. Većina sadržaja u sistemu ima kratak vijek trajanja: dokumenti ostaju relevantni samo nekoliko sati. Stoga je potrebno što je brže moguće konstruirati njihov vektorski prikaz.
3. Ako napravite dekompoziciju odmah nakon objavljivanja dokumenta, dovoljan broj korisnika neće imati vremena da ga procijeni. Stoga, njegova vektorska reprezentacija najvjerovatnije neće biti dobra.
4. Ako se korisniku sviđa ili ne sviđa, to nećemo moći odmah uzeti u obzir u dekompoziciji.
Da bismo riješili ove probleme, implementirali smo distribuiranu dekompoziciju matrice korisnik-dokument sa čestim inkrementalnim ažuriranjima. Kako tačno funkcioniše?
Pretpostavimo da imamo klaster od N mašina (N je u stotinama) i želimo da izvršimo distribuiranu dekompoziciju matrice na njima koja ne stane na jednu mašinu. Postavlja se pitanje kako izvršiti ovu dekompoziciju tako da, s jedne strane, ima dovoljno podataka o svakoj mašini, a s druge strane, da proračuni budu nezavisni?
Koristićemo gore opisani algoritam ALS dekompozicije. Pogledajmo kako izvršiti jedan ALS korak na distribuiran način - ostali koraci će biti slični. Recimo da imamo fiksnu matricu dokumenata i želimo da napravimo matricu korisnika. Da bismo to učinili, podijelit ćemo ga na N dijelova po linijama, svaki dio će sadržavati približno isti broj linija. Svakoj mašini ćemo poslati neprazne ćelije odgovarajućih redova, kao i matricu ugradnje dokumenata (u potpunosti). Budući da njegova veličina nije velika, a matrica korisničkih dokumenata je obično vrlo rijetka, ovi podaci će stati na običnu mašinu.
Ovaj trik se može ponavljati kroz nekoliko epoha dok se model ne konvergira, mijenjajući fiksnu matricu jednu po jednu. Ali čak i tada, razgradnja matrice može potrajati nekoliko sati. I to ne rješava problem da trebate brzo primiti ugradnje novih dokumenata i ažurirati ugradnje onih o kojima je bilo malo informacija prilikom izgradnje modela.
Pomoglo nam je uvođenje brzih inkrementalnih ažuriranja modela. Recimo da imamo trenutno obučeni model. Od njenog treninga, pojavili su se novi članci sa kojima su naši korisnici imali interakciju, kao i članci koji su imali malo interakcije tokom obuke. Da bismo brzo dobili ugrađivanje takvih članaka, koristimo korisnička ugrađivanja dobijena tokom prve velike obuke modela i radimo jedan ALS korak da bismo izračunali matricu dokumenta s obzirom na fiksnu korisničku matricu. Ovo vam omogućava da primite ugradnje prilično brzo - u roku od nekoliko minuta nakon što je dokument objavljen - i često ažurirate ugradnje nedavnih dokumenata.
Da bismo dali preporuke odmah uzeli u obzir ljudske radnje, u vremenu izvođenja ne koristimo korisničke ugradnje dobijene van mreže. Umjesto toga, radimo ALS korak i dobivamo stvarni korisnički vektor.
Prijenos na drugu domenu
Kako koristiti povratne informacije korisnika o tekstualnim člancima za izgradnju vektorske reprezentacije videa?
U početku smo preporučivali samo tekstualne članke, tako da su mnogi naši algoritmi prilagođeni ovoj vrsti sadržaja. No, prilikom dodavanja drugih vrsta sadržaja, suočili smo se s potrebom prilagođavanja modela. Kako smo riješili ovaj problem koristeći video primjer? Jedna od opcija je ponovno obučavanje svih modela od nule. Ali to traje dugo, a neki od algoritama su zahtjevni za veličinu uzorka za obuku, koji još nije dostupan u potrebnoj količini za novu vrstu sadržaja u prvim trenucima svog života na servisu.
Otišli smo drugim putem i ponovo koristili tekstualne modele za video. Isti ALS trik nam je pomogao da kreiramo vektorske reprezentacije videa. Uzeli smo vektorsku reprezentaciju korisnika na osnovu tekstualnih članaka i uradili ALS korak koristeći informacije o gledanju videa. Tako smo lako dobili vektorski prikaz videa. A za vrijeme rada jednostavno izračunavamo blizinu između korisničkog vektora dobivenog iz tekstualnih članaka i video vektora.
zaključak
Razvijanje jezgra sistema preporuka u realnom vremenu uključuje mnoge izazove. Morate brzo obraditi podatke i primijeniti ML metode da biste efikasno koristili ove podatke; izgraditi složene distribuirane sisteme sposobne za obradu korisničkih signala i novih jedinica sadržaja u minimalnom vremenu; i mnoge druge zadatke.
U postojećem sistemu, čiji sam dizajn opisao, kvalitet preporuka za korisnika raste zajedno sa njegovom aktivnošću i dužinom boravka na servisu. Ali, naravno, ovdje leži glavna poteškoća: sistemu je teško odmah razumjeti interese osobe koja ima malo interakcije sa sadržajem. Poboljšanje preporuka za nove korisnike naš je ključni cilj. Nastavit ćemo optimizirati algoritme kako bi sadržaj koji je relevantan za osobu brže ušao u njegov feed, a nebitan sadržaj se ne bi prikazivao.
izvor: www.habr.com