Myn namme is Pavel Parkhomenko, ik bin in ML-ûntwikkelder. Yn dit artikel wol ik prate oer de struktuer fan 'e Yandex.Zen-tsjinst en diele technyske ferbetteringen, wêrfan de útfiering it mooglik makke hat om de kwaliteit fan oanbefellings te ferheegjen. Fan dizze post sille jo leare hoe't jo de meast relevante foar de brûker fine kinne tusken miljoenen dokuminten yn mar in pear millisekonden; hoe't jo trochgeande ûntbining fan in grutte matrix dwaan (besteande út miljoenen kolommen en tsientallen miljoenen rigen) sadat nije dokuminten har fektor yn tsientallen minuten ûntfange; hoe't jo de matrix-ûntbining fan brûker-artikel opnij brûke om in goede fektorfoarstelling te krijen foar fideo.
Us oanbefellingsdatabase befettet miljoenen dokuminten fan ferskate formaten: tekstartikels makke op ús platfoarm en nommen fan eksterne siden, fideo's, ferhalen en koarte berjochten. De ûntwikkeling fan sa'n tsjinst is ferbûn mei in grut oantal technyske útdagings. Hjir binne guon fan harren:
- Diel komputertaken: doch alle swiere operaasjes offline, en útfiere yn realtime allinich rappe tapassing fan modellen om ferantwurdlik te wêzen foar 100-200 ms.
- Nim fluch rekken mei brûkersaksjes. Om dit te dwaan is it needsaaklik dat alle eveneminten direkt oan 'e oanbefeller wurde levere en de resultaten fan' e modellen beynfloedzje.
- Meitsje de feed sa dat it foar nije brûkers fluch oanpast oan har gedrach. Minsken dy't krekt lid binne fan it systeem moatte fiele dat har feedback beynfloedet oanbefellings.
- Begryp fluch oan wa't in nij artikel oanbefelje moat.
- Reagearje fluch op it konstante ûntstean fan nije ynhâld. Tsientûzenen artikels wurde alle dagen publisearre, en in protte fan harren hawwe in beheinde libbensdoer (sii, nijs). Dit is wat se ûnderskiedt fan films, muzyk en oare lange libbene en djoere ynhâld om te meitsjen.
- Oerdrage kennis fan it iene domeingebiet nei it oare. As in oanbefellingssysteem modellen hat oplaat foar tekstartikels en wy tafoegje fideo deroan, kinne wy de besteande modellen opnij brûke, sadat it nije type ynhâld better ranks.
Ik sil jo fertelle hoe't wy dizze problemen hawwe oplost.
Seleksje fan kandidaten
Hoe te ferminderjen it oantal dokuminten ûnder behanneling troch tûzenen kearen yn in pear millisekonden, mei praktysk gjin efterútgong yn de kwaliteit fan ranglist?
Stel dat wy in protte ML-modellen oplaat hawwe, funksjes genereare op basis fan har, en in oar model oplaat dat dokuminten ranglist foar de brûker. Alles soe goed wêze, mar jo kinne net allinich alle tekens foar alle dokuminten yn realtime nimme en berekkenje, as d'r miljoenen fan dizze dokuminten binne, en oanbefellings moatte yn 100-200 ms boud wurde. De taak is om in bepaalde subset út miljoenen te selektearjen, dy't sil wurde rangearre foar de brûker. Dizze poadium wurdt meastentiids kandidaatseleksje neamd. Der binne ferskate easken foar. Foarearst moat de seleksje hiel fluch barre, sadat safolle mooglik tiid oerbliuwt foar de ranglist sels. Twads, nei't wy it oantal dokuminten foar ranglist sterk fermindere hawwe, moatte wy dokuminten dy't relevant binne foar de brûker sa folslein mooglik bewarje.
Us prinsipe fan kandidaatseleksje is evoluearre, en op it stuit binne wy oankommen by in skema mei meardere etappe:
Earst wurde alle dokuminten ferdield yn groepen, en de populêrste dokuminten wurde út elke groep nommen. Groepen kinne siden, ûnderwerpen, klusters wêze. Foar elke brûker wurde, op basis fan syn skiednis, de groepen dy't it tichtst by him binne selektearre en de bêste dokuminten wurde fan har helle. Wy brûke ek de kNN-yndeks om dokuminten te selektearjen dy't it tichtst by de brûker yn echt binne. D'r binne ferskate metoaden foar it bouwen fan in kNN-yndeks dy't ús it bêste wurke (Hierarchical Navigable Small World-grafiken). Dit is in hiërargysk model wêrmei jo te finen de N tichtst vectors foar in brûker út in database fan miljoenen yn in pear millisekonden. Wy yndeksearje earst ús hiele dokumintdatabase offline. Om't sykjen yn 'e yndeks frij fluch wurket, as d'r ferskate sterke ynbêden binne, kinne jo ferskate yndeksen meitsje (ien yndeks foar elke ynbêding) en tagong krije ta elk fan har yn realtime.
Wy hawwe noch tsientûzenen dokuminten foar elke brûker. Dit is noch in protte om alle funksjes te tellen, dus op dit stadium brûke wy ljochte ranglist - in lichtgewicht swier ranglistmodel mei minder funksjes. De taak is om foarsizze hokker dokuminten in swier model sil hawwe yn de top. Dokuminten mei de heechste foarsizzer sille brûkt wurde yn it swiere model, dat is yn 'e lêste faze fan ranglist. Dizze oanpak lit jo de database fan dokuminten dy't beskôge wurde foar de brûker fan miljoenen nei tûzenen yn tsientallen millisekonden ferminderje.
ALS stap yn runtime
Hoe kinne jo direkt nei in klik rekken hâlde mei feedback fan brûkers?
In wichtige faktor yn oanbefellings is de reaksjetiid op feedback fan brûkers. Dit is foaral wichtich foar nije brûkers: as in persoan gewoan begjint mei it oanbefellingssysteem, krijt hy in net-personalisearre feed fan dokuminten fan ferskate ûnderwerpen. Sadree't hy de earste klik makket, moatte jo dit fuortendaliks rekken hâlde en oanpasse oan syn ynteresses. As jo alle faktoaren offline berekkenje, sil in rappe systeemantwurd ûnmooglik wurde fanwegen de fertraging. Sa is it nedich om brûkersaksjes yn realtime te ferwurkjen. Foar dizze doelen brûke wy de ALS-stap by runtime om in fektorfoarstelling fan 'e brûker te bouwen.
Litte wy oannimme dat wy in fektorfoarstelling hawwe foar alle dokuminten. Wy kinne bygelyks offline ynbêdingen bouwe op basis fan 'e tekst fan in artikel mei ELMo, BERT of oare masine-learmodellen. Hoe kinne wy in fektorfoarstelling krije fan brûkers yn deselde romte basearre op har ynteraksjes yn it systeem?
Algemiene prinsipe fan formaasje en ûntbining fan 'e brûker-dokumint matrixLit ús hawwe m brûkers en n dokuminten. Foar guon brûkers is har relaasje mei bepaalde dokuminten bekend. Dan kin dizze ynformaasje wurde fertsjintwurdige as in mxn-matrix: rigen oerienkomme mei brûkers, en kolommen oerienkomme mei dokuminten. Om't de persoan de measte dokuminten net sjoen hat, sille de measte matrixsellen leech bliuwe, wylst oaren ynfolle wurde. Foar elk barren (lykas, net leuk, klik) wurdt wat wearde levere yn 'e matrix - mar litte wy in ferienfâldige model beskôgje wêryn in like oerienkomt mei 1, en in dislike oerienkomt mei -1.
Litte wy de matrix opsplitse yn twa: P (mxd) en Q (dxn), wêrby't d de dimensje is fan 'e fektorfoarstelling (meastentiids in lyts getal). Dan sil elk objekt oerienkomme mei in d-dimensionale fektor (foar in brûker - in rige yn 'e matrix P, foar in dokumint - in kolom yn' e matrix Q). Dizze vectoren sille de ynbêdings wêze fan 'e oerienkommende objekten. Om foarsizze oft in brûker in dokumint sil leuk fine, kinne jo gewoan fermannichfâldigje harren ynbêdings.
Ien fan 'e mooglike manieren om in matrix te ûntbinen is ALS (Alternating Least Squares). Wy sille de folgjende ferliesfunksje optimalisearje:
Hjir is rui de ynteraksje fan brûker u mei dokumint i, qi is de fektor fan dokumint i, pu is de fektor fan brûker u.
Dan wurdt de optimale brûkersvektor út it eachpunt fan 'e gemiddelde fjouwerkante flater (foar fêste dokumintvektoren) analytysk fûn troch it oplossen fan de oerienkommende lineêre regression.
Dit wurdt de "ALS-stap" neamd. En it ALS-algoritme sels is dat wy ôfwikseljend ien fan 'e matrices (brûkers en artikels) reparearje en de oare bywurkje, de optimale oplossing fine.
Gelokkich is it finen fan de fektorfertsjintwurdiging fan 'e brûker in frij rappe operaasje dy't kin wurde dien by runtime mei vectorynstruksjes. Dizze trúk lit jo feedback fan brûkers fuortendaliks yn 'e ranglist nimme. Deselde ynbêding kin brûkt wurde yn de kNN-yndeks om kandidaatseleksje te ferbetterjen.
Ferspraat gearwurkjende filtering
Hoe kinne jo inkrementele ferdielde matrixfaktorisaasje dwaan en fektorfoarstellings fan nije artikels fluch fine?
Ynhâld is net de ienige boarne fan oanbefellingssinjalen. In oare wichtige boarne is gearwurkjende ynformaasje. Goede ranglistfunksjes kinne tradisjoneel wurde krigen fan 'e ûntbining fan' e brûkersdokumintmatrix. Mar by it besykjen om sa'n ûntbining te dwaan, troffen wy problemen:
1. Wy hawwe miljoenen dokuminten en tsientallen miljoenen brûkers. De matrix past net hielendal op ien masine, en ûntbining sil duorje in hiel lang.
2. It grutste part fan de ynhâld yn it systeem hat in koarte lifespan: dokuminten bliuwe relevant foar mar in pear oeren. Dêrom is it needsaaklik om har fektorfoarstelling sa gau mooglik te konstruearjen.
3. As jo bouwe in ûntbining fuortendaliks nei it dokumint is publisearre, in foldwaande oantal brûkers sil gjin tiid om te evaluearjen. Dêrom sil syn fektorfoarstelling nei alle gedachten net heul goed wêze.
4. As in brûker it leuk of net leuk fynt, kinne wy dit net fuortendaliks yn 'e ûntbining rekken hâlde.
Om dizze problemen op te lossen, hawwe wy in ferdielde ûntbining fan 'e matrix fan brûkersdokumint ymplementearre mei faak ynkrementele updates. Hoe wurket it krekt?
Stel dat wy in kluster fan N masines hawwe (N is yn 'e hûnderten) en wy wolle in ferdielde ûntbining dwaan fan in matriks op har dy't net past op ien masine. De fraach is hoe't jo dizze ûntbining útfiere, sadat oan 'e iene kant genôch gegevens binne op elke masine en oan' e oare, sadat de berekkeningen ûnôfhinklik binne?
Wy sille it hjirboppe beskreaune ALS-ûntbiningsalgoritme brûke. Litte wy sjen hoe't jo ien ALS-stap op in ferdielde manier kinne útfiere - de rest fan 'e stappen sille ferlykber wêze. Litte wy sizze dat wy in fêste matrix fan dokuminten hawwe en wy wolle in matrix fan brûkers bouwe. Om dit te dwaan, sille wy it ferdielen yn N dielen troch rigels, elk diel sil sawat itselde oantal rigels befetsje. Wy sille stjoere nei eltse masine net-lege sellen fan de oerienkommende rigen, likegoed as de matrix fan dokumint ynbêdings (hielendal). Sûnt syn grutte is net hiel grut, en de brûker-dokumint matrix is meastal hiel sparse, dizze gegevens sille passe op in gewoane masine.
Dizze trúk kin wurde werhelle oer ferskate epoken oant it model konvergeart, wikseljend de fêste matrix ien foar ien. Mar sels dan kin matrix ûntbining ferskate oeren duorje. En dit lost it probleem net op dat jo ynbêdingen fan nije dokuminten fluch moatte ûntfange en de ynbêdingen bywurkje fan dyjingen dy't by it bouwen fan it model net folle ynformaasje wie.
De ynfiering fan rappe ynkrementele modelupdates holp ús. Litte wy sizze dat wy in op it stuit oplaat model hawwe. Sûnt har training binne d'r nije artikels west wêrmei ús brûkers ynteraksje hawwe, lykas artikels dy't net folle ynteraksje hienen tidens training. Om de ynbêdingen fan sokke artikels fluch te krijen, brûke wy de brûker-ynbêdingen krigen tidens de earste grutte training fan it model en dogge ien ALS-stap om de dokumintmatrix te berekkenjen jûn in fêste brûkersmatrix. Hjirmei kinne jo ynbêdings frij fluch ûntfange - binnen in pear minuten nei't it dokumint is publisearre - en faaks de ynbêdingen fan resinte dokuminten bywurkje.
Om oanbefellings fuortendaliks rekken hâlden mei minsklike aksjes, yn runtime wy brûke gjin brûkers ynbêdings krigen offline. Ynstee dêrfan dogge wy in ALS-stap en krije de eigentlike brûkersvektor.
Oerstapje nei in oar domeingebiet
Hoe kinne jo feedback fan brûkers op tekstartikels brûke om in fektorfoarstelling fan in fideo te bouwen?
Yn it earstoan riede wy allinich tekstartikels oan, sadat in protte fan ús algoritmen binne ôfstimd op dit soarte ynhâld. Mar by it tafoegjen fan oare soarten ynhâld, waarden wy konfrontearre mei de needsaak om de modellen oan te passen. Hoe hawwe wy dit probleem oplost mei in fideofoarbyld? Ien opsje is om alle modellen fanôf it begjin te retrainen. Mar dit duorret in lange tiid, en guon fan 'e algoritmen binne easket op' e grutte fan 'e training sample, dy't noch net beskikber is yn' e fereaske kwantiteit foar in nij soart ynhâld yn 'e earste mominten fan syn libben op' e tsjinst.
Wy gongen de oare kant op en brûkten de tekstmodellen foar de fideo opnij. Deselde ALS trúk holp ús it meitsjen fan fektorfoarstellings fan fideo's. Wy namen in fektorfertsjintwurdiging fan brûkers basearre op tekstartikels en diene in ALS-stap mei help fan fideo-werjefteynformaasje. Sa krigen wy maklik in fektorfoarstelling fan 'e fideo. En by runtime berekkenje wy gewoan de tichtby tusken de brûkersfektor krigen fan tekstartikels en de fideovektor.
konklúzje
It ûntwikkeljen fan de kearn fan in real-time oanbefellingssysteem omfettet in protte útdagings. Jo moatte gegevens fluch ferwurkje en ML-metoaden tapasse om dizze gegevens effektyf te brûken; bouwe komplekse ferdielde systemen dy't yn steat binne om brûkerssinjalen en nije ienheden fan ynhâld yn in minimale tiid te ferwurkjen; en in protte oare taken.
Yn it hjoeddeistige systeem, it ûntwerp wêrfan ik beskreau, groeit de kwaliteit fan oanbefellings foar de brûker tegearre mei syn aktiviteit en de lingte fan ferbliuw op 'e tsjinst. Mar fansels, hjir leit de wichtichste muoite: it is dreech foar it systeem om fuortendaliks begripe de belangen fan in persoan dy't net folle ynteraksje mei de ynhâld. It ferbetterjen fan oanbefellings foar nije brûkers is ús haaddoel. Wy sille trochgean mei it optimalisearjen fan de algoritmen sadat ynhâld dy't relevant is foar in persoan flugger yn syn feed komt, en irrelevante ynhâld wurdt net werjûn.
Boarne: www.habr.com
