Ang akong ngalan mao si Pavel Parkhomenko, usa ako ka developer sa ML. Niini nga artikulo, gusto nakong hisgutan ang istruktura sa serbisyo sa Yandex.Zen ug ipaambit ang mga pag-uswag sa teknikal, ang pagpatuman niini nagpaposible sa pagdugang sa kalidad sa mga rekomendasyon. Gikan sa kini nga post mahibal-an nimo kung giunsa pagpangita ang labing may kalabutan alang sa tiggamit taliwala sa milyon-milyon nga mga dokumento sa pipila lang ka millisecond; unsaon paghimo sa padayon nga pagkadunot sa usa ka dako nga matrix (nga gilangkuban sa minilyon nga mga kolum ug napulo ka milyon nga mga laray) aron ang mga bag-ong dokumento makadawat sa ilang vector sa napulo ka minuto; unsaon paggamit pag-usab ang user-article matrix decomposition aron makakuha og maayong representasyon sa vector para sa video.
Ang among database sa rekomendasyon naglangkob sa milyon-milyon nga mga dokumento sa lainlaing mga pormat: mga artikulo sa teksto nga gihimo sa among plataporma ug gikuha gikan sa gawas nga mga site, video, mga asoy ug mubu nga mga post. Ang pag-uswag sa ingon nga serbisyo adunay kalabotan sa daghang mga teknikal nga hagit. Ania ang pipila niini:
- Bahina ang mga buluhaton sa pag-compute: buhata ang tanan nga bug-at nga mga operasyon sa offline, ug sa tinuud nga oras himuon ra ang dali nga aplikasyon sa mga modelo aron mahimong responsable sa 100-200 ms.
- Dali nga tagda ang mga aksyon sa tiggamit. Aron mahimo kini, kinahanglan nga ang tanan nga mga panghitabo ipadala dayon sa tigrekomenda ug maimpluwensyahan ang mga sangputanan sa mga modelo.
- Himoa ang feed aron alang sa mga bag-ong tiggamit kini dali nga mopahiangay sa ilang pamatasan. Ang mga tawo nga bag-o lang miapil sa sistema kinahanglan nga mobati nga ang ilang feedback nakaimpluwensya sa mga rekomendasyon.
- Sabta dayon kon kinsay irekomendar ug bag-ong artikulo.
- Pagtubag dayon sa kanunay nga pagtungha sa bag-ong sulud. Napulo ka libo nga mga artikulo ang gipatik kada adlaw, ug daghan niini adunay limitado nga kinabuhi (ingon, balita). Mao kini ang nagpalahi kanila sa mga pelikula, musika ug uban pang dugay ug mahal nga sulod nga himoon.
- Pagbalhin sa kahibalo gikan sa usa ka domain nga lugar ngadto sa lain. Kung ang usa ka sistema sa rekomendasyon adunay gibansay nga mga modelo alang sa mga artikulo sa teksto ug gidugangan namon kini nga video, mahimo namong gamiton pag-usab ang kasamtangan nga mga modelo aron ang bag-ong matang sa sulud mas maayo nga ranggo.
Sultihan ko ikaw kung giunsa namo pagsulbad kini nga mga problema.
Pagpili sa mga kandidato
Giunsa ang pagkunhod sa gidaghanon sa mga dokumento nga gikonsiderar sa libu-libo ka beses sa pipila ka mga millisecond, nga halos walaβy pagkadaot sa kalidad sa ranggo?
Ibutang ta nga nagbansay kami sa daghang mga modelo sa ML, nakamugna og mga bahin base niini, ug nagbansay sa laing modelo nga naghan-ay sa mga dokumento alang sa tiggamit. Maayo ra ang tanan, apan dili nimo makuha ug kuwentahon ang tanan nga mga timailhan alang sa tanan nga mga dokumento sa tinuud nga oras, kung adunay milyon-milyon niini nga mga dokumento, ug ang mga rekomendasyon kinahanglan nga matukod sa 100-200 ms. Ang tahas mao ang pagpili sa usa ka piho nga subset gikan sa milyon-milyon, nga ma-ranggo alang sa tiggamit. Kini nga yugto sagad gitawag nga pagpili sa kandidato. Adunay daghang mga kinahanglanon alang niini. Una, ang pagpili kinahanglan nga mahitabo sa labing madali, aron nga kutob sa mahimo ang nahabilin alang sa ranggo mismo. Ikaduha, nga nakunhuran pag-ayo ang gidaghanon sa mga dokumento alang sa ranggo, kinahanglan namon nga tipigan ang mga dokumento nga may kalabutan sa tiggamit sa hingpit kutob sa mahimo.
Ang among prinsipyo sa pagpili sa kandidato milambo, ug sa pagkakaron nakaabot kami sa multi-stage scheme:
Una, ang tanan nga mga dokumento gibahin sa mga grupo, ug ang labing inila nga mga dokumento gikuha gikan sa matag grupo. Ang mga grupo mahimong mga site, mga hilisgutan, mga cluster. Alang sa matag tiggamit, base sa iyang kasaysayan, ang mga grupo nga labing duol kaniya gipili ug ang labing kaayo nga mga dokumento gikuha gikan kanila. Gigamit usab namo ang kNN index sa pagpili sa mga dokumento nga labing duol sa user sa tinuod nga panahon. Adunay ubay-ubay nga mga pamaagi alang sa pagtukod sa usa ka kNN index; ang amon labing maayo nga nagtrabaho (Hierarchical Navigable Small World graphs). Kini usa ka hierarchical nga modelo nga nagtugot kanimo sa pagpangita sa N nga labing duol nga mga vectors alang sa usa ka tiggamit gikan sa usa ka database nga milyon-milyon sa pipila ka mga millisecond. Una namo nga gi-index ang among tibuok database sa dokumento offline. Tungod kay ang pagpangita sa indeks dali nga molihok, kung adunay daghang mga lig-on nga pag-embed, mahimo ka maghimo daghang mga indeks (usa ka indeks alang sa matag pag-embed) ug ma-access ang matag usa kanila sa tinuud nga oras.
Aduna pa kami'y napulo ka libo nga mga dokumento alang sa matag tiggamit. Daghan pa kini sa pag-ihap sa tanan nga mga bahin, mao nga sa kini nga yugto gigamit namon ang light ranking - usa ka lightweight heavy ranking nga modelo nga adunay gamay nga bahin. Ang tahas mao ang pagtagna kung unsang mga dokumento ang naa sa usa ka bug-at nga modelo sa taas. Ang mga dokumento nga adunay labing taas nga prediktor gamiton sa bug-at nga modelo, nga mao, sa katapusan nga yugto sa ranggo. Kini nga pamaagi nagtugot kanimo sa pagpakunhod sa database sa mga dokumento nga gikonsiderar alang sa user gikan sa minilyon ngadto sa liboan sa napulo ka milliseconds.
ALS nga lakang sa runtime
Giunsa pagkonsiderar ang feedback sa user pagkahuman sa usa ka pag-klik?
Usa ka hinungdanon nga hinungdan sa mga rekomendasyon mao ang oras sa pagtubag sa feedback sa gumagamit. Kini labi ka hinungdanon alang sa mga bag-ong tiggamit: kung ang usa ka tawo nagsugod na sa paggamit sa sistema sa rekomendasyon, nakadawat siya usa ka dili personal nga feed sa mga dokumento sa lainlaing mga hilisgutan. Sa diha nga siya naghimo sa una nga pag-klik, kinahanglan nimo nga hunahunaon dayon kini ug ipahiangay sa iyang mga interes. Kung imong kuwentahon ang tanan nga mga hinungdan sa offline, ang usa ka dali nga tubag sa sistema mahimong imposible tungod sa paglangan. Busa gikinahanglan ang pagproseso sa mga aksyon sa user sa tinuod nga panahon. Alang niini nga mga katuyoan, among gigamit ang ALS nga lakang sa runtime aron magtukod usa ka representasyon sa vector sa tiggamit.
Ibutang nato nga kita adunay representasyon sa vector alang sa tanang mga dokumento. Pananglitan, makahimo kami og mga embeddings offline base sa teksto sa usa ka artikulo gamit ang ELMo, BERT o uban pang mga modelo sa pagkat-on sa makina. Sa unsa nga paagi kita makakuha og representasyon sa vector sa mga tiggamit sa samang luna base sa ilang mga interaksyon sa sistema?
Kinatibuk-ang prinsipyo sa pagporma ug pagkadunot sa user-document matrixIhatag kanamo ang m mga tiggamit ug n mga dokumento. Alang sa pipila nga mga tiggamit, nahibal-an ang ilang relasyon sa pipila nga mga dokumento. Dayon kini nga impormasyon mahimong irepresentar isip m x n matrix: ang mga laray katumbas sa mga tiggamit, ug ang mga kolum katumbas sa mga dokumento. Tungod kay ang tawo wala makakita sa kadaghanan sa mga dokumento, kadaghanan sa mga selula sa matrix magpabilin nga walay sulod, samtang ang uban mapuno. Alang sa matag panghitabo (sama, dili gusto, pag-klik) pipila ka kantidad ang gihatag sa matrix - apan atong tagdon ang usa ka gipasimple nga modelo diin ang usa ka gusto katumbas sa 1, ug ang dili gusto katumbas sa -1.
Atong decompose ang matrix sa duha: P (m x d) ug Q (d x n), diin ang d mao ang dimensyon sa representasyon sa vector (kasagaran gamay nga numero). Unya ang matag butang katumbas sa usa ka d-dimensional nga vector (alang sa usa ka user - usa ka laray sa matrix P, alang sa usa ka dokumento - usa ka kolum sa matrix Q). Kini nga mga vector mao ang mga embeddings sa katugbang nga mga butang. Aron matagna kung gusto ba sa usa ka tiggamit ang usa ka dokumento, mahimo nimo nga padaghanon ang ilang mga embeddings.
Usa sa posible nga mga paagi sa pag-decompose sa usa ka matrix mao ang ALS (Alternating Least Squares). Atong i-optimize ang mosunod nga pagkawala function:
Dinhi ang rui mao ang interaksyon sa user u sa dokumento i, qi ang vector sa dokumento i, pu ang vector sa user u.
Dayon ang kamalaumon nga user vector gikan sa punto sa panglantaw sa mean square error (alang sa fixed document vectors) makita nga analytical pinaagi sa pagsulbad sa katugbang nga linear regression.
Gitawag kini nga "ALS step". Ug ang algorithm sa ALS mismo mao nga magpulipuli kami sa pag-ayo sa usa sa mga matrice (mga tiggamit ug mga artikulo) ug pag-update sa lain, pagpangita sa labing maayo nga solusyon.
Maayo na lang, ang pagpangita sa representasyon sa vector sa tiggamit usa ka paspas nga operasyon nga mahimo sa runtime gamit ang mga panudlo sa vector. Gitugotan ka niini nga limbong nga mahunahuna dayon ang feedback sa gumagamit sa ranggo. Ang parehas nga pag-embed mahimong magamit sa kNN index aron mapauswag ang pagpili sa kandidato.
Giapod-apod nga Collaborative Filtering
Giunsa paghimo ang incremental distributed matrix factorization ug dali nga makit-an ang mga representasyon sa vector sa bag-ong mga artikulo?
Ang sulud dili lamang ang gigikanan sa mga signal sa rekomendasyon. Ang laing importante nga tinubdan mao ang kolaborasyon nga impormasyon. Ang maayo nga ranggo nga mga bahin mahimong tradisyonal nga makuha gikan sa pagkadunot sa user-document matrix. Apan sa pagsulay sa paghimo sa ingon nga pagkadunot, nakasugat kami og mga problema:
1. Kami adunay minilyon nga mga dokumento ug napulo ka milyon nga mga tiggamit. Ang matrix dili hingpit nga mohaum sa usa ka makina, ug ang pagkadunot molungtad og taas nga panahon.
2. Kadaghanan sa sulod sa sistema adunay mubo nga kinabuhi: ang mga dokumento nagpabilin nga may kalabutan sulod lamang sa pipila ka oras. Busa, gikinahanglan ang paghimo sa ilang representasyon sa vector sa labing madali nga panahon.
3. Kung magtukod ka usa ka pagkadunot pagkahuman sa pagmantala sa dokumento, ang igo nga gidaghanon sa mga tiggamit walaβy panahon sa pagtimbang-timbang niini. Busa, ang representasyon sa vector niini lagmit dili kaayo maayo.
4. Kung ang usa ka tiggamit ganahan o dili gusto, dili dayon namo kini mahunahuna sa pagkadunot.
Aron masulbad kini nga mga problema, among gipatuman ang usa ka distributed decomposition sa user-document matrix nga adunay kanunay nga incremental updates. Sa unsang paagiha kini molihok?
Ibutang ta nga kita adunay usa ka pungpong sa N nga mga makina (N anaa sa gatusan) ug kita gusto nga mobuhat sa usa ka distributed decomposition sa usa ka matrix sa kanila nga dili mohaum sa usa ka makina. Ang pangutana kung giunsa paghimo kini nga pagkadunot aron, sa usa ka bahin, adunay igo nga datos sa matag makina ug, sa pikas, aron ang mga kalkulasyon independente?
Atong gamiton ang ALS decomposition algorithm nga gihulagway sa ibabaw. Atong tan-awon kung giunsa pagpatuman ang usa ka lakang sa ALS sa usa ka giapod-apod nga paagi - ang nahabilin nga mga lakang parehas. Ingnon ta nga kita adunay usa ka fixed matrix sa mga dokumento ug gusto namong magtukod ug matrix sa mga tiggamit. Aron mahimo kini, among bahinon kini sa N nga mga bahin pinaagi sa mga linya, ang matag bahin adunay gibana-bana nga parehas nga gidaghanon sa mga linya. Magpadala kami sa matag makina nga walaβy sulod nga mga selyula sa katugbang nga mga laray, ingon man ang matrix sa mga embeddings sa dokumento (bug-os). Tungod kay ang gidak-on niini dili kaayo dako, ug ang user-document matrix kasagaran gamay ra kaayo, kini nga data mohaum sa usa ka regular nga makina.
Kini nga lansis mahimong balik-balikon sa daghang mga panahon hangtod nga ang modelo maghiusa, mag-alternate sa naayos nga matrix sa usa-usa. Apan bisan pa niana, ang pagkadunot sa matrix mahimong molungtad ug daghang oras. Ug dili kini makasulbad sa problema nga kinahanglan nimo nga dali nga makadawat mga embeddings sa mga bag-ong dokumento ug i-update ang mga embeddings nga adunay gamay nga kasayuran sa pagtukod sa modelo.
Ang pagpaila sa paspas nga incremental nga mga update sa modelo nakatabang kanamo. Ingnon ta nga aduna kitay nabansay nga modelo karon. Sukad sa iyang pagbansay, adunay bag-ong mga artikulo nga nakig-uban sa among mga tiggamit, ingon man mga artikulo nga adunay gamay nga interaksyon sa panahon sa pagbansay. Aron dali nga makuha ang mga embeddings sa maong mga artikulo, among gigamit ang user embeddings nga nakuha sa panahon sa unang dako nga pagbansay sa modelo ug naghimo sa usa ka ALS nga lakang aron kuwentahon ang dokumento nga matrix nga gihatag sa usa ka fixed user matrix. Gitugotan ka niini nga makadawat og mga embeddings nga dali - sulod sa pipila ka minuto human mamantala ang dokumento - ug kanunay nga mag-update sa mga embeddings sa bag-ong mga dokumento.
Aron makahimo og mga rekomendasyon diha-diha dayon tagda ang mga aksyon sa tawo, sa panahon sa pagdagan wala kami mogamit sa mga embeddings sa user nga nakuha offline. Hinuon, naghimo kami usa ka lakang sa ALS ug makuha ang aktwal nga vector sa gumagamit.
Pagbalhin sa laing lugar sa domain
Giunsa paggamit ang feedback sa gumagamit sa mga artikulo sa teksto aron makahimo usa ka representasyon sa vector sa usa ka video?
Sa sinugdan, girekomendar lang namo ang mga artikulo sa teksto, mao nga daghan sa among mga algorithm ang gipahaom niining matang sa sulod. Apan kung gidugang ang ubang mga lahi sa sulud, nag-atubang kami sa panginahanglan nga ipahiangay ang mga modelo. Giunsa namo pagsulbad kini nga problema gamit ang usa ka pananglitan sa video? Usa ka kapilian mao ang pagbansay pag-usab sa tanan nga mga modelo gikan sa wala. Apan nagkinahanglan kini og taas nga panahon, ug ang pipila sa mga algorithm nangayo sa gidak-on sa sample sa pagbansay, nga wala pa magamit sa gikinahanglan nga gidaghanon alang sa usa ka bag-ong matang sa sulod sa unang mga gutlo sa kinabuhi niini sa serbisyo.
Miadto kami sa laing paagi ug gigamit pag-usab ang mga modelo sa teksto alang sa video. Ang parehas nga limbong sa ALS nakatabang kanamo sa paghimo og mga representasyon sa vector sa mga video. Nagkuha kami usa ka representasyon sa vector sa mga tiggamit base sa mga artikulo sa teksto ug naghimo usa ka lakang sa ALS gamit ang impormasyon sa pagtan-aw sa video. Mao nga dali ra kaming nakakuha usa ka representasyon sa vector sa video. Ug sa runtime gikalkulo lang namo ang kaduol tali sa user vector nga nakuha gikan sa text articles ug sa video vector.
konklusyon
Ang pagpalambo sa kinauyokan sa usa ka real-time nga sistema sa rekomendasyon naglakip sa daghang mga hagit. Kinahanglan nimo nga dali nga maproseso ang datos ug magamit ang mga pamaagi sa ML aron epektibo nga magamit kini nga datos; magtukod ug komplikadong gipang-apod-apod nga mga sistema nga makahimo sa pagproseso sa mga signal sa tiggamit ug bag-ong mga yunit sa sulod sa labing gamay nga panahon; ug daghan pang mga buluhaton.
Sa kasamtangan nga sistema, ang disenyo nga akong gihulagway, ang kalidad sa mga rekomendasyon alang sa user motubo uban sa iyang kalihokan ug gidugayon sa pagpabilin sa serbisyo. Apan siyempre, dinhi nahimutang ang nag-unang kalisud: lisud alang sa sistema nga masabtan dayon ang mga interes sa usa ka tawo nga adunay gamay nga interaksyon sa sulud. Ang pagpaayo sa mga rekomendasyon alang sa mga bag-ong tiggamit mao ang among panguna nga katuyoan. Magpadayon kami sa pag-optimize sa mga algorithm aron ang sulud nga may kalabotan sa usa ka tawo mas paspas nga makasulod sa iyang feed, ug dili ipakita ang walaβy kalabotan nga sulud.
Source: www.habr.com