Kiel ni laboras pri la kvalito kaj rapideco de elekto de rekomendoj

Mia nomo estas Pavel Parkhomenko, mi estas ML-programisto. En ĉi tiu artikolo, mi ŝatus paroli pri la strukturo de la servo Yandex.Zen kaj dividi teknikajn plibonigojn, kies efektivigo ebligis pliigi la kvaliton de rekomendoj. De ĉi tiu afiŝo vi lernos kiel trovi la plej gravajn por la uzanto inter milionoj da dokumentoj en nur kelkaj milisekundoj; kiel fari daŭran malkomponadon de granda matrico (konsistanta el milionoj da kolumnoj kaj dekoj da milionoj da vicoj) por ke novaj dokumentoj ricevu sian vektoron en dekoj da minutoj; kiel reuzi la uzant-artikola matrica malkomponaĵo por akiri bonan vektoran reprezenton por video.

Nia rekomenda datumbazo enhavas milionojn da dokumentoj de diversaj formatoj: tekstaj artikoloj kreitaj sur nia platformo kaj prenitaj de eksteraj retejoj, filmetoj, rakontoj kaj mallongaj afiŝoj. La disvolviĝo de tia servo estas rilata al granda nombro da teknikaj defioj. Jen kelkaj el ili:

• Dividu komputikajn taskojn: faru ĉiujn pezajn operaciojn eksterrete, kaj en reala tempo nur faru rapidan aplikon de modeloj por respondeci pri 100-200 ms.
• Rapide konsideru uzantajn agojn. Por fari tion, necesas, ke ĉiuj eventoj estu tuj transdonitaj al la rekomendanto kaj influu la rezultojn de la modeloj.
• Faru la nutradon por ke por novaj uzantoj ĝi rapide adaptiĝu al ilia konduto. Homoj, kiuj ĵus aliĝis al la sistemo, devus senti, ke iliaj sugestoj influas rekomendojn.
• Rapide komprenu al kiu rekomendi novan artikolon.
• Respondu rapide al la konstanta apero de nova enhavo. Dekoj da miloj da artikoloj estas publikigitaj ĉiutage, kaj multaj el ili havas limigitan vivdaŭron (ni ekzemple novaĵoj). Jen kio distingas ilin de filmoj, muziko kaj aliaj longdaŭraj kaj multekostaj enhavoj por krei.
• Transloki scion de unu domajna areo al alia. Se rekomendsistemo trejnis modelojn por tekstaj artikoloj kaj ni aldonas filmeton al ĝi, ni povas reuzi la ekzistantajn modelojn por ke la nova enhavo pli bone rangiĝu.

Mi rakontos al vi kiel ni solvis ĉi tiujn problemojn.

Elekto de kandidatoj

Kiel redukti la nombron da konsiderataj dokumentoj je miloj da fojoj en kelkaj milisekundoj, kun preskaŭ neniu difekto en la kvalito de rangotabelo?

Supozu, ke ni trejnis multajn ML-modelojn, generis funkciojn bazitajn sur ili kaj trejnis alian modelon, kiu rangigas dokumentojn por la uzanto. Ĉio estus bone, sed vi ne povas simple preni kaj kalkuli ĉiujn signojn por ĉiuj dokumentoj en reala tempo, se ekzistas milionoj da ĉi tiuj dokumentoj, kaj rekomendoj devas esti konstruitaj en 100-200 ms. La tasko estas elekti certan subaron el milionoj, kiuj estos vicigitaj por la uzanto. Ĉi tiu stadio estas kutime nomita kandidato-elekto. Estas pluraj postuloj por ĝi. Unue, la elekto devas okazi tre rapide, por ke restas kiel eble plej multe da tempo por la ranking mem. Due, tre reduktinte la nombron da dokumentoj por rangado, ni devas konservi dokumentojn rilatajn al la uzanto kiel eble plej tute.

Nia principo de elekto de kandidatoj evoluis, kaj nuntempe ni alvenis al plurŝtupa skemo:

Unue, ĉiuj dokumentoj estas dividitaj en grupojn, kaj la plej popularaj dokumentoj estas prenitaj de ĉiu grupo. Grupoj povas esti retejoj, temoj, aretoj. Por ĉiu uzanto, surbaze de lia historio, la grupoj plej proksimaj al li estas elektitaj kaj la plej bonaj dokumentoj estas prenitaj de ili. Ni ankaŭ uzas la kNN-indekson por elekti dokumentojn, kiuj estas plej proksimaj al la uzanto en reala tempo. Estas pluraj metodoj por konstrui kNN-indekson; la nia funkciis plej bone HNSW (Hierarkiaj Navigeblaj Malgrandaj Mondaj grafikaĵoj). Ĉi tio estas hierarkia modelo, kiu ebligas al vi trovi la N plej proksimajn vektorojn por uzanto el datumbazo de milionoj en kelkaj milisekundoj. Ni unue indeksas nian tutan dokumentan datumbazon eksterrete. Ĉar serĉado en la indekso funkcias sufiĉe rapide, se estas pluraj fortaj enkonstruaĵoj, vi povas krei plurajn indeksojn (unu indekso por ĉiu enmetado) kaj aliri ĉiun el ili en reala tempo.

Ni ankoraŭ havas dekojn da miloj da dokumentoj por ĉiu uzanto. Ĉi tio ankoraŭ estas multe por kalkuli ĉiujn funkciojn, do en ĉi tiu etapo ni uzas malpezan rangotabelon - malpezan pezan rangomodelon kun malpli da funkcioj. La tasko estas antaŭdiri, kiujn dokumentojn peza modelo havos en la supro. Dokumentoj kun la plej alta prognozilo estos uzataj en la peza modelo, tio estas, ĉe la lasta etapo de rango. Ĉi tiu aliro permesas redukti la datumbazon de dokumentoj konsiderataj por la uzanto de milionoj al miloj en dekoj da milisekundoj.

ALS paŝo en rultempo

Kiel konsideri uzantajn komentojn tuj post klako?

Grava faktoro en rekomendoj estas la respondtempo al uzantreagoj. Ĉi tio estas precipe grava por novaj uzantoj: kiam persono ĵus ekuzas la rekomendsistemon, li ricevas nepersonigitan fluaĵon de dokumentoj pri diversaj temoj. Tuj kiam li faras la unuan klakon, vi devas tuj konsideri tion kaj adaptiĝi al liaj interesoj. Se vi kalkulas ĉiujn faktorojn eksterrete, rapida sistema respondo fariĝos neebla pro la malfruo. Do necesas prilabori uzantajn agojn en reala tempo. Por ĉi tiuj celoj, ni uzas la paŝon ALS ĉe rultempo por konstrui vektoran reprezenton de la uzanto.

Ni supozu, ke ni havas vektoran reprezenton por ĉiuj dokumentoj. Ekzemple, ni povas konstrui enkonstruojn eksterrete surbaze de la teksto de artikolo uzante ELMo, BERT aŭ aliajn maŝinlernajn modelojn. Kiel ni povas akiri vektoran reprezentadon de uzantoj en la sama spaco bazita sur iliaj interagoj en la sistemo?

Ĝenerala principo de formado kaj malkomponaĵo de la uzantdokumenta matricoNi havu m uzantojn kaj n dokumentojn. Por iuj uzantoj, ilia rilato al certaj dokumentoj estas konata. Tiam ĉi tiu informo povas esti reprezentita kiel mxn-matrico: vicoj respondas al uzantoj, kaj kolumnoj respondas al dokumentoj. Ĉar la persono ne vidis la plej multajn el la dokumentoj, la plej multaj el la matricaj ĉeloj restos malplenaj, dum aliaj estos plenigitaj. Por ĉiu evento (kiel, malŝato, klako) iu valoro estas provizita en la matrico - sed ni konsideru simpligitan modelon, en kiu simila respondas al 1, kaj malŝato respondas al -1.

Ni malkomponu la matricon en du: P (mxd) kaj Q (dxn), kie d estas la dimensio de la vektora prezento (kutime malgranda nombro). Tiam ĉiu objekto respondas al d-dimensia vektoro (por uzanto - vico en la matrico P, por dokumento - kolumno en la matrico Q). Ĉi tiuj vektoroj estos la enkonstruado de la respondaj objektoj. Por antaŭdiri ĉu uzanto ŝatos dokumenton, vi povas simple multobligi iliajn enkonstruaĵojn.

Unu el la eblaj manieroj malkomponi matricon estas ALS (Alternating Least Squares). Ni optimumigos la sekvan perdan funkcion:

Ĉi tie rui estas la interago de uzanto u kun dokumento i, qi estas la vektoro de dokumento i, pu estas la vektoro de uzanto u.

Tiam la optimuma uzantvektoro de la vidpunkto de la averaĝa kvadrata eraro (por fiksaj dokumentvektoroj) estas trovita analize solvante la ekvivalentan linearan regreson.

Ĉi tio estas nomita la "ALS-paŝo". Kaj la ALS-algoritmo mem estas, ke ni alterne fiksas unu el la matricoj (uzantoj kaj artikoloj) kaj ĝisdatigas la alian, trovante la optimuman solvon.

Feliĉe, trovi la vektoran reprezenton de la uzanto estas sufiĉe rapida operacio, kiu povas esti farita ĉe rultempo uzante vektorajn instrukciojn. Ĉi tiu lertaĵo permesas vin tuj konsideri uzantajn komentojn en la rangotabelo. La sama enkonstruado povas esti uzata en la kNN-indekso por plibonigi kandidatelekton.

Distribuita Kunlabora Filtrado

Kiel fari pliigan distribuitan matrican faktorigon kaj rapide trovi vektorajn prezentojn de novaj artikoloj?

Enhavo ne estas la sola fonto de rekomendaj signaloj. Alia grava fonto estas kunlabora informo. Bonaj rangotabeloj tradicie povas esti akiritaj de la putriĝo de la uzantdokumenta matrico. Sed kiam ni provis fari tian malkomponaĵon, ni renkontis problemojn:

1. Ni havas milionojn da dokumentoj kaj dekojn da milionoj da uzantoj. La matrico ne konvenas tute sur unu maŝino, kaj putriĝo prenos tre longan tempon.
2. Plejparto de la enhavo en la sistemo havas mallongan vivdaŭron: dokumentoj restas trafaj dum nur kelkaj horoj. Tial, estas necese konstrui ilian vektoran reprezenton kiel eble plej rapide.
3. Se vi konstruas malkomponaĵon tuj post la publikigo de la dokumento, sufiĉa nombro da uzantoj ne havos tempon por taksi ĝin. Tial, ĝia vektora reprezentado plej verŝajne ne estos tre bona.
4. Se iu uzanto ŝatas aŭ malŝatas, ni ne povos tuj konsideri tion en la malkomponaĵo.

Por solvi ĉi tiujn problemojn, ni efektivigis distribuitan malkomponadon de la uzantdokumenta matrico kun oftaj pliigaj ĝisdatigoj. Kiel ĝuste ĝi funkcias?

Supozu ke ni havas areton de N maŝinoj (N estas en la centoj) kaj ni volas fari distribuitan putriĝon de matrico sur ili kiu ne taŭgas sur unu maŝino. La demando estas kiel fari ĉi tiun malkomponaĵon por ke, unuflanke, estu sufiĉe da datumoj pri ĉiu maŝino kaj, aliflanke, por ke la kalkuloj estu sendependaj?

Ni uzos la algoritmon de malkomponaĵo ALS priskribita supre. Ni rigardu kiel efektivigi unu ALS-paŝon en distribuita maniero - la ceteraj paŝoj estos similaj. Ni diru, ke ni havas fiksan matricon de dokumentoj kaj ni volas konstrui matricon de uzantoj. Por fari tion, ni dividos ĝin en N partojn per linioj, ĉiu parto enhavos proksimume la saman nombron da linioj. Ni sendos al ĉiu maŝino nemalplenajn ĉelojn de la respondaj vicoj, same kiel la matricon de dokument-enkonstruado (tute). Ĉar ĝia grandeco ne estas tre granda, kaj la uzantdokumenta matrico estas kutime tre malabunda, ĉi tiuj datumoj taŭgos sur regula maŝino.

Tiu ĉi truko povas esti ripetita dum pluraj epokoj ĝis la modelo konverĝas, alternante la fiksan matricon unu post unu. Sed eĉ tiam, matrica putriĝo povas daŭri plurajn horojn. Kaj ĉi tio ne solvas la problemon, ke vi bezonas rapide ricevi enkonstruojn de novaj dokumentoj kaj ĝisdatigi la enkonstruojn de tiuj pri kiuj estis malmulte da informoj dum konstruado de la modelo.

La enkonduko de rapidaj pliigaj modelaj ĝisdatigoj helpis nin. Ni diru, ke ni havas nuntempe trejnitan modelon. Ekde ŝia trejnado, ekzistas novaj artikoloj, kun kiuj niaj uzantoj interagis, kaj ankaŭ artikoloj, kiuj havis malmulte da interagado dum trejnado. Por rapide akiri la enkonstruojn de tiaj artikoloj, ni uzas la uzantajn enkonstruojn akiritajn dum la unua granda trejnado de la modelo kaj faras unu ALS-paŝon por kalkuli la dokumentmatricon donitan fiksan uzantmatricon. Ĉi tio ebligas al vi ricevi enkonstruaĵojn sufiĉe rapide - ene de kelkaj minutoj post la publikigo de la dokumento - kaj ofte ĝisdatigi la enkonstruaĵojn de lastatempaj dokumentoj.

Por fari rekomendojn tuj konsideru homajn agojn, en rultempo ni ne uzas uzantajn enkonstruojn akiritajn eksterrete. Anstataŭe, ni faras ALS-paŝon kaj ricevas la realan uzantan vektoron.

Translokiĝu al alia domajna areo

Kiel uzi uzantajn komentojn pri tekstaj artikoloj por konstrui vektoran reprezenton de video?

Komence, ni rekomendis nur tekstajn artikolojn, do multaj el niaj algoritmoj estas adaptitaj al ĉi tiu speco de enhavo. Sed aldonante aliajn specojn de enhavo, ni alfrontis la bezonon adapti la modelojn. Kiel ni solvis ĉi tiun problemon per videoekzemplo? Unu opcio estas retrejni ĉiujn modelojn de nulo. Sed ĉi tio daŭras longan tempon, kaj iuj el la algoritmoj postulas la grandecon de la trejna specimeno, kiu ankoraŭ ne haveblas en la bezonata kvanto por nova speco de enhavo en la unuaj momentoj de sia vivo en la servo.

Ni iris la alian vojon kaj reuzis la tekstajn modelojn por la video. La sama ALS-truko helpis nin krei vektorajn reprezentojn de videoj. Ni prenis vektoran reprezenton de uzantoj surbaze de tekstaj artikoloj kaj faris ALS-paŝon uzante videajn informojn. Do ni facile akiris vektoran reprezenton de la video. Kaj ĉe rultempo ni simple kalkulas la proksimecon inter la uzantvektoro akirita de tekstaj artikoloj kaj la videovektoro.

konkludo

Evoluigi la kernon de realtempa rekomendsistemo implikas multajn defiojn. Vi devas rapide prilabori datumojn kaj apliki ML-metodojn por efike uzi ĉi tiujn datumojn; konstrui kompleksajn distribuitajn sistemojn kapablajn prilabori uzantsignalojn kaj novajn enhavunuojn en minimuma tempo; kaj multaj aliaj taskoj.

En la nuna sistemo, kies dezajnon mi priskribis, la kvalito de rekomendoj por la uzanto kreskas kune kun lia aktiveco kaj daŭro de restado en la servo. Sed kompreneble ĉi tie kuŝas la ĉefa malfacilaĵo: malfacilas por la sistemo tuj kompreni la interesojn de homo, kiu malmulte interagas kun la enhavo. Plibonigi rekomendojn por novaj uzantoj estas nia ĉefa celo. Ni daŭrigos optimumigi la algoritmojn por ke enhavo grava por persono eniru sian nutradon pli rapide, kaj sensigniva enhavo ne montriĝas.

fonto: www.habr.com