Moje ime je Pavel Parkhomenko, ja sam ML programer. U ovom bih članku želio govoriti o strukturi usluge Yandex.Zen i podijeliti tehnička poboljšanja čija je implementacija omogućila povećanje kvalitete preporuka. Iz ove objave naučit ćete kako među milijunima dokumenata u samo nekoliko milisekundi pronaći one najrelevantnije za korisnika; kako napraviti kontinuiranu dekompoziciju velike matrice (koja se sastoji od milijuna stupaca i desetaka milijuna redaka) tako da novi dokumenti dobiju svoj vektor za desetke minuta; kako ponovno upotrijebiti dekompoziciju matrice korisnik-članak da biste dobili dobru vektorsku reprezentaciju za video.
Naša baza preporuka sadrži milijune dokumenata različitih formata: tekstualne članke stvorene na našoj platformi i preuzete s vanjskih stranica, videozapise, narative i kratke objave. Razvoj takve usluge povezan je s velikim brojem tehničkih izazova. Ovo su neki od njih:
- Podijelite računalne zadatke: obavljajte sve teške operacije izvan mreže, au stvarnom vremenu samo brzu primjenu modela kako biste bili odgovorni za 100-200 ms.
- Brzo uzmite u obzir radnje korisnika. Da biste to učinili, potrebno je da se svi događaji trenutno dostavljaju preporučitelju i utječu na rezultate modela.
- Napravite feed tako da se za nove korisnike brzo prilagodi njihovom ponašanju. Ljudi koji su se tek pridružili sustavu trebali bi osjećati da njihove povratne informacije utječu na preporuke.
- Brzo shvatite kome preporučiti novi članak.
- Brzo reagirajte na stalnu pojavu novih sadržaja. Svaki dan se objavi na desetke tisuća članaka, a mnogi od njih imaju ograničen vijek trajanja (recimo vijesti). To je ono što ih razlikuje od filmova, glazbe i drugih dugotrajnih i skupih sadržaja za stvaranje.
- Prijenos znanja iz jednog domenskog područja u drugo. Ako sustav preporuke ima obučene modele za tekstualne članke i mi mu dodamo video, možemo ponovno upotrijebiti postojeće modele tako da nova vrsta sadržaja bude bolje rangirana.
Reći ću vam kako smo riješili te probleme.
Odabir kandidata
Kako smanjiti broj dokumenata koji se razmatraju tisućama puta u nekoliko milisekundi, gotovo bez pogoršanja kvalitete rangiranja?
Pretpostavimo da smo istrenirali mnogo ML modela, generirali značajke na temelju njih i istrenirali još jedan 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 stvarnom vremenu, ako postoje milijuni tih dokumenata, a preporuke se moraju izgraditi za 100-200 ms. Zadatak je odabrati određeni podskup od milijuna, koji će biti rangiran za korisnika. Ova faza se obično naziva selekcija kandidata. Postoji nekoliko zahtjeva za to. Prvo, selekcija se mora odvijati vrlo brzo, kako bi što više vremena ostalo za samu rang listu. Drugo, nakon što smo uvelike smanjili broj dokumenata za rangiranje, moramo što potpunije sačuvati dokumente relevantne za korisnika.
Naš princip selekcije kandidata je evoluirao, i trenutno smo došli do sheme u više faza:
Najprije su svi dokumenti podijeljeni u skupine, a iz svake skupine uzeti su najpopularniji dokumenti. Grupe mogu biti stranice, teme, klasteri. Za svakog korisnika se na temelju njegove povijesti odabiru njemu najbliže grupe i od njih se uzimaju najbolji dokumenti. Također koristimo kNN indeks za odabir dokumenata koji su najbliži korisniku u stvarnom vremenu. Postoji nekoliko metoda za konstruiranje kNN indeksa; naša je bila najbolja (Hijerarhijski plovni grafikoni malog svijeta). Ovo je hijerarhijski model koji vam omogućuje da pronađete N najbližih vektora za korisnika iz baze podataka od milijuna u nekoliko milisekundi. Prvo indeksiramo našu cijelu bazu dokumenata offline. Budući da pretraživanje u indeksu radi prilično brzo, ako postoji nekoliko jakih ugrađivanja, možete stvoriti nekoliko indeksa (jedan indeks za svako umetanje) i svakom od njih pristupati u stvarnom vremenu.
Još uvijek imamo desetke tisuća dokumenata za svakog korisnika. To je još uvijek puno za brojanje svih značajki, tako da u ovoj fazi koristimo lagano rangiranje - lagani model teškog rangiranja s manje značajki. Zadatak je predvidjeti koje dokumente će teški model imati na vrhu. Dokumenti s najvećim prediktorom koristit će se u teškom modelu, odnosno u posljednjoj fazi rangiranja. Ovaj vam pristup omogućuje smanjenje baze podataka dokumenata koji se razmatraju za korisnika s milijuna na tisuće u desecima 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 koristiti sustav preporuka, dobiva nepersonalizirani feed dokumenata različitih tema. Čim napravi prvi klik, morate to odmah uzeti u obzir i prilagoditi se njegovim interesima. Ako izračunate sve faktore izvan mreže, brz odgovor sustava postat će nemoguć zbog kašnjenja. Stoga je potrebno obraditi radnje korisnika u stvarnom vremenu. U te svrhe koristimo ALS korak tijekom izvođenja za izgradnju vektorske reprezentacije korisnika.
Pretpostavimo da imamo vektorski prikaz za sve dokumente. Na primjer, možemo izgraditi ugradnje izvan mreže na temelju teksta članka koristeći ELMo, BERT ili druge modele strojnog učenja. Kako možemo dobiti vektorski prikaz korisnika u istom prostoru na temelju njihovih interakcija u sustavu?
Opći princip formiranja i dekompozicije matrice korisnik-dokumentNeka imamo m korisnika i n dokumenata. Nekim korisnicima je poznat njihov odnos prema određenim dokumentima. Zatim se ove informacije mogu predstaviti kao mxn matrica: retci odgovaraju korisnicima, a stupci odgovaraju dokumentima. Budući da osoba nije vidjela većinu dokumenata, većina će ćelija matrice 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 navedena u matrici - ali razmotrimo pojednostavljeni model u kojem lajk odgovara 1, a nesviđanje odgovara -1.
Rastavimo matricu na dvije: P (mxd) i Q (dxn), gdje je d dimenzija vektorske reprezentacije (obično mali broj). Tada će svaki objekt odgovarati d-dimenzionalnom vektoru (za korisnika - red u matrici P, za dokument - stupac u matrici Q). Ovi vektori će biti ugradnje odgovarajućih objekata. Da biste predvidjeli hoće li se korisniku svidjeti dokument, možete jednostavno pomnožiti njegove ugradnje.
Jedan od mogućih načina dekomponiranja matrice je ALS (Alternating Least Squares). Optimizirat ćemo sljedeću funkciju gubitka:
Ovdje je rui interakcija korisnika u s dokumentom i, qi je vektor dokumenta i, pu je vektor korisnika u.
Tada se optimalni korisnički vektor sa stajališta srednje kvadratne pogreške (za fiksne vektore dokumenata) pronalazi analitički rješavanjem odgovarajuće linearne regresije.
To se naziva "ALS korak". A sam algoritam ALS-a sastoji se u tome da naizmjenično popravljamo jednu od matrica (korisnici i članci) i ažuriramo drugu, pronalazeći optimalno rješenje.
Srećom, pronalaženje korisnikove vektorske reprezentacije prilično je brza operacija koja se može obaviti tijekom izvođenja pomoću vektorskih instrukcija. Ovaj vam trik omogućuje da povratne informacije korisnika odmah uzmete u obzir pri rangiranju. Isto ugrađivanje može se koristiti u kNN indeksu za poboljšanje odabira kandidata.
Distribuirano suradničko filtriranje
Kako napraviti faktorizaciju inkrementalne distribuirane matrice i brzo pronaći vektorske prikaze novih članaka?
Sadržaj nije jedini izvor signala preporuke. Drugi važan izvor su informacije o suradnji. Dobra svojstva rangiranja tradicionalno se mogu dobiti dekompozicijom matrice korisničkih dokumenata. Ali kada smo pokušali napraviti takvu dekompoziciju, naišli smo na probleme:
1. Imamo milijune dokumenata i desetke milijuna korisnika. Matrica ne stane u potpunosti na jedan stroj, a razgradnja će trajati jako dugo.
2. Većina sadržaja u sustavu ima kratak životni vijek: dokumenti ostaju relevantni samo nekoliko sati. Stoga je potrebno što brže konstruirati njihov vektorski prikaz.
3. Ako napravite dekompoziciju odmah nakon što je dokument objavljen, dovoljan broj korisnika neće imati vremena da ga ocijeni. Stoga njegova vektorska reprezentacija najvjerojatnije neće biti baš dobra.
4. Ako se korisniku sviđa ili ne sviđa, nećemo to moći odmah uzeti u obzir u dekompoziciji.
Kako bismo riješili te probleme, implementirali smo distribuiranu dekompoziciju matrice korisničkih dokumenata s čestim inkrementalnim ažuriranjima. Kako to točno radi?
Pretpostavimo da imamo klaster od N strojeva (N je u stotinama) i želimo na njima napraviti distribuiranu dekompoziciju matrice koja ne stane na jedan stroj. Pitanje je kako izvesti ovu dekompoziciju tako da, s jedne strane, ima dovoljno podataka na svakom stroju, a s druge strane, da izračuni budu neovisni?
Koristit ćemo gore opisani algoritam ALS dekompozicije. Pogledajmo kako izvršiti jedan ALS korak na raspodijeljeni način - ostali koraci bit će slični. Recimo da imamo fiksnu matricu dokumenata i želimo izgraditi matricu korisnika. Da bismo to učinili, podijelit ćemo ga na N dijelova po linijama, svaki dio će sadržavati približno isti broj redaka. Svakom stroju ćemo poslati neprazne ćelije odgovarajućih redaka, kao i matricu umetanja dokumenta (u cijelosti). Budući da njegova veličina nije jako velika, a matrica korisničkog dokumenta obično je vrlo rijetka, ti će podaci stati na obično računalo.
Ovaj se trik može ponavljati tijekom 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. A to ne rješava problem da morate brzo primati 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 njezine obuke bilo je novih članaka s kojima su naši korisnici komunicirali, kao i članaka koji su imali malo interakcije tijekom obuke. Kako bismo brzo dobili ugradnje takvih članaka, koristimo korisničke ugradnje dobivene tijekom prve velike obuke modela i radimo jedan ALS korak za izračun matrice dokumenta s obzirom na fiksnu korisničku matricu. To vam omogućuje da vrlo brzo primate ugradnje - unutar nekoliko minuta nakon što je dokument objavljen - i često ažurirate ugradnje nedavnih dokumenata.
Kako bi preporuke odmah uzele u obzir ljudske radnje, u vremenu izvođenja ne koristimo korisničke ugradnje dobivene izvan mreže. Umjesto toga, radimo ALS korak i dobivamo stvarni korisnički vektor.
Prijenos na drugo područje domene
Kako upotrijebiti povratne informacije korisnika o tekstualnim člancima za izradu vektorskog prikaza videozapisa?
U početku smo preporučivali samo tekstualne članke, tako da su mnogi naši algoritmi prilagođeni ovoj vrsti sadržaja. Ali kada smo dodavali druge vrste sadržaja, suočili smo se s potrebom prilagođavanja modela. Kako smo riješili ovaj problem koristeći video primjer? Jedna je mogućnost prekvalificirati sve modele od nule. Ali to traje dugo, a neki od algoritama zahtijevaju veličinu uzorka za obuku, koji još nije dostupan u potrebnoj količini za novu vrstu sadržaja u prvim trenucima svog života na usluzi.
Otišli smo drugim putem i ponovno upotrijebili tekstualne modele za video. Isti ALS trik pomogao nam je stvoriti vektorske prikaze videozapisa. Uzeli smo vektorski prikaz korisnika na temelju tekstualnih članaka i napravili korak ALS-a pomoću informacija o prikazu videozapisa. Tako smo lako dobili vektorski prikaz videa. A tijekom izvođenja jednostavno izračunavamo blizinu između korisničkog vektora dobivenog iz tekstualnih članaka i video vektora.
Zaključak
Razvijanje jezgre sustava preporuka u stvarnom vremenu uključuje mnoge izazove. Morate brzo obraditi podatke i primijeniti ML metode za učinkovito korištenje tih podataka; izgraditi složene distribuirane sustave sposobne obraditi korisničke signale i nove jedinice sadržaja u minimalnom vremenu; i mnoge druge zadatke.
U postojećem sustavu, čiji sam dizajn opisao, kvaliteta preporuke za korisnika raste s njegovom aktivnošću i dužinom boravka na usluzi. Ali naravno, ovdje leži glavna poteškoća: sustavu je teško odmah shvatiti 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 došao u njegov feed, a nebitan sadržaj se ne bi prikazivao.
Izvor: www.habr.com