Ang pangalan ko ay Pavel Parkhomenko, isa akong developer ng ML. Sa artikulong ito, nais kong pag-usapan ang tungkol sa istraktura ng serbisyo ng Yandex.Zen at ibahagi ang mga teknikal na pagpapabuti, ang pagpapatupad nito ay naging posible upang madagdagan ang kalidad ng mga rekomendasyon. Mula sa post na ito matututunan mo kung paano hanapin ang mga pinakanauugnay para sa user sa milyun-milyong dokumento sa loob lamang ng ilang millisecond; kung paano gawin ang tuluy-tuloy na agnas ng isang malaking matrix (binubuo ng milyun-milyong column at sampu-sampung milyong row) upang matanggap ng mga bagong dokumento ang kanilang vector sa sampu-sampung minuto; kung paano muling gamitin ang user-article matrix decomposition para makakuha ng magandang representasyon ng vector para sa video.
Ang aming database ng rekomendasyon ay naglalaman ng milyun-milyong dokumento ng iba't ibang format: mga tekstong artikulo na nilikha sa aming platform at kinuha mula sa mga panlabas na site, video, salaysay at maikling post. Ang pagbuo ng naturang serbisyo ay nauugnay sa isang malaking bilang ng mga teknikal na hamon. Narito ang ilan sa mga ito:
- Hatiin ang mga gawain sa pag-compute: gawin ang lahat ng mabibigat na operasyon nang offline, at sa real time ay magsagawa lamang ng mabilis na aplikasyon ng mga modelo upang maging responsable para sa 100-200 ms.
- Mabilis na isaalang-alang ang mga aksyon ng user. Upang gawin ito, kinakailangan na ang lahat ng mga kaganapan ay agad na maihatid sa nagrerekomenda at maimpluwensyahan ang mga resulta ng mga modelo.
- Gawin ang feed para sa mga bagong user ay mabilis itong umangkop sa kanilang gawi. Dapat maramdaman ng mga taong kakasali lang sa system na nakakaimpluwensya sa mga rekomendasyon ang kanilang feedback.
- Mabilis na maunawaan kung kanino magrerekomenda ng bagong artikulo.
- Mabilis na tumugon sa patuloy na paglitaw ng bagong nilalaman. Sampu-sampung libong mga artikulo ang nai-publish araw-araw, at marami sa kanila ay may limitadong habang-buhay (sabihin, balita). Ito ang pinagkaiba nila sa mga pelikula, musika at iba pang pangmatagalan at mamahaling content na gagawin.
- Maglipat ng kaalaman mula sa isang domain area patungo sa isa pa. Kung ang isang sistema ng rekomendasyon ay may mga sinanay na modelo para sa mga tekstong artikulo at nagdagdag kami ng video dito, maaari naming muling gamitin ang mga kasalukuyang modelo upang ang bagong uri ng nilalaman ay mas mahusay ang ranggo.
Sasabihin ko sa iyo kung paano namin nalutas ang mga problemang ito.
Pagpili ng mga kandidato
Paano bawasan ang bilang ng mga dokumentong isinasaalang-alang ng libu-libong beses sa loob ng ilang millisecond, na halos walang pagkasira sa kalidad ng ranking?
Ipagpalagay na nagsanay kami ng maraming modelo ng ML, nakabuo ng mga feature batay sa mga ito, at nagsanay ng isa pang modelo na nagra-rank ng mga dokumento para sa user. Magiging maayos ang lahat, ngunit hindi mo maaaring kunin at kalkulahin ang lahat ng mga palatandaan para sa lahat ng mga dokumento sa real time, kung mayroong milyun-milyong mga dokumentong ito, at ang mga rekomendasyon ay kailangang itayo sa loob ng 100-200 ms. Ang gawain ay pumili ng isang partikular na subset mula sa milyun-milyon, na iraranggo para sa user. Ang yugtong ito ay karaniwang tinatawag na pagpili ng kandidato. Mayroong ilang mga kinakailangan para dito. Una, ang pagpili ay dapat mangyari nang napakabilis, upang ang mas maraming oras hangga't maaari ay natitira para sa pagraranggo mismo. Pangalawa, nang lubos na nabawasan ang bilang ng mga dokumento para sa pagraranggo, dapat nating panatilihin ang mga dokumentong nauugnay sa user nang ganap hangga't maaari.
Ang aming prinsipyo ng pagpili ng kandidato ay umunlad, at sa sandaling nakarating kami sa isang multi-stage scheme:
Una, ang lahat ng mga dokumento ay nahahati sa mga grupo, at ang pinakasikat na mga dokumento ay kinuha mula sa bawat grupo. Ang mga pangkat ay maaaring mga site, paksa, kumpol. Para sa bawat gumagamit, batay sa kanyang kasaysayan, ang mga pangkat na pinakamalapit sa kanya ay pinili at ang pinakamahusay na mga dokumento ay kinuha mula sa kanila. Ginagamit din namin ang kNN index upang pumili ng mga dokumento na pinakamalapit sa user sa real time. Mayroong ilang mga pamamaraan para sa pagbuo ng isang kNN index; ang sa amin ay pinakamahusay na nagtrabaho (Hierarchical Navigable Small World graphs). Ito ay isang hierarchical na modelo na nagbibigay-daan sa iyong mahanap ang N pinakamalapit na vectors para sa isang user mula sa isang database ng milyun-milyon sa loob ng ilang millisecond. Ini-index muna namin ang aming buong database ng dokumento nang offline. Dahil ang paghahanap sa index ay gumagana nang medyo mabilis, kung mayroong maraming malakas na pag-embed, maaari kang lumikha ng ilang mga index (isang index para sa bawat pag-embed) at i-access ang bawat isa sa kanila sa real time.
Mayroon pa kaming libu-libong mga dokumento para sa bawat gumagamit. Ito ay marami pa rin upang mabilang ang lahat ng mga tampok, kaya sa yugtong ito ay gumagamit kami ng magaan na pagraranggo - isang magaan na modelo ng pagraranggo na may mas kaunting mga tampok. Ang gawain ay hulaan kung aling mga dokumento ang magkakaroon ng mabigat na modelo sa itaas. Ang mga dokumentong may pinakamataas na predictor ay gagamitin sa mabigat na modelo, iyon ay, sa huling yugto ng pagraranggo. Binibigyang-daan ka ng diskarteng ito na bawasan ang database ng mga dokumentong isinasaalang-alang para sa user mula sa milyun-milyon hanggang sa libo-libo sa sampu-sampung millisecond.
ALS hakbang sa runtime
Paano isasaalang-alang ang feedback ng user kaagad pagkatapos ng isang pag-click?
Ang isang mahalagang kadahilanan sa mga rekomendasyon ay ang oras ng pagtugon sa feedback ng user. Ito ay lalong mahalaga para sa mga bagong user: kapag ang isang tao ay nagsimulang gumamit ng sistema ng rekomendasyon, siya ay tumatanggap ng isang hindi naka-personalize na feed ng mga dokumento ng iba't ibang mga paksa. Sa sandaling gawin niya ang unang pag-click, kailangan mong agad na isaalang-alang ito at umangkop sa kanyang mga interes. Kung kalkulahin mo ang lahat ng mga salik nang offline, ang isang mabilis na tugon ng system ay magiging imposible dahil sa pagkaantala. Kaya kinakailangan na iproseso ang mga aksyon ng user sa real time. Para sa mga layuning ito, ginagamit namin ang hakbang ng ALS sa runtime upang bumuo ng representasyon ng vector ng user.
Ipagpalagay natin na mayroon tayong representasyon ng vector para sa lahat ng mga dokumento. Halimbawa, maaari tayong bumuo ng mga pag-embed nang offline batay sa teksto ng isang artikulo gamit ang ELMo, BERT o iba pang mga modelo ng machine learning. Paano tayo makakakuha ng representasyon ng vector ng mga user sa parehong espasyo batay sa kanilang mga pakikipag-ugnayan sa system?
Pangkalahatang prinsipyo ng pagbuo at pagkabulok ng user-document matrixHayaan kaming magkaroon ng m user at n dokumento. Para sa ilang mga gumagamit, ang kanilang kaugnayan sa ilang mga dokumento ay kilala. Pagkatapos ang impormasyong ito ay maaaring katawanin bilang isang m x n matrix: ang mga hilera ay tumutugma sa mga user, at ang mga column ay tumutugma sa mga dokumento. Dahil hindi nakita ng tao ang karamihan sa mga dokumento, ang karamihan sa mga matrix cell ay mananatiling walang laman, habang ang iba ay mapupunan. Para sa bawat event (like, dislike, click) may ilang value na ibinibigay sa matrix - ngunit isaalang-alang natin ang isang pinasimpleng modelo kung saan ang like ay tumutugma sa 1, at isang hindi gusto ay tumutugma sa -1.
I-decompose natin ang matrix sa dalawa: P (m x d) at Q (d x n), kung saan ang d ay ang dimensyon ng representasyon ng vector (karaniwang maliit na numero). Pagkatapos ang bawat bagay ay tumutugma sa isang d-dimensional na vector (para sa isang gumagamit - isang hilera sa matrix P, para sa isang dokumento - isang haligi sa matrix Q). Ang mga vector na ito ang magiging mga pag-embed ng mga kaukulang bagay. Upang mahulaan kung magugustuhan ng isang user ang isang dokumento, maaari mong i-multiply lang ang kanilang mga pag-embed.
Ang isa sa mga posibleng paraan upang mabulok ang isang matrix ay ang ALS (Alternating Least Squares). I-optimize namin ang sumusunod na function ng pagkawala:
Narito ang rui ay ang interaksyon ng user u sa document i, qi ang vector ng document i, pu ang vector ng user u.
Pagkatapos, ang pinakamainam na vector ng gumagamit mula sa punto ng view ng mean square error (para sa mga nakapirming vector ng dokumento) ay matatagpuan nang analitikal sa pamamagitan ng paglutas ng kaukulang linear regression.
Ito ay tinatawag na "ALS step". At ang algorithm ng ALS mismo ay ang halili naming ayusin ang isa sa mga matrice (mga user at artikulo) at i-update ang isa, sa paghahanap ng pinakamainam na solusyon.
Sa kabutihang palad, ang paghahanap ng representasyon ng vector ng gumagamit ay isang medyo mabilis na operasyon na maaaring gawin sa runtime gamit ang mga tagubilin sa vector. Binibigyang-daan ka ng trick na ito na agad na isaalang-alang ang feedback ng user sa pagraranggo. Ang parehong pag-embed ay maaaring gamitin sa kNN index upang mapabuti ang pagpili ng kandidato.
Naipamahagi Collaborative Filtering
Paano gumawa ng incremental distributed matrix factorization at mabilis na makahanap ng mga representasyon ng vector ng mga bagong artikulo?
Hindi lang content ang pinagmumulan ng mga signal ng rekomendasyon. Ang isa pang mahalagang mapagkukunan ay collaborative na impormasyon. Ang mga mahusay na feature sa pagraranggo ay tradisyonal na makukuha mula sa decomposition ng user-document matrix. Ngunit kapag sinusubukang gawin ang naturang agnas, nakatagpo kami ng mga problema:
1. Mayroon kaming milyon-milyong mga dokumento at sampu-sampung milyong mga gumagamit. Ang matrix ay hindi ganap na magkasya sa isang makina, at ang agnas ay tatagal ng napakatagal.
2. Karamihan sa nilalaman sa system ay may maikling habang-buhay: ang mga dokumento ay nananatiling may kaugnayan sa loob lamang ng ilang oras. Samakatuwid, ito ay kinakailangan upang bumuo ng kanilang vector representasyon sa lalong madaling panahon.
3. Kung bubuo ka kaagad ng agnas pagkatapos mai-publish ang dokumento, ang sapat na bilang ng mga user ay hindi magkakaroon ng oras upang suriin ito. Samakatuwid, ang representasyon ng vector nito ay malamang na hindi napakahusay.
4. Kung gusto o hindi gusto ng isang user, hindi namin ito agad na maisasaalang-alang sa pagkabulok.
Upang malutas ang mga problemang ito, nagpatupad kami ng distributed decomposition ng user-document matrix na may madalas na incremental na mga update. Paano eksaktong gumagana ito?
Ipagpalagay na mayroon kaming isang kumpol ng mga N machine (N ay nasa daan-daan) at gusto naming gumawa ng isang distributed decomposition ng isang matrix sa mga ito na hindi magkasya sa isang makina. Ang tanong ay kung paano isagawa ang agnas na ito upang, sa isang banda, mayroong sapat na data sa bawat makina at, sa kabilang banda, upang ang mga kalkulasyon ay independyente?
Gagamitin namin ang ALS decomposition algorithm na inilarawan sa itaas. Tingnan natin kung paano isagawa ang isang hakbang ng ALS sa isang distributed na paraan - ang iba pang mga hakbang ay magiging katulad. Sabihin nating mayroon kaming nakapirming matrix ng mga dokumento at gusto naming bumuo ng matrix ng mga user. Upang gawin ito, hahatiin namin ito sa N bahagi sa pamamagitan ng mga linya, ang bawat bahagi ay naglalaman ng humigit-kumulang sa parehong bilang ng mga linya. Ipapadala namin sa bawat machine na walang laman na mga cell ng kaukulang mga hilera, pati na rin ang matrix ng mga pag-embed ng dokumento (ganap). Dahil ang laki nito ay hindi masyadong malaki, at ang user-document matrix ay kadalasang napakadalang, ang data na ito ay magkasya sa isang regular na makina.
Ang trick na ito ay maaaring ulitin sa ilang mga panahon hanggang sa mag-converge ang modelo, na isa-isang pinapalitan ang fixed matrix. Ngunit kahit na, ang matrix decomposition ay maaaring tumagal ng ilang oras. At hindi nito malulutas ang problema na kailangan mong mabilis na makatanggap ng mga pag-embed ng mga bagong dokumento at i-update ang mga pag-embed ng mga kung saan mayroong kaunting impormasyon sa pagbuo ng modelo.
Nakatulong sa amin ang pagpapakilala ng mabilis na incremental na mga update sa modelo. Sabihin nating mayroon tayong kasalukuyang sinanay na modelo. Mula sa kanyang pagsasanay, nagkaroon ng mga bagong artikulo na nakipag-ugnayan ang aming mga user, pati na rin ang mga artikulong may kaunting pakikipag-ugnayan sa panahon ng pagsasanay. Upang mabilis na makuha ang mga pag-embed ng naturang mga artikulo, ginagamit namin ang mga pag-embed ng user na nakuha sa unang malaking pagsasanay ng modelo at gumawa ng isang hakbang sa ALS upang kalkulahin ang matrix ng dokumento na binigyan ng isang nakapirming user matrix. Binibigyang-daan ka nitong makatanggap ng mga pag-embed nang mabilis - sa loob ng ilang minuto pagkatapos mai-publish ang dokumento - at madalas na i-update ang mga pag-embed ng mga kamakailang dokumento.
Upang gumawa ng mga rekomendasyon kaagad na isinasaalang-alang ang mga aksyon ng tao, sa runtime hindi kami gumagamit ng mga pag-embed ng user na nakuha offline. Sa halip, gumawa kami ng isang hakbang sa ALS at makuha ang aktwal na vector ng gumagamit.
Ilipat sa ibang domain area
Paano gamitin ang feedback ng user sa mga tekstong artikulo upang bumuo ng representasyon ng vector ng isang video?
Sa una, inirekomenda lang namin ang mga tekstong artikulo, kaya marami sa aming mga algorithm ay iniangkop sa ganitong uri ng nilalaman. Ngunit kapag nagdaragdag ng iba pang mga uri ng nilalaman, nahaharap kami sa pangangailangang iangkop ang mga modelo. Paano namin nalutas ang problemang ito gamit ang isang halimbawa ng video? Ang isang pagpipilian ay upang sanayin muli ang lahat ng mga modelo mula sa simula. Ngunit ito ay tumatagal ng mahabang panahon, at ang ilan sa mga algorithm ay hinihingi ang laki ng sample ng pagsasanay, na hindi pa magagamit sa kinakailangang dami para sa isang bagong uri ng nilalaman sa mga unang sandali ng buhay nito sa serbisyo.
Pumunta kami sa kabilang direksyon at ginamit muli ang mga modelo ng teksto para sa video. Ang parehong trick ng ALS ay nakatulong sa amin na lumikha ng mga representasyon ng vector ng mga video. Kumuha kami ng vector representation ng mga user batay sa mga text na artikulo at gumawa kami ng ALS step gamit ang impormasyon sa panonood ng video. Kaya madali kaming nakakuha ng representasyon ng vector ng video. At sa runtime, kinakalkula lang namin ang kalapitan sa pagitan ng vector ng gumagamit na nakuha mula sa mga artikulo ng teksto at ng vector ng video.
Konklusyon
Ang pagbuo ng core ng isang real-time na sistema ng rekomendasyon ay nagsasangkot ng maraming hamon. Kailangan mong mabilis na iproseso ang data at ilapat ang mga pamamaraan ng ML upang epektibong magamit ang data na ito; bumuo ng mga kumplikadong distributed system na may kakayahang magproseso ng mga signal ng user at mga bagong unit ng content sa pinakamababang oras; at marami pang ibang gawain.
Sa kasalukuyang sistema, ang disenyo kung saan inilarawan ko, ang kalidad ng mga rekomendasyon para sa gumagamit ay lumalaki kasama ng kanyang aktibidad at haba ng pananatili sa serbisyo. Ngunit siyempre, narito ang pangunahing kahirapan: mahirap para sa sistema na agad na maunawaan ang mga interes ng isang tao na may kaunting pakikipag-ugnayan sa nilalaman. Ang pagpapabuti ng mga rekomendasyon para sa mga bagong user ay ang aming pangunahing layunin. Patuloy naming i-optimize ang mga algorithm upang ang content na nauugnay sa isang tao ay mas mabilis na makapasok sa kanyang feed, at hindi maipakita ang hindi nauugnay na content.
Pinagmulan: www.habr.com