Jmenuji se Pavel Parkhomenko, jsem ML vývojář. V tomto článku bych chtěl mluvit o struktuře služby Yandex.Zen a sdílet technická vylepšení, jejichž implementace umožnila zvýšit kvalitu doporučení. Z tohoto příspěvku se dozvíte, jak během několika milisekund najít ty nejrelevantnější pro uživatele mezi miliony dokumentů; jak provést souvislý rozklad velké matice (skládající se z milionů sloupců a desítek milionů řádků) tak, aby nové dokumenty získaly svůj vektor za desítky minut; jak znovu použít rozklad matice uživatel-článek k získání dobré vektorové reprezentace pro video.
Naše databáze doporučení obsahuje miliony dokumentů různých formátů: textové články vytvořené na naší platformě a převzaté z externích stránek, videa, příběhy a krátké příspěvky. Vývoj takové služby je spojen s velkým množstvím technických výzev. Zde jsou některé z nich:
- Rozdělte výpočetní úlohy: provádějte všechny náročné operace offline a v reálném čase provádějte pouze rychlou aplikaci modelů, abyste byli zodpovědní za 100-200 ms.
- Rychle zohledněte akce uživatele. K tomu je nutné, aby všechny události byly okamžitě doručeny doporučovateli a ovlivnily výsledky modelů.
- Udělejte feed tak, aby se novým uživatelům rychle přizpůsobil jejich chování. Lidé, kteří se právě připojili k systému, by měli mít pocit, že jejich zpětná vazba ovlivňuje doporučení.
- Rychle pochopte, komu nový článek doporučit.
- Rychle reagujte na neustálý vznik nového obsahu. Denně vyjdou desítky tisíc článků a mnoho z nich má omezenou životnost (řekněme novinky). To je odlišuje od filmů, hudby a dalšího dlouhodobého a nákladného obsahu.
- Přeneste znalosti z jedné oblasti domény do druhé. Pokud má systém doporučení natrénované modely pro textové články a my k němu přidáme video, můžeme znovu použít stávající modely, aby se nový typ obsahu umístil lépe.
Řeknu vám, jak jsme tyto problémy vyřešili.
Výběr kandidátů
Jak snížit počet posuzovaných dokumentů tisíckrát během několika milisekund a prakticky bez zhoršení kvality hodnocení?
Předpokládejme, že jsme natrénovali mnoho modelů ML, vygenerovali na nich funkce a vytrénovali další model, který řadí dokumenty pro uživatele. Všechno by bylo v pořádku, ale nemůžete jen vzít a vypočítat všechna znamení pro všechny dokumenty v reálném čase, pokud existují miliony těchto dokumentů, a doporučení je třeba vytvořit za 100–200 ms. Úkolem je vybrat z milionů určitou podmnožinu, která se uživateli seřadí. Tato fáze se obvykle nazývá výběr kandidátů. Je na to kladeno několik požadavků. Za prvé, výběr musí proběhnout velmi rychle, aby na samotné hodnocení zbylo co nejvíce času. Za druhé, výrazným snížením počtu dokumentů pro hodnocení musíme co nejúplněji zachovat dokumenty relevantní pro uživatele.
Náš princip výběru kandidátů se vyvinul a v tuto chvíli jsme dospěli k vícefázovému schématu:
Nejprve jsou všechny dokumenty rozděleny do skupin az každé skupiny jsou převzaty nejoblíbenější dokumenty. Skupiny mohou být weby, témata, shluky. Pro každého uživatele se na základě jeho historie vyberou skupiny jemu nejbližší a z nich se převezmou nejlepší dokumenty. Pomocí kNN indexu také vybíráme dokumenty, které jsou uživateli nejblíže v reálném čase. Existuje několik metod pro konstrukci indexu kNN (Hierarchical Navigable Small World grafy). Jedná se o hierarchický model, který vám umožňuje najít N nejbližších vektorů pro uživatele z databáze milionů během několika milisekund. Nejprve indexujeme celou naši databázi dokumentů offline. Protože vyhledávání v indexu funguje poměrně rychle, pokud existuje několik silných vložení, můžete vytvořit několik indexů (jeden index pro každé vložení) a přistupovat ke každému z nich v reálném čase.
Stále máme desítky tisíc dokumentů pro každého uživatele. To je ještě hodně, abychom spočítali všechny funkce, takže v této fázi používáme lehké hodnocení - lehký těžký model s menším počtem funkcí. Úkolem je předpovědět, jaké dokumenty bude mít těžký model nahoře. Dokumenty s nejvyšším prediktorem budou použity v těžkém modelu, tedy v poslední fázi hodnocení. Tento přístup umožňuje zmenšit databázi dokumentů zvažovaných pro uživatele z milionů na tisíce během desítek milisekund.
Krok ALS za běhu
Jak zohlednit zpětnou vazbu uživatelů ihned po kliknutí?
Důležitým faktorem v doporučeních je doba odezvy na zpětnou vazbu od uživatelů. To je důležité zejména pro nové uživatele: když člověk právě začne používat systém doporučení, obdrží nepersonalizovaný zdroj dokumentů různých témat. Jakmile udělá první klik, musíte to okamžitě vzít v úvahu a přizpůsobit se jeho zájmům. Pokud vypočítáte všechny faktory offline, rychlá reakce systému bude nemožná kvůli zpoždění. Je tedy nutné zpracovávat uživatelské akce v reálném čase. Pro tyto účely používáme krok ALS za běhu k vytvoření vektorové reprezentace uživatele.
Předpokládejme, že máme vektorovou reprezentaci pro všechny dokumenty. Můžeme například vytvářet vložení offline na základě textu článku pomocí ELMo, BERT nebo jiných modelů strojového učení. Jak můžeme získat vektorovou reprezentaci uživatelů ve stejném prostoru na základě jejich interakcí v systému?
Obecný princip tvorby a dekompozice matice uživatel-dokumentMějme m uživatelů a n dokumentů. U některých uživatelů je znám jejich vztah k určitým dokumentům. Tyto informace pak mohou být reprezentovány jako matice mxn: řádky odpovídají uživatelům a sloupce odpovídají dokumentům. Vzhledem k tomu, že osoba neviděla většinu dokumentů, většina buněk matrice zůstane prázdná, zatímco ostatní budou vyplněny. Pro každou událost (líbí se mi, nelíbí se, kliknutí) je v matici uvedena nějaká hodnota – ale uvažujme zjednodušený model, ve kterém hodnocení Líbí se odpovídá 1 a Nelíbí odpovídá –1.
Rozložme matici na dvě: P (mxd) a Q (dxn), kde d je rozměr vektorové reprezentace (obvykle malé číslo). Potom bude každý objekt odpovídat d-rozměrnému vektoru (pro uživatele - řádek v matici P, pro dokument - sloupec v matici Q). Tyto vektory budou vnořením odpovídajících objektů. Chcete-li předpovědět, zda se uživateli bude dokument líbit, můžete jednoduše znásobit jeho vložení.
Jedním z možných způsobů rozkladu matice je ALS (Alternating Least Squares). Optimalizujeme následující ztrátovou funkci:
Zde rui je interakce uživatele u s dokumentem i, qi je vektor dokumentu i, pu je vektor uživatele u.
Poté je analyticky nalezen optimální uživatelský vektor z hlediska střední kvadratické chyby (pro fixní vektory dokumentů) řešením odpovídající lineární regrese.
Toto se nazývá „krok ALS“. A samotný algoritmus ALS spočívá v tom, že střídavě opravujeme jednu z matic (uživatele a články) a aktualizujeme druhou, přičemž najdeme optimální řešení.
Naštěstí je nalezení uživatelské vektorové reprezentace poměrně rychlá operace, kterou lze provést za běhu pomocí vektorových instrukcí. Tento trik vám umožní okamžitě zohlednit zpětnou vazbu od uživatelů při hodnocení. Stejné vložení lze použít v indexu kNN ke zlepšení výběru kandidátů.
Distribuované kolaborativní filtrování
Jak provést inkrementální rozklad distribuované matice a rychle najít vektorové reprezentace nových článků?
Obsah není jediným zdrojem signálů doporučení. Dalším důležitým zdrojem jsou informace o spolupráci. Dobré klasifikační vlastnosti lze tradičně získat dekompozicí matice uživatel-dokument. Ale při pokusu o takový rozklad jsme narazili na problémy:
1. Máme miliony dokumentů a desítky milionů uživatelů. Matrice se nevejde úplně na jeden stroj a rozklad bude trvat velmi dlouho.
2. Většina obsahu v systému má krátkou životnost: dokumenty zůstávají relevantní pouze několik hodin. Proto je nutné co nejrychleji zkonstruovat jejich vektorovou reprezentaci.
3. Pokud vytvoříte rozklad ihned po zveřejnění dokumentu, dostatečný počet uživatelů nestihne jej vyhodnotit. Jeho vektorová reprezentace tedy s největší pravděpodobností nebude příliš dobrá.
4. Pokud se to uživateli líbí nebo nelíbí, nebudeme to moci okamžitě zohlednit při rozkladu.
K vyřešení těchto problémů jsme implementovali distribuovanou dekompozici matice uživatel-dokument s častými přírůstkovými aktualizacemi. Jak přesně to funguje?
Předpokládejme, že máme shluk N strojů (N je ve stovkách) a chceme na nich provést distribuovaný rozklad matice, která se na jeden stroj nevejde. Otázkou je, jak tento rozklad provést, aby jednak bylo na každém stroji dostatek dat a jednak aby výpočty byly nezávislé?
Použijeme výše popsaný algoritmus rozkladu ALS. Podívejme se, jak provést jeden krok ALS distribuovaným způsobem - ostatní kroky budou podobné. Řekněme, že máme pevnou matici dokumentů a chceme sestavit matici uživatelů. K tomu jej rozdělíme na N částí po řádcích, každá část bude obsahovat přibližně stejný počet řádků. Každému stroji zašleme neprázdné buňky odpovídajících řádků a také matici vložení dokumentu (celou). Protože jeho velikost není příliš velká a matice uživatelských dokumentů je obvykle velmi řídká, vejdou se tato data na běžný stroj.
Tento trik lze opakovat v několika epochách, dokud model nekonverguje, přičemž se pevná matice střídá jednu po druhé. Ale i tak může rozklad matrice trvat několik hodin. A to neřeší problém, že potřebujete rychle přijímat vložení nových dokumentů a aktualizovat vložení těch, o kterých bylo při sestavování modelu málo informací.
Pomohlo nám zavedení rychlých inkrementálních aktualizací modelu. Řekněme, že máme aktuálně trénovaný model. Od jejího školení se objevily nové články, se kterými naši uživatelé interagovali, a také články, které byly během školení málo interagovány. Abychom rychle získali vložení takových článků, používáme uživatelská vložení získaná během prvního velkého trénování modelu a provedeme jeden krok ALS k výpočtu matice dokumentu s pevnou uživatelskou maticí. To vám umožňuje přijímat vložené položky poměrně rychle – během několika minut po publikování dokumentu – a často aktualizovat vložení posledních dokumentů.
Aby doporučení okamžitě zohledňovala lidské činy, nepoužíváme za běhu uživatelská vložení získaná offline. Místo toho uděláme krok ALS a získáme skutečný uživatelský vektor.
Přeneste se do jiné oblasti domény
Jak využít zpětnou vazbu od uživatelů k textovým článkům k vytvoření vektorové reprezentace videa?
Zpočátku jsme doporučovali pouze textové články, takže mnoho našich algoritmů je přizpůsobeno tomuto typu obsahu. Při přidávání dalších typů obsahu jsme ale stáli před nutností přizpůsobit modely. Jak jsme tento problém vyřešili pomocí příkladu videa? Jednou z možností je přeškolit všechny modely od začátku. To ale trvá dlouho a některé algoritmy jsou náročné na velikost trénovacího vzorku, který v prvních okamžicích jeho životnosti ve službě ještě není k dispozici v potřebném množství pro obsah nového typu.
Šli jsme jinou cestou a znovu jsme použili textové modely pro video. Stejný trik ALS nám pomohl vytvořit vektorové reprezentace videí. Vzali jsme vektorovou reprezentaci uživatelů na základě textových článků a provedli jsme krok ALS pomocí informací o zobrazení videa. Snadno jsme tedy získali vektorovou reprezentaci videa. A za běhu jednoduše vypočítáme blízkost mezi uživatelským vektorem získaným z textových článků a vektorem videa.
Závěr
Vývoj jádra systému doporučení v reálném čase zahrnuje mnoho výzev. Potřebujete rychle zpracovat data a aplikovat metody ML, abyste tato data efektivně využili; vybudovat komplexní distribuované systémy schopné zpracovat uživatelské signály a nové jednotky obsahu v minimálním čase; a mnoho dalších úkolů.
V současném systému, jehož design jsem popsal, roste kvalita doporučení pro uživatele spolu s jeho aktivitou a délkou setrvání ve službě. Zde však samozřejmě leží hlavní problém: pro systém je obtížné okamžitě porozumět zájmům osoby, která má malou interakci s obsahem. Naším hlavním cílem je zlepšit doporučení pro nové uživatele. Budeme pokračovat v optimalizaci algoritmů, aby se obsah, který je pro člověka relevantní, dostal do jeho zdroje rychleji a nezobrazoval se irelevantní obsah.
Zdroj: www.habr.com
